×

Packet routing system and method for achieving uniform link usage and minimizing link load

  • US 5,596,722 A
  • Filed: 04/03/1995
  • Issued: 01/21/1997
  • Est. Priority Date: 04/03/1995
  • Status: Expired due to Term
First Claim
Patent Images

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 all claims
  • 3 Assignments
Timeline View
Assignment View
    ×
    ×