设计本官方网站广告,东莞市住房和城乡建设局网上办事平台,建设工程规范在哪个网站下载,合肥知名网页制作公司链路状态路由算法#xff08;LS算法#xff09;
工作原理
每个路由器将自己的链路状态信息洪泛到网络上的所有路由器。tips:#xff08;每个路由器都洪泛会给网络带来负担#xff09;每个路由器最终会知道整个网络的拓扑结构#xff08;LSDB#xff09;。每个路由器使用…链路状态路由算法LS算法
工作原理
每个路由器将自己的链路状态信息洪泛到网络上的所有路由器。tips:每个路由器都洪泛会给网络带来负担每个路由器最终会知道整个网络的拓扑结构LSDB。每个路由器使用Dijkstra最短路径算法计算本路由器到其他路由器的最短路径更新路由表。路由器的链路状态发生变化时会继续洪泛自身的链路状态信息到其他路由器。 链路与链路状态 链路的本质上是路由器上的一个接口 链路状态是有关各条链路的状态信息 链路状态数据包洪泛 路由器一旦接收到来自相邻路由器的LSP立即将该LSP从除接收该LSP的接口以外的所有接口发出
Dijkstra算法直接见图
Dijkstra算法分析 算法复杂度n个节点
每次迭代需要检查不在N的节点最差的复杂度n*n - 1/2次比较O(n^2)平均的复杂度O(nlogn) 路由振荡假设link cost amount of carried traffic链路代价与流量和有关且链路代价的具有方向性LS算法可能会让分组一会逆时针转发一会顺时针转发形成振荡。本质同时执行最短路径算法导致路由振荡可以采用随机数解决同时问题
OSPF协议
概述
Open Shortest Path First开放式最短路径优先路由协议链路状态路由算法无路由自环用于AS内部属于IGP使用区域划分适用于大规模网络支持VLSM和CIDR使用组播方式发送协议报文支持验证OSPF是基于IP的协议号为89OSPF是典型的停止等待协议自身实现了可靠传输
路由器标识Router ID
用于唯一确定OSPF路由器一个32位的无符号整数整个自治系统内唯一若不手动配置一般取该路由器的所有接口的IP地址的最大值loopback地址优先
OSPF的链路代价 一条OSPF链路的代价定义为10^8/BandWidth 一条OSPF路由的代价为其经过的所有链路代价的总和
OSPF规定的网络类型
网络类型举例广播以太网非广播多路访问NBMA帧中继、X.25点到点PPPHDLC点到多点多个点到点链路的集合全连通网络的处理 选取DR和BDR DR指定路由器 村长 BDR备份指定路由器 副村长 DR负责通告路由 BDR备份
选取规则 选取优先级最大的 选取router id 最大的
选取方式 投票制和终身制 OSPF的数据包格式
ODPF包类型描述Hello 不需要确认用户邻居路由器之间建立和维护邻接关系数据库描述包DBD描述每台OSPF路由器的链路状态数据库的内容链路状态请求包LSR请求链路状态数据库的部分内容链路状态更新包LSU传送链路状态数据通告LSA给邻居路由器链路状态确认包LSAck不需要确认确认邻居发过来的LSA已经收到
OSPF划分区域 目的减少洪泛的范围 工作方式
同一个区域内部路由器之间使用链路状态算法洪泛的范围限于一个区域内部。不同区域之间的路由通过ABR区域边界路由器负责通告距离矢量算法必须要有骨干区域area 0)且所有区域应当和骨干区域物理上直连保证不会出现路由环路问题。区域划分可以和IP地址结合在ABR上通告汇总的路由。
