Document Open Access Logo

Online and Offline Algorithms for Circuit Switch Scheduling

Authors Roy Schwartz, Mohit Singh, Sina Yazdanbod

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2019.27.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Author Details

Roy Schwartz
  • Technion - Israel Institute of Technology, Haifa, Israel
Mohit Singh
  • Georgia Institute of Technology, Atlanta, GA, USA
Sina Yazdanbod
  • Georgia Institute of Technology, Atlanta, GA, USA

Funding

  • Schwartz, Roy: Research is supported by NSF-BSF grant 2016742.
  • Singh, Mohit: Research is supported by NSF- AF:1910423 and NSF-AF:1717947.

Cite As Get BibTex

Roy Schwartz, Mohit Singh, and Sina Yazdanbod. Online and Offline Algorithms for Circuit Switch Scheduling. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.FSTTCS.2019.27

Abstract

Motivated by the use of high speed circuit switches in large scale data centers, we consider the problem of circuit switch scheduling. In this problem we are given demands between pairs of servers and the goal is to schedule at every time step a matching between the servers while maximizing the total satisfied demand over time. The crux of this scheduling problem is that once one shifts from one matching to a different one a fixed delay delta is incurred during which no data can be transmitted.
For the offline version of the problem we present a (1-(1/e)-epsilon) approximation ratio (for any constant epsilon >0). Since the natural linear programming relaxation for the problem has an unbounded integrality gap, we adopt a hybrid approach that combines the combinatorial greedy with randomized rounding of a different suitable linear program. For the online version of the problem we present a (bi-criteria) ((e-1)/(2e-1)-epsilon)-competitive ratio (for any constant epsilon >0 ) that exceeds time by an additive factor of O(delta/epsilon). We note that no uni-criteria online algorithm is possible. Surprisingly, we obtain the result by reducing the online version to the offline one.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
  • Theory of computation → Scheduling algorithms
Keywords
  • approximation algorithm
  • online
  • matching
  • scheduling

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Nir Andelman and Yishay Mansour. Auctions with budget constraints. In Scandinavian Workshop on Algorithm Theory, pages 26-38, 2004. Google Scholar
  2. Ashwinkumar Badanidiyuru and Jan Vondrák. Fast algorithms for maximizing submodular functions. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 1497-1514, 2014. Google Scholar
  3. Siddharth Barman. Approximating Nash Equilibria and Dense Bipartite Subgraphs via an Approximate Version of Caratheodory’s Theorem. In Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing, STOC '15, pages 361-369, 2015. Google Scholar
  4. G Celik, Sem C Borst, Philip A Whiting, and Eytan Modiano. Dynamic scheduling with reconfiguration delays. Queueing Systems, 83(1-2):87-129, 2016. Google Scholar
  5. Cheng-Shang Chang, Wen-Jyh Chen, and Hsiang-Yi Huang. On service guarantees for input-buffered crossbar switches: a capacity decomposition approach by Birkhoff and von Neumann. In 1999 Seventh International Workshop on Quality of Service (IWQoS'99), pages 79-86, 1999. Google Scholar
  6. K. Chen, A. Singla, A. Singh, K. Ramachandran, L. Xu, Y. Zhang, X. Wen, and Y. Chen. OSA: An Optical Switching Architecture for Data Center Networks With Unprecedented Flexibility. IEEE/ACM Transactions on Networking, 22(2):498-511, 2014. Google Scholar
  7. Abel Dasylva and R Srikant. Optimal WDM schedules for optical star networks. IEEE/ACM Transactions on Networking, 7(3):446-456, 1999. Google Scholar
  8. Fanny Dufossé, Kamer Kaya, Ioannis Panagiotas, and Bora Uçar. Further notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices. Linear Algebra and its Applications, 554:68-78, 2018. Google Scholar
  9. Alina Ene and Huy L. Nguyen. A Nearly-linear Time Algorithm for Submodular Maximization with a Knapsack Constraint. CoRR, abs/1709.09767, 2017. URL: http://arxiv.org/abs/1709.09767.
  10. Nathan Farrington, George Porter, Sivasankar Radhakrishnan, Hamid Hajabdolali Bazzaz, Vikram Subramanya, Yeshaiahu Fainman, George Papen, and Amin Vahdat. Helios: a hybrid electrical/optical switch architecture for modular data centers. ACM SIGCOMM Computer Communication Review, 40(4):339-350, 2010. Google Scholar
  11. Shu Fu, Bin Wu, Xiaohong Jiang, Achille Pattavina, Lei Zhang, and Shizhong Xu. Cost and delay tradeoff in three-stage switch architecture for data center networks. In 2013 IEEE 14th International Conference on High Performance Switching and Routing (HPSR), pages 56-61, 2013. Google Scholar
  12. Leonidas Georgiadis, Michael J Neely, Leandros Tassiulas, et al. Resource allocation and cross-layer control in wireless networks. Foundations and Trendsregistered in Networking, 1(1):1-144, 2006. Google Scholar
  13. Navid Hamedazimi, Zafar Qazi, Himanshu Gupta, Vyas Sekar, Samir R Das, Jon P Longtin, Himanshu Shah, and Ashish Tanwer. Firefly: A reconfigurable wireless data center fabric using free-space optics. In ACM SIGCOMM Computer Communication Review, volume 44 (4), pages 319-330, 2014. Google Scholar
  14. Thomas Inukai. An efficient SS/TDMA time slot assignment algorithm. IEEE Transactions on Communications, 27(10):1449-1455, 1979. Google Scholar
  15. Srikanth Kandula, Jitendra Padhye, and Victor Bahl. Flyways to DeCongest Data Center Networks. Proc. of Hot Nets, 2009. Google Scholar
  16. Samir Khuller, Anna Moss, and Joseph Seffi Naor. The budgeted maximum coverage problem. Information processing letters, 70(1):39-45, 1999. Google Scholar
  17. Janardhan Kulkarni, Euiwoong Lee, and Mohit Singh. Minimum Birkhoff-von Neumann Decomposition. In International Conference on Integer Programming and Combinatorial Optimization, pages 343-354, 2017. Google Scholar
  18. Conglong Li, Matthew K. Mukerjee, David G. Andersen, Srinivasan Seshan, Michael Kaminsky, George Porter, and Alex C. Snoeren. Using Indirect Routing to Recover from Network Traffic Scheduling Estimation Error. In Proceedings of the Symposium on Architectures for Networking and Communications Systems, ANCS '17, pages 13-24, 2017. Google Scholar
  19. Xin Li and Mounir Hamdi. On scheduling optical packet switches with reconfiguration delay. IEEE Journal on Selected Areas in Communications, 21(7):1156-1164, 2003. Google Scholar
  20. He Liu, Matthew K Mukerjee, Conglong Li, Nicolas Feltman, George Papen, Stefan Savage, Srinivasan Seshan, Geoffrey M Voelker, David G Andersen, Michael Kaminsky, et al. Scheduling techniques for hybrid circuit/packet networks. In Proceedings of the 11th ACM Conference on Emerging Networking Experiments and Technologies, page 41, 2015. Google Scholar
  21. Liang Liu, Long Gong, Sen Yang, Jun Xu, and Lance Fortnow. Better Algorithms for Hybrid Circuit and Packet Switching in Data Centers. arXiv preprint, 2017. URL: http://arxiv.org/abs/1712.06634.
  22. Vahab Mirrokni, Renato Paes Leme, Adrian Vladu, and Sam Chiu wai Wong. Tight Bounds for Approximate Carathéodory and Beyond. In Proceedings of the 34th International Conference on Machine Learning, volume 70, pages 2440-2448, 2017. Google Scholar
  23. Roy Schwartz, Mohit Singh, and Sina Yazdanbod. Online and Offline Greedy Algorithms for Routing with Switching Costs. arXiv preprint, 2019. URL: http://arxiv.org/abs/1905.02800.
  24. Maxim Sviridenko. A note on maximizing a submodular set function subject to a knapsack constraint. Operations Research Letters, 32(1):41-43, 2004. Google Scholar
  25. Brian Towles and William J Dally. Guaranteed scheduling for switches with configuration overhead. IEEE/ACM Transactions on Networking, 11(5):835-847, 2003. Google Scholar
  26. Shay Vargaftik, Katherine Barabash, Yaniv Ben-Itzhak, Ofer Biran, Isaac Keslassy, Dean Lorenz, and Ariel Orda. Composite-path switching. In Proceedings of the 12th International on Conference on emerging Networking Experiments and Technologies, pages 329-343, 2016. Google Scholar
  27. S. Bojja Venkatakrishnan, M. Alizadeh, and P. Viswanath. Costly circuits, submodular schedules and approximate carathéodory theorems. Queueing Systems, pages 1-37, 2018. Google Scholar
  28. Guohui Wang, David G Andersen, Michael Kaminsky, Konstantina Papagiannaki, TS Ng, Michael Kozuch, and Michael Ryan. c-Through: Part-time optics in data centers. In ACM SIGCOMM Computer Communication Review, volume 40 (4), pages 327-338, 2010. Google Scholar
  29. Xia Zhou, Zengbin Zhang, Yibo Zhu, Yubo Li, Saipriya Kumar, Amin Vahdat, Ben Y Zhao, and Haitao Zheng. Mirror mirror on the ceiling: Flexible wireless links for data centers. ACM SIGCOMM Computer Communication Review, 42(4):443-454, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact