Topological design of loss-free switch-based LANs
Bülent Yener, Y. Ofek, Moti M. Yung · 2002
The paper presents a new design methodology and tools to construct a switch-based LAN with (i) scalable throughput, (ii) no loss due to congestion, and (iii) two routing modes: FIFO or non-FIFO. More specifically, given a bounded degree (number of switch ports) at each node, the design is based on the construction of multiple virtual rings under the following constraints: (i) the virtual rings are pairwise edge-disjoint, and (ii) 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 objectives of the above two constraints are (i) to ensure no loss due to congestion inside the network of bursty traffic sources, and (ii) to ensure convergence of packets/cells to their destinations. The virtual rings are constructed by a new methodology that employs combinatorial block designs together with a new algorithm for realizing any size networks. It is shown that the bound on the maximum route length, under the two constraints, is O(/spl radic/N) for an N-node network.