数据链路层 Data Link Layer

数据链路层 Data Link Layer

Responsible for packaging bits into frames with appropriate control information to synchronise, control errors and address other connected nodes.

通常被分为两个子层:Medium Access Control Layer (MAC) 和 Logical Link Control Layer (LLC)

Frame Synchronisation 帧同步

了使传输中发生差错后只将有错的有限数据进行重发,数据链路层将比特流组合成以帧(frame)为单位传送,每个帧包含一个帧头,一个有效载荷域,和一个帧尾

帧的组织结构必须设计成使接收方能够 明确地从物理层收到的比特流中对其进行识别,也即能从比特流中区分出帧的起始与终止,这就是帧同步要解决的问题。由于网络传输中很难保证计时的正确和一致,所以不可采用依靠时间间隔关系来确定一帧的起始与终止的方法。有四种解决方法:

Character Count 字节计数法

这是一种以一个在帧头部的专门字段来标明帧内字节数的帧同步方法。接收方可以通过对该特殊字符的识别从比特流中区分出帧的起始并从专门字段中获知该帧中随后跟随的数据字节数,从而可确定出帧的终止位置。

这个方法的问题在于,这个专门字段有可能被传输错误篡改,从而接收方无法得到下一帧的起始位置,由于校验和是错误的,即使接收方知道改帧已被损坏要求重传也无济于事,因为目标方并不知道要跳过多少字符才能到重传的开始处。

Flag bytes with byte stuffing 使用字节填充的首尾定界符法

该法用(两个)标志字符(flag)来定界一帧的起始与终止,当数据中也存在标志字符时,在前面加上转义字符ESC。若转义字符也存在于数据中,在转义字符当前面也加上一个转义字符来表示数据自带的转义字符。

Flag bits with bit stuffing 使用比特填充的首尾标志法

该法以一组特定的比特模式(如01111110 实际就是一个flag字节)来标志一帧的起始与终止。为了不使信息位中出现的与特定比特模式相似的比特串被误判为帧的首尾标志,可以采用比特填充的方法。比如,采用特定模式01111110,则对信息位中的任何连续出现的五个“1”,发送方自动在其后插入一个“0”,而接收则做该过程的逆操作,即每接收到连续五个“1”,则自动删去其后所跟的“0”

Error Detection 错误检测

解决来“标示每一帧的起始于结束位置”的问题之后,我们现在来看:如何确保所有的帧最终都被递交给了目标机器上的网络层,并且保持正确的顺序。

Parity 奇偶校验位

一个二进制码字,如果它的码元有奇(偶)数个1,就称为具有奇(偶)性,增加可用验证奇偶性来检测奇数个错误。

Cyclic Redundancy Check 循环冗余校验码CRC

For a block of k bits, transmitter generates n bit check sequence. n bits chosen such that k+n is exactly divisible by some number. Receiver divides the frame contents by that number; if no remainder, assumes no error

Data Link Protocols for Error Control

Stop-And-Wait 停等协议

发送方发出一帧,然后等待一个确认(ACK),再继续发送。否则重传最后帧,每个帧必须被标记数字序列,因为当发送方没有接收到ASK时会重新传输最后帧,接收方就会收到两个相同帧,加上序列即可discard重复的帧。

Tagging frames with a 1-bit identifier enables the receiver to tell whether a frame is new or a retransmission. The transmitter must keep the last frame in a buffer in case retransmission is required. 

A timer is required in the transmitter – an ACK is expected within the timeout period. If no ACK is received, the last frame is retransmitted, otherwise the next frame can be sent.

Sliding Window Protocols 滑动窗口协议

In these protocols, the Transmitter (TX) and Receiver (RX) both maintain “windows” of frames:

  • The TX window contains frames sent but unacknowledged.
  • The RX window specifies the frames accepted by the receiver.
  • As RX gets ‘wanted’ frames, it slides its window forward and as TX receives ACKs, it slides its window.

最简单的滑动窗口协议——后退N帧协议(Go-back-N): 发送窗口>1,接收窗口为1,如果接收方遇到错误,发送Rejection(REJ),丢弃所有后续的帧,并不为后续的帧发送ASK,直到正确帧到达。

  1. 第i帧在传输过程中损坏:接收方发送REJ,发送方重新发送第i帧与其后续帧。
  2. 第i帧在传输过程中丢失:发送方继续发送第i+1帧,接收方收到第i+1帧并发送REJ,发送方重新发送第i帧与其后续帧。
  3. 第i帧丢失,没有后续帧到达:既不发送ACK也不发送REJ,发送方超时后重新发送第i帧。
  4.  ACK丢失:若发送方没有超时,后续ACK成功到达,则没有关系;若发送方超时则重新发送没有收到ACK的对应帧与其后续帧。

GBN只允许顺序接收帧,并且为了减少开销,可在连续收到好几个确认帧后,才对最后一个数据帧发送ACK,也就是说,对某一帧对确认就表示对该帧和之前的所有数据帧都已正确收到了。

选择重传协议(Selective Retransmission SR):发送窗口>1,接收窗口>1。接收方总会缓存所有的帧,当某个帧出现错误时,只会要求重传这一个帧。

PPP(Point-to-Point)协议: 用户计算机与互联网服务提供商(ISP)进行通信的协议

PPP handles error detection, supports multiple protocols, allows IP addresses to be negotiated at connection time, permits authentication, etc.

使用LCP(链路控制协议)建立并维护数据链路连接(身份验证,上网计费),使用NCP(网络控制协议)允许早点到点连接上使用多种网络层协议。