Outline of the Talk
Osaka University
Osaka, Japan• Introduction and motivation• P2P file sharing networks

UniversitéUniversité Libre de Bruxelles
Bruxelles, Belgium– The role of bandwidth sharing– File segmentation

Modeling of P2P File Sharing witha LevelLevel-Dependent QBD Process• Analysis with level-dependent QBD– Scenario 1: all segments are lost– Scenario 2: any segment is lost (catastrophe)

Sophie Hautphenne1, Kenji Leibnitz2, Marie-Ange Remiche3
1 Université Libre de Bruxelles

2 Osaka University, Graduate School of

Département d’Informatique
Bruxelles, Belgium
shautphe@ulb.ac.be

Information Science and Technology
Osaka, Japanleibnitz@ist.osaka-u.ac.jp

3 Université Libre de Bruxelles
Faculté des Sciences Appliquées
Bruxelles, Belgium
mremiche@ulb.ac.be

The Second Asia-Pacific Symposium on Queueing Theory and Network
Applications (QTNA2007), Kobe, Japan, August 1-4, 2007

1Introduction

Kenji Leibnitz
Osaka University

3

P2P System Model
1...

i...

1...

kj...

• Advantages:o Ease of connection setup
o Load is distributed among
all sharing peers
Î better scalabilityo Flash crowds are easily
compensated• Drawbacks:x Data may be lost due to churnx Content may be manipulated by peers(pollution/poisoning)
Kenji Leibnitz
Osaka University• File size is F split inNs = 2 segments12Î 3 phase system• Asymmetrical bandwidths (ADSL)

num_chunks

num_segments
num_blocks

size depends
onsize
ICH180kB
implementation
block

4

12

phase 1phase 31122

phase 2– Upload bandwidth ru = 128 kbps
– Download bandwidth rd = 768 kbps

• Model is similar to eDonkey file sharing network• File structure consists of chunks and blocks• Peers share blocks, corrupt chunks are discarded• Improvement by Intelligent Corruption Handling(segments)
Kenji Leibnitz
Osaka University2Download Bandwidth Sharing

chunk size 9.5MB
segments
blocksKenji Leibnitz
Osaka University

PeerPeer-toto-Peer FileFile-Sharing Networks• Internet traffic volume has rapidly
increased due to peer-to-peer (P2P)• Common applications used for file sharing:eDonkey, BitTorrent, Kazaa, Winny• Each peer acts simultaneously as clientand server• P2P networks form logical overlay
topology on application layerchunks• Numerical evaluation• Conclusion and Outlook5• Fair share mechanism for upload rates lead toDownload bandwidth oftransition rates μ1 and μ2:
peer limits transmission

S: all peers sharing segment 1
D: all peers downloading segment 1Kenji Leibnitz
Osaka University

Upload bandwidth ofpeer limits transmission
61

Analytical P2P Model

Markovian Process Description• We evaluate the extinction probability, when
diffusion ends due to unavailability of segments• Main contribution:
Proposal of algorithmically tractable analysis oflevel-dependent QBD process with application toP2P file sharing• In the paper we consider two scenarios:

The system is completely described by thefollowing Markovian process:Number of peers having
both segments at time t

Number of peers in thesystem at time t

where– File diffusion stops when all segments are lost– File diffusion stops when any segment is lost

Number of peers having
segment 1 at time t

Number of peers having
segment 2 at time t

withKenji Leibnitz
Osaka University

Kenji Leibnitz
Osaka University

7

Level Transitions

LevelLevel-Dependent QBD with Catastrophes• Extinction occurs when any segment is lostÎ File cannot be entirely retrieved anymore• Two views of the transition graph:

The system may move from level L(k) to• Level L(k+1) with rates A0(k)peer enters system after infinitesimal time period• Level L(k) with rates A1(k)peer changes status and gets missing segment• Level L(k-1) with rates A2(k)peer leaves system after infinitesimal time period• Level L(0) with rates A3(k)essential peer leaves system Î extinction
e.g. (k-1, 1, 0), (1, k-1, 0), (0, k-1, 1), or (k-1, 0, 1)– Level detailed view– State detailed view

• Level k ≥ 1 corresponds to set of states

and level 0 is

Kenji Leibnitz
Osaka University

Kenji Leibnitz
Osaka University

9Generator Matrix

10State Transitions

This yields the following generator matrix Q
for the Markovian process

MatrixTransitions

Rates

A0(k)

(S1, S2, S3) Æ (S1+1, S2, S3)

S1 μ1(1, S2+1) + S3 μ2(1, S1+S2+1)(S1, S2, S3) Æ (S1, S2+1, S3)

S2 μ2(1, S1+1) + S3 μ2(1, S1+S2+1)

A1(k)(S1, S2, S3) Æ (S1-1, S2, S3+1)

μ2(S2+S3, S1)(S1, S2, S3) Æ (S1, S2-1, S3+1)

μ1(S1+S3, S2)

S1 > 1 ∨ S3 > 0: (S1, S2, S3) Æ (S1-1, S2, S3)

S1 d

A2(k)

S2 > 1 ∨ S3 > 0: (S1, S2, S3) Æ (S1, S2-1, S3)

S2 d(S1 > 1 ∧ S2 > 1) ∨ S3 > 0: (S1, S2, S3) Æ (S1, S2, S3-1)

S2 d

S2 > 0: (0, S2, 1) Æ (0, k, 0)

dS2 > 0: (1, S2, 0) Æ (0, k, 0)

dA3(k)

Kenji Leibnitz
Osaka University

811

Kenji Leibnitz
Osaka University

S1 > 0: (S1, 0, 1) Æ (k, 0, 0)d

S1 > 0: (S1, 1, 0) Æ (k, 0, 0)d(0, 0, 1) Æ (0, 0, 0)d122

Extinction Probability

Extinction Probability (2)We define the following notations:• The extinction probability is computed startingfrom state (0, 0, 1), i.e., a single sharing peer
• We define two types of matrices:

for the probability that starting fromL(k), the next level-transition
observed is to level L(k+1)

probability to reach level L(0) in phase j, giventhat the process starts at L(k) in phase i andavoids L(1), L(2), …, L(k-1)
probability to reach level L(k-1) in phase j giventhat the process starts from level L(k) in phase I

for the probability that starting fromL(k), the next level-transition
observed is to level L(k-1)• The quantity of interest is thus
for the probability that starting fromL(k), the next level-transition
observed is to level L(0)Kenji Leibnitz
Osaka University

13

Extinction Probability (3)14Extinction Probability (4)• We now study matrices Gk for k ≥ 2 satisfying:

one level transition

Kenji Leibnitz
Osaka University

More generally, to know
we first need to know
via the general recursion

one or more level transitions• This may be rewritten as

which may be rewritten as• The Logarithmic Reduction algorithm allows computationof any Gk, k ≥ 2, but it is sufficient to compute GM (M ≥ 2)
• Different for k = 1:

Kenji Leibnitz
Osaka University

L(0) is reached without returning to L(1)15

Accuracy of Truncation LevelÎ Truncation of the QBD after level L(M), so that

Kenji Leibnitz
Osaka University16Extinction Probability (5)We finally obtain the following system which
provides us the absorption probability

M = 5 is sufficient• File size F = 9.28 MB, constant death rate d = 10-2
• Whole file extinction (0, 0, 0) unaffected by M
• Truncation at M = 5 provides sufficient accuracy
Kenji Leibnitz
Osaka University

17

Kenji Leibnitz
Osaka University

183

Numerical Evaluation

Conclusion• We proposed algorithmically tractable analysisof level-dependent QBD process• Application to P2P file sharing network withsegmentation

Deaths occur
faster thandownloadingRequire at least
one birth frominitial state

Both segments
have equal size

• Smaller size of second segment leads to lower extinction
probability• Extinction probability decreases when d » μ1(1,1)+μ2(1,1)
Kenji Leibnitz
Osaka University

19– Peers should have long sojourn time to maintain low
extinction probability– Content provider should offer incentives• Future work includes derivation of further(transient) performance measures and moredetailed user behavior (impatience, pollution, …)
Kenji Leibnitz
Osaka University

204