Gather：一种能够优化这些用于转发控制流的流表项的方法

带内控制（in-band）的SDN网络由于有着良好的灵活性以及部署的经济性，已经受到了越来越多的关注。但是在带内控制的SDN网络中，控制流和数据流共用一个一个物理链路进行转发。因此，交换机需要存储用于转发控制流的流表项。这在一些大型网络，例如数据中心网络中会造成一些接近控制器的SDN交换机流表项过多的问题。大量的流表不仅会带来管理的复杂，还会占用例如TCAM等网络资源。所以我们提出了Gather：一种能够优化这些用于转发控制流的流表项的方法。

设计介绍

（1） 设计根据

下图是传统带内控制下的SDN网络的流表分布图（本文中只关注一个控制器的情况）：

图表 1：传统SDN网络中流表的组织方式

在一个网络拓扑中，如果使用最短路径算法计算各个交换机到控制器的路径，可以得到一个树状的控制拓扑图，Gather便是基于这一树状的拓扑图进行优化。从图可以看出传统网络中流表存储的特点是靠近控制器的交换机需要为之后的子节点存储控制流的流表项，因此越是靠近树根（控制器）的交换机需要存储更多的控制流的流表项。而在交换机数量很多的网络中，例如数据中心网络，这会造成靠近控制器的交换机出现一个明显的流表数量激增的现象。Gather的主要目标是减少这些不必要的流表开销。

（2）设计思路

Gather的基本思路是将拓扑中的交换机划分为一个个组（group）。一个组相当于整个控制树的一个联通子集。同时一个组由一个标签（label or tag）来表示。实现标签的方式有很多，在本文中，我们使用segment rouTIng来实现标签系统。下图是Gather的示意图：

图表 2：Gather 实现流表项优化示意图

从图中可以看出S2，S3，S4被分为一组，所有被发往该组的包都被打上X标签（label）。S2在收到包之后，通过匹配X标签，就会知道该包是发往组内交换机的数据，之后其会继续在流表2中匹配该包的流表，决定转发策略。同时，在对拓扑进行一轮优化之后，仍然可以在现有的分组基础上进行第二轮优化。具体的做法是将组都视作交换机，进行替换。之后会得到一个缩小的拓扑，可以在该拓扑上继续重复优化，进一步减少控制流的流表。但同时数据包中的标签会增加一个。

（3）如何找出有效的组（group）？

可以找出有效的组的方法有很多，可以根据需求自己设计需要的算法。在介绍算法之前，首先给出其中的一些定义：Node distance指一个节点到控制器的中间节点的个数，S指子节点的集合，G是最终输出的组的集合，TIme of opTImizaTIon是指全拓扑优化的次数，一次optimization之后需要修改拓扑（进行组和交换机的替换）。在本算法中，基本的思路是先利用深度优先算法，从叶子节点开始计算。从算法中可以看出，其使用迭代的思路，一直延伸到一个叶子节点后向上逐个节点进行计算和比较。之后其会根据比较的结果决定组的分布。

设计测试

首先，我们对数据包中的label（本论文中使用segment routing实现组的结构）对于转发延迟的影响进行测试。测试结果如下：

图表 3 Label数量对转发延迟的测试结果图

从表格中可以看出label对于转发延迟的影响比较小，即使在3个label的情况下也只比传统转发多了4%的延迟。之后我们对优化流表的能力进行测试，结果如下：

图表 4 流表优化结构示意图

在三种拓扑中可以看出第一次优化的结果普遍较好，而第二次，第三次优化的比例下降的特别快。这是因为在一遍优化，将组替换为交换机之后的拓扑会比优化之前的拓扑小很多。因此可以优化的流表项也会少很多。同时，这与算法的设计也会有一定的关系。