数据链路层的作用

  • 对物理层进行差错控制
  • 流量控制
  • 从数据流中区分出完整的一帧（成帧）

数据链路层的功能

相邻节点 可靠传输 帧

Data link layer has responsibility of transferring data in the type of frame from one node to adjacent node in a reliable and efficient way over a link

  • 成帧
  • 差错控制
  • 流量控制

hop-to-hop communication 逐跳通信

一跳就是两个相邻节点之间，中间没有其他同层设备

数据链路层的协议发生在一跳之间

数据链路层的硬件实现是通过网卡，所以网卡负责物理层和数据链路层的硬件实现

发送时

  • 对包进行封装
  • 添加错误校验位，流量控制，数据安全等等

接收时

  • 进行错误校验，流量控制，数据安全控制
  • 解封为包

特点

  • 无连接服务
    • LAN
    • 不标准的连接
    • 不可靠的信道
  • 可靠的面向连接服务
    • ATM技术
    • HDLC 数据通信网的一个基础协议

成帧 framing

发送方标记数据流中帧的开始和结束位置，供接收方识别

需要：

  • 接收方容易实现
  • 与传输内容无关（不可见）
  • 使用的信道带宽无关
  • 不易出错，出错后也应容易重新同步（鲁棒性）

字符计数法 Character Count

成帧方法：帧头加上长度字符

ep：51234

透明传输：无

缺点：长度字符出错，很难恢复

应用：DDCMP


字节/字符填充 Byte/Character Stuffing

成帧方法：用不常用字符或者转义字符，在数据头和尾加上字符

ep：FLAG+数据+FLAG

透明传输：利用ESC转义字符，告知接收方是否为FLAG还是数据

缺点：

  • 依赖于字符集，不同协议使用不同字符集时，不通用

  • 只适用于字符通信，对长度不为字符规格的数据不适用

应用：BISYNC（IBM），PPP


比特填充 Bit Stuffing

成帧方法：面向位成帧，用01111110来标志帧的开始与结束

透明传输：在连续五个1后插入一个0，避免出现连续六个1（即01111110）形成FLAG影响数据

缺点：受噪声影响可能会出错，可能会使数据中间出现或者失去一个FLAG导致出错

应用：HDLC

ComputerNetwork4.9


物理层编码违例法 Physical Layer Coding Violations

成帧方法：使用非法编码来标记帧的头尾

透明传输：天然支持，因为传输数据不可能是非法编码

缺点：需要存在非法编码冗余

应用：曼彻斯特编码，10Mbps网，LAN


差错控制 Error Control

单比特差错

突发差错（多位差错）

从第一位出错到最后一位出错之间的间隔就是几位差错，也就是突发长度

步骤

第一步：查错

对单比特差错：奇偶校验法

对突发差错：CRC循环冗余校验，校验盒

第二步：改错

FEC前向纠错（直接纠错）

ARQ检错校验


奇偶校验法

能查出奇数个位翻转错误，其他情况漏检率50%

CRC循环冗余校验

汉明距离：两个码字不同位的个数

如果要检测出t位的错误，需要t+1的汉明距离的码字

如果要纠正t位的错误，需要2t+1的汉明距离的码字

m - message bits 信息码

r - check bits 校验码

n = m+r

对2m2^m个合法的码字，有n个1比特差错的非法码字，也就是说总共有(N+1)2m(N+1)2^m个码字

得到不等式

(n+1)2m≤2n得（m+r+1）≤2r(n+1)2^m\le 2^n\\得\\ （m+r+1）\le 2^r

如：对7位ascii码，校验位要求4位


汉明码的校验

ComputerNetwork4.5

偶校验时，偶数个1得到0，奇数个1得到1

发送时，对第7位举例，7=1+2+4，此时1，2，4均为0，所以偶数个1，7的编码就是0

接收时，对构成的位进行异或操作，如果结果为1，那么最后结果的和就是错误的位


偷懒可以用这个方法：

ComputerNetwork4.10


检错与重传

On channels that are reliable, such as fiber, it is cheaper to use an error detecting code and just retransmitthe occasional block found to be faulty

On channels such as wirelesslinks that make many errors, it is better to add enough redundancy to each block for the receiver to be able to figure out what the original block was, i.e. using error correcting code

Example: Bit Error Rate(BER)=10−610^{-6}, 1 block= 1000bits, Data= 1Mbits

The overhead for 1000 blocks

Error detection(parity check 1bit)*1000 + （retransmission 1001bits）: 2001 bits

Hamming code : 10,000 bits, with 10 check bits for each block


多项式编码 Polynomial Code（CRC 循环冗余校验）

发送端和接收端要约定同一个生成多项式

步骤为：

（1）把生成多项式写成二项式形式

x5+x4+1:110001x^5+x^4+1:110001

（2）校验位比生成多项式的位数少一位，也就是生成多项数的最高幂数r

计算之前，被除数也就是数据的后面要添上r个0，也就是说发送数据是原数据+校验数据

（3）以数据为被除数，生成多项式为除数，进行二进制除法（最好用异或的算法）

ComputerNetwork4.1

（4）得到运算结果，加上校验数据（r个0），得到发送数据


现在我们来分析这种方法的能力。什么样的错误能被检测出来?想象一下在传输过程 中发生了一个错误，因此接收方收到的不是 T(x)，而是 T(x)+E(x)，其中 E(x)中对应的每位 1 都变反了。如果 E(x)中有 k 个 1，则表明发生了 k个1 位错误。单个突发错误可以这样描 述:初始位是 1，然后是 0和 1 的混合，最后一位也是 1，所有其他位都是 0。

接收方在收到了带校验和的帧之后，用 G(x)来除它:也就是说，接收方计算[T(x) + E(x)]/G(x)。 T(x)/G(x)是0，因此计算结果简化为 E(x)/G(x)。

如果错误恰好发生在作为因子的 G(x)多项式中，那么将无法被检测到。所有其他的错误都能够检测出来。

发送帧的顺序：先添加校验位，再进行0比特填充，再进行头尾flag的添加



流量控制 Flow Control

Ensuring the sending entity does not overwhelm the receiving entity

i.e. 避免缓冲溢出

Feedback-based flow control: （反馈流量控制）

the receiver sends back information to the sender giving it permission to send more data or at least telling the sender how the receiver is doing

  • Stop-and-Wait 单工停-等协议

    Sending ONE frame at a time


  • Sliding Window 滑动窗口协议

    Sending several frames at a time


Rate-based flow control: (速度流量控制)

the protocol has a built-in mechanism that limits the transmitting rate of senders, without using feedback from the receiver, to be studied in network layer 待网络层学习


基本算法

Utopian Simplex Protocol 乌托邦单工协议

  • 单工
  • 无错
  • 接收缓存无限
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void sender(void){
  frame s;
  packet buffer;
  while(1){
    from_network_layer(&buffer);
    s.info = buffer;
    to_physical_layer(&s);
  }
}

void receiver(void){
  frame r;
  event_type event;
  while(1){
    wait_for_event(&event);
    from_physical_layer(&r);
    to_network_layer(&r.info);
  }
}

Simplex Stop-and-Wait Protocol 无错单工停-等协议

  • 单工
  • 无错
  • 缓存有限
  • 流量控制：stop&wait
  • ack：一次只发一帧

流量控制功能：限制发送方的速度，防止淹没接收方

流量控制方法：停止等待——发送方每发完一帧，即停下来等待；收到接收方反馈（ACK），发送方才能继续发送

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void sender(void){
  frame s;
  packet buffer;
  event_type event;
  while(1){
    from_network_layer(&buffer);
    s.info = buffer;
    to_physical_layer(&s);
    wait_for_event(&event);//add:等待接收方的ack
  }
}

void receiver(void){
  frame r,s;
  event_type event;
  while(1){
    wait_for_event(&event);
    from_physical_layer(&r);
    to_network_layer(&r.info);
    to_physical_layer(&s);//add：发送一个ack给发送方
  }
}

ARQ：自动请求重传方法

如果收到的数据是错的，会进行差错控制CRC/FCS；

如果根本没收到数据（丢数据），还可能有两种情况：

  • 数据没收到：可以等重发

  • ack没收到：双方都在等，死锁

    因为发送方无法区分两种情况，所以解决方法是：设置定时器超时重发

    但是这引发了新的问题，当ack没收到时，重发会引起重复帧

要解决重复帧的问题，可以采取添加唯一序号的方法来标识帧，这时接收端会主动丢掉这个帧，并且再次发送一个ack

序号1位就够了，01交替使用


当数据没收到，或者ack没收到时，ack是否带有自身的序号，对结果是没有影响的

但是，当发生**ack到达延迟（Delayed ACK）**时会有意外的情况

无序号的ACK会使发送方误以为帧发送成功，会进行下一个帧的发送，造成本帧的丢包

所以出现ack到达延迟时，ack需要序号

总结：单向传输数据的停止等待ARQ协议

  • 发送方在数据帧中增加校验字段，发送帧之后启动超时定时器
  • 接收方检错，出错则丢弃此帧；如果校验无错，接收方发送确认帧（ACK）
  • 收到ACK后，发送方发送下一帧，重启定时器
  • 如果定时器超时，发送方重传刚发送的数据帧
  • 数据帧中携带序号，接收方根据序号来判断是否是重复的数据帧
  • ACK中携带序号，发送方根据序号判断是否是重复的ACK


双工传输技术：Sliding-Window（滑动窗口）

  • 全双工数据传输，允许捎带应答（piggybacking）/ ack来确认发送接收状态
  • 允许多个帧连续发送的情况 n个比特时，序号有[0到2n−1]共2n[0到2^n-1]共2^n个
  • Sender can send up to W frames without ACK
    • W is the sending window size
  • Destination may be able to buffer multiple frames

Piggybacking(捎带应答/确认)

When a data frame arrives, instead of immediately sending a separate control frame (ACK), the receiver restrains itself and waits until the network layer passes it the next packet

ack携带在帧中

ACK is attached to the outgoing data frame (using the ACK field in the frame header)


Sending Window & Receiving Window

Sending Window

是发送时，可以发送的帧的序号的集合

最大容量是WTW_T

Receiving Window

是接收时，可以接收的帧的序号的集合

最大容量是WRW_R

在protocol4中，WT=WR=1W_T=W_R=1


ComputerNetwork4.6

ComputerNetwork4.7

当A，B同时发送时，B会因为收到的是0，1，认为是丢包，导致重发，

连锁反应导致每条帧都要重发两次


总结：Protocol 4：实用的停止等待ARQ协议

  • 在数据帧中增加校验字段，发送帧之后启动超时定时器
  • 对于收到的数据进行检错，出错则丢弃此帧；如果校验无错，则发送确认帧（ACK）或者在回传的数据帧中捎带确认
  • 收到确认后，继续发送下一帧，重启定时器
  • 如果定时器超时，则重传刚发送的数据帧
  • 数据帧中携带发送序号，根据序号来判断是否是重复的数据帧根据ACK序号判断是否是重复的ACK

存在的问题：效率低下

efficiency=bandwidth_usedtotal_bandwidth=TtransTtotalTtrans:开始发送至收到ack的时间efficiency = \frac{bandwidth\_used}{total\_bandwidth}\\ \\=\frac{T_{trans}}{T_{total}}\\T_{trans}:开始发送至收到ack的时间

计算的时候，ack的发送时间和ack的大小可以忽略，只计算帧的发送时间，传输时延，ack的传输时延即可

要解决这个效率低下的问题，要使用protocol 5



protocol5 : Go Back N Principles

WT>1,WR=1W_T>1,W_R=1

  • Based on sliding window

    • Sending window: buffers for outstanding frames
    • Receiving window: buffers to receive frames

  • Use window to control number of outstanding frames

  • Sender is allowed to send multiple frames before receiving ACK: pipelining(流水线)

  • If Receiver detects error, discard that frame and all future frames until error frame received correctly (按序接收)

  • Transmitter must go backand retransmit that frame and all subsequent frames

ComputerNetwork4.3

ComputerNetwork4.8

Go Back N : No Need to ACK Every Frame

利用累积ACK（Cumulative ACK），一次完成多位的检验

丢数据时

接收方一旦发现数据丢失，便不会向发送方发送ack，导致发送方超时重发

ComputerNetwork4.11

丢ack时

接收方返回的ack丢失后，待发送方超时重发后，会返回最后一个收到正确数据的序号，也就是ack2

ComputerNetwork4.4

所以，Go Back N的意思就是一旦第I号帧丢掉，超时后就会将第I帧到第N帧全部重发，也就是回退到第I帧，并且此时ack并不需要重发。

极限情况下会回退N帧重发。


可能存在的问题

n位的序号有2n2^n个,

当WT=2nW_T=2^n时，若ack全部丢失，会导致一整个序列全部被重发，恰好接收方接收了一整个循环，那么接收就会出问题，所以WT≤2n−1W_T\le2^n-1

ComputerNetwork4.2

对protocol 5的改进与效率

设置ack定时器

  • 在没有数据要发送时，发送ack帧

NAK帧

  • 对于同一帧错误，只发送一次NAK，加快重传，可以不用等到超时再重传
  • NAK的序号就是出错的帧的序号
  • 在错误帧到达时或者超前帧到达时发送

协议参数与线路利用率

  • 超时定时器时限的设计

  • 滑动窗口


protocol 6 : Selective Repeat sliding window 选择重传

WR>1,WT>1W_R>1,W_T>1，可以不按序接收，不需要重传，但是要按序向上层提交

窗口大小的规定：一般情况下，要求WT+WR≤2n,也可以WT=WR≤2n−1W_T+W_R\le 2^n,也可以W_T=W_R\le 2^{n-1}

与go back N不同的是，当某一帧出现超时时，选择重传只会重发这一帧，而go back N会重发这一帧到窗口最后一帧的帧

时延计算

T=t数据传播时延+t数据处理时延（可忽略）+t数据发送时延+tack传播时延+tack发送时延+tack处理时延（可忽略）T=t_{数据传播时延}+t_{数据处理时延（可忽略）}+t_{数据发送时延}+\\t_{ack传播时延}+t_{ack发送时延}+t_{ack处理时延（可忽略）}

当忽略ack发送时延与处理时延时，

T=t数据发送时延+2t传播时延T=t_{数据发送时延}+2t_{传播时延}

信道利用率U=ttran2tprop+ttran=11+2α,α=tpropttranttran:time to transmit a frame 发送时延,tprop:propagation time from Source to Destination 传输时延信道利用率U=\frac{t_{tran}}{2t_{prop}+t_{tran}}=\frac{1}{1+2\alpha},\\\alpha =\frac{ t_{prop}}{t_{tran}}\\\\ t_{tran}: time\ to\ transmit\ a\ frame\ 发送时延,\\t_{prop}: propagation\ time\ from\ Source\ to\ Destination\ 传输时延

停等协议

当停-等协议单帧出错概率为p时，

U=1−p1+2α,U=\frac{1-p}{1+2\alpha},

滑动窗口/go back N/选择重传

U=W2α+1,W<2α+1或U=1,W≥2α+1W:窗口大小U=\frac{W}{2\alpha+1},W<2\alpha+1\\ 或\\ U=1,W\ge2\alpha+1\\\\ W:窗口大小

其实和带宽时延积BD是一样的：

U≤w1+2BDU\le \frac{w}{1+2BD}

捎带确认

要加上反向数据

U=W2(1+α)U=\frac{W}{2(1+\alpha)}

算信道利用率只算单向的信道传输，所以不需要2W



具体应用例子

只举点到点链路的样例

HDLC

  • 成帧：同步传输，以位为单位传输（面向位）

    FLAG：01111110，零比特填充（在除了FLAG的其他所有地方）

  • CRC校验

  • 流量控制和差错控制：GoBackN ARQ和选择重传ARQ

  • 面向连接服务


PPP

  • 无连接不确认服务
  • 以字节为单位传输（面向字节）
  • 只检错（CRC校验），但是不纠错
  • 没有流量控制，没有序号
  • 增强了对多种协议的支持
  • 增强了用户身份认证
  • 物理层可以是同步或者异步
  • Negotiation of connections
  • Negotiation of data compression

PPPoE(PPP over Ethernet,ADSL)

无序号，采用字节填充

所以FLAG=01111110 => 0x7D

  • 地址一般为0xFF，代表全部站点
  • 控制一般为0x03，表示未标号的模式
  • 协议支持多种
  • 校验段采用CRC检查错误