Algorithmic foundations of the internet

ABSTRACT

In this paper we survey the field of Algorithmic Foundations of the Internet, which is a new area within theoretical computer science. We consider six sample topics that illustrate the techniques and challenges in this field.

REFERENCES

• 1: {Adams et al. 2000} A. Adams, T. Bu, R. Caceres, N. Duffield, T. Friedman, J. Horowitz, F. Lo Presti, S. B. Moon, V. Paxson, and D. Towsley. The Use of End-to-end Multicast Measurements for Characterizing Internal Network Behavior, May 2000.
• 2: {Adams et al. 1998} A. Adams, J. Mahdavi, M. Mathis, and V. Paxson, Creating a Scalable Architecture for Internet Measurement. 1998.
• 3: Micah Adler , Tian Bu , Ramesh K. Sitaraman , Donald F. Towsley, Tree Layout for Internal Network Characterizations in Multicast Networks, Proceedings of the Third International COST264 Workshop on Networked Group Communication, p.189-204, November 07-09, 2001
• 4: Susanne Albers , Sanjeev Arora , Sanjeev Khanna, Page replacement for general caching problems, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.31-40, January 17-19, 1999, Baltimore, Maryland, United States
• 5: {Albert et al. 2000} R. Albert, H. Jeong, and A.-L. Barabśi. Error and attack tolerance of complex networks. Nature 406, 378--482 (2000).
• 6: Yossi Azar , Amos Fiat , Anna Karlin , Frank McSherry , Jared Saia, Spectral analysis of data, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.619-626, July 2001, Hersonissos, Greece [doi>10.1145/380752.380859]
• 7: F. Baboescu , G. Varghese, Fast and scalable conflict detection for packet classifiers, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.42 n.6, p.717-735, 21 August 2003 [doi>10.1016/S1389-1286(03)00213-5]
• 8: {Barabasi 2001} A.-L. Barabási. The physics of the Web. 14, 33 (2001).
• 9: {Barabasi et al. 2000} A.-L. Barabási, R. Albert, H. Jeong, and G. Bianconi. Power-Law Distribution of the World Wide Web, Science 287, 2115 (2000).
• 10: {Barabasi and Bonabeau 2003} A.-L. Barabási, and E. Bonabeau. Scale-free networks. fi, 288(5):60, 2003.
• 11: {Barford et al. 2001} P. Barford, A. Bestavros, J. W. Byers, and M. Crovella. On the marginal utility of network topology measurements. 2001, pp. 5--17.
• 12: Steve Branigan , Hal Burch , Bill Cheswick , Frank Wojcik, What Can You Do with Traceroute?, IEEE Internet Computing, v.5 n.5, p.96, September 2001 [doi>10.1109/4236.957902]
• 13: {Bu et al. 2002} T. Bu, N. G. Duffield, F. Lo Presti, and D. F. Towsley. Network tomography on general topologies. 2002, pp. 21--30
• 14: {Bestavros 1995} A. Bestavros, Demand-based Document Dissemination for the World-Wide Web. February, 1995.
• 15: {Bestavros et al. 1995} A. Bestavros, R. L. Carter, M. E. Crovella, C. R. Cunha, A. Heddaya, and S. A. Mirdad. Application-Level Document Caching in the Internet. Revised March, 1995.
• 16: {Bonato et al. 2005} Anthony Bonato. A survey of models of the Web graph. To appear, in proceedings of the (CAAN), Lecture Notes in Computer Science 3405, Springer Verlag, 2005.
• 17: {Caceres et al. 1999} R. Caceres, N. G. Duffield, J. Horowitz, and D. Towsley. Multicast-based inference of network internal loss characteristics. v.45, n.7, 1999, pp. 2462--2480.
• 18: {Cao and Irani 1997} Pei Cao, and Sandy Irani. Cost-Aware WWW Proxy Caching Algorithms. In Proceedings of 1997.
• 19: {Chakrabarti 1999a} S. Chakrabarti, B. Dom, D. Gibson, J. Kleinberg, S. R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins. Hypersearching the Web. fi June 1999.
• 20: Soumen Chakrabarti , Byron E. Dom , S. Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins , David Gibson , Jon Kleinberg, Mining the Web's Link Structure, Computer, v.32 n.8, p.60-67, August 1999 [doi>10.1109/2.781636]
• 21: {Chen et al. 2002} Qian Chen, Hyunseok Chang, Ramesh Govindan, Sugih Jamin, Scott Shenker, and Walter Willinger. The Origin of Power-Laws in Internet Topologies Revisited. In Proceedings of INFOCOM, 2002.
• 22: Ludmila Cherkasova , Gianfranco Ciardo, Role of Aging, Frequency, and Size in Web Cache Replacement Policies, Proceedings of the 9th International Conference on High-Performance Computing and Networking, p.114-123, June 25-27, 2001
• 23: {Cheswick et al. 2000} Bill Cheswick, Hal Burch, and Steve Branigan. Mapping and Visualizing the Internet. 2000.
• 24: {Claffy et al. 1998} K. Claffy, G. Miller and K. Thompson. The nature of the beast: recent traffic measurements from an Internet backbone. 1998.
• 25: {Claffy et al. 1999} K. Claffy, T. E. Monk and D. McRobb. Internet Tomography. 7th January 1999.
• 26: {Dahlin et al. 1994} M. D. Dahlin, R. Y. Wang, T. E. Anderson, D. A. Patterson, Cooperative Caching: Using Remote Client Memory to Improve File System Performance. Proceedings of the pp. 267--280, 1994.
• 27: Erik D. Demaine , Alejandro López-Ortiz, A linear lower bound on index size for text retrieval, Journal of Algorithms, v.48 n.1, p.2-15, August 2003 [doi>10.1016/S0196-6774(03)00043-9]
• 28: Mikael Degermark , Andrej Brodnik , Svante Carlsson , Stephen Pink, Small forwarding tables for fast routing lookups, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.3-14, September 14-18, 1997, Cannes, France
• 29: Erik D. Demaine , Alejandro López-Ortiz , J. Ian Munro, Adaptive set intersections, unions, and differences, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.743-752, January 09-11, 2000, San Francisco, California, United States
• 30: David Eppstein , S. Muthukrishnan, Internet packet filter management and rectangle geometry, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.827-835, January 07-09, 2001, Washington, D.C., United States
• 31: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 32: {Francis et al. 1999} P. Francis, S. Jamin, V. Paxson, L. Zhang, D. F. Gryniewicz, Y. Jin. An Architecture for a Global Internet Host Distance Estimation Service. 1999, pp. 210--217.
• 33: Richard F. Geary , Rajeev Raman , Venkatesh Raman, Succinct ordinal trees with level-ancestor queries, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 34: David Gibson , Jon Kleinberg , Prabhakar Raghavan, Inferring Web communities from link topology, Proceedings of the ninth ACM conference on Hypertext and hypermedia : links, objects, time and space---structure in hypermedia systems: links, objects, time and space---structure in hypermedia systems, p.225-234, June 20-24, 1998, Pittsburgh, Pennsylvania, United States [doi>10.1145/276627.276652]
• 35: Steven Glassman, A caching relay for the World Wide Web, Selected papers of the first conference on World-Wide Web, p.165-173, November 1994, Geneva, Switzerland
• 36: {Golding and Long 1991} R. Golding, and D. D. E. Long, Accessing Replicated Data in a Large-Scale Distributed System. January, 1991.
• 37: {Golynski et al. 2003} Alexander Golynski, Alejandro López-Ortiz, and Ray Sweidan. Exploiting Statistics of Web Traces to Improve Caching Algorithms. 2003.
• 38: Roberto Grossi , Jeffrey Scott Vitter, Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.397-406, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335351]
• 39: {Gwertzman and Seltzer 1994} J. Gwertzman, and M. Seltzer. The Case for Geographical Push-Caching, in VINO: The 1994 Fall Harvest, December, 1994.
• 40: {Gwertzman 1995} J. Gwertzman. Autonomous Replication in Wide-Area Internetworks. April, 1995.
• 41: {Henzinger 2004} Monika R. Henzinger. Algorithmic Challenges in Web Search Engines. vol. 1, no. 1, 2004, pp. 115--126.
• 42: Joseph D. Horton , Alejandro López-Ortiz, On the number of distributed measurement points for network tomography, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948231]
• 43: {Internet Software Consortium 2004} Internet Software Consortium http://www.isc.org.
• 44: Sandy Irani, Page replacement with multi-size pages and applications to Web caching, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.701-710, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258666]
• 45: Sandy Irani, Competitive Analysis of Paging, Developments from a June 1996 seminar on Online algorithms: the state of the art, p.52-73, January 1998
• 46: {Jamin et al. 2000} S. Jamin, C. Jin, Y. Jin, D. Raz, Y. Shavitt, L. Zhang. On the Placement of Internet Instrumentation. 2000, pp. 295--304.
• 47: {Jeong et al. 2000} H. Jeong, B. Tombor, R. Albert, Z. Oltvai, and A.-L. Barabsi. The large-scale organization of metabolic networks. 407, pp. 651--654, 2000.
• 48: Russ Jones, Digital's World-Wide Web server: a case study, Selected papers of the first conference on World-Wide Web, p.297-306, November 1994, Geneva, Switzerland
• 49: {Kalindi and Zekauskas 1999} S. Kalidindi and M. J. Zekauskas. Surveyor: An infrastructure for Internet performance measurements. ISOC, 1999.
• 50: {Kangasharju et al. 2002} Jussi Kangasharju, James W. Roberts, Keith W. Ross. Object replication strategies in content distribution networks. 2002, vol. 25, no.4, pp. 376--383.
• 51: {Karlsson and Mahalingan 2002} Magnus Karlsson and Mallik Mahalingam. Do We Need Replica Placement Algorithms in Content Delivery Networks. In Proceedings of (WCW), 2002.
• 52: {Karlsson et al. 2002} Magnus Karlsson, Christos Karamanolis, and Mallik Mahalingam. fi. Technical Report HPL-2002, HP Laboratories, July 2002.
• 53: David Karger , Eric Lehman , Tom Leighton , Rina Panigrahy , Matthew Levine , Daniel Lewin, Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.654-663, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258660]
• 54: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.668-677, January 25-27, 1998, San Francisco, California, United States
• 55: {Kleinberg et al. 1999} J. Kleinberg, S. R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins. The Web as a graph: Measurements, models and methods. 1999.
• 56: P. Krishnan , Danny Raz , Yuval Shavitt, The cache location problem, IEEE/ACM Transactions on Networking (TON), v.8 n.5, p.568-582, Oct. 2000 [doi>10.1109/90.879344]
• 57: Ritesh Kumar , Jasleen Kaur, Efficient beacon placement for network tomography, Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, October 25-27, 2004, Taormina, Sicily, Italy [doi>10.1145/1028788.1028810]
• 58: 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
• 59: {Li et al. 1999} Bo Li, Mordecai J. Golin, Giuseppe F. Italiano, Xin Deng and Kazem Sohraby. On the optimal placement of web proxies in the internet. Proceedings of (INFOCOM) 1999, pp.1282--1290.
• 60: {López-Ortiz and Germán 1996} A. López-Ortiz and D. M. Germán. A Multicollaborative Push-Caching HTTP Protocol for the WWW, (WWW96), 1996.
• 61: Udi Manber , Gene Myers, Suffix arrays: a new method for on-line string searches, SIAM Journal on Computing, v.22 n.5, p.935-948, Oct. 1993 [doi>10.1137/0222058]
• 62: Zhuoqing Morley Mao , Jennifer Rexford , Jia Wang , Randy H. Katz, Towards an accurate AS-level traceroute tool, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863996]
• 63: {Mao et al. 2004} Zhuoqing Morley Mao, David Johnson, Jennifer Rexford, Jia Wang, and Randy Katz. Scalable and Accurate Identification of AS-Level Forwarding Paths. Proceedings of (INFOCOM), 2004.
• 64: Evangelos P. Markatos, Main memory caching of Web documents, Proceedings of the fifth international World Wide Web conference on Computer networks and ISDN systems, p.893-905, May 1996, Paris, France
• 65: S. Muthukrishnan, Efficient algorithms for document retrieval problems, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.657-666, January 06-08, 2002, San Francisco, California
• 66: {Page et al. 1999} Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The PageRank Citation Ranking: Bringing Order to the Web. 1999-66.
• 67: {Paxson 1997} V. Paxson. Measurements and Analysis of End-to-End Internet Dynamics. 1997.
• 68: {Paxson et al. 1998} V. Paxson, J. Mahdavi, A. Adams and M. Mathis, An Architecture for Large-Scale Internet Measurement. v.36, n.8, 1998, pp. 48--54.
• 69: {Pitkow and Recker 1994} J. E. Pitkow, M. M. Recker, A Simple Yet Robust Caching Algorithm Based on Dynamic Access Patterns. Proceedings of the (WWW94), Elsevier, May, 1994.
• 70: Priyank Warkhede , Subhash Suri , George Varghese, Multiway range trees: scalable IP lookup with fast updates, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.44 n.3, p.289-303, 20 February 2004 [doi>10.1016/j.comnet.2003.09.004]
• 71: T. Roughgarden , E. Tardos, How bad is selfish routing?, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.93, November 12-14, 2000
• 72: {Sedayao 1994} J. Sedayao. Mosaic Will Kill My Network! Studying Network Traffic. Proceedings of the (WWW94), Elsevier, May, 1994.
• 73: {Siamwalla et al. 1998} R. Siamwalla, R. Sharma, and S. Keshav. Discovering Internet Topology. Technical Report, Cornell University, July 1998.
• 74: {Skitter 2001} Cooperative Association for Internet Data Analysis (CAIDA). http://www.caida.org/tools/measurement/skitter/index.html, 2001.
• 75: {Suri et al. 2003} Subhash Suri, Tuomas Sandholm, Priyank Ramesh Warkhede. Compressing Two-Dimensional Routing Tables. vol. 35, no. 4, pp. 287--300, 2003.
• 76: {Towsley 2001} D. Towsley. Network tomography through to end-to-end measurements. Abstract in 2001.
• 77: {Vöcking 2004} Berthold Vöcking. Selfish Routing and Congestion Games: Towards a game based analysis of the Internet. Santorini, Greece, 2004. http://www.cti.gr/AAGTLSN/#LECTURERS.
• 78: Marcel Waldvogel , George Varghese , Jon Turner , Bernhard Plattner, Scalable high speed IP routing lookups, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.25-36, September 14-18, 1997, Cannes, France

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.3 Communications Applications

          Nouns: Internet

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Theory