Browse Prior Art Database

The Diminishing Weight Scheduling Disclosure Number: IPCOM000013710D
Original Publication Date: 2001-Sep-01
Included in the Prior Art Database: 2003-Jun-18
Document File: 5 page(s) / 91K

Publishing Venue



The Diminishing Weight Scheduling

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 30% of the total text.

Page 1 of 5

The Diminishing Weight Scheduling

The Diminishing Weight Scheduling

Abstract: This invention relates to a class of packet scheduling algorithms for packet switches and routers used in a packet communication network. All the algorithms of this invention have the property that the scheduling weight of a traffic stream is a function of its arrival rate. In particular, the scheduling weights decrease as the arrival rate of the traffic stream increases.

Background of the Invention

Packet scheduling algorithms are being used extensively in packet switches and routers to control the sharing of various link resources [G99, Z95, S96].

One class of scheduling algorithms is based on an idealized (fluid-flow based) scheduler called the Generalized Processor Sharing (GPS) [PG93, PG94]. GPS is defined based on a continuous fluid-like flow of traffic of different streams. The central theme of GPS is:

a) [fairness]: to server traffic from different streams in proportion to the stream scheduling weights, and
b) [work conserving]: to never let the link idle if there are packet backlogged at the link buffer.

Mathematically, if i(t) and j(t) are the respective service rates of streams i and j which are backlogged at time t then, the fairness condition can be represented as:
i(t) / i = j(t) / j, where i and j are the weights of stream i and stream j, and if there is any backlog traffic at the scheduler at time t, then the work conserving condition can be represented as:
i(t) = C,

where C is the link capacity.

In a real switch or router, traffic arrives in the form of discrete packets, which is not a continuous fluid-like flow. The packet scheduling algorithms that are derived from GPS try to emulate GPS as close as possible in a packetized form [PG93, Z95, BZ97, SV95, Z90]. Different implementations have different implementation complexity and approximate GPS to different degrees [S96, VS97, ZK91, BSZ97].

Most of the packetized implementation of GPS are based on the concept of virtual time [Z95, S96, VS97, ZK91]. The system maintains a virtual time, which signifies the time that would have elapsed if the system was to serve the traffic streams at a rate that is exactly equal to the rate allocated to the stream. The weight allocated to stream i is given by wi = C i / (j).

Upon a packet arrival, the scheduler assigns a virtual finish time to the packet as follows:


Page 2 of 5

Fik = Max [ v(aik), Fik-1 ] + Lik / wi

where Fik represents the virtual finish time of the kth packet of ith stream, aik represents the real arrival time of the kth packet of the ith stream, Lik is the length of the kth packet of ith stream, wi is the rate allocated to the ith stream and v(t) is the virtual time at time t.

In most of the implementations, packets are sent to the output link in the increasing order of their virtual finish times.

The calculation of v(t) is complex and requires GPS emulation in general, which is time consuming. There are several approximations that redu...