abstract

目前针对SDN网络更新优化都是集中在控制平面，数据平面也存在优化空间，为了减少流表项更新时间，首先可以使用依赖图（DAG）更新交换机上的流表项，使用DAG可以避免一些不必的流表更新。本文提出了一种流表更新算法FATSRULE，①利用贪心算法加DAG实现部分性能优化②考虑了算法的可扩展性问题。
文中进行了实验对比，本文的算法对于大小为1K的流表对标最新的算法快了100倍。（性能优化真的超级多）。

index term: Software-Defined Networks, TCAM, OpenFlow, greedy algorithm, flow update

Introduction

SDN对网络更新时间的响应时间决定了控制层的敏捷性， 运营商网络中要求重路由要在25ms内，避免丢包或者拥塞。根据最新的测量结果，一个商业的open flow交换机1s最多处理42条流表更新。
流表更新延迟的时间主要用于增加，删除，修改流表项，openflow交换机处理更新效率低的原因是因为它使用tcam.（可以看做能进行并行查询的有序数组），主要用于快速查找，但是更新并不高效。

流表项在TACM中从top到bottom存储，物理地址递降。如果一个数据包可以匹配多个流表项，那么最高地址的流表项优先匹配选择。 流表更新过程中，可能为了维持优先级造成大量的流表项移动。

实际上，不仅基于OpenFlow的交换机，而且5G移动网络都高度依赖TCAM更新效率。 据报道，一些新的5G防火墙设计使用TCAM来提高其检测，区分和选择性阻断效率.

考虑两个维度解决效率问题：

一. 减少控制器发送给交换机的流表更新项数量。例如使用一些调度方法。
二. 交换机中使用算法减少TCAM中流表项移动。更新过程中使用最小依赖图DAG（有向无环图），可以减少很多不必要的流表项移动。

使用DAG需要一个police compiler,功能是将流表项更新转化为DAG图。
对应的，需要一个TCAM update scheduler,功能是将DAG调度转化为TCAM中流表项移动。 RuleTris 这篇论文设计了第一个方面，没有考虑第二个。

本文提出FastRule, 高效的可扩展的流表项框架，通过提供高性能的TCAM更新调度程序，可以在1k大小的流量表中实现每次更新0.04毫秒的固件时间。

并且计算更新调度的时间复杂度从 减少到O(n), 其中n是TCMA的大小，Cavg是DAG的平均直径。根据测量，对于n=40k的流表，Cavg一般小于15，这个数字远远小于n.

实验将在 ONetSwitch上实现，这是一个可编程硬件，实验结果对标RuleTris，实验结果快100倍。
同时FastRule也适合不同的交换机具有可扩展性。

background

A. flow dependency

如果incoming packet匹配两个流量项，需要提供一个执行匹配顺序，这就是流依赖（flow dependency）

定义：

flow entry A is dependent on a flow entry B if B should be matched first,
We also use A → B to indicate A is dependent on B directly

B.Flow entry update in existing hardware switches

之前提过，TCAM更新慢的主要原因是需要维持一些基于优先级的流依赖， TCAM中每个流表项都拥有物理地址，当数据包匹配多个流表项总是返回最高地址的流表项。如果需要增加一个流表项，首先需要找到一个位置，移动所有的低物理地址的流表项，腾出一个空间。相当于插入排序，如果有N个流表项，平均需要移动N/2次。

C.Dependency graph

移动所有的流表项性能低下，但我们只移动具有依赖关系的流表项会大大提高性能。
如下图插入C*A, 可以只移动两个流表项。

定义:

The minimum dependency graph, which is a kind of Directed Acyclic Graph (DAG) commonly used to describe the flow dependency in a flow table.

抽象模型:

node fu—flow entry
directed edge from node fb to fa—node entry fa is dependent on entry fb.
if fa is dependent on entry fb ,phyaddr(fa) must be higher than phyaddr(fb). 这里我有疑问. A依赖于B， B需要先执行，所以B的物理地址需要更高

下图是一个符号表示列表

图的直径等于图中两个节点之间的“longest shortest path”，Cmax表示流表中流依赖的复杂性。大多情况下Cmac<<n.
一般一个DAG（从路由表或者访问控制列表转化的），可能包含几个不相连的部分，不相连的部分互相不影响，因此Cavy<Cmax<<n.

D.TCAM update scheduler

定义：

For inserting a flow entry into the TCAM, after the correct place for the newly inserted entry is chosen, a sequence of flow entry movements is applied in order to make the chosen space free in the TCAM， such a sequence is called update sequence.

(I, f, A) 表示插入操作，I-insert， f-flow entry, A-address, eg, (I,C ∗ A, 0x5)
(D, A) 表示删除操作.

对于上图1-③中更新操作，可以表示为： (I,C∗A, 0x5), (I,∗∗A, 0x2), (I,∗∗∗, 0x1) 。

THE WORKING FLOW OF FASTRULE

fastRule工作流程如图2所示：

first stage: compiler.

• 有很多实现的方案，可以利用这些工作，比如论文RuleTris。
• 输出是：node, 也就是流表项f以及f需要满足的流表依赖。

The second stage searches for a sequence of TCAM entry movements

• 设计一个贪心算法寻找最优解
• 这个算法不断寻找移动最小步数的地址，最终找到可行的地址，每个候选地址关联一个metric，测量值越小表示性能越好，移动次数越少。

third stage is the TCAM

• 应用更新序列到tcam

图2示例解释：

首先利用贪心算法为f找到候选地址集，选择metric小的值A，为f的插入地址。获得A地址原有的流表项fp = val(A), 将fp作为新的f, 继续贪心寻找候选地址集。 知道找到一个空地址，循环结束。
算法时间复杂度为O（Cavg）.

显然获取最小测量值是最重要的，给出三种方法，根据不同需求获得最小测量值。
1）**on-demand:**每次都从头计算候选集中所有的metric，时间复杂度O（Cavgn）, g综合时间复杂度O（Cav^2n）
2)Pre-compute with array: 使用一个数组存储所有流表项metric，每次循环结束更新metric。每次选择最小metric时间复杂度O（n）, 每次更新时间复杂度0（Cavg）综合时间复杂度O（Cavg*n.）每次遍历metric需要遍历地址也就是tcam, 所以时间复杂度O（n）
3） Pre-compute with BIT：使用一个改进的BIT（binary Indexed Tree）存储所有候选集的metric值，每次循环结束更新。每次选择最小metric时间复杂度为o(logn), 更新metric有O（Cavg(logn)^2）.

定义:

firmware time :As we have mentioned above, the time for the second stage is called firmware time,
TCAM update time:the time for the third stage is called TCAM update time.

IV. GREEDY ALGORITHM

A.On-demand: finding candidate addresses

当需要插入一个流表项f, 具有依赖关系fa->f->fb,那么f的地址在范围add(fa)+1到add(fb)之间，

B. Address metric computation

M（A）表示为地址A的metric值。简单来说就是需要移动的流表项数目，从A地址开始移动流表项，一直到找到一个空地址。
定义：

M(A) is the number of nodes in a specific path P(A) in DAG that starts from val(A) and ends with val(Al). The out-degree of val(Al) must be 0.

作者提出了伪代码：不知道是否理解偏差，伪代码仿佛缺少一个循环。

我的理解为：
对于地址A，原地址A的流表项为h = val(A), 寻找DAG中依赖h的所有节点中，物理地址最大的一个（最接近h的节点），他的物理地址赋值为新一轮的地址A，继续寻找，知道找到一个空地址。
疑问：循环过程不是寻找两个物理地址之间有没有空就可以了 。。。。否则一定要找到很多的节点替换。。。
理解：因为需要找A的测量值计算，如果A地址所在的流表项是一个依赖很多的流表项不符合要求，我们总算法中的确是有一个候选地址集的，所以这只是一个测量方法，大循环中寻找可用的地址集合，如果第一轮有空地址，直接结束循环，如果都没有空的，选择一个测量值小的地址，测量值小就意味着需要移动的流表项小，这就是我们这个算法计算的原理。

C. Greedy algorithm

update sequence: 上文提过，当插入一个f, 以及地址A都已经选定，需要确定一个移动流表项的顺序。这就是update sequence.
这是本节探讨的主要内容

如下：

• 5-9表示为节点f找到合适地址A并且插入。
• 10-12表示循环找到update sequence
• 13表示如果有空位置，循环结束
• 5-9 结束之后，fp = val(A)变成新一轮的节点f, 他的候选地址为A+1–succ(A)
• 理解succ(A)为fp在G的依赖中最小的地址。
  
  论文简单证明了算法的正确性，只要存在空余空间DAG又是无环图，总能找到插入方案。

如图3是一个算法调用的例子。

ps： 假设总是高地址有空位，所有M的计算方式是依赖，不是被依赖。–之后可以检查一下。

D.Using an array data structure to store metrics

通过数组M[]保存每个地址预先计算的测量值。
算法过程如下：

更新每次U(F)调度之后的节点的metric值。

示例如图4