PhD Thesis Proposal 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 proposal, 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. We further study 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 or a Minimum Stress
Multicast Tree, depending on whether the link bandwidth is available or
not. We prove that both of them are NP-hard and not approximable within a
factor of 2/3+e, for any e>0, unless P=NP. We then present and analyze
approximation algorithms to address them.

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 if a little accuracy, say 5%, can be
compromised. And 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 and Overcast, our approximation algorithms achieve high tree
bandwidth and low link stress with low penalty in end-to-end delay. Our
study show that indeed the knowledge of the underlay is important for
constructing efficient overlay trees.

A limitation of above approaches is that the schemes rely on a central
server to collect traceroute results and to construct the overlay tree. In
the future, we will study distributed topology inference and distributed
tree construction techniques.


Date:     		Tuesday, 6 February 2007

Time:                   10:30a.m.-12:30p.m.

Venue:                  Room 3501
			lifts 25-26

Committee Members:      Dr. Gary Chan (Supervisor)
                        Dr. Jogesh Muppala (Chairperson)
			Dr. Brahim Bensaou
			Prof. Lionel Ni


**** ALL are Welcome ****