On High Performance Load-Aware Balanced Routing Schemes For Datacenters

The communication performance of distributed applications is mainly determined by data-center network,the infrastructure of modern distributed computing.As the rapid development of big data technologies and cloud computing facilities,more and more distributed computing tasks are deployed on datacenters.To guarantee the performance and reliability,structured multipath topologies,such as fat-tree,are usually used for datacenter networks.The routing processes in multipath networks are different from those in generic IP networks.If traditional routing algo-rithms are used in the aforementioned kind of network,the routing efficiency will be decreased.Therefore,in this thesis,high performance routing schemes dedicated to datacenter networks are researched.The major contents are the following:First,a high performance iterative scheduling algorithm for datacenter switch is designed.Switching is the basic of routing.And the switching capability is determined by scheduling algo-rithm.Usually,the development of hardware cannot catch up with the switching requirements,so traditional multiple-iteration scheduling algorithms based on queue length are not suitable for future high-speed datacenters.To solve this problem,the thought of Highest Order First(HOF)is presented and a single-bit-single-iteration scheduling algorithm based on HOF is designed in this thesis.The new algorithm has low computational complexity and communication overhead,and performs much better than other scheduling algorithms,which provides a new direction for the designment of datacenter switching devices.Second,the load-aware balancing strategy and roulette wheel selection mechanism are de-signed to solve the path selection problems in multipath datacenter networks.There are two kind of strategies for load awareness,global load feedback and local load prediction.The former is accurate but the later has lower cost.In this thesis,both of them are discussed.The load feedback process is combined with modularized network architecture to improve the scalability of global load awareness.And the Link Capacity Aggregation(LCA)mechanism is adopted to improve the accuracy of local load counting.After the load is determined,roulette wheel selection can solve the link bottleneck and load fluctuation problems.Compared with other selection meth-ods,roulette wheel selection can improve the utilization of network bandwidth and decrease the queuing delay effectively.Third,a high performance unicast routing scheme based on Dynamic FlowLet Switching(DFLS)is provided.In this scheme,flowlet switching is combined with load awareness.The resulting routing scheme based on DFLS not only has powerful load balancing capability but also guarantees the order of flows,so that the routing efficiency can be much improved.Last but not least,the group communications in datacenter networks are discussed and a distributed and dynamic multicast routing scheme is provided.There are two properties for the new scheme,dynamics and distributed scheduling.The former can support dynamic extension of multicast trees and improve the universality and adaptability in complicated traffic.The later is aimed at solving the scalability and reliability problems of centralized multicast schemes.Ac-cording to the structured topologies of datacenter networks,the routing rules based on upstream self-routing and downstream table look-up are designed,so as to decrease the complexity.At the same time,for compatibility with existing distributed applications,a complete distributed Address Dispatching Protocol(ADP)is designed.And based on ADP,a load balancing strat-egy named Uniform Forest is provided.The resulting dislribuied multicast scheme has lower complexity and higher reliability.It can also get better performance than existing centralized multicast schemes.The researches on switching technologies and routing schemes are aimed at improving the efficiency,scalability as well as reliability of datacenter networks while reducing the complex-ity of traffic scheduling.Besides solving practical problems,there are also some new thoughts for designment.For example,the concepts of HOF,LCA,DFLS and distributed multicast are firstly presented in this thesis.With systematic discussion for routing mechanisms in multipath networks,the research in this thesis opens up a new way to design large-scale high-speed data-centers,and provides significant guidelines for researches in future datacenter networking.