The Proof of a Folk Theorem on Queuing Delay with Applications to Routing in Networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The Proof of a Folk Theorem on Queuing Delay with Applications to Routing in Networks

Full text

Pdf (827 KB)

Source

Journal of the ACM (JACM) archive
Volume 30 , Issue 4 (October 1983) table of contents

Pages: 834 - 851

Year of Publication: 1983

ISSN:0004-5411

Author

Bruce Hajek

Coordinated Science Laboratory, University of Illinois, 1101 W. Springfield, Urbana, IL

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 56, Citation Count: 2

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/2157.322409 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Bm~rsE~s, D.P.Algonttmas for nonlinear multicomodity network flow. Int. Syrup. on Systems Optimization and Analysis, A. Bensoussan and J.L. Lions, Eds., Springer-Verlsg, New York, 1979, pp 210-224.
	2	BOROVKOV, A.A. Stochastic Processes in Queueing Theory. Springer-Verlag, New York, 1976.
	3	Bm~x~, L.Probability. Addison-Wesley, Reading, Mass, 1968.
	4	EPrtREMIDES, A. Regularity and delay in queueing systems. In Proc 181h Annual Conference on Communication, Control, and Computing, Coordinated Science Laboratory, University of Illinois (Urbana, I11., Oct. 1980), p. 339.
	5	EP~~, A., Vnp.arYx, P., AND WALRAND, J. A simple dynamic routing problem, IEEE Trans. Automatic Control 25, 4 (Aug. 1980), 690--693.
	6	Foscmm, G J., AND SnLZ, J A basic dynamic routing problem and diffusion. IEEE Trans. Commun. 26, 3 (Mar. 1978), 320-327.
	7	FRATTA, L., GERLA, M., AND K_~ImtOCK, L.The flow deviation method--an approach to store and forward commumeation network design. Networks 3 (1973), 97-133.
	8	FuctLs, L. A new proof of an inequality of Hardy-Littlewood-Polya. Mmematisk Tidsskritt B (1974), 53-54.
	9	GALLAGHER, R. A minimum delay routing algorithm using distnbuted computation. IEEE Trans. Commurt 25, l Oan. 1977), 73-85
	10	HOMBLtrr, P.A.Determinism minimizes wamng time in queues. Preprint. Dept. of Electrical Engineenng and Computer Science, Massachusetts InsUtute of Technology, Cambridge, Mass., May 1982.
	11	JACKSOn, J.P. Networks of waiting hnes. Oper. Res. 5 (1957), 518-521.
	12	Kt,sir,~ocK, L.Queueing Systems--Volume 2: Computer Applications. Wiley, New York, 1976.
	13	NEUTS, M.F.Matrix-Geometric Solutions m Stochastic Models--An Algorithmic Approach. Johns Hopkins University Press, Baltimore, Md., 1981.
	14	ROC~FELt.nR, R.T Convex Analysis. Princeton University Press, Princeton, New Jersey, 1970.
	15	RoGoz~, B.A.Some extremal problems m the theory of mass service. Theor. Probab, Appl. 11, i (1966), 144-151.
	16	SEOAt~, A.Optimal distributed routing for line-switched data networks. IEEE Trans. Commun. 27, 1 (Jan. 1979), 201-209.
	17	T~.KACS, L.Introduction to the Theory of Queues. Oxford Umversity Press, New York, 1962.
	18	VAslcmc, O.A An inequality for the variance of waiting time under a general queueing discipline. Oper. Res. 25, 5 (Sept.-Oct. 1977), 879--884.
	19	VAN Loot~, T G. Application of phase-type Markov processes to multiple access and routing for packet communicauon. M.S. thesis, Dept. of Elec. Eng., University of Illinois, Urbana, Ill, (1981).
	20	Yu~, T.P The design and analysis of a semidynamic deterministic routing rule. IEEE Trans. Commun. 29, 4 (April 1981), 498-504.

CITED BY 2

	Christopher Rose , Roy Yates, Ensemble polling strategies for increased paging capacity in mobile communication networks, Wireless Networks, v.3 n.2, p.159-167, May 1997
	François Baccelli , William A. Massey , Don Towsley, Acyclic fork-join queuing networks, Journal of the ACM (JACM), v.36 n.3, p.615-642, July 1989