23_recv(p)//upon receiving packet p d= head(p id_stack); //get head ofp's stack HIML-W ML transcoder(T lis local server responsible for id's best match? if ( is Match Local(id)=FALSE) 63-forward(p); / matching trigger stored elsewhere return: HIML-WML, idh, data pop(p id_stack); //pop id from p's stack (R) set=get_matches(id); //get all triggers matching id (a)Service composition if (p id_stack=0 MPEG-H. 263 transcoder T) drop(p)∥ nowhere i3_forward(p) while(setto)forward packet to each matching trigger t= get frigger(set_) pl=copy (p); // create new packet to sene l/.add I's stack at head of pl's stack Nid, R2)F ef(R2) prepend(t id _stack, pl id_stack) ward(p1); (b) Heterogeneous multicast 23-forward(p)//sendfonward packet p Figure 4:(a) Service composition: The sender(s)specifies that id= head(p id_stack); //get head of p's stack if (type(id)=IP-ADDR_TYPE) packets should be transcoded at server T before being delivered to the destination(R).(b) Heterogeneous multicast: Receiver IP-send(id, p); // id is an IP address send p to id via IP Rl specifies that wants to receive H 263 data, while R2 specifies else that wants to receive mpeg data. The sender sends mPeg forward(p); //forward p via overlay network data Figure 3: Pseudo-code of the receiving and forward operations executed by an 3 server For each matching trigger t, the identifier stack of the trig prepended to p's identifier stack. The packet p is then forwarded based on the first identifier in its stack The generalized form of packets allows a source to send a packet 3. USING i3 to a series of identifiers much as in sour rce routin ized form of triggers allows a trigger to send a packet to another In this section we present a few examples of how i3 can be used. identifier rather than to an address This extension allows for a We discuss service composition, heterogeneous multicast, server much greater flexibility. To illustrate this point, in Sections 3. 1, 3. 2, selection, and large scale multicast. In the remainder of the paper, and 4.3, we discuss how identifier stacks can be used to provide we say that packet p matches trigger t if the first identifier of ps service composition, implement heterogeneous multicast, and in- crease 23s robustness, respectively for ser identifer z always forwarded based on the first identifier id 3.1 Service Composition A packet ck until it reaches the server who is responsible Some applications may require third parties to process the data for storing the matching trigger(s) for p. Consider a packet p with before it reaches the destination [10]. An example is a wireless n identifier stack(idi, id2, id3). If there is no trigger in i3 whose application protocol (WAP) gateway translating HTML web pages identifier matches id1, id is popped from the stack. The process is to WML for wireless devices [35]. WML is a lightweight version of repeated until an identifier in ps identifier stack matches a trigger HTML designed to run on wireless devices with small screens and If no such trigger is found, packet p is dropped. If on the other limited capabilities. In this case, the server can forward the web hand. there is a trigger t whose identifier matches id, then idi is page to a third-party server T that implements the HTML-WML replaced by t's identifier stack. In particular, if ts identifier stack transcoding, which in turn processes the data and sends it to the is(a, ) then p,s identifier stack becomes(a, 3, id2, id3). If idi destination via WAP. is an IP address, p is sent via IP to that address, and the rest of In general, data might need to be transformed by a series of Ps identifier stack, i.e,(id2, id3)is forwarded to the application. third-party servers before it reaches the destination. In today's In- The semantics of id2 and id3 are in general application-specific. ternet, the application needs to hnow the set of servers that pe owever, in this paper we consider only examples in which the form transcoding and then explicitly forward data packets via these application is expected to use these identifiers to forward the packet servers. after it has processed it. Thus, an application that receives a packet With i3, this functionality can be easily implemented by using a ith identifier stack(id2, id3) is expected to send another packet ack of identifiers. Figure 4(a) shows how data packets containing with the same identifier stack(id2, id3). As shown in the next HTML information can be redirected to the transcoder and thus section this allows 23 to provide support for service composition. arrive at the receiver containing WML information. The sender Figure 3 shows the pseudo-code of the receiving and forward- associates with each data packet the stack(id HTM L-WML, id), ing operations executed by an 23 node. Upon receiving a packet where id represents the flow identifier. As a result, the data packet server first checks whether it is responsible for storing the trig is routed first to the server which performs the transcoding. Next, ger matching packet p. If not, the server forwards the packet at the server inserts packet(id, dat a) into 23, which delivers it to the the 23 level. If yes, the code returns the set of triggers that match receiver☎✝✆ recv(✵) // upon receiving packet ✵ ☎❅✸ ❏✁￾✄✂✧✽❀✸ ✷✵ ✱ ☎✦✸ ☎ ✿✕✽✝✆❉❆✻ ; // get head of p’s stack // is local server responsible for id’s best match? if ✷ ☎✞☎✠✟✽✾✿✡✆☛￾✄☞✍✌✠✆✽✏✎❁✷ ☎❅✸✘✻✢❏ FALSE✻ ☎✝✆ forward(✵); // matching trigger stored elsewhere return; ✵✑✌✵ ✷✵✱ ☎❅✸ ☎ ✿✕✽✝✆✚❉❂✻ ; // pop id from p’s stack... ☎✒✂✚✿ ✿✢❏✔✓✏✂✚✿ ❇✽❀✿✕✆✖￾✄✂✠☎✒✷ ☎❅✸✘✻ ; // get all triggers matching id if ✷✗☎✒✂✧✿ ✿✢❏✁✘✒✻ if ✷✵ ✱ ☎❅✸ ☎ ✿✕✽✝✆❉P❏✁✘✒✻ drop(✵) // nowhere else to forward else ☎ ✆ forward ✷✵✻ ; while (☎✒✂✚✿ ✿✚✙❏✁✘) // forward packet to each matching trigger ✿ ❏✛✓✏✂✚✿ ✿✕❈☎✜✓✢✓✏✂✧❈✘✷✗☎✒✂✧✿ ✿✑✻ ; ✵◗ ❏✛✆☛✌✵✄✣ ✷✵✻ ; // create new packet to send // ... add t’s stack at head of p1’s stack ✵❆❈✤✂✵✥✂✒✦✸ ✷✜✿✺✱ ☎❅✸ ☎ ✿✕✽✝✆✚❉ ✹ ✵ ◗ ✱ ☎❅✸ ☎ ✿✕✽✝✆✚❉❂✻ ; ☎✝✆ forward(✵ ◗ ); ☎✝✆ forward(✵) // send/forward packet ✵ ☎❅✸ ❏✁￾✄✂✧✽❀✸ ✷✵ ✱ ☎✦✸ ☎ ✿✕✽✝✆❉❆✻ ; // get head of p’s stack if ✷✜✿✡✣✵✥✂✾✷ ☎❅✸✘✻ ❏ IP ADDR TYPE✻ IP send(☎❅✸✠✹ ✵); // id is an IP address; send p to id via IP else forward ✷✵✻ ; // forward ✵ via overlay network Figure 3: Pseudo-code of the receiving and forward operations executed by an ☎✝✆ server. The generalized form of packets allows a source to send a packet to a series of identifiers, much as in source routing. The general￾ized form of triggers allows a trigger to send a packet to another identifier rather than to an address. This extension allows for a much greater flexibility. To illustrate this point, in Sections 3.1, 3.2, and 4.3, we discuss how identifier stacks can be used to provide service composition, implement heterogeneous multicast, and in￾crease ☎✝✆’s robustness, respectively. A packet ✵ is always forwarded based on the first identifier ☎❅✸ in its identifier stack until it reaches the server who is responsible for storing the matching trigger(s) for ✵. Consider a packet ✵ with an identifier stack ✷ ☎❅✸ ■ ✹ ☎❅✸✮ ✹ ☎❅✸✰ ✻ . If there is no trigger in ☎ ✆ whose identifier matches ☎❅✸ ■ , ☎❅✸ ■ is popped from the stack. The process is repeated until an identifier in ✵’s identifier stack matches a trigger ✿. If no such trigger is found, packet ✵ is dropped. If on the other hand, there is a trigger ✿ whose identifier matches ☎❅✸ ■ , then ☎✦✸ ■ is replaced by ✿’s identifier stack. In particular, if ✿’s identifier stack is ✷★✧ ✹✡✣❂✻ , then ✵’s identifier stack becomes ✷★✧ ✹✡✣ ✹ ☎❅✸✮✬✹ ☎❅✸★✰✧✻ . If ☎❅✸ ■ is an IP address, ✵ is sent via IP to that address, and the rest of ✵’s identifier stack, i.e., ✷ ☎❅✸✮✎✹ ☎❅✸★✰✧✻ is forwarded to the application. The semantics of ☎❅✸✮ and ☎✦✸✰ are in general application-specific. However, in this paper we consider only examples in which the application is expected to use these identifiers to forward the packet after it has processed it. Thus, an application that receives a packet with identifier stack ✷ ☎❅✸✮✎✹ ☎❅✸★✰☛✻ is expected to send another packet with the same identifier stack ✷ ☎✦✸✮✬✹ ☎❅✸★✰☛✻ . As shown in the next section this allows ☎ ✆ to provide support for service composition. Figure 3 shows the pseudo-code of the receiving and forward￾ing operations executed by an ☎✝✆ node. Upon receiving a packet ✵, a server first checks whether it is responsible for storing the trig￾ger matching packet ✵. If not, the server forwards the packet at the ☎✝✆ level. If yes, the code returns the set of triggers that match ✩✪✩✪✩✪✩ ✫✪✫✪✫ ✬✪✬✪✬✪✬ ✭✪✭✪✭ ✮✪✮✪✮✪✮ ✯✪✯✪✯ ✰✪✰✪✰✪✰ ✱✪✱✪✱ HTML−WML transcoder (T) (id, R) (R, data) ((T, R1), data) (id, (id , R1)) MPEG−H.263 ((id , R1), data) MPEG−H.263 MPEG−H.263 transcoder (T) (id, R2) (R1, data) (R2, data) receiver (R2) receiver (R1) sender (S) (id, data) sender (S) ((T,id), data) (b) Heterogeneous multicast (a) Service composition HTML−WML MPEG−H.263 ((id , id), data) HTML−WML (id , T) (id , T) receiver (R) Figure 4: (a) Service composition: The sender (✲) specifies that packets should be transcoded at server ✳ before being delivered to the destination (✶). (b) Heterogeneous multicast: Receiver ✶◗ specifies that wants to receive H.263 data, while ✶✼▲ specifies that wants to receive MPEG data. The sender sends MPEG data. ✵. For each matching trigger ✿ , the identifier stack of the trigger is prepended to ✵’s identifier stack. The packet ✵ is then forwarded based on the first identifier in its stack. 3. USING ❃ ❄ In this section we present a few examples of how ☎✝✆ can be used. We discuss service composition, heterogeneous multicast, server selection, and large scale multicast. In the remainder of the paper, we say that packet ✵ matches trigger ✿ if the first identifier of ✵’s identifier stack matches ✿’s identifier. 3.1 Service Composition Some applications may require third parties to process the data before it reaches the destination [10]. An example is a wireless application protocol (WAP) gateway translating HTML web pages to WML for wireless devices [35]. WML is a lightweight version of HTML designed to run on wireless devices with small screens and limited capabilities. In this case, the server can forward the web page to a third-party server ✳ that implements the HTML-WML transcoding, which in turn processes the data and sends it to the destination via WAP. In general, data might need to be transformed by a series of third-party servers before it reaches the destination. In today’s In￾ternet, the application needs to know the set of servers that per￾form transcoding and then explicitly forward data packets via these servers. With ☎✝✆, this functionality can be easily implemented by using a stack of identifiers. Figure 4(a) shows how data packets containing HTML information can be redirected to the transcoder, and thus arrive at the receiver containing WML information. The sender associates with each data packet the stack ✷ ☎❅✸✑✴✶✵✥✷✹✸✄✺✼✻✽✷✾✸ ✹ ☎❅✸✘✻ , where ☎❅✸ represents the flow identifier. As a result, the data packet is routed first to the server which performs the transcoding. Next, the server inserts packet ✷ ☎❅✸✠✹✺✸✾✽✾✿✕✽❂✻ into ☎✝✆, which delivers it to the receiver