Topology inference and tree construction for topology-aware overlay streaming

In the recent years, overlay networks have been increasingly used to deploy network services. In order to build an efficient overlay network, the knowledge of underlay is important. In this thesis, we study the following issues: (1) How to efficiently infer the underlay topology among hosts by means of end-to-end measurement tools such as traceroute? We propose a centralized Max-Delta heuristic to infer a highly accurate topology among hosts with a few traceroutes. We investigate how to deal with the noise of anonymous routers in measurements. (2) As the above inference schemes are centralized, we further develop a distributed inference scheme based on them, and study how to reduce measurement cost. (3) Given an underlay topology, we theoretically study how to build a high-bandwidth overlay tree among hosts. 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 factor of (2/3 + ∈), for any ∈ > 0, unless P = NP. We then present centralized approximation algorithms as benchmark schemes, 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. The results also show that the distributed scheme can build a low-diameter tree to facilitate quick data exchange between hosts, and that our merging algorithms in the presence of anonymous routers can efficiently infer an underlay topology with good accuracy. Furthermore, as compared to traditional tree-based protocols such as Narada, Overcast and TAG, our approximation algorithms achieve 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 overlay trees