Transcript Engineering for QoS and the limits of service differentiation

Tequila Workshop
Jan 2001
The statistical nature of
traffic and its impact on
the realisability of QoS
guarantees
Jim Roberts, France Telecom R&D
([email protected])
France Télécom R&D
Quality of service: a commodity?
Example SLS:
Scope: N/N
Flow identification: EF-valued DSCP, set of destination prefixes
Traffic conformance: token bucket (r,b)
Excess treatment: drop
Service schedule: Oct 3, 9:00 - 11:00
Performance parameters: 0% loss
The role of traffic engineering:
What is the relation between (r,b) and user traffic characteristics ?
How can the network guarantee 0% loss ?
How much does this service cost ?
Maybe these questions don’t have a satisfactory answer...
depending on the statistical nature of traffic and the realisability of QoS
guarantees
France Télécom R&D
Outline
What is “Quality of Service” ?
Characterising IP traffic
Performance for stream applications
Performance for elastic applications
QoS and pricing
France Télécom R&D
QoS and reservation
users express their demand in terms of aggregates
different classes (EF, AF1-4, ...)
different scopes : point to point,..., point to world, (world to point?)
e.g., 2 Mb/s “class 1” from A to B, 5 Mb/s “class 3” from A to C or D,...
network filters traffic at ingress
packets are “in” or “out” ... or “nearly in”
e.g., token bucket, sliding window,...
network “reserves” bandwidth
admission control / traffic engineering
using policy servers, signalling,...
resource provisioning
relies on “adequate provisioning”
e.g., service differentiation through different overbooking factors
France Télécom R&D
Doubts about aggregates
traffic characterization
can a user choose its filter parameters?
how can the network reserve enough resources?
what about the small user?
end-to-end performance
what absolute quality of service?
what relative quality of service?
pricing
pricing for value...
...or pricing for cost?
France Télécom R&D
QoS and end-to-end performance
transparency for streaming applications
audio and video: interactive or playback
QoS  low packet loss and delay
scope for differentiation: real time/non-real time, hi-fi / lo-fi,...
response time for elastic applications
Web, e-mail, file transfer, MP3,...
QoS  high throughput
scope for differentiation: interactive/background, large flows/small flows,...
QoS is a statistical phenomenon
probabilities, averages,...
...depending on available capacity
...and traffic demand
QoS is often binary
“good enough”...
...or “too bad” !
France Télécom R&D
Outline
What is Quality of Service?
Characterising IP traffic
Performance for stream applications
Performance for elastic applications
QoS and pricing
France Télécom R&D
Internet traffic is self-similar
a self-similar process
variability at all time scales
due to:
infinite variance of flow size
TCP induced burstiness
Ethernet traffic, Bellcore 1989
France Télécom R&D
Internet traffic is self-similar
a self-similar process
variability at all time scales
due to:
infinite variance of flow size
TCP induced burstiness
a practical consequence
difficult to characterise a traffic
aggregate
10 s
Ethernet traffic, Bellcore 1989
France Télécom R&D
Traffic on a US backbone link
(Thomson et al, 1997)
traffic intensity is predictable ...
... and stationary in the busy hour
France Télécom R&D
Traffic on a French backbone link
traffic intensity is predictable ...
... and stationary in the busy hour
tue
12h
France Télécom R&D
wed
thu
18h
fri
sat
00h
sun
mon
06h
IP flows
a flow = one instance of a given application
a "continuous flow" of packets
basically two kinds of flow, stream and elastic
stream flows
audio and video, real time and playback
rate and duration are intrinsic characteristics
highly variable rate and duration
Poisson arrival process (?)
elastic flows
digital documents ( Web pages, files, ...)
rate and duration are measures of performance
highly variable size
Poisson arrivals (?)
95% of packets are in elastic flows
France Télécom R&D
Modelling traffic demand
stream traffic demand
arrival rate x bit rate x duration
elastic traffic demand
arrival rate x size
a stationary process in the "busy hour"
e.g., Poisson flow arrivals, independent flow size
traffic
demand
Mbit/s
busy hour
France Télécom R&D
time of day
Outline
What is Quality of Service?
Characterising IP traffic
Performance for stream applications
Performance for elastic applications
QoS and pricing
France Télécom R&D
Open loop control for stream
traffic
buffered of bufferless multiplexing ?
jitter control ?
admission control or adaptive applications ?
reservation or implicit admission control ?
scope for service differentiation ?
user-network
interface
France Télécom R&D
network-network
interface
user-network
interface
Buffered multiplexing
performance
a buffer to absorb rate overload
admission control to ensure
Pr[buffer overflow]<e
but performance depends on complex
traffic characteristics
e.g., self-similarity
 QoS of buffered multiplexing is
uncontrollable
0
buffer size
0
NB. token bucket is a virtual queue
difficult choice of r and b parameters?
 no satisfactory descriptor for
more variable
variable rate flows or aggregates
less variable
log Pr[saturation]
France Télécom R&D
“Bufferless” multiplexing: alias
rate envelope multiplexing
admission control to ensure Pr [Lt>C] < e
performance depends only on stationary rate distribution
loss rate  E [(Lt -C)+] / E [Lt]
performance is insensitive to self-similarity (and other correlation)
“negligible jitter” for flows shaped at the ingress (cf. INFOCOM 2001)
output
rate C
combined
input
rate Lt
time
France Télécom R&D
Efficiency of bufferless
multiplexing
low loss imposes small amplitude of rate variations ...
peak rate << link rate (eg, 1%)
... or low utilisation
overall mean rate << link rate
we may have both in an integrated network
priority to streaming traffic
residue shared by elastic flows
France Télécom R&D
Implicit admission control
accept new flow only if transparency preserved
given flow peak rate
and estimated available bandwidth
reject new flow if necessary
by discarding first packets (probes)
uncritical decision threshold if streaming traffic is light
in an integrated network
France Télécom R&D
Differentiation for stream traffic
 different delays?
 priority queues, WFQ, ...
 but what guarantees?
 different loss?
 different utilisation (WFQ, ...)
 "spatial queue priority"
delay
delay
loss
loss
 partial buffer sharing, push out
 or negligible loss and delay for all
 elastic-stream integration ...
 ... and low stream utilisation
loss
delay
France Télécom R&D
Provisioning for negligible
blocking
"classical" teletraffic theory; assume
Poisson arrivals, rate l
constant rate per flow r
mean duration 1/m
 mean demand, A = l/m r bits/s
blocking probability for capacity C
B = E(C/r,A/r)
E(m,a) is Erlang's formula:
m
 E(m,a)= a /
m!
 scale economies
generalizations exist:
for different rates
for variable rates
France Télécom R&D

ai
i m i !
utilization (r=a/m) for E(m,a) = 0.01
r
0.8
0.6
0.4
0.2
m
0
20
40
60
80
100
Outline
What is Quality of Service?
Characterising IP traffic
Performance for stream applications
Performance for elastic applications
QoS and pricing
France Télécom R&D
Closed loop control for elastic
traffic
impact of packet scale on flow scale response time?
performance of statistical bandwidth sharing ?
need for admission control ?
scope for service differentiation ?
user-network
interface
France Télécom R&D
network-network
interface
user-network
interface
Bandwidth and packet loss rate
congestion
avoidance
loss rate
p
B(p)
a multi-fractal arrival process
but loss and bandwidth related by TCP (cf. Padhye et al.)
Wmax
for p = 0
RTT
1
B( p ) 
for small p > 0
2
RTT 2 p / 3  T0 min 1,3 3p / 8 p(1  32 p )
1
for p  1
64T0


thus, p = p(B): i.e., loss rate depends on bandwidth share
France Télécom R&D
Bandwidth sharing
reactive control (TCP, scheduling) shares bottleneck bandwidth
unequally
depending on RTT, protocol implementation, etc.
and differentiated services parameters
optimal sharing in a network: objectives and algorithms...
max-min fairness, proportional fairness, maximal utility,...
... but response time depends more on traffic process than the static
sharing algorithm!
Example: a linear network
route 0
route 1
France Télécom R&D
route L
Flow level performance of a
bottleneck link
assume perfect fair shares
link rate C, n elastic flows 
each flow served at rate C/n
assume Poisson flow arrivals
an M/G/1 processor sharing queue
load, r = arrival rate x size / C
performance insensitive to size distribution
Pr [n transfers] = rn(1-r)
E [response time] = size / C(1-r)
instability if r > 1
i.e., unbounded response time
stabilized by aborted transfers...
... or by admission control
link capacity C
fair shares
 a processor sharing queue
throughput
C
r
0
0
France Télécom R&D
1
Generalizations of PS model
non-Poisson arrivals
transfer
Poisson
session
arrivals
Poisson sessions
general session structure
discriminatory processor sharing
weight fi for class i flows
service rate  fi
rate limitations (same for all flows)
maximum rate per flow (eg, access rate)
minimum rate per flow (by admission control)
France Télécom R&D
flows
processor
sharing
think time
infinite
server
Admission control can be useful
France Télécom R&D
Admission control can be useful
France Télécom R&D
Admission control can be useful
...
... to prevent disasters at sea !
France Télécom R&D
Admission control can also be
useful for IP flows
improve efficiency of TCP
reduce retransmissions overhead ...
... by maintaining throughput
implicit admission control
discard packets of new flows
when available capacity is low
prevent instability
due to overload (r > 1)...
...and retransmissions
avoid aborted transfers
user impatience
"broken connections"
a means for service differentiation...
France Télécom R&D
Choosing an admission control
threshold
 N = the maximum number of flows admitted
 negligible blocking when r<1, maintain quality when r>1
 M/G/1/N processor sharing system
 bandwidth  C/N; bandwidth  C/N , for r>1
 Pr [blocking] = rN(1 - r)/(1 - rN+1)  (1 - 1/r) , for r>1
 uncritical choice of threshold
 eg, 1% of link capacity (N=100)
1
300
.8
Blocking probability
E [Response time]/size
200
.6
.4
r = 1.5
r = 1.5
100
.2
r = 0.9
r = 0.9
0
0
0
France Télécom
R&D100
200
N
0
100
200
N
Impact of access rate on
backbone sharing
TCP throughput is limited by access rate...
modem, DSL, cable
... and by server performance, TCP receive window, other links,...
 backbone link transparent unless saturated!
ie, unless r > 1 (or r > 0.9...)
throughput
C
backbone link
(rate C)
access links
(rate<<C)
access
rate
0
0
France Télécom R&D
1
r
Differentiation for elastic traffic
different utilization
separate pipes
class based queuing
different per flow shares
WFQ
impact of RTT,...
throughput
C
access
rate
0
r
0
discrimination in overload
impact of aborts (?)
or by admission control
1
throughput
C
access
rate
0
France Télécom R&D
0
r
1
Integrating streaming and
elastic traffic
priority to packets of streaming flows
low utilization  negligible loss and delay
using EF ?
elastic flows use all remaining capacity
better response times
per flow fair queuing (?)
to prevent overload
implicit admission control...
...and adaptive routing
an identical admission criterion for streaming and elastic flows
available rate > R
France Télécom R&D
Differentiation by accessibility
 block class 1 when 100 flows in progress
- block class 2 when N2 flows in progress
 in underload: both classes have negligible blocking (B1  B2  0)
 in overload: discrimination is effective
 if r1 < 1 < r1 + r2, B1 0,
B2  (r1+r2-1)/r2
 if 1 < r1,
B1 (r1-1)/r1, B2  1
1
1
1
r1 = r2 = 0.4
r1 = r2 = 0.6
0
0
N2
France Télécom R&D
r1 = r2 = 1.2
B2
.33
B2B10
B2
B1
0
0
N2
B1
.17
100
0
N2
100
Provisioning for negligible
blocking for elastic flows
"elastic" teletraffic theory; assume
Poisson arrivals, rate l
mean size s
blocking probability for capacity C
utilization r = ls/C
m = admission control limit
 B(r,m) = rm(1-r)/(1-rm+1)
impact of access rate
C/access rate = m
B(r,m)  E(m,rm)
utilization (r) for B = 0.01
r
0.8
E(m,rm)
0.6
0.4
0.2
m
0
France Télécom R&D
20
40
60
80
100
Outline
What is Quality of Service?
Characterising IP traffic
Performance for stream applications
Performance for elastic applications
QoS and pricing
France Télécom R&D
Service differentiation and
pricing
different QoS requires different prices...
or users will always choose the best
...but streaming and elastic applications are qualitatively different
choose streaming class for transparency
choose elastic class for throughput
 no need for streaming/elastic price differentiation
different prices exploit different "willingness to pay"...
bringing greater economic efficiency
...but QoS is not stable or predictable
depends on route, time of day,..
and on factors outside network control: access, server, other networks,...
 network QoS is not a sound basis for price discrimination
France Télécom R&D
Pricing to pay for the network
fix a price per byte
to cover the cost of infrastructure and operation
estimate demand
at that price
provision network to handle that demand
with excellent quality of service
optimal price
 revenue = cost
capacity
demand
demand
capacity
$$$
$$$
time of day
France Télécom R&D
time of day
Price differentiation
maximise value by exploiting different “willingness to pay”
business, professional, residential
price components
flat rate subscription
per byte charge ( 0)
time of day variations
price differences based on stable criteria
e.g., access rate, available services
pay for differentiated accessibility...
e.g., flat rate payment for guaranteed reliability
...but not for congestion
i.e., pay more for worse quality !
France Télécom R&D
Conclusions
a statistical characterisation of demand
a stationary random process in the busy period
a flow level characterisation (streaming and elastic flows)
transparency for streaming flows
rate envelope ("bufferless") multiplexing
the "negligible jitter conjecture"
response time for elastic flows
a "processor sharing" flow scale model
instability in overload (i.e., E[demand]>capacity)
service differentiation
distinguish streaming and elastic classes
limited scope for within-class differentiation
flow admission control in case of overload
pricing
per byte + flat rate charges
France Télécom R&D
C
r
0
0
1