US5477536A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for routing information between nodes in a communication network
Assignee: Intergraph Corp
•
Filing: 1993-12-07
•
Granted: 1995-12-19
•
Expires: 2013-12-07
Abstract
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.
Inventors
- 👤 Jean L. Picard
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 23:31
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/34
Claims Analysis
Total Claims: 29
Claim 1
Independent Claim
220 words
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.
Claim 2
Independent Claim
220 words
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.
Claim 3
Dependent Claim
31 words
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.
Claim 4
Dependent Claim
72 words
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.
Claim 5
Dependent Claim
145 words
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.
Claim 6
Independent Claim
261 words
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.
Claim 7
Independent Claim
261 words
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.
Claim 8
Dependent Claim
36 words
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.
Claim 9
Dependent Claim
75 words
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.
Claim 10
Dependent Claim
150 words
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.
Claim 11
Independent Claim
114 words
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.
Claim 12
Dependent Claim
152 words
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.
Claim 13
Dependent Claim
152 words
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.
Claim 14
Dependent Claim
24 words
The method of claim 10 wherein the combining of port addresses is done by XORing the input port address and the output port address.
Claim 15
Dependent Claim
56 words
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.
Claim 16
Dependent Claim
19 words
The method of claim 12 wherein the determining step includes XORing the routing code and the input port address.
Claim 17
Dependent Claim
46 words
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.
Claim 18
Dependent Claim
56 words
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.
Claim 19
Dependent Claim
150 words
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.
Claim 20
Dependent Claim
150 words
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.
Claim 21
Dependent Claim
27 words
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.
Claim 22
Dependent Claim
64 words
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.
Claim 23
Dependent Claim
22 words
The apparatus of claim 18 wherein the determining means includes a circuit for XORing the routing code and the input port address.
Claim 24
Dependent Claim
139 words
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.
Claim 25
Dependent Claim
139 words
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.
Claim 26
Dependent Claim
32 words
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.
Claim 27
Dependent Claim
86 words
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.
Claim 28
Dependent Claim
80 words
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.
Claim 29
Dependent Claim
80 words
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.
References Cited (Backward Citations)
WO1984000266A1
Cited
US4993018A
Cited
US5367518A
Cited
EP0377360A1
Cited
US4939726A
Cited
US5115433A
Cited
WO1992005648A1
Cited
US5309433A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-12-18 | 1999-06-19 | 1999-12-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-12-18 | 2003-06-19 | 2003-12-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-12-18 | 2007-06-19 | 2007-12-19 | $7700.00 | Window Closed / Lapsed |