David Hay, Ph.D. Thesis Seminar
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
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.