Research On Efficient And Reliable Virtual Network Mapping Algorithms

Network virtualization abstracts multiple isolated virtual networks on theinfrastructure, and different virtual networks can deploy different network technologiesand architectures. It can overcome network ossification that prevents the innovations ofnetwork technologies. And multiple virtual networks sharing the infrastructure leads toutilizing the infrastructure resources more efficiently and flexibly, which is also theessential technology in cloud computing.The first step of deploying virtual netwoks is the allocation of computing (node) andcommunication (link) resources on the infrastructure for virtual networks. Each virtualnetwork consists of virtual nodes that are interconnected by virtual links. There arecomputing resource requirement on virtual nodes and bandwidth requirement on virtuallinks. The resource allocation for virtual networks, i.e., the virtual network mappingproblem is which substrate nodes and paths to be mapped to virtual nodes and links. Inthis paper, the author studies basic virtual network mapping, virtual network mappingacross multiple domains (administrative domains or data centers) and reliable virtualnetwork mapping, and presents the algorithms to address the problems, which theperformance of mapping cost, runtime or quality of service is better than otheralgorithms.Basic virtual network mapping is that the given virtual network is mapped onto thegiven infrastructure in a centralized manner, aiming to minimize the mapping cost. Thevirtual network mapping problem is NP-hard, thus heuristic algorithms should bepresented to address the problem. The well-known algorithm vnmFlib is based on graphisomorphism detection. But with different setting in the vnmFlib algorithm, there is ashortcoming whether the runtime is longer or the mapping cost is higher. In this paper,the author improves the vnmFlib algorithm, i.e., the Improved-vnmFlib algorithm, inwhichthe mapping is guided by cost evaluation, and then the runtime is short and themapping cost is low simultaneously.Compared with basic virtual network mapping, the structure of underlyinginfrastructures is more complex in the problem of virtual network mapping acrossmultiple domains. In this paper, the author studies the mapping of a given virtualnetwork onto the given infrastructure, aiming to optimize the global price and quality ofservice. The underlying infrastructure consists of multiple administrative domains.Since the topology and resource information of each domain is kept in secret, the virtual network should be mapped onto the infrastructure in a decentralized manner. In theexisting research, the subgraphs of a virtual network are mapped in multiple domains,and the inter-domain paths are established for the virtual links of which the end nodesare in different domains. It lacks a global view for optimizing global mappingperformance. In this paper, the author proposes the framework MD-VNM (MultipleDomain Virtual Network Mapping) which leads to lower mapping price and highquality of service. In MD-VNM, a global graph is constructed by the mappingcandidates provided by different domains, so that the global mapping performance canbe considered for selecting mapping candidate.The author also studies the mapping of a given virtual network onto a giveninfrastructure that consists of data centers interconnected by a wide-area network, withthe aim of minimizing the mapping cost. The unit bandwidth cost in a data center islower than that on the wide-area network. Survivability against the failures of datacenters is not guaranteed in the existing studies on virtual mapping across multiple datacenters. In this paper, the author studies the problem, presents the SG-VNM(Survivability Guarantee Virtual Network Mapping) algorithm, in which with theguarantee of survivability virtual nodes are distributed in several data centers to reducethe bandwidth on the wide-area network. While guaranteeing the required survivability,the SG-VNM algorithm leads to lower mapping cost than other algorithms.Reliable network mapping is that a virtual network is mapped onto the infrastructurewith the reliability against probabilistic failures physical servers, aiming to minimizethe total mapping cost. Backup virtual nodes and backup virtual links are added to theprimary virtual network for guaranteeing the desired reliability, i.e., reliable virtualnetwork. Firstly, the author presents the reliable virtual network mapping algorithmRVNM (Reliable Virtual Network Mapping), with the design that all primary virtualnodes share backup virtual nodes. The RVNM algorithm considers the sharing betweenbackup bandwidth and the reuse of primary bandwidth simultaneously, leading to lowerreliable mapping cost. However, the above reliability design results in large bandwidthof backup virtual links, thus it only applies to the infrastructure of low unit bandwidthcost, e.g., in data centers. Then based on the primary virtual network mapping acrossmultiple data centers where the unit bandwidth cost between data centers is higher thanthat in data centers, we also propose the local protection approach to avoid backupbandwidth on the wide-area network, leading to lower reliable mapping cost.