《计算机网络原理第三章数据链路层》由会员分享，可在线阅读，更多相关《计算机网络原理第三章数据链路层（96页珍藏版）》请在金锄头文库上搜索。
1、第三章 数据链路层,数据链路层设计问题,需要完成的特定功能： 为网络层提供设计良好的服务接口 确定如何将物理层的比特组成成帧 处理传输差错 调整帧的流速,为网络层提供的服务,基本服务是将源机器中来自网络层的数据传输给目的机器的网络层 一般都提供3种服务： 无确认无连接服务 有确认无连接服务 有确认的面向连接的服务,无确认无连接服务,此服务是指源机器向目的机器发送独立的帧，而目的机器对收到的帧不作确认。事先没有建立连接，事后也不存在释放。 此服务的适用范围：误码率很低的链路，例如，大多数局域网的数据链路层,有确认无连接服务,此服务不建立连接，但发送的每一帧都进行单独确认 如果在某个确定的时间间隔
2、内，帧没有到达，就必须重发此帧 此服务的适用范围：无线系统之类的不可靠信道,有确认的面向连接的服务,数据链路层为网络层提供的最复杂的服务 源机器和目的机器在传递任何数据之前，先建立一条连接。在这条连接上所发送的每一帧都被编上号，数据链路层保证所发送的每一帧都确实已收到。 保证每帧只收到一次，而且所有的帧都是按正确顺序收到 为网络层进程间提供可靠传送比特流的服务,面向连接服务传送的三个阶段,第一阶段：通过对双方的用于追踪哪个帧接收到了，哪个帧未接收到所需要的变量和计数器初始化，从而建立连接。 第二阶段：进行实际的帧传输。 第三阶段：断开连接，释放用于维护连接的变量、缓冲区及其他资源。,成帧,物理
3、层所做的工作是接收一个原始的比特流，并准备把它交给目的地。 不能保证这个比特流无差错。 上到数据链路层后才做差错检查、纠错等工作。 通常的方法是把比特流分成离散的帧，并对每帧计算出校验和。 当一帧到达目的地后重新计算校验和时，如果新计算的校验和不同于帧中所包括的值，数据链路层就知道出错了，从而会采取措施处理差错。,把比特流分成帧的一种方法是：在帧之间插入时间间隔 缺点：由于网络很难保证计时准确，所以在传输过程中时间间隔可能会被压缩，或者再插入其他间隔。 其他的成帧方法：1、字符计数法。2、带字符填充的首尾界符法。3、带位填充的首尾标志法。4、物理层编码违例法。,字符计数法,在帧头部中使用一个字
4、段来标明帧内字符数。 面临的问题是计数值有可能由于传输差错而被“篡改”。 一旦出错，无法重新找到帧边界。 此方法已经很少使用。,带字符填充的首尾界符法,每一帧以ASCII字符序列DLE STX开头，以DLE EXE结束。 目的机器一旦丢失帧边界，只需查找DLE STX或DLE EXE字符序列，就可找到它所在的位置。 缺点：1、当DLE STX或DLE EXE出现在数据中时会干扰帧界的确定。2、完全依赖于8位字符，特别是ASCII字符。 第1点的解决方法：采用字符填充，即在数据中的每个偶然遇到的DLE字符前，插入一个DLE的ASCII代码。,第2点的解决方法：采用位填充 允许数据帧包含任意个数的
5、比特，而且也允许每个字符的编码包含任意个数的比特。 工作方式如下：每一帧使用一个特殊的位模式，即01111110作为开始和结束标志字节。当发送方的数据链路层在数据中遇到5个连续的1时，它自动在其后插入一个0到输出比特流中。,物理层编码违例法,只适用于那些在物理层介质的编码策略中采用冗余技术的网络。,差错控制,为了保证可靠传送，常采用的方法是向数据发送方提供有关接受方接收情况的反馈信息。 典型的做法：协议要求接收方发回特殊的控制帧，作为对输入肯定或否定性的确认。 若发送方收到关于某个帧的肯定确认，则它知道此帧已正确到达。若收到否定确认，则意味着发生了差错，相应的帧必须被重传。 若接收方没收到帧（
6、即发送的帧丢失）或确认帧丢失，则使用计数器来解决这个问题。,当发送方发送一帧时，通常也启动计数器。 计数器计数到设定值时清0。在这个时间间隔内，要保证一帧到达对方并作相应处理后，对方的确认帧还能返回发送方。 正常情况下，在计时器终止计时前，帧被正确接收并返回确认帧，计时器清为0。 若所传出的帧或确认帧丢失，则计时器会发出超时信号，提醒发送方可能出现了问题，最明显的解决方法是重传此帧。,多次传送同一帧的危险：接收可能两次甚至多次收到同一帧，因而也会将同一帧多次交给网络层。 防止措施：对发出的各帧编号，这样接收方就能够辨别是重复帧还是新帧。,流量控制,解决发送方的传送能力比接收方大的问题。 此问题
7、会导致的后果：即使传送过程中毫无差错，接收方也会因无力处理收到的帧而会丢失一些帧。 解决方法：引入流量控制来限制发送方发出的数据流量，使之不超过接收方的能力。 需要某种反馈机制使发送方知道接收方的情况。 大部分流量控制方案的基本原理相同。,差错检验和纠正,通常数字传输时，差错很少发生 模拟传输经常发生差错 光纤干线差错率很小 无线通信差错率较大 两种基本的处理差错策略： 纠错码 检错码,纠错码,纠错码：在每一个要发送的数据块上附加足够的冗余信息，使接收方能够推导出已发出的字符应该是什么。 通常，一帧包括m个数据位和r个冗余位或校验位。设整个长度为n（n=m+r）。 码字：长度为n的单元。 海明
8、距离：两个码字中不同位的个数。 海明距离的意义：若两个码字具有海明距离d，则需要d个位差错才能将其中一个码字转换成另一个。 数据信息的可能组合：2m 所有的码字的可能组合：2n,一种编码的校验和纠错能力取决于它的海明距离。 为检测出d-1比特错，需要使用距离为d的编码；因为这种编码， d-1比特错决不可能将一个有效的码字改变成另一个有效码字。 当接收方看见无效码字时，它就能明白发送了传输差错。 为了纠正d比特错，必须用距离为2d+1的编码。这是因为有效码字的距离远到即使发生d个变化，这个发生了变化的码字仍然比任何其他码字都更接近原始码字。,奇偶校验（一个检错码例子）,奇偶位的选取原则是使码字内
9、的1的数目是偶数（或奇数）。 这种代码的距离为2，因为任何单比特错都会产生奇偶位不正确的码字。,一个纠错码例子,下面代码的距离为5，即能纠正2比特错。假设码字0000000111到达后，接收方知道应该是0000011111。,在给定信息位数目m的情况下，用来纠正单比特误码的校验位数目的下界r满足下式： 对2m 个有效信息中的任意一个而言，有n个与该码字距离为1的无效码字，依次将该码字中n个比特变反，即可得到。 2m 个信息中的每一个都需占用n+1个位模式，共有（ n+1 ） 2m 。 因为位模式的总数目是2n个，所以有,海明码字内位的编号,从最左边1开始依次编号。位号为2的幂的位是r个校验位，
10、例如，1，2，4，8等，其余为m个数据位。,已知：信息码为：“0010“。海明码的监督关系式为： S2=a2+a4+a5+a6 S1=a1+a3+a5+a6 S0=a0+a3+a4+a6 求：海明码码字。 解：1)由监督关系式知冗余码为a2a1a0。 2)冗余码与信息码合成的海明码是：“0010a2a1a0“。,设S2=S1=S0=0,由监督关系式得： a2=a4+a5+a6=1 a1=a3+a5+a6=0 a0=a3+a4+a6=1 因此，海明码码字为：“0010101“,已知：信息码为：“ 1 1 0 0 1 1 0 0 ” (k=8) 求：海明码码字。 解：1)把冗余码A、B、C、，顺序
11、插入信息码中，得海明码 码字:“ A B 1 C 1 0 0 D 1 1 0 0 ” 码位: 1 2 3 4 5 6 7 8 9 10 11 12 其中A,B,C,D分别插于2k位(k=0,1,2,3)。码位分别为1,2,4,8。 2)冗余码A,B,C,D的线性码位是：(相当于监督关系式) A-1,3,5,7,9,11； B-2,3,6,7,10,11； C-4,5,6,7,12；(注 5=4+1；6=4+2；7=4+2+1；12=8+4) D-8,9,10,11,12。,3)把线性码位的值的偶校验作为冗余码的值(设冗余码初值为0)： A=(0,1,1,0,1,0)=1 B=(0,1,0,0,
12、1,0)=0 C=(0,1,0,0,0) =1 D=(0,1,1,0,0) =0 4)海明码为:“1 0 1 1 1 0 0 0 1 1 0 0“,检错码,检错码：加入足够的冗余位，使接收方知道有差错发生，但不知道是什么样的差错，然后让接收方请求重传。 CRC(循环冗余校验码) 基本思想：将位串看成是系数为0或1的多项式 一个K位的帧看作是一个K-1次多项式的系数列表，称为K-1阶多项式。 多项式的算术运算采用代数域理论的规则，以2为模来完成。加法和减法等同于异或。,生成多项式G（x）：当使用多项式编码时，发送方和接收方预先商定的一个多项式。 生成多项式的最高位和最低位必须是1。 为了计算校验
13、和，帧对应的多项式M（x）必须比生成多项式长。 在帧的尾部追加校验和，使得追加之后的帧所对应的多项式能够被生成多项式除尽。,计算校验和的算法： （1）假设G（x）的阶为r。在帧的低位端加上r个0位，所以该帧现在包含m+r位，对应多项式为xr M（x）。 （2）利用模2除法，用对应于G（x）的位串去除对应于xr M（x）的位串。 （3）利用模2减法，从对应于xr M（x）的位串中减去余数（总是小于等于r位）。结果就是将被传输的带校验和的帧。,已知：信息码:110011 信息多项式:M(X)=X5+X4+X+1 生成码:11001 生成多项式:G(X)=X4+X3+1(r=4) 求：循环冗余码和码
14、字。 解：1)(X5+X4+X+1)*X4的积是 X9+X8+X5+X4 对应的码是1100110000。,2)积G(X)(按模二算法)。 由计算结果知冗余码是1001，码字就是1100111001。 1 0 0 0 0 1Q(X) G(x)1 1 0 0 1 )1 1 0 0 1 1 0 0 0 0M(X)*Xr 1 1 0 0 1 ， 1 0 0 0 0 1 1 0 0 1 1 0 0 1T(X)(冗余码),基本数据链路协议,假设物理层、数据链路层和网络层都是独立的进程，它们通过来回传递报文进行通信。这有助于使概念更加清晰，同时也可以强调每一层的独立性。 假设机器A希望用一个可靠的、面向连
15、接的服务，向机器B发送一个长的数据流。 假定A要发送的数据总是已经准备好了，不必等待这些数据被生成出来。 假定机器不会崩溃，也就是说，这些协议只处理通信错误，但不处理因为机器崩溃和重新启动而引起的问题。,当数据链路层接收一个分组时，就在分组之前加上帧头，在分组之后加上帧尾。然后传输到目的机器的数据链路层。 假设有一个现成的代码库，其中库过程to_physical_layer用于发送一帧， from_physical_layer用于接收一帧。 负责传输的硬件会计算校验和，并追加在尾部。,在本章例子中，数据链路层通过过程调用wait_for_event(&event)来等待帧的到来。只有当一帧到来
16、时，该过程才返回。 在实际环境中，可能会通过中断来处理，这里作了简化，忽略了并行活动的细节。,当一个帧到达接收方时，硬件会计算校验和。若有传输错误，会收到通知（ event =cksum_err），若无错误，则收到通知（ event =frame_arrival），利用from_physical_layer接收进来的帧并做处理。,定义的五种数据结构： 见书143，新书168 帧的组成：见书144，新书169 认识分组和帧的关系很重要。见书144，新书170 还有一些库例程，见书144，新书170,内部计时器或时钟。见书145，新书170,协议1：一种无限制的单工协议,假定数据只作单向传输，而且传送和接收的双方网络层都一直处于就绪状态。 包括两个过程：发送 接收 见书146147 新书171172,协议2：一个单工的停-等协议,抛弃协议
