MPhil Thesis Defence


"High-Performance Scheduling Algorithms for Buffered Crossbar Switches"

By

Mr. Lotfi Mhamdi


Abstract

Until recently, Internet routers and ATM switches were traditionally built
around a central pool of shared memory buffers and a fast shared-bus
backplane. However two main challenges have evolved out of the limitations
in memory bandwidth and interconnect technology:  queue management and
packet forwarding. Input queued crossbar-based switches  (IQ) have largely
been considered as a solution since they improve distribution of memory
over each switch input and for their effective simultaneous transfer of
packets due to the switched backplane. Input queued switches have gained
heightened interest and demand, since they have low hardware requirements.
The difficulty lies in the ability to design fast and simple schedulers to
support the growing diversity of services, the Internet is expected to
provide, continually making it harder for IQ switches to keep pace with
the tremendous growth of the Internet. To meet these new demands, careful
designs of the switching fabric, buffer architecture, and switching
algorithms centered around IQ switches cannot be undertaken in order to
reach aggregate data rates of multiple terabits per second and forwarding
rates of billions of packets per second.

In this thesis, we explore the basic architecture of routers and different
types of switch fabrics. This includes IQ switches, combined input and
output queued switches (CIOQ) and output queued switches  (OQ)
architectures.  IQ switches and CIOQ switches architectures are based on
the Virtual Output Queuing (VOQ) architecture. The two basic performance
metrics for switches are throughput and delay respectively. They depend on
both architecture choice and the scheduling policy. It is the main purpose
of this thesis, to address the two important issues of throughput and
delay. We investigate an efficient switching architecture, along with a
variety of scheduling algorithms, to achieve the above-mentioned goals in
a Gigabit/Terabit networking environment. The investigated architecture,
based on a one cell internally buffered crossbar switch, along with the
input VOQ architecture, improves the throughput of the switch and reduces
the delay imultaneously.  We illustrate its substantial advantages by
making comparisons to the IQ crossbar based switches. We then propose a
wide class of distributed scheduling algorithms and closely study their
performance and stability properties. We then propose a class of practical
scheduling algorithms that can be implemented in real-time for high input
traffic. We also show how their distributed nature makes them desirable
and in high demand for such ultra-capacity networks.


Date:			Thursday, 15 August 2002

Time:			10:00a.m.-12:00noon

Venue:			Room 2303
			Lifts 17-18

Committee Members:		Dr. Mounir Hamdi (Supervisor)
			Dr. Brahim Bensaou (Chairman)
			Dr. Chi-Ying Tsui (ELEC)


**** ALL are Welcome ****