第三章 数据链路层2005.doc

第三章 数据链路层3.1数据链路层的基本概念1、链路(物理链路link)一条点到点的物理线路段，中间没有任何交换结点。计算机之间的通路是由许多的链路串接而成的。2、数据链路(逻辑链路datalink)在物理链路上附加上实现数据传输所必须的通信规程（协议）。规程由硬件和软件实现。在数据链路上可以进行数据通信。采用复用技术时，一条链路上可以有多条数据链路。 3、功能 通过数据链路层协议(链路控制规程)，在不太可靠的物理链路上实现可靠的数据帧的传输。(1)链路管理 数据链路的建立、维持和释放。(2)帧同步 收方应当能从收到的比特流中准确地区分出一帧的开始和结束。 (3)流量控制 发送方发送数据的速率不能大于接收方的接收能力。当接收方来不及接收时，必须及时控制发方发送数据的速率。防止出现数据丢失或信道堵塞。(4)差错控制 包括差错的检测和纠正。如：正确的接收，出错重传等。采用编码技术： 前向纠错FEC：收方收到有差错的数据帧时，能够自动将差错改正过来。即收方发现差错，并自动纠正。开销较大，不适合于计算机通信。检错重发ARQ（自动反馈重发）：收方可以检测出收到的帧是否有差错，但不知道错在哪儿。通知发方重新发送该帧，直到收方正确收到为止。即收方发现差错，告知发方重发。计算机通信中常用。(5) 区分数据和控制信息 要传的数据和相关控制信息在同一帧中。(6)透明传输 任意位流组合的数据帧都能传输，不会引起接收方的误操作。如：如果所传帧的数据字段出现与某一控制字段组合一样的信息时，接收方能正确区分，不会引起误操作。帧开始帧结束数据011111100111111001111110(7)寻址 发送方发送的每一帧都能正确到达目的地，接收方知道是哪个站所发。3.2 停止等待协议 也叫应答式协议。基本思想：发送方发完一帧后，停止，等待对方回答。分几种讨论：一、理想情况：传输信道完全可靠，不出错不丢失；不管发方速率多快，收方都能接收，即接收速率与发送速率完全匹配。不需要数据链路层协议。二、信道无差错传输信道完全可靠，不出错不丢失；接收速率与发送速率不一定匹配，即收方可能来不及接收处理。需要进行简单流量控制。流量控制基本方法：由收方控制发方发送数据的速率或流量。即发方发完帧后，停止等待对方应答，根据应答决定如何操作。收发双方能够很好同步。计算机网络中常用。具体：发方发完一帧后，停止等待，收到对方应答后，再发送下一个数据帧。应答实际是“空帧”，无任何具体的内容，因为不会出错。三、信道有差错信道不完全可靠，有可能产生差错；接收速率与发送速率不一定匹配，即收方可能来不及接收处理。需要进行差错控制和流量控制。1、正常情况 数据在传输过程中不出差错，只需流量控制。由收方对发方进行流量控制。发方发完一帧后，停止，收到应答（确认ACK），再发下一帧。2、异常情况 数据帧在传输过程中出现了差错。（1） 数据帧出错接收方：通过差错检测(CRC循环容余码)发现数据帧有错误，回发一个否认帧NAK；发送方：重发出错的数据帧，直到收到确认帧ACK为止。如果重传多次都出现差错，超过一定次数（如16次），就停止发送，向上一层报告。图3-3(b)（2） 数据帧丢失接收方：收不到发来的数据帧，不发送任何应答帧；发送方：发方一直等待应答，出现“死锁”。超时重发：设置“超时定时器”，发方每发完一个数据帧，就启动定时（重发时间tout）。 重发时间tout内收到应答，发送新数据帧，定时“复位”；若超出重发时间tout未收到应答，就重传前面发送的数据帧。见图3-3(c)。重发时间tout略大于“从发完数据帧到收到应答帧所需的平均时间”。（3） 确认帧丢失接收方：收到正确帧，回发确认帧ACK，在传送中丢失；发送方：发方一直等待应答，出现“死锁”。采用“超时重发”，可避免“死锁”。见图3-3(d)存在问题：“超时重发”使收方收到两个同样的数据帧，即同一帧收到两次，出现了重复帧。给数据帧编号，即数据帧设序号字段：发送方：按序号发送，每发送一个新的数据帧“序号加1”；接收方：按序号接收，若收到两个序号相同的数据帧，出现重复帧，将该重复帧丢弃，并回发一个确认帧ACK。 序号位数适当选择。停止等待协议用一位，即“0”和“1”两种不同的序号，区分前后相邻的两帧。0、1、0、1、四、 停止等待协议流程V(S)：发送序号变量，发送新帧时，V(S)+1；N(S)：帧发送序号字段，当前传送帧的编号；V(R)：接收序号变量，当前准备接收的帧的序号，每收到一个新帧时，V(R)+1；判断重复帧：N(S)=V(R)，收到的是新数据帧；N(S) V(R)，收到的是重复帧。发送方：重 新 发 送NAKACKYYNNV(S)0从网络层取数装配成帧N(S)V(S)送物理层发送启动定时应答到超时取新数V(S)V(S)+1NAK/ACK接收方：出 错 帧 丢 弃重 复 帧 丢 弃NYYYYNNV(R)0接收帧取数送网络层等待帧正确帧N(S)=V(R)V(R)V(R)+1发ACK发NAK五、停等协议的信道利用率U成功传一帧所需的时间发送一帧的时间U = 设：帧长lf（bit），数据传输率（信道容量）C(bps)，传播时延tp，忽略接收处理时间tpr和确认帧ACK发送时间tatftpAB发送接收tprta发送一帧的时间：tf = lf /C成功传一帧所需的时间：tT = tf2tp 重传时间tout = 2tptf2tptfU =lf2tp Clf 例：某卫星信道容量为100kbps，帧长1000b，往返传播时延500ms1000+0.51051000U =511= 2%信道利用率很低。3.3 滑动窗口协议 停止等待协议简单、效率低。采用滑动窗口协议。 基本思想：发送方连续发送多个数据帧，再停下来等待接收方应答：收到确认帧ACK，接着继续发送多个数据帧；收到否认帧NAK或未收到应答，进行重发： 从出错帧开始重发-连续ARQ协议； 只重发出错帧-选择ARQ协议减少等待时间，信道利用率提高。一、 连续ARQ协议工作原理： 发送方：连发多个数据帧，每个帧一个定时，停止等待：收到确认帧ACK，继续发送后面帧；超时，未收到应答，从出错帧开始重发接收方：按序号接收数据帧，差错检测：正确：接收处理，发确认帧ACK；出错：将该帧及后面帧均丢弃回发否认帧NAK；不发任何应答；（常用） 如图3-6。出错重传时，要先回退n个帧，再开始重传，又称为Go-back-N ARQ。说明： 连续发送帧数并不是越多越好 未被确认的数据帧太多，一旦出现出错帧，就要重传很多的数据帧，降低效率； 连发帧数多，发送序号占用位数多，增加额外开销。采用滑动窗口技术，对连续发送的数据帧数加以限制。通过在发送端和接收端分别设定发送窗口和接收窗口来控制。1、发送窗口对发送端进行流量控制，即控制连发的个数。p56发送窗口大小（尺寸）WT ：发方在收到应答前最多可连续发送数据帧的个数。WT 1。实际是允许连续发送的序号表，只有落在发送窗口所含序号之内的，才能不等待应答发送。发送窗口的滑动过程：如图3-7设发送序号字段3位（0#7#），WT = 5（1）发送窗口内的帧允许发送，窗口外帧不允许发送，图(a)；（2）每发完一帧，允许发送的帧数就减1，但发送窗口的位置不变，图(b)；（3）允许发送的帧都发完，还没收到确认，不能再发送。图(c)（4）每收到一个帧的确认，发送窗口就向前(向右)滑动一个序号，图(d)。2、接收窗口对帧的接收进行控制，即控制哪些帧可以接收，哪些不可以接收。接收窗口的大小（尺寸）WR：规定收方允许接收的帧数。WR = 1，即按序接收。实际是允许连续接收的序号表，要判断序号：收到的数据帧的发送序号落在接收窗口内，接收并处理；否则，将其丢弃。收方应答方法：立即发：一个帧一个应答，窗口向前移动一个序号；不立即发：几个帧一个应答，窗口向前移动几个序号，表示最后一个数据帧及其以前的数据帧均已正确地收到。接收窗口滑动过程：如图3-8。（1）只有当收到的帧的序号与接收窗口一致时才能接收该帧。否则，就丢弃；（2）每收到一个序号正确的帧，接收窗口就向前(向右)滑动一个序号，同时向发送端发送对该帧的确认。3、发送与接收窗口关系只在接收窗口向前移动时，发送窗口才有可能向前移动。收发两端的窗口随着发送和接受的进行不断向前滑动。有许多帧在信道上象“流水线”一个一个传送，也叫流水线协议。停止等待协议：WT = WR = 1。4、发送窗口最大尺寸规则： 若序号位数n位，连续ARQ，发送窗口最大尺寸是 2n-1,而不是2n。反例说明：设序号3位，则序号空间为0#7#（共8个）（1） WT = 8 j发方发送0#7#共8帧，停止等待应答； k收方全部正确收到，分别发应答，窗口序号变为0#（准备收0#帧）； 应答全部到达：发方接着发送8个新帧0#7#，协议正确进行； 应答全部丢失：发方超时，重新发送8个旧帧0#7#， 收方出现重复帧接收，协议错误。发送方： 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 接收方： 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 h(2) WT = 7 j 发方发送0#6#共7帧，停止等待应答； k 收方全部正确收到，分别发应答，窗口序号变为7#（准备收7#帧）；应答全部到达：发方接着发送7个新帧7#、0#5#，协议正确进行；应答全部丢失：发方超时，重新发送7个旧帧0#6#，与收方准备接收的帧序号不相同，拒绝接收，丢弃。发送方： 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 接收方： 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 h5、缓存区管理实现时，收、发双方都设适当的缓存区保存已发送或接收的帧。缓存数量应和窗口尺寸相同，即分别为WT和WR。WT发完后送入收到确认后移走43210（1）发送方：已发送出去、尚未被确认的数据帧都保存在发送缓冲区中，以便出错重发。采用“先进先出”的方式。 发送端每发完一个新的数据帧就将该帧存入这个队列。当队列长度达到发送窗口大小WT 时，即停止发送新的数据帧。 重发时，队列不发生变化。只有当收到对应于队首的帧的确认时，才将队首的数据帧清除。队列变空，表明全部已发出的数据帧均已得到了确认。（2）接收方：收到一个帧，判断正确：数据交上层，缓存“空”，发应答；错误：丢弃缓存数量多，占用的内存空间就大。停止等待协议，收、发缓存区数量均为1。二、选择重传ARQ协议 连续ARQ，出错时，要重发出错及其后各帧，影响效率。可进一步改进：只重传出错的数据帧或者是定时器超时的数据帧。1、工作原理： 发送方：连发多个数据帧，每个帧启动一个定时，停止等待：收到确认帧ACK，继续发送后面帧；超时，未收到应答，只重发出错帧接收方：不按序号接收数据帧，差错检测：正确：接收、保存在缓存区，发确认帧ACK；出错：丢弃该帧当帧全部正确收到后，按顺序一起交主机。说明：接收窗口尺寸WR 1，即只要序号落在接收窗口内的正确帧都可接收，不一定按顺序接收。不按序接收。2、窗口最大尺寸规则：若序号位数n位，选择重传ARQ，发送窗口和接收窗口尺寸最大是2n-1，不是2n-1。即序号空间一半。 反例说明：设序号3位，则序号空间为0#7#。（1）WT= WR =7 j发方发送0#6#共7帧，停止等待应答； k收方全部正确收到，发应答，窗口滑动，允许接收7#、0#5#帧； 应答全部到达：发方发送7个新帧7#、0#5#，协议正确进行；应答全部丢失：发方超时，重新发送0#6#共7帧，与准备接收序号重叠，出现重复帧接收，协议错误。发送方： 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 接收方： 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 h（2）WT= WR =4 j发方发送0#3#共4帧，停止等待应答； k收方全部正确收到，发应答，窗口滑动，允许接收4#7#帧； 应答全部到达：发方发送4个新帧4#7#，协议正确进行； 应答全部丢失：发方超时，重新发送4个旧帧0#3#，序号不在接收窗口内，拒绝接收，丢弃；发送方： 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 接收方： 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 h3、缓存区管理发送和接收存放缓存区个数分别为窗口尺寸大小，WT 和WR。三、三种协议比较停等协议连续ARQ选择重传ARQ发送方发一帧重发出错帧连发n帧从出错帧开始重发连发n帧只重发出错帧接收方按序号接收出错帧、重复帧丢弃按序号接收从出错帧开始丢弃不按序号接收只丢弃出错帧窗口大小WT = WR = 11 WT 2n-1WR = 11 WT、WR 2n-1 3.4 差错控制技术采取有效措施发现信息传输中的差错，并加以纠正，提高信息传输的质量。常用的方法是采用差错控制编码。基本思想：对所传输的信息进行抗干扰编码，以此来检测和校正传输中的错误。发送方：将要发送的信息按一定规则附加上若干位冗余码一起发送。编码接收方：收到后，按相应规则检查信息与冗余码的关系，以发现是否出现差错。 解码差错控制编码类型：检错码：能自动发现差错； ARQ纠错码：不仅能发现差错、而且能自动纠正差错。 FEC一、奇偶校验码：是一种检错码，最简单、最常用。发送方：发送的信息后面附加校验位，使其“1”的个数是奇数（奇校验）或偶数（偶校验）；接收方：检测“1”的个数是否与发送方相符，来判断传送是否出错。1、垂直奇偶校验将要发送的信息分为若干组（n组，每组长度相同m位），每组垂直排列，在每组后面产生一个奇偶校验位。传输时，按列的顺序串行发送：第1列、第2列、第n列。例：发送一串信息 10111 11110 01000 10001 11000将其5位一组划分5组，采用偶校验。1 1 0 1 10 1 1 0 11 1 0 0 01 1 0 0 01 0 0 1 00 0 1 0 0 校验位第 第 第 第 第1 2 3 4 5 列 列 列 列 列发送结果：101110111100010001100010110000通常，取一个字符的长度来分组。如：7位一组划分。特点：能检测出每列中的奇数位错误，测不出偶数位错误。2、水平奇偶校验将要发送的信息分为若干组（n组，每组长度相同m位），每组垂直排列，对每组相应位横向编码，在每行后面产生一个奇偶校验位。传输时，按列的顺序串行发送：第1列、第2列、第n+1列。例：发送一串信息10111 11110 01000 10001 11000将其5位一组划分5组，采用偶校验。1 1 0 1 1 00 1 1 0 1 11 1 0 0 0 01 1 0 0 0 01 0 0 1 0 0 第 第 第 第 第1 2 3 4 5 列 列 列 列 列校验位发送结果：101111111001000100011100001000特点：能检测出每行中的奇数位错误，以及突发长度m位的所有突发错误；不能边产生校验位边发送，必须等要发信息到齐后，才产生校验位，接收方必须等全部信息都接收后，才能开始校验。3、垂直水平奇偶校验（方阵码奇偶校验）同时进行水平和垂直两个方向的奇偶校验。例：发送一串信息10111 11110 01000 10001 11000将其5位一组划分5组，采用偶校验。1 1 0 1 1 00 1 1 0 1 11 1 0 0 0 01 1 0 0 0 01 0 0 1 0 00 0 1 0 0 1 第 第 第 第 第1 2 3 4 5 列 列 列 列 列校验位校验位发送结果：101110111100010001100010110000010001特点：能检测出所有3位或3位以下的错误，奇数位错误、突发长度m位的突发错误，以及部分偶数位错误；能纠正部分差错。如：只有一位错误，可确定在某行和某列的交叉处，并纠正。二、CRC循环冗余码（多项式码） p50奇偶校验简单，但漏检率高。CRC循环冗余码是一种在计算机网络和数据通信中广泛使用的检错码。检错能力很强，只需用一个简单的电路即可实现。1、基本思想将要传的信息位串后面附加上校验位串，构成CRC码，一起传送。设：信息位串Mmk-1 m1 m0 (k位) 校验位串Rrn-1 r1 r0 (n位)CRC码：mk-1 m1 m0 rn-1 r1 r0 (k + n位)即2nM+R2、校验位串产生将信息位串变换除以事先给定的位串余数位串为校验位串事先给定的位串：生成多项式位串Ppn p1 p0 (n+1位)信息位串变换：在原串后加n个“0”，2nM除法进行“模2运算”：加法无进位、减法无借位。余数位串：Rrn-1 r1 r0 (n位)也叫“帧校验序列FCS”3、错误检测接收方将收到的CRC码，除以同一生成多项式余数为0：正确，去掉尾部n位，得所需信息；否则，出错4、特点能检测出所有奇数位错、 所有长度FCS长度的突发错、单位错、双位错等。关键是生成多项式应选择合适。常用的生成多项式CRC-16=X16+ X15+ X2+1CRC-CCITT=X16+ X12+ X5+1CRC-32= X32+ X26+ X23+ X16+ X12+ X11+ X10+X8+ X7+ X5+ X4+ X2+ X+1通常，16位CRC码用于广域网的通信协议；32位CRC码用于局域网的通信协议。例：要传信息位串1010001101，生成多项式P(x)= X5+ X4+ X2+1（110101）。信息位串变换后：101000110100000CRC码：1010001101011103.5 面向比特的链路控制规程HDLC本节介绍一些实际的数据链路控制协议。多种，可分两类：一、面向字符：链路上传送的是由字符组成的报文。20世纪60年代初开始发展，典型代表是IBM公司的BSC规程(BISYNC，二进制同步通信协议)。通过定义一些特殊字符进行传输控制。传送的报文分为两种：数据报文：传输数据控制报文：传输控制信息主要缺陷：(1)线路利用率低：采用停止等待协议，收发双方交替地工作；(2)兼容性差：所有通信设备必须使用同样字符代码；(3)可靠性较差：只对数据部分进行差错控制，控制部分未控制；(4)不易扩展：增加一种功能需要设定一个新的控制字符。二、面向比特： 链路上传送的是由比特流组成的帧。20世纪70年代初，IBM公司最先提出了一个面向比特的规程SDLC（同步数据链路控制规程）。ISO修改后作为国际标准，称为HDLC(高级数据链路控制)。CCITT将HDLC进一步修改，作为X.25建议书的数据链路层协议的一部分，最后版本为LAPB（平衡式链路访问规程）。HDLC特点：高效率、高可靠性、能传输任意代码，应用广泛，如：X.25、帧中继广域网及IEEE802局域网等。1、基本概念HDLC可适用于不同的链路配置和传送模式。（1）站类型主站：控制整个链路的工作。包括链路初始化、数据传送的组织、差错检测和恢复等。 主站发出的帧叫做命令，要求次站完成某些特定操作。次站（从站）：受主站控制的站，只完成主站指示的操作。 次站发出的帧叫做响应，对主站命令的回答（接收或拒绝）。复合站：同时具有主站与次站的功能。每个复合站都可以发出命令和响应。（2）基本链路配置非平衡配置：点点结构：一个主站，一个次站命令响应主站次站多点结构：一个主站，多个次站响应响应命令主站次站次站平衡配置： 点点结构：链路两端的两个站都是复合站。复合站复合站（3）操作模式非平衡配置： 正常响应方式NRM：主站才能发起数据传输，次站只有在主站向它探询(poll)时，才能传输响应帧。异步响应方式ARM：次站可不经探询主动发送响应帧。平衡配置：异步平衡方式ABM：每个复合站都可以平等地发起数据传输。2、HDLC的帧格式 HDLC采用同步传输方式，传送单位是帧，是数据链路层的协议数据单元PDU。 8 8n 8,16 可变 16 8标志F地址A控制C信息INFO帧校验序列FCS标志F（1） 标志F ：8位，用“01111110”表示。标志每一帧的开始和结束，并进行同步。透明传输：为避免在其他字段中出现和该标志一样的比特组合时，可能造成接收的误控（误认为是帧的边界）。采用“零比特填充法（零比特插入和删除）”。规则：发送端：在发送A、C、Info和FCS字段时，如果出现连续5个 “1”，则立即在其后填入一个“0”。使这些字段不会出现连续6个 “1”。接收端：先确定帧的开始，继续接收后面字段，若出现连续5个“1”，判其后一位：“0”：发送时插入，需删除；“1”：再查下一位：w“0”：结束标志； w“1”：错，不可能出现连续7个“1”。由收、发方硬件自动完成。(2) 地址A：基本长度8位，必要时可扩展。全1：广播地址；全0：无效地址。不扩展：8位地址，有效地址254个；地址扩展：以8位（字节）为单位扩展，以字节的第一位做扩展标志，其余7位为地址位。第1位为“0”时：下一个字节也是地址；第l位为“1”时：该字节是最后一个地址字节0地址0地址1地址（3）控制字段C：监视和控制链路，表示命令和响应的类别、功能及帧类型（信息帧I、监督帧S和无编号帧U）。1 2 3 4 5 6 7 8 0N(S)P/FN(R)10S SP/FN(R)11M MP/FM M M信息帧I监督帧S无编号帧U基本格式：8位。扩展格式：16位，将序号扩展到7位。1 2 8 9 10 160N(S)P/FN(R)10S S x x x xP/FN(R)11M M 0 MM MP/Fx x x x x x x 信息帧I监督帧S无编号帧U（4）信息Info：存放要传送的数据，上层网络层传来数据，长度可变。（5）帧校验序列FCS：16bit。用于差错检测，采用CRC循环冗余码校验，生成多项式是CRC-CCITT。校验范围：A、C、Info。3、帧类型（1）信息帧I传数据。为保证正确发送和接收，给帧编号。发送序号N(S)：表示当前发送的信息帧的序号；接收序号N(R)：表示N(R)之前的帧都正确收到，准备接收第N(R)帧。“捎带应答”：在双向通信中，通过N(R)，接收方不需要专门为收到的每一个信息帧发送“确认应答帧”。可以在该站有信息帧回发时，将确认信息放在其接收序号N(R)中与信息帧一起传送，作为对已收到的几个正确帧的“捎带应答”，提高信道利用率。例如：连续收到4个信息帧后，回发信息帧并“捎带应答”。I，4，1I，0，4I，0，0I，1，0I，2，0I，3，0信息帧：I，N(S)，N(R)P/F (探询Poll/最后Final) 位：主站发出：该位为“1”（P=1），表示要求次站响应；次站发出：该位为“1”（F=1），表示是次站本次发出的最后一个帧。（2）监督帧S链路的控制功能。只作为应答使用，只有N(R)，无数据和N(S) 字段，监督帧总长48位。流量控制3、4位帧名功能0 0RR接收准备好肯定回答，准备接收N(R)及以后各帧，N(R)-1及其以前的各帧均正确收到1 0RNR接收未准备好收方暂停接收后面帧，N(R)-1及其以前的各帧均正确收到0 1REJ拒绝出错，从N(R)开始重发，N(R)-1及其以前的各帧均正确收到1 1SREJ选择拒绝出错，只重发N(R) 帧，N(R)-1及其以前的各帧均正确收到(3)无编号帧U附加的链路控制功能。无N(S)和N(R)，用来传送命令和控制信息。常用15种无编号帧，用第34678（5位）编码表示。如：设置正常响应模式SNRM(00001)；拆除连接DISC(00010)3、通信过程 三阶段：建立数据链路、数据传送、释放数据链路如：主站A与次站B通信，以正常响应方式工作。（1）建立数据链路：通过交换无编号帧，设置双方通信模式。 如：主站A向次站B发出SNRM命令，B站同意建立链路，发送无编号确认UA响应。（2）数据传输：通过信息帧I发送数据、监控