Number of DSL Subscribers
Institute of Computer Science
Department of Distributed Systems
Prof. Dr.-Ing. P. Tran-Gia

Millions of DSL subscribers

X Broadband access is stillincreasing
X Allows IPTV and highquality multimedia services

Modeling and Evaluation of an Online
TV Recording ServiceTobias Hoßfeld1, Kenji Leibnitz2

X 16 Mbps DSL user
downloads 700 MB in~6 min

1 University of Würzburg, Germany

hossfeld@informatik.uni-wuerzburg.de50
40302010

DSL subscribers per 100
inhabitants

X 1 Mbps DSL user
downloads 700 MB in~90 min

60

03025201510leibnitz@ist.osaka-u.ac.jp
Session 3
Wednesday, June 13
1:30 - 3:30

Osaka University
Information Science and Technology
Advanced Network Architecture Lab

502 Osaka University, Japan
source: OECD Broadband Statistics
December 2005
http://www.oecd.org

2Tobias Hoßfeld

Television in the Current Internet

Outline of the Talk

X Real-time streaming (broadcast, application layer multicast, …)
X Non-real-time streaming (video on demand, podcasts, …)
X Download platforms and video recorder platforms
Advantage: shows can be cut before viewing

X Online TV Recording Service
X Modeling the service and its users
X Markovian Model for Steady-State Analysis
X Time-Dynamic Evaluation with Fluid Model
X Numerical Results

X Technologies
centralized systems: client/server (farms)
distributed systems: peer-to-peer
Tobias Hoßfeld

X Conclusions

3Online TV Recording Service

4

Tobias Hoßfeld

Download of a TV Show

X Free web service for registered users
X Focus is on German TV channels

1. Choose file format
2. Choose way of download and download TV show

X User requests recording of TV show before broadcasting
X TV show recorded at server,
X converted to several video formats (mp4,wmv,divx,hq),
X and provided for download
X (Specialized) Mirror servers offer same content after some time
X Users support distribution via P2P (eDonkey or BitTorrent)

3. Download key of TV show to decode file (onlypossible if registered for this show at the server)
4. Decode file
5. Watch TV ☺
3Tobias Hoßfeld

5Tobias Hoßfeld

46

Making Money with Server / Mirror

Waiting Queue at Mirrors

X Tons of ads on web pages: several clicks required to start
X Best-effort user and priority users
priority scheduling in queues are offereduser paying money get a better position in queue

X User requests download of an OTRKey at a mirror
X Download request is queued
X Position in queue depends on credit points of the user
X Points can be gained by clicking on ads, paying for a download, ordonating
TV show decoded
as OTRKey

Points of user

Position inqueue

X User does not know
how long he has to wait before being served
which download speed he will get
7Tobias Hoßfeld

8Tobias Hoßfeld

Modeling the Server and its users

Fitting the File Size

X Impatience of users
balking: a customer views a queue and does not enter it
because it is too long.
reneging: a customer joins the queue, but then leaves it
because the waiting time was too longunsatisfied: experienced service rate too low

X measurements in April 2007 over 11563 TV shows (19 channels)
10.90.8

mean: 359.7898 MB
std: 196.8240 MB

0.7
0.6
CDF

X We do not consider different user classes
X Download requests are scheduled in FCFS manner
X At most N users are served in parallel

Erlang-kE[B] = 107.67 MB
k = 3.34

0.5
0.4
0.30.2X Due to large number of users we assume Poisson arrivals
X But flash crowd arrivals:
popular shows are broadcast late (?)
users requests download in the evening (?)

00

9Tobias Hoßfeld

measured
lognormal
erlang-k

0.1

200

400

600
800
size [MB]

1000

1200

1400

Tobias Hoßfeld

General System Model

10Service Rate

X M(t) / GI / 1N – PS with impatience θX State-dependent service rates
at time t the number of served/downloading users is D(t)service rate is inverse of download time for file of size fs

X Nonstationary Poisson process of download requests
X Generally distributed file sizes FX At most N users are served in parallel

guarantees minimal
bandwidth per user

X If, user access speed R is limiting
service rate is constantM(t)/GI/n-FCFS
X Otherwise, state-dependent service rates

homogeneous userswithusers
equal access
X Capacity C of server is equally shared among served
speed

admission control by

X Bandwidth of user is restricted by downlink capacity
R queue sizerestricting
state-dependent patience

X If N users are served, a newly arriving
userenterstime moreaccurate
to waiting queue andis served according to FCFS discipline
capture nearly finished
downloads

X For n ∞ and R>C, system goes towards real processor sharing
M(t)/GI/1-PS

X User leaves after generally distributed impatience time θTobias Hoßfeld

11Tobias Hoßfeld

12

Outline of the Talk

Steady State Analysis with Markov Model
X We consider simplest casearrival rate gets constant: M(t)Mfile size is exponentially distributed
patience time is exponentially distributed

X Online TV Recording Service
X Modeling the service and its users
X Markovian Model for Steady-State Analysis

X User leaves system if patience time exceeded or download readymin{ θ, T } is exponential RV with rate θ / ( θ + T )X Time-Dynamic Evaluation with Fluid Model
X Birth-death process
downloading users

X Numerical Results

λ0X Conclusions

μ1λ

λ...

nμ2μn

13

Tobias Hoßfeld

waiting users

λ1λ...

n+1μn+1μ n+214

Tobias Hoßfeld

Performance Metrics for Markov Model

Steady State Population Distributions

X Waiting probability for a newly arriving customer

X Parameters chosen that N=9<C/R and N=10>C/R∞

pW = ∑ x(i )1i =n0.9

X Occupied server slots
n −1∞

i=0

i =n0.8

E [ X B ] = ∑ ix(i) + n∑ x(i )probability x(i)X Average queue length∞

E [ X W ] = ∑ (i − n) x(i)i=nX Waiting time with Little’s theorem
E [ X W ] = λ E [W ] ⇒ E [W ] =N=9
N=100.6

N=140.50.40.3

E [ XW ]

0.2

λ0.1

X Success probability to finish a download is loss ratepS =N=50.7

E [ X ]θ −1

simulation
analysis0010λ15

Tobias HoßfeldX Cumulated arrival intensities are equal in both scenarios of time t

5060

16

Flash Crowd vs. Poisson Arrivals
X Number of arriving users in the system is limited

0.9250flash crowd arrivals with
time-dependent request rate λ (t)

0.8

0.6

moving average sojourn time [min]0.7

λ (t ) = β e−α tPoisson arrivals with λ0.50.4
0.30.2200

150100Poisson arrivals withconstant request rate λ50

flash crowd arrivals with λ (t)

0.1
0030
40
number i of customers

Tobias Hoßfeld

Simulation of Flash Crowd and Poisson Arrivals

moving average success ratio

20

2

4

6

8
10time [min]Tobias Hoßfeld

12

14

16

0018

17

2

4

6

8
10time [min]Tobias Hoßfeld

1214161818

Outline of the Talk

Fluid Model
X Consider population sizes at time t: Waiting users, Downloadingusers, Finished downloads, Aborted downloads

X Online TV Recording ServiceX A newly arriving customer enters
directly the downloading population, if D(t)<nX Modeling the service and its users

D<nX Markovian Model for Steady-State Analysis
λ (t )

W(1 − p )μD

X Time-Dynamic Evaluation with Fluid ModelFpμA

X Numerical Results

waiting population, if download slots are full
D=nX Conclusionsλ (t )

W~μD(1 − p)μFpμνA

19

Tobias Hoßfeld

20

Tobias Hoßfeld

Fluid Model

Differential Equations

X Waiting users
get impatient and leave system with rate
proceed to downloading state with

X Waiting population

D=nX With probability 1-p download is finished successfully
X Downloading population

λ (t )

W~μ(1 − p)μDpμν

with impatience rate, download rate
and time-dependent capacity per userA

X Aborting and finishing downloads
X We obtainλ (t )

W

D=n~μD(1 − p)μ

Fpμν

A
21

Tobias Hoßfeld

Tobias HoßfeldPopulation Changes with Fluid Model

22

Outline of the Talk

X Analytical results obtained with Runge-Kutta
X Online TV Recording Service700
simulation
analysis600

aborted downloads

500population size

X Modeling the service and its users

waiting users

X Markovian Model for Steady-State Analysis

400

X Time-Dynamic Evaluation with Fluid Model
300
successful downloads

X Numerical Results

200

00X Conclusions

downloading users

100

0.2

0.4

0.6

0.8

1time [s]Tobias Hoßfeld

1.2

1.4

1.6

1.8

24x 1023

Tobias Hoßfeld

24F

File Size Distribution

File Size Distribution

1300
lognormal
exponential
Erlang-k
deterministic

0.9
250
mean download time [min]

0.8
0.7

CDF

0.6clear impact of file sizedistribution

0.5
0.4
0.3
0.2

200

150

100
exponential
Erlang-k
lognormal

0.10050100

50 010150

download time [min]26750
lognormal
exponential
Erlang-k
deterministic

700
650

mean goodput [kbps]

0.35
success ratio

310

File Size Distribution

0.5

0.3
0.25

higher variability of filesize increases successratio

0.20.15

lognormal
exponential
Erlang-k
deterministic

higher variability leads
to successful
downloads of smaller
files

600
550
500

N = C/R is optimal
value

450
400
350

0.13000.05
0 0102Tobias Hoßfeld

File Size Distribution

0.4

11010maximum number of parallel downloads n

25

Tobias Hoßfeld

0.45

higher variability of filesize decreases
download time

121010maximum number of parallel downloads n

250 010310

Tobias Hoßfeld

27

Conclusions

121010maximum number of parallel downloads n

310Tobias Hoßfeld

28

Discussion and Open Issues

X Online TV recording service for distributing large volume video files
X System model proposed: M(t)/GI/1n-PS with impatient users
X Simple analytical results derivedsteady state analysis with Markov Modeltime-dynamic evaluation with fluid model
X Impact of file size distribution is interesting
X Several open issues: general distributions, priority users,
impatience based on experienced performance, ...

First-Come-First-Server
X 1957 Barrer: M/M/1+D
X 1959 Brodi: M/M/1+D
X 1965 Daley: GI/GI/1+GI
X 1966 Gnedenko: M/M/s+D
X 1970 Jarkevic: M/M/s+min(D,M)
X 1971 Jarkevic: M(m)/M/s+GI
X 1980 Haugen: M/M/s+GI
X 1981 Baccelli: M/M/s+GI
X 1997 Brandt: M(n)/M(m)/s+GI
X 2002 Garnett: M/M/n+M

Processor sharing
X 1994 Coffman: M/M/1-PS+M
X Boyer, Guillemin, Robert,Zwart, Bakker ...
X 2006 Gromoll: GI/GI/1-PS+GI• reneging before and while service• state-dependent service rates• impatience time based on QoE• priority classes• heterogeneous access speeds• schedulingTobias Hoßfeld

29

Tobias Hoßfeld

30

Patience Time
Institute of Computer Science
Department of Distributed Systems
Prof. Dr.-Ing. P. Tran-Gia
200

θ = 25 min
θ = 50 min
θ = 100 min
θ = 200 min

180mean download time [min]160

BACKUP

140120100
806040202030405060
maximum number of parallel downloads n

Tobias Hoßfeld

7080

32

Patience Time
0.6
0.55
0.5

θ = 25 min
θ = 50 min
θ = 100 min
θ = 200 min

success ratio

0.45
0.4
0.35
0.3
0.25
0.2
0.15
0.1
20

30

40
5060
maximum number of parallel downloads n

Tobias Hoßfeld

70

80

33

Tobias Hoßfeld

34

X Download a TV show

Tobias Hoßfeld

35

Tobias Hoßfeld

36

Modeling the service and its users
X asTV show

Tobias Hoßfeld

37