1、计算机网络第 3 章 数据链路层第3章 数据链路层n3.1 数据链路层概述n3.2 帧同步功能n3.3 流量控制功能n3.4 差错检测（重点）3.1 数据链路层概述n数据链路层是OSI参考模型中的第二层,介乎于物理层和网络层之间，在物理层所提供的服务的基础上向网络层提供服务。数据链路层的作用是对物理层传输原始比特流的功能的加强，将物理层提供的可能出错的物理连接改造成为逻辑上无差错的数据链路，即使之对网络层表现为一条无差错的链路。n数据链路层在相邻结点的物理连接上为网络层建立、维持、释放链路连接，并在链路连接上可靠地、正确地传送链路层协议数据单元(通常称为帧-Frame)数据链路层的简单模型局域
2、网广域网主机 H1主机 H2路由器 R1路由器 R2路由器 R3电话网局域网主机 H1 向 H2 发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2从层次上来看数据的流动数据链路层的简单模型(续）局域网广域网主机 H1主机 H2路由器 R1路由器 R2路由器 R3电话网局域网主机 H1 向 H2 发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2仅从数据链路层观察帧的流动3.1 使用点对点信道的数据链路层3.1.
3、1 数据链路和帧 n链路(link)是一条无源的点到点的物理线路段，中间没有任何其他的交换结点。n一条链路只是一条通路的一个组成部分。n数据链路(data link)除了物理线路外，还必须有通信协议来控制这些数据的传输。若把实现这些协议的硬件和软件加到链路上，就构成了数据链路。n现在最常用的方法是使用适配器（即网卡）来实现这些协议的硬件和软件。n一般的适配器都包括了数据链路层和物理层这两层的功能。IP 数据报1010 0110帧取出数据链路层网络层链路结点 A结点 B物理层数据链路层结点 A结点 B帧(a)(b)发送帧接收链路IP 数据报1010 0110帧装入数据链路层传送的是帧3.1.2
4、三个基本问题(1)封装成帧(2)透明传输(3)差错控制 3.2 帧同步功能n为了使传输中发生差错后只将出错的有限数据进行重发，数据链路层将比特流组织成以帧为单位传送。n帧的组织结构必须设计成使接收方能够明确的从物理层收到的比特流中区分出帧的起始与终止，这就是帧同步要解决的问题。n同步的方法n字符填充的首尾定界符法n比特填充的首尾定界符法1.封装成帧n封装成帧(framing)就是在一段数据的前后分别添加首部和尾部，然后就构成了一个帧。确定帧的界限。n首部和尾部的一个重要作用就是进行帧定界。帧结束帧首部IP 数据报帧的数据部分帧尾部 MTU数据链路层的帧长开始发送帧开始用控制字符进行帧定界的方法
5、举例 SOH装在帧中的数据部分帧帧开始符帧结束符发送在前EOT2.透明传输SOHEOT出现了“EOT”被接收端当作无效帧而丢弃被接收端误认为是一个帧数据部分EOT完整的帧发送在前解决透明传输问题n发送端的数据链路层在数据中出现控制字符“SOH”或“EOT”的前面插入一个转义字符“ESC”(其十六进制编码是 1B)。n字节填充(byte stuffing)或字符填充(character stuffing)接收端的数据链路层在将数据送往网络层之前删除插入的转义字符。n如果转义字符也出现数据当中，那么应在转义字符前面插入一个转义字符。当接收端收到连续的两个转义字符时，就删除其中前面的一个。SOHSO
6、HEOTSOHESCESCEOTESCSOHESCESCESCSOH原始数据EOTEOT经过字节填充后发送的数据字节填充字节填充字节填充字节填充发送在前帧开始符帧结束符用字节填充法解决透明传输的问题 SOH3.2.2 比特填充的首尾定界符法n在前面介绍的字符分界法中存在一个大的不足，那就是它仅依靠8位模式。而事实上，并不是所有的字符编码都使用8位模式，如UNICODE编码就使用了16位编码方式。n“比特填充的首尾界定符法”是以一组特定的比特模式（如01111110）来标志一帧的起始与终止，它允许任意长度的位码，也允许任意每个字符有任意长度的位。透明传输 n发送端：n若发现要发送的数据中有 5
7、个连续 1，则立即填入一个 0。n接收端：n对帧中的数据比特流进行扫描。每当发现 5 个连续1时，就把这 5 个连续 1 后的一个 0 删除。0 1 0 0 1 1 1 1 1 0 1 0 0 0 1 0 1 00 1 0 0 1 1 1 1 1 1 0 0 0 1 0 1 00 1 0 0 1 1 1 1 1 0 1 0 0 0 1 0 1 0信息字段中出现了和标志字段 F 完全一样的 8 比特组合发送端在 5 个连续 1 之后填入 0 比特再发送出去在接收端把 5 个连 续1之后的 0 比特删除会被误认为是标志字段 F 发送端填入 0 比特接收端删除填入的 0 比特零比特填充例题：nPPP
8、协议使用同步传输技术传送比特串0110111111111100。试问经过零比特填充后变成怎样的比特串?n若接收端收到的PPP帧的数据部分是0001110111110111110110，问删除发送端加入的零比特后变成怎样的比特串?n答案：（1）011011111011111000 （2）000111011111-11111-1103.3 流量控制功能(传输层TCP来讲)n流量控制是指一组过程n限制发送方在等待确认前能够发送的数据量n保证发送实体发送的数据不超出接收实体接收数据的能力n防止缓冲溢出？发送方：发送方：？接收方：接收方：？传输过程：传输过程：！解决这些问题，是链路层的主要任务。解决这些
9、问题，是链路层的主要任务。！针对这些问题所制定的通信规程就是数据链路层的通信协议。针对这些问题所制定的通信规程就是数据链路层的通信协议。以多快的速度发送数据帧，即每帧之间相隔多长时间？以多快的速度发送数据帧，即每帧之间相隔多长时间？如何确认对方是否收到数据？如何确认对方是否收到数据？是否接收到正确的数据帧？如何告诉发送方？是否接收到正确的数据帧？如何告诉发送方？能及时处理接收到的数据帧吗？能及时处理接收到的数据帧吗？在数据链路层上传输数据帧会出错吗？会丢失数据帧吗？会出错吗？会丢失数据帧吗？数据链路层功能数据链路层功能3.3.1 完全理想化的数据传输数据链路层主机 A缓存主机 B数据链路AP2
10、AP1缓存发送方接收方帧高层帧完全理想化的数据传输所基于的两个前提n1：链路是理想的传输信道，所传送的任何数据既不会出差错也不会丢失。n2：不管发方以多快的速率发送数据，收方总是来得及收下，并及时上交主机。具有简单的流量控制具有简单的流量控制DATA0DATA0ACKACKACKACKACKACKDATA2DATA2DATA1DATA1假设：假设：链路是理想化的，所传输的数据不会出错也不会丢失。链路是理想化的，所传输的数据不会出错也不会丢失。协协议议算算法法协议思想：协议思想：协调、控制接收方、发送方的速度。协调、控制接收方、发送方的速度。等待；等待；将收到的数据帧将收到的数据帧上交主机；上交
11、主机；发送应答信息；发送应答信息；转到第一步转到第一步发出一帧；发出一帧；等待；等待；直到收到直到收到ACKACK才发送下一帧才发送下一帧发送方发送方接收方接收方2 停止等待协议两种情况的对比（传输均无差错）ABDATADATADATADATA送主机 B送主机 B送主机 B送主机 BABDATA送主机 BDATA送主机 B时间不需要流量控制需要流量控制实用的停止等待协议时间ABDATA0送主机ACKDATA1送主机ACK(a)正常情况ABDATA0DATA0送主机ACK(c)数据帧丢失重传tout丢失！ABDATA0送主机ACKDATA0丢弃ACK(d)确认帧丢失重传tout丢失！ABDATA
12、0NAKDATA0送主机ACK(b)数据帧出错重传出错四种情况超时计时器的作用n结点A发送完一个数据帧时，就启动一个超时计时器(timeout timer)。n计时器又称为定时器。n若到了超时计时器所设置的重传时间 tout而仍收不到结点 B 的任何确认帧，则结点 A 就重传前面所发送的这一数据帧。n一般可将重传时间选为略大于“从发完数据帧到收到确认帧所需的平均时间”。解决重复帧的问题 n使每一个数据帧带上不同的发送序号。每发送一个新的数据帧就把它的发送序号加 1。n若结点 B 收到发送序号相同的数据帧，就表明出现了重复帧。这时应丢弃重复帧，因为已经收到过同样的数据帧并且也交给了主机 B。n但
13、此时结点 B 还必须向 A 发送确认帧 ACK，因为 B 已经知道 A 还没有收到上一次发过去的确认帧 ACK。帧的编号问题 n任何一个编号系统的序号所占用的比特数一定是有限的。因此，经过一段时间后，发送序号就会重复。n序号占用的比特数越少，数据传输的额外开销就越小。n对于停止等待协议，由于每发送一个数据帧就停止等待，因此用一个比特来编号就够了。n一个比特可表示 0 和 1 两种不同的序号。帧的发送序号 n数据帧中的发送序号 N(S)以 0 和 1 交替的方式出现在数据帧中。n每发一个新的数据帧，发送序号就和上次发送的不一样。用这样的方法就可以使收方能够区分开新的数据帧和重传的数据帧了。停止等
14、待协议的算法n这里不使用否认帧（实用的数据链路层协议大都是这样的），而且确认帧带有序号 n。n按照习惯的表示法，ACKn 表示“第 n 1 号帧已经收到，现在期望接收第 n 号帧”。nACK1 表示“0 号帧已收到，现在期望接收的下一帧是 1 号帧”；nACK0 表示“1 号帧已收到，现在期望接收的下一帧是 0 号帧”。停止等待协议的要点n连续出现相同发送序号的数据帧，表明发送端进行了超时重传。连续出现相同序号的确认帧，表明接收端收到了重复帧。n发送端在发送完数据帧时，必须在其发送缓存中暂时保留这个数据帧的副本。这样才能在出差错时进行重传。只有确认对方已经收到这个数据帧时，才可以清除这个副本。
15、停止等待协议的要点n实用的 CRC 检验器都是用硬件完成的。nCRC 检验器能够自动丢弃检测到的出错帧。因此所谓的“丢弃出错帧”，对上层软件或用户来说都是感觉不到的。n发送端对出错的数据帧进行重传是自动进行的，因而这种差错控制体制常简称为 ARQ(Automatic Repeat reQuest)，直译是自动重传请求，但意思是自动请求重传。停止等待协议的定量分析n设 tf 是一个数据帧的发送时间，且数据帧的长度是固定不变的。显然，数据帧的发送时间 tf 是数据帧的长度 lf(bit)与数据的发送速率 C(bit/s)之比，即 tf=lf/C=lf/C(s)（3-1）n发送时间 tf 也就是数据
16、帧的发送时延。n数据帧沿链路传到结点B还要经历一个传播时延 tp。n结点 B 收到数据帧要花费时间进行处理，此时间称为处理时间 tpr，发送确认帧 ACK 的发送时间为 ta。停止等待协议中数据帧和确认帧的发送时间关系 ABDATADATAACK传播时延 tp处理时间 tpr确认帧发送时间 ta传播时延 tp处理时间 tprtT时间两个成功发送的数据帧之间的最小时间间隔数据帧的发送时间tf设置的重传时间tout重传时间 n重传时间的作用是：数据帧发送完毕后若经过了这样长的时间还没有收到确认帧，就重传这个数据帧。n为方便起见，我们设重传时间为 tout=tp+tpr+ta+tp+tpr n设上式
17、右端的处理时间 tpr 和确认帧的发送时间 ta 都远小于传播时延 tp，因此可将重传时间取为两倍的传播时延，即 tout=2tpn两个发送成功的数据帧之间的最小时间间隔是 tT=tf+tout=tf +2tp停止等待协议 ARQ 的优缺点 n优点：比较简单。n缺点：通信信道的利用率不高，也就是说，信道还远远没有被数据比特填满。n为了克服这一缺点，就产生了另外两种协议，即连续 ARQ 和选择重传 ARQ。这将在后面进一步讨论。n例：信道的数据传输速率为例：信道的数据传输速率为4Kbps,传播传播延迟时间延迟时间20ms（未注明往返则指单程）（未注明往返则指单程），求帧长在什么范围内才使停等协议
18、的信，求帧长在什么范围内才使停等协议的信道利用率达到道利用率达到50%以上。（以上。（注：信道利用注：信道利用率：指信道用于发送数据帧的时间在所有率：指信道用于发送数据帧的时间在所有信道占用时间中的百分比信道占用时间中的百分比）解析：已知信道的数据传输速率B=4kbps=4000bps，信道的单向传播时延R=20ms=0.02s，一帧的帧长为L。在停止等待协议中，协议忙的时间为数据发送的时间=L/B，协议空闲的时间为数据发送后等待确认帧返回的时间=2R。则要使停止等待协议的效率至少为50%，即要求信道利用率至少为50%。因为信道利用率数据发送时延/（传播时延数据发送时延），则有：L/B/(L/
19、B2R)50%可得，L2BR=240000.02=160(b)因此，当帧长大于等于160比特时，停止等待协议的效率至少为50%。3 连续 ARQ 协议n在发送完一个数据帧后，不是停下来等待确认帧，而是可以连续再发送若干个数据帧。n如果这时收到了接收端发来的确认帧，那么还可以接着发送数据帧。n由于减少了等待时间，整个通信的吞吐量就提高了。连续 ARQ 协议的工作原理 DATA0DATA1DATA2DATA3DATA4DATA5重传 DATA2重传 DATA3ACK1ACK2ACK1 确认 DATA0ACK2 确认 DATA1DATA2 出错，丢弃DATA3 不按序，丢弃，重传 ACK2DATA4
20、 不按序，丢弃，重传 ACK2DATA5 不按序，丢弃，重传 ACK2ACK3ACK3 确认 DATA2ACK4 确认 DATA3ACK4重传 DATA5重传 DATA4超时重传时间ABtout送交主机送交主机?ACK2ACK2ACK2需要注意：(1)接收端只按序接收数据帧。虽然在有差错的 2号帧之后接着又收到了正确的 3 个数据帧，但接收端都必须将这些帧丢弃，因为在这些帧前面有一个 2 号帧还没有收到。虽然丢弃了这些不按序的无差错帧，但应重复发送已发送过的最后一个确认帧（防止确认帧丢失）。(2)ACK1 表示确认 0 号帧 DATA0，并期望下次收到 1 号帧；ACK2 表示确认 1 号帧
21、DATA1，并期望下次收到 2 号帧。依此类推。需要注意：(3)结点 A 在每发送完一个数据帧时都要设置该帧的超时计时器。如果在所设置的超时时间内收到确认帧，就立即将超时计时器清零。但若在所设置的超时时间到了而未收到确认帧，就要重传相应的数据帧（仍需重新设置超时计时器）。在等不到 2 号帧的确认而重传 2 号数据帧时，虽然结点 A 已经发完了 5 号帧，但仍必须向回走，将 2号帧及其以后的各帧全部进行重传。连续 ARQ 又称为Go-back-N ARQ，意思是当出现差错必须重传时，要向回走 N 个帧，然后再开始重传。4 4 选择重传选择重传ARQARQ协议协议 GO-BACK-NGO-BACK
22、-N可能将已正确传送到目的方的帧再重传一遍，这显然是一可能将已正确传送到目的方的帧再重传一遍，这显然是一种浪费。另一种效率更高的策略是当接收方发现某帧出错后，其后继续送种浪费。另一种效率更高的策略是当接收方发现某帧出错后，其后继续送来的正确的帧虽然不能立即递交给接收方的高层，但接收方仍可收下来，来的正确的帧虽然不能立即递交给接收方的高层，但接收方仍可收下来，存放在缓冲区中，同时要求发送方重新传送出错的那一帧。一旦收到重新存放在缓冲区中，同时要求发送方重新传送出错的那一帧。一旦收到重新传来的帧后，就可以和已存于缓冲区中的其余帧一并按正确的顺序递交高传来的帧后，就可以和已存于缓冲区中的其余帧一并按
23、正确的顺序递交高层。这种方法称为选择重发，其工作过程如图所示。图中层。这种方法称为选择重发，其工作过程如图所示。图中2 2号帧的否认返回号帧的否认返回信息信息NAK2NAK2要求发送方选择重发要求发送方选择重发2 2号帧。显然，选择重发减少了浪费，但要求号帧。显然，选择重发减少了浪费，但要求接收方有足够大的缓冲区空间。接收方有足够大的缓冲区空间。选择重发选择重发ARQ原理示意原理示意5 滑动窗口协议 在使用连续ARQ协议时，在没收到应答时，实际上不能无限制的发送数据。因为：1、重传太多会花费较多的时间，增大开销；2、发送序号也占用比特数。因此应对已发送出去而未被确认的数据帧的数因此应对已发送出
24、去而未被确认的数据帧的数目加以限制，这就是滑动窗口所要研究的内容。目加以限制，这就是滑动窗口所要研究的内容。滑动窗口的概念n发送端和接收端分别设定发送窗口和接收窗口。n发送窗口用来对发送端进行流量控制。n发送窗口的大小 WT 代表在还没有收到对方确认信息的情况下发送端最多可以发送多少个数据帧。01234567012发送窗口WT不允许发送这些帧允许发送 5 个帧(a)01234567012不允许发送这些帧还允许发送 4 个帧WT已发送(b)01234567012不允许发送这些帧WT已发送(c)01234567012不允许发送这些帧还允许发送 3 个帧WT已发送 已发送并已收到确认(d)接收端设置
25、接收窗口 n在接收端只有当收到的数据帧的发送序号落入接收窗口内才允许将该数据帧收下。n若接收到的数据帧落在接收窗口之外，则一律将其丢弃。n在连续 ARQ 协议中，接收窗口的大小 WR=1。n只有当收到的帧的序号与接收窗口一致时才能接收该帧。否则，就丢弃它。n每收到一个序号正确的帧，接收窗口就向前（即向右方）滑动一个帧的位置。同时发送对该帧的确认。不允许接收这些帧01234567012WR准备接收 0 号帧(a)不允许接收这些帧01234567012WR准备接收 1 号帧已收到(b)不允许接收这些帧01234567012WR准备接收 4 号帧已收到(c)滑动窗口的重要特性n只有在接收窗口向前滑动
26、时（与此同时也发送了确认），发送窗口才有可能向前滑动。n收发两端的窗口按照以上规律不断地向前滑动，因此这种协议又称为滑动窗口协议。n当发送窗口和接收窗口的大小都等于 1时，就是停止等待协议。发送窗口的最大值 n当用 n 个比特进行编号时，若接收窗口的大小为 1，则只有在发送窗口的大小 WT 2n 1时，连续 ARQ 协议才能正确运行。n例如，当采用 3 bit 编码时，发送窗口的最大值是 7 而不是 8。n后退 N帧ARQ协议，发送窗口不能大于2k1，接收窗口大小为1 说明：假定帧编号字段为3位长，发送窗口尺寸为8(显然不能大于8)。当发送器收到一个单独的ACK1后（这意味接收器期望接收第1帧
27、及其之后的帧），把窗口推进到后沿为1，前沿为0的位置，即发送窗口现在包含的帧号为l、2、3、4、5、6、7和0。如果这时又收到一个捎带回的ACK1，发送器如何动作呢？这后一个ACK1可能表示窗口中的所有帧都未曾接收，也可能意味着窗口中的帧都已正确接收。然而，如果规定窗口的大小为7，则就可以避免这种二义性 n选择重发ARQ协议 W发=W收2k1若假设帧编号为3位，发送和接收窗口大小都是7，考虑下面的情况；(1)发送窗口和接收窗口中的帧编号都是0到6；(2)发送站发出0到6号帧，但尚未得到肯定应答，窗口不能向前滑动；(3)接收站正确地接收了0至6号帧，发出了肯定应答ACK7（注意，这个应答信号表示
28、0至6号帧已收到，下面期望收到7号及其以后的帧），因而接收窗口向前滑动，新的窗口中的帧编号为7、0、1、2、3、4和5；(4)ACK7丢失，发送站定时器超时，重发0号帧；(5)接收站收到0号帧并看到该帧编号落在接收窗口内，以为是新的0号帧而保存起来。认为7号帧丢失了（其实发送站从未发出过），并继续接收重复发来的1、2、3、4和5号帧。3.4差错控制功能1、差错的特性 n通信信道中的噪声主要有热噪声和冲击噪声：n热噪声，是由传输媒体的电子热运动产生的，这类噪声主要是信道中存在的随机噪声（白噪声）引起的随机性差错；特点是随机存在，幅度小，与频率无关，而且是单个码元出现差错，码元间互不影响。n冲击噪
29、声，是由外界电磁干扰引起的，这类噪声主要是信道中的脉冲干扰、信号衰落和瞬时中断等因素造成的突发性差错；特点是幅度大，持续时间长，而且是成批码元突发性错误，前后码元的差错具有一定的相关性。虽然可以采用屏蔽、改善线路质量、选择有效的编码方式等措施来减少噪声，但还不能完全消除噪声的影响。也就是说，在传输数据时，或多或少总会出现差错。通常，使用误码率Pe来衡量信道的传输质量，即：错误接收的码元数接收的总码元数Pe=n为了减少传输差错，通常采用以下两种方法：（1）改善线路质量。加强线路本身的抗干扰能力，是减少差错最根本的途径。例如，现在的网络系统中越来越多地使用光纤传输系统，其误码率已低于109，这就从
30、根本上提高了信道的传输质量。但是，这种改善是以较大的投入为代价的。（2）差错的检测与纠正。这是一种主动式的差错控制措施。它的主要思想是：对所传输的数据进行抗干扰编码，并以此来检测和校正传输中的错误。2、差错控制编码n信号在物理信道中传输时，会造成信号的失真。在数据通信中，将会使接收端收到的二进制数位和发送端实际发送的二进制数位不一致，从而造成由“0”变成“1”或由“1”变成“0”的差错。n差错控制就是指在通信过程中，发现、检测错误，对差错进行纠正。最常用的差错控制方法是差错控制编码 n最简单的差错控制方法是将每一个数据发送两遍。接收方将这两遍数据比较如有不同，即可认定出错了。这样做将使传输速率
31、大大下降，数据本身传输时间要加倍，且逐位比较也要花费大量时间。差错控制最常用的技术是在每个数据单元中加入一些称为“冗余码”的附加数位(差错控制编码)。这种技术之所以被称为“冗余校验技术”,因为一旦传输被确认无误，那些附加的冗余数位便被自动丢弃。发送的码字=信息位+冗余位 （输入密码或告诉对方电话号码两遍，第二遍给出的即为“冗余位”）信息位信息位要发送的数据 冗余位冗余位差错控制编码差错的控制编码n差错控制编码可分为检错码和纠错码。检错码能自动发现差错的编码；不能纠正错误纠错码不仅能发现差错而且能自动纠正差错的编码 差错的控制方法n差错控制方法分两类，一类是自动请求自动请求重发重发ARQARQ，
32、另一类是前向纠错前向纠错FECFEC n自动请求重发自动请求重发ARQARQ，当接收端发现差错时，就设法通知发送端重发，直到收到正确的码字为止。ARQ方式只使用检错码 n前向纠错前向纠错FECFEC，接收端不但能发现差错，而且能确定二进制码元发生错误的位置，从而加以纠正。循环冗余校验(CRC)Cyclic Redundancy Checkn在数据链路层传送的帧中，广泛使用了循环冗余检验 CRC 的检错技术。CRC基于二进制除法n在CRC中，在数据单元（比如一个字节）的后面附加一个称为“循环冗余码循环冗余码”或“CRC余数余数”的冗余数位串，使该数据单元可被另一个预先给定的二进制数完全除尽。n接
33、收端将所接收的数据单元用同样的二进制数相除，如果无余数，则可认为所接收的数据单元正确无误，如果有余数，则认定该数据单元已有差错。循环冗余校验码循环冗余校验码 循环冗余校验编码是通过多项式除法检测错循环冗余校验编码是通过多项式除法检测错误的。方法是将待传输的数据位串看成系数误的。方法是将待传输的数据位串看成系数为为0 0或或1 1的多项式，如位串的多项式，如位串1001110011可表示为可表示为f(x)=xf(x)=x4+x+1.+x+1.发送前收发双方约定一个生成多发送前收发双方约定一个生成多项式项式G(x)(G(x)(其最高阶和最低阶系数必为其最高阶和最低阶系数必为1)1)，发，发送方在数
34、据位串的末尾加上校验和，使带校送方在数据位串的末尾加上校验和，使带校验和的位串多项式能被验和的位串多项式能被G(x)G(x)整除。接收方收整除。接收方收到后用到后用G(x)G(x)除多项式，若有余数，则传输有除多项式，若有余数，则传输有错错n1、若G(x)为r阶，原始数据为m位，其多项式为M(x)，则在原始数据后面添加r个0，实际传输数据为m+r位，相应多项式为xrM(x)。n2、按模2除法用对应于G(x)的位串去除对应于xrM(x)的位串。n3、按模2加法把xrM(x)的位串与余数相加，结果就是要传送的带校验和的数据多项式T(x)。例1 取生成多项式h（X）X4+X+1，假设欲发送的一段信息
35、101100110，问在线路上传输的码字是？解：由h(X)X4+X+1得 生成的码字为：10011，n为4n在101100110后面添加n（此时n=4）个0，得到1011001100000。n 用1011001100000去除10011，得到余数为1000（保持n位，若不够前面用0补上）n把余数1000添加到要发送的数据101100110的后面，就是实际要传送的码字，为：1011001101000 10101100010011 1011001100000 10011 10101 10011 11010 10011 10010 10011 1000例3.已知：接收码字:1100111001，生成
36、多项式:h(X)=X4+X3+1(r=4)求：码字的正确性。若正确，则指出冗余码和信息码。解：1)用接收到的码字除以生成码，余数为0，所以码字正确。2)因r=4，所以冗余码是：1001，信息码是:110011 n例4.要发送的数据为1101。采用CRC的生成多项式是P(x)=x2+1。试求应添加在数据后面的余数。数据在传输过程中要发送的数据1101变成1100，问接收端能否发现？能否发现那几位发生错误？若数据在传输过程中要发送的数据1101变成1000，问接收端能否发现？能否发现那几位发生错误？n答：（1）添加的检验序列为10（1101除以101）n（2）数据在传输过程中要发送的数据1101变
37、成1100，110010除以101，余数为01，不为0，接收端可以发现差错。n（3）若数据在传输过程中要发送的数据1101变成1000，100010除以101，余数为0，接收端不能发现差错。检错及纠错原理n信源产生的信息码一般是由0、1序列表示的，其中0或1称为码元。n假定在一码组中任一码字均是由n个码元组成的，则码组个数N2n构成了一个全码集，若将全码集中所有码组用来代表信息编码，就不具有抗干扰的能力。n为了更好地说明，假设由3个码元组成8（23）个码组的全码集，3位二进制码元共有8种可能的组合：000、001、010、011、100、101、110、111。如果这8种码组都可传递消息，若在
38、传输过程中发生一个误码，则一种码组会错误地变成另一种码组。由于每一种码组都可能出现，没有多余的信息量，因此接收端不可能发现错误，认为发送的就是另一种码组。n如果选其中000、011、101、110来传送消息，这相当于只传递00、01、10、11四种信息，而第3位是监督位。保证码组中“1”码的个数为偶数。这4种码组称为许用码组。另外4种码组不满足这种校验关系，称为禁用码组，它们在编码后的发送码元中不会出现。n接收时一旦发现有禁用码组，就表明传输过程中发生了错误。用这种简单的校验关系可以发现1个或3个错误，但不能纠正错误。因为当接收到的码组为禁用码组时，比如为010，无法判断发送的是哪个码组。虽然
39、原发送码组为101的可能性很小(因为3个误码的概率一般很小)，但不能绝对排除，即使传输过程中只发生一个误码，也有三种可能的发送码组即000、011和110。n假如进一步将许用码组限制为二种即000和111，显然这样可以发现所有2位以下的误码，若用来纠错，可以用最大似然准则纠正1位错误。n一个编码系统中任意两个两个码组中对应码位上具有不同二进制码元的位数为两码组的距离，称为汉明(Hamming)距，简称码距。在前面3位二进制码组的例子中，当8种码组均为许用码组时，两码组间的最小距离为1，称这种编码的最小码距为1，一般记为dmin=1；当选4种码组为许用码组时，最小码距dmin=2；当用2种码组作
40、为许用码组时，dmin=3。n对于分组码一般有以下结论:n在一个码组内检测e个误码，要求最小码距 dmin e+1(3-9)n在一个码组内纠正t个误码，要求最小码距 dmin 2t+1(3-10)n在一个码组内纠正t个误码，同时检测e(et)个误码，要求最小码距 dmin t+e+1（3-11）差错纠正Error Detection差错纠正的基本技术自自动动请请求求重重发发(ARQ,Automatic Repeat Request）自动发现差错并要求对方重发正正向向纠纠错错(FEC,Forward Error Correction）自动发现并纠正错误ARQ只需检错码，编码效率高，设备简单，但要
41、求双向信道，发送方要有数据缓冲区。FEC要用纠错码，编码效率低，设备复杂，但实时性好，只需单向信道。数数据据通通信信中中使使用用更更多多的的还还是是A AR RQQ差差错错控控制制方方式。式。F FE ECC常常用用于于没没有有反反向向信信道道发发送送请请求求重重发发信信息息（如如单单工工传传输）输）或或重重发发不不经经济济的的场场合合（如如卫卫星星传传输）输）。n理论上，自动纠正每一个二进制代码的传输差错是可以做到的。但纠错码比检错码复杂得多，而且需要更多的冗余位。用于多位或突发差错纠错的位数太大的，以致大部分情况下，将使编码效率低到不可接受的程度。为此，大部分纠错码只限于处理1位、2位或3
42、位差错。n在数据通信中，最常用的纠错码是所谓“汉明码”(Hamming Code），是贝尔实验室的科学家R.W.Hamming 于1950年提出的，主要用来纠正1位差错。纠错码Error-correcting Code1位差错的纠错Single-bit Error Correctionn奇偶校验可以检测出1位差错的情况，方法是加上一个冗余的奇校验位或偶校验位。纠错则需确定其中哪位有差错。n如果要确定一个ASCII字符（7位）中的某位差错，此时需要区别8种情况：没差错，第1位错，第2位错，第7位错。于是，需要3个冗余位来表示8种不同的状态（000-111）。n实际上，3位冗余是不够的。因为，冗余
43、位本身也可能出现差错！纠错码Error Correction冗余位Redundancy Bitsn如何计算为m位数据纠错时所需的冗余位数 r 呢?n此时数据传输的总位数是m+r，且要求 r必须能够至少表示 m+r+1 种状态。其中，一种状态表示无差错，m+r 种状态分别表示在 m+r 位每个位置上发生的差错。n由于r 位二进制数可以表示2r种不同的状态,所以，2r必须大于或等于 m+r+1。2 r m+r+1 如果m=7（ASCII代码），则能满足上式的最小 r 值是4。因为：24 7+4+1数据位数数据位数 m 与冗余位数与冗余位数 r 的关系的关系 下表为一些可能的 m 值及其对应的 r
44、值。纠错原理n冗余位的定位冗余位的定位 汉明码可用于任何长度的数据块，并利用了上面讨论的数据位数和冗余位数的关系。例如，一个7位ASCII码要求4个冗余位，它们可以附加在数据位的后面，亦可散布在数据位之中。下图中，各冗余位处于第1、2、4、8位（2的n次方处），分别用r1，r2，r4，r8表示。确定冗余位的位置n在汉明码中，每一个r位都是一组数据位的奇偶校验码。用于计算7数据位4个r值（奇偶校验码）的方案是：r1:第 1，3，5，7，9，11 位 r2:第 2，3，6，7，10，11 位 r3:第 4，5，6，7 位 r4:第 8，9，10，11 位r1和r2值的计算r4和r8值的计算 纠错码
45、的计算为了搞清楚这种技术后面的窍门，不妨看看每一数位的位置号（用二进制表示）。r1位使用的是所有位置号右侧为1开头的数位。r2使用的是所有位置号第2位为1的数位，以此类推。示例：各r位值的计算假设使用偶校验。假设上述数据发送后，接收端收到的:10010100101（第7位差错）。此时接收端取出接收结果，并使用与发送端相同的方法计算出一组新的奇偶校验码。然后将这些奇偶校验码按r的顺序（r8,r4,r2,r1）组成一个二进制数。本例中，组成的二进制数是0111（十进制数7），这就是准确的差错位置。一旦找出差错位，接收端即可将该位的值反转，以纠正差错。检错与纠错1确定校验关系n假设要传输的信息位k=
46、4，要构造海明码,必须满足上述不等式2rm+r+1，则有r3,n将每个信息位的位置写成用2的幂次之和的形式，即 7=22+21+20 6=22+21 5=22+20 3=21+20n从上式可得，I4要参与r2,r1和r0的生成，I3参与r2和r1的生成，I2参与r2,r0的生成，I1参与r1和r0的生成。即r2和I4，I3，I2构成偶校验；r1和I4，I3，I1构成偶校验；r0和I4，I2，I1构成校验；于是有以下公式：r2=I4+I3+I2r1=I4+I3+I1r0=I4+I2+I1于是，接收端使用以下关系式对这三个偶校验关系进行验证：s2=r2+I4+I3+I2 s1=r1+I4+I3+I
47、1 s0=r0+I4+I2+I1n其中s2，s1，s0称为校正因子。n若没有错，三个校正因子都为0，若不全为0，则有错误发生，错误的位置在S=s2s1s0处，将该位取反即得到正确的数据。3.6 数据链路层协议3.6 因特网的点对点协议 PPP3.6.1 PPP 协议的工作原理n现在全世界使用得最多的数据链路层协议是点对点协议 PPP(Point-to-Point Protocol)。n用户使用拨号电话线接入因特网时，一般都是使用 PPP 协议。用户拨号入网的示意图 路由器调制解调器调制解调器因特网服务提供者(ISP)用户家庭拨号电话线 使用 TCP/IP 的 PPP 连接使用 TCP/IP 的
48、 客户进程路由选择 进程至因特网PC 机n一个发送方、一个接收方、一段链路：比广播链路容易处理:n无媒体访问控制n不需要明确的MAC编址n如：拨号链路、ISDN链路n PPP(Point to point protocol),提供了一种提供了一种在点对点的链路上封装在点对点的链路上封装多协议数据报多协议数据报（IPIP、IPXIPX和和AppleTalkAppleTalk）的标准方法。）的标准方法。协议常用于家庭用户与ISP通过拨号建立连接 时使用的数据链路层协议。PPPPPP协议介绍协议介绍 PPP PPP协议的功能协议的功能n能够控制数据链路的建立；n允许多个PPP物理连接绑定在一起作为一
49、条单独的逻辑连接。n支持多种网络层协议(IP、IPX 和AppleTalk)AppleTalk)；n可运行在多种类型的链路上（串行/并行，同 步/异步n能够有效进行错误检测（CRC）；n支持验证（PAP,CHAP）n有协商选项，能够对网络层的地址和数据压缩 等进行协商。PPP 协议 n1992 年制订了 PPP 协议。经过 1993 年和 1994 年的修订，现在的 PPP 协议已成为因特网的正式标准RFC 1661。nPPP协议有三个组成部分 n一个将 IP 数据报封装到串行链路的方法。n链路控制协议 LCP(Link Control Protocol)。n网络控制协议 NCP(Networ
50、k Control Protocol)。3.6.2 PPP 3.6.2 PPP协议的组成协议的组成 nPPPPPP协议有三个组成部分：协议有三个组成部分：n帧格式和成帧：将 IP 数据报封装到串行链路的方法。n链路控制协议 LCP(Link Control Protocol):用于建立,配置,测试链路。n网络控制协议 NCP(Network Control Protocol):用于建立和配置网络层协议,IPCP。（1）PPP 协议的帧格式n标志字段 F 仍为 0 x7E（符号“0 x”表示后面的字符是用十六进制表示。十六进制的 7E 的二进制表示是 01111110）。n地址字段 A 只置为
