Combinatorial design method and apparatus for multi-ring...

Details Combinatorial design method and apparatus for multi-ring... Combinatorial design method and apparatus for multi-ring...

1999-01-05

2003-05-13

Chin, Wellington (Department: 2664)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S452000

Reexamination Certificate

active

06563833

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to a system for designing multi-ring networks, and more particularly, to a system for designing multi-ring networks based on a combinatorial design theory.
BACKGROUND OF THE INVENTION
The ever-increasing growth of data traffic and the associated bandwidth requires careful design and planning of the infrastructures of next-generation networks. The underlying network infrastructure directly determines how well the routing, flow and access control protocols perform. Thus, the design of the network infrastructure, as well as the routing and network control protocols, should be addressed as a combined problem.
The integrated design approach for network infrastructure and network control protocols should produce a network that exhibits low packet loss as well as throughput scalability. Current network designs do not ensure both of these properties simultaneously. Networks with a simple network topology, such as a bus or a ring architecture, are not throughput scalable. Likewise, networks with an Internet-like topology are throughput scalable, but they typically do not exhibit low packet loss.
A popular building block for network design is a ring network topology, such as those used in local area network (LAN) environments. A multi-ring topology is the backbone topology of choice in the Synchronous Optical Network (SONET) standard and in telecommunication infrastructure networks. Traditional approaches to the design of multi-ring networks either face computationally hard problems, or use heuristic methods with approximate answers. A multi-ring network design should exhibit small rings, thereby providing low propagation delay, and low degree (the number of rings a node belongs to). Typically, there is a trade-off between the ring size and the node degree.
Well-known combinatorial design theory (CDT) principles were first applied to multi-ring network designs in B. Yener et al., “Topological Design of Loss-Free Switch-Based LANs,” IEEE INFO-COM '94, (1994) and B. Yener et al., “Combinatorial Design of Congestion-Free Networks,” Transactions on Networking, Vol. 5, No. 6, 989-1000 (December, 1997), collectively, referred to herein as the “BIBD Systems.” The BIBD Systems use balanced incomplete block designs (BIBDs) to obtain congestion-free multi-ring networks with scalable throughput. The BIBD Systems include networks in which the maximum route length and the maximum degree are both bounded by a value on the order of the square root of N, in an N-node network. These bounds are similar to those of earlier approaches to multi-ring network design, such as chordal rings, or ring-connected rings, with the additional property of congestion-free routing.
A need exists for a method and apparatus for designing multi-ring networks that are throughput scalable, so that new nodes or links can be added without decreasing the throughput. In addition, a further need exists for multi-ring networks that provide congestion-free routing with improved bounds on the maximum route length and the node degree.
SUMMARY OF THE INVENTION
Generally, a method and apparatus are disclosed for designing multi-ring networks based on combinatorial design theory. According to one aspect of the invention, multi-ring networks are constructed using generalized quadrangles of combinatorial design theory, together with a scaling algorithm for realizing networks of arbitrary size. Initially, generalized quadrangles are used to obtain a network of multiple rings where 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 (giving low propagation delay) and low degree, while also permitting efficient congestion-free flow control protocols. Multi-ring networks designed using generalized quadrangles have additional symmetry properties that are useful for routing protocols. If a first node needs to send a packet to a second node, and they are not neighbors, then the first node can select any of the rings that the first node is a member of, and place the packet on this ring. On each of the first node's rings, there exists a bridge node that also belongs to one of the second node's rings and the bridge node is capable of bridging the packet to its destination. Thus, using a generalized quadrangle as the underlying design of the network provides a great deal of flexibility in a routing protocol.
According to further aspects of the invention, 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 packet can be placed on any arbitrary ring, and the packet will arrive at the destination node. 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
i
, that the node belongs to, during any cycle. A node can send packets as long as the quota counter is positive, and the counter is decremented for every packet sent.
According to a further aspect of the invention, a set of flow control buffers, consisting of a local queue, LQ
i
, a remote queue, RQ
ij
(x), and a buffer queue, BQ
ij
, and a flow control quota matrix, Q
i
, are utilized to implement a flow control mechanism. The access control technique ensures that local traffic is congestion free, since packets are not dropped while they are on a single ring. In addition, the one-bridge property of the present invention ensures that a remote packet needs to cross only one bridge, so only a single bridge buffer may overflow along the path of a packet. Furthermore, the bridge node shares a ring with the source node. Thus, feedback is provided to all the sources on a ring, in the form of a circulating quota-matrix, Q
i
. The quota-matrix, Q
i
, allows the source nodes to slow down transmissions when the bridge buffers are close to capacity.
Flow control is implemented using a system of quotas that govern the service rates for the different flow queues. The quotas are in units of packets that a node can transmit during a cycle rotation time, D. Since local traffic does not pose a buffer overflow problem, a specific quota is not imposed on the local queue, LQ (other than the general access control quota, k). A node is allowed to transmit at most r
u
ij
(x) packets per cycle out of each remote buffer RQ
ij
(x).
The r
u
ij
(x) quotas are modified adaptively by a combined routing, flow and access process. Generally, as a buffer queue, BQ
ij
, at a bridge node, x, is filled, the bridge node adaptively reduces the r
u
ij
(x) quotas of all the other nodes on a ring, R
i
. The buffer queues, BQ
ij
, are managed by circulating a quota matrix, Q
i
, on each ring, R
i
. The quota matrix, Q
i
, contains entries indicating the total number of packets that each node is willing to bridge from rings R
i
to R
j
.
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. In addition, the disclosed multi-ring networks guarantee convergence and are throughput scalable, so that adding new nodes or links will not decrease the throughput.
The multi-ring networks of the present invention exhibit a maximum route length on the order of N
⅓
(where N is the number of nodes) and have a degree (number of ports per node) on the order of N
⅓
as well. In addition, the multi-ring networks require a total number of links on the order of N
{fraction (4/3)}
, which is less than the

Affiliated with

Also associated with

Rating

Combinatorial design method and apparatus for multi-ring... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Combinatorial design method and apparatus for multi-ring..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Combinatorial design method and apparatus for multi-ring... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3036078