Probabilistic filters for use in network forwarding and services
AssigneeVMware, Inc.
InventorHeeyeol Yu
Life of this patent
Estimating the term…
Abstract
Some embodiments of the invention provide novel methods for using probabilistic filters to keep track of data message flows that are processed at an element (e.g., forwarding element or middlebox service element) of a network. In some embodiments, the method iteratively switches between two probabilistic filters as the active and backup filters as a way of maintaining and refreshing its active probabilistic filter without the need for maintaining time values for removing outdated records from its active filter.
Claims20
A method of processing data messages forwarded through a network, the method comprising:
- at a network element in the network:
- maintaining (i) a first probabilistic filter as an active filter to keep track of a first plurality of data message flows processed by the network element during a first time period, and (ii) a second probabilistic filter as a backup filter to keep track of a second plurality of data message flows, which is a sampled subset of the first plurality of data message flows, processed by the network element during the first time period;
- at a start of a second time interval, resetting the first probabilistic filter;
- using (i) the second probabilistic filter as the active filter to keep track of a third plurality of data message flows processed by the network element during a second time period, and (ii) the first probabilistic filter as the backup filter to keep track of a fourth plurality of data message flows, which is a sampled subset of the third plurality of data message flows, processed by the network element during the second time period;
- during each time period, using the active filter for that time period to determine whether received data messages are part of flows previously processed by the network element and based on the determination, process the received data messages.
A non-transitory machine readable medium storing a program for processing data messages forwarded through a network, the program for execution by at least one processing unit, the program comprising sets of instructions for:
- maintaining (i) a first probabilistic filter as an active filter to keep track of a first plurality of data message flows processed by a network element during a first time period, and (ii) a second probabilistic filter as a backup filter to keep track of a second plurality of data message flows, which is a sampled subset of the first plurality of data message flows, processed by the network element during the first time period;
- at a start of a second time interval, resetting the first probabilistic filter;
- using (i) the second probabilistic filter as the active filter to keep track of a third plurality of data message flows processed by the network element during a second time period, and (ii) the first probabilistic filter as the backup filter to keep track of a fourth plurality of data message flows, which is a sampled subset of the third plurality of data message flows, processed by the network element during the second time period;
- during each time period, using the active filter for that time period to determine whether received data messages are part of flows previously processed by the network element and based on the determination, process the received data messages.
Dependencies are inferred from the claim text.