IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 12, NO. 2, APRIL 2004 205Internet Indirection InfrastructureIon Stoica, Daniel Adkins, Shelley Zhuang, Scott Shenker, Fellow, IEEE, and Sonesh SuranaAbstract—Attempts to generalize the Internet’s point-to-pointcommunication abstraction to provide services like multicast, any-cast, and mobility have faced challenging technical problems anddeployment barriers. To ease the deployment of such services, thispaper proposes a general, overlay-based Internet Indirection In-frastructure( 3)that offers a rendezvous-based communicationabstraction. Instead of explicitly sending a packet to a destination,each packet is associated with an identifier; this identifier is thenused by the receiver to obtain delivery of the packet. This level ofindirection decouples the act of sending from the act of receiving,and allows3to efficiently support a wide variety of fundamentalcommunication services. To demonstrate the feasibility of this ap-proach, we have designed and built a prototype based on the Chordlookup protocol.Index Terms—Anycast, indirection, mobility, multicast, networkinfrastructure, service composition.I. INTRODUCTIONTHE original Internet architecture was designed to provideunicast point-to-point communication between fixed lo-cations. In this basic service, the sending host knows the IP ad-dress of the receiver and the job of IP routing and forwarding issimply to deliver packets to the (fixed) location of the desiredIP address. The simplicity of this point-to-point communicationabstraction contributed greatly to the scalability and efficiencyof the Internet.However, many applications would benefit from more gen-eral communication abstractions, such as multicast, anycast, andhost mobility. In these abstractions, the sending host no longerknows the identity of the receiving hosts (multicast and anycast)and the location of the receiving host need not be fixed (mo-bility). Thus, there is a significant and fundamental mismatchbetween the original point-to-point abstraction and these moregeneral ones. All attempts to implement these more general ab-stractions have relied on a layer of indirection that decouplesthe sending hosts from the receiving hosts; for example, senderssend to a group address (multicast or anycast) or a home agent(mobility), and the IP layer of the network is responsible for de-livering the packet to the appropriate location(s).Although these more general abstractions would undoubtedlybring significant benefit to end-users, it remains unclear how toManuscript received October 3, 2002; revised December 17, 2002; approvedby IEEE TRANSACTIONS ON NETWORKING Editor J. Rexford. This work wassupported by the National Science Foundation under Grants ITR-00225660,ITR-0205519, ANI-0207399, ITR-0121555, ITR-0081698, ANI-0196514, NSFCareer Award ANI-0133811, and a Hertz Foundation Fellowship.I. Stoica, D. Adkins, S. Zhuang, and S. Surana are with the Depart-ment of Electrical Engineering and Computer Science, University ofCalifornia, Berkeley, CA 94720 USA (e-mail: [email protected]; [email protected]; [email protected]; [email protected].)S. Shenker is with the International Computer Science Institute, Berkeley, CA94704 USA (e-mail: [email protected]).Digital Object Identifier 10.1109/TNET.2004.826279achieve them. These abstractions have proven difficult to imple-ment scalably at the IP layer [6], [14], [29]. Moreover, deployingadditional functionality at the IP layer requires a level of com-munity-wide consensus and commitment that is hard to achieve.In short, implementing these more general abstractions at the IPlayer poses difficult technical problems and major deploymentbarriers.In response, many researchers have turned to application-layer solutions (either end-host or overlay mechanisms) to sup-port these abstractions [6], [17], [26]. Overlay networks con-sist of logical connections between end-hosts at the applicationlevel. While these proposals achieve the desired functionality,they do so in a very disjointed fashion in that solutions for oneservice are not solutions for other services; e.g., proposals forapplication-layer multicast do not address mobility, and viceversa. As a result, many similar and largely redundant mech-anisms are required to achieve these various goals. In addition,if overlay solutions are used, adding a new abstraction requiresthe deployment of an entirely new overlay infrastructure.In this paper, we propose a single new overlay network thatserves as a general-purpose Internet Indirection Infrastructure. offers a powerful and flexible rendezvous-based com-munication abstraction; applications can easily implement a va-riety of communication services, such as multicast, anycast, andmobility, on top of this communication abstraction. Our ap-proach provides a general overlay service that avoids both thetechnical and deployment challenges inherent in IP-layer solu-tions and the redundancy and lack of synergy in more traditionalapplication-layer approaches. We, thus, hope to combine thegenerality of IP-layer solutions with the deployability of overlaysolutions.The paper is organized as follows. In Sections II and III weprovide an overview of thearchitecture and then a generaldiscussion on howmight be used in applications. Section IVcovers additional aspects of the design such as scalability andefficient routing. Section V describes some simulation resultsonperformance along with a discussion on an initial imple-mentation. Related work is discussed in Section VI, followedby a discussion on future work Section VII. We conclude witha summary in Section VIII.II. OVERVIEWIn this section we present an overview of . We start withthe basic service model and communication abstraction, thenbriefly describe the design of.A. Service ModelThe purpose ofis to provide indirection; that is, it decou-ples the act of sending from the act of receiving. Theservice1063-6692/04$20.00 © 2004 IEEE206 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 12, NO. 2, APRIL 2004Fig. 1. (a)i3’s API. Example illustrating communication between two nodes. (b) The receiverRinserts trigger(id; R). (c) The sender sends packet(id; data).model is simple: sources send packets to a logical identifier, andreceivers express interest in packets sent to an identifier. De-livery is best-effort like in today’s Internet, with no guaranteesabout packet delivery.This service model is similar to that of IP multicast. The cru-cial
View Full Document
Unlocking...