Gebali F. Analysis Of Computer And Communication Networks

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

450 12 Scheduling Algorithms

In processor sharing, all flows had the same weight and all active flows had an

equal share of the outgoing link capacity. In GPS, each session or flow is assigned

a weight that indicates the desired share of the outgoing link capacity. Flow i will

have a weight w

≥ 1, and the share of session i out of the outgoing link bandwidth

C (bps) is given by

(t) = C ×



j∈B(t)

(12.34)

where B(t) is the set of backlogged sessions at time t.

The number of bits transmitted from flow i in a time period t

−t

is given by

= c

(

−t

)

bits (12.35)

where t

≥ t

The time T required to completely transmit a packet of length A

in flow i is

determined from the expression



t=0

(t)dt (12.36)

This time depends on the number of backlogged sessions which could vary.

Example 12.4 Assume a GPS scheduler serving four flows with associated weights

= 1, w

= 2, w

= 3, and w

= 4. The outgoing link capacity is 1 Mbps and

the packet arrival pattern in the different flows is as shown below:

t (ms) 0 10

Session 1 3

Session 2 1

Session 3 2

Session 4 7

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

arrived at that time in units of kb. Calculate the assigned bandwidth and completion

times for the arriving packets.

At t = 0 sessions 1 and 3 are backlogged and their combined weights are 1+3 =

4. The bandwidth assigned to sessions 1 and 3 is

(0) = 10

×1/4 = 0.25 Mbps

(0) = 10

×3/4 = 0.75 Mbps

12.16 Fair Queuing (FQ) 451

Assuming the system is not changed, the completion times for the backlogged

packets are

= 3 ×10

/0.25 = 12 ms

= 2 ×10

/0.75 = 2.67 ms

At t = 10, packet 3 is gone but a small portion of packet 1 is still left.

The number of bits transmitted from packet 1 of session 1 is given from (12.35)

= 0.25 ×10 = 2.5kb

Thus at t = 10 ms, there are 0.5 kb still left to be transmitted for packet p

(1).

The bandwidth assigned to sessions 1, 3, and 4 is

(10) = 10

×1/8 = 0.125 Mbps

(10) = 10

×3/8 = 0.375 Mbps

(10) = 10

×4/8 = 0.5 Mbps

Assuming no more sessions become backlogged, the completion times for the

backlogged packets are

= 0.5 ×10

/0.125 = 4ms

= 10

/0.375 = 2.67 ms

= 7 ×10

/0.5 = 14 ms

12.16 Fair Queuing (FQ)

The fair queuing (FQ) algorithm proposed independently in [9, 15] is completely

equivalent to the virtual clock (VC) algorithm proposed by Zhang [10] in which

the individual sessions are assigned separate queues. The queues are serviced in a

round robin manner which prevents a source from arbitrarily increasing its share of

the bandwidth. It is called “fair” because it allocates an equal share of the output

bandwidth to each traffic flow or queue.

Figure 12.5 schematically shows queue serving sequence in FQ. In the figure, it

was assumed that the incoming flows are divided among m queues. Fair queuing is

used on a per-flow basis. Note, however, that the algorithm works on a packet-by-

packet basis with no consideration to the separate end-to-end connections carried in

each flow.

452 12 Scheduling Algorithms

Fig. 12.5 Fair queuing

scheduling in which each

queue shares an equal portion

of server bandwidth in a

round robin fashion

Session 1

Scheduler

Session 2

Session m

...

Assume flow i has an arrival rate λ

. The bandwidth allocated to flow i is deter-

mined according to max–min scheduling strategy discussed in Section 12.13:



= min

(

, f

)

(12.37)

where f is the fair rate assigned by the algorithm to each flow as follows:

f =

(12.38)

where C is the outgoing link rate and K is the number of backlogged sessions. f

is calculated such that when the switch is congested, the aggregate flow rate equals

the switch capacity C.

Equation (12.37) indicates that f is calculated recursively by removing the user

with the minimal λ

and reducing the link capacity accordingly

C ← C − λ

min

(12.39)

Example 12.5 Assume four sessions are being served by a fair queuing scheduler.

The system parameters (in units of Mbps) are as follows:

C = 20

= 1

= 3

= 8

= 10

Find the rates assigned to each flow.

The sum of the flows due to all backlogged sessions is

1 +3 +8 +10 = 22

12.16 Fair Queuing (FQ) 453

which is larger than the link capacity. The initial fair share f is give by

f = 20/4 = 5

Flow 1 has the minimal rate and is assigned the flow:



= min(1, 5) = 1

We adjust the link capacity shared among the remaining three users as

C = 20 −1 = 19

The fair share becomes

f = 19/3 = 6.33

Flow 2 has minimal rate and is assigned the flow:



= min(3, 56.33) = 3

We adjust the link capacity shared among the remaining two users as

C = 19 −3 = 16

The fair share becomes

f = 16/2 = 8

The bandwidths assigned to the flows become



= 1



= 3



= 8



= 8

The sum of all the assigned rates equals the outgoing link capacity.

Greedy flows that exceed the fair rate will have similar flow rate at the output

equal to the fair rate assigned by the scheduler and will succeed only in filling their

buffer which increases their cell loss probability.

Fair queuing is not completely satisfactory because it does not distinguish among

long versus short queues or high-priority versus low-priority queues. Thus when

bursty traffic is encountered, some queues will become full and their packets will be

lost even if some of the other queues are far from full.

454 12 Scheduling Algorithms

Switches or routers employing FQ have to classify each incoming packet to as-

sign it to the proper queue. Furthermore, the switch or router has to perform some

operations on each queue to determine its instantaneous flow λ

12.17 Packet-by-Packet GPS (PGPS)

Packet-by-packet GPS (PGPS) is a packetized approximation of the GPS algorithms

for fluid flow [34, 35]. This algorithm is also known as weighted fair queuing

(WFQ). Thus in PGPS, data are served in terms of complete packets and only one

packet can be served at a time.

A PGPS/WFQ server works on incoming flows in a static priority fashion based

on a timestamp calculation. The flows or sessions are assigned separate queues

based on packet header information. The scheduler scans the backlogged queues or

sessions to select a packet for service. The packet with the highest priority (least

timestamp) is selected and the output link capacity is dedicated to sending that

packet without sharing the resource with any other queued packets. After a packet

has moved out of a FIFO queue, all packet in that queue move ahead by one position

and the head of the line (HOL) packet enters the pool of selection from among all

other HOL packets belonging to other sessions.

PGPS requires the computation of three quantities:

1. Virtual time, V (t): Indicates the share of the outgoing link capacity for each

backlogged session.

2. Finish number, F

: Determines the priority of serving the packet in flow i.The

packet with the least finish number is the one that will be served by the scheduler.

3. Completion time, T

: Determines the service time required by the packet based

on the packet length and outgoing link bandwidth.

12.17.1 Virtual Time Calculation for PGPS/WFQ

Assuming B(t) to the set of backlogged sessions at time t,thevirtual time V (t)is

defined using the differential equation

V (0) = 0 (12.40)

dV (t)



i∈B

(12.41)

where w

≥ 1 is the weight assigned to session i. Figure 12.6 shows the time devel-

opment of V (t) as packets arrive and sessions become backlogged.

When all sessions are idle, the virtual time is reset to zero

V (t) = 0 when all sessions are idle (12.42)

12.17 Packet-by-Packet GPS (PGPS) 455

Fig. 12.6 Development of the

virtual time V (t)in

PGPS/WFQ scheduling

V(t)

01234

2.0

1.0

3.0

Example 12.6 Assume a PGPS/WFQ scheduler serving flows of equal weights.

The outgoing link capacity is 1 Mbps and all arriving packets equal lengths of 1 kb.

The packet arrival pattern is shown below where it is assumed that packets arrived

at the idle sessions:

t (ms) 0123456

Arrivals 4 1 2

Determine the number of backlogged sessions versus t and obtain the values for

V (t).

A packet will require 1 ms to be transmitted.

At t = 0, four packets arrived and the number of backlogged sessions is

m(0) = 4.

At t = 1, no packets arrive and number of active sessions is reduced by one.

Therefore, m(1) = 3 since one packet is guaranteed to be serviced.

At t = 2, no packets arrive and number of active sessions is decremented by one

m(2) = 2.

At t = 3, one packet arrives and one packet leaves which leaves m(3) =

m(2) = 2.

At t = 4, no packets arrive and number of active sessions is decremented by

one.

At t = 5, no packets arrive and number of active sessions is decremented by one

and we get m(5) = 0.

At t = 6, two packets arrive and m(6) = 2.

The following table shows the development of m(t):

t (ms) 0123456

Arrivals4001002

m(t) 4322102

456 12 Scheduling Algorithms

We use (12.41) to determine the value of V (t) at each time:

t (ms) 0123456

Arrivals4001002

m(t) 4322102

dV (t)/dt 1/4 1/3 1/2 1/2 1/1 0 1/2

V (t) 0.0 0.25 0.58 1.08 1.58 2.58 0

12.17.2 Finish Number Calculation for PGPS/WFQ

Assuming packet k has arrived at the queue for session i, then the finish number for

that packet is calculated as

(k) = max

[

(k −1), V (t)

]

(12.43)

where F

(k − 1) is the finish number for preceding packet in queue i and A

the length of the arriving packet. An empty queue will have a zero finish number

associated with it.

The first term on the RHS ensures that for a backlogged queue, an arriving packet

will have bigger finish number compared to packets already in queue i so that each

queue functions as first-in/first-out (FIFO).

The second term on the RHS ensures that the finish number for packet k of queue

i takes into account the size of that packet and the weight associated with the session.

This ensures that sessions with lots of bits to send are slightly penalized to ensure

fairness to other users that might have smaller packets to send.

Notice that a long packet or a greedy session will be characterized by large finish

numbers and will receive lower service priority. On the other hand, short packets

belonging to a conforming session with short queue will by characterized by small

finish numbers and will be served more frequently. A greedy or bursty user traffic

will only succeed in filling its buffer and losing packets while other users will still

access their fair share of the link capacity.

The scheduler orders all the finish numbers for the packets at the head of all the

queues. The packet with the least finish number is served first.

One last remark is worth making here. The finish number equation (12.43) guar-

antees that packets already in the system at time t will be served before any packets

that arrive after t.

When session i is idle, its finish number is reset to zero

= 0 whensessionisidle (12.44)

12.17 Packet-by-Packet GPS (PGPS) 457

12.17.3 Completion Time Calculation for PGPS/WFQ

The completion time for a packet is simple to calculate in PGPS/WFQ 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 given by

T =

s (12.45)

where C is the outgoing link capacity in bps.

Example 12.7 Assume a PGPS/WFQ scheduler serving four flows of equal weights.

The outgoing link capacity is C = 1 Mbps and 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 virtual time and finish numbers for the arriving

packets of each session.

A packet of unit length (1 kb) takes 1 ms to transmit. At the start, virtual time and

all the finish numbers are reset to 0.

At t = 0, our table will be

t (ms) 0 123

Session 1

∗

3 2

Session 2

Session 3

∗

(2) 7

Session 4

dV /dt

0.5

V (t) 0.0

Sessions 1 and 3 are backlogged, as indicated by the asterisk (

∗

), and the finish

numbers for the arriving packets 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 round the entry for this packet.

458 12 Scheduling Algorithms

At t = 1, our table will be

t (ms) 0 1 23

Session 1

∗

Session 2

∗

1 4

Session 3

∗

(2) 7

Session 4

dV /dt 0.5

0.3

V (t)0.00.5

The finish numbers for all congested sessions (i.e., 1, 2, and 3) are given by

(1) = 2

(1) = max(0, 0.5) +1 = 1.5

(1) = 3

Since F

(1) has the least finish number, we could have chosen the packet in

session 2 for transmission. However, this would mean that we stop the transmis-

sion of packet in session 3 which is not finished yet. This is a form of preemptive

scheduling. We choose a nonpreemptive scheduling scheme and continue transmit-

ting packet out of session 3 as indicated by the brackets surrounding the packet of

session 3.

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

dV /dt 0.5 0.3

0.3

V (t)0.00.50.8

Packet p

(1) is chosen for transmission since it has the lowest finish number

among all the backlogged sessions. The finish numbers for the new packets are

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

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

Since finish number for packet in session 2 is 1.5, we choose this packet for

transmission as indicated by the brackets surrounding that packet.

12.18 Frame-Based Fair Queuing (FFQ) 459

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

∗

dV /dt 0.5 0.3 0.3 0.25

V (t) 0.0 0.5 0.8 1.1

The finish numbers for the new packets are

(2) = max(1.5, 1.1) +4 = 5.5

(1) = max(0, 1.1) +5 = 6.1

Since the finish number for the HOL packet in session 1 is 3, we pick this packet

for transmission.

12.18 Frame-Based Fair Queuing (FFQ)

Frame-based fair queuing (WFQ) belongs to the general class of rate-proportional

servers (RPS) proposed in [36]. This type of schedulers are claimed to offer similar

delay and fairness bounds as PGPS/WFQ but with much simpler computations of

the packet priorities.

FFQ server works on incoming flows in a static priority fashion based on a

timestamp calculation. The flows or sessions are assigned separate queues based on

packet header information. The scheduler scans the backlogged queues or sessions

to select a packet for service. The packet with the highest priority (least timestamp)

is selected and the output link capacity is dedicated to sending that packet without

sharing the resource with any other queued packets. After a packet has moved out

of a FIFO queue, all packets in that queue move ahead by one position and the head

of the line (HOL) packet enters the pool of selection from among all other HOL

packets belonging to other sessions.

FFQ requires the computation of three quantities:

1. System potential, P(t): Indicates the amount of data transferred through the out-

going link up to time t.

2. Timestamp, S

: Determines the priority of serving the packet in flow i. The packet

with the least timestamp is the one that will be served by the scheduler.

3. Completion time, T

: Time required by the packet to be fully transmitted. It de-

pends on the packet length and outgoing link bandwidth.