Understanding network delay changes caused by routing events

ABSTRACT

Network delays and delay variations are two of the most important network performance metrics directly impacting real-time applications such as voice over IP and time-critical financial transactions. This importance is illustrated by past work on understanding the delay constancy of Internet paths and recent work on predicting network delays using virtual coordinate systems. Merely understanding currently observed delays is insufficient, as network performance can degrade not only due to traffic variability but also as a result of routing changes. Unfortunately this latter effect so far has been ignored in understanding and predicting delay related performance metrics of Internet paths. Our work is the first to address this short coming by systematically analyzing changes in network delays and jitter of a diverse and comprehensive set of Internet paths. Using empirical measurements, we illustrate that routing changes can result in roundtrip delay increase of converged paths by more than 1 second. Surprisingly, intradomain routing changes can also cause such large delay increase.

Given these observations, we develop a framework to analyze in detail the impact of routing changes on network delays between end-hosts. Using topology information and properties associated with routing changes, we explain the causes for observed delay fluctuations and more importantly identify routing changes that lead to predictable effects on delay-related metrics. Using our framework, we study the predictability of delay and jitter changes in response to both passively observed interdomain and actively measured intradomain routing changes.

REFERENCES

• 1: NANOG Panel: Smart Routing Technologies. http://www.nanog.org/mtg-0206/smart.html, June 2003.
• 2: Y. Amir, C. Danilov, S. Goose, D. Hedqvist, and A. Terzis. An Overlay Architecture for High Quality VoIP Streams. IEEE Transactions on Multimedia, 2006.
• 3: David Andersen , Hari Balakrishnan , Frans Kaashoek , Robert Morris, Resilient overlay networks, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 4: 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]
• 5: Suman Banerjee , Bobby Bhattacharjee , Christopher Kommareddy, Scalable application layer multicast, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 6: Miguel Castro , Peter Druschel , Anne-Marie Kermarrec , Animesh Nandi , Antony Rowstron , Atul Singh, SplitStream: high-bandwidth multicast in cooperative environments, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 7: Cisco Systems, Inc. Cisco Optimized Edge Routing. http://www.cisco.com/en/US/products/ps6628/products ios protocol option home.html.
• 8: Frank Dabek , Russ Cox , Frans Kaashoek , Robert Morris, Vivaldi: a decentralized network coordinate system, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 9: Frank Dabek , Russ Cox , Frans Kaashoek , Robert Morris, Vivaldi: a decentralized network coordinate system, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 10: N. Feamster, L. Gao, and J. Rexford. How to lease the Internet in your spare time. Technical Report GT-CSS-06-10, Georgia Tech, August 2006.
• 11: P. Francis, S. Jamin, V. Paxson, L. Zhang, D. Gryniewicz, and Y. Jin. An Architecture for a Global Internet Host Distance Estimation Service. In Proceedings of IEEE INFOCOM, March 1999.
• 12: R. Govindan and V. Paxson. Estimating Router ICMP Generation Delays. In Proc of Passive and Active Measurement (PAM), 2002.
• 13: Yang-hua Chu , Sanjay G. Rao , Hui Zhang, A case for end system multicast (keynote address), Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.1-12, June 18-21, 2000, Santa Clara, California, United States
• 14: Craig Labovitz , Abha Ahuja , Abhijit Bose , Farnam Jahanian, Delayed Internet routing convergence, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.175-187, August 28-September 01, 2000, Stockholm, Sweden
• 15: K. Lakshminarayana, I. Stoica, S. Shenker, and J. Rexford. Routing as a Service. Technical Report UCB/EECS-2006-19, UC Berkeley, 2006.
• 16: Harsha V. Madhyastha , Thomas Anderson , Arvind Krishnamurthy , Neil Spring , Arun Venkataramani, A structural approach to latency prediction, Proceedings of the 6th ACM SIGCOMM conference on Internet measurement, October 25-27, 2006, Rio de Janeriro, Brazil [doi>10.1145/1177080.1177092]
• 17: T. S. E. Ng and H. Zhang. Predicting Internet Network Distance with Coordinates-Based Approaches. In Proceedings of IEEE INFOCOM, June 2002.
• 18: T. S. E. Ng and H. Zhang. Predicting Internet Network Distance with Coordinates-Based Approaches. In Proc. of IEEE INFOCOM, 2002.
• 19: U. of Oregon Route Views Archive Project. http://www.routeviews.org.
• 20: Jitendra Padhye , Victor Firoiu , Don Towsley , Jim Kurose, Modeling TCP throughput: a simple model and its empirical validation, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.303-314, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 21: Vern Edward Paxson, Measurements and analysis of end-to-end Internet dynamics, University of California at Berkeley, Berkeley, CA, 1998
• 22: D. Pei, L. Wang, D. Massey, S. F. Wu, and L. Zhang. A Study of Packet Delivery Performance during Routing Convergence. In Proc. of IEEE International Conference on Dependable Systems and Networks (DSN), 2003.
• 23: PlanetLab. http://www.planet-lab.org.
• 24: Shansi Ren , Lei Guo , Xiaodong Zhang, ASAP: an AS-Aware Peer-Relay Protocol for High Quality VoIP, Proceedings of the 26th IEEE International Conference on Distributed Computing Systems, p.70, July 04-07, 2006 [doi>10.1109/ICDCS.2006.18]
• 25: RON. http://nms.csail.mit.edu/ron/sites/.
• 26: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 27: N. Spring, R. Mahajan, and T. Anderson. Quantifying the causes of internet path inflation. In Proc. of SIGCOMM, 2003.
• 28: Lakshminarayanan Subramanian , Venkata N. Padmanabhan , Randy H. Katz, Geographic Properties of Internet Routing, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.243-259, June 10-15, 2002
• 29: S. Tao, K. Xu, A. Estepa, T. Fei, L. Gao, R. Guerin, J. Kurose, D. Towsley, and Z. -L. Zhang. Improving VoIP quality through path switching. In Proc. of INFOCOM, 2005.
• 30: S. Tao, K. Xu, A. Estepa, T. Fei, L. Gao, R. Guerin, J. Kurose, D. Towsley, and Z. -L. Zhang. Improving VoIP quality through path switching. In Proc. of INFOCOM, 2005.
• 31: Feng Wang , Lixin Gao , Jia Wang , Jian Qiu, On Understanding of Transient Interdomain Routing Failures, Proceedings of the 13TH IEEE International Conference on Network Protocols (ICNP'05), p.30-39, November 06-09, 2005 [doi>10.1109/ICNP.2005.29]
• 32: Feng Wang , Zhuoqing Morley Mao , Jia Wang , Lixin Gao , Randy Bush, A measurement study on the impact of routing events on end-to-end internet path performance, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 33: Wen Xu , Jennifer Rexford, MIRO: multi-path interdomain routing, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 34: Xiaowei Yang , David Wetherall, Source selectable path diversity via routing deflections, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 35: Xiaowei Yang , David Wetherall, Source selectable path diversity via routing deflections, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 36: B. Zhang, S. Jamin, and L. Zhang. Host Multicast: A Framework for Delivering Multicast To End Users. In Proc. of IEEE INFOCOM, June 2002.
• 37: Bo Zhang , T. S. Eugene Ng , Animesh Nandi , Rudolf Riedi , Peter Druschel , Guohui Wang, Measurement based analysis, modeling, and synthesis of the internet delay space, Proceedings of the 6th ACM SIGCOMM conference on Internet measurement, October 25-27, 2006, Rio de Janeriro, Brazil [doi>10.1145/1177080.1177091]
• 38: Ming Zhang , Junwen Lai , Arvind Krishnamurthy , Larry Peterson , Randolph Wang, A transport layer approach for improving end-to-end performance and robustness using redundant paths, Proceedings of the USENIX Annual Technical Conference 2004 on USENIX Annual Technical Conference, p.8-8, June 27-July 02, 2004, Boston, MA
• 39: 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]
• 40: B. Y. Zhao, L. Huang, J. Stribling, S. C. Rhea, A. D. Joseph, and J. Kubiatowicz. Tapestry: A Resilient Global-Scale Overlay for Service Deployment. IEEE JSAC, 2004.
• 41: Akamai. http://www.akamai.com/.
• 42: Skype. http://www.skype.com.

INDEX TERMS

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

General Terms:
Measurement, Performance

Keywords:
network delay changes, network jitter changes, routing dynamics, routing events