Method for load-balancing with FIFO guarantees in multipath networks

  • US 7,002,958 B1
  • Filed: 09/10/1999
  • Issued: 02/21/2006
  • Est. Priority Date: 09/10/1999
  • Status: Expired due to Fees
First Claim
Patent Images

1. A method for routing packets in a multipath network of nodes, each packet having a routing in the network determined by a directed-graph index, comprising;

  • accessing a tag and a directed-graph index from the packet at a first node;

    producing a normalized tag from the accessed tag by applying a normalizing function to the tag, the normalizing function used substantially throughout the network;

    determining a second node of a successor set of nodes by using the normalized tag and directed-graph index to access a routing bias table;

    replacing the tag of the packet with a randomized tag to give an updated packet; and

    routing the updated packet from the first node to the second node;

    wherein the directed-graph index determines at least one destination node, and the routing bias table is selected from a plurality of routing bias tables indexed by the first node and the directed-graph index, and the routing bias tables satisfy an acyclic property, and the normalizing function enhances network performance by reducing the number of bits involved in accessing the routing table bias table, and the randomized tag arbitrarily varies paths in the network in order to fully utilize the network resources.

View all claims
  • 4 Assignments
Timeline View
Assignment View