Scheduling Using Interactive Optimization Oracles for Constrained Queueing Networks

References

• Anderson TE, Owicki SS, Saxe JB, Thacker CP (1993) High speed switch scheduling for local area networks. ACM Trans. Comput. Systems 11(4):319–352.Crossref, Google Scholar
• Atalla S, Cuda D, Giaccone P, Pretti M (2010) Belief-propagation assisted scheduling in input-queued switches. Petrini F, Abts D, Brightwell R, Balaji P, Minkenberg C, eds. Proc. IEEE 18th Annual Sympos. High Performance Interconnects, HOTI 2010 (IEEE Computer Society, Washington, DC), 7–14.Crossref, Google Scholar
• Bayati M, Shah D, Sharma M (2008) Max-product for maximum weight matching: Convergence, correctness, and LP duality. IEEE Trans. Inform. Theory 54(3):1241–1251.Crossref, Google Scholar
• Dai JG, Prabhakar B (2000) The throughput of data switches with and without speedup. Proc. Nineteenth Annual Joint Conf. IEEE Comput. Comm. Socieites, INFOCOM 2000 (IEEE. Piscataway, NJ), 556–564.Crossref, Google Scholar
• Dimakis A, Walrand J (2006) Sufficient conditions for stability of longest-queue-first scheduling: Second-order properties using fluid limits. Adv. Appl. Probab. 38(2):505–521.Crossref, Google Scholar
• Edmonds J (1965) Maximum matching and a polyhedron with 0, 1 vertices. J. Res. National Bureau of Standards 69 B:125–130.Crossref, Google Scholar
• Edmonds J (1965) Paths, trees, and flowers. Canadian J. Math. 17:449–467.Crossref, Google Scholar
• Foss S, Konstantopoulos T (2004) An overview of some stochastic stability methods. J. Oper. Res. Soc. Japan 47(4):275–303.Crossref, Google Scholar
• Giaccone P, Prabhakar B, Shah D (2003) Randomized scheduling algorithms for high-aggregate bandwidth switches. IEEE J. Selected Areas in Comm. 21(4):546–559.Crossref, Google Scholar
• Goldberg LA, MacKenzie PD (1996) Analysis of practical backoff protocols for contention resolution with multiple servers. Tardos E, ed. Proc. Seventh Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 554–563.Google Scholar
• Gupta P, Stolyar AL (2006) Optimal throughput allocation in general random-access networks. Proc. 40th Annual Conf. Inform. Sci. Systems, CISS (IEEE, Piscataway, NJ), 1254–1259.Crossref, Google Scholar
• Joo C, Lin X, Shroff NB (2009) Understanding the capacity region of the greedy maximal scheduling algorithm in multihop wireless networks. IEEE/ACM Trans. Networking 17(4):1132–1145.Crossref, Google Scholar
• Jordan MI (2004) Graphical models. Statist. Sci. 19(1):140–155.Crossref, Google Scholar
• Kolmogorov V (2009) Blossom V: A new implementation of a minimum cost perfect matching algorithm. Math. Programming Comput. 1(1):43–67.Crossref, Google Scholar
• Kumar S, Giaccone P, Leonardi E (2002) Rate stability of stable-marriage scheduling algorithms in input-queued switches. Titolo volume non avvalorato.Google Scholar
• Leconte M, Ni J, Srikant R (2009) Improved bounds on the throughput efficiency of greedy maximal scheduling in wireless networks. Proc. 10th ACM Interat. Sympos. Mobile Ad Hoc Networking Comput., MobiHoc ’09 (ACM, New York), 165–174.Crossref, Google Scholar
• Mallows CL, Richter D (1969) Inequalities of Chebyshev type involving conditional expectations. Ann. Math. Statist. 40(6):1922–1932.Crossref, Google Scholar
• Marbach P, Eryilmaz A, Ozdaglar A (2007) Achievable rate region of CSMA schedulers in wireless networks with primary interference constraints. Proc. 46th IEEE Conf. Decision and Control (IEEE, Piscataway, NJ), 1156–1161.Crossref, Google Scholar
• McKeown N (1999) The iSLIP scheduling algorithm for input-queued switches. IEEE/ACM Trans. Networking 7(2):188–201.Crossref, Google Scholar
• Modiano E, Shah D, Zussman G (2006) Maximizing throughput in wireless networks via gossiping. Marie RA, Key PB, Smirni E, eds. Proc. Joint Internat. Conf. Measurement and Modeling Comput. Systems, SIGMETRICS/Performance ’06 (ACM, New York), 27–38.Crossref, Google Scholar
• Rajagopalan S, Shah D, Shin J (2009) Network adiabatic theorem: An efficient randomized protocol for contention resolution. Douceur JR, Greenberg AG, Bonald T, Nieh J, eds. Proc. Eleventh Internat. Joint Conf. Measurement and Modeling Comput. Systems, SIGMETRICS/Performance ’09 (ACM, New York), 133–144.Crossref, Google Scholar
• Sanghavi S, Bui L, Srikant R (2007) Distributed link scheduling with constant overhead. Golubchik L, Ammar MH, Harchol-Balter M, eds. Proc. 2007 ACM SIGMETRICS Internat. Conf. Measurement and Modeling Comput. Systems, SIGMETRICS ’07 (ACM, New York), 313–324.Crossref, Google Scholar
• Sanghavi S, Malioutov DM, Willsky AS (2007) Linear programming analysis of loopy belief propagation for weighted matching. Adv. Neural Inform. Processing Systems 20, Proc. Twenty-First Annual Conf. Neural Inform. Processing Systems 2007, 1273–1280.Google Scholar
• Shah D, Shin J (2012) Randomized scheduling algorithm for queueing networks. Ann. Appl. Probab. 22(1):128–171.Crossref, Google Scholar
• Tassiulas L (1998) Linear complexity algorithms for maximum throughput in radio networks and input queued switches. Proc. Sixteenth Annual Joint Conf. IEEE Comput. Comm. Socieites, INFOCOM ’98 (IEEE. Piscataway, NJ), 533–539.Crossref, 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–1949.Crossref, Google Scholar