Packet routing system and method therefor

• US 5,467,345 A
• Filed: 05/31/1994
• Issued: 11/14/1995
• Est. Priority Date: 05/31/1994
• Status: Expired due to Fees

• Current Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Young, Kenneth P., Richetta, Peter, Davieau, Gerald J., Cutler, Victor H. Jr.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): NGO, RICKY QUOC
• Application Number:
  US08/251,459
• Time in Patent Office: 532 Days
• Field of Search: 370/60, 370/57, 370/24, 370/95.3, 370/97, 370/94.3, 370/94.1, 370/94.2, 370/29, 370/30, 370/33, 370/16, 370/75, 370/76, 370/95.1, 370/104.1
• US Class Current: 370/229
• CPC Class Codes: H04B 7/1856 for call routing
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04W 40/18 based on predicted events
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update
• CPC Class Codes: H04W 40/38 adapting due to varying relative distances between nodes

Abstract

Information packets are routed among a constellation of satellite nodes in a communication system in a distributed, yet systematic fashion. Routing tables for each node are generated in advance by a recursive process that considers link usage and anticipated link loading for different times and states of the constellation. Routing tables are generated centrally, distributed to, and maintained in each satellite node. The routing tables are updated regularly to reflect anticipated traffic loading and physical changes in node connectivity within the constellation which occur as a result of satellite motion. The tables are also updated responsively to reflect changes in network connectivity which occur because of failures that may occur in the cross-links or satellite nodes.

Claims

1. In a communication system comprised of nodes that communicate with each other over links, a method of routing data packets among said nodes comprising the steps of:

(a) partitioning an anticipated system traffic load into traffic levels, each traffic level being a subset of said anticipated system traffic load;

(b) providing an initial routing instruction set for each node;

(c) performing a routing simulation using said initial routing instruction set and traffic loading of said one traffic level;

(d) finding overloaded links by comparing a link capacity of each of said links with a utilized capacity of each of said links during said routing simulation;

(e) performing a second routing simulation using traffic loading of said one traffic level excluding links determined to be overloaded from step (d);

(f) generating a new routing instruction set based on said second routing simulation, said links determined to be overloaded being excluded from said new routing instruction set; and

(g) routing said data packets away from one of said nodes according to said new routing instruction set.

2. A method as claimed in claim 1 further comprising the step of repeating steps (d) and (e) until no links are found to be overloaded.

3. A method as claimed in claim 2 further comprising the step of repeating steps (b) through (f) for each of said traffic levels.

4. A method as claimed in claim 3 wherein step (f) further comprises the step of generating a routing table for each of said nodes, said routing table comprising said new routing instruction set for each of said traffic levels.

5. A method as claimed in claim 1 wherein step (b) further comprises the step of determining minimum hop routes between source and destination pairs of said nodes,

6. A method as claimed in claim 5 wherein step (d) further comprises the step of marking said overloaded links as failed links, and wherein said determining step comprises the step of determining said minimum hop routes without considering said links marked as failed links.

7. In a communication system comprised of nodes that communicate with each other over links, a method of routing data packets among said nodes comprising the steps of:

(a) predicting an actual traffic load during a planning interval to determine an anticipated system traffic load during said planning interval, said planning interval being a predetermined period of time;

(b) partitioning said anticipated system traffic load into traffic levels, each traffic level being a subset of said anticipated system traffic load;

(c) providing a routing instruction set for each node for one of said traffic levels;

(d) performing a routing simulation using said initial routing instruction set and traffic loading of said one traffic level;

(e) finding overloaded links by comparing a link capacity of each of said links with a utilized capacity of each of said links during said routing simulation;

(f) performing a second routing simulation using traffic loading of said one traffic level excluding links determined to be overloaded from step (d);

(g) generating a new routing instruction set based on said second routing simulation, said links determined to be overloaded being excluded from said new routing instruction set;

(h) repeating steps (e) through (g) until no links are overloaded;

(i) repeating steps (c) through (h) for each of said traffic levels;

(j) repeating steps (a) through (i) for subsequent planning intervals; and

(k) generating a routing table for each of said nodes, said routing table comprising said new routing instruction set for each of said traffic levels

(l) routing said data packets away from one of said nodes according to said routing table for said one node.

8. A method as claimed in claim 7 wherein said predicting step includes the step of sampling an actual traffic load during said planning interval to determine said anticipated system traffic load for said planning interval.

9. A method as claimed in claim 7 wherein step (k) includes the step of repeating steps (a) through (j) for said subsequent planning intervals, each planning interval being between fifteen seconds and one minute, and wherein said subsequent planning intervals comprise a planning period, said planning period being approximately twenty-four hours.

10. A method as claimed in claim 7 further comprising the step of sending said routing table for each of said nodes to each of said nodes.

11. A method as claimed in claim 7 wherein each of said data packets include a destination routing code that indicates a destination node for each of said data packets, said method further comprising the step of receiving one of said data packets at said one of said nodes, and the step of routing said data packets comprises the steps of:

reading said destination routing code from said one data packet;

reading a connection identification (ID) from said one data packet;

indexing said routing table based on said connection ID and said destination routing code; and

determining an exit link of said one node by reading said routing table.

12. A method as claimed in claim 11 wherein said connection ID includes least significant bits (LSB), and wherein the reading said connection ID step includes the step of reading said LSBs of said connection ID, and wherein the indexing step includes the step of pointing to one of several portions of said routing table based on said LSB, each portion of said routing table being associated with one of said traffic layers.

13. A method as claimed in claim 11 further comprising the step of determining a packet type from said one data packet, and wherein said indexing step further comprises the step of indexing one of said routing tables based on said packet type when said packet type indicates that said one data packet contains non-voice data.

14. In a communication system comprised of nodes that communicate with each other over links, a method of routing data packets among said nodes wherein said data packets include a destination routing code, the method comprising the steps of:

(a) partitioning an anticipated system traffic load into traffic levels, each traffic level being a subset of said anticipated system traffic load;

(b) providing a routing instruction set for each node for one of said traffic levels;

(c) performing a routing simulation using said routing instruction set and traffic loading of said one traffic level;

(d) finding overloaded links by comparing a link capacity of each of said links with a utilized capacity of each of said links during said routing simulation;

(e) performing a second routing simulation using traffic loading of said one traffic level excluding links determined to be overloaded from step (d);

(f) generating a new routing instruction set based on said second routing simulation, said links determined to be overloaded being excluded from said new routing instruction set, said new routing instruction set associating said destination routing code with an exit link of each of said nodes; and

(g) routing said data packets away from one of said nodes according to said new routing instruction set.

15. A method as claimed in claim 14 wherein step (f) further comprises the step of generating said new routing instruction set using a robustness criteria for each of said links, said robustness criteria including a reduced link capacity.

16. A method as claimed in claim 15 wherein said robustness criteria is a predetermined percentage of said link capacity associated with each of said links, and wherein step (f) further comprises the step of generating said new routing instruction set based on said predetermined percentage of said link capacity.

17. A method as claimed in claim 15 wherein said nodes are satellites that move with respect to each other, said satellites moving in an associated orbital plane, and wherein at least some of said links are cross-links coupling said nodes located in adjacent orbital planes, and wherein said link capacity of said cross-links varies as a function of an orbital position of each of said satellites within said associated orbital plane, and wherein step (f) further comprises the step of generating said new routing instruction set considering said link capacity of said cross-links for a planning interval associated with said orbital position of each of said satellites, said planning interval being a predetermined period of time.

18. A method as claimed in claim 17 wherein some of said cross-links are shut off as said satellites change said orbital position,

wherein:

step (d) further comprises the step of marking said cross-links that are shut off as failed links, and

step (e) further comprises the step of performing said second routing simulation without considering said failed links, and

step (f) further comprises the step of generating a routing table for each of said nodes, said routing table comprising said new routing instruction set for each of said traffic levels, said routing table not including any of said failed links.

19. A method as claimed in claim 15 wherein step (d) further comprises the step of determining whether any of said links that will be overloaded by comparing a used capacity of each link with an available capacity of each link, said used capacity based on said routing instruction set, said available capacity based on said robustness criteria for each of said links.

20. A method of routing a data packet among nodes in a constellation of nodes coupled by links, said nodes being part of a communication system wherein said data packet includes a destination routing code that indicates a destination node for said data packet, said method comprising the steps of:

receiving said data packet at one of said nodes;

reading said destination routing code from said data packet;

reading a connection identification (ID) from said data packet;

reading least significant bits (LSB) from said connection ID;

indexing a routing table stored in said one of said nodes based on said connection ID and said destination routing code;

determining an exit link of said one node by reading said routing table; and

routing said data packet away from said one node over said exit link, and

wherein said routing table being generated by the steps of;

partitioning an anticipated system traffic load of said communication system into traffic levels, each traffic level being a subset of said anticipated system traffic load;

generating an initial routing instruction set for each node for one of said traffic levels;

determining if any of said links will be overloaded based on said initial routing instruction set;

re-generating, when said any of said links are determined to be overloaded, said routing instruction set for each node by excluding said links determined to be overloaded;

repeating the re-generating and determining steps until no links are determined to be overloaded;

repeating the generating step, the determining step and the re-generating step for each of said traffic levels; and

generating said routing table for each of said nodes, said routing table comprising said routing instruction set for each of said traffic levels,

and wherein said indexing step includes the step of pointing to one of several portions of said routing table based on said LSB, each portion of said routing table being associated with one of said traffic levels.

21. A method of recursively determining routing for data packets in a communication system comprised of nodes connected by links, said method comprising the steps of:

(a) partitioning an anticipated system traffic load into traffic levels, each traffic level being a subset of said anticipated system traffic load;

(b) generating an initial routing instruction set for each node for one of said traffic levels;

(c) determining if any of said links will be overloaded based on said initial routing instruction set;

(d) re-generating, when said any of said links are determined to be overloaded, said routing instruction set for each node by excluding said links determined to be overloaded

(e) repeating the re-generating and determining steps until no links are determined to be overloaded;

(f) repeating steps (b), (c) and (d) for each of said traffic levels;

(g) generating a routing table for each of said nodes, said routing table comprising said routing instruction set for each of said traffic levels; and

(h) sending said routing table for each of said nodes to said each node

wherein said step (a) partitions said anticipated system traffic load into traffic levels for each of a plurality of planning interval, said planning intervals, each planning interval being a predetermined period of time, said plurality of planning intervals comprising a planning period, and

wherein said method further comprises the step of repeating steps a through g for each of said planning intervals in a planning period, said planning interval being between fifteen seconds and one minute, said planning period being approximately twenty-four hours.

22. A communication system that routes a data packet comprising:

a plurality of nodes that move with respect to each other, said nodes coupled by communication links;

transceivers associated with each node of said plurality of said nodes for routing said data packet over said communication links;

a memory for storing a routing table;

a first processor for generating said routing table; and

a second processor for reading said routing table and instructing said transceivers to send said data packet away from one of said nodes based on said routing table, and said first processor comprising;

means for partitioning an anticipated system traffic load into traffic levels, each traffic level being a subset of said anticipated system traffic load;

means for generating a routing instruction set for said one of said nodes for said traffic levels;

means for determining if any of said communication links will be overloaded based on said routing instruction set; and

means for re-generating, when said any of said communication links are determined to be overloaded, said routing instruction set for said one of said nodes by excluding said communication links determined to be overloaded.