Design And Optimization Of Routing Methods For Uncertain Multicast Transfers

Multicast can reduce the consumption of network resource efficiently,and it has been widely used in traditional network.On the other hand,data centers are the key infrastructures for not only cloud services but also massively distributed computing.Since the amount of flows in data centers is growing,using multicast transfer in data center network will be a good choice.The application of software defined network technology makes the fine grained manipulation and centralized routing possible.And the application of network function virtualization reshapes the topology of routing and makes it more complicated.In detail,multicast in traditional network has single source node,and it has fixed place.While in data center network,multicast can have multiple source nodes,and the routing can select any one among these source nodes.The flexibility of source nodes selection in multicast convert the deterministic multicast into uncertain multicast.Additionally,the resource of data center network is limited,including the node compute resource and the link bandwidth resource.When there are several multicast sessions simultaneously,how to design routing for each uncertain multicast session becomes a new question.For some delay sensitive application,how to construct routing satisfying constraints is also a new question.Thus,this thesis studies above problems and the main works are as follows:(1)Summarizing the existing multicast researches systematically.In traditional network,the routing of multicast is calculated by the union of unicast paths because of lacking the whole view of network.In software defined data center,the routing topology has been changed.This thesis reviews the history and relate works.(2)Putting forward the packing problem of uncertain multicast(MPU)and designing two methods.When deploying some uncertain multicast applications at the same time,we must considering the restriction of limited network resource.MPU studies how to satisfy these sessions under the constraints of network resource.This thesis models the MPU problem,optimizing the total cost of all multicast forest,and gives the NP-hard proof.Then,this thesis design two methods,priority placement algorithm based on greedily strategies and reconstruction algorithms based on adjusting congested links.(3)Putting forward the problem of delay-guaranteed minimum cost forest for uncertain multicast(D-MCF)and designing two methods.There are many uncertain multicast applications which have constraints of end-to-end delay.Given the delay bound,how to find a routing for uncertain multicast satisfying the delay constraint is an important problem.This thesis builds an Integer Programming model for D-MCF,and prove that it is NP-hard.This thesis designs two methods for the D-MCF problem,including multicast group partition algorithm and uncast paths combination algorithm.The correctness and approximation ratio are presented in the analysis of algorithms.(4)Conducting massive simulations to evaluate the performance of the algorithms.This thesis conducts massive simulations to evaluate the performance of the algorithms for MPU and D-MCF.These simulations study the impact of different parameters,such as the network size,multicast size,delay bound and so on.Also,this thesis compare these methods as far as their performance.