Fluid models of congestion collapse in overloaded switched networks. (English) Zbl 1230.90069

Summary: We consider a switched network (i.e. a queueing network in which there are constraints on which queues may be served simultaneously), in a state of overload. We analyse the behaviour of two scheduling algorithms for multihop switched networks: a generalized version of max-weight, and the \(\alpha \)-fair policy. We show that queue sizes grow linearly with time, under either algorithm, and we characterize the growth rates. We use this characterization to demonstrate examples of congestion collapse, i.e. cases in which throughput drops as the switched network becomes more overloaded. We further show that the loss of throughput can be made arbitrarily small by the max-weight algorithm with weight function \(f(q)=q ^{\alpha }\) as \(\alpha \rightarrow 0\).


90B22 Queues and service in operations research
90B36 Stochastic scheduling theory in operations research
60K25 Queueing theory (aspects of probability theory)
60K30 Applications of queueing theory (congestion, allocation, storage, traffic, etc.)
Full Text: DOI Link


[1] Bonald, T., Massoulie, L.: Impact of fairness on Internet performance. In: Proceedings of ACM Sigmetrics (2001)
[2] Chan, C.W., Armony, M., Bambos, N.: Fairness in overloaded parallel queues. Personal communication (2011) · Zbl 1338.60220
[3] Dai, J.G., Lin, W.: Maximum pressure policies in stochastic processing networks. Oper. Res. 53(2) (2005) · Zbl 1165.90359
[4] Dai, J.G., Lin, W.: Asymptotic optimality of maximum pressure policies in stochastic processing networks. Ann. Appl. Probab. 18(6) (2008) · Zbl 1175.90083
[5] Dai, J.G., Prabhakar, B.: The throughput of switches with and without speed-up. In: Proceedings of IEEE Infocom, pp. 556–564 (2000)
[6] Egorova, R., Borst, S., Zwart, B.: Bandwidth-sharing networks in overload. Perform. Eval. 64, 978–993 (2007) · Zbl 1303.60081 · doi:10.1016/j.peva.2007.06.024
[7] Georgiadis, L., Tassiulas, L.: Optimal overload response in sensor networks. IEEE Trans. Inf. Theory 52(6), 2684–2696 (2006) · Zbl 1300.94010 · doi:10.1109/TIT.2006.874401
[8] Gromoll, H.C., Williams, R.J.: Fluid limits for networks with bandwidth sharing and general document size distributions. Ann. Appl. Probab. 19(1) (2009) · Zbl 1169.60025
[9] Harrison, J.M., Zeevi, A.: A method for staffing large call centers based on stochastic fluid models. Manuf. Serv. Oper. Manag. (2005)
[10] Jacobson, V.: Congestion avoidance and control. In: Proceedings of SIGCOMM (1988)
[11] Kelly, F.P., Williams, R.J.: Fluid model for a network operating under a fair bandwidth-sharing policy. Ann. Appl. Probab. 14, 1055–1083 (2004) · Zbl 1066.60093 · doi:10.1214/105051604000000224
[12] Klemm, F., Boudec, J.Y.L., Aberer, K.: Congestion control for distributed hash tables. In: IEEE Symposium on Network Computing and Applications. http://doi.ieeecomputersociety.org/10.1109/NCA.2006.19 (2006)
[13] Mo, J., Walrand, J.: Fair end-to-end windows-based congestion control. IEEE/ACM Trans. Netw. 8(5), 556–567 (2000) · doi:10.1109/90.879343
[14] Roberts, J., Massoulie, L.: Bandwidth sharing and admission control for elastic traffic. Telecommun. Syst. 15, 185–201 (2000) · Zbl 1030.68774 · doi:10.1023/A:1019138827659
[15] Shah, D., Wischik, D.: Switched networks with maximum weight policies: fluid approximation and multiplicative state space collapse. Ann. Appl. Probab. (2011, to appear) · Zbl 1242.90066
[16] Tassiulas, L., Ephremides, A.: Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Trans. Autom. Control 37, 1936–1948 (1992) · Zbl 0771.60070 · doi:10.1109/9.182479
[17] Venkataramanan, V.J., Lin, X.: Structural properties of LDP for queue-length based wireless scheduling algorithms. In: Proceedings of Allerton (2007)
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.