计算机网络
Computer Networks
第三讲 数据链路控制内容提要
流量控制
差错控制
HDLC协议数据链路控制
要解决的问题:如何在有差错的线路上,进行无差错传输。
ISO关于数据链路层的定义:
数据链路层的目的是为了提供功能上和规程的方法,以便建立、维护和释放网络实体间的数据链路。
数据链路:从数据发送点到数据接收点所经过的传输途径。
数据链路控制
数据链路层协议应提供的最基本功能
数据在数据链路上的正常传输(建立、维护和释放)
定界与同步,也处理透明性问题
差错控制
顺序控制
流量控制数据链路控制为网络层提供三种合理的服务
无确认无连接服务适用于
误码率很低的线路,错误恢复留给高层;
实时业务
大部分局域网
有确认无连接服务适用于不可靠的信道,如无线网。
有确认有连接服务停止等待流量控制
最简单的流量控制策略
发送方每发送一帧后就等待一个应答,
只有当收到肯定的应答后,才接着发送下一帧,如果收到否定应答或超时未收到应答,则重发该帧数据
ACK
ACK
下一帧数据后面的数据
A B
正常情况数据
NAK
ACK
数据 (重传 )
下一帧数据
A B
数据错误数据
ACK
数据 (重传 )
下一帧数据
A B
超时数据丢失数据
ACK
数据 (重传 )
下一帧数据
A B
超时
ACK
丢弃此帧应答丢失停止等待的链路利用率停止等待协议的传输效率传输效率 =
Tframe
---------
2 Tprop + Tframe
Tfrae 数据应答应答下一个数据
A B
Tprop
Tprop =
距离--------------------
信号传输速度
Tframe =
帧的大小---------------
比特率
= Tprop / Tframe
传输效率 = 1 / (2? + 1)
Tfrae:帧传输时间 Tprop:帧传播时间传输效率举例
短距离链路 (1 km),tprop = 5?s
帧大小 = 4000 bits
数据传输速率 =10 Mbps? tframe = 4k/10M= 400?s
= tprop /tframe =5/400=0.012
U = 1/(2?+1) = 0.98
卫星链路,传播延时 tprop = 270 ms
帧大小 = 4000 bits
数据传输速率 = 56 kbps? tframe = 4/56 = 71 ms
= tprop /tframe = 270/71 = 3.8
U = 1/(2?+1) = 0.12
停止等待协议的优点:
简单,每一帧都进行校验并进行应答
缺点:
在信号传输时延较长时传输效率比较低滑动窗口流量控制
允许多帧发送
接收方为 W个帧分配缓存
发送方无需接到确认就可以连续发送 W

每帧都编有序号
确认帧( ACK)包含下一个期望接收的帧序号
窗口 = 发送方 /接收方允许发送 /接收的帧的序号表
Data 1
ACK 1
Data 4
A B
Data 2
Data 3 ACK 2
ACK 3Data 5
Data 6 ACK 4ACK 5
ACK 6
滑动窗口滑动窗口效率
Tfram
eT
prop
A B
Data 1
Data …
Data N
Data
Data
Data
传输效率 =
N Tframe
---------
2 Tprop + Tframe
滑动窗口举例发送者接收者大小为 1、序号为 3的滑动窗口发送窗口
6 0 1 2 3 4 5 67 70 1 2 3 4 5… …
将要发送的帧已经发送的帧已发送的最后一帧当帧被发送时窗口从后沿收缩当接收到确认时窗口从前沿扩展帧序号接收窗口
6 0 1 2 3 4 5 67 70 1 2 3 4 5… …
可以接收的帧已经接收的帧已确认的最后一帧收到帧时窗口从后沿收缩发送确认后窗口从前沿扩展帧序号内容提要
流量控制
差错控制
HDLC协议差错控制
数据传输过程中,受到噪声的影响,不可避免地会出现传输差错,为了保证传输的可靠性,就要采取措施进行差错控制
处理差错问题的两种策略:
检测出错误,然后请求发送方重传( 检错码 )
发现错误并纠正( 纠错码 )
差错编码理论
在数据块中加入冗余信息的过程称为差错编码
一种编码的检错和纠错能力取决于它的海明距离
海明距离 —— 两个码字中不同的位的数目称作海明距离海明距离举例
1 0 0 0 1 0 0 1
1 0 1 1 0 0 0 1
海明距离 =3
要能检测出 d个比特错误,需要使用距离为 d+1的编码
0 0 0 0 0 0
0 0 0 1 1 1
1 1 1 0 0 0
1 1 1 1 1 1
1 1 1 0 0 0
0 0 0 1 1 1
1 1 1 0 0 0
1 1 1 1 1 1
1 0 1 0 0 0
0 0 0 1 1 1
1 1 1 0 0 0
1 1 1 1 1 1
海明距离 =3
错 2位 错 3位
要能纠正出 d个比特错误,需要使用距离为 2d+1的编码
0 0 0 0 0 0
0 0 0 1 1 1
1 1 1 0 0 0
1 1 1 1 1 1
0 0 0 0 0 0
0 0 0 1 1 1
1 1 1 0 0 0
1 1 1 1 1 1
0 0 1 0 0 0
0 0 0 1 1 1
1 1 1 0 0 0
1 1 1 1 1 1
海明距离 =3
错 1位 纠正奇偶校验码
奇偶校验,在数据后填加一个奇偶校验位( parity bit)。
例:使用偶校验(,1”的个数为偶数)
10110101 —— > 101101011
10110001 —— > 101100010
问题
奇偶校验码能否检查出偶数个错误?
不能,奇偶校验码只能检查出奇数个错
1 0 1 1 0 1 0 1 —— > 1 0 1 1 0 1 0 1 1
1 0 1 1 0 1 1 1 —— > 1 0 1 1 0 1 1 1 0
1 0 1 1 0 0 1 1 —— > 1 0 1 1 0 0 1 1 1
1 0 1 1 1 0 1 1 —— > 1 0 1 1 1 0 1 1 0
1 0 1 0 1 0 1 1 —— > 1 0 1 0 1 0 1 1 1
原码字:
错一位:
错两位:
错三位:
错四位:
奇偶校验码漏检率达 50%
循环冗余码( CRC)
由于奇偶校验漏检率高,在计算机和数据通信中使用最广泛的检错码是循环冗余码。该码漏检率低且容易实现。
循环冗余码( CRC码,多项式编码)把位串看成是系数为 0或 1的多项式。例如:
110001,表示成多项式 x5 + x4 + 1
生成多项式 G(x)
发方、收方事前商定;
生成多项式的高位和低位必须为 1
生成多项式必须比传输信息对应的多项式短。
CRC码基本思想:校验和加在帧尾,使带校验和
( checksum)的帧的多项式能被 G(x)除尽;收方接收时,
用 G(x)去除它,若有余数,则传输出错。
循环冗余码( CRC)
校验和计算算法
设 G(x)为 r 阶,在 帧的末尾加 r 个 0,使帧为 m + r位,相应多项式为 xrM(x);
按模 2除法用对应于 G(x)的位串去除对应于 xrM(x)的位串;
按模 2减法从对应于 xrM(x)的位串中减去余数(等于或小于 r位),结果就是要传送的带校验和的多项式 T(x)。
CRC举例
生成多项式的表示方法,
543210
||||||
10011 = x4+x+1
110101 = x5+x4+x2+1
帧,1101011011
生成多项式,10011
帧后加 4个 0的位串,11010110110000
余数传输的帧模 2除法接收方校验常用的生成多项式
CRC-12 = x12+x11+x3+x2+x1+1
CRC-16 = x16+x15+x2+1
CRC-ITU = x16+x12+x5+1
海明码
纠正单比特错的编码可以通过海明 1950
年提出的方法实现
海明编码位从左边开始按顺序依次编号;
编号为 2的幂的位是校验位,其余的位填入数据位;
每个校验位的取值应使得包括自己在内的一些位的集合服从规定的奇偶性。
海明码
为了知道编号为 k的数据位对哪些检测位有影响,将编号 k改写成 2的幂的和,
例如,11=1+2+8,29=1+4+8+16,一个位只由扩展式中所示编号的位检测,例中,11的位只由编号为 1,2和 8的检测位检测。
海明码举例
以一个 7位的 ASCII字符为例,m=7(数据位 ),r=4(校验位 ),
n=11(编码总长 )
11=1+2+8,10=2+8,9=1+8,8=8
7=1+2+4,6=2+4,5=1+4,4=4
3=1+2,2=2,1=1
① = ① + ③ + ⑤ + ⑦ + ⑨ + ⑾
② = ② + ③ + ⑥ + ⑦ + ⑩ + ⑾
④ = ④ + ⑤ + ⑥ + ⑦
⑧ = ⑧ + ⑨ + ⑩ + ⑾
对于 ASCII字符,d”,二进制码为 1100100
海明码为:
① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ ⑩ ⑾
1 1 1 1 1 0 0 1 1 0 0
校验位内容提要
流量控制
差错控制
HDLC协议
HDLC协议高级数据链路控制规程 HDLC
1976年,ISO提出 HDLC( High-level Data Link
Control)面向比特的数据链路控制协议
HDLC的组成
帧结构
规程元素
规程类型 语义使用 HDLC的语法可以定义多种具有不同操作特点的链路层协议。
HDLC定义了三种类型的数据站、两种链路配置和三种数据传输方式
}语法
数据站(简称站 station),由计算机和终端组成,负责发送和接收帧。 HDLC涉及三种类型的站:
主站( primary station):主要功能是发送命令(包括数据),接收响应,负责整个链路的控制(如系统的初始、
流控、差错恢复等);
从站( secondary station):主要功能是接收命令,发送响应,配合主站完成链路的控制;
复合站( combined station):同时具有主、次站功能,既发送又接收命令和响应,并负责整个链路的控制。
HDLC适用的链路构型
非平衡型
点 — 点式 主站 从站
多点式适合把智能和半智能的终端连接到计算机。
平衡型
仅用于点对点线路,由两个复合站组成
适合于计算机和计算机之间的连接主站 从站从站从站,..
复合站 复合站
HDLC的基本操作模式
正规响应模式 NRM( Normal Response Mode)
适用于点 — 点式和多点式两种非平衡构型。只有当主站向次站发出探询后,次站才能获得传输帧的许可。
异步响应模式 ARM( Asynchronous Response Mode)
适用于点 — 点式非平衡构型和主站 — 次站式平衡构型。次站可以随时传输帧,不必等待主站的探询。
异步平衡模式 ABM( Asynchronous Balanced Mode)
适用于通信双方都是复合站的平衡构型,也采用异步响应,双方具有同等能力。使用最广泛的一种模式。
HDLC帧结构
地址域( Address)
多终端线路,用来区分终端;
点到点线路,有时用来区分命令和响应。
若 A是接收该帧的站的地址,则该帧是命令帧。
若 A是发送该帧的站的地址,则该帧是响应帧。
控制域( Control)
根据控制域格式,可分为三种类型的帧:
信息帧( I)
管理帧( S)
无编号帧( U)
HDLC帧结构
数据域( Data)
任意信息,任意长度(有上限)
只有信息帧和某些无编号帧含有数据域
校验和( Checksum)
CRC校验
常用 16位生成多项式,CRC-ITU
标志域( F)
01111110作为帧的定界符(面向比特的同步)
同一个标志既可作为前一帧的结束,也可作为后一帧的开始,为避免错误,要使用 位填充技术,
即发送器在发送的数据比特序列中一旦发现 5个连续的 1,则在其后插入一个 0
HDLC帧格式信息帧无编号帧管理帧
信息帧:用户数据
该帧的编号
捎带的肯定应答:期望接收的下一个帧的编号
Poll/Final (询问 /终止) = 命令 /响应
管理帧:流量和差错控制
有 4种管理帧,由控制域中的两位 S来区分
接收就绪 (RR)、接收未就绪 (RNR)
拒绝接收 (REJ)、选择性拒绝接收 (SREJ)
无编号帧:链路控制
拆除连接( DISC)、帧拒绝( FRMR)、无编号应答( UA)等
链路控制命令
DISC( DISConnect)拆除连接请求
SNRM(置正常响应方式)
SARM(置异步响应方式)
SABM(置异步平衡方式)
SABME(置扩展的异步平衡方式)
SNRME(置扩展的正常响应方式)
FRMR(帧拒绝)
UA(无编号应答)
对控制帧进行确认,用于确认模式建立和接受拆除命令。
UI(无编号信息)
HDLC举例超时
( a)链路建立和拆除
( b)双向数据交换
( c)接收站忙
RR
( d)后退重发 ( e)超时重发超时第三讲“数据链路控制”