Packet routing system and method with quasi-real-time control

• US 5,579,307 A
• Filed: 03/23/1995
• Issued: 11/26/1996
• Est. Priority Date: 03/23/1995
• Status: Expired due to Term

• Current Assignee: CDC Propriete Intellectuelle
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Cutler, Jr., Victor H., Richetta, Peter J., Peterson, Kenneth M.
• Primary Examiner(s): Safourek, Benedict V.
• Assistant Examiner(s): NGO, RICKY QUOC
• Application Number:
  US08/409,288
• Time in Patent Office: 614 Days
• Field of Search: 370/17, 370/54, 370/58.1, 370/58.2, 370/58.3, 370/60, 370/92, 370/94.1, 370/104.1, 370/105, 379/220, 395/200, 455/12.1, 455/13.1, 455/13.2, 342/350, 375/219
• US Class Current: 370/409
• CPC Class Codes: H04B 7/1856 for call routing
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04W 40/38 adapting due to varying relative distances between nodes

Abstract

In a system that includes a constellation of satellite communication nodes, information packets are routed through the constellation using routing tables stored in each communication node. When a packet is received at a node, the packet'"'"'s destination and routing table ID are read. One of several routing tables are selected using a mapping table. Each of the several routing tables has a different routing instruction set. The packet is routed away from the node using the selected routing table. When system traffic is heavy, or some of the communication links are overloaded or have failed, routing table control bits are sent to the nodes updating the mapping table. Packets are subsequently routed using different sets of routing tables, such as ones having greater hop counts.

Claims

1. A method of routing data packets among nodes of a communication system, said nodes coupled to each other by links wherein each of said nodes have a plurality of routing tables stored therein and a mapping table stored therein, said mapping table referring to one of said plurality of routing tables for each of a plurality of routing table identifiers, said method comprising the steps of:

receiving mapping table control bits at one of said nodes;

updating said mapping table using said mapping table control bits, the updating step causing said mapping table to reference other routing tables for each of said routing table identifiers;

receiving a data packet at said one of said nodes, said data packet including one of said routing table identifiers;

reading a destination routing code and said routing table identifier from said data packet;

identifying one routing table of said plurality of routing tables by indexing said mapping table using said routing table identifier;

indexing said one routing table based on said destination routing code to determine an exit link; and

routing said data packet away from said one of said nodes over said exit link.

2. A method as claimed in claim 1 further comprising the step of assigning to each of said data packets, one routing table identifier by a source node wherein said routing table identifiers assigned in the assigning step exhibit a substantially randomly distribution.

3. A method as claimed in claim 1 wherein each of said data packets has a header, and wherein said routing table identifier includes least significant bits (LSB'"'"'s) of said header, and wherein the step of reading includes the step of reading said LSB'"'"'s of said header.

4. A method as claimed in claim 3 wherein said header includes a logical channel number (LCN) and wherein the step of reading includes the step of reading LSB'"'"'s of said LCN.

5. A method as claimed in claim 1 further comprising the steps of:

generating said mapping table control bits for a heavy traffic load situation; and

transmitting said mapping table control bits to each of said nodes when said heavy traffic load situation occurs,

and wherein the updating step includes the step of updating said mapping table using said mapping table control bits causing said mapping table to reference each of said routing tables for each of said routing table identifiers.

6. A communication system that routes data packets comprising:

a plurality of nodes, each node of said plurality having a memory for storing a plurality of routing tables and a mapping table therein, said mapping table referring to one of said plurality of routing tables for each of a plurality of routing table identifiers;

communication links coupling said nodes;

a first transceiver associated with each of said nodes for receiving mapping table control bits;

a processor associated with each of said nodes with means for updating said mapping table using said mapping table control bits, the processor causing said mapping table to reference other routing tables for each of said routing table identifiers; and

a second transceiver associated with each of said nodes for reading a destination routing code and said routing table identifier from said data packets, wherein

said processor has means for identifying one routing table of said plurality of routing tables by indexing said mapping table using said routing table identifier and said destination routing code to determine an exit link, said exit link being one of said communication links, and

wherein said second transceiver routes said data packets away from one of said nodes over said exit link.

7. A communication system as claimed in claim 6 wherein said processor includes means for assigning each of said data packets said routing table identifier by a source node wherein said routing table identifiers exhibit a substantially randomly distribution.

8. A communication system as claimed in claim 6 wherein each of said data packets has a header, and wherein said routing table identifier includes least significant bits (LSB'"'"'s) of said header, and wherein the transceiver includes means for reading said LSB'"'"'s of said header.

9. A communication system as claimed in claim 8 wherein said header includes a logical channel number (LCN) and wherein the means for reading includes means for reading LSB'"'"'s of said LCN.

10. A communication system as claimed in claim 6 further comprising a control facility that includes:

means for generating said mapping table control bits for a heavy traffic load situation; and

means for transmitting said mapping table control bits to each of said nodes when said heavy traffic load situation occurs, and

wherein the means for updating includes means for updating said mapping table using said mapping table control bits causing said mapping table to reference each of said routing tables for each of said routing table identifiers.

11. A method of routing data packets among nodes of a communication system, each of said nodes having a mapping table and a plurality of routing tables stored therein, said method comprising the steps of:

receiving mapping table control bits at one of said nodes, said mapping table control bits causing said mapping table to reference particular routing tables of said plurality of routing tables for a plurality of routing table identifiers;

updating said mapping tables using said mapping table control bits, the updating step causing said mapping tables to reference other routing tables for each of said routing table identifiers;

reading a destination routing code and one of said routing table identifiers from a data packet;

identifying one routing table of said plurality of routing tables by indexing said mapping table using said one of said routing table identifiers;

identifying an exit link by indexing said one routing table based on said destination routing code; and

routing said data packet away from said one of said nodes over said exit link.