路由算法-SDN第一届初赛.pdfVIP

第二题路由算法题实验报告

第1步：路由算法编程（8分）

一、实验目的

在由给定的输入文件input.txt文件定义的拓扑中，计算出同时满足带宽资源

约束和路径需求的最优路线。

输入文件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

1,7,90

1,8,90

其中leftnodeID为左节点（字段名固定），rightnodeID为右节点（字段名固定），

bandwidth为带宽。srcNodeID为源节点（字段名固定）,dstNodeID为目的节点（字

段名固定）。

算法计算后得到的输出文件output.txt格式如下：

1,3,6,7

2,4,5,8

在原input.txt的基础上，本实验进行了扩展，加入了cost和priority两个字

段，新的input.txt格式如下所示：

1/12

leftnodeID,rightnodeID,bandwidth,cost

1,3,100,5

1,4,100,8

2,3,100,8

2,4,100,5

3,4,100,5

3,5,100,5

3,6,100,8

4,5,100,8

4,6,100,5

5,6,100,5

5,7,100,5

5,8,100,8

6,7,100,8

6,8,100,5

;

srcNodeID,dstNodeID,bandwidth,priority

1,7,90,5

1,8,90,10

其中cost为开销，priority为权值。cost用来衡量左节点到达右节点的代价，在

现实中可以是与带宽成反比的一个度量值，也可以是实时的时延。priority反映

目标的权值，权值越大，在最终选择匹配路径组合中向该目标倾斜的程序就越大。

二、算法简介

本实验采用的算法首先读入Input.txt文件初始化各参数，包括带宽矩阵和开

销矩阵。然后根据input.txt中的第一个目标的带宽资源约束和路径需求计算得到

满足条件的路径集合并储存起来。在这个路径集合的基础上，更新带宽矩阵，根

据下一个目标的带宽资源约束和路径需求计算得到满足条件的路径集合并储存

起来，以此类推，直到得到最后一个目标的路径集合。最后根据这些路径集合，

计算得出加权开销和最小的一组满足各目标的路径，输出到output.txt中。

在本实验中，并没有采用Dijkstra的最短路径算法，Dijkstra算法用于计算

一个节点到其他节点的最短路径，主要特点是以起始点为中心向外层层扩展，直

到扩展到终点为止。但是本实验首先要满足的要求是目标集合的带宽约束和路径

需求，若是存在多个目标，目标间的路径选取是会相互影响的。采用Dijkstra算

法只能得到单个目标的最短链路，但要得到多个目标的组合最优路径，则没法做

到。本实验所采用的算法思想也是扩展，从源节点开始向外扩展，并会保存满足

目标的路径集合，这样做的出发点是为了保证找到满足实验目的中的带宽约束和

路径需求的路径组合。在此基础上，再选出加权开销和最小的一组路径。

2/12

三、算法数据结构

下面介绍一下本算法中所采用的一些基本数据结构：

Path结构体

Path结构体用于储存一条路径，如“1-3-5-7”，成员cost表示这条路径的

总开销，由各段路径的开销值相加所得；成员depth表示路径所包含的节点

数；成员pathPoint是一个int型数组，按顺序储存路径的各节点号。

node：List链表的基本组成单位

List链表

List链表是一个类，用于储存一个路径集合，私有成员为head，用于指向链

表的头部。成员函数包括基本的构造函数和析构函数，用于在屏幕上输出信