Method for load-balancing with FIFO guarantees in multipath networks
DCFirst 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.
4 Assignments
Litigations
0 Petitions
Accused Products
Abstract
A method for routing packets in a multipath network of nodes balances the loading of system resources while guaranteeing a FIFO network (i.e., First In First Out). Acyclic directed graphs based on local network information are used at each node with routing bias tables that allow for local preferences. A randomizing function may be used throughout the network to allow uniform utilization of system resources. A normalizing function may be used throughout the network to reduce bit operations in routing packets.
-
Citations
23 Claims
-
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 Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A method for routing flows in a multipath network of nodes, each flow including a sequence of packets, each flow having a flow entry node and a flow directed-graph index, and each packet including a tag having a plurality of bits included in the packet, comprising:
-
marking packets belonging to a flow with a flow entry tag before entry into the network at a flow entry node; and changing tags of packets in the network by accessing the tag and a directed-graph index from the packet at a first node, producing a normalized tag from the accessed tag and replacing the tag of the packet with a randomized tag to give an updated packet, so that the packets of a flow receive an identical tag when being routed to an identical node; wherein, producing a normalized tag from the tag is accomplished by applying a normalizing function to the tag, and determining a second node of a successor set of nodes is accomplished by using the normalized tag and a directed-graph index to access the first routing bias table, and the normalizing function enhances network performance by limiting bit operations 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 Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23)
-
Specification