Combinatorial design of congestion-free networks

Abstract

This paper presents a new design methodology and tools to construct a packet switched network with bursty data sources. This network design combines two important properties for arbitrary traffic pattern: 1) the aggregate throughput is scalable and 2) there is no packet loss within the subnet. More specifically, given a bounded number of ports in every switching node, the design is based on the construction of multiple virtual rings under the following constraints: 1) the virtual rings are pairwise edge-disjoint and 2) there is at least one virtual ring between any pair of nodes. The target topology is obtained from the edge union of the multiple virtual rings. The two constraints ensure no loss due to congestion inside a network with arbitrary traffic pattern and that packets will reach (or converge) their destinations. The virtual rings are constructed by using combinatorial block designs together with an algorithm for realizing any size networks. It is shown that the bound on the maximum route length, under the two constraints, is O(√N) for an N-node network. This sublinear bound facilitates the throughput scalability property. © 1997 IEEE.