OSPF协议及链路状态算法.ppt

OSPF协议及链路状态算法 链路状态（Link-State）算法 L-S算法的基本概念 L-S算法的动态特性 L-S算法的性能分析 L-S算法与 D-V算法的比较 OSPF协议 链路状态算法的基本概念 链路状态算法的基本概念 链路状态法的计算举例 最短路径算法计算结果 链路状态算法的基本概念 链路状态法的计算举例 最短路径算法计算结果 L-S算法的动态特性 L-S建立路由表的初始过程 L-S网络发现过程剖析 C发现直连网络30.0.0.0和40.0.0.0 构造包含发现信息的L-S报文(LSP)向全网广播 接收全网的其他路由器发来的L-S报文 根据收集的信息建立拓扑数据库 启动SPF算法以C为源点计算SPF树 建立到达所有信宿的路由表（端口和代价） （1）发现拓扑变化 （2）修改拓扑数据库 （3）各自重新计算SPF树 （4）修改各自的路由表 L-S算法的性能分析 L-S算法的优点 所有路由器具有相同的网络拓扑知识（L-S图） 一次性、无修改地向全网广播LSP 路由器根据全局信息维护各自的路由表 保证链路状态信息的单向传播 保证算法的收敛性 L-S算法的代价 SPF算法计算和拓扑数据库需要更多的CPU和内存资源 网络启动时的扩散路由信息需要占用很多带宽资源 线路传输速率不同产生的影响 网络运行状态不同产生的影响 网络的一部分已经启动，而另一部分正待启动 网络的一部分刷新速度快，而另一部分刷新速度慢 造成网络的不同部分学习拥有不同的L-S图 D-V和L-S算法的比较 D-V 通过与邻居的信息交换获得网络拓扑知识 路由计算是增加路由器之间的站点数（hops） 定期刷新路由：收敛慢 向相邻站点传送路由表的副本 L-S 全网获得共同的全局性网络拓扑知识（L-S图） 计算到达其他站点的最短路径（SPF准则） 触发刷新：收敛快 向其他站点发送链路状态的动态变化 平衡混合路由选择 第三种路由选择协议将D-V和L-S两种结合起来，称为平衡混合路由协议。 1、用度量更精确的距离矢量来确定到达目 的网络的最佳路径。 2、使用拓扑结构改变来触发路由数据库的 更新，而不是定期更新。 能迅速的收敛，且使用更少的资源。 如： Cisco开发的EIGRP（增强内部网关路由协议） * 每个路由器周期性地收集和发送信息 主动测试其到所有邻居的链接状态（度量值） 向所有的路由器发送（广播）自己拥有的状态信息 得到一个全网的、动态的逻辑链路状态（L-S）图 每个路由器刷新自己的路由表 当L-S变化时，用最短路径优先(SPF)算法重新计算本地路由 D C A B ______________________________ _______________ _______________ _______________ _______________ 路由表 SPF 算法 拓扑数据库（L-S图） SPF树 L-S包 A E D C B 2 1 2 1 1 3 最短路径算法 计算加权无向图（即L-S图）中两个结点之间的最短路径 对每结点赋以标注{D(v),NP(v)} F 3 5 5 2 其中 自变量v：无向图中的结点 函数D(v)：到目前为止，从源点到结点v的最短路径（边长之和） 函数NP(v)：沿从源点到结点v且与其相邻的前一结点 A E D C B 2 1 2 1 1 3 源点A到所有结点的最短路径 F 3 5 5 2 D F E A B C 1 1 2 1 2 L-S图 SPF树 ? ? 建立路由表的初始过程 发现新的网络 路由表的维护 发现拓扑变化 修改拓扑数据库 计算SPF树 修改路由表 A C B 10.0.0.0 40.0.0.0 30.0.0.0 20.0.0.0 a0 a1 b0 b1 c0 c1 A C B 40.0.0.0 c1 LSP 30.0.0.0 c0 A E D C B F ? Net X Net X Down Net X Down LSP LSP 发现网络X不可达 构造LSP 向全网广播 发现网络X不可达 构造LSP 向全网广播 A E D C B F ? Net X 全网具有相同的L-S逻辑图。 A E D C B F ? Net X 2 2 3 3 1 1 5 2 5 A E D C B F ? Net X 根据各自计算的SPF树刷新路由表 a0 a1 a2 Net Y 路由表 路由表 路由表 路由表 路由表 2 2 1 优点 代价 路由刷新问题 线路传输速率不同 网络运行状态不同 解决办法 E应该选择哪棵SPF树？ Net X Down Net X up Net X Down 来自D 来自A 慢 Net