×

Stability of a subcritical fluid model for fair bandwidth sharing with general file size distributions. (English) Zbl 1460.60104

Summary: This work concerns the asymptotic behavior of solutions to a (strictly) subcritical fluid model for a data communication network, where file sizes are generally distributed and the network operates under a fair bandwidth-sharing policy. Here we consider fair bandwidth-sharing policies that are a slight generalization of the \(\alpha\)-fair policies introduced by J. Mo and J. Walrand [“Fair end-to-end window-based congestion control”, IEEE Trans. Networks 8, No. 5, 556–567 (2000; doi:10.1109/90.879343)]. Since the year 2000, it has been a standing problem to prove stability of the data communications network model of L. Massoulié and J. W. Roberts [Telecommun. Syst. 15, No. 1–2, 185–201 (2000; Zbl 1030.68774)], with general file sizes and operating under fair bandwidth sharing policies, when the offered load is less than capacity (subcritical conditions). A crucial step in an approach to this problem is to prove stability of subcritical fluid model solutions. In [IEEE Trans. Autom. Control 57, No. 3, 579–591 (2012; Zbl 1369.93700)], F. Paganini et al. introduced a Lyapunov function for this purpose and gave an argument, assuming that fluid model solutions are sufficiently smooth in time and space that they are strong solutions of a partial differential equation and assuming that no fluid level on any route touches zero before all route levels reach zero. The aim of the current paper is to prove stability of the subcritical fluid model without these strong assumptions. Starting with a slight generalization of the Lyapunov function proposed by Paganini et al., assuming that each component of the initial state of a measure-valued fluid model solution, as well as the file size distributions, have no atoms and have finite first moments, we prove absolute continuity in time of the composition of the Lyapunov function with any subcritical fluid model solution and describe the associated density. We use this to prove that the Lyapunov function composed with such a subcritical fluid model solution converges to zero as time goes to infinity. This implies that each component of the measure-valued fluid model solution converges vaguely on \(( 0,\infty )\) to the zero measure as time goes to infinity. Under the further assumption that the file size distributions have finite \(p\)th moments for some \(p>1\) and that each component of the initial state of the fluid model solution has finite \(p\)th moment, it is proved that the fluid model solution reaches the measure with all components equal to the zero measure in finite time and that the time to reach this zero state has a uniform bound for all fluid model solutions having a uniform bound on the initial total mass and the \(p\)th moment of each component of the initial state. In contrast to the analysis of Paganini et al., we do not need their strong smoothness assumptions on fluid model solutions and we rigorously treat the realistic, but singular situation, where the fluid level on some routes becomes zero, whereas other route levels remain positive.

MSC:

60K30 Applications of queueing theory (congestion, allocation, storage, traffic, etc.)
60G57 Random measures
60J70 Applications of Brownian motions and diffusion theory (population genetics, absorption problems, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bonald T, Massoulié L (2001) Impact of fairness on Internet performance. SIGMETRICS Performance Evaluation Rev. 29(1):82-91.Google Scholar
[2] Borst S, Egorova R, Zwart B (2014) Fluid limits for bandwidth-sharing networks in overload. Math. Oper. Res. 39(2):533-560.Google Scholar · Zbl 1303.60081
[3] Bramson M (2008) Stability of queueing networks. Probab. Surveys 5:169-345.Google Scholar · Zbl 1189.60005
[4] Bramson M (2010) Network stability under max-min fair bandwidth sharing. Ann. Appl. Probab. 20(3):1126-1176.Google Scholar · Zbl 1208.60087
[5] Chiang M, Shah D, Tang A (2006) Stochastic stability under network utility maximization: General file size distribution. Proc. 44th Allerton Conf. Comm. Control Comput., vol. 5 (IEEE, Piscataway, NJ), 49-77.Google Scholar
[6] Dai JG (1995) On positive Harris recurrence of multiclass queueing networks: A unified approach via fluid limit models. Ann. Appl. Probab. 5(1):49-77.Google Scholar · Zbl 0822.60083
[7] De Veciana G, Lee TJ, Konstantopoulos T (2001) Stability and performance analysis of networks supporting elastic services. IEEE/ACM Trans. Networks 9(1):2-14.Google Scholar
[8] Gromoll HC, Williams RJ (2008) Fluid Model for a Data Network with α-Fair Bandwidth Sharing and General Document Size Distributions: Two Examples of Stability, vol. 4 (Institute of Mathematical Statistics, Beachwood, OH), 253-265.Google Scholar · Zbl 1166.90312
[9] Gromoll HC, Williams RJ (2009) Fluid limits for networks with bandwidth sharing and general document size distributions. Ann. Appl. Probab. 19(1):243-280.Google Scholar · Zbl 1169.60025
[10] Gromoll HC, Puha AL, Williams RJ (2002) The fluid limit of a heavily loaded processor sharing queue. Ann. Appl. Probab. 12(3):797-859.Google Scholar · Zbl 1017.60092
[11] Kelly FP, Williams RJ (2004) Fluid model for a network operating under a fair bandwidth-sharing policy. Ann. Appl. Probab. 14(3):1055-1083.Google Scholar · Zbl 1066.60093
[12] Lee NH (2008) A sufficient condition for stochastic stability of an internet congestion control model in terms of fluid model stability. PhD thesis, Department of Mathematics, University of California, San Diego, San Diego.Google Scholar
[13] Massoulié L (2007) Structural properties of proportional fairness: Stability and insensitivity. Ann. Appl. Probab. 17(3):809-839.Google Scholar · Zbl 1125.60104
[14] Massoulié L, Roberts J (2000) Bandwidth sharing and admission control for elastic traffic. Telecomm. Systems 15(1):185-201.Google Scholar · Zbl 1030.68774
[15] Mo J, Walrand J (2000) Fair end-to-end window-based congestion control. IEEE/ACM Trans. Networks 8(5):556-567.Google Scholar
[16] Paganini F, Tang A, Ferragut A, Andrew LLH (2012) Network stability under alpha fair bandwidth allocation with general file size distribution. IEEE Trans. Automatic Control 57(3):579-591.Google Scholar · Zbl 1369.93700
[17] Puha AL, Williams RJ (2016) Asymptotic behavior of a critical fluid model for a processor sharing queue via relative entropy. Stochastic Systems 6(2):251-300.Link, Google Scholar · Zbl 1359.60113
[18] Ye HQ,
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.