CS Colloquium
Thursday, April 10, 2003
4:15 PM
B17 Upson Hall

John Jannotti
Massachusetts Institute of Technology
Laboratory for Computer Science

Internet Infrastructure for Efficient Overlays

Overlay networks are virtual networks formed by cooperating nodes that share an underlying physical network. Overlays are a flexible and deployable approach for obtaining new network semantics without modification of the underlying network, but they suffer from efficiency concerns. Two new router-based primitives can help end-hosts alleviate these inefficiencies. Packet Reflection allows end hosts to request that routers perform routing and duplication for certain packets. Path Painting allows end hosts to determine where their paths to a rendezvous point meet. This knowledge facilitates building overlay topologies that resemble the topology of the underlying network. Both primitives can be incrementally deployed for incremental benefit.

These primitives can be used to provide an efficient application-level multicast (ALM) system. Experimental results on simulated topologies show that when all routers support the proposed primitives, the ALM system incurs less than 5% overhead (in terms of link usage and latency) compared to IP Multicast. In addition, the benefits gained are significant even at low deployment levels. With intelligent deployment strategies, link usage overhead is less than 30% with less than 10% deployment. Finally, these benefits apply mostly to the area local to the deployed routers, providing a deployment incentive to independent networks.