计算机网络第4章

1、峨眉校区计算机网络第4章 数据链路层计算机网络4.1数据链路层的基本概念14.2停止等待协议234 本章主要内容4.3连续ARQ协议4.4选择重传ARQ协议564.5HDLC4.6 PPP计算机网络 数据链路层简称为链路层 本章主要研究直接相连的两台计算机间的数据链路层进可靠、有效通信的协议。 计算机网络 4.1 4.1 数据链路层的基本概念 4.1.1 4.1.1 链路 4.1.2 4.1.2 数据链路层提供的基本服务和功能 4.1.3 4.1.3 数据链路连接与物理连接的区别 1计算机网络u 4.1 数据链路层的基本概念 远程网的路由器之间通常由点到点租用线路连接，下图显示了在两个路由器之

2、间的数据流。至路由器的传输线数据链路层进程路由选择进程帧分组322路由器322路由器数据链路层协议计算机网络 链路就是一条无源的点到点的物理线路段，中间没有任何交换节点（指数据链路层和以上层的交换），也称为物理链路。 4.1.1链路计算机网络链路控制链路控制节点交换机节点交换机modemmodem数据传输链路数据链路计算机网络结点0 1 0 110 1 01 1 1 010 0 01 0 0 111 0 0结点数据链路数据链路数据链路链 路计算机网络IP 数据报1010 0110帧取出数据链路层网络层链路结点 A结点 B物理层数据链路层结点 A结点 B帧(a)(b)发送帧接收链路IP 数据报1

3、010 0110帧装入数据链路层传送的是帧计算机网络 异步传输和同步传输既与物理层有关（利用来决定每个比特的起始和结束），又与数据链路层有关（收方应当能从收到的比特流中准确地区分出一帧的开始和结束在什么地方，称为帧同步，又称成帧）。1. 异步传输和同步传输计算机网络1 0 1 0 0 1 1 01 0 0 1 0 1 0 1数据链路层物理层时钟帧同步比特流帧计算机网络 异步传输的原理是，在一定的比特数目内，时钟漂移的程度是有限的。接收方可以在偏移积累到采样发生错误之前正确地接收若干个比特。2. 异步传输计算机网络1234567*“1”标记状态低电压数据位开启位数据流注：停止位：可以是1位/1.

4、5位/2位；*：可以是第8位或奇偶位图 4-3 异步传输的启停位组帧格式计算机网络 同步传输以一种同步传输以一种连续的流方式传送比特块连续的流方式传送比特块( (数数据链路帧据链路帧) )，而不使用起始位和停止位把每个字节编而不使用起始位和停止位把每个字节编码成码成1 1个帧个帧。该数据块在长度上可以是多个比特。该数据块在长度上可以是多个比特。3. 同步传输计算机网络p数据虚通路与实际传输路径 数据链路层为网络层提供的基本服务是，将源机器网络层的数据传给目的机器的网络层， 如图4-5（a）所示。4.1.2 4.1.2 链路层提供的服务和功能链路层提供的服务和功能计算机网络4321主机1主机2虚

5、拟数据通路1234a4321主机1主机2实际数据通路1234b图4-5 （a）虚拟通信过程 （b）实际通信过程计算机网络 数据链路层一般提供以下3种基本服务：p基本服务1） 无确认的无连接服务2） 有确认的无连接服务 3） 有确认的面向连接服务 计算机网络l）链路管理 数据链路的建立、维持和释放称为链路管理。2）帧同步 帧同步是指收方应当能从到达的比特流中准确地区分出一帧的开始和结束，帧同步又称为成帧。p数据链路层的功能 计算机网络考察以下4种方法： 字符计数法 带字符填充的首尾界符法 带位填充的首尾标志法 物理层编码违例法计算机网络5 1 2 3 4 5 6 7 8 9 8 0 1 2 3

6、4 5 6 8 7 8 9 0 1 2 3第一帧5个字符第二帧5个字符第四帧8个字符字符计数5 1 2 3 4 5 6 7 8 9 8 0 1 2 3 4 5 6 8 7 8 9 0 1 2 3出错第一帧第二帧错误的现在的一个字符计数一个字符流 （a）无差错 （b）有差错（1）字符计数法（a）（b）计算机网络 （2）带字符填充的首尾界符法（a）字符填充前的数据流 （b）经数据链路层填充后的数据流 （c）去掉填充字符后的数据流A(a)(b)(c)STXDLEDLEBDLEETXASTXDLEDLEDLEBDLEETXi填充的DLEASTXDLEDLEBDLEETX计算机网络 在最大帧长范围内，该

7、技术允许数据帧包含任意个数的比特，其排列模式也不受限制。每一帧使用一个特殊的位模式例如01111110 ，作为开始和结束标志（flag）字节。（3）带位填充的首尾标志法计算机网络 当发送方的数据链路层在数据中遇到5个连续的1时，就自动在其后插入一个0。接收方看到5个连续的1后面跟着一个0时，自动将此0删去。称为位填充（bit stuffing）技术。如下图：(a) 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0(b) 0 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 0 0 1 0 (a) 0 1 1 0

8、 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 填充的位（a） 原始数据 （b） 传送中的数据 （c） 去掉填充位后接收方存储器中的数据计算机网络 在物理线路编码（将数据用电信号的波形表示出来）方案中采用冗余技术的网络，可以采用这种成帧方法。 很多数据链路协议为提高可靠性，采用字符计数与其它方法相结合的策略。当一个帧到达时，其计数字段被用来确定帧尾。只有当帧界定符出现在帧尾，且校验和正确时，该帧才会被接受为有效帧。否则，将继续扫描输入流直到下一个界定符。（4）物理层编码违例法计算机网络n 计算机通信要求有极低的比特差错率，为此，广泛采用编码技术。n 一类是前向

9、纠错（采用纠错码）， 另一类是检错重发方法（采用检错码）。n 计算机通信中常用检错重发方法。3）差错控制计算机网络n 设M为待传送的数据1010001101，共n bit。 设长度为 k + 1 bit 的数 G = 110101，k = 5。n 用2k 乘 M ，这相当于在 M 后面添加 k 个 0 ，即2k M为 101000110100000（这是n + k bit的数） 。循环冗余码CRC的计算（模 2 运算）计算机网络 101000110100000除以G（模 2 运算）的结果 1101010110 Q 商 除数 G 110101 101000110100000 2kM 被除数 11

10、0101 111011 110101 111010 110101 111110 110101 101100 110101 110010 110101 01110 R 余数计算机网络商 Q = 1101010110， 余数 R = 01110。 将余数 R 作为冗余码添加在数据 M 的后面发送，即发送的循环冗余码是101000110101110，即2k M + R。计算机网络n 由于2k M = Q G + R ;则2k M + R = Q Gn 可见，当循环冗余码无差错地传送到接收方时，该码字应当能被G 整除。n 如果不能被G 整除，就说明出现了差错。检错原理计算机网络 CRCITUT CRC

11、16 CRC12 以下三个生成多项式已成为国际标准：1)(51216xxxxG1)(21516xxxxG1)(231112xxxxxxG计算机网络 待编码的n位信息码组1100 （即待传送的数据）用多项式 M(x)表示：M(x) = x3 + x2， 生成多项式 G(x) = x3 + x+ 1（k =3）。 将M(x) x3 = x6 + x5 除以G(x)， 采用多项式的概念后，循环冗余码CRC的计算可用多项式运算的方法进行：计算机网络 得到余式 R(x) = x，其码多项式为m(x) = M(x) x3 + R(x) = x6 + x5 + x 与上述码多项式对应的循环冗余码（即发送的码

12、字） ：m = 1100010计算机网络 x3+x2+xQ(x) 商x3+x+1x6+x5M (x) xk被除数除数G(x)x6 +x4+x3 x5+x4+x3 x5 +x3+x2 x4 +x2 x4 +x2+x xR(x) 余数多项式运算： G(x) = x3 + x+ 1（k =3）计算机网络 控制链路上的数据流量，保证发送与接收速度匹配，防止出现发送速度超过接收能力的现象，以免丢失数据。大多数流量控制方法都需要启用反馈机制，使发方直接或是间接地获得收方指示的发送时机。在未得到允许前，禁止发出帧。4）流量控制计算机网络 数据和控制信息在同一信道中传送，许多情况下共处同一帧中。因此一定要有相

13、应的措施使收方能够将它们区分开来。5）将数据和控制信息区分开 计算机网络 在多点连接和局域网的情况下，必须保证每一帧都能送到正确的目的站。收方也应当知道发方是哪一个站。6）寻址计算机网络 当位于链路两端结点的包交换机（路由器或结点交换机）处于关闭状态时，就称连接这两个结点的物理媒体即通信线路）处于静止状态（见下图）。4.1.3数据链路连接与物理连接的区别 计算机网络物理媒体状态物理媒体状态活动状态活动状态空闲状态空闲状态静止状态静止状态开机开机关机关机物理连接生存期物理连接生存期TPH数据链路生存期数据链路生存期TDL1TDL2TDL3t1t2t3t4t5t6计算机网络4.2 4.2 停止等待

14、协议 4.2.1 4.2.1 数据链路协议基础 4.2.2 4.2.2 停止等待协议的算法2计算机网络 发送方每发送一个数据帧，就停下来等待确认信息，在确定的时间段内收到肯定应答，就发下一帧，否则重发，即为停止等待（stop-and-wait）协议。 u4.2 停止等待协议计算机网络4.2.1 数据链路协议基础主机1数据链路层主机2数据链路层链路链路图4-10 两台主机经链路通信的简化模型 为集中考虑数据链路层本身，在图4-10的简化模型中，将数据链路层以上各层用一个主机代替，而把物理层简单地看成一条链路。计算机网络n 为解决计算机内部数据的并行传输（例如以字节为单位）与物理链路串行比特流传送

15、的矛盾。在收发双方的数据链路层分别设置发送缓冲区和接收缓冲区。n 若采用全双工通信，则每一方均设置发送缓冲区和接收缓冲区。此外，缓冲区在差错重发、窗口流控等方面还可发挥作用。全双工计算机网络4.2.2 停止等待协议的算法图4-11是停止等待协议的模型： HOST L层的用户 HOSTL层的用户N（S）N（S）L层实体L层实体V（S）V（R）计算机网络计算机网络 n 仅当接收方正确收到数据帧（一切正常无误），将该帧数据部分递交给主机，而且发回的ACK被发送方正确接收后，发送方才能更新V（S）为1-V（S）（mod 2），这就意味着，发送缓冲区中保留的副本已可以清除了，可以为主机发送新的一帧。n

16、可见，收到ACK，就表明收发双方一切正常（协议可以向前推进了）。接收方：计算机网络 发送方收到NAK（Negative ACK），就必须重传发送缓冲区中保留的副本，并等待回应。若定时器超时，则重发该帧。发送方：计算机网络4.3 连续ARQ协议 4.3.1 连续ARQ协议的工作原理 4.3.2 滑动窗口控制3计算机网络 停止等待协议使发送方能自动完成对出错帧的重传，称这种差错控制机制为ARQ（Automatic Repeat reQuest），可译为自动请求重传或自动重发请求。 停止等待协议在等待期间，收发双方之间的信道（或链路）处于空闲状态。为提高信道利用率，可让发送方发完一帧后，不必等待AC

17、K的到来，直接传送下一帧。为此，帧的顺序号要用多个比特，才能使发送方连续发出的若干帧都能分配到不同的顺序号。 称这种协议为连续ARQ协议。u4.3 连续ARQ协议计算机网络4.3.1 连续ARQ协议的工作原理01234567345678012 3456734567Tout超时间隔重发3号帧tACK0ACK1ACK2ACK3ACK4ACK5ACK6正确的帧送主机并发回ACK3号帧出错，丢弃丢弃这些帧不发任何回应正确的帧送主机并发回ACK计算机网络1.在发送方 4.3.2 滑动窗口控制(a)0123456707发送窗口WT发送窗口后沿发送窗口前沿允许发0到2号帧012345670WR发送窗口后沿发

18、送窗口前沿准备收0帧(b)0123456707WT允许发1到3号帧012345670WR准备收1帧(c)0123456707WT允许发3到5号帧012345670WR准备收3帧窗口前移1帧收到0帧的确认已收到的确认帧已收到的0至2号帧发送窗口WT的变化计算机网络2. 在接收方n 图（a）指明接收窗口为0号帧，即可接收0号帧。收到0号帧后，接收窗口前移一帧。n 如图（b）所示，即准备接收1号帧，并发送对0号帧的确认。n 图（c）显示，已收到2号帧后，接收窗口的位置。计算机网络(a)0123456707发送窗口WT发送窗口后沿发送窗口前沿允许发0到2号帧012345670WR发送窗口后沿发送窗口前

19、沿准备收0帧(b)0123456707WT允许发1到3号帧012345670WR准备收1帧(c)0123456707WT允许发3到5号帧012345670WR准备收3帧窗口前移1帧收到0帧的确认已收到的确认帧已收到的0至2号帧发送窗口WT的变化接收窗口WR的变化计算机网络图4-15用另一种图示方法对停等协议中发送方和接收方的滑动窗口状态变化过程进行了描述，其中 WT = WR = 1(a)初始时（b）第一个帧发出后（c）第一个帧收到后（d）第一个确认收到后计算机网络4.4选择重传ARQ协议 012345673458910012 3456734589Tout重发3号帧tACK0ACK1ACK2A

20、CK7ACK8正确的帧送主机并发回ACK3号帧出错，丢弃数据链路层缓存的帧正确的帧送主机并发回ACK丢弃的重发帧收下3号帧，将3至7号帧一并送主机计算机网络4.5 HDLC 4.5.1 HDLC的产生 4.5.2 HDLC的基本工作方式 4.5.3 HDLC的主要内容5计算机网络 IBM公司于公司于1974年推出的系统网络体系结构年推出的系统网络体系结构SNA，其数据链路层就采用了面向比特的规程其数据链路层就采用了面向比特的规程SDLC,ANSI修修改改SDLC后作为美国国家标准，并命名为后作为美国国家标准，并命名为ADCCP,ISO则则把把SDLC修改为修改为HDLC，作为国际标准，作为国际

21、标准ISO.4.5.1 HDLC的产生计算机网络 HDLC定义了三种类型的链路层实体（即站点）：主站，次站，复合站。4.5.2 HDLC的基本工作方式的基本工作方式次站BP主站A命令（B）P响应（B)（a）非平衡型配置点对点结构响应（B)响应（C)P主站A命令（B或C）（b）非平衡型配置多点结构SBSC次站CP复合站A命令（B）P响应（B)（c）平衡配置复合站B命令（A）响应（A）计算机网络 HDLC根据站点类型和线路连接方式的不同，定义了两种链路配置：非平衡型链路由主站p（primary station）和次站s（secondary station）构成。计算机网络n 正常响应方式（Norm

22、al Response Mode，NRM）n 异步响应方式（Asynchronous Response Mode，ARM）n 异步平衡方式（Asynchronous Balanced Mode，ABM）HDLC定义了三种数据传送方式：计算机网络p 4.5.3.1 HDLC的帧结构 HDLC HDLC的帧结构如图的帧结构如图4-184-18所所示示4.5.3 HDLC的主要内容 透明传输区间透明传输区间校验区间校验区间标志字段标志字段F帧校验序列帧校验序列FCS信息字段信息字段Info控制字段控制字段C地址字段地址字段A标志字段标志字段F816可变可变888 位位图4-18 HDLC的帧结构 计

23、算机网络p2 HDLC的命令和响应见表4-1p3 HDLC的规程类型 HDLC的三种数据传送方式NRM、ARM和ABM分别对应的三种规程类型（非平衡正常类型（UNC）、非平衡异步类型（UAC）和平衡异步类型（BAC）定义了各自的基本命令和响应集，作为它们必须实现的功能。计算机网络1）UNC（非平衡正常类型）的数据传输计算机网络2）BAC（平衡异步类型）的数据传输复合站A复合站B变量初始化立链路, 状态A 站与B 站建V ( R ) - - 0V ( S ) - - 0V ( S ) - - 0V ( R ) - - 0变量初始化B 站将状态B , I 0 0 , PB , I 1 0A , I

24、 1 0 , PA , I 0 0B , I 3 1B , I 2 0A , I 2 2B , R R 2 , FB , I 4 2A , R R 2 , FB , I 5 2A , I 3 4B , R R 2 , PB , I 7 2B , I 6 2A , I 4 5A , I 2 6 , PA , R R 3 , FA , I 3 0B , R R O , FA , I 4 0A , I 5 0 , PA , R R 6 , FB 站发起释放链路A 站释放链路A , D I S C , PA , U A , FB , S A B M , PB , U A , F丢失2 号帧超时时间链路

25、建立阶段阶段传输数据阶段释放链路计算机网络4.6 PPP 4.6.1 Internet中的数据链路层协议 4.6.2 PPP简介6计算机网络4.6.1 Internet中常用的数据链路层协议 TCP/IP协议族的标准虽然没有规定应该使用何种数据链路层协议，但PPP（Point-to-Point Protocol，点对点协议）和SLIP（Serial Line Internet Protocol，串行线路网际协议）却在Internet中得到了广泛的应用。 SLIP是在早期使用的一个简单的面向字符的协议，主要用于低速（不超过9.2kb/s）交互性业务，功能较差，已逐渐被PPP协议取代。u4.6 P

26、PP计算机网络 一般情况下，家庭个人用户使用拨号电话线接入Internet，用户较多的单位则采用专线接入。用户拨号入网的方法如图4-23所示。1 用户接入Internet的方法 计算机网络 在多厂商网络产品混用的Internet中，PPP通常是路由器间点对点网络连接（例如通过E1链路）的主要选择。如图示。2 Internet中路由器间的点对点连接CISIO路由器华为路由器信号变换器E1信号变换器PPP图4-24 Internet中路由器间的点对点连接 计算机网络PPP由三部分组成： 帧格式； 链路控制协议LCP 网络控制协议NCP4.6.2 PPP简介计算机网络 PPP 既支持异步链路（无奇偶校验的8比特数据），也支持面向比特的同步链路。PPP 的帧格式和HDLC的相似（见图4-25），但 PPP 不是面向比特的，因而所有的PPP帧的长度都是