计算机网络

评分

课程作业 20%
实验 20%
小测 5%
出勤 5%
期末闭卷 50%

概述

网络、互联网与因特网

网络 Network 是由若干节点 Node 和连接这些节点的链路 Link 组成的。节点可以是各种设备，链路可以是有线的，也可以是无线的。
互联网 internet 是由若干网络和连接这些网络的路由器组成的，即网络的网络。
因特网 Internet 是世界上最大的互联网。

internet 泛指由多个计算机网络互连而成的网络，这些网络之间可以使用任意的通信协议作为通信规则。

Internet 专指世界上最大的互联网，这些网络之间必须使用 TCP/IP 协议族作为通信规则。

因特网已发展成为基于因特网服务提供者 ISP 的多层次结构的互联网络。任何用户都可以通过 ISP 接入因特网。

alt text

制定因特网标准的过程为“因特网草案”->“建议标准”->“因特网标准”。任何一个建议标准在成为因特网标准之前，都以 RFC(Request For Comments)的形式在因特网上发表。

在功能上，因特网可以简单地划分成核心部分和边缘部分。

alt text

互联网的核心部分由大量异构型网络和连接这些网络的路由器构成，为边缘部分提供连通性和数据交换等服务。

电路交换、分组交换和报文交换

路由器 Router 对收到的分组进行存储转发来实现分组交换。

电路交换 Circuit Switching

电路交换的三个步骤：

建立连接。从主叫方到被叫方（中间可能有多层中继）建立一条专用的物理通路，简称为连接。
通话：主叫方和被叫方通话，始终占用连接。
释放连接：通话完毕，交换机释放通信资源。

alt text

计算机之间的数据传送并不适合使用电路交换的方式。因为计算机在线的大部分时间其实并没有进行数据传输，大部分通信资源都会被浪费。

分组交换

分组交换：源主机将待发送的整块数据构造成若干分组发送出去，中途各交换节点（路由器）对分组进行存储转发，目的主机收到这些分组后将它们组合还原成原始数据块。

待发送的整块数据被成为报文 Message。报文被划分成多个数据段进行传输，每隔数据段前面添加一些必要的控制信息（如源地址，目的地址）组成的首部 Header，这就形成了一个个分组 Packet。分组是分组交换网上数据传送的单元。

alt text

源主机将分组发送到分组交换网中，分组交换网中的分组交换机收到一个分组后，先将其缓存，然后从其首部提取目的地址，并根据地址查找自己的转发表，找到相应转发接口后转发出去，把分组交给下一个分组交换机。

值得注意的是，与电路交换占用一整条连接不同，分组交换只会占据分组所在的一小段线路，而不会占有整条线路，这提高了通信线路的利用率。

不过，分组交换也带来一些问题：

分组首部的额外传输开销
路由器存储转发造成一定时延
分组可能出现失序与丢失问题

报文交换

报文交换是分组交换的前身。报文交换没有分组操作，报文直接被整个发送，这导致交换节点把报文整体接收完成后才能查找转发表，提升了转发时延。同时，对交换节点的缓存空间要求也更高。

如果传送大量数据，且数据传送时间远长于建立连接的时间，电路交换效率较高。而处理突发数据时，分组交换更灵活。

计算机网络的定义和分类

定义

计算机网络没有精确和统一的定义，不同阶段有不同定义。

一个较好的定义是：计算机网络主要是由一些通用的、可编程的硬件互连而成的。这些硬件能够用来传送多种不同类型的数据，并能支持广泛的和日益增长的应用。

计算机网络的性能指标

速率

速率指数据的传送速率，也称为数据率 Data Rate 或比特率 Bit Rate，基本单位为 bit/s。

需要注意的是，数据量的计算是基于 2 进制的，但是速率的单位却是基于 10 进制的。如：

1KB= $2^{10}$ B
1kb/s= $10^3$ b/s

带宽 Bandwidth

带宽表示单位时间内从网络中的某一点到另一点所能通过的最高数据率。因此，带宽的单位与速率单位相同。

线路的带宽越宽，其所传输的数据的最高数据率就越高。应用中，设备的接口速率和线路带宽遵循木桶效应。

alt text

吞吐量 throughput

吞吐量指单位时间内通过某个网络或接口的实际数据量。它常被用于对实际网络的测量。

吞吐量收到带宽的限制。

alt text

时延 delay/latency

时延指数据（由多个分组组成）从网络的一段传送到另一端所耗费的时间，也称为延迟或迟延。网络中的时延由发送时延、传播时延、排队时延和处理时延这四部分组成。

alt text

如图，主机 A 发送一个分组到主机 B，经过了两个发送时延，两个传播时延，一个排队时延和一个处理时延。

发送时延

发送时延是主机或路由器发送分组所耗费的时间：

\text{发送时延}=\frac{\text{分组长度}}{\text{发送速率}}

传播时延

传播时延是电磁波在链路上传播一定的距离所耗费的时间：

\text{传播时延}=\frac{\text{链路长度}}{\text{电磁波在链路上的传播速率}}

电磁波在链路上的传播速率主要有如下三种：

自由空间： $3\times 10^8$ m/s
铜线电缆： $2.3\times 10^8$ m/s
光纤： $2\times 10^8$ m/s

排队时延

分组进入路由器后，会在路由器的输入队列中排队缓存并等待处理。
在路由器确定了分组的转发接口后，分组会在输出队列中排队缓存并等待转发。

分组在输入队列和输出队列中排队缓存所耗费的时间就是排队时延。

处理时延

路由器从自己的输入队列中取出分组后，会进行一系列处理工作，这些工作的耗费时间就是处理时延。

alt text

排队时延和处理时延往往难以计算。上图展示了不考虑排队时延和处理时延的情况下，网络时延的组成。此时，若源主机通过 $n$ 个路由器转发，给目的主机发送 $m$ 个分组，则总时延为

m\cdot\text{主机发送单个分组的时延}+(n+1)\cdot\text{传送时延}+n\cdot\text{转发单个分组的时延}

发送时延和传播时延较容易计算，排队时延和处理时延则不容易计算。当发送数据块较大时，发送时延会成为主导；反之，当传送距离较长、信号传播速率较低时，传播时延会成为主导。

时延带宽积

时延带宽积是传播时延和带宽的乘积：

\text{时延带宽积}=\text{传播时延}\times\text{带宽}

我们可以直观地把时延带宽积理解成链路可以容纳的比特数量。

如果发送端连续发送数据，那么在发送的第一个比特到达线路另一端时，发送端已经发送了时延带宽积个比特，且这些比特正在链路上跑。因此，链路的时延带宽积也被称为以比特为单位的链路长度。

往返时间 Round-Trip Time

RTT 指从发送端发送数据分组开始，到发送端收到接收端发来的相应确认分组为止，总共耗费的时间。

ping 命令就是通过往返时间来反映网站的连通性的。

利用率

链路利用率是指某条链路有百分之几的时间是被利用的（即有数据通过）。
网络利用率是指网络中所有链路的链路利用率的加权平均。

当链路空闲时，该链路引起的排队时延为 0，此时链路时延最小。当链路的利用率增大时，链路引起的时延就会迅速增加。

令 $D_0$ 表示网络空闲时的时延， $D$ 表示网络当前的时延， $U$ 表示网络利用率，那么在理想的假定条件下，有：

D=\frac{D_0}{1-U}

可见，网络利用率增加时，时延会急剧增大。因此，一些大型 ISP 往往会控制信道利用率不超过 50%。如果超过了就要进行扩容，增大线路的带宽。

丢包率

丢包率是指在一定的时间范围内，传输过程中丢失的分组数量与总分组数量的比率。

分组丢失主要有以下两种情况：

分组在传输过程中出现误码，被传输路径中的节点交换机（例如路由器）或目的主机检测出误码而丢弃。
节点交换机根据丢弃策略主动丢弃分组。

丢包率可以反映网络的拥塞情况。丢包率越高，拥塞情况越严重。

计算机网络体系结构

常见的三种计算机网络体系结构

alt text

OSI 标准由于协议实现过分复杂、运行效率低，部分功能在多个层次中重复出现，最终失败。

alt text

计算机网络体系结构分层的必要性

计算机网络很复杂，分层可以把大问题转化成小问题。

在物理层，我们考虑：

用什么传输媒体
用什么物理接口
用什么信号表示比特 0 和 1

在数据链路层，我们考虑：

如何标识网络中各主机（主机编址，如 MAC 地址）
如何从比特流中区分出地址和数据（数据封装格式）
协调各主机争用总线（媒体接入控制）
以太网交换机的实现（自学习和转发帧）
检测数据是否误码（差错检测）
出现传输差错如何处理（可靠传输和不可靠传输）
接收方控制发送方注入网络的数据量（流量控制）

在网络层，我们考虑：

标识网络和网络中的各主机（网络和主机共同编址，例如 IP 地址）
路由器转发分组（路由选择协议、路由表和转发表）

在运输层，我们考虑：

进程之间基于网络的通信（进程的标识，例如端口号）
出现传输差错如何处理（可靠传输和不可靠传输）

在应用层，我们考虑：

通过应用进程间的交互来完成特定的网络应用
进行会话管理和数据表示

总结如下：

应用层	运输层	网络层	数据链路层	物理层
解决通过应用进程的交互来实现特定网络应用的问题	解决进程之间基于网络的通信问题	解决数据包在多个网络之间传输和路由的问题	解决数据包在一个网络或一段链路上传输的问题	解决使用何种信号来表示比特 0 和 1 的问题

计算机网络体系结构分层思想举例

浏览器：

应用层：生成 http 请求报文，请求 Web 服务器执行相应操作
运输层：添加 TCP 报文段，区分应用进程，实现可靠传输
网络层：添加 IP 数据报，用于 IP 寻址和路由
链路层：在首尾包裹以太网帧，用于 MAC 寻址和帧校验
物理层：将上述内容转换成电信号

路由：

物理层：解析电信号链路层：拆解以太网帧网络层：根据 IP 数据包首部中的目的 IP 地址查表转发该 IP 数据报

然后路由又反序执行操作，将原电信号发向 Web 服务器。

Web 服务器类似逐层操作，获得浏览器所请求的内容。

计算机网络体系结构中的专用术语

实体

实体指任何可发送或接收信息的硬件或软件进程，对等实体则指通信双方相同层次中的实体。

协议

协议是控制两个对等实体在“水平方向”进行“逻辑通信”的规则的集合。

协议的三要素：

语法定义所交换信息的格式
语义定义通信双方所要完成的操作
同步定义通信双方的时序关系

服务

如果说，协议是水平的，那么服务就是垂直的。在协议的控制下，两个对等实体在水平方向的逻辑通信使本层向上一层提供服务，从而允许上一层能够实现协议。

下层的协议对上层的实体是透明的。实体可以接受下层服务，但不知道实现这个服务的具体协议。

在同一系统中，相邻两层的实体交换信息的逻辑接口称为服务访问点 SAP Service Access Point。

如，帧的“类型”字段、IP 数据报的“协议”字段，TCP 报文段或 UDP 用户数据报的“端口号”字段都是 SAP。

上层要使用下层提供的服务，必须通过与下层交换一些命令，这些命令称为服务原语。

对等层次之间传送的数据包称为该层的协议数据单元（Protocol Data Unit，PDU）。
同一系统内层与层之间交换的数据包称为服务数据单元（Service Data Unit，SDU）。

物理层

物理层用于提供比特流传输服务。

alt text

传输媒体

物理层下面有传输媒体（传输媒体不属于物理层，从而不属于计算机网络体系结构）。传输媒体是计算机网络设备之间的物理通路，也称为传输介质或传输媒介。

传输媒体被分为导向型传输媒体和非导向型传输媒体。

导向性传输媒体

同轴电缆

双绞线

光纤

非导向型传输媒体

无线电波、微波、红外线、激光、可见光

传输方式

串行传输和并行传输

对于串行传输，发送端和接收端之间只有一条数据传输通路，并行传输则有多条。并行传输所使用的数据传输线路的数量，被称为数据总线宽度，常用的 8 位，16 位，32 位，64 位。

由于并行传输成本较高，往往用于短距离传输。

alt text

同步传输和异步传输

同步传输以比特为传输单位。同步传输时，字节之间没有间隔，没有起始位和终止位。这要求收发双方对表示比特的信号的时间长度达成一致，即同步。如果收发双方的时钟频率不严格同步，就会产生采样时刻的误差积累，最终导致接收方对比特信号的误判。

alt text

异步传输以字节为传输单位。异步传输时，字节之间的时间间隔并不固定，接收端只在每个字节的起始处对字节内的比特实现同步。因此，一般要给每个字节添加起始位和结束位。即：字节之间异步，字节之内同步。

单向，双向交替和双向同时通信

单向通信：只能有一个方向，又叫单工通信。
双向交替通信：通信双方都可以发送信息和接收信息，但对于任何一方，发送信息和接收信息不能同时进行，又叫半双工通信。
双向同时通信：通信双方都可以同时发送信息和接收信息，又称为全双工通信。

编码与调制

基本概念

消息 message；需要由计算机处理和传输的文字、图片、音频等内容。
数据 data：运送消息的实体，对于计算机而言，即二进制数据。
信号 signal：数据的电磁表现。
基带信号：由信源发出的原始信号称为基带信号（基本频带信号）。基带信号需要进行调制 modulation 后才能在信道上传输。
基带调制：对数字基带信号的波形进行变换，使其能与信道特性相适应。基带调制是把数字信号转换成另一种形式的数字信号，因此也被称为编码 coding。
带通调制：将数字基带信号的频率范围搬移到较高的频段，并转换为模拟信号，使其能在模拟信道中传输。
码元：信号的编码单元。对于模拟信号，载波参数（振幅、频率、初相位）的变化就是一个码元。对于数字信号，一个数字脉冲就是一个码元。

alt text

常用编码方式

不归零制：信号在每个码元期间不会回归到零电平。
归零制：信号在每个码元期间会回归到零电平。
曼彻斯特编码：每个码元的中间时刻发生跳变。电平的跳变表示数据。10Mb/s 的传统以太网采用的是曼彻斯特编码。
差分曼彻斯特编码：电平的跳变仅表示时钟信号，不表示数据。数据的表示在于每个码元开始处是否有电平跳变。无跳变表示 1，有跳变表示 0。

alt text

跳变越少，编码效率越高。不归零制编码效率最高，但是存在同步问题。归零制中，大部分的数据带宽都因“归零”浪费掉了。但是，它相当于将时钟信号编码在了数据内，从而避免了同步问题。所以，采用了归零编码的信号被称为自同步信号。曼彻斯特编码和差分曼彻斯特编码信号都是自同步信号。

alt text

基本的带通调制方法

Recall：带通调制：将数字基带信号的频率范围搬移到较高的频段，并转换为模拟信号，使其能在模拟信道中传输。

alt text

调幅 Amplitude Modulation,AM

调幅让载波的振幅随基带数字信号的变化而变化。

调频 Frequency Modulation,FM

调频让载波的频率随基带数字信号的变化而变化。

调相 Phase Modulation,PM

调相让载波的初相位随基带数字信号的变化而变化。

混合调制方法

为了提高数据传输效率，可以使用混合调制，使一个码元可以表示多个比特的信息量。

由于频率和相位相关，所以频率和相位不能混合调制。

正交振幅调制 Quadrature Amplitude Modulation 是一个相位和振幅结合起来调制的例子：

alt text

QAM-16 可以调制出 16 中不同码元，所以每个码元的信息量是 4 个比特( $2^4=16$ )。

信道的极限容量

信号在信道上传输时不可避免地产生失真。

码元传输速率越高……
信号传输距离越远……
噪声干扰越大……
传输媒体的质量越差……

奈氏准则

每种信道能通过信号的频率范围是有限的。

信道上传输的数字信号可以看作多个频率的模拟信号进行多次叠加后形成的方波。

alt text

总而言之，模拟信号在模拟信道传输时，受模拟信道频率带宽的限制。数字信号在数字信道传输时，信号中的许多高频分量往往不能通过信道。

如果数字信号中的高频分量失真严重，接收端接收到的波形前沿和后沿就不那么陡峭，每个码元的时间界限就不明确了，这种现象被称为码间串扰。信号的频率带宽越宽，能通过的信号的高频分量就越多，那么码元的传输速率就可以更高。

奈氏准则给出了理想低通信道的最高码元传输速率的计算公式：

\text{理想低通信道的最高码元传输速率}=2 \text{W Baud}

W 是理想低通信道的频率带宽，单位为 Hz；Baud（波特）是码元传输速率的单元，即码元/秒。

一个实际信道所能传输的最高码元效率，要明显低于奈氏准则给出的上限。

香农公式

奈氏准则提出，信道的码元传输速率存在上限。我们于是很容易想到，能不能通过提高每个码元携带比特的数量来提高信息传输效率？然而，信息的传输效率并不能无限制地提高。因为，实际的信道中存在噪声，这会影响接收端对码元的识别，且噪声功率相对信号功率越大，影响越大。

香农公式指出了频率带宽受限、存在高斯白噪声干扰的信道的极限信息传输速率：

C=W \log_{2}\left(1+\frac{S}{N}\right)(\text{b/s})

$C$ ：信道的极限信息传输效率，单位为 b/s
$W$ ：信道的频率带宽，单位为 Hz
$S$ ：信道内传输信号的平均功率
$N$ ：信道内的高斯噪声功率
信噪比： $10 \log_{10}\left(\frac{S}{N}\right)$ ，单位为 dB。

实际信道中能够达到的信息传输速率要比香农公式给出的极限信息传输速率低不少。

信道复用 Multiplexing 技术

复用，即在一条传输媒体上同时传输多路用户的信号。当一条传输媒体的传输容量大于多条信道传输的总容量时，就可以使用复用技术，以充分利用传输媒体的带宽。

alt text

在发送端需要一个复用器，让多个用户通过复用器使用一个大容量共享信道进行通信。
在接收端需要使用一个分用器，将共享信道中传输的信息分别发送给相应的用户。

接下来介绍常用的信道复用技术。

频分复用 Frequency Division Multiplexing(FDM)

频分复用是将传输媒体的总频带划分成多个子频带，每个频带作为一个通信的子信道。

alt text

时分复用 Time Division Multiplexing(TDM)

时分复用是将时间划分为一段段等长的时隙，每个用户在相应时隙内独占传输媒体的资源进行通信。

时分复用各用户对应的时隙构成了时分复用帧 TDM 帧。每个用户的时隙的周期即 TDM 帧长度。

alt text

由于计算机数据发送有突发性，每个用户对分配到的 TDM 帧中时隙的利用率并不高。为此，有方法统计时分复用 Statistic TDM(STDM) 做了改进。

波分复用 Wavelength Division Multiplexing(WDM)

波分复用是光的频分复用。

alt text

码分复用 Code Division Multiplexing(CDM)

码分复用也常称为码分多址 Code Division Multiple Access(CDMA)。CDM 发送的信号有很强的抗干扰能力，每个用户可以在相同的时间使用相同的频带进行通信。

CDM 将每个比特时间划分为 $m$ （往往为 64 或 128）个更短的时间片，即码片 Chip。每个站点被指派一个唯一的 $m$ 比特的码片序列 Chip Sequence。每当站点发送比特 1，就改为发送这个序列；若要发送比特 0，就发送这个序列的反码。

为了能够从信道中分离出每个站的信号，我们需要定义正交的概念。以一个 8 比特的码片序列 01011001 为例，我们记它的码片向量为 $(-1,1,-1,1,1,-1,1)$ 。如果两个码片序列的码片向量规格化内积为 0，就称这两个序列正交。

需要注意，规格化内积的概念相比常规内积添加了一个尺寸系数：

A\cdot B = \frac{1}{m}\sum_{i=1}^{m}A_iB_i

我们可以很简单地得到：

\left\{ \begin{align*} A\cdot B &= - A \cdot \bar{B}\\ A\cdot A &= 1\\ A\cdot \bar{A} &= -1 \end{align*} \right.

如此，每个站接收时，可以用自己的码片序列和复合信号做规格化内积：

结果为 1，说明收到比特 1
结果为 -1，说明收到比特 0
结果为 0，说明没有信号

alt text

数据链路层

概述

数据链路层的主要任务是实现帧在一段链路上或一个网络中进行传输的问题。

链路 Link 指从一个节点到相邻节点的一段物理线路，中间没有任何交换节点。
数据链路 Data Link 基于链路。当在链路上传送数据时，除了需要链路本身还需要一些必要的通信协议来控制这些数据的传输。把实现这些协议的硬件和软件（eg.网络适配器(即网课)和相应的软件驱动程序）加到链路上，就构成了数据链路。
帧 Frame 是数据链路层对等实体之间在水平方向进行逻辑通信的协议数据单元 PDU。

数据链路层的三个重要问题

封装成帧 framing 和透明传输

封装成帧就是给网络层交付下来的分组添加首部和尾部。

alt text

帧首部中往往包含帧开始符、帧的源地址和目的地址。
帧尾部中往往包含帧检验序列和帧结束符。
帧的数据载荷长度上限为 Maximum Transfer Unit(MTU)。以太网的 MTU 为 1500 个字节。不同数据链路层协议对此有不同规定。

透明传输要求数据链路层对 PDU 的内容不要做限制。如，PDU 中依旧可以包含帧的定界符。实现透明传输的方法一般为字节填充或比特填充。

字节填充：转义字符法。

alt text

比特填充：

alt text

以太网的数据链路层没有使用字符填充或比特填充法。这是因为以太网帧的首部和尾部中压根没有帧定界符。物理层会在以太网帧前添加 8 字节的前导码，表明后面紧跟的就是以太网帧。另外，以太网还有帧间间隔时间为 96 比特的发送时间。

差错检测

某段时间内，出现传输错误的比特数量占这段时间内传输比特总数量的比例称为误码率 Bit Error Rate(BER)。

帧尾部中，有字段帧检测序列 Frame Check Sequence(FCS)，用于存放检错码。在数据链路层，接收方从帧尾部取出检错码，采用和发送方相同的检错技术来检测帧在传输过程中是否出现误码。

奇校验：待发送的数据后添加一个校验位，使整个数据中 1 的个数是奇数。
偶校验：待发送的数据后添加一个校验位，使整个数据中 1 的个数是偶数。
循环冗余校验 Cyclic Redundancy Check(CRC)：见下图。

alt text

循环冗余检验具体操作如下：

通过生成多项式的各项系数得到除数。如 $X^3+X+1$ 生成 1010。
在待发送数据后面追加生成多项式最高次数个 0。
整个数据（包含追加的 0）做二进制除法（逐次按位异或即可）。

alt text

将追加的 0 替换成余数。
接收方就把这段数据也同样除一除，如果余数为 0 就说明没问题。

循环冗余检测检错能力较好，且易于用硬件实现，所以被广泛应用于数据链路层。

可靠传输

数据链路层提供的服务类型有两种；

不可靠传输服务：接收方的数据链路层直接丢弃有误码的帧。
可靠传输服务：数据链路层需要用某种机制实现发送方发送什么，接收方就能收到什么。

事实上，可靠传输服务并不局限于数据链路层，其上各层都可以选择实现可靠传输服务。因此，本小节中将数据传送单元从帧改为更广泛的分组。

下面介绍几个实现可靠传输的机制。

停止-等待 Stop-and-Wait 协议

发送方每发送完一个数据分组就必须停下来，等待接收方发来的确认 Acknowledgement(ACK)或否认 Negative Acknowledgement(NAK)分组。

如果发送方发送的数据分组丢失了，那等待方一直不返回，那发送方就会陷入永远等待的状态。因此，发送方应该每发送完一个数据分组，就启动一个超时计时器。如果超过了超时重传时间 Retransmission Time-Out(RTO)，发送方就重新发一下数据分组。这就是超时重传。

但是还有个问题：如果不是发送方发送的数据分组丢失了，而是接收方返回的数据分组丢失了，那么实际上接收方还是接受到了数据。如果发送方由于超时重传又传了一段相同的数据，但是接收方不知道这是相同的数据，就会发生重复接收的错误。因此，发送方还应该额外添加一个轮换的比特编号。每发送一个不同的数据分组，就将这个编号进行一次轮换。这样，接收方就能识别出是不是发生了重复传输，从而避免了重复接收。

alt text

假设忽略处理时间，记

\left\{ \begin{align*} T_D&=数据分组的发送时延\\ T_A&=确认分组的发送时延\\ RTT&=收发双方的往返时间 \end{align*} \right.

那么停止-等待协议的信道利用率可以近似计算（忽略超时重传）为

U=\frac{T_D}{T_D+RTT+T_A}

因此，如果数据分组发送时延较小，但是往返时间较大（如卫星链路），就不适合使用停止-等待协议。如果往返时间远小于数据分组的发送时延（如无线局域网），停止-等待协议就还算不错。

回退 N 帧协议 Go-back-N(GBN)

GBN 协议采用流水线传输方式，并使用发送窗口来限制发送方连续发送数据分组的数量。