Predicting and bypassing end-to-end internet service degradations

ABSTRACT

We study the patterns and predictability of Internet End-to-End service degradations, where a degradation is a significant deviation of the round trip time between a client and a server. We use simultaneous RTT measurements collected from several locations to a large representative set of Web sites and study the duration and extent of degradations. We combine these measurements with BGP cluster information to learn on the location of the cause.We evaluate a number of predictors based upon Hidden Markov Models and Markov Models. Predictors typically exhibit a tradeoff between two types of errors, false positives (incorrect degradation prediction) and false negatives (a degradation is not predicted). The costs of these error-types is application dependent, but we capture the entire spectrum using a precision versus recall tradeoff. Using this methodology, we learn what information is most valuable for prediction (recency versus quantity of past measurements). Surprisingly, we also conclude that predictors that utilize history in a very simple way perform as well as more sophisticated ones.One important application of prediction is gateway selection, which is applicable when a LAN is connected through multiple gateways to one or several ISP's. Gateway selection can boost reliability and survivability by selecting for each connection the (hopefully) best gateway. We show that gateway selection using our predictors can reduce the degradations to half of that obtained by routing all the connections through the best gateway.

REFERENCES

• 1: Y. Rekhter and T. Li, "A border gateway protocol 4 (BGP4)," Tech. Rep., IETF, 1999, draft-ietf-idr-bgp4-09.txt.
• 2: 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
• 3: Stefan Savage , Andy Collins , Eric Hoffman , John Snell , Thomas Anderson, The end-to-end effects of Internet path selection, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.289-299, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 4: "Route science company," http://www.routescience.com/.
• 5: "Sockeye networks," http://www.sockeye.com/.
• 6: "Opnix inc.," http://www.opnix.com/.
• 7: "Netvmg," http://www.netvmg.com/.
• 8: "Radware company," http://www.radware.com/.
• 9: "Internap company," http://www.internap.com/.
• 10: Z. Fei, S. Bhattacharjee, E. W. Zegura, and M. H. Ammar, "A novel server selection technique for improving the response time of a replicated service," in Proceedings of the IEEE INFOCOM Conference, 1998.
• 11: Paul Francis , Sugih Jamin , Cheng Jin , Yixin Jin , Danny Raz , Yuval Shavitt , Lixia Zhang, IDMaps: a global internet host distance estimation service, IEEE/ACM Transactions on Networking (TON), v.9 n.5, p.525-540, October 2001 [doi>10.1109/90.958323]
• 12: 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]
• 13: 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
• 14: "IRcache home," http://www.ircache.net.
• 15: "Nanog digest 900," http://www.nanog.org/.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Internet (e.g., TCP/IP)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network monitoring
      C.2.4 Distributed Systems
          Subjects: Client/server

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

General Terms:
Management, Measurement, Performance