一种在分布式网络中支持集中控制的高效算法

摘要

本发明涉及一种在分布式网络中支持集中控制的高效算法，中心控制器计算数据转发路径的时候，不仅考虑链路方面的开销，同时也将虚假结点相关的开销考虑进去。本发明从质上减少了将中心控制运用在分布式网络中的总开销。

说明书

技术领域

本发明涉及分布式网络领域，特别是一种在分布式网络中支持集中控制的高效算法。

背景技术

在传统网络中，每个转发设备(如交换机、路由器)通过分布式路由协议(如RIP、OSPF、ISIS)相互之间交换网络状态信息并计算数据的转发路径，然后根据得出的转发路径并配置自己的转发表，当网络请求到来时按照转发表进行转发；在软件定义网络(SDN)中，由SDN控制器根据整个网络的状态计算数据的转发路径，然后控制器一一为每个转发设备配置转发表，当网络请求到来时，转发设备按照转发表进行转发。我们可以结合传统网络和SDN的特点，由中心控制器根据整个网络的状态计算数据的转发路径，然后控制器根据计算出的转发路径，计算出一个增广的网络(在原本的网络中添加一些虚假结点和虚假链路)，然后控制器根据计算出的增广拓扑在网络中添加虚假结点和虚假链路，然后转发设备通过分布式路由协议计算出数据在增广后的网络转发路径，因为有虚假结点和虚假链路的存在，所以转发设备通过分布式路由协议计算出的转发路径会达到和之前中心控制器计算出的转发路径相同的效果，之后各个转发设备按照自己计算出的转发路径配置自己的转发表，当网络请求到来时，转发设备按照转发表进行转发。

发明内容

有鉴于此，本发明的目的是提出一种在分布式网络中支持集中控制的高效算法，能从质上减少虚假结点与链路这两方面的总开销。

本发明采用以下方案实现：一种在分布式网络中支持集中控制的高效算法，中心控制器计算数据转发路径的时候，不仅考虑链路方面的开销，同时也将虚假结点相关的开销考虑进去，具体包括以下步骤：

步骤S1：当一个中心控制的分布式网络接收到一个网络请求时，依次以网络中每一个结点作为源点，用线性规划求最小费用流的方法求出每个源点到汇点的链路开销最小的路径并记录下来；其中这一步不考虑链路上的带宽限制；

步骤S2：将网络中每段链路上通过的数据流量设为未知数，对于每个出度大于或等于2的结点，根据从该点流出的流是否流向从该点该点到汇点的链路开销最小的路径上的下一跳，用未知数表示出在该点处添加的虚假结点个数；

步骤S3：用线性规划求最小费用流的方法结合步骤S2中用未知数表示出的虚假结点个数，求出一数据传输路径，使得链路相关的开销和虚假结点相关开销的总和达到最小。

进一步地，步骤S1中，用一个无向图G＝(V,E)来表示网络，其中V为网络中的结点的集合，E为网络中的链路的集合，即边的集合；用C^S表示单位流量从每条边通过所需的开销的集合，用B^S表示每条边上剩余带宽的集合；用W1表示V中的结点数，用W2表示E中的边数，用W3和W4分别表示C^S和B^S中元素的个数；则V＝{v1,v2,...,vW1}，E＝{e1,e2,...,eW2}；如果l为G中的一条边，C(l)是单位流量从l通过所需的开销，B(l)是l上剩余的带宽，并且C(l)∈C^S，B(l)∈B^S；对于每一个e∈E,e＝＜vi,vj＞,vi,vj∈V,1≤i,j≤W1；网络请求包括源点、汇点、需求的带宽，用R＝(S,D,B^R)表示，其中，S表示源点，D表示汇点，B^R表示需求的宽带；目标为最小化虚假结点方面和链路方面的总开销用TC表示：

$>TC=\underset{l\in E}{\Sigma }\left(C\right(l)*f(l\left)\right)+\alpha F;$>

其中，f(l)表示边l上的流量，F表示网络中需要添加的虚假结点个数总和，α为一个可变参数，用来根据具体情况调整虚假结点方面和链路方面开销的所占的权重。

进一步地，步骤S1中所述用线性规划求最小费用流的方法求出每个源点到汇点的链路开销最小的路径并记录下来中，用线性规划求最小费用流时约束条件为：

(1)对于任一结点v∈V，且V不为源点或汇点，有：

$>\underset{vi\in V,vi\ne v,<vi,v>\in E}{\Sigma }f(<vi,v>)=\underset{vi\in V,vi\ne v,<v,vi>\in E}{\Sigma }f(<v,vi>);$>

(2)

(3)对所有边＜vi,s＞，如果vi∈V，且vi≠s，且＜vi,s＞∈E，则f(＜vi,s＞)＝0；

(4)

(5)对所有边＜t,vi＞，如果vi∈V，且vi≠t，且＜t,vi＞∈E，则f(＜t,vi＞)＝0；

线性规划的目标为：使最小。

进一步地，所述步骤S2中用未知数表示出在该点处添加的虚假结点个数具体包括以下步骤：

步骤S21：设从A向A到汇点的最短路径上下一跳的流量为x，判断x是否等于从A点流出的总流量，若是，则在结点A处添加0个虚假结点；否则，进入步骤S22；

步骤S22：判断x是否等于0，若是，则进入步骤S23；否则进入步骤S24；

步骤S23：判断网络中是否存在一条边以A为弧尾，且该边上的流量等于从A流出的总流量；若是，则在结点A处添加1个虚假结点；否则在结点A处添加20个虚假结点；

步骤S24：判断x是否等于从A点流出的总流量的一半，若否，则在结点A处添加20个虚假结点；若是，则进入步骤S25；

步骤S25：判断网络中是否存在一条边以A为弧尾，且这条边不在A到汇点的最短路径上，且该边上的流量等于x，若是，则在结点A处添加1个虚假结点；否则，在结点A处添加20个虚假加点。

进一步地，所述步骤S3的线性规划的约束条件为：

(1)对于任一结点v∈V，且V不为源点或者汇点，有：

$>\underset{vi\in V,vi\ne v,<vi,v>\in E}{\Sigma }f(<vi,v>)=\underset{vi\in V,vi\ne v,<v,vi>\in E}{\Sigma }f(<v,vi>);$>

(2)

(3)对所有边＜vi,s＞，如果vi∈V，且vi≠s，且vi≠s，且＜vi,s＞∈E，则f(＜vi,s＞)＝0；

(4)

(5)对所有边＜t,vi＞，如果vi∈V，且vi≠t，且＜t,vi＞∈E，则f(＜t,vi＞)＝0；

(6)对每一条边l∈E，则f(l)≤B(l)；

线性规划的目标为：使得最小。

与现有技术相比，本发明有以下有益效果：本发明中心控制器计算数据转发路径的时候，不仅考虑链路方面的开销，同时也将虚假结点相关的开销考虑进去。本发明从质上减少了将中心控制运用在分布式网络中的总开销。

附图说明

图1为本发明的原理流程示意图。

图2为本发明实施例的分布式网络中支持集中控制的高效方法示意图。

图3为本发明实施例单个结点处所添加的虚假结点个数的算法的流程图。

具体实施方式

下面结合附图及实施例对本发明做进一步说明。

如图1所示，本实施例提供了一种在分布式网络中支持集中控制的高效算法，中心控制器计算数据转发路径的时候，不仅考虑链路方面的开销，同时也将虚假结点相关的开销考虑进去，具体包括以下步骤：

步骤S1：当一个中心控制的分布式网络接收到一个网络请求时，依次以网络中每一个结点作为源点，用线性规划求最小费用流的方法求出每个源点到汇点的链路开销最小的路径并记录下来；其中这一步不考虑链路上的带宽限制；

步骤S2：将网络中每段链路上通过的数据流量设为未知数，对于每个出度大于或等于2的结点，根据从该点流出的流是否流向从该点该点到汇点的链路开销最小的路径上的下一跳，用未知数表示出在该点处添加的虚假结点个数；

步骤S3：用线性规划求最小费用流的方法结合步骤S2中用未知数表示出的虚假结点个数，求出一数据传输路径，使得链路相关的开销和虚假结点相关开销的总和达到最小。

在本实施例中，步骤S1中，用一个无向图G＝(V,E)来表示网络，其中V为网络中的结点的集合，E为网络中的链路的集合，即边的集合；用C^S表示单位流量从每条边通过所需的开销的集合，用B^S表示每条边上剩余带宽的集合；用W1表示V中的结点数，用W2表示E中的边数，用W3和W4分别表示C^S和B^S中元素的个数；则V＝{v1,v2,...,vW1}，E＝{e1,e2,...,eW2}；如果l为G中的一条边，C(l)是单位流量从l通过所需的开销，B(l)是l上剩余的带宽，并且C(l)∈C^S，B(l)∈B^S；对于每一个e∈E,e＝＜vi,vj＞,vi,vj∈V,1≤i,j≤W1；网络请求包括源点、汇点、需求的带宽，用R＝(S,D,B^R)表示，其中，S表示源点，D表示汇点，B^R表示需求的宽带；目标为最小化虚假结点方面和链路方面的总开销用TC表示：

$>TC=\underset{l\in E}{\Sigma }\left(C\right(l)*f(l\left)\right)+\alpha F;$>

其中，f(l)表示边l上的流量，F表示网络中需要添加的虚假结点个数总和，α为一个可变参数，用来根据具体情况调整虚假结点方面和链路方面开销的所占的权重。

如图2所示，图2为一个拥有4个点和4条边的网络图，V＝{v1,v2,v3,v4}，E＝{e1,e2,e3,e4}。图中每条边上方框里的数表示该边的剩余带宽；每条边旁边的数表示单位数据从这条边通过所需的开销，比如C(e1)＝10，B(e1)＝20。

在本实施例中，步骤S1中所述用线性规划求最小费用流的方法求出每个源点到汇点的链路开销最小的路径并记录下来中，用线性规划求最小费用流时约束条件为：

(1)对于任一结点v∈V，且V不为源点或汇点，有：

$>\underset{vi\in V,vi\ne v,<vi,v>\in E}{\Sigma }f(<vi,v>)=\underset{vi\in V,vi\ne v,<v,vi>\in E}{\Sigma }f(<v,vi>);$>

(2)

(3)对所有边＜vi,s＞，如果vi∈V，且vi≠s，且＜vi,s＞∈E，则f(＜vi,s＞)＝0；

(4)

(5)对所有边＜t,vi＞，如果vi∈V，且vi≠t，且＜t,vi＞∈E，则f(＜t,vi＞)＝0；

线性规划的目标为：使最小。

例如，图2中，若B^R＝10，求v1到v4的链路开销最小的路径的约束条件为(将f(ei)设为未知数xi，1≤xi≤W2)；

$>\left(\begin{array}{c}x1=x2\\ x3=x4\\ x1+x3=10\\ x2+x4=10\end{array}\right)$>

目标为使x1×20+x2×20+x3×16+x4×16最小。

该线性规划需进行W1-1次以求出每个点到汇点的链路开销最小的路径并记录下来。

如图3所示，在本实施例中，所述步骤S2中用未知数表示出在该点处添加的虚假结点个数具体包括以下步骤：

步骤S21：设从A向A到汇点的最短路径上下一跳的流量为x，判断x是否等于从A点流出的总流量，若是，则在结点A处添加0个虚假结点；否则，进入步骤S22；

步骤S22：判断x是否等于0，若是，则进入步骤S23；否则进入步骤S24；

步骤S23：判断网络中是否存在一条边以A为弧尾，且该边上的流量等于从A流出的总流量；若是，则在结点A处添加1个虚假结点；否则在结点A处添加20个虚假结点；

步骤S24：判断x是否等于从A点流出的总流量的一半，若否，则在结点A处添加20个虚假结点；若是，则进入步骤S25；

步骤S25：判断网络中是否存在一条边以A为弧尾，且这条边不在A到汇点的最短路径上，且该边上的流量等于x，若是，则在结点A处添加1个虚假结点；否则，在结点A处添加20个虚假加点。

在本实施例中，所述步骤S3的线性规划的约束条件为：

(1)对于任一结点v∈V，且V不为源点或者汇点，有：

$>\underset{vi\in V,vi\ne v,<vi,v>\in E}{\Sigma }f(<vi,v>)=\underset{vi\in V,vi\ne v,<v,vi>\in E}{\Sigma }f(<v,vi>);$>

(2)

(3)对所有边＜vi,s＞，如果vi∈V，且vi≠s，且vi≠s，且＜vi,s＞∈E，则f(＜vi,s＞)＝0；

(4)

(5)对所有边＜t,vi＞，如果vi∈V，且vi≠t，且＜t,vi＞∈E，则f(＜t,vi＞)＝0；

(6)对每一条边l∈E，则f(l)≤B(l)；

线性规划的目标为：使得最小。

以上所述仅为本发明的较佳实施例，凡依本发明申请专利范围所做的均等变化与修饰，皆应属本发明的涵盖范围。