The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


"Design and Analysis of Scheduling and Queue Management Schemes
for High Performance Switches and Routers"

By

Mr. Zhen Zhou


Abstract

The growth of today's Internet has been constrained substantially by the
performance of interconnecting routers and switches.  High performance
routers and switches rely heavily on scheduling and queuing technologies
in order to provide quality services to today's Internet users.  In this
thesis, we have designed and analyzed fast and efficient scheduling
algorithms and fair queuing management schemes for routers and switches.

We commenced by proving the theoretical limitations on the queuing lengths
in the framework of on-line switching scheduling with Virtual Output
Queuing.  Those bounds determine the size of the memory that must be
allocated to switch ports without knowing the future traffic in order to
avoid packet loss.

We then modelled a particular class of scheduling problem as Batch
Scheduling to relax the scheduling time constraint; and its on-line
competitiveness is examined. Two randomized algorithms are proposed and
evaluated by both approximation ratios and simulation. Batch Scheduling
algorithms find their practical significance when facing the challenges of
optical switch scheduling. Two deterministic batch scheduling algorithms
of different paradigms are proposed for optical switching. A third
deterministic algorithm explores the asynchronous property of optical
fabrics and overcomes the reconfiguration delays.

Internet research stresses more and more on the quality of service
provided to the network end users rather than engineering realization of
service implementation. We studied the problem of flow splitting where
some sources intend to acquire more link resources than their fair share
by splitting their flow into many parallel flows, which results in unfair
resource allocation to the other sources on the bottleneck link. We have
devised active queue management algorithms according to our theoretical
analysis to detect and counteract the effects of these so called ``Network
Ants''. Technical realization and simulation results show that the
algorithms are able to maintain fairness among the flows by mitigating
these effects.


Date:			Monday, 20 August 2007

Time:			2:00p.m.-4:00p.m.

Venue:			Room 3501
			Lifts 25-26

Chairman:		Prof. Guochen Jia (CHEM)

Committee Members:	Prof. Mordecai Golin (Supervisor)
			Prof. Mounir Hamdi (Supervisor)
			Prof. Jogesh Muppala
			Prof. Qian Zhang
			Prof. Khaled Ben Letaief (ECE)
			Prof. Jack Lee (Inf. Engg., CUHK)


**** ALL are Welcome ****