×

AIMD algorithms and exponential functionals. (English) Zbl 1041.60072

The asymptotic behaviour of a connection transmitting packets into a network according to a general additive-increase multiplicative-decrease (AIMD) algorithm is investigated. The stationary properties of this algorithm are analyzed when the rate of occurrence of clumps (loss of packets) becomes arbitrary small. From a probabilistic point of view, it is shown that exponential functionals associated to compound Poisson processes play a key role. A formula for the fractional moments and some density functions are obtained. Analytically, to derive the explicit expression of the distributions involved, the natural framework of this study turns out to be the q-calculus. Different loss models are then compared using concave ordering. It is shown, quite surprisingly, that for a fixed loss rate, the correlated loss model has higher throughput than an uncorrelated loss one.

MSC:

60K30 Applications of queueing theory (congestion, allocation, storage, traffic, etc.)
90B18 Communication networks in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aldous, D. (1989). Probability Approximations via the Poisson Clumping Heuristic . Springer, New York. · Zbl 0679.60013
[2] Altman, E., Avrachenko, K., Barakat, C. and Nuñez-Queija, R. (2001). State dependent \(M/G/1\) type queueing analysis for congestion control in data networks. In Infocom 2001 . IEEE, New York.
[3] Andrews, G. E., Askey, R. and Roy, R. (1999). Special Functions . Cambridge Univ. Press. · Zbl 0920.33001
[4] Bertoin, J., Biane, P. and Yor, M. (2002). Poissonian exponential functionals, \(q\)-series, \(q\)-integrals and the moment problem for log-normal distributions. Technical Report PMA-705, Laboratoire de Probabilités, Univ. Paris 6. · Zbl 1056.60046
[5] Bertoin, J. and Yor, M. (2001). On the entire moments of self-similar Markov processes and exponential functionals of Lévy processes. Technical Report PMA-702, Laboratoire de Probabilités, Univ. Paris 6. · Zbl 1024.60030
[6] Bolot, J. (1993). End-to-end packet delay and loss behavior in the Internet. In ACM SIGCOMM’93 289–298. ACM Press, New York.
[7] Carmona, P., Petit, F. and Yor, M. (1997). On the distribution and asymptotic results for exponential functionals of Lévy processes. In Exponential Functionals and Principal Values Related to Brownian Motion (M. Yor, ed.) 73–130. Rev. Mat. Iberoam., Madrid. · Zbl 0905.60056
[8] Dumas, V., Guillemin, F. and Robert, P. (2002). A Markovian analysis of Additive-Increase Multiplicative-Decrease (AIMD) algorithms. Adv. in Appl. Probab. 34 85–111. · Zbl 1002.60091 · doi:10.1239/aap/1019160951
[9] Feller, W. (1971). An Introduction to Probability Theory and Its Applications , 2nd ed. Wiley, New York. · Zbl 0219.60003
[10] Ferguson, T. S. (1972). Lose a dollar or double your fortune. Proc. Sixth Berkeley Symp. Math. Statist. Probab. 3 657–666. Univ. California Press, Berkeley. · Zbl 0255.60013
[11] Flajolet, P., Gourdon, X. and Dumas, P. (1995). Mellin transforms and asymptotics: Harmonic sums. Theoret. Comput. Sci. 144 3–58. · Zbl 0869.68057 · doi:10.1016/0304-3975(95)00002-E
[12] Floyd, S. (1991). Connections with multiple congested gateways in packet-switched networks 1: One way traffic. Computer Comm. Rev. 21 30–47.
[13] Gasper, G. and Rahman, M. (1990). Basic Hypergeometric Series . Cambridge Univ. Press. · Zbl 0695.33001
[14] Harrison, J. M. (1977). Ruin problems with compounding assets. Stochastic Process. Appl. 5 67–79. · Zbl 0361.60053 · doi:10.1016/0304-4149(77)90051-5
[15] Jacobson, V. (1988). Congestion avoidance and control. In SIGCOMM’88 Symposium : Communications Architectures and Protocols . ACM, New York.
[16] Kingman, J. F. C. (1993). Poisson Processes . Clarendon Press, New York. · Zbl 0771.60001
[17] Koornwinder, T. H. (1994). \(q\)-special functions, a tutorial. In Representation of Lie Groups and Quantum Groups (V. Baldoni and M. A. Picardello, eds.) 46–128. Longman, New York. · Zbl 0821.17015
[18] Misra, V., Gong, W. and Towsley, D. (1999). Stochastic differential equation modeling and analysis of TCP windowsize behavior. In Performance’99 .
[19] Neveu, J. (1977). Processus ponctuels. École d’Été de Probabilités de Saint-Flour VI . Lecture Notes in Math. 598 249–445. Springer, Berlin. · Zbl 0439.60044
[20] Ott, T. J., Kemperman, J. H. B. and Mathis, M. (1996). The stationary behavior of ideal TCP congestion avoidance. Unpublished manuscript.
[21] Padhye, J., Firoiu, V., Towsley, D. and Kurose, J. (1998). Modeling TCP throughput: A simple model and its empirical validation. In ACM Sigcomm ’98. ACM, New York.
[22] Paxson, V. (1999). End-to-end internet packet dynamics. IEEE/ACM Trans. Networking 7 277–292.
[23] Stevens, W. R. (1994). TCP-IP Illustrated 1 : The Protocols . Addison–Wesley, Reading, MA. · Zbl 0828.68017
[24] Stoyan, D. (1983). Comparison Methods for Queues and Other Stochastic Models . Wiley, New York. · Zbl 0536.60085
[25] Yajnik, M., Kurose, J. and Towsley, D. (1995). Packet loss correlation in the MBone multicast network experimental measurements and Markov chain models. Technical Report UM-CS-1995-115, Univ. Massachusetts, Amherst.
[26] Yor, M. (1992). Some Aspects of Brownian Motion. Part I . Some Special Functionals . Birkhäuser, Basel. · Zbl 0779.60070
[27] Yor, M. (1997). Some Aspects of Brownian motion. Part II. Some Recent Martingale Problems . Birkhäuser, Basel. · Zbl 0880.60082
[28] Yor, M. (2001). Exponential Functionals of Brownian Motion and Related Processes . Springer, Berlin. · Zbl 0999.60004 · doi:10.1007/978-3-642-56634-9
[29] Zhang, Y., Paxson, V. and Shenker, S. (2000). The stationarity of internet path properties: Routing, loss, and throughput. Technical report ACIRI.
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.