Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-13T00:42:58.925Z Has data issue: false hasContentIssue false
  • English
  • Français

Sample Path Criteria for Weak Majorization

Part of: Special processes

Published online by Cambridge University Press:  01 July 2016

Panayotis D. Sparaggis ,
Don Towsley  and
Christos G. Cassandras
Panayotis D. Sparaggis*
Affiliation:
University of Massachusetts, Amherst
Don Towsley*
Affiliation:
University of Massachusetts, Amherst
Christos G. Cassandras*
Affiliation:
University of Massachusetts, Amherst
*
* Postal address: Department of Electrical and Computer Engineering
** Department of Computer Science, University of Massachusetts, Amherst, MA 01003, USA.
* Postal address: Department of Electrical and Computer Engineering
Get access Rights & Permissions [Opens in a new window]

Abstract

We present two forms of weak majorization, namely, very weak majorization and p-weak majorization that can be used as sample path criteria in the analysis of queueing systems. We demonstrate how these two criteria can be used in making comparisons among the joint queue lengths of queueing systems with blocking and/or multiple classes, by capturing an interesting interaction between state and performance descriptors. As a result, stochastic orderings on performance measures such as the cumulative number of losses can be derived. We describe applications that involve the determination of optimal policies in the context of load-balancing and scheduling.

Keywords

MAJORIZATIONSTOCHASTIC ORDERINGBLOCKINGROUTINGSCHEDULING

MSC classification

Primary: 60K99: None of the above, but in this section
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 26 , Issue 1 , March 1994 , pp. 155 - 171
Copyright
Copyright © Applied Probability Trust 1994 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

This work was partly supported by an IBM Graduate Fellowship Award and by NSF under contracts ECS-8801912 and NCR-9116183.

References

[1] Bremaud, P. (1981) Point Processes and Queues. Wiley, New York.CrossRefGoogle Scholar
[2] Chang, C. S. (1992) A new ordering for stochastic majorization: theory and applications. Adv. Appl. Prob. 24, 604–634.CrossRefGoogle Scholar
[3] Chang, C. S. (1991) Smoothing point processes as a means to increase throughput. IBM Technical Report RC 16886.Google Scholar
[4] Chang, C. S., Chao, X., Pinedo, M. and Shanthikumar, J. G. (1991) Stochastic convexity of multidimensional processes and their applications. IEEE Trans. Autom. Control 36, 1347–1355.CrossRefGoogle Scholar
[5] Glasserman, P. and Yao, D. D. (1992) Monotonicity in generalized semi-Markov processes. Math. Operat. Res. 17, 1–21.CrossRefGoogle Scholar
[6] Marshall, A. W. and Olkin, I. (1979) Inequalities: Theory of Majorization and Its Applications. Academic Press, New York.Google Scholar
[7] Menich, R. (1987) Optimality of the shortest queue routing for dependent service stations. Proc. 26th IEEE Conf. Decision and Control, Los Angeles, California.CrossRefGoogle Scholar
[8] Shaked, M. and Shanthikumar, J. G. (1990) Convexity of a set of stochastically ordered random variables. Adv. Appl. Prob. 22, 160–167.CrossRefGoogle Scholar
[9] Shanthikumar, J. G. and Yao, D. D. (1991) Strong stochastic convexity: closure properties and applications. J. Appl. Prob. 28, 131–145.CrossRefGoogle Scholar
[10] Sparaggis, P. D. and Cassandras, C. G. (1991) Monotonicity of throughput in communication networks with blocking. Proc. IEEE INFOCOM'91. Google Scholar
[11] Sparaggis, P. D. and Towsley, D. (1992) Optimal routing and scheduling of customers with deadlines.Google Scholar
[12] Sparaggis, P. D., Towsley, D. and Cassandras, C. G. (1993) Extremal properties of the shortest/longest non-full queue policies in finite-capacity systems with state-dependent service rates. J. Appl. Prob. 30, 223–236.CrossRefGoogle Scholar
[13] Towsley, D. and Panwar, S. S. (1992) Optimality of the stochastic earliest deadline policy for the G/M/c queue serving customers with deadlines. Preprint, 1992.Google Scholar
[14] Towsley, D. Fdida, S. and Santoso, H. (1991) Design and analysis of flow control protocols for Metropolitan area networks. In High-capacity Local and Metropolitan Area Networks, ed. Pujolle, G., pp. 471–992, Springer-Verlag, New York.CrossRefGoogle Scholar
[15] Towsley, D., Sparaggis, P. D. and Cassandras, C. G. (1992) Optimal routing and buffer allocation for a class of finite capacity queueing systems. IEEE Trans. Autom. Control 37, 1446–1451.CrossRefGoogle Scholar
[16] Walrand, J. (1988) An Introduction to Queueing Networks. Prentice-Hall, Englewood Cliffs, NJ.Google Scholar