Packet path selection using shuffle sharding

Patent metadata

Field	Value
Publication number	US-9722932-B1
Application number	US-201414526410-A
Country	US
Kind code	B1
Filing date	Oct 28, 2014
Priority date	Oct 28, 2014
Publication date	Aug 1, 2017
Grant date	Aug 1, 2017

Abstract

A path selector device of a network receives a network packet. A packet flow category to which the packet belongs is identified. A candidate outbound link set corresponding to the packet flow category, comprising a subset of the available outbound links of the path selector device, is determined. The packet is transmitted on a particular outbound link of the candidate outbound link set. Subsequent packets of the packet flow category are distributed among the members of the candidate outbound link set.

First claim

What is claimed is:

1. A system, comprising:
a plurality of path selectors of a network, including a particular path selector from which a plurality of outbound links are available for transmitting network packets received at the particular path selector;
wherein the particular path selector is configured to:
receive or determine a mapping between a plurality of packet flow categories and a plurality of candidate outbound link sets of the particular path selector, wherein the mapping indicates respective numbers of outbound links corresponding to respective candidate outbound link sets (COLS), wherein the respective numbers of outbound links are determined based at least in part on characteristics of the network, and wherein the respective numbers of outbound links are smaller than a number of the plurality of outbound links available from the particular path selector;
identify, based at least in part on one or more headers of a particular network packet received from a particular traffic source and directed to a particular traffic destination, a first packet flow category (PFC) to which the particular network packet belongs;
determine, based at least in part on the mapping between the plurality of packet flow categories and the plurality of candidate outbound link sets, the first COLS mapped to the first PFC, wherein the first COLS includes at least a first outbound link of a first path to the particular traffic destination and a second outbound link of a second path to the particular traffic destination;
select a particular outbound link of the first COLS on which the particular network packet is to be transmitted from the particular path selector;
transmit the particular network packet on the particular outbound link; and
subsequent to a determination that a different network packet received at the particular path selector belongs to the first PFC,
select another outbound link of the first COLS based at least on the other outbound link of the first COLS being different than the particular outbound link of the first COLS, wherein the different network packet is to be transmitted on the other outbound link of the first COLS; and
transmit the different network packet on the other outbound link.

2. The system as recited in claim 1 , wherein the mapping between the PFCs and the COLs is based on fault isolation characteristics of the network and on the workload balance of traffic over the network, and wherein the plurality of path selectors is arranged in one of: a fat tree topology, a VL2 (Virtual Layer 2) topology, a BCube topology, or a different Clos topology.

3. The system as recited in claim 1 , wherein the particular path selector is further configured to:
determine that another network packet received at the particular path selector belongs to a second PFC;
identify a second COLS corresponding to the second PFC, wherein at least one outbound link of the second COLS is also included in the first COLS and at least one outbound link of the second COLS is not included in the first COLS; and
transmit the other network packet on an outbound link of the second COLS.

4. The system as recited in claim 1 , wherein the particular path selector comprises a network switch device, wherein the number of outbound links available from the particular path selector is no greater than a number of output ports of the network switch device.

5. The system as recited in claim 1 , wherein the particular path selector is further configured to determine at least one of: (a) the first PFC, (b) the first COLS, or (c) the particular outbound link using a parameter stored in a configuration file accessible from the particular path selector.

6. A method, comprising:
performing, by a particular path selector of a plurality of path selectors of a network, wherein a plurality of outbound links are available for transmitting network packets received at the particular path selector:
identifying, in response to receiving a particular network packet from a particular traffic source and directed to a particular traffic destination, a first packet flow category (PFC) to which the particular network packet belongs;
determining a candidate outbound link set (COLS) corresponding to the first PFC, wherein the COLS includes at least a first outbound link and a second outbound link, wherein the COLS includes a number of outbound links that is based at least in part on a probability of a network failure between a particular source and a particular destination, and wherein the number of outbound links included in the COLS is smaller than a number of outbound links available from the particular path selector;
transmitting the particular network packet on a selected outbound link of the COLS.

7. The method as recited in claim 6 , wherein the particular path selector comprises a network switch device, wherein the number of outbound links available from the particular path selector is no greater than a number of output ports of the network switch device, and wherein the number of outbound links is based at least in part on a balance between the probability of a network failure between the particular source and the particular destination and a level of network workload distribution.

8. The method as recited in claim 6 , wherein the network comprises a plurality of switch tiers including a first tier and a second tier, wherein the particular path selector comprises a first network switch device at the first tier, and wherein the first outbound link connects the first network switch device to a second network switch device of the second tier.

9. The method as recited in claim 6 , wherein a virtualization management component of a particular instance host of a provider network comprises the particular path selector, wherein the number of outbound links available from the particular path selector corresponds to a number of virtual network interfaces associated with a network intermediary reachable from the particular instance host.

10. The method as recited in claim 6 , wherein the number of outbound links included in the COLS is based at least in part on one or more of: (a) a fault isolation goal or (b) a load balancing goal.

11. The method as recited in claim 6 , further comprising:
assigning, by the particular path selector to a different network packet received at the particular path selector, a label indicating a plurality of network links over which the different network packet is to be transmitted sequentially, wherein the plurality of network links includes the first outbound link, wherein the first outbound link connects the particular path selector to a different path selector; and
forwarding, by the different path selector, the different network packet along a particular outbound link indicated in the label.

12. The method as recited in claim 6 , wherein said identifying the first PFC is based at least in part on examining one or more headers of the particular network packet.

13. The method as recited in claim 12 , wherein the one or more headers include one or more of: (a) a source address header, (b) a destination address header, (c) a source port, (d) a destination port, (e) a source media access control (MAC) address, or (f) a destination MAC address.

14. The method as recited in claim 6 , wherein said identifying the first PFC is based at least in part on a value of a link polarization prevention factor.

15. The method as recited in claim 6 , further comprising:
identifying, by the particular path selector from among the outbound links of the COLS, a particular outbound link on which the particular network packet is to be transmitted, whe

Assignees

• Amazon Tech Inc

Inventors

• Brandwine Eric Jason

Classifications

• H04L47/2441 Primary

  relying on flow classification, e.g. using integrated services [IntServ] · CPC title

• H04L45/74

  Address processing for routing · CPC title

• H04L47/125

  by balancing the load, e.g. traffic engineering · CPC title