Packet Scheduling

 

نوع فایل: PowerPoint

تعداد اسلاید (ها): 46

متن پاورپوینت به زبان انگلیسی است.

 

چکیده ای از متن:

Packet Scheduling & Buffer Management

● Decides when and what packet to send on output link

- Usually implemented at output interface

Why Packet Scheduling?

● Can provide per flow or per aggregate protection

● Can provide absolute and relative differentiation in terms of

- Delay

- Bandwidth

- Loss

Fair Queueing

● In a fluid flow system it reduces to bit-by-bit round robin among flows

- Each flow receives min(ri, f) , where

• ri– flow arrival rate

• f – link fair rate (see next slide)

● Weighted Fair Queueing (WFQ)

– associate a weight with each flow [Demers, Keshav & Shenker ’89] - In a fluid flow system it reduces to bit-by-bit round robin

● WFQ in a fluid flow system  Generalized Processor Sharing (GPS) [Parekh & Gallager ’92] Fair Rate Computation

● If link congested, compute f such that

Fair Rate Computation in GPS

● Associate a weight wi with each flow i

● If link congested, compute f such that

Generalized Processor Sharing

● Red session has packets backlogged between time 0 and 10

● Other sessions have packets continuously backlogged

Generalized Processor Sharing

● A work conserving GPS is defined as

● 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 al flows during [t1, t2)

- B(t) – number of flows backlogged

Properties of GPS

● End-to-end delay bounds for guaranteed service [Parekh and Gallager ‘93]

● Fair allocation of bandwidth for best effort service [Demers et al. ‘89, Parekh and Gallager ‘92]

● Work-conserving for high link utilization Packet vs. Fluid System

● GPS is defined in an idealized fluid flow model

- Multiple queues can be serviced simultaneously

● Real system are packet systems

- One queue is served at any given time

- Packet transmission cannot be preempted

● Goal

- Define packet algorithms approximating the fluid system

- Maintain most of the important properties

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

Table of contents:

Packet Scheduling

Packet Scheduling & Buffer Management

Why Packet Scheduling?

Fair Queueing

Fair Rate Computation

Fair Rate Computation in GPS

Generalized Processor Sharing

Properties of GPS

Packet vs. Fluid System

Packet Approximation of Fluid System

Approximating GPS with WFQ

System Virtual Time

Service Allocation in GPS

The following slides are optional. You may read it yourself.

Virtual Time Implementation of Weighted Fair Queueing

System Virtual Time in GPS

Virtual Start and Finish Times

Goals in Designing Packet Fair Queueing Algorithms

Worst-case Fair Index (WFI)

WFI example

Hierarchical Resource Sharing

Hierarchical-GPS Example

Packet Approximation of H-GPS

Problems with Idea 1

Hierarchical-WFQ Example

Hierarchical-WF2Q Example

WF2Q+

Example Hierarchy

Uncorrelated Cross Traffic

Correlated Cross Traffic

Recap: System Virtual Time

Why Service Curve?

What is a Service Model?

Arrival and Departure Process

Traffic Envelope (Arrival Curve)

Service Curve

Big Picture

Delay and Buffer Bounds

Service Curve-based Earliest Deadline (SCED)

Linear Service Curves: Example

Non-Linear Service Curves: Example

Summary

the end

 

 

منبع:

فروشگاه آنلاين محصولات دانلودی

پشتیبانی خرید: 09337266852