Design and analysis of scheduling and queue management schemes for high performance switches and routers

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 high throughput and quality services to today's Internet users. In this thesis, we design and analyze fast and efficient scheduling algorithms and fair queuing management schemes for routers and switches to achieve the above objectives.;First, we prove 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 model a particular class of scheduling problems as Batch Scheduling to relax the scheduling time constraint, and we examine its on-line competitiveness. Two randomized algorithms are proposed and evaluated by both approximation ratios and simulation. In particular, 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 flows 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 analysis and simulation experimentation show that the algorithms are able to maintain fairness among the flows by mitigating these effects.