Internet Indirection Infrastructure

I. Stoica, D. Adkins, S. Zhuang, S. Shenker, S. Surana, “Internet Indirection Infrastructure,” ACM SIGCOMM Conference, (August 2002). [PDF]

Summary

Internet Indirection Infrastructure (i3) is an overlay network that offers a rendezvous-based communication abstraction to decouple the act of sending from the act of receiving in order to support diverse communication services (e.g., multicast, anycast, mobility etc.). Instead of directly sending packets to their destinations using the IP network, senders in i3 send packets to intermediate i3 nodes (using logical identifiers); receivers interested in receiving packets from particular identifiers must explicitly express their interests by inserting triggers. In their simplest forms, packets are pairs (id, data) where id is an m-bit identifier and data consists of a payload, and triggers are pairs (id, addr), where id is the trigger identifier and addr is the receiver’s address.

Extensions to the Basic Model

1. Inexact identifier matching: Instead of exact-matching all m-bits to find appropriate triggers for a packet, an exact-match threshold k (k < m) is defined; a match is considered to exist when a trigger identifier matches a packet identifier in at least k-bits and that is the also the longest prefix match. By changing/exploiting k, i3 provides increased flexibility to support anycast, locality- and capacity-aware i3 server selection, and hot-spot avoidance. To facilitate inexact matching, all id‘s agreeing in their first k bits must reside on the same server.
2. Stack of identifiers: Instead of using scalar identifiers, the authors propose using identifier stacks, which are vectors of identifiers or addresses. In this case, packets carry (id_stack, data) and triggers are represented by (id, id_stack). This generalized form allows a source to send a packet to a series of identifiers (similar to source routing). Similarly, a trigger can send a packet to another intermediate identifier instead of directly sending it to the receiver. A packet is forwarded over the i3 overlay until one of its identifiers in the id_stack matches a trigger id; in that case that matching identifier is replaced by the trigger’s id_stack and the process goes on. Unmatched identifiers are popped off without any change to the packet’s id_stack, and if no trigger can be found for a packet, it is eventually dropped.
3. Private triggers: i3 makes distinction between public triggers, which are known to everyone for end-to-end communication and private triggers, which are temporary triggers between two end points to carry on secure communication. Private triggers are established using public triggers.
4. Potpourri: In addition to aforementioned extensions/generalizations, the authors also propose hierarchy of triggers to support large scale multicast, backup triggers for robustness, caching and randomization of trigger identifiers for routing efficiency.

Implementation Issues

The performance of i3 depends on the underlying overlay network. The authors implemented i3 on top of Chord for its robustness, scalability, efficiency of lookup, stability, and self-organization capability. Each i3 node/server is assigned a unique identifier in the Chord ring, and Chord lookups are used to find identifiers on a packet’s identifier stack while forwarding it. How to efficiently exact- or inexact- match triggers is not very well-defined.

The authors have spent some time in discussing the security concerns (e.g., eavesdropping, trigger hijacking, DoS attacks etc.) in using i3. Solutions are mostly simple in theory, but expected to lower performance.

Evaluation

Latency stretch (the ratio of the inter-node latency using i3 to the inter-node latency using IP) is used as the main performance metric in evaluating i3. Simulations show i3 not to perform as good as the IP network due to random placement of servers. Caching and heuristics for proximity placement significantly improve that performance. Overheads of trigger insertion and packet forwarding are found to be manageable, albeit not too impressive.

Critique

The simple abstraction mechanism presented in this paper manages to generalize multiple communication patterns that plague the current Internet. In addition, i3 is a great hash of many existing ideas, which IMO is a good thing for any systems or networking paper. However, i3′s performance and security aspects are not so simple, and even with the proposed increasingly complex tricks they still might fall short in real-life scenarios.

The evaluation section is probably the weakest part of the paper. Comparison against basic multicast seems to be a big missing thing. In addition, many of the clever stuff was not or could not be implemented/simulated, which fails to remove doubts about their applicability.