trade-ofifs involved by using various lookup protocols to implement [6 DEERING, S, AND CHERITON, D. R Multicast routing in 23 is a topic of future research. datagram internetworks and extended LANs. ACM While these design decisions are important, they may have lit- Transactions on Computer Systems 8, 2(May 1990),85-111 tle to do with whether 23 is ever deployed. We don't know what [7 DEMERS, A, KESHAV, S, AND SHENKER, S Analysis and the economic model of 23 would be and whether its most likely imulation of a fair queueing algorithm. In Journal of deployment would be as a single provider for-profit service (like Internetworking Research and Experience(Oct 1990), ontent distribution networks), or a multiprovider for-profit service pp 3-26. (Also in Proc. of ACM SIGCOMM'89, pages (like ISPs), or a cooperatively managed nonprofit infrastructure While deployment is always hard to achieve, 23 has the advantage [8 ESTRIN, D GoVINDAN, R, HEIDEMANN, J,AND that it can be incrementally deployed (it could even start as a sin- KUMAR, S Next century challenges: Scalable coordination gle, centrally located server! ) Moreover, it does not require the in sensor networks. In Proc. ofACAIEEE MOBICOM99 cooperation of ISPs, so third-parties can more easily provide thi Cambridge, MA, Aug 1999) service. Nonetheless, 23 faces significant hurdles before ever being [9 FRANCIS, P, AND GUMMADI, R IPNL: A NAT extended internet architecture. In Proc. ACMSIGCOMMOl(San Diego,2001),pp.6980 8. SUMMARY 0] GRIBBLE, S.D., WELSH, M, VON BEHREN, J BREWER E.A. CULLER D. E. BORISOV. N Indirection plays a fundamental role in providing solutions for mobility, anycast and multicast in the Internet. In this paper we pro- CZERWINSKI, S. E, GUMMADI, R, HILL, J.R., JOSEPH, pose a new abstraction that unifies these solutions. In particular, we A. D. KATZ. R.H. MAO. ZM.. ROSS. S. AND ZHAO propose to augment the point-to-point communication abstraction B. Y. The ninja architecture for robust internet-scale systems with a rendezvous-based communication abstraction. This level and services. Computer Networks 35, 4(2001), 473-49 f indirection decouples the sender and the receiver behaviors and [11] Georgia tech internet topology model allows us to provide natural support for mobility, anycast and mul- http://www.cc.gatech.edu/fac/ellen.Zegura/graphs.htm [12 HILDRUM, K, KUBATOWICZ, J. D, RAO, S, AND ZHAO, To demonstrate the feasibility of this approach, we have built an B. Y. Distributed Object Location in a Dynamic Network. In verlay network based on the Chord lookup system. Preliminary Proc. 14th ACM Symp. on Parallel algorithms and experience with i3 suggests that the system is highly flexible and Architectures(Aug 2002) can support relatively sophisticated applications that require mo- [13 HOLBROOK, H, AND CHERITON, D IP multicast channels bility, multicast, and/or anycast. In particular, we have developed a simple heterogeneous multicast application in which MPEG video In Proc of ACM SIGCOMA99(Cambridge, Massachusetts traffic is transcoded on the fly to H263 format. In addition, we Aug.1999,pp.65-78 haverecentlydevelopedtwootherapplicationsprovidingtranspar-[14]JavaSpaceshttp://www.javaspaces.homestead.com/ ent mobility to legacy applications [38], and a large scale reliable [15] JANNOTTI, J, GIFFORD, D. K, JOHNSON, K.L. multicast protocol [18] KAASHOEK, M. F, AND J w.O TOOLE, J. Overcast Reliable multicasting with an overlay network. In Proc. of 9. ACKNOWLEDGMENTS The authors would like to thank Sylvia Ratnasamy, Kevin Lai Karthik Lakshminarayanan, Ananthapadmanabha Rao, Adrian Per- [16] JIN, C, CHEN, Q, AND JAMIN, S. Inet: Internet topolog rig, and Randy Katz for their insightful comments that helped im- generator, 2000. Technical report CSE-TR-433-00 prove the 23 design. We thank Hui Zhang, Dawn Song, Volker University of Michigan, EECS dept, Roth, Lakshminarayanan Subramanian, Steve McCanne, Srinivasan http://topology.eecsumich.edu/inet. Keshav, and the anonymous reviewers for their useful commen [17 KATABI, D, AND WROCLAWSKI, J. A framework for that helped improve the paper scalable global ip-anycast(gia). In Proc. of SIGCOMM 2000 Stockholm, Sweden, Aug 2000), pp 3-15 10. REFERENCES [18 LAKSHMINARAYANAN, K, RAO, A, STOICA, I, AND SHENKER, S. Flexible and robust large scale multicast using [1 CALLON, R, DOOLAN, P, FELDMAN, N, FREDETTE, A, 13. Tech Rep. CS-02-1187, University of California SWALLOW. G. AND VISWANATHAN A. A framework for multiprotocol label switching, Nov. 1997. Internet Draft, [19 MOCKAPETRIS, P, AND DUNLAP, K. Develo fthe draft-ietf-mpls-framework-02.txt. Domain Name System. In Proc. ACM SIGCO [2] CARRIERO, N. The Implementation of Tuple space CA,1988),p.123-133 Machines. PhD thesis, Yale University, 1987 20] NG, T.S.E., AND ZHANG, H. Predicting internet network 3 CHERITON, D R, AND GRITTER, M. TRIAD: A new next distance with coordinates-based approaches. In Proc. o eneration Internet archite INFOCOM02(New York, NY, 2002) http://www-dsg.stanford.edu/triad/triadps.gz. 21 PARTRIDGE, C, MENDEZ, T, AND MILLIKEN, WHost 14] CHU, Y, RAO, S.G., AND ZHANG, H. A case for end anycasting service, nov 1993. RFC-1546 system multicast. In Proc of ACM SIGMETRICS00(Santa [22 RATNASAMY, S, FRANCIS, P, HANDLEY, M, KARP, R Clara, CA, June 2000), pp. 1-12. AND SHENKER. S. A scalable content-addressable network. AASHOEK. F K AND STOICA, I Wide-area cooperative storage with cfs. In In Proc. ACM SIGCOMM (San Diego, 2001), pp Proc. ACM SOSP01 Banff, Canada, 2001), pp. 202-215trade-offs involved by using various lookup protocols to implement ☎✝✆ is a topic of future research. While these design decisions are important, they may have lit￾tle to do with whether ☎✝✆ is ever deployed. We don’t know what the economic model of ☎✝✆ would be and whether its most likely deployment would be as a single provider for-profit service (like content distribution networks), or a multiprovider for-profit service (like ISPs), or a cooperatively managed nonprofit infrastructure. While deployment is always hard to achieve, ☎✝✆ has the advantage that it can be incrementally deployed (it could even start as a sin￾gle, centrally located server!). Moreover, it does not require the cooperation of ISPs, so third-parties can more easily provide this service. Nonetheless, ☎✝✆ faces significant hurdles before ever being deployed. 8. SUMMARY Indirection plays a fundamental role in providing solutions for mobility, anycast and multicast in the Internet. In this paper we pro￾pose a new abstraction that unifies these solutions. In particular, we propose to augment the point-to-point communication abstraction with a rendezvous-based communication abstraction. This level of indirection decouples the sender and the receiver behaviors and allows us to provide natural support for mobility, anycast and mul￾ticast. To demonstrate the feasibility of this approach, we have built an overlay network based on the Chord lookup system. Preliminary experience with ☎✝✆ suggests that the system is highly flexible and can support relatively sophisticated applications that require mo￾bility, multicast, and/or anycast. In particular, we have developed a simple heterogeneous multicast application in which MPEG video traffic is transcoded on the fly to H.263 format. In addition, we have recently developed two other applications: providing transpar￾ent mobility to legacy applications [38], and a large scale reliable multicast protocol [18]. 9. ACKNOWLEDGMENTS The authors would like to thank Sylvia Ratnasamy, Kevin Lai, Karthik Lakshminarayanan, Ananthapadmanabha Rao, Adrian Per￾rig, and Randy Katz for their insightful comments that helped im￾prove the ☎✝✆ design. We thank Hui Zhang, Dawn Song, Volker Roth, Lakshminarayanan Subramanian, Steve McCanne, Srinivasan Keshav, and the anonymous reviewers for their useful comments that helped improve the paper. 10. 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