数据链路

计算机网络COMPUTERNETWORKS第5章数据链路层5.1基本概念链路：一条无源的点到点的物理线路段。数据链路：链路+规程（控制数据传输）。数据链路层的作用：通过一些数据链路层协议（即链路控制规程），在不太可靠的物理链路上实现可靠的数据传输。学习重点:两台机器之间实现可靠、有效的通信而涉及到的一些算法。数据链路层的主要功能：①链路管理：数据链路的建立、维持和释放；②帧同步：收方能从收到的比特流中区分一帧开始和结束的地方；③流量控制：发方发送数据的速率必须使收方来得及接收；④差错控制：收方收到有差错的数据帧时，能检错重传或纠错；⑤透明传输：不管所传数据是什么样的比特组合，收方都能正确接收。并能将数据与控制信息分开；⑥寻址：保证每一帧都能发送到目的站。设计要点；1）向网络层提供一个定义良好的服务接口2）处理传输错误3）调节数据流，确保慢速的接收方不会被除快速的发送方淹没。5.1.2为网络层提供的服务最主要的服务是将数据从源机器的网络层传输到目标机器的网络层.①无确认的无连接的服务：(P56)适用于误码率很低的通信信道；或语音通信；②有确认的无连接的服务：适用于误码率很高的通信信道；如无线通信；③有确认的面向连接的服务：适用于通信要求较高（可靠性、实时性）的情况5.1.3成帧方法①字符计数法：在帧头部指明帧内字符数。问题：由于传输差错导致计数值被“篡改”；②字符填充首尾界符法：以ASCII字符DLE和STX作为帧的头部，DLE和ETX作为帧的尾部（DLE＝10H、STX＝02H、ETX＝03H）技术：如何避免二进制数据可能与帧的头尾标志相同？发送方在数据中遇到DLE时，自动在其前后插入一个DLE;接收方在数据中遇到单个DLE时,可确定帧界;遇到2个DLE时，自动删除一个DLE。③位填充首尾标志法：以一个特定的字节信息作为帧的头尾标志；如01111110；为了避免与原始数据比特组合相同，发送方在数据中遇到5个连续的1时，自动在其后插入一个0；接收方在数据中遇到5个连续的1后面跟着一个0，自动将此0删除。5.1.4差错控制差错产生的原因主要由通信信道的噪声引起，通信信道噪声分为二种：（1）热噪声：由传输介质导体的电子热运动产生。幅度较小，是产生随机差错的主要根源；（2）冲击噪声：由外界电磁干扰产生，幅度较大，是产生突发差错的主要根源。其中冲击噪声是引起差错的主要原因。差错评价指标如下：（1）误码率：错传的码元数与所传输码元总数之比。Pe＝Ne/N其中，N─传输的码元总数，Ne─错传的的码元数。（2）误比特率：错传的比特数与所传输总比特数之比。在二进制码元时，误比特率＝误码率。差错控制的基本方式如下：（1）反馈纠错在接收端能发现差错，但不能确定错码的位置，通过反馈信息请求发送端重发，直到接收端肯定确认为止。适用于双工通信和非实时通信系统。（2）前向纠错在接收端不仅能发现错码，而且还能确定错码的位置，并纠正错误。适用于单工通信和实时通信系统。（3）混合纠错少量差错在接收端自动纠正，若超出自行纠正能力时，通过反馈信息请求发送端重发。5.1.5流控制基于反馈的流控制基于速率的流控制5.2错误检测和纠正码字的检错与纠错能力码字(n位)＝数据码(m位)+冗余码(r位)。海明距离：两个码字之间对应码元位的不同码元的个数。码字编码的海明距离对于一种码字编码，在这个码字集合中，可得到所有任意两个码字的海明距离，其中最小的海明距离称为该码字编码的海明距离d。定理1：如果d≥2t+1,则该编码可纠正任何t个(或t个以下)的错误。定理2：如果d≥e+1,则该编码可检测出任何e个(或e个以下)的错误。一般情况下，冗余位越多(即r越大)，检错纠错能力越强，但相应的编码效率也随之降低了。示例：偶校验的检错与纠错能力例：对于偶校验（使每个码字中都有偶数个1）数据码为2位（有用数据为00、01、10、11）冗余码为1位（偶校验位）有用数据经过偶校验编码，其码字集合：000、011、101、110；该编码的海明距离d=2，根据定理1，该编码不能纠正任何错误(t＝0)。D=2t+1根据定理2，该编码可检测出任何1个错误(e＝1)。D=e+1奇校验的检错能力与偶校验一样。误码控制编码的分类按冗余码的控制功能分:①纠错码：在接收端能发现并自动纠正差错。叫前向纠错纠错检错的常用方法①海明码：可纠错和检错，实现复杂，效率低。②奇偶校验码：方法简单，检错能力差。③循环冗余编码(CRC)：实现容易，检错能力强，广泛使用。5.2.1纠错码：海明码海明在1950年提出的可纠正一位错的编码方法。用r个校验位构造出r个校验关系式来指示一位错码的n(=m+r)种可能位置及表示无差错。码字排列：从最左边位开始依次编号(1、2、…、n);r个校验位：在2k的位置(1、2、4、8、…);m个数据位：在其余位(3、5、6、7、9、…)。r的确定：r2－r≥m+1;（∵r2≥n＋1=m+r+1）例如：4个信息位D1D2D3D4，3个校验位P1P2P3。5.2.2检错码：循环冗余码－CRC码特点：实现容易，检错能力强，广泛使用。常结合反馈重传法来保证信息的可靠传输。码字组成：例：若数据码＝110011，可表示为：M(x)=1·x5+1·x4+0·x3+0·x2+1·x+1即：M(x)=x5+x4+x+1。生成多项式G(x)：G(x)=grxr+...+gixi+...+g1x+g0其中,gi=0或1,r≥i≥0,gr≠0,g0≠0,共r+1位G(x)被通信双方事先共同选定使用：发送端：通过G(x)生成校验码；接收端：通过G(x)校验接收的码字。对于多项式的运算：采用模2计算（加法不进位，减法不借位）；加减法是一样的。模2计算即是异或运算。循环冗余检验的原理在数据链路层传送的帧中，广泛使用了循环冗余检验CRC的检错技术。在发送端，先把数据划分为组。假定每组k个比特。假设待传送的一组数据M=101001（现在k=6）。我们在M的后面再添加供差错检测用的n位冗余码一起发送。冗余码的计算用二进制的模2运算进行2n乘M的运算，这相当于在M后面添加n个0。得到的(k+n)位的数除以事先选定好的长度为(n+1)位的除数P，得出商是Q而余数是R，余数R比除数P少1位，即R是n位。冗余码的计算举例现在k=6,M=101001。除数P=1101，则n=3,被除数是2nM=101001000。110101←Q(商)P(除数)→1101101001000←2nM(被除数)11011110110101110000111011010110000011001101001←R(余数)，作为FCS循环冗余检验的原理说明模2运算的结果是：商Q=110101，余数R=001。把余数R作为冗余码添加在数据M的后面发送出去。发送的数据是：2nM+R即：101001001，共(k+n)位。检测出差错接收方对接收到的数据除以同样的除数,只要得出的余数R不为0，就表示检测到了差错。但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。一旦检测出差错，就丢弃这个出现差错的帧。只要经过严格的挑选，并使用位数足够多的除数P，那么出现检测不到的差错的概率就很小很小。1数据链路(即逻辑链路)与链路(即物理链路)有何区别?“电路接通了”与”数据链路接通了”的区别何在?答：数据链路与链路的区别在于数据链路出链路外，还必须有一些必要的规程来控制数据的传输，因此，数据链路比链路多了实现通信规程所需要的硬件和软件。“电路接通了”表示链路两端的结点交换机已经开机，物理连接已经能够传送比特流了，但是，数据传输并不可靠，在物理连接基础上，再建立数据链路连接，才是“数据链路接通了”，此后，由于数据链路连接具有检测、确认和重传功能，才使不太可靠的物理链路变成可靠的数据链路，进行可靠的数据传输当数据链路断开连接时，物理电路连接不一定跟着断开连接。2为了进行差错控制,必须对传送的数据进行校验.在局域网中广泛使用的校验方法是_(1)___,CRC-16标准规定生成多项式为G(x)=x16+X15+x2+1,它产生的校验码是__(2)__位,接收端发现错误后采取的措施是__(3)__.如果CRC的生成多项式是G(x)=x4+x+1,信息码字是10110,由计算出来的CRC校验码是__(4)_.(1)A奇偶检验B海明码C格雷码D循环冗余校验(2)A2B4C16D32(3)A自动纠错B报告上层协议C自动请求重发D重新生成原始数据(4)A0100B1010C0111D1111书上作业练习:P845-41要发送的数据为1101011011。采用CRC的生成多项式是P（X）=X4+X+1。试求应添加在数据后面的余数。数据在传输过程中最后一个1变成了0，问接收端能否发现？若数据在传输过程中最后两个1都变成了0，问接收端能否发现？采用CRC检验后，数据链路层的传输是否就变成了可靠的传输？答：作二进制除法，1101011011000010011得余数1110，添加的检验序列是1110.作二进制除法，两种错误均可发现仅仅采用了CRC检验，缺重传机制，数据链路层的传输还不是可靠的传输。本课重点掌握CRC冗余校验码的计算.5.3基本数据链路协议数据链路协议主要考虑的问题：①避免所传送的数据可能出现差错和丢失；②使发方发送数据的速率适应收方的接收能力。理想化的数据传输假设1：所传送的数据即不会出现差错和也不会丢失；不考虑差错控制问题）假设2：接收端的数据接收速率足够快，有能力接收发送端的数据发送率。（不考虑流量控制问题）在理想化的条件下，数据链路层不需要：①差错控制协议；②流量控制协议；就可保证数据的正确传输。实用的停止等待协议（ARQ）去掉假设1；去掉假设2。考虑差错控制问题®差错控制协议；考虑流量控制问题®流量控制协议；初步协议：①发送端发送数据帧后，等待接收端的应答帧；②接收端收到数据帧后，通过CRC校验(一般用硬件检验)，如果无差错，回送一个确认帧ACK，否则，回送一个否认帧NAK。③发送端收到应答帧，如果是ACK，发送下一数据帧，如果是NAK，重发数据帧。死锁现象：当出现帧丢失时，发送端永远等待下去。如何解决？解决方法：发送端设立一个超时计时器，发送完一个数据帧时，就启动它；如果在规定时间tout内得不到应答帧，就判定为超时，重传数据帧。Tout也称重传时间重复帧差错：若应答帧丢失，按照超时重发方法，接收端将收到重复帧，如何解决？解决方法：给每个数据帧附加不同的发送序号Ns，如果接收端收到相同序号的数据帧,则丢弃,并回送一个ACK。发送序号需要多少位?对于ARQ协议，发送序号有0和1即可(只需1个bit);每发一个新的数据帧，发送序号就和上次发送的不一样，重发的数据帧发送序号不变。ARQ协议：重传时间tout的选择若Tout太长，浪费时间，若Tout太短，过早重传数据，产生“额外”应答帧。如何解决？提示：在确认帧ACK和否认帧NAK中附加序号。停止等待协议的信道利用率连续ARQ协议目的：提高信道利用率。方法：发送端发送完一个数据帧后，不停下来等待应答帧，而是连续再发送数据帧。当收到否认帧NAK时，再控制重发。实现要求：数据帧需附加发送序号信息。否认帧附加出错的数据帧发送序号。常用协议：①回退N帧ARQ协议（gobackn）②选择重发ARQ协议（selectiverepeat）回退N帧ARQ协议（gobackn）①方式1：反馈否认帧NAK（含出错的数据帧发送序号）。再从出错的数据帧开始重传。要求：发送端要求有一个能存储N个数据帧的缓冲区。接收端只需能存储一个数据帧的缓冲。②方式2：不反馈否认帧NAK。发送端采用超时机制。发送端每发送一个数据帧就启动该帧计时器，当收到确认帧后，计时器复位；如果直到超时还没有收到确认帧，则重发该数据帧及后继的帧。选择重发ARQ协议（selectiverepeat）目的：进一步提高信道利用率。方