Transcript Icc10QoS

Quality of
Service
Support
Multimedia and QoS
#1
QOS in IP Networks
 IETF groups are working on proposals to provide
QOS control in IP networks, i.e., going beyond
best effort to provide some assurance for QOS
 Work in Progress includes RSVP, Differentiated
Services, and Integrated Services
 Simple model
for sharing and
congestion
studies:
Multimedia and QoS
#2
Principles for QOS Guarantees
 Consider a phone application at 1Mbps and an FTP
application sharing a 1.5 Mbps link.


bursts of FTP can congest the router and cause audio packets
to be dropped.
want to give priority to audio over FTP
 PRINCIPLE 1: Marking of packets is needed for
router to distinguish between different classes; and
new router policy to treat packets accordingly
Multimedia and QoS
#3
Principles for QOS Guarantees (more)
 Applications misbehave (audio sends packets at a rate higher
than 1Mbps assumed above);
 PRINCIPLE 2: provide protection (isolation) for one class
from other classes
 Require Policing Mechanisms to ensure sources adhere to
bandwidth requirements; Marking and Policing need to be
done at the edges:
Multimedia and QoS
#4
Principles for QOS Guarantees (more)
 Alternative to Marking and Policing: allocate a set
portion of bandwidth to each application flow; can
lead to inefficient use of bandwidth if one of the
flows does not use its allocation
 PRINCIPLE 3: While providing isolation, it is
desirable to use resources as efficiently as
possible
Multimedia and QoS
#5
Principles for QOS Guarantees (more)
 Cannot support traffic beyond link capacity
 Two phone calls each requests 1 Mbps
 PRINCIPLE 4: Need a Call Admission Process;
application flow declares its needs, network may
block call if it cannot satisfy the needs
Multimedia and QoS
#6
Summary
Multimedia and QoS
#7
Scheduling And Policing Mechanisms
 Scheduling: choosing the next packet for transmission
 FIFO
 Priority Queue
 Round Robin
 Weighted Fair Queuing
 We had a lecture on that!
Multimedia and QoS
#8
Multimedia and QoS
#9
Discussion of RED
 Advantages
 Early drop
 TCP congestion
 Fairness in drops
 Bursty versus non-Bursy
 Disadvantages
 Many additional parameters
 Increasing the loss
Multimedia and QoS
#10
Policing Mechanisms
 (Long term) Average Rate
 100 packets per sec or 6000 packets per min??
• crucial aspect is the interval length
 Peak Rate:
 e.g., 6000 p p minute Avg and 1500 p p sec Peak
 (Max.) Burst Size:
 Max. number of packets sent consecutively, ie over a
short period of time
 Units of measurement
 Packets versus bits
Multimedia and QoS
#11
Policing Mechanisms
 Token Bucket mechanism, provides a means for
limiting input to specified Burst Size and Average
Rate.
 Bucket can hold b tokens;
 tokens are generated at a rate of r token/sec

unless bucket is full of tokens.
 Over an interval of length t, the number of
packets that are admitted is less than or equal to
(r t + b).
Multimedia and QoS
#12
Token bucket example
arrival queue
bucket
sent
p1 (5)
0
-
-
p2 (2)
p1
3
-
p3 (1)
p2
1
p1
1
p3,p2
parameters:
b=5
r=3
4
5
Multimedia and QoS
#13
Integrated Services
 An architecture for providing QOS guarantees in
IP networks for individual application sessions
 relies on resource reservation, and routers need
to maintain state info (Virtual Circuit??),
maintaining records of allocated resources and
responding
to new Call
setup
requests
on that
basis
Multimedia and QoS
#14
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 R-spec
and T-spec to the routers where reservation is
required;
RSVP is a leading candidate for such signaling
protocol
Multimedia and QoS
#15
RSVP request (T-Spec)
 A token bucket specification
 bucket size, b
 token rate, r
 the packet is transmitted onward only if the number of
tokens in the bucket is at least as large as the packet
 peak rate, p
 p >r
 maximum packet size, M
 minimum policed unit, m
 All packets less than m bytes are considered to be m bytes
 Reduces the overhead to process each packet
 Bound the bandwidth overhead of link-level headers
Multimedia and QoS
#16
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.
Multimedia and QoS
#17
Integrated Services: Classes
 Guaranteed QOS: this class is provided with firm
bounds on queuing delay at a router; envisioned for
hard real-time applications that are highly
sensitive to end-to-end delay expectation and
variance
 Controlled Load: this class is provided a QOS
closely approximating that provided by an unloaded
router; envisioned for today’s IP network realtime applications which perform well in an
unloaded network
Multimedia and QoS
#18
R-spec
 An indication of the QoS control service
requested

Controlled-load service and Guaranteed service
 For Controlled-load service
 Simply a Tspec
 For Guaranteed service
 A Rate (R) term, the bandwidth required
• R  r, extra bandwidth will reduce queuing delays

A Slack (S) term
• The difference between the desired delay and the delay
that would be achieved if rate R were used
• With a zero slack term, each router along the path must
reserve R bandwidth
• A nonzero slack term offers the individual routers greater
flexibility in making their local reservation
• Number decreased by routers on the path.
Multimedia and QoS
#19
QoS Routing: Multiple constraints
 A request specifies the desired QoS requirements
 e.g., BW, Delay, Jitter, packet loss, path reliability etc
 Two type of constraints:
 Additive: e.g., delay
 Maximum (or Minimum): e.g., Bandwidth
 Task
 Find a (min cost) path which satisfies the constraints
 if no feasible path found, reject the connection
Multimedia and QoS
#20
Example of QoS Routing
A
B
Constraints: Delay (D) < 25, Available Bandwidth (BW) > 30
Multimedia and QoS
#21
Differentiated Services
 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 want to specify a more
qualitative notion of service
Multimedia and QoS
#22
Differentiated Services
 Approach:
 Only simple functions in the core, and relatively complex
functions at edge routers (or hosts)
 Do not define service classes, instead provides functional
components with which service classes can be built
Multimedia and QoS
#23
Edge Functions at DiffServ (DS)
 At DS-capable host or first DS-capable router
 Classification: edge node marks packets according
to classification rules to be specified (manually by
admin, or by some TBD protocol)
 Traffic Conditioning: edge node may delay and
then forward or may discard
Multimedia and QoS
#24
Core Functions
 Forwarding: according to “Per-Hop-Behavior” or
PHB specified for the particular packet class; such
PHB is strictly based on class marking (no other
header fields can be used to influence PHB)
 BIG ADVANTAGE:
No state info to be maintained by routers!
Multimedia and QoS
#25
Classification and Conditioning
 Packet is marked in the Type of Service (TOS) in
IPv4, and Traffic Class in IPv6
 6 bits used for Differentiated Service Code Point
(DSCP) and determine PHB that the packet will
receive
 2 bits are currently unused
Multimedia and QoS
#26
Classification and 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
Multimedia and QoS
#27
Forwarding (PHB)
 PHB result in a different observable (measurable)
forwarding performance behavior
 PHB does not specify what mechanisms to use to
ensure required PHB 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
Multimedia and QoS
#28
Forwarding (PHB)
 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)
 Assured Forwarding: 4 classes, each guaranteed a
minimum amount of bandwidth and buffering; each with
three drop preference partitions
Multimedia and QoS
#29
Differentiated Services Issues
 AF and EF are not even in a standard track yet…
research ongoing
 “Virtual Leased lines” and “Olympic” services are
being discussed
 Impact of crossing multiple ASs and routers that
are not DS-capable
Multimedia and QoS
#30
DiffServ Routers
DiffServ
Edge
Router
Classifier
DiffServ
Core
Router
Marker
Select PHB
Extract
DSCP
PHB
PHB
PHB
PHB
Meter
Policer
Local
conditions
Packet
treatment
Multimedia and QoS
#31
IntServ vs. DiffServ
IntServ
network
DiffServ
network
"Call blocking"
approach
"Prioritization"
approach
Multimedia and QoS
#32
Comparison of Intserv & Diffserv
Architectures
Intserv
Granularity of service
differentiation
State in routers(e.g.
scheduling, buffer
management)
Traffic Classification
Basis
Type of service
differentiation
Individual Flow
Admission Control
Required
Signaling Protocol
Required(RSVP)
Diffserv
Per Flow
Aggregate of
flows
Per Aggregate
Several header fields
DS Field
Deterministic or
statistical guarantees
Absolute or
relative
assurance
Required for
absolute
differentiation
Not required for
relative schemes
Multimedia and QoS
#33
Comparison of Intserv & Diffserv
Architectures
Coordination for
service differentiation
Scope of Service
Differentiation
Scalabilty
Network Accounting
Network Management
Interdomain
deployment
Intserv
Diffserv
End-to-End
Local (Per-Hop)
A Unicast or Multicast Anywhere in a
path
Network or in
specific paths
Limited by the number Limited by the
of flows
number of classes
of service
Based on flow
Based on class
characteristics and QoS usage
requirement
Similar to Circuit
Similar to existing
Switching networks
IP networks
Multilateral
Bilateral
Agreements
Agreements
Multimedia and QoS
#34
Diffserv
Theoretical
Model
Multimedia and QoS
#35
Basic Theoretical Model
 Single FIFO queue.
 Bounded capacity: holds up to B packets
 All packets have same size
 Packet Arrival: arbitrary
 Packet Send: 1 packet/time unit
 Actions:
 Non-Preemptive model: accept or reject
 Preemptive model: also preempt
FIFO
Multimedia and QoS
#36
Packet Values
 Goal:
 Each packet has an intrinsic value
 maximize the total value of packet sent!
 Cheap and expensive packets (two values):
 low value of 1 and high value of 
 Continuous packet values
 any value in [1,]
Multimedia and QoS
#37
Competitive Analysis
 Analysis for online algorithms
packets
algorithm
decisions
 For a given sequence S: VA(S) / Vopt(S)
 Competitive Ratio: MINS {VA(S) / Vopt(S)}
 Worse case guarantee
Multimedia and QoS
#38
Non-Preemptive Policies
 Fixed Partition(x)
 At most xB low value and (1-x)B high value.
 Flexible Partition (x)
 At most xB low value and any high value.
 Round Robin(x):
 Like fixed partition.
 send x low and (1-x) high [fractional!]
 Simulate it using FIFO queue.
Multimedia and QoS
#39
Implementing Round Robin
 Implementation:
 Maintain two variables:
• high
• low

If low packet arrives tests low +1 < xB
• IF YES ACCEPT
• IF NO REJECT


High packets the same
Sending:
• low = low –x
• high = high – (1-x)
 Main observation:
 once a packet is accepted it will be sent eventually.
 Sending order not important!
Multimedia and QoS
#40
Analysis of Round Robin
 Consider the case that all packet values are 1.
 Claim:
 For any input sequence
 The number of packet a buffer of size B/2 accepts
 is at least half of a buffer of size B
 Let x= ½
 Consider Low and High packets separately
 RR(½) :
 Accepts at least half High and half Low
 Benefit at least half
Multimedia and QoS
#41
Preemptive Policies
 Greedy:
 Always accept if the buffer is not full
 Preempt a low value packet to accept a high one
 COMPETITIVE RATIO 2
 -Preemptive:
 Drop from the head packets with total value /
 Active queue management (AQM)
Multimedia and QoS
#42
Preemptive Model: 1/2 -Preemptive
 We consider 1/2-Preemptive Policy
 There are two packet values: 1 and 
 For =9 each high value packet preempts 3 low
value packets (pro-active preemptions)
high
low
Multimedia and QoS
#43
1/2-Preemptive: Theorem
 Claim 1: VA(Slow) VOPT(Slow)
+ 1/1/2 VOPT(Shigh)
 Claim 2: VA(Shigh)  VOPT(Shigh) + 1/1/2 VOPT(Shigh)
 Theorem:
VA(S)  VOPT(S) + 2/1/2 VOPT(S)
Multimedia and QoS
#44
Optimal Offline
 Process the packet in decreasing order of value.
 Accept a packet if possible.
 otherwise reject
 Two values:
 Maximizes
the number of high value packets
• Given a buffer of size B

Maximizes the total number of packets
• Using the remaining buffer space.
Multimedia and QoS
#45
Proof Outline: Claim 2
We partition the schedule to intervals:
• Intervals ends when the buffer is empty.
• Overloaded intervals: some high value packet is lost
and only high value packets are scheduled.
• Underloaded intervals: no high value packet is lost
time
Overloaded Intervals
Multimedia and QoS
#46
Proof (Claim 1):
 We show: VA(Slow) VOPT(Slow)
+ 1/1/2 VA(Shigh)
 Low packet loss: overflow + Preemption
 Low packet lost in overflow:

Opt also lost a packet.
 Low packet preempted by a high packet
 Value of high 
 Preempted 1/2
 Value is 1/1/2 V(high)
 Recall VA(Shigh)  VOPT(Shigh)
Multimedia and QoS
#47
Proof Outline (Claim2):
We divide the HIGH packet loss into two subsets:
• The packets lost by OPT (easy case)
• The packets scheduled by OPT
Multimedia and QoS
#48
Proof Outline (Claim 2):
Observation 1:
When some high value packet is lost the buffer is
full of high value packets
B
high
Multimedia and QoS
#49
Proof Outline (Claim 2):
Observation 2:
If there are at least B/1/2 high value packets in the
buffer then the next packet to be scheduled is a high
value packet.
B/1/2
high
Multimedia and QoS
#50
Proof Outline (Claim 2):
• Observation 1  The length of an overloaded
interval is at least B
• Observation 2  An optimal offline policy could
have scheduled at most B/1/2 additional high value
packets
• The ratio between the additional loss and the benefit
of the overloaded interval is bounded by 1/1/2
•VA(Shigh)  VOPT(Shigh) + 1/1/2 VOPT(Shigh)
Multimedia and QoS
#51
Lower bound (Non-Preemptive)
 Scenario:
 B low value packets
 [maybe] B high value packets
 Online: accepts xB low value
 Case I: only low values
• Online xB Offline B

Case II: Both low and high value
• online xB + (1-x) B offline B
 Competitive ratio  /(2-1)
 For large values of  we have /(2-1)  ½
Multimedia and QoS
#52
Lower bound: Preemptive model
 Scenario:
 B low value packets
 For zB time units:
• one high value packet arrives each time unit

[Maybe] B high value packets
 Let zB be the time the Online sends the last low
 (1) No more packets arrive
 (2) B high value packets arrive
 Online Benefit:
(1) zB + zB (2) zB + B
 Offline Benefit: (1) B + zB (2) zB + B
 Solving for best z gives a lower bound (about 0.8)
Multimedia and QoS
#53
Fixed vs. Flexible Partition
Arrival event
time
Flexible
Fixed
B high
B/2 low
1
B high
B/2 high
B/2 low
B/2 low
B/2 high
B/2
B/2 low
B/2 low
B
B/2 high
B/2 low
Multimedia and QoS
#54
Summary of Results: Non-preemptive
Values
Multiple
Two values
Policies
Always accept
Round Robin
Fixed Partition
Flexible Partition
Dynamic Flexible Partition
Impossibility
optimal online
Policies
cont RR
Impossibility
= 
=2
=1
0
½
[1/3,0.41]
0.41
½
½
½
½
½
[0.41,1/2]
[0.41,0.56]
[0.53,0.56]
2/3
2/3
1
½
½
1
1
1
1
Competitive ratio
1/(2+ ln )
1/(1+ ln )
Multimedia and QoS
#55
Summary of Results: Preemptive
Multiple Values
Policies
Greedy
Better Than G
Impossibility
Competitive ratio
½
1/(1.98..)
0.8
2 Values
Policies
1/2-Preemptive
Impossibility
Competitive ratio
1-2/1/2
1-1/(21/2)
Multimedia and QoS
#56