第五章 网络层 (1)
5.1 电路交换和分组交换
5.2 虚电路和数据报
5.3 路由选择网络层
OSI参考模型中的第三层，在数据链路层提供的服务基础上，将数据从源端经过若干中间节点传送到目的段。
如何选择合适的路径把数据从源端传送到目的端？
路由选择的功能电路交换和分组交换
通信网络包括广播通信网络和交换网
交换通信网络：电路交换和分组交换
C
2
D
E
F
31
4 6
5
7
B
A
＝ 端系统
＝ 通信网络节点图 5.1 简单交换网络
电路交换：
电路建立,A和 F间建立电路
数据传输：通过建立的电路传输数据
电路释放：任一方发起，释放资源分组交换
分组交换：
数据以分组方式传输，分组包括控制信息
分组的传送采用存储转发方式
分组的传递根据控制信息来进行路径选择
分组交换：多个站点共享网络资源虚电路和数据报
分组交换网中,虚电路和数据报
通信子网向端系统提供服务
通信子网内部的操作方式
通信子网内部的操作方式
虚电路方式
数据传输前建立一条逻辑的通道，和电路类似
,虚,电路：分组仍然进行存储转发
每个节点维护一个虚电路表：虚电路号、上一个节点和下一个节点虚电路方式（ 1）
动态虚电路机制：参见图 5.1
每个节点独立选择虚电路号，局部标识
站点 A选择最低虚电路号 N(A)，呼叫请求分组
节点 4从 4和 5之间未用的虚电路号选择,N(4)，
替换原来的虚电路号。 …,.
虚电路所跨越的每段的虚电路号唯一。
虚电路表：两个虚电路号，前一节点选取的虚电路号和本节点选取的虚电路号虚电路方式（ 2）
动态虚电路机制：数据传输是双向的
考虑两条虚电路：
A-4-5-6-F：节点 4选择 4和 5间未用的虚电路号
D-3-5-4-A：节点 5选择 5和 4间未用的虚电路号
都相等 (N)时会带来问题：
节点 5从 4-5线路上收到一个虚电路号为 N的分组，有可能是
A-4-5-6-F虚电路上的正向分组
D-3-5-4-A虚电路上的反向分组
解决方法：节点 5选择 (第 2条 )虚电路号时还要考虑与下一节点 4在另一条虚电路中作为上一节点时使用的虚电路号（ 5能够从虚电路表中知道从 4来的虚电路号）不同
C
2
D
E
F
3
1
4 6
5
7
B
A
＝ 端系统
＝ 通信网络节点图 5.1 简单交换网络数据报方式
数据报的传递是单独处理的，无需建立连接
数据报包括控制信息：目的地址
数据报经过的路径可能会各不相同，可能会丢失、延迟、失序。
虚电路子网和数据报子网比较数据报子网 虚电路子网延时 分组传输延时 电路建立,分组传输延时路由选择 每个分组单独选择路由 建立虚电路时选择路由,以后所有分组都使用该路由状态信息 子网无需保存状态信息 每个节点要保存一张虚电路表地址 每个分组包括源端和目的端的完整地址每个分组含有一个短的虚电路号节点失败的影响除了在崩溃时正在由该节点处理的分组都丢失外,无其他影响所有经过失效节点的虚电路都要被终止拥塞控制难如果有足够的缓冲区分配给已建立的虚电路,则容易控制网络层提供的服务（ 1）
设计目标
服务与通信子网的技术无关。
通信子网的数量、类型和拓扑结构对运输层透明
网络地址应该采用统一的编码方式
有连接和无连接方式服务的争论：
复杂的功能放在哪一层？
网络层提供的服务（ 2）
面向连接的服务：
运输层要求建立网络连接，源端向网络节点发出呼叫请求；
在目地端，网络节点向端系统的网络层发送呼叫分组，网络层向运输层发出连接指示。
通信子网内部可以使用虚电路或数据报方式
虚电路方式,ATM的 AAL1
数据报方式：通信子网内部为数据报方式，与端系统相连的网络节点向端系统提供面向连接方式,
无连接方式的服务：
数据报子网,UDP over IP
虚电路子网,IP over ATM
理想路由算法的基本特性（ 1）
基本特性,
正确：满足用户的业务需求
简单：节点和通信负载
健壮：网络的运行尽可能不要中断
稳定：对网络状态变化的反应恰到好处
公平：全局效率和局部的公平性的平衡
最优：优化什么？ 减少分组经过的站点数
高效：带来的处理开销应该小于带来的好处理想路由算法的基本特性（ 2）
公平和最优经常是矛盾的理想路由算法的基本特性（ 3）
技术要素,
性能标准 跳段数 /花费 /延迟 /吞吐量路由选择时机 数据报 /虚电路路由判决地点 每个节点 （ 分布式 ） /中心节点 （ 集中式 ） /始发节点 （ 源 ）
网络信息来源 无来源 /本地 /相邻节点 /路由中的节点 /所有节点路由选择策略 静态策略 /动态策略网络信息更新时间 连续更新 /定期更新 /显著负载变化 /
拓扑变化扩散 Flooding（ 1）
一个网络节点从某条输入线路收到一个分组之后，把该分组从除了分组到来的线路外的所有其他输出线路上发出扩散 Flooding（ 2）
可以用于健壮性要求很高的场合，但也会产生大量的重复分组
每个分组头部包含一计数器，每个接收到该分组的节点将该字段减 1，如果计数器值为 0，扔掉该分组。
另一种方法是记录下分组扩散的路径，防止它第二次再扩散到已扩散过的路径中。
最后一种方法为选择扩散法。节点并不是简单地向所有其他节点转发分组，而是选择那些很可能向目的节点的方向去的节点。这里考虑的方向可以是地理上的方向，也可以是网络拓扑中的大致方向
扩散可被用来分发信息、判断可达性、找到最短路径静态策略：固定路由（ 1）
固定路由选择：
预先计算出每对节点间的最佳路由，然后每个节点构造一个固定的路由表。
路由表中包括：目的节点＋下一个节点 Hop
最优原理：
如果节点 A到节点 B的最优路由经过了节点 C，则该路由上的 A到 C和 C到 B分别也是节点 A和节点 C、
节点 C和节点 B的最优路由静态策略：固定路由（ 2）
拓扑图：节点表示网络节点，边表示通信线路，线路上有一个权值，给出线路的性能度量
权值的确定：根据距离、信道带宽、平均通信量、平均队列长度、延迟等
最优路由：两个节点间所有可能路由中具有最小花费的那条路由。
静态策略：固定路由（ 3）
Dijkstra算法：
N=网络中所有节点的集合,S＝源节点
M＝已由算法归并的节点的集合
L(i,j)=节点 i与 j之间链路的权值
C(n)：算法求得的当前从 S到 n的最小花费
基本思想：不断找出一些中间节点归并入 M，
这些中间节点到源节点的最优路由已经确定，
算法直到 M=N时结束静态策略：固定路由（ 4）
Dijkstra算法：
1.初始化,M={S},C(n) = L(s,n)
2,从不在 M的相邻节点中寻找 使得把 w归并入 M中
3.更新最小花费路径,
Mw?
)(m in)( jCwC Mj
Mn )],()(),(m i n [)( 对所有nwLnCnCnC
A
B C
DE F
G H
2
7
3
2
2
3
22
4
6
1
E(?,-) F(?,-)
D((?,1)
A
B C
DE F
G H
A
B(2,A) C(?,-)
D(?,-)
G(6,A) H(?,-)
2
7
32
2
3
22
46
A
B(2,A) C(9,B)
E(4,B)
F(6,E)
G(5,E)
A
C(9,B)
D(?,-)E(4,B)
F(?,-)
G(6,A) H H(?,-)
B(2,A)
(a) (b)
(c) (d)
静态策略
固定路由：冗余路由，概率数
随机路由选择：随机选择一条输出线路
基于流量的路由选择：考虑网络的负载和拓扑结构
参看前面补充的第二章网络拓扑性能分析的内容
假设：网络中每对节点间的平均负载是相当稳定、可以预测的，即能预先估计 i到 j的平均通信量
拓扑结构已知
通信量矩阵 Fij
容量矩阵 Cij
基本思想：在上述已知条件下，我们可以计算出整个网络的平均分组延迟。路由选择问题归结为如何找出最接近平均分组延迟的路由选择算法。
动态策略
节点的路由选择根据网络的当前状态信息决定，以适应网络流量、拓扑的变化
动态策略：
可能会增加节点的处理负担
增加网络的负载
算法的收敛性：过快、过慢？
网络状态信息的来源划分：孤立、集中、
分布路由选择动态策略：孤立路由选择
孤立路由选择：本地信息来选择路由
队列长度：
所有输出队列中最短的线路
与固定路由结合：首先找到正确方向的那些路由，
这些路由分配权值，根据队列长度＋权值来选择
逆向学习法：
如果节点收到过来自于某个节点的分组，则能够了解到它到该节点的距离，一段时间后，学习到到其他节点的最短路径
定期刷新，重新学习动态策略：集中路由选择
集中路由选择：
每个节点定期发送状态信息给路由控制中心
RCC,RCC利用这些信息计算每对节点之间的最优路径，分发给每个节点
RCC成为瓶颈，路由表分发过程中的不一致
δ 路由选择,RCC计算出 k条等价的路径，
分发给各个节点, 1ijLij CC
动态策略：分布路由选择
分布路由选择：
相邻节点交换路由信息
距离向量路由和链路状态路由
距离向量路由：
递归、分布式的路由计算方法，每个节点只知道直接连接的链路花费。
根据从相邻节点了解到的到目的地的路径花费来计算。
链路状态路由：
每个节点了解全局网络的拓扑和链路花费。
每个节点最初知道相邻链路的负载情况，并且扩散给网络中的所有节点距离向量路由（ 1）
距离向量路由
Assume：每个路由器只了解邻居的位置和花费
Goal,每个路由器计算到每个目的地的下一跳段信息
Idea：告诉邻居节点其学习到的至所有目的地距离
Bellman-Ford算法
每个路由器维护一个路由表，给出了到所有目的地的路径花费和下一个跳段：初始为到邻居的花费，其它目的地为
infinity
路由器定期发送距离向量（到所有目的地）给邻居路由器
如果从邻居收到路由信息，发现通过邻居到某个目的地的路由更好，则更新相应的路由表项：
距离向量路由（ 2）
在收到路由更新消息时
以前没有到该目的地的路由，新增,
到目的地 Z的路由经过 Y转发，距离为 C(x,y)+D(y,z)
以前有到目的地的路由，并且下一跳段也正好是该邻居，
则更新路径花费
比较是否新的路径要更短，如果是，则更新表项
C(x,y) + D(y,z) < D(x,z)
路由表中的每个表项有一个计时，如果过时则从表中移走。
如果路径花费不再改变，慢慢算法收敛。
X Y Z
距离向量路由（ 3）
无穷计数问题：
好消息的传播迅速，但是坏消息的传播缓慢
好消息意味着一条更好的路径，很快被相邻路由器知道，并且更新相应路由表，再通知给其它路由器。
坏消息则不然：
一个例子,A/B是两个相邻路由器，数字为到
Internet的路径花费距离向量路由（ 4）
无穷计数问题：
B到 Internet的链路断开,A发送给 B的更新消息中有一条到 Internet的距离为 2的路由
B更新到 Internet的路由为经 A、距离 3
A收到 B的更新消息，更新路径为 4
B收到 A的更新消息，更新路径为 5
……,直到距离达到 Infinity
无穷计数
水平分割,Split-Horizon
不要把从某个接口了解到的路由信息再通过该接口传递给其他路由器。
即如果 A到某个目的地 D的路由要经过邻居 B，
则 A向 B发送的更新消息不会包含到 D的路由
对三个节点以上路由回路无能为力
A
B
C D
链路状态路由算法
SPF：链路状态最短路由优先算法
基本思想：
每个路由器都了解整个网络的拓扑信息，从而按照 Dijkstra算法计算出到每个目的地的最短路由
如何知道整个网络的拓扑信息？
节点了解它相邻的节点，以及所有邻居节点的状态
定期把链路状态信息传播给所有其他路由器链路状态路由算法：邻居发现
HELLO协议：回应 Router ID
k-out-of-n方法：为了测试某种状态，如果 n
次测试中有 k次满足，则认为该状态满足
广播网络用一个网络节点来描述链路状态路由算法：链路花费
链路花费：
发一个分组，邻居节点响应，分组来回的时间 /2为链路延迟
测量延迟时是否考虑负载因素：排队还是队头？
考虑负载因素：
负载均衡
可能产生不稳定路由链路状态路由算法：扩散
链路状态信息的分发：
扩散法：
路由分组包括顺序号，节点记录最新收到的来自于各个节点的最大顺序号
过时、重复的信息丢弃，新的信息被扩散
顺序号重复使用，并且路由器可能崩溃
解决方法：
32比特的顺序号
增加一个计时字段：丢弃过时的路由器信息链路状态路由算法：扩散
节点间的路由信息交换采用确认机制
收到路由分组后不是马上扩散，而是等待一段时间，丢弃这段时间来的重复和过时的分组，减少负载开销
路由器从 X收到 S的 LSP时
如果顺序号更新，则接受，增加 S的状态，设置 ACK X，设置 Send给其它路由器
如果更老，则忽略
如果相等，则设置 ACK X，清楚 SEND X
轮流扫描 ACK和 SEND标志，发送实际的报文层次路由
网络规模很大时，将网络分成若干个区域，各个区域内的节点只考虑本区域内的路由，而区域之间的路由选择由各个区域中某几个节点负责完成
100个节点分成 10个区域，每个区域内有 10个节点，
每个节点路由表项为 10＋ 10＝ 20，而不是 100
Kamoun和 Kleinrock结论：理论上将 N个节点分成 m个层次，最佳的分层方法是使每个节点存放的信息：
m Nmmf?)(
习题
5.5
5.7
5.8
5.1 电路交换和分组交换
5.2 虚电路和数据报
5.3 路由选择网络层
OSI参考模型中的第三层，在数据链路层提供的服务基础上，将数据从源端经过若干中间节点传送到目的段。
如何选择合适的路径把数据从源端传送到目的端？
路由选择的功能电路交换和分组交换
通信网络包括广播通信网络和交换网
交换通信网络：电路交换和分组交换
C
2
D
E
F
31
4 6
5
7
B
A
＝ 端系统
＝ 通信网络节点图 5.1 简单交换网络
电路交换：
电路建立,A和 F间建立电路
数据传输：通过建立的电路传输数据
电路释放：任一方发起，释放资源分组交换
分组交换：
数据以分组方式传输，分组包括控制信息
分组的传送采用存储转发方式
分组的传递根据控制信息来进行路径选择
分组交换：多个站点共享网络资源虚电路和数据报
分组交换网中,虚电路和数据报
通信子网向端系统提供服务
通信子网内部的操作方式
通信子网内部的操作方式
虚电路方式
数据传输前建立一条逻辑的通道，和电路类似
,虚,电路：分组仍然进行存储转发
每个节点维护一个虚电路表：虚电路号、上一个节点和下一个节点虚电路方式（ 1）
动态虚电路机制：参见图 5.1
每个节点独立选择虚电路号，局部标识
站点 A选择最低虚电路号 N(A)，呼叫请求分组
节点 4从 4和 5之间未用的虚电路号选择,N(4)，
替换原来的虚电路号。 …,.
虚电路所跨越的每段的虚电路号唯一。
虚电路表：两个虚电路号，前一节点选取的虚电路号和本节点选取的虚电路号虚电路方式（ 2）
动态虚电路机制：数据传输是双向的
考虑两条虚电路：
A-4-5-6-F：节点 4选择 4和 5间未用的虚电路号
D-3-5-4-A：节点 5选择 5和 4间未用的虚电路号
都相等 (N)时会带来问题：
节点 5从 4-5线路上收到一个虚电路号为 N的分组，有可能是
A-4-5-6-F虚电路上的正向分组
D-3-5-4-A虚电路上的反向分组
解决方法：节点 5选择 (第 2条 )虚电路号时还要考虑与下一节点 4在另一条虚电路中作为上一节点时使用的虚电路号（ 5能够从虚电路表中知道从 4来的虚电路号）不同
C
2
D
E
F
3
1
4 6
5
7
B
A
＝ 端系统
＝ 通信网络节点图 5.1 简单交换网络数据报方式
数据报的传递是单独处理的，无需建立连接
数据报包括控制信息：目的地址
数据报经过的路径可能会各不相同，可能会丢失、延迟、失序。
虚电路子网和数据报子网比较数据报子网 虚电路子网延时 分组传输延时 电路建立,分组传输延时路由选择 每个分组单独选择路由 建立虚电路时选择路由,以后所有分组都使用该路由状态信息 子网无需保存状态信息 每个节点要保存一张虚电路表地址 每个分组包括源端和目的端的完整地址每个分组含有一个短的虚电路号节点失败的影响除了在崩溃时正在由该节点处理的分组都丢失外,无其他影响所有经过失效节点的虚电路都要被终止拥塞控制难如果有足够的缓冲区分配给已建立的虚电路,则容易控制网络层提供的服务（ 1）
设计目标
服务与通信子网的技术无关。
通信子网的数量、类型和拓扑结构对运输层透明
网络地址应该采用统一的编码方式
有连接和无连接方式服务的争论：
复杂的功能放在哪一层？
网络层提供的服务（ 2）
面向连接的服务：
运输层要求建立网络连接，源端向网络节点发出呼叫请求；
在目地端，网络节点向端系统的网络层发送呼叫分组，网络层向运输层发出连接指示。
通信子网内部可以使用虚电路或数据报方式
虚电路方式,ATM的 AAL1
数据报方式：通信子网内部为数据报方式，与端系统相连的网络节点向端系统提供面向连接方式,
无连接方式的服务：
数据报子网,UDP over IP
虚电路子网,IP over ATM
理想路由算法的基本特性（ 1）
基本特性,
正确：满足用户的业务需求
简单：节点和通信负载
健壮：网络的运行尽可能不要中断
稳定：对网络状态变化的反应恰到好处
公平：全局效率和局部的公平性的平衡
最优：优化什么？ 减少分组经过的站点数
高效：带来的处理开销应该小于带来的好处理想路由算法的基本特性（ 2）
公平和最优经常是矛盾的理想路由算法的基本特性（ 3）
技术要素,
性能标准 跳段数 /花费 /延迟 /吞吐量路由选择时机 数据报 /虚电路路由判决地点 每个节点 （ 分布式 ） /中心节点 （ 集中式 ） /始发节点 （ 源 ）
网络信息来源 无来源 /本地 /相邻节点 /路由中的节点 /所有节点路由选择策略 静态策略 /动态策略网络信息更新时间 连续更新 /定期更新 /显著负载变化 /
拓扑变化扩散 Flooding（ 1）
一个网络节点从某条输入线路收到一个分组之后，把该分组从除了分组到来的线路外的所有其他输出线路上发出扩散 Flooding（ 2）
可以用于健壮性要求很高的场合，但也会产生大量的重复分组
每个分组头部包含一计数器，每个接收到该分组的节点将该字段减 1，如果计数器值为 0，扔掉该分组。
另一种方法是记录下分组扩散的路径，防止它第二次再扩散到已扩散过的路径中。
最后一种方法为选择扩散法。节点并不是简单地向所有其他节点转发分组，而是选择那些很可能向目的节点的方向去的节点。这里考虑的方向可以是地理上的方向，也可以是网络拓扑中的大致方向
扩散可被用来分发信息、判断可达性、找到最短路径静态策略：固定路由（ 1）
固定路由选择：
预先计算出每对节点间的最佳路由，然后每个节点构造一个固定的路由表。
路由表中包括：目的节点＋下一个节点 Hop
最优原理：
如果节点 A到节点 B的最优路由经过了节点 C，则该路由上的 A到 C和 C到 B分别也是节点 A和节点 C、
节点 C和节点 B的最优路由静态策略：固定路由（ 2）
拓扑图：节点表示网络节点，边表示通信线路，线路上有一个权值，给出线路的性能度量
权值的确定：根据距离、信道带宽、平均通信量、平均队列长度、延迟等
最优路由：两个节点间所有可能路由中具有最小花费的那条路由。
静态策略：固定路由（ 3）
Dijkstra算法：
N=网络中所有节点的集合,S＝源节点
M＝已由算法归并的节点的集合
L(i,j)=节点 i与 j之间链路的权值
C(n)：算法求得的当前从 S到 n的最小花费
基本思想：不断找出一些中间节点归并入 M，
这些中间节点到源节点的最优路由已经确定，
算法直到 M=N时结束静态策略：固定路由（ 4）
Dijkstra算法：
1.初始化,M={S},C(n) = L(s,n)
2,从不在 M的相邻节点中寻找 使得把 w归并入 M中
3.更新最小花费路径,
Mw?
)(m in)( jCwC Mj
Mn )],()(),(m i n [)( 对所有nwLnCnCnC
A
B C
DE F
G H
2
7
3
2
2
3
22
4
6
1
E(?,-) F(?,-)
D((?,1)
A
B C
DE F
G H
A
B(2,A) C(?,-)
D(?,-)
G(6,A) H(?,-)
2
7
32
2
3
22
46
A
B(2,A) C(9,B)
E(4,B)
F(6,E)
G(5,E)
A
C(9,B)
D(?,-)E(4,B)
F(?,-)
G(6,A) H H(?,-)
B(2,A)
(a) (b)
(c) (d)
静态策略
固定路由：冗余路由，概率数
随机路由选择：随机选择一条输出线路
基于流量的路由选择：考虑网络的负载和拓扑结构
参看前面补充的第二章网络拓扑性能分析的内容
假设：网络中每对节点间的平均负载是相当稳定、可以预测的，即能预先估计 i到 j的平均通信量
拓扑结构已知
通信量矩阵 Fij
容量矩阵 Cij
基本思想：在上述已知条件下，我们可以计算出整个网络的平均分组延迟。路由选择问题归结为如何找出最接近平均分组延迟的路由选择算法。
动态策略
节点的路由选择根据网络的当前状态信息决定，以适应网络流量、拓扑的变化
动态策略：
可能会增加节点的处理负担
增加网络的负载
算法的收敛性：过快、过慢？
网络状态信息的来源划分：孤立、集中、
分布路由选择动态策略：孤立路由选择
孤立路由选择：本地信息来选择路由
队列长度：
所有输出队列中最短的线路
与固定路由结合：首先找到正确方向的那些路由，
这些路由分配权值，根据队列长度＋权值来选择
逆向学习法：
如果节点收到过来自于某个节点的分组，则能够了解到它到该节点的距离，一段时间后，学习到到其他节点的最短路径
定期刷新，重新学习动态策略：集中路由选择
集中路由选择：
每个节点定期发送状态信息给路由控制中心
RCC,RCC利用这些信息计算每对节点之间的最优路径，分发给每个节点
RCC成为瓶颈，路由表分发过程中的不一致
δ 路由选择,RCC计算出 k条等价的路径，
分发给各个节点, 1ijLij CC
动态策略：分布路由选择
分布路由选择：
相邻节点交换路由信息
距离向量路由和链路状态路由
距离向量路由：
递归、分布式的路由计算方法，每个节点只知道直接连接的链路花费。
根据从相邻节点了解到的到目的地的路径花费来计算。
链路状态路由：
每个节点了解全局网络的拓扑和链路花费。
每个节点最初知道相邻链路的负载情况，并且扩散给网络中的所有节点距离向量路由（ 1）
距离向量路由
Assume：每个路由器只了解邻居的位置和花费
Goal,每个路由器计算到每个目的地的下一跳段信息
Idea：告诉邻居节点其学习到的至所有目的地距离
Bellman-Ford算法
每个路由器维护一个路由表，给出了到所有目的地的路径花费和下一个跳段：初始为到邻居的花费，其它目的地为
infinity
路由器定期发送距离向量（到所有目的地）给邻居路由器
如果从邻居收到路由信息，发现通过邻居到某个目的地的路由更好，则更新相应的路由表项：
距离向量路由（ 2）
在收到路由更新消息时
以前没有到该目的地的路由，新增,
到目的地 Z的路由经过 Y转发，距离为 C(x,y)+D(y,z)
以前有到目的地的路由，并且下一跳段也正好是该邻居，
则更新路径花费
比较是否新的路径要更短，如果是，则更新表项
C(x,y) + D(y,z) < D(x,z)
路由表中的每个表项有一个计时，如果过时则从表中移走。
如果路径花费不再改变，慢慢算法收敛。
X Y Z
距离向量路由（ 3）
无穷计数问题：
好消息的传播迅速，但是坏消息的传播缓慢
好消息意味着一条更好的路径，很快被相邻路由器知道，并且更新相应路由表，再通知给其它路由器。
坏消息则不然：
一个例子,A/B是两个相邻路由器，数字为到
Internet的路径花费距离向量路由（ 4）
无穷计数问题：
B到 Internet的链路断开,A发送给 B的更新消息中有一条到 Internet的距离为 2的路由
B更新到 Internet的路由为经 A、距离 3
A收到 B的更新消息，更新路径为 4
B收到 A的更新消息，更新路径为 5
……,直到距离达到 Infinity
无穷计数
水平分割,Split-Horizon
不要把从某个接口了解到的路由信息再通过该接口传递给其他路由器。
即如果 A到某个目的地 D的路由要经过邻居 B，
则 A向 B发送的更新消息不会包含到 D的路由
对三个节点以上路由回路无能为力
A
B
C D
链路状态路由算法
SPF：链路状态最短路由优先算法
基本思想：
每个路由器都了解整个网络的拓扑信息，从而按照 Dijkstra算法计算出到每个目的地的最短路由
如何知道整个网络的拓扑信息？
节点了解它相邻的节点，以及所有邻居节点的状态
定期把链路状态信息传播给所有其他路由器链路状态路由算法：邻居发现
HELLO协议：回应 Router ID
k-out-of-n方法：为了测试某种状态，如果 n
次测试中有 k次满足，则认为该状态满足
广播网络用一个网络节点来描述链路状态路由算法：链路花费
链路花费：
发一个分组，邻居节点响应，分组来回的时间 /2为链路延迟
测量延迟时是否考虑负载因素：排队还是队头？
考虑负载因素：
负载均衡
可能产生不稳定路由链路状态路由算法：扩散
链路状态信息的分发：
扩散法：
路由分组包括顺序号，节点记录最新收到的来自于各个节点的最大顺序号
过时、重复的信息丢弃，新的信息被扩散
顺序号重复使用，并且路由器可能崩溃
解决方法：
32比特的顺序号
增加一个计时字段：丢弃过时的路由器信息链路状态路由算法：扩散
节点间的路由信息交换采用确认机制
收到路由分组后不是马上扩散，而是等待一段时间，丢弃这段时间来的重复和过时的分组，减少负载开销
路由器从 X收到 S的 LSP时
如果顺序号更新，则接受，增加 S的状态，设置 ACK X，设置 Send给其它路由器
如果更老，则忽略
如果相等，则设置 ACK X，清楚 SEND X
轮流扫描 ACK和 SEND标志，发送实际的报文层次路由
网络规模很大时，将网络分成若干个区域，各个区域内的节点只考虑本区域内的路由，而区域之间的路由选择由各个区域中某几个节点负责完成
100个节点分成 10个区域，每个区域内有 10个节点，
每个节点路由表项为 10＋ 10＝ 20，而不是 100
Kamoun和 Kleinrock结论：理论上将 N个节点分成 m个层次，最佳的分层方法是使每个节点存放的信息：
m Nmmf?)(
习题
5.5
5.7
5.8
