软件定义网络(SDN,Software-definned Networking)是一种新型的网络架构模型,其核心思想是将控制层和数据转发层分离。控制层中的控制器集中式管理数据转发层网络,可以获得全网的拓扑信息。根据全网的拓扑信息,控制器可以提供链路的负载均衡、路径优化、流量分发等应用功能。当网络规模较小时,一个控制器可以集中式管理全网,控制器获取全网拓扑信息简单直接。但当网络规模较大时,依靠单一控制器已无法满足管理全网的需求,多控制器共同管理全网的方式随之出现。使用多控制器管理全网,每个控制器只集中管理全网的一个子网,即每个控制器只收集它负责管理的子网的信息,并对这个子网的资源性能分配。控制器彼此之间交换自身控制的子网中的网络拓扑信息,以此来获得全网完整的拓扑信息,并在此基础上做出决策。然而,如果其中某个控制器由于故障无法正确获得自身子网中网络拓扑信息,那么,其它控制器都无法从该控制器获得完整的全网拓扑信息,由此导致控制器上各种应用的决策失误。本论文提出了解决这个问题的两个方案,在这两个方案中,控制器独立探测网络中的链路状态,并能定位网络中出现的链路故障的方案。论文的贡献如下：(1)针对已有方案定位多控制器SDN中多链路故障能力弱的问题,本文提出了基于遗传算法的多环生成算法,该算法可以生成多环覆盖网络中所有链路,通过这些多环定位网络中的多链路故障。算法同时对生成的多环的性能进行了优化,使得生成的多环包含的重复链路数尽量少。实验结果表明该方案在探测多链路故障的能力上比现有方案优越。(2)为了适应网络中出现链路增删的情形,本文提出了基于树分解定位多控制器SDN中链路故障的方案。首先,提出多度无损图分割算法将网络分割成多个独立子网,相较于传统的图分割算法生成的子网,有如下特点：每个子图中的节点具有连通性并且节点的度大于等于2；生成的子图之间既有独立性又具有连通性。其次,提出了最大度-宽度优先树分解算法在子图中生成多环,该算法生成的多环的链路数目的均匀性和总时延较遗传算法生成的多环优越。实验表明,基于树分解定位多控制器SDN中链路故障的方案在需要下发的静态流表项、发送探测信息的个数等指标上比现有方案优越。