article

Determining end-to-end delay bounds in heterogeneous networks

Authors:

Harrick M. VinAuthors Info & Claims

Multimedia Systems, Volume 5, Issue 3

Pages 157 - 163

https://doi.org/10.1007/s005300050052

Published: 01 May 1997 Publication History

Abstract

We define a class of Guaranteed Rate (GR) scheduling algorithms. The GR class includes Virtual Clock, Packet-by-Packet Generalized Processor Sharing and Self-Clocked Fair Queuing. For networks that employ scheduling algorithms belonging to GR, we present a method for determining an upper bound on end-to-end delay. The method facilitates determination of end-to-end delay bounds for a Variety of sources. We illustrate the method by determining end-to-end delay bounds for sources conforming to Leaky Bucket and exponentially bounded burstiness.

References

[1]

1. Clark DD, Shenker S, Zhang L (1992) Supporting reai-time applications in an integrated services packet network. In: Proceedings of ACM SIGCOMM, pp 14-26

[2]

2. Cruz RL (1991) A calculus for network delay, Part I: network elements in isolation. IEEE Trans Inf Theory 37:114-131

Digital Library

[3]

3. Cruz RL (1991) A calculus for network delay, Part II: network analysis. IEEE Trans Inf Theory, 37:132-141

Digital Library

[4]

4. Davin J, Heybey A (1990) A simulation study of fair qneueing and policy enforcement. Comput Commun Rev 20(5):23-29

Digital Library

[5]

5. Demers A, Keshav S, Shenker S (1989) Analysis and simulation of a fair queueing algorithm. In: Proceedings of ACM SIGCOMM, pp 1-12

[6]

6. Ferrari D, Verma DC (1990) A scheme for real-time channel establishment in wide-area networks. IEEE J Sel Areas Commun 8:368-379

Digital Library

[7]

7. Figuera N, Pasquale J (1995) Leave-in-time: a new service discipline for real-time communication in a packet-switching data network. In: ACM SIGCOMM 95, pp 207-218

[8]

8. Golestani SJ (1991) A framing strategy for congestion management. IEEE J Sel Areas Commun pp 1064-1077

[9]

9. Golestani SJ (1994) A self-clocked fair queueing scheme for high-speed applications. In: Proceedings of INFOCOM '94

[10]

10. Kalmanek CR, Kanakia H, Keshav S (1990) Rate-controlled servers for very high-speed networks. In: Proceedings of IEEE GLOBECOM '90, San Diego, CA, pp 300.3:1-300.3.9

[11]

11. Lam SS, Xie GG (1995) Burst scheduling: architecture and algorithm for switching packet video. In: Proceedings of INFOCOM '95

[12]

12. Parekh AK, Gallager RG (1994) A generalized processor-sharing approach to flow control in integrated services networks: the multiple node case. IEEE/ACM Trans Networking 2(2):137-150

Digital Library

[13]

13. Parekh AK (1992) A generalized processor-sharing approach to flow control in integrated services networks. PhD thesis, Department of Electrical Engineering and Computer Science, MIT, Cambridge, Mass.

[14]

14. Shenker S (1994) Making Greed Work in Networks: A Game-Theoretic Analysis of Switch Service Disciplines. In: Proceedings of ACM SIGCOMqVI '94, pp 47-57

[15]

15. Xie GG, Lam SS (1994) Delay Guarantee of Virtual Clock Server. Technical Report TR-94-24, Dept. of Computer Sciences, UT-Austin, TX

[16]

16. Yaron O, Sidi M (1994) Generalized processor-sharing networks with exponentially bounded burstiness arrivals. In: Proceedings of INFOCOM '94

[17]

17. Zhang H, Ferrari D (1993) Rate-controlled static priority queueing. In: Proceedings of INFOCOM '93, volume 2, pp 227-236

[18]

18. Zhang H, Keshav S (1991) Comparison of rate-based service disciplines. In: Proceedings of ACM SIGCOMM, pp 113-121

[19]

19. Zhang L (1990) Virtual clock: a new traffic control algorithm for packet-switching networks. In: Proceedings of ACM SIGCOMM '90, pp 19-29

Cited By

Schmitt JWang HMartinovic I(2010)A self-adversarial approach to delay analysis under arbitrary schedulingProceedings of the 4th international conference on Leveraging applications of formal methods, verification, and validation - Volume Part I10.5555/1939281.1939300(169-183)Online publication date: 18-Oct-2010
https://dl.acm.org/doi/10.5555/1939281.1939300
Eshete AJiang Y(2010)Flow aggregation using dynamic packet stateProceedings of the 16th EUNICE/IFIP WG 6.6 conference on Networked services and applications: engineering, control and management10.5555/1875907.1875943(263-265)Online publication date: 28-Jun-2010
https://dl.acm.org/doi/10.5555/1875907.1875943
Mahmood KJiang YEshete A(2010)On the modeling of delay and burstiness for calculating throughputProceedings of the 33rd IEEE conference on Sarnoff10.5555/1843486.1843488(6-10)Online publication date: 12-Apr-2010
https://dl.acm.org/doi/10.5555/1843486.1843488
Show More Cited By

Index Terms

Determining end-to-end delay bounds in heterogeneous networks

Recommendations

End-to-end delay bounds for traffic aggregates under guaranteed-rate scheduling algorithms

This paper evaluates, via both analysis and simulation, the end-to-end (e2e) delay performance of aggregate scheduling with guaranteed-rate (GR) algorithms. Deterministic e2e delay bounds for a single aggregation are derived under the assumption that ...
Tight end-to-end per-flow delay bounds in FIFO multiplexing sink-tree networks

Aggregate scheduling has been proposed as a solution for achieving scalability in large-size networks. However, in order to enable the provisioning of real-time services, such as video delivery or voice conversations, in aggregate scheduling networks, ...
Deterministic End-to-End Delay Bounds in an Accumulation Network
NETWORKING '00: Proceedings of the IFIP-TC6 / European Commission International Conference on Broadband Communications, High Performance Networking, and Performance of Communication Networks

In this paper, we focus on the determination of end-to-end delay bounds for FIFO accumulation networks with leaky bucket constrained sources, including IP and ATM network cases. We determine an upper bound for the overall end-to-end delay and prove its ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Multimedia Systems

Multimedia Systems Volume 5, Issue 3

Special issue on the fifth workshop on network and operating system support for digital audio and video 1995 (NOSSDAV)

May 1997

58 pages

ISSN:0942-4962

Editors:
P. Venkat Rangan
Univ. of California at San Diego, La Jolla
,
Thomas D. C. Little
Boston Univ., Boston, MA
,
Riccardo Gusella
China Hewlett-Pachard, Being, China

Issue’s Table of Contents

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 May 1997

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Schmitt JWang HMartinovic I(2010)A self-adversarial approach to delay analysis under arbitrary schedulingProceedings of the 4th international conference on Leveraging applications of formal methods, verification, and validation - Volume Part I10.5555/1939281.1939300(169-183)Online publication date: 18-Oct-2010
https://dl.acm.org/doi/10.5555/1939281.1939300
Eshete AJiang Y(2010)Flow aggregation using dynamic packet stateProceedings of the 16th EUNICE/IFIP WG 6.6 conference on Networked services and applications: engineering, control and management10.5555/1875907.1875943(263-265)Online publication date: 28-Jun-2010
https://dl.acm.org/doi/10.5555/1875907.1875943
Mahmood KJiang YEshete A(2010)On the modeling of delay and burstiness for calculating throughputProceedings of the 33rd IEEE conference on Sarnoff10.5555/1843486.1843488(6-10)Online publication date: 12-Apr-2010
https://dl.acm.org/doi/10.5555/1843486.1843488
Marosits TMolnár S(2009)Characterization of advanced round robin schedulerWSEAS TRANSACTIONS on COMMUNICATIONS10.5555/1852337.18523428:12(1233-1242)Online publication date: 1-Dec-2009
https://dl.acm.org/doi/10.5555/1852337.1852342
Gabor RMendelson AWeiss S(2009)Service level agreement for multithreaded processorsACM Transactions on Architecture and Code Optimization10.1145/1543753.15437556:2(1-33)Online publication date: 6-Jul-2009
https://dl.acm.org/doi/10.1145/1543753.1543755
Chu X(2008)Provisioning of parameterized quality of service in 802.11e based wireless mesh networksMobile Networks and Applications10.1007/s11036-008-0028-613:1-2(6-18)Online publication date: 1-Apr-2008
https://dl.acm.org/doi/10.1007/s11036-008-0028-6
Wiggers MBekooij MSmit G(2007)Modelling run-time arbitration by latency-rate servers in dataflow graphsProceedingsof the 10th international workshop on Software & compilers for embedded systems10.1145/1269843.1269846(11-22)Online publication date: 20-Apr-2007
https://dl.acm.org/doi/10.1145/1269843.1269846
Jiang Y(2006)Delay bound and packet scale rate guarantee for some expedited forwarding networksComputer Networks: The International Journal of Computer and Telecommunications Networking10.5555/1119569.164854150:1(15-28)Online publication date: 16-Jan-2006
https://dl.acm.org/doi/10.5555/1119569.1648541
Jiang Y(2006)Per-domain packet scale rate guarantee for expedited forwardingIEEE/ACM Transactions on Networking10.1109/TNET.2006.87617714:3(630-643)Online publication date: 1-Jun-2006
https://dl.acm.org/doi/10.1109/TNET.2006.876177
Urgaonkar BShenoy P(2004)SharcIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2004.126478115:1(2-17)Online publication date: 1-Jan-2004
https://dl.acm.org/doi/10.1109/TPDS.2004.1264781
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents