第3章数据链路层课件

Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 1/169第第3章章 数据链路层数据链路层v定定义和功能和功能v数据数据帧的的组成成v可靠性可靠性传输v数据数据链路路层示例示例Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 2/169v为网网络层提供一个提供一个较好的服好的服务接口接口v为网网络层提供可靠的提供可靠的传输服服务数据链路层的定义数据链路层的定义数据链路层的上层是网络层，数据链路层数据链路层的上层是网络层，数据链路层将借助于物理层为网络层提供服务将借助于物理层为网络层提供服务数据链路层的协议数据单元（数据链路层的协议数据单元（PDU）是帧）是帧Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 3/169数据链路层的功能数据链路层的功能v数据数据链路路层的任的任务是把网是把网络层的数字数据的数字数据组合成合成帧，并，并加上一定的校加上一定的校验码后交物理后交物理层v物理物理层用不同的信号表示二用不同的信号表示二进制数据位，从而把制数据位，从而把帧用一用一段段连续的信号串表示并的信号串表示并传送到目的主机送到目的主机v目的主机的物理目的主机的物理层将信号将信号还原成比特串交数据原成比特串交数据链路路层，井数据井数据链路路层确确认正确后送到网正确后送到网络层v数据数据链路路层为源和目的主机的网源和目的主机的网络层之之间提供一条可靠提供一条可靠的数据的数据链路路Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 4/169相连、物理链路和数据链路相连、物理链路和数据链路v所所谓相相连，可以理解，可以理解为物理介物理介质的的连接，但当接，但当采用多路复用技采用多路复用技术时也可以是信道的也可以是信道的连接，其接，其特征特征为：所：所传输的数据是按序的的数据是按序的v物理物理链路：一段无源的点到点的物理路：一段无源的点到点的物理连接，中接，中间没有任何交没有任何交换节点点v数据数据链路：包括一条物理路：包括一条物理连接和接和为实现数据数据传输而在两端配置的硬件及其相关的通信而在两端配置的硬件及其相关的通信协议Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 5/169数据链路层提供的服务数据链路层提供的服务v数据数据链路路层的服的服务是通是通过有无有无连接、接、有无确有无确认来区分的来区分的无确无确认无无连接的服接的服务有确有确认无无连接的服接的服务有确有确认有有连接的服接的服务Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 6/169确认和连接确认和连接v确确认：接收方在收到数据：接收方在收到数据帧后，必后，必须给发送方送方发回一个确回一个确认v面向面向连接：接：发送方和接收方在送方和接收方在传输数据数据之前必之前必须建立一条数据建立一条数据链路，路，传输结束束后必后必须释放放该链路路Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 7/169数据链路层的服务数据链路层的服务v无确无确认无无连接的服接的服务v有确有确认无无连接的服接的服务v有确有确认有有连接的服接的服务Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 8/169无确认面向无连接的服务无确认面向无连接的服务 v无确无确认是指接收方在收到数据是指接收方在收到数据帧后，毋需后，毋需发回一个确回一个确认v无无连接的服接的服务是指在数据是指在数据传输前毋需建立数据前毋需建立数据链路路v物理物理线路的路的连接并非意味着提供了有接并非意味着提供了有连接的服接的服务v无确无确认并非不可靠，其可靠性可由上并非不可靠，其可靠性可由上层负责例如：局域网例如：局域网1.共享信道不需要、也不允许建立连接共享信道不需要、也不允许建立连接2.信道较为理想，数据传输的误码率很低信道较为理想，数据传输的误码率很低3.即使出错或丢失由上层负责恢复即使出错或丢失由上层负责恢复Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 9/169数据链路层的服务数据链路层的服务v无确无确认无无连接的服接的服务v有确有确认无无连接的服接的服务v有确有确认有有连接的服接的服务Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 10/169有确认面向无连接的服务有确认面向无连接的服务 v使用前不建立使用前不建立连接，即不建立数据接，即不建立数据链路，但每路，但每帧传输必必须得到确得到确认v这在信号在信号传播延播延时较大、大、线路状路状态不一定很可靠的情不一定很可靠的情况下是有效的况下是有效的例如：无例如：无线通信通信1.如建立连接，则信道使用率很低如建立连接，则信道使用率很低2.然而，由于数据传输的误码率相对较然而，由于数据传输的误码率相对较高，所以确认是必要的高，所以确认是必要的Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 11/169数据链路层的服务数据链路层的服务v无确无确认无无连接的服接的服务v有确有确认无无连接的服接的服务v有确有确认有有连接的服接的服务Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 12/169有确认的面向连接服务有确认的面向连接服务 v使用前先建立使用前先建立连接，即先建立数据接，即先建立数据链路，并且每路，并且每帧的的传输必必须得到确得到确认v有有连接的服接的服务必必须在使用前先建立在使用前先建立连接（即建立接（即建立数据数据链路），然后使用，最后路），然后使用，最后释放放连接接例如：例如：电话1.电话是一种实时的应用，如不是面向连电话是一种实时的应用，如不是面向连接，则实时性难以得到保证接，则实时性难以得到保证2.电话是一对一的、双向的数据传输电话是一对一的、双向的数据传输Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 13/169数据的可靠传输数据的可靠传输v将将传输的信息的信息组合成合成帧v校校验和重和重发v流量控制流量控制保证直接相连的两台主机的可靠性传输保证直接相连的两台主机的可靠性传输Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 14/169第第3章章 数据链路层数据链路层v定定义和功能和功能v数据数据帧的的组成成v可靠性可靠性传输v数据数据链路路层示例示例Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 15/169数据帧的组成数据帧的组成v字符字符计数法数法v带字符填充的首尾界符法字符填充的首尾界符法v带位填充的首尾位填充的首尾标志法志法 v物理物理层编码违例法例法帧的组成必须保证能识别一个完整的帧，并保证一帧的组成必须保证能识别一个完整的帧，并保证一旦出现传输差错而导致前一个帧丢失时，也必须能旦出现传输差错而导致前一个帧丢失时，也必须能识别后一个帧，即具有识别后一个帧，即具有帧帧再同步能力再同步能力Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 16/169字符计数法字符计数法v假假设帧的的长度用一个字度用一个字节表示，并作表示，并作为帧的的头部部一旦帧长度计数被误读，将无法再同步，所以不能采用一旦帧长度计数被误读，将无法再同步，所以不能采用 第第1帧帧第第2帧帧帧长度计数错帧长度计数错帧长度计数帧长度计数第第1帧帧第第4帧帧第第3帧帧第第2帧帧5123456789801234568789012351234767898012345687890123TnbmP188Fig.3-4字符计数成帧法字符计数成帧法Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 17/169数据帧的组成数据帧的组成v字符字符计数法数法v带字符填充的首尾界符法字符填充的首尾界符法v带位填充的首尾位填充的首尾标志法志法 v物理物理层编码违例法例法帧的组成必须保证能识别一个完整的帧，帧的组成必须保证能识别一个完整的帧，并保证一并保证一旦出现传输差错而导致前一个帧丢失时旦出现传输差错而导致前一个帧丢失时，也必须能，也必须能识别下一个帧，识别下一个帧，即具有帧再同步能力即具有帧再同步能力Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 18/169带字符填充的首尾界符法带字符填充的首尾界符法 v用特殊的字符作用特殊的字符作为帧头和和帧尾界符尾界符FLAG HeaderPayloadfieldTrailer FLAG这是一种面向字符的帧格式，所传输的数据都是字符这是一种面向字符的帧格式，所传输的数据都是字符（ASCII或或EBCDIC字符），但帧中不允许出现帧界符字符），但帧中不允许出现帧界符标志，在面向字符的串型通信中常使用这种格式标志，在面向字符的串型通信中常使用这种格式(PPP)接收方一旦丢失了一个接收方一旦丢失了一个FLAG，只要继续搜索下一个，只要继续搜索下一个FLAG，就可重新确定帧边界，即具有再同步能力，就可重新确定帧边界，即具有再同步能力TnbmP189Fig.3-5(a)由由Flag标志的一个帧标志的一个帧Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 19/169面向字符的帧格式面向字符的帧格式v面向字符的面向字符的帧格式不适宜格式不适宜传输数据中包含二数据中包含二进制数的制数的帧，因因为在包含二在包含二进制数的制数的帧中很可能出中很可能出现与与FLAG相同的相同的bit序列（通常序列（通常FLAG用用ASCII字符字符7EH定定义）v一种方法是在二一种方法是在二进制数中偶然出制数中偶然出现的的FLAG前再插入一个前再插入一个ESC（ASCII字符字符1BH），），这种方法称种方法称为字符填充法字符填充法41337E5C4B0C41331B5C4B0C41331B7E5C4B0C41331B1B5C4B0C41331B7E5C4B0C41331B1B5C4B0C41331B1B1B7E5C4B0C41331B1B1B1B5C4B0CComputer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 20/169数据帧的组成数据帧的组成v字符字符计数法数法v带字符填充的首尾界符法字符填充的首尾界符法v带位填充的首尾位填充的首尾标志法志法 v物理物理层编码违例法例法帧的组成必须保证能识别一个完整的帧，并保证一帧的组成必须保证能识别一个完整的帧，并保证一旦出现传输差错而导致前一个帧丢失时，也必须能旦出现传输差错而导致前一个帧丢失时，也必须能识别下一个帧，即具有帧再同步能力识别下一个帧，即具有帧再同步能力Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 21/169带位填充的首尾标志法带位填充的首尾标志法 v在面向二在面向二进制位的同步串行通信中常使用制位的同步串行通信中常使用带位位填充的首尾填充的首尾标志志格式，如格式，如HDLC这是一种面向二进制位的帧格式，把所有需传输的数据（不论是字符这是一种面向二进制位的帧格式，把所有需传输的数据（不论是字符或表示一个浮点数的二进制位串，还是一个或表示一个浮点数的二进制位串，还是一个MP3的文件）一字排开，的文件）一字排开，并以特殊的位模式并以特殊的位模式01111110作为帧标志，即一个帧的开始（同时标志作为帧标志，即一个帧的开始（同时标志前一个帧的结束）前一个帧的结束）如果由于干扰，一个帧标志没有被正确接收，则继续扫描接收串，一如果由于干扰，一个帧标志没有被正确接收，则继续扫描接收串，一旦扫描到旦扫描到01111110，即新的一帧从此开始，即具有再同步能力，即新的一帧从此开始，即具有再同步能力即使字符也并非都是即使字符也并非都是8位的，东方文字是位的，东方文字是16位，位，UNICODE是是16位位Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 22/169面向面向bit的帧格式的帧格式v当帧中出现一个与帧标志相同的位串当帧中出现一个与帧标志相同的位串01111110，则在，则在连续连续5个个1后自动插入一个后自动插入一个0，即变成，即变成01111101，接收，接收方将自动删除第方将自动删除第5个个1后的后的0v这称为位插入法，也称为透明传输这称为位插入法，也称为透明传输011011111111111111110010011011111011111011111010010011011111111111111110010TnbmP190Fig.3-6(a)(b)(c)位插入法示例位插入法示例Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 23/169数据帧的组成数据帧的组成v字符字符计数法数法v带字符填充的首尾界符法字符填充的首尾界符法v带位填充的首尾位填充的首尾标志法志法 v物理物理层编码违例法例法帧的组成必须保证能识别一个完整的帧，并保证一帧的组成必须保证能识别一个完整的帧，并保证一旦出现传输差错而导致前一个帧丢失时，也必须能旦出现传输差错而导致前一个帧丢失时，也必须能识别下一个帧，即具有帧再同步能力识别下一个帧，即具有帧再同步能力Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 24/169物理层编码违例法物理层编码违例法 v在曼切斯特在曼切斯特编码中，中，连续高高电平或平或连续低低电平可用作平可用作帧界符界符采用冗余编码技术，如曼切斯特编码，即对连续两个信号进行采用冗余编码技术，如曼切斯特编码，即对连续两个信号进行采样，可得到一个二进制位采样，可得到一个二进制位数据数据0：低：低-高电平对高电平对数据数据1：高：高-低电平对低电平对高高-高电平对和低高电平对和低-低电平对没有使用，如在二进制编低电平对没有使用，如在二进制编码中出现则称为编码违例，但这两种违例编码正好可码中出现则称为编码违例，但这两种违例编码正好可用作帧界符，在令牌环网中使用编码违例格式用作帧界符，在令牌环网中使用编码违例格式Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 25/169第第3章章 数据链路层数据链路层v定定义和功能和功能v数据数据帧的的组成成v可靠性可靠性传输v数据数据链路路层示例示例Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 26/169可靠性传输可靠性传输v差差错控制：校控制：校验、重、重发和序号和序号避免帧错误的保证：帧的校验避免帧错误的保证：帧的校验避免帧丢失的保证：超时和重发避免帧丢失的保证：超时和重发避免帧重复的保证：帧有序号避免帧重复的保证：帧有序号v流量控制：窗口流量控制：窗口协议发送方和接收方之间传输速率的协调发送方和接收方之间传输速率的协调v协议描述和描述和验证Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 27/169差错控制差错控制 v确确认v数据数据帧丢失失v重复重复帧如何保证数据帧的正常传输，将通过如何保证数据帧的正常传输，将通过三种手段处理三种可能出现的情况三种手段处理三种可能出现的情况：Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 28/169确认确认 接收方在收到了正确的接收方在收到了正确的帧后向后向发送方送方发肯定性确肯定性确认；如收到的；如收到的帧有有问题，则发否定性确否定性确认，此，此时发送方将重送方将重发此此帧确确认的前提是必的前提是必须经过差差错检测Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 29/169差错检测和校正差错检测和校正 v差差错的的产生主要是在生主要是在传输时，数据中的一位或，数据中的一位或几位因噪声干几位因噪声干扰而出而出错v噪声分两种：噪声分两种：信道所固有的、持续存在的热噪声信道所固有的、持续存在的热噪声 外界突发原因而造成的随机的冲击噪声外界突发原因而造成的随机的冲击噪声 v通常接收方通常接收方应能能检错，甚至，甚至纠错v纠错码是除是除m个数据位外增加个数据位外增加r个冗余位作个冗余位作为纠错位，位，传输的的总长度度为n=m+rComputer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 30/169纠错码和检错码纠错码和检错码v纠错码：海明（海明（Hamming）码v检错码：校校验和（和（CheckSum）块校校验码（BlockCheckCode）循循环冗余冗余检错码CRC（CyclicRedundancyCheck）Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 31/169校验和校验和 v算法算法简单、实现容易，但容易，但检错强度度较弱弱以以16位为例：位为例：4865H+6C6CH+6F20H+776FH+726CH+642EH+进位进位=71FCHHelloworld.48656C6C6F20776F726C642E71FC将发送的数据看成是二进制整数序列，并划分成一段段规将发送的数据看成是二进制整数序列，并划分成一段段规定的长度（如定的长度（如8位、位、16位、位、32位等），计算它们的和，如位等），计算它们的和，如计算和时有进位，则将进位加到最后的校验和中，并将校计算和时有进位，则将进位加到最后的校验和中，并将校验和与数据一起发送；在接收端，重新计算校验和，并与验和与数据一起发送；在接收端，重新计算校验和，并与接收到的原校验和比较，如要传输接收到的原校验和比较，如要传输“Helloworld.”Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 32/169纠错码和检错码纠错码和检错码v纠错码：海明（海明（Hamming）码v检错码：校校验和（和（CheckSum）块校校验码（BlockCheckCode）循循环冗余冗余检错码CRC（CyclicRedundancyCheck）Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 33/169块校验码块校验码v块校校验码BCC（BlockCheckCode）简单常用，但常用，但检错的的强度度较弱，如在同一列上有偶数位弱，如在同一列上有偶数位错，则不能不能检测如传输的数据都是如传输的数据都是ASCII字符（即面向字符，这在应用中很多），字符（即面向字符，这在应用中很多），每个字符进行奇偶校验，然后把所有的字符（连同奇偶位）进行异每个字符进行奇偶校验，然后把所有的字符（连同奇偶位）进行异或运算，运算结果即为其块校验码，通常发送端在发送完数据区的或运算，运算结果即为其块校验码，通常发送端在发送完数据区的结束标志后发送结束标志后发送BCC，接收端一边接收数据一边计算，接收端一边接收数据一边计算BCC，最后与，最后与接收到的接收到的BCC比较，以确认所接收到的数据正确与否比较，以确认所接收到的数据正确与否如如“Helloworld.”，采用偶校验，校验后的字符序列为：，采用偶校验，校验后的字符序列为：48H 65H 6CH 6CH 6FH A0H 77H 6FH 72H 6CH E4H 2EH=2EHHelloworld.48656C6C6FA0776F726CE42E2EComputer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 34/169纠错码和检错码纠错码和检错码v纠错码：海明（海明（Hamming）码v检错码：校校验和（和（CheckSum）块校校验码（BlockCheckCode）循循环冗余冗余检错码CRC（CyclicRedundancyCheck）Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 35/169循环冗余检错码循环冗余检错码CRCv任何一个任何一个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二二进制运算中，减法和加法都做异或运算：制运算中，减法和加法都做异或运算：0+1=1,1+1=0v因因为(xrM(x)-R(x)一定能被一定能被G(x)整除，即余数整除，即余数为0，则接收方接收方只要只要计算算CRC，并所得余数，并所得余数为0即即为正确正确Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 36/169CRC码计算举例码计算举例如一如一帧为1101011011即：即：M(x)=x9+x8+x6+x4+x3+x+1G(x)=x4+x+1T(x)=x4M(x)=x4(x9+x8+x6+x4+x3+x+1)=x13+x12+x10+x8+x7+x5+x4Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 37/169CRC码计算举例码计算举例（续（续（续（续1 1）v帧：1101011011v除数：除数：10011v实际传输帧：1 1 0 0 0 0 1 0 1 01 0 0 1 1 1 1 0 1 0 1 1 0 1 1 0 0 0 01 0 0 1 11 0 0 1 11 0 0 1 10 0 0 0 10 0 0 0 00 0 0 1 00 0 0 0 00 0 1 0 10 0 0 0 00 1 0 1 10 0 0 0 01 0 1 1 01 0 0 1 10 1 0 1 00 0 0 0 01 0 1 0 01 0 0 1 10 1 1 1 00 0 0 0 01 1 1 0余数余数1101011011 1110帧数据帧数据余数余数TnbmP198Fig.3-8CRC码计算举例码计算举例Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 38/169CRC码计算举例码计算举例（续（续（续（续2 2）11010110110000/10011=11000010101110即即11010110110000+1110能被能被10011整除整除（注：模（注：模2运算的加、减和异或，其运算结果相同）运算的加、减和异或，其运算结果相同）发送方发送的是发送方发送的是T(x)+R(x)能被能被G(x)整除整除，如接收，如接收方收到的是方收到的是T(x)+R(x)+E(x)，除非，除非E(x)是是G(x)的整倍的整倍数，否则不能被整除，即都能被检测到已出错数，否则不能被整除，即都能被检测到已出错Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 39/169三个生成多项式国际标准三个生成多项式国际标准 vCRC-12：x12+x11+x3+x2+x1+1用于字符用于字符长度度为6位位vCRC-16：x16+x15+x2+1用于字符用于字符长度度为8位位vCRC-CCITT：x16+x12+x5+1用于字符用于字符长度度为8位位vIEEE802：x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x1+1CCITT：ConsultativeCommitteeonInternationalTelegraphyandTelephone国际电报和电话咨询委员会，即现在的国际电报和电话咨询委员会，即现在的ITU-TITU-T：InternationalTelecommunicationsUnionTelecommunicationsStandardizationSector国际电信联盟国际电信联盟电信标准分部电信标准分部Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 40/169差错控制差错控制 v确确认v数据数据帧丢失失v重复重复帧如何保证数据帧的正常传输：通过三如何保证数据帧的正常传输：通过三种手段处理三种可能出现的情况种手段处理三种可能出现的情况：Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 41/169数据帧丢失数据帧丢失 v通通过发送方的重送方的重发定定时器（超器（超时）解决）解决v超超时（TimeOut）：在）：在传输过程中，如果所程中，如果所发送的送的帧丢失，接收方根本没有收到，不可能失，接收方根本没有收到，不可能发送确送确认帧（包括否定性确（包括否定性确认），当然），当然发送方也送方也不可能等待收到如何信息，所以不可能等待收到如何信息，所以发送方每送方每发送送一一帧，就启，就启动一个重一个重发定定时器，在所器，在所设定的定的时间内，一般都内，一般都应该收到确收到确认，如收不到确，如收不到确认，则在重在重发定定时器溢出后，再重器溢出后，再重发此此帧Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 42/169差错控制差错控制 v确确认v数据数据帧丢失失v重复重复帧如何保证数据帧的正常传输：通过三如何保证数据帧的正常传输：通过三种手段处理三种可能出现的情况种手段处理三种可能出现的情况：Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 43/169重复帧重复帧 v重重发机制也包括当接收方机制也包括当接收方发送的确送的确认帧丢失而失而导致致发送方的重送方的重发定定时器超器超时而重而重发v由于接收方确由于接收方确认帧的的丢失，失，导致致发送方多次送方多次发送同一送同一帧，接收方也将多次收到同一，接收方也将多次收到同一帧，为能能识别是否是否为相同的相同的帧，应该在在帧格式中增加一格式中增加一个个帧的的编号（序号）号（序号）Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 44/169帧的格式帧的格式基于上述讨论，一个数据链路层的帧至少应该包括下基于上述讨论，一个数据链路层的帧至少应该包括下列内容：列内容：信息信息校校验信息验信息infoCRC确认号确认号Ack_no帧序号帧序号Seq_no帧类型帧类型type帧头帧头Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 45/169可靠性传输可靠性传输v差差错控制：校控制：校验、重、重发和序号和序号避免帧错误的保证：帧的校验避免帧错误的保证：帧的校验避免帧丢失的保证：超时和重发避免帧丢失的保证：超时和重发避免帧重复的保证：帧有序号避免帧重复的保证：帧有序号v流量控制：窗口流量控制：窗口协议发送方和接收方之间的协调发送方和接收方之间的协调v协议描述和描述和验证Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 46/169流量控制流量控制 v发送速率和接收速率的匹配即流量控制送速率和接收速率的匹配即流量控制如接收方的处理能力低于发送方，即使传输中没有如接收方的处理能力低于发送方，即使传输中没有出错，也可能被出错，也可能被“淹没淹没”，所以通常在接收方的缓，所以通常在接收方的缓冲区到达一定量时，应及时通知发送方，暂停发送，冲区到达一定量时，应及时通知发送方，暂停发送，等候通知，这就是流量控制机制等候通知，这就是流量控制机制基本数据基本数据链路路协议滑滑动窗口窗口协议Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 47/169A、B两台主机要求可靠的、面向两台主机要求可靠的、面向连接的通接的通信，在接收方的数据信，在接收方的数据链路路层，目前正运行，目前正运行的是的是wait_for_event(&event)，即等待某，即等待某个事件个事件发生生基本数据链路协议基本数据链路协议可以这样理解：在一台主机中，物理层、数据可以这样理解：在一台主机中，物理层、数据链路层、网络层等，都有各自的进程在运行，链路层、网络层等，都有各自的进程在运行，并且假设：并且假设：Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 48/169wait_for_event(&event)的参数的参数v如如event=checksum_err，意即所接收，意即所接收帧的校的校验和和错，应考考虑不不发送确送确认帧ACK，或，或发送否定性确送否定性确认帧NAKv如如event=frame_arrival，即，即帧已到达并校已到达并校验正确，正确，应调用用from_physical_layer，从物理，从物理层取得取得帧，并，并检查帧头的控制信息，如一切正常，的控制信息，如一切正常，则仅把其中的分把其中的分组交网交网络层v一系列一系列过程和数据程和数据结构的定构的定义：TnbmP202Fig.3-9如发生了某个事件，此过程将返回参数如发生了某个事件，此过程将返回参数event，event有两个取值：有两个取值：checksum_err（CRC错）错）frame_arrival（正确收到）（正确收到）Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 49/169三个基本数据链路协议三个基本数据链路协议（协议（协议（协议（协议1-31-3）v无限制的无限制的单工工协议（协议1）TnbmP205Fig.3-10一种无限制的一种无限制的单工工协议v单工的停工的停 等等协议（协议2）TnbmP207Fig.3-11一个一个单工的停工的停等等协议v噪声信道的噪声信道的单工工协议（协议3）TnbmP210Fig.3-12一个肯定性确一个肯定性确认和超和超时重重发协议Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 50/169无限制的单工协议无限制的单工协议v链路是理想的路是理想的传输通道，所通道，所传输的任何数据的任何数据既不会出既不会出错也不会也不会丢失失即：不需校验，也不可能出现重发，毋需差错控制即：不需校验，也不可能出现重发，毋需差错控制v不管不管发送方以怎送方以怎样的速率的速率发送数据，接收方送数据，接收方都能及都能及时接收并接收并处理理即接收端处理器的处理速度无限高，处理时间可忽略即接收端处理器的处理速度无限高，处理时间可忽略不计，缓冲区空间无限大，毋需流量控制不计，缓冲区空间无限大，毋需流量控制TnbmP205Fig.3-10一种无限制的单工协议一种无限制的单工协议一种理想的环境，理想的协议，假定：一种理想的环境，理想的协议，假定：Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 51/169协议协议1：SENDERvoidsender1(void)frames;packetbuffer;while(true)from_network_layer(&buffer);s.info=buffer;to_physical_layer(&s);Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 52/169协议协议1：RECEIVERvoidreceiver1(void)framer;event_typeevent;while(true)wait_for_event(&event);from_physical_layer(&r);to_network_layer(&r.info);Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 53/169三个基本数据链路协议三个基本数据链路协议（协议（协议1-3）v无限制的无限制的单工工协议（协议1）TnbmP205Fig.3-10一种无限制的一种无限制的单工工协议v单工的停工的停 等等协议（协议2）TnbmP207Fig.3-11一个一个单工的停工的停等等协议v噪声信道的噪声信道的单工工协议（协议3）TnbmP210Fig.3-12一个肯定性确一个肯定性确认和超和超时重重发协议Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 54/169单工的停单工的停 等协议等协议v链路是理想的路是理想的传输通道，所通道，所传输的任何数据既不会的任何数据既不会出出错也不会也不会丢失失v考考虑实际情况，接收方不可能具有足情况，接收方不可能具有足够高的高的CPU处理能力来及理能力来及时处理所有的接收理所有的接收帧，也不可能具有永，也不可能具有永不溢出的不溢出的缓冲区冲区即：毋需差错控制，但必须进行流量控制即：毋需差错控制，但必须进行流量控制这里的单工，其实是半双工，所谓流量控制是发送方必须收这里的单工，其实是半双工，所谓流量控制是发送方必须收到前一帧的确认后才允许发送下一帧，接收方发出确认，意到前一帧的确认后才允许发送下一帧，接收方发出确认，意味着前一帧已接收并交网络层，准备接收下一帧味着前一帧已接收并交网络层，准备接收下一帧TnbmP207Fig.3-11一个单工的停一个单工的停等协议等协议 协议协议1中第一个假设保留，第二个假设撤消，假定：中第一个假设保留，第二个假设撤消，假定：Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 55/169协议协议2：SENDERvoidsender2(void)frames;packetbuffer;event_typeevent;while(true)from_network_layer(&buffer);s.info=buffer;to_physical_layer(&s);wait_for_event(&event);Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 56/169协议协议2：RECEIVERvoidreceiver2(void)framer,s;event_typeevent;while(true)wait_for_event(&event);from_physical_layer(&r);to_network_layer(&r.info);to_physical_layer(&s);Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 57/169协议协议2说明说明v协议2是一个半双工是一个半双工协议，即，即发送方和接收方使用同送方和接收方使用同一信道，但一信道，但发送方送方发送数据送数据帧的的过程和接收方程和接收方发送确送确认帧的的过程是程是严格交替的格交替的v协议2中，中，发送方送方发送的数据送的数据帧和接收方和接收方发送的确送的确认帧采用相同的采用相同的帧格式，格式，发送方送方发送的数据送的数据帧中中仅包含包含数据，接收方数据，接收方发送的确送的确认帧数据数据为空，空，仅为一个信号一个信号v由于由于协议2定定义的是一个理想的的是一个理想的传输通道，所以不考通道，所以不考虑传输差差错问题Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 58/169三个基本数据链路协议三个基本数据链路协议（协议（协议1-3）v无限制的无限制的单工工协议（协议1）TnbmP205Fig.3-10一种无限制的一种无限制的单工工协议v单工的停工的停 等等协议（协议2）TnbmP207Fig.3-11一个一个单工的停工的停等等协议v噪声信道的噪声信道的单工工协议（协议3）TnbmP210Fig.3-12一个肯定性确一个肯定性确认和超和超时重重发协议Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 59/169噪声信道的单工协议噪声信道的单工协议v噪声信道的差噪声信道的差错控制控制v采用定采用定时器器实现差差错控制控制v简单的重的重发机制存在的机制存在的问题v较为实用的噪声信道用的噪声信道单工工协议Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 60/169噪声信道的差错控制噪声信道的差错控制v帧的数据出的数据出错：帧数据中若干位出错，帧数据中若干位出错，通常通常CRC都能检测到都能检测到v帧的的丢失：失：一旦帧头出错，则该帧丢失一旦帧头出错，则该帧丢失v帧的重复：的重复：如发送方有重发机制，当接收方发出的如发送方有重发机制，当接收方发出的ACK丢失时，丢失时，接收方将收到发送方重发的重复帧接收方将收到发送方重发的重复帧在噪声信道中应考虑传输有差错的情况，所谓差错：在噪声信道中应考虑传输有差错的情况，所谓差错：Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 61/169噪声信道的单工协议噪声信道的单工协议v噪声信道的差噪声信道的差错控制控制v采用定采用定时器器实现差差错控制控制v简单的重的重发机制存在的机制存在的问题v较为实用的噪声信道用的噪声信道单工工协议Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 62/169采用定时器实现差错控制采用定时器实现差错控制v如在如在协议2的基的基础上增加一个重上增加一个重发定定时器，当器，当发送方送方发送完一送完一帧后启后启动一个重一个重发定定时器并等待确器并等待确认v无无论是由于接收方收到一个是由于接收方收到一个错帧而不而不发ACK（无否定（无否定性确性确认机制），机制），还是由于是由于帧标志志错而而导致致帧的的丢失，失，接收方不可能接收方不可能发送送ACK，或者接收方所，或者接收方所发送的送的ACK丢失，失，发送方的重送方的重发定定时器都将超器都将超时，重，重发定定时器一旦器一旦超超时则立即重立即重发，以，以实现差差错控制控制Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 63/169噪声信道的单工协议噪声信道的单工协议v噪声信道的差噪声信道的差错控制控制v采用定采用定时器器实现差差错控制控制v简单的重的重发机制存在的机制存在的问题v较为实用的噪声信道用的噪声信道单工工协议Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 64/169简单的重发机制存在的问题简单的重发机制存在的问题v效率效率较低低如接收方收到的帧出错或者整个数据帧丢失，则不发如接收方收到的帧出错或者整个数据帧丢失，则不发ACK（无（无否定性确认机制），发送方将在重发定时器超时后重发，直至否定性确认机制），发送方将在重发定时器超时后重发，直至正确，然而重发定时器的设定时间可能是正常正确，然而重发定时器的设定时间可能是正常ACK返回时间的返回时间的2倍、倍、3倍和更多，所以效率极低倍和更多，所以效率极低v接收方会收到重复接收方会收到重复帧如接收方收到了正确的数据帧并发送了如接收方收到了正确的数据帧并发送了ACK，但此，但此ACK丢失，丢失，发送方在重发定时器超时后重发此帧，这样，接收方的数据链发送方在重发定时器超时后重发此帧，这样，接收方的数据链路层路层会收到两个完全相同的帧，其网络层将收到两个完全相同会收到两个完全相同的帧，其网络层将收到两个完全相同的分组，这是不允许的的分组，这是不允许的 Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 65/169噪声信道的单工协议噪声信道的单工协议v噪声信道的差噪声信道的差错控制控制v采用定采用定时器器实现差差错控制控制v简单的重的重发机制存在的机制存在的问题v较为实用的噪声信道用的噪声信道单工工协议Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 66/169较为实用的噪声信道单工协议较为实用的噪声信道单工协议v这里的噪声信道里的噪声信道单工工协议，其，其实是噪声信道半双工是噪声信道半双工协议v协议3的的帧格式中定格式中定义一个一个帧序号字段序号字段v发送方要送方要记录下一个准下一个准备发送的送的顺序号序号v接收方要接收方要记录下一个期待接收的下一个期待接收的顺序号序号v由于是半双工噪声信道，由于是半双工噪声信道，发送和接收送和接收过程将程将严格交替格交替v协议3只定只定义了肯定性确了肯定性确认帧ACK，而没有定，而没有定义否定性否定性确确认NAKv接收方收到一个正确（接收方收到一个正确（CRC正确）的正确）的帧，即便不是所期，即便不是所期待的待的帧（即重复（即重复帧），都必），都必须发送一个确送一个确认帧ACK也称为也称为ARQ协议：协议：AutomaticRepeatreQuestComputer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 67/169协议协议3中帧格式中帧格式v帧类型：有数据型：有数据帧DATA和确和确认帧ACK（肯（肯定性确定性确认）两种）两种类型型v帧序号：序号：仅一个一个bit，在，在发送方的数据送方的数据帧中是中是该帧的序号的序号0/1，在接收方的确，在接收方的确认帧中是接收中是接收方期待接收的下一方期待接收的下一帧的序号的序号1/0Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 68/169协议协议3:SENDERvoidsender3(void)next_frame_to_send=0;from_network_layer(&buffer);while(true)s.info=buffer;s.seq=next_frame_to_send;to_physical_layer(&s)；start_timer(s.seq)；wait_for_event(&event);if(event=frame_arrival)from_physical_layer(&s);if(s.ack=next_frame_to_send)stop_timer(s.ack);from_network_layer(&buffer);inc(next_frame_to_send);TnbmP210Fig.3-12一个肯定性确认和超时重发协议一个肯定性确认和超时重发协议 Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 69/169协议协议3:RECEIVERvoidreceiver3(void)frame_expected=0;while(true)wait_for_event(&event);if(event=frame_arrival)from_physical_layer(&r);if(r.seq=frame_expected)to_network_layer(&r.info);inc(frame_expected);s.ack=1-fram_expected;to_physical_layer(&s);Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 70/169流量控制流量控制 v发送速率和接收速率的匹配即流量控制送速率和接收速率的匹配即流量控制如接收方的处理能力低于发送方，即使传输中没有如接收方的处理能力低于发送方，即使传输中没有出错，也可能被出错，也可能被“淹没淹没”，所以通常在接收方的缓，所以通常在接收方的缓冲区到达一定量时，应及时通知发送方，暂停发送，冲区到达一定量时，应及时通知发送方，暂停发送，等候通知，这就是流量控制机制等候通知，这就是流量控制机制基本数据基本数据链路路协议滑滑动窗口窗口协议Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 71/169协议协议3尚存的问题尚存的问题v由于数据是由于数据是单向向传输的，数据的，数据传输和和应答不答不会同会同时传输，因此可使用半双工信道（通常，因此可使用半双工信道（通常半双工半双工仅需需单信道），但不能信道），但不能实现同同时双向双向传输。也可以用两根信道，但。也可以用两根信道，但传输应答的信答的信道效率道效率较低低v如如发送方的重送方的重发定定时器器设定的初始定的初始值较小，小，可能出可能出现系系统死死锁Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 72/169双向传输解决方案双向传输解决方案v但在但在实际情况下，一般需要的是双向情况下，一般需要的是双向传输v双向双向传输的解决方案：的解决方案：用四条信道：两条数据，两条用四条信道：两条数据，两条应答答但信道利用率很低但信道利用率很低用两条信道：一条用两条信道：一条A到到B，另一条，另一条B到到Al用不同的帧类型标志区分数据帧和确认帧用不同的帧类型标志区分数据帧和确认帧l采用捎带确认采用捎带确认（piggybacking）进一步提高信道效率）进一步提高信道效率Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 73/169捎带确认捎带确认v不不专门发确确认帧，当有数据要，当有数据要发送送给对方方时，顺便捎上确便捎上确认号号v一个捎一个捎带确确认不一定只确不一定只确认一个一个帧，而能，而能确确认许多多帧v例如，例如，A连续发送送0、1、2、3、4号号帧给B，而，而B一直没有数据要一直没有数据要发送。当收到送。当收到4以后，以后，B要要发送数据，此送数据，此时捎捎带确确认4，表示，表示0到到4号号帧都收到了都收到了Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 74/169双向传输总结双向传输总结v收、收、发使用两条信道使用两条信道发送方可连续发送多帧，接收方接收到一帧后发送方可连续发送多帧，接收方接收到一帧后就从另一个信道发回一个就从另一个信道发回一个ACK，为提高信道，为提高信道使用效率，接收方可使用捎带确认使用效率，接收方可使用捎带确认v帧是有序号的是有序号的即使过早超时而导致的重发也可根据帧的序号即使过早超时而导致的重发也可根据帧的序号来避免帧的重复来避免帧的重复Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 75/169滑动窗口协议滑动窗口协议v滑滑动窗口是控制流量的一种方法窗口是控制流量的一种方法v发送方送方维护一个一个发送窗口，包含允送窗口，包含允许发送的送的帧序号范序号范围v接收方接收方维护一个接收窗口，表示允一个接收窗口，表示允许接接受的受的帧序号范序号范围Computer Networks v5 cs.sjtu 2024/7/12第3章 数据链路层 76/169滑动窗口原理滑动窗口原理（设（设（设（设WWT T=1=1，WWR R=1=1）v发送方送方v接收方接收方TnbmP213Fig.3-13一个大小为一个大小为1、有、有3位序列号的滑动窗