基于贪婪算法的集合覆盖方法获取SDN网中服务节点的方法

技术领域

本发明涉及计算机网络领域，尤其涉及一种基于贪婪算法的集合覆盖方 法获取SDN网中服务节点的方法。

背景技术

随着网络规模的不断扩大和应用类型的日益丰富，互联网的功能和结构 变得越来越复杂，这无疑给管理控制层面施以重压，越发不堪重负，管控能 力不断减弱。尤其是作为网络核心的路由器承载的功能越来越多，使得数据 转发单元变得非常臃肿，很难回到最初定义的简单的数据转发单元。我们急 需寻找一种新的、简单的重新部署和设计路由器的方法来解决TCP/IP体系结 构所面临的诸多问题，而不是如现在大部分厂家所做的那样，在现有的基础 上进行性能的提升和功能扩展。世界各国已经大规模开展未来互联网的研究, 如美国的GENI、欧盟的FIRE、日本的JGN2plus和我国的SOFIA等。研究未 来互联网体系结构首先考虑的是网络核心设备路由器的重新设计和部署，允 许用户自行定义路由器功能模块，实现适应未来互联网发展的新型协议功能。 目前，可编程虚拟化路由器已经受到广泛关注，而设计的开放性和可控性将 决定其设计思想是否可以得到长远的发展。

在此基础上，出现了SDN（Software Defined Network,，软件定义网络） 的概念。SDN作为一种最新的网络架构，对网络设备控制面、转发面和应用 层功能进行重新定义抽象，目的是对现有复杂的网络控制面进行抽象简化， 使控制面能独立创新发展，使得网络面向应用可编程。SDN是由美国斯坦福 大学Cleanslate研究组提出的一种新型网络架构，设计初衷是为了解决无法 利用现有网络中的大规模真实流量和丰富应用进行实验，以便研究如何提高 网络的速度、可靠性、能效和安全性等问题。其基本思想是把当前IP网络互 连节点中决定报文如何转发的复杂控制逻辑从交换机/路由器等设备中分离 出来，以便通过软件编程实现硬件对数据转发规则的控制，最终达到对流量 进行路由操控的目的。

SDN体系架构分为网络基础设施层、控制层和应用层三层。其中，控制 层中控制软件与基础设施中的交换/路由等网络设备经由控制数据面接口交 互，与应用层各种APP经由开放API交互；网络基础设施充当原交换/路由设 计中的转发面角色，也被称为OpenFlow交换。随着服务器、桌面、应用、存 储等虚拟技术的广泛应用，网络虚拟化的目的是为了在共享的同一物理网络 资源上划出逻辑上独立的网络，以满足多租户、流量隔离和逻辑网络自由管 控的应用趋势。SDN网络对基础网络硬件设施进行整网抽象，在控制器上增 加虚拟抽象层实现，有利于SDN应用层只看到整网视图的局部，并提供更加 抽象的网络资源描述，实现更加灵活的编程。

目前,ONF是SDN技术领域的推动者，其主要的研究成果包括了定义SDN 基本架构、OpenFlow标准和OpenFlow配置与管理协议。国际互联网工程组 成立了SDNBOF，并且提出了他们所认为的SDN架构。其早期的两个研究工作 组之一的ForCES已经发布了9个RFC，主要涉及需求、框架、协议、转发单 元模型、MIB(主系统模块master information block)等；另一个工作组 ALTO(网页电邮客户端)主要通过为应用层提供更多的网络信息来完成应用层 的流量优化。国际电信联盟在SG13组明确了SDN的研究任务，相关工作在 WP5组Q21研究。目前成立了Y.FNsdn-fm和Y.FNsdn两个项目，分别面向SDN 的需求和框架。中国通信标注化协会也成立了多个SDN研究组，主要涉及应 用场景及需求、问题分析、术语定义、互通规范和测试规范等等。SDN技术 还处于起步阶段，各方面都还处于尝试探索阶段，但是各国都积极参与到这 场网络改良工作中来，有待一日SDN必将付诸实施，真正达到其优化网络的 目的。2012年开始Cisco、HP、Arista等企业都开始利用SDN帮助其客户架 构更加灵活虚拟化的网络。目前运用最成功的是Google通过10Gbit/s网络 链接其分布在全球的12个数据中心，部署周密的流量工程和优先级调度工 作，将链路使用率提高到将近100%。

FlowVisor在控制器和OpenFlow交换机之间实现了基于OpenFlow的网 络虚拟层，它使得硬件转发平面能够被多个逻辑网络切片(slice)共享,每个 网络切片拥有不同的转发逻辑策略。在这种切片模式下，多个控制器能够同 时管理一台交换机，多个网络实验能够同时运行在同一个真实网络中，网络 管理者能够并行地控制网络，因此网络正常流量可以运行在独立的切片模式 下，从而保证正常流量不受干扰。

综上所述，网络进行虚拟化技术显得尤为重要。在虚拟化网络的构建过 程中，服务节点的选择至关重要。

该方案提出的基于贪婪算法的集合覆盖方法来选择SDN网络中的服务节 点的方法是借鉴移动对等网中超节点的选取算法，对其进行改进的基础上用 来对SDN网中服务节点的选取。SDN技术实现了控制和数据转发技术的分离， 但由于网络事件可能发生在任何一台交换机或端主机上，控制器和交换机之 间存在的时延将影响到控制器控制逻辑性能。

基于此，目前主要有两种思路来解决上述矛盾：

1）修改交换机的处理流程或硬件架构，或者给交换机增加部分控制功能， 从而减少控制器和交换机之间的信息交互，分担控制器负担，减少时延。（纵 向思路）

2）多控制器的分布式管控平面，通过分域管理网络，控制器之间实现基 本的状态分发过程。

发明内容

针对上述缺陷或不足，本发明的目的在于提供一种基于贪婪算法的集合 覆盖方法获取SDN网中服务节点的方法，能够有效的选取SDN网中的服务节 点。

为达到以上目的，本发明的技术方案为：

包括以下步骤：

1）、确定节点衡量指标，采用数据模糊归一化的方法，得到自治域中各 个节点的综合能力值；所述节点衡量指标包括计算能力、转发能力，以及节 点连接度；

2）、利用贪心算法，选出每一次都覆盖自治域中综合能力值最高的节点 S；

3）、将综合能力值最高的节点S确立为服务节点，并使其相邻的节点成 为该服务节点的子节点；

4）、去掉SDN网络中已经选出来的服务节点及其子节点构成的集合；

5）、重复步骤2）至4），直到该网络中没有可候选的网络节点为止，所 有确立的服务节点为最终的SDN网络服务节点。

步骤5）后还包括：

将选出的SDN网络服务节点设置一个综合能力值阈值M，将综合能力值 小于M的SDN网络服务节点作为和该服务节点距离最近的SDN网络服务节点 的子节点；

若该综合能力值小于M的SDN网络服务节点最近的SDN网络服务节点已 经达到了连接度的上限，则再找和其次近的服务节点，作为其子节点，以此 类推，直到找到能够连接的SDN网络服务节点。

所述步骤1）中采用数据模糊归一化的方法，得到自治域中各个节点的 综合能力值具体为:

1.1、对于节点的计算能力：

通过估算服务节点最大可处理的数据量，得到各节点的计算能力值，设 自治域中n个节点的计算能力值为（c₁,c₂,…,c_n）,根据SDN网络的最小计算 能力值min c,各个节点的计算能力为c_i,模糊归一化后的该节点的计算能力 值C_i'为：其中，i表示节点的序号，n为正整数；

1.2、对于节点的路由转发能力：

通过测量得到自治域中n个节点的路由转发能力，设各个节点的路由转 发能力值为（z₁,z₂,…,z_n）,SDN网络中要求的节点最小转发能力为min z， 节点的转发能力为Z_i,模糊归一化后的节点的转发能力值Zi'为: 其中，i表示节点的序号，n为正整数；

1.3、对于节点的连接度：

设自治域中n个节点的连接度为（d₁,d₂,…,d_n），SDN网络中要求的节点 最小连接度为min d，各个节点的连接度为d_i,模糊归一化后的节点的连接度 值D_i'为:其中，i表示节点的序号，n为正整数；

1.4、将标准化得到的C_i'，Z_i'和D_i'代入到综合评价公式中： Y_i=(C_i',Z_i',D_i')·W,(i=1,2,...,n)中，其中，W为各个指标所占的权重，最终节点的综 合能力值按Y_i的大小来排序。

所述步骤2）中利用贪心算法，选出每一次都覆盖自治域中综合能力值 最高的节点S具体为：

采用贪心算法遍历自治域中的所有节点，获得所有节点的综合能力值， 然后采用集合覆盖算法进行服务节点的选举；其中，集合覆盖问题的描述为：

在自治域中所有节点的综合能力值yi组成有限集Y，Y={y₁、y₂、y₃…… y_n}，设置有限集Y的子集为f₁、f₂……f_m，从所有子集中获取能够最小覆盖 所有节点的子集族F，其中，i为自治域中节点个数，m为子集个数。

当所选出的服务节点失效，则从和其相连的邻居节点中重新选出性能最 高的节点作为新的服务节点，其相邻的节点为该新的服务节点的子节点。

当有新节点加入时，首先计算和所有SDN网络服务节点的距离，得到与 所述新节点距离最短的SDN网络服务节点，然后判断服务节点的度约束：

d≤(θ/α)·C

d为与新节点距离最短的SDN网路服务节点的度，C表示与新节点距离最 短的SDN网络服务节点的计算能力；θ表示与新节点距离最短的SDN网络服 务节点的转发能力和计算能力比率，α表示新节点距离最短的SDN网络服务 节点转发能力影响因子；

若d>(θ/α)·C结果不在度约束范围内，则重新选择服务节点加入；

若d≤(θ/α)·C，则再将新节点与距离最短的SDN网络服务节点综合能力值 进行比较：若新节点综合能力值比该SDN网络服务节点的综合能力值小，则 直接加入；若新节点综合能力值比SDN网络服务节点的综合能力值大，则选 该节点作为新的服务节点，原来的服务节点作为该节点的子节点。

当已存在的节点需要离开，该节点首先通知和自己相连的SDN网络服务 节点，即发送离开请求的消息，服务节点收到请求后断开和此节点的连接。

与现有技术相比较，本发明的有益效果为：

本发明提供了一种基于贪婪算法的集合覆盖方法获取SDN网中服务节点 的方法，提出的集合覆盖方法选举服务节点的方法，算法思想简单，在一次 选举完成后，和服务节点相邻的节点便不用在参加后面的选举，后面的选举 涉及到的节点将越来越少，因此，比时间复杂度上算法性能优越，并且在一 次选举完成后，所有节点所保存的信息可用于服务节点的重新选择，大大降 低了系统的负载。进一步的，本发明通过在一个自治域中选择一个或多个SDN 网络服务节点，实现分布式控制，能有效减小在整个网络中只部署一个服务 节点时，跨域请求时造成的时延。

附图说明

图1是本发明的选举过程，其中，（a）为第一次选举过程，（b）为第二 次选举过程，（c）第三次选举过程；

图2是本发明选举结果图；

图3是本发明节点动态加入图；

图4是本发明算法流程图；

图5是本发明失效节点流程图；

图6是本发明节点动态加入流程图；

图7为本发明基于贪婪算法的集合覆盖方法来选择SDN网络中的服务节 点的方法流程图。

具体实施方式

为了使本发明的内容、效果以及优点更加清楚明白，下面结合附图和具 体实施例子对本发明进一步地详细阐述。

本发明基于贪婪算法的集合覆盖方法来选择SDN网络中的服务节点的方 法是借鉴移动对等网中超节点的选取算法，对其进行改进的基础上用来对 SDN网中服务节点的选取。SDN技术实现了控制和数据转发技术的分离，但由 于网络事件可能发生在任何一台交换机或端主机上，控制器和交换机之间存 在的时延将影响到控制器控制逻辑性能。

如图7所示，本发明提供了一种基于贪婪算法的集合覆盖方法获取SDN 网中服务节点的方法，包括以下步骤：

1）、确定节点衡量指标，采用数据模糊归一化的方法，得到自治域中各 个节点的综合能力值；所述节点衡量指标包括计算能力、转发能力，以及节 点连接度；

2）、利用贪心算法，选出每一次都覆盖自治域中综合能力值最高的节点 S；

3）、将综合能力值最高的节点S确立为服务节点，并使其相邻的节点成 为该服务节点的子节点；

4）、去掉SDN网络中已经选出来的服务节点及其子节点构成的集合；

5）、重复步骤2）至4），直到该网络中没有可候选的网络节点为止，所 有确立的服务节点为最终的SDN网络服务节点；

6）、将选出的SDN网络服务节点设置一个综合能力值阈值M，将综合能 力值小于M的SDN网络服务节点作为和该服务节点距离最近的SDN网络服务 节点的子节点；

若该综合能力值小于M的SDN网络服务节点最近的SDN网络服务节点已 经达到了连接度的上限，则再找和其次近的服务节点，作为其子节点，以此 类推，直到找到能够连接的SDN网络服务节点。

所述步骤1）中采用数据模糊归一化的方法，得到自治域中各个节点的 综合能力值具体为:

1.1、对于节点的计算能力：

通过估算服务节点最大可处理的数据量，得到各节点的计算能力值，设 自治域中n个节点的计算能力值为（c₁,c₂,…,c_n）,根据SDN网络的最小计算 能力值min c,各个节点的计算能力为c_i,模糊归一化后的该节点的计算能力 值C_i'为：其中，i表示节点的序号，n为正整数。

1.2、对于节点的路由转发能力：

通过测量得到自治域中n个节点的路由转发能力，设各个节点的路由转 发能力值为（z₁,z₂,…,z_n）,SDN网络中要求的节点最小转发能力为min z， 节点的转发能力为Z_i,模糊归一化后的节点的转发能力值Z_i'为: 其中，i表示节点的序号，n为正整数。

1.3、对于节点的连接度：

设自治域中n个节点的连接度为（d₁,d₂,…,d_n），SDN网络中要求的节点 最小连接度为min d，各个节点的连接度为d_i,模糊归一化后的节点的连接度 值D_i'为:其中，i表示节点的序号，n为正整数；

1.4、将标准化得到的C_i'，Z_i'和D_i'代入到综合评价公式中： Y_i=(C_i',Z_i',D_i')·W,(i=1,2,...,n)中，其中，W为各个指标所占的权重，最终节点的能 力值按Y_i的大小来排序。

所述步骤2）中利用贪心算法，选出每一次都覆盖自治域中综合能力值 最高的节点S具体为：

采用贪心算法遍历自治域中的所有节点，获得所有节点的综合能力值， 然后采用集合覆盖算法进行服务节点的选举；其中，集合覆盖问题的描述为：

在自治域中所有节点的综合能力值y_i组成有限集Y，Y={y₁、y₂、y₃……y_n}， 设置有限集Y的子集f₁、f₂……f_m，从所有子集中获取能够最小覆盖所有节点 的子集族F，其中，i为自治域中节点个数，m为子集个数。

示例性的，设置有限集X，有限集X中的元素为 X={A,B,C,D,E,F,G,H,I,K}.X的一个子集族F1中的元素为F1={S1，S2，S3， S4，S5}.S1={A,D}S2={B,C,E}S3={A,B,C,D}S4={{E,F,H}S5={G,I,K} S6={F,H,K}.则由此可知子集族F1覆盖了有限集X。也就是说X中的每一个 元素至少属于F1中的一个子集。对于F1中的一个子集C,若C中X的子集覆 盖了X,则称C覆盖了X。对于本例，集合覆盖问题就是要找出F1中覆盖X 的最小子集C*,对于本例C*={S3,S4,S5}.即C*为覆盖X的最小子集。

进一步的，当所选出的服务节点失效，则从和其相连的邻居节点中重新 选出性能最高的节点作为新的服务节点，其相邻的节点为该新的服务节点的 子节点。

当有新节点加入时，首先计算和所有SDN网络服务节点的距离d，得到 与所述新节点距离最短的SDN网络服务节点，然后判断节点的度约束：

d≤(θ/α)·C

C表示与新节点距离最短的SDN网络服务节点的计算能力；θ表示与新节 点距离最短的SDN网络服务节点的转发能力和计算能力比率，α表示新节点 距离最短的SDN网络服务节点转发能力影响因子；

若d结果不在度约束范围内，则重新选择服务节点加入；

若d≤(θ/α)·C，则再将新节点与距离最短的SDN网络服务节点综合能力值 进行比较：若新节点综合能力值比该SDN网络服务节点的综合能力值小，则 直接加入；若新节点综合能力值比SDN网络服务节点的综合能力值大，则选 该节点作为新的服务节点，原来的服务节点作为该节点的子节点。

当已存在的节点需要离开，该节点首先通知和自己相连的SDN网络服务 节点，即发送离开请求的消息，服务节点收到请求后断开和此节点的连接。

本发明的实施过程：

本发明适用于SDN网络架构下虚拟网络服务节点的选取机制，所提出的 算法能够有效快速的找到所需的服务节点，并且适用于节点的动态加入和退 出。

如图1所示，图1为一个自治域的网络物理拓扑结构示意图。假设每个 节点的能力值已经计算出来，具体如下：

A(10),B(5),C(4),D(1),E(9),F(6),G(7),H(3),I(8),K(2)

（1）采用贪婪算法，先遍历所有节点，统计各个节点的能力值，找到性 能最优的节点，作为第一轮选举的服务节点，再将其邻居节点选出作为其子 节点。在此图中，能力值最高的节点是节点A,其邻居节点是B,C,D。则在下 次选举时就将A,B,C,D从选举中剔除出去。第一次选举的范围如图1(a)。

（2）第二次选举时，在第一次的基础上，在剩下的节点中进行选举，进 一步选出节点E,则E为第二次选举时的服务节点，和其相邻的节点F和H将 在第三次选举时被剔除。第二次选举的范围图1(b)。

（3）第三次选举时，自治域中只剩下节点I,G,K。则可知在进行第三次 选举时，被选出来的节点是I,其邻居节点是G和K。第三次选举的范围图 1(c)。

（4）进行第四次选举时，由于自治域中已经没有节点，则选举结束。图 2为选举结束时选出来的服务节点图。选出来的服务节点为A,E,I.若选出来 的服务节点A失效，则再从节点B,C,D中进行选举，可知B节点将被选出， 则C,D将成为其子节点。以此类推，若节点E,I失效，同样从其子节点中进 行重新选举。

（5）对于节点的加入，假如有两个节点L和N要加入到网络中，它们首 先计算和已存在服务节点的距离，对于此图它们将找到节点E。L加入时，它 先判断节点E的节点度约束，假设在度约束范围内，再和E的能力值进行比 较，由于其能力值比E大，所以L将成为新的服务节点，E,F,H成为其子节 点。

对于节点N，它计算和服务节点的距离，可知L和I将被选出，然后判 断它们的度约束，若都在度约束范围内，再判断其能力值，可知L的能力值 大些，N将优先加入L,成为L的子节点。图3表示了节点动态加入图。

对于节点的离开，假如N要离开，它首先向它的服务节点L发送离开请 求消息，服务节点L收到消息后将此节点从它的子节点中去除。

图4为该算法的流程图，该流程的逻辑控制伪码可以写为如下的形式：

设X为一个自治域中所有节点的集合，F为X的一个子集族。集合U用 于存放每一个阶段中尚未被覆盖的X中元素。集合C包含了当前已构造的覆 盖。

给集合U、C赋初值，U<—X，

算法的循环体是整个算法的主体。在该循环体中，首先选择集合中性能 最高的节点S，然后确定其邻居节点，S的邻居节点和S共同构成集合S’。 然后，将U中被S’覆盖的元素删去，并将S加入C。算法结束时，C中包含 了覆盖X的F的一个子集族。且C中选出来的节点集S便为服务节点。

图5为节点失效时的流程图，首先对服务节点进行判断，若其没有失效 则继续选它为服务节点，若其失效则在其子节点中重新进行选择。图6为节 点动态加入时的流程图，先计算和服务节点的距离，再找要加入的服务节点， 比较能力值的大小，进行判断后再加入。

至此，已经完成了对SDN网络架构下虚拟网络服务节点的选取机制。通 过该机制，可以快速的进行服务节点的选择。在SDN网络架构下对虚拟网络 服务节点的选取，提出的集合覆盖方法选举服务节点的方法，算法思想简单， 在一次选举完成后，和服务节点相邻的节点便不用在参加后面的选举，后面 的选举涉及到的节点将越来越少，因此在时间复杂度上算法性能较优一些。 并且在一次选举完成后，所有节点所保存的信息可用于服务节点的重新选择， 大大降低了系统的负载。另外考虑了节点动态加入和离开变化问题，使算法 具有较好鲁棒性。本发明选取服务节点时综合考虑了多个指标，克服了选取 节点的标准单一的情况，更能反映出节点的真实能力值。