The Taub Faculty of Computer Science Events and Talks

To support the growing need for Internet bandwidth, contemporary backbone routers and switches operate with an external rate of 20 GB/s and hundreds of ports. At the same time, applications with stringent quality of service (QoS) requirements demand powerful control mechanisms, such as packet scheduling and queue management algorithms. In this talk we discuss an analytic methodology for evaluating such switches by a worst-case comparison of the switch performance relative to an ideal output-queued switch, with no limitations and no stochastic assumptions on the arrival process. This competitive approach is natural due to the central role of incomplete knowledge. It reveals the strengths and weaknesses of the studied mechanisms and indicates important design choices. The talk demonstrates this methodology in the context of two different switch architectures. The first example deals with parallel packet switches (PPS) in which cells are switched in parallel through intermediate slower switches. We study the affect of this parallelism on the overall performance and present tight bounds on the average queuing delay introduced by the switch relative to an ideal output-queued switch. Our lower bounds hold even if the algorithm in charge of balancing the load among middle-stage switches is randomized. In the second example, we study how variable-size packets can be scheduled contiguously without segmentation and reassembly in a combined input-output queued (CIOQ) switch. This mode of scheduling becomes very attractive recently, since most common network protocols (e.g., IP) work with variable size packets. We present frame-based schedulers that allow a packet-mode CIOQ switch with small speedup to mimic an ideal output-queued switch with bounded relative queuing delay. The schedulers are pipelined and are based on matrix decompositions. The talk is self-contained and does not assume prior knowledge.