计算机网络第四章.pdf

1Chapter 4 数据链路层4.1数据链路层的功能4.2差错检测与校正4.3基本数据链路协议4.4滑动窗口（Slide Windows）协议4.5面向位的协议HDLC4.6Internet中的数据链路层24.1数据链路层的功能向网络层提供良好的服务接口将物理层的比特流编成帧差错检测34.1.1为网络层提供服务无确认、无连接的服务源端可以不需要建立连接就向目的端发送独立的数据 帧，而目的端也不需要对收到的帧进行确认有确认、无连接的服务源端可以不需要建立连接就向目的端发送独立的数据 帧，但目的端需要对收到的帧进行确认面向连接的服务源端与目的端在通信前要先建立连接，然后在此连接 上互相传输数据帧，每一个帧都被编号，数据链路层 保证传送的帧被对方收到，且只收到一次，双方通信 完毕后拆除连接44.1.2成帧(framing)1.字符计数每一个帧的头上描述帧的长度识别或表示一个帧的起 始和结尾5 1 2 3 4 5 6 7 8 9 8 0 1 2 3 4 5 7第一帧第二帧第三帧缺点：帧头出错不光影响本数据帧，还影响后续的帧54.1.2成帧(framing)2.字符标志在帧的起始和结尾用特殊的字符标志 例如：用ASCII字符DLE STX表示帧的起始，DLE ETX表示结尾。

识别或表示一个帧的起 始和结尾在发送端检查数据中是否有DLE字样，如果有的话，就 在它前面插入DLE，到接收端的链路层再将两个或两个 以上的DLE，去掉一个DLE还原674.1.2成帧(framing)3.位标志用特殊的位序列表示帧的起始和结尾 例如，用01111110表示帧的起始和结尾识别或表示一个帧的起 始和结尾为了避免起始、结尾标志与帧中的数据混淆，发送端 的数据链路层在检测到数据比特流中有连续5个1出现 时，就在其后加一个0，接收端的数据链路层在将5个 1后面的0取走还原894.1.2成帧(framing)4.物理层编码在物理层用1.5或2个物理位表示一个数据位来 表示帧的起始与结尾例如在物理层编码中，用表示1，用表示0 则可用，作为起始、结尾标志识别或表示一个帧的起 始和结尾104.1.3出错控制在有确认的服务中，接收方需要对收到的数据 帧进行确认，通常以返回特别控制帧来告诉发 送方收到的数据有没有出错，也可以通过返回 的数据帧中的某些位来捎带地进行确认如果发送的数据丢失，那么接收端是不可能进 行确认的，怎么办呢？在发送端引入计数器，进行超时重发为了避免相 同的帧收到多次，需要对帧进行编号。

114.1.4流量控制当发送端的发送速度大于接收端的接收速度，或发送端所 在的网络传输速率大于接收端所在的网络传输速率时，就 需要流量控制窗口机制在任意时刻，发送方发出n帧，其中有l帧已得到确认 而同一时刻，接收方收到并应答了m帧，显然l=n+1纠正单比特误码的校验位下界16纠正单比特错的校验位下界设计一种编码，它有m个信息位和r个校验位，当r满足什么条件时，能 纠正所有单比特错？码字长度n=m+r, 总共有2n个种组合，其中有效码字数为2m每一个有效码字X，例如X=10101010有n个与其距离为1的无效码字00101010， 1110101010001010， 1011101010100010， 1010111010101000， 10101011对其某一位取反（n+1）2m=n+1 纠正单比特误码的校验位下界要纠正单比特错，需采 用距离至少为3的编码17海明编码海明在1950年提出一种编码来纠正单比特错的 编码该编码是将码字内的位从左到右依次编 号，编号为2的幂的位是校验位（如第1，2，4， 8…），其余为信息位每个校验位的取值应使得包括自己在内的一些 集合服从规定的奇偶性。

集合的选取如下：对编号为K的信息位来说，K可以分解成2的幂的和， 如编号为11，11=1+2+8，即第11位由1，2，8校 验位校验，它同时属于1，2，8所在的集合18海明编码举例上例中，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位出错，…194.2.2检错码在实际通信中使用纠错码好还是检错码好呢？例题：假设一个信道误码率是10-6，且出错是孤立 产生的（即只有单比特错），数据块长度为1000 比特，如果采用纠错编码，需要10个校验位 （210>1011），传送1M数据需要10000个校验位； 如果采用检错编码，每个数据块只需一个奇偶校 验位，传送1M数据只需1000个校验位和一个重传 的数据1001位，共需要2001比特在多数通信中采用检错编码，但在单工信道中需 要纠错编码20改进的奇偶校验对数据位组成一个L位宽，K位高的长方形距阵来发送，然后对每 一列单独计算奇偶位，并附在最后一行作为冗余位。

X X X X X X……XX X X X X X……XX X X X X X……X……X X X X X X……XR R R R R R.….R奇偶位K行L列 检错率：1.该方法可以检测长度为L的突发性错误，但不 能检测长度为L+1的突发性错误2.假设L列中任意一列检测出错的概率为1/2，那 么，整个数据块的错判率为（1/2）L 该方法用在ICMP报头检验中21多项式编码（循环冗余码CRC）CRC（Cyclic Redundancy Check)CRC编码的一般操作：给定一个m比特的 帧或报文，发送方生成r比特的序列（也 称为帧检验序列FCS，Frame Check Series），形成（m+r）的码字，该码字 能被某个事先确定的数整除接收方用 相同的数去除收到的帧，如果无余数， 则认为数据帧无差错22CRC也称多项式编码多项式表示：即将k比特的数据用k项多 项式表示，它的各项为X k-1…X0，它的系 数为数据中对应位的0或1例如：110001可表示成X5+X4+123多项式编码的推导设数据帧多项式表示为M（X）m位序列事先约定的除数为G（X）r+1位序列 帧检验序列FCS为F（X）r位序列加了检验序列的帧为T（X）=Xr M（X）+F（X） m+r位序列设Xr M（X）/G（X）=P（X）+R（X）/G（X）[Xr M（X）-R（X）]/G（X）=P（X）在模2运算中，加法与减法等同，取F（X）=R（X） 就能使T（X）被G（X）整除2425CRC的检错率能检验出所有长度小于等于r的错误如果突发长度为r+1，当且仅当差错与G（X） 相同时才被整除。

根据突发错误长度的定义， 其第1位和最后1位必须是1，因此与G（X）完 全相同的概率为（1/2）r-1对于长度大于r+1的差错，其错判率为1/2 r26常用的多项式国际标准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+1274.3基本数据链路协议4.3.1一种无限制的单工协议（An Unrestricted Simplex Protocol）4.3.2停-等协议（Stop-and-Wait Protocol）4.3.3有噪音信道的停-等协议（Stop-and- Wait Protocol for a Noisy Channel）284.3.1一种无限制的单工协议完全理想的条件：数据单向传输，收发双方的网络层一直处于就绪状态，处理时间可忽略不计，接收缓冲空间无限大（无需任何流量控 制）信道不会损坏或丢失帧（无需任何差错控制）发送端无限循环地重复三个动作：从网络层取分组。

构造帧发出帧接收端也是无限循环地重复三个动作：等待事件（唯一的未损坏帧的到达）发生帧到达后，从硬件缓冲中取出新到的帧将帧的数据部分传给网络层只需成帧处理，无需做其它任何处理294.3.2停-等协议条件基本同协议1，修改：接收端需要一定的接收处理时间，接 收缓冲只能存放一个帧为了防止发送快于接收而造成数据丢失， 发送端在发送一帧后必须停止发送，等 待接收端发回的反馈确认短帧；接收端 在收到一个帧并发送网络层后，需向发 送端发一反馈确认短帧（不需包含任何 信息，因为信道是无差错的），表示可 发新帧由于需要反馈，且帧的发送和反馈是严 格交替进行的，所以一般采用半双工信 道DATAABDATA传播延时处理延时重传时间tout传播延时30有噪音信道所涉及的问题进一步考虑实际的会出错的信道，帧既可能损坏（接收端可通过校验检查 出错误），也可能完全丢失发送端仍通过接收端的反馈来决定怎么做但由于帧会丢失，发送端可能 收不到反馈的确认帧，因此发送端必须引入超时机制（time out），即增加 一个定时计数器，在一定时间后对没有确认的帧进行重发，也称作ARQ （Automatic Retransmit reQuest）。

时间值应选择稍大于两倍端到端的信号传输时间和接收端的接收处理时间之和当接收端的反馈确认帧丢失时，必须通过为帧编制序号来解决重复帧的问 题帧的序号位数应尽量的短从而少占用帧头的空间，在简单停-等协议中只需1个 比特位（“0”→“1”，“1”→“0”）即可这是由于在本协议中，发送端每发送一 个帧都是建立在此帧之前的所有帧都已正确发送的基础上，只需区分相邻的两 个连续帧即可避免重复的可能314.3.3有噪音信道的停-等协议收发双方都需维护各自的帧序号（sequence number）发 送端维护的帧序号N(S)表示当前所发帧的序号，接收端维护 的帧序号N(R)表示接收端当前所期待接收的帧序号发送端从网络层取得第一个分组进行组帧，将N(S)=0的序号 放入帧头中作为第一个帧，通过物理层的发送缓存器发送出 去，并启动定时计数器，然后停下来等待其响应帧接收端收到一个帧后，对其序号和N(R)进行比较：若相等则对其接收，经校验正确并送交网络层后，将N(R)加1 （模2运算）并放入确认帧中反馈回发送端；若校验出错，则丢 弃出错的帧，保持N(R)的值不变并放入确认帧中反馈回发送端若不等，则将其作为重复帧而丢弃；N（R）值不变，反馈确认 帧发送端若在规定的时间内没有收到接收端的反馈确认帧（超 时），就认为数据帧丢失，在保持N(S)不变的情况下重新发 送缓冲器中的（旧）帧；发送端若接收到确认帧后，比较确认帧中的序号和N(S)：若不等，则将确认帧中的序号赋予N(S)，从网络层获取新的分 组并组成新帧（N(S)作为序号放入帧头中）交由物理层发送出 去。

若相等，则保持N(S)不变，重新发送缓冲器中的（旧）帧；DATA0发送端接收端DATA0N（S）0N（R）01tout丢弃DATA1132停-等协议对信道利用率的影响在时延大的信道（如卫星通信）中，停-等协议的效率是很低的考虑两个地面站通过卫星通信，典型的传播时间约为270ms假设一 个帧的发送时间为20ms，则从发送站开始发送算起，经20ms+ 270ms=290ms，数据帧才能到达目的站假设不考虑目的站的处理时 间，且认为确认帧非常短，其发送时间可忽略不计，则又需270ms确 认帧才能被发送站收到因此信道的利用率为： 20ms/(290ms+270ms)=1/28，非常低这是由于每发一个帧之前都 必须等待前一个帧的确认帧所造成的为了提高传输效率，可以设想让发送站连续不断地发送数据帧，当发 完第28个帧数据后，恰好第1帧的确认帧到达，根据确认可紧接着。