软件定义网络中集主控制器的推选方法

本发明涉及一种网络集主控制器推选方法，特别涉及一种软件定义网络中集主控制器的推选方法，属于主控制器推选技术领域。

随着网络技术的不断发展，传统网络出现了诸多问题，如网络配置复杂度高、路由表条数过多导致路由器变得臃肿不堪等问题，这些问题说明传统网络体系架构面临着革新，可编程网络为后期软件定义网络的产生提供了可以参考的依据。主动网络中，允许将用户程序放置到数据包中，并能让网络设备路由器自动执行转发过程，用户可以通过编程的方式动态的配置自己需要的网络形态，达到方便管控网络的目的。但由于主动网络有诸多缺点，如网络协议兼容性差，致使其并未在实际中得到部署，4D架构的出现将决策平面从数据平面中分离，使控制平面自动化和中心化，其设计思想便是软件定义网络出现的基础。

通过参考计算机系统的抽象结构，网络体系结构也可以抽象为转发抽象、状态抽象和配置抽象三部分。在转发抽象中，将传统路由器中的逻辑控制抽离出来，交由控制层管控，在控制平面与转发平面加以标准协议，确保数据包能在此网络结构中正确转发。控制层得到全网的拓扑图，便于通过全网拓扑对网络进行统一配置。配置抽象又能更近一层的简化网络模型，用户只需通过控制平面提供给应用层的接口便能对网络进行简单配置，完成对交换机的统一部署，因此网络结构抽象是软件定义网络产生的决定性因素。目前，在分布式环境中进行主结点的推选已经成为各个领域研究中必不可少的一部分，主结点作为分布式结构下的leader结点，掌控着整个网络中的状态信息，其功能主要有负载均衡的协调、网络决策仲裁、消息接收与下发和路由的查询等。主结点应该选择性能最优的结点，并且在其失效时能够推选出新的主结点继续服务，从而保证网络的可靠性。

软件定义网络体系架构的核心是将网络的控制平面与转发平面分离，通过对控制平面的软件编程管控整个网络，转发平面依旧运行于网络设备上，而分离出的控制平面交由控制器管控，控制器负责对软件定义网络进行逻辑控制。当软件定义网络的部署跨越多个区域时，采用分布式控制器集结构，避免单一控制器结点在扩展性和性能等方面的不足。为确保控制器集达到管控整个软件定义网络的目的，所考虑的第一个问题即是集中主控制器推选，主控制器维护整个集中其它控制器和交换机的状态信息，若主控制器出现失效，则需要从集剩余的控制器中选出新的主控制器，因此需要进行主控制器推选算法，来解决这一问题。现有技术缺少应用到软件定义网络中主控制推选的算法。

现有技术的软件定义网络的仍然有许多问题亟待解决：

第一，控制平面所面临的问题主要有流安装的可靠性和控制器的扩展性，控制器在和交换机通信进行流安装过程时，可能存在着数据包的丢失，网络联接的中断等情况，软件定义网络是一个集中化控制结构，这对软件定义网络的扩展带来了极大阻碍，影响网络规模的扩大，而且单一的集中化控制方式也在安全性和性能上有一定的风险，如果单一的控制器出现失效或者是临时断开，将会导致整个软件定义网络的瘫痪，。即使使用多控制器的结构来解决这一瓶颈，但多控制器中也面临着消息的一致性和扩展性的问题，而本发明的重点是控制平面中控制器的扩展性问题；

第二，转发平面面临的问题，软件定义网络转发平面主体是交换机，随着网络规模不断扩大，交换机中的流表项数目越来越多，流表字段的定义也在不断的变化，流表的结构也从开始的单级流表发展为后来的多级流表结构，给交换机的设计带来了很大的阻碍，现有技术的软交换机在性能上存在着很大的不足，即使是硬件交换机同样面临着性能上的问题，并且硬件交换机对OpenFlow技术的支持力度不够，而且由于交换机没有一个特定的标准，导致各个生产交换机厂商不能达成设备的一致性和兼容性；

第三，现有分布式推选方法的不足之处主要有以下三个：一是过程存在活锁问题，二是不能做到完全的分布式，三是算法时间复杂度和通信复杂度高，Lien最小生成树算法在最坏的情况下，(nd)的时间复杂度和(2p+nd/2－1)的通信复杂度都过高，影响算法的性能；Gallager最小生成树算法执行过程过于繁琐，致使其理解难度增大，算法的时间复杂度和通信复杂度也并不好。

第四，现有技术软件定义网络体系结构无法解决单一控制器在安全性、扩展性和性能方面的不足，缺少对控制器集的通信机制、数据缓存机制、数据一致性和事件通知进行设计实现的方法；缺少控制器性能值的计算方法，无法选出性能值最佳的结点充当主控制器结点，无法把推选结果传播下去，现有技术的主控制器推选方法执行频率高、推选过程中产生的消息类型多、未充分考虑容错处置，实现比较复杂，具有时间复杂度高和通信复杂度低等缺点。

本发明提供的软件定义网络中集主控制器的推选方法，提出了控制器集的机制架构和功能运行设计方法，软件定义网络体系结构采用控制器集的架构方式，对控制器集的通信机制、数据缓存机制、数据一致性和事件通知进行了设计和实现，解决单一控制器在安全性、扩展性和性能方面的不足；提出了一种控制器性能值的计算方法，该方法融合直接影响控制器性能的几个关键的指标，得出综合指标的一个评定函数，评定函数的值即为每个控制器的性能值大小；本发明提出软件定义网络中主控制器推选方法：由发现主控制器结点失效或者临时断开的结点即根结点发起推选命令，然后经由三个阶段的推选过程，根结点统计全网范围内的结点性能值，选出性能值最佳的结点充当主控制器结点，并把推选结果经由最小生成树传播下去，最后分析方法性能，最终得出本发明拥有执行频率低、推选过程中产生的消息类型少、充分考虑容错处置，实现比较简单、具有较低的时间复杂度和较高的通信复杂度等优点。

为达到以上技术效果，本发明所采用的技术方案如下：

软件定义网络中集主控制器的推选方法，首先提出了控制器集实现架构和功能设计方法，包括控制器集的通信机制、数据缓存机制、数据一致性和事件通知；其次，本发明提出影响控制器性能的几个关键指标，通过对指标的分析检测，提出一种控制器性能值的计算方法；最后，本发明基于最小生成树的构造思想，提出一种控制器集的软件定义网络架构中主控制器推选方法，并分析研判算法设计时边的容错处置、主控制器失效再推选和算法执行的时间复杂度与通信复杂度问题；本发明具体包括：

第一，控制器集设计，一方面，控制器通过软件定义网络的南向接口向转发设备发送流表和网络管控；另一方面，控制器给上层应用程序提供若干北向接口，应用程序通过这些标准接口对底层网络进行配置和高效的资源调度，本发明主要采用控制器集方式，控制器集设计包括控制器集的通信机制、数据缓存机制、通过分布式的协作关系确保全网状态的一致性设计和事件通知设计；

第二，控制器性能值计算方法，提出一种控制器性能值的计算方法，本发明控制器的性能指标包括控制器运算性能、控制器存储性能、控制器下发流表的带宽性能：控制器运算性能是控制器在收到交换机通过OpenFlow协议通道传送来的数据包信息时，具有快速查该数据包转发路径的能力；控制器存储性能是控制器所能存储的流表和全网拓扑结构视图资源的性能；控制器带宽性能是控制器将已查到的流表项转发给交换机的速度，控制器的带宽、控制器与交换机之间的通信信道的带宽较高时，控制器接收和下发流表的速度越快，软件定义网络的性能越高；

第三，主控制器推选方法，设计主控制器推选方法时，整个分布式网络分成多个集，每个集域中采用集中式控制，由主控制器集中控制该集，在控制器集模式下，所有控制器将消息传送到主控制器汇总，主控制器对集中的其它控制器和交换机进行维护，主控制器推选方法是自适应过程，两种场景会执行主控制器推选方法：一是整个基于控制器集的软件定义网络初始化时，由集中的任一结点发起主控制器推选方法，在控制器集内部选出最优控制器作为集主控制器；二是网络运行过程中，集的剩余控制器周期性的监控主控制器的工作状态，一旦发现访问不可达，则立即启动推选方法，从集剩余的控制器中选出新的主控制器，接管已出现故障的主控制器的工作，网络运行过程中主控制器保存的数据信息周期性存储，以便主控制器失效后仍能获取主控制器失效前状态信息；根据计算得到的集中所有控制器的性能值信息，本发明提出的主控制推选方法：基于最小生成树构造思想，分析检测获取的每个控制器的性能指标，得到每个控制器的最终性能值，推选出的主控制器即是性能值最佳的控制器。

软件定义网络中集主控制器的推选方法，进一步的，集通信机制：控制器集中的通信使用Jgroups通信机制，在搭建控制器集架构时，首先在集中选出一个主控制器结点，当有新的结点需要加入集时，主控制器可发现该结点并告知新加入的结点应该和集中的哪些控制器相连，其中GossipRouter在集中所有结点启动前运行，集中的每个控制器都和GossipRouter建立TCP联接，当集中的所有控制器都启动后，构建拥有N个结点的控制器集，此时Jgroups负责控制器之间的通信，并且对集中的控制器结点进行维护，对控制器的维护采用心跳失效检测机制，该机制检测每一个控制器结点信息，若发现发出的心跳消息超出设置的最大时间，则通过多次尝试与其进行通信，当尝试次数超过设置的某一个最大值时，仍没有收到其返回消息，则说明该结点处于失效状态，然后通知集中其它结点该失效的控制器信息，控制器集中若有结点临时离开该集，也通过心跳失效检测机制来实现，达到控制器集中信息的同步；采用TCP作为底层传输协议，集中结点的发现使用UDP多播的方式；

数据缓存机制：控制器集中同步信息包括集的拓扑信息和每个控制器的状态信息，这些信息的存储采用分布式缓存机制infinispan，在分布式环境中，将多个infinispan组成一个集，向外提供一个大容量的堆内存，infinispan为每个结点分配副本，任意一个结点信息在集的其它结点中存在着备份，在设计控制器集时采用封装Jgroups协议的infinispan数据缓存结构；infinispan在集环境下使用时，能够实现集间同步通信，即当有缓存需要存入集中的某个结点时，同时将该缓存内容添加到集中的其它所有结点内，确保访问每一个结点时都能够读取到当前集的全部同步信息；在对缓存内容进行同步复制的过程中，即数据修改操作时，禁止对其内容进行读取，直至集中所有结点上数据的写入完成，并返回修改完成的消息为止，保证数据的读写一致性。

软件定义网络中集主控制器的推选方法，进一步的，事件通知：集中产生事件通知的情形主要有控制器自身的状态改变，控制器与转发设备之间的联接改变以及缓存改变，联接改变事件包括：一是控制器结点离开集或者有新的结点加入集以及某个控制器结点失效导致的联接变化，二是控制器与转发设备之间或者是转发设备相互之间的联接发生改变，三是控制器向集中的其它控制器发送自身状态发生改变的事件；缓存改变事件的实现采用infinispan，它向外提供了接口，客户端使用该接口获取事件发生改变的消息，集中若发生控制器与转发设备断开联接、集中添加新的控制器以及转发设备间链路变更情形，导致缓存表项的新建、删除和变更，对于这些事件的发生，集快速获取，同时将变更后的缓存同步到集的所有控制器中；

对于事件通知的设计，在控制器中使用集服务提供同步事件的接口，联接管控模块收到监听得到的集视图改变事件或缓存改变事件后，调用事件处置模块，事件处置模块调用联接服务模块，最终完成事件的同步工作，在控制器集中实现数据的一致性和事件的同步处理，方便应用程序通过北向接口对控制器进行开放式编程，也方便底层转发设备通过南向接口对控制器进行访问。

软件定义网络中集主控制器的推选方法，进一步的，本发明控制器性能指标主要有三个：cpu大小、存储大小和带宽大小，软件定义网络中主控制器推选方法执行时，总是推选控制器性能最佳的控制器作为主控制器，控制器性能值采用控制器的三个性能指标综合而成，假设控制器的硬件性能指标都已知，控制器的性能值采用正则化和加权法的形式进行评估，j代表的性能指标分别为控制器的cpu、存储和带宽，Fj表示控制器性能指标j对应的实际值，分别是所有控制器中性能指标j的实际值中最大值和最小值，vj是Fj的正则化值，其计算式为：

权重是各性能指标所占的比重，由指标特征决定，若有k个性能指标，则且sj∈[0,1]，控制器的整体性能值计算式为：

在本发明中有三个性能指标，所以k＝3，主控制器推选时，推选性能值Q最大的控制器作为主控制器。

软件定义网络中集主控制器的推选方法，进一步的，基于本发明的控制器性能值计算方法，在推选过程中假定：每个控制器在参与主控制推选时已经计算出自己的性能值，这个计算过程在推选方法执行前进行；

控制器集采用图论的方式，软件定义网络中的控制器被缩成一个无向图的结点形式，当无向图中的某个结点监测到主控制器结点失效或临时断开后，该结点将启动主控制器推选方法，算法基于最小生成树的思想设计，主控制器推选方法由三个阶段构建：第1阶段是使用洪泛的方法在无向连通图中构造一棵生成树，同时产生最小生成树的分支结构；第2阶段从生成树的叶子结点开始返回消息，直至消息转发到根结点为止，消息内容包括每个结点的性能值、最小生成树的树边消息和无向图中的非树边消息，根结点将得到的每个结点的性能值排序，选出性能值最佳的结点，该结点即是所求的主控制器结点；根结点再根据得到的树边信息和非树边信息，将最小生成树的分支结构使用非树边联接成一颗最小生成树；第3阶段从根结点开始沿着最小生成树的路径发送推选结果。

软件定义网络中集主控制器的推选方法，进一步的，算法第1阶段从无向图中指定的某个结点作为根结点开始，根结点向自己的所有邻接结点发送推选命令，并且出邻接边中权重最小的边，对其进行标记，标记信号用EdgeTree表示，代表该边属于最小生成树的边，无向图中的结点收到推选命令后，将发送方当作自己的父结点进行标记，并给父结点返回一个ahead消息，然后将自己作为新的父结点，向自己的子结点发送推选消息，并在消息的发送和返回中将最小权重边加以EdgeTree标记；如果某个结点收到该结点的邻接结点发来的推选消息，但是其已经有了父结点，该结点就不会向其邻接结点再次返回ahead消息，每个结点结点都只能有一个直接的父结点；无向图中的结点在收到推选消息或返回父结点消息过程中，如果该消息中包含有EdgeTree的标记信号，则记录下该边属于最小生成树的边；

经过第1阶段发送消息的过程，无向连通图中的每个结点都确定了自己的父结点和子结点消息，父结点是发送推选命令的结点，子结点是向自己回复ahead消息的结点，每个结点的子结点有一个或者多个，甚至没有子结点，即是叶子结点，无向连通图中的全部结点通过这种父结点和子结点的关系建立了一个生成树，同时得到了最小生成树的一些分支。

软件定义网络中集主控制器的推选方法，进一步的，算法执行的第2阶段从无向连通图中的叶子结点开始返回消息，叶子结点定义为：在算法第1阶段执行过程中，除父结点之外，若是有结点没有收到任何从其子结点返回的ahead消息，则判断该结点是叶子结点，于是从该结点开始，逐步向根结点发送消息，发送的消息包含三个内容：一是所有结点的性能值信息和结点的IP地址信息；二是结点的属于最小生成树的边；三是结点不属于最小生成树的最小权重边，也即非树边；

无向连通图中除根结点和叶子结点外的其它结点，当其收到子结点返回过来的消息后，对消息内容进行整理，并向自己的父结点发送，消息整理主要有三个步骤：

步骤一，比较子结点和自己的性能值大小，选择性能值大的结点和该结点的IP地址上传给自己的父结点；

步骤二，整合子结点和自己的树边信息，将整合后的消息发送给自己的父结点，整合的规则定义为：若是两个树边拥有同一个结点，则将这两个树边放在一个集合内，若某条树边与一个集合有共同的结点，则将该树边合并到该集合中，若某条树边的两个结点分别在两个集合中，则把该树边加入到这两个集合，并把两个集合合并为一个大的集合，树边的集合就是最小生成树的一个连通分支；

步骤三，把子结点和自己的最小权重非树边进行整合操作，删除重复的非树边，再把整合后的结果发送给自己的父结点；

根据从叶子结点逐步返回的消息，根结点获取无向连通图中的所有的树边和非树边的信息、每个结点的性能值信息和结点的IP地址信息，然后进行以下两个步骤：

步骤1，根结点综合所有的结点性能值，出性能值最大的结点，该结点就是多控制器的软件定义网络中的主控制器结点；

步骤2，将不连通的最小生成树的分支联接起来，具体操作是从返回的非树边的信息中，选择最小权重的非树边，分析该非树边的两个结点是否属于两个分支，若是，则将这条非树边转化为树边，将两个连通分支合并为最小生成树的一个分支；若否，则删除此非树边，使用次小权重的非树边，做同样的处理，重复该过程，直至最后所有的连通分支被联接起来，形成一棵最小生成树；若无向连通图中有n个最小生成树的分支，则需要n-1条非树边，将其转换为树边。

软件定义网络中集主控制器的推选方法，进一步的，算法执行第3阶段：根结点沿着最小生成树的路径发送推选结果，消息中包括推选的结果和在第2阶段选出的联接几个生成树分支的新增加的树边，消息中树边使用的结点对的形式表示，无向图中收到消息的结点，分析消息中的内容判断自己的相邻边中是否含有最小生成树的边，若存在树边，则继续沿着树边结点继续转发消息，不断的重复此过程，直到消息到达最小生成树的叶子结点为止。

软件定义网络中集主控制器的推选方法，进一步的，容错处置：在设计主控制器推选方法时要考虑对边的错误处置问题，软件定义网络中主控制器推选方法设计有3个阶段，因此边发生故障的情形就有可能在任意阶段内产生，分三种情形考虑边出现的问题：

情形一，无向连通图中的边在推选时的第1阶段可能会出现故障状况的情形有四种：

第一种，发生故障的边在最小生成树中，解决方法是该边属于最小生成树，该边一定是无向连通图中某个结点的最小的权重边，此刻该结点将故障边删除，同时向与其相邻的次小权重边的联接结点发送带有标记的空的消息，然后收到该消息的结点记录下树边信息，而发生故障的树边的另一端的结点只要把该故障树边的信息删除即可；

第二种，发生故障的树边在生产树中，而不属于最小生成树，故障边属于生成树，解决方法是生成树中的父结点首先到该边的子结点，然后子结点到其相邻的最小权重边，然后子结点向到的最小权重边的另一端结点发送ahead消息，让接收ahead消息的结点与父结点产生新的父子关系，而之前的子结点信息只要删除即可；

第三种，如果发生故障的边既属于生成树中，同时又从属于最小生成树，解决方法是同时执行第一种、第二种中的操作即可；

第四种，如果发生故障的边既不在最小生成树中，同时又不在生成树中，解决方法最简单，只要把该边对应的两个结点上有关该边的信息删除即可，对后期的推选过程不会产生任何的影响；

情形二，无向连通图中的边在推选过程中的第二阶段可能会出现故障的情形也有四种：

第1种，发生故障的边在生成树中，解决方法是：这个阶段故障的边联接着父结点和它的子结点，子结点把自己的信息重新整理，然后子结点向除故障边之外的其它的邻接的最小权重边发送消息，之后该子结点的信息被删除，不去理会发生故障的边的任何消息；

第2种，如果发送故障的边在最小生成树中，解决方案是该故障的边的两端的结点分别重新整顿自己的信息，然后各自向自己的父结点汇报自己的情况；

第3种，如果发生故障的边既属于生成树中，同时又从属于最小生成树，解决方法是同时执行第1种和第2种中的操作即可；

第4种，如果发送故障的边既不在生成树中，又不在最小生成树中，解决办法同第2种一样，各自整理自己的消息，并向其父结点发送消息汇报；

情形三，无向连通图中的边在推选的第3阶段可能会出现故障的情形有两种：

第一，由于推选的最后一阶段只是进行推选结果的广播，所以如果发送故障的边不属于最小生成树，则不会对消息的广播产生影响，因此该故障边不处理即可；

第二，如果发送故障的边在最小生成树中，并且该故障边的父结点没有其它的子结点，则把故障信息沿着父结点的方向传递下去，告知无向连通图中的其它结点，此时借助非树边来传递信息；如果该故障边的父结点除了故障边一端的子结点外还有其它一些子结点，则把故障边的结点消息同时沿着父结点和子结点的方向同时传递，告知其它的结点发送故障的情况，传递消息时通过非数边进行推选结果的发送。

软件定义网络中集主控制器的推选方法，进一步的，主控制器失效再推选：通过最小生成树完成一次推选过程后，根结点获取到所有的控制器结点的性能值信息，根结点将所有控制器结点的性能值排序，选出性能值最强的前N个控制器结点，然后将排序后的结果通过最小生成树的路径下发出去，告知其它所有结点，其中性能值最大的控制器结点默认被推举为主控制器结点；若主控制器结点失效或者是临时断开，不进行二次推选，直接从排序好的控制器结点中选出性能值第二高的结点作为新的主控制器结点，如果第二高的主控制器再失效或者临时断开，选择第三高的性能值的控制器作为新的主控制器结点，依次类推，直至所有的前N个结点全部失效或者是临时断开，再重新开始新一轮的推选过程，重新选出主控制器。

与现有技术相比，本发明的贡献和创新点在于：

第一，本发明提供的软件定义网络中集主控制器的推选方法，提出了一种控制器集实现架构和功能设计方法，由于控制器对网络行为的集中化控制，使得控制器必须拥有极高的性能和可靠性，不能因为自身性能差、可靠性低而成为网络运行的阻碍，而且伴随着网络范围的逐步扩大，单一的控制器结构已不能支持庞大的网络拓扑结构，软件定义网络在控制平面的扩展是最好的解决途径，因此产生了基于控制器集和分域方式的多控制器的软件定义网络结构，本发明使用多个控制器的方式使软件定义网络在扩展性和性能上得到极大的提升，使用控制器集技术对软件定义网络的控制平面进行扩展，可以解决单一控制器结构带来的可靠性、安全性和性能方面的缺陷和不足；

第二，本发明提供的软件定义网络中集主控制器的推选方法，提出了一种新的控制器性能值计算方法，控制器性能值的高低直接影响控制器的性能，而控制器性能直接影响软件定义网络的整体运行效率，影响控制器性能的指标包括：控制器计算性能、存储性能、带宽性能、稳定性、控制器部署位置和控制器集中的结点联接度，本发明的控制器性能指标主要包括计算性能、存储性能和通信性能。通过综合分析每个指标的值，使用正则化和加权形式计算每个控制器的性能值，该方法中得到的控制器性能值是选出主控制器的依据，主控制器的推选方法科学合理、简便巧妙，在实际应用中有很高的利用价值；

第三，本发明提供的软件定义网络中集主控制器的推选方法，基于最小生成树的构造思路，提出了一种新的分布式网络中主结点推选方法，即软件定义网络中主控制器推选方法；与现有技术相比，本发明的推选方法具有消息类型少、算法执行过程简易等优点，而且考虑到了容错处置，算法鲁棒性好，在完成一次主控制器推选过程后，将一次得到的数据多次利用，减少后期推选方法执行频率，降低了系统负载，在通信复杂度上优于现有技术，而且其还具有更优的时间复杂度，让推选方法的执行在更短的时间内完成，大幅提高系统的执行效率。

第四，本发明提供的软件定义网络中集主控制器的推选方法，提出了控制器集的机制架构和功能运行设计方法，软件定义网络体系结构采用控制器集的架构方式，解决单一控制器在安全性、扩展性和性能方面的不足，本发明对控制器集的通信机制、数据缓存机制、数据一致性和事件通知进行了设计和实现；提出了一种控制器性能值的计算方法，该方法融合直接影响控制器性能的几个关键的指标，得出综合指标的一个评定函数，评定函数的值即为每个控制器的性能值大小；在参考最小生成树的构造过程后，本发明提出软件定义网络中主控制器推选方法：由发现主控制器结点失效或者临时断开的结点即根结点发起推选命令，然后经由三个阶段的推选过程，根结点统计全网范围内的结点性能值，选出性能值最佳的结点充当主控制器结点，并把推选结果经由最小生成树传播下去，最后分析方法性能，最终得出本发明拥有执行频率低、推选过程中产生的消息类型少、充分考虑容错处置，实现比较简单、具有较低的时间复杂度和较高的通信复杂度等优点。

图1是本发明的事件通知流程示意图。

图2是本发明推选方法第1阶段执行的流程示意图。

图3是本发明推选方法第2阶段执行的流程示意图。

图4是本发明推选方法第3阶段执行的流程示意图。

下面结合附图，对本发明提供的软件定义网络中集主控制器的推选方法的技术方案进行进一步的描述，使本领域的技术人员可以更好的理解本发明并能予以实施。

软件定义网络是新型网络体系架构，其控制与转发分离架构很好的解决了传统网络中路由器的路由表过度臃肿的问题，但软件定义网络中控制逻辑的集中化，使得软件定义网络的性能受到严重制约，采用控制器集对控制平面进行扩展能有效解决。控制器集设计的关键是主控制器的推选，主控制器管控集所有控制器和交换机的网络状态信息。

本发明首先提出了控制器集实现架构和功能设计方法，包括控制器集的通信机制、数据缓存机制、数据一致性和事件通知；其次，本发明提出影响控制器性能的几个关键指标，通过对指标的分析检测，提出了一种控制器性能值的计算方法；最后，本发明基于最小生成树的构造思想，提出了一种控制器集的软件定义网络架构中主控制器推选方法，并分析研判算法设计时边的容错处置、主控制器失效再推选和算法执行的时间复杂度与通信复杂度问题。本发明具体包括：

第一，控制器集设计，控制器是软件定义网络的核心，是联接下层的网络基础设施和上层应用程序的关键桥梁，一方面，控制器通过软件定义网络的南向接口向转发设备发送流表和网络管控；另一方面，控制器给上层应用程序提供若干北向接口，应用程序通过这些标准接口对底层网络进行配置和高效的资源调度，实现对网络的灵活管控和操控。

控制器负责全网的集中控制，拥有全网的拓扑结构图，通过网络配置使其具有改善全网资源交付的性能，由于控制器对网络行为的集中化控制，使得控制器必须拥有极高的性能和可靠性，不能因为自身性能差、可靠性低而成为网络运行的阻碍，而且伴随着网络范围的逐步扩大，单一的控制器结构已不能支持庞大的网络拓扑结构，软件定义网络在控制平面的扩展是最好的解决途径，因此产生了基于控制器集和分域方式的多控制器的软件定义网络结构，这种使用多个控制器的方式使软件定义网络在扩展性和性能上得到极大的提升，本发明主要采用控制器集方式，控制器集设计包括控制器集的通信机制、数据缓存机制、通过分布式的协作关系确保全网状态的一致性设计和事件通知设计。

第二，控制器性能值计算方法，控制器管控全网的网络状态和资源配置，对控制器的性能有很高的要求，本发明通过分析检测各种指标，提出一种控制器性能值的计算方法，本发明控制器的性能指标包括控制器运算性能、控制器存储性能、控制器下发流表的带宽性能：

控制器运算性能是控制器在收到交换机通过OpenFlow协议通道传送来的数据包信息时，具有快速查该数据包转发路径的能力，控制器的运算性能越强，查流表的速度越快，数据包的整个交付过程越迅速；

控制器存储性能是控制器所能存储的流表和全网拓扑结构视图资源的性能，一个控制器能管控的网络设备资源越多，其所覆盖的范围就越广，但过多的流表信息，会造成查流表时间延迟；

控制器带宽性能是控制器将已查到的流表项转发给交换机的速度，控制器的带宽、控制器与交换机之间的通信信道的带宽较高时，控制器接收和下发流表的速度就越快，软件定义网络的性能就越高。

第三，主控制器推选方法，控制器集结构能拓宽网络的覆盖范围，增加网络的健壮性和可靠性，为保证控制器集架构下的软件定义网络对整个集的控制效果，首要任务是在集中进行主控制器推选，主控制器负责监控整个集的其它控制器和交换机的信息，负责全网的配置任务，因此主控制器的选择要综合多方面因素；

设计主控制器推选方法时，整个分布式网络分成多个集，每个集域中采用集中式控制，由主控制器集中控制该集，在控制器集模式下，所有控制器将消息传送到主控制器汇总，主控制器对集中的其它控制器和交换机进行维护，主控制器推选方法是自适应过程。两种场景会执行主控制器推选方法：一是整个基于控制器集的软件定义网络初始化时，由集中的任一结点发起主控制器推选方法，在控制器集内部选出最优控制器作为集主控制器；二是网络运行过程中，集的剩余控制器周期性的监控主控制器的工作状态，一旦发现访问不可达，则立即启动推选方法，从集剩余的控制器中选出新的主控制器，接管已出现故障的主控制器的工作，网络运行过程中主控制器保存的数据信息周期性存储，以便主控制器失效后仍能获取主控制器失效前状态信息；

根据计算得到的集中所有控制器的性能值信息，本发明提出的主控制推选方法：基于最小生成树构造思想，分析检测获取的每个控制器的性能指标，得到每个控制器的最终性能值，推选出的主控制器即是性能值最佳的控制器。

一、问题定义与描述

本发明解决的问题包括以下三个：

(一)控制器集架构设计

在软件定义网络中控制器的作用至关重要，而单一控制器面临诸多问题，如可靠性上容易失效，安全性上容易信息泄露，性能上容易受自身性能指标影响等。其解决方案采用基于控制器集的软件定义网络架构，使用多控制器结构，不仅解决了单一控制器在安全性、可靠性和性能上的不足，而且能应对跨多个地域的软件定义网络问题。

控制器集设计时，每个控制器之间的相互协作非常重要，因此要设计控制器之间的通信机制和同步信息存储的数据缓存机制，采用Jgroups实现控制器之间的通信，采用infinispan技术实现信息存储；控制器集设计时的分布式系统中一致性问题，通过集的通信机制和数据缓存机制，保证数据一致性和事件一致性。

(二)控制器性能值计算方法

控制器性能值的高低直接影响控制器的性能，而控制器性能直接影响软件定义网络的整体运行效率，影响控制器性能的指标包括：控制器计算性能、存储性能、带宽性能、稳定性、控制器部署位置和控制器集中的结点联接度，本发明的控制器性能指标主要包括计算性能、存储性能和通信性能。通过综合分析每个指标的值，使用正则化和加权形式计算每个控制器的性能值。

(三)主控制器推选方法

基于控制器集的软件定义网络架构中，一个主控制器和一组普通的控制器构建整个集的控制器，主控制器对普通控制器和全网的交换机进行监控，如果在软件定义网络运行过程中，主控制器失效或是临时断开，控制器集自组织的推选出性能值最佳的控制器作为新的主控制器，方法是构造一棵生成树来遍历所有的控制器，推选出性能值最大的控制器，每个控制器的性能值定义为：通过分析控制器集的性能指标，分析综合每个控制器的性能值，得到一个所有指标的综合评定函数，评定函数值即是每个控制器的性能值。

二、具体定义与说明

控制器结点：软件定义网络中将集中的一个控制器量化成一个结点，整个集的控制器集合用一个无向连通图表示，图中的结点即为控制器结点，无向连通图表示为t＝(u，b，value)，其中u是控制器结点的集合，|u|＝m；b是无向连通图中边的集合，|b|＝q；value表示每个边的权重大小，这里的权重表示消息在每条边上传递所用的时间，分别用m、q和h代表系统中节点的数量、边的数目和遍历一次全网节点的时间大小，假设每条边上的时间已知，这个时间通过特定的测量技术获取，为了唯一的标识每个控制器结点，结点的主键用IP地址表示；假设每个控制器结点都知道与自己相邻的控制器结点联接边的权重大小和IP地址，控制器结点之间的通信通过消息传递实现，消息在边的两个结点之间传送，并且按顺序到达。

主控制器推选方法采用生成树，包括树结构中的几个概念，分别是根结点、父结点、子结点和叶子结点。

三、控制器集设计

(一)控制器集设计要素

软件定义网络中参考服务器集技术使用软件来部署软件定义网络控制器集，考虑控制器之间的通信，系统中为完成控制器之间的消息传递，采用专门的集通信机制，采用Jgroups通信库来实现。

为确保控制器集达到对软件定义网络的有效管控，在设计软件定义网络架构时，有两点十分重要：一是在控制器集中进行主控制器的推选，集中的主控制器主要管控整个软件定义网络中所有设备状态信息，主控制器一旦出现故障，需要从集的其它剩余控制器中选出一个成为新的主控制器；二是控制器集对转发设备的不可见，即在软件定义网络的运行时，交换机不需要知道当前它接受的命令是从何控制器传来的，同时交换机在向控制器发送没有到流表的数据包时，能够保持譬如单一控制器的操作过程，对外把控制器集当作逻辑上的一台控制器，保证控制器在逻辑上集中；控制器集具体包括以下要素：

要素一，主控制器推选，首要任务是考虑主控制器的推选，集中剩余的控制器需要周期性的向主控制器发送监控信号，监听主控制器的当前状态，一旦发现主控制器不能返回应答消息，启动主控制器的推选，本发明提出了一种在控制器集下的主控制器推选方法，考虑算法实现的复杂度。

要素二，扩展性和可用性，控制器良好的扩展性是控制器能根据系统的需求适当增加控制器数量，满足性能的需求，若控制器负载过高，当前控制器集不足以应对过多的网络转发设备，此时能通过加入额外的控制器来解决该问题，从而使控制器集的性能不会降低；同时，若网络负载降低时，为防止资源的浪费，将过多的控制器撤离集中，达到在性能不会降低的同时保持资源的合理使用，由于控制器是使用软件设计的，因此考虑控制器的几个软件化的特征需求，具体是功能上的升级和软件的移植，控制器的软件技术变化后系统能够对其进行适应，在不同的平台上进行应用的切换。

控制器高可用性是控制器在各种不良因素的影响下，也能够不受影响的正常运行，高可用性主要有三个方面：一是在系统运行过程中，若某个控制器出现失效或者临时断开，能立刻出现新的控制器接管该控制器的工作，该控制器能获取到失效控制器失效前的状态信息；二是当转发设备之间的通信链路出现故障或者是控制器与转发设备之间的链路出现故障时，能快速恢复到故障前的状态；三是若系统中的故障让控制器集发生分支，能快速的恢复故障，若故障难度较高，也要保障分支的各个小的控制器集能正常工作，管控好自己集内的转发设备的工作。

要素三，控制器集的访问控制，应用程序通过北向接口，提出对控制器的访问控制，达到对下层转发设备进行资源调度的目的。因此设计控制器集既要考虑上层应用对控制器的访问控制，又要考虑下层的转发设备对控制器集的访问控制，软件定义网络的控制平面中对上层的网络应用，提供统一的API，应用程序根据控制器的请求与集中的控制器建立联接，若一个应用程序被安置到控制器中，当实行控制器集的结构时，所有的控制器都必须实现该应用程序，并且要做到在应用程序间的信息同步。

要素四，集虚拟地址，在控制器集架构中考虑负载均衡，尽量让每个控制器能管控数目大致相同的交换机，让交换机将其信息发送给某个虚拟IP地址，控制器再根据当前的负载情况，通过控制器之间的通信到该虚拟IP地址所属的控制器并保存，告知该控制器负责对此交换机的管控，控制器返回给交换机的数据包的源目的地址也将使用控制器的虚拟IP地址，达到控制器集相对于交换机的不可见的目的。

要素五，获取全网拓扑，全局拓扑信息是进行网络资源调度的前提，为获取全网范围内控制器和交换机的状态信息，集中所有控制器周期性的进行链路发现，并将收集到的网络状态信息发送给主控制器，主控制器进行整理后，再统一下发给集中的其它控制器，若控制器在转发数据流时，发现所要发送的数据流涉及的转发设备超过其对交换机的控制范围时，该控制器通过控制器间的通信通知交换机所属的控制器，统一下发给交换机。

要素六，控制器失效应对，若出现主副控制器失效的情形，控制器集采用负载均衡技术解决，具体执行的步骤是首先获取失效的控制器的虚拟IP地址，然后在集中出与失效控制器性能和位置最接近的，或者是该时刻最闲的控制器，将失效控制器的虚拟IP地址赋给得到的新的控制器，新产生的控制器接管失效控制器的所有工作，同时触发一次全网拓扑信息的更新，最后由主控制器获取更新后的全网拓扑。

软件定义网络使用控制器集的架构方式，不仅有效解决单一控制器带来的单点故障问题，同时在应对网络中的巨大流量也有很好的扩展性，控制器集解决了软件定义网络的控制平面在东西向扩展方面的问题。

(二)控制器集架构设计

使用多个控制器构建一个控制器集，集内部是多控制器形式，而对外则在逻辑上可以当成一个控制器，基于本发明提出的控制器集设计要素，从控制器集的机制架构和功能运行两个方面进行设计。

1.机制架构

设计控制器集各结点之间的相互协作非常重要，因此在实现控制器集的架构时，考虑控制器结点之间用于信息同步的集通信机制和用于数据信息存储的缓存机制。

(1)集通信机制

控制器集中的通信使用Jgroups通信机制，在搭建控制器集架构时，首先在集中选出一个主控制器结点，当有新的结点需要加入集时，主控制器可发现该结点并告知新加入的结点应该和集中的哪些控制器相连。其中GossipRouter在集中所有结点启动前运行，集中的每个控制器都和GossipRouter建立TCP联接，当集中的所有控制器都启动后，构建拥有N个结点的控制器集，此时Jgroups负责控制器之间的通信，并且对集中的控制器结点进行维护，对控制器的维护采用心跳失效检测机制，该机制检测每一个控制器结点信息，若发现发出的心跳消息超出设置的最大时间，则通过多次尝试与其进行通信，当尝试次数超过设置的某一个最大值时，仍没有收到其返回消息，则说明该结点处于失效状态，然后通知集中其它结点该失效的控制器信息，控制器集中若有结点临时离开该集，也通过心跳失效检测机制来实现，达到控制器集中信息的同步。

为保证集中状态信息一致可靠性，Jgroups采用TCP作为底层传输协议，将控制器结点分布在更大规模的网络中，使软件定义网络部署在跨域的情形中，给软件定义网络的部署带来更好的扩展性，集中结点的发现使用UDP多播的方式。

(2)数据缓存机制

控制器集中同步信息包括集的拓扑信息和每个控制器的状态信息，这些信息的存储采用分布式缓存机制infinispan，在分布式环境中，将多个infinispan组成一个集，向外提供一个大容量的堆内存，infinispan为每个结点分配副本，任意一个结点信息在集的其它结点中存在着备份，提高infinispan数据网格的容错性能和扩展性，在设计控制器集时采用封装Jgroups协议的infinispan数据缓存结构。

infinispan在集环境下使用时，能够实现集间同步通信，即当有缓存需要存入集中的某个结点时，同时将该缓存内容添加到集中的其它所有结点内，确保访问每一个结点时都能够读取到当前集的全部同步信息；在对缓存内容进行同步复制的过程中，即数据修改操作时，禁止对其内容进行读取，直至集中所有结点上数据的写入完成，并返回修改完成的消息为止，保证数据的读写一致性。

2.功能运行设计

本发明分别从数据一致性和事件一致性两方面进行详细的功能运行设计。

(1)数据一致性

为保障集的协同工作，要确保一些重要信息的一致性，基于控制器集的软件定义网络架构，为实现对整个网络的管控，以下几种信息必须做到信息的一致性：

第一，集拓扑信息，使用控制器集的方式，在集内部是多控制器的结构，而对于整个软件定义网络来说，该集逻辑上表现为一个控制器。因此当软件定义网络对该集中的任一一个结点访问时，要保证集中的每一个结点拥有该集相同的拓扑信息，拓扑的获取使用链路层发现协议来实现；

第二，物理设备信息，网络中的交换机的端口信息以及交换机是否访问可达信息；

第三，配置信息，包括控制器中的流表信息，交换机的端口性能信息以及一些冗余信息，这些冗余信息在结点失效时，让结点恢复到失效前的状态；

第四，控制器与交换机联接信息，每个控制器可联接多个交换机，同时每个交换机也可联接多个控制器，做到该联接信息的一致性，有助于链路失效时的恢复。

集运行过程中，可能出现链路失效的情形，整个集被失效的链路分为几个小的集，此时同样要保证结点状态的一致性和整个集的可用性，在该情形下，采用CAP定理分析，在一个分布式环境中，一致性、可用性和容忍网络分区这三个特征不能同时被达成，通过缓存同步复制机制满足一致性和可用性两项特征。

(2)事件通知

集中产生事件通知的情形主要有控制器自身的状态改变，控制器与转发设备之间的联接改变以及缓存改变，联接改变事件包括：一是控制器结点离开集或者有新的结点加入集以及某个控制器结点失效导致的联接变化，二是控制器与转发设备之间或者是转发设备相互之间的联接发生改变，三是控制器向集中的其它控制器发送自身状态发生改变的事件；缓存改变事件的实现采用infinispan，它向外提供了接口，客户端使用该接口获取事件发生改变的消息，集中若发生控制器与转发设备断开联接、集中添加新的控制器以及转发设备间链路变更情形，导致缓存表项的新建、删除和变更，对于这些事件的发生，集快速获取，同时将变更后的缓存同步到集的所有控制器中。

对于事件通知的设计，在控制器中使用集服务提供同步事件的接口，如图1所示。联接管控模块收到监听得到的集视图改变事件或缓存改变事件后，调用事件处置模块，事件处置模块调用联接服务模块，最终完成事件的同步工作。在控制器集中实现数据的一致性和事件的同步处理，方便应用程序通过北向接口对控制器进行开放式编程，也方便底层转发设备通过南向接口对控制器进行访问。

四、控制器性能值计算方法

本发明控制器的重要的性能指标包括：一是控制器的处理流表的性能，当软件定义网络交换机在自己的流表中查询路由失败时，将该数据包的信息发送给控制器，控制器根据数据包的头部信息，在控制器的流表中查询其相应的路径，控制器的cpu处理性能越强，获取路由信息就越迅速；二是全局拓扑和转发表信息需要的存储性能，控制器中的内存空间越大，能够存储的流表项越多，可促进查询流表的速度，加快数据包传递的速度；三是从网络设备接收流和将流表信息传送给网络设备的I/O性能，控制器拥有的带宽越大，发送相同数据所需要的时间越短，软件定义网络性能越好。

综上，本发明控制器性能指标主要有三个：cpu大小、存储大小和带宽大小。软件定义网络中主控制器推选方法执行时，总是推选控制器性能最佳的控制器作为主控制器，控制器性能值采用控制器的三个性能指标综合而成，假设控制器的硬件性能指标都已知，控制器的性能值采用正则化和加权法的形式进行评估，j代表的性能指标分别为控制器的cpu、存储和带宽，Fj表示控制器性能指标j对应的实际值，分别是所有控制器中性能指标j的实际值中最大值和最小值，vj是Fj的正则化值，其计算式为：

权重是各性能指标所占的比重，由指标特征决定，若有k个性能指标，则且sj∈[0,1]，控制器的整体性能值计算式为：

在本发明中有三个性能指标，所以k＝3，主控制器推选时，推选性能值Q最大的控制器作为主控制器。

五、主控制器推选方法

基于本发明的控制器性能值计算方法，在推选过程中假定：每个控制器在参与主控制推选时已经计算出自己的性能值，这个计算过程在推选方法执行前进行。

本发明提出一种基于控制器集的软件定义网络中主控制器推选方法，与现有技术相比，本发明的推选方法具有消息类型少、算法执行过程简易等优点，而且考虑到了容错处置，算法鲁棒性好，在完成一次主控制器推选过程后，将一次得到的数据多次利用，减少后期推选方法执行频率，降低了系统负载，在通信复杂度上优于现有技术，而且其还具有更优的时间复杂度，让推选方法的执行在更短的时间内完成，大幅提高系统的执行效率。

(一)主控制器推选算法设计

控制器集采用图论的方式，软件定义网络中的控制器被缩成一个无向图的结点形式，当无向图中的某个结点监测到主控制器结点失效或临时断开后，该结点将启动主控制器推选方法，算法基于最小生成树的思想设计，主控制器推选方法由三个阶段构建：第1阶段是使用洪泛的方法在无向连通图中构造一棵生成树，同时产生最小生成树的分支结构；第2阶段从生成树的叶子结点开始返回消息，直至消息转发到根结点为止，消息内容包括每个结点的性能值、最小生成树的树边消息和无向图中的非树边消息，根结点将得到的每个结点的性能值排序，选出性能值最佳的结点，该结点即是所求的主控制器结点；根结点再根据得到的树边信息和非树边信息，将最小生成树的分支结构使用非树边联接成一颗最小生成树；第3阶段从根结点开始沿着最小生成树的路径发送推选结果。

1.算法执行第1阶段

算法第1阶段从无向图中指定的某个结点作为根结点开始，根结点向自己的所有邻接结点发送推选命令，并且出邻接边中权重最小的边，对其进行标记，标记信号用EdgeTree表示，代表该边属于最小生成树的边，无向图中的结点收到推选命令后，将发送方当作自己的父结点进行标记，并给父结点返回一个ahead消息，然后将自己作为新的父结点，向自己的子结点发送推选消息，并在消息的发送和返回中将最小权重边加以EdgeTree标记；如果某个结点收到该结点的邻接结点发来的推选消息，但是其已经有了父结点，该结点就不会向其邻接结点再次返回ahead消息，每个结点结点都只能有一个直接的父结点；无向图中的结点在收到推选消息或返回父结点消息过程中，如果该消息中包含有EdgeTree的标记信号，则记录下该边属于最小生成树的边。

经过第1阶段发送消息的过程，无向连通图中的每个结点都确定了自己的父结点和子结点消息，父结点是发送推选命令的结点，子结点是向自己回复ahead消息的结点，每个结点的子结点有一个或者多个，甚至没有子结点，即是叶子结点，无向连通图中的全部结点通过这种父结点和子结点的关系建立了一个生成树，同时得到了最小生成树的一些分支。算法第1阶段执行的流程图如图2所示。

2.算法执行第2阶段

算法执行的第2阶段从无向连通图中的叶子结点开始返回消息，叶子结点定义为：在算法第1阶段执行过程中，除父结点之外，若是有结点没有收到任何从其子结点返回的ahead消息，则判断该结点是叶子结点，于是从该结点开始，逐步向根结点发送消息，发送的消息包含三个内容：一是所有结点的性能值信息和结点的IP地址信息；二是结点的属于最小生成树的边；三是结点不属于最小生成树的最小权重边，也即非树边；

无向连通图中除根结点和叶子结点外的其它结点，当其收到子结点返回过来的消息后，对消息内容进行整理，并向自己的父结点发送，消息整理主要有三个步骤：

步骤一，比较子结点和自己的性能值大小，选择性能值大的结点和该结点的IP地址上传给自己的父结点；

步骤二，整合子结点和自己的树边信息，将整合后的消息发送给自己的父结点，整合的规则定义为：若是两个树边拥有同一个结点，则将这两个树边放在一个集合内，若某条树边与一个集合有共同的结点，则将该树边合并到该集合中，若某条树边的两个结点分别在两个集合中，则把该树边加入到这两个集合，并把两个集合合并为一个大的集合，树边的集合就是最小生成树的一个连通分支；

步骤三，把子结点和自己的最小权重非树边进行整合操作，删除重复的非树边，再把整合后的结果发送给自己的父结点。

根据从叶子结点逐步返回的消息，根结点获取无向连通图中的所有的树边和非树边的信息、每个结点的性能值信息和结点的IP地址信息，然后进行以下两个步骤：

步骤1，根结点综合所有的结点性能值，出性能值最大的结点，该结点就是多控制器的软件定义网络中的主控制器结点；

步骤2，将不连通的最小生成树的分支联接起来，具体操作是从返回的非树边的信息中，选择最小权重的非树边，分析该非树边的两个结点是否属于两个分支，若是，则将这条非树边转化为树边，将两个连通分支合并为最小生成树的一个分支；若否，则删除此非树边，使用次小权重的非树边，做同样的处理，重复该过程，直至最后所有的连通分支被联接起来，形成一棵最小生成树；若无向连通图中有n个最小生成树的分支，则需要n-1条非树边，将其转换为树边。算法第2阶段执行的流程图如图3所示。

3.算法执行第3阶段

根结点沿着最小生成树的路径发送推选结果，消息中包括推选的结果和在第2阶段选出的联接几个生成树分支的新增加的树边，消息中树边使用的结点对的形式表示，无向图中收到消息的结点，分析消息中的内容判断自己的相邻边中是否含有最小生成树的边，若存在树边，则继续沿着树边结点继续转发消息，不断的重复此过程，直到消息到达最小生成树的叶子结点为止。算法第3阶段执行的流程图如图4所示。

(二)容错处置

软件定义网络中主控制器的推选在分布式集中进行，控制器集之间的通信是通过消息传递的方式，在通信过程中可能存在消息丢失的状况，因此对应在无向连通图中是推选过程中在连通图的边上发生故障情况，在设计主控制器推选方法时要考虑对边的错误处置问题，软件定义网络中主控制器推选方法设计有3个阶段，因此边发生故障的情形就有可能在任意阶段内产生，分三种情形考虑边出现的问题：

情形一，无向连通图中的边在推选时的第1阶段可能会出现故障状况的情形有四种：

第一种，发生故障的边在最小生成树中，解决方法是该边属于最小生成树，该边一定是无向连通图中某个结点的最小的权重边，此刻该结点将故障边删除，同时向与其相邻的次小权重边的联接结点发送带有标记的空的消息，然后收到该消息的结点记录下树边信息，而发生故障的树边的另一端的结点只要把该故障树边的信息删除即可；

第二种，发生故障的树边在生产树中，而不属于最小生成树，故障边属于生成树，解决方法是生成树中的父结点首先到该边的子结点，然后子结点到其相邻的最小权重边，然后子结点向到的最小权重边的另一端结点发送ahead消息，让接收ahead消息的结点与父结点产生新的父子关系，而之前的子结点信息只要删除即可；

第三种，如果发生故障的边既属于生成树中，同时又从属于最小生成树，解决方法是同时执行第一种、第二种中的操作即可；

第四种，如果发生故障的边既不在最小生成树中，同时又不在生成树中，解决方法最简单，只要把该边对应的两个结点上有关该边的信息删除即可，对后期的推选过程不会产生任何的影响。

情形二，无向连通图中的边在推选过程中的第二阶段可能会出现故障的情形也有四种：

第1种，发生故障的边在生成树中，解决方法是：这个阶段故障的边联接着父结点和它的子结点，子结点把自己的信息重新整理，然后子结点向除故障边之外的其它的邻接的最小权重边发送消息，之后该子结点的信息被删除，不去理会发生故障的边的任何消息；

第2种，如果发送故障的边在最小生成树中，解决方案是该故障的边的两端的结点分别重新整顿自己的信息，然后各自向自己的父结点汇报自己的情况；

第3种，如果发生故障的边既属于生成树中，同时又从属于最小生成树，解决方法是同时执行第1种和第2种中的操作即可；

第4种，如果发送故障的边既不在生成树中，又不在最小生成树中，解决办法同第2种一样，各自整理自己的消息，并向其父结点发送消息汇报。

情形三，无向连通图中的边在推选的第3阶段可能会出现故障的情形有两种：

第一，由于推选的最后一阶段只是进行推选结果的广播，所以如果发送故障的边不属于最小生成树，则不会对消息的广播产生影响，因此该故障边不处理即可；

第二，如果发送故障的边在最小生成树中，并且该故障边的父结点没有其它的子结点，则把故障信息沿着父结点的方向传递下去，告知无向连通图中的其它结点，此时借助非树边来传递信息；如果该故障边的父结点除了故障边一端的子结点外还有其它一些子结点，则把故障边的结点消息同时沿着父结点和子结点的方向同时传递，告知其它的结点发送故障的情况，传递消息时通过非数边进行推选结果的发送。

(三)主控制器失效再推选

通过最小生成树完成一次推选过程后，根结点获取到所有的控制器结点的性能值信息，根结点将所有控制器结点的性能值排序，选出性能值最强的前N个控制器结点，然后将排序后的结果通过最小生成树的路径下发出去，告知其它所有结点，其中性能值最大的控制器结点默认被推举为主控制器结点；若主控制器结点失效或者是临时断开，不进行二次推选，直接从排序好的控制器结点中选出性能值第二高的结点作为新的主控制器结点，如果第二高的主控制器再失效或者临时断开，选择第三高的性能值的控制器作为新的主控制器结点，依次类推，直至所有的前N个结点全部失效或者是临时断开，再重新开始新一轮的推选过程，重新选出主控制器。

(四)主控制器推选方法性能分析

本发明从两方面分析软件定义网络中主控制器推选方法的性能，主要是消息复杂度和时间复杂度，主控制器推选方法在算法执行的第1阶段采用洪泛的方式发送消息，从根结点开始，假如每个结点都向其邻接的结点发送推选命令，因此每条边会传递两次推选消息，消息传递次数为2q，q为无向图中的边的数量，由于收到推选消息的结点向其子结点发送推选消息，而不会重复向自己的父结点发送推选消息，但每个结点会向其父结点返回ahead消息，因此推选消息被发送的次数为q，返回父结点的消息次数也为q，在第1阶段总的传递消息的次数为2q；在算法的第2阶段，叶子结点通过生成树的路径，逐步向根结点发送每个结点的性能值信息，便于根结点汇总，拥有m个结点的无向连通图有m-1条边，因此第2阶段传递消息的次数为m-1；在算法的第3阶段中，推选结果的消息沿着最小生成树的路径传送，无向连通图中有m个结点，最小生成树有m-1条边，因此第3阶段传递消息的次数同样为m-1次。算法在执行完三个阶段后总的消息传递次数为2q+2m-2，因此算法的通信性能为2q+2m-2，若无向连通图中遍历一次全部结点的时间用h表示，在主控制器推选方法中的三个阶段中，都会遍历一次网络结点，因此算法遍历结点的时间复杂度为3h。

对于基于控制器集的软件定义网络中主控制器推选方法，当集中的主控制器失效或临时断开时，集中的剩余控制器使用主控制器推选方法自组织的选出新的主控制器，这对软件定义网络可靠运行有重要意义。在参考最小生成树的构造过程后，本发明提出软件定义网络中主控制器推选方法：由发现主控制器结点失效或者临时断开的结点即根结点发起推选命令，然后经由三个阶段的推选过程，根结点统计全网范围内的结点性能值，选出性能值最佳的结点充当主控制器结点，并把推选结果经由最小生成树传播下去，最后分析方法性能，最终得出本发明拥有执行频率低、推选过程中产生的消息类型少、充分考虑容错处置，实现比较简单、具有较低的时间复杂度和较高的通信复杂度等优点。