Non-concave network utility maximization: A distributed optimization approach
Non-concave network utility maximization: A distributed optimization approach
复制标题
DOI：
10.1109/infocom.2017.8057155
复制
发表时间：
2017-05
期刊：
影响因子：
--
通讯作者：
M. Ashour;Jingyao Wang;C. Lagoa;N. Aybat;Hao Che
中科院分区：
文献类型：
--
作者：
M. Ashour;Jingyao Wang;C. Lagoa;N. Aybat;Hao Che
本文提出了一种通信网络中最优分散流量工程的算法。我们的目标是在可用的路由，使网络效用最大化之间分配的流量。在一些实际应用中，使用非凹函数对网络效用进行建模是特别感兴趣的，例如，视频流因此，我们解决的问题，优化广义类的非凹效用函数。用于解决由此产生的非凸网络效用最大化（NUM）问题的方法依赖于设计一系列的凸松弛，其解决方案收敛到原来的问题。提出了一种求解凸松弛问题的分布式算法。每个用户独立地控制其流量，以将整体网络流量分配到受网络容量约束的最佳操作点。该算法所需的所有计算都是独立执行的，并在每个用户本地使用本地信息和最小的通信开销。唯一需要的非本地信息是来自拥塞链路的二进制反馈。该算法的鲁棒性被证明，其中示出的流量自动重新路由的情况下，链路故障或有新的用户加入网络。数值模拟结果验证了我们的研究结果。
This paper proposes an algorithm for optimal decentralized traffic engineering in communication networks. We aim at distributing the traffic among the available routes such that the network utility is maximized. In some practical applications, modeling network utility using non-concave functions is of particular interest, e.g., video streaming. Therefore, we tackle the problem of optimizing a generalized class of non-concave utility functions. The approach used to solve the resulting non-convex network utility maximization (NUM) problem relies on designing a sequence of convex relaxations whose solutions converge to that of the original problem. A distributed algorithm is proposed for the solution of the convex relaxation. Each user independently controls its traffic in a way that drives the overall network traffic allocation to an optimal operating point subject to network capacity constraints. All computations required by the algorithm are performed independently and locally at each user using local information and minimal communication overhead. The only non-local information needed is binary feedback from congested links. The robustness of the algorithm is demonstrated, where the traffic is shown to be automatically rerouted in case of a link failure or having new users joining the network. Numerical simulation results are presented to validate our findings.