Abstract
This paper studies a discrete-time queueing system in which the traffic regulation places an upper bound on the number of arrivals in each of the non-overlapping time windows (virtual frames) of a fixed length. The worst traffic passing through this traffic regulation is characterized. As a criterion for traffic comparison, this paper employs the weighted sum of queueing delays with the weighting factors decaying geometrically over the time horizon. This paper uses dynamic programming techniques and convexity argument to characterize the worst traffic.
Similar content being viewed by others
References
J.M. Barceló, J. García and O. Casals, Comparison of models for the multiplexing of worst case traffic sources, in: First Workshop on ATM Traffic Management, Paris, France, December 1995.
J.M. Barceló, J. García-Vidal and O. Casals, Worst-case traffic in a tree network of ATM multiplexers, IEEE/ACM Trans. Networking 8(4) (2000) 507-516.
D. Bertsekas, Dynamic Programming: Deterministic and Stochastic Models (Prentice-Hall, Englewood Cliffs, NJ, 1987).
D. Bertsekas and R. Gallager, Data Networks, 2nd ed. (Prentice-Hall, Englewood Cliffs, NJ, 1992).
S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang and W. Weiss, An architecture for differentiated services, Internet Society, RFC 2475 (December 1998).
M. Bonatti and A.A. Gaivoronski, Worst case analysis of ATMsources with application to access engineering of broadband multiservice networks, in: The Fundamental Role of Teletraffic in the Evolution of Telecommunication Networks, eds. J. Labetoulle and J.W. Roberts (Elsevier Science, Amsterdam, 1994) pp. 559-569.
B.T. Doshi, Deterministic rule based traffic descriptors for broadband ISDN: Worst case behavior and connection acceptance control, in: The Fundamental Role of Teletraffic in the Evolution of Telecommunication Networks, eds. J. Labetoulle and J.W. Roberts (Elsevier Science, Amsterdam, 1994) pp. 591-600.
B. Erimli, J. Murphy and J. Murphy, On worst case traffic in ATM networks, in: Twelfth UK IEE Teletraffic Symposium, Windsor, United Kingdom, March 1995.
S.J. Golestani, Congestion-free communication in broadband packet networks, IEEE Trans. Commun. 39(12) (1991) 1802-1812.
A. Skliros, Characterizing the worst traffic profile passing through an ATM-UNI, in: First UK Workshop on Performance Modeling and Evaluation of ATM Networks, IFIP, 1993, pp. 74-84.
T. Tsuchya and H. Saito, The worst case cell arrival patterns that conform to the GCRA in ATM networks, in: Proc. of GLOBECOM'95, November 1995, pp. 1432-1438.
T. Tsuchya and H. Saito, The worst case cell arrival patterns in ATM networks, IEICE Trans. Commun. B 81(5) (1998) 996-1003.
J.S. Turner, New directions in communications (or which way to the information age?), IEEE Commun. Mag. (October 1986).
T. Worster, Modelling deterministic queues: the leaky bucket as an arrival process, in: The Fundamental Role of Teletraffic in the Evolution of Telecommunication Networks, eds. J. Labetoulle and J.W. Roberts (Elsevier Science, Amsterdam, 1994) pp. 581-590.
N. Yamanaka, Y. Sato and K. Sato, Performance limitation of leaky bucket algorithm for usage parameter control and bandwidth allocation methods, IEICE Trans. Commun. E75-B(2) (1992) 82-86.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Lee, D.C. Worst Traffic Passing Virtual Frame Regulation: Analysis with Dynamic Programming. Queueing Systems 38, 381–395 (2001). https://doi.org/10.1023/A:1010943810954
Issue Date:
DOI: https://doi.org/10.1023/A:1010943810954