Transiently Consistent SDN Updates: Being Greedy is Hard
Transiently Consistent SDN Updates: Being Greedy is Hard
复制标题
DOI：
10.1007/978-3-319-48314-6_25
复制
发表时间：
2016-05
期刊：
影响因子：
--
通讯作者：
S. A. Amiri;Arne Ludwig;Jan Marcinkowski;S. Schmid
中科院分区：
文献类型：
--
作者：
S. A. Amiri;Arne Ludwig;Jan Marcinkowski;S. Schmid
软件定义的网络范例带来了以更灵活但正式可验证的方式运营网络的有趣机会。然而，尽管逻辑上是集中控制，软件定义网络控制器(SDN)仍然是一个分布式系统，在交换机和控制器之间具有固有的延迟。尤其是以一致的方式改变网络配置的问题，也称为一致的网络更新问题，在过去的几年里受到了极大的关注。本文回顾了如何以瞬时一致、无环路的方式更新SDN的问题。首先，我们严格地证明了计算最大(“贪婪”)无环网络更新通常是NP难的；这一结果对经典的最大非循环子图问题(对偶反馈弧集问题)也有启示。其次，我们证明了对于特殊的问题实例，存在快速且良好的近似算法。
The software-defined networking paradigm introduces interesting opportunities to operate networks in a more flexible yet formally verifiable manner. Despite the logically centralized control, however, a Software-Defined Network (SDN) is still a distributed system, with inherent delays between the switches and the controller. Especially the problem of changing network configurations in a consistent manner, also known as the consistent network update problem, has received much attention over the last years. This paper revisits the problem of how to update an SDN in a transiently consistent, loop-free manner. First, we rigorously prove that computing a maximum (“greedy”) loop-free network update is generally NP-hard; this result has implications for the classic maximum acyclic subgraph problem (the dual feedback arc set problem) as well. Second, we show that for special problem instances, fast and good approximation algorithms exist.