Delay Analysis of the Max-Weight Policy Under Heavy-Tailed Traffic via Fluid Approximations

References

• Andrews M, Zhang L (2003) Achieving stability in networks of input-queued switches. IEEE/ACM Trans. Networking 11(5):848–857.Crossref, Google Scholar
• Avrachenkov K, Ayesta U, Brown P, Nunez-Queija R (2005) Discriminatory processor sharing revisited. Proc. 24th Annual Joint Conf. IEEE Comput. Comm. Societies, INFOCOM ’05 (IEEE, Piscataway, NJ), 784–795.Crossref, Google Scholar
• Baccelli F, Foss S (2004) Moments and tails in monotone-separable stochastic networks. Ann. Appl. Probab. 14(2):612–650.Crossref, Google Scholar
• Baccelli F, Foss S, Lelarge M (2005) Tails in generalized Jackson networks with subexponential service-time distributions. J. Appl. Probab. 42(2):513–530.Crossref, Google Scholar
• Bertsimas D, Gamarnik D, Tsitsiklis JN (2001) Performance of multiclass Markovian queueing networks via piecewise linear Lyapunov functions. Ann. Appl. Probab. 11(4):1384–1428.Crossref, Google Scholar
• Borovkov AA (1970) Factorization identities and properties of the distribution of the supremum of sequential sums. Theory Probab. Appl. 15(3):359–402.Crossref, Google Scholar
• Borst SC, Zwart AP (2005) Fluid queues with heavy-tailed M/G/∞ input. Math. Oper. Res. 30(4):852–879.Link, Google Scholar
• Borst SC, Boxma OJ, Jelenkovic PR (2003a) Reduced-load equivalence and induced burstiness in GPS queues with long-tailed traffic flows. Queueing Systems 43(4):273–306.Crossref, Google Scholar
• Borst SC, Mandjes M, Van Uitert MJG (2003c) Generalized processor sharing with light-tailed and heavy-tailed input. IEEE/ACM Trans. Networking 11(5):821–834.Crossref, Google Scholar
• Borst SC, Nunez-Queija R, Zwart AP (2006) Sojourn time asymptotics in processor-sharing queues. Queueing Systems 53(1):31–51.Crossref, Google Scholar
• Borst SC, Van Ooteghem DTMB, Zwart AP (2005) Tail asymptotics for discriminatory processor-sharing queues with heavy-tailed service requirements. Performance Evaluation 61(2–3):281–298.Crossref, Google Scholar
• Borst SC, Boxma OJ, Nunez-Queija R, Zwart AP (2003b) The impact of the service discipline on delay asymptotics. Performance Evaluation 54(2):175–206.Crossref, Google Scholar
• Boxma OJ, Dumas V (1998) Fluid queues with long-tailed activity period distributions. Comput. Comm. 21(17):1509–1529.Crossref, Google Scholar
• Boxma OJ, Deng Q, Zwart AP (2002) Waiting-time asymptotics for the M/G/2 queue with heterogeneous servers. Queueing Systems 40(1):5–31.Crossref, Google Scholar
• Bramson M (2008) Stability of queueing networks. Probab. Surveys 5:169–345.Crossref, Google Scholar
• Bramson M, D’Auria B, Walton N (2016) Instability of max-weight in multi-hop networks. Working paper, University of Minnesota.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. Networking 19(6):1597–1609.Crossref, Google Scholar
• Cohen JW (1973) Some results on regular variation for distributions in queueing and fluctuation theory. J. Appl. Probab. 10(2):343–353.Crossref, Google Scholar
• 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.Crossref, Google Scholar
• Dai JG, Lin W (2005) Maximum pressure policies in stochastic processing networks. Oper. Res. 53(2):197–218.Link, Google Scholar
• D’Auria B, Samorodnitsky G (2005) Limit behavior of fluid queues and networks. Oper. Res. 53(6):933–945.Link, Google Scholar
• Down D, Meyn SP (1997) Piecewise linear test functions for stability and instability of queueing networks. Queueing Systems 27(3–4):205–226.Crossref, Google Scholar
• Ersoz D, Yousif M, Das C (2007) Characterizing network traffic in a cluster-based, multi-tier data center. Proc. 27th IEEE Internat. Conf. Distributed Comput. Systems, ICDCS ’07 (IEEE Computer Society, Washington, DC).Crossref, Google Scholar
• Fisher M, Raman A (1996) Reducing the cost of demand uncertainty through accurate response to early sales. Oper. Res. 44(1):87–99.Link, Google Scholar
• Foss S, Korshunov D (2012) On large delays in multi-server queues with heavy tails. Math. Oper. Res. 37(2):201–218.Link, Google Scholar
• Gamarnik D, Katz D (2009) On deciding stability of multiclass queueing networks under buffer priority scheduling policies. Ann. Appl. Probab. 19(5):2008–2037.Crossref, Google Scholar
• Gans N, Van Ryzin G (1997) Optimal control of a multi-class, flexible queueing system. Oper. Res. 45(5):677–693.Link, Google Scholar
• Ganti A, Modiano E, Tsitsiklis JN (2007) Optimal transmission scheduling in symmetric communication models with intermittent connectivity. IEEE Trans. Inform. Theory 53(3):998–1008.Crossref, Google Scholar
• Georgiadis L, Neely M, Tassiulas L (2006) Resource allocation and cross-layer control in wireless networks. Foundations and Trends in Networking 1(1):1–144.Crossref, Google Scholar
• Gut A (2005) Probability: A Graduate Course. (Springer, New York).Google Scholar
• Hajek B (1982) Hitting-time and occupation-time bounds implied by drift analysis with applications. Adv. Appl. Probab. 14(3):502–525.Crossref, Google Scholar
• Harrison JM (2000) Brownian models of open processing networks: Canonical representation of workload. Ann. Appl. Probab. 10(1):75–103.Crossref, Google Scholar
• Jagannathan K, Markakis MG, Modiano E, Tsitsiklis JN (2012) Queue-length asymptotics for generalized max-weight scheduling in the presence of heavy-tailed traffic. IEEE/ACM Trans. Networking 20(4):1096–1111.Crossref, Google Scholar
• Jelenkovic PR, Lazar AA (1999) Asymptotic results for multiplexing subexponential on-off processes. Adv. Appl. Probab. 31(2):394–421.Crossref, Google Scholar
• Jelenkovic PR, Momcilovic P (2002) Finite buffer queue with generalized processor sharing and heavy-tailed input processes. Comput. Networks 40(3):433–443.Crossref, Google Scholar
• Jelenkovic PR, Momcilovic P (2003) Large deviation analysis of subexponential waiting times in a processor sharing queue. Math. Oper. Res. 28(3):587–608.Link, Google Scholar
• Ji B, Joo C, Shroff NB (2013a) Delay-based back-pressure scheduling in multihop wireless networks. IEEE/ACM Trans. Networking 21(5):1539–1552.Crossref, Google Scholar
• Ji B, Joo C, Shroff NB (2013b) Throughput-optimal scheduling in multihop wireless networks without per-flow information. IEEE/ACM Trans. Networking 21(2):634–647.Crossref, Google Scholar
• Kotopoulos C, Likhanov N, Mazumdar RR (2001) Asymptotic analysis of the GPS system fed by heterogeneous long-tailed sources. Proc. 20th Annual Joint Conf. IEEE Comput. Comm. Societies, INFOCOM ’05 (IEEE, Piscataway, NJ), 299–308.Crossref, Google Scholar
• Kumar PR, Seidman T (1990) Dynamic instabilities and stabilization methods in distributed real-time scheduling of manufacturing systems. IEEE Trans. Automatic Control 35(3):289–298.Crossref, Google Scholar
• Lelarge M (2009) Asymptotic behavior of generalized processor sharing queues under subexponential assumptions. Queueing Systems 62(1–2):51–73.Crossref, Google Scholar
• Likhanov N, Mazumdar RR (2000) Loss asymptotics in large buffers fed by heterogeneous long-tailed sources. Adv. Appl. Probab. 32(4):1168–1189.Crossref, Google Scholar
• Liu J, Stolyar A, Chiang M, Poor HV (2009) Queue back-pressure random access in multi-hop wireless networks: Optimality and stability. IEEE Trans. Inform. Theory 55(9):4087–4098.Crossref, Google Scholar
• Maguluri ST, Srikant R, Ying L (2012) Stochastic models of load balancing and scheduling in cloud computing clusters. Greenberg AG, Sohraby K, eds. Proc. 31st Annual IEEE Internat. Conf. Comput. Comm., INFOCOM ’12 (IEEE, Piscataway, NJ), 702–710.Crossref, Google Scholar
• Markakis MG (2013) Scheduling in switched queueing networks with heavy-tailed traffic. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA.Google Scholar
• Markakis MG, Modiano E, Tsitsiklis JN (2014) Max-weight scheduling in queueing networks with heavy-tailed traffic. IEEE/ACM Trans. Networking 22(1):257–270.Crossref, Google Scholar
• Markakis MG, Modiano E, Tsitsiklis JN (2016) Delay stability of back-pressure policies in the presence of heavy-tailed traffic. IEEE/ACM Trans. Networking 24(4):2046–2059.Crossref, Google Scholar
• McKeown N, Mekkittikul A, Anantharam V, Walrand J (1999) Achieving 100% throughput in an input-queued switch. IEEE Trans. Comm. 47(8):1260–1267.Crossref, Google Scholar
• Neely MJ (2008) Order optimal delay for opportunistic scheduling in multi-user wireless uplinks and downlinks. IEEE/ACM Trans. Networking 16(5):1188–1199.Crossref, Google Scholar
• Nunez-Queija R (2002) Queues with equally heavy sojourn time and service requirement distributions. Ann. Oper. Res. 113(1):101–117.Crossref, Google Scholar
• Pakes AG (1975) On the tails of waiting-time distributions. J. Appl. Probab. 12(3):555–564.Crossref, Google Scholar
• Park K, Willinger W (2000) Self-similar network traffic: An overview. Self-Similar Network Traffic and Performance Evaluation (John Wiley & Sons, New York), 1–38.Crossref, Google Scholar
• Rege KM, Sengupta B (1994) A decomposition theorem and related results for the discriminatory processor sharing queue. Queueing Systems 18(3):333–351.Crossref, Google Scholar
• Resnick S, Samorodnitsky G (1999) Activity periods of an infinite server queue and performance of certain heavy tailed fluid queues. Queueing Systems 33(1):43–71.Crossref, Google Scholar
• Rybko A, Stolyar A (1992) Ergodicity of stochastic processes describing the operation of open queueing networks. Problems Inform. Transmission 28(3):199–220.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
• Shah D, Tsitsiklis JN, Zhong Y (2010) Qualitative properties of α-weighted scheduling policies. Misra V, Barford P, Squillante MS, eds. Proc. ACM SIGMETRICS Internat. Conf. Measurement Modeling Comput. Systems, SIGMETRICS ’10 (ACM, New York), 239–250.Crossref, Google Scholar
• Sharifnassab A (2016) Sharif University, Iran. Personal communication with the authors, October 12, 2016.Google Scholar
• Sigman K, Wolff R (1993) A review of regenerative processes. SIAM Rev. 35(2):269–288.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
• Subramanian V (2010) Large deviations of max-weight scheduling policies on convex rate regions. Math. Oper. Res. 35(4):881–910.Link, Google Scholar
• Tassiulas L, Ephremides A (1992) Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Trans. Automatic Control 37(12):1936–1948.Crossref, Google Scholar
• Tsitsiklis JN (1987) Analysis of a multiaccess control scheme. IEEE Trans. Automatic Control 32(11):1017–1020.Crossref, Google Scholar
• Van Uitert MJG, Borst SC (2002) A reduced-load equivalence for generalised processor sharing networks with long-tailed input flows. Queueing Systems 41(1):123–163.Crossref, Google Scholar
• Venkataraman VJ, Lin X, Ying L, Shakkottai S (2010) On scheduling for minimizing end-to-end buffer usage over multihop wireless networks. Proc. 29th IEEE Internat. Conf. Comput. Comm., INFOCOM ’10 (IEEE, Piscataway, NJ), 2847–2855.Google Scholar
• Veraverbeke N (1977) Asymptotic behaviour of Wiener-Hopf factors of a random walk. Stochastic Processes and Their Appl. 5(1):27–37.Crossref, Google Scholar
• Williams D (1991) Probability with martingales (Cambridge University Press, New York).Crossref, Google Scholar
• Zwart AP, Boxma OJ (2000) Sojourn time asymptotics in the M/G/1 processor sharing queue. Queueing Systems 35(1):141–166.Crossref, Google Scholar
• Zwart AP, Borst SC, Mandjes M (2004) Exact asymptotics for fluid queues fed by multiple heavy-tailed on-off flows. Ann. Appl. Probab. 14(2):903–957.Crossref, Google Scholar