Transcript A Framework for End-to

Measuring Service in Multi-Class Networks
Aleksandar Kuzmanovic and Edward W. Knightly
Rice Networks Group
http://www.ece.rice.edu/networks
Background

QoS services
– SLA guaranteed rate

Ex. Class X serviced at
minimum rate R
– Relative performance

Ex. Class X has strict
priority over class Y
– Statistical service

Ex. P(class X pkt.
Delay>100ms)<.001
Need:

QoS mechanisms
– Priority queues

Rate-based, delaybased...
– Policing

Rate limiting...
– Over-engineering

Just add more
bandwidth...
Tools for network clients to assess the
networks QoS capabilities
Kuzmanovic & Knightly | Rice Networks Group | INFOCOM 2001
Inverse QoS Problem
Assess mechanisms and parameters of an unknown QoS system





Is a class rate limited?
What is the inter-class relationship?
– Fair/weighted fair/strict priority
Is resource borrowing fully allowed or not?
Is the service’s upper bound identical to its lower
bound?
What are the service’s parameters?
Kuzmanovic & Knightly | Rice Networks Group | INFOCOM 2001
Applications - Network Example
Providers reluctant to divulge precise QoS
policy (if any...)
B

SLA validation for VPNs
– Is the SLA fulfilled?

Capacity planning
– What is the relationship
among classes?

A
VPN class 1
VPN class 2
Background
Edge-based admission control [CK00] and
implementation [SSYK01]
Kuzmanovic & Knightly | Rice Networks Group | INFOCOM 2001
Performance Monitoring and
Resource Management



Single WEB server
– CPU resource sharing
– Listen queue differentiation
– Admission control
Distributed WEB server
– Load balancing
Internet Data Center
– Machine migration
Goal:
Back-end
Server
Front End
Server
Measurement
Module
Back-end
Server
Back-end
Server
Estimate a class’ net “guaranteed rate”
Kuzmanovic & Knightly | Rice Networks Group | INFOCOM 2001
“Off-Line” Solution is Simple

Consider a router with unknown QoS mechanisms
Input
Class 1
Class 2
Output
Unknown QoS
Mechanism
Packet Arrivals
Full Capacity
Class 1
rate limited
Class 2
not rate limited
Weighted Fairness
Output Rate
Kuzmanovic & Knightly | Rice Networks Group | INFOCOM 2001
“On-Line” Case: Operational
Network


Undesirable to disrupt on-going services
– High rate probes to detect inter-class
relationships would degrade performance
Impossible to force other classes to be idle
– … to detect policers
Unknown QoS
Mechanism
Kuzmanovic & Knightly | Rice Networks Group | INFOCOM 2001
System Model and Problem
Formulation


Two stage server
– Non-work conserving elements
– Multi-class scheduler
Rate Limiters Unknown Multi-Class Server
Observations
– Arrival and
departure times
– Class ID
– Packet size
Kuzmanovic & Knightly | Rice Networks Group | INFOCOM 2001
Determine...

Infer the service discipline
– Most likely hypothesis among WFQ, EDF and SP

Detect the existence of non-work conserving
elements
– Rate limiters (ex. leaky bucket policers)

Estimate the system parameters
– WFQ guaranteed rates, EDF deadlines, rate
limiter values
Kuzmanovic & Knightly | Rice Networks Group | INFOCOM 2001
Remaining Outline

Inter-class Resource Sharing Theory

Empirical Arrival and Service Models

MLE of Parameters

EDF/WFQ/SP Hypothesis Testing

Simulation Results and Conclusions
Kuzmanovic & Knightly | Rice Networks Group | INFOCOM 2001

General statistical char. for a
(virtual) minimally
backlogged flow

Flows receive additional
service beyond min rate
– Function of other flow
demand
– Function of scheduler


service
Theoretical Tool: Statistical
Service Envelopes [QK99]
99% service
General characterization of
inter-class resource sharing
Framework for admission
control for EDF/WFQ/SP
Kuzmanovic & Knightly | Rice Networks Group | INFOCOM 2001
guaranteed
rate
interval
Strategy

Inter-class theory
S i (t )  f ( B n (t ), H k , )

S i (t )
Service
B n (t )
Arrivals
Hk
Hypothesis

Unknowns
Key technique:
– Passively monitor arrivals and services at edges
– Devise hypothesis tests to jointly:


Detect most likely hypothesis
Estimate unknown parameters
Kuzmanovic & Knightly | Rice Networks Group | INFOCOM 2001
Empirical Arrival Model
E*( I ) = 3
time
t


t+I
Envelopes characterize arrivals as a function of
interval length
– Statistical traffic envelope [QK99]
Empirical envelope - measure first two moments of
arrivals over multiple time scales
Goal:
S i  f ( B n , H k , )  p ( S i | H k , )
assuming Gaussian distribution for B
Kuzmanovic & Knightly | Rice Networks Group | INFOCOM 2001
Empirical Service Model
Service

A real-world paradigm for statistical service
envelope
Observe: Service can be measured only when
packets are backlogged
Arrivals
Departures
Interval
Arrivals
Departures
Service

Interval
Kuzmanovic & Knightly | Rice Networks Group | INFOCOM 2001
Empirical Service Distributions

For each class and time scale
– Expected service distributions p( s | H k , )
– Service measures (data)
Empirical service distributions
35
35
Empirical rate proability
Empirical rate proability

30
25
20
15
10
5
0
0
100
200
300
400
500
600
700
800
900
30
25
20
15
10
5
0
0
100
200
300
400
500
600
700
Service rate (Kbps)
Service rate (Kbps)
WFQ (400 ms)
SP (400 ms)
Kuzmanovic & Knightly | Rice Networks Group | INFOCOM 2001
800
900
Parameter Estimation and
Scheduler Inference

GLRT for each time scale
~
(s1 , s 2 ) 
max p(s1 , s 2 | WFQ , 1 , 2 )
1 ,2
max p(s1 , s 2
d1 , d 2



>
1
<
| EDF, d , d )
1
2
Under MLE parameters for
each scheduler
Choose most likely scheduler
Apply majority rule over all
time scales
si
Service for class i (data)
WFQ
Hypothesis 1
EDF
Hypothesis 2
i
di
Unknown parameters
Kuzmanovic & Knightly | Rice Networks Group | INFOCOM 2001
EDF/WFQ Testing

Correctness ratio
True WFQ  94%
True EDF  100%
Importance of time scales


Short time scales
– Fluid vs. packet model
Long time scales
– Ratio of delay shift and
time scale decreases as
time scale increases
(d1=25ms)
Kuzmanovic & Knightly | Rice Networks Group | INFOCOM 2001
Measurable Regions

What if there is no traffic in
particular class?

What traffic load “allows”
inferences?

Region where we are able to
estimate true value within
5%

Typical utilization should be
> 62% for 1.5 Mbps link

Otherwise, active probing
required
Kuzmanovic & Knightly | Rice Networks Group | INFOCOM 2001
Conclusions

Framework for clients of multi-class services to
assess a system’s core QoS mechanisms
– Scheduler type
– Estimate parameters (both w-c and n-w-c)

General multiple time-scale traffic and service model
to characterize a broad set of behaviors within a
unified framework
Kuzmanovic & Knightly | Rice Networks Group | INFOCOM 2001
Measuring Service in Multi-Class Networks
Aleksandar Kuzmanovic and Edward W. Knightly
Rice Networks Group
http://www.ece.rice.edu/networks
Ongoing Work


Unknown cross-traffic
– Cannot monitor all
A
systems inputs/outputs
– Treat cross-traffic statistics
VPN class 1
VPN class 2
as another unknown
Background
Web servers
– Evaluation of the framework in a single web
server through trace driven simulations
– Capacity is statistically characterized
Kuzmanovic & Knightly | Rice Networks Group | INFOCOM 2001
B
WFQ Parameter Estimation


Class 1: 65-68 flows
Class 2: 25-28 flows
Large windows improve
confidence level
– T=2sec: 95% in 11% of
true value
– T=10sec: 95% in 1.4% of
true value
 Flow level dynamics & nonstationarities must be
considered
0.9
WFQ relative weight estimate

0.85
0.8
0.75
0.7
0.65
0.6
0.55
0.5
1
2
3
4
5
6
7
8
9
Measurement interval (sec)
Kuzmanovic & Knightly | Rice Networks Group | INFOCOM 2001
10
11
Rate Limited Class State Detection

Can include parameter r in
service envelope equations
for each class
Importance of time scales


Example
– Class based fair queuing
– C=1.5Mbps, r=1Mbps
Probability decreases with
time scale  higher errors
when measuring multi-level
leaky-buckets
Kuzmanovic & Knightly | Rice Networks Group | INFOCOM 2001
Generalized Likelihood Ratio Test

Detection with unknowns
~
( x) 
max p( x | H1 ,1 ) H 1
>
1
<
max p( x | H , ) H
1
0


0
0
0
x
Data set
Hi
Hypothesis
 i, j
Unknown parameters
Note: we do not find a single value of  that
maximizes likelihood ratio
Under mild conditions (as N  ), GLRT is
Uniformly Most Powerful (maximizes the probability
of detection)
Kuzmanovic & Knightly | Rice Networks Group | INFOCOM 2001