Approximation algorithms for data-intensive service chain embedding
Approximation algorithms for data-intensive service chain embedding
复制标题
DOI：
10.1145/3397166.3409149
复制
发表时间：
2020-10
期刊：
影响因子：
--
通讯作者：
Konstantinos Poularakis;Jaime Llorca;A. Tulino;L. Tassiulas
中科院分区：
文献类型：
--
作者：
Konstantinos Poularakis;Jaime Llorca;A. Tulino;L. Tassiulas
网络虚拟化和可编程性的最新进展实现了创新的服务模型，例如服务链（SC），其中可以通过部署在不同云位置的预定义服务功能序列来引导流。决定SC性能和效率的一个关键方面是它在物理基础设施上的实例化。虽然现有的SC嵌入（SCE）算法可以有效地解决SC的实例化消耗计算和通信资源，他们缺乏有效的机制来处理下一代服务的数据密集型的性质。与以专用的每请求方式分配的计算和通信资源相应地，可以共享存储资源以满足对相同数据的多个请求。为了填补这一空白，在本文中，我们制定的数据密集型SCE问题的目标是最大限度地减少存储，计算和通信资源的成本受到资源容量，服务链，和数据共享的限制。使用随机舍入技术，利用一种新的数据感知线性规划分解过程，我们开发了一个多标准近似算法，可证明的性能保证。评估结果表明，该算法实现了接近最优的资源成本与高达27.8%的成本节省归因于数据的共享。
Recent advances in network virtualization and programmability enable innovative service models such as Service Chaining (SC), where flows can be steered through a pre-defined sequence of service functions deployed at different cloud locations. A key aspect dictating the performance and efficiency of a SC is its instantiation onto the physical infrastructure. While existing SC Embedding (SCE) algorithms can effectively address the instantiation of SCs consuming computation and communication resources, they lack efficient mechanisms to handle the increasing data-intensive nature of next-generation services. Differently from computation and communication resources, which are allocated in a dedicated per request manner, storage resources can be shared to satisfy multiple requests for the same data. To fill this gap, in this paper, we formulate the data-intensive SCE problem with the goal of minimizing storage, computation, and communication resource costs subject to resource capacity, service chaining, and data sharing constraints. Using a randomized rounding technique that exploits a novel data-aware linear programming decomposition procedure, we develop a multi-criteria approximation algorithm with provable performance guarantees. Evaluation results show that the proposed algorithm achieves near-optimal resource costs with up to 27.8% of the cost savings owed to the sharing of the data.