ftp://ftpcssjtueducn/net330第3章数据链路层1
文件类型：PDF/Adobe Acrobat 文件大小：字节
文件类型：PDF/Adobe Acrobat 文件大小：字节
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层1 / 159
第第33章章数据链路层数据链路层
定义,功能
数据帧的组成
可靠性传输
数据链路层示例
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层2 / 159
数据链路层的定义数据链路层的定义
网络层有个实体即进程,数据链路层将借
助于物理层为网络层提供服务
为网络层提供一个较好定义的服务接口
定义一个合适的传输差错率
对传输的数据流进行管理,以免快速的
发送淹没慢速的接收端
数据链路层的协议数据单元(PDU)是帧
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层3 / 159
数据链路层的功能数据链路层的功能
数据链路层的任务是把网络层的数据组合成
帧,加上一定的校验,然后交物理层用某种
信号表示二进制数据位送到目的计算机,并
通过目的计算机的物理层和数据链路层送到
网络层,也就是为网络层提供一条可靠的数
据链路
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层4 / 159
相连,物理链路和数据链路相连,物理链路和数据链路
所谓相连,可以理解为物理的连接,但当采用
多路复用技术时也可以是信道连接.其特征是
传输的数据是顺序的
物理链路:一段无源的点到点的物理连接,中
间没有任何交换节点
数据链路:一条物理连接加上为实现数据的传
输,两端配置的硬件和相关的通信协议
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层5 / 159
数据链路层服务的区分规则数据链路层服务的区分规则
数据链路层的服务是通过有无连接,有
无确认来区分的
无确认无连接
有确认无连接
有确认有连接
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层6 / 159
确认和连接确认和连接
确认:接收方在收到数据帧后,必须给
发送方发回一个确认
面向连接:发送方和接收方在传输数据
之前必须建立逻辑连接,传输结束后必
须释放连接
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层7 / 159
数据链路层的服务数据链路层的服务
无确认无连接
有确认无连接
有确认有连接
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层8 / 159
无确认是指接收方在收到数据帧后,毋需发回一
个确认
无连接服务是指在数据传输前毋需建立逻辑链路
物理线路的连接并非意味着提供有连接的服务
无确认并非不可靠,其可靠性由上层负责
例如:局域网共享信道毋需建立连接
信道较为理想,数据传输的误码率很低
即使出错或丢失由上层负责恢复
无确认的面向无连接服务无确认的面向无连接服务
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层9 / 159
数据链路层的服务数据链路层的服务
无确认无连接
有确认无连接
有确认有连接
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层10 / 159
有确认的面向无连接服务有确认的面向无连接服务
使用前不建立连接,即不建立数据链路,但
每帧传输必须得到确认
这在信号传播延时较大,线路状态不一定很
可靠的情况下是有效的
例如:无线通信如建立连接,则信道使用率很低
但数据传输的误码率相对较高,
确认是必要的
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层11 / 159
数据链路层的服务数据链路层的服务
无确认无连接
有确认无连接
有确认有连接
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层12 / 159
有确认的面向连接服务有确认的面向连接服务
使用前先建立连接,即先建立数据链路,
并且每帧的传输必须得到确认
有连接的服务必须在使用前先建立连接
(即建立逻辑链路),然后使用,最后
释放连接
例如:电话
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层13 / 159
数据的可靠传输数据的可靠传输
保证直接相连的两台主机的可靠性传输
将传输的信息组合成帧
校验和重发
流量控制
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层14 / 159
第第33章章数据链路层数据链路层
定义,功能
数据帧的组成
可靠性传输
数据链路层示例
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层15 / 159
数据帧的组成数据帧的组成
帧的组成必须保证能识别一个完整的帧,并保证一
旦出现传输差错导致前一个帧丢失,也必须能识别
下一个帧,即再同步
字符计数法
带字符填充的首尾界符法
带位填充的首尾标志法
物理层编码违例法
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层16 / 159
字符计数法字符计数法
帧的长度用一个字节表示,作为帧的头部
帧长度计数
第1帧第4帧第3帧第2帧
51234567898012345687890123
帧长度计数错
51234367898012345687890123
第1帧第第2帧第3帧4帧
Tnbm P188 Fig. 3-4 字符计数成帧法
一旦帧长度计数被误读,将无法再同步,所以很少采用
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层17 / 159
数据帧的组成数据帧的组成
帧的组成必须保证能识别一个完整的帧,并保证一
旦出现传输差错导致前一个帧丢失,也必须能识别
下一个帧,即再同步
字符计数法
带字符填充的首尾界符法
带位填充的首尾标志法
物理层编码违例法
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层18 / 159
带字符填充的首尾界符法带字符填充的首尾界符法
用特殊的字符作为帧头和帧尾
FLAGHeaderPayload field TrailerFLAG
Tnbm P189 Fig. 3-5 (a) 由Flag标志的一个帧
这是一种面向字符的帧格式,所传输的数据都是字符
(ASCII或EBCDIC字符),但帧中不允许出现帧界符
标志,在面向字符的串型通信中常使用这种格式(PPP)
接收方一旦丢失了一个FLAG,只要继续搜索下一个
FLAG,就可重新确定帧边界,即具有再同步能力
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层19 / 159
面向字符的帧格式面向字符的帧格式
面向字符的帧格式不适宜传输数据中包含二进制数的帧,因为
在包含二进制数的帧中很可能出现FLAG的字符(通常FLAG用
ASCII字符7EH定义)
一种方法是在二进制数中偶然出现的FLAG前再插入一个ESC
(ASCII字符1BH),这就称为字符填充法
41 33 7E9C 4B 0C
41 33 1B9C 4B 0C
41 33 1B7E9C 4B 0C
41 33 1B1B9C 4B 0C
41 33 1B7E9C 4B 0C
41 33 1B 1B9C 4B 0C
41 33 1B1B 1B7E9C 4B 0C
41 33 1B1B 1B 1B9C 4B 0C
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层20 / 159
数据帧的组成数据帧的组成
帧的组成必须保证能识别一个完整的帧,并保证一
旦出现传输差错导致前一个帧丢失,也必须能识别
下一个帧,即再同步
字符计数法
带字符填充的首尾界符法
带位填充的首尾标志法
物理层编码违例法
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层21 / 159
带位填充的首尾标志法带位填充的首尾标志法
字符并非都是8位的,东方文字是16位的,UNICODE是16位的
在面向二进制位的同步串型通信中常使用带
位填充的首尾标志格式,如HDLC
这是一种面向二进制位的帧格式,把所有需传输的数据(不论是字符
或表示一个浮点数的二进制位串,还是一个MP3的文件)一字排开,
并以特殊的位模式01111110作为帧标志,即一个帧的开始(同时标志
前一个帧的结束)
如果由于干扰,一个帧标志没有正确接收,则继续扫描接收串,一旦
扫描到01111110,即新的一帧从此开始,即具有再同步能力
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层22 / 159
面向面向bitbit的帧格式的帧格式
当帧中出现一个与帧标志相同的位串01111110,则
在5个1后插入一个0,即变成01111101,接收方将自
动删除第5 个1后的0
这称为位插入法,也称为透明传输
011011111111111111110010
011011111011111011111010010
011011111111111111110010
Tnbm P190 Fig. 3-6 (a) (b) (c) 位插入法示例
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层23 / 159
数据帧的组成数据帧的组成
帧的组成必须保证能识别一个完整的帧,并保证一
旦出现传输差错导致前一个帧丢失,也必须能识别
下一个帧,即再同步
字符计数法
带字符填充的首尾界符法
带位填充的首尾标志法
物理层编码违例法
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层24 / 159
物理层编码违例法物理层编码违例法
在曼切斯特编码中,连续高电平或连续
低电平可用作帧边界
采用冗余编码技术,如曼切斯特编码,即两个采样脉冲才可得
到一个二进制位
数据0:低-高电平对
数据1:高-低电平对
高-高电平对和低-低电平对没有使用,如在二进制
编码中出现称为编码违例,但这两种违例编码可用
作帧边界,在令牌环网中使用编码违例格式
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层25 / 159
第第33章章数据链路层数据链路层
定义,功能
数据帧的组成
可靠性传输
数据链路层示例
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层26 / 159
可靠性传输可靠性传输
差错控制:校验,重发和序号
流量控制:窗口协议
协议描述和验证
避免帧错误的保证:帧的校验
避免帧丢失的保证:超时和重发
避免帧重复的保证:帧有序号
发送方和接收方之间的协调
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层27 / 159
差错控制差错控制
如何保证数据帧的正常传输:通过三
种手段处理三种可能出现的情况:
确认
数据帧丢失
重复帧
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层28 / 159
确认确认
接收方在收到了正确的帧后向发送方发
肯定性确认.如收到的帧有问题,则发
否定性确认,此时发送方将重发此帧
确认的前提是必须经过差错检测
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层29 / 159
差错检测和校正差错检测和校正
超时只是传输出错的一种情况,更多的传输出
错是数据中的一位或几位因噪声干扰而出错
噪声分两种:
信道所固有的,持续存在的随机热噪声
外界突发原因而造成的冲击噪声
通常接收方应能检错,甚至纠错
纠错码是除m个数据位外增加r个冗余位作为
纠错位,整个长度为n = m + r
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层30 / 159
纠错码:
检错码:
海明(Hamming)码
校验和(Check Sum)
块校验码(Block Check Code)
循环冗余检错码CRC
(Cyclic Redundancy Check)
纠错码和检错码纠错码和检错码
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层31 / 159
海明海明((HammingHamming))纠错码纠错码
m个数据位外加r 个纠错位.在2i(i=0,1,2,3…) 的
位置放的是纠错位.m个数据位的次序不变.如
字符m的7位二进制码为1101101,要加上4位纠
错码0011(偶校验),共11个bit.
1110987654321
A7
1
A5A6
10
P4
0
A4A3A2P3A1P2P1
1100111
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层32 / 159
信息位影响的纠错位信息位影响的纠错位
一个信息位影响多个纠错位
信息位信息组位组位展开影响的纠错位
A711=8+2+1对P4,P2,P1有影响
A610=8+2对P4,P2有影响
A59=8+1对P4,P1有影响
A47=4+2+1对P3,P2,P1有影响
A36=4+2对P3,P2有影响
A25=4+1对P3,P1有影响
A13=2+1对P2,P1有影响
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层33 / 159
纠错位的取值纠错位的取值
一个纠错位由多个信息异或然后取偶/奇校验
纠错位纠错位的取值(再取偶/奇校验)
P4=A7⊕A6⊕A5
P3=A4⊕A3⊕A2
P2=A7⊕A6⊕A4⊕A3⊕A1
P1=A7⊕A5⊕A4⊕A2⊕A1
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层34 / 159
海明码纠错位取值举例海明码纠错位取值举例
采用偶校验
1110987654321
A7
1
A5A6
10
P4
0
A4A3A2P3A1P2P1
1100111
检错位纠错位的取值(再取偶校验)
P4=A7⊕A6⊕A5 =0
P3=A4⊕A3⊕A2 =0
P2=A7⊕A6⊕A4⊕A3⊕A1 =1
P1=A7⊕A5⊕A4⊕A2⊕A1 =1
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层35 / 159
接收方的校验接收方的校验
校验位校验位计算表达式
S4=A7⊕A6⊕A5⊕P4
S3=A4⊕A3⊕A2⊕P3
S2=A7⊕A6⊕A4⊕A3⊕A1⊕P2
S1=A7⊕A5⊕A4⊕A2⊕A1⊕P1
计算结果S4 S3 S2 S1为0 0 0 0意味着接收正确
计算结果S4 S3 S2 S1为0 1 0 1意味着第5位出错
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层36 / 159
接收方的校验举例接收方的校验举例(无错)(无错)
字符m采用海明码的发送序列为11001100111
如接收到的序列也为11001100111
1110987654321
A7A6A5P4A4A3A2P3A1P2P1
11001100111
校验位校验位计算表达式的值
S4
S3
S2
S1
=A7⊕A6⊕A5⊕P4=1⊕1⊕0⊕0=0
=A4⊕A3⊕A2⊕P3=1⊕1⊕0⊕0=0
=A7⊕A6⊕A4⊕A3⊕A1⊕P2=1⊕1⊕1⊕1⊕1⊕1=0
=A7⊕A5⊕A4⊕A2⊕A1⊕P1=1⊕0⊕1⊕0⊕1⊕1=0
S4 S3 S2 S1 = 0 0 0 0意味校验正确
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层37 / 159
接收方的校验举例接收方的校验举例(有错)(有错)
字符m采用海明码的发送序列为11001100111
如接收到的序列为11001110111
1110987654321
A7A6A5P4A4A3A2P3A1P2P1
11001110111
校验位校验位计算表达式的值
S4
S3
S2
S1
=A7⊕A6⊕A5⊕P4=1⊕1⊕0⊕0=0
=A4⊕A3⊕A2⊕P3=1⊕1⊕1⊕0=1
=A7⊕A6⊕A4⊕A3⊕A1⊕P2=1⊕1⊕1⊕1⊕1⊕1=0
=A7⊕A5⊕A4⊕A2⊕A1⊕P1=1⊕0⊕1⊕1⊕1⊕1=1
S4 S3 S2 S1 = 0 1 0 1意味第5位出错
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层38 / 159
纠错码:
检错码:
海明(Hamming)码
校验和(Check Sum)
块校验码(Block Check Code)
循环冗余检错码CRC
(Cyclic Redundancy Check)
纠错码和检错码纠错码和检错码
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层39 / 159
校验和校验和
算法简单,实现容易,但检错率不高
以16位为例:
4865H+6C6CH+6F20H+776FH+726CH+642EH+进位=71FCH
Helloworld.
48656C6C6F20776F726C642E71FC
将发送的数据看成是二进制整数序列,并划分成一段段
规定的长度(如8位,16位,32位等),计算他们的
和.如校验和大于规定的长度,则将进位加到最后的校
验和中.将校验和和数据一起发送.在接收端,重新计
算校验和,与原校验和比较.如要传输"Hello world."
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层40 / 159
纠错码:
检错码:
海明(Hamming)码
校验和(Check Sum)
块校验码(Block Check Code)
循环冗余检错码CRC
(Cyclic Redundancy Check)
纠错码和检错码纠错码和检错码
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层41 / 159
块校验码块校验码
块校验码BCC(Block Check Code)简单
常用,但检错的强度较弱,如在同一列上有
偶数位错,则不能检测
如传输的数据都是ASCII字符(即面向字符,这在应用中很
多),每个字符进行奇偶校验,然后把所有的字符(连同奇偶
位)进行异或运算,运算结果即为其块校验码.发送端一面发
送一面计算,最后发送块校验码,接收端一面接收一面计算,
最后与接收到的块校验码比较
如"Hello world.",采用偶校验,校验后的字符序列为:
Helloworld.
48656C6C6FA0776F726CE42E2E
48H⊕65H⊕6CH⊕6CH⊕6FH⊕A0H⊕77H⊕6FH⊕72H
⊕6CH⊕E4H⊕2EH = 2EH
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层42 / 159
纠错码:
检错码:
海明(Hamming)码
校验和(Check Sum)
块校验码(Block Check Code)
循环冗余检错码CRC
(Cyclic Redundancy Check)
纠错码和检错码纠错码和检错码
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层43 / 159
循环冗余检错码循环冗余检错码CRCCRC
任何一个k位的帧看成为一个k-1次的多项式M(x)
如:1011001看成x6+x4+x3+x0
设定一个多项式编码生成多项式G(x),G(x)为r阶,k>r
如xrM(x)/G(x) = Q(x) + R(x)/G(x) 其中Q(x)为商,R(x)为
余数,R(x)即为M(x)的CRC码
将CRC码接在帧后一起发送,即发送数据为xrM(x) + R(x)
二进制运算中,减法和加法都做异或运算:0+1=1,1+1=0
因为( xrM(x) -R(x) )一定能被G(x)整除,即余数为0,则接
收方只要计算的余数为0即为正确
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层44 / 159
CRCCRC码计算举例码计算举例
如一帧为1101011011
即:M(x)= x9+x8+x6+x4+x3+x+1
G(x)=x4+x+1
T(x)= x4M(x)
=x4(x9+x8+x6+x4+x3+x+1)
=x13+x12+x10+x8+x7+x5+x4
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层45 / 159
CRCCRC码计算举例码计算举例(续(续11))
帧:1101011011
除数:10011
实际传输帧:
1100001010
1001111010110110000
10011
10011
10011
00001
00000
00010
00000
00101
00000
01011
00000
10110
10011
01010
00000
10100
10011
01110
00000
1110
余数
11010110111110
帧数据余数
TnbmP198 Fig. 3-8 CRC码计算举例
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层46 / 159
CRCCRC码计算举例码计算举例(续(续22))
11010110110000/10011
= 1100001010 ……1110
即11010110110000 + 1110能被10011整除
(模2运算的加,减和异或,其运算结果相同)
如发送方发送的T(x),接收方收到的是
T(x)+E(x),除非E(x)是G(x)的整倍数,否则不能
被整除,即都能被检测到已出错
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层47 / 159
三个生成多项式国际标准三个生成多项式国际标准
CRC-12:x12 + x11 + x3 + x2 + x1 + 1
用于字符长度为6位
CRC-16 :x16 + x15+ x2+ 1
用于字符长度为8位
CRC-CCITT:x16 + x12+ x5+ 1
用于字符长度为8位
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层48 / 159
差错控制差错控制
如何保证数据帧的正常传输:通过三
种手段处理三种可能出现的情况:
确认
数据帧丢失
重复帧
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层49 / 159
数据帧丢失数据帧丢失
通过发送方计时器(超时)解决
超时(TimeOut):在传输过程中,所发送
的帧丢失,接收方根本没有收到,不可能发
送确认帧(包括否定性确认),而发送方正
在等待接收方的确认帧,当然也不可能等到
接收方的回音.所以,发送方一旦发送一
帧,就启动一计时器,在规定的时间内,一
般都应收到回音,如收不到回音,则在计时
器溢出时,再重发此帧
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层50 / 159
差错控制差错控制
如何保证数据帧的正常传输:通过三
种手段处理三种可能出现的情况:
确认
数据帧丢失
重复帧
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层51 / 159
重复帧重复帧
重发机制也包括当接收方发送的确认帧
丢失而导致发送方的重发
由于接收方确认帧的丢失,导致发送方
多次发送同一帧,接收方也将多次收到
同一帧,要能区别是否是同一帧,则每
帧都应有一个帧的编号
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层52 / 159
可靠性传输可靠性传输
差错控制:校验,重发和序号
流量控制:窗口协议
协议描述和验证
避免帧错误的保证:帧的校验
避免帧丢失的保证:超时和重发
避免帧重复的保证:帧有序号
发送方和接收方之间的协调
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层53 / 159
流量控制流量控制
发送方和接收方速率的匹配即流量控制
如接收方的处理能力低于发送方,即使传输中没有
出错,也可能被"淹没",所以通常在接收方的缓冲
区到达一定量时,应及时通知发送方,暂停发送,
等候通知,这就是流量控制机制
基本数据链路协议
滑动窗口协议
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层54 / 159
基本数据链路协议基本数据链路协议
可以这样理解:在一台主机中,物理层,数据
链路层,网络层等等都有各自的进程在运行,
并且假设:
A,B两台主机要求可靠的,面向连接的
通信,在接收方的数据链路层,目前正运
行的是wait_for_event(&event),即等待
某个事件发生
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层55 / 159
wait_for_event(&event)wait_for_event(&event)的参数的参数
如发生了某个事件,此过程将返回参数,
event有两个取值:
checksum_err和frame_arrival
如event = checksum_err,意即所接收的帧的校验
和错,应考虑不发送确认帧,或发送否定性确认帧
如event = frame_arrival,即帧已到达并校验正
确,则调用from_physical_layer,从物理层取得
帧,检查帧头的控制信息,如一切正常,则仅把其
中的分组交网络层
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层56 / 159
帧的基本格式帧的基本格式
一般意义上的帧的格式
帧类型顺序号确认号分组
帧头
一系列过程和数据结构的定义:
Tnbm P202 Fig. 3-9
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层57 / 159
协议协议11:一种无限制的单工协议:一种无限制的单工协议
一种理想的环境,理想的协议,假定:
链路是理想的传输通道,所传输的任何数据
既不会出错也不会丢失
即:不需校验,也不可能重发
不管发送方以怎样的速率发送数据,接收方
都能及时接收
即接收端处理器的处理速度无限高,处理时间可忽
略不计,缓冲区空间无限大,毋需流量控制
Tnbm P205 Fig.3-10 一种无限制的单工协议
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层58 / 159
协议协议11::SENDERSENDER
void sender1(void)
{
frame s;
packet buffer;
while (true)
{
from_network_layer(&buffer);
s.info=buffer;
to_physical_layer(&s);
}
}
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层59 / 159
协议协议11::RECEIVERRECEIVER
void receiver1(void)
{
frame r;
event_type event;
while (true)
{
wait_for_event(&event);
from_physical_layer(&r);
to_network_layer(&r.info);
}
}
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层60 / 159
协议协议22:一个单工的停:一个单工的停--等协议等协议
然而,接收方不可能具有足够高的CPU处理能力来
及时处理所有的接收帧,也不可能具有足够大的缓
冲区,但仍假定:
链路是理想的传输通道,所传输的任何数据
既不会出错也不会丢失
即:不需校验,也不可能重发
所以,当它来不及处理时,应通知发送方暂缓发送,
一旦可以继续接收,则通知发送方继续发送
Tnbm P207 Fig.3-11 一个单工的停-等协议
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层61 / 159
协议协议22::SENDERSENDER
void sender2(void)
{ frame s;
packet buffer;
event_type event;
while (true)
{
from_network_layer(&buffer);
s.info=buffer;
to_physical_layer(&s);
wait_for_event(&event);
}
}
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层62 / 159
协议协议22::RECEIVERRECEIVER
void receiver2(void)
{
frame r,s;
event_type event;
while (true)
{
wait_for_event(&event);
from_physical_layer(&r);
to_network_layer(&r.info);
to_physical_layer(&s);
}
}
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层63 / 159
协议协议33:有噪声信道的单工协议:有噪声信道的单工协议
在噪声信道中应考虑传输有差错的情况
所谓差错:
帧的损坏:如帧中若干位出错,通常CRC都能检测到
帧的丢失:一旦帧头出错,接收方将检测下一个帧
头,以同步,但该帧已丢失
帧的重复:如确认帧丢失,接收方将接收到重复帧
所以,发送方应启动一个计时器,一旦超时立即重发
Tnbm P210 Fig. 3-12 一个肯定性确认和超时重发协议
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层64 / 159
协议协议33的要点的要点
发送方要记录下一个准备发送的顺序号
接收方要记录下一个期望接收的顺序号
发送过程和接收过程是严格交替的
接收方收到一个正确的帧,即便不是期望的
帧,都将发送一个确认(即一个空的确认帧)
也称为ARQ协议:
Automatic Repeat reQuest
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层65 / 159
协议协议3: SENDER3: SENDERvoid sender3(void)
{next_frame_to_send=0;
from_network_layer(&buffer);
while (true)
{ s.info=buffer;
s.seq=next_frame_to_send;
to_physical_layer(&s);
start_time(s.seq)
wait_for_event(&event);
if (event==frame_arrival)
{from_physical_layer(&s);
if (s.ack==next_frame_to_send) {
stop_timer(s.ack);
from_network_layer(&buffer);
inc(next_frame_to_send);
}
}
}
}
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层66 / 159
协议协议3: RECEIVER3: RECEIVER
void receiver3(void)
{ frame_expected=0;
while (true)
{ wait_for_event(&event);
if (event==frame_arrival)
{ from_physical_layer(&r);
if (r.seq==frame_expected)
{ to_network_layer(&r.info);
inc(frame_expected); }
s.ack=1-fram_expected;
to_physical_layer(&s);
}
}
}
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层67 / 159
协议协议33的重发机制存在的问题的重发机制存在的问题
效率较低
如接收方收到的帧出错或者整个数据帧丢失,则不
发确认帧,发送方在超时后重发,直至正确(效率
极低)
接收方会收到重复帧
如接收方收到了正确的数据帧并发送了确认,但此
确认丢失,发送方在超时后重发此帧,这样,接收
方的数据链路层收到了两个完全相同的帧,其网络
层将收到两个完全相同的分组(这是不能允许的)
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层68 / 159
流量控制流量控制
发送方和接收方速率的匹配即流量控制
如接收方的处理能力低于发送方,即使传输中没有
出错,也可能被"淹没",所以通常在接收方的缓冲
区到达一定量时,应及时通知发送方,暂停发送,
等候通知,这就是流量控制机制
基本数据链路协议
滑动窗口协议
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层69 / 159
协议协议33的问题的问题
不能双向传输,效率低
由于应答无序号,导致系统不可靠
其实,在协议3中,发送方应重发当前帧还是
发下一帧,仅根据超时还是收到确认而定,
亦即仅与前一帧和后一帧有关,所以,在协
议3中,顺序号仅需一位,0/1
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层70 / 159
双向传输解决方案双向传输解决方案
用四根信道:两根数据,两根应答
但信道利用率很低
用两根信道:一根A到B,另一根B到A
问题是如何区分数据和应答
解决方法有两种:
用不同的帧类型
用捎带确认
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层71 / 159
滑动窗口协议滑动窗口协议
收发使用两条信道
发送方可连续发送多帧,接收方接受到一帧
后就从另一个信道发一个确认,为提高信道
使用效率,可使用捎带确认
帧是有序号的
即使过早超时而导致的重发也可根据帧的序
号来避免帧的重复
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层72 / 159
滑动窗口原理滑动窗口原理(设(设WWTT=5=5,,WWRR=3=3))
发送方
接收方
(a) (b) (c) (d)
0
1
2
34
5
6
70
1
2
34
5
6
70
1
2
34
5
6
70
1
2
34
5
6
7
前沿
后沿
0
1
2
34
5
6
70
1
2
34
5
6
70
1
2
34
5
6
7
前沿
0
1
2
34
5
6
7
后沿
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层73 / 159
三个窗口协议三个窗口协议(协议(协议44--66))
发送窗口WT=1,接收窗口WR=1
Tnbm P215 Fig.3-14 一位滑动窗口协议(协议4)
发送窗口WT=7,接收窗口WR=1
Tnbm P220 Fig.3-17 后退n帧的滑动窗口协议(协议5 )
发送窗口WT=4,接收窗口WR=4
Tnbm P224 Fig.3-19 选择性重发滑动窗口协议(协议6)
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层74 / 159
一位滑动窗口协议一位滑动窗口协议
发送窗口WT=1,接收窗口WR=1
即停-等协议
Tnbm P215 Fig.3-14 (协议4)
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层75 / 159
一位滑动窗口协议一位滑动窗口协议
void protocol4(void)
{ next_frame_to_send=0;
frame_expected=0;
from_network_layer(&buffer);
s.info=buffer;
s.seq=next_frame_to_send;
s.ack=1-frame_expected;
to_physical_layer(&s);
start_time(s.seq) ;
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层76 / 159
while (true)
{ wait_for_event(&event);
if (event==frame_arrival)
{ from_physical_layer(&r);
if (r.seq==frame_expected)
{ to_network_layer(&r.info);
inc(frame_expected); }
if (r.ack==next_frame_to_send)
{ stop_timer(r.ack);
from_network_layer(&buffer);
inc(next_frame_to_send); }
}
s.info=buffer;
s.seq=next_frame_to_send;
s.ack=1-frame_expected
to_physical_layer(&s);
start_time(s.seq)
}
}
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层77 / 159
比较两种情况比较两种情况
情况1:
A端首先发送,B端等待发送,无过早超时,
其运行过程正常
情况2:
A端和B端都同时发送,无过早超时,其运行
过程不正常
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层78 / 159
情况情况11:主机:主机AA发送主机发送主机BB等待等待
主机A
初始化后组成发送
帧,其中:
主机B
初始化后尚未组成发送
帧,在接收到A0帧后交
网络层并组成发送帧,
(捎带确认)其中:
发送帧顺序号seq=0
对接收到的帧的确认
ack=1
实际上此确认无意义
通过物理层发送
发送帧顺序号seq=0
对接收到的帧的确认
ack=0
通知A,0帧收到
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层79 / 159
情况情况11:运行过程正常:运行过程正常A发送(0,1,A0)SeqackA发送A0,seq= 0
B收到(0,1,A0)▲B收到A0
B发送(0,0,B0)B发送B0,并确认A0
A收到(0,0,B0)▲A收到B0及对A0的确认
A发送(1,0,A1)A发送A1及对B0的确认
B收到(1,0,A1)▲B收到A1及对B0的确认
B发送(1,1,B1)B发送B1及对A1的确认
A收到(1,1,B1)▲A收到B1及对A1的确认
A发送(0,1,A2)A发送A2及对B1的确认
B收到(0,1,A2)▲B收到A2及对B1的确认
B发送(0,0,B2)B发送B2及对A2的确认
A收到(0,0,B2)▲A收到B2及对A2的确认
A发送(1,0,A3)A发送A3及对B2的确认
B收到(1,0,A3)▲B收到A3及对B2的确认
B发送(1,1,B3)
Tnbm P216 Fig. 3-15 (a) 协议4,运行过程正常
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层80 / 159
比较两种情况比较两种情况
情况1:
A端首先发送,B端等待发送,无过早超时,
其运行过程正常
情况2:
A端和B端都同时发送,无过早超时,其运行
过程不正常
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层81 / 159
情况情况22::主机主机AA发送主机发送主机BB也发送也发送
主机A
初始化后组成发送
帧,其中:
主机B
初始化后也组成发
送帧,其中:
发送帧顺序号seq=0
对接收到的帧的确认
ack=1
实际上此确认无意义
通过物理层发送
发送帧顺序号seq=0
对接收到的帧的确认
ack=1
实际上此确认无意义
通过物理层发送
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层82 / 159
情况情况22:运行过程不正常:运行过程不正常
A发送(0,1,A0)B发送(0,1,B0)B也已从网络层得到B0
B收到(0,1,A0)▲B以为B0分组A没有收到
B发送(0,0,B0)所以B又重发B0分组
A收到(0,1,B0)▲A以为A0分组B没有收到
A发送(0,0,A0)所以A又重发A0分组
B收到(0,0,A0)B收到对B0的确认并丢弃A0
B发送(1,0,B1)B发送B1及对A0的确认
A收到(0,0,B0)A收到对A0的确认并丢弃B0
A发送(1,0,A1)A发送A1及对B0的确认
B收到(1,0,A1)▲B以为B1分组A没有收到
B发送(1,1,B1)所以B又重发B1分组
A收到(1,0,B1)▲A以为A1分组B没有收到
A发送(1,1,A1)所以A又重发A1分组
B收到(1,1,A1)B收到对B1的确认并丢弃A1
B发送(0,1,B2)
Tnbm P216 Fig. 3-15 (b) 协议4,运行过程不正常
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层83 / 159
三个窗口协议三个窗口协议(协议(协议44--66))
发送窗口WT=1,接收窗口WR=1
Tnbm P215 Fig.3-14 一位滑动窗口协议(协议4)
发送窗口WT=7,接收窗口WR=1
Tnbm P220 Fig.3-17 后退n帧的滑动窗口协议(协议5 )
发送窗口WT=4,接收窗口WR=4
Tnbm P224 Fig.3-19 选择性重发滑动窗口协议(协议6)
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层84 / 159
退后退后nn帧的协议帧的协议
协议4的主要问题是信道利用率太低:
发送端的等待时间至少是发送端到接收端信号传播时间
的两倍
信道的利用率为:
数据发送时间/从数据发送开始到确认返回的总耗时
发送管道化(pipelining):
在等待确认的时间内连续发送
存在的问题主要是信道不可靠:
一旦数据帧丢失,在发送端在意识到丢失(TimeOut)
时,已有大量数据帧到达接收端
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层85 / 159
退后退后n n 帧协议(帧协议(go back ngo back n))
当接收端发现一错帧后,抛弃此帧及以后所
有收到的帧,不发确认.当发送端出现超时
(错帧的TimeOut)后,重发自该帧起的所
有已发送帧
问题:浪费带宽
发送方连续发送了7帧(2 ~ 8),但2#帧无确
认,超时后,从2#帧起开始重发
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层86 / 159
后退后退nn帧的滑动窗口协议帧的滑动窗口协议图例图例
有一个差错时后退n帧(接收窗口为1,发送窗口为7)
超时间隔
出错时间被数据链路层丢弃的帧
发
收
0
ACK0ACK1ACK2ACK3ACK4ACK5
125432876543876
01EDDDDDD25436
Tnbm P218 Fig. 3-16 (a)
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层87 / 159
后退后退nn帧的滑动窗口协议帧的滑动窗口协议程序程序
void protocol5(void)
{
enable_network_layer();
ack_expected = 0;
next_frame_to_send = 0;
frame_expected = 0;
nbuffered = 0;
0
1
2
34
5
6
7
Next_frame_to_send
ack_expected
nbuffered = 3
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层88 / 159
while (true)
{ wait_for_event(&event);
switch (event)
{case network_layer_ready:
network_layer_ready处理;
case frame_arrival: frame_arrival处理;
case cksum_err: 暂且忽略;
case timeout:timeout处理;
}
if nbuffered < MAX_SEQ)
enable_network_layer();
else disable_network_layer();
}
}
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层89 / 159
network_layer_readynetwork_layer_ready处理处理::
from_network_layer
(&buffer[next_frame_to_send]);
nbuffered = nbuffered + 1;
send_data
(next_frame_to_send,
frame_expected,buffer);
inc(next_frame_to_send);
装配一个数据帧
并发送,发送缓
冲区数+1,准备
发送下一数据帧
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层90 / 159
frame_arrivalframe_arrival处理:处理:
from_physical_layer(&r);
if (r.seq == frame_expected)
{ to_network_layer(&r.info);
inc(frame_expected);
}
while (between(ack_expected, r.ack,
next_frame_to_send))
{ nbuffered = nbuffered -1;
stop_timer(ack_expected);
inc(ack_expected);
}
如收到一个数据帧
则交网络层,并期
望接收下一数据帧
如收到一个确认帧
则释放一个缓冲区
定时器复位,并期
望接收下一确认帧
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层91 / 159
TimeOutTimeOut处理:处理:
next_frame_to_send = ack_expected;
for ( i = 1; i <= nbuffered; i++)
{
send_data(next_frame_to_send,
frame_expected, buffer);
inc(next_frame_to_send);
}
从等待确认的帧开始全部重发
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层92 / 159
后退后退nn帧的滑动窗口协议帧的滑动窗口协议
((WWT T = 2= 2n n --11, W, WR R = 1= 1))
如果编号由n位组成,则发送窗口
WT = 2n -1,接收窗口WR = 1
即管道化(pipelining)协议
Tnbm P220 Fig. 3-17 (协议5 )
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层93 / 159
三个窗口协议三个窗口协议(协议(协议44--66))
发送窗口WT=1,接收窗口WR=1
Tnbm P215 Fig.3-14 一位滑动窗口协议(协议4)
发送窗口WT=7,接收窗口WR=1
Tnbm P220 Fig.3-17 后退n帧的滑动窗口协议(协议5 )
发送窗口WT=4,接收窗口WR=4
Tnbm P224 Fig.3-19 选择性重发滑动窗口协议(协议6)
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层94 / 159
选择性重发窗口协议图例选择性重发窗口协议图例
有一个差错时仅重发一帧(接收窗口和发送窗口都为7)
超时间隔
出错将分组2 ~ 8交网络层被数据链路层丢弃的帧
发
收
0
ACK0ACK1ACK8ACK9ACK10ACK11
12111092876543141312
01E34567821110912
ACK1ACK1ACK1ACK1ACK1ACK1
Tnbm P218 Fig. 3-16 (b)
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层95 / 159
选择性重发窗口协议选择性重发窗口协议
((WWT T = 2= 2n n /2/2,,,W,WR R = 2= 2n n /2/2))
如果编号由n位组成:
发送窗口WT = 2n/2,接收窗口WR = 2n/2
当接收到一个错帧(包括CRC错或帧序号错)
时,发送一个否定性确认NAK
接收方定义了一个辅助计时器
Tnbm P224 Fig.3-19 (协议6)
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层96 / 159
选择性重发窗口协议程序选择性重发窗口协议程序
void protocol6(void)
{
enable_network_layer();
ack_expected = 0;
next_frame_to_send = 0;
frame_expected = 0;
too_far = NR_BUFS;
nbuffered = 0;
for (i = 0; i < NR_BUFS;i++) arrived[i] = false;
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层97 / 159
while (true)
{ wait_for_event(&event);
switch (event)
{ case network_layer_ready:
case frame_arrival:
case cksum_err:
if (no_nak) send_frame(nak,0, frame_expected, out_buf);
case timeout:
send_frame(data, oldest_frame, frame_expected, out_buf);
case ack_timeout:
send_frame(ack, 0, frame_expected, out_buf);
}
if (nbuffered =0168
01111110地址控制数据校验和01111110
帧标志序列即01111110,作为帧的分隔标志,如线路空闲,
则用标志序列填充,用位插入方法实现透明传输
地址域在总线型多终端情况下,是终端的站号;在点对
点的情况下,用来标志命令和响应
控制域定义帧的类型,序号等和其它一些功能
数据域用户数据,长度任意
校验和CRC码,ISO和CCITT有相似的生成多项式
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层125 / 159
HDLCHDLC的帧类型的帧类型
HDLC的帧有三种类型,不同的类型其
控制域的定义有些不同
信息帧(I):Information Frame
监控帧(S):Supervisory Frame
无序号帧(U):Unnumbered Frame
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层126 / 159
信息帧(信息帧(II))
0当前发送帧号P/F捎带确认帧号
P/F(Poll/Final)位:
P 主机查询哪个终端要发送数据
F 终端发送数据的最后一帧用F
捎带确认帧号:
即下一个期望接收帧号,意味着以前的帧
的接收确认
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层127 / 159
HDLCHDLC的帧类型的帧类型
HDLC的帧有三种类型,不同的类型其
控制域的定义有些不同
信息帧(I):Information Frame
监控帧(S):Supervisory Frame
无序号帧(U):Unnumbered Frame
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层128 / 159
监控帧监控帧((SS))
监控帧有四种格式
1000P/F捎带确认号
1001P/F捎带确认号
1010P/F捎带确认号
1011P/F捎带确认号
RR
RNR
REJ
SREJ
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层129 / 159
接收准备好接收准备好
RR(Receive Ready):接收准备好
即确认Next-1及Next-1帧以前的所有
帧,并准备好接收Next帧
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层130 / 159
监控帧监控帧((SS))
监控帧有四种格式
1000P/F捎带确认号
1001P/F捎带确认号
1010P/F捎带确认号
1011P/F捎带确认号
RR
RNR
REJ
SREJ
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层131 / 159
接收未准备好接收未准备好
RNR(Receive Not Ready):接收未
准备好
即确认Next-1及Next-1帧以前的帧,并
要求发送方停止发送
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层132 / 159
监控帧监控帧((SS))
监控帧有四种格式
1000P/F捎带确认号
1001P/F捎带确认号
1010P/F捎带确认号
1011P/F捎带确认号
RR
RNR
REJ
SREJ
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层133 / 159
拒绝接收拒绝接收
REJ(REJect):拒绝接收
即否定性确认,确认Next-1及Next-1帧
以前的所有帧,并要求重发Next及Next
以后的所有帧
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层134 / 159
监控帧监控帧((SS))
监控帧有四种格式
1000P/F捎带确认号
1001P/F捎带确认号
1010P/F捎带确认号
1011P/F捎带确认号
RR
RNR
REJ
SREJ
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层135 / 159
选择性拒收选择性拒收
SREJ(Selective REJect):选择性拒收
即否定性确认,确认Next-1及Next-1帧以
前的所有帧,并仅要求重发Next帧.(此
类型在SDLC及LAPB中不允许)
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层136 / 159
HDLCHDLC的帧类型的帧类型
HDLC的帧有三种类型,不同的类型其
控制域的定义有些不同
信息帧(I):Information Frame
监控帧(S):Supervisory Frame
无序号帧(U):Unnumbered Frame
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层137 / 159
无序号帧(无序号帧(UU))
控制字段的1,2 bit都为1的帧为无序号帧
无序号帧用于控制链路本身.如呼叫,确认
和断开连接等控制
在无序号帧中用5位(3,4,6,7,8)来表
示无序号帧的类型,但32种可能的类型中有
些是保留的,并且,不同的协议中,无序号
类型区别很大(略)
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层138 / 159
HDLCHDLC帧的校验帧的校验
CRC校验
生成多项式为X16+X12+X5+1
校验范围
FACIFCSF
校验范围
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层139 / 159
数据链路层示例数据链路层示例
HDLC -高级数据链路层控制
因特网中的数据链路层
SLIP ---串型线路IP
PPP ---点对点协议
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层140 / 159
因特网模型因特网模型11
因特网中的网络互联
Internet
R
R
S
PC
PC
PC
PC
R
S
PC
PC
PC
PC
R
其中的路由器之间是通过点对点来连接的
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层141 / 159
因特网模型因特网模型22
因特网中家庭用户的入网
InternetRSW
PC
PC
Server
ISP
Access
Server
PSTN
PC
PCM
M
MMMMM
远程家庭用户通过拨号与ISP联接后,采用点对点方式连接
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层142 / 159
因特网中的数据链路层因特网中的数据链路层
SLIP ---串型线路IP
(Serial Line IP )
PPP ---点对点协议
(Pointe -to -Point Protocol)
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层143 / 159
SLIP SLIP ------串型线路串型线路IPIP
SLIP ---串型线路IP(Serial Line IP )
协议简单,无差错控制,只适用于IP,
通信的每一方必须事先知道对方的IP地
址,只支持低速的业务(19.2K)
未成为标准,不详细介绍
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层144 / 159
因特网中的数据链路层因特网中的数据链路层
SLIP ---串型线路IP
(Serial Line IP )
PPP ---点对点协议
(Pointe -to -Point Protocol)
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层145 / 159
PPP PPP ------点对点协议点对点协议
PPP ---点对点协议
(Pointe -to -Point Protocol)
PPP的功能
PPP的组成部分
PPP的帧格式
PPP的链路控制协议
PPP的工作过程
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层146 / 159
PPPPPP的功能的功能
PPP是Internet标准
(RFC1661 1662 1663)
处理错误监测
支持多种协议(IP,IPX,DECnet等)
连接时允许协商IP地址
允许身份认证
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层147 / 159
PPP PPP ------点对点协议点对点协议
PPP ---点对点协议
(Pointe -to -Point Protocol)
PPP的功能
PPP的组成部分
PPP的帧格式
PPP的链路控制协议
PPP的工作过程
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层148 / 159
PPPPPP的组成部分的组成部分
PPP提供了串行点对点链路上传输数据报的
方法,包括以下三个部分:
串行链路上封装数据报的方法.既支持异步链
路,也支持面向bit的同步链路
扩展的链路控制协议(Link Control Protocol -
LCP),用于建立,配置和测试数据链路的连接
网络控制协议(NCP)簇,支持各种网络层协议
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层149 / 159
PPP PPP ------点对点协议点对点协议
PPP ---点对点协议
(Pointe -to -Point Protocol)
PPP的功能
PPP的组成部分
PPP的帧格式
PPP的链路控制协议
PPP的工作过程
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层150 / 159
PPPPPP的帧格式的帧格式
PPP的帧格式类似于HDLC,但是面向
字符的协议(以字节为单位)
1111/2可变2/41
标志
01111110
地址
11111111
控制
00000011
协议有效载荷校验和
标志
01111110
标志域:固定为01111110,与HDLC相同
地址域:固定为11111111
控制域:缺省为00000011,即无序号帧
(即毋需确认)
协议域:不同的协议不同的代码
载荷域:可变长,缺省最长1500字节
校验和:缺省为2字节,也可定义为4
字节,仅是头部的校验和
由于地址域和控制域基本固定,所以在LCP中省略
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层151 / 159
PPP PPP ------点对点协议点对点协议
PPP ---点对点协议
(Pointe -to -Point Protocol)
PPP的功能
PPP的组成部分
PPP的帧格式
PPP的链路控制协议
PPP的工作过程
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层152 / 159
PPPPPP的链路控制协议的链路控制协议LCPLCP
PPP的LCP (Link Control Protocol)提供
了建立,配置,维护和终止点对点链接的方法
LCP的过程按以下四个阶段进行:
链路的建立和配置协调
链路质量检测
网络层协议配置阶段
关闭链路
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层153 / 159
LCPLCP帧的类型帧的类型
LCP帧的类型有三种:
链路建立帧:建立和配置链路
链路终止帧:终止链路
链路维护帧:管理,维护链路
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层154 / 159
PPP PPP ------点对点协议点对点协议
PPP ---点对点协议
(Pointe -to -Point Protocol)
PPP的功能
PPP的组成部分
PPP的帧格式
PPP的链路控制协议
PPP的工作过程
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层155 / 159
PPPPPP的工作过程的工作过程
发送端PPP首先发送LCP帧,以配置和测试数据链路
在LCP建立好数据链路并协调好所选设备之后,发送端
PPP发送NCP帧,以选择和配置一个或多个网络协议
当所选的网络层协议配置好后,便可将各网络层协议的
分组发送到数据链路上
配置好的链路将一直保持通信状态,直到LCP帧或NCP
帧明确提示关闭链路,或有其它的外部事件发生(如用
户干预等)
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层156 / 159
一次使用一次使用PPPPPP协议的过程协议的过程
1.初始状态
2.建立连接:建立成功到3),否则到1)
3.选项协商:协商成功到4),否则到7)
4.身份认证:认证成功到5),否则到7)
5.配置网络:网络配置完后到6)
6.数据传输:数据传输完后到7)
7.释放链路:回到1)
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层157 / 159
一次使用一次使用PPPPPP协议的状态图协议的状态图
死
终止打开
线路检测到
完成线路丢弃掉
两边认可选项
NCP配置
失败失败
身份认证成功
身份认证建立
网络
Tnbm P241 Fig. 3-28
建立/取消线路的简化阶段流程图
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层158 / 159
第第33章章习题习题
Tnbm P243
#5 ,#15,#17 (#11)
#18 (#12) ,#29 (#22)
#31 (#24)
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层159 / 159
v3v3中没有的习题中没有的习题
5. A bit string, 0111101111101111110, needs to be transmitted at
the data link layer. What is the string actually transmitted after bit
stuffing
15. A bit stream 10011101 is transmitted using the standard CRC
method described in the text. The generator polynomial is x3+1.
Show the actual bit string transmitted. Suppose the third bit from
the left id inverted during transmission. Show that this error is
detected at the receiver's end.
·上一篇：本章首先介绍客户-服务器事务概念我们从使用Uftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层1 / 159
第第33章章数据链路层数据链路层
定义,功能
数据帧的组成
可靠性传输
数据链路层示例
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层2 / 159
数据链路层的定义数据链路层的定义
网络层有个实体即进程,数据链路层将借
助于物理层为网络层提供服务
为网络层提供一个较好定义的服务接口
定义一个合适的传输差错率
对传输的数据流进行管理,以免快速的
发送淹没慢速的接收端
数据链路层的协议数据单元(PDU)是帧
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层3 / 159
数据链路层的功能数据链路层的功能
数据链路层的任务是把网络层的数据组合成
帧,加上一定的校验,然后交物理层用某种
信号表示二进制数据位送到目的计算机,并
通过目的计算机的物理层和数据链路层送到
网络层,也就是为网络层提供一条可靠的数
据链路
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层4 / 159
相连,物理链路和数据链路相连,物理链路和数据链路
所谓相连,可以理解为物理的连接,但当采用
多路复用技术时也可以是信道连接.其特征是
传输的数据是顺序的
物理链路:一段无源的点到点的物理连接,中
间没有任何交换节点
数据链路:一条物理连接加上为实现数据的传
输,两端配置的硬件和相关的通信协议
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层5 / 159
数据链路层服务的区分规则数据链路层服务的区分规则
数据链路层的服务是通过有无连接,有
无确认来区分的
无确认无连接
有确认无连接
有确认有连接
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层6 / 159
确认和连接确认和连接
确认:接收方在收到数据帧后,必须给
发送方发回一个确认
面向连接:发送方和接收方在传输数据
之前必须建立逻辑连接,传输结束后必
须释放连接
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层7 / 159
数据链路层的服务数据链路层的服务
无确认无连接
有确认无连接
有确认有连接
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层8 / 159
无确认是指接收方在收到数据帧后,毋需发回一
个确认
无连接服务是指在数据传输前毋需建立逻辑链路
物理线路的连接并非意味着提供有连接的服务
无确认并非不可靠,其可靠性由上层负责
例如:局域网共享信道毋需建立连接
信道较为理想,数据传输的误码率很低
即使出错或丢失由上层负责恢复
无确认的面向无连接服务无确认的面向无连接服务
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层9 / 159
数据链路层的服务数据链路层的服务
无确认无连接
有确认无连接
有确认有连接
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层10 / 159
有确认的面向无连接服务有确认的面向无连接服务
使用前不建立连接,即不建立数据链路,但
每帧传输必须得到确认
这在信号传播延时较大,线路状态不一定很
可靠的情况下是有效的
例如:无线通信如建立连接,则信道使用率很低
但数据传输的误码率相对较高,
确认是必要的
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层11 / 159
数据链路层的服务数据链路层的服务
无确认无连接
有确认无连接
有确认有连接
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层12 / 159
有确认的面向连接服务有确认的面向连接服务
使用前先建立连接,即先建立数据链路,
并且每帧的传输必须得到确认
有连接的服务必须在使用前先建立连接
(即建立逻辑链路),然后使用,最后
释放连接
例如:电话
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层13 / 159
数据的可靠传输数据的可靠传输
保证直接相连的两台主机的可靠性传输
将传输的信息组合成帧
校验和重发
流量控制
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层14 / 159
第第33章章数据链路层数据链路层
定义,功能
数据帧的组成
可靠性传输
数据链路层示例
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层15 / 159
数据帧的组成数据帧的组成
帧的组成必须保证能识别一个完整的帧,并保证一
旦出现传输差错导致前一个帧丢失,也必须能识别
下一个帧,即再同步
字符计数法
带字符填充的首尾界符法
带位填充的首尾标志法
物理层编码违例法
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层16 / 159
字符计数法字符计数法
帧的长度用一个字节表示,作为帧的头部
帧长度计数
第1帧第4帧第3帧第2帧
51234567898012345687890123
帧长度计数错
51234367898012345687890123
第1帧第第2帧第3帧4帧
Tnbm P188 Fig. 3-4 字符计数成帧法
一旦帧长度计数被误读,将无法再同步,所以很少采用
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层17 / 159
数据帧的组成数据帧的组成
帧的组成必须保证能识别一个完整的帧,并保证一
旦出现传输差错导致前一个帧丢失,也必须能识别
下一个帧,即再同步
字符计数法
带字符填充的首尾界符法
带位填充的首尾标志法
物理层编码违例法
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层18 / 159
带字符填充的首尾界符法带字符填充的首尾界符法
用特殊的字符作为帧头和帧尾
FLAGHeaderPayload field TrailerFLAG
Tnbm P189 Fig. 3-5 (a) 由Flag标志的一个帧
这是一种面向字符的帧格式,所传输的数据都是字符
(ASCII或EBCDIC字符),但帧中不允许出现帧界符
标志,在面向字符的串型通信中常使用这种格式(PPP)
接收方一旦丢失了一个FLAG,只要继续搜索下一个
FLAG,就可重新确定帧边界,即具有再同步能力
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层19 / 159
面向字符的帧格式面向字符的帧格式
面向字符的帧格式不适宜传输数据中包含二进制数的帧,因为
在包含二进制数的帧中很可能出现FLAG的字符(通常FLAG用
ASCII字符7EH定义)
一种方法是在二进制数中偶然出现的FLAG前再插入一个ESC
(ASCII字符1BH),这就称为字符填充法
41 33 7E9C 4B 0C
41 33 1B9C 4B 0C
41 33 1B7E9C 4B 0C
41 33 1B1B9C 4B 0C
41 33 1B7E9C 4B 0C
41 33 1B 1B9C 4B 0C
41 33 1B1B 1B7E9C 4B 0C
41 33 1B1B 1B 1B9C 4B 0C
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层20 / 159
数据帧的组成数据帧的组成
帧的组成必须保证能识别一个完整的帧,并保证一
旦出现传输差错导致前一个帧丢失,也必须能识别
下一个帧,即再同步
字符计数法
带字符填充的首尾界符法
带位填充的首尾标志法
物理层编码违例法
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层21 / 159
带位填充的首尾标志法带位填充的首尾标志法
字符并非都是8位的,东方文字是16位的,UNICODE是16位的
在面向二进制位的同步串型通信中常使用带
位填充的首尾标志格式,如HDLC
这是一种面向二进制位的帧格式,把所有需传输的数据(不论是字符
或表示一个浮点数的二进制位串,还是一个MP3的文件)一字排开,
并以特殊的位模式01111110作为帧标志,即一个帧的开始(同时标志
前一个帧的结束)
如果由于干扰,一个帧标志没有正确接收,则继续扫描接收串,一旦
扫描到01111110,即新的一帧从此开始,即具有再同步能力
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层22 / 159
面向面向bitbit的帧格式的帧格式
当帧中出现一个与帧标志相同的位串01111110,则
在5个1后插入一个0,即变成01111101,接收方将自
动删除第5 个1后的0
这称为位插入法,也称为透明传输
011011111111111111110010
011011111011111011111010010
011011111111111111110010
Tnbm P190 Fig. 3-6 (a) (b) (c) 位插入法示例
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层23 / 159
数据帧的组成数据帧的组成
帧的组成必须保证能识别一个完整的帧,并保证一
旦出现传输差错导致前一个帧丢失,也必须能识别
下一个帧,即再同步
字符计数法
带字符填充的首尾界符法
带位填充的首尾标志法
物理层编码违例法
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层24 / 159
物理层编码违例法物理层编码违例法
在曼切斯特编码中,连续高电平或连续
低电平可用作帧边界
采用冗余编码技术,如曼切斯特编码,即两个采样脉冲才可得
到一个二进制位
数据0:低-高电平对
数据1:高-低电平对
高-高电平对和低-低电平对没有使用,如在二进制
编码中出现称为编码违例,但这两种违例编码可用
作帧边界,在令牌环网中使用编码违例格式
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层25 / 159
第第33章章数据链路层数据链路层
定义,功能
数据帧的组成
可靠性传输
数据链路层示例
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层26 / 159
可靠性传输可靠性传输
差错控制:校验,重发和序号
流量控制:窗口协议
协议描述和验证
避免帧错误的保证:帧的校验
避免帧丢失的保证:超时和重发
避免帧重复的保证:帧有序号
发送方和接收方之间的协调
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层27 / 159
差错控制差错控制
如何保证数据帧的正常传输:通过三
种手段处理三种可能出现的情况:
确认
数据帧丢失
重复帧
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层28 / 159
确认确认
接收方在收到了正确的帧后向发送方发
肯定性确认.如收到的帧有问题,则发
否定性确认,此时发送方将重发此帧
确认的前提是必须经过差错检测
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层29 / 159
差错检测和校正差错检测和校正
超时只是传输出错的一种情况,更多的传输出
错是数据中的一位或几位因噪声干扰而出错
噪声分两种:
信道所固有的,持续存在的随机热噪声
外界突发原因而造成的冲击噪声
通常接收方应能检错,甚至纠错
纠错码是除m个数据位外增加r个冗余位作为
纠错位,整个长度为n = m + r
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层30 / 159
纠错码:
检错码:
海明(Hamming)码
校验和(Check Sum)
块校验码(Block Check Code)
循环冗余检错码CRC
(Cyclic Redundancy Check)
纠错码和检错码纠错码和检错码
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层31 / 159
海明海明((HammingHamming))纠错码纠错码
m个数据位外加r 个纠错位.在2i(i=0,1,2,3…) 的
位置放的是纠错位.m个数据位的次序不变.如
字符m的7位二进制码为1101101,要加上4位纠
错码0011(偶校验),共11个bit.
1110987654321
A7
1
A5A6
10
P4
0
A4A3A2P3A1P2P1
1100111
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层32 / 159
信息位影响的纠错位信息位影响的纠错位
一个信息位影响多个纠错位
信息位信息组位组位展开影响的纠错位
A711=8+2+1对P4,P2,P1有影响
A610=8+2对P4,P2有影响
A59=8+1对P4,P1有影响
A47=4+2+1对P3,P2,P1有影响
A36=4+2对P3,P2有影响
A25=4+1对P3,P1有影响
A13=2+1对P2,P1有影响
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层33 / 159
纠错位的取值纠错位的取值
一个纠错位由多个信息异或然后取偶/奇校验
纠错位纠错位的取值(再取偶/奇校验)
P4=A7⊕A6⊕A5
P3=A4⊕A3⊕A2
P2=A7⊕A6⊕A4⊕A3⊕A1
P1=A7⊕A5⊕A4⊕A2⊕A1
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层34 / 159
海明码纠错位取值举例海明码纠错位取值举例
采用偶校验
1110987654321
A7
1
A5A6
10
P4
0
A4A3A2P3A1P2P1
1100111
检错位纠错位的取值(再取偶校验)
P4=A7⊕A6⊕A5 =0
P3=A4⊕A3⊕A2 =0
P2=A7⊕A6⊕A4⊕A3⊕A1 =1
P1=A7⊕A5⊕A4⊕A2⊕A1 =1
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层35 / 159
接收方的校验接收方的校验
校验位校验位计算表达式
S4=A7⊕A6⊕A5⊕P4
S3=A4⊕A3⊕A2⊕P3
S2=A7⊕A6⊕A4⊕A3⊕A1⊕P2
S1=A7⊕A5⊕A4⊕A2⊕A1⊕P1
计算结果S4 S3 S2 S1为0 0 0 0意味着接收正确
计算结果S4 S3 S2 S1为0 1 0 1意味着第5位出错
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层36 / 159
接收方的校验举例接收方的校验举例(无错)(无错)
字符m采用海明码的发送序列为11001100111
如接收到的序列也为11001100111
1110987654321
A7A6A5P4A4A3A2P3A1P2P1
11001100111
校验位校验位计算表达式的值
S4
S3
S2
S1
=A7⊕A6⊕A5⊕P4=1⊕1⊕0⊕0=0
=A4⊕A3⊕A2⊕P3=1⊕1⊕0⊕0=0
=A7⊕A6⊕A4⊕A3⊕A1⊕P2=1⊕1⊕1⊕1⊕1⊕1=0
=A7⊕A5⊕A4⊕A2⊕A1⊕P1=1⊕0⊕1⊕0⊕1⊕1=0
S4 S3 S2 S1 = 0 0 0 0意味校验正确
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层37 / 159
接收方的校验举例接收方的校验举例(有错)(有错)
字符m采用海明码的发送序列为11001100111
如接收到的序列为11001110111
1110987654321
A7A6A5P4A4A3A2P3A1P2P1
11001110111
校验位校验位计算表达式的值
S4
S3
S2
S1
=A7⊕A6⊕A5⊕P4=1⊕1⊕0⊕0=0
=A4⊕A3⊕A2⊕P3=1⊕1⊕1⊕0=1
=A7⊕A6⊕A4⊕A3⊕A1⊕P2=1⊕1⊕1⊕1⊕1⊕1=0
=A7⊕A5⊕A4⊕A2⊕A1⊕P1=1⊕0⊕1⊕1⊕1⊕1=1
S4 S3 S2 S1 = 0 1 0 1意味第5位出错
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层38 / 159
纠错码:
检错码:
海明(Hamming)码
校验和(Check Sum)
块校验码(Block Check Code)
循环冗余检错码CRC
(Cyclic Redundancy Check)
纠错码和检错码纠错码和检错码
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层39 / 159
校验和校验和
算法简单,实现容易,但检错率不高
以16位为例:
4865H+6C6CH+6F20H+776FH+726CH+642EH+进位=71FCH
Helloworld.
48656C6C6F20776F726C642E71FC
将发送的数据看成是二进制整数序列,并划分成一段段
规定的长度(如8位,16位,32位等),计算他们的
和.如校验和大于规定的长度,则将进位加到最后的校
验和中.将校验和和数据一起发送.在接收端,重新计
算校验和,与原校验和比较.如要传输"Hello world."
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层40 / 159
纠错码:
检错码:
海明(Hamming)码
校验和(Check Sum)
块校验码(Block Check Code)
循环冗余检错码CRC
(Cyclic Redundancy Check)
纠错码和检错码纠错码和检错码
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层41 / 159
块校验码块校验码
块校验码BCC(Block Check Code)简单
常用,但检错的强度较弱,如在同一列上有
偶数位错,则不能检测
如传输的数据都是ASCII字符(即面向字符,这在应用中很
多),每个字符进行奇偶校验,然后把所有的字符(连同奇偶
位)进行异或运算,运算结果即为其块校验码.发送端一面发
送一面计算,最后发送块校验码,接收端一面接收一面计算,
最后与接收到的块校验码比较
如"Hello world.",采用偶校验,校验后的字符序列为:
Helloworld.
48656C6C6FA0776F726CE42E2E
48H⊕65H⊕6CH⊕6CH⊕6FH⊕A0H⊕77H⊕6FH⊕72H
⊕6CH⊕E4H⊕2EH = 2EH
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层42 / 159
纠错码:
检错码:
海明(Hamming)码
校验和(Check Sum)
块校验码(Block Check Code)
循环冗余检错码CRC
(Cyclic Redundancy Check)
纠错码和检错码纠错码和检错码
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层43 / 159
循环冗余检错码循环冗余检错码CRCCRC
任何一个k位的帧看成为一个k-1次的多项式M(x)
如:1011001看成x6+x4+x3+x0
设定一个多项式编码生成多项式G(x),G(x)为r阶,k>r
如xrM(x)/G(x) = Q(x) + R(x)/G(x) 其中Q(x)为商,R(x)为
余数,R(x)即为M(x)的CRC码
将CRC码接在帧后一起发送,即发送数据为xrM(x) + R(x)
二进制运算中,减法和加法都做异或运算:0+1=1,1+1=0
因为( xrM(x) -R(x) )一定能被G(x)整除,即余数为0,则接
收方只要计算的余数为0即为正确
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层44 / 159
CRCCRC码计算举例码计算举例
如一帧为1101011011
即:M(x)= x9+x8+x6+x4+x3+x+1
G(x)=x4+x+1
T(x)= x4M(x)
=x4(x9+x8+x6+x4+x3+x+1)
=x13+x12+x10+x8+x7+x5+x4
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层45 / 159
CRCCRC码计算举例码计算举例(续(续11))
帧:1101011011
除数:10011
实际传输帧:
1100001010
1001111010110110000
10011
10011
10011
00001
00000
00010
00000
00101
00000
01011
00000
10110
10011
01010
00000
10100
10011
01110
00000
1110
余数
11010110111110
帧数据余数
TnbmP198 Fig. 3-8 CRC码计算举例
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层46 / 159
CRCCRC码计算举例码计算举例(续(续22))
11010110110000/10011
= 1100001010 ……1110
即11010110110000 + 1110能被10011整除
(模2运算的加,减和异或,其运算结果相同)
如发送方发送的T(x),接收方收到的是
T(x)+E(x),除非E(x)是G(x)的整倍数,否则不能
被整除,即都能被检测到已出错
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层47 / 159
三个生成多项式国际标准三个生成多项式国际标准
CRC-12:x12 + x11 + x3 + x2 + x1 + 1
用于字符长度为6位
CRC-16 :x16 + x15+ x2+ 1
用于字符长度为8位
CRC-CCITT:x16 + x12+ x5+ 1
用于字符长度为8位
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层48 / 159
差错控制差错控制
如何保证数据帧的正常传输:通过三
种手段处理三种可能出现的情况:
确认
数据帧丢失
重复帧
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层49 / 159
数据帧丢失数据帧丢失
通过发送方计时器(超时)解决
超时(TimeOut):在传输过程中,所发送
的帧丢失,接收方根本没有收到,不可能发
送确认帧(包括否定性确认),而发送方正
在等待接收方的确认帧,当然也不可能等到
接收方的回音.所以,发送方一旦发送一
帧,就启动一计时器,在规定的时间内,一
般都应收到回音,如收不到回音,则在计时
器溢出时,再重发此帧
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层50 / 159
差错控制差错控制
如何保证数据帧的正常传输:通过三
种手段处理三种可能出现的情况:
确认
数据帧丢失
重复帧
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层51 / 159
重复帧重复帧
重发机制也包括当接收方发送的确认帧
丢失而导致发送方的重发
由于接收方确认帧的丢失,导致发送方
多次发送同一帧,接收方也将多次收到
同一帧,要能区别是否是同一帧,则每
帧都应有一个帧的编号
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层52 / 159
可靠性传输可靠性传输
差错控制:校验,重发和序号
流量控制:窗口协议
协议描述和验证
避免帧错误的保证:帧的校验
避免帧丢失的保证:超时和重发
避免帧重复的保证:帧有序号
发送方和接收方之间的协调
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层53 / 159
流量控制流量控制
发送方和接收方速率的匹配即流量控制
如接收方的处理能力低于发送方,即使传输中没有
出错,也可能被"淹没",所以通常在接收方的缓冲
区到达一定量时,应及时通知发送方,暂停发送,
等候通知,这就是流量控制机制
基本数据链路协议
滑动窗口协议
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层54 / 159
基本数据链路协议基本数据链路协议
可以这样理解:在一台主机中,物理层,数据
链路层,网络层等等都有各自的进程在运行,
并且假设:
A,B两台主机要求可靠的,面向连接的
通信,在接收方的数据链路层,目前正运
行的是wait_for_event(&event),即等待
某个事件发生
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层55 / 159
wait_for_event(&event)wait_for_event(&event)的参数的参数
如发生了某个事件,此过程将返回参数,
event有两个取值:
checksum_err和frame_arrival
如event = checksum_err,意即所接收的帧的校验
和错,应考虑不发送确认帧,或发送否定性确认帧
如event = frame_arrival,即帧已到达并校验正
确,则调用from_physical_layer,从物理层取得
帧,检查帧头的控制信息,如一切正常,则仅把其
中的分组交网络层
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层56 / 159
帧的基本格式帧的基本格式
一般意义上的帧的格式
帧类型顺序号确认号分组
帧头
一系列过程和数据结构的定义:
Tnbm P202 Fig. 3-9
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层57 / 159
协议协议11:一种无限制的单工协议:一种无限制的单工协议
一种理想的环境,理想的协议,假定:
链路是理想的传输通道,所传输的任何数据
既不会出错也不会丢失
即:不需校验,也不可能重发
不管发送方以怎样的速率发送数据,接收方
都能及时接收
即接收端处理器的处理速度无限高,处理时间可忽
略不计,缓冲区空间无限大,毋需流量控制
Tnbm P205 Fig.3-10 一种无限制的单工协议
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层58 / 159
协议协议11::SENDERSENDER
void sender1(void)
{
frame s;
packet buffer;
while (true)
{
from_network_layer(&buffer);
s.info=buffer;
to_physical_layer(&s);
}
}
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层59 / 159
协议协议11::RECEIVERRECEIVER
void receiver1(void)
{
frame r;
event_type event;
while (true)
{
wait_for_event(&event);
from_physical_layer(&r);
to_network_layer(&r.info);
}
}
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层60 / 159
协议协议22:一个单工的停:一个单工的停--等协议等协议
然而,接收方不可能具有足够高的CPU处理能力来
及时处理所有的接收帧,也不可能具有足够大的缓
冲区,但仍假定:
链路是理想的传输通道,所传输的任何数据
既不会出错也不会丢失
即:不需校验,也不可能重发
所以,当它来不及处理时,应通知发送方暂缓发送,
一旦可以继续接收,则通知发送方继续发送
Tnbm P207 Fig.3-11 一个单工的停-等协议
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层61 / 159
协议协议22::SENDERSENDER
void sender2(void)
{ frame s;
packet buffer;
event_type event;
while (true)
{
from_network_layer(&buffer);
s.info=buffer;
to_physical_layer(&s);
wait_for_event(&event);
}
}
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层62 / 159
协议协议22::RECEIVERRECEIVER
void receiver2(void)
{
frame r,s;
event_type event;
while (true)
{
wait_for_event(&event);
from_physical_layer(&r);
to_network_layer(&r.info);
to_physical_layer(&s);
}
}
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层63 / 159
协议协议33:有噪声信道的单工协议:有噪声信道的单工协议
在噪声信道中应考虑传输有差错的情况
所谓差错:
帧的损坏:如帧中若干位出错,通常CRC都能检测到
帧的丢失:一旦帧头出错,接收方将检测下一个帧
头,以同步,但该帧已丢失
帧的重复:如确认帧丢失,接收方将接收到重复帧
所以,发送方应启动一个计时器,一旦超时立即重发
Tnbm P210 Fig. 3-12 一个肯定性确认和超时重发协议
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层64 / 159
协议协议33的要点的要点
发送方要记录下一个准备发送的顺序号
接收方要记录下一个期望接收的顺序号
发送过程和接收过程是严格交替的
接收方收到一个正确的帧,即便不是期望的
帧,都将发送一个确认(即一个空的确认帧)
也称为ARQ协议:
Automatic Repeat reQuest
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层65 / 159
协议协议3: SENDER3: SENDERvoid sender3(void)
{next_frame_to_send=0;
from_network_layer(&buffer);
while (true)
{ s.info=buffer;
s.seq=next_frame_to_send;
to_physical_layer(&s);
start_time(s.seq)
wait_for_event(&event);
if (event==frame_arrival)
{from_physical_layer(&s);
if (s.ack==next_frame_to_send) {
stop_timer(s.ack);
from_network_layer(&buffer);
inc(next_frame_to_send);
}
}
}
}
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层66 / 159
协议协议3: RECEIVER3: RECEIVER
void receiver3(void)
{ frame_expected=0;
while (true)
{ wait_for_event(&event);
if (event==frame_arrival)
{ from_physical_layer(&r);
if (r.seq==frame_expected)
{ to_network_layer(&r.info);
inc(frame_expected); }
s.ack=1-fram_expected;
to_physical_layer(&s);
}
}
}
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层67 / 159
协议协议33的重发机制存在的问题的重发机制存在的问题
效率较低
如接收方收到的帧出错或者整个数据帧丢失,则不
发确认帧,发送方在超时后重发,直至正确(效率
极低)
接收方会收到重复帧
如接收方收到了正确的数据帧并发送了确认,但此
确认丢失,发送方在超时后重发此帧,这样,接收
方的数据链路层收到了两个完全相同的帧,其网络
层将收到两个完全相同的分组(这是不能允许的)
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层68 / 159
流量控制流量控制
发送方和接收方速率的匹配即流量控制
如接收方的处理能力低于发送方,即使传输中没有
出错,也可能被"淹没",所以通常在接收方的缓冲
区到达一定量时,应及时通知发送方,暂停发送,
等候通知,这就是流量控制机制
基本数据链路协议
滑动窗口协议
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层69 / 159
协议协议33的问题的问题
不能双向传输,效率低
由于应答无序号,导致系统不可靠
其实,在协议3中,发送方应重发当前帧还是
发下一帧,仅根据超时还是收到确认而定,
亦即仅与前一帧和后一帧有关,所以,在协
议3中,顺序号仅需一位,0/1
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层70 / 159
双向传输解决方案双向传输解决方案
用四根信道:两根数据,两根应答
但信道利用率很低
用两根信道:一根A到B,另一根B到A
问题是如何区分数据和应答
解决方法有两种:
用不同的帧类型
用捎带确认
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层71 / 159
滑动窗口协议滑动窗口协议
收发使用两条信道
发送方可连续发送多帧,接收方接受到一帧
后就从另一个信道发一个确认,为提高信道
使用效率,可使用捎带确认
帧是有序号的
即使过早超时而导致的重发也可根据帧的序
号来避免帧的重复
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层72 / 159
滑动窗口原理滑动窗口原理(设(设WWTT=5=5,,WWRR=3=3))
发送方
接收方
(a) (b) (c) (d)
0
1
2
34
5
6
70
1
2
34
5
6
70
1
2
34
5
6
70
1
2
34
5
6
7
前沿
后沿
0
1
2
34
5
6
70
1
2
34
5
6
70
1
2
34
5
6
7
前沿
0
1
2
34
5
6
7
后沿
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层73 / 159
三个窗口协议三个窗口协议(协议(协议44--66))
发送窗口WT=1,接收窗口WR=1
Tnbm P215 Fig.3-14 一位滑动窗口协议(协议4)
发送窗口WT=7,接收窗口WR=1
Tnbm P220 Fig.3-17 后退n帧的滑动窗口协议(协议5 )
发送窗口WT=4,接收窗口WR=4
Tnbm P224 Fig.3-19 选择性重发滑动窗口协议(协议6)
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层74 / 159
一位滑动窗口协议一位滑动窗口协议
发送窗口WT=1,接收窗口WR=1
即停-等协议
Tnbm P215 Fig.3-14 (协议4)
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层75 / 159
一位滑动窗口协议一位滑动窗口协议
void protocol4(void)
{ next_frame_to_send=0;
frame_expected=0;
from_network_layer(&buffer);
s.info=buffer;
s.seq=next_frame_to_send;
s.ack=1-frame_expected;
to_physical_layer(&s);
start_time(s.seq) ;
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层76 / 159
while (true)
{ wait_for_event(&event);
if (event==frame_arrival)
{ from_physical_layer(&r);
if (r.seq==frame_expected)
{ to_network_layer(&r.info);
inc(frame_expected); }
if (r.ack==next_frame_to_send)
{ stop_timer(r.ack);
from_network_layer(&buffer);
inc(next_frame_to_send); }
}
s.info=buffer;
s.seq=next_frame_to_send;
s.ack=1-frame_expected
to_physical_layer(&s);
start_time(s.seq)
}
}
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层77 / 159
比较两种情况比较两种情况
情况1:
A端首先发送,B端等待发送,无过早超时,
其运行过程正常
情况2:
A端和B端都同时发送,无过早超时,其运行
过程不正常
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层78 / 159
情况情况11:主机:主机AA发送主机发送主机BB等待等待
主机A
初始化后组成发送
帧,其中:
主机B
初始化后尚未组成发送
帧,在接收到A0帧后交
网络层并组成发送帧,
(捎带确认)其中:
发送帧顺序号seq=0
对接收到的帧的确认
ack=1
实际上此确认无意义
通过物理层发送
发送帧顺序号seq=0
对接收到的帧的确认
ack=0
通知A,0帧收到
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层79 / 159
情况情况11:运行过程正常:运行过程正常A发送(0,1,A0)SeqackA发送A0,seq= 0
B收到(0,1,A0)▲B收到A0
B发送(0,0,B0)B发送B0,并确认A0
A收到(0,0,B0)▲A收到B0及对A0的确认
A发送(1,0,A1)A发送A1及对B0的确认
B收到(1,0,A1)▲B收到A1及对B0的确认
B发送(1,1,B1)B发送B1及对A1的确认
A收到(1,1,B1)▲A收到B1及对A1的确认
A发送(0,1,A2)A发送A2及对B1的确认
B收到(0,1,A2)▲B收到A2及对B1的确认
B发送(0,0,B2)B发送B2及对A2的确认
A收到(0,0,B2)▲A收到B2及对A2的确认
A发送(1,0,A3)A发送A3及对B2的确认
B收到(1,0,A3)▲B收到A3及对B2的确认
B发送(1,1,B3)
Tnbm P216 Fig. 3-15 (a) 协议4,运行过程正常
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层80 / 159
比较两种情况比较两种情况
情况1:
A端首先发送,B端等待发送,无过早超时,
其运行过程正常
情况2:
A端和B端都同时发送,无过早超时,其运行
过程不正常
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层81 / 159
情况情况22::主机主机AA发送主机发送主机BB也发送也发送
主机A
初始化后组成发送
帧,其中:
主机B
初始化后也组成发
送帧,其中:
发送帧顺序号seq=0
对接收到的帧的确认
ack=1
实际上此确认无意义
通过物理层发送
发送帧顺序号seq=0
对接收到的帧的确认
ack=1
实际上此确认无意义
通过物理层发送
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层82 / 159
情况情况22:运行过程不正常:运行过程不正常
A发送(0,1,A0)B发送(0,1,B0)B也已从网络层得到B0
B收到(0,1,A0)▲B以为B0分组A没有收到
B发送(0,0,B0)所以B又重发B0分组
A收到(0,1,B0)▲A以为A0分组B没有收到
A发送(0,0,A0)所以A又重发A0分组
B收到(0,0,A0)B收到对B0的确认并丢弃A0
B发送(1,0,B1)B发送B1及对A0的确认
A收到(0,0,B0)A收到对A0的确认并丢弃B0
A发送(1,0,A1)A发送A1及对B0的确认
B收到(1,0,A1)▲B以为B1分组A没有收到
B发送(1,1,B1)所以B又重发B1分组
A收到(1,0,B1)▲A以为A1分组B没有收到
A发送(1,1,A1)所以A又重发A1分组
B收到(1,1,A1)B收到对B1的确认并丢弃A1
B发送(0,1,B2)
Tnbm P216 Fig. 3-15 (b) 协议4,运行过程不正常
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层83 / 159
三个窗口协议三个窗口协议(协议(协议44--66))
发送窗口WT=1,接收窗口WR=1
Tnbm P215 Fig.3-14 一位滑动窗口协议(协议4)
发送窗口WT=7,接收窗口WR=1
Tnbm P220 Fig.3-17 后退n帧的滑动窗口协议(协议5 )
发送窗口WT=4,接收窗口WR=4
Tnbm P224 Fig.3-19 选择性重发滑动窗口协议(协议6)
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层84 / 159
退后退后nn帧的协议帧的协议
协议4的主要问题是信道利用率太低:
发送端的等待时间至少是发送端到接收端信号传播时间
的两倍
信道的利用率为:
数据发送时间/从数据发送开始到确认返回的总耗时
发送管道化(pipelining):
在等待确认的时间内连续发送
存在的问题主要是信道不可靠:
一旦数据帧丢失,在发送端在意识到丢失(TimeOut)
时,已有大量数据帧到达接收端
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层85 / 159
退后退后n n 帧协议(帧协议(go back ngo back n))
当接收端发现一错帧后,抛弃此帧及以后所
有收到的帧,不发确认.当发送端出现超时
(错帧的TimeOut)后,重发自该帧起的所
有已发送帧
问题:浪费带宽
发送方连续发送了7帧(2 ~ 8),但2#帧无确
认,超时后,从2#帧起开始重发
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层86 / 159
后退后退nn帧的滑动窗口协议帧的滑动窗口协议图例图例
有一个差错时后退n帧(接收窗口为1,发送窗口为7)
超时间隔
出错时间被数据链路层丢弃的帧
发
收
0
ACK0ACK1ACK2ACK3ACK4ACK5
125432876543876
01EDDDDDD25436
Tnbm P218 Fig. 3-16 (a)
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层87 / 159
后退后退nn帧的滑动窗口协议帧的滑动窗口协议程序程序
void protocol5(void)
{
enable_network_layer();
ack_expected = 0;
next_frame_to_send = 0;
frame_expected = 0;
nbuffered = 0;
0
1
2
34
5
6
7
Next_frame_to_send
ack_expected
nbuffered = 3
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层88 / 159
while (true)
{ wait_for_event(&event);
switch (event)
{case network_layer_ready:
network_layer_ready处理;
case frame_arrival: frame_arrival处理;
case cksum_err: 暂且忽略;
case timeout:timeout处理;
}
if nbuffered < MAX_SEQ)
enable_network_layer();
else disable_network_layer();
}
}
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层89 / 159
network_layer_readynetwork_layer_ready处理处理::
from_network_layer
(&buffer[next_frame_to_send]);
nbuffered = nbuffered + 1;
send_data
(next_frame_to_send,
frame_expected,buffer);
inc(next_frame_to_send);
装配一个数据帧
并发送,发送缓
冲区数+1,准备
发送下一数据帧
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层90 / 159
frame_arrivalframe_arrival处理:处理:
from_physical_layer(&r);
if (r.seq == frame_expected)
{ to_network_layer(&r.info);
inc(frame_expected);
}
while (between(ack_expected, r.ack,
next_frame_to_send))
{ nbuffered = nbuffered -1;
stop_timer(ack_expected);
inc(ack_expected);
}
如收到一个数据帧
则交网络层,并期
望接收下一数据帧
如收到一个确认帧
则释放一个缓冲区
定时器复位,并期
望接收下一确认帧
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层91 / 159
TimeOutTimeOut处理:处理:
next_frame_to_send = ack_expected;
for ( i = 1; i <= nbuffered; i++)
{
send_data(next_frame_to_send,
frame_expected, buffer);
inc(next_frame_to_send);
}
从等待确认的帧开始全部重发
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层92 / 159
后退后退nn帧的滑动窗口协议帧的滑动窗口协议
((WWT T = 2= 2n n --11, W, WR R = 1= 1))
如果编号由n位组成,则发送窗口
WT = 2n -1,接收窗口WR = 1
即管道化(pipelining)协议
Tnbm P220 Fig. 3-17 (协议5 )
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层93 / 159
三个窗口协议三个窗口协议(协议(协议44--66))
发送窗口WT=1,接收窗口WR=1
Tnbm P215 Fig.3-14 一位滑动窗口协议(协议4)
发送窗口WT=7,接收窗口WR=1
Tnbm P220 Fig.3-17 后退n帧的滑动窗口协议(协议5 )
发送窗口WT=4,接收窗口WR=4
Tnbm P224 Fig.3-19 选择性重发滑动窗口协议(协议6)
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层94 / 159
选择性重发窗口协议图例选择性重发窗口协议图例
有一个差错时仅重发一帧(接收窗口和发送窗口都为7)
超时间隔
出错将分组2 ~ 8交网络层被数据链路层丢弃的帧
发
收
0
ACK0ACK1ACK8ACK9ACK10ACK11
12111092876543141312
01E34567821110912
ACK1ACK1ACK1ACK1ACK1ACK1
Tnbm P218 Fig. 3-16 (b)
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层95 / 159
选择性重发窗口协议选择性重发窗口协议
((WWT T = 2= 2n n /2/2,,,W,WR R = 2= 2n n /2/2))
如果编号由n位组成:
发送窗口WT = 2n/2,接收窗口WR = 2n/2
当接收到一个错帧(包括CRC错或帧序号错)
时,发送一个否定性确认NAK
接收方定义了一个辅助计时器
Tnbm P224 Fig.3-19 (协议6)
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层96 / 159
选择性重发窗口协议程序选择性重发窗口协议程序
void protocol6(void)
{
enable_network_layer();
ack_expected = 0;
next_frame_to_send = 0;
frame_expected = 0;
too_far = NR_BUFS;
nbuffered = 0;
for (i = 0; i < NR_BUFS;i++) arrived[i] = false;
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层97 / 159
while (true)
{ wait_for_event(&event);
switch (event)
{ case network_layer_ready:
case frame_arrival:
case cksum_err:
if (no_nak) send_frame(nak,0, frame_expected, out_buf);
case timeout:
send_frame(data, oldest_frame, frame_expected, out_buf);
case ack_timeout:
send_frame(ack, 0, frame_expected, out_buf);
}
if (nbuffered =0168
01111110地址控制数据校验和01111110
帧标志序列即01111110,作为帧的分隔标志,如线路空闲,
则用标志序列填充,用位插入方法实现透明传输
地址域在总线型多终端情况下,是终端的站号;在点对
点的情况下,用来标志命令和响应
控制域定义帧的类型,序号等和其它一些功能
数据域用户数据,长度任意
校验和CRC码,ISO和CCITT有相似的生成多项式
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层125 / 159
HDLCHDLC的帧类型的帧类型
HDLC的帧有三种类型,不同的类型其
控制域的定义有些不同
信息帧(I):Information Frame
监控帧(S):Supervisory Frame
无序号帧(U):Unnumbered Frame
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层126 / 159
信息帧(信息帧(II))
0当前发送帧号P/F捎带确认帧号
P/F(Poll/Final)位:
P 主机查询哪个终端要发送数据
F 终端发送数据的最后一帧用F
捎带确认帧号:
即下一个期望接收帧号,意味着以前的帧
的接收确认
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层127 / 159
HDLCHDLC的帧类型的帧类型
HDLC的帧有三种类型,不同的类型其
控制域的定义有些不同
信息帧(I):Information Frame
监控帧(S):Supervisory Frame
无序号帧(U):Unnumbered Frame
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层128 / 159
监控帧监控帧((SS))
监控帧有四种格式
1000P/F捎带确认号
1001P/F捎带确认号
1010P/F捎带确认号
1011P/F捎带确认号
RR
RNR
REJ
SREJ
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层129 / 159
接收准备好接收准备好
RR(Receive Ready):接收准备好
即确认Next-1及Next-1帧以前的所有
帧,并准备好接收Next帧
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层130 / 159
监控帧监控帧((SS))
监控帧有四种格式
1000P/F捎带确认号
1001P/F捎带确认号
1010P/F捎带确认号
1011P/F捎带确认号
RR
RNR
REJ
SREJ
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层131 / 159
接收未准备好接收未准备好
RNR(Receive Not Ready):接收未
准备好
即确认Next-1及Next-1帧以前的帧,并
要求发送方停止发送
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层132 / 159
监控帧监控帧((SS))
监控帧有四种格式
1000P/F捎带确认号
1001P/F捎带确认号
1010P/F捎带确认号
1011P/F捎带确认号
RR
RNR
REJ
SREJ
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层133 / 159
拒绝接收拒绝接收
REJ(REJect):拒绝接收
即否定性确认,确认Next-1及Next-1帧
以前的所有帧,并要求重发Next及Next
以后的所有帧
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层134 / 159
监控帧监控帧((SS))
监控帧有四种格式
1000P/F捎带确认号
1001P/F捎带确认号
1010P/F捎带确认号
1011P/F捎带确认号
RR
RNR
REJ
SREJ
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层135 / 159
选择性拒收选择性拒收
SREJ(Selective REJect):选择性拒收
即否定性确认,确认Next-1及Next-1帧以
前的所有帧,并仅要求重发Next帧.(此
类型在SDLC及LAPB中不允许)
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层136 / 159
HDLCHDLC的帧类型的帧类型
HDLC的帧有三种类型,不同的类型其
控制域的定义有些不同
信息帧(I):Information Frame
监控帧(S):Supervisory Frame
无序号帧(U):Unnumbered Frame
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层137 / 159
无序号帧(无序号帧(UU))
控制字段的1,2 bit都为1的帧为无序号帧
无序号帧用于控制链路本身.如呼叫,确认
和断开连接等控制
在无序号帧中用5位(3,4,6,7,8)来表
示无序号帧的类型,但32种可能的类型中有
些是保留的,并且,不同的协议中,无序号
类型区别很大(略)
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层138 / 159
HDLCHDLC帧的校验帧的校验
CRC校验
生成多项式为X16+X12+X5+1
校验范围
FACIFCSF
校验范围
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层139 / 159
数据链路层示例数据链路层示例
HDLC -高级数据链路层控制
因特网中的数据链路层
SLIP ---串型线路IP
PPP ---点对点协议
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层140 / 159
因特网模型因特网模型11
因特网中的网络互联
Internet
R
R
S
PC
PC
PC
PC
R
S
PC
PC
PC
PC
R
其中的路由器之间是通过点对点来连接的
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层141 / 159
因特网模型因特网模型22
因特网中家庭用户的入网
InternetRSW
PC
PC
Server
ISP
Access
Server
PSTN
PC
PCM
M
MMMMM
远程家庭用户通过拨号与ISP联接后,采用点对点方式连接
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层142 / 159
因特网中的数据链路层因特网中的数据链路层
SLIP ---串型线路IP
(Serial Line IP )
PPP ---点对点协议
(Pointe -to -Point Protocol)
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层143 / 159
SLIP SLIP ------串型线路串型线路IPIP
SLIP ---串型线路IP(Serial Line IP )
协议简单,无差错控制,只适用于IP,
通信的每一方必须事先知道对方的IP地
址,只支持低速的业务(19.2K)
未成为标准,不详细介绍
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层144 / 159
因特网中的数据链路层因特网中的数据链路层
SLIP ---串型线路IP
(Serial Line IP )
PPP ---点对点协议
(Pointe -to -Point Protocol)
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层145 / 159
PPP PPP ------点对点协议点对点协议
PPP ---点对点协议
(Pointe -to -Point Protocol)
PPP的功能
PPP的组成部分
PPP的帧格式
PPP的链路控制协议
PPP的工作过程
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层146 / 159
PPPPPP的功能的功能
PPP是Internet标准
(RFC1661 1662 1663)
处理错误监测
支持多种协议(IP,IPX,DECnet等)
连接时允许协商IP地址
允许身份认证
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层147 / 159
PPP PPP ------点对点协议点对点协议
PPP ---点对点协议
(Pointe -to -Point Protocol)
PPP的功能
PPP的组成部分
PPP的帧格式
PPP的链路控制协议
PPP的工作过程
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层148 / 159
PPPPPP的组成部分的组成部分
PPP提供了串行点对点链路上传输数据报的
方法,包括以下三个部分:
串行链路上封装数据报的方法.既支持异步链
路,也支持面向bit的同步链路
扩展的链路控制协议(Link Control Protocol -
LCP),用于建立,配置和测试数据链路的连接
网络控制协议(NCP)簇,支持各种网络层协议
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层149 / 159
PPP PPP ------点对点协议点对点协议
PPP ---点对点协议
(Pointe -to -Point Protocol)
PPP的功能
PPP的组成部分
PPP的帧格式
PPP的链路控制协议
PPP的工作过程
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层150 / 159
PPPPPP的帧格式的帧格式
PPP的帧格式类似于HDLC,但是面向
字符的协议(以字节为单位)
1111/2可变2/41
标志
01111110
地址
11111111
控制
00000011
协议有效载荷校验和
标志
01111110
标志域:固定为01111110,与HDLC相同
地址域:固定为11111111
控制域:缺省为00000011,即无序号帧
(即毋需确认)
协议域:不同的协议不同的代码
载荷域:可变长,缺省最长1500字节
校验和:缺省为2字节,也可定义为4
字节,仅是头部的校验和
由于地址域和控制域基本固定,所以在LCP中省略
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层151 / 159
PPP PPP ------点对点协议点对点协议
PPP ---点对点协议
(Pointe -to -Point Protocol)
PPP的功能
PPP的组成部分
PPP的帧格式
PPP的链路控制协议
PPP的工作过程
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层152 / 159
PPPPPP的链路控制协议的链路控制协议LCPLCP
PPP的LCP (Link Control Protocol)提供
了建立,配置,维护和终止点对点链接的方法
LCP的过程按以下四个阶段进行:
链路的建立和配置协调
链路质量检测
网络层协议配置阶段
关闭链路
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层153 / 159
LCPLCP帧的类型帧的类型
LCP帧的类型有三种:
链路建立帧:建立和配置链路
链路终止帧:终止链路
链路维护帧:管理,维护链路
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层154 / 159
PPP PPP ------点对点协议点对点协议
PPP ---点对点协议
(Pointe -to -Point Protocol)
PPP的功能
PPP的组成部分
PPP的帧格式
PPP的链路控制协议
PPP的工作过程
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层155 / 159
PPPPPP的工作过程的工作过程
发送端PPP首先发送LCP帧,以配置和测试数据链路
在LCP建立好数据链路并协调好所选设备之后,发送端
PPP发送NCP帧,以选择和配置一个或多个网络协议
当所选的网络层协议配置好后,便可将各网络层协议的
分组发送到数据链路上
配置好的链路将一直保持通信状态,直到LCP帧或NCP
帧明确提示关闭链路,或有其它的外部事件发生(如用
户干预等)
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层156 / 159
一次使用一次使用PPPPPP协议的过程协议的过程
1.初始状态
2.建立连接:建立成功到3),否则到1)
3.选项协商:协商成功到4),否则到7)
4.身份认证:认证成功到5),否则到7)
5.配置网络:网络配置完后到6)
6.数据传输:数据传输完后到7)
7.释放链路:回到1)
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层157 / 159
一次使用一次使用PPPPPP协议的状态图协议的状态图
死
终止打开
线路检测到
完成线路丢弃掉
两边认可选项
NCP配置
失败失败
身份认证成功
身份认证建立
网络
Tnbm P241 Fig. 3-28
建立/取消线路的简化阶段流程图
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层158 / 159
第第33章章习题习题
Tnbm P243
#5 ,#15,#17 (#11)
#18 (#12) ,#29 (#22)
#31 (#24)
《Computer Networks v4》cs.sjtu 2004-5-20
ftp://ftp.cs.sjtu.edu.cn/net330第3章数据链路层159 / 159
v3v3中没有的习题中没有的习题
5. A bit string, 0111101111101111110, needs to be transmitted at
the data link layer. What is the string actually transmitted after bit
stuffing
15. A bit stream 10011101 is transmitted using the standard CRC
method described in the text. The generator polynomial is x3+1.
Show the actual bit string transmitted. Suppose the third bit from
the left id inverted during transmission. Show that this error is
detected at the receiver's end.
·下一篇：第7章基本NetWare