（2）改进方法：当数据包被泛洪到其他 路由器时并没有被立即排入队列等待， 首先放到保留区。在它被转发出去前另 一个来自同一源路由器的链路状态数据 包也到来，就比较他们的序号来判定转 发哪一个。实用文档
路由器B的状态包缓冲区 特殊情况：如果一个重复数据包到来时，原来 的数据包仍然在缓冲区。此时标志位的变化。C 的副本从F到达，那么标志位变为100011.
假设使用延迟作为距离度量，并且路由器知道他到 每个邻居的延迟。每隔T秒每个路由器向他的每个 邻居发送一个表，该表记录了它到每个目标的延迟， 同时它也从邻居那里收到一个类似的表。实用文档ຫໍສະໝຸດ 交换距离信息更新路由表示例
实用文档
无穷计算问题
A BCD E
A BCD E
∞∞∞ 1 ∞∞ 12∞ 123 123
由器的网络，最优的层数是lnN， 每个路由器所需的路由器表项是
elnN个。当然由分层引起的路 径长度的实际增长非常小。
实用文档
广播路由
同时给全部的目标地址发送一个 数据包称为广播
扩散法。 多目标路由：每个数据包含一组
目标地址，经过路由器，针对目 标选路，目标分散
逆向路径转发（reverse path forwarding)
（a）
∞ 初始时
1
∞ 第1次交换后 3
∞ 第2次交换后 3 ∞ 第3次交换后 5
4 第4次交换后 5
7
7
∞
23 23 43 45 65 67 8... 7 ∞∞
（b）
4 初始时 4 第1次交换后 4 第2次交换后 4 第3次交换后 6 第4次交换后 6 第5次交换后 8 第6次交换后
∞
问题的核心在于当X告诉Y自己有一条通往某个地方的路径 的Y不知道自己是否在这条路径上。
或者估计的流量和拓扑结构，来 调整它的路由决策。所用的路由 选择是在预先离线情况下计算好 的，并在网络启动时被下载到路 由器中的。
自适应---根据拓扑结构、通信 量的变化来改变其路由选择。
实用文档
5.2.1 优化原则
最优路径一般陈述：如果路由器J 在路由器I到K的最优路径上，那
么J到K的最优路径也必须遵循同
实用文档
链路状态路由算法
发现邻居，了解其网络地址 设置到每个邻居节点的距离或成 本度量值。
构造一个包含所有刚刚获知的 链路信息包。 将这个包发送给所有其他的路由 器，并接受来自其他路由器的信 息包。
计算每个到其他路由器的最短 路径。
实用文档
发现邻居 在每一条点到点的线路上发送
一个特殊的HELLO数据包，线路另一端 的路由器返回一个应答说明自己是谁。
也能找到一条路径使得数据包到达目
的地。
实用文档
距离矢量路由算法 （Distance Vector Routing）
工作原理 :每个路由器维护一张表，表中 给出了到每个目的路由器的已知最短 “距离”和相应输出线路,并通过与相 邻路由器交换距离信息来更新表。
“距离” :到目的路由器的跳数、估计的 时间延迟、路由排队的分组估计总数或 类似的值。
实用文档
一个网络示例
链路状态包
实用文档
分发链路状态数据包
（1）泛洪法：为了控制泛洪规模，每个 数据包包含一个序号，序号随着每个数 据包发出逐一递增，路由器记录下它所 看到的所有（源路由器，序号）对，当 一个新的链路状态数据包到达时，路由 器检查这个数据包是否已经出现在上述 观察到的列表中，若是新的数据包，则 转发，若重复或过时则丢弃。
两个或多个路由器通过一个广 播链路连接的情况：
实用文档
设置链路成本 一种与带宽成反比； 链路延迟是成本的组成部分。 方法：通过线路给另一边发送一个特
殊的ECHO数据包，要求对方立即发回， 通过测量往返时间再除以2，发送路由 器可以得到一个合理的延迟估算值。 构造链路状态包 内容：发送方的标示符，接着是一个 序号和年龄，邻居列表。 创建时间：周期性，发生重要事情时。
Dijksstra算法
实用文档
实用文档
5.2.3 泛洪算法
泛洪：将每一个入境数据包发送到了 除该数据包到达的那条线路外的每条 出境线路。
缺点：产生大量重复数据包。 措施 ：（1）设置跳计数器；
（2）跟踪数据包。
优点：确保数据包被传送到每个网络中 的节点；
泛洪途径的鲁棒性非常好；
即使大量路由器被炸成碎片路由器
对于大型网络，两级层次结构可能不 够，一般将区域组织成簇，将簇组织 成区，将区组织成群。
实用文档
两级分层实例
区域1
区域2
1A完整表
1A层次表
区域3 区域4 区域5
实用文档
优点：随着区域数与每个区域中 路由器数量之比值的增加，节省 下来的空间也随之增加。
缺点：增加了路径长度。 经科学发现，对于一个包含N个路
路由算法（Routing Algorithm）
是网络层软件的一部分，负责所 收到数据包发送到哪一条线路上。
路由选择算法应具有下列特性： 正确性、简单性、鲁棒性、稳定性、 公平性和最优性。 路由算法应该能够处理拓扑结构和 流量方面的各种变化，而不能要求所 有主机停止所有工作。
实用文档
路由选择算法可以分为两大类： 非自适应---不会根据当前测量
样的路径。
B
汇集树： A
C
I
D
E G
J
F
H
路由器B的汇集树
实用文档
5.2.2 最短路径算法
基本想法：构造一张网络图中每 个节点代表一个路由器，每条边 代表一条通信线路或链路，为了 选择给定路由器之间的路由，只 需找出他们的最短路径。
最短路径：
度量方法：跳数，以千米为单 位的距离。标准测试包的平均延 迟。
计算新路由：利用Dijikstra算法。
链路状态路由算法优点：没有慢收敛问题。
实用文档
5.2.6 层次路由
原理：路由器被划成了区域，每个路 由器知道如何将数据包路由到自己所 在区域内的目标地址，但是对于其他 区域的内部结构毫不知情，当不同的 网络相互连在一起，很自然地就会将 每个网络当做一个独立的区域，一个 网络中的路由器并不知道其他路由器 的拓扑结构。
沿汇集树（sink tree）生成树 （spann实i用n文档g tree）扩散
路由器收到广播分组，看到来那条路 径是否是用来给广播源发送分组的那 条线路，是，转发到其他所有线路上， 否则，丢弃。
逆向路径转发的优点：有效而且易于 实现。
实用文档