计算机网络复习笔记

Author：AlexEz Mail：mao.looper@gmail.com
若发现错误和遗漏请指正
原创，禁止转载

1 计算机网络概述

接口与协议的区别

接口规定了运行在一个端系统上的程序请求因特网基础设施向运行在另一个端系统上的特定目的地程序交付数据的方式

协议定义了在两个或多个通信实体之间交换的报文的格式和顺序，以及报文发送/或接收一条报文或其他事件所采取的动作。

TCP/IP只是一个协议栈，就像操作系统的运行机制一样，必须要具体实现，同时还要提供对外的操作接口。这个就像操作系统会提供标准的编程接口，比如win32编程接口一样，TCP/IP也要提供可供程序员做网络开发所用的接口，这就是Socket编程接口。

1.1 网络概念

网络：许多计算机连在一起
互联网： internet 许多网络连在一起
因特网： Internet 全求最大的互联网

1.2 数据交换方式

电路交换（Circuit Switching）实时性、建立专用路线
报文交换（Message Switching）报文一般比分组长、报文交换的时延较长
分组交换（Packet Switching）高效、迅速时延高
- 路由器存储转发功能

1.3 网络分类

按作用范围分：

新的理解，不单单从网络覆盖的范围来区分广域网、局域网

使用了广域网技术即广域网

使用了局域网技术即局域网

局域网：自己花钱购买设备、自己维护、带宽固定（100M，1000M），距离一般在100m以内
广域网：花钱买服务、花钱买带宽

1.4 网络的性能指标

速率：数字信道上传送数据位数的速率
带宽：数字信道能传送的最高速率 (b/s)
吞吐量(Throughput)：发送端与接收端之间传送数据速率（b/s）瓶颈链路
时延：
- 发送(传输)时延(transmission delay)=$分组长度(bit)/链路带宽(bit/s)$
- 传播时延(propagation delay)=$物理链路长度(m)/信号在信道上的传播速率(m/s)$
- 处理时延：差错检测、确定输出链路，一般<msec
- 排队时延：分组在路由器缓存中排队产生，等待输出链路可用
  - 丢包：分组到达速率超出输出链路容量时，超出部分丢弃
时延带宽积=$传播时延\times带宽$ ;又称以比特为单位的链路长度
RTT（Round-Trip Time）往返时间
利用率：
- 信道利用率
- 网络利用率：信道利用率加权平均值

1.5 网络体系结构

优点：模块化的分层易于系统的更新、维护，任何一层服务的改变对于系统其他层都是透明的

1. 概念

实体（Entity）：交换信息的硬件或软件进程
协议（Protocol）：控制两个对等通信的规则
服务（Service）：下层向上层提供服务，上层需要下层提供的服务来实现本层的功能
服务访问点（SAP）：相邻两层实体间交换信息的地方

2. OSI参考模型

（Reference Model）

1 物理层

编码方式
- 单/双极性不归零码
- 单/双极性归零码 (缺点：无法判断结束信号)
- 曼切斯特编码
- 差分曼切斯特编码（抗干扰更强）
传输模式
- 单工（Simplex）
- 半双工（half-duplex）
- 全双工（full-duplex）
接口特性
- 机械、电气、功能、规程特性
比特同步
- 时钟同步

2 数据链路层

负责结点-结点（node-to-node）数据传输
组帧（Framing）
物理寻址（Physical addressing）
流量控制（Flow control）
- 避免淹没接收端
差错控制（Error control）
- 检测并重传损坏或丢失帧，并避免重复帧
访问(接入)控制（Access control）
- 在任一给定时刻决定哪个设备拥有链路（物理介质控制使用权）

3 网络层

负责源主机到目的主机数据分组（packet）交付：跨越多个网络
逻辑寻址（Logical addressing）：全局唯一，IP地址
路由（Routing）：路径选择
分组转发

4 传输层

负责源-目的（端-端）（进程间）完整报文传输
报文分段与重组
SAP寻址
- 确保将完整报文提交给正确进程，如端口号
连接控制
流量控制
差错控制

5 会话层

对话控制（dialog controlling）
- 建立、维护
同步（synchronization）
- 在数据流中插入“同步点”
最“薄”的一层

6 表示层

处理两个系统间交换信息的语法与语义（syntax and semantics）问题
数据表示转化
- 转换为主机独立的编码
加密/解密
压缩/解压缩

7 应用层

支持用户通过用户代理（如浏览器）或网络接口使用网络(服务)
典型应用层服务
- 文件传输（FTP）
- 电子邮件（SMTP）
- Web（HTTP）
- ……

通信过程

数据封装

增加控制信息：构造协议数据单元（PDU）
- 地址（Address）：标识发送端/接收端
- 差错检测码（Error-detecting code）
- 协议控制（Protocol control）：实现协议功能的附加信息

网络排错

从底层到高层

物理层安全

数据链路层安全：ADSL、无线AP

网络层安全

应用层安全：SQL注入漏洞、上传漏洞

3. TCP/IP参考模型

实际网络的运行方式

IP over Everything

4. 5层参考模型

综合OSI和TCP/IP的优点

5层结构

应用层: 通过应用进程间的交互来完成特定网络应用。应用层协议定义的是应用进程间通信和交互的规则。

FTP, SMTP, HTTP
传输层: 运输层的任务是负责为两个主机中进程之间的通信提供通用的数据传输服务。应用进程利用该服务传送应用层报文：

TCP, UDP
网络层: 网络层为分组交换网上不同主机提供通信服务。网络层将运输层产生的报文段或用户数据报封装成分组和包进行传送

IP协议、路由协议等
链路层: 两台主机间的数据传输，总是一段一段在数据链路上传送的，这就需要使用专门的链路层协议。在两个相邻节点间的链路上传送帧，每一帧包括数据和必要的控制信息（如同步信息，地址信息，差错控制等）。相邻网络元素（主机、交换机、路由器等）的数据传输

以太网（Ethernet）、802.11 (WiFi)、 PPP
物理层:比特传输

数据封装

2. 应用层

2.1 体系结构

1. 客户机/服务器结构（Client/Server）

服务器

24小时不间断提供服务

永久性访问地址/域名

利用大量服务器实现可扩展性
客户机

使用服务器提供的服务

间歇性接入网络

可能使用动态IP地址

不会与其他客户机直接通信

2. P2P结构（peer-to-peer）

没有永远在线的服务器
任意端系统/节点之间可以直接通讯
节点间歇性接入网络
节点可能改变IP地址

高度可伸缩，难以管理

3. 混合结构

综合以上两者的优点，规避缺点。如Napster

2.2 进程间通信

1. Socket

客户机进程：发起通信的进程

服务器进程：等待通信请求的进程

同一主机上的进程通信有进程间通信机制，由操作系统提供：管道、消息队列、共享内存、信号量

不同主机间的进程通信：使用套接字（Socket）,也称为网络编程的API

2. 寻址

IP地址
端口号/Port number
- 为主机上每个需要通信的进程分配一个端口号

3. 应用层协议

网络应用需遵循应用层协议
公开协议：由RFC（Request For Comments）定义
私有协议 : 多数P2P共享文件应用
消息类型（type）
消息语法（syntax）
字段语义（semantics）
规则（rules）

2.3 Web应用

1. HTTP协议

C/S结构
请求(命令)/响应交互模式
使用TCP传输服务
- 服务器在80端口等待客户请求
- 浏览器发起TCP连接请求
- 服务器接受TCP连接
- 交换HTTP消息
- 关闭TCP连接
无状态（stateless）
- 服务器不维护任何有关客户端过去所发请求的信息
1.0version 非持久性连接
- 每次传输一个对象
- 任何格式的内容都可以发送，这使得互联网不仅可以传输文字，还能传输图像、视频、二进制等文件
- 有GET、POST、HEAD请求命令
- 响应时间：2RTT+文件发送时间
1.1version 持久性连接
- 每次可传输多个对象
- 支持长连接（persistent connection）和请求的流水线（pipelining），connection字段默认keep-alive
- 错误通知的管理：新增了24个错误状态码
- 带宽优化及网络连接的使用：增加range头域，允许只请求资源的某个部分
- 新增方法：PUT、 PATCH、 OPTIONS、 DELETE
请求消息
响应消息
2.0 version 提升性能
- 多路复用，允许同时通过单一的HTTP/2连接发起多重的请求-响应消息
- 二进制分帧，文本表示形式多样，需要考虑较多场景，二进制比文本更方便健壮
- header压缩，通讯双方各自cache一份header fields表避免重复header传输
- 服务端推送
3.0 version QUIC实现机制
- 基于UDP协议
- 快速重启会话（支持手机网络切换），使用uuid来标识每一次连接，网络环境变化但uuid不变就不需要握手
与HTTPS的区别
- https需要到CA申请证书
- http运行在tcp上，所有传输的数据都是明文的，https运行在SSL/TLS之上，所有传输的内容都经过加密
- http默认端口为80，后者是443
HTTPS工作流程

第一步：客户使用https的URL访问Web服务器，要求与Web服务器建立SSL连接。

第二步：Web服务器收到客户端请求后，会将网站的证书信息（证书中包含公钥）传送一份给客户端。

第三步：客户端的浏览器与Web服务器开始协商SSL连接的安全等级，也就是信息加密的等级。

第四步：客户端的浏览器根据双方同意的安全等级，建立会话密钥（随机产生），然后利用网站的公钥将会话密钥加密，并传送给网站。

第五步：Web服务器利用自己的私钥解密出会话密钥。

第六步：Web服务器利用会话密钥加密与客户端之间的通信。
Q: 用户访问一个网站的时候背后的过程与步骤是怎样的？

A: 基本流程：

利用DNS协议进行域名解析 –> 建立tcp协议三次握手过程 –> 客户端发出访问网站相应页面请求（发出http协议请求报文） –> 服务端发出相应访问页面的响应信息（发出http响应报文） –> 断开tcp协议四次挥手过程
1. DNS查询顺序：Hosts表–>本地DNS缓存–>上层DNS(迭代、泛洪)
2. 在本机与目标服务器之间的路由过程，包括IP协议、ARP协议、OSPF协议、BGP协议
3. 拿到响应消息了还需要浏览器进行解析渲染

记录用户状态，有隐私问题

响应消息cookie头部行
请求消息cookie头部行
保存在客户端主机上的cookie文件，由浏览器管理
Web服务器后台数据库

3. Web缓存/代理服务器技术

一般由ISP架设

在不访问服务器的前提下满足客户端的HTTP请求
缩短客户请求的响应时间
减少机构/组织的流量
在大范围内实现有效的内容分发（CDN）

条件性GET方法更新缓存的数据，解决一致性问题

2.4 Email应用

1. 邮件客户端（user agent）

2. 邮件服务器（mail server）

邮箱：储存发给该用户的Email
消息队列（message queue）：存储等待发送的Email

3. SMTP协议（Simple Mail Transfer Protocol）

客户端：发送消息的服务器
服务端：接受消息的服务器
使用TCP进行Email消息的可靠传输
端口25
传输三个阶段
- 握手
- 消息传输
- 关闭
命令/响应交互模式
- 命令command ：ASCII文本
- 响应 response：状态代码和语句

//先去qq邮箱打开smtp，获取授权码
//输入需要进行base64加密
c:telnet smtp.qq.com 25
s:220 xxx.qq.com
c:helo host //打招呼
s:250 xxx.qq.com
c:AUTH LOGIN     //登录认证
s:334 VXNbWU6 //输入账号
c:MTA3MxcS5jb20=
s:334 UGFc3d6 //输入授权码
c:dWdwaXF5Y3ZzraWhQ==
s:235 Authentication successful
c:mail from: <1073788244@qq.com> //来自
s:250 OK
c:rcpt to: <1073788244@qq.com> //发往
s:250 OK
c:data
s:354 End data with <CR><LF>.<CR><LF>.
c:here is what i want to send
c:.
s:250 OK: queued as.
c:quit
s:221 bye

MIME:多媒体邮件扩展，在头部行增加扩展

4. 邮件访问协议

用于从服务器获取邮件

POP: Post Office Protocol

较简单，认证授权和下载

无状态
IMAP: Internet Mail Access Protocol

更多功能，更复杂

有状态
HTTP

2.5 DNS应用

1.DNS服务

Domain Name System

解决Internet上主机/路由器的识别问题

域名向IP地址的翻译
主机别名
邮件服务器别名
负载均衡：Web服务器

多个IP地址对应一个名字

2.分布式层次式数据库

解决的问题：
- 单点失败问题
- 流量问题
- 距离问题
- 维护性问题
根域名服务器
- 不知道映射访问权威域名服务器
- 全球13个
顶级域名服务器(TLD, top-level domain)
- com, org,net, edu等
权威域名服务器(Authoritative)
- 组织的域名解析服务器
本地域名解析服务器
- 不严格属于层级体系发
- 每个ISP有一个
- 主机进行查询发送给本地进行代理
- 迭代查询：代理进行多次询问
- 递归查询：代理询问一次让其他服务器去找

4. DNS记录和消息格式

1.DNS记录

资源记录（RR，resource records）

format：(name, value, type, ttl)

2.DNS协议与消息

查询（query）和回复（relpy）消息

消息格式相同

同时使用TCP（区域传输时）和UDP（域名解析时）

2.6 P2P应用

文件分发比C/S架构快

1. BitTorrent

文件分为chunk
- 获取：稀缺优先、定期查询邻居持有的chunk列表
- 发送：tit-for-tat
节点可自由加入和离开

Q：为什么运营商会封BT？

A：很简单，影响网络运营商超卖带宽了。ISP尤其是国内ISP最大的问题是，给用户提供网络接入服务，但从不保证服务质量。宣传上的“100M带宽光纤入户”从来不意味着你真的能用上100M带宽。甚至ISP从主观上，会用各种手段限制你，不让你用满这100M带宽。

抛开远端服务器和整体网络链路的因素以外，跑不满100M最主要原因在于ISP超卖，他们手里总共有1000M带宽，就敢给20家住户每家卖100M带宽，然后祈祷这20家不要同时把100M带宽跑满。只要你用任何技术手段，不管是BT CT 还是ET，只要大部分用户能这个技术稳定跑满带宽，ISP就会对这个技术恨得牙痒痒，恨不得封杀了之~除此以外的理由都是借口。
链接：https://www.zhihu.com/question/310343843/answer/618352530

2. 索引设计

集中式索引：增设中央服务器
- 单点失效问题
- 性能瓶颈
- 版权问题
洪泛式查询：query flooding
- 覆盖网络（overlay network）： Graph
- 有很大的网络负担
- 查询消息通过已有TCP连接发送
- 节点转发查询消息
- 查询命中反向路经返回
层次式覆盖网络
- 介于集中与洪泛之间
- 节点和超级节点间维持TCP连接：集中
- 某些超级节点之间维持TCP连接：洪泛
- 如：skype

2.7 Socket编程

1. Socket API

标识通信端点（对外）：IP地址+端口号
操作系统/进程管理（对内）：套接字描述符(socket descriptor)

类型：

SOCK_STREAM: TCP协议
SOCK_DGRAM: UDP协议
SOCK_RAW：面向网络层

函数：

WSAStartup() 使用之前调用，初始化socket动态链接库
WSACleanup() 使用之后调用
socket() 创建套接字
closesocket() 关闭套接字，引用为0关闭
bind() 为套接字设置本地端点地址，
- 客户程序一般不必调用
- 服务端使用地址通配符 INADDR_ANY
listen() 仅服务端，TCP连接，置服务器端的流套接字处于监听状态，设置连接请求队列大小
connect() 仅客户端，客户端调用使其与特定计算机的特定端口的套接字进行连接
accept() 服务器端，用于TCP连接，创建一个新的套接字与客户通信，因为TCP连接是点对点的，实现并发的TCP服务器
send() 有连接的方式TCP(客户与服务器)，或调用了connect函数的UDP(客户)套接字
sendto() 无连接方式UDP(服务器)，或未调用connect函数的UDP客户端套接字
recv() 同上
recvfrom() 同上

2. API调用流程

网络字节顺序：实现本地字节顺序与网络字节顺序进行转换

基本服务类型：

循环无连接
循环面向连接
并发无连接：创建子进程处理
并发面向连接

2.8 CDN

内容分发网络

DASH（Dynamic Adaptive Streaming over HTTP）经HTTP的动态适应流

可以压缩生成相同视频的多个版本，每个版本有不同的质量等级。

CDN管理分布在多个地理位置上的服务器，在它的服务器中存储视频（或其他资源）的副本，并且所有试图将每个用户请求定向到一个将提供最好的用户体验的CDN位置

3. 传输层

传输层协议为运行在不同Host上的应用进程提供了一种逻辑通信机制

位于网络层之上

依赖于网络层的服务

对网络层服务进行增强

3.1 传输层服务

1. 多路复用/分用

此处的复用和分用是逻辑上的概念

发送端多路复用：处理来自多个套接字的数据，添加传输头

Q: I/O多路复用技术（multiplexing）是什么？

A：

常见的IO操作，如read和write，通常是阻塞IO，也就是说当你调用read时，如果没有数据收到，那么线程或者进程就会被挂起，直到收到数据。这样在处理大量连接时可能需要很多线程，比如4个核要跑1000个线程，那么每个线程的时间槽非常短，而线程切换非常频繁，大量时间花费在上下文切换。

此时引入非阻塞IO的概念，通过fcntl（POSIX）或ioctl（Unix）设为非阻塞模式，这时，当你调用read时，如果有数据收到，就返回数据，如果没有数据收到，就立刻返回一个错误，如EWOULDBLOCK。这样是不会阻塞线程了，但是你还是要不断的轮询来读取或写入。

于是，我们需要引入IO多路复用的概念。多路复用是指使用一个线程来检查多个文件描述符（Socket）的就绪状态，比如调用select和poll函数，传入多个文件描述符，如果有一个文件描述符就绪，则返回，否则阻塞直到超时。得到就绪状态后进行真正的操作可以在同一个线程里执行，也可以启动线程执行（比如使用线程池）。这样在处理1000个连接时，只需要1个线程监控就绪状态，对就绪的每个连接开一个线程处理就可以了，这样需要的线程数大大减少，减少了内存开销和上下文切换的CPU开销。

接收端多路分解：使用传输头信息交付接收到的段到正确的套接字

注意：服务端一个进程有多个线程，一个线程有多个套接字

UDP的socket用二元组标识
TCP的socket用四元组标识

2.可靠数据传输机制

Q：什么是可靠（reliable）？

A：不错、不丢、不乱

信道的不可靠特性决定了可靠数据传输协议（RDT）的复杂性

接口的结构：

RDT版本

Reliable Data Transfer

Rdt 1.0：可靠信道

Rdt 2.0: 产生位错误的信道

利用校验和检测位错误
确认机制（Acknowledgments，ACK）：正确接收
NAK：告知分组有错，重传分组
基于这种重传机制的rdt协议称为ARQ（Automatic Repeat reQuest）协议
FSM(Finit State Machine)规约

Rdt 2.1: 应对ACK/NAK破坏

发送方为每个分组增加序列号
两个序列号（0，1）就够用了，因为只用记住当前的序列号
接收方判断分组是否重复
发送方
接收方

Rdt 2.2：无NAK消息协议

接收方通过ACK告知最后一个被正确接受的分组
发送方接收到重复ACK之后，重传当前分组
FSM（相比2.1有较大简化）

Rdt 3.0: 信道既可能发送错误，也可能丢失分组

发送方等待“合理”时间，如果没有收到ACK，重传
添加定时器
时延有影响
性能很差
网络协议可能影响物理资源的利用

流水线协议

流水线机制提高资源利用率
需要更大的序列号范围
需要更大的存储空间以缓存分组

滑动窗口协议

Sliding-window protocol

窗口
- 允许使用的序列号范围
- 窗口尺寸为N: 最多有N个等待确认的消息
滑动窗口
- 随着协议的运行，窗口在序列号空间内向前滑动

Go-Back-N（GBN）协议

发送方：
- 设置一个计时器
- ACK(n): 确认到序列号n(包含n)的分组均已被正确接收
- 超时Timeout(n)事件：重传序列号大于等于n，还未收到ACK的所有分组
接收方：
- ACK机制：发送拥有最高序列号的、已被正确接收的分组的ACK
  - 可能产生重复的ACK
  - 只需要记住唯一的expectedseqnum
- 乱序到达的分组
  - 直接丢弃-> 没有缓存
  - 重新确认序列号最大的、按序到达的分组
Selective Repeat（SR）协议

发送方

只重传没有接收到ACK的分组
N个连续的序列号
用单个硬件定时器模拟多个逻辑定时器

接收方

对每个分组单独进行确认
设置缓存机制，缓存乱序到达可以

序列号空间大小与窗口尺寸应满足的关系：

$发送方窗口尺寸+接收方窗口尺寸\le可用序列号个数(2^k, k为序列号使用位数)$

TCP可靠数据传输

累计确认，返回期望收到的
使用单一重传定时器

定时器时间设置：
$TimeoutInterval=EstimatedRTT+4*DevRTT$

即EstimatedRTT+“安全边界”

$EstimatedRTT=(1-\alpha)\cdot EstimatedRTT+\alpha \cdot SampleRTT (typically, \alpha=0.125)$

$DevRTT=(1-\beta)\cdot DevRTT+\beta \cdot |SampleRTT-EstimatedRTT| (typically, \beta =0.25)$
快速重传机制

如果sender收到对同一数据的3个ACK，则假定该数据之后的段已经丢失，在定时器超时之前立即重传。

Q:为什么是三次冗余ACK？

A: 假定通信双方A和B发送4个TCP Segment

TCP segment 乱序有2/5 = 40%的概率会造成A收到三次 duplicated ACK(N);

而如果 N 丢了，则 A 有100%概率会收到三次duplicated ACK(N);

基于以上的统计，当 A 接收到三次 duplicated ACK(N)启动 Fast Retransmit 算法是合理的，即立马 retransmit N，可以起到 Fast Recovery 的功效，快速修复一个丢包对 TCP 管道的恶劣影响

而如果 A 接收到二次 duplicated ACK(N)，则一定说明是乱序造成的，即然是乱序，说明数据都到达了 B，B 的 TCP 负责重新排序而已，没有必要 A 再来启动 Fast Retransmit 算法

3. 流量控制机制

消除发送发使接受方缓存溢出的可能，是一种速度匹配服务，发送发发送速率与接收方的读取速率匹配。

TCP流量控制：

Receiver通过在Segment的头部字段将RcvWindow告诉Sender

$rwnd = RcvBuffer – (LastByteRcvd – LastByteRead)$
Sender限制自己已经发送的但还未收到ACK的数据不超过接收方的空闲RcvWindow大小

$LastByteSent – LastByteAcked \le rwnd$

4. 拥塞控制机制

发送方维持一个叫做拥塞窗口cwnd（congestion window）的状态变量。拥塞窗口的大小取决于网络的拥塞程度，并且动态地在变化。发送方让自己的发送窗口等于拥塞窗口，另外考虑到接受方的接收能力，发送窗口可能小于拥塞窗口。

MSS（maximun segment size）最大报文段大小，不包括TCP/IP首部的长度，典型值为1460字节

代价：

当分组到达速率接近链路容量时，分组将经历较长的排队时延。
发送方必须执行重传以补偿因为缓存溢出而丢弃(丢失)的分组。
在多跳网络中，当分组被drop时，任何用于该分组的”上游“传输能力全都被浪费掉

控制方法：

端到端拥塞控制：在端到端拥塞控制方法中，网络层没有为传输层拥塞控制提供显式支持。即使在网络中存在拥塞，端系统也必须通过对网络行为的观察(如分组丢失与时延) 来推断拥塞的发生。

TCP 必须通过端到端的方法处理拥塞控制，因为 lP 层不会向端系统提供有关网络拥塞的反馈信息。TCP报文段的丢失(通过超时或 3 次冗余确认而得知)被认为是网络拥塞的一个迹象，TCP会相应地减小其发送窗口长度。具有公平性。
- $LastByteSent-LastByteAcked\le CongWin$
- $rate\approx \frac {CongWin}{RTT} Bytes/sec$
- 加性增-乘性减（AIMD）
- Additive Increase：每个RTT将CongWin增大一个MSS–拥塞避免
  - Multiplicative Decrease：发生loss后将CongWin减半
  - 锯齿状

慢启动

cwnd的值以一个MSS开始，并且每当收到一个传输报文段的确认时就增加1MSS（相当于变为2倍）

拥塞避免

也就是每个传输轮次，拥塞窗口cwnd只能线性加一，而不是像慢开始算法时，每个传输轮次，拥塞窗口cwnd按指数增长。

发生超时重传，判断网络可能出现拥塞：

将ssthresh的值更新为发生拥塞时的cwnd的一半
将cwnd的值减小为1，并重新开始执行慢启动算法

快速恢复

发送方一旦收到3个重复确认，就知道现在只是丢失了个别的报文段。于是不启动慢开始算法，而执行快恢复算法

发送方将慢开始ssthresh的值和拥塞窗口cwnd值调整为当前窗口的一半，开始执行拥塞避免算法
也有的快恢复实现是把快恢复开始时的拥塞窗口cwnd值再增大一些，即等于新的ssthresh+3
- 既然发送方收到3个重复的确认，就表明有3个数据报文段已经离开了网络;
- 这3个报文段不再消耗网络资源而是停留在接收方的接收缓存中;
- 可见现在网络中不是堆积了报文段而是减少了3个报文段。因此可以适当把拥塞窗口扩大些。

在这里插入图片描述

Q: 何时将指数增长切换为线性增长：

A：当CongWin达到Loss事件前值的1/2时,即到达Threshold

添加变量Threshold，发生loss时将其设置为CongWin达到Loss事件前值的1/2

发生Timeout时，Threshold设置为1/2CongWin，直接将CongWin设为1MSS，

网络辅助的拥塞控制：在网络辅助的拥塞控制中，网络层设备件(即路由器)向发送方提供关于网络中拥塞状态的显式反馈信息。这种反馈可以通过数据报中的某个字段来指示链路中的拥塞情况。这种方法在早期的 IBM SNA 和 ATM 等体系结构中采用。

对于网络辅助的拥塞控制，拥塞信息从网络反馈到发送方通常有两种方式，直接反馈信息可以由网络路由器发给发送方。另一种形式是，路由器标记或更新从发送方流向接收方的分组中的某个字段来指示拥塞的产生(可以理解为对经过一个拥塞路由器的数据报做记号)。一旦接收方收到这个有拥塞标记的分组，就会通知发送方网络发生了拥塞。

3.2 Internet传输层协议

1. UDP

User Datagram Protocol

为什么存在？

无需建立连接

实现简单：无需维护连接状态

头部开销少

没有拥塞控制：应用可更好的控制发送时间和速率

特点：

基于Internet IP协议
- 复用/分用
- 简单的错误校验
“Best effort”服务
- 可能丢失
- 可能非按序到达
- 在应用层增加可靠性机制
无连接
- 发送方和接受方不需要握手
- 每个UDP段的处理独立于其他段

应用：

流媒体（容许错误、速率敏感）
DNS
SNMP

可靠性保证

在应用层添加可靠性保证
与具体应用相关的错误恢复
在http 3.0中使用
http3.0 with google quick

报文格式：

分解示意图：

UDP长度字段包含首部长度

单位：字节

校验和（checksum）：检测UDP段在传输中是否发生错误（如位翻转）

2. TCP

Transmission Control Protocol

特点：

点对点
可靠的、按序的字节流
流水线机制
发送方/接收方缓存
全双工
面向连接
流量控制机制

报文格式：

连接管理

三次握手

三次握手（Three-way Handshake）其实就是指建立一个TCP连接时，需要客户端和服务器总共发送3个包。进行三次握手的主要作用就是为了确认双方的接收能力和发送能力是否正常、指定自己的初始化序列号为后面的可靠性传送做准备。实质上其实就是连接服务器指定端口，建立TCP连接，并同步连接双方的序列号和确认号，交换TCP窗口大小信息。

握手过程：

刚开始客户端处于 Closed 的状态，服务端处于 Listen 状态。

第一次握手：客户端给服务端发一个 SYN (同步)报文，并指明客户端的初始化序列号 ISN(Initial sequence number)。此时客户端处于 SYN_SEND 状态。

首部的同步位SYN=1，初始序号seq=x，SYN=1的报文段不能携带数据，但要消耗掉一个序号。
服务端得出结论：客户端的发送能力、服务端的接收能力是正常的。

第二次握手：服务器收到客户端的 SYN 报文之后，进行资源分配（可能受到SYN Flood攻击，可以使用SYN cookie进行防御），以自己的 SYN 报文作为应答，并且也是指定了自己的初始化序列号 ISN。同时会把客户端的 ISN + 1 作为ack（确认号）的值，表示自己已经收到了客户端的 SYN，此时服务器处于 SYN_REVD 的状态。
- 在确认报文段中SYN=1，ACK=1，确认号ack=x+1，初始序号seq=y。
- 客户端得出结论：服务端的接收、发送能力，客户端的接收、发送能力是正常的。不过此时服务器并不能确认客户端的接收能力是否正常。
第三次握手：客户端收到 SYN 报文之后，会发送一个 ACK 报文，当然，也是一样把服务器的 ISN + 1 作为 ack 的值，表示已经收到了服务端的 SYN 报文，此时客户端处于 ESTABLISHED 状态。服务器收到 ACK 报文之后，也处于 ESTABLISHED 状态，此时，双方已建立起了连接。

确认报文段SYN=0，ACK=1，确认号ack=y+1，序号seq=x+1（初始为seq=x，第二个报文段所以要+1），ACK报文段可以携带数据，不携带数据则不消耗序号。
服务端得出结论：客户端的接收、发送能力正常，服务器自己的发送、接收能力也正常。

发送第一个SYN的一端将执行主动打开（active open），接收这个SYN并发回下一个SYN的另一端执行被动打开（passive open）。

在socket编程中，客户端执行connect()时，将触发三次握手。

Q：为什么要进行3次握手，不是2次或更多？

A：假设采用2次握手。如客户端发出连接请求，但因连接请求报文丢失而未收到确认，于是客户端再重传一次连接请求。后来收到了确认，建立了连接。数据传输完毕后，就释放了连接，客户端共发出了两个连接请求报文段，其中第一个丢失，第二个到达了服务端，但是第一个丢失的报文段只是在某些网络结点长时间滞留了，延误到连接释放以后的某个时间才到达服务端，此时服务端误认为客户端又发出一次新的连接请求，于是就向客户端发出确认报文段，同意建立连接，不采用三次握手，只要服务端发出确认，就建立新的连接了，此时客户端忽略服务端发来的确认，也不发送数据，则服务端一致等待客户端发送数据，浪费资源。

四次挥手

TCP 的连接的拆除需要发送四个包，因此称为四次挥手(Four-way handshake)，客户端或服务器均可主动发起挥手动作。

刚开始双方都处于 ESTABLISHED 状态，假如是客户端先发起关闭请求。四次挥手的过程如下：

第一次挥手：客户端发送一个 FIN 报文，报文中会指定一个序列号。此时客户端处于 FIN_WAIT1 状态。
- 即发出连接释放报文段（FIN=1，序号seq=u），并停止再发送数据，主动关闭TCP连接，进入FIN_WAIT1（终止等待1）状态，等待服务端的确认。
第二次挥手：服务端收到 FIN 之后，会发送 ACK 报文，且把客户端的序列号值 +1 作为 ACK 报文的序列号值，表明已经收到客户端的报文了，此时服务端处于 CLOSE_WAIT 状态。
- 即服务端收到连接释放报文段后即发出确认报文段（ACK=1，确认号ack=u+1，序号seq=v），服务端进入CLOSE_WAIT（关闭等待）状态，此时的TCP处于半关闭状态，客户端到服务端的连接释放。客户端收到服务端的确认后，进入FIN_WAIT2（终止等待2）状态，等待服务端发出的连接释放报文段。
第三次挥手：如果服务端也想断开连接了，和客户端的第一次挥手一样，发给 FIN 报文，且指定一个序列号。此时服务端处于 LAST_ACK 的状态。
- 即服务端没有要向客户端发出的数据，服务端发出连接释放报文段（FIN=1，ACK=1，序号seq=w，确认号ack=u+1），服务端进入LAST_ACK（最后确认）状态，等待客户端的确认。
第四次挥手：客户端收到 FIN 之后，一样发送一个 ACK 报文作为应答，且把服务端的序列号值 +1 作为自己 ACK 报文的序列号值，此时客户端处于 TIME_WAIT 状态。需要过一阵子以确保服务端收到自己的 ACK 报文之后才会进入 CLOSED 状态，服务端收到 ACK 报文之后，就处于关闭连接了，处于 CLOSED 状态。
- 即客户端收到服务端的连接释放报文段后，对此发出确认报文段（ACK=1，seq=u+1，ack=w+1），客户端进入TIME_WAIT（时间等待）状态。此时TCP未释放掉，需要经过时间等待计时器设置的时间2MSL后，客户端才进入CLOSED状态。

收到一个FIN只意味着在这一方向上没有数据流动。客户端执行主动关闭并进入TIME_WAIT是正常的，服务端通常执行被动关闭，不会进入TIME_WAIT状态。

在socket编程中，任何一方执行close()操作即可产生挥手操作。

Q: 挥手为什么需要四次？

A：因为当服务端收到客户端的SYN连接请求报文后，可以直接发送SYN+ACK报文。其中ACK报文是用来应答的，SYN报文是用来同步的。但是关闭连接时，当服务端收到FIN报文时，很可能并不会立即关闭SOCKET，所以只能先回复一个ACK报文，告诉客户端，“你发的FIN报文我收到了”。只有等到我服务端所有的报文都发送完了，我才能发送FIN报文，因此不能一起发送（服务器的两次发送不能合并）。故需要四次挥手。

Q：释放连接时，等待2MSL的意义?

A：MSL是Maximum Segment Lifetime的英文缩写，可译为“最长报文段寿命”，它是任何报文在网络上存在的最长时间，超过这个时间报文将被丢弃。

保证客户端发送的最后一个ACK报文段能够到达服务端。

因为这个ACK有可能丢失，从而导致处在LAST-ACK状态的服务器收不到对FIN-ACK的确认报文。服务器会超时重传这个FIN-ACK，接着客户端再重传一次确认，重新启动时间等待计时器。最后客户端和服务器都能正常的关闭。假设客户端不等待2MSL，而是在发送完ACK之后直接释放关闭，一但这个ACK丢失的话，服务器就无法正常的进入关闭连接状态。

防止“已失效的连接请求报文段”出现在本连接中。

客户端在发送完最后一个ACK报文段后，再经过2MSL，就可以使本连接持续的时间内所产生的所有报文段都从网络中消失，使下一个新的连接中不会出现这种旧的连接请求报文段。

进一步解释：

主动断开的一侧为A，被动断开的一侧为B。

第一个消息：A发FIN

第二个消息：B回复ACK

第三个消息：B发出FIN

此时此刻：B单方面认为自己与A达成了共识，即双方都同意关闭连接。

此时，B能释放这个TCP连接占用的内存资源吗？不能，B一定要确保A收到自己的ACK、FIN。

所以B需要静静地等待A的第四个消息的到来：

第四个消息：A发出ACK，用于确认收到B的FIN

当B接收到此消息，即认为双方达成了同步：双方都知道连接可以释放了，此时B可以安全地释放此TCP连接所占用的内存资源、端口号。

所以被动关闭的B无需任何wait time，直接释放资源。

但，A并不知道B是否接到自己的ACK，A是这么想的：

1）如果B没有收到自己的ACK，会超时重传FIN

那么A再次接到重传的FIN，会再次发送ACK，重新计时

2）如果B收到自己的ACK，也不会再发任何消息，包括ACK

无论是1还是2，A都需要等待，要取这两种情况等待时间的最大值，以应对最坏的情况发生，这个最坏情况是：

ACK从A到B最多经过1MSL，超过这个时间B会重发FIN
B重发的FIN最多经过1MSL到达A

去向ACK消息最大存活时间（MSL) + 来向FIN消息的最大存活时间(MSL)。

这恰恰就是2MSL( Maximum Segment Life)。

等待2MSL时间，A就可以放心地释放TCP占用的资源、端口号，此时可以使用该端口号连接任何服务器。

TCP的四种计时器

重传计时器(Retransmission Timer)

目的：为了控制丢失的报文段或者丢弃的报文段。这段时间为对报文段的等待确认时间。
创建时间：在TCP发送报文段时，会创建对次特定报文段的重传计时器。
可能发生的两种情况：在截止时间（通常为60秒）到之前，已经收到了对此特定报文段的确认，则撤销计时器；在截止时间到了，但为收到对此特定报文段的确认，则重传报文段，并且将计时器复位。
重传时间：2*RTT（Round Trip Time，为往返时间）

坚持计时器(Persistent Timer)

目的：主要解决零窗口大小通知可能导致的死锁问题
死锁问题的产生：当接收端的窗口大小为0时，接收端向发送端发送一个零窗口报文段，发送端即停止向对端发送数据。此后，如果接收端缓存区有空间则会重新给发送端发送一个窗口大小，即窗口更新。但接收端发送的这个确认报文段有可能会丢失，而此时接收端不知道已经丢失并认为自己已经发送成功，则一直处于等待数据的状态；而发送端由于没有收到该确认报文段，就会一直等待对方发来新的窗口大小，这样一来，双方都处在等待对方的状态，这样就形成了一种死锁问题。如果没有应对措施，这种局面是不会被打破的。为了解决这种问题，TCP为每一个连接设置了坚持计时器。
工作原理：当发送端TCP收到接收端发来的零窗口通知时，就会启动坚持计时器。当计时器的期限到达时，发送端就会主动发送一个特殊的报文段告诉对方确认已经丢失，必须重新发送。【这个特殊的报文段就称为探测报文段，探测报文段只有1个字节的大小，里边只有一个序号，该序号不需要被确认，甚至在计算其他部分数据的确认时该序号会被忽略。】
截止期的设置：设置为重传时间的值。但如果没有收到接收端的响应，则会发送另一个探测报文段，并将计时器的值加倍并复位，直到大于门限值（一般为60秒）。在此之后，发送端会每隔60秒发送一个探测报文段，直到窗口重新打开。

保活计时器(Keeplive Timer)

目的：主要是为了防止两个TCP连接出现长时间的空闲。当客户端与服务器端建立TCP连接后，很长时间内客户端都没有向服务器端发送数据，此时很有可能是客户端出现故障，而服务器端会一直处于等待状态。保活计时器就是解决这种问题而生的。
工作原理：每当服务器端收到客户端的数据时，都将保活计时器重新设置（通常设置为2小时）。过了2小时后，服务器端如果没有收到客户端的数据，会发送探测报文段给客户端，并且每隔75秒发送一个，当连续发送10次以后，仍没有收到对端的来信，则服务器端认为客户端出现故障，并会终止连接。

时间等待计时器(Time_Wait Timer)

时间等待计时器是在连接终止期间使用的。
当TCP关闭连接时并不是立即关闭的，在等待期间，连接还处于过渡状态。这样就可以使重复的FIN报文段在到达终点之后被丢弃。
时间设置：一般为报文段寿命期望值的2倍。
原文链接：https://blog.csdn.net/qq_33951180/java/article/details/60468267

游戏服务器协议选择

那么到底是用UDP还是TCP呢？

如果是由客户端间歇性的发起无状态的查询，并且偶尔发生延迟是可以容忍，那么使用HTTP/HTTPS吧。
如果客户端和服务器都可以独立发包，但是偶尔发生延迟可以容忍（比如：在线的纸牌游戏，许多MMO类的游戏），那么使用TCP长连接吧。
如果客户端和服务器都可以独立发包，而且无法忍受延迟（比如：大多数的多人动作类游戏，一些MMO类游戏），那么使用UDP吧。

这些也应该考虑在内：你的MMO客户端也许首先使用HTTP去获取上一次的更新内容，然后使用UDP跟游戏服务器进行连接。

永远不要害怕去使用最佳的工具来解决问题。
链接：https://www.jianshu.com/p/08af0f7d335b

王者荣耀

4. 网络层

4.1 网络层服务

1. 转发

forwarding：将分组从路由器的输入端口转移到合适的输出端口

转发表确定在本路由器如何转发分组

2. 路由

routing：确定分组从源到目的经过的路径

路由算法（协议）确定通过网络的端到端路径

路由器结构

输入输出端口

交换机构内，基于目的的转发，使用最长前缀匹配原则

输出端口侧，当数据包从交换机构中以高于传输速率的速度到达时需要缓冲，可按照一定的调度策略进行分发

分组调度策略

先来先服务
优先权排队
循环和加权公平排队

3. 连接建立

某些网络的功能

注意：网络层连接是两个主机之间（路径上的路由器等网络设备参与其中）

传输层连接：两个应用进程之间（对中间网络设备透明）

4. 网络层服务模型

无连接服务（connection-less service）：数据报网络
连接服务（connection service）：虚电路网络

4.2 虚电路网络

ATM网络

虚电路（VIrtual circuits）：一条从源主机到目的主机，类似于电路的路径

每个分组的传输利用链路的全部带宽
每个分组携带虚电路标识（VCID），沿路每段链路一个编号
虚电路经过的每个网络设备维护每条经过它的虚电路的连接状态
简化边缘、复杂网络

虚电路信令协议（signaling protocols）

建立和拆除电路

4.3 数据报网络

Internet网络

网络层不连接
每个分组携带目的地址
数据报转发表（按地址范围划分）
- 最长前缀匹配优先
简化网络、复杂边缘

4.4 IPv4协议

1. IP数据报格式

首部长度以4字节为单位，即一位代表一行
首部校验和：只对IP首部进行校验
总长度字段（首部+数据），数据最大长度$2^{16} -20=65515B$
TTL(Time To Live):IP分组在网络中可以通过的路由器数（跳数），每转发一次减一，为零丢弃分组
协议：指示IP分组封装的是哪个协议的数据包，实现复用/分用

2. IP分片

最大传输单元（MTU）

不同链路的MTU不同

分片（fregmented）

重组（reassembled）

标识字段：IP协议利用一个计数器，每产生一个IP分组计数器加1，作为IP分组的标识（结合源目的地址唯一标识）
标志位：3位： | 保留 | DF（Dont Fragment）| MF（More Fragment）|
- DF=1：禁止分片
- DF=0：允许分片
- MF=1：非最后一片，有更多分片
- MF=0：最后一片（或未分片）
片偏移：13位，以8字节为单位：一个IP分组分片封装原IP分组数据的相对偏移量
- 区分最后一片还是未分片

分片过程：

3. IP编址(addressing)

点分十进制IP地址

网络号（NetID）- 高位比特
主机号（HostID）- 低位比特

相同网络号构成IP子网（Subnets）

不跨越路由器

有类划分

IP地址根据网络号和主机号来分，分为A、B、C三类及特殊地址D、E。全0和全1的都保留不用。

A类：(1.0.0.0-126.0.0.0)（默认子网掩码：255.0.0.0或 0xFF000000）第一个字节为网络号，后三个字节为主机号。该类IP地址的最前面为“0”，所以地址的网络号取值于1~126之间。一般用于大型网络。

B类：(128.0.0.0-191.255.0.0)（默认子网掩码：255.255.0.0或0xFFFF0000）前两个字节为网络号，后两个字节为主机号。该类IP地址的最前面为“10”，所以地址的网络号取值于128~191之间。一般用于中等规模网络。

C类：(192.0.0.0-223.255.255.0)（子网掩码：255.255.255.0或 0xFFFFFF00）前三个字节为网络号，最后一个字节为主机号。该类IP地址的最前面为“110”，所以地址的网络号取值于192~223之间。一般用于小型网络。

D类：是多播地址。该类IP地址的最前面为“1110”，所以地址的网络号取值于224~239之间。一般用于多路广播用户。

E类：是保留地址。该类IP地址的最前面为“1111”，所以地址的网络号取值于240~255之间。

在IP地址3种主要类型里，各保留了3个区域作为私有地址，其地址范围如下：
A类地址：10.0.0.0～10.255.255.255
B类地址：172.16.0.0～172.31.255.255
C类地址：192.168.0.0～192.168.255.255

私有地址：不向特定的用户分配，被IANA（The Internet Assigned Numbers Authority，互联网数字分配机构）作为私有地址保留。这些地址可以在任何组织或企业内部使用，和其他Internet地址的区别就是，仅能在内部使用，不能作为全球路由地址。这就是说，出了组织的管理范围这些地址就不再有意义，无论是作为源地址，还是目的地址。对于一个封闭的组织，如果其网络不连接到Internet，就可以使用这些地址而不用向IANA提出申请，而在内部的路由管理和报文传递方式与其他网络没有差异。

回送地址：127.0.0.1。也是本机地址，等效于localhost或本机IP。一般用于测试使用。例如：ping 127.0.0.1来测试本机TCP/IP是否正常。

子网划分：

网络号（NetID）- 高位比特
子网号（SubID）- 原网络主机号部分比特
主机号（HostID）- 低位比特

子网掩码

形如IP地址
NetID、SubID位全取1
HostID位全取0
A类网络缺省子网掩码：255.0.0.0
B类网络缺省子网掩码：255.255.0.0
C类网络缺省子网掩码：255.255.255.0 仅能容纳254个主机
将IP分组的目的IP地址与子网掩码按位与运算，提取子网地址

4. CIDR

无类别域间路由（Classless InterDomain Routing）

消除传统的A、B、C类地址界限
无类地址格式：a.b.c.d/x, 其中x为前缀长度
提升IPv4地址空间分配效率

5. 路由聚合

route aggregation

路由聚集的目的

简化路由转发表的规则，提升路由寻址效率

如何进行路由聚集

取消有类地址划分，NetID+SubID不定长度
需要聚合的子网地址按位取相同的前缀作为新的子网地址（超网）
转发表合并这些子网的转发规则为新的子网规则，同时保证为非合并前子网地址但满足条件的地址增加更长的前缀匹配规则

什么情况下可以路由聚集

当多个子网均通过其中某个子网地址来转发时

总结：

划分子网的意义

提升IP地址的利用效率

按规则分配IP地址，提升IP地址的辨识度，便于寻址，IP地址形成自上而下层次鲜明的结构

对不同地区不同类型的网络设备加以区分

如何划分子网

IP地址逻辑上分为NetID+SubID+HostID，NetID+SubID作为网络地址，HostID作为主机号

按有类地址的NetID，SubID从HostID的高bit进行借位(借n位可划分2^n个等长的子网)，组合成网络地址

通过子网掩码声明网络地址的bit宽度

定长子网划分

划分后的几个子网，子网掩码相同

变长子网划分

根据实际情况，选择不同长度的网络地址，子网掩码不一定相同

如何描述子网

子网网关描述子网的首地址

子网掩码描述子网的大小

4.5 DHCP协议

动态主机配置协议-DHCP：Dynamic Host Configuration Protocol

特点：

从服务器动态获取：
- IP地址
- 子网掩码
- 默认网关
- DNS服务器名称与IP地址
即插即用
允许地址重用
支持在用地址续租
支持移动用户加入网络

工作过程

DHCP协议在应用层实现
- 请求报文封装到UDP数据报中
- IP广播
- 链路层广播
DHCP服务器内建于路由器中

4.6 NAT

Network Address Translation 网络地址转换
我们利用端口号的唯一性实现了公网ip转换为私网ip的这一步。PAT（NAT重载）能够使用传输层端口号来标识主机，因此，从理论上说，最多可让大约65000台主机共用一个公有IP地址
NAT 路由器必须:

输出数据报: 将每个输出数据报的 (源 IP 地址, 端口号) 替换为 (NAT IP 地址, 新端口号)

远程客户端/服务器使用(NAT IP地址, 新端口号)作为目标地址进行响应
记录 (在 NAT 转换表中) 每一 (源 IP 地址, 端口号) 到 (NAT IP 地址, 新端口号) 转换配对
输入数据报: 将每个输入数据报目标字段中的(NAT IP 地址, 新端口号) 替换为存储在NAT 转换表中相应的 (源 IP 地址, 端口号)

Q: 为什么需要？

A:

只需从ISP申请一个IP地址，有地址耗尽问题

本地网络设备IP地址的变更，无需通告外界网络

变更ISP时，无需修改内部网络设备IP地址

内部网络设备对外界网络不可见，即不可直接寻址

引发争议：

路由器应该只处理第3层功能

违背端到端通信原则，应用开发人眼要考虑到NAT的存在，例如p2p应用

地址短缺问题应该由IPv6来解决

NAT在实现上将多个内部主机发出的连接复用到一个IP上，这就使依赖IP进行主机跟踪的机制都失效了。

NAT穿透：如果客户端想要连接到NAT后的服务器？

静态配置NAT（IP地址是一对一的，是一直不变的）
使用UPnP（Universal Plug and Play）互联网网关协议（IGD-Internet Gateway Device）自动配置
中继

4.7 ICMP协议

互联网控制报文协议-ICMP（Internet Control Message Protocol）

两类ICMP报文：

差错报告报文
- 目的不可达
- 源抑制（Source Quench）
- 超时/超期，TTL=0
- 参数问题
- 重定向（Redirect）
网络探询报文
- 回声Echo请求/应答报文Reply
- 时间戳请求与应答报文

报文格式

差错报告报文数据封装

4.8 IPv6协议

动机：

32位地址空间很快将被分配完

数据报格式：

定长40字节首部
不允许数据包分片
无校验和（加快路由器的处理，因为TTL的改变而每跳需重新计算）

4.9 路由算法

典型的路由选择方式有两种:静态路由和动态路由。

静态路由是在路由器中设置的固定的路由表。除非网络管理员干预，否则静态路由不会发生变化。静态路由不能对网络的改变作出反映.

动态路由是网络中的路由器之间相互通信，传递路由信息，利用收到的路由信息更新路由器表的过程。它能实时地适应网络结构的变化。如果路由更新信息表明发生了网络变化，路由选择软件就会重新计算路由，并发出新的路由更新信息。这些信息通过各个网络，引起各路由器重新启动其路由算法，并更新各自的路由表以动态地反映网络拓扑变化。动态路由适用于网络规模大、网络拓扑复杂的网络。当然，各种动态路由协议会不同程度地占用网络带宽和CPU资源。

静态路由和动态路由有各自的特点和适用范围，因此在网络中动态路由通常作为静态路由的补充。当一个分组在路由器中进行寻径时，路由器首先查找静态路由，如果查到则根据相应的静态路由转发分组;否则再查找动态路由。

根据是否在一个自治域内部使用，动态路由协议分为内部网关协议(IGP)和外部网关协议(EGP)。这里的自治域指一个具有统一管理机构、统一路由策略的网络。自治域内部采用的路由选择协议称为内部网关协议，常用的有RIP、OSPF;外部网关协议主要用于多个自治域之间的路由选择，常用的是BGP和BGP-

链路状态(Link State)算法：

Dijkstra算法

可能有震荡（oscillations）

Initailization:
N\' = {u}
for all nodes v:
	if v adjacent to u
		then D(v)=c(u,v)
	else D(v)=INF

Loop:
//可以使用堆来进行加速，在对数时间中找到最小值
find w not in N\' such that D(w) is a minimum 
add w to N\'
update D(v) for all v adjacent to w and not in N\':
	//此时更新父节点可以构建最短路径树
	D(v)=min(D(v),D(w)+c(w,v))
until all nodes in N\'

距离向量（Distance Vector）算法

Bellman-Ford方程动态规划

当节点x发现他的直接相连的链路开销变化或从某个邻居收到一个距离向量的更新时，他就更新其距离向量估计值

结点获得最短路径的下一跳，该信息用于转发表中
好消息传播快
坏消息传播慢
- 可能出现无穷计数问题（count to infinity）：路由选择环路（routing loop），y即为了到达x, 通过z路由，z又通过y路由到达x（因为此时距离最短）
- 使用毒性逆转（poisoned reverse）/反向下毒：如果一个节点到达目的的最小费用路径是通过某个邻居，则通告给该邻居到达该目的的距离为无穷大，直到路径不通过该邻居
  
  注意：涉及3个或更多节点，而不是两个直接相连的邻居节点的环路将无法用毒性逆转技术检测到
- 定义最大度量

4.10 Internet路由

AS（Autonomous system）：自治系统，指在一个（有时是多个）组织管辖下的所有IP网络和路由器的全体，它们对互联网执行共同的路由策略。也就是说，对于互联网来说，一个AS是一个独立的整体网络。而BGP实现的网络自治也是指各个AS自治。每个AS有自己唯一的编号。

在相同AS中的路由器都运行相同的路由选择算法并且有彼此的信息。在一个自治系统内运行的路由选择算法叫做自治系统内部路由选择协议

IGP（Interior Gateway Protocol）：内部网关协议，在一个AS内部所使用的一种路由协议。一个AS内部也可以有多个路由器管理多个网络。各个路由器之间需要路由信息以知道子网络的可达信息。IGP就是用来管理这些路由。代表的实现有RIP（Routing Information Protocol）、OSPF（Open Shortest Path First）、IGRP(内部网关路由协议)。

EGP（Exterior Gateway Protocol）：外部网关协议，在多个AS之间使用的一种路由协议，现在已经淘汰，被BGP取而代之。

1. RIP协议

路由信息协议（Routing Information Protocol）

2. OSPF

Open Shortest Path First

安全
采用链路状态算法-Dijkstra
允许使用多条相同费用的路径（RIP只能选一条）
对于每条链路，可以针对不同的TOS（Terms of service）设置多个不同的费用度量
集成单播路由与多播路由

OSPF比RIP强大的地方是，OSPF对整网的拓扑结构了如指掌，一旦某一条路径断了，可以及时选择备份链路，对通信的影响小。

RIP是基于谣言，对整网的拓扑结构没有概念，只知道有几个邻居，至于更远的邻居是什么样子，对不起，不知道！

IS-IS（intermediate system to intermediate system）与OSPF近乎相同 [IS-IS为第二层协议，OSPF为第三层协议]

3.BGP协议

Border Gateway Protocol：事实上的域间路由协议

在BGP中，分组并不是路由到一个特定的目的地址，相反是路由到CIDR化的前缀，其中每一个前缀表示一个子网或子网的集合，一台路由器的转发表将具有形式为（x, I）的表项，其中x是一个前缀（例如138.16.68/22）， I是该路由器的接口之一的接口号

eBGP：从邻居AS获取子网可达性信息
iBGP：将可达性信息传播给所有AS内部路由器

每条BGP路由包含3个组件：NEXT-HOP；ASPATH；目的前缀

热土豆算法：对于路由器，尽可能快的将分组送出其AS（更明确地说，用可能的最低开销），而不担心其AS外部到目的地的余下部分的开销，是一种自私的算法

路由选择策略（由上至下执行）：

路由被指定一个本地偏好值作为其属性之一
从余下路由中选择有最短AS-PATH的路由
从余下路由中用热土豆路由选择
最后使用BGP标识符选择

ISP遵循的经验法则：任何穿越某ISP主干网的流量必须是其源或目的（或两者）位于该ISP的某个客户网络中

4.11 SDN控制平面

software define network

远程控制器计算和分发转发表以供每台路由器使用，因为计算转发表并与路由器交互的控制器是用软件实现的，故网络是“软件定义”的

强化控制平面：可靠、可信、性能可扩展、安全的分布式系统
- 故障鲁棒性：控制平面的可靠分布系统的强壮理论发挥的作用

4.12 网络管理与SNMP

SNMP（Simple Network Management Protocol）

PDU（Protocol Data Unit）

5. 数据链路层

链路层的猪蹄部分是在网络适配器Network adapter中实现的，也被称为网络接口卡（Network Interface Card，NIC）。位于网络适配器核心的是链路层控制器，该控制器通常是一个实现了许多链路层服务（成帧、链路接入、差错检测等）

概述：

主机和路由器：结点（nodes）
连接相邻结点的通信信道：链路（links）
数据分组：帧（frame）

提供服务：

成帧
链路接入
可靠交付
差错检测和纠正

5.1 差错检测和纠正比特

Error-Detection and- Correction，EDC

汉明距离：两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数

检错码与纠错码：

1. 奇偶校验码

parity check

采用何种校验是事先规定好的。通常专门设置一个奇偶校验位，用它使这组代码中“1”的个数为奇数或偶数。若用奇校验，则当接收端收到这组代码时，校验“1”的个数是否为奇数，从而确定传输代码的正确性；偶校验则检测是否为偶数。

1比特校验位
- 检测奇数位差错
二维奇偶校验
- 检测奇数位差错、部分偶数位差错
- 纠正同一行/列的奇数位数

2. Internet校验和

计算checksum

3. 循环冗余校验码

Cyclic Redundancy Check ，CRC

有限代数理论（Galois域）

考虑d比特的数据D，发送节点要将它发送给接收节点。发送方和接受方首先必须协商一个r+1比特模式，称为生成多项式G，要求G的最高有效位的比特为1. 对于一个给定的数据段D，发送发要选择r个附加比特R，并将它们附加到D上，使得得到的d+r比特模式用模2算数恰好能被G整除。接受方用G去除收到的d+r比特。

【说明】“模2除法”与“算术除法”类似，但它既不向上位借位，也不比较除数和被除数的相同位数值的大小，只要以相同位数进行相除即可。模2加法运算为：1+1=0，0+1=1，0+0=0，无进位，也无借位；模2减法运算为：1-1=0，0-1=1，1-0=1，0-0=0，也无进位，无借位。相当于二进制中的逻辑异或运算。也就是比较后，两者对应位相同则结果为“0”，不同则结果为“1”。如100101除以1110，结果得到商为11，余数为1，如11×11=101

编码简单、性能优良

5.2 多路访问控制（MAC）协议

Multiple Access Control Protocol

采用分布式算法决定结点如何共享信道，即决策结点何时可以传输数据

MAC协议分类：

信道划分
- 将信道划分为小的“片段”
- 将片段分配给节点独占使用
随机接入
- 不分割信道，允许冲突/碰撞
- 冲突后恢复
轮流
- 节点轮流发送，但发送多的节点可以轮流发送更长的时间

1. 信道划分（channel partitioning）MAC协议

多路复用技术
TDMA：time division multiple access 时分多址
FDMA：frequency division multiple access 频分复用
CDMA：code division multiple access 码分多址
WDMA

2. 随机访问（random access）MAC协议

信道不划分，允许冲突
采用冲突、恢复机制
- 有碰撞时，涉及碰撞的每个节点反复地重发它的帧，直到该帧无障碍通过

时隙（sloted）ALOHA

时钟同步
碰撞时以概率p选择是否重传
效率极限为37%

ALOHA协议

无时钟同步，纯分散协议
比时隙ALOHA协议更差（为其一半），更简单

CSMA 载波监听多路访问协议（carrier sense multiple access）

发送帧之前，监听信道
由于信号传播延迟，可能仍有冲突
继续发送冲突帧，浪费信道资源

CSMA/CD（with Collision Detection）协议

短时间内可以检测到冲突
冲突后传输中止，减少信道浪费
- 中止后进入二进（指数）退避
$L_{min}/R=2d_{max}/V $ 网络带宽R 数据帧长度L 信号传播速度V 两个站点之间的距离d
性能远由于ALOHA协议
以太网

3. 轮转（taking turns）MAC协议

结点轮流使用信道
蓝牙

轮询（polling）

主结点轮流邀请从属结点发送数据

令牌传递（token passing）

控制令牌一次从一个结点传递到下一个结点
令牌-特殊帧

5.3 ARP协议

Address Resolution Protocol

1. MAC地址

或称LAN地址，物理地址，以太网地址

48位MAC地址，固化在网卡的ROM中，有时也可以软件设置
e.g:1A-2B-3C-34-AD-00
由IEEE统一管理与分配

2. 地址解析协议

ARP表：LAN中的每个IP结点（主机、路由器）维护一个表

一台路由器对它的每个接口都有一个IP地址。对路由器的每个接口，也有一个ARP模块和一个适配器。

查询ARP报文是在广播帧中发送的，而响应ARP报文在一个标准帧中发送

存储某些LAN结点的IP/MAC地址映射关系：<IP地址；MAC地址；TTL>

5.4 以太网

物理拓扑

总线（bus）
- 所有结点在同一冲突域（collision domain）
星形（star）

CSMA/CD算法

检测到冲突后进入二进制指数退避

连续冲突次数越多，平均等待时间越长

以太网帧结构

交换机

自学习、泛洪构建转发表，依据MAC地址

过滤：决定转发一个帧还是丢弃该帧

转发：决定一个帧被导向哪个接口

特点：

消除碰撞
异质的链路，不同链路有不同速率且运行在不同媒体上
管理

交换机与路由器的区别：

交换机是二层的分组交换机，即插即用，有较高的分组过滤和转发速率

路由器是三层的分组交换机，使用路由算法和IP地址注册转发表

VLANs

virtual local area network

流量隔离（traffic isolation）
动态成员

在VLAN中转发：通过路由（就像在独立的交换机之间）

干线端口- 扩展以太网帧格式 802.1Q

多协议标签交换

Multiprotocol Label Switching，MPLS

固定长度标签

本文链接：https://www.cnblogs.com/unnling/p/14470833.html

计算机网络复习笔记

目录

1 计算机网络概述

1.1 网络概念

1.2 数据交换方式

1.3 网络分类

1.4 网络的性能指标

1.5 网络体系结构

1. 概念

2. OSI参考模型

1 物理层

2 数据链路层

3 网络层

4 传输层

5 会话层

6 表示层

7 应用层

通信过程

数据封装

网络排错

3. TCP/IP参考模型

4. 5层参考模型

5层结构

数据封装

2. 应用层

2.1 体系结构

1. 客户机/服务器结构（Client/Server）

2. P2P结构（peer-to-peer）

3. 混合结构

2.2 进程间通信

1. Socket

2. 寻址

3. 应用层协议

2.3 Web应用

1. HTTP协议

2. Cookie

3. Web缓存/代理服务器技术

2.4 Email应用

1. 邮件客户端 （user agent）

2. 邮件服务器 （mail server）

3. SMTP协议（Simple Mail Transfer Protocol）

4. 邮件访问协议

2.5 DNS应用

1.DNS服务

2.分布式层次式数据库

4. DNS记录和消息格式

1.DNS记录

2.DNS协议与消息

2.6 P2P应用

1. BitTorrent

2. 索引设计

2.7 Socket编程

1. Socket API

2. API调用流程

2.8 CDN

3. 传输层

3.1 传输层服务

1. 多路复用/分用

2.可靠数据传输机制

RDT版本

流水线协议

滑动窗口协议

TCP可靠数据传输

3. 流量控制机制

4. 拥塞控制机制

3.2 Internet传输层协议

1. UDP

特点：

应用：

可靠性保证

报文格式：

2. TCP

特点：

报文格式：

连接管理

三次握手

四次挥手

4. 网络层

4.1 网络层服务

1. 转发

1. 邮件客户端（user agent）

2. 邮件服务器（mail server）