×

Fluid limits for networks with bandwidth sharing and general document size distributions. (English) Zbl 1169.60025

The authors consider a stochastic model of Internet congestion control that represents the randomly varying number of flows in a network where bandwidth is shared among document transfers. In contrast to an earlier work by F. P. Kelly and R. J. Williams [Ann. Appl. Probab. 14, No. 3, 1055–1083 (2004; Zbl 1066.60093)], the present paper allows interarrival times and document sizes to be generally distributed, rather than exponentially distributed. Furthermore, they allow a fairly general class of bandwidth sharing policies that includes the weighted \(\alpha \)-fair policies of J. Mo and J. Walrand [Fair end-to-end window-based congestion control. IEEE/ACM Transactions on Networking 8, 556–567 (2000)], as well as certain other utility based scheduling policies. To describe the evolution of the system, measure valued processes are used to keep track of the residual document sizes of all flows through the network. A fluid model (or formal functional law of large numbers approximation) associated with the stochastic flow level model is proposed. Under mild conditions, they show that the appropriately rescaled measure valued processes corresponding to a sequence of such models (with fixed network structure) are tight, and that any weak limit point of the sequence is almost surely a fluid model solution. For the special case of weighted \(\alpha \)-fair policies, they also characterize the invariant states of the fluid model.

MSC:

60K30 Applications of queueing theory (congestion, allocation, storage, traffic, etc.)
60F17 Functional limit theorems; invariance principles
90B15 Stochastic network models in operations research

Citations:

Zbl 1066.60093
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bonald, T. and Massoulié, L. (2001). Impact of fairness on Internet performance. In Proceedings of ACM Sigmetrics 2001 82-91.
[2] Bramson, M. (2005). Stability of networks for max-min fair routing. Presentation at the 13th INFORMS Applied Probability Conference, Ottawa.
[3] Chiang, M., Shah, D. and Tang, A. (2006). Stochastic stability under fair bandwidth allocation: General file size distribution. In Proceedings of the 44th Allerton Conference 899-908.
[4] Dai, J. G. (1995). On positive Harris recurrence of multiclass queueing networks: A unified approach via fluid limit models. Ann. Appl. Probab. 5 49-77. · Zbl 0822.60083 · doi:10.1214/aoap/1177004828
[5] de Veciana, G., Konstantopoulos, T. and Lee, T.-J. (2001). Stability and performance analysis of networks supporting elastic services. IEEE/ACM Transactions on Networking 9 2-14.
[6] Ethier, S. N. and Kurtz, T. G. (1986). Markov Processes . Wiley, New York. · Zbl 0592.60049
[7] Gromoll, H. C., Puha, A. L. and Williams, R. J. (2002). The fluid limit of a heavily loaded processor sharing queue. Ann. Appl. Probab. 12 797-859. · Zbl 1017.60092 · doi:10.1214/aoap/1031863171
[8] Gromoll, H. C. and Williams, R. J. (2008). Fluid model for a data network with \alpha -fair bandwidth sharing and general document size distributions: Two examples of stability. In Proceedings of Markov Processes and Related Topics- A Festschrift (T. G. Kurtz, S. N. Ethier, J. Feng and R. H. Stockbridge, eds.). Institute of Mathematical Statistics. Forthcoming. · Zbl 1166.90312 · doi:10.1214/074921708000000417
[9] Hansen, J., Reynolds, C. and Zachary, S. (2007). Stability of processor sharing networks with simultaneous resource requirements. J. Appl. Probab. 44 636-651. · Zbl 1132.60062 · doi:10.1239/jap/1189717534
[10] Harrison, J. M. (2000). Brownian models of open processing networks: Canonical representation of workload. Ann. Appl. Probab. 10 75-103. Corr. 13 (2003) 390-393. · Zbl 1131.60306 · doi:10.1214/aoap/1019737665
[11] Kallenberg, O. (1986). Random Measures , 4th ed. Academic Press, London. · Zbl 0345.60032
[12] Kelly, F. P. and Williams, R. J. (2004). Fluid model for a network operating under a fair bandwidth-sharing policy. Ann. Appl. Probab. 14 1055-1083. · Zbl 1066.60093 · doi:10.1214/105051604000000224
[13] Key, P. and Massoulié, L. (2006). Fluid models of integrated traffic and multipath routing. Queueing Syst. 53 85-98. · Zbl 1114.90007 · doi:10.1007/s11134-006-7588-6
[14] Lakshmikantha, A., Beck, C. L. and Srikant, R. (2004). Connection level stability analysis of the internet using the sum of squares (sos) techniques. In Conference on Information Sciences and Systems ( Princeton , New Jersey ).
[15] Lin, X. and Shroff, N. (2004). On the stability region of congestion control. In Proceedings of the 42nd Allerton Conference on Communications , Control and Computing 1266-1275.
[16] Lin, X., Shroff, N. and Srikant, R. (2008). On the connection-level stability of congestion-controlled communication networks. IEEE Trans. Inform. Theory 54 2317-2338. · Zbl 1330.90020 · doi:10.1109/TIT.2008.920213
[17] Massoulié, L. (2007). Structural properties of proportional fairness: Stability and insensitivity. Ann. Appl. Probab. 17 809-839. · Zbl 1125.60104 · doi:10.1214/105051606000000907
[18] Massoulié, L. and Roberts, J. (2000). Bandwidth sharing and admission control for elastic traffic. Telecommunication Systems 15 185-201. · Zbl 1030.68774 · doi:10.1023/A:1019138827659
[19] Mo, J. and Walrand, J. (2000). Fair end-to-end window-based congestion control. IEEE/ACM Transactions on Networking 8 556-567.
[20] Puha, A. L. and Williams, R. J. (2004). Invariant states and rates of convergence for a critical fluid model of a processor sharing queue. Ann. Appl. Probab. 14 517-554. · Zbl 1061.60098 · doi:10.1214/105051604000000017
[21] Srikant, R. (2004). On the positive recurrence of a Markov chain describing file arrivals and departures in a congestion-controlled network. Presentation the IEEE Computer Communications Workshop.
[22] Ye, H.-Q. (2003). Stability of data networks under an optimization-based bandwidth allocation. IEEE Trans. Automat. Control 48 1238-1242. · Zbl 1364.90103 · doi:10.1109/TAC.2003.814269
[23] Ye, H.-Q., Ou, J. and Yuan, X.-M. (2005). Stability of data networks: Stationary and bursty models. Oper. Res. 53 107-125. · Zbl 1165.90371 · doi:10.1287/opre.1040.0139
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.