Maximum flow and minimum-cost flow in multi-interface networks
Maximum flow and minimum-cost flow in multi-interface networks
复制标题
多接口网络中的最大流量和最小成本流量
DOI：
10.1145/1968613.1968637
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
A. Navarra
中科院分区：
文献类型：
--
作者：
Gianlorenzo D'angelo;G. Stefano;A. Navarra
在异构网络中，设备可以通过多个有线或无线接口进行通信。通过在接口之间切换或通过组合可用接口，每个设备可以建立多个连接。当位于其端点的设备共享至少一个活动接口时，连接被建立。假设每个接口需要激活成本，并提供通信带宽。在本文中，我们考虑两个基本的优化问题。在第一个中，我们的目标是激活网络G =（V，E）中的一组接口，以保证两个给定节点之间的最大带宽。节点V表示设备，边E表示可以根据设备中接口的可用性建立的连接。在第二个问题中，我们寻求激活网络中最便宜的接口集，以保证两个指定节点之间的最小通信带宽B。我们表明，第一个问题是多项式可解的，而第二个是NP-困难的。然而，我们通过实验分析了第二个问题的算法，表明在实际情况下，它保证了低近似比，这使我们能够在现实世界的网络中使用它。
In heterogeneous networks, devices can communicate by means of multiple wired or wireless interfaces. By switching among interfaces or by combining the available interfaces, each device might establish several connections. A connection is established when the devices at its endpoints share at least one active interface. Each interface is assumed to require an activation cost, and provides a communication bandwidth. In this paper, we consider two fundamental optimization problems. In the first one, we aim to activate a set of interfaces in the network G = (V, E) in order to guarantee the maximal bandwidth between two given nodes. Nodes V represent the devices, edges E represent the connections that can be established according to the availability of the interfaces in the devices. In the second problem, we look for activating the cheapest set of interfaces among a network in order to guarantee a minimum bandwidth B of communication between two specified nodes. We show that the first problem is polynomially solvable while the second one is NP-Hard. However, we experimentally analyzed an algorithm for the second problem, showing that in practical cases it guarantees a low approximation ratio which allows us to use it in real-world networks.