路由算法-sdn第一届初赛
12页1、 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
2、 在原 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 文件初始化各参数, 包括带宽矩阵
3、和开 销矩阵。 然后根据 input.txt 中的第一个目标的带宽资源约束和路径需求计算得到 满足条件的路径集合并储存起来。在这个路径集合的基础上,更新带宽矩阵,根 据下一个目标的带宽资源约束和路径需求计算得到满足条件的路径集合并储存 起来,以此类推,直到得到最后一个目标的路径集合。最后根据这些路径集合, 计算得出加权开销和最小的一组满足各目标的路径,输出到 output.txt 中。 在本实验中,并没有采用 Dijkstra 的最短路径算法,Dijkstra 算法用于计算 一个节点到其他节点的最短路径,主要特点是以起始点为中心向外层层扩展, 直 到扩展到终点为止。 但是本实验首先要满足的要求是目标集合的带宽约束和路径 需求,若是存在多个目标,目标间的路径选取是会相互影响的。采用 Dijkstra 算 法只能得到单个目标的最短链路,但要得到多个目标的组合最优路径,则没法做 到。本实验所采用的算法思想也是扩展,从源节点开始向外扩展,并会保存满足 目标的路径集合, 这样做的出发点是为了保证找到满足实验目的中的带宽约束和 路径需求的路径组合。在此基础上,再选出加权开销和最小的一组路径。 3
4、/ 12 三、算三、算法数据结构法数据结构 下面介绍一下本算法中所采用的一些基本数据结构:下面介绍一下本算法中所采用的一些基本数据结构: Path 结构体 Path 结构体用于储存一条路径,如“1-3-5-7” ,成员 cost 表示这条路径的 总开销,由各段路径的开销值相加所得;成员 depth 表示路径所包含的节点 数;成员 pathPoint 是一个 int 型数组,按顺序储存路径的各节点号。 node:List 链表的基本组成单位 List 链表 List 链表是一个类,用于储存一个路径集合,私有成员为 head,用于指向链 表的头部。成员函数包括基本的构造函数和析构函数,用于在屏幕上输出信 息的 print 函数,以及往链表中添加一条路径的几个 addPath 函数,有直接在 链表尾部添加,有根据路径长度从小到大按序添加,也有根据路径的开销值 从小到大添加。本实验的算法使用的添加方法是按路径开销值的大小添加的 方式。 4 / 12 Target 结构体 Target 结构体用于储存目标相关的数据,包括路径需求的源点 srcPoint 和目 的地 destPoint,带宽约束
《路由算法-sdn第一届初赛》由会员第***分享,可在线阅读,更多相关《路由算法-sdn第一届初赛》请在金锄头文库上搜索。
校园足球汇报
异甘草酸镁注射液【治疗急性药物性肝损伤】Ⅱ期临床研究总结
云教室课程行政伦理学行政良心
语文S版小学二年级语文下册诺亚方舟课件优质课教学课件
未来中考趋势作文考与练
近年来广东历史试题中考易错点分析与教学启示
搜索推广那些事
小学语文二年级上册红领巾真好说课稿设计(说课设计)
新课标人教版二年级语文上册红领巾真好课件
新课程背景下的高中化学课堂教学改革
危机管理与突发事件应对
背影朱自清教案课件二课时
突发公共卫生事件培训
统计学简史及数据科学中南财经大学
水泥混凝土路面技术现状及发展终
有家真好作文讲评课
西南大学植物造景设计总复习
海外汉语教学新探索在线交流学习平台Goclef
动态黑色背景年终总结模板
孙子的治军之道与现代管理谋略总结
2024-04-26 11页
2024-04-26 23页
2024-04-26 27页
2024-04-26 23页
2024-04-26 37页
2024-04-26 20页
2024-04-26 18页
2024-04-26 10页
2024-04-26 34页
2024-04-26 24页