计算机网络与通信（第4章）

1、 第4章 数据链路控制 第4章 数据链路控制 4.1 概述 4.2 数据链路控制的基本机制 4.3 自动请求重传 4.4 差错校验 4.1 概述数据链路层负责在单个链路上的发送和接收结点之间传送帧 4.1 概述 数据链路层的通信对等实体之间的数据传输通道称为数据链路(Data Link)，包括物理链路和必要的传输控制规程。 理想的数据链路应该满足以下两个条件： 不管发送方以多快的速率发送数据，接收方总能够来得及接收、处理并上交主机； 传输的任何数据，既不会出现差错也不会丢失。 第1个条件不满足就必须进行流量控制(Flow Control)。 第2个条件不满足就必须进行差错控制(Error Co

2、ntrol)。4.1 概述 实现流量控制的一个重要方法是滑动窗口(Sliding Window)机制。 实现差错控制的一个基本方式是反馈重传纠错。 自动请求重传ARQ (Automatic Repeat reQuest)，ARQ综合了滑动窗口机制和确认-重传机制，进行流量控制和差错控制，实现可靠传输。 媒体接入控制(Medium Access Control, MAC)。4.2 数据链路控制的基本机制 4.2.1 滑动窗口 发送方和接收方分别设置发送窗口和接收窗口。 发送窗口用来对发送方进行流量控制，落在窗口内的帧是可以连续发送的，其大小WT指明在收到对方确认(ACK)之前发送方最多可以发送多

3、少个帧。 只有到达的数据帧的序号落在接收窗口之内时才可以被接收，否则将被丢弃。一般地，当接收方收到一个有序且无差错的帧后，接收窗口向前滑动，准备接收下一帧，并向发送方发送出一个ACK。 当发送方收到接收方的ACK后，发送窗口才能向前滑动，滑动的长度取决于接收方确认的序号。 4.2.1 滑动窗口发送方的滑动窗口 4.2.2 反馈重传 反馈重传机制可以采用以下措施： 差错发现 反馈确认信息 正确认/肯定确认(Positive Acknowledgement) 累计确认(Cumulative Acknowledgement) 捎带确认(Piggybacking) 负确认(Negative AcKno

4、wledgement, NAK) 重传 超时重传(Timeout Retransmission) 负确认重传 4.3 自动请求重传 4.3.1 停等自动请求重传 发送方发出一个数据帧后停下来不再发送，等待接收方的ACK到达，ACK到达后才发送下一帧。 发送窗口大小是WT=1，接收窗口大小也是1。 处理 3 种传输差错： 接收方收到了发来的数据帧，但检测出差错； 发送方发出的数据帧丢失； 接收方收到正确的数据帧，但发出的ACK丢失。 对于差错1，即收方丢弃此帧，并可采取下面两种方式进行重传。 负确认重传。 超时重传。 4.3.1 停等自动请求重传 对于2和3这两种差错，可采取超时重传。但对于差错

5、3，超时重传会使接收方收到两个同样的数据帧。解决重复帧的方法是为数据帧和确认帧编上序号。 停等ARQ采用超时重传的方式。 停等ARQ机制的问题是可能产生严重的低效率。 链路的利用率：/2/2/2DATADATAACKPRODATADATATTTTTT 帧的比特长度帧的比特长度链路的比特长度 4.3.1 停等自动请求重传停等ARQ传输过程示例 4.3.2 回退-N ARQ WT1，发送方在每收到一个ACK之前不必等待，可以连续地发送窗口内的多个帧，也称为连续ARQ，提高了传输的吞吐量和传输效率。 也使用超时重传机制。定时器超时仍未收到ACK，则要重传此帧，而且还必须重传此帧后面所有的已发帧，这正

6、是这种 机制称为回退-N ARQ的原因。 接收方的接收窗口WR=1，当接收方收到一个有序且无差错的帧后，接受窗口向前移动，并向发送方发出一个ACK。 发送窗口应满足：21nTW 最大序号 4.3.2 回退-N ARQ回退-N ARQ接收窗口 4.3.2 回退-N ARQ回退-N ARQ传输过程示例 4.3.3 选择重传ARQ 在回退-N ARQ机制的基础上作了如下两点改进： 接收窗口WR1，这样可以接收和保存正确到达的失序的帧； 出现差错时只重传出错的帧，后续正确到达的帧不再重传，从而提高了信道的利用率。 选择重传ARQ应该满足：2 / 21 / 2nTRWW最大序号 4.4 差错校验 4.4

7、.1 奇偶校验 在发送数据后附加一个校验位，校验位的取值时的包括数据和校验位中的“1”的个数分别为奇数/偶数。 奇偶校验检错能力有限，只能校验出奇数个错但不能校验出偶数个错。 优点是简单、易实现，在位数不长的情况下常常采用。 4.4.2 循环冗余校验 码多项式 n 位长度的位串 可以用n -1次码多项式表示： 例如，位串1010001的码多项式为: 数据后面附加上冗余码：k 位的信息码后面附加上r 位的冗余码: 由信息码生成冗余码 用一个特定的r 次多项式G(x)去除 ，其余数为r-1次的码多项式R(x)，对应的r 位的位串作为冗余码。G(x)称为生成多项式(Generator Polynom

8、ial)。 除法中使用模2减(无借位减，相当于作异或(XOR)运算)。1210nnCCCC C 121210nnnnC xCxCxC xC641xx rC xx K xR x rx K x 4.4.2 循环冗余校验 生成冗余码示例 信息段： m(x) = 111111 生成多项式： g(x) = 1001 ，检验位 r = 3，CRC多项式： r(x) = 111111000 求解 r(x) 除以 g(x) 的余数： 1 1 1 0 0 0 _ 1 0 0 1 / 1 1 1 1 1 1 0 0 0 1 0 0 1 - 1 1 0 1 1 0 0 1 - 1 0 0 1 1 0 0 1 - 0 0 0 4.4.2 循环冗余校验 传输差错校验 接收方将接收到的C(x)除以生成多项式G(x)，只要余数不为零，则表明校验出传输差错，若余数为零，则可以认为传输无误。 常用的生成多项式 CRC-8用于ATM信元头差错校验。 CRC-16是HDLC规程中使用的。 CRC-32是IEEE802.3以太网中采用的。 4.4.3 校验和 IP、ICMP、TCP和UDP中广泛使用校验和运算的例子 二进制反码求和 对一个无符号的数，先求其反码，然后从低位到高位，按位相加，有益处则向高位进1(和一般的二进制法则一样),若最高位有进位，则向最低位若最高位有进位，则向最低位进