Packet routing system and method for achieving uniform link usage and minimizing link load
First Claim
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 capacity associated therewith, a method of routing data packets among said plurality of nodes comprising the steps of:
- (a) finding routes between a source node and a destination node, each of said routes comprising a sequence of links over which to send a data packet;
(b) calculating a link usage probability (LUP) for each link associated with each of said routes, said LUP being proportional to a number of times an associated link is included on one of said routes and inversely proportional to said link capacity of said associated link;
(c) calculating a normalized network routing entropy (NRE) for each of said routes using said LUPs associated with each link of said routes, said normalized NRE being normalized by an aggregate traffic load on all of said links;
(d) selecting a final route from said routes, said final route having a largest of said normalized NREs; and
(e) routing said data packet from said source node to said destination node over said final route.
3 Assignments
0 Petitions
Accused Products
Abstract
Data packets are routed among nodes of a communication system in a uniform fashion. Substantial uniform link usage is achieved within allowed routes determined by end to end transport delay criteria. Initial routes are selected for each source--destination pair from alternative minimal hop routes. Link usage probabilities are calculated for the links involved in each route and system network routing entropy is calculated from the link usage probabilities. Final routes are chosen to maximize the network routing entropy resulting in uniform usage of the system'"'"'s communication links in proportion to link capacity. The aggregate link load is also minimized. Individual routing tables are generated for each communication node based on the selected routes. The routing tables reflect changes in the traffic demand, changes in link capacity and changes in node connectivity within the constellation which occur as a result of satellite motion.
202 Citations
14 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 capacity associated therewith, a method of routing data packets among said plurality of nodes comprising the steps of:
-
(a) finding routes between a source node and a destination node, each of said routes comprising a sequence of links over which to send a data packet; (b) calculating a link usage probability (LUP) for each link associated with each of said routes, said LUP being proportional to a number of times an associated link is included on one of said routes and inversely proportional to said link capacity of said associated link; (c) calculating a normalized network routing entropy (NRE) for each of said routes using said LUPs associated with each link of said routes, said normalized NRE being normalized by an aggregate traffic load on all of said links; (d) selecting a final route from said routes, said final route having a largest of said normalized NREs; and (e) routing said data packet from said source node to said destination node over said final route. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. In a communication system comprised of a plurality of nodes that communicate over links, a method of routing data packets among said nodes comprising the steps of:
-
(a) determining available links during each of a plurality of predetermined time periods, each predetermined time period having an associated traffic forecast; (b) finding, for each of said predetermined time periods, routes between source and destination node pairs, each of said routes comprising a sequence of said available links over which to send a data packet; (c) 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; (d) calculating a normalized network routing entropy (NRE) for each of said routes based on said LUP of each link of said routes; (e) selecting, for each of said source and destination node pairs, one of said routes for each of said predetermined time periods, said one route resulting in a largest normalized NRE; and (f) routing, during said predetermined time periods, said data packet between a source node and a destination node of one of said source and destination node pairs over the route selected in step (e). - View Dependent Claims (12, 13)
-
-
14. A communication system that routes data packets over routes resulting in a substantially uniform usage of communication links, said 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 coupled by said communication links, each of said communication links having a link capacity; multi-channel transceivers associated with each node for sending and receiving data packets over said communication links using said routes; and a control facility coupled to said nodes for providing routing tables to each of said nodes, wherein said routing tables are generated by a computer that;
finds routes between said source node and said destination node;calculates a link usage probability (LUP) for each communication link associated with each of said routes, wherein said LUP is proportional to a number of times an associated communication link is included on one of said routes and inversely proportional to said link capacity of said associated communication link; calculates a normalized network routing entropy (NRE) for each of said routes using said LUPs associated with each communication link of said routes, said normalized NRE being normalized by an aggregate traffic load on all of said communication links; selects a final route from said routes, said final route having a largest of said normalized NREs; and includes said final route in said routing tables.
-
Specification