 |
|
|
|
|
|
 Title: |
US5596722:
Packet routing system and method for achieving uniform link usage and minimizing link load
[ 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: |
1997-01-21
/ 1995-04-03
|
| Application Number: |
US1995000415948
|
| IPC Code: |
Advanced:
H04B 7/185;
H04J 3/24;
Core:
more...
IPC-7:
H04J 3/24;
|
| ECLA Code: |
H04B7/185S4; H04J3/24D;
|
| U.S. Class: |
Current:
709/241;
370/400;
709/242;
Original:
395/200.15;
370/400;
|
| Field of Search: |
395/200.15,200.14,200.13,200.12,200.11,200.1-9
370/94.1-94.3,16-17,54,60-60.1
|
| Priority Number: |
| 1995-04-03 |
US1995000415948 |
|
| 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.
|
| Attorney, Agent or Firm: |
Gorrie, Gregory J. ;
|
| Primary / Asst. Examiners: |
Shin, Christopher B.;
|
| INPADOC Legal Status: |
Show legal status actions
|
| Parent Case: |
CROSS-REFERENCE TO RELATED APPLICATIONS
This application is related to co-pending U.S. patent application Ser. No. 08/222,067, filed on Apr. 04, 1994, entitled "METHOD AND APPARATUS FOR ADAPTIVE DIRECTED ROUTE RANDOMIZATION AND DISTRIBUTION IN A RICHLY CONNECTED COMMUNICATION NETWORK" which is assigned to the same assignee as the present application.
|
| Family: |
None
|
First Claim:
Show all 14 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 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.
|
| Background / Summary: |
Show background / summary
|
| Drawing Descriptions: |
Show drawing descriptions
|
| Description: |
Show description
|
| Forward References: |
Show 42 U.S. patent(s) that reference this one
|
