US 5,430,729 A · Method and apparatus for adaptive directed route randomization and distribution in a richly connected communication network

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.

Claims20

Dependent claims

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.

3 more elements

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.

4 more elements

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.

1 more element

Dependencies are inferred from the claim text.

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

Life of this patent

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

Life of this patent

Abstract

Claims20