Gebali F. Analysis Of Computer And Communication Networks

Подождите немного. Документ загружается.

460 12 Scheduling Algorithms

12.18.1 System Potential Calculation for FFQ

Assume that the server started serving a packet at time t

. At a later time t ≥ t

,the

system potential P(t) is defined as

P(t) ← P +

C(t −t

)

(12.46)

where C (bps) is the outgoing link capacity and F is the frame size in bits. The

system potential P(t) measures the amount of data transferred up to time t relative

to the frame size F. The system potential is updated each time a packet starts service

and when all sessions are idle, the system potential is reset to zero.

P(t) = 0 when all sessions are idle (12.47)

The frame size F is chosen so that at least the maximum length packet from any

session can be sent during one frame period, i.e.,

F > A

max

bits (12.48)

The frame period T corresponding to the chosen frame size is given by

T =

s (12.49)

12.18.2 Timestamp Calculation for FFQ

When a k packet arrives at session i, a timestamp is associated with it according to

the following formula

(k) = max

[

(k −1), P(t)

]

(12.50)

where S

(k−1) is the timestamp of the previous packet in the queue, A

is the packet

length in bits, and λ

is the reserved rate for session i. An empty queue will have a

zero timestamp associated with it.

A long packet will be penalized by having a large timestamp value and users with

higher reserved bandwidth will consistently receive lower timestamp values so as to

obtain their reserved rate in a fair manner.

One issue remains to be resolved which is determining when the current frame

is to be completed and a new frame is to be started. We mentioned above that a new

frame starts when all sessions are idle. When one or more sessions are backlogged,

a new frame is started when the accumulated bits transferred approaches the frame

12.18 Frame-Based Fair Queuing (FFQ) 461

size F. To keep track of the number of bits transferred, a bit counter could be used.

When a packet is selected for transmission, the counter contents are updated

B(k) = B(k − 1) + A

(12.51)

If B(k) ≤ F, the current frame is continued and the packet is sent. If B(k) > F,

a new frame is started and the packet is sent during the new frame.

12.18.3 Completion Times Calculation for FFQ

The completion time for a packet is simple to calculate in FFQ since the outgoing

resources are completely dedicated to the selected packet.

Assuming packet k in session i has a length A

, then the time T required to

transmit it is

T =

s (12.52)

where C is the outgoing link capacity in bps.

Example 12.8 Assume a FFQ scheduler serving flows of equal weights. The outgo-

ing link capacity is 1 Mbps and the frame size is chosen as F = 10

bits. The packet

arrival pattern is shown below:

t (ms) 0123

Session 1 3 2

Session 2 1 4

Session 3 2 7

Session 4 5

where the numbers in the rows of each session indicate the length of the packet in

units of kb. Calculate the system potential and timestamps for the arriving packets

of each session.

A packet of unit length (1 kb) takes 1 ms to transmit. At the start, system potential

and all the timestamps are reset to 0.

At t = 0, our table will be

t (ms) 0 123

Session 1

∗

3 2

Session 2

0 14

Session 3

∗

(2) 7

Session 4

0 5

B(t)

P(t) 0.0

462 12 Scheduling Algorithms

where the session entries at t = 0aretimestamp values. Sessions 1 and 3 are back-

logged, as indicated by the asterisk (∗), and the timestamp values are

(1) = max(0, 0) +3 = 3

(1) = max(0, 0) +2 = 2

Packet p

(1) will be served first and will require 2 ms to transmit. This is indi-

cated by the brackets a round the entry for this packet.

At t = 1, our table will be

t (ms) 0 1 23

Session 1

∗

Session 2

∗

1 4

Session 3

∗

(2) 7

Session 4

B(t)0

P(t)0.00.1

where the entry for B(t) is in kbits. The timestamp for p

(1) is

(1) = max(0, 0.1) +1 = 1.1

At t = 2, our table will be

t (ms) 0 1 2 3

Session 1

∗

3 2

Session 2

∗

(1) 4

Session 3

∗

2 7

Session 4 5

B(t)01

P(t)0.00.10.2

Packet p

(1) is chosen for transmission since it has the lowest timestamp among

all the backlogged sessions. The timestamps for the new packets are

(2) = max(3, 0.2) +2 = 5

(2) = max(2, 0.2) +7 = 9

At t = 3, our table will be

t (ms) 0 1 2 3

Session 1

∗

(3) 2

Session 2

∗

1 4

Session 3

∗

Session 4

∗

B(t) 0123

P(t) 0.0 0.1 0.2 0.3

12.19 Core-Stateless Fair Queuing (CSFQ) 463

The timestamps for the new packets are

(2) = max(1.1, 0.3) +4 = 5.1

(1) = max(0, 0.3) +5 = 5.3

12.19 Core-Stateless Fair Queuing (CSFQ)

The problem with the schedulers discussed so far is the need to maintain a separate

state for each flow at all routers in the path of the packets. Such schedulers allow the

system to provide firm QoS guarantees for each flow. However, they are complex

to implement and their performance is limited by the number of flows that can be

supported [37].

Core-stateless fair queuing (CSFQ) attempts to simplify matters by dividing the

routers in the network into two categories: edge routers and core routers as shown

in Fig. 12.7 [37].

Edge routers maintain a per-flow state and label incoming packets accordingly.

They also regulate the incoming flows such that flow i receives a fair service rate λ

determined by

= min

[

, f

]

(12.53)

where λ

is the arrival rate for flow i and f is the fair share rate determined in the

following section.

Figure 12.8 shows the functions performed by each edge router. The rate of each

incoming flow is estimated based on the timing of arriving packets. The estimated

arrival rates for all incoming traffic are used to obtain an estimated value for the fair

share f . The edge router also decides whether to accept or drop the arriving packet

based on the arrival rate and the fair share estimate as discussed below. The figure

End-node

Edge switch/

router

Core switch/

router

Network

Fig. 12.7 Routers in core-stateless fair queuing (CSFQ) are divided into edge routers (grey circles)

and core routers (empty circles). End-nodes (squares) are connected to edge routers

464 12 Scheduling Algorithms

Fig. 12.8 The architecture of

an edge router implementing

CSFQ scheduling

Rate estimator

Labeling

Flow 1

...

Rate estimator

Labeling

Flow m

Packet

Dropping

Fair rate

Estimator

FIFO

Buffer Occupancy

Information

shows that the packet drop probability depends on the arrival rate, estimated fair

share, and the state of the FIFO buffer occupancy.

Core routers do not maintain a per-flow state but use the per-flow label in each

packet to decide whether to drop an incoming packet or to accept it. The probability

that a packet is dropped is calculated by each core router based on the packet label

and on the estimated fair rate at the core router. Accepted packets are placed in a

simple FIFO buffer for transmission.

Figure 12.9 shows the functions performed by each core router. The rate of each

incoming flow is extracted from the header of arriving packets. The arrival rates for

all incoming traffic are used to obtain an estimated value for the fair share f .The

core router also decides whether to accept or drop the arriving packet based on the

arrival rate and the fair share estimate as discussed below. The figure shows that

the packet drop probability depends on the arrival rate, estimated fair share, and the

state of the FIFO buffer occupancy.

12.19.1 Determination of Packet Arrival Rate λ

Central to CSFQ is obtaining an accurate estimate of the average packet arrival rate

for each flow. The arrival rate λ

is estimated in an iterative manner each time a new

packet arrives:

(k) =

(

1 −α

)

(k)

+αλ

(k − 1) (12.54)

α = exp −T

(k)/K (12.55)

Fig. 12.9 The architecture of

a core router implementing

CSFQ scheduling

Packet

Dropping

Fair rate

Estimator

FIFO

12.19 Core-Stateless Fair Queuing (CSFQ) 465

where T

(k) is the packet interarrival time for flow i at time k, K is some constant,

and A

(k) is the length of the arriving packet.

A conforming user will have a high value for the interarrival time T

(k). This

will result in an exponentially low value for α which increases the assigned rate

(k).

12.19.2 Determination of Fair Rate f

The fair share f is determined based on whether the link is congested or uncon-

gested. The update operation is performed at regular intervals of time determined

by the system administrator.

The link is congested when the total arrival rate exceeds the outgoing link

capacity C:

C ≤



i=1

min

(

, f

)

linkcongested (12.56)

and in that case, the fair share is set equal to its old value

f (k) = f (k − 1) (12.57)

The link is uncongested when the total arrival rate is smaller than the outgoing

link capacity C:

C >



i=1

min

(

, f

)

linkuncongested (12.58)

and in that case, the fair share is determined as follows

f (k) = f (k −1)

max

(

)

(12.59)

The estimated fair share also is slightly modified based on the level of occu-

pancy of the FIFO buffer but this is a minor detail that the reader could check in

reference [37].

12.19.3 Bit Dropping Probability p

When the traffic rate for flow i is such that λ

< f , then that session is conforming

and no bit dropping is necessary. The packets of that flow can pass through the

network.

466 12 Scheduling Algorithms

A misbehaving session i is characterized by λ

> f and the packet must be

dropped with a bit drop probability given by

= max



0, 1 −



(12.60)

12.20 Random Early Detection (RED)

The schedulers we discussed in the previous sections emphasized techniques for

selecting the next packet for service. Selecting which packet to drop when the buffer

overflows was simple. The last packet to arrive is dropped when the buffer is full.

This type of packet drop is called tail drop strategy. To achieve max–min buffer

sharing, the scheduler must assign a buffer to each service class or each user.

Random early drop detection (RED) belongs to the class of early drop sched-

ulers where a packet is dropped even when the buffer is not full. There are several

plausible reasons why early dropping of packets is beneficial:

1. In tail drop schedulers, misbehaving users occupy precious buffer space and

packets belonging to conforming users would be dropped if they arrive when

the buffer is full.

2. Dropping packets from some sessions or classes sends a message to end points to

reduce their rate before the network becomes congested and more packets would

then be lost.

In random early detection, the switch calculates the average queue size at each

time step. Based on this estimate, the switch decides whether to drop the packet

or label it with a probability that is a function of the queue size [38]. The switch

calculates the average queue size Q

using a low-pass filter. Calculating an average

queue length based on filtering is better than using the instantaneous queue length

since this allows small temporary traffic bursts to go through unharmed.

The average queue size is compared to two thresholds Q

min

and Q

max

1. When Q

< Q

min

, packets are not marked.

2. When Q

> Q

max

, all packets are marked.

3. When Q

min

≤ Q

max

, packets are marked with a probability p

given by

1 − Qp

(12.61)

where Q is the number of packets received since the last marked packet and p

is given by

− Q

min

max

− Q

min

(12.62)

12.21 Packet Drop Options 467

One of the problems of RED is the amount of operations that have to be done at

each time step on each packet. This is one reason why FIFO with tail drop method

is still in use.

Another related algorithm that is similar to RED is flow random early drop

(FRED) where the switch drops each arriving packet with a fixed drop probability

when the queue size exceeds a certain drop threshold. FRED is classified as a

early random drop algorithm where arriving packets are randomly dropped. The

reasoning being that misbehaving users send more packets and will have a higher

probability that their packets are dropped. However, it has been shown that this drop

policy is not very successful [10].

12.21 Packet Drop Options

We discussed above two advantages for dropping packets in a router. Packets are

dropped to reduce network congestion and to improve its efficiency [39]. There are

several options for selecting the next packet to drop and for determining the times

when the drop policies are implemented. Below, we discuss some of the packet

drop policies that could be implemented alone or in combinations, depending on the

transmission and scheduler protocols being used.

The simplest packet drop policy is to drop incoming packets when the shared

buffer or queue is full. This drop policy does not offer protection against misbe-

having users. A full buffer most probably has been caused by a misbehaving user

and the packets dropped might belong to conforming users. Of course, such sim-

ple policy does not require maintaining any state information. There is only one

state to maintain here which is the level of occupancy of the buffer. Attempting to

protect conforming users requires defining state variables for each user indicating

the amount of packets present in the system and belonging to each session. During

periods of congestion, users that have high buffer occupancy states are eligible to

have their packets dropped. While this offers protection against misbehaving users,

the system must maintain many state variables.

An intermediate solution is to group or aggregate the users into classes of ser-

vice and maintain state information for these classes only. This solution offers some

protection and isolation and also reduces the amount of state variables required.

If the scheduler implements PGPS/WFQ or FFQ algorithms, then a simple packet

drop strategy is to drop the packet with the highest finish number or timestamp

value. The reasoning for this is that large values for these parameters indicate either

long packets or many packets belonging to this session.

Sometimes the packet header contains information that can help with the packet

drop policy. For example, in ATM, the AAL layer contains information about miss-

ing cells. When a switch or router detects that a connection has a missing cell, it

drops all subsequent cells until the last cell of the frame [39]. This frees the network

from supporting a cell stream that will be discarded by the receiver since the frame

will be retransmitted anyway.

468 12 Scheduling Algorithms

Problems

Scheduler Functions

12.1 Explain the main functions performed by a scheduler.

12.2 What are the main switch resources shared among the different users?

12.3 What are the scheduler performance measures most important to the follow-

ing applications: electronic mail, file transfer, web browsing, voice commu-

nications, and one-way video.

12.4 Which is the important QoS parameter for best-effort applications and CBR

traffic.

12.5 Explain the functions performed by the scheduler at the different contention

points for input, output, and shared buffer switches.

12.6 One solution to solve the HOL problem in input queued switches is to use

virtual output queuing (VOQ). Explain how VOQ works then explain how

the scheduler will work in such a scheme.

12.7 Explain what is meant by fairness and what is meant by protection from a

scheduler perspective.

12.8 It was explained that to provide deterministic QoS guarantees, the scheduler

must maintain separate queues for the separate sessions. Explain how this

can be done in input, output, and shared buffer switches. Discuss the pros

and cons of each scheme from the point of view of the implementation of the

scheduler in each case.

Scheduler Performance Measures

12.9 Explain what is meant by protection in terms of outgoing link bandwidth

utilization.

12.10 Explain what is meant by protection in terms of switch buffer utilization.

12.11 Investigate how a scheduler might be able to reduce delay jitter for the dif-

ferent sessions.

Scheduler Classifications

12.12 Explain the difference between work-conserving and nonwork-conserving

schedulers.

12.13 Explain what is meant by degree of aggregation and the advantages and dis-

advantages of this strategy.

12.14 Explain the different packet drop policies that could be used by sched-

ulers.

Problems 469

Max–Min Fairness

12.15 Explain max–min fairness as it applies to outgoing link bandwidth.

12.16 Explain max–min fairness as it applies to outgoing shared buffer space in a

switch.

12.17 Assume an outgoing link is being shared among six channels. The system

parameters (in units of Mbps) are as follows:

C = 622

= 200

= 30

= 100

= 50

= 180

Find the rates assigned to each flow according to the max–min algorithm.

12.18 Assume a 1000 byte buffer is being shared among five sessions. The buffer

requirements (in units of bytes) for each session are as follows:

= 250

= 300

= 400

= 150

Find the buffer space assigned to each flow according to the max–min algo-

rithm.

FIFO (or FCFS) Scheduling

12.19 Assume a FIFO scheduler where the output link rate is C and the arrival rate

for each session is λ, the number of arriving sessions is m and all flows have

equal packet lengths L. Find the performance of the system assuming a fluid

flow model.

12.20 Assume a FIFO scheduler where there are m users accessing the buffer but

one of the users has an arrival probability that is different from that of the

other users. Derive the transition matrix for such a system.

12.21 Assume a FIFO scheduler where there are m users accessing the buffer but

one of the users produces packets with different lengths compared to those