无人机集群SDN 交换机转发表的设计与实现*

张 栋，徐任晖，乔庐峰，续 欣，鲁铭洋

（中国人民解放军陆军工程大学，江苏 南京 210007）

0 引言

无人机集群的发展越来越迅速，应用范围不断扩展。当无人机集群应用于战场环境时，其对载荷业务数据和控制数据传输有很高的要求。如图1 所示，无人机集群战场环境包括无线通信、卫星通信、延迟容忍网络等多种通信方式；包括陆地、海上、空中、指挥所等多个作战单元。多种通信手段需要互联互通，多个协议之间需要彼此协调。网络拓扑始终处于变化之中。由于无人机集群是一种由具有移动性的无线设备组成的网络，拓扑始终处于频繁变化的状态，因此无人机集群需要这样一个软件架构，使集群能够自主根据感知情况计算行动资源，动态完成感知、决策、实施等一系列任务。无人机集群在向分布式、大规模、智能自治方向发展，重点需要集群自治、人机组队、集群感知、集群组网和集群智能[1]这5 种能力。此外，为了有效应对军事任务需求，无人机集群还要能够克服固定架构网络的不足，适应战场未知多变环境，因而需要一个开放、可动态调整的网络架构。

图1 无人机集群战场要素

软件定义网络（Soft Design Network，SDN）具有网络可编程、业务调度灵活、开放性好、成本低的特点，因此基于SDN 架构的无人机网络研究日益得到重视。软件定义网络的网络架构由美国斯坦福大学Clean Slate 研究组提出[2]，具体如图2 所示。SDN 设计初衷是为了使硬件标准化，用软件对所有的设备进行统一控制。通过编程实现对硬件数据转发规则的控制，从而达到对流量进行自由操控的目的。

图2 SDN 体系结构

现今SDN 主要应用于数据中心业务。SDN 技术能很好地契合数据中心网络的集中网络管理、虚拟机部署和智能迁移、灵活组网多路径转发、虚拟多租户、云计算基础设施服务（Infrastructure as a Service，IaaS）等方面的需求，非常适合在数据中心网络中应用。SDN 处理大容量数据时，其资源管控、队列调度能力比较强，对功耗不敏感[3]。SDN应用于数据中心时，仅用于处理2 层交换或3 层交换，不能满足多层交换的需求。如图3 所示为典型无人机集群网络，图中共有3 个无人机网络，每个无人机网络都有一个负责人master，master 具有组织协调功能，负责协调各项资源。集群中任何一个无人机都可以充当master。无人机之间、无人机集群之间可能采用不同的网络协议手段。例如，无人机集群之间采用的是延迟容忍网络（Delay Tolerance Network，DTN）协议，集群内无人机之间采用无线传输控制协议（Transmission Control Protocol，TCP）等协议。

图3 无人机蜂群

综上，SDN 应用于无人机网络需要满足以下需求：（1）小型化、低功耗、集成度高；（2）满足大容量数据交换需求；（3）要具有服务质量（Quality of Service，QoS）保证能力。

传统流表功耗较高，硬件资源消耗较大。查找时，传统流表采用片内查找的方法，片内资源较少，表项数量不可能做得太大。因此亟须一种新的算法统一设计流表和规则表，功耗较低，并且能够处理大容量数据。

本文设计一种流表算法，采用多级流表查找方式。每一级流表关注不同的字段。根据实际应用需求，灵活组合形成不同级的流表。流表级数越高，查找优先级越高。例如，最高级的流表关注源IP地址、目的IP 地址、源端口号、目的端口号、服务类型字段，次一级流表关注源IP 地址、目的IP地址和服务类型字段，最低一级流表关注源IP地址、目的IP 地址。将规则表和流表统一设计，降低资源消耗，同时兼顾灵活性、功耗、查找速度，使其达到平衡状态，更加适用于大容量查询的场景。

1 Open Flow 协议

Open Flow 是开放网络基金会（Open Network Foundation，ONF）给出的SDN 架构中的首个标准协议，用于定义控制器和转发设备之间的接口。Open Flow 协议将网络设备的控制层面和数据层面解耦合实现网络流量的控制和管理，现已成为SDN最重要的南向接口标准。自从2009 年12 月发布第一个版本以来，Open Flow 协议已经有多个版本发布，2014 年8 月发布最新的1.5 版本。交换机通过Open Flow 协议与控制器进行通信，控制器使用Open Flow 协议下发指令给网络设备，它可以添加、更新和删除网络设备中流表的表项。交换机通过解析数据包匹配流表中的特定字段，执行控制器下发的后续操作指令。Open Flow 使用流水线来完成包的匹配工作。在Open Flow v1.0 版本中，还未提出多级流表的概念，整个交换机都只使用一个流表，包含非常多的流表项，每一个流表项的字段均为全匹配域。在后续的版本中才出现了多级流表的概念。

Open Flow v1.1 版本协议中规定多级流表。许多硬件厂商受到自己设备原始设计的限制，很难提供足够的支持，目前普遍支持的只有能力受限的两级流表，灵活性低。此外，传统的网络协议字段大多是5 元组（源IP 地址、目的IP 地址、源端口号、目的端口号、网络协议），而Open Flow 协议包含更多的协议字段，如图4 所示，在Open Flow v1.1版本中就包含有数据链路层、网络层、传输层在内的12 个协议字段。为了在数据转发时提供更丰富、更灵活的规则，Open Flow v1.5 版本协议包含的字段数量已达40 多个[4]。这些字段数量多、长度不等、匹配方式不同，导致数据包的转发速度和存储效率下降。数据包的转发速度决定着Open Flow 交换机的吞吐能力。数据包转发速度和存储效率的降低已经成为Open Flow 交换机提高转发性能的瓶颈，因此，设计一个高效的流表匹配算法对SDN 的发展至关重要。

图4 Open Flow 协议包头流表项

2 SDN 交换机硬件结构设计

SDN 交换机和传统交换机本质上都是根据规则将接收到的数据进行转发，区别在于遵循的规则标准不同。传统交换机得到网络数据后，要对数据包进行解析，之后进行链路发现、地址学习、路由建立、协议控制等一系列步骤，再决定数据转发的端口，这大大降低了传统交换机的工作效率。SDN 交换机将传统交换机需要完成的复杂的逻辑控制和计算交给控制端完成，交换机只需要执行控制端下发的指令就可以完成转发。

本文设计的SDN 交换机结构如图5 所示，是基于Xlinx ZYNQ-7100系列开发板（Field Programmable Gate Array，FPGA）实现整体架构。片内包括处理系统（Processing System，PS）侧的处理器平台、可编程逻辑（Programmable Logic,PL）侧的逻辑部分。处理器平台和逻辑部分通过高级可扩展接口（Advanced eXtensible Interface，AXI）与总线连接。片外为双倍速率同步动态随机存储器（Double Data Rate SDRAM，DDR）和Flash 等存储载体。逻辑部分包括以太网MAC 控制器接收模块MAC_RX、以太网MAC 控制器发送模块MAC_TX、交换单元、转发表（流表）、分组处理单元、输出队列管理器、DTN 消息处理引擎和TCP 引擎等。转发表通过分组处理单元与交换单元连接。交换单元有一端口，与DTN 消息处理引擎和TCP 引擎连接。DTN 消息处理引擎通过DDR 接口电路与片外DDR3 存储连接。片外各有一块DDR3 存储和Flash 存储，作为处理器平台工作的内存和闪存。

图5 SDN 交换机硬件结构设计

MAC 接收控制器接收上一节点传来的数据，并将数据传递给后级分组处理单元。分组处理单元将数据帧头中的关键信息，如源IP、目的IP、源端口、目的端口、服务类型等抽取出来，并将这些关键信息传入转发表（流表）。转发表（流表）收到这些信息后根据优先级匹配相应的流表项。如果匹配成功，则将查找结果返回给分组处理单元；如果未匹配成功，则将传入的信息丢弃。分组处理单元接收到查找结果后，根据结果中的输出端口映射位图、数据帧长度及转发优先级等信息形成该数据帧的本地头，后由交换单元转发至相应的端口。

3 转发表（流表）的设计与实现

3.1 设计思路

转发表（流表）是SDN 交换机的核心单元。转发表（流表）应满足以下条件：（1）添加表项时，表项信息中带有优先级；（2）优先级可以根据业务需求灵活配置；（3）查找表项时，从优先级最高的表项到优先级最低的表项依次查找；（4）采取多级流表查找的方式；（5）考虑使用静态随机存储器（Static Random Access Memory，SRAM）实现查表结构，降低资源消耗，更加适用于大容量查询的场景。

为满足以上条件，设计以下算法实现功能。首先采用算法1 实现表项的添加。

算法2 描述了流表表项删除的过程。删除流表表项时，首先根据需要删除的关键字clear_key 搜索四桶哈希电路中关键字的key 值。若能搜索到，则删除key 所对应的表项；若不能搜索到，则返回未搜索到信号clear_nak。

算法3 描述了表项查找的过程。查找表项时，首先提取出关键信息；其次根据关键信息，按照优先级由高到低的顺序依次匹配表项。如果匹配成功，则输出查找结果；如果并未匹配成功，则继续查找下一优先级的表项；如果到最低一级优先级仍未匹配成功，则输出查找结果为全0。

3.2 四桶哈希查找电路

流表项的存储与查找采用四桶哈希查找电路。哈希查找电路的工作原理是利用哈希函数建立关键字到哈希表地址空间的映射，将关键字进行哈希散列运算得到哈希值（Hash），并将哈希值作为存储地址来存储表项。这种映射是一种压缩映射，不同的关键字可能会产生相同的Hash，从而导致冲突。为了尽可能减少哈希冲突，可以采用哈希多桶技术，这里采用四桶哈希表结构[5]。

四桶哈希技术通过增大哈希表的位宽，使得一个Hash 对应的存储空间中可以同时存储4 个关键字及其对应的结果信息，从而减少哈希冲突。本设计中的哈希查找电路的关键字是目的IP 地址、源IP 地址、源端口、目的端口、服务类型等从帧头中提取的关键信息。本设计中，关键字可以根据业务需要灵活配置，只要关键字位数小于或等于128 位即可。输出结果是流号（flow_id）、输出端口映射位图、源MAC、目的MAC 等。同样的，输出结果在写入时也可以根据业务需要灵活配置，只需要输出结果位数小于或等于144 位即可。

哈希查找电路实现的功能有表项添加操作、表项删除操作和表项查找操作。表项添加操作是在Hash 对应的存储中写入流表项。哈希查找电路添加表项时，利用哈希函数计算关键字key 得到Hash，以Hash 为地址将关键字key 及其对应的result 写入，完成表项添加操作。哈希查找电路查找表项时，根据关键字key 值计算出Hash 值，通过Hash 值读取4 个哈希桶中对应的表项。表项匹配成功，得到相应的查找结果result。哈希查找电路进行删除操作时，根据关键字key 得到Hash 读取4 个哈希桶中对应的表项，将该表项全部清零，完成表项删除操作。

3.3 优先级划分标准

整个转发电路中，优先级划分的标准是一个关键问题。当优先级划分的标准确定后，才能明确各个表项的优先级。优先级的划分应该满足以下条件：（1）添加表项时应该带入优先级；（2）表项查找时，可能会产生多个结果，这时需要通过优先级确定输出结果；（3）查找时先查找优先级较高的表项，再查找优先级较低的表项；（4）要能够根据业务需求灵活设置表项的优先级。

综上，本文设计采用匹配中关键信息的多少来划分优先级，即能匹配中的关键信息越多优先级越高，匹配中的关键信息越少优先级越低。当添加表项时，关键字key 值的高8 位作为优先级的数值。

如图6 所示为包含优先级的数据帧结构。添加流表项时，关键字key 值高8 位为优先级数值，优先级越高数值越大。key 值中除需要匹配的数据位外，其余数据位均为0。表项查找时，从数据帧中提取关键信息后，组建查找关键字se_key。se_key值高8 位为优先级数值，se_key 值中除需要匹配查找的数据位外，其余数据位均为0。

图6 包含优先级的数据帧结构

如图7 所示为查找流程。当数据帧进入查找电路后，经过帧提取，得到不同优先级的查找关键字se_key_1,se_key_2,…,se_key_n。首先查找优先级最高的关键字se_key_n。如果能够查找到，则直接输出结果；如果不能查找到，则查找优先级低一级的关键字se_key_n-1。对于关键字se_key_n-1，如果能查找到，则输出查找结果；如果不能查找到，则依次类推，继续查找优先级低一级的关键字。如果最低优先级的查找关键字se_key_1 也不能被查找到，那么输出查找结果全0。

图7 查找流程

4 仿真分析

本文以Xilinx ZYNQ-7100 开发板为硬件平台搭建SDN 交换机电路。其转发表（流表）算法电路仿真如图8 至图12 所示。图8 和图9 为表项添加仿真结果。

图8 表项添加仿真结果

图9 表项查找仿真结果1

图8 中共添加4 个流表项，在图中分别以数字1 到4 标出，标1 处至标4 处的优先级依次增大。由cpu_add_ack 信号值为1’b1 可知，4 个表项添加成功。通过add_key 信号可以看到，这4 个表项匹配分别为：表项1 仅匹配目的IP 地址32’hc0_a8_01_01，表项2 仅匹配源IP 地址32’hc0_a8_01_02，表项3匹配目的IP地址32’hc0_a8_01_01和源IP 地址32’hc0_a8_01_01，表项4 匹配目的IP 地址32’hc0_a8_01_01、源IP 地址32’hc0_a8_01_02、协议类型8’h11、源端口16’h99_98 和目的端口16’h99_99。

图9 给出了表项查找仿真结果。由于数据帧提取后匹配表项的优先级由高到低，所以图9 中se_key 有2 个值，即它匹配中了表项3。表项3 对应的动作action 为从端口3 和端口2 转发数据。从图10 可以看到，数据已经从端口3 和端口2 转发出去，表项查找成功。

图11 为表项删除仿真结果。clear_key 是表项3对应的关键字，删除的是表项3。由于表项3 删除，且表项查找时总是由优先级高的表项到优先级低的表项。因此再次查找时，查找结果应为表项2。表项2 对应的动作action 为从端口3、端口2 和端口1 转发。从图12 可以看到，数据已经从端口3、端口2 和端口1 转发出去，表项3 删除成功。根据表1 所示的资源利用率统计表，查找表（Lookup Table，LUT）资 源 利 用 率 为15.01%，触 发 器（Flip-Flop，FF）资源利用率为10.33%，块状存储器（Block Ram，BRAM）资源利用率为39.21%。整体资源消耗率较低。每秒最高支持6×107次查找。

表1 资源利用率统计表

图11 表项删除仿真结果1

图12 表项删除仿真结果2

5 结语

本文给出了一种针对无人机集群的SDN 交换机的系统设计方案，由数据收发单元、交换单元、转发表（流表）、分组处理单元、输出队列管理器、DTN 消息处理引擎和TCP 引擎组成。为满足多样化的业务需求，设计的流表可灵活配置转发优先级，灵活设置表项关键字及其对应的匹配结果，搜索键值最高支持128 bit。针对SDN 交换机关键电路在Xilinx ZYNQ-7100 平台开发板上进行了设计与仿真分析，结果表明，转发表（流表）电路可以满足多样化业务需求，并能为不同业务流提供所需的QoS 保证。