Internet indirection infrastructure

ABSTRACT

Attempts to generalize the Internet's point-to-point communication abstraction to provide services like multicast, anycast, and mobility have faced challenging technical problems and deployment barriers. To ease the deployment of such services, this paper proposes an overlay-based Internet Indirection Infrastructure ( I3) that offers a rendezvous-based communication abstraction. Instead of explicitly sending a packet to a destination, each packet is associated with an identifier; this identifier is then used by the receiver to obtain delivery of the packet. This level of indirection decouples the act of sending from the act of receiving, and allows I3 to efficiently support a wide variety of fundamental communication services. To demonstrate the feasibility of this approach, we have designed and built a prototype based on the Chord lookup protocol.

References

1. Callon, R., Doolan, P., Feldman, N., Fredette, A., Swallow, G., and Viswanathan, A. A framework for multiprotocol label switching, Nov. 1997. Internet Draft, draft-ietf-mpls-framework-02.txt.]]
2. Carriero, N. The Implementation of Tuple Space Machines. PhD thesis, Yale University, 1987.]]
3. Cheriton, D. R., and Gritter, M. TRIAD: A new next generation Internet architecture, Mar. 2000. http://www-dsg.stanford.edu/triad/ triad.ps.gz]]
4. Chu, Y., Rao, S. G., and Zhang, H. A case for end system multicast. In Proc. of ACM SIGMETRICS'00 (Santa Clara, CA, June 2000), pp. 1--12.]]
5. Dabek, F., Kaashoek, F., Karger, D., Morris, R., and Stoica, I. Wide-area cooperative storage with cfs. In Proc. ACM SOSP'01 (Banff, Canada, 2001), pp. 202--215.]]
6. Deering, S., and Cheriton, D. R. Multicast routing in datagram internetworks and extended LANs. ACM Transactions on Computer Systems 8, 2 (May 1990), 85--111.]]
7. Demers, A., Keshav, S., and Shenker, S. Analysis and simulation of a fair queueing algorithm. In Journal of Internetworking Research and Experience (Oct. 1990), pp. 3--26. (Also in Proc. of ACM SIGCOMM'89, pages 3-12).]]
8. Estrin, D., Govindan, R., Heidemann, J., and Kumar, S. Next century challenges: Scalable coordination in sensor networks. In Proc. of ACM/IEEE MOBICOM'99 (Cambridge, MA, Aug. 1999).]]
9. Francis, P., and Gummadi, R. IPNL: A NAT extended internet architecture. In Proc. ACM SIGCOMM'01 (San Diego, 2001), pp. 69--80.]]
10. Gribble, S. D., Welsh, M., von Behren, J. R., Brewer, E. A., Culler, D. E., Borisov, N., Czerwinski, S. E., Gummadi, R., Hill, J. R., Joseph, A. D., Katz, R. H., Mao, Z. M., Ross, S., and Zhao, B. Y. The ninja architecture for robust internet-scale systems and services. Computer Networks 35, 4 (2001), 473--497.]]
11. Georgia tech internet topology model. http://www.cc.gatech.edu/fac/Ellen.Zegura/graphs.html]]
12. Hildrum, K., Kubatowicz, J. D., Rao, S., and Zhao, B. Y. Distributed Object Location in a Dynamic Network. In Proc. 14th ACM Symp. on Parallel Algorithms and Architectures (Aug. 2002).]]
13. Holbrook, H., and Cheriton, D. IP multicast channels: EXPRESS support for large-scale single-source applications. In Proc. of ACM SIGCOMM'99 (Cambridge, Massachusetts, Aug. 1999), pp. 65--78.]]
14. Java Spaces. http://www.javaspaces.homestead.com/.]]
15. Jannotti, J., Gifford, D. K., Johnson, K. L., Kaashoek, M. F., and J. W. O'Toole, J. Overcast: Reliable multicasting with an overlay network. In Proc. of the 4th USENIX Symposium on Operating Systems Design and Implementation (OSDI 2000) (San Diego, California, October 2000), pp. 197--212.]]
16. Jin, C., Chen, Q., and Jamin, S. Inet: Internet topology generator, 2000. Technical report CSE-TR-433-00, University of Michigan, EECS dept, http://topology.eecs.umich.edu/inet.]]
17. Katabi, D., and Wroclawski, J. A framework for scalable global ip-anycast (gia). In Proc. of SIGCOMM 2000 (Stockholm, Sweden, Aug. 2000), pp. 3--15.]]
18. Lakshminarayanan, K., Rao, A., Stoica, I., and Shenker, S. Flexible and robust large scale multicast using i3. Tech. Rep. CS-02-1187, University of California - Berkeley, 2002.]]
19. Mockapetris, P., and Dunlap, K. Development of the Domain Name System. In Proc. ACM SIGCOMM (Stanford, CA, 1988), pp. 123--133.]]
20. Ng, T. S. E., and Zhang, H. Predicting internet network distance with coordinates-based approaches. In Proc. of INFOCOM'02 (New York, NY, 2002).]]
21. Partridge, C., Mendez, T., and Milliken, W. Host anycasting service, nov 1993. RFC-1546.]]
22. Ratnasamy, S., Francis, P., Handley, M., Karp, R., and Shenker, S. A scalable content-addressable network. In Proc. ACM SIGCOMM (San Diego, 2001), pp. 161--172.]]
23. Rowstron, A., and Druschel, P. Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. In Proc. of the 18th IFIP/ACM International Conference on Distributed Systems Platforms (Middleware 2001) (Nov. 2001), pp. 329--350.]]
24. Snoeren, A. C., and Balakrishnan, H. An end-to-end approach to host mobility. In Proc. of ACM/IEEE MOBICOM'99 (Cambridge, MA, Aug. 1999).]]
25. Snoeren, A. C., Balakrishnan, H., and Kaashoek, M. F. Reconsidering internet mobility. In Proc. of the 8th IEEE Workshop on Hot Topics in Operating Systems (HotOS-VIII) (Elmau/Oberbayern, Germany, May 2001).]]
26. Stoica, I., Morris, R., Karger, D., Kaashoek, M. F., and Balakrishnan, H. Chord: A scalable peer-to-peer lookup service for internet applications. In Proc. ACM SIGCOMM'01 (San Diego, 2001), pp. 149--160.]]
27. Stoica, I., Ng, T., and Zhang, H. REUNITE: A recursive unicast approach to multicast. In Proc. of INFOCOM'00 (Tel-Aviv, Israel, Mar. 2000), pp. 1644--1653.]]
28. Tanenbaum, A. S., Kaashoek, M. F., van Renesse, R., and Bal, H. E. The amoeba distributed operating system: a status report. Computer Communications 14 (1), 324--335.]]
29. Tibco software. http://www.tibco.com.]]
30. Vahdat, A., Dahlin, M., Anderson, T., and Aggarwal, A. Active names: Flexible location and transport. In Proc. of USENIX Symposium on Internet Technologies & Systems (Oct. 1999).]]
31. Vitria. http://www.vitria.com.]]
32. W. Adjie-Winoto and E. Schwartz and H. Balakrishnan and J. Lilley. The design and implementation of an intentional naming system. In Proc. ACM Symposium on Operating Systems Principles (Kiawah Island, SC, Dec. 1999), pp. 186--201.]]
33. Wetherall, D. Active network vision and reality: lessons form a capsule-based system. In Proc. of the 17th ACM Symposium on Operating System Principles (SOSP'99) (Kiawah Island, SC, Nov. 1999), pp. 64--79.]]
34. Whitaker, A., and Wetherall, D. Forwarding without loops in icarus. In Proc. of OPENARCH 2002 (New York City, NY, June 2002).]]
35. WAP wireless markup language specification (WML). http://www.oasis-open.org/cover/wap-wml.html.]]
36. Wyckoff, P., McLaughry, S. W., Lehman, T. J., and Ford, D. A. T Spaces. IBM System Journal 37, 3 (1998), 454--474.]]
37. Yarvin, C., Bukowski, R., and Anderson, T. Anonymous rpc: Low-latency protection in a 64-bit address space. In Proc. of USENIX (June 1993), pp. 175--186.]]
38. Zhuang, S., Lai, K., Stoica, I., Katz, R., and Shenker, S. Host mobility using an internet indirection infrastructure. Tech. Rep. UCB/CSD-02-1186, Computer Science Division, U. C. Berkeley, June 2002.]]

Index Terms

• Information systems

  • World Wide Web

    • Web applications

      • Internet communications tools