Hostname: page-component-78c5997874-ndw9j Total loading time: 0 Render date: 2024-11-05T14:19:40.746Z Has data issue: false hasContentIssue false
  • English
  • Français

Stability of spatial queueing systems

Part of: Stochastic processes Special processes Operations research and management science

Published online by Cambridge University Press:  01 July 2016

C. Bordenave
C. Bordenave*
Affiliation:
Ecole Normale Supérieure and INRIA
*
∗ Postal address: DI/TREC, Ecole Normale Supérieure, 45 rue d'Ulm, F-75230 Paris Cedex 05, France. Email address: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

In this paper, we analyze a queueing system characterized by a space-time arrival process of customers served by a countable set of servers. Customers arrive at points in space and the server stations have space-dependent processing rates. The workload is seen as a Radon measure and the server stations can adapt their power allocation to the current workload. We derive the stability region of the queueing system in the usual stationary ergodic framework. The analysis of this stability region gives some counter-intuitive results. Some specific subclasses of policy are also studied. Wireless communications networks is a natural field of application for the model.

Keywords

Stability regionspace-time point processwireless networkdynamic schedulingoptimal resource allocation

MSC classification

Primary: 60K25: Queueing theory 60K30: Applications (congestion, allocation, storage, traffic, etc.) 90B15: Network models, stochastic
Secondary: 60G55: Point processes
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 38 , Issue 2 , June 2006 , pp. 487 - 504
Copyright
Copyright © Applied Probability Trust 2006 

Footnotes

Presented at the ICMS Workshop on Spatial Stochastic Modelling with Applications to Communications Networks (Edinburgh, June 2004).

References

Armony, M. and Bambos, N. (2003). Queueing dynamics and maximal throughput scheduling in switched processing systems. Queueing Systems 44, 209–252.Google Scholar
Baccelli, F. and Brémaud, P. (2003). Elements of Queueing Theory. Palm Martingale Calculus and Stochastic Recurrences (Appl. Math. 26), 2nd edn. Springer, Berlin.Google Scholar
Baccelli, F., Blaszczyszyn, B. and Tournois, F. (2003). Downlink admission/congestion control and maximal load in CDMA networks. In Proc. INFOCOM 2003, Vol. 1, ed. Bauer, F., IEEE, Piscataway, NJ, pp. 723–733.Google Scholar
Bambos, N. and Michailidis, G. (2004). Queueing and scheduling in random environments. Adv. Appl. Prob. 36, 293–317.Google Scholar
Bambos, N. and Michailidis, G. (2005). Queueing networks of random link topology: stationary dynamics of maximal throughput schedules. Queueing Systems 50, 5–52.CrossRefGoogle Scholar
Billingsley, P. (1968). Convergence of Probability Measures. John Wiley, New York.Google Scholar
Bordenave, C. (2004). Stability properties of data flows on a CDMA network in macrodiversity. INRIA Tech. Rep. RR-5257. Available at http://www.inria.fr/rrrt/rr-5257.html.Google Scholar
Bordenave, C. (2006). Spatial capacity of multiple access networks. Submitted. Draft version available at http://www.inria.fr/rrrt/rr-5102.html.Google Scholar
Borovkov, A. (ed.) (1998). Ergodicity and Stability of Stochastic Processes (Wiley Ser. Prob. Statist.). John Wiley, Chichester.Google Scholar
Daley, D. J. and Vere-Jones, D. (1988). An Introduction to the Theory of Point Processes (Springer Ser. Statist.). Springer, New York.Google Scholar
Lindvall, T. (1992). Lectures on the Coupling Method (Wiley Ser. Prob. Math. Statist. Prob. Math. Statist.). John Wiley, New York.Google Scholar
Penrose, M. (2003). Random Geometric Graphs (Oxford Stud. Prob. 5). Oxford University Press.Google Scholar
Rudin, W. (1974). Real and Complex Analysis (McGraw-Hill Ser. Higher Math.), 2nd edn. McGraw-Hill, New York.Google Scholar
Tassiulas, L. and Ephremides, A. (1992). Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Trans. Automatic Control 37, 1936–1936.Google Scholar
Tassiulas, L. and Ephremides, A. (1996). Throughput properties of a queueing network with distributed dynamic routing and flow control. Adv. Appl. Prob. 28, 285–307.Google Scholar
Wasserman, K., Michailidis, G. and Bambos, N. (2001). Differentiated processors scheduling on heterogeneous task flows. Tech. Rep. SU-Netlab-2001-12/1, Engineering Library, Stanford University.Google Scholar
Wasserman, K. M., Michailidis, G. and Bambos, N. (2005). Optimal processor allocation to differentiated Job flows. Performance Eval. 63, 1–14.CrossRefGoogle Scholar