Transcript Scheduling - s3.amazonaws.com

Chapter 6 outline
 6.1 Multimedia
 6.5 Beyond Best Effort
Networking Applications  6.6 Scheduling and
 6.2 Streaming stored
Policing Mechanisms
audio and video
(cont)
 RTSP
 6.7 Integrated Services
 6.3 Real-time,
Interactive Multimedia:  6.8 RSVP
Internet Phone Case
 6.9 Differentiated
Study
Services
 6.4 Protocols for RealTime Interactive
Applications


RTP,RTCP
SIP
Scheduling
 scheduling: choose next packet to send on link
 FIFO (first in first out) scheduling: send in order of
arrival to queue


real-world example?
discard policy: if packet arrives to full queue: who to discard?
• Tail drop: drop arriving packet
• priority: drop/remove on priority basis
• random: drop/remove randomly
Scheduling (more)
Priority scheduling: transmit highest priority queued
packet
 multiple classes, with different priorities


class may depend on marking or other header info, e.g. IP
source/dest, port numbers, etc..
Real world example?
Scheduling (more)
round robin scheduling:
 multiple classes
 cyclically scan class queues, serving one from each
class (if available)
 real world example?
Scheduling (more)
Weighted Fair Queuing:
 generalized Round Robin
 each class gets weighted amount of service in each
cycle
 real-world example?
Scheduling and delay (a measure of quality)
 Basic scheduling policy
 Single queue, no priority, FIFO
 Recall, average queuing delay
d = 1 / (  )


Scheduling and delay (more)
 Priority scheduling
 Simple example: 2 classes/queues, each /2 arrival rates
 What are the average delays of two classes?
 Higher-priority packets: do you see it?
 Lower-priority packets: tricky (notice work-conserving).
/2

/2
Scheduling and delay (more)
 Round robin scheduling
 Simple example: two queues, 1 packet per round, no
priority
 What is the average queuing delay of a packet?
/2

/2
 How about Weighted Fair Queuing? Much more
complicated and need queuing theory (beyond this
course).
Policing mechanisms
Goal: limit traffic to not exceed declared parameters
Three common-used criteria:
 (Long term) Average Rate: how many packets can be
sent per unit time (in the long run)

crucial question: what is the interval length: 100 packets per
second or 6000 packets per min have same average!
 Peak Rate: e.g., 6000 packets per min. (ppm) avg.;
1000 packets per sec. peak rate
 (Max.) Burst Size: max. number of packets sent
consecutively (with no intervening idle)
Policing mechanisms (more)
Token Bucket: limits input to specified Burst Size
and Average Rate.
 bucket can hold b tokens
 tokens generated at rate r token/sec unless bucket
full
 Over any interval of length t: number of packets
admitted less than or equal to (r t + b).
Policing mechanisms (more)
Token Bucket: can also limit input to specified Peak
Rate p pps. How? Just add a second token bucket,
taking the output of the first token bucket as the
input.
 2nd bucket can hold 1 token
 tokens generated at rate p token/sec unless bucket
full
Policing mechanisms (more)
 token bucket and WFQ combined provide
guaranteed upper bound on delay, i.e., QoS
guarantee !
arriving
traffic
WFQ
Summary: Meeting the principles
 Packet classification

Marking at edge; not done by scheduling/policing.
 Flow isolation


Multiple queues, different priorities, weights
Policing with leaky bucket to limit (average rate, burst length,
peak rate)
 High resource utilization

Work-conserving scheduling
 Call admission


Guaranteed level of quality (WFQ + leaky bucket)
Resource reservation
Chapter 6 outline
 6.1 Multimedia
 6.5 Beyond Best Effort
Networking Applications  6.6 Scheduling and
 6.2 Streaming stored
Policing Mechanisms
audio and video
 6.7 Integrated Services
 RTSP
 6.8 RSVP
 6.3 Real-time,
Interactive Multimedia:  6.9 Differentiated
Internet Phone Case
Services
Study
 6.4 Protocols for RealTime Interactive
Applications


RTP,RTCP
SIP
Remaining schedule
 04/21, Wednesday
IntServ, RSVP
 04/23, Friday
2nd half recap, selected homework solutions, final exam info
 04/26, Monday
Lab, bring your question on project#3
 04/30, Friday
Exam, homework#7 due (posted), project#3 due