About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
IEEE/ACM Transactions on Networking
Paper
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.