Scheduling

7/29/97


Click here to start


Table of Contents

Scheduling

Outline

Scheduling

Components

Where?

Outline

Why do we need one?

What can scheduling disciplines do?

Outline

Requirements

Requirements: 1. Ease of implementation

Requirements: 2. Fairness

Fairness (contd.)

Requirements: 3. Performance bounds

Bandwidth

Delay and delay-jitter

Req’ments: 4. Ease of admission control

Outline

Fundamental choices

Choices: 1. Priority

Choices: 2. Work conserving vs. non-work-conserving

Non-work-conserving disciplines

Do we need non-work-conservation?

Choices: 3. Degree of aggregation

Choices: 4. Service within a priority level

Outline

Scheduling best-effort connections

More on GPS

What next?

Weighted round robin

Problems with Weighted Round Robin

Weighted Fair Queueing (WFQ)

WFQ: first cut

A catch

WFQ continued

WFQ: computing the round number

Problem: iterated deletion

WFQ implementation

Analysis

Evaluation

Outline

Scheduling guaranteed-service connections

WFQ

Parekh-Gallager theorem

Significance

Problems

Delay-Earliest Due Date

Rate-controlled scheduling

Examples

Analysis

Decoupling

Evaluation

Summary

Outline

Packet dropping

Classification of drop strategies

1. Degree of aggregation

2. Drop priorities

CLP bit: pros and cons

2. Drop priority (contd.)

3. Early vs. late drop

3. Early vs. late drop: RED

4. Drop position

4. Drop position (contd.)

Author: S. Keshav

Email: skeshav@cs.cornell.edu

Home Page: http://www.cs.cornell.edu/home/skeshav

Download presentation source