数据链路层

设计目标：关注的是点到点、两个临近机器之间的高效的、可靠的关系链接算法。”像一根线又不是一根线“

成帧

错误控制

流控制

为网络层做服务

通过协议栈的方式链接到物理层上

基本数据交互传递原理

Q：如何向网络层提供服务？

A：非确定的面向非链接服务（LANS局域网）、确定的面向非链接的服务（常用于非可靠链接例如无线系统）、确定的面向链接的服务（计时器、序列号、建立的链接）

帧

很容易说明出统一协议的重要性

结点A与结点B通过点对点的方式链接起来，接收结点必须明确发送出的帧的bits构成、是什么、从哪里开始从哪里结束

字节计数（DEC：DDCMP）：每一帧的帧首就是计数位，储存了发送的这一帧的大小位数

如果某一帧首发生错误，那么取址发生错误，容易对后面帧的取址造成严重影响

字节填充：增加一个标志来区别不同的帧，在帧首前与帧尾后增添一个flag

如果传递的信息内就包含flag等，解决办法如下：

比特填充（HDLC）：起始flag使用比特填充（01111110），若信息内出现连续6个1，那么在第五个1后添加0，在接收的时候自动去除。

和字节填充比起来更加有效率

但是两者也都不是完全能避免错误

差错控制

确保传输到网络层的所有帧都是要在正确的顺序之上

方式：

向寄件人提供一些有关错误信息的反馈
如果帧数据完全消失——如果帧的ADC丢失了，或者超时，向寄件人发出警告；管理计时器与帧序列，保证传输的帧是确切的那一个，不多也不少

典型错误：丢帧（传送过程丢失）——有时候由于噪音，有时候直接从队列中丢失、帧损坏（bits损坏）

错误纠错——FEC：前向纠错

更多用于错误率较高的信道上，因为重传的信息也有高概率出错

错误检错——Parity check：能够检测出单个bit错误、CRC、ARQ

用于高度可靠的信道上（光纤），如果发生错误重传即可

流控——缓速接收者不被高速发送者淹没

两种常用方式进行控制：

Feedback-based：接收者向发送方发送反馈信息，给与发送方许可来接收更多信息，或者至少告诉发送方接收者正在做什么

Rate-based：该协议的内置机制直接限制发送方的数据传输速率，无需接收方反馈

Stop-Wait
滑动窗口协议

HDLC and PPP

Elementary Data Link Protocols

首先，假设物理层、数据链路层和网络层都是独立的进程，它们通过来回传递消息进行通信。有助于使概念更加清晰，同时也可以强调每一层的独立性。

许多协议公用的一些声明：

#define MAX_PKT 1024 /*determines packet size in bytes */
typedef enum (false, true} boolean;  /* boolean type */ 
typedef unsigned int seq_nr;/* sequence or ack numbers */
typedef struct (unsigned char data [MAX_PKT]；} packet;/* packet definition */  
typedef enum (data, ack, nak} frame_kind; /* frame_kind definition */ 
typedef struct{/* frames are transported in this layer */ 
    frame_kind kind;  /* what kind of frame is it? */ 
    seq_nr seq;  /* sequence number */
    seq_nr ack; /* acknowledgement number */
    packet info; /* the network layer packet */
    } frame;
 /* Wait for an event to happen； return its type in event. */ 
void wait_for_event(event_type *event);
/* Fetch a packet from the network layer for transmission on the channel. */ 
void from_network_layer(packet *p);
/* Deliver information from an inbound frame to the network layer. */ 
void to_network_layer(packet *p); 
/* Go get an inbound frame from the physical layer and copy it to r. */ 
void from_physical_layer(frame *r);
/* Pass the frame to the physical layer for transmission. */ 
void to_physical_layer(frame *s);
/* Start the clock running and enable the timeout event. */ 
void start_timer(seq_nr k);
/* Stop the clock and disable the timeout event. */ 
void stop_timer(seq_nr k);
/* Start an auxiliary timer and enable the ack_timeout event. */ void start_ack_timer(void);
/* Stop the auxiliary timer and disable the ack_timeout event. */ void stop_ack_timer(void);
/* Allow the network layer to cause a network_layer_ready event. */ void enable_network_layer(void); 
/* Forbid the network layer from causing a network_layer_ready event. */ 
void disable_network_layer(void);
/* Macro inc is expanded in-line: increment k circularly. */ 
#define inc(k) if (k < MAX SEQ) k = k + 1； else k = 0

Utopia(乌托邦式单工协议)

不会出现任何错误的协议，不需要考虑任何情况，数据只能单向传输

这个没道理的协议分为发送过程与接收过程。发送过程运行在源机器的数据链路层上；接收过程运行在目标机器的数据链路层上。唯一需要处理的事件类型是frama_arrival（收到完好帧）

typedef enum {frame_arrival} event_type;
#include "protocol.h"
void senderl(void){
    frame s;//buffer for an outbound frame
    packet buffer;//buffer for an outbound packer
    while(true){
        from_network_layer(&buffer);//go get something to send
        s.info=buffer;//copy it onto s for transmission
        to_physical_layer(&s);//send it on its way
    }
}
              
void receiver1(void){
    frame r;
    event_type event;
    while(trye){
        wait_fot_event(&event);
        from_physical_layer(&r);//go get the inbound frame
        to_network_layer(&r.info);//pass the data to the network layer
    }
}

stop-and-wait(无错信道上的单工停-等式协议)

解决发送方以高于接收方能处理到达帧的速度发送帧，导致接收方被淹没的问题，但是仍然单工

如果升级接收方硬件，使用更强大的接收器，具有更大的缓存与数据处理能力，但是成本较高，容易浪费资源，并只是纯粹将问题转移到网络层。

就像水龙头与蓄水池，最好的解决方法就是关小水龙头。

接收方给发送方提供反馈信息：等待对方确认到达后才能继续发送，这样的协议称为停-等式协议。这个模型规定了流量交替关系，只允许发送方发送一帧接收方再发送一帧，依次反复。可以说是采用半双工的物理信道即可。

typedef enum {frame_arrival} event_type;
#include "protocol.h"
void sender2(void){
    frame s;//buffer for an outbound frame
    packet buffer;//buffer for an outbound packer
    event_type event;/*********/
    while(true){
        from_network_layer(&buffer);//go get something to send
        s.info=buffer;//copy it onto s for transmission
        to_physical_layer(&s);//send it on its way
        wait_for_event(&event);/*********/
    }
}
              
void receiver2(void){
    frame r,s;
    event_type event;
    while(true){
        wait_fot_event(&event);
        from_physical_layer(&r);//go get the inbound frame
        to_network_layer(&r.info);//pass the data to the network layer
        to_physical_layer(&s);//send a dummy frame*****
    }
}

ARQ或者PAR(有错信道上的单工停-等式协议)

现在信道有可能出错，帧有可能损坏，也可能被丢失

发送错误的帧会使得接收方能检测出来，这是这种协议最大的目的。

在协议二的基础上，增加一个计时器。

如果接收方受到错误帧，就将其丢弃，那么发送方就会超时，并再次进行发送。

缺陷是接收方其实并不知道送过来的包是被丢失了，还是被发送了多份过来，他只管进行信息查验。

试想一下确认帧完全丢失，接收方是不管确认帧的存活的，于是发送方一遍又一遍地进行包发送，接收方一次又一次接收重复的包，并认为这样子是没问题的。

所以新的需求是让接收方知道收到的帧是新帧还是老帧。

做法就是在帧头加一个序号，序号的格式需要着重考虑，理论上，需要位数很多，因为包会很多；需要位数很少，因为不能冗余。

但实际情况发送方选择是否发送新一帧的条件是前一个帧成功完成了流程，也就是说其实帧头序号只需要一个二进制位，因为只需要和前一帧做对比即可。

typedef enum {frame_arrival} event_type;
#include "protocol.h"
void sender3(void){
    seq_nr next_frame_to_send;//帧头序号
    frame s;//buffer for an outbound frame
    packet buffer;//buffer for an outbound packer
    event_type event;/*********/
    next_frame_to_send=0;//initialize
    from_network_layer(&buffer);//go get something to send
    while(true){
        s.info=buffer;//copy it onto s for transmission
        s.seq=next_frame_to_send;//帧头写入
        to_physical_layer(&s);//send it on its way
        start_timer(s.seq);//timer
        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);//下一帧头信息（0变11变0）
            }
        }
    }
}
              
void receiver3(void){
    seq_nr frame_expected;//所期望的帧头
    frame r,s;
    event_type event;
    frame_expected=0;
    while(true){
        wait_fot_event(&event);
        from_physical_layer(&r);//go get the inbound frame
        if(r.seq==frame_expected){
            to_network_layer(&r.info);//pass the data to the network layer
            inc(frame_expected);
        }
        s.ack=1-frame_expected;
        to_physical_layer(&s);//send a dummy frame*****
    }
}

//解析略，看不懂代码自己看书去

滑动窗口协议

保证两个方向的数据传输，也就是全双工数据传输

有一种方法是将前面的协议复制一份，一份用来传递数据，一份用来传递确认帧——这样就导致了带宽浪费。这是最差的情况。

在正常情况下前面的协议其实可以进行双工数据传输，毕竟确认帧的存在已经证实了可以进行双工数据交流。

捎带确认（piggybacking）指接收方在收到包的时候，确认帧并不马上发出，而是等待下一个要逆向发出的正常包一起发出。

这样的方法节省了带宽，但不保证时间，因为接收方接收到包与接收方下一个包的发出之间有一定时间，在这个时间内发送方不可能进行下一个包的传输，这样的时间浪费十分可惜。

可以进行手动操控这个时间，比如设置一个计时器，如果在这段时间内下一个数据包没有到来，那么马上发送单独的确认帧。

这是一种方法，不过网络传播这么大一个工程，不太可能会为了等待一个确认帧而真的停滞不前了，要知道第一个数据帧的发出是不需要确认帧的，所以有没有可能一次性发出多个数据帧，然后把这些数据帧的信息都保存起来，一个个等候确认帧呢？

当然这儿的“一次性”并不是真的一次性并发出去了，而是将这一系列待发送的数据包标记，然后一个个待发送。这么一个队列称为“滑动窗口”，当然，多个包的并发使得确认帧头的01失效，必须使用更多的1234...来进行更多帧的标记。

本质上就是对这些帧进行缓存。在进行确认过后或者重发并确认过后再移动窗口。

1位滑动窗口协议

滑动窗口的缓冲效果是有限的，现在设想这样一个场景，在景区检票口的队列上，检票员如果检查到了有问题的票务，他并不会停下来，而是一边确认有问题的票务，一边继续检查队列后的票务，这样在问题票务解决时，已经被检查过的人员可以保证一股脑放出。但机器代码协议并不像人，普通的滑动窗口协议，这个“出问题的人”会一直将队列拥堵，就好比如果窗口下限一直未解决，且缓冲到了一定限制，那么这个检票口就会一直拥堵。

这是一个夸张的例子，但是如果把出问题的人单独拉到一边形成队列，让他不堵上窗口，保证后面的正常游客能顺利出游，甚至派专人来调查问题人，也就是说把滑动窗口分裂，是不是就不会造成拥堵了呢？

但是在我们似乎能进行性能优化之前，我们最好先解决1位滑动窗口协议的一些残留问题。

发送方与接收方相互发送包，等待确认帧的到来再继续发送下一个包，这只是单方面为信息传递划分了界限、做出了严厉的限制。理想情况的下的发包在实验室外永远不会发生，现实情况下可以会出现以下情况：超时时间设置较短（或者说发送过程时间较长），在第一个包还在发送的过程中就不断超时，然后发送方不断发出重复包。即使没有出现错误的情况下，重复发包仍然会不断浪费宝贵的带宽。

回退N协议

如果把传输路程夸张化，会发现保护机制变成了纯粹的累赘

如果和月球通信，哪怕信息以光速传播，传播时间也是用分钟来计时，试想一下你玩的网络游戏下一帧要等待几分钟才能加载？

放宽这个限制是必然的结局，于是我们便有了“滑动窗口”，那么如何找到一个滑动窗口的“容量”呢。从最佳效率解上看，这个容量其实也就是信道传播路程的容量，只要我们能保证信道源源不断地在进行信息传输，那么带宽利用率一定不会低。这个容量由比特/秒的带宽乘以单向传送时间决定，如果一次发送路程可以容纳BD（带宽-延迟乘积）数量的帧，那么w设置成2BD+1，+1指那个确认帧。

这是最佳效率的容量，也可以说是“最大窗口尺寸”，如果w是一次性发送，或者说是成功发送的帧数，那么链路利用率=w/（1+2BD）

保持多个帧同时传送的技术是管道化的一个内容，它可以保证如果在传输过程中出现了差错，比如某个帧丢失，那么他后面的那些正在路上的帧的处置方式。

回退N：将后续所有的帧都丢失，不发出确认帧，让发送方直接重新发送。这样的话，大量的错误会=造成大量的带宽浪费。
选择重传：坏帧丢弃，缓存正常的帧。如果窗口很大，那么这种方式对内存需求很大。
结合使用：当接收到坏帧时，发送一个否定确认，直接让发送方进行重传，不用等待超时时间。

在发送方这边，由于接收方需要将缓存的数据在坏帧重新发送成功时直接输送给网络层，释放缓存空间，所以发送方需要同时将一系列帧都“确认”，这个特性叫累计确认。

选择重传协议

前面已经暗示了，这个协议需要发送方与接收方各自维护一个缓存区域。

//协议示例代码过长。。//

按照惯例，这个协议也应该出现了一点毛病了，那就是“窗口重叠”问题。现在假设一组窗口帧全部丢失的情况，那么发送方不会理会丢失，而是直接发送下一组前序一模一样但内容不一样的帧，接收方在接收到这一组帧的时候返回确认帧，那么这一组确认帧的表现到底是“前一组丢失的帧”还是“这一组正常的帧”呢，发送方无法分辨，接收方就更得知不了了，于是协议“正确”，发送发出了一个错误的包。

解决方法是限制窗口最大尺寸小于序号空间的一半，这样的话，在任何时候都只会出现一半序号空间数量的待确认的帧，这样就能避免重叠的情况发生。

PPP

点到点协议

PPP的帧格式酷似HDLC帧格式，区别在于PPP面向字节而不是比特