Methods and apparatus for implementing anycast flow stickiness in stateful sessions

• US 9,363,102 B1
• Filed: 12/21/2010
• Issued: 06/07/2016
• Est. Priority Date: 12/21/2010
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Brandwine, Eric J., Sivasubramanian, Swaminathan, Marshall, Bradley E., Certain, Tate Andrew
• Primary Examiner(s): Christensen, Scott B
• Assistant Examiner(s): Do, Lam
• Application Number:
  US12/975,292
• Time in Patent Office: 1,995 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: H04L 12/4633 Interconnection of networks using encapsulation techniques, e.g. tunneling
• CPC Class Codes: H04L 12/54 Store-and-forward switching systems packet switching systems H04L45/00, H04L47/00
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 45/586 of virtual routers
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 47/825 Involving tunnels, e.g. MPLS
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming
• CPC Class Codes: H04L 61/2592 using tunnelling or encapsulation
• CPC Class Codes: H04L 63/0236 Filtering by address, protocol, port number or service, e.g. IP-address or URL
• CPC Class Codes: H04L 63/0272 Virtual private networks

Abstract

Methods and apparatus for implementing anycast flow stickiness in stateful sessions are described. For the first packet from a source device to an anycast group, a destination anycast endpoint is selected from the anycast group by a routing process via an algorithm that is specified for the anycast group. A record of the mapping of the source device to the destination anycast endpoint may be stored. Additional packets in the flow are routed to the same anycast endpoint as the first packet according to the stored information. Alternatively, a hashing technique may be used to route packets to an anycast endpoint. The packets may be encapsulated in an encapsulation format that includes network substrate routing information to the destination anycast endpoint; anycast forwarding decisions are made at the overlay network level and not at the network substrate level, and thus flow stickiness can be maintained.

Claims

1. An overlay network device on a network, comprising:

at least one processor; and

a memory comprising program instructions, wherein the program instructions are executable by the at least one processor to;

receive an initial packet from an endpoint on a source device;

determine that the initial packet is directed to an anycast group on the network, wherein the anycast group comprises a plurality of anycast group endpoints that all publish the same anycast address;

determine one of the plurality of anycast group endpoints as a destination anycast endpoint for the initial packet;

store flow information for a session between the endpoint on the source device and the anycast group, wherein the flow information maps the endpoint on the source device to the determined destination anycast endpoint;

subsequent to determining the one of the plurality of anycast group endpoints as the determined destination anycast endpoint for the initial packet, encapsulate the initial packet according to an overlay network encapsulation format to form an overlay network packet, wherein the overlay network encapsulation format includes an overlay IP address of a host device that hosts the determined destination anycast endpoint, and forward the overlay network packet to the determined destination anycast endpoint on the network;

receive one or more additional packets from the endpoint on the source device; and

forward the one or more additional packets to the determined destination anycast endpoint on the network according to the stored flow information for the session between the endpoint on the source device and the anycast group;

wherein at least the initial packet is forwarded from the overlay network device to the determined destination anycast endpoint on the network according to the overlay IP address of the host device included in the overlay network packet and thus without anycast forwarding decisions being made at the network substrate level.

2. The overlay network device as recited in claim 1, wherein the network implements an overlay network on the network substrate, wherein packets on the overlay network are encapsulated by overlay network devices according to the overlay network encapsulation format for routing the packets to and from overlay network addresses of the overlay network.

3. The overlay network device as recited in claim 1, wherein, to determine that the packet is directed to an anycast group on the network, the program instructions are executable by the at least one processor to intercept and examine the packet to determine that the packet is directed to the anycast address of the respective anycast group.

4. The overlay network device as recited in claim 1, wherein, to determine one of the plurality of anycast group endpoints as a destination anycast endpoint for the initial packet, the program instructions are executable by the at least one processor to:

in response to determining that the initial packet is directed to the anycast group, obtain anycast information for the anycast group, wherein the anycast information includes an indication of an algorithm for selecting an anycast group endpoint from among the plurality of anycast group endpoints in the anycast group; and

determine the one of the plurality of anycast group endpoints as the destination anycast endpoint according to the indicated algorithm.

5. The overlay network device as recited in claim 4, wherein the algorithm for selecting an anycast group endpoint is one of a load-balancing algorithm, a round robin algorithm, a least cost algorithm, a nearest algorithm, a lowest response time algorithm, or an algorithm that evaluates an indication of endpoint availability.

6. The overlay network device as recited in claim 1, wherein, to determine one of the plurality of anycast group endpoints as a destination anycast endpoint for the initial packet, the program instructions are executable by the at least one processor to examine only flow state information related to flows seen by the respective overlay network device to determine the destination anycast endpoint.

7. The overlay network device as recited in claim 4, wherein, to obtain anycast information for the anycast group, the program instructions are executable by the at least one processor to query a mapping service for the network, wherein the mapping service obtains, stores, and distributes network address information, including anycast group information, for the network.

8. The overlay network device as recited in claim 4, wherein the anycast information further includes two or more network addresses for host devices on the network that each host at least one of the anycast group endpoints on the network.

9. The overlay network device as recited in claim 8, wherein, in said forwarding the overlay network packet to the determined destination anycast endpoint on the network, the overlay network packet is forwarded to the host device that hosts the determined destination anycast endpoint according to the overlay IP address of host device in the overlay network packet.

10. The overlay network device as recited in claim 1, wherein, in said forwarding the overlay network packet to the determined destination anycast endpoint on the network, the overlay network packet is forwarded to a host device on the network that hosts the determined destination anycast endpoint.

11. The overlay network device as recited in claim 1, wherein, to forward the one or more additional packets to the determined destination anycast endpoint on the network according to the stored flow information for the session between the endpoint on the source device and the anycast group, the program instructions are executable by the at least one processor to, for each of the one or more additional packets received from the endpoint on the source device:

determine that the respective packet is directed to the anycast group on the network;

encapsulate the respective packet according to the overlay network encapsulation format to form a respective overlay network packet; and

forward the respective overlay network packet to the determined destination anycast endpoint on the network according to the stored flow information for the session between the endpoint on the source device and the anycast group.

12. The overlay network device as recited in claim 1, wherein the initial packet is a stateful protocol packet.

13. The overlay network device as recited in claim 12, wherein the stateful protocol is Transmission Control Protocol (TCP).

14. The overlay network device as recited in claim 1, wherein the network is a hardware virtualization network that includes a plurality of host devices each implementing one or more virtual machines (VMs), wherein each of the plurality of anycast group endpoints corresponds to a different one of the VMs on the plurality of host devices.

15. The overlay network device as recited in claim 14, wherein the endpoint on the source device corresponds to one of the VMs on one of the plurality of host devices, and wherein the overlay network device is one of the host devices.

16. The overlay network device as recited in claim 14, wherein the source device is external to the network.

17. A method, comprising:

receiving, by an overlay network device on a network, an initial packet from an endpoint on a source device;

determining, by the overlay network device, that the initial packet is directed to an anycast group on the network, wherein the anycast group comprises a plurality of anycast group endpoints that all publish the same anycast address;

determining, by the overlay network device, one of the plurality of anycast group endpoints as a destination anycast endpoint for the initial packet;

storing flow information for a session between the endpoint on the source device and the anycast group, wherein the flow information maps the endpoint on the source device to the determined destination anycast endpoint;

subsequent to said determining one of the plurality of anycast group endpoints as the determined destination anycast endpoint for the initial packet, encapsulating the initial packet according to an overlay network encapsulation format to form an overlay network packet, wherein the overlay network encapsulation format includes an overlay network address of a host device that hosts the determined destination anycast endpoint, and forwarding the overlay network packet to the determined destination anycast endpoint on the network;

receiving one or more additional packets from the endpoint on the source device; and

forwarding the one or more additional packets to the determined destination anycast endpoint on the network according to the stored flow information for the session between the endpoint on the source device and the anycast group;

wherein the initial packet is forwarded from the overlay network device to the determined destination anycast endpoint on the network according to the overlay IP address of the host device included in the overlay network packet and thus without anycast forwarding decisions being made at the network substrate level.

18. The method as recited in claim 17, wherein the network implements an overlay network on the network substrate, wherein packets on the overlay network are encapsulated by overlay network devices according to the overlay network encapsulation format for routing the packets to and from overlay network addresses of the overlay network.

19. The method as recited in claim 17, wherein said determining, by the overlay network device, one of the plurality of anycast group endpoints as a determined destination anycast endpoint for the initial packet comprises:

in response to determining that the initial packet is directed to the anycast group, obtaining, by the overlay network device, anycast information for the anycast group, wherein the anycast information includes an indication of an algorithm for selecting an anycast group endpoint from among the plurality of anycast group endpoints in the anycast group; and

determining, by the overlay network device, the one of the plurality of anycast group endpoints as the determined destination anycast endpoint according to the indicated algorithm.

20. The method as recited in claim 19, wherein the algorithm for selecting an anycast group endpoint is one of a load-balancing algorithm, a round robin algorithm, a least cost algorithm, a nearest algorithm, a lowest response time algorithm, or an algorithm that evaluates an indication of endpoint availability.

21. The method as recited in claim 19, wherein said obtaining, by the overlay network device, anycast information for the anycast group comprises the overlay network device querying a mapping service for the network, wherein the mapping service obtains, stores, and distributes network address information, including anycast group information, for the network.

22. The method as recited in claim 19, wherein the anycast information further includes two or more network addresses for host devices on the network that each host at least one of the anycast group endpoints on the network, and wherein said forwarding the overlay network packet to the determined destination anycast endpoint on the network comprises forwarding the overlay network packet to one of the two or more host devices on the network that hosts the determined destination anycast endpoint.

23. The method as recited in claim 17, wherein said forwarding the one or more additional packets to the determined destination anycast endpoint on the network according to the stored flow information for the session between the endpoint on the source device and the anycast group comprises, for each of the one or more additional packets received by the overlay network device from the endpoint on the source device:

determining that the respective packet is directed to the anycast group on the network;

encapsulating the respective packet according to the overlay network encapsulation format to form a respective overlay network packet; and

forwarding the respective overlay network packet to the determined destination anycast endpoint on the network according to the stored flow information for the session between the endpoint on the source device and the anycast group.

24. The method as recited in claim 17, wherein the initial packet is a stateful protocol packet.

25. A non-transitory computer-accessible storage medium, storing program instructions, wherein the program instructions are computer-executable to implement:

receiving an initial packet from an endpoint on a source device;

determining that the initial packet is directed to an anycast group implemented on a hardware virtualization network, wherein the anycast group comprises a plurality of anycast group endpoints that all publish the same anycast address, and wherein the hardware virtualization network includes a plurality of host devices each providing one or more virtual resources, wherein each of the plurality of anycast group endpoints corresponds to a different one of the virtual resources on the plurality of host devices;

determining one of the plurality of anycast group endpoints as a destination anycast endpoint for the initial packet;

subsequent to determining one of the plurality of anycast group endpoints as the determined destination anycast endpoint for the initial packet, encapsulating the initial packet according to an overlay network encapsulation format to form an overlay network packet, wherein the overlay network encapsulation format includes an overlay network address of a host device of the plurality of host devices that hosts the determined destination anycast endpoint; and

forwarding the overlay network packet to the determined destination anycast endpoint on the hardware virtualization network;

wherein the initial packet is forwarded to the determined destination anycast endpoint on the hardware virtualization network according to the overlay network address of the host device included in the overlay network packet and thus without anycast forwarding decisions being made at the network substrate level.

26. The non-transitory computer-accessible storage medium as recited in claim 25, wherein the hardware virtualization network implements an overlay network on the network substrate, wherein packets on the overlay network are encapsulated by overlay network devices according to the overlay network encapsulation format for routing the packets to and from overlay network addresses of the overlay network.

27. The non-transitory computer-accessible storage medium as recited in claim 25, wherein, in said determining one of the plurality of anycast group endpoints as a destination anycast endpoint for the initial packet, the program instructions are computer-executable to implement:

obtaining anycast information for the anycast group from a mapping service for the hardware virtualization network, wherein the anycast information includes an indication of an algorithm for selecting an anycast group endpoint from among the plurality of anycast group endpoints in the anycast group; and

determining the one of the plurality of anycast group endpoints as the determined destination anycast endpoint according to the indicated algorithm.

28. The non-transitory computer-accessible storage medium as recited in claim 27, wherein the algorithm for selecting an anycast group endpoint is one of a load-balancing algorithm, a round robin algorithm, a least cost algorithm, a nearest algorithm, a lowest response time algorithm, or an algorithm that evaluates an indication of endpoint availability.

29. The non-transitory computer-accessible storage medium as recited in claim 27, wherein the anycast information further includes two or more network addresses for host devices on the hardware virtualization network that each host at least one of the anycast group endpoints on the hardware virtualization network, and wherein, in said forwarding the overlay network packet to the determined destination anycast endpoint on the hardware virtualization network, the program instructions are computer-executable to implement forwarding the overlay network packet to one of the two or more host devices on the hardware virtualization network that hosts the determined destination anycast endpoint.

30. The non-transitory computer-accessible storage medium as recited in claim 25, wherein the program instructions are computer-executable to implement:

storing flow information for a session between the endpoint on the source device and the anycast group, wherein the flow information maps the endpoint on the source device to the determined destination anycast endpoint; and

for each of one or more additional packets received by the overlay network device from the endpoint on the source device;

determining that the respective packet is directed to the anycast group on the hardware virtualization network;

encapsulating the respective packet according to the overlay network encapsulation format to form a respective overlay network packet; and

forwarding the respective overlay network packet to the determined destination anycast endpoint on the hardware virtualization network according to the stored flow information for the session between the endpoint on the source device and the anycast group.

31. The non-transitory computer-accessible storage medium as recited in claim 25, wherein, in said determining one of the plurality of anycast group endpoints as a destination anycast endpoint for the initial packet, the program instructions are computer-executable to implement:

applying a hash function to source address and destination address information in the initial packet, wherein the initial packet is a first packet in a flow; and

applying a portion of results of the hash function as an index to determine the one of the plurality of anycast group endpoints as a destination anycast endpoint for the initial packet in the flow;

wherein the program instructions are further computer-executable to implement applying the hash function to additional packets in the flow from the source endpoint to the anycast group and applying a portion of results of the hash function as an index to route the additional packets in the flow to the same anycast group endpoint as the initial packet in the flow.

32. The non-transitory computer-accessible storage medium as recited in claim 25, wherein the endpoint on the source device corresponds to one of the resources on one of the plurality of host devices on the hardware virtualization network, and wherein the overlay network device is one of the host devices.

33. The non-transitory computer-accessible storage medium as recited in claim 25, wherein the source device is external to the hardware virtualization network.

34. The non-transitory computer-accessible storage medium as recited in claim 25, wherein the virtual resources include virtual machines (VMs) implemented on the host devices.

35. The non-transitory computer-accessible storage medium as recited in claim 25, wherein the initial packet is a stateful protocol packet.