Gebali F. Analysis Of Computer And Communication Networks

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

References 429

10. H. Saito, Teletraffic Technologies in ATM Networks, Artech House, Boston, 1994.

11. G.E.P. Box and G.M. Jenkins, Time Series Analysis: Forecasting and Control, Prentice-Hall,

New Jersey, 1976.

12. V.S. Frost and B. Melamed, “Traffic modeling for telecommunications networks”, IEEE Com-

munications Magazine, vol. 32, March 1994.

13. M.R. Schroeder, Number Theory in Science and Communications, Springer-Verlag, New York,

1986.

14. L.M. Sander, “Fractal growth”, Scientific American, vol. 256, pp. 94–100, 1987.

15. T. Hettmansperger and M. Keenan,“Tailweight, statistical interference and families of distri-

butions - A brief survey” in Statistical Distributions in Scientific Work,vol.1,G.P.Patilet.al.

ed., Kluwer, Boston, 1980.

16. F.A. Tobagi, T. Kwok, and F.M. Chiussi, “Architecture, performance, and implementation of

the tandem-banyan fast packet switch”, Proceedings of the IEEE, vol. 78, pp. 133–166, 1990.

17. V.J. Friesen and J.W. Wong, “The effect of multiplexing, switching and other factors

on the performance of broadband networks”, Proceedings of the IEEE INFOCOM’93,

pp. 1194–1203, 1993.

18. G.F. Pfister and V.A. Norton, “Hot-spot contention and combining in multistage interconnec-

tion networks”, IEEE Transactions Computers, vol. 34, pp. 943–948, 1993.

19. M. Guizani and A. Rayes, Designing ATM Switching Networks, McGraw-Hill, New York,

1999.

20. A. Erramilli, G. Gordon, and W. Willinger, “Applications of fractals in engineering for realistic

traffic processes”, International Teletraffic Conference, 14:35–44, 1994.

21. W. Stallings, Data and Computer Communications, Fifth edition, Prentice Hall, New Jersey,

1998.

22. N. Likhanov, B. Tsybakov, and N.D. Georganas, “Analysis of an ATM buffer with self-similar

(“fractal”) input traffic”, INFOCOM, vol. 3, pp. 8b.2.1–8b.2.7, 1995.

23. I. Norros, “A storage model with self-similar input”, Queuing Systems, vol. 16, 1994.

24. J. Gordon, “Pareto process as a model of self-similar packet traffic”, IEEE Global Telecom-

munications Conference (Globecom 95), Singapore, 14 November, pp. 2232–2235, 1995.

25. F. Gebali, A queuing model for self-similar traffic, The 1st IEEE International Symposium on

Signal Processing and Information Technology, December 28–30, 2001, Cairo, Egypt.

26. L. Kleinrock, Queuing Systems, volume I, John Wiley, New York, 1975.

27. P. Sen, B. Maglaris, N.-E. Rikli, and D. Anastassiou, “Models for packet switching of

variable-bit-rate video sources”, IEEE Journal on Selected Areas in Communications,vol.7,

pp. 865–869, 1989.

28. B. Maglaris, D. Anastassiou, P. Sen, G. Karlsson, and J. Robbins, “Performance models of

statistical multiplexing in packet video communications”, IEEE Transactions on Communica-

tions, vol. 36, pp. 834–844, 1988.

29. P. Sen, B. Maglaris, N. Rikli, D. Anastassiou, “Models for packet switching of variable-bit-rate

video sources”, IEEE Journal on Selected Areas in Communications, vol. 7, pp. 865–869,

1989.

30. M. Nomura, T. Fujii, and N. Ohta, “Basic characteristics of variable rate video coding in ATM

environment”, IEEE Journal on Selected Areas in Communications, vol. 7, pp. 752–760, 1989.

31. R. Grunenfelder, J.P. Cosmos, S. Manthorpe, and A. Odinma-Okafor, “Characterization of

video codecs as autoregressive moving average process and related queuing system perfor-

mance”, IEEE Journal on Selected Areas in Communications, vol. 9, pp. 284–293, 1991.

32. P. Sen, “Models for packet switching of variable-bit-rate video sources”, IEEE Journal on

Selected Areas in Communications, vol. 7, pp. 865–869, 1989.

33. H.E. Jurst, “Long-term storage capacity of reservoirs”, Transactions of the American Society

of Civil Engineers, vol. 116, pp. 770–799, 1951.

34. B.B. Mandelbrot and J.W. van Ness, “Fractional Brownian motions, fractional noises and

applications”,

SIAM Review, vol. 10, pp. 422–437, 1968.

35. R.Y. Awdeh and H.T. Muftah, “Survey of ATM switch architectures”, Computer Networks and

ISDN Systems, vol. 27, pp. 1567–1613, 1995.

Chapter 12

Scheduling Algorithms

12.1 Introduction

A scheduling algorithm must be implemented at each network router or switch

to enable the sharing of the switch-limited resources among the packets traveling

through it. The resources being shared include available link bandwidth and buffer

space. The main functions of a scheduler in the network are to (1) provide required

QoS for the different users, by making proper choices for selecting next packet for

forwarding to the next node; (2) select next packet for dropping during periods of

congestion when the switch buffer space is starting to get full; and (3) provide fair

sharing of network resources among the different users.

12.1.1 Packet Selection Policy

In a typical switch or router, several packets will request to access a certain output

port. Because only one packet can leave, the rest must be stored in an intermediate

buffer. Somehow we must find a way to decide which stored packet must be sent

next. Different selection policies could be implemented for different types of queues

depending on the service classes of the queues. For example, some applications have

rigid real-time constraints on delay and jitter, while other adaptive applications agree

to modify their behavior based on the network status. At the time of writing, most

Internet applications are handled using best-effort packet transfer policy with no

bandwidth or delay guarantees [1].

12.1.2 Packet Dropping Policy

The fact that packets have to be stored in each switching node of the network implies

that buffer storage in a switch is a resource that must be shared among the different

users or sessions. During periods of congestion, the switch buffers become full and

the scheduler must also decide which packets to drop.

F. Gebali, Analysis of Computer and Communication Networks,

DOI: 10.1007/978-0-387-74437-7

12,



Springer Science+Business Media, LLC 2008

431

432 12 Scheduling Algorithms

12.1.3 Fair Sharing Policy

The switch resources such as available output link bandwidth and local buffer space

must be shared among the switch users. Because of the different classes of service

supported by the switch, an equal sharing of the resources is not the best option.

Rather, the scheduler must allocate these finite resources in a fair manner so that

each user can get its share based on its class of service. Another issue related to fair

sharing is isolation or protection. This is required because not all users abide by their

agreed-upon data rate. When this happens, the misbehaving (nonconforming) user

starts to hog the resources at the expense of other well-behaving (conforming) users.

It is obvious from the previous discussion that data scheduling is required at each

node in the network for three reasons: (a) selection of a packet for transmission from

the population of queued packets destined to a certain switch output; (b) provide

QoS for the different types of flows going through the switch; and (c) drop packets

when the buffer space becomes full.

12.2 Scheduling as an Optimization Problem

From the above discussion, it is clear that the scheduling problem is an optimiza-

tion problem since the scheduler distributes the system-limited resources among

the user traffic which impacts the offered quality of service (QoS). The schedul-

ing algorithms to be discussed in the following sections are all heuristic and have

no solid proof that the proposed scheduling policy is optimal in any mathemati-

cal sense. Further, we will note that the scheduler discussed here reduces packet

delay by allocating large bandwidth to the delay-sensitive traffic. This might be

self-contradictory for some types of traffic, which is delay sensitive but does not

require high bandwidth.

The author developed a hierarchical scheduler [2] that is based on the transporta-

tion problem optimization technique [3, 4]. The transportation problem technique

allows optimizing different QoS types such as delay-sensitive traffic and bandwidth-

sensitive traffic through the same switch.

Finding the optimum solution to a transportation problem is not simple and might

consume a certain amount of time. However, the author developed a simple greedy

algorithm for solving the transportation problem based on computational geometric

concepts. The algorithm uses only simple add/subtract operations and hence should

be fast to compute [2].

12.3 Scheduler Location in Switches

The scheduler will be located in the switch where packets are buffered and where

packets must share a resource like the switch fabric or the output links.

12.3 Scheduler Location in Switches 433

Fig. 12.1 Virtual output

queuing (VOQ) and output

queuing switches with

different queues for each

service class. The points at

which packet contention

occurs are shown

Multiple input queuing/

Virtual output queuing

Input

Queues

...

Multiple output queuing

...

Output

Queues

When a switch is capable of supporting different QoS classes, each service class

will have its own dedicated buffer. At the extreme, each session or user channel

will have its own dedicated buffer in each switch it encounters. Figure 12.1 shows

two buffer location options in switches. The rectangles labeled “SF” indicated the

switching fabric of the switch whose function is to provide connectivity between

each input port and each output port. The figure on the top shows an input queuing

switch where the buffers are located at each input port. The figure on the bottom

shows an output queuing switch where the buffers are located at each output port.

Multiple buffers are shown at each input or output port when multiple service classes

are supported.

Irrespective of the buffering strategy employed, packets will contend for the

shared resources and some form of scheduling algorithm will be required. The figure

shows that there are three types of shared resources: (1) the buffer storage space; (2)

the switch fabric (SF); and (3) the output links (i.e., available bandwidth)

For the input queuing switch, top sketch in Fig. 12.1, we can get two potential

contention points. Point 1 is a potential contention point where all the packets from

the different queues at an input port compete to access the switch fabric. Of course,

a remedy for this problem would be to modify the switch fabric to allow more than

one packet to access the fabric simultaneously. At point 1, the scheduler must also

determine which packets to drop when the buffers start being full. Point 2 is another

potential contention point where packets from the different inputs compete to access

a certain output port. At this point, usually the output link is only able to transmit

434 12 Scheduling Algorithms

one packet only except when the output link is composed of multiple channels such

as in wavelength division multiplexing (WDM).

For output queuing switch also, bottom sketch in Fig. 12.1, we can get two con-

tention points. Point 1 is a potential contention point where all the packets from

the different inputs compete to access the queues of a certain output port. Point

2 is another potential contention point where packets from the different queues in

each output compete to access the output link. At point 2 the scheduler must also

determine which packets to drop when the buffers start being full.

12.4 Scheduling and Medium Access Control

From the discussion in the previous section, we can tell that a scheduling algorithm

is a method to allow many users or traffic flows to access the output link. In that

sense, the problem is to access the shared resource. Chapters 10, 13, and 14 discuss

media access control techniques and architectures which allow packets to access

a shared resource such as the communication channel. A question naturally arises

whether schedulers and MAC protocols are one and the same. The quick answer is

that they are similar but not the same thing. Table 12.1 compares scheduler algo-

rithms and media access control (MAC) techniques.

12.5 Scheduler Design Issues

There are several design issues related to schedulers. These issues are reviewed in

the following subsections. In the discussion to follow we shall use the terms “user”,

“session”, “connection”, or “flow” to describe the traffic carried by the switch.

Table 12.1 Comparison between scheduling algorithms and media access control (MAC)

techniques

Scheduling algorithms MAC techniques

Designed to provide QoS guarantees Designed to provide resource access only

Determine the user’s share of bandwidth,

buffer space allocation, and packet

discard decisions

Does not deal with these issues

Shared resource is outgoing link of a

switch/router and buffer space

Shared resource is a bus, a wireless

channel, or a shared memory

Operate at switch or router output ports Operate at output ports or each device

connected to the medium

Used with switches or routers Used with buses, wireless channels, etc

Physically exists inside a switch or router Distributed among all users and MAC

controllers

Implemented in software (at least for

now)

Implemented in software and hardware

Operate at layers above the physical layer Operate at the physical layer

12.5 Scheduler Design Issues 435

12.5.1 Priority

Ideality dictates that equality is a good thing. However, real life tells us that special

people are “more equal”! Alas, equality is not a good thing in computers or net-

works. The scheduler is only able to do a decision to select a certain user only when

this user has higher priority compared to all other users. Priority assignment could

be static or dynamic. A static priority assignment implies that users belonging to a

certain class of service have a certain level of priority that does not change with time

or with the traffic load. On the other hand, dynamic priority allocation changes the

priority of a certain class of service with time or based on the traffic volume.

In addition to priority assignment, there is an arbitration rule that is invoked to

resolve the conflicts between users with the same priority.

12.5.2 Degree of Aggregation

In order to provide guaranteed QoS, the scheduler has to keep state information

about the performance of each user or connection. The problems with such sched-

ulers are limitations on scaling, deployment difficulties, and the requirement of map-

ping between application and network service parameters [5]. The large number of

states that must be maintained and references slow down the scheduler and limit

the number of users that can be accepted. Other schedulers aggregate several con-

nections into classes to reduce the amount of state information and workload. This

approach is more promising since it deals with large aggregates of network traffic

and its per-hop behavior is configurable [6]. The differentiated services scheduler

provides constant ratios of the quality of service ratios between the service classes

even when the quality level is varying. The price to be paid by aggregating traffic is

loss of deterministic QoS guarantees since the state of each connection is lost. QoS

guarantees for a high-level aggregation server are provided on a probabilistic basis.

In other words, the scheduler loses specific information about the status of each user

since it only keeps track of groups of users. This reduces the number of states that

must be checked and updated. Guarantees can be provided on the QoS for groups of

users, but each user cannot be guaranteed specific level of service.

12.5.3 Work-Conserving Versus Nonwork-conserving

A work-conserving algorithm is idle when all of the priority queues are empty. A

nonwork-conserving algorithm might not transmit a packet even when the priority

queues are occupied. This might happen to reduce the delay jitter for example [7].

This is nice in theory but is not implemented in practice. In general, it was found that

work-conserving algorithms provide lower average delay than nonwork-conserving

algorithm.

436 12 Scheduling Algorithms

Examples of work-conserving algorithms include generalized processor sharing

[8], weighted fair queuing [9], virtual clock [10], weighted round robin [11], delay-

earliest-due date (Delay-EDD) [12], and deficit round robin [13].

Examples of nonwork-conserving algorithms are stop-and-go, jitter earliest-due

date (jitter-EDD) [14], and rate-controlled static priorities (RCSP).

12.5.4 Packet Drop Policy

Schedulers not only select which packet to serve next, but also have to select which

packet to drop when the system resources become overloaded. There are several

options for dropping packets such as dropping packets that arrive after the buffer

reaches a certain level of occupancy (this is known as tail dropping). Another option

is to drop packets from any place in the buffer depending on their priority. As we

shall see later, a third approach is to randomly select packets for dropping once the

system resources become congested.

12.6 Rate-Based Versus Credit-Based Scheduling

Scheduling methods could be classified broadly as rate-based or time-based. A

rate-based scheduler selects packets based on the data rate allocated for the service

class. Rate-based scheduling methods include fair queuing (FQ) [9, 15], which is

equivalent to virtual clock (VC) [10] weighted fair queuing (WFQ) [9], hierarchi-

cal round robin (HRR) [16], deficit round robin (DRR) [13], stop-and-go (S&G)

[17, 18, 19, 20], and rate-controlled static priority (RCSP) [21]. Rate-based meth-

ods allow a variety of techniques for arriving at a service policy [22]. Some of the

methods are fairly complex to implement since they require complex mathematical

operations and require knowledge of the states of the different flows. However, they

can only provide guarantees based on the maximum delay or delay jitter bounds

since they translate these requirements into an equivalent bandwidth. This proves to

be the weak point on these algorithms since providing bandwidth guarantees to ef-

fect delay guarantees ignores the actual bandwidth requirements of the actual traffic

stream. Needless to say, this would lead to unfair bandwidth allocation to the other

services that have real QoS bandwidth requirements.

A time-based scheduler selects packets based on their time of arrival. Time-based

methods include earliest-due date for delay (EDD-D) [23], earliest-due date for jitter

(EDD-J) [24], and smallest response time (SRT) [25]. Scheduler-based methods

require keeping track of the arrival times of the different packets and calculate the

packet priority based on the packet arrival time and the deadline imposed on it. To

provide end-to-end guarantees on the delay and delay jitter, the scheduler must be

implemented at all the switching nodes and the incoming traffic must conform very

closely with the assumed model [22].

12.9 First-In/First-Out (FIFO) 437

12.7 Scheduler Performance Measures

A good scheduling algorithm must satisfy several of the following performance

measures [26]:

QoS: The scheduler must be able to support different types of QoS classes with

varying requirements such as bandwidth (throughput), delay, delay jitter, and

loss probability [27].

Fairness: The main goal of fairness is to serve sessions in proportion to some

specified value [28]. The simplest fair allocation of resources is to equally

divide the available bandwidth and buffer space among all the users and to

drop excess packets equally from the different queues. However, if a user

does not require all of its allocated share, then the excess share should be

divided equally among the other users.

Isolation or protection: Isolation means that a misbehaving user should not

adversely impact other users. The user becomes misbehaving when its packet

arrival rate exceeds what is expected. Isolating the effects of misbehaving

users is equivalent to protecting conforming users.

Simplicity: The scheduler must be easy to implement in hardware especially

at high network speeds. This requires that computations to be done by the

scheduler to be small in number and simple to calculate.

Scaling: The scheduler must perform well even when the number of sessions

increases or when the link speed is increased. Some scheduling algorithm

must keep state information about every user and must update this infor-

mation very frequently. This places limitations on how many users can be

supported by the scheduler and places limitations on the scheduler delay.

12.8 Analysis of Common Scheduling Algorithms

The remainder of this chapter discusses several scheduling algorithms that vary in

performance from support of best-effort traffic with no performance guarantees to

schedulers that support guaranteed services with bounds on bandwidth and delay.

Models that describe the performance of each algorithm are also developed.

12.9 First-In/First-Out (FIFO)

First-in/first-out (FIFO) is also known as first-come/first-served (FCFS). The FIFO

method sorts users according to their arrival time. The users that arrive early are

served first [29]. In that sense, all users have the same priority and the arbitration

rule is based on the time of arrival of the packets. This method is used naturally to

store incoming packets in queues that could be associated with the input or output

ports.

438 12 Scheduling Algorithms

FIFO is simple to implement and packet insertion and deletion are particularly

simple and do not require any state to be maintained for each session. However, this

proves to be a disadvantage since the server has no way of distinguishing between

the packets belonging to different users. Thus some users might be misbehaving and

fill a large portion of the queue which increases the chance of dropping the packets

of other users.

When all incoming flows are queued in a single queue, greedy users exhibiting

long periods of activity (bursty behavior) will take the lion’s share of the queue

capacity at the expense of other flows. When the queue is filled, packets at the tail

are dropped. This is the reason why this method is known as FIFO with tail drop.

Most routers adopt this method because of its simplicity.

FIFO does not provide per-connection delay or rate guarantees since priority is

based solely on arrival time. One way to provide delay bounds is to limit the size

of the queue so that the maximum delay equals the time to serve a full queue. Of

course, once the queue size is limited, there will be a probability that an arriving

packet will be discarded if it arrives when the queue is full. To reduce the packet

discard probability, the number of sessions should be limited.

12.9.1 Queuing Analysis of FIFO/FCFS

Let us perform a simple queuing analysis for a FIFO buffer. We make the following

simplifying assumptions:

1. The size of the buffer is B.

2. The maximum number of customers that could arrive at the input of the buffer at

a certain time step is m.

3. The average length of packets from any user is A.

4. The arrival probability for any user is a.

5. The departure probability for the buffer is c.

Figure 12.2 shows the FIFO buffer where several sessions converge at the input

and only one packet can leave which corresponds to an M

/M/1/B queue. The

transition matrix for such queue was derived in Section 7.7 on page 241. Based on

that, we can derive expressions for the scheduling delay which corresponds to the

queuing delay in that situation.

Fig. 12.2 AFIFObufferwith

m flows at its input

Session 1

FIFO

Session 2

Session m

...

12.11 Round Robin Scheduler (RR) 439

The throughput of the FCFS queue was given in Section 7.7, which we repeat

here for convenience.

The average throughput is estimated as

Th = c

(

1 −a

)

(12.1)

where a

is the probability that no packets arrive during a time step and s

is the

probability that the queue is empty.

The average lost traffic Na(lost) is given by

Na(lost) = Na(in) − N a(out)

= Na(in) −Th

= ma−c

(

1 −a

)

(12.2)

We refer the reader to Sections 7.7.1 and 7.7.2 for a more detailed discussion of

the performance figures for the M

/M/1/B queue.

12.10 Static Priority (SP) Scheduler

In a static priority scheduler, separate queues are assigned different priorities. In-

coming data are routed to the different queues depending on their priority. The

scheduler serves packets in a lower priority queue only if all the higher priority

queues are empty [30, 31, 29, 32, 33].

The static priority scheduler is also known as the IEEE 802.1p, which was dis-

cussed in Chapter 10. A queuing analysis of the static priority scheduler was per-

formed in Section 10.2 on page 326.

12.11 Round Robin Scheduler (RR)

The round robin scheduler serves backlogged sessions one after another in a fixed

order. When the scheduler finishes transmitting a packet from session 1, say, it

moves on to session 2 and checks if there are any packets waiting for transmission.

After the scheduler has finished going through all sessions, it comes back to the first

session, hence the name round robin. Figure 12.3 shows a round robin scheduler

serving four sessions.

The main features of this scheduler are ease of implementation in hardware and

protection of all sessions even best-effort sessions. A greedy or misbehaving user

will not be able to transmit more than one packet per round. Hence all other users

will not be penalized. The misbehaving user will only succeed in filling its own

buffer and data will start getting lost. However, the long packets will be transmitted

since the scheduler serves whole packets. This could affect the delay experienced

by other sessions that might have short packets to transmit.