Research On Kautz Graph Based Data Center Networks

In recent years, with the rapid development of Cloud Computing(CC) and Data-IntensiveSuperComputing(DISC),DataCenterNetwork(DCN)isplayinganincreasinglyimportant role as the underlying infrastructure of CC, and becoming a popular research is-sue. DCN provides reliable, fault-tolerant and efficient services to the upper applicationssuch as Distributed File System(DFS) and virtualization techniques, which including datacommunication, computing and data storage. How to efficiently connect the growingnumber of servers, that means, how to design an efficient topological structure of DCN,is becoming a key issue in research field. Almost all the Enterprise DCNs use multi-roottree as their topological structure. However , multi-root tree suffers from problems ofperformance bottleneck and single point failure at the upper layer. DCell structure hasgood bandwidth, scalable, and fault-tolerant features, but its drawbacks are higher wiringcost and complex interconnection. That is why DCell is so difficult to be deployed inlarge-scale condition. This thesis studies Kautz graph based DCN structure and its rout-ing strategy through making use of Kautz graph's excellent properties in node degree, pathlength and fault tolerance. The goal is to build efficient, fault-tolerant and scalable DCN.The main work including:Kautz graph based DCN topological structure. To solve the performance bottleneckof tree-based structure and complex interconnection of DCell, this thesis proposes a Kautzgraph based DCN structure which called HUK(Hierarchical Undirected Kautz). HUK isa recursive structure which makes use of Kautz graph's excellent properties on the nodenumber and path length to achieve high performance, good scalability and fault-tolerance.HUK structure includes addressing method, interconnection rules and incremental expan-sion algorithm. From theoretical analysis we observe that, compared with DCell, HUKstructure can effectively reduces the number of levels, and simplify the interconnection.Sothecostofdeploymentandmaintenanceisdecreased. Atthesametime,basedonKautzgraph's 2-admissible extension feature, this thesis inherits DCell's incremental expansionand design HUK's incremental expansion algorithm, which supports HUK0 as atomic unitto be incrementally added into HUK, meets the DCN's requirement of scalability.Design of HUK based distributed and fault-tolerant routing algorithm. This thesis proposesadistributedroutingalgorithmwhichusesKautzgraph'sshiftedroutingbetweennodesinthesamelevelandrecursiveroutingstrategybetweennodesindifferentlevels. Todeal with various types of failures in DCN, HUK designs a fault-tolerant routing strategybased on Kautz graph's good fault-tolerant feature. Further, HUK's fault-tolerant routingstrategy is improved by its relatively simple structure. Theoretical analysis and experi-mental verification shows that, compared with DCell, routing length of HUK's distributedrouting strategy is acceptable in large scale condition. During the process of incrementalexpansion, nodes in HUK still have rich links, and routing performance and fault-tolerantfeatures are maintained. In the case of equipments failure in DCN, HUK fault-tolerantrouting strategy can keeps DCN running well. Simultaneously as invalidation rate in-creases, routing length of HUK is growing slowly than that of DCell.Implementing a simulation program to validate HUK structure and routing algorithmin large scale condition. Simulation program includes interconnection definition, conven-tionalroutingalgorithm,fault-tolerantroutingstrategyandincrementalexpansionprocess.This thesis validates the effectiveness of HUK structure and its routing strategy in largescale condition by simulation program.