5.1 网络层设计

一个路由器提供的功能:建立局域网,连接局域网和广域网。

网络层的位置和功能

网络层位于传输层之下,数据链路层之上。

主要功能

  • 联网(Internetworking)
  • 打包(Packetizing)
  • 编址(Addressing):对网卡,接口地址唯一。
  • 路由(Routing)核心功能
  • 分片(Fragmenting)

相关功能:

  • 路由选择

  • 一对多通信(多播,组播)

  • 地址解析

跳(Hop):数据报跨越网络的过程。每一跳经过一个路由器,进入一个网络。

设计目标:

  • 不依赖于路由器的实现
  • 向传输层提供统一的服务,屏蔽细节

虚电路交换和数据报

在电路交换中,需要建立专门的线路。而分组交换是分包发送,可以通过虚电路提供面向连接的服务,通过数据报提供无连接的服务。

A 发给 B N 个包,由于路由选择不同,到达可能乱序。

VCI:虚电路的局部编号。

在建立虚连接时,创建路由表

虚电路路由表:

In				Out
Port	VCI		Port	VCI
1		14		3		22
1		77		2		41

表示:从 Port 1 收到的 VCI = 14 的包,转发到 Port 3,VCI 改为 22

这样所有的包都走这条虚电路,实现有序传送。

虚电路:

  • 不需要携带完整的地址。
  • 需要保存连接的状态信息
  • 故障时途径的虚电路全部失效

5.2 路由算法

静态路由:实现设计

动态路由:~

路由器一般通过下一条选路,而不是给出完整路径。

衡量选录算法的标准:

  • 正确
  • 简单
  • 健壮
  • 稳定
  • 公平
  • 优化
    • 低延迟
    • 高吞吐

选路:构造路由表的过程

转发:根据路由表发送包的过程

汇集树(sink tree):以目的节点为根,所有源节点到它的最优路由。

泛洪(Flooding):当路由表中没有某地址时,将包发给所有其它链路。

  • 缺点:导致网络中存在大量重复包,以及死循环。
  • 解决方法:递减计数器,归零丢弃、序列号
  • 优点:健壮,可以用于路由信息分发

随机选路

自适应选路(Adaptive Routing):根据网络状况更新。

Dijkstra 算法:一种最短路径算法。

image-20210609212247050

image-20210609212701515

从而可以得到 A 的路由表:

image-20210609212721972

以及 A 为根的最短路径树:

image-20210609212804351

距离向量路由(DVR)

  1. 首先知道两个节点之间的距离
  2. 需要在路由器之间交换信息(目的地和距离)
    1. 例如 RIP 算法,每 30s 交换一次
  3. 丢弃旧信息,根据信息更新路由表
  4. 如果路由器长期不回应,则视为失效(RIP 算法为 180s)

例子:

image-20210609213940684

对于 J,其有 AIHK 四个邻居。一开始,J 会收到来自邻居的路由信息(如上图 b 四列)。同时 J 还知道自己和邻居的距离,JA = 8, JI = 10, JH = 12, JK = 6。从而,J 可以更新自己的路由表:用邻居给它的距离加上自己到邻居的距离,从而知道经过邻居转发后,到达任意目的地的距离。例如,要求自己到 B 的距离:

注意:AB != BA

  1. J 要到 B,可以选择 AIHK 任一做下一跳:
    1. 如果下一跳是 A:JB = JA+AB = 8+12 = 20
    2. 如果下一跳是 I:JB + JI + IB = 10+36=46
    3. 从而可以知道 J 到 B 最短的下一跳是谁。
  2. 对每个节点都采用同样操作,可以求出 J 到任意节点的最短距离。

路由表的创建过程:

image-20210609214826887

最初,只知道直连的节点的路由,其它的设为 $\infty$。进行迭代,直到收敛。

DVR 的缺点:

  • 收敛慢。在添加节点时,最多经过直径相当的开销,可以完成更新。但是故障出现时,可能要经过无穷次信息交换才能传递失效信息(存在死循环)(很像红石电路的循环)。

使用于:

  • RIP 路由信息协议
  • Cisco EIGPR

改进:

  • BGP-4:路径矢量选路
  • IDRP(Inter-domain Routing Protocol)

LSR 链路状态路由

  • 每个路由器分享数据给邻居链路状态包(LSP)
  • LSP 定义了自己节点所知的最佳路径

构造步骤:

  1. 获知邻居
  2. 测量到邻居的开销
  3. 构造局部(邻居)网络拓扑,写入链路状态包
  4. 将状态包发给所有邻居
  5. 计算到其它路由的最短路径

获知邻居

  1. 发送 HELLO 包给邻居。

  2. 邻居收到后响应唯一 ID

  3. 简化

测量开销

  1. 发送 ECHO 包
  2. 得到环回时延

如果考虑负载,会导致路由不稳定

如果不考虑负载,可能不能计算最优线路

image-20210609220257465

Seq:序号,一般递增

  • 如果是新包,就泛洪
  • 如果是旧包,就丢弃

Age:递减计数,用于避免循环

LSP 收到后要 ACK

构造拓扑

当收到了所有节点的 LSP,就可以构造出拓扑结构。可以计算出以自己节点为根的最短路径树,构造出路由表。

应用:

  • ISIS
  • OSPF

分级路由

当节点数量很多的时候,如果需要知道全部节点信息,就会导致性能下降。

可以通过分区(cluster/region/router),区抽象为一个节点,在区间和区内分别选路。

缺点:

  • 可能得到的不是最优路径

5.3 拥塞控制

原因:负载超过网络容量。

影响

  • 时延增加
  • 丢包

解决方法

  1. 增加资源
    1. 网络提供:规划,调整网络
    2. 业务量感知选路
  2. 减小负载
    1. 接纳控制:基于令牌桶、漏桶,决定是否允许虚连接建立。
    2. 节流(Throttling)
      1. 检测拥塞
        1. 利用率
        2. buffer
        3. 指数加权移动平均(EWMA)
      2. 拥塞信息传输
        1. 发送抑制分组(Choke Packet)
      3. 降速

image-20210609224053260

源主机降低负载

逐跳反压:不止源节点响应 Choke,每个上一节点都响应 Choke

ECN(显式拥塞提醒

通知方式:显式通知。IP 包的两个位用于记录拥塞

丢包策略:负载掉落(Loading Shedding)只在缓冲耗尽丢包。Wine / Milk

RED(随机早期检测)

通知方式:不通知(隐式通知,等超时)

丢包策略:提前丢包

流量控制和拥塞控制的区别:

流量控制:局部的问题,只涉及两个终端。

拥塞:全局的问题

5.4 QoS

  1. 可靠性:

    1. 差错率
    2. 丢失率
  2. 时延

  3. 抖动(时延差分)

  4. 带宽

提高 QoS 的方式

业务量整形(Traffic Shaping)

消除突发,尽量平均发送。

漏桶:相当于用个数据池放数据,延缓突发的影响(类似电容)(缓存队列)

  • 劣势:缓存溢出,数据丢失
  • 无突发性

令牌桶:有令牌则输出,令牌耗尽则以令牌产出速率输出。

  • 允许有限的突发性

分组调度(Packet Scheduling)

FIFO 队列:尾部丢弃

优先级多队列:根据优先级送入不同队列处理

  • 对低优先级数据不公平

公平队列:多队列循环处理。

公平加权队列:多队列,轮流处理,不同队列的机会不同。

资源预留、接纳控制

传输之前协商:通过流描述协商。

流描述:

  • 源主机产生
  • 沿途可修改

5.5 网络互联

允许节点能够访问不同网络的节点。

实现:使用同样的网络层协议(IP)

应用网关:例如用于 RFC 5822 与 X.400 两种邮件格式之间的转换

交换机互联和路由器互联

交换机互联:根据 MAC 地址,处理帧

路由器互联:根据 IP 地址,查路由表选路。

隧道:源主机与目的主机网络协议相同,中间网络不同,用中间网络的协议封装源主机发送的数据包。

分片

MTU:最大传输单元

5.6 互联网的网络层

IPv4 地址:32bit,每个接口的地址不同。

IPv4 地址(通常意义的 IP 地址)

  • 分类地址:网络号 + 主机号

image-20210609231146004

网络地址:例如 123.0.0.0 表示 123 开头的所有地址。(路由选择大多使用网络地址)

默认掩码:屏蔽主机号的地址。

例如:

  • A 类:255.0.0.0
  • B 类: 255.255.0.0

若 IPv4:=200.1.2.3,默认掩码 255.255.255.0,二者求与,得到网络地址 200.1.2.0

0.0.0.0:本主机

255.255.255.255:广播地址,本子网内广播。

N.255.255.255:网络内广播。

127.x.x.x:环回地址。发给本机其它进程。

  • 无分类地址

子网划分

获得子网地址的方法:子网掩码与目的地址的按位与。

可以用于判断 IP 包是否发往本网内主机。

例如将 141.14.0.0 的子网划分为四个,则可以确定范围:

141.14.0.0~141.14.63.0
141.14.64.0~141.14.127.0
141.14.128.0~141.14.191.0
141.14.192.0~141.14.254.0

超网划分(Supernetting)

将几个连续的网络合并在一起。

例如将四个连续的 C 类网络合并:X.Y.32.0~X.Y.35.254

超网掩码:255.255.252.0 (256-4)

image-20210609232932699

无类别地址

CIDR 记法

200.23.15.0/23 表示网络号占 23 位,主机号占 9 位,有 $2^9$ 个地址,其中 $2^9-2$ 个可分配。

路由聚合

把相邻地址合并在一起,减少路由表的占用。

  • 问题:合并后地址空间被放大,包含了不属于的空间

NAT(网络地址翻译)

私有地址规定:

  • 10.0.0.0 - 10.255.255.255/8
  • 172.16.0.0 - 172.31.255.255/12
  • 192.168.0.0 - 192.168.255.255/16

NAT 路由:负责私有地址到外部地址的转换(另外也进行端口转发)。

封装

IP 协议

包头:

image-20210609234441359

IHL 的值要乘以 4. 取值范围(5-15)。

总长度最大 65535B.

Time to live 一般时存活跳数。

校验只对包头进行

支持的协议字段:

  • TCP = 6
  • UDP = 17
  • ICMP = 1
  • IGMP = 2
  • OSPF = 89

Differentiated Services (服务类型):

  • 0,1,2 优先级
  • 3 D
  • 4 T
  • 5R
  • 6C
  • 7 未用

服务类型(Type of Service):长度 8 比特。8 位 按位被如下定义 PPP DTRC0

PPP:定义包的优先级,取值越大数据越重要

000 普通 (Routine)

001 优先的 (Priority)

010 立即的发送 (Immediate)

011 闪电式的 (Flash)

100 比闪电还闪电式的 (Flash Override)

101 CRI/TIC/ECP (找不到这个词的翻译)

110 网间控制 (Internetwork Control)

111 网络控制 (Network Control)

D 时延: 0: 普通 1: 延迟尽量小

T 吞吐量: 0: 普通 1: 流量尽量大

R 可靠性: 0: 普通 1: 可靠性尽量大

M 传输成本: 0: 普通 1: 成本尽量小

0 最后一位被保留,恒定为 0

IP 包头结构详解 - 御用闲人 - 博客园 (cnblogs.com)

为什么只校验包头? 答:首先, 包头的错误比数据中的错误要严重的多,例如目的地址发生错误可能会导致数据包被发送到错误的主机。 由于许多主机并不检查收到的包是不是给自己的, 该包将会被错误地接收下来。因此必须对于包头进行校验。如果对数据部分进行校验,将增加路由器的处理时间 导致端到端时延大幅增加。数据链路层和传输层都有校验功能,因此 IP 无需对于数据部分进行校验。

校验和

16 位一组,不足填充零。累加起来得到 16 bit 的和,取反得到校验和。

分片和重装(Fragmentation and Reassembly)

分段的字段:

image-20210619194411976

Identification:标识符,复制到每一个片段里

Offset:数据的偏移量,相当于顺序。便于排序。(单位是 8 octets)

DF(Don’t Fragment):如果是 1,说明不是分片。

MF(More Fragments):如果是 1 说明不是最后一个。否则说明是最后一个。

分片规则: 选择最接近 MTU 的 8 倍数的八位组。

例如 MTU 是 900,包大小是 1200,则 900/8=112+0.5,所以分为 960+240.

重装的规则:启动重组计时器,等待片段到达,到达一个放进缓存,超时未全部到达,则清空缓存,丢弃。

【例子】 如果一个数据报拆分为 4 个分组,前 3 个到达,然后超时了。这时候第四个到了,怎么处理? 答:第四个先放进缓存,然后等前三个到达,如果超时仍然未到达,就丢弃。

重装只在目的主机进行。

IP 包头选项:

  • 严格源选路:需要列出完整路径
  • 宽松源选路
  • 记录路由:要求路由器记录自己的 IP
  • 时间戳:记录时间

IPv6

  • IPv4 地址不够
  • 对实时应用没有保障
  • 安全性低
  • 移动性支持不好

改进:

  1. 更长地址空间
  2. 简化包头
  3. 更好的选项支持
  4. 身份认证、加密
  5. 更好的 QoS

image-20210609235802705

  • 去除 IHL。固定 40 字节基本包头。
  • 协议字段去除。
  • 不校验包头,让数据链路层做。
  • 去除分段,设为选项。
  • 服务类型替换为流标签
  • 包总长替换为数据总长
  • TTL 换为跳计数

IPv4 头部的 “协议(protocol)” 字段并没有出现在 IPv6 中,为什么? 答:答:IPv4 包头中的协议字段的作用是告诉目的地主机包中数据部分应该交给哪个协议实体来进行处理。 中间转发的路由器不需要处理这个字段, 因此不需要放在 IPv6 的基本包头中。事实上扩展包头的 “下一个包头” 字段的功能包含了 protocol 的功能。

扩展的包头:

image-20210610000144696

地址

冒号分隔。冒号内连续 0 可以记作一个。冒号间多个连续零可以记作 ::

其它

连接:IP 只提供无连接服务

差错控制:只检测头

通过 ICMP 进行流控。

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

功能:

  • 报道目的地不可达、过长但不可分段
    • 超时报告
    • 源抑制
    • 重定向
  • 测试
    • ping 测试(利用 ECHO)
    • 通告

ICMP 封装在 IP 包传输。

ARP(地址解析协议)

通过 ARP,广播 MAC,寻求拥有此 MAC 地址的用户的 IP。

BOOTP(启动协议)

基于 UDP 实现。

DHCP:动态主机配置协议,自动配置上网信息,如:IP 地址,路由器地址,子网地址,DNS 服务器地址。

  1. 客户端广播 DHCPDISCOVER
  2. 服务器返回 DHCPOFFER
  3. 客户端选择一个服务器返回 DHCPREQUEST
  4. 服务器分配 IP DHCPACK

CIDR

路由表结构:

目的 IP | 子网掩码 | 接口 | 下一跳 IP

image-20210610002044292

最长前缀匹配:当多行匹配时,以小网络为准(如上图二三行,以第二行为准)

RIP

  • 路由信息协议
  • 限制最大跳数(16)
  • 基于 UDP
  • v1 不支持子网掩码
  • v2 支持子网掩码

image-20210610002416782

OPSF:开放最短路径优先

  • 基于 LSR
  • 允许设置花销
  • 每个路由器都知道全局拓扑
  • 需要全网通告邻居
  • IP 包传输
  • 支持子网(area)

image-20210610002716161

BGP(边界网关协议)

  • 路径矢量选路
  • 每个节点保存完整路径
  • 避免无限环路
  • 策略路由
  • 基于 TCP 传递消息

IP 多播

组播、多播

IGMP:因特网组管理协议

  • 让路由器知道自己连接了哪些组地址
  • 周期询问(224.0.0.1),让节点报告所属组。

移动 IP

目标:移动到外地网络的节点依然能连接归属地 IP 的数据报

MN:移动节点

HA:本地代理(归属地路由器)

FA:外地代理

CoA:关照地址,FA 的地址

相关节点:和 MN 直接通信的节点

关键: 建立隧道

  1. 首先发到归属地
  2. 归属地隧道发给新地址
  3. 新地址直接通信