计算机网络原理与应用4.ppt

1、计算机网络原理与应用,第4章 数据链路层,4.1 基本概念 4.2 数据链路层的作用 4.3 停止等待协议 4.4 连续ARQ协议 4.5 选择重传ARQ协议 4.6 面向比特的链路控制规程HDLC,4.1 基本概念,链路(link)：物理链路，就是一条无源的点到点的物理线路段，中间没有任何其他的交换结点。在进行数据通信时，两个计算机之间的通路往往是由许多的链路串接而成的。而一条链路只是一条通路的一个组成部分。传输单位是比特。 数据链路(data link)：逻辑链路，在物理链路加上必要的通信规程就构成了数据链路。数据链路就像一个数字管道，可以在它上面进行数据通信。当采用复用技术时，一条链路上

2、可以有多条数据链路。传输单位是帧。 数据链路层协议：数据链路层通信规程，为在不太可靠的物理链路上建立数据链路从而实现可靠的数据传输而规定的一些规程。,数据链路建立在两台物理上连接起来的设备之间 主机-路由器，路由器-路由器，主机-主机 数据链路上传输的数据单位：帧（Frame）,network link physical,M,frame,物理链路,数据链路协议,网络接口卡,数据链路/逻辑链路 = （物理）链路 + 数据链路层协议,4.2 数据链路层的作用,链路管理：两个网络结点进行通信时，对数据链路的建立、维持和释放的管理。 帧同步：在数据链路层，数据的传送单位是帧。帧同步是指收方应当能从收到

3、的比特流中准确地区分出一帧的开始和结束在什么地方。 流量控制：发方发送数据的速率必须使收方来得及接收。当收方来不及接收时，就必须及时控制发方发送数据的速率。 差错控制： 控制的比特差错率。采用了编码技术。有两大类：一类是前向纠错；另一类是检错重传。 将数据和控制信息区分开：在许多情况下，数据和控制信息处于同一帧中。因此一定要有相应的措施使收方能够将它们区分开来。 透明传输：就是不管所传数据是什么样的比特组合，都应当能够在链路上传送。当所传数据中的比特组合恰巧出现了与某一个控制信息完全一样时，必须采取适当的措施，使收方不会将这样的数据误认为是某种控制信息。 7)寻址：保证每一帧都能发送到正确的目

4、的站。收方也应知道发方是哪个站。,4.3 停止等待协议,停止等待(stop-and-wait)协议是最简单但也是最基本的数据链路层协议。,4.3.1 不需要数据链路层协议的数据传输 4.3.2 具有最简单流量控制的数据链路层协议 4.3.3 实用的停止等待协议 4.3.4 停止等待协议的算法,4.3.1 不需要数据链路层协议的数据传输,数据的传输收到两个因素的影响： (1)信道可靠性 (2)发送和接收能力 理想情况下，基于以下两个假定： 假定1：信道无差错,不丢失：无需检错重发 假定2：缓冲区无穷大：无需流量控制 此时无需任何协议 而在一般情况下，上述情况难以保证。 两机通过一条链路进行通信的

5、简化模型,4.3.2 具有最简单流量控制的数据链路层协议,现在去掉上述假定2，但假定1仍然保留。即主机A向主机B传输数据的信道仍然是无差错的理想信道。而缓冲区有限，此时只需要流量控制。 最简单流量控制的数据链路层协议： 在发送结点： (1) 从主机取一个数据帧； (2) 将数据帧送到数据链路层的发送缓存； (3) 将发送缓存中的数据帧发送出去； (4) 等待； (5) 若收到由接收结点发过来的信息(由收方控制发方的数据流量信息)，则从主机取一个新的数据帧，然后转到(2)； 在接收结点： (1) 等待； (2) 若收到由发送结点发过来的数据帧，则将其放入数据链路层的接收缓存； (3) 将接收缓存

6、中的数据帧上交主机； (4) 向发送结点发一信息，表示数据帧已经上交给主机； (5) 转到(1)；,现在去掉前面的两个假定，不仅要流量控制，还要进行差错控制 若接收方检测出错误，则发送一个否认帧NAK 发送方设置一个定时器，用来限定收到响应帧的时间,frame 0,NAK,Frame 0,ACK,Frame 1,frame 1,ACK,Frame 0,ACK,Frame 0,ACK,发送方,接收方,超时,超时,帧丢失,重发f(1),ACK丢失,重发f(0)， 接收方丢弃重复帧,数据帧出错,数据帧丢失,响应帧丢失,t,t,帧出错,重发f(0),4.3.3 等待协议差错处理,正常情况：据在传输中不

7、出差错。收方在收到一个正确的数据帧后,即交付给主机B,同时向主机A发送一个确认帧ACK(ACKnowledgement)。当主机A收到确认帧ACK后才能发送一个新的数据帧。这样就实现了收方对发方的流量控制。 数据帧错（但已接收）：数据帧在传输中出现了差错。通常在数据帧中加上了循环冗余检验CRC (Cyclic Redundancy Check)，结点B用硬件检验出收到的数据帧是否有差错。当发现差错时，结点B就向主机A发送一个否认帧NAK，以表示主机A应当重传出现差错的那个数据帧。 解决方案：重发 数据帧丢失：导致死锁 解决方案：超时重发 数据帧正确，但应答帧丢失，超时重发后，使得该数据帧再接收

8、方收到两次：重复帧 解决方案：使每个数据帧带上不同的发送序号，每发送一个新的帧就把它的发送序号加1，这样，若两个数据帧序号相同，则为重复帧，可丢弃一个。对于每次只发送一个帧的停止等待协议，可以只用两个不同的编号（1个比特）。,差错检测- 循环冗余检验（1）,差错检测主要有两种方法：奇偶校验(Parity Checking)和循环冗余检验CRC(Cyclic Redundancy Check)。 循环冗余检验CRC是一种最普遍最有效的检错码。用于ARQ协议。 基本原理：假设待传送的数据M (共kbit)。发送端在M的后面再添加供差错检测用的n bit冗余码一起发送, 这n bit冗余码称为帧检验

9、序列FCS (Frame Check Sequence)。把FCS加到数据块M的后面组成一个包含(k+n)bit的发送帧T,使得T能够用一个已知数P整除（P为（n+1)bit,是发送双方约定的）。若没有余数，则认为没有出错。 模2算法 设: M=1010001101（k=10bit） P = 110101(6bit) 求FCS: (1)2nM 由于P包含6位，所以n=5。把M左移5位2nM=101000110100000 (2)求FCS 把2nM 除以P ,得余数R =01110 即为FCS (3)组成发送帧T= 2nM +R=101000110101110 注：模2运算进行加法时不进位，减法

10、和加法一样。如，1111+1010=0101,差错检测- 循环冗余检验（2）,生成多项式 一种较方便的方法是用多项式来表示循环冗余检验过程，即使用多项式相应的系数来表示上述二进制数字中的1和0。 例如，可以用多项式P(X) = X5+X4+X2+1来表示上面的除数P（称为生成多项式）。因此，在接收端进行的运算就可以写为：,只要得出的余数Q不为0，就表示检测到了差错。 P的挑选 只要经过严格的挑选，并使用位数较多的除数P，那么出现检测不到的差错的概率就可以是个很小的数值。现在广泛使用的P(X)有： CRC-16 = X16+X15+X2+1 CRC-CCITT = X16+X12+X5+1 CR

11、C-32 = X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5 +X4+X2+X+1,4.3.4 停止等待协议的算法（1）,在发送结点： (1)从主机取一个数据帧； (2)V(S)0； /*发送状态变量初始化*/ (3)N(S)V(S)； /*将发送状态变量的数值写入发送序号*/ 将数据帧送交发送缓存； (4)将发送缓存中的数据帧发送出去； (5)设置超时计时器； /*选择适当的超时重传时间tout*/ (6)等待； /*等待以下3个事件中最先出现的一个*/ (7)若收到确认帧ACK，则从主机取一个新的数据帧； V(S)1V(S)； /*更新发送状态变量，变为下

12、一个序号*/ 转到 (3)； (8)若收到否认帧NAK，则转到(4)； /*重传数据帧*/ (9)若超时计时器时间到，则转到(4)； /*重传数据帧*/ 注：每发送一个数据帧，都必须将发送状态变量V(S)的值(0或1)写到数据帧的发送序号N(S)上。但只有收到一个确认帧ACK后，才更新发送状态变量V(S)一次(将1变成0或0变成1)并发送新的数据帧。,4.3.4 停止等待协议的算法（2）,在接收结点： (1)V(R)0；/*接收状态变量初始化,其数值等于欲接收的数据帧的发送序号*/ (2)等待； (3)当收到一个数据帧，就检查有无产生传输差错(如用CRC)； 若检查结果正确无误，则执行后续算法

13、； 否则转到(8)； (4)若N(S)= V(R)，则执行后续算法; /*收到发送序号正确的数据帧*/ 否则丢弃此数据帧，然后转到(7)； (5)将收到的数据帧中的数据部分送交主机； (6)V(R)1V(R)；/*更新接收状态变量，准备接收下一个数据帧*/ (7) 发送确认帧 ACK，并转到(2)； (8) 发送否认帧 NAK，并转到(2)； 注：(1)在接收端，每接收到一个数据帧，就要将发方在数据帧上设置的发送序号N(S) 与本地的接收状态变量V(R) 相比较。若二者相等就表明是新的数据帧，否则为重复帧。 (2) 在接收端，若收到一个重复帧，则丢弃之，且接收状态变量不变，但此时仍须向发送端发

14、送一个确认帧ACK。,停止等待协议工作过程,4.3.4 停止等待协议的算法（3）,由于发送端对出错的数据帧进行重传是自动进行的，所以这种差错控制体制常简称为ARQ (Automatic Repeat reQuest)，直译是自动重传请求，但意思是自动请求重传。 ARQ评价：简单易行；通信信道的利用率不高。,4.4 滑动窗口协议,滑动窗口是另外一种流量控制方法，发送方在受到确认之前可以连续发送若干帧。接收方只对其中若干帧进行确认. 滑动窗口协议：即使用一个ACK帧对多个数据帧进行确认。,滑动窗口,滑动窗口是指发送方和接收方都要创建额外的缓冲区。这个窗口可以在两端存取数据，它的大小（记为n）对确认

15、之前可以传输的帧的数目进行限制。 发送窗口,所能够发送的帧的范围区间，它代表了在未收到确认信息的情况下，发送端最多能发送多少个数据帧。 接收窗口，用来限制连续接收帧的个数，实现流量控制。 收发两端的窗口按照以上规律不断地向前滑动，因此这种协议称为滑动窗口协议。,滑动窗口（帧）的标号,窗口（帧）以模n+1的方式标号。 例如n=7，则帧编号是：0，1，2，3，4，5，6，7，0，1，2，3，4，5，6，7，0，1，2，3，4。 窗口的大小是7，也就是说，窗口大小不能覆盖所有的编号（8帧） 当接收方发送一个确认帧时，它就包含了一个预期接收的下一帧的编号。 比如发送了一个包含编号5的帧，表示到编号4为

16、止的所有数据帧都被正确接收了，希望发第5帧。,发送方窗口（帧）,随着数据的发送，窗口的左边界向右移动，窗口不断缩小，表示现在可以发送的帧变少。 一旦一个确认帧到来，窗口的右边界向右移动被确认帧的个数，窗口变大，即把新的可发送的帧纳入窗口。,接受方窗口（帧）,随着数据的到来，窗口的左边界向右移动，它的大小表示在必须发送确认帧之前还可以接收的帧的个数。 随着每个ACK帧的发出，接收窗口按新确认的帧的数量向右扩展相同数目的空位。,滑动窗口协议的示例,随着数据的到来，窗口的左边界向右移动，它的大小表示在必须发送确认帧之前还可以接收的帧的个数。 随着每个ACK帧的发出，接收窗口按新确认的帧的数量向右扩展

17、相同数目的空位。,4.4 .1 连续ARQ协议(Go-back-N ARQ),基本原理： 发送设备在发送出去的帧被确认之前保持它们的所有备份 在发送完一个数据帧后，不是象ARQ中那样等待应答帧后再发，而是可以连续发送若干个数据帧。 但接收端口只按顺序接收数据帧，一旦中间有一个帧出错，接收方可以发否定帧NAK,而且则在其后发送的帧要全部重发。 正确的数据可以隔若干个确认一次，但每个被破坏的帧必须被确认 和停止-等待ARQ类似，发送方有计时器，处理确认丢失的情况 当发送窗口和接收窗口大小都等于1时，就是ARQ协议。,frame 1,发送方,接收方,出错,7、8两帧被丢弃,frame 2,frame

18、 3,ACK 4,frame 4,frame 5,frame 6,frame 7,frame 8,ACK 9,frame 7,frame 6,frame 8,超时，重传6、7、8帧,发送方若收到对其中某一帧的否认帧，则从该帧开始的后续帧全部重发回退重传 若超时，则重发所有未确认帧,tout,4.4.2 Go-back-N ARQ的差错处理,优点： 连续发送提高了信道利用率和通信吞吐量 信道的延迟大，连续ARQ比ARQ效率要高。 缺点： 回退重传导致某些已正确接收的帧的重传，因此当信道错误率较高时，传输效率会急剧下降。这时连续ARQ协议不一定优于停止等待协议。 发送方需要有很大的缓冲区来保存未被

19、确认的帧，要为每一个未确认的帧都设置一个超时计数器，因此占用资源较多。 改进： 只重传出错的帧选择重传ARQ,Go-back-N ARQ协议的评价,4.4.3 选择重传ARQ协议,在连续ARQ中，一旦中间有一个帧出错，则在其后接收到的帧全部丢失，要发送端全部重发，为此的改进； 在选择重传ARQ中，接收端把后面接收到的数据帧暂存在接收端的缓存中，等待前面那个出错的数据帧重传后，再接收确认缓存中的数据，减少了重传的数据帧。,4.5 面向比特的链路控制规程HDLC,ARQ系列主要针对流量控制，同时保证数据传输的正确。那么如何能实现ARQ协议功能，如何在数据单元加上相应的控制信息以及建立、保持和释放连

20、接,这需要其他具体的链路层控制协议，如HDLC。 早期规定在链路上所传送的数据必须由一些规定的字符集组成(如ASCII码)，控制信息也只能用其中的几个来描述，这被称为面向字符的协议，缺点： 只对数据部分进行差错控制，可靠性差 依赖于字符集，不易扩展 70年代后，出现面向比特的协议 IBM SNA的 SDLC（同步数据链路控制 ） ANSI 的ADDCP（先进的数据通信控制规程） ISO 的HDLC （高级数据链路控制） CCITT的LAP（链路接入规程） X.25采用LAPB（链路接入规程 - 平衡型 ）,链路配置,概念： 主站：发送命令帧、数据信息帧和应答帧，负责控制链路 从站（次站）：接收命令帧，向主站发送响应帧，并配合主站 复合站（组合站）：同时具有主站和从站功能。 两种基本配置： 非平衡配置 点 - 点工作 多点工作 平衡配置 点 - 点工作,数据传送方式,对于非平衡配置： 正常响应方式(NRM)： 数据传输由主站发起，从站只能响应主站的轮询 异步响应方式(ARM)： 从站可以主动发送数据，但链路管理由主站负责 对于平衡配置： 异步平衡方式(ABM)： 任一复合站都可以发起数据传输,HDLC的帧结构,帧是数据链路层协议的数据单元，信息字段的头尾各加上24bit的控制信息，就构成了完整的