Files in this item



application/pdfJi_Zhu.pdf (2MB)
(no description provided)PDF


Title:Stability and performance in peer to peer networks
Author(s):Zhu, Ji
Director of Research:Hajek, Bruce
Doctoral Committee Chair(s):Hajek, Bruce
Doctoral Committee Member(s):Srikant, Rayadurgam; Viswanath, Pramod; Godfrey, Philip B.; Nedich, Angelia
Department / Program:Electrical & Computer Eng
Discipline:Electrical & Computer Engr
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Peer to peer (P2P)
Stability Region
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
Abstract: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 can be 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 is commonly 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.
Issue Date:2014-01-16
Rights Information:Copyright 2013 Ji Zhu
Date Available in IDEALS:2014-01-16
Date Deposited:2013-12

This item appears in the following Collection(s)

Item Statistics