The Relationship between Similar Invariant Subspaces and Invariant Subspaces
-
摘要: 给出了“类不变子空间”的定义,研究了可逆线性变换和一般线性变换的类不变子空间与不变子空间的关系:利用向量空间的理论,证明了对于可逆线性变换,类不变子空间与不变子空间是等价的;进一步证明对于非可逆的线性变换,类不变子空间是不变子空间,反之不成立.Abstract: The concept of "similar invariant subspace" is defined and the relationship between similar invariant subspace and invariant subspace under the conditions of reversible linear transformation and general linear transformation is discussed. Using the theory of vector space, it is proved that similar invariant subspace is equivalent to invariant subspace under the condition of reversible linear transformation. Furthermore, it is proved that for a linear transformation σ of vector space V, if W is a similar invariant subspace, W must be an invariant subspace.
-
软件定义网络(Software Defined Network,SDN)是一种分离控制平面与数据平面的新型网络架构,数据平面的交换机仅负责数据转发与信息收集,控制功能由控制平面的控制器负责。控制器监控和管理数据平面,以实现个性化的网络控制逻辑。
故障恢复是保证SDN网络可靠性的关键,目前有关SDN故障恢复方面的研究主要分为反应式恢复和主动式恢复[1]。反应式恢复的时延较长,因为其恢复过程中,交换机需要与控制器通信以及更新流表项。而主动式恢复在故障发生之前安装备份流表项,故障发生后立即进行数据流的重路由,从而保证故障在电信级时间(50 ms)内恢复。因此,主动式恢复是当前故障恢复研究领域的主流恢复方案。
由于软件定义网络的特性,故障恢复主要发生在控制平面[2-4]和数据平面[5-14]。数据平面的组件故障会导致数据流无法到达目的交换机,影响用户的通信质量。在SDN的数据平面,为了更合理地分配网络资源,WANG等[5]提出了一种反应式策略和主动式策略相协同的链路故障恢复机制,以保证网络连通性能够在故障发生后短时恢复,然后基于网络实时监控信息对备份路径进行动态调整,从而实现了恢复时间和带宽资源利用上的平衡;ZHANG等[6]对网络中的链路进行重要性分级,针对不同等级链路提供不同的备份策略,减少了流表项数量;WANG等[7]提出一种基于共享环的备份路径方案,使得连接核心交换机所形成的环路被所有备份路径共享,环中备份流表项复用率高,从而节省了备份资源;WANG[8]提出了对数据流进行分类并分配不同的备份策略,减少了故障恢复时延和数据包丢失率;在计算备份路径时,ISYAKU等[9]除了对数据流进行分类外,还考虑了交换机中的流表利用率,减少了备份路径的资源消耗;THORAT等[10]提出使用VLAN标签的恢复策略,受故障影响的数据流被统一贴上标签形成聚合流,随即被转发到故障链路的另一端节点,从而减少了备份流表项;肖军弼等[11]将网络进行划域,域内数据流使用MPLS标签进行匹配,同样节省了备份流表项;TRAM等[12]借助机器学习方法学习流量的动态性,估算路径的优度后,自适应更新备份路径,其带宽利用率、恢复时间分别比基准模型提升了24%、50%;MOHAN等[13]提出了2种实现主路径保护的主动式算法(FLR算法和BLR算法),故障发生后,可根据当时的网络状态选择FLR算法或者BLR算法,2种算法都在一定程度上减少了备份路径的资源消耗,但是FLR算法仍然消耗了较多备份资源,BLR算法的故障恢复时延还有待提升。
现有主动式恢复方法的备份路径设计往往难以兼顾故障恢复的备份资源消耗和恢复时延,基于单链路故障,本文提出了一种基于链路故障位置的主动式故障恢复方案(LBR),将主路径中的链路根据位置分成两部分,采用分而治之的方式,对不同故障位置的链路配置不同的备份路径,以实现快速故障恢复和对备份流表项资源的合理利用。并通过实验评估该方案性能,实验包括:(1)注重恢复时延和注重备份资源消耗的不同场景下,LBR方案与典型方案所展现的性能;(2)各方案在备份流表项消耗、恢复时延指标上的比较;(3)不同主路径长度对LBR方案性能的影响;(4)LBR方案在不同网络拓扑的适用性。
1. 问题描述
根据备份路径的起点与终点,可将现有备份路径的策略归纳为3类:
(1) 第1类为连接数据流源节点到目的节点的备份路径。这类策略主要有1+1方案[14]和回溯方案[14]。其中,1+1方案是指为主路径计算一条从源节点到目的节点且尽量不与主路径相交的备份路径,2条路径同时传输数据流,因此,主路径即使断开也能保持正常通信。但1+1方案需要占用2条路径的带宽资源,难以进行推广。回溯方案是指在故障发生后数据流沿着主路径回溯至源节点,然后沿着备份路径传输至目的节点。与1+1方案相比,回溯方案不需占用过多的带宽资源。如图 1所示,路径 < S1—S2—S3—S4—S5—S6>为数据流的主路径,当链路 < S2—S3>发生故障时,回溯方案的备份路径为 < S2—S1—S7—S8—S9—S10—S6>。因为回溯方案为主路径配置了一条公共备份路径,所以备份路径的复用率高,需要的备份资源较少。然而,此方案在恢复过程中会造成额外的延迟,如出现最坏的情况,即当链路 < S5—S6>发生故障时,数据流必须沿着主路径回溯至源节点S1,再沿着备份路径到达S6,特别是在大型网络中,回溯方案会导致较大的恢复时延。
(2) 第2类为连接故障链路两端节点的备份路径。如图 1,当链路 < S2—S3>发生故障时,备份路径为 < S2—S11—S12—S3>。数据流重路由至故障链路另一端节点后,继续沿着主路径传输到目的节点,从而复用后序主路径的备份资源。但这种策略需要为主路径的每一条链路都计算一条备份路径,消耗较多的备份资源。
(3) 第3类为连接故障上游节点到数据流目的节点的备份路径。如图 1,当链路 < S2—S3>发生故障时,备份路径为 < S2—S13—S14—S6>。数据流直接重路由至目的节点,可以保证恢复时延,但需要的备份路径数量较多,且从检测节点直接连接至目的节点,需要消耗大量的备份资源。
综上所述,一般的故障恢复策略往往难以兼顾恢复时延和备份资源消耗。本文在综合考虑故障恢复时延和备份资源2个因素的前提下,将恢复问题建模为一个优化问题,然后基于该问题提出了一种恢复方案,从而选取最合适的备份路径,以在节省备份资源的基础上减少故障恢复时延。
2. 系统建模
本文将SDN网络记为一个无向图G=(V,E),其中,V为所有交换机的集合,E为连接交换机的链路集合。本文所用其他主要符号见表 1。
表 1 主要符号及其含义Table 1. Mathematical notations and description符号 含义 M 网络所有交换机的备份资源消耗之和 Trec 网络故障恢复时间 mi 交换机i的备份资源消耗 s, d 主路径的源节点、目的节点 k 故障恢复时在主路径中的一个绕行节点 Pi, jwork 主路径中节点i到节点j的路径 L1, L2 第1类链路、第2类链路的集合 Ps, dback1 第1类链路所有备份路径的公共路径 Pk, dback2 第2类链路所有备份路径的公共路径 Pi, jback1 路径Ps, dback1中节点i到节点j的路径 lin, lout 链路l的入口节点、出口节点 trlink 单个数据包在链路r的传输时延 tenode 单个数据包在节点e的处理时间 V(P) 路径P中交换机节点的集合 E(P) 路径P中链路的集合 C 备份路径的恢复成本 N 主路径的节点数 链路故障发生之前,控制器规划备份路径并将相应备份流表项部署于备份路径的交换机中。故障恢复过程中所有交换机的备份资源消耗之和M可以用下式表示:
M=∑i∈V(Pback )mi, (1) 其中,mi为交换机i中备份流表项需要的内存空间,V(Pback)为用于恢复链路故障的备份路径Pback中交换机节点的集合。
故障恢复需要综合考虑恢复时间和备份资源消耗。本文用恢复成本C表示故障恢复过程中恢复时间和备份资源消耗的情况[5, 13]:
C=α⋅f(Trec )+β⋅f(M), (2) 其中:权重参数α、β分别为恢复时间、备份资源消耗在恢复过程中所占的比重;Trec为网络的恢复时间,即原数据流的最后一个数据包到达目的交换机和重定向流的第一个数据包到达目的交换机的时间之差;f(·)为指标的标准化函数,取值范围为[0, 1],本文采用最小最大归一化函数。可知,恢复成本C是一个综合考虑了恢复时间和备份资源消耗的指标,C较小,则意味着故障恢复方案的恢复时间和备份资源消耗会在一个较小的范围。因此,整个链路故障的恢复问题可以转化为一个优化模型:
minC (3) Subject to:
mi<mmax, (4) Trec <Tmax , (5) α+β=1, (6) 其中,条件(4)是为了避免备份路径中的交换机发生流表溢出现象,即避免备份流表项的存储空间小于交换机中的存储空间上限mmax;条件(5)是为了整个恢复过程所需的时间小于电信级的恢复时间上限Tmax(50 ms)。
3. LBR方案
若为主路径的每条链路都分配一条备份路径,则将产生较大的备份资源消耗。采用回溯方案为主路径配置一条公共备份路径,可以节省备份资源。然而,当接近目的节点的链路发生故障时,数据流需回溯至源节点并沿着备份路径重路由至目的节点,会产生较大恢复时延。若这部分链路发生故障,受到影响的数据流既不需要回溯至源节点,又能绕行至公共备份路径,则可在节省备份资源的基础上减少恢复时延。因此,本文提出对主路径中的前半部分和后半部分链路采取分而治之的方式,设计了一种基于链路故障位置的主动式故障恢复方案(LBR)。
LBR方案的具体流程(图 2)为:首先,在主路径中选取一个特殊的核心交换机作为绕行节点,记为节点k;然后,对主路径中在节点k之前的链路和在节点k之后的链路采用不同的故障恢复策略;最后,将备份路径对应的备份流表项存储于交换机中。
3.1 快速修复组表
实现主动式故障恢复,需要在故障发生前下发备份流表项,并可以通过OpenFlow协议的快速修复组表(fast failover)实现链路故障的本地化修复[15]:对于每个需要快速修复组表功能的流表项,在动作字段中指定相应的组表,然后在动作桶中部署所需的指令集,其中的组表类型设置fast failover。若动作桶中的首个指令可以执行,则跳出动作桶,后面的指令不再执行。若指令不可执行,则向下执行第一个可正常工作的指令,随后跳出动作桶。如图 3所示,图中的2个流表项成功匹配到数据包后,执行流表项动作字段中指向的组表的动作桶。若动作桶中第一个指令可以正常工作,即端口1正常,则将数据包发送到该端口。若端口1异常,则将数据包发送到端口2。利用组表,交换机可以在故障发生后自主地将中断流转移到备份路径。目前借助于组表实现主动式恢复是主流方式,因此,本文提出的LBR方案通过组表实现链路故障的主动式恢复。
3.2 链路的备份策略
本文将主路径中节点k之前的链路l归为第1类链路,满足l∈E(Ps, kwork);节点k之后的链路l归为第2类链路,满足l∈E(Pk, dwork);为2类链路分别配置不同的备份路径。记第1类链路的集合为L1,第2类链路的集合为L2,具体的备份策略见算法1。
算法1 链路备份策略
输入:网络拓扑G,主路径Ps, dwork,绕行节点k
输出:第1类链路的备份路径集合P1,第2类链路的备份路径集合P2
//1~5行计算第1类链路的备份路径集合
1. P1←{}
2. Ps, dback1←ShortestPath(G, s, d)
3. for all l∈L1 do
4. P1←{Pwork lin ,s∪Pback1 s,d}∪P1
5. end for
//6~29行计算第2类链路的备份路径集合
6. P2←{}
7. Pk, d←Pk, swork∪Ps, dback1
8. P ← Ps, dback1-{s, d}
9. C ← Inf
10. for all n∈ V(P) do
11. if ShortestPath(G, k, n) exists then
12. temp←ShortestPath(G, k, n)∪Pn, dback1
13. C′← C(temp)
14. if C′ < C then
15. Pk, d=temp
16. C←C′
17. end if
18. end if
19. end for
20. if ShortestPath(G, k, d) exists then
21. Pk, d′←ShortestPath(G, k, d)
22. if C(P′k,d)<C(Pk,d) then
23. Pback2 k,d←P′k,d
24. else
25. Pback2k,d←Pk,d
26.end if
27.for all l∈L2 do
28. P2←{Pwork lin,k∪Pback2 k,d}∪P2
29.end for
对于第1类链路l,算法1根据主路径的源节点s与目的节点d,计算一条与主路径的各条链路都不相交的最短路径,记为Ps, dback1,作为第1类链路的所有备份路径的公共路径,又称为第1类链路的共享备份路径。路径Plin, swork与路径Ps, dback1组成第1类链路l的备份路径。当故障发生时,数据流回溯到源节点后沿着Ps, dback1重路由至目的节点。如图 4所示,假设节点S3作为绕行节点k,则链路 < S1—S2>及 < S2—S3>为第1类链路,第1类链路的共享备份路径为 < S1—S7—S8—S9—S10—S6>。当链路 < S2—S3>发生故障时,数据流的备份路径为 < S2—S1—S7—S8—S9—S10—S6>。其中节点S1、S2中的流表项和组表项的情况如图 5所示。
对于第2类链路l,首先以节点k为绕行节点,计算一条连接至Ps, dback1且复用Ps, dback1后半部分的路径,记为Pk, d。连接点的选取基于最小恢复成本原则。其次,根据节点k与主路径的目的节点,计算一条与主路径和Ps, dback1的各条链路都不相交的最短路径,记为Pk, d′。比较路径Pk, d和路径Pk, d′,从中选择使得恢复成本C最小的路径,作为第2类链路所有备份路径的公共路径,即第2类链路的共享备份路径,记为Pk, dback2。可知,若选择前者则无需再为复用Ps, dback1部分的路径下发备份流表项。路径Plin, kwork与路径Pk, dback2组成第2类链路l的备份路径。如图 6所示,假设节点S3作为绕行节点k,则链路 < S3—S4>、 < S4—S5>和 < S5—S6>为第2类链路。比较路径 < S3—S9—S10—S6>和路径 < S3—S11—S6>用于共享备份路径的恢复成本C,若路径 < S3—S9—S10—S6>用于共享备份路径的恢复成本C更小,则第2类链路的共享备份路径为 < S3—S9—S10—S6>。即当链路 < S4—S5>发生故障时,数据流的备份路径为 < S4—S3—S9—S10—S6>。否则,第2类链路的共享备份路径为 < S3—S11—S6>。当链路 < S4—S5>发生故障时,数据流的备份路径为 < S4—S3—S11—S6>。其中,节点S3中的流表项组表项情况如图 7所示。由于第2类链路只需要回溯至节点k即可重路由至目的节点,大大减少了目的节点近端链路故障发生时网络的恢复时延。
3.3 绕行节点k的选取
当第1类链路l发生故障时,数据流立即回溯至源节点,然后流经路径Ps, dback1到达目的节点。同时,链路故障点之后的数据流继续沿着主路径到达目的节点。网络的恢复时间为原数据流的最后一个数据包到达目的交换机和重定向流的第一个数据包到达目的交换机的时间之差。数据流到达目的节点的时间由所经过路径上的全部链路的传输时延和在全部节点上的处理时间组成。记数据流中的一个数据包在链路r的传输时延为trlink,数据包在节点r的处理时间为trnode。当第1类链路l发生故障时,原数据流尾数据包与重定向流首数据包所经过路径的全部链路传输时延之差ΔT1link(l)为:
ΔTlink 1(l)=∑r∈E(Pwork lin ,s)tlink r+∑r∈E(Pback1 s,d)tlink r−∑r∈E(Pwork lin ,d)tlink r, (7) 其中,E(P)表示路径P上所有链路的集合,Pi, jwork表示主路径中节点i到节点j的路径,Ps, dback1表示第1类链路的所有备份路径的公共路径。所经过的全部节点处理时间之差ΔT1node(l)为:
ΔTnode 1(l)=∑e∈V(Pwork lin ,s)tnode e+∑e∈V(Pback1 s,d)tnode e−∑e∈V(Pwork lout ,d)tnode e, (8) 其中,V(P)表示路径P上所有节点的集合。则对于第1类链路,发生故障时平均恢复时延为:
T1=∑l∈L11|L1|⋅(ΔTlink 1(l)+ΔTnode 1(l)), (9) 其中,L1表示第1类链路的集合。
对于第2类链路,链路l发生故障时,原数据流尾数据包与重定向流首数据包所经过路径的全部链路传输时延之差ΔT2link(l)、所经过的全部节点处理时间之差ΔT2node(l)分别为:
ΔTlink 2(l)=∑r∈E(Pwork lin ,k)tlink r+∑r∈E(Pback2k,d)tlink r−∑r∈E(Pwork lin ,d)tlink r, (10) ΔTnode 2(l)=∑e∈V(Pwork lin ,k)tnode e+∑e∈V(Pback2 k,d)tnode e−∑e∈V(Pwork lout ,d)tnode e, (11) 其中,Pk, dback2表示第2类链路的所有备份路径的公共路径。则发生故障时平均恢复时延为:
T2=∑l∈L21|L2|⋅(ΔTlink2(l)+ΔTmode2(l)), (12) 其中,L2表示第2类链路的集合。
由3.2可知,若Pk, dback2复用了Ps, dback1的一部分路径,记Pk, dback2与Ps, dback1的第1个交点为节点n,则网络所有交换机的备份资源消耗之和为:
M=∑i∈V(Pback1 s,d)mi+∑i∈V(Pwork s,d)mi+∑i∈V(Pback2 k,n)mi, (13) 其中,mi表示交换机i的备份资源消耗。
若Pk, dback2是一条与Ps, dback1的各条链路都不相交的路径,则网络所有交换机的备份资源消耗之和为:
M=∑i∈V(Pback1 s,d)mi+∑i∈V(Pwork s,d)mi+∑i∈V(Pback2 k,d)mi。 (14) 由式(2)、(7)~(12),有
C=α⋅f(|L1|T1+|L2|T2|L1|+|L2|)+β⋅f(M)。 (15) 由以上分析可知,绕行节点k的选取直接决定了用于故障恢复所需要的恢复成本,即网络的恢复时延和备份资源消耗。为了尽可能减小恢复成本,首先评估主路径中所有节点作为绕行节点k的恢复成本,然后选取使得恢复成本最小的节点作为绕行节点k,如算法2。
算法2 节点k的选取
输入:网络拓扑结构G,主路径Ps, dwork
输出:节点k
1.P ← Ps, dwork-{s, d}
2.C(k)← Inf
3.for all i∈V(P) do
4. if C(i) < C(k) then
5. k←i
6. end if
7.end for
本文的LBR方案借鉴回溯方案的思想配置备份路径,以使备份方案具有备份路径复用率高的特性,因此所需的备份资源较少。针对主路径后半部分链路故障造成恢复时延过长的问题,在主路径中间节点采用“搭桥”方式,使得后半链路发生故障时,不必重新回溯到远端的源节点再重路由到目的节点,而是回溯到中间节点k即可重路由至目的节点,有效保障了故障发生时网络的恢复时延。
4. 实验评估
将LBR方案与DT方案[14]、ST方案[5]、FLR方案[13]进行对比实验,其中,DT方案为与LBR方案的研究思路比较相近的回溯方案,ST方案为基于最短路径的故障恢复方案,FLR方案为根据最少跳数原则将数据流从故障点前向路由到主路径上的另一个下行交换机的方案。将数据流在每条链路的传输时延和在每个节点的处理时间设置为定值,则故障恢复时间用故障发生后原数据流所经过路径和重定向流所经过路径的跳数之差来近似表示。本文依次选取网络拓扑所有的节点作为主路径的源节点来进行多组实验,每组实验中的目的节点为网络中除源节点外的所有节点。对相同主路径长度产生的实验数据取平均值,并将此平均值作为该主路径长度的最终实验数据。
4.1 实验环境
本文采用的实验环境为Intel(R)Core(TM)i5-5200U CPU@2.20 GHz, 4.00 GB内存,操作系统Windows10版本(64位),利用PyCharm软件进行实验,使用NetworkX工具建模。
4.2 实验拓扑
实验采用的拓扑结构选自于SNDLib[16]的3种骨干网拓扑:JANOS-US-CA、Cost266、NOBEL-EU(图 8)。
4.3 结果与分析
4.3.1 不同权重系数β对恢复成本的影响
本实验中交换机流表项消耗数量的权重系数β的取值范围为[0.1, 0.9]。当主路径的节点数N=11时,拓扑JANOS-US-CA中不同故障恢复方法的恢复成本(图 9)表明:(1)在β的取值范围为[0.1, 0.4]时,即较为注重网络恢复时延的情况下,FLR方案的恢复成本最小,DT方案的恢复成本最大,LBR方案的恢复成本较接近于FLR、ST方案。这是由于FLR方案和ST方案都是基于最短路径原则配置备份路径,网络能在故障后进行快速恢复,DT方案需要数据流重新回溯到源节点,恢复时间并不理想。(2)在β的取值范围为[0.5, 0.9]时,即较为注重备份资源消耗的情况下,ST方案的恢复成本逐渐变得最大,LBR方案的恢复成本最小。这是由于ST方案需要为每条链路都分配备份路径,消耗较多的备份流表项。LBR方案只需要在DT方案的基础上增加少量备份流表项,便可明显减少恢复时延。所以,LBR方案的恢复成本是最小的。
4.3.2 LBR方案的有效性分析
设交换机流表项消耗数量的权重参数β=0.7,相应地,α=0.3,主路径的节点数N为4~11,研究拓扑JANOS-US-CA中不同故障恢复方法的备份流表项消耗数和恢复时间。
由结果(表 2)可知:(1)随着主路径节点数的增加,FLR、ST方案的恢复时间较为稳定,LBR方案的恢复时间逐渐增大,这是因为FLR、ST方案的中断流总是沿着最短路径回到主路径,其恢复时间较少且稳定,而LBR方案的中断流所经过的路径长于最短路径。LBR、FLR、ST方案的备份流表项消耗数都逐渐增加,但LBR方案消耗的备份流表项数量少于FLR、ST方案,这是因为LBR方案的备份路径复用率高于FLR、ST方案。因此,对于时延较不敏感的数据流采用LBR方案进行故障恢复可以有效节省备份流表项。(2)FLR方案使用故障链路上游节点到主路径下行节点的最短路径作为链路的备份路径,ST方案使用故障链路两端的最短路径作为链路的备份路径,所以FLR方案为链路分配的备份路径长度比ST方案的短,更能节省备份流表项,恢复时间也更少。而故障链路两端的最短路径经常是故障链路上游节点到主路径下行节点的最短路径,因此FLR方案与ST方案的性能较相近。(3)与DT方案相比,LBR方案在大约增加了1条备份流表项的情况下,恢复时间减少了34%~44%,显示LBR方案具有一定的实用性。这是由于LBR方案并不需要回溯到源节点,只需要回溯到中间的绕行节点就能进行重路由。主路径与第1类链路的共享备份路径在网络拓扑中的位置往往较为接近,因此数据流从中间节点绕行至该共享备份路径所需的流表项较少。综上可知,LBR方案的优势为:与FLR、ST方案相比,LBR方案节省了备份流表项,主路径的节点数N=11时的备份流表项分别比FLR、ST方案减少23%、27%, 随着主路径长度的增加,节省效果更明显;LBR方案的恢复时间虽多于FLR方案,但其增幅较为平缓;LBR方案仅比DT方案增加了0.3~1.3条备份流表项,但恢复时间减少了34%~44%,在只付出极小存储资源的代价下大幅减少了恢复时间。
表 2 4种方案在不同主路径长度的备份流表项和恢复时间Table 2. Backup flow entries and recovery time of ST、FLR、DT and LBR at different lengths of work path主路径节点数 ST方案 FLR方案 DT方案 LBR方案 备份流表项/条 恢复时间/跳 备份流表项/条 恢复时间/跳 备份流表项/条 恢复时间/跳 备份流表项/条 恢复时间/跳 4 8.589 1.937 8.507 1.896 6.736 3.736 8.062 2.354 5 11.601 1.949 11.350 1.879 8.658 4.658 9.674 2.759 6 14.318 1.916 14.026 1.860 10.698 5.698 11.603 3.296 7 17.333 1.973 17.086 1.934 12.729 6.729 13.621 3.907 8 20.634 1.986 20.291 1.938 14.901 7.901 15.745 4.820 9 23.428 2.025 23.306 2.007 16.750 8.750 17.416 5.270 10 25.333 2.007 25.062 1.951 18.187 9.187 18.562 5.340 11 27.500 1.850 26.000 1.633 19.666 9.666 19.967 5.433 4.3.3 不同主路径长度对恢复成本的影响
设β=0.7,主路径的节点数N为4~11,研究拓扑JANOS-US-CA中不同故障恢复方法的恢复成本。由结果(图 10)可知:主路径节点数越多,不同故障恢复方法用于恢复故障的恢复成本均越大。其中,LBR方案的恢复成本基本上都是最小的,并且随着节点数增加,这种优势越来越明显。主要原因为:(1)随着主路径长度的增加,FLR、ST方案都需要为每条链路都分配备份路径,因此,备份流表项的消耗越来越大,导致恢复成本明显增大。(2)DT方案中接近目的节点的链路故障造成的恢复时延随着主路径长度的增加愈发增大,导致恢复成本也明显增大。(3)LBR方案能一定程度地缓解上述2种问题,因此恢复成本上升趋势较为缓和,主路径长度越大,数据流从中间节点重路由至目的节点的作用也越大。
4.3.4 在不同网路拓扑下各算法的恢复成本
由4.3.1至4.3.3节的实验结果可知,在拓扑JANOS-US-CA中,LBR方案较好地兼顾了故障恢复时的恢复时间和资源消耗。本节在拓扑Cost266、NOBEL-EU中进行实验,实验结果表明LBR方案同样具备快速恢复和节约备份资源的性能。具体为:(1)当主路径的节点数N=8、交换机流表项消耗数量的权重系数β的取值范围为[0.1, 0.9]时,拓扑Cost266中不同故障恢复方法的恢复成本(图 11)表明:在β的取值范围为[0.1, 0.3]时,FLR方案的恢复成本最小,LBR方案与FLR、ST方案的恢复成本相差很少;当β>0.3时,LBR方案的恢复成本在β=0.9时略低于DT方案,在β的取值范围为[0.4, 0.8]时是最小的。(2)当主路径的节点数N=8、交换机流表项消耗数量的权重参数β的取值范围为[0.1, 0.9]时,拓扑NOBEL-EU中不同故障恢复方法的恢复成本(图 12)表明:在β的取值范围为[0.1, 0.6]时,LBR方案的恢复成本接近FLR、ST方案;β的取值范围为[0.7, 0.9]时,LBR方案的恢复成本最小。(3)当β=0.6、主路径的节点数N的取值范围为[4, 8]时,拓扑Cost266中不同故障恢复方法的恢复成本如图 13所示;当β=0.8、主路径的节点数N的取值范围为[4, 8]时,拓扑NOBEL-EU中不同故障恢复方法的恢复成本如图 14所示。可以看出,随着主路径节点数的增加,LBR方案的恢复成本都是最小的,并且随着节点数增加,这种优势越来越明显。综上可知,LBR方案在3种拓扑下的性能表现相似,显示该算法具有一定的适用性。
5. 结束语
本文讨论了SDN数据平面的故障恢复问题,针对现有主动式恢复方法的备份路径设计难以兼顾故障恢复的备份资源消耗和恢复时延的不足,提出了一种基于链路位置的SDN数据平面故障恢复方案(LBR)。该方案采用分而治之的思想,根据主路径链路的位置进行分类,不同类型的链路采用不同的恢复策略,以实现恢复时间和备份资源消耗的有效平衡。实验结果表明:LBR方案有效利用了备份资源,与回溯方案相比,在增加了0.3条流表项的条件下,LBR方案的恢复时延减小了34%~44%;在保证了恢复时延的前提下,与FLR、ST方案相比,LBR方案分别减少了23%、27%的备份流表项。
-
[1] 周晓阳, 石岩月, 卢玉峰.多圆盘的加权Bergman空间上的不变子空间和约化子空间[J].中国科学:数学, 2011, 41(5):427-438. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=zgkx-ca201105004 ZHOU X Y, SHI Y Y, LU Y F. Invariant subspaces and reducing subspaces of weighted Bergman space over polydisc[J]. Scientia Sinica:Mathematica, 2011, 41(5):427-438. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=zgkx-ca201105004
[2] JIE S X, GUANG F C. Wandering subspaces and quasi-wandering subspaces in the Hardy-Sobolev spaces[J]. Acta Mathematica Sinica:English Series, 2017, 33(12):1684-1692. doi: 10.1007/s10114-017-7041-2
[3] XU X M, FANG X C, GAO F G. Principal invariant subspaces theorems[J]. Linear & Multilinear Algebra:An International Journal Publishing Articles, Reviews and Pro-blems, 2014, 62(10):1428-1436. http://d.old.wanfangdata.com.cn/NSTLQK/NSTL_QKJJ0233696766/
[4] 朱春蓉, 窦彩玲.一般非齐次非线性扩散方程的等价变换和高维不变子空间[J].数学年刊:A辑, 2015, 36(3):291-302. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=sxnk201503006 ZHU C R, DOU C L. Equivalent transformations and higher-dimensional invariant subspaces of generalized inhomogeneous nonlinear diffusion equations[J]. Chinese Annals of Mathematics:Series A, 2015, 36(3):291-302. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=sxnk201503006
[5] 左苏丽, 勾明, 李吉娜, 等. Black-Scholes方程的条件Lie-Backlund对称和不变子空间[J].工程数学学报, 2015, 32(6):883-892. doi: 10.3969/j.issn.1005-3085.2015.06.009 ZUO S L, GOU M, LI J N, et al. Conditional Lie-Backlund symmetry and invariant subspace for Black-Scholes equation[J]. Chinese Journal of Engineering Mathema-tics, 2015, 32(6):883-892. doi: 10.3969/j.issn.1005-3085.2015.06.009
[6] MA W X, LIU Y P. Invariant subspaces and exact solutions of a class of dispersive evolution equations[J]. Communications in Nonlinear Science and Numerical Simu-lation, 2012, 17(10):3795-3801. doi: 10.1016/j.cnsns.2012.02.024
[7] BYERS R, KRESSNER D. Structured condition numbers for invariant subspaces[J]. SIAM Journal on Matrix Analy-sis and Applications, 2006, 28(2):326-347. doi: 10.1137/050637601
[8] BEATTLE C, EMBREE M, ROSSI J. Convergence of restarted Krylov subspaces to invariant subspaces[J]. SIAM Journal on Matrix Analysis and Applications, 2004, 25(4):1074-1109. doi: 10.1137/S0895479801398608
[9] YOUSEFI B, KHOSHDEL S, JAHANSHAHI Y. Multiplication operators on invariant subspaces of function spaces[J]. Acta Mathematica Scientia:Series B, 2013, 33(5):1463-1470. doi: 10.1016/S0252-9602(13)60096-X
[10] POPOV A I, RADJAVI H, MARCOUX L W. On almost-invariant subspaces and approximate commutation[J]. Journal of Functional Analysis, 2013, 264(4):1088-1111. doi: 10.1016/j.jfa.2012.11.010
[11] BROWN S W, CHEVREAN B, PEARCY C. On the structure of contraction operators Ⅱ[J]. Journal of Functional Analysis, 1988(76):1-29. https://www.sciencedirect.com/science/article/pii/002212368890047X
[12] BROWN S W. Hyponormal operators with thick spectra have invariant subspaces[J]. Annals of Mathematics, 1987(125):93-103. doi: 10.2307-1971289/
[13] JOHNSON W B, LINDENSTRAUSS J. Handbook of the geometry of Banach spaces[M]. North Holland:Elsevier, 2001:85-122.
[14] ANSARI S, ENFLO P. Extremal vectors and invariant subspaces[J]. Transactions of the American Mathematical, 1998, 350(2):539-558. doi: 10.1090/S0002-9947-98-01865-0
[15] IZUCHI K J, IZUCHI K H. Rank-one cross commutators on backward shift invariant subspaces on the bidisk[J]. Acta Mathematica Sinica, 2009, 25(5):693-714. doi: 10.1007/s10114-009-7215-7
[16] GOHBERG I, LANCASTER P, RODMAN L. Invariant subspaces of matrices with applications[M]. Philadelphia:Society for Industrial and Applied Mathematics, 2006:671-672.
[17] CHEN J J, WANG X F, XIA J, et al. Riccati equations and Toeplitz-Berezin type symbols on Dirichlet space of unit ball[J]. Frontiers of Mathematics in China, 2017, 12(4):769-785. doi: 10.1007/s11464-017-0640-5
[18] 张禾瑞, 郝鈵新.高等代数[M]. 5版.北京: 高等教育出版社, 2007: 163-233.
计量
- 文章访问数: 2052
- HTML全文浏览量: 653
- PDF下载量: 46