Method and system for routing information between nodes in a communication network

• US 5,477,536 A
• Filed: 12/07/1993
• Issued: 12/19/1995
• Est. Priority Date: 01/26/1993
• Status: Expired due to Term

• Current Assignee: Intergraph Hardware Technologies Company (Hexagon AB)
• Original Assignee: International Business Machines Corporation
• Inventors: Picard, Jean L.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): BLUM, RUSSELL
• Application Number:
  US08/163,106
• Time in Patent Office: 742 Days
• Field of Search: 370/54, 370/60, 370/94.1, 370/58.1, 370/58.2, 370/58.3
• US Class Current: 370/400
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/34 Source routing

Abstract

A method and apparatus for routing packets through a multinode communication network includes a packet format with a sub-field in which a routing list (RL) having entry addresses and exit addresses for ports of nodes, through which the packet must be routed. Each node on receiving a packet, extracts routing information specific to the node and forwards the packet according to the extracted routing information.

Claims

1. A method for routing packets from a first end node to a second end node in a communication network comprising a plurality of nodes having input/output ports, through which the packets are routed and means for establishing a route to be followed by the packets sent from the first end node to the second end node, thereby identifying the nodes to be passed by the packets and in each node the ports through which the packets will enter the node and exit it, said input/output ports having port addresses, said method being characterized in that it comprises the following steps:

a) for each node, combining by the means for establishing the route the port addresses of the node input port and node output port in order to obtain a routing code which is specific to the node, and arranging the routing codes obtained for the successive nodes of the route into a routing code list (RL),

b) transmitting from said first end node each packet including the routing list,

c) receiving the packets at each node of the route and extracting from the routing list the routing code specific to the node, determining the address of the output port of the node from the routing code and the input port address, and providing the packet to the so-determined output port.

2. The method according to claim 1, characterized in that the combining step a) comprises the XORing of the input port address and output port address of each node of the route.

3. The method according to claim 1 or 2, characterized in that it comprises the step of:

associating a direction indicator (F/B) to the routing list and setting said indicator to a first value when the packets are sent in a forward direction from the first end node to the second end node and setting the indicator to a second value when feedback packets are returned in the reverse direction of the route.

4. The method according to claim 3, characterized in that it comprises the steps of:

reading at each node the direction indicator of the packets received at an input port,

reading at each node either the first routing code of the routing list if the direction indicator is set to the first value or the last routing code of the list if the direction indicator is set to the second value,

XORing the routing code read from the routing list with the address of the input port, thereby obtaining the address of the output port,

arranging the routing list by rotating the routing codes forward if the direction indicator is set to the first value or backward if the direction indicator is set to the second value and passing the packets with the arranged routing list and direction indicator to the next node on the route.

5. An apparatus for routing packets from a first end node (A) to a second end node (E) in a communication network comprising a plurality of nodes (A to E) having input/output ports (0 to 7), through which the packets are routed and means (64) for establishing a route to be followed by the packets sent from the first end node to the second end node, thereby identifying the nodes to be passed by the packets and in each node the ports through which the packets will enter the node and exit it, said input/output ports having port addresses;

said apparatus being characterized in that;

the means for establishing the route combines for each node of the route the port addresses of the node input port and node output ports for obtaining a routing code (RC) which is specific to the node and arranges the routing codes obtained for the successive nodes of the route into a routing code list (RL), which is provided to the first end node and transmitted with the packets, and in that each node comprises for each input/output port;

receiving means (70) for receiving the packets from the input port,

means (122, 162,

     166) for reading the routing code specific to the node from the routing list of the packet,

combining means (176,174) for combining the read routing code with the address of the node input port for determining the address of the node output port, and

transmitting means (152,182,

     82) for transmitting the packets to the output port having the address determined by the combining means.

6. The apparatus according to claim 5, characterized in that the routing code specific to each node is obtained by the means for establishing the route by XORing the addresses of the input port and output port.

7. The apparatus according to claim 5 or 6, characterized in that the means for establishing the route associates a direction indicator (F/B) to the routing list, said indicator being set a first value when the packets are sent in a forward direction from the first end node to the second end node and set to a second value when the packets are returned (feedback) to the first end node by a node of the route.

8. The apparatus according to claim 7, characterized in that it further comprises:

means (160) for receiving at each node the direction indicator of the packets received at an input port,

means (122,

     166) responsive to the value of the direction indicator for reading at each node either the first routing code of the routing list if the direction indicator is set to the first value or the last routing code of the list if the direction indicator is set to the second value,

XORing means (174,176) for XORing the routing code read from the routing list with the address of the input port, thereby obtaining the address of the output port,

means (182, 122, 184, 186,

     188) for arranging the routing list by rotating the routing codes forward if the direction indicator is set to the first value or backward if the direction indicator is set to the second value.

9. The apparatus according to any one of claims 5 to 8 wherein the packet comprises control bits indicative that feedback packets are to be returned by a node and is characterized in that it comprises:

in each node, means (161, 122, 218, 220,

     212) for generating the feedback packets, having a direction indicator set to a value opposite to the direction indicator of the forward packets, and having the first routing code in the routing list set equal to a value (all

     0) which is different from the combination of input and output addresses, and the other routing codes identical and arranged as the routing codes in the routing list of the forward packets.

10. In a communications network comprising a plurality of interconnected nodes having input/output ports for routing packets of data sent from a first node to a second node with one of the nodes specifying a route including nodes through which the packets are to be transported and output address of exit ports from which the packets exit each node, a method for routing the packets of data comprising the steps of:

generating at a node, wanting to send information, a data packet including a Routing List (RL) containing Routing Codes each one being specific to a node in the route and formed by combining the port addresses of the input port and output port of the node in the route; and

forwarding the generated data packet onto the communications network so that other nodes in the route use the Routing Code (RC) to identify node ports whereat the data packet exits a node.

11. The method of claim 10 wherein the combining of port addresses is done by XORing the input port address and the output port address.

12. The method of claim 10 further including receiving the packet at each node of the route and extracting from the Routing List the Routing Code specific to the node;

determining the output port of the node from the Routing Code RC and the input port address; and

sending the data packet to the so-determined output port.

13. The method of claim 12 wherein the determining step includes XORing the routing code and the input port address.

14. The method of claim 10 further including the steps of generating a Control Field C having at least one bit for indicating to a node in the route action to be taken relative to the data packet;

and

concatenating said Control Field to the RL field.

15. The method of claim 14 wherein the Control Field C includes a data byte with bit 0 representing a Forward/Backward (F/B) indicator, bit 1 representing a congestion indicator, bit 2 representing a TRACE indicator, bit 3 representing a WARP indicator, bit 4 representing a Feedback Packet indicator, and bits 5 to 7 representing RL Length indicators.

16. In a communications network comprising a plurality of interconnected nodes having input/output ports for routing packets of data sent from a first node to a second node with one of the nodes specifying a route including nodes through which the packets are to be transported and output address of exit ports from which the packets exit each node, a means for routing the packets of data comprising:

first means for generating, at a node, a data packet including a Routing List (RL) containing Routing Codes each one being specific to a node in the route and formed by means for combining the port addresses of the node input port and the node output port; and

second means for forwarding the generated data packet onto the communications network so that other nodes in the route use the Routing Code (RC) to identify node ports whereat the data packet exits a node.

17. The apparatus of claim 16 wherein the combining of port addresses is done by a circuit means for XORing the input port address and output port address.

18. The apparatus of claim 16 further including means for receiving the packet at each node of the route;

and means for extracting from the Routing List the Routing Code specific to the node;

means for determining the output port of the node from the Routing Code RC and the input port address; and

means for sending the data packet to the so-determined output port.

19. The apparatus of claim 18 wherein the determining means includes a circuit for XORing the routing code and the input port address.

20. A communications network comprising:

a plurality of interconnected nodes having input/output ports for routing packets of data sent from a first node to a second node with one of the nodes specifying a route including nodes through which the packets are to be transported and output address of exit ports from which the packets exit each node;

generating means at a node for generating a data packet including a Routing List (RL) containing Routing Codes each one being specific to a node in the route and formed by means for combining the port addresses of the node input port and the node output port; and

means for forwarding the generated data packet onto the communications network so that other nodes in the route use the Routing Code (RC) to identify node ports whereat the data packet exits a node.

21. The apparatus of claim 20 wherein the node includes:

a switch fabric (62);

a plurality of link adapters coupled to the switch fabric; and

a node management adapter for managing the node.

22. The node of claim 21 wherein each link adapter includes

a framing control IN circuit means for managing a serial bit input data flow;

a framing control OUT circuit means for managing a serial bit output data flow;

a routing circuit means for processing the routing list including rotating said list;

a feedback circuit means coupled to the routing circuit means for feeding back packets from an input link to an output link;

and a bus interface means for interfacing the adapter to the switch fabric.

23. A node adapter comprising:

a framing control IN circuit means for managing a serial bit input data flow;

a framing control OUT circuit means for managing a serial bit output data flow;

a routing circuit means for processing a routing list including rotating said list;

a feedback circuit means coupled to the routing circuit means for feeding back packets from an input link to an output link;

and a bus interface means for interfacing the adapter to the switch fabric.