第04章数据链路层

1、第04章 数据链路层一 数据链路层概述1 什么是数据链路？为了在相邻的两个节点间实现可靠的数据传输，除了需要一条物理链路外，还必须有一些规程控制数据的传输。把实现这些规程的软硬件加到物理链路上，就构成了所谓的数字链路，我们也称之为逻辑链路链路控制调制解调器 调制解调器 链路控制节点交换机节点交换机数据传输物理链路逻辑链路2 数据链路层的主要功能1）链路管理数据链路的建立、维持和释放就叫链路管理2）帧同步在数据链路层，数据的传送单位是帧。帧同步是指接收方能从收到的比特流中识别出一帧的开始和结束3）流量控制发送方发送数据的速率必须得到控制，以使得接收方能够从容接收5）差错控制有两类差错控制方法前向

2、纠错和检错重发。在计算机通信中通常采用检错重发机制提供差错控制功能6）帧格式接收方能识别帧中的每一个字段7）透明传输不管数据是什么样的比特组合，都能在数据链路上传送8）寻址在多点连接的情况下，确保每一帧能到达正确的目的站点。同时接收方也能知道发送方是哪个站点二 如何识别一帧的开始和结束？1 带字符填充的首尾界符法FlagHeaderPayload fieldTrailerFlag帧举例 Flag=7EH 填充字符=1BH 原始字符 填充以后 41 33 7E 5C 4B 0C 41 33 1B 7E 5C 4B 0C 41 33 1B 5C 4B 0C 41 33 1B 1B 5C 4B 0C

3、 41 33 1B 7E 5C 4B 0C 41 33 1B 1B 1B 7E 5C 4B 0C41 33 1B 1B 5C 4B 0C 41 33 1B 1B 1B 1B 5C 4B 0C2 带位填充的首位界符法比如，在HDLC帧中，用比特序列01111110表示一帧的开始和结束，当有效载荷中出现连续的5个1，则在其后插入1位0；接收方在收到5个1后自动删除紧随其后的03 物理层编码违例法比如，在曼彻斯特编码中，连续的高电平或连续的低电平可用作帧头和帧尾（令牌环使用该方法）三 检错技术1 校验和将数据按一定长度分段，然后以段为单位相加，若最高位有进位，将进位加到最低位上，形成校验码2 块校验

4、码将所有字符的内码异或，结果为块校验码3 循环冗余校验码（CRC）n 信息多项式M（x） 以k个信息比特为系数的多项式n 生成多项式G（x） 根据多项式理论求得、具有某些特殊属性的多项式n 冗余多项式R（x） 以r个冗余比特为系数的多项式n 码多项式P（x） k个信息比特加r个冗余比特构成的码字所对应的多项式n 如何求冗余多项式？ 用G（x）除x r M（x），得到的余式即为冗余多项式R（x）n 如何求码多项式？ P（x）= x r M（x）+ R（x）n 接收方如何检错？ 用G（x）除收到的码多项式，除尽表示无错n 强调 上面的除法都是模2除法，即加减都采用异或运算，不进位和借位n 国际标准

5、生成多项式举例² CRC-12：x 12 + x 11 + x 3 + x 2 + x 1 + x 0² CRC-16：x 16 + x 15 + x 2 + x 0² CRC-ITU：x 16 + x 12 + x 5 + x 0五 差错控制和流量控制技术1 帧编号通过在帧中加上帧编号字段告诉接收方现在过来的是几号帧。帧编号字段的长度是有限的，所以帧的编号是循环编号。假如帧编号的长度是3比特，则最大的帧编号是7，7号以后的帧又从0开始编号2 应答号通过在帧中包含应答号字段告诉发送方下一次期待接收的是几号帧3 肯定应答帧ACK N接收方收到一个通过校验的帧，给发送

6、方返回一个肯定应答帧ACK N，N是应答号，这意味着接收方已经收下了编号为N -1及其以前的各个帧，期待接收N号帧4 否定应答帧NAK N接收方收到一个没有通过校验的帧，给发送方返回一个否定应答帧NAK N，N是应答号，这意味着接收方没能正确接收第N号帧，但已经正确收下了N -1及其以前的各帧5 滑动窗口技术发送窗口 用来限制在收到对方确认以前能发送的帧的数目；仅当编号落在发送窗口内的数据帧才允许被发送出去；发送窗口的长度WT代表收到对方的确认前发送方最多能发送多少个数据帧；其实，发送窗口的长度就是发送缓冲区能容纳的帧数接收窗口 仅当编号落在接收窗口内的数据帧才允许被接收；接收窗口的长度WR等

7、于接收缓冲区的能容纳的帧数滑动窗口的工作原理如下图所示，其中帧编号字段长度为3比特，发送窗口长度为5，接收窗口长度为1Sendera）初始化b）发送0号帧之后c）收到0号帧之后d）收到ACK0之后0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 receiver6 超时重发也就是所谓的自动重发；发送方每发送一个数据帧，便启动一个定时器，如果在定时时间到之前收到了对该数据帧的确认就关闭它的定时

8、器；一旦一个数据帧的定时器超时，发送方便立即启动重传，或者将该数据帧及其以后的帧重发，或者只重传该数据帧7 GO - BACK- N接收方如果收到NAK N或者N号帧超时，就将N号帧及其以后的帧重新发送一遍8 选择重传接收方如果收到NAK N或者N号帧超时，只重发N号帧9 捎带应答A和B进行双工通信，假设A如果收到来自B的数据帧B6，这时A并不马上回复一个专门的肯定应答帧ACK 7，而是等到有数据帧发给B时，在该数据帧的应答号字段插入编号7，表示已经收到B6及其以前的各帧，期待接收第7帧，这就是所谓的捎带应答六 基本的数据链路层协议1 停等协议的工作原理帧0ACK1 帧1ACK0 帧0ACK1

9、 帧0ACK1 帧1NAK11 帧1ACK0 帧0帧0帧0交网络层帧1交网络层帧0交网络层帧0重复丢弃帧1出错丢弃帧1交网络层帧0交网络层超时超时2 连续ARQ协议的工作原理0 1 2 3 4 5 2 3 3 0 1 E D D D 2 3 3 4 5 4 5 3 6 7 0 6 6 ACK1ACK2NAK2ACK3ACK4ACK57 ACK6重传 3 选择重传ARQ协议的工作原理0 1 2 3 4 5 2 3 6 0 1 E 3 4 5 2 3 6 7 0 7 0 3 1 2 3 1 ACK1ACK2NAK2ACK6ACK7ACK0ACK1ACK22 被数据链路层缓冲的帧ACK3将2至5帧一

10、起交网络层3 重传 七 基本的数据链路层协议的性能分析1 停等协议的性能分析tp帧0ACK0tftout帧1帧1tTtptfACK1SenderReceiver在忽略处理时延和应答帧的发送时延的前提下（如下图所示）t o u t = 2 t Pt T = t f + t o u t = t f + 2 t P假设数据帧出错的概率是P，则重传1次的概率为P（1-P），重传2次的概率为P 2（1-P），重传n次的概率为P n（1-P），则一帧的平均传送次数Nr：=1 + 1 × P（1- P）+ 2 × P 2（1- P）+ 3 × P 2（1- P）+ = 1 /（

11、1- P）链路的利用率= t f / t T=1/（2a+1）协议的效率E：=1 / Nr × 链路的利用率=（1- P）/（2a+1）其中a = t P / t f ，叫线路的帧时长2 连续ARQ协议的性能分析W T = 3 tftftftftfW T = 5 tftftftftftftftfa = 2 a = 2 链路效率=1 链路效率 = W /（2a+1） n 如果W > = 2a+1，链路的利用率为1n 如果W < = 2a+1，链路的利用率为W / ( 2a+1 )n 协议效率：E = 链路利用率 ×（1 / N r ）n 连续ARQ采用的是后退N帧

12、的重发机制，即当一个数据帧出错时，要重传N个数据帧，而且可能要重传多次才能成功n 假设一个数据帧传送了i次才成功（重传了i -1次），则为了纠正该数据帧一共传送的帧数：f（i）= 1 + （i -1）N = 1- N + N in 所以为了成功传送一个数据帧，平均传送的帧数：N r = f（i）P i - 1（1- P）= 1 + N /（1 - P）n 当W > = 2a+1时，N近似等于2 a + 1；当W < = 2a+1时，N近似等于W3 选择重传ARQ协议的性能分析n 对于选择重传ARQ协议而言，一帧的平均传送次数：N r = 1 / （1 - P）n 将该式代入E =

13、链路利用率 ×（1 / Nr ）即可得选择重传ARQ协议的效率八 高级数据链路控制协议（HDLC）1 HDLC的基本配置1）3种类型的站n 主站 对链路进行控制，主站发出的帧叫做命令帧n 从站 在主站控制下操作，从站发出的帧叫做响应帧n 复合站 具有主站和从站的双重功能，复合站既可发命令帧，又可发响应帧2）两种链路配置n 非平衡配置 适用于点对点和多点链路，有一个主站和一到多个从站，支持全双工和半双工传输n 平衡配置 仅适用于点对点链路，链路两端的两个站都是复合站，支持全双工和半双工传输3）3种数据传输方式n 正常响应方式（Normal Response Mode，NRM）：适用于不

14、平衡配置。只有主站才能发起向从站的数据传输，而从站只有在主站向它发送命令帧进行轮询时，才能以响应帧的方式回答主站n 异步响应方式（Asynchronous Response Mode，ARM）：适用于不平衡配置。从站可以主动向主站发送响应帧。但主站仍负责对链路进行管理n 异步平衡方式（Asynchronous Balance Mode，ABM）：适用于平衡配置。每个平衡站都可以平等的发起数据传输，无须得到对方的允许2 HDLC的帧格式F A C INFO FCS F 8 8 可扩展 8 可扩展 可变长16OR328 HDLC的帧结构校验区间 透明传输区间 1 2 3 4 5 6 7 8 0 1

15、 1 0 1 N(S)N(R)P/FP/FP/FN(R)M S M 信息帧I管理帧S无编号帧U1）帧标志字段Fn 帧标志字段的长度为8比特，其值为01111110n HDLC规定每个帧的开头头和结尾各有一个帧标志字段F，用作帧的边界。即两个F字段之间的比特串一定是一个帧n 0比特填充法 如果两个F字段之间的比特串中出现和F字段一样的比特组合，会被误认为是帧结束标志，为了避免出现这种错误，HDLC规定使用0比特填充法确保两个F字段之间的比特串中不会出现6个连续的1：发送端在给一串比特流加帧标志前，先扫描该比特流，一旦发现5个连续的1即在其后插入0；接收端收到一帧后，扫描两个F字段之间的比特串，一

16、旦发现5个连续的1即删除其后的02）地址字段An 地址字段总是填入从站的地址或应答站的地址n 地址字段的长度通常是8比特的整数倍，长度可变，地址字段最后一个8位组的以1开头，其余的8位组都以0开头n 全1的地址代表广播地址，全0地址是无效地址3）控制字段Cn 基本的控制字段长度是8比特，扩展的控制字段长度是16比特n HDLC帧分为3大类信息帧（I帧）、监督帧（S帧）和无编号帧（U帧），信息帧的控制字段以0开头，监督帧的控制字段以10开头，无编号帧的控制字段以11开头n N（S）代表当前发送的信息帧的编号，N（R）代表期待下一次收到的帧的编号n 监督帧中的有两个S比特，用于区分4种不同的监督帧

17、n 无编号帧中有5个M比特，用来区分不同作用的无编号帧。目前定义了15种无编号帧n P / F比特是 询问 / 终止 比特，该比特功能较多，以后叙及4）信息字段INFOn 只有I帧和U帧包含信息字段，用户数据包含在该字段之中，其长度可变，但有个上限5）帧校验序列FCSn 校验的范围是从地址字段的第一个比特开始，到信息字段的最后一个比特结束n 使用的生成多项式是x 16 + x 15 + x 2 + x 0，即CCITT的CRC-16。有时也使用CCITT的CRC-323 HDLC帧的类型1）信息帧n 信息帧的控制字段以0开头n N（S） 表示当前发送的信息帧的编号n N（R） 表示期待下一次收

18、到的帧的编号，它同时暗示对方我已经正确无误地收下了编号为N（R）-1的帧及其以前的各帧n P / F比特 也叫询问终止比特，在命令帧中，这个位叫P比特，表示询问，在响应帧中，这个位叫F比特，表示终止n 在NRM中，仅当从站收到主站发来的P比特为1的命令帧（S帧或I帧）后才能发送响应帧，并在最后的一个响应帧中将F比特置1，表示一批数据发送完n 在ARM或ABM中，任何一个复合站收到P比特为1的命令帧应尽早回复本站状态并将F比特置1，不过此时不代表无数据发送或数据已发完2）监督帧n 监督帧的控制字段以10开头n S比特用来区分4种不同的监督帧，分别是RR（接收准备就绪），RNR（接收未就绪），RE

19、J（拒绝），SREJ（选择拒绝）；前3种帧用于连续ARQ协议，最后一种用于选择重传ARQ协议n 监督帧只有N（R）字段，没有N（S）字段4种监督帧的名称和功能S比特帧名功能00RR接收准备就绪准备接受下一帧确认编号为N（R）-1及其以前的各帧01RNR接收未就绪暂停接收下一帧确认编号为N（R）-1及其以前的各帧10REJ拒绝从N（R）起所有的帧被否认但确认编号为N（R）-1及其以前的各帧11SREJ选择拒绝只否认编号为N（R）的帧但确认编号为N（R）-1及其以前的各帧3）无编号帧n 无编号帧的控制字段以11开头，用于建立和释放链路，不含编号字段，不影响带编号帧的交换顺序n M比特用来区分不同作

20、用的无编号帧，目前已经定义了15种无编号帧15种无编号帧的名称和功能帧名功能描述置正常响应方式SNRM命令置数据传送方式为NRM置扩展的正常响应方式SNRME命令置数据传输方式为扩展的NRM置异步响应方式SARM命令置数据传输方式为ARM置扩展的异步响应方式SARME命令置数据传输方式为扩展的ARM置异步平衡方式SABM命令置数据传输方式为ABM置扩展的异步平衡方式SABME命令置数据传输方式为扩展的ABM置初始化方式SIM命令由接收站启动数据链路控制过程拆除连接DISC命令拆除逻辑连接无编号应答UA响应对置方式命令的肯定应答非连接方式DM响应从站处于逻辑上断开的状态请求拆除连接RD响应请求断

21、开逻辑连接15种无编号帧的名称和功能（续）请求初始化方式RIM响应请求发送SIM命令，启动初始化过程无编号信息UI命令响应交换控制信息无编号询问UP命令请求发送控制信息复位（REST）命令用于复位，重置N（R）、N（S）交换标识XID命令响应交换标识和状态测试命令响应交换用于测试的信息字段帧拒绝响应报告接收到不能接收的帧4 HDLC的操作a） 链路建立和清除b） 双向数据交换c） 接收 站忙d） 后退 重发e） 超时 重发SABMSABM UADISCUAA B I00I01I11I21I13I32I24I34RR4I30RNR4RNR0PRNR4FRNR0PRR4FI40I30I40I50R

22、EJ4I40I50I60I20RNR0PRR3FI30RR4RR3I30超时超时A B A B A B A B 九 互联网的链路层协议点对点协议（PPP）PPP是一种被广泛使用的、数据链路层协议，它提供了在串行点对点链路上传输多种网络层数据报的方法，既支持异步链路（无奇偶校验的8比特数据），也支持面向比特的同步链路，现在已成为互联网标准。IETF对PPP设计提出的最初要求是：n 封包成帧 发送方的PPP协议实体将网络层分组封装成链路层帧，以使接收方能确定帧的起、止位置以及帧中数据分组的起、止位置n 透明传输 PPP协议允许在网络层分组中使用任意一种比特组合n 支持多种网络层协议 PPP允许多种

23、的网络层协议同时运行于同一条物理链路之上，如IP、IPX、AppleTalk等。这意味着PPP帧中应该有一个协议类型字段，以使得接收方PPP协议实体能将受到的帧导向合适的网络层协议实体n 支持多种类型的链路 PPP能工作在多种类型的物理链路之上，包括同步的和异步的n 差错检测 接收方的PPP协议实体能检测帧中的比特级差错n 连接的活性 PPP能检测出链路级故障并向网络层通报故障n 网络层地址协商 PPP能为通信双方的网络层模块提供一个机制来获知或配置对方的网络层地址1 PPP的组成1 2 3 物理层协议用于封装的协议Link Control Protocol（LCP）Network Contr

24、ol Protocol（NCP）PPP 上层协议（如IP、IPX、Apple Talk等）PPP由3部分组成，分别是封装协议、LCP和NCP，它们构成一个3层的结构n 用于封装的协议 IP数据报在放到PPP链路上传输前，必须先将它封装成数据帧，这项工作由PPP的封装协议完成。其封装IP数据报的方法和HDLC是类似的n 链路控制协议LCP 建立、配置和测试数据链路层连接n 网络控制协议NCP 一个协议族，每个3层协议都有与之对应的NCP，如与IP对应的是IPCP，与IPX对应的是IPXCP，与Apple Talk对应的是ATALKCP等。在网络层数据报通过PPP链路传输之前，允许网络层模块用来配

25、置它们自己2 PPP的帧格式（面向字节的协议）ISO HDLC Frame Flag Address Control Data FCS Flag 1B 1B 1 OR 2B <=1500B 2OR 4B 1B PPP Frame Flag Address Control Data FCS Flag 1B 1B 1 OR 2B <=1500B 2OR 4B 1B Protocol 1 OR 2B n PPP的帧格式和HDLC是类似的n 帧标志字段Flag 该字段的值仍为01111110（0X7E）n 地址字段Address 始终为11111111（0XFF），实际上地址字段在此不起任

26、何作用n 控制字段Control 该字段的值始终为0X03n 协议字段Protocol 该字段填入的是网络层协议代码：如果协议字段的值为0X0021，PPP帧的信息字段就是IP分组；如果协议字段的值为0XC021，PPP帧的信息字段就是LCP分组；如果协议字段的值为0X8021，PPP帧的信息字段就是NCP分组n PPP 是面向字节的，所有的 PPP 帧的长度都是整数字节n 关于透明传输¢ PPP用在同步链路上时，协议规定采用硬件完成比特填充（和HDLC的做法相似）¢ PPP用在异步链路上时，使用特殊的字符填充法：将信息字段中出现的每一个 0X7E 字节转变成为 2 字节序

27、列（0X7D, 0X5E）；若信息字段中出现一个 0X7D 的字节, 则将其转变成为 2 字节序列（0X7D, 0X5D）；若信息字段中出现 ASCII 码的控制字符（即数值小于 0X20 的字符），则在该字符前面要加入一个 0X7D 字节，同时将该字符的编码加以改变3 PPP协议的工作过程链路建立身份认证网络打开终止静止检测到载波 LCP选项协商 失败 通过认证失败 NCP配置 通信结束 载波停止 n 一旦串行链路两头的端点建立起物理层连接，它们中的LCP实体便开始交换一系列的LCP分组以建立和配置数据链路层连接。当然这些LCP分组在送到物理层之前被封装成了PPP帧，这些帧的协议字段设置为L

28、CP，信息字段包含具体的链路层参数，包括最大帧长、使用何种鉴别协议等n 当数据链路层连接建立之后，两端的LCP实体通过交换LCP分组进行身份鉴别n 鉴别通过后，两端的NCP协议实体便通过交换一系列的NCP分组配置两端的网络层模块。假如PPP链路上运行的是IP协议，则由PPP链路两头的IPCP协议实体通过交换IPCP报文配置两端的IP协议模块，如分配IP地址等。NCP分组在交给物理层之前同样被封装成PPP帧，其协议字段被置成NCP。当网络层配置结束后，PPP链路即可传输网络层数据报了n 当通信完成后，一方的LCP协议实体发LCP终止请求分组，对方的LCP协议实体回复一个LCP终止确认分组，PPP链路进入终止状态，当物理层连接断开后从终止状态进入静止状态。PPP链路的状态变迁如下图所示4 LCP选项在链路建立阶段，可以通过LCP协商链路层连接的许多方面，包括n 采用何种认证协议（Authentication Protocol） PPP允许被呼叫方对呼叫方的身份进行验证，以证实呼叫方是否拥有有效的用户名和密码。有两种认证协议可供选择，分别是口令认证协议PAP和挑战握手认证协议CHAPn 回拨