软件定义卫星网络(software-defined satellite network, SDSN)将星载转发设备原本紧密耦合的控制与转发逻辑分离，通过控制平面的集中管控，高效地进行业务路径规划及星上资源优化配置，从而提升整个网络的服务能力^[1-5]。与地面网络不同，卫星网络节点在服务来自地面基站的IP数据包的同时，还可能接收来自其他航天器的基于国际空间数据系统咨询委员会(Consultative Committee for Space Data Systems, CCSDS)协议甚至自定义网络协议的分组转发任务。因此，SDSN数据平面的转发设备存在多协议分组转发的需求。多协议分组转发会增加卫星节点中过滤规则的数量及存储开销，而星上存储资源是严格受限的，因此在SDSN数据平面存储过滤规则时进行压缩能够有效提高网络业务支持能力。

软件定义网络(software-defined network, SDN)或SDSN架构采用流表来存储过滤规则。通过对传统路由设备中转发表的匹配字段及转发动作的扩展，OpenFlow^[6]定义了部署于SDN数据平面的支持丰富过滤规则及处理指令的流表结构。OpenFlow 1.1版本首次提出基于多级流表的流水线转发机制，通过将单流表中的字段拆分存储至多级流表，可有效缓解字段间的乘积效应(字段取值的Descartes积)导致的规则数量扩张，缩减流表存储消耗。OpenFlow标准不规定具体的多级流表构建方案。为了有效拆分字段以实现高效的流表存储压缩，已有研究取得了大量的成果，主要可分为3类：基于字段共存/互斥关系的流类别拆分，如H-SOFT^[7]及其改进算法^[8-9]、Field Trimmer模型剪裁等^[10-12]，可有效消除通配字段带来的存储浪费；基于字段重复率的流表构建算法^[13-14]可有效缓解乘积效应带来的存储冗余；以及二者混合的字段拆分方案，典型如Two-step算法^[15]，根据流类别及字段重复率分2步将单表映射为多级流表，可取得较好的压缩效果。

SDSN场景下，多协议转发将导致严重的流表规模扩展问题。由于不同协议字段间存在语义歧义，不同协议的字段无法实现流表存储的共享。例如，以太帧分组的前6字节代表的是媒体接入控制(medium access control，MAC)地址，而CCSDS的高级在轨系统(advanced orbiting systems, AOS)帧中该位置则代表传输帧首包头字段，若将二者直接存储至同一流表，则很可能导致一个IP分组的MAC地址被错误地匹配到一个记录AOS帧的表项上，从而执行错误的指令动作，造成网络传输故障。对于典型的转发设备，“匹配-动作”流水线仅支持单协议，由于语义歧义的存在，若要支持多协议分组转发，则需要针对每种协议单设一条流水线，即对于M种协议，流表规模扩展至单协议下的M倍。此外，交换设备的存储资源具有最小不可分颗粒^[16]，各流表规则通常无法完全填充分配给其存储块，由此造成的填充浪费加剧了流表规模扩展的存储开销。已有的流表压缩算法主要针对单协议场景下的存储压缩需求，无法解决多协议场景下流表规模扩展所带来的严重存储消耗。

对此，本文提出了一种适用于多协议分组转发的多级流表压缩算法。本文首先介绍了多协议流表的结构模型及其存储优化问题，进而提出了满足流表初始化及表项更新2种压缩需求的二维扩域搜索(2-dimensional expanded-field search, 2D-EFS)算法。仿真结果表明：对流表初始化过程，2D-EFS算法的存储压缩效率高于已有单协议算法，可压缩86%的流表存储消耗，与全局搜索算法接近，同时还有效降低了初始化耗时；在表项更新阶段，2D-EFS算法具有最低的更新耗时，并可取得76%的平均存储压缩效率，优于已有单协议算法的性能。

1 多协议流表结构及存储压缩分析 1.1 多协议流表结构

为解决多协议场景下的流表规模扩展问题，本文构建了一种多协议流表结构。如图 1所示，受转发设备的延迟约束，设流水线最多支持K级流表，并支持M种协议的分组转发。PID_j代表第j个协议的协议标识(protocol identification，PID)，f_j^e为第j个协议的第e个字段的匹配值。在传统多级流表结构下，由于流表/流水线仅能支持单个协议字段的存储，M种协议则需要开销M条流水线(共O(MK)个流表)的硬件资源。对于多协议流表结构，引入PID作为各协议的唯一协议标识后，通过将PID与字段匹配值拼接存储至各表项，可消除多协议字段间的语义歧义，使多种协议字段合并存储于同一流表。多协议流表配置一条流水线即可支持M种协议的分组转发，有效缩减了流表规模(O(K)个流表)，从而节省了资源开销。

多协议流表的分组转发过程如下：输入分组经解析模块进行协议区分后^[17]，不同协议的数据包将获得其对应的PID(承载于元数据上)。将PID与包头字段共同组成搜索字，参与各级流表的匹配并执行相应指令。当最后一级流表查找完成后，以其在各级表中的匹配结果作索引，该分组对应的动作索引模块中的动作则会被执行(动作索引的实现取决于具体的算法，如Cross-Producting^[18]、聚合折叠位向量(aggregated and folded bit vector，AFBV)算法^[19]等)，执行完成后的分组将被输出以进行后续处理。

多协议流表结构将协议种类数与流表规模解耦，有效缩减了多协议场景下的流表规模，却增加了流表存储压缩的复杂性。在传统单协议场景下，压缩算法仅解决将原本多个匹配字段如何拆分至各级流表中并最小化存储消耗的问题。在多协议流表结构中，多级流表的拆分不仅涉及单协议内各字段如何“横向”拆分的问题(即传统算法所解决的问题)，更需要优化不同协议的字段间“纵向”合并以共享流表存储，即问题从原来的一维“横向”拆分，转变为二维的“横向”拆分加“纵向”合并。对于M个协议、K级流表来说，其可行解范围扩展了(K!)^M-1倍，大大增加了算法的求解复杂度。

1.2 存储压缩分析

对于第i个协议，设过滤规则集合为R_i，含N_i个匹配字段，各字段位宽由向量w_i=(w₁, w₂, …, w_Ni)表示，其中w_i表示第i个字段的位宽。将第i个协议在第j个流表中的字段存储情况表示为列向量b_{i, j}=(b₁, b₂, …, b_Ni)。其中：b_i=1表示第i个字段存储于该表中，b_i=0则表示其不在。此外，假设最小存储颗粒宽度为Q、深度为D，并考虑到存储颗粒的种类区别，设三态内容寻址存储器(ternary content addressable memory, TCAM)与静态随机存取存储器(static random-access memory, SRAM)的每比特存储开销比值为α_s，则多协议流表j的存储可表示为(以α表示存储开销归一化为SRAM的系数，则当流表j为SRAM时取α=1，否则取α=α_s)

$ S_{j}=\alpha Q D \sum\limits_{i=1}^{M}\left\lceil {\frac{f\left(R_{i}, \boldsymbol{b}_{i, j}\right)}{D}} \right\rceil \left\lceil {\frac{\max\limits _{i=1}^{M}\left(\boldsymbol{w}_{i} \boldsymbol{b}_{i, j}\right)+p}{Q}} \right\rceil . $

(1)

其中：“ $\left\lceil {} \right\rceil $”为向上取整; f(R_i, b_{i, j})表示规则集合R_i在b_{i, j}的映射分布下不同值的计数，即第i个协议在第j个流表中的表项数; p为PID位宽。另外，设e_N为长度为N的全1列向量。考虑不进行存储优化时，各协议过滤规则单独存储于各单级表，则未压缩时的总存储消耗为

$ S_{O}=\alpha Q D \sum\limits_{i=1}^{M}\left\lceil\frac{f\left(R_{i},\boldsymbol e_{N_{i}}\right)}{D}\right\rceil\left[\frac{w_{i} \boldsymbol e_{N_{i}}}{Q}\right\rceil. $

(2)

定义多协议流表的存储空间压缩效率为

$ \eta=1-\frac{\sum\limits_{j=1}^{K} S_{j}+S_{\text {action }}}{S_\rm{O}}. $

(3)

其中S_action表示实现最终动作索引所需的存储消耗，与具体选择的算法有关。在最大化压缩效率的同时，本文在多级流表的构建过程中还有以下考虑：

1) 各协议的每个字段存在且仅能存在于唯一一级流表中。这主要是出于简化流水线执行的考虑。如果一个字段存在于多个流表中，那么对该字段的动作将需要重复多次匹配查找才能最终决定，这会增加流水线的执行复杂度，不利于效率的提升。由于第i个协议在整个多级流表中的字段分布为矩阵B_i= [b_{i, 1}, b_{i, 2}, …, b_{i, K}]，则该策略可表示为

$ \boldsymbol{B}_{i} \boldsymbol{e}_{K}=\boldsymbol{e}_{N_{i}} . $

(4)

其中i=1, 2, …, M。

2) 不同字段根据其查找性质放置于不同流表中，如MAC地址适合采用SRAM进行精确匹配，而IP地址适合采用TCAM进行掩码匹配。定义第i个协议与第j个协议的字段间的关系矩阵为M_{i, j}=[m_uv]N_i×N_j。其中：m_uv=1表示第u个字段可以与第v个字段共存于同一流表中；反之，m_uv=0则表示不能共存。式(5)应当被满足，

$ \boldsymbol{B}_{i} \odot \boldsymbol{B}_{j}^{\mathrm{T}} \vee \boldsymbol{M}_{i, j}=\boldsymbol{M}_{i, j}$.

(5)

其中：i，j=1, 2, …, M，符号“⊙”和“∨”分别表示Boole矩阵的Boole积和并集。

综上所述，多协议流表压缩问题可总结为如下0-1非线性整数规划问题：

$ \begin{aligned} &\max \eta\left(\boldsymbol{B}_{1}, \cdots, \boldsymbol{B}_{M}\right)=1-\frac{\sum\limits_{j=1}^{K} S_{j}+S_{\text {action }}}{S_{\mathrm{O}}}, \\ &\text { s.t. }\left\{\begin{array}{l} \boldsymbol{B}_{i} \boldsymbol{e}_{K}=\boldsymbol{e}_{N_{i}}, i=1,2, \cdots, M, \\ \boldsymbol{B}_{i} \odot \boldsymbol{B}_{j}^{\mathrm{T}} \vee \boldsymbol{M}_{i, j}=\boldsymbol{M}_{i, j}, i, j=1,2, \cdots, M, \\ \boldsymbol{B}_{i}=\left[b_{u v}\right]_{N_{i} \times K}, b_{u v} \in\{0,1\}, i=1,2, \cdots, M . \end{array}\right. \end{aligned} $

(6)

上述0-1非线性整数规划问题作为非线性规划问题的子集，属于NP难问题，难以通过多项式时间算法进行求解。

2 二维扩域搜索算法2D-EFS

针对以上问题，本文提出一种高效求解算法2D-EFS。该算法的核心是：假设各匹配字段均单独存储于各流表中，每次选择合并后存储冗余增加最小的2个流表进行字段融合(同协议字段间“横向”拼接，异协议字段间“纵向”合并)，直至最终流表数量满足级数约束。2D-EFS算法包括应用于流表初始化过程的2D-EFS-1算法和应用于表项更新过程的2D-EFS-2算法2个部分。

2.1 多协议流表初始化算法2D-EFS-1

对第j个流表，定义其存储的字段用0-1矩阵描述为

$ \boldsymbol{T}_{j}=\left[\begin{array}{cc} \boldsymbol{B}_{1, j}^{\mathrm{T}}, & {[0]_{1 \times\left(N_{\max }-N_{1}\right)}} \\ \boldsymbol{B}_{2, j}^{\mathrm{T}}, & {[0]_{1 \times\left(N_{\max }-N_{2}\right)}} \\ \vdots \\ \boldsymbol{B}_{M, j}^{\mathrm{T}}, & {[0]_{1 \times\left(N_{\max }-N_{M}\right)}} \end{array}\right]. $

(7)

其中N_max=max(N₁, N₂, …, N_M)。式(5)对T_j的约束可简化为

$ \begin{gathered} \boldsymbol{B}_{i_{0}, j} \odot \boldsymbol{B}_{i_{1}, j}^{\mathrm{T}} \vee \boldsymbol{M}_{i_{0}, i_{1}}=\boldsymbol{M}_{i_{0}, i_{1}}, \\ i_{0}, i_{1}=1,2, \cdots, M . \end{gathered} $

(8)

为简化算法的计算复杂度，在统计各级流表中的表项条目数时，采用随机抽样的方式进行计数。设样本规模为Sp，则T_j的存储开销为

$ S_{j}=\alpha Q D \sum\limits_{i=1}^{M}\left\lceil {\frac{f^{\prime}\left(R_{i},\boldsymbol{b}_{i, j}\right)}{D}} \right\rceil\left\lceil {\frac{\max\limits_{i=1}^{M}\left(\boldsymbol{w}_{i} \boldsymbol{b}_{i, j}\right)+p}{Q}} \right\rceil . $

(9)

其中：f′(R_i, b_{i, j})=|R_i|f(R_i^Sp, b_{i, j})/Sp，代表流表中表项条目的抽样计数结果，|R_i|和R_i^Sp分别代表规则集合R_i的基数及其Sp个抽样值所组成的样本集合。2D-EFS-1算法的具体执行步骤如图 2所示。

2.2 多协议流表表项更新算法2D-EFS-2

在转发设备运行阶段，各级流表的表项处于不断更新之中，控制器需及时运行压缩算法，以维持转发设备较高的流表存储效率。但与初始化阶段不同，用于表项更新阶段的流表压缩算法应简单快速，以保障表项更新速度。因此，本文表项更新过程中的流表重压缩每次仅选取2个流表进行字段重组。

用于表项更新的2D-EFS-2算法的核心是：将各级流表两两组合，计算每个组合当前存储消耗之和与两表的规则合并存储于单表时的存储消耗比值，比值越大，反映当前两表的表项压缩效果越差(即对乘积效应的消除越差)。每次重压缩将选择当前存储消耗比值最大的一个组合进行字段重组：以两表中的规则作为原始规则集，运行2D-EFS-1算法。

为减少算法运行频率，本文对表项更新次数进行计数，仅当其超出设定的更新阈值θ时才执行2D-EFS-2算法。具体过程为：在流表初始化后，实时记录表项更新次数。当表项更新次数达到θ时，执行压缩算法，并依据其计算结果对流表进行重新填充，同时清零表项更新计数。2D-EFS-2算法的具体流程如图 3所示。

2.3 算法分析

2D-EFS算法初始化及更新过程的计算复杂度分别为O(M³N²C-MK²C)及O(M³N₀²C+MK²C)。其中：C代表流表中各协议的规则计数，N₀代表进行重压缩的2个流表中的各协议字段个数。由于采用抽样计数，有C=Sp为常数，且考虑到K受限于实际转发设备的延迟约束，因此2D-EFS算法的整体计算复杂度为O(M³N²)。

由于在字段融合过程中同时考虑同协议字段间的“横向”拼接及异协议字段间的“纵向”合并，2D-EFS算法的求解实际上是“二维”迭代进行的。与传统算法按照字段间的共存/互斥关系或字段重复率(O(N)种可行解)将单表逐步拆分为多表不同，2D-EFS算法采用字段融合的方式(两两流表组合，O(N²)种可行解)逐步生成多级表，这大幅扩展了求解过程中每步迭代的搜索域，从而有效避免局部极值，提升了压缩效率。理论上，搜索域的扩展将会消耗更多的计算量，因此为了避免随着流表规模的增大所带来的计算量激增，本文在计算冗余表项时采用抽样计数的方式，从而有效保证了算法的执行速度。

在SDSN场景下，2D-EFS算法可以由控制面执行，直接运行在高轨卫星上，也可以由地面运控中心执行完之后再由高轨卫星负责表项分发，这取决于具体场景下的卫星网络结构设计。另外，在SDSN的流表初始化阶段结束后，对于常规的流表更新，通常可直接运行2D-EFS-2算法。对于非静止轨道卫星，当其产生服务区域切换时，由于流表项会产生大量变动，此时应直接运行2D-EFS-1算法，以保证较高的压缩效率。

3 仿真结果

本文仿真以规则集生成软件ClassBench-ng^[20]产生的规则为原始规则，并进行适当扩充，包括IPv4(含目的MAC、IPv4五元组字段)、IPv6(含目的MAC、目的IP、目的端口、传输层协议标识字段)及AOS(含航空器标识、虚拟信道标识字段)3种不同协议。仿真中，除MAC地址、传输层协议标识、航空器标识、虚拟信道标识4种字段为精确匹配外，其余字段均为掩码匹配。动作索引模块采用Cross-Producting算法^[18]实现，另设p=2、Q=8、D=1 024，并取Sp=1 000、α_s=6.4^[21]。

从已有压缩算法类别中分别选取H-SOFT^[7]、流表映射机制(flow table mapping scheme, FTMS)^[13]及Two-step^[15]3个典型算法作为对比。由于仅考虑了单协议场景下的存储优化，因此对比算法在仿真过程中针对各协议分别进行存储压缩(生成多条流水线，每条流水线长度不超过约束K)，最终的压缩效率为总压缩存储与总原始存储之比。为进一步验证算法性能，针对所述多协议流表结构，还将2D-EFS算法与全局搜索算法(穷举所有可行解以寻找全局最优值)进行了对比。

在实际转发设备中，转发速率、延时及存储消耗是多级流表构建的重点考虑因素。1) 转发速率。由于多级流表以流水线形式工作，因此转发速率主要由瓶颈流表的查找速率决定，与多级流表本身关系较小。2) 延时性能及存储消耗。在常用查找算法下(硬件并行查找、Hash查找等)，单个流表的查找延时为常数级，故多级流表的延时性能主要取决于流表级数，流表级数越大，延时越大，但存储压缩效率也会越高(字段间乘积效应变小)。因此，延迟性能与存储压缩是相互制约的，应在保证延迟的情况下进行流表存储的压缩。在下文的仿真中，各算法之间的压缩效果对比均以同等延迟保障(即相同流表级数)为前提进行。

由于在流表初始化及表项更新的仿真中，H-SOFT算法的压缩效率始终为0，因此下文仿真图中并未画出H-SOFT的结果曲线。导致这一结果的原因在于算法应用场景的不同：H-SOFT算法针对地面SDN网络中的OpenFlow转发设备，以字段间互斥关系及丰富的流类别为依托，采用特定启发式策略进行流类别划分。对于多协议网络下的分组转发，由于协议区分，各协议内规则集合无互斥字段，且流类别有限，因此H-SOFT算法无法正常工作。实际上，不仅是H-SOFT算法，基于它的改进算法^[8-9]以及近年提出的依字段关系拆分流类别的算法(如Field Trimmer模型剪裁^[10]、独立规则集位提取(bit extraction of independent rule subsets，BEIS)压缩^[11]、RETCAM^[12]等)，在SDSN场景下均存在同样的问题。作为这类算法的代表，从H-SOFT算法的应用效果可以看出，SDSN多协议网络场景下的过滤规则与地面SDN网络区别较大，传统针对地面SDN网络的流表构建算法适用性受到限制。

3.1 流表初始化阶段仿真对比

图 4展示了初始化阶段各算法压缩效率的对比，其中IPv4、IPv6、AOS三者的规则条目数比值取3∶2∶1。

仿真结果表明，对于流表初始化，2D-EFS算法的存储压缩效率比FTMS算法提高9%以上，比Two-step算法提高40%以上，可压缩86%的存储消耗，与全局搜索算法相近。图 4a显示了在各流表级数约束下压缩效果对比。随着流表级数的上升，2D-EFS和全局搜索算法压缩效率的提升逐渐平缓，这是由于此时各协议的字段趋向于独立存储于各级表中，字段间乘积效应逐渐得到完全消除，压缩效果趋于最大值。由图 4b可知，随着规则条目数的上升，各算法压缩效率逐渐升高，这是由于对于相对稳定的网络，转发节点中各字段的取值不会随着规则条目数的上升出现较大变化，因此规则条目数增多更多表现为字段间Descartes乘积的增加，乘积效应的存储冗余变得更为明显。此外，更多的规则条目数也使压缩效率受表项填充浪费的影响变小，存储压缩的效果得以提高。

实际上，在不考虑存储颗粒时，2D-EFS算法的压缩效率比全局搜索算法下降约10%左右，而考虑存储颗粒时，由于存储颗粒对实际的存储消耗存在“向上取整”的效果，因此仿真结果显示二者具有相近的压缩效率。当流表级数较高(6~8)时，各算法压缩效率本应因乘积效应的完全消除而趋于最大值，但对于Two-step算法，由于流类别拆分占用流表，乘积效应消除有限，且受多协议流表规模扩展的影响，因此其压缩效率低于本文所提算法；而对于FTMS算法，由于其未考虑SRAM与TCAM之间的存储区别，并受到多协议流表规模扩展的影响，因此压缩效率无法达到最优。此外，Two-step和FTMS算法在设计时均未考虑存储颗粒的影响，在规则条目数或流表级数较小时，由于填充浪费的存在可能出现压缩率为负的情况，即存储优化后的多级流表反而比原始单表消耗更多的存储空间。虽然Two-step算法压缩效果有限，但是由于它对流表按流类别进行预拆分，可以支持分组包在不同流类别的流表中并行匹配，因此有助于加速数据包过滤流程。

各算法的初始化运行耗时对比如图 5所示。随着流表级数的上升，全局搜索算法的运行时间呈指数增长；与之相比，2D-EFS算法的运行时间基本保持不变，缩短约1~3个数量级；与FTMS和Two-step算法相比，2D-EFS算法可明显缩短初始化耗时。随着规则条目数的增长，各算法的初始化耗时均逐渐增加，但2D-EFS算法仍具有较小的运行耗时。

在流表级数较小时，受字段匹配类型的影响，可能的拆分方案十分有限(如2级表时，仅存在“TCAM表+SRAM表”一种拆分方案)，因此全局搜索算法具有较低的运行耗时。此时，其余算法由于依旧按照特定的搜索原则进行迭代计算，其耗时略高于全局搜索算法。

3.2 表项更新阶段仿真对比

设初始化规则集合中IPv4、IPv6、AOS协议各占1 600、1 600、800条，更新时按照2∶2∶1的概率随机对3个协议的规则进行更新，总计更新10 000条规则。在相同的流表级数约束下，对比2D-EFS算法与其他算法在不同更新阈值下的平均压缩率(每100次更新进行1次压缩率采样)及总更新耗时，仿真结果如图 6所示。

由图 6a可以看出，在更新阶段，2D-EFS算法可取得76%的平均压缩效率，与FTMS算法相比提高26%以上，与Two-step算法相比提高63%以上。由图 6b可以看出，在更新耗时方面，2D-EFS算法具有最小的总更新耗时，可有效保障表项更新速度。此外，由图 6还可以看出，随着更新阈值的增大，2D-EFS算法平均压缩效率下降，但总更新耗时也随之减小，因此在实际使用中应当在压缩效率和更新速度之间根据需求进行折中，选择合适的更新阈值。

4 结论

本文针对SDSN多协议业务场景下的多级流表存储压缩需求，分析了其所面临的流表规模扩展问题，构建了适用于多协议转发的多级流表模型，并提出了多协议流表压缩算法2D-EFS。该算法考虑了存储颗粒对流表压缩带来的影响，采用字段逐步融合的方式生成多级流表，包括流表初始化及表项更新2个阶段。仿真结果表明：在流表初始化阶段，2D-EFS算法可取得86%的存储压缩效率，与全局搜索算法相近，优于已有的H-SOFT、FTMS及Two-step算法，并有效缩减运行耗时；在表项更新阶段，2D-EFS算法可取得76%的平均存储压缩效率，压缩能力高于已有单协议算法，同时具有最短的更新耗时，可有效保证表项的快速更新。