loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Fundamental Trade-Offs in Aggregate Packet Scheduling
December 2005 (vol. 16 no. 12)
pp. 1166-1177
ASCII Text
x 
 
Zhenhai Duan, Zhi-Li Zhang, Yiwei Thomas Hou, "Fundamental Trade-Offs in Aggregate Packet Scheduling," IEEE Transactions on Parallel and Distributed Systems, vol. 16, no. 12, pp. 1166-1177, December, 2005.
 
 
BibTex
x
 
@article{ 10.1109/TPDS.2005.149,
author = {Zhenhai Duan and Zhi-Li Zhang and Yiwei Thomas Hou},
title = {Fundamental Trade-Offs in Aggregate Packet Scheduling},
journal ={IEEE Transactions on Parallel and Distributed Systems},
volume = {16},
number = {12},
issn = {1045-9219},
year = {2005},
pages = {1166-1177},
doi = {http://doi.ieeecomputersociety.org/10.1109/TPDS.2005.149},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - JOUR
JO - IEEE Transactions on Parallel and Distributed Systems
TI - Fundamental Trade-Offs in Aggregate Packet Scheduling
IS - 12
SN - 1045-9219
SP1166
EP1177
EPD - 1166-1177
A1 - Zhenhai Duan,
A1 - Zhi-Li Zhang,
A1 - Yiwei Thomas Hou,
PY - 2005
KW - Packet scheduling algorithms
KW - aggregate packet scheduling algorithms
KW - quality of services (QoS)
KW - performance analysis.
VL - 16
JA - IEEE Transactions on Parallel and Distributed Systems
ER -
 

Abstract—In this paper, we investigate the fundamental trade-offs in aggregate packet scheduling for support of guaranteed delay service. In our study, we consider two classes of aggregate packet scheduling algorithms: the static earliest time first (SETF) and dynamic earliest time first (DETF). Through these two classes of aggregate packet scheduling (and together with the simple FIFO packet scheduling algorithm), we show that, with additional timestamp information encoded in the packet header for scheduling purposes, we can significantly increase the maximum allowable network utilization level, while, at the same time, reducing the worst-case edge-to-edge delay bound. Furthermore, we demonstrate how the number of the bits used to encode the timestamp information affects the trade-off between the maximum allowable network utilization level and the worst-case edge-to-edge delay bound. In addition, the more complex DETF algorithms have far superior performance than the simpler SETF algorithms. These results illustrate the fundamental trade-offs in aggregate packet scheduling algorithms and shed light on their provisioning power in support of guaranteed delay service.

[1] J. Bennett, K. Benson, A. Charny, W. Courtney, and J.-Y. Le Boudec, “Delay Jitter Bounds and Packet Scale Rate Guarantee for Expedited Forwarding,” Proc. IEEE INFOCOM, Apr. 2001.[2] S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang, and W. Weiss, “An Architecture for Differentiated Services,” RFC 2475, Dec. 1998.[3] T. Bonald, A. Proutiere, and J. Roberts, “Statistical Guarantees for Streaming Flows Using Expedited Forwarding,” Proc. IEEE INFOCOM, Apr. 2001.[4] J.-Y. Le Boudec and P. Thiran, Network Calculus. Springer-Verlag, http:/lcawww.epfl.ch, July 2001.[5] C.-S. Chang, A Filtering Theory for Communication Networks. Springer-Verlag, 1999.[6] A. Charny and J.-Y. Le Boudec, “Delay Bounds in a Network with Aggregate Scheduling,” Proc. Workshop Quality of Future Internet Services, Oct. 2000.[7] R. Cruz, “A Calculus for Network Delay, Part I: Network Elements in Isolation,” IEEE Trans. Information Theory, vol. 37, no. 1, pp. 114-131, Jan. 1991.[8] V. Jacobson, K. Nichols, and K. Poduri, “An Expedited Forwarding PHB,” RFC 2598, June 1999.[9] V. Jacobson, K. Nichols, and K. Poduri, “The ‘Virtual Wire’ Per-Domain Behavior,” Internet Draft, July 2000.[10] S. Keshav, An Engineering Approach to Computer Networking. Addison-Wesley, 1997.[11] J. Liebeherr and D.E. Wrege, “A Versatile Packet Multiplexer for Quality-of-Service Networks,” Proc. Fourth Int'l Symp. High Performance Distributed Computing (HPDC-4), pp. 148-155, Aug. 1995.[12] I. Stoica and H. Zhang, “Providing Guaranteed Services without Per Flow Management,” Proc. ACM SIGCOMM, Sept. 1999.[13] Z.-L. Zhang, Z. Duan, and Y.T. Hou, “Fundamental Trade-Offs in Aggregate Packet Scheduling,” technical report, Computer Science Dept., Univ. of Minnesota, http://www.cs.umn.edu/~zhzhangpapers.html , Feb. 2001.

Index Terms:
Packet scheduling algorithms, aggregate packet scheduling algorithms, quality of services (QoS), performance analysis.
Citation:
Zhenhai Duan, Zhi-Li Zhang, Yiwei Thomas Hou, "Fundamental Trade-Offs in Aggregate Packet Scheduling," IEEE Transactions on Parallel and Distributed Systems, vol. 16, no. 12, pp. 1166-1177, Dec. 2005, doi:10.1109/TPDS.2005.149
Usage of this product signifies your acceptance of the Terms of Use.