Technical Report PHD-2007-06

Title: Competitive Evaluation of Switch Architectures
Authors: David Hay
Supervisors: Hagit Attiya
Abstract: To support the growing need for Internet bandwidth, contemporary backbone routers and switches operate with an external rate of 40 GB/s and hundreds of ports. At the same time, applications with stringent quality of service (QoS) requirements call for powerful control mechanisms, such as packet scheduling and queue management algorithms.

The primary goal of our research is to provide analytic ethodologies for designing and evaluating high-capacity high-speed switches. A unique feature of our approach is a worst-case comparison of switch performance relative to an ideal switch, with no limitations. This competitive approach is natural due to the central role of incomplete knowledge, and it can reveal the strengths and weaknesses of the studied mechanisms and indicate important design choices.

We first consider the parallel packet switch (PPS) architecture in which cells are switched in parallel through intermediate slower switches. We study the effects 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.

We also 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 became 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.

A slightly different line of research involves studying how different QoS measures can be guaranteed in a stand-alone environment, where traffic arrives to a regulator that should shape it to meet the demand. We focus on jitter regulators, which should shape the incoming traffic to be perfectly periodic and show upper and lower bounds for multiple stream jitter regulation: In the offline setting, jitter regulation can be solved in polynomial time, while in the online setting a buffer augmentation is needed in order to compete with the optimal algorithm; the amount of buffer augmentation depends linearly on the number of streams.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2007
To the main CS technical reports page

Computer science department, Technion