计算机网络学习笔记2

[TOC]

Chap3 数据链路层

功能

成帧(Framing)

将bit流划分成"帧"的主要目的是为了检测和纠正物理层在比特传输中可能出现的错误，数据链路层功能需借助帧的各个域来实现
差错控制(Error Control)

处理传输中出现的差错
流量控制

确保发送方的发送速率，不大于接收方的处理速率，避免接收缓冲区溢出

服务

无确认无连接服务(Unacknowledged connectionless)

接收方不对收到的帧进行确认
适用场景:误码率低的可靠信道
网络实例:以太网

有确认无连接服务 (acknowledged connectionless)

每一帧都得到单独的确认
适用场景:不可靠的信道(无线信道)
网络实例:802.11

有确认有连接服务(Acknowledged connection-oriented)

适用场景:长延迟的不可靠信道

成帧

标识帧的开始

接收方必须能从物理层接收的bit流中明确区分出一帧的开始和结束，这个问题被称为帧同步或帧定界
关键:选择何种定界符？定界符出现在数据部分如何处理？

成帧的方式

带bit填充的定界符法

定界符:两个0bit之间，连续6个1bit，即01111110,0x7E

发送方检查有效载荷：若在有效载荷中出现连续5个1比特，则直接插入1个0比特

接收方的处理：
若出现连续5个1比特，
若下一比特为0，则为有效载荷，直接丢弃0比特；
若下一比特为1，则连同后一比特的0，构成定界符，一帧结束

物理层编码违例

核心思想: 选择的定界符不会在数据部分出现
4B/5B编码方案

4bit数据映射成5bit编码，剩余的一半码字未使用，可以用作帧定界符

例如:00110组合不包含在4B/5B编码中，可做帧定界符
前导码

存在很长的前导码(preamble)，可以用作定界符

例如:传统以太网,802.11
曼切斯特编码/差分曼切斯特编码

正常的信号在周期中间有跳变，持续的高电平(或低电平)为违例码，可以用作定界符

例如:802.5令牌环网

差错控制

背景

链路层存在的一个问题:信道的噪声导致数据传输问题

差错(incorrect):数据发生错误
丢失(lost): 接收方未收到
乱序(out of order): 先发后到，后发先到
重复(repeatedly delivery):一次发送，多次接收

解决方案:差错检测与纠正，确认重传

确认:接收方校验数据（差错校验)，并给发送方应答，防止查错
定时器:发送方启动定时器，防止丢失
顺序号:接收方检查序号，防止乱序递交，重复递交

差错检验与纠正

目标

保证一定差错检测和纠错能力的前提下，如何减少冗余信息量？
考虑的问题
- 信道的特征和传输需求
- 冗余信息的计算方法，携带的冗余信息量
- 计算的复杂度等
两种主要策略
- 检错码(error-detecting code)
在被发送的数据块中，包含一些冗余信息，但这些信息只能使接收方推断是否发送错误，而不能判断哪位发生错误，接收方可以请求发送方重传数据主要用在高可靠，误码率较低的信道上，例如光纤链路偶尔发生的差错，可以通过重传解决差错问题
- 纠错码(error-correcting code)
发送方在每个数据块中加入足够的冗余信息，使得接收方能够判断接收到的数据是否有错，并能纠正错误定位出错的位置）主要用于错误发生比较频繁的信道上，如无线链路也经常用于物理层，以及更高层（例如，实时流媒体应用和内容分发）使用纠错码的技术通常称为前向纠错（FEC，Forward Error Correction)

常用的检错码包括：

①奇偶检验 (Parity Check)
1位奇偶校验是最简单、最基础的检错码。

1位奇偶校验：增加1位校验位，可以检查奇数位错误

偶校验 :1的个数为偶数个，则校验位为0
奇效验:1的个数为奇数个，则校验位为1

②校验和 (Checksum)

主要用于TCP/IP体系中的网络层和传输层

③循环冗余校验 (Cyclic Redundancy Check，CRC)
数据链路层广泛使用的校验方法

CRC校验码计算方法

设原始数据D为k位二进制位模式
如果要产生n位CRC校验码，事先选定一个n+1位二进制位模式G (称为生成多项式，收发双方提前商定)，G的最高位为1
将原始数据D乘以2^n （相当于在D后面添加 n 个 0），产生k+n位二进制位模式，用G对该位模式做模2除，得到余数R（n位，不足n位前面用0补齐）即为CRC校验码

CRC校验码计算示例

D = 1010001101
n = 5
G = 110101 或 G = x5 + x4 + x2 + 1
R = 01110
实际传输数据：101000110101110

④汉明码

目标：以奇偶校验为基础，找到出错位置，提供1位纠错能力

给定n位待发送的数据，首先确定校验位的个数k（根据2^k≥k+n+1）
确定校验位在码流中的位置，2^i,i=0,1,2,……，得到校验位P_1,P_2,P_4,P_8,……
确定分组，即每个校验位分别负责哪些数据位

P_1负责位置号的二进制符合XXXX1形式的数据位，即1,3,5,7,9,……
P_2负责位置号的二进制符合XXX1X形式的数据位，即2,3,6,7,10,……
P_3负责位置号的二进制符合XX1XX形式的数据位，即4,5,6,7,12,13,14,15,……
基于偶校验确定每组的校验位（0或1）

注：汉明码是采用奇偶校验的码。它采用了一种非常巧妙的方式，把这串数字分了组，通过分组校验来确定哪一位出现了错误。

实际的海明码编码的过程也并不复杂，我们通过用不同过的校验位，去匹配多个不同的数据组，确保任何一个数据位出错，都会产生一个多个校验码位出错的唯一组合。这样，在出错的时候，我们就可以反过来找到出错的数据位，并纠正过来。当只有一个校验码位出错的时候，我们就知道实际出错的是校验码位了。

流量控制

链路层存在的另一个问题：接收方的处理速率

接收方的接收缓冲区溢出

解决方案

基于反馈 (feedback-based) 的流量控制
接收方反馈，发送方调整发送速率
基于速率 (rate-based) 的流量控制
发送方根据内建机制，自行限速

媒体介入控制MAC

MAC(Medium Access Control)

数据链路层分为两个子层：
MAC子层：介质访问
LLC子层：承上启下（弱层）

信道分配问题

时分多址接入-TDMA

TDMA:time division multiple access
- 按顺序依次接入并使用信道
- 每个用户使用固定且相同长度的时隙
- 某时隙轮到某用户使用时，该用户没有数据要发送，则该时隙被闲置
例子:6-user LAN,1,3,4时隙有数据发送，2,5,6时隙被闲置
频分多址接入-FDMA

FDMA:frequency division multiple access
- 信道总频带被划分为多个相同宽度的子频带
- 每个用户占用一个子频带，不管用户是否有数据发送
例如:6-user LAN 1,3,4频带有数据发送 2，5,6频带被闲置

多路访问协议

随机访问协议

特点:冲突不可避免

ALOHA
1. 纯ALOHA协议
  
  原理:随意发送
  
  特点:
  1. 冲突:两个或以上的帧
  2. 随时可能冲突
  3. 冲突的帧完全破坏
  4. 破坏的帧要重传
2. 分隙ALOHA
  - 分隙ALOHA是把时间分为时隙
  - 时隙的长度对应一帧的传输时间
  - 帧的发送必须在时隙的起点
  - 冲突只发生在时隙的起点
载波侦听多路访问协议CSMA
- 特点: 先听后发
1. 非持续式CSMA
  
  特点
  - 经侦听，如果介质空闲，开始发送
  - 如果介质忙，则等待一个随机分布的时间，然后重复
  好处
  - 等待一个随机事件可以减少再次碰撞冲突的可能性
  缺点
  - 等待时间内介质上如果没有数据传送，会浪费这段时间
2. 持续式CSMA
  - p-持续式CSMA
    1. 特点
      - 经侦听，如果介质空闲，那么以p的概率发送，以（1-p）的概率延迟一个时间单元发送
      - 如介质忙，持续侦听，一旦空闲重复1
      - 如果发送已推迟一个时间单元，再重复1
  - 1-持续式CSMA
    1. 特点
      - 经侦听，如介质空闲，则发送
      - 如介质忙，持续侦听，一旦空闲立刻发送
      - 如果发生冲突，等待一个随机分布的时间再重复步骤1
    2. 好处
      
      持续式的延迟时间少于非持续式
    3. 问题
      
      如果两个以上的站等待发送
      
      一旦介质空闲就一定发生冲突
  - 1-持续式是p-持续式的特例