SDN（SoftwareDefinedNetworking），一种为SDN应用实现路由算法的工具，是一种新型的网络架构，通过一个集中的控制平面来管理数据层面的转发等操作。网络连接是最基本的要求。为了保证网络连通性，控制器需要应用相应的图论算法计算转发路径，完成数据转发。在开发SDN应用时，为了完成基本的路径计算，开发者往往需要独立编写网络算法，不仅繁琐，而且性能和代码复用性也受到开发者个人编程水平的影响。所以本文将介绍网络算法工具networkx，用于完成路径算法的开发。networkx是一个Python语言包，用于创建、操作和研究复杂网络的动力学、结构和功能。networkx支持创建简单的无向图、有向图和多重图；内置许多标准图论算法，节点可以是任意数据，例如图像文件；支持任意边界值维度，功能丰富，简单易用。由于Networkx代码经过多次测试，在性能方面做了大量工作，使用Networkx内置的各种图论算法可以为SDN应用的开发带来很多便利，节省开发时间，减少代码失败率。读者可以从官网文档快速获取networkx的安装和使用，不再赘述。下面的内容将简单介绍Networkx的经典图论算法，包括最短路径、KSP（KShortestPaths）算法和Traversal（遍历）算法BFS（广度优先搜索）/DFS（深度优先搜索）。最短路径算法Dijkstra和FloydDijkstra计算单个源到所有其他节点的最短路径的算法和Floyd计算所有节点之间的最短路径的算法是最经典的网络算法之一。下面分别介绍二者在networkx中的实现。Dijkstra不管有向图还是无向图都可以使用Dijkstra算法，G是networkx生成的图数据结构。source是起点，target是终点。起点、终点和权重是可选参数。networkx.shortest_path(G,source=None,target=None,weight=None)没有右图networkx.single_source_shortest_path(G,source[,cutoff])有右图networkx.dijkstra_path(G,source,target,weight='weight')Floyd对于Floyd算法，有两种实现：unweightedgraph和weightedgraph：unweightedgraphnetworkx.all_pairs_shortest_path(G[,cutoff])weightedgraphnetworkx.all_pairs_dijkstra_path(G[,cutoff,weight])为路径长度计算可以通过调用network.XXX_length函数获得，其中XXX为对应路径计算算法的名称。除了上面提到的几种算法，networkx还针对很多需求设计了变体函数，比如返回多个相同长度的***路径算法等，读者可以根据自己的需要定制学习内容。K-Shortestpaths在研究网络路由算法/转发算法时，除了以跳数作为计算最优路径的标准外，还会用到很多其他的指标，比如带宽、时延等，它也可以根据各项指标，建立多维评价体系，计算权重值，进而计算出最优路径。例如，当涉及带宽作为标准时，计算量可能非常大。首先获取网络链路的剩余带宽数据，然后从源头开始，在路径中选择带宽最高的路径。由于一条链路的最大剩余带宽取决于剩余带宽最小的那条，如果采用贪心算法逐跳剔除，很可能计算错误，所以每遇到一个分支，需要一条路径被选中，其他未选中的路径应被保存。路径数据。每个节点都需要比对所有的数据，从而选择当前最好的路径，直到比对完所有的链路。这样的算法可以通过修改Dijkstra算法来完成。逻辑不难，但是效率不高。具体实现不再赘述。读者可以查看我在网上找到的一篇介绍文章：基于SDN的最短路径算法(Dijkstra)dijkstra。在研究过程中发现很多论文中提到的方法都是基于拓扑信息算法K条最短路径，然后根据带宽计算出最优路径。根据算法，可以直接在K条路径中选择最佳路径，也可以设置权重，计算跳数和带宽的加权值，然后选择***。由于跳数的值和带宽的值相差很大，因此两者都需要归一化/正则化。之所以要考虑跳数，是因为交换机每经过一次，就多消耗一个资源，所以需要考虑。例：路径A带宽为100M，跳数为2；路径B的带宽为110M，跳数为5。如果根据带宽选择B，路径B经过的路径是A的数倍，消耗更多的资源，产生更多的传输。还有更多的延迟和传播延迟（假设5跳的链路长度大于2，否则不成立），所以考虑A可能是更好的路径。传统的KSP算法有很多。Yen和JinY在1971年发表的论文“FindingthekShortestLooplessPathsinaNetwork”中提出的Yen's算法就是经典算法之一。读者可以直接点击Yen算法的wiki。算法思路并不复杂，基本思路是：Dijkstra选择第一条***路径，保存为A[0]的外层循环，k从1到k。内循环，以第k-1条（上一条）***路径为路径，从路径的***点开始作为fork节点，fork节点之前的前一条***路径和当前路径的一致的部分称为根路径；去除分叉点上选择的路径的分支（权重设置为正无穷大），然后计算dijkstra，将路径计算结果放入临时数据结构B中，然后随着循环进行，分叉点继续向前移动，直到它跳到终点之前。与内循环相比，选择了多个潜在的最优路径。对临时数据结构B中的路径进行排序，找出最佳路径，加入到A数据结构中，保存为A[k]，结束外层循环round。外循环继续，直到找到K***路径。Networkx已经实现了KSP算法。该算法补丁是在2015年4月左右加入到networkx项目中的，由于已经使用了networkx中的all\_shrtest\_paths这个名字，所以新加入的算法对应的函数在networkx中命名为all_simple_pay。具体参数如下：all_simple_paths(G,source,target,cutoff=None)其中G是networkx的图数据结构，source是起点，target是终点，cutoff是搜索深度，只有路径有返回比截止时间短的路径长度。为了优化性能，函数的返回值是一个生成器（generator），读者可以通过for循环生成对应的K条最短路径。使用生成器可以将结果一个一个计算出来，而不是将一个运算的结果全部写入内存，这样可以大大减少内存占用。在一些网络应用场景中，Traversal会使用遍历算法，比如BFS（广度优先搜索）/DFS（深度优先搜索）算法，networkx已经定义了相应的函数，具体内容限于篇幅不再介绍。读者可以查看networkx官方文档中关于遍历的文档进行学习。小结在开发SDN应用时，网络连通性是最基本的需求。在开发网络应用时，可以使用networkx来保存网络数据、计算路径等，大大提高了开发效率。在学习的过程中，从不断自己造轮子到逐渐使用成熟的开源软件，接触了很多工具，学到了很多有用的知识。很多时候，自己做的轮子的性能、适用性和接口稳定性都是一个很大的考验。逐渐尝试优秀的开源工具将成为我以后编程学习的方向。
