计算机网络第4章

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第四章 数据链路层,本章学习目标,链路、数据链路的概念,数据链路层的功能,停止等待协议的工作原理与过程,数据链路层是如何进行差错控制的,数据链路层流量控制的意义与方法,面向比特数据链路层协议HDLC的帧结构,PPP链路协议的帧结构,4.1 数据链路层基本概念,数据链路(逻辑链路)与链路(物理链路)区别,链路：是一条无源的点到点的物理线路段，中间没有任何其他的交换节点，是一条通路的一个组成部分,数据链路除链路外，还必须有一些必要的规程控制数据的传输。因此，数据链路比链路多了实现通信规程所需要的硬件和软件,*采用复用技术时，一条链路上可以有多条数据链路,*,数据链路层的作用：通过数据链路层协议，在不太可靠的物理链路上实现可靠的数据传输,4.1 数据链路层基本概念,数据链路(逻辑链路)与链路(物理链路)区别,示意图,链路控制,节点,链路控制,节点,数据链路,Modem,Modem,链路,数据传输,4.1 数据链路层功能,具体功能：,1、链路管理：当网络中的两个结点进行通信时，发送方必须确知接收方是否已处在准备接收状态。也即,数据链路的建立、维持和释放,2、帧的透明传输。,为了向网络层提供服务，数据链路层必须使用物理层提供给它的服务。物理层所做的工作是接收一个原始的比特流，并准备把它交给目的端，物理层并不能进行完好的数据校验，一直要到数据链路层才进行校验。,对于数据链路层，通常的方法是把比特流分成离散的帧，并对每一帧计算出校验和，当帧到达目的地后重新计算校验和，相符无差错，不相符则有差错。,帧同步的方法：带字符填充的,首尾界符法,，带位填充的,首尾标志法,。,4.2 数据链路层功能,具体功能：,3、流量控制：协调发送方与接收方的工作。具体来说就是限制发送方所发出的数据流量，使其发送速率不要超过接收方能处理的速率,4、差错控制：接收方可通过校验帧的差错编码，判断接收到的帧是否有差错。保证所有的帧最终都能按照正确的顺序交付给目的机器的网络层。,5、寻址：在多点连接的情况下，保证每一帧都能送到正确的目的站。接收方应知道发送方是那个站。,6、将数据和控制信息区分开,4.3 差错控制编码,噪声的概念,数据传输过程中线路上的各种干扰，称为噪声。可分为随机噪声和冲击噪声：,随机噪声：由信道本身特征引起的热噪声,冲击噪声：外界突发的短暂原因,4.3 差错控制编码,差错的分类,由两种噪声的引起了两种差错,随机差错,提高信噪比,突发差错,信息速率很高往往影响一串码元,强度很大，线路无能为力，是重要原因,4.3 差错控制编码,差错检测方法,差错控制编码,通常有两种类型,检错码：能自动发现，但不能纠正错误的编码,纠错码：能自动发现，能自动纠正错误的编码,4.3 差错控制编码,常用的差错控制编码CRC,CRC(循环冗余校验码),原理：发送端按照某种算法产生一个循环冗余码，附加在信息后面一并发出，接受端接受后按照同样的算法由信息位产生循环冗余码，并将两个冗余码进行比较，若一致则无差错，否则说明传输有错。,4.3 差错控制编码,循环冗余校验所使用的算法,任何一个二进制数据串组成的代码可以用一个多项式来表示。具体表示方法为：,多项式中的各项系数二进制代码中的0，1,各项的次数码元在代码中的位置,例如：10101对应的多项式为：,1*x,4,+0*,x,3,+1*,x,2,+0*,x,1,+1*,x,0,=,x,4,+ 0 +,x,2,+0 +1*,1,= x,4,+,x,2,+1,4.3 差错控制编码,循环冗余校验所使用的算法,几个概念,信息多项式M(x),将发送的信息表示成多项式形式,生成多项式G(x),发送双方事先约定好的多项式,冗余多项式R(x),将冗余位表示成多项式形式，冗余位(r为冗余位数)的产生靠生成多项式G(x)。,R(x)是M(x)*x,r,/ G(x)所得到的余式,Q(x),是M(x)*x,r,/ G(x)所得到的商式,发送多项式T(x), T(x)= M(x)*x,r,+,R(x),结论：,发送多项式T(x) 一定能够被生成多项式G(x)整除,4.3 差错控制编码,循环冗余校验所使用的算法,解释,r的求法？,R就是余数的位数,二进制除法中，余数比除数少一位,模2运算规则,加法运算不进位，减法和加法一样，按加法规则运算,4.3 差错控制编码,循环冗余校验所使用的算法,模2运算示例,4.3 差错控制编码,编码信息为1101011011， 采用生成多项式G(X)=X,4,+X+1 ，求CRC发送多项式及其代码。,4.3 差错控制编码,差错处理,自动请求重发(ARQ),检错控制编码,空闲请求重发,停止等待法,连续请求重发,前向纠错(FEC),纠错控制编码,4.2 停止等待协议,两个结点数据链路层间的通信模型：,理想链路的通信。,实际链路的通信：采用停止等待协议保证数据通信双方的协调工作。,链,路,层,主,机,A,链,路,层,主,机,B,4.2 停止等待协议,(1) 不需要数据链路层协议的数据传输,*数据链路层接收到一个分组，就会在其上增加一个数据链路层的帧头和帧尾，包装成一个帧。这样，帧就是由嵌入的分组和一些控制信息组成的。随后，把帧传输给对方的数据链路层。,理想化数据传输：,假定1：所传送的数据不会出错和丢失,假定2：传送和接收方的网络层一直处于就绪状态。接收方链路层处理时间可以忽略不计，接收方缓冲空间为无限大,4.2 停止等待协议,(2) 具有最简单流量控制的数据链路层协议,去掉第二个假定：面临的问题是,如何防止发送过程发送过快，使接收过程来不及处理,。,具体的讲：如果接收数据的过程(从物理层到网络层)需要,t的时间，则发送过程则必须以低于每,t时间一帧的平均速率进行传输,更进一步讲，如果在接收方的硬件中没有自动的缓冲和排队功能，那么发送方只有当前一个帧被物理层取走后才能传输新的帧，否则新的帧就会把前一个帧覆盖掉,处理方法：要求接收方向发送方提供反馈。当把一个分组传给本地的网络层后，向发送方发送一个短帧，也就是说，允许发送方发送下一个帧。在发送下一帧之后，协议要求发送方等待一段时间，直到该段帧（确认）到达。这就是停-等协议。,4.2 停止等待协议,(3) 实用的(有噪声信道)的停止等待协议,两个假定都去掉。帧可能损坏，也可能完全丢失,初步想法加一个计时器。超时重传。重传时间选为略大于从发完数据帧到受到确认帧所需的平均时间,问题没有解决，只加个计时器为什么不行？,有重复分组出现的可能性：响应帧丢失。数据链路层的任务是在两个网络层之间提 供无差错的透明的通信。所以数据链路层必须保证不会有任何差错，此方法可能导致重复的分组提交给网络层。,显然，对接收方而言，需要有一些方法能够区分某一帧是新帧还是重发的帧。实现它的方法：让发送过程在每个待发的帧的头部放一个序号，接收过程通过检查每一个到达帧的序号，看是否是新帧还是重复帧。,4.2 停止等待协议,停止等待协议的工作原理：,4.3 连续ARQ协议,工作原理：,连续ARQ协议，即采用连续自动请求重传方案。发送方可以连续发送一系列信息帧，即不用等待前一帧被确认便可发送下一帧。这就需要在发送方设置一个较大的缓冲存储空间，用以存放若干待确认的信息帧。当发送方收到对某信息帧的确认帧后便可从帧缓存中将该信息帧删除，并继续发送数据帧。所以，连续ARQ协议使得信道利用率大大提高。,4.3 连续ARQ协议,滑动窗口的概念,每发送的一帧都有帧序号，帧序号循环使用,在发送端和接收端分别设定所谓的发送窗口和接收窗口.,发送窗口用来对发送端进行流量控制。发送窗口的大小代表在还没有受到对方确认信息的情况下发送端最多可以发送多少个数据帧（发送端缓冲区的个数）,4.3 连续ARQ协议,滑动窗口的概念,发送窗口中的序列号代表已发送了的但尚未得到确认的帧。发送分组时窗口的上限加1，接受一个确认应答，下限加1。,由于在发送窗口内的当前帧最终有可能在传输中丢失或损失，所以发送过程必须把所有的这些帧保存在内存中，以备重传。,因此，如果最大的窗口大小为n时，发送过程需要n个缓冲区，来保存未确认的帧。如果一旦窗口达到最大帧，发送过程的数据链路层必须强制关闭网络层，直到有一个缓冲区空前出来为止。,4.3 连续ARQ协议,滑动窗口的概念,连续ARQ协议可以在连续收到好几个正确的数据帧后，才对最后的数据帧发确认信息。或者可以在自己有数据要发送时采用捎带方式进行确认。,捎带方式：当一个数据帧到达后，接收过程不是立即发送一个独立的控制帧，而是维持等待，直到其网络层向其发送一个分组，确认被附加到即将发送的数据帧上，这种技术称为“捎带技术”,相对应接收窗口是为了控制可以接收哪些帧，接收窗口（receive window）对应于一组允许接收的帧。,任何落在窗口外面的帧都不加说明地丢弃,每受到一个正确的帧，交给网络层，产生确认，窗口的上、下限加1。,4.4 数据链路层协议-HDLC,数据链路层协议标准，可分为两类，面向字符的与面向比特的链路控制协议。典型的面向字符的链路控制协议为IBM公司的BSC规程；面向比特的链路控制协议为HDLC协议。HDLC可适用于链路的两种基本配置，即非平衡配置与平衡配置。非平衡配置有两种数据传送方式：正常响应方式NRM和异步响应方式ARM。平衡配置则只有异步平衡方式ABM。,4.4 数据链路层协议-HDLC,HDLC定义了三种类型的帧，即信息帧、监控帧与无编号帧。,4.4 数据链路层协议-HDLC,二、HDLC帧结构,F：帧首帧尾标志，表示一帧的开始或结束，它也作为发送站和接收站传输信息的同步标志,透明传输采用位填充技术,A：地址字段，其长度可为8位，也可以是16位，即是说其长度为8n位。,当A字段最高位为1时，表示A只有8位,当A字段最高位位0时，表示A有16位,当此字段8位全为1时，表示为广播地址,当此字段8位全为0时，表示为无效地址,在非平衡链路时，地址字段写入次站地址,在平衡链路时，地址字段写入对方地址,4.4 数据链路层协议-HDLC,控制字段共8位：根据前两位的取值可将HDLC帧划分为信息帧、监督帧和无编号帧,信息字段，长度=0,帧校验序列FCS长度为16位,4.5 Internet的链路层协议-PPP协议,用户接入Internet的一般方法有两种。一种是用户通过电话线，拨号接入Internet，另一种是使用专线接入。不管使用哪一种方法，在传送数据时都需要有数据链路层协议。全世界范围内使用最多的协议为非常简单的点对点协议PPP（Point-to-Point Protocol）。早期Internet使用非常简单的面向字符的协议SLIP（Serial Line Internet Protocol），但SLIP缺点很多。,4.5 Internet的链路层协议-PPP协议,PPP的帧格式与HDLC帧格式很相似,标志字段为7E（01111110），地址字段为FF（11111111），控制字段为03（00000110）。这三各字段是固定不变的，所有PPP帧都应以07EFF03开始。协议字段占两个字节，当协议字段为0021时，PPP帧的信息就是IP数据报。若为C021，则信息字段是PPP链路控制数据。而8021表示这是网络控制数据。帧校验序列FCS与HDLC的相同。由于PPP不是面向比特的，因此帧的长度应为整数个字节。,4.5 Internet的链路层协议-PPP协议,PPP的工作过程可通过PPP状态图来描述,