【网络】计算机网络笔记——网络层简要笔记

网络层主要功能

网络层主要有三个重要的功能——转发路由选择以及连接建立

  • 转发牵涉到在一台路由器中从入链路到出链路的传送。当一个分组到达时,路由器需要根据其内部的转发表来决定其对应的出链路,之后将其移动到适当的输出链路上。
  • 路由选择涉及了网络中所有的路由器,通过路由选择协议的交互从而决定分组从源头到目的地所采用的路径。其中计算这些路径的算法被称为路由选择算法,分为集中式分布式两种,
  • 连接建立主要表示在一些网络层体系结构中,需要从源到目的地之间沿着路径彼此握手,从而使得在规定的源到目的地连接中的网络层数据能在开始流动前建立起状态。

Internet 的网络层主要由三个组件组成:IP 协议、路由选择协议(RIP、OSPF、BGP 等)、ICMP 协议。

分组交换机与路由器

分组交换机一般分为两种,一种主要基于链路层字段中的值进行转发决定,我们往往把它称作链路层分组交换机。而另一种分组交换机则主要是基于网络层中字段的值进行转发决定,我们通常称其为路由器

网络层服务模型

网络服务模型定义了网络层可能提供的服务,主要包括以下的服务:

  • 确保交付:确保分组最终到达目的地
  • 具有时延上界的确保交付:不仅确保交付,并且保证了在特定的时延上界内交付。
  • 有序分组交付:确保分组以其发送的顺序到达目的地
  • 确保最小带宽:保证了只要发送主机以低于特定速率的状态传输数据,则该分组不会丢失。
  • 确保最大时延抖动:确保发送方所发送的两个分组之间的时间差与接收方接收到这两个分组之间的时间差相等。
  • 安全性服务:发送方能够加密向目的主机的所有数据报,目的主机则可以对该数据报进行解密,从而保证数据的机密性。同时提供数据的完整性和源鉴别服务。

但对于我们日常中所使用的 Internet,在网络层仅仅提供了一种尽力而为服务

而比对于 Internet 网络体系,ATM 网络体系则提供了一些可靠性的服务模型,如 CBR(恒定比特率)网络服务以及 ABR(可用比特率)网络服务。其中 CBR 保证了恒定的传输速率,而 ABR 则保证了最小的传输速率。

虚电路及数据报网络

类似运输层,网络层也在两台主机之间提供了两种连接服务——面向连接的虚电路网络以及无连接的数据报网络

虚电路网络

虚电路网络是一种面向连接的服务,它主要有三个过程:

  • 虚电路建立:在建立阶段,发送方运输层与网络层联系,指定了接收方地址,网络层决定发送方与接收方之间的路径,之后为沿着该路径的每一条链路决定一个 VC 号,在沿着该路径的每台路由器的转发表中增加一个表项,表示了出入接口以及出入 VC 号。在建立虚电路期间网络层还可以预留该路径上的资源。
  • 数据的传送:虚电路建立后,数据就可以沿着建立的虚电路进行流动了
  • 虚电路拆除:当发送方运输层通知网络层终止虚电路时,就会启动该阶段,网络层会通知另一侧端系统停止呼叫,并更新路径中每台路由器的转发表从而表示该虚电路已经不存在。

运输层与网络层面向连接服务的不同:运输层的连接建立仅仅涉及了两个端系统,网络中的路由器对这个过程毫无感知。而网络层中的连接建立则涉及了该路径上的每一台路由器,这条路径上的每一台路由器对这个过程都是完全清楚的。

数据报网络

数据报网络是一种无连接的服务,每当一个端系统需要发送分组,它会为该分组加上目的端系统的地址,之后将分组推入网络。其中路由器不维护任何虚电路的状态信息

这个分组从源发送到目的地的过程中,经历一系列路由器的传递,但这些路由器每台都会使用目的地址来转发该分组,每台路由器都有一个将目的地址映射到链路接口的转发表,当分组到达时,它们会根据分组的目的地址在转发表中查找合适的链路接口,之后将该分组向该链路接口转发

最长前缀匹配规则

在数据报网络中我们往往使用类似下面的转发表:

前缀匹配 链路接口
11001000 00010111 00010 0
11001000 00010111 00011000 1
11001000 00010111 00011 2
其他 3

而我们往往在路由器中采用目的地址的前缀与转发表中的表项进行匹配,如果有多个能够与目的地址匹配的前缀,则路由器会采用最长前缀匹配规则,也就是找到前缀匹配的最长项,这样的设计与因特网的编址规则有关。

路由器的工作原理

一般来说路由器由四个部分构成:

  • 输入端口:负责将一条输入的物理链路与路由器相连接,与位于入链路的数据链路层交互,以及负责查找功能,查找路右转发表从而决定输出端口。
  • 交换结构:将输入端口与输出接口相连接
  • 输出端口:存储从交换结构中接收的分组,并在输出链路上传递这些分组
  • 路由选择处理器:执行路由选择协议,维护路由选择表及连接链路状态信息。

输入端口

输入端口中往往会进行如下的处理:

线路端接->数据链路处理(协议,拆封)->查找、转发、排队

输入端口中的查找功能十分重要,转发表一般来说由路由选择处理器进行计算和更新,但每个输入端口往往会持有一份路由转发表的副本从而使得转发决策能在输入端口实现,加快转发速率。

交换结构

交换结构实现了将分组从输入端口输出到输出端口中,主要有内存交换、总线交换、互联网络交换三种方式。

输出端口

输出端口处理取出存放于输出端口内存中的分组然后将其发送到输出链路上。主要是如下的处理:

排队(缓存管理)->数据链路处理(协议,封装)->线路端接->

排队问题

在输入和输出端口中都会有一个分组队列,随着队列的增长,路由器的缓存空间很有可能最终耗尽,造成丢包问题。因此往往在输出端口上有一个分组调度程序,通过一些规则来管理这些分组队列,如果没有足够内存来缓存一个入分组时,会采用其对应的策略来将分组丢弃(如弃尾策略)。

IPv4 协议

IPv4 协议是一个网络层应用十分广泛的协议,也是 Internet 中主要使用的网络层协议。顾名思义,它是 IP 协议的 V4 版本,我们平时所使用的运输层 TCP、UDP 协议正是基于该协议所实现的。

格式

IPv4 数据报的格式如下所示:

œ

其中有如下的关键字段:

  • 版本号:规定了 IP 协议版本,路由器可以根据版本号决定数据报的后续字节该如何解析。
  • 首部长度:由于 IPv4 的数据报在首部中包含了一些可变长度的选项,因此需要这个字段从而确定数据区域从何处开始。
  • 服务类型:这个字段主要为了使得不同类型 IP 数据报能区分开(如一些需要低时延高吞吐量的数据报)
  • 数据报长度:代表了数据报的总长度,有 16bit,也就是说 IP 数据报最大长度为 65535 字节。
  • 标识、标志、片偏移:与 IP 分片有关
  • 寿命:为了防止数据报在网络中循环,每当一台路由器处理该数据报,则这个字段减一,为 0 时数据报会被丢弃。
  • 协议:指示了该数据报的数据部分应该交由哪个运输层协议,如 6 表明了 TCP 协议。通过这一字段可将网络层与运输层绑定到一起。
  • 首部检验和:用于检测收到的数据报是否出现了错误
  • 源和目的 IP 地址:源生成数据报时,在源 IP 字段插入自己的 IP 地址,在目的 IP 字段插入最终的目的地址
  • 选项:允许 IP 首部被扩展,但一般用不到,因此在 IPv6 中被去除
  • 数据:数据报所传输的数据

在无选项的情况下,一个 IPv4 数据报的首部占用 20 字节。

分片

由于某些链路可承载的数据大小有限(最大传输单元 MTU),为了解决这个问题,因此设计者将 IPv4 数据报中较大的数据分片为了多个较小的数据报,当目的主机收到一系列数据报时,会确定这些数据报中某些是否是原来的较大数据报的片,若是片则会在收到了最后一片后,将其按照数据报中的字段拼接到一起形成初始数据报。

因此,在 IPv4 数据报中包含了 标识、标志、片偏移 字段:

  • 标识字段:发送的主机通常将其发送的每一个数据报的标识加 1,通过标识字段即可确定某些数据报是否是同一数据报的分。
  • 标志字段:标志字段有 0、1 两个值,最后一个片的标志部分为 0,而其余片的标志部分均为 0,从而判断该分片是否是最后一个分片
  • 片偏移字段:通过片偏移字段可以确定该分片应该放在 IP 数据报的具体哪个位置。

由于在路由器中重新组装这些分片会影响性能,因此 IPv4 的设计者将分片的组装过程放到了端系统中实现*(分片仍在路由器中进行)

编址

IPv4 的地址有 32 位(4个字节),一般以十进制表示,每个字节之间用点分隔开,如 192.168.0.1,互联网中的每台主机及路由器上的每个接口都有一个唯一的 IP 地址(除了 NAT 这种特殊情况)。

由于 IPv4 的地址只有 32 位,因此其最多只能支持 4294967296 个不同的 IP 地址,这还是算上了一些实际上不能用于公网的地址。看上去 42 亿个 IP 地址十分多,但考虑到目前地球总人口已经超过这个数字,并且每个人不仅仅拥有一个需要联网的电子设备,而且物联网是未来的趋势,显然这些地址的数量是远远不够的。在上个月也就是 2019.11 月,全球的 IPv4 地址已经正式耗尽,关于 IPv4 地址耗尽的解决办法,后面将会提到,我们可以通过 NAT 或 IPv6 来解决。

互联主机接口与路由器接口的网络构成了一个子网,IP 编址时会为该子网分配一个地址,比如 223.1.1.0/24,这种记录方法称为子网掩码,表示 32 个位中左边的 24 位是子网的地址,任何连接到该网络中的主机都需要地址具有 223.1.1.xxx 的形式。

CIDR 编址

Internet 的地址分配策略被称为无类别域间路由选择(CIDR),CIDR 将子网寻址的概念一般化了,对于子网寻址,32 位的 IP 地址被划分为两部分,也具有 a.b.c.d/x 的形式,其中 x 表示地址第一部分的位数。前面的 x 位通常被称为该地址的『前缀』,一个组织一般被分配一块连续地址,也就是具有相同前缀的一块地址,组织内部的设备共享同样的前缀,这也就是为何路由转发表采用了最长前缀匹配原则

比如下图中的例子,ISP A 向外通告了应该向它发送地址前 20 位与 200.23.16.0/20 相符的数据包,而外界并不需要知道在该 ISP 下的组织,每个组织有自己的子网。地址就是像如下这样,分块分配给 ISP,而 ISP 又将其分配给客户组织。

image-20190902140321485

但上面的方式存在一个问题,比如如果 ISP A 获取到了 ISP B,并且让组织 2 通过 ISP B 与互联网连接,那此时对于组织 2 而言,可能需要让其下属的所有路由器及主机都重新进行编号,但这样的措施无疑是代价非常高的。因此我们通常采用的做法是让组织 2 仍然保持 200.23.18.0/23,而 ISP B 则同时通告 199.31.0.0/16 及 200.23.18.0/23 这两个地址。这样在路由选择时,由于最长匹配原则,因此数据能够正常流向 ISP B 下属的组织 2。

分类编制

在使用 CIDR 之前,采用了一种分类编址的方案,它将具有 8、16、24 三种子网地址的子网分别称为 A、B、C 类网络,但这样的方案最大的缺陷就是不够灵活,造成了 IP 地址的浪费。比如这里有一个 300 台主机的组织,此时如果采用 C 类子网,则只能容纳 254 台主机(剩下两个地址用于特殊用途),太小了。而如果使用 B 类子网,则又能容纳 65534 台主机,太大了。这就造成了大量的地址浪费。而 CIDR 则解决了上述问题。

动态获取地址(DHCP 协议)

网络管理员可以通过和 ISP 联系,让 ISP 从它所具有的地址块中提供一部分地址。而 ISP 的地址则是由一个全球性的权威机构 ICANN 来进行管理。

当组织获取到了一块地址后,它就可以为组织内的主机和路由器分配 IP 地址。这个手动配置的过程是非常麻烦的,而且对于一些经常变动的网络,如一些公共场所的网络,手动配置是十分麻烦的。所以往往采用的是动态主机配置协议(DHCP)完成,它允许主机自动获取一个 IP 地址,网络管理员可以对 DHCP 进行配置,从而达到不同的分配策略。比如让一些主机每次连接都能获取到一个相同的地址,或者是被分配一个临时的 IP 地址。

DHCP 是一个应用层协议,基于 UDP 协议进行工作,它基于 C/S 模型,客户端是新到达的主机,它需要获得自身使用的 IP 地址等信息。一般来说,每个子网都将具有一台 DHCP 服务器,若没有这个服务器,则需要通过 DHCP 中继代理(通常是服务器)来连接 DHCP 服务器,这个中继代理知道这个网络的 DHCP 服务器的地址。DHCP 协议一般采用两个端口—— 67 / 68,一般用 68 进行发送,67 进行接收

步骤

DHCP 协议主要分为如下四个步骤:

  1. DHCP 服务器发现:新到达的主机通过发送一个DHCP 发现报文从而实现,该主机需要通过 UDP 分组,向 68 端口发送报文,由于不知道数据报的目的地址,因此采用了广播目的地址 255.255.255.255,并且填入本机源地址 0.0.0.0 从而进行发送。链路层会将该帧广播到所有与该子网连接的子网中。
  2. DHCP 服务器提供:DHCP 服务器收到了 DHCP 发现报文后,会用一个 DHCP 提供报文 向客户响应。由于不知道目的地址,因此同样采用广播目的地址 255.255.255.255,端口号采用 67。由于子网中可能有几个 DHCP 服务器,客户可能有多个提供报文可进行选择。每台服务器提供的报文包含了收到的发现报文的事务 ID、向客户推荐的 IP 地址、网络掩码及IP 地址租用期等信息。
  3. DHCP 请求:新到达的客户从一个或多个服务器中选择一个,向选中的服务器发送一个 DHCP 请求报文 进行相应,回显配置参数。
  4. DHCP ACK:服务器通过 DHCP ACK 报文对 DHCP 请求报文进行响应,证实要求的参数(和 DHCP 提供报文中提供的信息相似)。

DHCP 饥饿攻击

对 DHCP 有一种类似 SYN 洪泛攻击的攻击方式。攻击方通过仿冒 MAC 地址不断向 DHCP 服务器请求 IP 地址,从而耗尽 DHCP 服务器的 IP 地址资源,从而使得 IP 地址无法正常分配。

网络地址转换(NAT 协议)

如果 ISP 已经为一个组织分配过一块连续地址,但此时如果该组织子网变大了该如何处理呢?如果要增大这个子网所分配的连续地址显然是一个工作量十分大的事情。因此出现了一种方案来适应这种场合——网络地址转换(NAT)。

NAT 的核心思路就是一群设备共用同一个 IP 地址,通过端口号来对不同的设备进行区分。它需要依赖于具有 NAT 功能的路由器,这种路由器在 Internet 中看来更像是一个具有单一 IP 的单一设备,它主要负责了转发的功能。它的 IP 由 DHCP 取得,同时在路由器内部又运行了一个 DHCP 服务器,为该路由器控制下的网络的设备提供地址。

它的实现原理就是在 NAT 路由器中维护了一张 NAT 转换表,表项中包含了端口号及 IP 地址,如下所示:

WAN端 LAN端
138.76.29.7:5001 10.0.0.1:3345
...... ......

这张 NAT 转换表就完成了 NAT 网络中的地址到 NAT 路由器上对应端口的映射,而 NAT 路由器就负责了在网络请求过程中对报文中的 IP 地址及端口号的替换,以及报文的转发功能,从而通过端口来扩充支持的主机数量。

两个存在的问题

虽然 NAT 解决了 IPv4 地址短缺的问题,在近几年有广泛的应用。但 NAT 存在一些问题:

  • NAT 的设计不是很合理。端口号本应当是用于为进程编址的,但 NAT 却将端口号也作为了主机编址的一部分。
  • NAT 会影响网络速率。由于数据的传输过程中还需要 NAT 设备对数据包进行修改,这会降低数据传输的效率。
  • 有的协议无法通过 NAT 进行传输。例如 P2P 协议,如果 P2P 应用的对等方在 NAT 后面,则它无法充当服务器接收 TCP 连接,。

对于第一个问题,确实无法解决,NAT 确实是不是非常合理的,但无论其合理与否,它已经成为了 Internet 中非常重要的一个组成部分。

对于第三个问题,可以通过穿透技术解决。例如对于 P2P 应用,可以通过一个『中间对等方』与在 NAT 之后的真正的对等方联系。通过这个中间对等方,可以在两个实际上并不对等的『对等方』之间建立 TCP 连接。这种方式通常叫做连接反转。许多 P2P 应用使用了这种技术来实现 NAT 穿透

NAT 的分类

首先,NAT 分为了静态 NATNAPT 两种。其中静态 NAT 指一个公网的 IP 对应了一个私有的 IP,两者是一对一的,不需要端口号的参与。而 NAPT 使用了端口复用技术,在同一个 IP 地址下,将不同的端口号映射到网络下的不同设备,也就是一对多的方式,这就是我们上面提到的那种 NAT。

我们这里主要讨论 NAPT 的分类,主要有下面四种分类:

  • 完全锥型 NAT:它的 IP、端口都不受限制。A 机器由内而外建立了一个映射(也就是挖了一个洞),此时其他内部 IP、端口不同的 B 机器也可以通过这个洞与外界进行通信。
  • 受限锥型 NAT:它的 IP 受限,但端口不受限。A 机器所建立的映射,不能供内部 IP 地址不同的 B 机器使用,但同一个机器上的不同端口的应用可以公用这个洞。
  • 端口受限性NAT:它的 IP、端口均受限。A 机器指定端口的应用建立的映射,不能供内部 IP 不同的 B 机器以及同一台机器上不同端口的应用使用。
  • 对称型 NAT:对每个外部主机、端口的会话映射为不同的外部端口(洞)。只有来自同一个内部 IP、端口号,并且是同一个目标 IP、端口号的请求才会转换至公网,否则 NAT 会为其配置一个新的公网 IP、端口号。

因特网控制报文(ICMP 协议)

ICMP 协议用于在主机和路由器之间彼此沟通网络层信息,最典型的用途是差错报告。比如应用层很常见的『目的网络不可达』错误就是由 ICMP 中产生的。

ICMP 是基于 IP 协议的,但它不是运输层的功能,因此将其归类为网络层的协议。当主机收到了指明上层协议为 ICMP 的 IP 报文后,就会拆解出 ICMP 的部分,并进行相应处理。

ICMP 是搭配 IPv4 使用的,对于 IPv6,对应的是 ICMPv6

ICMP 报文有一个类型字段及一个编码字段,且包含了该 ICMP 报文首次生成的 IP 首部及前 8 字节内容(从而确定引发差错的数据报)。它的类型、编码对应表格如下:

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

ping 程序的原理

我们平时查看与指定主机连接状态所用到的 ping 程序正是使用 ICMP 报文所实现的。它会发送一个类型为 8 编码为 0 的『回显请求报文』到指定的主机,当看到回显请求后,目的主机会发回一个类型为 0 编码为 0 的 ICMP 『回显回答报文』。

traceroute 的原理

同时,可以用来跟踪与其他主机之间的路由的 traceroute 程序也是通过 ICMP 报文来实现的,它是基于 ICMP 类型 11 编码 0 的『TTL 过期报文』所实现的,它会分别向目的主机发送从 1 开始递增的 TTL 的报文,并且为每个数据报启动定时器。当第 n 个报文到达第 n 个路由器时,由于 TTL 超时会发送 TTL 过期的 ICMP 报文给源主机,这个报文包含了这个路由器的名字及 IP 地址,当该报文到达源主机时,源主机就能从报文中获取需要的信息,并且从定时器中获取到往返时延。

IPv6 协议

IPv6 是上世纪 90 年代为了替代 IPv4 而开发的一种协议,主要原因是因为 IPv4 的地址即将耗尽(如今已经耗尽)。它不但增加了编址的位数,并且对 IPv4 的一些缺点进行了弥补与强化。

格式

可以发现,它的数据报格式与 IPv4 相比有很大不同,它有如下几个关键字段:

  • 版本号:用于标识 IP 的版本号,显然 IPv6 报文中它的值是 6。
  • 流量类型:与 IPv4 中的 TOS 字段类似。
  • 流标签:用于标识一条数据报的流。
  • 有效载荷长度:标明了定长 40 字节首部后的字节数。
  • 下一个首部:标识数据报中的内容所交付的协议(TCP、UDP 等),与 IPv4 中协议字段值相同
  • 跳限制:类似 IPv4 的寿命字段,转发该数据报的每台路由器对其值减 1,当其为 0 时数据报会被丢弃。
  • 源地址、目的地址:共有 128 bit 也就是 16 字节。
  • 数据:IPv6 对有效载荷部分,数据报到达时会从 IP 数据报中移除并交给下一个首部字段指定的协议处理。

与 IPv4 的不同

IPv6 数据报与 IPv4 点最大不同是在于其结构更简单,更高效:

  • 地址容量更大:IPv6 的地址有 128 bit,几乎保证了地球上每粒沙子都能有自己的 IP 地址,并且引入了任播地址,这种地址可以实现数据报交给一组机器中的任意一个。
  • 定长40 字节的首部:IPv6 舍弃了许多 IPv4 中有的字段,它的首部具有 40 字节的固定长度,可以使得对 IP 数据报的处理更快。
  • 流标签与优先级:IPv6 引入了的概念,例如音频、视频的传输就可以当作一个流,并且引入了流量类型字段用于区分不同类型的流,可以通过流量类型而对某些流量赋予更高的优先级。

相比 IPv4,舍弃了如下几个功能:

  • 分片/重新组装:IPv6 不允许在中间路由器进行分片、重新组装,如果路由器收到的 IPv6 数据报太大无法发给链路,则会丢弃该数据报,并向发送方返回 『分组太大』的 ICMP 报问,发送方就能够用较小长度的 IP 数据报重发数据。也就是将分组、组装的功能交给了端系统实现,大大增加了 IP 转发速度。
  • 首部检验和:由于运输层和链路层有检验的操作,因此将该功能进行了去除,这样可以避免每台路由器上进行首部检验和的计算从而降低效率。
  • 选项:删除了选项字段从而使得首部成为定长的 40 字节,从而加快对 IPv6 数据报的处理速度。

可以看到,IPv6 相比 IPv4 的改变都是为了提高处理 IP 报文的速度,这也说明了网络层最主要的任务是快速处理 IP 分组,因此一些耗时的操作可以交给端系统做从而避免在每台路由器上执行一些耗时操作。

IPv6 面临的迁移问题

IPv6 看起来十分美好,但我们都知道目前普遍使用的网络层协议仍然是 IPv4,并且能够处理 IPv4 的系统不一定能处理 IPv6 数据报,我们该如何将 IPv4 迁移到 IPv6 成为了一个十分关键的问题,目前主要有下面几种解决办法:

全球同步迁移

也就是全球统一一个固定的时间,在那个时间点所有 Internet 中的机器均关机并从 IPv4 迁移到 IPv6,涉及到的机器过多,显然是不现实的。

双栈(double stack)

使用一种同时具有 IPv6、IPv4 完整实现的节点,当 IPv4 节点互操作时,使用 IPv4,当 IPv6 节点互操作时,使用 IPv6。这种节点必须同时具有 IPv4、IPv6 两种地址,并且能确定另一个节点是 IPv4 还是 IPv6 点,这些问题可以通过 DNS 来解决。DNS 可以通过解析的节点和发出请求的节点的类型来返回对应的 IP 地址。

这种方法如果发送方和接收方中任意一个是 IPv4 的,则必须使用 IPv4,IPv6 的数据报在向 IPv4 进行转换时,会丢失一些无对应字段的信息。

建隧道(tunnel)

还有一种建隧道的方式来解决,隧道的核心思想就是用支持的协议来运输不支持的协议。例如两个 IPv6 的节点之间有一系列 IPv4 的路由器,可以在隧道的入口 IPv6 节点将 IPv6 数据报放在 IPv4 数据报的数据字段,而该 IPv4 数据报的地址指向接收 IPv6 节点。这样隧道的中间路由器就可以像传送 IPv4 数据报一样进行传输,接收端的 IPv6 节点再从收到的 IPv4 数据报中取出 IPv6 数据报,这样就可以通过 IPv4 路由器对 IPv6 数据报进行传输。

无论是哪种方法,显然都无法完美的解决 IPv4 向 IPv6 的迁移问题,可以看出来要改变网络层的协议是十分困难的,不知道在有生之年能不能看到 IPv4 向 IPv6 的完全转变了...

路由选择算法

我们需要在源主机到目的主机之间确定一条路径,并且尽量保证这条路径能够尽量的费用低。因此我们需要路由选择算法来进行这样的路由选择过程从而得到一条从源主机到目的主机到最低费用路径。

路由选择算法分类

路由选择算法可以大致分为全局式和分布式两类:

  • 全局式:用完整的、全局性的网络信息来计算出一条由源主机到目的主机的最低费用路径,因此这种算法开始之前需要首先获取这些全局性的信息,一种典型的全局式的路由选择算法是链路状态(LS)算法
  • 分布式:以迭代、分布式的方式计算最低费用路径,不需要拥有完整的全局性信息,每个节点只需要有与其相连的节点的信息即可计算,通过相邻节点交换信息,最终算出一条最低费用路径。典型的分布式路由选择算法是距离向量(DV)算法

路由选择算法还可以根据算法静态与否分为静态和动态两类:

  • 静态:路由随着时间变化得比较缓慢,通常是人工进行调整。
  • 动态:当网络流量负载发生变化时即时改变路由选择路径,但更容易受到路由选择循环、路由震荡之类的影响。

链路状态(LS)算法

在链路状态算法中,网络拓扑及所有链路费用均为已知的,一般是通过每个节点向网络中所有其他节点广播链路状态分组实现。实践中通常使用 Internet 的 OSPF 路由选择协议,由链路状态广播算法完成。

下面的链路状态路由选择算法为 Dijkstra 算法,它是一种迭代算法。

首先我们定义如下的符号:

  • D(v):到算法的本次迭代,从源节点到目的节点 v 的最低费路径对应的费用。
  • p(v):从源节点到 v 沿着最低费路径的前一节点。
  • N':节点的子集。

可以用下面的伪代码来表示其具体过程:

N' = {u};
// 将 u 的所有邻居的 D(v) 进行计算,其他节点 D(v) 置为无穷。
for v in nodes {
    if v is neighbor of u   
        D(v) = c(u, v);
    else
        D(v) = ∞;
}
do {
  // 寻找不在 N‘ 中并且 D(w) 最小的 w
    find w not in N' and D(w) is minimum;
  // 将 w 加入 N'
    add w to N';
  // 更新 w 到其不在 N' 中的邻居 v 的最小距离 D(v)
    update D(v) for neighbor v of w and not in N':
        D(v) = min(D(v), D(w) + c(w, v));
} while(N' != N)

LS 算法终止时,对每个节点我们都有从源节点到该节点的最低费路径的前一节点,这样我们可以构建从源节点到所有目的节点的完整路径。节点中的转发表可以根据这个信息从而构建。

这种 LS 算法的最坏情况时间复杂度为 O(n^2)

距离向量(DV)算法

距离向量(DV)为一种迭代、异步、分布式的算法,它的每个节点从其直接相邻的邻居处接收信息,执行计算,之后将计算结果发送给邻居。这个过程会一直持续到邻居之间无更多信息交换。并且它并不需要各个节点相互之间步伐一致的工作。

d(x, y) 是从 x 到 y 的最低费路径的费用。则有如下方程(Bellman-Ford 方程):

d(x, y) = minv(c(x, v) + d(v, y))

其中 minv 针对了 x 的所有邻居 v。

DV 算法基本思想是,每个节点 x 以 d(x, y) 开始,对 N 中的所有节点估计从它到 y 的最低费路径的费用。令 Dx=[d(x, y), y in N] 是节点 x 的距离向量,它表示了从 x 到 N 中所有其他节点 y 到费用估计。

每个节点 x 需要维护下列路由选择信息:

  • 对于邻居 v,从 x 到 v 的费用为 c(x, v)
  • 节点 x 的距离向量Dx=[d(x, y), y in N]
  • 它每个邻居的距离向量 Dv=[d(v, y), y in N]

每个节点不断向邻居发送其距离向量副本,每当 x 从邻居 v 中接收到一个新的距离向量,则通过 Bellman-Ford 方程更新自己的距离向量:

d(x, y) = minv(c(x, v) + d(v, y)) // 对N中每个节点

伪代码表示如下:

// 初始化
for destinations y in N
  d(x, y) = c(x, y)
for w in neighbors
  d(w, y) = ? for all y in N
// 向所有邻居发送距离向量
for w in neighbors
  send distance vector Dx to w;
while(true){
  // 等待到 w 的费用改变或者收到 w 发来的距离向量
  wait(see cost change to w || receive distance vector from w);
  // 更新到 N 中 y 的距离
  for y in N
    d(x, y) = minv(c(x, y) + d(v, y));
  // 如果更新了距离,向所有邻居发送距离向量
  if (d(x, y) changed)
    send distance vector to all neighbors;
}

好消息与坏消息

我们往往将某条链接的费用减少称为『好消息』,而将某条链接的费用增加称为『坏消息』。

在 DV 算法中,好消息往往是传递的很快的,例如:

如图所示的情况,Y 发现 X-Y 间的费用由 4 减为了 1,于是它更新了自己的距离向量,并通知了 Z。Z 在收到 Y 的更新报文后,也更新了自己的距离向量(5 -> 2),之后通知了 Y,Y 收到后发现费用没有改变,于是网络回归了静止,仅仅经过了两次迭代。

在 DV 算法中,『坏消息』传递却非常的慢,例如:

如图所示的情况,Y 发现 X-Y 间的费用变为了 60,于是 Y 开始更新距离向量。在更新向量的过程中,Y 首先会发现 Z 到 X 的距离只有 5,因此它选择了先到 Z 再到 X,也就是 d(y, x) 变为了 5 + 1 = 6

从全局来看这个逻辑显然是错误的,因为 Z 到 X 只需要 5 的前提是要经过 Y,但 Y 并不知道这一点,现在 Z 到 X 要经过 Y,而 Y 到 X 要经过 Z,这就导致 Z 收到 Y 的更新报文后,发现可以经过 Y 到达 X,于是更新 d(z, x) 为 6 + 1 = 7,而 Y 收到更新后又选择从 Z 到 X,d(y, x) 更新为了 7 + 1 = 8。这就造成了一个选择环路的问题,更新报文不断在 Y、Z 之间传递,直到 44 次迭代后,Z 算出它经由 Y 的路径费用大于 50 为止。此时,Z 最终确定到 X 的最短路径费用是直接到达 X 的费用 50,而 Y 也得到了最短路径是经 Z 到 X 的费用 51。

显然,坏消息传递的速度实在是太慢了,并且如果 X 和 Y 之间的费用为 10000,Z 和 X 的费用是 9999 时,就会出现无穷计数的问题,我们可以通过毒性逆转的方式来解决这个问题。

毒性逆转

毒性逆转的思想就是,如果 Z 要通过 Y 到达 Z,则通知 Y 的时候让 Y 以为自己到 X 的距离是无穷,通过这样『善意的谎言』,可以解决一部分的选择环路问题。

之所以说是一部分,是因为当涉及 3 个或更多节点的环路将无法被毒性逆转技术检测到,因此毒性逆转不是一个万能的方法。

自治系统

前面的路由算法的研究,我们仅仅将网络看做了一个互联路由器的集合,但真实的环境中的网络并没有这么简单,主要有以下的原因:

  • 规模:随着路由器数目的增加,涉及路由选择信息的计算、存储、通信的开销非常之高,难以实现,因此需要采取一些措施减少路由选择计算的复杂度。
  • 管理自治:某个组织可能想要按自己的意愿来运行路由器,对外隐藏其内部的组织面貌,并且还需要它的网络能与外部的网络连接。

为了解决这一问题,采用了一种将路由器组织进自治系统(AS)的方式。每个 AS 由一组处在相同管理控制下的路由器组成,同一个 AS 中的路由器运行相同的路由选择算法。这种在一个 AS 内运行的路由选择算法叫做自治系统内部路由选择协议

为了实现 AS 之间的互联,AS 中的一台或多台路由器可能有另外的任务:负责向 AS 之外的目的地转发分组。这些路由器被称为『网关路由器』。

当分组需要传递到 AS 外部的目的地时,这个路由选择过程又变成了一个比较难以解决的问题。如果 AS 只有一个网关连接一个其他 AS,这个问题并不复杂,但如果有多条通往外部的 AS 时,这个问题就变得复杂了。

为了解决这个问题,传递数据的 AS 需要知道经过这几个外部 AS 分别能到达哪些目的地,同时还需要向该 AS 中的所有路由器传达这些可达性信息。这个任务是由自治系统间路由选择协议完成。Internet 中所有 AS 都运行了同一个协议——BGP4协议

也就是说,每个路由器将接收来自 AS 内部路由选择协议和 AS 间路由选择协议所提供的信息,通过这些信息来配置自己的转发表。

大部分情况下,到达一个目的地可以通过 AS 内的多个网关到达,此时路由器就会使用 AS 内部路由选择协议提供的费用信息,选择有最低费用低网关,这种路由选择称为热土豆路由选择

因此可以将路由器转发表中增加一个 AS 之外目的地的步骤描述为如下图所示:

路由选择协议

路由选择协议的主要任务就是确定一条源主机到目的主机之间的路径。Internet 中使用的路由选择协议主要有三个:

其中两个为 AS 内部路由选择协议,分别为 RIP协议OSPF协议

另外一个为 AS 间的路由选择协议,即为 BGP协议

AS 内部的路由选择协议一般用于确定在 AS 内部执行路由选择的方式,它又称为内部网关协议

路由选择信息(RIP)协议

RIP 协议是一种距离向量协议,它使用跳数作为其费用测度,也就是说 RIP 中每条链路的费用为 1。RIP 中用跳来描述从沿着源路由器到目的子网(包括目的子网)的最短路径所经过的子网数量。

RIP 只能使用在网络直径不超过 15 跳的 AS 内,使用 RIP 响应报文来实现邻居之间的信息交换,响应报文又称为 RIP 通告

每张路由器维护了一张叫做路由选择表的 RIP 表,它包括了该路由器的距离向量以及该路由器的转发表。转发表如下所示:

目的子网 下一台路由器 到目的地的跳数
w A 2
y B 2
z B 7
x - 1
... ... ...

RIP 路由器大概每 30 秒会进行一次交互通告,如果一台路由器超过 180 秒没有从邻居处收到报文,则该邻居不再认为是可达的,此时该路由器会修改本地路由选择表,然后向相邻路由器发送通告来传播该消息。

RIP 路由器还可以发送 RIP 请求报文来请求其邻居到目的地的费用。

用 UDP 协议通过 520 端口可以相互发送 RIP 请求、响应报文,这里可能会比较奇怪,因为 RIP 使用了一个网络层之上的运输层协议来实现网络层的功能,这看上去很不符合逻辑,但实际上是因为在许多路由器上运行的系统如 UNIX 中,RIP 通常是被当作一个应用层的进程来实现的,它可以在 Socket 上发送和接受报文。

因此可以说 RIP 是一个运行在 UDP 上的应用层协议

开放最短路优先(OSPF)协议

OSPF 的核心就是一个使用洪泛链路状态信息的联络状态协议和一个 Dijkstra 最低费用路径算法,通过 OSPF,一台路由器构建了一幅关于整个 AS 的完整拓扑图。之后在本地运行 Dijkstra 最短路径算法,即可确定以自身为根节点到所有子网的最短路径树。

OSPF 中的各条链路费用是由网络管理员配置的,不强制如何设置链路权值的策略,但提供了一种机制(协议)为给定链路权值集合确定最低费用路径的路由选择。

使用 OSPF 时,路由器会向 AS 内所有其他路由器广播路由选择信息,而不仅仅是向它的邻居广播。当一条链路状态改变时,路由器就会广播链路状态信息,即使状态未变化,它也会周期性广播链路状态(至少 30 分钟一次)。

OSPF 报文由 IP 协议承载,因此其需要自己实现可靠报文传输、链路状态广播等功能

并且 OSPF 还需要检查链路正在运行(通过向邻居发送 HELLO 报文),并允许 OSPF 路由器获得邻居路由器等网络范围链路状态的数据库。

OSPF 主要有以下优点:

  • 安全:可以鉴别 OSPF 路由器之间的交换,只有受信任的路由器能参与 AS 内的 OSPF 协议,防止有恶意入侵者将错误信息注入路由器表内。鉴别方式主要分为两类:
    • 简单鉴别:每台路由器配置相同的口令,发送 OSPF 分组时以明文方式包含了口令。
    • MD5 鉴别:对密钥计算了 MD5 值,将该 MD5 值包括在 OSPF 的报文中,接收方通过对密钥进行 MD5 比较从而验证分组的真实性。
  • 多条费用相同的路径:到达目的地有多条费用相同路径时,OSPF 支持使用多条路径(可以分摊压力)
  • 对单播、多播路由选择的支持:多播 OSPF(MOSPF)对 OSPF 进行了扩展,支持了多播路由选择,其使用现有的 OSPF 链路数据库,并为现有 OSPF 链路状态广播机制添加了一种新型的链路状态通告。
  • 支持在多个路由选择域内的层次结构:OSPF 具有按层次结构构件一个 AS 的能力。

OSPF 层次路由

一个 OSPF 自治系统可以分为多个区域,每个区域都运行自己的 OSPF 路由选择算法,一个区域内每台路由器都向该区域其他路由器广播链路状态。一个区域内,一台或多台区域边界路由器负责向流向该区域外的分组提供路由选择。最后,AS 内只有一个 OSPF 区域配置为主干区域,它的作用是为其他区域之间的流量提供路由选择。这个主干包含了 AS 内的所有区域边界路由器,以及一些非边界路由器。

AS 内的区域间路由选择分组首先路由到一个区域边界路由器,再通过主干路由到位于目的区域的区域边界路由器,最后路由到目的地。

边界网关(BGP)协议

BGP 协议是全球 Internet 中统一使用的 AS 间路由选择协议。它为每个 AS 提供了以下功能的支持:

  • 从相邻 AS 获取子网可达性信息
  • 向本 AS 内部所有路由器传播这些可达性信息
  • 基于可达性信息和 AS 的策略,决定到子网的最优路由

BGP 使得每个子网向 Internet 的其余部分通告了它的存在,且 BGP 确保了 Internet 中每个 AS 都知道该子网并且知道如何到达。

基础

BGP 中,路由器通过 179 端口上的半永久 TCP 连接来交换路由选择信息。在连接位于两个不同的 AS 中的路由器的链路之间,通常都存在这样的一条 BGP TCP 连接,同时在一个 AS 的路由器之间也有许多半永久 BGP TCP 连接。

img

如上图,每个 AS 内部产生了网状的 TCP 连接,对于每条 TCP 连接,两个端点分别称为 BGP 对等方,沿着该连接发送的 BGP 报文称为 BGP 会话。跨越两个 AS 的 BGP 会话称为 外部 BGP(eBGP)会话 ,而同一个 AS 中的两台路由器之间的 BGP 会话称为 内部 BGP(iBGP)会话

BGP使得每个 AS 知道了通过其相邻 AS 能到达哪些目的地,BGP 中的目的地不是主机,而是 CDIR 化的前缀,每个前缀表示一个子网/子网集合,

对于网关之间的 EBGP 会话,发送的是当前 AS 可达的前缀列表。

当任何网关路由器收到 EBGP 中获得的前缀列表后,将会通过 IBGP 会话向其他路由器发布这些前缀。

当一台路由器(包括网关路由器)收到一个新前缀后,都会为这个前缀在转发表中新增一个项。

路径属性和 BGP 路由

在 BGP 中的 AS 由它自己的全局唯一的自治系统号(ASN)所标识(只有比较特殊的桩 AS 没有 ASN),ASN 由 ICANN 机构分配。

一台路由器通过 BGP 会话通告一个前缀的时候,它的前缀中包含了一些 BGP 属性,这种带有属性的前缀一般被称为一条路由。其中 AS-PATHNEXT_HOP 属性比较重要。

  • AS_PATH:包含了前缀的通告以及通过的 AS,每当一个前缀传送到一个 AS,该 AS 会在 AS_PATH 中加入自己的 ASN。通过 AS_PATH 可以检测和防止循环通告。
  • NEXT_HOP:是一个传递某个 AS-PATH 的路由器接口,路由器需要用到这条属性来正确地配置转发表,可以根据 NEXT_HOPAS_PATH 来选择一条到网关的最短距离。

除此之外,属性中还包含了一个叫做本地偏好值的属性,通过它可以在多条同样的路径下选择更偏好的一条。

当网关路由器收到路由器通告时,它通过输入策略决定是否接受这条路由,是否设置某个属性。

BGP 路由选择

对于一个路由器,它可能知道到达任何一个前缀的多条路由,此时它必须从几条路由中选择一条,如果存在多条路由时,路由器通过下面的规则来筛选直至只剩一条路由:

  • 若路由被指派了一个本地偏好值,则选择偏好值最高的
  • 相同本地偏好值下,选择具有最短的 AS_PATH 的路由
  • 本地偏好值、AS_PATH 长度相同的情况下,选择具有最靠近 NEXT_HOP 路由器的路由。
  • 若仍剩下,则使用 BGP 标识符选择路由。

桩网络

如图所示,A、B、C、W、X、Y 分别为 6 个互联的 AS,其中 W、X、Y 为桩网络,A、B、C为主干提供商网络。所有进入桩网络的流量必定是去向该网络,所有离开桩网络的流量必定是离开该网络

W、Y 毫无疑问是桩网络,而 X 是一种多宿桩网络,通过控制 BGP 路由的通告方式,防止了 X 转发 B、C 之间的流量。

广播和多播路由选择协议

前面提到的都是单播(点对点)的路由选择协议,而广播路由选择中,网络层提供了从一个源节点到网络中所有其他节点交付分组的服务,多播路由选择则提供了单个源节点向其他网络节点的一个子集交付分组的服务。

广播路由选择算法

N 次单播实现广播

最简单的方法就是由发送节点向每个目的地分别发送分组的副本,这种方式利用了 N 次单播实现广播,但这种方式的效率较低下。

并且这意味着源节点需要知道所有的接收方及其地址,要达到这一点必然会增加更多开销。

更好的方案是经第一跳仅发送单个副本,之后让第一跳后面的其他端节点生成并转发所需的副本。

无控制洪泛

可以通过洪泛的方法实现广播,它要求某节点接受了广播分组后,向其所有的邻居发送该分组的副本。

但很显然如果图中存在圈,就会导致多个分组副本的传递在无休止的循环。这种问题叫做广播风暴,会导致无休止的广播分组赋值,最后使得网络中生成大量的广播副本。

受控洪泛

可以通过对洪泛分组进行一定控制,主要有如下几种方式:

序号控制洪泛

源节点将地址及广播序号放入分组,之后向每个邻居发送分组。每个节点会维护它收到、复制和转发的分组的源地址和序号列表。如果收到一个广播分组会首先检查它是否在列表中,如果在会丢弃这个分组。

反向路径转发(RPF)

当一台路由器收到具有给定源地址的广播分组时,只有该分组到达的链路正好是位于其返回的最短单播路径上时才向所有出链路(除接受分组的链路)传输报文。否则路由器丢弃分组。

生成树广播

受控洪泛虽然避免了广播风暴,但冗余的分组仍然会传输,只是会被丢弃而已。

通过生成树可以解决以上的问题,我们首先可以对网络节点构造一棵最小生成树,之后接收广播分组的节点向生成树的所有邻居转发该分组。

但生成树算法意味着我们需要对树进行生成及维护,这会带来一定的复杂性。

参考资料

《计算机网络:自顶向下方法》

BGP漫谈

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注

%d 博主赞过: