Chapter 4 数据链路层n4.1数据链路层的功能n4.2差错检测与校正n4.3基本数据链路协议n4.4滑动窗口（Slide Windows）协议n4.5面向位的协议HDLCn4.6 Internet中的数据链路层14.1数据链路层的功能n向网络层提供良好的服务接口n将物理层的比特流编成帧n差错检测24.1.1为网络层提供服务n无确认、无连接的服务n源端可以不需要建立连接就向目的端发送独立的数据帧，而目的端也不需要对收到的帧进行确认。n有确认、无连接的服务n源端可以不需要建立连接就向目的端发送独立的数据帧，但目的端需要对收到的帧进行确认。n面向连接的服务n源端与目的端在通信前要先建立连接，然后在此连接上互相传输数据帧，每一个帧都被编号，数据链路层保证传送的帧被对方收到，且只收到一次，双方通信完毕后拆除连接。3用OSI服务原语表示服务接口请求证实响应指示网络层数据链路层物理层时间发送方网络层接收方网络层服务提供者数据链路层请求证实响应指示44.1.2成帧(framing)n1.字符计数n每一个帧的头上描述帧的长度识别或表示一个帧的起始和结尾5 1 2 3 4 5 6 7 8 9 8 0 1 2 3 4 5 7第一帧第二帧第三帧缺点：帧头出错不光影响本数据帧，还影响后续的帧。54.1.2成帧(framing)n2.字符标志n在帧的起始和结尾用特殊的字符标志例如：用ASCII字符DLE STX表示帧的起始，DLE ETX表示结尾。识别或表示一个帧的起始和结尾在发送端检查数据中是否有DLE字样，如果有的话，就在它前面插入DLE，到接收端的链路层再将两个或两个以上的DLE，去掉一个DLE还原。674.1.2成帧(framing)n3.位标志n用特殊的位序列表示帧的起始和结尾例如，用01111110表示帧的起始和结尾识别或表示一个帧的起始和结尾为了避免起始、结尾标志与帧中的数据混淆，发送端的数据链路层在检测到数据比特流中有连续5个1出现时，就在其后加一个0，接收端的数据链路层在将5个1后面的0取走还原。894.1.2成帧(framing)n4.物理层编码n在物理层用1.5或2个物理位表示一个数据位来表示帧的起始与结尾。例如在物理层编码中，用 表示1，用 表示0则可用 ， 作为起始、结尾标志。识别或表示一个帧的起始和结尾104.1.3出错控制n在有确认的服务中，接收方需要对收到的数据帧进行确认，通常以返回特别控制帧来告诉发送方收到的数据有没有出错，也可以通过返回的数据帧中的某些位来捎带地进行确认。n如果发送的数据丢失，那么接收端是不可能进行确认的，怎么办呢？n在发送端引入计数器，进行超时重发。为了避免相同的帧收到多次，需要对帧进行编号。114.1.4流量控制n当发送端的发送速度大于接收端的接收速度，或发送端所在的网络传输速率大于接收端所在的网络传输速率时，就需要流量控制。n窗口机制n在任意时刻，发送方发出n帧，其中有l帧已得到确认。而同一时刻，接收方收到并应答了m帧，显然l=m = n，等待确认的帧的数目不允许超过W，即n-l =W，该W就是窗口。ll+WWn发送方mm+W接收方124.2差错检测与校正n信号在任何信道上传输都存在着传输差错，这些差错由多种物理现象引起，解决差错问题的方法有两种：n一种是在要发送的数据中加入一定的冗余位，使接收方能知道数据是否出错，但不知道是哪里出错，这种编码方法叫差错检测码，或简称检错码。n另一种是在要发送的数据中加入足够多的冗余位，使接收方能纠正出错的位，这种编码方法叫差错校正码，或简称纠错码。134.2.1纠错码n定义：一帧由m个数据位（即报文）和r个冗余位（即校验位）组成，设总长度为n（n=m+r)，此长度为n的单元常称为n位码字。n定义：两个码字不同的位的数目称为海明距离例如，10001001 与10110001它们的海明距离为3。n对于n位码字的集合，只有2m个码字是有效的，在任意两个有效码字间找出具有最小海明距离的两个码字，该海明距离便定义为全部码字的海明距离。14n一种编码的检错和纠错能力取决于编码后码字的海明距离的大小。n为了检测出d个比特的错，需要使用距离为d+1的编码。例如：数据后加奇偶校验位，编码后的海明距离为2，能检测1比特错。n为了纠正d个比特的错，必须用距离为2d+1的编码。例如有4个有效码字：它们是0000000000，0000011111，1111100000，1111111111，海明距离为5，能纠正2比特错。15纠正单比特错的校验位下界n设计一种编码，它有m个信息位和r个校验位，当r满足什么条件时，能纠正所有单比特错？ 对2m个有效码字的任何一个而言，有n个与该码字距离为1的无效码字，所以2m个有效码字每一个都对应有n+1个各不相同的位图，n位码字的总的位图是2n个。（n+1）2m=2n，n=m+r代入（m+r+1）2m=n+1 纠正单比特误码的校验位下界16海明编码n海明在1950年提出一种编码来纠正单比特错的编码。该编码是将码字内的位从左到右依次编号，编号为2的幂的位是校验位（如第1，2，4，8），其余为信息位。n每个校验位的取值应使得包括自己在内的一些集合服从规定的奇偶性。n集合的选取如下：n对编号为K的信息位来说，K可以分解成2的幂的和，如编号为11，11=1+2+8，即第11位由1，2，8校验位校验，它同时属于1，2，8所在的集合。17海明编码举例上例中，m=7，r=4，n=11，显然24=11+1，采用偶校验 3=1+2，5=1+46=2+4，7=1+2+49=1+8，10=2+811=1+2+8校验位：1（3，5，7，9，11） 2 （3，6，7，10，11） 4 （5，6，7） 8 （9，10，11）能纠正单比特错！在接收方，如果校验位1不满足偶校验，而其他校验位都满足，则第1位出错，184.2.2检错码n在实际通信中使用纠错码好还是检错码好呢？n例题：假设一个信道误码率是10-6，且出错是孤立产生的（即只有单比特错），数据块长度为1000比特，如果采用纠错编码，需要10个校验位（2101011），传送1M数据需要10000个校验位；如果采用检错编码，每个数据块只需一个奇偶校验位，传送1M数据只需1000个校验位和一个重传的数据1001位，共需要2001比特。n在多数通信中采用检错编码，但在单工信道中需要纠错编码。19改进的奇偶校验n对数据位组成一个L位宽，K位高的长方形距阵来发送，然后对每一列单独计算奇偶位，并附在最后一行作为冗余位。X X X X X XXX X X X X XXX X X X X XXX X X X X XXR R R R R R.R奇偶位K行L列检错率：1.该方法可以检测长度为L的突发性错误，但不能检测长度为L+1的突发性错误。2.假设L列中任意一列检测出错的概率为1/2，那么，整个数据块的错判率为（1/2）L 。该方法用在ICMP报头检验中。20多项式编码（循环冗余码CRC）nCRC（Cyclic Redundancy Check)nCRC编码的一般操作：给定一个m比特的帧或报文，发送方生成r比特的序列（也称为帧检验序列FCS，Frame Check Series），形成（m+r）的码字，该码字能被某个事先确定的数整除。接收方用相同的数去除收到的帧，如果无余数，则认为数据帧无差错。21CRC也称多项式编码n多项式表示：即将k比特的数据用k项多项式表示，它的各项为X k-1X0，它的系数为数据中对应位的0或1。n例如：110001可表示成X5+X4+122多项式编码的推导设数据帧多项式表示为M（X） m位序列 事先约定的除数为G（X） r+1位序列 帧检验序列FCS为F（X） r位序列加了检验序列的帧为T（X）=X r M（X）+F（X） m+r位序列设X r M（X）/G（X）=P（X）+R（X）/G（X）X r M（X）-R（X）/G（X）=P（X）在模2运算中，加法与减法等同，取F（X）=R（X）就能使T（X）被G（X）整除2324CRC的检错率n能检验出所有长度小于等于r的错误n如果突发长度为r+1，当且仅当差错与G（X）相同时才被整除。根据突发错误长度的定义，其第1位和最后1位必须是1，因此与G（X）完全相同的概率为（1/2）r-1。n对于长度大于r+1的差错，其错判率为1/2 r。25常用的多项式国际标准nCRC-12=X12+X11+X3+X2+X+1nCRC-16= X16 +X15 +X2 +1nCRC-CCITT= X16 +X15 +X5 +1nCRC-32=X32+X26+X23 +X22 +X16 +X12 +X11 +X10 +X8 +X7 +X5 +X4 +X2+X+1264.3基本数据链路协议n4.3.1一种无限制的单工协议（An Unrestricted Simplex Protocol）n4.3.2停-等协议（Stop-and-Wait Protocol）n4.3.3有噪音信道的停-等协议（Stop-and-Wait Protocol for a Noisy Channel）274.3.1一种无限制的单工协议n完全理想的条件：数据单向传输，收发双方的网络层一直处于就绪状态，处理时间可忽略不计，接收缓冲空间无限大，信道不会损坏或丢失帧。n发送端无限循环地重复三个动作：n从网络层取分组。n构造帧。n发出帧。无需任何差错控制和流量控制。n接收端也是无限循环地重复三个动作：n等待事件（唯一的未损坏帧的到达）发生。n帧到达后，从硬件缓冲中取出新到的帧。n将帧的数据部分传给网络层。无需做其它任何处理。284.3.2停-等协议n条件基本同协议1，只是接收缓冲只能存放一个帧且接收端需要一定的接收处理时间。n为了防止发送快于接收而造成数据丢失，发送端在发送一帧后必须停止发送，等待接收端发回的反馈确认短帧；接收端在收到一个帧并发送网络层后，需向发送端发一反馈确认短帧（不需包含任何信息，因为信道是无差错的），表示可发新帧。n由于需要反馈，且帧的发送和反馈是严格交替进行的，所以一般采用半双工信道。29有噪音信道所涉及的问题n进一步考虑实际的会出错的信道，帧既可能损坏（接收端可通过校验检查出错误），也可能完全丢失。n发送端仍通过接收端的反馈来决定怎么做。但由于帧会丢失，发送端可能收不到反馈的确认帧，因此发送端必须引入超时机制（time out），即增加一个定时计数器，在一定时间后对没有确认的帧进行重发，也称作ARQ（Automatic Retransmit reQuest）。n时间值应选择稍大于两倍端到端的信号传输时间和接收端的接收处理时间之和。n当接收端的反馈确认帧丢失时，必须通过为帧编制序号来解决重复帧的问题。n帧的序号位数应尽量的短从而少占用帧头的空间，在简单停-等协议中只需1个比特位（“0”“1”，“1”“0”）即可。这是由于在本协议中，发送端每发送一个帧都是建立在此帧之前的所有帧都已正确发送的基础上，只需区分相邻的两个连续帧即可避免重复的可能。304.3.3有噪音信道的停-等协议n收发双方都需维护各自的帧序号（sequence number）。发送端维护的帧序号N(S)表示当前所发帧的序号，接收端维护的帧序号N(R)表示接收端当前所期待接收的帧序号。发送端从网络层取得第一个分组进行组帧，将N(S)=0的序号放入帧头中作为第一个帧，通过物理层的发送缓存器发送出去，并启动定时计数器，然后停下来等待其响应帧。n接收端收到一个帧后，对其序号和N(R)进行比较：n若不等，则将其作为重复帧而丢弃；n若相等则对其接收，经校验正确并送交网络层后，将N(R)加1（模2运算）并放入确认帧中反馈回发送端；若校验出错，则丢弃出错的帧，保持N(R)的值不变并放入确认帧中反馈回发送端。n发送端若在规定的时间内没有收到接收端的反馈确认帧（超时），就认为数据帧丢失，在保持N(S)不变的情况下重新发送缓冲器中的（旧）帧；若接收到确认帧后，比较确认帧中的序号和N(S)：n若相等，则保持N(S)不变，重新发送缓冲器中的（旧）帧；n若不等，则将确认帧中的序号赋予N(S)，从网络层获取新的分组并组成新帧（N(S)作为序号放入帧头中）交由物理层发送出去。发送端每发送一帧，都会重新启动定时计数器，然后停下来等待其响应帧。31停-等协议对信道利用率的影响n在时延大的信道（如卫星通信）中，停-等协议的效率是很低的。n考虑两个地面站通过卫星通信，典型的传输时间约为270ms。假设一个帧的发送时间为20ms，则从发送站开始发送算起，经20ms+ 270ms=290ms，数据帧才能到达目的站。假设不考虑目的站的处理时间，且认为确认帧非常短，其发送时间可忽略不计，则又需270ms确认帧才能被发送站收到。因此信道的利用率为：20ms/(290ms+270ms)=1/28，非常低。这是由于每发一个帧之前都必须等待前一个帧的确认帧所造成的。n为了提高传输效率，可以设想让发送站连续不断地发送数据帧，当发完第28个帧数据后，恰好第1帧的确认帧到达，根据确认可紧接着发第29帧或重发第1帧。以后，每过20ms（发一个帧）就有一个确认帧到达，这样信道的利用率就大大地提高了。n允许发送站连续发送多个帧而不需等待确认的做法称作管道化（pipelining），属于一种窗口（windows）机制。324.4滑动窗口（Slide Windows）协议n滑动窗口协议是一种非常可靠、适用于各种条件的通用流量控制协议，特别是在效率、复杂性及对缓冲区的需求等方面可作灵活调配。n主要的滑动窗口协议有出错全部重发协议和选择重发协议两种。n实际上，有噪音信道的停-等协议就是滑动窗口协议的一个特例，将停-等协议中的帧序号从1位扩展到n位（范围为02n-1），收发双方维护的序号也变为一组序号表，分别称作发送窗口（sending window）和接收窗口（receiving window）。33发送窗口n发送窗口就是发送端允许不等确认而连续发送的帧的序号表。n允许连续发送的帧的数量称为发送窗口尺寸，表示为W。发送端必须有W个输出缓冲区来存放W个数据帧的副本以备数据帧的重发。n当发送端收到发送窗口下沿帧的肯定确认时，将发送窗口整体向前滑动一个序号，并从输出缓冲区中将相应的数据帧副本删除。ll+WWj发送方34接收窗口n接收窗口是接收端允许接收的帧的序号表。n允许接收的帧的数量称为接收窗口尺寸。同样接收端也必须设置相应数量的输入缓冲区来支持接收窗口。n对接收端收到的帧的序号落在接收窗口外的帧被直接丢弃。只有落在接收窗口内的帧才会被接收端进行校验处理，若校验正确：n当接收的帧不是接收窗口下沿帧时，必须暂存在输入缓冲区，不能交给网络层。n当接收到接收窗口下沿帧时，会将其连同后面连续的若干个检验过的正确帧按顺序交给网络层，在发回确认帧的同时将接收窗口向前滑动相应的数量。ll+Wi接收方W35滑动窗口示意图012345670123456701234567012345670123456701234567012345670123456701234567012345670123456701234567发送端发送端接收端接收端n帧的序号由3位组成（07），发送窗口和接收窗口的尺寸都为3。36停-等协议的窗口机制n帧的序号由1位组成（01），发送窗口和接收窗口的尺寸都为1。010101010101010101010101发送端发送端接收端接收端37数据的全双工传输n在实际通信中，通常收发双方都相互发送数据。n为了提高效率，可以将确认信息放在数据帧中作为一个控制字段连同数据一起发送给对方，这种方式称为捎带应答（piggybacking）。n当一方收到对方的数据帧后：n若正好也有数据需发给对方，则立即可使用捎带应答。n若暂时没有数据需发给对方或数据还未准备好，则等待一定的时间，如果在该时间内准备好了数据，则可以使用捎带应答。如果未准备好，为了防止对方等待时间过长而超时重发，必须立即发送一个单独的确认帧。n使用捎带应答就不可能对每一个帧都作确认，可以用对某一个帧的确认来代替对该帧之前的所有帧的确认。38出错全部重发协议（go-back-n）n出错全部重发协议中，发送窗口的尺寸是大于1，而接收窗口的尺寸则等于1。n由于接收窗口的尺寸为1，接收端只能按顺序地接受数据帧，一旦某个帧出错或丢失，只能简单地丢弃该帧及其所有的后续帧（因为发送窗口的尺寸是大于1的），不作任何确认。发送端超时后需重发出错或丢失的帧及其后续所有的帧。n发送端需要为每个待确认的帧都各自设置一个定时计数器。n发送窗口的尺寸不能超过2n-1(这里的n为序号的编码位数)，否则会造成接收端无法分辨新、旧数据帧。n出错全部重发协议只要求发送端保持一定数量的缓存来保存没有确认的数据帧，对接收端没有缓存的要求。但在误码率高的情况下，会大大降低信道的利用率。39选择重发协议（selective repeat）n选择重发协议中，发送和接收窗口的尺寸都大于1。n由于接收窗口的尺寸大于1，接收端可存储坏帧之后的其它数据帧（落在接收窗口），接收端对错帧发否定确认帧，因此发送端只需重发出错的帧，而不需重发其后的所有后续帧。n接收端正确收到重发的帧后，可对其后连续的已接收的正确帧作一次总体确认（最大序号的确认），并交送网络层。大大提高了信道的利用率。n接收窗口的尺寸不能超过2n-1（即序号范围的1/2），否则可能造成帧的重叠。n发送窗口的尺寸一般和接收窗口的尺寸相同，发送端为每一个输出缓存区设置一个定时计数器，定时器一旦超时，相应输出缓存区中的帧就被重发。40出错全部重发协议和选择重发协议41接收窗口的尺寸超过2n-1造成帧的重叠424.5面向位的协议HDLCn高级数据链路控制（High-Level Data Link Control）是由国际标准化组织制定的面向位的有序链路层协议。n是为非平衡的链路级操作而研制的，采用主从结构，链路上一个主站控制多个从站，主站向从站发命令，从站向主站返回响应。nHDLC中只有一个地址域，即从站的地址，在命令帧中，它是目的地址，在响应帧中，它是源地址。43HDLC的帧格式1.帧标志序列：01111110，作为起始和结束标志，在数据位有5个连续的1出现时，就插入1个0（位填充）2.地址段：在命令帧中表示目的地址，在响应帧中表示源地址，全1为广播地址，全0为测试地址443.控制字段用来表示帧的种类，执行信息传送，监控功能：信息帧（I：Information）：用来实现信息的传送，含有信息字段监控帧（S：Supervision）：帧中不包含信息字段，具有监控链路的作用，并能对收到的帧进行确认。无编号帧（U：Unnumbered）：对数据链路进行附加控制。I帧S帧U帧Seq：发送端发送序列编号，这里是3比特，采用模8循环编号。Next：表示发送端准备接收的序列号，也采用模8循环编号。Type：表示监控功能的类型。Modifier：附加的修改功能。P/F：在命令帧中作为询问比特，在响应帧中作为终止比特。454.6 Internet中的数据链路层464.6.1 SLIP（Serial Line IP)1.IP数据报用字符END（0XC0）定界。2.如果在IP数据中出现END字符（0XC0），就用2字节字符0Xdb，0Xdc代替。3.如果IP数据报中有字节为0Xdb，就用0Xdb，0Xdd代替。C0dbIP数据报dbdbC0C0dcdd问题：1.没有类型域，只能支持IP数据报 2.没有校验位。SLIP帧474.6.2 PPP(Point to Point Protocol)nPPP由以下3部分组成：n串形链路上的数据报封装方法n链路控制协议（LCP：Link Control Protocol），用来建立、配置、测试数据链路连接n对不同的网络层协议定义了网络控制协议族48PPP的帧格式nPPP与SLIP相比，有以下优点：n可在一条串形线上支持多种网络层协议n有CRC检错n用网络控制协议动态协商每一端的IP地址n链路控制协议协商多种数据链路选项。FLAG7EADDRFFCONTROL03PROTOCOLINFORMATION（=1500）CRCFLAG7E0021IP数据报C021链路控制数据8021网络控制数据49小结n熟悉数据链路层的基本功能，掌握常用的几种检错码和数据链路层协议。n习题：5，12，14，17，2050