教材:计算机网络(第四版)
作者:吴功宜 吴英
出版社:清华大学
第三章 数据链路层
3.1 差错产生的原因与差错控制方法
物理线路:由传输介质与通信设备组成
设计数据链路层的主要目的:在有差错的物理线路的基础上,采取差错检测、差错控制与流量控制等方法
从参考模型的角度来看,物理层以上的各层都有改善数据传输质量的责任,数据链路层是最重要的一层
传输差错:通过物理线路传输之后接收数据与发送数据不一致的现象
传输差错由随机差错与突发差错共同构成
物理线路噪声分为两类:热噪声(随机差错)和冲击噪声(突发差错)
误码率:二进制比特在数据传输系统中被传错的概率
Pe=Ne/NP_e = N_e/N Pe=Ne/N
NeN_eNe:被传错的比特数
NNN:传输的二进制比特总数
注意:如果传输的不是二进制比特,要折合成二进制比特来计算
差错控制:如果在通信信道传输数据的过程中产生差错,能够自动检测出错误并进行纠正的方法
差错控制的两种策略: 纠错码和检错码
3.3.1 纠错码
每个传输的分组带上足够的冗余信息
接收端能发现并自动纠正传输差错
优点:能自动纠正错误
缺点:实现困难,在一般通信场合不易采用
3.3.2 检错码
分组仅包含足以使接收端发现差错的冗余信息
接收端能发现出错,但不能确定哪一比特是错的,并且自己不能纠正传输差错
优点:工作原理简单,实现容易
缺点:需通过重传机制达到纠错目的
1. 奇偶校验码
垂直奇(偶)校验
水平奇(偶)校验水平
水平垂直奇(偶)校验(方阵码)
特点:方法简单,但检错能力差,只用于通信要求较低的环境
2. 循环冗余编码CRC
目前应用最广的检错码编码方法之一
工作原理:
任意一个由二进制位串组成的代码都可以和一个系数仅为‘0’和‘1’取值的多项式一一对应。
例如:发送数据比特序列为10111,其对应的多项式为f(x)=x4+x2+x+1f(x)=x^4+x^2+x+1f(x)=x4+x2+x+1
生成多项式为事先约定好的
如:G(x)=x4+x3+1G(x)=x^4+x^3+1G(x)=x4+x3+1;则对应G(x)的二进制代码为: 11001
f(x)﹒xk,kf(x)﹒x^k,kf(x)﹒xk,k为生成多项式的最高幂值,即生成多项式用二进制表示的位数-1
k=4=5−1k=4=5-1k=4=5−1。表示将发送数据比特序列左移k位,用来存放余数
f(x)﹒xk/G(x)f(x)﹒x^k/G(x)f(x)﹒xk/G(x),得到余数R(x)R(x)R(x)
将f(x)﹒xk+R(x)f(x)﹒x^k+R(x)f(x)﹒xk+R(x)作为整体,发送到接收端
接收端用接收到的数据f′(x)采用相同的算法,去除G(x)G(x)G(x),得到余数R′(x)R′(x)R′(x)。如果R′(x)R′(x)R′(x)等于 R(x)R(x)R(x),表示发送没有出错
举例
发送数据比特序列为f(x)=110011f(x)=110011f(x)=110011
生成多项式比特序列为G(x)=11001G(x)=11001G(x)=11001(k=5-1)
将发送数据比特序列×24×2^4×24,f(x).xk=1100110000f(x).x^k=1100110000f(x).xk=1100110000
将乘积f(x).xkf(x ).x^kf(x).xk用生成多项式G(x)比特序列去除,按模二法(异或)
3. 差错控制机制
接收端通过检错码检查数据帧是否出错,一旦发现错误,通常采用反馈重发(automatic request for repeat,ARQ)方法来纠正
传输正确:ACK传输失败:NAK
3.2 数据链路层的基本概念
链路:由物理线路与通信设备构成物理线路:一般指点对点的线路段,中间无交换结点数据链路:实现协议或规程的硬件、软件与物理线路共同构成设计数据链路层目的:发现和纠正链路在传输过程中可能出现差错,将原始的、有差错的物理线路变为对网络层无差错的数据链路数据链路层为网络层提供的服务主要表现在:正确传输网络层的用户数据,为网络层屏蔽物理层采用的传输技术的差异性3.2.2 主要功能
链路管理
数据链路的建立、维持和释放
帧同步
数据链路层传输单位为帧
帧同步:接受方应能从收到的比特流中正确地判断出一帧的开始位和结束位
流量控制
发送端发送数据超过物理线路的传输能力或超出接收端的帧接收能力,会造成链路阻塞
为了防止出现链路拥塞,数据链路层必须具有流量控制功能
差错控制
发现与纠正传输错误
帧的透明传输
不管传输数据是什么样的组合,都应当能在链路上传送
寻址
保证每一帧能传送到正确的目的结点
3.2.4 数据链路层协议
数据链路层协议 :为实现数据链路控制功能而制定的规程或协议
数据链路层协议可以分为两类:面向字符型与面向比特型
面向字符型的协议:利用已定义好的一种标准字编码的一个子集来执行通信控制功能
如:二进制同步通信(BSC)协议
面向比特型协议有HDLC与PPP协议
3.3 数据链路层协议演变与发展
3.3.1 面向字符型数据链路层协议
缺点:
用专用的控制字符实现数据链路管理,效率低;控制帧与数据帧格式不同不能实现数据的“透明传输”停止等待工作方式的协议效率低,通信线路利用率低1. 部分控制字符
2. 工作阶段划分
第一阶段:建立数据链路连接
发送端与接收端开始数据传输之前,发送端通过发送控制字符ENQ询问接收端;
接收端同意建立数据链路连接,则通过回送控制字符ACK确认数据链路连接,并进入准备接收帧状态
第二阶段:帧传输
发送端软件按照协议规定的帧结构,将网络层传送来的IP分组数据封装成帧,在通过物理层发送到接收端
接收端通过校验字段BCC来判断帧传输是否出错
如果出错则丢弃该帧,并向发送端发送控制字符NAK,要求发送端重发;
如果正确,则向发送端发送ACK确认信息,并取出帧中数据字段,传送到网络层
第三阶段:释放数据链路连接
发送端发送完数据之后,发送传输结束EOT控制字符给接收端;
接收端同意释放数据链路连接,也要通过回送控制字符ACK来表示同意释放数据链路连接
停止等待工作方式:BSC协议规定发送端发出ENQ询问字符之后,必须等待接收端发送ACK确认自负之后才能够进入发送帧状态。当发送端发送一端帧,必须等待接收端收到ACK或NAK确认字符之后,才能进入下一帧的发送
特点:协议效率低,通信线路的利用率低
3. 帧封装
帧类型:控制帧和数据帧
控制帧:一般只包含长度为1B的控制字段
用于数据链路的建立、释放以及帧封装与帧传输状态控制
网络层的IP分组放在帧数据字段中,数据链路层软件需要根据协议对帧格式的规定,为IP分组数据加上帧头和帧尾,封装成数据帧
最大传输单元(maximum transfer unit,MTU):帧数据字段的最大长度
简化的BSC协议帧封装过程
帧头:1B的报头开始(SOH)控制字符、用户定义的报头字段以及1B的正文开始(STX)控制字段组成帧尾:控制字读ETX与帧校验字段BCC组成
4. 透明性问题
透明传输:通信协议可以传输的任意比特组合数据的特性面向字符型数据链路层协议存在着传输“不透明”问题3.3.2 面向比特型数据链路层协议
1. 数据链路配置
基本配置方式:非平衡配置与平衡配置
平衡配置特点:两个站都是复合站
复合站同时拥有主站与从站的功能
每个复合站都可以发出命令与相应
异步平衡模式的每个复合站都可以平等地发起数据传输,而不需要得到对方复合站的许可
平衡配置数据传送方式:异步响应模式
非平衡配置:根据一组结点在通信过程中的地位,分主站与从站
主站:控制数据链路的工作过程。主站发出命令
从站:接受命令,发出响应,配合主站工作
非平衡配置结构分类:点对点方式和多点方式
多点方式的链路中,主站与每个从站之间都要分别建立数据链路
非平衡配置数据传送方式:正常响应模式与异步响应模式
正常响应模式:(主说从答)
主站可以随时向从站传输数据帧
从站只有在主站向它发送命令帧探询,从站响应后才可以向主站发送数据帧
异步响应模式:(主从随时互传)
主站和从站可以随时相互传输数据帧
从站不需要等待主站发出探询就可以发送数据帧
主站仍然负责数据链路的初始化、链路的建立、释放与差错控制等功能
2. HDLC
面向字符型数据链路层协议的缺点
报文格式不一样停止等待发送方式,传输效率低只对数据部分进行差错控制,系统可靠性差功能扩展困难面向比特型协议的设计目标:
以比特作为传输控制信息的基本单元数据帧与控制帧格式相同传输透明性好连续发送,传输效率高HDLC帧结构
标志字段F(flag)
固定格式:01111110
作用:标记帧的开始与结束,帧同步
HDLC帧数据存在“透明传输”问题
为了避免出现这种错误,HDLC协议规定采用“0比特插入/删除方法”
发送端在两标志字段间的比特序列中,如果查出连续的5个“1”,都增加1个“0”
接收端接收后,检查中间比特序列,若发现5个连续”1”,就将后面的1个“0”删除
地址字段A(address)
使用非平衡方式传送数据时,地址字段为从站地址使用平衡方式时,为应答站地址全1时,为广播地址,要求网中所有站都要接收该帧控制字段C(control)
帧的类型、帧的编号、命令与控制信息
根据最前面两比特的取值,分为3类:
信息帧:I帧(0)
监控帧:S帧(10)
无编号帧:U帧(11)
信息帧(I帧 )
N(S)N(S)N(S):当前发送的信息帧的序号
N(R)N(R)N(R):该站已正确接收序号为N(R)−1N(R)-1N(R)−1的帧及以前各帧
P/F=Poll/FinalP/F= Poll / FinalP/F=Poll/Final, P/F=0P/F=0P/F=0表示该位没有意义
P=1P=1P=1 探询,F=1F=1F=1 终止,P与F成对出现
监控帧(S帧 ):监控功能位
S=00S = 00S=00,RR(receive ready)
S=01S = 01S=01,RNR(receive not ready)
S=10S = 10S=10,RJE(reject)
S=11S = 11S=11,SREJ(select reject)
无编号帧(U帧) :用于实现数据链路控制功能
本身不带编号,即无N(S)、N(R)N(S)、N(R)N(S)、N(R)位,用b2b3b5b6b7b_2b_3b_5b_6b_7b2b3b5b6b7表示不同的作用
信息字段I(information)
用于传送网络层IP分组数据Nmax=256BN_{max} = 256BNmax=256B仅出现在信息帧和无编号帧中帧校验字段FCS
校验A、C、I字段的数据正常相应模式的工作过程
3. 数据链路层与物理层的关系
3.3.3 数据链路层滑动窗口协议与帧传输效率分析
(补充内容,书上无)
数据链路层的差错控制与流量控制采用了滑动窗口协议(Sliding Windows Protocol)
1. 滑动窗口协议(Sliding Window )
窗口机制:发送方和接收方都具有一定容量的缓冲区(即窗口),允许发送站连续发送多个幀而不需要等待应答。发送窗口:发送端允许连续发送的幀的序号表,发送端可以不等待应答而连续发送的最大幀数称为发送窗口的尺寸接收窗口:接收方允许接收的幀的序号表,凡落在接收窗口内的幀,接收方都必须处理,落在接收窗口外的幀被丢弃.接收方每次允许接收的幀数称为接收窗口的尺寸滑动窗口
目的:对可以连续发出的最多帧数(已发出但未确认的帧)作限制
序号使用:循环重复使用有限的帧序号
HDLC协议帧头发送序号N(S)N(S)N(S)与接收序号N®能起到捎带确认的作用,也可用于数据链路层流量控制的滑动窗口协议中。长度为3,能表示序号0~7的帧。
流量控制
发送窗口:其大小WsW_sWs表示在收到对方确认的信息之前,以连续发出的最多数据帧数(只有序号在窗口内的帧才可以发送)
接收窗口:其大小WrW_rWr为可以连续接收的最多数据帧数(只有序号在窗口内的帧才可以接收,否则丢弃)
接收窗口驱动发送窗口的转动
基本工作原理
发送端可以连续发送帧的数量要受到接收端的限制。
限制主要因素:接收端的接收缓冲区可以用于接收新的接收帧的字节数,接收端处理数据帧的速度,以及接收端需要等待重传的帧的多少。
HDLC协议帧头发送序号N(S)与接收序号N®能起到捎带确认的作用,也可用于数据链路层流量控制的滑动窗口协议中
1. 单帧停止等待协议(1位滑动窗口协议)
ACK:传输正确NAK:传输错误优点:简单缺点:传输效率低1. 帧传输总延时分析
传播延时tp=传输介质长度/电磁波传播速度=L/Vt_p=传输介质长度/电磁波传播速度=L/Vtp=传输介质长度/电磁波传播速度=L/V
发送延时=帧长度/发送速率=帧长度/发送速率=帧长度/发送速率
数据帧、确认帧长度不同,延时不同,用tf、tat_f、t_atf、ta分别表示
数据帧、确认帧长度不同,延时不同,用tf、tat_f、t_atf、ta分别表示
处理延时tprt_{pr}tpr接收端接收帧和处理帧所需要的时间。忽略数据帧和确认帧的处理时间的区别,统一记为tprt_{pr}tpr
•理想状态下,总延时$t_T=t_p+t_f+t_{pr}+t_a+ t_p+t_{pr}=2t_p+2t_{pr}+t_f+t_a $
• 忽略帧的处理延时tprt_{pr}tpr ,确认帧的发送延时tat_ata
tT=2tp+tft_T=2t_p + t_ftT=2tp+tf
•理想状态下,停止等待协议的帧传输效率为:
U=tf/(2tp+tf)U=t_f /(2t_p + t_f)U=tf/(2tp+tf)
设α=传播延时/发送延时=tp/tfα=传播延时/发送延时=t_p /t_fα=传播延时/发送延时=tp/tf, 则 U=1/(1+2α)U=1/(1+2α)U=1/(1+2α)
2. 结论
当传播延时一定时,发送的数据长度越长,发送延时越大,ααα越小,传输效率UUU越高推论:在保持tT=2tp+tft_T=2t_p + t_ftT=2tp+tf时间内不出现差错的条件下,连续发送多个帧,可以提高帧传输效率2. 多帧连续发送协议
后退N帧(GBR)拉回重发方式
选择重发(SR)方式
选择重发纠错滑动窗口控制过程
3.4 PPP协议
3.4.1 PPP协议的主要特点
特点:简单,适用范围广,广泛应用于广域网环境中路由器-路由器连接,以及家庭用户接入Internet之中,成点-点线路中应用最多的数据链路层协议
在物理层支持点-点线路连接、全双工通信,支持异步通信或同步通信。在数据链路层实现PPP数据帧的组帧、传输与拆帧,CRC校验;不使用帧序号,不提供流量控制功能。通过链路控制协议(LCP)来建立、配置、管理和测试数据链路连接;通过网络控制协议(NCP)来建立和配置不同的网络层协议。可以用于用户计算机通过Modem与电话线路、ADSL Modem与电话线路,以及HFC传输网中Cable Modem与同轴电缆接入,也可以用于光纤接入。在网络层支持IP协议与NetWare IPX等多种协议。广泛应用于主机—路由器、路由器—路由器的连接。
3.4.2 PPP协议帧结构
1. PPP协议帧类型
PPP链路控制帧
用以建立、配置和测试PPP数据链路
PPP网络控制帧
链路建立后,用以选择和配置网络层协议
PPP信息帧
网络层数据通过PPP信息帧传输
2. PPP信息帧结构
标志字段(7E)
值为“01111110”,即“0x7E”,表示帧的开始与结束
地址字段(FF)
值为“11111111”,(0xFF)
控制字段(03)
值为“00000011”,(0x03)
协议(protocol)字段值:(表示三种类型帧,采用何种格式)
0x0021—表示PPP帧的信息字段是IP分组数据
0xC021—表示信息字段是PPP协议的LCP数据帧
0x8021—表示信息字段是PPP帧的NCP数据帧
信息字段
长度可变,最长为1500字节
帧校验字段(FCS)
一般为2个字节,协商后可以是4个字节
小结
物理传输线路上传输数据信号是有差错的。
设置数据链路层的目的:将一条有差错的物理线路变为对网络层无差错的数据链路、
数据链路层必须执行链路管理、帧传输、流量控制、差错控制等功能
差错控制是检测并纠正数据传输差错。
最常用的检错方法是循环冗余编码方法
数据链路层协议分为:
面向字符型协议(二进制同步同信协议BSC)
面向比特型协议(高级数据链路控制协议HDLC、点-点协议PPP)
差错控制与流量控制采用滑动窗口协议分为:
单帧停止等待协议
多帧连续发送协议(后退N帧协议GBN、选择重传协议SR)