Combinatorial design of congestion-free networks
Authors:
- 1 January 1997
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 5 (6) , 989-1000
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 net- works. It is shown that the bound on the maximum route length, under the two constraints, is for an -node network. This sublinear bound facilitates the throughput scalability prop- erty.Keywords
This publication has 10 references indexed in Scilit:
- Fault-Tolerant Convergence RoutingJournal of Parallel and Distributed Computing, 1997
- METANET: principles of an arbitrary topology LANIEEE/ACM Transactions on Networking, 1995
- Routing and flow control on the MetaNet: an overviewComputer Networks and ISDN Systems, 1994
- MetaRing-a full-duplex ring with fairness and spatial reuseIEEE Transactions on Communications, 1993
- Combinatorial Theory1988
- A survey of multi-connected loop topologies for local computer networksComputer Networks and ISDN Systems, 1986
- Reliable Loop Topologies for Large Local Computer NetworksIEEE Transactions on Computers, 1985
- Architecture and Design of a Reliable Token-Ring NetworkIEEE Journal on Selected Areas in Communications, 1983
- EthernetCommunications of the ACM, 1976
- An experimental distributed switching system to handle bursty computer traffic1969