计算机网络——数据链路层（数据链路层概述及基本问题）

链路、数据链路和帧的概念 

        数据链路层在物理层提供服务的基础上向网络层提供服务，其主要作用是加强物理层传输原始比特流的功能，将物理层提供的可能出错的物理连接改造为逻辑上无差错的数据链路，使之对网络层表现为一条无差错的链路。

           链路(Link）是指从一个节点到相邻节点的一段物理线路（有线或无线)，而中间没有任何其他的交换节点。 

        因为H1——R2的路径中存在R1路由器，所以只能称作通信路径

        数据链路(Data Link)是基于链路的。当在一条链路上传送数据时，除需要链路本身，还需要一些必要的通信协议来控制这些数据的传输，把实现这些协议的硬件和软件加到链路上，就构成了数据链路。

        计算机中的网络适配器（俗称网卡）和其相应的软件驱动程序就实现了这些协议。一般的网络适配器都包含了物理层和数据链路层这两层的功能。
 

         

        帧(Frame）是数据链路层对等实体之间在水平方向进行逻辑通信的协议数据单元PDU。

        为了简单起见，我们可以不考虑其他各层，可以考虑成帧是在通信双方的通信数据链路层的对等实体之间

         

几个基本问题 

封装成帧

        封装成帧是数据链路层的重要功能之一。它指的是在数据链路层将上层（通常是网络层）传来的数据加上帧头和帧尾，形成一个完整且独立的数据传输单元，这个单元被称为帧。

        接收端在收到物理层上交了比特流后，就能根据首部和尾部的标记，从收到的比特流中识别出帧的开始和结束，也就是进行帧定界。

        帧头通常包含源地址、目的地址以及其他控制信息，而帧尾包含用于检测数据传输错误的校验码

1. 数据链路层在接收到网络层的数据报文后，在其前后添加特定的首部和尾部信息。
2. 首部信息可能包括源和目的MAC地址、协议类型标识等。
3. 尾部信息通常包含校验序列，用于在接收端验证数据在传输过程中是否发生错误。
4. 成帧后的数据能够被物理层准确识别并进行传输，同时在接收端也能准确地恢复原始的数据报文。

        为了提高帧的传输效率，应当使帧的数据部分长度尽可能地大于首部和尾部的长度。但是，每一种链路层协议都规定了所能传送的帧的数据部分长度上限——最大传送单元 MTU

透明传输

        某些特定的比特序列恰好与帧界定符相同，这就可能导致帧边界混淆。 

        为了解决以上问题，我们引出了透明传输：

                透明传输是指数据链路层对上层交付下来的协议数据单元PDU没有任何限制，就好像数据链路层不存在—样。  

面向字节的透明传输 

        为了使数据中的“帧定界”在接收端不被解释为控制字符，具体的方法是:发送端的数据链路层在数据中出现控制字符“Flag”的前面插入一个转义字符“ESC”(其十六进制编码是 1B，二进制是00011011)。

        而在接收端的数据链路层在把数据送往网络层之前删除这个插入的转义字符。这种方法称为字节填充(byte stuffing)或字符填充(character stuffing)。

        如果转义字符也出现在数据当中，那么解决方法仍然是在转义字符的前面插入一个转义字符。

面向比特的透明传输         

                如果数据中连续出现了多个1比特，则在传输时会在连续的1比特之间自动插入一个0比特，接收端再按照规定移除这些额外插入的0比特。 

练习 

 

        因为记错帧首部位置和帧尾部位置而没弄明白。

 差错检测

        实际的通信链路都不是理想的，比特在传输过程中可能会产生差错（称为比特差错)∶

                        1.比特1可能变成比特0

                        2.比特0可能变成比特1

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

        提高链路的信噪比，可以降低误码率。但在实际的通信链路上，不可能使误码率下降为零，使用差错检测技术来检测数据在传输过程中是否产生了比特差错,是数据链路层所要解决的重要问题之一。

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

奇偶校验 

1. 奇校验是在待发送的数据后面添加1个校验位，使得添加该校验位后的整个数据中比特1的个数为奇数。
2. 偶校验是在待发送的数据后面添加1个校验位，使得添加该校验位后的整个数据中比特1的个数为偶数。

        但是数据位和校验位各1位误码可能就校验不出来 

       

        奇偶校验的标准都是一样。

循环冗余校验 

        数据链路层广泛使用漏检率极低的循环冗余校验(Cyclic Redundancy Check，CRC)检错技术

循环冗余校验CRC的基本思想:

        收发双方约定好一个生成多项式G(X)。

        发送方基于待发送的数据和生成多项式G(X)，计算出差错检测码（冗余码)，将冗余码添加到待发送数据的后面一起传输。

        接收方收到数据和冗余码后，通过生成多项式G(X)来计算收到的数据和冗余码是否产生了误码。

生成多项式 

冗余码的求法

                        这是发送方传输的内容：冗杂码替换构造被除数时生成的0     

         接收方只需要通过被除数和除数来验证余数是否为0，依次判断传输是否产生误码。

两种校验方式的特点 

1. 奇偶校验、循环冗余校验等差错检测技术，只能检测出传输过程中出现了差错，但并不能定位错误，因此无法纠正错误。
2. 要想纠正传输中的差错，可以使用冗余信息更多的纠错码（例如海明码）进行前向纠错。但纠错码的开销比较大，在计算机网络中较少使用。
3. 在计算机网络中，通常采用我们后续课程中将要介绍的检错重传方式来纠正传输中的差错，或者仅仅丢弃检测到差错的帧，这取决于数据链路层向其上层提供的是可靠传输服务还是不可靠传输服务。
4. 循环冗余校验CRC具有很好的检错能力（漏检率极低)，虽然计算比较复杂，但非常易于用硬件实现，因此被广泛应用于数据链路层。

可靠传输 

        可靠传输是当接收方接受到的帧出现误码时，接收方会通知发送方进行重传，发送方就给接收方重传

        帧传输结束后，利用帧尾部FSC字段码检测出帧的数据部分出现误码

        检测出误码后的处理方式取决于数据链路层向上层提供的服务类型：

• 不可靠传输服务:仅仅丢弃有误码的帧，其他什么也不做;
• 可靠传输服务:通过某种机制实现发送方发送什么，接收方最终就能收到什么。

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

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

 传输差错

分组丢失

        假设H1向H3发送一个分组，此时R2输入队列快满了，主动丢弃收到的分组，于是造成了分组丢失的结果。

分组失序 

        假设H1向H3发送一个分组，因为走的路径不同，致使分组到达顺序与发送顺序不同，导致分组失序

分组重复

        假设H1向H3发送一个分组，起先分组到达R5，R5路由器繁忙所以在队列中等待较长时间，致使H1超时重发，致使H3获得了重复分组 

 可靠传输的一些基本概念

 

 停止-等待协议的实现机制

停止等待协议中的理想情况

        这是停止等待协议中的理想情况，对数据分组逐一发送，当检测出有差别的组再否认分组，使发送方重新传送之前误码的数据分组。

传输出现差错的情况及解决措施

发送方传输数据时丢失

        接收方收不到数据分组，就不会发送相应的ACK或NAK，如果不采取措施，发送方就会一直处于等待接收方ACK或NAK的状态。

---

解决方式

        设置一个超时重传时间，使接受方超过一定时间未接受到传输的数据，便使发送方传输数据。

接收方方传输“确认”指令时丢失

        当接收方接收方方传输“确认”指令时丢失，会使发送方误以为“传输数据失败”而重新发送数据，致使分组重复。

---

解决方式

        

• 为了避免分组重复这种传输错误，必须给每个分组带上序号。
• 对于停止-等待协议，由于每发送一个数据分组就停止等待，只要保证每发送一个新的数据分组，其序号与上次发送的数据分组的序号不同就可以了，因此用一个比特来编号就够了，序号有0和1这两个。

        当发送误以为“传输数据失败”而重新发送数据后，接收方会检测数据序号，重复的数据分组丢弃，再发送下一个分组。       

确认指令也可以编序号避免传输错误

        当第一个数据（data0）的确认指令传输延误时，致使发送方再次传输data0，重复的data0传输完成后，接收方识别序号辨认出重复，丢弃后会再次发送一个确认分组

        data0的确认指令随之到达后，但发送方会认为这是第二组数据data1的确认指令，便发送了data1，此时重复分组的data0的确认指令传输到发送方。

        发送方会以为，这是对data1数据的确认，将发送下一组data0。（这里需要注意以为编序号只用0和1，所以下一组data0与第一次data0不是同一组数据）

---

确认指令编序号后

        总而言之，谁迟到了，就不管谁，随便它用什么方式来都可以，来了就记录你的序号。成功过的就从该序号下一位开始，再发也不管。

停止-等待协议的【注意事项】 

        否认机制的使用：使用超时重传机制后，就可以不使用否认机制了，这样可使协议实现起来更加简单。但是，如果点对点链路的误码率较高，使用否认机制可以使发送方在超时计时器超时前就尽快重传。

        比特编号的使用：为了让接收方能够判断所收到的数据分组是否是重复的，需要给数据分组编号。由于停止-等待协议的特性，只需1个比特编序号即可，即序号0和序号1。

        为了让发送方能够判断所收到的确认分组是否是重复的，需要给确认分组编号，所用比特数量与数据分组所用比特数量一样

        数据链路层可以不给确认分组信号：数据链路层一般不会出现确认分组迟到的情况，因此在数据链路层实现停止-等待协议可以不用给确认分组编号。

        重传时间的设置：给超时计时器设置的超时重传时间RTO应当仔细选择，一般将RTO设置为略大于收发双方的平均往返时间RTT。

                不同层重传时间的设置方法：

                        在数据链路层，点对点的往返时间RTT比较固定，RTO就比较好设定。

                        在运输层，由于端到端往返时间非常不确定，设置合适的超时重传时间RTO有时并不容易

        重传协议的原理：停止-等待协议属于自动请求重传(Automatic Repeat reQuest，ARQ）协议。即重传的请求是发送方自动进行的，而不是接收方请求发送方重传某个误码的数据分组。（这一点我现在才明白）
 

信道利用率 

        信道利用率是指发送方在单位时间内有效发送数据的时间占整个发送周期的比例。

         

        TD:发送方发送数据分组所耗费的发送时延

        RTT:是信号在收发双方之间往返专播航耗费的时间

        TA:是接收方发送确认分组航耗费的发送时延

---

1. 若出现超时重传，对于传送有用的数据信息来说，信道利用率还要降低。
2. 在往返时间RTT相对较大的情况下，为了提高信道利用率，收发双方不适合采用停止-等待协议，而可以选择使用回退N帧(GBN)协议或选择重传（SR)协议。

练习——信道利用率 

 

后退N帧协议

        后退N帧协议（简称GBN）是一种在数据链路层使用的基于滑动窗口的流量控制和差错控制机制。

        相对于停止-等待协议，GBN提高了传输效率，允许发送方一次性发送多个数据帧而不必等待每个帧的确认后再发送下一个帧。 

• 在使用流水线传输方式时，发送方不能无限制地连续发送数据分组，否则可能会导致网络中的路由器或接收方来不及处理这些数据分组，进而导致数据分组的丢失，这实际上是对网络资源的浪费。因此，必须采取措施来限制发送方连续发送数据分组的数量。
• 回退N帧协议采用流水线传输方式，并且利用发送窗口来限制发送方连续发送数据分组的数量，这属于连续ARQ协议。

 

滑动窗口协议

• 接收方每正确收到一个序号落入接收窗口的数据分组，就将接收窗口向前滑动一个位置,这样就有一个新的序号落入接收窗口。与此同时，接收方还要给发送方发送针对该数据分组的确认分组。
• 发送方每收到一个按序确认的确认分组，就将发送窗口向前滑动一个位置，这样就有一个新的序号落入发送窗口，序号落入发送窗口内的数据分组可继续被发送。
• 在回退N帧协议的工作过程中，发送方的发送窗口和接收方的接收窗口按上述规则不断向前滑动。因此，这类协议又称为滑动窗口协议。

 

 无差错的情况下