文档介绍：网络层的作用:1、路由选择
2、网络互连
3、拥塞控制
4、为上层提供服务
网络层的主要功能是将分组从源机器路由到目标机器。完成路由选择的路由算法是网络层设计的最主要内容。
路由算法:它负责确定一个进来的分组应该被传送到哪一条输出线路上。
如果是数据报子网,将在每一个分组到达时作此决定
如果是虚电路子网,是在虚电路建立时决定,该连接上所有分组都将沿此线路传输
路由算法设计必须考虑的问题:正确性简单性健壮性稳定性公平性最优性
路由算法的原则:按照某种指标(传输延迟,所经过的站点数目等)找到一条从源节点到目标节点的较好路径。
路由算法
静态算法
最短路径算法
扩散法
自适应算法
距离矢量算法
链路状态算法
静态算法:不会根据当前测量或者估计的流量和拓扑结构,来调整它们的路由决策,所有的路由选择是预先在离线情况下计算好的,在网络启动的时候被下载到路由器中。
最短路径路由:
如图所示,图中的每个节点代表一台路由器,每条弧代表一条通信线路,线路上的数字是它的开销。现在我们想找到从A到D的最短路径。过程:
(1)节点A标记为永久节点,依次检查每一个与A相邻的节点,并检查它们与A之间的距离。
(2)如果新的标记距离小于该节点原来的标记,说明找到了一条更短路径,该节点需要重新标记,作为暂时性标记
(3)检查整个图中所有有暂时性标记的节点,使其中具有最小标记的那个节点成为永久节点,并且作为下一个工作节点。
(4)重复上述过程,直到没有新的永久节点为止。
如下图所示
2、扩散法:每一个进来的分组将被发送到除了它进来的那条线路之外的每一条输出线路上。
产生的问题:会产生大量的重复分组。
解决办法:
在数据包头设一个计数器初值,每经过一个节点自动减1,计数值为0 时,丢弃该数据包
在每个节点上建立登记表,则数据包再次经过时丢弃
缺点:重复数据包多,浪费带宽
优点:可靠性高,可用于并发数据库更新。极好的健壮性,可用于军事应用。常作为衡量标准,评价其它路由算法
现代计算机网络通常使用动态的路由算法(自适应算法),而不是上面介绍的静态路由算法,因为静态路由算法不会考虑到网络的当前负载情况。
自适应算法:随拓扑结构和流量的变化改变它们的路由决策,又称为动态路由算法。
距离矢量路由:每个路由器维护一张表(即一个矢量),表中列出了当前抑制的到每个目标的最佳距离,以及所使用的线路。通过邻居之间互相交换信息,路由器不断更新它们内部的表。
举例:
5
0
8
12
6
2
B
A
E
F
D
C
2
3
7
6
1
8
5
4
延迟信息B
B
D
E
C
线路
A
5
16
7
11
B
B
0
12
6
6
B
C
8
6
3
0
-
D
12
0
9
3
D
E
6
9
0
5
E
F
2
10
4
8
B
缺点:交换的路径信息量大;路径信息不一致;坏消息收敛速度慢;不适合大型网络。
坏消息传播慢的原因:无穷计算问题。
A
B
C
D
E
 
 
 
 
 
 
 
∞
∞
∞
∞
初始时
 
1
∞
∞
∞
第1次交换后
 
1
2
∞