计网网络层

数据链路层保证了数据在相邻节点的可靠传输，网络层关注的是如何将源端数据包经过网络上的节点一路送到接收方。为了实现这个目标，网络层必须知道网络拓补结构，并从中选出适当的路径。本章包含到路由算法、拥塞控制、服务质量、网络互连和IP 协议。

上图为本章考试重点，非原书结构，仅供参考。

网络层两类服务

  • 无连接服务——数据报网络

    特点：所有的数据包都被独立地注入到网络中，并且每个数据包独立路由，不需要提前建立任何设置。在这样的上下文中，数据包通常称为数据报，对应的网络称为数据报网络。

  • 面向连接服务——虚电路网络

    特点：发送数据报前，首先建立一条从源到目标的路径，每条报文都沿这条路径传送。这个连接称为虛电路，对应的网络称为虚电路网络。

路由算法——基于最优路径的路由算法

最优化原则

遵循最优化原则以破除环路，方便设计路由算法。

最优化原则：如果J 在从I 到K 的最优路径上，那么从J 到K 的最优路径也必定遵循
相同的路由。即最优路径的子路径还是最优路径。

汇集树：依照最优化原则，从所有的源到一个指定目标的最优路径的集合构成一颗以目
标节点为根的树。

泛洪算法

泛洪路由的基本想法是源节点将消息以分组的形式发给其相邻的节点，相邻的节点再转发给它们的相邻节点，继续下去，直至分组到达网络中所有的节点。很显然，泛洪法会产生大量的重复数据包，除非采取某些措施来抑制泛洪过程，否则将会产生无限多的数据包。

距离矢量路由算法DV（RIP 协议）

每个路由器维护一张表，表中列出了当前已知的到每个目标的最短距离，以及所使用的线路的下一跳，通过在邻居之间相互交换信息，路由器不断地更新它们的内部表，最终每个路由器都了解到达目的地的最佳链路。届时就可以根据路由表和目的地址，在任意路由上确定下一跳进行跳转。

路由表的具体维护方式：当前点与所有邻居节点交换的路由表，然后根据这些表计算该点去所有其他点的最优下一跳

如上面的例子所示，当求点J 到点C 的最短距离和下一跳时，分别求出Ji+iC 的最小值，即min{8+25,10+18,12+19,6+36}=28，最短路径是经过I，时长28。

无穷计数问题：“坏消息”传播的很慢，可以从下面的例子进行理解

如图所示，ABC 各自维持自己的路由表，但如果AB 之间的线路突然断开，那么B 和C 在计算各自与A 的距离的时候，就会互为参考，每次路由表更新的时候计算出的与C 的距离只会加1 直到数值趋近于无穷，所以AB 之间的断开很慢被发现。

链路状态路由算法LSP（OSPF、IS_IS 协议）

每个节点都将自己的邻居信息表传给所有节点，每个节点都保存所有节点的邻居信息表，并使用Dijkstra 计算出本节点到其他所有节点的最短路。

上面可以看到，邻居信息表中都包含两个字段：Seq 和Age。

Seq:由于邻居信息表需要泛洪给所有节点，为了控制泛洪的规模，所以使用Seq 序号。新的链路状态数据包到达一个节点的时候，路由器检查这个新来的数据包的序号和源路由器是否已经出现在自己的列表中。重复则丢弃，源路由器相同而序号过时则拒绝接受。

Age:在数据包发出时设定初值，然后每一秒都会减一，变为0 则会被丢弃，①可以在泛洪时防止数据包无限生存②及时清理路由器中链路状态数据库中旧的或无效的信息，以防以下问题的影响，如：路由器崩溃后重启序号从0 开始的话会被当做过时信息丢弃；传递过程中序号出现差错如4 变65540，那么只有seq 字段就会导致后面的5-65539 全被拒绝。

算法步骤：

  1. 发现邻居节点，并知道其网络地址
  2. 测量到各邻居节点的延迟或开销
  3. 构造一个分组，分组中包含所有它刚知道的信息
  4. 将这个分组发送给所有其他的路由器
  5. 计算出到每一个其他路由器的最短路径

务必重点掌握距离矢量算法和链路状态算法，详见中文课本P285—P291

因为距离矢量算法每个节点只与邻居节点交换信息，在面临路由器失效时会出现无穷计数问题。链路状态算法用泛洪的方式分发链路状态包，所以每个节点都知道完整的网络加权0拓补图，重点在链路状态包的构造和分发方法以及健壮性。

层次路由

随着网络规模的增长，路由器的路由表也成比例增长，结果是路由器效率下降，成为网络服务的瓶颈。解决之道是将网络分层，采用分层路由之后，路由器被划分成区域，每个路由器知道如何将数据包路由到自己所在区域内的目标地址，但是对于其他区域的内部结构毫不知情。

可以认为每个区域是一个村，普通村民知道如何与本区域所有其他人联系，而村长除此之外还知道如何与别的村的村长联系，村民与外村人联络时会先将信交给村长由村长转发，他负责本区域与其他区域的联络。后面IP 协议的子网划分中的分类寻址就是层次化的设计。

拥塞控制

主要掌握RED 协议，完整的流量控制应该是网络层（RED 协议）和传输层（TCP 慢启动）配合的任务。

拥塞：网络中存在太多数据包导致数据包被延迟和丢失，从而降低了传输性能。当拥塞出现后，有可能遭遇拥塞崩溃。

随机早期检测（RED）（P310）
当某条链路上的平均队列长度超过某个阈值时，该链路就被认为即将拥塞，因此路由器随机丢弃一小部分数据包。

当拥塞时，若路由器向发送方发抑制包，那么大量的抑制包反而会加重拥塞。所以网络层解决拥塞的思路就是防患于未然，在局面变得毫无希望前让路由器舍弃负担。后面配合传输层可以降低用户发送速率，从根本上解决拥塞。

流量整形——平滑的流量更好管理

流量整形（traffic shaping）是指调节进入网络的数据流的平均速率和突发性所采用的技术，包括漏桶和令牌桶。

  • 漏桶算法：无论注入桶内的速率是大是小，出桶的速率总是恒定的。
  • 令牌桶算法：桶内存放发送数据的令牌，每单位时间获得一定量的令牌，发送数据时取出令牌，流量大小受限于积累的令牌数量。一般令牌桶下面会有一个漏桶用于平滑发送速率。

IPv4 协议

层与层之间数据的传递：上层整段消息内容是对下一层透明的数据

IP 头

IP 协议Internet Protocol 提供尽最大努力的数据传输，不保证可靠

IP 数据报由头和正文组成，正文是有效净荷，携带数据；头由20 字节定长及一个可选变长组成，携带此数据报的解释信息。下面是IP 头的相关介绍。

  1. 版本：记录数据报属于什么版本，Ipv4 Ipv6
  2. IHL：IP 头长，单位为4 字节，因为头部至少20 字节定长，所以值域5~15。
  3. 区分服务：前6 位标识数据报服务类型，后2 位携带显示拥塞信息，了解。
  4. 总长度：数字报总长度，单位是1 字节（8bit），包括头和数据，最大长度216 字节
  5. 生存期TTL：计数单位为跳数，每经过一跳减一，递减到0 的时候数据包被丢弃并由路由器给源地址发送一个报警包。设定目的主要解决环路问题，避免数据包被永远都留在网路中。不同协议的技术单位不同，有的还设定为秒，这是为了控制拥塞，但是秒不好实现。
  6. 协议：记录IP 分组携带数据的协议类型，即传输层协议的编号，如TCP、UDP 等
  7. 头校验和：对IP 头信息进行校验，检测数据包穿过网络时是否发生错误。但是由于只校验了头，所以IP 数据报整体依旧不可靠
  8. 源地址和目的地址：源地址可以用于丢包时给源地址发消息；目的地址用于寻找路径时查路由表
  9. 选项：给出对寻址过程中要求必须经过的路由器，如今，几乎已经不再使用IP 选项
  10. IP 头第二行都是关于分段的处理，其用途就是：不同网络的最大帧长的要求可能不同，从而大数据进入小网络需要对大的数据进行分段。标识表示这段分段属于哪个数据报：DF 表示是否允许分段，DF=1 表示该数据报不允许分段，到达需要分段的地方就丢包返回消息；MF 表示所属于的数据报是否还有更多的段。MF=0 表示当前分段是该数据报的最后一段；分段偏移量表示该分段在整个数据包中的位置，以8 字节为单位。具体计算此处不再详细介绍，这一行了解即可。

分类寻址Classful Addresing

IP 地址被分为五类。如A 类允许27 个网络，每个网络中允许有224 台主机，由于每类网络中允许的主机数量是固定的，所以造成了IP 地址极大的浪费，这才引入了后面的CIDR

子网Subnet 与前缀prefix

  1. IP 地址长32 位，由高位的可变长网络号和低位的主机号组成，同一网络上所有主机的网络号相同，一个网络对应一块连续的IP 地址空间，这块地址空间就被称为地址的前缀
  2. 写法：点分十进制，如18.0.31.0/24，24 表示网络号位数。子网掩码是网络号长度个1 和主机号长度个0 组成，子网掩码和IP 按位与可以得到网络号
  3. 子网划分subnetting：在内部将一个网络块分成几个部分供多个内部网络使用，但对外部世界仍然像是单个网络一样。而第一章的子网subnet 是分割一个大型网络得到的一系列结果网络，是指网络中所有路由器和通信线路的集合。
  4. 转发过程：数据报到达后，路由器检查该数据包的目的地址，将该目的地址与路由表中每个子网目标的子网掩码按位与看是否匹配

无类域间路由CIDR

Classless Inter-Domain Routing，是为解决IP 路由表爆炸、IP 地址耗尽而提出的一种措施。在变长子网掩码的基础上提出的一种消除ABCDE 类网络划分，并且可以在软件的支持下实现构造超网的一种IP 地址的划分方法。

子网划分与聚合的一个实例：以下页图为例用一块从194.24.0.0 开始的大小为213 的地址分配三个大学的地址。计算过程如下。其中每个地点的两行分别代表该地的起始和终止IP 地址。竖虚线为网络号和主机号划分。

分配的原则是：一个网路只能有一个网络号，进行IP 地址分配时尽可能连续分配。以牛津大学为例，尽管前面余下210 个空白，但是依旧选择向后。

路由聚合rounte aggregation：为了减小路由表长度，将多个小前缀地址块合并为一个大前缀地址块，如上面的三个地址就可以聚合成一个地址，方法是将三者网络号最大公共部分聚合为新网络号
194.21.0.0/21
194.24.8.0/22 → 194.24.0.0/19
194.24.16.0/20

如此，就可以将三个路由表项合成一个，其下一跳是伦敦。但由此带来一个问题：如果上面空白的那部分被分配给非洲某学校，那么空白部分就会被错误的聚合。因此要在路由表中新增一项单独指明空白部分的下一跳。

所以，在没有聚合时，查路由只需要找到匹配的一项就可以跳到下一跳，但是有聚合以后，需要寻找路由表项中的最长匹配

路由器的转发过程完善如下：当新的消息进入路由器时，首先进入等待队列，通过一定的调度策略进行调度。调度到这个消息时，获取其目的地址，将目的地址分别与路由表中的每一项网络号的子网掩码进行比对，选取最长匹配的网络表项进行转发。当然，没有查询到匹配的时候，转发到缺省表项，也就是给上一层路由，继续寻找。

NAT 网络地址转换

  1. IP 地址短缺问题解决策略：①动态分配IP ②迁移到IPv6 ③多台共用一个IP
  2. NAT(Network Address Translation)，它的思想是设定两套IP 地址,内网相对于外网来说共用一个public 地址，而在内网中，每台机器对应一个private 地址
  3. 内网之间的通信使用private 地址，当想要向外网发送消息时，只需将源地址替换为内网共用的public 地址
  4. 当外网向内网发送消息时，因无法区分内网的主机，所以引入了port。将私有IP与端口号影射成新的port，当与这个端口号交互时，根据影射算法可以知道私有IP
  5. 缺点：①违反了最基本的协议分层原则，传输层的数据不再对网络层透明②私有IP 与port 对公有port 的映射关系不是一一对应的③违反IP 唯一性原则等。

隧道技术

隧道技术（tunneling）：是一种通过使用互联网络的基础设施在不同网络之间传递数据的方式。使用隧道传递的数据（或负载）可以是不同协议的数据帧或包。隧道协议将其它协议的数据帧或包重新封装然后通过隧道发送，到达对方以后再将被包裹的数据提取出来进行传递。新的帧头提供路由信息，以便通过互联网传递被封装的负载数据。

简言之，就是处理不同网络相连接的情形，隧道技术对于两头网络相同中间不同的特例有效。它的方法就是在经过中间网络的时候加一个新的IP 头，度过以后再拆掉。

Internet 控制协议

ICMP 控制消息协议

为了提高IP 数据报交付成功的机会，在网络层使用了网络控制报文协议来允许主机或者路由器来报告差错和异常情况。了解即可，详见P358。ICMP 是通过向数据包的源地址报告有关事件使网络运行正常。

ARP

Address Resolution Protocol，地址解析协议是一个连接二三层的协议，可以说是IP 分组-帧连接协议。

某一层的地址只在本层有效，网络层负责寻找路径，而真正实现消息传递的是链路层，所以要实现两层地址之间的映射。

路由器之间消息的传递

现在的关键在于已知源IP、源MAC 和目的IP 的情况下怎样获取目的MAC

交换机原理

在上图中的交换机中存储着一张MAC 和port 的对应表，交换机的一个端口和一台主机一一对应。只有发送过消息的端口的对应关系才会被交换机所知道，而一个广播能同时将一个子网的全部对应关系都传送给交换机。

同一子网中消息的传递

如上，主机1 欲给主机2 发消息，应首先经过如下两个过程：

不同子网消息的传递

E3 作为通往外网的代理分析广播的接收方是否在这个子网中。若目的IP 与E3 所在网络号相同那么E3 就当做一个普通主机，否则提交到路由器的网络层，而E3 则作为这条消息的代理与网外交互。

而在路由表中找到对方所属的子网以后，在该子网中通过ARP 广播找到该IP