Method for load-balancing with FIFO guarantees in multipath networks
AssigneePluris, Inc.
InventorsErok Basturk, Vadim Antonov
Life of this patent
Estimating the term…
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.
Claims23
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.
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.
Dependencies are inferred from the claim text.