Rakesh Kumar

Result

  • performance is largely determined by a critical value.
  • a certain ratio of traffic loads exceeds the critical value
  • buffering can bring more improvement than can additional infrastructure bandwidth.

Basic

  • In P2P streaming systems, participating nodes are very heterogeneous, particularly in terms of the amount of upload bandwidth they contribute [9].
  • Broadly speaking, a P2P streaming system performs well if all participating peers can continuously playback the video (without freezing or skipping) with a small playback delay.

Model

  • Server upload rate: Us bps
  • Video rate: r bps
  • two-class model
    • Super peer upload rate: U1
    • Ordinary peer upload rate: U2. (500kbps or less)
    • Assumption: U2 < r < U1
  • Peers join and leave the P2P streaming system at random times..
    • Join: Poison processes. Join rate:λi
    • 1/μi for the average amount of view time
  • Pi(t): peer number, M/G/∞ processes [10].
    • Poisson distribution with mean E[Pi] = ρi =λi /μi

Streaming: focus on the instantaneous rate

bufferless model:

  • when all participating peers receive the video at rate r, we say that the system provides universal streaming.
  • maximal average rate is a function of P1(t) and P2(t), denote it as φ(P1(t), P2(t)) ≥ r. decided by streaming protocol.

Without churn

  • ui denote of the upload capacity of peer i
  • bits arrive to the server at rate r – video rate
  • maximum achievable rate rmax: the maximum value of r for universal streaming
    • rmax = min{us, (us + Sum(ui))/n }.
    • denote u(P) = Sum(ui)

Case 1. if us ≤ (us + u(P))/n

  • Split us into n substream. si = ui u(P)/us
  • because (n - 1)si ≤ ui :
  • so can reach r = us

Case 2. if > ,

  • Divide this video stream into n+1 substreams,
  • si = ui/(n -1), sn+1 = (us - u(P)/(n –1))/n
  • server copy two substreams to each peer i: the ith substream and the (n + 1)st substream.
  • r = (us + u(P))/n can be supported.

Corollary 1: For any rate r such that u2 < r < u1, universal streaming is achievable by some fluid distribution scheme if and only if r ≤ φ(n1, n2), where φ(n1, n2) = min{us, (us + n1u1 + n2u2 )/(n1 + n2 )}.

With Churn:

universal streaming probability. Let Pi be the random variable denoting the number of active type-i peers in steady state. It is well-known that Pi has a Poisson distribution with mean E[Pi] = ρi.

P(universal streaming) = P(P1 ≥ cP2 - u′s), Where c = (r - u2)/(u1 – r), and u′s = us/(u1 – r)

Since P1 and P2 are independent Poison random variables, we can explicitly calculate the universal streaming probability as follows.

xxxx

Large System Analysis

Scaling, i.e. ρ1 → ∞ and ρ2 → ∞,

Using scaling regimes ρ1 = Kρ2 + β* sqrt(ρ2)

P(universal streaming) =

  • 1 if K > c
  • F( -β/ sqrt(c+c*c) ) if K = c, where 1 - F(·) is the distribution function of the standard normal random variable.
  • 0 if K < c

Proof:

  • Define the normalized random variables X1 = (P1 - ρ1)/sqrt(ρ1)
  • c is the threshold for K ~ρ1/ρ2
  • P(universal streaming) ≈ F((ρ1 - cρ2)/√ρ2 )/√(c + c*c)).

Result evaluation:

  • r = 3, u1 = 1, u2 = 7, so c = 0.5,
  • 1/μ1 = 1/μ2 = 0.5 hr
  • ordinary peers λ2, super peers in vicinity of λ2/2
  • small sys λ2 = 100/hr
  • big sys:λ2 = 10,000/hr, ρ2 = λ2/μ2 = 5,000
  • so ρ1/ρ2 =λ1/λ2

Usage:

  • trend evaluation when ρ1/ρ2 increase, the degraded service probability decrease.
  • The effect of increase Us.
  • The critical ρ1/ρ2 area.
  • Difference between big sys and small sys.

Buffering:

  • make average uploading rate in the system exceeds r.
  • to set the server buffer size to d, and to have the server drop at rate r - φ(t) from the head of the buffer when the server buffer is full.
  • built a simple simulation tool to analyze the affects of buffering as well as the distribution of degraded-service durations.
  • different buffer capacities of 0, 30, 60 and 120 seconds of video.
  • when operating at ρ1/ρ2 = c = 0.5, With buffering, degraded service probability drops from 50% to approximately 5%.
  • 30-second lag is sufficient to obtain almost all the potential buffering gains from buffering.
  • 30 seconds lag is more effective than deploying 10 times the server capacity for this large system.
  • degraded-service durations: decreases by a factor of 10 by increasing the buffer sizes.
  • For under-capacity region for which ρ1/ρ2 < c + e. need special processing.

Refer

BT fluid model

  • [15] D. Qiu and S. Srikant, “Modeling and Performance Analysis of BitTorrent-Like Perr-to-Peer networks,” ACM SIGCOMM 2004, August 2004, Portland, Oregon.
    • The model accounts for churn, and views the number of seeds and leechers as fluid quantities. They develop simple differential equations for the fluids and solve the equations in steady state.
  • [4] F. Clevenot, P. Nain and K.W. Ross, “Multiclass P2P Networks: Static Resource Allocation for Bandwidth for Service Differentiation and Bandwidth
    • The multiclass fluid model leads to a non-linear system of differential equations with special structure.
    • They prove the system of differential equations admits a unique stable equilibrium, which is computed in closed-form.
  • The fluid models in [15] and [4] are not applicable to streaming systems with heterogeneous upload rates, since there is no notion of leechers(水蛭) transitioning to seeds.

Modeling the time it takes to distribute a file from seeds to leechers in churnless download systems.

  • [12] J. Mundinger, R. R. Weber and G. Weiss, “Analysis of Peer-to-Peer File Dissemination amongst Users of Different Upload Capacities,”Performance Evaluation Review, Performance 2005 Issue.
    • studied the problem for heterogeneous peers with infinite download capacity, both for chunkbased and fluid-based systems [12].
  • Kumar and Ross derived an explicit expression for the minimum download time in a general heterogenous fluid system with finite download rates. They also extended this result to multi-class systems with first and second-class leechers.
  • [2] E.W. Biersack, P. Rodriguez and P. Felber, “Performance Analysis of Peer-to-Peer Networks for File Distribution,” In proceedings of Quality of Future Internet Services (QOFIS04), September 2004, Barcelona, Spain.
    • used a chunk-based model to derive expressions for the distribution time for a several practical overlay topologies.

M/G/∞ processes [10].

  • [10] L. Kleinrock, “Queueing Systems, vol. I: Theory,” John Wiley and Sons, 1975.