数据链路层-上篇
概述
咱们首先来看看数据链路层在网络体系结构中的位置。
如图所示，主机H1向主机H2发送数据，两头要通过3个路由器和电话网、局域网、广域网等多种网络。
从五层协定原理体系结构的角度来看，主机应具备体系结构中的各个档次。
而路由器仅需具备体系结构中上面三层，各设施通过物理层上面的传输媒体进行互连。
当主机H1向H2发送数据时，主机H1将待发送的数据逐层封装后，通过物理层将形成数据包的各比特转换为电信号，发送到传输媒体。
数据包进入路由器后，由下往上逐层解封到网络层。路由器依据数据包的目标网络地址和本身转发表，确定数据报的转发端口。而后从网络层向下逐层封装数据包，并通过物理层将数据包发送到传输媒体。
数据包最终达到主机H2时，还要由下往上逐层解封，最终解封出主机H1所发送的数据。
主机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 reQuest)，意思是重传的申请是主动进行，因为不须要接管方显式地申请，发送方重传某个发送的分组。
回退N帧协定GBN
为什么应用回退N帧协定？
因为进行-期待协定的信道利用率很低，若呈现超时重传，则信号利用率更低。
在雷同的工夫内，应用进行-期待协定的发送方只能发送一个数据分组，而采纳流水线传输的发送方，能够发送多个数据分组。
回退N帧协定在流水线传输的根底上，利用发送窗口来限度发送方可间断发送数据分组的个数。
无差错状况流程
发送方将序号落在发送窗口内的0~4号数据分组，顺次间断发送进来。
他们通过互联网传输正确达到接管方，没有乱序和误码，接管方按序接管它们，每接管一个，接管窗口就向前滑动一个地位，并给发送方发送针对所接管分组的确认分组，再通过互联网的传输正确达到了发送方。
发送方每接管一个、发送窗口就向前滑动一个地位，这样就有新的序号落入发送窗口，发送方能够将收到确认的数据分组从缓存中删除了，而接管方能够择机将已接管的数据分组交付下层解决。
应用回退N帧协定的接管方，能够采纳累积确认的形式。也就是说，接管方不肯定要对收到的数据分组一一发送确认，而是能够在收到几个数据分组后，对按序达到的最初一个数据分组发送确认，ACKn示意序号为n及以前的数据分组都已正确接管。
假如发送方发送0-4号数据分组，正确达到接管方后进行发送确认分组，比方当确认到1号数据分组时，给发送方发送了一个累计确认ACK1，随后进行后续承受完2-4号数据分组后，又发送了一个ACK4。
即便ACK1在发送给发送方时失落了，当ACK4达到发送方时，也能够晓得序号为4及以前的数据曾经被接管方正确接管了。发送方就能够将收到确认分组的数据从缓存中删除。
累计确认的优缺点：
长处:
- 即便确认分组失落，发送方也可能不用重传
- 减小接管方的开销
- 减小对网络资源的占用
毛病：
- 不能向发送方及时反映出接管方曾经正确接管的数据分组信息
有过错状况
例如，在传输数据分组时，5号数据分组呈现误码，接管方通过数据分组中的检错码发现了谬误。
于是抛弃该分组，而后续达到的这剩下四个分组与接管窗口的序号不匹配。
接管方同样也不能接管它们，将它们抛弃，并对之前按序接管的最初一个数据分组进行确认，发送ACK4，每抛弃一个数据分组，就发送一个ACK4。
当收到反复的ACK4时，就晓得之前所发送的数据分组呈现了过错，于是能够不等超时计时器超时就立即开始重传，具体收到几个反复确认就立即重传，依据具体实现决定。
如果收到这4个反复的确认并不会触发发送方立即重传，一段时间后。超时计时器超时，也会将发送窗口内已发送过的这些数据分组全副重传。
在本例中，只管序号6、7、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个地位，这样6、7、0、1这四个新的序号落入接管窗口。
2号确认分组通过互联网的传输达到发送方，发送方接管该确认分组，发送方窗口能够向前滑动4个地位。这样6、7、0、1这四个新的序号落入发送窗口。
这样就能够持续发送接下来的数据了，并且从缓存中删除之前的数据分组。
总结
如果发送窗口和接管窗口的尺寸超过了取值范畴，就会使接管方无奈分辨新、旧数据分组，进而呈现分组反复这种传输过错。