COMBINATORIAL DESIGN OF CONGESTION-FREE NETWORKS

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) th e aggregate throughput is scalable and 2) there is no packet loss with in the subnet. More specifically, given a bounded number of ports in e very switching node, the design is based on the construction of multip le 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 ed ge 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 vir tual rings are constructed by using combinatorial block designs togeth er 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(root N) for an N-node network, This sublinear bound facilitates the throughput scalability property.