Truthful auction mechanisms for VNF chain provisioning and allocation across geo-distributed datacenters
Truthful auction mechanisms for VNF chain provisioning and allocation across geo-distributed datacenters
复制标题
跨地理分布式数据中心的 VNF 链配置和分配的真实拍卖机制
DOI：
10.1016/j.comnet.2022.109331
复制
发表时间：
2022-09
影响因子：
5.6
通讯作者：
Min Huang
中科院分区：
文献类型：
--
作者：
Xueyi Wang;Xingwei Wang;Dongkuo Wu;Lianbo Ma;Min Huang
随着网络功能虚拟化（NFV）的快速发展，NFV市场正在出现，其允许网络服务提供商（NSP）在用户之间交易不同的虚拟网络功能（VNF）链。因此，VNF链供应和分配的有效机制是保证NFV市场有效运营的关键。一个基本问题是如何最大化市场的社会福利，使得自私的用户有动机从市场获取VNF链。为了克服这个问题，在本文中，我们提出了一个真实的随机组合拍卖机制（TRCAM），它集成了原始-对偶近似算法设计技术和有效的定价策略。该机制考虑NSP的动态VNF链供应和用户的灵活VNF链部署。具体而言，我们首先将社会福利最大化问题表示为整数线性规划，并证明了该问题是NP-难的。然后，我们提出了一个原始-对偶近似算法，这是接近最优的多项式时间复杂度，并采用它作为一个积木设计TRCAM。此外，我们开发了一种新的基于二进制搜索的算法，以提高TRCAM的平均情况下的性能。严格的理论分析和广泛的实验研究表明，我们提出的TRCAM的有效性，它实现了近似的真实性，接近最优的社会福利，个人的理性，和计算效率。
With the fast development of network function virtualization (NFV), NFV markets are emerging that allows network service providers (NSPs) to trade different virtual network function (VNF) chains among users. Therefore, efficient mechanisms for VNF chain provisioning and allocation are key to guarantee efficient operations of the NFV markets. One fundamental issue is how to maximize the social welfare of the market such that selfish users have incentives to acquire VNF chains from the markets. To overcome this issue, in this paper, we propose a truthful randomized combinatorial auction mechanism (TRCAM), which integrates the primal–dual approximation algorithm design technique and efficient pricing strategy. This mechanism considers dynamic VNF chain provisioning of the NSP and flexible VNF chain deployment of users. To be specific, we first formulate the social welfare maximization problem as an integer linear program, which is proven to be NP-hard. Then, we propose a primal–dual approximate algorithm which is near-optimal with polynomial-time complexity and employ it as a building block to design the TRCAM. Furthermore, we develop a novel binary-search-based algorithm to boost the average-case performance of the TRCAM. Both strict theoretical analysis and extensive experimental studies demonstrate the effectiveness of our proposed TRCAM, which achieves approximate truthfulness, near-optimal social welfare, individual rationality, and computational efficiency.
登录
查看更多内容
影响因子：
8
作者：
W. Vickrey
通讯作者：
W. Vickrey
DOI：
10.1016/j.geb.2007.12.009
发表时间：
2008-11
期刊：
--
影响因子：
--
作者：
Ahuva Mu'alem;N. Nisan
通讯作者：
Ahuva Mu'alem;N. Nisan
DOI：
10.1109/tnsm.2016.2598420
发表时间：
2016-09-01
影响因子：
5.3
作者：
Herrera, Juliver Gil;Botero, Juan Felipe
通讯作者：
Botero, Juan Felipe
影响因子：
16.4
作者：
Hassan Halabian
通讯作者：
Hassan Halabian
DOI：
10.1109/infocom.2016.7524565
发表时间：
2016-04
期刊：
IEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications
影响因子：
--
作者：
Tung-Wei Kuo;Bang-Heng Liou;K. Lin;Ming-Jer Tsai
通讯作者：
Tung-Wei Kuo;Bang-Heng Liou;K. Lin;Ming-Jer Tsai