A methodology for estimating interdomain web traffic demand

ABSTRACT

This paper introduces a methodology for estimating interdomain Web traffic lows between all clients worldwide and the ervers belonging to over one housand content providers. The idea is to use the server logs from a large ontent Delivery Network (CDN) to identify client downloads of content provider (i.e., publisher) Web pages. For each of these Web pages, a client typically downloads some objects from the content provider, some from the CDN, and perhaps some from third parties such as banner advertisement agencies. The sizes and sources of the non-CDN downloads associated with each CDN download are estimated separately by examining Web accesses in packet traces collected at several universities.

The methodology produces a (time-varying) interdomain HTTP traffic demand matrix pairing several hundred thousand blocks of client IP addresses with over ten thousand individual Web servers. When combined with geographical databases and routing tables, the matrix can be used to provide (partial) answers to questions such as "How do Web access patterns vary by country?", "Which autonomous systems host the most Web content?", and "How stable are Web traffic flows over time?".

REFERENCES

• 1: Matthew Roughan , Mikkel Thorup , Yin Zhang, Traffic engineering with estimated traffic matrices, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948237]
• 2: Yin Zhang , Matthew Roughan , Carsten Lund , David Donoho, An information-theoretic approach to traffic matrix estimation, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863990]
• 3: Stefan Saroiu , Krishna P. Gummadi , Richard J. Dunn , Steven D. Gribble , Henry M. Levy, An analysis of internet content delivery systems, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060319]
• 4: B. Krishnamurthy and J. Rexford, Web Protocols and Practice. Addison-Wesley, 2001.
• 5: Mark E. Crovella , Azer Bestavros, Self-similarity in World Wide Web traffic: evidence and possible causes, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.835-846, Dec. 1997 [doi>10.1109/90.650143]
• 6: Walter Willinger , Vern Paxson , Murad S. Taqqu, Self-similarity and heavy tails: structural modeling of network traffic, A practical guide to heavy tails: statistical techniques and applications, Birkhauser Boston Inc., Cambridge, MA, 1998
• 7: Martin F. Arlitt , Carey L. Williamson, Internet Web servers: workload characterization and performance implications, IEEE/ACM Transactions on Networking (TON), v.5 n.5, p.631-645, Oct. 1997 [doi>10.1109/90.649565]
• 8: Arun K. Iyengar , Mark S. Squillante , Li Zhang, Analysis and characterization of large-scale Web server access patterns and performance, World Wide Web, v.2 n.1-2, p.85-100, 1999 [doi>10.1023/A:1019244621570]
• 9: C. Wills and M. Mikhailov, "Studying the impact of more complete server information on Web caching," in Proc. of the 5th International Web Caching and Content Delivery Workshop, 2000.
• 10: D. Awduche, A. Chiu, A. Elwalid, I. Widjaja, and X. Xiao, "Overview and principles of Internet traffic engineering." Request for Comments 3272, 2002.
• 11: Anja Feldmann , Albert Greenberg , Carsten Lund , Nick Reingold , Jennifer Rexford , Fred True, Deriving traffic demands for operational IP networks: methodology and experience, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.257-270, August 28-September 01, 2000, Stockholm, Sweden
• 12: A. Medina , N. Taft , K. Salamatian , S. Bhattacharyya , C. Diot, Traffic matrix estimation: existing techniques and new directions, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 13: A. Medina, C. Fraleigh, N. Taft, S. Bhattacharyya, and C. Diot, "A taxonomy of IP traffic matrices," in Workshop on Scalability and Traffic Control in IP Networks at the SPIE ITCOM+OPTICOMM Conference, 2002.
• 14: X. Xiao, A. Hannan, B. Bailey, and L. Ni, "Traffic engineering with MPLS in the Internet," IEEE Network Magazine, 2000.
• 15: K. Thompson, G. Miller, and R. Wilder, "Wide-area Internet traffic patterns and characteristics," IEEE Network Magazine, 1997.
• 16: V. Paxson, G. Almes, J. Mahdavi, and M. Mathis, "Framework for IP performance metrics." Request for Comments 2330, 1998.
• 17: Matthew Roughan , Albert Greenberg , Charles Kalmanek , Michael Rumsewicz , Jennifer Yates , Yin Zhang, Experience in measuring backbone traffic variability: models, metrics, measurements and meaning, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637213]
• 18: Yin Zhang , Matthew Roughan , Nick Duffield , Albert Greenberg, Fast accurate computation of large-scale IP traffic matrices from link loads, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA
• 19: Augustin Soule , Antonio Nucci , Rene Cruz , Emilio Leonardi , Nina Taft, How to identify and estimate the largest traffic matrix elements in a dynamic environment, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 20: G. Liang and B. Yu, "Pseudo likelihood estimation in network tomography," in Proc. IEEE INFOCOM, March 2003.
• 21: B. Fortz, J. Rexford, and M. Thorup, "Traffic engineering with traditional IP routing protocols," in IEEE Communication Magazine, 2002.
• 22: Nick Feamster , Hari Balakrishnan, Towards a logic for wide-area Internet routing, Proceedings of the ACM SIGCOMM workshop on Future directions in network architecture, August 25-27, 2003, Karlsruhe, Germany
• 23: B. Quoitin, S. Uhlig, C. Pelsser, L. Swinnen, and O. Bonaventure, "Interdomain traffic engineering with BGP," IEEE Communications Magazine, Internet Technology Series, 2003.
• 24: B. Quoitin, S. Uhlig, and O. Bonaventure, "Using redistribution communities for interdomain traffic engineering," in Quality of Future Internet Services (QoFIS 2002), 2002.
• 25: S. Uhlig, O. Bonaventure, and B. Quoitin, "Interdomain traffic engineering with minimal BGP configurations," in 18th International Teletraffic Congress (ITC), September 2003.
• 26: S. Agarwal, C.-N. Chuah, and R. Katz, "OPCA: Robust interdomain policy routing and traffic control," in IEEE Openarch, 2003.
• 27: J. Winick, S. Jamin, and J. Rexford, "Traffic engineering between neighboring domains," 2002. http://www.research.att.com/ jrex/papers/interAS.pdf.
• 28: Lili Qiu , Yang Richard Yang , Yin Zhang , Scott Shenker, On selfish routing in internet-like environments, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863974]
• 29: B. Lavoie and H. Nielsen, "Web characterization terminology & definitions sheet." http://www.w3c.org/1999/05/WCA-terms/.
• 30: Scott Hull, Content Delivery Networks: Web Switching for Security, Availability, and Speed, McGraw-Hill, Inc., New York, NY, 2002
• 31: John Dilley , Bruce Maggs , Jay Parikh , Harald Prokop , Ramesh Sitaraman , Bill Weihl, Globally Distributed Content Delivery, IEEE Internet Computing, v.6 n.5, p.50-58, September 2002 [doi>10.1109/MIC.2002.1036038]
• 32: S. Gadde, J. Chase, and M. Rabinovich, "Web caching and content distribution: a view from the interior," Computer Communications, 2001.
• 33: L. Bent and G. Voelker, "Whole page performance," in In Proc. of the 7th Int. Workshop on Web Content Caching and Distribution, 2002.
• 34: K. Johnson, J. Carr, M. Day, and M. Kaashoek, "The measured performance of content distribution networks," in Proceedings of the 5th International Web Caching and Content Delivery Workshop, 2000.
• 35: Balachander Krishnamurthy , Craig Wills , Yin Zhang, On the use and performance of content distribution networks, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505224]
• 36: http://www.akamai.com.
• 37: Bassam Halabi, Internet Routing Architectures, Cisco Press, 1997
• 38: John W. Stewart, III, BGP4: Inter-Domain Routing in the Internet, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 39: Chadi Barakat , Patrick Thiran , Gianluca Iannaccone , Christophe Diot, On Internet backbone traffic modeling, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 40: N. G. Duffield , M. Grossglauser, Trajectory sampling for direct traffic observation, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.271-282, August 28-September 01, 2000, Stockholm, Sweden
• 41: W. Teeuw, "The CDN state of the art.," 2001. http://www.trc.nl/Middleware/cdn/ENindex.htm.
• 42: B. Davison, "Content delivery and distribution services," 2003. http://www.web-caching.com/cdns.html.
• 43: L. Breslau, P. Cao, L. Fan, G. Philips, and S. Shenker, "Web caching and Zipf-like distributions: Evidence and implications," in Proc. IEEE INFOCOM, 1999.
• 44: W. Fang and L. Peterson, "Inter-AS traffic patterns and their implications," in Proc. IEEE Global Internet, 1999.
• 45: "Zipf's law." http://linkage.rockefeller.edu/wli/zipf.
• 46: B. Krishnamurthy and J. Rexford, Web Protocols and Practice. Addison-Wesley, 2001.
• 47: Venkata N. Padmanabhan , Jeffrey C. Mogul, Improving HTTP latency, Computer Networks and ISDN Systems, v.28 n.1-2, p.25-35, Dec. 1995 [doi>10.1016/0169-7552(95)00106-1]
• 48: T. Kroeger, D. Long, and J. Mogul, "Exploring the bounds of Web latency reduction from caching and prefetching," in Proc. USENIX Symp. on Internet Technologies and Systems, 1997.
• 49: Anja Feldmann, BLT: Bi-layer tracing of HTTP and TCP&slash;IP, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.321-335, June 2000, Amsterdam, The Netherlands
• 50: H. Balakrishnan, V. Padmanabhan, S. Seshan, M. Stemm, and R. Katz, "TCP behavior of a busy Internet server: Analysis and improvements," in Proc. IEEE INFOCOM, 1998.
• 51: S. Gribble and E. Brewer, "System design issues for Internet middleware services: Deductions from a large client trace," in Proc. USENIX Symp. on Internet Technologies and Systems, 1997.
• 52: B. Liu, "A different approach to content delivery." http://www.isp-planet.com/news/2001/routescience.html.
• 53: Vern Paxson, Bro: a system for detecting network intruders in real-time, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.23-24, p.2435-2463, Dec. 1999 [doi>10.1016/S1389-1286(99)00112-7]
• 54: RouteViews project. http://www.routeviews.org/.
• 55: RIPE's Routing Information Service Raw Data Page. http://data.ris.ripe.net/.
• 56: L. Gao, "On inferring autonomous system relationships in the Internet," in Proc. IEEE Global Internet, 2000.
• 57: A. Feldmann, "Characteristics of TCP connection arrivals," in Self-Similar Network Traffic And Performance Evaluation (K. Park and W. Willinger, eds.), J. Wiley & Sons, Inc. 2000.
• 58: Robin Sommer , Anja Feldmann, NetFlow: information loss or win?, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637226]

INDEX TERMS

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

General Terms:
Algorithms, Management, Measurement

Keywords:
analysis, estimation, interdomain, traffic demand, traffic matrix, web