METHODS OF FORWARDING/RECEIVING DATA PACKETS USING UNICAST AND/OR MULTICAST COMMUNICATIONS AND RELATED LOAD BALANCERS AND SERVERS

Data packets may be forwarded to servers identified by respective server IDs. A mapping table includes bucket IDs identifying respective buckets. The mapping table maps: a first bucket ID to a first server ID as a current server ID; a second bucket ID to a second server IDs as a current server ID; and the first bucket ID to a third server ID as an old server ID. A data packet of a data flow may be received, and a bucket ID may be computed for the data packet. Responsive to computing the first bucket ID as the bucket ID for the data flow and responsive to the mapping table mapping the first bucket ID to the to the first server ID as the current server ID and to the third server ID as the old server ID, the data packet may be transmitted to the first server and/or to the third server.

DETAILED DESCRIPTION

Embodiments of present inventive concepts will now be described more fully hereinafter with reference to the accompanying drawings, in which examples of embodiments of inventive concepts are shown. Inventive concepts may, however, be embodied in many different forms and should not be construed as limited to the embodiments set forth herein. It should also be noted that these embodiments are not mutually exclusive. Components from one embodiment may be tacitly assumed to be present/used in one or more other embodiments. According to embodiments disclosed herein, a blade may be interpreted/implemented as a server and/or a server may be interpreted/implemented as a blade.

As shown inFIG. 6, processing systems according to some embodiments of inventive concepts disclosed herein may include a plurality of servers S1 to Sn and one or more load balancers LB coupled with a plurality of clients C1 to Cm and/or one or more outside servers OS through a network N (such as a local area network, a wide area network, the Internet, etc.). As shown inFIG. 7, each server S may include a processor701, memory707, and a load balancer interface703providing a communications interface with load balancer LB. Load balancer interface703may thus support transmission/reception of communications (including data packets and flows of data packets) between processor701and load balancer LB. As shown inFIG. 8, load balancer LB may include a processor801, memory807, server interface803, and network interface805. Server interface803may thus support transmission/reception of communications (including data packets and flows of data packets) to/from servers51to Sn, and network interface805may support transmission/reception of communications (including data packets and flows of data packets) to outside clients and/or servers over the network. As discussed in greater detail below, load balancer processor801may map different data flows/packets to different servers, and/or server processor701may accept/reject data flows/packets received from load balancer LB. While one load balancer LB is shown inFIG. 6, a plurality of load balancers may be provided for purposes of redundancy/resiliency.

According to some embodiments, hitless dynamic behavior (e.g., hitless addition and/or removal of blades/servers, hitless changes in the load distribution, etc.) and/or reduced hit dynamic behavior in hash based load balancing architectures may be provided while maintaining flow stickiness. In some embodiments, load balancing approaches may include: (1) Multicast/Broadcast Based Distributed Approaches; (2) Transient Table Based Approaches; and/or (3) HTTP Redirect based Approaches.

In multicast/broadcast based distributed approaches, packets in each bucket may be multicast to both original and new target blades for that bucket while Bucket to Blade (B2B) mapping changes dynamically. These approaches may maintain flow stickiness and hitless (or reduced hit) support for addition/removal/remapping of blades for both type 1 and type 2 flows. Load balancing operations may run in a distributed fashion (i.e., partially on the load balancer and partially on the blades themselves). Related load balancing operations are discussed, for example, in U.S. patent application Ser. No. 13/464,608 entitled “Two Level Packet Distribution With Stateless First Level Packet Distribution To A Group Of Servers And Stateful Second Level Packet Distribution To A Server Within The Group” filed May 4, 2012, the disclosure of which is hereby incorporated herein in its entirety by reference.

In transient tables based approaches, load balancing operations may be handled on the load balancer without burdening blades with additional operations to support load balancing. Moreover, load balancer LB provides unicast transmissions of packets thereby saving bandwidth. More particularly, transient tables are temporarily maintained in memory807at load balancer LB while changing bucket to blade mappings. Transient tables based approaches, however, may only support type 1 flows.

HTTP redirect based approaches are based on a concept of HTTP (Hypertext Transfer Protocol) redirect within an application layer. Each blade uses HTTP redirect to point the incoming flows to their new destination blade when the Bucket-to-Blade (B2B) mapping is modified. In this mechanism, there is no multicast of packets and/or there are no additional tables to be maintained. HTTP redirect based approaches may support both type-1 and type-2 flows, but may work only for HTTP traffic.

Multicast/broadcast based distributed approaches, transient table based approaches, and HTTP redirect based approaches are discussed in greater detail below.

Modifying a Bucket-to-Blade (B2B) Mapping Table

According to some embodiments, a bucket to blade (B2B) mapping table is maintained in memory807of load balancer LB, and the B2B mapping table includes a first column for bucket IDs, a second column for blade IDs (also referred to as current blade IDS), and a third column for old blade IDs. When a server/blade is added to, removed from, or reassigned within the plurality of servers/blades ofFIG. 6, the B2B (Bucket-to-Blade) mapping table in load balancer memory807is modified. When a Blade ID (blade identification) corresponding to a certain bucket changes from Blade A to Blade B, for example, the original Blade ID (i.e., Blade A) is recorded in an additional column referred to as an Old Blade ID column, and this entry (the old blade ID) may be erased by control plane operations when it is no longer needed. In addition, the new blade ID (now the current blade ID or just blade ID) is recorded in the Current Blade ID column (or just the Blade ID column).

Addition of a Blade

Modification of a B2B mapping table responsive to adding a blade is illustrated inFIGS. 9A and 9B. Initially Buckets 1 through B are mapped to Blades 1, 2, and 3 using the mapping table ofFIG. 9Asaved in load balancer memory807. When blade 4 is added to the plurality of blades ofFIG. 6, Buckets 2 and 3 are remapped to Blade 4 as shown in the blade ID column (or current blade ID column) ofFIG. 9B. The new Blade ID (i.e., Blade 4) is thus identified in the Blade ID column (also referred to as the current blade ID column) while the original (or old) Blade IDs (i.e., Blade ID 1 for Bucket ID 2 and Blade ID 2 for Blade ID 3 respectively) are preserved in the Old Blade ID column as shown inFIG. 9B.

By adding a new Blade (e.g., Blade 4) to the plurality of blades, additional capacity may be added to the system, and buckets originally mapped to previously existing blades may be remapped to the new blade to provide load balancing. Accordingly, data traffic to previously existing blades may be reduced while providing traffic for the newly added blade. In addition, the old blade ID column may be used according to some embodiments to support data flows from buckets 2 and 3 that began before and continue after the remapping.

A bucket is defined to be in steady-state when the Old Blade ID field corresponding to that bucket is empty. InFIG. 9A, for example, buckets 1, 2, 3, 4, and B are in steady state because no old blade ID is recorded for any of the buckets. InFIG. 9B, buckets 1, 4, and B are in steady state for the same reason.

A bucket is defined to be in a transient state if the Old Blade ID field corresponding to that bucket identifies an old blade ID (e.g., the old blade ID field is non-empty). Buckets 2 and 3 ofFIG. 9Bare considered to be in the transient state because old blade IDs 1 and 2 are respectively identified for buckets 2 and 3. Once a bucket has entered the transient state, the bucket may reenter the steady state when the old blade ID entry is erased, for example, by control plane operations.

Removal of a Blade

Modification of a B2B mapping table responsive to removing a blade is illustrated inFIGS. 10A and 10B. Initially, Buckets 1 through B are mapped to Blades 1, 2 and 3 with all buckets in the steady state as shown inFIG. 10A. Blade 3 is then removed, for example, for scheduled maintenance. Bucket 1 (which was originally mapped to and served by Blade 3) is now assigned/mapped to Blade 2 as shown inFIG. 10B, and this change is reflected in the Blade ID (or current blade ID) and old blade ID columns ofFIG. 10B. In particular, the original Blade ID (i.e., Blade 3) is now recorded in the Old Blade ID column for Bucket 1, and the new blade ID (i.e., Blade 2) is now recorded in the blade ID (or current blade ID) column for Bucket 1. Once the mapping table is modified as shown inFIG. 10B, Bucket 1 is considered to be in the transient state while buckets 2, 3 and 4 are considered to be in steady state.

By removing a Blade (e.g., Blade 3) from the plurality of blades, capacity may be reduced, and buckets originally mapped to the blade that is removed may be remapped to a remaining blade to provide load balancing. Accordingly, data traffic to previously existing blades may be increased. In addition, the old blade ID column may be used according to some embodiments to support data flows from Bucket 1 that began before and continue after the remapping.

Reallocation of Buckets to Blades

Modification of a B2B mapping table responsive to rescheduling data flows is illustrated inFIGS. 11A and 11B. An initial mapping between Buckets 1 through B and Blades 1, 2 and 3 is shown inFIG. 11A. This mapping may be modified, for example, to provide load balancing even though no blades have been added or removed. For example, a load of Blade 1 may increase so that some of its traffic should be offloaded to Blade 3 by reassigning Bucket 4 to Blade 3. The original serving blade (i.e., Blade 1) is recorded in the Old Blade ID column for bucket 4 while Blade 3 takes its place in the (current) Blade ID column for bucket 4. InFIG. 11B, Bucket 4 is considered to be in transient state while buckets 1, 2 and 3 are considered to be in steady state.

A Multicast/Broadcast Based Distributed Approach may enable hitless (or reduced hit) addition, removal, and/or reallocation of blades while maintaining flow stickiness. In this approach, packets that belong to buckets in steady-state may be unicast from load balancer LB to respective blades (as identified by the current blade IDs for the respective steady state bucket IDs), packets that belong to buckets in transient state may be multicast/broadcast (to both current and old blades) for the buckets in transient state. In this case, additional operations may be performed on each blade to determine whether each received packet is to be processed or dropped. This sharing of operations between load balancer and servers is referred to as a distributed approach, and this approach may work for both type-1 and type-2 flows.

While discussion of transient multicast/broadcast operations is provided for a multicast group of 2 for the sake of conciseness, embodiments of inventive concepts may be implemented with larger multicast groups. Transient Multicast/Broadcast based distributed approaches, for example, may be generalized to larger multicast groups discussed below in the section entitled “Extended Operations For Multiple Cascaded Transients”. Similarly, operations disclosed herein are not limited to multicast. These operations may be generalized using, for example, VLAN based broadcast, as briefly discussed below in the section entitled “VLAN Based Broadcast Implementation Alternative”.

For Type-1 Flows

As discussed above, type-1 data flows are those data flows for which it is possible to detect the start of the data flow or the first data packet of the data flow by considering only bits in the first data packet of the data flow (i.e., without consulting any other data/information). In this section, a multicast based distributed approach is presented for type-1 flows, with type-1 flows being the ones that are most commonly encountered. This approach may be broken into two parts: data plane operations; and control plane operations.

Data plane operations may primarily be used to handle how incoming data packets are forwarded to and received by the blades assuming an instance of a B2B Mapping Table at any given point in time. Data plane operations may include operations running on both the load balancer and the blades. Control plane operations may primarily be used to handle maintenance and modification of the load balancer table.

Data Plane Operations for Type-1 Flows

In this approach, a two-stage ‘distributed’ mechanism may be followed. The first stage includes the screening of packets at the load balancer LB to make an appropriate forwarding decision. The second stage includes the screening of received packets at the blade.

Operations at the load balancer are discussed as follows. A B2B mapping table is maintained in memory807at load balancer LB. For every incoming data packet, load balancer processor801obtains the Bucket ID using the hash function. The bucket ID may be computed as a hash of element(s) of the packet header (e.g., a hash of the Flow ID including in the packet header). If the bucket is in steady state, the packet is unicast to the blade (identified in the current blade ID column of the B2B mapping table) corresponding to the bucket. If the bucket is in transient state (with both current and old blades identified for the bucket) and the data packet is an initial data packet of the data flow (as indicated by an INIT identifier), the packet is unicast to the current blade ID for the transient state bucket. If the bucket is in transient state and the data packet is not an initial data packet of the data flow, the packet may be multicast to both the current blade and the old blade as indicated in the blade ID and old blade ID columns of the B2B mapping table.

FIG. 12Ais a flow chart illustrating load balancer processor807operations for type-1 data flows using transient multicast/broadcast based distributed approaches according to some embodiments.FIG. 12Bis a B2B mapping table provided for the purpose of discussion withFIG. 12A. At block1200, processor801defines/revises B2B mapping table ofFIG. 12Bin memory807. As discussed above, a bucket is in the steady state if the corresponding Old Blade ID field is empty for that bucket. In the example ofFIG. 12B, Buckets 2 and G are in steady-state while Bucket 1 is in transient state. Accordingly, any packet that belongs to Bucket 2 will be unicast only to Blade 3. This includes both initial (INIT) and subsequent (non-INIT) data packets of data flows. Any INIT packet that belongs to Bucket 1 will be unicast by load balancer LB only to Blade 4, and a non-INIT data packet that belongs to Bucket 1 will be multicast to both blades 4 and 7.

By way of example, a first data packet may be received at block1201from the network through network interface805, and processor807may perform the hash function on a flow ID from a header of the first data packet at block1203to obtain a bucket ID corresponding to the flow ID. If the hash function outputs bucket ID 2, processor807consults the B2B mapping table (e.g., as shown inFIG. 12B) to determine the state (steady state or transient state) of Bucket 2 at block1205. As shown inFIG. 12B, Bucket 2 is steady state because there is no old blade identified in its old blade field. Accordingly, the first data packet is unicast only to blade 3 (the blade identified for Bucket 2 in the B2B mapping table ofFIG. 12B) at block1211through server interface803.

A second data packet may be received at block1201from the network through network interface805, and processor807may perform the hash function on a flow ID from a header of the second data packet at block1203to obtain a bucket ID corresponding to the flow ID. If the hash function outputs bucket ID 1, processor807consults the B2B mapping table (e.g., as shown inFIG. 12B) to determine the state (steady state or transient state) of the bucket at block1205. As shown inFIG. 12B, Bucket 1 is in the transient state because bucket 7 is identified as an old blade in its old blade field. Provided that the second data packet is not an initial data packet of a data flow at block1207, the data packet is multicast to both the current blade (blade 1) and the old blade (blade 7) at block1209through server interface803. If the second data packet is an initial data packet of a data flow at block1207, the data packet is unicast to only the current blade (blade 1) at block1211through server interface803. By transmitting all initial data packets for new data flows to only the current blade of a bucket in the transient state, the current blade is effectively signaled to establish all new data flows for the bucket in the transient state. By multicasting all non-initial data packets to both the current and old blades for the bucket in the transient state, the current blade can service all new data flows initiated after the bucket entered the transient state, and the old blade can continue servicing all data flows that were initiated before the bucket entered the transient state. According to some embodiments, initial data packets for a transient state bucket (as determined at block1207) may thus be unicast only to the current blade at block1211, and non-initial data packets for a transient state bucket (as determined at block1207) may be multicast to both current and old blades at block1209.

In embodiments ofFIG. 12A, some additional screening may occur at the blades to determine which blade should process packets that were multicast. For example, each blade may maintain a list of flow IDs for data flows being processed by that blade, and this list may be referred to as a ‘my-flows-table’. While a more detailed architecture of the my-flows-table may be useful for discussion of control plane operations, for purposes of data plane operations, a ‘my-flows-table’ including a list of flow IDs for data flows being processed by that blade may be sufficient. If the blade receives an initial data packet of a data flow (e.g., indicated by an INIT flag in header information) indicating that this data packet is a first data packet for a new data flow, processor701adds the flow ID to its my-flow table and processes the packet. As shown inFIG. 12A, all initial data packets for transient state buckets are identified at block1207and unicast to only the current blade for the transient state bucket at block1211allowing the current blade for the transient state bucket to identify all new data flows. Stated in other words, load balancer LB is able to inform each blade of the data flows to be processed by that blade by unicasting all INIT packets only to the blade that is to process that data flow for the INIT packet. By creating a ‘my-flows-table’ for a blade based on the INIT packets received at that blade, a blade can process only those non-INIT packets having data flow IDs matching a data flow ID of an INIT packet received by that blade. The old blade for the transient state bucket will thus not add any new flows to its ‘my-flows-table’ once the bucket enters the transient state. The old blade, however, will maintain its ‘my-flows-table’ identifying data flows initiated before the bucket entered the transient state, and the old blade can continue accepting/processing non-initial data packets of these data flows that were initiated before the bucket entered the transient state.

If a received non-INIT data packet is unicast from load balancer LB at block1211for a steady state bucket, the packet is being sent only to the blade that is to process the non-INIT data packet, and the receiving blade should thus process this packet because the receiving blade should have the data flow for this non-INIT data packet in its ‘my-flows-table’. As shown inFIG. 12A, a NON-INIT packet is unicast only for steady state buckets, while non-INIT packets for transient state buckets are always multicast to both the current and old blades at block1209. If a blade receives a non-INIT data packet that was multicast to multiple blades, the blade checks if the non-INIT data packet belongs to one of the flows listed in my-flows-table. If the non-INIT data packet does belong to a data flow identified in the my-flows-table, the blade processes the packet. If the non-INIT data packet does not belong do a data flow identified in the my-flows-table, the blade drops the packet.

FIG. 13Ais a flow chart illustrating blade/server operations for type-1 data flows using transient multicast/broadcast based distributed approaches corresponding to load balancer operations ofFIG. 12A, andFIG. 13Bis a ‘my-flows-table’ according to some embodiments. At block1300, processor701defines/revises the my-flows-table (generically referred to as a server flow table) ofFIG. 13Bin memory707. When a data packet is received through interface703at block1301, processor701determines if the data packet is an initial data packet of a new flow at block1303(e.g., by checking for an INIT flag in a header of the data packet). If the data packet is an initial data packet at block1303, processor701adds a data flow ID for the new data flow to the my-flows-table ofFIG. 13Bat block1305, and processor701processes the data packet at block1307. Processor701can thus take responsibility for every new data flow for which it receives the initial data packet (e.g., indicated by a INIT flag) because the load balancer unicasts each initial data packet of a data flow to only one blade (i.e., the current blade for the respective bucket) as discussed above with respect toFIG. 12A.

If the data packet is not an initial data packet (referred to as a non-initial data packet) at block1303(e.g., the non-initial data packet does not include an INIT flag), processor701determines if the non-initial data packet belongs to a data flow being handled by the blade. More particularly, processor701compares a data flow ID of the non-initial data packet (e.g., included in a header of the packet) with data flow IDs from the ‘my-flows-table’ ofFIG. 13B(identifying data flows being handled by the blade). If the non-initial data packet does belong to a data flow being handled by the blade at block1309, the blade processes the non-initial data packet at block1307. If the non-initial data packet does not belong to a data flow being handled by the blade at block1309, the blade drops the non-initial data packet at block1311.

Alternate Data Plane Operations for Type-1 Flows

In this section, another two-stage ‘distributed’ data plane algorithm is described. These alternate operations may provide a relatively simplified load balancer, such that the load balancer merely forwards the packets based on the buckets they are hashed to. In this approach, there is no assumption as to whether load balancer is capable of identifying start-of-the-flow (INIT) packets. Even though some operations of this approach may be common with respect to operations discussed above with respect toFIGS. 12A-Band13A-B, a detailed description is provided for clarity/completeness.

At the load balancer LB, a bucket to blade mapping table is maintained, and for every incoming packet, the Bucket ID is obtained using the hash function (e.g., by computing a hash of an element of the packet header such as the Flow ID). If the bucket is in steady state, the packet is unicast to the blade corresponding to the bucket (i.e., the current blade from the B2B table for the bucket). If the bucket is in transient state, the load balancer multicasts the packet to both the current Blade ID and the Old Blade ID identified in the B2B mapping table.

FIG. 14Ais a flow chart illustrating load balancer operations for data flows using transient multicast/broadcast based distributed approaches where knowledge of initial/non-initial data packet status is not used, andFIG. 14Bis a B2B mapping table according to some embodiments. InFIG. 14A, operations of blocks1200,1201,1203, and1205may be the same as discussed above with respect toFIG. 12A. If the hash function maps the flow ID of a received data packet to a bucket (e.g., Bucket 1) in transient state at block1205, LB processor801multicasts the data packet (through server interface803) to both of the current and old blades (e.g., blades 4 and 7) for the transient state bucket identified in the B2B mapping table ofFIG. 14Bat block1409. If the hash function maps the flow ID of a received data packet to a bucket (e.g., Bucket 2) in steady state at block1205, LB processor801unicasts the data packet (through server interface803) to the current blade (e.g., blade 3) for the steady state bucket identified in the B2B mapping table ofFIG. 14Bat block1411. InFIG. 14A, LB processor801does not consider an initial/non-initial status of the received data packets, effectively removing block1207ofFIG. 12A.

As shown inFIGS. 1409 and 1411, load balancer LB may transmit data packets with a unicast/multicast indicator to identify the transmission as a multicast or unicast transmission to the receiving blade or blades. According to some embodiments, the multicast/unicast indicator may be provided as the destination address of the data packet. If the data packet is transmitted as a multicast to both the current and old blades of Bucket 1 (in transient state) at block1409, for example, load balancer processor801may include a multicast destination address (with addresses/IDs of both blade 4 and blade 7) in the header of the data packet. If the data packet is transmitted as a unicast to only the current blade of Bucket 2 (in steady state) at block1411, for example, load balancer processor801may include a unicast destination address (with address/ID of only blade 3) in the header of the data packet. The receiving blade or blades can thus determine whether a received data packet was transmitted from the load balancer as a unicast or multicast transmission based on the destination address or addresses included in the data packet. According to some other embodiments, the load balancer LB may transmit each data packet with an indicator flag having a first value (e.g., one) for a multicast transmission and a second value (e.g., zero) for a unicast transmission.

The potentially reduced complexity of load balancer operations ofFIG. 14A(e.g., disregarding the initial/non-initial status of received data packets) relative toFIG. 12A, however, may require additional processing at the blades (relative toFIG. 13A) to decide whether a received packet is to be processed or dropped.

Each blade may maintain both a list of flow IDs for data flows being processed by that blade (also referred to as a server flow table) as well as list of buckets that the blade is serving (also referred to as a buckets table), and both lists may be provided in a table referred to as a ‘my-flows-and-buckets-table’. A more detailed architecture of this table may be significant from a control plane perspective, but for purposes of data plane operations, each blade may include a list of flow IDs for data flows being processed by the blade and a list of buckets that the blade is serving.

If the load balancer unicasts a data packet (so that the data packet includes a unicast indicator) to only one blade in accordance with operations ofFIG. 14A, the blade receiving the data packet (with the unicast indicator) is intended to process that packet. If an initial data packet with a unicast indicator is received at a blade through LB interface703, the blade processor701may add a flow ID for the initial data packet to the list of data flows in the ‘my-flows-and-buckets-table’, and the blade processor may determine a bucket ID for the data flow (by computing a hash of the flow ID) and add the bucket ID to the list of bucket IDs in the ‘my-flows-and-buckets-table’. If an initial data packet with a multicast indicator is received at a blade through LB interface703, the blade processor701may obtain a bucket ID for the initial data packet by computing a hash of the flow ID and compare the resulting bucket ID with the list of bucked IDs in the ‘my-flows-and-buckets-table’ to determine if the initial data packet was from a bucket being served by the blade. If the multicast initial data packet is from a bucket being served by the blade, the blade processor701adds the flow ID to the list of flow IDs in the ‘my-flows-and-buckets-table’ and processes the data packet. If the multicast initial data packet is from a bucket that is not being served by the blade, the blade processor701drops the packet. If a non-initial data packet is received as a multicast (e.g., with a multicast indicator), the blade processor701looks up the flow ID in the my-flows-and-buckets table. If the flow ID is not present in flow ID list of the ‘my-flows-and-buckets-table’, the non-initial multicast data packet belongs to a flow of another blade, and the blade processor701can drop the packet. If the flow ID is present in the flow ID list of the ‘my-flows-and-buckets-table’, the non-initial multicast data packet belongs to a flow being handled by the blade, and the blade processor701can process the packet.

FIG. 15Ais a flow chart illustrating blade/server operations for type-1 data flows using transient multicast/broadcast based distributed approaches corresponding to load balancer operations ofFIG. 14A,FIG. 15Bis a my-flows-table, andFIG. 15Cis a my-buckets-table according to some embodiments. Operations ofFIG. 15Amay be performed by processor701, and the my-flows-table and the my-buckets-table may be saved in memory707. At block1500, processor701may define/revise the server flows and buckets tables ofFIGS. 15B and 15Cin memory707. When a data packet is received through interface703at block1501, processor701determines if the data packet was transmitted from the load balancer LB as a unicast or a multicast transmission at block1503. As discussed above with respect toFIG. 14A, a data packet may be transmitted with a unicast/multicast indicator (e.g., a unicast destination address or a multicast destination address) to allow blade processor701to determine whether the data packet was a unicast or multicast data packet at block1503.

If the data packet is a unicast data packet at block1503and an initial data packet for a new data flow (e.g., as indicated by an INIT flag) at block1505, processor701may perform the hash function on the flow ID of the data packet to compute a bucket ID used to process the data packet at the load balancer at block1507. Processor701may then add the flow ID for the new flow to the my-flows table at block1511, and process the data packet at block1517. By adding the flow ID to the table ofFIG. 15Bin memory707, processor701can identify subsequent data packets belonging to the new data flow for processing at block1517whether the subsequent data packets are unicast or multicast. If the data packet is a unicast data packet at block1503and a non-initial data packet for a previously established data flow (e.g., as indicated by the absence of an INIT flag) at block1505, processor701may process the data packet at block1517without performing operations of blocks1507and/or1511.

If the data packet is a multicast data packet at block1503and an initial data packet for a new data flow (e.g., as indicated by an INIT flag) at block1519, processor701may perform the hash function on the flow ID of the data packet to compute a bucket ID used to process the data packet at the load balancer at block1521. If the resulting bucket ID is included in the table ofFIG. 15C(meaning that the blade is serving data flows from that bucket) at block1523, processor701may add the data flow ID to the table ofFIG. 15Bat block1511, and process the data packet at block1517. If the resulting bucket ID is not included in the table ofFIG. 15Cat block1523, then processor701may drop the data packet at block1527. If the data packet is a multicast data packet at block1503and a non-initial data packet for a previously established data flow (e.g., as indicated by the absence of an INIT flag) at block1519, processor701may determine at block1525if the flow ID of the data packet is included in the table ofFIG. 15B. If the flow ID is included in the table ofFIG. 15Bat block1525, processor701may process the data packet at block1517. If the flow ID is not included in the table ofFIG. 15Bat block1525, processor701may drop the data packet at block1527.

In embodiments ofFIG. 15C, the control plane may maintain the my-buckets-table for each server. The my-buckets-table may provide a list of bucket IDs identifying the buckets that are mapped to the server associated with the my-buckets-table. The control plane may thus define/update/modify a respective my-buckets table for each server coupled to the load balancer LB.

While not shown inFIG. 15B, the table ofFIG. 15Bmay also include the bucket ID associated with each flow ID (separate from the table ofFIG. 15C). Once the bucket ID is identified at block1507(or at block1521), the flow ID and associated bucket ID for the new flow may be added to the My-Flows table at block1511.

FIGS. 15D,15E, and15F illustrate alternative server operations (relative to those discussed above with respect toFIGS. 15A,15B, and15C) where the server/blade does not need to differentiate whether traffic is unicast or multicast.FIGS. 15E and 15Fare my-flows and my-buckets tables that may be the same asFIGS. 15B and 15Cdiscussed above. Where reference numbers ofFIG. 15Dare the same as corresponding reference numbers ofFIG. 15A, the corresponding operations having the same reference numbers may be the same/similar.

FIG. 15Dis a flow chart illustrating blade/server operations for type-1 data flows using transient multicast/broadcast based distributed approaches corresponding to load balancer operations ofFIG. 14A,FIG. 15Eis a my-flows-table, andFIG. 15Fis a my-buckets-table according to some embodiments. Operations ofFIG. 15Dmay be performed by processor701, and the my-flows-table and the my-buckets-table may be saved in memory707. At block1500, processor701may define/revise the server flows and buckets tables ofFIGS. 15B and 15Cin memory707. When a data packet is received through interface703at block1501, processor701determines if the data packet is an initial or non-initial data packet for a data flow.

If the data packet is an initial data packet for a new data flow (e.g., as indicated by an INIT flag) at block1519, processor701may perform the hash function on the flow ID of the data packet to compute a bucket ID used to process the data packet at the load balancer at block1521. If the resulting bucket ID is included in the table ofFIG. 15F(meaning that the blade is serving data flows from that bucket) at block1523, processor701may add the data flow ID to the table ofFIG. 15Eat block1511, and process the data packet at block1517. If the resulting bucket ID is not included in the table ofFIG. 15Fat block1523, then processor701may drop the data packet at block1527. If the data packet is a non-initial data packet for a previously established data flow (e.g., as indicated by the absence of an INIT flag) at block1519, processor701may determine at block1525if the flow ID of the data packet is included in the table ofFIG. 15E. If the flow ID is included in the table ofFIG. 15Eat block1525, processor701may process the data packet at block1517. If the flow ID is not included in the table ofFIG. 15Eat block1525, processor701may drop the data packet at block1527.

In embodiments ofFIG. 15D, the control plane may maintain the my-buckets-table for each server. The my-buckets-table may provide a list of bucket IDs identifying the buckets that are mapped to the server associated with the my-buckets-table. The control plane may thus define/update/modify a respective my-buckets table for each server coupled to the load balancer LB.

While not shown inFIG. 15E, the table ofFIG. 15Emay also include the bucket ID associated with each flow ID (separate from the table ofFIG. 15F). Once the bucket ID is identified at block1521, the flow ID and associated bucket ID for the new flow may be added to the My-Flows table at block1511.

Control Plane Operations for Type-1 Flows

In this section, control plane embodiments are discussed. There are multiple viable ways in which a control plane can be implemented depending on the use case and various embodiments are disclosed herein.

As discussed above, the a bucket enters the transient state from the steady state when the Blade ID corresponding to the bucket is modified and the original Blade ID is recorded in the Old Blade ID column. Control plane operations may be used to decide when the bucket can return to the steady state after having entered the transient state. When a signal is received from the control plane indicating that the bucket should return to the steady state (from the current transient state), the Old Blade ID field corresponding to the bucket is erased. The control plane may thus decide when the Old Blade ID is no longer needed.

For example, an Old Blade ID may no longer needed when all flows belonging to the bucket that are mapped to the Old Blade ID have ended. In other words, the Old Blade ID for bucket ‘x’ may no longer be needed when a number of connections on and/or data flows to the old blade that correspond to bucket ‘x’ go to zero. This criterion, however, may be unnecessarily strict. For example, a few connections may be active for a very/relatively long time, connections may be inactive but kept open for a relatively long time, or FIN/FINACKs (end of data flow indicators) may go missing. Under such conditions, a bucket may be in the transient state for an unnecessarily long time, resulting in a loss of bandwidth due to unnecessary multicast transmissions and/or additional processing on blades. Therefore, a mechanism that provides a reasonable criterion to conclude that Old Blade ID for the bucket is no longer needed may be desired.

As discussed above, a more detailed architecture of the My-flows-table may be useful from the control plane perspective.FIG. 16Ais a table illustrating an example of a my-flows table that may be stored in memory707of a blade. In table16A, each data flow being processed by the blade is provided in a row of the my-flows-table, with each row identifying a different flow ID (identifying the respective data flow), a bucket ID identifying the bucket to which the flow ID maps (based on the hash function), a bit-rate for the data flow, and a timer value. The timer for a data flow refers to the time at which a last (most recent) data packet for the data flow was received. Based on information in the my-flows-table ofFIG. 16A, the blade processor701may also generate a consolidated version of the my-flows-table which can be used to assist control plane decision making. The consolidated flows table ofFIG. 16Bprovides the data of the my-flows-table grouped by bucket ID. Stated in other words, the my-flows-table ofFIG. 16Aprovides a row for each data flow (with multiple data flows potentially mapping to the same bucket ID, e.g., with Flow IDs 216.43.56.23 and 200.1.12.10 both mapping to bucket ID 5), while the consolidated flows table ofFIG. 16Bprovides one row for each bucket ID (without providing separate information for data flows). The number of connections column identifies the number of data flows handled by the blade that map to the respective bucket ID, the net bit-rate column identifies a net bit-rate for all of the data flows handled by the blade that map to the respective bucket ID, and the timer column identifies the time at which a last (most recent) data packet was received for any data flow mapping to the respective bucket ID. Of the data flows mapping to bucket 5 in the my-flows-table ofFIG. 16A, the most recent of these timer values is used for bucket 5 in the consolidated flows table ofFIG. 16B.

Information from the consolidated flows table ofFIG. 16B, for example, may be used to determine when a flow of packets from an bucket to the blade is no longer significant. For example, a criterion may be based on a number of data flows (# connections) to the blade which map to a given bucket ID dropping below a certain threshold. As discussed above, requiring the number of data flows to drop to zero may be an unnecessarily strict criterion, and the number of data flows reaching a near zero number may be good enough. Care should be taken when using this criterion, however, because a relatively small number of data flows may be significant if the relatively small number of connections generate significant data throughput (i.e., net bit-rate). As shown inFIG. 16B, only two data flows may map to Bucket 2, but these data flows may account for a significant net bit-rate.

Another criterion may be based on a net bit-rate corresponding to the bucket being less than a threshold. A low net bit-rate may be a good reason to drop the existing flows corresponding to the bucket and release the bucket to a steady state.

Still another criterion may be based on the timer which can be used to determine periods of inactivity. If the last data packet from any data flow for a bucket was received a relatively long time ago, data flows from that bucket may be inactive. If the flows corresponding to the bucket have been inactive for a sufficiently long period of time, that bucket may be dropped to the steady state without significant loss of data.

One or more of the above referenced criterion may be used alone or in combination to determine when a bucket should be returned from the transient state to the steady state. Additionally, For type-1 flows, a Consolidated Flows Table may also be created and maintained at the load balancer LB for each blade. The load balancer can keep track of numbers of connections for each blade by incrementing or decrementing a respective connection counter whenever an outgoing INIT/INITACK or FIN/FINACK packet is generated for the blade. It may also be possible to keep track of bucket net bit-rates and/or last packets received in a similar manner for each blade.

For Type 2 Flows

As discussed above, type-2 flows are data flows which may be substantially arbitrary such that initial packets of a type-2 data flow may be difficult to identify when considering packet header information. In this section, a multicast based distributed approach is discussed for type-2 data flows. The approach may include two parts: data plane operations; and control plane operations. Data plane operations may primarily handle how incoming data packets are forwarded to and received by the blades assuming an instance of a B2B Mapping Table at any given point in time. Data plane operations may include operations running on both the load balancer and the blades. Control plane operations may be used to maintain and modify the B2B Mapping Table residing on load balancer memory807.

Data Plane Operations for Type-2 Flows

In this approach, a two-stage ‘distributed’ mechanism may be used (similar to that discussed above with respect to type-1 flows). The first stage includes screening data packets at the load balancer to make an appropriate forwarding decision. The second stage includes screening of received packets at the blade. Because the load balancer may be unable to identify start-of-the-flow/INIT data packets for type-2 data flows, the load balancer forwarding decisions for type-2 data flows may be based on whether the bucket to which a data packet maps is in steady state or transient state (without considering whether the data packet is an initial or subsequent data packet of its data flow).

Load balancer LB operations may include maintaining a B2B mapping table at load balancer memory807. For each incoming data packet, load balancer processor801may obtain the Bucket ID using the hash function. As discussed above, the Bucket ID is computed as a hash of an element of the packet header such as the Flow ID. If the bucket is in steady state, the data packet is unicast to the blade corresponding to the bucket (i.e., the current blade identified for the bucket ID in the B2B mapping table). If the bucket is in transient state, the data packet is multicast to both current Blade ID and Old Blade ID (i.e., the current blade and the old blade identified for the bucket ID in the B2B mapping table).

FIG. 17Ais a flow chart illustrating operations of the above data plane operations implemented by load balancer processor801. Operations ofFIG. 17Amay be the same as and/or similar to those discussed above with respect toFIG. 14A. As discussed above, a bucket is in the steady state if the corresponding Old Blade ID field for that bucket is empty. As an example, inFIG. 17A, Bucket 2 is in steady-state while Bucket 1 is not (i.e. Bucket 1 is in transient state). Therefore, any data packet that maps/belongs to Bucket 2 will be forwarded to Blade 3 only, while any data packet that maps/belongs to Bucket 1 will be forwarded to both Blade 4 and Blade 7. These forwarding decisions will be the same for both initial (INIT) and non-initial (non-INIT) data packets because load balancer processor801may be unable to distinguish initial and non-initial data packets for type-2 data flows.

According to some embodiments, the multicast/unicast indicator may be provided as the destination address of the data packet. If the data packet is transmitted as a multicast to both the current and old blades of Bucket 1 (in transient state) at block1409, for example, load balancer processor801may include a multicast destination address (with addresses/IDs of both blade 4 and blade 7) in the header of the data packet. If the data packet is transmitted as a unicast to only the current blade of Bucket 2 (in steady state) at block1411, for example, load balancer processor801may include a unicast destination address (with address/ID of only blade 3) in the header of the data packet. The receiving blade or blades can thus determine whether a received data packet was transmitted from the load balancer as a unicast or multicast transmission based on the destination address or addresses included in the data packet.

At the Blades

A Multicast Partner of a blade for a given data packet/flow is defined as the other blade (in a multicast group) to which a data packet/flow is being multicast (forwarded). Stated in other words, a multicast group for a transient state bucket is defined to include the current and old blades for the transient state bucket, and each blade of the multicast group is defined as a multicast partner of the other blade(s) of the multicast group. In operations discussed above, a data packet may be multicast to at most two blades (the current and old blade for the corresponding transient state bucket). According to such embodiments, a blade will have at most one multicast partner for any given data packet. By way of example, for operations of FIGS.17A and17B, Blade 7 is the multicast partner of Blade 4, and Blade 4 is the multicast partner of Blade 7 for any data packets/flows that hash to Group 1 in the illustrated transient state.

A blade can determine its multicast partner for a given packet by considering the destination multicast group address that the data packet is sent to. As discussed above, the header of each data packet may include a unicast/multicast destination address allowing a receiving blade to determine whether the data packet was transmitted as a unicast or multicast transmission, and also allowing the receiving blade to identify a multicast partner(s) for any multicast data packets. Each receiving blade can thus maintain a mapping between active multicast group addresses and constituent blades. Each receiving blade can also determine its multicast partner(s) by hashing the flow ID of the packet to obtain Bucket ID and then looking it up in the B2B Mapping Table to determine which other (old or current) Blade ID it is being grouped with. The load balancer may also encode the multicast partner in one of the header fields. In summary, regardless of the implementation, a blade may be able to identify its multicast partner.

Operations running on the blades may be summarized as follows with reference toFIGS. 18A,18B, and18C.

Each blade maintains a list of data flow IDs being processed by that blade and a list of buckets being served by that blade, referred to as a ‘my-flows-table’ as shown inFIG. 18Band a ‘my-buckets-table’ as shown inFIG. 18D. While a more detailed architecture of this table may be significant from a control plane perspective, for data plane operations, the lists ofFIGS. 18B and 18Care sufficient. For purposes of data plane operations, it may be sufficient to have on each blade a list of data flow IDs and buckets IDs for buckets being served by the blade (saved in memory707). If the blade is a part of a multicast group, the blade also maintains a list of data flow IDs that its Multicast Partner is currently serving as shown inFIG. 18C. Note that the blade may need to maintain partner data flows only for transient state buckets being served by the blade. Furthermore, the blade only needs to maintain a list of those partner flows which correspond to transient state buckets being served by the blade.

At block1800, processor701defines/revises data flow and bucket lists ofFIGS. 18B and 18Dand the list of multicast partners ofFIG. 18Cin memory707. Responsive to receiving a data packet from the load balancer at block1801through LB interface703, processor701determines if the packet was received as a unicast or a multicast at block1803. If the packet header includes only one destination blade address (i.e., the blade address of the receiving blade), processor701can determine that the data packet was unicast. If the packet header includes multiple destination blade addresses (i.e., the blade addresses of the receiving blade and a multicast partner blade), processor701can determine that the data packet was multicast.

If the blade receives a packet as a unicast (e.g., only one destination blade address for the blade is included in the packet header) at block1803, the data packet is intended for that blade for processing, and the blade processes the packet. If the data packet is an initial data packet for a new data flow (i.e., the flow address is not already included in the list of data flows of the my-flows table) at block1805, processor701: performs the hash function on the flow ID at block1807to determine the bucket ID for the data flow; adds the flow ID to the list of data flows at block1811, and processes the data packet at block1817. If the data packet is a subsequent data packet for an existing flow for the blade (i.e., the flow address is already included in the list of data flows of the my-flows-and-buckets-table) at block1805, processor701may process the data packet at block1817without updating list ofFIG. 18B.

If a data packet is received as a multicast at block1803, processor701determines if the flow ID is present in the my-flows-and-buckets table ofFIG. 18Bat block1819. If the data flow ID of the multicast data packet is present in the list of data flows ofFIG. 18B, the data packet is part of a data flow being processed by the blade, and processor701processes the data packet at block1817.

If a data packet is received as a multicast at block1803and its data flow ID is not found in the list of data flows for the blade ofFIG. 18Bat block1819, processor701determines if the data packet belongs to one of the data flows of a multicast partner (provided in the list ofFIG. 18C) at block1821. If a data flow indication of the data packet is included in the list ofFIG. 18Cat block1821, another multicast partner blade will process the data packet. Accordingly, processor701may drop the data packet at block1827.

If the data packet is received as a multicast data packet at block1803and its data flow ID is not included in either of the lists of data flows ofFIGS. 18B and 18Cat blocks1819and1821, processor701may determine that the data packet is an initial data packet of a new data flow. Accordingly, processor701obtains the bucket ID for the data packet at block1823. More particularly, processor701computes the bucket ID of the data packet by performing the hash function on the data flow ID of the data packet as discussed above. If the bucket ID of the data packet is included to the list of my-buckets ofFIG. 18Dat block1825, processor701may add the data flow ID of the data packet to the list of data flows ofFIG. 18Bat block1811and process the data packet at block1817. If the bucket ID of the data packet is not included in the list of my-buckets ofFIG. 18Dat block1825, processor701may drop the data packet at block1827.

WhileFIG. 18Ashows that Flow IDs of partner data flows may be checked at block1821before checking the list of buckets for the server/blade at block1825, this order of operations/logic may be reversed. For example, if the flow ID is not included in my-flows-table at block1819, processor701may perform operations of blocks1823and1825to determine if the bucket ID is included in the list of buckets for the server/blade ofFIG. 18D. If the bucket ID is not included in the list, processor701may drop the data packet at block1827. If the bucket ID is included in the list, processor701may determine if the flow ID is in the table of partner data flows ofFIG. 18C. If the flow ID is included in the table of partner data flows ofFIG. 18C, processor701may drop the data packet at block1827, or if the flow ID is not included in the table of partner data flows ofFIG. 18C(after determining that the bucket ID is included in the my-buckets-table), processor701may add the data flow ID to the table ofFIG. 18Band process the data packet.

In embodiments ofFIG. 18D, the control plane may maintain the my-buckets-table for each server. The my-buckets-table may provide a list of bucket IDs identifying the buckets that are mapped to the server associated with the my-buckets-table. The control plane may thus define/update/modify a respective my-buckets table for each server coupled to the load balancer LB.

While not shown inFIG. 18B, the table ofFIG. 18Bmay also include the bucket ID associated with each flow ID (separate from the table ofFIG. 18B). Once the bucket ID is identified at block1807(or block1823), the flow ID and associated bucket ID for the new flow may be added to the My-Flows table at block1811.

FIGS. 18E,18F,18G, and18H illustrate alternative server operations (relative to those discussed above with respect toFIGS. 18A,18B,18C, and18D) where the server/blade does not need to differentiate whether traffic is unicast or multicast.FIGS. 18F,18G, and18H may be the same asFIGS. 18B,18C, and18D discussed above. Where reference numbers ofFIG. 18Eare the same as corresponding reference numbers ofFIG. 18A, the corresponding operations having the same reference numbers may be the same/similar.

At block1800, processor701defines/revises data flow and bucket lists ofFIGS. 18F and 18Hand the list of multicast partners ofFIG. 18Gin memory707. Responsive to receiving a data packet from the load balancer at block1801through LB interface703, processor701determines if the flow ID is present in the my-flows-and-buckets table ofFIG. 18Bat block1819. If the data flow ID of the multicast data packet is present in the list of data flows ofFIG. 18F, the data packet is part of a data flow being processed by the blade, and processor701processes the data packet at block1817.

If the data flow ID is not found in the list of data flows for the blade ofFIG. 18Fat block1819, processor701determines if the data packet belongs to one of the data flows of a multicast partner (provided in the list ofFIG. 18G) at block1821. If a data flow indication of the data packet is included in the list ofFIG. 18Gat block1821, another multicast partner blade will process the data packet. Accordingly, processor701may drop the data packet at block1827.

If the data flow ID is not included in either of the lists of data flows ofFIGS. 18F and 18Gat blocks1819and1821, processor701may determine that the data packet is an initial data packet of a new data flow. Accordingly, processor701obtains the bucket ID for the data packet at block1823. More particularly, processor701computes the bucket ID of the data packet by performing the hash function on the data flow ID of the data packet as discussed above. If the bucket ID of the data packet is included to the list of my-buckets ofFIG. 18Hat block1825, processor701may add the data flow ID of the data packet to the list of data flows ofFIG. 18Bat block1811and process the data packet at block1817. If the bucket ID of the data packet is not included in the list of my-buckets ofFIG. 18Hat block1825, processor701may drop the data packet at block1827.

In embodiments ofFIG. 18H, the control plane may maintain the my-buckets-table for each server. The my-buckets-table may provide a list of bucket IDs identifying the buckets that are mapped to the server associated with the my-buckets-table. The control plane may thus define/update/modify a respective my-buckets table for each server coupled to the load balancer LB.

While not shown inFIG. 18F, the table ofFIG. 18Fmay also include the bucket ID associated with each flow ID (separate from the table ofFIG. 18H). Once the bucket ID is identified at block1823, the flow ID and associated bucket ID for the new flow may be added to the My-Flows table at block1811.

WhileFIG. 18Eshows that Flow IDs of partner data flows may be checked at block1821before checking the list of buckets for the server/blade at block1825, this order of operations/logic may be reversed as discussed above with respect toFIG. 18A.

Control Plane Operations for Type-2 Flows

Control plane operations for type-2 flows may be similar to and/or the same as those discussed above with respect toFIGS. 16A and 16Bfor type-1 flows. Repetition of similar details is omitted here for the sake of conciseness. With type-2 flows, however, load balancer LB may be unable to implement control plane operations and/or underlying architectures (e.g., a Consolidated Flows Table), because initial (INIT) data packets (indicating the start of a new flow) cannot be identified by considering only header information of the data packet. Accordingly, control plane operations may be required to reside on blades when dealing with type-2 flows. This aspect of control plane operations for type-2 flows may thus differ from that of control plane operations for type-1 flows discussed above with respect toFIGS. 16A and 16B.

Extended Algorithm for Multiple Cascaded Transients

As discussed above, load balancer and blade operations have been discussed with respect to examples with one transient bucket (i.e., the blade corresponds to the bucket that changes from A to B and is not reassigned until it reaches steady state), which may be handled with a multicast group of size of at most 2.

It is possible, however, that a bucket may be reassigned multiple times in a short period of time (before it reaches steady state after the first of the multiple reassignments). For example, a certain bucket ‘x’ may be assigned to Blade A and then reassigned to Blade B. While the bucket ‘x’ is still in the transient state, it may be reassigned to Blade C. In such a scenario, an extended mechanism may be used as discussed in greater detail below.

To address this issue, a multicast group having a size greater than two may be used. In the example noted above (where bucket ‘x’ was initially assigned to Blade A, then reassigned to Blade B, and then reassigned to Blade C while the bucket ‘x’ is still in the transient state with Blade A as the old blade), processor801can store both Blade A and Blade B in the list of Old Blade IDs corresponding to the Bucket x. Blades A, B, and C may together form a multicast group having a size of three. Any data packet that belongs/maps to bucket ‘x’ can thus be multicast to a multicast group including Blade A, Blade B, and Blade C. A number of blades in the multicast group is thus 3. Respective processes running on each of the three blades (i.e., A, B, and C) in the multicast group will thus govern whether the data packet is to be dropped or processed by respective blades of the multicast group.

Briefly, multicast based load balancing mechanisms set forth above may be generic and may be extended to cases of multiple cascaded transients. If a number of cascaded transients for a particular bucket is T, then the multicast group for that bucket may include T+1 blades. Issues regarding these extended operations and workarounds relating thereto are discussed below.

Virtual Machine Based Cloud Infrastructure

In a virtual machine (VM) application, a server defined as discussed above with respect toFIGS. 13A,15A,15D,18A, and/or18E may be instantiated in a VM (Virtual Machine). Moreover, VMs may be moved from one physical server to another and all the connections of that server in that VM may be preserved as such to the new physical server with a new Server ID.

The load balancing logic (e.g., as discussed with respect toFIGS. 12A,14A, and/or17A) may apply with no change. The server side logic (e.g., as discussed with respect toFIGS. 13A,15A,15D,18A, and/or18E) may not be needed since there is only one server which simply moved to the new location, and hence, there may be no need to coordinate anything at the server level (unlike in previous cases where load is coordinated/split between two different servers. In other words, server side logic ofFIGS. 13A,15A,15D,18A, and/or18E may not necessarily apply in VM based clout infrastructure applications. Once the control plane decides that some bucket is in the transient/transition mode (due to the server in the VM moving from one physical server to another) the control plane triggers the bucket to be in the transient mode and the load balancer logic is used to multicast/broadcast the traffic between the current and the old servers/blades during the time period of the server movement (while the bucket is in the transient/transition mode. Then, multicasting is stopped and unicasting to the new location of the server is initiated after the movement is completed. A need to provide synchronization of traffic switchover and server movement may thus be avoided.

VLAN Based Broadcast Implementation Alternative

Embodiments forwarding packets to multiple servers are not limited to multicast group mechanisms discussed above. For example, VLAN (Virtual Local Area Network) based broadcasts may be used. If a certain bucket ‘x’ was initially assigned to Blade A and the reassigned to Blade B, then load balancer processor801forwards data packets (or only non-INIT data packets, depending on the method) that correspond to bucket ‘x’ to both blades A and B. This can be implemented by considering both the blades to be in one VLAN. Then, the data packet is just forwarded to that VLAN, and the VLAN takes care that the packet is broadcasted to the individual blades.

FIG. 19is a block diagram illustrating such a VLAN based alternative according to some embodiments. As shown inFIG. 19, Blades 1 and 2 are part of one VLAN referred to as VLAN-1. Any packets that are broadcast (i.e., multicast) to VLAN-1 will reach both Blades 1 and 2. If all buckets served by a blade are in the steady state, then that blade can be part of a single blade VLAN. For example, VLAN-2 may be a single blade VLAN including only blade 3, and VLAN-3 may be a single blade VLAN including only blade 4. Accordingly, data packets sent to VLAN-2 are received by blade 3 only, and data packets that are sent to VLAN-3 are received by blade 4 only. If a certain bucket is reassigned from Blade 3 to Blade 4, a new VLAN may be created that includes both Blade 3 and Blade 4. Such VLAN based implementations may provide a flexible way of broadcasting packets to multiple blades/servers within a group.

Advantages of Multicast Based Distributed Approaches

Multicast based distributed approaches discussed above may support load balancing with reduced hit or hitless addition and/or removal of blades. Accordingly, data flow disruption may be reduced when a new blade is added or when a blade is removed.

Even though mapping between data Flow IDs and Bucket IDs is static, the mapping between Bucket IDs and Blades can be changed dynamically to provide better uniformity (e.g., load balancing). Dynamic mapping between bucket IDs and blade IDs may be applicable when a blade is added or removed. In addition, dynamic mapping between bucket IDs and blade IDs may provide a mechanism allowing the load balancer to maintain a uniformity index (e.g., a Jain's fairness index) over time as loads of different blades change.

If the uniformity index drops below a certain threshold, processor801may call for a reassignment of one or more buckets to different blades. The buckets selected for reassignment may depend on parameters such as number of flows corresponding to the bucket(s), bit-rate corresponding to the bucket(s), current load on the blades, blades on downtime, and control parameters (e.g., when the last packet from the bucket was received). An exact mechanism governing this choice, however, may be beyond the scope of this disclosure. Approaches disclosed herein may enable a load balancer to provide a relatively smooth reassignment of buckets to blades with reduced loss of data flows when such a reassignment takes place.

Multicast Based Distributed Approaches disclosed herein may provide flow awareness. Each blade, for example, may decide whether to process or drop a received data packet depending on whether it belongs to a list of data flows that are being processed by the respective blade.

Multicast Based Distributed Approaches disclosed herein may support dynamicity of resources (e.g., blades), by enabling resources (e.g., blades) to be added and/or removed with reduced disruption to existing data flows.

In multicast based distributed approaches disclosed herein, a relatively low complexity load balancer may unicast or multicast the data packets based on whether the bucket is in the steady-state or in the transient state. Additional Load balancer architecture may include a hash module/function, fixed length B2B (Bucket-to-Blades) mapping and O(1) table lookup.

Multicast based distributed approaches disclosed herein may support different types of data traffic and/or flows. While approaches have been discussed with respect to type-1 and type-2 data flows, other data types may be supported.

A B2B mapping table may have a fixed size and is not expected to change frequently. Therefore, a backup load balancer may not need to perform computationally intensive tasks (e.g., copying and syncing large tables or flow-level information) in real time, thereby providing a relatively low complexity failover mechanism for the load balancer. It may suffice for the backup load balancer to know the hash module/function and to sync up with the active load balancer B2B mapping table when the B2B mapping table changes.

Issues for Multicast Based Distributed Approaches

The relatively low complexity load balancer may generate a greater load on the blades. Rather than simply processing the received packets, a blades may be required to first perform operations to determine whether or not to process the received packet. Increased processing and/or memory requirements may thus be imposed on blades potentially resulting in latency issues in some scenarios. Because multicast/broadcast transmissions only occur for buckets in the transient state this additional burden may be reduced/limited.

Broadcast/multicast transmission of data packets to multiple servers/blades may reduce backplane bandwidth available for other traffic because repetitive information (data packets) is forwarded over multiple links (i.e., between the load balancer and multiple blades) when different incoming packets could be forwarded over the links Because the multicast/broadcast transmissions only occur for buckets in the transient state, this additional burden may be reduced/limited.

Handling of multiple cascaded transients (e.g., T number of cascaded transients) for a same bucket was discussed above using multicast group of size T+1. Bandwidth loss, however, may be proportional to a number of servers in the multicast group to which the packet is multicast/broadcast. For example, the packets may be broadcast to all the servers potentially consuming bandwidth that could otherwise be used to transmit other information. Moreover, in the context of type-2 flows, operations running on blades in case of type-2 flows may need access to the list of partner flows. In a multiple transient situation, if there are K blades in the multicast group, each blade may have K−1 partners. Therefore, at any point of time, each blade in transient may need to synchronize flow tables with all K blades in the group.

The blades, however, may not need to synchronize all their flows. The blades may only need to synchronize those flows corresponding to the bucket in the transient state which resulted in formation of the multicast group. As an example, even if there are one million existing flows, if 64K buckets are maintained, assuming reasonable uniformity, only tables of size about 100 rows (flows) per blade may need to be synchronized (as opposed to the one million flows).

To reduce/avoid issues of synchronizing large numbers of servers and/or to reduce/avoid waste of bandwidth, a number of simultaneous transitions allowed may be reduced/limited. In other words, a maximum number of blades in one multicast group may be reduced/limited to a certain upper limit. In some embodiments discussed above, that limit was set to two blades.

Transient Table Based Approach (Approach II)

Transient Table Based Approaches may enable reduced hit and/or hitless addition, removal, and/or reallocation of blades while increasing/maintaining flow stickiness. In this approach, a “Transient Table” is maintained that includes ‘new’ connections for every bucket in the transient state.

Transient table based approaches use unicast transmissions of each packet to the blade that will process that packet. Accordingly, multicast transmissions of packets to multiple blades may be reduced/avoided. Therefore, load balancing operations presented according to this approach may run solely at/on the load balancer, and additional load balancing operations running on blades may not be required. Accordingly, each blade may process the packets received at that blade without determining whether a given packet is intended for that blade.

Transient table based approaches, however, may be better suited for type-1 flows, and transient table based approaches may not be applicable to type-2 flows. As discussed above, type-1 flows are those flows for which it is possible to detect the start of a data flow or a first data packet of a data flow by only considering bits in the first data packet of the data flow, without considering any other information.

Transient table based approaches according to some embodiments disclosed herein may be broken into data plane operations and control plane operations. Data plane operations may be used primarily to handle how incoming data packets are forwarded to and received by the blades assuming an instance of a B2B Mapping Table at any given point in time.

Control plane operations may be used primarily to handle maintenance and/or modification of the B2B Mapping Table residing on/at the load balancer.

Data Plane Operations

As discussed above, operations of transient table based approaches may run on/at the load balancer without requiring additional operational overhead at the blades. Moreover, load balancer LB maintains an additional table(s) in memory807called a ‘Transient Table’ (also referred to as a ‘Current Flows Table For Transient Bucket’) for each bucket in the transient state.

Transient Table For Transient Bucket

A Transient Table for bucket ‘x’ includes a list of all flows corresponding to the bucket ‘x’ that are initiated while the bucket ‘x’ is in the transient state. Once a bucket that was in the transient state returns to the steady state, the Transient Table for the bucket may be cleared (e.g., erased, deleted, disregarded, etc.).

Bucket ‘x’ enters the transient state whenever the blade ID corresponding to bucket ‘x’ changes, for example, from blade A to blade B. During such a change, Blade B is the new current blade, and Blade A is recorded as the Old Blade ID in the B2B mapping table as discussed above. At the initiation of the transition from blade A to blade B, all existing data flows through bucket ‘x’ are being served by Blade A, and any data packets received for these existing data flows should be forwarded to the old blade, (i.e., Blade A). Any data flows that are initiated after this transition to the transient state and during the transient state are recorded in the “Transient Table” for the bucket ‘x’. These data flows which are recorded in the “Transient Table” for bucket ‘x’ are to be forwarded to the new/current blade, i.e., Blade B.

Operations of load balancer processor801are illustrated in the flow chart ofFIG. 20A. At block2000, processor801defines/revises the mapping table ofFIG. 20Band/or any transient tables for any transient buckets. When a data packet is received through network interface805at block2001, processor801performs the hash function using a flow ID (or other header information) of the data packet to obtain a bucket ID to be used to process the data packet at block2003. If the bucket identified by the bucket ID of block2003is in the steady state at block2005(e.g., Bucket 2 from the B2B mapping table ofFIG. 20Bthat is stored in memory807), processor801clears the transient table from Bucket 2 (the current bucket) at block2009(if a/the transient table for Bucket 2 has not already been cleared), and unicasts the data packet to the current blade (e.g., blade 3) for the current bucket (e.g., Bucket 2). Operations of block2009may be omitted, for example, if transient tables are automatically cleared when a bucket transitions from the transient state back to the steady state, if the transient table for the current bucket in steady state was cleared responsive to a previous data packet, if the current bucket was never before in the transient state, etc.

If the bucket identified by the bucket ID of block2003is in the transient state at block2005(e.g., Bucket 1 from the B2B mapping table ofFIG. 20Bthat is stored in memory807), processor801determines if the data packet is an initial data packet (e.g., responsive to an INIT flag in a header of the data packet) of a new data flow at block2007. If the data packet is an initial data packet at block2007, processor801records the data flow ID for the data packet in the transient table ofFIG. 20Cat block2011, and unicasts the data packet to the current blade (e.g., blade 4) for the bucket in transient state at block2015. Accordingly, for each initial data packet for a new flow that is received for a bucket that is in transient state at blocks2005and2007, the data flow ID from the initial data packet is saved in the transient table ofFIG. 20Cat block2011allowing subsequent data packets of the same data flow to be identified at block2017for transmission to the current blade while the bucket is in the transient state.

For each non-initial data packet for an existing data flow that is received for a bucket that is in transient state (e.g., Bucket 1) at blocks2005and2007, processor801determines if the flow ID of the data packet matches one of the flow IDs in the transient table ofFIG. 20Cfor the current bucket at block2017. If the flow ID of the data packet does not match any of the flow IDs in the transient table ofFIG. 20Cfor the current bucket at block2017, the data packet belongs to a flow being handled by the old blade of the transient state bucket, and processor801unicasts the data packet to the old blade (e.g., blade 7) of the transient state bucket (e.g., Bucket 1) at block2019. Stated in other words, the data packet belongs to a data flow that was initiated before the bucket entered the transient state, and data packets of this previously existing flow should continue to be processed by the old blade. If the flow ID of the data packet does match one of the flow IDs in the transient table ofFIG. 20Cfor the current bucket at block2017, the data packet belongs to a flow being handled by the current blade of the transient state bucket, and processor801unicasts the data packet to the current blade (e.g., blade 4) of the transient state bucket (e.g., Bucket 1) at block2015. Stated in other words, the data packet belongs to a data flow that was initiated after the bucket entered the transient state, and data packets of this flow should be processed by the current blade.

Examples of operations ofFIGS. 20A,20B, and20C when Bucket 1 is in the transient state while Bucket 2 is in steady state are discussed below. Any data packet that belongs to steady state Bucket 2 will be forwarded to the Blade 3 (in accordance with blocks2005,2009, and2015), including both initial (INIT) and non-initial (non-INIT) data packets. Any initial (INIT) data packets that belongs to Bucket 1 will be forwarded to Blade 4 (in accordance with blocks2005,2007,2011, and2015). Non-initial (non-INIT) data packets that belong to Bucket 1 will be forwarded to Blade 4 if their flow IDs are included in the Transient Table for Bucket 1 (in accordance with blocks2005,2007,2017, and2015), or non-initial (non-INIT) data packets that belong to Bucket 1 will be forwarded to blade 7 if their flow IDs are not included in the transient table (in accordance with blocks2005,2007,2017, and2019).

As discussed above with respect to embodiments ofFIGS. 20A,20B, and20C, the load balancer may track new data flows that are added to a bucket in the transient state to determine whether packets to the transient state bucket should be forwarded to the new or old server/blade. According to some other embodiments discussed below with respect toFIGS. 20D,20E, and20F, the load balancer may track old data flows for a bucket that are initiated for the bucket before it enters the transient state. For example, for a period of time before a bucket enters the transient state (while the bucket is still in steady state), Flow IDs for data packets that map to the bucket are saved in a transient table for the bucket. Once the bucket enters the transient state, the list of data flows in the transient table for the transient bucket is maintained (without adding new data flows) to determine how to forward data packets while the bucket is in the transient state. When the bucket is in the transient state, the load balancer uses the list of old data flows from the transient table for the transient bucket to either: (1) transmit data packets belonging to data flows included on the list to the old server/blade, or (2) transmit data packets belonging to data flows not included on the list to the current/new server/blade. Once the bucket returns to the steady state, the transient table may be discarded.

Operations of load balancer processor801are illustrated in the flow chart ofFIG. 20D. At block2000, processor801defines/revises the mapping table ofFIG. 20Eand/or any transient tables for any transient buckets. When a data packet is received through network interface805at block2001, processor801performs the hash function using a flow ID (or other header information) of the data packet to obtain a bucket ID to be used to process the data packet at block2003. If the bucket identified by the bucket ID of block2003is in the steady state at block2005(e.g., Bucket 2 from the B2B mapping table ofFIG. 20Ethat is stored in memory807), processor801determines whether a decision has been made to move the bucket to transient state at block2029. Once a decision is made to move a bucket to the transient state, for example, the bucket may be maintained in the steady state for a period of time to record flow identifications for data flows being routed to the old server/blade before moving the bucket to the transient state.

If bucket is in steady state at block2005and the bucket has not been designated for movement to the transient state at block2029, processor801unicasts the data packet to the current blade (e.g., blade 3) for the current bucket (e.g., Bucket 2) at block2035. If the bucket is in steady state at block2005and the bucket has been designated for movement to the transient state at block2029, processor801records the flow ID for the data flow in the existing transient table ofFIG. 20Ffor the bucket (provided that the data flow has not been recorded already) at block2031and unicasts the data packet to the current blade (e.g., blade 3) for the current bucket (e.g., Bucket 2) at block2035. If the data flow has already been recorded in the table ofFIG. 20F, processor801may unicast the data packet without recording. Processor801may thus add entries to the table ofFIG. 20Ffor each data flow for which a data packet is received during the period of time that the bucket is designated for movement to the transient state before the bucket is moved to the transient state. The resulting transient table ofFIG. 20Fcan then be used by processor801to determine which data flows should continue to be routed to the old server/blade when the bucket enters the transient state.

If the bucket identified by the bucket ID of block2003is in the transient state at block2005(e.g., Bucket 1 from the B2B mapping table ofFIG. 20Ethat is stored in memory807), processor801determines if the flow ID of the data packet matches one of the flow IDs in transient table ofFIG. 20Ffor the current bucket at block2037. If the flow ID of the data packet matches any of the flow IDs in the transient table ofFIG. 20Ffor the bucket at block2037, the data packet belongs to a flow being handled by the old server/blade of the transient state bucket, and processor801unicasts the data packet to the old blade (e.g., blade 7) of the transient state bucket (e.g., Bucket 1) at block2039. Stated in other words, the data packet belongs to a data flow that was initiated before the bucket entered the transient state, and data packets of this previously existing flow should continue to be processed by the old server/blade. If the flow ID of the data packet does not match one of the flow IDs in the transient table ofFIG. 20Ffor the current bucket at block2037, the data packet likely belongs to a flow being handled by the current blade of the transient state bucket, and processor801unicasts the data packet to the current blade (e.g., blade 4) of the transient state bucket (e.g., Bucket 1) at block2039. Stated in other words, the data packet belongs to a data flow that was initiated after the bucket entered the transient state, and data packets of this flow should be processed by the current blade/server.

Control Plane

In this section, implementations of control planes using Transient Table Based Approaches are discussed according to some embodiments. As discussed above with respect to Multicast Based Distributed Approaches, a control plane can be implemented in different ways depending on the use case. Unlike Multicast Based Distributed Approaches, however, control planes for transient table based approaches may be implemented on/at only the load balancer, and additional processing on/at the blades may be reduced/avoided.

As discussed above, a bucket enters the transient state from the steady state when the Blade ID corresponding to the bucket is modified and the original Blade ID is recorded in the Old Blade ID column for the transient state bucket. Once a bucket has entered the transient state, control plane operations may decide when the bucket can return to the steady state from the transient state. When the signal is received from the control plane indicating that the bucket is ready to return to the steady state from the transient state, the Old Blade ID field corresponding to the old bucket is cleared/erased. The control plane may thus decide when is it reasonable to conclude that the Old Blade ID is no longer needed.

In some embodiments discussed above with respect toFIGS. 20A,20B, and20C, an Old Blade ID may no longer be needed when all data flows belonging to the bucket that are mapped to the Old Blade ID have ended. Requiring that all data flows mapped to the old blade ID have ended before returning to the steady state, however, may be an unnecessarily strict criterion. For example, a few data flows that are mapped to the old blade may remain active for a significant period of time after entering the transient state, and/or data flows can be inactive but kept open for a long time, and/or finish (FIN) or finish acknowledge (FINACK) indications (indicating the end of a data flow) may be missed/lost. Under such conditions, a bucket may remain in the transient state for an unnecessarily long period of time resulting in unnecessary processing overhead at the load balancer. A mechanism that provides a reasonable criterion to conclude that an Old Blade ID for the bucket is no longer needed may thus be desired.

Because transient table based approaches are used with type-1 data flows, load balancer LB can identify starts and ends of data flows by considering the initial (INIT/INITACK) or final (FIN/FINACK) data packets arriving for the data flows. Accordingly, it may be possible to maintain a Load Balancer Control Table in memory807as shown, for example, inFIG. 21. Load balancer control table, for example, may include a row for each bucket. Load balancer control table, for example, may include information (e.g., number of flows, net-bit rate, and timer information) for both current and old blades mapped to transient state buckets (e.g., buckets 1 and 3), but load balancer control table may include information (e.g., number of flows, net-bit rate, and timer information) for only the current blades mapped to transient state buckets (e.g., buckets 2 and B).

Load balancer processor801can thus keep track of numbers of data flows (connections) to each of the current and old blades mapped to a transient bucket by incrementing or decrementing the connection counter whenever it detects an outgoing initial (INIT/INITACK) data packet or final (FIN/FINACK) data packet for a data flow to one of the blades. Processor801may also keep track of a net bit-rate for each bucket and a time that a last packet was received for each bucket in a similar manner. Information included in the load balancer control table may thus be used by processor801to determine when a data flow to an old blade of a transient state bucket is no longer significant so that the transient state bucket can be returned to steady state (thereby terminating any remaining data flows to the old blade). Criteria that may be used to determine when a bucket can be returned to the steady state using information of a load balancer control table are discussed in greater detail below.

When a number of data flows being serviced by the Old Blade drops below a threshold, processor801may return the transient state bucket to the steady state. As discussed above, the number of flows serviced by an old blade dropping to zero may be an unnecessarily stringent criterion, and a number of data flows for an old blade reaching a near-zero number may be sufficient to return the transient state bucket to the steady state.

When a bucket is returned to steady state with a data flow to the old blade still active, the data flow to the old blade may be terminated because the current blade may be unable to service the data flow that was initiated with another blade. Accordingly, care may be taken to provide that a significant data flow is not lost even if a total number of data flows for an old blade falls below a threshold. Bucket 1 in the Load Balancer Control Table ofFIG. 21, for example, is in the transient state with only two data flows remaining to the old blade. Even thought the remaining number of data flows to the old blade is small (i.e., 2 data flows), one or both of these data flows may be significant as indicated by the net-bit rate for the old blade. Accordingly, even if the number of data flows to the old bucket is below the threshold, processor801may wait until a net bit-rate corresponding to the Old Blade is below a threshold returning the transient state bucket to the steady state.

Considering only net-bit rates may result in unwanted loss of data flows. Bucket 3 ofFIG. 21, for example, may be directing a relatively low bit-rate towards the old blade, but releasing bucket 3 to steady-state may result in dropping a relatively large number of data flows. Accordingly, other criteria and/or combinations of different criteria may be considered even if the total number of flows to the old blade and/or the net bit-rate to the blade are below the respective thresholds.

For example, processor801may consider a time elapsed since a last data packet to the old blade before returning a transient state bucket to the steady state. Processor801, for example, may require some minimum period of time to pass after a last data packet to an old blade before returning the bucket to the steady state. If the last data packet received from any flow from the transient state bucket to the old blade was a sufficiently long period of time ago (e.g., exceeding a threshold), processor801may return the bucket to the steady state. Stated in other words, if the flows from the transient state bucket to the old blade have been inactive for a sufficiently long period of time, any remaining data flows to the old blade may be dropped.

Any of the criteria discussed above (based on information from the table ofFIG. 21) may be used alone or in combination to determine when to return a transient state packet to the steady state. As shown in the flow chart ofFIG. 22, processor801may monitor the information ofFIG. 21for transient state buckets to determine when to return each transient state bucket to steady state. As shown inFIG. 22, when a number of old blade data flows from the transient state bucket are less than a first threshold at block2201, when a net-bit rate to the old blades from the transient state bucket is less than a second threshold at block2205, and when a time since a last data packet transmission from the transient state bucket to the old blade exceeds a third threshold at block2209, processor801may return the transient state bucket to the steady state. As shown inFIG. 22, the conditions of blocks2201,2205, and2209may be logically ‘ANDed’ so that all conditions must be fulfilled before processor801returns the transient state bucket to the steady state. According to some other embodiments, the conditions of blocks2201,2205, and2209may be logically ‘ORed’ so that satisfaction of the condition of any one of the decision blocks may be sufficient for processor801to return the transient state bucket to the steady state.

Multiple Transients

Transient table based approaches may also be able to handle multiple transients. For example, a bucket may be reassigned multiple times in a short period of time. For example, a certain bucket ‘x’ may be assigned to Blade A and then reassigned to Blade B. While the bucket ‘x’ is still in the transient state, it may again get reassigned to Blade C, a situation referred to as 3 layers of transitions (A, B and C). Blade C thus corresponds to the current blade while Blade A would still be designated as the Old Blade ID. In such a situation, the transient stateful table may be expected to have flows for both blades B and C. Once the control plane decides that all the flows associated to the OLD blade (i.e. Blade A) have been terminated gracefully, the stateless entry in the bucket to blade table can be switched to blade C, and all the related stateful table entries of blade C can be erased. However, there may still be stateful entries in the stateful table for blade B and such entries may need to be cleaned up as the lifetimes of the connections have ended. The above example can be extended to even greater numbers of transients by considering blade B as a set of blades instead of a single blade where the transients become A, B1, B2, . . . Bn, C where B={B1, B2 . . . , Bn}.

As discussed above, Transient table based approaches may thus provide reduced hit and/or hitless addition and/or removal of blades. Accordingly, disruptions of flows may be reduced/eliminated when a new blade is added and/or when an old blade is removed.

Despite mappings between Flow IDs and Bucket IDs that may be relatively static, the mapping between Bucket IDs and Blades can be changed dynamically to provide better uniformity and/or load balancing. This dynamic mapping of bucket IDs to blades may be applicable when a blade is added or removed, but dynamic bucket to blade mapping is not restricted to these two use cases. For example, a mechanism may be provide where load balancer processor801maintains some sort of a uniformity index (e.g., a Jain's fairness index) at all times. If the uniformity index drops below a certain threshold, processor801may call for a reassignment of one or more buckets to other blades. The bucket(s) selected for reassignment may depend on various parameters, such as, numbers of data flows corresponding to the buckets, bit-rates corresponding to the buckets, current loads on the blades, blades on downtime, and control parameters (e.g., when last packets from buckets were received). Approaches described herein may enable relatively smooth reassignments of buckets to blades with reduced loss of data flows when reassignments occur.

Transient table based approaches may provide/enhance flow awareness, because the load balancer temporarily maintains a list of flows for the old blade to provide flow stickiness while a bucket is in the transient state. Transient table based approaches may support dynamicity of resources (e.g., blades) by enabling addition/removal of resources (e.g., blades) with reduced disruption of the previously existing flows. In transient table based approaches, all load balancing functionality may reside on/at the load balancer so that additional processing at the blades (other than processing received packets) may be reduced. Transient table based approaches may not be limited to any particular type of traffic or flow provided that initial data packets of the data flows can be identified.

By reducing additional processing at the blades, additional processing may be required at the load balancer. The load balancer, for example, may need to store an additional table (Transient Table) for every bucket in the transient state. A number of rows in the Transient Table may be equal to the number of new data flows initiated for the bucket during the transient state. In a high traffic situation, the number of rows of a transient table may be relatively high. Assuming a total number of buckets is on the order of 64K (e.g., in current Smart Services Router Line Card implementations), only the states of the data flows for the buckets in transient state may need to be maintained. In practice, a total number of flow IDs that may need to be maintained in a transient table is expected to be relatively low, and a bucket is not expected to be in the transient state for long.

As discussed above, transient table based approaches may require that the load balancer identify the start of each data flow (e.g., using initial or INIT data packets). Therefore, transient table based approaches may be difficult to implement for type-2 flows.

In case of multiple transients, the temporary usage of memory807for transient tables may increase. As discussed above, for example, once all the data flows for Blade A are finished, the destination on the bucket ‘x’ can be switched to blade C and the transient stateful entries for blade B may still exist on the stateful table until all such flows are finished/terminated.

Alternative Approaches to Modifying B2B Mapping Tables

Before discussing third approaches of the present disclosure, a modified B2B mapping table is discussed. This modified B2B mapping table will be used in HTTP Redirect approaches discussed below. Note that underlying mechanisms may partially resemble embodiments of B2B tables discussed above, and such underlying mechanisms may be repeated below for the sake of clarity.

When a Blade ID corresponding to a certain bucket changes from Blade A to Blade B, the new Blade ID (i.e., Blade B) is recorded in an additional column called a New Blade ID column. The entry in the new Blade ID (i.e. Blade B) column is moved to the (current) Blade ID column when signaled by the control plane. This may typically happen when the original Blade ID (i.e. Blade A) is no longer needed.

Use Case 1—Addition of a Blade

Considering the situation ofFIGS. 23A,23B, and23C, buckets 1 through B are initially mapped to Blades 1, 2 and 3 by the mapping shown in the table ofFIG. 23A. When the blade 4 is added to the system, Buckets 2 and 3 are remapped to Blade 4, so that the new Blade ID (i.e. Blade 4) for buckets 2 and 3 appears in the New Blade ID column ofFIG. 23B. The New blade ID (i.e. Blade 4) replaces the original blade IDs (i.e. Blade ID 1 and Blade ID 2) inFIG. 23Cresponsive to receiving a control signal from the control plane that the corresponding original Blade IDs (i.e., blade IDs 1 and 2) are no longer needed. WhileFIGS. 23B and 23Cshow blades 1 and 2 of buckets 2 and 3 are replaced with blade 4 at the same time, simultaneous replacement is not necessary.

In embodiments ofFIGS. 23A-C, a bucket may be defined to be in steady-state if the New Blade ID field corresponding to that bucket is empty. Buckets 1 and 4 inFIG. 23Bare considered to be in steady state. All buckets inFIGS. 23A and 23Care in steady state.

A bucket is defined to be in transient state if the New Blade ID field corresponding to that group is non-empty. Buckets 2 and 3 inFIG. 23Bare considered to be in transient state, and no buckets are in transient state in either ofFIG. 23Aor23B.

Use Case 2—Removal of a Blade

Considering the situation ofFIGS. 24A,24B, and24C, Buckets 1 through B are initially mapped to Blades 1, 2 and 3 as shown inFIG. 24A, and Blade 3 is being removed, for example, for scheduled maintenance. Bucket 1 which was initially being served by Blade 3 is now assigned to Blade 2. The New blade corresponding to Bucket 1 (i.e. Blade 2) is now recorded in the New Blade ID column for Bucket 1 as shown inFIG. 24B. Once a control signal is received from the control plane indicating that blade 3 is no longer needed, this change is reflected in the Blade ID column as shown inFIG. 24C. The original Blade ID (i.e. Blade 3) is recorded in the Old Blade ID column. In the example ofFIGS. 24A-C, Bucket 1 is considered to be in the transient state inFIG. 24B, while buckets 2, 3 and 4 are considered to be in steady state inFIG. 24B. All buckets are in steady state inFIGS. 24A and 24C.

Use Case 3—Reallocation of Buckets to Blades

Considering the situation ofFIGS. 25A,25B, and25C, an initial mapping between Buckets 1 through B and Blades 1, 2 and 3 is illustrated inFIG. 25A. This mapping is modified to provide load balancing (without adding or removing any blades). For example, Blade 1 may be heavily loaded relative to other blades so that some of its traffic should be offloaded to Blade 3 by reassigning Bucket 4 to Blade 3. Accordingly, the new serving blade (i.e. Blade 3) is recorded in the New Blade ID column as shown inFIG. 25B. Blade 3 then replaces Blade 1 in the (current) Blade ID column once a control signal is received from the control plane indicating that the original blade information (i.e. Blade 1) is no longer needed as shown inFIG. 25C. InFIG. 25B, Bucket 4 is considered to be in the transient state while buckets 1, 2 and 3 are considered to be in steady state. Once the control signal is received, bucket 4 switches to the steady-state as shown inFIG. 25C. InFIGS. 25A and 25C, all buckets are in the steady state.

HTTP Redirect based Approach (Approach III)

In HTTP Redirect based approaches, concepts of HTTP redirect are used for every bucket in the transient state. HTTP Redirect based approaches can also be used for gradual load correction rather than taking a whole blade into congestion collapse.

In HTTP redirect based approaches, the Load balancing site (including load balancer LB and blades/servers S1-Sn ofFIG. 6) may have a single IP address type architecture where all the servers/blades S1-Sn in the load balancing site expose a same primary virtual IP address towards the external network (including clients C1-Cm, outside server OS, etc.). In addition to the primary virtual IP address (also referred to as a primary IP address), the load balancing site also maintains an additional IP address, referred to as a stand-by virtual IP address (also referred to as a stand-by IP address). The external network is aware of the primary IP address and forwards any packets destined to this primary IP address to the load balancer. According to some embodiments, load balancer LB may separately handle any data packets that are addressed to the stand-by IP address (as opposed to the primary IP address). Load balancing operations may run at the load balancer and at individual blades/servers.

HTTP redirect based approaches may be organized into two parts, data plane operations, and control plane operations. Data plane operations may primarily handle how incoming data packets are forwarded to and received by the blades/servers assuming an instance of B2B Mapping Table at any given point in time. Control plane operations may handle maintenance and/or modification of the B2B Mapping Table residing on/at the load balancer. As discussed herein, a same primary IP address covers all of the blades/servers and a same stand-by IP address covers all of the blades/servers. A destination IP based router may be sufficient with HTTP redirect from the blades/servers with a control plane orchestrating the overall load distribution.

Data Plane Operations

As mentioned earlier, load balancing operations may run both at the load balancer and at the blades/servers. According to HTTP redirect based approaches, each blade/server also has access to the B2B mapping table that may reside on/at the load balancer.

When all blades/servers are operating in steady state, outside devices (e.g., clients C1-Cm) may transmit data packets to the system using the primary IP address. Upon receipt of data packets addressed to the primary IP address, the load balancer performs the hash function using the data flow ID of the data packet to generate a bucket ID for the data flow to which the data packet belongs, the load balancer uses the B2B mapping table to map the bucket ID to a respective current blade ID, and the load balancer forwards the data packet to the blade/server indicated by the current blade ID corresponding to the bucket ID. The blade can then process data packets received in this manner as discussed in greater detail below.

At the Blade

Operations performed at a blade/server may be used to decide whether to process or drop a data packet received from the load balancer as discussed in greater detail below with respect toFIGS. 26A-C. Moreover, each blade/server maintains a list of data flows that it is currently serving, and this list is referred to as ‘my-flows table’. An architecture of this table may be determined by the control plane, and the blade/server will accept and process data packets of data flows identified in the my-flows-table. At block2600, processor701defines/revises the my-flows-table ofFIG. 26Band the mapping table ofFIG. 26C.

When a data packet is received through LB interface703of blade/server S at block2601, processor701determines at block2603if the data packet belongs to an existing data flow being processed by the server. This determination may be made with reference to the my-flows-table by determining if a flow ID of the data packet matches any flow IDs included in the my-flows-table. If the data packet belongs to an existing data flow being processed by the server at block2603(as indicated by the my-flows-table ofFIG. 26B), processor701accepts and processes the data packet at block2615.

If the data packet does not belong to an existing data flow being processed by the server at block2603, the data packet is for a new data flow, and processor701should decide whether to accept or reject the data flow. For a data packet for a new data flow (not an existing data flow), processor701performs the hash function using the data flow ID of the data packet to determine a bucket ID to which the data flow is mapped at block2607. At block2609, processor701determines if the bucket ID is in steady state or in transient state with reference to the B2B mapping table ofFIG. 26C. As discussed above, the B2B mapping table may be maintained at the load balancer and/or used by the load balancer to map received data packets from buckets to blades/servers.

If the bucket ID is in steady state (e.g., bucket ID 1, 2, or 3 ofFIG. 26C) at block2609, processor701adds the data flow ID to the my-flows-table ofFIG. 26Bat block2611and processes the data packet at block2615.

If the bucket ID is in transient state (e.g., bucket ID 4 ofFIG. 26C) at block2609, processor701determines at block2621if the server is identified as the current blade or the new blade with reference to the B2B mapping table ofFIG. 26C. If the server is identified as the new blade for the bucket ID (e.g., new blade 3 for bucket 4 from the B2B table ofFIG. 26C), processor701adds the data flow ID to the my-flows-table ofFIG. 26Bat block2611and processes the data packet at block2615.

If the server is identified as the current blade for the bucket ID (e.g., current blade 1 for bucket 4 from the B2B table ofFIG. 26C) at block2621, processor701responds by transmitting an HTTP redirect including the stand-by IP address at block2623, and drops the data packet at block2625. The HTTP redirect will thus be transmitted when the blade/server which received the data packet is identified as the current blade for a bucket in the transient state per the B2B mapping table ofFIG. 26C.

The HTTP redirect is transmitted to the client device (e.g., client C1, C2, C3, etc.) outside of the load balancing system that originally generated the data packet that triggered the HTTP redirect. On receipt of the HTTP redirect (including the stand-by IP address), the client retransmits the data packet addressed to the stand-by IP address. Operations of load balancer will now be discussed in greater detail below with respect toFIG. 27.

At the Load Balancer

In general, the load balancer considers the packet header of a data packet and determines where to send the packet.

Data packets addressed to the stand-by IP address are transmitted to the new server/blade identified by the new Blade ID corresponding to the bucket that the packet flow belongs to. Operations at a load balancer may be summarized as follows:

A B2B (Buckets-to-Blade) mapping table is stored at the load balancer. This BTB table may be provided as discussed above with respect toFIGS. 23A-C,24A-C, and25A-C;

For every incoming data packet, the load balancer computes the hash of the Flow ID (or equivalent) to obtain the Bucket ID;

If the bucket is in the steady-state, the packet is forwarded to the Current Blade ID;

If the packet belongs to a bucket in transient state and is sent to the Stand-by IP address, the load balancer forwards the packet to the New Blade ID corresponding to the Bucket ID; and

If the packet belongs to a bucket in transient state and is sent to the Primary IP address, the load balancer forwards the packets to the (current) Blade ID corresponding to the Bucket ID.

Load balancer operations are discussed in greater detail below with respect to the flow chart ofFIGS. 27A and 27B. At block2700, processor801defines/revises the mapping table ofFIG. 27B. When a data packet is received through network interface805at block2701, processor801performs the hash function using a flow ID (or other header information) of the data packet to obtain a bucket ID to be used to process the data packet at block2703. If the bucket identified by the bucket ID of block2703is in the steady state at block2705(e.g., Bucket 2 from the B2B mapping table ofFIG. 27Bthat is stored in memory807), processor801transmits the data packet through the server interface to the current blade (e.g., blade 2 having blade ID 2 corresponding to bucket ID 3 of the B2B mapping table ofFIG. 27B). More generally, when the bucket is in steady state at block2705, the data packet is transmitted to the current server/blade for the bucket whether the data packet is addressed to the stand-by address or to the primary address.

If the bucket identified by the bucket ID of block2703is in the transient state at block2705(e.g., bucket 4 from the B2B mapping table ofFIG. 27Bthat is stored in memory807), processor801determines at block2711whether the data packet is addressed to the primary IP address or to the stand-by IP address. If the data packet is addressed to the primary IP address at block2711, processor801transmits the data packet through the server interface to the current server/blade for the bucket (e.g., server/blade 1 having blade ID 1 corresponding to bucket ID 4 of the B2B mapping table ofFIG. 27B). If the data packet is addressed to the stand-by IP address at block2711, processor801transmits the data packet through the server interface to the new server/blade assigned to the bucket (e.g., server/blade 3 having blade ID 3 corresponding to bucket ID 4 of the B2B mapping table ofFIG. 27B).

In embodiments ofFIGS. 26A-Cand27A-B, the flow ID of an original HTTP data packet to the primary IP address as well as the flow ID of the redirected HTTP data packet to the standby IP address is the same even though the destination IP address has been changed. In this approach, all data packets are transmitted as a unicast transmissions to a single server/blade. Accordingly, the load balancer may not be required to store massive tables (e.g., having a size of the order of a number of connections).

Moreover, this approach may not be limited to a single transition. For example, consider mapping as Bucket ‘x’ changes from Blade A to Blade B and then changes again from Blade B to Blade C. In this case with two transitions, two a priori advertized stand-by IP addresses may be used. Server/blade A will respond with the HTTP redirect option with the first stand-by IP address for of any data packets of new flows that corresponds to Bucket ‘x’. Load balancer will forward any packets from Bucket ‘x’ and are destined to first stand-by IP address to server/blade B whose ID will be stored in New Blade ID 1. At the same time, Bucket B will respond with HTTP redirect option with the second stand-by UP address for any data packets of new flows from Bucket ‘x’. The load balancer will forward any packets from Bucket ‘x’ that are destined to the second stand-by IP address to server/blade C whose ID will be stored in New Blade ID 2. Server/blade C will process the new flows belonging to Bucket ‘x’. Note that it is also possible that server/blade A sends the HTTP redirect option with the second stand-by IP address directly. These details may depend on corresponding control plane implementations. In summary, this approach can be generalized to any number of transitions lower than the number of available stand-by IP addresses. Moreover, this scenario may be different from each server/blade having its own IP address because of the resulting flexibility and dynamicity. In fact, it may be beneficial when a number of advertized IP addresses is smaller as compared to a number of servers/blades.

Control Plane Algorithm

In this section, control plane implementations are described. There are multiple viable ways in which the control plane may be implemented depending on the use case.

As discussed above with respect toFIGS. 23A-C,24A-C, and25A-C, a bucket enters the transient state from steady state when a New Blade ID corresponding to the bucket is added. Control plane operations may decide when the bucket can return from a current transient state to steady state. When a signal is received from the control plane indicating that the bucket is ready to return from a current transient state to a steady state, the New Blade ID replaces the original Blade ID in the B2B/Mapping Table. HTTP redirect is no longer employed by the original Blade ID (since flows from the bucket in question will no longer be sent from the original Blade ID). The control plane may thus decide when is it reasonable that the original Blade ID is no longer needed.

In an ideal scenario, the original Blade ID is no longer needed when all existing flows belonging to the bucket that were mapped to the original Blade ID have ended. In other words, the original Blade ID for bucket ‘x’ is no longer needed when the number of connections on the original blade that correspond to bucket ‘x’ goes to zero. A requirement that all data flows to the original server/blade, however, may be an unnecessarily strict criterion. A few connections may be active for a very long time, connections may be inactive but kept open for a long time, and/or FIN/FINACKs can go missing. Under such scenarios, a bucket may be in the transient state for a relatively long time resulting in continued HTTP redirect processing and/or suboptimal routing for periods of time that may be longer than desired. Accordingly, mechanisms that provide reasonable criterion to conclude that an original Blade ID for the bucket is no longer needed may be desired.

Suitable implementations of the my-flows table may assist the control plane in making these decisions. A sample implementation of the my-flows table on every blade is discussed above with respect toFIGS. 16A and 16B. The heading “Timer” refers to the time at which a last data packet from the respective data flow was received. The servers/blades can also provide a consolidated version of the my-flows-table that may assist control plane decision making. As shown inFIG. 16B, the consolidated flows table is a grouped-by-bucket-ID version of the my-flows-table.

A criterion any/or criteria may thus be defined for a server/blade to reasonably conclude that the flow of data packets from the bucket is no longer significant. One or more of the following heuristics, for example, may be used:

A number of data flows corresponding to the bucket drops below a threshold. As discussed above, a number of flows dropping to zero may be an unnecessarily stringent criterion. A number of data flows reaching a near-zero number, however, might be good enough. Care should be taken, however, when employing this heuristic. For Bucket 2 in the consolidated flows table ofFIG. 16B, for example, even though the number of data flows is relatively small (only 2), Bucket 2 may still corresponds to a significant data throughput.

A net bit-rate corresponding to the bucket dropping below a threshold may be a good reason to drop the existing flows corresponding to the bucket and release the bucket to a steady state.

A last packet received from any data flow to the bucket was a sufficiently long period of time ago. If the data flows corresponding to the bucket have been inactive for a sufficiently long period of time, the bucket may be released to the steady state without significant impact on performance.

Any combinations of the above and/or any other heuristics may also be used.

Appropriate control plane operations may be selected based on the use case. Whenever one or more (or combinations) of these criteria are met, the control plane may instruct the load balancer to replace original Blade ID for the bucket with the corresponding New Blade IDs and thereby release the bucket to the steady-state.

Additionally, a consolidated flows table can be created and maintained on/at the load balancer. The load balancer can keep track of a number of connections by incrementing or decrementing a connection counter(s) whenever it detects an outgoing SYN or FIN packet originating from one of the blades. Net bit-rates and/or last packets received of a bucket may be tracked in a similar manner. Operations/logic used to determine when to return a bucket to steady state are discussed above with respect toFIG. 22.

HTTP Redirect based approaches may provide reduced hit addition and/or removal of servers/blades.

HTTP redirect based approaches may provide increased uniformity.

Despite the fact that mapping between Flow IDs and Bucket IDs is static, the mapping between Bucket IDs and servers/blades can be changed dynamically to provide increased uniformity. This dynamic mapping may be applicable when a server/blade is added or removed, but dynamic mapping is not restricted to these use cases. For example, mechanism may be provided in which the load balancer maintains a uniformity index (e.g., a Jain's fairness index) at all times. If the uniformity index drops below a threshold, a reassignment of buckets to servers/blades may be initiated. Which buckets to reassign may depend on various parameters like number of flows corresponding to the bucket, bit-rate corresponding to the bucket, current load on the blades, blades on downtime and control parameters (such as when the last packet from the bucket was received). Approaches disclosed herein may enable a relatively smooth reassignment of buckets to servers/blades with reduced loss of data flows when such a reassignment takes place.

HTTP redirect based approaches may provide increased flow awareness, and/or HTTP redirect based approaches may support dynamicity of resources (servers/blades) by enabling addition/removal of resources (servers/blades) with reduced disruption of existing data flows.

Moreover, HTTP redirect based approaches may be implemented with relatively low complexity. With HTTP redirect base approaches, each data packet is unicast to only one server/blade. Accordingly, waste of backplane bandwidth may be reduced by reducing/eliminating multicasts of data packets to multiple servers/blades. Moreover, HTTP redirect based approaches may be implemented at the servers/blades without additional processing/operations other than responding to new data flows with an HTTP redirect option. Moreover, additional memory requirements at the load balancer and/or servers/blades may be reduced because additional flow tables may be reduced.

HTTP Redirect based approaches may work only for HTTP data traffic. Therefore, HTTP redirect based approaches may be of significant use in applications involving only HTTP traffic, but may not work for other types of application layer traffic. Because HTTP runs over TCP, HTTP redirect based approaches may only work for Type 1 data flows.

HTTP redirect is an application layer redirection method. Because the load balancer does not maintain a list of ongoing flows, every new flow from the bucket in transient state is first forwarded to the original blade which in turn forwards it to the appropriate server/blade via HTTP redirect. If the number of transitions (i.e., changes in the B2B table) and/or the number of flows are too large, significant overhead may occur at the load balancer site.

HTTP redirect based approaches may require use of Multiple IP addresses for the load balancer site. HTTP redirect based approaches discussed above may provide reduced hit support for one bucket-to-blade transition at a time using one additional IP address. If the blade corresponding to bucket changes multiple of times, additional IP addresses may be needed to support the additional transitions. Each of these IP addresses may need to be maintained at all times and advertized to the external network, thereby increasing cost. A maximum allowed number transitions per bucket may be limited to the number of stand-by IP addresses chosen.

HTTP redirect based approaches may result in multiple cascaded transients, and increased complexity of the control plane and/or an increased number of IP addresses may be needed to provide reduced hit support for data flows in the system.

Summary of Approaches

As discussed above, three different approaches may enable reduced hit addition and/or removal of servers/blades as well as reassignment of buckets to servers/blades.

Transient Multicast based Distributed Approaches may be based on the multicast of data packets that belong to a bucket in transient state. These approaches may provide a relatively low complexity load balancer without requiring significant/huge tables, but efficiency of backplane bandwidth usage may be reduced and/or additional processing on the servers/blades may be required.

Transient Table based Approaches may be based on temporarily storing data flow IDs corresponding to a bucket in transient state. These approaches may provide increased efficiency of backplane bandwidth use without requiring additional processing on the servers/blades. Additional storage and/or computation on/at the load balancer, however, may result.

HTTP Redirect based Approaches may be based on HTTP redirect of unwanted new flows. HTTP redirect based approaches may provide increased efficiency of backplane bandwidth use without requiring additional table storage. HTTP redirect based approaches, however, may work only for HTTP traffic.

Sample Implementations and Embodiments

As discussed below, embodiments of load balancing frameworks disclosed herein may be adapted to different scenarios/applications/platforms.

Implementation on a Multi-Application/Service Router (MASR) Platform (e.g., Ericsson's Smart Services Router SSR)

A Multi-Application/Service Router (MASR) Platform is a Next Generation Router aimed at providing a relatively flexible, customizable, and high throughput platform for operators. An MASR platform may provide support for a number of applications, such as, B-RAS, L2/3 PE, Multi Service Proxy, Service Aware Support Node, GGSN+MPG (SGW, PGW of LTE/4G), etc.

An MASR architecture illustrated inFIG. 28may include line cards (LCs or I/O cards) to make forwarding decisions (which correspond to load balancers of server load balancing sites discussed above), Service Cards SCs (e.g., Smart Service Cards SSCs according to some embodiments) to process application packets (which correspond servers/blades server load balancing sites discussed above), and switch cards with unicast/multicast/broadcast support (e.g. forming a backplane providing communication between the line cards and the SCs). As mentioned before, the cards (SC and LC) are interconnected through a switch fabric. The MASR platform may have other types of cards, but discussion thereof is not needed for the present disclosure.

As shown inFIG. 28, an MASR forwarding plane may provide a load balancing site. Line cards may act as load balancers, and Service Cards (SCs) may act as servers/blades. For example, an SC can act as a server to provide a service to an external UE (user equipment node), or an SC can act as a client seeking service from an external node like PCRF (Policy and Charging Rules Function). A line Card (LC) may forward data packets to one or more SCs for processing. Moreover, a line card may try to load balance between different SCs while forwarding the packets, but flow level granularity may need to be maintained. This is known as SC Traffic Steering.

SC Traffic Steering may follow a hash based implementation of a load balancer as discussed above, for example, with respect toFIG. 5. A server/blade may be a Service Card. Each service provided by an SC may be identified using a blade/server ID. Transient multicast based distributed approaches and/or transient table based approaches, as discussed above, may be used in the context of MASR. In multicast based distributed approaches, line cards may unicast or multicast the data packets based on whether the bucket is in transient state. SC cards may have to do additional work to decide whether to process the packet or drop the packet. In transient table based approaches, the line card maintains an additional transient table corresponding to each bucket in transient state and forwards the packets according to operations discussed above. Similarly, for HTTP traffic, HTTP Redirect based approaches discussed above can also be used in the context of MASR.

Embodiments for CDN (Content Delivery Network) on MASR

CDN is a significant feature of MASR that may provide subscribers access to HTTP content without having to query an original host server for every subscriber. The MASR may have multiple SC cards dedicated to CDN and there may be a need for a load balancing mechanism within those CDN SCs. Approaches of embodiments disclosed herein may be applied to carry out load balancing between different CDN SCs. More specifically, the fact that CDN traffic is HTTP only may be used. Therefore, highly advantageous HTTP Redirect based approaches may be applied to perform load balancing for CDN traffic.

Embodiments for Multi-Application on MASR and Service Chaining

Multiple Applications can be collocated at the same MASR chassis, causing certain qualifying traffic to travel to multiple applications/services within the same MASR. Thus an inter-SC load balancing may become necessary. Methods according to embodiments discussed above may cover all service chaining use cases, such that load balancing functionality may reside not only on/at the load balancer (e.g., an LC of an MASR) but also on the servers/blades as discussed above with respect toFIG. 1(e.g. SC of MASR) where the traffic can not only be load balanced from load balancers (e.g., LCs) towards the servers/blades (e.g., SCs) but also from a server/blade (e.g., SC) to another server/blade (e.g., SC).

Load balancing algorithms presented according to some embodiments of inventive concepts may have significant use cases for multi-application on MASR. Customers for CDN, TIC (Transparent Internet Caching), SASN (Service Aware Support Node), etc., are asking for a server load balancing which supports hitless ISSU (In Service Software Upgrade), hitless In service addition, and removal of Servers/SCs. Customers are interested in flexible, uniform load balancing that provides overall protection. At the same time, methods employed should desirably have low complexity, low cost, and/or low TTM (Time to Market). As discussed above, these may be advantages of some embodiments disclosed herein with respect to mechanisms used on MASR. While stateful methods for server load balancing, when implemented on a line card, may be expected to have performance issues with large state tables, embodiments disclosed herein may have reduced complexity, reduced costs, and/or increased performance. In addition, features such as energy efficient server load balancing can be performed by setting some of the servers in a sleep mode more gracefully (e.g., hitless or with reduced hits) when the load is not high.

A traffic flow may need to visit multiple servers at the same load balancing site, for example, if there are multiple services in the same load balancing site, each with multiple servers. In this case, when the traffic goes out from one of the service/server cards, the traffic may need to be load balanced again over the next service cards. In this respect, individual servers may also have a load balancer inside to perform similar load balancing as that done at the load balancer of the load balancing site.

Embodiments on Policy Based Forwarding (PBF/ACL) and Software Defined Networking Rule (SDN) Based Mechanisms.

SDN refers to separation of the control plane and the data plane where the data plane includes only a set of forwarding rules instructed by the central control plane. ACL/PBF also similarly has a control plane which sets up the set of simple forwarding rules.

In ACL/PBF, stateless hash based server load balancing may be provided using policy based forwarding (PBF) and/or Access Control List (ACL) and/or Software Defined Networking (SDN). Basically, legacy ACL/PBF/SDN data plane rules match a certain set of bits of the flow IDs (e.g., Source IP, Destination IP, Source/Destination Port, etc.) and map them statically to the servers/blades.

Transient Multicast/Broadcast Based Distributed Methods Via ACL/PBF/SDN

Assuming a set of SDN/ACL/PBF rules are set via an intelligent control plane realizing a stateless hash based server load balancing, each slice/bucket in the B2B table may be realized using an ACL/PBF/SDN rule. The action associated with each rule can be switched (e.g., by the intelligent control plane) between unicast and multicast forwarding action (e.g., sending the matching packet to a single or to multiple destinations/servers/blades) depending on whether the rule/bucket is in steady or transient state respectively. As used herein, SDN means Software Defined Networking, ACL means Access Control List, and PBF means Policy Based Forwarding.

As an example of a load balancer and/or line card implementation, inFIGS. 29 and 30, load balancer operations ofFIG. 14Aare shown as provided by ACL/PBF/SDN. (Similarly, operations ofFIG. 12Amay can be implemented.)FIG. 29illustrates an embodiment of a stateless SLB (Server Load Balancing) using a set of rules. As shown in the embodiment ofFIG. 29, all the rules/buckets may be in steady state in the sense that there is only unicast traffic forwarding action.

FIG. 30illustrates an embodiment where the control plane decided to reassign the traffic (or at least the new traffic) associated with rule 1 from the OLD Blade to a NEW blade. At that time, the action of rule one is changed from unicast to multicast, such that rule 1 sends the traffic to both the current OLD blade as well as the NEW blade. Operations on the server(s)/blade(s) may stay the same and do not need to be changed. When all the connections/flows of the OLD blade associated with Rule 1 are finished/terminated/completed, then the multicast action of Rule 1 is switched back to Unicast with the destination as the New Blade ID.

Transient Table Based Approach Via ACL/PBF/SDN

FIG. 29may still apply for a steady state case where the traffic is load balanced over multiple static rules/buckets towards the blades/servers.FIG. 31illustrates Transient Table and/or Rules for ACL/PBF/SDN according to some embodiments where the traffic to the first rule is to be reassigned to another server/blade. To achieve this in an SDN/ACL/PBF environment, the control plane may add an additional rule to the stateless side of the rules to send the initial packets of the new flows (e.g., SYN packets of the TCP traffic) to itself (i.e., the control plane, such as an OFC open flow controller). Then as the new connections/flows arrive, the control plane sets up rules per flow (which are called as stateful SLB rules in the figure) to send the new connections to the new blade. When all the old connections of the old blade are finished/terminated, then the control plane removes all the per flow (e.g., stateful) rules and removes the rule identifying the initial packets (SYN) and changes the blade ID of the original stateless rule (i.e., Rule 1's) destination to the new blade.

HTTP Redirect Method Via ACL/PBF/SDN

As can be seen from the previous two embodiments, HTTP redirect operations discussed above may be realized in an SDN/ACL/PBF environment.

Adapting to Elephant and Mice Flow Model

A significant volume of traffic in many networks (including the Internet) can be attributed to a relatively small number of data flows, known as Elephant flows. Other flows which are relatively large in number, may each consume relatively little bandwidth, and are known as Mice flows. For example, at least one study has shown that in a traffic trace, about 0.02% of all flows contributed more than 59.3% of the total traffic volume. See, Tatsuya et al., “Identifying elephant flows through periodically sampled packets,” Proceedings of the 4thACM SIGCOMM conference on Internet Measurement (IMC 2004), NY, NY, USA, 115-120. Some embodiments disclosed herein may be adapt a load balancer framework to an Elephant and Mice flow model case. A hybrid model, for example, may combine multicast based distributed approaches and transient table based approaches.

In such a hybrid model, transient table based operations may be performed for elephant flows while multicast based distributed approach operations may be performed for the mice flows. Elephant flows are relatively low in number but high in bandwidth. Accordingly, it may be easier to maintain elephant data flows in the transient table while relatively expensive to multicast them to multiple servers. Mice flows are relatively high in number. Accordingly, it may be relatively expensive to maintain a list of mice flows in the transient table but reasonable to multicast mice flows to multiple servers since they do not consume significant bandwidth. Note that this hybrid model is discussed here with respect to type 1 flows, and that concepts of a transient table may not work for type-2 flows. Details of the hybrid method are discussed below.

Operations of the hybrid method at the load balancer will now be discussed.

In the Transient Table based Approach, the load balancer maintains a table of new data flows for each bucket in the transient state (i.e., data flows that are created after the bucket enters the transient state). In this hybrid model, however, the load balancer will only maintain a list of elephant flows that are created after the bucket enters the transient state.

When a data packet arrives, the load balancer performs the hash function to determine the bucket for the data packet. If the data packet corresponds to a bucket in steady-state or is an INIT data packet of a new data flow, the packet is forwarded to the corresponding current blade. If the data packet is a non-initial data packet that corresponds to the bucket in the transient state, the load balancer checks if the packet is in the list of elephant flows corresponding to the bucket in the transient state. If the non-initial data packet is part of a data flow included in the list of elephant data flows, the load balancer forwards the data packet to the current blade. If the non-initial data packet is not part of a data flow included in the list of elephant flows, the load balancer assumes the data packet is a mice flow and multicasts the data packet to both current and old blades.

Operations of the hybrid method at the server(s)/blade(s) will now be discussed. As a packet arrives at a server/blade, the server/blade processes the data packet if the packet is unicast to the blade, and if the data packet is an INIT data packet of a new data flow, the server/blade records it in the “my-flows table”. If the data packet is received as a multicast, the server/blade checks if the packet belongs to its “my-flows table”. If yes, then the server/blade processes the packet, and if not, the server/blade drops the packet.

In addition, the servers/blades may also try to estimate whether a flow is an Elephant flow or a Mice flow. Identification of Elephant flows may already be an active research area and there may exist mechanisms by which such estimations may be performed. See, Tatsuya et al., “Identifying elephant flows through periodically sampled packets,” Proceedings of the 4thACM SIGCOMM conference on Internet Measurement (IMC 2004), NY, NY, USA, 115-120; and Yi Lu, et al., “ElephantTrap: A low cost device for identifying large flows,” High-Performance Interconnects, Symposium on, pp. 99-108, 15th Annual IEEE Symposium on High-Performance Interconnects (HOTI 2007), 2007. Once a server/blade classifies a data flow as an Elephant flow, the server/blade instructs the Load Balancer to add the Flow ID and its Blade ID to the Elephant Flow table corresponding to the transient state group. Detection of elephant flows may thus occur at the blades/servers.

The assumption here is that when a packet arrives at the load balancer, if the data packet does not belong to any flow in the elephant flow table of the load balancer, then the data packet is automatically considered as a mice flow, and the load balancer multicasts data packet of the mice flow. Then the servers/blades decide whether to process or drop the data packet based on operations described above and elephant/mice detection is also performed at the server/blade which accepted the flow. If the flow is detected as a mice flow, there is no need for further action. However, if the flow is detected as an elephant flow, then the blade/server in question manipulates the elephant flow table and from that time on, the load balancer switches to unicasting the packets belonging to that flow.

There may be advantages of this hybrid method. Since elephant flows are not multicast to multiple servers, more efficient bandwidth utilization may be provided. Only data packets of mice flows (which correspond to a relatively small fraction of the load) are sent using multicast transmissions. Therefore, this hybrid strategy may save bandwidth. Similarly, all flows are not maintained in the transient table. Only elephant flows (which are relatively small in number) are maintained in the transient table. In other words, only a relatively small amount of information is saved in the transient table on/at the load balancer. In essence, this hybrid method may combine positive elements from multicast based distributed approaches and from transient table based approaches.

The computer program instructions may also be loaded onto a computer and/or other programmable data processing apparatus to cause a series of operational steps to be performed on the computer and/or other programmable apparatus to produce a computer-implemented process such that the instructions which execute on the computer or other programmable apparatus provide steps for implementing the functions/acts specified in the block diagrams and/or flowchart block or blocks. Accordingly, embodiments of present inventive concepts may be embodied in hardware and/or in software (including firmware, resident software, micro-code, etc.) that runs on a processor such as a digital signal processor, which may collectively be referred to as “circuitry,” “a module” or variants thereof

Many different embodiments have been disclosed herein, in connection with the above description and the drawings. It will be understood that it would be unduly repetitious and obfuscating to literally describe and illustrate every combination and subcombination of these embodiments. Accordingly, the present specification, including the drawings, shall be construed to constitute a complete written description of various example combinations and subcombinations of embodiments and of the manner and process of making and using them, and shall support claims to any such combination or subcombination.

Many variations and modifications can be made to the embodiments without substantially departing from the principles of present inventive concepts. All such variations and modifications are intended to be included herein within the scope of present inventive concepts. Accordingly, the above disclosed subject matter is to be considered illustrative, and not restrictive, and the appended claims are intended to cover all such modifications, enhancements, and other embodiments, which fall within the spirit and scope of present inventive concepts. Thus, to the maximum extent allowed by law, the scope of present inventive concepts is to be determined by the broadest permissible interpretation of the following claims and their equivalents, and shall not be restricted or limited by the foregoing detailed description. Any reference numbers in the claims are provided only to identify examples of elements and/or operations from embodiments of the figures/specification without limiting the claims to any particular elements, operations, and/or embodiments of any such reference numbers.