In this paper we present a novel design technique, and combined routing and flow control algorithms, for congestion-free packet switched networks.
The design is based on the construction of multiple virtual rings, under the constraint that the path between any two nodes is either confined to a single ring, or traverses exactly two rings (passing through a single bridge node).
Our best designs are constructed by using Finite Generalized Quadrangles of combinatorial design theory, together with a scaling algorithm for realizing networks of arbitrary size. The target topology is obtained by taking the edge union of the multiple virtual rings.
Capitalizing on the underlying topological properties, we design routing, flow and access control protocols. We prove that the proposed network architecture, coupled with our protocols, ensures that (i) no loss due to congestion occurs inside a network, under arbitrary traffic patterns; (ii) all the packets reach their destinations within bounded time; and (iii) the bandwidth is allocated fairly and no host is starved.
Moreover, we achieve these desirable properties much more efficiently than earlier proposals. Our best designs have a maximum route length of O(N^{1/3}) and require O(N^{1/3}) ports to be used at each node for an N-node network. The designs attain these bounds while manifesting a high degree of redundancy, with multiple disjoint paths between all pairs of nodes. This significantly improves upon the designs of [YOY94b,YOY98], where both the route length and number of ports are Omega(sqrt(N)), and only a single path exists between every pair of nodes.
We also provide a theoretical bound for the impact of fairness and congestion-freeness on netwok utilization. We used this design technique to generate network designs of various sizes. We then implemented our protocols and verified their performance by simulations.
DIMACS Home Page