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

;

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