Check out the new USENIX Web site. next up previous
Next: ROAM Design Up: Background Previous: Rendezvous-based Communication


Figure: (a) A Chord identifier circle for $m = 6$, with 5 servers identified by 5, 16, 24, 36, and 50, respectively. (b) Receiver R inserting trigger $(30, R)$, and sender S sending packet $(30, data)$.

$i3$is implemented as an overlay network composed of servers that store triggers and forward packets.

To maintain this overlay network and to route packets in $i3$, we use the Chord lookup protocol [25]. Chord assumes a circular identifier space of integers $[0, 2^{m})$, where $0$ follows $2^{m} -
1$. Every $i3$server has an identifier in this space, and all trigger identifiers belong to the same identifier space. The $i3$server with identifier $n$ is responsible for all identifiers in the interval $(n_p, n]$, where $n_p$ is the identifier of the node preceding $n$ on the identifier circle. Figure 2(a) shows an identifier circle for $m = 6$. There are five $i3$servers in the system with identifiers 5, 16, 24, 36, and 50, respectively. All identifiers in the range (5, 16] are mapped on server 16, identifiers in (17, 24] are mapped on server 24, and so on.

When a trigger $(id, addr)$ is inserted, it is stored at the $i3$node responsible for $id$. When a packet is sent to $id$, it is routed by $i3$to the node responsible for its $id$; there it is matched against (any) triggers for that $id$ and forwarded (using IP) to all hosts interested in packets sent to that identifier. Chord ensures that the server responsible for an identifier is found after visiting at most $O(\log n)$ other $i3$servers irrespective of the starting server ($n$ represents the total number of servers in the system). To achieve this, Chord requires each node to maintain only $O(\log n)$ routing state. Chord allows servers to leave and join dynamically, and it is highly robust against failures. For more details refer to [25]. Figure 2(b) shows an example in which trigger $(30, R)$ is inserted at node 36 (i.e., the node that maps $(24,36]$, and thus is responsible for identifier 30). Packet $(30, data)$ is forwarded to server 30, matched against trigger $(30, R)$, and then forwarded via IP to $R$.

Note that packets are not stored in $i3$; they are only forwarded. End hosts must periodically refresh their triggers in $i3$. Hosts need only know one $i3$node to use the $i3$infrastructure. This can be done through a static configuration file, or by a DNS lookup assuming $i3$is associated with a DNS domain name. In Figure 2(b), the sender knows only server 16, and the receiver knows only server 5.

next up previous
Next: ROAM Design Up: Background Previous: Rendezvous-based Communication
Shelley Zhuang 2003-03-03