软件定义网络(software-defined networking，SDN)^[1]中，控制器将不同网络应用产生的更新策略编译成等价的规则，然后将其下发到相对应的交换机中。交换机收到规则后，本地CPU将规则解析成三态内容寻址存储器(ternary content addressable memory，TCAM)可以识别的微指令，最后将这些微指令更新到TCAM中。也就是说，用户策略的更新是通过更新交换机流表中的表项来实现的。表 1显示了一个包含5个规则的流表样例。其中：*表示wildcard。可以看出，流表规则通常由优先级、匹配域以及相应执行动作组成。样例中的匹配域字段包含源IP地址、源端口号以及协议域。

不同应用产生的更新事件的延时需求具有多样性^[2]。数据中心中，流量工程为了实现流量预测，要求更新在几百ms内完成^[3]。蜂窝网络中，设置路由的延时必须在30~40 ms，以确保用户能够及时与网络服务交互^[4]。与上述有严格延时限制的更新事件相比，部分网络例行维护的更新相对没有那么紧急，只需要在流量较低时执行就可以，比如晚上。

一方面，TCAM表项中规则的匹配域会存在重叠，称之为规则的相互依赖^[5-6]。这种依赖使得流表的更新问题变得复杂。一条更新规则往往会触发多条TCAM表项搬动，造成更新时间的增加。另一方面，现有SDN交换机中TCAM多为单端口设计。TCAM读操作和写操作是互斥的。当TCAM进行流表更新时，数据包查找被阻塞，这使得数据平面的转发受到影响。因此，实现快速更新并同时保障数据包查找对于提高网络性能非常重要。

目前解决SDN流表更新问题的研究中，部分工作^[5-8]在不改变现有TCAM接口基础上，阻塞查找数据包，进行规则更新。这类算法的重点是尽可能地减少每条规则更新带来的表项移动，从而减少更新时间。偏序图理论(partial order theory, POT)算法^[5]将规则之间的依赖关系建模为偏序图，并在偏序图上计算移动代价。RuleTris^[7]提出了一种基于动态规划的算法来计算规则移动代价，但是RuleTris没有考虑更新规则和TCAM中已有规则发生冲突的情况(具体描述见节3)，这会导致匹配错误。这些阻塞TCAM方案^[5-8]忽视了查找的延时需求，可能会导致查找包的丢失，或者是需要大量的额外存储空间来缓存等待查找的数据包。还有一些工作通过改变采用单一TCAM即单端口TCAM的结构，来降低更新代价^{[5, 9-10]}。CoPTUA^[9]基于双端口TCAM提出一种无锁的更新算法，使得查找和更新能够同时进行。POT算法^[5]也研究了将相互依赖的规则尽可能地存储在不同的TCAM中。以上这些方法虽然通过改变现有硬件结构能够取得比较好的效果，但是现有硬件无法直接应用这些算法，还增加了算法的实现成本。

不同于以往的研究，本文：1) 提出多个网络应用的流表更新通过前端应用整合同时下达后，应优先响应紧急程度高的任务；2) 改变以往更新优先访问TCAM的思路，更新操作和查找操作穿插地访问TCAM，减少查找等待以及相应的存储代价。为此，本文设计并实现了基于TCAM的流表更新系统UPSys(flow table update system)。具体地，本文有以下主要贡献：

1) 基于不同更新事件的延时需求不同，设计并实现更新重排模块，使得紧急的更新能够得到快速响应。

2) 针对不同的流量特征，采用4种调度策略，使得单端口TCAM能够被合理地使用。为了让调度模块尽可能发挥作用，设计了一种“可打断”算法，保证TCAM随时从更新切换到查找情况下，数据包匹配不会出错。

3) 实现了流表更新算法的测试平台，现有以及后续的更新算法都可以在该平台进行相关测试。

实验结果表明，UPSys中高延时等级、次高延时等级更新的平均延时下降幅度分别达到22.8%和12.1%，代价是低延时等级更新的延时稍有增大。综合看来，UPSys通过3个模块的配合以及不同调度策略的使用，其性能在完全侧重更新和完全侧重查找之间取得了平衡。

基于TCAM的流表更新系统UPSys由数据包解析模块、调度模块、更新规则重排序模块、更新微指令转换模块、TCAM、关联SRAM以及出口模块等组成。各个模块之间互联关系以及数据流如图 1所示。图 1中：ACL表示访问控制列表(access control list)，NAT表示网络地址转换(network address translation)。一方面，在数据平面，数据包从入口模块进入，数据包解析模块将流表查找所需要的字段提取出来，送往查找请求队列等待调度模块调度，同时将数据包净荷缓存。另一方面，在控制平面，诸如防火墙、L3路由以及流量管理等不同应用产生的更新请求经前端模块整合并解析成为流表更新规则。更新规则重排模块考虑到不同更新规则需要响应的紧急程度不同，对更新规则进行重新排序。更新规则重排模块将紧急的更新规则调整到前面，将计算资源以及TCAM存储资源优先分配给更紧急的更新规则，使之能够得到更快响应。更新微指令转换模块预先构建数据结构，将调整顺序后的更新规则“翻译”成一系列微指令。微指令是TCAM可以执行的原子指令。单端口TCAM读操作和写操作需要共享TCAM物理端口，这意味着流表的查找和更新需要互斥地访问TCAM。调度模块依据不同的调度策略，为查找数据包以及更新微指令生成执行序列，然后将其送往TCAM执行。如果到来的是查找数据包指令，TCAM则输出关联静态随机存取存储器(dynamic random access memory，SRAM)的索引值，该索引值会进一步地送到SRAM进行查询，查询所得动作结果将送到出口模块。最后，出口模块将数据包载荷以及相应动作结果组装后输出。

图 1 基于TCAM的流表更新系统UPSys框架图

图选项

更新请求越紧急，延时等级就越高。多个网络应用的规则更新通过前端应用整合后，以批量的形式同时下达。为了改善高延时等级更新请求的响应时间，本文设计了重排序模块，其作用是将到来的流表更新规则进行重新排序，优先执行延时等级高的更新。

直观上来说，采用贪心策略是最优的选择，即按照延时等级从高到低的顺序重新排列并下载规则。但是，更新规则相互依赖，而存在依赖关系的两条规则不能交换顺序，否则会导致交换前后，对于同样的数据包出现查找结果不一致的情况。因此，本文需要寻找一种更新规则下载序列，在满足更新表项依赖约束下，尽可能地满足高延时等级规则的更新需求。本文的解决思路分为两步：1) 确定到达的一批更新规则之间的依赖关系；2) 在保持一致的前提下，优化更新规则的下载序列。

对于同时到达的一批规则，要找出所有更新规则之间的依赖关系，最直观的做法是两两比较更新规则，检测它们是否相交，算法复杂度为O(N²)。显然，这种简单的两两比较算法的复杂度过高。

首先讨论更新规则域个数为1时的情况，同理可推广到更新规则多维的情况。本文用区间来表示更新请求的匹配域。所有区间范围构成集合S。首先找到所有区间起始点的最小值，即min(t_i.start)，以及结束点的最大值，即max(t_i.end)，并记录二者的中间点，该点便是整个区间范围的中间点mid。所有区间中，一部分区间t_i满足t_i.start < mid < t_i.end，把它放到集合S_center中；其余区间范围中，将满足t_i.end < mid的区间放到集合S_left中，将满足t_i.start≥mid的区间放到集合S_right中，这样便将所有区间范围划分到S_left、S_center以及S_right 3个子集中。表 2的例子包含8个更新请求的区间表示；图 2中，本文将这些请求区间用线段表示。

图 2 依赖检测：利用List_start检测相交关系

图选项

基于3个子集合可以得出，对于集合S_center，区间范围都和中间点mid相交，因此集合中区间范围两两相交。除此之外，还有两部分依赖关系需要继续考察。第一部分，S_left和集合S_right中的相交关系；第二部分，S_center中的区间还有可能和集合S_left、集合S_right中的区间相交。比如，图 2中S_left中t₁与S_center中t₅存在相交关系，t₂与S_center中t₃、t₅存在相交关系。对于第一部分依赖关系，可以用递归的方法对它们进行检测。为了加速第二部分相交关系的查找，可预先构建辅助数据结构：将S_center包含的区间，�