开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 网络协议 -> 计算机网络之（7）：TCP流量控制、拥塞控制 + 网络层 -> 正文阅读

[网络协议]计算机网络之（7）：TCP流量控制、拥塞控制 + 网络层

TCP 流量控制

Go back N

原则：接收方应该尽可能的简单
使用的是累积确认 cumulative acknowledgement
每一组发送的 segment 使用一个 timer，当发生超时的时候，将全部的 N 个 packet 全部进行重发

Selective Repeat

原则：避免没必要的重传行为，
对每个的 packet 进行 acknowledgement，而不使用累积确认的方式
对于每个 packet 设置一个 timer，当 timer 超时的时候只是重发超时的 packet 即可

Go back N v.s. Selective Repeat

go back n 不需要保存 packet
selective repeat 只需要重发丢失的包即可

流量控制中的问题

接收方的 buffer 中的没有空闲的位置了，发送发的发送窗口的尺寸变成 0，这个时候发送方不会再向接收方发送任何的 packet，但是当接收方的 buffer 有空闲了，发送方也不知道，所以依然不发 packet。

方法 1：接收方主动

接收方主动发送一个 windowUpdate 的信息

方法2：发送方主动

发送方隔一段时间就发送一个 zeroWindowProb 来询问接收方的 buffer 是否有空闲的位置

TCP 拥塞控制

TCP 的拥塞控制和流量控制通常是一起实现的

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

流量控制是为了避免发送方的发送速度太快而接收方的速率跟不上而导致丢包的问题，因此发送方需要通过接收方的发送窗口 RWND 的信息来调整发送速度
拥塞控制是为了保证整个网络中的多个发送和接收方的通信效率，而不是为了单个的设备

RWND & CWND

接收窗口 RWND：在不 overflowing 的基础上，接收方的 buffer 最多能够接收的 byte 的数量
拥塞窗口 CWND：在不 overfitting 的基础上，router 能够发送的 byte 数量
CWND 的大小是 sender 维护和调整的，而 RWND 的大小时 receiver 决定的。

如何检测拥塞

三次冗余 ACK 表示轻度拥塞
超时 timeout 表示重度拥塞

如何处理拥塞

对于轻度拥塞（fast retransmission and recovery）：CWND 降为原来的一半，然后按照 CA 的方式线性增长
对于重度拥塞：CWND 变为 1，然后使用慢启动直到 CWND/2 然后进入 CA 阶段线性增长
通过乘性减、加性增的方式可以保证最终的拥塞控制可以达到 fairness and efficiency
单纯慢启动的缺点：每次都从 1 开始，效率低
结合快速重传（在轻度拥塞的时候）的方法，可以避免从 1 开始的慢启动状态，从而提高拥塞控制的效率

复用 Multiplexing / Demultiplexing

将多个单独的 stream（流）整合到一个流中，这个过程就叫做复用
将一个复合的流进行拆解，这个过程就是 demultiplexing

远程过程调用 RPC

远程调用一个过程（函数、方法、处理过程等），仿佛在本地调用一样，对用户来说是透明的
RPC 不是一个单独的 api 或者协议，而是有很多中不同的变体
假设机器 C 想让服务器 S 来完成计算任务，C 调用了一个 S 提供的接口，任务在 S 中被解决，然后结果传回 C，这就是 C 远程调用了 S 的某个功能或者进程
RPC 在概念上很简单，但是实现的过程中却很困难，因为：

RTP 实时传输协议

real time transport protocol
RTP是一种运行在 user space（ presentation层）的协议，通常基于 UDP 协议，但也支持 TCP 协议
RTP用来为IP网上的语音、图像、传真等多种需要实时传输的多媒体数据提供端到端的实时传输服务
RTP 将多个多媒体流进行复用整合成单个的 UDP segment

使用多媒体视频或者音频的时候可能会出现抖动的现象
对于 delay 的 packet，不同的算法的处理方式不同，有些是 wait 有些是直接 skip
buffer 的 size 也是随着不同的应用变化

网络层（Internet Layer）

建立在 link 链路层之上，为传输层提供服务
routers 通过多个路径进行 packet 的转发
packet 是如何到达目标主机的？主要采取如下两种网络服务模型（network service models）
- 基于连接的方式（connection-oriented）
- 基于非连接的方式(connectionless)
参考文章

connectionless

packet switch（internet protocol-IP)
被称为 datagram network
这种方式不事先确定路由的路线

connection-oriented

也叫做（虚拟电路交换）virtual circuit Switching
通常是事先确定的路由路径

存储转发分组交换（store & forward packet switching)

无论是基于连接的还是非连接的网络服务模型，都要使用存储和转发分组交换技术：
- router 收到一个完整的 packet，在转发之前临时性地存储它
每个 router 都会有一个 buffer，可以看做一个先入先出的队列，当这个 buffer 满了的时候，后面的 packet 无法加入队列，进而造成丢包问题（发送方会因为 timeout 而认为发生了 congestion）

connectionless （datagram model）

packet 包含了一个 destination 的地址，每个 router 会维护一个路由表，路由表中记录了去往每个destination 所采取的下一跳的节点信息，按照路由表来转发相应的 packet
不同的 packet 可能选择不同的路径到达目的地
路由表可能实时更新

connection-oriented(Virtual Circuit Model)

分为三个阶段：
- 建立连接阶段（circuit information stored in routers）
- 传输数据阶段（使用 circuit ）
- 结束连接阶段
packet 只需要 包含一个简短的 label 来识别对应的 circuit

connection v.s. connectionless

在这里插入图片描述

Multi-protocol label switching

ISP 指的是网络服务供应商
通过添加 MPLS 协议，原本需要对 packet 解包才能够获得的 destination address 现在被用一个 label 表示在 MPLS 中，因此可以直接在每个 router 中直接查到 destination 的地址并跳转
主要目的是为了服务质量（可以设置 packet 的优先级，在 ipv4 的 differentiated services 可以设置哪些是优先级高的 packet，哪些是优先级低的
商业中经常使用
较为昂贵，相同的流量话费通常是 20-100倍的代价

网络协议 IPV4 & IPV6

在这里插入图片描述

除了 internet 层，其他层的协议种类都很多，他们在 internet 层交汇

IP 协议设计原则 & 要求

可用性要很高，因为一个理想中性能很好但是很难实现的模型对于网络来说是没有意义的
简单
发送的时候严苛一些（多标记一些信息），接收的时候要宽容一些

职责是将 packets 从网络的源主机发送到目标主机
在网络中可以选择多条路径
使用路由算法来决定最终选择哪条路径
尽力而为（什么也不保证）

IPV4

在这里插入图片描述

version 版本号，是 v4 还是 v6
IHL 头部长度
Differentiated services 通过设置这个标志位运营商可以规定某些 packet 可以以高优先级的身份传输
Total length 代表数据部分的总长度
ID, DF, MF, Offset：用于对 packet 切分，ID 是 packet 的序号，被切分的 packet 应该具有相同的 ID，MF 表示当前的 fragment 是不是当前 ID 被切分的最后一段，Offset 是 fragement 的偏移量
TTL 是这个 packet 的存活时间，没经过一条 router 就减 1，减少到 0 的时候会被抛弃掉
Protocol 使用的传输层的协议
Source / Destination 表示 packet 发出的 ip 地址以及目标的 ip地址

IPV4 地址

注意 ip 地址其实并不是来标定主机的，而是标定接入网络的节点的，即 interface 的位置的。例如如果一个主机 host 接入了好几个网络，那么在这几个网络中他都是接入的 interface，那么他就可以有多个 ip 地址

地址种类（type）

单播地址（只有一个 destination）
广播地址（发送给局域网中的每一个设备）
多播地址（发送给局域网中的一部分设备）

地址级别（classes）

最开始的时候，ip 地址是按照等级划分的，A 级的地址是以 0 开头的地址，网络部分的长度是 7 个字节，主机有 24 个字节，因此 A 级网络全球只有 $2^7$ 128 个，每个 A 级网络下的主机数量可以有 $2^{24}$ 个，一般机构根本用不完
B 级网络以 10 开头，网络位数占了14位，也就是说 B 级网络的个数一共有 $2^{14}$ 个，每个 B 级网络能分配到 $2^16=65535$ 个主机，一般机构也用不完
C 级网络 110 开头，网络位数 21 位，也就是一共有 $2^21$ 个 C 级网络，每个网络只能分配 $2^8$ 个主机，这就很少了
按照这种原始的方式进行划分的特点是：
- 路由非常简单，只需匹配前几位就可以快速的完成网络的分级和转发任务
- 但是非常浪费，因为绝大多数机构用不完 B 级网络但 C 级又太小了，因此采用 Classless InterDomain Routing （CIDR）的方法

CIDR(Classless InterDomain Routing) 无类别域间路由选择

不再对网络进行分类，所有的网络号段一视同仁；通过子网掩码来标定一个网络的 network 部分和 host 部分
将网络划分成一个一个的 block，每个 block 中的主机都有相同的 prefix
这些分块的 network 又被叫做 subnet（子网）
这些子网是路由器提高效率的关键，因为路由器并不是在 host 之间建立路径，而是在不同的子网之间寻找最短的路径

路由聚集 (route aggregation)

在这里插入图片描述

聚集行为是自发的
通过聚集的行为可以不断的将多个 subnet 聚合到一起，这样将相关联的子网进行聚合对路由器来说可以减少选择，提高路由的效率（减小路由表中的表项）
前缀是可以重合的，但是在路由器寻找下一跳的时候，需要匹配具有最长匹配前缀的下一跳

特殊的 IPV4 地址

在这里插入图片描述

在一个子网中，假设已经确定了前 19 位是 network 的范围，那么也就是说 host 的段长度为 13，那么可以分配给主机的 address 数量其实是 $2^{13}-2$ 个有效的，因为主机号段中全 0 和全 1 的 ip 是预留的不能使用的，全 0 的是来标识这个网络的（网络地址），全 1 的是做广播的

IPV6

为了解决 IPV4 耗尽的问题
简化了头部，提高了安全性，更加精细地设计了 Quality of service 的支持
地址用不完

IPV6 地址

在这里插入图片描述

8 组 16 进制数，每组最多4 个
可以简化书写（当出现连续的 0 的时候）
可以与 IPV4 的地址兼容性书写
没有大规模应用

NAT(Network Address Translation)

NAT 的出现是为了解决 IPV4 的短缺问题；
它的原理是一堆 subnet 中的网络只通过一个网关参与公网的信息交流，而局域网中的 ip 均为 private ip
一般我们熟悉的 private ip 是：
- 172.16…/12
- 192.168…/16
- 10.0.0.0/8
而且通过这样的方式，公网的 ip 是可以重用的，例如一个区域中的代理商只有 20 个公网 ip，但是它也可以支持很多个 subnet，因为只需要每个 subnet （subnet 中可能有很多台设备，他们通过一个共同的网关介入公网）在参与公网的时候给它的网关分配一个公网 ip 即可
NAT 扮演了一个 “应用层访问代理” 的身份来代替 private ip 来访问公网的 ip
一个 subnet 中的所有设备都有 LAN 来分配 private ip 地址，这个 LAN 就是 local area network（局部区域网络）

工作原理

在这里插入图片描述

例如现在有四台设备通过一个 LAN 试图访问公网中的某个 ip，那么首先假设是计算机 A 发出了访问 baidu 的请求，那么这个 packet （A 机器的 ip=10.0.0.1， 5544 号端口发出）将会被发送到默认的网关，然后网关会通过 NAT Box 从这个设备上找一个没有被分配的 port 来完成映射关系，即（10.0.0.1,5544）-> (198.60.42.12, 3344) 然后以这个新的身份将 packet 经过路由器发送出去。当回复的 packet 要重新进入这个 subnet 的时候，通过 NAT 进行反过来的映射过程，将数据重新映射回 subnet 中的 A 主机 5544 端口即可
注意这里的 10.0.0.1 不是网关的 ip 而是 A 的 ip 地址

存在的问题

打破了端到端的原则，网络中的传输应该是从一个 source 主机到一个 destination 主机的模式，但是在这里必须要借助一个中介 NAT box
破坏了 IP 体系结构模型：即 internet上的每个接口都有唯一的IP地址（因为 NAT 存在的缘故，连接到internet的数百万接口都有相同的地址（私有地址））
破坏了层级模型（layering violation)
将网络的模型结构从“connectionless” 变成了 pseudo-connectio-oriented，因为 NAT 维持了那些 subnet 中的网络介入公网的能力，一旦 NAT box 损坏，那么 subnet 中的所有的网络都无法接入公网
有限的接入能力，因为 NAT 只有 16 bit 位的 ports，所以最多允许 $2^16$ 个 outgoing connection

优势

缓解了 IPV4 紧张的问题，运营商只会给用户 private ip
非常好的安全性，因为从外部无法访问到 private 网络中的主机，保障了安全性，但是不能替代防火墙
即使在IPv6广泛部署且IP地址不再稀缺之后，仍有可能继续使用

Fragmentation（切片）

分割 packet 的原因

链路的 MTU 可能无法支持很多很大的 packet
分层协议栈的性质意味着较低层可能需要能够分割较大的数据包
数据包路径上限制最大的链路可能位于发送方未连接的链路上（潜在的限制）
将数据包划分为碎片）允许网关满足 size constraints

Fragmentation 的方法

对于 packet 的切分容易，但是重新组合更加困难

Transparent fragmentation

当 packet 进入一个子网的时候进行 fragment，出去之前重新拼接；后面的 router 意识不到 fragement 的发生，在下一个子网中依然如此进行

Nontransparent Fragmentation

拼接发生在最终的目标主机上；中间过程中不进行拼接的行为，所以中间的 router 都知道 fragment 发生了，因此是不透明的
透明与不透明指的是对 router 来说 fragement 的操作是否可见

Fragmentation 的步骤

切分步骤
- 将一个大的 packet 切成小段
- 复制 ip header 给每一个 fragment
- 设置 offset 标识
- 设置 MF 标识
接收步骤
- 将所有 ID 相同的 fragement 进行拼接，按照 MF 判断后面是否还有没拼完的 fragement
如果忽略 header 的时候，直接切分成 fragement，那么这些小的 fragement 的标识设置应该如下
但真实情况下，我们的 MTU 中也要包含 header 的长度，因此 MTU=1500 的时候 header=20 那么数据只能最大长度为 1480
同时 fragement 的最小单元是 8 个 byte，offset 是按照最小单元来设置的，而不是按照单纯的 byte 数量
将一个 5000 byte 的数据切分成 MTU = 1500 的 fragement，首先每个 header 的长度是 20，因此最大的数据长度应该是 1480，因此第一个 fragement 的各个参数分别是：
- ID=77
- DF=0
- MF=1
- Offset=0
第二个 fragement 的数据部分是从原始数据中的第 1480 byte开始的，因此其 offset=1480 / 8 = 185
第三个 fragement 的数据部分是从第 1480 + 1480 个字节开始的，因此 offset = 1480 * 2 / 8 = 375
第四个 fragement 的数据部分是从第 1480 + 1480 + 1480 个字节开始的，因此 offset = 1480 * 3 / 8 = 555
第四个 fragement 的长度只有 4980 - （1480）*3=540

Fragmentation 的缺点

对于 router 和 host 来说工作量太大
放大了丢包的影响，因为只要有一个 fragement 丢失了，那么整个 packet 都要重新全部发送一遍
存在安全漏洞

Path MTU Discovery

检测路径中的 MTU ，可以帮助我们避免 fragement，因为得到链路中的 MTU 之后主机可以直接发小的 packet，就不需要在中间进行切分了
这是现在常用的一种方法

检测方法

host 向 destination 发一个很大的 packet，如果中间的 router 觉得这个包超过了自己的 MTU，那么会发送一个反馈给 host，告诉他这个包太大了，换小一点
问题是：可能导致开始的 packet 丢失，但是 host 可以讯速地知道最合适的发送尺寸来减少后续的丢包问题
IPV4 支持 nontransparent fragement 或者 path MTU discovery
IPV4 的最小接收尺寸是 576 bytes
IPV6 期望主机使用 path MTU Discovery
在 iPV6 中主机不会 fragement
ipv6 的最小接收尺寸是 1280 bytes

子网 subnet

多个具有相同前缀的网络可以进行 aggregation 称为一个更大的 subnet，同样的，一个大的网络也可以进行拆分成为几个子网
当一个 packet 到达 internet，路由器会使用子网掩码来匹配一个子网然后将 packet 发过去，而不是寻找某个单独的 host 进行 packet 的发送行为

在这里插入图片描述

路由算法 Routing algorithm

路由算法的目的是为了建立 router 中的路由表，因此他们在进行转发的时候就知道去往目的地的下一跳应该去往哪个 router，在下图中，如果 A 想去往 F，那么下一跳应该去往 C

路由算法应该具备的性质

正确性：找到一条从 source 到 destination 的有效路径
简洁性
鲁棒性：即使中途的某个 router 挂机了，也能够迅速调整到一条没有问题的新路径
稳定性：在条件不变的情况下，路由的路径不应该频繁发生变更
公平性
高效
实施政策的灵活性

在这里插入图片描述

如果A和A’、B和B’以及C和C’之间有足够的流量使水平链路饱和，那么处理X和X’之间的流量的最有效的方法是什么？（即，什么使网络吞吐量最大化？）

静态路由算法（static routing）

不随网络拓扑的变化而更新，
路由表经过离线计算并且上传到路由器中固定
对 failure 的情况没有响应
这种算法适合家庭内部网络这种非常小而且固定成员的方式

动态路由算法（adaptive）

当网络中的拓扑结构发生变化的时候，路径也会及时更新
根据一些衡量指标（距离，跳数，转发时间）等并尽可能地降低指标
从邻居 router 获得信息或者试图获得整个网络的宏观拓扑信息

洪泛算法（Flooding）

最简单的动态路由算法
- 可以保证最短的路径和最小的延迟
- 非常鲁棒，只要路径存在，就能找到
- 非常低效，因为会产生大量的冗余 packet
- 需要借助 packet 中设置的 TTL 来清除冗余的 packet

在这里插入图片描述

但是洪泛不走回头路，注意下面图示中的箭头方向

迪杰斯特拉算法（Dijkstra) / Link State

可以参考我的另一篇文章：路由选择算法

在这里插入图片描述

使用地杰斯特拉算法的最终目的是为了找到一棵 sink tree，之所以是 tree 不是 graph，是因为 tree 没有环路
Link state routing 是基于分布式的算法，取代了距离向量算法，因为距离向量算法的收敛速度非常慢
link state 算法的五个步骤：
获得到自己 neighbor 的代价，它到所有邻居的代价信息叫做它自己的链路状态信息
然后通过洪泛的方式将自己和 neighbor 的之间的链路状态信息传播到全网中所有的 routers
同时也接收全网其他的 router 发来的洪泛信息，借此可以构建整个网络的拓扑结构
在构建的网络拓扑中使用 dijkstra 算法获得到 destination 的最小的代价路径
在得到其他 router 的时候使用 flooding 的方式有如下优缺点：
- flooding 是非常可靠的方式，收到洪泛信息的 routers 都会给出一个确认信息告诉当前的节点它们已经收到了当前节点的链路状态信息
- 为了避免资源的浪费，每个 router 会保留这个状态信息，如果下次再从其他 router 收到相同router 的洪泛信息，就直接丢弃不做处理
- 使用 32 bit 的 sequence number 来避免出现环
- 如果某个 router 损坏，它将会重启 sequence number from 0
  - 解决的办法是使用 age field，没经过一秒，它就会减 1，减到 0 的时候这个 packet 就被丢弃了