7.2路由算法(11) 水平分裂算法 工作过程与距离向量算法相同,区别在于到X的距离不向 真正通向X的邻居结点报告,使得坏消息传播的也快 Fjg.5-11 虽然广泛使用,但有时候会失败 B Router
7.2 路由算法（11） ▪ 水平分裂算法 - 工作过程与距离向量算法相同，区别在于到X的距离不向 真正通向X的邻居结点报告，使得坏消息传播的也快。 Fig. 5-11 - 虽然广泛使用，但有时候会失败
7.2路由算法(12) 7.2.6链路状态路由算法( Link State Routing) ■距离向量路由算法的主要问题 实际应用选择路由时,用队列长度衡量时延没有考虑线路带 宽 路由收敛速度慢。 链路状态路由算法 发现邻居结点,并学习它们的网络地址; 路由器启动后,通过发送 HELLO包发现邻居结点; 测量到每个邻居结点的延迟或开销 种直接的方法是:发送一个要对方立即响应的ECHO包 来回时间除以2即为延迟。 载荷的考虑,从ECHO包进入队列时算时或开始发送时计
7.2 路由算法（12） 7.2.6 链路状态路由算法（Link State Routing） ▪ 距离向量路由算法的主要问题 - 实际应用选择路由时，用队列长度衡量时延没有考虑线路带 宽； - 路由收敛速度慢。 ▪ 链路状态路由算法 - 发现邻居结点，并学习它们的网络地址； • 路由器启动后，通过发送HELLO包发现邻居结点； - 测量到每个邻居结点的延迟或开销； • 一种直接的方法是：发送一个要对方立即响应的ECHO包 ，来回时间除以2即为延迟。 • 载荷的考虑,从ECHO包进入队列时算时或开始发送时计 时
7.2路由算法(13) 将所有学习到的内容封装成一个包; 以发送方的标识符开头,后面是序号、年龄和一个邻居 点列表 列表中对应每个邻居结点,都有发送方到它们的延迟或开 Fig.5-15 ·链路状态包定期创建或发生重大事件时创建。 将这个包发送给所有其它路由器; 由器,序 个链路状态包到达时,若是新的,则 发;若是重复的:,则丢弃;若序号比路由器记录中的最 序号小,则认为过时而去弃 改进 序号循环使用会混淆,解决办法:使用32位序号;
7.2 路由算法（13） - 将所有学习到的内容封装成一个包； • 包以发送方的标识符开头，后面是序号、年龄和一个邻居 结点列表； • 列表中对应每个邻居结点，都有发送方到它们的延迟或开 销； Fig. 5-15 • 链路状态包定期创建或发生重大事件时创建。 - 将这个包发送给所有其它路由器； • 基本思想：洪泛链路状态包，为控制洪泛，每个包包含一 个序号，每次发送新包时加1。路由器记录信息对（源路 由器，序号），当一个链路状态包到达时，若是新的，则 分发；若是重复的，则丢弃；若序号比路由器记录中的最 大序号小，则认为过时而丢弃； • 改进 序号循环使用会混淆，解决办法：使用32位序号；
7.2路由算法(14) 路由器崩溃后,序号重置 序号出错; 秒钟车问题的解决办法:增加年龄(ae)域,每 第 减1,为零则丢弃 链路状态包到达后,延迟一段时间,并与其它已到达 的来自同一路由器的链路状态包比较序号,丢弃重复 包,保留新包 链路状态包需要应答; Fig.5-16 计算到每个其它路由器的最短路径 根据 Dijkstra算法计算最短路径 ■实用协议 OSPF IS-IS
7.2 路由算法（14） 路由器崩溃后，序号重置； 序号出错； 第二、三问题的解决办法：增加年龄（age）域，每 秒钟年龄减1，为零则丢弃。 链路状态包到达后，延迟一段时间，并与其它已到达 的来自同一路由器的链路状态包比较序号，丢弃重复 包，保留新包； 链路状态包需要应答； Fig. 5-16 - 计算到每个其它路由器的最短路径。 • 根据Dijkstra算法计算最短路径； ▪ 实用协议 - OSPF - IS-IS
7.2路由算法(15) ■链路状态算法(LS)和距离向量算法(DV)的比较 路由信息的复杂性 LS 路由信息向全网发送 with n nodes, E links, O(nE)msgs sent each DV exchange between neighbors only 收敛( convergence)速度 使用最短路径优先算法,算法复杂度为O(η*2) 》n个结点(不包括源结点),需要n*n+1)/2次比较 》使用更有效的实现方法,算法复杂度可以达到( nlogn) 可能存在路由振荡( oscillations) DV convergence time varies >)may be routing loops )count-to- infinity problen
7.2 路由算法（15） ▪ 链路状态算法（LS）和距离向量算法（DV）的比较 - 路由信息的复杂性 • LS 路由信息向全网发送 with n nodes, E links, O(nE) msgs sent each • DV exchange between neighbors only - 收敛（Convergence）速度 • LS 使用最短路径优先算法，算法复杂度为O(n**2) »n个结点（不包括源结点），需要n*(n+1)/2 次比较 »使用更有效的实现方法，算法复杂度可以达到O(nlogn) 可能存在路由振荡（oscillations） • DV convergence time varies »may be routing loops »count-to-infinity problem