基于SDN的最短路径算法(dijkstra)实现

基于SDN的最短路径算法（dijkstra）实现

一.实验要求

把路由算法作为APP加入到控制器中，使SDN网络实现根据拓扑情况自动选择路由的功能。

二.实验环境及思路

本实验的控制器采用Floodlight，向Floodlight添加模块zhlruote以实现控制器路由功能。

将上题中采用的dijkstra最短路径算法加入到控制器中，控制器根据选择出的路由下发流表给交换机，从而使主机节点能够相互通信。实验中各个链路的带宽约束及带宽需求bdw通过zhlroute模块在init()方法中读取input.txt文件获得，源节点与目的节点通过packetin消息获得。

zhlroute模块初始化完成后，监听PacketIn消息，收到消息后进行判断，如果需要转发，则通过returnRoute（）方法获取目的节点到源节点的完整路径，并对路径上的节点进行遍历以下发流表。在获取路由路径时，使用

floodlight提供的拓扑管理模块（TopologyManager.java）来获取各链路的连接状态（包括连接节点及端口，存储于clusters类集中），通过对各个节点上与其相连的链路的遍历来获取源节点到目的节点的完整路径。

模块整体流程图如图1所示：

1

图1：zhlroute模块流程图

三.实验步骤

（1）修改第一大题中用到的创建拓扑的myfirst.py文件，创建如下所示拓网络拓扑：拓扑中包括8台交换机和8台主机，交换机根据其SwitchDPID（00:00:00:00:00:00:00:00到00:00:00:00:00:00:00:08）由低到高分别标记为s1到s8，主机h1-h8（ip）分别与s1-s8相连。

2

图2：网络拓扑

图3：网络拓扑

（2）启动floodlight，注意将forwarding模块禁止启动加载，然后对zhlroute模块进行连通性测试，结果如图4。说明各主机可以进行通信，zhlroute模块能够发现路径并下发流表。

3

图4：zhlroute模块功能测试

实验中带宽约束及带宽需求（bdw）通过读取input.txt文件获得，input.txt文件内容如下（本实验中的源节点与目的节点从PacketIn消息中获得，不通过input.txt文件获得）：

leftnodeID,rightnodeID,bandwidth

1,3,100 1,4,100 2,3,100 2,4,100 3,4,100 3,5,100 3,6,100 4,5,100 4,6,100 5,6,100 5,7,100 5,8,100 6,7,100 6,8,100 ;

srcNodeID,dstNodeID,bandwidth 3,8,90

（3）进行路径分析测试，在模块中添加语句System.out.println(route)以输出获取

到的Route，输入以下命令：测试主机h1与h7能否通信并获取经过的路径信息。

4

elcipse控制台中输出的信息（整条路径）如下：

Route

[id=RouteId

[src=00:00:00:00:00:00:00:07

port=1],

port=5], port=5],

dst=00:00:00:00:00:00:00:01],

port=2], port=2], port=2],

switchPorts=[[id=00:00:00:00:00:00:00:07, [id=00:00:00:00:00:00:00:05, [id=00:00:00:00:00:00:00:03, Route

[id=RouteId

[id=00:00:00:00:00:00:00:07,

[id=00:00:00:00:00:00:00:05, [id=00:00:00:00:00:00:00:03,

[id=00:00:00:00:00:00:00:01, port=2], [id=00:00:00:00:00:00:00:01, port=1]]]

[src=00:00:00:00:00:00:00:01

port=1],

port=2], port=2],

dst=00:00:00:00:00:00:00:07],

port=2], port=5], port=5],

switchPorts=[[id=00:00:00:00:00:00:00:01, [id=00:00:00:00:00:00:00:03, [id=00:00:00:00:00:00:00:05,

[id=00:00:00:00:00:00:00:01,

[id=00:00:00:00:00:00:00:03, [id=00:00:00:00:00:00:00:05,

[id=00:00:00:00:00:00:00:07, port=2], [id=00:00:00:00:00:00:00:07, port=1]]]

输出的route中，每条完整路径由id确定（源节点和目的节点）。完整路径包括了路径所经过的每个端口的信息（所属交换机、端口号）。

上面输出的route信息中，路径节点包括（1，3，5，7），即该路径经过了s1、s3、s5、s7交换机，结果和路由算法题中的结果一致，说明该模块成功完成了上题中的路由算法功能。

（4）修改输入数据，再次进行路径分析测试

修改input.txt文件中的数据如下所示：

leftnodeID,rightnodeID,bandwidth 1,3,80 1,4,100 2,3,60 2,4,100 3,4,100 3,5,95 3,6,100 4,5,80 4,6,110 5,6,90 5,7,120 5,8,100 6,7,95 6,8,100

5

;

srcNodeID,dstNodeID,bandwidth 3,8,90

再次输入命令如下图所示：测试主机h1与h7能否通信并获取经过的路径信息。

elcipse控制台中输出的信息（整条路径）如下：

Route

[id=RouteId

[src=00:00:00:00:00:00:00:07

port=1],

port=5], port=2], port=6], port=6],

dst=00:00:00:00:00:00:00:01],

port=2], port=6], port=3], port=3], port=2],

switchPorts=[[id=00:00:00:00:00:00:00:07, [id=00:00:00:00:00:00:00:05, [id=00:00:00:00:00:00:00:08, [id=00:00:00:00:00:00:00:06, [id=00:00:00:00:00:00:00:04, Route

[id=RouteId

[id=00:00:00:00:00:00:00:07,

[id=00:00:00:00:00:00:00:05, [id=00:00:00:00:00:00:00:08, [id=00:00:00:00:00:00:00:06, [id=00:00:00:00:00:00:00:04,

[id=00:00:00:00:00:00:00:01, port=3], [id=00:00:00:00:00:00:00:01, port=1]]]

[src=00:00:00:00:00:00:00:01

port=1],

port=2], port=3], port=3], port=6],

dst=00:00:00:00:00:00:00:07],

port=3], port=6], port=6], port=2], port=5],

switchPorts=[[id=00:00:00:00:00:00:00:01, [id=00:00:00:00:00:00:00:04, [id=00:00:00:00:00:00:00:06, [id=00:00:00:00:00:00:00:08, [id=00:00:00:00:00:00:00:05,

[id=00:00:00:00:00:00:00:01,

[id=00:00:00:00:00:00:00:04, [id=00:00:00:00:00:00:00:06, [id=00:00:00:00:00:00:00:08, [id=00:00:00:00:00:00:00:05,

[id=00:00:00:00:00:00:00:07, port=2], [id=00:00:00:00:00:00:00:07, port=1]]]

上面输出的route信息中，路径节点包括（1、4、6、8、5、7），即该路径经过了s1、s4、s6、s8、s5、s7交换机，结果和路由算法题中的结果一致，说明该模块成功完成了上题中的路由算法功能。

四.实验结论：zhlroute模块实现了上题中的路由算法功能，能根据input.txt文

件中提供的数据进行最优路径的计算，根据计算出的路径（route）对相关交换机下发流表以完成数据的传输。

五.zhlroute模块分析

（1）模块中的zhldjst()方法是上题中Dijkstra()方法的实现，用来计算最短路径。程序代码如下：

protected void zhldjst(Cluster cl,int v,int b, int dist[], int mprev[] ,int c[][],int hop[]) {

6

boolean s[] = new boolean[maxnum]; for (long node: cl.links.keySet()) { dist[(int)node] = c[v][(int)node]; s[(int)node] = false;

if(dist[(int)node] == minint) mprev[(int)node] = 0; else {

mprev[(int)node] = v; hop[(int)node] = 1; } }

dist[v] = maxint; s[v] = true;

for (long node: cl.links.keySet()) { int tmp = b; int u =v;

for (long node1: cl.links.keySet()) {

if((!s[(int)node1])&& dist[(int)node1]> =tmp){ u =(int)node1;

tmp = dist[(int)node1]; } }

s[u] = true;

for (long node1: cl.links.keySet()) { int least = dist[u];

if(c[u][(int)node1]

if((!s[(int)node1]) &&(least >dist[(int)node1])){ hop[(int)node1] = hop[u]+1; mprev[(int)node1] = u; dist[(int)node1] = least; }

else if((!s[(int)node1]) && (least == dist[(int)node1])){ if(hop[(int)node1]>hop[u]+1){ hop[(int)node1] = hop[u]+1; mprev[(int)node1] = u; dist[(int)node1] = least; } } } } }

（2）getRoute()方法用来获取从源节点到目的节点的完整路径，即上面测试中

7

输出的route，流程图如下图：

图5：getRoute()方法流程图

getRoute()方法程序代码如下：

public Route getRoute(long src, short srcPort, long dst, short dstPort, long cookie,

8

boolean tunnelEnabled) {

RouteId id = new RouteId(src,dst); Route result = null;

for(Cluster cl: TopologyInstance.clusters) {

zhldjst(cl,(int)src, bdw, dist, mprev, c,hop); LinkedList switchPorts = new LinkedList(); NodePortTuple npt;

npt = new NodePortTuple(dst, dstPort); switchPorts.addFirst(npt);

for(Iterator iter = cl.links.get(dst).iterator();iter.hasNext();){ Link ln = (Link)iter.next();

if((ln.getDst()==dst)&&(ln.getSrc()==mprev[(int)dst])){ npt = new NodePortTuple(ln.getDst(), ln.getDstPort()); switchPorts.addFirst(npt);

npt = new NodePortTuple(ln.getSrc(), ln.getSrcPort()); switchPorts.addFirst(npt); dst = ln.getSrc(); break; } }

while(dst != src){

for(Iterator iter =

cl.links.get(dst).iterator();iter.hasNext();){ Link ln = (Link)iter.next();

if((ln.getDst()==dst)&&(ln.getSrc()==mprev[new Long(dst).intValue()])){

npt = new NodePortTuple(ln.getDst(), ln.getDstPort()); switchPorts.addFirst(npt);

npt = new NodePortTuple(ln.getSrc(), ln.getSrcPort()); switchPorts.addFirst(npt); dst = ln.getSrc(); break; } } }

npt = new NodePortTuple(src, srcPort); switchPorts.addFirst(npt);

result = new Route(id,switchPorts); }

return result; }

9

本文来源：https://www.bwwdw.com/article/3lxv.html