Reading list on scheduling algorithms in packet switches.
Classics
-
Abhay K. Parekh and Robert G. Gallager, "A Generalized Processor Sharing
Approach to Flow Control in Integrated Services Networks: The Single Node
Case," IEEE/ACM Transactions on Networking, vol. 1, no. 3, pp. 344--357,
Jun. 1993.
[ pdf ]
[ google search ]
-
Abhay K. Parekh and Robert G. Gallager, "A Generalized Processor Sharing
Approach to Flow Control in Integrated Services Networks: The Multiple
Node Case," IEEE/ACM Transactions on Networking, vol. 2, no. 2, pp.
137--150, Apr. 1994. [ google search ]
-
R. L. Cruz, "SCED+: Efficient management of quality of service guarantees",
Proceedings of INFOCOM'98, 1998.
[ citeseer ]
-
Jon C.R. Bennett and H. Zhang, "Hierarchical Packet Fair Queueing Algorithms".
IEEE/ACM Transactions on Networking, 5(5):675-689, Oct 1997. Also in Proceedings
of SIGCOMM'96, Aug, 1996.
[ citeseer
]
-
D. Stiliadis, "Traffic Scheduling in Packet-Switched Networks: Analysis,
Design, and Implementation," Ph.D. Dissertation, University of California
at Santa Cruz, USA, June 1996.
[ citeseer
]
Implementation and others
-
Ion Stoica, Scott Shenker and Hui Zhang, "Core-Stateless Fair Queueing:
A Scalable Architecture to Approximate Fair Bandwidth Allocations in High
Speed Networks", SIGCOMM'98. [ Overview ]
-
J.C.R. Bennett and H. Zhang, "Why WFQ Is Not Good Enough for Integrated
Services Networks", Proceedings of NOSSDAV'96, Apr, 1996.
[ citeseer ]
-
J.C.R. Bennett and H. Zhang, "WF2Q: Worst-case Fair Weighted Fair Queueing",
INFOCOM'96, Mar, 1996.
[ citeseer ]
-
Ion Stoica, Hui Zhang, T. S. Eugene Ng, "A Hierarchical Fair Service
Curve Algorithm for Link-Sharing, Real-Time and Priority Services",
Proceedings of SIGCOMM 97.
[ citeseer ]
-
P. Goyal and H.M. Vin, "Generalized Guaranteed Rate Scheduling Algorithms:
A Framework", IEEE/ACM Transactions on Networking, Vol. 5, No. 4, pp.
561-571, August 1997.
[ citeseer ]
-
P. Goyal and H.M. Vin., "Fair Airport Scheduling Algorithms", Submitted
for publication to IEEE/ACM Transactions on Networking, August 1998.
[ citeseer ]
-
Pawan Goyal, Harrick M. Vin and Haichen Cheng, "Start-Time Fair Queueing:
A Scheduling Algorithm for Integrated Services Packet Switching Networks,"
IEEE/ACM Transactions on Networking, vol. 5, no. 5, pp. 690-704,
Oct. 1997.
[ citeseer ]
-
Dimitrios Stiliadis and Anujan Varma, "Latency-Rate Servers: A General
Model for Analysis of Traffic Scheduling Algorithms", UCSC-CRL-95-38
July 18, 1995. Also in IEEE/ACM ToN.
[ citeseer ]
-
D. Stiliadis and A. Varma, ``Frame-based Fair Queueing: A New Traffic
Scheduling Algorithm for Packet-Switched Networks,'' Technical Report
UCSC-CRL-95-39, July 1995. A shortened version was published in Proceedings
of ACM SIGMETRICS '96, May 1996.
[ citeseer
]
[ ps.Z ]
-
A. Varma and D. Stiliadis, "Hardware implementation of fair queuing
algorithms for asynchronous transfer mode networks", IEEE Communications
Magazine, 35(12), pp. 54-68, Dec, 1997.
-
D. Stiliadis and A. Varma, "A General Methodology for Designing Efficient
Traffic Scheduling and Shaping Algorithms", Proceedings of IEEE INFOCOM
'97. Extended version in IEEE/ACM Transactions on Networking, October 1998.
[ citeseer
]
[ ToN ps.Z ]
-
Rahul Garg, "Traffic Management in Integrated Services Networks: Scheduling
and Resource Partitioning", PhD Thesis, Department of Computer Science
and Engineering, IIT Delhi, India, July 1999.
[ ps (5Mb) ]
[ ps.gz (860Kb) ]
-
Rahul Garg and Xiaoqiang Chen,
"RRR: Recursive Round Robin Scheduler,",
In the Proceedings of the IEEE Global Telecommunications Conference,
Globecom'98, November 1998. Sydney. Extended version in
Computer Networks 31(18): 1951-1966, (1999).
[ ps ]
[ ps (extended version) ]
-
Rahul Garg and Huzur Saran,
"Scheduling Algorithms for Bounded Delay Service in Virtual
Networks", In Proceedings of IEEE Global Telecommunication
Conference, Globecom'99, Dec. 1999, Rio de Janeiro, Brazil.
[ ps ]
-
S. Suri, G. Varghese, and G. Chandranmenon,
" Leap Forward Virtual Clock: A New Fair Queueing Scheme with
Guaranteed Delays and Throughput fairness",
in Proceeding of IEEE INFOCOM '97.
[ citeseer ]
[ ps.Z ]
-
Jon C.R. Bennett, Donpaul C. Stephens, Hui Zhang, "High Speed, Scalable,
and Accurate Implementation of Fair Queueing Algorithms in ATM Networks",
ICNP'97.
[ citeseer ]
[ ps.gz
]
[ pdf ]
Scheduling algorithms and switch/router design
-
Guest Editorial, "Next-Generation IP switches and Routers", IEEE
JSAC Vol. 17, No. 6, JUNE 1999.
-
S. Keshav, R. Sharma, "Issues and trends in router design," IEEE
communications Magazine, May 1998.
[ pdf ]
-
Shang-Tse Chuang, Ashish Goel, Nick McKeown, and Balaji Prabhakar, "Matching
Output Queueing with a Combined Input Output Queued Switch," IEEE Journal
on Selected Areas in Communications, vol.17, n.6, Dec.1999, pp. 1030-1039.
[ citeseer ]
[ ps ]
-
Balaji Prabhakar and Nick McKeown, "On the Speedup Required for Combined
Input and Output Queued Switching," Automatica, Vol. 35, no. 12, December
1999.
[ citeseer ]
[ ps ]
-
Adisak Mekkittikul, and Nick McKeown, "A Practical Scheduling Algorithm
to Achieve 100% Throughput in Input-Queued Switches," IEEE Infocom
98, Vol 2, pp. 792-799, April 1998, San Francisco.
[ pdf ]
-
Nick McKeown, Venkat Anantharam and Jean Walrand, "Achieving 100% Throughput
in an Input-Queued Switch," Proceedings of IEEE Infocom '96, Vol 1,
pp. 296-302, San Francisco, March 1996.
[ citeseer ]
[ pdf ]
Oldies
-
S. Jamaloddin Golestani, "A Self-Clocked Fair Queueing Scheme for Broadband
Applications," in Proceedings of the Conference on Computer Communications
(IEEE Infocom), (Toronto, Canada), Jun. 1994.
-
Alan Demers, Srinivasan Keshav and Scott Shenker, "Analysis and simulation
of a fair queueing algorithm," in SIGCOMM Symposium on Communications
Architectures and Protocols, (Austin, Texas), pp. 1--12, Sep. 1989.
-
C. R. Kalmanek, H. Kanakia and S. Keshav, "Rate Controlled Servers for
Very High-Speed Networks," Proc. Globecom 1990, December 1990, 300.3.1-300.3.9.
-
Lixia Zhang, "Virtual Clock: A New Traffic Control Algorithm for Packet
Switching Networks," in SIGCOMM Symposium on Communications Architectures
and Protocols, (Philadelphia, Pennsylvania), pp. 19--29, Sep. 1990.
-
H. Zhang, "Service Disciplines For Guaranteed Performance Service in
Packet-Switching Networks'', Proceedings of the IEEE, 83(10), Oct
1995.
[ citeseer ]
[ pdf ]
-
Hui Zhang and Srinivasan Keshav, "Comparison of Rate-Based Service Disciplines,"
in Sigcomm '91 Symposium - Communications Architectures and Protocols,
(Zürich, Switzerland}), pp. 113--121, Sep. 1991.
[ citeseer ]
[ pdf ]
-
Golestani, S.J., "A Framing Strategy for Congestion Management,"
IEEE Journal on Selected Areas in Communications, 9(7), September 1991,
1064--1077.
-
S.J. Golestani, "A Stop-and-Go Queueing Framework for Congestion Management",
Proc. ACM SigComm 1990, September 1990, pp 8-18.
Miscellaneous
-
Shivendra S. Panwar. Thomas K. Philips and Mon-Song Chen, "Golden Ratio
Scheduling for Flow Control with Low Buffer Requirements," IEEE Transactions
on Communications, 40(4), April 1992.
-
Izhak Rubin and Zhensheng Zhang, "Message Delay Analysis for TDMA Schemes
Using Contiguous-Slot Assignments", IEEE Transactions on Communications,
40(4), April 1992.
If you have any comments or suggestions please contact me
at: grahul[at]in.ibm.com