基础概念

在应用层和运输层已经将数据封装好了，网络层所做的工作就是把数据尽可能传输过去，其中的难点在于选择传输的路径。有些传输算法可能导致需要经过4个路由器，而有的只需要两个。

  • 转发： 从输入接口转移到输出接口，是路由器内部过程。路由器本身有许多个接口，可能要从一个接口输入再从另一个接口输出。
  • 路由选择： 选择从源到目的地的路径。

路由器中的一个关键元素就是转发表，它决定了这个路由器可以传输到哪些路由器，

路由器工作原理

路由器的组件有：

  • 输入端口： 输入端口负责接收数据和查找。查找指的是通过转发表找到输出端口。这里的端口并不是逻辑端口（如计算机上的端口）而是交换机上实实在在的端口。
  • 交换结构： 将输入端口连接到输出端口
  • 输出端口：
  • 路由选择处理器： 它是操作转发表的结构。它通过路由选择协议来改变维护转发表

输入端口处理

例如：

目的地址范围 链路接口
0xC8171000 - 0xC81717FF 0
0xC8171800 - 0xC81718FF 1
0xC8171900 - 0xC8171FFF 2
其他 3

可以看到他们的范围中前缀都是一样的，因此我们可以使用前缀来表示范围

前缀 接口
1100 1000 0001 0111 0001 0 0
1100 1000 0001 0111 0001 1000 1
1100 1000 0001 0111 0001 1 2
其他 3

从最高位向最低位匹配，寻找最长的匹配项。这种比较是在硬件中实现的，速度在纳秒级别。

交换

交换就是从输入端口到输出端口的过程，交换也有多种实现方式。

  • 经内存交换： 经内存交换是在路由选择处理器的直接控制之下完成的。处理器决定输出端口并且将数据输送到输出窗口的缓存中
  • 经总线交换： 输入端口通过一条共用的总线传递，这条总线连接所有的输出端口。然后在输入端口处贴上一个标签然后在总线处决定具体要传输到哪条总线，在输出端口消除标签
  • 经互联网络交换： 如图2，这种模式可以并行的转发多个分组，但是输出总线一次只能运输一条数据，因此如果有多个数据到了同一个输出端口还需要等待。

排队

输入排队

如果交换速率不够快，例如输入速率为v，交换速率为1.5v,有两个输入口进入同一个输出端口，那么两个输入口接收完毕之后还必须等N / 3v时间。而如果交换速率>=2v,那么就可以边输入边转移，当输入完毕时全部转移到输出接口（理想情况）

输出排队

当有许多个输入分组到达同一个输出端口时就会导致数据的积累，输出端口中有一个缓存，但是如果持续的输入到这个缓存中便会使缓存满，缓存满要么丢弃已有分组，要么拒绝新接收的分组，都会导致丢包。

现在一般都有丢弃不重要分组的机制，但是具体丢弃哪些分组就涉及到了分组调度

分组调度

先进先出

优先权排队

优先权高的在前面，同一优先权先来先服务。有时每个优先权都有自己的队列。

循环和加权公平排队

同样有多个队列，输入到同一队列中的归为一队。最简单的方式就是先服务第一队，再服务第二队，这样依次循环下去。

其次还可以为每一类赋一个加权值w，然后每个类的服务时间是 w / w总

IPv4

数据报格式

  • 版本： 指的是IPv4协议的版本
  • 首部长度： 因为有可变长度的选项，所以要表明首部长度
  • 服务类型： 讲一些需要低时延、高吞吐量的数据报和可靠性的数据报分开来
  • 数据包长度： 总长度
  • 标识、标志、位偏移： 和IP分片有关
  • 寿命（TTL）： 确保数据包不会永远由于路由选择环路在网络中循环。每当一台路由器处理数据报时，TTL-1
  • 协议： 只有到目的地才会使用。指示了要交给哪个运输层协议。例如6代表要交给TCP，17则要交个UDP
  • 首部检验和： 计算过程为： 每两个字节当成一个数，然后求和再取反码。

数据报分片

由于在链路层所能一次输送的数据量不一致并且可能小于数据报，因此可能会出现把一个数据报拆分成若干个小数据报然后合并的事件。这个时候就要使用标识位来标识这是第节个小数据报，每发送一个就让他加一。标志位是为了区分最后一个小数据报的，最后一个小数据报标志位是0，其他都是1，这样一旦检测到0就可以立刻合并。

编址

我们将主机和物理链路之间的边界叫接口，通常主机只有一个接口，而交换机有多个接口。

如图一个路由器连接着一些主机，可以看到有些主机前缀相同。

例如： 223.1.1.1 和 223.1.1.2 和 223.1.1.3 和 223.1.1.4前面24位都相同。可以把这些前缀相同的主机看成一个小的网络，而这些网络之间通过交换机进行连接。

我们可以把前缀相同的记成223.1.1.0/24，其中/24可以称为子网掩码，他表示这条线路之后的前24位都相同。

一般来讲每一个ISP或组织机构都会分配一个掩码，然后从本地ISP接入网时都会分配一个掩码下的IP地址，然后本地ISP在一个更大掩码的交换机下。但是组织不是固定不变的，并且更换IP所需工作量巨大， 如果它跑到另一个地区并且在那里接入网络这时就会出现查无此机的现象（因为数据一定会分发到原来的ISP下）

考虑这样的情况223.1.1.1跑到了223.1.3.1的地盘，而数据还是从223.1.1.0/24接口转发。

为了解决这个问题，在接入新的网络时上层交换及还要接受和新转入主机有关的数据并且采用最长前缀匹配。也就是说223.1.3.0/24还需要接收223.1.1.1的数据

地址分配

当一个ISP从一个管理IP地址的机构那获得了一块地址之后，通常情况下还需要考虑把这片地址继续向下划分。

例如某个学校获得了一块地址200.32.8.0/21,现在需要分配给各个学院地址，假设分别需要分配1000， 500， 200， 201个地址

注意： 开始200.32.8.0/21的空间没有人使用，可以随意分配。也就是说这片空间可以划分成200.32.000010/00.0 /22和200.32.000011/00.0 /22

  • 首先我们可以分配200.32.00001000.0/22 给需要1000的学院。
  • 之后200.32.00001100.0 /23 给500的学院
  • 之后分配200.32.00001110.0 /24 给200的学院
  • 分配200.32.00001111.0 /24 给201的学院

我们可以分配00001000 /22给1000的学院是因为在路由表中200.32.8.0/21和200.32.8.0/22是不同的

之后因为000010/00.0 的空间全部划分给了第一个学院，现在这部分空间是不能动的。因此我们可以动的是000011/00.0的空间

然后从000011/00.0的空间中划分出512的空间，也就是0000110/0.0的空间，此时还剩下0000111/0.0的空间可以使用。

然后分别把00001110/.0的空间和00001111/.0的空间分配出去

DHCP

现在用户是经常移动的，每移动到新地区就需要拥有对应的掩码，不然就无法联网。为了处理移动用户，便专门使用动态主机配置协议（DHCP）

DHCP是在某个ISP或接口处连接一个DHCP服务器，或者至少给出处理该接口的DHCP服务器IP地址。通过DHCP服务器，我们可以动态的分配IP。

连接过程：

  • DHCP服务器发现： 一台新到达的主机首先要发现负责的DHCP服务器，这可以使用DHCP发现报文。用户使用UDP向67端口发送发现报文。并且它的目的地址是255.255.255.255（广播目的地址）并且本地IP设定为0.0.0.0.
  • DHCP服务器提供： 当DHCP服务器收到DHCP发现报文时，会发一个返回报文，这个报文的目的地址也是255.255.255.255（发现报文没告诉源地址，也没有源地址），如果有几台响应，那么就根据向客户推荐IP数量，IP地址有效时间等因素挑最好的。
  • DHCP请求：
  • DHCP ACK：

NAT

在一些小家庭中的网络可能编址一模一样（因为之间开始并没有联系也没有连接到互联网），但是 如果小家庭中的网络连接到互联网时怎么办呢？如果不进行地址转换，可能会导致成千上万个重复地址。这时就需要NAT进行转换了。

NAT路由器甚至不像路由器，所有进入家庭网络的报文首先都需要经过它，所有从家庭网络发出的报文首先要经过NAT的转换。它相当于是家庭网络和外界的接口。

所有从家庭网络发出的报文首先要经过NAT，NAT会把端口号改成自己空闲的端口号并且把IP地址改成自己的IP地址（因为家庭网络中的IP对外界而言是无效的，而NAT路由器使用的是DHCP分配的IP）。并且有一张NAT转换表记录了内网的IP和端口号。

响应报文的目的地也是NAT路由器，然后由NAT路由器根据NAT转换表转发给家庭网络内的成员。

NAT穿越

NAT穿越需要解决的问题是让两个内网的主机相互通讯。因为双方都是内网地址，并且双方都只知道内网地址和端口号，直接获得内网地址是没有用的，尤其是在p2p应用如聊天中。

为了解决这个问题，需要一个额外的NAT服务器用来告诉主机经过地址转换之后的地址。首先内网向这个服务器发送一个数据包，然后服务器返回经nat映射下的公网ip和端口号。之后互相交换公网ip后就可以进行通信了。

IPv6

由于IPv4地址即将耗尽，人们不得不开发出地址更多的空间。IPv6有128字节，是IPv4的2^96倍，也就是说不可能被用完。

数据报格式

  • 版本：
  • 流量类型： 和IPv4中服务类型类似
  • 流标签： 用来表示优先级的
  • 有效载荷长度： 表示了跟在40字节数据报后的字节数量（也就是除首部外的大小）
  • 下一个首部： 标识数据报要交给哪个协议
  • 跳限制： 每过一个路由器减一

他和IPv4相比少了

  • 分片： IPv4不允许在路由器中拆分合并。如果IPv6数据报太大而不能传输，路由器只需丢掉数据报然后发送一个分组太大的差错报文即可。
  • 首部检验和： 因为IPv6的设计者认为在应用层和传输层都有了检验和，这里显得有些多余，并且耗时巨大

从IPv4到IPv6的迁移

一种方式是借用现有的IPv6网络，起点和终点是IPv6网络，中间是IPv4网络，我们将中间的IPv4网络称为隧道。首先在IPv6网络中使用IPv6数据报，然后到IPv4部分再套一个IPv4数据报的头部，IPv4数据报的内容就是IPv6数据报，之后在IPv4网络中进行传输。

路由选择算法

我们可以把路由器简化成一个图，图中的节点代表路径，边上的值代表路径之间的消耗（一般由物理长度确定），如果两个路由器之间没有路，那么长度是$\infty$,现在任务简化成了找单源最短路。

路由算法的一种分类方式是根据算法是集中计算还是分类计算来划分。

  • 集中式路由算法： 这种算法在计算开始之前就有全局的网络信息，知道每一个节点的消耗。
  • 分散式路由选择算法： 每个节点只知道部分信息，然后通过这部分信息知道下一步的路径。

链路状态路由选择算法

这种算法是一种集中式算法，每个节点都知道完整的网络信息。在实践中，通常用链路状态广播算法来实现。在知道信息之后，就可以使用Dijkstra算法

距离向量

距离向量算法是一种分散式的路由选择算法。其实这里使用的是Ford算法

一旦(x, v)的值发生改变，那么x和v就会立刻按照这个数据重新计算表，如果表有变化则发送到相邻节点。

首先每个端点对它直接相连的端点的消耗值是清楚的。消耗值是c(x, v)【从x节点到v节点】。

  • 设定从n节点到某个节点（m）的最短距离为 $D_{n}(m)$，初始化距离为从n到m的距离。也就是图中的第一列。
  • 之后首先向各个相邻端点传输一次自己的最短距离表，然后发现和自己表不同并且如果开始时无穷就直接填表
  • 之后按照$disx(y) = min{v \in V and v != x}{c(x, v) + dis_v(y)}$（V是和该点相邻点的集合）更新值（更新值时使用传过来的表），每次更新完成之后就向直接相邻的节点发送更新后的值，然后邻居节点也用上式进行比较，如果有新值也进行更新

更新只需要更新从该节点到其他节点的距离。例如y节点需要更新$D_y(x), D_y(z)$

例如下面这个例子，先只看x。第一步是节点y和节点z将他们的距离发送给x，然后x进行更新

之后如果有更新就把更新发送给其他表，其他标按照上述过程再次进行更新直到没有变化。

也就是说我们需要维护cost(x, y)和D(N, N)两张表，其中cost是从初始节点到其他相邻节点的直接距离，而D(N, N)是两个节点之间的最短距离。

链路故障

上面算法不是完全可靠的，例如x到y的值从2到60。那么我们计算$D_y(x)$时会得到$D_y(x) = min{c(y, x) + D_x(x),\quad c(y,z) + D_z(x)} = min{60 + 0, 1 + 3} = 4$.这毫无疑问是错误的，更重要的是这会导致循环很多次。

这是因为x和y之间链路改变时从z到x的最短链路也改变了，但是这时还没有将更新传到z因此没法获得z到x的最短链路，此时使用过期的值便可能出错。

解决问题的一个方法时首先让到达终点的路变为$\infty$，例如$D_z(x)$ = $\infty$。这样就会先将其他的路径全更新了，待到更新完成之后再换成真实值，然后再进行更新。

自治系统内部的路由选择策略

互联网是一个庞大的系统，如果所有主机都参与路由选择，那么开销是不可估计的，并且不同的机构可能想使用不同的管理策略。因此可以按照机构或地区分成一个个子系统，子系统中可以单独操作。

开放最短路优先（OSPF)

开放最短路优先使用的算法是Dijkstra算法。但是这里有一个管理员设置链路开销，可能会把所有开销设置成1，那么关注的是最少跳数。如果按链路容量反比设置，那么表示不鼓励使用低宽带链路。

并且为了保证链路的健壮性，当链路接入或断开时会第一时间发送信息。如果没有变化也会每隔30分钟发送当前状态信息。

ISP之间路由选择：BGP

如果路由器在自治系统边缘，那么就叫他网关路由器，否则叫他内部路由器。网关路由器负责两个自治系统之间的链接，他们的连接叫外部BGP。反之为内部BGP。

使用BGP选择策略时要传递一些信息，这些信息统称为路由，其中最重要的两个属性是AS-PATH和NEXT-HOP

  • AS-PATH: 指的是已经通过的自治系统的列表，它可以痛啊哦路径并且检测环路。例如从1a到3d，当他到达3a时AS-PATH = “AS2 AS3”,而如果是1d到3d，那么值为AS3

  • NEXT-HOP: 指的是AS-PATH中起始位置的IP地址（注意AS-PATH中不包含起始的自治系统）。例如上面第一个例子NEXT-HOP = 2a左边端口地址。第二个例子NEXT-HOP = 3d左边端口地址。

  • eBGP：外部BGP，从其他的自治区域获得可达性信息

  • iBGP: 内部BGP，从自治区域内部获得可达性信息

热土豆路由选择

热土豆选择算法是一种贪心算法，它的思想是尽快将数据穿输出自己的自治系统。假设我们已经知道了到终点的所有可能路径，然后计算起始点到NEXT-HOP之间的最短开销，然后把这个最短开销对应的接口和终点自治系统记录(x, I)到自己的转发表上

路由器选择算法

路由器选择算法是热土豆选择算法的改进。它对热土豆选择算法加了许多限制。它的运行流程如下

  1. 路由被指定一个本地偏好值。这个值可能由路由器设置或者从相同自治系统中的另一台路由器中学习得到。具有最高本地路由编号值的将被优先选择。
  2. 如果学习偏好值相同，那么寻找最短AS-PATH的路由
  3. 否则，按照热土豆路由选择
  4. 否则，按照BGP标识符选择

IP任播

IP任播服务通常被利用于DNS中，他主要对具有相同内容但是位置不同的服务器进行最佳选择。

例如CDN公司的多台服务器配制了相同的IP地址。然后某台BGP路由器收到了该IP地址的多个路由通告，之后根据路由器选择算法选出最佳的一个。

SDN控制平面

传统路由器和交换机基于IP地址进行转发，而通用转发除了IP地址外，还有许多其他因素如TCP端口、IP协议等用于匹配，匹配完成之后不一定只有转发一个动作，还可能重写、拒绝等等一系列操作。

通用转发是传统转发的拓展，它拓展了匹配和动作的范围。

匹配和动作

在分组交换机中有匹配和动作表，这个表由远程控制器进行维护，这个表又被称为流表，它包含以下内容

  • 首部字段值集合： 这是用于匹配的部分，也就是下图的字段。这些字段可以是空也可以使用正则表达式替代
  • 计数器集合： 计数器可以包括该表项已经匹配的分组数量，还可以记录自上次更新所经过的时间
  • 动作集合： 每个匹配就会对应一个动作。这些动作可以是转发到给定的输出端口，丢弃分组，复制分组和发送到多个输出端口。

如图是OpenFlow(一种通用转发标准）的匹配字段。这些匹配字段实际上就是各个协议的首部字段中一些重要内容。

每个流表项可以有零个或多个动作列表，如果有多个动作，那么这些动作按序执行。

例如我们想把h5的数据发送到h3,并且想要从s3->s1->s2方式进行发送，那么流表为

匹配 动作
s1流表
Ingress Port=1; IP Src=10.3.*.*; IP Dst=10.2.*.* Forward(4)
s3流表
IP Src=10.3.*.*; IP Dst=10.2.*.* Forward(3)
s2流表
Ingress Port=2; IP Dst=10.2.0.3 Forward(3)

其中的Forward表示要把数据发送到哪个输出接口

ICMP：因特网控制报文协议

ICMP被用来进行主机和路由器之间的沟通，它最典型的用途是差错报告。它在体系结构中位于IP之上，换言之ICMP包括IP。

ICMP结构为一个类型字段和一个编码字段，不同的类型和编码组合有不同的作用

ICMP类型 编码 描述
0 0 回显回答
3 0 目的网络不可达
3 1 目的主机不可达
3 2 目的协议不可达
3 3 目的端口不可达
3 6 目的网络未知
4 0 拥塞控制
8 0 回显请求
10 0 路由器发现
11 0 TTL过期
12 0 IP首部损坏

其中回显请求也就是ping命令所发送的。