Stability and performance in peer to peer networks

Peer to peer (P2P);Stability Region;Scalability;Robustness;BitTorrent;file sharing;video on demand;live streaming;Foster Lyapunov stability criterion;network coding;seed dwelling;missing piece syndrome;one club;bundling swarms;multi swarm;stochastic model;queuing network;Markov chain;sojourn time;video broadcast;broadcast tree;tree management;distributed streaming algorithm;sub stream;multicast trees;butt servers

Zhu, Ji

关键词: Peer to peer (P2P);    Stability Region;    Scalability;    Robustness;    BitTorrent;    file sharing;    video on demand;    live streaming;    Foster Lyapunov stability criterion;    network coding;    seed dwelling;    missing piece syndrome;    one club;    bundling swarms;    multi swarm;    stochastic model;    queuing network;    Markov chain;    sojourn time;    video broadcast;    broadcast tree;    tree management;    distributed streaming algorithm;    sub stream;    multicast trees;    butt servers;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/46753/Ji_Zhu.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

Stability regions of P2P systems describe analytically the scalability and robustness of the systems; they reveal intrinsic properties of P2P systems and provide intuition and guidance for system design.One contribution of the thesis is to characterize stability regions of BitTorrent-like P2P networks and analyze methods to enlarge the regions. Stability regions are characterized by stochastic models for a variety of popular methods, namely, those providing pieces to peers upon arrival and requiring seeds to dwell. Necessary and sufficient conditions for stabilizing the system are provided and proved. The thesis identifies the least amount of assistance needed from the seeds to stabilize the system. Take the method related to dwelling, for example; the stability canbe achieved if every peer dwells on average only long enough to upload one additional piece. Another practical method considered is network coding. It is shown that network coding substantially increases the stability region if a portion of peers arrive with randomly coded pieces; nevertheless, such region remains unchanged if peers arrive without pieces. Lastly, the method of bundling files together, termed as multiswarm networks, is considered, along with the stability region provided. Stability region is shown to be determined by the largest arrival rate of all swarms and insensitive to the number of swarms. For all methods considered here, stability regions are shown to be identical for various work-conserving piece selection policies. However, these piece selection policies differ significantly in their abilities to prolong the time for an unstable system to stay under normal states. This prompts one to introduce the notion of metastability. In this sense, a piece selection policy prioritizing rarer pieces is advantageous in that it keeps the system metastable far longer.Another contribution of the thesis is to present an asynchronous distributed algorithm for P2P streaming. The proposed algorithm organizes the streaming topology as multicast trees, one for each substream. The topology of trees, which iscommonly used for streaming, has advantages in low disruption rate, small delay, low interference, good fluency and high efficiency; but it is difficult to build and maintain in a distributed way. The difficulty is tackled by the algorithm, through which cycles are efficiently eliminated and the topology is constantly adjusted towards balanced trees. Compared to existing methods, the algorithm is more robust, converges faster, and scales to as many peers as possible; it does not require any centralized routing servers. Under the algorithm, each peer is guaranteed to be covered by sufficiently many trees with the delay time scaling only logarithmically in the number of peers. The algorithm works under heterogeneous constraints on peer upload capacity, where peers with higher degrees can enjoy lower delay. Thus it fits not only the case of P2P, but also the case of butt servers.