计算机网络基础

计算机网络基础#

分层和协议#

计算机网络是以连接和资源共享为目的把一些计算机和其他硬件设备通过通信通道互联所形成的集合体。

在计算机网络中，分层和协议的集合称为计算机网络的体系结构。其中，实际应用最广的是体系结构是 TCP/IP，由它组成了 Internet 的一整套协议。

网络体系结构中的分层概念保持网络灵活且易于修改，把相关的网络功能组合在同一层中。通过协议分层可以把设计问题划分成较小的易于处理的片段。

分层意味着某一层协议的改变不会影响较高层或较低层的协议，以下是 OSI 参考模型中每个分层的职责概述：

分层	职责
物理层	定义连接到介质的特征，在物理线路上传输原始的二进制数据位
数据链路层	指定在网络上沿着网络链路在相邻节点之间移动数据的技术规范，在有差错的物理线路上提供无差错的数据传输
网络层	在由许多开放系统构成的环境中允许网络实体之间进行通信，控制通信子网提供源点到目的点的数据传送
传输层	为用户提供端到端的数据传送服务，并且有错误恢复和流控功能
应用层	包含大量人们普遍需要的协议，提供各种通用和专用的功能

在 OSI 参考模型中，对等层之间的通信通过协议进行；要实现第 N 层的协议，需要使用 N+1 层提供的服务。

通信子网#

通信子网为网络源节点与目的节点之间提供了多条传输路径的可能，路由选择指的是网络中间节点收到一个分组后，确定转发分组的路径。

源节点的一个用户发送一个信息给目标节点的一个用户时：

在源节点的网络用户产生信息；
信息传给源节点的最高层（OSI 模型的应用层）；
当信息通过源节点时，每一层都给它加上控制信息；
信息以电信号的形式通过物理链路发射；
信息向上通过目标节点的各个网络层次，每一层都除去它的控制信息；
在目标节点的网络用户接收信息。

面向连接的通信#

面向连接的通信有三个阶段：

在连接建立阶段，先要做一个请求，然后才能建立连接；
只有在这个阶段被成功完成后，才可以开始数据传送阶段；
然后是连接释放阶段，例如 TCP。

无连接的通信#

无连接通信没有这些阶段，它只是发送数据，例如 IP。

传输效率#

如果一个帧被损坏的概率为 \(p\)，那么平均传输次数是 \(1/(1-p)\)。

奈奎斯特无噪声有限带宽信道最大数据传输率 \(= 2Hlog2(V)bps\)：任意信号通过一个带宽为 H 的低通滤波器，则每秒采样 2H 次就能完整地重现该信号，信号电平分为 V 级。

香农带宽为 \(H\) 赫兹，信噪比为 \(S/N\) 的任意信道的最大数据传输率 \(=Hlog2(1+S/N)bps\)。

编码方式#

曼彻斯特码：

也称相位编码，每一位中间都有一个跳变，从低跳到高表示 0，从高跳到低表示 1。

CRC 循环码性质：

由任何多于一项的生成多项式 \(g(x)\) 产生的循环码能够检测所有单个错误；
每个被 \((1+x)\) 除尽的多项式都具有偶数项；若生成多项式 \(g(x)\) 具有偶数项，则由它产生的编码就能检测所有奇数个错误；
若码长 \(n\) 不大于生成多项式 \(g(x)\) 的指数 \(e (即n≤e)\)，则由 \(g(x)\) 产生的码能够检测所有单个和两个错码；
\(g(x)\) 的指数 \(e\)：\(e\) 是使 \(g(x)\) 能除尽 \(exp{x}+1\) 的最小正整数；若码长 \(n\) 不大于 \(g1(x)\) 的指数，则由生成多项式 \(g(x)=(x+1)g1(x)\) 产生的码能检测所有单个、两个及三个错误；由 \((n-m)\) 次多项式产生的任一循环码，能检测所有长度不超过 \((n-m)\) 的突发错误；
长度为 \(b > (n-m)\) 的突发错误中：若 \(b = n - m + 1\)，则不能检测部分占 \(2^{-(n-m-1)}\)；若b>n-m+1，则不能检测部分占 \(2^{-(n-m)}\)。

传输协议#

滑动窗口协议工作原理：

发送的信息帧都有一个序号，从 0 到某个最大值，\(0 ~ 2n-1\)，一般用 \(n\) 个二进制位表示；
发送端始终保持一个已发送但尚未确认的帧的序号表，称为发送窗口。
发送窗口的上界表示要发送的下一个帧的序号，下界表示未得到确认的帧的最小编号。
发送窗口大小 = 上界 - 下界，大小可变；
发送端每发送一个帧，序号取上界值，上界加 1；每接收到一个正确响应帧，下界加 1；
接收端有一个接收窗口，大小固定，但不一定与发送窗口相同。
接收窗口的上界表示允许接收的序号最大的帧，下界表示希望接收的帧；
接收窗口容纳允许接收的信息帧，落在窗口外的帧均被丢弃。
序号等于下界的帧被正确接收，并产生一个响应帧，上界、下界都加 1。接收窗口大小不变。

退后 n 帧协议：

接收方从出错帧起丢弃所有后继帧；
接收窗口为 1；
对于出错率较高的信道，浪费带宽。

选择重传协议：

接收窗口大于 1，先暂存出错帧的后继帧；
只重传坏帧；
对最高序号的帧进行确认；
接收窗口较大时，需较大缓冲区。

数据链路层#

高级数据链路控制规程 HDLC：

适用范围：计算机-计算机、计算机-终端、终端-终端。
数据站：由计算机和终端组成，负责发送和接收帧；
主站：主要功能是发送命令（包括数据），接收响应，负责整个链路的控制（如系统的初始、流控、差错恢复等）；
次站：主要功能是接收命令，发送响应，配合主站完成链路的控制；
组合站：同时具有主、次站功能，既发送又接收命令和响应，并负责整个链路的控制。

链路构型：

非平衡型：点-点式（主站- 次站）、多点式（主站-多个次站），适合把智能和半智能的终端连接到计算机；
平衡型：主站-次站式（主站+次站 =逻辑通道= 主站+次站）、组合式（组合站-组合站），适合于计算机和计算机之间的连接。

基本操作模式：

正规响应模式 NRM：适用于点-点式和多点式两种非平衡构型，只有当主站向次站发出探询后，次站才能获得传输帧的许可；
异步响应模式 ARM：适用于点-点式非平衡构型和主站-次站式平衡构型，次站可以随时传输帧，不必等待主站的探询；
异步平衡模式 ABM:适用于通信双方都是组合站的平衡构型，也采用异步响应，双方具有同等能力。

点到点协议 PPP：

与 SLIP 相比，提供差错校验、支持多种协议、允许动态分配 IP 地址、支持认证；以帧为单位发送，而不是原始 IP 包；
包括两部分：链路控制协议LCP，可使用多种物理层服务：modem、HDLC 串线、SDH/SONET 等；
网络控制协议NCP，可支持多种网络层协议帧格式与HDLC 相似，区别在于 PPP 是面向字符的，采用字符填充技术，而HDLC 面向比特，其数据域可以包含任意长度的任意信息（上层协议SDU 有上限）。

局域网：

是一种将小区域内的各种通信设备互联在一起的通信网络；
特点：高数据传输率（100 ~ 1000Mbps）、短距离（0.1~10km）、低出错率（1e-8 ~ 1e-11）；
拓扑结构：星型结构、环形结构、总线形结构、树形结构；
传输介质：双绞线、基带同轴电缆、光线、无线；

信道分配

解决信道争用的协议称为介质访问控制协议 MAC，是数据链路层协议的一部分；
静态分配：频分多路复用 FDM（波分复用 WDM）、时分多路复用 TDM；
动态分配：ALOHA 协议：一对多的星形无线广播的校园网络；

纯 ALOHA 协议

用户有数据要发送时，可以直接发至信道，然后监听信道看是否产生冲突，若产生冲突，则等待一段随机的时间重发；
只要用户有数据待发，就让他们发；
无线信道为无差错信道；
在某时间间隔内如只有一个用户发送帧，中心站接收后通过另一独立信道发回应答信号ACK；
多用户共享单一信道，并由此产生冲突，这样的系统称为竞争系统；
信道效率：平均每个帧时产生 \(G\) 帧，发送一帧不受冲突影响的概率 \(P0=exp{-2G}\)，吞吐率 \(S=GP0=Gexp{-2G}\)，信道利用率最高只有 18.4%，此时 \(G=0.5\)，每个成功传送的帧的平均发送次数 \(=G/S=exp{2G}\)，平均重发次数 \(=G/S-1=exp{2G}-1\)；

分槽 ALOHA 协议

把信道时间分成离散的时间槽，槽长为一个帧所需的发送时间；
每个站点只能在时槽开始时才允许发送，其他过程与纯 ALOHA 协议相同；
信道效率：冲突危险区是纯 ALOHA 的一半，所以 \(P0=exp{-G}\)，\(S=Gexp{-G}\)，与纯 ALOHA 相比，降低了产生冲突的概率，信道利用率最高为 36.8%。

载波监听多路访问协议 CSMA

若站点有数据发送，先监听信道；若产生冲突，等待一随机时间，然后重新开始发送过程，延迟值 \(D=N(exp{G}-1)\)，其中 \(N\) 为等待时间对应的时槽数期望；
1-坚持型：若站点发现信道空闲，则发送；若信道忙，则继续监听直至发现信道空闲，然后完成发送；
非坚持型：若信道忙，等待以随机时间，然后重新开始发送过程；
p-坚持型：若站点发现信道空闲，则以概率 \(p\) 发送数据，以概率 \(q=1-p\) 延迟至下一个时槽发送。若下一个时槽仍空闲，重复此过程，直至数据发出或时槽被其他站点所占用；
若信道忙，则等待下一个时槽，重新开始发送。

带冲突检测的载波监听多路访问协议 CSMA/CD

在发送期间如果检测到冲突，立即停止发送，并发出一个瞬间干扰信号，使所有的站点都知道发生了冲突；
在发出干扰信号后，等待一段随机时间，再重复上述过程；
工作状态：传输周期、竞争周期、空闲周期，一个站点确定发生冲突，最好情况（同时发送）下要花一倍电缆传输时间，最坏情况（即将到达时发送）下要花两倍电缆传输时间。

二进制下数法

所有站的地址用等长二进制位串表示，若要占用信道，则广播该位串；
不同站发的地址的位做或操作，一旦某站了解到比本站地址高位更高的位置被置为 1，便放弃发送请求；
效率 \(d/(d+log2(N))\)。

无线局域网协议

隐藏站点问题：由于站点距离竞争者太远，从而不能发现潜在介质竞争者（\(A*BC\)，C 由于收不到 A 的数据，也可以向 B 发送数据，导致 B 接收发生冲突）；
暴露站点问题：由于非竞争者距离发送站点太近，从而导致介质非竞争者不能发送数据（\(AB*CD\)，B 向 A 发送数据，被 C 监听到，导致 C 不能向 D 发送数据）；

MACA

发送站点刺激接收站点发送应答短帧，从而使得接收站点周围的站点监听到该帧，并在一定时间内避免发送数据；
基本过程：A 向 B 发送 RTS 帧，A 周围的站点在一定时间内不发送数据，以保证 CTS 帧返回给 A；
B 向 A 回答 CTS 帧，B 周围的站点在一定时间内不发送数据，以保证 A 发送完数据；
A 开始发送；
若发生冲突，采用二进制指数后退算法等待随机时间，再重新开始。

IEEE 802.3

802.3（10M）、802.3u（100M）、802.3i（1000M）；
布线拓扑结构：总线型、脊椎型、树形、分段；
由于曼彻斯特编码的简单，所有的 802.3 基带系统都使用曼彻斯特编码；

最短帧长：

避免帧的第一个比特到达电缆的远端前帧已经发完，帧发送时间应该大于 2τ，其中 τ 为最大冲突检测时间；网络速度提高，最短帧长也应该增大或者站点间的距离要减小；最小的以太网帧是 64B，包括在帧头中的两个地址、类型/长度段和校验和，头段占 18B。

二进制指数后退算法 BEB

将冲突发生后的时间划分为长度为 51.2 微妙的时槽；
发生第一次冲突后，各个站点等待 0 或 1 个时槽再开始重传；
发生第二次冲突后，各个站点随机地选择等待 0 ~ 3 个时槽再开始重传；
第 \(i\) 次冲突后，在 0 至 \(2^{i-1}\) 间随机地选择一个等待的时槽数，再开始重传；
10 次冲突后，选择等待的时槽数固定在 0 至 1023 间；
16 次冲突后，发送失败，报告上层。

网桥

是工作在数据链路层的一种网络互连设备，它在互联的 LAN 之间实现帧的存储和转发；
工作原理：连接 k 个不同 LAN 的网桥具有 k 个 MAC 子层和 k 个物理层；
连接 802.X 和 802.Y 的网桥，互联时需要解决的相同问题：
- 不同 LAN 帧格式的转换；
- 不同 LAN 速率不同，网桥要有缓存能力；
- 高层协议的计时器设置；
- 不同 LAN 支持的最大帧长度不同，分别为 1500、8191、5000。
解决办法：丢弃无法转发的帧。

交换机

根据物理结构可分为独立式、堆叠式、模块化；
根据功能可分为智能式、直通式、存储转发式。

自适应树遍历协议

先序遍历，例如 0 ~ 15 中的素数站要发送：
2, 3, 5, 7, 11, 13;
2, 3, 5, 7;
2, 3;
idle;
2, 3;
2;
3;
5, 7;
5;
7;
11, 13;
11;
13;
共 13 个时槽。

网络层#

基本功能：

分组转发与路由选择。

基本原理：

无连接数据报分组交换

每个数据报都携带完整的目的/源地址，浪费带宽，在每次路由时过程复杂，不太容易保证服务质量，但是对于通信线路的故障，适应性很强；

虚电路分组交换

路由器需要维护虚电路的状态信息，需要在建立连接时花费时间，很容易保证服务质量 QoS，适用于实时操作，但比较脆弱。

路由算法

是网络层软件的一部分；
子网采用数据报方式，每个包都要做路由选择；
子网采用虚电路方式，只需在建立连接时做一次路由选择；
特性：正确、简单、健壮、稳定、公平、最优；
分类：非自适应算法/静态路由算法、自适应算法/动态路由算法。

最优化原则

如果路由器 J 在路由器 I 到 K 的最优路由上，那么从 J 到 K 的最优路由会落在同一路由上。

汇集树

从所有的源节点到一个给定的目的节点的最优路由的集合形成了一个以目的节点为根的树，路由算法的目的是找出并使用汇集树。

最短路径路由算法

构建子网的拓扑图，图中的每个节点代表一个路由器，每条弧代表一条通信线路，为了选择两个路由器之间的路由，算法在图中找出最短路径（节点数量、地理距离、传输延迟、多参数加权函数）。

洪泛算法

把收到的每一个包，向除了该包到来的线路外的所有输出线路发送；
主要问题：洪泛要产生大量重复包；
解决措施：
- 每个包头包含站点计数器，每经过一站计数器减 1，为 0 时则丢弃该包；
- 记录包经过的路径。

选择性洪泛算法

将进来的每个包仅发送到与正确方向接近的线路上。

距离向量路由算法

属于动态路由算法，每个路由器维护一张表，表中给出了到每个目的地的已知最佳距离和线路，
并通过相邻路由器交换信息来更新表（定期）；
以子网中其他路由器为表的索引，表项包括两部分：到达目的地节点的最佳输出线路，和到达目的节点所需时间或距离；
每隔一段时间，路由器向所有邻居节点发送它到每个目的节点的距离表，同时它也接收每个邻居节点发来的距离表；
邻居节点 \(X\) 发来的表中， \(X\) 到路由器 \(i\) 的距离为 \(X_i\)，本路由器到 \(X\) 的距离为 \(m\)，则路由器经过 \(X\) 到 \(i\) 的距离为 \(X_i+m\)，根据不同邻居发来的信息，计算其最小值，更新本路由器的路由表；
本路由器中的老路由表在计算中不被使用（要看情况）。

链路状态路由算法

发现邻居节点，并学习它们的网络地址：路由器启动后，通过发送 HELLO 包发现邻居节点；
两个或多个路由器连载一个 LAN 时，引入人工节点；
测量到每个邻居节点的延迟或开销（echo 时间/2）；
将所有学习到的内容封装成一个包：包衣发送方的标识符开头，后面是序号、年龄和一个邻居节点列表；
列表中对应每个邻居节点，都有发送方到它们的延迟或开销；
链路状态包定期创建或发生重大事件时创建；
将这个包发送给所有其他路由器：洪泛链路状态包；
计算到每个其他路由器的最短路径。

反向路径转发 RPF

用于组播：在所有接口上转发分组，除了在反向网络源端最短路径的接口上；
BFS 建树，分支结点画圈。

IP 地址分类

A 类地址 0[Network7][Host24]
B 类地址 10[Network14][Host16]
C 类地址 110[Network21][Host8]
D 类地址 1110[Multicast address28]
E 类地址 11110[Reserved for future use27]。

IP 地址全 0 表示本网络或本主机，全 1 表示广播地址。

地址解析协议 ARP

解决网络层 IP 地址与数据链路层 MAC 地址的映射问题；
工作流程：发送节点已知接收节点逻辑地址；
发送结点广播 ARP 查询分组（发送结点逻辑地址、物理地址，接收节点逻辑地址，查询接收节点物理地址）；
接收节点单播返回 ARP 相应分组。

RIP 协议

距离向量算法。

内部网关路由协议，开放最短路径优先 OSPF

根据实际的网络、路由器和线路构造有向拓扑图；
每个弧赋一个开销值。
建立 TCP 连接：SYN1, ACK0; RST1 / SYN1, ACK1; SYN0, ACK1.
单向的连接释放：FIN1 并启动定时器，在收到确认或无确认超时后关闭连接。
SYN 段不携带任何数据，但它要消耗一个序号；
SYN+ACK 段不携带任何数据，但它要消耗一个序号；
ACK 段如果不携带数据就不消耗序号；
释放连接 FIN 消耗序号与 SYN 相同。

TCP 拥塞控制

快网络小缓存接收者，在连接建立时声明最大可接受段长度，利用可变滑动窗口协议防止出现拥塞；
慢网络大缓存接收者，发送方维护两个窗口：可变发送窗口和拥塞窗口，按两个窗口的最小值发送，拥塞窗口按照慢启动算法和拥塞避免算法变化。

慢启动算法

连接建立时拥塞窗口初始值为该连接允许的最大段长，阈值为 64K；
发出一个最大段长的 TCP 段，若正确确认，拥塞窗口变为两个最大段长；
发出（拥塞窗口/最大段长）个最大长度的 TCP 段，若都得到确认，则拥塞窗口加倍；
重复上一步，直至发生丢包超时事件，或拥塞窗口大于阈值。

拥塞避免算法

若拥塞窗口大于阈值，从此时开始，拥塞窗口线形增长，一个 RTT 周期增加一个最大段长，直至发生丢包超时事件；
当超时事件发生后，阈值设置为当前拥塞窗口大小的一半，拥塞窗口重新设置为一个最大段长；
执行慢启动算法。

性能指标#

速率

也称数据率，或数据传输率，或比特率。连接在计算机网络上的主机在数字信道上传输数据位数的速率。单位是 b/s、kb/s、Mb/s、Gb/s、Tb/s。

带宽

原本指某个信号具有的频带宽度，即最高频率与最低频率之差，单位是赫兹（Hz）。计算机网络中的带宽，用来表示网络的通信线路传输数据的能力，通常是指单位时间内从网络中的某一点到另一个点所能通过的 “最高数据率”。单位是 “比特每秒”，b/s，kb/s，Mb/s，Gb/s。

吞吐量

表示单位时间内通过某个网络（或信道、接口）的数据量。单位是 b/s，kb/s，Mb/s 等。吞吐量受网络的带宽或网络的额定速率的限制。

注意到，速率、带宽和吞吐量具有相同的单位。区别在于，一个是实时速率，一个是最高速率，一个是同一信道上实时速率的加总。如下图所示：

时延

指数据（报文/分组/比特流）从网络（或链路）的一端传送到另一端所需的时间。也叫延迟或迟延。单位是 s。

时延带宽积

又称为以比特为单位的链路长度，即某段链路现在有多少比特（表示的是容量）。单位是 bit。时延带宽积 = 传播时延 × 带宽。

往返时延 RTT

指从发送方发送数据开始，到发送方收到接收方的确认（接收方收到数据后立即发送确认），总共经历的时延。RTT 包括往返传播时延（传播时延 * 2）和末端处理时间。

加权平均往返时间 RTTs

\(RTTs=(1-\alpha)(旧的 RTTs)+\alpha(新的 RTT)\)。

超时重传时间 RTO

\(RTO=RTTs+4RTTd\)

\(新的 RTTd=(1-\beta)(旧的RTTd)+\beta \times abs(RTTs-新的RTT)\)

\(\alpha=0.125, \beta=0.25\)

修正的 Karn 算法：

报文段每重传一次， \(新的 RTO=\gamma(旧的 RTO), \gamma=2\)

UDP 头格式：

源端口、目的端口、UDP 长度、UDP 校验和。

利用率

可以细分为信道利用率和网络利用率。
信道利用率 = 有数据通过的时间 / (有 + 无) 数据通过的时间。
网络利用率 = 信道利用率的加权平均值。