Abstract-In this paper we address the problem of virtual network reconfiguration. In our previous work on virtual network embedding strategies, we found that most virtual network rejections were caused by bottlenecked substrate links while peak resource use is equal to 18%. These observations lead us to propose a new greedy Virtual Network Reconfiguration algorithm, VNR. The main aim of our proposal is to 'tidy up' substrate network in order to minimise the number of overloaded substrate links, while also reducing the cost of reconfiguration. We compare our proposal with the related reconfiguration strategy VNA-Periodic, both of them are incorporated in the best existing embedding strategies VNE-AC and VNE-Greedy in terms of rejection rate. The results obtained show that VNR outperforms VNA-Periodic. Indeed, our research shows that the performances of VNR do not depend on the virtual network embedding strategy. Moreover, VNR minimises the rejection rate of virtual network requests by at least 83% while the cost of reconfiguration is lower than with VNA-Periodic. Keywords: Network virtualization, Embedding problem, Reconfiguration. In the last few years, network virtualization has attracted a great deal of interest from industry and research communities as a means for designing the future Internet architecture. In fact, Network virtualization offers a promising way to share a physical network among many simultaneous, independent and isolated virtual networks [1], [2] . Each Virtual Network (VN ) allocates resources in the Substrate Network (SN ) such as processing power, memory and bandwidth. The network virtualization paradigm is confronted with many challenges [3] , such as security, interoperability, resource scheduling, etc. In this research paper, we will examine the problem of resource allocation in SN s. The main objective is to maximise the VN provider's revenue by finding a judicious assignment of a VN request in the SN . It is worth noting that each virtual node is hosted in only one substrate node. Furthermore, each virtual link is embedded into one substrate path. Indeed, in our previous work [4], we proposed an embedding strategy, denoted by VNE-AC. It is based on Max-Min Ant System metaheuristic and outperforms all the related strategies found in existing literature [5]-[8]. However, in spite of the efficiency of the proposed algorithm, we observed two drawbacks in the results obtained. The first one is the underuse of the SN 's resources. In this regard, we noticed that the average rate of bandwidth use is low (i.e. 15%). We can therefore conclude that the SN 's profitability can be improved. The second drawback is bottlenecking in the substrate links. Therefore, in most cases, rejected VN requests are caused by a bandwidth shortfall. It is worth noting that, over time, the SN 's resources become fragmented due to the arrival and departure of new and already hosted VN s respectively. These observations have motivated us to explore the reconfiguration of VN s mapped in the SN so as to overcome the problem of resource fragmentation. In other words, we aim to 'tidy up' the SN in order to minimise the rate of overloaded substrate links. The rejection rate of VN requests will in turn be minimised. In this paper we will propose a new hybrid (i.e. reactive and proactive) Virtual Network Reconfiguration algorithm, denoted by VNR. The proposed approach is reactive so it is carried out only when an embedding strategy cannot assign a VN request in the SN . Moreover, VNR is a proactive approach in that it operates only with the SN and its hosted VN s in order to minimise the rejection rate of future VN requests. Note that VNR is not interrelated with any mapping algorithm and operates only with the SN and its hosted VN s. A virtual node with its attached hanging virtual links form a star moving candidate, denoted by ℵ i . Since migration is costly in terms of service interruption period, VNR does not migrate a whole VN topology but only a minimum set of {ℵ i } hosted in the SN . The main idea behind our proposal is to relocate, using migration, star moving candidates {ℵ i } in the aim of minimising the number of congested substrate links. To do so, VNR first of all sorts, in decreasing order, star moving candidates {ℵ i } of all VN s deployed in the SN . Candidates are sorted based on a predefined metric, κ i , quantifying the suitability for migration of each ℵ i . Then, VNR selects only the first successful migrating ℵ i in the sorted selection, among the N max highest (i.e. in terms of κ i ) star moving candidates {ℵ 1 , ℵ 2 , · · · , ℵ Nmax }. If VNR does not succeed the migration, the embedding strategy rejects the VN request. Otherwise, the embedding strategy tries to map the VN request again. If it fails once more, the process is repeated from the sorting stage, at the most N mig iterations. We incorporated our reconfiguration scheme, VNR, with the best embedding strategies, in term of rejection rate, found in existing literature i) VNE-Greedy [6] and ii) VNE-AC [4]. Based on extensive simulations, we found that VNR significantly decreases the rejection rate of VN requests. Moreover, we compared VNR with the reconfiguration algorithm VNA-Periodic [5] . The results obtained show that our proposal outperforms VNA-Periodic. The remainder of this paper is organised as follows. In the next Section we will summarise the related approaches to solving the VN reconfiguration problem. In Section III we will outline the main reasons that motivated this research. Then, we will formulate the VN reconfiguration problem in Section IV, before describing our VN reconfiguration algorithm, VNR, and providing a performance evaluation in Section V and Section VI respectively. Finally, Section VII will conclude this U.S. Government work not protected by U.S. copyright This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE Globecom 2011 proceedings.
(2) Based on the analysis on resource utilization, Fajjari et al. REF found that the existence of bottlenecked substrate links is the main reason of most of the request rejections.
VNR Algorithm: A Greedy Approach for Virtual Networks Reconfigurations
2011 IEEE Global Telecommunications Conference - GLOBECOM 2011
2011 IEEE Global Telecommunications Conference - GLOBECOM 2011
Computer Science