【计算机网络】3数据链路层

【计算机网络】3数据链路层

文章目录

• 前言
• 一、数据链路层设计
• • 数据链路层功能
  • 成帧
  • 差错控制
• 二、差错检测和纠正
• • 纠错码
  • 检错码
• 三、基本数据链路层协议
• • 乌托邦式单工协议（协议1）
  • 无错信道上的单工停等协议（协议2）
  • 有错信道上的单工停-等式协议（协议3）
• 四、滑动窗口协议
• • 一位滑动窗口协议(协议4)
  • 回退N协议(协议5)
  • 选择重传协议(协议6)

---

前言

DLL层设计问题
检错和纠错
数据链路层的协议 滑动窗口
数据链路层协议实例

---

一、数据链路层设计

数据链路层使用物理层提供的服务在通信信道上发送和接收比特。

数据链路层功能

(1)向网络层提供一个定义良好的服务接口。
(2)处理传输错误。
(3)调节数据流，确保慢速的接收方不会被快速的发送方淹没。

数据包和帧的关系：

提供给网络层的服务：

无确认的无连接服务	有确认的无连接服务	有确认的有连接服务
无确认式指接收方在收到数据帧后无需发回一个确认无连接服务是指在数据传输前无需建立逻辑链路	使用前不建立连接即不建立数据链路，但每帧传输必须得到确认，如果没有得到确认，将重传	使用前先建立连接，即先建立数据链路，并且每帧的传输必须得到确认
无确认并非不可靠，可靠性由上层协议负责	适用于信号传播延时较大、线路状态不一定很可靠时	适用于长距离不可靠的链路
局域网、实时通信	无线通信	卫星信道、长途电话

成帧

数据链路层使用物理层提供的服务，物理层处理的是位流，数据链路层处理的是帧
为检测错误/纠正错误，将比特流拆成离散的帧，就叫成帧。
(1)字节计数法。
利用头部中的一个字段来标识该帧中的字符数。当接收方的数据链路层看到字符计数值时，它就知道后面跟着多少个字节，因此也就知道了该帧在哪里结束。

优点： 简单
缺点： 出错无法恢复，很少使用

(2）字节填充的标志字节法。

(3)比特填充的标志比特法。

这是一种面向二进制位的帧格式，把所有需传输的数据以比特位一字排开并以特殊的位模式01111110作为帧标志，即一个帧的开始（同时标志前一个帧的结束）
当帧内容中出现一个与帧标志相同的位串01111110，则在5个1后插入一0，即变成01111101，接收方将自动删除第5个1后的0。这称为位填充法，也称为透明传输。
如果由于干扰，一个帧没有正确接收，则可扫描接收串，一旦扫描到01111110，即新的一帧从此开始。即可以再同步

(4）物理层编码违禁法。
在曼切斯特编码中，连续高电平或连续低电平可用作帧边界
采用冗余编码技术，如曼切斯特编码，即两个脉冲宽来表示一个二进制位
数据0：低-高电平对
数据1：高-低电平对
高-高电平对和低-低电平对没有使用，可用作帧边界

差错控制

差错控制： 帧的校验
          接收端对帧的确认（确认帧)
          超时与重发（计时器)
          帧的序号
流量控制： 基于反馈的流控
          基于速率的流控（发送端确定，在DLL中几乎不采用)
差错类型：

单个错误	突发错误
分散在各块	集中在各块

突发错误优点： 从优势方面来看，计算机数据总是成块发送。
突发错误缺点： 突发错误的缺点在于当它们发生时比单个错误更难以纠正。

二、差错检测和纠正

纠错码： 前向纠错技术，因其需要太多的冗余位，纠错开销太大，在有线网络中极少使用，主要用于无线网络中。
检错码 ： 只能发现错误，不能纠正，可重传，主要用于局域网
码字： 包含数据位和校验位的n位单元（模式）
海明距离： 两个码字不同位的海明距离

int x=mazi1&mazi2;
int distance = 0;
while(x){distance++;x -= x & -x;
}

海明距离越大，纠错能力越强，有效信息越少，传输效率越低
海明距离d+1，可检测d位错，海明距离2d+1，可纠正d位错
例：奇偶校验海明距离为2，1个比特错误可检测出来，两个比特错误，不能检测出错。

纠错码

纠一位错的海明码：
发送方： 根据校验集合填充校验位，数据直接填入数据位

校验位： 1，2，4，8，16，32,…
数据位： 3，5，6，7，9，10，…
校验位1校验的集合为： 1，3，5，7，9，…
校验位2校验的集合为： 2，3，6，7,10,11，…
校验位3校验的集合为： 4，5，6，7,12,…
例：发送数据1001000，m=7，计算得r=4，校验位为1，2，4，8


则发送数据为00110010000
接受端纠正海明码：
接收方： 根据检验集合判定校验位是否出错，出错位的位编号累加到计数器
将计数器counter=0，将校验位校验集合进行奇/偶校验，出错则counter加上校验位的编号，counter的值则是出错位的编号（counter=0无错误）
例:分析得到11位错了，正确码00111000101

利用海明码纠正突发错误： 将连续的k个码按行排列成矩阵发送数据时，按列发送，每列k位，如果一个突发性错误长度是k位，则在k个码字中，至多只有一位受到影响，正好可用海明码纠错改位后恢复

检错码

奇偶校验：
奇偶位取值等同于对数据位进行模2和运算
例如，采用偶校验：发方1110000->11100001
检测出错的概率为50%
循环冗余检错码CRC：
工作原理：k位的帧等于k-1次多项式
例如：1011001 -> x⁶+x⁴+x³ +x⁰（6阶7项多项式）
生成多项式: G(x)为r阶
例如：x⁴ +1->1001为4阶
m位帧的多项式： m>r,M(x)>G(x)
T(x)=x^r M(x)（相当于在原码字后加r个0）
如T(x)/G(x) = Q(x) + R(x)/G(x) 其中Q(x)为商，R(x)/G(x)为余数则( T(x) -R(x) )一定能被G(x)整除，即余数为0
发送方码字： 被除数减去模2除法的余数
接收方： 判断余数是否为0，为0（正确），不为0（错误）

三、基本数据链路层协议

假设：
物理层、数据链路层和网络层各自是独立的处理进程
机器A希望向B发送的是一个可靠的、面向连接的长数据流
假设机器不会崩溃
从网络层拿到的数据是纯数据
最简单的三个协议：

无限制的单工协议	单工停-等协议	有噪声信道的单工协议
信号的传播在某时刻是单向的，即单工
处理的是“完美”的传输 环境一 “ 乌托邦” 协议	做简单的流控 防止接收方被数据所淹没	解决噪声信道带来的错误 引出肯定确认技术

帧结构：

typedef struct {frame_kind kind;//帧类型seq_nr seq;//顺序号seq_nr ack ;//确认号packet info;//分组（分组是帧的纯数据）} frame;

与物理层、网络层接口：

乌托邦式单工协议（协议1）

数据单向传送
收发双方的网络层都处于就绪状态（随时待命)处理时间忽略不计（瞬间完成)
可用的缓存空间无穷大（无限空间)
假设DLL之间的信道永远不会损坏或者丢失帧（完美通道)
“乌托邦”

typedef enum {frame_arrival} event_type;
#include "protocol.h"
void sender1 (void)//封装
{frame s;packet buffer;while (true){from_network_layer (&buffer) ;s.info = buffer;to_physical_layer (&s);
}void receiver1 (void)//解封装
{frame r;event_type event;while (true) {wait_for_event (&event);from_physical_layer(&r);to_network_layer (&r .info) ;}
}

无错信道上的单工停等协议（协议2）

解决如何避免收方被涌入的数据淹没，即取
消“接收方允许无限量接收”的假设
解决方法：收方回发一个哑帧，接收方收到
哑帧，表明收方允许接收数据，此时再次发
送下一帧数据。
实际上是半双工协议

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 packet */event_type event ;/*frame_arrival is the only possibility */while (true) {from_network_1ayer (&buffer) ;/*go get something to send */s.info = buffer;/*copy it into s for transmission */to_physical_layer(&s);/*bye-bye little frame *///-----------------------------------------------------------------------------wait_for_event (&event) ;/*do not proceed until given the go ahead*///-----------------------------------------------------------------------------void receiver2(void)
{frame r,s;/*buffers for frames */event_type event;/*frame_arrival is the only possibility */while (true){wait_for_event(&event);/*only possibility is frame_arrival */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 to awaken sender * ///-----------------------------------------------------------------------------

有错信道上的单工停-等式协议（协议3）

异常： 发送方发出的数据丢失，收方发送的确认帧丢失导致发送方一直等待
解决： 发送方设置定时器，一定时间未收到答复，则重发。
异常： 定时器设置时间过短导致，发送方重复发送帧，接收方无法区别
解决： 设置帧序号，用于排序

#define MAX_SEQ1/*must be 1 for protocol 3 */
typedef enum {frame_arrival,cksum_err,timeout } event_type;
#include "protocol .h"
void sender3(void)
{seq_nr next_frame_to_send;/*seg number of next outgoing frame*/frame s;/*scratch variable */packet buffer;/*buffer for an outbound packet*/event_type event;next_frame_to_send = 0;/* initialize outbound sequence numbers */from_network_layer(&buffer);/* fetch first packet */while (true){s .info =buffer;/*construct a frame for transmission */s.seq= next_frame_to_send;/*insert sequence number in frame */to_physical_layer (&s) ;/*send it on its way *///-----------------------------------------------------------------------------start_timer(s. seq);/*if answer takes too long. time out*///-----------------------------------------------------------------------------wait_for_event(&event) ;/*frame arrival, cksum_err,timeout*/if(event == frame_arrival) {from_ physical_layer(&s);/*get the acknowledgement*/if(s.ack == next_frame_to_send){//-----------------------------------------------------------------------------stop_timer(s.ack) ;/*turn the timer off *///-----------------------------------------------------------------------------from_network_layer ( &buffer) ;/*get the next one to send*/inc (next_frame_to_send) ;/*invert next_frame_to send*/}}}
}void receiver3 (void)
{seq_nr frame_expected;frame r,s;event_type event;frame_expected = 0;while (true) {wait_for_event(&event） ;/*possibilities: frame_arrival, cksum_err */if(event == frame_arrival){/*a valia frame has arrived */from physical_layer(&r) ;/*go get the newly arrived frame */if (r.seq == frame_expected){/*this is what we have been waiting for */to_network_layer(&r.info);/*pass the data to the net work layer */inc(frame_expected) ;/*next time expect the other sequence nr */}//-----------------------------------------------------------------------------s.ack =1 - frame_expected;to_physical_layer(&s);//-----------------------------------------------------------------------------}}
}

提高传输效率：
全双工
捎带确认（和外发的数据帧一起）
批发数据（在等待的时间发送数据帧）

四、滑动窗口协议

发送窗口	接受窗口
已经发送，未被确认的帧的序列号	期望接受的帧的序列号

一位滑动窗口协议(协议4)

接收方收到帧后，首先核对是否为预期帧号(seq=frame_expected)，如果是的，则接收并frame_expected+1，即移动接收窗口。
发送端收到应答帧，核对响应帧号ack=next_frame_to_send，核对无误后，从网络层取新的帧，并执行next_frame_to_send+1，即移动发送窗口。如核对帧号不正确，则不移动窗口

特点：
序列号seq和确认值ack“0”“1”交替
滑动窗口长度W=1，收到确认才移动窗口
保证按顺序将接收到的正确帧只一次上交网络层
协议4的信道利用率：
信道传输速率是:b bps
每帧的大小是:k bits
来回的时间是:R sec
则信道的利用率是：
k/(k+bR)
提高效率的方法：
增加滑动窗口最大长度W，在等待的时间继续发送
W的确定：
带宽-延迟积：BD
窗口值：W=2BD+1
上述的例子：
BD=50kbps0.250=12.5kb
W=2*12.5kb+1=26kb=26帧

回退N协议(协议5)

接受方： 丢弃错误帧及其以后
发送方： 重发错误帧及其以后

选择重传协议(协议6)

回退N帧和选择性重传的比较:

	回退N帧	选择性重传
缓冲区	发送方	接收方
适用网络环境	出错率小	出错率大

协议6滑动窗口的选择：
发送窗口：W=(MAX_SEQ+1)/2
发送窗口通常小于接受窗口，使新老窗口不重叠
三个协议的窗口大小：

	协议4:滑动窗口	协议5:回退N帧	协议6:选择性重传
发送窗口(SWnd)	0<SWnd<=1	0<SWnd<=MAX_SEQ	0<SWnd<=RWnd
接受窗口(RWnd)	RWnd=1	RWnd=1	RWnd<=(MAX_SEQ+1)/2