Ankit Singla
Sylvia Ratnasamy
ABSTRACT
We introduce a protocol which routes on flat, location-independent identifiers with guaranteed scalability and low stretch. Our design builds on theoretical advances in the area of compact routing, and is the first to realize these guarantees in a dynamic distributed setting.
- I. Abraham, A. Badola, D. Bickson, D. Malkhi, S. Maloo, and S. Ron. Practical locality-awareness for large scale information sharing. In Proc. IPTPS, 2005. Google Scholar
Digital Library
- I. Abraham, C. Gavoille, and D. Malkhi. Routing with improved communication-space trade-off. Lecture notes in computer science, pages 305--319, 2004.Google Scholar
- I. Abraham, C. Gavoille, D. Malkhi, N. Nisan, and M. Thorup. Compact name-independent routing with minimum stretch. In SPAA '04: Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, pages 20--24, New York, NY, USA, 2004. ACM. Google ScholarDigital Library
- I. Abraham, D. Malkhi, and O. Dobzinski. Land: Stretch (1 + e) locality-aware networks for dhts. In Proc. SODA, pages 550--559, 2004. Google ScholarDigital Library
- D. G. Andersen, H. Balakrishnan, N. Feamster, T. Koponen, D. Moon, and S. Shenker. Accountable Internet Protocol (AIP). In ACM SIGCOMM, Seattle, WA, August 2008. Google ScholarDigital Library
- M. Arias, L. J. Cowen, K. A. Laing, R. Rajaraman, and O. Taka. Compact routing with name independence. In SPAA '03: Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, pages 184--192, New York, NY, USA, 2003. ACM. Google ScholarDigital Library
- B. Awerbuch, A. Bar-noy, N. Linial, and D. Peleg. Compact distributed data structures for adaptive routing. In Proc. STOC, pages 479--489. ACM Press, 1989. Google ScholarDigital Library
- J. Brutlag. Speed matters for Google web search, June 2009. http://code.google.com/speed/files/delayexp.pdf.Google Scholar
- M. Caesar, M. Castro, E. Nightingale, G. O'Shea, and A. Rowstron. Virtual ring routing: network routing inspired by DHTs. ACM SIGCOMM Computer Communication Review, 36(4):362, 2006. Google ScholarDigital Library
- M. Caesar, T. Condie, J. Kannan, K. Lakshminarayanan, I. Stoica, and S. Shenker. ROFL: routing on flat labels. In ACM SIGCOMM, 2006. Google ScholarDigital Library
- D. Clark. The design philosophy of the DARPA Internet protocols. In Proc. SIGCOMM, page 114, 1988. Google ScholarDigital Library
- D. Clark, R. Braden, A. Falk, and V. Pingali. Fara: reorganizing the addressing architecture. SIGCOMM Comput. Commun. Rev., 33(4):313--321, 2003. Google ScholarDigital Library
- D. Farinacci, V. Fuller, D. Meyer, and D. Lewis. Locator/ID separation protocol (LISP). In Internet-Draft, March 2009.Google Scholar
- R. Fonseca, S. Ratnasamy, J. Zhao, C. Ee, D. Culler, S. Shenker, and I. Stoica. Beacon vector routing: Scalable point-to-point routing in wireless sensornets. In NSDI, May 2005. Google ScholarDigital Library
- B. A. Ford. UIA: A Global Connectivity Architecture for Mobile Personal Devices. PhD thesis, Massachusetts Institute of Technology, September 2008. Google ScholarDigital Library
- P. Fraigniaud and C. Gavoille. Memory requirement for universal routing schemes. In PODC '95: Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, pages 223--230, New York, NY, USA, 1995. ACM. Google ScholarDigital Library
- C. Gavoille. An overview on compact routing schemes. In Presentation at 2nd Research Workshop on Flexible Network Design, October 2006. http://www.aladdin.cs.cmu.edu/workshops/netdes2/slides/gavoille.pdf.Google Scholar
- C. Gavoille and M. Gengler. Space-efficiency for routing schemes of stretch factor three. J. Parallel Distrib. Comput., 61(5):679--687, 2001. Google ScholarDigital Library
- P. B. Godfrey, I. Ganichev, S. Shenker, and I. Stoica. Pathlet routing. In ACM SIGCOMM, 2009. Google ScholarDigital Library
- M. Gritter and D. R. Cheriton. An architecture for content routing support in the internet. In USENIX Symposium on Internet Technologies and Systems, March 2001. Google ScholarDigital Library
- P. Jokela, P. Nikander, J. Melen, J. Ylitalo, and J. Wall. Host identity protocol-extended abstract. In Wireless World Research Forum, February 2004.Google Scholar
- D. Karger, E. Lehman, T. Leighton, R. Panigrahy, M. Levine, and D. Lewin. Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the world wide web. In Proc. STOC, pages 654--663, New York, NY, USA, 1997. ACM. Google ScholarDigital Library
- B. Karp and H. Kung. GPSR: greedy perimeter stateless routing for wireless networks. In Proc. MobiCom, pages 243--254. ACM, August 2000. Google ScholarDigital Library
- E. Karpilovsky and J. Rexford. Using forgetful routing to control BGP table size. In CoNEXT, 2006. Google ScholarDigital Library
- R. Kessler and J. Schwarzmeier. CRAY T3D: A new dimension for Cray Research. Compcon Spring'93, Digest of Papers., pages 176--182, 1993.Google ScholarCross Ref
- C. Kim, M. Caesar, and J. Rexford. Floodless in SEATTLE: A Scalable Ethernet Architecture for Large Enterprises. In ACM SIGCOMM, Seattle, WA, August 2008. Google ScholarDigital Library
- L. Kleinrock and F. Kamoun. Hierarchical routing for large networks: Performance evaluation and optimization. Computer Networks, 1(3):155--174, January 1977.Google Scholar
- T. Koponen, M. Chawla, B. Chun, A. Ermolinskiy, K. Kim, S. Shenker, and I. Stoica. A data-oriented (and beyond) network architecture. ACM SIGCOMM Computer Communication Review, 37(4):192, 2007. Google ScholarDigital Library
- D. Krioukov, K. Fall, and X. Yang. Compact routing on Internet-like graphs. In IEEE INFOCOM, volume 1, pages 209--219. Citeseer, 2004.Google ScholarCross Ref
- D. Krioukov, kc claffy, K. Fall, and A. Brady. On compact routing for the internet. ACM SIGCOMM Computer Communication Review, 37(3):52, 2007. Google ScholarDigital Library
- K. Levchenko, G. Voelker, R. Paturi, and S. Savage. XL: An efficient network routing algorithm. In ACM SIGCOMM, pages 15--26, August 2008. Google ScholarDigital Library
- G. S. Manku, M. Bawa, P. Raghavan, and V. Inc. Symphony: Distributed hashing in a small world. In Proceedings of the 4th USENIX Symposium on Internet Technologies and Systems, pages 127--140, 2003. Google ScholarDigital Library
- G. S. Manku, M. Naor, and U. Wieder. Know thy neighbor's neighbor: the power of lookahead in randomized p2p networks. In Proc. STOC, pages 54--63, 2004. Google ScholarDigital Library
- Y. Mao, F. Wang, L. Qiu, S. Lam, and J. Smith. S4: Small state and small stretch routing protocol for large wireless sensor networks. In Proc. NSDI, April 2007. Google ScholarDigital Library
- D. Mazieres, M. Kaminsky, M. Kaashoek, and E. Witchel. Separating key management from file system security. In ACM SOSP, December 1999. Google ScholarDigital Library
- S. Nath, P. B. Gibbons, S. Seshan, and Z. R. Anderson. Synopsis diffusion for robust aggregation in sensor networks. In ACM SenSys, 2004. Google ScholarDigital Library
- D. Peleg and E. Upfal. A tradeoff between space and efficiency for routing tables. In Proc. STOC, pages 43--52, New York, NY, USA, 1988. ACM. Google ScholarDigital Library
- C. G. Plaxton, R. Rajaraman, and A. W. Richa. Accessing nearby copies of replicated objects in a distributed environment. In Proc. SPAA, pages 311--320, New York, NY, USA, 1997. ACM. Google ScholarDigital Library
- A. Rowstron and P. Druschel. Pastry: Scalable, Distributed Object Location and Routing for Large-scale Peer-to-Peer Systems. In Proc. Middleware, 2001. Google ScholarDigital Library
- M. Särelä, T. R. Aho, and T. Tarkoma. RTFM: Publish/subscribe internetworking architecture. ICT Mobile Summit, 2008.Google Scholar
- A. Singla, P. B. Godfrey, K. Fall, G. Iannaccone, and S. Ratnasamy. Scalable routing on flat names, July 2010. http://www.cs.illinois.edu/homes/singla2/compactrouting.pdf. Google ScholarDigital Library
- I. Stoica, D. Adkins, S. Zhuang, S. Shenker, and S. Surana. Internet indirection infrastructure. In Proc. SIGCOMM, pages 73--86. ACM New York, NY, USA, 2002. Google ScholarDigital Library
- I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. In Proc. SIGCOMM, 2001. Google ScholarDigital Library
- M. Thorup and U. Zwick. Compact routing schemes. In Proc. SPAA, pages 1--10. ACM, 2001. Google ScholarDigital Library
- P. F. Tsuchiya. The landmark hierarchy: a new hierarchy for routing in very large networks. In Proc. SIGCOMM, pages 35--42, New York, NY, USA, 1988. ACM. Google ScholarDigital Library
- M. Walfish, H. Balakrishnan, and S. Shenker. Untangling the Web from DNS. In Proc. NSDI, page 17. USENIX Association, 2004. Google ScholarDigital Library
- C. Westphal and J. Kempf. A compact routing architecture for mobility. In Proc. MobiArch, pages 1--6. ACM, 2008. Google ScholarDigital Library
- Young Hyun, Bradley Huffaker, Dan Andersen, Emile Aben, Colleen Shannon, Matthew Luckie, and kc claffy. The CAIDA IPv4 Routed /24 Topology Dataset. http://www.caida.org/data/active/ipv4_routed_24_topology_dataset.xml (accessed on 2009--11).Google Scholar
- Young Hyun, Bradley Huffaker, Dan Andersen, Emile Aben, Matthew Luckie, kc claffy, and Colleen Shannon. The IPv4 Routed /24 AS Links Dataset. http://www.caida.org/data/active/ipv4_routed_topology_aslinks_dataset.xml (accessed on 2009--11).Google Scholar
- B. Y. Zhao, J. D. Kubiatowicz, and A. D. Joseph. Tapestry: An infrastructure for fault-tolerant wide-area location and routing. Technical Report UCB/CSD-01-1141, UC Berkeley, Apr. 2001. Google ScholarDigital Library
Index Terms
- Scalable routing on flat names
Recommendations
Scalable routing in delay tolerant networks
MobiHoc '07: Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computingThe non-existence of an end-to-end path poses a challenge inadapting the traditional routing algorithms to delay tolerantnetworks (DTNs). Previous works include centralized rout-ing approaches based on deterministic mobility, ferry-basedrouting with ...
Scalable Routing in Cyclic Mobile Networks
The nonexistence of an end-to-end path poses a challenge in adapting traditional routing algorithms to delay-tolerant networks (DTNs). Previous works have covered centralized routing approaches based on deterministic mobility, ferry-based routing with ...
Scalable routing overlay networks
Routing overlays have become a viable approach to working around slow BGP convergence and sub-optimal path selection, as well as to deploy novel forwarding architectures. A common sub-component of a routing overlay is a routing mesh: the route-selection ...
Comments