Method and apparatus for adaptive directed route randomization and distribution in a richly connected communication network

• US 5,430,729 A
• Filed: 04/04/1994
• Issued: 07/04/1995
• Est. Priority Date: 04/04/1994
• Status: Expired due to Term

• Current Assignee: CDC Propriete Intellectuelle
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Rahnema, Moe
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Patel, Ajit
• Application Number:
  US08/222,067
• Time in Patent Office: 456 Days
• Field of Search: 370/941, 370/942, 370/60, 370/54, 370/943, 370/60.1, 370/16, 370/17, 395/200, 364/284, 364/284.3, 364/284.4, 364/242.94, 364/229, 364/229.3, 364/229.4, 364/229.5, 364/514
• US Class Current: 370/409
• CPC Class Codes: H04B 7/1856 for call routing
• CPC Class Codes: H04L 2012/5608 Satellite
• CPC Class Codes: H04L 2012/5619 Network Node Interface, e.g. tandem connections, transit switching
• 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 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections
• CPC Class Codes: H04W 40/248 Connectivity information update
• CPC Class Codes: H04W 40/34 Modification of an existing route

Abstract

In a global communication system that includes a constellation of satellite nodes that move with respect to each other, data packets are routed across communication links in a evenly distributed fashion. Uniform link usage is achieved within allowed routes determined by end to end transport delay criteria. The routing method computes routes in advance using an iterative process which selects routes for each source-destination pair from an allowed feasible set of alternative minimal hop routes by trying to equalize link usage probabilities for the links involved at each step of the route determination process. The routing method takes into account link failures and link and node shutdowns. Minimum hop routes are selected based on maximizing network routing entropy resulting in a uniform usage of the system'"'"'s communication links. Directed randomization of routes between source-destination pairs of nodes is implemented to prevent link congestion while minimizing packet transport delay. Individual routing tables are generated and maintained in each satellite node. The tables may be updated regularly to reflect changes in the traffic demand distribution and the physical node connectivity within the constellation which occur as a result of satellite motion and failures in the network.

Claims

1. In a communication system comprising a plurality of nodes that communicate with each other over links wherein each of said links has a link usage probability (LUP) associated therewith, said LUP being proportional to a number of times an associated link is part of a selected route, a method of routing data packets among said plurality of nodes comprising the steps of:

(a) finding alternative minimum hop routes between a source node and a destination node, each of said alternative minimum hop routes comprising a sequence of links over which to send a data packet;

(b) temporarily updating said LUP for each link associated with each of said alternative minimum hop routes, said temporarily updating step performed by increasing said LUP proportionally to a number of times said associated link is part of one of said alternative minimum hop routes;

(c) calculating a network routing entropy (NRE) for each of said alternative minimum hop routes using said LUPs associated with each link of said alternative minimum hop routes;

(d) selecting a first choice minimum hop route from said alternative minimum hop routes, said first choice minimum hop route having a largest of said NREs; and

(e) routing said data packet from said source node to said destination node over said first choice minimum hop route.

2. A method as claimed in claim 1 further comprising the step of updating said LUP for each link associated with said first choice minimum hop route by increasing said LUP proportionally to said number of times each link of said first choice minimum hop route is part of said first choice minimum hop route.

3. A method as claimed in claim 1 further comprising the step of determining, for each of said alternative minimum hop routes, a link having a maximum value of said LUPs, and wherein the selecting step includes the step of choosing said first choice minimum hop route having said link with a lowest of said maximum value of said LUPs.

4. A method as claimed in claim 1 wherein the determining step further comprises the step of determining which links are not available for transfer of said data packet during said predetermined time periods, said links being shut off as said nodes change said orbital position.

5. A method as claimed in claim 1 wherein said alternative minimum hop routes includes a transit node in said sequence of links, said transit node being one node on said first choice minimum hop route, and wherein each node of said plurality of nodes has a plurality of links associated therewith, and wherein the selecting further comprises the step of selecting first choice minimum hop routes for each source - destination pair of nodes of said plurality of nodes, and said method further comprises the step of:

calculating, for said transit node, a percentage each link associated with said transit node is identified by said first choice minimum hop routes that use said transit node for routing to said destination node, and wherein

the routing step comprises the step of routing said data packet away from said transit node to said destination node over one of said plurality of links associated with said transit node based on said percentage.

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

generating a table for said transit node including said percentage for each link of said plurality of links associated with said transit node; and

sending said table to said transit node.

7. A method as claimed in claim 6 wherein the generating step further comprises the step of generating said table for each node of said plurality of nodes.

8. A method as claimed in claim 1 further comprising the step of storing said first choice minimum hop route for said destination node in each node of said plurality of nodes.

9. A method as claimed in claim 1 further comprising the step of determining available links that will be usable during a predetermined time period, and said finding step further comprises the step of considering only said available links for finding said alternative minimum hop routes.

10. A method as claimed in claim 9 wherein said nodes are orbiting satellite communication stations and wherein the determining step further comprises the step of determining available links during predetermined time periods, said predetermined time periods based on different constellation configurations for said plurality of nodes, said constellation configurations including orbital position of each of said nodes during each of said predetermined time periods including links planned to be turned off during each of said predetermined time periods.

11. A method as claimed in claim 10 wherein the determining step further comprises the step of determining failed links and links not available for transfer of said data packet for each of said predetermined time periods.

12. A method as claimed in claim 11 further comprising the steps of repeating the determining, the finding, the temporarily updating, the calculating and the selecting steps for each of said predetermined time periods, and generating a list of first choice minimum hop routes for each of said constellation configurations.

13. A method as claimed in claim 1 wherein the finding step comprises the step of finding additional alternative minimum hop routes when the finding step finds only one of said alternative minimum hop routes, said alternative minimum hop routes including routes having less than a predetermined number of hops, said predetermined number being greater than a number of hops of said one of said alternative minimum hop routes.

14. A method as claimed in claim 2 further comprising the step of repeating the finding, the temporarily updating, the calculating, the selecting and the updating steps for all source - destination node combinations of said plurality of nodes.

15. In a communication system comprised of a plurality of nodes that move with respect to each other and communicate with each other over links, a method of routing data packets among said plurality of nodes comprising the steps of:

determining available links during each of a plurality of predetermined time periods, each time period based on different constellation configurations for said nodes, said constellation configurations including orbital position of each of said nodes during each of said predetermined time periods;

finding, for each of said constellation configurations, minimum hop routes between source and destination node pairs, each of said minimum hop routes comprising a sequence of said available links over which to send a data packet between a source node and a destination node;

calculating a link usage probability (LUP) for each of said links of said sequences, said LUP based on a number of times a link is used in each of said sequences;

calculating a network routing entropy for each of said minimum hop routes based on said LUP of each link of said minimum hop routes;

selecting, for each of said source and destination node pairs, one of said minimum hop routes for each of said constellation configurations, said one minimum hop route resulting in a largest network routing entropy (NRE); and

routing, during said predetermined time periods associated with said constellation configurations, said data packet between said source node and said destination node over said one minimum hop route.

16. A method as claimed in claim 15 wherein:

the finding step comprises the step of finding alternative minimum hop routes when the finding step finds only one minimum hop route, said alternative minimum hop routes including routes having less than a predetermined number of hops, said predetermined number based on an acceptable delay for a type of said data packet, and

the selecting step further comprises the step of selecting second and third choice minimum hop routes from said minimum hop routes and said alternative minimum hop routes, said second and third choice minimum hop routes resulting in a next largest NRE.

17. A communication system that routes data packets over minimum hop routes resulting in a distributed usage of communication links, said minimum hop routes comprising a list of said communication links to send a data packet between a source node and a destination node, said system comprising:

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

multi-channel transceivers associated with each node of said plurality of nodes for sending data packets over said communication links using said minimum hop routes; and

a control facility coupled to said nodes for determining which of said communication links will be available during predetermined time periods, finding said minimum hop routes between said nodes, calculating link usage probabilities (LUPs) for each communication link of said minimum hop routes, calculating a network routing entropy (NRE) based on said LUPs, and selecting a first choice minimum hop route from said minimum hop routes for said source node and said destination node based on said NRE.

18. A communication system as claimed in claim 17 wherein said first choice minimum hop routes include a transit node in said sequence of links, said transit node being one node on said first choice minimum hop route, and wherein said control facility further comprises:

means for calculating a percentage each communication link of said plurality associated with said transit node that is identified by said first choice minimum hop route that uses said transit node; and

means for instructing said transceiver coupled to said transit node to send said data packet from said transit node over one of said communication links associated with said transit node based on said percent.

19. A communication system as claimed in claim 17 further comprising a storage medium on each node coupled to said processors, said storage medium stores a table including said first choice minimum hop route, said table being sent from said control facility to each node of said plurality of nodes over an uplink.

20. A communication system as claimed in claim 17 wherein said control facility includes means for finding alternative hop routes when only one minimum hop route is found, said alternative hop routes including routes having hop a length less than an acceptable threshold for a type of said data packet, said acceptable threshold based on a delay associated with said alternative hop route.