Subdiffusive Load Balancing in Time-Varying Queueing Systems

References

• Ananthanarayanan G, Ghodsi A, Shenker S, Stoica I (2013) Effective straggler mitigation: Attack of the clones. NSDI'13 Proc. 10th USENIX Conf. Networked Systems Design Implementation (USENIX Association, Berkeley, CA), 185–198.Google Scholar
• Ananthanarayanan G, Kandula S, Greenberg AG, Stoica I, Lu Y, Saha B, Harris E (2010) Reining in the outliers in map reduce clusters using Mantri. OSDI'10 Proc. 9th USENIX Conf. Operating Systems Design Implementation (USENIX Association, Berkeley, CA), 265–278.Google Scholar
• 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
• Atar R, Saha S (2016) An {{\epsilon}}-Nash equilibrium with high probability for strategic customers in heavy traffic. Math. Oper. Res. 42(3):626–647.Link, Google Scholar
• Baharian G, Tezcan T (2011) Stability analysis of parallel server systems under longest queue first. Math. Methods Oper. Res. 74(2):257–279.Crossref, Google Scholar
• Bertsimas D, Paschalidis IC, Tsitsiklis JN (1998) Asymptotic buffer overflow probabilities in multiclass multiplexers: An optimal control approach. IEEE Trans. Automatic Control 43(3):315–335.Crossref, Google Scholar
• Billingsley P (2013) Convergence of Probability Measures (Wiley, Hoboken, NJ).Google Scholar
• Borst S, Boxma O, Groote JF, Mauw S (2003) Task allocation in a multi server system. J. Scheduling 6(5):423–436.Crossref, Google Scholar
• Bramson M (1998) State space collapse with application to heavy traffic limits for multiclass queueing networks. Queueing Syst. 30(1-2):89–140.Crossref, Google Scholar
• Bramson M, Lu Y, Prabhakar B (2013) Decay of tails at equilibrium for FIFO join the shortest queue networks. Ann. Appl. Probab. 23(5):1841–1878.Crossref, Google Scholar
• Brown L, Gans N, Mandelbaum A, Sakov A, Shen H, Zeltyn S, Zhao L (2005) Statistical analysis of a telephone call center: A queueing-science perspective. J. Amer. Statist. Assoc. 100(469):36–50.Crossref, Google Scholar
• Brutlag J (2009) Speed matters for Google web search. Google Al Blog (June 23), https://ai.googleblog.com/2009/06/speed-matters.html.Google Scholar
• Chen H, Mandelbaum A (1991) Leontief systems, RBVs and RBMs. Davis MHA, Elliott RJ, eds. Applied Stochastic Analysis (Gordon and Breach, New York), 1–43.Google Scholar
• Chen H, Yao DD (2013) Fundamentals of Queueing Networks: Performance, Asymptotics, and Optimization, vol. 46 (Springer Science and Business Media, New York).Google Scholar
• Chen H, Ye HQ (2012) Asymptotic optimality of balanced routing. Oper. Res. 60(1):163–179.Link, Google Scholar
• Čudina M, Ramanan K (2011) Asymptotically optimal controls for time-inhomogeneous networks. SIAM J. Control Optim. 49(2):611–645.Crossref, Google Scholar
• Dean J, Barroso LA (2013) The tail at scale. Comm. ACM 56(2):74–80.Crossref, Google Scholar
• Dean J, Ghemawat S (2008) MapReduce: Simplified data processing on large clusters. Comm. ACM 51(1):107–113.Crossref, Google Scholar
• Durrett R (1999) Essentials of Stochastic Processes, vol. 1 (Springer, New York).Google Scholar
• Eschenfeldt P, Gamarnik D (2016) Supermarket queueing system in the heavy traffic regime. Preprint, submitted October 11, https://arxiv.org/abs/1610.03522.Google Scholar
• Foss S, Chernova N (1998) On the stability of a partially accessible multi station queue with state dependent routing. Queueing Systems 29(1):55–73.Crossref, Google Scholar
• Gardner K, Harchol-Balter M, Scheller-Wolf A, Van Houdt B (2017a) A better model for job redundancy: Decoupling server slowdown and job size. IEEE/ACM Trans. Networking 25(6):3353–3367.Crossref, Google Scholar
• Gardner K, Harchol-Balter M, Scheller-Wolf A, Velednitsky M, Zbarsky S (2017b) Redundancy-d: The power of d choices for redundancy. Oper. Res.65(4):1078–1094.Link, Google Scholar
• Gardner K, Zbarsky S, Doroudi S, Harchol-Balter M, Hyytia E (2015) Reducing latency via redundant requests: Exact analysis. ACM SIGMETRICS Performance Evaluation Rev. 43(1):347–360.Crossref, Google Scholar
• Hampshire RC, Harchol-Balter M, Massey WA (2006) Fluid and diffusion limits for transient sojourn times of processor sharing queues with time varying rates. Queueing Systems 53(1/2):19–30.Crossref, Google Scholar
• He YT, Down DG (2008) Limited choice and locality considerations for load balancing. Performance Evaluation 65(9):670–687.Crossref, Google Scholar
• Honnappa H, Jain R, Ward AR (2014) On transitory queueing. Preprint, submitted December 7, https://arxiv.org/abs/1412.2321.Google Scholar
• Honnappa H, Jain R, Ward AR (2015) A queueing model with independent arrivals, and its fluid and diffusion limits. Queueing Systems 80(1–2):71–103.Crossref, Google Scholar
• Joshi G, Liu Y, Soljanin E (2012) Coding for fast content download. 2012 50th Annual Allerton Conf. Comm. Control Comput. (Allerton) (IEEE, Piscataway, NJ), 326–333.Crossref, Google Scholar
• Joshi G, Liu Y, Soljanin E (2014) On the delay storage trade off in content download from coded distributed storage systems. IEEE J. Selected Areas Comm. 32(5):989–997.Crossref, Google Scholar
• Kandula S, Sengupta S, Greenberg A, Patel P, Chaiken R (2009) The nature of data center traffic: Measurements and analysis. Proc. 9th ACM SIGCOMM Conf. Internet Measurement (ACM, New York), 202–208.Crossref, Google Scholar
• Keller JB (1982) Time-dependent queues. SIAM Rev. 24(4):401–412.Crossref, Google Scholar
• Koole G, Righter R (2008) Resource allocation in grid computing. J. Scheduling 11(3):163–173.Crossref, Google Scholar
• Le LB, Modiano E, Joo C, Shroff NB (2010) Longest-queue-first scheduling under SINR interference model. Proc. 11th ACM Internat. Sympos. Mobile Ad Hoc Networking Comput. (ACM, New York), 41–50.Crossref, Google Scholar
• Li B, Boyaci C, Xia Y (2012) Performance guarantee under longest-queue-first schedule in wireless networks. IEEE Trans. Inform. Theory 58(9):5878–5889.Crossref, Google Scholar
• Lipshutz D, Ramanan K (2016) On directional derivatives of Skorokhod maps in convex polyhedral domains. Preprint, submitted February 4, https://arxiv.org/abs/1602.01860.Google Scholar
• Maguluri ST, Hajek B, Srikant R (2014) The stability of longest-queue-first scheduling with variable packet sizes. IEEE Trans. Automatic Control 59(8):2295–2300.Crossref, Google Scholar
• Mandelbaum A, Massey WA (1995) Strong approximations for time-dependent queues. Math. Oper. Res. 20(1):33–64.Link, Google Scholar
• Mandelbaum A, Ramanan K (2010) Directional derivatives of oblique reflection maps. Math. Oper. Res. 35(3):527–558.Link, Google Scholar
• Massey WA (1981) Non-stationary queues. PhD thesis, Stanford University, Stanford, CA.Google Scholar
• Massey WA (1985) Asymptotic analysis of the time dependent M/M/1 queue. Math. Oper. Res. 10(2):305–327.Google Scholar
• Massey WA, Whitt W (1998) Uniform acceleration expansions for Markov chains with time-varying rates. Ann. Appl. Probab. 8(4):1130–1155.Crossref, Google Scholar
• McDonald DR, Turner SRE (2000) Comparing load balancing algorithms for distributed queueing networks. McDonald DR, Turner SRE, eds. Analysis of Communication Networks: Call Centres, Traffic, and Performance, Fields Institute Communication Series, vol. 28 (American Mathematical Society, Providence, RI), 109–134.Crossref, Google Scholar
• Newell GF (1968a) Queues with time-dependent arrival rates I—The transition through saturation. J. Appl. Probab. 5(2):436–451.Crossref, Google Scholar
• Newell GF (1968b) Queues with time-dependent arrival rates II—The maximum queue and the return to equilibrium. J. Appl. Probab. 5(3):579–590.Crossref, Google Scholar
• Newell GF (1968c) Queues with time-dependent arrival rates III—A mild rush hour. J. Appl. Probab. 5(3):591–606.Crossref, Google Scholar
• Ousterhout K, Wendell P, Zaharia M, Stoica I (2013) Sparrow: Distributed, low latency scheduling. Proc. 24h ACM Sympos. Operating Systems Principles (ACM, New York), 69–84.Crossref, Google Scholar
• Özkan E, Ward AR (2015) On the control of fork-join networks. Preprint, submitted May 17, https://arxiv.org/abs/1505.04470.Google Scholar
• Pedarsani R, Walrand J (2016) Stability of multiclass queueing networks under longest-queue and longest-dominating-queue scheduling. J. Appl. Probab. 53(2):421–433.Crossref, Google Scholar
• Reiman MI (1984) Some diffusion approximations with state space collapse. Baccelli F, Fayolle G, eds. Modelling and Performance Evaluation Methodology (Springer, Berlin), 207–240.Crossref, Google Scholar
• Shah NB, Lee K, Ramchandran K (2012) The MDS queue: Analyzing latency performance of codes and redundant requests. Preprint, submitted November 23, https://arxiv.org/abs/1211.5405.Google Scholar
• Shah NB, Lee K, Ramchandran K (2016) When do redundant requests reduce latency? IEEE Trans. Comm. 64(2):715–722.Crossref, Google Scholar
• Souders S (2009) Velocity and the bottom line. O’Reilly (July 1), http://radar.oreilly.com/2009/07/velocity-making-your-site-fast.html.Google Scholar
• Stolyar AL, Ramanan K (2001) Largest weighted delay first scheduling: Large deviations and optimality. Ann. Appl. Probab. 11(1):1–48.Crossref, Google Scholar
• Torrieri D (2015) Principles of Spread-Spectrum Communication Systems (Springer, New York).Google Scholar
• van der Boor M, Borst SC, van Leeuwaarden JS, Mukherjee D (2018) Scalable load balancing in networked systems: A survey of recent advances. Preprint, submitted June 14, https://arxiv.org/abs/1806.05444.Google Scholar
• Vulimiri A, Godfrey PB, Mittal R, Sherry J, Ratnasamy S, Shenker S (2013) Low latency via redundancy. Proc. 9th ACM Conf. Emerging Networking Experiments Tech. (ACM, New York), 283–294.Crossref, Google Scholar
• Vvedenskaya ND, Dobrushin RLV, Karpelevich FI (1996) Queueing system with selection of the shortest of two queues: An asymptotic approach. Problems Inform. Transmission 32(1):20–34.Google Scholar
• Wan PJ, Xu X, Wang Z, Tang S, Wan Z (2012) Stability analyses of longest-queue-first link scheduling in MC-MR wireless networks. Proc. 13th ACM Internat. Sympos. Mobile Ad Hoc Networking Comput. (ACM, New York), 45–54.Crossref, Google Scholar
• Wang D, Joshi G, Wornell G (2014) Efficient task replication for fast response times in parallel computation. ACM SIGMETRICS Performance Evaluation Rev. 42(1):599–600.Crossref, Google Scholar
• Whitt W (2002) Stochastic-Process Limits: An Introduction to Stochastic-Process Limits and their Application to Queues (Springer Science and Business Media, New York).Crossref, Google Scholar
• Whitt W (2016) Heavy-traffic limits for a single-server queue leading up to a critical point. Oper. Res. Lett. 44(6):796–800.Crossref, Google Scholar
• Williams RJ (1998) Diffusion approximations for open multiclass queueing networks: Sufficient conditions involving state space collapse. Queueing Systems 30(1):27–88.Crossref, Google Scholar
• Xu H, Li B (2014) Repflow: Minimizing flow completion times with replicated flows in data centers. Proc. IEEE INFOCOM 2014 - IEEE Conf. Comput. Comm. (IEEE, Piscataway, NJ), 1581–1589.Crossref, Google Scholar
• Ying L, Srikant R, Eryilmaz A, Dullerud GE (2006) A large deviations analysis of scheduling in wireless networks. IEEE Trans. Inform. Theory 52(11):5088–5098.Crossref, Google Scholar
• Zaharia M, Konwinski A, Joseph AD, Katz RH, Stoica I (2008) Improving MapReduce performance in heterogeneous environments. Proc. 8th USENIX Conf. Operating Systems Design Implementation (USENIX Association, Berkeley, CA), 29–42.Google Scholar