Vineet Bharti
Mark Crovella
ABSTRACT
A traffic matrix encompassing the entire Internet would be very valuable. Unfortunately, from any given vantage point in the network, most traffic is invisible. In this paper we describe results that hold some promise for this problem. First, we show a new characterization result: traffic matrices (TMs) typically show very low effective rank. This result refers to TMs that are purely spatial (have no temporal component), over a wide range of spatial granularities. Next, we define an inference problem whose solution allows one to infer invisible TM elements. This problem relies crucially on an atomicity property we define. Finally, we show example solutions of this inference problem via two different methods: regularized regression and matrix completion. The example consists of an AS inferring the amount of invisible traffic passing between other pairs of ASes. Using this example we illustrate the accuracy of the methods as a function of spatial granularity.
- Akamai Technologies, Inc. The state of the Internet. 4th Quarter, 2009.Google Scholar
- A. Broido and kc claffy. Analysis of RouteViews BGP data: policy atoms. In Proceedings of Network Related Data Management Workshop (NRDM), Santa Barbara, CA, May 2001.Google Scholar
- CAIDA. Atom computation scripts. http://www.caida.org/funding/atomized_routing/documents/report1.xml, February 2003.Google Scholar
- Emmanuel J. Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foundations of Computational Mathematics, 9(6):712--772, 2009. Google ScholarDigital Library
- H. Chang, S. Jamin, Z. Mao, and W. Willinger. An empirical approach to modeling inter-AS traffic matrices. In Proceedings of IMC, 2005. Google ScholarDigital Library
- V. Erramilli, M. Crovella, and N. Taft. An independent-connection model for traffic matrices. In Proceedings of the Internet Measurement Conference, October 2006. Google ScholarDigital Library
- W. Fang and L. Peterson. Inter-AS traffic patterns and their implications. In Proceedings of GLOBECOM, 1999.Google ScholarCross Ref
- A. Feldmann, N. Kammenhuber, O. Maennel, B. Maggs, R. De Prisco, and R. Sundaram. A methodology for estimating interdomain web traffic demand. In Proceedings of IMC, 2004. Google ScholarDigital Library
- T. Hastie, R. Tibshirani, and J. Friedman. The Elements of Statistical Learning. Springer, 2nd edition, 2009.Google Scholar
- R. H. Keshavan, S. Oh, and A. Montanari. Matrix completion from a few entries. http://arxiv.org/abs/0901.3150, 2009. Google ScholarDigital Library
- L. Kleinrock and W. Naylor. On the measured behavior of the ARPANetwork. In AFIPS Conference Proceedings, National Computer Conference, pages 767--780, May 1974. Google ScholarDigital Library
- A. Lakhina, K. Papagiannaki, M. Crovella, C. Diot, E. D. Kolaczyk, and N. Taft. Structural analysis of network traffic flows. In Proceedings of ACM SIGMETRICS, pages 61--72, June 2004. Google ScholarDigital Library
- A. Medina, N. Taft, K. Salamatian, S. Bhattacharyya, and C. Diot. Traffic matrix estimation: Existing techniques and new directions. In Proceedings of ACM SIGCOMM, 2002. Google ScholarDigital Library
- W. Mühlbauer, S. Uhlig, B. Fu, M. Meulle, and O. Maennel. In search for an appropriate granularity to model routing policies. In Proceedings of ACM SIGCOMM, 2007. Google ScholarDigital Library
- University of Oregon. Route views project. http://www.routeviews.org/, July 2009.Google Scholar
- M. Roughan. First order characterization of Internet traffic matrices. Invited paper at the 55th Session of the International Statistics Institute, April 2005.Google Scholar
- J. Wallerich, H. Dreger, A. Feldmann, B. Krishnamurthy, and W. Willinger. A methodology for studying persistency aspects of Internet flows. Computer Communication Review, April 2005. Google ScholarDigital Library
- Z. Wen, W. Yin, and Y. Zhang. Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm. Technical report, Rice University, 2010.Google Scholar
- Y. Zhang, M. Roughan, N. Duffield, and A. Greenberg. Fast accurate computation of large-scale IP traffic matrices from link loads. In Proceedings of ACM SIGMETRICS, 2003. Google ScholarDigital Library
- Y. Zhang, M. Roughan, C. Lund, and D. Donoho. Estimating point-to-point and point-to-multipoint traffic matrices: An information-theoretic approach. IEEE/ACM Transactions on Networking, 13(5):947960, 2005. Google ScholarDigital Library
- Y. Zhang, M. Roughan, W. Willinger, and L. Qiu. Spatio-temporal compressive sensing and Internet traffic matrices. In Proceedings of ACM SIGCOMM, 2009. Google ScholarDigital Library
Index Terms
- Inferring invisible traffic
Recommendations
A JPEG-based statistically invisible steganography
ICIMCS '11: Proceedings of the Third International Conference on Internet Multimedia Computing and ServiceThe objective of steganography is to implement covert communication by hiding data in digital files such that there is no indication of the existence of hidden data; so an ideal steganographic system should be able to withstand all steganalysis methods--...
Digital invisible ink: revealing true secrets via attacking
ASIACCS '06: Proceedings of the 2006 ACM Symposium on Information, computer and communications securityA novel steganographic approach analogy to the real-world secret communication mechanism, in which secret messages are written on white papers using invisible ink like lemon juice and are revealed only after the papers are heated, is proposed. Carefully-...
Comments