更新于2024-04-29 20:32:48

不同于电信网络面向连接的通信方式，网络层向上只提供简单灵活的、无连接的、尽最大努力交付的数据报服务。

也就是说网络层不提供服务质量的承诺。

1. 网际协议: $IP$协议#

$IP$协议是用来使互连起来的**许多计算机网络(网络之间，网际)**能够进行通信的。

1.1 虚拟互连网络#

在市面上有很多种性能不同、不同网络协议的网络，供不同的用户选用。

从一般的概念讲，将网络连接在一起需要一些中间设备。

​ (1) 物理层使用的中间设备叫做转发器(repeater)。

​ (2) 数据链路层使用的中间设备叫做网桥或者桥接器(bridge)。

​ (3) 网络层使用的中间设备叫做路由器(router)。

​ (4) 在网络层以上使用的中间设备叫做网关(gateway)，用网关连接两个不兼容的系统需要在高层进行转换。

网关的使用非常复杂，因此如今使用的很少了。转发器和网桥是在物理层和数据链路层拓展网络，但这只是把一个网络扩大了，并没有产生新的网络。

因此讨论网络互联一般就指用路由器进行网络互连和路由选择。

如果参加互连的计算机网络都是用同一种网际协议$IP$​，那么可以忽略这些网络本身客观存在的异构性，而把它们都看成是一个虚拟互连网络相连接的。

$IP$协议使得性能各异的网络看上去就像是一个统一的网络。看不到每个网络具体的细节。

1.2 $IP$地址#

1.2.1 分类的$IP$地址#

把网络分为$A,B,C,D,E$这5个类。

注意$A,B,C$类每类第一个网络号[最小的网络号$非固定位全0$]都是不可用的，并且$A$类的$127$网络号用作本地软件的环回测试。

特别的$A$类地址中的网络号为$0$的网络，名为$this$，表示这个网络。

主机号全0表示该网络本身。主机号全1表示广播。

特殊的$ip$:

1.2.2 子网的划分#

2级$IP$利用率非常低，原因就在于被分配了某一级地址以后，该级别的地址的主机号往往用不完。另外2级$IP$地址也不够灵活，没办法立刻在一个地区新开一个网络。

于是1985年在原来二级$IP$的基础上增加一个子网号字段。使二级$IP$地址变为$3$级$IP$地址。主要的做法是把一个网络分割成几个小的子网，但是对外仍然表现出同一个大网络的特性。

子网划分是建立在分类$IP$的基础上。这些子网对外仍然表现为一个大网络，然而当数据报传到大网络后，又会被路由器分开送到不同的子网。实现的方式是使用子网掩码(subnet mask)

在子网划分中，子网号一般不全0全1。

以划分一个$B$类地址为例，假设子网位数是$k$位，那么子网个数为$2^k-2$个，主机个数为$2^{16-k}-2$个。总共有$(2^k-2)*(2^{16-k}-2)=2^{16}-2*(2^k+2^{16-k})+4$个可分配地址。比不划分子网要少一些

子网划分提升了$IP$分配的灵活性，但是是以减少可以在网络上连接的主机数量为代价的。

1.2.3 无分类编制$CIDR$​[构成超网]#

1.2.3.1 $CIDR$划分#

无分类编制不基于地址分类，是一种2级$IP$。

使用子网掩码把网络$IP$分为:

另外也可以直接用斜线记法，记为$IP/ 前缀位数$这样的记法。

网络前缀都一样的$IP$地址构成一个**$CIDR$地址块**。

$CIDR$编址就没有子网号全为0这样的概念，因此$k$位网络前缀就有$2^k$个网络号，$2^{32-k}-2个主机号$

另外，$CIDR$编码方式还有其他简写方式：

比如$10.0.0.0/10$可以表示为$0000101000^*$(把网络前缀用2进制表示后，$^*$​​表示主机号任意。)

使用了$CIDR$划分得到大网络以后，可以继续使用$CIDR$进行二级、多级划分。

1.2.3.2 地址聚合#

$CIDR$也可以继续多级划分，就会造成网络号还是非常多，路由器查找、存储非常慢。地址聚合指的是在路由器表中，路由器往往会把一些处于同一个大的$CIDR$网络的并且下一跳都是同一个路由的表项聚合到一起，有效地减少表项。

在路由时，如果有很多表项都能够匹配成功，则选择网络前缀最长的那一个表项。

网络聚合时往往也是寻找$IP$​的最长公共网络前缀。而且要注意网络聚合的时候不能有父网络和其子网络的聚合[重叠]。不能引入其他的网络。

1.2.3.4 二叉线索查找路由表($trie$​树)#

具体看书…似乎和trie树几乎一致。

有时会为这棵$0-1trie$树做压缩，压缩掉公共路径部分，以提高查找速度。

另外，地址聚合实际上就是在这棵树上查询$lca$。

1.2.4 $IP$地址和物理地址#

物理地址($MAC$)是物理层和数据链路层使用的地址，而$IP$​地址是网络层及以上使用的逻辑地址。

但从网络层上看，$IP$协议把下层复杂的细节全屏蔽了，只是用单一的、抽象的$IP$地址进行通信，这极大简化了互联网的传输过程。

但数据报在数据链路层进行传输时就变成帧(frame)，只能使用物理地址($MAC$)，在跨局域网时会变。

另外在数据报传输时有以下几个特点:

1. 网络层上只能看到$IP$数据报，$IP$源地址和目的地址根本不变
2. 尽管$IP$数据报中有$IP$源地址，但是路由选择时只看目的地址。
3. 数据链路层中只能看见$MAC$地址，每当从一个主机/路由器转发到另一个主机/路由器时，主机/路由器都要封装帧，把源$MAC$和目的$MAC$都告诉数据链路层。

要解决的问题有:

1. 主机/路由器如何根据$IP$得到要发送的帧的目的$MAC$($ARP$协议)
2. 路由器/主机如何在只知道最终目的$IP$的情况下找到下一跳$IP$($路由表$)

1.2.4.1 $ARP$协议#

地址解析协议$ARP(Address \ Resolution \ Procotol)$通过$IP$地址解析出局域网内的目的$MAC$地址，过去还有逆地址解析协议$RARP(Reverse \ Address \ Resolution \ Procotol)$，通过$MAC$地址解析出$IP$地址。#

$ARP$协议在每台主机/路由器中都设立一个$ARP$缓冲区，表中存放了$IP$地址向$MAC$​​地址的映射，以及**生存时间**。

1.2.4.1.1 同一局域网下#

当终端(可以是主机，也可以是路由器)$A$要向同一局域网中的终端$B$发送数据报时，$ARP$​协议的基本工作模式是:

1. A查找自身的ARP缓冲区$buffer$，如果A中$ARP$缓冲区存在B的$IP$表项，则直接根据表映射出$B$的$MAC$地址，结束
2. 如果缓冲区$buffer$中没有$B$的$IP$表项，则向局域网内所有终端广播$ARP$请求分组，内容是$我的IP地址是xx.xx.xx.xx,\ MAC地址是XX-XX-XX-XX$，请问$IP地址为B.IP$的终端的$MAC$地址是？
3. 非$B$终端都无视该帧，而$B$主机发现此数据报文是发送给自己的，则收下这个数据报，并且回复给$A$一个$ARP$单播的响应分组，内容是我的$IP$地址是xx.xx.xx.xx，$MAC$是XX-XX-XX-XX
4. 主机$A$收到$B$的响应分组后，就在自己的缓冲区里更新$B$的$IP$到$MAC$的映射，并且$B$也知道了$A$的相关信息，因此再发送数据报就很方便了！

1.2.4.1.2 不同局域网下#

实际上，不同局域网中的$A$和$B$通信时，$A$是没办法通过$ARP$协议解析出$B$的$MAC$地址的，因为没有必要解析的出来，$A$只需要把数据报转发给可以转发数据报的路由器即可。$A$要做的事情应该是根据下一跳的$IP$地址解析出该终端的$MAC$​地址，这个过程还是在同一个局域网下的。

所以每次跳转的时候重复同一局域网下的过程就能完成不同局域网下的$ARP$​协议工作过程。

通过$ARP$协议让网络通信时要完成的复杂物理地址的转换变得很透明，只需要主机$A$和$B$的有独立的$IP$，就好像$A$和$B$连在同一个网络下。

1.2.5 $IP$数据报的格式#

$IP$下层的数据链路层帧有最大传送单元$MTU(Maximum \ Transfer \ Unit)$的限制，$IP$数据报就不能无限制地长，要通过分片的方式切分数据报文，这也就是数据报首部$标识、标志、片偏移$存在的意义。

$IP$数据报尽可能长会让传输效率变大($所需要的首部信息变少$)，但是在路由器转发时会让速度下降。数据报长度比较短能在转发时速度变快。

$IP$协议规定，任何主机/路由器都至少能处理$576 = 512+60 + 4$字节的数据报，576字节以下的数据报不用分片就一定可以处理，但是576字节以上的数据报就要先了解途径的路由器/主机的处理能力。

数据报中的标志字段有$DF,MF$字段，只有当$DF=0(Don't \ Fragment=0)$时该数据才允许分段，而$MF=1$表示该数据报后还有其他分片数据报。同一个源数据报的不同分组都具有同一标识，并且用片偏移确定当前分片的数据部分在源数据报中的位置。

通过标识和片偏移就能够在接收端恢复出源$IP$​数据报。

请特别注意每个字段的单位是什么:

首部长度: 4字节 总长度: 字节 片偏移: 8字节

另外，还有标识上层协议的协议-$id$表:

其中$IP和IPv6$指的是该$IP$数据报是由$IP/IPv6的数据报再封装到IP数据报中$，(有2个首部？)

1.3 网络层的分组转发#

1.4 网际控制报文协议$ICMP(Internet \ Control \ Message \ Protocol)$#

$ICMP$的所有信息都被封装在$IP$数据报内，包括$ICMP$​自身的首部。

$ICMP$的首部包括类型、代码、校验和，以及额外的4个字节。首部是所有$ICMP$报文都不变的。

其中$ICMP$报文的类型主要分**$ICMP$差错报告报文和$ICMP$询问报文**。

$ICMP$的校验和校验的是整一个$ICMP$报文！不是只有首部！

1.4.1 差错报告报文#

主要有:

1. 报文不可到达
2. 超时(TLL=0)
3. 报文参数有误
4. 重定向

这几种差错。

对于差错报告报文的数据部分，取的是:出错的$IP$数据报的首部[定位该出错$IP$数据报]和该$IP$数据报数据字段的前8字节[$TCP$和$UDP$协议中的端口号]

然鹅，并非所有出差错的$IP$数据报都需要发送差错报告报文，

比如:

1. 对装有$ICMP$差错报文的$IP$数据报不再发送$ICMP$差错报文
2. 除了分片的第一个$IP$数据报以外，其余所有后续的数据报都不再发送$ICMP$数据报
3. 多播$IP$数据报都不发送$ICMP$数据报
4. 对具有(应该包括源地址和目标地址)的特殊$IP$地址的数据报都不再发送$ICMP$数据报。

1.4.2 询问报文#

主要有:

1. 回送请求和回答报文: 由主机或路由器询问另一台特定目的主机，需要由该目的主机回答自己的有关状态。用这种方式来获得目的主机的是否可达和有关状态。
2. 时间戳请求和回答报文: 请某台特定目的主机回答自己的时间戳，在$ICMP$时间戳回答报文里有一个$32$位的字段，表示从$1900.01.01$到当前经过的秒数。用这种方式进行时钟同步和时钟测量。

1.4.3 $ICMP$的应用#

1.4.3.1 ping命令#

ping命令是一个应用$ICMP$回送请求和回答报文的例子。

发起ping的主机一下子发送$k$个$ICMP$回送请求报文，而接受方响应这个请求报文并且回答报文。

由于往返的$ICMP$报文都带了时间戳，因此也很容易得出往返时间。

1.4.3.2 tracert命令($Unix$中为tracerroute)#

tracert命令主要应用的是差错报告报文中的超时这一种报文。

发送方依次发送$TTL=1, TTL=2\cdots$的$UDP$报文，并且该$UDP$报文的端口号是非法的，也就是不能交付的。

$TTL=1$的报文在发送给第一个路由器$R_1$后，$TTL$变为0，因此由$R_1$发送$ICMP$超时报文给发送主机。

$TTL=2$的报文在发送给第一个路由器$R_2$后，$TTL$变为0，因此由$R_2$发送$ICMP$​超时报文给发送主机。

$TTL=k$的报文在发送给最后一个路由器$R_k$后，$TTL$变为0，因此由$R_k$发送$ICMP$超时报文给发送主机。

$TTL=k+1$的报文在发送给最后路由器$R_k$后，$TTL$变为1，该报文是可以转发到目的主机上的！但是因为源$UDP$报文是不可交付的，目的主机收到报文后，会发送一个$ICMP$目的不可达差错报告报文。

有这个过程，就得到了发送方到目的主机上的所有路由器和最后的目的主机的$ip$。

1.5 路由选择协议: 路由器中的路由表从何而来#

希望有一个理想的路由选择算法，它:

1. 必须是正确且完整的
2. 计算简单
3. 能够适应网络状况和网络拓扑的变化
4. 算法应该稳定
5. 算法公平
6. 算法在某一种角度下是”最佳”的

路由选择分为静态路由选择策略(人工设置)和动态路由选择策略(自适应路由选择)。

一般路由选择总会分层次，把一个大网络分为较小的自治系统$AS$(Autonomous System)。

自治系统$AS$(Autonomous System)指的是在单一技术管理下的一组路由器。

让一个自治系统$AS$对同层次的$AS$都表现为一个单一的、一致的路由选择策略。原因在于:

1. 网络规模比较大，如果每个路由表中存放了这个大网络的所有网路，那路由表会很大，浪费时间和效率
2. 某些子网络部分并不希望其他部分知道内部网络的状况，但也希望能连接到互联网上。

在分层次的网络上进行路由选择就有2种形式:

1. 内部网关协议$IGP$(Interior Gateway Protocol): 在域内进行路由选择 $RIP、OSPF$
2. 外部网关协议$EGP$(External Gateway Protocol): 在域间进行路由选择 $BGP$[注意: 每一个$AS$中至少有一个或多个路由器要运行$EGP$协议和其他$AS$交换路由]

比如在$AS 24, AS 777 ,AS 46$内部进行路由选择就是域内路由选择。

而与其他$AS$相连接的路由器则需要进行域间路由选择。

如果一级划分的$AS$仍旧很大，达不到需求，可以进行二级甚至是多级划分。

1.5.1 内部网关协议$IGP$#

1.5.1.1 路由信息协议$RIP(Routing \ Information \ Protocol)$#

$RIP$是一种分布式的基于距离向量的路由选择协议。但是很少被使用。它最大的特点是简单，开销很小。

$RIP$协议定义距离:

1. 从一路由器到直接连接的网络的距离定义为1。
2. 从一路由器到非直接相连接的网络的距离定义为经过的路由器数+1。
3. 定义距离为16及以上就为不可达。

$RIP$​要求路由器不仅记录网络号和下一跳地址，还要为每一表项记录到该网络的距离。

那么$RIP$的路由表大致长这样:

如此一来，$RIP$协议就能够选择一条经过最少路由器的一条路径。

1.5.1.1.1 $RIP$如何交换信息#

交换信息的要点是：

1. 和谁交换$=>$ $RIP$协议要求每个路由器仅和直接相邻的路由器交换信息。
2. 交换什么样的信息$=>$ 整一个路由表中所有的信息，就是”我到本自治系统中所有网络的(最短)距离，下一跳的地址”。
3. 什么时候交换 $=>$ 按照固定的时间间隔交换信息，比如间隔$30$秒，保证路由中的信息是最新的。

1.5.1.1.2 $RIP$交换信息算法#

得到相邻路由器$R'$发送的路由信息

1. $\star$先进行”初始化”：把距离都+1，把下一跳地址都改为$R'$。

2. 接着对**每一个表项$row'$**都执行以下过程:

   • 查看该表项对应的网络号是否存在于当前路由表，如果不存在，就把$row'$直接加入到路由表中。否则执行下一步

   • 该网络号已在路由表中，则查看该表项对应的下一跳地址$X'$，如果$X'$就是路由表中的下一跳地址，则直接更新路由表中的表项为$row'$[确保路由表中的信息总是最新的]。否则执行下一步

   • 该网络号在路由表中且下一跳地址并不相同，则查看该表项的距离$distance'$，如果$distance' < distance$才更新[确保路由表中的距离总是最近的]，否则就什么也不做，扫描下一个表项。

3. $\star$如果某个时间间隔里(3分钟)总接受不到某个相邻路由表的更新报文，就在路由表中把该路由器的表项都设置为不可达(距离为16)。

但是这样的算法会带来一定的问题，比如$RIP$中最大的问题**“好消息传得快，坏消息传得慢”**。

当一个网络出现故障时，$RIP$​协议往往要经过比较长的时间才能把这个信息传递给所有的路由器。

但是如果有一个路由器发现了一个更加短的路由，这种信息就传播的很快。

可以考虑以下事件：

坏消息传的慢事件：$10.4.0.0$到路由器$C$的网络不可达从可达变成不可达，$C$更新自己的路由表，把到$10.4.0.0$的表项的距离改为不可达。且在路由器$C$把更新的路由表传给$B$前，路由器$B$先把路由表传递给了$C$。

1.5.1.1.3 $RIP$协议报文格式#

$RIP2$协议支持子网划分和$CIDR$无分类编址网络。

$RIP2$协议数据报使用$UDP$协议进行传输！因此应该是$RIP2$数据报文封装在$UDP$数据报中再封装$IP$数据报里传输。

$RIP$自身的数据报文由首部和路由部分组成。

特别地，由于一个路由部分最多可以放入$25$个路由信息，因此一个$RIP$数据报的最大长度是$25*20+4=504$字节。

$RIP$协议还可以进行简单地鉴别功能，使用鉴别功能时将第一个路由信息作为鉴别信息。把地址族标识改为$0$x$FFFF$(全1)，而路由标记写入鉴别类型，剩余的16个字节全都可以作为鉴别数据。

1.5.1.2 开放最短路径优先协议$OSPF$(Open Shortest Path First)#

$OSPF$最大的特征是使用了分布式的链路状态协议。它就是为了克服$RIP$​​协议的缺点而开发的。

$OSPF$协议的目的是让每一台路由器都能够维护一个链路状态数据库，也就是全网的带权拓扑图。在这张带权图上跑$dijkstra$​​就能找到该路由器到其他路由器的最短路径。

链路状态数据库的同步是指使得不同路由器的链路状态数据库变得一样。

完全邻接指的是相邻的 同步路由器。

$OSPF$的另一特征是更新收敛的速度非常快。($RIP$比较慢)。

1.5.1.2.1 $OSPF$如何交换信息#

交换信息的要点有3条:

1. 和谁交换信息 $=>$ $OSPF$协议要求每台路由器和自治系统内的所有路由器都发送信息。使用的方法是泛洪法。
2. 交换哪些信息 $=>$ $OSPF$协议要求路由器分享和本路由器相邻的所有路由器的链路状态(路由器知道的部分信息)。其中链路状态包括相邻路由器的地址和连接到该路由器的度量(可以被称为是代价)。
3. 何时交换信息 $=>$ $OSPF$中无需路由器定时发送自己的链路状态信息。只需要链路状态发生改变时发送链路状态信息即可。

由于每台路由器都要和自治系统内部所有路由器都发送信息，想必网络拥塞程度会非常大，为了能让$OSPF$可以在大网络上运行，往往会把一个自治系统划分为几个区域(用32位$bit$标识)。并且把泛洪法交换信息的范围从整个AS变为整个区域。

把区域分为2大类:

1. 主干区域(backbone Area): 标识符为$0.0.0.0$，联通其他区域
2. 其他区域

并且划分出3类特殊的路由器:

1. 区域边界路由器(area border router): 处于每个区域和主干区域交接处的路由器。其他区域来的信息都由区域边界路由器进行概括。
2. 主干路由器(backbone router): 处于主干区域的路由器。
3. 自治系统边界路由器：处于主干区域中，专门处理本自治系统和其他自治系统之间的路由交换。

层次划分又一次使得网路变得容易在大规模的情况下变得适用。

1.5.1.2.2 $OSPF$协议报文格式#

$OSPF$协议不再使用$UDP$协议传输报文，而是直接使用$IP$协议传输报文。

$OSPF$5种分组是:

$OSPF$规定每$10$秒钟都要交换一次问候分组，以此知晓哪些邻站可达。如果间隔$40$秒钟没有收到某个相邻路由器的问候分组，则认为该路由器不可达。

$OSPF$协议一般并不采用泛洪法来从空白链路状态数据库建立完整的链路状态数据库，只有在链路状态发生改变的时候才进行泛洪法。

而建立的方法一般是：

1. 路由器和邻站交换状态数据库的摘要[哪些链路已经被写入数据库]
2. 向邻站请求缺少的链路状态

以此大大减少了网络的负担。

而当有路由器的邻接链路状态发生改变时，采用可靠的泛洪法(泛洪法+确认信息)来向整个区域内的路由器都通知这个消息。

$OSPF$​协议还有以下几个特点:

1. $OSPF$协议允许管理员给一条链路设置不同的度量以适应不同的业务。(比$RIP$灵活)
2. $OSPF$允许负载均衡的情况，即当多条路径的总度量都一样时，可以允许把起点到终点的数据报分散到这几条路径中去。($RIP$只会选其中一条，比$RIP$高效）
3. 所有在$OSPF$中的链路之间都可以进行鉴别，可以仅在信任的路由器之间同步链路状态
4. 也可以支持子网划分和$CIDR$无分类编址方式。
5. $OSPF$让每一段链路都带上一个**$32bit$​的序号**，序号越大，链路状态越新。
6. 每隔$30$秒，刷新一次链路状态数据库。
7. 为了更多地减少路由器之间的信息交换，$OSPF$又选定某些特殊路由器作为指定路由器(其他所有的路由器的信息都传递给他，由它转交给其他路由器)，从两两之间的$N(N-1)$减小到$2*N$。