计算机网络概论复习(一)

博主： Rainshaw
发布时间：2019 年 04 月 06 日
835 次浏览
暂无评论
22498字数
分类：计算机网络概论

# 计算机网络概论

## 计算机网络的应用

- 商业应用: `Client-Server`服务模式
- 构建计算机网络的三个主要目标:
  
  1. 数据共享
  2. 个人信息共享
  3. 电子商务
- 家庭应用: `B:Business, C:Consumer, G:Goverment, P:Peer`
- 不采用点到点的通信的原因:
  
  1. 通信设备相距太远
  2. 通信链路数为终端数的平方,不实用
- 电路交换:
  每次呼叫建立一个专用电路
  是专用资源,不是共享的,可以保证性能
  需要考虑链路带宽和交换容量
  需要呼叫建立过程
- 分组交换:
  数据以离散的数据块形式在网络上发送
  统计复用——分组内部序列无固定模式
  多个用户处于同一分组,共享网络资源
  每个分组使用全部的链路带宽,资源按需使用
  会出现资源竞争,拥塞——分组排队等待
  节点接受整个分组后才转发
- 分组交换细节:
  
  1. 内容: 消息或者报文
  2. 分组: 网络上交换数据的基本单位
     分组头: 源地址、目标地址
  3. 帧: 在链路上传输数据的基本单位
     帧头、帧尾: 地址、序号、校验位
  4. 发送过程:
     1. 发送端: 先将长报文划分为较短的、固定长度的数据段,每个数据段前添加首部构成分组
     2. 分组交换网以“分组”作为数据传输单元,以此把各分组发送到接受端
     3. 接收端收到分组后剥去首部还原为报文,最后再组合起来
- 分组交换的特点:
  优点:
  
  1. 高效: 动态分配带宽,逐段占用通信链路
  2. 灵活: 以分组为单位传输、存储和转发,各链路速率可以不同
  3. 迅速: 不必先建立连接,直接想其他主机发送分组,充分利用带宽
  4. 可靠: 网络协议与路由选择协议提高网络的生存性
  
  缺点:
  
  1. 存储转发时需排队,增加时延
  2. 分组增加首部,加大了开销
- 分组交换与电路交换对比:
  分组交换更适用于突发数据,且资源共享,无需事先建立连接,但存在拥塞问题,增大延时和丢包率
- 分组交换的时延: 处理时延、排队时延、发送时延、传播时延
- `Entity`实体——表示发送或接收信息的硬件或软件
- `Protocol`协议——通信实体之间的规则和约定
- `Peers`对等体——不同机器上构成相同层的实体——对等体使用协议相互通信
- `Interface`接口:定义下层向上层提供哪些原语操作和服务
- 数据并非在两台机器的第n层之间直接传输,而是每一层将数据和控制信息直接传递给下层,一直至最底层
- 设计问题: 可靠性、检错、纠错、路由、协议分层、寻址、互联、可扩展、资源分配、流量控制、拥塞控制、服务质量、网络安全
- 每层向其上层提供两种服务:
  
  1. 面向连接的服务: 电话模式、呼叫虚电路——信令
  2. 无连接的服务: 因特网模式——无呼叫建立过程、不维护端对端的连接状态
- 服务原语——一个服务由一组原语说明,用户进程通过原语访问该服务.原语告诉服务要执行某个动作.
- 服务是一层向其上层提供的一组原语(操作),服务定义了该层准备代表用户执行哪些操作,但并不包括如何实现
  协议是一组规则,规定了对等实体之间所交换的报文格式和含义
  服务和协议是完全独立的
- 网络体系结构模型:
  应用层——提供网络应用、传输层——进程之间的数据传输、网络层——源到目的之间的数据报路由、链路层——临近网络部件间的数据传送、物理层——在线路上传输的位
- `OSI(Open Systems Interconnection)`模型的概念
  
  1. 服务: 每一层向上层提供某些服务
  2. 接口: 告诉上层如何访问本层,规定了参数以及结果,没有说明本层是如何工作的
  3. 协议: 协议是内部的事情,可以使用或改变任意协议,只要能完成既定的任务,不影响上面的各层
- 网络标准化:
  
  1. 电信领域: 国际电信联盟`ITU`有三个部门 `-T`电话电报数据接口 `-R`无线电通信分配无线频率 `-D`发展部门
  2. 著名的国际标准化组织: 国际标准化组织`ISO(International Organization for Standardization)`,电器和电子工程师协议`IEEE`
  3. 因特网标准: `IEEE`, `RFC(Request For Coments)`
- 互联网标准: `802.3`——以太网、`802.11`——无线局域网、`802.15`——蓝牙&Zigbee、`802.16`宽带无线

## 物理层

- 物理层: 定义了为建立、维护和拆除物理链路所需的机械、电气、功能和规程等特性,其作业是使比特流能在物理介质上传输.
- 提供以下服务:
  1. 提供传送和接收比特流的能力,物理连接的建立、维持和释放
  2. 在两个相邻系统之间唯一地标识数据电路

### 数据传输理论: 信道传输等限制

- 通信系统的一般模型
  ![5cd5391c97dcd.jpg][1]
  数据(`data`)——携带信息(即比特)的实体; 信号(`signal`)——信号是表示消息的物理量,随时间变化
- 通信系统的主要参数
  1. 信号功率`S`,单位为瓦特(焦耳每秒`W`)
  2. 信号带宽`B`,单位为赫兹(`Hz`): 与收发设备及传输介质的特性有关
  3. 噪声功率`N`: 通信线路上的平均噪声功率
  4. `SNR`: `S/N`是信噪比,单位为分贝(`dB`), $SNR_{dB}=10\log_{10}(S/N)$
  5. 数据率,单位为`bps`: 数据传输速率
  6. 误码率: 数据传输错误的概率,衡量数据传输的质量,单位为 $1\times10^{-n}$
- 信号分析方法——傅立叶变换: 任一个周期为T的函数`g(t)`,可以用傅立叶级数来表示
  $g(t)=\frac{c}{2}+\sum_{n=1}^\infty a_n\sin(2\pi nft)+\sum_{n=1}^\infty b_n\cos(2\pi nft)$,
  $\int_0^T\sin(2\pi kft)\cos(2\pi nft)=\delta_{k,n}\frac{T}{2}$
  $a_n=\frac{2}{T}\int_0^Tg(t)\sin(2\pi nft)dt, b_n=\frac{2}{T}\int_0^Tg(t)\cos(2\pi nft)dt,c=\frac{2}{T}\int_0^Tg(t)dt$
- 信号带宽受限: 各频率分量的幅度$\sqrt{a_n^2+b_n^2}$表示信号传输的能量
- 传输带宽会影响数据率,正相关, 传输带宽与通信设备、传输介质有关
- 传输带宽: 传输中幅度衰减不明显的频率范围;定义为接收功率由最大将为1/2(3dB)的频率范围
- 奈奎斯特定理: 在理想无噪声的信道条件下最大数据率$=2B\log_2V$,其中B为信道带宽,V为信号中的状态数
- 香农容量公式: 信道极限信息传输速率或无误码容量C遵从公式: $C=B\log_2(1+S/N)\ b/s$

### 传输介质: 常用传输介质的特性

- 双绞线:(STP)屏蔽双绞线, (UTP)无屏蔽双绞线, 传输距离为100米, 可传数字信号和模拟信号
  
  | Type(Category) | 1 | 2 | 3 | 4 | 5 | 5e | 6 | 7 |
| :- | :- | :- | :- | :- | :- | :- | :- | :- |
| Use | Voice Only | Data to 4Mbps | 10Mbps | 20Mbps | 100Mbps | 100Mbps | 250MHz | 600MHz |
| Where | Telephone Wire | Local Talk | Ethernet | 16Mbps Token Ring | Fast Ethernet | Fast Ethernet | Gigabit Ethernet |   |
  
  
- 同轴电缆:
  
  1. 系带同轴电缆:阻抗匹配$50\Omega$,用于数字信号传输
     1. 粗缆10Base-5,单段最长500米,最长5段2.5公里
     2. 细缆10Base-2,单段最长185米,最长5段925米
  2. 宽带同轴电缆:阻抗匹配$75\Omega$,用于电视信号传播
- 光缆: 由传导光波的高纯石英玻璃纤维和保护层构成,全反射原理,多根光纤封装在坚固的外壳中构成多芯光纤
- 光发射系统:
  
  1. 光源: LED(发光二极管),ILD(注入型激光二极管),光信号的有无表示1和0
  2. 检测器: 接收端由光电二极管构成的光检测器将光信号转换成电信号
- 光纤的连接: 机械式0.1dB快速无需特殊设备, 熔结,极低损耗0.05dB,昂贵的特殊设备,长距离链路唯一方法
- 无线传输: 中频0.3-3M、高频3-30M、甚高频30-300M、超高频0.3-3G 用于移动通信, 特高频3-30GHz用于数字通信
- 微波,利用抛物面天线聚集能量可沿直线实现视距传输(LOS),具有很高的信噪比
  可以利用地面传播,地波传播——2MHz以下平行地表传播,天波传播——2-30MHz在地面与大气层之间来回反射

### 数字调制技术: 比特与信号间的转换技术及常见通信系统

#### 基带传输

- 带宽效率——与一个符号承载的比特数有关:
  1. 符号电平数多,则承载比特也多, 如8电平的符号可以表示3比特
  2. 符号率: 信号改变的频率,单位为波特率,若带宽为B,则符号率为2B
- 非归零码NRZ(Non-Return-Zero): 0为高电平,1为低电平
  - 时钟恢复: 根据跳变来恢复时钟,可能因长时间发送0或1导致信号电平无跳变,导致收发之间难以同步
  - 信号平衡(基线漂移):用接受信号的平均值确定信号电平的高低,连1或连0会改变信号均值
  - 对于NRZ,若带宽为B,则数据率为2B
- 非归零反转码NRZI(NRZ Inverted):是一种差分编码
  - 信号跳变表示1, 无跳变表示0
  - 解决了连1问题,未解决连0
  - 弱带宽为B,则数据率为2B
- 曼彻斯特编码(Manchester Encoding)
  - 发送0时,电平从高到低跳变, 发送1时,电平从低到高跳变
  - 每比特时间必有一次电平跳变,接受方通过检测该跳变实现与发送方的位同步
  - 带宽为B,则数据率为2B
- 差分曼彻斯特编码
  - 在每位信号起始处,没有跳变表示1,有跳变表示0,
  - 每比特时间仍有一个跳变用来同步
  - 需要更复杂的设备,有更好的抗干扰性
- 4B5B编码
  - 4比特数据用5比特编码,保证码组前部最多1个0,尾部最多2个0,即码流中连0不超过3个
  - 对码组再用NRZI编码,每5比特至少有2个1,即有两次跳变
  - 4B5B的编码效率为80%, 用于100Mb/s以太网和光纤分布式数据接口FDDI

#### 通带传输

- 由于基带信号在信道上长距离传输会受到衰减、畸变和噪声影响,低频信号不适合远距离传输, 各个传输介质有其适于的信号频率范围, 需要将数字信号转换成一种适合于在信道上传输的信号,称转换过程为调制(modulation);相应的,从信号中提取数字信号的过程称为解调(demodulation)
- 调制解调器(MODEM)就是调制器(MOdulator)和解调器(DEModulator)的组合
- 数字调制技术:
  - 用$A\sin(2nft+\Phi)$表示正弦信号,使A,f或$\Phi$随基带信号而变化,称为对载波进行调制
  - 基本调制方法: 调幅(AM), 调频(FM), 调相(PM)
- 调幅: 在幅度调制中,两个不同载波信号的幅值分别代表0和1,有时也用恒定幅度的载波的有和无代表1和0
- 调频: 频率调制是用两个不同频率的载波分别代表0和1, 抗干扰能力优于调幅,但频带利用率不高,常用于传输低速数字信号
- 调相: 相位调制是用不同相位的载波分别表示0和1, BPSK
- 调制: QPSK正交相移键控:用信号的45度135度225度315度表示2比特
  - 联合信号的幅度和相位,使一个符号表示更多比特,黑点表示合法的幅度和相位
  - QAM正交振幅调制 QAM-16,振幅相位16种组合,可表示4比特
    ![5cd5391ca0665.jpg][2]
  - 调制星座图: 数字通信中,将数字信号表示在复平面上,给出信号及信号之间的关系的图示就是星座图

### 信道复用: 在一条传输介质上提供多个数据传输信道的方法

#### 频分复用 FDM(frequency division multiplexing)

- 信号在同样时间占用不同频段
- 当信道带宽B为基带调制信号带宽的N倍时,将信道分割为N个子信道,在每个子信道上传输一路基带信号
  - 子信道之间有保护间隔
  - 基带滤波器
- 用各路基带信号调制不同频率的载波,将各路信号搬移到各个子信道上
- 举例: 广播系统、电话系统、电视系统

#### 时分复用 TDM(time division multiplexing)

- 信号在不同时间占用同样的频段
- 所有用户占用同样频段的不同时隙,组成信道传输的帧
- 用户按照“轮”来访问信道,每一轮,每个用户得到固定长度的时隙
- 用户之间需要同步, 需要在时隙之间设置保护间隔,应对同步偏差和远近效应
- 举例: 电话系统骨干网中数据传输,第二代蜂窝无线通信系统,以太网中的数据传输

#### 码分复用 CDM(code division multiplexing)

- 从代码集$C_k$中选取特有的“码序列”分配给每个用户,码序列特点是

$$
\frac{1}{m}\sum_{i=1}^mC_{ki}C_{ji}=\delta_{k,j}
$$

- 所有用户共享相同频率,但每个用户用其特定码序列对数据进行编码或调制,允许多个用户“共存”并同时传输,具有最小的干扰,因为“码”是正交的
- 编码信号=原始数据x码序列, 解码信号=编码信号x码序列
  ![5cd5391ca9ea8.jpg][3]
- CDMA(Code Division Multiple Access) 码分多址,是无线广播信道的标准,扩展了频谱,通常码片速率为信息速率的m倍, 编码信号=原始数据x码片序列
- 原始数据经CDMA编码后,信号频谱被展宽,称为扩频,例如原始10Kbps,100倍扩频后码速率为1Mbps
- 展宽的信号频谱不易被检测,已知码序列才能解调数据,因此扩频通信具有保密性

#### 各子载波正交 OFDM(Orthogonal frequency division Modulation)

- M是调制不是复用, 其方法时:在某一子载波的中心采样,则其他正交子载波的干扰为0
- 用基带数据调制一个正交频率子载波, 子载波之间没有保护间隔,更有效地利用带宽(最大的频谱效率), 要求子载波间严格正交,接收频率严格对准

#### 对比

- FDMA:抑制带外信号,需设置保护频段
- TDMA:各信号严格同步,需设置保护时间间隔
- CDMA:需要功率控制
- OFDM:需要各子载波频率正交,接发频率对齐

#### 单双工

- 单工: 信道只能在一个方向上传输数据
- 双工(duplex): 信号可以在两个方向上同时传输数据
  1. TDD(Time Division Duplex)——时分双工
  2. FDD(Frequency Division Duplex)——频分双工
  3. CDD(Code Division Duplex)——码分双工

#### 脉冲编码调制 PCM(Pulse Code Modulation)

- 脉冲编码调制PCM是将模拟信号变换为数字信号的方法,包括采样、量化和解码三个步骤
- 编解码器codec
- 采样: 奈奎斯特定理,若模拟信号带宽为WHz,则采样频率为2W时,足以捕获模拟信号的信息
- 量化: 对取样点信号幅值分级取整
- 编码: 将量化后的整数值用二进制表示

#### TDM复用——T1标准

- 长距离链路TDM传输语音和数据混合信号,24个信道总数据率为1.544Mbps, 每个信道8位数据(7语言1信令),数据率位56(7x8)Kbps
  ![5cd5391cc9eb0.jpg][4]
- T1总速率 [(7+1)x24+1]x8k=193bx8k=1.544Mbps E1:2.048Mbps=8x32x8K(32个子信道,30个语音,2个控制信号及帧同步)
- PDH(Plesiochronous Digital Hierarchy)准同步数字系列,各路时钟频率有一定偏差,复接时需插入一定脉冲实现同步
- SDH(Synchronous Digitial Hierarchy)同步数字系列, SONET(Synchronous Optical NETwork同步光网络), 系统由一个精度$10^{-9}$的时钟控制,精准同步,易于复接和分接

#### SONET/SDH 速率和复用

- SONET基本信道, $125\mu s$传输810字节(90列x9行),数据率=8bit x 810Byte x 8KHz=51.84Mbps 称为STS-1同步传输信号
- 多路STS-1复用:3路STS-1合成为STS-3.155.52Mbps,STS-n的光纤线路称为OC-n,从 OC-3开始 称作同步传输模块STM-1,

#### GSM

- 25MHz, FDM将25MHz分为124个信道,每个信道200KHz,再在每个子信道用TDM
- 手机发送频率比接收频率高45MHz

## 数据链路层

### 组帧及检错

#### 数据链路层

- 结点(node):主机及路由器
- 链路(link):连接**相邻**结点之间的通信信道,可分为有线链路、无线链路
- 帧(frame):在数据链路上传输数据的基本单位,用于承载数据
- 数据链路层: 负责在**一个结点与其相邻结点**之间经过一条链路传递数据
- 在每个主机中,链路实现是在适配器,即网卡(NIC)——网卡实现链路层及物理层,与主机的系统总线连接,是软件硬件及固件的结合,可分为以太网卡、PCMCI网卡、802.11网卡
- 适配器之间通信: 发端——将数据封装成帧,增加校验位,接收地址,实施流量控制等; 发端——检查错误,检查接收地址,实施流量控制等,提取数据,交由高层处理
  ![5cd5391ceb181.jpg][5]

#### 成帧——同步、透明传送

- 同步: 计算机之间的通信需要收发双方协调发送和接收之间的动作
  1. 异步传输: 以字符为传输单位,字符之间的时间间隔是可变的,而字符中的位则以固定速率传送.
     - 起停位、数据为、校验位
     - 传输字符之间无固定时间间隔
     - 接收时钟与发送时钟存在偏差
     - 特点: 简单、廉价、每帧一个字符
  2. 同步传输: 发送和接收之间的每位都是同步的,接收端从接受的信号中提取时钟,以保持与发送信号的时钟同步
     - 以数据块位传输单位
     - 要求时钟同步——提供时钟线给接收端或从接收信号中提取时钟
     - 适用于长距离的数据传输,效率高
     - 举例: 以太帧——同步码:8个字节,前7 用于帧的位同步,最后1个是帧开始定界符,表示后面的信息是MAC帧
       ![5cd5391d02acc.jpg][6]
- 帧是链路层的基本单位,用于承载链路层的数据、实施差错控制
- 异步传输中的起始停止位、同步传输中的同步位之后需要确定帧开始.
- 成帧方法:
  1. 字节计数法: 利用头部的一个字段来标识该帧的字节数
     - 问题:若头部字节出错,则会失去同步
     - 解决:若能将一个**特殊的字节**作为帧的首尾标志,则帧失步后可以重新同步
  2. 封装成帧: 在一段数据的前后分别加首部“SOH”(0x01)和尾部“EOT”(0x04),构成一个帧
     - 首部和尾部的作用就是帧定界
     - 问题: 若帧数据部分含有帧头或帧尾,则会导致同步出错,遗失信息
     - 解决:
       1. 字符填充实现透明传输:
          - 发送端若在数据中出现“SOH”或“EOT”,则在其前面插入一个转义符“ESC”(0x1B).
          - 接收端将数据送往高层之前删除插入的转义符.
          - 若转义符也在数据中出现,则在转义符前插入一个转义符,当接收段收到连续两个转义符时就删除一个
            ![5cd5391e40b9c.jpg][7]
       2. 用比特填充实现透明传输:
          - HDLC,帧标志位F为01111110,采用零比特填充,
          - 数据中某一段比特组合恰好和F一样时,
          - 发送端在连续发送5个连1后,填入一个0比特再发送出去,
          - 接收端将5个连1之后的0比特删除,恢复原帧
            ![5cd5391e5fa9e.jpg][8]

#### 差错控制技术:检错及纠错

- 差错: 数字通信系统中接收位与发送位不一致
- 信道误码率: $P_b=$误码位数/发送总位数
- 若误码率为$P_b$,帧长为L位,则无差错帧的概率为$P_1=(1-P_b)^L$
- 差错检测: 在信息位中加入冗余位——编码
  - 信息位:要发送的数据
  - 冗余位:按某种关系对信息位运算所得到的数据
  - 发送过程:信息位+冗余位,构成**码字**,发送码字
  - 接受过程: 检查信息位和冗余位之间的关系(校验过程),以发现传输过程是否初心啊差错
- 奇偶校验
  - 增加冗余位,使码字中的1的个数为奇数或偶数个,称为奇(或偶)校验
  - 一维奇偶校验: 检测单比特错,无法纠错
  - 二维奇偶校验: 检测并纠正**单**比特错
- 检错码: 能自动发现差错的编码,如奇偶校验码、循环冗余码CRC(Cyclic Redundancy Code)
- 纠错码: 不仅能发现差错而且能定位差错的位置:,如汉明码、卷积码等
- 汉明距离(码距)为两个码字中不相同位的个数
- 编码就是增大码距,解码就是找出距离码字最近的码字
- m位信息+r位校验,在$2^{m+r}$中仅传输$2^m$种码字,码距大于1,码字空间稀疏
- 码距与检错、纠错能力的关系（当d≤4）
  1. 若码距d为奇数,则能发现d-1位错,或能纠正(d-1)/2位错.
  2. 若码距d为偶数,则能发现d/2位错,并能纠正(d/2-1)位错.
- 若要检测d位错,则需要码距为d+1,若要纠正d位错,则需要码距为2d+1
- 码率: 衡量编码效率——若码长为n的码字中含有信息位m位,则码率=m/n
- 理论上, m位信息位,r位校验位,则$m+r+1\leq2^r$,给出了纠1位错r的下界
- **纠错码**——汉明码:
  - 校验位:(p1,p2,p4,p8,p16,...)r位,位于$2^n$,n=0,1,...,r-1
  - 信息位:(m3,m5,m6,m7,m9,...)m位
  - 第K位信息的校验位来自2的幂次只和,如5=1+4
  - 例如(7,4)汉明码,码长7,信息位4,校验位3
    - 信息位m3=p1+p2,m5=p1+p4,m6=p2+p4,m7=p1+p2+p4
  - 根据校验位的计算结果,可以定位差错的位置——纠1位错
- **检错码**——交织与校验和
  - 码字的检错能力有限,如奇偶校验码,汉明码只能纠检1位错
  - **突发长度**:在码字中第1位错与最后1位错之间的间隔
  - 交织:将信息位组成n列k行,按列计算校验位,按行顺序发送,只要突发长度$\leq$n,则可以检错,
    - 实现最多只有1位错
  - 校验和:对发送数据位计算校验和,接收端实施同样运算以检错,例如IP头、UDP报文
- **检错码**——循环冗余校验CRC
  - d位数据,组成一个二进制数D, 选择r+1位生成式G,计算r位的CRC位R
  - 发送端使<D,R>能被G整除(模2),计算端已知G,用<D,R>除以G,若余数为0则保留,否则出错
  - 可以检测所有突发长度小于等于r位的错误
  - 用于Ethernet,802.11WiFi,ATM
  - 编码效率高
    - G(X)能检出所有1比特错,因为G(X)不含$X^i$因子即含1
    - G(X)能检出所有2比特错,因为G(X)不含$X^i$因子且对任何$0< e \leq n-1$的e除不尽$x^{e+1}$
    - G(X)能检出所有奇数位错,因为G(X)含因式(X+1)
    - 能检出所有长度小于等于CRC长度的突发错
    - 易于硬件实现——移位、异或
    - 举例: CRC-12 $X^12+X^11+X^3+X^2+X+1$
- 差错控制方法:
  1. 前向纠错FEC(Forward Error Correction):采用纠错码,接收端发现差错并纠正
     - 纠错编码模型——发送端纠错编码送信道传输,接收端接收信号译码,检测到错误自动纠正
       ![5cd5391e7084e.jpg][9]
     - 优点: 无需反向信道、单工即可,也可用于一对多的通信
     - 缺点: 译码设备复杂,为纠错需附加冗余码
  2. 自动请求重传ARQ(Automatic Repeat reQuest): 接收端检测到错误时,通知发送端重传,直到收到正确的数据
     - 模型——发送端将数据发向信道,同时缓存数据.如果接到重发请求,则将放入缓存器的数据重新编码发送,接收端判决,如果接收正确则发送ACK,若检测到错误则发送NACK,要求重发.
       ![5cd5391e87e8f.jpg][10]
     - 三种ARQ方式:停发等候重发、返回重发、选择重发
  3. 混合纠错HARQ(Hybrid ARQ)检错码+纠错码
     - 若发现差错但在纠错范围内,则直接纠错; 当超出纠错能力时,则要求发端重传
  4. 对比
     FEC不需要重传,实时性好,常用于无线链路
     ARQ常用于计算机网络
     ![5cd5391e90b57.jpg][11]

### ARQ

- 基本的数据链路层协议
  - 检错及纠错:在帧头增加控制信息,帧尾增加帧校验
  - 定义一系列函数,例如:`wait_for_event(&event); event表示发生的事件`
  - 发送方:发送帧给另一主机
  - 接收方:收到数据后计算帧校验,设置event
    - 若有错,则event=chksum_err;否则event=frame_arrival
- 停等协议:
  - 发送端发送数据时同时缓存;当收到确认帧后,才清除
  - 只有收到确认帧ACK后,才发送新的数据帧
  - 接收端受到数据帧后,发送确认; 若时新数据帧,则保存;若为重复帧,则丢弃
  - 发送端自动对错帧重传,因此称为自动请求重传ARQ
  - 信道利用率:
    - 设数据帧长 $l_f$(bit) ,数据发送速率$R$(bit/s), 则一个数据帧的发送时间$t_f=l_f/R$
      ![5cd5391e9d7b6.jpg][12]
    - 数据帧发送后若经过重传时间还没有收到确认帧,则重传数据帧,设重传时间为
      
      $$
      _{out}=t_p+t_{pr}+t_a+t_p+t_{pr}
      $$
    - 一般处理时间$t_{pr}$和确认帧发送时间$t_a$远小于传播时延$t_p$,故忽略他们,得到$t_{out}=2t_p$
    - 定义$\alpha=t_p/t_f$,表示传播时间(即延迟)与帧发送时间(为带宽倒数)之比,则信道利用率
      
      $$
      =t_f/(t_f+2t_p)=1/(1+2\alpha)
      $$
  - 优点: 简单
    缺点: 信道利用率不高,尤其不适于再长时延的信道上采用
- 连续ARQ:
  - 发送发连续发送多个分组,不必每发完一个分组就停下来等待确认,提高了信道利用率
  - 若延迟为$t_p$,带宽为帧率$1/t_f$(单位时间发送的帧数), 则延迟带宽积为$\alpha=t_p/t_f$
  - 若可连续发送的帧数为w,则利用率$\leq w/(1+2\alpha)$
  - 接收确认帧ACKi表示期望收到的下一个帧的序号是i
  - 接收端: **按序接收**数据帧
  - 发送端: 收到ACKn时取消n-1的计时器, n计时器超时时,重传第n个数据帧
  - 又被称为**Go-back-N** ARQ
- 滑动窗口:
  - 发送端和接收端分别设置发送窗口和接收窗口
  - 发送窗口WT用来对发送端进行流量控制,表示发送端最多可发送的数据帧数量
  - 接收端只接收发送序号落入接收窗口的数据帧
  - 连续ARQ中,接收窗口WR=1,收发两端窗口不断向前滑动,协议又称滑动窗口协议
  - 若WT=1,则为停止等待协议
  - 当帧序号用n个比特编号时,若接收窗口为1,则发送窗口$W_T\leq 2^n-1$
- 选择重传ARQ:
  - 增大接受窗口WR, 接受序号不连续但仍在接收窗口的数据帧,等收到缺失序号的数据帧后再送交主机
  - 避免重传正确到达接收端的数据帧,但需要接收端有缓存
  - 若用n比特编号,则接受窗口最大为$W_R\leq2^{n-1}$
- 捎带确认与累计确认:
  - 累计确认:接收端不是每收到一个数据帧就发送一个确认帧,若确认序号为i,则表示 (i-1)及之前的所有数据帧均被确认,且期望收到的下一个帧的序号为i.
  - 捎带确认:当接收端向发送端发送确认信息时,如 果同时存在需要发送的数据,那么可以将确认信息和数据合并在一个帧中发送

## MAC

### 信道分配与多路访问协议

一个共享信道, 两个或更多结点同时发送:干扰,碰撞:如果同时接收到两个或两个以上的结点的发射信号

- 介质访问控制MAC(Medium Access Control):
  - 决定结点如何共享信道,确定下一个使用信道的结点
  - 信道共享的控制必须使用自身的信道
  - 与信道复用的区别:
    MAC:关注多个用户如何使用共享的信道 ,分配算法
    信道复用:关注信道如何划分为多个信道,TDM、FDM、CDM、OFDM
- 划分信道
  - 将总的信道资源分割为更小的信道(时隙,频率,码字)
  - 为需要使用信道的结点分配信道资源
  - 通常需要一个信道分配中心,信道资源集中控制
- 随机接入
  - 不分割信道,允许碰撞
  - 接收端避免碰撞

#### 划分信道

- 时分多址TDMA(time division multiple access)
  
  - 按照“轮”来访问信道, 在每一轮,每个站得到固定长度的时隙(长度=分组发送时间)
  - 未使用的时隙成为空闲的
  - 实现问题:需要时隙同步;设置保护间隔
- 频分多址FDMA(frequency division multiple access)
  
  - 将信道划分为频段, 为每个站分配固定的频段
  - 不传输信号,则频段为空闲的
  - 实现问题:需要带通滤波器,设置频率保护带
- 静态信道分配
  
  - 传统的复用技术(FDM,TDM等),N个用户N个信道,信道数与用户数相同
  - 面临的问题:用户数量很多且动态变化,例如当每个用户的数据为突发时
  - 将信道划分为N个独立的信道,降低了信道效率
  - 信道容量为C ,帧的平均长度为$1/\mu$ b,平均到达率为$\lambda$帧/s,
    平均延迟时间为$T=\frac{1}{\lambda-\mu C}$
- 动态信道分配
  
  - 划分信道,增大了平均延迟,降低了信道利用率
  - 对于数据突发业务,N的数量动态变化,需要一种动态信道分配技术
  
  1. 随机访问控制: 当结点有分组要发送时,以全信道速率R发送分组,结点之间没有优先级协同
     
     - 两个或两个以上的发送结点——碰撞
     
     1. ALOHA:
        - 假设:
          帧长度相同,发送时间为1;
          各个站不需要同步;
          一个帧到达时,就立即发送
        - 那么在$t_0$时刻发送的帧将与发送时刻位于[$t_0$-1,$t_0$+1] 的帧碰撞
        - 效率:
          当 N -> 无限,**最大利用率 = 1/(2e) = 0.18**
     2. 时隙ALOHA
        - 假设:
          帧长度相同、信道时间划分为相同的时隙(每个时隙发送一个帧)、
          结点只有在时隙开始时刻才能发送,以降低碰撞的概率、
          结点之间是同步的、
          若在一个时隙中有2个以上的结点同时发送,所有结点都可以检测碰撞
        - 当结点得到一个新的帧,则在下一个时隙发送
          - 若没有碰撞:结点可以在后续时隙发送新的帧
          - 若碰撞:结点在后续时隙中以概率p重传该帧,直到成功发送
        - 效率(成功发送的时隙比率):
          当N趋于无穷时,**最大效率 = 1/e = 0.37**
        - 优点:
          - 一个活动的结点可以 以全信道速率连续发 送数据
          - 非集中式:只是结点 的时隙需要同步
          - 简单
        - 缺点:
          - 碰撞,浪费时隙
          - 空闲时隙
          - 结点在发送数据之前 不能够检测碰撞
          - 时钟需要同步
     3. 载波侦听CSMA(Carrier Sense Multiple Access)
        - 结点在发射信号前测试信道状态,如果信道空闲(即没有检测到载波),则按照以下算法来发送.
          - 1-坚持CSMA(1-persistent CSMA)
            当信道空闲时，以概率1发送
          - 非坚持CSMA(non-persistent CSMA)
            若信道忙，则等待一随机时间，之后再进行载波侦听
          - p坚持CSMA(p-persistent CSMA)
            若信道空闲，则以概率P在当前时隙发送，而以概率1-p推迟到下一时隙发送
        - 在低负载时，采用1坚持CSMA，吞吐率高于ALOHA的;在高负载时，非坚持更好;非坚持CSMA峰值吞吐率约比1-坚持CSMA高2倍
          ![5cd5391ebcb39.jpg][13]
        - 仍然可能发送碰撞:传播延迟致使两个结点无法听到对方发送的信号
        - CSMA/CD (碰撞检测)
          - 在短时间内做碰撞检测
          - 终止有碰撞的发送, 降低信道的浪费
          - 易于在LAN中实现:测量信号强度，比较发送、接收信号
          - 难于在WLAN中实现:接收信号很小，而发送信号很大
  2. 无冲突协议
     碰撞降低了带宽、增加了帧的发送时延
     通过竞争方式预约信道，而在预约的信道上用无冲突的方式传输数据
     
     - 位图协议(预约协议reservation protocols)
       - N个站，每个站的地址为0~(N-1)，忽略传播延迟
       - 每个竞争周期有N个时隙
       - 第j号站有帧要发送时，则在时隙 j 发送比特1预约 时隙，不允许其它站在该时隙发送
         要求各站在预约时隙的尺度上是同步的
       - 经过预约时隙后，每个站都知道哪些站要发送，每个站按顺序发送帧
       - 低负载时的信道利用率: 平均等待时间为N个时隙
       - 高负载时的信道利用率: 平均延迟:排队时间+N+(N-1)d
     - 轮询
       - 主结点邀请从结点按序发送,典型地用于主从式通信环境
       - 问题:轮询的开销、延迟、主结点故障
       - 令牌环:控制令牌依次经过各个结点、携载信息
         - WLAN中的PCF方式
  3. 有限竞争协议
     降低竞争的站数，则增加了获得信道的概率
     有限竞争协议是适当调整竞争站点数
     
     - 将结点划分为组
     - 第0组的成员只允许在第0时隙竞争
     - 若某个站竞争成功，则其占用信道并发送帧;若发生碰撞，则第1组的成员继续在第1时隙竞争

### 以太网与WLAN

#### IEEE802.3 以太网:CSMA/CD

- 总线型:用同轴电缆连接，或用双绞线通过集线器连接
  所有的节点在同一碰撞域，节点之间相互碰撞
- 星型拓扑
  交换机:位于中心
  每个链路执行以太网协议，节点之间不再相互碰撞
- ![5cd5391ed8c0e.jpg][14]
  - 8个字节前导码:前7字节是同步码，实现帧的位同步，最后1个字节是帧开始定界符，表示后面的信息是MAC帧
  - 地址字段:目的地址首位为0的为普通地址，为1的为组播地址;全1的为广播地址;源地址前3字节为组织标识符，分配给网络制造商
  - 类型字段:通知接收方帧内包含的协议类型
  - 数据字段:最小长度 (64-18) 字节，不足时，插入填充字段
- 以太网以多点接入方式共享总线资源, CSMA/CD:Carrier Sense Multiple Access with Collision Detection，载波监听多点接入/碰撞检测
- $\tau$为端到端传播时延，发送数据帧后最多经过$2\tau$后,可判决是否发生碰撞;$2\tau$称为争用期
  - 发生碰撞后，推迟一个随机时间再发送;退避时间由二进制指数退避算法决定
  - 基本退避时间取$2\tau$
  - 重传次数为k，每次退避后，K累加k = Min[k+1,10]
  - 随机选取一个数r， r$\in$[0,1,...,($2^k-1$)]
  - 重传时延为 r×2$\tau$
  - 当重传10次仍不成功，则丢弃该帧并通知上层
- 以太网的争用期为51.2$\mu$s(5120m=2\*10^8 \*51.2*10^-6/2),10Mb/s可发送512b，即64B
- 最短有效帧长为64B，长度小于64B的帧为无效帧。因检测到冲突就中止发送，此时的数据长度小于64字节
- 强化碰撞:当发送数据结点一旦检测到碰撞，立即停止发送数据，并要发送若干比特的干扰信号，让所有站都检测到碰撞
- CSMA/CD的信道利用率
  - $t_{prop}$ = LAN上两节点的最长传播延迟
  - $t_{trans}$ = 最长帧的发送时间
  - $efficiency=1/(1+5t_{prop}/t_{trans})$
- 以太网信道利用率
  - $T_0$为帧发送时间, 帧长为L(b)，数据速率为R(b/s)，则帧的发送时间 $T_0$ = L/R (s), 争用期为$2\tau$
  - 当N无穷大时, $S\approx\frac{1}{1+4.44a}$,$a=\tau/T_0$
- 10 Mbps，512b争用期时，节点数与利用率的关系——增加帧长，则利用率更高
  ![5cd5391ee4750.jpg][15]

####IEEE802.11 WLAN:CSMA/CA

- 无线主机与基站之间的通信(基站 = AP)
- 有固定基础设施下的基本业务集(BSS:Basic Service Set)
  - 无线主机
  - AP(access point):基站
  - ad hoc模式:仅有主机
    - 没有基站、节点只能在其信号覆盖范围内将传输数据、节点构成网络——节点实现路由
- 与有线链路的区别:
  - 信号强度的衰减:无线信号强度与其传播路径有关 (路径损耗)
  - 各种信号间的干扰:标准的无线网络频段 (如 2.4GHz) 为其它设备共享;设备之间也存在干扰
  - 多径传播:无线信号经地面及物体发射，使到达 目的节点的信号有不同的延迟
  - 信噪比SNR:更高的SNR–易于从噪声中提取信号
  - SNR与BER(Bit Error Rate)的折中
    - 对给定的物理层 增加功率=增加SNR=降低BER
    - 对给定的SNR:为得到更高的吞吐量，选择不同的物理层技术,使之满足BER要求
      SNR可以随移动而改变:动态 地调整物理层(调制技术，速率等)
      - 随着节点与BS距离的增加 ，SNR降低, BER增大
      - 当BER太高时, 切换到更低的传输速率，BER随之降低
- 注册:
  AP周期性地(如每100ms)发送信标(Beacons)广播帧，建立同步，维持连通性或关联: 信标中含有BSS-ID用于指示AP及网络;业务指示(用于sleep mode);功率管理，用于站点的节能
  节点: 基于信标测量RSS,与AP建立关联:节点向AP注册，节点发送请求，AP予以响应;只有注册后，节点才能发送接收数据DATA
- 802.11b: 信道, 关联
  - 信道管理与分配:AP管理所选择的信道;可能的干扰:工作信道可能被其他AP占用!
  - 主机:必须与AP关联
  - 信道分配及注册: 节点周期性地扫描所有信道，对信道的接收信号强度进行估计(CCA Channel)
    - 关联: 由信道强度决定，选择一个 AP 并注册
    - 重关联:与新的AP关联，出现在下述情况下: 节点离开当前AP覆盖区;当信号条件改变时;当有多个用户与当前的AP关联时
  - 802.11b: 2.4GHz-2.485GHz,定义了11(13/14) 信道，信 道带宽22MHz，信道间隔5MHz,完全正交的信道是3个，如 1,6,11
- 802.11: 被动扫描与主动扫描
  - 被动扫描: AP发送信标帧
  - 主动扫描: 客户端以广播方式发送信标帧, AP发送探测响应帧
- 隐蔽终端问题
- 多点访问:碰撞避免: 2个以上的节点同时发送
  - 802.11: CSMA – 在发送之前侦听,不与正在发送的节点发生碰撞
  - 802.11: 没有碰撞检测
    - **因信号衰落的原因，接收信号很弱，难以在发送的同时进行接收以检测碰撞**
    - **因存在信号衰落以及隐蔽节点，不能检测到碰撞**
    - 目的:避免碰撞CSMA/CA
- 暴露节点
- 802.11 MAC: CSMA/CA
  - 发端: 若信道空闲DIFS，则发送一个帧(无CD); 若信道占用，则:启动随机退避定时器、若信道空闲，则计时、若定时时间到，则发送、若没有收到ACK，则增加随机退避时间间隔, 返回
  - 收端: 若收到一个帧，则:等待SIFS时间之后，响应ACK(因隐蔽节点问题，需要ACK)
- MACA: 为解决WLAN中存在的隐蔽节点问题，采用MACA(MultipleAccess with Collosion Avoidance)
  - 发送端采用CSMA先发送短RTS帧(RTS之间也可能发送碰撞，但它很短)
  - 收端收到RTS后，发送CTS
  - CTS可被附近节点检测到，从而避免隐蔽节点问题
    - 发端发送更长的数据帧
    - 其他节点延迟发送
  - 完全避免数据帧的碰撞，采用更短的预约分组!
- 载波侦听有两类，物理的和虚拟的
  - 物理的载波侦听:通过PLCP在空闲信道评估(CCA:Clear Channel Assessment)阶段，侦听相关比特或检查 RSS(received signal strength)是否高于门限
  - 虚拟的载波侦听:基于网络分配矢量(NAV， Network allocation vector)，从RTS/CTS帧中提取NAV
  - 优先级:定义不同的帧间隔
    - SIFS (Short Inter Frame Spacing):高优先级,用于ACK,CTS,轮询响应
    - PIFS (PCF IFS):中等优先级, 用于PCF方式的有时限限制的业务
    - DIFS (DCF IFS):低优先级, 用于异步数据业务
- PCF: 基于DCF之上，支持无竞争、有时限要求的传输方式
  - 为可选的MAC功能 – 有些产品不支持
  - 主要过程:
    - AP周期性地轮询所有设备，建立CFP;
    - 在PCF期间，设置设备的NAV为ON
    - PCF周期的长度可变，并占用CFP的固定位置;其他时段用于竞争并传送DCF帧

### 高速局域网及链路层交换机

- 100BASE-T以太网
  - MAC帧格式仍采用802.3 标准
  - R增大10倍，$\tau$减小到1/10
  - 保持最短帧长不变，但将一个网段的最大电缆长度减小到100m
  - 帧间时间间隔从原来的9.6$\mu$s改为0.96$\mu$s——网络设备在接收一个帧之后，需要一段 时间恢复并为接收下一帧做准备。固定的为96b的时间
- 千兆以太网——允许在1Gb/s下采用全双工和半双工(与集线器 连接)两种方式工作，使用802.3的帧格式
  - 全双工方式:发送接收同时进行，无碰撞，不需要CSMA/CD
  - 在半双工方式下使用CSMA/CD协议，与10BASE-T和100BASE-T技术后向兼容
  - 为使参数a较小并保持网段最大长度为200m，采用“载波延伸”(carrier extension)使最短帧长仍为64字节，将争用时间增大为512字节 (4.096$\mu$s, 409.6m)
    - 载波延伸: 若发送的MAC帧长不足512字节时(例如46字节数据)就在帧后填充一些特殊字符，使帧的发送长 度增大到512字节(此时链路利用率约为9%);接收端在收到MAC帧后，删除填充的特殊字节后 才交付给高层
  - 帧突发: 允许发送方将多个帧级联在一起，一次传输、帧长最长为1500字节、若不足512字节，则采用载波延伸;
- 集线器Hubs:物理层的转发器(repeaters)
  - 来自一个端口的数据以相同速率在所有端口上发送
  - 连接到集线器的所有节点可以相互侦听到
  - 没有帧的缓存
  - 集线器不做CSMA/CD:主机NIC检测碰撞
- 交换式以太网:
  - 需要决定一个帧去往哪个端口
  - 在不同端口上传输的帧不发生碰撞
  - 更安全:因为以太网卡支持混杂模式，例如协议分析软件Wireshark可以捕获全部的帧
- 交换机Switch:链路层设备
  - 比集线器更智能，其主要作用
    - 存储，转发以太帧
    - 检测输入帧的MAC地址，有选择地向一个或多个端口转发帧，在转发接口对应的网段上实施 CSMA/CD
  - 透明:主机不感知交换机是否存在
  - 分类:
    1. 学习网桥:即插即用，自学习;无需配置即可工作
    2. 生成树网桥:
    3. 虚拟局域网:VLAN
  - 网桥或以太网交换机:将多个局域网连接在一起，工作在链路层，检测MAC地址并转发帧
  - 交换: 允许多点同时传输
    - 主机通过专线与交换机相连
    - 交换机缓存分组
    - 在每条输入链路上采用以太协议，各个链路间没有碰撞;
    - 每条链路有各自的碰撞
    - 全双工
  - 交换表: 表项组成(主机的MAC地址，达到主机 的接口，时间标记)类似于路由表
    - 自学习: 当收到帧，交换机知道其发送的位置:输入LAN网段;将发送“主机/位置”记入交换表
      - 不知帧的目的地址的位置: flood(在除帧接收的端口以外的其它所有端口上转发)
      - 目的地址 A 的位置已知: 选择发送
      - 交换机从某一端口上接收到来自H1的帧，则记录:由此端口可以发送数据给H1,不需要知道哪个AP与H1关联
    - 生成树网桥:(环路问题) 网桥之间通信，构造一个连接各网桥的生成树——网桥周期地发送配置消息给邻居，并处理接收的消息;配置消息中含标识(基于MAC地址)及与其他节点的跳 数;选择最小标识作为生成树的根;构造由根到每个网桥的最短路径树
    - VLAN:按照用户的组织结构而非物理结构，构建局域网
    - 优点:1.安全;2.负载均衡 3.减少广播流量
    - 方法:必须建立配置表，设置其端口属于G或W或GW

[1]: https://blog.ruixiaolu.com/usr/uploads/20200312023138.jpg
[2]: https://blog.ruixiaolu.com/usr/uploads/20200312023149.jpg
[3]: https://blog.ruixiaolu.com/usr/uploads/20200312023159.jpg
[4]: https://blog.ruixiaolu.com/usr/uploads/20200312023209.jpg
[5]: https://blog.ruixiaolu.com/usr/uploads/20200312023222.jpg
[6]: https://blog.ruixiaolu.com/usr/uploads/20200312023233.jpg
[7]: https://blog.ruixiaolu.com/usr/uploads/20200312023241.jpg
[8]: https://blog.ruixiaolu.com/usr/uploads/20200312023253.jpg
[9]: https://blog.ruixiaolu.com/usr/uploads/20200312023304.jpg
[10]: https://blog.ruixiaolu.com/usr/uploads/20200312023312.jpg
[11]: https://blog.ruixiaolu.com/usr/uploads/20200312023319.jpg
[12]: https://blog.ruixiaolu.com/usr/uploads/20200312023330.jpg
[13]: https://blog.ruixiaolu.com/usr/uploads/20200312023338.jpg
[14]: https://blog.ruixiaolu.com/usr/uploads/20200312023346.jpg
[15]: https://blog.ruixiaolu.com/usr/uploads/20200312023355.jpg

最后修改：2020 年 10 月 11 日