计算机网络-网络层

Posted on
Words count in article: 17.5k | Reading time ≈ 62

计算机网络-网络层

学习自：https://github.com/crisxuan/bestJavaer/blob/master/computer-network/computer-internet.md

https://zhuanlan.zhihu.com/p/126754314

之前我们说了应用层和运输层。运输层是提供进程的端到端通信。那么下面我们将学习网络层是怎样实现主机到主机的通信服务的。几乎每个端系统都有网络层这一部分，所以，网络层必然是很复杂的。

网络服务模型

因特网的网络层提供了单一的服务，即尽力而为。 这让传送的分组不能保证以它们发送的顺序被接收，也不能保证它们最终交付；既不能保证端到端时延，也不能保证最小有效带宽。尽管什么都不保证，但是这种服务模型却能满足大多数网络服务。

网络层概述

网络层是OSI的第三层，它位于传输层和链路层之间，网络层的主要目的是实现两个端系统之间透明的数据传输。

TCP/IP 把表示层和会话层都归入了应用层。

网络层可以分成两种平面，在第四章主要讲的是数据平面，负责转发网络流量，如路由器交换机中的转发表；在第五章主要讲的是控制平面, 作用是控制网络的行为，比如网络路径的选择(路由)。

网络层的作用从表面看上去非常简单，即将分组从一台主机移动到另外一台主机。为了实现这个功能，网络层需要两种功能

  • 转发：因为在互联网中有很多路由器的存在，而路由器是构成互联网的根本，路由器最重要的一个功能就是分组转发，当一个分组到达某路由器的一条输入链路时，该路由器会将分组移动到适当的输出链路。转发是在数据平面中实现的唯一功能。
  • 路由选择： 当分组由发送方流向接收方时，网络层必须选择这些分组的路径。计算这些路径选择的算法被称为 路由选择算法(routing algorithm)。

也就是说，转发是指将分组从一个输入链路转移到适当输出链路接口的路由器本地动作，而路由选择是指确定分组从源到目的地锁定为的路径的选择。我们后面会经常提到。

那么，路由器怎么知道有哪些路径可以选择呢？

每台路由器都有一个关键的概念就是 转发表(forwarding table)。路由器通过检查数据包标头中字段的值，来定位转发表中的项来实现转发。标头中的值即对应着转发表中的值，这个值指出了分组将被转发的路由器输出链路。如下图所示:

上图中有一个 1001 分组到达路由器后，首先会在转发表中进行索引，然后由路由选择算法决定分组要走的路径。每台路由器都有两种功能：转发和路由选择。下面我们就来聊一聊路由器的工作原理。

数据层面

路由器工作原理

下面是一个路由器体系的体系结构图，路由器主要是由4个组件组成：

  • 输入端口：输入端口(input port)有很多功能。线路终端功能和数据链路处理功能，这两个功能实现了路由器的单个输入链路相关联的物理层和数据链路层。输入端口查找/转发功能对路由器的交换功能来说至关重要，由路由器的交换结构来决定输出端口，具体来讲应该是查询转发表来确定的。
  • (高速)交换结构：交换结构(Switching fabric)就是将路由器的输入端口连接到它的输出端口。这种交换结构相当于是路由器内部的网络。
  • 输出端口：输出端口(Output ports) 通过交换结构转发分组，并通过物理层和数据链路层的功能传输分组，因此，输出端口作为输入端口执行反向数据链接和物理层功能。
  • 路由选择处理器：路由选择处理器(Routing processor) 在路由器内执行路由协议，维护路由表并执行网络管理功能。这属于控制平面的内容

输入端口

上面介绍了输入端口有很多功能，包括线路终端、数据处理、查找转发，其实这些功能在输入端口的内部有相应的模块，输入端口的内部实现如下图所示

每个输入端口中都有一个路由处理器维护的路由表的副本，根据路由处理器进行更新。这个路由表的副本能 够使每个输入端口进行切换，而无需经过路由处理器统一处理。这是一种分散式的切换，这种方式避免了路 由选择器统一处理造成转发瓶颈。

在输入端口处理能力有限的路由器中，输入端口不会进行交换功能，而是由路由处理器统一处理，然后根据 路由表查找并将数据包转发到相应的输出端口。

一般这种路由器不是单独的路由器，而是工作站或者服务器充当的路由，这种路由器内部中，路由处理器其实就是 CPU，而输入端口其实只是网卡。

输入端口会根据转发表定位输出端口，然后再会进行分组转发，那么现在就有一个问题，是不是每一个分组都有自己的一条链路呢？如果分组数量非常大，到达亿级的话，也会有亿个输出端口路径吗？

我们的潜意识中显然不是的，来看下面一个例子。

下面是三个输入端口对应了转发表中的三个输出链路的示例

可以看到，对于这个例子来说，路由器转发表中不需要那么多条链路，只需要四条就够，即对应输出链路 0 1 2 3 。也就是说，能够使用 4 个转发表就可以实现亿级链路。

如何实现呢？

使用这种风格的转发表，路由器分组的地址 前缀(prefix) 会与该表中的表项进行匹配。

如果存在一个匹配项，那么就会转发到对应的链路上，可能不好理解，我举个例子来说吧。

比如这时有一个分组是 11000011 10010101 00010000 0001100到达，因为这个分组与 11000011 10010101 00010000相匹配，所以路由器会转发到 0 链路接口上。如果一个前缀不匹配上面三个输出链路中的一种，那么路由器将向链路接口 3 进行转发。

路由匹配遵循 最长前缀匹配原则(longest prefix matching rule)，最长匹配原则故名思义就是如果有两个匹配项一个长一个短的话，就匹配最长的。

一旦通过查找功能确定了分组的输出端口后，那么该分组就会进入交换结构。在进入交换结构时，如果交换结构正在被使用，就会阻塞新到的分组，等到交换结构调度新的分组。

交换结构

交换结构是路由器的核心功能，通过交换功能把分组从输入端口转发至输出端口，这就是交换结构的主要功能。交换结构有多种形式，主要分为 通过内存交换、通过总线交换、通过互联网络进行交换，下面我们分开来探讨一下。

  • 经过内存交换：最开始的传统计算机就是使用内存交换的，在输入端口和输出端口之间是通过 CPU 进行的。输入端口和输出端口的功能就好像传统操作系统中的 I/O 设备一样。当一个分组到达输入端口时，这个端口会首先以中断 的方式向路由选择器发出信号，将分组从输入端口拷贝到内存中。然后，路由选择处理器从分组首部中提取目标地址，在转发表中找出适当的输出端口进行转发，同时将分组复制到输出端口的缓存中。这种方式比较低效，早期的路由器都是以这种方式实现的。

这里需要注意一点，如果内存带宽以每秒读取或者写入 B 个数据包，那么总的交换机吞吐量(数据包从输入端口到输出端口的总速率) 必须小于 B/2。

  • 经过总线交换：在这种处理方式中，总线经由输入端口直接将分组传送到输出端口，中间不需要路由选择器的干预。总线的工作流程如下：输入端口给分组分配一个标签，然后分组经由总线发送给所有的输出端口，每个输出端口都会判断标签中的端口和自己的是否匹配，如果匹配的话，那么这个输出端口就会把标签拆掉，这个标签只用于交换机内部跨越总线。如果同时有 多个 分组到达路由器的话，那么只有一个分组能够被处理，其他分组需要再进入交换结构前等待。也就是说这对总线的带宽要求很高。

  • 经过互联网络交换：这是一种纵横式的交换网络。它能克服单一、共享式总线带宽限制。它使输入端口和输出端口两两之间都有一条网路。如下图所示

输出端口处理

如下图所示，输出端口处理取出已经存放在输出端口内存中的分组并将其发送到输出链路上。包括选择和去除排队的分组进行传输，执行所需的链路层和物理层的功能。

在输入端口中有等待进入交换的排队队列，而在输出端口中有等待转发的排队队列，排队的位置和程度取决于流量负载、交换结构的相对频率和线路速率。

随着队列的不断增加，会导致路由器的缓存空间被耗尽，进而使没有内存可以存储溢出的队列，致使分组出现丢包(packet loss)，这就是我们说的在网络中丢包或者被路由器丢弃。于是，接下来我们来讲一下排队。

路由器出现排队

下面我们通过输入端口的排队队列和输出端口的排队队列来介绍一下可能出现的排队情况。

输入队列(HOL阻塞)

如果交换结构的处理速度没有输入队列到达的速度快，在这种情况下，输入端口将会出现排队情况，到达交换结构前的分组会加入输入端口队列中，以等待通过交换结构传送到输出端口。

为了描述清楚输入队列，我们假设以下情况：

  • 使用网络互联(crossbar)的交换方式；
  • 假定所有链路的速度相同；
  • 在链路中一个分组由输入端口交换到输出端口所花的时间相同，从任意一个输入端口传送到给定的输出端口；
  • 分组按照 FCFS 的方式，只要输出端口不同，就可以进行并行传送。但是如果位于任意两个输入端口中的分组是发往同一个目的地的，那么其中的一个分组将被阻塞，而且必须在输入队列中等待，因为交换结构一次只能传输一个到指定端口。

如下图所示

在 A 队列中，输入队列中的两个分组会发送至同一个目的地 X，假设在交换结构正要发送 A 中的分组，在这个时候，C 队列中也有一个分组发送至 X，在这种情况下，C 中发送至 X 的分组将会等待，不仅如此，C 队列中发送至 Y 输出端口的分组也会等待，即使 Y 中没有出现竞争的情况。这种现象叫做 线路前部阻塞(Head-Of-The-Line, HOL) 。

也就是说，在一个输入队列中排队的分组必须等待通过交换结构发送，即使输出端口是空的，因为它被位于线路前部的另一个分组所阻塞了。

输出队列

我们下面讨论输出队列中出现等待的情况。假设交换速率要比输入/输出的传输速率快很多，而且有 N 个输入分组的目的地是转发至相同的输出端口。在这种情况下，在向输出链路发送分组的过程中，将会有 N 个新分组到达传输端口。因为输出端口在一个单位时间内只能传输一个分组，那么这 N 个分组将会等待。然而在等待 N 个分组被处理的过程中，同时又有 N 个分组到达，所以 ，分组队列能够在输出端口形成。这种情况下最终会因为分组数量变的足够大，从而耗尽 输出端口的可用内存。

如果没有足够的内存来缓存分组的话，就必须考虑其他的方式，主要有两种：一种是丢失分组，采用 弃尾(drop-tail) 的方法；一种是删除一个或多个已经排队的分组，从而来为新的分组腾出空间。

网络层的策略对 TCP 拥塞控制影响很大的就是路由器的分组丢弃策略。在最简单的情况下，路由器的队列通常都是按照 FCFS 的规则处理到来的分组。由于队列长度总是有限的，因此当队列已经满了的时候，以后再到达的所有分组（如果能够继续排队，这些分组都将排在队列的尾部）将都被丢弃。这就叫做尾部丢弃策略。

通常情况下，在缓冲填满之前将其丢弃是更好的策略。

如上图所示，A B C 每个输入端口都到达了一个分组，而且这个分组都是发往 X 的，同一时间只能处理一个分组，然后这时，又有两个分组分别由 A B 发往 X，所以此时有 4 个分组在 X 中进行等待。

等上一个分组被转发完成后，输出端口就会选择在剩下的分组中根据 分组调度(packet scheduleer) 选择一个分组来进行传输，我们下面就会聊到分组调度

那么我们一般怎么来计算一个合理的缓冲区呢？ 我们的目标是不能丢包，但可以忍受排队。设 N 为TCP流的数目， C为链路的数量，RTT为往返时间

分组调度

现在我们来讨论一下分组调度次序的问题，即排队的分组如何经输出链路传输的问题。我们生活中有无数排队的例子，但是我们生活中一般的排队算法都是 先来先服务(FCFS)，也是先进先出(FIFO)。

先进先出

先进先出就映射为数据结构中的队列，只不过它现在是链路调度规则的排队模型。

FIFO 调度规则按照分组到达输出链路队列的相同次序来选择分组，先到达队列的分组将先会被转发。在这种抽象模型中，如果队列已满，那么弃尾的分组将是队列末尾的后面一个。

优先级排队

优先级排队是先进先出排队的改良版本，到达输出链路的分组被分类放入输出队列中的优先权类，如下图所示

通常情况下，每个优先级不同的分组有自己的优先级类，每个优先级类有自己的队列，分组传输会首先从优先级高的队列中进行，在同一类优先级的分组之间的选择通常是以 FIFO 的方式完成。

循环加权公平排队

在循环加权公平规则(round robin queuing discipline) 下，分组像使用优先级那样被分类。然而，在类之间却不存在严格的服务优先权。循环调度器在这些类之间循环轮流提供服务。如下图所示

在循环加权公平排队中，类 1 的分组被传输，接着是类 2 的分组，最后是类 3 的分组，这算是一个循环，然后接下来又重新开始，又从 1 -> 2 -> 3 这个顺序进行轮询。每个队列也是一个先入先出的队列。

这是一种所谓的保持工作排队(work-conserving queuing) 的规则，就是说如果轮询的过程中发现有空队列，输出端口不会等待分组，而是继续轮询下面的队列。

IP 协议

路由器对分组进行转发后，就会把数据包传到网络上，数据包最终是要传递到客户端或者服务器上的，那么数据包怎么知道要发往哪里呢？起到关键作用的就是 IP 协议。

IP 主要分为三个部分，分别是 IP 寻址、路由和分包组包。下面我们主要围绕这三点进行阐述。

IP地址

既然一个数据包要在网络上传输，那么肯定需要知道这个数据包到底发往哪里，也就是说需要一个目标地址信息，IP 地址就是连接网络中的所有主机进行通信的目标地址，因此，在网络上的每个主机都需要有自己的 IP 地址。

在 IP 数据报发送的链路中，有可能链路非常长，比如说由中国发往美国的一个数据报，由于网络抖动等一些意外因素可能会导致数据报丢失，这时我们在这条链路中会放入一些 中转站，一方面能够确保数据报是否丢失，另一方面能够控制数据报的转发，这个中转站就是我们前面聊过的路由器，这个转发过程就是 路由控制。

路由控制(Routing) 是指将分组数据发送到最终目标地址的功能，即使网络复杂多变，也能够通过路由控制到达目标地址。因此，一个数据报能否到达目标主机，关键就在于路由器的控制。

这里有一个名词，就是 跳，因为在一条链路中可能会布满很多路由器，路由器和路由器之间的数据报传送就是跳，比如你和隔壁老王通信，中间就可能会经过路由器 A-> 路由器 B -> 路由器 C 。

那么一跳的范围有多大呢？

一跳是指从源 MAC 地址到目标 MAC 地址之间传输帧的区间，这里引出一个新的名词，MAC 地址是啥？

MAC 地址指的就是计算机的物理地址(Physical Address)，它是用来确认网络设备位置的地址。在 OSI 网络模型中，网络层负责 IP 地址的定位，而数据链路层负责 MAC 地址的定位。MAC 地址用于在网络中唯一标示一个网卡，一台设备若有一或多个网卡，则每个网卡都需要并会有一个唯一的 MAC 地址，也就是说 MAC 地址和网卡是紧密联系在一起的。

路由器的每一跳都需要询问当前中转的路由器，下一跳应该跳到哪里，从而跳转到目标地址。而不是数据报刚开始发送后，网络中所有的通路都会显示出来。这种多次跳转也叫做多跳路由。在一定数量的跳 之后，数据报就会失去作用，被丢掉。

IP地址的定义

现如今有两个版本的 IP 地址，IPv4 和 IPv6，我们首先探讨一下现如今还在广泛使用的 IPv4 地址，后面再考虑 IPv6 。

IPv4 由 32 位正整数来表示，在计算机内部会转化为二进制来处理，但是二进制不符合人类阅读的习惯，所以我们根据易读性的原则把 32 位的 IP 地址以 8 位为一组，分成四组，每组之间以 . 进行分割，再将每组转换为十进制数。如下图所示

那么上面这个 32 位的 IP 地址就会被转换为十进制的 156.197.1.1。

除此之外，从图中我们还可以得到如下信息

每个这样 8 位位一组的数字，自然是非负数，其取值范围是 [0,255]。

IP 地址的总个数有 $2^{32}$次幂个，这个数值算下来是 4294967296 ，大概能允许 43 亿台设备连接到网络。实际上真的如此吗？

实际上 IP 不会以主机的个数来配置的，而是根据设备上的 网卡(NIC) 进行配置，每一块网卡都会设置一个或者多个 IP 地址，而且通常一台路由器会有至少两块网卡，所以可以设置两个以上的 IP 地址，所以主机的数量远远达不到 43 亿。

保留IP地址

在IPv4 的几类地址中，有几个保留的地址空间不能在互联网上使用。这些地址用于特殊目的，不能在局域网外部路由。

IP 地址构造和分类

IP 地址由 网络标识 和 主机标识 两部分组成，网络标识代表着网络地址，主机标识代表着主机地址。网络标识在数据链路的每个段配置不同的值。网络标识必须保证相互连接的每个段的地址都不重复。而相同段内相连的主机必须有相同的网络地址。IP 地址的 主机标识 则不允许在同一网段内重复出现。

子网

为了确定网络区域，分开主机和路由器的每个接口，从而产生了若干个分离的网络岛，接口端连接了这些独立网络的端点。这些独立的网络岛叫做子网

上图一共有6个子网，因为根据定义，分开主机和路由器的每个接口所产生的网络岛都算一个子网。

子网掩码

子网掩码(subnet mask) 又叫做网络掩码，它是一种用来指明一个 IP 地址的哪些位标识的是主机所在的网络。子网掩码用于屏蔽 IP 地址的一部分以区别网络标识和主机标识。 比如说：

上图中子网掩码有24位，也就是高位的24位相同的计算机IP地址属于一个子网。剩下的8位用来作为主机标识。也就是说，我们只要知道子网掩码，就可以计算出这个子网中最多有多少计算机(需要减去 0.0.0.0 和1.1.1.1)

从上面的介绍也可以看出，在一个子网中，如果主机多的话，是很容易导致地址冲突的，为此我们接下来要介绍动态地址分配协议: DHCP

DHCP

DHCP 的全称是： Dynamic Host Configuration Protocol .

首先在这个子网中有一个跑着DHCP的 Server. 它能帮助主机自动配置地址。

DHCP server和client 之间的对话过程如上图所示。

  • 一开始client是没有地址的，因此默认为 0.0.0.0，向全域进行广播(广播地址是 255.255.255.255)。
  • DHCP server听到后会给予回应，向需要IP的主机提供IP地址(以下图为例): 223.1.2.4, 网络掩码: 223.1.2.0/24, 默认路由器: 223.1.2.5 以及本地DNS服务器的IP地址.
  • client收到后还是进行广播(因为此时仍然没有给其分配地址)
  • 最后DHCP server会响应DHCP ACK报文，此时client正式拥有了地址

这边IP地址是有租约的，为3600秒，在这之后如果主机还在线，则可以续约。

DHCP不光会告诉你在子网的IP地址，还会告诉你DNS，网关和子网掩码。

DHCP是应用层协议，其底层是通过UDP实现的。

路由聚集

ISP会下发IP地址，同时通告那些IP地址是我管辖的。

ISP又会向ICANN申请地址。

那么路由聚集有什么好处呢？ 答：可以方便管理。因为我总不能每买一台电脑就像电信局打电话申请一个IP地址，肯定是在一个子网里面分配地址。这样一来，意味着一个子网只通过接入IP地址的部分前缀和外部因特网相连, 外界并不关心子网内还存在着多个组织, 这种使用单个网络前缀通告多个网络的能力通常称为路由聚集。而且这个做法相当大地减少了在这些路由器中转发表的长度.

那么子网中不同的电脑怎么和外界进行交流呢？ 比如下图，子网中有三台电脑，IP地址各不相同，但是出去的时候，都是一个地址 138.76.29.7 . 在子网中，通过不同的端口来判断不同的主机

  • 10.0.0.1 这个主机要通过3345端口发送一条信息
  • 信息交给NAT router之后，就变成 138.76.29.7 ，5001端口发出
  • 反馈信息在138.76.29.7 的5001端口收到之后，经过NAT router之后就传到变成10.0.0.1的3345串口

IPV4

IPv4 的全称是 Internet Protocol version 4，是 Internet 协议的第四版。IPv4 是一种无连接的协议，这个协议会尽最大努力交付数据包，也就是说它不能保证任何数据包能到达目的地，也不能保证所有的数据包都会按照正确的顺序到达目标主机，这些都是由上层比如传输控制协议控制的。也就是说，单从 IP 看来，这是一个不可靠的协议。

前面我们讲过网络层分组被称为 数据报，所以我们接下来的叙述也会围绕着数据报展开。

IPv4 的数据报格式如下

上图我们也看出来了，TCP和数据报报文段首部都是20字节，加在一起，40字节是必要的。

在IP数据报中有很多信息：

  • 版本字段(Version)占用 4 bit，通信双方使用的版本必须一致，对于 IPv4 版本来说，字段值是 4。
  • 首部长度(Internet Header Length) 占用 4 bit，首部长度说明首部有多少 32 位(4 字节)。由于 IPv4 首部可能包含不确定的选项，因此这个字段被用来确定数据的偏移量。大多数 IP 不包含这个选项，所以一般首部长度设置为 5， 数据报为 20 字节 。
  • 服务类型(Differential Services Codepoint，DSCP) 占用 6 bit，以便使用不同的 IP 数据报，比如一些低时延、高吞吐量和可靠性的数据报。服务类型如下表所示

  • 拥塞通告(Explicit Congestion Notification，ECN) 占用 2 bit，它允许在不丢弃报文的同时通知对方网络拥塞的发生。ECN 是一种可选的功能，仅当两端都支持并希望使用，且底层网络支持时才被使用。 最开始 DSCP 和 ECN 统称为 TOS，也就是区分服务，但是后来被细化为了 DSCP 和 ECN。

  • 数据报长度(Total Length) 占用 16 bit，这 16 位是包括在数据在内的总长度，理论上数据报的总长度为 2 的 16 次幂 - 1，最大长度是 65535 字节，但是实际上数据报很少有超过 1500 字节的。IP 规定所有主机都必须支持最小 576 字节的报文，但大多数现代主机支持更大的报文。当下层的数据链路协议的最大传输单元（MTU）字段的值小于 IP 报文长度时，报文就必须被分片。

  • 标识符(Identification) 占用 16 bit，这个字段用来标识所有的分片，因为分片不一定会按序到达，所以到达目标主机的所有分片会进行重组，每产生一个数据报，计数器加1，并赋值给此字段。

  • 标志(Flags) 占用 3 bit，标志用于控制和识别分片，这 3 位分别是

    • 0 位：保留，必须为0；
    • 1 位：禁止分片（Don’t Fragment，DF），当 DF = 0 时才允许分片；
    • 2 位：更多分片（More Fragment，MF），MF = 1 代表后面还有分片，MF = 0 代表已经是最后一个分片。

    如果 DF 标志被设置为 1 ，但是路由要求必须进行分片，那么这条数据报回丢弃

  • 分片偏移(Fragment Offset) 占用 13 位，它指明了每个分片相对于原始报文开头的偏移量，以 8 字节作单位。

  • 存活时间(Time To Live，TTL) 占用 8 位，存活时间避免报文在互联网中迷失，比如陷入路由环路。存活时间以秒为单位，但小于一秒的时间均向上取整到一秒。在现实中，这实际上成了一个跳数计数器：报文经过的每个路由器都将此字段减 1，当此字段等于 0 时，报文不再向下一跳传送并被丢弃，这个字段最大值是 255。

  • 协议(Protocol) 占用 8 位，这个字段定义了报文数据区使用的协议。协议内容可以在 https://www.iana.org/assignments/protocol-numbers/protocol-numbers.xhtml 官网上获取。比如值为6表明交给TCP, 值为17表明交给UDP.

  • 首部校验和(Header Checksum) 占用 16 位，首部校验和会对字段进行纠错检查，在每一跳中，路由器都要重新计算出的首部检验和并与此字段进行比对，如果不一致，此报文将会被丢弃。

  • 源地址(Source address) 占用 32 位，它是 IPv4 地址的构成条件，源地址指的是数据报的发送方

  • 目的地址(Destination address)占用 32 位，它是 IPv4 地址的构成条件，目标地址指的是数据报的接收方

  • 选项(Options) 是附加字段，选项字段占用 1 - 40 个字节不等，一般会跟在目的地址之后。如果首部长度 > 5，就应该考虑选项字段。

  • 数据 不是首部的一部分，因此并不被包含在首部检验和中。

IPv4 分片

一个链路层帧能承载的最大数据量叫做最大传输单元(Maximum Transmission Unit, MTU)，每个 IP 数据报封装在链路层帧中从一台路由器传到下一台路由器。因为每个链路层所支持的最大 MTU 不一样，当数据报的大小超过 MTU 后，会在链路层进行分片，每个数据报会在链路层单独封装，每个较小的片都被称为 片(fragement)。

每个片在到达目的地后会进行重组，准确的来说是在运输层之前会进行重组，TCP 和 UDP 都会希望发送完整的、未分片的报文，出于性能的原因，分片重组不会在路由器中进行，而是会在目标主机中进行重组。

当目标主机收到从发送端发送过来的数据报后，它需要确定这些数据报中的分片是否是由源数据报分片传递过来的，如果是的话，还需要确定何时收到了分片中的最后一片，并且这些片会如何拼接一起成为数据报。

针对这些潜在的问题，IPv4 设计者将 标识、标志和片偏移放在 IP 数据报首部中。当生成一个数据报时，发送主机会为该数据报设置源和目的地址的同时贴上标识号。发送主机通常将它发送的每个数据报的标识 + 1。当某路由器需要对一个数据报分片时，形成的每个数据报具有初始数据报的源地址、目标地址和标识号。当目的地从同一发送主机收到一系列数据报时，它能够检查数据报的标识号以确定哪些数据是由源数据报发送过来的。由于 IP 是一种不可靠的服务，分片可能会在网路中丢失，鉴于这种情况，通常会把分片的最后一个比特设置为 0 ，其他分片设置为 1，同时使用偏移字段指定分片应该在数据报的哪个位置。

IPv4 寻址

IPv4 支持三种不同类型的寻址模式，分别是

  • 单播寻址模式：在这种模式下，数据只发送到一个目的地的主机。

IPv6

随着端系统接入的越来越多，IPv4 已经无法满足分配了，所以，IPv6 应运而生，IPv6 就是为了解决 IPv4 的地址耗尽问题而被标准化的网际协议。IPv4 的地址长度为 4 个 8 字节，即 32 比特， 而 IPv6 的地址长度是原来的四倍，也就是 128 比特，一般写成 8 个 16 位字节。

从 IPv4 切换到 IPv6 及其耗时，需要将网络中所有的主机和路由器的 IP 地址进行设置，在互联网不断普及的今天，替换所有的 IP 是一个工作量及其庞大的任务。我们后面会说。

我们先来看一下 IPv6 的地址是怎样的

  • 版本与 IPv4 一样，版本号由 4 bit 构成，IPv6 版本号的值为 6。
  • 流量类型(Traffic Class) 占用 8 bit，它就相当于 IPv4 中的服务类型(Type Of Service)。
  • 流标签(Flow Label) 占用 20 bit，这 20 比特用于标识一条数据报的流，能够对一条流中的某些数据报给出优先权，或者它能够用来对来自某些应用的数据报给出更高的优先权，只有流标签、源地址和目标地址一致时，才会被认为是一个流。
  • 有效载荷长度(Payload Length) 占用 16 bit，这 16 比特值作为一个无符号整数，它给出了在 IPv6 数据报中跟在鼎昌 40 字节数据报首部后面的字节数量。
  • 下一个首部(Next Header) 占用 8 bit，它用于标识数据报中的内容需要交付给哪个协议，是 TCP 协议还是 UDP 协议。
  • 跳限制(Hop Limit) 占用 8 bit，这个字段与 IPv4 的 TTL 意思相同。数据每经过一次路由就会减 1，减到 0 则会丢弃数据。
  • 源地址(Source Address) 占用 128 bit (8 个 16 位 )，表示发送端的 IP 地址。
  • 目标地址(Destination Address) 占用 128 bit (8 个 16 位 )，表示接收端 IP 地址。

可以看到，相较于 IPv4 ，IPv6 取消了下面几个字段

  • 标识符、标志和比特偏移：IPv6 不允许在中间路由器上进行分片和重新组装。这种操作只能在端系统上进行，IPv6 将这个功能放在端系统中，加快了网络中的转发速度。
  • 首部校验和：因为在运输层和数据链路执行了报文段完整性校验工作，IP 设计者大概觉得在网络层中有首部校验和比较多余，所以去掉了。IP 更多专注的是快速处理分组数据。
  • 选项字段：选项字段不再是标准 IP 首部的一部分了，但是它并没有消失，而是可能出现在 IPv6 的扩展首部，也就是下一个首部中。

IPv6 扩展首部

IPv4 首部长度固定，无法将选项字段加入其中，取而代之的是 IPv6 使用了扩展首部

扩展首部通常介于 IPv6 首部与 TCP/UDP 首部之间，在 IPv4 中可选长度固定为 40 字节，在 IPv6 中没有这样的限制。IPv6 的扩展首部可以是任意长度。扩展首部中还可以包含扩展首部协议和下一个扩展字段。

IPv6 首部中没有标识和标志字段，对 IP 进行分片时，需要使用到扩展首部。

具体的扩展首部表如下所示

下面我们来看一下 IPv6 都有哪些特点

IPv6 特点

IPv6 的特点在 IPv4 中得以实现，但是即便实现了 IPv4 的操作系统，也未必实现了 IPv4 的所有功能。而 IPv6 却将这些功能大众化了，也就表明这些功能在 IPv6 已经进行了实现，这些功能主要有

  • 地址空间变得更大：这是 IPv6 最主要的一个特点，即支持更大的地址空间。
  • 精简报文结构: IPv6 要比 IPv4 精简很多，IPv4 的报文长度不固定，而且有一个不断变化的选项字段；IPv6 报文段固定，并且将选项字段，分片的字段移到了 IPv6 扩展头中，这就极大的精简了 IPv6 的报文结构。
  • 实现了自动配置：IPv6 支持其主机设备的状态和无状态自动配置模式。这样，没有 DHCP 服务器不会停止跨段通信。
  • 层次化的网络结构： IPv6 不再像 IPv4 一样按照 A、B、C等分类来划分地址，而是通过 IANA -> RIR -> ISP 这样的顺序来分配的。IANA 是国际互联网号码分配机构，RIR 是区域互联网注册管理机构，ISP 是一些运营商（例如电信、移动、联通）。
  • IPSec：IPv6 的扩展报头中有一个认证报头、封装安全净载报头，这两个报头是 IPsec 定义的。通过这两个报头网络层自己就可以实现端到端的安全，而无需像 IPv4 协议一样需要其他协议的帮助。
  • 支持任播：IPv6 引入了一种新的寻址方式，称为任播寻址。

IPv6 地址

我们知道，IPv6 地址长度为 128 位，他所能表示的范围是 2 ^ 128 次幂，这个数字非常庞大，几乎涵盖了你能想到的所有主机和路由器，那么 IPv6 该如何表示呢？

一般我们将 128 比特的 IP 地址以每 16 比特为一组，并用 : 号进行分隔，如果出现连续的 0 时还可以将 0 省略，并用 :: 两个冒号隔开，记住，一个 IP 地址只允许出现一次两个连续的冒号。

下面是一些 IPv6 地址的示例

  • 二进制数表示

  • 用十六进制数表示

  • 出现两个冒号的情况

如上图所示，A120 和 4CD 中间的 0 被 :: 所取代了。

如何从 IPv4 迁移到 IPv6

我们上面聊了聊 IPv4 和 IPv6 的报文格式、报文含义是什么、以及 IPv4 和 IPv6 的特征分别是什么，看完上面的内容，你已经知道了 IPv4 现在马上就变的不够用了，而且随着 IPv6 的不断发展和引用，虽然新型的 IPv6 可以做到向后兼容，即 IPv6 可以收发 IPv4 的数据报，但是已经部署的具有 IPv4 能力的系统却不能够处理 IPv6 数据报。所以 IPv4 噬需迁移到 IPv6，迁移并不意味着将 IPv4 替换为 IPv6。这仅意味着同时启用 IPv6 和 IPv4。

那么现在就有一个问题了，IPv4 如何迁移到 IPv6 呢？这就是我们接下来讨论的重点。

标志

最简单的方式就是设置一个标志日，指定某个时间点和日期，此时全球的因特网机器都会在这时关机从 IPv4 迁移到 IPv6 。上一次重大的技术迁移是在 35 年前，但是很显然，不用我过多解释，这种情况肯定是 不行的。影响不可估量不说，如何保证全球人类都能知道如何设置自己的 IPv6 地址？一个设计数十亿台机器的标志日现在是想都不敢想的。

隧道技术

现在已经在实践中使用的从 IPv4 迁移到 IPv6 的方法是 隧道技术(tunneling)。

什么是隧道技术呢？

隧道技术是一种使用互联网络的基础设施在网络之间的传输数据的方式，使用隧道传递的数据可以是不同协议的数据帧或包。使用隧道技术所遵从的协议叫做隧道协议(tunneling protocol)。隧道协议会将这些协议的数据帧或包封装在新的包头中发送。新的包头提供了路由信息，从而使封装的负载数据能够通过互联网络进行传递。

使用隧道技术一般都会建一个隧道，建隧道的依据如下：

比如两个 IPv6 节点(下方 B、E)要使用 IPv6 数据报进行交互，但是它们是经由两个 IPv4 的路由器进行互联的。那么我们就需要将 IPv6 节点和 IPv4 路由器组成一个隧道，如下图所示

借助于隧道，在隧道发送端的 IPv6 节点可将整个 IPv6 数据报放到一个 IPv4 数据报的数据(有效载荷) 字段中，于是，IPv4 数据报的地址被设置为指向隧道接收端的 IPv6 的节点，比如上面的 E 节点。然后再发送给隧道中的第一个节点 C，如下所示

隧道中间的 IPv4 提供路由，路由器不知道这个 IPv4 内部包含一个指向 IPv6 的地址。隧道接收端的 IPv6 节点收到 IPv4 数据报，会确定这个 IPv4 数据报含有一个 IPv6 数据报，通过观察数据报长度和数据得知。然后取出 IPv6 数据报，再为 IPv6 提供路由，就好像两个节点直接相连传输数据报一样。

通用转发与SDN(软件定义网络)

现在我们来讲通用转发和SDN, 其核心技术OpenFlow通过将网络设备的控制面与数据面分离开来，从而实现了网络流量的灵活控制，使网络作为管道变得更加智能，为核心网络及应用的创新提供了良好的平台。

在前面说的转发中，首先要查找目的IP地址(匹配)，然后将分组发送到特定输出端口(动作)。现在说的通用转发则是在一张表中就实现匹配加动作模式。而基于目的的转发可能意味着路由转发表非常庞大，且功能单一，不具有普遍性

下图就是SDN的模式

利用分层的思想，SDN将数据与控制相分离。在控制层，包括具有逻辑中心化和可编程的控制器，可掌握全局网络信息。在数据层，包括交换机，仅提供简单的数据转发功能，可以快速处理匹配的数据包，适应流量日益增长的需求。两层之间采用开放的统一接口（如OpenFlow等）进行交互。控制器通过标准接口向交换机下发统一标准规则，交换机仅需按照这些规则执行相应的动作即可

使用了这张本地流表，当路由器收到一些垃圾网站的地址时，就可以直接丢弃了，相当于防火墙的功能。

通用转发规则

  • Pattern: match values in packet header fields

  • Actions: for matched packet: drop, forward, modify, matched packet or send matched packet to controller

  • Priority: disambiguate overlapping patterns

  • Counters: #bytes and #packets

下面是一张流表，* 是通配符。比如收到来自1.2.*.* 的数据报就直接丢掉

Openflow 可以通过MAC地址进行匹配,也可以通过IP地址进行匹配。

  • 第一个例子，从 51.6.0.8来的包就转发到port6
  • 第二个例子，只要通过端口号22来的包就直接扔掉
  • 第三个例子，所有来自主机 128.119.1.1 发来的包就直接丢掉
  • 第四个例子，屏蔽了某个特殊的MAC地址

例1

P19. Consider the SDN OpenFlow network shown in Figure 4.30 . Suppose that the desiredforwarding behavior for datagrams arriving at s2 is as follows:

  • any datagrams arriving on input port 1 from hosts h5 or h6 that are destined to hosts h1 or h2 should be forwarded over output port 2;
  • any datagrams arriving on input port 2 from hosts h1 or h2 that are destined to hosts h5 or h6 should be forwarded over output port 1;
  • any arriving datagrams on input ports 1 or 2 and destined to hosts h3 or h4 should be delivered to the host specified;
  • hosts h3 and h4 should be able to send datagrams to each other

Specify the flow table entries in s2 that implement this forwarding behavior

对于S2来说，接口1收到来自h5或者h6的包之后，需要通过接口2来转发给h1或者h2

同样的，接口2收到来自h1或者h2的包之后，需要通过接口1来转发给h5或者h6

因此可以这样写：

匹配 动作
Ingress Port = 1,src= 10.3.*.* ,Dst = 10.1.*.* Forward(2)
Ingress Port = 2,src= 10.1*.* ,Dst = 10.3.*.* Forward(1)

对于第三条要求，从接口1、2收到的数据报，要通过接口3、4定向发送到h3和h4

因此可以这样写：

匹配 动作
Ingress Port = 1,Dst = 10.2.0.3 Forward(3)
Ingress Port = 1,Dst = 10.2.0.4 Forward(4)
Ingress Port = 2,Dst = 10.2.0.3 Forward(3)
Ingress Port = 2,Dst = 10.2.0.4 Forward(4)

对于第四条要求，h3和h4可以通过接口互相传信息

因此可以这样写：

匹配 动作
Ingress Port = 4,src= 10.2.0.4 ,Dst = 10.2.0.3 Forward(3)
Ingress Port = 3 ,src= 10.2.0.3 ,Dst = 10.2.0.4 Forward(4)

匹配 动作
Ingress Port=3 Dst=10.1.*.* Forward(2)
Ingress Port=3 Dst=10.3.*.* Forward(2)
Ingress Port=4 Dst=10.1.*.* Forward(1)
Ingress Port=4 Dst=10.3.*.* Forward(1)

也就是说，来自h3主机的会从s2的接口2转发到s1，并由s1转发到h1、h2,或者再转发到s3, 这样就是顺时针转发

同样的，来自h4主机的包会在s2的接口1直接转发给s3，然后再有s3转发给s1，这就是逆时针方向

控制层面

传统上，控制平面功能与数据平面的转发功能在一起实现，在路由器中作为统一的整体。 但是在SDN中，在数据平面和控制平面做出了明确的分割，在一台分离的”控制器”服务中实现了控制平面功能，该控制器服务与它所控制的路由器转发组件完全分开并远离

在这个部分，我们将学习转发表和流表是如何计算、维护和安装的。下面给出了两种控制平面和数据平面的方案。

每路由器控制：在控制平面中各个路由选择算法相互作用

逻辑集中式控制：一个完全分开的(Normally remote)控制器与本地控制代理交互 这对路由器的计算能力的要求可以没那么高。而且能够统一化接口，对品牌的差异性要求不大。

路由选择算法

路由选择算法的目的是从发送方到接收方的过程中确定一条通过路由器网络的好的路径。 因为无论是每路由器控制方法还是逻辑集中式控制方法，发送过程中必定总是要经过一条定义良好的一连串路由器路径。

在数据结构中，我们学过在图中找一条最短路径的算法，如Djkstra 算法和 Bellman-Ford算法。 它们分别对应着链路状态路由选择算法(link state)和距离向量路由选择方法(distance vector)

链路状态路由选择算法

LS 算法中，所有的链路开销都是已知的。实践中，这是通过让每个节点向网络中所有其他节点广播链路状态分组来完成的。每个链路状态分组包含他所连接的链路的标识和开销。

LS算法的实现就是Djkstra算法，详见我的博客： 最短路径：Dijkstra算法

当LS算法终止时，对于每个节点，我们都能得到从源节点沿着它的最低开销路径的前一节点。以此方式我们可以构建从源节点到所有目的节点的完整路径。

虽然在局域网中，主机的个数有限，因此可以简单的计算，但是整个英特网的节点很多，计算起来会比较麻烦。其算法复杂度平均为 $O(n^2)$， 优化过后可得到 $O(n\log n)$

振荡问题

上图是一个简单的网络拓扑，图中的链路开销等于链路上承载的负载，例如反映要经历的时延。在该例中，链路开销是非对称的，即当在链路$(u,v)$两个方向所承载的负载相同时，$c(u,v)$和$c(v,u)$ 才相等。在上例中，节点z产生发往w的一个单元的流量，节点x也产生发往w的一个单元的流量，并且节点y也产生发往w的一个数量为e的流量。

那么当LS算法再次运行时，节点y (5-5a)确定顺时针到w的路径开销为1，逆时针(一直使用的) 到w的路径开销为1+e。因此y到w的最低开销路径现在变为顺时针的。类似的，x确定其到w的新的最低开销路径也是顺时针的，产生如(5-5b) 中所示的开销。当LS算法下次运行时，节点x、y和z都检测到一条到w的逆时针方向开销为0的路径。它们都将其流量引导到逆时针方向的路由上。

在下次运行LS算法时，x,y,z 又将其流量引导到顺时针方向的路由上。

很显然，这是一种不好的振荡。如何才能防止这样的振荡？一种解决方案可能强制链路开销不依赖于所承载的流量，但那是一种不可接受的解决方案——因为路由选择的目标之一就是要避开高度拥塞的链路。

另一种解决方案就是确保并非所有的路由器都同时运行LS算法，在每个节点上算法的时机也将是不同的。

距离向量路由选择方法

DV算法是一种迭代的，异步的和分布式的算法，而LS算法是一种使用全局信息的算法。其本质是 Bellman-Ford算法。

Bellman-Ford 算法是一种动态规划的算法。那么首先我们来了解一下Bellman-Ford 方程式：

令 $d_x(y)$ 为 x节点到y节点的最小代价，那么

其中，$c(x,v)$ 代表 x到邻居v的距离，$d_v(y)$ 代表邻居 v到y节点的最小代价。我们看到下一张图

我们从u出发，计算到z的距离。

显然$d_v(z) = 5,d_x(z) = 3,d_w(z) = 3$ ,那么

与 LS算法相比，DV算法只知道它邻居的信息，而不掌握全局的拓扑信息。

DV算法的迭代是这样的一个循环：

每个节点都在等待它邻居发来的变化信息，收到以后就重新计算距离，计算完成后把更新后的信息传给它的所有邻居并等待进入下次循环。直到距离不再变化，收敛的时候就停止算法

现在来看一个具体的例子：

DV算法存在的问题

DV算法也存在一些问题。其一就是好消息传播得快，坏消息传播得慢，我们分别讨论。

好消息情况

当x与y之间的距离向量从4变为1时，这是个好消息。

$t_0$ 时刻，y收到了这个变动，更新了它的DV表格，并告诉了它的邻居

$t_1$ 时刻，z收到了y发来的信息，并更新了它的DV表格，这时候，z到x的距离就从5变成2了。然后z也将这个好消息发给它的邻居

$t_2$时刻，y收到了来自z的更新，z告诉y：“我到x的距离只有2啦，可以借助我来更新！”，结果y并不需要更新它的表格了，因为y到x 的距离本来就比2小。至此，算法到这里就结束了，因为DV表都收敛了。

坏消息情况

当x与y之间的距离向量从4变为60时，这是个十足的坏消息。这时候，会发生如下的事：

  1. 在链路开销变化之前，$D_y(x) = 4,D_y(z) = 1,D_z(y)=1,D_z(x)=5$. 在 $t_0$ 时刻，y检测到链路开销变化。y计算它到x的新开销。$D_y(x) = \min{c(y,x)+D_x(x),c(y,z)+D_z(x)}=\min{60+0,1+5}=6$ (因为此时 $D_z(x)$ 尚未更新。这就是我们所谓的路由环路，即为到达x，y通过z路由，z又通过y路由。路由选择环路就像一个黑洞，即目的地为x的分组在 $t_1$ 时刻到达y或者z之后，将在这两个节点之间不停地来回反复，直到转发表再次收敛为止
  2. 因为节点y已经算出到x的新的最低开销，其在$t_1$时刻将该新距离向量通知z
  3. 在$t_1$之后的某个时间，z收到了来自y的新距离向量，他指示了y到x的最低开销是6。z知道它能以开销1到达y，因此计算出到x的新最低开销 $D_z(x) = \min{50+0,1+6}=7$ 。因为z到x的最低开销已经增加了，于是他在 $t_2$时刻通知y其新开销
  4. 以类似的方式，在收到z的新距离向量后，$D_y(x) = \min(60+0,1+7) =8$, 并向z发送其距离向量。接下来z确定$D_z(x) = 9$ 并向y发送其距离向量……
  5. 最终，直到z最终算出它经由y的路径开销大于50为止，算法才能停止，而此时已经过了44次迭代。这就是坏消息传播得慢的原理
增加毒性逆转

那么怎么破解这个问题呢？就是要破这个环路。

如果 $z$ 通过 $y$ 路由选择到目的地x，则z将通告y：“嗨，兄弟，我到x的距离是无穷大！“，也就是告诉y $D_z(x) = \infty$ . 那么，只要z经由y到x，那么z就会持续地向y讲述这个善意的小谎言。因为y相信z没有到x的路径，因此只要z继续经y到x，y将永远不会试图经由z路由选择到x

这时候$D_z(x) = \infty$, 因此$D_y(x) = \min{60+0,\infty} = 60$, 而 $D_z(x) =\min {60+1,50+0} = 50$, 最后 $D_y(x) = \min{50+1,60+0}=51$

然而，毒性逆转并没有解决一般的无穷级数问题。当涉及到3个或者更多节点(不只是直接相连的两个邻居节点)的环路，将无法使用毒性逆转技术检测到

LS和DV的对比

LS DV
报文复杂度 每次更新O(nE) 条信息 只在邻居间交换，时间不等
收敛速度 要求 $O(nE)$个报文的$O(n^2)$算法 收敛较慢，有时会遇到选择环路
鲁棒性 较为鲁棒，路由计算较为分离 鲁棒性较差，会将错误扩散至整个网络

AS内：OSPF

事实上，因特网是网络的网络，它并不是扁平的。我们把一个局域网叫做 AS(autonomous systems)。然后定义局域网内部的路由选择为 （intro-AS routing), 局域网和局域网之间的路由选择为 (inter-AS routing)

在同一个局域网内，采用相同的路由选择算法。我们通常使用 OSPF 路由

OSPF即开放最短路优先，它是一种链路状态协议，并使用Dijkstra来计算转发表。

OSPF的优点：

  • 安全 ，它可以在密码学上通过一些方法来保证数据不能被恶意篡改，另外能确定是某个人发出的信息，不能冒名顶替
  • 允许有多条相同开销的路径 。这就是说，当存在多条相等开销的路径时，无需仅选择单一的路径来承载所有的流量
  • 对单播与多播路由选择的综合支持较好
  • 支持在单个AS中的层次结构

OSFP 协议 试运行在 应用层上的。

AS之间的路由选择：BGP

在ISP之间进行路由选择，就需要一个BGP协议

BGP 的全程是 Broder Gateway Protocol 边界网关协议。其无疑是所有因特网协议中最重要的。正式这个协议将因特网中数以千计的ISP黏合起来。对于自治系统AS之间的路由选择，要使用OSPF协议那样代价作为度量来寻找最佳路由是不现实的。比较合理的做法是在自治系统之间交换“可达性”信息。例如，告知相邻路由器：达到目的网路N可经过自治系统$AS_x$。在BGP的世界中，在路由器的转发表将具有形式为$(x,I)$的表项，其中x是一个前缀，如(138.16.68/22)，I 则是该路由器的接口之一的接口号

作为一种AS间的路由选择协议，BGP为每台路由器提供了这样的服务：

  • 从邻居AS获得前缀的可达性信息，BGP允许每个子网向因特网的其它部分通告：”嗨！我在这！”。 如果没有BGP，每个子网将孤独地存在
  • 确定到该前缀的“最好的”路由。最好的路由将基于策略以及可达性信息来确定

通告BGP路由信息

对于每个AS，每台路由器要么是一台网关路由器(gateway router)，要么是一台内部路由器(internal router).网关路由器是一台位于AS边缘的路由器，它直接连接到AS中的一台或者多台路由器。内部路由器仅连接在它自己AS中的主机和路由器。

如图所示， BGP 按照运行方式分为 EBGP（External/Exterior BGP）和 IBGP（Internal/Interior BGP）。

EBGP：运行于不同 AS 之间的 BGP 称为 EBGP。为了防止 AS 间产生环路，当 BGP 设备接收 EBGP 对等体发送的路由时，会将带有本地 AS 号的路由丢弃。

IBGP：运行于同一 AS 内部的 BGP 称为 IBGP。为了防止 AS 内产生环路， BGP 设备不将从IBGP 对等体学到的路由通告给其他 IBGP 对等体，并与所有 IBGP 对等体建立全连接。为了解决 IBGP 对等体的连接数量太多的问题， BGP 设计了路由反射器和 BGP 联盟。

考虑下面这张图，AS内部的短虚线是IBGP，AS之间有长虚线是EBGP。 现在 AS3 要想 AS2发送一个BGP报文，告知 x 存在并位于AS3中。

在这个过程中:

网关路由器3a先向网关路由器2c发送了一个eBGP报文“AS3 x”。

网关路由器2c然后向AS2中的所有其他路由器(包括网关路由器2a)发送iBGP报文”AS3 x”

网关路由器2a接下来向网关路由器1c发送一个eBGP报文“AS2 AS3 x”

最后，网关路由器1c使用iBGP向AS1中的所有路由器发送报文”AS2 AS3 x”。

在这个过程完成之后，在AS1和AS2中的每个路由器都知道了x的存在并且也都知道了通往x的AS路径

再来看一个例子，当路由器1c到路由器3a附加了一条物理链路之后，在这种情况下，从AS1到x有两条路径：经过路由器1c的路径AS2 AS3 x以及经过路由器1d的新路径 AS3 x

确定最好的路由

就像上面的图一样，从一个给定的路由器到一个目的子网可能有多条路径。事实上，因特网中的路由器常常接收到很多不同的可能路径的可达性信息。

那么，一台路由器怎么在这些路径中进行选择呢？

我们首先来了解一些BGP属性：AS-PATH 和 NEXT-HOP

AS-PATH 属性包含了已经通告过的 AS的列表，如我们在前面的例子中所见。当一个前缀通过某AS时，该AS将其$ASN$ 加入 AS-PATH 中的现有列表。此外，AS-PATH 还可以用来检测和防止通告环路，因为如果一台路由器在列表中看到了包含他自己的AS，它将拒绝该通告

NEXT-HOP 是 AS-PATH 起始的路由器接口的IP地址。我们还是那上面这张图为例：
对于AS1通过AS2到x的路由“AS2 AS3 x” ，其属性 NEXT-HOP 是路由器2a最左端的接口的IP地址;
对于AS1绕过AS2到x的路由”AS3 x” ，其NEXT-HOP 是路由器3a的下侧接口

热土豆路由选择

对于 AS 间的路由选择，路由器要如何学习到哪些网络可供转发？BGP 路由选择的原理是热土豆路由选择，即从所有路由中选择到开始该路由的 NEXT-HOP 路由器具有的最小开销作为学习的信息。通过热土豆路由选择添加 AS 外前缀的步骤如图所示，当 路由表学习可达性信息时，BGP 协议和 AS 内路由选择协议(OSPF 协议)需要协同工作。

热土豆路由选择的思想是：将分组发给最近的网关路由器，用尽可能最低开销将分组送出其所在 AS。之所以称之为热土豆，就是当分组被类比为“热土豆”时，由于烫手，所以我们要尽可能快地把“热土豆”扔给下一个人。因此热土豆路由选择是一种自私的算法，它只考虑到减小自己 AS 内传输分组的开销，但是忽略了 AS 外端到端的其他开销。

比如说下面这个例子：

现在 路由器1b想发送给x信息，有两条路由可以走：AS2 AS3 x和AS3 x. 假设开销定义为需要穿越的链路数，那么如果选择AS2 AS3 x ，NEXT-HOP 为 2a最左侧接口，最低开销为 2， 如果选择 AS3 x ，NEXT-HOP 则为3d的最左端接口，开销为3。 这时候，虽然我们从上帝视角看选择路由 AS3 x 更快，但是这颗热土豆太烫手了，1b想要尽快的把这个烫手的山芋扔给下一个人，那么它还是会选择AS2 AS3 x这条路径。

因而，热土豆路由选择是自私的算法，即他试图在减小他自己AS中的开销，而忽略在其AS之外的端对端开销的其他部分。

路由器选择算法

在实践中，BGP使用了一种比热土豆路由选择更复杂但却结合了其特点的算法。我们知道BGP的路由选择算法的输入是到某前缀的所有路由的集合。如果到相同的前缀有两条或者多条路由，则顺序调用下列消除规则直到余下一条路由。

  1. 路由被指派一个本地偏好(local preference) 值作为其属性之一。一条路由的本地偏好可能由该路由器设置或者可能由在相同AS中的另一台路由器学习到 。本地偏好属性的值是一种策略决定，它完全取决于AS的网络管理员。具有最高本地偏好值的路由将被选择
  2. 从余下的路由中(现在都具有相同的最高本地偏好值)，将选择具有最短的AS-PATH路由。如果该规则是路由选择的唯一规则，那么BGP将使用DV算法决定路径，其中距离的测度使用AS跳的跳数而不是使用路由器跳的跳数
  3. 从余下的路由中(现在都具有最高本地偏好值和相同的AS-PATH长度)，使用热土豆选择，即选择具有最靠近 NEXT-HOP路由器的路由
  4. 如果仍留下多条路由，该路由器使用BGP标识符来选择路由。

这样，回到上面这个例子。

首先使用规定1(这里假设都具有最高的本地偏好值)

然后使用规定2，选择出最短的AS-PATH。因此将直接使用 AS3 x 路由。我们看到, BGP此时不再使用一种自私的算法了。

SDN 控制平面

下图提供了一个通用的SDN控制器详尽的示意图。控制器的功能大体可以分为3个层次，我们以一种非典型的自底向上的方式考虑这些层次：

  • 通信层： SDN 控制器和受控网络设备之间的通信。如果SDN控制器需要控制远程的机器运行，需要一个协议来传送控制器与这些设备的信息。如上图所示，这个协议构成了控制器体系结构的最底层。 控制器和受控设备之间的通信跨越了一个接口，他现在被称为控制器的南向接口
  • 网络范围状态管理层：由SDN控制平面做出的最终控制决定，将要求控制其具有 有关网络的主机、链路、交换机等设备的最新状态信息。
  • 对于网络控制应用程序层的接口：控制器通过其北向API 与网络控制应用程序交互。该API允许网络控制应用程序在状态管理层之间 读写网络状态和流表。 当状态改变事件发生时，应用程序能够注册进行通告。

例题

1

前面讲过路由器和链路层交换机都被称为分组交换机. 路由器与链路层交换机间的根本区别是什么?

答:
路由器和链路层交换机的根本区别是它们服务于不同的网络层协议. 链路层交换机基于链路层帧中的字段值做出转发决定, 服务于第二层链路层; 路由器基于网络层数据报中的首部字段值做出转发决定, 服务于第三层网络层.

2

讨论为什么在高速路由器的每个输入端口都存储转发表的影子副本.

答：

首先一个路由器是有很多个输入端口的, 转发行为的第一步是在转发表中查找输出接口. 如果每个输入端口都并发地调用路由选择器查找输出接口必然会产生时延. 所以要在高速路由器的每个输入端口都存储转发表的影子副本, 使转发决策能在每个输入端口本地做出,避免了集中式处理的瓶颈.

3

路由器有IP地址吗? 如果有, 多少个?

  • 路由器有IP地址, 这里的有IP地址并不是说有一个IP地址标志一台路由器. 而是说路由器的一个输入或输出端口对应着一个IP地址.
  • 所以一个路由器拥有的IP地址数是不确定的, 假如一个路由器有一个输入端和两个输出端, 那么对应地就有三个IP地址, 分别对应三个端口.
4

什么时候一个大数据报分割成多个较小的数据报? 较小的数据报在什么地方装配成一个较大的数据报?

  • 网络层的数据报需要往下经过链路层封装成链路层帧才能放上链路开始传输. 然而一个链路层帧的载荷大小根据链路层协议的不同而不同, 数据报的大小不能超过一个链路层帧的最大传送单元(Maximum Transmission Unit, MTU). 所以当链路层遇到大于自身MTU的数据报时需要把数据报分割成多个较小的数据报. 这项工作将放到端系统中进行, 因为如果在路由器中进行的话会大大降低路由器的性能.
  • 较小的数据报在目的端系统的网络层进行装配.
-------------本文结束，感谢您的阅读-------------