Fast overlay tree based on efficient end-to-end measurements

Most of the application-layer multicast protocols use end-to-end delay as their primary metric. However, for applications such as stored video delivery, meeting a certain target bandwidth requirement is of primary importance. In this paper, we present a centralized approach on how to build a fast overlay tree based on efficient end-to-end measurements. We first investigate how to infer underlay topology (in terms of connectivity) with low measurement cost. Given N end-hosts, traditionally full N(N-1)/2 traceroutes are needed to accurately determine the underlay topology. We propose a much faster heuristic (Max-Delta) where a server selects appropriate hostpairs to probe in parallel so as to reveal the most information on the underlay in each round. Given an inferred network topology, we then present the algorithm of Fast Application-layer Tree (FAT), which builds an overlay tree of a certain target bandwidth by estimating possible load on each underlay link. Simulation results show that almost full measurements are needed to discover completely underlay topology. However, substantial reduction in measurements (by almost an order of magnitude) can be achieved if some accuracy, say 5%, can be sacrificed. As compared to traditional ALM protocols such as Narada and Overcast, FAT achieves high bandwidth, low link stress, and low RDP.