Distributed in-order load spreading resilient to topology changes
First Claim
1. A method implemented by a load splitter configured to receive incoming packets and distribute the packets to a plurality of servers coupled to the load splitter, the method comprising:
- detecting that n servers are available to receive packets, wherein n is at least 3;
employing an n-way distribution function to distribute packets to the n servers, wherein the n-way distribution function is configured such that packets belonging to the same flow are distributed to the same server;
detecting that a first of the n servers is unavailable to receive packets, leaving n−
1 available servers;
while there are n−
1 available servers,in response to receiving a first packet,classifying the first packet to associate the first packet with a flow; and
performing the n-way distribution function on the packet;
if the result of the n-way distribution function directs the first packet to be distributed to an available server, forwarding the first packet to the available server;
if the result of the n-way distribution function directs the first packet to be distributed to the first unavailable server,employing an (n−
1)-way distribution function to determine an available server to redistribute the first packet to and forwarding the first packet to that server;
storing indicia indicating that packets associated with the flow for the first packet belong to a redistributed flow; and
when the number of available servers returns to n servers,forwarding subsequently received packets associated with the redistributed flow to the same server the first packet was redistributed to.
1 Assignment
0 Petitions
Accused Products
Abstract
Methods, apparatus, and systems for distributing network loads in a manner that is resilient to system topology changes. Distribution functions and associated operations are implemented on multiple load splitters such that if a load splitter becomes inoperative, another or other load splitters can forward packets corresponding to flows previously handled by the inoperative load splitter without requiring flow state synchronization to be maintained across load splitters. The distribution functions are implemented in a manner that distributes packets for the same flows to the same servers through system topology changes, addressing both situations when servers fail and/or are taken off-line and when such servers or replacement servers are brought back on-line. The techniques are facilitated, in part, via use of redistributed flow lists and/or Bloom filters that are marked to track redistributed flows. A novel Bloom filter recycle scheme is also disclosed.
-
Citations
30 Claims
-
1. A method implemented by a load splitter configured to receive incoming packets and distribute the packets to a plurality of servers coupled to the load splitter, the method comprising:
-
detecting that n servers are available to receive packets, wherein n is at least 3; employing an n-way distribution function to distribute packets to the n servers, wherein the n-way distribution function is configured such that packets belonging to the same flow are distributed to the same server; detecting that a first of the n servers is unavailable to receive packets, leaving n−
1 available servers;while there are n−
1 available servers,in response to receiving a first packet, classifying the first packet to associate the first packet with a flow; and performing the n-way distribution function on the packet; if the result of the n-way distribution function directs the first packet to be distributed to an available server, forwarding the first packet to the available server; if the result of the n-way distribution function directs the first packet to be distributed to the first unavailable server, employing an (n−
1)-way distribution function to determine an available server to redistribute the first packet to and forwarding the first packet to that server;storing indicia indicating that packets associated with the flow for the first packet belong to a redistributed flow; and when the number of available servers returns to n servers, forwarding subsequently received packets associated with the redistributed flow to the same server the first packet was redistributed to. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. An apparatus, comprising:
-
a plurality of upstream network ports; at least one downstream network port; wherein the apparatus is configured to be installed in a system and to be implemented as a load splitter that distributes packets received at the at least one downstream port to a number of servers communicatively coupled to the plurality of upstream ports, wherein an initial number of servers is n, the apparatus further configured, when installed in the system and operating, to perform operations including, in response to receiving a packet, initializing an integer i=n; identifying a flow the packet is to be associated with; (a) performing an i-way distribution function to identify a server to distribute or redistribute the packet to; (b) if the result of the i-way distribution function identifies an available server, determining whether the packet is associated with a redistributed flow for the available server; and i if the packet is associated with a redistributed flow for the available server decrementing i by 1 and returning to (a);
otherwise,ii forwarding the packet to the available server; (c) if the result of the i-way distribution function identifies an unavailable server, storing indicia indicating that packets belonging to the flow the packet is associated with belong to a redistributed flow, decrementing i by 1, and returning to (a); and (d) repeating operations (a), (b), (b)i and (c), as applicable, until the i-way distribution function identifies an available server in operation (b) that does not have a redistributed flow for which the packet is associated, resulting in the packet being forwarded to the available server in (b)ii. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20, 21, 22)
-
-
23. A tangible non-transient machine-readable medium having instructions stored thereon configure to be executed by at least one processing element on a load splitter to enable the load splitter to effect packet distribution and redistribution operations when the load splitter is installed in a system and operating, the packet distribution and redistribution operations comprising:
in response to receiving a packet, initializing an integer i=n; identifying a flow the packet is to be associated with; (a) performing an i-way distribution function to identify a server to distribute or redistribute the packet to; (b) if the result of the i-way distribution function identifies an available server, determining whether the packet is associated with a redistributed flow for the available server; and i. if the packet is associated with a redistributed flow for the available server decrementing i by 1 and returning to (a);
otherwise,ii. forwarding the packet to the available server; (c) if the result of the i-way distribution function identifies an unavailable server, storing indicia indicating that packets belonging to the flow the packet is associated with belong to a redistributed flow, decrementing i by 1, and returning to (a); and (d) repeating operations (a), (b), (b)i and (c), as applicable, until the i-way distribution function identifies an available server in operation (b) that does not have a redistributed flow for which the packet is associated, resulting in the packet being forwarded to the available server in (b)ii. - View Dependent Claims (24, 25, 26, 27, 28, 29, 30)
Specification