积分商城

最新搜索： 总线标准 电池故障 PMW-HEX KiCad 品为道宣传册 CurrentRanger
您现在的位置是：首页 > 技术资料 > 软件定义网络一致性协同更新算法
推荐星级：
  • 1
  • 2
  • 3
  • 4
  • 5

软件定义网络一致性协同更新算法

更新时间：2019-12-24 08:16:34 大小：1M 上传用户：守着阳光1985查看TA发布的资源 标签：软件定义网络 下载积分：1分 评价赚积分 （如何评价?） 打赏 收藏 评论(0) 举报

资料介绍

为实现软件定义网络的一致性更新,本文提出一种协同利用分段路由、顺序更新、两步复制三种机制的更新算法.算法首先启用分段路由机制,尝试用现有路径规则拼接待更新数据流的最终路径,并根据最终路径是否能由现有规则拼接,将数据流分为可拼接与不可拼接两种.对于可拼接流,分段路由可将最终路径信息封装入数据包包头,使得数据包能立即沿最终路径转发.对于不可拼接流,算法计算最长一致性更新序列,并按照此序列依次更新节点,最后利用两步复制机制来完成剩余未更新节点的更新.并且经实验验证,算法比之前研究提出的算法不仅消耗更少的三态内容寻址存储器的空间资源,并且有更好的适用性与稳定性


部分文件列表

文件名 大小
软件定义网络一致性协同更新算法.pdf 1M

【关注B站账户领20积分】

部分页面预览

（完整内容请下载后查看）
10  
Vol． 46 No． 10  
Oct． 2018  
第
2018  
期
10  
电
子
ACTA ELECTRONICA SINICA  
学
报
年
月
软件定义网络一致性协同更新算法  
，
，
于倡和 兰巨龙 胡宇翔  
(
，
450002)  
国家数字交换系统工程技术研究中心 河南郑州  
:
，
、
、
摘
要
为实现软件定义网络的一致性更新 本文提出一种协同利用分段路由 顺序更新 两步复制三种机制的  
．
，
，
更新算法 算法首先启用分段路由机制 尝试用现有路径规则拼接待更新数据流的最终路径 并根据最终路径是否能  
，
．
，
由现有规则拼接 将数据流分为可拼接与不可拼接两种 对于可拼接流 分段路由可将最终路径信息封装入数据包包  
，
．
，
，
头 使得数据包能立即沿最终路径转发 对于不可拼接流 算法计算最长一致性更新序列 并按照此序列依次更新节  
，
．
，
点 最后利用两步复制机制来完成剩余未更新节点的更新 并且经实验验证 算法比之前研究提出的算法不仅消耗更  
，
．
少的三态内容寻址存储器的空间资源 并且有更好的适用性与稳定性  
:
;
; OpenFlow  
关键词  
中图分类号  
URL: http: / /www． ejournal． org． cn  
一致性更新 分段路由  
:
TP393  
:
A
:
0372-2112 ( 2018) 10-2341-06  
文献标识码  
文章编号  
DOI: 10． 3969 /j． issn． 0372-2112． 2018． 10． 005  
电子学报  
Synergetic Consistent Update Algorithm for SDN Networks  
YU Chang-he，LAN Ju-long，HU Yu-xiang  
( National Digital Switching System Engineering ＆ Technological Research Center，Zhengzhou，Henan 450002，China)  
Abstract: To achieve consistent update in software defined network，a consistent update algorithm which combines  
segment routing，two-phase commit and node scheduling mechanism is proposed in this work． The algorithm first leverages  
segment routing mechanism，which attempts to splice the final path with existing paths． According to whether the final path  
can be spliced by the existing paths，the algorithm divides flows into either segmentable flows or flows that are not segment-  
able． For the segmentable flow，segment routing mechanism can encapsulate the final path information into the packet header  
so that packets can be forwarded immediately along the final path． For the flows not segmentable，the algorithm calculates the  
longest consistent update sequences for them，and updates nodes in accordance with these sequences． Finally，the algorithm u-  
ses the two-phase commit mechanism to complete the update of the remaining nodes． We verified its performance by experi-  
ments and the outcome illustrates that our algorithm not only requires less additional ternary content addressable memory re-  
sources but also has better performance stability and applicability than prior techniques．  
Key words: consistent update; segment routing; OpenFlow  
、
，
网络环路 丢包等一系列异常 所以如何维护更新一致  
1
引言  
，
，
性 保障网络的正常运行 避免各种异常与错误是网络  
．
，
因网络状态的动态变化特性 规则更新是软件定  
更新的关键  
( Software Defined Network，SDN)  
．
义网络  
中的常见现象  
，
更新的一致性 便是确保每个流的转发要么采用  
、
运营商可通过网络更新来调整路由 更改访问权限以  
，
，
．
初始规则 要么采用最终规则 没有第三种选择 而关于  
、
．
完成网络维护 漏洞修补等运维操作 而转发信息表  
SDN  
，
网络的一致性更新 之前已经有了大量的研究工  
( Forward Information Base，FIB)  
的更改是网络更新的核  
FIB  
．
［1 ～ 5］ ( ordered scheduling)  
作 文献 基于顺序更新  
机
，
FIB  
心 用新的  
．
规则替代旧有的  
规则是更新过程的  
，
．
制 即按照特定约束下求得的节点序列来更新网络 虽  
，
本质 网络更新是一个渐进的增量过程 在全网更新完  
( Terna-  
然该机制不会引入额外的三态内容寻址存储器  
ry Content Addressable Memory，TCAM)  
，
，
成前 不同交换机的配置可能是不一致的 这可能造成  
，
资源消耗 但这  
: 2017-11-20;  
: 2018-06-02;  
:
收稿日期  
修回日期  
责任编辑 李勇锋  
:
( No． 61502530) ;  
863  
( No． 2015AA016102)  
高技术研究发展计划  
基金项目 国家自然科学基金  
国家  
2342  
2018  
电
子
学
报
年
种机制的强一致性更新序列未必一定存在［1］ 故而只  
识符序列  
数多种拼接方式 且最终路径可以同时有多个可行的  
1， ＜ u v z w d ＞ ＜ uv vz  
是困难的 因现有路径规则有指  
，
( SID List，SL)  
．
、
、
，
能保证全网策略维护 网络无环 无拥塞等弱一致性更  
新［2 ～ 5］ 文献  
基于两步复制机制  
拼接集 如图 路径  
zw wd ＞ ＜ uvzw wd ＞  
可以有拼接集  
．
［6，7］ ( two-phase com-  
，
mit) ，  
其核心在于让相关节点同时维护初始与最终两种  
， ，  
的方式拼接 显然 第二种  
也可以按  
拼接方式需要安装的  
何找到所有的可拼接流并且分配最优的  
，
SL  
，
，
规则 并通过入口节点为相关数据流所加的不同标签  
短 引入的额外带宽小 所以如  
，
SL  
来决定所采取的转发规则 这类算法一般会消耗大量  
是利用分段  
TCAM GPIA +  
．
，
［8］  
．
的
FED  
资源 除此之外 文献 中提出的  
路由完成网络更新的关键  
算法是协同利用顺序更新机制与两步复制机制来  
． GPIA + FED  
完成网络更新  
算法虽然可以很好的完成  
TCAM  
，
．
网络更新 并减少更新过程的  
ordered scheduling  
资源冗余 但是当  
机制失效或者所求最长一致性更新  
，
序列的节点数目远小于全网待更新的节点数目时 算  
TCAM two-phase commit  
资源逼近  
，
机制  
法所需的额外  
．
，
性能迅速恶化 综上 之前一致性更新算法一般受限于  
．
适用性与资源开销  
SDN  
，
为了实现  
文协同利用分段路由  
commit  
网络的普适低冗余一致性更新 本  
［9］，ordered scheduling  
two-phase  
与
，
FCUA ( Fast Coopera-  
等机制来更新网络 提出了  
tive Consistent Update Algorithm)  
．
，
算法 其中 分段路由可  
以通过现有路径拼接的方式来尝试构建待更新数据流  
，
，
的最终路径 若最终路径可拼接 则可以通过为数据包  
( segment identifier，SID)  
包头加装对应段标识符  
来指导数据包沿最终路径转发 这里  
IP  
的方式  
，
SL  
由于各个数据流之间相互独立 各数据流的  
的
，
SID  
是由各拼接段  
．
寻找与优化问题可利用分治法思想独立求解 而在  
．
，
，
末尾节点的 构成 相应的 若最终路径不可拼接 则  
CASR  
，
SL  
算法中 我们将求解某一数据流  
的问题转化  
( Integer Linear Programming，  
整数线性规划  
ordered scheduling  
two-phase commit  
可以利用  
与
等机制  
0 － 1  
为一个  
． FCUA  
来完成网络更新  
算法具体架构在第二章中有详  
ILP)  
，
，
问题 通过求解所建立的模型 我们可以判断出该  
，
细论述 并且实验证明该算法可以在保持更新过程强  
，
，
，
数据流是否可拼接 如果模型有解 则数据流可拼接 并  
SL．  
，
TCAM  
，
的额外消耗 并且  
．
一致性的提前下 极大的减少  
得到最优的  
明显提升了算法的性能稳定性与适用性  
1
CASR  
．
算法 详细的记述了  
算法的核心思想 根据  
网络的初始与最终配置 算法可以计算出发生变化需  
2) ．  
，
2
算法设计  
(
，
确定待更新数据流集后  
要更新的数据流集合 行  
FCUA  
SDN  
我们提出的  
算法通过三步更新来实现  
，
依次遍历待更新的数据流 对数据流分别建立相应的  
，
网络的一致性更新 第一步通过运行基于分段路由机  
ILP  
，
，
模型并求解 便可判断出数据流是否可拼接 如果  
CASR ( Consistent update Algorithm using Segment  
制的  
Routing)  
，
．
可拼接 则模型的解便是最优的拼接集 对于任意待更  
，
算法 利用分段路由为可拼接数据流安装相应  
，
新数据流 我们首先查找其最终路径所有可能的拼接  
SID，  
，
在保证一致性的前提下 使得数据流可以立即  
的
，
C( 5) ， L  
段在现有路径集中是否存在 并形成集合  
行
而
，
．
沿着新路径传输 并快速更新节点 因不可拼接流可能  
，seg  
，
为数据流最终路径的跳数  
的拼接集中拼接段数量的最大值 随后求解  
seg  
代表当前模型下 数据流  
，
CASR  
．
算法可能无法完成全网更新 所以  
存在 单一的  
，
ILP  
，
模型  
的值加一重新建模求解 直到模型  
8 － 11) ，  
CASR  
，
ordered  
在第 二 步 在  
scheduling  
处 理 的 基 础 上 运 行 基 于  
，
，
若模型无解 将  
NOUA ( Node Ordering Update Algo-  
机 制 的  
seg  
(
有解或者  
的值超出界限 行  
如果最终模型  
rithm)  
，
，
算法 计算最长一致性更新序列 按照该序列更  
，
SID，  
，
有解 则存储该流的  
如果模型最终无解 则标记该  
模型建立与求解过程本质上  
0 － 1  
．
，
two-phase  
新节点 如果网络中尚有待更新节点 则启用  
(
12 － 17) ．  
流不可拼接 行  
commit  
，
．
机制 通过规则复制的方式来完成最后的更新  
是将搜索拼接段组成新路径的过程建模为一个  
规
2. 1 CASR  
算法设计  
分段路由更新机制的性能与网络中可拼接的数据  
，
，
L
划 并求解的过程 当拼接段数目的上界 与候选拼接  
C
，
ILP  
，
( 1)  
而约  
取得最  
段集 已知后 我们建立  
模型 目标为式  
，
流比例直接相关 但甄别可拼接流并分配合适的段标  
( 2) ～ ( 5) ．  
flag  
束为式  
优化目标是让布尔变量  

相关下载

全部评论(0)

暂无评论
评论赚积分>>

上传资源 上传优质资源有赏金

热门标签

更多>>

最新上传

  • 打赏
  • 30日榜单

热门下载

资料专题

推荐下载

本站上的所有资源均为源于网上收集或者由用户自行上传，仅供学习和研究使用，无任何商业目的，版权归原作如有侵权，请 来信指出，本站将立即改正。

ICP许可证号：京ICP证070360号     21IC电子网 2000- 版权所有

京ICP备11013301号

京公网安备 11010802024343号