数据链路层-计算机通信网ComputerNetwork

第3章数据链路层3.1数据链路层的功能3.2差错检测与校正3.3基本数据链路协议3.4滑动窗口（SlideWindows）协议3.5面向位的协议HDLC3.6Internet中的数据链路层3.1数据链路层的功能向网络层提供良好的服务接口将物理层的比特流编成帧差错检测流量控制RelationshipbetweenpacketsandframesServicesProvidedtoNetworkLayer(a)Virtualcommunication.(b)Actualcommunication.为网络层提供服务无确认、无连接的服务源端可以不需要建立连接就向目的端发送独立的数据帧，而目的端也不需要对收到的帧进行确认。有确认、无连接的服务源端可以不需要建立连接就向目的端发送独立的数据帧，但目的端需要对收到的帧进行确认。面向连接的服务源端与目的端在通信前要先建立连接，然后在此连接上互相传输数据帧，每一个帧都被编号，数据链路层保证传送的帧被对方收到，且只收到一次，双方通信完毕后拆除连接。Placementofthedatalinkprotocol成帧(framing)1.字符计数每一个帧的头上描述帧的长度识别或表示一个帧的起始和结尾缺点：帧头出错不光影响本数据帧，还影响后续的帧成帧(framing)2.字符标志在帧的起始和结尾用特殊的字符标志成帧(framing)3.位标志用特殊的位序列表示帧的起始和结尾例如，用01111110表示帧的起始和结尾为了避免起始、结尾标志与帧中的数据混淆，发送端的数据链路层在检测到数据比特流中有连续5个1出现时，就在其后加一个0，接收端的数据链路层在将5个1后面的0取走还原。Bitstuffing(a)Theoriginaldata.(b)Thedataastheyappearontheline.(c)Thedataastheyarestoredinreceiver’smemoryafterdestuffing.成帧(framing)4.物理层编码在物理层用1.5或2个物理位表示一个数据位来表示帧的起始与结尾。例如在物理层编码中，用表示1，用表示0则可用，作为起始、结尾标志。错误控制在有确认的服务中，接收方需要对收到的数据帧进行确认，通常以返回特别控制帧来告诉发送方收到的数据有没有出错，也可以通过返回的数据帧中的某些位来捎带地进行确认。如果发送的数据丢失，那么接收端是不可能进行确认的，怎么办呢？在发送端引入定时器，进行超时重发为了避免相同的帧收到多次，需要对帧进行编号流量控制当发送端的发送速度大于接收端的接收速度，或发送端所在的网络传输速率大于接收端所在的网络传输速率时，就需要流量控制。窗口机制在任意时刻，发送方发出n帧，其中有l帧已得到确认。而同一时刻，接收方收到并应答了m帧，显然l=m=n，等待确认的帧的数目不允许超过W，即n-l=W，该W就是窗口。ll+WWn发送方mm+W接收方3.2差错检测与校正信号在任何信道上传输都存在着传输差错，这些差错由多种物理现象引起，解决差错问题的方法有两种：在要发送的数据中加入一定的冗余位，使接收方能知道数据是否出错，但不知道是哪里出错，这种编码方法叫差错检测码，或简称检错码。在要发送的数据中加入足够多的冗余位，使接收方能纠正出错的位，这种编码方法叫差错校正码，或简称纠错码。纠错码一帧由m个数据位（即报文）和r个冗余位（即校验位）组成，设总长度为n（n=m+r)，此长度为n的单元常称为n位码字(codeword)。两个码字不同的位的数目称为海明距离例如，10001001与10110001它们的海明距离为3对于n位码字的集合，只有2m个码字是有效的，在任意两个有效码字间找出具有最小海明距离的两个码字，该海明距离便定义为全部码字的海明距离。一种编码的检错和纠错能力取决于编码后码字的海明距离的大小。为了检测出d个比特的错，需要使用距离为d+1的编码。例如：数据后加奇偶校验位，编码后的海明距离为2，能检测1比特错。为了纠正d个比特的错，必须用距离为2d+1的编码。例如有4个有效码字：它们是0000000000，0000011111，1111100000，1111111111，海明距离为5，能纠正2比特错。纠正单比特错的校验位下界设计一种编码，它有m个信息位和r个校验位，当r满足什么条件时，能纠正所有单比特错？对2m个有效码字的任何一个而言，有n个与该码字距离为1的无效码字，所以2m个有效码字中每一个都对应有n+1个各不相同的位模式，n位码字的总的位模式是2n个。（n+1）2m=2n，n=m+r代入（m+r+1）2m=2m+r2r=n+1纠正单比特误码的校验位下界海明编码海明在1950年提出一种编码来纠正单比特错的编码。该编码是将码字内的位从左到右依次编号，编号为2的幂的位是校验位（如第1，2，4，8…），其余为数据位。每个校验位的取值应使得包括自己在内的一些集合服从规定的奇偶性（如偶数个1）。集合的选取如下：对编号为K的信息位来说，K可以分解成2的幂的和，如编号为11，11=1+2+8，即第11位由1，2，8校验位校验，它同时属于1，2，8所在的集合。海明编码举例上例中，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位出错，…检错码在实际通信中使用纠错码好还是检错码好呢？例题：假设一个信道误码率是10-6，且出错是孤立产生的（即只有单比特错），数据块长度为1000比特，如果采用纠错编码，需要10个校验位（2101011），传送1M数据需要10000个校验位；如果采用检错编码，每个数据块只需一个奇偶校验位，传送1M数据只需1000个校验位和一个重传的数据1001位，共需要2001比特。在多数通信中采用检错编码，但在单工信道中需要纠错编码。改进的奇偶校验对数据位组成一个L位宽，K位高的长方形距阵来发送，然后对每一列单独计算奇偶位，并附在最后一行作为冗余位。XXXXXX……XXXXXXX……XXXXXXX……X……XXXXXX……XRRRRRR.….R奇偶位K行L列检错率：1.该方法可以检测长度为L的突发性错误，但不能检测长度为L+1的突发性错误。2.假设L列中任意一列检测出错的概率为1/2，那么，整个数据块的错判率为（1/2）L。该方法用在ICMP报头检验中。多项式编码（循环冗余码CRC）CRC（CyclicRedundancyCheck)CRC编码的一般操作：给定一个m比特的帧或报文，发送方生成r比特的序列（也称为帧检验序列FCS，FrameCheckSeries），形成（m+r）的码字，该码字能被某个事先确定的数整除。接收方用相同的数去除收到的帧，如果无余数，则认为数据帧无差错。CRC也称多项式编码多项式表示：即将k比特的数据用k项多项式表示，它的各项为Xk-1…X0，它的系数为数据中对应位的0或1。例如：110001可表示成X5+X4+1多项式编码的推导设数据帧多项式表示为M（X）m位序列事先约定的除数为G（X）r+1位序列帧检验序列FCS为F（X）r位序列加了检验序列的帧为T（X）=XrM（X）+F（X）m+r位序列设XrM（X）/G（X）=P（X）+R（X）/G（X）[XrM（X）-R（X）]/G（X）=P（X）在模2运算中，加法与减法等同，取F（X）=R（X）就能使T（X）被G（X）整除CRC的检错率能检验出所有长度小于等于r的错误如果突发长度为r+1，当且仅当差错与G（X）相同时才被整除。根据突发错误长度的定义，其第1位和最后1位必须是1，因此与G（X）完全相同的概率为（1/2）r-1。对于长度大于r+1的差错，其错判率为1/2r。常用的多项式国际标准CRC-12=X12+X11+X3+X2+X+1CRC-16=X16+X15+X2+1CRC-CCITT=X16+X15+X5+1CRC-32=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+13.3基本数据链路协议一种无限制的单工协议（AnUnrestrictedSimplexProtocol）停-等协议（ASimplexStop-and-WaitProtocol）有噪音信道的停-等协议（ASimplexProtocolforaNoisyChannel）ProtocolDefinitionsContinuedSomedefinitionsneededintheprotocolstofollow.Thesearelocatedinthefileprotocol.h.ProtocolDefinitions(ctd.)Somedefinitionsneededintheprotocolstofollow.Thesearelocatedinthefileprotocol.h.数据链路层协议的基本功能物理层数据链路层网络层比特流物理层数据链路层网络层发送方A接收方Bfrom_network_layerfrom_physical_layerto_network_layerto_physical_layerframe物理传输通道packetarrivalframearrival一种无限制的单工协议完全理想的条件：数据单向传输，收发双方的网络层一直处于就绪状态，处理时间可忽略不计，接收缓冲空间无限大，信道不会损坏或丢失帧。发送端无限循环地重复三个动作：从网络层取分组构造帧发出帧无需任何差错控制和流量控制接收端也是无限循环地重复三个动作：等待事件（唯一的未损坏帧的到达）发生帧到达后，从硬件缓冲中取出新到的帧将帧的数据部分传给网络层无需做其它任何处理UnrestrictedSimplexProtocol停-等协议条件基本同协议1，只是接收缓冲只能存放一个帧且接收端需要一定的接收处理时间。为了防止发送快于接收而造成数据丢失，发送端在发送一帧后必须停止发送，等待接收端发回的反馈确认短帧；接收端在收到一个帧并发送网络层后，需向发送端发一反馈确认短帧（不需包含任何信息，因为信道是无差错的），表示可发新帧。由于需要反馈，且帧的发送和反馈是严格交替进行的，所以一般采用半双工信道。SimplexStop-and-WaitProtocol有噪音信道所涉及的问题进一步考虑实际的会出错的信道，帧既可能损坏（接收端可通过校验检查出错误），也可能完全丢失。发送端仍通过接收端的反馈来决定怎么做。但由于帧会丢失，发送端可能收不到反馈的确认帧，因此发送端必须引入超时机制（timeout），即增加一个定时计数器，在一定时间后对没有确认的帧进行重发，也称作ARQ（AutomaticRetransmitreQuest）。时间值应选择稍大于两倍端到端的信号传输时间和接收端的接收处理时间之和。当接收端的反馈确认帧丢失时，必须通过为帧编制序号来解决重复帧的问题。帧的序号位数应尽量的短从而少占用帧头的空间，在简单停-等协议中只需1个比特位（“0”→“1”，“1”→“0”）即可。这是由于在本协议中，发送端每发送一个帧都是建立在此帧之前的所有帧都已正确发送的基础上，只需区分相邻的两个连续帧即可避免重复的可能。有噪音信道的停-等协议收发双方都需维护各自的帧序号（sequencenumber）。发送端维护的帧序号N(S)表示当前所发帧的序号，接收端维护的帧序号N(R)表示接收端当前所期待接收的帧序号。发送端从网络层取得第一个分组进行组帧，将N(S)=0的序号放入帧头中作为第一个帧，通过物理层的发送缓存器发送出去，并启动定时计数器，然后停下来等待其响应帧。接收端收到