数据链路层-上篇

概述

咱们首先来看看数据链路层在网络体系结构中的地位。算法

如图所示，主机H1向主机H2发送数据，中间要通过3个路由器和电话网、局域网、广域网等多种网络。缓存

从五层协议原理体系结构的角度来看，主机应具备体系结构中的各个层次。网络

而路由器仅需具备体系结构中下面三层，各设备经过物理层下面的传输媒体进行互连。并发

当主机H1向H2发送数据时，主机H1将待发送的数据逐层封装后，经过物理层将构成数据包的各比特转换为电信号，发送到传输媒体。性能

数据包进入路由器后，由下往上逐层解封到网络层。路由器根据数据包的目的网络地址和自身转发表，肯定数据报的转发端口。而后从网络层向下逐层封装数据包，并经过物理层将数据包发送到传输媒体。编码

数据包最终到达主机H2时，还要由下往上逐层解封，最终解封出主机H1所发送的数据。spa

主机H1到H2的通讯，能够当作是在4段不一样的链路上的通讯组成的。计算机网络

所谓链路（Link）就是从一个结点到相邻结点的一段物理线路，而中间没有任何其余的交换节点。队列

仅有链路还不够，还须要一些通讯协议来控制这些数据的传输。资源

数据链路（Data Link）是指把视线通讯协议的硬件和软件加到链路上，就构成了数据链路。

在数据链路层上传输的数据包，又称为帧。

也就是说，数据链路层是以帧为单位传输和处理数据。

数据链路层的三个重要问题

数据链路层传送的协议数据单元是帧

封装成帧

• 封装成帧 (framing) 就是在一段数据的先后分别添加首部和尾部，而后就构成了一个帧。
• 首部和尾部的一个重要做用就是进行帧定界。

差错控制

发送方将封装好的帧经过物理层发送到传输媒体，在传输过程当中可能会产生比特差错：1 可能会变成 0， 而 0 也可能变成 1。

可是，接收方主机如何判断帧在传输过程当中是否出现误码？

这能够经过检错码来发现。发送方在发送帧以前，基于待发送的数据和检错算法计算出检错码。并将其封装在帧尾。

可靠传输

接收方主机收到有误码的帧后，是不会接受该帧的，会将它丢弃。

若是数据链路层向其上层提供的是不可靠服务，那么丢弃就丢弃了，不会再有更多措施。

若是数据链路层向其上层提供的是可靠服务，那就还须要其余措施，来确保接收方主机还能够从新收到被丢弃的这个帧的正确副本。

以上三个问题都是使用 点对点信道的数据链路层来举例的

若是使用广播信道的数据链路层除了包含上面三个问题外，还有一些问题要解决

如图所示，主机A，B，C，D，E经过一根总线进行互连，主机A要给主机C发送数据，表明帧的信号会经过总线传输到总线上的其余各主机，那么主机B，D，E如何知道所收到的帧不是发送给它们的，主机C如何知道发送的帧是发送给本身的？

能够用编址（地址）的来解决。将帧的目的地址添加在帧中一块儿传输。

另外还有数据碰撞问题。

当总线上多台主机同时使用总线来传输帧时，这是采用广播信道的共享式局域网不可避免的。

随着技术的发展，交换技术的成熟，

在 有线（局域网）领域 使用点对点链路和链路层交换机的交换式局域网取代了共享式局域网。

在无线局域网中仍然使用的是共享信道技术。

封装成帧

封装成帧是指数据链路层给上层交付的协议数据单元添加帧头和帧尾使之成为帧。

帧头和帧尾中包含有重要的控制信息。

发送方的数据链路层将上层交付下来的协议数据单元封装成帧后，还要经过物理层，将构成帧的各比特，转换成电信号交给传输媒体，那么接收方的数据链路层如何从物理层交付的比特流中提取出一个个的帧？

实际上，帧头和帧尾的做用之一就是帧定界。

但比不是每一种数据链路层协议的帧都包含有帧定界标志，例以下面例子：

前导码

• 前同步码：做用是使接收方的时钟同步
• 帧开始定界符：代表其后面紧跟着的就是MAC帧

另外以太网还规定了帧间间隔为96比特时间，所以，MAC帧不须要帧结束定界符。

接下来咱们介绍透明传输的问题，透明传输是指数据链路层对上层交付的传输数据没有任何限制，就好像数据链路层不存在同样。

帧界定标志也就是个特定数据值，若是在上层交付的协议数据单元中， 刚好也包含这个特定数值，接收方就不能正确接收。

因此数据链路层应该对上层交付的数据有限制，其内容不能包含帧定界符的值。

解决透明传输问题

解决方法：面向字节的物理链路使用字节填充 (byte stuffing) 或字符填充 (character stuffing)，面向比特的物理链路使用比特填充的方法实现透明传输。

发送端的数据链路层在数据中出现控制字符“SOH”或“EOT”的前面插入一个转义字符“ESC”(其十六进制编码是1B)。

接收端的数据链路层在将数据送往网络层以前删除插入的转义字符。

若是转义字符也出如今数据当中，那么应在转义字符前面插入一个转义字符 ESC。当接收端收到连续的两个转义字符时，就删除其中前面的一个。

为了提升帧传输的效率，应当使帧的数据部分的长度尽量大些。

考虑到差错控制等多种因素，每一种数据链路层协议都规定了帧的数据部分的长度上限，即最大传送单元MTU（Maximum Transfer Unit）。

差错检测

介绍

咱们知道，实际的通讯链路都不是理想的，比特在传输过程当中可能出现差错：1可能会变成0，而0可能会变成1。这称为比特差错。

在一段时间内，传输错的比特占所传输比特总数比率称为误码率BER（Bit Error Rate）

使用差错检测码来检测数据在传输过程当中是否产生了比特差错，是数据链路层所要解决的重要问题之一。

奇偶校验

在待发送的数据后面添加1位奇偶校验位，使整个数据（包括所添加的校验位在内）中"1"的个数为奇数（奇校验）或偶数（偶校验）。

经过下面例子能够看出：

若是有奇数个位发生误码，则奇偶性发生变化，能够检测出误码。

若是有偶数个位发生误码，则奇偶性不发生变化，不能检测出误码（漏检）。

因为奇偶校验的漏检率比较高，所以计算机网络的数据链路层通常不会采用这种检测方法。

循环冗余校验CRC(Cyclic Redundancy Check)

这是一种具备很强检错能力的检错方法，漏检率极低。

• 收发双方约定好一个生成多项式G(x)；
• 发送方基于待发送的数据和生成多项式计算出差错检测码（冗余码），将其添加至待传输数据后面一块儿传输；
• 接收方经过生成多项式来计算收到的数据是否产生了误码；

总结

• 检错码只能检测出帧在传输过程当中出现了差错，但并不能定位错误，所以没法纠正错误。
• 要想纠正传输中的差错，可使用冗余信息更多的纠错码进行前向纠错。但纠错码的开销比较大，在计算机网络中较少使用。
• 循环冗余校验CRC有很好的检错能力（漏检率很是低），虽然计算比较复杂，但很是易于用硬件实现，所以被普遍应用于数据链路层。
• 在计算机网络中一般采用咱们将要讨论的检错重传方式来纠正传输中的差错，或者仅仅是丢弃检测到差错的帧，这取决于数据链路层向其上层提供的是可靠传输服务仍是不可靠传输服务。

循环冗余校验 CRC 是一种检错方法，而帧校验序列 FCS 是添加在数据后面的冗余码。

可靠传输

基本概念

当检测出帧中出现了比特差错，那么，接下来该如何处理呢？这取决于数据链路层向其上层提供的服务类型。

若是提供的是不可靠传输服务：仅仅丢弃有误码的帧，其余什么也不作。

若是提供的是可靠传输服务：想办法实现发送端发送什么，接收端就接收什么。

通常状况下，有线链路的误码率比较低，为了减小开销，并不要求数据链路层向上提供可靠传输服务，即便出现了误码，可靠传输的问题也由其上层处理。

然而，无线链路易受干扰，误码率比较高，所以要求数据链路层必须向上层提供可靠传输服务。

须要说明的是比特差错只是传输差错中的一种。

从整个计算机网络体系结构来看，传输差错还包括分组丢失、分组失序以及分组重复。

• 分组丢失：路由器输入队列快满了，主动丢弃收到的分组。
• 分组失序：数据并未按照发送顺序依次到达接收端。
• 分组重复：因为某些缘由，有些分组在网络中滞留了，没有及时到达接收端，这可能会形成发送端对该分组的重发，重发的分组到达接收端，但一段时间后，滞留在网络的分组也到达了接收端，这就形成分组重复的传输差错。

分组丢失、分组失序以及分组重复这些传输差错，通常不会出如今数据链路层，而会出如今其上层。

可靠传输服务并不只局限于数据链路层，其余各层都可选择实现可靠传输。

三种可靠协议

• 中止-等待协议SW
• 回退N帧协议GBN
• 选择重传协议SR

这三种可靠传输实现机制的基本原理并不只限于数据链路层，能够应用到计算机网络体系结构的各层协议中。

中止-等待协议SW

确认与否定

以下图所示，收发双方基于互联网通讯，而不是局限于一条点对点的数据链路。

发送方给接收方发送数据分组，接收方收到后对其进行差错检测，如没有误码，则接受该数据分组，并给发送方发送确认分组，简称为ACK。

发送方收到对所发送数据分组的确认分组后，才能发送下一个数据分组。

假设这个数据分组在传输过程当中出现了误码，接收方收到后对其进行差错检测，发现了误码，则丢弃该分组。并给发送方发送否定分组，简称NAK。

发送方收到对所发送数据分组的否定分组后，就知道了本身以前发送的数据分组出现了差错而被接收方拒绝，因而马上重传该数据分组。

所以发送方每发送完一个数据分组后，并不能马上将该数据分组从缓存中删除，只有在收到针对该数据分组的确认分组后，才能够将其从缓存中删除。随后发送下一个数据分组。

超时重传

发送方给接收方发送数据分组，然而该数据分组在传输过程当中丢失了。

须要说明的是，对于数据链路层点对点信道而言，不太容易出现这种状况。

但对于多个网络经过多个路由器互连的复杂互联网环境而言，是会常常出现的。

接收方收不到数据分组，就不会发送ACK或者NAK。若是不采起其它措施，发送方就会一直处于等待接收方ACK或者NAK的状态。

为解决该问题，能够在发送方发送完一个数据分组后，启动一个超时计时器。若到了超时计时器所设置的重传时间而发送方仍没有收到接收方的ACK或NAK，则重传原来的数据分组，这就叫作超时重传。

通常可将重传时间设置为略大于"从发送方到接收方的平均往返时间"。

• 在数据链路层点对点的往返时间比较肯定，重传时间比较好设定。
• 然而在运输层，因为端到端往返时间很是不固定，设置合适的重传时间并不容易。

确认丢失

到目前为止，貌似基于中止等待、使用确认或否定分组，再加上超时重传的手段，就能够实现可靠传输了。

但请你们思考一下，是否还会出现目前手段不足以应对实现可靠传输的状况呢？

既然发送方发送的数据分组可能丢失，那么接收方放的确认或否定分组也可能丢失。

当接收方发送ACK或NAK丢失时候，必然会形成发送方对以前所发送数据分组的超时重传。

那么接收方如何判断该数据分组是不是一个重复分组呢？

为避免分组重复这种传输错误，必须给每一个分组带上序号。

对于中止-等待协议，因为每发送一个数据分组就中止等待，只要保证每发送一个新的数据分组，其发送序号与上次发送的数据分组的序号不一样便可。

所以，使用一个比特来编号就够了。

确认迟到

既然发送分组须要编号，那么确认分组是否也须要编号呢？

咱们来看这种状况，发送方发送0号数据分组，接收方正确接收后，给发送方发送确认分组。因为某些缘由，该分组迟到了。

这必然会致使发送方进行超时重传，在重传0号数据分组的传输过程当中，发送方接收到迟到了确认分组。因而发送1号数据分组。

接收方收到数据分组后，发现是一个重复的数据分组，则丢弃。并针对该数据分组发送确认分组，以避免再次超时重传。

咱们能够清楚地看到，这是对0号数据的重复确认。

可是发送方又如何知道呢？若是不采起其它措施的话，发送方会误认为这是对1号数据分组的确认分组。

若是对确认分组也进行编号，就能够解决这种误判。

对于数据链路层的点对点信道，往返时间比较固定，不会出现确认迟到的状况，能够不用给确认分组编号。

像中止-等待协议这样经过确认和重传机制实现的可靠传输协议，常称为自动请求重传协议ARQ( Automatic Repeat re Quest)，意思是重传的请求是自动进行，由于不须要接收方显式地请求，发送方重传某个发送的分组。

回退N帧协议GBN

为何使用回退N帧协议？

由于中止-等待协议的信道利用率很低，若出现超时重传，则信号利用率更低。

在相同的时间内，使用中止-等待协议的发送方只能发送一个数据分组，而采用流水线传输的发送方，能够发送多个数据分组。

回退N帧协议在流水线传输的基础上，利用发送窗口来限制发送方可连续发送数据分组的个数。

无差错状况流程

发送方将序号落在发送窗口内的0~4号数据分组，依次连续发送出去。

他们通过互联网传输正确到达接收方，没有乱序和误码，接收方按序接收它们，每接收一个，接收窗口就向前滑动一个位置，并给发送方发送针对所接收分组的确认分组，再经过互联网的传输正确到达了发送方。

发送方每接收一个、发送窗口就向前滑动一个位置，这样就有新的序号落入发送窗口，发送方能够将收到确认的数据分组从缓存中删除了，而接收方能够择机将已接收的数据分组交付上层处理。

使用回退N帧协议的接收方，能够采用累积确认的方式。也就是说，接收方不必定要对收到的数据分组逐个发送确认，而是能够在收到几个数据分组后，对按序到达的最后一个数据分组发送确认，ACKn表示序号为n及之前的数据分组都已正确接收。

假设发送方发送0-4号数据分组，正确到达接收方后进行发送确认分组，好比当确认到1号数据分组时，给发送方发送了一个累计确认ACK1，随后进行后续接受完2-4号数据分组后，又发送了一个ACK4。

即便ACK1在发送给发送方时丢失了，当ACK4到达发送方时，也能够知道序号为4及之前的数据已经被接收方正确接收了。发送方就能够将收到确认分组的数据从缓存中删除。

累计确认的优缺点：

优势:

• 即便确认分组丢失，发送方也可能没必要重传
• 减少接收方的开销
• 减少对网络资源的占用

缺点：

• 不能向发送方及时反映出接收方已经正确接收的数据分组信息

有差错状况

例如，在传输数据分组时，5号数据分组出现误码，接收方经过数据分组中的检错码发现了错误。

因而丢弃该分组，然后续到达的这剩下四个分组与接收窗口的序号不匹配。

接收方一样也不能接收它们，将它们丢弃，并对以前按序接收的最后一个数据分组进行确认，发送ACK4，每丢弃一个数据分组，就发送一个ACK4。

当收到重复的ACK4时，就知道以前所发送的数据分组出现了差错，因而能够不等超时计时器超时就马上开始重传，具体收到几个重复确认就马上重传，根据具体实现决定。

若是收到这4个重复的确认并不会触发发送方马上重传，一段时间后。超时计时器超时，也会将发送窗口内已发送过的这些数据分组所有重传。

在本例中，尽管序号六、七、0、1的数据分组正确到达接收方方，但因为5号数据分组误码不被接受，它们也会受牵连而不被接受，发送方还要重传这些数据分组，这就是所谓的GO-back_N（回退N帧）。

可见，当通讯线路信号很差时，回退N帧协议的信道利用率并不比中止-等待协议高。

总结

• 回退N帧协议在流水线传输的基础上利用发送窗口来限制发送方连续发送数据分组的数量，是一种连续ARQ协议。
• 在协议的工做过程当中发送窗口和接收窗口不断向前滑动，所以这类协议又称为滑动窗口协议。

选择重传协议SR

回退N帧协议的接收窗口尺寸WR只能等于1，所以接收方只能按序接收正确到达的数据分组。

一个数据分组的误码就会致使其后续多个数据分组不能被接收方按序接收而丢弃（尽管它们无乱序和误码）。这必然会形成发送方对这些数据分组的超时重传，显然这是对通讯资源的极大浪费。

为了进一步提升性能，可设法只重传出现误码的数据分组。所以，接收窗口的尺寸WR不该再等于1而应该大于1，以便接收方先收下失序到达但无误码而且序号落在接收窗内的那些数据分组，等到所缺分组收齐后再进一并送交给上层。这就是选择重传协议。

须要注意的是： 选择重传协议为了使发送方仅重传出现差错的分组，接收方 不能再使用累计确认，而须要对每一个正确接收到的数据分组进行 逐一确认

假设采用3个比特给分组编序号，所以序号的取值范围是0-7，当序号到达7时再从0开始。

接收方的WR通常可与发送窗口的尺寸WT取值相同

发送方将数据分组按序发送出去，通过互联网传输后陆续到达接收方，但其中2号数据分组丢失了。

只要序号落入接收窗口内且无误码的数据分组，接收方都会接收。

接收方接收0号和1号数据分组，并发送0号和1号确认分组，接收窗口向前滑动两个位置，这样就有4和5这两个新的序号落入接收窗口。

接收方接收3号分组，并发送3号确认分组，但接收窗口不能向前滑动，由于3号数据分组是未按序到达的数据分组。

这些确认分组通过互联网的传输陆续到达发送方。发送方每按序收到一个确认分组，发送窗口就向前滑动一个位置。

发送方接收0号和1号确认分组，发送窗口向前滑动两个位置。这样就有4和5这两个新的序号落入发送窗口。

发送方将序号落入发送窗口的4号和5号数据发送出去。这时发送方就能够删除0号和1号数据缓存。

接收方可择机将已接收到的0和1交付给上层处理。

发送方接收3号确认分组，但发送窗口不能向前滑动，由于这是一个未按序到达的确认分组，发送方还未收到它以前的2号确认分组。不过须要记录3号数据分组已收到确认，这样该数据分组就不会超时重发。

随后接收方接收4号和5号数据分组，并发送4号和5号确认分组，但接收窗口不能向前滑动，由于它们是未按序到达的数据分组。接收方还没收到它们以前的2号数据分组。

随后发送方会针对2号数据进行超时重发，此时发送方也接收到了4号和5号的确认分组，但发送窗口不能向前滑动，由于由于这是一个未按序到达的确认分组，发送方还未收到它以前的2号确认分组。不过须要记录4号和5号数据分组已收到确认，这样该数据分组就不会超时重发。

随后接收方接收到2号数据分组，接受窗口就能够向前滑动4个位置，这样六、七、0、1这四个新的序号落入接收窗口。

2号确认分组通过互联网的传输到达发送方，发送方接收该确认分组，发送方窗口能够向前滑动4个位置。这样六、七、0、1这四个新的序号落入发送窗口。

这样就能够继续发送接下来的数据了，而且从缓存中删除以前的数据分组。

总结

若是发送窗口和接收窗口的尺寸超过了取值范围，就会使接收方没法分辨新、旧数据分组，进而出现分组重复这种传输差错。