Computer Science Department

Computer Science Colloquium

Internet Infrastructure for Efficient Overlays

John Jannotti

Monday, February 24, 2003
11:00 a.m.
Room 1302 WWH
251 Mercer Street
New York, NY 10012-1185

Host: Richard Cole,, 212-998-3119
Colloquium Information:


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.