Randomization and heavy traffic theory: New approaches to the design and analysis of switch algorithms.

摘要

This thesis addresses the design and analysis of implementable high-performance algorithms for high speed data networks, such as the Internet. Our focus is on designing scheduling algorithms for crossbar switches. We exhibit a natural tradeoff between implementational simplicity and goodness of performance for scheduling algorithms operating in very high speed switches. Our goal will be to resolve this tradeoff using novel design methods which involve randomization on the one hand; and to develop new methods to analyze the performance of these algorithms on the other. Along these lines, this thesis has two main parts.; The first part is motivated by the following considerations. The scheduler of a high speed switch poses challenging problems to the algorithm designer. It needs to provide a good performance even though scheduling decisions need to be made in a very limited time and while utilizing meagre computational resources. To illustrate, a switch in the Internet core operates at a line rate of 10 Gbps. This implies that scheduling decisions need to be made roughly every 50 ns. Complicated algorithms cannot be designed to operate at this speed; only the simplest algorithms are implementable. But a simple algorithm may perform rather poorly, if it is not well-designed.; We choose randomization as a central tool to design simple, high-performance switch schedulers. This choice affords us the ability to exploit several desirable features of randomized algorithms: simplicity, good performance, robustness, and the possibility of derandomization for eventual implementation. Specifically, we exhibit three algorithms that exhibit these features.; Our second contribution is a new approach for analyzing the delay induced by a switch scheduling algorithm. Traditional methods, based largely on queueing and large deviation theories, are inadequate for the purpose of analyzing the delays induced by switch schedulers. We adopt a different strategy based on Heavy Traffic Theory which advances our understanding of delay in the following two senses. First, it leads to the characterization of a delay-optimal scheduling algorithm. Second, it helps explain some intriguing observations other researchers have made through simulation-based studies about the delay of scheduling algorithms.