The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


"Overlay Topology Inference and Tree Construction"

By

Mr. Xing Jin


Abstract

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 two problems: (1) How to efficiently infer the underlay topology
among hosts by means of end-to-end measurement tools such as traceroute?
We propose a Max-Delta heuristic to infer a highly accurate topology among
hosts with a few traceroutes. As it is centralized, we further develop a
distributed inference scheme based on it, and study how to reduce
measurement cost. Furthermore, we investigate how to deal with the noise
of anonymous routers in measurements. (2) Given an underlay topology, 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+e), for any e>0, unless P=NP. We then
present approximation algorithms to address them, 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.


Date:			Tuesday, 28 August 2007

Time:			10:00a.m.-12:00noon

Venue:			Room 3416
			Lifts 17-18

Chairman:		Prof. Kuo-Chiang Wei (FINA)

Committee Members:	Prof. Gary Chan (Supervisor)
			Prof. Jogesh Muppala
			Prof. Lionel Ni
			Prof. Chin-Tau Lea (ECE)
			Prof. Jack Lee (Inf. Engg., CUHK)


**** ALL are Welcome ****