Modeling and Performance Analysis of BitTorrent-Like Peer-to

Modelling and Performance Analysis
of BitTorrent-Like
Peer-to-Peer Networks
 Simple deterministic fluid model – to calculate average file
transfer delay in BitTorrent
 Stochstic fluid model – characterizes number of peers
around equilibrium
 Model to study efficiency of BitTorrent
 Incentive mechanism in BitTorrent and its effect on n/w
Brief Introduction to BitTorrent
 Single large file is divided into pieces of 256 KB each
 Peer downloads different pieces from different peers
 Each peer uploads to fixed number of users (Default 4)
 Uploads to peers having best downloading rates
 Optimistic unchoking
Deterministic fluid model
 x(t) number of downloaders (also known as leechers) in the system at
time t.
y(t) number of seeds in the system at time t.
λ the arrival rate of new requests( Poisson process)
μ the uploading bandwidth of a given peer.We assume that
all peers have the same uploading bandwidth.
c the downloading bandwidth of a given peer.We assume
that all peers have the same downloading bandwidth.
θ the rate at which downloaders abort the download.
γ the rate at which seeds leave the system.
η indicates the effectiveness of the file sharing
 dx/dt= λ − θx(t) − min{cx(t), μ(ηx(t) + y(t))},
 dy/dt= min{cx(t), μ(ηx(t) + y(t))} − γy(t),
To study steady state performance
dx(t)/dt=dy(t)/dt= 0 and obtain equilibrium values x and y
By using Little’s law
 ((λ − θx)/λ)x = (λ − θx)T,
T =1/(θ + β)
where 1/β = max{1/c , 1/η ( 1/μ− 1/γ )}.
 The average downloading time T is not related to λ, hence
p2p system scales very well
 When η increases, T decreases
 When γ increases, T increases because a larger γ means that
there are fewer seeds in the system
 Initially, when c increases, T decreases. However, once c is
large enough, increasing c further will not decrease T,
because the downloading bandwidth is no longer the
bottleneck. A similar observation can be made regarding the
uploading bandwidth μ.
Importance of η
 When η = 0 and γ > μ
dy(t)/dt ≤ (μ − γ)y(t)
number of seeds will
exponentially decrease to zero and the system dies
 When η > 0, the system reaches a steady state no matter what
γ is.
 η = 1− P{downloader j needs no piece from downloader i}^ k
η is close to 1 in BitTorrent
Stability around equilibrium
 Eigenvalues of matrix obtained from differential equations
have strict negative real parts in all cases hence system is
stable around equilibrium
 Stochastic fluid model :
From the solution of stochastic differential equation it can be
seen that in steady-state, the number of seeds and
downloaders is distributed as Gaussian random variables
 it involves showing that the original stochastic process
converges to the deterministic and stochastic differential
equation limits when the arrival rate goes to ∞
Incentive Mechanism in BitTorrent
 In BitTorrent a peer decides to upload to peers from which it can
get highest downloading rates
Here optimistic unchoking is ignored and assumed that each peer
has global information of uploading rates
Stepwise peer selection algorithm
Each peer tries to maximize downloading rate(gain) and minimize
uploading rate(cost),this can be seen as non-cooperative game
given game rules (peer selection algorithm)
In a general n/w setting, nash equilibrium point exists with
equilibrium uploading b/w = max physical uploading b/w of peer
Optimistic unchoking and free riding
 In Bittorrent n/w peer has the rate information about peers
from which it is downloading.
 Hence optimistic unchoking is used to explore the network
and obtain information about other peers and this gives
opportunity to free-ride.
 In a network with group of peers having same b/w μ,free
rider gets average downloading rate ≈ μ/(nu + 1)
 In Bittorrent , nu = 4 (default),hence free rider gets 20% of the
max downloading rate
Fairness, incentives and performance in
 To study sensitivity of service capacity of P2P networks,
following models are proposed
1.Branching process model in transient regime
2.Markov chain model in stationary regime
 Fairness and incentives in P2P system
Throughput in BitTorrent N/w
Transient regime
 Deterministic model to understand file sharing mechanism
 Assumptions : Initially only one copy of file available
n= 2^k demands,
limited upload capacity = b ,unlimited download
file size = s
 A peer can only serve a document once it has been fully
 Then average delay per peer = t log2 n where t= s/b
• Average delay seen by peers scales as log2 n which is favorable
relative to the linear scaling of n in case of fixed set of servers
• Delay is further reduced by a factor of 1/m in case of
multipart download
Branching process model
Following model takes care of randomness of service times and
abnormal departures of peers
Observations :
1. Variability in generation times improves the growth exponent
2. Increased parallelism typically may decrease the growth exponent
3. Uncooperative peers and parallel downloads : if seeds leave the
system with probability p , here vp>1 and to keep growth rates
higher keep higher v
Stationary regime : Markov chain
x- number of downloaders
y- number of seeds
(x,y) – two dimensional markov chain with following generator
Can find mean number of seeds,downloaders and
mean delay for this system

similar documents