一种用于SDN控制器的水平方向接口系统

摘要

本发明公开了一种用于SDN控制器的水平方向接口系统，应用于软件定义网络领域。该系统包括网络视图学习单元，用于发现本地物理网络拓扑以及本地物理网络与其他网络之间的域间连接；网络视图抽象单元，将本地物理网络视图抽象为包含多个端口和多条链路的本地虚拟网络视图；水平接口单元，其用于与其他SDN控制器建立水平方向的连接；其中，本地SDN对等体通过所述对等虚拟网络向其他SDN对等体分发本地网络拓扑或者本地虚拟网络视图，并根据域间连接构建全局网络视图。本发明合理设置虚拟对等网络中的连接度，从而在出现网络失效时仍然能够保证对等网络中良好的连接状况，使得控制器间建立的虚拟对等网络更稳健。

权利要求

1.一种用于SDN控制器的水平方向接口系统，其特征在于，包括：

网络视图学习单元，其包括LLDP模块和LLDP扩展模块，所述LLDP模块用于发现本地物理网络拓扑，所述LLDP扩展模块用于发现本地物理网络与其他网络之间的域间连接；

网络视图抽象单元，其将本地物理网络视图抽象为包含多个端口和多条链路的本地虚拟网络视图；

水平接口单元，其用于与其他SDN控制器建立水平方向的连接，将SDN控制器抽象为彼此等价的SDN对等体，构建由全部SDN对等体构成的非结构化的对等虚拟网络；

其中，本地SDN对等体通过所述对等虚拟网络向其他SDN对等体分发本地网络拓扑或者本地虚拟网络视图，并根据域间连接构建全局网络视图；

对于跨域的数据流，根据所述全局网络视图计算端到端的路径，向沿路径的域控制器发送协作请求，在沿路径的域控制器中安装本地路径片段，从而建立跨域数据流端到端的完整路径，其中，所述LLDP是链路层发现协议。

2.根据权利要求1所述的用于SDN控制器的水平方向接口系统，其特征在于，在所述对等虚拟网络中，在SDN控制器硬件资源受限的前提下在对等体之间建立最大数目的连接，每一SDN对等体与其他对等体之间建立的连接数处于最小连接度和最大连接度之间。

3.根据权利要求2所述的用于SDN控制器的水平方向接口系统，其特征在于，在所述对等虚拟网络中，相邻两个对等体之间的跳数最小，以使得对等体之间的同步时间最短。

4.根据权利要求1所述的用于SDN控制器的水平方向接口系统，其特征在于，在本地物理网络拓扑更新的情况下，本地SDN控制器基于所述对等虚拟网络向其他SDN对等体并行发送更新文件。

5.根据权利要求4所述的用于SDN控制器的水平方向接口系统，其特征在于，新加入的SDN对等体从对等虚拟网络中的其他对等体获取全局网络视图文件。

6.根据权利要求1所述的用于SDN控制器的水平方向接口系统，其特征在于，所述本地虚拟网络为仅包含网络边缘交换机的虚拟网络，或者仅保留域间连接的虚拟节点，从而提供本地SDN控制器与其他SDN控制器之间交换的最少网络信息。

7.根据权利要求1所述的用于SDN控制器的水平方向接口系统，其特征在于，所述LLDP扩展模块还用于学习本地交换机的链接利用率、OpenFlow协议版本、流表数量和流表条目的数量，为本地SDN控制器向本地交换机下发流表提供依据。

8.根据权利要求1所述的用于SDN控制器的水平方向接口系统，其特征在于，所述网络视图包括网络静态信息和网络动态信息；其中，所述网络静态信息包括可达性信息、网络节点及拓扑信息、网络服能力和服务质量参数；

所述网络动态信息包括交换机当前流表条目内容、实时带宽使用率、流表使用率、网络实体存活状态和网络端口数据包统计。

9.根据权利要求8所述的用于SDN控制器的水平方向接口系统，其特征在于，根据SDN对等体之间实时带宽使用率向其他SDN对等体分发本地网络拓扑或者本地虚拟网络视图。

说明书

一种用于SDN控制器的水平方向接口系统

技术领域

[0001] 本发明涉及软件定义网络(Software Defined Network,SDN)领域，尤其涉及一种用于SDN控制器的水平方向接口系统。

背景技术

[0002] 软件定义网络以集中控制模式工作，在每个SDN网络上部署专用的网络操作系统(NOS，Network Operating System)。每个NOS可以学习当地的网络视图，从而控制如何转发其网络内的数据包。然而，互联网由多个不同的域共同管理，这使得集中控制在域间不起作用。整个网络中的数据包的路由控制需要每个NOS有一个相对全局的网络视图以确定数据包下一跳的网络。因此，NOS之间需要共享或交换域间网络信息，如可达性和拓扑信息。到目前为止，如何有效地交换此类信息，尤其是在多个NOS来自不同供应商的情况下，还没有得到很好的解决。

[0003] 所以，需要提供一种SDN水平方向接口系统来解决异构的NOS在域间SDN网络的合作问题，高效地交换和共享域间网络信息。

发明内容

[0004] 本发明的目的在于解决现有技术中异构NOS在域间SDN网络的合作中存在的缺陷。

[0005] 本发明提供一种用于SDN控制器的水平方向接口系统，包括：网络视图学习单元，其包括LLDP模块和LLDP扩展模块，所述LLDP模块用于发现本地物理网络拓扑，所述LLDP扩展模块用于发现本地物理网络与其他网络之间的域间连接；

[0006] 网络视图抽象单元，其将本地物理网络视图抽象为包含多个端口和多条链路的本地虚拟网络视图；

[0007] 水平接口单元，其用于与其他SDN控制器建立水平方向的连接，将SDN控制器抽象为彼此等价的SDN对等体，构建由全部SDN对等体构成的非结构化的对等虚拟网络；

[0008] 其中，本地SDN对等体通过所述对等虚拟网络向其他SDN对等体分发本地网络拓扑或者本地虚拟网络视图，并根据域间连接构建全局网络视图。

[0009] 在一个实施例中，在所述对等虚拟网络中，在SDN控制器硬件资源受限的前提下在对等体之间建立最大数目的连接，每一SDN对等体与其他对等体之间建立的连接数处于最小连接度和最大连接度之间。

[0010] 在一个实施例中，在所述对等虚拟网络中，相邻两个对等体之间的跳数最小，以使得对等体之间的同步时间最短。

[0011] 在一个实施例中，在本地物理网络拓扑更新的情况下，本地SDN控制器基于所述对等虚拟网络向其他SDN对等体并行发送更新文件。

[0012] 在一个实施例中，新加入的SDN对等体从对等虚拟网络中的其他对等体获取全局网络视图文件。

[0013] 在一个实施例中，对于跨域的数据流，根据全局网络视图计算端到端的路径，向沿路径的域控制器发送协作请求，在沿路径的域控制器中安装本地路径片段，从而建立跨域数据流端到端的完整路径。

[0014] 在一个实施例中，所述本地虚拟网络为仅包含网络边缘交换机的虚拟网络，或者仅保留域间连接的虚拟节点，从而提供本地SDN控制器与其他SDN控制器之间交换的最少网络信息。

[0015] 在一个实施例中，所述LLDP扩展模块还用于学习本地交换机的链接利用率、OpenFlow协议版本、流表数量和流表条目的数量，为本地SDN控制器向本地交换机下发流表提供依据。

[0016] 在一个实施例中，所述网络视图包括网络静态信息和网络动态信息；其中，[0017] 所述网络静态信息包括可达性信息、网络节点及拓扑信息、网络服能力和服务质量参数；

[0018] 所述网络动态信息包括交换机当前流表条目内容、实时带宽使用率、流表使用率、网络实体存活状态和网络端口数据包统计。

[0019] 在一个实施例中，根据SDN对等体之间实时带宽使用率向其他SDN对等体分发本地网络拓扑或者本地虚拟网络视图。

[0020] 本发明的实施例为异构NOS提供一种通用的水平方向接口方案，实现SDN管理域内子网间、SDN管理域间的互联互通，控制器间能够建立虚拟对等网络，共享网络的可达性和其他信息。此外，本发明的实施例合理设置虚拟对等网络中的连接度，从而在出现网络失效时仍然能够保证对等网络中良好的连接状况，使得控制器间建立的虚拟对等网络更稳健。

[0021] 本发明的其它特征和优点将在随后的说明书中阐述，并且部分地从说明书中变得显而易见，或者通过实施本发明而了解。本发明的目的和其他优点可通过在说明书、权利要求书以及附图中所特别指出的结构来实现和获得。

附图说明

[0022] 图1为本发明实施例的水平方向接口系统的示意图；

[0023] 图2为本发明实施例中将本地物理网络视图抽象为域内虚拟网络视图的示意图；

[0024] 图3为本发明实施例中生成虚拟对等网络的示意图；

[0025] 图4为本发明实施例中第(N+1)对等体加入虚拟对等网络的步骤流程图；

[0026] 图5为对等网络中每一节点接收信息的概率分布曲线；

[0027] 图6为单点失效和单链路失效的情况下网络可靠性曲线。

具体实施方式

[0028] 为使本发明的目的、技术方案和优点更加清楚，以下结合附图对本发明作进一步的详细说明。

[0029] 本发明的实施例提供一种SDN网络间对等互联的新型构架，设计了在SDN网络中水平方向的SDN对等体之间互联和通信机制。具体来说，涉及网络视图的抽象、存储、学习、虚拟化、表达及传输格式，网络视图信息分发和共享机制，为上层网络应用提供良好的运行环境。需要说明的是，本发明设计的水平方向对等互联架构是一种通用的对等机制，可应用于SDN管理域内的多个子网之间，也可应用于SDN的管理域之间。

[0030] 本发明提供的SDN水平方向接口系统所分发的网络信息的目的主要分为两个方面：(1)满足对等网络中网络操作系统(NOS)或者控制器之间协作的需求，例如共同建立跨NOS路径；(2)将学习到的全局视图以合理的数据结构，作为网络服务的形式提供给上层网络应用。

[0031] 为清楚起见，对下文中将要出现的关键术语进行说明。

[0032] 网络视图：是指网络拓扑、实体(交换机、链路、端口等)，网络可达性(路由)，网络能力，以及网络状态如数据流，带宽占用率等一切静态和动态的网络信息。

[0033] SDN子网：是指管理域内部署了一个SDN控制器实例范围的网络。

[0034] SDN域：SDN管理域。

[0035] 水平方向：控制器与控制器方向。说明：SDN网络中控制器向下控制交换机，控制器向上为网络应用创新提供API(Application Programming Interface)(通称北向API)。控制器之间是等价的，位于同一层次，水平方向通信就是指控制器之间的通信。

[0036] 本实施例提供的SDN控制器的水平方向接口系统内部包含了多个逻辑功能，如网络虚拟化(Network Virtualiztion)、水平方向接口(West-East Bridge Interface)、LLDP扩展(LLDP Extension)等。水平方向接口系统可设计为兼容不同网络操作系统NOS，可以向任意一个网络操作系统增加水平方向接口系统。

[0037] 系统结构

[0038] 图1为本实施例提供的SDN控制器的水平方向接口系统的结构示意图。如图1所示，接口系统包括网络视图学习单元、网络视图抽象单元和水平接口单元。

[0039] 网络视图学习单元用于发现控制器本地和域间的拓扑。网络视图学习模块包括LLDP模块和LLDP扩展模块。其中，LLDP(Link Layer Discovery Protocol，链路层发现协议)模块被用于控制器进行本地网络的拓扑发现，即发现本地物理网络拓扑，而LLDP扩展模块用于发现本地物理网络与其他域之间的域间连接。

[0040] 网络视图抽象单元将本地物理网络视图抽象为包含多个端口和多条链路的本地虚拟网络视图。具体而言，本地虚拟网络为仅包含网络边缘交换机的虚拟网络，或者仅保留域间连接的虚拟节点，从而提供本地SDN控制器与其他SDN控制器之间交换的最少网络信息。

[0041] 水平接口单元与其他SDN控制器建立水平方向的连接，将SDN控制器抽象为彼此等价的SDN对等体，构建由全部SDN对等体构成的非结构化的对等虚拟网络。其中，本地SDN对等体通过所述对等虚拟网络向其他SDN对等体分发本地网络拓扑或者本地虚拟网络视图，并根据域间连接构建全局网络视图。一旦学习到网络视图的所有信息，这些视图信息将会提供给上层的各种网络应用。

[0042] 网络视图学习

[0043] 现有技术中，链路层发现协议LLDP(Link Layer Discovery Protocol)被用于控制器进行本地的拓扑发现。通常情况下，每个SDN域的控制器会指示所有连接OpenFlow的交换机，从每台交换机的所有端口上发出LLDP数据包。其中，LLDP数据包携带着源交换机的标识，出口和其他信息。

[0044] 因为OpenFlow交换机依靠交换机内部的流表条目信息，对数据包进行匹配和转发。对于一个在流表中不存在相应匹配条目的数据包，OpenFlow交换机把这类数据当做一个新的数据流，并且把新数据流的第一个数据包发送给控制器。LLDP协议目前被互联网研究者应用于SDN网路内拓扑的发现过程。依靠OpenFlow交换机的该特点，交换机接收到LLDP链路发现数据包之后，邻居交换机会直接把此类数据包发送给上联的控制器。

[0045] 然后，控制器提取并分析从交换机接收到的该LLDP数据包：(1)如果LLDP数据包中携带的源交换机标识属于自己的网络(子网或管理域)，并且接收到此LLDP数据包的邻居也属于自己的网络，那么控制器会认为这是一个网络内的链路，并且创建一条从源交换机到其邻居的链路。(2)对于网络间链路，LLDP扩展模块的功能如下：如果源交换机的标识不属于本网络，控制器可以推断，这个LLDP数据包是来自其他的网络，那么控制器将会根据源交换机的标识，源交换机的出口，和物理位置在本网络的、收到LLDP数据包的这台邻居OpenFlow交换机及其入口，创建一个网络间的链路，如图2中的链路2(S6,S7)。需要强调的是：在交换本地网络视图之前，网络间链路两侧的网络都应该存储该网络间链路信息到自己本地的网络视图中。

[0046] LLDP扩展模块还用于发现更详细的网络视图信息，如OpenFlow版本号，每个OpenFlow交换机节点上的流表的数量、链路的使用率、流表条目内容等。通过统计每个端口在单位时间内收到的数据包个数，或单位时间内这台交换机上所有流表中与此端口相匹配的数据包个数，从而统计出端口流量和链路带宽使用率；通过调用OpenFlow协议的南向接口或交换机命令，可获得OpenFlow版本、流表数目、流表项等内容，从而为本地SDN控制器向本地交换机下发流表提供依据。

[0047] 更进一步，网络视图主要包含两类信息，网络静态信息和网络动态信息。网络静态信息包含以下几个方面：(1)可达性信息。在运营商网络中，可达性信息主要是指IP地址前缀；在数据中心，企业网中，可达性信息还包含主机和服务器地址信息。(2)网络节点及拓扑信息：节点信息(OpenFlow交换机，服务器，主机，控制器，防火墙，负载均衡器等)，链路，链路属性，端口吞吐量，链路连接状态。(3)网络服务能力。如基于等级的服务SLA(Service Level Agreement)支持情况，对GRE(Generic Routing Encapsulation)、SSL(Secure Sockets Layer)等网络协议的支持情况，节点流表数量，单表所支持流表条目数量等。(4)服务质量QoS(Quality of Service)参数。例如如费用、时延、时延抖动、丢包率、高可用性、可靠性、吞吐量等。

[0048] 网络动态信息方面主要包含以下几个方面的网络状态：(1)每台OpenFlow交换机上当前流表条目内容信息；(2)当前网络流信息；(3)网络实时带宽使用率；(4)流表使用率；(5)网络实体存活状态：节点、节点端口、链路；(6)网络端口数据包统计。

[0049] 网络视图抽象

[0050] 通常情况下，网络视图是指整个的网络状态信息。但是，考虑到安全问题和隐私问题，某些网络可能不愿意公开其全部的物理网络视图信息，而只是考虑公开其网络信息的一部分。根据这种实际需求，网络视图抽象单元支持从物理网络到虚拟网络的虚拟化，可将本地物理网络视图抽象为包含多个端口和多条链路的本地虚拟网络视图。

[0051] 图2为将本地物理网络视图抽象为本地虚拟网络视图的示意图。本实施例提供三种不同的视图虚拟化方法。

[0052] (1)把一个物理网络抽象成一个只包含有边界交换机的虚拟网络。如图2所示，路径片段如VP1，VP2，VP3从网络中的入口交换机到出口交换机之间可以带有SLA(Service Level Agreement)服务等级的路径属性。这些路径属性包含：时延，带宽，丢包率，高可用等。一种最简单的来估算入口交换机和出口交换机对间的费用，可以通过计算二者之间的跳数作为费用。OSPF(Open Shortest Path First，开放最短路径优先)同样采用了跳数来作为距离。

[0053] 如图2所示，将物理网络视图201抽象成为虚拟网络视图202，只保留边缘交换机S1和S6。其中，虚拟网络视图202中网络实体包括虚拟节点S1和S6，以及路径片段VP1，VP2，VP3等。虚拟网络视图202中的实体属性包括虚拟节点S1的IP地址，端口号，是否边缘节点，设备类型，设备功能，等等。

[0054] 网络控制器保存物理网络视图201与虚拟网络视图202之间的映射表(表1)。在表1中，PP(Physical Path)表示物理路径，VP(Virtual Path)表示虚拟路径。

[0055] 表1

[0056]PP VP SLA
(S1,S2,S6) (S1,S6) 延时
(S1,S3,S6) (S1,S6) 费用
(S1,S4,S5,S6) (S1,S6) 带宽

[0057] (2)把一个物理网络抽象成一个虚拟节点。这个虚拟节点仅仅保留网络间的链路如链路2，链路3，链路4。在图2中，将物理网络视图203抽象成为虚拟节点204。虚拟节点204只保留三个物理域间(跨域)链路。网络被抽象之后，网络控制器保存物理网络视图203与虚拟节点204之间的映射表，如表2所示。

[0058] 表2

[0059]PP VP SLA
(S7,S8,S11) S11 带宽
(S7,S8,S9,S10) S11 带宽

[0060] (3)当水平接口系统应用于管理域间时，考虑到一个管理域可能会包含多个自治域AS，如AS1和AS2属于同一管理域，那么自治域AS1和自治域AS2可以被抽象成一个仅仅含有管理域边界节点的域或者一个虚拟节点。

[0061] 在图2中，网络201和203可被抽象为只保留管理域边界交换机S1,S10和S11的虚拟域205，或者被抽象为一个虚拟节点206。

[0062] 需要强调的是，本实施例中网络视图抽象的显著效果在于，对于跨域数据流的转发可以有效避免传统路由机制中“洪范”现象的发生。

[0063] 为了计算出一条端到端的路由路径，位于网络操作系统之上的路径计算应用需要知道其他网络的网络视图。至少应该知道其他网络的虚拟视图信息。在所有域的水平方向接口系统交换本地网络视图之后，每个网络就可以基于所有的网络的本地网络视图，和网络间的链路及其属性，构建一个相对全局的网络视图，并且提供给上层应用。

[0064] 此时，路径计算应用就可以根据全局网络视图，计算出一条端到端的路径，并且可以把目的地址不在本网络的数据包直接发送到相应的边界出口交换机，这种方式比洪泛要高效。

[0065] 在水平方向接口系统中，路由一个数据包的流程如下。当一个SDN网络内的交换机收到一个数据包之后，他首先会检查交换机的流表中是否有相应的匹配条目。如果有，那么交换机就会根据流表进行匹配转发；如果没有，交换机会认为这是一个新的数据流，并且把该数据流的第一个数据包发送到控制器。控制器进一步触发路径计算应用。此时，路径计算应用会根据全局的视图来判断，数据包的目的地址是否属于本网络(子网或域)。如果属于，那么路径计算应用会计算出相应的路径和流表项，并且把流表项安装到本网络内相应的OpenFlow交换机上。如果不属于本网络，路径计算应用认为这个数据流是跨网络的数据流，它将会计算一条端到端(end-to-end)的路径，给沿路的相关网络的的路径计算应用发送协作请求，请求安装相关的路径片段，最后成功建立一条通往目的IP地址的路径，此数据包和其数据流被进行跨网路由。这里的路径片段的格式被设计如表3所示。

[0066] 表3

[0067]

[0068] 以下对协作建立路径的方式进行详细说明。如果水平方向接口系统的应用场景是同一管理域内或者不同管理域间，那么路径计算应用可以在计算出全局路径之后，给沿路相关的网络发送路径片段安装请求，然后相应网络根据请求进行流表项的计算和生成，并且安装路径片段到本网络。这种方式仅仅在网络上传输建路请求，是一种轻量级的方法。

[0069] 此外，在实际网络中，具体传输物理视图还是虚拟视图，取决于网络的实时带宽使用率和网络间的策略。但是要达到全网的互通，每个网络至少要把自己抽象成一个节点的虚拟视图进行共享。基于全局网络视图，水平方向接口系统还可以进一步提供更高级别的服务给上层的应用，如特定网络视图:接入网络视图，边缘网络视图等。

[0070] 虚拟对等网络

[0071] 在本实施例中，将SDN控制器抽象为对等体，通过相互连接构成一个无结构化的对等虚拟网络。我们把所有SDN对等体构成的网络抽象成一个如图3所示的无向连接图，用G表示。每个对等体用顶点V来标识，每两个SDN对等体之间的连接用一条边E来表示。由于每个SDN对等体的硬件资源是有限的，例如带宽、计算能力。每个控制器在现实中只能建立有限数目的连接。因此，进一步把一个对等体能够建立连接的最大数目用D来表示，而实时的连接数目用d来表示。在一个具有(N+1)个对等体构成的SDN网络中，如果最大连接度D等于N，那么这个对等体之间构成的虚拟拓扑就是一个全连接的(full-mesh)。

[0072] 需要说明的是，所有对等体建立合理的连接时，由对等体构成的网络中，连接数越多，网络越稳定，传输数据也就越可靠。具体来说，每一SDN对等体与其他对等体之间建立的连接数处于最小连接度和最大连接度之间。此外，在虚拟对等网络中，两个对等体之间的平均跳数越短，网络通信同步的速度就会越快。因此，可使相邻两个对等体之间的跳数最小，以使得对等体之间的同步时间最短。

[0073] 在一个优选的实施方式中，一个含有10个对等体的网络中，连接度设置为6以上，一个100个对等节点的网络中，连接度设置为7以上。

[0074] 以下结合图4说明第(N+1)对等体加入对等虚拟网络的步骤。

[0075] 在步骤S401中，首先该第(N+1)对等体VN+1注册自己，且获取可用的对等体列表。遍历列表中所有的对等体，计算每个对等体i的剩余连接度R(D)＝D-C(d)，其中D表示对等体i的可以建立的最大连接度，C(d)表示该对等体当前实时连接度。判断对等体i的剩余连接度R(D)是否大于等于1。如果R(D)>＝1，则表示该对等体可以被选择建立连接。统计所有R(D)>＝1的对等体，依次存入当前对等体集合target。其中包含的对等体的数量|targer|，记作num。

[0076] 随后，在步骤S402中判断第(N+1)对等体的最大连接度是否大于等于对等体的数量，即判断是否满足num<＝DN+1。若满足，则表示第(N+1)对等体有足够的资源和数量为num的对等体中每个对等体建立连接。那么执行步骤S403，第(N+1)对等体与当前对等体集合target中记录的每个对等体建立对等连接。

[0077] 若不满足，即num>DN+1，也即第(N+1)对等体的最大连接度小于num，则表示第(N+1)对等体没有足够的资源和数量为num的对等体中每个对等体建立连接，此时需要从target的对等体进一步选择合适的对等体与第(N+1)对等体建立连接。

[0078] 在步骤S404中判断DN+1的奇偶性，根据DN+1的奇偶性分别执行步骤S405和步骤S406。

[0079] 如果DN+1是偶数，在步骤S405中，按照步长为2，从k＝0到k＝DN+1遍历，每步k＝k+2，总共DN+1/2步。对于每一步执行如下操作。

[0080] 首先生成三角矩阵Z[n][n]，矩阵中第i行，第j列的元素是节点i到j的最短路径的跳数，(0<＝i<＝n,0<＝j<＝n，i<＝j)，；其次，找到矩阵Z[n][n]中数值最大的元素。如果有多个数值最大的元素，则选择所在行i和列j对应的节点vi和vj的当前节点度之和C(vi)+C(vj)最大的元素，当前节点度较大表明该节点已经建立较多的会话，通过和这样的节点建立连接，则可以缩小到其他节点的跳数，所以优先选择当前节点度之和较大的元素。如果当前节点度之和仍然相等，则随机选择一个元素。假设最后选择出的为第i行，第j列的元素，则节点Vi和Vj是选择出来的VN+1的对等体，更新target[k]＝Vi，target[k+1]＝Vj；最后更新矩阵Z[n+1][n+1]中相应元素的值。

[0081] 如果DN+1是奇数，在步骤S406中则对连接数DN+1-1执行步骤S405，对剩余的连接数1执行如下步骤。首先构建一个对称矩阵Z[n][n]，矩阵中第i行，第j列元素，(0<＝i<＝n,0<＝j<＝n)，是节点i到j的最短路径的跳数；其次，选出每一列元素的最大值，在这些最大值中再选择最小值。如果有多个最小值，则考察元素所在列的序号j对应的节点vj的当前节点度C(vj)，选择当前节点度最大的元素，假设最后节点Vj被选为节点VN+1的对等体，target[DN+1]＝Vj；最后更新矩阵Z[n+1][n+1]中相应元素的值。

[0082] 此外，本发明的实施例还支持具有联盟关系的SDN网络之间交互特定于该联盟的更细致的网络视图，建立东西向对等关系的SDN网络之间交换的网络视图会分为“联盟网络视图”和“普通(非联盟)网络视图”。两个建立对等关系的SDN网络通过OPEN消息交换各自的联盟号，默认联盟号为0表示不属于任何联盟。具有相同联盟号的SDN网络是同一个联盟。如果一个SDN网络得知对等的SDN网络是在相同的联盟，则可以交互特定于该联盟的“联盟网络视图”，同时还可以交互不针对任何联盟的“普通网络视图”。一个SDN网络A从某个对等SDN网络获得“联盟网络视图”，可以把该视图传递给A所对等的其他相同联盟的SDN网络，但是不能传递给A所对等的非相同联盟的SDN网络。而A从某个对等SDN网络获得的“普通网络视图”可以继续传递给A所对等的其他所有SDN网络。

[0083] 可行性分析

[0084] 在上文所述的虚拟对等网络中，网络故障可定义为两种类型：单点失效SNF和单链路失效SVLF。

[0085] 在单点失效(Single Node/NOS/Controller Failure，SNF)的情况下，这个点可以是网络实体节点如交换机，控制器或操作系统本身。单链路失效(Single Virtual Link Failure，SVLF)的一个示例如下。由于网络视图本身的增加，导致了某个对等体的最大连接度D减小，对已经建立的连接不能继续维持而丢失连接

[0086] 为了在出现网络故障是快速恢复，将全局网络视图存储在每一个域的控制器内。若某个域控制器失效，收到影响的SDN对等体可主动与其他顶点建立新的连接。

[0087] 和物理网络不同，所有SDN对等体构成的网络是无结构的，所有的邻居关系可以动态的改变。根据随机多播协议高斯理论对可靠性的分析：在一个具有N个节点的网络中，一个节点随机的向其他(logN+k)个节点传递信息，所有节点都收到该信息的概率趋向于exp(-exp(-k))。根据此理论，绘制图5。图5表示对等网络中每一节点接收信息的概率分布。

[0088] 如图5所示，当k＝5时，每个节点均接收到消息的概率趋向于99.3％。所以我们推荐k的值为5。这意味着当k≥5时，一个SDN网络中对等体保持连接的概率超过99.3％，无论单节点失效或单链路失效。

[0089] 优选地，在一个节点数目为N的SDN网络中，最小连接度设置为(logN+5)。由于99.5％的自治域需要划分的子网个数少于100。所以建议最小连接度是log100+5＝7。更详细的连接度建议值请参考表4。

[0090] 表4

[0091]N取值 最小连接度推荐值
<＝10 6
11～100 7
101～1000 8

[0092]1001～10000 9
>10001 logN+5

[0093] 在实际网络应用中，网络管理员可以根据自己的资源情况将连接度配置为一个位于最小连接度和(N-1)之间的值。但是，一旦资源足够的话，建议把连接度设置为最大(N-1)。连接度越大，SDN对等网络越健壮可靠。

[0094] 实验验证

[0095] 下文提供在单节点失效SNF和单链路失效SVLF两种情况下，对等网络连接状况的分析结果。

[0096] 根据夏普阈值理论(Sharp threshold theory)在随机图方面的结论：如果一个图形G是k连接的，具有n个顶点，边的可靠性是概率是p(n)，并且满足p(n)≥clog(n/k)(c是一个足够大的常量，c>0)，那么这个子图Gp是可以保证连结状态的。采用此理论模拟单链路失效SVLF以及单点失效SNF时的网络连接状况，如图6所示。

[0097] 从图6可以看出，当连接度大于等于3的时候，整个网络失效的概率接近0。因此在N＝100的时候，推荐的连接度值7是一个非常稳妥的值。

[0098] 本领域的技术人员应该明白，上述的本发明的各模块或步骤可以用通用的计算装置实现，它们可以集中在单个的计算装置上，或者分布在多个计算装置所组成的网络上，可选地，它们可以用计算装置可执行的程序代码来实现，从而，可以将它们存储在存储装置中由计算装置来执行，或者将它们分别制作成各个集成电路模块，或者将它们中的多个模块或者步骤制作成单个集成电路模块来实现。这样，本发明不限制于任何特定的硬件和软件结合。

[0099] 虽然本发明所公开的实施方式如上，但所述的内容只是为了便于理解本发明而采用的实施方式，并非用以限定本发明。任何本发明所属技术领域内的技术人员，在不脱离本发明所公开的精神和范围的前提下，可以在实施的形式上及细节上作任何的修改与变化，但本发明的专利保护范围，仍须以所附的权利要求书所界定的范围为准。