计算机网络

1.1 计算机网络在信息时代的作用

计算机网络已由一种通信基础设施发展成为一种重要的信息服务基础设施。
计算机网络已经像水、电、煤气这些基础设施一样，成为我们生活中不可或缺的一部分。

1.2 因特网概述

网络、互连网（互联网）和因特网

网络（Network）由若干**结点（Node）和连接这些结点的链路（Link）**组成。
多个网络还可以通过路由器互连起来，这样就构成了一个覆盖范围更大的网络，即互联网（或互连网）。因此，互联网是“网络的网络（Network of Networks）”。
因特网（Internet）是世界上最大的互连网络（用户数以亿计，互连的网络数以百万计）。

internet（互联网或互连网）是一个通用名词，它泛指由多个计算机网络互连而成的网络。在这些网络之间的通信协议可以是任意的。

Internet（因特网）则是一个专用名词，它指当前全球最大的、开放的、由众多网络相互连接而成的特定计算机网络，它采用TCP/IP协议簇作为通信的规则，其前身是美国的ARPANET。

因特网发展的三个阶段

从单个网络ARPANET向互联网发展
- 1969年，第一个分组交换网ARPANET；
- 70年代中期，研究多种网络之间的互连；
- 1983年，TCP/IP协议成为ARPANET的标准协议（因特网诞生时间）
逐步建成三级结构的因特网
- 1985年，NSF围绕六个大型计算机中心建设NSFNET（主干网、地区网和校园网）；
- 1990年，ARPANET任务完成，正式关闭；
- 1991年，美国政府将因特网主干网交给私人公司经营，并开始对接入因特网的单位收费；
逐步形成了多层次ISP结构的因特网
- 1993年，NSFNET逐渐被若干个商用因特网主干网替代；政府机构不再负责因特网运营，让各种因特网服务提供者ISP来运营。
- 1994年，万维网WWW技术促使因特网迅猛发展；
- 1995年，NSFNET停止运作，因特网彻底商业化。

因特网的组成

边缘部分
- 由所有连接在因特网上的主机组成。这部分是用户直接使用的，用来进行通信（传送数据、音频或视频）和资源共享。
核心部分
- 核心部分由大量网络和连接这些网络的路由器组成。这部分是为边缘部分提供服务的（提供连通性和交换）。

1.3 三种交换方式

电路交换

电话交换机接通电话线的方式称为电路交换；
从通信资源的分配角度来看，交换（Switching）就是按照某种方式动态地分配传输线路的资源；
电路交换的三个步骤：
1. 建立连接（分配通信资源）
2. 通话（一直占用通信资源）
3. 释放连接（归还通信资源）
当使用电路交换来传送计算机数据时，其线路的传输效率往往很低。

分组交换

通常我们把表示消息的整块数据称为一个报文，在发送报文之前，先把较长的报文划分成为一个个更小的等长数据段。在每一个数据段前面，加上一些由必要的控制信息组成的首部后，就构成了一个分组，也可简称为“包”，相应地，首部也可叫作“包头”。
分组交换机收到一个分组后，先将分组暂时存储下来，再检查其首部，按照首部中的目的地址进行查表转发，找到合适的转发接口，通过该接口将分组转发给下一个分组交换机。各分组经过途中各分组交换机的存储转发，最终达到目标主机。
目标主机收到这些分组后，去掉它们的首部，将各数据段组合还原出原始报文。

电路交换、报文交换、分组交换的对比

电路交换

优点	缺点
通信时延小	建立连接时间长
有序传输	线路独占，使用效率低
没有冲突	灵活性差
适用范围广	难以规范化
实时性强
控制简单

报文交换

优点	缺点
无需建立连接	引起了转发时延
动态分配线路	需要较大存储缓存空间
提高线路可靠性	需要传输额外的信息量
提高线路利用率
提供多目标服务

分组交换

优点	缺点
无需建立连接	引起了转发时延
线路利用率高	需要传输额外的信息量
简化了存储管理	对于数据报服务，存在失序、丢失或重复分组的问题；对于虚电路服务，存在呼叫建立、数据传输和虚电路释放三个过程
加速传输
减少出错概率和重发数据量

1.4 计算机网络的定义和分类

计算机网络的定义

计算机网络的精确定义并未统一
计算机网络的最简单的定义是：一些互相连接的、自治的计算机的集合。
- 互连是指计算机之间可以通过有线或无线的方式进行数据通信；
- 自治是指独立的计算机，它有自己的硬件和软件，可以单独运行使用；
- 集合是指至少需要两台计算机；
计算机网络的较好的定义是：计算机网络主要是由一些通用的、可编程的硬件互连而成的，而这些硬件并非专门用来实现某一特定目的（例如，传送数据或视频信号）。这些可编程的硬件能够用来传送多种不同类型的数据，并能支持广泛的和日益增长的应用。

计算机网络的分类

分类方式
按交换技术分类	电路交换网络、报文交换网络、分组交换网络
按使用者分类	公用网、专用网
按传输介质分类	有线网络、无线网络
按覆盖范围分类	广域网WAN、城域网MAN、局域网LAN、个域网PAN
按覆盖范围分类	总线型网络、星型网络、环型网络、网状型网络

1.5 计算机网络的性能指标

速率

计算机中数据量的单位，也是信息论中信息量的单位。一个比特就是二进制数字中的一个1或0。
常用数据量单位：

$8 bit = 1 Byte$

$KB = 2^{10} B$

$MB = K·KB = 2^{10}·2^{10} B = 2^{20} B$

$GB = K·MB = 2^{10}·2^{20} B = 2^{30} B$

$TB = K·GB = 2^{10}·2^{30} B = 2^{40} B$

连接在计算机网络上的主机在数字信道上传送比特的速率，也称为比特率或数据率。
常用数据率单位：

bit/s (b/s, bps)

$k b/s = 10^3 b/s$ (bps)

$M b/s = k \cdot k b/s = 10^3 \cdot 10^3 b/s = 10^6 b/s$ (bps)

$G b/s = k \cdot M b/s = 10^3 \cdot 10^6 b/s = 10^9 b/s$ (bps)

$T b/s = k \cdot G b/s = 10^3 \cdot 10^9 b/s = 10^{12} b/s$ (bps)

带宽

用来表示网络的通信线路所能传送数据的能力，因此网络带宽表示在单位时间内从网络中的某一点到另一点所能通过的“最高数据率”；
单位：b/s（kb/s, Mb/s, Gb/s, Tb/s）和速率相同

吞吐量

吞吐量表示在单位时间内通过某个网络（或信道、接口）的数据量。
吞吐量被经常用于对现实世界中的网络的一种测量，以便知道实际上到底有多少数据量能够通过网络。
吞吐量受网络的带宽或额定速率的限制。

时延

时延带宽积

$时延带宽积 = 传播时延 \times 带宽 $
若发送端连续发送数据，则在所发送的第一个比特即将到达终点时，发送端就已经发送了时延带宽积 $B \cdot W$ 个比特；
链路的时延带宽积又称为以比特为单位的链路长度。

往返时间

在许多情况下，因特网上的信息不仅仅单方向传输，而是双向交互；
我们有时很需要知道双向交互一次所需的时间；因此，往返时间RTT(Round-Trip Time)也是一个重要的性能指标。

利用率

信道利用率：用来表示某信道有百分之几的时间是被利用的（有数据通过）。
网络利用率：全网络的信道利用率的加权平均。
根据排队论，当某信道的利用率增大时，该信道引起的时延也会迅速增加；因此，信道利用率并非越高越好；
如果令 $D_0$ $D_{0}$ 表示网络空闲时的时延， $D$ $D$ 表示网络当前的时延，那么在适当的假定条件下，可以用下面的简单公式来表示 $D$ $D$ 、 $D_0$ $D_{0}$ 和利用率 $U$ $U$ 之间的关系： $D = \frac{D_0}{1 - U}$ $D = \frac{D _{0}}{1 - U}$
- 当网络的利用率达到50%时，时延就要加倍；
- 当网络的利用率超过50%时，时延急剧增大；
- 当网络的利用率接近100%时，时延就趋于无穷大。
- 因此，一些拥有较大主干网的ISP通常会控制它的信道利用率不超过50%。如果超过了，就要准备扩容，增大线路的带宽。
- 也不能使信道利用率太低，这会使宝贵的通信资源输白白浪费。应该使用一些机制，可以根据情况动态调整输入到网络中的通信量，使网络利用率保持在一个合理的范围内。

丢包率

丢包率即分组丢失率，是指在一定的时间范围内，传输过程中丢失的分组数量与总分组数量的比率。
丢包率具体可分为接口丢包率、结点丢包率、链路丢包率、路径丢包率、网络丢包率等。
丢包率是网络运维人员非常关心的一个网络性能指标，但对于普通用户来说往往并不关心这个指标，因为他们通常意识不到网络丢包。
分组丢失主要有两种情况：
- 分组在传输过程中出现误码，被结点丢弃；
- 分组到达一台队列已满的分组交换机时被丢弃；在通信量较大时就可能造成网络拥塞。
因此，丢包率反映了网络的拥塞情况：
- 无拥塞时路径丢包率为0
- 轻度拥塞时路径丢包率为1%~4%
- 严重拥塞时路径丢包率为5%~15%

1.6 计算机网络体系结构

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

原理参考模型，从下到上以此为：物理层、数据链路层、网络层、运输层、应用层

分层的必要性


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

分层思想举例

专用术语

实体
- 实体是指任何可发送或接收信息的硬件或软件进程。
- 对等实体是指通信双方相同层次中的实体。
协议
- 协议是控制两个对等实体在“水平方向”进行“逻辑通信”的规则的集合。
- 协议的三要素：
  - 语法定义所交换信息的格式
  - 语义定义通信双方所要完成的操作
  - 同步定义通信双方的时序关系
服务
- 在协议的控制下，两个对等实体在水平方向的逻辑通信使得本层能够向上一层提供服务。
  - 要实现本层协议，还需要使用下面一层所提供的服务。
  - 协议是“水平”的，而服务是“垂直”的。
  - 实体看得见下层提供的服务，但并不知道实现该服务的具体协议。下层的协议对上层的实体是“透明”的。
- 在同一系统中相邻两层的实体交换信息的逻辑接口称为服务访问点SAP，它被用于区分不同的服务类型。
- 帧的“类型”字段、IP数据报的“协议”字段，TCP报文段或UDP用户数据报的“端口号”字段都是SAP。
- 上层要使用下层所提供的服务，必须通过与下层交换一些命令，这些命令称为服务原语。
- 对等层次之间传送的数据包称为该层的协议数据单元（Protocol Data Unit，PDU）。
- 同一系统内层与层之间交换的数据包称为服务数据单元（Service Data Unit，SDU）。

2.1 物理层概述

物理层要实现的功能

数据链路层“看不见”（也无需看见）物理层究竟使用的是什么方法来传输比特流。数据链路层**只管“享受”**物理层提供的比特流传输服务即可。
物理层之间“透明”传输比特流。

物理层接口特性

机械特性
- 形状和尺寸
- 引脚数目和排列
- 固定和锁定装置
电气特性
- 信号电压的范围
- 阻抗匹配的情况
- 传输速率
- 距离限制
功能特性
- 规定接口电缆的各条信号线的作用
过程特性
- 规定在信号线上传输比特流的一组操作过程，包括各信号间的时序关系

2.2 传输媒体

传输媒体是计算机网络设备之间的物理通路，也称为传输介质或传输媒介。
传输媒体并不包含在计算机网络体系结构中。
导向型传输媒体（固体媒体）
- 同轴电缆
- 双绞线
- 光纤
非导向型传输媒体（自由空间）
- 无线电波
- 微波
- 红外线
- 大气激光
- 可见光

2.3 传输方式

串行运输和并行运输

同步传输和异步传输

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

2.4 编码与调制

基本概念

基带调制（编码）
- 以太网采用的曼彻斯特编码、4B/5B、8B/10B
- 数字基带信号 -> 数字信道
带通调制
- Wi-Fi采用的CCK/DSSS/OFDM调制
- 数字基带信号 -> 模拟信道
码元
- 在使用时间域的波形表示信号时，代表不同离散数值的基本波形称为码元。

常用编码方式

双极性不归零编码
- 编码效率高，但存在同步问题
双极性归零编码
- 自同步，但编码效率低
曼彻斯特编码
- 自同步，10Mb/s传统以太网
- 码元中间时刻的电平跳变既表示时钟信号，也表示数据。正跳变表示1还是0，负跳变表示0还是1，可以自行定义。
差分曼彻斯特编码
- 码元中间时刻的电平跳变仅表示时钟信号，而不表示数据。数据的表示在于每一个码元开始处是否有电平跳变：无跳变表示1，有跳变表示0。

差分曼彻斯特编码对比曼彻斯特编码

在传输大量连续1或连续0的情况下，差分曼彻斯特编码信号比曼彻斯特编码信号的变化少。

在噪声干扰环境下，检测有无跳变比检测跳变方向更不容易出错，因此差分曼彻斯特编码信号比曼彻斯特编码信号更易于检测。

在传输介质接线错误导致高低电平翻转的情况下，差分曼彻斯特编码仍然有效。

带通调制方法和混合调制方法

2.5 信道的极限容量

造成信号失真的主要因素

传输速率越高，信号经过传输后的失真就越严重。
传输距离越远，信号经过传输后的失真就越严重。
噪声干扰越大，信号经过传输后的失真就越严重。
传输媒体质量越差，信号经过传输后的失真就越严重。
信道上传输的数字信号，可以看做是多个频率的模拟信号进行多次叠加后形成的方波。
如果数字信号中的高频分量在传输时受到衰减甚至不能通过信道，则接收端接收到的波形前沿和后沿就变得不那么陡峭，每一个码元所占的时间界限也不再明确。这样，在接收端接收到的信号波形就失去了码元之间的清晰界限，这种现象称为码间串扰。
如果信道的频带越宽，则能够通过的信号的高频分量就越多，那么码元的传输速率就可以更高，而不会导致码间串扰。
然而，信道的频率带宽是有上限的，不可能无限大。因此，码元的传输速率也有上限。

奈氏准则

理想低通信道的最高码元传输速率 = $2W Baud=2W(码元/秒)=2Wlog_2X(比特/秒)$

W：信道的频率带宽（单位为Hz） Baud：波特，即码元/秒

使用奈氏准则给出的公式，就可以根据信道的频率带宽，计算出信道的最高码元传输速率。
只要码元传输速率不超过根据奈氏准则计算出的上限，就可以避免码间串扰。
奈氏准则给出的是理想低通信道的最高码元传输速率，它和实际信道有较大的差别。因此，一个实际的信道所能传输的最高码元传输速率，要明显低于奈氏准则给出的上限值。
码元传输速率又称为波特率、调制速率、波形速率或符号速率。
波特率与比特率有一定的关系：
- 当1个码元只携带1比特的信息量时，波特率（码元/秒）与比特率（比特/秒）在数值上是相等的。
- 当1个码元携带n比特的信息量时，波特率（码元/秒）转换成比特率（比特/秒）时，数值要乘以n。

香农公式

带宽受限且有高斯白噪声干扰的信道的极限信息传输速率

C=Wlog_2(1+\frac{S}{N})(b/s)

C：信道的极限信息传输速率（单位为b/s）

W：信道的频率带宽（单位为Hz）

S：信道内所传信号的平均功率

N：信道内的高斯噪声功率

S/N：信噪比，常用分贝（dB）表示

信噪比（dB）= $10log_{10}(\frac{S}{N})(dB)$

信道的频率带宽W或信道中的信噪比S/N越大，信道的极限信息传输速率C就越高。
实际信道不可能无限制地提高频率带宽W或信道中的信噪比S/N。
实际信道中能够达到的信息传输速率，要比香农公式给出的极限传输速率低不少。这是因为在实际信道中，信号还要受到其他一些损伤，例如各种脉冲干扰和信号衰减等，这些因素在香农公式中并未考虑。

2.6 信道复用技术

基本原理

复用（Multiplexing）就是在一条传输媒体上同时传输多路用户的信号。
当一条传输媒体的传输容量大于多条信道传输的总容量时，就可以通过复用技术，在这条传输媒体上建立多条通信信道，以便充分利用传输媒体的带宽。
尽管实现信道复用会增加通信成本（需要复用器、分用器以及费用较高的大容量共享信道），但如果复用的信道数量较大，还是比较划算的。

常见技术

频分复用 FDM
- 所有用户同时占用不同的频带资源并行通信
时分复用 TDM
- 所有用户在不同的时间占用同样的频带
波分复用 WDM
- 根据频分复用的设计思想，可在一根光纤上同时传输多个频率（波长）相近的光载波信号，实现基于光纤的频分复用技术。
- 目前可以在一根光纤上复用80路或更多路的光载波信号。因此，这种复用技术也称为密集波分复用DWDM。
码分复用 CDM
- 如果有两个或多个站同时发送数据，则信道中的信号就是这些站各自所发送一系列码片序列或码片序列反码的叠加。为了从信道中分离出每个站的信号，给每个站指派码片序列时，必须遵循以下规则：
  - 分配给每个站的码片序列必须各不相同，实际常采用伪随机码序列。
  - 分配给每个站的码片序列必须相互正交，即各码片序列相应的码片向量之间的规格化内积为0。
- 令向量A表示站A的码片向量，向量B表示站B的码片向量。两个不同站A和B的码片序列相互正交，就是向量A与向量B的规格化内积为0，如下式所示。
  $A\cdot B=\frac{1}{m}A_iB_i=0$
- 假设知道各手机的码片序列，给手机A发送比特1，给手机B发送比特0，各手机用自己的码片向量与收到的叠加后的码片向量，做规格化内积运算：
  - $(A + \overline{B}) \cdot A = A \cdot A + A \cdot \overline{B} = 1 + 0 = 1$ 运算结果为1，表明收到的是比特1
  - $(A + \overline{B}) \cdot B = A \cdot B + \overline{B} \cdot B = 0 + (-1) = -1$ 运算结果为-1，表明收到的是比特0
  - $(A + \overline{B}) \cdot C = A \cdot C + \overline{B} \cdot C = 0 + 0 = 0$ 运算结果为0，表明没有收到信息

3.1 数据链路层概述

在网络体系中的地位

链路、数据链路和帧

链路（Link）是指从一个节点到相邻节点的一段物理线路（有线或无线），而中间没有任何其他的交换节点。
数据链路（Data Link）是基于链路的。当在一条链路上传送数据时，除需要链路本身，还需要一些必要的通信协议来控制这些数据的传输，把实现这些协议的硬件和软件加到链路上，就构成了数据链路。
计算机中的网络适配器（俗称网卡）和其相应的软件驱动程序就实现了这些协议。一般的网络适配器都包含了物理层和数据链路层这两层的功能。
帧（Frame）是数据链路层对等实体之间在水平方向进行逻辑通信的协议数据单元PDU。

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

封装成帧和透明传输

数据链路层给上层交付下来的协议数据单元PDU添加帧首部和帧尾部，这称为封装成帧。
如果能够采取措施，使得数据链路层对上层交付的PDU的内容没有任何限制，就好像数据链路层不存在一样，就称其为透明传输。

差错检测

帧在传输的过程中可能出现误码。
接收方根据发送方添加在帧尾部中的检错码，可以检测出帧是否出现了误码。

可靠传输

不可靠传输服务：收到有误码的帧，直接丢弃，其他什么也不做；未收到发送方发送的帧，也不进行任何处理。
可靠传输服务：实现发送方发送什么，接收方最终都能正确收到。

3.2.1 封装成帧和透明传输

封装成帧

封装成帧是指数据链路层给上层交付下来的协议数据单元PDU添加一个首部和一个尾部，使之成为帧。
- 帧的首部和尾部中有包含一些重要的控制信息。
- 帧首部和尾部的作用之一就是帧定界。
  
  但帧首部和尾部不一定有帧定界标志。
为了提高数据链路层传输帧的效率，应当使帧的数据载荷的长度尽可能地大于首部和尾部的长度。
考虑到对缓存空间的需求以及差错控制等诸多因素，每一种数据链路层协议都规定了帧的数据载荷的长度上限，即最大传送单元（Maximum Transfer Unit，MTU）。例如，以太网的MTU为1500个字节。

透明传输

透明传输是指数据链路层对上层交付的PDU的内容没有任何限制，就好像数据链路层不存在一样。
如果传输的内容中有和定界符完全一样的内容，那么就会误判帧结束，但是如果限制了内容，就不是透明传输。
- 面向字节的物理链路使用字节填充的方法实现透明传输。即在把帧交给物理层之前，要在和定界符相同的内容前加入转义字符，或者在和转义字符相同的内容前加入转义字符
- 面向比特的物理链路使用比特填充的方法实现透明传输。即在内容中连续遇到5个1时，在后面加0（因为01111110就是帧定界符了）

3.2.2 差错检测

误码

实际的通信链路都不是理想的，受到噪声干扰、传输媒体质量等因素影响，比特在传输过程中可能会产生差错（称为比特差错）：
- 比特1可能变成比特0
- 比特0可能变成比特1
在一段时间内，传输错误的比特数量占所传输比特总数的比率称为误码率（Bit Error Rate, BER）。
提高链路的信噪比，可以降低误码率。但在实际的通信链路上，不可能使误码率下降为零。

奇偶校验

奇校验是在待发送的数据后面添加1个校验位，使得添加该校验位后的整个数据中比特1的个数为奇数。
偶校验是在待发送的数据后面添加1个校验位，使得添加该校验位后的整个数据中比特1的个数为偶数。
如果在数据位产生了1位误码，1的个数的奇偶性发生改变，可检出错误。校验位同理。但是若数据位和校验位各出现1位误码，那么1个数的奇偶性不变，检验不到错误

循环冗余校验

数据链路层广泛使用漏检率极低的循环冗余校验（Cyclic Redundancy Check，CRC）检错技术。

生成多项式

G(X) = X^4 + X^2 + X + 1= \boxed{1} \cdot X^4 + \boxed{0} \cdot X^3 + \boxed{1} \cdot X^2 + \boxed{1} \cdot X^1 + \boxed{1} \cdot X^0

生成多项式各项系数构成的比特串：10111（计算冗余码时作为除数）

生成多项式必须包含最低此项，即"1"

CRC操作

发送方CRC操作

接收方CRC操作

总结

奇偶校验、循环冗余校验等差错检测技术，只能检测出传输过程中出现了差错，但并不能定位错误，因此无法纠正错误。
要想纠正传输中的差错，可以使用冗余信息更多的纠错码（例如海明码）进行前向纠错。但纠错码的开销比较大，在计算机网络中较少使用。
在计算机网络中，通常采用后续课程中将要介绍的检错重传方式来纠正传输中的差错，或者仅仅丢弃检测到差错的帧，这取决于数据链路层向其上层提供的是可靠传输服务还是不可靠传输服务。
循环冗余校验CRC具有很好的检错能力（漏检率极低），虽然计算比较复杂，但非常易于用硬件实现，因此被广泛应用于数据链路层。

3.2.3 可靠传输

可靠传输的相关概念

可靠传输服务：通过某种机制实现发送方发送什么，接收方最终就能收到什么
传输差错包括：分组重复、分组失序、分组丢失和误码（比特差错）。其中分组重复、分组失序、分组丢失出现在数据链路层的上层，误码出现在数据链路层的下层
可靠传输服务并不局限于数据链路层，其他各层均可选择实现可靠传输。
可靠传输的实现比较复杂，开销比较大，是否使用可靠传输取决于应用需求。

停止-等待 (SW) 协议

实现原理

发送方发送DATA，接收方的差错检测若检测无误码，则接受并发送确认分组ACK。
发送方发送DATA，接收方的差错检测若检测有误码，则丢弃并发送否认分组NAK。那么然后发送方要重传之前有误码的数据分组，再去经过接收方的差错检测。
发送方发送DATA，若是传输中途丢失，接收方就不会返回分组，发送方需要设置超时重传时间RTO，而且要略大于收发双方的平均往返时间RTT。然后进行重新传输。
- 在数据链路层，点对点的往返时间 RTT 比较固定，RTO 就比较好设定。
- 在运输层，由于端到端往返时间非常不确定，设置合适的超时重传时间 RTO 有时并不容易。
接收方发送ACK，若是传输中途丢失，结合上一条，发送方就会超时重传，但这样接收方就重复接收了同一个DATA。为解决该问题，引入数据分组编号，分组编号即0和1，DATA就该叫做DATA0/1。接收方丢弃重复的数据分组，再发送一个确认分组。
更复杂的情况会出现ACK被发送方重复接收，同理需要给ACK分组编号。

停止-等待协议属于自动请求重传（Automatic Repeat reQuest, ARQ）协议。 即重传的请求是发送方自动进行的，而不是接收方请求发送方重传某个误码的数据分组。

信道利用率

信道利用率\ U \approx \frac{T_D}{T_D + RTT + T_A}

说明：

$T_D$ ：发送方发送数据分组所耗费的发送时延。
$RTT$ ：收发双方之间的往返时间。
$T_A$ ：接收方发送确认分组所耗费的发送时延。

由于确认分组的长度通常远小于数据分组的长度，即 $T_A \ll T_D$ ，公式可以简化为：

U \approx \frac{T_D}{T_D + RTT}

简化后的利用率主要受 $RTT$ 与 $T_D$ 比例关系的影响：

当 $RTT \gg T_D$ 时：
- 结果：信道利用率 $U$ 很低。
- 典型案例：卫星链路（由于距离极远，往返时延很大）。
当 $RTT \ll T_D$ 时：
- 结果：信道利用率 $U$ 比较高。
- 典型案例：无线局域网（往返时间远小于数据发送时间）。

回退N帧 (GBN) 协议

在使用流水线传输方式时，发送方不能无限制地连续发送数据分组，否则可能会导致网络中的路由器或接收方来不及处理这些数据分组，进而导致数据分组的丢失，这实际上是对网络资源的浪费。因此，必须采取措施来限制发送方连续发送数据分组的数量。
回退N帧协议采用流水线传输方式，并且利用发送窗口来限制发送方连续发送数据分组的数量，这属于连续ARQ协议。

发送方

发送窗口 $W_T$ $W_{T}$ 的取值范围是 $1 < W_T \leq (2^n - 1)$ $1 < W_{T} \leq (2^{n} - 1)$ ，其中， $n$ $n$ 是构成分组序号的比特数量。
- 如果 $W_T = 1$ ：变成了停止-等待协议。
- 如果 $W_T > (2^n - 1)$ ：接收方无法分辨新旧数据分组。
可在未收到接收方确认分组的情况下，将序号落入发送窗口内的多个数据分组全部发送出去。
只有收到对已发送数据分组的确认分组时，发送窗口才能向前滑动到相应位置。
收到多个重复确认时，可在重传计时器超时前尽早开始重传，由具体实现决定（即确定收到几个重复确认进行重传）。
发送窗口内某个已发送的数据分组产生超时重传时，发送窗口内该数据分组的后续已发送的数据分组也必须全部重传，这就是回退N帧 (Go-back-N, GBN) 协议名称的由来。

接收方

接收窗口 $W_R = 1$ 的，因此只能按序接收数据分组。
只接收序号落入接收窗口内且无误码的数据分组，并且将接收窗口向前滑动一个位置，与此同时给发送方发送相应的确认分组。
为了减少开销，接收方不必每收到一个按序到达且无误码的数据分组就给发送方发送一个相应的确认分组。
- 可以在连续收到多个按序到达且无误码的数据分组后（数量由具体实现决定），才针对最后一个数据分组发送确认分组，这称为累积确认。
- 或者可以在自己有数据分组要发送时才对之前按序接收且无误码的数据分组进行捎带确认。
接收方收到未按序到达的数据分组后，除丢弃外，还可对之前最后一个按序到达的数据分组进行重复确认，以便发送方尽快重传。

选择重传协议

用 $n (n > 1)$ 个比特给分组编号，发送窗口 $W_T$ 与接收窗口 $W_R$ 的关系如下：

\begin{cases} 1 < W_R \leq W_T \\ W_T + W_R \leq 2^n \end{cases} \implies 1 < W_R \leq 2^{(n-1)}

当 $W_R$ 取最大值 $2^{(n-1)}$ 时， $W_T$ 能取到的最大值也为 $2^{(n-1)}$ 。
$W_R$ 超过 $W_T$ 没有意义
确保接收窗口向前滑动后，落入接收窗口内的新序号与之前的旧序号没有重叠，避免无法分辨新旧数据分组。

发送方

可在未收到接收方确认分组的情况下，将序号落入发送窗口内的多个数据分组全部发送出去。
只有按序收到对已发送数据分组的确认分组时，发送窗口才能向前滑动到相应位置。
如果收到未按序到达的确认分组，应对其进行记录，以防止其相应数据分组的超时重发，但发送窗口不能向前滑动。

接收方

可接收未按序到达但没有误码并且序号落入接收窗口内的数据分组。
为了使发送方仅重传出现差错的分组，接收方不再采用累积确认，而需要对每一个正确接收的数据分组进行逐一确认。
只有在按序接收数据分组后，接收窗口才能向前滑动到相应位置。

3.3 点对点协议 (PPP)

概述

点对点协议（Point-to-Point Protocol, PPP）是目前使用最广泛的点对点数据链路层协议。
点对点协议PPP主要有两种应用：
- 用户到 ISP 的连接：例如通过拨号或 ADSL 接入互联网。
- 路由器之间的点对点链路：用于连接核心网络中的两个节点。
从网络体系结构的角度看点对点协议 PPP 的组成
- 一套网络控制协议 NCPs
- 一个网络层 PDU 封装到串行链路的方法
- 一个链路控制协议 LCP

帧格式

标志（Flag）字段：PPP帧的定界符，取值为 0x7E。
地址（Address）字段：取值为 0xFF，预留（目前没有什么作用）。
控制（Control）字段：取值为 0x03，预留（目前没有什么作用）。
协议（Protocol）字段：其值用来指明帧的数据载荷应向上交付给哪个协议处理。
帧检验序列（Frame Check Sequence, FCS）字段：其值是使用循环冗余校验CRC计算出的检错码。

透明传输

面向字节的异步链路

发送方的处理：
- 将数据载荷中出现的每一个 0x7E 减去 0x20（相当于异或 0x20），然后在其前面插入转义字符 0x7D。
- 若数据载荷中原来就含有 0x7D，则把每一个 0x7D 减去 0x20，然后在其前面插入转义字符 0x7D。
- 将数据载荷中出现的每一个 ASCII 码控制字符（即数值小于 0x20 的字符），加上 0x20（相当于异或 0x20，将其转换成非控制字符），然后在其前面插入转义字符 0x7D。
接收方的处理：
- 进行与发送方相反的变换，就可以正确地恢复出未经字节填充的原始数据载荷。

面向比特的同步链路

发送方的处理：
- 对帧的数据载荷进行扫描（一般由硬件完成），每出现 5 个连续的比特 1，则在其后填充一个比特 0。
接收方的处理：
- 对帧的数据载荷进行扫描，每出现 5 个连续的比特 1 时，就把其后的一个比特 0 删除。

差错检测

帧检验序列FCS字段：其值是使用循环冗余校验CRC计算出的检错码。
CRC采用的生成多项式为：

CRC-CCITT = X^{16} + X^{12} + X^5 + 1

工作状态

以用户主机拨号接入因特网服务提供者ISP的拨号服务器的过程为例

3.4 共享式以太网

年份	里程碑事件	关键细节
1975年	以太网诞生	Robert Metcalfe (1946-)，美国Xerox公司，速率 2.94Mb/s
1976年	以太网里程碑论文	Robert Metcalfe 与助手 David Boggs 发表论文《以太网：局域计算机网络的分布式包交换技术》
1979年	3Com公司成立	Robert Metcalfe 离开 Xerox 成立 3Com；游说 DEC、Intel 和 Xerox 共同将以太网标准化
1980年	以太网标准V1	DIX Ethernet V1，速率 10Mb/s
1982年	以太网标准V2	DIX Ethernet V2：第一个局域网产品的标准，被大量使用
1983年	IEEE 以太网标准	IEEE 802.3 以太网标准：对 DIX Ethernet V2 的帧格式做了很小的改动，当时没有被广泛使用

以太网目前已经从传统的共享式以太网发展到交换式以太网，传输速率已经大幅提高。

3.4.1 网络适配器和MAC地址

网络适配器

要将计算机连接到以太网，需要使用相应的网络适配器（Adapter），网络适配器一般简称为“网卡”。
在计算机内部，网卡与CPU之间的通信，一般是通过计算机主板上的I/O总线以并行传输方式进行的。
网卡与外部以太网（局域网）之间的通信，一般是通过传输媒体（同轴电缆、双绞线电缆、光纤）以串行方式进行的。
网卡除要实现物理层和数据链路层功能，其另外一个重要功能就是要进行并行传输和串行传输的转换。由于网络的传输速率和计算机内部总线上的传输速率并不相同，因此在网卡的核心芯片中都会包含用于缓存数据的存储器。
在确保网卡硬件正确的情况下，为了使网卡正常工作，还必须要在计算机的操作系统中为网卡安装相应的设备驱动程序。驱动程序负责驱动网卡发送和接收帧。

MAC地址

在点对点信道，数据链路层不需要使用地址。而在广播信道，数据链路层必须使用地址来区分各主机。
MAC地址一般被固化在网卡的电可擦可编程只读存储器EEPROM中，因此MAC地址也被称为硬件地址，有时被称为物理地址（和物理层无关，属于数据链路层范畴）
MAC地址是对网络上各接口的唯一标识，而不是各设备的唯一标识。

地址格式

其中第 1 字节的 b1 位：G/L (Global/Local)

$G/L = 0$ ：全球管理
$G/L = 1$ ：本地管理

第 1 字节的 b0 位：I/G (Individual/Group)

$I/G = 0$ ：单播地址
$I/G = 1$ ：多播地址

第 1 字节 b1 位	第 1 字节 b0 位	MAC 地址类型	地址占比
0	0	全球单播（由厂商生产网络设备时固化在设备中）	1/4
0	1	全球多播（交换机、路由器等标准网络设备所支持的多播地址）	1/4
1	0	本地单播（由网络管理员分配，优先级高于网络接口的全球单播地址）	1/4
1	1	本地多播（可由用户对网卡编程实现，以表明其属于哪些多播组）	1/4

其字节发送顺序是从第1字节开始，到第6字节。字节内的比特发送顺序是从b0到b7。

网卡对无误码帧的处理

网卡从网络上每收到一个无误码的帧，就检查帧首部中的目的 MAC 地址，按以下情况处理：
1. 如果目的 MAC 地址是广播地址（FF-FF-FF-FF-FF-FF），则接受该帧。
2. 如果目的 MAC 地址与网卡上固化的全球单播 MAC 地址相同，则接受该帧。
3. 如果目的 MAC 地址是网卡支持的多播地址，则接受该帧。
4. 除上述 (1)、(2) 和 (3) 情况外，丢弃该帧。
网卡还可被设置为一种特殊的工作方式：混杂方式。工作在混杂方式的网卡，只要收到共享媒体上传来的帧就会收下，而不管帧的目的 MAC 地址是什么。
- 用途：对于网络维护和管理人员，这种方式可以监视和分析局域网上的流量，以便找出提高网络性能的具体措施。
- 工具示例： 嗅探器 (Sniffer) 就是一种工作在混杂方式的网卡，再配合相应的工具软件（WireShark），就可以作为一种非常有用的网络工具来学习和分析网络。
- 风险提示：混杂方式就像一把“双刃剑”，黑客常利用这种方式非法获取网络用户的口令。

3.4.2 以太网在共享信道下的运作机制

CSMA/CD协议

在以太网的发展初期，人们普遍认为“无源的电缆线比有源器件可靠”，因此将多个站点连接在一条总线上来构建共享总线以太网。
共享总线以太网具有天然的广播特性，即使总线上某个站点给另一个站点发送单播帧，表示帧的信号也会沿着总线传播到总线上的其他各站点。
当某个站点在总线上发送帧时，总线资源会被该站点独占。此时，如果总线上的其他站点也要在总线上发送帧，就会产生信号碰撞。
当两个或多个站点同时使用总线发送帧时，就会产生信号碰撞。
为了解决各站点争用总线的问题，共享总线以太网使用了一种专用协议 CSMA/CD，它是载波监听多址接入/碰撞检测 (Carrier Sense Multiple Access/Collision Detection) 的英文缩写词。

协议组成

多址接入 MA：

多个站点连接在一条总线上，竞争使用总线。

载波监听 CS：

每个站点在发送帧之前，先要检测一下总线上是否有其他站点在发送帧（“先听后说”）：
- 若检测到总线空闲 96 比特时间（发送 96 比特所耗费的时间，也称为帧间最小间隔），则发送这个帧；
- 若检测到总线忙，则继续检测并等待总线转为空闲 96 比特时间，然后发送这个帧。

碰撞检测 CD：

每个正在发送帧的站点边发送边检测碰撞（“边说边听”）：
- 一旦发现总线上出现碰撞，立即停止发送，退避一段随机时间后再次从载波监听开始进行发送（“一旦冲突，立即停说，等待时机，重新再说”）。

协议局限

载波监听检测到总线空闲，但总线并不一定空闲。
使用CSMA/CD协议的共享总线以太网上的各站点，只是尽量避免碰撞并在出现碰撞时做出退避后重发的处理，但不能完全避免碰撞。
在使用CSMA/CD协议时，由于正在发送帧的站点必须“边发送帧边检测碰撞”，因此站点不可能同时进行发送和接收，也就是不可能进行全双工通信，而只能进行半双工通信（双向交替通信）。

共享式以太网的争用期

站点从发送帧开始，最多经过时长 $2\tau$ （即 $\delta \to 0$ ）就可检测出所发送的帧是否遭遇了碰撞。
因此，共享总线以太网的端到端往返时间 $2\tau$ 被称为争用期（Contention Period）或碰撞窗口（Collision Window），它是一个非常重要的参数。
- 站点从发送帧开始，经过争用期 $2\tau$ 这段时间还没有检测到碰撞，就可以肯定这次发送不会产生碰撞。
从争用期的概念可以看出，共享总线以太网上的每一个站点从发送帧开始，到之后的一小段时间内，都有可能遭遇碰撞，而这一小段时间的长短是不确定的，它取决于另一个发送帧的站点与本站点的距离，但不会超过总线的端到端往返传播时延，即一个争用期 $2\tau$ 。
- 很显然，总线的长度越长（单程端到端传播时延越大），网络中站点数量越多，发生碰撞的概率就越大。
- 因此，共享以太网的总线长度不能太长，接入的站点数量也不能太多。
10Mb/s 共享总线以太网参数规定：争用期 $2\tau$ 的值为 512 比特的发送时间，即 $51.2\mu s$ 。也称为512 比特时间：这是传统以太网的一个基石参数。
由于 $10Mb/s$ 下 512 比特等于 64 字节，这也就是以太网最短帧长为 64 字节的物理由来：为了确保在发送完 64 字节之前，信号一定能完成一个来回（争用期），从而检测出是否发生了碰撞。
$2\tau = \frac{512\ b}{10\ Mb/s} = \frac{512\ b}{10 \times 10^6\ b/s} = 51.2\mu s$
除考虑了信号传播时延外，还考虑到网络中可能存在转发器所带来的时延以及产生碰撞时继续发送 32 比特或 48 比特人为干扰信号所持续的时间等。
假设信号的传播速率为： $2 \times 10^8\ m/s$

则总线长度为： $2 \times 10^8\ m/s \times 25.6\mu s = 5120m$