资源描述
本章将介绍：l数据链路层的基本概念；l两个重要的数据链路层流量控制方法：停止等待协议和连续ARQ协议；l差错控制方法：循环冗余校验；l连续ARQ协议的实现机制：滑动窗口机制；l数据链路层的具体协议：BSC、HDLC、PPPl区分“链路链路”和“数据链路数据链路”的概念。链路链路是一条无源的点到点的物理线路段，中间没有任何其他交换结节，又称物理链路物理链路。数据链路数据链路是除了有一条物理线路外，还施加了一些必要的通信协议来控制数据的传输。又称逻逻辑链路辑链路。l数据链路层的作用：在数据链路层协议的控制下，在不太可靠的物理链路上实现相邻结点之间的可靠传输实现相邻结点之间的可靠传输。l时期链路层的主要功能时期链路层的主要功能:1、链路管理、链路管理 当网络中的两个相邻结点要进行通信时，发送方必须知道接收方是否已经准备就绪。为此，通信双方必须先要交换一些必要的信息，建立一条数据链路，在传输数据时要维持数据链路，传完后要释放数据链路。l 帧同步帧同步在数据链路层，数据的传送单位是帧，数据一帧一帧地传送，帧同步是指接收方应当能从接收到的比特流中区分出一帧的开始和结束，不至错位。通过在帧的开始和结束处加帧标志来实现。3、流量控制、流量控制 发送方发送数据的速率必须使接收方来得及接收。因此必须控制发送方的速率。4、差错控制、差错控制差错控制广泛采用了编码技术，通过在帧中添加一定的校验位（冗余位）来实现。编码技术有两大类：(1)前向纠错前向纠错，接收方收到出错的帧后，能自动将其改正过来，但这种方法开销大，编码复杂，在计算机通信中很少采用。如海明码.(2)差错检测差错检测，一般是接收方检测到出错的帧后，将其丢弃，然后通知发送方重发。如循环冗余码.5、将数据和控制信息区分开、将数据和控制信息区分开 数据和控制信息封装在同一帧中，要有一定的措施使接收方能够区分开来。可通过规定帧的格式来实现。6、透明传输、透明传输透明传输指不管所传数据是什么样的比特组合，都能实现正确传输。如当所传数据中出现“帧标志”比特组合时，不能将其误认为是帧标志，而要当成数据，为此，必须采取一定的控制措施。7、寻址、寻址帧中必须封装有接收方的物理地址（MAC地址）。l停止等待协议是最简单但也是最基本的数据链路层协议。l4.2.1 不需要数据链路层协议的数据传输不需要数据链路层协议的数据传输两台计算机通过一条数据链路进行通信的简化模型如下：l当同时满足以下当同时满足以下两个条件两个条件时，不需要数据链路层协议：时，不需要数据链路层协议：(1)链路是理想的传输信道，链路是理想的传输信道，不会出错不会出错。(2)不管发送方以多快的速率发送，接收方都不管发送方以多快的速率发送，接收方都来得及收下来得及收下，并及时上交主机。并及时上交主机。 当接收方缓存的容量无限大且发送方的速率永远低于接当接收方缓存的容量无限大且发送方的速率永远低于接收方的接收速率时才可能。收方的接收速率时才可能。l4.2.2 具有最简单流量控制的数据链路层协议具有最简单流量控制的数据链路层协议保留上述的第一个假设，去掉第二个假设。保留上述的第一个假设，去掉第二个假设。为了使接收方的缓存在任何情况下都不会溢出，最简单为了使接收方的缓存在任何情况下都不会溢出，最简单的方法是发送方每发送一帧就暂停，接收方收到并处理的方法是发送方每发送一帧就暂停，接收方收到并处理完后通知发送方，发送方才发下一帧。完后通知发送方，发送方才发下一帧。这种由接收方控制发送方的发送速率是计算机网络中流这种由接收方控制发送方的发送速率是计算机网络中流量控制的基本方法。量控制的基本方法。l具有最简单流量控制的数据链路层协议算法如下：具有最简单流量控制的数据链路层协议算法如下：l发送方：发送方：l(1)从主机取一个数据帧；l(2)将数据帧送到数据链路层的发送缓存；l(3)将发送缓存中的数据帧发送出去；l(4)等待；l(5)若收到接收方发来的通知，则从主机取一个新的数据帧，然后转到（2）。l接收方：接收方：l(1)等待；l(2)若收到发送方发来的数据帧，将其送入数据链层的接收缓存；l(3)将接收缓存中的数据帧上交主机；l(4)向发送结点发送通知，表示已上交主机；l(5) 转到（1）。l两种数据传输情况对比图见书P73 图4-2l4.2.3实用的停止等待协议实用的停止等待协议l现在去掉前面的两个假定，讨论实用的数据链现在去掉前面的两个假定，讨论实用的数据链路层协议。设主机路层协议。设主机A 主机主机B，分以下几种情，分以下几种情况讨论：况讨论：l(1)B正确收到，向A发送一个确认帧ACK；l(2)B检测出帧在传输过程中出错，向A发送一个否认帧NAK，通知A重传出错的帧。l(3)A发送的数据帧在传输过程中丢失，或B发送的确帧在传输过程中丢失。会出现什么情况？方法是给每一帧编号方法是给每一帧编号，编号应既能识别出重复帧，又要尽可能短。如何编号最好？编号占用一个比特位，0 0和和1 1交替编号交替编号即可，为什么？l发送方发送方“死等死等”。l解决方法是：A每发送一个数据帧，就启动一个超时计时器超时计时器，在规定的时间内未收到B的任何应答，应重传该帧，重传时间不能设置过短或过长。l(4) 如果是B发送的确认帧在传输过程中丢失，则超时重传会使B收到两个同样的数据帧，此时应丢弃，但主机B如何识别出一个数据帧是否为重复帧重复帧？l4.2.4循环冗余检验（循环冗余检验（CRC）l用来检测帧在传输过程中有没有出错。用来检测帧在传输过程中有没有出错。lCRC的工作方法：的工作方法：在发送端产生一个循环冗余码，附加在信息位后面一起发送到接收端，接收端收到的信息按发送端形成循环冗余码同样的算法进行校验，若有错，需重发。 lCRC将数据块看成是一个多项式系数系列。将数据块看成是一个多项式系数系列。l如数据块:110011对应的多项式:M(X)=X5+X4+X+1双方约定一个生成多项式双方约定一个生成多项式，如P(X)=X4+X3+1，其系数系列为：11001 l利用两个多项式相除利用两个多项式相除，余数作为校验位，除法过程中所有的减法按模二算法模二算法（即异或运算）。 例：数据块M(X)为1010001101 ，生成多项式P(X)=X5+X4+X2+1，即110101，求CRClCRC的计算过程如下：的计算过程如下：l(1)设约定多项式P(x)为n阶，在数据块M(X)的未尾添加n个0，得到Xn n M(X)。l(2)用Xn n M(X)/ P(X)，得到余数R(X)。l(3)用Xn n M(X)+ R(X)，得CRC码。l 1 1 0 1 0 1 0 1 1 0Q商 110101) 1 0 1 0 0 0 1 1 0 1 0 0 0 0 0XnM1 1 0 1 0 1l 1 1 1 0 1 1l 1 1 0 1 0 1l 1 1 1 0 1 0l 1 1 0 1 0 1l 1 1 1 1 1 0l 1 1 0 1 0 1l 1 0 1 1 0 0l 1 1 0 1 0 1l 1 1 0 0 1 0l 1 1 0 1 0 1 l 0 1 1 1 0 R余数lCRC码为1 0 1 0 0 0 1 1 0 1 0 1 1 1 0 l接收方的处理过程：接收方的处理过程：l接收方用收到的信息，除以生成多项式，若除数为0，则传输中没有出错，否则，出错。l现在国际上有一些标准的约定生成多项式。l停止等待协议的算法如下：停止等待协议的算法如下：l发送方：发送方：l(1)从主机取一个数据帧；l(2)V(S) 0； 发送状态变量初始化l(3)N(S) V(S); 将发送状态变量的数值写入发送序号并 将数据帧送交发送缓存；l(4)将发送缓存中的数据帧发送出去；l(5)设置超时计时器l(6)等待以下三个事件中最先出现的一个；l(7)若收到确认帧ACK，则：l 从主机取一个新的数据帧；l V(S) 1- V(S)；更新发送状态变量，变为下一个序号l 转到（3），发送下一帧。l(8)若收到否认帧NCK，则转到（4），重传数据帧。l(9)若超时计时器时间到，则转到（4），重传数据帧。l接收方：接收方：l(1)V(R) 0;接收状态变量初始化，为欲接收的序号l(2)等待；l(3)当收到一个数据帧，检查有无传输差错(如用CRC)，l 若检查正确，则执行后续算法，否则转到(8)。l(4)若N(S)=V(R)，则执行后续算法；(序号正确)l否则丢弃此数据帧，然后转到(7) 为重复帧，发ACKl(5)将接收缓存中数据帧的数据部分上交主机；l(6) V(R) 1- V(R),更新状态变量，准备接收下一帧l(7)发送确认帧，并转到(2)；l(8)发送否认帧，并转到(2) 。Tp为传播时延，tf f为发送时间，tprpr为处理时间，ta a为ACK的发送时间， toutout为重传时间。当tprpr和ta a都远小于Tp时， tout out =2=2Tp停止等待协议ARQ的优点是简单，但效率低。tTtf ftoutouttptprprta atptprpr4.2.6停止等待协议中几个重要的时间关系停止等待协议中几个重要的时间关系l4.3.14.3.1连续连续ARQARQ的工作原理的工作原理l连续ARQ不是每发一帧就停下来等待确认，而是可以连续发送若干个帧后，才等待确认。l在连续发送的若干个帧中，如果某一帧出错，则其后发送的帧全部丢弃，从出错帧开始重发。l4.3.24.3.2滑动窗口的概念滑动窗口的概念l连续ARQ中连续发送帧的数量不能太大，因为：(1)出错是重传的帧数较多。(2)给帧进行编号时，序号要占较多的比特位，增大了开销。如何控制发送方的发送和接收方的接收？l发送窗口(WT)：在还没有收到对方确认信息的情况下发送端最多可以发送多少个数据帧。用来对发送端进行流量控制。停止等待协议中发送窗口的大小为1。l设发送序号用3个比特来编码，即发送序号可以从0-7，又假定发送窗口WT=5，发送窗口的规则如下：(1)发送窗口内是允许发送的帧，而不考虑有没有收到确认。右侧是不允许发送的帧。01234567012WT允许发送5个帧不允许发送的帧(2)每发送完一帧，允许发送的帧数就减1，但发送窗口的位置不变。如已发送了0号帧。01234567012WT还允许发送4个帧不允许发送的帧已发送(3)如果允许发送的5个帧都发送完了，但还没有收到任何确认，就不能再发送了，进入等待状态。01234567012WT已发送不允许发送的帧(4)每收到对一个帧的确认，发送窗口就向前滑动一个位置，如发送方已收到0、1和2号帧的确认。01234567012WT已发送并已收到确认不允许发送的帧已发送还允许发送3帧为了减少开销，接收端可以在连续收到好几个帧后，才对最后一个数据帧发确认信息，或自己有数据要发送时才对以前收到的数据帧加以捎带确认捎带确认。对某一数据帧的确认表示该帧及以前所有的数据帧均已某一数据帧的确认表示该帧及以前所有的数据帧均已正确收到正确收到。如上例中接收端可以只发对2号帧的确认，表示2号及0、1号均已正确收到。减少开销。l接收窗口(WR)：接收端允许接收的帧的序号。WR=1，接收窗口的规则如下：(1)只有当收到的数据帧的发送序号落在接收窗口内才允许接收，否则，丢弃。(2)每收到一个序号正确的帧，接收窗口就向前滑动一个帧的位置。同时可以向发送端发送对该帧的确认。01234567012WR准备接收0号帧不允许接收这些帧01234567012WR准备接收1号帧不允许接收这些帧已收到l发送窗口的最大值：当采用3个比特来编号时，可以编出8个不同的序号，发送窗口的最大值是不应为8？l不能为不能为8！l如果发送窗口W WT T=8，设发送方已发送完0-7号共8个帧。因发送窗口已满，发送暂停，等待确认。假定这8个帧已正确到达接收端，并且接收端已对这8帧发回确认帧。下面考虑两种不同情况：第一种情况是：确认帧正确到达了接收端，发送方又发送0-7号共8个新帧。第二种情况是：确认帧丢失，接收端超时后重传这先前发送的8个旧帧。接收端第二次收到编号为0-7的8个帧时，无法判定是8个新帧，还是重传的8个旧帧。因为它不知道上次的确认帧是不已丢失。当用n个比特编号时， W WT T 2n-1 l信道的利用率信道的利用率指扣除控制信息后的数据率与信道容量之比。还受出错重传影响，不可能达到100%，当信道不出错时，其值为数据位/帧长。l最佳帧长最佳帧长（1）当帧长帧长取得很短很短时，控制信息所占的比重增大，开销增大，信道利用率降低。（2）当帧长帧长取得很长很长时，帧在传输过程中出错的概率增大，重传次数增大，也会使信道利用率降低。l数据帧长的选择帧长的选择与信道的好坏信道的好坏有很大的关系。 当信道质量好时，帧长应该长还是短？ 当信道质量不好时，帧长应该长还是短？ARQl为进一步提高信道利用率提高信道利用率，可只重传出错帧或超时帧。必须做到：（1）加大接收窗口加大接收窗口，以便先收下发送序号不连续但仍处在接收窗口中的帧。（2）接收端要设置相当容量的缓存空间相当容量的缓存空间，这样不够经济。所以目前应用较少，但目前随着存储器价格的下降，受到更多的重视。 接收窗口的最大值受下式约束： WR 2n/2 因WT +WR 2n l4.5.1HDLC概述l数据链路控制规程分两大类：（1）面向字符面向字符的数据链路控制规程 典型代表有IBM的BSC二进制同步通信规程。 特点：所传数据及控制信息都必须是规定字符集（如ASCII码）中的字符,且控制字符很多。 采用停止等待协议，效率低。（2）面向比特面向比特的数据链路控制规程 典型代表有ISO的HDLC高级数据链路控制规程。 特点： 所传数据可以是任意的比特流。 采用连续ARQ，效率高。lCCITT将HDLC修改后称为链路接入规程LAP，并作为X.25的数据链路层协议，不久后又将LAP改为LAPB平衡型链路接入规程。lHDLC可适用于链路的两种基本配置，即平衡配置与非平衡配置。l非平衡配置的特点非平衡配置的特点是站有主站和从站之分，由一个主站控制整个链路的工作，只有主站才能发起向次站的数据传输，而次站只有在主站对它进行轮询时，才能以响应帧的形式回答主站。l平衡配置的特点平衡配置的特点是站是复合站，同时具有主站和从站的功能，能平等地发起数据传输。标志标志F地址地址A控制控制C信息信息Info帧检验序帧检验序列列FCS标志标志FlHDLC的帧结构比特：比特：8 8 8 可变可变 16 8检验区间检验区间透明传输区间透明传输区间1、各字段的意义1、标志位Fl作用：用来标识帧的开头和结尾标识帧的开头和结尾。l标志位F为：01111110l透明性处理： 当两个标志位之间碰巧出现了和标志位F一样的比特组合时，接收方会误认为帧结束了。 为了避免出现这种错误，HDLC采用零比特填充法。 发送方在数据连续连续5个个1之后自动插入一个之后自动插入一个0，这样数据中就不会出现6个连续1。 接收方在数据连续5个1之后自动去0。例如：要发送的数据为： 010001010实际发送的数据为： 010001010接收方去0： 010001010l采用零比特填充法就可传送任意的比特流。2、地址字段Al在平衡方式时，填入接收方的地址。全全1为为广播方式广播方式，全0为无效地址，因此，有效地址为254个。l当用户数很多时，可用地址字段的第一个比特表示扩展比特，当该位为1时，表示后面还有地址字段，当为0时，表示这已是最后一个地址字段了。3、帧检验序列FCS 为CRC的校验码。4、控制字段C 长8位，根据前两位的取值，将HDLC帧分为三大类：信息帧信息帧I、监督帧、监督帧S和无编号和无编号帧帧U。 控制字段的结构如下：比特序号1 2 3 4 5 6 7 8信息帧I0N(S)P/FN(R) 监督帧S10SP/FN(R)无编号帧U11MP/FN(R)2、信息帧l第一位为0，表示该帧为信息帧。l第24位N(S)为当前发送的信息帧的序号发送的信息帧的序号l第68位N(R)为接收序号接收序号，即接收方期望收到的帧的序号。 N(R) 带有确认的意思，它表示序号为N(R)-1(mod 8)的帧以及在这之前的各帧都已正确收到。如N(R) 为4，意思是？l通信的每一方都有一个N(S)和N(R)。l在全双工通信中，收发双方还设置了两个状状态变量态变量V(S)和和V(R)，由这两个状态变量的值确定发送序号N(S)和接收序号N(R) 的值。l每从主机取一帧新的数据就要将V(S)和V(R) 的值分别写入帧的控制字段N(S)和N(R) 中。l每发完一帧V(S)+1(mod 8)。l当出错重传时，只需从缓存队列中取出已发送过的旧帧，重新发送，帧中的序号帧中的序号N(S)仍仍为原序号；为原序号； V(S)不变；不变；l每收到一个无差错的信息帧V(R)+1(mod 8)。l当出错重传时， N(R) 必须与必须与V (R)的当前值的当前值一致一致。l信息帧中设置N(R) 的目的是不必专门为收到的信息帧发送确认帧，可以在本站有信息发送时，将确认信息捎带捎带走。提高信道利用率。l控制字段的第5个比特是探询/终止比特，即P/F。主站发出的命令帧中若将P置为1表示要求对方立即响应。在平衡链路中若将F置1，表示数据发送完毕。3、监督帧Sl第第12比特为比特为10。监督帧共有四种，取决于34比特的值。第34比特帧名功能00RR接收准备就绪准备接收下一帧确认序号为N(R)-1及以前的各帧10RNR接收未就绪暂停接收下一帧确认序号为N(R)-1及以前的各帧01REJ拒绝从N(R) 起的所有帧都被否认，但确认序号为N(R)-1及以前的各帧11SREJ选择拒绝只否认序号为N(R)的帧，但确认序号为N(R)-1及以前的各帧，较少用。l监督帧不包含数据，不需要发送序号N(S)。lRR和RNR还具有流量控制作用。4、无编号帧U第第12比特为比特为11，无编号帧不带V(S)和V(R)字段,而用5位，即3、4、6、7、8来表示不同功能的无编号帧，无编号帧主要起控制作用。如要与对方建立连接，可发SABM（请求发送）帧，对方同意发UA确认帧，断开连接发DISC帧。l用户拨号上网的示意图l用户拨通ISP的号码(如163或169),用户机中的TCP/IP客户进程客户进程就和ISP的路由器中的路路由选择进程由选择进程建立了一个PPP连接；ISP识别用户名和口令后,用户获得一个临时的IP地址,当用户结束通信时,该IP地址被回收。lPPP协议由如下三个部分组成：（1）一个将IP数据报封装数据报封装到串行链路的方法。IP数据报在PPP帧中是其数据部分。（2）一个建立、配置和测试数据链路连接的链路控制协议LCP。双方可协商一些选项。（3）网络控制协议NCP。标志标志F(7E)地址地址A(FF)控制控制C(03)协议协议信息信息(IP数据数据报报)帧检验帧检验序列序列FCS标志标志F(7E)字节：字节：1 1 1 2 1500字节字节 2 1l1、与HDLC比较，PPP的特点：（1）地址为固定值，控制字段与U帧相同，帧不使用编号，增加了一个协议字段，表示上层使用的协议，如IP，则为0 x0021。l2、PPP是面向字符面向字符的协议。l3、透明性处理方法：在同步传输链路中采用位填充（与HDLC相同），在异步传输链路中采用字符填充字符填充，将(0 x7E)转换成(0 x7D,0 x5E)。l4、PPP不提供可靠的传输服务不提供可靠的传输服务。当CRC检验出帧出错时，只简单丢弃，其可靠性由高层来负责。目的是为了提高效率。lPPP建立连接过程：（1）拨号，建立起物理连接。（2）PC机向路由器发LCP（封装成PPP帧），协商PPP参数，如最大帧长，并鉴别用户身份。建立起数据链路层的连接。（3）接着进行网络层配置，由NCP给PC机分配一个临时的IP地址。lPPP释放连接的过程则正好相反。l使用PPP协议的状态图 见书P92，图4-14l复习l作业P93 12，16，17
展开阅读全文