Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Probability Read chapter Read first chapter

2015 | OriginalPaper | Chapter

16. Scheduling Algorithms

Author : Fayez Gebali

Published in: Analysis of Computer Networks

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

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 (1) provide required quality of service (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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Modeling Network Traffic
Literature
1.
N. McKeown, T.E. Anderson, A quantitative comparison of iterative scheduling algorithms for input-queued switches. Comput. Netw. ISDN Syst. 30, 2309–2326 (1998)CrossRef
2.
T. Nasser, F. Gebali, A new scheduling technique for packet switching networks using the transportation problem optimization model, in 1st International Symposium on Signal Processing and Information Technology (ISSPIT 2001), pp. 360–363, Cairo, Egypt, Dec 2001
3.
G.B. Dantzig, Linear Programming (Springer, New York, 1985)
4.
S.S. Rao, Engineering Optimization (Princeton University Press, Princeton, 1996)
5.
J.A. cobb, M.G. Gouda, A. El-Nahas, Time-shift scheduling—fair scheduling of flows in high-speed networks. IEEE/ACM Trans. Netw. 6(3), 274–285 (1998)
6.
K. Nichols, S. Blake, F. Baker, D.L. Blake, Definition of the differentiated services field (DS Field) in the IPv4 and IPv6 headers. Dec 1999, IETF RFC 2474
7.
D. Stiliadis, A. Varma, Latency-rate servers: A general model for analysis of traffic scheduling algorithms. IEEE/ACM Trans. Netw. 6(5), 611–624 (1995), p. 41
8.
A.K. Parekh, R.G. Gallager, A generalized processor sharing approach to flow control - the single node case, in Proceedings of IEEE INFOCOM, vol. 2, pp. 915–924, May 1992
9.
A. Demers, S. Keshav, S. Shenker, Analysis and simulation of a fair queuing algorithm, in SIGCOM’89, pp. 3–12
10.
L. Zhang, Virtual clock: A new traffic control algorithm for packet switching networks. ACM Trans. Comput. Syst. 9, 101–124 (1991)CrossRef
11.
M. Datevenis, S. Sidiropoulos, C. Courcoubetis, Weighted round-robin cell multiplexing in a general-purpose ATM switch chip. IEEE J. Sel. Areas Commun. 9, 1265–1279 (1991)CrossRef
12.
D. Ferrari, D. Verma, A scheme for real-time channel establishment in wide-area networks. IEEE J. Sel. Areas Commun. 8, 368–379 (1990)CrossRef
13.
M. Shreedhar, G. Varghese, Efficient fair queuing using deficit round robin, in SIGCOMM’95, Sep 1995
14.
D.C. Verma, H. Zhang, D. Ferrari, Delay jitter control for real-time communication in a packet switching network, in Proceedings of Tricomm’91, pp. 35–43, Chapel Hill, North Carolina, Apr 1991
15.
J. Nagle, On packet switches with infinite storage. IEEE Trans. Commun. 35, 435–438 (1987)CrossRef
16.
C.R. Kalmanek, H. Kanakia, S. Keshav, Rate controlled servers for very high-speed networks, in Conference on Global Communications (GLOBECOM), pp. 12–20, San Diego, CA, USA, Dec 2–5, 1990
17.
S.J. Golestani, A framing strategy for congestion management. IEEE J. Sel. Areas Commun. 9(7), 1064–1077 (1991)CrossRef
18.
S.J. Golestani, Congestion-free transmission of real-time traffic in packet networks, in 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, in Proceedings of the ACM Symposium on Communications Architectures and Protocols (SIGCOMM’90), ACM Press, Philadelpia, PA, USA, vol. 20, pp. 8–18, Sep 24–27, 1990
20.
S.J. Golestani, Duration-limited statistical multiplexing of delay-sensitive traffic in packet networks, in Proceedings of the ACM Symposium on Communications Architectures and Protocols (SIGCOMM’91), ACM Press, pp. 323–332, Zurich, Switzerland, Sep 3–6, 1991
21.
H. Zhang, D. Ferrari, Rate-controlled static-priority queueing”, Conference on Computer Communications (IEEE INFOCOM), San Francisco, CA, USA, pp. 227–236, Mar 28–Apr 1, 1993
22.
M. Aras, J.F. Kurose, D.S. Reeves, H. Schulzrinne, Real-time communication in packet-switched networks. Proc. IEEE 82(1), 122–139 (1994)CrossRef
23.
D. Ferrari, D.C. Verma, Scheme for real-time channel establishment in wide-area networks. IEEE J. Sel. Areas Commun. 8(3), 368–379 (1990)CrossRef
24.
D.C. Verma, H. Zhang, D. Ferrari, Delay jitter control for real-time communications in a packet switching network, in Proceedings of TRICOMM’91, pp. 35–46, Chapel Hill, North Carolina, Apr 1991
25.
D.D. Kandlur, K.G. Shin, D. Ferrari, Real-time communication in multi-hop networks, in 11th International Conference on Distributed Computing Systems (ICDCS), pp. 300–307, Arlington, TX, May 1991
26.
H. Fattah, Frame-based fair queuing: analysis and design. Thesis, Department of Electrical and Computer Engineering, p. 111, University of Victoria, Victoria, B.C., 2000
27.
D. Ferrari, Client requirements for real-time communication services. IEEE Commun. Mag. 28(11), (1990) also RFC 1193
28.
S.J. Glestani, Congestion-free transmission of real-time traffic in packet networks, in ACM SIGCOMM’90, pp. 527–542, June 1990
29.
R. Guerin, V. Peris, Quality of service in packet networks: basic mechanisms and directions, in Proceedings of INFOCOM’97, vol. 31, pp. 169–189, 1999
30.
F. Elguibaly, Analysis and design of arbitration protocols. IEEE Trans. Comput. 38(2), 1168–1175 (1989)
31.
L. Bic, A.C. Shaw, The Logical Design of Operating Systems, pp. 275–280 (1995), Prentice-Hall, New Jersey, USA
32.
J. Crowcroft, J. Oechslin, Differentiated end-to-en internet services using a weighted proportional fair sharing TCP. ACM SIGCOMM 28(3), 53–67 (1998)CrossRef
33.
D. Ferrari, D. Verma, A scheme for real-time channel establishment in wide-area networks. IEEE J. Sel. Areas Commun. 8, 368–379 (1990)CrossRef
34.
S. Floyd, V. Jacobson, Link-sharing and resource management models for packet networks. IEEE/ACM Trans. Netw. 3(4), 365–386 (1995)CrossRef
35.
M. Grossglauser, S. Keshav, D. Tse, RCBR: A simple and efficient service for multiple time-scale traffic, in Proceedings of ACM SIGCOMM’95, 1995CrossRef
36.
D. Stiliadis, A. Varma, Efficient fair queuing algorithms for packet-switched networks. IEEE/ACM Trans. Netw. 6(2), 175–185 (1998)CrossRef
37.
I. Stoica, S. Shenkar, H. Zhang, Core-stateless fair queuing: A scalable architecture to approximate fair bandwidth allocation in high speed networks, in Proceedings of SIGCOMM’98, pp. 118–130
38.
S. Floyd, V. Jackobson, Random early detection for congestion avoidance. IEEE/ACM Trans. Netw. 1, 397–413 (1993)CrossRef
39.
S. Keshav, An Engineering Approach to Computer Networking (Addison Wesley, Reading, MA, 1997)
Metadata
Title
Scheduling Algorithms
Author
Fayez Gebali
Copyright Year
2015
Book
Analysis of Computer Networks

Print ISBN: 978-3-319-15656-9

Electronic ISBN: 978-3-319-15657-6

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-15657-6_16