טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentHay David
SubjectCompetitive Evaluation of Switch Architectures
DepartmentDepartment of Computer Science
Supervisor Professor Hagit Attiya
Full Thesis textFull thesis text - English Version


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 methodologies 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.