Fundamental trade-offs in aggregate packet scheduling

Zhenhai Duan; Zhi Li Zhang; Yiwei Thomas Hou

doi:10.1109/TPDS.2005.149

Fundamental trade-offs in aggregate packet scheduling

Zhenhai Duan, Zhi Li Zhang, Yiwei Thomas Hou

Computer Science and Engineering

Research output: Contribution to journal › Article › peer-review

8 Scopus citations

Abstract

In this paper, we investigate the fundamental trade-offs in aggregate packet scheduling for support of guaranteed delay serviće. 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 worstcase 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.

Original language	English (US)
Pages (from-to)	1166-1177
Number of pages	12
Journal	IEEE Transactions on Parallel and Distributed Systems
Volume	16
Issue number	12
DOIs	https://doi.org/10.1109/TPDS.2005.149
State	Published - Dec 2005

Bibliographical note

Funding Information:
The authors would like to thank the anonymous reviewers of the Proceedings of the IEEE International Conference on Network Protocols 2001 and the IEEE Transactions on Parallel and Distributed Systems for many valuable comments. This work was supported in part by US National Science Foundation Grants CAREER Award NCR-9734428, EIA-9818338, and ITR ANI-0085824. Any opinions, findings, and conclusions or recommendations expressed in this paper are those of the authors and do not necessarily reflect the views of the US National Science Foundation. An earlier, abridged version of this paper appeared in the Proceedings of the IEEE International Conference on Network Protocols 2001 under the same title.

Keywords

Aggregate packet scheduling algorithms
Packet scheduling algorithms
Performance analysis
Quality of services (QoS)

Publisher link

10.1109/TPDS.2005.149

Find It

Find It at U of M Libraries

Cite this

@article{5161d4adc560467b86452fab82b7fa4d,

title = "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 servi{\'c}e. 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 worstcase 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.",

keywords = "Aggregate packet scheduling algorithms, Packet scheduling algorithms, Performance analysis, Quality of services (QoS)",

author = "Zhenhai Duan and Zhang, {Zhi Li} and Hou, {Yiwei Thomas}",

note = "Funding Information: The authors would like to thank the anonymous reviewers of the Proceedings of the IEEE International Conference on Network Protocols 2001 and the IEEE Transactions on Parallel and Distributed Systems for many valuable comments. This work was supported in part by US National Science Foundation Grants CAREER Award NCR-9734428, EIA-9818338, and ITR ANI-0085824. Any opinions, findings, and conclusions or recommendations expressed in this paper are those of the authors and do not necessarily reflect the views of the US National Science Foundation. An earlier, abridged version of this paper appeared in the Proceedings of the IEEE International Conference on Network Protocols 2001 under the same title.",

year = "2005",

month = dec,

doi = "10.1109/TPDS.2005.149",

language = "English (US)",

volume = "16",

pages = "1166--1177",

journal = "IEEE Transactions on Parallel and Distributed Systems",

issn = "1045-9219",

publisher = "IEEE Computer Society",

number = "12",

}

TY - JOUR

T1 - Fundamental trade-offs in aggregate packet scheduling

AU - Duan, Zhenhai

AU - Zhang, Zhi Li

AU - Hou, Yiwei Thomas

N1 - Funding Information: The authors would like to thank the anonymous reviewers of the Proceedings of the IEEE International Conference on Network Protocols 2001 and the IEEE Transactions on Parallel and Distributed Systems for many valuable comments. This work was supported in part by US National Science Foundation Grants CAREER Award NCR-9734428, EIA-9818338, and ITR ANI-0085824. Any opinions, findings, and conclusions or recommendations expressed in this paper are those of the authors and do not necessarily reflect the views of the US National Science Foundation. An earlier, abridged version of this paper appeared in the Proceedings of the IEEE International Conference on Network Protocols 2001 under the same title.

PY - 2005/12

Y1 - 2005/12

N2 - In this paper, we investigate the fundamental trade-offs in aggregate packet scheduling for support of guaranteed delay serviće. 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 worstcase 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.

AB - In this paper, we investigate the fundamental trade-offs in aggregate packet scheduling for support of guaranteed delay serviće. 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 worstcase 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.

KW - Aggregate packet scheduling algorithms

KW - Packet scheduling algorithms

KW - Performance analysis

KW - Quality of services (QoS)

UR - http://www.scopus.com/inward/record.url?scp=30344478561&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=30344478561&partnerID=8YFLogxK

U2 - 10.1109/TPDS.2005.149

DO - 10.1109/TPDS.2005.149

M3 - Article

AN - SCOPUS:30344478561

SN - 1045-9219

VL - 16

SP - 1166

EP - 1177

JO - IEEE Transactions on Parallel and Distributed Systems

JF - IEEE Transactions on Parallel and Distributed Systems

IS - 12

ER -

Fundamental trade-offs in aggregate packet scheduling

Abstract

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this