Research On Function Deployment And Routing In Network Virtualization

Information system and information management is an important scientific field that takes information as the core resource and information technology as the core capability to solve practical economic and management problems at macro and micro levels,and has three important dimensions of "information,technology and management".The computer network system relying on various network functional devices and routing protocols plays an irreplaceable and important role in linking information systems,which itself evolves with the change of application requirements.The applications on information systems which is represented by the Internet,continue to put forward new requirements on the network,specifically including low latency,large bandwidth,nondisruptive and security isolation characteristics.To satisfy these requirements from applications,we need to continuously develop new network technologies and improve network management capabilities.Network virtualization is an important grip to achieve flexible,efficient and reliable scheduling of network resources,and is a key technology to realize the future network vision.Starting from two important components of computer networks,i.e.,network functional devices and routing systems,this paper carries out an in-depth study of function deployment and routing issues in network virtualization.The research results are of great value to the development and deployment of virtualized networks,and also have implications for research work in related fields.The paper carries out research in the following five main areas.Firstly,we propose an optimal deployment method of service function chain in Multicast transfer.In this paper,we find that the number of virtual network instances is non-decreasing along the access order of the service function chain in Multicast transfer,i.e.,the number of upstream virtual network function instances is always no more than the number of downstream virtual network function instances.Based on this finding,this paper proposes that the optimal deployment of service function chain in Multicast transfer should be a tree-like structure.Based on this,an algorithm based on Multi-level Overlay Directed graph is designed and the approximate ratio analysis of the algorithm is given.The experimental results show that the proposed algorithm can reduce the cost by 22.41%.Secondly,we propose the optimal deployment method of service function chain in Incast transfer.In this paper,we find that the number of virtual network function instances is non-increasing along the access order of service function chain in Incast transfer,i.e.,the number of upstream virtual network function instances is always no less than the number of downstream virtual network function instances.Based on this finding,this paper proposes that the optimal deployment of service function chains in Incast transport should also be a tree structure.Based on this,an algorithm based on submodular maximization is designed with the special structure of the problem itself,and the approximate ratio analysis of the algorithm is given.The experimental results show that the proposed algorithm can reduce the cost by 24.1%.Thirdly,a joint optimization approach for service function chain deployment and traffic scheduling is proposed.In this paper,it is argued by example that the deployment scheme of the service function chain and the scheduling policy of the data flow on the node will jointly determine the completion time of the data flow.Based on this,this paper discretizes the flow scheduling policy in the time dimension,thus organically combining the variables used to represent the service function chain deployment and the flow scheduling.In the single-flow scenario,we design an algorithm based on the placement decision graph to transform the problem into a shortest path problem on the placement decision graph.In the multi-flows scenario,we propose to decompose the original problem into a series of sub-problems using Lagrangian relaxation and decomposition techniques,and design a dynamic programming algorithm to solve these sub-problems.Based on this,a subgradient iterative optimization algorithm is designed to continuously approximate the optimal solution.Experiments show that our designed algorithm can reduce the total completion time of the flow by 22.04%,60.99% and 39.95% on average compared with the three comparison algorithms.Fourthly,the optimal deployment method of SRv6 routing nodes in network interconnection services is proposed.When interconnecting branches with SRv6 in practice,we must consider how to gradually upgrade the equipments in the network to SRv6-enabled devices.In this paper,we study the incremental deployment of routing nodes in SRv6 networks from the perspective of traffic balancing and give a mathematical model of the problem.Then,this paper transforms the original model into a graph model,followed by a greedy algorithm based on reinforcement learning,which has preference for long-term gains.In this paper,we design a network embedding algorithm to embed problem instances with different network topologies,different budgets,and different number of flows in a unified way,which makes our algorithm have good generalization ability.Experimental results show that the proposed method can reduce the maximum link utilization by up to 59.1% compared to the default shortest path algorithm.Finally,a multi-domain federation low-delay routing method based on SRv6 is proposed.The Internet is composed of many autonomous domain systems,and since inter-domain routing protocols take reachability as the first claim,it makes many routes in the network are not minimum-delay routes.As a result,it makes the phenomenon of delay triangle inequality violation on the Internet.In this paper,we exploit the delay triangle inequality violation phenomenon and the emerging SRv6 routing technology to build a multi-domain federation in Overlay network to provide low delay routing services.In this paper,an algorithm based on virtual network coordinates is designed to find a lowlatency path between any pair of nodes,which is divided into three steps: measurement,broadcast,and computation.Meanwhile,in order to further increase the number of candidate indirect low-latency paths,a dynamic strategy of rotating the virtual network coordinates is proposed in this paper.After that,SRv6 is used to steer the traffic on the low-latency path.Thanks to the compatibility of SRv6 itself,the proposed method is well compatible with existing routing systems,and experiments on real data sets show that the method can reduce end-to-end delay by 5.4%-58.9% on average.