Q-SR: An Extensible Optimization Framework for Segment Routing
Q-SR: An Extensible Optimization Framework for Segment Routing
复制标题
Q-SR：分段路由的可扩展优化框架
DOI：
10.1016/j.comnet.2021.108517
复制
发表时间：
2020-12
影响因子：
5.6
通讯作者：
Chenwei Zhao
中科院分区：
文献类型：
--
作者：
Jianwei Zhang;Chenwei Zhao
分段路由（SR）结合了由软件定义网络（SDN）范例驱动的源路由和传统网络基础设施中的逐跳路由的优点。近年来，SR在多域网络和服务功能链（SFC）中的应用需要有效地使用多个网段。然而，由于计算效率低，它几乎是不可能准确地评估是否以及在何种程度上各种类型的网络将受益于SR与多个段使用传统的方法。在本文中，我们提出了一个灵活的Q-SR框架，以及它的制定，以充分探索SR的潜力，从算法的角度来看。该框架是高度可扩展的设计和评估算法，可以适应各种网络拓扑结构和流量矩阵。对于离线设置，我们开发了一个完全多项式时间近似方案（FPTAS），它可以找到一个（1+ ω）-近似解决方案，任何指定的ω> 0的时间是一个多项式函数的网络规模。据我们所知，建议的FPTAS是第一个算法，可以计算任意精确的解决方案。对于在线设置，我们开发了一个在线的原始-对偶算法，被证明是O（1）-竞争和违反链路容量的一个因素O（log n），其中n是网络的节点数。对于所提出的近似算法，我们证明了理论性能界限，并在合成和现实网络上进行了广泛的模拟，以分析SR相关参数和算法参数，并验证离线和在线场景下的计算效率。
Segment routing (SR) combines the advantages of source routing powered by software-defined networking (SDN) paradigm and hop-by-hop routing in legacy network infrastructure. The recent applications of SR in multi-domain network and service function chaining (SFC) entail the efficient use of multiple segments. However, because of the computation inefficiency, it is nearly impossible to accurately evaluate whether and to what extent various types of networks will benefit from SR with multiple segments using conventional approaches. In this paper, we propose a flexible Q-SR framework as well as its formulation in order to fully explore the potential of SR from an algorithmic perspective. The framework is highly extensible to design and evaluate algorithms that can be adapted to various network topologies and traffic matrices. For the offline setting, we develop a fully polynomial time approximation scheme (FPTAS) which can find a (1+ ω)-approximation solution for any specified ω> 0 in time that is a polynomial function of the network size. To the best of our knowledge, the proposed FPTAS is the first algorithm that can compute arbitrarily accurate solution. For the online setting, we develop an online primal–dual algorithm that is proven to be O (1)-competitive and violates link capacities by a factor of O (log n), where n is the node number of the network. For the proposed approximation algorithms, we prove theoretical performance bounds and conduct extensive simulations on synthetic and realistic networks to analyze SR related and algorithmic parameters and validate the computation efficiency in both offline and online scenarios.
登录
查看更多内容
DOI：
10.1109/tnsm.2017.2654681
发表时间：
2017-03
影响因子：
5.3
作者：
David Dietrich;Ahmed Abujoda;Amr Rizk;Panagiotis Papadimitriou
通讯作者：
David Dietrich;Ahmed Abujoda;Amr Rizk;Panagiotis Papadimitriou
DOI：
--
发表时间：
2019-03
期刊：
--
影响因子：
--
作者：
通讯作者：
--
DOI：
10.17487/rfc9087
发表时间：
2017-12
期刊：
RFC
影响因子：
--
作者：
C. Filsfils;S. Previdi;G. Dawra;E. Aries;Dmitry Afanasiev
通讯作者：
C. Filsfils;S. Previdi;G. Dawra;E. Aries;Dmitry Afanasiev
DOI：
10.17487/rfc8279
发表时间：
2017-11
期刊：
RFC
影响因子：
--
作者：
IJsbrand Wijnands;E. Rosen;A. Dolganow;T. Przygienda;S. Aldrin
通讯作者：
IJsbrand Wijnands;E. Rosen;A. Dolganow;T. Przygienda;S. Aldrin
DOI：
10.1109/nca51143.2020.9306706
发表时间：
2020-11
期刊：
2020 IEEE 19th International Symposium on Network Computing and Applications (NCA)
影响因子：
--
作者：
Jean-Romain Luttringer;Thomas Alfroy;Pascal M'erindol;Quentin Bramas;F. Clad;C. Pelsser
通讯作者：
Jean-Romain Luttringer;Thomas Alfroy;Pascal M'erindol;Quentin Bramas;F. Clad;C. Pelsser