(a)Mobility idplidsI, RI) R2|(R2 (过3R2( Y(d, R3 (b)Multicast (c)Anycast Figure 2: Communication abstractions provided by 3. (a)Mobility: The change of the receivers address from R to R' is transparent to the sender.(b)Multicast: Every packet (d, data) is forwarded to each receiver R; that inserts the trigger(d, R;).(c)Anycast The packet matches the trigger of receiver R2. d l ds denotes an identifier of size m, where dp represents the prefix of the k most significant bits, and dg represents the suffix of the m-k least significant bits. eshing to maintain their tris goers in 3. Hosts contact an ny packet that matches d is forwarded to all members of the group 3 node when sending 3 packets or inserting triggers. This 3 node as shown in Figure 2(b). We discuss how to make this approac then forwards these packets or triggers to the 3 node responsible scalable in Section 3 for the associated identifiers. Thus, hosts need only know one 2 Note that unlike ip multicast with 3 there is no difference be. node in order to use the 3 infrastructure tween unicast or multicast packets, in either sending or receiving 2.4 Communication Primitives Provided by i3 application can switch on-the-fly from unicast to multicast by sim- We now describe how e can be used by applications to achieve ly having more hosts maintain triggers with the same identifier he more general com cation abstractions of mobility, multi For example, in a telephony application this would allow multiple cast, and anycast. parties to seamlessly join a two-party conversation. In contrast, with IP, an application has to at least change the IP destination ad 2.4.1 Mobility dress in order to switch from unicast to multicas The form of mobility addressed here is when a host(e.g, a lap p) is assigned a new address when it moves from one location to 2.4.3 Anycast another. A mobile host that changes its address from R to R as a Anycast ensures that a packet is delivered to exactly one receiver result of moving from one subnet to another can preserve the end- in a group, if any. Anycast enables server selection, a basic building to-end connectivity by simply updating each of its existing triggers block for many of todays applications. To achieve this with 33, all from(d R)to(d, R'), as shown in Figure 2(a). The sending host hosts in an anycast group maintain triggers which are identical in needs not be aware of the mobile host,s current location or address. the h most significant bits. These h bits play the role of the anycast Furthermore, since each packet is routed based on its identifier to group identifier. To send a packet to an anycast group, a sender uses the server that stores its trigger, no additional operation needs to be an identifier whose k-bit prefix matches the anycast group identi- invoked when the sender moves. Thus, 3 can maintain end-to-end fier. The packet is then delivered to the member of the group whose connectivity even when both end-points move simultaneously trigger identifier best matches the packet identifier according to the With any scheme that supports mobility, efficiency is a major longest prefix matching rule(see Figure 2(c). Section 3.3 gives e the last k bits of the cached at the sender, and thus subsequent packets are forwarded directly to that server via IP. This way, most packets are forwarded 2.5 Stack of identifiers through one 3 server in the overlay network. Second to al In this section, we describe a second generalization of 3, which leviate the triangle routing problem due to the trigger being stored replaces identifiers with identifier stacks. An identifier stack is a at a server far away, end-hosts can use off-I ine heuristics to choose list of identifiers that takes the form d1,d2, e d3,..,e dk)where ggers that are stored at 3 servers close to themselves( see Sec di is either an identifier or an address. Packets p and triggers t ar thus of the form. 2.4.2 Multicast Packetp=(edstack, data) Creating a multicast group is equivalent to having all members of the group register triggers with the same identifier d. As a result,￾✁￾✁￾✁￾ ✂✁✂✁✂ ✄✁✄✁✄✁✄ ☎✁☎✁☎ ✆✁✆✁✆✁✆ ✝✁✝✁✝ ✞✁✞✁✞✁✞ ✟✁✟✁✟✁✟ ✠✁✠✁✠✁✠ ✠✁✠✁✠✁✠ ✡✁✡✁✡ ✡✁✡✁✡ ☛✁☛✁☛✁☛ ☛✁☛✁☛✁☛ ☞✁☞✁☞✁☞ ☞✁☞✁☞✁☞ ✌✁✌✁✌✁✌ ✍✁✍✁✍✁✍ (id |id , R1) p s1 (id |id , R2) p s2 (id |id , R3) p s3 (id |id , data) p s ✎✁✎✁✎✁✎ ✎✁✎✁✎✁✎ ✏✁✏✁✏ ✏✁✏✁✏ (a) Mobility ✑✁✑✁✑✁✑ ✑✁✑✁✑✁✑ ✒✁✒✁✒✁✒ ✒✁✒✁✒✁✒ ✓✁✓✁✓✁✓ ✔✁✔✁✔✁✔ receiver (R2) receiver (R1) receiver (R3) ✕✁✕✁✕✁✕ ✖✁✖✁✖ ✗✁✗✁✗✁✗ ✘✁✘✁✘✁✘ (b) Multicast (id, R2) sender (S) (R2, data) (id, R1) (id, R3) receiver (R2) (R3, data) receiver (R1) (R1, data) (id, data) receiver (R3) (c) Anycast (R2, data) sender (S) (id, data) sender (S) receiver (R’) (id, R) (id, data) sender (S) receiver (R) (R, data) (id, R’) (R’, data) Figure 2: Communication abstractions provided by ☎✝✆. (a) Mobility: The change of the receiver’s address from ✶ to ✶✚✙ is transparent to the sender. (b) Multicast: Every packet ✷ ☎✦✸✠✹✕✸✾✽❀✿❁✽❂✻ is forwarded to each receiver ✶✜✛ that inserts the trigger ✷ ☎❅✸✠✹✑✶✢✛ ✻ . (c) Anycast: The packet matches the trigger of receiver ✶✼▲. ☎❅✸✤✣✦✥ ☎❅✸★✧ denotes an identifier of size ❇, where ☎❅✸✩✣ represents the prefix of the ❉ most significant bits, and ☎✦✸✧ represents the suffix of the ❇✫✪ ❉ least significant bits. periodic refreshing to maintain their triggers in ☎✝✆. Hosts contact an ☎✝✆ node when sending ☎✝✆ packets or inserting triggers. This ☎✝✆ node then forwards these packets or triggers to the ☎✝✆ node responsible for the associated identifiers. Thus, hosts need only know one ☎✝✆ node in order to use the ☎ ✆ infrastructure. 2.4 Communication Primitives Provided by ❃✚❄ We now describe how ☎✝✆ can be used by applications to achieve the more general communication abstractions of mobility, multi￾cast, and anycast. 2.4.1 Mobility The form of mobility addressed here is when a host (e.g., a lap￾top) is assigned a new address when it moves from one location to another. A mobile host that changes its address from ✶ to ✶✬✙ as a result of moving from one subnet to another can preserve the end￾to-end connectivity by simply updating each of its existing triggers from ✷ ☎❅✸✠✹✑✶✼✻ to ✷ ☎❅✸✠✹✑✶✢✙ ✻ , as shown in Figure 2(a). The sending host needs not be aware of the mobile host’s current location or address. Furthermore, since each packet is routed based on its identifier to the server that stores its trigger, no additional operation needs to be invoked when the sender moves. Thus, ☎✝✆ can maintain end-to-end connectivity even when both end-points move simultaneously. With any scheme that supports mobility, efficiency is a major concern [25]. With ☎ ✆, applications can use two techniques to achieve efficiency. First, the address of the server storing the trigger is cached at the sender, and thus subsequent packets are forwarded directly to that server via IP. This way, most packets are forwarded through only one ☎ ✆ server in the overlay network. Second, to al￾leviate the triangle routing problem due to the trigger being stored at a server far away, end-hosts can use off-line heuristics to choose triggers that are stored at ☎ ✆ servers close to themselves (see Sec￾tion 4.5 for details). 2.4.2 Multicast Creating a multicast group is equivalent to having all members of the group register triggers with the same identifier ☎✦✸. As a result, any packet that matches ☎❅✸ is forwarded to all members of the group as shown in Figure 2(b). We discuss how to make this approach scalable in Section 3.4. Note that unlike IP multicast, with ☎✝✆ there is no difference be￾tween unicast or multicast packets, in either sending or receiving. Such an interface gives maximum flexibility to the application. An application can switch on-the-fly from unicast to multicast by sim￾ply having more hosts maintain triggers with the same identifier. For example, in a telephony application this would allow multiple parties to seamlessly join a two-party conversation. In contrast, with IP, an application has to at least change the IP destination ad￾dress in order to switch from unicast to multicast. 2.4.3 Anycast Anycast ensures that a packet is delivered to exactly one receiver in a group, if any. Anycast enables server selection, a basic building block for many of today’s applications. To achieve this with ☎✝✆, all hosts in an anycast group maintain triggers which are identical in the ❉ most significant bits. These ❉ bits play the role of the anycast group identifier. To send a packet to an anycast group, a sender uses an identifier whose ❉-bit prefix matches the anycast group identi- fier. The packet is then delivered to the member of the group whose trigger identifier best matches the packet identifier according to the longest prefix matching rule (see Figure 2(c)). Section 3.3 gives two examples of how end-hosts can use the last ❇✭✪ ❉ bits of the identifier to encode their preferences. 2.5 Stack of Identifiers In this section, we describe a second generalization of ☎✝✆, which replaces identifiers with identifier stacks. An identifier stack is a list of identifiers that takes the form ✷ ☎✦✸ ■ ✹ ☎❅✸✯✮✎✹ ☎❅✸★✰✬✹✲✱✳✱✲✱ ✹ ☎❅✸✯✴✤✻ where ☎❅✸★✛ is either an identifier or an address. Packets ✵ and triggers ✿ are thus of the form: ✶ Packet ✵ ❏ ✷ ☎❅✸✧✕❍✸✷✺✹ ✴✒✹✺✸✾✽✾✿✕✽❂✻ ✶ Trigger ✿✢❏ ✷ ☎❅✸✠✹ ☎❅✸✯✧❁❍✸✷✲✹ ✴ ✻