【作者】 李波；

【导师】 田臣；

【作者基本信息】 南京大学 ， 计算机科学与技术， 2019， 硕士

【摘要】 随着网络的迅速发展,传统网络封闭僵硬,功能耦合等弊端日益凸显。为了更加灵活地定制网络功能,将原本高度硬件化的传统网络软件化,增强网络的可编程性,软件定义网络应运而生。在软件定义网络架构中,控制层和数据层实现了分离,控制层可以集中地调度管理数据层,实现整个网络的灵活更新。然而不合理的更新方案不仅会造成网络性能的大幅下降,甚至还会导致整个网络瘫痪。由于软件定义网络中的更新操作相当频繁,因此设计出一套高效可靠的更新系统显得尤为重要。对此,本文分析研究了软件定义网络中不同场景下的更新问题,设计并实现了两种不同的网络更新系统。本文的第一个工作是提出了一个可以主动预测流速率,且对网络整体效用感知的更新系统Hermes。为了更好地分析最大化效用的网络更新问题,此项工作中提出了详细的优化框架,证明了最大化效用的网络更新问题的难度,同时分析了相关算法的复杂度。该系统首先主动预测流的速率,接着采用凸松弛技术获取流量降速方案的初始解,为了进一步增加更新过程中的整体效用,该系统继续采用贪心的方式调整每条流的速率,同时仍然保持更新过程中无拥塞。真机实验和大规模的仿真结果均表明,和现有的工作相比,该系统可以提升约80%的效用,同时减少约40%的更新时间和55%的更新开销。本文的第二个工作主要研究OpenFlow 1.5版本新引入的同步定时更新特性,并基于此特性提出了一个保证更新过程无拥塞的更新系统Chronicle。和第一个工作不同,此项工作不再关心网络效用,而是关注更为一般性的问题,即如何在不对数据流降速的情况下,通过调度每个交换机节点的更新时间,得到一套更新过程无拥塞的更新方案。此项工作引入了时间扩展网络等一系列概念,可以有效地帮助分析和设计基于同步定时网络的更新算法。该系统通过构造资源关系依赖图,找出更新节点之间的依赖关系,为每个节点计算出精确的更新时刻和对应的转发规则,实现整个更新过程无拥塞。真机实验和大规模的仿真结果均表明,该系统可以避免更新过程中瞬时的拥塞,从而减少约63%的更新时间和50%的更新规则数目,与最优解差距平均小于20%。更多还原

【Abstract】 With the rapid development of the network,the disadvantages of the traditional network such as function coupling are increasingly prominent.In order to customize network functions more flexibly and push the network which was originally highly hardware-based to software-based,software defined network technology came into be-ing.In the software defined network,the control layer and the data layer are separated.The control layer centrally schedules and manages the data layer.This helps realize the flexible network update of the whole network.However,the unreasonable update plan will bring many problems,which will not only cause the degradation of network performance,but also bring the catastrophic network collapses.At the same time,up-date operation is very frequent in the software defined network,so it is very important to design an efficient update algorithm.This paper studies the update problem under different scenarios and designs two network update systems.The first proposed system is Hermes which actively predicts the flow rate and perceives the overall utility of the network.In order to analyze the maximum utility network update problem,this work presents a detailed optimization framework.This work also demonstrates the difficulty of the maximum utility network update problem and carefully analyzes the complexity of proposed algorithm.This work first proac-tively predicts the flow rate,and then use convex relaxation techniques to obtain an initial solution.To further increase the overall utility,this work continues to adjust the rate of each flow with a greedy method based on the initial solution,meanwhile guaranteeing congestion-free during update process.Extensive simulation and testbed experiments demonstrate that this work increases the total utility by 80%.At the same time,it reduces the total update time and control overhead by 40%and 55%,respec-tively.The second work is mainly concerned with how to utilize the synchronized net-work update feature proposed by OpenFlow 1.5 to design an update system.The pro-posed system is called Chronicle which can ensure the update process is congestion-free.Different from the first work,this work no longer cares about the network util-ity.It focuses on a more general problem of how to get an update plan guaranteeing congestion-free during the update process by scheduling the update time of each switch instead of reducing the rate of flows.To solve this problem,a series of concepts are in-troduced such as time-extended network,which can be well used to analyze and design update algorithm based on timed update.By constructing resource dependency graph,this work finds out the dependency between update blocks,then calculates the accurate update time and the corresponding forwarding rules for each switch.Extensive sim-ulation and testbed experiments show that this work can avoid congestion during the whole update process,reducing the makespan by 63%and the number of changed rules by 50%compared to state-of-the-art.The average gap between this work and optimal solution is less than 20%.更多还原