[理学]计算机网络技术第3章.ppt

第3章 数据链路层,导入,PPP协议是目前Internet上使用最为广泛的点对点数据链路层协议。 什么是数据链路层？其功能是什么？它包括哪些设计要点和关键技术？数据链路层协议包含哪些基本类型和具体实现方法？,主要内容,3.1 数据链路层的基本概念 3.2 差错控制编码技术 3.3 数据链路层协议 3.4 数据链路层协议示例,3.1 数据链路层的基本概念,3.1.1 链路和数据链路 3.1.2 数据链路层为网络层提供的服务 3.1.3 数据链路层设计要点,数据链路层属于计算机网络的低层，数据链路层的主要功能是在不可靠的物理线路上实现数据的可靠传输，即数据链路层提供网络中相邻节点之间的可靠的数据通信。 数据链路层按使用信道类型的不同可以分为点对点信道的数据链路层和广播信道的数据链路层两种。本章主要介绍前者。,3.1.1 链路和数据链路,链路，又叫物理链路，是一条无源的点到点的物理线路，中间没有任何交换节点。 物理链路加上必要的通信协议(规程)，或者说把实现通信协议（规程）的硬件或软件加在链路上，就构成了数据链路，也称逻辑链路。,3.1.2 数据链路层为网络层提供的服务,设立数据链路层的主要目的 将原始的、不可靠的物理线路变为对网络层无差错的数据链路。为了实现这个目的，数据链路层必须实现链路管理、成帧与透明传输、流量控制、差错控制等功能。 数据链路层必须实现链路管理、成帧与透明传输、流量控制、差错控制等功能。 数据链路层为网络层提供的服务中最主要的是 将数据从源主机的网络层传输到目的主机的网络层。,数据链路层提供以下3种可能服务,1. 无确认的无连接服务 当线路通信质量高(错误率很低)时，或在实时通信中，此类服务是很合适的。 目前，绝大多数局域网中均采用此项服务。 2. 有确认的无连接服务 数据链路层上提供确认只是一种优化，而永远不应该是一种要求。此类服务用在不可靠的无线信道上是非常适合的。 3. 有确认的面向连接服务 数据链路层的面向连接的服务为网络层提供了可靠的数据传输服务。 面向连接的服务的数据传输要经过3个不同的阶段：建立连接、数据传输和释放连接。,3.1.3 数据链路层设计要点,组帧与帧同步 透明传输 流量控制 差错控制 寻址,组帧与帧同步,在数据链路层，数据传送的基本单位是帧 。 组帧主要是便于进行错误检测和纠正，在某些情况下可提高传输效率。 帧同步是指接收端应当能从收到的比特流中准确地区分出一帧的开始和结束的位置。 网络传输中很难保证计时的正确和一致（很难保证收发双方的时钟能精确一致），所以采用依靠时间或时间间隔关系来标识一帧的开始和结束位置的方法显然是不可行的。,常用的有4种帧同步方法,字节计数法 字符填充首尾定界法 比特填充首尾定界法 物理层违例编码法,透明传输,透明传输就是不管所传数据是什么样的比特组合（字符型数据或二进制数据），都应当能够在链路上安全可靠地传输。,非透明传输举例,字节填充法解决透明传输问题的示例,比特填充法解决透明传输的问题示例,流量控制,流量控制实际上是对发送方数据流量的控制，使其发送速率不至于超过接收端的处理能力。 当接收端来不及接收时，就必须及时控制发送端发送数据的速率，以使收发双方达到匹配。 流量控制常用的方法有两种。 基于反馈的流量控制（Feedback-Based Flow Control） 基于速率的流量控制（Rate-Based Flow Control）,流量控制并不是数据链路层特有的功能，许多高层协议也提供流量控制功能，只不过流量控制的对象不同而已。 对于数据链路层来说，控制的是相邻两节点之间数据链路上的流量，而对于运输层来说，控制的则是从源主机到目的主机之间端对端的流量。,差错控制,前向纠错（Forward Error Correction, FEC） 即接收方收到有差错的数据帧时能自动将差错改正过来。 这种方法的开销较大，不适合于计算机网络通信。 自动请求重发(Automatic Repeat reQuest, ARQ) 即接收方如果检测出收到的帧中有差错，就让发送方重复发送这一帧，直到接收方正确收到这一帧为止。 这种方法在计算机网络通信中是最常用的。 传输差错可分为两大类：一类是比特差错；而另一类就是出现了帧丢失、帧重复或帧失序。 要解决这两类传输差错问题，从而实现数据链路层的可靠传输，必须在差错检测技术的基础上，增加定时器、帧编号、确认和重传机制。 目前因特网上广泛使用的数据链路层协议已不再使用确认和重传机制了，即不提供向上的可靠传输服务了。,寻址,必须保证每一帧都能送到正确的目的站，接收方也应知道发送方是哪个站。,3.2 差错控制编码技术,3.2.1 奇偶校验码 3.2.2 循环冗余校验码 3.2.3 海明码,纠错码（Error-Correcting Code）和检错码（Error-Detecting Code）是实现差错检测和纠正的两种不同的差错控制编码技术。 纠错码（Error-Correcting Code）和检错码各有优缺点。 比较常见的检错码主要有奇偶校验码和循环冗余校验码，常见的纠错码主要有海明码、正反码等。,3.2.1 奇偶校验码,奇偶校验码 是通过增加冗余位来使得码字中“1”的个数为奇数（奇校验）或偶数（偶校验）的编码方法。 奇偶校验码可分为垂直、水平、水平垂直奇偶校验等几种方式,垂直偶校验,水平偶校验,水平垂直偶校验,3.2.2 循环冗余校验码 （Cyclic Redundancy Check, CRC）,CRC又叫多项式编码（polynomial code） 基本思想是：将比特串看成是系数为0或1的多项式。一个k比特构成的帧看作是一个k-1次多项式系数列表，该多项式共有k项，从xk-1到x0，这个多项式的最高阶为k-1。 如比特串110011共有6位，对应一个共有6项的多项式，其系数分别为1、1、0、0、1和1，即x5+x4+x+1（1*x5+ 1*x4+ 0*x3+ 0*x2+ 1*x1+ 1*x0）。 多项式的算术运算采用模2运算法则。按照它的运算法则，加法不进位，减法不借位，加法和减法两者都与异或运算相同，因而计算结果相同。 CRC具有较强的检错能力，可以检测出所有的奇数位错、双比特错、小于等于校验和长度的突发错。,CRC进行编码和校验的原理,(1) 发送方和接收方事先约定一个生成多项式G(x)，生成多项式的最高位和最低位必须是1。 (2) 发送端根据生成多项式G(x)去计算要附加在信息帧尾部的冗余位（校验和，Checksum）。计算校验和的算法如下。 假设信息帧的比特数为k位，对应的多项式为K(x)，G(x)为r阶。在信息帧的低位端加上r个0，此时信息帧的比特数变为k+r位，对应的多项式为xrK(x)。 按模2除法，用对应于G(x)的比特串去除对应于xrK(x)的比特串，从而得到一个小于等于r位的余数。这个余数便可作为校验和。 (3) 将校验和附加在k位信息帧尾部，组成一个新的帧，由发送端发送给接收端。假设这个新的帧对应的多项式为T(x)，其显然能被G(x)除尽。因为这个新的帧的多项式T(x)所对应的比特串可以看作是由多项式xrK(x)对应的比特串减去余数而得到的。 (4) 当接收方收到带有校验和的帧时，用G(x)去除它，如果余数不为0，则说明传输过程中出现了错误；如果余数为0，则认为传输无差错。,发送端生成带校验和的CRC帧的过程举例,信息帧 1101011011 生成多项式 x4+ x+1,3.2.3 海明码,海明码是由R.Hamming在1950年首次提出的，是一种可以纠正一比特错的编码。 简单的奇偶校验中的一个重要的结论 信息位为k=n-1位an-1an-2a1，加上一个偶校验位a0，构成一个n位的码字an-1an-2a1a0。在接收端校验时，可按关系式：S0=an-1+an-2+a1+a0（模2运算）来计算，若S0=0，则认为无错；若S0=1，则肯定有错。上面关系式称为监督关系式，S0称为校正因子。,海明码原理推导,对上面结论的分析 在上面偶校验情况下，只有一个监督关系式，一个校正因子，其取值只有0或1两种可能，分别代表了无错和有错两种情况，但却不能指出差错所在的位置。不难设想，如果增加冗余位，让每个冗余位分别与信息中的某些位构成一个偶校验关系，则就会相应地增加监督关系式和校正因子，就能区分更多的情况。 不难推出，信息位为k位，增加r位冗余位，构成n=k+r位码字。若希望用r个监督关系式产生的r个校正因子来区分无错和在码字中的n个不同位置的1位错，则要求：2rn+1或2rk+r+1,k=4时，海明码产生基本原理示例,构造S2S1S0取值与错码位置的对应关系,也可以规定成另外的对应关系，这并不影响讨论的一般性,根据上表推出监督关系式,令校正因子都等于零，代入已知信息位，计算出冗余位,K=4时由信息位算得的冗余位,基于上面构造的海明码，可得到各种信息位与冗余位的对应关系,海明码纠正突发性错误,海明码只能纠正1位错，为了纠正在传输过程中出现的突发性错误，可以采用如下的技巧或方法。将k个连续的码字排成一个矩阵，每行一个码字，传输数据时每次发送一列，从左边的列开始，如图所示。,海明码生成方案,海明码是一种可以纠正一位差错的编码。它是利用在信息位为k位，增加r个冗余位，构成一个n=k+r位的码字，然后用r个监督关系式产生的r个校正因子来区分无错和在码字中的n个不同位置的1位错。它必须满足 2rn+1或2rk+r+1 海明码的生成方案主要有两种，二者的主要区别是对冗余位在生成后的码字中的位置处理方式不一样。 前面已经介绍了第一种方案，它是将r个冗余位顺序放在k个信息位的后面， 另一种方案叫顺序生成法，是将r个冗余位分别放在k+r位的码字中位置（按位从右往左数）为20到2r-1的那些位上，其余的用信息位来填充。,海明码的生成与接收过程,(1) 假设信息位为k位，将k的值代入公式（2rk+r+1）计算出冗余位的个数r的取值范围，从中选择一个（通常会取最小的那一个），以方案一或顺序生成法对r个冗余位进行处理，构造一个n=k+r的码字。 (2) 约定r个校正因子组成的二进制序列Sr-1S1S0的取值与错码的位置对应关系（通常将其表示成表格的形式）。 (3) 确定监督关系式。 (4) 令监督关系式中所有的校正因子均为0，同时将信息位的值代入相应的监督关系式，从而计算出各冗余位的值。 (5) 将信息位与冗余位组成的码字发送给接收端。 (6) 接收端将其收到的码字，利用监督关系式进行校验。如果Sr-1S1S0 =0，则表示没有错误。如果Sr-1S1S0不为0，则根据约定的Sr-1S1S0的取值与错码的位置对应关系确定出错码的位置，对错码位进行取反，得到正确的码字。,3.3 数据链路层协议,为了便于说明，采用一个简化的通信模型，把数据链路层以上的各层抽象为一个主机，而把物理层和传输媒体抽象成一条简单的链路。 假设全双工通信，则收发两端要同时设有发送和接收缓冲区。,理想传输条件下的数据传输,所谓的理想传输条件是指满足以下两个假定的理想化状态。 (1) 链路是理想的传输信道，不会产生差错，数据帧传输过程中不会出错也不会丢失。 (2) 不管发送端以多快的速度发送数据帧，接收端总是来得及接收，并及时上交主机。,在这样的理想传输条件下，不需要采取任何措施就能实现可靠传输，即不需要任何数据链路层协议就可保证可靠传输。 然而实际的网络都不具备以上两个理想条件,3.3 数据链路层协议,3.3.1 简单的停止等待协议 3.3.2 实用的停止等待协议 3.3.3 连续ARQ协议 3.3.4 选择重传ARQ协议 3.3.5 滑动窗口(Sliding Window)协议,3.3.1 简单的停止等待协议,简单的停止等待协议的工作原理 假定链路是理想的传输信道，不会产生差错，数据帧传输过程中不会出错也不会丢失。在发送端，每发送完一个数据帧就暂停发送，等待着接收端的确认。如果收到了来自接收端的确认帧，就继续发送下一帧。在接收端每收到一个无差错的帧，就将其交给上层，并向发送端发送一个确认帧。,简单的停止等待协议算法,3.3.2 实用的停止等待协议,实用的停止等待协议就是在理想传输条件的两个假定都不成立的情况下，保证数据可靠传输的一种协议。 在简单的停止等待协议中 通过引入“确认”解决了流量控制问题，这种方法对于实用的停止等待协议同样适用 。 实用的停止等待协议还要处理数据帧在传输过程中出现的差错，主要包括数据帧出错、数据帧丢失、确认帧丢失等几种情况。,数据帧出错时的两种解决方法,为了进行重传，在发送端必须暂时保存已发送过的数据帧的副本，直到收到对已发送帧的确认帧为止。 当通信质量太差时，可能要进行多次重传，但当重传达到一定的次数后，应立即停止，并向高层报告。 超时定时器设置的超时时间应仔细选择确定。,两种不同的帧丢失的解决方法,超时重传与确认帧丢失的使用可能会引入了新的问题-重复帧 为解决重复帧的问题，引入了给数据帧编号的方法 任何一个编号系统的序号所占用的比特数一定是有限的，经过一段时间后序号就会重复。 序号占用的比特数越少，数据传输的额外开销就越小,实用的停止等待协议算法,算法描述中，几个参数的意义如下 V(S)是发送端的状态变量，用来对发送端将要发送的数据帧进行编号； V(R)是接收端的状态变量，用来表示接收端所期望接收到的数据帧的序号； N(S)是数据帧的帧编号。 另外，对于数据帧出错的处理，是使用超时重传的方法，而没有采用向发送端发送否定确认帧的方法。,在发送端,(1) 从主机取一个数据帧。 (2) V(S)取0（发送状态变量V(S)初始化）。 (3) 令N(S)等于V(S)（将发送状态变量的数值写入数据帧中的发送序号N(S)，将数据帧送交发送缓冲区）。 (4) 将发送缓冲区中的数据帧发送出去（发送缓冲区中保留此数据帧的副本）。 (5) 设置超时定时器（选择适当的超时时间）。 (6) 等待（等待以下步骤中的两个事件中最先出现的一个）。 (7) 收到确认帧ACKn，若n=1-V(S)，则（接收方已经正确接收了发送端发出的数据帧，并给出了确认）从主机取一个新的数据帧；令V(S)等于“1-V(S)”（更新发送状态变量，使用下一个序号）；转到执行步骤(3)。否则，丢弃这个确认帧，转到执行步骤(6)。 (8) 若超时定时器的时间到，则转到执行步骤(4)（重发数据帧）。,在接收端,(1) V(R)取0（接收状态变量初始化，其数值等于欲接收的数据帧的序号）。 (2) 等待。 (3) 当收到一个数据帧，检查数据帧是否出错（通常使用CRC进行检测）。若检查结果正确无误，则转到执行步骤(4)；否则，丢弃此数据帧，转到步骤(2)； (4) 若N(S)=V(R)（收到了所期望的数据帧），将收到的数据帧中的数据部分送交主机，转到执行步骤(5)。否则，丢弃此数据帧，然后转到执行步骤(6)；（丢弃的帧为重复的帧）。 (5) 使V(R)等于“1-V(R)“（更新接收状态变量，准备接收下一个数据帧）。 (6) 令n= V(R)，发送确认帧ACKn，并转到步骤(2)。（期望接收n号帧，在它之前的帧收到了）,实用的停止等待协议算法要点,(1) 发送端每发送一个数据帧，都要将发送状态变量V(S)的值（0或1）写到数据帧的发送序号N(S)上。只有收到已发送帧的确认帧后，才能更新发送状态变量V (S)（1变为0，或0变为1），并发送新的数据帧。 (2) 接收端每接收到一个无差错的数据帧，就要将发送端在数据帧上设置的发送序号N(S)与本地的接收状态变量V(R)进行比较。若二者相等就表明是所期望的数据帧，就收下，并发送确认。否则为重复帧，必须丢弃，但这时仍需要向发送端发送确认帧ACKn，而接收状态变量V(R)和确认序号n都不变，即重发上次的确认帧。 (3) 发送端在发送完数据帧时，必须在其发送缓冲区中保留已发送数据帧的副本，以便在出现差错时进行重发。只有在收到接收端发来的确认帧，表示已经正确接收数据帧时，才能清除这个副本。,3.3.3 连续ARQ协议,连续ARQ协议的工作要点 发送端每发送完一个数据帧后，不是停下来等待接收端的确认帧，而是可以连续再发送若干个数据帧。如果在此过程中收到了接收端发来的确认帧，那么还可以继续发送数据帧。由于减少了等待时间，整个通信的吞吐量就提高了。,连续ARQ协议的工作原理示例,注意： 接收端只能按顺序接收数据帧。 连续ARQ又称为Go-back-N ARQ，意思是当出现差错必须重传时，要向回走N个帧，然后再开始重传。 连续ARQ要求发送端的发送缓冲区必须能缓存多个数据帧，而接收端的缓冲区只需要能容纳一个数据帧就足够了。 数据帧丢失与数据帧出错时的情况是基本相同的。 数据帧的确认帧丢失了，则情况较为复杂 。,连续ARQ协议的工作原理：数据帧出错,3.3.4 选择重传ARQ协议,为了进一步提高信道的利用率和传输效率，可以设法只重传出错的数据帧或者是超时的数据帧。此时必须加大接收端的缓冲区使其能容纳多个数据帧，以便接收端先缓存那些正确的数据帧（发送序号可能是不连续的），等到所缺序号的数据帧收到之后再一并送交主机。,选择重传ARQ协议的工作原理示例,选择重传ARQ协议可避免重传那些本来已经正确到达接收端的数据帧，但是必须付出的代价：在接收端需要设置具有相当容量的缓存空间 数据帧的确认帧丢失的情况较为复杂,选择重传ARQ协议示意图：数据帧出错,3.3.5 滑动窗口(Sliding Window)协议,在使用连续ARQ协议时，如果发送端一直没有收到对方的确认，那么实际上发送端并不能无限制的发送数据帧，其原因如下。 (1) 当未被确认的数据帧的数目太多时，只要有一帧出错或丢失，就会有很多的数据帧需要重传，这必然浪费很多时间，增大了开销。 (2) 为了对所发送的大量数据帧进行编号，每个数据帧的发送序号也要占用较多的比特，这样又增加了一些不必要的开销。 在连续ARQ协议中必须将已发送出去、但未被确认的数据帧的数目加以限制，这就是滑动窗口协议所要讨论的内容。,发送窗口与接收窗口,加入适当的控制机制，循环使用已收到确认的那些帧的序号，在发送端和接收端分别设定“发送窗口”和“接收窗口”。 发送窗口用来对发送端进行流量控制，而发送窗口的大小Ws代表在还没有收到对方确认的条件下发送端最多可以发送多少个数据帧。 接收窗口是为了控制哪些数据帧可以接收而哪些帧不可以接收。在接收端，只有当收到的数据帧的发送序号落入接收窗口内才允许将该数据帧收下。 只有在接收窗口旋转（滑动）时，发送窗口才有可能旋转（滑动）。但发送端如果没有收到已发送的那些帧的任何确认，同样也不会旋转（滑动）。接收窗口保持不动时，发送窗口无论如何也不会旋转（滑动），正因为收发两端的窗口按照以上规律不断旋转（滑动），因此这种协议被称为滑动窗口协议。,滑动窗口协议示例-3比特编号,注：可以用水平窗口和圆形窗口两种方法来表示发送与接收窗口。,发送端,接收端,发送窗口的最大值讨论,3个比特可编出8个不同的序号 发送窗口的最大值似乎应当是8。 其实不然，设置发送窗口为8将使协议在某些情况下无法工作。 如图(b)所示，发送窗口Ws=8将导致协议失败,发送窗口应满足的约束关系,如图所示，采用3个比特供数据帧的序号使用，WS=6，WR=3。,根据当前接收窗口的情况，只能推测发送端发送窗口的可能位置为 。 接收端在收到一个数据帧时，必须在下列3种情况中做出正确无误的选择。 (1) 是所期望接收的数据帧。 (2) 是重复帧（已对此帧发过确认帧，且已交付给主机）。 (3) 是序号错误的超前帧。,发送窗口应满足的约束关系（续）,对于图中的位置，应要求在WS+WR的范围内无重复序号 对于位置，要求在WS的范围内无重复序号 对于位置，除了要求在WS的范围内无重复序号外,还要求发送端重发的那些数据帧的序号不能与WR的范围内的序号重复 综合以上3种要求可知，当用n个比特进行编号时，发送窗口的大小WS和接收窗口的大小WR必须满足WS+WR2n (3-1) 对于停止等待协议，WS=1，WR=1，根据公式(3-1)可知n1 对于连续ARQ协议，WR=1，根据公式