路由算法-sdn第一届初赛

1 / 12 第二题第二题路由路由算法题实验报告算法题实验报告 第第 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 格式如下所示： 2 / 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 算 法只能得到单个目标的最短链路，但要得到多个目标的组合最优路径，则没法做 到。本实验所采用的算法思想也是扩展，从源节点开始向外扩展，并会保存满足 目标的路径集合， 这样做的出发点是为了保证找到满足实验目的中的带宽约束和 路径需求的路径组合。在此基础上，再选出加权开销和最小的一组路径。 3 / 12 三、算三、算法数据结构法数据结构 下面介绍一下本算法中所采用的一些基本数据结构：下面介绍一下本算法中所采用的一些基本数据结构： Path 结构体 Path 结构体用于储存一条路径，如“1-3-5-7” ，成员 cost 表示这条路径的 总开销，由各段路径的开销值相加所得；成员 depth 表示路径所包含的节点 数；成员 pathPoint 是一个 int 型数组，按顺序储存路径的各节点号。 node：List 链表的基本组成单位 List 链表 List 链表是一个类，用于储存一个路径集合，私有成员为 head，用于指向链 表的头部。成员函数包括基本的构造函数和析构函数，用于在屏幕上输出信 息的 print 函数，以及往链表中添加一条路径的几个 addPath 函数，有直接在 链表尾部添加，有根据路径长度从小到大按序添加，也有根据路径的开销值 从小到大添加。本实验的算法使用的添加方法是按路径开销值的大小添加的 方式。 4 / 12 Target 结构体 Target 结构体用于储存目标相关的数据，包括路径需求的源点 srcPoint 和目 的地 destPoint，带宽约束 bw，权值 priority。指针 next 指向当前 target 链表 的下个节点，startPath 储存当前 target 的起始路径，即只包含源点 srcPoint 的一条路径。List 链表储存满足目标的路径集合，ePathList 链表储存满足前 面的 target 的路径集合。 TargetTable 结构体 TargetTable 结构体是一个目标表，用于储存多个 target，成员包括目标表的 大小 size 和 Target 数组 target。 算法算法的的 exe 可执行可执行文件文件、源代码源代码及及测试用例测试用例我们我们以以附件附件形式形式上传上传。 四、实验流程四、实验流程 1. 算法首先调用 initialFromFile 函数读入输入文件 input.txt， 根据文件中的内容 初始化带宽矩阵 B，开销矩阵 C 和目标表。其中带宽矩阵 B 和开销矩阵 C 都是大小为 M 的对称阵，其中 M 为由 input.txt 定义的拓扑中节点的数目， 由于输入文件中的路径是双向路径，故 B 和 C 都是对称阵。 图 4-1 带宽矩阵 B 示意图 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 5 / 12 图 4-2 开销矩阵 C 示意图 使用实例input.txt文件得到的带宽矩阵B和开销矩阵C如图4-1和图4-2 所示。在实现上，B，C 使用的是（M+1）*(M+1)的二维数组，数组的下标 从 1 开始（为了和矩阵的行和列对应） ，如图 4-1 所示，B23值为 100，表 示 2-3 这条链路的带宽为 100，同理，C34值为 5，表示 3-4 这条链路的 开销为 20 。 初始化后的目标表中每个目标的情形如图 4-3 所示：可以看到输入文件 中第一个目标的路径需求和带宽约束以及权值都已经储存到 target 0，当前 target 0 中的 list 和 ePathList 链表都为空。 图 4-3 目标表中的 target 0 中的信息 2. 调用 getNextPoint 函数计算满足第一个目标的路径集，储存到 target 0 的 list 链表中。 getNextPoint 的声明如图 4-4 所示。 图 4-4 getNextPoint 函数的声明 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 6 / 12 getNextPoint 函数的运行步骤如下： 1) 假设输入路径 path 为“P1,P2Pk” ，函数首先判断输入路径节点数（即 k）的奇偶性，若是奇数，则在带宽矩阵 B 第 Pk 行中寻找满足带宽约束 条件的下一跳， 反之则在 B 中第 Pk 列寻找满足带宽约束条件的下一跳。 这里假设 k 为奇数，偶数情况类似。 2) 对 B 中第 Pk 行进行遍历，假如 BPki（1next，重复步骤 1） 。 4. 调用 getLeastSumCostPath 函数， 从目标表中选出加权开销和最小的一组路径 组合，写入到程序的输出文件中。加权开销和的计算方式为： Sum = () ( ) 即该组路径组合中每条路径的开销乘以对应目标的权值再求和。由于每 个 target 的 list 中路径是按开销从小到大排列的，故寻找加权开销和最小的 一组路径组合时，只需要计算 target 链表中包含 list 的第一条路径的那些路 径组合，在它们中选出加权开销和最小的一组。 举个例子：假如有两组路径，如图 4-7 所示，假如目标 1 和目标 2 的权 值分别为 5 和 10，那么路径组 1 的加权开销和1= 21 5 + 15 10 = 255， 路径组 2 的加权开销和2= 15 5 + 21 10 = 285， 那么程序选择的路径组 为路径组 1。 上述例子中，假如目标 1 和目标 2 的权值分别为 10 和 5，那么容易得出 最后选择的路径组为路径组 2，由此可看出权值在选择路径过程中所起的作 用。 图 4-7 两组路径（含开销） 路径组 1： 1,3,6,7 cost：21 2,4,6,8 cost：15 路径组 2： 1,4,6,7 cost：15 2,3,5,8 cost：21 8 / 12 五、实验结果五、实验结果 以下是几个测试用例及对应的结果分析： 1. 不包含 cost 和 priority 字段的情形： 输入文件和输出文件的input文件及运行程序后得到的output 文件如图 5-1所 示。 图 5-1 测试用例 1 的输入和输出文件 9 / 12 2. 目标数量为 2 的情形： input 文件定义的拓扑如图 5-2 所示，input 文件及运行程序后得到的 output 文件如图 5-3 所示： 图 5-2 测试用例 2 的拓扑 图 5-3 测试用例 2 的输入和输出文件 10 / 12 3. 链路带宽不等的情形： 所用拓扑中包含带宽为 100 和 80 的链路，如图 5-4 所示，input 文件及运行 程序后得到的 output 文件如图 5-5 所示： 图 5-4 测试用例 3 的拓扑 图 5-5 测试用例 3 的输入和输出文件 11 / 12 4. 拓扑较复杂的情形： 所用拓扑如图 5-6 所示，input 文件及运行程序后得到的 output 文件如图 5-7 所示： 图 5-6 测试用例 4 的拓扑 图 5-7 测试用例 4 的输入和输出文件 12 / 12 5. 不存在满足目标集的路径集合情形： 对于这种情形，程序的处理是在输出文件 output.txt 中显示” There exists no path satisfied all targets.”如图 5-8 所示： 图 5-8 测试用例 5 的输入和输出文件 综合以上几个例子可以得出，本算法能够处理不同的 Input.txt 数据，并且可 以处理带宽资源约束和路径需求，并综合考虑路径的开销和权值，得到加权开销 和最小的路径组合，基本满足了实验目的，达到实验的基本和扩展要求。