Multi-tier stateful network flow management architecture

• US 9,998,955 B1
• Filed: 06/10/2015
• Issued: 06/12/2018
• Est. Priority Date: 06/10/2015
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: MacCarthaigh, Colm
• Primary Examiner(s): Phunkulh, Bob
• Application Number:
  US14/736,163
• Time in Patent Office: 1,098 Days
• Field of Search: None
• CPC Class Codes: H04L 12/16 Arrangements for providing special services to substations
• CPC Class Codes: H04L 45/74 Address processing for routing
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 65/611 for multicast or broadcast systems for broadcast or conference H04L12/18; arrangements for broadcast or distribution combined with broadcast H04H20/00; arrangements for broadcast applications with a direct linkage to broadcast information or to broadcast space-time H04H60/00; selective distribution of broadcast services, e.g. multimedia broadcast multicast service [MBMS], H04W4/06
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

A packet transformation node of a multi-tier flow management system receives a packet of a particular network flow. The packet transformation node produces a modified version of the packet with changes to one or more header elements based on a rewrite entry generated at a rewriting decisions tier of the system, and transmits the modified version to a destination. A rewriting decisions node of the system generates rewrite entries corresponding to various packet processing requirements, based at least partly on state information regarding various flows for which rewriting entries have already been generated.

Claims

1. A method, comprising:

receiving, at a packet transformation tier of a stateful network flow management service of a provider network, a particular network packet of a particular network flow, wherein the particular network flow is distinguishable from other network flows by a combination of one or more of;

a network protocol, a transmission direction, a source network address, a source network port, a destination network address or a destination network port;

generating, at a rewriting decisions tier of the stateful network flow management service, a rewrite entry indicating transformations to be applied to a plurality of network packets of the particular network flow in accordance with a packet processing requirement of a client;

modifying, at the packet transformation tier in accordance with the rewrite entry, one or more header elements of the particular network packet;

transmitting, from the packet transformation tier, a transformed version of the particular network packet resulting from said modifying to a destination network address indicated in the transformed version;

updating, at a flow state tracking tier of the stateful network flow management service, a flow state record corresponding to the particular network flow;

transmitting, from the flow state tracking tier to the rewriting decisions tier, a representation of one or more flow state records corresponding to respective active network flows including the particular network flow; and

generating, at the rewriting decisions tier based at least in part on the representation of the one or more flow state records, at least one additional rewrite entry corresponding to a different network flow.

2. The method as recited in claim 1, wherein said generating the rewrite entry at the rewriting decisions tier is responsive to receiving an indication at the rewriting decisions tier of a cache miss at a particular rewrite entry cache of the packet transformation tier, further comprising:

storing the rewrite entry in the particular rewrite entry cache;

determining, after said storing, that the rewrite entry stored in the particular rewrite entry cache is applicable to a different packet received at the packet transformation tier, wherein the different packet is part of the particular network flow; and

modifying, at the packet transformation tier, one or more headers of the different packet based at least in part on the rewrite entry.

3. The method as recited in claim 1, further comprising:

replicating, at a plurality of nodes of the rewriting decisions tier, the rewrite entry prior to said modifying the one or more header elements at the packet transformation tier.

4. The method as recited in claim 1, further comprising:

receiving, at a control-plane component of the stateful network flow management service via a programmatic interface, an indication of the packet processing requirement of a client;

selecting, from among a plurality of nodes of the packet transformation tier, a subset of nodes to be used for operations corresponding to the packet processing requirement; and

providing, to the client, an indication of one or more network addresses associated with the packet processing requirement.

5. The method as recited in claim 1, further comprising:

selecting, at a particular node of the packet transformation tier based at least in part on a first health state update message received at the particular node, a first target node of the flow state tracking tier with respect to the particular network packet flow; and

selecting, at the first target node of the flow state tracking tier based at least in part on a second health state update message received at the target node, a second target node of the rewriting decisions tier with respect to at least the particular network packet flow.

6. A multi-tier network flow management system implemented at one or more computing devices, comprising:

one or more nodes of a packet transformation tier; and

one or more nodes of a rewriting decisions tier;

wherein the one or more nodes of the packet transformation tier are configured to;

receive a particular network packet of a particular network flow, wherein the particular network flow is distinguishable from other network flows by a combination of one or more of;

a network protocol, a source network address, a source network port, a destination network address or a destination network port;

generate a modified version of the particular network packet, wherein the modified version includes changes to one or more header entries of the particular network packet in accordance with a particular rewrite entry created at the rewriting decisions tier;

transmit the modified version of the particular network packet to a destination network address indicated in the modified version; and

wherein the one or more nodes of the rewriting decisions tier are configured to;

receive an indication from a client of a selected packet processing requirement to be applied to one or more network flows, wherein

the selected packet processing requirement is selected from a plurality of supported packet processing requirements for network flows, and wherein the plurality of supported packet processing requirements comprise two or more of;

(a) a source address substitution requirement, (b) a multicast requirement, (c) an anycast requirement or (d) a load balancing requirement;

generate a plurality of rewrite entries, including the particular rewrite entry, to fulfill the packet processing requirements of the client, wherein at least one entry of the plurality of rewrite entries is based at least in part, on an analysis of state information pertaining to one or more network flows.

7. The multi-tier network flow management system as recited in claim 6, wherein the one or more nodes of the rewriting decisions tier include a first node and a second node, wherein the particular rewrite entry is generated at the first node, and wherein the first node is configured to:

initiate a replication, prior to a transmission of the particular rewrite entry to the packet transformation tier, of the particular rewrite entry at the second node.

8. The multi-tier network flow management system as recited in claim 6, further comprising one or more nodes of a flow state tracking tier configured to:

update, based at least in part on one or more messages received from the packet transformation tier, a flow state record corresponding to the particular network flow; and

transmit the state information pertaining to the one or more network flows to the rewriting decisions tier, wherein the state information comprises the flow state record.

9. The multi-tier network flow management system as recited in claim 8, wherein the one or more nodes of the rewriting decisions tier include a first node and a second node, and wherein the one or more nodes of the flow state tracking tier are configured to transmit respective copies of the state information to the first node and the second node.

10. The multi-tier network flow management system as recited in claim 8, wherein the one or more nodes of the packet transformation tier include a first node at which the particular network packet is received, wherein the first node is configured to:

determine whether a first cache of rewrite entries associated with the first node includes a rewrite entry applicable to the particular network packet; and

in response to a determination that the first cache does not include a rewrite entry applicable to the particular network packet, transmit, to a selected node of the flow state tracking tier, a representation of a first cache miss corresponding to the particular network packet.

11. The multi-tier network flow management system as recited in claim 10, wherein the first node at which the particular network packet is received is configured to:

choose the selected node of the flow state tracking layer as a destination to which the representation of the first cache miss is to be transmitted, based at least in part on one or more of;

(a) identity information of a client associated with the particular network packet or (b) a hash function applied to one or more header entries of the particular network packet.

12. The multi-tier network flow management system as recited in claim 10, wherein the particular rewrite entry is generated at a particular node of the rewriting decisions tier, wherein the selected node of the flow state tracking tier is configured to:

in response to receiving the representation of the first cache miss, determine whether a second cache of rewrite entries associated with the selected node includes a rewrite entry applicable to the particular network packet; and

in response to a determination that the second cache does not include a rewrite entry applicable to the particular network packet, transmit, to the particular node of the rewriting decisions tier, a representation of a second cache miss corresponding to the particular network packet.

13. The multi-tier network flow management system as recited in claim 12, wherein the particular node of the rewriting decisions tier is configured to:

transmit the particular rewrite entry to the first node of the packet transformations layer.

14. The multi-tier network flow management system as recited in claim 12, wherein the particular node of the rewriting decisions tier is configured to:

transmit the particular rewrite entry to the selected node of the flow state tracking layer.

15. The multi-tier network flow management system as recited in claim 12, wherein the selected node of the flow state tracking tier is configured to:

choose the particular node of the rewriting decisions tier as a destination to which the representation of the second cache miss is to be transmitted, based at least in part on one or more of;

(a) identity information of a client associated with the particular network packet, (b) a hash function applied to one or more header entries of the particular network packet, or (c) a category of packet processing to be performed on the particular network packet.

16. The multi-tier network flow management system as recited in claim 6, further comprising one or more association nodes, wherein a particular node of the packet transformation tier is configured to:

receive a particular fragment of a message, wherein the message comprises a plurality of fragments transmitted in respective packets; and

transmit the particular fragment to a selected association node of the one or more association nodes; and

wherein the selected association node is configured to;

store the particular fragment until each fragment of the plurality of fragments has been received at the selected association node;

transmit, to the particular node of the packet transformation tier (a) header information indicated in a second fragment of the plurality of fragments, wherein the header information is not indicated in the particular fragment and (b) contents of the plurality of fragments.

17. A non-transitory computer-accessible storage medium storing program instructions that when executed on one or more processors implement a node of a rewriting decisions tier of a network flow management system, wherein the node of the rewriting decisions tier is configured to:

receive an indication from a client of a selected packet processing requirement to be applied to one or more network flows, wherein the selected packet processing requirement is selected from a plurality of supported packet processing requirements for network flows, wherein the plurality of supported packet processing requirements comprise two or more of;

(a) a source address substitution requirement, (b) a multicast requirement, (c) an anycast requirement or (d) a load balancing requirement;

receive an indication that a rewrite entry to be used to modify one or more network packets of a particular network flow is to be generated, wherein the particular network flow is distinguishable from other network flows by a combination of one or more of;

a network protocol, a source network address, a source network port, a destination network address and a destination network port;

generate the rewrite entry based at least in part on the indication of the client selected packet processing requirement; and

initiate a transmission of the rewrite entry to a node of a different tier of the network flow management system.

18. The non-transitory computer-accessible storage medium as recited in claim 17, wherein the node of the rewriting decisions tier is configured to:

transmit a request to replicate the rewrite entry at another node of the rewriting decisions tier.

19. A non-transitory computer-accessible storage medium storing program instructions that when executed on one or more processors implement a node of a flow state tracking tier of a network flow management system, wherein the node of the flow state tracking tier is configured to:

receive a first request for a rewrite entry to be used to modify one or more network packets of a particular network flow at a first node of a packet transformation tier of the network flow management system, wherein the particular network flow is distinguishable from other network flows by a combination of one or more of;

a network protocol, a source network address, a source network port, a destination network address and a destination network port;

in response to a determination that a rewrite entry cache does not include a rewrite entry usable to respond to the first request, transmit a second request for the rewrite entry to a selected node of a rewriting decisions tier of the network flow management system;

transmit, to the first node of the packet transformation tier, a rewrite entry generated at the selected node of the rewriting decisions tier in response to the second request;

update, based at least in part on one or more messages received from the first node of the packet transformation tier subsequent to transmission of the rewrite entry to the first node, a first flow state record corresponding to the particular network flow; and

transmit, to at least the selected node of the rewriting decisions tier, a representation of one or more flow state records including the first flow state record.

20. The non-transitory computer-accessible storage medium as recited in claim 19, wherein the node of the flow state tracking tier is configured to:

transmit a request to replicate the rewrite entry at another node of the flow state tracking tier.

21. The non-transitory computer-accessible storage medium as recited in claim 19, wherein the node of the flow state tracking tier is configured to:

generate, based at least in part on the rewrite entry, a transformed packet corresponding to a particular packet of the particular network flow; and

transmit the transformed packet to a destination address indicated in the transformed packet.