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