Combinatorial design method and apparatus for multi-ring networks with combined routing and flow control

Abstract

A method and apparatus are disclosed for designing multi-ring networks based on generalized quadrangles of combinatorial design theory, together with a scaling algorithm for realizing networks of arbitrary size. Multi-ring networks based on generalized quadrangles ensures 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), referred to herein as the “one-bridge property.” The one-bridge property allows the construction of networks with small rings and low degree, while also permitting efficient congestion-free flow control protocols. Routing, access and flow control protocols are provided for the multi-ring network that capitalize on the combinatorial properties of the disclosed multi-ring networks. A “self-routing” routing protocol is disclosed wherein a source node does not need to know how to route a packet to a destination node that is not a neighbor. The access control mechanism disclosed herein utilizes a quota counter, k, and allows each node to transmit up to the predefined quota of k packets on each ring, R , that the node belongs to, during any cycle. A set of flow control buffers, consisting of a local queue, LQ , a remote queue, RQ (x), and a buffer queue, BQ , and a flow control quota matrix, Q , are utilized to implement a flow control mechanism. The routing, flow and access control protocols, together with the disclosed network architecture, ensure that (i) no loss due to congestion occurs inside a network, under arbitrary traffic patterns; (ii) all the packets reach their destinations within a bounded time; and (iii) the bandwidth is allocated fairly and no host is starved.