Nalanda

Citations:

Walfish, M., Stribling, J., Krohn, M., Balakrishnan, H., Morris, R., and Shenker, S. 2004. Middleboxes no longer considered harmful. In Proceedings of the 6th Conference on Symposium on Opearting Systems Design & Implementation - Volume 6 (San Francisco, CA, December 06 - 08, 2004). Operating Systems Design and Implementation. USENIX Association, Berkeley, CA, 15-15

Stoica, I., Adkins, D., Zhuang, S., Shenker, S., and Surana, S. 2002. Internet indirection infrastructure. SIGCOMM Comput. Commun. Rev. 32, 4 (Oct. 2002), 73-86. DOI=http://doi.acm.org/10.1145/964725.63303

Both these papers build on our recent readings to explore new addressing and routing mechanisms that would allow easier deployment of existing network elements (such as middleboxes), and enable a wide variety of modern network services. The approaches outlined in these papers - Delegation Oriented Architecture (DOA) and Internet Indirection Infrastructure (i3) - have some features in common: a reliance on a new kind of host identifier to be embedded in packets, the use of DHTs as address lookup services, and implementation as an overlay network to provide the necessary function and at the same time allow them to coexist with the current Internet architecture.The principal difference between these approaches is perhaps in their use of identifiers: where DOA maps identifiers to individual hosts, i3 uses identifiers to map to potentially multiple hosts.

The authors of DOA make the point that although reviled, middleboxes provide essential network services; we should therefore ask how they might be better integrated into the Internet architecture without violating the fundamental tenets that every Internet entity has a unique network identifier and that network elements should not not process packets that are not addressed to them. DOA packets may specify a sequence of hosts to which the packet must be routed, allowing middleboxes to exist at locations other than the topological “middle”. With this abstraction in place, packets are source routed across the specified sequence of hosts before reaching the receiver. Users may adaptively select new services that they wish to process their packets, and outsource them accordingly.

i3 requires receivers to register “triggers” against common identifiers, indicating that packets to an identifiers should be forwarded to them. A mobile host may update its triggers to reflect its new network location, with no need for senders to be aware of this change. Multicast groups may be formed by multiple hosts registering triggers for the same identifier. The most interesting application of i3, to me, was for anycast, where the hosts in the anycast group maintain triggers with identical prefixes; senders form identifiers with a matching prefix, and the request is routed to the trigger with the longest matching prefix. Such services may provide load balancing by having senders generate random identifier suffixes, or location awareness by having receivers and senders encode their location into the identifier suffix. As with DOA, i3 provides a means by which packets may be source routed - an “identifier stack” - to enable service composition.

Each of these proposals is put forward to address fundamental mismatches between current network architecture, and the uses to which this architecture is being put. DOA deals with the problem of middleboxes, and how these might be better integrated into the network architecture, while i3 deals with the problem of network services which do not follow the point-to-point abstraction of Internet routing (multicast, anycast and mobility).

Citation: Andersen, D., Balakrishnan, H., Kaashoek, F., and Morris, R. 2001. Resilient overlay networks. SIGOPS Oper. Syst. Rev. 35, 5 (Dec. 2001), 131-145. DOI=http://doi.acm.org/10.1145/502059.502048

In order to operate at the scale of the Internet, the Internet’s current interdomain routing protocol, BGP-4, aggregates routes, but at the same time hides details of topology and traffic conditions, which leads to time intervals of the order of tens of minutes (or even hours) for BGP’s recovery mechanisms to converge on a consistent routing table. This paper presents the Resilient Overlay Network (RON) as a remedy to BGP’s problems.

A RON consists of a set of nodes residing in a variety of routing domains, which maintain a full mesh of routes between themselves using a link state routing protocol. Link metrics are collected using a combination of active periodic probing, and passive listening. This allows RON to route around failures in the order of seconds, a significant improvement over BGP. For a RON of 50 nodes, an approximate overhead of 30 kbps will be required with the implementation described in the paper; this does not seem excessive considering the capacity of current Internet links.

An interesting feature of RON is an explicit interaction with applications for the purposes of deciding metrics for route selection. By default, RON offers latency, loss and throughput metrics, though this set may be extended to include application-specific metrics such as jitter. This allows applications to choose trade-offs between different metrics for route selection, and in effect enables application-specific routing. In this context, the paper introduces the useful notion of a performance failure, where a link does not provide adequate performance to the application using it.

RON also puts in place rich routing policies, which may restrict the flow of certain kinds of traffic over certain routes: for instance, in the tests the authors conducted, policies were put in place to prevent commercial traffic from flowing over the non-commercial Internet2 backbone.

Two sets of tests were run, one of 12 academic networks (several of which are on the Internet2 backbone), and another which added 4 commercial networks. In the former case, RON was able to overcome all observed outages, and in the latter, 60%, with an average of 18 seconds to recover from a fault. In addition, thanks to its explicit attention to application-dependent metrics, RON is able to improve loss rate, latency and TCP throughput.

As the authors themselves note, individual RONs will not scale to the level of the Internet: RONs operate best with relatively small numbers of nodes. This smaller scale is also important administratively, from the perspective of attempting to deal with malicious nodes, as such problems are obviously easier to deal with at an administrative, rather than a technical level. In my reading, RON is an important and useful adjunct to BGP routing, both for its rapid recovery from fault, but especially for its ability to route according to application-specified metrics.