网络组合优化问题的分布式近似算法设计研究

Many important network resource allocation problems in wireless networking,Peer-to-Peer networking,cloud computing and network coding are combinatorial optimization problems. In general, exact solutions of these problems are computationally prohibitive. Efficient approximation algorithms either do not exist or only allow centralized implementation. In this project, we aim to develop a general framework to guide distributed algorithm design for solving combinatorial network optimization problems. Within this framework, we can synthesize distributed approximation algorithms in a systematical way, which converge fast, attain close-to-optimal performances, scale with the network size, and adapt smoothly to network and user dynamics. Our investigations on this framework include: equivalence between distributed algorithm design and distributed implementation of Markov chain;state-connectivity structure of Markov chain, state transition rate of Markov chain, perturbation of Markov chain, quantization of optimality loss caused by the perturbation, application of this framework to various network domains such as reverse-engineering BitTorrent protocol and traffic engineering of data center networks.

无线网络，点到点网络，云计算以及网络编码中的许多重要的网络资源分配问题都是组合优化问题。一般而言，精确求解这些问题的计算复杂度之高让人望而却步。有效的近似算法或者不存在，或者只能允许集中式实现。本课题旨在发展一套解决网络组合优化问题的分布式算法设计通用框架。通过该框架，我们可以系统性的设计出分布式近似算法。这套算法的特点是收敛快，可取得近似最优的性能，具有随着网络尺寸伸缩的可扩展性，并且能平滑的适应网络和用户的动态。针对这套算法设计框架，我们的研究内容包括:分布式算法设计与马尔可夫链的分布式实现的等价性，马尔可夫链的状态链接结构，马尔可夫链的状态转移速率，马尔可夫链的扰动，量化由于扰动带来的最优性能损失，以及应用该框架到广泛的网络领域 （例如针对BitTorrent协议的逆向工程以及数据中心网络的流量工程）。

网络组合优化问题的分布式近似算法设计非常重要。在本项目的资助下,项目组对网络组合优化问题的分布式近似算法设计展开了深入的研究，在理论基础与实际应用两方面均取得了重要成果,完善了分布式网络组合优化问题的近似算法设计框架、并拓宽了其潜在的应用场景。其中,论证了分布式算法设计与马尔科夫链的分布式实现的等价性;建立起马尔科夫链的状态链接结构以及状态转移速率的设计原则；量化了由于扰动带来的优化性能损失；并且将完善后的算法设计框架用于广泛的网络领域，解决了不少公开难题，其中包括无线网络中分布式离散功率控制的最优算法设计问题, 点到点网络中最优流速的分布式算法设计, 软件定义网络中数据平面与控制平面的流量平衡设计, 数据中心网络中流量工程的并行算法设计, 网络博弈论的分布式学习机制。这些成果收到网络领域众多同行的关注，并被工业界所看重。在本项目支持下,项目组成员共发表1篇SCI期刊论文、1篇EI国际会议论文,项目负责人在IEEE举办的国际无线网络大会年会(WiOpt) 等知名国际会议上作口头报告1次。此外，还有多篇论文被接收与在审。