软件定义网络(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个模块的配合以及不同调度策略的使用，其性能在完全侧重更新和完全侧重查找之间取得了平衡。

1 基于TCAM的流表更新系统设计

基于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进行查询，查询所得动作结果将送到出口模块。最后，出口模块将数据包载荷以及相应动作结果组装后输出。

2 更新规则重排序模块

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

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

2.1 基于区间树的规则依赖检测

对于同时到达的一批规则，要找出所有更新规则之间的依赖关系，最直观的做法是两两比较更新规则，检测它们是否相交，算法复杂度为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中，本文将这些请求区间用线段表示。

基于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包含的区间，按照区间的起始点顺序进行排序，排序结果存储在List_start中；类似地，按照区间的结束点顺序进行排序，将结果存储在List_end中。因此，S_center包含的区间关联了两个List。

S_left(S_right)中每个区间，在List_start(List_end)中进行顺序查找，直到遇到第一个不相交的区间便停止查找。图 2中，对于t₁，需要在有序链表List_start中进行顺序查找，检测到t₁与t₃不相交后，便可以停止查找。由此，得到所有与S_center相交的区间。对S_left和S_right递归执行该算法，可以得到所有依赖关系。可以看出，递归执行的过程中得到的结果形成了一棵树；而且由于每次都是选择所有区间的中间点划分S_left与S_right，因此递归的深度不超过O(log N)。事实上，整个算法并不需要建立树结构，只需要辅助的数据结构存储相关链表信息即可。

与最简单的两两比较算法相比，基于区间树的依赖关系检测算法实际上减掉了很多不必要的检测操作，这是因为算法递归地将规则集合分为3个子集，其中S_left和S_right中的规则是没有必要去比较的，这一部分比较在改进算法中被剪枝剪掉了。

2.2 更新请求重排

更新请求重排的目的是在不破坏依赖关系的前提下，将高延时等级的更新规则尽可能地提前。同时到达的N条规则以及它们之间的依赖关系可以构成一个有向无环图(directed acyclic graph, DAG)。求解更新请求重排序列可以转换成DAG图的拓扑排序全排列问题。一个有向无环图的拓扑排序是该图节点的一种排序，该图中如果存在一条有向边从节点u出发到达节点v，那么拓扑排序生成的序列中，节点u需要在节点v之前。然而，有向无环图的全排列问题已经被证明是一个非确定多项式(non-deterministic polynomial，NP)完全问题^[11-12]，且采用复杂度高的回溯操作解决本问题性价比较低。

本文提出采用基于贪心策略的近似算法，在多项式时间复杂度下，求得相对较优的解。算法执行过程如下：

1) 每次找到DAG中所有没有前驱即入度为0的节点；

2) 从中选出延时等级最高的节点进行输出，然后删除这些节点以及以这些节点为起点的有向边；

3) 删除后再找到入度为0的节点；

4) 重复上述过程，直到当前DAG图为空，或者不存在没有前驱的节点为止。

3 TCAM更新算法

一条更新请求经过本地CPU翻译成多条微指令。为了使调度模块能够调度微指令，需要TCAM更新算法输出的微指令序列能够被随时打断，同时要保证TCAM查找请求不会出错。另外，TCAM更新算法还需要尽可能少地移动TCAM表项，以便更新请求能够尽快地部署。系统将优先级高的规则放到索引值小的表项中(下文中也会表述为TCAM上方)。

流表更新可以分为3类：删除、修改、插入。对规则的删除，只需要直接在DAG图上将规则置为无效。修改操作可以理解为先删除规则，再插入规则。因此，优化流表更新的关键在于优化规则的插入。对于规则的插入，不仅要在DAG上插入，而且还要在TCAM中找出一个合适的空位，然后进行相应的表项移动。另外，对于待插入规则R，必须要保证插入完成后，与R相交且优先级比R高的规则都在R的上方；与R相交且优先级比R低的规则都在R的下方，这是更新算法正确的充分必要条件。

首先，需要找到待插入规则R的上界和下界。具体地，在DAG图中，找到R所有前驱规则和后继规则。在后继规则中，TCAM索引值最小的规则为R的下界low(R)；同理，在前驱规则中，TCAM索引值最大的规则为R的上界high(R)。

其次，需要判断是否出现规则冲突并予以消除。如果high(R)>low(R)，也就是表项low(R)在TCAM上方，表项high(R)在TCAM下方，则表明出现了规则冲突，需要先移动R的上下界，把high(R)移动到TCAM上方，保证上界在上方，下界在下方。

没有规则冲突后，上下界之间的规则都与R没有交叠关系，因此R可以放在上下界之间的任意位置。如果上下界之间存在空表项，那么R可以直接插入。如果上下界之间没有空表项，则将R的下界low(R)取出，将R插入到该位置。对取出的low(R)，递归地寻找它的上下界，直到找到某条下界对应的位置为空，此时更新结束。

在更新时，需要移动的规则在DAG图上构成了一条路径。为了保证更新可被打断，算法实现了以下两点：1) 更新应该从路径的最后一个点开始，而且向TCAM的下方移动，一直更新到第一个点；2) 移动TCAM中的某条规则时，先在新的地方写入这条规则，然后删除当前位置的规则。以上两点使得规则先重复地写在比当前规则优先级低的地方，如果在旧规则删除前更新被打断，转向查找，此时根据TCAM特性，匹配到的仍然是旧规则；当旧规则删除后更新被打断，TCAM会匹配新写入的规则。以上两点保证了更新算法在查找被打断后，流表的匹配结果不会发生变化。

4 TCAM快速更新调度策略设计

流表更新规则经过更新微指令转换模块中的TCAM更新算法转换成一系列TCAM更新原子指令。这些TCAM更新原子指令需要与查找请求互斥地访问TCAM。如图 1所示，调度模块前面设计有两个等待队列，分别缓冲到达的更新请求和查找请求。调度模块的作用就是根据一定策略，从这两个等待队列中读取更新微指令或者待查找数据包，合理地安排读写TCAM顺序。

4.1 调度的动机

现有TCAM更新的研究工作^[5-8]默认随时响应更新，即只要有流表的更新请求到达，数据平面便暂停TCAM的数据包查找，转而执行更新微指令，直到更新完成后，再恢复之前暂停的查找操作。这种随时响应更新的策略，本文称之为更新优先调度策略。该策略尽量地满足了更新方面的性能指标，但是同时也导致当更新流量比较大时，查找得不到响应，造成查找的延时高，甚至丢包，无法满足查找的性能需求。

4.2 改进的更新优先调度策略和改进的查找优先调度策略

本节对传统的更新优先调度策略进行改进，提出改进的更新优先调度策略。图 3显示了改进的更新优先调度策略的执行流程。当查找等待队列利用率超过阈值时，查找十分紧急，调度模块应当优先响应查找。调度模块切换到更新后，启动计时器，当查找等待队列中数据包等待超过一定时间后，也优先响应查找。其他情况下，将到达的查找请求缓存到等待队列中，调度模块优先响应更新请求，以便尽快完成更新。

另一方面，数据包连续进入TCAM时，TCAM会以流水的形式进行查找。当TCAM从执行查找操作切换到执行更新原子指令时，TCAM需要等正在流水线上执行查找的数据包完全输出后，才能进行更新。以本文实验中参考的Cypress半导体公司生产的CYNSE70256 TCAM芯片^[13]为例，从数据包进入到输出结果，需要8个时钟周期，意味着从查找切换到更新，TCAM有8个时钟周期的排空流水线的代价。基于以上考虑，为了减少排空代价，当TCAM执行查找时，会将缓存的数据包处理完后再切换到执行更新原子指令。

相对应地，本文进一步提出改进的查找优先调度策略，其执行过程是把上面过程中“查找”和“更新”相互调换即可。用户可以根据需求选择相应的策略。

对比3种调度策略可以看出，更新优先调度策略总是优先响应更新，由于忽略了查找，导致查找方面的性能得不到保障。改进的更新优先调度策略则是添加了查找方面的性能约束：更新时，数据包等待时间过长或者等待队列有溢出风险，则需要转向响应查找。改进的查找优先调度策略则是在侧重查找的场景中，既不让更新等待时间太久，也不让更新等待队列有溢出的风险。

4.3 自适应调度策略

网络流量在不断地变化，系统目标是能够根据当前状态自动地选择优先响应查找或者优先响应更新。为此，本文设计了一种自适应调度策略，将改进的更新优先调度策略和改进的查找优先调度策略作为自适应调度策略的两个分支。根据当前系统状态，采用某种策略，自动选择执行上述分支。依据的系统状态包括：等待队列中请求数量以及等待时间、最近一段时间查找请求和更新请求的到达时间分布。调度考虑以下两点：1) 根据一段时间内查找和更新请求到达速率来判定切换到哪一个分支。系统不能也没有必要完整记录请求的所有历史状态，而通常情况下，最近一段时间的特征更接近当前状态。另外，考虑到请求到达间隔可能波动比较大，系统取最近一段时间内的数据包到达时间求出平均速率，以避免计算请求到达速率噪声大的问题，也使得系统运行更稳定。2) 等待队列的状态直接反映了当前查找和更新的繁忙程度。

不同调度策略有不同适用场景。用户根据不同更新到达情况以及流量特征选择相应的调度策略。改进的更新优先算法实际上是考虑了查找方面的约束(不能等太久，不能让等待的数据包积累太多)，改进的查找优先调度策略则是在侧重查找的场景中，增加了对更新性能的保障。另外，还有一些场景，更新规则不能被任意打断，此时系统应该采用更新优先算法。比如，网络受到攻击而需要更新重要的防火墙过滤规则时，经过交换机的流量中含有恶意流量，如果未能及时更新规则将其过滤，可能导致较为严重的后果，此时应该采用更新优先算法。

调度模块以及调度策略存在有效区间。具体地，如果更新以及查找流量较小时，等待队列的利用率较低，TCAM能够轻松地应对流量，调度的作用就不那么明显。如果两种流量非常大时，以至于超过了TCAM的处理能力，此时调度策略的作用也十分有限，如果流量短时间不能降下来，就可能存在丢包的风险。如果两种流量介于上述两种情况之间时，如果策略不当，就可能无法满足对查找和更新的性能要求，此时选择合理的调度策略是十分重要的。

5 系统实现和性能评价 5.1 仿真系统设计

图 4显示了仿真系统的框架结构。系统主要包含两个部分：性能测试平台和流表更新系统。其中：流表更新系统由C++语言实现，性能测试平台由C++和Python语言实现。系统采用ClassBench^[14]来生成原始规则集。系统对生成的规则进一步地扩展，生成更新流量。实验中TCAM相关的参数均参考Cypress半导体公司生产的CYNSE70256 TCAM芯片。

将原始规则集随机地分配到两组，一组作为初始的流表规则集，另一组作为更新流量的基础集。之后，为每条更新规则添加延时等级以及到达时间。在仿真系统中，查找数据包的到达时间生成方式有两种：1) 从CAIDA(https://www.caida.org/) 下载真实流量，将数据包到达时间戳映射到更新流量时间区间中。2) 采用合成到达时间。由于真实网络中的更新到达时间难以获取，采用Poisson分布生成更新到达时间。最后，添加了到达时间以及延时等级的更新流量、流表规则集，与相应的查找流量一起输入到流表更新系统中。

5.2 更新规则重排模块性能测试

本节将更新规则重排模块与其他所有模块一起运行，采集每条更新规则的延时，研究高延时等级的更新是否得到快速响应。

将更新规则的延时等级划分为4类：低延时等级、中等延时等级、稍高延时等级、高延时等级。本节研究了添加重排模块、没有重排模块两种场景，4类更新规则平均延时的差异，结果见图 5。上述实验中，低延时、中等延时、稍高延时、高延时等级4类规则数量之比为0.3∶0.3∶0.2∶0.2。由于一条更新规则被TCAM更新算法分解为数条微指令, 因此某一条更新规则的开始时间是其对应的第一条微指令开始执行的时间，结束时间是最后一条微指令执行完成的时间。

从图 5中可以看出，没有重排模块时，各类更新规则延时相差不大。UPSys添加了重排模块后，高延时等级以及稍高延时等级更新规则的平均延时下降幅度分别为22.8%和12.1%。由于硬件资源没有增加，作为代价，低延时等级和中等延时等级更新规则的平均延时则有一定程度的上升。综上可见，重排模块牺牲了一部分低延时等级任务延时，保证了高延时等级任务得到快速响应。

5.3 调度模块性能测试

本节测试调度模块的性能，讨论各种调度策略在各种场景下的表现。待测试的调度策略包括已有研究工作都在使用的更新优先(U)、本文提出的改进的更新优先(UI)、改进的查找优先(SI)以及自适应调度策略(A)。测试性能指标包括衡量查找性能的查找吞吐率、查找延时以及衡量更新性能的更新延时。

首先设定更新流量、逐步增大查找压力，考察查找延时的改变情况，结果见图 6。PPS表示每s到达的数据包的数量(packet per second)。可以看出，更新优先、改进的查找优先以及自适应调度3种策略的后续数据缺失，其原因是在这3种策略下，系统不能及时处理过量的数据包，发生了丢包，导致查找延时不再有效。刚丢包时对应的数据包到达速率为算法的吞吐率，反映了更新策略对查找性能的影响。

更新优先策略总是优先响应更新，因此最先出现丢包，吞吐率最低。改进的更新优先策略，数据包延时较大，但由于加入了数据包快要丢包时优先响应查找的限制条件，使得改进的更新优先能够达到几个策略中最大的吞吐率。改进的查找优先策略在所设定的更新到达分布下，查找延时性能良好，但是当更新积累较多时，需要响应更新，因此出现了丢包。自适应调度策略的性能介于更新优先策略和改进的查找优先策略之间。

接下来讨论设定更新流量、逐步增大查找压力情况下更新延时的变化，结果如图 7所示。原始的更新优先策略只要有更新到达，立即响应更新，因此它的更新延时最低。改进的更新优先策略在速率较低时，平均更新延时接近原始的更新优先策略，但随着查找的压力增大，由于它有保证查找不能阻塞太久的约束条件，从而调度会频繁响应查找，导致更新等待，延时会急剧上升。相反，改进的查找优先策略后期总是触发执行更新，因此更新延时较小。自适应策略则再次取得了平衡。

5.4 系统整体性能测试

本节将UPSys与目前已有研究成果进行性能比较。UPSys__U表示UPSys采用更新优先调度策略，UPSys__UI、UPSys__SI以及UPSys__A含义类似。待比较的TCAM更新算法包括RuleTris、FastUp以及POT工作中第一个算法POT₁。

利用ClassBench生成IPC规则，表项数目为1 000~5 000。固定更新流量和查找流量，测试不同算法的查找延时和更新延时，实验结果分别见表 3和4。由于生成的数据包到达时间具有一定的随机性，同一参数下运行10次程序，取其平均结果。在本节实验参数配置下，POT₁算法在流表数目增多时，移动TCAM次数过多，导致算法性能下降，出现了严重的丢包，延时数据不再有效，因此部分查找和更新延时均未列出。

从表 3和4中可以看出，UPSys采用默认的更新优先的调度策略时，查找、更新延时都比RuleTris、FastUp略高，这是因为在没有规则冲突的情况下，本文提出的更新算法产生的TCAM移动次数比RuleTris、FastUp略多。另外，UPSys采用更新优先策略时，更新性能最优；采用改进的查找优先策略时，更新性能最差。自适应调度策略参数可调节，因此其性能可以在更新优先策略和改进的查找优先策略之间浮动。综合看来，通过采用不同的调度策略，UPSys能够在完全侧重更新和完全侧重查找之间取得平衡。

6 结论

本文设计并实现了基于TCAM的SDN流表更新系统UPSys。多个网络应用的流表更新通过前端应用整合同时下达后，UPSys对延时需求高的规则赋予高优先级，使其能够得到快速响应。UPSys还实现了查找和更新交替执行，减少了缓存查找包的存储需求。仿真测试结果表明，UPSys通过采用不同的调度策略，能够在完全侧重更新和完全侧重查找之间取得平衡。现有更新算法是以单条规则为输入，未来可以考虑批量更新规则的场景下，如何进一步减少TCAM表项移动次数，还可以进一步分析真实的SDN更新特征，以生成更贴近实际的更新规则。