Data routing method and apparatus for communication systems having multiple nodes

• US 5,572,512 A
• Filed: 07/05/1995
• Issued: 11/05/1996
• Est. Priority Date: 07/05/1995
• Status: Expired due to Term

• Current Assignee: Motorola Solutions, Inc.
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Happ, Henry J. III, Cutler, Victor H. Jr.
• Primary Examiner(s): HSU, ALPUS
• Application Number:
  US08/498,213
• Time in Patent Office: 489 Days
• Field of Search: 370/13, 370/16, 370/54, 370/60, 370/94.1, 370/94.3, 340/825.03, 340/826, 340/827, 379/219, 379/220, 379/221, 379/271, 379/272, 379/273
• US Class Current: 370/248
• 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 47/10 Flow control; Congestion control

Abstract

A method and apparatus for balancing data packet routing through a communication system (10) and for routing data packets based on their type is accomplished by using multiple routing table pages (152, 154) and page maps (180, 190) stored in nodes (100-112). For a given data packet type, a first page map (180) is used to select a routing table page (152, 154) so that only certain types of data may be routed through a target node (100). In a test mode, a neighboring node (102-112) will be configured such that it can route test data packets through the target node (100) while not routing other types of data packets through the target node (100). For a given routing number, a second page map (190) is used to select a routing table page (152, 154) so that traffic loads are balanced throughout the system (10).

Claims

1. A method for routing a data packet through a communication system comprising a selected node and neighboring nodes that communicate directly with the selected node, wherein the data packet has a packet destination variable that specifies an intended destination of the data packet, the method comprising the steps of:

a) generating, for a neighboring node, routing instructions comprising a first set of the routing instructions and a second set of the routing instructions, the first set having routing directions for assigned destination identifiers recognized by the communication system, wherein no routing direction of the first set instructs the neighboring node to route the data packet in a direction of the selected node, and the second set having the routing directions for the assigned destination identifiers, wherein at least one of the routing directions of the second set instructs the neighboring node to route the data packet in the direction of the selected node;

b) sending the routing instructions to the neighboring node;

c) receiving the data packet by the neighboring node, the data packet having a routing number and the packet destination variable, the routing number for determining which routing instruction of the first set or the second set to use, and the packet destination variable for correlating with the assigned destination identifiers in the first set and the second set;

d) evaluating the routing number to determine whether the data packet should be routed according to the first set or the second set;

e) if the data packet should be routed according to the first set, correlating the packet destination variable with the assigned destination identifiers of the first set to determine in which of the routing directions to route the data packet;

f) if the data packet should be routed according to the second set, correlating the packet destination variable with the assigned destination identifiers of the second set to determine in which of the routing directions to route the data packet; and

g) routing the data packet according to a direction determined in steps e) and f).

2. The method as claimed in claim 1, wherein the data packet may take at least one alternative path through the communication system, and the step a) of generating the routing instructions comprises the steps of:

a1) generating the first set to include at least one first page of routing instructions, wherein a first page corresponds to an alternative path for the data packet and none of the at least one of the routing instructions of the at least one first page instructs the neighboring node to route the data packet in the direction of the selected node; and

a2) generating the second set to include at least one second page of routing instructions, wherein at least one of the routing instructions of the at least one second page instructs the neighboring node to route the data packet in the direction of the selected node.

3. The method as claimed in claim 2, further comprising the steps of:

h) creating a data structure that correlates possible routing numbers to one of the at least one first page or the at least one second page;

i) sending the data structure to the neighboring node; and

wherein the step d) of evaluating the routing number comprises the step of correlating the routing number to the data structure to determine which of the at least one first page or the at least one second page corresponds to the routing number.

4. The method as claimed in claim 3, further comprising the steps of:

j) sending a message to the neighboring node to alter the data structure so that at least one of the possible routing numbers correlates to a different one of the at least one first page or the at least one second page; and

k) altering the data structure according to the message.

5. The method as claimed in claim 3, further comprising the steps of:

j) creating a bias value which is used to offset the routing number by an index into the data structure;

k) sending a first message to the neighboring node that includes the bias value;

wherein step e) comprises the step of adding the bias value to the routing number prior to correlating the routing number; and

wherein step f) comprises the step of adding the bias value to the routing number prior to correlating the routing number.

6. The method as claimed in claim 1, further comprising the steps of:

h) creating an update message that has a time of execution and a new routing instruction that corresponds to an old routing instruction in the first set or the second set;

i) sending the update message to the neighboring node; and

j) at the time of execution, replacing the old routing instruction with the new routing instruction.

7. A method for routing a data packet through a communication system comprising a selected node and neighboring nodes that communicate directly with the selected node, wherein the data packet has a packet destination variable that specifies an intended destination of the data packet, the method comprising the steps of:

a) generating, for a neighboring node, routing instructions comprising a first set of the routing instructions and a second set of the routing instructions, the first set having routing directions for assigned destination identifiers recognized by the communication system, wherein no routing direction of the first set instructs the neighboring node to route the data packet in a direction of the selected node, and the second set having the routing directions for the assigned destination identifiers, wherein at least one of the routing directions of the second set instructs the neighboring node to route the data packet in the direction of the selected node;

b) sending the routing instructions to the neighboring node;

c) receiving the data packet, the data packet having a type and the packet destination variable, the type for determining which routing instruction of the first set or the second set to use, and the packet destination variable for correlating with the assigned destination identifiers in the first set and the second set;

d) evaluating the type to determine whether the data packet should be routed to the selected node according to the first set or the second set;

e) if the data packet should be routed according to the first set, correlating the packet destination variable with the assigned destination identifiers of the first set to determine in which of the routing directions to route the data packet;

f) if the data packet should be routed according to the second set, correlating the packet destination variable with the assigned destination identifiers of the second set to determine in which of the routing directions to route the data packet; and

g) routing the data packet according to a direction determined in steps e) and f).

8. The method as claimed in claim 7, wherein a number of possible data packet types exist within the communication system and the step a) of generating the routing instructions comprises the step of:

a1) generating the first set to include at least one first page of routing instructions, wherein a first page corresponds to a first type of the data packet and none of the at least one of the routing instructions of the at least one first page instructs the neighboring node to route the data packet in the direction of the selected node; and

a2) generating the second set to include at least one second page of routing instructions, wherein a second page corresponds to a second type of the data packet and at least one of the routing instructions of the at least one second page instructs the neighboring node to route the data packet in the direction of the selected node.

9. The method as claimed in claim 8, further comprising the steps of:

h) creating a data structure that maps the possible data packet types to one of the at least one first page or to the at least one second page;

i) sending the data structure to the neighboring node; and

wherein the step d) of evaluating the type comprises the step of correlating the type to the data structure to determine which of the at least one first page or the at least one second page corresponds to the type.

10. The method as claimed in claim 9, wherein at least one additional data packet type is possible within the communication system, the method further comprising the step of:

a3) generating at least one additional set of routing instructions that includes at least one additional page of the routing instructions, an additional page corresponding to an additional data packet type;

wherein step h) comprises the step of creating the data structure that maps the at least one additional data packet type to the at least one additional page; and

wherein step d) of evaluating the type comprises the step of correlating the type to the data structure to determine which of the at least one first page, the at least one second page, or the at least one additional page corresponds to the type.

11. The method as claimed in claim 9, further comprising the steps of:

j) sending a message to the neighboring node to alter the data structure so that at least one of the possible data packet types correlates to a different one of the at least one first page or the at least one second page; and

k) altering the data structure according to the message.

12. The method as claimed in claim 8, wherein the communication system further comprises multiple communication units which send and receive mission type data and the step d) of evaluating the type comprises the steps of:

d1) evaluating the type to determine whether the data packet contains the mission type data that originates from a communication unit;

d2) where the type indicates that the data packet contains the mission type data, determining from a routing number included in the data packet which of the at least one first page or the at least one second page to use to route the data packet, wherein the routing number is for determining which routing instruction of the first set or the second set to use; and

d3) where the type indicates that the data packet does not contain mission type data, not evaluating the routing number.

13. The method as claimed in claim 12, wherein the step d2) of determining comprises the step of correlating the routing number with a second data structure that maps possible values of the routing number to the at least one first page or the at least one second page.

14. A method for routing a data packet through a communication system comprising a selected node and neighboring nodes that communicate directly with the selected node, wherein the data packet has a packet destination variable that specifies an intended destination of the data packet, the method comprising the steps of:

a) generating, for a neighboring node, routing instructions comprising a first set of the routing instructions and a second set of the routing instructions, the first set having routing directions for assigned destination identifiers recognized by the communication system, wherein no routing direction of the first set instructs the neighboring node to route the data packet in a direction of the selected node, and the second set having the routing directions for the assigned destination identifiers, wherein at least one of the routing directions of the second set instructs the neighboring node to route the data packet in the direction of the selected node;

b) receiving the data packet, the data packet having a routing number and the packet destination variable, the routing number for determining which routing instruction of the first set or the second set to use, and the packet destination variable for correlating with the assigned destination identifiers in the first set and the second set;

c) evaluating the routing number to determine whether the data packet should be routed according to the first set or the second set;

d) if the data packet should be routed according to the first set, correlating the packet destination variable with the assigned destination identifiers of the first set to determine in which of the routing directions to route the data packet;

e) if the data packet should be routed according to the second set, correlating the packet destination variable with the assigned destination identifiers of the second set to determine in which of the routing directions to route the data packet; and

f) routing the data packet according to a direction determined in steps d) and e).

15. A method for routing a data packet through a communication system comprising a selected node and neighboring nodes that communicate directly with the selected node, wherein the data packet has a packet destination variable that specifies an intended destination of the data packet, the method comprising the steps of:

a) receiving, by a neighboring node, routing instructions comprising a first set of the routing instructions and a second set of the routing instructions, the fast set having routing directions for assigned destination identifiers recognized by the communication system, wherein no routing direction of the first set instructs the neighboring node to route the data packet in a direction of the selected node, and the second set having the routing directions for the assigned destination identifiers, wherein at least one of the routing directions of the second set instructs the neighboring node to route the data packet in the direction of the selected node;

b) receiving the data packet, the data packet having a type and the packet destination variable, the type for determining which routing instruction of the first set or the second set to use, and the packet destination variable for correlating with the assigned destination identifiers in the first set and the second set;

c) evaluating the type to determine whether the data packet should be routed to the selected node according to the first set or the second set;

d) if the data packet should be routed according to the first set, correlating the packet destination variable with the assigned destination identifiers of the first set to determine in which of the routing directions to route the data packet;

e) if the data packet should be routed according to the second set, correlating the packet destination variable with the assigned destination identifiers of the second set to determine in which of the routing directions to route the data packet; and

f) routing the data packet according to a direction determined in steps d) and e).

16. A method for testing operability of a selected node in a communication system, wherein the communication system comprises a system control facility and multiple nodes which communicate through communication links, and neighboring nodes support the communication links with the selected node, the method comprising the steps of:

a) generating, for a neighboring node, routing instructions comprising a first set of the routing instructions and a second set of the routing instructions, the first set having routing directions for assigned destination identifiers recognized by the communication system, wherein no routing direction of the first set instructs the neighboring node to route a data packet in a direction of the selected node, and the second set having the routing directions for the assigned destination identifiers, wherein at least one of the routing directions of the second set instructs the neighboring node to route the data packet in the direction of the selected node;

b) sending the routing instructions to the neighboring node;

c) creating at least one test packet for testing operability of the selected node;

d) sending the at least one test packet to the neighboring node;

e) routing the at least one test packet by correlating a packet destination variable contained within the at least one test packet with the assigned destination identifiers in the second set to determine a direction of routing;

f) evaluating telemetry data that indicates whether routing the at least one test packet through the selected node was successful; and

g) where routing the at least one test packet was successful, sending an instruction to the neighboring node to route future data packets by correlating the packet destination variable contained within the future data packets with the assigned destination identifiers in the second set to determine the direction of routing.

17. The method as claimed in claim 16, further comprising the step of sending a test initiation message to the neighboring node to route the at least one test packet according to the second set, and to route other types of data packets according to the first set.

18. The method as claimed in claim 17, wherein the step a) of generating the routing instructions comprises the steps of:

a1) generating the first set to include at least one first page of routing instructions, wherein a first page corresponds to a non-test type of the data packet and none of the routing instructions of the at least one first page instruct the neighboring node to route the data packet in the direction of the selected node; and

a2) generating the second set of routing instructions to include at least one second page of routing instructions, wherein a second page corresponds to a test type of the data packet and at least one of the routing instructions of the at least one second page instructs the neighboring node to route the data packet in the direction of the selected node.

19. A communication system comprising:

a system control facility for generating and sending routing instructions to a neighboring node, the routing instructions comprising a first set of the routing instructions and a second set of the routing instructions, the first set having routing directions for assigned destination identifiers recognized by the communication system, wherein none of the routing directions of the first set instruct the neighboring node to route a data packet in a direction of a selected node, and the second set having the routing directions for the assigned destination identifiers, wherein at least one of the routing directions instructs the neighboring node to route the data packet in the direction of the selected node; and

multiple nodes in communication proximity to the system control facility, the multiple nodes comprising the selected node and neighboring nodes that directly communicate with the selected node, the neighboring nodes for receiving the routing instructions, receiving the data packet, the data packet having a type and a packet destination variable, the type for determining which routing instruction of the first set or the second set to use, and the packet destination variable for correlating with the assigned destination identifiers in the first set and the second set, evaluating the type to determine whether the data packet should be routed to the selected node according to the first set or the second set, if the data packet should be routed according to the first set, correlating the packet destination variable with the assigned destination identifiers of the first set to determine in which of the routing directions to route the data packet, if the data packet should be routed according to the second set, correlating the packet destination variable with the assigned destination identifiers of the second set to determine in which of the routing directions to route the data packet, and sending the data packet according to a direction so determined.

20. A communication node in a communication system having a system control facility and neighboring nodes that support communication links with the communication node, the communication node comprising:

at least one down-link receiver for receiving routing instructions, the routing instructions comprising a first t of the routing instructions and a second set of the routing instructions, the first set having routing directions for assigned destination identifiers recognized by the communication system, wherein none of the routing directions of the first set instruct the communication node to route a data packet in a direction of a selected node, and the second set having the routing directions for the assigned destination identifiers, wherein at least one of the routing directions of the second set instructs the communication node to route the data packet in the direction of the selected node;

at least one data packet receiver for receiving the data packet, the data packet having a type and a packet destination variable, the type for determining which routing instruction of the first set or the second set to use, and the packet destination variable for correlating with the assigned destination identifiers in the first set and the second set;

a node controller coupled to the at least one down-link receiver and the at least one data packet receiver, the node controller for evaluating the type to determine whether the data packet should be routed to the selected node according to the first set or the second set, if the data packet should be routed according to the first set, correlating the packet destination variable with the assigned destination identifiers of the first set to determine in which of the routing directions to route the data packet, if the data packet should be routed according to the second set, correlating the packet destination variable with the assigned destination identifiers of the second set to determine in which of the routing directions to route the data packet; and

at least one data packet transmitter coupled to the node controller, the at least one data packet transmitter for sending the data packet according to a direction determined by the node controller.