2017 · 46 citations · 23 references
ComputingComputer ScienceComputer SystemsComputer NetworksInterconnection NetworksSchedulingJob SchedulingNetwork OptimizationNetwork Performance AnalysisResource SchedulingResource-constrained SchedulingSoftware-defined NetworkingCentralized ControlCompetitive RatioData Transfer SchedulingEfficient Resource UseGreedy ApproximationGreedy HeuristicsNetwork ResourcesOnline Approximation Algorithms
Planetary‑scale online services transfer massive data over WANs, and because building such networks is costly and applications demand tight timing, operators must use resources efficiently; SDN and reconfigurable optical devices enable centralized cross‑layer control, yet existing solutions lack theoretical performance guarantees. This paper presents approximation algorithms and theoretical analysis for the online transfer scheduling problem over optical WANs, aiming to minimize makespan or total completion time. We design greedy online scheduling algorithms achieving a 3‑competitive ratio for makespan, a 2‑competitive ratio for unit‑size jobs’ sum of completion times, and a 3α‑competitive ratio for arbitrary‑size jobs with node degree constraints, where α = 1 for d = 1 and α = 1.86 for d ≥ 2. We evaluated these algorithms and found that they outperform prior heuristics.
Modern planetary-scale online services have massive data to transfer over the wide area network (WAN). Due to the tremendous cost of building WANs and the stringent timing requirement of distributed applications, it is critical for network operators to make efficient use of network resources to optimize data transfers. By leveraging software-defined networking (SDN) and reconfigurable optical devices, recent solutions design centralized systems to jointly control the network layer and the optical layer. While these solutions show it is promising to significantly reduce data transfer times by centralized cross-layer control, they do not have any theoretical guarantees on the proposed algorithms. This paper presents approximation algorithms and theoretical analysis for the online transfer scheduling problem over optical WANs. The goal of the scheduling problem is to minimize the makespan (the time to finish all transfers) or the total sum of completion times. We design and analyze various greedy, online scheduling algorithms that can achieve 3-competitive ratio for makespan, 2-competitive ratio for minimum sum completion time for jobs of unit size, and 3α-competitive ratio for jobs of arbitrary transfer size and each node having degree constraint d, where α = 1 when d = 1 and α = 1.86 when d ≥ 2. We also evaluated the performance of these algorithms and compared the performance with prior heuristics.
23
Sushant Jain, Alok Kumar, Subhasree Mandal et al. · 2013 · 1.8K citations
Achieving high utilization with software-driven WAN
Chi-Yao Hong, Srikanth Kandula, Ratul Mahajan et al. · 2013 · 1.1K citations · Full text
Inter-datacenter bulk transfers with netstitcher
Nikolaos Laoutaris, Michael Sirivianos, Xiaoyuan Yang et al. · 2011 · 266 citations · Full text
Traffic engineering with forward fault correction
Hongqiang Harry Liu, Srikanth Kandula, Ratul Mahajan et al. · 2014 · 193 citations · Full text