Dynamic generation of deadlock-free routings

Details Dynamic generation of deadlock-free routings Dynamic generation of deadlock-free routings

1999-06-02

2004-09-14

Nguyen, Hanh (Department: 2662)

Multiplex communications

Fault recovery

Bypass an inoperative switch or inoperative element of a...

C370S219000, C370S238000, C370S400000, C709S238000, C709S239000

Reexamination Certificate

active

06791939

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to data processing systems and, more particularly, to dynamic generation of deadlock-free routings.
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 empties. As a result, network traffic can form congestion which may 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 stalement 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 family of networks depicted in FIG.
1
A. The hypercube 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 possible sequences of multi-hop packets that can form a loop.
Although it prevents deadlock, this routing method cannot be changed at runtime. Therefore, if a failure occurs, network traffic cannot be rerouted to avoid the failure, thus significantly impacting the performance of the network. For example, if the failure were a node failure, all paths through this node are rendered nonoperational until the node is repaired, which renders the entire network virtually nonoperational. It is thus desirable to improve network operation when a failure is encountered.
SUMMARY OF THE INVENTION
In accordance with methods and systems consistent with the present invention, an improved failure recovery system is provided that, upon detecting a failure, generates new routings for the network which (1) avoid the failure and (2) avoid deadlock. In this manner, after a failure is detected, the network remains as operational as possible while still avoiding deadlock. Thus, by using the improved failure recovery system, a network failure has a much less severe impact on the network than in conventional systems.
In accordance with methods consistent with the present invention, a method is provided in a distributed system containing nodes interconnected via links. Each node contains a routing table with routings for routing traffic. The method initiates operation of the distributed system such that the traffic is routed through the nodes using the routings contained in the routing tables. Furthermore, while the distributed system remains operational, the method generates new routings for the routing tables that avoid deadlock and updates the routing tables to utilize the new routings.
In accordance with methods consistent with the present invention, a method is provided in a data processing system having a network with nodes and links interconnecting the nodes. This method assigns numerical values to each of the links and identifies, for each pair of the nodes, a path through the network that traverses at least one of the links. Furthermore, the method determines whether the numerical values for each link of each path that traverses more than one link follows a predefined sequence and determines that routing traffic through the network using the paths avoids deadlock when it is determined that the numerical values for each link of each path that traverses more than one link follows the predefined sequence.
In accordance with methods consistent with the present invention, a method is provided in a data processing system with a network having nodes and routings for routing traffic between a plurality of the nodes. The routings lack a routing for routing traffic between a first of the nodes and a second of the nodes. The method identifies a proposed route for routing traffic between the first node and the second node, determines whether adding the proposed route to the routings subjects the network to deadlock, and adds the proposed route to the routings when it is determined that the addition of the proposed route to the routings does not subject the network to deadlock.
In accordance with methods consistent with the present invention, a method is provided in a data processing system having a network with nodes and links interconnecting the nodes. The data processing system has routings for routing traffic between a plurality of the nodes. The routings lack a routing for routing traffic between a first of the nodes and a second of the nodes. This method adds a new routing to the routings for transferring traffic between the first node and the second node, determines that the routings subject the network to deadlock, and replaces a routing other than the new routing to render the network deadlock free.
In accordance with systems consistent with the present invention, a distributed system is provided with a plurality of nodes that route traffic using routings in routing tables. The distributed system contains a failure recovery one of the plurality of nodes including a memory and a processor. The memory contains a failure recovery prog

Affiliated with

Also associated with

Rating

Dynamic generation of deadlock-free routings does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Dynamic generation of deadlock-free routings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic generation of deadlock-free routings will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3248773