论文阅读一：SDN 中基于流重定向的 MPLS 标签算法

54 阅读 0 评论 36 点赞

我是靠谱客的博主拉长鸡，最近开发中收集的这篇文章主要介绍论文阅读一：SDN 中基于流重定向的 MPLS 标签算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

名词解释：

Software-Defined Network, SDN: 软件定义网络

Ternary Content Addressable Memory, TCAM: 三态内容寻址存储器

Multi-Protocol Label Switching, MPLS: 数据包封装多协议标签交换

Segment Routing, SR: 分段路由

FRML: 基于流重定向的MPLS标签算法

“摘要：针对软件定义网络中数据平面三态内容寻址存储器(TCAM)性能受限导致的流表下发拥塞问题，提出一种基于流重定向的多协议标签交换算法。利用源节点交换机流重定向和路径交换机下放MPLS标签的方法，占用部分数据链路带宽来缓解TCAM更新流表速率过慢的情况，同时增大系统容量。实验结果表明，与传统OSPF算法相比，该算法可以减小60%的链路负载和近90%的流表项插入延时，并能够增加最多200%的系统容量。”

0 概述

FRML通过设置触发阈值，当路径中需安装的流表数超过阈值时，选取路径上合适的交换机，仅向该交换机下发添加标签的流表，之后的交换机只需根据打好的标签即可选择相应端口的转发操作，以缓解交换机中下行控制链路资源紧张的状况。

1 分析与建模

问题分析：受TCAM性能限制，流表项更新速率为200条/秒；当系统内突发流量过大或遇到恶意攻击时可能会出现TCAM存储空间充足但流表无法及时更新到TCAM的情况，导致SDN网络下行控制链路拥塞，新流无法及时传输。

优化目标：使下行控制链路负载因子最小

约束条件：（1）表项插入延时约束；（2）交换机容量约束；（3）数据链路开销约束

2 算法设计

主要方法：（1）基于OpenFlow协议周期性收集流表安装分布情况和接口状况；（2）预测下一周期的各交换机流表安装负载，将下周期可能超载的源节点交换机的流量重定向到相邻的负载较低的交换机，作为新的源节点进行路径计算；（3）计算路径中如果存在下行控制链路负载超过阈值的交换机，则对该条流采用MPLS方式下发流表，借用一部分数据链路的带宽来缓解下行控制链路负载过高的问题。

优势与代价：降低复用路径上的流表安装负载，利用邻居节点分担源节点的流表安装负载；同时付出增加数据链路负担的代价。

源节点重定向算法

$fleft ( v_{i} ,v_{ij}right )$ ：交换机 $v_{i}$ 重定向到 $v_{ij}$ 的流表数

R：重定向阈值

T：重定向下限（T<R）

$fleft ( v_{i} right )$ ：交换机 $v_{i}$ 待下发流表数

假设交换机 $v_{i}$ 有邻居交换机 $small v_{i1},v_{i2},cdot cdot cdot ,v_{ip} epsilon v_{i}$ ，且 $small fleft ( v_{i1} right )< fleft ( v_{i2} right )< cdot cdot cdot < fleft ( v_{ip} right )$ ，则：

规则1 当 $small fleft ( v_{i}right )< r$ 即交换机负载小于重定向阈值时，不进行重定向，则：

$f_{t}^{}left ( v_{i},v_{ij} right )= 0$

规则2 当 $small fleft ( v_{i1} right )< r$ 即负载最小的邻居节点负载低于重定向阈值,且 $small fleft ( v_{i} right )-t< r-fleft ( v_{i1} right )$ ,则：

$f_{t}left ( v_{i},v_{i1} right )= fleft ( v_{i} right )-t$

规则3 当 $small fleft ( v_{i1} right )< r$ ， $small fleft ( v_{i} right )-t> r-fleft ( v_{i1} right )$ ，且对于 $small v_{ij}, j=1,2,cdot cdot cdot ,m,m< p$ ，有 $small fleft ( v_{ij} right )< r$ ，且 $small left ( m-1 right )r-sum_{j=1}^{m-1}fleft ( v_{ij} right )< fleft ( v_{i} right )-t< mr-sum_{j=1}^{m}fleft ( v_{ij} right )$ ，即 $v_{i}$ 中流量总数减去T后，多出的流量可以重定向到m个邻居节点，且这些邻居节点均不过载，则：

$left{begin{matrix} f_tleft ({v_{i},v_{ij}} right )=r-fleft ( v_{ij} right ), j=1,2,cdot cdot cdot ,m-1 \ \f_{t}left ( v_{i} ,v_{im}right)=fleft ( v_{i}right )-left ( m-1 right )r+sum_{j=1}^{m-1}fleft ( v_{ij} right ) end{matrix}right.$

规则4 当 $small fleft ( v_{i1} right )< r$ ， $small fleft ( v_{i} right )-t> r-fleft ( v_{i1} right )$ ，且对于 $small v_{ij}, j=1,2,cdot cdot cdot ,m,m< p$ ，有 $small fleft ( v_{ij} right )< r$ 以及 $small fleft ( v_{i(m+1)} right )> r$ ，且 $small fleft ( v_{i} right )-t> mr-sum_{j=1}^{m}fleft ( v_{ij} right )$ ，即 $v_{i}$ 中流量总数减去T后，多出的流量全部重定向到邻居节点后仍有多出流量，则：

$f_{t}left ( v_{i},v_{ij} right )=r-fleft ( v_{ij} right ), j=1,2,cdot cdot cdot ,m$

规则5 当 $small fleft ( v_{i1}right )> r$ ，且 $small fleft ( v_{i} right )-r> fleft ( v_{i1} right )-r$ ，即邻居节点均超超载但仍有负载低于 $v_{i}$ 的节点，则：

$small f_{t}left ( v_{i},v_{i1} right )=frac{fleft ( v_{i} right )-fleft ( v_{i1}^{} right )}{2}$

规则6 当 $small fleft ( v_{i1} right )> r$ ，且 $small fleft ( v_{i} right )-r< fleft ( v_{i1} right )-r$ ，即 $v_{i}$ 为所有节点中负载最小的节点，则：

$f_{t}^{}left ( v_{i},v_{ij} right )= 0$

算法步骤描述如下：

MPLS算法

将路径信息作为额外标签封装在原始数据包中，只需在源节点和路径上某几个交换机节点下发流表项对标签信息进行封装，其他交换机只需读取MPLS中的端口信息，将数据包从相应的端口发送出去即可。

算法步骤描述如下：

算法复杂度分析：O(m+n)，m为控制器数量，n为交换机数量。

(1)检测交换机超载情况；（2）遍历源节点的邻居节点，并选择合适的邻居节点对流量进行重定向；（3）选择流量进行MPLS标签安装。

最坏的情况即是所有的交换机都需要选择一遍。

3 实验验证

性能指标：（1）系统的负载因子 $small omega$ ；（2）最大流表插入延时 $small frac{1}{c_{d}left ( nu right )-delta _{i}}$ ，假设流表项插入速度 $small c_{d}left ( nu right )$ 为每秒200条；（3）网络吞吐量，即网络能够承载的最大的流量数。