IDEAS home Printed from https://ideas.repec.org/a/spr/queues/v88y2018i3d10.1007_s11134-017-9546-x.html
   My bibliography  Save this article

Costly circuits, submodular schedules and approximate Carathéodory Theorems

Author

Listed:
  • Shaileshh Bojja Venkatakrishnan

    (University of Illinois Urbana-Champaign)

  • Mohammad Alizadeh

    (Massachusetts Institute of Technology)

  • Pramod Viswanath

    (University of Illinois Urbana-Champaign)

Abstract

Hybrid switching—in which a high bandwidth circuit switch (optical or wireless) is used in conjunction with a low bandwidth packet switch—is a promising alternative to interconnect servers in today’s large-scale data centers. Circuit switches offer a very high link rate, but incur a non-trivial reconfiguration delay which makes their scheduling challenging. In this paper, we demonstrate a lightweight, simple and nearly optimal scheduling algorithm that trades off reconfiguration costs with the benefits of reconfiguration that match the traffic demands. Seen alternatively, the algorithm provides a fast and approximate solution toward a constructive version of Carathéodory’s Theorem for the Birkhoff polytope. The algorithm also has strong connections to submodular optimization, achieves a performance at least half that of the optimal schedule and strictly outperforms the state of the art in a variety of traffic demand settings. These ideas naturally generalize: we see that indirect routing leads to exponential connectivity; this is another phenomenon of the power of multi-hop routing, distinct from the well-known load balancing effects.

Suggested Citation

  • Shaileshh Bojja Venkatakrishnan & Mohammad Alizadeh & Pramod Viswanath, 2018. "Costly circuits, submodular schedules and approximate Carathéodory Theorems," Queueing Systems: Theory and Applications, Springer, vol. 88(3), pages 311-347, April.
    • Handle: RePEc:spr:queues:v:88:y:2018:i:3:d:10.1007_s11134-017-9546-x
    DOI: 10.1007/s11134-017-9546-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s11134-017-9546-x
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s11134-017-9546-x?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Cynthia Barnhart & Yosef Sheffi, 1993. "A Network-Based Primal-Dual Heuristic for the Solution of Multicommodity Network Flow Problems," Transportation Science, INFORMS, vol. 27(2), pages 102-117, May.
    2. BIENSTOCK, Daniel & CHOPRA, Sunil & GÜNLÜK, Oktay & TSAI, Chih-Yang, 1998. "Minimum cost capacity installation for multicommodity network flows," LIDAM Reprints CORE 1391, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Agarwal, Y.K. & Aneja, Y.P. & Jayaswal, Sachin, 2022. "Directed fixed charge multicommodity network design: A cutting plane approach using polar duality," European Journal of Operational Research, Elsevier, vol. 299(1), pages 118-136.
    2. Yogesh Agarwal, 2013. "Design of Survivable Networks Using Three- and Four-Partition Facets," Operations Research, INFORMS, vol. 61(1), pages 199-213, February.
    3. Yogesh K. Agarwal, 2002. "Design of Capacitated Multicommodity Networks with Multiple Facilities," Operations Research, INFORMS, vol. 50(2), pages 333-344, April.
    4. Ada Suk‐fung Ng & Trilochan Sastry & Janny M.Y. Leung & X.Q. Cai, 2004. "On the uncapacitated K‐commodity network design problem with zero flow‐costs," Naval Research Logistics (NRL), John Wiley & Sons, vol. 51(8), pages 1149-1172, December.
    5. Garg, Manish & Smith, J. Cole, 2008. "Models and algorithms for the design of survivable multicommodity flow networks with general failure scenarios," Omega, Elsevier, vol. 36(6), pages 1057-1071, December.
    6. Moon, Mark A. & Mentzer, John T. & Smith, Carlo D., 2003. "Conducting a sales forecasting audit," International Journal of Forecasting, Elsevier, vol. 19(1), pages 5-25.
    7. Hongbin Liu & Guopeng Song & Tianyu Liu & Bo Guo, 2022. "Multitask Emergency Logistics Planning under Multimodal Transportation," Mathematics, MDPI, vol. 10(19), pages 1-25, October.
    8. Andrew P. Armacost & Cynthia Barnhart & Keith A. Ware, 2002. "Composite Variable Formulations for Express Shipment Service Network Design," Transportation Science, INFORMS, vol. 36(1), pages 1-20, February.
    9. Geir Dahl & Alexander Martin & Mechthild Stoer, 1999. "Routing Through Virtual Paths in Layered Telecommunication Networks," Operations Research, INFORMS, vol. 47(5), pages 693-702, October.
    10. Kaj Holmberg & Di Yuan, 2003. "A Multicommodity Network-Flow Problem with Side Constraints on Paths Solved by Column Generation," INFORMS Journal on Computing, INFORMS, vol. 15(1), pages 42-57, February.
    11. Pengfei Zhang & Neng Fan, 2017. "Analysis of budget for interdiction on multicommodity network flows," Journal of Global Optimization, Springer, vol. 67(3), pages 495-525, March.
    12. Keely L. Croxton & Bernard Gendron & Thomas L. Magnanti, 2007. "Variable Disaggregation in Network Flow Problems with Piecewise Linear Costs," Operations Research, INFORMS, vol. 55(1), pages 146-157, February.
    13. Majid Taghavi & Kai Huang, 2016. "A multi‐stage stochastic programming approach for network capacity expansion with multiple sources of capacity," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(8), pages 600-614, December.
    14. Bernard Fortz & Martine Labbé & Francesco Maffioli, 2000. "Solving the Two-Connected Network with Bounded Meshes Problem," Operations Research, INFORMS, vol. 48(6), pages 866-877, December.
    15. Mervat Chouman & Teodor Gabriel Crainic & Bernard Gendron, 2018. "The impact of filtering in a branch-and-cut algorithm for multicommodity capacitated fixed charge network design," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 6(2), pages 143-184, June.
    16. Jack Brimberg & Pierre Hansen & Keh-Wei Lin & Nenad Mladenović & MichÈle Breton, 2003. "An Oil Pipeline Design Problem," Operations Research, INFORMS, vol. 51(2), pages 228-239, April.
    17. Ayşegül Altın & Hande Yaman & Mustafa Ç. Pınar, 2011. "The Robust Network Loading Problem Under Hose Demand Uncertainty: Formulation, Polyhedral Analysis, and Computations," INFORMS Journal on Computing, INFORMS, vol. 23(1), pages 75-89, February.
    18. Hall, Randolph W., 1999. "Stochastic freight flow patterns: implications for fleet optimization," Transportation Research Part A: Policy and Practice, Elsevier, vol. 33(6), pages 449-465, August.
    19. Raymond K. Cheung & B. Muralidharan, 2000. "Dynamic Routing for Priority Shipments in LTL Service Networks," Transportation Science, INFORMS, vol. 34(1), pages 86-98, February.
    20. Sara Mattia & Michael Poss, 2018. "A comparison of different routing schemes for the robust network loading problem: polyhedral results and computation," Computational Optimization and Applications, Springer, vol. 69(3), pages 753-800, April.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:queues:v:88:y:2018:i:3:d:10.1007_s11134-017-9546-x. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.