第讲数据链路层

1/31第 5 讲 数据链路层(1)2/31知识回顾l 物理层的功能物理层的功能l 数据通信模型数据通信模型l 信道复用技术信道复用技术l 数字传输系统数字传输系统l 宽带接入技术宽带接入技术3/31本讲内容及教学目标l 理解数据链路层的功能。理解数据链路层的功能。l 掌握帧、链路等相关概念。掌握帧、链路等相关概念。l 掌握帧定界的方法。掌握帧定界的方法。l 理解数据链路层的三个基本问题。理解数据链路层的三个基本问题。l 掌握差错检测掌握差错检测CRC的计算方法。的计算方法。l 理解透明传输问题。理解透明传输问题。4/31数据链路层的服务l 数据链路层数据链路层最基本的服务是将源计算机网络层来的数据可最基本的服务是将源计算机网络层来的数据可靠的传输靠的传输到相邻节点的目标计算机的网络层。它为网络层到相邻节点的目标计算机的网络层。它为网络层提供以下服务：提供以下服务：l 无确认、无连接的服务无确认、无连接的服务 源端可以不需要建立连接就向目的端发送独立的数据帧，而目的端也不需要对收到的帧进行确认。以太网采用此服务。l 有确认、无连接的服务有确认、无连接的服务 源端可以不需要建立连接就向目的端发送独立的数据帧，但目的端需要对收到的帧进行确认。l 面向连接的服务面向连接的服务 源端与目的端在通信前要先建立连接，然后在此连接上互相传输数据帧，每一个帧都被编号，数据链路层保证传送的帧被对方收到，且只收到一次，双方通信完毕后拆除连接。电话网络采用。5/31数据链路层的主要功能l 为达到上述目的，数据链路层必须具备一系列相应的功能，主要为达到上述目的，数据链路层必须具备一系列相应的功能，主要有：如何将数据有：如何将数据组合成数据组合成数据块；如何控制帧在物理信道上的传输，块；如何控制帧在物理信道上的传输，包括如何包括如何处理传输差错处理传输差错，如何调节发送速率以使之与接收方相匹，如何调节发送速率以使之与接收方相匹配；在两个网路实体之间提供数据链路通路的配；在两个网路实体之间提供数据链路通路的建立、维持和释放建立、维持和释放管理管理。具体如下：具体如下：l 链路管理链路管理l 帧定界帧定界l 流量控制流量控制l 差错控制差错控制l 将数据和控制信息区分开将数据和控制信息区分开l 透明传输透明传输l 寻址寻址6/31 数据链路层的基本概念 l 在数据链路层中将这种在数据链路层中将这种数据块称为帧数据块称为帧，帧是数据链路层的，帧是数据链路层的传送单位。传送单位。l 链路链路(link)是一条无源的点到点的物理线路段，中间没有任是一条无源的点到点的物理线路段，中间没有任何其他的交换结点。何其他的交换结点。一条链路只是一条通路的一个组成部分。l 数据链路数据链路(data link)除了物理线路外，还必须有通信协议来除了物理线路外，还必须有通信协议来控制这些数据的传输。若把实现这些协议的硬件和软件加控制这些数据的传输。若把实现这些协议的硬件和软件加到链路上，就构成了到链路上，就构成了数据链路数据链路。现在最常用的方法是使用适配器（即网卡）来实现这些协议的硬件和软件。一般的适配器都包括了数据链路层和物理层这两层的功能。7/31Functions of the Data Link Layer(2)Relationship between packets and frames.8/31Services Provided to Network Layer(a)Virtual communication.(b)Actual communication.9/31数据链路层数据链路层使用的信道主要有以下两种类型：数据链路层使用的信道主要有以下两种类型：l 点对点信道点对点信道。这种信道使用一对一的点对点通信方。这种信道使用一对一的点对点通信方式。式。l 广播信道广播信道。这种信道使用一对多的广播通信方式，。这种信道使用一对多的广播通信方式，因此过程比较复杂。广播信道上连接的主机很多，因此过程比较复杂。广播信道上连接的主机很多，因此必须使用专用的共享信道协议来协调这些主机因此必须使用专用的共享信道协议来协调这些主机的数据发的数据发 10/31数据链路层的简单模型局域网广域网主机 H1主机 H2路由器 R1路由器 R2路由器 R3电话网局域网主机 H1 向 H2 发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2从层次上来看数据的流动11/31数据链路层的简单模型cont.局域网广域网主机 H1主机 H2路由器 R1路由器 R2路由器 R3电话网局域网主机 H1 向 H2 发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2仅从数据链路层观察帧的流动12/31数据链路层l 数据链路层像个数字管道。数据链路层像个数字管道。l 常常在两个对等的数据链路层之间画出一个数字管常常在两个对等的数据链路层之间画出一个数字管道，而在这条数字管道上传输的数据单位是帧。道，而在这条数字管道上传输的数据单位是帧。l 早期的数据通信协议曾叫作通信规程早期的数据通信协议曾叫作通信规程(procedure)。因此在数据链路层，规程和协议是同义语。因此在数据链路层，规程和协议是同义语。结点结点帧帧13/31成帧（帧同步）l 为了向网络层提供服务，数据链路层必须使用物理层提供为了向网络层提供服务，数据链路层必须使用物理层提供的服务。的服务。l 物理层物理层,是以比特流进行传输的是以比特流进行传输的，这种比特流并不保证在数，这种比特流并不保证在数据传输过程中没有错误，接收到的位数量可能少于、等于据传输过程中没有错误，接收到的位数量可能少于、等于或者多于发送的位数量。而且它们还可能有不同的值，这或者多于发送的位数量。而且它们还可能有不同的值，这时数据链路层为了时数据链路层为了能实现数据有效的差错控制，就采用了能实现数据有效的差错控制，就采用了一种一种“帧帧”的数据块进行传输。的数据块进行传输。分段传输分段传输。l 采用采用帧格式传输，就必须有相应的帧同步技术帧格式传输，就必须有相应的帧同步技术，这就是数，这就是数据链路层的据链路层的“成帧成帧”（也称为（也称为“帧同步帧同步”）功能。）功能。14/31成帧（帧同步）（续）l 采用帧传输方式的好处是采用帧传输方式的好处是 在发现有数据传送错误时，只需将有差错的帧再次传送，而不需要将全部数据的比特流进行重传，这就在传送效率上将大大提高。但同时也带来了两方面的问题：（1）如何识别帧的开始与结束；（2）在夹杂着重传的数据帧中，接收方在接收到重传的数据帧时是识别成新的数据帧，还是识别成已传帧的重传帧呢？这就要靠数据链路层的各种“帧同步”技术来识别了。l“帧同步帧同步”技术既可使接收方能从以上并不是完全技术既可使接收方能从以上并不是完全有序的比特流中准确地区分出每一帧的开始和结束，有序的比特流中准确地区分出每一帧的开始和结束，同时还可识别重传帧。同时还可识别重传帧。15/31IP 数据报1010 0110帧取出数据链路层网络层链路结点 A结点 B物理层数据链路层结点 A结点 B帧(a)(b)发送帧接收链路IP 数据报1010 0110帧装入数据链路层传送的是帧16/31封装成帧l 封装成帧封装成帧(framing)就是在就是在一段数据的前后分别添加首部和一段数据的前后分别添加首部和尾部，然后就构成了一个帧尾部，然后就构成了一个帧。确定帧的界限。确定帧的界限。l 首部和尾部的一个重要作用就是进行首部和尾部的一个重要作用就是进行帧定界帧定界。帧结束帧首部IP 数据报帧的数据部分帧尾部 MTU数据链路层的帧长开始发送帧开始17/31用控制字符进行帧定界的方法举例 SOH装在帧中的数据部分帧帧开始符帧结束符发送在前EOT18/31透明传输方法SOHEOT出现了“EOT”被接收端当作无效帧而丢弃被接收端误认为是一个帧数据部分EOT完整的帧发送在前19/31解决透明传输问题l 发送端的数据链路层在数据中出现发送端的数据链路层在数据中出现控制字符控制字符“SOH”或或“EOT”的的前面插入一个转义字符前面插入一个转义字符“ESC”(其十六进制编码是其十六进制编码是 1B)。l 字节填充字节填充(byte stuffing)或或字符填充字符填充(character stuffing)接收端接收端的数据链路层在将数据送往网络层之前删除插入的转义字符。的数据链路层在将数据送往网络层之前删除插入的转义字符。l 如果转义字符也出现在数据当中，那么应在转义字符前面插入一个如果转义字符也出现在数据当中，那么应在转义字符前面插入一个转义字符。当接收端收到连续的两个转义字符时，就删除其中前面转义字符。当接收端收到连续的两个转义字符时，就删除其中前面的一个。的一个。l“透明传输透明传输”是指可以让是指可以让无论是哪种比特组合的数据，都可以在数无论是哪种比特组合的数据，都可以在数据链路上进行有效传输据链路上进行有效传输。这就需要在所传数据中的比特组合恰巧与。这就需要在所传数据中的比特组合恰巧与某一个控制信息完全一样时，能采取相应的技术措施，使接收方不某一个控制信息完全一样时，能采取相应的技术措施，使接收方不会将这样的数据误认为是某种控制信息。以保证数据链路层的传输会将这样的数据误认为是某种控制信息。以保证数据链路层的传输是透明的。是透明的。20/31SOHSOHEOTSOHESCESCEOTESCSOHESCESCESCSOH原始数据EOTEOT经过字节填充后发送的数据字节填充字节填充字节填充字节填充发送在前帧开始符帧结束符用字节填充法解决透明传输的问题 SOH21/31差错检测l 在传输过程中可能会产生在传输过程中可能会产生比特差错比特差错：1 可能会变成可能会变成 0 而而 0 也可也可能变成能变成 1。l 在一段时间内，传输错误的比特占所传输比特总数的比率称为在一段时间内，传输错误的比特占所传输比特总数的比率称为误码率误码率 BER(Bit Error Rate)。l 误码率与信噪比有很大的关系。误码率与信噪比有很大的关系。l 为了保证数据传输的可靠性，在计算机网络传输数据时，必须为了保证数据传输的可靠性，在计算机网络传输数据时，必须采用各种差错检测措施采用各种差错检测措施。l 在数据通信过程可能会因物理链路性能和网络通信环境等因素，在数据通信过程可能会因物理链路性能和网络通信环境等因素，难免会出现一些传送错误，但为了确保数据通信的准确，又必难免会出现一些传送错误，但为了确保数据通信的准确，又必须须使得这些错误发生的机率尽可能使得这些错误发生的机率尽可能低。这一功能也是在数据链低。这一功能也是在数据链路层实现的，就是它的路层实现的，就是它的“差错控制差错控制”功能。功能。22/31差错检测与校正l 信号在任何信道上传输都存在着传输差错，这些差错由多信号在任何信道上传输都存在着传输差错，这些差错由多种物理现象引起，解决差错问题的方法有种物理现象引起，解决差错问题的方法有两种两种：一种是在要发送的数据中加入一定的冗余位，使接收方能知道数据是否出错，但不知道是哪里出错，这种编码方法叫差错检测码，或简称检错码。如CRC 另一种是在要发送的数据中加入足够多的冗余位，使接收方能纠正出错的位，这种编码方法叫差错校正码，或简称纠错码。如海明码。23/31纠错码海明码l 定义：一帧由定义：一帧由m个数据位（即报文）和个数据位（即报文）和r个冗余位（即校验位）组成，设个冗余位（即校验位）组成，设总长度为总长度为n（n=m+r)，此长度为，此长度为n的单元常称为的单元常称为n位码字。位码字。l 定义：两个码字不同的位的数目称为定义：两个码字不同的位的数目称为海明距离海明距离 例如，10001001 与10110001它们的海明距离为3。l 对于对于n位码字的集合，只有位码字的集合，只有2m个码字是有效的，在任意两个有效码字间个码字是有效的，在任意两个有效码字间找出具有最小海明距离的两个码字，该海明距离便定义为全部码字的海找出具有最小海明距离的两个码字，该海明距离便定义为全部码字的海明距离。明距离。l 一种编码的检错和纠错能力取决于编码后码字的海明距离的大小。一种编码的检错和纠错能力取决于编码后码字的海明距离的大小。为了检测出d个比特的错，需要使用距离为d+1的编码。例如：数据后加奇偶校验位，编码后的海明距离为2，能检测1比特错。l 为了纠正为了纠正d d个比特的错，必须用距离为个比特的错，必须用距离为2d+12d+1的编码。的编码。例如有4个有效码字：它们是0000000000，0000011111，1111100000，1111111111，海明距离为5，能纠正2比特错。24/31纠正单比特错的校验位下界l 设计一种编码，它有设计一种编码，它有m个信息位和个信息位和r个校验位，当个校验位，当r满足什么满足什么条件时，能纠正所有单比特错？条件时，能纠正所有单比特错？对对2m个有效码字的任何一个而言，有个有效码字的任何一个而言，有n个与该码字距离为个与该码字距离为1的无效码字，的无效码字，所以所以2m个有效码字每一个都对应有个有效码字每一个都对应有n+1个各不相同的位图，个各不相同的位图，n位码字的位码字的总的位图是总的位图是2n个。个。（n+1）2m=2n，n=m+r代入代入（m+r+1）2m=n+1 纠正单比特误码的校验位下界纠正单比特误码的校验位下界25/31海明编码l 海明在海明在1950年提出一种编码来纠正单比特错的编码。年提出一种编码来纠正单比特错的编码。l 该编码是将码字内的位从左到右依次编号，编号为该编码是将码字内的位从左到右依次编号，编号为2的幂的的幂的位是校验位（如第位是校验位（如第1，2，4，8），其余为信息位。），其余为信息位。l 每个校验位的取值应使得包括自己在内的一些集合服从规每个校验位的取值应使得包括自己在内的一些集合服从规定的奇偶性。定的奇偶性。l 集合的选取如下：集合的选取如下：对编号为K的信息位来说，K可以分解成2的幂的和，如编号为11，11=1+2+8，即第11位由1，2，8校验位校验，它同时属于1，2，8所在的集合。26/31改进的奇偶校验l 对数据位组成一个对数据位组成一个L位宽，位宽，K位高的长方形距阵来发送，然后对每一列单独计位高的长方形距阵来发送，然后对每一列单独计算奇偶位，并附在最后一行作为冗余位。算奇偶位，并附在最后一行作为冗余位。X X X X X XXX X X X X XXX X X X X XXX X X X X XXR R R R R R.R奇偶位K行L列检错率：1.该方法可以检测长度为L的突发性错误，但不能检测长度为L+1的突发性错误。2.假设L列中任意一列检测出错的概率为1/2，那么，整个数据块的错判率为（1/2）L。该方法用在ICMP报头检验中。27/31海明编码举例上例中，m=7，r=4，n=11，显然24=11+1，采用偶校验 3=1+2，5=1+46=2+4，7=1+2+49=1+8，10=2+811=1+2+8校验位：1（3，5，7，9，11）2（3，6，7，10，11）4（5，6，7）8（9，10，11）能纠正单比特错！在接收方，如果校验位1不满足偶校验，而其他校验位都满足，则第1位出错，28/31检错码l 在实际通信中使用纠错码好还是检错码好呢？在实际通信中使用纠错码好还是检错码好呢？l 例题例题 假设一个信道误码率是10-6，且出错是孤立产生的（即只有单比特错），数据块长度为1000比特，如果采用纠错编码，需要10个校验位（2101011），传送1M数据需要10000个校验位；如果采用检错编码，每个数据块只需一个奇偶校验位，传送1M数据只需1000个校验位和一个重传的数据1001位，共需要2001比特。l 在多数通信中采用检错编码，但在单工信道中需要纠错编在多数通信中采用检错编码，但在单工信道中需要纠错编码。码。29/31多项式编码（循环冗余码CRC）l CRC（Cyclic Redundancy Check)l CRC编码的一般操作编码的一般操作 给定一个m比特的帧或报文，发送方生成r比特的序列（也称为帧检验序列FCS，Frame Check Series），形成（m+r）的码字，该码字能被某个事先确定的数整除。接收方用相同的数去除收到的帧，如果无余数，则认为数据帧无差错。l 多项式表示：即将多项式表示：即将k比特的数据用比特的数据用k项多项式表示，它的各项多项式表示，它的各项为项为X k-1X0，它的系数为数据中对应位的，它的系数为数据中对应位的0或或1。l 例如：例如：110001可表示成可表示成X5+X4+130/31循环冗余检验的原理 l 在数据链路层传送的帧中，广泛使用了在数据链路层传送的帧中，广泛使用了循环冗余循环冗余检验码检验码 CRC 的检错技术。的检错技术。l 在发送端，先把数据划分为组。假定每组在发送端，先把数据划分为组。假定每组 k 个比个比特。特。l 假设待传送的一组数据假设待传送的一组数据 M=101001（现在（现在 k=6）。）。我们在我们在 M 的后面再添加供差错检测用的的后面再添加供差错检测用的 n 位位冗余冗余码码一起发送。一起发送。31/31冗余码的计算 l 用二进制的模用二进制的模 2 运算进行运算进行 2n 乘乘 M 的运算，这相当的运算，这相当于在于在 M 后面添加后面添加 n 个个 0。l 得到的得到的(k+n)位的数除以事先选定好的长度为位的数除以事先选定好的长度为(n+1)位的位的除数除数 P，得出，得出商商是是 Q 而而余数余数是是 R，余数，余数 R 比除数比除数 P 少少1 位，即位，即 R 是是 n 位。位。32/31冗余码的计算举例 l 现在现在 k=6,M=101001。l 设设 n=3,除数除数 P=1101，l 被除数是被除数是 2nM=101001000。l 模模 2 运算的结果是：运算的结果是：商商 Q=110101，余数余数 R=001。l 把余数把余数 R 作为作为冗余码冗余码添加在数据添加在数据 M 的后面发送出去。发送的后面发送出去。发送的数据是：的数据是：2nM+R 即：即：101001001，共，共(k+n)位。位。33/31 1101010110 Q 商 除数 P 110101 101000110100000 2nM 被除数 110101 111011 110101 111010 110101 111110 110101 101100 110101 110010 110101 01110 R 余数循环冗余检验的原理说明 34/31接收端对收到的每一帧进行 CRC 检验 l(1)若得出的余数若得出的余数 R=0，则判定这个帧没有差错，就，则判定这个帧没有差错，就接受接受(accept)。l(2)若余数若余数 R 0，则判定这个帧有差错，就，则判定这个帧有差错，就丢弃丢弃。l 但这种检测方法并不能确定究竟是哪一个或哪几个比但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。特出现了差错。l 只要经过严格的挑选，并使用位数足够多的除数只要经过严格的挑选，并使用位数足够多的除数 P，那么出现检测不到的差错的概率就很小很小。那么出现检测不到的差错的概率就很小很小。35/31帧检验序列 FCS l 在数据后面添加上的冗余码称为在数据后面添加上的冗余码称为帧检验序列帧检验序列 FCS(Frame Check Sequence)。l 循环冗余检验循环冗余检验 CRC 和帧检验序列和帧检验序列 FCS并不等并不等同。同。CRC 是一种常用的检错方法，而 FCS 是添加在数据后面的冗余码。FCS 可以用 CRC 这种方法得出，但 CRC 并非用来获得 FCS 的唯一方法。36/31应当注意 l 仅用循环冗余检验仅用循环冗余检验 CRC 差错检测技术只能做到无差错差错检测技术只能做到无差错接受接受(accept)。l“无差错接受无差错接受”是指：是指：“凡是接受的帧（即凡是接受的帧（即不不包括丢包括丢弃的帧弃的帧），我们都能以非常接近于），我们都能以非常接近于 1 的概率认为这些的概率认为这些帧在传输过程中没有产生差错帧在传输过程中没有产生差错”。l 也就是说：也就是说：“凡是接收端数据链路层接受的帧都没有凡是接收端数据链路层接受的帧都没有传输差错传输差错”（有差错的帧就丢弃而不接受）。（有差错的帧就丢弃而不接受）。l 要做到要做到“可靠传输可靠传输”（即发送什么就收到什么）就必（即发送什么就收到什么）就必须再加上须再加上确认确认和和重传重传机制。机制。37/31常用的多项式国际标准l CRC-12=X12+X11+X3+X2+X+1l CRC-16=X16+X15+X2+1l CRC-CCITT=X16+X15+X5+1l CRC-32=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+138/31本讲小结l 数据链路层的功能数据链路层的功能l 帧定界帧定界l 差错检测差错检测 循环冗余检验码（纠错码）海明码（检错码）39/31作业l 上交作业上交作业 P105,3-01,3-02,3-04,3-05,3-07