□Node The main use of a public trigger is to allow an end-host to contact nother end-host. The identifier of a public trigger is known by all end-hosts in the system. An example is a web server that maintains a public trigger to allow any client to contact it. A public trigger can be defined as a the hash of the hosts dns name of a web address, or of the public key associated with a web server. Public triggers are long lived, typically days or months. In contrast, private triggers are chosen by a small number of end-hosts and they are short lived Typically, private triggers exist only during the duration of a flow To illustrate the difference between public and private triggers, consider a client A accessing a web server B that maintains a public trigger(idpub, B). First, client A chooses a private trigger iden- fier ida, inserts trigger (ida, A)into 23, and sends ida to the web server via the server's public trigger (idpub, B). Once con- Figure 6: Routing information(finger tables) maintained by tacted, server B selects a private identifier idb, inserts the associ- the chord nodes ated trigger(idb, B)into 23, and sends its private trigger identifier ids to client A via As private trigger(ida, A). The client and the server then use both the private triggers to communicate. Once the duration of a flow. This property allows end-hosts to op- the communication terminates, the private triggers are destroyed. their performance by choosing triggers that are stored Sections 4.5 and 4 10 discuss how private triggers can be used to on nearby servers increase the routing eficiency, and the communication security Next, we discuss i3s properties in more detail To implement 23 we have chosen the Chord lookup protocol [26], 4.3 Robustness which is known to satisfy the above properties. Chord uses an bit circular identifier space where 0 follows 2-1. Each server in that routing of packets within 3 is fairly robust against 23 node protocol, each identifier id is mapped on the server with the clos. failures. In addition, end-hosts use periodic refreshing to maintain est identifier that follows id on the identifier circle. This server is called successor of id and it is denoted by successor(id). Fig- and efficient implementation and frees the 23 infrastructure from ure 6 shows an example in which there are three nodes, and m=3 ai. If Server 2 is responsible for identifiers o, 1, and 2, server 5 is respon- for example, as a result of an i3 server failure-the will be ible for 3, 4 and 5, and server 7 is responsible for 6 and 7. reinserted, possibly at another server, the next time the end-host To implement the routing operation, each server maintains a rout- refreshes it ing table of size m. The i-th entry in the routing table of server One potential problem with this approach is that although the triggers are eventually reinserted, the time during which they are 2i-1). This server is called the i-th finger of n. Note that the first unavailable due to server failures may be too large for some appli- finger is the same as the successor serve ations. There are at least two solutions to address this problem. Upon receiving a packet with identifier id, server n checks whether The first solution does not require 13-level changes. The idea is to id lies between itself and its successor. If yes, the server forward have each receiver R maintain a backup trigger(idbackup, R) the packet to its successor, which should store the packets trigger. addition to the primary trigger(id, R), and have the sender send If not, n sends the packet to the closest server(finger) in its rout packets with the identifier stack(id, idbackup). If the server sto ing table that precedes id. In this way, we are guaranteed that the ing the primary trigger fails, the packet will be then forwarded via distance to id in the identifier space is halved at each step. As a re- the backup trigger to R. Note that to accommodate the case when the best matching trigger for the packet, irrespective of the start.(see Section 3. 2), we use a flag in the packet header, whcih i ack sult, it takes O(log N) hops to route a packet to the server storing the packet is required to match every trigger in its identifier st ing point of the packet, where N is the number of i3 servers in the causes the packet to be dropped if the identifier at the head of its stack doesnt find a match. The second solution is to have the over- In the current implementation, we assume that all identifiers that lay network itself replicate the triggers and manage the replicas share the same k-bit prefix are stored on the same way to achieve this is to set the last m-k bits of every node iden- trigger on the immediate successor of the server responsible for that tifier to zero. As a result, finding the best matching trigger reduces trigger [5].Finally, note that when an end-host fails, its triggers are to performing a longest prefix matching operation local automatically deleted from 3 after they time-out. While i3 is implemented on top of Chord, in principle 23 can use 4.4 Self-Organizing any of the recently proposed P2P lookup systems such as CAn[22) Pastry [23] and Tapestry [12] 3 is an overlay infrastructure that may grow to large sizes. Thus, it is important that it not require extensive manual configuration or 4.2 Public and Private triggers human intervention. The Chord overlay network is self-configuring, Before discussing 13s properties, we introduce an important tech in that nodes joining the 23 infrastructure use a simple bootstrap- ping mechanism(see [26]) to find out about at least one existing ciently. With this technique applications make a distinction be node, and then contacts that node to join the 23 infrastructure. Sim- tween two types of triggers: public and private. This distinction 4Here we implicitly ry and backt made only at the application level: 83 itself doesn't differentiate are stored on different servers. The receiver can ensure the between private and public triggers. the case with high probability by choosing idbackup=2i finger 1 5 2 5 3 7 1 2 7 1 4 5 3 6 2 Node i finger 1 7 2 7 3 2 i finger 2 2 3 5 0 Figure 6: Routing information (finger tables) maintained by the Chord nodes. the duration of a flow. This property allows end-hosts to op￾timize their performance by choosing triggers that are stored on nearby servers. To implement ☎ ✆ we have chosen the Chord lookup protocol [26], which is known to satisfy the above properties. Chord uses an ❇- bit circular identifier space where ￾ follows ▲✂✁ ✪▼◗ . Each server is associated a unique identifier in this space. In the original Chord protocol, each identifier ☎✦✸ is mapped on the server with the clos￾est identifier that follows ☎✦✸ on the identifier circle. This server is called successor of ☎✦✸ and it is denoted by ☎☎✄✑✆☛✆✖✂✠☎ ☎✖✌✬❈✘✷ ☎❅✸✘✻ . Fig￾ure 6 shows an example in which there are three nodes, and ❇❑❏ ✆. Server 2 is responsible for identifiers 0, 1, and 2, server 5 is respon￾sible for 3, 4 and 5, and server 7 is responsible for 6 and 7. To implement the routing operation, each server maintains a rout￾ing table of size ❇. The ☎-th entry in the routing table of server ✦ contains the first server that follows ✦✝✆ ▲ ✛★✺ ■ , i.e., ☎✞✄✄✆✆✖✂✠☎ ☎✒✌✎❈✘✷★✦✝✆ ▲ ✛✜✺ ■ ✻ . This server is called the ☎-th finger of ✦. Note that the first finger is the same as the successor server. Upon receiving a packet with identifier ☎❅✸,server ✦ checks whether ☎❅✸ lies between itself and its successor. If yes, the server forwards the packet to its successor, which should store the packet’s trigger. If not, ✦ sends the packet to the closest server (finger) in its rout￾ing table that precedes ☎✦✸. In this way, we are guaranteed that the distance to ☎❅✸ in the identifier space is halved at each step. As a re￾sult, it takes ✟P✷✡✠☞☛✂✌✎✍✮✻ hops to route a packet to the server storing the best matching trigger for the packet, irrespective of the start￾ing point of the packet, where ✍ is the number of ☎ ✆ servers in the system. In the current implementation, we assume that all identifiers that share the same ❉-bit prefix are stored on the same server. A simple way to achieve this is to set the last ❇ ✪ ❉ bits of every node iden￾tifier to zero. As a result, finding the best matching trigger reduces to performing a longest prefix matching operation locally. While ☎✝✆ is implemented on top of Chord, in principle ☎✝✆ can use any of the recently proposed P2P lookup systemssuch as CAN [22], Pastry [23] and Tapestry [12]. 4.2 Public and Private Triggers Before discussing ☎✝✆’s properties, we introduce an important tech￾nique that allows applications to use ☎✝✆ more securely and effi- ciently. With this technique applications make a distinction be￾tween two types of triggers: public and private. This distinction is made only at the application level: ☎✝✆ itself doesn’t differentiate between private and public triggers. The main use of a public trigger is to allow an end-host to contact another end-host. The identifier of a public trigger is known by all end-hosts in the system. An example is a web server that maintains a public trigger to allow any client to contact it. A public trigger can be defined as a the hash of the host’s DNS name, of a web address, or of the public key associated with a web server. Public triggers are long lived, typically days or months. In contrast, private triggers are chosen by a small number of end-hosts and they are short lived. Typically, private triggers exist only during the duration of a flow. To illustrate the difference between public and private triggers, consider a client ✏ accessing a web server ✑ that maintains a public trigger ✷ ☎❅✸✣☎✒✔✓ ✹✕✑✻ . First, client ✏ chooses a private trigger iden￾tifier ☎❅✸★✷ , inserts trigger ✷ ☎❅✸★✷✘✹✕✏✻ into ☎✝✆, and sends ☎❅✸✩✷ to the web server via the server’s public trigger ✷ ☎❅✸✣☎✒✔✓ ✹✕✑✻ . Once con￾tacted, server ✑ selects a private identifier ☎❅✸✓ , inserts the associ￾ated trigger ✷ ☎❅✸✓ ✹✕✑✻ into ☎ ✆, and sends its private trigger identifier ☎❅✸✓ to client ✏ via ✏’s private trigger ✷ ☎❅✸★✷❂✹✕✏✻ . The client and the server then use both the private triggers to communicate. Once the communication terminates, the private triggers are destroyed. Sections 4.5 and 4.10 discuss how private triggers can be used to increase the routing efficiency, and the communication security. Next, we discuss ☎✝✆’s properties in more detail. 4.3 Robustness ☎✝✆ inherits much of the robustness properties of the overlay itself in that routing of packets within ☎✝✆ is fairly robust against ☎✝✆ node failures. In addition, end-hosts use periodic refreshing to maintain their triggers into ☎✝✆. This soft-state approach allows for a simple and efficient implementation and frees the ☎✝✆ infrastructure from having to recover lost state when nodes fail. If a trigger is lost— for example, as a result of an ☎✝✆ server failure—the trigger will be reinserted, possibly at another server, the next time the end-host refreshes it. One potential problem with this approach is that although the triggers are eventually reinserted, the time during which they are unavailable due to server failures may be too large for some appli￾cations. There are at least two solutions to address this problem. The first solution does not require ☎✝✆-level changes. The idea is to have each receiver ✶ maintain a backup trigger ✷ ☎❅✸✓✷✲✹ ✴ ✒✲✣ ✹✑✶✼✻ in addition to the primary trigger ✷ ☎❅✸✠✹✑✶✼✻ , and have the sender send packets with the identifier stack ✷ ☎❅✸✠✹ ☎✦✸✓✷✲✹ ✴ ✒✳✣ ✻ . If the server stor￾ing the primary trigger fails, the packet will be then forwarded via the backup trigger to ✶. 4 Note that to accommodate the case when the packet is required to match every trigger in its identifier stack (see Section 3.2), we use a flag in the packet header, which, if set, causes the packet to be dropped if the identifier at the head of its stack doesn’t find a match. The second solution is to have the over￾lay network itself replicate the triggers and manage the replicas. In the case of Chord, the natural replication policy is to replicate a trigger on the immediate successor of the server responsible for that trigger [5]. Finally, note that when an end-host fails, its triggers are automatically deleted from ☎✝✆ after they time-out. 4.4 Self-Organizing ☎✝✆ is an overlay infrastructure that may grow to large sizes. Thus, it is important that it not require extensive manual configuration or human intervention. The Chord overlay network isself-configuring, in that nodes joining the ☎✝✆ infrastructure use a simple bootstrap￾ping mechanism (see [26]) to find out about at least one existing ☎ ✆ node, and then contacts that node to join the ☎✝✆ infrastructure. Sim- ✖ Here we implicitly assume that the primary and backup triggers are stored on different servers. The receiver can ensure that this is the case with high probability by choosing ☎❅✸✗✓✷✲✹ ✴ ✒✲✣✼❏ ▲✔✁ ✪ ☎❅✸