AS-friendly peer selection algorithms without AS topology information in P2P live streaming
Yukinobu Fukushima, Tao Yin, Kazuya Inada, Tokumi Yokohira · Asia-Pacific Symposium on Information and Telecommunication Technologies · 2010
In recent years, peer-to-peer (P2P) live streaming systems are emerging because of their high scalability and robustness. In the systems, peer selection algorithms that determine logical topologies of P2P overlay networks have a great influence on important performance metrics such as the maximum number of joining peers and inter-AS (autonomous systems) traffic volume. As conventional algorithms that take account of those metrics, MLH (Minimum Logical Hop) and MPH (Minimum Physical Hop) have been proposed. In MLH, a newly joining peer (say P new ) selects peers whose logical hop counts are as small as possible, where the logical hop count of a peer is defined as the number of hops from an origin streaming server (OSS) to itself. When there are too many such peers, P new selects peers whose physical hop counts are as small as possible, where the physical hop count between two peers is defined as the number of ASs between them. In MPH, P new selects peers in the reverse order of MLH. These conventional peer selection algorithms use physical hop count under the assumption that complete AS topology information is available. However, it is hard to obtain the complete information. In this paper, we modify the conventional algorithms so that they use each peer's belonging AS information only instead of AS topology information in order to make them practical. In the modified version of MLH and MPH (MLH' and MPH'), P new selects the peers within the same AS as P new instead of peers whose physical hop counts are as small as possible. In addition, in order to distribute top level peers (i.e., peers that directly retrieve video from an OSS) to many ASs, MPH' gives higher priority to selecting peers except OSSs in ASs with OSSs. We evaluate the performance of the modified algorithms by simulation. Simulation results show that 1) MLH' and MPH' achieve almost the same maximum number of joining peers as MLH and MPH, respectively, 2) MLH' shows a maximum of 37% larger inter-AS traffic volume than MLH, 3) MPH' shows larger traffic volume than MPH when the number of joining peers is small, while MPH' shows a maximum of 38% smaller traffic volume than MPH when the number of joining peers is large thanks to the distribution of top level peers to many ASs.