摘要
随着软件定义网络SDN的出现和崛起，传统的路由策略和规则放置算法已经不再完全适用。因此，结合OpenFlow协议设计一种能够满足网络操作者目标的高效的路由规则放置算法成为了SDN研究领域一个亟待解决的问题。本课题深入研究了SDN网络的架构与OpenFlow协议体系，总结了时下几个比较优秀的针对不同网络目标或不同环境下的路由规则放置算法，并给出分析且提出了一种新的基于默认路径的路由规则放置算法，与现有算法进行了比较。最后，本课题设计并实现了一个开源的路由规则测试算法框架，使算法研究者能够通过简单的编程接口实现规则放置算法并测试其性能。
背景与动机
课题背景
在传统网络中，交换机负责数据链路层的MAC匹配和帧转发，而路由器负责网络层的IP寻址和数据包转发。交换机和路由器的功能都是预先写入硬件内部的，当需求变更时需要操作人员手工进行配置。 由于网络厂商杂，设备类型多，设备数量大，不同厂商的命令和标准不一致，传统网络的部署和管理非常麻烦。 另外，在传统路由网络中，每个设备独立计算，设备间通信主要通过协议来实现，当流量增大时，设备间的通信开销也随之增大。在这样的背景下，软件定义网络SDN(Software-Defined Networking)的概念应运而生。 SDN是一种网络设计理念，一种推倒重来的设计思想。网络中转发设备的控制层面被逻辑上集中在一起。 数据平面和控制平面分开，就可以认为是SDN，因此，SDN并不是一个具体的技术，而是一种框架。 框架的实现需要具体的技术和协议，SDN网络的重中之重便是OpenFlow协议，它使用像API（应用程序编程接口）这样的流程来设置网络交换机，搭载了OpenFlow协议的交换机就称为OpenFlow交换机。 SDN+OpenFlow实现了控制转发的分离，能够对网络进行集中式控制，可编程，开放接口，因此是一个革命性的网络发展方向，又被称为“下一代网络”。 本课题正是基于SDN网络架构和OpenFlow协议，研究路由规则的放置问题。
课题价值
研究路由规则放置问题对于SDN网络，具有十分重要的现实意义。实际网络中存在着诸如端点规则限制、带宽限制、OpenFlow交换机内存限制等条件，这就要求在进行规则放置时要能够综合考虑网络环境，最优化网络中的流量分配。除此之外，对于区分服务的流量传输、流表可扩展性、流量均匀化等目标，规则放置也发挥着重要作用。具体来说，在流等级约束层面，对不同性质的流区分服务可以使系统工作更高效，首先完成最重要的任务组；在流表规模化层面，所有的控制权限被交给了控制器，就必然要求网络规模增大时能够保证网络服务的稳定性，传统网络恰恰没有这个问题；在流量均匀化层面，使链路上的流量得以均匀分配、减少链路过载现象是由来已久的研究问题，而在以控制器为中心的网络中对流量均匀化的要求就更加突出，直接关系到控制器的工作细节设计。 对路由规则放置问题的研究可以启发对包括但不限于以上三点技术问题的解决方案，并更好地服务现实中的网络对象。
相关工作
在路由规则放置问题上，国内外的研究者们针对不同方面的问题做出了相当部分卓有成效的研究成果，当然也存在亟待解决的问题。 比如在优化本地交换机方面：[DevoFlow][2]使用通配符规则在交换机本地处理短流，[DomainFlow][3]将网络用通配符规则划分为一个域，用精确匹配规则划分为另一个域。[SwitchReduce][4]提出了压缩所有具有相同动作的规则到一个通配符规则中。以上方案可以加快处理已安装规则的效率。虽然它们提升了内存使用率，但是依然不能消除随着网络中流和节点数增加时交换机内存压力呈指数上升的问题。 在路由聚合方面：一些工作提出使用特殊设备来进行规则放置。[DIFANE][5]将最重要的规则放置在附加的叫权威交换机（ authority switches ）的设备上。这样，入口交换机就会将那些没有匹配的包指向这些特殊设备，这就减少了控制器上的负载，与此同时，也减少了需要安装在入口交换机上的规则数量。[vCRIB][6]在管理程序和交换机上都安装规则，在减小资源使用的同时提升性能。其他工作则优化交换机本身上的规则分配。[Palette][7]和[OneBigSwitch][8]生成了能够满足端点规则的聚合规则集合并把它们放置在交换机上，同时也能符合路由规则和最小化资源准则。在其他一些情形中，规则分配被模型化为一个聚焦于最小化交换机上总的能源消耗的受限最优化问题。最后，还有研究人员提出了一个全网络优化来在内存和链路容量限制条件下放置尽可能多的规则。然而无论是Palette还是OneBigSwitch都不能在为满足端点规则而丧失交换机存储资源的场景中使用。 在处理端点规则、网络限制和最大化网络流量方面：一个已知的研究成果叫[OFFICER][9]，它将网络模型化为一个符合端点规则的黑盒子，并且通过松散路由规则从可达资源中获取最大值，而其余（转发规则）不能安装的流量就通过默认路径进行路由。它是一个抽象化的OpenFlow网络的解决方案。然而，它只是在松散路由规则下进行推导，而定义的模型实际是NP难求解的，也缺乏更多的诸如转发时延、服务区分等限制条件的考虑。
课题挑战
本课题的研究主要是基于OFFICER算法，第一步是根据已有的理论推导编程实现它的算法，并测试在不同网络拓扑结构下的算法执行情况。基于此算法，本课题提出一个针对不同优化目标的改进算法LinkRank，使得该算法的性能在部分技术指标上能够好于或持平于OFFICER算法。此外本课题还将援引其他优秀的研究成果如EAR算法[10]设计思路、路由规则聚合技术等。研究过程中本课题采用Mininet搭建实验环境（仿真平台），通过对已有工作成果的仿真来探索路由规则改进的可行方案，并考虑更多场景约束情况下具有通用性的有效规则分配算法。 而针对规则放置，本课题主要难点主要有三： 1. 对新型路由规则问题的设计需要深刻的理论基础认识和严谨的数学建模分析，并和具体的应用场景进行联系； 2. 算法的实现和测试包括对Mininet环境的部署与算法框架的设计，二者必须在OpenFlow协议的基础上无缝融合； 3. 问题的相关假设和实验条件应当基于现实中的网络模型与流量数据，在仿真过程中必须保持环境的一致性从而保证结果的公平性，这就涉及到关于网络拓扑、流量分布等细节的设计。
OFFICER 算法
问题分析
OFFICER算法的研究者针对OpenFlow的规则分配问题提出了一个标准化的通用优化模型，使之能够满足端点规则。所谓端点规则，就是指一条流或数据包穿越网络时需按照操作者的目标从指定入口进入，从指定出口（指定的入口和出口可以是可选集合）离开。例如，共享消费链路经常被网络服务提供商（ISPs）特权占用，数据中心要保证包能够被传送到可以处理它们的服务商那里去。 研究优化的目标是找到一个在OpenFlow网络中转发规则的分配方式，使之既能够满足操作者的目标，即端点规则，又能够满足网络条件的限制。然而，使每一条流都满足端点规则是不太可能的，那些不能满足端点规则的数据包就会通过任意一条默认路径。在OpenFlow环境中，研究者假设了以下条件： 1. 一个对所有OpenFlow交换机可达的中心控制器； 2. 对于不能匹配任何转发规则的流，交换机使用转发到控制器的默认规则。 基于以上假设，研究者将优化模型表达为一个整数线性规划（ILP）问题。为不失一般性，研究者假设一个转发规则适用且仅适用一条流。这样就可以使模型变为一个线性的问题。
该研究试图建立一个F×L的布尔分配矩阵；其中每一个矩阵元素表示某一条流f是否通过有向链路l=(u,v)，其中u,v表示交换机节点。
研究者根据网络条件数学化了网络限制、带宽限制、存储限制、端点规则限制并提出了最大化总体流收益（每条流对应不同的收益权重）的优化目标。但是该优化问题可以简化为一个0-1背包问题，因此是是一个NP难问题，不能直接求解。为了解决这个NP难问题，研究者结合了一种叫做偏转技术的策略提出了一个高效的启发式算法OFFICER。
偏转技术
任意节点对之间的路径数量是会随着网络规模的增大而呈指数级增加的，因此尝试所有的路径是不切实际的。为了减少探索的空间，可以利用已经存在于交换机表项中的默认转发规则。这一想法是在流的出口点和默认路径上的一个结点之间的最短路径上转发一个流的包。因此，一个流的包第一次转发是根据默认路由规则，走默认路径，这样不会消耗任何特定的内存表项，然后它会从默认路径上偏转以最终到达一个出口点。这一方法使得尝试的路径数量是可处理的，同时也能够保有足够的决定权从而在网络的路径多样性中获得好处。决定采用默认路径和出口点之间的最短路径是根据以下事实激励的：路径越短，需要安装的内存表项就越少，就给其他流留出了安装内存表项的空间。
为了实现这一思路，对于每条流而言，在默认路径上的交换机需要被划分等级（排名），这个算法就尝试每一个交换机（从最佳等级开始）直到一个符合所有限制条件的闲置路径的分配被找到。如果这样一个分配是存在的，一个对于这条流的转发规则就被安装在从被选出的在默认路径上的交换机到出口点的最短路径上的每一个交换机中。在默认路径上的每一个交换机的排序是根据用户定义的策略进行计算的。三种可能的策略是： 1. 最近优先（CF）：流的入口链路尽可能近; 2. 最远优先（FF）：控制器尽可能近; 3. 最近边优先（CE）：出口链路尽可能近
在CF（FF）中路径上交换机的权重就是入口链路（控制器）与交换机之间的跳数。而CE中交换机的权重是它与出口点之间的跳数。
LinkRank 算法
讨论（如何才能更好）
总结
[2]: