当前位置: 首页 > 科技观察

Networkx

时间:2023-03-13 04:39:33 科技观察

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来保存网络数据、计算路径等,大大提高了开发效率。在学习的过程中,从不断自己造轮子到逐渐使用成熟的开源软件,接触了很多工具,学到了很多有用的知识。很多时候,自己做的轮子的性能、适用性和接口稳定性都是一个很大的考验。逐渐尝试优秀的开源工具将成为我以后编程学习的方向。