利用加速梯度法实现集中式网络效用最大化

《IEEE Transactions on Networking》：Centralized Network Utility Maximization With Accelerated Gradient Method

网络效用最大化（NUM）是网络资源分配的核心问题，传统研究侧重去中心化算法，而SDN环境下的集中式算法需兼顾效率与可扩展性。本文提出一种融合平滑效用函数与Nesterov加速梯度法（AGM）的集中式NUM算法，通过设计O(d2/t2)收敛速度的优化模型，解决大规模多流场景下的效率瓶颈，并验证其在多优先级复杂路径中的有效性。

　　

摘要：

网络效用最大化（Network Utility Maximization, NUM）是网络流量管理和资源分配中的一个基本问题。由于网络固有的去中心化和复杂性，现有的大部分研究都集中在开发用于NUM的去中心化算法上。然而，随着软件定义网络（Software-Defined Networking, SDN）的兴起，特别是在由大型企业管理的云网络和数据中心间网络中，人们对集中式NUM算法的兴趣日益增加。为了应对这类SDN网络中大量且不断增加的数据流，现有的集中式NUM研究主要关注算法在数据流数量方面的可扩展性，而忽略了效率问题。在本文中，我们提出了一种集中式、高效且可扩展的NUM算法。通过设计平滑的效用函数和惩罚函数，我们将NUM问题表述为一个具有平滑目标函数的优化问题，从而能够使用Nesterov加速梯度法（AGM）进行求解。我们证明了所提出的方法能够实现O(d/t^2)的收敛速率，这表明其收敛速度优于传统的迭代方法，并且该算法在数据流数量d方面具有很好的可扩展性。我们的平滑目标函数表述和AGM方法不仅在数据流沿单一路径传输的简单网络场景中有效，也适用于涉及数据流跨多个复杂路径传输的更复杂和实际的应用场景。实验结果证实，我们的方法能够在更少的迭代次数内获得精确的解，并实现接近最优的网络效用。

引言

网络流量的快速增长以及网络用户数量的增加给有效和公平的网络资源分配带来了前所未有的挑战。网络效用最大化（NUM）问题最初由Kelly [1] 提出，为解决这一挑战提供了基本的框架。在NUM问题中，多个源沿预定路径发送弹性流量，每个源都有一个与其发送速率相关的、连续可微分、非递减且凹性的效用函数。最常用的效用函数是Mo和Walrand [2][3] 提出的“-fair”函数。问题的目标是在满足链路容量约束的前提下，最大化所有源的总效用。由于其通用性和灵活性，NUM已被应用于各种网络场景，包括无线网络 [4]、多层无线接入网络 [5]、网络功能虚拟化 [6] 等。