基于网络编码的HPC拥塞控制技术研究

With the scale increasing of high-performance computers, interconnection resources become relatively scarce, and therefore the HPC congestion control has become one of the key technologies for the performance guarantee for high-performance computers. Existing HPC congestion control mechanisms have some limitations, e.g. congestion notification with long time lags, congestion tree with high growing speed. How to accelerate the queue draining speed on routers to alleviate the congestion, under the trends of larger high performance computers with longer congestion notification lags , becomes an urgent problem for the next-generation HPC congestion control technology. Network coding is the right technique that merges many packets to one coded packets. This feature could efficiently speed up the queue draining. Therefore network coding is regarded as one of the most promising techniques to achieve the next-generation HPC interconnection networks. To handle the problems which affects the congestion control in the next-generation HPC interconnection networks, this project is to carry out researches on network coding-based congestion control technology. By breaking through a series of key techniques, such as coding-aware performance characteristic analysis of HPC interconnection networks, coding-based queue draining strategies with delay constraints, topology characteristic based decoding path construction algorithms, we arm to design a network coding-based congestion control mechanism. This mechanism can meet the demand of low latency data transmission for the HPC applications, and to ensure the interconnection networks do not become a performance bottleneck for the next-generation high-performance computers.

随着高性能计算机并行规模的增大，互连资源变得相对紧缺，因此HPC拥塞控制技术已成为保障高性能计算机性能的关键。现有的HPC拥塞控制机制存在拥塞通告时间长、路由树生长快等不足，如何在高性能计算机并行规模不断增大、通告延迟越来越长的情况下，加快路由器缓冲队列的清空速率，是下一代HPC拥塞控制技术亟待解决的问题。网络编码技术通过将多个数据包融合成一个编码包发送，能够有效的提高路由器缓冲队列的清空速率，因此被看作是实现下一代HPC拥塞控制的有效途径。针对下一代HPC互连网络拥塞控制所面临的问题，本项目拟开展基于网络编码的拥塞控制技术研究，突破面向网络编码的HPC互连网络性能特征分析、延迟约束下的编码缓冲清空策略以及基于拓扑特征的解码路径构建算法等关键技术，设计一套基于网络编码的HPC 拥塞控制机制，满足高性能计算应用对低延迟数据传输需求，确保互连网络不成为下一代高性能计算机的性能瓶颈

随着高性能计算机并行规模不断扩大，互连资源变得相对紧缺，因此HPC拥塞控制技术已成为保障高性能计算机性能的关键。现有的HPC拥塞控制机制存在拥塞通告时间长、路由树生长快等不足，通过网络编码技术加快路由器缓冲队列的清空速率，是下一代HPC拥塞控制技术的有效手段之一。本项目在HPC互连网络背景下开展基于网络编码的拥塞控制技术研究，具体包括面向网络编码的HPC互连网络性能特征分析、延迟约束下的编码缓冲清空策略、基于网络编码的HPC拥塞控制机制等四个方面的研究内容。.重要结果：（1）在流间和流内网络编码的排队模型中，信用可以看成一种特殊的数据包，与输入流数据包之间进行同步流间网络编码操作。同步流间网络编码可以通过队列分解方法开展近似排队分析。（2）扩展了随机网络演算理论，提出了网络编码端到端的分析方法，通过随机网络演算的串联性，避免了多跳以后性能界限的偏差积累，能够得到较紧致的性能界限。（3）流间网络编码缓冲清空策略的关键是要减小冗余路径开销，可以通过分组编码来解决，且证明了流间网络编码分组问题是一个NP难的问题，并给出了近似算法。（4）流内网络编码缓冲清空策略可通过动态段粒度来满足延迟约束，提出了动态段粒度的概念，并从编码方式、取值范围和输出能力三个方面证明了动态段粒度的可行性。（5）针对互连路由器芯片设计一套支持拥塞控制的高效动态分配缓冲架构和一种新的流控机制，能够利用更浅的缓冲达到更高的互连网络吞吐率。.科学意义：网络编码技术通过将多个数据包融合成一个编码包发送，能够瞬时增大缓冲队列的清空速率，快速地减轻拥塞，但需要构建一条解码路径，通过发送“恢复包”来帮助目的结点解码。通过增大缓冲清空速率来减轻拥塞这一核心理念不同于现有各种拥塞控制技术，既能够为流控策略降低源结点的注入速率赢取更多的时间，又能够从拥塞树的根部迅速阻止拥塞的传播，是实现HPC互连网络拥塞控制的有效途径。