计算机网络备忘

本文最后更新于 2023年3月3日下午

学习计算机网络时提炼的备忘，主要就是看 MOOC 和谢希仁的计算机网络（第7版）

计算机网络备忘

互联网概述

互联网：由数量极大的各种计算机网络互连起来而形成的网络。

两个重要特点：
1. 连通性(Connectivity) ——上网用户之间可以交换信息
2. 共享(Sharing)——资源共享
网络(计算机网络)：由若干节点(node)和连接这些节点的链路(link)组成【与网络相连的计算机称为主机】
互连网(internetwork)：通过路由器将网络互连，构成更大的计算机网络
互联网(Internet)：特指世界上最大的、覆盖全球的计算机网络
- 互联网服务提供者 ISP：任何机构和个人只要向某个 ISP 交纳规定的费用，就可从该 ISP 获取所需 IP 地址的使用权，并可通过该ISP 接入到互联网；ISP 根据层次可以分成：主干 ISP 、地区 ISP 、本地 ISP 。
互联网的标准化：所有互联网标准都以 RFC 的形式在互联网上发表。
- 三个阶段：互联网草案(还不是RFC文档)→建议标准(RFC文档)→互联网标准

互联网的组成

边缘部分

端系统：连接在互联网上的所有的主机。
端系统之间的通信方式
- 客户—服务器方式(C/S方式)
  - 客户(client) 和服务器(server) 都是指通信中所涉及的两个应用进程
  - 描述的是进程之间服务和被服务的关系
  - 客户(被用户调用后运行)是服务的请求方，服务器(一直不断地运行着，被动地等待)是服务的提供方
- 对等连接(P2P)peer-to-peer
  - 对等连接中的每一个主机既是客户又是服务器

核心部分

在网络核心部分起特殊作用的是路由器(router)
路由器是实现分组交换的关键构件，其任务是转发收到的分组，这是网络核心部分最重要的功能。
电路交换：每一部电话都直接连接到交换机上，而交换机使用交换的方法，让电话用户彼此之间可以很方便地通信。
- “交换”就是按照某种方式动态地分配传输线路的资源
- 电路交换必然是面向连接的
- 电路交换的三个阶段：建立连接→通信→释放连接
- 由于计算机数据具有突发性，这导致在传送计算机数据时，通信线路的利用率很低
分组交换：采用存储转发技术，步骤如下
1. 在发送端，先把较长的报文划分成较短的、固定长度的数据段。
2. 每一个数据段前面添加上首部构成分组(packet)
3. 分组交换网以“分组”作为数据传输单元，依次把各分组发送到接收端
4. 最后，在接收端把收到的数据恢复成为原来的报文
- 高效、灵活、迅速、可靠，但是会因为分组转发时需要排队而造成一定时延，首部也会造成一定的开销
- 类似的有：电报通信的报文交换
路由器
- 在路由器中的输入和输出端口之间没有直接连线
- 处理分组的过程
  - 把收到的分组先放入缓存（暂时存储）
  - 查找转发表，找出到某个目的地址应从哪个端口转发
  - 把分组送到适当的端口转发出去
- 路由器在转发分组时最高只用到网际层

互联网核心部分中的路由器之间一般都用高速链路相连接，而在网络边缘的主机接入到核心部分则通常以相对较低速率的链路相连接。

※：接入网 AN：是从某个用户端系统到互联网中的第一个路由器之间的一种网络，既不属于互联网的核心部分，也不属于互联网的边缘部分

计算机网络的性能指标：速率、带宽、吞吐率、时延、时延带宽积、往返时间RTT、利用率
计算机网络的非性能特征：费用、质量、标准化、可靠性、时延带宽积、可扩展性和可升级性、易于管理和维护

计算机网络的体系结构

开放系统互连参考模型 OSI/RM：一个试图使各种计算机在世界范围内互连成网的标准框架
※：法律上的国际标准 OSI 并没有得到市场的认可，非国际标准TCP/IP 却获得了最广泛的应用。
网络协议：为进行网络中的数据交换而建立的规则、标准或约定【文字描述和程序代码】
- 语法：数据与控制信息的结构或格式
- 语义：需要发出何种控制信息，完成何种动作以及做出何种响应
- 同步：事件实现顺序的详细说明

OSI的体系结构	TCP/IP的体系结构	五层协议的体系结构
应用层	应用层	应用层
表示层
会话层
运输层	运输层（TCP或UDP）	运输层
网络层	网络层IP	网络层
数据链路层	网络接口层	数据链路层
物理层	网络接口层	物理层

- 协议数据单元 PDU：对等层次之间传送的数据单位

“对等层”(peer layers)之间的通信：任何两个同样的层次把数据（即数据单元加上控制信息）通过水平虚线直接传递给对方

协议与服务

实体：表示任何可发送或接收信息的硬件或软件进程
协议：控制两个对等实体进行通信的规则的集合
- 在协议的控制下，两个对等实体间的通信使得本层能够向上一层提供服务
- 要实现本层协议，还需要使用服务原语使用下层所提供的服务
  
  ※：服务是”垂直的“，协议是”水平的“
服务访问点 SAP：同一系统相邻两层的实体进行交互的地方
服务数据单元 SDU：层与层之间交换的数据的单位【可以和PDU不一样，因为可以组合和划分】

物理层

物理层的基本概念

主要功能：提供透明比特流传输
- 尽可能地屏蔽掉不同传输媒体和通信手段的差异
- 只关心比特流的正确搬运，不关心内容
特性
1. 机械特性：接口所用接线器的形状、尺寸、引线数目和排列等
2. 电气特性：接口电缆的各条线上出现的电压范围
3. 功能特性：某条线上出现的某一电平的电压表示的意义
4. 过程（规程，procedure，即物理层的协议）特性：对于不同功能的各种可能事件的出现顺序

数据通信系统的模型

数据：运送消息的实体
信号：数据的电气或者电磁的表现
模拟信号：代表消息的参数的取值是连续的
数字信号：代表消息的参数的取值是离散的
码元：在使用时域的波形表示数字信号是，代表不同离散数值的基本波形

信道：一般表示向某一方向发送信息的媒体

单向通信（单工通信）：只能有一个方向的通信而没有反方向的交互
双向交替通信（半双工通信）：通信的双方都可以发送信息，但是不能同时发送
双向同时通信（全双工通信）：通信的双方可以同时发送和接收信息
基带信号：来自信源的信号
- 由于基带信号往往包含较多的低频成分，甚至直流成分，许多信道并不能传输这种低频分量或直流分量。因此必须对基带信号进行调制，一般可以分成两大类
  - 基带调制（编码）：基带信号→基带信号（仅变换波形）
  - 带通调制：使用载波，将信号频率提高，转换为模拟信号，得到带通信号
常用编码方式
- 不归零制：正电平代表1，负电平代表0
- 归零制：正脉冲代表1，负脉冲代表0
- 曼切斯特编码：位周期中心的向上跳变代表0，位周期中心的向下跳变代表1（反过来定义也可）
- 差分曼切斯特编码：在每一位的钟信处始终都有跳变。位开始边界有跳变代表0，没有跳变代表1

※：可以从图中看出

曼彻斯特编码和差分曼彻斯特编码产生的信号频率比不归零制高
不归零制不能从信号波形本身中提取信号时钟频率（这叫作没有自同步能力），而曼彻斯特编码和差分曼彻斯特编码具有自同步能力

基本的带通调制方法
- 调幅 AM：载波的振幅随基带数字信号而变化
- 调频 FM：载波的频率随基带数字信号而变化
- 调相 PM：载波的初始相位随基带数字信号而变化

※：技术上更为复杂的多元制的振幅相位混合调制方法可以提高码元，从而提高数据传输率，但是这在进行解调时出错率会增加

信道的极限容量的两个限制因素
- 信道能够通过的频率范围：【奈氏准则】在假定的理想条件下，为了避免码间串扰，码元的传输速率的上限值——在任何信道中，码元传输的速率是有上限的，否则就会出现码间串扰的问题，从而导致失真
- 信噪比：信噪比就是信号的平均功率和噪声的平均功率之比。常记为 S/N，并用分贝 (dB) 作为度量单位。即：信噪比(dB) = 10 log10(S/N) (dB)
  【香农公式】带宽受限且有高斯白噪声干扰的信道的极限、无差错的信息传输速率
  $C=Wlog_{2}(1+\frac{S}{N})(bit/s,bps)$
  其中： $W$ 位信道带宽（ $Hz$ ）; $S$ 为信道内所传信号的平均功率； $N$ 为信道内部的高斯噪声功率

※：对于频带宽度已确定的信道，如果信噪比不能再提高了，并且码元传输速率也达到了上限值，那么还可以用编码的方法让每一个码元携带更多比特的信息量提高信息的传输速率。

※ 采样定理（奈奎斯特定理）： $C=B*log_2n$ ，其中 $B$ 为波特率（码率，采样率，符号率，指每秒钟信号变化的次数）， $C$ 是比特率（位传输率、数据传输速率、数字带宽）， $n$ 为调制电平数或者线路的状态数，为 2 的整数倍，但是也有例外

物理层下面的传输媒体

传输媒体：也称为传输介质或传输媒介，它就是数据传输系统中在发送器和接收器之间的物理通路

引导型传输媒体：电磁波被导引沿着固体媒体（铜线或光纤）传播

双绞线：最常用的传输媒体
- 屏蔽双绞线 STP（Shielded Twisted Pair）：带金属屏蔽层
- 无屏蔽双绞线 UTP（Unshielded Twisted Pair）
- 标准：EIA/TIA-568、EIA/TIA-568A（5类线）
同轴电缆：具有很好的抗干扰特性性，被广泛用于传输较高速率的数据
- 50Ω：LAN/数字传输常用 70Ω：有线电视/模拟传输常用

光缆：光纤通信的传输媒体，传输带宽远远大于目前其他各种传输媒体的带宽
- 多模光纤：可以存在多条不同角度入射的光线在一条光纤中传输
- 单模光纤：光纤的直径减小到只有一个光的波长，光线一直向前传播，而不会产生多次反射

※：优点：通信容量非常大；传输损耗小，中继距离长；抗雷电和电磁干扰性能好；无串音干扰，保密性好；体积小，重量轻

非引导型传输媒体：自由空间

在自由空间，电磁波的传输常称为无线传输
短波通信：主要是靠电离层的反射，但短波信道的通信质量较差，传输速率低
微波在空间主要是直线传播
传统微波通信有两种方式：地面微博接力通信、卫星通信

信道复用技术

复用：允许用户使用一个共享信道进行通信，降低成本，提高利用率
- 频分复用 FDM (Frequency Division Multiplexing)：将整个带宽分为多份，用户在分配到一定的频带后，在通信过程中自始至终都占用这个频带。
  - 频分复用的所有用户在同样的时间占用不同的带宽资源
    （※：这里的“带宽”是频率带宽而不是数据的发送速率）

时分复用 TDM (Time Division Multiplexing)：是将时间划分为一段段等长的时分复用帧（TDM 帧）。每一个时分复用的用户在每一个 TDM 帧中占用固定序号的时隙。
- 每一个用户所占用的时隙是周期性出现的，所以 TDM 信号又叫做等时信号
- 时分复用的所有用户是在不同的时间占用同样的频带宽度
- 由于计算机数据的突发性质，用户对分配到的子信道的利用率一般是不高的
统计时分复用 STDM (Statistic TDM)：STDM 帧不是固定分配时隙，而是按需动态地分配时隙。因此统计时分复用可以提高线路的利用率。
波分复用 WDM(Wavelength Division Multiplexing)：使用一根光纤来同时传输多个光载波信号，即光的频分复用
码分复用 CDM (Code Division Multiplexing)：各用户使用经过特殊挑选的不同码型，因此彼此不会造成干扰
- 码片 (chip)：每一个比特时间划分为 m 个短的间隔
- 每个站被指派一个唯一的 m bit 码片序列
  eg：发送比特 1，则发送自己的 m bit 码片序列；如发送比特 0，则发送该码片序列的二进制反码
  这就实现了（直接序列）扩频 DSSS：假定S站要发送信息的数据率为 b bit/s。由于每一个比特要转换成 m 个比特的码片，因此 S 站实际上发送的数据率提高到 mb bit/s，同时 S 站所占用的频带宽度也提高到原来数值的 m 倍
  ※：还有一种跳频扩频 FHSS
  - 每个站的码片序列必须各不相同，而且必须相互正交
  - 任何一个码片向量和他自己规格化内积都是1，和该码片反码的向量的规格化内积是-1
  - 在实际系统中用的是伪随机码序列

一个原理的实例

设 $m=8$ ，每个向量为 $8bit$
假设在A站和B站同时向C站发送数据时：

A站发送数据1:码片向量 $\vec{S}$ 为 $(-1,+1,-1,-1,+1,+1,-1,-1)$

B站发送数据0:码片向量 $\vec{T}$ 为 $(+1,+1,-1,-1,+1,-1,+1,+1)$

二者在公共信道上会向量复合(两个向量相加)得到 $\overrightarrow{S+T}$ 的向量信息，主站收到这个信息后会让它所拥有的所有站的8位码片向量和 $\overrightarrow{S-T}$ 相乘

结合上述性质推导下列算式:

比如：码片向量 $\vec{S} :\vec{S} \bullet \overrightarrow{S+T}=\frac{1}{8}\left(\sum_{i=1}^{8} S_{i} S_{i}-\sum_{i=1}^{8} S_{i} T_{i}\right)=1$ ，则表示 $\vec{S}$ 对应的A站向C站发送了数据1

同理，向量 $\vec{-T}$ : $\vec{T} \bullet \overrightarrow{S+T}=\frac{1}{8}\left(\sum_{i=1}^{8} T_{i} S_{i}-\sum_{i=1}^{8} T_{i} T_{i}\right)=-1$ ，则表示 $\vec{T}$ 对应的B站向C站发送了数据0

当然对于其他的码片 $\vec{M}$ (代指是除了A站,B站以外的所有码片)，

$\vec{M} \bullet \overrightarrow{S-T}=\frac{1}{8}\left(\sum_{i=1}^{8} M_{i} S_{i}-\sum_{i=1}^{8} M_{i} T_{i}\right)=0-0=0$

这一切都是因为 $\vec{M}$ 和 $\vec{S}$ , $\vec{T}$ 相互正交。

数字传输系统

PTSN 公共交换电话网络

graph LR
A[呼叫方的语音] -->|本地回路| B[端局]
    B -->|干线| C[上级交换局]
    C -->  D[对方的端局]
    D -->E[被叫方]

PSTN 的主要构成
- 本地回路：模拟线路——连接端局和千家万户或业务部门
  - 传输模拟信号，需要调制解调器（数模转换，就是猫，56k）
  - 突破电话信号的4k限制——宽带服务
  - 突破物理特性的限制——光纤到户 FTTH
- 干线：数字光纤——连接交换局、端局
  - 使用了复用技术
    - SONET/SDH：同步数据传输的标准
  - 端局：含有编解码器codec，利用脉冲编码调制 PCM，用于数模转换，构成了现代 PTSN 的核心
- 交换局：语音拨接的场所
  - 电路交换：提前分配，容错能力弱，按序，按时间计费
  - 包交换：按需分配，容错能力强，乱序，按流量计费

宽带接入技术

非对称数字用户线 ADSL：用数字技术对现有的模拟电话用户线进行改造，使它能够承载宽带业务（低频用于电话，高频用于上网）
- 用户线（铜线）两端各安装一个 ADSL 调制解调器
- 上行和下行带宽做成不对称的
  - 上行指从用户到 ISP，而下行指从 ISP 到用户
- 采用自适应调制技术使用户线能够传送尽可能高的数据，但是不能保证固定的数据率

光纤同轴混合网（HFC网）

HFC：在目前覆盖面很广的有线电视网 CATV 的基础上开发的一种居民宽带接入网
- 将原 CATV 网中的同轴电缆主干部分改换为光纤，并使用模拟光纤技术
- 每个家庭要安装一个用户接口盒 UIB，提供三种连接

FTTx技术

光纤到……：FTTH、FTTB、FTTC

物理层设备

收发器 Transceiver，MAU
- 现在退化成网卡上一个部件
中继器 Reapter
- 再生信号：去噪、放大，这样可以延伸线缆
- 不能过滤流量
集线器 Hub：多端口的中继器
- 作为星型拓扑的中心
- 广播（泛洪）：从除了来的那个端口外的所有其他端口转发出去
冲突：信号的碰撞
- 冲突域：数据包产生和冲突的网络区域，即共享介质的区域
  - 冲突域越大，冲突的可能性越大，网络性能下降
  - 中继器、集线器扩大了冲突域

数据链路层

概述

数据链路层：保证数据传输的有效、可靠（差错检测和控制、流量控制）
PDU：帧=帧头+载荷+帧尾

※：物理层：位流 bits ；数据链路层：帧 frame

成帧

成帧：将原始的位流分散到离散的帧中
- 字符计数法
  - 发送方：在每个帧头部的第一个字段，标识该帧的长度，总共有多少字符数
  - 接收方：通过第一个字段就知道该帧有几个字符啊，在哪里结束帧
  - 特点：简单，容易实现；但是一旦出错无法恢复
字节填充的标志字节法
- 考虑到重新同步问题，每个帧采用了一个特殊的标记字节（flag）做帧界（帧的开始和结束）
- 在数据中的标记字节前面加上转义符，防止与帧界混淆
- 缺点：任意比特数的帧不适用，须是8位整数倍
比特填充的标记比特法
- 为了适用于任意比特位数的帧，使用比特填充法
- 传输效率更高：标记 flag 占用比特数少
物理层编码违例法
- 帧界：冗余信号

差错处理概述

不存在完美的信道，传输总会出错
单个错误、突发错误（集中在一个数据块内）
纠错（前向纠错错误）发现错误，从错误中恢复出正确的来。开销大，所以有线传输使用少。
检错：只能发现错误，不能从错误中恢复，但是可重传恢复。局域网中主要采用检错码。
码字：包含数据位和校验位的 n 位单元（模式）
海明距离：两个码字的海明距离等于两个码字之间不同位的数目——可以用异或来计算
- 全部码字的海明距离：全部码字中任意两个码字之间海明距离的最小值
- 海明距离的意义：如果海明距离为 d，则一个码字需要发生 d 个 1 位错误才能变成另外一个码字
- 海明距离与检错位数的关系：海明距离为 d+1 的编码能检测出 d 为差错
- 海明距离与纠错位数的关系：海明距离为 2d+1 的编码能检测出 d 为差错
- 海明距离增加，纠错能力越强，但是合法码字就减少了，传输效率会降低

纠 1 位错的海明码

纠 1 位错需要的冗余位 $r$ 跟数据位 $m$ 的关系： $(m+r+1)\leq 2^r$
海明纠错码
- 每一个码字从左往右编号，最左边是第一位
- 校验位：凡是编号为 2 的幂次的位。依据包括它自身在内的一些位的集合的奇偶值可以设置。
- 如何决定每个数据位的校验位：将某一数据为的编号展开成 2 的乘幂的和，那么每一项对应的位即为该数据为的校验位（接收方使用）。反过来，校验位的校验集合也包含这些数据位。
- 纠错方法：设置差错计数器 count ，然后逐个检查校验位，每错一个就count+=出错校验位的编号，最后 count 的值就是出错的位编号
- 用于纠正突发错误：数据按行排列成矩阵，然后按列发送。但是能够纠错的突发错误的个数小于等于发送矩阵的行数

检错码

奇偶检验

奇偶位取值等同于对数据位进行模 2 和运算

能够判断正确的概率是 50%

互联网校验和

校验和：按照 n 位码字进行模 2 加运算
校验位：发方追加到报文尾部
常见：16 位互联网校验和

循环冗余检错码 CRC

工作原理： $k$ 位的帧 = $k-1$ 次的多项式
对于发方：生成多项式 $G(x)$ 阶数为 $r$ ， $m$ 位帧的多项式 $m>r$ ， $M(x)>G(x)$

设 $X^rM(x)/G(x)=Q(x)+R(x)$ ，则 $(X^rM(x)-R(x))/G(x)=Q(x)$

发送被除数减去模 2 除法的余数 $X^rM(x)-R(x)$ ， $X^rM(x)$ 相当于在数据帧的低端加上 r 个 0

对于收方：把收到的码字去除生成多项式，如果除得结果为 0 ，则没有发生传输错误
生成多项式国际标准：CRC32等

基本数据链路层协议

假设
1. 物理层、数据链路层、网络层各自是独立的处理进程
2. 机器 A 希望向 B 发送的是一个可靠的、面向连接的长数据流
3. 假设机器不会崩溃
4. 从网络层拿到的是纯数据
几点说明
- 六个协议共同使用的数据类型、调用的函数过程定义在 protocol.h 中
- 与网络层、物理层之间的数据传送接口
  - 发送：from_network_layer、to_physical_layer
  - 接收：from_physical_layer、to_network_layer
- Wait_for_event 等待某个事件发生：frame_arrival、cksum_err、timeout
- Timer 计时器作用
  - 重传定时器：start_timer、stop_timer
  - 捎带确认定时器：start_ack_timer、stop_ack_timer
- 帧结构
  1
  2
  3
  4
  5
  6
  typedef struct{ frame_kind kind; seq_nr seq; # 序号 seq_nr ack; # 确认号 packet info; }frame;

协议1：无限制的单工协议

【乌托邦协议】

假设
数据单向传送
- 收发双方的网络层都处于就绪状态
- 处理时间可忽略不计
- 可用的缓存空间无穷大
- 假设 DLL 之间的信道永远不会损坏或者丢失帧

协议2：单工停—等协议

取消”接收方允许无限量接收“的假设，解决如何避免收方被涌入的数据淹没的问题
解决方法：收方回发一个哑帧，接收方收到哑帧，表明收方允许接受数据，此时再次发送下一帧数据
实际上是半双工协议（因为收方回发哑帧）

协议3：有噪声信道的单工协议

有噪声就会产生差错，有差错就可能会引起以下问题：
- 接收方检测到错误帧，如何通知发送方？如何恢复正确帧？
  - 对正确帧的确认
  - 定时器超期：重传
  - 重传定时器可防止死锁的产生
- 数据帧或确认帧再途中丢失将如何解决？
  - 定时器超期：重传
- 有可能收到重复帧，如何解决？
  - 给每个帧一个独一无二的序列号
  - 序号也拿来重组排序
主动确认重传：接收方无误，回发确认帧
- PAR/ARQ的基本工作机制
  - 发送方每发出一个帧，就启动一个重传定时器
    - 超时前，如果接收到收方的确认，拆除定时器
    - 超时未得到确认，重传，重置定时器
如何进一步提高数据传输效率？
- 全双工
- 捎带确认：将确认暂时延迟以便可以钩到一个外发的数据帧（s.ack）
  - 如无法”捎带“，当一个控制捎带确认的定时器超时后，单独发确认帧
- 批发数据：在等待的时间发送数据帧

协议4：W=1 的滑窗协议

两个窗口
- 发送窗口：对应着已经发送但还未被确认的帧的序号
- 接收窗口：对应着期望接受的帧的序号
窗口滑动的条件
- 接收方：收到帧后，首先核对是否为 frame_expected，如果是的，那么接受并 frame_expected+1
- 发送方：收到应答帧，核对响应帧号 next_frame_to_send，核对无误后，从网络层取出新的帧，并 next_frame_to_send+1
滑动窗口的基本概念
- 每个待发送帧被赋予一个序列号 seq，取值在 $[0,2^n-1]$ （n 位字段）
- 建立缓冲区
  - 发送窗口：缓存已发送，待确认的帧 W
  - 接受窗口：缓存期待接受的帧（序号）
协议 4 的滑动窗口的基本工作原理
- 窗口设置
  - 滑动窗口最大值：MAX_SEQ=1
  - 通信双方的初始值：seq=0、ack=1（期待接收 seq=0）
- 窗口滑动机制
  - A 首先发送数据帧（seq=0，ack=1，A0）
  - B 收到 A0，发送捎带确认帧（seq=0，ack=0，B0）
  - A收到对 A0 的确认，滑动窗口，发送帧（seq=1，ack=0，A1）
协议 4 的滑动窗口特点
- 序列号 seq 和确定值 ack 在 0，1交替
- 滑动窗口长度 W=1，收到确认后才移动窗口
- 保证按顺序将接收到的正确帧只一次上交网络层
协议 4 的信道利用率
- 由于协议 4 中忽略了：接收方处理到达帧的时间，事实上，发送方在来回时间 RTT 时处在 blocked 状态
- 如果信道传输速率是 b bps，每帧的大小是 k bits，来回时间是 R sec
  
  则信道的利用率是：Line Utilization Rate = $k/(k+bR)$
- 提高信道利用率的方法
  - 增加滑动窗口最大长度 W
    
    信道利用率 = $W*T_f/(T_f+R)=W*k/(k+bR)$
    
    Q：怎样找到一个合适的 W 值？
    
    A：信道上的容量：一帧从发送方传输到接收期间可容纳的帧数量
    
    带宽-延迟积：BD
    
    窗口值：W=2*BD+1
面临的问题：连续发个数据帧，其中有一帧出错，但是后续帧被成功发送
- 丢弃错帧及后续帧——协议 5
- 丢弃错帧，缓存后续正确帧——协议 6

协议 5：回退 n 帧的滑窗协议

工作原理
- 发送方
  - 正常发送：对帧编号，待确认帧缓存
  - 收到确认：释放确认帧所占缓存，滑动发送窗口
  - 差错帧超时时间到：回退到超时帧，顺序重传最后被确认帧以后的缓冲区中缓存的帧
  - 发送窗口： $W\leq MAX\_SEQ$
- 接收方
  - 收到每一个期望的正确帧：上交网络层、会送确认【累计确认】
  - 收到出错帧：丢弃，回发最后一个正确的帧的确认
  - 接收窗口： $W=1$

协议 6：选择性重传

工作原理
- 发送方
  - 正确发送：对帧标号，待确认帧缓存
  - 收到确认：释放确认帧所占缓存，滑动发送窗口
  - 差错帧超时时间到：重传缓存的最后被确认帧以后的那一帧
- 接收方
  - 正常接收：上交网络层，回信确认，滑动接收窗口
  - 收到非期望的正确帧：缓存，回送对接收最后正确帧的确认
  - 收到重传帧：将缓存帧排序上交，回送确认，话哦的那个接收窗口
否定确认 NAK：可以加快重传节奏
与协议 5 对比

	回退 n 帧	选择性重传
缓冲区	发送方	接收方
适用网络环境	出错率小	出错率大

协议 6 中，滑动窗口长度 W 的选择

接收窗口：W=（MAX_SEQ+1）/2

发送窗口通常小于接收窗口
3 个协议的窗口大小

	协议 4：滑动窗口	协议 5：回退 n 帧	协议 6：选择性重传
发送窗口（SWnd）	$0<SWnd\leq1$	$0<SWnd\leq MAX_SEQ$	$0\leq SWnd\leq Rwnd$
接收窗口（Rwnd）	$RWnd=1$	$RWnd=1$	$RWnd=(MAX_SEQ+1)/2$

介质访问控制子层

MAC 子层概述

数据通信方式
- 单播：一对一
- 广播：一对所有（局域网）
- 组播：一对组
广播网络面临的问题：多路访问信道的分配
怎么分配信道（介质访问控制）
- 静态分配：预先分配给各用户
  - FDM 和 TDM 就是信道的静态分配的例子
  - 缺点：资源分配不合理、有资源的浪费、延迟时间增大 N 倍
  - 适用于：用户少且数目固定、通信量大且流量稳定的情况
- 动态分配：信道开放，按需分配
  - 多路访问协议
    - 随机访问协议
    - 受控访问协议

ALOHA 协议

ALOHA 协议是随机访问协议

纯 ALOHA 协议

工作原理
- 生成帧后即可发送
- 检测信道，判断是否发送成功
- 如果冲突，则重发
- 任性，想法就发
信道衡量指标
- 吞吐率 $S$ ：在发送时间 $T$ 内发送成功的平均帧数
- 运载负载 $G$ ：时间 $T$ 内所有通信站总共发送的帧的平均值
- $P_0$ $P_{0}$ ：一帧发送成功的概率
  - 冲突危险期：
    - 时间长度： $2t$
    - 生成帧的均值： $2G$
    - $S=G*P_0$
    - 在 2t 的时间内都不产生新帧： $P_0=e^{-2G}$ $P_{0} = e^{- 2 G}$
      - $G=0.5\quad S_{0_{max}}=18.4%$

分隙 ALOHA

工作原理
- 把时间分成时隙——时隙长度对应一帧的传输时间
- 新帧随机产生，但是不允许随机发送，发送必须在时隙的起点
  - 所以冲突发送只会发生在起点
性能分析
- $P_0=e^{-G}$ $P_{0} = e^{- G}$
  - $G=1\quad S_{0_{max}}=36.8%$

CSMA 协议

改进的 ALOHA 协议
特点：先听后发

非持续式——载波侦听多路访问协议

侦听介质空闲：发帧
侦听介质繁忙：等待随机时间后重新侦听

非持续式——载波侦听多路访问协

侦听介质空闲：发帧
侦听介质繁忙：持续侦听
问题：如果同时侦听，那么空闲时后会同时发送导致冲突

p-持续式

侦听介质空闲：以 p 的概率发帧
侦听介质繁忙：持续侦听
问题：如果同时侦听，那么空闲时后会同时发送导致冲突

冲突窗口

定义：发送冲突时间的上限，即发送站发出帧后能检测到碰撞的最长时间，数值上等于最远两站的传播时间的两倍
公式：

物理信道长度 $s$

信道在物理信道上的传播速度 $v$

网卡延时 $t_{PHY}$

$N$ 个中继器，每个中继器延迟时间位 $t_{\text{中继器}}$

则冲突窗口时间 $Slot\quad time =2*(s/v+t_{PHY}+N*t_{\text{中继器}})$

CSMA/CD (1-持续)

先听后发，变发边听
工作原理
- 侦听介质空闲：发帧
- 侦听介质繁忙：持续侦听，一旦空闲立即发送
- 如果发生冲突，等待一个随机分布的时间再重新侦听
特点
- 所有工作站在发送的同时也接收自己的信号，监测发送的情况，一旦收到的信号与发出的不一致，就说明发生了冲突
- 发送站感知冲突后立即停止帧的发送，并且发一个简短的堵塞信号（强化冲突信号），通知各工作站已经发生冲突，所有站都等待一段随机分布的时间，然后再按 CSMA/CD 方式重发帧

冲突的检测和处理

冲突检测的要求
1. 时隙宽度=最大冲突检测时间：保证一个时隙内能够检测到最远距离的冲突
2. 发送有效帧的时间 >= 最大冲突检测时间：防止因在发生冲突时已完成短帧发送而造成的异常情况

以太网概述

经典以太网
交换式以太网：广泛使用

IEEE 以太网命名规则

10Base2
- 10：传输带宽（Mbps）
- Base：基带传输
- 2：支持的分段长度
10Base-TX
- T：铜制非屏蔽双绞线
- F：表示光缆

以太网工作站接收数据流程图

二进制指数后退算法

Q：发送方在检测到冲突后，双方（或多方）都将延时一段时间，那么这段时间到底是多长？

A：冲突检测到后，时间被分成离散的时隙

时隙的长度等于信号在介质上来回传输时间 $51.2μshe$
一般地， $i$ 次冲突后，等待的时隙数将从 $（0 ∼2^{i-1}）×51.2μs$ 中随机选择。

以太网帧

IEEE 802.3和以太网帧的比较

IEEE802.3和以太网帧的比较

帧结构的各个字段含义

前导码与帧起始字段
- 前导码：7个字节，10101010…101010比特序列
- 帧起始符：1字节，10101011
目的地址和源地址字段
- 地址字段长度：48位（6个字节）
- 目的地址类型：
  - 单一结点地址（unicast address）
  - 组播地址（multicast address）
  - 广播地址（broadcast address）
- 物理地址（MAC地址）
  - 地址数约 $7 X 10^{13}$ ，7万亿个。
  - Ethernet地址= Manufacture ID + NIC ID=24bit (OUI)+ 24bit
  - 表示方法：- : .
  - 具有全球唯一性
长度字段（DIX以太帧中变为：类型）
- 帧的最小长度为64字节，最大长度为1518字节，不包括前导码
- 在DIX以太帧中，type 字段指明上层网络协议的了类型
- 在IEEE 802.3帧中，length 字段指明了携带的数据的长度
数据字段
- LLC数据字段是帧的数据字段，长度最小为46个字节
  - 如果少于46个字节，需要填充。
帧校验字段：采用32位的CRC校验
- 校验范围：目的/源地址、长度、LLC数据等字段

Q：怎么区分到底代表类型还是长度呢？

A：检查这个字段的数值：如果小于等于1536(0x600)，则是长度（802.3）字段，如果大于1536，则表示类型（以太帧）

Q：为什么有效帧长度最小为64 Byte

A：CSMA/CD的要求——最短帧的发送时间>=争用时隙 2t，以太网（802.3）规定，在10Mbps局域网中：时隙：2t= 51.2 微秒，最短帧长度：10Mbps×2t/8 = 64 Byte

二层交换

问题引入

Q：为什么需要二层交换

A：有很多LAN，可用网桥（bridges）将它们连接起来

网桥工作在DLL层，通过检查MAC地址做出转发帧的决策，不会检查网络层

Q：谁来完成二层交换？

A：网桥/交换机

透明的网桥

通过透明网桥将多个LAN连接起来，硬件和软件不需要做任何的变化
透明网桥工作在混杂模式，它接收所有跟它相联的LAN的帧
当一个帧到达网桥时，它必须作出丢弃还是转发的决策，如果是转发，它还要知道向哪个LAN转发
- 决策是通过在网桥内部的一张地址表中查找目的MAC地址而作出的
网桥/交换机隔离了冲突域

维护转发表

初始时，这张表是空的
扩散算法（泛洪算法）：当网桥不知道目的地址时（表中查不到），它会将这帧从除来的LAN外的所有LAN转发出去
逆向学习：网桥从到达帧的源地址认识到源地址对应的那台机是在帧来的那个LAN上，所以，把它写入MAC地址表

※：但是拓扑是变化的，网桥怎样适应这种变化？

无论何时，凡往表中加入记录，也必须同时打下时戳
到达帧的源地址在表中已有记录，将时戳更新为当前时间
网桥周期性地扫描表，将那些超时的记录从表中删除

网桥工作原理

当一帧到达时，网桥启动如下算法
1. 如果源LAN和目的LAN相同，则丢弃该帧；
2. 如果源LAN和目的LAN不同，则转发该帧；
3. 如果目的LAN未知，则广播该帧。
4. 每当一帧到达，上述算法都将执行一遍

生成树协议

为了可靠，采用冗余结构；但是透明网桥会产生无休止循环的问题
- 冗余交换拓扑可能带来的问题
  1. 广播风暴
  2. 多帧传送
  3. MAC地址库不稳定
生成树协议：STP（spanningtree protocol）
- 新标准：RSTP
STP的运作
- 每个网络一个根网桥
- 每个网桥一个根端口
- 每网段一个指定端口
- 非指定端口不被使用

※：生成树算法，生成在逻辑上无回路的树，即生成树

生成树算法能在有物理回路的网络中，生成一棵没有逻辑回路的生成树，但并不能保证其中的路径是最优的
当逻辑STP树上的某点出故障了，非指定端口将会被重新启用

虚拟局域网

虚拟局域网（VLAN）：一组逻辑上的设备或用户，这些设备和用户不受物理位置的限制，相互之间的通信就好像它们在同一个网段中一样
- 一个VLAN对应一个广播域
- 有了VLAN，可使用二层交换机实现广播域的分割
实现方法
- 基于端口（最常用）
- 基于MAC地址
- 基于三层协议
IEEE 802.1Q 标准：1998年颁布的一种帧标记方法：VLAN ID
- 通过trunk的时候使用

二层设备

NIC 网卡

NeworkInterface Card
- 为主机提供介质的访问
- MAC地址烧在网卡的ROM中
功能
- Logical link control (LLC): 和上层通信
- Naming: 提供一个独特的MAC 地址标识符
- Framing: 封装过程的一部分，为传输比特流打包
- Media Access Control (MAC): 为访问共享介质提供访问策略
- Signaling:创建信号和与介质的接口
运作
- 第一层设备
  - 创建信号和与介质的接口
  - 内建转发器
- 主要是第二层的设备
  - 在计算机中与上层通信
  - 烧入芯片的 MAC 地址
  - 封装数据城帧
  - 提供介质访问

网桥

连接不同的 LAN 网段。
通过过滤部分交通流量，减少冲突的机会，改善网络性能。
以 LAN 段分流交通，基于 MAC 地址过滤流量

交换机

交换机：多端口的网桥

LAN交换机中地址表的维护

动态更新
- 直接读取数据包中的源地址信息，存入CAM，如在CAM中没有找到所需的地址，添加到CAM中删除过时的地址记录：
时间标记
- 每增加一条记录，为它打上时间标记
- 每引用或找到某条记录，为它打上新的时间标记
- 当某条地址记录超过一定时间没被引用，则删除它

交换机的工作原理

flooding：当目的地址未知或为广播地址时，桥发送帧到除源端口之外的每个端口
learning：通过读取每个帧的源地址和对应源端口来学习连在网段上的每个设备的地址
forwarding：对于已学到的目的地址，桥将直接发送帧到对应的目的设备所在端口
filtering：如果目的地址和源地址在同一端口，桥将丢掉帧

交换机的作用

使网络段处于无冲突环境
LAN 交换机利用现有硬件设备
使配置和管理更加灵活方便

交换机的特点

无冲突域
- 微分段：LAN 被交换机分隔开的网段，在一个大的冲突域中产生无冲突域
- 虚拟线路：在交换机内部把段连接成一个虚拟网络的电路，只在需要时才成立

交换机的交换模式

存储转发：读完，计算校验再发送
- 延迟大
- 出错率小
直通交换（贯穿）：读到目的 MAC 地址就发送
- 延迟小
- 出错率大
无分片交换：读完字节满 64 个再发送
- 折中

一层、二层设备比较

功能	网桥	中继器
再生信号	Yes	Yes
连接采用不同 MAC 协议的网段	Yes	No
隔离冲突域	Yes	No
根据帧头的物理地址转发帧	Yes	No
丢弃损坏帧	Yes	No

网络层

网络层概述

网络层的作用：将源端数据包（分组）一路送到接收方
- 封装源数据
- 识别目的机
- 找到一根好的路径（路由）
源和目的之间的网络
- 数据包网络：无连接的服务
- 虚电路网络：面向连接的服务

比较项目	数据报子网（无连接服务）	虚电路子网（面向连接服务）
建立电路	不需要	要求
地址信息	每个分组含完整的SA和DA	每个VC包含一个很短的VC号码
状态信息	路由器不保留任何连接状态信息	每个VC都要求路由器建立表项
路由	每个分组独立选择路由	每个分组沿建立VC时确定的路由
路由器失效影响	没有，只有系统崩溃时丢失分组	所有经过失效R的VC都终止
服务质量/拥塞控制	很难实现	总资源（带宽、缓存）足够的情况下，采用提前给每个VC分配资源的方法，很容易实现

IP 互联网协议

IP 的任务：提供一种尽力而为（best-effort）地把数据从源端传输到接收方的方法
封装的格式：Internet Protocol
标识收发数据机

IP 地址

ICANN域名和地址分配机构负责总池：层级分配
点分十进制表示
- 32位被分成了4个8位组
相邻8位组之间用“.”分隔
- 每个8位组转换成十进制数，从0到255

A 类地址

前 1 字节标识网络地址部分，后 3 字节标识主机地址部分
每个网络最多可容纳 $2^{24}-2$ 台主机
第1字节用十进制表示的取值范围为0－127
具有 A 类地址特征的网络总数为 128 个

A类地址

B 类地址

前 2 字节标识网络地址部分，后 2 字节标识主机地址部分
每个网络最多可容纳 $2^{16}-2$ 台主机
第1字节用十进制表示的取值范围为 128－191
具有 B 类地址特征的网络总数为 $2^{14}$ 个

B类地址

C 类地址

前 3 字节标识网络地址部分，后 1 字节标识主机地址部分
每个网络最多可容纳 254 台主机
第 1 字节用十进制表示的取值范围为 192－223
具有 C 类地址特征的网络总数为 221 个

C类地址

三类IP地址的比较

类别	网络数	主机数/网络	最高字节取值范围	网络规模
A 类	128	1600 万	0-127	大型
B 类	1.6 万	6.5 万	128-191	中型
C 类	200 万	254	192-223	小型

保留的 IP 地址

D类（224.0.0.0~239.0.0.0）【多址传送地址】和 E类（240.0.0.0~254.0.0.0）【保留将来使用】
网络地址：主机部分全为 0 的IP 地址
广播地址：主机部分全为 1 的IP 地址
32位全为0，0.0.0.0
- 这个主机、这个网络
- Cisco路由器指定的默认路由
32位全为1，255.255.255.255
- 泛洪广播（Flood Broadcast）= 本地广播（Local Broadcast）
127.0.0.0 Lookback Network
127.0.0.1 Lookback test
169.254.x.x，非正常地址

子网

局域网不断增长，越来越难于管理，必须将它分割成子网
一个网络被分隔成几个部分（子网），但是在外界看来，该网络仍被看成一个整体(体现在路由表例上，就是外部的路由器只对应一条路由）
主/边界路由器和外部联系，然后转发给子网

子网掩码

路由器使用子网掩码决定分组往哪个子网转发，是子网的重要属性
子网掩码可用点分十进制表示（1表示网络位，0表示主机位），也可用“/网络位数+子网位数”表示
路由器采用 AND 操作（目的IP和子网掩码），得到目的网络地址
- 减少了路由器的存储压力
默认子网掩码
- A：/8
- B：/16
- C：/24

构建子网

构建子网是通过从网络地址的主机部分借位来进行
- 从主机域的高位开始借位
- 主机域至少保留 2 位
可用主机数量的公式 $2^n-2$

IP 寻址

定位到目的机：通常要定位到目的机，是先通过IP寻址找到目的网络，再通过MAC寻址找到目的机
路由器的主要功能
- 打开分组
- 确定目标网络（AND），查找路由表
- 重新封装，转发
路由器转发数据的依据：路由表
- 主要包括：目的网络地址，接口，代价metric (f.g. hop)，子网掩码，网关

IP 分组

IP分组

协议版本
- 4 bits
- 标明IP协议的版本号
  - IPv4 : 0100
  - IPv6 : 0110
报头长度
- 4 bits
- 以 4 bytes 为单位标明报文长度，可指向数据开始处
- 最小为 20 bytes，最大为 60 bytes，其中的 40 bytes 供IP选项使用
服务类型
- 8 bits
- 上层协议表明该分组的重要程度
  - Precedence
  - Reliability
  - ECN.
数据报总长度
- 16 bits
- 指明整个数据分组的总长度，包括数据头和数据。单位 bytes
数据报标识号
- 16 bits
- 标识当前数据报的序列号
- 由发送者分配，以便接收方可以依据来做重组
标志
- 3 bits
- 标志分组是否分片
分片偏移
- 13 bits
- 帮助收方重组
生存时间
- 8 bits
- TTL 维护一个计数器，递减为零时，数据报被丢弃，防止分组在网络中无限循环
用户协议
- 8 bits
- 用来指定传输层协议
  - 17(UDP)
  - 6(TCP)
报头检验和
- 16 bits
- 针对头部计算校验和，验证分组头部的正确性
源/目的站点IP地址
- 源和目的地址都是32位（IPv4）
数据报选项（可选）
- 可变长字段
- 允许 IP 支持一些安全、时间戳等可选项
填充
- 可变长字段
- 确保 IP 头是 32 位的整数倍

IPv6

Q：为什么需要 IPv6？

IPv4 先天不足，自带危机——安全问题、地址缺乏、端到端业务模式、配置复杂，路由表的膨胀等
- 地址匮乏可以使用 NAT 来缓解，但是这将 “端——端” 变成了 “端——转换器——端”

IPv6 地址

最显著的变化——地址空间
- IPv4：约40亿
- IPv6：约340涧
IPv6 地址表示：冒分十六进制
- 把 128 位的二进制数，分成 8 组，然后每组转换为 4 位 16 进制数
- 规则 1：省略每组的前导 0（0001→1）
- 规则2：忽略全 0，用双冒号表示（1:0:0:2→1::2）
  - 一个地址最多一个双冒号
- 地址前缀长度用 “/xx” 来表示
IPv6 地址分类
- 单播地址
- 组播地址
- 任播地址
- 特殊地址

地址类型	二进制前缀	IPv6标识
未指定	00…0 (128 bits)	::/128
环回地址	00…1 (128 bits)	::1/128
组播	11111111	FF00::/8
链路本地地址	1111111010	FE80::/10
网点本地地址	1111111011	FEC0::/10
全局单播	（其他）

单播地址
- 应用范围：用在单一链路上
- 带有链路-本地源或目的地址的数据包不转发到其他链路
链路本地地址
- 应用范围：只在同一本地链路节点之间使用
- 节点启动时，自动配置一个本地链路地址
- 生成链路本地地址
  - 前 64 位：FE80:0:0:0
  - 后 64 位：EUI-64 地址
    - 先将 MAC 地址写成二进制形式，一分为二
    - 然后在中间添加 11111111 11111110，将第一组的第一个 0 转化为 1
站点本地地址
- 应用范围：站点内，与 IPv4 私人地址类似
- FEC0:0:0:SID::/64
- 不是自动生成的
可聚合全球单播地址
- 提供商分配的前缀：/48
- Site拓扑：由组织机构划分子网
- 接口ID：64
组播地址
任播地址
- 用于标识一组网络接口
- 目标地址为任播地址的数据报将发送给最近的一个接口

Q：IPv6 如何做到即插即用的？

A：

启动时，生成链路本地地址
该地址可和网关通信，获得全球IP地址前缀，利用手工、EUI-64地址、随机生成的方法生成后缀
也可利用DHCP获得上网所需的资源

各类地址的应用范围

IPv6各类地址应用范围

IPv6地址子网规划

IPv6 子网划分是根据路由器的数量及它们所支持的网络来构建寻址分层结构

IPv6子网规划

IPv6 分组

IPv6分组

版本号
- 4 bits
业务服务
- 8 bits
- 提供区分服务，表明该分组的重要长度、优先级等
流标记
- 20 bits
- 表示分组的业务需求标记，提供服务质量
净荷长度
- 16 bits
- 指明了搭载数据的长度（不含报头）
下一个头
- 8 bits
- 指明了紧跟的扩展头类型
- 最后一个扩展头或无扩展头，退化为用户协议
  - 6：TCP
  - 17：UDP
跳数限制
- 8 bits
- 和 TTL 的功能完全一样
源/目的站点IP地址
- 源和目的地址都是128位（IPv6）

Ipv6 扩展头

目前，已经定义了6种扩展头
扩展头是可选的，可以有多个扩展头，但是必须按一定的顺序排列
扩展头有固定的格式
其他扩展头包含可变数目的可变长度域
- 每个可变项都被编码成(Type，Length，Value) 三元组
每一种扩展报头其实也有自己特定的协议号（下一个头NextHeader），例如：路由报头为43，AH报头为51

路由表

路由器分组转发的依据：路由表
路由表从何而来：直连路由、静态路由、动态路由
直连路由：开启了路由器接口后，自动发现
静态路由：管理员手工配置的路由
- 一种常用的静态路由：默认/缺省路由
  - 是默认的路径，找不到路的时候可以从这里通过
动态路由：由路由选择协议动态地建立、更新和维护的路由
- 适合大型的、经常变动的网络，需要维护开销
- 减少了网络管理员的负担
- 动态路由从何而来？
  - 距离矢量路由选择（DV）：RIP：路由信息协议
  - 链路状态路由选择（LS）：OSPF：开放的最短路径优先
- 怎么量度路径的优劣？
  - 路径长度、可靠性、延迟、带宽、负载、通信代价

距离矢量路由选择

D-V 算法是动态的和分布式的，它常被用于小型网络
- RIP是一个典型的DV

DV的工作原理

每个路由器（节点）维护两个向量， $D_i$ 和 $S_i$ ，分别表示从该路由器到所有其它路由器的距离及相应的下一跳
在邻居路由器之间交换路由信息（矢量）
每个路由器（节点）根据收到的矢量信息，更新自己的路由表
- 更新规则：选择 i 到 j 最短的距离的路径

D-V算法的特点

优点：简单
缺点：交换的信息太大了；路由信息传播慢，可能导致路径信息不一致；收敛慢，度量计数到无穷；不适合大型网络

路由选择信息协议 RIP

种类
- RIPv1：有类的路由选择协议
- RIPv2：无类的路由选择协议，支持 CIDR、VLSM 等
- RIPng：支持 IPv6
主要特点
- RIP 是一种典型的D-V 路由选择协议
- RIP 采用了跳数（hop）作为量度（metric）
- 当量度超过15 跳，目的被认为不可达
- 默认地，每30秒钟交换一次矢量（全部路由表）
主要缺陷
- 不能到达量度超过15跳的目标网络
- RIP的度量（代价）是跳数，有时候不能真正反映网络的状况
- 实际运行中，会遇到度量计数到无穷、形成路由环、收敛慢等问题
  - 因为路由器只能直接获取近邻信息，所以有可能传播、学习到错误的路由信息
解决办法
- 定义路径度量（代价）的最大值
- 提高收敛速度
  - 水平分割
  - 毒性逆转
  - 抑制定时器
  - 触发更新

链路状态路由选择

优点
- 每个路由器的认识一致
- 收敛快
- 适合在大型网络中使用
缺点
- 路由器需要较大的储存空间
- 计算负担大
主要思想
- 发现它的邻居节点们，了解它们的网络地址
- 设置到它的每个邻居的成本度量
- 构造一个分组，包含它所了解到的所有信息
- 发送这个分组给所有其他的路由器
- 计算到每个路由器的最短路径

发现

一个路由器启动的时候，在每个点到点的线路发送一个特别的 HELLO 分组
收到HELLO分组的路由器回送一个应答，应答中有它自己全球唯一的名字

设置

为了决定线路的开销，路由器发送一个特别的ECHO 分组，另一端立刻回送一个应答
通过测量往返时间（round-trip time），发送路由器可以获得一个合理的延迟估计值

构造

链路状态分组构造后被发送给其他的路由器
周期性地构造和发送，或者有特别的事件发生时构造，比如某条线路或邻居down掉了

发布

基本算法
- 每个分组都包含一个序列号，序列号随着新分组产生而递增
- 路由器记录下他看见的所有(源路由器，序列号)对
- 当一个的新的分组到达时，路由器根据它的记录：
  - 如果该分组是新的，就被从除了来线路外的所有其他线路广播
  - 如果是重复分组，即被丢弃
  - 如果该分组的序列号比对应的源路由器发送的到过此地的分组的最大序列号还小，则该分组被当作过时的信息而被拒绝
可能遇见的问题及解决方法
- 序列号回转：采用 32-bit 序列号
- 序列号传输时出错：利用 Age 丢弃
进一步的改进使基本算法更加健壮：使用保留区

计算

一个路由器获得了全部的链路状态分组就可以构造出全网络图来了
- 所有路由器的链路状态分组是一样的
使用最短路径算法来计算路由器之间的最短路径

L-S路由协议的实例—OSPF

OSPF 是一种基于开放标准的链路状态路由协议，是目前IGP中应用最广、性能最优的一个协议
必须划分区域，所有子区域必须连接到区域 0 上

单区域OSPF

RouterID：一台路由器的唯一标识，在整个自治系统内唯一
协议号：IP头代表 OSPF 报文的协议号是 89
TTL=1：通常 OSPF 报文不转发，只被传递一条

OSPF包类型

Hell：o与邻居建立和维护毗邻关系。
数据库描述包（DD）：描述一个OSPF路由器的链路状态数据库内容
链路状态请求（LSR）：请求相邻路由器发送其链路状态数据库中的具体条目
链路状态更新（LSU）：向邻居路由器发送链路状态通告
链路状态确认（LSA）：确认收到了邻居路由器的LSU

OSPF的运行步骤

建立路由器毗邻关系
选举DR和BDR
发现路由
选择最佳路由
维护路由信息

无类域间路由CIDR

目的：缓解了地址枯竭的趋势；控制甚至缩减了路由表的开销
基本思想：分配IP地址的时候不再以类别来分，而是按照可变长的地址块来分配（按需分配）
- 路由表必须扩展，增加一个32-bit 的子网掩码
当一个分组到来到的时候
1. 分组中的目标IP地址被检查
2. 目标IP和子网掩码进行与操作，获得目标网络地址，以查找路由表
3. 如果路由表中有多个表项匹配（这些表项有不同的子网掩码），使用子网掩码最长的那个表项
CIDR 可以路由聚合，形成超网
CIDR 的好处
- 缩减路由表规模
- 隔离路由翻动

网络地址翻译 NAT

目的：缓解地址枯竭的趋势
NAT：私有IP地址和公有IP地址之间的转换
PAT：将多个私有IP地址影射到同一个公有IP地址的不同端口

※概括：内部网络使用私人地址，当内网需要和外网通信的时候，私人地址转换成合法的 global 的地址

原理
1. 由NAT转换器（盒子）完成这种转换；NAT转换器能够转换并且维护一个地址转换表，以便回来的分组找到它的去处
2. 当回来的分组到达NAT转换器的时候，它查找地址转换表（以源端口作索引），获得目标机的私人地址，并转换地之后发往目标机
NAT 带来的问题
- 违背了IP的结构模型——每个IP地址唯一地标识了一台机器
- 将互联网改变成了“面向连接”的网络，NAT转换器维护着连接的状态，一旦它崩溃，连接也没有了
- 违背了最基本的协议分层原则（涉及端口，这是传输层）
- 如果传输层不是采用TCP或UDP，而是采用了其它的协议，NAT将不再工作
- 有些应用会在payload中插入IP地址，然后接收方会提取出该IP地址并使用，但是NAT转换器对此一无所知，导致该类应用不再有效

互联网控制协议ICMP

目的：IP分组传送不可靠，可能遭遇各种问题。ICMP 用来向源报告这些问题或状况，ICMP也能用来测试网络
消息格式

ICMP格式

应用
- ping：发送ICMP回声请求报文
- tracert：利用 ICMP 超时报文来获得一张途径的路由器列表
- PMTU：获得途经的最小 MTU
规定：ICMP 消息不生成自己的报告差错

地址解析协议ARP

目的：找到一个给定IP地址所对应的MAC地址
ARP请求/ARP应答
优化措施
- 缓存ARP 结果
- 在ARP请求中包括源机的IP-to-MAC 地址的映射
- 每台机器在启动的时候，广播它的IP-MAC地址对
免费ARP
- 当一台主机启动时，发送要给一个免费ARP
  - 如果意外收到一个应答，即是IP地址发生了冲突
- 当一个接口（interface）的配置发生了改变，会发送一个免费ARP
缺省网关（代理ARP）
- 当源设备需要的目的地址与自己不在同一个网络时，如果源不知道目的MAC地址，它必须使用路由器的服务使它的数据达到目的，当路由器在这种方式下使用时，称为缺省网关
- 缺省网关是与源设备所处的网段相连的路由器接口上的IP地址
ARP table
- IP地址到MAC地址的映射表
- 为了减少ARP请求的次数，每个设备拥有自己的ARP表，包括路由器
- 储存在存储器（RAM）中，自动维护（掉电消失）
ARP具有安全隐患

拥塞控制

拥塞：当一个子网或子网的一部分出现太多分组的时候，网络的性能急剧下降（负载>资源）
处理策略
- 开环（Open loop）：试图用良好的设计来解决问题，本质是从一开始就保证问题不会发生
- 闭环：建立在反馈环路的概念上，进行：检测、传递、调整
【闭环|检测】拥塞量度：衡量拥塞程度
【闭环|传递】拥塞休息传播
对于拥塞采取的措施
- 抑制分组：收到抑制分组后，会减少它发向目标的流量
- 逐跳抑制分组：让分组路径的每个路由器都采取相应措施
- 负载丢弃/载荷脱落：最极端的方法
  - 随机丢弃
  - 葡萄酒策略：丢弃新的，适合文件传输类
  - 牛奶策略：丢弃旧的，适合多媒体类
  - 丢弃不重要的：需要表明优先级
- 随机早期检测：防患于未然

流量整形

目的：调节数据传输的平均速率

漏桶算法

算法描述
1. 每个主机连接到网络的接口中都有一个漏桶，即一个优先长度的内部队列
2. 当桶中有分组的时候，输出速率是恒定的，当桶空的时候，输出速率是0
3. 当一个分组到达满的桶的时候，分组将被丢弃（满则溢）
4. 每个时钟嘀嗒( tick)，仅允许一个分组或固定数量的分组发送出去
效果：让输出到网路的分组流变成一个稳定流，抹平了突发尖峰，极大地减少了发生拥塞的机会
缺点：不能大量地突发数据（满则溢）

令牌桶算法

算法描述
1. 当大量数据突发的时候，令牌桶算法允许输出加快到某种程度
2. 令牌桶拥有令牌（tokens），且以每 $\Delta T$ 秒产生一个令牌的速度往桶中输入令牌
3. 一个分组要发送的时候，它必要从桶中取出和获取到一个令牌
4. 令牌桶算法允许累积令牌，但最多可以累积 $n$ （令牌桶的容量）个令牌
对比漏桶算法
- 允许突发，但是最大突发受制于令牌桶容量
- 桶满时，丢掉的是令牌而不是分组
计算最大突发时间
- 突发时间：S 秒
- 令牌桶容量：B字节
- 令牌到达的速率：R字节/秒
- 最大输出速率：M字节/秒
则 $B+RS=MS\\S=B/(M-R)$

传输层

传输层概述

传输层是整个协议栈（TCP/IP）的核心
传输层的协议主要两个：UDP、TCP
传输层的人物是提供可靠的、高效的数据传输
- 向上提供标准的传输服务
- 向下屏蔽不同的通信子网
与网络层类似，传输层有两种传输层服务
- 面向连接的服务
- 无连接的服务 Connectionless

Q：既然如此，为什么需要两个独立的不同的层（网络层和传输层）？

A：网络层运行再承运商操作的路由器上，用户不能真正控制网络层；

把另一层放在网络层之上，可以让用户能够控制到服务质量；

传输层原语独立于网络层原语，而网络层原语会因为网络的不同而不同

传输层提供的功能
- 端点标识
- 传输服务
  - 面向连接：端到端的连接管理、流控制、差错控制
  - 无连接
传输服务和网络服务的两个主要差别
- 网络服务试图按照实际网络提供的服务来建模（不可靠的），而面向连接的传输服务是可靠的
- 网络服务仅被传输实体所使用；而传输服务直接被应用程序所使用，必须方便易用

数据段（TPDU，传输层协议数据单元）

TPDU(Transport Protocol Data Unit) 是从传输实体发到对端传输实体的信息
TPDUs 被封装在分组（packet）中，由网络层交换
分组被封装在帧（frames）中，由数据链路层交换

用户数据报协议 UDP

UDP 是一个无连接的传输层协议
UDP不提供数据传输的可靠保证，追求简洁高效
UDP 数据段包括8字节的头部和数据两个部分

UDP

其中的长度域表示的长度包括头部和数据总共的长度
校验和是可选的，如果不计算校验和，则该域置为0
UDP比IP好的地方在于它可以使用源端口和目的端口

端口 port

16位，共有 $2^{16}$ 个端口
端口的范围：0~65535

端口	作用
<1023	用于公共应用
1024~49151	用户端口，注册端口
>49152	动态端口，私人端口

TCP/UDP伪头部(pseudo header)

UDP伪头部

通信模型

套接字 Socket：（IP，Port）
通信5元组
- 源IP
- 源端口
- 目的IP
- 目的端口
- 协议

※：此端口 port 和路由器的端口 interface 不一样！

传输层的PDU不仅仅送达主机，而且送达端点

TCP数据段

TCP是专门为了在不可靠的互联网络上提供可靠的端到端字节流而设计的
支持 TCP 的机器都有一个 TCP 实体，或者是用户进程或者是操作系统内核，都可以管理 TCP 流和跟 IP 层的接口
- 发：分片封装
- 收：解封装，重构字节流
TCP软件决定数据段的大小，有两个因素限制了数据段的长度
- TCP数据段必须适合IP的65515(65535-头部20)的载荷限制
- 每个TCP数据段必须适合于下层网络的MTU（如，1500 字节–以太网载荷大小）
TCP使用的基本协议具有动态窗口大小的滑动窗口协议

TCP 数据段（TPDU）格式

TCP分组

源端口和目的端口字段：标明了一个连接的两个端点
- 用来跟踪同一时间内通过网络的不同会话
- 一般每个端口对应一个应用程序
序列号：字节号(32 位)
- 初始序列号ISNs(initial sequence numbers )：随机产生
- SYN：携带了ISNs 和SYN 控制位的数据段
确认号：期望接收的字节号(32位）
TCP 段头长度：TCP段头长度，单位32位（4字节）
保留域/字段
URG：当紧急指针使用的时候，URG 被置为1。紧急指针是一个对于当前序列号的字节偏移量，标明紧急数据从哪里开始（1字节）
ACK：1表示确认号有效，0标明确认号无效（1字节）
PSH：表示这是带有PUSH标志的数据接收方收到这样的数据，应该立刻送到上层，而不需要缓存它（1字节）
RST：用来重置一个已经混乱的连接（1字节）
SYN ：用在连接建立的过程（1字节）
- SYN=1，ACK=0连接请求；当SYN=1，ACK=1连接接受
FIN被用来释放连接，它表示发送方已经没有数据要传输了，但是可以继续接收数据（1字节）

※：TCP中的流控(Flow control)使用一个可变长的滑动窗口来完成的

Window size：告诉对方可以发送的数据字节数
- 从确认字节号开始（决定于接收方）
Checksum：提供额外的可靠性
选项域提供了一种增加基本头没有包含内容的方法

TCP 连接的建立

采用三次握手建立连接

SYN泛洪导致DoS攻击（伪造源IP）

TCP 连接释放

两军队问题：最后信息的发送者，永远无法知道这个信息是否到达
- 解决方法：定时器
TCP 连接释放的步骤
1. 任何一方在没有数据要传送的时候，都可以发送一个FIN置位了的TCP
2. 数据段当FIN被确认的时候，该方向的连接被关闭
3. 当双向连接都关闭了的时候，连接释放
4. 如果一方发送了FIN数据段出去却在一个设定的时间没有收到应答，释放连接
5. 另一方最终会注意到连接的对方已经不在了，超时后连接释放
半开放连接
- 理论上讲，如果初始DR的和重传都丢了，协议失败
- 发送者将放弃发送且释放连接，但是，另外一端却不知道这些情况，仍然处于活跃的状态
- 这种情形导致半开放连接
杀死半开放连接的方式
- 如果在一定的时间内，没有TPDUs 到达的话，连接自动释放
- 如果这样，传输实体在发送一个TPDU的时候必须启动定时器，定时器超期，将发动一个哑TPDU，以免被断掉

TCP 传输策略

窗口尺寸受制于接收方
当窗口数为0 时，发送者不能正常发送数据段，除非:
1. Urgent数据。比如，用户想杀掉远端机器上的进程的时候，可以发送数据
2. 发送者可以发送一个字节的数据段，以便让接收者再次发送期待接收的字节号和窗口数（避免死锁）
如果每一字符进行一次响应，那么对带宽的要求会非常高，对应的解决方法
- 优化接收端：推迟发送确认分组和窗口更新窗口
- 优化发送端：Nagle 算法
傻瓜窗口综合症：Clark解决方案

TCP 拥塞控制

虽然网络层也试图管理拥塞，但是，大多数繁重的任务是由TCP来完成的，因为针对拥塞的真正解决方案是减慢数据率
分组守恒：当有一个老的分组离开之后才允许新的分组注入网络
TCP希望通过动态维护窗口大小来实现这个目标
两种因素引起拥塞警报
- 接收方处理不过来
- 通信子网中出现拥塞
处理拥塞的具体方法
- 接收者窗口：大小反映了目前窗口的容量（容易控制）
- 拥塞窗口：大小反映了网络目前的容量（难于控制）
CWND通过慢起动方法尝试而来
- 拥塞窗口二进制指数增长至接收窗口大小或超时
通过阈值调节CWND尝试的精度

TCP 定时器

最重要的定时器：重传定时器
持续定时器：用来接收方发出避免窗口数为零的确认后，再次发送更新窗口的数据段丢失导致的死锁
保活定时器：用来检查连接是否存活
在关闭时刻处于TIMED WAIT 状态中使用的定时器：运行两倍的最大分组生存时间，以确保连接关闭之后，该连接上的所有分组都完全消失

TCP 和 UDP 对比

TCP
- 可靠传输方式
- 可让应用程序简单化，程序员可以不必进行错误检查、修正等工作
UDP
- 为了降低对计算机资源的需求（DNS）
- 应用程序本身已提供数据完整性的检查机制，勿须依赖传输层的协议来保证
- 应用程序传输的并非关键性的数据（路由器周期性的路由信息交换）
- 一对多方式，必须使用UDP（TCP限于一对一的传送）（视频传播）

性能	TCP	UDP
可靠性	√	×
传输建立	不确定	网络延迟
拥塞控制	√	×

应用层

应用层概述

位置：没有上一层供它服务，直接服务于模型外的用户
主要功能：向应用程序提供网络通信
网络应用程序可被分为两大类
- 直接网络应用程序
- 间接网络应用程序：依赖于重定向器

DNS概述

在互联网中，使用IP地址作为机器的绝对地址，是行不通的，有两个原因：
1. 计算机可能常常地更换IP地址
2. IP地址难于记忆
域名系统DNS
- DNS是分层次的，基于域的命名方案，且采用了分布式数据库系统来实现
- 互联网被分成200多个顶级域每个域被分成若干子域，子域还可进一步划分
域名
- 每个域的名字是：从它向上到根（未命名）的路径，各个部分间用圆点隔开
- 域名可以是绝对的，也可以是相对的，绝对域名总是以圆点结束
  - 相对域名必须在一定的上下文环境中被解释出来才有意义，从而唯一地确定其真实的含义
  - 绝对域名和相对域名都引用了域名树中一个特定的节点，以及它下面的所有节点
- 域名是大小写无关的
- 各组成部分的名字最多有63个字符长，整个路径不超过255 个字符
- 没有规则限制同时在两个或多个顶级域名下的注册——域名抢注
- 每个域自己控制它下面的域（子域）的划分
- 要创建一个新的域，创建者必须得到该新域的上级域的许可，一旦创建成功，该新域可以创建子域，而无需征得上级域的同意
资源记录
- 每个域，无论是单主机域还是顶级域，都可以有一组跟它相关联的资源记录
- 当一个解析器把域名传递给DNS时，DNS所返回的是与该域名相关联的资源记录。所以DNS的主要功能是将域名映射到资源记录上
- 一个资源记录包括5个部分
  - 域名：指出这条记录适用于哪个域
  - 生存期：指示该条记录的稳定程度
  - 类别：对于互联网信息，它总是IN
  - 类型：指出了这是什么类型的记录 eg：A（IPV4），AAAA（IPV6）
  - 值
域名服务器：资源记录储存的地方
- DNS名字空间被分割成不相交的区域，每个区域包含域名树的一部分，也包含一台主域名服务器
- 主域名服务器从自己硬盘的一个文件中读取信息，次域名服务器分享这些信息
根域服务器：最高级域名服务器，存储所有顶级域名的名字和 IP
- 全球有 13 个根域服务器

域名解析

域名解析：将域名映射为IP地址的方法和过程
DNS的使用方法
- 为了将一个名字映射为IP地址，应用程序调用一个叫解析器的库过程，把名字作为参数传递给这个过程
- 解析器发送一个UDP分组给本地DNS服务器，它会负责查找该名字，然后将对应的IP地址返回给解析器
- 解析器返回结果给应用程序，然后应用程序即可开始工作了
域名解析的种类
- 递归查询：主机向本地域名服务器一般采用这种方法
  - 主机所询问的本地域名服务器不知道被查询域名的IP
    - 地址本地域名服务器以DNS 客户的身份，向其他根域名服务器继续发出查询请求报文
- 迭代查询：本地域名服务器向根域名服务器一般采用这种方法
  - 根域名服务器收到本地域名服务器的迭代查询请求报文
    - 给出所要查询的IP 地址
    - 告诉本地域名服务器：“你下一步应当向哪一个域名服务器
      - 进行查询”本地域名服务器进行后续的查询
域名解析的优化：高速缓存——减少查询环节，提高效率，但是缓存中的内容不具有权威性
DNS 的信息传递
- 使用 UDP
- 使用 TCP：报文超过512Byte、从服务器的数据更新

电子邮件

电子邮件系统通常由两部分组成：
- 用户代理(UA)：让用户能够阅读和发送邮件
  - 本地程序，提供命令行或图形界面，让用户和电子邮件系统交互
- 消息传输代理(MTA)：将消息从源端送到目标端
  - 通常是系统守护进程，即运行在后台的进程，在系统中传递电子邮件
电子邮件消息格式：RFC 822、MIME
- MIME –the Multipurpose Internet Mail Extensions，多用途互联网邮件扩展
  - 解决这些问题：带有重音符的语言（如法语）、非拉丁字母（如俄语）、不带字母的语言（如汉语）、完全不包含文本的消息（如视频）
Email 消息传输：SMTP
- 源机与目标机（SMTP守护进程在监听）的25端口建立TCP连接
- SMTP 的一些问题
  - 没有认证
  - 传输的是ASCII消息而不是二进制数据，需要编码，效率低下
  - 邮件是明文
最后传递：在ISP的一台机器上运行一个消息传输代理；这台机器可以一天24小时运行，随时都可以接收邮件
- POP3、IMAP、Webmail

万维网

WWW的组成部分
- 资源
- 统一资源定位器：URL
- 通信协议：http,https,ftp,etc.
Web 页面由 URL (Uniform Resource Locators)标识
- eg：http://www.abcd.com/products.html
  - 协议：http
  - 页面所在的机器的 DNS 域名：www.abcd.com
  - 包含web页面的文件的名字：products.html
- 当用户单击一个超级链接（URL）时，客户端：
  1. 浏览器检查 URL (读取浏览器的输入)
  2. 浏览器向 DNS 服务器询问域名的 IP 地址
  3. DNS 返回对应的 IP 地址
  4. 浏览器和 Web 服务器建立 TCP 连接（在端口80）
  5. 浏览器发送请求，要求获取文件 products.html
  6. Web 服务器返回被请求的文件
  7. TCP 连接被释放
  8. 浏览器解释显示下载到本地的文件
- 当用户单击一个超级链接（URL）时，服务器端：
  1. 接收来自客户的TCP连接
  2. 获取所需文件的名字
  3. 从本地磁盘上获取文件（静态页面）
  4. 将文件返回给客户
  5. 释放TCP连接
  - 改进：在内存维护一个缓存，保存最近用过的 n 个文件；多线程服务器
客户的TCP连接中止于前端，所以应答也必须经过前端
- 一种解决的方法是TCP移交，TCP端点被传递给处理节点，所以应答可以直接向客户端发送
浏览器解释资源的不同方式：内嵌插件或外挂
代理服务器(proxy server)：又称为万维网高速缓存(Web cache)，它代表浏览器发出HTTP 请求
- 万维网高速缓存把最近的一些请求和响应暂存在本地磁盘中。
- 当与暂时存放的请求相同的新请求到达时，万维网高速缓存就把暂存的响应发送出去，而不需要按URL 的地址再去因特网访问该资源。
服务器如何辨别用户？
- Cookie：一个小于4kB的命名串
- 当客户请求时，web服务器除了应答外，附送一个cookie，存储在客户机磁盘；客户再访问同一个web服务器时，同时发送cookie

其它应用

文件传输

FTP：一种可靠的面向连接的服务，采用 TCP 在支持 FTP 的系统间传输文件，它支持双向二进制文件和 ASCII 文件传输
TFTP：一种无连接的不可靠的服务，采用 UDP 在支持 TFTP 的系统间传输文件。
FTP 使用两条 TCP 链接
- 21 端口：控制进程
- 20 端口：数据传送进程

远程登陆

Telnet：不要求远地系统创建众多的服务器，只需为每个远程登陆用户建立一个进程，这个进程再通过创建子进程为远程登陆用户提供各种允许的服务
- 它提供与本地登陆几乎完全相同的用户界面
Telnet 工作在23端口
- SSH 工作在22端口

多媒体应用

实时：CiscoTele-Presence，华为智真
非实时

备忘

#计算机 #网络

计算机网络备忘

https://justloseit.top/计算机网络备忘/

作者

Mobilis In Mobili

发布于

2020年10月24日

更新于

2023年3月3日

许可协议

博客主题迁移以及一些杂谈上一篇