Gebali F. Analysis Of Computer And Communication Networks
Подождите немного. Документ загружается.
470 12 Scheduling Algorithms
of the other users. Derive an expression for the average length of the queue
and the average queuing delay of such a system.
Static Priority Scheduling
12.22 Consider queue i in the static priority scheduler. Assume the arrival proba-
bility for this queue a
i
and its priority is i, where lower values of i indicate
higher priority. Write down the transition matrix for this queue and comment
on methods to find its steady-state distribution vector.
12.23 Repeat Problem 12.22 for the case when all queues have the same size B and
have the same arrival probability a.
12.24 Consider a static priority protocol serving four users where the packet arrival
probabilities for all users are equal (i.e., a
i
= 0.3 for all 1 ≤ i ≤ 4) and all
users have the same buffer size (i.e., B
i
= 8 for all 1 ≤ i ≤ 4). Estimate the
performance of each user.
12.25 Consider a static priority protocol serving four users where the packet arrival
probabilities for all users are equal (i.e., a
i
= 0.6 for all 1 ≤ i ≤ 4) and all
users have the same buffer size (i.e., B
i
= 4 for all 1 ≤ i ≤ 4). Estimate the
performance of each user.
12.26 Repeat Problem 12.25 when the probability of the queue being empty be-
comes high e = 0.9.
Round Robin Scheduler
12.27 Assume a round robin scheduler in which all packets have equal lengths.
Obtain expressions for the maximum scheduler delay and the fraction of the
bandwidth assigned to any session.
12.28 Assume a round robin scheduler in which all queues have identical traffic
characteristics (arrival probability, packet length, etc.) Obtain the transition
matrix for one queue and obtain expressions for its performance parameters:
queue length, throughput, and loss probability.
12.29 Assume a round robin scheduler in which all sessions are identical with the
following parameters:
m = 8 sessions C = 10 Mbps
B = 8 packets L = 512 bits
λ = 100 kbps σ = 500 kbps
Determine the transition matrix and determine the system performance pa-
rameters.
Problems 471
Generalized Processor Sharing
12.30 Assume a GPS scheduler serving four flows with associated weights w
1
= 4,
w
2
= 2, w
3
= 3, and w
4
= 1. The outgoing link capacity is 10 Mbps and the
packet arrival pattern in the different flows is as shown below:
t (ms) 0 1 2
Session 1 3 2
Session 2 1 3
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 band-
width and completion times for the arriving packets.
12.31 What is the longest delay bound experienced by the packet in session i in
GPS?
Fair Queuing (FQ)
12.32 Assume four sessions are being served by a fair queuing scheduler. The sys-
tem parameters (in units of Mbps) are as follows:
C = 40
λ
1
= 6
λ
2
= 2
λ
3
= 20
λ
4
= 16
Find the rates assigned to each flow.
Packet-by-Packet GPS (PGPS)/Weighted Fair Queuing (WFQ)
12.33 Assume a PGPS/WFQ scheduler serving flows of equal weights. The out-
going link capacity is 1 Mbps and all arriving packets have equal lengths of
1 kb. The packet arrival pattern is shown below:
t (ms) 0123456
Arrivals 2 2 4
Determine the number of backlogged sessions versus t and obtain the values
for V (t).
472 12 Scheduling Algorithms
12.34 Assume a PGPS/WFQ scheduler serving flows of equal weights. The outgo-
ing link capacity is 1 Mbps and the packet arrival pattern is shown below:
t (ms) 0123
Session 1 4 2
Session 2 2 3
Session 3 1 5
Session 4 4
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.
12.35 Assume a PGPS/WFQ scheduler serving flows of equal weights. The outgo-
ing link capacity is 1 Mbps and the packet arrival pattern is shown below:
t (ms) 0123
Session 1 2
Session2321
Session 3 1 2
Session 4 1 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.
12.36 Assume a PGPS/WFQ scheduler serving flows of equal weights. The out-
going link capacity is 2 Mbps and the packet arrival pattern is shown be-
low:
t (ms) 0123
Session 1 7 2
Session 2 3 2
Session 3 3 7
Session 4 8
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.
Frame-Based Fair Queuing (FFQ)
12.37 Assume a FFQ scheduler serving flows of equal weights. The outgoing link
capacity is 1 Mbps and the frame size is chosen as F = 10
4
bits. The packet
arrival pattern is shown below:
References 473
t (ms) 0123
Session 1 1 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.
12.38 Assume a FFQ scheduler serving flows of equal weights. The outgoing link
capacity is 1 Mbps and the frame size is chosen as F = 10
4
bits. The packet
arrival pattern is shown below.
t (ms) 0123
Session 1 2 2
Session 2 1 4
Session 3 1 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.
References
1. N. McKeown and T.E. Anderson, “A quantitative comparison of iterative scheduling al-
gorithms for input-queued switches”, Computer Networks and ISDN Systems, vol. 30,
pp. 2309–2326, 1998.
2. T. Nasser and F. Gebali, “A new scheduling technique for packet switching networks using the
transportation problem optimization model”, 1st International Symposium on Signal Process-
ing and Information Technology (ISSPIT 2001), Cairo, Egypt, December 2001, pp. 360–363.
3. G.B. Dantzig, Linear Programming, Springer-Verlag, New York, 1985.
4. S.S. Rao, Engineering Optimization, Princeton University Press, Princeton, New Jersey,
USA, 1996.
5. J.A. cobb, M.G. Gouda, and A. El-Nahas, Time-shift scheduling—fair scheduling of flows
in high-speed networks. IEEE/ACM Transactions on Networking, vol. 6, no. 3, pp. 274–
285, 1998.
6. K. Nichols, S. Blake, F. Baker, and D.L. Blake, “Definition of the differentiated services field
(DS Field) in the IPv4 and IPv6 headers”, December 1999, IETF RFC 2474.
7. D. Stiliadis and A. Varma, “Latency-rate servers: A general model for analysis of traffic
scheduling algorithms”, IEEE/ACM Transactions on Networking, vol. 6, no. 5, pp. 611–624,
41 pp, 1995.
8. A.K. Parekh and R.G. Gallager, “A generalized processor sharing approach to flow control -
the single node case,” Proceedings of IEEE INFOCOM, vol. 2, pp. 915–924, May 1992.
9. A. Demers, S. Keshav, and S. Shenker, “A generalized processor sharing approach to flow con-
trol in integrated services networks: the multiple node case”, A.K. Parekh, and R.G. Gallager,
Eds., IEEE/ACM Transactions on Networking, Vol. 2, no. 2, pp. 137–150, April 1994.
10. L. Zhang, “Virtual Clock: A new traffic control algorithm for packet switching networks,”
ACM Transactions on Computer Systems, vol. 9, pp. 101–124, May 1991.
474 12 Scheduling Algorithms
11. M. Datevenis, S. Sidiropoulos, and C. Courcoubetis, “Weighted round-robin cell multiplexing
in a general-purpose ATM switch chip”, IEEE Journal on Selected Areas in Communications,
vol. 9, pp. 1265–1279, 1991.
12. D. Ferrari and D. Verma, “A scheme for real-time channel establishment in wide-area net-
works”, IEEE Journal on Selected Areas in Communications, vol. 8, pp. 368–379, 1990.
13. M. Shreedhar and G. Varghese, “Efficient fair queuing using deficit round robin”, SIG-
COMM’95, September 1995.
14. D.C. Verma, H. Zhang, and D. Ferrari, “Delay jitter control for real-time communication
in a packet switching network”, Proceedings of Tricomm’91, pp. 35–43, Chapel Hill, North
Carolina, April 1991.
15. J. Nagle, “On packet switches with infinite storage”, IEEE Transactions on Communications,
vol. 35, pp. 435–438, 1987.
16. C.R. Kalmanek, H. Kanakia, and S. Keshav, “Rate Controlled Servers for Very High-Speed
Networks”, Conference on Global Communications (GLOBECOM), San Diego, California,
USA, pp. 12–20, December 2–5, 1990.
17. S.J. Golestani, “A Framing Strategy for Congestion Management”, IEEE Journal of Selected
Areas in Communications, vol. 9, no. 7, pp. 1064–1077, September 1991.
18. S.J. Golestani, “Congestion-Free Transmission of Real-Time Traffic in Packet Networks”,
Proceedings of IEEE INFOCOM’90, San Francisco, California, USA, pp. 527–536, June
1990.
19. S.J. Golestani, “A Stop-and-Go Queuing Framework for Congestion Management”, Pro-
ceedings of the ACM Symposium on Communications Architectures and Protocols (SIG-
COMM’90), ACM Press, Philadelpia, Pennsylvania, USA, vol. 20, pp. 8–18, September
24–27, 1990.
20. S.J. Golestani, “Duration-Limited Statistical Multiplexing of Delay-Sensitive Traffic in Packet
Networks”, Proceedings of the ACM Symposium on Communications Architectures and Pro-
tocols (SIGCOMM’91), ACM Press, Zurich, Switzerland, pp. 323–332, September 3–6, 1991.
21. H. Zhang and D. Ferrari, “Rate-Controlled Static-Priority Queueing”, Conference on Com-
puter Communications (IEEE INFOCOM), San Francisco, California, USA, pp. 227–236,
March 28–April 1, 1993.
22. M. Aras, J.F. Kurose, D.S. Reeves, and H. Schulzrinne, “Real-time Communication in Packet-
Switched Networks”, Proceedings of the IEEE, vol. 82, no. 1, pp. 122–139, January 1994.
23. D. Ferrari and D.C. Verma, “Scheme for Real-Time Channel Establishment in Wide-Area
Networks”, IEEE Journal on Selected Areas in Communications, vol. 8, no. 3, pp. 368–379,
April 1990.
24. D.C. Verma, H. Zhang, and D. Ferrari, “Delay Jitter Control for Real-Time Communications
in a Packet Switching Network”, Proceedings of TRICOMM’91, pp. 35–46, Chapel Hill, North
Carolina, April 1991.
25. D.D. Kandlur and K.G. Shin and D. Ferrari, “Real-Time Communication in Multi-Hop Net-
works”, 11th International Conference on Distributed Computing Systems (ICDCS), Arling-
ton, TX, pp. 300–307, May 1991.
26. H. Fattah, “Frame-based fair queuing: Analysis and design”, M.A.Sc. Thesis, Department of
Electrical and Computer Engineering, University of Victoria, Victoria, British Columbia, 111
pp., 2000.
27. D. Ferrari, “Client requirements for real-time communication services”, IEEE Communica-
tions Magazine, vol. 28, no. 11, November 1990. also RFC 1193.
28. S.J. Glestani, “Congestion-free transmission of real-time traffic in packet networks”, ACM
SIGCOMM’90, pp. 527–542, June 1990.
29. R. Guerin and V. Peris, “Quality of service in packet networks: Basic mechanisms and direc-
tions”, Proceedings of INFOCOM’97, vol. 31, pp. 169–189, 1999.
30. L. Bic and A.C. Shaw, The Logical Design of Operating Systems, pp. 275–280, 1995.
31. F. Elguibaly, “Analysis and design of arbitration protocols”, IEEE Transactions on Computers,
vol. 38, no. 2, pp. 1168–1175, 1989.
References 475
32. J. Crowcroft and J. Oechslin, “Differentiated end-to-end Internet services using a weighted
proportional fair sharing TCP”, ACM SIGCOMM, vol. 28, no. 3, pp. 53–67, 1998.
33. D. Ferrari and D. Verma, “A scheme for real-time channel establishment in wide-area net-
works”, IEEE Journal on Selected Areas in Communications, vol. 8, pp. 368–379, 1990.
34. S. Floyd and V. Jacobson, “Link-sharing and resource management models for packet net-
works”, IEEE/ACM Transactions on Networking, vol. 3, 1995.
35. M. Grossglauser, S. Keshav, and D. Tse, “RCBR: A simple and efficient service for multiple
time-scale traffic”, Proceedings of ACM SIGCOMM’95, 1995.
36. D. Stiliadis and A. Varma, “Efficient fair queuing algorithms for packet-switched networks”,
IEEE/ACM Transactions on Networking, vol. 6, no. 2, pp. 175–185, 1998.
37. I. Stoica, S. Shenkar, and H. Zhang, “Core-stateless fair queuing: A scalable architecture to
approximate fair bandwidth allocation in high speed networks”, SIGCOMM’98, pp. 118–130.
38. S. Floyd and V. Jackobson, “Random early detection for congestion avoidance”, IEEE/ACM
Transactions on Networking, vol. 1, pp. 397–413, 1993.
39. S. Keshav, An Engineering Approach to Computer Networking, Addison Wesley, Reading,
Massachusetts, 1997.
Chapter 13
Switches and Routers
13.1 Introduction
The three main building blocks of high-performance networks are the links, the
switching equipment connecting the links together, and the software layers (com-
prising protocols and applications) implemented at the switching equipments and
end-nodes. These components enable transferring information between the users of
the network [1]. Figure 13.1 shows the principal network hardware elements which
are end-nodes, links, and switches.
The end-nodes, shown as squares in the figure, are the sources and sinks of
information and users access the network through these end-nodes. Examples of
end-nodes could be a personal computer, a file server, a printer, or a scanner.
The links provide the paths to carry the information streams from one end-node to
another. Examples of links could be the telephone copper wires, TV cable, wireless
transmitters/receivers, optical fiber cables, and satellite links through dish antennas.
As can be expected, different channels offer different service characteristics such as
the available data rate, the bit error rate to be expected, and the propagation delay
encountered in each hop. It is often mentioned that the optical fiber channel is the
most ideal one since it has the highest data rate and least amount of bit error rate.
However, the increasing data rates on these channels lead to increased bit error rate
due to channel imperfection (dispersion and attenuation) and detection problems. If
I am allowed to digress a bit here, I note that the current prevalent way to move data
on a fiber channel is to send optical pulses. This is the same technique that was used
to send data on the telegraph channel (dots and dashes) about 200 years ago at the
time when Custer hastily sheared his hair during the heat of battle, so he would not
be recognized during the battle of Little-Big-Horn!
The links or channels comprising the network need not be identical. For example,
some end-nodes could be connected to the network through TV cables while other
end-nodes could be connected through telephone wires.
Not only need the links of the network in Fig. 13.1 not be identical, but also the
data rates supported by the different links are different. For example, an end-node
might access the network using an old-style modem operating at 56.6 kbps while
another user could be accessing the network using a TV cable connection offering
F. Gebali, Analysis of Computer and Communication Networks,
DOI: 10.1007/978-0-387-74437-7
13,
C
Springer Science+Business Media, LLC 2008
477
478 13 Switches and Routers
Fig. 13.1 The main network
elements are end-nodes
(squares), links, and
switches. The links connect
the end-nodes and switches
together
End-node
Edge switch
/
router
Core switch/
router
Network
a maximum (advertised) data rate of 1 Mbps. Some of the links of that network
might also be optical fiber lines operating at OC-192 rate, which corresponds to
9.9533 Gbps.
The switches connect several incoming and outgoing links together. The function
of the switch is to route the data flows or streams from one incoming link to another
outgoing link. The switch determines the proper outgoing link for each incoming
packet based on the information in its header. We see that such decisions require
quick classification of data which is done electronically at electronic data rates
even when incoming data are optical pulses. Figure 13.1 identifies two types of
switches: edge switches (grey circles) and core switches (empty circles). An edge
switch connects one or more end-nodes to the network. On the other hand, core
switches connect to other core switches.
The software enables error-free transfer of data between the network users. That
software spans many layers of the network. Table 13.1 shows some examples of
networking software components and their location in the TCP/IP and ISO models
of the network.
Table 13.1 Examples of networking software components and their location in the TCP/IP and
ISO models of the network
Software TCP/IP layer OSI layer
E-mail Application layer Layer 7
FTP Application layer Layer 7
SNMP Application layer Layer 7
DNS Application layer Layer 7
Voice over IP Application layer Layer 7
World-Wide Web Application layer Layer 7
TCP Transport layer Layer 4
UDP Transport layer Layer 4
ATM Transport and Internet layer Layers 4 and 3
Frame relay Internet layer Layer 3
IP Internet Layer 3
HDLC Internet layer Layer 3
Ethernet Host-to-network Layer 2
SONET/SDH Physical layer Layer 1
13.3 Media Access Techniques 479
The performance of a communication network is determined by the links, the
routers, and the switches that tie the network together. We will find that message
switching through the network is the fundamental activity done by the different
components of the network. The network performance parameters such as capacity,
bandwidth, and delay, are basically determined by the switches and routers. We start
this chapter by reviewing the concepts of switching networks and identifying their
main components. Different switch design strategies are introduced which include
input queuing, output queuing, and shared buffering. The impact of each design
option on the switch performance is discussed such as packet loss probability, speed,
and ability to support broadcast and hot-spot traffic.
13.2 Networking
Communication networks are used to achieve connectivity between users through
shared communication links. Users could be physically close or they could be at dif-
ferent continents. For any reasonable number of users, it is not possible to establish
one-to-one connection since this has many disadvantages such as cost and the need
to reconfigure the network every time someone joins or leaves the group. Commu-
nication networks aim to achieve the desired connectivity without the disadvantages
of one-to-one connections by using shared communication links. The cost to each
user of the network drops as the network size grows. This is known as the economies
of scale which we are all familiar with from the classic telephone network and in
the dropping prices of computers and related hardware and software products. The
natural downside to sharing is a reduced quality of service (QoS) such as increased
delay to reach the intended user or occasional loss of data. The dropping of price per
user in networks allows for establishing global high-performance networks whose
price would otherwise be beyond the reach of small groups of users. Local-area
networks (LANs) are examples of communication networks where a group of users
is connected at a reasonable cost.
Wide and metropolitan area networks are constructed in a hierarchical fashion
from groups of LANs through the use of switches
1
that connect the different parts
together. The result is called a switched network since switches are used as the
glue that connects the different parts of the network together [2]. In effect, switches
enable users with few links to access a large high-capacity network and be able to
connect to any location in the globe at a very reasonable cost.
13.3 Media Access Techniques
We mentioned earlier that the links in a network could be wire based, point-to-point
wireless, broadcast wireless, or optical. Irrespective of the nature of the medium, the
techniques used for sharing it among several users are similar and we discuss them
1
Most network components such as bridges and routers contain switches in their hardware.
480 13 Switches and Routers
briefly here. Access to the medium is done through a sharing scheme commonly
referred to as media access control (MAC) .
13.3.1 Time Division Multiple Access (TDMA)
In time division multiple access, a single link is shared among many users but each
user has sole access to the link at any given time. This is similar to staying in a
hotel room. The room is shared among many guests but each guest has sole access
to the room at any given time. Figure 13.2 shows two different TDMA schemes
where time is divided into frames and each frame is in turn divided into time slots.
Figure 13.2(a) shows TDMA using fixed assignment where each user has a reserved
time slot in each frame. Figure 13.2(b) shows TDMA using random assignment
where each user has to compete to use any time slot in each frame.
An example of TDMA is the use of a wireless broadcast channel within one
geographical cell of a cellular phone system. In that case, several users in the geo-
graphical cell are allocated a portion of the time to use the channel. Another example
of TDMA is of course the backplane bus in computers where the peripherals access
the shared channel (bus) one at a time using an interrupt mechanism.
13.3.2 Space Division Multiple Access (SDMA)
In space division multiple access (SDMA), several physical links are provided and
the users get access to them through some arbitration protocol, which could be con-
sidered as media access control (MAC) protocol. An example of SDMA is the tele-
phone switching network where separate lines are used to connect the users to the
central office. Another example is in cellular telephones where a certain region or
city is divided into several cells. The users in the different cells can use the network
using the same frequency band since there is no chance of interference. Thus SDMA
refers to the simultaneous use of several communication media in parallel.
Fig. 13.2 Time division
switching: (a)fixed
assignment, (b) random
assignment
Time
Frame n Frame n
+ 1
(a)
Time
35442
Frame n
41254
Frame n + 1
(b)
1
1
2345
2345