Systems and methods for fast detection of elephant flows in network traffic
In a system for efficiently detecting large/elephant flows in a network, the rate at which the received packets are sampled is adjusted according to a top flow detection likelihood computed for a cache of flows identified in the arriving network traffic. After observing packets sampled from the network, Dirichlet-Categorical inference is employed to calculate a posterior distribution that captures uncertainty about the sizes of each flow, yielding a top flow detection likelihood. The posterior distribution is used to find the most likely subset of elephant flows. The technique rapidly converges to the optimal sampling rate at a speed O(1/n), where n is the number of packet samples received, and the only hyperparameter required is the targeted detection likelihood.
1. A method for sampling a stream of packets arriving at a network node at an optimized sampling rate, so as to facilitate efficient classification of network flows corresponding to the stream of packets arriving at a network node, the method comprising:
(a) at a selected sampling rate, sampling a packet from the stream of packets arriving at the network node;
(b) for each candidate number of elephant flows in a set of candidate numbers computing, and storing in a cache of candidate elephant flows associated with the stream of packets, a respective detection likelihood using the sampled packet; and
(c) updating the selected sampling rate according to the one or more detection likelihoods,
wherein the computation of the respective detection likelihood for a particular candidate number of elephant flows is based on pairwise probabilities of relative flow sizes of flow pairs in the cache, and comprises, for each pair of flows in a cache of flows, updating a pairwise probability of relative flow sizes using flow-size metrics of flows in the pair and the sampled packet.
2. The method of claim 1 , wherein updating the pairwise probability of relative flow sizes for a pair comprises:
determining whether the sampled packet belongs to a first flow of the pair, or a second flow of the pair, or to neither flow of the pair; and
updating the pairwise probability of relative flow sizes based on the determination.
3. The method of claim 1 , wherein updating the pairwise probability of relative flow sizes for a pair comprises:
selecting, based on the determination, a Beta distribution based function of positive and negative flow-size metrics;
computing an adjustment factor using the selected function and the positive and negative flow-size metrics associated with each flow in the pair; and
updating the pairwise probability using an adjustment factor.
4. The method of claim 2 , wherein updating the pairwise probability of relative flow sizes for a first pair comprises:
determining that a flow-size metric for a first flow in a first pair is the same as a flow-size metric for a first flow in a second pair, wherein: (i) a second flow in the second pair is the same as a second flow in the first pair, and (ii) the pairwise probability for the second pair was updated; and
copying the pairwise probability for the second pair as the pairwise probability for the first pair.
5. The method of claim 1 , wherein a flow-size metric comprises a positive metric and a negative metric, the method further comprising, for each flow in the cache, updating a respective flow-size metric by:
incrementing a positive metric associated with the flow if the sampled packet belongs to the flow; and
otherwise, incrementing a negative metric associated with the flow.
6. The method of claim 1 , wherein updating the selected sampling rate comprises:
if for at least one candidate number of elephant flows the detection likelihood is greater than a specified threshold, decreasing or maintaining the sampling rate; and
otherwise, increasing the sampling rate.
7. The method of claim 1 , further comprising repeating the steps (a) through (c) using the updated sampling rate.
8. The method of claim 1 , wherein the set of candidate numbers of elephant flows comprises numbers from one through a number of flows in the cache minus one.
9. The method of claim 1 , wherein for at least one candidate number of elephant flows the detection likelihood is greater than a specified threshold, the method further comprising:
identifying a largest candidate number of elephant flows ({circumflex over (∈)}) for which the detection likelihood is greater than the specified threshold; and
designating first {circumflex over (∈)} flows in the cache as elephant flows.
10. The method of claim 1 , further comprising initializing the cache by:
sampling a plurality of packets from the stream of packets arriving at the network node at the selected sampling rate;
identifying a flow associated with each one of the sampled plurality of packets;
computing a flow-size metric for each identified flow; and
including γ flows having largest flow-size metrics in the cache, wherein size of the cache is γ.
11. The method of claim 10 , wherein a total number of identified flows is greater than γ.
12. The method of claim 1 , further comprising updating the cache by:
removing a removable flow from the cache when a flow removal condition occurs;
replacing in the cache the removed flow with a new flow associated with the stream of packets; and
updating pairwise probabilities for all pairs comprising the new flow using an initial flow-size metric for the new flow.
13. The method of claim 12 , wherein the flow removal condition occurs: (i) when a flow-size metric for the removable flow is not updated during a specified time window, or (ii) when a cache update time period has elapsed since a previous cache update, and a flow-size metric for the removable flow is smallest among flow-size metrics for all flows in the cache.
14. The method of claim 12 , wherein:
the cache comprises a dummy flow that is not associated with the stream of packets, a flow-size metric for the dummy flow being the initial flow-size metric; and
updating the pairwise probabilities for all pairs comprising the new flow comprises designating the dummy flow as the new flow;
the method further comprising copying the dummy flow and designating the copy as the dummy flow.
15. The method of claim 1 , wherein the selected sampling rate is updated to a value in a range from 0.000001 up to 1.0.
16. The method of claim 1 , wherein a rate of arrival of the packets in the stream is in a range from 1 kbps up to 100 Tbps.
17. The method of claim 1 , wherein a sampled packet belongs to a particular flow based on at least one of:
a pair of source and destination addresses in a header of the sampled packet;
a pair of source and destination port numbers in the header of the sampled packet;
a virtual local area network (VLAN) identifier included in the header of the sampled packet; or
a multiprotocol label switching (MPLS) label included in the header of the sampled packet.
18. The method of claim 1 , wherein a flow-size metric for a flow is based on one or more of:
(i) a number of packets belonging to the flow at a time of computing the flow-size metric;
(ii) a number of bytes belonging to the flow at the time of computing the flow-size metric;
(iii) an average number of packets belonging to the flow per unit time; and
(iv) an average number of bytes belonging to the flow per the unit time.
19. The method of claim 1 , wherein after updating the selected sampling rate, the selected sampling rate is not updated at least for a specified rate adjustment interval.
20. The method of claim 1 , wherein:
increasing the selected sampling rate comprises increasing the selected sampling rate by a first step size; and
decreasing the selected sampling rate comprises decreasing the selected sampling rate by a second step size.
21. A system for sampling a stream of packets arriving at a network node at an optimized sampling rate, so as to facilitate efficient classification of network flows corresponding to the stream of packets arriving at a network node, the system comprising:
a first processor; and
a first memory in electrical communication with the first processor, the first memory comprising instructions which, when executed by a processing unit comprising at least one of the first processor and a second processor, and in electronic communication with a memory module comprising at least one of the first memory and a second memory, configure the processing unit to:
(a) sample, at a selected sampling rate, a packet from the stream of packets arriving at the network node;
(b) compute and store in a cache of candidate elephant flows associated with the stream of packets, for each candidate number of elephant flows in a set of candidate numbers, a respective detection likelihood using the sampled packet; and
(c) update the selected sampling rate according to the one or more detection likelihoods,
wherein the computation of the detection likelihood for a particular candidate number of elephant flows is based on pairwise probabilities of relative flow sizes of flow pairs in the cache, and the instructions further program the processing unit to:
update, for each pair of flows in a cache of flows, a pairwise probability of relative flow sizes using flow-size metrics of flows in the pair and the sampled packet.
22. The system of claim 21 , wherein to update the pairwise probability of relative flow sizes for a pair the instructions program the processing unit to:
determine whether the sampled packet belongs to a first flow of the pair, or a second flow of the pair, or to neither flow of the pair; and
update the pairwise probability of relative flow sizes based on the determination.
23. The system of claim 22 , wherein to update the pairwise probability of relative flow sizes for a pair the instructions program the processing unit to:
select, based on the determination, a Beta distribution based function of positive and negative flow-size metrics;
compute an adjustment factor using the selected function and the positive and negative flow-size metrics associated with each flow in the pair; and
update the pairwise probability using an adjustment factor.
24. The system of claim 22 , wherein to update the pairwise probability of relative flow sizes for a first pair the instructions program the processing unit to:
determine that a flow-size metric for a first flow in a first pair is the same as a flow-size metric for a first flow in a second pair, wherein: (i) a second flow in the second pair is the same as a second flow in the first pair, and (ii) the pairwise probability for the second pair was updated; and
copy the pairwise probability for the second pair as the pairwise probability for the first pair.
25. The system of claim 21 , wherein a flow-size metric comprises a positive metric and a negative metric, and to update a respective flow-size metric for each flow in the cache, the instructions program the processing unit to:
increment a positive metric associated with the flow if the sampled packet belongs to the flow; and
otherwise, increment a negative metric associated with the flow.
26. The system of claim 21 , wherein to update the selected sampling rate the instructions program the processing unit to:
decrease or maintain the sampling rate, if for at least one candidate number of elephant flows the detection likelihood is greater than a specified threshold; and
otherwise, increase the sampling rate.
27. The system of claim 21 , wherein the instructions further program the processing unit to repeat operations (a) through (c) using the updated sampling rate.
28. The system of claim 21 , wherein the set of candidate numbers of elephant flows comprises numbers from one through a number of flows in the cache minus one.
29. The system of claim 21 , wherein for at least one candidate number of elephant flows the detection likelihood is greater than a specified threshold, and the instructions further program the processing unit to:
identify a largest candidate number of elephant flows ({circumflex over (∈)}) for which the detection likelihood is greater than the specified threshold; and
designate first {circumflex over (∈)} flows in the cache as elephant flows.
30. The system of claim 21 , wherein to initialize the cache, the instructions further program the processing unit:
sample a plurality of packets from the stream of packets arriving at the network node at the selected sampling rate;
identify a flow associated with each one of the sampled plurality of packets;
compute a flow-size metric for each identified flow; and
include γ flows having largest flow-size metrics in the cache, wherein size of the cache is γ.
31. The system of claim 30 , wherein a total number of identified flows is greater than γ.
32. The system of claim 21 , wherein to update the cache, the instructions further program the processing unit to:
remove a removable flow from the cache when a flow removal condition occurs;
replace in the cache the removed flow with a new flow associated with the stream of packets; and
update pairwise probabilities for all pairs comprising the new flow using an initial flow-size metric for the new flow.
33. The system of claim 32 , wherein the flow removal condition occurs: (i) when a flow-size metric for the removable flow is not updated during a specified time window, or (ii) when a cache update time period has elapsed since a previous cache update, and a flow-size metric for the removable flow is smallest among flow-size metrics for all flows in the cache.
34. The system of claim 32 , wherein:
the cache comprises a dummy flow that is not associated with the stream of packets, a flow-size metric for the dummy flow being the initial flow-size metric;
to update the pairwise probabilities for all pairs comprising the new flow, the instructions program the processing unit to designate the dummy flow as the new flow; and
the instructions further program the processing unit to copy the dummy flow and designating the copy as the dummy flow.
35. The system of claim 21 , wherein the selected sampling rate is updated to a value in a range from 0.000001 up to 1.0.
36. The system of claim 21 , wherein a rate of arrival of the packets in the stream is in a range from 1 kbps up to 100 Tbps.
37. The system of claim 21 , wherein the instructions program the processing unit to determine a particular flow to which a sampled packet belongs based on at least one of:
a pair of source and destination addresses in a header of the sampled packet;
a pair of source and destination port numbers in the header of the sampled packet;
a virtual local area network (VLAN) identifier included in the header of the sampled packet; or
a multiprotocol label switching (MPLS) label included in the header of the sampled packet.
38. The system of claim 21 , wherein a flow-size metric for a flow is based on one or more of:
(i) a number of packets belonging to the flow at a time of computing the flow-size metric;
(ii) a number of bytes belonging to the flow at the time of computing the flow-size metric;
(iii) an average number of packets belonging to the flow per unit time; and
(iv) an average number of bytes belonging to the flow per the unit time.
39. The system of claim 21 , wherein after updating the selected sampling rate, the instructions program the processing unit to suspend updating the selected sampling rate at least for a specified rate adjustment interval.
40. The system of claim 21 , wherein:
to increase the selected sampling rate, the instructions program the processing unit to increase the selected sampling rate by a first step size; and
to decreasing the selected sampling rate, the instructions program the processing unit to decrease the selected sampling rate by a second step size.