Proportional Switching in First-in, First-out Networks

References

• Andrews M, Kumaran K, Ramanan K, Stolyar A, Vijayakumar R, Whiting P (2004) Scheduling in a queuing system with asynchronously varying service rates. Probab. Engrg. Inform. Sci. 18(2):191–217.Crossref, Google Scholar
• Andrews M, Zhang L (2003) Achieving stability in networks of input-queued switches. Networking, IEEE/ACM Trans. 11(5):848–857.Crossref, Google Scholar
• Anselmi J, D’Auria B, Walton N (2013) Closed queueing networks under congestion: Nonbottleneck independence and bottleneck convergence. Math. Oper. Res. 38(3):469–491.Link, Google Scholar
• Appenzeller G, Keslassy I, McKeown N (2004) Sizing router buffers. Yavatkar R, Zegura EW, Rexford J, eds. Proc. ACM SIGCOMM 2004 Conf. (ACM, New York), 281–292.Crossref, Google Scholar
• Armony M, Bambos N (2003) Queueing dynamics and maximal throughput scheduling in switched processing systems. Queueing Systems 44(3):209–252.Crossref, Google Scholar
• Baskett F, Chandy K, Muntz R, Palacios F (1975) Open, closed, and mixed networks of queues with different classes of customers. J. ACM 22(2):248–260.Crossref, Google Scholar
• Billingsley P (1999) Convergence of Probability Measures (John Wiley & Sons, New York).Crossref, Google Scholar
• Bonald T, Massoulié L (2001) Impact of fairness on Internet performance. Vernon MK, ed. Proc. 2001 ACM Sigmetrics Internat. Conf. Measurement Modeling Comput. Systems ACM, New York), 82–91.Crossref, Google Scholar
• Bonald T, Proutière A (2002) Insensitivity in processor-sharing networks. Performance Evaluation 49(1–4):193–203.Crossref, Google Scholar
• Bonald T, Proutière A (2003) Insensitive bandwidth sharing in data networks. Queueing Systems 44(1):69–100.Crossref, Google Scholar
• Bonald T, Proutière A (2004) On performance bounds for balanced fairness. Performance Evaluation 55(1–2):25–50.Crossref, Google Scholar
• Borodin A, Kleinberg J, Raghavan P, Sudan M, Williamson D (2001) Adversarial queuing theory. J. ACM 48(1):13–38.Crossref, Google Scholar
• Bramson M (1994) Instability of FIFO queueing networks. Ann. Appl. Probab. 4(2):414–431.Crossref, Google Scholar
• Bramson M (1996) Convergence to equilibria for fluid models of FIFO queueing networks. Queueing Systems Theory Appl. 22(1–2):5–45.Crossref, Google Scholar
• Bramson M (2008) Stability of queueing networks. Probab. Surv. 5: 169–345.Crossref, Google Scholar
• Bui L, Srikant R, Stolyar A (2011) A novel architecture for reduction of delay and queueing structure complexity in the back-pressure algorithm. IEEE/ACM Trans. Netw. 19(6):1597–1609.Crossref, Google Scholar
• Burke P (1956) The output of a queuing system. Oper. Res. 4(6):699–704.Link, Google Scholar
• Dai J (1995) On positive Harris recurrence of multiclass queueing networks: A unified approach via fluid limit models. Ann. Appl. Probab. 5(1):49–77.Crossref, Google Scholar
• Dai J, Lin W (2005) Maximum pressure policies in stochastic processing networks. Oper. Res. 53(2):197–218.Link, Google Scholar
• De Veciana G, Lee T, Konstantopoulos T (1999) Stability and performance analysis of networks supporting services with rate control—Could the Internet be unstable? IEEE/ACM Trans. Networking 9(1):2–14.Crossref, Google Scholar
• Dieker A, Shin J (2013) From local to global stability in stochastic processing networks through quadratic Lyapunov functions. Math. Oper. Res. 38(4):638–664.Link, Google Scholar
• Eryilmaz A, Srikant R, Perkins J (2005) Stable scheduling policies for fading wireless channels. Networking, IEEE/ACM Trans. 13(2): 411–424.Crossref, Google Scholar
• Georgiadis L, Neely M, Tassiulas L (2006) Resource Allocation and Cross-Layer Control in Wireless Networks (Now Publishers, Boston).Google Scholar
• Gromoll H, Williams R (2009) Fluid limits for networks with bandwidth sharing and general document size distributions. Ann. Appl. Probab. 19(1):243–280.Crossref, Google Scholar
• Harrison J, Mandayam C, Shah D, Yang Y (2014) Resource sharing nertworks: Overview and an open problem. Stochastic Systems 4(2): 524–555.Link, Google Scholar
• Hsu J, Burke P (1976) Behavior of tandem buffers with geometric input and Markovian output. Comm., IEEE Trans. 24(3):358–361.Crossref, Google Scholar
• Jackson J (1963) Jobshop-like queueing systems. Management Sci. 10(1): 131–142.Link, Google Scholar
• Jagannathan K, Markakis M, Modiano E, Tsitsiklis J (2011) Queue length asymptotics for generalized max-weight scheduling in the presence of heavy-tailed traffic. Proc. 30th IEEE Internat. Conf. Comput. Communications, INFOCOM, ’11 (IEEE, Piscataway, NJ), 2318–2326.Crossref, Google Scholar
• Ji B, Joo C, Shroff N (2013) Throughput-optimal scheduling in multihop wireless networks without per-flow information. Networking, IEEE/ACM Trans. 21(2):634–647.Crossref, Google Scholar
• Jonckheere M, López S (2014) Large deviations for the stationary measure of networks under proportional fair allocations. Math. Oper. Res. 39(2):418–431.Link, Google Scholar
• Kang W, Kelly F, Lee N, Williams R (2007) Product form stationary distributions for diffusion approximations to a flow level model operating under a proportional fair sharing policy. Performance Evaluation Rev. 35 (2):36–38.Crossref, Google Scholar
• Kang W, Kelly F, Lee N, Williams RJ (2009) State space collapse and diffusion approximation for a network operating under a fair bandwidth sharing policy. Ann. Appl. Probab. 19 (5):1719–1780.Crossref, Google Scholar
• Kannan R, Krueger C (1996) Advanced Analysis: On the Real Line, Universitext Series (Springer, New York).Crossref, Google Scholar
• Kelly F (1975) Networks of queues with customers of different types. J. Appl. Probab. 12(3):542–554.Crossref, Google Scholar
• Kelly F (1979) Reversibility and Stochastic Networks (John Wiley & Sons, Chicester, UK).Google Scholar
• Kelly FP (1989) On a class of approximations for closed queueing networks. Queueing Systems 4(1):69–76.Crossref, Google Scholar
• Kelly F (1997) Charging and rate control for elastic traffic. Eur. Trans. Telecommunications 8(1):33–37.Crossref, Google Scholar
• Kelly F, Williams R (2004) Fluid model for a network operating under a fair bandwidth-sharing policy. Ann. Appl. Probab. 14(3):1055–1083.Crossref, Google Scholar
• Kelly F, Massoulié L, Walton N (2009) Resource pooling in congested networks: Proportional fairness and product form. Queueing Systems 63(1–4):165–194.Crossref, Google Scholar
• Kushner H, Whiting P (2004) Convergence of proportional-fair sharing algorithms under general conditions. Wireless Comm., IEEE Trans. 3(4):1250–1259.Crossref, Google Scholar
• Li B, Srikant R (2016) Queue-proportional rate allocation with per-link information in multihop wireless networks. Queueing Systems 83(3):329–359.Crossref, Google Scholar
• Lu SH, Kumar P (1991) Distributed scheduling based on due dates and buffer priorities. Automatic Control, IEEE Trans. 36(12):1406–1416.Crossref, Google Scholar
• Mandelbaum A, Stolyar A (2004) Scheduling flexible servers with convex delay costs: Heavy-traffic optimality of the generalized cμ-rule. Oper. Res. 52(6):836–855.Link, Google Scholar
• Markakis MG, Modiano E, Tsitsiklis JN (2014) Max-weight scheduling in queueing networks with heavy-tailed traffic. IEEE/ACM Trans. Networking (TON) 22(1):257–270.Crossref, Google Scholar
• Massoulié L (2007) Structural properties of proportional fairness: Stability and insensitivity. Ann. Appl. Probab. 17(3):809–839.Crossref, Google Scholar
• Massoulié L, Roberts J (1999) Bandwidth sharing: Objectives and algorithms. IEEE Infocom 1999 10(3):320–328.Google Scholar
• Massoulié L, Roberts JW (2000) Bandwidth sharing and admission control for elastic traffic. Telecommunication Systems 15(1–2):185–201.Crossref, Google Scholar
• McKeown N (1999) The Islip scheduling algorithm for input-queued switches. Networking, IEEE/ACM Trans. 7(2):188–201.Crossref, Google Scholar
• McKeown N, Mekkittikul A, Anantharam V, Walrand J (1999) Achieving 100% throughput in an input-queued switch. Comm., IEEE Trans. 47(8):1260–1267.Crossref, Google Scholar
• Meyn S (2009) Stability and asymptotic optimality of generalized maxweight policies. SIAM J. Control Optim. 47(6):3259–3294.Crossref, Google Scholar
• Mo J, Walrand J (2000) Fair end-to-end window-based congestion control. IEEE/ACM Trans. Networking (ToN) 8(5):556–567.Crossref, Google Scholar
• Paganini F, Tang A, Ferragut A, Andrew L (2012) Network stability under alpha fair bandwidth allocation with general file size distribution. Automatic Control, IEEE Trans. 57(3):579–591.Crossref, Google Scholar
• Rybko A, Stolyar A (1992) Ergodicity of stochastic processes describing the operation of open queueing networks. Problemy Peredachi Informatsii 28(3):3–26.Google Scholar
• Schweitzer P (1979) Approximate analysis of multiclass closed networks of queues. Proc. Internat. Conf. Stochastic Control Optim. (Free University, Amsterdam).Google Scholar
• Shah D, Wischik D (2011) Fluid models of congestion collapse in overloaded switched networks. Queueing Syst. 69(2):121–143.Crossref, Google Scholar
• Shah D, Wischik D (2012) Switched networks with maximum weight policies: Fluid approximation and multiplicative state space collapse. Ann. Appl. Probab. 22(1):70–127.Crossref, Google Scholar
• Stolyar A (2004) Maxweight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic. Ann. Appl. Probab. 14(1):1–53.Crossref, Google Scholar
• Stolyar A (2011) Large number of queues in tandem: Scaling properties under back-pressure algorithm. Queueing Syst. Theory Appl. 67(2):111–126.Crossref, Google Scholar
• Tassiulas L, Ephremides A (1992) Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. Automatic Control, IEEE Trans. 37(12):1936–1948.Crossref, Google Scholar
• Varaiya P (2013) Max pressure control of a network of signalized intersections. Transportation Res. Part C: Emerging Tech. 36(November):177–195.Crossref, Google Scholar
• Venkataramanan V, Lin X (2007) Structural properties of LDP for queue-length based wireless scheduling algorithms. Proc. 45th Annual Allerton Conf Comm., Control, Comput. Monticello, IL, 759–766.Google Scholar
• Viswanath P, Tse D, Laroia R (2002) Opportunistic beamforming using dumb antennas. Inform. Theory, IEEE Trans. 48(6):1277–1294.Crossref, Google Scholar
• Vlasiou M, Zhang J, Zwart B (2014) Insensitivity of proportional fairness in critically loaded bandwidth sharing networks,. Preprint, arXiv: 1411.4841v2.Google Scholar
• Walton N (2011) Insensitive, maximum stable allocations converge to proportional fairness. Queueing Systems 68 (1):51–60.Crossref, Google Scholar
• Walton NS (2009) Proportional fairness and its relationship with multi-class queueing networks. Ann. Appl. Probab. 22(6):2301–2333.Crossref, Google Scholar
• Whittle P (1985) Partial balance and insensitivity. J. Appl. Probab. 22(1): 168–176.Crossref, Google Scholar
• Williams D (1991) Probability with Martingales (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Ye HQ, Yao D (2012) A stochastic network under proportional fair resource control-diffusion limit with multiple bottlenecks. Oper. Res. 60(3):716–738.Link, Google Scholar
• Ye HQ, Ou J, Yuan XM (2005) Stability of data networks: Stationary and bursty models. Oper. Res. 53(1):107–125.Link, Google Scholar
• Ying L, Srikant R, Towsley D, Liu S (2011) Cluster-based back-pressure routing algorithm. Networking, IEEE/ACM Trans. 19(6):1773–1786.Crossref, Google Scholar
• Zachary S (2007) A note on insensitivity in stochastic networks. J. Appl. Probab. 44(1):238–248.Crossref, Google Scholar
• Zhong Y (2012) Resource allocation in stochastic processing networks: Performance and scaling. Ph.D. thesis, MIT, Cambridge, MA.Google Scholar