Scalable Algorithms for Communication Networks.

Abstract

Network scalability has emerged as the essential problem in designing architectures and protocols for large-scale communication systems. Minor efficiencies, that can be tolerated in small networks, can accumulate and become a dominant factor determining the performance of large networks. In this thesis, we consider three problems that are related to scalability. First, we examine the size of routing tables as the number of nodes in the network increases. It is shown that the widely used shortest-path and straightline routing algorithm can be implemented only when nodes’ memory increases with the network size. On the other hand, it is established that there exist information-efficient algorithms, e.g., column-first routing protocol, that route packets correctly even if each node in the network is capable of storing information on a fixed number of destinations only. In the second part, we present a novel computational model utilizing time encoding, that enables a distributed scheduling mechanism. The scheduling algorithm we propose achieves performance comparable to centralized algorithms under uniform traffic. Exploiting a connection between switch scheduling and interval packing, we argue that the distributed nature of the algorithm limits the maximum relative load to 1 − e^−2 under the worst-case scenario. The stability of the algorithm can be improved by enabling reversibility in distributed decision making. Finally, we discuss the bandwidth sharing problem for multi-hop networks. A buffer management policy that utilizes only simple packet attributes delivers a constant fraction of the maximum possible throughput. Moreover, the policy is robust to heavy traffic loads in the sense that the throughput does not degrade due to congestion.