考研笔记-计算机之计算机网络:网络层关键算法“表”述

表-各层协议的关键算法

协议层

协议算法

算法实现

网络层

主机和路由器ARP算法

ARP对象的确定过程：

1) 若发送方是主机，且要将IP数据报发送到本网络上的另一主机，这时用ARP找到目的主机的MAC地址；

2) 若发送方是主机，且要将IP数据报发送到另一网络上的一个主机，这时用ARP找到本网络上的一个路由器的MAC地址，剩下的工作由该路由器来完成；

3) 若发送方是路由器，且要将IP数据报发送到本网络上的一个主机，这时用ARP找到目的主机的MAC地址；

4) 若发送方是路由器，且要将IP数据报发送到另一网络上的一个主机，这时用ARP找到本网络上的一个路由器的MAC地址，剩下的工作由该路由器来完成。

说明：

1) 以上算法中的目的IP均为主机（其实也可以为路由器）；

2) ARP只能找到本网上的主机或路由器的MAC地址；

3) 以上ARP对象的确定是由发送方自行确定的，即通过判断目的主机与自身是否处于同一网络来确定ARP的对象是本网络上的主机还是路由器；

ARP地址的解析过程：

主机A的IP地址为192.168.1.1，MAC地址为0A-11-22-33-44-01；

主机B的IP地址为192.168.1.2，MAC地址为0A-11-22-33-44-02；

当主机A要与主机B通信时，地址解析协议可以将主机B的IP地址（192.168.1.2）解析成主机B的MAC地址，以下为工作流程：

1) 根据主机A上的路由表内容，IP确定用于访问主机B的转发IP地址是192.168.1.2。然后A主机在自己的本地ARP缓存中检查主机B的匹配MAC地址。

2) 如果主机A在ARP缓存中没有找到映射，它将询问192.168.1.2的硬件地址，从而将ARP请求分组广播到本地网络上的所有主机。源主机A的IP地址和MAC地址都包括在ARP请求分组中。本地网络上的每台主机都接收到ARP请求并且检查是否与自己的IP地址匹配。如果主机发现请求的IP地址与自己的IP地址不匹配，它将丢弃ARP请求。

3) 主机B确定ARP请求中的IP地址与自己的IP地址匹配，则将主机A的IP地址和MAC地址映射添加到本地ARP缓存中。

4) 主机B将包含其MAC地址的ARP响应分组直接（单播）发送回主机A。

5) 当主机A收到从主机B发来的ARP响应时，会用主机B的IP和MAC地址映射更新ARP缓存。本机缓存是有生存期的，生存期结束后，将再次重复上面的过程。主机B的MAC地址一旦确定，主机A就能向主机B发送IP通信了。

说明：

1) ARP请求分组的以广播形式发送，ARP响应分组以单播形式发送。

2) ARP只能对连接在同一个网络上的主机或路由器进行地址解析。当使用ARP对不属于同一网络的某个IP地址进行解析时，得到的ARP响应分组中的源MAC地址（即解析结果）实际是转发该ARP响应分组的路由器的MAC地址。

路由器的分组转发算法（用于使用路由表）

分类编址IP的分组转发算法：（目的网络由目的地址即可确定）

1) 提取目的网络地址。从IP数据报的首部提取目的IP地址D，根据目的IP的网络类别位提取出目的网络地址N；

2) 直接交付。若N是与此路由器直接相连的某个网络地址，则进行直接交付，即直接把数据报交付给目的主机（包括把目的主机的IP地址D转换为具体的MAC地址，把数据报封装为MAC帧，再发送此帧）；否则执行3)；

3) 特定主机路由。若路由表中有目的地址为D的特定主机路由，则把数据报传送给路由表中所指明的下一跳路由器；否则执行4)；

4) 指定网络路由。若路由表中有到达网络N的路由，则把数据报传送给路由表中所指明的下一跳路由器；否则执行5)；

5) 默认路由。若路由表中有一个默认路由，则把数据报传送给路由表中所指明的默认路由器；否则执行6)；

6) 出错。报告转发分组出错。

划分子网IP的分组转发算法：（目的网络由目的地址和各个网络的子网掩码与其网络地址共同确定）

1) 提取目的IP地址。从IP数据报的首部提取目的IP地址D；

2) 直接交付。对与此路由器直接相连的网络逐个进行检查：用各网络的子网掩码和目的IP地址D逐位相与，若结果和相应的网络地址匹配，则进行直接交付，即直接把数据报交付给目的主机（包括把目的主机的IP地址D转换为具体的MAC地址，把数据报封装为MAC帧，再发送此帧）；否则执行3)；

3) 特地主机路由。若路由表中有目的地址为D的特定主机路由，则把数据报传送给路由表中所指明的下一跳路由器；否则执行4)；

4) 指定网络路由。对路由表中的每一项（行），用其中的子网掩码和IP地址D相与，若结果和该行的目的网络地址相匹配，则把数据报传送给路由表中该行所指明的下一跳路由器；否则执行5)；

5) 默认路由。若路由表中有一个默认路由，则把数据报传送给路由表中所指明的默认路由器；否则执行6)；

6) 出错。报告转发分组出错。

CIDR IP的分组转发算法：（目的网络由目的地址和各个网络的网络前缀共同确定）

1) 提取目的IP地址。从IP数据报的首部提取目的IP地址D；

2) 直接交付。对与此路由器直接相连的网络逐个进行检查：用各网络的地址掩码和目的IP地址D逐位相与，若结果和相应的网络地址匹配，则进行直接交付，即直接把数据报交付给目的主机（包括把目的主机的IP地址D转换为具体的MAC地址，把数据报封装为MAC帧，再发送此帧）；否则执行3)；

3) 特地主机路由。若路由表中有目的地址为D的特定主机路由，则把数据报传送给路由表中所指明的下一跳路由器；否则执行4)；

4) 指定网络路由。使用最长前缀匹配方法判断目的网络是否在路由表中（使用二叉线索（类似霍夫曼编码）查找路由表：与唯一前缀匹配找到可能的目的网络前缀，与网络前缀匹配确定最终的目的网络），若目的网络在路由表中，则把数据报传送给路由表中目的网络所在项目所指明的下一跳路由器；否则执行5)；

5) 默认路由。若路由表中有一个默认路由，则把数据报传送给路由表中所指明的默认路由器；否则执行6)；

6) 出错。报告转发分组出错。

说明：

1) 由于一个CIDR地址块中有很多地址，所以在路由表中就利用CIDR地址块来查找目的网络，这种地址聚合称为路由聚合，路由聚合使得路由表中的一个项目可以表示原来传统分类地址的很多个路由（即把目的网络的网络前缀具有公共前缀，且下一跳IP地址相同的多个路由聚合为一个下一跳IP地址保持不变，但目的网络的网络前缀变为参与聚合的目的网络的网络前缀的公共前缀的路由），路由聚合也称为构成超网

2) 三类分组转发算法的流程框架相同，唯一的区别是确定目的网络的方法不同；

RIP距离向量算法（用于构造路由表）

对每一个相邻路由器发送过来的RIP报文，进行以下步骤：

1) 修改。对地址为X的相邻路由器发来的RIP报文，先修改此报文中的所有项目：把“下一跳”字段中的地址都改为X，把所有的“距离”字段的值加1。每一个项目都有三个关键数据，即：“（到目的网络N，距离（跳数）是d，下一跳路由器是X）”。

2) 对修改后的RIP报文中的每一个项目“（目的网络N，距离（跳数）d，下一跳路由器X）”，进行以下步骤：

a) 添加。若原来的路由表中没有目的网络N，则把该项目添加到路由表中，否则（即在路由表中有目的网络N）执行b)；

b) 更新。若下一跳路由器地址是X，则用收到的项目替换原路由表中的项目（以最新的消息为准），否则（即这个项目是：到目的网络N，但下一跳路由器不是X）执行c)；

c) 择优。若收到的项目中的距离d小于路由表中的距离，则进行更新（选择较短的路由），否则（即这个项目是：到目的网络N，下一跳路由器不是x，距离大于当前值）执行d)；

d) 保持。即什么也不做；

3) 若3分钟还没有收到相邻路由器的更新路由表，则把此相邻路由器记为不可达的路由器，即将距离置为16（距离16表示不可达）；

4) 返回。

OSPF链路状态算法（用于构造路由表）

1) 问候分组。一个路由器刚开始工作时，只能通过发送问候分组以发现它有哪些相邻的路由器在工作，以及将数据发往相邻路由器所需的“代价”；正常工作中相邻路由器之间也需定时发送问候分组以维持可达性。

2) 描述分组。OSPF让每一个路由器用数据库描述分组和相邻路由器交换本数据库中已有的链路状态摘要信息。摘要信息主要就是指出有哪些路由器的链路状态信息（以及其序号——用于标识新旧）已经写入了数据库。

3) 请求分组。经过与相邻路由器交换数据库描述分组后，路由器就使用链路状态请求分组，向对方请求发送自己所缺少的某些链路状态项目的详细信息。通过一系列的这种分组交换，全网同步的链路数据库就建立了。

4) 更新分组。在网络运行的过程中，只要一个路由器的链路状态发生变化，该路由器就主动使用链路状态更新分组，用洪泛法向全网（AS内该路由器所在的区域）更新链路状态；当收到链路状态请求分组时，也需发送链路状态更新分组。

5) 确认分组。可靠的洪泛法是在收到更新分组（主动发送的或请求发送的）后发送链路状态确认分组（收到重复的分组只需发送一次确认）。

多播路由选择中洪泛的反向路径广播算法

反向路径广播（RPB）算法用于避免路由器使用洪泛法转发多播数据报时出现兜圈。

RPB的要点：

1) 每个路由器在收到多播数据报时，先检查数据报是否是从源点经最短路径传送来的，检测方法是；判断从本路由器到源点的最短路径上（之所以成为反向路径，是因为在计算最短路径时将源点当作终点）的第一个路由器是否是刚才把多播数据报送来的路由器（若本路由器有多个相邻的路由器都处在到源点的最短路径上，即存在多条同样长度的最短路径，则将IP地址最小的路由器看做是唯一的到源点的最短路径上与本路由器相邻的路由器）；

2) 若1)中的检测结果为是，则向所有其他方向转发刚才收到的多播数据报（进入的方向除外）；

3) 若1)中的检测结果为否，则丢弃而不转发。