第3数据链路层

1、computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 1 / 169v定义和功能定义和功能v数据帧的组成数据帧的组成v可靠性传输可靠性传输v数据链路层示例数据链路层示例computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 2 / 169v为网络层提供一个较好的服务接口为网络层提供一个较好的服务接口v为网络层提供可靠的传输服务为网络层提供可靠的传输服务数据链路层的上层是网络层，数据链路层数据链路层的上层是网络层，数据链路层将借助于物理层为网络层提供服务将借助于物理层为网络层提供服务数据链路层的协议数据单元（数

2、据链路层的协议数据单元（pdu）是帧）是帧computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 3 / 169v数据链路层的任务是把网络层的数字数据组合成帧，并数据链路层的任务是把网络层的数字数据组合成帧，并加上一定的校验码后交物理层加上一定的校验码后交物理层v物理层用不同的信号表示二进制数据位，从而把帧用一物理层用不同的信号表示二进制数据位，从而把帧用一段连续的信号串表示并传送到目的主机段连续的信号串表示并传送到目的主机v目的主机的物理层将信号还原成比特串交数据链路层，目的主机的物理层将信号还原成比特串交数据链路层，井数据链路层确认正确后送到网络层

3、井数据链路层确认正确后送到网络层v数据链路层为源和目的主机的网络层之间提供一条可靠数据链路层为源和目的主机的网络层之间提供一条可靠的数据链路的数据链路computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 4 / 169v所谓相连，可以理解为物理介质的连接，但当所谓相连，可以理解为物理介质的连接，但当采用多路复用技术时也可以是信道的连接，其采用多路复用技术时也可以是信道的连接，其特征为：所传输的数据是按序的特征为：所传输的数据是按序的v物理链路：一段无源的点到点的物理连接，中物理链路：一段无源的点到点的物理连接，中间没有任何交换节点间没有任何交换节点v

4、数据链路：包括一条物理连接和为实现数据传数据链路：包括一条物理连接和为实现数据传输而在两端配置的硬件及其相关的通信协议输而在两端配置的硬件及其相关的通信协议computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 5 / 169v数据链路层的服务是通过有无连接、数据链路层的服务是通过有无连接、有无确认来区分的有无确认来区分的无确认无连接的服务无确认无连接的服务有确认无连接的服务有确认无连接的服务有确认有连接的服务有确认有连接的服务computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 6 / 169v确认：接收方

5、在收到数据帧后，必须给确认：接收方在收到数据帧后，必须给发送方发回一个确认发送方发回一个确认v面向连接：发送方和接收方在传输数据面向连接：发送方和接收方在传输数据之前必须建立一条数据链路，传输结束之前必须建立一条数据链路，传输结束后必须释放该链路后必须释放该链路 computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 7 / 169v无确认无连接的服务无确认无连接的服务v有确认无连接的服务有确认无连接的服务v有确认有连接的服务有确认有连接的服务computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 8 / 16

6、9v无确认是指接收方在收到数据帧后，毋需发回一个确认无确认是指接收方在收到数据帧后，毋需发回一个确认v无连接的服务是指在数据传输前毋需建立数据链路无连接的服务是指在数据传输前毋需建立数据链路v物理线路的连接并非意味着提供了有连接的服务物理线路的连接并非意味着提供了有连接的服务v无确认并非不可靠，其可靠性可由上层负责无确认并非不可靠，其可靠性可由上层负责例如：局域网例如：局域网1.共享信道不需要、也不允许建立连接共享信道不需要、也不允许建立连接2.信道较为理想，数据传输的误码率很低信道较为理想，数据传输的误码率很低3.即使出错或丢失由上层负责恢复即使出错或丢失由上层负责恢复computer ne

7、tworks v5 cs.sjtu 2021-11-10第3章 数据链路层 9 / 169v无确认无连接的服务无确认无连接的服务v有确认无连接的服务有确认无连接的服务v有确认有连接的服务有确认有连接的服务computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 10 / 169v使用前不建立连接，即不建立数据链路，但每帧传输使用前不建立连接，即不建立数据链路，但每帧传输必须得到确认必须得到确认v这在信号传播延时较大、线路状态不一定很可靠的情这在信号传播延时较大、线路状态不一定很可靠的情况下是有效的况下是有效的例如：无线通信例如：无线通信 1.如建立连接，

8、则信道使用率很低如建立连接，则信道使用率很低2.然而，由于数据传输的误码率相对较然而，由于数据传输的误码率相对较高，所以确认是必要的高，所以确认是必要的computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 11 / 169v无确认无连接的服务无确认无连接的服务v有确认无连接的服务有确认无连接的服务v有确认有连接的服务有确认有连接的服务computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 12 / 169v使用前先建立连接，即先建立数据链路，并且每使用前先建立连接，即先建立数据链路，并且每帧的传输必须得到确认

9、帧的传输必须得到确认v有连接的服务必须在使用前先建立连接（即建立有连接的服务必须在使用前先建立连接（即建立数据链路），然后使用，最后释放连接数据链路），然后使用，最后释放连接例如：电话例如：电话 1.电话是一种实时的应用，如不是面向连电话是一种实时的应用，如不是面向连接，则实时性难以得到保证接，则实时性难以得到保证2.电话是一对一的、双向的数据传输电话是一对一的、双向的数据传输computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 13 / 169v将传输的信息组合成帧将传输的信息组合成帧v校验和重发校验和重发v流量控制流量控制保证直接相连的两台主机的

10、可靠性传输保证直接相连的两台主机的可靠性传输computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 14 / 169v定义和功能定义和功能v数据帧的组成数据帧的组成v可靠性传输可靠性传输v数据链路层示例数据链路层示例computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 15 / 169v字符计数法字符计数法v带字符填充的首尾界符法带字符填充的首尾界符法v带位填充的首尾标志法带位填充的首尾标志法 v物理层编码违例法物理层编码违例法帧的组成必须保证能识别一个完整的帧，并保证一帧的组成必须保证能识别一个完整的帧，并

11、保证一旦出现传输差错而导致前一个帧丢失时，也必须能旦出现传输差错而导致前一个帧丢失时，也必须能识别后一个帧，即具有识别后一个帧，即具有帧帧再同步能力再同步能力computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 16 / 169v假设帧的长度用一个字节表示，并作为帧的头部假设帧的长度用一个字节表示，并作为帧的头部 一旦帧长度计数被误读，将无法再同步，所以不能采用一旦帧长度计数被误读，将无法再同步，所以不能采用 第第1帧帧第第2帧帧帧长度计数错帧长度计数错帧长度计数帧长度计数第第1帧帧第第4帧帧第第3帧帧第第2帧帧5123456789801234568

12、789012351234767898012345687890123tnbm p188 fig. 3-4 字符计数成帧法字符计数成帧法computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 17 / 169v字符计数法字符计数法v带字符填充的首尾界符法带字符填充的首尾界符法v带位填充的首尾标志法带位填充的首尾标志法 v物理层编码违例法物理层编码违例法帧的组成必须保证能识别一个完整的帧，帧的组成必须保证能识别一个完整的帧，并保证一并保证一旦出现传输差错而导致前一个帧丢失时旦出现传输差错而导致前一个帧丢失时，也必须能，也必须能识别下一个帧，识别下一个帧，即具

13、有帧再同步能力即具有帧再同步能力computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 18 / 169v用特殊的字符作为帧头和帧尾界符用特殊的字符作为帧头和帧尾界符flag headerpayload field trailer flag这是一种面向字符的帧格式，所传输的数据都是字符这是一种面向字符的帧格式，所传输的数据都是字符（ascii或或ebcdic字符），但帧中不允许出现帧界符字符），但帧中不允许出现帧界符标志，在面向字符的串型通信中常使用这种格式标志，在面向字符的串型通信中常使用这种格式(ppp)接收方一旦丢失了一个接收方一旦丢失了一个fl

14、ag，只要继续搜索下一个，只要继续搜索下一个flag，就可重新确定帧边界，即具有再同步能力，就可重新确定帧边界，即具有再同步能力tnbm p189 fig. 3-5 (a) 由由flag标志的一个帧标志的一个帧computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 19 / 169v面向字符的帧格式不适宜传输数据中包含二进制数的帧，面向字符的帧格式不适宜传输数据中包含二进制数的帧，因为在包含二进制数的帧中很可能出现与因为在包含二进制数的帧中很可能出现与flag相同的相同的bit序列（通常序列（通常flag用用ascii字符字符7eh定义）定义）v一种方

15、法是在二进制数中偶然出现的一种方法是在二进制数中偶然出现的flag前再插入一个前再插入一个esc （ascii字符字符1bh），这种方法称为字符填充法），这种方法称为字符填充法 41 33 7e 5c 4b 0c41 33 1b 5c 4b 0c41 33 1b 7e 5c 4b 0c41 33 1b 1b 5c 4b 0c41 33 1b 7e 5c 4b 0c41 33 1b 1b 5c 4b 0c41 33 1b 1b 1b 7e 5c 4b 0c41 33 1b 1b 1b 1b 5c 4b 0ccomputer networks v5 cs.sjtu 2021-11-10第3章 数据

16、链路层 20 / 169v字符计数法字符计数法v带字符填充的首尾界符法带字符填充的首尾界符法v带位填充的首尾标志法带位填充的首尾标志法 v物理层编码违例法物理层编码违例法帧的组成必须保证能识别一个完整的帧，并保证一帧的组成必须保证能识别一个完整的帧，并保证一旦出现传输差错而导致前一个帧丢失时，也必须能旦出现传输差错而导致前一个帧丢失时，也必须能识别下一个帧，即具有帧再同步能力识别下一个帧，即具有帧再同步能力computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 21 / 169v在面向二进制位的同步串行通信中常使用在面向二进制位的同步串行通信中常使用带

17、带位填充的首尾标志位填充的首尾标志格式，如格式，如hdlc 这是一种面向二进制位的帧格式，把所有需传输的数据（不论是字符这是一种面向二进制位的帧格式，把所有需传输的数据（不论是字符或表示一个浮点数的二进制位串，还是一个或表示一个浮点数的二进制位串，还是一个mp3的文件）一字排开，的文件）一字排开，并以特殊的位模式并以特殊的位模式01111110作为帧标志，即一个帧的开始（同时标志作为帧标志，即一个帧的开始（同时标志前一个帧的结束）前一个帧的结束） 如果由于干扰，一个帧标志没有被正确接收，则继续扫描接收串，一如果由于干扰，一个帧标志没有被正确接收，则继续扫描接收串，一旦扫描到旦扫描到011111

18、10，即新的一帧从此开始，即具有再同步能力，即新的一帧从此开始，即具有再同步能力 即使字符也并非都是即使字符也并非都是8位的，东方文字是位的，东方文字是16位，位，unicode是是16位位computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 22 / 169v当帧中出现一个与帧标志相同的位串当帧中出现一个与帧标志相同的位串01111110，则在，则在连续连续5个个1后自动插入一个后自动插入一个0，即变成，即变成01111101，接收，接收方将自动删除第方将自动删除第5 个个1后的后的0v这称为位插入法，也称为透明传输这称为位插入法，也称为透明传输0

19、11011111111111111110010011011111011111011111010010011011111111111111110010tnbm p190 fig. 3-6 (a) (b) (c) 位插入法示例位插入法示例computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 23 / 169v字符计数法字符计数法v带字符填充的首尾界符法带字符填充的首尾界符法v带位填充的首尾标志法带位填充的首尾标志法 v物理层编码违例法物理层编码违例法帧的组成必须保证能识别一个完整的帧，并保证一帧的组成必须保证能识别一个完整的帧，并保证一旦出现传输差错而导

20、致前一个帧丢失时，也必须能旦出现传输差错而导致前一个帧丢失时，也必须能识别下一个帧，即具有帧再同步能力识别下一个帧，即具有帧再同步能力computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 24 / 169v在曼切斯特编码中，连续高电平或连续在曼切斯特编码中，连续高电平或连续低电平可用作帧界符低电平可用作帧界符 采用冗余编码技术，如曼切斯特编码，即对连续两个信号进行采用冗余编码技术，如曼切斯特编码，即对连续两个信号进行采样，可得到一个二进制位采样，可得到一个二进制位 数据数据0：低：低-高电平对高电平对 数据数据1：高：高-低电平对低电平对 高高- -

21、高电平对和低高电平对和低- -低电平对没有使用，如在二进制低电平对没有使用，如在二进制编码中出现则称为编码违例，但这两种违例编码正编码中出现则称为编码违例，但这两种违例编码正好可用作帧界符，在令牌环网中使用编码违例格式好可用作帧界符，在令牌环网中使用编码违例格式computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 25 / 169v定义和功能定义和功能v数据帧的组成数据帧的组成v可靠性传输可靠性传输v数据链路层示例数据链路层示例computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 26 / 169v差错控制

22、：校验、重发和序号差错控制：校验、重发和序号避免帧错误的保证：帧的校验避免帧错误的保证：帧的校验避免帧丢失的保证：超时和重发避免帧丢失的保证：超时和重发避免帧重复的保证：帧有序号避免帧重复的保证：帧有序号v流量控制：窗口协议流量控制：窗口协议发送方和接收方之间传输速率的协调发送方和接收方之间传输速率的协调v协议描述和验证协议描述和验证computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 27 / 169v确认确认v数据帧丢失数据帧丢失v重复帧重复帧如何保证数据帧的正常传输，将通过如何保证数据帧的正常传输，将通过三种手段处理三种可能出现的情况三种手段处

23、理三种可能出现的情况 ：computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 28 / 169接收方在收到了正确的帧后向发送方发接收方在收到了正确的帧后向发送方发肯定性确认；如收到的帧有问题，则发肯定性确认；如收到的帧有问题，则发否定性确认，此时发送方将重发此帧否定性确认，此时发送方将重发此帧 确认的前提是必须经过差错检测确认的前提是必须经过差错检测computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 29 / 169v差错的产生主要是在传输时，数据中的一位或差错的产生主要是在传输时，数据中的一位或几位因噪

24、声干扰而出错几位因噪声干扰而出错v噪声分两种：噪声分两种： 信道所固有的、持续存在的热噪声信道所固有的、持续存在的热噪声 外界突发原因而造成的随机的冲击噪声外界突发原因而造成的随机的冲击噪声 v通常接收方应能检错，甚至纠错通常接收方应能检错，甚至纠错 v纠错码是除纠错码是除m个数据位外增加个数据位外增加r个冗余位作为个冗余位作为纠错位，传输的总长度为纠错位，传输的总长度为n = m + r computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 30 / 169v纠错码：纠错码：海明（海明（hamming） 码码v检错码：检错码：校验和（校验和（che

25、ck sum）块校验码（块校验码（block check code）循环冗余检错码循环冗余检错码 crc （cyclic redundancy check）computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 31 / 169v算法简单、实现容易，但检错强度较弱算法简单、实现容易，但检错强度较弱以以16位为例：位为例：4865h+6c6ch+6f20h+776fh+726ch+642eh+进位进位=71fchhelloworld.48656c6c6f20776f726c642e71fc将发送的数据看成是二进制整数序列，并划分成一段段规将发送的数据看成

26、是二进制整数序列，并划分成一段段规定的长度（如定的长度（如8位、位、16位、位、32位等），计算它们的和，如位等），计算它们的和，如计算和时有进位，则将进位加到最后的校验和中，并将校计算和时有进位，则将进位加到最后的校验和中，并将校验和与数据一起发送；在接收端，重新计算校验和，并与验和与数据一起发送；在接收端，重新计算校验和，并与接收到的原校验和比较，如要传输接收到的原校验和比较，如要传输“ hello world.” computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 32 / 169v纠错码：纠错码：海明（海明（hamming） 码码v检错码：

27、检错码：校验和（校验和（check sum）块校验码（块校验码（block check code）循环冗余检错码循环冗余检错码 crc （cyclic redundancy check）computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 33 / 169v块校验码块校验码bcc（block check code）简单常用，但检）简单常用，但检错的强度较弱，如在同一列上有偶数位错，则不能检测错的强度较弱，如在同一列上有偶数位错，则不能检测如传输的数据都是如传输的数据都是ascii字符（即面向字符，这在应用中很多），字符（即面向字符，这在应用中很多），

28、每个字符进行奇偶校验，然后把所有的字符（连同奇偶位）进行异每个字符进行奇偶校验，然后把所有的字符（连同奇偶位）进行异或运算，运算结果即为其块校验码，通常发送端在发送完数据区的或运算，运算结果即为其块校验码，通常发送端在发送完数据区的结束标志后发送结束标志后发送bcc，接收端一边接收数据一边计算，接收端一边接收数据一边计算bcc，最后，最后与接收到的与接收到的bcc比较，以确认所接收到的数据正确与否比较，以确认所接收到的数据正确与否 如如“ hello world.”，采用偶校验，校验后的字符序列为：，采用偶校验，校验后的字符序列为：48h 65h 6ch 6ch 6fh a0h 77h 6fh

29、 72h 6ch e4h 2eh = 2ehhelloworld.48656c6c6fa0776f726ce42e2ecomputer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 34 / 169v纠错码：纠错码：海明（海明（hamming） 码码v检错码：检错码：校验和（校验和（check sum）块校验码（块校验码（block check code）循环冗余检错码循环冗余检错码 crc （cyclic redundancy check）computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 35 / 169v任何

30、一个任何一个k位的帧都可看成为一个位的帧都可看成为一个k-1次的多项式次的多项式m(x)的系数列表的系数列表 如：如：1011001看成是多项式看成是多项式x6+x4+x3+x0的系数列表的系数列表v设定一个生成多项式设定一个生成多项式g(x)，g(x)为为r阶，阶，krv如如xrm(x)/g(x) = q(x) + r(x)/g(x) 其中其中q(x)为商、为商、r(x)为余数，为余数，r(x)即为即为m(x)的的crc码码v将将crc码接在帧后一起发送，即发送数据为码接在帧后一起发送，即发送数据为xrm(x) + r(x) v二进制运算中，减法和加法都做异或运算：二进制运算中，减法和加法都

31、做异或运算：0+1=1,1+1=0 v因为因为( xrm(x) - r(x) )一定能被一定能被g(x)整除，即余数为整除，即余数为0，则接收方，则接收方只要计算只要计算crc，并所得余数为，并所得余数为0即为正确即为正确computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 36 / 169如一帧为如一帧为1101011011即：即：m(x) = x9+x8+x6+x4+x3+x+1 g(x) = x4+x+1 t(x) = x4m(x) =x4(x9+x8+x6+x4+x3+x+1) =x13+x12+x10+x8+x7+x5+x4 compute

32、r networks v5 cs.sjtu 2021-11-10第3章 数据链路层 37 / 169v帧：帧：1101011011v除数：除数：10011v实际传输帧：实际传输帧： 1 0 0 1 1 111011000000110000001011100000011110000000001101010101100000000000001101010101101101100000010011010101000001101100110100000余数余数1101011011帧数据帧数据1110余数余数tnbm p198 fig. 3-8 crc码计算举例码计算举例computer network

33、s v5 cs.sjtu 2021-11-10第3章 数据链路层 38 / 16911010110110000/10011 = 1100001010 1110 即即11010110110000 + 1110能被能被10011整除整除（注：模（注：模2运算的加、减和异或，其运算结果相同）运算的加、减和异或，其运算结果相同）发送方发送的是发送方发送的是t(x)+r(x) 能被能被g(x)整除整除，如接收，如接收方收到的是方收到的是t(x)+r(x)+e(x)，除非，除非e(x)是是g(x)的整倍的整倍数，否则不能被整除，即都能被检测到已出错数，否则不能被整除，即都能被检测到已出错computer

34、networks v5 cs.sjtu 2021-11-10第3章 数据链路层 39 / 169vcrc-12：x12 +x11 +x3 +x2 +x1 + 1 用于字符长度为用于字符长度为6位位 vcrc-16 ：x16 +x15 +x2 + 1 用于字符长度为用于字符长度为8位位 vcrc-ccitt ：x16 +x12 +x5 + 1 用于字符长度为用于字符长度为8位位 vieee 802 ：x32 +x26 +x23 +x22 +x16 +x12 +x11 +x10 +x8 +x7 +x5 +x4 +x2 +x1 + 1ccitt：consultative committee on i

35、nternational telegraphy and telephone 国际电报和电话咨询委员会，即现在的国际电报和电话咨询委员会，即现在的 itu-titu-t：international telecommunications union telecommunications standardization sector 国际电信联盟国际电信联盟 电信标准分部电信标准分部computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 40 / 169v确认确认v数据帧丢失数据帧丢失v重复帧重复帧如何保证数据帧的正常传输：通过三如何保证数据帧的正常传输：通

36、过三种手段处理三种可能出现的情况种手段处理三种可能出现的情况 ：computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 41 / 169v通过发送方的重发定时器（超时）解决通过发送方的重发定时器（超时）解决v超时（超时（timeout）：在传输过程中，如果所发）：在传输过程中，如果所发送的帧丢失，接收方根本没有收到，不可能发送的帧丢失，接收方根本没有收到，不可能发送确认帧（包括否定性确认），当然发送方也送确认帧（包括否定性确认），当然发送方也不可能等待收到如何信息，所以发送方每发送不可能等待收到如何信息，所以发送方每发送一帧，就启动一个重发定时器，在所

37、设定的时一帧，就启动一个重发定时器，在所设定的时间内，一般都应该收到确认，如收不到确认，间内，一般都应该收到确认，如收不到确认，则在重发定时器溢出后，再重发此帧则在重发定时器溢出后，再重发此帧 computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 42 / 169v确认确认v数据帧丢失数据帧丢失v重复帧重复帧如何保证数据帧的正常传输：通过三如何保证数据帧的正常传输：通过三种手段处理三种可能出现的情况种手段处理三种可能出现的情况 ：computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 43 / 169v重发机

38、制也包括当接收方发送的确认帧丢失重发机制也包括当接收方发送的确认帧丢失而导致发送方的重发定时器超时而重发而导致发送方的重发定时器超时而重发v由于接收方确认帧的丢失，导致发送方多次由于接收方确认帧的丢失，导致发送方多次发送同一帧，接收方也将多次收到同一帧，发送同一帧，接收方也将多次收到同一帧，为能识别是否为相同的帧，应该在帧格式中为能识别是否为相同的帧，应该在帧格式中增加一个帧的编号（序号）增加一个帧的编号（序号） computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 44 / 169基于上述讨论，一个数据链路层的帧至少应该包括下基于上述讨论，一个数据

39、链路层的帧至少应该包括下列内容：列内容： 信息信息 校验信息校验信息 info crc确认号确认号ack_no帧序号帧序号seq_no帧类型帧类型type帧头帧头computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 45 / 169v差错控制：校验、重发和序号差错控制：校验、重发和序号避免帧错误的保证：帧的校验避免帧错误的保证：帧的校验避免帧丢失的保证：超时和重发避免帧丢失的保证：超时和重发避免帧重复的保证：帧有序号避免帧重复的保证：帧有序号v流量控制：窗口协议流量控制：窗口协议发送方和接收方之间的协调发送方和接收方之间的协调v协议描述和验证协议描述

40、和验证computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 46 / 169v发送速率和接收速率的匹配即流量控制发送速率和接收速率的匹配即流量控制如接收方的处理能力低于发送方，即使传输中没有如接收方的处理能力低于发送方，即使传输中没有出错，也可能被出错，也可能被“ 淹没淹没”，所以通常在接收方的缓，所以通常在接收方的缓冲区到达一定量时，应及时通知发送方，暂停发送，冲区到达一定量时，应及时通知发送方，暂停发送，等候通知，这就是流量控制机制等候通知，这就是流量控制机制 基本数据链路协议基本数据链路协议 滑动窗口协议滑动窗口协议computer netwo

41、rks v5 cs.sjtu 2021-11-10第3章 数据链路层 47 / 169a、b两台主机要求可靠的、面向连接的通两台主机要求可靠的、面向连接的通信，在接收方的数据链路层，目前正运行信，在接收方的数据链路层，目前正运行的是的是wait_for_event(&event)，即等待某，即等待某个事件发生个事件发生可以这样理解：在一台主机中，物理层、数据可以这样理解：在一台主机中，物理层、数据链路层、网络层等，都有各自的进程在运行，链路层、网络层等，都有各自的进程在运行，并且假设：并且假设：computer networks v5 cs.sjtu 2021-11-10第3章 数据链

42、路层 48 / 169v 如如event = checksum_err，意即所接收帧的校验和错，意即所接收帧的校验和错，应考虑不发送确认帧应考虑不发送确认帧ack，或发送否定性确认帧，或发送否定性确认帧nakv 如如event = frame_arrival，即帧已到达并校验正确，应调，即帧已到达并校验正确，应调用用from_physical_layer，从物理层取得帧，并检查帧头，从物理层取得帧，并检查帧头的控制信息，如一切正常，则仅把其中的分组交网络层的控制信息，如一切正常，则仅把其中的分组交网络层v 一系列过程和数据结构的定义：一系列过程和数据结构的定义：tnbm p202 fig. 3

43、-9 如发生了某个事件，此过程将返回参数如发生了某个事件，此过程将返回参数event， event有两个取值：有两个取值：checksum_err（crc错）错）frame_arrival（正确收到）（正确收到）computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 49 / 169v无限制的单工协议无限制的单工协议（协议（协议1）tnbm p205 fig. 3-10 一种无限制的单工协议一种无限制的单工协议v单工的停单工的停 等协议等协议（协议（协议2）tnbm p207 fig. 3-11 一个单工的停一个单工的停 等协议等协议v噪声信道的单工协

44、议噪声信道的单工协议（协议（协议3）tnbm p210 fig. 3-12 一个肯定性确认和超时重发协议一个肯定性确认和超时重发协议computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 50 / 169v链路是理想的传输通道，所传输的任何数据链路是理想的传输通道，所传输的任何数据既不会出错也不会丢失既不会出错也不会丢失即：不需校验，也不可能出现重发，毋需差错控制即：不需校验，也不可能出现重发，毋需差错控制v不管发送方以怎样的速率发送数据，接收方不管发送方以怎样的速率发送数据，接收方都能及时接收并处理都能及时接收并处理即接收端处理器的处理速度无限高，处

45、理时间可忽即接收端处理器的处理速度无限高，处理时间可忽略不计，缓冲区空间无限大，毋需流量控制略不计，缓冲区空间无限大，毋需流量控制tnbm p205 fig. 3-10 一种无限制的单工协议一种无限制的单工协议 一种理想的环境，理想的协议，假定：一种理想的环境，理想的协议，假定：computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 51 / 169void sender1(void) frame s; packet buffer; while (true) from_network_layer(&buffer);=buffer;t

46、o_physical_layer(&s); computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 52 / 169void receiver1(void) frame r; event_type event; while (true) wait_for_event(&event); from_physical_layer(&r); to_network_layer(&);computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 53 / 169v无限制的单工协议无限制

47、的单工协议（协议（协议1）tnbm p205 fig. 3-10 一种无限制的单工协议一种无限制的单工协议v单工的停单工的停 等协议等协议（协议（协议2）tnbm p207 fig. 3-11 一个单工的停一个单工的停 等协议等协议v噪声信道的单工协议噪声信道的单工协议（协议（协议3）tnbm p210 fig. 3-12 一个肯定性确认和超时重发协议一个肯定性确认和超时重发协议computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 54 / 169v链路是理想的传输通道，所传输的任何数据既不会链路是理想的传输通道，所传输的任何数据既不会出错也不会丢失

48、出错也不会丢失v考虑实际情况，接收方不可能具有足够高的考虑实际情况，接收方不可能具有足够高的cpu处处理能力来及时处理所有的接收帧，也不可能具有永理能力来及时处理所有的接收帧，也不可能具有永不溢出的缓冲区不溢出的缓冲区即：毋需差错控制，但必须进行流量控制即：毋需差错控制，但必须进行流量控制这里的单工，其实是半双工，所谓流量控制是发送方必须收这里的单工，其实是半双工，所谓流量控制是发送方必须收到前一帧的确认后才允许发送下一帧，接收方发出确认，意到前一帧的确认后才允许发送下一帧，接收方发出确认，意味着前一帧已接收并交网络层，准备接收下一帧味着前一帧已接收并交网络层，准备接收下一帧tnbm p207

49、 fig. 3-11 一个单工的停一个单工的停 等协议等协议协议协议1中第一个假设保留，第二个假设撤消，假定：中第一个假设保留，第二个假设撤消，假定：computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 55 / 169void sender2(void) frame s; packet buffer; event_type event; while (true) from_network_layer(&buffer); =buffer; to_physical_layer(&s); wait_for_event(&

50、;event); computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 56 / 169void receiver2(void) frame r,s; event_type event; while (true) wait_for_event(&event); from_physical_layer(&r); to_network_layer(&); to_physical_layer(&s); computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 57 / 16

51、9v协议协议2是一个半双工协议，即发送方和接收方使用同是一个半双工协议，即发送方和接收方使用同一信道，但发送方发送数据帧的过程和接收方发送确一信道，但发送方发送数据帧的过程和接收方发送确认帧的过程是严格交替的认帧的过程是严格交替的v协议协议2中，发送方发送的数据帧和接收方发送的确认中，发送方发送的数据帧和接收方发送的确认帧采用相同的帧格式，发送方发送的数据帧中仅包含帧采用相同的帧格式，发送方发送的数据帧中仅包含数据，接收方发送的确认帧数据为空，仅为一个信号数据，接收方发送的确认帧数据为空，仅为一个信号v由于协议由于协议2定义的是一个理想的传输通道，所以不考定义的是一个理想的传输通道，所以不考虑

52、传输差错问题虑传输差错问题computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 58 / 169v无限制的单工协议无限制的单工协议（协议（协议1）tnbm p205 fig. 3-10 一种无限制的单工协议一种无限制的单工协议v单工的停单工的停 等协议等协议（协议（协议2）tnbm p207 fig. 3-11 一个单工的停一个单工的停 等协议等协议v噪声信道的单工协议噪声信道的单工协议（协议（协议3）tnbm p210 fig. 3-12 一个肯定性确认和超时重发协议一个肯定性确认和超时重发协议computer networks v5 cs.sjt

53、u 2021-11-10第3章 数据链路层 59 / 169v噪声信道的差错控制噪声信道的差错控制v采用定时器实现差错控制采用定时器实现差错控制v简单的重发机制存在的问题简单的重发机制存在的问题v较为实用的噪声信道单工协议较为实用的噪声信道单工协议computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 60 / 169v帧的数据出错：帧的数据出错：帧数据中若干位出错，帧数据中若干位出错， 通常通常crc都能检测到都能检测到 v帧的丢失：帧的丢失：一旦帧头出错，则该帧丢失一旦帧头出错，则该帧丢失v帧的重复：帧的重复：如发送方有重发机制，当接收方发出的如发

54、送方有重发机制，当接收方发出的ack丢失时，丢失时，接收方将收到发送方重发的重复帧接收方将收到发送方重发的重复帧 在噪声信道中应考虑传输有差错的情况，所谓差错：在噪声信道中应考虑传输有差错的情况，所谓差错：computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 61 / 169v噪声信道的差错控制噪声信道的差错控制v采用定时器实现差错控制采用定时器实现差错控制v简单的重发机制存在的问题简单的重发机制存在的问题v较为实用的噪声信道单工协议较为实用的噪声信道单工协议computer networks v5 cs.sjtu 2021-11-10第3章 数据链

55、路层 62 / 169v如在协议如在协议2的基础上增加一个重发定时器，当发送方发的基础上增加一个重发定时器，当发送方发送完一帧后启动一个重发定时器并等待确认送完一帧后启动一个重发定时器并等待确认v无论是由于接收方收到一个错帧而不发无论是由于接收方收到一个错帧而不发ack（无否定（无否定性确认机制），还是由于帧标志错而导致帧的丢失，性确认机制），还是由于帧标志错而导致帧的丢失，接收方不可能发送接收方不可能发送ack，或者接收方所发送的，或者接收方所发送的ack丢丢失，发送方的重发定时器都将超时，重发定时器一旦失，发送方的重发定时器都将超时，重发定时器一旦超时则立即重发，以实现差错控制超时则立即重

56、发，以实现差错控制computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 63 / 169v噪声信道的差错控制噪声信道的差错控制v采用定时器实现差错控制采用定时器实现差错控制v简单的重发机制存在的问题简单的重发机制存在的问题v较为实用的噪声信道单工协议较为实用的噪声信道单工协议computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 64 / 169v效率较低效率较低如接收方收到的帧出错或者整个数据帧丢失，则不发如接收方收到的帧出错或者整个数据帧丢失，则不发ack（无（无否定性确认机制），发送方将在重发定时器超时

57、后重发，直至否定性确认机制），发送方将在重发定时器超时后重发，直至正确，然而重发定时器的设定时间可能是正常正确，然而重发定时器的设定时间可能是正常ack返回时间的返回时间的2倍、倍、3倍和更多，所以效率极低倍和更多，所以效率极低v接收方会收到重复帧接收方会收到重复帧 如接收方收到了正确的数据帧并发送了如接收方收到了正确的数据帧并发送了ack，但此，但此ack丢失，丢失，发送方在重发定时器超时后重发此帧，这样，接收方的数据链发送方在重发定时器超时后重发此帧，这样，接收方的数据链路层路层会收到两个完全相同的帧，其网络层将收到两个完全相同会收到两个完全相同的帧，其网络层将收到两个完全相同的分组，这是

58、不允许的的分组，这是不允许的 computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 65 / 169v噪声信道的差错控制噪声信道的差错控制v采用定时器实现差错控制采用定时器实现差错控制v简单的重发机制存在的问题简单的重发机制存在的问题v较为实用的噪声信道单工协议较为实用的噪声信道单工协议computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 66 / 169v这里的噪声信道单工协议，其实是噪声信道半双工协议这里的噪声信道单工协议，其实是噪声信道半双工协议v协议协议3的帧格式中定义一个帧序号字段的帧格式中定义一

59、个帧序号字段v发送方要记录下一个准备发送的顺序号发送方要记录下一个准备发送的顺序号v接收方要记录下一个期待接收的顺序号接收方要记录下一个期待接收的顺序号v由于是半双工噪声信道，发送和接收过程将严格交替由于是半双工噪声信道，发送和接收过程将严格交替 v协议协议3只定义了肯定性确认帧只定义了肯定性确认帧ack，而没有定义否定性，而没有定义否定性确认确认nakv接收方收到一个正确（接收方收到一个正确（crc正确）的帧，即便不是所正确）的帧，即便不是所期待的帧（即重复帧），都必须发送一个确认帧期待的帧（即重复帧），都必须发送一个确认帧ack也称为也称为arq协议：协议：automatic repeat

60、 request computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 67 / 169v帧类型：有数据帧帧类型：有数据帧data 和确认帧和确认帧ack（肯（肯定性确认）两种类型定性确认）两种类型v帧序号：仅一个帧序号：仅一个bit，在发送方的数据帧中是，在发送方的数据帧中是该帧的序号该帧的序号0/1，在接收方的确认帧中是接，在接收方的确认帧中是接收方期待接收的下一帧的序号收方期待接收的下一帧的序号1/0computer networks v5 cs.sjtu 2021-11-10第3章 数据链路层 68 / 169void sender3(void) next_frame_to_send=0; from_network_layer(&buffer); while (true) =bu