دانلود رایگان مقاله یک الگوریتم ACO اصلاح شده برای شبکه های مجازی، جاسازی بر پایه تجزیه نمودار

Abstract

Network virtualization is a promising scheme to solve Internet ossification. A challenging problem in this scheme is virtual network embedding (VNE), which involves efficiently embedding multiple heterogeneous virtual networks into one or more physical networks. The VNE problem is known to be NP-hard and thus requires an approximate algorithm as a solution. This study models the VNE problem based on virtual network topology invariance and analyzes the shortcomings of a general embedding algorithm under different network topologies. A modified ant colony optimization algorithm is proposed based on network topology decomposition. A pre-computation algorithm is first proposed based on ant random walking to accelerate the recognition of the ring characteristics of a network topology. Pre-computation results are used to guide the decomposition of virtual networks and the embedding process of ring structures. The topology of a virtual network is decomposed into a combination of ring structures and tree structures, which have different characteristics. Different embedding algorithms are then designed for these structures. Point-disjoint paths are searched for any two virtual links to ensure the reliability of the network topology in the embedding process. The proposed algorithm shows an enhanced optimization performance, which is better than those of the ViNE-LB and GN-SP algorithms.

6. Conclusion

We modeled the VNE problem based on virtual network topology invariance to guarantee the reliability requirements of SPs. We analyzed the differences between ring structure and tree structure mapping process and proposed a modified ACO algorithm for the VNE problem based on graph decomposition. We also obtained the ring characteristics of the SN and VN requests through pre-computation and decomposed each VN request into a combination of ring structures and tree structures by using pre-computation results. We designed different mapping algorithms for the ring and tree structures. The ring structure mapping algorithm uses the ring characteristic of the SN, and the tree structure mapping algorithm uses a tree-indexed random walking construction process. These algorithms can use the topology characteristics efficiently for an enhanced performance. To satisfy the requirement of the VN in the VN topology, we proposed the term “topology invariance,” which avoids the unnecessary sharing of nodes and links. Candidate nodes were used to achieve topology invariance. The proposed algorithm not only guarantees topology invariance but also improves the load balance of the SN to accept several future VN requests.