计算机网络（第2版）数据链路层

ComputerNetwork计算机网络

数据链路层2数据链路层的定义和主要功能3.1数据链路层概述3.2组帧3.3差错控制技术本章主要内容差错控制技术：数据链路层传输产生差错的原因、差错控制机制和差错控制编码字符计数法、首尾定界法、首尾标志法、违例编码法3.4流量控制与可靠传输机制流量控制：停止等待协议、后退N帧协议、选择重传协议可靠传输：确认机制、超时重传机制第3章

数据链路层3信道划分介质访问控制方式：随机访问和轮询访问3.5介质访问控制方式3.6局域网3.7广域网本章主要内容广域网的基本概念HDLC的工作原理和帧格式PPP的帧

式、工作原理及PPP认证局域网的基本概念和体系结构3.1数据链路层概述4差错校验：数据在物理传输过程中可能受到噪声干扰，使数据传输会产生差错，而物理层只关心原始比特流的传送，不考虑所传输信号的意义和信息的结构，无法识别或判断数据在传输过程中是否发生变化，因此也无法采取补救措施。速度匹配：物理层不能协调发送节点的发送速率和接收节点的接收速率。设计数据链路层的原因数据链路层定义数据链路层模型数据链路层功能数据链路层服务数据链路层处于OSI模型的第二层，介于物理层与网络层之间，属于通信子网范围。数据链路层和物理层通常构成网络通信中必不可少的低层服务，在节点的网络接口（如通常所称的网卡）中实现。3.1数据链路层概述5数据链路层定义利用物理层建立的不可靠的物理链路向网络层提供可靠的数据链路，实现网络中两个相邻节点之间的无差错数据传输。因此，数据链路层是利用物理层提供的原始比特流传输服务，检测并校正物理层的传输差错，在相邻节点之间构建一条无差错的链路，从而向网络层提供可靠的数据传输服务。数据链路（逻辑链路）：是将实现通信协议的硬件、软件加载到物理链路上所构成的可以通信的链路。数据链路层的定义数据链路层定义数据链路层模型数据链路层功能数据链路层服务3.1数据链路层概述6节点1节点2节点3数据链路层协议数据链路层协议数据链路数据链路物理链路物理链路主机A主机B物理链路数据链路层提供的数字信道

物理层提供的无源点到点物理线路数据链路层协议数据链路/逻辑链路

+通信规程数据链路层定义数据链路层模型数据链路层功能数据链路层服务数据链路层的模型3.1数据链路层概述7组帧：将数据划分成帧的方法，即如何界定帧的界限。帧的透明传输：对帧进行特殊处理以便可以自动区分数据与控制信息，而这些特殊处理对高层来说是透明的。流量控制：指控制数据的发送速度，以免接收缓冲区溢出数据丢失。差错控制：接收方对数据帧进行差错校验，并能够进行相应处理。数据链路管理：能够建立、维持和释放数据链路连接。链路访问控制：能够确定节点如何获取对链路的控制权。物理寻址：多点连接情况下，可以识别正确源节点和目的节点。数据链路层定义数据链路层模型数据链路层功能数据链路层服务数据链路层主要功能3.1数据链路层概述8无确认、无连接

服务（

Unacknowledgedconnectionless

）接收方不对收到的帧进行确认适用场景：误码率低的可靠信道，实时通信，如以太网（IEEE802.3）有确认、无连接

服务（

Acknowledgedconnectionless）每一帧都得到单独的确认适用场景：不可靠的信道（无线信道），如

无线局域网（IEEE802.11）有确认、有连接服务（

Acknowledgedconnection-oriented

）在建立的连接上传输数据帧，每一帧都得到确认适用场景：长延迟的不可靠信道数据链路层定义数据链路层模型数据链路层功能数据链路层服务数据链路层提供的服务3.2组帧9组帧机制基本概念常用的组帧方法组帧目的：为了使物理层能透明、成块传输数据，将比特流划分为离散的帧。组帧的需解决的关键问题：如何标识一个帧的开始？帧定界：接收方必须能从物理层接收的比特流中明确区分出每一帧的开始和结束，这个问题被称为帧定界或帧同步。关键：如何选择定界符？如果定界符出现在数据部分该如何处理？组帧机制基本概念3.2组帧10字符计数法带填充字符的首尾界符法带填充位的首尾标志法物理层违规编码法常用的组帧方法组帧机制基本概念常用的组帧方法3.2组帧11无差错传输的情形第1帧5字节第2帧5字节第3帧8字节第4帧6字节512345123481234567612345问题：如果某个计数字节出错会发生什么情况？第1帧5字节第2帧出现差错第3帧8字节第4帧6字节512348123481234567612345破坏了帧的边界，导致一连串帧的错误出现一个字节差错的情形字符计数法组帧机制基本概念常用的组帧方法3.2组帧12每一帧以ASCII字符序列“DLESTX”开头，以“DLEETX”结束。格式如下：DELSTX开始字符数据（DLEDLE）结束字符DLEETX问题：如果传送的数据中包含与“DLESTX”或“DLEETX”相同的字符会有什么问题？如何解决？解决：填充DEL字符组帧机制基本概念常用的组帧方法首尾界符法：填充字符3.2组帧13STXADLEBCDLEDLEETXDLESTXADLEDLEBDLEDLEDLECETXDLESTXADLEBCDLEDLEETXDLE网络层发出的数据发送方填充后的数据接收方去掉填充后上传给网络层的数据问题：带填充字符的首尾界符法有什么不足？组帧机制基本概念常用的组帧方法首尾界符法：填充字符3.2组帧14采用特定位模式，即01111110，作为帧开始和结束标志字节。发送方：原始数据1011111100011111111111011101010111111001111110帧首标志帧尾标志数据1011111010001111101111101011101010111111001111110帧首标志帧尾标志数据1011111100011111111111011101010111111001111110帧首标志帧尾标志数据填充位传输中：带填充比特的传输数据接收方：删除填充比特后恢复的数据组帧机制基本概念常用的组帧方法首尾标志法：填充比特0发送方：检查有效载荷若在有效载荷中出现连续5个比特1，则直接插入1个比特0接收方：若出现连续5个比特1，则判断下一个比特值若下一比特为0，则为有效载荷，直接丢弃比特0若下一比特为1，则连同后一比特的0，构成定界符，一帧结束3.2组帧4B/5B编码方案4

比特数据

映射为

5

比特编码，剩余的一半码字（16个码字）未使用，可以用做帧定界符例如：00100

组合不包含在

4B/5B

编码中，可做帧定界符前导码存在很长的前导码（preamble），可以作为定界符例如：传统以太网、802.11曼切斯特编码/差分曼切斯特编码正常的信号在周期

中间有跳变，持续的高电平（或低电平）为违例码，可以用作定界符例如：802.5令牌环网15组帧机制基本概念常用的组帧方法违例编码法核心思想：选择的帧定界符不会在数据部分出现3.3差错控制技术差错产生的原因差错类型差错产生的原因：信道中存在的噪声可能导致数据传输产生差错。16信道噪声差错解决方案检错码纠错码信道噪声一般可分为热噪声和冲击噪声两类热噪声：由传输介质导体的电子热运动产生，属于随机噪声。由热噪声引起的差错称为随机差错。冲击噪声：由意外干扰产生，如外界磁场变换、电源开关跳变等。冲击噪声引起的传输差错称为突发差错。冲击噪声可引起相邻多个数据位出错。计算机网络中的差错主要指突发差错。3.3差错控制技术信道的噪声导致的差错类型主要如下：错误（incorrect）：数据发生错误丢失（lost）：接收方未收到乱序（outoforder）：先发后到，后发先到重复（repeatedlydelivery）：一次发送，多次接收17差错类型数据链路层如何解决上述问题？差错产生的原因差错类型差错解决方案检错码纠错码3.3差错控制技术后向纠错：采用检错码检错，然后重传数据帧予以纠正。检错码：能够使接收方检测收到的数据帧是否存在差错的编码。常用的检错码有奇偶校验码和循环冗余码（CRC码）。重传：接收方进行差错校验，若出错，则通知发送方重传，纠正差错。前向纠错：差错校验的同时可进行纠正。纠错码：数据帧在传输过程中发生错误后，接收方能够自行发现并纠正的编码。常用的前向纠错码有海明码。18差错解决方案一般采用冗余编码进行差错检测与纠正（重传、自动纠错）。差错产生的原因差错类型差错解决方案检错码纠错码3.3差错控制技术检错编码一般采用冗余编码技术，即在有效数据（信息位）发送前，先按照某种关系附加一定的冗余位，构成一个符合某一规则的码字后再发送。当要发送的有效数据位发生变化时，相应的冗余位也将随之改变，始终保证码字遵循既定的规则。接收方则根据收到的码字是否仍符合原规则来判断传输是否出错。常用的检错编码有奇偶校验码和循环冗余码。19差错产生的原因差错类型差错解决方案检错码纠错码检错编码3.3差错控制技术奇偶校验码：通过增加冗余位使得码字中“1”的个数恒为奇数或偶数。1位奇偶校验：增加1位校验位，可以检查奇数位错误。偶校验：保证“1”的个数为偶数个

例如：奇校验：保证“1”的个数为奇数个

例如：10110100数据位校验位10110101数据位校验位思考：采用二维奇偶校验码，是否可以进行纠错？20差错产生的原因差错类型差错解决方案检错码纠错码奇偶校验码3.3差错控制技术循环冗余校验方法是数据通信中差错检测的重要方法，它对随机错码和突发错码均能以较低的冗余度进行严格检查。循环冗余校验码（CRC码）：又称为多项式码，按照线性计算规则产生一个CRC码进行差错检测。CRC码的检错过程发送方：计算产生一个CRC码，附加在信息位后面一起发送。接收方：将收到的信息（信息位+CRC码）按发送方形成CRC码的相同算法进行校验计算，以检测数据传输是否存在差错。21差错产生的原因差错类型差错解决方案检错码纠错码循环冗余码3.3差错控制技术确定信息多项式：M(x)，由发送信息构造确定确定一个生成（素）多项式：G(x)，通常是选择或构造确定计算余数多项式R(x)：计算

R(x)=xrM(x)%G(x)（模2除）

注意：R(x)称为CRC码形成码元多项式C(x)：计算

C(x)=xrM(x)+R(x)22差错产生的原因差错类型差错解决方案检错码纠错码循环冗余码的计算过程3.3差错控制技术23确定信息多项式M(x)：将二进制位串作为一个多项式的系数，该多项式称为信息多项式M(x)。任何一个由二进制数位串组成的代码都可以和一个只含有0和1两个系数的多项式建立一一对应关系。一个k位的数据帧可以看成是从xk-1到x0的k-1次多项式的系数序列，该多项式的阶数为k-1，最高位（最左边）是xk-1项的系数，下一位是xk-2的系数，依次类推。

例如：若信息位为1011011（7位），则信息多项式M(x)为M(x)=1×x6+0×x5+1×x4+1×x3+0×x2+1×x1+1×x0=x6+x4+x3+x+1

同理，若M(x)=x5+x4+x2+1，则对应的二进制位串为

110101

差错产生的原因差错类型差错解决方案检错码纠错码CRC码计算3.3差错控制技术24确定一个素（生成）多项式：G(x)生成多项式的作用是与信息多项式进行计算产生余数多项式。生成多项式的最高位和最低位系数必须是1。目前，国际标准中生成多项式有以下几类。CRC-12：x12+x11+x3+x2+x+1CRC-16：x16+x15+x2+1CRC-CCITT-1：x16+x12+x5+1CRC-32：x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1计算余数多项式R(x)：计算

R(x)=xrM(x)%G(x)（模2除），保留余数，商舍掉。形成码元多项式C(x)：计算

C(x)=xrM(x)+R(x)，R(x)附加在M(x)后面。差错产生的原因差错类型差错解决方案检错码纠错码CRC码计算3.3差错控制技术25差错产生的原因差错类型差错解决方案检错码纠错码CRC码简化计算方法设信息位为m位，生成多项式G(x)为r阶，则计算CRC校验码步骤简化如下：1）在信息码尾部添加r个0，成为m+r位二进制位串，相应多项式为xr·M(x)；2）按模2除法用G(x)对应的位串去除xr·M(x)对应的位串，得到余数R(x)所对应的位串；3）按模2加法从xrM(x)对应的位串中加上得到的余数R(x)所对应的位串，其结果就是要传送的带CRC校验码的完整数据。3.3差错控制技术26【例3-1】设信息位M=101001101，生成多项式

G(x)=x4+x3+x+1，试计算信息M的CRC校验码。【解】由已知G(x)最高次幂为4，得

r=4，即CRC码为4位

生成多项式G(x)对应的位串为

11011

xrM(x)对应的位串为

101001101

0000

计算余数R：xrM(x)%G(x)，模2除法，计算过程如图所示

得：余数R为

0010（补足4位）

因此，信息M=101001101的CRC校验码为：0010

带CRC校验码的码元为：10100110100101010011010000110111101111111101110011011011100111101110000110111011110111101011011100余数差错产生的原因差错类型差错解决方案检错码纠错码循环冗余码计算举例3.3差错控制技术27接收方收到码元C'(x)，计算C'(x)%G(x)（模2除法），得到余数R'(x)。如果R'(x)=0，则传输无错误，否则，传输中产生了差错。差错产生的原因差错类型差错解决方案检错码纠错码循环冗余码校验【例3-2】若接收方收到信息为10110011010，其生成多项式G(x)=x4+x3+1，问接收方收到的数据是否正确？【解】由题意知

G(x)

最高次幂为4，则r=4

，即CRC码为4位

且

G(x)

对应位串为

11001

又知：收到信息C(x)为

10110011010

计算余数R：R(x)=C(x)%G(x)

，

计算过程如图所示

计算结果：余数R=0，则接收数据正确。10110011010110011100111001110011111011111110011100100余数R=03.3差错控制技术28如果使用r位校验码，则生成多项式G(x)的最高次幂应为

r；生成多项式G(x)必须包含常数项“1”，否则校验码的最低有效位LSB将始终为0。差错产生的原因差错类型差错解决方案检错码纠错码生成多项式的要求能检出全部1位错能检出全部离散的2位错能检出奇数个错能检出全部长度小于等于(n-k)的突发错能以相当大的概率检出长度大于r（校验位长度）的连续的突发错循环冗余码的检错能力3.3差错控制技术29海明码是一种可以纠正一位差错的编码。几个相关概念如下：正确码

1101错误码

0101100111111100

差错产生的原因差错类型差错解决方案检错码纠错码海明码n位码字：对于m位数据位（信息位），若增加r位冗余位（校验位），则组成总长度为n位（n=m+r）的编码，称为n位码字（n=m+r），其有效码字为2n个。可识别码字：对于一个特定的n位码字，当且仅当其中任意1位改变时，都可以形成n个无效但可以纠错的码字（即知道出错位置），即有n+1个可识别的码字（1个有效码字，n个无效但可识别的码字）。

例如：4位编码，其中1位错误，将产生4个错误码。有效码字：m位数据产生2m个有效码字，共有2m(n+1)个可识别的码字、2n个可识别与不可识别（出错的）码字。为了能纠正单比特错，m和r之间应该满足以下关系式：

2m(n+1)≤2n

将n=m+r代入，得

m+r+1≤2r3.3差错控制技术30目标：以奇偶校验为基础，如何找到出错位置，提供1位纠错能力理解海明码编码过程，以(15,11)海明码为例例如：11比特的数据

0101100110111比特数据按顺序放入数据位校验位：2

的幂次方位（记为p1,p2,p4,p8）每个校验位对数据位的子集做校验，缩小定位错误的范围问题：每个校验位如何计算？校验位数据位右下角数字为码字中位序号10101100101123456789101112131415差错产生的原因差错类型差错解决方案检错码纠错码海明码的编码方法3.3差错控制技术31选择子集与校验位计算海明码缺省为偶校验（也可以使用奇校验）101011001011234567891011121314155个1p1=111010110010112345678910111213141510101100101123456789101112131415101011001011234567891011121314152个1p2=0010第1组第2组第3组第4组每组的数据位每组的校验位5个1p4=14个1p8=0101011001011234567891011121314150110差错产生的原因差错类型差错解决方案检错码纠错码海明码的编码方法3.3差错控制技术32发送与接收码字如果发送过程中第7位出现差错，如何定位错误？101100101100101123456789101112131415校验位数据位校验位数据位100110001001101101100100100101123456789101112131415发送方接收方差错产生的原因差错类型差错解决方案检错码纠错码海明码的传输3.3差错控制技术33错误定位与纠正第1组和第2组校验结果可定位错误所在的列例如：第1组和第2组校验结果都指明存在错误，可定位错误位于第4列其他出错情况判断校验列234组1╳╳组2╳╳101001001011234567891011121314155个1有错误1101001001011234567891011121314151个1有错误0第1组第2组差错产生的原因差错类型差错解决方案检错码纠错码海明码的检错方法3.3差错控制技术34错误定位与纠正（续）第3组和第4组校验结果可定位错误所在的行校验行234组3╳╳组4╳╳101001001011234567891011121314151010010010112345678910111213141510第3组第4组结论：错误位于第2行、第4列（位置7）5个1有错误4个1无错误例如：第3组校验结果指明存在错误，第4组校验结果指明无错误，可定位错误位于第2行其他出错情况判断差错产生的原因差错类型差错解决方案检错码纠错码海明码的检错方法3.3差错控制技术35错误定位与纠正（续）：总体的定位错误列表出错位123456789101112131415组1:X1╳╳╳╳╳╳╳╳组2:X2╳╳╳╳╳╳╳╳组3:X4╳╳╳╳╳╳╳╳组4:X8╳╳╳╳╳╳╳╳101011001011234567891011121314151101011001011234567891011121314151010110010112345678910111213141510101100101123456789101112131415010第1组第2组第3组第4组差错产生的原因差错类型差错解决方案检错码纠错码海明码的检错方法3.4流量控制与可靠传输机制36流量控制：是对链路上帧的发送速率进行控制，使得接收方能够有足够的缓冲空间来接收处理每个帧。流量控制的基本方法：是由接收方来控制发送方发送数据的速率。常见的流量控制方式有停止-等待协议和滑动窗口协议。流量控制机制基本概念流量控制概述停止-等待协议后退N帧协议选择重传协议3.4流量控制与可靠传输机制37停止-等待机制基本原理发送方每发送一帧，都要等待接收方的应答信号，之后才能发送下一帧。接收方每接收一帧，都要反馈应答信号才可接收下一帧，否则发送方一直等待。滑动窗口机制基本原理任意时刻，发送方都维持一组连续的允许发送帧的序号，称为发送窗口WT。发送方只发送帧序号落在发送窗口内的数据帧。任意时刻，接收方也维持一组连续的允许接收帧的序号，称为接收窗口WR。接收方收到的数据帧序号落入接收窗口内时，才允许将该数据帧收下，否则丢弃该数据帧。流量控制机制基本原理流量控制概述停止-等待协议后退N帧协议选择重传协议3.4流量控制与可靠传输机制3801234567012发送窗口WT允许发送5个帧不允许发送的帧已发送01234567012发送窗口WT还允许发送4个帧不允许发送的帧01234567012发送窗口WT已发送不允许发送的帧01234567012发送窗口WT已发送不允许发送的帧已发送并收到确认还允许发送3个帧a）允许发送0-4号共5个帧b）还允许发送1-4号共4个帧c）不允许发送任何帧d）还允许发送5-7号共3个帧发送窗口工作原理流量控制概述停止-等待协议后退N帧协议选择重传协议3.4流量控制与可靠传输机制39设接收窗口WR=1a）准备接收0号帧c）准备接收3号帧01234567012WR不允许接收的帧准备接收0号帧b）准备接收1号帧01234567012WR不允许接收的帧准备接收1号帧已收到01234567012不允许接收的帧WR准备接收3号帧已收到接收窗口工作原理流量控制概述停止-等待协议后退N帧协议选择重传协议3.4流量控制与可靠传输机制40只有接收窗口向前滑动（同时接收方发送了确认帧）时，发送窗口才有可能（只有发送方收到确认帧后才一定）向前滑动。从滑动窗口的概念来讲，停止-等待协议、后退N帧协议和选择重传协议只在发送窗口大小与接收窗口大小上有所区别：停止-等待协议：发送窗口大小=1，接收窗口大小=1。后退N帧协议：发送窗口大小>1，接收窗口大小=1。选择重传协议：发送窗口大小>1，接收窗口大小>1。接收窗口的大小为1时，可保证帧的有序接收。滑动窗口的特性流量控制概述停止-等待协议后退N帧协议选择重传协议注意数据链路层的滑动窗口协议中，窗口的大小在传输过程中是固定的（与传输层的滑动窗口协议是不同的）。3.4流量控制与可靠传输机制41数据链路层可靠传输通常使用确认和超时重传两种机制完成。可靠传输机制基本原理流量控制概述停止-等待协议后退N帧协议选择重传协议确认：它一种无数据的控制帧，是接收方通知发送方哪些内容已被正确接收。有些情况下为了提高传输效率，可将确认捎带在一个回复帧中，称为捎带确认。超时重传：发送方在发送某个数据帧后就开启一个计时器，在一定时间内如果没有得到发送数据帧的确认帧，则重新发送该数据帧，直到发送成功为止。自动重传请求（AutoRepeatreQuest，ARQ）通过接收方请求发送方重传出错的数据帧来恢复出错的帧，它是处理信道所带来差错的主要方法。3.4流量控制与可靠传输机制42停止-等待协议：指源站发送单个帧后必须等待确认，在目的站的应答到达源站之前，源站不能发送其他数据帧。单帧滑动窗口协议：从滑动窗口机制角度看，停止-等待协议相当于发送窗口和接收窗口大小均为1的滑动窗口协议，即单帧滑动窗口协议。单帧滑动窗口与停止-等待协议流量控制概述停止-等待协议后退N帧协议选择重传协议3.4流量控制与可靠传输机制43在停止-等待协议中，除数据帧丢失外，还可能出现以下两种差错。数据帧出错：到达目的站的帧被破坏，则接收站利用差错控制技术检出错误后将该帧丢弃。

解决方法：源站设置计数器，在一个帧发送之后，源站等待确认，如果在计数器计满时仍未收到确认，则再次发送相同的帧。重复上述过程直到该数据帧正确到达目的站为止。确认帧出错：数据帧正确而确认帧被破坏，此时目的站已收到正确的数据帧，但源站未收到确认帧，若源站重传已被接收的数据帧，则出现重复帧问题。

解决方法：目的站收到重复的数据帧时会丢弃该帧，并重传一个该帧的对应确认帧。发送的帧交替地用0和1来标识，肯定确认分别用ACK0和ACK1来表示，收到的确认有误时，重传已发送的帧。停止-等待协议可能的差错流量控制概述停止-等待协议后退N帧协议选择重传协议3.4流量控制与可靠传输机制44N(重复帧)V(R)=0将收到帧中的数据部分上交主机V(R)=1-V(R)Y发送ACK发送NAKNY接收数据帧并进行差错校验NY丢弃此帧N(S)=V(R)？正确？帧收到？V(S)=0从主机取出一个数据帧并送入发送缓冲区保存从发送缓冲区中取出数据帧并发送N(S)=V(S)设置超时定时器toutV(S)=1-V(S)YACKNAKNYNACK/NAK？超时？应答到？流量控制概述停止-等待协议后退N帧协议选择重传协议停止-等待协议算法发送方算法接收方算法3.4流量控制与可靠传输机制45发送方法算法①

设置

V(S)=0//初始化发送状态变量②

取一个待发送的数据帧存入缓冲区③N(S)←V(S)//设置数据帧的发送序号④从发送缓冲区取出数据帧发送//该帧副本仍保留在发送缓冲区中⑤设置超时计时器Tout//选择适当的超时重传时间tout⑥等待

//等待⑦和⑧两个事件中最先出现的一个⑦收到确认帧（ACKn），则判断n值

若n=1-V(S)，则//已发送的数据帧被接收方确认

V(S)←1-V(S)

//更新发送状态变量，序号交替为0和1

转到②

//准备发送下一数据帧否则，丢弃该确认帧，转到⑥

//已发送的数据帧未被接收方确认⑧超时计数器时间到，则转到④//重传数据帧停止-等待协议算法流量控制概述停止-等待协议后退N帧协议选择重传协议V(S)=0从主机取出一个数据帧并送入发送缓冲区保存从发送缓冲区中取出数据帧并发送N(S)=V(S)设置超时定时器toutV(S)=1-V(S)YACKNAKNYNACK/NAK？超时？应答到？3.4流量控制与可靠传输机制46接收方算法①

V(R)=0//接收状态变量初始化，其值等于欲接收数据帧的发送序号②等待③收到一个数据帧，检查有无产生传输差错（如CRC校验）若检查结果正确无误，则继续执行④；否则直接丢弃，转到②④判断N(S)==V(R)？是，则继续执行⑤//接收发送序号正确的数据帧

否则，丢弃此数据帧，然后转到⑦//丢弃的帧是重复帧⑤将收到的数据帧中的数据部分送交高层⑥V(R)←1-V(R)//更新接收状态变量，准备接收下一数据帧⑦发送确认帧ACKn，转到②//n=V(R)流量控制概述停止-等待协议后退N帧协议选择重传协议N(重复帧)V(R)=0将收到帧中的数据部分上交主机V(R)=1-V(R)Y发送ACK发送NAKNY接收数据帧并进行差错校验NY丢弃此帧N(S)=V(R)？正确？帧收到？停止-等待协议算法3.4流量控制与可靠传输机制47发送方：可以连续发送落在发送窗口中未发送的信息帧。接收方：只允许按顺序接收信息帧。后退N帧机制当接收方检测出失序的信息帧后，则要求发送方重发最后一个正确接收的信息帧之后的所有未被确认的帧。当发送方发送了N个帧后，若发现该N个帧的前一个帧在计时器超时后仍未返回其确认信息，则该帧被判为出错或丢失，此时发送方将不得不重传该出错帧及随后的N个帧。多帧滑动窗口与后退N帧协议流量控制概述停止-等待协议后退N帧协议选择重传协议3.4流量控制与可靠传输机制48后退N帧协议的工作原理01234567823456789012345678EDDDDDDACK0ACK1ACK2ACK3ACK4ACK5ACK6超时间隔出错被数据链路层丢弃的帧多帧滑动窗口与后退N帧协议流量控制概述停止-等待协议后退N帧协议选择重传协议发送方接收方3.4流量控制与可靠传输机制490123456782910111213141501291011121314E345678ACK0ACK1ACK8ACK9ACK10ACK11ACK12超时间隔出错由数据链路层缓冲的帧将分组2-8送交网络层多帧滑动窗口与选择重传协议流量控制概述停止-等待协议后退N帧协议选择重传协议选择重传（SR）协议的工作原理发送方接收方SR协议：为进一步提高信道的利用率，可设法只重传出现差错的数据帧或计时器超时的数据帧。要求：必须加大接收窗口，以便先收下发送序号不连续但仍处在接收窗口中的数据帧，待所缺失序号的数据帧收到后再一并送交高层。3.5介质访问控制方式50计算机网络中的地址：物理地址与逻辑地址。介质访问控制定义信道分配地址的概念随机访问轮询访问网络地址分类物理地址：数据链路层和物理层使用的地址，称为MAC地址或硬件地址。用于识别网络（主要是局域网）中各节点设备。逻辑地址：网络层使用的地址，TCP/IP中称为IP地址。用于标识网络中每个设备相互连接时所处的逻辑位置，又称为网络地址或IP地址。IP地址分为IPv4和IPv6两类。IPv4由32位二进制数组成，IPv6由128位二进制数组成。3.5介质访问控制方式51当多个节点在共享信道上进行通信时，需要采用一定策略以解决多个节点如何使用信道问题，即信道使用的分配策略，简称信道分配。信道分配信道分配方法静态分配：指时分、频分、波分和码分多路复用技术在时域、频域或编码空间固定划分信道的方法。动态分配：不固定节点使用信道带宽，即获得使用权的节点能够以信道提供的全部带宽发送数据帧，但需要通过某种方法来协调多个节点对通信媒体的使用。动态介质访问控制分为：随机接入方式和受控接入方式。随机接入方式目前占主流，以太网采用随机接入方式。介质访问控制定义信道分配地址的概念随机访问轮询访问3.5介质访问控制方式介质访问控制方式：指在广播信道中信道分配的方式，即网络中各节点访问共享信道采用何种方式。规定节点对信道访问的要求，属于数据链路层的MAC子层功能。52静态分配信道动态分配信道轮询访问随机访问频分多路复用FDM时分多路复用TDM波分多路复用WDM码分多路复用CDM令牌传递协议ALOHA协议CSMA协议CSMA/CD协议CSMA/CA协议介质访问控制定义介质访问控制分类数据传输冲突不可避免用户在通信中不会互相干扰数据传输不会产生冲突介质访问控制定义信道分配地址的概念随机访问轮询访问3.5介质访问控制方式53随机访问方式又称为共享介质访问方式。随机访问基本概念共享介质访问：共享传输介质（总线）上各节点采用随机接入方式使用传输介质，多个有发送需求的节点自由竞争共享信道的使用权。冲突：在访问共享介质过程中，当两个或多个节点同时发送数据时将会产生冲突，导致所传输的帧出错。共享介质访问控制的核心：发送数据前监测介质是否空闲，尽量避免冲突，发生冲突后采用退避算法解决冲突。

介质访问控制定义信道分配地址的概念随机访问轮询访问3.5介质访问控制方式54ALOHA协议的基本思想：载波监听和冲突检测。发送方在数据发送过程中通过载波监听进行冲突检测，若检测到冲突，发送节点将等待一段随机长的时间后再重传该帧。

ALOHA协议分类纯ALOHA（P-ALOHA）时隙ALOHA（S-ALOHA）ALOHA技术介质访问控制定义信道分配地址的概念随机访问轮询访问3.5介质访问控制方式55纯ALOHA：采用完全随机接入方式，又称为非时隙ALOHA。纯ALOHA技术工作原理：设m个网络节点各自独立地以平均λ个帧/秒的泊松过程产生并发送帧，数据帧长度固定，且发送一个帧的时间为τ秒。纯ALOHA系统的最大信道利用率只有18.4%。介质访问控制定义信道分配地址的概念随机访问轮询访问M11M12M12tN1M21tN2M31M31tN3Mm1M31tNmM11Mm1M12M12M21M31t信道碰撞

随机时间间隔t1随机时间间隔t3τ3.5介质访问控制方式56划分时间片：将信道在时间轴上划分为固定长度的时间段（时间片）。每个节点只能在一个时间片的起始时刻开始发送数据，即用户每次发送数据时必须等到下一个时间片的开始，而且每次传送的数据必须小于等于一个时间片。时隙ALOHA技术时隙ALOHA系统数据帧冲突是整个帧冲突。时隙ALOHA系统的最大信道利用率可达到36.8%。各节点只能在时隙起点发送数据

T冲突ttAB介质访问控制定义信道分配地址的概念随机访问轮询访问3.5介质访问控制方式57CSMA：载波监听多路访问技术。CSMA的基本原理如下：CSMA技术发送前监听信道：网络节点发送数据帧前，首先监听共享信道中是否有其他节点正在发送数据的信号。若监听到信号，则说明信道正忙，否则信道空闲。数据帧发送策略：节点监听到信道空闲是否发送数据帧是由预定控制策略决定的。若信道忙：继续坚持监听信道（持续式），或者暂时退避一段时间再监听（非持续式）。若信道空闲：立即发送数据帧（1-持续），或者为慎重，暂时不发送数据帧（p-持续）。介质访问控制定义信道分配地址的概念随机访问轮询访问CSMA持续式非持续式p-持续1-持续(CSMA/CD)3.5介质访问控制方式58工作过程①监听，如果介质空闲，开始发送数据②如果介质忙，则等待一个随机分布的时间，然后重复步骤①优点等待一个随机时间可以减少再次发生碰撞冲突的可能性缺点等待时间内介质上如果没有数据传送，这段时间是浪费的非持续CSMA介质访问控制定义信道分配地址的概念随机访问轮询访问3.5介质访问控制方式59工作过程①监听，如果介质空闲，则开始发送数据②如果介质忙，则持续监听，一旦空闲立即发送③如果发生冲突，等待一个随机分布的时间再重复步骤①优点持续式的延迟时间要少于非持续式主要问题如果两个以上的节点等待发送，一旦介质空闲就一定会发生冲突1-持续CSMA介质访问控制定义信道分配地址的概念随机访问轮询访问3.5介质访问控制方式60工作过程①监听，如果介质空闲，则以p的概率发送，以(1–p)的概率延迟一个时间单元发送②如果介质忙，则持续监听，一旦空闲重复①③如果发送已推迟一个时间单元，再重复步骤①注意1-持续式是p-持续式的特例p-持续CSMA介质访问控制定义信道分配地址的概念随机访问轮询访问3.5介质访问控制方式61算法状态非持续CSMA1-持续CSMAp-持续CSMA信道空闲立即发送帧立即发送帧以概率p发送帧，以概率1-p推迟发送帧信道忙等待一个随机时间后再监听持续监听，直到信道空闲持续监听，直到信道空闲发生冲突等待一个随机时间再监听等待一个随机时间再监听等待一个随机时间再监听三种CSMA算法比较介质访问控制定义信道分配地址的概念随机访问轮询访问3.5介质访问控制方式62CSMA信道监听时间：只在数据帧发送之前，一旦帧开始发送，不再监听。问题：若发送过程中产生冲突将会浪费信道时间，降低信道利用率。解决：传输过程中持续监听，可以及时发现信道冲突而中止帧的继续发送。问题：CSMA监听信道的时间？产生的问题？如何解决？CSMA/CD(CSMAwithCollisionDetection)：带有冲突检测的载波监听多路访问。CSMA/CD是对1-持续CSMA方式的改进，增加了冲突检测功能。

CSMA/CD（1-持续

）介质访问控制定义信道分配地址的概念随机访问轮询访问3.5介质访问控制方式63CSMA/CD原理：先听后发、边发边听。CSMA/CD工作过程：如右图所示①监听介质：若介质空闲，则发送帧。②若介质忙：持续监听，一旦空闲立即发送。③监听是否冲突：若发生冲突，则发送Jam(强化)信号，等待一个随机分布的时间再重复步骤①。待发送帧装配帧信道忙?发送完?冲突次数过多?发送帧加强冲突发送Jam信号冲突次数N=N+1

设置冲突次数计数器N=0冲突?结束：发送失败结束：发送成功等待后退延迟时间延迟随机后退时间YNYYNYNN

监听信道

监听信道CSMA/CD（1-持续

）介质访问控制定义信道分配地址的概念随机访问轮询访问3.5介质访问控制方式64发送数据监听信道监听信道A发送数据发送数据主机A主机F监听信道主机D主机B主机C监听信道主机EF监听到信道空闲F发送数据发生碰撞F检测到碰撞F停止发送数据，只发送Jam信号A检测到碰撞FAFFFFAAAA碰撞监听信道监听信道t=0t=2τ-δt=τ-δ单程时间τ传播时间

t剩余时间δt=τ-δ/2t=τCSMA/CD碰撞介质访问控制定义信道分配地址的概念随机访问轮询访问δ/2δ/23.5介质访问控制方式65A、B两个节点发生冲突的相关时间点t0时刻：A监听后发送数据帧t1时刻：B监听后发送数据帧t2时刻：发生冲突t3时刻：B检测到冲突t4时刻：A检测到冲突CSMA/CD的冲突时间时间tBA时间tt1t2t3t0t4冲突介质访问控制定义信道分配地址的概念随机访问轮询访问3.5介质访问控制方式66冲突窗口：发送节点发出数据帧后能检测到冲突（碰撞）的最长时间。冲突窗口数值上等于最远两站传播时间的两倍，即2τ，其中：τ是单向最大传播延迟RTT（RoundTripTime）。发送数据帧的时长要求发送帧的时间不能过短至少一个冲突窗口的时间：2τCSMA/CD冲突窗口介质访问控制定义信道分配地址的概念随机访问轮询访问3.5介质访问控制方式671）设置基本退避时间：假设信道两端的单程传播时延为τ，则往返时延为2τ，因此，基本退避时间设置为2τ。2）获取退避时间：若某个帧发送不成功，遭遇了n

次冲突，则发送该帧的退让时间为

r

倍的基本退避时间

r×2τ

其中：r

是离散整数集合{0，1，2，3，…，(2k-1)}中随机取出的一个数

k和

n

满足下列关系：k=min[n,10]

当冲突发生次数

n>10后，取

k=103）设置最大重传次数：例如可以设置为16，当重传（冲突）次数大于该数，则不再重传，并报告出错。

CSMA/CD冲突退避介质访问控制定义信道分配地址的概念随机访问轮询访问3.5介质访问控制方式68CSMA/CA是带有冲突避免的载波侦听多路访问技术。它是为无线局域网设计的一个协议。基本思想：发送方在发送数据前，先发送一个短帧刺激一下接收方，让其也输出一个短帧，回应发送方的同时也可以使接收方附近的其他节点检测到该帧，表示有数据帧要发送，从而在接下去的数据帧传输过程中它们不再发送数据，避免了冲突的发生。CSMA/CA技术介质访问控制定义信道分配地址的概念随机访问轮询访问3.5介质访问控制方式69CSMA/CA工作过程如图所示，节点A向节点B发送数据。A的发射范围B的发射范围ABCFGHDERTSA的发射范围B的发射范围ABCFGHDECTSCSMA/CA工作过程1）节点A向节点B发送一个RTS帧，请求节点B准备接收数据，该短帧（30字节）包含了随后将要发送的数据帧的长度。2）节点B用一个CTS帧作为应答，CTS帧中包含了从接收到的RTS帧中复制过来数据帧的长度。节点A在收到CTS帧后则开始数据帧的传输。介质访问控制定义信道分配地址的概念随机访问轮询访问3.5介质访问控制方式70【例3-3】设某总线网长度为400m，信号传播速度为200m/μs，若位于总线两端的节点A和B在发送数据帧时发生了冲突，问题：（1）A、B两个节点之间信号的传播延迟时间为多少？（2）最多经过多长时间才能检测到冲突？例题【解】（1）A、B两个节点之间信号的传播延迟时间

τ=t传播时间=400m/

200(m/μs)

=2μs

（2）最多经过2τ时间，即4μs才能检测到冲突。

介质访问控制定义信道分配地址的概念随机访问轮询访问3.5介质访问控制方式71【例3-4】设有以太网，总线长度1km，传输速率10Mbps，传播速度200m/μs，数据帧长256bit，其中含32bit帧首部、校验和及其他开销。若1个帧成功发送后的第1个时间片保留给接收方捕获信道，发送1个32bit确认帧。假设没有冲突，则不包括开销的有效数据速率是多少？例题【解】由已知，总线长度：1000m，传播速度：200m/μs

得：传播时间：τ=1000m/200(m/μs)=5μs

往返时间：2τ=2×5μs=10μs

又已知：数据帧长：256bit，其中各种开销：32bit，传输速率：10Mbps

得：数据帧发送时间：t=256bit/10Mbps=256bit

/(10×106)bps=25.6μs

32bit

确认帧的发送时间：tA

=32bit/10Mpbs=3.2μs

理想效率：U=(25.6μs

-3.2μs)/(25.6μs+3.2μs+10μs)=22.4/38.8=0.577

有效数据率：C=10Mbps×0.577=5.77Mbps

介质访问控制定义信道分配地址的概念随机访问轮询访问3.5介质访问控制方式72轮询式介质访问控制是利用令牌传递协议完成数据传输的机制。轮询式介质访问控制方式主要有令牌环（IEEE802.5）和令牌总线（IEEE802.4）两种，前者是物理环，后者是逻辑环。基本思想：环中设置一个令牌，让其在环中依次移动，当一个设备要发送数据帧时，必须等到令牌到达时才可以发送，即持有令牌的设备允许发送数据，当该设备发送结束时，令牌被传递给环中的下一个设备。轮询式介质访问基本概念介质访问控制定义信道分配地址的概念随机访问轮询访问3.5介质访问控制方式73IEEE802.5令牌环结构如图(a)所示。IEEE802.5令牌环介质访问控制的关键部件是转发器TCU，如图(b)所示。令牌环(IEEE802.5)（a）令牌环网结构令牌环主机B主机C主机E主机A主机D转发器TCU线路接收发送缓冲区控制发送接收接收缓冲区联网的计算机线路驱动出环路转发器TCU节点主机入环路出节点入节点（b）转发器TCU结构介质访问控制定义信道分配地址的概念随机访问轮询访问3.5介质访问控制方式74转发（又称监听）状态：转发器工作在转发状态时，从环路输入比特流（其最小延迟为1bit）的同时，监视两种特殊的比特组合。第一种特殊比特组合：本节点的地址。转发器一旦发现有本节点的地址，则立即将环路输入的比特流从转发器输入到本节点。第二种特殊比特组合：空令牌。空令牌平时一直在环路上流动，当节点有数据要发送时，必须等待空令牌的到来。发送状态：当站点处于发送状态时，以帧为单位传输数据。只要节点不处于发送数据状态，转发器就工作在监听状态。令牌环(IEEE802.5)转发器的状态入环路出环路延迟出节点入节点（c）监听状态入环路出环路延迟出节点入节点（d）发送状态介质访问控制定义信道分配地址的概念随机访问轮询访问3.5介质访问控制方式75环网上有节点要发送帧时，必须等待空令牌。当获取空令牌，将其标记位改为忙标记，其后跟随数据帧发送。数据帧在一个循环内其他节点不能发送数据。直至所发送的帧在环中循环一周，回到发送节点，将该帧移去。将令牌忙标记改成空标记，形成空令牌继续传送，供后续节点发送数据帧。令牌环(IEEE802.5)基本工作原理介质访问控制定义信道分配地址的概念随机访问轮询访问3.5介质访问控制方式76令牌环MAC帧结构格式如图所示。令牌环(IEEE802.5)MAC帧结构JK0JK000PPPTMRRRFFZZZZZZI/G15/47位目的地址I(单播)

15/47位源地址

信息字段，长度≥032位CRC校验码JK1JK0

IEACXXACXX1字节1字节1字节2/6字节2/6字节长度可变4字节1字节1字节SDACEDSDACFCDASAINFOFCSEDFSFCS校验内容帧尾序列帧首序列数据帧格式各字段格式令牌帧格式SD/ED：起始/结束定界符0/1：差分曼彻斯特编码特殊比特J、K(违例编码)：

J起始像0，K起始像1，但中间无跳变I：是否中间帧

中间帧

I=1，最后一帧

I=0E：错误位，出错时，E=1AC：访问控制字段PPP：优先级位T：令牌位M：监控位RRR：预约优先级位FC：帧控制FF：帧类型，区分MAC/LLC帧Z：控制位，用于环维护FS：帧状态。A/C：地址识别/帧复制位。

帧到达目的节点，置A=1。

目的节点复制该帧，置C=1。X：未定义介质访问控制定义信道分配地址的概念随机访问轮询访问3.5介质访问控制方式77帧的发送帧的接收回收和恢复令牌令牌的维护保证环内令牌不致丢失消除环上无效帧和无限循环帧保障环路的最小长度令牌环(IEEE802.5)的基本功能介质访问控制定义信道分配地址的概念随机访问轮询访问3.5介质访问控制方式78【例3-7】设环上有20个节点，数据速率为1Mbps，总介质长度为1km，传播速度为200m/μs，每个中继器延迟1bit。问：环上传输数据的位数等于多少？例题【解】环上传输的位数=传播时间×数据速率+中继器延迟因为环的介质长度为1000m，传播速度为200m/μs，因此传播时间为：

τ=1000/200=5(μs)每个中继器延迟1bit，则20个节点有20个中继器共延迟20bit

所以，环上的位数=(5×10-6)s×(1×106)bit/s+20bit=25bit。介质访问控制定义信道分配地址的概念随机访问轮询访问3.5介质访问控制方式79【例3-8】100站点成环，站间平均距离为10m，数据速率为10Mbps，传播速度为200m/μs，每个中继器延迟1bit。问环上可容纳多少比特？例题【解】由已知，得

环上可容纳位数=传播时间×数据速率+中继器延迟

两节点间链路长度的位数=10m/(200m/μs)×(10×106)bps=0.5bit每个中继器延迟1bit。因此，环上可容纳比特数=(1+0.5)×100=150bit介质访问控制定义信道分配地址的概念随机访问轮询访问令牌总线逻辑环主机B主机E主机D主机A主机C3.5介质访问控制方式80令牌总线（IEEE802.4）的物理结构（拓扑结构）如图所示。令牌总线介质访问控制方法：在物理总线上建立逻辑环。各节点根据序号（地址）连成一个逻辑环，如图所示

A→B→E→C→D→A。令牌总线(IEEE802.4)工作原理主机A主机E主机D主机B主机C总线介质访问控制定义信道分配地址的概念随机访问轮询访问3.5介质访问控制方式81控制方式能确保在总线上不会产生冲突。节点具有公平的访问权。若使节点等待令牌的时间为确知的，需限定每个节点发送帧的最大长度。如果只有一个节点有报文发送，其等待令牌的最长时间等于令牌传递时间的总和，而平均等待时间是令牌传递时间总和的一半。允许设置优先级。令牌总线(IEEE802.4)介质访问控制特点介质访问控制定义信道分配地址的概念随机访问轮询访问3.5介质访问控制方式82逻辑环初始化：初始化节点在

0、2、4、6个间隙时间依次发布将地址头两位设置为00、01、10、11的令牌帧，然后中监听介质，若监听到有其他节点也在发布，则停止发布。4个地址对都用完时，获得成功的节点确认自己为令牌持有节点。令牌环征求后继节点：令牌持有节点向其后继节点发出一个令牌帧，后继节点立即发出一个数据帧或令牌帧；在送出令牌后，令牌发出者将监听一个间隙时间，以确定其后继是否正常工作。令牌传递：令牌持有节点发送完数据帧后，将令牌传递给其后继节点，后继节点则立即发送数据帧或令牌帧。节点插入：每个节点均提供让新节点进入环的机会。当节点捕获令牌时，发出一个征求后继节点的帧，邀请节点（地址在自己与逻辑环下一节点之间）加入环。等待1个间隙时间的响应窗口，以确认是否有节点加入。节点删除：当节点TS希望退出逻辑环时，收到令牌时，向其前趋节点PS发出重置后继节点的帧，帧中包含TS后继节点的地址NS，并将令牌传递给后继节点。故障控制：逻辑环故障可能是下游节点失败或多令牌故障。下游节点失败可用令牌环征求后继节点算法处理。多令牌故障可采用各节点放弃令牌方法，若出现无令牌状态，则重新进入逻辑环的初始化。令牌总线(IEEE802.4)介质访问控制算法介质访问控制定义信道分配地址的概念随机访问轮询访问3.6局域网83局域网：在一个较小的地理范围内（如某个学校的校园网络），将各种计算机、外部设备和数据库等应用系统通过双绞线、同轴电缆、光纤等连接介质互相连接起来，组成资源和信息共享的计算机互联网络。特点为一个单位所拥有，且地理范围和站点数目均有限。所有站点共享较高的总带宽（即较高的数据传输率）。较低的时延和较低的误码率。各站为平等关系而非主从关系。能够进行广播和组播。IEEE802.11局域网概述以太网概述局域网的基本概念局域网体系结构3.6局域网84常见的局域网拓扑结构主要有星形、环形、总线型以及星形和总线型结合的复合型结构。3种特殊的局域网拓扑结构实现以太网（目前使用范围最广的局域网）：逻辑拓扑是总线型结构，物理拓扑是星形或拓展星形结构。令牌环（TokenRing，IEEE802.5）：逻辑拓扑是环形结构，物理拓扑是星形结构。FDDI（光纤分布式数据接口，IEEE802.8）。逻辑拓扑是环形结构，物理拓扑是双环结构。局域网的介质访问控制方法CSMA/CD（总线型局域网）令牌总线（总线型局域网）令牌环（环形局域网）局域网拓扑结构及介质访问控制方法IEEE802.11局域网概述以太网概述局域网体系结构3.6局域网85IEEE802标准定义的局域网模型只对应于OSI参考模型的数据链路层和物理层。数据链路层拆分为两个子层：逻辑链路控制（LLC）子层和介质访问控制（MAC）子层。MAC子层：是数据链路层中靠近物理层的子层，与接入的传输介质相关。它向上层屏蔽对物理层访问的各种差异，提供对物理层的统一接口，主要功能包括：组帧和拆卸帧、比特传输差错检测、透明传输。LLC子层：与传输媒体无关。它向网络层提供无确认无连接、带确认无连接、面向连接、高速传送四种不同的连接服务类型。由于以太网在局域网市场中占据垄断地位，几乎成为局域网的代名词，而IEEE802指定的LLC子层作用已经不大，因此，现在很多网卡仅封装MAC协议而没有LLC协议。局域网的体系结构IEEE802.11局域网概述以太网概述局域网体系结构3.6局域网86IEEE802.3标准一种基带总线型的局域网标准，描述了物理层和数据链路层的MAC子层的实现方法。以太网逻辑上采用总线型拓扑结构，以太网中的所有计算机共享同一总线，信息以广播方式发送。为了保证数据通信的方便性和可靠性，以太网简化了通信流程并使用了CSMA/CD方式对总线进行访问控制。以太网应该是指符合DIXEthernetV2标准的局域网，但因其与IEEE802.3标准只有很小的差别，故通常将802.3局域网