数据链路层示例课件

第5章数据链路层第5章数据链路层15.1基本概念链路：一条无源的点到点的物理线路段。数据链路：链路+规程（控制数据传输）。数据链路层的作用：通过一些数据链路层协议（即链路控制规程），在不太可靠的物理链路上实现可靠的数据传输。学习重点:两台机器之间实现可靠、有效的通信而涉及到的一些算法。5.1基本概念2数据链路层的主要功能：①链路管理：数据链路的建立、维持和释放；②帧同步：收方能从收到的比特流中区分一帧开始和结束的地方；③流量控制：发方发送数据的速率必须使收方来得及接收；④差错控制：收方收到有差错的数据帧时，能检错重传或纠错；⑤透明传输：不管所传数据是什么样的比特组合，收方都能正确接收。并能将数据与控制信息分开；⑥寻址：保证每一帧都能发送到目的站。设计要点；1）向网络层提供一个定义良好的服务接口2）处理传输错误3）调节数据流，确保慢速的接收方不会被除快速的发送方淹没。数据链路层的主要功能：35.1.2为网络层提供的服务最主要的服务是将数据从源机器的网络层传输到目标机器的网络层.①无确认的无连接的服务：(P56)适用于误码率很低的通信信道；或语音通信；②有确认的无连接的服务：适用于误码率很高的通信信道；如无线通信；③有确认的面向连接的服务：适用于通信要求较高（可靠性、实时性）的情况5.1.2为网络层提供的服务最主要的服务是将数据从源机器的45.1.3成帧方法①字符计数法：在帧头部指明帧内字符数。问题：由于传输差错导致计数值被“篡改”；5.1.3成帧方法①字符计数法：5②字符填充首尾界符法：以ASCII字符DLE和STX作为帧的头部，DLE和ETX作为帧的尾部（DLE＝10H、STX＝02H、ETX＝03H）技术：如何避免二进制数据可能与帧的头尾标志相同？发送方在数据中遇到DLE时，自动在其前后插入一个DLE;接收方在数据中遇到单个DLE时,可确定帧界;遇到2个DLE时，自动删除一个DLE。②字符填充首尾界符法：6③位填充首尾标志法：以一个特定的字节信息作为帧的头尾标志；如01111110；为了避免与原始数据比特组合相同，发送方在数据中遇到5个连续的1时，自动在其后插入一个0；接收方在数据中遇到5个连续的1后面跟着一个0，自动将此0删除。③位填充首尾标志法：75.1.4差错控制差错产生的原因主要由通信信道的噪声引起，通信信道噪声分为二种：（1）热噪声：由传输介质导体的电子热运动产生。幅度较小，是产生随机差错的主要根源；（2）冲击噪声：由外界电磁干扰产生，幅度较大，是产生突发差错的主要根源。其中冲击噪声是引起差错的主要原因。5.1.4差错控制8差错评价指标如下：（1）误码率：错传的码元数与所传输码元总数之比。Pe＝Ne/N其中，N─传输的码元总数，Ne─错传的的码元数。（2）误比特率：错传的比特数与所传输总比特数之比。在二进制码元时，误比特率＝误码率。差错评价指标如下：9差错控制的基本方式如下：（1）反馈纠错

在接收端能发现差错，但不能确定错码的位置，通过反馈信息请求发送端重发，直到接收端肯定确认为止。

适用于双工通信和非实时通信系统。（2）前向纠错在接收端不仅能发现错码，而且还能确定错码的位置，并纠正错误。

适用于单工通信和实时通信系统。（3）混合纠错少量差错在接收端自动纠正，若超出自行纠正能力时，通过反馈信息请求发送端重发。差错控制的基本方式如下：105.1.5流控制基于反馈的流控制基于速率的流控制5.1.5流控制115.2错误检测和纠正5.2错误检测和纠正12码字的检错与纠错能力码字(n位)＝数据码(m位)+冗余码(r位)。海明距离：两个码字之间对应码元位的不同码元的个数。码字的检错与纠错能力码字(n位)＝数据码(m位)+冗余码(r13码字编码的海明距离对于一种码字编码，在这个码字集合中，可得到所有任意两个码字的海明距离，其中最小的海明距离称为该码字编码的海明距离d。定理1：如果d≥2t+1,则该编码可纠正任何t个(或t个以下)的错误。定理2：如果d≥e+1,则该编码可检测出任何e个(或e个以下)的错误。一般情况下，冗余位越多(即r越大)，检错纠错能力越强，但相应的编码效率也随之降低了。码字编码的海明距离对于一种码字编码，在这个码字集合中，可得到14示例：偶校验的检错与纠错能力例：对于偶校验（使每个码字中都有偶数个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奇校验的检错能力与偶校验一样。示例：偶校验的检错与纠错能力例：对于偶校验（使每个码字中都有15误码控制编码的分类按冗余码的控制功能分:①纠错码：在接收端能发现并自动纠正差错。叫前向纠错纠错检错的常用方法①海明码：可纠错和检错，实现复杂，效率低。②奇偶校验码：方法简单，检错能力差。③循环冗余编码(CRC)：实现容易，检错能力强，广泛使用。误码控制编码的分类按冗余码的控制功能分:165.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.1纠错码：海明码海明在1950年提出的可纠正一位错的175.2.2检错码：循环冗余码－CRC码特点：实现容易，检错能力强，广泛使用。常结合反馈重传法来保证信息的可靠传输。码字组成：5.2.2检错码：循环冗余码－CRC码特点：实现容易，检错能18例：若数据码＝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计算即是异或运算。例：若数据码＝110011，19循环冗余检验的原理在数据链路层传送的帧中，广泛使用了循环冗余检验CRC的检错技术。在发送端，先把数据划分为组。假定每组k个比特。假设待传送的一组数据M=101001（现在k=6）。我们在M的后面再添加供差错检测用的n位冗余码一起发送。循环冗余检验的原理在数据链路层传送的帧中，广泛使用了循环冗20冗余码的计算用二进制的模

2

运算进行2n乘M的运算，这相当于在M后面添加n个0。得到的(k+n)位的数除以事先选定好的长度为(n+1)位的除数P，得出商是Q而余数是R，余数R比除数P少1位，即R是n位。冗余码的计算用二进制的模2运算进行2n乘M的运21冗余码的计算举例现在k=6,M=101001。除数P=1101，则n=3,被除数是2nM=101001000。冗余码的计算举例现在k=6,M=101001。22

110101

←

Q

(商)P(除数)→

1101101001000

←

2nM(被除数)

1101

1110

1101

0111

0000

1110

1101

0110

0000

1100

1101

001←R(余数)，作为FCS

循环冗余检验的原理说明

23模2运算的结果是：商Q=110101，余数R=001。把余数R作为冗余码添加在数据M的后面发送出去。发送的数据是：2nM+R

即：101001001，共(k+n)位。模2运算的结果是：商Q=110101，24检测出差错接收方对接收到的数据除以同样的除数,只要得出的余数R不为0，就表示检测到了差错。但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。一旦检测出差错，就丢弃这个出现差错的帧。只要经过严格的挑选，并使用位数足够多的除数P，那么出现检测不到的差错的概率就很小很小。检测出差错接收方对接收到的数据除以同样的除数,只要得出的余数25数据链路层示例课件261数据链路(即逻辑链路)与链路(即物理链路)有何区别?“电路接通了”与”数据链路接通了”的区别何在?答：数据链路与链路的区别在于数据链路出链路外，还必须有一些必要的规程来控制数据的传输，因此，数据链路比链路多了实现通信规程所需要的硬件和软件。“电路接通了”表示链路两端的结点交换机已经开机，物理连接已经能够传送比特流了，但是，数据传输并不可靠，在物理连接基础上，再建立数据链路连接，才是“数据链路接通了”，此后，由于数据链路连接具有检测、确认和重传功能，才使不太可靠的物理链路变成可靠的数据链路，进行可靠的数据传输当数据链路断开连接时，物理电路连接不一定跟着断开连接。1数据链路(即逻辑链路)与链路(即物理链路)有何区别?“272为了进行差错控制,必须对传送的数据进行校验.在局域网中广泛使用的校验方法是_(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)A0100B1010C0111D11112为了进行差错控制,必须对传送的数据进行校验.在局域网中28书上作业练习:P845-41要发送的数据为1101011011。采用CRC的生成多项式是P（X）=X4+X+1。试求应添加在数据后面的余数。数据在传输过程中最后一个1变成了0，问接收端能否发现？若数据在传输过程中最后两个1都变成了0，问接收端能否发现？采用CRC检验后，数据链路层的传输是否就变成了可靠的传输？

书上作业练习:P845-41要发送的数据为110101129答：作二进制除法，1101011011000010011得余数1110，添加的检验序列是1110.作二进制除法，两种错误均可发现仅仅采用了CRC检验，缺重传机制，数据链路层的传输还不是可靠的传输。答：作二进制除法，11010110110000130本课重点掌握CRC冗余校验码的计算.本课重点掌握CRC冗余校验码的计算.315.3基本数据链路协议数据链路协议主要考虑的问题：①避免所传送的数据可能出现差错和丢失；②使发方发送数据的速率适应收方的接收能力。5.3基本数据链路协议数据链路协议主要考虑的问题：32理想化的数据传输假设1：所传送的数据即不会出现差错和也不会丢失；不考虑差错控制问题）假设2：接收端的数据接收速率足够快，有能力接收发送端的数据发送率。（不考虑流量控制问题）在理想化的条件下，数据链路层不需要：①差错控制协议；②流量控制协议；就可保证数据的正确传输。理想化的数据传输假设1：所传送的数据即不会出现差错和也不会丢33实用的停止等待协议（ARQ）去掉假设1；去掉假设2。考虑差错控制问题®差错控制协议；考虑流量控制问题®流量控制协议；初步协议：①发送端发送数据帧后，等待接收端的应答帧；②接收端收到数据帧后，通过CRC校验(一般用硬件检验)，如果无差错，回送一个确认帧ACK，否则，回送一个否认帧NAK。③发送端收到应答帧，如果是ACK，发送下一数据帧，如果是NAK，重发数据帧。实用的停止等待协议（ARQ）去掉假设1；去掉假设2。34数据链路层示例课件35死锁现象：当出现帧丢失时，发送端永远等待下去。如何解决？解决方法：发送端设立一个超时计时器，发送完一个数据帧时，就启动它；如果在规定时间tout内得不到应答帧，就判定为超时，重传数据帧。Tout也称重传时间死锁现象：当出现帧丢失时，发送端永36重复帧差错：若应答帧丢失，按照超时重发方法，接收端将收到重复帧，如何解决？解决方法：给每个数据帧附加不同的发送序号Ns，如果接收端收到相同序号的数据帧,则丢弃,并回送一个ACK。重复帧差错：若应答帧丢失，按照超37发送序号需要多少位?对于ARQ协议，发送序号有0和1即可(只需1个bit);每发一个新的数据帧，发送序号就和上次发送的不一样，重发的数据帧发送序号不变。发送序号需要多少位?对于ARQ协议，发送序号有0和138ARQ协议：ARQ协议：39重传时间tout的选择若Tout太长，浪费时间，若Tout太短，过早重传数据，产生“额外”应答帧。如何解决？提示：在确认帧ACK和否认帧NAK中附加序号。重传时间tout的选择若Tout太长，浪费时间，40停止等待协议的信道利用率停止等待协议的信道利用率41数据链路层示例课件42连续ARQ协议目的：提高信道利用率。方法：发送端发送完一个数据帧后，不停下来等待应答帧，而是连续再发送数据帧。当收到否认帧NAK时，再控制重发。实现要求：数据帧需附加发送序号信息。否认帧附加出错的数据帧发送序号。常用协议：①回退N帧ARQ协议（gobackn）②选择重发ARQ协议（selectiverepeat）连续ARQ协议目的：提高信道利用率。43回退N帧ARQ协议（gobackn）①方式1：反馈否认帧NAK（含出错的数据帧发送序号）。再从出错的数据帧开始重传。要求：发送端要求有一个能存储N个数据帧的缓冲区。接收端只需能存储一个数据帧的缓冲。回退N帧ARQ协议（gobackn）①方式1：44②方式2：不反馈否认帧NAK。发送端采用超时机制。发送端每发送一个数据帧就启动该帧计时器，当收到确认帧后，计时器复位；如果直到超时还没有收到确认帧，则重发该数据帧及后继的帧。②方式2：45选择重发ARQ协议（selectiverepeat）目的：进一步提高信道利用率。方法：只重传出现差错的数据帧或者超时的数据帧。要求：在接收端要设置具有相当容量的缓存空间。选择重发ARQ协议（selectiverepeat）目的：46选择重发ARQ协议－工作原理示意图选择重发ARQ协议－工作原理示意图475.4滑动窗口协议（SlidingWindowsprotocol）①当未被确认的数据帧数目太多时；只要有一帧出错，就有很多数据帧需要重传，因而增大开销。②为了对发送出去的大量未被确认的数据帧进行编号，每个数据帧的发送序号也要占用较多的比特数，因而又增大了开销。对于连续ARQ协议，采用了发送端不等待确认帧返回就可连续发送帧，存在问题：滑动窗口协议：对发送端已发送出去但未被确认的帧的数目加以限制。在发送端和接收端分别设置发送窗口和接收窗口。5.4滑动窗口协议（SlidingWindowspro48发送窗口（在发送端）目的：用来对发送端进行流量控制。发送窗口尺寸Ws：在还没有收到应答帧的情况下，发送端最多可以连续发送数据帧的个数。发送序号：一般采用n位bit进行编号（0～2n-1）。若n=3；则用3位bit进行编号（0～7）。发送窗口（在发送端）目的：用来对发送端进行流量控制。49·发送端只能连续发送窗口内的数据帧；·每收到一个确认帧后，发送窗口的前、后沿顺时针旋转一个号，并可以一个发送新的数据帧。·若未应答帧的数目等于发送窗口尺寸时，便停止发送新的数据帧。·发送端只能连续发送窗口内的数据帧；50接收窗口（在接收端）目的：用来控制可以接收哪些数据帧而不可以接收哪些帧。接收窗口Wr：只有当收到的数据帧的发送序号落入接收窗口内，才允许将该数据帧收下；否则，丢弃。接收窗口（在接收端）目的：用来控制可以接收哪些数据帧而不可以51如果Wr=1，意味着只能按顺序接收数据帧。如果Wr较大，有可能会出现数据帧的失序。差错情况：设Wr=1；若收到0号数据帧，接收窗口顺时针旋转一个号，并发出0号确认帧；准备接收1号数据帧。此时，如果收到的不是1号数据帧，而是0号数据帧，表明发出0号确认帧发送端没有收到，因此再发送一次0号确认帧，此时收到的0号数据帧必须丢弃，否则发生重复。若是2号数据帧，表明发送端发出的1号数据帧丢失，因此发送1号否认帧，让对方重新发送1号数据帧。如果Wr=1，意味着只能按顺序接收数据帧。52应答帧丢失情况应答帧丢失情况53应答帧被“篡改”情况:ACK→NAK应答帧被“篡改”情况:ACK→NAK54数据链路层示例课件55重叠问题在接收前后，接收窗口范围内的有效序号出现重叠。重叠问题在接收前后，接收窗口范围内的有效序号出现重叠。56避免重叠问题为了避免重叠问题，接收窗口尺寸Wr≤2n/2。避免重叠问题为了避免重叠问题，接收窗口尺寸Wr≤2n/2。57发送窗口的最大尺寸值发送窗口的最大尺寸值58累积确认方法接收端在连续接收若干个正确的数据帧以后，对最后一个数据帧发回确认帧。累积确认方法接收端在连续接收若干个正确的数据帧以59窗口控制协议的信道利用率窗口控制协议的信道利用率60窗口控制协议的信道利用率设：单程传输时延Td，数据帧发送时间Tf，数据传输率C，数据帧长度L，窗口尺寸Ws在正常传输情况下，忽略应答帧长度和处理时间：窗口控制协议的信道利用率设：单程传输时延Td，数据帧发送时61依据信道利用率进行窗口尺寸的选择优化原则：发送端收到窗口中第一个已发数据帧的确认时，正好发完窗口中的最后一个数据帧。Ws大于上述选择，则Cr=100%，但浪费缓冲区；Ws小于上述选择，则Cr<100%，发送端需要等待应答而使发送停顿。依据信道利用率进行窗口尺寸的选择优化原则：62示例例：卫星信道：单程传输时延Td＝250ms，数据传输率C＝50kb/s，数据帧长度L＝1000bit，在已知条件不变的情况下，设置L=160bit，信道利用率如何？示例例：卫星信道：63ARQ协议、连续ARQ协议的窗口尺寸ARQ协议：发送窗口Ws＝1，接收窗口Wr＝1连续ARQ协议:·回退N帧ARQ协议：发送窗口Ws＞1，接收窗口Wr=1。·选择重发连续ARQ协议：发送窗口Ws＞1，接收窗口Wr＞1，且Wr≤Ws。ARQ协议、连续ARQ协议的窗口尺寸ARQ协议：64重难点讲解与练习1流量和差错控制1)差错控制方法:A自动请求重发(AutomaticRepeatRequest,ARQ)B前向纠错2)形成两种重要的流控制A选择重发ARQ协议:只重发出错帧B后退N帧ARQ协议:退回到出错帧重难点讲解与练习1流量和差错控制65效率分析公式:1停等协议:假设线路不出错,则如出错概率为P,则(其中a=tp/tf,可理解为线路的帧计数长度)2选择重发ARQ协议,假设发送窗口的大小为W,则不出错时为:如果对出错进行重发,设出错概率为P,则效率分析公式:663后退N帧:当W>=2a+1,N近似等于2a+1,则当W<2a+1,N=W.则3后退N帧:67例1:已知数据帧长为1000bit,帧头为64bit,数据速率为500kb/s,线路传播延迟为5ms,则1)信道无差错,采用停等协议,求利用率2)滑动窗口为大窗口,求窗口至少为多大?3)设P=0.01,用选择重发ARQ协议,窗口大小W=4,求利用率.解:1)a=Tp/TfTp=5Tf=1064/500a=5X500/1064=2.35E=0.182)所谓大窗口就是W>=2a+1,由上面知a=2.35故w>=2X2.35+1=5.7取w=6例1:已知数据帧长为1000bit,帧头为64bit,数据683)P一般比较小,在分母看作为0,故得:由于w=4,2a+1=5.7,为小窗口,W=w(1-p)/2a+1=4X(1-0.01)/5.7=0.693)695.5协议1.协议开发过程5.5协议1.协议开发过程70协议的形式描述描述方法：①有限状态机采用状态流程图进行描述。②事件状态表采用表格进行描述。③结构化程序采用程序代码进行描述。④Petri网模型采用状态流程图进行描述。协议的形式描述描述方法：71有限状态机模型FSMFSM协议描述方法也称状态转移图。特点：易懂、易理解和易于实现。组成：状态圆和有向弧。有限状态机模型FSMFSM协议描述方法也称状态转移图。72Petri网模型德国C.A.Petrit提出(1962,博士论文)。4个基本元素：位置：系统可能处于的状态；用圆圈表示。转换：改变状态；用线段表示。有向弧：位置与转换之间的相互依赖关系；用弧线表示。标记：系统当前处于的状态；在圆圈中用黑点表示。Petri网模型德国C.A.Petrit提出(1962,博士73数据链路层示例课件74数据链路层示例分类：数据链路层示例分类：75高级数据链路控制HDLC1976年，ISO提出HDLC（High-levelDataLinkControl）适用范围：计算机—计算机、计算机—终端、终端—终端三种类型的站：主站：主要功能是发送命令（包括数据），接收响应，负责整个链路的控制（如系统的初始、流控、差错恢复等）；次站：主要功能是接收命令，发送响应，配合主站完成链路的控制；复合站：同时具有主、次站功能，既发送又接收命令和响应，并负责整个链路的控制。高级数据链路控制HDLC1976年，ISO提出HDLC（Hi76HDLC的链路构型非平衡配置主站控制整个链路工作。主站发出的帧叫命令；次站发出的帧叫响应。适合把智能和半智能的终端连接到计算机。HDLC的链路构型非平衡配置77HDLC的链路构型平衡配置复合站具有主站和次站的功能。地位平等。适合于计算机和计算机之间的连接HDLC的链路构型平衡配置78HDLC的基本操作模式正规响应模式NRM：适用于点—点式和多点式两种非平衡构型。只有当主站向次站发出探询后，次站才能获得传输帧的许可。异步响应模式ARM：适用于点—点式非平衡构型和主站—次站式平衡构型。次站可以随时传输帧，不必等待主站的探询。异步平衡模式ABM：适用于通信双方都是复合站的平衡构型，也采用异步响应，双方具有同等能力。HDLC的基本操作模式正规响应模式NRM：79HDLC的帧结构帧标志（Flag）定界符为01111110＝7EH（零比特填充法）。地址域（Address）多终端线路，用来区分终端；点到点线路，有时用来区分命令和响应。–若是接收该帧的站的地址，则该帧是命令帧；–若是发送该帧的站的地址，则该帧是响应帧。HDLC的帧结构帧标志（Flag）80HDLC的帧结构有效地址为254个（通常为8位，可扩展到16位）–全1的8位地址表示广播（所有次站接收）；–全0的8位地址是无效地址。控制域（Control）标识帧的类型和功能，使对方站执行特定的操作。–信息帧（Information帧）；–管理帧（Supervisory帧）；–无序号帧（Unnumbered帧）。HDLC的帧结构有效地址为254个（通常为8位，可扩展到1681HDLC的帧结构数据域（Data）任意比特串或字符串（有上限）校验和（Checksum）循环冗余校验（CRC）生成多项式：HDLC的帧结构数据域（Data）82控制域的格式Seq－发送序号使用滑动窗口技术，3位序号，发送窗口Ws=7；Next－捎带确认接收站期望收到的帧序号，而不是最后一个已收到的帧序号；控制域的格式Seq－发送序号83控制域的格式P/F－询问/终止命令帧置P位，表示要求对方立即发送响应；响应帧置F位，表示要发送的数据已经发送完毕。注：最后一个帧P/F位置为“F”，其它置为“P”。有些协议，P/F位用来强迫对方机器立刻发控制帧；Type－类型“Type0”表示确认帧；“Type1”表示否定帧。“Type2”表示接收未准备好；“Type3”表示选择拒绝。无序号帧可以用来传控制信息，也可在不可靠无连接服务中传数据。尽管HDLC被广泛地被使用了,但它还不够完美,这就是网络.控制域的格式P/F－询问/终止84因特网的点对点协议PPP1992年，PPP:Point-to-PointProtocol应用：①拨号方式入网②专线方式入网因特网的点对点协议PPP1992年，PPP:Point-85PPP的组成Internet需要一个点到点协议,它有多种用途,其中包括传送从路由器到路由器之间的流量,以及从家庭用户到ISP之间的流量.PPP处理错误检测,支持多个协议,允许在连接时刻协商IP地址,允许身份认证.PPP提供了三类功能:(P201)①成帧方法（面向比特和面向字符）②链路控制协议LCP③网络控制协议NCPPPP的组成Internet需要一个点到点协议,它有多种用86PPP的帧结构的字段描述帧标志（Flag）定界符为01111110＝7EH。–在同步链路传输时：采用零比特填充法；–在异步链路传输时：采用字符填充法。若数据字段出现一个7EH，变为7DH和5EH；若数据字段出现一个7DH，变为7DH和5DH；若数据字段出现ASCII码的控制字符(小于20H的字符)，则在该字符前插入一个7DH。地址域（Address）始终为FFH。实际上，不需要地址。PPP的帧结构的字段描述帧标志（Flag）87PPP的帧结构的字段描述控制域（Control）

一般为03H，表示是无序号帧。协议域（Protocol）

若为C021H，则数据字段是PPP链路控制数据；

若为8021H，则数据字段是PPP网络控制数据。净荷域:最大不超过1500字节PPP的帧结构的字段描述控制域（Control）88PPP的通信过程当用户拨号接入ISP，–路由器的modem对拨号做出确认，–建立一条物理连接；–PC机发送LCP分组（PPP参数）–路由器进行网络层配置，–NCP给PC机一个临时IP地址；当用户挂机时，–NCP释放网络层连接，–收回原来分配出去的IP地址；–LCP释放数据链路层连接，–最后，释放物理层连接。PPP的通信过程当用户拨号接入ISP，89本章小结数据链路层的任务检错与纠错滑动窗口协议HDLC与PPP协议相应协议的软件程序实现本章小结数据链路层的任务90作业5-415-42作业5-4191第5章数据链路层第5章数据链路层925.1基本概念链路：一条无源的点到点的物理线路段。数据链路：链路+规程（控制数据传输）。数据链路层的作用：通过一些数据链路层协议（即链路控制规程），在不太可靠的物理链路上实现可靠的数据传输。学习重点:两台机器之间实现可靠、有效的通信而涉及到的一些算法。5.1基本概念93数据链路层的主要功能：①链路管理：数据链路的建立、维持和释放；②帧同步：收方能从收到的比特流中区分一帧开始和结束的地方；③流量控制：发方发送数据的速率必须使收方来得及接收；④差错控制：收方收到有差错的数据帧时，能检错重传或纠错；⑤透明传输：不管所传数据是什么样的比特组合，收方都能正确接收。并能将数据与控制信息分开；⑥寻址：保证每一帧都能发送到目的站。设计要点；1）向网络层提供一个定义良好的服务接口2）处理传输错误3）调节数据流，确保慢速的接收方不会被除快速的发送方淹没。数据链路层的主要功能：945.1.2为网络层提供的服务最主要的服务是将数据从源机器的网络层传输到目标机器的网络层.①无确认的无连接的服务：(P56)适用于误码率很低的通信信道；或语音通信；②有确认的无连接的服务：适用于误码率很高的通信信道；如无线通信；③有确认的面向连接的服务：适用于通信要求较高（可靠性、实时性）的情况5.1.2为网络层提供的服务最主要的服务是将数据从源机器的955.1.3成帧方法①字符计数法：在帧头部指明帧内字符数。问题：由于传输差错导致计数值被“篡改”；5.1.3成帧方法①字符计数法：96②字符填充首尾界符法：以ASCII字符DLE和STX作为帧的头部，DLE和ETX作为帧的尾部（DLE＝10H、STX＝02H、ETX＝03H）技术：如何避免二进制数据可能与帧的头尾标志相同？发送方在数据中遇到DLE时，自动在其前后插入一个DLE;接收方在数据中遇到单个DLE时,可确定帧界;遇到2个DLE时，自动删除一个DLE。②字符填充首尾界符法：97③位填充首尾标志法：以一个特定的字节信息作为帧的头尾标志；如01111110；为了避免与原始数据比特组合相同，发送方在数据中遇到5个连续的1时，自动在其后插入一个0；接收方在数据中遇到5个连续的1后面跟着一个0，自动将此0删除。③位填充首尾标志法：985.1.4差错控制差错产生的原因主要由通信信道的噪声引起，通信信道噪声分为二种：（1）热噪声：由传输介质导体的电子热运动产生。幅度较小，是产生随机差错的主要根源；（2）冲击噪声：由外界电磁干扰产生，幅度较大，是产生突发差错的主要根源。其中冲击噪声是引起差错的主要原因。5.1.4差错控制99差错评价指标如下：（1）误码率：错传的码元数与所传输码元总数之比。Pe＝Ne/N其中，N─传输的码元总数，Ne─错传的的码元数。（2）误比特率：错传的比特数与所传输总比特数之比。在二进制码元时，误比特率＝误码率。差错评价指标如下：100差错控制的基本方式如下：（1）反馈纠错

在接收端能发现差错，但不能确定错码的位置，通过反馈信息请求发送端重发，直到接收端肯定确认为止。

适用于双工通信和非实时通信系统。（2）前向纠错在接收端不仅能发现错码，而且还能确定错码的位置，并纠正错误。

适用于单工通信和实时通信系统。（3）混合纠错少量差错在接收端自动纠正，若超出自行纠正能力时，通过反馈信息请求发送端重发。差错控制的基本方式如下：1015.1.5流控制基于反馈的流控制基于速率的流控制5.1.5流控制1025.2错误检测和纠正5.2错误检测和纠正103码字的检错与纠错能力码字(n位)＝数据码(m位)+冗余码(r位)。海明距离：两个码字之间对应码元位的不同码元的个数。码字的检错与纠错能力码字(n位)＝数据码(m位)+冗余码(r104码字编码的海明距离对于一种码字编码，在这个码字集合中，可得到所有任意两个码字的海明距离，其中最小的海明距离称为该码字编码的海明距离d。定理1：如果d≥2t+1,则该编码可纠正任何t个(或t个以下)的错误。定理2：如果d≥e+1,则该编码可检测出任何e个(或e个以下)的错误。一般情况下，冗余位越多(即r越大)，检错纠错能力越强，但相应的编码效率也随之降低了。码字编码的海明距离对于一种码字编码，在这个码字集合中，可得到105示例：偶校验的检错与纠错能力例：对于偶校验（使每个码字中都有偶数个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奇校验的检错能力与偶校验一样。示例：偶校验的检错与纠错能力例：对于偶校验（使每个码字中都有106误码控制编码的分类按冗余码的控制功能分:①纠错码：在接收端能发现并自动纠正差错。叫前向纠错纠错检错的常用方法①海明码：可纠错和检错，实现复杂，效率低。②奇偶校验码：方法简单，检错能力差。③循环冗余编码(CRC)：实现容易，检错能力强，广泛使用。误码控制编码的分类按冗余码的控制功能分:1075.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.1纠错码：海明码海明在1950年提出的可纠正一位错的1085.2.2检错码：循环冗余码－CRC码特点：实现容易，检错能力强，广泛使用。常结合反馈重传法来保证信息的可靠传输。码字组成：5.2.2检错码：循环冗余码－CRC码特点：实现容易，检错能109例：若数据码＝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计算即是异或运算。例：若数据码＝110011，110循环冗余检验的原理在数据链路层传送的帧中，广泛使用了循环冗余检验CRC的检错技术。在发送端，先把数据划分为组。假定每组k个比特。假设待传送的一组数据M=101001（现在k=6）。我们在M的后面再添加供差错检测用的n位冗余码一起发送。循环冗余检验的原理在数据链路层传送的帧中，广泛使用了循环冗111冗余码的计算用二进制的模

2

运算进行2n乘M的运算，这相当于在M后面添加n个0。得到的(k+n)位的数除以事先选定好的长度为(n+1)位的除数P，得出商是Q而余数是R，余数R比除数P少1位，即R是n位。冗余码的计算用二进制的模2运算进行2n乘M的运112冗余码的计算举例现在k=6,M=101001。除数P=1101，则n=3,被除数是2nM=101001000。冗余码的计算举例现在k=6,M=101001。113

110101

←

Q

(商)P(除数)→

1101101001000

←

2nM(被除数)

1101

1110

1101

0111

0000

1110

1101

0110

0000

1100

1101

001←R(余数)，作为FCS

循环冗余检验的原理说明

114模2运算的结果是：商Q=110101，余数R=001。把余数R作为冗余码添加在数据M的后面发送出去。发送的数据是：2nM+R

即：101001001，共(k+n)位。模2运算的结果是：商Q=110101，115检测出差错接收方对接收到的数据除以同样的除数,只要得出的余数R不为0，就表示检测到了差错。但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。一旦检测出差错，就丢弃这个出现差错的帧。只要经过严格的挑选，并使用位数足够多的除数P，那么出现检测不到的差错的概率就很小很小。检测出差错接收方对接收到的数据除以同样的除数,只要得出的余数116数据链路层示例课件1171数据链路(即逻辑链路)与链路(即物理链路)有何区别?“电路接通了”与”数据链路接通了”的区别何在?答：数据链路与链路的区别在于数据链路出链路外，还必须有一些必要的规程来控制数据的传输，因此，数据链路比链路多了实现通信规程所需要的硬件和软件。“电路接通了”表示链路两端的结点交换机已经开机，物理连接已经能够传送比特流了，但是，数据传输并不可靠，在物理连接基础上，再建立数据链路连接，才是“数据链路接通了”，此后，由于数据链路连接具有检测、确认和重传功能，才使不太可靠的物理链路变成可靠的数据链路，进行可靠的数据传输当数据链路断开连接时，物理电路连接不一定跟着断开连接。1数据链路(即逻辑链路)与链路(即物理链路)有何区别?“1182为了进行差错控制,必须对传送的数据进行校验.在局域网中广泛使用的校验方法是_(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)A0100B1010C0111D11112为了进行差错控制,必须对传送的数据进行校验.在局域网中119书上作业练习:P845-41要发送的数据为1101011011。采用CRC的生成多项式是P（X）=X4+X+1。试求应添加在数据后面的余数。数据在传输过程中最后一个1变成了0，问接收端能否发现？若数据在传输过程中最后两个1都变成了0，问接收端能否发现？采用CRC检验后，数据链路层的传输是否就变成了可靠的传输？

书上作业练习:P845-41要发送的数据为1101011120答：作二进制除法，1101011011000010011得余数1110，添加的检验序列是1110.作二进制除法，两种错误均可发现仅仅采用了CRC检验，缺重传机制，数据链路层的传输还不是可靠的传输。答：作二进制除法，110101101100001121本课重点掌握CRC冗余校验码的计算.本课重点掌握CRC冗余校验码的计算.1225.3基本数据链路协议数据链路协议主要考虑的问题：①避免所传送的数据可能出现差错和丢失；②使发方发送数据的速率适应收方的接收能力。5.3基本数据链路协议数据链路协议主要考虑的问题：123理想化的数据传输假设1：所传送的数据即不会出现差错和也不会丢失；不考虑差错控制问题）假设2：接收端的数据接收速率足够快，有能力接收发送端的数据发送率。（不考虑流量控制问题）在理想化的条件下，数据链路层不需要：①差错控制协议；②流量控制协议；就可保证数据的正确传输。理想化的数据传输假设1：所传送的数据即不会出现差错和也不会丢124实用的停止等待协议（ARQ）去掉假设1；去掉假设2。考虑差错控制问题®差错控制协议；考虑流量控制问题®流量控制协议；初步协议：①发送端发送数据帧后，等待接收端的应答帧；②接收端收到数据帧后，通过CRC校验(一般用硬件检验)，如果无差错，回送一个确认帧ACK，否则，回送一个否认帧NAK。③发送端收到应答帧，如果是ACK，发送下一数据帧，如果是NAK，重发数据帧。实用的停止等待协议（ARQ）去掉假设1；去掉假设2。125数据链路层示例课件126死锁现象：当出现帧丢失时，发送端永远等待下去。如何解决？解决方法：发送端设立一个超时计时器，发送完一个数据帧时，就启动它；如果在规定时间tout内得不到应答帧，就判定为超时，重传数据帧。Tout也称重传时间死锁现象：当出现帧丢失时，发送端永127重复帧差错：若应答帧丢失，按照超时重发方法，接收端将收到重复帧，如何解决？解决方法：给每个数据帧附加不同的发送序号Ns，如果接收端收到相同序号的数据帧,则丢弃,并回送一个ACK。重复帧差错：若应答帧丢失，按照超128发送序号需要多少位?对于ARQ协议，发送序号有0和1即可(只需1个bit);每发一个新的数据帧，发送序号就和上次发送的不一样，重发的数据帧发送序号不变。发送序号需要多少位?对于ARQ协议，发送序号有0和1129ARQ协议：ARQ协议：130重传时间tout的选择若Tout太长，浪费时间，若Tout太短，过早重传数据，产生“额外”应答帧。如何解决？提示：在确认帧ACK和否认帧NAK中附加序号。重传时间tout的选择若Tout太长，浪费时间，131停止等待协议的信道利用率停止等待协议的信道利用率132数据链路层示例课件133连续ARQ协议目的：提高信道利用率。方法：发送端发送完一个数据帧后，不停下来等待应答帧，而是连续再发送数据帧。当收到否认帧NAK时，再控制重发。实现要求：数据帧需附加发送序号信息。否认帧附加出错的数据帧发送序号。常用协议：①回退N帧ARQ协议（gobackn）②选择重发ARQ协议（selectiverepeat）连续ARQ协议目的：提高信道利用率。134回退N帧ARQ协议（gobackn）①方式1：反馈否认帧NAK（含出错的数据帧发送序号）。再从出错的数据帧开始重传。要求：发送端要求有一个能存储N个数据帧的缓冲区。接收端只需能存储一个数据帧的缓冲。回退N帧ARQ协议（gobackn）①方式1：135②方式2：不反馈否认帧NAK。发送端采用超时机制。发送端每发送一个数据帧就启动该帧计时器，当收到确认帧后，计时器复位；如果直到超时还没有收到确认帧，则重发该数据帧及后继的帧。②方式2：136选择重发ARQ协议（selectiverepeat）目的：进一步提高信道利用率。方法：只重传出现差错的数据帧或者超时的数据帧。要求：在接收端要设置具有相当容量的缓存空间。选择重发ARQ协议（selectiverepeat）目的：137选择重发ARQ协议－工作原理示意图选择重发ARQ协议－工作原理示意图1385.4滑动窗口协议（SlidingWindowsprotocol）①当未被确认的数据帧数目太多时；只要有一帧出错，就有很多数据帧需要重传，因而增大开销。②为了对发送出去的大量未被确认的数据帧进行编号，每个数据帧的发送序号也要占用较多的比特数，因而又增大了开销。对于连续ARQ协议，采用了发送端不等待确认帧返回就可连续发送帧，存在问题：滑动窗口协议：对发送端已发送出去但未被确认的帧的数目加以限制。在发送端和接收端分别设置发送窗口和接收窗口。5.4滑动窗口协议（SlidingWindowspro139发送窗口（在发送端）目的：用来对发送端进行流量控制。发送窗口尺寸Ws：在还没有收到应答帧的情况下，发送端最多可以连续发送数据帧的个数。发送序号：一般采用n位bit进行编号（0～2n-1）。若n=3；则用3位bit进行编号（0～7）。发送窗口（在发送端）目的：用来对发送端进行流量控制。140·发送端只能连续发送窗口内的数据帧；·每收到一个确认帧后，发送窗口的前、后沿顺时针旋转一个号，并可以一个发送新的数据帧。·若未应答帧的数目等于发送窗口尺寸时，便停止发送新的数据帧。·发送端只能连续发送窗口内的数据帧；141接收窗口（在接收端）目的：用来控制可以接收哪些数据帧而不可以接收哪些帧。接收窗口Wr：只有当收到的数据帧的发送序号落入接收窗口内，才允许将该数据帧收下；否则，丢弃。接收窗口（在接收端）目的：用来控制可以接收哪些数据帧而不可以142如果Wr=1，意味着只能按顺序接收数据帧。如果Wr较大，有可能会出现数据帧的失序。差错情况：设Wr=1；若收到0号数据帧，接收窗口顺时针旋转一个号，并发出0号确认帧；准备接收1号数据帧。此时，如果收到的不是1号数据帧，而是0号数据帧，表明发出0号确认帧发送端没有收到，因此再发送一次0号确认帧，此时收到的0号数据帧必须丢弃，否则发生重复。若是2号数据帧，表明发送端发出的1号数据帧丢失，因此发送1号否认帧，让对方重新发送1号数据帧。如果Wr=1，意味着只能按顺序接收数据帧。143应答帧丢失情况应答帧丢失情况144应答帧被“篡改”情况:ACK→NAK应答帧被“篡改”情况:ACK→NAK145数据链路层示例课件146重叠问题在接收前后，接收窗口范围内的有效序号出现重叠。重叠问题在接收前后，接收窗口范围内的有效序号出现重叠。147避免重叠问题为了避免重叠问题，接收窗口尺寸Wr≤2n/2。避免重叠问题为了避免重叠问题，接收窗口尺寸Wr≤2n/2。148发送窗口的最大尺寸值发送窗口的最大尺寸值149累积确认方法接收端在连续接收若干个正确的数据帧以后，对最后一个数据帧发回确认帧。累积确认方法接收端在连续接收若干个正确的数据帧以150窗口控制协议的信道利用率窗口控制协议的信道利用率151窗口控制协议的信道利用率设：单程传输时延Td，数据帧发送时间Tf，数据传输率C，数据帧长度L，窗口尺寸Ws在正常传输情况下，忽略应答帧长度和处理时间：窗口控制协议的信道利用率设：单程传输时延Td，数据帧发送时152依据信道利用率进行窗口尺寸的选择优化原则：发送端收到窗口中第一个已发数据帧的确认时，正好发完窗口中的最后一个数据帧。Ws大于上述选择，则Cr=100%，但浪费缓冲区；Ws小于上述选择，则Cr<100%，发送端需要等待应答而使发送停顿。依据信道利用率进行窗口尺寸的选择优化原则：153示例例：卫星信道：单程传输时延Td＝250ms，数据传输率C＝50kb/s，数据帧长度L＝1000bit，在已知条件不变的情况下，设置L=160bit，信道利用率如何？示例例：卫星信道：154ARQ协议、连续ARQ协议的窗口尺寸ARQ协议：发送窗口Ws＝1，接收窗口Wr＝1连续ARQ协议:·回退N帧ARQ协议：发送窗口Ws＞1，接收窗口Wr=1。·选择重发连续ARQ协议：发送窗口Ws＞1，接收窗口Wr＞1，且Wr≤Ws。ARQ协议、连续ARQ协议的窗口尺寸ARQ协议：155重难点讲解与练习1流量和差错控制1)差错控制方法:A自动请求重发(AutomaticRepeatRequest,ARQ)B前向纠错2)形成两种重要的流控制A选择重发ARQ协议:只重发出错帧B后退N帧ARQ协议:退回到出错帧重难点讲解与练习1流量和差错控制156效率分析公式:1停等协议:假设线路不出错,则如出错概率为P,则(其中a=tp/tf,可理解为线路的帧计数长度)2选择重发ARQ协议,假设发送窗口的大小为W,则不出错时为:如果对出错进行重发,设出错概率为P,则效率分析公式:1573后退N帧:当W>=2a+1,N近似等于2a+1,则当W<2a+1,N=W.则3后退N帧:158例1:已知数据帧长为1000bit,帧头为64bit,数据速率为500kb/s,线路传播延迟为5ms,则1)信道无差错,采用停等协议,求利用率2)滑动窗口为大窗口,求窗口至少为多大?3)设P=0.01,用选择重发ARQ协议,窗口大小W=4,求利用率.解:1)a=Tp/TfTp=5Tf=1064/500a=5X500/1064=2.35E=0.182)所谓大窗口就是W>=2a+1,由上面知a=2.35故w>=2X2.35+1=5.7取w=6例1:已知数据帧长为1000bit,帧头为64bit,数据1593)P一般比较小,在分母看作为0,故得:由于w=4,2a+1=5.7,为小窗口,W=w(1-p)/2a+1=4X(1-0.01)/5.7=0.693)1605.5协议1.协议开发过程5.5协议1.协议开发过程161协议的形式描述描述方法：①有限状态机采用状态流程图进行描述。②事件状态表采用表格进行描述。③结构化程序采用程序代码进行描述。④Petri网模型采用状态流程图进行描述。协议的形式描述描述方法：162有限状态机模型FSMFSM协议描述方法也称状态转移图。特点：易懂、易理解和易于实现。组成：状态圆和有向弧。有限状态机模型FSMFSM协议描述方法也称状态转移图。163Petri网模型德国C.A.Petrit提出(1962,博士论文)。4个基本元素：位置：系统可能处于的状态；用圆圈表示。转换：改变状态；用线段表示。有向弧：位置与转换之间的相互依赖关系；用弧线表示。标记：系统当前处于