1
Bilingual Course
Network Communications
网络通信
(For Master Students in the Department of Electronic Engineering)
Chapter 7 Data Link Control
Instructor,Dr,Tianshuang Qiu
School of the Electronic and Information Engineering
Fall of 2004
2
Background
在分层协议（特别是 OSI协议）体系中，包含一个 数据链路层。
为什么需要数据链路层
– Because of the possibility of transmission errors,and because the
receiver of data may need to regulate the rate at which data arrives,
It is necessary to impose（施加） a layer of control in each
communicating device that provides functions such as flow control,
error detection,and error control,This layer of control is know as a
data link control protocol.
数据链路层：实现实体之间链路的建立，维护和拆除，
形成可用的连接。
数据链路：在使用数据链路控制协议时，系统之间的传输媒体称为数据链路。
3
数据链路控制的主要功能
线路规程
– 解决现在时刻该谁发送的问题
流量控制
– 负责调整某个时间间隙中可以发送多少数据。使接收方能够调整来自发送方的数据流，以防止接收方出现溢出。
差错控制
– 检测和纠正传输错误。
– 差错检测的实现：依靠差错检测码的计算实现，它是传输比特的一个函数。差错检测码通常附加在传输的数据位之后。接收方根据接收到的比特计算出差错检测码，然后将其与收到的差错检测码比较，
以检查是否有差错。
– 差错控制的实现：通过重传损坏帧来实现。
4
数据链路控制的要求和目标
Frame synchronization,Data are sent in blocks called frames,The beginning
and end of each frame must be recognizable,
Flow control,The sending station must not send frames at a rate faster than
the receiving station can absorb them.
Error control,Bit errors introduced by the transmission system should be
corrected.
Addressing,On a multipoint line,such as a local area network (LAN),the
identity of the two stations involved in a transmission must be specified.
Control and data on same link,It is usually not desirable to have a
physically separate communications path for control information,Accordingly,
the receiver must be able to distinguish control information from the data
being transmitted.
Link management,The initiation,maintenance and termination of a sustained
（持续的） data exchange requires a fair amount of coordination and
cooperation among stations,Procedures for the management of this exchange
are required.
5
§ 7-1 线路规程
三种方式
1,询问 /应答模式（ Enquiry/ Acknowledge）
- 常在专用链路中使用；
- 负责协调哪个设备可以开始传输
- 工作方式：
（ 1）启动方发一个询问帧（ ENQ），问接收方是否可以接收数据；
（ 2）若接收方准备好，回答一个确认帧（ ACK），若未准备好，
则回答一个否定帧（ NAK）；
（ 3）若未收到回答（等待一定时间），则再发一次（一般发三次）；
（ 4）若回答为否定，或三次都无回答，则断开连接。在另一时刻再重新开始；
（ 5）若回答肯定，启动方就可以随时发送数据了；
（ 6）发完时，发方传一个结束帧（ EOT）
6
询问 /应答方式的流程图
ENQ
ENQ=Enquiry
ACQ
ACQ=Acknowledge
数据应答数据应答传输结束时间时间
A站 B站
7
2,轮询 /选择模式
- 这种模式用于多点设备结构，但其中某一个为主设备，其余的为从设备。
- 主设备：控制链路，总是会话的发起者；
- 从设备：遵从住设备的指令；
- 工作方式：
（ 1）选择方式 —主设备有数据发送，告知从设备准备好接收；
（ 2）轮询方式 —主设备希望接收数据，询问从设备有无数据待发。
- 地址：
· 链路上每个设备有自己的名字或地址；
· 每次传输，数据帧中会建立地址部分（称为地址域或称为报头）
A B C
主设备
8
（ 1） 选择模式当主设备有数据要发送时：
- 通知从设备准备好接收；
- 等待从设备的回答；
- 发送数据之前，主设备产生一个选择祯（ SEL），其中包含一个地址域，填入要发送的从设备的地址；
- 当数据沿着链路发送时，任何一个从设备均有可能接收到此数据。各个从设备都校验数据中的地址域；
- 若与自己的一致，则读入；
- 若不一致，则放弃
A B C
主设备
SEL
ACK
数据应答时间时间选择C
9
（ 2） 轮询模式主设备请求从设备发送数据。
A B C
主设备时间时间轮询否定应答
ENQ
数据应答帧
ENQ
否定应答
10
§ 7-2 流量控制
为什么要进行流量控制
– Flow control is a technique for assuring that a transmitting entity
does not overwhelm a receiving entity with data,The receiving
entity typically allocates a data buffer of some maximum length for
a transfer,When data are received,the receiver must do a certain
amount of processing before passing the data to the higher level
software,In the absence of flow control,the receiver’s buffer may
fill up and overflow while it is processing old data.
流量控制的方法
（ 1）停止等待流量控制（ Stop-and-Wait Flow Control）
（ 2）滑动窗流量控制（ Sliding Window Flow Control）
11
（ 1） Stop-and-Wait Flow Control
– 工作方式
发送方：传一个帧；
接收方：收到后，发回一个确认，表示愿意接收下一帧；
发送方：等待，直到收到确认信息；
若接收方不发确认，则简单中止传输。
– 帧的长度 不能太长。 A source need to break up a large block of
data into smaller blocks and transmit the data in many frames.
– 原因,
(1) The buffer size of the receiver may be limited（缓冲器容量）,
(2) The longer the transmission,the more likely that there will be an
error,necessitating retransmission of the entire frame,With smaller
frames,errors are detected sooner,and a smaller amount of data
needs to be retransmitted.（出错重传）
(3) On a shared medium,such as a LAN,it is usually desirable not to
permit one station to occupy the medium for an extended period,
thus causing long delays at the other sending stations.（共享媒体）
12
Bit Length and Frame Length
Bit Length,the bit length of a link is the number of bits present on the
link when a stream of bits fully occupies the link,即当数据流占满链路时，给定的链路上能排布多少个 bit，可如下计算：
Bit length=R*d/V (bit)
Where R is the data rate in bps;
d is the distance of the link in meters;
V is the velocity of propagation in m/s
Frame Length,一帧数据的 bit数。
Transmission Time,1（传输时间； 发送时间 ）,The time it takes for
a station to transmit a frame.
Propagation Time,a（传播时间）,The time it takes for a bit to travel
from sender to receiver,
13
The Inefficiency of Stop-and Wait (Figure 7.2)
14
Stop-and-Wait方式的缺点
In the situation where the bit length (a) of the link is greater than the
frame length (1),series inefficiencies result,（参见图 7.2,P.197）
The transmission time （ 发送时间 ） is normalized to 1,and the
propagation delay （ 传播时间 ） is expressed as the variable a,
When a<1,the propagation time is less than the transmission time,
Then the frame is sufficiently long that the first bits of the frame have
arrived at the destination before the source has completed the
transmission of the frame.
When a>1,the propagation time is greater than the transmission time,
In this case,the sender completes transmission of the entire frame
before the leading bits of that frame arrive at the receiver,
In Figure 7.2,if a>1,the line is always underutilized （没有充分利用） ; even if a<1,the line is also inefficiently utilized（利用率也不高）,In essence,for very high data rates,for very long distances
between sender and receiver,stop-and-wait flow control provide
inefficient line utilization.
15
（ 2） Sliding Window Flow Control
停止等待的缺点
– The essence of the problem described so far is that only one frame
at a time can be in transit,In situations where the bit length of the
link is greater than the frame length (a>1),serious inefficiencies
result,
解决的思路
– Efficiency can be greatly improved by allowing multiple frames to
be in transit at the same time.
滑动窗方法
– 假定 A,B两个站,A为发送站,B为接收站，全双工方式；
– A,B站各维护一个 长度为 W的 buffer（窗口）,即 A可连续发
W帧,B可连续收 W帧，其间可以不应答；
– B对 A发送的多帧数据进行一次应答，而不是每一帧应答一次；
16
操作的一般描述
连发多帧,发送方收到应答（ ACK）之前，可以发送多帧，以便充分利用链路的能力；
窗口,发送方和接收方分别建立缓冲区，称为窗口（ window），
用于存储帧数据；
窗口滑动,窗口在缓冲区内移动，窗口内包含了待发的若干帧；
编号,需对待发的帧编号，以 M（ =2^k）为模（ 0,1,…,M -1,0,1,…)
编号 ;
若 M=8，则窗口的大小取为 M-1=7。
17
具体说明（略）
– B receives frames 2,3,and 4 at one time.
– A maintains a list of sequence numbers that it is allowed to send.
– B maintains a list of sequence number that it is prepared to receive,
– Each of these lists can be thought of as a window of frames.
– The operation is referred to as sliding-window flow control.
– The size of the window,if k bits is used to express the number of the
frames,the window size is 2^k,The sequence number is 0 through 2^k-1,
对 图 7.3(see next slide)的说明
– It assumes the use of 3 bit sequence number,So that frames are numbered
sequentially from 0 through 7,and then the same numbers are reused for
subsequent frames,The shaded rectangle indicates the frames that may be
sent; in this figure,the sender may transmit 5 frames,beginning with
frame 0,Each time a frame is sent,the shaded window shrinks; each time
an acknowledgement is received,the shaded window grows,Frames
between the vertical bar and the shaded window have been sent but not yet
acknowledged,As we shall see,the sender must buffer these frames in
case they need to be retransmitted.
18
Sliding Window Depiction (Figure 7.3)
19
发送窗口和接收窗口移动规则
发送窗口
– 在发送开始时,发送窗口中有 M-1帧数据；
– 每发送一帧，发送窗的左端缩进一帧（向右）；
– 一旦有 ACK从接收方来，窗口右端向右扩张，扩展的帧数为所收到的 ACK确认收到的帧数
接收窗口
– 随着新数据的到来，接收窗口的大小不断缩小（表示在发出
ACK之前，所能接收新数据的帧数的减小）；
– 接收窗口的左端：当接收一帧时，接收窗口的左端向右移动一 帧；
– 接收窗口的右端：每发送一个 ACK（有时又记为 RR,Receive
response），接收窗口的右端向右扩张若干帧，扩张的帧数为上一次 ACK帧的编号与当前 ACK帧编号之差值。
20
Example 1（ 发送窗 ）
例 1
– 发送开始时,发送窗中包含 7帧；
– 发送方已经发送 0—4帧，未收到 ACK（或 RR）应答。此时，发送窗口的左端需向右收缩 5帧；
– 发送方收到 RR5，表示接收方已经收到 0—4帧，希望接收第 5帧，则发送窗口右端向右扩张 5帧。
01 2 3 4 5 6 70 1 2 3
发送窗
01 2 3 4 5 6 70 1 2 3
发送窗
4 5
21
Example 2（ 接收窗 ）
例 2
– 发送开始时（前），接收窗中包含 7帧（ 0--7），表示接收窗能够接收连续的 7帧；
– 接收方收到 2帧（第 0，第 1帧），暂时未发应答（ ACK或 RR），则接收窗口左端需向右收缩 2帧；
– 在接收 2帧之后，接收方发出 ACK 2（或 RR 2），表示已经收到第 0和第 1帧，并希望继续接收第 2帧。此时，接收窗的右端向右扩张 2帧。
01 2 3 4 5 6 70 1 2 3
01 2 3 4 5 6 70 1 2 3 4 5
接收窗
22
Example of a Sliding Window Protocol (Figure7.4)
23
双向传输与捎带
双向传输
– 双向传输表示全双工的传输，即通信的双方均有数据要发送且接收；
– 这样，双方均需维护 2张表，即双方均需有 2个窗口（发送，
接收）；
– 双方均需对收到对方的数据进行确认
捎带技术
– 若数据中含有存放确认序号的字段，且在一帧中同时发送，则称为捎带，即数据中含有控制信息。
24
§ 7-3 Error Detection
与传输帧的差错有关的几个概率
– Pb（比特差错率）,Probability of a single bit error,known as the bit
error rate (BER);
– P1（无错帧概率）,Probability that a frame arrives with no bit errors;
– P2（未检测到的有错帧概率）,Probability that a frame arrives with one
or more undetected bit errors;
– P3（检测到的有错概率）,Probability that a frame arrives with one or
more detected bit errors,but no undetected bit errors
几个概率之间的联系
– 若没有检测差错的手段，则有
where F is the number of bits per frame.
25
An Example
例
– ISDN 64 kbps 信道,一分钟内至少有 90%的时间里 满足 Pb<10^(-6)。
要求：每天最多允许出现一个未被检测到的有比特差错的帧，已知帧长度为 1000 bit。
求：实际的 P1=？,P2=？
解：根据给定的条件，该信道一天能传输的帧数为：
M=64*1000*3600*24/1000=5.529*10^6 帧要求的未检测到的有错帧概率为,P2=1/M=0.18*10^(-6)
根据给定条件,Pb=10^(-6)，且 F=1000，则 实际的 无错帧概率为
P1=（ 1-Pb)^F=（ 1-10^-6)^1000=0.999
实际的 未检测到的有错帧概率为,P2=1-P1=10^(-3)
结论,P2>>P2，即实际的 P2比要求的 P2高了 3个数量级，不满足要求。
26
Error Detection,Why
为什么要进行差错检测
– This is the kind of result that motivates the use of error-detection
techniques,All of these techniques operate on the following
principle (Figure 7.5,E6),For a given frame of bits,additional
bits that constitute an error detecting code are added by the
transmitter,This code is calculated as a function and compares the
two results,A detected error occurs if and only if there is a
mismatch,Thus P3 is the probability that a frame contains errors
and that the error-detection scheme will detect that fact,P2 is
known as the residual error rate and is the probability that an error
will be undetected despite the use of an error-detection scheme.
P3（检测到的有错概率）
P2（未检测到的有错帧概率）
27
Error Detection,How (Figure 7.5,E6)
28
Parity Check
方法
– To append a parity bit to the end of a block of data,A typical
example is character transmission,in which a parity bit is attached
to each 7-bit ASCII character,
– The value of the bit is selected so that the character has an even
number of 1s (even parity) or an odd number of 1s,
例：
假定要传输的 ASCII字符为 G，其 ASCII编码为 1110001（ 71H）。
对于奇校验,G的传输码为,1110001 1,1的个数为奇数对于偶校验,G的传输码为,1110001 0,1的个数为偶数在接收端，若任意一个比特出错（ 1?0或 0?1），会引起传输码
1的个数的变化，则可以检测出该字符出错。若有偶数个 bit出错，则不能检测。
29
Cyclic Redundancy Check (CRC)
CRC（循环冗余检测）的概念
– One of the most common,and one of the most powerful,error-detecting
codes is the cyclic redundancy check (CRC),which can be described as
follows,Given a k-bit block of bits,or message（报文）,the transmitter
generates an n-bit sequence,known as a frame check sequence (FCS),so
that the resulting frame,consisting of k+n bits,is exactly divisible by
some predetermined number,The receiver then divides the incoming
frame by that number and,if there is no remainder,assumes there was no
error.
CRC的方法
30
CRC校验
（ 1）模 2运算
（ 2）定义
T=要传输的（ k+n） bit 帧,n<k
M=k bit报文
F=n bit FCS（帧校验序列）
P=（ n+1） bit 的模式（预定的除数）
110101
10011
10011 1010
11 0101
10011 1111
31
（ 3）校验原理给定一个 k bit报文，发送器生成 n bit序列，称为帧校验序列
（ FCS）。这个 bit序列要使最后得到的 (k+n) bit的帧可以被一些预定的数值整除。于是接收器采用同样的数值去除接收到的帧时，
若无余数，则无差错。若有余数，则有差错。
要传输的报文为 M；加上 CRC的传输数据为 T；
在校验时，希望 T/P的余数为 0；
实际上,T=2^n M+F;
设,(2^n M)/P=Q+R/P,其中,Q为商,R/P为余数；
若实际传输的数据为,T=2^n M+R （即取 R=F）
则：在接收端，
T/P= (2^n M+R)/P=Q+R/P+R/P
按照模 2加的方法,R/P+R/P=0，
故：余数为 0。
32
（ 3）例已知,M=1010001101 （ 10bit报文）
方案,P=110101 （ 6bit模式）
R为 5bit （ FCS序列，由计算得）
2^5M=101000110100000
2^5M/P=1101010110+01110/110101 （ Q+R/P）
T=2^5M+R=101000110101110 （真正传输的）
在接收端,T/P=1101010110 （余数为 0）
33
CRC by Polynomials （自行阅读）
This method expresses all values as polynomials in a dummy（哑的）
variable X,with binary coefficients,The coefficients correspond to the
bits in binary number,
For M=110011,we have
For P=11001,we have
Arithmetic operation are again modulo 2.
CRC的两个主要公式
34
CRC by Polynomials（ Cont’d）
CRC校验可以检测以下各种差错
– All single bit errors;
– All double bit errors,as long as P(X) has at least three 1s;
– Any odd number of errors,as long as P(X) contains a factor (X+1);
– Any burst error for which the length of the burst is less than the length of
the divisor polynomial; that is,less than or equal to the length of the FCS;
– Most larger burst errors
常用的 P(X)
– CRC-12
– CRC-16
– CRC-CCITT
– CRC-32
35
CRC by Digital Logic（自行阅读）
CRC校验可以用包含异或门和移位寄存器的数字电路实现；
电路如图 7.6（ P.206）
– The register contains n bits,equal to the length of the FCS.
– There are up to n exclusive-OR gates.
– The presence or absence of a gate corresponds to the presence or absence
of a term in the divisor polynomial,P(X),excluding the X^n term.
36
用移位寄存器产生FS
C
码
37
接收端的差错检测
At the receiver:
– The same logic is used,As each bit of M arrives,it is inserted into
the shift register,If there have been no errors,the shift register
should contain the bit pattern for R at the conclusion of M,the
transmitted bits of R now begin to arrive,and the effect is to zero
out the register so that,at the conclusion of reception,the register
contains all 0s.
– 接收方所使用的逻辑相同。 M中的各个 bit在到达时被输入到移位寄存器，若无差错，则寄存器中应当含有由 M计算而得出的
R的模式。这时传输的 R序列开始到达，并且使寄存器全部清零。因此，在接收之后，寄存器中的值全部为 0。
– 反之，若有差错，则计算得不到 R模式，当 R序列到达并进行异或运算时，不能是寄存器清零，从而表明出现差错。
38
General CRC Architecture
39
§ 7-4 Error Control
Concept
– Error control refers to mechanism to detect and correct errors that
occur in the transmission of frames,As before,data are sent as a
sequence of frames; frames arrive in the same order in which they
are sent; and each transmitted frame suffers an arbitrary and
potentially variable amount of delay before reception,In addition,
we admit the possibility of two types of errors:
Lost frame（丢失帧）,frame fails to arrive at the other side,
For example,a noise burst may damage a frame to the extent
that the receiver is not aware that a frame that a frame has been
transmitted.
Damaged frame（损坏帧）,A recognizable frame does arrive,
but some of the bits are in error.
40
差错控制的常用方法
Error detection（差错检测）
– As discussed in the preceding section;
Positive acknowledgement（肯定确认）
– The destination returns a positive acknowledgement to successfully
received,error-free frames;
Retransmission after timeout（超时后重传）
– The source retransmits a frame that has not been acknowledged after a
predetermined amount of time;
Negative acknowledgement and retransmission（否认与重传）
– The destination returns a negative acknowledgement to frame in which an
error is detected,The source retransmits such frame.
上述方法均可以称为 自动重发请求 ARQ。
41
三种 ARQ标准
Stop-and-wait（停止等待） ARQ（ Automatic Repeat reQuest ）
– 停止等待 ARQ的基础是前面介绍过的停止等待流量控制技术。源站发送一个帧 之后，必须等待一个确认（ ACK），在目的站点的确认返回源站之前，源站不能发送其他数据帧。
Go-back-N（返回 N帧） ARQ
– 是最常用的基于滑动窗口流量控制的差错控制形式。尚未被确认的帧的最大数目取决于窗口的大小。正常情况下，接收站发肯定确认（ RR,Receive
Ready），若检测到差错，则接收站发一个否认（ REJ=拒绝），并将该帧及以后各帧丢弃，直到差错帧被正确接收到。源站收到 REJ后，重传出错帧及以后各帧。
Selective-reject（选择拒绝） ARQ
– 对于选择拒绝 ARQ，被重传的只有接收到的否认的帧或超时的帧。
否认被称为 SREJ。
42
停止等待 ARQ
到达站点的帧已经损坏
– 接收方
由差错检测技术检测；
处理：简单丢弃
– 发送方
设置计时器
若超时则重发
,确认”信息损坏
– 发送的帧被接收方正确接收，并返回确认信息，但是该确认信息损坏。
– 发方的计时器超时，则重发。
– 为避免接收方重复接收，需对发送的帧编号
优点：简单易行
缺点：效率低
43
返回 N ARQ
Consider that station A is sending frames to station B,After each
transmission,A sets an acknowledgement timer for the frame just
transmitted,Suppose that B has previously successfully received frame
(i-1) and A has just transmitted frame i,The go-back-N technique
takes into account the following contingencies（作出反应）,
Damaged frame,If the received frame is invalid,B discards the frame
and takes no further action as a result of that frame,There are two
subcases:
– Within a reasonable period of time,A subsequently sends frame (i+1),B
receives frame (i+1) out of order and sends a REJ i,A must retransmit
frame i and all subsequent frames.
– A does not soon send additional frame,B receives nothing and returns
neither an RR nor a REJ,When A’s timer expires,it transmits an RR
frame that includes a bit known as the P bit,which is set to 1,B interprets
the RR frame with a P bit of 1 as a command that must be acknowledged
by sending an RR,indicating the next frame that it expects,which is frame
i,When A receives the RR,it retransmits frame i.
44
Damaged RR
– B receives frame i and send RR(i+1),which is lost in transit,Because
acknowledgements are cumulative,it may be that A will receive a
subsequent RR to a subsequent frame and that it will arrive before the
timer associated with frame i expires,
– If A’s timer expires,it transmits an RR command,It sets another timer,
called the P-bit timer,If B fails to respond to the RR command,or if its
response is damaged,then A’s P-bit timer will expire,At this point,A
will try again by issuing a new RR command and restarting the P-bit timer,
This procedure is tried for a number of iterations,If A fails to obtain an
acknowledgement,after some maximum number of attempts,it initiates a
reset procedure.
Damaged REJ
– If a REJ is lost,this is equivalent to the second case of ―Damaged frame‖.
45
返回N
AR
Q
与选择拒绝ARQ
46
选择拒绝 ARQ
特点
– 被重传的只有接收到否认的帧和超时的帧；
– 由于重传的帧减少到最少，故效率高；
– 但是系统的复杂性较高：
– 接收方必须维护一个足够大的缓存，以保存 SREJ后收到的帧，
直到有差错的帧被重传；
– 接收方需具有按照正确顺序插入后到的帧的功能；
– 发送方需要具有发送失序帧的能力；
– 选择拒绝 ARQ的应用例见 Figure 7.9
47
§ 7-5 High-Level Data Link Control
(HDLC)
简介
– The most important data link control protocol is HDLC (ISO 3009,ISO
4335),Not only is HDLC widely used,but it is the basis for many other
important data link control protocols,which uses the same or similar
formats and the same mechanisms as employed in HDLC,
1,HDLC协议
（ 1）规定三种类型的站点
Primary station,负责控制链路操作，有主站发出的帧称为 命令 ；
Secondary station,在主站的控制下操作，由从站发出的帧称为 响应 ；
Combined station,混合了主站和从站的特点（发出的帧可以是命令，
也可以是响应）
48
（ 2）使用两种链路配置
Unbalanced configuration,由一个主站及一个或多个从站组成，支持全双工和半双工传输；
Balanced configuration,由两个混合站组成，支持全双工和半双工传输；
（ 3）支持三种数据链路模式
Normal response mode (NRM),使用主从关系非平衡配置，用于多点线路，也可以用于点对点链路。主站能够初始化从站的数据传输，而从站只能通过数据传输来响应主站的命令；
Asynchronous balanced mode (ABM),使用平衡配置，两个混合站都能够初始化数据传输，不需要得到对方混合站的许可；
Asynchronous response mode (ARM),使用非平衡配置。从站能够初始化传输。但主站仍对线路全权负责，包括初始化、差错恢复和联络的逻辑断开。
49
2,帧结构
（ 1）标志字段标志,01111110
注意：与数据 01111110
的区别，若出现与标志相同的数据，按如下方法处理。
50
比特填充
在发送端：若在起始标志和结束标志之间出现连续 5个 1，则发送端插入一个 0，称为 bit填充。
在接收端：若出现任意一个连续的 5个 1，则检查第 6个 bit:
– 若 bit6=1，且 bit7=0，则为标志段；
– 若 bit6=1，且 bit7=1，则此时处于由发方指明的丢弃状态；
– 若 bit6=0,则为数据
举例
– 原始数据为,0111111011111111111101111110111111001111110
– 比特填充后,01111110111110111110110111110101111101001111110
– 恢复的数据,0111111011111111111101111110111111001111110
51
（ 2）地址字段
· 地址字段标识传输该帧或准备接收该帧的从站。实际上，点对点传输不需要这个字段，但是为了统一，所有帧均包含这个字段。
· 地址字段常为 8bit，但是可以使用扩展格式，这时地址的实际长度是
7bit的倍数（见图 7.10）。
· 地址字段的最后一个八位组的最低位为 0。
· 若地址为全 1，则表示所有站点的地址，实际上是广播方式。
（ 3）控制字段
· HDLC定义 3种帧，各有不同的控制字段
- 信息帧（ I帧）,携带向用户传输的数据，此外还捎带流量控制和差错控制的数据；
- 监控帧（ S帧）,在未使用捎带技术时提供了 ARQ机制；
- 无编号帧（ U帧）,提供增补的链路控制功能。
- 控制字段中的,轮询 /结束（ P/F）,bit：
- 在命令帧中，为 P比特，若设置为 1，则向对等实体请求（轮询）响应帧；
- 在响应帧中，为 F比特，若设置为 1，则表示发送的这个响应是一个请求命令的结果
52
（ 4）信息字段
· 只有 I帧和 U帧才具有信息字段；
· 可以包含任意的比特序列，但必须由整数倍的八位组组成；
· 信息字段的长度不固定，可以大到系统设定的最大值。
（ 5）帧检验序列字段
· 帧检验序列（ FSC）是一个差错检测码，由帧中除了标志字段以外的其它位计算得到；
· 这个检测码通常是 16bit的 CRC-CCITT码；
· 也可以选择使用 CRC-32的 32bit的 FCS。
3,操作
（ 1）内容包含在两个站点之间交换 I,S,U帧
（ 2）三个阶段
· 初始化链路；
· 交换数据和控制信息；
· 一方发出信号来中止操作
53
表 7.1 HDLC命令和响应
54
Initialization
Initialization may be requested by either side by issuing one setmode
command,This command serves three purposes:
– It signals（通知） the other side that initialization is requested.
– It specifies which of the three modes (NRM,ABM,ARM) is requested.
– It specifies whether 3- or 7- bit sequence numbers are to be used,
If the other side accepts this request,then the HDLC module on that
end transmits an unnumbered acknowledged (UA，无编号确认 )
frame back to the initiating side,
If the request is rejected,then a disconnected mode (DM) frame is sent.
55
Data Transfer
当初始化一个请求并被接受后，就会建立起一个逻辑连接。双方都可以通过 I帧开始发送用户信息，帧的序号从 0开始。 I帧的 N(S)和 N(R)是用于支持流控制和差错控制的序号。 HDLC模块在发送 I帧序列时，会按顺序对它们编号，并将序号放在 N(S)中，这些编号以 8或 128为模，取决于使用的是 3bit序号还是 7bit序号。 N(R)是对接收到的 I帧的确认。有了 N(R)，
HDLC模块就能够指出自己希望接收的下一个 I帧的序号。
S帧同样也用于流控制和差错控制。其中，接收就绪帧（ RR）通过指出希望接收到的下一帧来确认接收到的最后一个 I帧。在缺少能够捎带确认的反向用户数据流（ I帧）时，就需要使用 RR帧。接收未准备就绪
（ Received-not-Ready,RNR）帧和 RR帧一样，都可以用于对 I帧的确认，
但它同时还要求对等实体暂停 I帧的传输。当发出 RNR的实体再次准备就绪之后，会发送一个 RR。 REJ对返回 N ARQ进行初始化。它指出最后一个接收到的 I帧已经被拒绝，并要求重发以 N(R)序号为首的所有后续 I帧。
选择拒绝（ SREJ）用于对某一个帧的重发请求。
56
Disconnect
Either HDLC module can initiate a disconnect,either on its own
initiative if there is some sort of fault,or at the request of its higher-
layer user,HDLC issues a disconnect by sending a disconnect (DISC)
frame,The remote entity must accept the disconnect by replying with a
UA and informing its layer 3 user that the connection has been
terminated,Any outstanding unacknowledged（未被确认的） I-
frame may be lost,and their recovery is the responsibility of higher
layers.
57
Examples
58
说明图 7.12（ c）表示忙状态其原因可能为 HDLC实体处理 I帧的速度无法跟上帧到达的速度。这时，
接收缓存会填满，则接收端不得不使用 RNR命令来阻止进入缓存的 I
帧流。在本例中,A 发出一个 RNR，又一个它要求 B停止传输 I帧。
收到 RNR的站点，通常会每隔一段时间就向忙站点发出询问，这是通过发送一个 P bit为 1的 RR来实现的，它请求对方用 RR或者 RNR来响应。当忙状态清除后,A 返回一个 RR，这时来自的 B帧可以继续传输。
59
Examples (Cont’d)
60
§ 7-6 Other Data Link Control Protocols
1,LAPB (Link Access Procedure,Balanced)
作为 X.25分组交换网接口标准的一部分，是 HDLC的子集，只提供 ABM下的 HDLC，帧格式与 HDLC一致，适用于节点之间的点对点链接。
2,LAPD (Link Access Procedure,D-Channel)
是 ISDN规约集的一部分，提供 D信道（用户与 ISDN借口的逻辑信道）的数据链路控制。 LAPD与 HDLC的区别,LAPD中限于 ABM；永远使用 7bit序号；
FSC总是 16bit的 CRC；地址字断段 16bit等。
3,逻辑链路控制（ LLC）
属于 IEEE802协议族中有关局域网的控制操作标准的一部分。 LLC与 HDLC
的区别：格式不同（参见图 7.13），链路控制功能被分为 2层，媒体接入层
（ MAC，下）和 LLC层（上）。
4,帧中继（ Frame Relay）
是一种数据链路控制设施，用于高速分组交换网，提供流水作业能力。
5,异步传输模式（ ATM,Asynchronous Transfer Mode）
ATM的设计目标是提供流水化数据传送能力。 ATM不是基于 HDLC的，又称为信元中继。信元的长度固定为 53个字节。
61
Homework of Chapter 7
7.4,7.11（ This Time,October 18）
7.17,7.24 （ Next Time,October 25）
Due by Next Monday
62
End of This Chapter
Bilingual Course
Network Communications
网络通信
(For Master Students in the Department of Electronic Engineering)
Chapter 7 Data Link Control
Instructor,Dr,Tianshuang Qiu
School of the Electronic and Information Engineering
Fall of 2004
2
Background
在分层协议（特别是 OSI协议）体系中，包含一个 数据链路层。
为什么需要数据链路层
– Because of the possibility of transmission errors,and because the
receiver of data may need to regulate the rate at which data arrives,
It is necessary to impose（施加） a layer of control in each
communicating device that provides functions such as flow control,
error detection,and error control,This layer of control is know as a
data link control protocol.
数据链路层：实现实体之间链路的建立，维护和拆除，
形成可用的连接。
数据链路：在使用数据链路控制协议时，系统之间的传输媒体称为数据链路。
3
数据链路控制的主要功能
线路规程
– 解决现在时刻该谁发送的问题
流量控制
– 负责调整某个时间间隙中可以发送多少数据。使接收方能够调整来自发送方的数据流，以防止接收方出现溢出。
差错控制
– 检测和纠正传输错误。
– 差错检测的实现：依靠差错检测码的计算实现，它是传输比特的一个函数。差错检测码通常附加在传输的数据位之后。接收方根据接收到的比特计算出差错检测码，然后将其与收到的差错检测码比较，
以检查是否有差错。
– 差错控制的实现：通过重传损坏帧来实现。
4
数据链路控制的要求和目标
Frame synchronization,Data are sent in blocks called frames,The beginning
and end of each frame must be recognizable,
Flow control,The sending station must not send frames at a rate faster than
the receiving station can absorb them.
Error control,Bit errors introduced by the transmission system should be
corrected.
Addressing,On a multipoint line,such as a local area network (LAN),the
identity of the two stations involved in a transmission must be specified.
Control and data on same link,It is usually not desirable to have a
physically separate communications path for control information,Accordingly,
the receiver must be able to distinguish control information from the data
being transmitted.
Link management,The initiation,maintenance and termination of a sustained
（持续的） data exchange requires a fair amount of coordination and
cooperation among stations,Procedures for the management of this exchange
are required.
5
§ 7-1 线路规程
三种方式
1,询问 /应答模式（ Enquiry/ Acknowledge）
- 常在专用链路中使用；
- 负责协调哪个设备可以开始传输
- 工作方式：
（ 1）启动方发一个询问帧（ ENQ），问接收方是否可以接收数据；
（ 2）若接收方准备好，回答一个确认帧（ ACK），若未准备好，
则回答一个否定帧（ NAK）；
（ 3）若未收到回答（等待一定时间），则再发一次（一般发三次）；
（ 4）若回答为否定，或三次都无回答，则断开连接。在另一时刻再重新开始；
（ 5）若回答肯定，启动方就可以随时发送数据了；
（ 6）发完时，发方传一个结束帧（ EOT）
6
询问 /应答方式的流程图
ENQ
ENQ=Enquiry
ACQ
ACQ=Acknowledge
数据应答数据应答传输结束时间时间
A站 B站
7
2,轮询 /选择模式
- 这种模式用于多点设备结构，但其中某一个为主设备，其余的为从设备。
- 主设备：控制链路，总是会话的发起者；
- 从设备：遵从住设备的指令；
- 工作方式：
（ 1）选择方式 —主设备有数据发送，告知从设备准备好接收；
（ 2）轮询方式 —主设备希望接收数据，询问从设备有无数据待发。
- 地址：
· 链路上每个设备有自己的名字或地址；
· 每次传输，数据帧中会建立地址部分（称为地址域或称为报头）
A B C
主设备
8
（ 1） 选择模式当主设备有数据要发送时：
- 通知从设备准备好接收；
- 等待从设备的回答；
- 发送数据之前，主设备产生一个选择祯（ SEL），其中包含一个地址域，填入要发送的从设备的地址；
- 当数据沿着链路发送时，任何一个从设备均有可能接收到此数据。各个从设备都校验数据中的地址域；
- 若与自己的一致，则读入；
- 若不一致，则放弃
A B C
主设备
SEL
ACK
数据应答时间时间选择C
9
（ 2） 轮询模式主设备请求从设备发送数据。
A B C
主设备时间时间轮询否定应答
ENQ
数据应答帧
ENQ
否定应答
10
§ 7-2 流量控制
为什么要进行流量控制
– Flow control is a technique for assuring that a transmitting entity
does not overwhelm a receiving entity with data,The receiving
entity typically allocates a data buffer of some maximum length for
a transfer,When data are received,the receiver must do a certain
amount of processing before passing the data to the higher level
software,In the absence of flow control,the receiver’s buffer may
fill up and overflow while it is processing old data.
流量控制的方法
（ 1）停止等待流量控制（ Stop-and-Wait Flow Control）
（ 2）滑动窗流量控制（ Sliding Window Flow Control）
11
（ 1） Stop-and-Wait Flow Control
– 工作方式
发送方：传一个帧；
接收方：收到后，发回一个确认，表示愿意接收下一帧；
发送方：等待，直到收到确认信息；
若接收方不发确认，则简单中止传输。
– 帧的长度 不能太长。 A source need to break up a large block of
data into smaller blocks and transmit the data in many frames.
– 原因,
(1) The buffer size of the receiver may be limited（缓冲器容量）,
(2) The longer the transmission,the more likely that there will be an
error,necessitating retransmission of the entire frame,With smaller
frames,errors are detected sooner,and a smaller amount of data
needs to be retransmitted.（出错重传）
(3) On a shared medium,such as a LAN,it is usually desirable not to
permit one station to occupy the medium for an extended period,
thus causing long delays at the other sending stations.（共享媒体）
12
Bit Length and Frame Length
Bit Length,the bit length of a link is the number of bits present on the
link when a stream of bits fully occupies the link,即当数据流占满链路时，给定的链路上能排布多少个 bit，可如下计算：
Bit length=R*d/V (bit)
Where R is the data rate in bps;
d is the distance of the link in meters;
V is the velocity of propagation in m/s
Frame Length,一帧数据的 bit数。
Transmission Time,1（传输时间； 发送时间 ）,The time it takes for
a station to transmit a frame.
Propagation Time,a（传播时间）,The time it takes for a bit to travel
from sender to receiver,
13
The Inefficiency of Stop-and Wait (Figure 7.2)
14
Stop-and-Wait方式的缺点
In the situation where the bit length (a) of the link is greater than the
frame length (1),series inefficiencies result,（参见图 7.2,P.197）
The transmission time （ 发送时间 ） is normalized to 1,and the
propagation delay （ 传播时间 ） is expressed as the variable a,
When a<1,the propagation time is less than the transmission time,
Then the frame is sufficiently long that the first bits of the frame have
arrived at the destination before the source has completed the
transmission of the frame.
When a>1,the propagation time is greater than the transmission time,
In this case,the sender completes transmission of the entire frame
before the leading bits of that frame arrive at the receiver,
In Figure 7.2,if a>1,the line is always underutilized （没有充分利用） ; even if a<1,the line is also inefficiently utilized（利用率也不高）,In essence,for very high data rates,for very long distances
between sender and receiver,stop-and-wait flow control provide
inefficient line utilization.
15
（ 2） Sliding Window Flow Control
停止等待的缺点
– The essence of the problem described so far is that only one frame
at a time can be in transit,In situations where the bit length of the
link is greater than the frame length (a>1),serious inefficiencies
result,
解决的思路
– Efficiency can be greatly improved by allowing multiple frames to
be in transit at the same time.
滑动窗方法
– 假定 A,B两个站,A为发送站,B为接收站，全双工方式；
– A,B站各维护一个 长度为 W的 buffer（窗口）,即 A可连续发
W帧,B可连续收 W帧，其间可以不应答；
– B对 A发送的多帧数据进行一次应答，而不是每一帧应答一次；
16
操作的一般描述
连发多帧,发送方收到应答（ ACK）之前，可以发送多帧，以便充分利用链路的能力；
窗口,发送方和接收方分别建立缓冲区，称为窗口（ window），
用于存储帧数据；
窗口滑动,窗口在缓冲区内移动，窗口内包含了待发的若干帧；
编号,需对待发的帧编号，以 M（ =2^k）为模（ 0,1,…,M -1,0,1,…)
编号 ;
若 M=8，则窗口的大小取为 M-1=7。
17
具体说明（略）
– B receives frames 2,3,and 4 at one time.
– A maintains a list of sequence numbers that it is allowed to send.
– B maintains a list of sequence number that it is prepared to receive,
– Each of these lists can be thought of as a window of frames.
– The operation is referred to as sliding-window flow control.
– The size of the window,if k bits is used to express the number of the
frames,the window size is 2^k,The sequence number is 0 through 2^k-1,
对 图 7.3(see next slide)的说明
– It assumes the use of 3 bit sequence number,So that frames are numbered
sequentially from 0 through 7,and then the same numbers are reused for
subsequent frames,The shaded rectangle indicates the frames that may be
sent; in this figure,the sender may transmit 5 frames,beginning with
frame 0,Each time a frame is sent,the shaded window shrinks; each time
an acknowledgement is received,the shaded window grows,Frames
between the vertical bar and the shaded window have been sent but not yet
acknowledged,As we shall see,the sender must buffer these frames in
case they need to be retransmitted.
18
Sliding Window Depiction (Figure 7.3)
19
发送窗口和接收窗口移动规则
发送窗口
– 在发送开始时,发送窗口中有 M-1帧数据；
– 每发送一帧，发送窗的左端缩进一帧（向右）；
– 一旦有 ACK从接收方来，窗口右端向右扩张，扩展的帧数为所收到的 ACK确认收到的帧数
接收窗口
– 随着新数据的到来，接收窗口的大小不断缩小（表示在发出
ACK之前，所能接收新数据的帧数的减小）；
– 接收窗口的左端：当接收一帧时，接收窗口的左端向右移动一 帧；
– 接收窗口的右端：每发送一个 ACK（有时又记为 RR,Receive
response），接收窗口的右端向右扩张若干帧，扩张的帧数为上一次 ACK帧的编号与当前 ACK帧编号之差值。
20
Example 1（ 发送窗 ）
例 1
– 发送开始时,发送窗中包含 7帧；
– 发送方已经发送 0—4帧，未收到 ACK（或 RR）应答。此时，发送窗口的左端需向右收缩 5帧；
– 发送方收到 RR5，表示接收方已经收到 0—4帧，希望接收第 5帧，则发送窗口右端向右扩张 5帧。
01 2 3 4 5 6 70 1 2 3
发送窗
01 2 3 4 5 6 70 1 2 3
发送窗
4 5
21
Example 2（ 接收窗 ）
例 2
– 发送开始时（前），接收窗中包含 7帧（ 0--7），表示接收窗能够接收连续的 7帧；
– 接收方收到 2帧（第 0，第 1帧），暂时未发应答（ ACK或 RR），则接收窗口左端需向右收缩 2帧；
– 在接收 2帧之后，接收方发出 ACK 2（或 RR 2），表示已经收到第 0和第 1帧，并希望继续接收第 2帧。此时，接收窗的右端向右扩张 2帧。
01 2 3 4 5 6 70 1 2 3
01 2 3 4 5 6 70 1 2 3 4 5
接收窗
22
Example of a Sliding Window Protocol (Figure7.4)
23
双向传输与捎带
双向传输
– 双向传输表示全双工的传输，即通信的双方均有数据要发送且接收；
– 这样，双方均需维护 2张表，即双方均需有 2个窗口（发送，
接收）；
– 双方均需对收到对方的数据进行确认
捎带技术
– 若数据中含有存放确认序号的字段，且在一帧中同时发送，则称为捎带，即数据中含有控制信息。
24
§ 7-3 Error Detection
与传输帧的差错有关的几个概率
– Pb（比特差错率）,Probability of a single bit error,known as the bit
error rate (BER);
– P1（无错帧概率）,Probability that a frame arrives with no bit errors;
– P2（未检测到的有错帧概率）,Probability that a frame arrives with one
or more undetected bit errors;
– P3（检测到的有错概率）,Probability that a frame arrives with one or
more detected bit errors,but no undetected bit errors
几个概率之间的联系
– 若没有检测差错的手段，则有
where F is the number of bits per frame.
25
An Example
例
– ISDN 64 kbps 信道,一分钟内至少有 90%的时间里 满足 Pb<10^(-6)。
要求：每天最多允许出现一个未被检测到的有比特差错的帧，已知帧长度为 1000 bit。
求：实际的 P1=？,P2=？
解：根据给定的条件，该信道一天能传输的帧数为：
M=64*1000*3600*24/1000=5.529*10^6 帧要求的未检测到的有错帧概率为,P2=1/M=0.18*10^(-6)
根据给定条件,Pb=10^(-6)，且 F=1000，则 实际的 无错帧概率为
P1=（ 1-Pb)^F=（ 1-10^-6)^1000=0.999
实际的 未检测到的有错帧概率为,P2=1-P1=10^(-3)
结论,P2>>P2，即实际的 P2比要求的 P2高了 3个数量级，不满足要求。
26
Error Detection,Why
为什么要进行差错检测
– This is the kind of result that motivates the use of error-detection
techniques,All of these techniques operate on the following
principle (Figure 7.5,E6),For a given frame of bits,additional
bits that constitute an error detecting code are added by the
transmitter,This code is calculated as a function and compares the
two results,A detected error occurs if and only if there is a
mismatch,Thus P3 is the probability that a frame contains errors
and that the error-detection scheme will detect that fact,P2 is
known as the residual error rate and is the probability that an error
will be undetected despite the use of an error-detection scheme.
P3（检测到的有错概率）
P2（未检测到的有错帧概率）
27
Error Detection,How (Figure 7.5,E6)
28
Parity Check
方法
– To append a parity bit to the end of a block of data,A typical
example is character transmission,in which a parity bit is attached
to each 7-bit ASCII character,
– The value of the bit is selected so that the character has an even
number of 1s (even parity) or an odd number of 1s,
例：
假定要传输的 ASCII字符为 G，其 ASCII编码为 1110001（ 71H）。
对于奇校验,G的传输码为,1110001 1,1的个数为奇数对于偶校验,G的传输码为,1110001 0,1的个数为偶数在接收端，若任意一个比特出错（ 1?0或 0?1），会引起传输码
1的个数的变化，则可以检测出该字符出错。若有偶数个 bit出错，则不能检测。
29
Cyclic Redundancy Check (CRC)
CRC（循环冗余检测）的概念
– One of the most common,and one of the most powerful,error-detecting
codes is the cyclic redundancy check (CRC),which can be described as
follows,Given a k-bit block of bits,or message（报文）,the transmitter
generates an n-bit sequence,known as a frame check sequence (FCS),so
that the resulting frame,consisting of k+n bits,is exactly divisible by
some predetermined number,The receiver then divides the incoming
frame by that number and,if there is no remainder,assumes there was no
error.
CRC的方法
30
CRC校验
（ 1）模 2运算
（ 2）定义
T=要传输的（ k+n） bit 帧,n<k
M=k bit报文
F=n bit FCS（帧校验序列）
P=（ n+1） bit 的模式（预定的除数）
110101
10011
10011 1010
11 0101
10011 1111
31
（ 3）校验原理给定一个 k bit报文，发送器生成 n bit序列，称为帧校验序列
（ FCS）。这个 bit序列要使最后得到的 (k+n) bit的帧可以被一些预定的数值整除。于是接收器采用同样的数值去除接收到的帧时，
若无余数，则无差错。若有余数，则有差错。
要传输的报文为 M；加上 CRC的传输数据为 T；
在校验时，希望 T/P的余数为 0；
实际上,T=2^n M+F;
设,(2^n M)/P=Q+R/P,其中,Q为商,R/P为余数；
若实际传输的数据为,T=2^n M+R （即取 R=F）
则：在接收端，
T/P= (2^n M+R)/P=Q+R/P+R/P
按照模 2加的方法,R/P+R/P=0，
故：余数为 0。
32
（ 3）例已知,M=1010001101 （ 10bit报文）
方案,P=110101 （ 6bit模式）
R为 5bit （ FCS序列，由计算得）
2^5M=101000110100000
2^5M/P=1101010110+01110/110101 （ Q+R/P）
T=2^5M+R=101000110101110 （真正传输的）
在接收端,T/P=1101010110 （余数为 0）
33
CRC by Polynomials （自行阅读）
This method expresses all values as polynomials in a dummy（哑的）
variable X,with binary coefficients,The coefficients correspond to the
bits in binary number,
For M=110011,we have
For P=11001,we have
Arithmetic operation are again modulo 2.
CRC的两个主要公式
34
CRC by Polynomials（ Cont’d）
CRC校验可以检测以下各种差错
– All single bit errors;
– All double bit errors,as long as P(X) has at least three 1s;
– Any odd number of errors,as long as P(X) contains a factor (X+1);
– Any burst error for which the length of the burst is less than the length of
the divisor polynomial; that is,less than or equal to the length of the FCS;
– Most larger burst errors
常用的 P(X)
– CRC-12
– CRC-16
– CRC-CCITT
– CRC-32
35
CRC by Digital Logic（自行阅读）
CRC校验可以用包含异或门和移位寄存器的数字电路实现；
电路如图 7.6（ P.206）
– The register contains n bits,equal to the length of the FCS.
– There are up to n exclusive-OR gates.
– The presence or absence of a gate corresponds to the presence or absence
of a term in the divisor polynomial,P(X),excluding the X^n term.
36
用移位寄存器产生FS
C
码
37
接收端的差错检测
At the receiver:
– The same logic is used,As each bit of M arrives,it is inserted into
the shift register,If there have been no errors,the shift register
should contain the bit pattern for R at the conclusion of M,the
transmitted bits of R now begin to arrive,and the effect is to zero
out the register so that,at the conclusion of reception,the register
contains all 0s.
– 接收方所使用的逻辑相同。 M中的各个 bit在到达时被输入到移位寄存器，若无差错，则寄存器中应当含有由 M计算而得出的
R的模式。这时传输的 R序列开始到达，并且使寄存器全部清零。因此，在接收之后，寄存器中的值全部为 0。
– 反之，若有差错，则计算得不到 R模式，当 R序列到达并进行异或运算时，不能是寄存器清零，从而表明出现差错。
38
General CRC Architecture
39
§ 7-4 Error Control
Concept
– Error control refers to mechanism to detect and correct errors that
occur in the transmission of frames,As before,data are sent as a
sequence of frames; frames arrive in the same order in which they
are sent; and each transmitted frame suffers an arbitrary and
potentially variable amount of delay before reception,In addition,
we admit the possibility of two types of errors:
Lost frame（丢失帧）,frame fails to arrive at the other side,
For example,a noise burst may damage a frame to the extent
that the receiver is not aware that a frame that a frame has been
transmitted.
Damaged frame（损坏帧）,A recognizable frame does arrive,
but some of the bits are in error.
40
差错控制的常用方法
Error detection（差错检测）
– As discussed in the preceding section;
Positive acknowledgement（肯定确认）
– The destination returns a positive acknowledgement to successfully
received,error-free frames;
Retransmission after timeout（超时后重传）
– The source retransmits a frame that has not been acknowledged after a
predetermined amount of time;
Negative acknowledgement and retransmission（否认与重传）
– The destination returns a negative acknowledgement to frame in which an
error is detected,The source retransmits such frame.
上述方法均可以称为 自动重发请求 ARQ。
41
三种 ARQ标准
Stop-and-wait（停止等待） ARQ（ Automatic Repeat reQuest ）
– 停止等待 ARQ的基础是前面介绍过的停止等待流量控制技术。源站发送一个帧 之后，必须等待一个确认（ ACK），在目的站点的确认返回源站之前，源站不能发送其他数据帧。
Go-back-N（返回 N帧） ARQ
– 是最常用的基于滑动窗口流量控制的差错控制形式。尚未被确认的帧的最大数目取决于窗口的大小。正常情况下，接收站发肯定确认（ RR,Receive
Ready），若检测到差错，则接收站发一个否认（ REJ=拒绝），并将该帧及以后各帧丢弃，直到差错帧被正确接收到。源站收到 REJ后，重传出错帧及以后各帧。
Selective-reject（选择拒绝） ARQ
– 对于选择拒绝 ARQ，被重传的只有接收到的否认的帧或超时的帧。
否认被称为 SREJ。
42
停止等待 ARQ
到达站点的帧已经损坏
– 接收方
由差错检测技术检测；
处理：简单丢弃
– 发送方
设置计时器
若超时则重发
,确认”信息损坏
– 发送的帧被接收方正确接收，并返回确认信息，但是该确认信息损坏。
– 发方的计时器超时，则重发。
– 为避免接收方重复接收，需对发送的帧编号
优点：简单易行
缺点：效率低
43
返回 N ARQ
Consider that station A is sending frames to station B,After each
transmission,A sets an acknowledgement timer for the frame just
transmitted,Suppose that B has previously successfully received frame
(i-1) and A has just transmitted frame i,The go-back-N technique
takes into account the following contingencies（作出反应）,
Damaged frame,If the received frame is invalid,B discards the frame
and takes no further action as a result of that frame,There are two
subcases:
– Within a reasonable period of time,A subsequently sends frame (i+1),B
receives frame (i+1) out of order and sends a REJ i,A must retransmit
frame i and all subsequent frames.
– A does not soon send additional frame,B receives nothing and returns
neither an RR nor a REJ,When A’s timer expires,it transmits an RR
frame that includes a bit known as the P bit,which is set to 1,B interprets
the RR frame with a P bit of 1 as a command that must be acknowledged
by sending an RR,indicating the next frame that it expects,which is frame
i,When A receives the RR,it retransmits frame i.
44
Damaged RR
– B receives frame i and send RR(i+1),which is lost in transit,Because
acknowledgements are cumulative,it may be that A will receive a
subsequent RR to a subsequent frame and that it will arrive before the
timer associated with frame i expires,
– If A’s timer expires,it transmits an RR command,It sets another timer,
called the P-bit timer,If B fails to respond to the RR command,or if its
response is damaged,then A’s P-bit timer will expire,At this point,A
will try again by issuing a new RR command and restarting the P-bit timer,
This procedure is tried for a number of iterations,If A fails to obtain an
acknowledgement,after some maximum number of attempts,it initiates a
reset procedure.
Damaged REJ
– If a REJ is lost,this is equivalent to the second case of ―Damaged frame‖.
45
返回N
AR
Q
与选择拒绝ARQ
46
选择拒绝 ARQ
特点
– 被重传的只有接收到否认的帧和超时的帧；
– 由于重传的帧减少到最少，故效率高；
– 但是系统的复杂性较高：
– 接收方必须维护一个足够大的缓存，以保存 SREJ后收到的帧，
直到有差错的帧被重传；
– 接收方需具有按照正确顺序插入后到的帧的功能；
– 发送方需要具有发送失序帧的能力；
– 选择拒绝 ARQ的应用例见 Figure 7.9
47
§ 7-5 High-Level Data Link Control
(HDLC)
简介
– The most important data link control protocol is HDLC (ISO 3009,ISO
4335),Not only is HDLC widely used,but it is the basis for many other
important data link control protocols,which uses the same or similar
formats and the same mechanisms as employed in HDLC,
1,HDLC协议
（ 1）规定三种类型的站点
Primary station,负责控制链路操作，有主站发出的帧称为 命令 ；
Secondary station,在主站的控制下操作，由从站发出的帧称为 响应 ；
Combined station,混合了主站和从站的特点（发出的帧可以是命令，
也可以是响应）
48
（ 2）使用两种链路配置
Unbalanced configuration,由一个主站及一个或多个从站组成，支持全双工和半双工传输；
Balanced configuration,由两个混合站组成，支持全双工和半双工传输；
（ 3）支持三种数据链路模式
Normal response mode (NRM),使用主从关系非平衡配置，用于多点线路，也可以用于点对点链路。主站能够初始化从站的数据传输，而从站只能通过数据传输来响应主站的命令；
Asynchronous balanced mode (ABM),使用平衡配置，两个混合站都能够初始化数据传输，不需要得到对方混合站的许可；
Asynchronous response mode (ARM),使用非平衡配置。从站能够初始化传输。但主站仍对线路全权负责，包括初始化、差错恢复和联络的逻辑断开。
49
2,帧结构
（ 1）标志字段标志,01111110
注意：与数据 01111110
的区别，若出现与标志相同的数据，按如下方法处理。
50
比特填充
在发送端：若在起始标志和结束标志之间出现连续 5个 1，则发送端插入一个 0，称为 bit填充。
在接收端：若出现任意一个连续的 5个 1，则检查第 6个 bit:
– 若 bit6=1，且 bit7=0，则为标志段；
– 若 bit6=1，且 bit7=1，则此时处于由发方指明的丢弃状态；
– 若 bit6=0,则为数据
举例
– 原始数据为,0111111011111111111101111110111111001111110
– 比特填充后,01111110111110111110110111110101111101001111110
– 恢复的数据,0111111011111111111101111110111111001111110
51
（ 2）地址字段
· 地址字段标识传输该帧或准备接收该帧的从站。实际上，点对点传输不需要这个字段，但是为了统一，所有帧均包含这个字段。
· 地址字段常为 8bit，但是可以使用扩展格式，这时地址的实际长度是
7bit的倍数（见图 7.10）。
· 地址字段的最后一个八位组的最低位为 0。
· 若地址为全 1，则表示所有站点的地址，实际上是广播方式。
（ 3）控制字段
· HDLC定义 3种帧，各有不同的控制字段
- 信息帧（ I帧）,携带向用户传输的数据，此外还捎带流量控制和差错控制的数据；
- 监控帧（ S帧）,在未使用捎带技术时提供了 ARQ机制；
- 无编号帧（ U帧）,提供增补的链路控制功能。
- 控制字段中的,轮询 /结束（ P/F）,bit：
- 在命令帧中，为 P比特，若设置为 1，则向对等实体请求（轮询）响应帧；
- 在响应帧中，为 F比特，若设置为 1，则表示发送的这个响应是一个请求命令的结果
52
（ 4）信息字段
· 只有 I帧和 U帧才具有信息字段；
· 可以包含任意的比特序列，但必须由整数倍的八位组组成；
· 信息字段的长度不固定，可以大到系统设定的最大值。
（ 5）帧检验序列字段
· 帧检验序列（ FSC）是一个差错检测码，由帧中除了标志字段以外的其它位计算得到；
· 这个检测码通常是 16bit的 CRC-CCITT码；
· 也可以选择使用 CRC-32的 32bit的 FCS。
3,操作
（ 1）内容包含在两个站点之间交换 I,S,U帧
（ 2）三个阶段
· 初始化链路；
· 交换数据和控制信息；
· 一方发出信号来中止操作
53
表 7.1 HDLC命令和响应
54
Initialization
Initialization may be requested by either side by issuing one setmode
command,This command serves three purposes:
– It signals（通知） the other side that initialization is requested.
– It specifies which of the three modes (NRM,ABM,ARM) is requested.
– It specifies whether 3- or 7- bit sequence numbers are to be used,
If the other side accepts this request,then the HDLC module on that
end transmits an unnumbered acknowledged (UA，无编号确认 )
frame back to the initiating side,
If the request is rejected,then a disconnected mode (DM) frame is sent.
55
Data Transfer
当初始化一个请求并被接受后，就会建立起一个逻辑连接。双方都可以通过 I帧开始发送用户信息，帧的序号从 0开始。 I帧的 N(S)和 N(R)是用于支持流控制和差错控制的序号。 HDLC模块在发送 I帧序列时，会按顺序对它们编号，并将序号放在 N(S)中，这些编号以 8或 128为模，取决于使用的是 3bit序号还是 7bit序号。 N(R)是对接收到的 I帧的确认。有了 N(R)，
HDLC模块就能够指出自己希望接收的下一个 I帧的序号。
S帧同样也用于流控制和差错控制。其中，接收就绪帧（ RR）通过指出希望接收到的下一帧来确认接收到的最后一个 I帧。在缺少能够捎带确认的反向用户数据流（ I帧）时，就需要使用 RR帧。接收未准备就绪
（ Received-not-Ready,RNR）帧和 RR帧一样，都可以用于对 I帧的确认，
但它同时还要求对等实体暂停 I帧的传输。当发出 RNR的实体再次准备就绪之后，会发送一个 RR。 REJ对返回 N ARQ进行初始化。它指出最后一个接收到的 I帧已经被拒绝，并要求重发以 N(R)序号为首的所有后续 I帧。
选择拒绝（ SREJ）用于对某一个帧的重发请求。
56
Disconnect
Either HDLC module can initiate a disconnect,either on its own
initiative if there is some sort of fault,or at the request of its higher-
layer user,HDLC issues a disconnect by sending a disconnect (DISC)
frame,The remote entity must accept the disconnect by replying with a
UA and informing its layer 3 user that the connection has been
terminated,Any outstanding unacknowledged（未被确认的） I-
frame may be lost,and their recovery is the responsibility of higher
layers.
57
Examples
58
说明图 7.12（ c）表示忙状态其原因可能为 HDLC实体处理 I帧的速度无法跟上帧到达的速度。这时，
接收缓存会填满，则接收端不得不使用 RNR命令来阻止进入缓存的 I
帧流。在本例中,A 发出一个 RNR，又一个它要求 B停止传输 I帧。
收到 RNR的站点，通常会每隔一段时间就向忙站点发出询问，这是通过发送一个 P bit为 1的 RR来实现的，它请求对方用 RR或者 RNR来响应。当忙状态清除后,A 返回一个 RR，这时来自的 B帧可以继续传输。
59
Examples (Cont’d)
60
§ 7-6 Other Data Link Control Protocols
1,LAPB (Link Access Procedure,Balanced)
作为 X.25分组交换网接口标准的一部分，是 HDLC的子集，只提供 ABM下的 HDLC，帧格式与 HDLC一致，适用于节点之间的点对点链接。
2,LAPD (Link Access Procedure,D-Channel)
是 ISDN规约集的一部分，提供 D信道（用户与 ISDN借口的逻辑信道）的数据链路控制。 LAPD与 HDLC的区别,LAPD中限于 ABM；永远使用 7bit序号；
FSC总是 16bit的 CRC；地址字断段 16bit等。
3,逻辑链路控制（ LLC）
属于 IEEE802协议族中有关局域网的控制操作标准的一部分。 LLC与 HDLC
的区别：格式不同（参见图 7.13），链路控制功能被分为 2层，媒体接入层
（ MAC，下）和 LLC层（上）。
4,帧中继（ Frame Relay）
是一种数据链路控制设施，用于高速分组交换网，提供流水作业能力。
5,异步传输模式（ ATM,Asynchronous Transfer Mode）
ATM的设计目标是提供流水化数据传送能力。 ATM不是基于 HDLC的，又称为信元中继。信元的长度固定为 53个字节。
61
Homework of Chapter 7
7.4,7.11（ This Time,October 18）
7.17,7.24 （ Next Time,October 25）
Due by Next Monday
62
End of This Chapter
