# 基本概念

# 概念、功能和分类

# 概念

计算机网络是一些采用单一技术的、互联的、自治的计算机系统的集合，用来实现资源共享和信息传递。

其包括三个基本要求：

自治的 (autonomous): 需要具有独立的硬件和操作系统
互联的 (interconnected): 通过通讯模块和接口交换信息
单一技术 (a single technology): 采用相同的协议和标准

# 因特网

因特网 (Internet) 是一些互联网子网连接而成的逻辑网络，其遵循的顶层协议是 TCP/IP 协议。因特网是最大的互连网。

从拓扑结构上看，因特网由结点 (node) 和连接结点的链路 (link) 组成。其拓扑结构按工作方式可以分为两个部分：

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

# 万维网

万维网 (World Wide Web, WWW) 是基于客户端 - 服务器 (Client/Server, C/S) 方式的信息发现技术和超文本技术的综合，是因特网顶层的分布式系统。

# 组成

计算机网络的组成可以按物理层面 (physical, hardware) 和逻辑层面 (logical, software) 进行区分。

在物理层面，计算机网络自小到大可以分为

个人局域网 (Personal Area Network, PAN)
局域网 (Local Area Network, LAN)
城域网 (Metropolitan Area Network, MAN)
广域网 (Wide Area Network, WAN)
互连网 (internetWork)

在逻辑层面，计算机网络有以下部分组成

层 (layer): 计算机网络大多由一系列层的集合组成
协议 (protocol): 两个通信实体如何交换信息的描述
服务 (service): 计算机网络向两通信实体提供的辅助
接口 (interface): 一个客户端如何使用服务的方式

# 功能

其主要有数据通信、资源共享、分布式处理、提高可靠性和负载均衡五大功能。

# 分类

计算机网络有多种分类方式。按照分布范围，可以分为广域网、城域网、局域网和个人区域网。按传输技术可以分为广播式网络和点对点网络。按拓扑结构可以分为总线形网络、星形网络、环形网络和网状网络。按交换技术可以分为电路交换网络、报文交换网络和分组交换网络 (包交换网络)。按传输介质可以分为有线网络和无线网络。

# 互联网标准

所有互联网标准以 RFC (Request For Comments) 形式在互联网上发表。

制定互联网标准需要经过如下三个阶段：

互联网草案 (Internet Draft): 有效期 6 个月，此时不是 RFC 文档
建议标准 (Proposed Standard): 此时成为 RFC 文档。
互联网标准 (Internet Standard): 正式标准。此时的每个标准有唯一 STD 编号。

# 计算机网络的性能

计算机网络常见的性能指标包括

速率 (bit/s): 数据的传送速率
带宽 (Hz & bit/s): 示某信道允许通过的信号频带范围 (Hz) 或单位时间内网络中的某信道所能通过的 “最高数据率”(bit/s)
吞吐量 (bit/s): 单位时间内通过某个网络的实际的数据量
时延 (s): 指数据从网络的一端传送到另一端所需的时间，可以细分为发送时延、传播时延、处理时延和排队时延
时延带宽积 (bit): 传播时延和带宽的乘积，就是以比特为单位的链路长度
往返时间 (s)
利用率：分为信道利用率和网络利用率

# 计算机网络体系结构

# 网络协议

在计算机网络中，一些规则明确确定了交换的数据格式以及有关的同步问题。这些为进行网络中的数据交换而建立的规则、标准或约定称为网络协议 (network protocol), 简称协议。网络协议一般由以下三要素组成：

语法：数据与控制信息的结构或格式
语义：需要发出何种控制信息，完成何种动作以及做出何种响应
同步：事件实现顺序的详细说明

# 计算机网络体系结构的设计思想

计算机网络体系结构设计成可分层的。分层的基本原则包括：

每层都实现一种相对独立的功能，降低大系统的复杂度
各层之间界面自然清晰，易于理解，相互交流尽可能少
各层功能的精确定义独立于具体的实现方法，可以采用最合适的技术来实现
保持下层对上层的独立性，上层单向使用下层提供的服务
整个分层结构应能促进标准化工作

通常情况下，每一层需要完成的工作包括以下一种或多种：

差错控制：使相应层次对等方的通信更加可靠
流量控制：发送端的发送速率必须使接收端来得及接收，不要太快
分段和重装：发送端将要发送的数据块划分为更小的单位，在接收端将其还原
复用和分用：发送端几个高层会话复用一条低层的连接，在接收端再进行分用
连接建立和释放：交换数据前先建立一条逻辑连接，数据传送结束后释放连接

# 计算机网络体系结构的概念

计算机网络各层及其协议的集合称为网络的体系结构 (architecture). 具有代表性的体系结构包括两种：OSI 模型和 TCP/IP 模型.

# OSI

OSI 是国际标准化组织 ISO 于 1977 年起研究并提出的，全称为开放系统互联基本参考模型 (Open Systems Interconnection Reference Model, OSI/RM). OSI 的体系结构包括 7 层，分别为物理层、数据链路层、网络层、运输层、会话层、表示层及应用层。OSI 是法律上的国际标准，但由于参与制定的专家缺乏实际经验、协议复杂、制定周期长、层次划分不合理等问题，OSI 没能广泛使用。

OSI 不是一种网络体系结构，因为对其中的层，其没有规定特定的服务和协议。其仅仅指出了每一层的功能。

上图是 OSI 的一个示例图。下面，我们将介绍 OSI 各层及其特点。

# 物理层

物理层 (the physical layer) 是借助通信信道传输比特流的层，为 OSI 的最底层。物理层的传输单元是比特 (bit)。

# 网络层

最基本的功能包括路由、差错控制以及如何分组。

# 传输层

传输层 (the transport layer) 承上启下，向上屏蔽了所有通信细节。其目的是保证端到端 (end-to-end) 的可靠传输，传输单位为传送协议数据单元 (Transport Protocol Data Unit, TPDU), 也可以笼统称之为报文 (message).

应用层上传输的数据也被称为报文，因此说报文是一个不严谨的概念。

# 会话层和表示层

会话层 (the session layer) 和表示层 (the presentation layer) 中没有协议被指定，于是成为了一个空层。表示和会话任务通过应用层实现。

# 应用层

应用层 (the application layer) 不是为上层提供服务，而是直接为最终用户进程提供应用服务。

# TCP/IP

TCP/IP 即传输控制协议 / 网络协议 (Transmission Control Protocol/Internet Protocol), 又称网络通讯协议。TCP/IP 本身是一些协议簇，其层是在协议簇结构的基础上后来进行划分的。因此其各层划分可能不十分严格，表述也不十分规范。TCP/IP 可以划分为

TCP/IP 是事实上的国际标准，也是 Internet 中最基本的协议。

TCP/IP 不具有可移植性。

# 链路层

TCP/IP 模型中的链路层 (the link layer) 实际上是接入 Internet 的所有接口的集合，其逻辑结构不十分完备

# 网络层

网络层 (the Internet layer) 中传递的数据单元也是 package. 其核心协议是 IP 协议。提供的服务是无连接服务 (connectionless service).

ip 数据报.

# 具有五层协议的体系结构

将 OSI 和 TCP/IP 的特点进行抽象，就得到了具有五层协议的体系结构。其包括物理层、数据链路层、网络层、运输层和应用层，与 OSI 和 TCP/IP 的关系图如下：

# 物理层的基本概念

# 数据传输的特征量

数据传输性能采用带宽、吞吐量、时延和时延带宽积等特征量描述。

# 带宽

带宽 (bandwidth) 单位为赫兹 (Hz) 或比特每秒 (bit/s). 以赫兹为单位描述的是信道所能传输的信号频率范围。以比特每秒为单位描述的是单位时间内信道可以传输的数据总量。

# Nyquist 定理

在带宽有限的无噪信道中，数据的极限传输速率 (Maximum data rate) 为 $2B\log_2V$ bits/sec.

# 香农定理

香农 (Shannon) 定理给出了带宽有限的有噪信道的极限传输速率为 $W \log_2(1+S/N)$ bits/sec.

# 结论

根据上述定理并结合显示条件，可以得到的结论是：

信噪比越大，信息的极限传输速率越高。
确定带宽和信噪比下，存在信息传输速率上限
只要信息传输速率低于上限，就可以找到某种方法实现无差错传输
实际传输速率远低于香农定理给出的信道传输速率上限

# 吞吐量

吞吐量 (throughput) 表示在单位时间内通过某个网络 (或信道、接口) 的数据量.

# 时延

时延 (delay/latency) 可以分为四部分：

发送时延 (transmission delay): 发送数据时，数据帧从结点进入到传输媒体所需要的时间。从发送数据帧的第一个比特算起，到该帧的最后一个比特发送完毕所需的时间。可以采用数据帧长度 (bit) 与发送速率 (bit/s) 的比值计算。
传播时延 (propagation delay): 电磁波在信道中传播一定的距离而花费的时间。可以用信道长度 (m) 与信道内信号传播速率 (m/s) 计算、
处理时延 (processing delay): 交换结点为存储转发而进行一些必要的处理所花费的时间。
排队时延 (queuing): 结点缓存队列中分组排队所经历的时延。排队时延的长短往往取决于网络中当时的通信量。

# 时延带宽积

时延带宽积 (bandwidth-delay product) 是时延与带宽的乘积，表示以比特为单位的链路长度。

# 调制方法

将数字信号转化为模拟信号的方式称为数字调制 (digital modulate). 更一般地，将需要传递的信息转化为易在信道中传输的信号的方式称为调制 (modulate), 相反的过程称为解调 (demodulate). 常见的调制与解调方法如下：

模拟信号调制为数字信号
- 脉冲编码调制 (Pulse Code Modulation)
数字信号调制为数字信号
- 不归零编码 (Non-Return-to-Zero encoding, NRZ)
- 曼彻斯特编码 (Manchester encoding)
- 差分曼彻斯特编码 (differential Manchester encoding)
数字信号调制为模拟信号
- 幅移键控 (Amplitude Shift Keying, ASK)
- 频移键控 (Frequency Shift Keying, FSK)
- 相移键控 (Phase Shift Keying, PSK)
  - 二进制相移键控 (Binary Phase Shift Keying, BPSK)
  - 正交相移键控 (Quadrature Phase Shift Keying, QPSK)

# 复用技术

常见的复用技术包括：

频分复用 (Frequency Division Multiplexing, FDM): 将频谱分成儿个频段，每个用户完全拥有其中的一个频段来发送自己的信号
时分复用 (Time Division Multiplexing, TDM): 用户以循环的方式轮流工作。每个用户周期性地获得整个带宽非常短的一个时间
码分复用 (Code Division Multiplexing, CDM): 把一个窄带信号扩展到一个很宽的频带上。这种方法更能容忍干扰，而且允许来自不同用户的多个信号共享相同的频带。码分复用又称码分多址 (Code Division Multiple Access, CDMA)

码分复用示例

# 数据链路层的设计要点

数据链路层的设计要点 (Design Issues) 包括：

如何将数据封装成帧 (framing)
如何进行差错控制 (error control), 即检测并纠正错误的数据。
如何处理发方和收方的数据传输速率不匹配问题，即流量控制 (flow control).

# 向网络层提供的服务

数据链路层向网络层提供虚拟通信服务，最终通过物理层实现数据通信。提供的服务包括：

无确认、无连接的服务 (Unacknowledged connectionless service): 不需要对发送的帧进行确认，也不需要提前建立逻辑链接。其适用于固有可靠性较高的网络，例如以太网 (Ethernet).
有确认、无连接的服务 (Acknowledged connectionless service): 不需要提前建立逻辑链接，但发送的每一个帧都需要单独确认。其适用于不可靠的信道，例如 IEEE 802.11(WiFi).
有确认、有连接的服务 (Unacknowledged connection-oriented service): 既需要进行帧确认，又需要提前进行逻辑链接。发送数据的过程包括三个阶段：建立连接 (establish the connection), 传输数据 (transfer data), 解除连接 (release the connection). 每一个发送的数据帧需要编号，这样可以确认每帧恰被接收一次，且依照正确的顺序被接收。其适用于长距离、不可靠的信道，例如卫星信道和长距离电话线路。

# 封装成帧

封装成帧过程需要解决两个问题:

帧的边界 (boundary) 确定
帧的透明传输

在以上两个任务的驱动下，产生了以下四种封装成帧的方法：

字节计数法 (Byte count): 在帧头部采用一个字段表明帧内字节数 (含自身)。当一个帧头部出现差错后，其后的帧可能全部出现差错，且纠错困难，很少使用。
字节填充的标志字节法 (Flag bytes with byte stuffing): 定义一个标志字节 (Flag byte) 表示帧的开始和结束。如果在传输的数据中出现标志字节，则加入一个转义符 (Escape Byte, ESC) 进行表示。即数据中的 FLAG 表示为 ESC FLAG , 数据中的 ESC 表示为 ESC ESC . 该方法在 PPP 协议中使用。
比特填充的标志比特法 (Flag bits with bit stuffing): 帧长度的最小单位为比特而非字节。帧开始和结束的标志为一个比特串: 01111110 即 0x7E. 为实现透明传输，发送端将传输数据中的任 5 个连续的 1 后都插入 1 个 0. 接收端将 5 个连续的 1 后的第一个 0 删去。若出现 6 个连续的 1, 则认为达到了帧的末尾。其在 HDLC 协议中使用。
物理层编码违例法 (Physical layer coding violations): 该做法没有实现完全的透明传输，而是将常规数据中不常用的比特组合作为标志位。因此其称之为 “违例” 法。其不十分常用。

# 差错控制

差错控制 (error control) 需要解决的问题是：如何确定所有的帧都被接收端按正确的顺序全部接收了。否则，其可能出现的错误包括：帧丢失、帧重复和帧失序。

应对以上方式采用的策略包括：

计时器 (timers) 和重传 (retransmission): 用来检测帧是否在信道上丢失。
顺序编号 (Sequence Numbers for each frame): 用来检测帧是否丢失，并检测帧的接收顺序是否出现问题。

# 可靠通信的实现

根据以上的策略，我们可以在不可靠的信道上实现可靠通信。其传输步骤如下：

发送端发送数据帧 $M_1$ 并启用计时器.
接收端接收 $M_1$ 后进行确认.
若发送端未收到 $M_1$ 的确认信号，则在一定时间后重传 $M_1$ , 即超时重传。此过程称为确认丢失。
若发送端在重新发送 $M_1$ 后收到了此前的 $M_1$ 的确认信号，则不再考虑。此过程称为确认迟到。

以上的可靠传输协议称为自动重传请求 (Automatic Repeat reQuest, ARQ).

# 流量控制

当发送方发送的数据远超接收方可以接收的数目时，接收方会出现帧丢失等情况。此时需要进行流量控制。流量控制有两种最基本的策略：

基于反馈的流量控制 (feedback-based flow control)
基于速率的流量控制 (rate-based flow control)

# 错误检测和纠正

当信道受到干扰等以外情况发生时，帧中的数据可能出现一位或数位的错误。对于这种情况，我们采用错误检测和错误纠正的方式予以应对。

其中，错误检测 (Error Detection) 即检查传输过程中是否发生错误。是一般采用的方法。其技术主要包括

奇偶校验 (parity)
校验和 (checksums)
循环冗余检验 (cyclic redundancy checks, CRC)

错误纠正 (Error Correction) 不仅要求检查传输过程中是否发生错误，还要求将错误进行纠正。此种方式传输效率低，使用相对较少。其技术主要包括

海明码 (Hamming codes)
二进制卷积码 (binary convolutional codes)
里德所罗门码 (Reed-Solomon codes)
低密度奇偶校验码 (low-density parity check codes)

注意！不要将此处的错误检测和纠正技术与前面所谈的差错控制技术混淆。差错控制技术使数据链路层面向网络层提供的服务，用来解决帧层面的错误，称为传输差错。而此处错误检测和纠正解决的是帧中某几位的错误，称为比特差错。

下面，我们主要介绍校验和技术和循环冗余检验技术。

# 校验和技术 (checksum)

校验和技术在诸多互联网协议中有应用，包括 IP 协议，TCP 协议和 UDP 协议等。广义的校验和技术即将信息分段求和，根据和进行校验。我们在这里给出因特网 16 位校验和技术 (Internet checksum) 的具体过程。

信息分段：将信息每 16 位分成一段
从左至右相邻两段求和
若出现进位，则抹去进位并在和上加一，并返回 2.
完成求和后，将最终的 16 位和各位求反，得到校验和

接收方按同样规则进行部分和求和，若最终得到的结果为 0xFFFF , 则说明传输无误。

# 循环冗余检验 (CRC)

循环冗余检验 (Cyclic Redundancy Check, CRC) 也称多项式编码 (polynomial code), 是最常用、最有效的错误检验方式。其具体方式如下：

假设传输的帧长度是 $m$ , 则将其看作一个系数为模 $2$ 意义下的 $m-1$ 次多项式 $M(x)$ . 发送方和接收方预先商定一个生成多项式 (generated polynomial) $G(x)$ . 设 $r:=\deg G(x)$ 是 $G(x)$ 的次数，则发送方计算 $x^r M(x)$ 模 $G(x)$ 得到的余式 $R(x)$ , 则最终发出的帧为

$T(x):= x^rM(x)+R(x)$

由于多项式系数是定义在模 $2$ 意义下的，因此 $G(x)|T(x)$ . 若接收方接受到的 $T(x)$ 可被 $G(x)$ 整除，则认为 $T(x)$ 传输成功，删去其后 $r$ 位即得到真实数据 $M(x)$ . 数据传输出现差错的情况复杂，可以参考课本 (section 3.2.2)。

另外需要注意实现的细节，由于是模 $2$ 意义下的多项式，因此求余式多次取异或即可。

# 流量控制

流量控制很难独自出现，常伴随差错控制出现。

# 数据链路层的基本协议

# 理想单工协议

在数据链路层中，最理想的协议为理想单工协议 (Utopian Simplex Protocol). 其要求

Data are transmitted in one direction only (数据单向传输);
Both the transmitting and receiving network layers are always ready (信息发送方和接收方总是处于等待状态);
Processing time can be ignored (信号处理时间可以被忽略);
Infinite buffer space is available (缓存空间无限大);
The communication channel between the data link layers never damages or loses frames (通信信道不会损坏或丢失帧).

因此只需要考虑封装成帧环节。发送方每完成一个帧的封装，就发送一个帧。接收方亦持续处于等待接收状态。

下面是一个简单的实现：

	/* Protocol 1 (Utopia) provides for data transmission in one direction only,
	from sender to receiver. The communication channel is assumed to be error
	free and the receiver is assumed to be able to process all the input
	infinitely quickly. Consequently, the sender just sits in a loop pumping
	data out onto the line as fast as it can. */I
	typedef enum {frame_arrival} event_type;
	#include "protocol.h"

	void sender1(void) {
	frame s;
	packet buffer;
	while (true) {
	from_network_layer(&buffer);
	s.info = buffer;
	to__physical_layer(&s);
	}
	}

	void receiver1(void) {
	frame r;
	event_type event;
	while (true) {
	wait_for_event(&event);
	from_physical_layer(&r);
	to_network_layer(&r.info);
	}
	}

# 无噪信道上的单工停等协议

在理想单工协议中去掉缓冲区无限大的条件，即接收方可能来不及处理发送方发出的数据。这时候显然理想单工协议中的假设 2 , 假设 3 亦不再成立。这时，就得到了无噪信道上的单工停等协议 (Simplex Stop-and-Wait Protocol for an Error-Free Channel). 其包括以下两个基本假设：

Data are transmitted in one direction only (数据单向传输);
The communication channel between the data link layers never damages or loses frames (通信信道不会损坏或丢失帧).

这时的解决方案是让接收方向发方提供反馈 (feedback). 发送方每发出一帧，待接收方确认后继续发送下一帧。这样的协议称为停等协议.

注意，此时需要信道是半双工的 (half-duplex). 即信号可以在信道中双向传输，但不能同时传输。

下面是停等协议的一个简单实现：

	/* Protocol 2 (Stop-and-wait) also provides for a one-directional flow of data
	from sender to receiver. The communication channel is once again assumed to
	be error free, as in protocol 1. However, this time the receiver has only a
	finite buffer capacity and a finite processing speed, so the protocol must
	explicitly prevent the sender from flooding the receiver with data faster
	than it can be handled. */

	typedef enum {frame_arrival} event_type;
	#include "protocol.h"
	void sender2 (void){
	frame s;
	packet buffer;
	event_type event;
	while (true) {
	from_network_layer(&buffer);
	s.info = buffer;
	to_physical_layer(&s);
	wait_for_event (&event);
	}
	}
	void receiver2(void){
	framer s;
	event_type event;
	while (true){
	wait_for_event(&event);
	from_physical_layer(&r);
	to_network_layer(&r.info);
	to_physical_layer(&s);
	}
	}

# 有噪信道中的单工停等协议

将无噪信道上的单工停等协议进一步现实化，我们假设帧在信道中的传输可能出错或丢失。这样就得到了有噪信道中的单工停等协议 (Simplex Stop-and-Wait Protocol for a Noisy Channel) 对应的情况。此时可能存在如下三种问题：

帧错误
帧丢失
确认帧丢失

# 滑动窗口协议

滑动窗口协议是停等协议的延伸，其可以实现流量控制与可靠传输 (结合重传)。

单帧滑动窗口与停等协议
多帧滑动窗口与后退 $N$ 帧协议 (Go-Back-N protocol, GBN)
多帧滑动窗口与选择重传协议 (Selective Repeat)

# 数据链路协议实例

# 协议三要素

协议的三要素为：

语法 (Syntax): 数据格式和控制信息
语义 (Semantics): 收到信息时采取的特殊操作
同步 (Synchronization): 又称时序，是网络上对等实体间发送和接受信息的顺序

# HDLC 协议

向高层提供面向连接的可靠的服务机制 (connection-oriented reliable service)。

station 分类:

主站 (Primary):
从站 (Secondary):
混合站 (Combined):

主站和从站形成非对等的链路。主站控制全部操作。混合站之间形成对等的链路。

# HDLC 协议的帧结构

# HDLC 协议中的帧分类

HDLC 协议中的帧可以分为三类：

信息帧 (information)
监控帧 (supervisory)
无序号帧 (unnumbered)

# PPP 协议

PPP 协议全称点对点协议 (Point-to-Point Protocol, PPP). 是数据链路层上两对等节点间数据包传输的封装协议。

# PPP 协议的组成

PPP 协议主要由三部分组成：

链路控制协议 (Link Control Protocol, LCP)
网络控制协议 (Network Control Protocol, NCP)
成帧方法 (framing method)

# PPP 协议的帧格式

PPP 协议的帧格式如下表所示：

字节长度	1	1	1	2	$x$	2	1
含义	Flag ( `0x7E` )	地址域 (A, `0xFF` )	控制域 (C, `0x03` )	协议	负载 (payload)	帧校验域 (FCS)	Flag ( `0x7E` )

# DSL 协议

# MAC 子层

IEEE 802 委员会将数据链路层划分为下述两个子层：

媒体访问控制子层 (medium access control sublayer, MAC), 解决信道资源分配问题。
逻辑链路控制子层 (Logic Link Control sublayer, LLC).

其中，PPP 仅需要 MAC, broadcast 需要 LLC 和 MAC.

# 信道分配策略

信道分配策略可以 cult 分为两类：静态信道分配策略和动态信道分配策略。

静态信道分配策略包括频分复用、时分复用、波分复用、码分复用等复用策略。大多被物理层采用。在数据链路层，大多使用的策略是动态分配策略。

动态信道分配策略可以分为随机接入策略和控制接入策略两大类。

# 随机接入策略

随机接入策略 (Random-access protocols). 站间公平，不存在优先权。包括

ALOHA:
- Pure ALOHA: 任何用户可以随时发送数据，效率低下。吞吐量 $S = Ge^{-2G}$ . $S_{\max} = 18.4\%$ .
- Slotted ALOHA: 固定帧的发送时间。吞吐量 $S = Ge^{-G}$ . $S_{\max} = 36.8\%$ . 缺点是节点发送数据过于随机。
载波侦听多路访问协议 (Carrier Sense Multiple Access Protocols, CSMA):
- 1-persistent CSMA (1 - 持续 CSMA)
- nonpersistent CSMA (非持续 CSMA)
- p-persistent CSMA (p - 持续 CSMA)
- CSMA with Collision Detection, CSMA/CD (带冲突检测的 CSMA)
- CSMA with Collision Avoidance, CSMA/CA

Questions of CSMA:

When can the station access medium?
What can the station do if the medium is busy?
How can the station determine the success or failure?
What can station do if there is a conflict?

# ALOHA

# CSMA

# 1-persistent CSMA

1-persistent CSMA 的机制如下：

When a station has data to send, it first listens to the channel.
If the channel is idle, the station transmit its data immediately.
If the channel is busy, the station just waits until it becomes idle, and then transmits the frame.
If a collision occurs, the station waits a random amount of time and starts all over again.

# nonpersistent CSMA

nonpersistent CSMA 的机制如下：

A station senses the channel when it wants to send a frame.
If the channel is idle, the station transmit it
immediately.
If the channel is busy, the station does not
continually sense it and waits a random period of time and starts listening again.

非持续 CSMA 信道传输效率更高了，因为其在信道空闲时永远选择等待一段随机时间再进行发送。这样冲突的概率会降低，从而提高信道利用率。然而，伴随信道利用率提高的代价是传输时延增大。

非持续 CSMA 不同于 1-persistent CSMA 的一个特点是其在忙状态不会持续侦听信道，而是等待一个随机时间后单次侦听信道。

# p-persistent CSMA

前面的 1-persistent CSMA 和 nonpersistent CSMA 都是 p-persistent CSMA 的特例。其在信道空闲时，选择以概率 $p$ 发送帧，而以 $1-p$ 概率推迟到下个时隙进行。

# CSMA/CD

带冲突检测 CSMA(CSMA with Collision Detection, CSMA/CD) 是经典以太网的基础。

# Reference

这是一篇介绍 access protocol 的文章: Multiple access protocol: ALOHA, CSMA, CSMA/CA and CSMA/CD.

# 以太网

以太网 (Ethernet) 是一种局域网标准，对应 IEEE 标准为 IEEE 802.3.

按速度划分为：

标准以太网 (Classic Ethernet)
高速以太网 (High Speed Ethernet), 又称交换式以太网 (Switched Ethernet), 速度高于 10Mbps. 进一步可以分为以下几类：
- Fast Ethernet: 100Mbps
- Gigabit Ethernet: 1000Mbps
- 10 Gigabit Ethernet: 10000Mbps

# 以太网帧格式

以太网帧格式分为 DIX 格式和 IEEE 802.3 格式。其中 DIX 格式最早提出，更加常用。

两种帧格式如下 (长度单位为字节)：

DIX:
前导码 (Preamble) 目标地址源地址类型 (区分 DIX 与 802.3) 数据填充 (padding) 校验和
8 6 6 2 0~1500 0~46 4
IEEE 802.3:
前导码 (Preamble) 目标地址源地址长度数据填充 (padding) 校验和
8 6 6 2 0~1500 0~46 4

前导码 (Preamble)	目标地址	源地址	类型 (区分 DIX 与 802.3)	数据	填充 (padding)	校验和
8	6	6	2	0~1500	0~46	4

前导码 (Preamble)	目标地址	源地址	长度	数据	填充 (padding)	校验和
8	6	6	2	0~1500	0~46	4

填充位需要保证数据与填充的长度之和不小于 46 Bytes. 因此，一个以太网帧的最小长度为 64 Bytes, 最大长度为 1518 Bytes.

# 二进制指数后退算法

第 $i$ 次冲突后，从后续 $0\sim 2^i-1$ 个时间槽中任意选择一个再次发送的算法称为二进制指数后退算法 (binary exponential back-off).

# 以太网性能

$a = \frac{\tau}{T_0} = \frac{\tau c}{L}$

其中 $\tau$ 为传播时延 (propagation time), $T_0$ 为发送时延 (sending time), $L$ 为帧长度 (frame length), $c$ 为数据传输率 (data rate). $a$ 越小，信道利用率越高。

# WLAN

WLAN 即无线局域网)(Wireless LANs), 遵循 IEEE 802.11 标准。

主要研究其物理层和数据链路层的技术变化与特点。

# 体系结构

WLAN 协议的体系结构是有基础设施 (infrastructure mode) 的体系结构。其将客户端 (Client) 与接入节点 (Access Point, AP) 相连。Client 间的通信均需要借助 AP 进行转接。

基本服务集合 (Basic Service Set, BSS) 是一个 AP 所服务的 Client 组成的集合。

分布式系统 (Distributed System) 是用来连接不同 AP 的系统。其将多个 BSS 连接起来，称为扩展的服务集 (Extended Service Set, ESS).

# Ad-Hoc 模式

除前述有基础设施的模式之外，802.11 该提供了一种无基础设施的模式，称为自组织的网络 (Ad-Hoc)，即网络中各终端相互连接形成组网，是无基础设施 (infrastructureless mode) 的体系结构。其多用于军事及救灾环境中。

# 隐藏终端和暴露终端

隐藏终端和暴露终端是无线信号传输中特有的问题，其主要原因是不同信号站的无线信号传输范围不同，因而不能像有线信号一样可以互相听到对方。

# 帧分类

管理帧 (Management Frame): 用来进行节点的协调
控制帧 (Control Frame): 对帧信息进行确认，不携带数据字段，例如 RTS, CTS 及 ACK
数据帧 (Data Frame)

# 网络层

从源到目标主机进行 packet 的传输。

# 网络层的设计要点

分组封装 (packetizing/encapsulation).
路由选择 (routing): 路由协议不全是网络层的协议。
转发 (forwarding): 偏向动作的描述。
差错控制 (error control)
QoS 在网络层上加入 virtual layer, 用来解决网络安全问题。

网络层向传输层提供的服务决定其设计要点。其提供的服务应包括以下考虑：

服务应该独立于网络层的路由技术。
应向传输层屏蔽路由相关信息 (路由数量、类型和拓扑关系等)。
传输层的网络地址应存在统一编码方案。

# 存储转发型的分组交换机制

存储转发型的分组交换机制 (Store-and-Forward Packet Switching) 是不同路由器 (router) 的组网连接进行资源调度的机制。其提供两种服务：

无连接的服务 (Connection-less services): 采用数据报 (datagram) 进行数据交换。
- 是不可靠的网络，会出现失序 (out of order)、丢失 (lost)、错误 (destroyed) 的情况。
- 其代表是 IP 协议。
- 无连接服务实现的核心是路由算法，有如下特点：
  - 尽最大努力交付 (best effort delivery): 各个
面向连接的服务 (Connection-oriented services): 采用虚电路 (virtual circuit) 进行数据交换。
- 不会出现失序的情况，因为线路是唯一的。因此可以保障 QoS.
- 其代表是 X.25, Frame Relay, ATM 和 MPLS.

# 向传输层提供服务的目标

网络层向传输层提供服务包括以下三个目标：

向上提供的服务应该独立于路由器技术；
应该向传输层屏蔽路由器的数量、类型和拓扑关系；
传输层可用的网络地址应该有一个统一编址方案，甚至可以跨越 LAN 和 WAN.

# 路由算法

路由算法 (routing algorithm) 负责确定一个入境数据包应该被发送到哪一条输出线路上。

# 泛洪算法

# 拥塞控制

# 拥塞控制的概念

当网络中同时出现过多的数据包，导致数据包被延迟或消失，从而降低网络传输效率的情况称为拥塞 (congestion). 网络层和传输层承担拥塞控制的主要责任。

拥塞控制不同于流量控制。拥塞控制是对网络整体的控制方式，而流量控制则是点对点的控制。

# 拥塞控制的主要途径

拥塞控制包括如下主要途径：

流量感知的路由 (traffic-aware routing)
准入控制 (admission control)
流量调节 (traffic throttling)
负载脱落 (loading shedding)

# Internet 的网络层

我们主要研究 Internet 网络层的 IPv4 协议。

# IPV4

IPv4 的特点是不可靠，无确认，无连接。只进行数据封装。唯一的优点是协议机制简单。

路由策略：有路则走，无路则丢

引出了 ICMP、IGMP、ARP、DHCP 协议。

# IP 数据报首部结构

IP 数据报的 header 可以分为两部分：长度为 20Bytes 的固定部分和长度为 1~40Bytes 的可变部分。

# IP 地址

这里说的 IP 地址是 IPV4 的地址。其为 32 位长度的地址。为方便表示，每 8 位为一段采用点隔开，称为点分十进制记法。

# IP 地址分类

IP 地址可以分为 A, B, C, D, E 类地址。

A 类地址网络号字段长 8 位，主机号字段长 24 位，首位为 0 , 前 8 位为 0 至 127，最多容纳 $2^7-2 = 126$ 个网络 (网络号为 0000 0000 和 0111 1111 留作他用)。可用的主机号共 $2^{24}-2$ 个 (全 0 和全 1 的表示网络本身和全体主机)。
B 类地址网络号字段长 16 位，主机号字段长 16 位，首位为 10 , 前 8 位为 128 至 191.
C 类地址网络号字段长 24 位，主机号字段长 8 位，首位为 110 , 前 8 位为 192 至 224.
D 类地址为多播地址，首位为 1110 .
E 类地址为保留地址，首位为 1111 .

子网掩码

子网划分使路由表变大了。

无分类的两级编址。

动态分配 IP 地址。

# CIDR 技术

# NAT 技术

网络地址转换 (Network Address Translation, NAT) 用来实现网络私有地址和公有地址的转换。

# DHCP 动态分配技术

# IPv6

# ICMP 协议

# 概述

# 传输层的功能

# 传输层的寻址

# UDP 协议

UDP 协议全称用户数据报协议 (User Datagram Protocol, UDP), 是运输层上最主要的无连接传输协议。UDP 只在 IP 的数据报服务之上增加了以下功能：

复用 (multiplexing) 和分用 (inverse multiplexing)
差错检测

# UDP 的数据报格式

# UDP 的应用场景

# 实时传输协议 (RTP)

用于传输流媒体信息，在实时应用中采用。

# 实时传输控制协议 (RCTP)

用来处理流同步信息，为源提供反馈信息。

# TCP 协议

TCP 协议全称传输控制协议 (Transmission Control Protocol, TCP), 是运输层上最主要的面向连接的传输协议，用来解决在无连接、不可靠的 IP 数据报服务上需要可靠传输的场景。

TCP 协议的主要特点如下：

TCP 是面向连接的运输层协议
每一条 TCP 连接只能有两个端点 (endpoint)，每一条 TCP 连接只能是点对点的（一对一）。
TCP 提供可靠交付的服务。
TCP 提供全双工通信。
面向字节流
1. TCP 中的流 (stream) 指的是流入或流出进程的字节序列。
2. 面向字节流：虽然应用程序和 TCP 的交互是一次一个数据块，但 TCP 把应用程序交下来的数据看成仅仅是一连串无结构的字节流。

# TCP 可靠传输的工作原理

# 连续 ARQ 协议

连续自动重传请求协议