SDN路由算法设计与实现
台湾牛轧糖
摘要
早安祝福语如今，计算机网络快速发展，自其基本架构提出以来，至今并未有本质的发展。而且，随着互联网的快速发展，对网络的要求不断提高，随着而来的问题则是传统的网络架构已经无法满足现今技术要求。在此背景下，SDN被提出并飞速发展，现已取得卓越成果。将转发平面从数据平面分离是SDN的核心思想，数据平面仅负责报文转发，转发的决策由控制平面负责，便易地实现了网络创新。网络的配置也解决了传统网络分布式架构的诸多问题，如网络不可控、配置复杂等。
在SDN之前的传统网络中，我们并不能完全知道整个网络的全局拓扑，这是，传统网络中的路由问题是一个瓶颈问题，路由器只能掌握网络中的一部分拓扑，那么整个网络的路由计算就是只能采取分布式算法。这样的话，整个网络的路由过程并能不是完全可控的，或者需要付出很大的代价才能实现对路由过程的控制。那么SDN的诞生就为解决这个问题提供一个思路，在SDN中，存在一个中心控制器，该控制器可以获得下层网络的整个拓扑，并且可以做出控制报文的转发决策，这样，传统网络中路由过程不可控的问题在SDN中就可以得到解决。现在主流SDN控制器所采用的路由算法为Dijkstra 算法，Dijkstra算法是一种最短路径算法，该算法只能算出源节点和目的节点之间的短路径。但是当我们对于从源节点到目的节点之间的路径有一些限制条件时，例如要绕过出现故障可能性较大的节点时，Dijkstra算法所能计
手动变速器算出的最短路径可能就不符合我们的要求。因此，在路由计算的实际应用中，我们不仅要考虑最短路径，还需要考虑次短路径、次次段路径，这时，KSP（K最短路径）算法就可以满足上述限制条件的路由计算。KSP算法可以计算出按最优、次优、次次优等顺序排列的一些路径集合，集合的大小根据K值得大小确定，我们便可以从这些路径中选出符合限制条件的路径来。KSP算法在物流、序列比对、网络和文本处理等领域有着非常广泛的应用。因此，本文希望将KSP算法应用与SDN控制器中，可以实现对SDN路由器路由功能的扩展，以便满足更多的路由需求。
本文针对KSP算法以及SDN控制器—Opendaylight进行研究，取得如下成果：
1、对Dijkstra算法和KSP算法在生存性以及必经节点下的性
能进行分析比较，分析结果表明，KSP算法可以实现多种条件
下的路由计算。
2、对KSP算法进行研究，在此基础上提出了Hraf算法，该
算法基于每一个状态空间中搜索的位置进行评估，进而得到最
好的位置，再从当前最好位置进行搜索直到目标节点。这种策
欧式快热炉
防辐射服略可以避免大量无谓的搜索路径，提高算法效率，实验证明，该算法在K较小的时候比现有算法效率高。
3、在研究Opendaylight控制器的基础上，提出了Opendaylight控
制器的扩展方案，该方案在服务抽象层增加了Router Manager
模块，在该模块上实现KSP算法。最后在与Mininet搭建的实
蔡艺林
验平台上，进行实验验证，实验结果与预期效果相符。
关键词：SDN；KSP；Opendaylight
THE DESIGN AND REALIZATION OF
ROUTING ALGORITHM IN SDN
ABSTRACT
At prent，the computer network is in a period of innovation，the basic framework of the network has not esntially change since the propod over the years.On the other hand the rapid developm
ent of the Internet makes the demand for network higher and higher.This makes it more and more unable for traditional network architecture to meet the demand of new technology.In order to meet the new requirements，SDN appeared，developed rapidly，and has made numerous success.Its main idea is to parate the forwarding plane from the data plane，the data plane only need to care about the forwarding of a message，control plane is ud to make forwarding decisions.Threshold of innovation is greatly reduced and configuration of network is just like software on the operating system，which can be installed or uninstalled very easily.So some problems of traditional network distributed architecture，such as complex configuration，network uncontrolled and many other incurable dias are solved.
In the traditional network，routing problem has always been a bottleneck，becau it is impossible to know global network topology，so we can only u distributed algorithm which is bad on local information.In this way，the routing process is uncontrollable，or need to be very costly to control.In the SDN，SDN controller has central controller，it gets unified access to the entire network topology information，and has the ability to control packet forwarding decision，so it is easy for SDN to solve traditional network routing problem.Now a lot of SDN controllers u the Dijkstra algorithm as their routing algorithm，Dijkstra algorithm is the shortest path algorithm，which can only calculate the sh
ortest path from source node to destination node. However if there are some constraints，such as bypassing the node which has high rate of failure，Dijkstra algorithm cannot meet this demand.So in practice，we need not only consider the shortest path，but also consider cond short path，third short path and so on.So KSP(K shortest paths)algorithm，which can get a t of paths ordered in the most optimal、optimal and suboptimal，has a very wide application in the logistics，quence alignment，networks，text processing，and other fields algorithm.KSP algorithm can also meet the practical requirements of routing computation in SDN controller.Therefore，this article wants to make KSP algorithm to apply in SDN controller，which can extend
functions of routing in SDN controller，and meet the demand of routing in future.徐整
The author of this paper makes rearch of KSP algorithm and the SDN controller–Opendaylight，and gets the following results：
1.Analyzes and compares the Dijkstra algorithm and KSP algorithm under the survivability and strait node performance，the analysis results show that the KSP routing calculation algorithm can work in a variety of conditions.
2.Bad on the study of KSP algorithm，we put forward the Hraf algorithm.Hraf algorithm evaluate b
ad on position arched in each state space，to get the best location，and then arch again until reaching the destination node from the best position.This strategy can avoid a lot of unnecessary arch path，improve the efficiency of the algorithm，experimental results show that when K is smaller the algorithm has more efficiency than the existing algorithm.
敦煌的艺术3.We put forward the extension scheme of Opendaylight controller bad on the basis rearch of Opendaylight controller.In this scheme，we add a module called Router Manager in the rvice abstraction layer.The realization of KSP algorithm is on the module. Finally we do some experiment on the platform which contains Mininet，the experimental results are in conformity with the desired effect.
