 |
|
|
|
|
|
 Title: |
US5430729:
Method and apparatus for adaptive directed route randomization and distribution in a richly connected communication network
[ Derwent Title ]
|
| Country: |
US United States of America
|
| |
| Inventor: |
Rahnema, Moe; Chandler, AZ
|
| Assignee: |
Motorola, Inc., Schaumburg, IL
other patents from MOTOROLA, INC. (386735) (approx. 18,357)
News, Profiles, Stocks and More about this company
|
| Published / Filed: |
1995-07-04
/ 1994-04-04
|
| Application Number: |
US1994000222067
|
| IPC Code: |
Advanced:
H04B 7/185;
H04L 12/56;
H04Q 11/04;
H04W 40/24;
H04W 40/34;
Core:
H04W 40/00;
more...
IPC-7:
H04J 3/24;
|
| ECLA Code: |
H04B7/185M10B; H04L12/56C; H04Q11/04S2; T04L12/56A4B4; T04L12/56A10; T04L12/56W4; T04L12/56W6; T04L12/56W19B; T04W40/24U; T04W40/34;
|
| U.S. Class: |
Current:
370/409;
709/242;
Original:
270/094.1;
370/060;
395/200;
|
| Field of Search: |
370/941,942,60,54,943,60.1,16,17
395/200
364/284,284.3,284.4,242.94,229,229.3,229.4,229.5,514
|
| Priority Number: |
| 1994-04-04 |
US1994000222067 |
|
| 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.
|
| Attorney, Agent or Firm: |
Gorrie, Gregory J. ;
|
| Primary / Asst. Examiners: |
Olms, Douglas W.; Patel, Ajit
|
| INPADOC Legal Status: |
Show legal status actions
Family Legal Status Report
|
| Family: |
Show 15 known family members
|
First Claim:
Show all 20 claims |
What is claimed is:
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.
|
| Background / Summary: |
Show background / summary
|
| Drawing Descriptions: |
Show drawing descriptions
|
| Description: |
Show description
|
| Forward References: |
Show 118 U.S. patent(s) that reference this one
|
