计算机网络 第三章 数据链路层
第三章 数据链路层
物理层给数据链路层提供的服务是传送数字信号,这个信号有可能是恒定的比特流或字节流
数据链路层在两个邻接的计算机之间提供可靠的,高效率的通信(点到点)
- 邻接:两个计算机之间用一个通信信道(有线或无线)连接在一起,也叫点到点。
通信信道在概念上就像一条线路(比如同轴电缆、电话线或者无线信道)。信道像一条线路的本质特性使得信道上传递的比特顺序与发送顺序完全相同。
数据链路层的设计问题
数据链路层使用物理层提供的服务在通信信道上发送和接收比特。它要完成一些功能,包括:
(1) 向网络层提供一个定义良好的服务接口。
(2) 把比特流或字节流封装成帧。
(3) 处理传输错误,尾部用于差错控制。
(4) 调节数据流,确保慢速的接收方不会被快速的发送方淹没。
数据链路层的功能:
为网络层提供业务接口
数据链路层通常会提供以下3种可能的服务:
无确认的无连接服务:源机器向目标机器发送独立的帧,目标机器并不对这些帧进行确认
想发就发,不管数据有没有差错或者丢失
例如以太网
差错率非常低,如果出错需要最高层去解决,但是越高层解决,代价就越大
语音传输
有确认的无连接服务:数据链路层仍然没有使用逻辑连接,但其发送的每一帧都需要单独确认
WiFi
发送方需要知道这一帧是正确到达了还是丢失了。若在特定的时间间隔内没有到达,则再发一遍
有确认的有连接服务:在数据链路层提供确认只是一种优化手段,永远不应该成为一种需求
可靠性较差的长链路
如果在计时器超时之前,该数据包的确认还没有到来,那么发送方只要再次发送整个报文即可。这一策略的麻烦在于它可能导致传输的低效率。
处理传输错误
调节数据流
成帧:
一个比特流(或是字节流)通过点到点链路从节点A发送到节点B。节点B必须准确地识别构成帧的比特集,也就是说,它必须确定帧的开始和结束位置,哪几个比特是一伙的
拆分比特流的4种方法:
字节计数法:
面临的物理层提供的服务是字节流
这个算法的问题在于计数值有可能因为一个传输错误而被弄混
字符填充法:
每个帧用一些特殊的字节作为开始和结束。这些特殊字节通常都相同,称为标志字节,作为帧的起始和结束分界符
浪费了带宽
比特填充法:
每个帧的开始和结束由一个特殊的比特模式,01111110标记,同时在数据当中每出现5个1,后面就插入1个0
接收方读取到连续5个1后的0,会直接丢弃
物理层编码违禁法:
比特编码成信号通常包括一些冗余比特,这种冗余意味着这种冗余不会出现在常规数据中。可以利用这些保留的信号来指示帧的开始和结束。
例如Manchester编码:一个周期内电压由低到高表示为0,由高到低表示为1。则当电压恒为高或恒为低时,不表示数据,可用做定界符。
例如4B/5B编码:11111表示空闲,11000表示一帧的开始
缺点:但只适用于存在冗余编码的环境。
差错控制:
数据链路层要确保所有的帧最终都被传递给目标机器的网络层,并且保持正确的顺序
对于无确认的无连接服务,不管发出去的帧是否正确抵达目标机器
但是对于可靠的、面向连接的服务,这样做肯定还远远不够
确保可靠传递的常用方法是向发送方提供一些有关线路另一端状况的反馈信息
有时候由于硬件的问题,一个帧被完全丢失了
有可能数据帧丢失接收方是否收到,也有可能接收方已经收到数据也做出了应答,但是ACK丢失了
这种可能性可以通过在数据链路层中引入计时器来解决:当发送方发出一帧时,通常要启动一个计时器,如果帧或者确认被丢失,则计时器将被触发,帧将会重新发送
同时为了避免接收方将两次或者多次接收到同一帧,要给每一帧分配序号,这样接收方可以根据帧的序号来有效区分原始帧和重传帧
流量控制:
基于反馈的流量控制: 接收方给发送方返回信息,允许它发送更多的数据,或者至少告诉发送方自己的情况怎么样。发送数据必须得到接收方的同意
基于速率的流量控制: 限制发送方传输数据的速率,无须利用接收方的反馈信息
差错检测和纠正
纠错码(ECC):
错误模型:
单比特错误:只有一个比特发生改变
突发错误:2个或多个比特发生改变
等价于在原始的数据基础上叠加了这么长的一个噪音
海明码:
码字: 一个包含了数据位和校验位的n位单元
海明距离: 两个码字中不相同的位的个数
为了可靠地检测d个错误,需要一个距离为d+1的编码方案(编码:把有效数据变成若干个码字,任意两个合法的码字之间的距离至少为n+1)
为了纠正d个错误,需要一个距离为2d+1的编码方案
纠正单个错误所需的校验位数:
m个消息位,r个校验位,n=m+r个码字
有$2^m$个合法的消息
则需要满足:
海明码:
在海明码中,码字的位被连续编号,从最左端的位开始,紧跟在右边的那位是2,依次从左到右编号。2的幕次方的位(1,2,4,8,16等)是校验位,其余位用来填充m个数据位
每一个校验位强制进行模2加,或对某些位的集合,包括其本身进行偶(或奇)校验
海明码纠正突发错误:
二进制卷积码
里德所罗门码
低密度奇偶校验码
检错码:
光纤或高品质铜线的错误率要低得多,因此对于偶尔出现的错误采用差错检测和重传的处理方式通常更加有效
海明码检测出错之后不用重传,可以自行纠错(翻转出错的比特)
奇偶校验:
可以检测突发错误小于等于r的
可能可以检测出偶数个比特的翻转,一定可以检测出奇数个比特的翻转
若突发错误的长度大于r且有偶数个比特的翻转,则被接受的概率为${(\frac{1}{2})^{r}}$
多项式编码(CRC,Cyclic Redundancy Check):
将位串看成是系数为0或1的多项式M(x),作为被除数。一个k位帧看作是一个k-1次多项式的系数列表,该多项式共有k项,从$x^{k-1}$到$x^0$
生成多项式G(x)作为除数,发送方和接收方约定好G(x)
多项式的模2算术:加法和减法等同于异或
M(x)/G(x),进行模2运算,得到余数即为帧校验序列
如果传输过程中出现了错误,则接收方收到的数据可以看作正确数据和差错的叠加,即T(x)+E(x)。由于接受方收到的正确数据T(x)一定有:T(x)/G(x)的余数一定为0,那么结果为E(x)/G(x)
若E(x)/G(x)余数恰好为0,则差错会被忽略
除此之外,其他情况都可以检测出来
突发错误的长度小于等于r:此时E(x)/G(x)一定有余数
两个独立的单比特错误:则$E(x)=x^{i}+x^{j}$,这里i>j。换一种写法,E(x)可以写成$E(x)=x^{j}(x^{i-j}+1)$。因此对于任何小于等于i-j最大值(即小于等于最大帧长)的k值,$G(x)$都不能除尽$x^k+1$
奇数个比特的翻转:在模2系统中,没有一个奇数项多项式包含x+1因子,因此可令$G(x)$含有因子$(x+1)$
- 突发错误的长度超过r:错误的帧被接收的概率为${(\frac{1}{2})^{r}}$
seq_nr=0 //用于记录buffer的序号 |
frame_expected=0 //希望收到几号帧 |
NAK:
当接收方有理由怀疑发生了错误,它将NAK帧发送回发送方,请求重新传输
有两种情况:
收到一个坏帧
收到一个不同于预期的帧
要避免对同一帧进行多个重传输请求,接收方应该跟踪是否已经为给指定帧发送了一个NAK帧
- 停等协议——无差错
- 停等协议——有差错
- 滑动窗口——无差错
- 捎带传输:$U=\frac{N}{2+2\alpha}$
数据链路协议实例
HDLC(High-level Data Link Control):
不平衡:一个主站,一个或多个从站
平衡:两个混合站,全双工
HDLC帧格式:
使用比特填充法
Control字段:
(a)I-frame(INFO):数据帧
(b)S-frame:监督帧
(c)U-frame:没有编号的帧
I-frame:
S-frame:
Code:RR, RNR, REJ, SREJ (3-bit N(R))
ACK帧:RR,RNR
NAK帧:REJ,SREJRR: 接收方准备好
表示期望的N(R)帧的ACK帧
只在没有反向流量可用于捎带时使用该帧
仍可以发送数据RNR: 接收方没有准备好
它像RR一样,识别所有不包括N(R)的帧
但它告诉发送方停止发送(流量控制)REJ: 拒绝
表示检测到传输错误
N(R)字段表示序列中第一个未正确接收的帧(即,要重传的帧)
发送端需要重传从N(R)开始的所有(悬而未决)帧SREJ: 选择性拒绝
只调用N(R)指定的帧的重传
如果接收端希望缓冲无序帧以备将来使用,它可以使用SREJ强制重传任何特定帧
U-frame:
P/F:
非平衡方式:
Poll:邀请终端发送数据
Final:终端发送的所有帧,除最后一帧外,均将P/F位设置为0,最后一个是1
平衡方式:
Command(P位):P=1以恳求(Poll)对方做出响应
Response(F位):F=1表示对请求命令的响应
强制另一台机器立即发送一个监督帧,而不是等待反向通信,以便在反向通信上捎带窗口信息
HDLC操作实例:
PPP(点到点协议)
PPP协议子层:
特性:
Layer 1
- 同步线路(支持面向比特的编码)
- 异步电路(支持面向字节编码)
- PPPoE (支持以太网)
LCP(Link Control Protocol):链路控制协议
- 错误检测(CRC)
- 允许认证
允许在连接时协商IP地址
多种协议:NCP(IP, IPX,…)
PPP帧格式:
PPP状态转移图:
LCP链路控制协议(Link Control Protocol):
数据帧的最大有效负载大小
身份验证和选择要使用的协议
PAP(Password Authentication Protocol):密码认证协议(密码会被偷听)
CHAP(Challenge Handshake Authentication Protocol):挑战握手认证协议
压缩:对头和数据进行压缩
异步方式,字节填充法,链接建立时指定转义字符集ACCM (Async-Control-Character-Map, 32 bits,用bitmap指定需转义的ASCII 码的控制字符集合)
- FLAG为0x7E,ESC为0x7D
0x7E==>0x7D, 0x5E
0x7D==>0x7D, 0x5D
控制字符C ==> 0x7D,C xor 0x20
判断方法 (C < 0x20) && ((1 << C) & ACCM)
反转义:看到0x7D,直接让后面的数与0x20异或
- FLAG为0x7E,ESC为0x7D
PPP和HDLC的区别:
- PPP是面向字节而不是面向比特的。特别是PPP使用字节填充技术,所有帧的长度均是字节的整数倍
HDLC协议则使用比特填充技术, 允许帧的长度不是字节的倍数 - HDLC协议提供了可靠的数据传输,PPP是面向连接的不可靠的
……未完待续♬