第三章 数据链路层 (2)
3.3 数据链路协议
3.4 协议描述与验证
3.5 链路通信规程举例可靠递交
差错帧：
丢失帧：比如比较长的突发噪声造成帧完全丢失
毁坏帧：帧到达接收者，但是帧的检验和不对
ARQ,Automatic Repeat Request
对收到的帧发送 确认
如果超时并且没有收到确认，则 重传 帧停等协议（ 1）
停等协议（ Stop-and-Wait）
发送者在发送一个帧之后停下来，等待对方确认后继续发送下一帧。如果确认在一段时间后无返回，发送者超时，重传帧。
简单版本 （ 协议有问题 !）Sender
while (1) {
transmit (frame i);
try {
receive (ack);
} catch (timeout) {
continue;
}
i++;
break;
}
Receiver
receive (frame);
transmit (ack);
发送者超时接收者
F r a m e
A C K
发送者超时接收者
F r a m e
A C K
F r a m e
A C K
发送者超时接收者
F r a m e
A C K
F r a m e
A C K
发送者超时接收者
F r a m e
F r a m e
A C K
停等协议（ 2）
帧中包含顺序号（ 1比特）字段，确认也包含顺序号
发送方维护 next_frame_to_send，接收方维护 frame_expected
Sender
while (1) {
transmit (frame next_frame_to_send);
try {
while (1) {
receive (ack n);
if (n != next_frame_to_send)
continue;
break;
}
} catch (timeout) {
continue;
}
next_frame_to_send ++;
break;
}
Receiver
frame_expected = 0;
while (1) {
receive (frame n);
ack (frame n);
if (n != frame_expected)
continue;
break;
}
frame_expected ++;
停等协议（ 3）
考虑停等因素的信道利用率：
信道容量 B bps
帧长 L bit
往返传播延迟 2R
忽略 ACK的开销
卫星信道,B=50kbps,2R=0.5s,L=1kb
U=1000/(1000+25000)=1/26
Mbps/Mb/MB和 Kbps/Kb/KB
为了估算方便，而且在不影响结论的情况下，常常采用 Back-of-
the-envelope calculation：假设每个字节 10个比特,106=220
发送者 接收者
2R
Fr a m e
A C K
L /B
RBL
L
RBL
BLU
22
停等协议（ 4）
捎带确认：大部分的通信是双向的,ACK帧通常可由反向发送的数据帧一起捎带回来。
图 3.11给出了捎带确认的例子,B中给出了由于双方不同步而导致每个数据帧都被重传一次的情形。也可以采用单独发送 ACK而不是捎带确认的方法。
停等协议（ 5）
一个更加全面的分析：考虑 ACK、重传、帧头开销
D为帧中有效数据长度,H为帧头长,L=H+D
ACK长度为 H
T表示等待 ACK的超时间隔
P1和 P2分别表示数据帧和 ACK丢失的概率
每个数据帧需要进行重传的概率：
P = 1–（ 1–P1）（ 1–P2）
数据帧的平均传输次数为
平均重传次数为
1 1 1 1)1(k k PPkP
PPP 111 1
发送者 接收者
2R
F r a m e
A C K
( L /B
超时 T
重传
H /B
)2()(1 BHRB DHTB DHPP
B
D
U
停等协议（ 6）
超时间隔 T必须取得足够大，
即 T≥H/B +2R
第一个因子表示停等的因素，第二个表示出错重传的因素，第三个为帧头的开销
假设信道上每比特的误码率为 E，且各比特相互独立：
这样利用率为：
DH
DPP
HRBDH
DH
B
HR
B
DH
P
P
B
D
U
)1)(1(
2
)2)(1
1
(
21
H
DH
EP
EP
)1(1
)1(1
2
1
)(
)1( 2
BTDH
EDU DH
停等协议（ 7）
假设 H,B,T,E不变，求最佳帧长度 Dopt
当 E?0时有
从而 E很小时：
0'?DU
)1)]1l n ()[(41(2D o p t EBTHBTH
)](/[41)]1l n ()/ [ (41 ~ BTHEEBTH
E
BTHD o p t
管道技术,Pipelining（ 1）
停等协议在开始传输一个数据帧到确认回来这一段时间里必须等待，传播时间远大于传输时间的时候会带来很大的浪费。
管道技术,Pipelining（ 2）
停等协议在开始传输一个数据帧到确认回来这一段时间里必须等待，传播时间远大于传输时间的时候会带来很大的浪费。
Pipelining：
发送方可以连续发送多个数据帧，而不用等待确认帧回来。
发送方和接收方可能要求能够缓存数据帧。发送者最少能够缓存那些已经发送的但是没有确认的帧。
如何进行 pipelined的差错恢复？ GBN/SR
L
BRL 2?
回退 N滑动窗口协议 GBN
GBN：接收方只允许顺序接收，也就是说如果一帧出错，则它后面的 N帧尽管可能正确到达接收方，但被直接丢弃，不发送确认。
发送方将超时，按序重传所有未被确认的帧。
选择重传 SR：若某一帧出错，后面送来的正确帧不是简单地丢弃，
而是缓存在接收缓冲区，当发送方意识到坏帧后，只重传坏帧。
一旦重传的帧收到后，与原先已收到但暂存在缓冲区中的其余帧一起按正确的顺序递交。
GBN滑动窗口（ 1）
发送方维护 3个变量：
SWS(Sending Window Size)：发送窗口大小
LAR(Last Acknowledge received)：最近收到的确认
LFS(Last Frame Sent)：最近发送的帧。
L A R L F S
S W S
已确认帧已发送尚未确认帧可以发送但尚未发送帧不能使用 发送方的滑动窗口
S W SL A RL F S
GBN滑动窗口（ 2）
接收方维护 1个变量：
NFE(Next Frame Expected)：期待接收的下一个帧
接收窗口为 1
发送方处理 3个事件：
高层（网络层）发送数据：如果允许，发送
接收到一个 ACK：移动发送窗口，看是否可以发送新的帧
超时：重传已发送但尚未确认的帧,GBN
接收方：
接收的帧序号为 NFE，则递交，并发送 ACK,更新 NFE
否则出错，丢弃帧，并发送 ACK
GBN滑动窗口（ 3）
停等协议可以看成是一个发送窗口等于 1的滑动窗口协议
假设顺序号字段为 n比特，则顺序号会回绕，发送窗口必须小于所有可能的顺序号的个数，即最大只有 2n-1：
以 3比特顺序号为例
发送者发送 0~7
接收者对 7的捎带确认回来，接收方准备接收 0~7帧
发送者发送新的 0~7帧
发送者又收到一个对 7的捎带确认：？？？ 考虑新帧全部丢失的情况
TCP使用顺序号、累加确认、检验和和超时重传机制，和 GBN非常类似，但是许多 TCP的实现都缓冲那些收到的但失序的 TCP段。
SR滑动窗口（ 1）
GBN在出错时要求重传所有未确认的帧,SR只要求重传那些怀疑出错的帧，单独 ACK那些正确接收的帧，
NAK那些出错的帧。
N ex t S eq N u m
S W S
已确认帧已发送尚未确认帧可以发送但尚未发送帧不能使用 发送方的滑动窗口
S en d _ b a s e
R W S
失序但已确认帧期待但是尚未接收的帧可以接收的帧不能使用 接收方的滑动窗口
R c v _ b a s e
SR滑动窗口（ 2）
发送者：
高层发送数据：如果发送窗口允许，则发送
超时：每个帧都要求有一个定时器
ACK：如果等于 send-base,SW移动
NAK：重传帧
接收者：
出错帧：发送 NAK
帧在 [rcv_base,rcv_base+RWS-1]中，缓冲起来，
并且发送 ACK，如果等于 rcv_base，则移动接收窗口
Sliding Window
发送窗口和接收窗口之间的关系？
RWS>SWS：没有任何意义
停等协议对应于 SWS=RWS=1的情况
GBN对应于 RWS=1的情况
RWS? SWS，当 SWS=RWS时,SWS?2n-1：
接收方移动接收窗口并发送 ACK，该 ACK可能会丢失。
协议描述与验证
自然语言描述协议带来二义性
形式描述模型：
协议的描述更加严密
验证协议的正确性和完整性
代码自动生成和一致性测试
两种协议描述模型：
有限状态机 FSM
Petri网有限状态机
FSM(Finite State Machine)：
系统的状态：有限状态
状态的变迁 transition：一定前提条件下，如果一些输入事件发生，系统采取相应的动作，并且转换到另一个状态
以停等协议为例：
系统状态,（发送者状态、接收者状态、信道状态）
发送者状态：发送 0/1号帧
接收者状态：希望接收 0/1号帧
信道状态：信道上有 0/1/A(ACK)帧 /S(没有 )帧
初始状态为 000，即发送者刚发送 0帧，接收方希望接收 0帧，
0帧正在信道上。
Who 收到的帧 发送帧 递交？ 状态变迁
0 - 帧丢失 xxx?xxs
1 R 合法 0帧 ACK Yes 000?01A
2 S ACK 1帧 01A?111
3 R 合法 1帧 ACK Yes 111?10A
4 S ACK 0帧 - 10A?000
5 R 非法 0帧 ACK No 010?01A
6 R 非法 1帧 ACK No 101?10A
7 S Timeout 0帧 - 0XS?0X0
8 S Timeout 1帧 - 1XS?1X1
有限状态机
主变迁路径为 1-2-3-4，信道出错时，偏离主路径，但会回到主路径上来，而且顺序没有改变
丢失 0/1帧比较简单
丢失 ACK复杂一些
ACK没有序号：
半双工信道
（ 00S ） （ 01S ） （ 010 ）
（ 01A ） （ 000 ）
（ 10A ）
（ 101 ） （ 10S ）
（ 111 ）
（ 1 1 S ）
2
1
3 4
5
6
7
8 0
0
8
7
0
0
0
0
有限状态机
全双工信道下的停等协议：
系统状态,（发送者状态、接收者状态、正向数据信道状态、
反向信道状态）
正向信道：信道上有 0/1/S（空）帧
反向信道：信道上有 ACK或 S（空）
新的状态转换图：图 3.16
数据帧和确认帧同时出现在信道上时,2个事件必须一起发生，
比如 2+5
状态变迁序列 000S,01SA,010A,111A,11SA,010S，
01SA,111S导致协议失败：经过事件 1,7,2+5,0,4,5,2。发送者发送 1号帧,0号帧都没有被接收者接收，发送方接着发送新的 1号帧。
pkt 0
pkt 0
pkt 1
pkt 0
pkt 1
A CK
协议描述与验证
自然语言描述协议带来二义性
形式描述模型：
协议的描述更加严密
验证协议的正确性和完整性
代码自动生成和一致性测试
两种协议描述模型：
有限状态机 FSM
Petri网有限状态机（ 1）
FSM(Finite State Machine)：
系统的状态：有限状态
状态的变迁 transition：一定前提条件下，如果一些输入事件发生，系统采取相应的动作，并且转换到另一个状态
以停等协议为例：
系统状态,（发送者状态、接收者状态、信道状态）
发送者状态：发送 0/1号帧
接收者状态：希望接收 0/1号帧
信道状态：信道上有 0/1/A(ACK)帧 /S(没有 )帧
初始状态为 000，即发送者刚发送 0帧，接收方希望接收 0帧，
0帧正在信道上。
Who 收到的帧 发送帧 递交？ 状态变迁
0 - 帧丢失 xxx?xxs
1 R 合法 0帧 ACK Yes 000?01A
2 S ACK 1帧 01A?111
3 R 合法 1帧 ACK Yes 111?10A
4 S ACK 0帧 - 10A?000
5 R 非法 0帧 ACK No 010?01A
6 R 非法 1帧 ACK No 101?10A
7 S Timeout 0帧 - 0XS?0X0
8 S Timeout 1帧 - 1XS?1X1
有限状态机（ 2）
主变迁路径为 1-2-3-4，信道出错时，偏离主路径，但会回到主路径上来，而且顺序没有改变
丢失 0/1帧比较简单
丢失 ACK复杂一些
ACK没有序号：
半双工信道
（ 00S ） （ 01S ） （ 010 ）
（ 01A ） （ 000 ）
（ 10A ）
（ 101 ） （ 10S ）
（ 111 ）
（ 1 1 S ）
2
1
3 4
5
6
7
8 0
0
8
7
0
0
0
0
有限状态机（ 3）
全双工信道下的停等协议：
系统状态,（发送者状态、接收者状态、正向数据信道状态、
反向信道状态）
正向信道：信道上有 0/1/S（空）帧
反向信道：信道上有 ACK或 S（空）
新的状态转换图：图 3.16
数据帧和确认帧同时出现在信道上时,2个事件必须一起发生，
比如 2+5
状态变迁序列 000S,01SA,010A,111A,11SA,010S，
01SA,111S导致协议失败：经过事件 1,7,2+5,0,4,5,2。发送者发送 1号帧,0号帧都没有被接收者接收，发送方接着发送新的 1号帧。
pkt 0
pkt 0
pkt 1
pkt 0
pkt 1
A CK
Petri网（ 1）
Petri网的四种基本元素：
位置：圆圈，表示可能进入的状态
标记：位置中的小黑点，某个位置中有标记表示系统处于该状态
变迁：直线段表示
带箭头的弧线：
指向某变迁的弧线表示该变迁产生的条件
离开某变迁的弧线表示该变迁产生的结果
变迁的就绪、触发、标记的重新分布
变迁的所有输入位置都有标记时，该变迁就绪
就绪的变迁随时可能被触发
标记移动：从该变迁每条输入弧线的输入位置处取出一个标记，并在该变迁的每条输出弧线的输出位置处放一个标记
Petri网（ 2）
以停等协议为例：
位置给出了发送方、信道或接收方的可能状态
初始状态,A,C,G中有标记，发送 0帧，接收期待 0帧,0帧在信道中。
图中有 1~8,9,10,11变迁,9,10,11对应于表 3.5中的事件 0的三种情况,0帧,ACK,1帧丢失
在初始状态，只有 1,7,9变迁就绪。
如果触发变迁 1，即 0帧到达接收方,C,G中的标志取走,D,F中放入标记,ACG----1?ADF。
变迁可以用代数形式来表示：
变迁 1,CG?DF 变迁 3,EF?DG
变迁 2,AD?BE 变迁 4,BD?AC … 变迁 7,A->AC
错误变迁,ACG—1?ADF—7?ACDF—2?BCEF—5?BDEF—
11?BDF—4?ACF—5?ADF—2?BEF?…
其他协议描述语言（ 1）
FSM,Petri网都是状态变迁模型
高级语言来进行协议描述
SDL：
CCITT提出的描述电信系统的规范和描述语言
有两种语法表示形式：
SDL/GR图形表示：类似程序框图
SDL/PR文字短语表示：定义具体的语法结构
一种扩充的有限状态机，使用辅助存储区来保存那些不必出现于状态之中的信息。
两种辅助操作：判决（条件语句）和任务（简单的处理）
其他协议描述语言（ 2）
ESTELLE,ISO
基于状态变迁模型额 PASCAL的协议形式描述语言
支持层次的分解、模块化和分别编译。
模块包括模块头说明、外部模块说明、模块体
模块体包括说明部分和执行部分，由一系列变迁语句组成
容易通过自动编译，进行协议的实现转换。
LOTOS,ISO
不关心系统内部的状态和动作，只描述其外部可见行为的时序
进程被看成一个黑盒子，事件则是进程之间在交互点处进行的交互，不可再细分
抽象级别较高，难于进行协议的实现转换链路通信规程 (数据链路层协议 )
举例
如何进行定时和同步？
位定时和字符定时
位定时：每个位（比特）的起始时间
字符定时：每个字符的起始时间
异步和同步协议
异步协议
在字符起始处进行同步
发送方和接收方采用近似同一频率的时钟,短时间内时钟的偏移是可以忍受的
同步协议
在帧的起始处同步
维持固定的时钟,时钟信号编码进数据中起止式异步规程（ 1）
基本思想,
1位起始位 +数据 (5-8)+奇偶校验 (选 )+终止位 (1-2)
起止位和终止位进行同步,起始位为低电平,终止位和空闲位为高电平,
数据位中最低有效位在前起始位
5 ~ 8 位数据奇偶校验 终止位起始位
1000101( E )
奇偶校验 终止位起止式异步规程（ 2）
接收端通过检测起始位的下降前沿来决定字符的开始，
并作为后面各位的定时基准
比如采用 16倍于位频率的时钟来采样，如图 3.20
检测到起始位下降前沿时将计数器清零
16倍频时钟的每个脉冲使计数器加 1
计数器到达 8时，位于起始位的中间。判断是否采样值为 0，
如果不是，为干扰。如果是清零
以后每次计数器到 16时进行采样，并将计数器清零。
终止位采样正确，则说明字符接收正确，否则丢弃。
起始位和终止位使得时钟误差不会积累，但效率降低面向字符的同步规程（ 1）
IBM的二进制同步通信协议 BSC/ISO 1745
基本思想：
利用一些特殊定义的字符来标识帧的起始位置，分隔不同的段和控制信息交换的过程。
正文很长时，分割成多个块传递，最后一个块以 ETX结束，其他块以 ETB结束
特殊字符随采用的字符编码集而不同：
ASCII/EBCDIC
S Y N S Y N S O H H e a d e r S TX T e x t ET B / ET X 块校验面向字符的同步规程（ 2）
字符填充：
利用转义字符 DLE来实现数据透明
每个独立的控制字符作为普通的数据字符
在控制字符前面有一个 DLE时才具有特殊意义
若数据段本身出现 DLE，则在前面插入一个 DLE。
接收方接收到连续两个 DLE，则去掉第一个 DLE，
并且作为普通字符看待，不再具有转义意义比如接收到 DLE/DLE/DLE/ETX，表示对方发送
DLE(data) + ETX(control)
面向字节计数的同步规程
DEC的 DDCMP协议
基本思想：
同步字符来进行帧同步,SOH标志帧开始
字节计数来确定帧的结束边界位置。
Flag中一位标识下一帧前是否有同步字符
CRC1对前面标题部分校验
CRC2对数据部分校验
S O H C o u n t F l a g A c k S eq A d d r CRC1 Da t a CRC2
8 14 2 8 8 8 16 16 1 ~ 1 6 3 8 3 B y t e
面向比特同步,HDLC（ 1）
帧格式
HDLC通过一个特定的比特模式,01111110”来标识帧的起始位置
比特填充：
帧中的其他字段中如果出现连续 5个 1，则之后插入一个 0。
当接收时，如果出现连续 5个 1后跟一个 0，则删除 0
帧起始序列 地址 控制 CRC D a t a
8 8 8 16 8
帧结束序列面向比特同步,HDLC（ 2）
HDLC支持三种帧
信息 I帧：携带用户数据，帧的序号在 N(S)中。并且支持捎带确认,N(R)表示之前的所有帧都正确
监控 S帧：单独确认机制。
无编号 U帧：其它链路控制功能
0 N ( S ) P / F N ( R )
3
I 帧
3
1 类型 P / F N ( R ) S 帧
3
0
1 M P / F M U 帧 1
N ( S ),发送顺序号
N ( R ),接收顺序号
M,U 帧功能编码
P / F,P o l l / F i n a l
面向比特同步,HDLC（ 3）
S帧：
Receive ready,positive ACK，准备接收 I帧
Receive not ready,positive ACK，尚未准备好接收
Reject,Negative ACK，回退 N
Selective reject,Negative ACK,选择重传
U帧：下面列出一些典型的 U帧
SABM：设置 ABM模式
DM：断开模式
DISC：终止链路连接
UA：确认 U帧
RSET：重置位,reset N(R),N(S)
面向比特同步,HDLC（ 4）
链路的初始化和断开
数据传输
双向数据传输：捎带确认＋单独确认 RR
一方忙
S A B M
超时
S A B M
UA
UA
DI S C
I /0 /0
I /0 /1
I /1 /1
I /2 /1
I /1 /3
I /3 /2
I /2 /4
I /3 /4
R R /4
I /3 /0
R NR /4
R R /0 /P
R NR /4 /F
R R /0 /P
R R /4 /F
I /4 /0
面向比特同步,HDLC（ 5）
差错恢复：
HDLC协议的变种
X.25的 LAPB协议
ISDN的 LAPD
帧中继的 LAPF协议：没有差错控制超时
I /3 /0
I /4 /0
I /5 /0
R E J /4
I /4 /0
I /5 /0
I /6 /0
I /2 /0
R R /3
I /3 /0
R R /0 /P
R R /3 /F
R R /4
I /3 /0
习题
3.9
3.17
3.20
3.23
3.3 数据链路协议
3.4 协议描述与验证
3.5 链路通信规程举例可靠递交
差错帧：
丢失帧：比如比较长的突发噪声造成帧完全丢失
毁坏帧：帧到达接收者，但是帧的检验和不对
ARQ,Automatic Repeat Request
对收到的帧发送 确认
如果超时并且没有收到确认，则 重传 帧停等协议（ 1）
停等协议（ Stop-and-Wait）
发送者在发送一个帧之后停下来，等待对方确认后继续发送下一帧。如果确认在一段时间后无返回，发送者超时，重传帧。
简单版本 （ 协议有问题 !）Sender
while (1) {
transmit (frame i);
try {
receive (ack);
} catch (timeout) {
continue;
}
i++;
break;
}
Receiver
receive (frame);
transmit (ack);
发送者超时接收者
F r a m e
A C K
发送者超时接收者
F r a m e
A C K
F r a m e
A C K
发送者超时接收者
F r a m e
A C K
F r a m e
A C K
发送者超时接收者
F r a m e
F r a m e
A C K
停等协议（ 2）
帧中包含顺序号（ 1比特）字段，确认也包含顺序号
发送方维护 next_frame_to_send，接收方维护 frame_expected
Sender
while (1) {
transmit (frame next_frame_to_send);
try {
while (1) {
receive (ack n);
if (n != next_frame_to_send)
continue;
break;
}
} catch (timeout) {
continue;
}
next_frame_to_send ++;
break;
}
Receiver
frame_expected = 0;
while (1) {
receive (frame n);
ack (frame n);
if (n != frame_expected)
continue;
break;
}
frame_expected ++;
停等协议（ 3）
考虑停等因素的信道利用率：
信道容量 B bps
帧长 L bit
往返传播延迟 2R
忽略 ACK的开销
卫星信道,B=50kbps,2R=0.5s,L=1kb
U=1000/(1000+25000)=1/26
Mbps/Mb/MB和 Kbps/Kb/KB
为了估算方便，而且在不影响结论的情况下，常常采用 Back-of-
the-envelope calculation：假设每个字节 10个比特,106=220
发送者 接收者
2R
Fr a m e
A C K
L /B
RBL
L
RBL
BLU
22
停等协议（ 4）
捎带确认：大部分的通信是双向的,ACK帧通常可由反向发送的数据帧一起捎带回来。
图 3.11给出了捎带确认的例子,B中给出了由于双方不同步而导致每个数据帧都被重传一次的情形。也可以采用单独发送 ACK而不是捎带确认的方法。
停等协议（ 5）
一个更加全面的分析：考虑 ACK、重传、帧头开销
D为帧中有效数据长度,H为帧头长,L=H+D
ACK长度为 H
T表示等待 ACK的超时间隔
P1和 P2分别表示数据帧和 ACK丢失的概率
每个数据帧需要进行重传的概率：
P = 1–（ 1–P1）（ 1–P2）
数据帧的平均传输次数为
平均重传次数为
1 1 1 1)1(k k PPkP
PPP 111 1
发送者 接收者
2R
F r a m e
A C K
( L /B
超时 T
重传
H /B
)2()(1 BHRB DHTB DHPP
B
D
U
停等协议（ 6）
超时间隔 T必须取得足够大，
即 T≥H/B +2R
第一个因子表示停等的因素，第二个表示出错重传的因素，第三个为帧头的开销
假设信道上每比特的误码率为 E，且各比特相互独立：
这样利用率为：
DH
DPP
HRBDH
DH
B
HR
B
DH
P
P
B
D
U
)1)(1(
2
)2)(1
1
(
21
H
DH
EP
EP
)1(1
)1(1
2
1
)(
)1( 2
BTDH
EDU DH
停等协议（ 7）
假设 H,B,T,E不变，求最佳帧长度 Dopt
当 E?0时有
从而 E很小时：
0'?DU
)1)]1l n ()[(41(2D o p t EBTHBTH
)](/[41)]1l n ()/ [ (41 ~ BTHEEBTH
E
BTHD o p t
管道技术,Pipelining（ 1）
停等协议在开始传输一个数据帧到确认回来这一段时间里必须等待，传播时间远大于传输时间的时候会带来很大的浪费。
管道技术,Pipelining（ 2）
停等协议在开始传输一个数据帧到确认回来这一段时间里必须等待，传播时间远大于传输时间的时候会带来很大的浪费。
Pipelining：
发送方可以连续发送多个数据帧，而不用等待确认帧回来。
发送方和接收方可能要求能够缓存数据帧。发送者最少能够缓存那些已经发送的但是没有确认的帧。
如何进行 pipelined的差错恢复？ GBN/SR
L
BRL 2?
回退 N滑动窗口协议 GBN
GBN：接收方只允许顺序接收，也就是说如果一帧出错，则它后面的 N帧尽管可能正确到达接收方，但被直接丢弃，不发送确认。
发送方将超时，按序重传所有未被确认的帧。
选择重传 SR：若某一帧出错，后面送来的正确帧不是简单地丢弃，
而是缓存在接收缓冲区，当发送方意识到坏帧后，只重传坏帧。
一旦重传的帧收到后，与原先已收到但暂存在缓冲区中的其余帧一起按正确的顺序递交。
GBN滑动窗口（ 1）
发送方维护 3个变量：
SWS(Sending Window Size)：发送窗口大小
LAR(Last Acknowledge received)：最近收到的确认
LFS(Last Frame Sent)：最近发送的帧。
L A R L F S
S W S
已确认帧已发送尚未确认帧可以发送但尚未发送帧不能使用 发送方的滑动窗口
S W SL A RL F S
GBN滑动窗口（ 2）
接收方维护 1个变量：
NFE(Next Frame Expected)：期待接收的下一个帧
接收窗口为 1
发送方处理 3个事件：
高层（网络层）发送数据：如果允许，发送
接收到一个 ACK：移动发送窗口，看是否可以发送新的帧
超时：重传已发送但尚未确认的帧,GBN
接收方：
接收的帧序号为 NFE，则递交，并发送 ACK,更新 NFE
否则出错，丢弃帧，并发送 ACK
GBN滑动窗口（ 3）
停等协议可以看成是一个发送窗口等于 1的滑动窗口协议
假设顺序号字段为 n比特，则顺序号会回绕，发送窗口必须小于所有可能的顺序号的个数，即最大只有 2n-1：
以 3比特顺序号为例
发送者发送 0~7
接收者对 7的捎带确认回来，接收方准备接收 0~7帧
发送者发送新的 0~7帧
发送者又收到一个对 7的捎带确认：？？？ 考虑新帧全部丢失的情况
TCP使用顺序号、累加确认、检验和和超时重传机制，和 GBN非常类似，但是许多 TCP的实现都缓冲那些收到的但失序的 TCP段。
SR滑动窗口（ 1）
GBN在出错时要求重传所有未确认的帧,SR只要求重传那些怀疑出错的帧，单独 ACK那些正确接收的帧，
NAK那些出错的帧。
N ex t S eq N u m
S W S
已确认帧已发送尚未确认帧可以发送但尚未发送帧不能使用 发送方的滑动窗口
S en d _ b a s e
R W S
失序但已确认帧期待但是尚未接收的帧可以接收的帧不能使用 接收方的滑动窗口
R c v _ b a s e
SR滑动窗口（ 2）
发送者：
高层发送数据：如果发送窗口允许，则发送
超时：每个帧都要求有一个定时器
ACK：如果等于 send-base,SW移动
NAK：重传帧
接收者：
出错帧：发送 NAK
帧在 [rcv_base,rcv_base+RWS-1]中，缓冲起来，
并且发送 ACK，如果等于 rcv_base，则移动接收窗口
Sliding Window
发送窗口和接收窗口之间的关系？
RWS>SWS：没有任何意义
停等协议对应于 SWS=RWS=1的情况
GBN对应于 RWS=1的情况
RWS? SWS，当 SWS=RWS时,SWS?2n-1：
接收方移动接收窗口并发送 ACK，该 ACK可能会丢失。
协议描述与验证
自然语言描述协议带来二义性
形式描述模型：
协议的描述更加严密
验证协议的正确性和完整性
代码自动生成和一致性测试
两种协议描述模型：
有限状态机 FSM
Petri网有限状态机
FSM(Finite State Machine)：
系统的状态：有限状态
状态的变迁 transition：一定前提条件下，如果一些输入事件发生，系统采取相应的动作，并且转换到另一个状态
以停等协议为例：
系统状态,（发送者状态、接收者状态、信道状态）
发送者状态：发送 0/1号帧
接收者状态：希望接收 0/1号帧
信道状态：信道上有 0/1/A(ACK)帧 /S(没有 )帧
初始状态为 000，即发送者刚发送 0帧，接收方希望接收 0帧，
0帧正在信道上。
Who 收到的帧 发送帧 递交？ 状态变迁
0 - 帧丢失 xxx?xxs
1 R 合法 0帧 ACK Yes 000?01A
2 S ACK 1帧 01A?111
3 R 合法 1帧 ACK Yes 111?10A
4 S ACK 0帧 - 10A?000
5 R 非法 0帧 ACK No 010?01A
6 R 非法 1帧 ACK No 101?10A
7 S Timeout 0帧 - 0XS?0X0
8 S Timeout 1帧 - 1XS?1X1
有限状态机
主变迁路径为 1-2-3-4，信道出错时，偏离主路径，但会回到主路径上来，而且顺序没有改变
丢失 0/1帧比较简单
丢失 ACK复杂一些
ACK没有序号：
半双工信道
（ 00S ） （ 01S ） （ 010 ）
（ 01A ） （ 000 ）
（ 10A ）
（ 101 ） （ 10S ）
（ 111 ）
（ 1 1 S ）
2
1
3 4
5
6
7
8 0
0
8
7
0
0
0
0
有限状态机
全双工信道下的停等协议：
系统状态,（发送者状态、接收者状态、正向数据信道状态、
反向信道状态）
正向信道：信道上有 0/1/S（空）帧
反向信道：信道上有 ACK或 S（空）
新的状态转换图：图 3.16
数据帧和确认帧同时出现在信道上时,2个事件必须一起发生，
比如 2+5
状态变迁序列 000S,01SA,010A,111A,11SA,010S，
01SA,111S导致协议失败：经过事件 1,7,2+5,0,4,5,2。发送者发送 1号帧,0号帧都没有被接收者接收，发送方接着发送新的 1号帧。
pkt 0
pkt 0
pkt 1
pkt 0
pkt 1
A CK
协议描述与验证
自然语言描述协议带来二义性
形式描述模型：
协议的描述更加严密
验证协议的正确性和完整性
代码自动生成和一致性测试
两种协议描述模型：
有限状态机 FSM
Petri网有限状态机（ 1）
FSM(Finite State Machine)：
系统的状态：有限状态
状态的变迁 transition：一定前提条件下，如果一些输入事件发生，系统采取相应的动作，并且转换到另一个状态
以停等协议为例：
系统状态,（发送者状态、接收者状态、信道状态）
发送者状态：发送 0/1号帧
接收者状态：希望接收 0/1号帧
信道状态：信道上有 0/1/A(ACK)帧 /S(没有 )帧
初始状态为 000，即发送者刚发送 0帧，接收方希望接收 0帧，
0帧正在信道上。
Who 收到的帧 发送帧 递交？ 状态变迁
0 - 帧丢失 xxx?xxs
1 R 合法 0帧 ACK Yes 000?01A
2 S ACK 1帧 01A?111
3 R 合法 1帧 ACK Yes 111?10A
4 S ACK 0帧 - 10A?000
5 R 非法 0帧 ACK No 010?01A
6 R 非法 1帧 ACK No 101?10A
7 S Timeout 0帧 - 0XS?0X0
8 S Timeout 1帧 - 1XS?1X1
有限状态机（ 2）
主变迁路径为 1-2-3-4，信道出错时，偏离主路径，但会回到主路径上来，而且顺序没有改变
丢失 0/1帧比较简单
丢失 ACK复杂一些
ACK没有序号：
半双工信道
（ 00S ） （ 01S ） （ 010 ）
（ 01A ） （ 000 ）
（ 10A ）
（ 101 ） （ 10S ）
（ 111 ）
（ 1 1 S ）
2
1
3 4
5
6
7
8 0
0
8
7
0
0
0
0
有限状态机（ 3）
全双工信道下的停等协议：
系统状态,（发送者状态、接收者状态、正向数据信道状态、
反向信道状态）
正向信道：信道上有 0/1/S（空）帧
反向信道：信道上有 ACK或 S（空）
新的状态转换图：图 3.16
数据帧和确认帧同时出现在信道上时,2个事件必须一起发生，
比如 2+5
状态变迁序列 000S,01SA,010A,111A,11SA,010S，
01SA,111S导致协议失败：经过事件 1,7,2+5,0,4,5,2。发送者发送 1号帧,0号帧都没有被接收者接收，发送方接着发送新的 1号帧。
pkt 0
pkt 0
pkt 1
pkt 0
pkt 1
A CK
Petri网（ 1）
Petri网的四种基本元素：
位置：圆圈，表示可能进入的状态
标记：位置中的小黑点，某个位置中有标记表示系统处于该状态
变迁：直线段表示
带箭头的弧线：
指向某变迁的弧线表示该变迁产生的条件
离开某变迁的弧线表示该变迁产生的结果
变迁的就绪、触发、标记的重新分布
变迁的所有输入位置都有标记时，该变迁就绪
就绪的变迁随时可能被触发
标记移动：从该变迁每条输入弧线的输入位置处取出一个标记，并在该变迁的每条输出弧线的输出位置处放一个标记
Petri网（ 2）
以停等协议为例：
位置给出了发送方、信道或接收方的可能状态
初始状态,A,C,G中有标记，发送 0帧，接收期待 0帧,0帧在信道中。
图中有 1~8,9,10,11变迁,9,10,11对应于表 3.5中的事件 0的三种情况,0帧,ACK,1帧丢失
在初始状态，只有 1,7,9变迁就绪。
如果触发变迁 1，即 0帧到达接收方,C,G中的标志取走,D,F中放入标记,ACG----1?ADF。
变迁可以用代数形式来表示：
变迁 1,CG?DF 变迁 3,EF?DG
变迁 2,AD?BE 变迁 4,BD?AC … 变迁 7,A->AC
错误变迁,ACG—1?ADF—7?ACDF—2?BCEF—5?BDEF—
11?BDF—4?ACF—5?ADF—2?BEF?…
其他协议描述语言（ 1）
FSM,Petri网都是状态变迁模型
高级语言来进行协议描述
SDL：
CCITT提出的描述电信系统的规范和描述语言
有两种语法表示形式：
SDL/GR图形表示：类似程序框图
SDL/PR文字短语表示：定义具体的语法结构
一种扩充的有限状态机，使用辅助存储区来保存那些不必出现于状态之中的信息。
两种辅助操作：判决（条件语句）和任务（简单的处理）
其他协议描述语言（ 2）
ESTELLE,ISO
基于状态变迁模型额 PASCAL的协议形式描述语言
支持层次的分解、模块化和分别编译。
模块包括模块头说明、外部模块说明、模块体
模块体包括说明部分和执行部分，由一系列变迁语句组成
容易通过自动编译，进行协议的实现转换。
LOTOS,ISO
不关心系统内部的状态和动作，只描述其外部可见行为的时序
进程被看成一个黑盒子，事件则是进程之间在交互点处进行的交互，不可再细分
抽象级别较高，难于进行协议的实现转换链路通信规程 (数据链路层协议 )
举例
如何进行定时和同步？
位定时和字符定时
位定时：每个位（比特）的起始时间
字符定时：每个字符的起始时间
异步和同步协议
异步协议
在字符起始处进行同步
发送方和接收方采用近似同一频率的时钟,短时间内时钟的偏移是可以忍受的
同步协议
在帧的起始处同步
维持固定的时钟,时钟信号编码进数据中起止式异步规程（ 1）
基本思想,
1位起始位 +数据 (5-8)+奇偶校验 (选 )+终止位 (1-2)
起止位和终止位进行同步,起始位为低电平,终止位和空闲位为高电平,
数据位中最低有效位在前起始位
5 ~ 8 位数据奇偶校验 终止位起始位
1000101( E )
奇偶校验 终止位起止式异步规程（ 2）
接收端通过检测起始位的下降前沿来决定字符的开始，
并作为后面各位的定时基准
比如采用 16倍于位频率的时钟来采样，如图 3.20
检测到起始位下降前沿时将计数器清零
16倍频时钟的每个脉冲使计数器加 1
计数器到达 8时，位于起始位的中间。判断是否采样值为 0，
如果不是，为干扰。如果是清零
以后每次计数器到 16时进行采样，并将计数器清零。
终止位采样正确，则说明字符接收正确，否则丢弃。
起始位和终止位使得时钟误差不会积累，但效率降低面向字符的同步规程（ 1）
IBM的二进制同步通信协议 BSC/ISO 1745
基本思想：
利用一些特殊定义的字符来标识帧的起始位置，分隔不同的段和控制信息交换的过程。
正文很长时，分割成多个块传递，最后一个块以 ETX结束，其他块以 ETB结束
特殊字符随采用的字符编码集而不同：
ASCII/EBCDIC
S Y N S Y N S O H H e a d e r S TX T e x t ET B / ET X 块校验面向字符的同步规程（ 2）
字符填充：
利用转义字符 DLE来实现数据透明
每个独立的控制字符作为普通的数据字符
在控制字符前面有一个 DLE时才具有特殊意义
若数据段本身出现 DLE，则在前面插入一个 DLE。
接收方接收到连续两个 DLE，则去掉第一个 DLE，
并且作为普通字符看待，不再具有转义意义比如接收到 DLE/DLE/DLE/ETX，表示对方发送
DLE(data) + ETX(control)
面向字节计数的同步规程
DEC的 DDCMP协议
基本思想：
同步字符来进行帧同步,SOH标志帧开始
字节计数来确定帧的结束边界位置。
Flag中一位标识下一帧前是否有同步字符
CRC1对前面标题部分校验
CRC2对数据部分校验
S O H C o u n t F l a g A c k S eq A d d r CRC1 Da t a CRC2
8 14 2 8 8 8 16 16 1 ~ 1 6 3 8 3 B y t e
面向比特同步,HDLC（ 1）
帧格式
HDLC通过一个特定的比特模式,01111110”来标识帧的起始位置
比特填充：
帧中的其他字段中如果出现连续 5个 1，则之后插入一个 0。
当接收时，如果出现连续 5个 1后跟一个 0，则删除 0
帧起始序列 地址 控制 CRC D a t a
8 8 8 16 8
帧结束序列面向比特同步,HDLC（ 2）
HDLC支持三种帧
信息 I帧：携带用户数据，帧的序号在 N(S)中。并且支持捎带确认,N(R)表示之前的所有帧都正确
监控 S帧：单独确认机制。
无编号 U帧：其它链路控制功能
0 N ( S ) P / F N ( R )
3
I 帧
3
1 类型 P / F N ( R ) S 帧
3
0
1 M P / F M U 帧 1
N ( S ),发送顺序号
N ( R ),接收顺序号
M,U 帧功能编码
P / F,P o l l / F i n a l
面向比特同步,HDLC（ 3）
S帧：
Receive ready,positive ACK，准备接收 I帧
Receive not ready,positive ACK，尚未准备好接收
Reject,Negative ACK，回退 N
Selective reject,Negative ACK,选择重传
U帧：下面列出一些典型的 U帧
SABM：设置 ABM模式
DM：断开模式
DISC：终止链路连接
UA：确认 U帧
RSET：重置位,reset N(R),N(S)
面向比特同步,HDLC（ 4）
链路的初始化和断开
数据传输
双向数据传输：捎带确认＋单独确认 RR
一方忙
S A B M
超时
S A B M
UA
UA
DI S C
I /0 /0
I /0 /1
I /1 /1
I /2 /1
I /1 /3
I /3 /2
I /2 /4
I /3 /4
R R /4
I /3 /0
R NR /4
R R /0 /P
R NR /4 /F
R R /0 /P
R R /4 /F
I /4 /0
面向比特同步,HDLC（ 5）
差错恢复：
HDLC协议的变种
X.25的 LAPB协议
ISDN的 LAPD
帧中继的 LAPF协议：没有差错控制超时
I /3 /0
I /4 /0
I /5 /0
R E J /4
I /4 /0
I /5 /0
I /6 /0
I /2 /0
R R /3
I /3 /0
R R /0 /P
R R /3 /F
R R /4
I /3 /0
习题
3.9
3.17
3.20
3.23
