On Virtual Network Embedding: Paths and Cycles
On Virtual Network Embedding: Paths and Cycles
复制标题
虚拟网络嵌入：路径和循环
DOI：
10.1109/tnsm.2020.3002849
复制
发表时间：
2020-09
影响因子：
5.3
通讯作者：
Zhang Ran
中科院分区：
文献类型：
--
作者：
Wu Haitao;Zhou Fen;Chen Yaojun;Zhang Ran
网络虚拟化为克服当前网络的僵化提供了一个很有前途的解决方案，允许在公共基础设施上嵌入多个虚拟网络请求(Vnr)。网络虚拟化中的主要挑战是虚拟网络嵌入(VNE)问题，该问题是将虚拟网络嵌入到共享底层网络上，并且已知是数学上的{NP}$困难。VNR的拓扑异构性是影响VNE性能的一个重要因素。然而，在许多专门的应用和基础设施中，VNR具有一些共同的结构特征，例如路径和循环。因此，为了获得更好的结果，通过考虑到拓扑特征，为这些应用和基础设施设计专用算法是至关重要的。此外，路径和圈是所有网络结构组成的两个最基本的拓扑。利用路径和圈嵌入的特性对于解决一般的VNE问题是至关重要的。在本文中，我们研究了路和圈嵌入问题。对于路径嵌入，我们证明了它的数学上的{NP}-困难和不可逼近。然后，利用多背包问题(MKP)和多维背包问题(MDKP)，提出了一种高效的基于MKP-MDKP的算法。对于循环嵌入，我们提出了一种加权有向辅助图(WDAG)来开发一个多项式时间的算法来确定最小资源消耗的嵌入。数值结果表明，与文献中的通用嵌入算法相比，我们的定制算法可以提高接受率和收益。
Network virtualization provides a promising solution to overcome the ossification of current networks, allowing multiple Virtual Network Requests (VNRs) to be embedded on a common infrastructure. The major challenge in network virtualization is the Virtual Network Embedding (VNE) problem, which is to embed VNRs onto a shared substrate network and known to be $\mathcal {NP}$ -hard. The topological heterogeneity of VNRs is one important factor hampering the performance of the VNE. However, in many specialized applications and infrastructures, VNRs are of some common structural features, e.g., paths and cycles. To achieve better outcomes, it is thus critical to design dedicated algorithms for these applications and infrastructures by taking into accounting topological characteristics. Besides, paths and cycles are two of the most fundamental topologies that all network structures consist of. Exploiting the characteristics of path and cycle embeddings is vital to tackle the general VNE problem. In this paper, we investigate the path and cycle embedding problems. For path embedding, we prove its $\mathcal {NP}$ -hardness and inapproximability. Then, by utilizing Multiple Knapsack Problem (MKP) and Multi-Dimensional Knapsack Problem (MDKP), we propose an efficient and effective MKP-MDKP-based algorithm. For cycle embedding, we propose a Weighted Directed Auxiliary Graph (WDAG) to develop a polynomial-time algorithm to determine the least-resource-consuming embedding. Numerical results show our customized algorithms can boost the acceptance ratio and revenue compared to generic embedding algorithms in the literature.
登录
查看更多内容
克服多样性的挑战：大数据抽象，AAL 通信系统数据管理的下一代发展
影响因子：
11.2
作者：
Mao Rui;Xu Honglong;Wu Wenbo;Li Jianqiang;Li Yan;Lu Minhua
通讯作者：
Lu Minhua
影响因子：
35.6
作者：
A. Belbekkouche;M. Hasan;A. Karmouch
通讯作者：
A. Belbekkouche;M. Hasan;A. Karmouch
影响因子：
5.3
作者：
Aris Leivadeas;C. Papagianni;S. Papavassiliou
通讯作者：
Aris Leivadeas;C. Papagianni;S. Papavassiliou
影响因子：
2.8
作者：
Cheng, Xiang;Su, Sen;Wang, Jie
通讯作者：
Wang, Jie
DOI：
10.1109/infcom.2013.6566800
发表时间：
2013-04
期刊：
2013 Proceedings IEEE INFOCOM
影响因子：
--
作者：
Shahrzad Shirazipourazad;Chenyang Zhou;Zahra Derakhshandeh;Arunabha Sen
通讯作者：
Shahrzad Shirazipourazad;Chenyang Zhou;Zahra Derakhshandeh;Arunabha Sen