Coflow Scheduling In OCS-based Data Centers

Due to the rapid development of big data applications,data centers are suffering increasing pressure on flow transmission.How to improve the transmission efficiency in data center networks becomes an urgent problem.Recently,optical circuit switches(OCS)has received extensive attention due to the advantage of high bandwidth and low power consumption.A large amount of works has been conducted to deploy OCS in data centers to accelerate data transmission.On the other hand,coflow scheduling,the management of a collection of related parallel flows,is also of great importance to improve the flow efficiency in data centers.It is a promising and challenging topic to combine the hardware advantages of OCS and the flexibility of coflow scheduling.Therefore,we here investigate how to design coflow scheduling in OCS to reduce the coflow completion time(CCT).The main work of this thesis is concluded as follows:1.For the single coflow scheduling problem,we propose a 2-approximation algorithm.We first derive a novel operation called regularization to process flow demand in coflow according to the circuit reconfiguration delay.Based on regularization and the combination of optimized BvN decomposition,reconfiguration frequency and hence the CCT can be reduced dramatically.2.For the multiple coflow scheduling,we consider how to optimize the weighted CCT in an offline scenario first.Based on regularization and alignment,we derive an optimization algorithm that can transform a coflow scheudling which is valid in electrical packet switches(EPS)into a scheduling deployed in OCS.Furthermore,we prove that based on the transformation,we can achieve a scheduling in OCS of a small constant approximation ratio compared with the optimal OCS scheduling.We next study online multiple coflow scheduling in OCS.We start from a heuristic idea,and combine it with BvN decomposition to accelerate coflow transmission.3.To evaluate the performance of our algorithms,we design a scheduling simulator and carry out extensive simulations based on Facebook data traces.The experimental results show that in single coflow scheduling,our reconfiguration frequency is 7.36×lower than the baselines and 2.21×faster in CCT.In multi-coflow scheduling,multiple coflows can be completed up to 8.87× faster and 2.45× respectively in offline and online cases,respectively.