Metadata synchronization in flow management systems

Patent metadata

Field	Value
Publication number	US-9934273-B1
Application number	US-201514736167-A
Country	US
Kind code	B1
Filing date	Jun 10, 2015
Priority date	Jun 10, 2015
Publication date	Apr 3, 2018
Grant date	Apr 3, 2018

Abstract

An iteratively updated metadata collection is used for making packet rewriting decisions at a flow management system. In a particular iteration at a particular rewriting decisions node of the system, metadata representing older local decisions is discarded, and metadata representing notifications of older rewriting decisions which were received at a different tier is also discarded. Representations of more recent local decisions and more recent notifications received at the different tier are added to the metadata collection during the particular iteration. New rewriting decisions are made using aggregations of the objects in the metadata collection.

First claim

What is claimed is:

1. A method, comprising:
performing, at a particular node of a rewriting decisions tier of a stateful network flow management service, a plurality of metadata update iterations, wherein a particular metadata update iteration of the plurality of metadata update iterations comprises:
substituting, within a metadata collection used for packet rewriting decisions at the particular node, a first local decisions summary with a second local decisions summary, wherein the second local decisions summary comprises indications of one or more packet rewriting decisions made at the particular node for one or more network flows subsequent to a set of packet rewriting decisions indicated in the first local decisions summary, wherein a 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;
substituting, within the metadata collection, a first flow state summary with a second flow state summary, wherein the second flow state summary corresponds to one or more packet rewriting decision notifications received at a different tier of the stateful network flow management system from the rewriting decisions tier subsequent to a set of packet rewriting decision notifications corresponding to the first flow state summary;
initializing, within the metadata collection, a third local decisions summary to be used to store indications of additional packet rewriting decisions made at the particular node;
storing, within the metadata collection, a third flow state summary received from the different tier, wherein the third flow state summary corresponds to one or more additional packet rewriting decision notifications received at the different tier subsequent to packet rewriting decision notifications corresponding to the second flow state summary; and

determining, at the particular node of the rewriting decisions tier using an aggregation of at least a portion of the metadata collection, at least one element of a rewrite entry to be used to generate, in accordance with a packet processing requirement of a client, one or more transformed packets corresponding to one or more received packets.

2. The method as recited in claim 1 , wherein at least one of: (a) a particular flow state summary of the metadata collection or (b) a particular local decisions summary of the metadata collection comprises one or more probabilistic data structures.

3. The method as recited in claim 2 , wherein the one or more probabilistic data structures include a Bloom filter corresponding to a plurality of network flows for which rewrite entries are generated at the rewriting decisions tier.

4. The method as recited in claim 2 , wherein the one or more probabilistic data structures include a HyperLogLog (HLL) structure representing a number of network flows whose traffic is directed at a particular server based on rewrite entries generated at the rewriting decisions tier.

5. The method as recited in claim 1 , further comprising:
performing, at the particular node, a Boolean OR operation on a plurality of summaries included in the metadata collection to obtain the aggregation of at least a portion of the metadata collection.

6. A network flow management system, comprising:
one or more nodes of a rewriting decisions tier;
wherein a particular node of the rewriting decisions tier is configured to:
perform a plurality of metadata update iterations, wherein a particular metadata update iteration of the plurality of metadata update iterations comprises:
discarding, from a metadata collection used for making packet rewriting decisions, (a) metadata representing one or more local packet rewriting decisions which meet a first age criterion and (b) metadata corresponding to one or more notifications of packet rewriting decisions received at a different tier of the network flow management system, wherein the one or more indicators meet a second age criterion;
adding, to the metadata collection (a) metadata representing one or more local packet rewriting decisions which do not meet the first age criterion and (b) metadata corresponding to one or more other notifications of packet rewriting decisions received at the different tier, wherein the one or more other indicators do not meet the second age criterion; and

determine, using at least a portion of the metadata collection, at least one element of a rewrite entry to be used to transform a plurality of packets in accordance with a network flow processing requirement of a client.

7. The system as recited in claim 6 , wherein the metadata collection comprises one or more probabilistic data structures.

8. The system as recited in claim 7 , wherein the one or more probabilistic data structures include a Bloom filter corresponding to a plurality of network flows for which rewrite entries are generated at the rewriting decisions tier.

9. The system as recited in claim 7 , wherein the one or more probabilistic data structures include a HyperLogLog (HLL) structure representing a number of network flows whose traffic is directed at a particular server based on rewrite entries generated at the rewriting decisions tier.

10. The system as recited in claim 6 , wherein to determine, using at least the portion of the metadata collection, an element of a rewrite entry, the particular node of the rewriting decisions tier is configured to:
combine, using a commutative aggregation technique, contents of a plurality of objects of the metadata collection.

11. The system as recited in claim 6 , wherein to determine, using at least the portion of the metadata collection, at least one element of a rewrite entry, the particular node of the rewriting decisions tier is configured to:
verify that at least one of: (a) a network port selected for the rewrite entry or (b) a network address selected for the rewrite entry is unassigned to a network flow.

12. The system as recited in claim 6 , wherein to determine, using at least the portion of the metadata collection, at least one element of a rewrite entry, the particular node of the rewriting decisions tier is configured to:
select a particular destination server from a pool of potential destination servers for network packets of a particular network flow, based at least in part on a workload level of the particular destination server indicated in the metadata collection.

13. The system as recited in claim 6 , wherein the metadata collection includes at least a first local decisions summary and a second local decisions summary, wherein the second local decisions summary comprises indications of one or more packet rewriting decisions made at the particular node subsequent to a set of packet rewriting decisions indicated in the first local decisions summary.

14. The system as recited in claim 6 , wherein the metadata collection includes at least a first flow state summary and a second flow state summary, wherein the second flow state summary corresponds to one or more packet rewriting decision notifications received at the different tier of the network flow management system from the rewriting decisions tier subsequent to a set of packet rewriting decisions corresponding to the first flow state summary.

15. The system as recited in claim 6 , wherein the one or more nodes of the rewriting decisions tier include a plurality of nodes, further comprising:
one or more nodes of a flow state tracking tier; and
one or more nodes of a packet transformation layer;
wherein a particular node of the one or more nodes of

Assignees

• Amazon Tech Inc

Inventors

• Maccarthaigh Colm

Classifications

• H04L45/74

  Address processing for routing · CPC title

• G06F17/30997

  Physics · mapped topic

• G06F17/30598

  Physics · mapped topic

• G06F17/30448 Primary

  Physics · mapped topic

• G06F16/24534

  Query rewriting; Transformation · CPC title