Efficient network architectures and switch fabrics for packet routing

We exploit a universal property of networks to find two most efficient network architectures. A network is universal if it can simulate, in routing packets, any other network of the same area A with a polylogarithmic overhead in terms of A. The area is perceived as the area of a solid chip into which the networks are fitted and in which the node and link patterns of the networks are preserved. The two architectures, the augmented fat-stack and the general fat-stack, are universal for an O(log A) and an O( log32 ) overhead respectively. We found that each of the fat-stack variants is the minimal universal network for its respective overhead, which implies that each one is not only efficient but also the simplest for that efficiency level. The augmented fat-stack is shown to perform better than the fat-tree and almost as well as the fat-pyramid in both delay and throughput. The general fat-stack has to be scaled up from the VLSI scale to represent a large-scale distributed network. For that, we proved a general theorem which states that asymptotically, a network's routing efficiency does not change with increased link lengths any more than necessitated by longer link delays.; We propose four switch fabric schedulers and their supporting architectures for input-queued switches and analyze them theoretically and experimentally. These schedulers find a maximum matching in a single iteration and have a time complexity of O(1). They are many times faster and have better throughput and lower complexity than existing algorithms. The SRA schedulers support both best-effort and quality of service traffic. The weighted SRA+ schedulers operate on arbitrary cells and packet-bounded cells to support quality of service. The schedulers sustain 100% throughput. They provide exact bandwidth guarantee and low delay bound in ensuring quality of service. New scalable architectures are designed to purposely and perfectly support these schedulers. The resultant switch fabrics are scalable in that their performance does not degrade with increased switch size and they can be implemented in simple hardware. They represent innovative and better solutions to the switching problem and exemplary designs for future-generation input-queued switches.