Abstract:
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.

Description:
RELATED APPLICATIONS 
     The following identified U.S. patent applications are relied upon and are incorporated by reference in this application. 
     U.S. patent application Ser. No. 09/323,963, entitled “Improved Network Topologies,” filed on even date herewith, assigned to a common assignee. 
     U.S. patent application Ser. No. 09/323,964, entitled “Dynamic Generation of Deadlock-Free Routings,” filed on Jun. 2, 1999. 
     U.S. patent application Ser. No. 09/323,965, entitled “Recursive Partitioning of Networks,” filed on even date herewith, assigned to a common assignee. 
     U.S. patent application Ser. No. 09/323,962, entitled “Improved Network Reconfiguration,” filed on even date herewith, assigned to a common assignee. 
    
    
     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&#39;s links typically has an associated buffer (“receive buffer”) that temporarily stores packets received via the link, and each of a node&#39;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&#39;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&#39;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&#39;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&#39;s destination), where node  2  is waiting to send a multi-hop packet to node  3  (which is not the packet&#39;s destination), and where node  3  is waiting to send a multi-hop packet to node  1  (which is not the packet&#39;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. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate an implementation of the invention and, together with the description, serve to explain the advantages and principles of the invention. In the drawings, 
     FIG. 1A depicts the hypercube family of networks; 
     FIG. 1B depicts the hypercube network with eight nodes from FIG. 1A where its nodes are numbered as part of its routing algorithm; 
     FIG. 2 depicts a data processing system suitable for use with methods and systems consistent with the present invention; 
     FIG. 3 depicts a more detailed diagram of the chassis of FIG. 2; 
     FIG. 4 depicts a more detailed diagram of a routing card depicted in FIG. 3; 
     FIG. 5 depicts a network topology for a network of 7 nodes in accordance with methods and systems consistent with the present invention; 
     FIG. 6 depicts a network topology for a network of 8 nodes in accordance with methods and systems consistent with the present invention; 
     FIG. 7 depicts a network topology for a network of 9 nodes in accordance with methods and systems consistent with the present invention; 
     FIG. 8 depicts a network topology for a network of 10 nodes in accordance with methods and systems consistent with the present invention; 
     FIG. 9 depicts a network topology for a network of 11 nodes in accordance with methods and systems consistent with the present invention; 
     FIG. 10 depicts a network topology for a network of 12 nodes in accordance with methods and systems consistent with the present invention; 
     FIG. 11 depicts a network topology for a network of 13 nodes in accordance with methods and systems consistent with the present invention; 
     FIG. 12 depicts a network topology for a network of 14 nodes in accordance with methods and systems consistent with the present invention; 
     FIG. 13 depicts a network topology for a network of 15 nodes in accordance with methods and systems consistent with the present invention; and 
     FIG. 14 depicts a network topology for a network of 16 nodes in accordance with methods and systems consistent with the present invention. 
    
    
     DETAILED DESCRIPTION 
     In accordance with methods and systems consistent with the present invention, an improved technique for deadlock-free routing is provided. According to this technique, preconfigured routing tables are used to optimize routing in a network while avoiding a deadlock. These routing tables have been empirically selected to reduce communications overhead while still preventing deadlock. 
     These routing tables are provided in a family of network topologies which have been selected to facilitate network performance. These network topologies are discussed below, and they are also discussed in further detail in copending U.S. patent application Ser. No. 09/323,963 entitled “Improved Network Topologies,” which has been previously incorporated by reference. In addition to being selected for network performance characteristics, these network topologies have been selected to facilitate reconfiguration as is further described in copending U.S. patent application Ser. No. 09/323,962 entitled “Improved Network Reconfiguration,” which has been previously incorporated by reference. 
     IMPLEMENTATION DETAILS 
     FIG. 2 depicts a data processing system  200  suitable for use with methods and systems consistent with the present invention. Data processing system  200  contains a chassis  202  connected to a video display  204  and a keyboard  206 . Data processing system  200  is suitable for use as one or more nodes in the network topologies described below. 
     As shown in FIG. 3, chassis  202  contains up to seven cards  302 - 314  interconnected via bus  315 . Of these cards, cards  308  and  314 , known as routing cards, perform routing functionality with each having five ports  316 - 324  and  326 - 334  that connect to a communication link (e.g., a cable). 
     The cards other than the routing cards (i.e., cards  302 - 306 ,  310 , and  312 ) typically contain multiple CPUs, memory, and secondary storage. In accordance with methods and systems consistent with the present invention, cards  302 - 308  form a single node  336 . Likewise, cards  310 - 314  form a single node  338 . Nodes  336  and  338  are referred to as partner nodes because they are both located in the same chassis  202 . Since node  336  and node  338  are separate communications nodes, they may be interconnected via a communications link  340 , known as a partner link. A partner link is used to transfer control information between two partner nodes: the actual data is transferred via the bus  315  for faster communications. One skilled in the art will appreciate that data processing system  200  and chassis  202  may include additional or different components, including additional nodes. 
     FIG. 4 depicts a more detailed diagram of routing card  308 , although routing card  314  is similarly configured. Routing card  308  contains a memory  402 , a switch  404 , and a processor  406  interconnected by an internal bus  407 , which also connects to bus  315 . Memory  402  contains routing software  408  that routes traffic through the network using routing table  410 . Routing table  410  may contain part or all of the information contained in the routing tables provided below. The switch coordinates the sending and receiving of information across the network via ports  316 - 324  by using a send and receive buffer  412 - 430  for each port. 
     Although aspects of the present invention are described as being stored in memory, one skilled in the art will appreciate that these aspects can also be stored on or read from other types of computer-readable media, such as secondary storage devices, like hard disks, floppy disks, or CD-ROM; a carrier wave from a network, such as the Internet; or other forms of RAM or ROM either currently known or later developed. Sun, Sun Microsystems, the Sun logo, Java™, and Java™-based trademarks are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries. 
     NETWORK TOPOLOGIES 
     In accordance with methods and systems consistent with the present invention, a number of network topologies are provided where the topologies have been selected based on both performance characteristics and the ease with which the network can be reconfigured. Network topologies for networks having seven to sixteen nodes are presented below with exemplary deadlock-free routings. The topologies for networks having less than seven nodes are not presented because they are fully connected. That is, since each routing card has five ports, in networks of six or less nodes, each node can be connected to each other node. In such a situation, the network is referred to as being fully connected. 
     FIG. 5 depicts a network topology for a network of seven nodes in accordance with methods and systems consistent with the present invention. Each node, node  0  through node  6 , has up to five links to other nodes. Each link is depicted as either a solid line or a dashed line. A solid line indicates that the link is a nonpartner link; a dashed line indicates that the link is a partner link between partner nodes. Accordingly, the two partner nodes are contained in the same device. In FIG. 5, the letters (e.g., “A”) indicate a continuing connection to another like-lettered node. For example, node  0  is connected to node  6 . 
     As shown in FIG. 5, node  0  has a partner link with node  1  and directly connects to nodes  3 ,  4 ,  5 , and  6 . Node  1  has a partner link with node  0  and directly connects to nodes  2 ,  3 ,  4 , and  5 . Node  2  has a partner link with node  3  and directly connects to nodes  1 ,  4 ,  5 , and  6 . Node  3  has a partner link with node  2  and directly connects to nodes  0 ,  1 ,  5 , and  6 . Node  4  has a partner link with node  5  and directly connects to nodes  0 ,  1 ,  2 , and  6 . Node  5  has a partner link with node  4  and directly connects to nodes  0 ,  1 ,  2 , and  3 , and node  6  directly connects to nodes  0 ,  2 ,  3 , and  4 . Below is a deadlock-free routing table for this network. The first row of this table, for example, shows that data from node  0  may be sent directly to nodes  1 ,  3 ,  4 ,  5 , and  6  and that data from node  0  may be sent to node  2  via node  3 . 
     
       
         
               
               
             
               
               
               
               
               
               
               
               
               
             
           
               
                   
                   
               
               
                   
                 TO 
               
             
          
           
               
                   
                 FROM 
                 0 
                 1 
                 2 
                 3 
                 4 
                 5 
                 6 
               
               
                   
                   
               
               
                   
                 0 
                   
                 — 
                 3 
                 — 
                 — 
                 — 
                 — 
               
               
                   
                 1 
                 — 
                   
                 — 
                 — 
                 — 
                 — 
                 4 
               
               
                   
                 2 
                 1 
                 — 
                   
                 — 
                 — 
                 — 
                 — 
               
               
                   
                 3 
                 — 
                 — 
                 — 
                   
                 5 
                 — 
                 — 
               
               
                   
                 4 
                 — 
                 — 
                 — 
                 2 
                   
                 — 
                 — 
               
               
                   
                 5 
                 — 
                 — 
                 — 
                 — 
                 — 
                   
                 3 
               
               
                   
                 6 
                 — 
                 0 
                 — 
                 — 
                 — 
                 4 
               
               
                   
                   
               
             
          
         
       
     
     FIG. 6 depicts a network topology for a network of 8 nodes in accordance with methods and systems consistent with the present invention. As shown in FIG. 6, node  0  has a partner link with node  1  and directly connects to nodes  3  through  6 . Node  1  has a partner link with node  0  and directly connects to nodes  2 , 4 ,  5 , and  7 . Node  2  has a partner link with node  3  and directly connects to nodes  1 ,  4 ,  6 , and  7 . Node  3  has a partner link with node  2  and directly connects to node  0  and nodes  5  through  7 . Node  4  has a partner link with node  5  and directly connects to nodes  0 - 2  and  6 . Node  5  has a partner link with node  4  and directly connects to nodes  0 ,  1 ,  3 , and  7 . Node  6  has a partner link with node  7  and directly connects to nodes  0  and  2 - 4 , and node  7  has a partner link with node  6  and directly connects to nodes  1 - 3  and  5 . Below is a deadlock-free routing table for this network. 
     
       
         
               
               
               
             
               
               
               
               
               
               
               
               
               
             
           
               
                   
                   
               
               
                   
                 TO 
                   
               
             
          
           
               
                 FROM 
                 0 
                 1 
                 2 
                 3 
                 4 
                 5 
                 6 
                 7 
               
               
                   
               
               
                 0 
                   
                 — 
                 3 
                 — 
                 — 
                 — 
                 — 
                 6 
               
               
                 1 
                 — 
                   
                 — 
                 2 
                 — 
                 — 
                 7 
                 — 
               
               
                 2 
                 1 
                 — 
                   
                 — 
                 — 
                 4 
                 — 
                 — 
               
               
                 3 
                 — 
                 0 
                 — 
                   
                 5 
                 — 
                 — 
                 — 
               
               
                 4 
                 — 
                 — 
                 — 
                 2 
                   
                 — 
                 — 
                 6 
               
               
                 5 
                 — 
                 — 
                 3 
                 — 
                 — 
                   
                 7 
                 — 
               
               
                 6 
                 — 
                 0 
                 — 
                 — 
                 — 
                 4 
                   
                 — 
               
               
                 7 
                 1 
                 — 
                 — 
                 — 
                 5 
                 — 
                 — 
               
               
                   
               
             
          
         
       
     
     FIG. 7 depicts a network topology for a network of 9 nodes in accordance with methods and systems consistent with the present invention. As shown in FIG. 7, node  0  has a partner link with node  1  and directly connects to nodes  3 ,  4 ,  6 , and  8 . Node  1  has a partner link with node  0  and directly connects to nodes  2 ,  4 ,  5 , and  7 . Node  2  has a partner link with node  3  and directly connects to nodes  1 ,  4 ,  6 , and  7 . Node  3  has a partner link with node  2  and directly connects to nodes  0 ,  5 ,  7 , and  8 . Node  4  has a partner link with node  5  and directly connects to nodes  0 - 2  and  6 . Node  5  has a partner link with node  4  and directly connects to nodes  1 ,  3 ,  7 , and  8 . Node  6  has a partner link with node  7  and directly connects to nodes  0 ,  2 ,  4 , and  8 . Node  7  has a partner link with node  6  and directly connects to nodes  1 - 3  and  5 , and node  8  directly connects to nodes  0 ,  3 ,  5 , and  6 . Below a deadlock-free routing table for this network. 
     
       
         
               
               
             
               
               
               
               
               
               
               
               
               
               
             
           
               
                   
                   
               
               
                   
                 TO 
               
             
          
           
               
                 FROM 
                 0 
                 1 
                 2 
                 3 
                 4 
                 5 
                 6 
                 7 
                 8 
               
               
                   
               
               
                 0 
                   
                 — 
                 3 
                 — 
                 — 
                 4 
                 — 
                 6 
                 — 
               
               
                 1 
                 — 
                   
                 — 
                 2 
                 — 
                 — 
                 7 
                 — 
                 5 
               
               
                 2 
                 1 
                 — 
                   
                 — 
                 — 
                 4 
                 — 
                 — 
                 6 
               
               
                 3 
                 — 
                 0 
                 — 
                   
                 5 
                 — 
                 7 
                 — 
                 — 
               
               
                 4 
                 — 
                 — 
                 — 
                 2 
                   
                 — 
                 — 
                 6 
                 0 
               
               
                 5 
                 1 
                 — 
                 3 
                 — 
                 — 
                   
                 7 
                 — 
                 — 
               
               
                 6 
                 — 
                 0 
                 — 
                 2 
                 — 
                 4 
                   
                 — 
                 — 
               
               
                 7 
                 1 
                 — 
                 — 
                 — 
                 5 
                 — 
                 — 
                   
                 3 
               
               
                 8 
                 — 
                 0 
                 3 
                 — 
                 5 
                 — 
                 — 
                 6 
               
               
                   
               
             
          
         
       
     
     FIG. 8 depicts a network topology for a network of 10 nodes in accordance with methods and systems consistent with the present invention. As shown in FIG. 8, node  0  has a partner link with node  1  and directly connects to nodes  3 ,  4 ,  6 , and  8 . Node  1  has a partner link with node  0  and directly connects to nodes  2 ,  5 ,  7 , and  9 . Node  2  has a partner link with node  3  and directly connects to nodes  1 ,  4 ,  6 , and  9 . Node  3  has a partner link with node  2  and directly connects to nodes  0 ,  5 ,  7 , and  8 . Node  4  has a partner link with node  5  and directly connects to nodes  0 ,  2 ,  6 , and  9 . Node  5  has a partner link with node  4  and directly connects to nodes  1 ,  3 ,  7 , and  8 . Node  6  has a partner link with node  7  and directly connects to nodes  0 ,  2 , 4 , and  8 . Node  7  has a partner link with node  6  and directly connects to nodes  1 ,  3 ,  5 , and  9 . Node  8  has a partner link with node  9  and directly connects to nodes  0 ,  3 ,  5 , and  6 , and n ode  9  has a partner link with node  8  and directly connects to nodes  1 ,  2 ,  4 , and  7 . Below is a deadlock-free routing table for this network. 
     
       
         
               
               
             
               
               
               
               
               
               
               
               
               
               
               
             
           
               
                   
                   
               
               
                   
                 TO 
               
             
          
           
               
                 FROM 
                 0 
                 1 
                 2 
                 3 
                 4 
                 5 
                 6 
                 7 
                 8 
                 9 
               
               
                   
               
               
                 0 
                   
                 — 
                 3 
                 — 
                 — 
                 4 
                 — 
                 6 
                 — 
                 8 
               
               
                 1 
                 — 
                   
                 — 
                 2 
                 5 
                 — 
                 7 
                 — 
                 9 
                 — 
               
               
                 2 
                 1 
                 — 
                   
                 — 
                 — 
                 4 
                 — 
                 6 
                 9 
                 — 
               
               
                 3 
                 — 
                 0 
                 — 
                   
                 5 
                 — 
                 7 
                 — 
                 — 
                 8 
               
               
                 4 
                 — 
                 0 
                 — 
                 2 
                   
                 — 
                 — 
                 6 
                 9 
                 — 
               
               
                 5 
                 1 
                 — 
                 3 
                 — 
                 — 
                   
                 7 
                 — 
                 — 
                 8 
               
               
                 6 
                 — 
                 0 
                 — 
                 2 
                 — 
                 4 
                   
                 — 
                 — 
                 8 
               
               
                 7 
                 1 
                 — 
                 3 
                 — 
                 5 
                 — 
                 — 
                   
                 9 
                 — 
               
               
                 8 
                 — 
                 0 
                 3 
                 — 
                 5 
                 — 
                 — 
                 6 
                   
                 — 
               
               
                 9 
                 1 
                 — 
                 — 
                 2 
                 — 
                 4 
                 7 
                 — 
                 — 
               
               
                   
               
             
          
         
       
     
     FIG. 9 depicts a network topology for a network of 11 nodes in accordance with methods and systems consistent with the present invention. As shown in FIG. 9, node  0  has a partner link with node  1  and directly connects to nodes  3 ,  4 ,  6 , and  8 . Node  1  has a partner link with node  0  and directly connects to nodes  5 ,  7 ,  9 , and  10 . Node  2  has a partner link with node  3  and directly connects to nodes  4 ,  6 ,  9 , and  10 . Node  3  has a partner link with node  2  and directly connects to nodes  0 ,  5 ,  7 , and  8 . Node  4  has a partner link with node  5  and directly connects to nodes  0 ,  2 ,  7 , and  9 . Node  5  has a partner link with node  4  and directly connects to nodes  1 ,  3 ,  8 , and  10 . Node  6  has a partner link with node  7  and directly connects to nodes  0 ,  2 ,  8 , and  10 . Node  7  has a partner link with node  6  and directly connects to nodes  1 ,  3 ,  4 , and  9 . Node  8  has a partner link with node  9  and directly connects to nodes  0 ,  3 ,  5 , and  6 . Node  9  has a partner link with node  8  and directly connects to nodes  1 ,  2 ,  4 , and  7 , and node  10  directly connects to nodes  1 ,  2 ,  5 , and  6 . A deadlock-free routing table for this network is provided below. 
     
       
         
               
               
             
               
               
               
               
               
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
               
               
               
               
               
             
           
               
                   
                   
               
               
                   
                 TO 
               
             
          
           
               
                 FROM 
                 0 
                 1 
                 2 
                 3 
                 4 
                 5 
                 6 
                 7 
                 8 
                 9 
                 10 
               
               
                   
               
             
          
           
               
                 0 
                   
                 — 
                 3 
                 — 
                 — 
                 4 
                 — 
                 6 
                 — 
                 8 
                 6 
               
               
                 1 
                 — 
                   
                 9 
                 5 
                 5 
                 — 
                 7 
                 — 
                 9 
                 — 
                 — 
               
               
                 2 
                 6 
                 10 
                   
                 — 
                 — 
                 4 
                 — 
                 6 
                 9 
                 — 
                 — 
               
               
                 3 
                 — 
                 0 
                 — 
                   
                 5 
                 — 
                 7 
                 — 
                 — 
                 8 
                 5 
               
               
                 4 
                 — 
                 0 
                 — 
                 2 
                   
                 — 
                 7 
                 — 
                 9 
                 — 
                 2 
               
               
                 5 
                 1 
                 — 
                 3 
                 — 
                 — 
                   
                 8 
                 1 
                 — 
                 8 
                 — 
               
               
                 6 
                 — 
                 0 
                 — 
                 2 
                 2 
                 8 
                   
                 — 
                 — 
                 8 
                 — 
               
               
                 7 
                 1 
                 — 
                 3 
                 — 
                 — 
                 4 
                 — 
                   
                 9 
                 — 
                 1 
               
               
                 8 
                 — 
                 0 
                 3 
                 — 
                 5 
                 — 
                 — 
                 6 
                   
                 — 
                 6 
               
               
                 9 
                 1 
                 — 
                 — 
                 2 
                 — 
                 4 
                 7 
                 — 
                 — 
                   
                 1 
               
               
                 10 
                 1 
                 — 
                 — 
                 2 
                 5 
                 — 
                 — 
                 6 
                 6 
                 2 
               
               
                   
               
             
          
         
       
     
     FIG. 10 depicts a network topology for a network of 12 nodes in accordance with methods and systems consistent with the present invention. As shown in FIG. 10, node  0  has a partner link with node  1  and directly connects to nodes  4 ,  6 ,  8 , and  11 . Node  1  has a partner link with node  0  and directly connects to nodes  5 ,  7 ,  9 , and  10 . Node  2  has a partner link with node  3  and directly connects to nodes  4 ,  6 ,  9 , and  10 . Node  3  has a partner link with node  2  and directly connects to nodes  5 ,  7 ,  8 , and  11 . Node  4  has a partner link with node  5  and directly connects to nodes  0 ,  2 ,  9 , and  11 . Node  5  has a partner link with node  4  and directly connects to nodes  1 ,  3 ,  8 , and  10 . Node  6  has a partner link with node  7  and directly connects to nodes  0 ,  2 ,  8 , and  10 . Node  7  has a partner link with node  6  and directly connects to nodes  1 ,  3 ,  9 , and  11 . Node  8  has a partner link with node  9  and directly connects to nodes  0 ,  3 ,  5 , and  6 . Node  9  has a partner link with node  8  and directly connects to nodes  1 ,  2 ,  4 , and  7 . Node  10  has a partner link with node  11  and directly connects to nodes  1 ,  2 ,  5 , and  6 , and node  11  has a partner link with node  10  and directly connects to nodes  0 ,  3 ,  4 , and  7 . A deadlock-free routing table is provided below. 
     
       
         
               
               
             
               
               
               
               
               
               
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
               
               
               
               
               
               
             
           
               
                   
                   
               
               
                   
                 TO 
               
             
          
           
               
                 FROM 
                 0 
                 1 
                 2 
                 3 
                 4 
                 5 
                 6 
                 7 
                 8 
                 9 
                 10 
                 11 
               
               
                   
               
             
          
           
               
                 0 
                   
                 — 
                 4 
                 8 
                 — 
                 4 
                 — 
                 6 
                 — 
                 8 
                 11 
                 — 
               
               
                 1 
                 — 
                   
                 9 
                 5 
                 5 
                 — 
                 7 
                 — 
                 9 
                 — 
                 — 
                 10 
               
               
                 2 
                 6 
                 10 
                   
                 — 
                 — 
                 4 
                 — 
                 6 
                 9 
                 — 
                 — 
                 10 
               
               
                 3 
                 11 
                 7 
                 — 
                   
                 5 
                 — 
                 7 
                 — 
                 — 
                 8 
                 11 
                 — 
               
               
                 4 
                 — 
                 0 
                 — 
                 2 
                   
                 — 
                 0 
                 9 
                 9 
                 — 
                 11 
                 — 
               
               
                 5 
                 1 
                 — 
                 3 
                 — 
                 — 
                   
                 10 
                 1 
                 — 
                 8 
                 — 
                 10 
               
               
                 6 
                 — 
                 0 
                 — 
                 2 
                 2 
                 10 
                   
                 — 
                 — 
                 8 
                 — 
                 10 
               
               
                 7 
                 1 
                 — 
                 3 
                 — 
                 9 
                 3 
                 — 
                   
                 9 
                 — 
                 11 
                 — 
               
               
                 8 
                 — 
                 0 
                 3 
                 — 
                 5 
                 — 
                 — 
                 6 
                   
                 — 
                 5 
                 0 
               
               
                 9 
                 1 
                 — 
                 — 
                 2 
                 — 
                 4 
                 7 
                 — 
                 — 
                   
                 1 
                 7 
               
               
                 10 
                 1 
                 — 
                 — 
                 2 
                 5 
                 — 
                 — 
                 6 
                 5 
                 2 
                   
                 — 
               
               
                 11 
                 — 
                 0 
                 3 
                 — 
                 — 
                 4 
                 7 
                 — 
                 3 
                 7 
                 — 
               
               
                   
               
             
          
         
       
     
     FIG. 11 depicts a network topology for a network of 13 nodes in accordance with methods and systems consistent with the present invention. As shown in FIG. 11, node  0  has a partner link with node  1  and directly connects to nodes  4 ,  6 ,  8 , and  11 . Node  1  has a partner link with node  0  and directly connects to nodes  5 ,  7 ,  9 , and  10 . Node  2  has a partner link with node  3  and directly connects to nodes  4 ,  6 ,  9 , and  10 . Node  3  has a partner link with node  2  and directly connects to nodes  5 ,  7 ,  8 , and  11 . Node  4  has a partner link with node  5  and directly connects to nodes  0 ,  2 ,  9 , and  12 . Node  5  has a partner link with node  4  and directly connects to nodes  1 ,  3 ,  6 , and  8 . Node  6  has a partner link with node  7  and directly connects to nodes  0 ,  2 ,  5 , and  10 . Node  7  has a partner link with node  6  and directly connects to nodes  1 ,  3 ,  11 , and  12 . Node  8  has a partner link with node  9  and directly connects to nodes  0 ,  3 ,  5 , and  12 . Node  9  has a partner link with node  8  and directly connects to nodes  1 ,  2 ,  4 , and  11 . Node  10  has a partner link with node  11  and directly connects to nodes  1 ,  2 ,  6 , and  12 . Node  11  has a partner link with node  10  and directly connects to nodes  0 ,  3 ,  7 , and  9 , and node  12  directly connects to nodes  4 ,  7 ,  8 , and  10 . A deadlock-free routing table for this network is provided below. 
     
       
         
               
               
             
               
               
               
               
               
               
               
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
               
               
               
               
               
               
               
             
           
               
                   
                   
               
               
                   
                 TO 
               
             
          
           
               
                 FROM 
                 0 
                 1 
                 2 
                 3 
                 4 
                 5 
                 6 
                 7 
                 8 
                 9 
                 10 
                 11 
                 12 
               
               
                   
               
             
          
           
               
                 0 
                   
                 — 
                 4 
                 8 
                 — 
                 4 
                 — 
                 6 
                 — 
                 8 
                 11 
                 — 
                 4 
               
               
                 1 
                 — 
                   
                 9 
                 5 
                 5 
                 — 
                 7 
                 — 
                 9 
                 — 
                 — 
                 10 
                 7 
               
               
                 2 
                 6 
                 10 
                   
                 — 
                 — 
                 4 
                 — 
                 6 
                 9 
                 — 
                 — 
                 10 
                 10 
               
               
                 3 
                 11 
                 7 
                 — 
                   
                 5 
                 — 
                 7 
                 — 
                 — 
                 8 
                 11 
                 — 
                 7 
               
               
                 4 
                 — 
                 0 
                 — 
                 2 
                   
                 — 
                 0 
                 12 
                 9 
                 — 
                 12 
                 0 
                 — 
               
               
                 5 
                 1 
                 — 
                 3 
                 — 
                 — 
                   
                 — 
                 6 
                 — 
                 8 
                 1 
                 3 
                 8 
               
               
                 6 
                 — 
                 0 
                 — 
                 2 
                 5 
                 — 
                   
                 — 
                 0 
                 2 
                 — 
                 10 
                 10 
               
               
                 7 
                 1 
                 — 
                 3 
                 — 
                 12 
                 3 
                 — 
                   
                 3 
                 11 
                 11 
                 — 
                 — 
               
               
                 8 
                 — 
                 0 
                 3 
                 — 
                 5 
                 — 
                 0 
                 12 
                   
                 — 
                 12 
                 0 
                 — 
               
               
                 9 
                 1 
                 — 
                 — 
                 2 
                 — 
                 4 
                 2 
                 1 
                 — 
                   
                 11 
                 — 
                 4 
               
               
                 10 
                 1 
                 — 
                 — 
                 2 
                 2 
                 6 
                 — 
                 6 
                 12 
                 2 
                   
                 — 
                 — 
               
               
                 11 
                 — 
                 0 
                 3 
                 — 
                 0 
                 3 
                 7 
                 — 
                 9 
                 — 
                 — 
                   
                 7 
               
               
                 12 
                 8 
                 10 
                 4 
                 8 
                 — 
                 4 
                 7 
                 — 
                 — 
                 8 
                 — 
                 10 
               
               
                   
               
             
          
         
       
     
     FIG. 12 depicts a network topology for a network of 14 nodes in accordance with methods and systems consistent with the present invention. As shown in FIG. 12, node  0  has a partner link with node  1  and directly connects to nodes  4 ,  6 ,  8 , and  11 . Node  1  has a partner link with node  0  and directly connects to nodes  5 ,  7 ,  9 , and  10 . Node  2  has a partner link with node  3  and directly connects to nodes  4 ,  6 ,  9 , and  10 . Node  3  has a partner link with node  2  and directly connects to nodes  5 ,  7 ,  8 , and  11 . Node  4  has a partner link with node  5  and directly connects to nodes  0 ,  2 ,  9 , and  12 . Node  5  has a partner link with node  4  and directly connects to nodes  1 ,  3 ,  8 , and  13 . Node  6  has a partner link with node  7  and directly connects to nodes  0 ,  2 ,  10 , and  13 . Node  7  has a partner link with node  6  and directly connects to nodes  1 ,  3 ,  11 , and  12 . Node  8  has a partner link with node  9  and directly connects to nodes  0 ,  3 ,  5 , and  12 . Node  9  has a partner link with node  8  and directly connects to nodes  1 ,  2 ,  4 , and  13 . Node  10  has a partner link with node  11  and directly connects to nodes  1 ,  2 ,  6 , and  12 . Node  11  has a partner link with node  10  and directly connects to nodes  0 ,  3 ,  7 , and  13 . Node  12  has a partner link with node  13  and directly connects to nodes  4 ,  7 ,  8 , and  10 , and node  13  has a partner link with node  12  and directly connects to nodes  5 ,  6 ,  9 , and  11 . A deadlock-free routing table for this network is provided below. 
     
       
         
               
               
             
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
             
           
               
                   
                   
               
               
                   
                 TO 
               
             
          
           
               
                 FROM 
                 0 
                 1 
                 2 
                 3 
                 4 
                 5 
                 6 
                 7 
                 8 
                 9 
                 10 
                 11 
                 12 
                 13 
               
               
                   
               
             
          
           
               
                 0 
                   
                 — 
                 4 
                 8 
                 — 
                 4 
                 — 
                 6 
                 — 
                 8 
                 11 
                 — 
                 8 
                 6 
               
               
                 1 
                 — 
                   
                 9 
                 5 
                 5 
                 — 
                 7 
                 — 
                 9 
                 — 
                 — 
                 10 
                 7 
                 5 
               
               
                 2 
                 6 
                 10 
                   
                 — 
                 — 
                 4 
                 — 
                 6 
                 9 
                 — 
                 — 
                 10 
                 10 
                 6 
               
               
                 3 
                 11 
                 7 
                 — 
                   
                 5 
                 — 
                 7 
                 — 
                 — 
                 8 
                 11 
                 — 
                 7 
                 11 
               
               
                 4 
                 — 
                 0 
                 — 
                 2 
                   
                 — 
                 0 
                 12 
                 9 
                 — 
                 12 
                 0 
                 — 
                 12 
               
               
                 5 
                 1 
                 — 
                 3 
                 — 
                 — 
                   
                 13 
                 1 
                 — 
                 8 
                 1 
                 13 
                 13 
                 — 
               
               
                 6 
                 — 
                 0 
                 — 
                 2 
                 2 
                 13 
                   
                 — 
                 0 
                 2 
                 — 
                 10 
                 13 
                 — 
               
               
                 7 
                 1 
                 — 
                 3 
                 — 
                 12 
                 3 
                 — 
                   
                 3 
                 1 
                 11 
                 — 
                 — 
                 12 
               
               
                 8 
                 — 
                 0 
                 3 
                 — 
                 5 
                 — 
                 0 
                 12 
                   
                 — 
                 12 
                 0 
                 — 
                 12 
               
               
                 9 
                 1 
                 — 
                 — 
                 2 
                 — 
                 4 
                 13 
                 1 
                 — 
                   
                 1 
                 13 
                 13 
                 — 
               
               
                 10 
                 1 
                 — 
                 — 
                 2 
                 2 
                 1 
                 — 
                 6 
                 12 
                 2 
                   
                 — 
                 — 
                 12 
               
               
                 11 
                 — 
                 0 
                 3 
                 — 
                 0 
                 3 
                 7 
                 — 
                 3 
                 13 
                 — 
                   
                 13 
                 — 
               
               
                 12 
                 8 
                 10 
                 4 
                 8 
                 — 
                 4 
                 7 
                 — 
                 — 
                 8 
                 — 
                 10 
                   
                 — 
               
               
                 13 
                 11 
                 9 
                 9 
                 5 
                 5 
                 — 
                 — 
                 6 
                 9 
                 — 
                 11 
                 — 
                 — 
               
               
                   
               
             
          
         
       
     
     FIG. 13 depicts a network topology for a network of 15 nodes in accordance with methods and systems consistent with the present invention. As shown in FIG. 13, node  0  has a partner link with node  1  and directly connects to nodes  4 ,  6 ,  8 , and  11 . Node  1  has a partner link with node  0  and directly connects to nodes  5 ,  7 ,  9 , and  10 . Node  2  has a partner link with node  3  and directly connects to nodes  4 ,  6 ,  9 , and  10 . Node  3  has a partner link with node  2  and directly connects to nodes  5 ,  7 ,  8 , and  11 . Node  4  has a partner link with node  5  and directly connects to nodes  0 ,  2 ,  9 , and  12 . Node  5  has a partner link with node  4  and directly connects to nodes  1 ,  3 ,  13 , and  14 . Node  6  has a partner link with node  7  and directly connects to nodes  0 ,  2 ,  13 , and  14 . Node  7  has a partner link with node  6  and directly connects to nodes  1 ,  3 ,  11 , and  12 . Node  8  has a partner link with node  9  and directly connects to nodes  0 ,  3 ,  12 , and  14 . Node  9  has a partner link with node  8  and directly connects to nodes  1 ,  2 ,  4 , and  13 . Node  10  has a partner link with node  11  and directly connects to nodes  1 ,  2 ,  12 , and  14 . Node  11  has a partner link with node  10  and directly connects to nodes  0 ,  3 ,  7 , and  13 . Node  12  has a partner link with node  13  and directly connects to nodes  4 ,  7 ,  8 , and  10 . Node  13  has a partner link with node  12  and directly connects to nodes  5 ,  6 ,  9 , and  11 , and node  14  directly connects to nodes  5 ,  6 ,  8 , and  10 . A deadlock-free routing table for this network is provided below. 
     
       
         
               
               
             
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
             
           
               
                   
                   
               
               
                   
                 TO 
               
             
          
           
               
                 FROM 
                 0 
                 1 
                 2 
                 3 
                 4 
                 5 
                 6 
                 7 
                 8 
                 9 
                 10 
                 11 
                 12 
                 13 
                 14 
               
               
                   
               
             
          
           
               
                 0 
                   
                 — 
                 4 
                 8 
                 — 
                 4 
                 — 
                 6 
                 — 
                 8 
                 11 
                 — 
                 4 
                 6 
                 8 
               
               
                 1 
                 — 
                   
                 9 
                 5 
                 5 
                 — 
                 7 
                 — 
                 9 
                 — 
                 — 
                 10 
                 7 
                 5 
                 5 
               
               
                 2 
                 6 
                 10 
                   
                 — 
                 — 
                 4 
                 — 
                 6 
                 9 
                 — 
                 — 
                 10 
                 10 
                 6 
                 6 
               
               
                 3 
                 11 
                 7 
                 — 
                   
                 5 
                 — 
                 7 
                 — 
                 — 
                 8 
                 11 
                 — 
                 7 
                 11 
                 5 
               
               
                 4 
                 — 
                 0 
                 — 
                 2 
                   
                 — 
                 0 
                 12 
                 9 
                 — 
                 12 
                 0 
                 — 
                 12 
                 5 
               
               
                 5 
                 1 
                 — 
                 3 
                 — 
                 — 
                   
                 13 
                 1 
                 3 
                 1 
                 1 
                 13 
                 13 
                 — 
                 — 
               
               
                 6 
                 — 
                 0 
                 — 
                 2 
                 2 
                 14 
                   
                 — 
                 14 
                 2 
                 2 
                 0 
                 13 
                 — 
                 — 
               
               
                 7 
                 1 
                 — 
                 3 
                 — 
                 12 
                 3 
                 — 
                   
                 3 
                 1 
                 11 
                 — 
                 — 
                 12 
                 6 
               
               
                 8 
                 — 
                 0 
                 3 
                 — 
                 12 
                 14 
                 0 
                 12 
                   
                 — 
                 12 
                 0 
                 — 
                 12 
                 — 
               
               
                 9 
                 1 
                 — 
                 — 
                 2 
                 — 
                 4 
                 13 
                 1 
                 — 
                   
                 1 
                 13 
                 13 
                 — 
                 8 
               
               
                 10 
                 1 
                 — 
                 — 
                 2 
                 2 
                 14 
                 2 
                 12 
                 14 
                 2 
                   
                 — 
                 — 
                 12 
                 — 
               
               
                 11 
                 — 
                 0 
                 3 
                 — 
                 0 
                 3 
                 7 
                 — 
                 3 
                 13 
                 — 
                   
                 13 
                 — 
                 10 
               
               
                 12 
                 8 
                 10 
                 4 
                 8 
                 — 
                 4 
                 7 
                 — 
                 — 
                 8 
                 — 
                 10 
                   
                 — 
                 8 
               
               
                 13 
                 11 
                 9 
                 9 
                 5 
                 5 
                 — 
                 — 
                 6 
                 9 
                 — 
                 11 
                 — 
                 — 
                   
                 5 
               
               
                 14 
                 6 
                 10 
                 10 
                 8 
                 5 
                 — 
                 — 
                 6 
                 — 
                 8 
                 — 
                 10 
                 10 
                 6 
               
               
                   
               
             
          
         
       
     
     FIG. 14 depicts a network topology for a network of 16 nodes in accordance with methods and systems consistent with the present invention. As shown in this figure, node  0  has a partner link with node and directly connects to nodes  4 ,  6 ,  8 , and  11 . Node  1  has a partner link with node  0  and directly connects to nodes  5 ,  7 ,  9 , and  10 . Node  2  has a partner link with node  3  and directly connects to nodes  4 ,  6 ,  9 , and  10 . Node  3  has a partner link with node  2  and directly connects to nodes  5 ,  7 ,  8 , and  11 . Node  4  has a partner link with node  5  and directly connects to nodes  0 ,  2 ,  12 , and  15 . Node  5  has a partner link with node  4  and directly connects to nodes  1 ,  3 ,  13 , and  14 . Node  6  has a partner link with node  7  and directly connects to nodes  0 ,  2 ,  13 , and  14 . Node  7  has a partner link with node  6  and directly connects to nodes  1 ,  3 ,  12 , and  15 . Node  8  has a partner link with node  9  and directly connects to nodes  0 ,  3 ,  12 , and  14 . Node  9  has a partner link with node  8  and directly connects to nodes  1 ,  2 ,  13 , and  15 . Node  10  has a partner link with node  11  and directly connects to nodes  1 ,  2 ,  12 , and  14 . Node  11  has a partner link with node  10  and directly connects to nodes  0 ,  3 ,  13 , and  15 . Node  12  has a partner link with node  13  and directly connects to nodes  4 ,  7 ,  8 , and  10 . Node  13  has a partner link with node  12  and directly connects to nodes  5 ,  6 ,  9 , and  11 . Node  14  has a partner link with node  15  and directly connects to nodes  5 ,  6 ,  8 , and  10 , and node  15  has a partner link with node  14  and directly connects to nodes  4 ,  7 ,  9 , and  11 . A deadlock-free routing table for this network topology is provided below. 
     
       
         
               
               
             
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
             
           
               
                   
                   
               
               
                   
                 TO 
               
             
          
           
               
                 FROM 
                 0 
                 1 
                 2 
                 3 
                 4 
                 5 
                 6 
                 7 
                 8 
                 9 
                 10 
                 11 
                 12 
                 13 
                 14 
                 15 
               
               
                   
               
             
          
           
               
                 0 
                   
                 — 
                 4 
                 8 
                 — 
                 4 
                 — 
                 6 
                 — 
                 8 
                 11 
                 — 
                 4 
                 6 
                 8 
                 4 
               
               
                 1 
                 — 
                   
                 9 
                 5 
                 5 
                 — 
                 7 
                 — 
                 9 
                 — 
                 — 
                 10 
                 7 
                 5 
                 5 
                 9 
               
               
                 2 
                 6 
                 10 
                   
                 — 
                 — 
                 4 
                 — 
                 6 
                 9 
                 — 
                 — 
                 10 
                 10 
                 6 
                 6 
                 4 
               
               
                 3 
                 11 
                 7 
                 — 
                   
                 5 
                 — 
                 7 
                 — 
                 — 
                 8 
                 11 
                 — 
                 7 
                 11 
                 5 
                 7 
               
               
                 4 
                 — 
                 0 
                 — 
                 2 
                   
                 — 
                 0 
                 12 
                 0 
                 2 
                 12 
                 0 
                 — 
                 12 
                 15 
                 — 
               
               
                 5 
                 1 
                 — 
                 3 
                 — 
                 — 
                   
                 13 
                 1 
                 3 
                 1 
                 1 
                 13 
                 13 
                 — 
                 — 
                 14 
               
               
                 6 
                 — 
                 0 
                 — 
                 2 
                 2 
                 14 
                   
                 — 
                 14 
                 2 
                 2 
                 0 
                 13 
                 — 
                 — 
                 14 
               
               
                 7 
                 1 
                 — 
                 3 
                 — 
                 15 
                 3 
                 — 
                   
                 3 
                 15 
                 1 
                 3 
                 — 
                 12 
                 15 
                 — 
               
               
                 8 
                 — 
                 0 
                 3 
                 — 
                 12 
                 14 
                 0 
                 12 
                   
                 — 
                 12 
                 0 
                 — 
                 12 
                 — 
                 14 
               
               
                 9 
                 1 
                 — 
                 — 
                 2 
                 15 
                 13 
                 13 
                 1 
                 — 
                   
                 1 
                 13 
                 13 
                 — 
                 15 
                 — 
               
               
                 10 
                 1 
                 — 
                 — 
                 2 
                 2 
                 14 
                 14 
                 12 
                 14 
                 2 
                   
                 — 
                 — 
                 12 
                 — 
                 14 
               
               
                 11 
                 — 
                 0 
                 3 
                 — 
                 15 
                 3 
                 13 
                 15 
                 3 
                 15 
                 — 
                   
                 13 
                 — 
                 15 
                 — 
               
               
                 12 
                 8 
                 10 
                 4 
                 8 
                 — 
                 4 
                 7 
                 — 
                 — 
                 8 
                 — 
                 10 
                   
                 — 
                 8 
                 4 
               
               
                 13 
                 11 
                 9 
                 9 
                 5 
                 5 
                 — 
                 — 
                 6 
                 9 
                 — 
                 11 
                 — 
                 — 
                   
                 5 
                 9 
               
               
                 14 
                 6 
                 10 
                 10 
                 8 
                 5 
                 — 
                 — 
                 6 
                 — 
                 8 
                 — 
                 10 
                 10 
                 6 
                   
                 — 
               
               
                 15 
                 11 
                 7 
                 9 
                 11 
                 — 
                 4 
                 7 
                 — 
                 9 
                 — 
                 11 
                 — 
                 7 
                 11 
                 — 
               
               
                   
               
             
          
         
       
     
     Although the present invention has been described with reference to a preferred embodiment thereof, those skilled in the art will know of various changes in form and detail which may be made without departing from the spirit and scope of the present invention as defined in the appended claims and their full scope of equivalents.