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