Transcript Chapter6.5

Quality of Service
Outline
Realtime Applications
Integrated Services
Differentiated Services
Spring 2002
CS 332
1
Application Classes
• Elastic: applications that can work fine without
guarantees of timely delivery of data
– Telnet, FTP, email, Web browser, etc.
• Real-time: sensitive to timeliness of data
–
–
–
–
Late data is completely worthless
Voice and video applications, industrial control, etc.
Hard real-time: data late => disaster (possible loss of life)
Soft real-time: data late => headache
We consider only soft real-time here
Spring 2002
CS 332
2
Realtime Applications
• Require “deliver on time” assurances
– must come from inside the network
Microphone
Sampler,
A D
converter
Buffer,
D A
Speaker
• Example application (audio)
–
–
–
–
–
sample voice once every 125us
each sample has a playback time
packets experience variable delay in network
add constant offset to playback time: playback point
trouble only if playback buffer drained
Spring 2002
CS 332
3
Playback Buffer
Sequence number
Packet
arrival
Packet
generation
Playback
Network
delay
Buffer
Time
Spring 2002
CS 332
4
Delay Variability
90% 97% 98%
Packets (%)
3
99%
2
1
50
100
150
200
Delay (milliseconds)
Spring 2002
CS 332
5
Taxonomy of RT Apps
• Tolerance of data loss (loss = late or lost packets)
– Tolerant: can tolerate occasional loss (e.g. can
interpolate to overcome loss of a single packet in audio
stream with little effect)
– Intolerant: even single lost packet is problematic (e.g.
industrial control “shut-down” packet)
• Note real-time can be more tolerant than non-realtime (consider FTP)
Spring 2002
CS 332
6
Taxonomy of RT Apps
• Adaptability
– Ex. Can (and do) adjust playback point in audio stream
slightly while executing
– Delay-adaptive applications: can adjust playback point
– Rate-adaptive applications: can trade off bit rate versus
quality (e.g. video apps can use coding algorithms with
parameters that can be set for differing levels of quality)
• Internet service model good for elastics, but
obviously not good for the rest of the crowd
Spring 2002
CS 332
7
Taxonomy
Applications
Real time
Tolerant
Adaptive
Delayadaptive
Nonadaptive
Elastic
Intolerant
Rate-adaptive
Interactive
Interactive
bulk
Asynchronous
Nonadaptive
Rateadaptive
Spring 2002
CS 332
8
Approaches
• Fine-grained: provide QoS to individual apps or
flows
– Integrated Services: developed by IETF and typically
associated with the Resource Reservation Protocol
(RSVP)
• Coarse-grained: provide QoS to larges classes of
data or aggregated traffic
– Differentiated Services (currently undergoing
standardization)
Spring 2002
CS 332
9
RSVP Service Classes
• Guaranteed: network guarantees maximum delay
that any packet will experience
– For intolerant apps
• Controlled Load: emulates a lightly loaded network,
even if network is heavily loaded
– For tolerant, adaptive apps
– Use queuing (i.e. WFQ) to isolate controlled load traffic
– Ex. Audio teleconferencing app vat
• Adjusts playback point according to network delay
• Can tolerate up to 10% packet loss
Spring 2002
CS 332
10
Implementation Issues
• Need to tell network what QoS we need (give it a
flowspec)
• Network needs to decide if it can provide
requested service (admission control)
• Need way for network and user to communicate
the above and other service info (resource
reservation, a.k.a. signalling)
• Network routers need way to meet service
requirement (packet scheduling)
Spring 2002
CS 332
11
Flowspec
• RSpec: describes service requested from network
(relatively easy)
– controlled-load: none
– guaranteed: delay target or related info
• TSpec: describes flow’s traffic characteristics (not
so easy)
– Need to give network enough info to make intelligent
admission control decisions
– Average bandwidth fails to account for burstiness (think
of 10 flows with average rate of 1 MBps each being
multiplexed onto 10MBps link)
Spring 2002
CS 332
12
Example TSpec: Token Bucket
•
•
•
•
•
•
•
•
Average bandwidth + burstiness: token bucket filter
Token rate r
Bucket size B
Must have n tokens to send n bytes
Accumulate tokens at rate of r per second (start with 0)
Can accumulate no more than B tokens
Can send any “bytes” in bucket as fast as you can/wish
Ex. Flow A: r = 1 MBps, B = 1
Flow B: r = 1 MBps, B = 1 MB
(note could describe A with same
TSpec)
Note: be explicit, save resources
Spring 2002
CS 332
13
Admission Control
• Look at RSpec and TSpec and decide whether to
admit new flow based on available resources and
other commitments
• Per-Router mechanism
• Very dependent on type of requested service and
queuing disciplines in routers
• Not same as policing (checking that individual
flows are adhering to their advertised RSpec)
Spring 2002
CS 332
14
RSVP
• Significantly different than typical signalling
protocols for connection-oriented networks
• Key assumption: do not detract from robustness of
connectionless network
– Lack of router state in connectionless allows for end-toend connectivity even during crash and reboot cycles
– RSVP uses soft state: does not need to be explicitly
deleted when no longer needed (instead refresh
periodically)
Spring 2002
CS 332
15
RSVP (cont.)
• Goal: support multicast as effectively as unicast(?!)
• Receiver-oriented protocol
– Because multicast typically has lots more receivers than
senders (senders shouldn’t need to keep track of all this)
– Because receivers have different requirements and may
wish to receive from different sets of senders
• Nice properties:
– Easy to change resource allocations provided to receiver
– Periodic refresh handles host crashes, down links, and the
like
Spring 2002
CS 332
16
RSVP (yet again)
• Sender transmits PATH message containing TSpec, routers
along path record reverse path from receiver to sender
• Receiver sends RECV message back up tree with Tspec and
Rspec.
• Each router along path performs admission control. If yes,
pass RECV toward root of tree, if no, send an error message
to receiver
• Source transmits PATH messages every 30 seconds
• Destination transmits RESV message every 30 seconds
• Merge requirements in case of multicast
• Can specify number of speakers
Spring 2002
CS 332
17
RSVP Example
Sender 1
PATH
R
Sender 2
R
PATH
RESV
(merged)
R
RESV
R
R
Receiver A
RESV
Receiver B
Spring 2002
CS 332
18
Packet Processing
• classification: associate each packet with the appropriate
reservation
– Examine source address, dest address, protocol number, source
port and dest port (or use single FlowLabel field in IPv6)
– Use mapping from flow-specific info to service class identifier
• Guaranteed: mapping may be one-to-one
• Controlled load: mapping may be many-to-one
• scheduling: manage queues so each packet receives the
requested service (not simple)
– Guaranteed: probably some form of WFQ
– Controlled load: maybe aggregate flows into single stream and use
a form of WFQ
– Difficulty: many services provided concurrently, each requiring its
own scheduling algorithm
Spring 2002
CS 332
19
A Big Problem…
• Consider the following: an OC-48 (2.5 Gbps) link
representing several multiplexed 64 Kbps audio
streams. Number of flows is thus:
(2.5  109)/(64  103) = 39,000
• Each flow has associated state which needs to be
periodically refreshed
• Each flow needs to be policed, classified, queued,
etc
• So clearly the problem is scalability (it’s BAD!)
Spring 2002
CS 332
20
Differentiated Services
• Solves scalability problems by allocating
resources to small number of classes of traffic
– Premium
– Best-effort
• Once packets marked, how are they handled?
– IETF standardizing set of per-hop behaviors (PHBs)
– Redefined TOS byte from IP header: six bits allocated
for Differentiated Services code points (DSCP), which
determines which PHB gets used.
Spring 2002
CS 332
21
Example PHBs
• Expedited Forwarding (EF)
– Packets marked EF forwarded with minimal delay and
loss
– Potential implementation strategies:
• Give EF strict priority over other packets
• Perform WFQ with EF packets, with weight set high enough to
guarantee necessary EF packet bandwidth (better than above
since helps prevent starvation for non-EF packets, including
things like routing update packets)
Spring 2002
CS 332
22
Example PHBs (cont.)
• Assured forwarding (AF)
– Based on RED with In and Out (RIO) or Weighted
RED
– Two classes of packets,
“In” (green curve) and “Out”
Used in conjunction with
“profile meter”
Spring 2002
CS 332
23