Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing
Reexamination Certificate
1999-06-02
2003-05-20
Trammell, James P. (Department: 3621)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
C710S260000, C710S268000, C709S242000, C709S244000, C709S239000
Reexamination Certificate
active
06567856
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to data processing systems and, more particularly, to deadlock-free routing.
BACKGROUND OF THE INVENTION
Networks comprise a number of nodes that are interconnected via links. As used herein, the term “node” refers to any device capable of communicating, such as a computer, router, switch, network processor, or symmetric multi-processor. The specific configuration of nodes and links in a network is referred to as the “network topology.”
Each node routes network traffic by interacting with internal buffers that store packets. Specifically, each of a node's links typically has an associated buffer (“receive buffer”) that temporarily stores packets received via the link, and each of a node's links typically has an associated buffer (“send buffer”) that temporarily stores packets before they are sent across the link. When a packet is received by a node that is not its destination, the packet arrives in one of the node's receive buffers. The node then determines which link to send the packet over using a routing algorithm. After the appropriate link is selected, the packet is stored in that link's send buffer for transmission. However, sometimes the node at the other end of the selected link is busy; in which case, the receive buffer for the link may be full. Thus, the packet cannot be sent and remains in the send buffer until the other node's receive buffer is emptied. As a result, network traffic can form congestion which can lead to deadlock.
Deadlock occurs when a cycle of multi-hop packets are each waiting on a busy node on the next hop. A “multi-hop” packet refers to a packet that is routed through at least one node before reaching its destination. A deadlock may occur, for example, in a network of three nodes (node
1
, node
2
and node
3
), where node
1
is waiting to send a multi-hop packet to node
2
(which is not the packet's destination), where node
2
is waiting to send a multi-hop packet to node
3
(which is not the packet's destination), and where node
3
is waiting to send a multi-hop packet to node
1
(which is not the packet's destination). Since each node is waiting on the other, a statement or deadlock occurs, and these nodes are rendered nonoperational.
To prevent deadlock from occurring, some networks have been developed that route traffic using predefined calculations. One family of networks that routes traffic in this way includes the hypercube networks depicted in FIG.
1
A. The hypercube family of networks are configured according to a predefined pattern. The hypercube networks accommodate only networks with a number of nodes that can be expressed as a power of 2. Accordingly,
FIG. 1A
depicts the hypercube networks having 2, 4, 8, and 16 nodes. The pattern that the hypercube networks follow is apparent from an examination of the different topologies.
To prevent deadlock in the hybercube networks, routing is performed using predefined calculations. For example,
FIG. 1B
depicts an example of a hypercube network of 8 nodes that performs this type of routing. Each node of the network is associated with a binary number (e.g.,
010
). When routing a packet through the network, each node performs a calculation to determine to which node to send the packet. According to this calculation, the number of the current node is compared to the number of the destination node of the packet to find the most significant bit that differs. The packet is then forwarded to a node whose number differs from the number of the current node in exactly that bit position. For example, node
000
will send a packet destined for node
111
to node
100
instead of
010
or
001
, because the third bit position (from the right) is the most significant. This calculation is performed at each node until the destination node is reached. Use of this calculation on each node prevents deadlock by preventing a cycle from occurring in the network. That is, there are no sequences of multi-hop packets that form a cycle. However, configuring the networks using a predefined pattern and using the predefined calculations to perform routing leads to inefficient routing, because little attention is given to optimizing either the network topology or the routing to reduce communications overhead. For example, traffic routed from node
000
to node
111
must take 3 hops: starting at
000
and traveling to
100
, to
110
, and then to
111
. It is thus desirable to improve network configuration and routing to reduce communication overhead.
SUMMARY OF THE INVENTION
In accordance with methods and systems consistent with the present invention, an improved deadlock-free routing system is provided to a family of network topologies where both the configuration of the networks and the routings are designed to optimize performance. In this system, each network utilizes static routing tables that perform deadlock-free routing in an optimized manner to reduce the amount of communication overhead when routing traffic. Specifically, the routings in accordance with methods and systems consistent with the present invention require no more than two hops for networks up to a size of 16 nodes. As a result, the deadlock-free routing provided in accordance with methods and systems consistent with the present invention incurs less communications overhead than some conventional systems while still avoiding deadlock.
In accordance with methods consistent with the present invention, a method is provided in a network containing nodes. According to this method, a first of the nodes receives a packet from a second of the nodes, accesses a statically-defined routing table to determine a third of the nodes to send the packet to such that a deadlock is avoided, and sends the packet to the third node.
In accordance with systems consistent with the present invention, a computer-readable memory device encoded with a routing table data structure for use in routing traffic in the network of nodes is provided. The routing table data structure comprises an entry indicating a next node for sending a received packet in such a manner as to avoid deadlock.
In accordance with systems consistent with the present invention, a distributed system with nodes and links interconnecting the nodes is provided. Each node contains a static routing table for use in routing a packet received from a first of the nodes to a second of the nodes to avoid deadlock.
REFERENCES:
patent: 5128932 (1992-07-01), Li
patent: 5453978 (1995-09-01), Sethu et al.
patent: 5602839 (1997-02-01), Annapareddy et al.
patent: 5680116 (1997-10-01), Hashimoto et al.
patent: 5721819 (1998-02-01), Galles et al.
patent: 5740346 (1998-04-01), Wicki et al.
patent: 5751967 (1998-05-01), Raab et al.
patent: 5768501 (1998-06-01), Lewis
patent: 5781546 (1998-07-01), Sethu
patent: 5812549 (1998-09-01), Sethu
patent: 5859981 (1999-01-01), Levin et al.
patent: 5874964 (1999-02-01), Gille
patent: 5884047 (1999-03-01), Aikawa et al.
patent: 5914953 (1999-06-01), Krause et al.
patent: 5970232 (1999-10-01), Passint et al.
patent: 6005860 (1999-12-01), Anderson et al.
patent: 6031835 (2000-02-01), Abali et al.
patent: 6055618 (2000-04-01), Thorson
patent: 6064671 (2000-05-01), Killian
patent: 6097718 (2000-08-01), Bion
patent: 6137781 (2000-10-01), Goto et al.
patent: 6230252 (2001-05-01), Passint et al.
patent: 6243760 (2001-06-01), Armbruster et al.
patent: 6256295 (2001-07-01), Callon
patent: 6295573 (2001-09-01), Bailey et al.
Whay C. Lee, “Topology Aggregation for Hierarchical Routing in ATM Networks.” Apr. 1, 1995, pp. 82-92, Computer-Communication Review.
IBM, “Clustering Algorithm for Computer Network Management Graphics,” Jun. 1988, pp. 71-79, IBM Technical Disclosure Bulletin, vol. 31, No. 1.
Peercy, M. et al., “Distributed Algorithms for Shortest-Path, Deadlock-Free Routing and Broadcasting in Arbitrarily Faulty Hypercubes,” International Symposium on Fault Tolerant Computing Systems (FTCS), US, Los Alamitos, IEEE Comp. Soc. Press, vol. Symp. 20, Jun. 26, 1990, pp. 218-225.
Fl
Cassiday Daniel
Heller Steven K.
Steele, Jr. Guy L.
Backer Firmin
Finnegan Henderson Farabow Garrett & Dunner L.L.P.
Sun Microsystems Inc.
Trammell James P.
LandOfFree
Deadlock-free routing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Deadlock-free routing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deadlock-free routing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3034290