Research On Algorithms Of Multicast Virtual Network Mapping

With the rapid development of the Internet and the Cloud computing, kinds of services have appeared. And the ossification of the current Internet architecture prevents it from supporting diverse applications and services. Network virtualization technology can prevent this ossification and diversify the Internet by allowing multiple heterogeneous virtual networks(VNs) share the resources of the same underlying substrate network. Virtual networks are abstracted from service providers’ demands, and virtual networks mapping means allocating resource from substrate network to virtual nodes and links of virtual networks. It also means mapping virtual nodes to substrate nodes and mapping virtual links to substrate paths. As the multicast network service has become more and more popular, we investigate the problem of survivable mapping of multicast virtual network with dynamic resource demands, the problem of survivable mapping for multicast virtual network under single regional failure and the problem of opportunistic provisioning for multicast virtual network requests.First, on the research of survivable mapping of multicast virtual network with dynamic resource demands, we assume that the bandwidth requirement follows a normal distribution and there is only one server failed any time. We design the heuristic algorithm SM-SMVN(the online survivable mapping for stochastic MVN requests) to solve this problem. We improve the min set cover algorithm to map the MVN leaf nodes in order to share the backup resource. And according the mapping of the MVN leaf nodes, map the MVN root node. Our algorithm improves the utilization of substrate resource.Second, we investigate the problem of survivable mapping for multicast virtual network under single regional failure. We decompose the problem of survivable MVN mapping under any single regional failure into separated mapping problem. We design an algorithm named SOUM*-M(Separate Optimization with Unconstrained Mapping for MVN) to integrate all separated mappings into a final mapping solution. In our algorithm, we introduce a non-survivable MVN request mapping algorithm: NSMVNM. We also introduce the strategy of resource sharing in each separated mapping and the strategy of min-cost set cover algorithm to eliminate redundant mapping solutions.Traditional process of the online virtual networks mapping usually reject the request once the mapping is failed, and it considers the load balance at the moment the virtual network arriving. So we improve those shortages and design a heuristic algorithm MVNE-WL(MVN embedding with waiting-tolerant and load-prediction). In our MVNE-WL algorithm, the strategy of waiting-tolerant makes the MVN request tolerate a certain time while it mapping failed and own more chances to mapping again. And the strategy of load-prediction takes the load of substrate network for a period of time into consideration to implement the load balancing, which improves the success rate of online MVN requests mapping.