用于SDN的路径确定方法、装置、计算机设备及存储介质

摘要

本发明实施例提供了一种用于软件定义网络SDN的路径确定方法、装置、计算机设备及存储介质，应用于SDN网络的控制器，所述方法包括：接收目标请求；将目标请求的源节点加入空的节点集中；根据当前节点集外的节点与当前节点集内的节点的位置关系，计算SDN网络中当前节点集外的节点到源节点的时延值；从当前节点集外的节点中，选出目标节点，并将目标节点加入当前节点集；判断目标节点的标识信息是否与目的节点的标识信息匹配；若为是，将源节点到目标节点的路径确定为目标请求的目标路径；若为否，继续计算SDN网络中当前节点集外的节点到源节点的时延值。通过本方案，为目标请求选择时延值和带宽同时满足的目标路径，从而提高了网络链路利用率。

权利要求

1.一种用于软件定义网络SDN的路径确定方法，其特征在于，应用于SDN网络的控制器，所述方法包括：接收目标请求，其中，所述目标请求中至少包括：源节点标识信息、目的节点标识信息、带宽信息；

将源节点加入空的节点集中，其中，所述源节点为所述源节点标识信息对应的节点；

根据当前节点集外的节点与当前节点集内的节点的位置关系，计算所述SDN网络中所述当前节点集外的节点到所述源节点的时延值；

从所述当前节点集外的节点中，选出目标节点，并将所述目标节点加入所述当前节点集中，其中，所述源节点到所述目标节点的路径经过的链路的带宽大于等于所述带宽信息中的带宽值，且与所述当前节点集外除目标节点之外的其他节点到所述源节点的路径的时延值相比，所述源节点到所述目标节点的路径的时延值最小；

判断所述目标节点的标识信息是否与所述目的节点的标识信息匹配；

若为是，将所述源节点到所述目标节点的路径确定为所述目标请求的目标路径；

若为否，继续计算所述SDN网络中当前节点集外的节点到所述源节点的时延值；

在接收到多个请求时，将所述多个请求对应的路径保存在矩阵A中，其中，所述矩阵A的行数为N2，N为所述SDN网络中节点的数量，第n行表示第n条链路，节点序号为i的节点到节点序号为j的节点的链路为第(i-1)×N+j条链路，所述矩阵A的列数与所述多个请求的数量相等，第k列表示第k个请求，所述多个请求的顺序是按照网络侧接收到所述多个请求的时间顺序对所述多个请求进行排序得到的，所述矩阵A的元素值为1或0，若第k个请求的路径经过第n条链路，则所述矩阵的第n行第k列对应的元素值为1，若第k条请求的路径未经过第n条链路，则所述矩阵的第n行第k列对应的元素值为0；

在∑1≤k≤KA[n][k]×maxk×x[1][k]≤B[n][1]时，计算目标函数取得最大值时对应的x，其中，k为第k个请求，n为第n条链路，A[n][k]为所述矩阵A中第n行第k列对应的元素值，maxk为第k个请求需要占用的带宽，B[n][1]为第n条链路的带宽，x为一个行矩阵，所述行矩阵的列数与所述多个请求的数量相等，第k列表示第k个请求，若所述SDN网络为第k个请求提供网络服务，则x[1][k]为1，若所述SDN网络没有为第k个请求提供网络服务，则x[1][k]为0；

控制所述SDN网络为x[1][k]为1对应的请求提供网络服务。

2.根据权利要求1所述的方法，其特征在于，所述根据当前节点集外的节点与当前节点集内的节点的位置关系，计算所述SDN网络中所述当前节点集外的节点到所述源节点的时延值的步骤，包括：当前节点集外的节点为所述源节点的相邻节点，将所述源节点到该节点的链路的时延值确定为该节点到所述源节点的时延值；或者当前节点集外的节点为所述源节点的非相邻节点且是当前节点集内除源节点之外的任一目标节点的相邻节点，将所述源节点到该目标节点的链路的时延值与该目标节点到该节点的链路的时延值之和确定为该节点到所述源节点的时延值；或者当前节点集外的节点为所述源节点的非相邻节点且是当前节点集内的任一目标节点的非相邻节点，将该节点到所述源节点的时延值确定为无穷大。

3.根据权利要求1所述的方法，其特征在于，

所述目标函数为 或者sum(x[1]

[k])，或者∑1≤k≤Kpriorityk×x[1][k]，其中，priorityk为第k个请求的优先级。

4.一种用于软件定义网络SDN的路径确定装置，其特征在于，应用于SDN网络的控制器，所述装置包括：目标请求接收模块、源节点加入节点集模块、时延值计算模块、目标节点确定模块、判断模块、确定模块；其中，所述目标请求接收模块，用于接收目标请求，其中，所述目标请求中至少包括：源节点标识信息、目的节点标识信息、带宽信息；

所述源节点加入节点集模块，用于将源节点加入空的节点集中，其中，所述源节点为所述源节点标识信息对应的节点；

所述时延值计算模块，用于根据当前节点集外的节点与当前节点集内的节点的位置关系，计算所述SDN网络中所述当前节点集外的节点到所述源节点的时延值；

所述目标节点确定模块，用于从所述当前节点集外的节点中，选出目标节点，并将所述目标节点加入所述当前节点集中，其中，所述源节点到所述目标节点的路径经过的链路的带宽大于等于所述带宽信息中的带宽值，且与所述当前节点集外除目标节点之外的其他节点到所述源节点的路径的时延值相比，所述源节点到所述目标节点的路径的时延值最小；

所述判断模块，用于判断所述目标节点的标识信息是否与所述目的节点的标识信息匹配；若为是，触发所述确定模块，若为否，触发所述源节点加入节点集模块；

所述确定模块，用于将所述源节点到所述目标节点的路径确定为所述目标请求的目标路径；

路径存储模块，用于在所述控制器接收到多个请求时，将所述多个请求对应的路径保存在矩阵A中，其中，所述矩阵A的行数为N2，N为所述SDN网络中节点的数量，第n行表示第n条链路，节点序号为i的节点到节点序号为j的节点的链路为第(i-1)×N+j条链路，所述矩阵A的列数与所述多个请求的数量相等，第k列表示第k个请求，所述多个请求的顺序是按照网络侧接收到所述多个请求的时间顺序对所述多个请求进行排序得到的，所述矩阵A的元素值为1或0，若第k个请求的路径经过第n条链路，则所述矩阵的第n行第k列对应的元素值为1，若第k条请求的路径未经过第n条链路，则所述矩阵的第n行第k列对应的元素值为0；

行矩阵计算模块，用于在∑1≤k≤KA[n][k]×maxk×x[1][k]≤B[n][1]时，计算目标函数取得最大值时对应的x，其中，k为第k个请求，n为第n条链路，A[n][k]为所述矩阵A中第n行第k列对应的元素值，maxk为第k个请求需要占用的带宽，B[n][1]为第n条链路的带宽，x为一个行矩阵，所述行矩阵的列数与所述多个请求的数量相等，第k列表示第k个请求，若所述SDN网络为第k个请求提供网络服务，则x[1][k]为1，若所述SDN网络没有为第k个请求提供网络服务，则x[1][k]为0；

网络服务控制模块，用于控制所述SDN网络为x[1][k]为1对应的请求提供网络服务。

5.根据权利要求4所述的装置，其特征在于，所述时延值计算模块，具体用于：

当前节点集外的节点为所述源节点的相邻节点，将所述源节点到该节点的链路的时延值确定为该节点到所述源节点的时延值；或者当前节点集外的节点为所述源节点的非相邻节点且是当前节点集内除源节点之外的任一目标节点的相邻节点，将所述源节点到该目标节点的链路的时延值与该目标节点到该节点的链路的时延值之和确定为该节点到所述源节点的时延值；或者当前节点集外的节点为所述源节点的非相邻节点且是当前节点集内的任一目标节点的非相邻节点，将该节点到所述源节点的时延值确定为无穷大。

6.根据权利要求4所述的装置，其特征在于，

所述目标函数为 或者sum(x[1]

[k])，或者∑1≤k≤Kpriorityk×x[1][k]，其中，priorityk为第k个请求的优先级。

7.一种计算机设备，其特征在于，包括处理器、通信接口、存储器和通信总线，其中，处理器，通信接口，存储器通过总线完成相互间的通信，存储器，用于存放计算机程序；

处理器，用于执行存储器上所存放的程序时，实现权利要求1-3任一所述的方法步骤。

8.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质内存储有计算机程序，所述计算机程序被处理器执行时实现权利要求1-3任一所述的方法步骤。

说明书

用于SDN的路径确定方法、装置、计算机设备及存储介质

技术领域

[0001] 本发明涉及网络通信技术领域，特别是涉及一种用于软件定义网络SDN的路径确定方法及装置。

背景技术

[0002] 软件定义网络SDN(Software Defined Network，SDN)是一种新型的网络，是网络虚拟化的一种实现方式，SDN网络可以实现网络控制平面与数据转发平面的互相分离。

[0003] 在SDN网络中，控制器接收到用户端发送的请求时，首先要为接收到的请求确定路径。并且，在现有技术中，控制器为接收到的请求确定的路径只需要满足时延最短的要求。但是，有些情况下，控制器确定的路径可能不能满足该请求需要占用的带宽，这种情况下，该路径所经过的链路将不能被利用，从而导致网络链路利用率较低。

发明内容

[0004] 本发明实施例的目的在于提供一种用于软件定义网络SDN的路径确定方法、装置、计算机设备及存储介质，以提高网络链路利用率。具体技术方案如下：

[0005] 第一方面，本发明实施例提供了一种用于软件定义网络SDN的路径确定方法，应用于SDN网络的控制器，所述方法包括：

[0006] 接收目标请求，其中，所述目标请求中至少包括：源节点标识信息、目的节点标识信息、带宽信息；

[0007] 将源节点加入空的节点集中，其中，所述源节点为所述源节点标识信息对应的节点；

[0008] 根据当前节点集外的节点与当前节点集内的节点的位置关系，计算所述SDN网络中所述当前节点集外的节点到所述源节点的时延值；

[0009] 从所述当前节点集外的节点中，选出目标节点，并将所述目标节点加入所述当前节点集中，其中，所述源节点到所述目标节点的路径经过的链路的带宽大于等于所述带宽信息中的带宽值，且与所述当前节点集外除目标节点之外的其他节点到所述源节点的路径的时延值相比，所述源节点到所述目标节点的路径的时延值最小；

[0010] 判断所述目标节点的标识信息是否与所述目的节点的标识信息匹配；

[0011] 若为是，将所述源节点到所述目标节点的路径确定为所述目标请求的目标路径；

[0012] 若为否，继续计算所述SDN网络中当前节点集外的节点到所述源节点的时延值。

[0013] 可选地，所述根据当前节点集外的节点与当前节点集内的节点的位置关系，计算所述SDN网络中所述当前节点集外的节点到所述源节点的时延值的步骤，包括：

[0014] 当前节点集外的节点为所述源节点的相邻节点，将所述源节点到该节点的链路的时延值确定为该节点到所述源节点的时延值；或者

[0015] 当前节点集外的节点为所述源节点的非相邻节点且是当前节点集内除源节点之外的任一目标节点的相邻节点，将所述源节点到该目标节点的链路的时延值与该目标节点到该节点的链路的时延值之和确定为该节点到所述源节点的时延值；或者

[0016] 当前节点集外的节点为所述源节点的非相邻节点且是当前节点集内的任一目标节点的非相邻节点，将该节点到所述源节点的时延值确定为无穷大。

[0017] 可选的，所述方法还包括：

[0018] 在接收到多个请求时，将所述多个请求对应的路径保存在矩阵A中，其中，所述矩阵A的行数为N2，N为所述SDN网络中节点的数量，第n行表示第n条链路，节点序号为i的节点到节点序号为j的节点的链路为第(i-1)×N+j条链路，所述矩阵A的列数与所述多个请求的数量相等，第k列表示第k个请求，所述多个请求的顺序是按照网络侧接收到所述多个请求的时间顺序对所述多个请求进行排序得到的，所述矩阵A的元素值为1或0，若第k个请求的路径经过第n条链路，则所述矩阵的第n行第k列对应的元素值为1，若第k条请求的路径未经过第n条链路，则所述矩阵的第n行第k列对应的元素值为0；

[0019] 在∑1≤k≤KA[n][k]×maxk×x[1][k]≤B[n][1]时，计算目标函数取得最大值时对应的x，其中，k为第k个请求，n为第n条链路，A[n][k]为所述矩阵A中第n行第k列对应的元素值，maxk为第k个请求需要占用的带宽，B[n][1]为第n条链路的带宽，x为一个行矩阵，所述行矩阵的列数与所述多个请求的数量相等，第k列表示第k个请求，若所述SDN网络为第k个请求提供网络服务，则x[1][k]为1，若所述SDN网络没有为第k个请求提供网络服务，则x[1][k]为0；

[0020] 控制所述SDN网络为x[1][k]为1对应的请求提供网络服务。

[0021] 可选的，所述目标函数为 或者sum(x[1][k])，或者∑1≤k≤Kpriorityk×x[1][k]，其中，priorityk为第k个请求的优先级。

[0022] 第二方面，本发明实施例还提供了一种用于软件定义网络SDN的路径确定装置，应用于SDN网络的控制器，所述装置包括：目标请求接收模块、源节点加入节点集模块、时延值计算模块、目标节点确定模块、判断模块、确定模块；

[0023] 其中，

[0024] 所述目标请求接收模块，用于接收目标请求，其中，所述目标请求中至少包括：源节点标识信息、目的节点标识信息、带宽信息；

[0025] 所述源节点加入节点集模块，用于将源节点加入空的节点集中，其中，所述源节点为所述源节点标识信息对应的节点；

[0026] 所述时延值计算模块，用于根据当前节点集外的节点与当前节点集内的节点的位置关系，计算所述SDN网络中所述当前节点集外的节点到所述源节点的时延值；

[0027] 所述目标节点确定模块，用于从所述当前节点集外的节点中，选出目标节点，并将所述目标节点加入所述当前节点集中，其中，所述源节点到所述目标节点的路径经过的链路的带宽大于等于所述带宽信息中的带宽值，且与所述当前节点集外除目标节点之外的其他节点到所述源节点的路径的时延值相比，所述源节点到所述目标节点的路径的时延值最小；

[0028] 所述判断模块，用于判断所述目标节点的标识信息是否与所述目的节点的标识信息匹配；若为是，触发所述确定模块，若为否，触发所述源节点加入节点集模块；

[0029] 所述确定模块，用于将所述源节点到所述目标节点的路径确定为所述目标请求的目标路径。

[0030] 可选的，所述时延值计算模块，具体用于：

[0031] 当前节点集外的节点为所述源节点的相邻节点，将所述源节点到该节点的链路的时延值确定为该节点到所述源节点的时延值；或者

[0032] 当前节点集外的节点为所述源节点的非相邻节点且是当前节点集内除源节点之外的任一目标节点的相邻节点，将所述源节点到该目标节点的链路的时延值与该目标节点到该节点的链路的时延值之和确定为该节点到所述源节点的时延值；或者

[0033] 当前节点集外的节点为所述源节点的非相邻节点且是当前节点集内的任一目标节点的非相邻节点，将该节点到所述源节点的时延值确定为无穷大。

[0034] 可选的，所述装置还包括：

[0035] 路径存储模块，用于在所述控制器接收到多个请求时，将所述多个请求对应的路径保存在矩阵A中，其中，所述矩阵A的行数为N2，N为所述SDN网络中节点的数量，第n行表示第n条链路，节点序号为i的节点到节点序号为j的节点的链路为第(i-1)×N+j条链路，所述矩阵A的列数与所述多个请求的数量相等，第k列表示第k个请求，所述多个请求的顺序是按照网络侧接收到所述多个请求的时间顺序对所述多个请求进行排序得到的，所述矩阵A的元素值为1或0，若第k个请求的路径经过第n条链路，则所述矩阵的第n行第k列对应的元素值为1，若第k条请求的路径未经过第n条链路，则所述矩阵的第n行第k列对应的元素值为0；

[0036] 行矩阵计算模块，用于在∑1≤k≤KA[n][k]×maxk×x[1][k]≤B[n][1]时，计算目标函数取得最大值时对应的x，其中，k为第k个请求，n为第n条链路，A[n][k]为所述矩阵A中第n行第k列对应的元素值，maxk为第k个请求需要占用的带宽，B[n][1]为第n条链路的带宽，x为一个行矩阵，所述行矩阵的列数与所述多个请求的数量相等，第k列表示第k个请求，若所述SDN网络为第k个请求提供网络服务，则x[1][k]为1，若所述SDN网络没有为第k个请求提供网络服务，则x[1][k]为0；

[0037] 网络服务控制模块，用于控制所述SDN网络为x[1][k]为1对应的请求提供网络服务。

[0038] 可选的，所述目标函数为 或者sum(x[1][k])，或者∑1≤k≤Kpriorityk×x[1][k]，其中，priorityk为第k个请求的优先级。

[0039] 第三方面，本发明实施例还提供了一种计算机设备，包括处理器、通信接口、存储器和通信总线，其中，处理器，通信接口，存储器通过总线完成相互间的通信，[0040] 存储器，用于存放计算机程序；

[0041] 处理器，用于执行存储器上所存放的程序时，使得计算机设备执行上述任一所述的用于软件定义网络SDN的路径确定方法。

[0042] 第四方面，本发明实施例还提供了一种计算机可读存储介质，所述计算机可读存储介质内存储有计算机程序，所述计算机程序被处理器执行时使得计算机设备执行上述任一所述的用于软件定义网络SDN的路径确定方法。

[0043] 与现有技术相比，本发明实施例提供的技术方案，SDN控制器在接收到用户端发送的目标请求时，根据目标请求的源节点标识信息、目的节点标识信息及带宽信息，为目标请求选择的目标路径不仅满足时延值最短，而且目标路径的带宽能够满足目标请求需要占用的带宽，可以使网络中的链路资源得到充分利用，提高了网络链路利用率。

附图说明

[0044] 为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

[0045] 图1为本发明实施例所提供的一种用于软件定义网络SDN的路径确定方法的第一种流程示意图；

[0046] 图2为本发明实施例所提供的一种用于软件定义网络SDN的路径确定方法的第二种流程示意图；

[0047] 图3为本发明实施例所提供的一种用于软件定义网络SDN的路径确定方法的一种应用实例示意图；

[0048] 图4为本发明实施例所提供的一种用于软件定义网络SDN的路径确定装置的第一种结构示意图；

[0049] 图5为本发明实施例所提供的一种用于软件定义网络SDN的路径确定装置的第二种结构示意图；

[0050] 图6为本发明实施例所提供的一种计算机设备的结构示意图。

具体实施方式

[0051] 下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

[0052] 为了提高网络链路利用率，本发明实施例提供了一种用于软件定义网络SDN的路径确定方法及装置。

[0053] 需要说明的是，本发明实施例提供了一种用于软件定义网络SDN的路径确定方法及装置，优先适用于软件定义网络SDN的控制器。在该方法中，将网络设备抽象成节点，每个节点具有唯一的标识信息，链路用来连接SDN网络中任一节点与其相邻的节点，所述链路中的任一链路具有带宽及时延值。

[0054] 网络中的节点可以是个人计算机、服务器、路由器以及其他与网络连接的网络设备，这些都是合理的。

[0055] 下面首先对本发明实施例所提供的一种用于软件定义网络SDN的路径确定方法进行介绍。

[0056] 如图1所示，本发明实施例所提供的一种用于软件定义网络SDN的路径确定方法，可以包括如下步骤：

[0057] S110，接收目标请求，其中，所述目标请求中至少包括：源节点标识信息、目的节点标识信息、带宽信息；

[0058] 由于SDN网络既可以接收同一用户端发送的多条请求，也可以接收不同用户端发送的请求，因此，目标请求既可以是同一用户端发送的多条请求中的任意一条请求，也可以是不同用户端发送的请求中的任意一条请求，这都是合理的。

[0059] 并且，目标请求至少包括三个重要的参数，分别为源节点标识信息、目的节点标识信息、带宽信息。其中，源节点标识信息可以为源节点序号，目的节点标识信息可以为目的节点序号，带宽信息中包括带宽值，该带宽值为目标请求需要占用的带宽。

[0060] 举例而言，目标请求的数据流需要从源节点序号对应的节点传输到目的节点序号对应的节点，且在数据流传输过程中需要占用一定的带宽。因此，SDN控制器在接收到目标请求时，可以根据目标请求的源节点序号、目的节点序号、需要占用的带宽来为目标请求寻找路径。

[0061] S120，将源节点加入空的节点集中，其中，所述源节点为所述源节点标识信息对应的节点；

[0062] 在为目标请求寻找路由路径之前，SDN网络中存在一个空的节点集，该空的节点集可以是预先建立的，也可以是在接收到目标请求时建立的空节点集，这都是合理的。在接收到目标请求时，控制器可以将目标请求的源节点标识信息对应的源节点加入到该空的节点集中，以在后续步骤中计算SDN网络中当前节点集外的节点到源节点的时延值。

[0063] S130，根据当前节点集外的节点与当前节点集内的节点的位置关系，计算所述SDN网络中所述当前节点集外的节点到所述源节点的时延值；

[0064] 在将目标请求的源节点加入到空的节点集中之后，控制器可以计算当前节点集外各个节点到源节点的时延值。由于当前节点集内的节点除了源节点之外没有其他节点，因此，此时需要计算网络中除源节点之外的其他各个节点到源节点的时延值。

[0065] 需要说明的是，在当前节点集内只有源节点时，SDN网络中当前节点集外的节点可以分为两类节点，第一类节点是源节点的相邻节点，第二类节点是源节点的非相邻节点。若当前节点集外的节点为第一类节点时，也就是说，当前节点集的节点为所述源节点的相邻节点，将源节点到该节点的链路的时延值确定为该节点到源节点的时延值；若当前节点集外的节点为第二类节点时，也就是说，当前节点集的节点为所述源节点的非相邻节点，该节点到源节点的时延值为无穷大。

[0066] S140，从所述当前节点集外的节点中，选出目标节点，并将所述目标节点加入所述当前节点集中，其中，所述源节点到所述目标节点的路径经过的链路的带宽大于等于所述带宽信息中的带宽值，且与所述当前节点集外除目标节点之外的其他节点到所述源节点的路径的时延值相比，所述源节点到所述目标节点的路径的时延值最小；

[0067] 在S130计算出当前节点集外各个节点到源节点的时延值之后，为了保证为目标请求确定的路径的时延值最小，且为目标请求确定的路径的带宽大于等于目标请求需要占用的带宽，因此，选出的目标节点应该满足两个条件，第一个条件为目标节点到源节点的时延值最小；第二个条件为连接源节点与目标节点的链路的带宽大于等于目标请求需要占用的带宽。

[0068] 需要说明的是，由于若当前节点集外的节点是源节点的非相邻节点，则当前节点集外的节点到源节点的时延值为无穷大，因此，此时选出的目标节点不可能是源节点的非相邻节点。也就是说，选出的目标节点为节点集外与源节点相邻的节点，在选出目标节点之后，将目标节点加入当前节点中。

[0069] S150，判断所述目标节点的标识信息是否与所述目的节点的标识信息匹配；若为是，则执行S160，若为否，继续执行S130；

[0070] S160，将所述源节点到所述目标节点的路径确定为所述目标请求的目标路径。

[0071] 选出目标节点之后，判断选出的目标节点对应的标识信息是否与目标请求的目的节点的标识信息匹配，如果选出的目标节点对应的标识信息与目标请求的目的节点的标识信息相匹配，则目标请求寻路目标路径成功，则可以将源节点到目标节点的路径确定为目标请求的目标路径；如果选出的目标节点对应的标识信息不是目标请求的目的节点的标识信息，则继续计算当前节点集外的各个节点到源节点的时延值。

[0072] 需要说明的是，在继续计算当前节点集外的各个节点到源节点的时延值时，由于当前节点集中有除了有源节点，还有目标节点，因此此时当前节点集外的节点可以分为三类节点，第一类节点为源节点的相邻节点；第二类为源节点的相邻节点且是目标节点的相邻节点；第三类为源节点的非相邻节点且是目标节点的非相邻节点。

[0073] 若当前节点集外的节点为第一类节点时，该节点到源节点的时延值为连接源节点与该节点的链路的时延值；若当前节点集外的节点为第二类节点时，该节点到源节点的时延值为连接源节点与目标节点的链路的时延值与连接目标节点与该节点的链路的时延值之和；若当前节点集外的节点为第三类节点时，该节点到源节点的时延值为无穷大。当计算完时延值之后，继续执行S140和S150，直到选出的目标节点的标识信息与目标请求的目的节点的标识信息匹配时，目标请求寻找目标路径成功，并将源节点到目标节点的信息确定为目标路径，否则目标请求寻找目标路径失败。

[0074] 与现有技术相比，本发明实施例提供的一种用于软件定义网络SDN的路径确定方法，SDN网络在接收到用户端发送的目标请求时，根据目标请求的源节点标识信息、目的节点标识信息及需要占用的带宽，为目标请求选择的目标路径不仅满足时延值最短，而且目标路径的带宽能够满足目标请求需要占用的带宽，可以使网络中的链路资源得到充分利用，提高了网络链路利用率。

[0075] 与现有技术相比，本发明实施例提供的技术方案，SDN控制器在接收到用户端发送的目标请求时，根据目标请求的源节点标识信息、目的节点标识信息及带宽信息，为目标请求选择的目标路径不仅满足时延值最短，而且目标路径的带宽能够满足目标请求需要占用的带宽，可以使网络中的链路资源得到充分利用，提高了网络链路利用率。

[0076] 可选地，在一种实现方式中，如图2所示，所述方法还可以包括：

[0077] S170，在接收到多个请求时，将所述多个请求对应的路径保存在矩阵A中；

[0078] 为了后续通过计算确定为哪些请求提供网络服务，因此可以将网络侧接收到的多个请求对应的路径保存在矩阵A中。

[0079] 需要说明的是，当控制器接收到用户端发送的多个请求时，可以按照多个请求的接收时间顺序对多个请求进行排序，依次记为第1个请求、第2个请求、……、第k个请求，并按照此顺序依次为多个请求寻找路径。

[0080] 另外，假如网络中有N个节点，则矩阵A的行数为N2，每一行表示一条链路，第1行表示第1条链路，第n行表示第n条链路。其中，源节点序号为i的节点与目的节点序号为j的节点的链路在矩阵中对应第(i-1)×N+j条链路。当链路的源节点序号与目的节点序号相等时，该条链路没有实际意义，也就是说，当i＝j时，链路没有实际意义。

[0081] 举例而言，假如网络中有4个节点，节点序号分别为1、2、3、4，则网络中链路的条数为16条，第1条链路中，i＝1，j＝1，由于i＝j，所以该条链路没有实际意义；第2条链路中，i＝1，j＝2，也就是说，第2条链路是源节点序号为1的节点及目的节点序号为2的节点对应的链路；以此类推，第3条链路中，i＝1，j＝3；第4条链路中，i＝1，j＝4；第5条链路中，i＝2，j＝1；第6条链路中，i＝2，j＝2；第7条链路中，i＝2，j＝3；第8条链路中，i＝2，j＝4；第9条链路中，i＝3，j＝1；第10条链路中，i＝3，j＝2；第11条链路中，i＝3，j＝3；第12条链路中，i＝3，j＝4；第13条链路中，i＝4，j＝1；第14条链路中，i＝4，j＝2；第15条链路中，i＝4，j＝3；
第16条链路中，i＝4，j＝4。

[0082] S180，在∑1≤k≤KA[n][k]×maxk×x[1][k]≤B[n][1]时，计算目标函数取得最大值时对应的x；

[0083] 由于网络中每条链路为请求提供的实际带宽总和不能大于该条链路的最大带宽，即∑1≤k≤KA[n][k]×maxk×x[1][k]≤B[n][1]。在此约束条件下，可以计算目标函数取得最大值时对应的x，由于行矩阵的第k列对应的元素值表示第k个请求是否被网络服务，所以可以通过计算目标函数取得最大值时对应的行矩阵，确定在目标函数取得最大值时，哪些请求能得到网络服务，哪些请求不能得到网络服务。

[0084] 需要强调的是，对于一个请求而言，该请求可能被网络服务，也可以被网络拒绝服务，不存在请求被部分服务的情况。也就是说，网络可能为该请求提供该请求需要占用的带宽，也可能为该请求提供带宽的为0，不会存在网络为一个请求提供的带宽大于0，但小于该请求需要占用的带宽的情况。

[0085] 可选的，所述目标函数可以为由于 表示多个请求在SDN网络中实际占
用的带宽总和，通过求得该目标函数的最大值，可以使网络中带宽资源得到充分的利用。

[0086] 需要说明的是，在一种实现方式中，可以利用线性规划来求得多个请求在SDN网络中实际占用的带宽总和，并求得网络中带宽总和取得最大值时对应的最优解，即求得x，从而得到在网络中带宽总和取得最大值时，哪些请求能得到服务，而哪些请求不能得到服务；其中，线性规划的目标函数为 且由于网
络中每条链路为占用该条链路的请求提供的带宽总和不能大于该条链路的最大带宽，所以线性规划的约束条件是∑1≤k≤KA[n][k]×maxk×x[1][k]≤B[n][1]，其中，B[n][1]为第n条链路的最大带宽。可以理解的是，本领域技术人员应该理解线性规划的具体求解过程，在此不再赘述线性规划的具体求解过程。

[0087] 可选的，所述目标函数可以为sum(x[1][k])。需要说明的是，sum(x[1][k]表示被SDN网络服务的请求的数量总和，求得被网络服务的请求的数量总和的最大值，可以使可能多的请求被网络服务，避免因个别请求占用过多的带宽而导致其他大多数请求不能被网络服务的情况，并计算该数量总和取得最大值时对应的行矩阵，由于行矩阵的第k列对应的元素值表示第k个请求是否被网络服务，所以可以通过计算该数量总和取得最大值时对应的行矩阵，确定在被网络服务的请求的数量总和取得最大值时，哪些请求能得到网络服务，哪些请求不能得到网络服务。

[0088] 需要说明的是，在一种实现方式中，可以利用线性规划来求得被网络服务的请求的数量总和的最大值，并求得该数量总和取得最大值时对应的最优解，即求得x，从而得到该数量总和取得最大值时，哪些请求能得到服务，而哪些请求不能得到服务；其中，线性规划的目标函数为sum(x[1][k])，且由于网络中每条链路为占用该条链路的请求提供的带宽总和不能大于该条链路的最大带宽，所以线性规划的约束条件是∑1≤k≤KA[n][k]×maxk×x[1][k]≤B[n][1]，其中，B[n][1]为第n条链路的最大带宽。可以理解的是，本领域技术人员应该理解线性规划的具体求解过程，在此不再赘述线性规划的具体求解过程。

[0089] 可选的，所述目标函数可以为∑1≤k≤Kpriorityk×x[1][k]，其中，priorityk为第k个请求的优先级。由于不同的请求的优先级不同，有些请求的优先级较高，而有些请求的优先级较低，在该实施例中，请求的优先级值越大，请求的优先级越高。

[0090] 为了使在网络带宽资源不能满足所有请求的带宽总和时，网络优先为优先级较高的请求提供服务，因此，以被网络服务的请求的优先级总和为最优化目标。也就是说，求得被网络服务的请求的优先级总和的最大值，并计算该优先级总和取得最大值时对应的行矩阵，由于行矩阵的第k列对应的元素值表示第k个请求是否被网络服务，所以可以通过计算该优先级总和取得最大值时对应的行矩阵，确定在被网络服务的请求的优先级总和取得最大值时，哪些请求能得到网络服务，哪些请求不能得到网络服务。

[0091] 需要说明的是，在一种实现方式中，可以利用线性规划来求得被网络服务的请求的优先级总和的最大值，并求得该优先级总和取得最大值时对应的最优解，即求得x[1][k]，从而得到该优先级总和取得最大值时，哪些请求能得到服务，而哪些请求不能得到服务；其中，线性规划的目标函数为∑1≤k≤Kpriorityk×x[1][k]，且由于网络中每条链路为占用该条链路的请求提供的带宽总和不能大于该条链路的最大带宽，所以线性规划的约束条件是∑1≤k≤KA[n][k]×maxk×x[1][k]≤B[n][1]，其中，B[n][1]为第n条链路的最大带宽。可以理解的是，本领域技术人员应该理解线性规划的具体求解过程，在此不再赘述线性规划的具体求解过程。

[0092] S190，控制所述SDN网络为x[1][k]为1对应的请求提供网络服务。

[0093] 在求得目标函数取得最大值对应的行矩阵x之后，若行矩阵的第k列对应的元素值为1时，说明在目标函数取得最大值时，SDN网络为第k个请求提供网络服务，因此，控制器可以控制SDN网络为x[1][k]为1对应的请求提供网络服务。

[0094] 与现有技术相比，本发明实施例提供的技术方案，SDN控制器在接收到用户端发送的目标请求时，根据目标请求的源节点标识信息、目的节点标识信息及需要占用的带宽，为目标请求选择的目标路径不仅满足时延值最短，而且目标路径的带宽能够满足目标请求需要占用的带宽，可以使网络中的链路资源得到充分利用，提高了网络链路利用率。而且通过将各个请求寻找路径的结果存储在矩阵A中，通过计算目标函数取得最大值时对应的行矩阵x，有利于控制器对网络资源进行集中调控，从而可以使得请求被SDN网络服务的情况与请求达到SDN网络的先后顺序无关，进而能够提高SDN网络的服务率；并且为多个请求提高差异化服务，从而多个请求能够得到更加公平的服务。

[0095] 下面结合具体的实施例，对本发明实施例所提供的一种用于软件定义网络SDN的路径确定方法进行介绍。

[0096] 如图3所示，该应用实例中，将网络抽象成一个无向图，无向图的4个顶点表示网络中的4个节点，每个节点旁边标有一个数字，其代表节点的节点序号，因此，4个节点序号分别为1、2、3、4，连接相邻节点的边表示链路，连接相邻节点的边外侧的数字为链路的带宽，连接相邻节点的边内侧的数字为链路的时延值。

[0097] 其中，连接节点序号为1的节点和节点序号为4的节点的链路的带宽为8，时延值为2；连接节点序号为4的节点和节点序号为2的节点的链路的带宽为6，时延值为3；连接节点序号为2的节点和节点序号为3的节点的链路的带宽为5，时延值为1；连接节点序号为1的节点和节点序号为3的节点的链路的带宽为1，时延值为2。

[0098] 假设当前网络侧依次接收到3个请求，第1个请求的源节点序号为1，目的节点序号为2，需要占用的带宽为2，优先级为5；第2个请求的源节点序号为4，目的节点序号为2，需要占用的带宽为6，优先级为10；第3个请求的源节点序号为4，目的节点序号为2，需要占用的带宽为3，优先级为15。

[0099] 首先，软件定义网络SDN的控制器依次为第1个请求、第2个请求、第3个请求寻找路径，具体过程为：

[0100] 1、将第1个请求的源节点序号对应的源节点加入到空的节点集中，也就是说，将节点序号为1的节点加入到空的节点集中。

[0101] 2、计算当前节点集外节点序号分别为2、3、4对应的节点与源节点的时延值，由于节点序号为2的节点与源节点是非相邻节点，所以节点序号为2的节点与源节点的时延值为无穷大；节点序号为3的节点与源节点是相邻节点，因此，节点序号为3的节点与源节点的时延值为连接这两个节点的链路的时延值，该时延值为2；节点序号为4的节点与源节点是相邻节点，因此，节点序号为4的节点与源节点的时延值为连接这两个节点的链路的时延值，该时延值也为2。

[0102] 综上所述，节点序号为2、3、4的节点与源节点的时延值分别为无穷大、2、2。

[0103] 3、从节点序号为2、3、4的节点中选出目标节点，由于节点序号为3的节点和节点序号为4的节点到源节点的时延值最小，且都为2，但连接节点序号为1的节点和节点序号为3的节点的链路的带宽为1，该带宽小于第1个请求需要占用的带宽，而连接节点序号为1的节点和节点序号为4的节点的链路的带宽值为8，该带宽大于第1个请求需要占用的带宽，因此，目标节点为节点序号为4的节点，并将该目标节点加入到当前节点集中。

[0104] 需要说明的是，若连接节点序号为1的节点和节点序号为3的节点的链路的带宽，以及连接节点序号为1的节点和节点序号为4的节点的链路的带宽均大于等于第1条请求需要占用的带宽，则选择节点序号为3的节点作为目标节点，也就是说，选择节点序号较小的节点作为目标节点。

[0105] 4、由于目标节点的节点序号为4，而第1个请求的目的节点序号为2，因此判断出目标节点的节点序号不是第1个请求的目的节点序号。因此，接下来需要继续计算当前节点集外的各个节点与源节点的时延值。

[0106] 5、计算节点集外节点序号为2的节点和节点序号为3的节点到源节点的时延值。

[0107] 对于节点序号为2的节点来说，由于节点序号为2的节点为目标节点的相邻节点，所以节点序号为2的节点到源节点的时延值为源节点到目标节点的链路的时延值，以及目标节点到节点序号为2的节点的链路的时延值之和，经计算节点序号为2的节点到源节点的时延值为5。

[0108] 对于节点序号为3的节点来说，节点序号为3的节点与源节点的时延值已经在第3步中计算，该时延值为2。

[0109] 6、从节点序号为2的节点和节点序号为3的节点中再次选出目标节点。

[0110] 对于节点序号为2的节点来说，连接源节点与目标节点的链路，以及连接目标节点与节点序号为2的节点的链路的带宽分别为8、6，均大于第1个请求需要占用的带宽；而对于节点序号为3的节点来说，连接节点序号为1的节点和节点序号为3的节点的链路的带宽为1，小于第1个请求需要占用的带宽；所以，再次选出的目标节点为节点序号为2的节点，并将该节点作为目标节点，再次加入当前节点集中。

[0111] 7、由于再次选出的目标节点的节点序号为2，而第1个请求的目的节点序号也为2，所以第1个请求寻找路径成功，其中，第1个请求的路径经过两条链路，首先经过i＝1，j＝4的链路，然后经过i＝4，j＝2的链路，也就是说，第1个请求的路径先后经过第4条链路、第14条链路。

[0112] 8、按照为第1个请求寻找路径的方法，为第2个请求及第3个请求寻路，第2个请求及第3个请求都寻找路径成功，其中，第2个请求的路径和第3个请求的路径都只经过一条链路，且经过的链路都为第14条链路。

[0113] 在为第1个请求、第2个请求、第3个请求寻找路径之后，将第1个请求、第2个请求、第3个请求寻找路径的结果都存储在矩阵A中，存储结果如下：

[0114] 矩阵A

[0115]0 0 0
0 0 0
0 0 0
1 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
1 1 1
0 0 0
0 0 0

[0116] 由于这三个请求的路径中，经过的链路为第4条链路和第14条链路，因此，需要保证第4条链路和第14条链路为请求提供的带宽小于等于其对应的最大带宽，并将此条件作为线性规划的约束条件，可以用如下表达式表示；

[0117]

[0118] 接下来，既可以以3个请求在SDN网络中占用的实际带宽总和为目标函数，经线性规划计算得到SDN网络中占用的带宽总和的最大值为6，在带宽总和取得最大值时，行矩阵x为{0,1,0}，也就是说，此时SDN网络为第2个请求提供网络服务。

[0119] 也可以以被SDN网络服务的请求的数量总和为目标函数，经线性规划计算得到被SDN网络服务的请求的数量总和的最大值为2，行矩阵x为{1,0,1}，也就是说，此时SDN网络为第1个请求和第3个请求提供网络服务。

[0120] 还可以以被网络服务的请求的优先级总和为目标函数，经线性规划计算得到被网络服务的请求的优先级总和的最大值为20，行矩阵x为{1,0,1}，也就是说，此时SDN网络为第1个请求和第3个请求提供网络服务。

[0121] 与现有技术相比，本发明实施例提供的技术方案，SDN控制器在接收到用户端发送的目标请求时，根据目标请求的源节点标识信息、目的节点标识信息及需要占用的带宽，为目标请求选择的目标路径不仅满足时延值最短，而且目标路径的带宽能够满足目标请求需要占用的带宽，可以使网络中的链路资源得到充分利用，提高了网络链路利用率。而且通过将各个请求寻找路径的结果存储在矩阵A中，通过计算目标函数取得最大值时对应的行矩阵x，有利于控制器对网络资源进行集中调控，从而可以使得请求被SDN网络服务的情况与请求达到SDN网络的先后顺序无关，进而能够提高SDN网络的服务率；并且为多个请求提高差异化服务，从而多个请求能够得到更加公平的服务。

[0122] 相应于上述方法实施例，本发明实施例提供了一种用于软件定义网络SDN的路径确定装置，应用于SDN网络的控制器，如图4所示，所述装置包括：

[0123] 目标请求接收模块410、源节点加入节点集模块420、时延值计算模块430、目标节点确定模块440、判断模块450、确定模块460；

[0124] 其中，

[0125] 所述目标请求接收模块410，用于接收目标请求，其中，所述目标请求中至少包括：源节点标识信息、目的节点标识信息、带宽信息；

[0126] 所述源节点加入节点集模块420，用于将源节点加入空的节点集中，其中，所述源节点为所述源节点标识信息对应的节点；

[0127] 所述时延值计算模块430，用于根据当前节点集外的节点与当前节点集内的节点的位置关系，计算所述SDN网络中所述当前节点集外的节点到所述源节点的时延值；

[0128] 所述目标节点确定模块440，用于从所述当前节点集外的节点中，选出目标节点，并将所述目标节点加入所述当前节点集中，其中，所述源节点到所述目标节点的路径经过的链路的带宽大于等于所述带宽信息中的带宽值，且与所述当前节点集外除目标节点之外的其他节点到所述源节点的路径的时延值相比，所述源节点到所述目标节点的路径的时延值最小；

[0129] 所述判断模块450，用于判断所述目标节点的标识信息是否与所述目的节点的标识信息匹配；若为是，触发所述确定模块460，若为否，触发所述时延值计算模块430；

[0130] 所述确定模块460，用于将所述源节点到所述目标节点的路径确定为所述目标请求的目标路径。

[0131] 与现有技术相比，本发明实施例提供的技术方案，SDN控制器在接收到用户端发送的目标请求时，根据目标请求的源节点标识信息、目的节点标识信息及需要占用的带宽，为目标请求选择的目标路径不仅满足时延值最短，而且目标路径的带宽能够满足目标请求需要占用的带宽，可以使网络中的链路资源得到充分利用，提高了网络链路利用率。

[0132] 可选的，所述时延值计算模块430，具体用于：

[0133] 当前节点集外的节点为所述源节点的相邻节点，将所述源节点到该节点的链路的时延值确定为该节点到所述源节点的时延值；或者

[0134] 当前节点集外的节点为所述源节点的非相邻节点且是当前节点集内除源节点之外的任一目标节点的相邻节点，将所述源节点到该目标节点的链路的时延值与该目标节点到该节点的链路的时延值之和确定为该节点到所述源节点的时延值；或者

[0135] 当前节点集外的节点为所述源节点的非相邻节点且是当前节点集内的任一目标节点的非相邻节点，将该节点到所述源节点的时延值确定为无穷大。

[0136] 可选地，在一种实施方式中，如图5所示，所述装置还包括：

[0137] 路径存储模块470，用于在所述控制器接收到多个请求时，将所述多个请求对应的2
路径保存在矩阵A中，其中，所述矩阵A的行数为N ，N为所述SDN网络中节点的数量，第n行表示第n条链路，节点序号为i的节点到节点序号为j的节点的链路为第(i-1)×N+j条链路，所述矩阵A的列数与所述多个请求的数量相等，第k列表示第k个请求，所述多个请求的顺序是按照网络侧接收到所述多个请求的时间顺序对所述多个请求进行排序得到的，所述矩阵A的元素值为1或0，若第k个请求的路径经过第n条链路，则所述矩阵的第n行第k列对应的元素值为1，若第k条请求的路径未经过第n条链路，则所述矩阵的第n行第k列对应的元素值为
0；

[0138] 行矩阵计算模块480，用于在∑1≤k≤KA[n][k]×maxk×x[1][k]≤B[n][1]时，计算目标函数取得最大值时对应的x，其中，k为第k个请求，n为第n条链路，A[n][k]为所述矩阵A中第n行第k列对应的元素值，maxk为第k个请求需要占用的带宽，B[n][1]为第n条链路的带宽，x为一个行矩阵，所述行矩阵的列数与所述多个请求的数量相等，第k列表示第k个请求，若所述SDN网络为第k个请求提供网络服务，则x[1][k]为1，若所述SDN网络没有为第k个请求提供网络服务，则x[1][k]为0；

[0139] 网络服务控制模块490，用于控制所述SDN网络为x[1][k]为1对应的请求提供网络服务。

[0140] 可选的，所述目标函数为

[0141] 可选的，所述目标函数为sum(x[1][k])。

[0142] 可选的，所述目标函数为∑1≤k≤Kpriorityk×x[1][k]，其中，priorityk为第k个请求的优先级。

[0143] 与现有技术相比，本发明实施例提供的技术方案，SDN控制器在接收到用户端发送的目标请求时，根据目标请求的源节点标识信息、目的节点标识信息及需要占用的带宽，为目标请求选择的目标路径不仅满足时延值最短，而且目标路径的带宽能够满足目标请求需要占用的带宽，可以使网络中的链路资源得到充分利用，提高了网络链路利用率。而且通过将各个请求寻找路径的结果存储在矩阵A中，通过计算目标函数取得最大值时对应的行矩阵x，有利于控制器对网络资源进行集中调控，从而可以使得请求被SDN网络服务的情况与请求达到SDN网络的先后顺序无关，进而能够提高SDN网络的服务率；并且为多个请求提高差异化服务，从而多个请求能够得到更加公平的服务。

[0144] 在本发明提供的又一实施例中，还提供了一种计算机设备600，如图6所示，该计算机设备包括处理器610、通信接口620、存储器630和通信总线640，其中，处理器，通信接口，存储器通过总线完成相互间的通信；存储器，用于存放计算机程序；处理器，用于执行存储器上所存放的程序时，执行上述图1-图3任一实施例所述的用于软件定义网络SDN的路径确定方法。

[0145] 在本发明提供的又一实施例中，还提供了一种计算机可读存储介质，该计算机可读存储介质内存储有计算机程序，计算机程序被处理器执行时实现上述图1-图3任一实施例所述的用于软件定义网络SDN的路径确定方法。

[0146] 需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个……”限定的要素，并不排除在包括所述要素的过程、方法、物品或者设备中还存在另外的相同要素。

[0147] 本说明书中的各个实施例均采用相关的方式描述，各个实施例之间相同相似的部分互相参见即可，每个实施例重点说明的都是与其他实施例的不同之处。尤其，对于系统实施例而言，由于其基本相似于方法实施例，所以描述的比较简单，相关之处参见方法实施例的部分说明即可。

[0148] 以上所述仅为本发明的较佳实施例而已，并非用于限定本发明的保护范围。凡在本发明的精神和原则之内所作的任何修改、等同替换、改进等，均包含在本发明的保护范围内。