随着互联网的快速发展,对网络的要求不断提高,随之而来的问题则是传统的网络架构已经无法满足现今技术要求。在此背景下,SDN被提出并飞速发展,现已取得卓越成果。将转发平面从数据平面分离是SDN的核心思想,数据平面仅负责报文转发,转发的决策由控制平面负责,很容易地实现了网络创新。在SDN之前的传统网络中,我们并不能完全知道整个网络的全局拓扑,这时,传统网络中的路由问题是一个瓶颈问题,路由器只能掌握网络中的一部分拓扑,那么整个网络的路由计算就是只能采取分布式算法。这样的话,整个网络的路由过程并不是完全可控的,或者需要付出很大的代价才能实现对路由过程的控制。那么SDN的诞生就为解决这个问题提供一个思路,在SDN中,存在一个中心控制器,该控制器可以获得下层网络的整个拓扑,并且可以做出控制报文的转发决策,这样,传统网络中路由过程不可控的问题在SDN中就可以得到解决。现在主流SDN控制器所采用的路由算法为Dijkstra算法,Dijkstra算法是一种最短路径算法,该算法只能算出源节点和目的节点之间的最短路径。但是当我们对于从源节点到目的节点之间的路径有一些限制条件时,例如要绕过出现故障可能性较大的节点时,Dijkstra算法所能计算出的最短路径可能就不符合我们的要求。因此,在路由计算的实际应用中,我们不仅要考虑最短路径,还需要考虑次短路径、次次短路径,这时,KSP(K最短路径)算法就可以满足上述限制条件的路由计算。KSP算法可以计算出按最优、次优、次次优等顺序排列的一些路径集合,集合的大小根据K值的大小确定,我们便可以从这些路径中选出符合限制条件的路径来。KSP算法在物流、序列比对、网络和文本处理等领域有着非常广泛的应用。因此,本文希望将KSP算法应用于SDN控制器中,可以实现对SDN路由器路由功能的扩展,以便满足更多的路由需求。本文针对KSP算法以及SDN控制器一Opendaylight进行研究,取得如下成果:对Dijkstra算法和KSP算法在生存性以及必经节点下的性能进行分析比较,分析结果表明,KSP算法可以实现多种条件下的路由计算。对KSP算法进行研究,在此基础上提出了 Hraf算法,该算法基于每一个状态空间中搜索的位置进行评估,进而得到最好的位置,再从当前最好位置进行搜索直到目标节点。这种策略可以避免大量无谓的搜索路径,提高算法效率,实验证明,该算法在K较小的时候比现有算法效率高。在研究Opendaylight控制器的基础上,提出了 Opendaylight控制器的扩展方案,该方案在服务抽象层增加了 Router Manager模块,在该模块上实现KSP算法。最后在与Mininet搭建的实验平台上,进行实验验证,实验结果与预期效果相符。