Min Sik Kim

The University of Texas at Austin
Department of Computer Sciences

Buildling and Maintaining Overlay Networks for Bandwidth-Demanding Applications

Min Sik Kim and Simon S. Lam
In Proceedings of IEEE INFOCOM 2005 Student Workshop, March 2005.


The demands of Internet applications have grown significantly in terms of required resources and types of services. Overlay networks have emerged to accommodate such applications. The performance of an overlay network is, however, highly dependent on its topology; keeping logical links in an overlay network from interfering with each other is crucial in achieving high throughput. In this thesis, I propose a novel technique that uses wavelet analysis to find bottlenecks caused by the interference between logical links. Based on this technique, I design an algorithm that eliminates all such bottlenecks from a multicast tree, and prove that there remains no such bottleneck in the tree upon termination of the algorithm. The scalability of the shared congestion detection technique is improved using an indexed multidimensional space, which reduces its computational complexity from O(N2) to O(N log N). This research will let bandwidth-demanding applications build more efficient overlay networks to achieve higher throughput.