Spectral probing, crosstalk and frequency multiplexing in internet paths

ABSTRACT

We present an end-to-end active probing methodology that creates frequency-domain signals in IP network paths. The signals are generated by periodic packet trains that cause short-lived queueing delay spikes. Different probers can be multiplexed in the frequency-domain on the same path. Further, a signal that is introduced by a "prober" in one path can cause a crosstalk effect, inducing a signal of the same frequency into another path (the "sampler") as long as the two paths share one or more bottleneck queues. Applications of the proposed methodology include the detection of shared store-and-forward devices among two or more paths, the creation of covert channels, and the modulation of voice or video periodic packet streams in less noisy frequencies. In this paper we focus on the first application. Our goal is to detect shared bottleneck(s) between a "sampler" and one or more "prober" paths. We present a spectral probing methodology as well as the corresponding signal processing/detection process. The accuracy of the method has been evaluated with controlled and repeatable simulation experiments, and it has also been tested on some Internet paths.

REFERENCES

• 1: Brice Augustin , Xavier Cuvellier , Benjamin Orgogozo , Fabien Viger , Timur Friedman , Matthieu Latapy , Clémence Magnien , Renata Teixeira, Avoiding traceroute anomalies with Paris traceroute, Proceedings of the 6th ACM SIGCOMM conference on Internet measurement, October 25-27, 2006, Rio de Janeriro, Brazil [doi>10.1145/1177080.1177100]
• 2: Paul Barford , Jeffery Kline , David Plonka , Amos Ron, A signal analysis of network traffic anomalies, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637210]
• 3: P. Bloomfield. Fourier Analysis of Time Series: An Introduction. Wiley-Interscience, 2nd edition, 2000.
• 4: Andre Broido , Evi Nemeth , kc claffy, Spectroscopy of Private DNS Update Sources, Proceedings of the The Third IEEE Workshop on Internet Applications, p.19, June 23-24, 2003
• 5: A. B. Carlson, P. Crilly, and J. Rutledge. Communication Systems (4th edition). McGraw-Hill, 2004.
• 6: A. Chen, J. Cao, and T. Bu. Network tomography: Identifiability and Fourier domain estimation. pages 1875--1883, 2007.
• 7: C.-M. Cheng, H. Kung, and K.-S. Tan. Use of spectral analysis in defense against DoS attacks. In Proceedings of IEEE GLOBECOM. IEEE, 2002.
• 8: D. Cousins, C. Partridge, K. Bongiovanni, A. Jackson, R. Krishnan, T. Saxena, and W. Strayer. Understanding Encrypted Networks Through Signal and Systems Analysis of Traffic Timing. In Proceedings of IEEE Aerospace Conference, Mar. 2003.
• 9: I. Csabai. 1/f Noise in Computer Network Traffic. Journal of Physics A, A27(L417-421), 1994.
• 10: W. Cui, S. Machiraju, R. H. Katz, and I. Stoica. SCONE: A tool to estimate shared congestion among Internet paths. UCB Technical Report UCB/CSD-04-1320.
• 11: X. He, C. Papadopoulos, J. Heidemann, and A. Hussain. Spectral characteristics of saturated links. Technical Report USC/CS-TR-2004-827, USC, June 2004.
• 12: X. He, C. Papadopoulos, J. Heidemann, U. Mitra, U. Riaz, and A. Hussain. Spectral analysis of bottleneck traffic. Technical Report USC/CS-TR-2005-853, USC, June 2005.
• 13: Polly Huang , Anja Feldmann , Walter Willinger, A non-instrusive, wavelet-based approach to detecting network performance problems, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505229]
• 14: Alefiya Hussain , John Heidemann , Christos Papadopoulos, A framework for classifying denial of service attacks, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863968]
• 15: D. Katabi and C. Blake. Inferring congestion sharing and path characteristics from packet interarrival times. Technical Report MIT-LCS-TR-828, MIT, 2002.
• 16: Min Sik Kim , Taekhyun Kim , YongJune Shin , Simon S. Lam , Edward J. Powers, A wavelet-based approach to detect shared congestion, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 17: M. S. Kim, T. Kim, Y. J. Shin, S. S. Lam, and E. J. Powers. Scalable clustering of Internet paths by shared congestion. Proceedings of IEEE INFOCOM, pages 1--10, 2006.
• 18: San-qi Li , James D. Pruneski, The linearity of low frequency traffic flow: an intrinsic I/O property in queueing systems, IEEE/ACM Transactions on Networking (TON), v.5 n.3, p.429-443, June 1997 [doi>10.1109/90.611107]
• 19: S. B. Moon, P. Skelly, and D. Towsley. Estimation and removal of clock skew from network delay measurements. In Proceedings of IEEE INFOCOM, 1999.
• 20: Alan V. Oppenheim , Ronald W. Schafer, Discrete-time signal processing, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 21: C. Partridge and D. Cousins. Systems and methods for creating covert channels using packet frequencies. United States Patent Application 20030091064, May 2003.
• 22: M. Rabbat, M. Coates, and R. D. Nowak. Multiple-source Internet tomography. IEEE JSAC, 24(12):2221--2234, 2006.
• 23: R. S. Tsay. Outliers, Level Shifts, and Variance Changes in Time Series. Journal of Forecasting, 1988.
• 24: Dan Rubenstein , Jim Kurose , Don Towsley, Detecting shared congestion of flows via end-to-end measurement, IEEE/ACM Transactions on Networking (TON), v.10 n.3, p.381-395, June 2002 [doi>10.1109/TNET.2002.1012369]
• 25: Yin Zhang , Nick Duffield, On the constancy of internet path properties, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505228]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network monitoring

General Terms:
Experimentation, Measurement, Performance

Keywords:
active probing, distributed agents, fourier transform, frequency multiplexing, network management, signal processing