基于非线性退火的软件定义网络多约束路由方法

摘要

本发明公开了一种基于非线性退火的软件定义网络多约束路由方法，解决现有技术无法适用于软件定义网络的问题。本发明具体实现步骤是，首先利用扩散法，向外得到全网虚拟拓扑图；然后利用正向线性标记法、反向线性标记法和花费量测量法对全网虚拟拓扑图进行简化以缩小检索空间；最后运用非线性退火标记法对初始路径进行修正，得到满足约束的路径。本发明计算获得的路径可满足多约束的QoS需求；检索空间简化，时间复杂度确定，满足工业化设计要求，路由安排更加合理，网络性能得到提高。

主权项

基于非线性退火的软件定义网络多约束路由方法，其步骤包括如下：(1)获取全网虚拟拓扑图：(1a)转发组件将网络中转发组件的变更信息通知控制组件，控制组件得到本地子网内的实际网络拓扑图；(1b)隐藏本地子网内的节点，保留边界节点，采用最短路径查找法，查找两两边界节点之间的最小跳数路径，将所有的最小跳数路径作为虚拟链路；(1c)本地子网的边界节点向本地子网外发送查询分组信息，根据本地子网外返回的应答分组信息，得到相邻子网边界节点信息和该相邻子网边界节点所属的控制组件信息；(1d)本地子网的边界节点向本地子网外发送测量分组信息，相邻子网边界节点返回应答分组信息，本地子网的边界节点根据该应答分组信息得到相邻子网间连接链路的参数信息；(1e)创建链路状态分组表；(1f)使用扩散法，控制组件发布链路状态分组信息，得到全网虚拟拓扑图；(2)确定源边界节点和目的边界节点：(2a)源节点的控制组件向目的节点的控制组件发送信息，指明要到达的目的节点信息；(2b)目的节点的控制组件，采用最短路径查找法，计算从目的节点到本地子网所有边界节点之间的最小跳数路径，选择所有最小跳数路径中跳数最小的边界节点，返回给源节点的控制组件，作为目的边界节点；(2c)源节点的控制组件，采用最短路径查找法，计算从源节点到本地子网所有边界节点之间的最小跳数路径，选择所有最小跳数路径中跳数最小的边界节点，作为源边界节点；(3)线性标记：(3a)采用正向线性标记法，对全网虚拟拓扑图进行正向线性标记；(3b)采用反向线性标记法，对全网虚拟拓扑图进行反向线性标记；(4)处理节点：采用花费量测量法，对全网虚拟拓扑图中的节点进行处理；(5)判断全网虚拟拓扑图中所有节点是否都完成节点处理，若是，得到简化的全网虚拟拓扑图，执行步骤(6)；否则，执行步骤(4)；(6)正向线性标记：采用正向线性标记法，对简化的全网虚拟拓扑图进行正向线性标记；(7)反向非线性退火标记：将目的边界节点作为根节点root，采用非线性退火标记法，对简化的全网虚拟拓扑图进行反向非线性退火标记；(8)判断d_k(s)≤c_k是否成立，若是，源边界节点的控制组件得到路径；否则，执行步骤(9)；其中，k表示约束参数的个数，k的取值为1,2...K，K表示约束参数个数的最大值，d_k(s)表示根节点到源边界节点s之间使用非线性退火标记所求得的连接链路的第k个约束参数的值，c_k表示源边界节点s到目的边界节点t之间连接链路需要满足的第k个约束参数的值；(9)按照下式更新温度：$t=\frac{t_1}{\mathrm{grad}}$其中，t表示更新后简化的全网虚拟拓扑图的模拟温度值，t₁表示更新前简化的全网虚拟拓扑图的模拟温度值，grad表示温度下降的梯度值；(10)正向非线性退火标记：将源边界节点作为根节点root，采用非线性退火标记法，对简化的全网虚拟拓扑图进行正向非线性退火标记；(11)判断d_k(t)≤c_k是否成立，若是，源边界节点的控制组件得到路径；否则，执行步骤(12)；其中，k表示约束参数的个数，k的取值范围是1,2...K，K表示约束参数个数的最大值，d_k(t)表示根节点到目的边界节点t之间使用非线性退火标记所求得的连接链路的第k个约束参数的值，c_k表示源边界节点s到目的边界节点t之间连接链路需要满足的第k个约束参数的值；(12)按照下式更新温度和迭代次数：$t=\frac{t_1}{\mathrm{grad}}$I＝I₁‑1其中，t表示更新后简化的全网虚拟拓扑图的模拟温度值，t₁表示更新前简化的全网虚拟拓扑图的模拟温度值，grad表示温度下降的梯度值，I表示更新后的迭代次数，I₁表示更新前的迭代次数；(13)判断更新后的迭代次数I≤0是否成立，若是，执行步骤(14)；否则，执行步骤(8)；(14)查找失败，路由结束。