Network Flow Scheduling In Cluster Systems

Currently,cluster systems are widely deployed and used.In a cluster system,a task is generally divided into a series of processing stages,and data or intermediate results need to be transmitted between stages through the internal network.Existing measurement shows that data transmission time accounts for a large proportion of task run time.Therefore,optimizing data transmission time in cluster systems is significant for accelerating tasks and improving application performance.Network flow scheduling is an effective way to optimize data transmission time,which mainly refers to setting transmission orders and allocating bandwidth for data flows.In small-scale cluster systems,there is easily no blocking inside the network,and flow scheduling is mainly on edge links.While in large-scale cluster systems,there may also be in-network bottlenecks,and flow scheduling should also act inside the network.Due to wide variety of cluster system applications and their diverse communication patterns,there are both independent individual flows and concurrent coflows in the internal network.Correspondingly,network flow scheduling includes both individual flow scheduling and coflow scheduling.According to above classification,this thesis respectively investigates individual flow scheduling and coflow scheduling problems in small-scale and large-scale cluster systems:(1)We propose a stable individual flow scheduling scheme.For the scheduling scheme instability problem existing in both small-scale and large-scale cluster systems,we design a stable individual flow scheduling scheme BASRPT for both small-scale and large-scale cluster systems.BASRPT takes into account both remaining flow size and queue backlog,preferentially transmitting short flows in large queues,which can control queue length and reduce flow completion time simultaneously.Simulation results show that BASRPT can keep queue length stable and achieve low flow completion time.(2)We propose an incomplete-information-based coflow scheduling scheme.In small-scale cluster systems,for the scenarios where partial coflow information is known,we propose an incomplete-information-based coflow scheduling scheme IICS.IICS predicts each coflow’s remaining transmission time according to its already arrived inner flows,and approximates the minimum remaining time first policy based on the prediction.Simulation results show that IICS can achieve the coflow completion time close to that of scheduling schemes based on complete coflow information.(3)We propose an in-network-bottleneck-aware coflow scheduling scheme.For in-network bottleneck constraints in large-scale cluster systems,we design a distributed bottleneck-aware coflow scheduling scheme DBA.Under bandwidth constraints of all links,DBA approximates the network-wide minimum remaining time first policy through rate evolution of each network node.Simulation results show that DBA has superior coflow completion time performance and high throughput.(4)We propose a coflow scheduling scheme in optical circuit switched networks.For the rapid development of optical circuit switching technology in large-scale cluster systems,we propose a scheduling scheme GMRTF to optimize coflow completion time in optical circuit switched networks.GMRTF integrates both circuit scheduling and coflow scheduling,appropriately grouping inner flows on the same circuit.Within each group there is no circuit reconfiguration,and among groups the minimum remaining time first policy is adopted.Extensive simulations verify that GMRTF can significantly reduce coflow completion time and improve throughput in optical circuit switched networks.