×

On large deviations in load sharing networks. (English) Zbl 0938.60097

At a load sharing network consumers of different types arrive according to independent Poisson processes. They can be served at certain locations within the network depending on their type, and they are assigned to suitable locations using an allocation policy. The holding times of the demands are i.i.d. exponentially distributed. Three different allocation policies are compared by evaluating the associated overflow exponents of the network: optimal repacking (AR), least load routing (LLR), and Bernoulli splitting (BS). At first the evaluation is performed for simple and basic networks and then in case of AR and BS generalized for networks with arbitrary topologies. For the LLR-policy in the general case a conjecture is formulated. The proofs heavily depend on large deviations theory.

MSC:

60K30 Applications of queueing theory (congestion, allocation, storage, traffic, etc.)
60F10 Large deviations
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90B15 Stochastic network models in operations research
Full Text: DOI

References:

[1] Alany ali, M. and Hajek, B. (1997). Analy sis of simple algorithms for dy namic load balancing. Math. Oper. Res. To appear. JSTOR: · Zbl 0904.60075 · doi:10.1287/moor.22.4.840
[2] Alany ali, M. and Hajek, B. (1978). On large deviations of Markov processes with discontinuous statistics. Ann. Appl. Probab. 8 45-66. · Zbl 0936.60021 · doi:10.1214/aoap/1027961033
[3] Azar, Y., Broder, A. and Karlin, A. (1992). On-line load balancing. In Proceedings Thirty-Third Annual Sy mposium on FOCS 218-225. · Zbl 0977.68878
[4] Blinovskii, V. M. and Dobrushin, R. L. (1994). Process level large deviations for a class of piecewise homogeneous random walks. In The Dy nkin Festschrift: Markov Processes and Their Applications 1-59. Birkhäuser, Boston. · Zbl 0819.60029
[5] Dembo, A. and Zeitouni, O. (1992). Large Deviations Techniques and Applications. Jones and Bartlett, Boston. · Zbl 0793.60030
[6] Dupuis, P. and Ellis, R. S. (1995). The large deviation principle for a general class of queueing sy stems I. Trans. Amer. Math. Soc. 347 2689-2751. JSTOR: · Zbl 0869.60022 · doi:10.2307/2154753
[7] Ethier, S. N. and Kurtz, T. G. (1986). Markov Processes. Wiley, New York. · Zbl 0592.60049
[8] Gibbens, R., Kelly, F. P. and Turner S. (1993). Dy namic routing in multiparented networks. IEEE/ACM Transactions on Networking 2 261-270.
[9] Hajek, B. (1990). Performance of global load balancing by local adjustment. IEEE Trans. Inform. Theory 36 1398-1414. · Zbl 0716.90065 · doi:10.1109/18.59935
[10] Shwartz, A. and Weiss, A. (1995). Large Deviations for Performance Analy sis, Queues, Communication and Computing. Chapman & Hall, London. · Zbl 0871.60021
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.