Fundamental Trade-Offs in Aggregate Packet Scheduling
|
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] 1166 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
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb