山东大学软件学院计算机网络知识总结第五章—网络层_计算机网络 山东大学

前导：网络层关注的是如何将源端数据包一路送到接收方。为了将数据包送到接收方，可能
沿途要经过许多跳（hop）中间路由器。这种功能显然与数据链路层的功能不同，数据链路
层的目标没那么宏伟，只是将帧从线路一边传送到另 边。因此 网络层是处理端到端数
据传输的最底层。

网络层为了顺利实现数据从一端到另一端传输必须知道网络的拓扑结构（即所有路由器和链路的集合），并从中选出适当的路径。同时要仔细选择路由器，避免某些路由器和通信线路负载过重，有些线路和路由器空闲。

一.网络层设计问题

1.存储转发数据包交换

网络中最主要的组件是 网络服务提供商（ISP) 的设备（通过传输线路连接的路由器〉和客户端设备，在图中ISP 的设备位于阴影椭圆内，而客户设备位于椭圆之外。

Internet网络层的数据传输要通过IP协议。

网络层提供给传输层的服务：向上提供的服务应该独立于路由器技术。应该向传输层屏蔽路由器的数量、类型和拓扑关系。传输层可用的网络地址应该有一个统一编址方案，甚至可以跨越 LAN和WAN。

a.无连接服务的实现

所有的数据包都被独立地注入到网络中，并且每个数据包独立路由，不需要提前建立任何设置。

在这样的上下文中，数据包通常称为数据报（datagram ），它类似于电报（telegram),对应的网络称为数据报网络（ datagram network ）。

上图解释：假设P1进程要发送一个很长的消息给P2。假设为最大数据包长度的4倍，所以网络层必须将消息拆分成4个数据包，1234。然后使用某种点到点协议发送给路由器A。这时ISP接管了这个传输任务。每个路由器有一个内部表，指明了目的地址以及下一跳。

存储转发: 在路由器A中数据包1,2,3到达之后经过验证校验和之后，被路由器暂时保存起来，然后根据A的路由表，将每一个数据包放到一个新的帧中，转发到新的通往C的出境链路。

然而，数据包4的情形有所不同。当它到达 之后，尽管它的目标地址也是指向 F,但它被A转发给了路由器 B。出于某种原因，A 决定采用不同于前三个数据包的路径来发送数据包 4。或许它了解到在 ACE 路径上发生了流量拥塞，因而更新了路由表。

管理这些路由表并做出路由选择的算法称为路由算法（ routing algorithm ）

IP 协议（ Internet Protocol ）是整个 Internet 的基础，它是无连接网络服务的重要范例。每个数据包携带一个目标 IP 地址，路由器使用该地址来单独转发每一个数据包。 IPv4 数据包的地址是 32 位， IPv6 数据包的地址是 128 位。

b.面向连接的服务的实现

发送数据包之前，必须首先建立起一条从源路由器到目标路由器之间的路径。这个连接称为虚电路 （VC， virtual circuit ），它类似于电话系统中建立的物理电路，对应的网络称为虚电路网络（ virtual-circuit network) 。

隐藏在虚电路背后的思想是避免为每个要发送的数据包选择一条新路径。

相反，当建立一个连接时，从源机器到目标机器之间的一条路径就被当作这个连接的一部分确定了下来，并且保存在这些中间路由器的表中。所有需要在这个连接上通过的流量，都使用这条路径，这与电话系统的工作方式完全一致。当连接被释放之后，虚电路也随之消失。在面向连接的服务中，每个数据包包含一个标识符，指明了它属于哪一条虚电路。

二.路由算法和路由协议

路由算法可以分为集中式路由算法和分布式路由算法。也可以分为静态路由算法和动态（自适应）路由算法。还可以有其它分类形式。
集中式路由算法一般要求有一个负责计算路由的中心节点，这个中心节点拥有全局网络信息，求解后的路由结果发送到其它节点。分布式路由算法中每个节点使用局部信息分别计算自己的路由。
静态路由算法是实现确定路由，路由确定后不再随着网络状态的变化而改变。动态（自适应）路由算法根据网络当前的情况“实时”确定路由。

路由算法根据网络状态计算路由时，需要了解网络的当前状态，这个状态也是路由算法使用的数据结构。这个结构的获得需要通过网络中路由节点之间交换信息获得，这些信息交换需要遵循一定的规则，属于路由协议。

路由算法（协议）属于网络层协议的一部分，一般驻留在节点的操作系统中。
虚电路路由只有在建立路径时才计算路径，在使用过程中不再改变，即使网络状态发生剧烈改变。
数据报路由“实时”的根据网络状态修改部分相关节点的路由，不同的数据包可能使用不同的路径。（在数据包传递过程中，路由算法根据当前网络状态修改了路由表）
“实时”一般采用周期性或重大改变触发式的计算路由表。或采用两者结合的方式。

1.路由算法

网络层的主要功能是将数据包从源机器路由到目标机器。在大多数网络中，数据包需要经过多跳 (hop )才能到达目的地。唯一一个值得指出的例外是广播网络，但即使在广播网络中，如果源机器和目标机器不在同一个网络段中时，路由仍然是一个问题。

路由算法（ routing algorithm ）是网络层软件的一部分，它负责确定一个入境数据包应该被发送到哪一条输出线路上。

如果网络内部使用了数据报，那么路由器必须针对每一个到达的数据包重新选择路径，因为自上一次选择了路径之后，最佳路径可能已经发生了改变。如果网络内部使用虚电路，那么只有当建立一条新的虚电路时，才需要做路由决策：此后，数据包只要沿着己经建立的路径向前传递即可。后一种情形有时候也称为会话路由(session routing ）。

路由和转发：

路由即对使用哪一条路径做出决策，而转发则是当一个数据包到达时该采取什么动作（被路由功能，如IPv4）。

可以把路由器想象成内部有两个进程：其中一个进程在每个数据包到达的时候对它进行处理，它在路由表中查找该数据包所对应的出境线路。这个进程即为转发( forwarding )进程 ;另一个进程负责生成和更新路由表，这正是路由算法发挥作用的地方。

优化原则：

最优路径的一般陈述如下 如果路由器J在从路由器I到路由器K的最优路径上，那么从J到K的最优路径也必定遵循同样的路由。

作为最优化原则的一个直接结果，从所有的源到一个指定目标的最优路径的集合构成了一棵以目标节点为根的树。这样的树称为汇集树（ sink tree ）。距离度量是跳数。

每个节点只知道自己和自己的邻居的信息。

汇集树分布式的存储在各个路由器中。

请注意，汇集树不一定是唯一的：有可能存在具有相同路径长度的其他汇集树。

如果我们允许选择所有可能的路径，则树就变成了更一般的结构，称为有向无环图（DAG)。

• 最优路径通常称为最短路径，可以使用不同的度量值或它们的组合来定义（依据优化目标）：

  跳数
  距离
  带宽
  平均流量
  通信成本
  平均延迟

a.泛洪算法：（flooding算法）

泛红算法技术将每一个入境数据包发送到除了该数据包到达的那条线路以外的每条出境线路。

优点：是一种最快的最可靠的数据传输算法。

缺点：泛洪法会产生大量的重复数据包。事实上，除非采取某些措施来抑制泛洪过程，否则将会产生无限多的数据包。其中一项措施是在每个数据包的头中设置一个跳计数器，每经过一跳该计数器减一，当计数器到达 时就丢弃该数据包。理想情况下，跳计数器的初始值应该等于从源端到接收方之间路径的长度。如果发送方不知道该路径有多长，它可以将计数器的初始值设置为最坏情形下的长度，即网络的直径。带有跳计数器的泛洪能够产生随着跳数增大而指数增长的重复数据包，而且路由器要复制以前已经看到过的数据包。

改进：抑制数据包泛滥的一种更好技术是让路由器跟踪己经泛洪过的数据包，从而避免第二次发送它们。实现这个目标的一种方式是让每个源路由器在接收来自主机的数据包时填上一个序号，然后每个路由器为每个源路由器准备一张表，记录己经观察到的来自源路由器的序号。如果入境数据包在这张表中，它就不能再被泛洪到其他路由器。

b.动态路由算法

每个路由器能够根据当前的网络状态（网络拓扑）计算从自己到所有其它路由器的最短路径。

动态路由算法也称为自适应路由算法，包含两个方面的内容：获得当前的网络状态，根据网络状态计算路由。

根据获得当前网络状态和计算最短路由的不同，常见的路由算法有：

• 距离矢量路由算法
• 链路状态路由算法
• 二者的混合

c.距离矢量路由算法（distance vector routing）也叫分布式Bellman-Ford路由算法

算法原理：每个路由器维护一张表（即一个矢量〉，表中列出了当前己知的到每个目标的最佳距离，以及所使用的链路。这些表通过邻居之间相互交换信息而不断被更新，最终每个路由器都了解到达每个目的地的最佳链路。
每个路由器维护一张路由表，以网络中每个路由器为索引，并且每个路由器对应一个表项。这个表项包含两部分，到达该路由器的首选出境线路，以及到达该路由器的距离估计值。

距离估计值的度量可以是跳数，或者传播延迟（路由器非常容易测出链路上的传播延迟，只需要给邻居发送一个特殊的ECHO数据包，邻居收到之后盖上时间戳发送回来即可）。

• 无穷计算问题：

  整个网络最佳路径的寻找过程称为收敛（ convergence ）。

  有一个严重的缺陷：虽然它总是能够收敛到正确的答案，但速度可能非常慢。

  尤其是，它对于好消息的反应非常迅速，而对于坏消息的反应异常迟缓。

d.链路状态路由算法（Link state routing）

导致距离适量算法退位的主要问题在于，当网络拓扑结构发生变化后距离矢量路由算法需要太长时间才能收敛到稳定状态。

因此，距离矢量路由算法被一个全新的算法所替代，该算法称为链路状态路由算法。

今天，链路状态路由算法的变种算法一IS-IS 或者 OSPF 己经成为大型网络或 Internet 应用最为广
泛的路由算法。

• 算法思想：
  • 1.发现自己的邻居节点，了解其网络地址。
  • 2.设置每个邻居节点的距离
  • 3.构造一个数据包，包含获得的所有链路信息
  • 4.将这个包发送给所有的路由器，并接受来自其他路由器的信息包。
  • 5.计算出到每个其他路由器的最短路径。

发现邻居：发送一个特殊的HELLO数据包，线路另一端的路由器应该返回一个应答，说明自己是谁，名字必须全局唯一。

设置链路成本：发送一个ECHO包，对方立即返回，通过往返时间除以2得到一个合理的延迟估算值。

构造链路数据包：一旦收集到了所需要的交换信息，每个路由器的下一步工作是构建一个包含所有这些信息的数据包。该数据包的内容首先是发送方的标识符，接着是一个序号（ Seq ）和年龄（Age），以及一个邻居列表，给出到每个邻居的延迟。

由于这个网络拓扑结构是一个无向图，因此存储会有一半的数据是冗余的。

一个节点得到其他所有节点的邻接信息就能构造出网络的拓扑图，这样就能通过最短路径算法计算出路由表表项。

构造链路数据包容易，难的是什么时候构造数据包。

两种做法：1.周期性构造2.触发时构造（比如一条线路断掉或者一个邻居节点停机，或重新恢复运行时。）

分发链路状态包：所有路由器必须快速并可靠地获得全部的链路状态数据包。

要解决数据不一致问题。

基本思路是使用泛洪法将链路状态数据包分发给所有路由器。为了控制泛洪规模，每个数据包都包含一个序号。需要随着每个数据包分发而逐一递增。路由器要记录他收到的所有（原路由器和序号）对。当一个新的链路状态数据包到达时，路由器检查这个新来的数据包是否己经出现在上
述观察到的列表中。如果这是一个新数据包，则把它转发到除入境线路之外的所有其他线路上。如果这是一个重复数据包，则将它丢弃。如果数据包的序号小于当前所看到过的来自该源路由器的最大序列号，则它将被当作过时数据包而拒绝接受，因为路由器己经有了更新的数据。
几个问题：

• 1.序号绕回问题：设置为32位序号
• 2.路由器崩溃，序号被破坏问题（比如数据错误但是未被校验出来）：在每个数据包的序号之后包含一个年龄(age ) 字段，并且每秒钟将年龄减 1。当年龄字段的值被减到0时，来自路由器的该信息将被丢弃。通常情况下，每隔一段时间，比如说 10 秒，一个新的数据包就会到来。在初始泛洪过程中，每个路由器也要递减 age 字段，这样可以确保没有数据包丢失，也不会无限制生存下去。
• 3.使算法更加健壮：加上序号，对数据包不立即转发而是放到一个等待传输队列中。这时再来一个相同的数据包，比较序号，丢弃重复的与老的数据包。并且为了防止丢包，每个链路状态数据包都要被确认。