Identifying elephant flows through periodically sampled packets

ABSTRACT

Identifying elephant flows is very important in developing effective and efficient traffic engineering schemes. In addition, obtaining the statistics of these flows is also very useful for network operation and management. On the other hand, with the rapid growth of link speed in recent years, packet sampling has become a very attractive and scalable means to measure flow statistics; however, it also makes identifying elephant flows become much more difficult. Based on Bayes' theorem, this paper develops techniques and schemes to identify elephant flows in periodically sampled packets. We show that our basic framework is very flexible in making appropriate trade-offs between false positives (misidentified flows) and false negatives (missed elephant flows) with regard to a given sampling frequency. We further validate and evaluate our approach by using some publicly available traces. Our schemes are generic and require <i>no</i> per-packet processing; hence, they allow a very cost-effective implementation for being deployed in large-scale high-speed networks.

References

1. N. Duffield, C. Lund, and M. Thorup, "Charging from Sampled Network Usage," ACM SIGCOMM Internet Measurement Workshop, California, November, 2001.
2. N. Duffield, C. Lund, and M. Thorup, "Properties and Prediction of Flow Statistics from Sampled Packet Streams," ACM SIGCOMM Internet Measurement Workshop, Marseille, France, November, 2002.
3. N. Duffield, C. Lund, and M. Thorup, "Estimating Flow Distributions from Sampled Flow Statistics," In Proceedings of ACM SIGCOMM, pp. 325--336, August 2003.
4. C. Estan and G. Varghese, "New Directions in Traffic Measurement and Accounting," In Proceedings of ACM SIGCOMM, pp. 323--336, August 2002.
5. S. Ben Fredj, T. Bonald, A. Proutiere, G. Regnie, and J. Roberts, "Statistical bandwidth sharing: a study of congestion at flow level, "In Proceedings of ACM SIGCOMM, pp. 111--122, August 2001.
6. L. Golab, D. DeHaan, E. Demaine, and A. Lopez-Ortiz, "Identifying Frequent Items in Sliding Windows over On-Line Packet Streams," ACM SIGCOMM Internet Measurement Conference, Florida, October, 2003.
7. A. Kumar, J. Xu, J. Wang, O. Spatschek, and L. Li, "Space-Code Bloom Filter for Efficient Per-Flow Traffic Measurement," In proceedings of IEEE INFOCOM, Hong Kong, China, March 2004.
8. T. Mori, R. Kawahara, S. Naito, and S. Goto, "On the characteristics of Internet Traffic variability: Spikes and Elephants," In Proceedings of IEEE/IPSJ SAINT, pp. 99--106, Tokyo, Japan, Jan 2004
9. NLANR: Abilene-I data set, http://pma.nlanr.net/Traces/long/ipls1.html
10. NLANR: CESCA-I data set, http://pma.nlanr.net/Special/cesc1.html
11. Cisco NetFlow, http://www.cisco.com/warp/public/732/netflow/index.html
12. K. Papagiannaki, N. Taft, S. Bhattacharya, P. Thiran, K. Salamatian, and C. Diot, "On the feasibility of identifying elephants in internet backbone traffic. Sprint ATL Technical Report TR01-ATL-110918," Sprint Labs, November 2001.
13. IETF Packet Sampling (psamp) Working Group, http://www.ietf.org/html.charters/psamp-charter.html
14. InMon sFlow Probe, http://www.inmon.com/products/probes.php
15. K. Thompson, G. J. Miller, and R. Wilder, "Wide-area internet traffic patterns and characteristics," IEEE Network, vol. 11, no. 6, pp. 10--23, November/December 1997.
16. Y. Zhang, L. Breslau, V. Paxson, and S. Shenker, "On the Characteristics and Origins of Internet Flow Rates," In Proceedings of ACM SIGCOMM, pp. 309--322, August 2002.

Index Terms

• Networks

  • Network services

    • Network monitoring