[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
research-article

Calendaring for wide area networks

Published: 17 August 2014 Publication History

Abstract

Datacenter WAN traffic consists of high priority transfers that have to be carried as soon as they arrive alongside large transfers with pre-assigned deadlines on their completion (ranging from minutes to hours). The ability to offer guarantees to large transfers is crucial for business needs and impacts overall cost-of-business. State-of-the-art traffic engineering solutions only consider the current time epoch and hence cannot provide pre-facto promises for long-lived transfers. We present Tempus, an online traffic engineering scheme that exploits information on transfer size and deadlines to appropriately pack long-running transfers across network paths and time, thereby leaving enough capacity slack for future high-priority requests. Tempus builds on a tailored approximate solution to a mixed packing-covering linear program, which is parallelizable and scales well in both running time and memory usage. Consequently, Tempus is able to quickly and effectively update its solution when new transfers arrive or unexpected changes happen. These updates involve only small edits to existing transfers. Therefore, as experiments on traces from a large production WAN show, Tempus can offer and keep promises to long-lived transfers well in advance of their actual deadline; the promise on minimal transfer size is comparable with an offline optimal solution and outperforms state-of-the-art solutions by 2-3X.

References

[1]
D. Applegate and E. Cohen. Making Intra-Domain Routing Robust to Changing and Uncertain Traffic Demands. In SIGCOMM, 2003.
[2]
B. Awerbuch and R. Khandekar. Stateless distributed gradient descent for positive linear programs. In STOC, 2008.
[3]
B. Awerbuch and R. Khandekar. Greedy distributed optimization of multi-commodity flows. Distributed Computing, 2009.
[4]
L. Chen et al. Towards minimal-delay deadline-driven data center tcp. In HotNets, 2013.
[5]
E. Danna, A. Hassidim, H. Kaplan, A. Kumar, Y. Mansour, D. Raz, and M. Segalov. Upward max min fairness. In INFOCOM, 2012.
[6]
E. Danna, S. Mandal, and A. Singh. A practical algorithm for balancing the max-min fairness and throughput objectives in traffic engineering. In INFOCOM, 2012.
[7]
A. D. Ferguson, P. Bodik, S. Kandula, E. Boutin, and R. Fonseca. Jockey: Guaranteed Job Latency in Data Parallel Clusters. In EuroSys, 2012.
[8]
L. K. Fleischer. Approximating fractional multicommodity flow independent of the number of commodities. SIAM J. Discret. Math., 2000.
[9]
B. Fortz and M. Thorup. Internet Traffic Engineering by Optimizing OSPF Weights in a Changing World. In INFOCOM, 2000.
[10]
N. Garg and J. Könemann. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. SIAM J. Comput., 2007.
[11]
C.-Y. Hong, S. Kandula, R. Mahajan, M. Zhang, V. Gill, M. Nanduri, and R. Wattenhofer. Achieving high utilization with software-driven wan. In SIGCOMM, 2013.
[12]
N. Jain, I. Menache, J. Naor, and J. Yaniv. Near-optimal scheduling mechanisms for deadline-sensitive jobs in large computing clusters. In SPAA, 2012.
[13]
S. Jain, A. Kumar, S. Mandal, J. Ong, L. Poutievski, A. Singh, S. Venkata, J. Wanderer, J. Zhou, M. Zhu, et al. B4: Experience with a globally-deployed software defined wan. In SIGCOMM, 2013.
[14]
S. Kandula, D. Katabi, B. Davie, and A. Charny. Walking the Tightrope: Responsive Yet Stable Traffic Engineering. In SIGCOMM, 2005.
[15]
S. Kandula, D. Katabi, B. Davie, and A. Charny. Walking the tightrope: Responsive yet stable traffic engineering. In SIGCOMM, 2005.
[16]
S. Kandula, I. Menache, R. Schwartz, and S. R. Babbula. Calendaring for Wide Area Networks (Extended Version), 2014. Available from http://research.microsoft.com/apps/pubs/default.aspx?id=217883.
[17]
S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, and J. Crowcroft. XORs In The Air: Practical Wireless Network Coding. In SIGCOMM, 2006.
[18]
C. Koufogiannakis and N. E. Young. Beating simplex for fractional packing and covering linear programs. In FOCS, 2007.
[19]
N. Laoutaris, M. Sirivianos, X. Yang, and P. Rodriguez. Inter-datacenter bulk transfers with netstitcher. In SIGCOMM, 2011.
[20]
M. Luby and N. Nisan. A parallel approximation algorithm for positive linear programming. In STOC, 1993.
[21]
V. Nagarajan, J. L. Wolf, A. Balmin, and K. Hildrum. Flowflex: Malleable scheduling for flows of mapreduce jobs. In Middleware, 2013.
[22]
S. A. Plotkin, D. B. Shmoys, and E. Tardos. Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res., 1995.
[23]
B. Vamanan et al. Deadline-Aware Datacenter TCP (D2TCP). In ACM SIGCOMM, 2012.
[24]
C. Wilson et al. Better Never than Late: Meeting Deadlines in Datacenter Networks. In SIGCOMM, 2011.
[25]
N. E. Young. Sequential and parallel algorithms for mixed packing and covering. In FOCS, 2001.

Cited By

View all
  • (2024)Asynchronous Multi-Class Traffic Management in Wide Area NetworksIEEE Transactions on Network and Service Management10.1109/TNSM.2024.335479321:2(1750-1763)Online publication date: Apr-2024
  • (2024)Online Training Flow Scheduling for Geo-Distributed Machine Learning Jobs Over Heterogeneous and Dynamic NetworksIEEE Transactions on Cognitive Communications and Networking10.1109/TCCN.2023.332633110:1(277-291)Online publication date: Feb-2024
  • (2023)LOAD-BALANCED ALGORITHM ON BANDWIDTH CALENDARING PROBLEMJournal of the Operations Research Society of Japan10.15807/jorsj.66.7966:1(79-93)Online publication date: 31-Jan-2023
  • Show More Cited By

Index Terms

  1. Calendaring for wide area networks

      Recommendations

      Comments

      Please enable JavaScript to view thecomments powered by Disqus.

      Information & Contributors

      Information

      Published In

      cover image ACM SIGCOMM Computer Communication Review
      ACM SIGCOMM Computer Communication Review  Volume 44, Issue 4
      SIGCOMM'14
      October 2014
      672 pages
      ISSN:0146-4833
      DOI:10.1145/2740070
      Issue’s Table of Contents
      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 17 August 2014
      Published in SIGCOMM-CCR Volume 44, Issue 4

      Check for updates

      Author Tags

      1. deadlines
      2. inter-datacenter
      3. mixed packing covering
      4. online temporal planning
      5. software-defined networking
      6. wide area network

      Qualifiers

      • Research-article

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)229
      • Downloads (Last 6 weeks)40
      Reflects downloads up to 11 Dec 2024

      Other Metrics

      Citations

      Cited By

      View all
      • (2024)Asynchronous Multi-Class Traffic Management in Wide Area NetworksIEEE Transactions on Network and Service Management10.1109/TNSM.2024.335479321:2(1750-1763)Online publication date: Apr-2024
      • (2024)Online Training Flow Scheduling for Geo-Distributed Machine Learning Jobs Over Heterogeneous and Dynamic NetworksIEEE Transactions on Cognitive Communications and Networking10.1109/TCCN.2023.332633110:1(277-291)Online publication date: Feb-2024
      • (2023)LOAD-BALANCED ALGORITHM ON BANDWIDTH CALENDARING PROBLEMJournal of the Operations Research Society of Japan10.15807/jorsj.66.7966:1(79-93)Online publication date: 31-Jan-2023
      • (2023)Utility Maximization in Satellite Networks Using Onboard Caching2023 4th Information Communication Technologies Conference (ICTC)10.1109/ICTC57116.2023.10154792(94-98)Online publication date: 17-May-2023
      • (2022)Traffic Engineering in a Shared Inter-DC WAN via Deep Reinforcement LearningIEEE Transactions on Network Science and Engineering10.1109/TNSE.2022.31722839:4(2870-2881)Online publication date: 1-Jul-2022
      • (2022)Deadline-Aware Fast One-to-Many Bulk Transfers over Inter-Datacenter NetworksIEEE Transactions on Cloud Computing10.1109/TCC.2019.293543510:1(304-321)Online publication date: 1-Jan-2022
      • (2022)Flow-Level Traffic Scheduling in Data Center Networks2022 IEEE 8th International Conference on Computer and Communications (ICCC)10.1109/ICCC56324.2022.10065692(423-429)Online publication date: 9-Dec-2022
      • (2022)DRLNPS: A deep reinforcement learning network path switching solutionInternational Journal of Communication Systems10.1002/dac.519235:11Online publication date: May-2022
      • (2021)Network bandwidth reservation method combining machine learning and linear programmingIEICE Communications Express10.1587/comex.2021XBL004810:6(331-336)Online publication date: 1-Jun-2021
      • (2020)Inter-Datacenter Bulk Transfers: Trends and ChallengesIEEE Network10.1109/MNET.011.190063234:5(240-246)Online publication date: Sep-2020
      • Show More Cited By

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Media

      Figures

      Other

      Tables

      Share

      Share

      Share this Publication link

      Share on social media