一种光网络中链路故障概率量化方法及sdn控制器部署方法
技术领域
1.本发明涉及软件定义光网络中控制平面生存性设计，具体是分布式二层sdn控制器的部署方法。
背景技术：2.近年来，随着用户对xr，视频直播等高流量消耗型互联网应用需求的快速增长，主干光网络正面临着前所未有的冲击：一方面网络容量急待增加；另一方面网络管理的灵活性以及服务质量也要得到保障。
3.软件定义网络(software defined networking，sdn)作为一种全新的网络架构其基本思想是将控制平面与数据平面进行分离，并开放控制面北向接口，供用户对网络进行定制，以适应特定业务的需求，实现了对网络统一、灵活的管控。软件定义光网络(software defined optical network，sdon)是对sdn技术在光网络上的一项具体应用，网络的节点被分为两类，一类专注于流量转发的数据节点；另一类专注于信令下发的控制节点。两类节点相互配合动态地完成光调制、光层路由、波长分配、波长转换等光层任务和流量转发任务，进而实现大规模光网络，海量业务中动态灵活的资源调度。
4.控制平面是sdon的核心，承载了大量重要的信令业务，如网络状态信息收集、路由决策、光通路动态建立与拆除等。一旦数据节点与控制平面失去联系，就会造成大规模的网络瘫痪。因此，sdon节点对于生存性有着严苛的要求。
5.数据节点与控制面失去联系有两种原因：
①
控制器设备故障导致失联。
②
控制链路故障导致失联。
①
所导致的失联通常是可控的，其原因是承担网络控制功能的控制器通常被放置在专用机房，保护设施完善，人员维护方便。而光纤链路则通常要穿越森林，河流等复杂的自然环境，易受鼠咬，人为等因素影响，导致故障。
6.据文献[[9]heller,brandon,rob sherwood,and nick mckeown."the controller placement problem."acm sigcomm computer communication review 42.4(2012):473-478.]研究，在传输链路故障更易发生的情况下，控制器的部署位置是否合理对保障控制平面的生存性起着关键性作用。目前，已经存在很多关于控制器部署方法的研究，例如文献[xiong yu,dong xiancun,li yuanyuan,et al.the cross-layer survivable design of control plane based on minimum point covering in software defined optical network[j].journal of electronics&information technology,2016 38(5):1211-1218.doi:10.11999/jeit150815]所提出的基于最小点覆盖的控制器部署方案，对控制平面进行分层，有效的解决了对单一控制器过度依赖和控制冲突的问题，但该方案使用了较多的控制器数量，存在控制冗余，并且无法根据用户对于网络的性能要求而改变控制部署方案。再例如文献[l f and oliveira r r.survivor:an enhanced controller placement strategy for improving sdn survivability[c].ieee global communications conference,austin,usa,2014:1909-1915.]用svvr(survivor)算法来确定控制器的部署方案，该算法使得sdn交换机节点与sdn
控制器之间满足链路分离的路径数的最大化，但是没有考虑控制链路的长度，实际应用中可能会造成控制时延过大。造成网络的性能恶化。
[0007]
又例如专利[cn113347514a]所提出的一种基于多路径生存性保护的软件定义光网络控制器部署方法，其在对于控制链路故障概率的量化上，考虑使用多个边分离路径互为冗余备份，以此来提高数据节点生存性。但其忽略了单光段故障并不会影响控制链路上其它光段正常使用这一事实，致使链路故障概率估计过高，控制器部署数量偏大。本发明基于控制器对网络结构较强的感知能力，拓展了可选的控制路径，并且在对于控制路径概率的量化方面，充分考虑到各个光段故障的独立性，量化更加精确，能为控制器部署提供数据支撑。
技术实现要素：[0008]
本发明旨在解决以上现有技术的问题。提出了一种光网络中链路故障概率量化及sdn控制器部署方法。本发明的技术方案如下：
[0009]
一种光网络中链路故障概率量化方法，其包括以下步骤：
[0010]
步骤1：利用深度优先搜索算法dfs求出源控制节点c到目的数据节点d之间满足跳数约束j的所有简单路径；
[0011]
步骤2：统计光段和满足跳数约束j的所有简单路径之间的映射关系，形成表格，表格各行代表步骤1所求出的简单路径，各列代表各个光段；
[0012]
步骤3：确定每一个能导致所有简单路径故障的故障事件，故障事件也即所有简单路径均包含的光段或者光段组合；
[0013]
步骤4：当所有光段故障相互独立时，计算步骤3各个故障事件的概率；
[0014]
步骤5：基于非互斥情况下的和事件概率计算方法，计算各个故障事件的和事件概率，和事件概率即为两点之间光链路故障概率。
[0015]
进一步的，所述步骤1：利用深度优先搜索算法dfs求出源控制节点c到目的数据节点d之间满足跳数约束j的所有简单路径，具体包括：
[0016]
首先从源控制节点出发任选一个与之相邻节点进行搜索，将此相邻节点加入已访问节点列表，路由跳数增加1，随后寻找此节点的相邻节点并循环此过程直到路由跳数已经达到限制或者搜索到目的数据节点。再此过程中若我们搜索到目的节点并且路由跳数没有超过跳数约束j，则将此时列表中的节点构成一条满足跳数约束下的简单路径，我们将此其记录并弹出列表中的最后一个节点，继续搜索未访问的其他相邻节点；若已经达到跳数限制，则不记录路径，继续搜索上一条节点的其他相邻节点。此过程在源节点的所有直接相邻节点搜索完毕后结束。
[0017]
进一步的，所述步骤2中，一条简单路径包含此光段则对应单元格标记为√，否则标记为
×
；若表格的某个单元格被√标记，则表示此行代表的路径包含此列；由该表可以确定导致两节点之间链路故障的所有故障事件；光段c1被所有的简单路径p包含，则认为光段组合c1是导致两节点故障的一个故障事件；同样，光段c2，c3同时故障也是一个故障事件。
[0018]
进一步的，所述步骤3确定每一个能导致所有简单路径故障的故障事件，转化为对于步骤2输出的路径-光段映射表的求解问题，也即找出能使表格每一行均包含√的列组合。
[0019]
进一步的，所述步骤4给出了各节点之间光段故障pi相互独立的假设，并且步骤3求解故障事件结果为各光段的组合，因此各个故障事件a,b,c......的出现概率可以直接写为形式。
[0020]
一种采用任一项方法的sdn控制器部署方法，其包括以下步骤：
[0021]
步骤a1：将网络节点分为控制，数据两个集合c,d，两集合初始元素与网络g(v,e)中的节点集v完全相同；
[0022]
步骤a2：使用光链路故障概率量化方法，计算源控制节点集合c到目的数据节点集合d中的每一对节点间光链路故障概率；
[0023]
步骤a3：依据用户指定的概率p，逐一与步骤2计算的各个节点对故障概率进行比较，保留满足要求的控制关系，删去不满足要求的控制关系；
[0024]
步骤a4：将节点之间的控制关系映射为控制关系表，行表示源控制节点，列表示目的数据节点，若两者之间存在控制关系，将对应单元格标记为√，否则标记为
×
；
[0025]
步骤a5：基于步骤a4输出的控制关系表，利用二分查找法求解能完成全图控制的最少控制器个数；
[0026]
步骤a6：找出控制器数量最少的方案中，数据节点平均故障概率最低的方案。
[0027]
进一步的，所步骤a5：基于步骤a4输出的控制关系表，利用二分查找法求解能完成全图控制的最少控制器个数，具体包括：
[0028]
将能完成全网控制的最小控制器数量作为搜索目标，初始设定最小数量为n为控制器数量；接着从控制关系表任选行进行组合，若某种组合能保障所有的列存在√，则表示这种部署方案能够完成全图控制，接着将最小数量更新为后继续搜索过程；若所有组合中不存在任何一种组合能保障所有列均存在√，则表示此时的控制器数量不能完成全图控制，接着将最小数量更新为后继续搜索过程，直到最终k个控制器能完成全网控制，k-1个控制器不能完成全网控制，即求解出完成全网控制的最小控制器数量k。
[0029]
进一步的，所述步骤a6的控制器部署方案的选择准则具体为：在步骤a5求解出最小的控制器数量后，能够穷举遍历出所有满足生存性要求的控制器部署方案，所提准则将所有节点分为控制节点ci和数据节点di；基于步骤a2节点间链路故障概率计算结果和步骤a5控制关系表，在一个数据节点di存在多个控制节点ci时，选择最小的链路故障概率作为此数据节点di的故障概率，即由此，计算出此种部署方案最终的数据节点平均故障概率最终所选择的部署方案为pe最小的方案。
[0030]
本发明的优点及有益效果如下：
[0031]
本发明方法从用户需求出发，结合实际网络拓扑结构，在满足用户需求前提下完成sdn控制器生存性的部署目标。本部署方法具有以下优势：
[0032]
其一，在此前的研究中，控制链路通常被认为是一条或几条连接控制器和交换机
节点之间的特定路径，其故障概率与路径长度呈正相关。依照此种方法对于控制链路的故障概率量化比较简单，但其忽略了控制链路是由多个光段组成的这一事实，造成量化所得的故障概率有失准确性。本发明考虑到控制器对于网络拓扑变化有较强的感知能力，能灵活的选择信令到达交换机的路由路径。在某些光段发生故障的情况下，其他正常工作的光段仍然能够为信令传输提供服务，极大的丰富了控制路径的选择，也大大降低了故障发生的概率。
[0033]
其二，随着可选控制链路数量的增加，某些控制链路由于时延过大等因素，会影响控制器的控制效率，影响网络控制性能。本发明考虑到交换机排队时延＝对时延影响最为严重，在步骤一中使用深度搜索寻找控制节点和交换机之间的控制路径时，使用路径路由跳数j作为约束，保障了控制链路的传输质量，提升了网络性能。
[0034]
其三，随着可选控制路径数量的增加，欲对求解一组非边分离径故障概率也愈加困难，本发明创新性的利用了公式pe＝[1-(1-p)w]对单光段故障概率进行量化，随后根据映射关系，构建步骤2所提的光段-路径映射关系表，借助非互斥情况下的和事件概率计算方法，对于所有能够引起路径集合中全部路径故障的和事件进行量化。该方法能够极大的提高链路故障概率的准确性，为后续基于链路故障概率的控制器部署方案提供保障。
[0035]
其四，在步骤a5确定了网络所需要的最少控制器数量之后，数量相同的控制器不同部署方案也会影响到控制面生存性。在一个数据节点di存在多个控制节点ci时，选择最小的链路故障概率作为此数据节点的故障概率，即由此，计算出此种部署方案最终的数据节点平均故障概率最终所选择的部署方案为pe最小的方案。此种部署方案，在满足网络生存性需求，控制器数量最小的情况下，进一步增加了控制冗余，提升了生存性。
附图说明
[0036]
图1是本发明提供优选实施例对真实网络的部署结果；
[0037]
图2本发明的部署流程图。
具体实施方式
[0038]
下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、详细地描述。所描述的实施例仅仅是本发明的一部分实施例。
[0039]
本发明解决上述技术问题的技术方案是：
[0040]
针对以上现有技术的不足，我们从用户对网络实际地生存性需求以及传输时延质量需求出发。通过限制信令下发路由跳数优化控制时延，再基于网络拓扑的真实连接关系，精准量化节点链路的故障概率，保障在用户要求的生存性条件p。最后还综合考虑到了网络的部署成本问题，求解出了最少的控制器部署方案。
[0041]
本发明解决上述技术问题的技术方案如下：提出一种光网络中的链路故障概率量化方法及sdn控制器部署策略。该方法需要在部署前与用户结合实际的网络情况进行协商讨论，在用户给出可接受的最大故障出现概率p，最大路由跳数j后,结合实际场景完成sdon
控制平面的搭建。该方法所应用的部署模型为分布式部署模型，全网分布着控制节点和数据节点，控制节点承担着所属数据节点的信令下发工作,网络架构更加扁平。
[0042]
其中，控制器的部署部分，需要先将网络中实际的sdn交换机节点划分为两个集合，即控制节点集和数据节点集，每个集合初始包含所有的交换机节点。然后，根据协商所得到的路由跳数限制j，使用深度优先搜索(dfs)算法求出任一控制节点到任一数据节点的所有简单路径，并由此量化出链路故障概率。量化方法为：对简单路径集合进行统计分析得到光段-路径映射表，根据表查找任一简单路径均包含的光段或者光段组合，也即链路故障事件(指此光段组合发生故障两节点间所有简单路径均不可用)。基于光段故障彼此独立的假设，计算每一个链路故障事件的发生概率，再求其和事件概率即为两节点之间的链路故障概率。在得到任意两节点之间的光链路故障概率后，将节点间链路故障概率映射为n行n列的控制关系表，n表示网络节点数量，每一行表示每个控制节点，每一列表示每一个数据节点。表格的每一个元素表示从控制节点到数据节点的链路故障概率。随后用与用户协商得到的可容忍故障概率p与表格各元素比对，确定各个节点对之间是否能存在控制关系。随后，利用二分搜索法确定最小需要的控制器数量，穷举最小部署数量的所有满足生存性要求的方案，从中选择数据节点平均故障概率最低的方案部署控制器，即完成了对sdn网络控制器的部署。
[0043]
对于节点间链路故障概率的精准量化，为生存性保障部署算法提供了基础。量化方法独立考虑每一个光段的故障对于节点间链路故障概率的影响，符合节点之间链路冗余越多，故障概率越低的常识，并且链路故障概率的量化，也是部署的结果更加具有说服力。
[0044]
部署效率方面本发明利用深度优先搜索(dfs)求解任意两节点间所有简单路径，具有较高复杂度。但是同时路由跳数的限制能对原始搜索的结果进行剪枝，保障了搜索的深度在一个较小的量级，整体时间复杂度维持在可接受范围内；并且该算法采用了离线部署的方式，有效弥补了方法中可能存在的复杂度较高的不足。该部署方法在网络建设前期一次性完成，不占用网络实际计算资源和运行时间，不降低网络部署和建成后的实时运行效率和整体传输性能。
[0045]
如图1所示为使用本发明部署的一个真实网络拓扑，多个分布式控制器控制器协同完成对整个网络的覆盖，其中每个控制器负责对所属的数据节点下发控制(在图中已经标记为同色)，多个控制器协同工作即可完成对于全网数据节点的管控。
[0046]
首先需要与用户协商最大的路由跳数j，路由跳数越大意味着控制面时延越大，在商定完毕最大控制路由跳数后，使用深度优先搜索(dfs)算法查找任意节点到其他节点的简单路径集合。
[0047]
随后对单个节点对之间的简单路径集合进行统计，得到路径和光段的映射表，如表1所示，每一行表示两节点之间存在的满足路由跳数约束的简单路径，每一列代表一个光段。若表格的某个单元格被√标记，则表示此行代表的路径包含此列。由该表可以确定导致两节点之间链路故障的所有故障事件。如表1所示，光段c1被所有的简单路径p包含，则认为光段组合c1是导致两节点故障的一个故障事件；同样，光段c2，c3同时故障也是一个故障事件
……
。
[0048][0049]
表1
[0050]
根据公式pe＝[1-(1-p)w]计算各个光段的故障概率，式中，p为光纤每百公里故障率，w为光段长度。再基于光段故障相互独立的前提，可以计算出中所提各故障事件的概率。最后，基于非互斥和事件概率求解方法，既可以求得两节点之间的故障故障概率。
[0051]
在精准求解节点间链路故障概率后，与用户协商最大可容忍的节点故障概率p，将求解结果逐一与p进行比较，故障概率小于p的标记为√，大于p的标记为x。由所有的比较结果可以形成表2所示的节点控制关系表，每一列表示一个控制节点，每一行表示一个数据节点。由此图选出k行，确保此k行中的每一列都至少有一个√标记，即能确保全网的数据节点得到控制，此时选择出来的k行即代表需要部署控制器的k个节点。
[0052] v0v1...vi...vnv0√
×
...
×
...√v1×
√...√...
×
.........√.........vi×
√...√...
×
...............√...vn√
×
...
×
...√
[0053]
表2节点控制关系表
[0054]
通过二分查找方法能确定确保生存性的最小的控制节点数量，为了进一步保障相同控制器数量下的网络生存性最优，我们寻找所有能保障生存性需求的k控制器部署方案，使用计算各方案的网络平均故障概率，其中代表计算所得的每一个数据节点的故障概率，n为全图节点数量，k为控制节点数量。选择pn最小的方案进行控制器部署。
[0055]
还需要说明的是，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、商品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、商品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个
……”
限定的要素，并不排除在包括所述要素的过程、方法、商品或者设备中还存在另外的相同要素。
[0056]
以上这些实施例应理解为仅用于说明本发明而不用于限制本发明的保护范围。在阅读了本发明的记载的内容之后，技术人员可以对本发明作各种改动或修改，这些等效变化和修饰同样落入本发明权利要求所限定的范围。
技术特征：1.一种光网络中链路故障概率量化方法，其特征在于，包括以下步骤：步骤1：利用深度优先搜索算法dfs求出源控制节点c到目的数据节点d之间满足跳数约束j的所有简单路径；步骤2：统计光段和满足跳数约束j的所有简单路径之间的映射关系，形成表格，表格各行代表步骤1所求出的简单路径，各列代表各个光段；步骤3：确定每一个能导致所有简单路径故障的故障事件，故障事件也即所有简单路径均包含的光段或者光段组合；步骤4：当所有光段故障相互独立时，计算步骤3各个故障事件的概率；步骤5：基于非互斥情况下的和事件概率计算方法，计算各个故障事件的和事件概率，和事件概率即为两节点之间光链路故障概率。2.根据权利要求1所述的一种光网络中链路故障概率量化方法，其特征在于，所述步骤1：利用深度优先搜索算法dfs求出源控制节点c到目的数据节点d之间满足跳数约束j的所有简单路径，具体包括：首先从源控制节点出发任选一个与之相邻节点进行搜索，将此相邻节点加入已访问节点列表，路由跳数增加1，随后寻找此节点的相邻节点并循环此过程直到路由跳数已经达到限制或者搜索到目的数据节点；再此过程中若搜索到目的节点并且路由跳数没有超过跳数约束j，则将此时列表中的节点构成一条满足跳数约束下的简单路径，将此其记录并弹出列表中的最后一个节点，继续搜索未访问的其他相邻节点；若已经达到跳数限制，则不记录路径，继续搜索上一条节点的其他相邻节点。此过程在源节点的所有直接相邻节点搜索完毕后结束。3.根据权利要求1所述的一种光网络中链路故障概率量化方法，其特征在于，所述步骤2中，一条简单路径包含此光段则对应单元格标记为√，否则标记为
×
；若表格的某个单元格被√标记，则表示此行代表的路径包含此列；由该表可以确定导致两节点之间链路故障的所有故障事件；光段c1被所有的简单路径p包含，则认为光段组合c1是导致两节点故障的一个故障事件；同样，光段c2，c3同时故障也是一个故障事件。4.根据权利要求3所述的一种光网络中链路故障概率量化方法，其特征在于，所述步骤3确定每一个能导致所有简单路径故障的故障事件，转化为对于步骤2输出的路径-光段映射表的求解问题，也即找出能使表格每一行均包含√的列组合。5.根据权利要求4所述的一种光网络中链路故障概率量化方法，其特征在于，所述步骤4给出了各节点之间光段故障p
i
相互独立的假设，并且步骤3求解故障事件结果为各光段的组合，因此各个故障事件a,b,c......的出现概率可以直接写为形式。6.一种采用权利要求1-5任一项方法的sdn控制器部署方法，其特征在于，包括以下步骤：步骤a1：将网络节点分为控制，数据两个集合c,d，两集合初始元素与网络g(v,e)中的节点集v完全相同；步骤a2：使用光链路故障概率量化方法，计算源控制节点集合c到目的数据节点集合d中的每一对节点间光链路故障概率；步骤a3：依据用户指定的概率p，逐一与步骤2计算的各个节点对故障概率进行比较，保
留满足要求的控制关系，删去不满足要求的控制关系；步骤a4：将节点之间的控制关系映射为控制关系表，行表示源控制节点，列表示目的数据节点，若两者之间存在控制关系，将对应单元格标记为√，否则标记为
×
；步骤a5：基于步骤a4输出的控制关系表，利用二分查找法求解能完成全图控制的最少控制器个数；步骤a6：找出控制器数量最少的方案中，数据节点平均故障概率最低的方案。7.根据权利要求6所述的sdn控制器部署方法，其特征在于，所步骤a5：基于步骤a4输出的控制关系表，利用二分查找法求解能完成全图控制的最少控制器个数，具体包括：将能完成全网控制的最小控制器数量作为搜索目标，初始设定最小数量为n为控制器数量；接着从控制关系表任选行进行组合，若某种组合能保障所有的列存在√，则表示这种部署方案能够完成全图控制，接着将最小数量更新为后继续搜索过程；若所有组合中不存在任何一种组合能保障所有列均存在√，则表示此时的控制器数量不能完成全图控制，接着将最小数量更新为后继续搜索过程，直到最终k个控制器能完成全网控制，k-1个控制器不能完成全网控制，即求解出完成全网控制的最小控制器数量k。8.根据权利要求6所述的sdn控制器部署方法，其特征在于，所述步骤a6的控制器部署方案的选择准则具体为：在步骤a5求解出最小的控制器数量后，能够穷举遍历出所有满足生存性要求的控制器部署方案，所提准则将所有节点分为控制节点c
i
和数据节点d
i
；基于步骤a2节点间链路故障概率计算结果和步骤a5控制关系表，在一个数据节点d
i
存在多个控制节点c
i
时，选择最小的链路故障概率作为此数据节点d
i
的故障概率，即由此，计算出此种部署方案最终的数据节点平均故障概率最终所选择的部署方案为p
e
最小的方案。
技术总结本发明请求保护一种光网络中链路故障概率量化方法及SDN控制器部署方法，属于网络技术领域，应用于二层SDN控制器的部署。为保障用户对于控制平面生存性需求，并在此前提下进一步降低控制冗余，优化控制时延，本发明通过与用户协商时延要求后设置最大路由跳数J，协商控制链路生存性要求和设置最大故障概率P。随后优先计算网络中任意两节点i,j之间满足跳数约束的简单路径集合，并基于光段故障相互独立的假设，由此计算出节点之间的故障概率。接着与最大可接受的故障概率进行比较，筛选出满足生存性要求的节点控制关系，并由此确定满足全网覆盖的最少控制器数量。接着，在控制器数量最少的方案中，选择控制链路平均故障概率最低的方案进行控制器部署。的方案进行控制器部署。的方案进行控制器部署。
技术研发人员：曾帅 何一鸣 张明宇 严吉平 徐江 方子健 杨越
受保护的技术使用者：重庆邮电大学
技术研发日：2022.06.08
技术公布日：2022/11/1
