Speaker: Dr. Xing Jin (Hong Kong University of Science and Technology)
Title: Overlay Network Topology Inference and Its Application in Streaming

Abstract:

Overlay networks have been increasingly used to deploy network
services. In order to build an efficient overlay network, the
knowledge of underlay is important. We have investigated two
fundamental issues on this topic, i.e., how to infer the underlay
topology, and how to make use of the inferred topology to build an
efficient overlay.

In this talk, we first propose the Max-Delta heuristic to infer a
highly accurate topology among hosts with a low cost. We also
investigate how to deal with the noise of anonymous routers in
measurements. We then study the tree construction problem on a given
underlay topology. We formulate the problem as building a Maximum
Bandwidth Multicast Tree (MBMT) or a Minimum Stress Multicast Tree
(MSMT), depending on whether link bandwidth is available or not. We
prove that both of them are NP-hard and are not approximable within a
certain factor, unless P=NP. We then present an approximation
algorithm to address it, and analyze the algorithm performance.

We have evaluated the proposed schemes on Internet-like and real
Internet topologies. Our results show that almost full measurement is
needed to fully discover the underlay topology. However, substantial
reduction in measurements can be achieved by Max-Delta if a little
accuracy, say 5%, can be compromised. Furthermore, our tree
construction algorithm achieves high tree bandwidth and low link
stress with low penalty in end-to-end delay. Our study shows that
indeed the knowledge of the underlay is important for constructing
efficient overlays.