Method for providing sticky load balancing

Patent metadata

Field	Value
Publication number	US-9992103-B2
Application number	US-201414162954-A
Country	US
Kind code	B2
Filing date	Jan 24, 2014
Priority date	Jan 24, 2014
Publication date	Jun 5, 2018
Grant date	Jun 5, 2018

Abstract

Presented herein are techniques to reduce the number of redirected subscriber packet flows while performing sticky hierarchical load balancing. An Nth head end network element may be activated such that a plurality of N head end network elements are active and capable of receiving and processing one or more packet flows. A primary load balancer may then be directed to overwrite a portion of pointers of a hash table in an evenly distributed manner with pointers to the Nth head end network element such that packet flows are forwarded to the Nth head end network element, wherein the hash table retains a static number of entries as the number of head end network elements is modified.

First claim

What is claimed is:

1. A method comprising:
in a network having N−1 head end network elements, activating a new head end network element such that the new head end network element is one of N head end network elements that are active and capable of receiving and processing one or more packet flows, where N is greater than two; and
directing a primary load balancer to overwrite a portion of pointers of a hash table in an evenly distributed manner with one or more pointers to the new head end network element such that packet flows are forwarded to the new head end network element, wherein the hash table includes pointers for a plurality of head end network elements and retains a static number of entries as the number of head end network elements is modified, and wherein the static number of entries is greater than N;
wherein directing includes directing the primary load balancer to overwrite every Nth entry in the hash table with a pointer to the new head end network element, such that packet flows are forwarded to the new head end network element.

2. The method of claim 1 , wherein each of the N head end network elements is a secondary load balancer configured to classify the one or more packet flows for distribution to one or more service chains associated with a head end network element and configured to forward data packet flows to the one or more service chains associated with the head end network element, and further comprising acquiring state information only from one or more service chains associated with overwritten hash table entries and providing the state information to the new head end network element.

3. The method of claim 1 , further comprising:
detecting that an association between a given data packet flow and a first head end network element has been changed to an association between the given packet flow and a second head end network element;
in response to detecting that the association has changed, acquiring state information from a first service chain formerly associated with the first head end network element; and
providing the state information to a second service chain associated with the second head end network element.

4. The method of claim 1 , wherein the hash table includes a plurality of pointers to a first head end network element, and further comprising:
detecting a failure of the first head end network element from the N head end network elements; and
directing the primary load balancer to overwrite in the hash table a first occurrence of a pointer to the first head end network element, and every Nth entry in the hash table after the first occurrence, with a pointer to a second head end network element such that packet flows are forwarded to the second head end network element.

5. The method of claim 4 , further comprising:
in response to detecting the failure, acquiring state information from a first service chain associated with the first head end network element; and
providing the state information to a second service chain associated with the second head end network element.

6. The method of claim 1 , wherein the hash table includes a plurality of pointers to each of the N head end network elements, and further comprising:
removing a head end network element from the N head end network elements; and
directing the primary load balancer to overwrite every Nth entry in the hash table, beginning with a first occurrence of a pointer to the removed head end network element, with a pointer that does not point to the removed head end network element, such that only pointers to N−1 head end network elements remain.

7. The method of claim 1 , wherein the hash table includes a plurality of pointers for each head end network element.

8. An apparatus comprising:
a plurality of network ports;
a network interface unit coupled to the plurality of network ports;
a processor coupled to the network interface unit, and configured to:
in a network having N−1 head end network elements, activate a new head end network element such that the new head end network element is one of N head end network elements that are active and capable of receiving and processing one or more packet flows, where N is greater than one two; and
direct a primary load balancer to overwrite a portion of pointers of a hash table in an evenly distributed manner with one or more pointers to the new head end network element such that packet flows are forwarded to the new head end network element, wherein the hash table includes pointers for a plurality of head end network elements and retains a static number of entries as the number of head end network elements is modified, and wherein the static number of entries is greater than N;
wherein the processor is further configured to direct the primary load balancer to overwrite every Nth entry in the hash table with a pointer to the new head end network element, such that packet flows are forwarded to the new head end network element.

9. The apparatus of claim 8 , wherein each of the N head end network elements is a secondary load balancer configured to classify the one or more packet flows for distribution to one or more service chains associated with a head end network element and configured to forward data packet flows to the one or more service chains associated with the head end network element, and wherein the processor is configured to acquire state information only from one or more service chains associated with overwritten hash table entries and provide the state information to the new head end network element.

10. The apparatus of claim 8 , wherein the processor is further configured to:
detect that an association between a given data packet flow and a first head end network element has been changed to an association between the given packet flow and a second head end network element;
in response to detecting that the association has changed, acquire state information from a first service chain formerly associated with the first head end network element; and
provide the state information to a second service chain associated with the second head end network element.

11. The apparatus of claim 8 , wherein the hash table includes a plurality of pointers to a first head end network element, and wherein the processor is further configured to:
detect a failure of the first head end network element from the N head end network elements; and
direct the primary load balancer to overwrite in the hash table a first occurrence of a pointer to the first head end network element, and every Nth entry in the hash table after the first occurrence, with a pointer to a second head end network element such that packet flows are forwarded to the second head end network element.

12. The apparatus of claim 11 , wherein the processor is further configured to:
in response to detecting the failure, acquire state information from a first service chain associated with the first head end network element; and
provide the state information to a second service chain associated with the second head end network element.

13. The apparatus of claim 8 , wherein the hash table includes a plurality of pointers to each of the N head end network elements, and wherein the processor is configured to:
remove a head end network element from the N head end network elements; and
direct the primary load balancer to overwrite every Nth entry in the hash table, beginning with a first occurrence of a pointer to the removed head end network element, with a pointer that does not point to the removed head end network element, such that only pointers to N−1 head end network elements remain.

14. The apparatus of claim 8

Assignees

• Cisco Tech Inc

Inventors

• Bosch Hendrikus G P
• Weinberger Peter
• Bhagwatula Praveen
• Lipman Michael E
• Duminuco Alessandro
• Samuel Louis Gwyn

Classifications

• H04W24/02 Primary

  Arrangements for optimising operational condition · CPC title

• H04L45/38 Primary

  Flow based routing · CPC title