《计算机网络》第三章

1、ATy *第三章数据链路层数据链路层的功能物理层只负责在通过传输介质相连的机器之间传输无结构的原始比特流， 是不可 靠的。数据链路层将相邻节点间不可靠的物理连接的数据电路转换成为可靠的数据链 路，为网络层提供透明的服务。为实现转换：-将物理层的无结构原始比特流划分成一定长度的结构数据单元一一帧(frame)，即组帧 (Framing )。-对帧进行差错控制(error control)，实现检错/纠错功能。-通过合适的流量控制(flow control )协议保证收发双方的传输同步。§ 3.1 数据链路层设计问题3种基本的服务：无确认的无连接服务：-源机器向目的机器发送独立的帧，而目

2、的机器不需作出确认。事先没有建 立连接，事后也不存在释放。对于丢失和错误的帧也不试图去恢复。恢复 工作留给上层完成。-适用于误码率很低或音视频实时传输的情况，如LAN有确认的无连接服务：-仍然不建立连接，但每一个帧都单独确认。发送方会重发丢失和出错的帧。-适用于象无线系统(wireless systems )之类的不可靠信道。 有确认的面向连接服务：-传输分为建立、传输和拆除三个阶段，且每一个帧都单独确认。主要用于WAN。§ 3.2 组帧将物理层的比特流划分成帧的 4种方法：-字符计数法(Character Count )-带字符填充的首位定界符法( Starting and end

3、ing characters with character stuffing )-带位填充的首位标志法( Starting and ending flags with bit stuffing-物理编码的违例码法(Physical layer coding violations)§3.3 差错的检测和纠正 涉及两方面理论与技术： 差错检测-差错控制编码差错纠正-前项纠错-重发出错帧(可与流量控制一起实现)差错控制编码发送端在发送的数据块中加入一定的冗余信息， 使数据块与冗余信息之间建立某 种关联的关系，接收端通过验证这种关系是否存在，来判定数据在传输过程中是 否出错。在数据块中加入冗

4、余信息的过程叫差错编码，有两种基本的差错编码策略：-检错码(error-detecti ngcode):只能检查是否有错，但不知错在何处的编码。-纠错码(error-correcting code ):不但能检查出错误，且能确定错误之处 并予以纠正的编码。任何一种差错编码都不能保证百分之百的准确。奇偶校验( Parity Check )在数据后面增加一个奇偶校验位( parity bit )的编码，奇偶校验位的选取原则 是使码字内的 1的数目为偶数(偶校验)或奇数(奇校验)。如: 10110101变为 101101011(偶校验)或 101101010(奇校验)。这种编码可检测单比特错，其海明

5、距离为 2。海明码( Hamming)海明码由海明于 1950年提出，是一种可纠正单比特错的编码。通过在特定的位置(2k, k?Y0£?1£?£?£8£?6)加入与某些特定数据信息位相关的奇偶校验位就构成了海明码。每位数据信息位可用2k的和来表示（如11=20+21+23），则该数据信息位是由展开式中的奇偶校验位（ 2k ）位来校验的， 如第11位的数据信息位分别由 1，2，8位进行校验。海明码的纠错接收方设置一计数器清零。检查所有的奇偶校验位（ 2k，k?Y0）。若校验出错，则将出错的奇偶校验位号加进计数器。全部检查完后，若计数器为 0，则表

6、示没有错误；若不为 0，则计数器中的值就是 出错的位号，对该位求反即纠正了错误。CR检错码CRC（ Cyclic Redundancy Code ，循环冗余码，也叫多项式编码）是一种高性能 的检错编码。将位串中每一位二进制数看成是一个一元多项式的系数，则一个k位帧可表示成一个阶数为k-1的从xk-1到X0的k次多项式，如110001表示成x5+x4+x0。多项式以 2为模运算，其加减法及除法中的减法都同于异或操作，只有被除数和 除数等长时才作减法。设发送方发送m位长的帧多项式为Mx），收发双方需共同商定一个r阶的生成多项 式qx），必须m > r+1。发送方在Mx）后面增加一个冗余多项式

7、&x）构成带校验 信息的传输帧多项式T（x），T（x）必须能被qx）整除。当接收方收到T（x）后，只要 检查t（x）和qx）的整除关系是否存在即可判定传输是否出错。具体算法：对Mx）左移r位，得到多项式xrM（x），帧长为m+r位。按模2除法将xrM（x）除以Qx）。按模2减法将xrM（x）减去中所得余数，即得到多项式T（x）。差错控制策略检/纠错码的检 /纠错能力与编码集的海明距离有关，海明距离越大，检 /纠错能 力就越强，但所需的冗余信息就越多，编码效率就越低。由于纠错码比检错码要求更大的海明距离，且技术复杂，纠正可靠性不高，所以 一般很少使用，只有在没有反馈信道的单工通信中，为了

8、确保可靠才会采用。在大多数通信中采用的是检错编码。接收方收到帧后，对其进行校验检查，并发回相应的反馈信息。发送方根据反馈信息来决定是继续发送新帧（肯定应答），还是重发出错的旧帧（否定应答）。§ 3.4 基本数据链路协议协议 1：一种无限制的单工协议（乌托邦）完全理想的条件：数据单向传输，收发双方的网络层一直处于就绪状态，处理时 间可忽略不计，接收缓冲空间无限大，信道不会损坏或丢失帧。发送端无限循环地重复三个动作：-从网络层取分组。-构造帧。-发出帧。无需任何差错控制和流量控制。接收端也是无限循环地重复三个动作：-等待事件（唯一的未损坏帧的到达）发生。-帧到达后，从硬件缓冲中取出新到的

9、帧。-将帧的数据部分传给网络层。无需做其它任何处理。协议2：停- 等协议条件基本同协议 1，只是接收缓冲只能存放一个帧且接收端需要一定的接收处理 时间。为了防止发送快于接收而造成数据丢失，发送端在发送一帧后必须停止发送，等 待接收端发回的反馈确认短帧；接收端在收到一个帧并发送网络层后，需向发送 端发一反馈确认短帧（不需包含任何信息，因为信道是无差错的），表示可发新 帧。由于需要反馈， 且帧的发送和反馈是严格交替进行的， 所以一般采用半双工信道有噪音信道的停 -等协议所涉及的问题进一步考虑实际的会出错的信道，帧既可能损坏（接收端可通过校验检查出错 误），也可能完全丢失。发送端仍通过接收端的反馈来

10、决定怎么做。但由于帧会丢失，发送端可能收不到 反馈的确认帧，因此发送端必须引入超时机制（ time out ），即增加一个定时 计数器，在一定时间后对没有确认的帧进行重发，也称作 ARQ（ AutomaticRetransmit reQuest )-时间值应选择稍大于两倍端到端的信号传输时间和接收端的接收处理时间之 和。当接收端的反馈确认帧丢失时，必须通过为帧编制序号来解决重复帧的问题。-帧的序号位数应尽量的短从而少占用帧头的空间，这里只需 1个比特位即可 这是由于在本协议中， 发送端每发送一个帧都是建立在此帧之前的所有帧都已 正确发送的基础上，只需区分相邻的两个连续帧即可避免重复的可能。协议

11、3：有噪音信道的停 - 等协议收发双方都需维护各自的帧序号(sequenee number,初始都为0)。发送端维护 的帧序号N(S)表示当前所发帧的序号，接收端维护的帧序号N(R)表示接收端当前 所期待接收的帧序号。发送端从网络层取得第一个分组进行组帧，将N(S)=0的序号放入帧头中作为第一个帧，通过物理层的发送缓存器发送出去，并启动定时计 数器，然后停下来等待其响应帧。接收端收到一个帧后，对其序号和N( R)进行比较：-若不等，则将其作为重复帧而丢弃；-若相等则对其接收，经校验正确并送交网络层后，将 N(R)加1 (模2运算)并放 入确认帧中反馈回发送端；若校验出错，则丢弃出错的帧，保持N

12、(R)的值不变 并放入确认帧中反馈回发送端。发送端若在规定的时间内没有收到接收端的反馈确认帧(超时)，就认为数据帧 丢失，在保持NS)不变的情况下重新发送缓冲器中的(旧)帧；若接收到确认帧 后，比较确认帧中的序号和 N(S)：-若相等，则保持NS)不变，重新发送缓冲器中的(旧)帧；-若不等，则将确认帧中的序号赋予 N( S)，从网络层获取新的分组并组成新帧(NS)作为序号放入帧头中)交由物理层发送出去。发送端每发送一帧，都会重新启动定时计数器，然后停下来等待其响应帧。停-等协议对信道利用率的影响在时延大的信道(如卫星通信)中，停 -等协议的效率是很低的。 为了提高传输效率，可以设想让发送站连续

13、不断地发送数据帧。允许发送站连续发送多个帧而不需等待确认的做法称作管道化( pipelining )， 属于一种窗口( windows)机制。§ 3.5 滑动窗口协议滑动窗口( Slide Windows )协议是一种非常可靠、适用于各种条件的通用流量 控制协议，特别是在效率、复杂性及对缓冲区的需求等方面可作灵活调配。主要的滑动窗口协议有出错全部重发协议和选择重发协议两种。收发双方维护的序号也变为一组序号表，分别称作发送窗口( sending window ) 和接收窗口( receiving window )。发送窗口发送窗口就是发送端允许不等确认而连续发送的帧的序号表。允许连续发

14、送的帧的数量称为发送窗口尺寸，表示为 W发送端必须有Wb输出缓 冲区来存放V个数据帧的副本以备数据帧的重发。发送端最早发送但还未收到确认的帧的序号称为发送窗口的下沿，表示为LN(R)。而(LN( R)+W1)模2n为发送窗口的上沿。发送端将来自网络层的分组按顺序编号组帧，只有帧序号落在发送窗口内的帧才 可不等确认直接通过输出缓冲区发送出去。当发送端收到发送窗口下沿帧的肯定确认时，将发送窗口整体向前滑动一个序 号，并从输出缓冲区中将相应的数据帧副本删除。接收窗口接收窗口是接收端允许接收的帧的序号表。 允许接收的帧的数量称为接收窗口尺寸。 同样接收端也必须设置相应数量的输入 缓冲区来支持接收窗口。

15、对接收端收到的帧的序号落在接收窗口外的帧被直接丢弃。 只有落在接收窗口内 的帧才会被接收端进行校验处理，若校验正确：-当接收的帧不是接收窗口下沿帧时，必须暂存在输入缓冲区，不能交给网络层。-当接收到接收窗口下沿帧时，会将其连同后面连续的若干个检验过的正确帧按 顺序交给网络层，在发回确认帧的同时将接收窗口向前滑动相应的数量。数据的全双工传输在实际通信中，通常收发双方都相互发送数据。为了提高效率， 可以将确认信息放在数据帧中作为一个控制字段连同数据一起发 送给对方，这种方式称为捎带应答( piggybacking )。当一方收到对方的数据帧后：-若正好也有数据需发给对方，则立即可使用捎带应答。-若

16、暂时没有数据需发给对方或数据还未准备好，则等待一定的时间，如果在该 时间内准备好了数据， 则可以使用捎带应答。 如果未准备好， 为了防止对方等 待时间过长而超时重发，必须立即发送一个单独的确认帧。使用捎带应答就不可能对每一个帧都作确认，可以用对某一个帧的确认来代替对 该帧之前的所有帧的确认。协议 4：出错全部重发协议（ go-back-n ） 出错全部重发协议中，发送窗口的尺寸是大于 1，而接收窗口的尺寸则等于 1。 由于接收窗口的尺寸为 1，接收端只能按顺序地接受数据帧，一旦某个帧出错或 丢失，只能简单地丢弃该帧及其所有的后续帧 （因为发送窗口的尺寸是大于 1的）， 不作任何确认。发送端超时

17、后需重发出错或丢失的帧及其后续所有的帧。 发送端需要为每个待确认的帧都各自设置一个定时计数器。 发送窗口的尺寸不能超过 2n-1 ，否则会造成接收端无法分辨新、旧数据帧。 出错全部重发协议只要求发送端保持一定数量的缓存来保存没有确认的数据帧， 对接收端没有缓存的要求。但在误码率高的情况下，会大大降低信道的利用率。协议5：选择重发协议（ selective repeat ） 选择重发协议中，发送和接收窗口的尺寸都大于 1。 由于接收窗口的尺寸大于 1，接收端可存储坏帧之后的其它数据帧（落在接收窗 口），接收端对错帧发否定确认帧，因此发送端只需重发出错的帧，而不需重发 其后的所有后续帧。接收端正确

18、收到重发的帧后，可对其后连续的已接收的正确帧作一次总体确认 （最大序号的确认），并交送网络层。大大提高了信道的利用率。接收窗口的尺寸不能超过2”1 （即序号范围的1/2 ），否则可能造成帧的重叠。 发送窗口的尺寸一般和接收窗口的尺寸相同，发送端为每一个输出缓存区设置一 个定时计数器，定时器一旦超时，相应输出缓存区中的帧就被重发。§ 3.5 数据链路层协议实例 数据链路层协议也称作链路控制规程，通常分为异步和同步两大类协议：-异步协议以字符为独立的传输单位，实现字符间的异步和字符内的同步传输。 简单，但效率低。-同步协议以许多字符（面向字符型协议）或比特（面向比特型协议）组成的数据块(

19、帧)为传输单位， 收发双方使用相同的时钟实现复杂的长数据块的同步 传输。速度快，效率高，但复杂且成本高。面向字符的同步控制协议?面向字符的同步协议是最早提出的同步协议，其典型代表是IBM的二进同步通信BSC(Binary Synchronous Communication)协议。随后 ANS和ISC都提出了类 似的相应标准。?用ASCII和EBCDI字符集定义的传输控制字符来实现建链、拆链等链路管理以 及同步等各种功能。高级数据链路控制规程 HDLCHDLC勺工作模式三种站：-主站(primary station ):负责链路的控制。-次站(secondary station ):仅完成主站指

20、示的工作。-复合站(combined station ):主站和次站组合成的站。四种工作模式:-正常响应模式NRM( Normal Response Mode :一种非平衡数据链路操作方式， 适用于面向终端的点 - 点或点 - 多点链路。-异步平衡模式ABM( Asy nchron ous Bala need Mode ):一种平衡的数据链路操 作方式，通信双方都为复合站，具有相同的功能且相互作用。-分别将上两种工作模式中的帧序号位从 3位扩展到7位就构成了两种扩展的 (extended )工作模式：NRM和 ABMEHDLC勺帧类型HDL使用具有3位序号(07)的滑动窗口协议。通过控制字段中的第1或2位可将 帧标识成三种类型:-信息(Information )帧-监控(Supervisory )帧-无序号(Unnumbered 帧HDLC勺信息帧信息帧用于传输数据，简称 I 帧NS)是发送帧的序号。N(R)用于捎带应答，表示下一个期待接收的帧。P/F为探询/终止(Poll/Final )比特：-当主站轮询各个从站时，将P置为“ 1”，表示允许从站发送数据；从站可连续 发送多帧数据，最后一帧的F必须为“ 1”，表示数据传输结束。-在命令帧中将PS为“ 1”还表示向对方询问状态，收到P