Transcript IP: Addresses and Forwarding

Better-than-best-effort: QoS,
IntServ, DiffServ, RSVP, RTP
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
[email protected]
http://www.ecse.rpi.edu/Homepages/shivkuma
Based in part on slides of Ion Stoica, Jim Kurose, Srini Seshan, Srini Keshav
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
1
Overview





Why better-than-best-effort (QoS-enabled) Internet ?
Quality of Service (QoS) building blocks
End-to-end protocols: RTP, H.323
Network protocols:
 Integrated Services(IntServ), RSVP.
 Scalable differentiated services: DiffServ
Control plane: QoS routing, traffic engineering, policy
management, pricing models
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
2
Why Better-than-Best-Effort (QoS)?

To support a wider range of applications
 Real-time, Multimedia, etc

To develop sustainable economic models and
new private networking services
 Current flat priced models, and best-effort
services do not cut it for businesses
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
3
Quality of Service: What is it?
Multimedia applications:
network audio and video
QoS
network provides
application with level of
performance needed for
application to function.
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
4
What is QoS?

“Better performance” as described by a set of
parameters or measured by a set of metrics.

Generic parameters:
 Bandwidth
 Delay, Delay-jitter
 Packet loss rate (or loss probability)

Transport/Application-specific parameters:
 Timeouts
 Percentage of “important” packets lost
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
5
What is QoS (contd) ?

These parameters can be measured at several
granularities:
 “micro” flow, aggregate flow, population.

QoS considered “better” if
 a) more parameters can be specified
 b) QoS can be specified at a fine-granularity.

QoS spectrum:
Best Effort
Leased Line
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
6
Fundamental Problems
Scheduling Discipline
FIFO
B

B
In a FIFO service discipline, the performance assigned to
one flow is convoluted with the arrivals of packets from all
other flows!
 Cant get QoS with a “free-for-all”
 Need to use new scheduling disciplines which provide
“isolation” of performance from arrival rates of
background traffic
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
7
Fundamental Problems

Conservation Law
(Kleinrock): (i)Wq(i) = K

Irrespective of scheduling
discipline chosen:


Average backlog
(delay) is constant

Average bandwidth is
constant
Zero-sum game => need
to “set-aside” resources
for premium services
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
8
QoS Big Picture: Control/Data Planes
Control Plane: Signaling + Admission Control or
SLA (Contracting) + Provisioning/Traffic Engineering
Router
Workstation
Router
Internetwork or WAN
Router
Workstation
Data Plane: Traffic conditioning (shaping, policing, marking
etc) + Traffic Classification + Scheduling, Buffer management
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
9
QoS Components
QoS => set aside resources for premium services
 QoS components:
 a) Specification of premium services:
(service/service level agreement design)
 b) How much resources to set aside?
(admission control/provisioning)
 c) How to ensure network resource utilization,
do load balancing, flexibly manage traffic
aggregates and paths ?
(QoS routing, traffic engineering)

Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
10
QoS Components (Continued)
 d)
How to actually set aside these resources in
a distributed manner ?
(signaling, provisioning, policy)
 e) How to deliver the service when the traffic
actually comes in (claim/police resources)?
(traffic shaping, classification, scheduling)
 f) How to monitor quality, account and price
these services?
(network mgmt, accounting, billing, pricing)
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
11
How to upgrade the Internet for QoS?

Approach: de-couple end-system evolution from
network evolution

End-to-end protocols: RTP, H.323 etc to spur the
growth of adaptive multimedia applications
 Assume best-effort or better-than-best-effort
clouds

Network protocols: IntServ, DiffServ, RSVP,
MPLS, COPS …
 To support better-than-best-effort capabilities
at the network (IP) level
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
12
QOS SPECIFICATION,
TRAFFIC, SERVICE
CHARACTERIZATION,
BASIC MECHANISMS
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
13
Service Specification
Loss: probability that a flow’s packet is lost
 Delay: time it takes a packet’s flow to get from
source to destination
 Delay jitter: maximum difference between the
delays experienced by two packets of the flow
 Bandwidth: maximum rate at which the soource
can send traffic
 QoS spectrum:

Best Effort
Leased Line
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
14
Hard Real Time: Guaranteed
Services
Service contract
 Network to client: guarantee a deterministic
upper bound on delay for each packet in a
session
 Client to network: the session does not send
more than it specifies
 Algorithm support
 Admission control based on worst-case
analysis
 Per flow classification/scheduling at routers

Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
15
Soft Real Time: Controlled Load
Service
Service contract:
 Network to client: similar performance as an
unloaded best-effort network
 Client to network: the session does not send
more than it specifies
 Algorithm Support
 Admission control based on measurement of
aggregates
 Scheduling for aggregate possible

Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
16
Traffic and Service Characterization
To quantify a service one has two know
 Flow’s traffic arrival
 Service provided by the router, i.e., resources
reserved at each router
 Examples:
 Traffic characterization: token bucket
 Service provided by router: fix rate and fix
buffer space
 Characterized by a service model (service
curve framework)

Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
17
Token Bucket
Characterized by three parameters (b, r, R)
 b – token depth
 r – average arrival rate
 R – maximum arrival rate (e.g., R link capacity)
 A bit is transmitted only when there is an available token
 When a bit is transmitted exactly one token is
consumed

r tokens per second
b tokens
bits
slope r
b*R/(R-r)
slope R
<= R bps
time
Shivkumar Kalyanaraman
regulator
Rensselaer Polytechnic Institute
18
Characterizing a Source by Token
Bucket
Arrival curve – maximum amount of bits transmitted by
time t
 Use token bucket to bound the arrival curve

bps
bits
Arrival curve
time
time
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
19
Example
Arrival curve – maximum amount of bits transmitted by
time t
 Use token bucket to bound the arrival curve

bits
(b=1,r=1,R=2)
Arrival curve
2
5
size of time
4
bps
3
2
2
1
1
0
1
2
3
4
5
1
time
3
4
interval
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
20
Per-hop Reservation


Given b,r,R and per-hop delay d
Allocate bandwidth ra and buffer space Ba such that to
guarantee d
slope ra
bits
slope r
Arrival curve
b
d
Ba
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
21
What is a Service Model?
“external process”
Network element
offered traffic


delivered traffic
(connection oriented)
The QoS measures (delay,throughput, loss, cost)
depend on offered traffic, and possibly other
external processes.
A service model attempts to characterize the
relationship between offered traffic, delivered
traffic, and possibly other external processes.
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
22
Arrival and Departure Process
Rin
Network Element
bits
Rout
Rin(t) = arrival process
= amount of data arriving up to time t
delay
buffer
Rout(t) = departure process
= amount of data departing up to time t
t
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
23
Traffic Envelope (Arrival Curve)

Maximum amount of service that a flow can send
during an interval of time t
b(t) = Envelope
slope = max average rate
“Burstiness Constraint”
slope = peak rate
Shivkumar
Kalyanaraman
t
Rensselaer Polytechnic Institute
24
Service Curve
Assume a flow that is idle at time s and it is
backlogged during the interval (s, t)
 Service curve: the minimum service received by
the flow during the interval (s, t)

Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
25
Big Picture
Service curve
bits
bits
Rin(t)
slope = C
bits
t
t
Rout(t)
t
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
26
Delay and Buffer Bounds
bits
E(t) = Envelope
Maximum delay
Maximum buffer
S (t) = service curve
t
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
27
Mechanisms: Traffic Shaping/Policing

Token bucket: limits input to specified Burst Size (b)
and Average Rate (r).
 Traffic sent over any time T <= r*T + b
 a.k.a Linear bounded arrival process (LBAP)

Excess traffic may be queued, marked BLUE, or
simply dropped
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
28
Mechanisms: Queuing/Scheduling
Traffic
Sources
$$$$$$



Traffic
Classes
Class A
$$$
Class B
$
Class C
Use a few bits in header to indicate which queue (class)
a packet goes into (also branded as CoS)
High $$ users classified into high priority queues,
which also may be less populated
=> lower delay and low likelihood of packet drop
Ideas: priority, round-robin, classification, aggregation,
...
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
29
Mechanisms: Buffer Mgmt/Priority Drop
Drop RED and BLUE packets
Drop only BLUE packets

Ideas: packet marking, queue thresholds,
differential dropping, buffer assignments
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
30
SCHEDULING
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
31
Packet Scheduling

Decide when and what packet to send on output link
 Usually implemented at output interface
flow 1
Classifier
1
2
flow 2
Scheduler
flow n
Buffer
management
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
32
Focus: Scheduling Policies



Priority Queuing: classes have different priorities;
class may depend on explicit marking or other
header info, eg IP source or destination, TCP Port
numbers, etc.
Transmit a packet from the highest priority class
with a non-empty queue
Preemptive and non-preemptive versions
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
33
Scheduling Policies (more)

Round Robin: scan class queues serving one
from each class that has a non-empty queue
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
34
Round-Robin Discussion

Advantages: protection among flows
 Misbehaving flows will not affect the performance
of well-behaving flows
 Misbehaving flow – a flow that does not
implement any congestion control
 FIFO does not have such a property

Disadvantages:
 More complex than FIFO: per flow queue/state
 Biased toward large packets – a flow receives
service proportional to the number of packets
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
35
Generalized Processor Sharing(GPS)
Assume a fluid model of traffic
 Visit each non-empty queue in turn (RR)
 Serve infinitesimal from each
 Leads to “max-min” fairness
 GPS is un-implementable!
 We cannot serve infinitesimals, only packets

Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
36
Generalized Processor Sharing

A work conserving GPS is defined as
Wi (t , t  dt) W (t , t  dt)

wi
 jB(t ) wj

i  B(t )
where
 wi – weight of flow i
 Wi(t1, t2) – total service received by flow i during [t1, t2)
 W(t1, t2) – total service allocated to all flows during [t1, t2)
 B(t) – number of flows backlogged
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
37
Fair Rate Computation in GPS
Associate a weight wi with each flow i
 If link congested, compute f such that

 max(r , f  w )  C
i
i
i
(w1 = 3) 8
10
4
4
2
(w2 = 1) 6
(w3 = 1) 2
f = 2:
min(8, 2*3) = 6
min(6, 2*1) = 2
min(2, 2*1) = 2
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
38
Bit-by-bit Round Robin

Single flow: clock ticks when a bit is transmitted.
For packet i:
 Pi = length, Ai = arrival time, Si = begin
transmit time, Fi = finish transmit time
 Fi = Si+Pi = max (Fi-1, Ai) + Pi

Multiple flows: clock ticks when a bit from all
active flows is transmitted  round number
 Can calculate Fi for each packet if number of
flows is known at all times
This can be complicated
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
39
Packet Approximation of Fluid
System



Standard techniques of approximating fluid GPS
 Select packet that finishes first in GPS
assuming that there are no future arrivals
Important properties of GPS
 Finishing order of packets currently in system
independent of future arrivals
Implementation based on virtual time
 Assign virtual finish time to each packet upon
arrival
 Packets served in increasing order of virtual
times
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
40
Fair Queuing (FQ)




Idea: serve packets in the order in which they would have
finished transmission in the fluid flow system
Mapping bit-by-bit schedule onto packet transmission
schedule
Transmit packet with the lowest Fi at any given time
Variation: Weighted Fair Queuing (WFQ)
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
41
Approximating GPS with WFQ

0

Fluid GPS system service order
2
4
6
8
10
Weighted Fair Queueing
 select the first packet that finishes in GPS
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
42
FQ Example
Flow 1
Flow 2
Output
F=10
F=8
Flow 1
(arriving)
F=5
Cannot preempt packet
currently being transmitted
Flow 2
transmitting
Output
F=10
F=2
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
43
FQ Advantages
FQ protect well-behaved flows from ill-behaved flows
 Example: 1 UDP (10 Mbps) and 31 TCP’s sharing a
10 Mbps link
10
2
9
1.8
RED
8
Throughput(Mbps)
Throughput(Mbps)

7
6
5
4
3
2
1.4
1.2
1
0.8
0.6
0.4
1
0.2
0
0
1
4
7
10 13 16 19 22 25 28 31
FQ
1.6
1
Flow Number
4
7
10 13 16 19 22 25 28 31
Flow Number
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
44
System Virtual Time: V(t)
Measure service, instead of time
 V(t) slope – rate at which every active flow receives service
 C – link capacity
 N(t) – number of active flows in fluid system at time t

V(t)
V (t )
C

t
N (t )
time
Service
in fluid flow
system
1
2
1
2
3
3
4
4
5
6
5
time
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
45
System Virtual Time

Virtual time (VGPS) – service that backlogged
flow with weight = 1 would receive in GPS
W (t , t  dt)
Wi (t , t  dt)  wi 
 jB(t ) wj
Wi
wi
W


t
 jB(t ) wj t
i  B(t )
i  B(t )


1

W
 dt
Wi (t1 , t2 )  wi   

t t1 

w

t

j
 jB (t )

t2
VGPS
1
W


t
 jB(t ) wj t
i  B(t )
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
46
Service Allocation in GPS

The service received by flow i during an interval
[t1,t2), while it is backlogged is
VGPS
Wi (t1 , t 2 )  wi  
dt
t t1
t
t2
i  B(t )
Wi (t1, t2 )  wi  (VGPS (t2 )  VGPS (t1 ))
i  B(t )
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
47
Virtual Time Implementation of
Weighted Fair Queueing
V
GPS
(0)  0
S kj  Fjk
if session j backlogged
S j  max(Fj ,V (akj ))
if session j un-backlogged
Fj  S j 
Lkj
w
j
ajk – arrival time of packet k of flow j
 Sjk – virtual starting time of packet k of flow j
 Fjk – virtual finishing time of packet k of flow j
 Ljk – length of packet k of flow j

Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
48
Virtual Time Implementation of
Weighted Fair Queueing
Need to keep per flow instead of per packet
virtual start, finish time only
 System virtual time is used to reset a flow’s
virtual start time when a flow becomes
backlogged again after being idle

Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
49
System Virtual Time in GPS
1/2
1/8
1/8
1/8
1/8
VGPS (t )
2*C
C
2*C
0
4
8
12
16
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
50
Virtual Start and Finish Times

Utilize the time the packets would start Sik and
finish Fik in a fluid system
k
L
Fi k  Sik  i
wi
VGPS (t )
Fi k
Sik
0
4
8
12
16
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
51
Big Picture
FQ does not eliminate congestion  it just
manages the congestion
 You need both end-host congestion control and
router support for congestion control
 end-host congestion control to adapt
 router congestion control to protect/isolate
 Don’t forget buffer management: you still need to
drop in case of congestion. Which packet’s would
you drop in FQ?
 one possibility: packet from the longest queue

Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
52
QoS ARCHITECTURES
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
53
Parekh-Gallager theorem
Let a connection be allocated weights at each
WFQ scheduler along its path, so that the least
bandwidth it is allocated is g
 Let it be leaky-bucket regulated such that # bits
sent in time [t1, t2] <= g(t2 - t1) + 
 Let the connection pass through K schedulers,
where the kth scheduler has a rate r(k)
 Let the largest packet size in the network be P

K 1
K
k 1
k 1
end _ to _ end _ delay   / g   P / g   P / r (k )
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
54
Significance
P-G Theorem shows that WFQ scheduling can
provide end-to-end delay bounds in a network of
multiplexed bottlenecks
 WFQ provides both bandwidth and delay
guarantees
 Bound holds regardless of cross traffic
behavior (isolation)
 Needs shapers at the entrance of the network
 Can be generalized for networks where
schedulers are variants of WFQ, and the link
service rate changes over time

Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
55
Stateless vs. Stateful QoS Solutions


Stateless solutions – routers maintain no fine grained
state about traffic
 scalable, robust
 weak services
Stateful solutions – routers maintain per-flow state
 powerful services
 guaranteed services + high resource utilization
 fine grained differentiation
 protection
 much less scalable and robust
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
56
Existing Solutions
Stateful
Stateless
Tenet [Ferrari &
 DiffServ
Verma ’89]
QoS
- [Clark &
 IntServ [Clark et al
Wroclawski ‘97]
’91]
- [Nichols et al ’97]
 ATM [late ’80s]
 Round Robin [Nagle  DecBit [Ramkrishnan &
’85]
Jain ’88]
Network
support for  Fair Queueing
 Random Early Detection
congestion
[Demers et al ’89]
(RED) [Floyd & Jacobson
control
 Flow Random Early ’93]
Drop (FRED) [Lin &
 BLUE [Feng et al ’99]
Morris ’97]
 REM Shivkumar
[Low atKalyanaraman
al ’00]
Rensselaer Polytechnic Institute

57
Integrated Services (IntServ)


An architecture for providing QOS guarantees in IP
networks for individual application sessions
Relies on resource reservation, and routers need to
maintain state information of allocated resources (eg:
g) and respond to new Call setup requests
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
58
Signaling semantics





Classic scheme: sender initiated
SETUP, SETUP_ACK, SETUP_RESPONSE
Admission control
Tentative resource reservation and confirmation
Simplex and duplex setup; no multicast support
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
59
RSVP: Internet Signaling
Creates and maintains distributed reservation
state
 De-coupled from routing:
 Multicast trees setup by routing protocols, not
RSVP (unlike ATM or telephony signaling)
 Receiver-initiated: scales for multicast
 Soft-state: reservation times out unless refreshed
 Latest paths discovered through “PATH”
messages (forward direction) and used by RESV
mesgs (reverse direction).

Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
60
Call Admission
Session must first declare its QOS requirement
and characterize the traffic it will send through
the network
 R-spec: defines the QOS being requested
 T-spec: defines the traffic characteristics
 A signaling protocol is needed to carry the Rspec and T-spec to the routers where reservation
is required; RSVP is a leading candidate for such
signaling protocol

Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
61
Call Admission

Call Admission: routers will admit calls based on
their R-spec and T-spec and base on the current
resource allocated at the routers to other calls.
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
62
Stateful Solution: Guaranteed
Services

Achieve per-flow bandwidth and delay guarantees
 Example: guarantee 1MBps and < 100 ms delay to a flow
Receiver
Sender
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
63
Stateful Solution: Guaranteed
Services

Allocate resources - perform per-flow admission
control
Receiver
Sender
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
64
Stateful Solution: Guaranteed
Services

Install per-flow state
Receiver
Sender
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
65
Stateful Solution: Guaranteed
Services

Challenge: maintain per-flow state consistent
Receiver
Sender
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
66
Stateful Solution: Guaranteed
Services

Per-flow classification
Receiver
Sender
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
67
Stateful Solution: Guaranteed
Services

Per-flow buffer management
Receiver
Sender
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
68
Stateful Solution: Guaranteed
Services
• Per-flow scheduling
Receiver
Sender
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
69
Stateful Solution Complexity


Data path
 Per-flow classification
 Per-flow buffer
management
 Per-flow scheduling
Control path
 install and maintain
per-flow state for
data and control paths
Per-flow State
…
flow 1
flow 2
Classifier
Scheduler
flow n
Buffer
management
output interface
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
70
Stateless vs. Stateful
Stateless solutions are more
 scalable
 robust
 Stateful solutions provide more powerful and
flexible services
 guaranteed services + high resource utilization
 fine grained differentiation
 protection

Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
71
Question

Can we achieve the best of two worlds, i.e.,
provide services implemented by stateful
networks while maintaining advantages of
stateless architectures?
 Yes, in some interesting cases. DPS, CSFQ.

Can we provide reduced state services, I.e.,
maintain state only for larger granular flows
rather than end-to-end flows?
 Yes: Diff-serv
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
72
Differentiated Services (DiffServ)




Intended to address the following difficulties with
Intserv and RSVP;
Scalability: maintaining states by routers in high
speed networks is difficult sue to the very large
number of flows
Flexible Service Models: Intserv has only two
classes, want to provide more qualitative service
classes; want to provide ‘relative’ service distinction
(Platinum, Gold, Silver, …)
Simpler signaling: (than RSVP) many applications
and users may only w ant to specify a more
qualitative notion of service
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
73
Differentiated Services Model
Interior Router
Ingress
Edge Router


Egress
Edge Router
Edge routers: traffic conditioning (policing, marking, dropping),
SLA negotiation
 Set values in DS-byte in IP header based upon negotiated
service and observed traffic.
Interior routers: traffic classification and forwarding (near
stateless core!)
 Use DS-byte as index into forwarding table
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
74
Diffserv Architecture
Edge router:
- per-flow traffic
management
scheduling
r marking
- marks packets as inprofile and out-profile
b
..
.
Core router:
- per class TM
- buffering and scheduling
based on marking at edge
- preference given to in-profile packets
- Assured Forwarding
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
75
Packet format support
Packet is marked in the Type of Service (TOS) in
IPv4, and Traffic Class in IPv6: renamed as “DS”
 6 bits used for Differentiated Service Code Point
(DSCP) and determine PHB that the packet will
receive
 2 bits are currently unused

Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
76
Traffic Conditioning

It may be desirable to limit traffic injection rate of
some class; user declares traffic profile (eg, rate
and burst size); traffic is metered and shaped if
non-conforming
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
77
Per-hop Behavior (PHB)

PHB: name for interior router data-plane functions
 Includes scheduling, buff. mgmt, shaping etc

Logical spec: PHB does not specify mechanisms
to use to ensure performance behavior

Examples:
 Class A gets x% of outgoing link bandwidth
over time intervals of a specified length
 Class A packets leave first before packets from
class B
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
78
PHB (contd)

PHBs under consideration:
 Expedited Forwarding: departure rate of
packets from a class equals or exceeds a
specified rate (logical link with a minimum
guaranteed rate)
Emulates leased-line behavior
 Assured Forwarding: 4 classes, each
guaranteed a minimum amount of bandwidth
and buffering; each with three drop preference
partitions
 Emulates frame-relay behavior
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
79
Question

Can we achieve the best of two worlds, i.e.,
provide services implemented by stateful
networks while maintaining advantages of
stateless architectures?
 Yes, in some interesting cases. DPS, CSFQ.

Can we provide reduced state services, I.e.,
maintain state only for larger granular flows
rather than end-to-end flows?
 Yes: Diff-serv
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
80
Scalable Core (SCORE)

A trusted and contiguous region of network in which
 edge nodes – perform per flow management
 core nodes – do not perform per flow management
core nodes
edge nodes
edge nodes
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
81
The DPS Approach
1.
Define a reference stateful network that
implements the desired service
2. Emulate the functionality of the reference
network in a SCORE network
Reference Stateful Network
SCORE Network
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
82
The DPS Idea

Instead of having core routers maintaining perflow state have packets carry per-flow state
Reference Stateful Network
SCORE Network
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
83
Dynamic Packet State (DPS)

Ingress node: compute and insert flow state
in packet’s header
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
84
Dynamic Packet State (DPS)

Ingress node: compute and insert flow state
in packet’s header
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
85
Dynamic Packet State (DPS)

Core node:
 process packet based on state it carries
and node’s state
 update both packet and node’s state
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
86
Dynamic Packet State (DPS)

Egress node: remove state from packet’s
header
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
87
Example: DPS-Guaranteed Services


Goal: provide per-flow delay and bandwidth guarantees
How: emulate ideal model in which each flow traverses
dedicated links of capacity r
flow
(reservation = r )

r
r
r
Per-hop packet service time = (packet length) / r
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
88
Guaranteed Services

Define reference network to implement service
 control path: per-flow admission control, reserve
capacity r on each link
 data path: enforce ideal model, by using Jitter
Virtual Clock (Jitter-VC) scheduler
Jitter-VC
Jitter-VC Jitter-VC
Jitter-VC
Jitter-VC
Jitter-VC Jitter-VC
Reference Stateful Network
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
89
Guaranteed Services

Use DPS to eliminate per-flow state in core
 control path: emulate per-flow admission control
 data path: emulate Jitter-VC by Core-Jitter
Virtual Clock (CJVC)
Jitter-VC
Jitter-VC Jitter-VC
Jitter-VC
Jitter-VC
CJVC
CJVC
Jitter-VC Jitter-VC
CJVC
CJVC
CJVC
CJVC
Reference Stateful Network
SCORE
Network
Shivkumar
Kalyanaraman
Rensselaer Polytechnic Institute
90
End-to-end Adaptive Applications
Video Coding, Error
Concealment,
Unequal Error
Protection (UEP)
Packetization,
Marking, playout
Buffer Management
Congestion control
Video Coding, Error
Concealment,
Unequal Error
Protection (UEP)
Packetization,
Marking, Source
Buffer Management
Congestion control
Internet
End-to-end
Closed-loop control
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
91
End-to-end: Real-Time Protocol (RTP)
Provides standard packet format for real-time
application
 Typically runs over UDP
 Specifies header fields below
 Payload Type: 7 bits, providing 128 possible
different types of encoding; eg PCM, MPEG2
video, etc.
 Sequence Number: 16 bits; used to detect
packet loss

Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
92
Real-Time Protocol (RTP)
Timestamp: 32 bytes; gives the sampling instant
of the first audio/video byte in the packet; used
to remove jitter introduced by the network
 Synchronization Source identifier (SSRC): 32
bits; an id for the source of a stream; assigned
randomly by the source

Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
93
RTP Control Protocol (RTCP)




Protocol specifies report packets exchanged
between sources and destinations of multimedia
information
Three reports are defined: Receiver reception,
Sender, and Source description
Reports contain statistics such as the number of
packets sent, number of packets
lost, inter-arrival jitter
Used to modify sender
transmission rates and
for diagnostics purposes
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
94
Eg: Streaming & RTSP
User interactive control is provided, e.g. the
public protocol Real Time Streaming Protocol
(RTSP)
 Helper Application: displays content, which is
typically requested via a Web browser; e.g.
RealPlayer; typical functions:
 Decompression
 Jitter removal
 Error correction: use redundant packets to be
used for reconstruction of original stream
 GUI for user control

Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
95
Using a Streaming Server



Web browser requests and receives a Meta File
(a file describing the object)
Browser launches the appropriate Player and passes
it the Meta File;
Player contacts a streaming server, may use a choice
of UDP vs. TCP to get the stream
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
96
Receiver Adaptation Options


If UDP: Server sends at a rate appropriate for client;
to reduce jitter, Player buffers initially for 2-5
seconds, then starts display
If TCP: sender sends at maximum possible rate;
retransmit when error is encountered; Player uses a
much large buffer to smooth delivery rate of TCP
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
97
H.323
H.323 is an ITU standard for multimedia
communications over best-effort LANs.
 Part of larger set of standards (H.32X) for
videoconferencing over data networks.
 H.323 includes both stand-alone devices and
embedded personal computer technology as well
as point-to-point and multipoint conferences.
 H.323 addresses call control, multimedia
management, and bandwidth management as
well as interfaces between LANs and other
networks.

Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
98
H.323 Architecture
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
99
Inter-domain QoS: Challenge
Provide high quality service across ISPs
 Problem: intermediate ISPs don’t have
incentive to provide “good” service
 e.g., “hot-potato” policy

ISP 2
?
ISP 3
ISP 1
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
100
Approach: Virtual ISP (V-ISP)


Avoid crossing ISP boundaries
 Each ISP will provide good service; V-ISP can easily
verify it
Allocate/buy service across each ISP and compose them
GPoP
(core)
GPoP
(core)
ISP 2
Proxy
(edge)
ISP 3
Proxy
(edge)
ISP 1
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
101
Composition Tools for QoS

Dynamic Packet State (DPS):
Proxy (edge): maintain per flow state; label packets
 Giga PoPs (core): maintain no per flow state;
process packets based on their labels


Closed-loop building blocks:

No core upgrades, smaller QoS service spectrum
I
Logical FIFO
B
I
Rensselaer Polytechnic Institute
E
E
E
I
Shivkumar Kalyanaraman
102
Closed-Loop Building Blocks for QoS
International Link
or
International Link
or
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
103
Edge-based QoS building blocks
I
E
Logical FIFO
B
I
E
E
I
New: Closed-loop control !
Policy/
Bandwidth Broker
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
104
Closed-loop QoS Building Blocks
Priority/WFQ
B
FIFO

B
Scheduler: differentiates service on a packet-bypacket basis

Loops: differentiate service on an RTT-by-RTT basis
using purely edge-based policy configuration.

Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
105
Recall: Accumulation-based CC Schemes!
1
j
j+1
J
dj
fi
μi
Λi
Λi,j+1
j
…
qi1 (t  di )
f
μi
…
J 1
qij (t   d k )
k j
di
I i (t  di , t )
dj
f
d J 1
f
qiJ (t )
ai (t )
t
1
j
time
Rensselaer Polytechnic Institute
106
Oi (t , t )
ai (t  t )
j+1
J
Shivkumar Kalyanaraman
106
Recall: Accumulation-based CC Schemes!
1
j
j+1
J
dj
fi
μi
Λi
Λi,j+1
j
…
qi1 (t  di )
f
μi
…
J 1
qij (t   d k )
k j
di
I i (t  di , t )
dj
f
d J 1
f
qiJ (t )
ai (t )
t
1
j
time
Rensselaer Polytechnic Institute
107
Oi (t , t )
ai (t  t )
j+1
J
Shivkumar Kalyanaraman
107
Recall: Accln-based Control Policy
1
j
j+1
J
dj
fi
μi
Λi

Λi,j+1
j
μi
control objective : keep ai (t )   i  0
 if ai (t )  0 , no way to probe increase of available
bandwidth;

control algorithm :
if
ai (t )   i
then i 
if
ai (t )   i
then i 
rec : ai (t , t )  [i (t  d i f , t )  i (t , t )] t
108
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
108
Recall: “Monaco” CC Scheme
 congestion
estimation:
 out-of-band
 congestion
and in-band control packets
response:
qm < α, cwnd(k+1) = cwnd(k) + 1;
 if qm > β, cwnd(k+1) = cwnd(k) – 1;[ 1 = α < β = 3 ]
 if
109
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
109
Closed-Loop Service Differentiation:
Loss-based or Accumulation-based ?
110
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
110
Closed-Loop QoS: Bandwidth
Assurances
Flow 1 with 4 Mbps assured
+ 3 Mbps best effort
Flow 2 with 3 Mbps best effort
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
111
QoS: an application-level approach
sophisticated services in application
• architecturally “above” network core
• open services: let 1000 flowers bloom
simple, fast, diffserv network
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
112
QoS: an application-level approach
Application-level infrastructure
• accommodate network-level service
• additional tailoring of user services
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
113
Content Delivery Motivation: congestion
Networks
Browsers
Routers
Web Servers
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
114
Content Delivery: idea
• Reduces load on server
• Avoids network congestion
Browsers
Replicated
content
Content Sink
Router
Content Source
Web Server
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
115
CDN: Architectural Layout
Request
Routing(RR)
4
1
Client
6
5
Distribution
System
2
Origin
3
Surrogate
 Publisher informs RR of Content Availability.
 Content Pushed to Distribution System.
 Client Requests Content, Requested redirected to RR.
 RR finds the most suitable Surrogate
 Surrogate services client request.
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
116
Summary





QoS big picture, building blocks
Integrated services: RSVP, 2 services, scheduling,
admission control etc
Diff-serv: edge-routers, core routers; DS byte
marking and PHBs
Real-time transport/middleware: RTP, H.323
New problems: inter-domain QoS, Application-level
QoS, Content delivery/web caching
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
117