CN103248571A

CN103248571A - 一种最优第二路由的计算方法

Info

Publication number: CN103248571A
Application number: CN2013101825083A
Authority: CN
Inventors: 李想
Original assignee: Hubei Post & Telecom Design Co Ltd
Current assignee: Hubei Post & Telecom Design Co Ltd
Priority date: 2013-05-16
Filing date: 2013-05-16
Publication date: 2013-08-14

Abstract

本发明公开了一种最优第二路由的计算方法，包括以下步骤，A、利用迪杰斯特拉算法，计算基于路径表的最优第一路由；B、将最优第一路由所经过的路径从路径表中删除，得到路径表1；C、通过迪杰斯特拉算法计算基于路径表1的最优第二路由，若无法生成基于路径表1的最优路由，将对路径表1中的路径进行回补，直到生成最优第二路由为止。本发明结合双路由需求，实现了尽力而为的最优第二路由选择算法；将此前手动统计资源的方式改变为程序自动化计算，改变了此前手工查找导致的人力消耗，目前已应用于通信运营商的网络规划中，极大减弱了规划中不同专业之间衔接的工作强度，提升了规划精度。

Description

一种最优第二路由的计算方法

技术领域

本发明适用于通信领域，尤其是一种最优第二路由的计算方法，适用于网络规划和衔接。

背景技术

通信领域中，例如城域网的路由器设备，通常会同时开通多条电路来规避少量电路故障对通信的影响。当其中少数几条电路发生故障时，路由器将通过路由收敛方式更新路由表，通过剩余电路来转发所有数据流量。

该保护方式实现了多条电路间的备份，在故障相对独立的情况下具有非常强的保护能力。但在实际工程操作过程中，常会遇到多条电路共用一组光缆的情况，当遇到野蛮施工挖断光缆时，管道内的所有光缆可能全部中断，而原先互为备份的电路将全部中断而丧失保护功能。因此，规划和设计过程中，设计人员需手工统计电路的第一路由和第二路由，进而提出网络对光缆资源的消耗，工作量非常巨大，且经常出现统计错误。本算法的提出，可以实现自动计算最合适的第二路由，释放了人工消耗，对通信网络的规划衔接起到了简化和促进作用。

发明内容

本发明的目的是在于针对现有技术存在的上述问题，提供一种最优第二路由的计算方法，降低工作中的人工消耗。

一种最优第二路由的计算方法，包括以下步骤：、

步骤1、设定路径表、电路需求表；路径表包括起点、终点、路径代价，电路需求表包括起点、终点、路由分离属性；

步骤2：利用迪杰斯特拉算法计算基于路径表的最优第一路由；

步骤3：将步骤2中计算出的最优第一路由使用的所有路径从路径表中删除形成路径表1；

步骤4：利用迪杰斯特拉算法计算基于路径表1的最优路由，如计算成功表示有基于路径表1的最优路由，则该路由即为最优第二路由；如计算失败，则进入步骤5；

步骤5：设定步骤2计算出的最优第一路由，所用到的全部路径为X₁～X_n，将所使用的n段路径按如下方式排列，

从X₁到X_n的n条链路中挑出k条链路，有C_n ^k种选择方式；k为1～n的整数；

以上面所有的排列组合方式选出的全部电路代价之和形成一个数组，该数组共由

个元素组成；

步骤6：将步骤5中生成的个元素的数组按从小到大的顺序排列，先选第一个元素，即代价最小对应的路径加入路径表1，重新计算两点间的最优路由，若能生成最优路由，就找到了与最优路由共用路径代价最小的最优第二路由；若无法生成，则将数组中第二个元素，即代价次小对应的路径加入路径表1再次计算，以此类推，直到生成最优路由为止，则该路由为最优第二路由。

假设任一路径中断的独立概率为x%，当互为主备的两条电路不共路径时，两条电路同时中断（即业务发生全阻）的概率为(1-x%)*(1-x%)=(1-x%)²。极端情况下两条电路故障完全相关，两条电路同时中断的概率为(1-x%)。根据常识可知0<x%<1，因此0<1-x%<1，那么（1-x%）>(1-x%)²。即证明得到两条电路共光缆的故障概率比不共光缆的概率更大。

在工程建设过程中，两条电路不共光缆可以达到更高的安全性能，理论上所有设备的主用和备用电路应该分散在不同的路径中，但现实情况是：由于光缆资源受限于建设成本、地形地貌以及其他各类因素的制约，仍然有少数局点只有唯一一个局向的出局光缆（或管道）。这些局点多条上联电路不得不使用同一路径（光缆、管道）资源。

假设某段路径距离为L，单位距离的路径故障率为y，并且故障相对独立，通过常理可推得这段路径的总故障率x%与L、y正相关，即路径距离（L）越长、单位距离的路径故障率（y）越大，则整段路径的故障率（x%）越大。

基于上述推导结论，在前文所述“主、备电路不得不复用相同路径”的妥协前提下，如能使复用路径的距离（代价）越短，则电路的安全性越高。这种思路即最优第二路由的原型，本文所述最优第二路由也可称作共路径代价最小的第二路由。

算法基本思路如下：

1、利用迪杰斯特拉算法，计算基于路径表的最优第一路由；

2、将最优第一路由所经过的路径从路径表中删除，得到路径表1，计算基于路径表1的最优路由——最优第二路由；

3、若无法生成基于路径表1的最优路由，将对路径表1中的路径进行回补，直到生成最优第二路由为止。

本发明与现有技术相比，具有以下优点：

1、结合双路由需求，实现了“尽力而为”的最优第二路由选择算法；

2、将此前手动统计资源的方式改变为程序自动化计算，改变了此前手工查找导致的人力消耗，目前已应用于通信运营商的网络规划中，极大减弱了规划中不同专业之间衔接的工作强度，提升了规划精度。

附图说明

图1为迪杰斯特拉算法的范例网络拓扑图；

图2为以A为根节点的生成树示意图；

图3为最优第二路由的范例网络拓扑图；

图4为完全不共路径的最优第二路由计算结果示意；

图5为共路径代价最小的最优第二路由计算结果示意；

图6为本方法的流程示意图。

具体实施方式

下面结合附图和实施例对本发明的技术方案作进一步详细描述：

实施例1：

步骤一：初始资料包括：路径表（起点、终点、路径代价）、电路需求表（起点、终点、路由分离属性——需与哪一条电路不共路由）；

路径表的基本格式至少包含起点、终点和路径代价，而路径代价是计算最短路由的关键参数，距离、造价、安全性等都可以作为路径代价来计算。

一条典型的路径信息见表1所示：

表1路径表的范例

序号	起点	终点	路径代价
				1	局点A	局点B	9.2
2	局点B	局点C	11.8
				3	局点C	局点D	13.7

而电路需求表，则表示仅提供起点和终点，需要在路径表中查找路径代价最小的路由的需求表。

表2电路需求表的范例

序号	起点	终点	不同路由	最优路由的代价
					1	局点A	局点D
2	局点A	局点D	1

电路需求表的起点和终点必须存在于路径表中，不同路由表示序号1和序号2的两条电路应尽可能通过不同的路径承载。

路径表是网状网络的路径信息，在本方法中仅作为标量，与方向性无关。迪杰斯特拉算法视路径表中的路径为矢量，即A->B与B->A是两条不同的路径。在实际工程中，若只以光缆为考量，可以约定在路径表中同一段光缆只录入一次——A->B，cost=x（例如以汉子的拼音排序，路径的起点拼音排序较终点排序靠前），在计算时自动补充一条B->A，cost=x的反向等价路径。

步骤二：利用迪杰斯特拉算法计算基于路径表的最优第一路由——最优路由即经过的路径代价之和最小的路由。

步骤三：若电路需求表中有第二路由需求，则将步骤二中计算出的最优第一路由使用的所有路径从路径表中删除形成路径表1；

步骤四：通过迪杰斯特拉算法计算基于路径表1的最优路由，如计算成功表示有基于路径表1的最短路由，则该路由即为最优第二路由；如计算失败，则表示除最优第一路由外，不存在与最优第一路由完全不共路径的第二路由，此时需考虑与最优第一路由共路径代价最小的路由，进入步骤五。

步骤五：将步骤二中计算出的最优第一路由上，所使用的路径——例如经过了n段路径（用X1、X2、X3……Xn表示），按如下方式排列：

从X₁到X_n的n条链路中挑出1条链路：有C_n ¹种选择方式；

从X₁到X_n的n条链路中挑出2条链路：有C_n ²种选择方式；

从X₁到X_n的n条链路中挑出3条链路：有C_n ³种选择方式；

……

从X₁到X_n的n条链路中挑出n条链路：有C_n ⁿ种选择方式；

以上面所有的排列组合方式选出的全部电路代价之和形成一个数组，该数组共由C_n ¹+C_n ²+C_n ³+……+C_n ⁿ个元素组成。

以n=4为例，即最优路由上使用了4段路径。假设每段路径的代价分别为：

Cost（X1）=a；

Cost（X2）=b；

Cost（X3）=c；

Cost（X4）=d；

从X₁到X₄的4条链路中挑出1条链路：有C₄ ¹=4种选择方式，对应的电路代价分别为{a，b，c，d}；

从X₁到X₄的4条链路中挑出2条链路：有C₄ ²=6种选择方式，对应的电路代价分别为{a+b，a+c，a+d，b+c，b+d，c+d}；

从X₁到X₄的4条链路中挑出3条链路：有C₄ ³=4种选择方式，对应的电路代价分别为{a+b+c，a+b+d，a+c+d，b+c+d}；

从X₁到X₄的4条链路中挑出4条链路：有C₄ ⁴=1种选择方式，对应的电路代价分别为{a+b+c+d}；

则由上述所有的排列组合方式选出的全部电路代价之和形成的数组应为{a，b，c，d，a+b，a+c，a+d，b+c，b+d，c+d，a+b+c，a+b+d，a+c+d，b+c+d，a+b+c+d}，共计15个元素。

步骤六：将步骤五中生成的（C_n ¹+C_n ²+C_n ³+……+C_n ⁿ）个元素的数组（即上述a、b、c、d赋值后，数组{a，b，c，d，a+b，a+c，a+d，b+c，b+d，c+d，a+b+c，a+b+d，a+c+d，b+c+d，a+b+c+d}各元素的实际值）按从小到大的顺序排列，先选第一个元素（代价最小）对应的路径加入路径表1，重新计算两点间的最优路由，若能生成最优路由，就找到了与最优路由共用路径代价最小的最优第二路由；若无法生成，则将数组中第二个元素（代价次小）对应的路径加入路径表1再次计算，以此类推，直到生成最优第二路由为止。

步骤六保证了加入路径表1的路径信息一定是能够生成第二路由的最短路径，即第一路由和第二路由共路径的代价最小。在极端情况下，该步骤将在加入了最优第一路由中所有n条路径后才能生成最优第二路由，这代表最优第一路由和最优第二路由完全相同，即不存在第二路由。

本算法的最大特点在于：普通的路由算法，仅在某一段链路发生故障时，计算摒弃了故障路径之外的最优路由，原路由和之后生成的路由只能确保不共用那段摒弃的故障路径，而其他无故障路径有可能仍然存在复用。而本算法，在计算第二最优路由时，不但充分考虑到“完全不共路径”的安全优势，还能对“不得不共路径”的极端情况进行妥协，将共路径的代价降到最低，从而尽最大可能提升网络的安全性。

迪杰斯特拉算法

以OSPF路由协议中的查找过程详述计算最短路径的迪杰斯特拉算法原理。建立一个如错误！未找到引用源。所示的网络模型，该网络由A、B、C、D、E、F六个网元组成。其中，A-B、A-C、B-D、C-D、B-F、C-E、D-E、D-F、E-F之间有互联链路，每条链路的代价标注在电路上方。互联链路属于矢量，例如图中A->C的电路代价为5，C->A的电路代价为2，两者并不相等。

OSPF路由协议维护并操作三张表格，分别是Link State（路径表，又作链路状态表）、Candidate（备选表）和Tree（生成树）。Link State存储链路信息，Candidate存储中间状态，Tree为最短路径生成树结果。

图1网络模型的Link State见表3所示。设置A为根节点，将(A,A,0)这条链路也加入Link State。

表3Link State

序号	起始节点	目的节点	链路代价	描述方式
					1	A	A	0	(A,A,0)
2	A	B	4	(A,B,4)
					3	A	C	5	(A,C,5)
4	B	A	3	(B,A,3)
					5	B	D	6	(B,D,6)
6	B	F	3	(B,F,3)
					7	C	A	2	(C,A,2)
8	C	D	1	(C,D,1)
					9	C	E	4	(C,E,4)
10	D	B	2	(D,B,2)
					11	D	C	2	(D,C,2)
12	D	E	8	(D,E,8)
					13	D	F	3	(D,F,3)
14	E	C	5	(E,C,5)

序号	起始节点	目的节点	链路代价	描述方式
					15	E	D	1	(E,D,1)
16	E	F	3	(E,F,3)
					17	F	B	2	(F,B,2)
18	F	D	5	(F,D,5)
					19	F	E	7	(F,E,7)

将(A,A,0)移动到Candadate表，计算从邻居节点A到根节点A的总开销，计算结果为0。删除Link State表中的(A,A,0)路径。

表4 Step1

将Candidate表中最小路径移动到表Tree，删除Candidate表中的(A,A,0)路径。此时，在Tree表中就描出了目标节点A到根节点A的路径代价最小值0。

将从刚加入Tree表的节点A作为起始节点的电路条目，从Link State表中移动到Candidate表。检查Tree表中已存在的目的节点是否在Candidate表中的目的节点重合。这里Tree表中仅有节点A，Candidate表目前两个目的节点为B和C，不重合因此程序继续；如果重合，需将Candidate表中目的节点在Tree表中的条目删除。

计算目的节点到根节点A的代价，填入Candidate中的“到根节点代价”关键字中。计算得B到根节点A的代价为4，C到根节点A的代价为5。

表5 Step2

将Candidate表中到根节点代价最小的条目(A,B,4)移动到Tree中。判断Candidate是否为空，不空则继续计算。

将从刚加入Tree表的节点B作为起始节点的电路条目，从LinkState表中移动到Candidate表。需将Candidate表中目的节点在Tree表中的条目删除。

检查Tree表中已存在的目的节点是否在Candidate表中的目的节点重合。这里Tree表中仅有节点A和B，Candidate表目前目的节点有C、A、D、F，其中(B,A,3)的目的节点A与Tree表中已知的节点A重复，删除(B,A,3)条目，

计算Candidate表中目的节点D、F到根节点A的代价，填入Candidate中的“到根节点代价”关键字中。计算得D到根节点A的代价为10，F到根节点A的代价为7。

表6 Step3

将Candidate表中到根节点代价最小的条目(A,C,5)移动到Tree中。这样我们就在Tree表中得到了A、B、C三个节点的最短路径。

重复上述循环，直到所有Link State和Candidate中的条目都被删除或移动到Tree表。最终结果见表7所示：

表7 Final Step

Tree表中描述的各链路是以A为根节点出发，到各节点代价最小的关键路径及其代价值。在原网络图上绘制结果见图2所示。

在实际中常以光缆距离作为路径代价，此时路径代价为标量。假设A节点有路由器1，E、F节点分别有路由器2和3。路由器2和路由器3都需通过2条电路连接到路由器1。网络结构见图3所示：

根据网络拓扑和节点电路需求可以生成表8和表9：

表8 路径表

序号	起点	终点	电路代价
				1	A	B	4.0
2	A	C	5.0
				3	B	D	6.0
4	B	F	6.0
				5	C	D	4.0
6	C	E	5.0
				7	D	E	8.0

表9 电路需求表

序号	起点	终点	不同路由
				1	A	E
2	A	E	1
				3	A	F
4	A	F	3

其中路径表中的电路代价赋值为该条光缆的距离。考虑双路由保护原则，电路需求表中的2、4行需分别与1、3行尽可能不同路由。

A->E的双路由计算——完全不共路径的最优第一和最优第二路由

电路需求表中序号1代表的A-E的最短路由，通过迪杰斯特拉算法计算可知A->E的最短路由为A->C->E，代价为10。

将A->C，C->E两条路径从原路径表中删除，形成路径表1。将电路需求表中序号2的A->E电路需求在路径表1中，利用迪杰斯特拉算法查找最短路由，得到A->E的最优第二路由为A->B->D->E，代价为18。

A->E的最优路由和最优第二路由路径完全不同，这样当网络图中任何一段路径故障时，都可以保证A节点的路由器1和E节点的路由器2之间，至少有一条电路保持正常。

A->F的双路由计算——最优第一路由和尽可能不共路径的第二路由

电路需求表中序号3代表的A-F的最短路由，通过迪杰斯特拉算法计算可知A->F的最短路由为A->B->F，代价为10。

将A->B，B->E两条路径从原路径表中删除，形成路径表1。将电路需求表中序号4的A->F电路需求在路径表1中，利用迪杰斯特拉算法查找最短路由，此时无法在路径表1中找到A->F的路由。从网络图中可知，A到F的路由必须通过B->F路径方可到达。因此，需对路径表1进行路径回补。

将最短路由A->B->F中所经过的所有路径（即A->B和B->F）的代价进行排列组合，并从小到大排序，形成一个数组{4,6,10}。

将数组中第一个（最小）元素4代表的路径（即A->B）插入到路径表1，形成路径表2。在路径表2中查找A->F的最短路由，由于此时路径表2代表的网络图仍然没有B->F路径，因此A->F仍然不可达。

将数组中第二个（次小）元素6代表的路径（即B->F）插入到路径表1，形成路径表3。在路径表3中查找A->F的最短路由，可以查找到A->C->D->B->F，代价为21。

可以看到A->F的两条路由，不得不仅对B->F路径进行了重复使用，而对A->B的两条路由进行分离保护，这样无论图中B->F之外的任何一条路径中断，都不会使得节点A的路由器1和节点F的路由器2之间的通信发生中断。

这种算法，使得需要分离的两条路由共路径的代价最小，若路径代价与故障率正相关，则同时发生故障的几率最低。

按双路由算法生成的路由示意见图4所示。

本文中所描述的具体实施例仅仅是对本发明精神作举例说明。本发明所属技术领域的技术人员可以对所描述的具体实施例做各种各样的修改或补充或采用类似的方式替代，但并不会偏离本发明的精神或者超越所附权利要求书所定义的范围。

Claims

1.一种最优第二路由的计算方法，其特征在于，包括以下步骤：、

个元素组成；

步骤6：将步骤5中生成的

个元素的数组按从小到大的顺序排列，先选第一个元素，即代价最小对应的路径加入路径表1，重新计算两点间的最优路由，若能生成最优路由，就找到了与最优路由共用路径代价最小的最优第二路由；若无法生成，则将数组中第二个元素，即代价次小对应的路径加入路径表1再次计算，以此类推，直到生成最优路由为止，则该路由为最优第二路由。