《计算机通信与网络》课件第四讲dl

1、数据链路层链路与数据链路数据链路层的基本功能数据链路层的服务停-等协议实用的停-等协议连续ARQ协议选择重传ARQ协议HDLC、SLIP、PPP要点数据链路层链路：一条无源的点到点的物理线路，中间没有任何交换结点。数据(逻辑)链路: (物理)链路+通信规程数据链路层的基本功能链路管理：数据链路的建立、维持和释放成帧:收方能从收到的比特流中准确地区分出一帧的开始和结束流量控制：发方发送数据的速率必须使收方来得及接收差错控制：前向纠错、检错重发区分数据和控制信息：寻址：多点连接的情况下，可保证每一帧都能送到正确的目的站, 收方也能知道发方是哪一个站。透明传输:不管所传数据是什么样的比特组合，都能在

2、链路上传送。H4M数据链路层的模型成帧字符计数法带字符填充的首尾界符法带位填充的首尾标志法物理层编码违例法字符计数法帧在帧头部中使用一个字段来标明帧内字符数51234567898012345687890123第1帧5个字符第2帧5个字符第3帧8个字符第4帧8个字符51234767898012345687890123第1帧第2帧(错误的)现在的一个字符计数 无差错 有差错 问题: 计数器在传输过程中出现错误，导致整个数据流出错。带字符填充的首尾界符法以特定的字符序列为控制字段DLESTXADLEBDLEETXDLESTXADLEBDLEETXDLEDLESTXADLEBDLEETX填充的DLE源

3、(网)目(网)每一帧以ASCII字符序列DLE STX,以DLE ETX结束。DLE= Date Link Escape STX=Start of Text ETX=End of Text缺点：依赖于字符集，不通用，也无法扩展面向字符的成帧方法，不利于系统之间相互通信。Bisync带位填充的首尾标志法 HDLC帧中采用 01111110 作为开始和结束的标志位采用统一的帧格式，以特定的位序列进行帧同步和定界。效率高，转义时只需插入一个比特。 位序列进行帧同步和定界物理层编码违例法SFD : 帧首定界 - 10101011IEEE 802.3 7 1 2/6 2/6 2 46-1500 4 字节

4、FCSPA SALENSFDDALLC PDUPad适用于在物理介质的编码策略中采用冗余技术的网络。数据位1: 编码成高-低电平对数据位0: 编码成低-高电平对高-高电平对、 低-低电平对在数据编码中没有使用。可用来确定位边界。优点：无需填充最简单而又最基本的一个数据链路层协议是：停止等待协议(stop-and-wait)两机通信的简化模型一般，数据的传输受到两个因素的影响信道可靠性发送和接收能力理想化的数据传输无需数据链路层协议 假定1：链路是理想的传输信道，数据既不会出错也不会丢失 假定2：不管发送方的速率多快，接收方总能接收到并上交,缓冲区无穷大，无需流量控制而在一般情况下，上述情况难以

5、保证 停止等待协议(假定传输信道理想) 发送方发出一帧后，要停下来等待接收方的应答，收到确认后才能发送下一帧。AP1主机AAP2主机B数据链路DL从主机取数据上交主机DATA1DATA2结点A结点BACKACK从主机取数据上交主机DATA1DATA4DATA3DATA2结点A结点B 理想信道 具有简单流量控制的数据链路层协议t实用的停止等待协议时间ABDATA0送主机ACKDATA1送主机ACK(a) 正常情况ABDATA0DATA0送主机ACK(c) 数据帧丢失重传tout丢失 ！ABDATA0送主机ACKDATA0丢弃ACK(d) 确认帧丢失重传tout丢失 ！ABDATA0NAKDATA

6、0送主机ACK(b) 数据帧出错重传出错四种情况超时计时器的作用结点A发送完一个数据帧时，就启动一个超时计时器(timeout timer)。计时器又称为定时器。若到了超时计时器所设置的重传时间 tout而仍收不到结点 B 的任何确认帧，则结点 A 就重传前面所发送的这一数据帧。一般可将重传时间选为略大于“从发完数据帧到收到确认帧所需的平均时间”。 解决重复帧的问题 使每一个数据帧带上不同的发送序号。每发送一个新的数据帧就把它的发送序号加 1。 若结点 B 收到发送序号相同的数据帧，就表明出现了重复帧。这时应丢弃重复帧，因为已经收到过同样的数据帧并且也交给了主机 B。但此时结点 B 还必须向

7、A 发送确认帧 ACK，因为 B 已经知道 A 还没有收到上一次发过去的确认帧 ACK。 帧的编号问题 任何一个编号系统的序号所占用的比特数一定是有限的。因此，经过一段时间后，发送序号就会重复。 序号占用的比特数越少，数据传输的额外开销就越小。 对于停止等待协议，由于每发送一个数据帧就停止等待，因此用一个比特来编号就够了。一个比特可表示 0 和 1 两种不同的序号。 帧的发送序号 数据帧中的发送序号 N(S) 以 0 和 1 交替的方式出现在数据帧中。每发一个新的数据帧，发送序号就和上次发送的不一样。用这样的方法就可以使收方能够区分开新的数据帧和重传的数据帧了。 可靠传输 虽然物理层在传输比特

8、时会出现差错，但由于数据链路层的停止等待协议采用了有效的检错重传机制，数据链路层对上面的网络层就可以提供可靠传输的服务。 实用的停止等待协议（ARQ协议）:前提：实际信道不满足理想化数据传输的假定 流量控制方法：等待发送 差错控制：发送方数据帧中加入校验码（CRC），由接收方检查；若出错，返回NAK；发送方收到NAK后重发。 帧丢失处理：超时定时器；以序号标识数据帧 优点：简单 缺点： 信道利用率低，停等方式是很慢的。在发送下一帧之前，每一帧必须穿越距离到达接收方，而每一帧的应答也必须从接收方传输回来。设缓冲区可以装下一个数据帧：情况1：正常情况2：数据帧错（但已接收）： 解决方案：重发情况3

9、：数据丢失 a数据帧丢失 ： 死锁 b应答帧丢失 ： 死锁 解决方案：超时重发情况4：数据帧正确，但应答帧丢失，超时重发后，使得该数据帧在接收方收到两次：重复帧 解决方案：使每个数据帧带上不同的发送序号，每发送一个新的帧就把它的发送序号加1，这样，若两个数据帧序号相同，则为重复帧，可丢弃一个。对于每次只发送一个帧的停止等待协议，可以只用两个不同的编号（一个比特）data iNAKidata iDatai 出错发出一帧等待，收到NAK重发上一帧发送方接收方ACKidata i+1直到收到ACK才发送下一帧数据帧错实用的停等协议frame iACK iframe I+1ACKi+1frame i+

10、2frame i+2ACK i+2frame i+3ACK i+3frame i+3ACK i+3发送方接收方超时超时帧丢失 重发ACK丢失 重发,丢失重复帧丢失重复帧停等协议的算法流程SGet !st Data from Network LayerV(s) = 0N(s)= V(s)Save Date Frame to BufferSend Buffered Data Frame to Physical LayerStart TimerWait EventReceived ACKReceived NAKTime OutGet Next Data V(s) = 1-V(s)RV(r) = 0W

11、ait Data FrameReceived Frame, and Test if Error occursCorrectErrorN(s) = V(r) ?Discard FramePass Data toNetwok Layer Send ACKSend NAKSend ACKV(r)= 1-V(r)停等协议的效率A:应答帧长度D:数据帧长度I: 传播时延p:数据帧出错的概率C:传输数据率H:帧头长度F:帧长度=H+DHDFt0无差错信道frame0数据帧的发送时间 F/CF/C+IF/C+A/C+2I=D/(F+A+2CI)=有差错信道senderreceiver1D F1+2CI+AF

12、=1D F1+2CI+AF(1-p)I两个成功发送的数据帧之间的最小时间间隔确认帧的发送时间Iframe1连续ARQ协议/流水线协议工作原理：发送方发完一帧后，不必停下来等待对方的应答，可以连续发送若干帧；如果在发送过程中收到接收方的肯定应答，可以继续发送；若收到对其中某一帧的否认帧，则从该帧开始的后续帧全部重发.由于减少了等待时间，整个通信的吞吐量就提高了。 流量控制方法：连续发送 差错控制：同停等协议 优点：连续发送提高了信道利用率,理想情况下效率高 缺点： 回走重传（Go-back-N）,导致某些已正确接收的帧的重传，因此降低了发送效率 误码率较低时，连续ARQ优于停等协议；反之则不一定

13、Go-back-N ARQframe 1senderreceiver出错7 ， 8帧 被丢弃frame 2frame 3ACK 4frame 4frame 5ACK 5frame 6frame 7frame 8NAK 6ACK 8frame 7frame 6frame 86, 7, 8帧 重传注意: 1 接收端只按序接收数据帧;虽然在有差错的6号帧后又收到了正确的2个数据帧，但都必须将它们丢弃。 2 发送节点在每发送完一个数据帧时都要设置超时定时器。只要在所设置的超时时间tout 到而仍未收到确认帧，就要重发相应的数据帧。Go-back-N。(重传6、7、8)。 3 为了减少开销，连续ARQ协

14、议还规定接收端不一定每收到一个正确的数据帧就必须发回一个确认帧，而是可以在连续收到好几个正确的数据帧后，才对最后一个数据帧发确认信息。即，对某一数据帧的确认就表明该数据帧和这以前所有的数据帧均已正确无误地收到了。这样可以使接收端少发一些确认帧，因而减少了开销。当未被确认的数据帧的数目太多时，只要有一帧出了差错，就可能有很多的数据帧需要重传，增加了开销。为了对所发送出去的大量数据帧进行编号，每个数据帧的发送序号也要占用较多的比特数，这样又增加了一些不必要开销。连续ARQ协议的问题滑动窗口概念前提：在连续ARQ协议中，必须对可以连续发出的最多帧数（已发出但未确认的帧）作限制。 原则：循环重复使用已

15、收到确认的帧的序号 窗口:是指一个发送方和接收方都要创建的额外缓冲区。这个窗口可以在收发两方存储数据帧，并且对收到应答之前可以传输的数据帧的数目进行了限制。 流量控制： 发送窗口：其大小WT表示在收到对方确认的信息之前，可以连续发出的最多数据帧数（只有序号在窗口内的帧才可以发送） 接收窗口：其大小WR可以连续接收的最多数据帧数（只有序号在窗口内的帧才可以接收，否则丢弃）接收窗口驱动发送窗口的转动当发送窗口和接收窗口的大小都等于1，即为停止等待协议。窗口后沿窗口前沿窗口后沿窗口前沿窗口后沿窗口前沿窗口后沿窗口前沿窗口后沿窗口前沿窗口后沿窗口前沿窗口后沿窗口前沿窗口后沿窗口前沿窗口后沿窗口前沿窗口

16、后沿窗口前沿滑动窗口协议0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7已成功发出的数据帧将发出的数据帧帧序号发送方缓冲区发送序号用3比特编码， 即发送序号可以有8个不同的序号，从0到7。设WT=7, 即在未收到对方确认信息的情况下，发送端最多可以发送出7个数据帧。0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7WT发送窗口允许发送6个帧不允许发送这些帧(a)0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7WT允许发送5个帧不允许发送这些帧(b)已发送0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7WT不允许发送这些帧(c)已发送0 1

17、2 3 4 5 6 7 0 1 2 3 4 5 6 7WT还允许发送4个帧不允许发送这些帧(d)已发送并已收到确认已发送0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7已收到0号帧接收窗口是为了控制可以接收哪些数据帧而不可以接收哪些帧。在接收端只有当收到的数据帧的发送序号落入接收窗口内才允许将该数据帧收下。若接收到的数据帧落在接收窗口之外，则一律将其丢弃。窗口后沿窗口前沿WR接收窗口0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 70 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7已收到03号帧WR=1(a) 准备接收0号帧(b) 准备接收1号帧,并发送A

18、CK0(b) 准备接收4号帧只有在接收窗口向前移动时，发送窗口才能向前移动。0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7已正确接收的数据帧接收方缓冲区窗口后沿窗口前沿当数据帧的的发送序号所占用的比特一定时，发送窗口的最大值是多少？ 发送窗口的最值：WT + WR 2n (n为序号的位数) WT 2n - 1 结点A 结点BTDATA0DATA3DATA2DATA1DATA4DATA5DATA6DATA7DATA0ACK0ACK7以n=3为例 WT=8 设发送端发送完07号共8个数据帧。因发送窗口已满，发送暂停。假定这8个数据帧都已正确到达接收端，并且对每一个数据帧，接收端都发

19、送出确认帧。下面考虑两种不同的情况:所有的确认帧都正确到达了发送端，因而发送端接着又发送8个新的数据帧，其编号应当是07。所有的确认帧都丢失了。经过一段时间后，发送端重发这8个旧的数据帧，其编号仍为07。TDATA0DATA3DATA2DATA1结点A结点BDATA4DATA5DATA6DATA0DATA1ACK0ACK6 WT=7连续ARQ协议一般情况下，窗口大小与信道的关系：如果信道的延迟大，则等待时间长，多开窗为宜如果信道的噪声大，则易出错，易导致重传，少开窗为宜选择重传ARQ协议在连续ARQ中，一旦中间有一个帧出错，则在其后接收到的帧全部丢失，要发送端全部重发，为此的改进：在选择重传A

20、RQ中，接收端把后面接收到的数据帧暂存在接收端的缓存中，等待前面那个出错的数据帧重传后，再接收确认缓存中的数据，减少了重传的数据帧。选择重传 ARQframe 1senderreceiver出错frame 2frame 3ACK 4frame 4frame 5NAK 6frame 6frame 7frame 8ACK 9frame 9frame 6frame 10只重传帧6ACK10选择重传ARQ协议基本原理: 出错时，只重传出错的数据帧或定时器超时的数据帧。 实现: WR1,暂存接收窗口中序号在出错数据帧之后的数据帧。 优点:可以避免重复传送已经正确到达接收端的数据帧，提高了信道的利用率。

21、缺点: 在接收端要设置具有相当容量的缓存空间。 接收窗口的最大值: WR 0888校验区间透明传输区间*信息字段的头尾各加上24bit的控制信息， 就构成了完整的一帧。各字段说明标志字段F：头尾各8位“01111110”标记帧的首尾边界以实现帧同步零比特填充(连续五个1后填0)以实现透明传输(透明传输区间)地址字段A： 多点线路中用于区别各个终端，对于点-点线路，用来区别命令和响应。非平衡方式，填入从站地址平衡方式，填入响应站地址 帧检验序列FCS：采用CRC-CCITT16， G(x) = x16 + x12 + x5 + 1 控制字段C：标记帧类型，并附加控制信息信息帧：若控制字段的第1比

22、特为0，传送的是数据信息监督帧：若控制字段的第1-2比特为10，传送的是确认等控制信息无编号帧：若控制字段的第1-2比特为11，建立和释放链路的信息等循环冗余检验的原理 在数据链路层传送的帧中，广泛使用了循环冗余检验 CRC 的检错技术。假设待传送的数据 M = 1010001101（共k bit）。我们在M的后面再添加供差错检测用的 n bit 冗余码一起发送。 虽然增大了数据传输的开销,但却可以进行差错检测。 冗余码的计算 用二进制的模 2 运算进行 2n 乘 M 的运算，这相当于在 M 后面添加 n 个 0。得到的 (k + n) bit 的数除以事先选定好的长度为 (n + 1) bi

23、t 的数 P，得出商是 Q 而余数是 R，余数 R 比除数 P 至少要少1 个比特。 冗余码的计算举例 设 n = 5, P = 110101，模 2 运算的结果是：商 Q = 1101010110， 余数R = 01110。将余数 R 作为冗余码添加在数据 M 的后面发送出去，即发送的数据是101000110101110，或 2nM + R。 1101010110 Q 商 除数 P 110101 101000110100000 2nM 被除数 110101 111011 110101 111010 110101 111110 110101 101100 110101 110010 11010

24、1 01110 R 余数循环冗余检验的原理说明 帧检验序列 FCS 在数据后面添加上的冗余码称为帧检验序列 FCS (Frame Check Sequence)。循环冗余检验 CRC 和帧检验序列 FCS并不等同。CRC 是一种常用的检错方法，而 FCS 是添加在数据后面的冗余码。FCS 可以用 CRC 这种方法得出，但 CRC 并非用来获得 FCS 的惟一方法。 检测出差错 如果数据在传输过程中不产生误码,则接收端收到的应该是2nM + R, 将这个数除以P后, 余数为0只要得出的余数 R 不为 0，就表示检测到了差错。但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。一旦检测出差

25、错，就丢弃这个出现差错的帧。只要经过严格的挑选，并使用位数足够多的除数 P，那么出现检测不到的差错的概率就很小很小。 FInfoCAFFCS8 位16 0888信息帧I比特序号监督帧S无编号帧U1234567811100N(S)SMP/FP/FP/FN(R)N(R)M序号N(S)和N(R)以3位表示，模8循环， N(S)表示当前发送的信息帧的序号(帧自身的识别号码)。 N(R)表示准备接收的最低帧序号，确认序号在其前面的帧都已正确接收可用N(R)字段捎带确认。在S-帧中的控制域包含一个N(R)域却没有N(S)域。S-帧并不传输数据因此并不需要N(S)域来识别帧。 S-帧中在P/F位之前的两位是

26、携带编码后的流量和错误控制信息的。 所有的监督帧只有48bit。扩展方式，序号N(S)和N(R)以7位表示，模128循环，用于卫星链路，此时控制字段占16位监督帧的名称和功能第3-4比特 帧 名功 能0 0RR(Receive Ready)接收准备就绪准备收下一帧确认序号为 N(R) -1及其以前的各帧1 0RNR(Receive Not Ready)接收未就绪暂停接收下一帧确认序号为N(R) -1及其以前的各帧0 1REJ(Reject)拒绝SREJ(Selective Reject)选择拒绝从N(R)起的所有帧都被否认但确认序号为N(R) -1及其以前的各帧1 1只否认序号为N(R)的帧但

27、确认序号为 N(R) -1及其以前的各帧前三种用在连续ARQ协议中，第四种用在选择重传ARQ协议。 在前两种监督帧相当于确认帧ACK, REJ帧相当于否认帧NAK。RR帧和RNR帧都具有流量控制的作用。RR帧表示已做好接收帧的准备，希望对方继续发送，而RNR帧则表示希望对方停止发送。TI 0,0结点A结点BI 1,0RR 1RR 2TI 0,0结点A结点BI 1,0I 0,2I 2,0TI 0,0结点A结点BI 1,0REJ 2I 0,2I 0,0TI 0,0结点A结点BI 1,0RNR 2RR 2Ttimeout= 0 无意义= 1 非平衡配置 正常响应方式 主站 S/I 帧 P=1 （命令

28、） S/I 帧 （响应）I中F=1，表示最后一个数据帧S中F=1，表示此时没有数据要发送从站NRM异步响应方式ARM平衡配置 异步平衡方式 ABM P=1 （询问）F=1 （回答本站状态）命令方响应方P/F(Poll/Final) 位的意义（询问/终止）在不同的数据传送方式中，P/F比特的用法是不一样的。在非平衡配置中P/F比特的使用方法主站A从站B从站C结点A结点B，CB,RR0,PB,I00B,I10B,I20B,I30,FB,RR4C,RR0,PC,RR0,FtFACB,RR0,P FB10RRP=1000FCSFB,I10 FB0001000FCSF P=0B,I30,F FB0011

29、000FCSFF=1无编号帧，定义了15种，起控制作用 建立数据链路： 正常响应方式，置正常响应方式SNRM 异步平衡方式，置异步平衡方式SABM 拆除数据链路：断连命令DISC 对命令的确认：无编号确认UA 帧拒绝FRMR：是一个响应帧，表示通过重发仍不能纠正的错误，如收到非法命令，收到了无效的控制字段，数据字段过长，收到无效的N(R) ，收到长度有错误的监督帧或无编号帧等等。无编号帧FRMR有3或5个字节的信息字段，用以说明发送此帧的原因。多点链路的建立和释放A站与B站建立链路状态变量初始化A站与C站建立链路状态变量初始化主站A次站B，CB,DISC,PtV1(S)0B,SNRM,PB,U

30、A,FV1(R)0V2(S)0V2(R)0V(R)0V(S)0B站将状态变量初始化V(R)0V(S)0C站将状态变量初始化数据传输阶段A站与B站的链路释放B,UA,FC,DISC,PC,UA,FA站与C站的链路释放B站的链路释放C站的链路释放C,SNRM,PC,UA,F正常响应方式复合站的链路建立和断连复合站A复合站BA,DISC,PtV (S)0B,SABM,PB,UA,FV (R)0V(R)0V(S)0B站将状态变量初始化数据传输阶段A站释放链路A,UA,FB站要求释放链路链路建立阶段A站状态变量初始化异步平衡方式:由于现在两个站平等，所以任何一个站都可以在数据传送完毕后提出断连的要求。I

31、nternet中的数据链路层 ISP拥有路由器，一般都用专线与Internet相连。用户用家中的电话线通过Modem接入ISP。ISP分配给该用户一个临时的IP地址，因而用户就可以像Internet上的主机一样使用网上所提供的服务。当用户结束通信时，ISP将该用过的IP地址收回，以便下次再分配给新拨号入网的其它用户。 在用户与ISP之间的链路上使用得最多的协议是SLIP和PPP协议。PC机用拨号方式入网SLIP: RFC1055字节11111SLIP是一个简单的面向字符的协议。DBC0C0DBDBDCDDC01IP数据报11ENDENDESCESCSLIP协议的缺点:1 SLIP没有差错检测的

32、功能。如果一个SLIP帧在传输中出了差错，就只能靠高层来进行纠正。2 通信的每一方必须事先知道对方的IP地址。在建立过程中，地址不能自动地设定。而IP地址紧缺，不可能给每个Internet用户分配一个唯一的IP地址。3 SLIP仅支持IP，而不支持其他的协议。4 SLIP没有提供任何形式的身份验证。不适于拨号方式5 SLIP并未成为Internet的标准协议。因此目前存在着多种互不兼容的版本，影响了不同网络的互连。压缩的SLIP(CSLIP)由于串行线路的速率通常较低，而通信经常是交互的，因此在SLIP线路上有许多小的TCP分组进行交换。为了传送1个字节的数据需要20字节的IP首部和20个字节

33、的TCP首部。为了提高数据传输的效率，又提出了一种CSLIP,它可将上面的40个字节的额外开销压缩到3或5个字节。压缩基于这样的考虑： 在一连串的分组中，一定会有很多的首部字段是相同的。如某一字段和前个分组中的相应字段是一样的，就可不发送这个字段。如这一字段与前个分组中的相应字段不同，就可只发送改变的部分。CSLIP大大地改善了交互响应的时间。点到点协议（PPP）:RFC1661,1662,1663PPP有三个部分:一个将IP数据报封装到串行链路的方法。这种帧格式也处理错误检测。 PPP既支持异步链路 (无奇偶校验的 8比特数据)，也支持面向比特的同步链路。(2) 一个用来建立、配置和测试数据链路连接的链路控制协议LCP(Link Control Procotol)，通信的双方可协商一些选项。当链路不再需要时，挑出这些线路，测试它们，商议选项，并仔细地再 释放链路控制协议。(3) 一套网络控制协议NCP(Network Control Protocol)，支持不同的网络层协议，如IP，OSI的网络层， DECnet ，以及 AppleTalk等。 对SLIP的改进，Internet的正式标准，支持差错检测、多种协议、允许连接时协商IP地址、允许身份验证.点到点协议（PPP）