【CCF优秀博士学位论文奖-2019】数据中心网络数据平面更新策略研究，南京大学郑嘉琦

论文摘要：数据中心(datacenter)也叫做“服务器农场”,起源于服务提供商(service provider),它的主要目标是降低用户管理服务器和应用程序的成本。近年来,随着Internet用户的大规模增长以及虚拟化技术、商业化服务器的出现,一些国际知名网络服务企业如美国谷歌、微软等公司都陆续建立了各自的数据中心,用于存储大规模数据,并利用其分布式存储的优势和强大的处理能力,将数据及时高效地传输给全球各个用户。与传统局域网、广域网环境不同,数据中心作为资源密集型基础设施,需要快速响应大量互联网终端用户的业务请求,并行处理多个具有海量数据特征的计算任务。软件定义网络(software defined networking)技术能很好地满足数据中心的新特性,在高效集中式的网络管理、虚拟机自动部署和智能迁移、灵活组网多径转发、虚拟多租户隔离和安全保障等方面展现出了具大的优势。谷歌和微软利用软件定义网络技术连接各自的数据中心,有效地提高了网络带宽利用率,降低了端到端传输时延和丢包率。软件定义的数据中心已成为数据中心演进的一个方向和趋势。本文针对软件定义数据中心网络中最小化拥塞网络异步更新、无环无拥塞网络同步更新和数据平面备份路由设计与部署三个关键问题进行研究,取得的研究成果如下:(1).研究最小化短暂拥塞网络更新问题,即给定网络流量分布的初始状态和目的状态,引入若干中间状态,使得转换时产生的拥塞最小。我们提出的方案是对更新速度和网络拥塞一个合理的权衡,为网络管理者提供了更广泛的设计空间。首先,为了更好的满足不同的应用需求,一些网络流在更新过程中是可分的(splittable),另一些网络流,例如视频流,在更新过程中是不可分的(unsplittable)。我们基于这两个分类,建立了最小拥塞网络更新问题的优化模型并证明这个问题是NP难的。其次,提出两个高效的近似算法:第一个算法是随机舍入算法,这个算法的近似比是O(logk),其中kK是网络中结点的数量;第二个算法是贪婪改进算法,在任意的网络拓扑中,贪婪改进算法和随机舍入算法具有相同的近似比。但在数据中心内部的Fat tree拓扑中,这个算法具有常数近似比4。最后,在数据中心内部的网络和数据中心之间的广域网这两个应用场景,对提出的算法进行性能评估。仿真实验表明提出的算法有效的减少了 60%拥塞,降低了30%的控制开销。Mininet实验表明提出的算法比现有方案的更新时间减少了50%。(2).研究无环无拥塞网络同步更新问题。大量网络更新不一致行为都是由于异步更新时间不确定性导致的。受到最新时钟同步数据平面设计的启发,我们在定时数据平面中研究一致性网络更新问题,即为每个交换机提前计算一个精确的更新调度时间,目标是最小化总的更新时间并且无环路和无拥塞的条件在任意时刻都成立。我们提出了一个方案Chronus,其设计基于可证明的无拥塞和无环路更新调度算法,完全避免了现有的两阶段更新方法所需的流表空间开销。我们将最小化更新时间问题形式化为一个优化问题并证明了问题的难度。我们进一步在多项式时间内提出了一个基于树的算法来计算一个可行的更新序列,以及一个贪心算法来找到更新时间最小的调度序列。Mininet实验和大量的仿真实验表明,Chronus可以大幅度减少更新过程中的短暂拥塞,并且与现有技术相比节省60%的流表规则空间。(3).研究数据平面备份路由设计与部署问题。来自微软的数据中心的统计报告数据表明:数据中心网络中每隔5分钟,有一条链路失效的概率高达21.5%。面对如此频繁出现的数据平面链路失效问题,我们提出了一个新的数据平面错误恢复系统,通过预先计算和建立备份路由来提高软件定义数据中心广域网的鲁棒性。当一条链路失效时,交换机立刻局部重路由数据包到备份路由中,不需要控制器的额外干预,从而大大节省了错误恢复的时间。另外我们的方案完全避免了额外的带宽开销,显著的提高了数据中心广域网的性能。我们形式化备份路由计算问题作为一个优化问题,提出了一个近似算法来解这个问题。基于Openflow的多级流表(multi-level flow table)和组表(group table),我们进一步提出了一个具体的系统设计和实现方案。大量的实验结果表明我们的方案具有节省时间的优势,并且比现有的错误恢复方案相比可以减少45%的拥塞,利用少量的流表空间开销就可以稳定地在现有的Openflow交换机上实现。

关键词： 数据中心网络; 软件定义网络; 网络更新; 数据平面鲁棒性; 集中式流量工程; Openflow

作者介绍：郑嘉琦，男，南京大学计算机科学与技术系博士研究生。2015年入选国家建设高水平大学公派研究生项目，于2015年10月至2016年10月期间，作为国家留学基金委员会的联合培养博士生，以访问学者身份在美国天普大学(Temple University)交流学习。于2015年1月到2015年6月期间，在香港城市大学担任助理研究员(Research Assistant )，与香港华为诺亚方舟实验室(Huawei Noah' S Ark Lab)合作从事数据中心网络方面的研究。2015年荣获计算机网络国际一流会 议IEEE ICNP最佳论文奖。