Multipath tunneling to a service offered at several datacenters

• US 10,326,830 B1
• Filed: 09/02/2016
• Issued: 06/18/2019
• Est. Priority Date: 09/02/2016
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Singh, Bijendra
• Primary Examiner(s): Rahman, Sm A
• Application Number:
  US15/256,304
• Time in Patent Office: 1,019 Days
• Field of Search: 709223
• CPC Class Codes: H04L 12/4633 Interconnection of networks using encapsulation techniques, e.g. tunneling
• CPC Class Codes: H04L 41/0813 characterised by the conditions triggering a change of settings
• CPC Class Codes: H04L 41/0826 for reduction of network costs H04L41/0833 takes precedence
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 41/0894 Policy-based network configuration management
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/40 using virtualisation of network functions or resources, e.g. SDN or NFV entities
• CPC Class Codes: H04L 67/1004 Server selection for load balancing

Abstract

Techniques are disclosed herein regarding interfaces and multipath groups each associated with some of the interfaces to a datacenter. The techniques can include forwarding a network packet to be processed by a service, the service offered on each datacenter such that the network packet can be processed interchangeably at each datacenter. The techniques can also include, selecting one of the multipath groups for outputting of the network packet to the datacenter corresponding to the selected multipath group for processing by the service, the selecting based upon a cost to process the network packet at a respective one of the datacenters corresponding to each of the multipath groups. The techniques can further include, upon determining that the selected multipath group corresponds to a datacenter with an intervening second domain between the device and the corresponding datacenter, encapsulating the network packet for tunneling the network packet through the second domain.

Claims

1. A device, comprising:

interfaces, each configured to output network packets;

a memory storing;

multipath groups each associated with some of the interfaces, wherein each multipath group is also associated with a corresponding datacenter, each datacenter being in a first domain shared with the device; and

routing logic configured to;

determine, for each of the multipath groups, a cost to process the network packet at the datacenter corresponding to the multipath group;

rank the multipath groups according to the cost;

receive, via one of the interfaces, a network packet;

determine that the network packet is to be processed by a service offered on each of the datacenters, the service indicating that the network packet can be processed interchangeably at any of the datacenters;

select, based on a result of the ranking of the multipath groups, one of the multipath groups for forwarding of the network packet to the datacenter of the selected multipath group;

upon determining that there is an intervening second domain between the device and a datacenter of the selected multipath group, encapsulate the network packet for tunneling the network packet through the second domain, the second domain being different from the first domain; and

forward the network packet via the selected multipath group.

2. The device of claim 1, wherein the memory further stores headers, each corresponding to one of the datacenters;

and

wherein the encapsulating includes selecting a header from the stored headers that corresponds to the datacenter of the selected multipath group.

3. The device of claim 1, wherein the cost further includes a latency, a bandwidth allocation, or a monetary cost associated with each of the datacenters.

4. The device of claim 1, wherein the routing logic is implemented by a processor, application specific integrated circuit (ASIC), digital signal processor (DSP), system on a chip (SoC), field programmable gate array (FPGA), or programmable logic device (PLD).

25. The device of claim 1, wherein the ranking is also based on a cost to transport the network packet to the datacenter corresponding to each of the multipath group.

26. The device of claim 25, wherein the routing logic is configured to:

forward a first portion of the network packets to interfaces of the highest ranked multipath group; and

forward a second portion of the network packets to interfaces of the second highest ranked multipath group, the second portion being smaller than the first portion.

27. The device of claim 26, wherein the routing logic is configured to:

tunnel the first portion of the network packets through the second domain to a corresponding datacenter of the highest ranked multipath group; and

tunnel the second portion of the network packets through a third domain to a corresponding datacenter of the second highest ranked multipath group, the third domain being different from the first domain.

5. A device, comprising:

interfaces, each configured to output network packets;

a memory storing;

multipath groups each associated with some of the interfaces, wherein each multipath group is also associated with a corresponding datacenter, each datacenter being in a first domain shared with the device; and

routing logic configured to;

receive a network packet to be processed by a datacenter of the datacenters, wherein the network packet can be processed interchangeably at the each datacenter of the datacenters;

select one of the multipath groups for outputting of the network packet to the datacenter corresponding to the selected multipath group for processing, the selecting based upon a result of ranking of the multipath groups based on a respective cost to process the network packet at the corresponding datacenter of each of the multipath groups; and

upon determining that there is an intervening second domain between the device and a corresponding datacenter of the selected multipath group, encapsulate the network packet for tunneling the network packet through the second domain, the second domain being different from the first domain.

6. The device of claim 5, wherein the cost of each multipath group further includes a latency time for transporting the network packet to each of the datacenters.

7. The device of claim 5, wherein the respective cost of each multipath group includes a total bandwidth available on interfaces of each of the multipath groups to each of the datacenters.

8. The device of claim 7, wherein cost of each multipath group further includes an available bandwidth of the total bandwidth available for each of the multipath groups to each of the datacenters.

9. The device of claim 5, wherein the cost of each multipath group includes a monetary cost to process the network packet at each of the datacenters.

10. The device of claim 5, wherein in the ranking is also based on a cost to transport the network packet to the datacenter corresponding to each of the multipath groups.

11. The device of claim 10, wherein the selecting the one of the multipath groups includes selecting a multipath group having a highest rank, the highest rank indicating a lowest corresponding cost.

12. The device of claim 10, wherein the selecting the one of the multipath groups includes load balancing the forwarding of the network packets across the multipath groups based on the cost of each multipath group, wherein the load balancing distributes the network packets for processing by the datacenters corresponding to the multipath groups.

13. The device of claim 10, wherein each of the ranked multipath groups corresponds to a portion of a hash range, wherein the selecting the one of the multipath groups includes generating a hash value and determining which portion of the hash range the hash value falls within;

and

wherein the routing logic is further configured to, upon determining that a datacenter is unavailable, reallocate the portion of the hash range corresponding to the unavailable datacenter to the multipath groups corresponding to available datacenters.

14. The device of claim 5, wherein the routing logic is further configured to, upon determining that the selected multipath group corresponds to a datacenter without an intervening network domain between the device and the datacenter, forward the network packet via the selected multipath group for processing without encapsulating the network packet for tunneling.

15. The device of claim 5, wherein the encapsulating includes selecting a header from a plurality of headers, each of the plurality of headers corresponding to a respective datacenter to tunnel the network packet to the respective datacenter.

21. The device of claim 5, wherein each multipath group includes a plurality of interfaces of the interfaces configured to forward at least some of the network packets to the corresponding datacenter.

22. The device of claim 5, wherein the tunneling the network packet through the second domain comprises transmitting the network packet through the second domain such that the second domain is unaware that the transmission is for the first domain.

23. The device of claim 10, wherein the routing logic is configured to:

forward a first portion of the network packets to interfaces of the highest ranked multipath group; and

forward a second portion of the network packets to interfaces of the second highest ranked multipath group, the second portion being smaller than the first portion.

24. The device of claim 23, wherein the routing logic is configured to:

tunnel the first portion of the network packets through the second domain to a corresponding datacenter of the highest ranked multipath group; and

tunnel the second portion of the network packets through a third domain to a corresponding datacenter of the second highest ranked multipath group, the third domain being different from the first domain.

16. A method, comprising:

receiving, by a device, a network packet to be processed by a service offered by datacenters such that the network packet can be processed at any of the datacenters, wherein each datacenter shares a first domain with the device;

determining, based on a cost associated with each datacenter, a ranking of the datacenters;

selecting, based on the ranking of the datacenters, one of a plurality of multipath groups, each multipath group associated with a corresponding one of the datacenters;

upon determining that there is an intervening second domain between the device and the corresponding datacenter of the selected multipath group, encapsulating the network packet for tunneling the network packet through the second domain, the second domain being different from the first domain; and

forwarding the network packet to the datacenter corresponding the selected one multipath group for processing by the service.

17. The method of claim 16, further comprising selecting a header from a plurality of headers, the selected header for the encapsulating the network packet for tunneling.

18. The method of claim 16, wherein the ranking is further based on at least one of a latency, a processing time, a bandwidth, or a monetary cost associated with each of the datacenters.

19. The method of claim 18, wherein the selecting the one multipath group includes selecting the one multipath group having the lowest cost, the cost including the latency and the processing time.

20. The method of claim 18, wherein the selecting the one multipath group includes selecting the one multipath group to load balance resources of the datacenters.

28. The method of claim 16, wherein the ranking is also based on a cost to transport the network packet to the datacenter corresponding to each of the multipath group.

29. The method of claim 28, further comprising:

forwarding a first portion of the network packets to interfaces of the highest ranked multipath group; and

forwarding a second portion of the network packets to interfaces of the second highest ranked multipath group, the second portion being smaller than the first portion.

30. The method of claim 29, further comprising:

tunneling the first portion of the network packets through the second domain to a corresponding datacenter of the highest ranked multipath group; and

1. tunneling the second portion of the network packets through a third domain to a corresponding datacenter of the second highest ranked multipath group, the third domain being different from the first domain.