OSPF路由协议的算法原理与仿真的设计方法.docx
《OSPF路由协议的算法原理与仿真的设计方法.docx》由会员分享,可在线阅读,更多相关《OSPF路由协议的算法原理与仿真的设计方法.docx(3页珍藏版)》请在三一文库上搜索。
1、OSPF路由协议的算法原理与仿真的设计方法近年来,随着Internet技术在全球范围的飞速发展,应用于TCP/IP协议组中的网路层协议OSPF路由协议已发展成为在各类大型网络中应用最广泛的路由协议之一,也是TCP/IP包含的路由协议中最具有代表行的路由协议之一【1】。OSPF路由协议通过SPF(Shortest Path First,最短路径生成树算法)来计算到各节点的最短路径,该文将就该路由协议的基本原理及仿真实现展开详细介绍。1 SPF算法与OSPF路由协议原理SPF算法也被称为Dijkstra算法,是OSPF路由协议的基础。Dijkstra算法本身是一种应用在通信网模型中的单源最短路径算
2、法。SPF算法则是根据目前网络的实际情况设定参数,可应用在实际大型网络中的最短路径算法【2】。这一部分主要介绍Dijkstra算法、SPF算法及OSPF路由协议的基本原理。1.1 Dijkstra算法Dijkstra算法是用于计算一个节点到其他所有节点的最短路径的一种单源最短路径算法,算法以起始点为中心向外层层扩展,直到扩展至终点为止。Dijkstra算法通常采用永久/临时标号和OPEN、CLOSE表两种表述方式,这里我们采用永久/临时标号的方式介绍Dijkstra算法的思想和具体实现步骤。Dijkstra算法要求图中不存在负权边,设G=(V,E)是一个带权有向图,v为Dijkstra算法的源
3、点,以该场景为例,我们介绍Dijkstra算法的基本思想如下:该算法将图G中的顶点集合V分为两组:一组是已求出最短路径的顶点集合S,算法开始时S中只有一个源点,随着算法的继续,每求得一条最短路径就将其加入到集合S中,当图中所有顶点都加入到S中时算法结束;另一组为其余未确定最短路径的顶点集合U,算法进行的过程是按最短路径的递增顺序依次把U中顶点加入S中。在这一过程中,要始终保持从源点v到集合S中各顶点的最短路径长度不大于从源点v到集合U中任何顶点的最短路径长度。为方便读者理解,这里列出Dijkstra算法的具体步骤:步骤一:算法初始状态,集合S中只有一个源点,即S=v;集合U中包含除v外的其他所
4、有顶点。如果集合U中顶点u与源点v之间存在边或u不是v的出边邻接点,则该边上的权即代表顶点u的距离;步骤二:选取集合U中与源点v距离最小的顶点u1,把u1加入集合S中。此时,该选定距离就是源点v到顶点u1的最短路径长度;步骤三:将u1作为重新考虑的中间点,修改U中各顶点的距离;若从源点v到顶点u的距离(经过中间点u1后)比原来距离(不经过中间点u1时)短,则修改顶点u的距离值,修改后的距离值为到顶点u1的距离与边上的权值之和;步骤四:重复步骤二和步骤三,直到图中所有顶点都包含到集合S中,算法结束。1.2 SPF算法SPF算法将路由域中的路由器作为根节点,计算这些节点到每一个目的节点(即目的地路
5、由器)的距离。算法执行过程中,根节点根据一个统一的数据库计算得到结构类似于一棵树的路由域的拓扑结构图,即SPF算法中的最短路径图,在该最短路径图上完成OSPF路由协议。最短路径树的树干长度代表OSPF路由器至每一个目的地路由器的距离,即OSPF的Cost,计算方法如式1:Cost = 100x106/链路带宽 (1)其中,链路带宽以bps来表示。可以看出,OSPF的Cost 与链路带宽成反比,带宽越高,Cost越小,表示OSPF到目的地的距离越近。1.3 OSPF路由协议OSPF路由协议是一种链路状态的协议,主要适用于同一个路由域。这个路由域内的所有OSPF路由器都维护一个相同的数据库,其中存
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- OSPF 路由 协议 算法 原理 仿真 设计 方法
链接地址:https://www.31doc.com/p-8906382.html