Responsive routing control method and apparatus

• US 5,903,545 A
• Filed: 02/19/1997
• Issued: 05/11/1999
• Est. Priority Date: 04/24/1995
• Status: Expired due to Term

• Current Assignee: CDC Propriete Intellectuelle
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Sabourin, Donald John, Dorin, Jeffrey Stuart, Happ, III, Henry Joseph
• Primary Examiner(s): VU, HUY DUY
• Application Number:
  US08/801,334
• Time in Patent Office: 811 Days
• Field of Search: 370/351, 370/216, 370/217, 370/218, 370/219, 370/220, 370/221, 370/222, 370/223, 370/224, 370/225, 370/226, 370/227, 370/228, 370/242, 370/244, 370/249, 370/250, 370/389 , 370/392, 370/422, 370/426, 370/522
• US Class Current: 370/225
• CPC Class Codes: H04B 7/18539 Arrangements for managing radio, resources, i.e. for establishing or releasing a connection
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/18 Loop-free operations
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/42 Centralised routing

Abstract

A method and apparatus for controlling routing within a communication system (10) modifies (258) routing tables (220, 230, 232, 234, 236) located within nodes (150) so that received data packets are not returned directly to their sending nodes. In response to detection (352) of a failed link, a node (150) modifies (354) its routing tables (220, 230, 232, 234, 236) to avoid the failed link. After notification (402) of the failed link, a control facility (28) responds by creating (404) commands that compensate for the failed link. The control facility (28) sends (404) the commands to at least the node (150) that detected the failed link. If not already performed by the control facility (28), the node (150) then modifies (364, 366) its routing tables (220, 230, 232, 234, 236) so that data packets are not returned to their sending nodes, and to avoid the failed link.

Claims

1. A method for controlling message routing through a communication system, the communication system comprising multiple nodes which communicate through communication links, the method comprising the steps of:

a) routing, by a node, data packets received from sending nodes in accordance with at least one current routing table accessible by a receiving port of the node, wherein the at least one current routing table is used to determine to which transmitting port of the node the data packets should be sent;

b) determining, for each entry of the at least one current routing table, whether a routing command included in the entry will cause the receiving port to route a data packet directly back to a sending node which sent the data packet;

c) performing modifications to those entries of the at least one current routing table which would cause the receiving port to route the data packet directly back to the sending node, where the modifications will cause the receiving port not to route the data packet directly back to a sending node, the modifications resulting in at least one modified routing table;

d) receiving the data packet from the sending node by the receiving port; and

e) routing the data packet according to the at least one modified routing table.

2. The method as claimed in claim 1, wherein at least one alternative routing table is accessible to the node, and step b) comprises the steps of:

b1) locating an entry in the at least one current routing table that would cause the receiving port to route the data packet directly back to the sending node; and

b2) replacing the entry with an alternate entry in the at least one alternative routing table that would not cause the receiving port to route the data packet directly back to the sending node.

3. The method as claimed in claim 1, wherein the at least one current routing table comprises a node routing table and multiple port routing tables, and step b) comprises the steps of:

b1) performing modifications to node routing table entries so that the receiving port will not route the data packet directly back to the sending node, resulting in modified entries;

b2) sending the modified entries to the multiple port routing tables; and

b3) changing port routing table entries according to the modified entries.

4. The method as claimed in claim 1, wherein the node has multiple ports, each of the multiple ports supports a communication link, each of the multiple ports accesses a separate port routing table, and step b) comprises the step of performing the modifications, by each of the multiple ports, to the entries in the separate port routing table, resulting in a modified routing table for each of the multiple ports.

5. The method as claimed in claim 4, further comprising the step of changing the separate port routing table according to at least one update command which instructs the node to alter the separate port routing table.

6. The method as claimed in claim 1, further comprising the step of changing the at least one current routing table according to at least one update command which instructs the node to alter the at least one current routing table.

7. The method as claimed in claim 6, further comprising the step of receiving the at least one update command from a control facility prior to the changing step.

8. A method for controlling message routing through a communication system, the communication system comprising multiple nodes which communicate through communication links, the method comprising the steps of:

a) routing, by a receiving port of a node, data packets in accordance with at least one current routing table accessible by the receiving port, wherein routing the data packets involves determining, based on the at least one current routing table, to which transmitting port of the node the data packets should be sent;

b) executing at least one update command comprising information required for the node to change one or more entries of the at least one current routing table, the information having been created after making a determination, for each entry of the one or more entries, whether a routing command included in the entry will cause the receiving port to route a data packet directly back to a sending node which sent the data packet;

c) changing the one or more entries in the at least one current routing table according to the at least one update command so that the one or more entries, once changed, will cause the receiving port not to route the data packet directly back to the sending node, resulting in at least one modified routing table; and

d) routing the data packets according to the at least one modified routing table.

9. A routing apparatus for routing data packets through a communication system, the routing apparatus comprising:

a central processor for controlling routing of incoming data packets received by and outgoing data packets sent by the routing apparatus, and for determining, for entries within a node routing table, whether a routing command included in each of the entries will cause the node to route the incoming data packets directly back to a sending node that sent the incoming data packets, and for modifying the entries so that the entries will cause the receiving port not to route the data packets directly back to the sending node, and for further modifying the node routing table to avoid a failed communication link, wherein the node routing table originated from a control facility;

at least one port, coupled to the central processor, wherein when a port is functioning as a receiving port which receives the incoming data packets, the port uses the node routing table to determine to which transmitting port to send the incoming data packets, a port supporting a communication link and including;

a port processor for controlling a receiving device and a transmitting device;

the receiving device, coupled to the port processor, for receiving the incoming data packets from the communication link; and

the transmitting device, coupled to the port processor, for sending the outgoing data packets across the communication link.

10. A routing apparatus for routing data packets through a communication system, the routing apparatus comprising:

a memory device for storing a port routing table which originated from a control facility; and

at least one port, wherein a port of the at least one port is coupled to the memory device and supports a communication link and has

a processor for controlling routing of incoming data packets received by and outgoing data packets sent by the port, and for determining, for entries within the port routing table, whether a routing command included in each of the entries will cause the receiving port to route a data packet directly back to a sending node which sent the data packet, and for modifying the entries so that the entries will cause the receiving port not to route the data packet directly back to the sending node,

a receiving device, coupled to the processor, for receiving the incoming data packets from the communication link, and

a transmitting device, coupled to the processor, for sending the outgoing data packets across the communication link.

11. The routing apparatus as claimed in claim 10, further comprising a central processor, coupled to the port, for controlling modifications to the port routing table.

12. The routing apparatus as claimed in claim 10, wherein the port further comprises a memory device, coupled to the processor, for storing the port routing table.