2011年计算机网络考研辅导讲座（3、数据链路层--上）

nullnull第三讲 数据链路层(上)第三讲：数据链路层—(上)第三讲：数据链路层—(上)2011年考研大纲考查范围:大纲考查范围（续）大纲考查范围（续） 1. 网桥的概念和基本原理 2. 局域网交换机及其工作原理知识点归纳知识点归纳 数据链路/逻辑链路 = (物理)链路 + 通信规程 （一）数据链路层的功能 1）作用： 将网络层交下来的数据报组装成幀，在两个相邻结点间的链路上传送以幀为单位的数据。接收端进行差错检测，若有错，则丢弃差错幀。然后或者通知对方重传、或者不处理交由上层解决。 2）目的： 在相邻结点间提供透明、无错的数据传输。 3）功能： 组幀(同步、定界、透明传输)、差错控制、重传策略、流量控制、寻址、链路管理等。知识点归纳知识点归纳知识点归纳（二） 组帧 把数据封装成帧 关键问题：让接收者能够从接收的位流中区分出帧的边界(幀同步)，即帧的开 始和结束。 幀同步方法： (1) 字节计数法: ■每帧以帧同步标志字节开始，后面紧跟幀长计数 ■接收方收到幀，知道幀的长度，每接收一个数据字节，计数减1， 直到为0，便是幀尾，幀后跟校验信息。 知识点归纳 (2) 使用字符填充的首尾定界符法 （ 如BSC 协议 离婚协议模板下载合伙人协议 下载渠道分销协议免费下载敬业协议下载授课协议下载 ） ■面向字符通信协议，以特定ASCII字符序列表帧首、帧尾及控制字段。 ■帧头两个同步字符SYN SYN之后，数据字段以DLE STX 开始，DLE ETX 结束，中间数据用“DLE插入删除技术”来实现字符的透明传输。知识点归纳知识点归纳 (3) 使用比特填充的首尾标志法（ 如HDLC 协议） ■以特殊的比特组合（如 01111110 同步 序列）标志帧的开始和结束 ② ■面向位的通信协议，用“0”比特插入删除技术”来实现字符的透明传输。 ■例： 0110111111100011111010 插入后： 011011111011000111110010 恢复： 0110111111100011111010 (4) 编码违例法 ■ 采用违反编码规律的策略标志帧边界。优点：无须另外透明传输方法 ■ 如差分Manchester编码中每一位中间不是 便是 。 而 、 则是违法编码，用其在令牌环网的帧中标志帧头、帧 尾，接收方易识别，帧中数据字段也不需另外设计透明传输法。知识点归纳知识点归纳（三） 差错控制 ■检错码(码字只有检错的功能，接收方只能判断数据块有错，但不能确切知道错 误的位置，从而也不能纠正错误)，如奇偶校验码、校验和码、CRC码。 ■纠错码(码字具有一定的纠错功能，接收方不仅能检出错，还知道错在什么地方, 这时只需将数据位取反即能获得正确的数据)，如海明码。 ■检错码举例： 奇偶校验码：[例] 异步数据通信时的偶校验，100100011(凑成偶数个1)。 校验和码： [例1] 路由器中网络层实体对IP信包头做的校验和：知识点归纳知识点归纳[例2]传输层实体中对整个UDP数据包(或TCP报文)做的校验和，以UDP为例：知识点归纳知识点归纳循环冗余校验码(CRC): [例]以太帧、无线帧、PPP帧尾的4字节CRC校验码。 它们做CRC除法运算时用的生成多项式除数CRC-32为： CRC-32 = x32+x26+x23+x22+x16+x12+ x11+x10+x8+x7+ x5+ x4+ x2+x+1 在发送方做CRC除法运算，计算所得的余数为CRC校验码，它跟在数据后面一起传输到接收方，接收方同样做CRC除法运算，若余数为0，则校验正确。 若帧数据为100100，以4位生成多项式 x3+ x2+1 即位串 1101 为例：知识点归纳知识点归纳 ■ 纠错码举例**： 海明码：[例] 单工通信时插入数据中的海明码(注意红字P1, P2, P4, P8)。 [解] 设‘A’的 ASCII 码为1000001, 由于海明码为 P1P2D3P4D5D6D7P8D9D10D11的形式， 即此处 D3 D5D6D7 D9 D10 D11 = 1000001 , P1, P2, P4, P8为插入的海明码， 则由式子 P1 = D3+D5+D7+D9+D11，P2 = D3+D6+D7+D10+D11， P4 = D5+D6+D7， P8 = D9+D10+D11 可计算得：P1=0，P2=0，P4=0，P8=1 ∴ 发送端形成的海明码为 00100001001 若接收方接收错误，收到：00100001011 (D10错误) 则检/纠错过程如下：计算校正因子S1、S2、S4、S8，方法如下： 由式子 S1 = P1+D3+D5+D7+D9+D11 S2 = P2+D3+D6+D7+D10+D11 S4 = P4+D5+D6+D7 S8 = P8+D9+D10+D11 若计算出的 S1＝ S2 ＝ S4 ＝ S8 ＝ 0， 则无错； 若 S1 ～ S8 不全为 0, 则有错，错误位置在 S＝ S8 S4 S2 S1 处， 由上法计算得： S1=0，S2=1，S4=0，S8=1 ∵ S2= S8= 1 ∴ 检测有错， 错误位置在 S＝1010 处，即D10处，因此将D10取反即可，纠错完毕■ ** ---- 选学，参考 知识点归纳知识点归纳■差错控制：前向纠错法（FEC）、反馈差错控制法(自动重发请求ARQ) 前向纠错法(FEC)： 自动纠错，发送端使用纠错码，接收端检出并纠正错，但监督码比较复杂、效率低，一般用于没有反馈信道的单工通信中。 自动重发请求(ARQ)： 使发送方确认接收方是否正确收到了由它发送的数据信息。发送方发送数据帧时附加一定的冗余检错码一并发送，接收方则根据检错码对数据帧进行差错检测，若发现错误，就返回请求重发的应答，发送方收到请求重发的应答后，便重新传送该数据帧。这种差错控制方法就称为自动重发请求法(Automatic Repeat reQuest)，简称ARQ法。知识点归纳知识点归纳 其中，ARQ法有几种实现 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ，停等法和连续ARQ是最基本的两种方案。 ■ 停等法(Stop and Wait) ： 该方案规定发送方每发送一帧后就要停下来等待接收方的确认返回，仅当接收方确认正确接收后再继续发送下一帧 。停等法方案的实现过程如下： ①发送方每次仅将当前信息帧作为待确认帧保留在缓冲存储器中； ②当发送方开始发送信息帧时，随即启动计时器； ③当接收方收到无差错信息帧后，即向发送方返回一个确认帧； ④当接收方检测到一个含有差错的信息帧时，便舍弃该帧； ⑤若发送方在规定时间内收到确认帧，即将计时器清零，继而开始下一帧的发送； ⑥若发送方在规定时间内未收到确认帧，即计时器超时，则应重发存于缓冲器中的待确认信息帧。 从以上过程可以看出，停等法方案的收、发送方仅需设置一个帧的缓冲存储空间，便可有效地实现数据重发并确保接收方接收的数据不会重份。停等法方案最主要的优点就是所需的缓冲存储空间最小，因此在链路端使用简单终端的环境中被广泛采用。为防止重复帧造成问题，帧编号0、1循环使用。 知识点归纳知识点归纳■ 连续ARQ法： 连续ARQ方案是指发送方可以连续发送一系列信息帧，即不用等前一帧被确认便可发送下一帧。这就需要在发送方设置一个较大的缓冲存储空间 ( 称作重发表 )，用以存放若干待确认的信息帧。当发送方得到对某信息帧的确认帧后便可从重发表中将该信息帧删除。所以，连续ARQ方案的链路传输效率大大提高，但相应地需要更大的缓冲存储空间。连续ARQ方案的实现过程如下： ①发送方连续发送信息帧而不必等待确认帧返回，每发一帧启动一个计时器； ②发送方在重发表中保存所发送的每个帧的备份，重发表按先进先出(FIFO)队列规则操作； ③接收方对每一个正确收到的信息帧返回一个确认帧（可以累积确认）；每一个确认帧包含对某一个信息帧的确认序号，随相应的确认帧返回； ④当发送方收到相应信息帧的确认后，将相应的计时器清零，从重发表中删除该信息帧的备份； ⑤若发送方在规定时间内未收到确认帧，即发送该帧时对应的计时器超时，便重发该未被确认的信息帧。 整个过程中，发送方某个时刻管理超时控制的计时器数目应等于缓冲器中当时已发但未获确认的帧数目。知识点归纳 上面连续ARQ过程中如果出现传输差错，如何进一步处理还可以有两种策略，即出错全部重发（ GO-BACK-N，GBN）策略和选择重发（ SELECT REPEAT ，SR）策略。 GO-BACK-N（GBN）即出错全部重发策略的基本原理是，当接收方检测出失序的信息帧后，要求发送方重发最后一个正确接收的信息帧之后的所有未被确认的帧；或者当发送方发送了N个帧后，若发现该N帧的前一个帧在计时器超时后仍未返回其确认信息，则该帧被判为出错或丢失，此时发送方就不得不重新发送出错帧及其后的N帧。这就是GO-BACK-N(退回N)法名称的由来。因为，对接收方来说，由于这一帧出错，就不能以正常的序号向它的高层递交数据，对其后发送来的N帧也都不能接收因而丢弃它们。GO-BACK-N可能将已正确传送到目的方的帧再重传一遍，这显然是一种浪费。 SELECT REPEAT (SR) 即选择重发策略的基本原理：另一种效率更高的策略是当接收方发现某帧出错后，其后继续送来的正确的帧虽然不能立即递交给接收方的高层，但接收方仍可收下来，存放在一个缓冲区中，同时要求发送方重新传送出错的那一帧。一旦收到重新传来的帧后，就可以与原已存于缓冲区中的其余帧一起按正确的顺序递交高层。知识点归纳知识点归纳（四） 流量控制与可靠传输机制 掌握流量控制、可靠传输（差错控制+重传机制）与滑动窗口机制的基本原理和方法，重点解析单帧滑动窗口即停止-等待协议，多帧滑动窗口与后退N帧协议（GBN），多帧滑动窗口与选择重传协议（SR），并进行实例化描述。 流量控制涉及链路上字符或帧的发送速率的控制, 以使接收方在接收前有足够的缓冲存储空间来接收每一个字符或帧。例如，在面向字符的“计算机—终端”链路中，若远程计算机为许多台终端服务，它就有可能因不能在高峰时按预定速率传输全部字符而暂时过载。同样，在面向帧的自动重发请求系统中，当待确认帧数量增加时，有可能超出缓冲器存储空间，也会造成过载。有两种常用的流量控制方案：XON/XOFF方案和滑动窗口机制。 ■ XON/XOFF方案（如“计算机—终端”链路的异步数据通信软件中） XON/XOFF方案中使用一对控制字符来实现流量控制，其中XON采用ASCII字符集中的控制字符DC1(ASCII码11H)，XOFF 采用ASCII字符集中的控制字符DC3(ASCII码13H)。当通信线路上的接收方发生过载时，便向发送方发送一个XOFF字符（类似交通灯“红灯”的作用） ，发送方接收XOFF字符后便暂停发送数据；等接收方处理完缓冲器中的数据、过载恢复后，再向发送方发送一个XON字符（类似交通灯“绿灯”的作用） ，以通知发送方恢复数据发送。在一次数据传输过程中，XOFF、XON的周期可重复多次，但这些操作对用户来说是透明的。知识点归纳知识点归纳知识点归纳■ 滑动窗口机制（如网络的发送、接收软件中） 为了提高信道的有效利用率，如前所述采用了不等待确认帧返回就连续发送若干帧的方案。由于允许连续发送多个未被确认的帧 ，帧号就需采用多位二进制数才能区分（一般只取有限位二进制数，到一定时间后就又反复循环，如帧号配3位二进制数，则帧号在0~7间循环）。由于凡被发出去而尚未被确认的帧都可能出错或丢失而要求重发，这些帧在发送方都要暂时保留，这就要求发送方有较大的发送缓冲区保留这些帧，并把这些可能要重发的帧号存在待重发表中。 接收缓冲区容量也是有限的，如果接收方不能以发送方的发送速率处理接收到的帧，则可能用完缓冲容量而暂时过载。为此，要对发送方可发送的帧的数目加以限制，可以控制发送方的发送窗口和保留在重发表中的待确认帧的数目来解决：如果接收方来不及对新到的帧进行处理，便停发确认信息，此时发送方由于连续发出多帧得不到确认，重发表就会增长，当由于连续发出多帧且得不到确认，导致发送窗口减为0、重发表增长到极限上限值时，发送方就不再能发送新帧，直至再次收到确认信息才行。 发送窗口就是发送端允许连续发送的幀的序号表，发送端可以不等待应答确认而连续发送的最大幀数称为发送窗口的尺寸。重发表是一个连续序号的列表，对应发送方已发送但尚未确认的那些帧。显然，如果发送窗口设置为1，即发送方缓冲能力仅为一个帧，则传输控制方案就回到了停等法方案，此时传输效率很低。故窗口限度应选为使接收方尽量能处理或接受收到的所有帧。当然选择时还必须考虑诸如帧的最大长度、可使用的缓冲存空间以及传输速率等因素。 接收方类似地也有接收窗口，它指示接收方允许接收的幀的序号表，凡落在接收窗口内的幀，接收方都必须处理，落在接收窗口外的幀将被丢弃。接收方每次允许接收的幀数称为接收窗口的尺寸。 知识点归纳知识点归纳 发送方初始化后，发送窗口等于发送窗口最大尺寸，重发表中待确认帧的数目等于0。每次发送一帧后，发送窗口便减1，同时重发表待确认帧的数目增1，每收到对一个帧的确认信息后，重发表待确认帧的数目便减1，由于得到确认而释放了一个帧的发送缓冲，于是发送窗口便增1。当这样的传送过程进行时，打开的窗口位置一直在滑动，称为滑动窗口(Slidding Window)。当发送方连续发出多帧得不到确认、发送窗口减为0、重发表中待确认帧的数目等于发送窗口最大尺寸时，便停止发送新的帧。 接收方初始化后，接收窗口等于接收窗口最大尺寸。每次收到一帧后，便会占用一帧的接收缓冲容量，接收窗口减1。当接收缓冲里的一帧校验正确、取出交给高层软件并向发送方发出对该帧的确认帧后，便会释放该帧占用的接收缓冲容量，接收窗口便增1。当这样的接收过程进行时，接收窗口位置也一直在滑动。 一般来说，凡是在接收窗口范围内到达的帧，即使它们不按顺序，接收方也应接收下来，此时，接收窗口大于1。而Go-back-N正是接收窗口等于1的一个特例，因为接收方对收到出错帧后收到的后续帧都不接收而丢弃。而选择重发SR发送窗口和接收窗口都大于1，因为接收方收到落在接收窗口范围内的帧时统统接收而不管是否按序接收。停等法则发送窗口和接收窗口都等于1。停等法、Go-back-N及选择重发三种协议的差别仅在于各自窗口尺寸的大小不同而已，已经证明，三者对发送窗口、接收窗口的尺寸有一定的限制要求，如不满足便不能正常工作，它们是： 停等法：　　发送窗口=1，接收窗口=1； WT = WR = 1 Go-back-N： 发送窗口>1，接收窗口=1; WR = 1, 须WT ≤ 2n－1 选择重发：　发送窗口>1，接收窗口>1； WT = WR时, 须WR ≤ 2n-1 如帧序号采用3位二进制编码(n=3)，对于GBN有序接收方式，发送窗口最大尺寸应为23-1=7 ；对于SR无序接收方式，接收窗口最大尺寸最多是23-1=4。知识点归纳 (停-等协议示例)知识点归纳 (停-等协议示例)流量控制： 控制发送方的发送数据量，使得不能超过接收方的接收能力。（接收方使用反馈机制，向发送方应答， 报告 软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载 自己当前的接收情况和能力。接收能力由接收设备的处理速度、接收缓冲的容量等影响） 局域网中两种常用的流量控制策略： 停-等协议，滑动窗口协议 停-等协议示例：frame 0ACK 1frame 1ACK 0frame 0frame 0ACK 1frame 1ACK 0frame 1ACK 0发送方接收方超时超时帧丢失 重发ACK丢失 重发知识点归纳（滑动窗口示例1）知识点归纳（滑动窗口示例1）知识点归纳（滑动窗口示例2）知识点归纳（滑动窗口示例2）知识点归纳（滑动窗口示例3）知识点归纳（滑动窗口示例3）知识点归纳（出错全部重发，Go-back-N ）知识点归纳（出错全部重发，Go-back-N ） 若发送方发出连续的若干幀后，收到对其中某一帧的否认帧，则从该帧及该幀开始的后续帧全部重发。 接收方只按序接收数据帧。虽然在有差错的帧之后接着又收到后续正确的数据帧，但都将其丢弃，因为不是所需的帧号。 ■ 优点：连续发送提高了信道利用率 ■ 缺点：导致某些对方已正确接收的帧也重传，因此降低了发送效率 ■ 出错全部重发时，若幀序号为n位， 接收窗口WR=1，须发送窗口 WT ≤ 2n－1 ■ 误码率较低时，连续ARQ优于停等协议；反之则不一定。WT＝2n-1时正常, WT>2n-1时出错WT＝2n-1时正常, WT>2n-1时出错知识点归纳（出错选择重发，SR ）知识点归纳（出错选择重发，SR ） 若发送方发出连续的若干幀后，收到对其中某一帧的否认帧，只重传该出错幀或定时器超时的数据帧。 接收方的接收窗口 WR > 1 ，会接收和暂存所有落在在接收窗口范围内的数据帧，即使帧序号在出错帧之后也收。 ■ 优点： 避免重传已正确传送的帧，提高了信道利用率。 ■ 缺点： 在接收端需要占用一定容量的缓存。 ■ 出错选择重发时，设幀序号为n位， WT = WR时, 须接收窗口的尺寸 WR ≤ 2n -1 WR＝2n-1时正常, WR>2n-1时出错WR＝2n-1时正常, WR>2n-1时出错知识点归纳知识点归纳（五）介质访问控制 知识点归纳知识点归纳 随机访问的介质访问控制。 主要有ALOHA随机争用协议 ( 纯ALOHA 和时隙ALOHA)、CSMA协议（先听后说）以及非坚持型算法，1-坚持型算法和p-坚持型算法、CSMA/CD协议，以及CSMA/CA协议，重点要掌握CSMA/CD──带有碰撞（冲突）检测的载波监听多路访问控制方法。知识点归纳（ CSMA/CD ）具有冲突检测的载波监听多路访问 CSMA/CD： ■ 工作原理：某站点要发送数据帧前，先监听信道，若信道空闲, 则立即发送数据 帧，若信道忙，则坚持一直监听到信道空闲，然后立即发送数据帧， 发送数据帧的同时，边发送边监听(在冲突检测窗口的2τ时间内，其 中2τ为最远的两个端点间一来一回传输的时间), 若在此期间监听到 冲突，立即停止发送，并发送Jam干扰信号串到网上通知全网站点以 强化冲突，使各冲突的站点马上停止发送，使信道很快空闲下来，然 后按截断的二进制指数退避算法延迟一段随机时间，再监听信道尝试 发送。 ■ 1-坚持CSMA, 再加上CD (冲突检测)。 ■ 冲突检测方法： （1） 比较接收到的信号电压的大小 或（2） 检测曼彻斯特编码的过零点 或（3） 比较接收到的信号与刚发出的信号 ■ 退避算法：为截断的二进制指数退避算法，来决定重发时延：从 0, 1, 2, ..., 2k-1  中随机取一个数r，重发时延 = r  (2τ)，其中 k = min[ 重发次数，10 ] 知识点归纳（ CSMA/CD ）知识点归纳(CSMA/CD工作 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 )知识点归纳(CSMA/CD工作流程)知识点归纳（ CSMA/CA ）知识点归纳（ CSMA/CA ）802.11 CSMA 发送站： 如监听到信道空闲, 经DIFS/PIFS/SIFS 时间后则发送整个幀（发送时不用冲突检测） 如果监听到信道忙，则到不忙时，经DIFS/PIFS/SIFS 时间后进入竞争期，进行二进制指数退避 （第 i 次退避时，在 2i+2 个时隙中随机选择一个），退避后重新尝试发送。 如果发送后未收到ACK(超时)，则重发幀。 802.11 CSMA 接收站： 如果接收时CRC校验正确，则在SIFS时间后应答一个ACK 幀 其它站点： 听到信道上其它站在发帧，则推迟访问信道 NAV(Network Allocation Vector)时间， 即虚拟载波侦听。 另外，由于发送时不进行冲突检测，因此在发送长的无线帧时，为进一步避免较长时间的冲突，CSMA/CA中还要再加进发送前首先预约信道： 发送站: 发出短的 RTS幀(request to send)预约信道 接收站: 应答短的 CTS幀 (clear to send)同意预约 CTS 帧为发送站保留了信道, 起了通知其它(可能隐蔽的)站点的效果，避免了隐蔽站点造成的冲突 。由于RTS帧短，若多站预约，同时发RTS帧冲突的概率很小。 总结以上CA 措施 《全国民用建筑工程设计技术措施》规划•建筑•景观全国民用建筑工程设计技术措施》规划•建筑•景观软件质量保证措施下载工地伤害及预防措施下载关于贯彻落实的具体措施 ：1. 二进制指数退避；2. 虚拟载波侦听；3. RTS/CTS预约信道； 4. 各站根据所发帧的优先级，采用不同的帧间间隔延迟DIFS、PIFS或SIFS知识点归纳(CSMA/CA操作)知识点归纳(CSMA/CA操作)知识点归纳(轮询及令牌传递协议)轮询访问的介质访问控制：如HDLC中主站依次轮询各从站是否传输数据。 令牌传递协议： 控制令牌是另一种传输媒体访问控制方法。在一个环上，从一个站点到另一个站点依次传递控制令牌，周而复始。一个站点只有当它取得令牌时，才能发送数据帧，发完帧后，再把令牌传递到环上的下一个站点，……。其操作具体如下： ■ 首先环上的管理站产生一个控制令牌，控制令牌由一个站点沿着环顺序向下一个站点、一个站点一个站点依次传递，周而复始； ■ 要发送帧的站点收到控制令牌后，组成发送的数据帧，发到环上； ■ 当数据帧沿环传输，经过接收站点时，接收站点在该帧的接收响应位上做标记，并将该帧拷贝到自己的缓冲内，从而接收该数据帧； ■ 数据帧继续沿着环传输，当帧沿环转一圈回到发送站点，发送站点将该帧回收，然后再发出控制令牌，继续沿着环一站一站传递，……。 令牌传递方法除了用于环形网拓扑结构即令牌环 (即IEEE 802.5) 之外，也可以用于总线网拓扑结构(即令牌总线,IEEE 802.4)，此时，将总线上的相关站点要用软件组织在一个逻辑环中，再在此逻辑环中使用以上的令牌传递方法。知识点归纳(轮询及令牌传递协议)