The Critical Network Flow Problem: Migratability and Survivability
The Critical Network Flow Problem: Migratability and Survivability
复制标题
DOI：
10.1109/tnet.2017.2747588
复制
发表时间：
2017-09
期刊：
影响因子：
--
通讯作者：
Ruozhou Yu;G. Xue;Xiang Zhang
中科院分区：
文献类型：
--
作者：
Ruozhou Yu;G. Xue;Xiang Zhang
在本文中，我们提出了一个新的网络抽象，称为关键网络流，它模拟了现代互联网应用和服务的带宽需求。关键网络流定义了网络中的常规流，其聚合带宽或通常称为流值具有明确的要求。与仅在正常操作期间保证带宽的常见带宽保证连接不同，关键网络流在各种瞬态网络状态（诸如网络重新配置或网络故障）期间要求严格执行带宽保证。本文研究了网络临界流在不同带宽临界条件下的适应算法，包括不考虑网络暂态的基本情况、考虑网络重构的情况和考虑网络重构的情况，以及针对链路故障的生存性的情况。我们提出了一个多项式时间的最优算法为每种情况。对于生存的情况下，我们进一步提出了一个更快的启发式算法。我们已经进行了大量的实验来评估我们的模型和验证我们的算法。
In this paper, we propose a new network abstraction, termed critical network flow, which models the bandwidth requirement of modern Internet applications and services. A critical network flow defines a conventional flow in a network with explicit requirement on its aggregate bandwidth, or the flow value as commonly termed. Unlike common bandwidth-guaranteed connections whose bandwidth is only guaranteed during normal operations, a critical network flow demands strictly enforced bandwidth guarantee during various transient network states, such as network reconfiguration or network failures. Such a demand is called the bandwidth criticality of a critical network flow, which is characterized both by its flow value and capability to satisfy bandwidth guarantee in the transient states.We study algorithmic solutions to the accommodation of critical network flows with different bandwidth criticalities, including the basic case with no transient network state considered, the case with network reconfiguration, and the case with survivability against link failures. We present a polynomial-time optimal algorithm for each case. For the survivable case, we further present a faster heuristic algorithm. We have conducted extensive experiments to evaluate our model and validate our algorithms.