,R) Trigger(t) (id,R) Figure 1:(a)i3s APl. Example illustrating communication between two nodes. (b) The receiver R inserts trigger(id, R).(e)The sender sends packet (id, data ). ditional aspects of the design such as scalability and efficient rout- inserts the trigger(id, R)into the network. When a packet is sent ing. Section 5 describes some simulation results on 3 performance to identifier id, the trigger causes it to be forwarded via IP to R along with a discussion on an initial implementation. Related work Thus, much as in IP multicast, the identifier id represents a log- discussed in Section 6, followed by a discussion on future work cal rendezvous between the sender's packets and the receiver's Section 7. We conclude with a summary in Section 8 trigger. This level of indirection decouples the sender from the receiver. The senders need neither be aware of the number of re- 2. 23OVERVIEW ceivers nor their location Similarly receivers need not be aware of In this section we present an overview of 23. We start with the the number or location of senders The above description is the simplest form of the abstraction. basic service model and communication abstraction, then briefly We now describe a generalization that allows inexact matching be- describe 83s design tween identifiers. (A second generalization that replaces identi- 2.1 Service model fiers with a stack of identifiers is described in Section 2. 5.) We The purpose of 13 is to provide indirection; that is, it sume identifiers are m bits long and that there is some exact-mate es threshold k with k m. We then say that an identifier id, in the act of sending from the act of receiving. The 13 service model trigger matches an identifier id in a packet if and only if s simple: sources send packets to a logical identifier, and receivers express interest in packets sent to an identifier. Delivery is best (a)id and id have a prefix match of at least k bits, and e ffort like in todays Internet, with no guarantees about packet de here is no trigger with an identifier that has a longer prefix This service model is similar to that of Ip multicast. The cru match with id cial difference is that the 23 equivalent of an IP multicast join is more flexible. IP multicast offers a receiver a binary decision of In other words, a trigger identifier idt matches a packet identi- whether or not to receive packets sent to that group(this can fier id if and only if idt is a longest prefix match(among all other indicated on a per-source basis). It is up to the multicast infrastruc trigger identifiers) and this prefix match is at least as long as the ture to build efficient delivery trees. The i3 equivalent of a join is exact-match threshold k. The value h is chosen to be large enough nserting a trigger. This operation is more flexible than an IP mul- so that the probability that two randomly chosen identifiers match ticast join as it allows receivers to control the routing of the packe is negligible. This allows end-hosts to choose the identifiers inde This provides two advantages. First, it allows them to create, at the pendently with negligible chance of collision application level, services such as mobility, anycast, and service 2.3 Overview of the design composition out of this basic service model. Thus, this one simple service model can be used to support a wide variety of application- We now briefly describe the infrastructure that supports this ren- level communication abstractions, alleviating the need for many dezvous communication abstraction; a more in-depth description parallel and redundant overlay infrastructures. Second, the infras- follows in Section 4. 23 is an overlay network which consists of tructure can give responsibility for efficient tree construction to the a set of servers that store triggers and forward packets(using IP) end-hosts. This allows the infrastructure to remain simple, robust, between 23 nodes and to end-hosts. Identifiers and triggers have meaning only in this 23 overlay One of the main challenges in implementing 23 is to efficiently 2.2 Rendezvous-Based Communication match the identifiers in the packets to those in triggers. This he service model is instantiated as a rendezvous-based com- done by mapping each identifier to a unique 23 node(server);at munication abstraction. In their simplest form, packets are pairs ny given time there is a single 23 node responsible for a given id data)where id is an m-bit identifier and data consists of When a trigger(id, addr) is inserted, it is stored on the i3 node a payload(typically a normal IP packet payload). Receivers use responsible for id. When a packet is sent to id it is routed by i3 to goers to indicate their interest in packets. In the simplest form, the node responsible for id; there it is matched against any triggers triggers are pairs(id, addr ), where id represents the trigger iden- for that &d and forwarded(using IP tifier, and addr represents a node's address which consists of an sent to that identifier. To facilitate inexact matching, we require that IP address and a port number. A trigger(id, addr)indicates that all id s that agree in the first k bits be stored on the same i3 serv all packets with an identifier id should be forwarded(at the IP The longest prefix match required for inexact matching can then be level) by the 23 infrastructure to the node identified by addr. More executed at a single node(where it can be done efficiently) specifically, the rendezvous-based communication abstraction ex Note that packets are not stored in 3; they are only forwarded. 23 ports three basic primitives as shown in Figure 1(a). ovides a best-effort service like todays Internet. i3 implements Figure I(b) illustrates the communication between two nodes neither reliability nor ordered delivery on top of IP, End-hosts use where receiver R wants to receive packets sent to id. The receiver In our implementation we choose m= 256 and k =128￾✂✁’s Application Programming Interface (API) ✄✆☎✞✝✠✟☛✡✌☞✎✍✑✏✒☎✞✓✕✔✖✘✗ send packet ￾✝✠✄✞☎✆✙✚✓✜✛✢✙ ￾✜✣☛✣ ☎✞✙✤✔✥✓✦✗ insert trigger ✙✧☎✆★✪✩✞✫✬☎✑✛✢✙ ￾✜✣☛✣ ☎✞✙✤✔✥✓✦✗ remove trigger (a) ✭✮✭✮✭✮✭ ✯✮✯✮✯ ✰✮✰✮✰✮✰ ✰✮✰✮✰✮✰ ✱✮✱✮✱✮✱ ✱✮✱✮✱✮✱ ✲✮✲✮✲✮✲ ✳✮✳✮✳✮✳ ✴✮✴✮✴✮✴ ✵✮✵✮✵ (id, R) (b) (id, R) (c) sender (S) (R, data) (id, data) receiver (R) sender (S) receiver (R) Figure 1: (a) ☎✝✆’s API. Example illustrating communication between two nodes. (b) The receiver ✶ inserts trigger ✷ ☎✦✸✠✹✺✶✼✻ . (c) The sender sends packet ✷ ☎✦✸✠✹✕✸✾✽❀✿❁✽❂✻ . ditional aspects of the design such as scalability and efficient rout￾ing. Section 5 describes some simulation results on ☎ ✆ performance along with a discussion on an initial implementation. Related work is discussed in Section 6, followed by a discussion on future work Section 7. We conclude with a summary in Section 8. 2. ❃✚❄ OVERVIEW In this section we present an overview of ☎✝✆. We start with the basic service model and communication abstraction, then briefly describe ☎✝✆’s design. 2.1 Service Model The purpose of ☎✝✆ is to provide indirection; that is, it decouples the act of sending from the act of receiving. The ☎✝✆ service model is simple: sources send packets to a logical identifier, and receivers express interest in packets sent to an identifier. Delivery is best￾effort like in today’s Internet, with no guarantees about packet de￾livery. This service model is similar to that of IP multicast. The cru￾cial difference is that the ☎✝✆ equivalent of an IP multicast join is more flexible. IP multicast offers a receiver a binary decision of whether or not to receive packets sent to that group (this can be indicated on a per-source basis). It is up to the multicast infrastruc￾ture to build efficient delivery trees. The ☎✝✆ equivalent of a join is inserting a trigger. This operation is more flexible than an IP mul￾ticast join as it allows receivers to control the routing of the packet. This provides two advantages. First, it allows them to create, at the application level, services such as mobility, anycast, and service composition out of this basic service model. Thus, this one simple service model can be used to support a wide variety of application￾level communication abstractions, alleviating the need for many parallel and redundant overlay infrastructures. Second, the infras￾tructure can give responsibility for efficient tree construction to the end-hosts. This allows the infrastructure to remain simple, robust, and scalable. 2.2 Rendezvous-Based Communication The service model is instantiated as a rendezvous-based com￾munication abstraction. In their simplest form, packets are pairs ✷ ☎❅✸✠✹✺✸✾✽✾✿❁✽❆✻ where ☎✦✸ is an ❇-bit identifier and ✸✾✽✾✿✕✽ consists of a payload (typically a normal IP packet payload). Receivers use triggers to indicate their interest in packets. In the simplest form, triggers are pairs ✷ ☎❅✸✠✹✺✽❀✸✾✸✾❈✒✻ , where ☎✦✸ represents the trigger iden￾tifier, and ✽❀✸✾✸✾❈ represents a node’s address which consists of an IP address and a port number. A trigger ✷ ☎❅✸✠✹✺✽❀✸✾✸✾❈✬✻ indicates that all packets with an identifier ☎❅✸ should be forwarded (at the IP level) by the ☎✝✆ infrastructure to the node identified by ✽❀✸✾✸✾❈. More specifically, the rendezvous-based communication abstraction ex￾ports three basic primitives as shown in Figure 1(a). Figure 1(b) illustrates the communication between two nodes, where receiver ✶ wants to receive packets sent to ☎❅✸. The receiver inserts the trigger ✷ ☎❅✸✠✹✑✶✼✻ into the network. When a packet is sent to identifier ☎✦✸, the trigger causes it to be forwarded via IP to ✶. Thus, much as in IP multicast, the identifier ☎✦✸ represents a log￾ical rendezvous between the sender’s packets and the receiver’s trigger. This level of indirection decouples the sender from the receiver. The senders need neither be aware of the number of re￾ceivers nor their location. Similarly, receivers need not be aware of the number or location of senders. The above description is the simplest form of the abstraction. We now describe a generalization that allows inexact matching be￾tween identifiers. (A second generalization that replaces identi- fiers with a stack of identifiers is described in Section 2.5.) We as￾sume identifiers are ❇ bits long and that there is some exact-match threshold ❉ with ❉❋❊●❇. We then say that an identifier ☎❅✸❂❍ in a trigger matches an identifier ☎❅✸ in a packet if and only if (a) ☎✦✸ and ☎✦✸❍ have a prefix match of at least ❉ bits, and (b) there is no trigger with an identifier that has a longer prefix match with ☎❅✸. In other words, a trigger identifier ☎❅✸❂❍ matches a packet identi- fier ☎❅✸ if and only if ☎❅✸❀❍ is a longest prefix match (among all other trigger identifiers) and this prefix match is at least as long as the exact-match threshold ❉. The value ❉ is chosen to be large enough so that the probability that two randomly chosen identifiers match is negligible.1 This allows end-hosts to choose the identifiers inde￾pendently with negligible chance of collision. 2.3 Overview of the Design We now briefly describe the infrastructure that supports this ren￾dezvous communication abstraction; a more in-depth description follows in Section 4. ☎✝✆ is an overlay network which consists of a set of servers that store triggers and forward packets (using IP) between ☎✝✆ nodes and to end-hosts. Identifiers and triggers have meaning only in this ☎ ✆ overlay. One of the main challenges in implementing ☎ ✆ is to efficiently match the identifiers in the packets to those in triggers. This is done by mapping each identifier to a unique ☎✝✆ node (server); at any given time there is a single ☎✝✆ node responsible for a given ☎❅✸. When a trigger ✷ ☎❅✸✠✹✺✽❀✸✾✸✾❈✒✻ is inserted, it is stored on the ☎✝✆ node responsible for ☎❅✸. When a packet is sent to ☎❅✸ it is routed by ☎✝✆ to the node responsible for ☎❅✸; there it is matched against any triggers for that ☎✦✸ and forwarded (using IP) to all hosts interested in packets sent to that identifier. To facilitate inexact matching, we require that all ☎✦✸’s that agree in the first ❉ bits be stored on the same ☎✝✆ server. The longest prefix match required for inexact matching can then be executed at a single node (where it can be done efficiently). Note that packets are not stored in ☎✝✆; they are only forwarded. ☎✝✆ provides a best-effort service like today’s Internet. ☎✝✆ implements neither reliability nor ordered delivery on top of IP. End-hosts use ■ In our implementation we choose ❇❑❏▼▲✤◆✎❖ and ❉P❏❘◗☛▲✎❙