计算机网络考研辅导讲座(3、数据链路层).ppt

2014计算机网络技术考研辅导,毕婧 沈阳师范大学软件学院 2013.11.11,第三讲：数据链路层(上),大纲考查范围（续）,1. 网桥的概念和基本原理 2. 局域网交换机及其工作原理,知识点归纳,数据链路/逻辑链路 = (物理)链路 + 通信规程 （一）数据链路层的功能 1）作用： 将网络层交下来的数据报组装成幀，在两个相邻结点间的链路上传送以幀为单位的数据。接收端进行差错检测，若有错，则丢弃差错幀。然后或者通知对方重传、或者不处理交由上层解决。 2）目的： 在相邻结点间提供透明、无错的数据传输。 3）功能： 组幀(同步、定界、透明传输)、差错控制、重传策略、流量控制、寻址、链路管理等。,局域网,广域网,主机 H1,主机 H2,路由器 R1,路由器 R2,路由器 R3,电话网,局域网,主机 H1 向 R1 发送数据,链路层,应用层,运输层,网络层,物理层,链路层,网络层,物理层,R1,H1,H2,0111111011010101111110,0111111011010101111110,局域网,广域网,主机 H1,主机 H2,路由器 R1,路由器 R2,路由器 R3,电话网,局域网,主机 H1 向 R1 发送数据,链路层,应用层,运输层,网络层,物理层,链路层,网络层,物理层,R1,H1,H2,0111111011010101111110,冲击噪声,局域网,广域网,主机 H1,主机 H2,路由器 R1,路由器 R2,路由器 R3,电话网,局域网,主机 H1 向 R1 发送数据,链路层,应用层,运输层,网络层,物理层,链路层,网络层,物理层,R1,H1,H2,0111111011010101111110,0111111011011111111110,知识点归纳,（三） 差错控制 检错码(码字只有检错的功能，接收方只能判断数据块有错，但不能确切知道错 误的位置，从而也不能纠正错误)，如奇偶校验码、校验和码、CRC码。 纠错码(码字具有一定的纠错功能，接收方不仅能检出错，还知道错在什么地方, 这时只需将数据位取反即能获得正确的数据)，如海明码。 检错码举例： 奇偶校验码：例 异步数据通信时的偶校验，100100011(凑成偶数个1)。 校验和码： 例1 路由器中网络层实体对IP信包头做的校验和：,知识点归纳,循环冗余校验码(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 为例：,知识点归纳, 纠错码举例*： 海明码：例 单工通信时插入数据中的海明码(注意红字D1, D2, D4, D8)。 解 设A的 ASCII 码为1000001, 由于海明码为 D1 D2 D3 D4 D5D6D7 D8 D9 D10 D11的形式， 即此处 D3 D5D6D7 D9 D10 D11 = 1000001 , D1, D2, D4, D8为插入的海明码， 则由式子 ： 3 = 1+2，5 = 1+4，6 = 2+4，7 = 1+2 +4，9 = 1 + 8，10 = 2+ 8，11 = 1+2+8 D1 = D3+D5+D7+D9+D11， D2 = D3+D6+D7+D10+D11， D4 = D5+D6+D7， D8 = D9+D10+D11 偶校验，可计算得：P1=0，P2=0，P4=0，P8=1 发送端形成的海明码为 00100001001,知识点归纳, 纠错码举例*： 海明码：例 单工通信时插入数据中的海明码(注意红字P1, P2, P4, P8)。 解 若接收方接收错误，收到：00100001011 (D10错误) 则检/纠错过程如下：计算校正因子S1、S2、S4、S8，方法如下： 由式子 S1 = D1+D3+D5+D7+D9+D11 S2 = D2+D3+D6+D7+D10+D11 S4 = D4+D5+D6+D7 S8 = D8+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 检测有错， 错误位置在 S1010 处，即D10处，因此将D10取反即可，纠错完毕,知识点归纳,差错控制：前向纠错法（FEC）、反馈差错控制法(自动重发请求ARQ) 前向纠错法(FEC)： 自动纠错，发送端使用纠错码，接收端检出并纠正错，但监督码比较复杂、效率低，一般用于没有反馈信道的单工通信中。 自动重发请求(ARQ)： 使发送方确认接收方是否正确收到了由它发送的数据信息。发送方发送数据帧时附加一定的冗余检错码一并发送，接收方则根据检错码对数据帧进行差错检测，若发现错误，就返回请求重发的应答，发送方收到请求重发的应答后，便重新传送该数据帧。这种差错控制方法就称为自动重发请求法(Automatic Repeat reQuest)，简称ARQ法。,数据链路层协议数据链路通信的简单模型,AP1,缓存,AP2,缓存,帧,帧,数据链路,发送方,接收方,主,机,A,主,机,B,完全理想化的数据传输,完全理想化的数据传输基于以下两个假定 假定1：链路式理想的传输信道，所传送的任何数据既不会出差错也不会丢失。 假定2： 不管发送方以多快的速率发送数据，接收方总来得及收下，并及时上交主机。(接收端向主机交付的数据速率永远不会低于发送端发送数据的速率),停等协议,停止等待(stop-and-wait)协议是最简单但也是最基本的数据链路层协议。 具有最简单流量控制的数据链路层协议 仍保留假定1，但去掉假定2 链路是理想的传输信道，即所传送的任何数据既不会出差错也不会丢失 由接收方控制发送方的数据流(计算机网络中流量控制的一个基本方法)。,停等协议,两种数据传输比较,实用的停止等待协议,前提：去掉两个假定，即传输数据的信道不能保证使所传的数据不产生差错，而且还需对数据的发送端进行流量控制。 流量控制方法：等待发送 差错控制：发送方数据帧中加入校验码（CRC），由接收方检查；若正确，返回ACK，若出错，返回NAK；发送方根据收到的返回帧，决定发送新帧和重发。 帧丢失处理：超时定时器；以序号标识数据帧 优点：简单 缺点：信道利用率低，信道还远远没有被数据比特填滿,数据帧在链路上传输的几种情况,3.5连续 ARQ 协议,在发送完一个数据帧后，不是停下来等待确认帧，而是可以连续再发送若干个数据帧。 如果这时收到了接收端发来的确认帧，那么还可以接着发送数据帧。 由于减少了等待时间，整个通信的吞吐量就提高了。,连续 ARQ 协议的工作原理,3.5.1 退后N帧 ARQ 协议的工作原理,ACK1 确认 DATA0,ACK2 确认 DATA1,DATA2 出错，丢弃,DATA3 不按序，丢弃，重传 ACK2,DATA4 不按序，丢弃，重传 ACK2,DATA5 不按序，丢弃，重传 ACK2,ACK3 确认 DATA2,ACK4 确认 DATA3,超 时 重 传 时 间,A,B,tout,送交主机,送交主机,?,3.5.2 滑动窗口的概念,发送端和接收端分别设定发送窗口和接收窗口 。 发送窗口用来对发送端进行流量控制。 发送窗口的大小 WT 代表在还没有收到对方确认信息的情况下发送端最多可以发送多少个数据帧。,0,1,2,3,4,5,6,7,0,1,2,发送窗口,WT,不允许发送这些帧,允许发送 5 个帧,(a),接收端设置接收窗口,在接收端只有当收到的数据帧的发送序号落入接收窗口内才允许将该数据帧收下。 若接收到的数据帧落在接收窗口之外，则一律将其丢弃。 在连续 ARQ 协议中，接收窗口的大小 WR = 1。 只有当收到的帧的序号与接收窗口一致时才能接收该帧。否则，就丢弃它。 每收到一个序号正确的帧，接收窗口就向前（即向右方）滑动一个帧的位置。同时发送对该帧的确认。,不允许接收这些帧,0,1,2,3,4,5,6,7,0,1,2,WR,准备接收 0 号帧,(a),滑动窗口的重要特性,只有在接收窗口向前滑动时（与此同时也发送了确认），发送窗口才有可能向前滑动。 收发两端的窗口按照以上规律不断地向前滑动，因此这种协议又称为滑动窗口协议。 当发送窗口和接收窗口的大小都等于 1时，就是停止等待协议。,发送窗口的最大值,当用 n 个比特进行编号时，若接收窗口的大小为 1，则只有在发送窗口的大小 WT 2n 1时，连续 ARQ 协议才能正确运行。 例如，当采用 3 bit 编码时，发送窗口的最大值是 7 而不是 8。,不允许发送这些帧,0,1,2,3,4,5,6,7,0,1,2,WT,准备发送 0 号帧,(a),不允许接收这些帧,0,1,2,3,4,5,6,7,0,1,2,WR,已收到,(b),准备接收这个帧,0,1,2,3,4,5,6,7,0,1,2,WR,已收到,(c),ACK,不允许发送这些帧,0,1,2,3,4,5,6,7,0,1,2,WT,准备发送 0 号帧,(a),不允许接收这些帧,0,1,2,3,4,5,6,7,0,1,2,WR,已收到,(b),准备接收这个帧,0,1,2,3,4,5,6,7,0,1,2,WR,已收到,(c),ACK,3.5.3 选择重传 ARQ 协议,可加大接收窗口，先收下发送序号不连续但仍处在接收窗口中的那些数据帧。等到所缺序号的数据帧收到后再一并送交主机。 选择重传 ARQ 协议可避免重复传送那些本来已经正确到达接收端的数据帧。 但我们付出的代价是在接收端要设置具有相当容量的缓存空间。 对于选择重传 ARQ 协议，若用 n 比特进行编号，则接收窗口的最大值受下式的约束 WR 2n/2 (3-18),选择重传ARQ协议,接收窗口的最大值受下式约束： WR 2n /2 当接收窗口WR为最大时，WT=WR=2n /2。,不允许发送这些帧,0,1,2,3,4,5,6,7,0,1,2,WT,准备发送 0 号帧,(a),不允许接收这些帧,0,1,2,3,4,5,6,7,0,1,2,WR,已收到,(b),准备接收这些帧,0,1,2,3,4,5,6,7,0,1,2,WR,已收到,(c),ACK,不允许发送这些帧,0,1,2,3,4,5,6,7,0,1,2,WT,准备发送 0 号帧,(a),不允许接收这些帧,0,1,2,3,4,5,6,7,0,1,2,WR,已收到,(b),准备接收这些帧,0,1,2,3,4,5,6,7,0,1,2,WR,已收到,(c),ACK,知识点归纳,(六)局域网 1.局域网的基本概念与体系结构 分析LAN特性的三个方面：传输介质、拓扑结构、介质访问控制方法（MAC），其中MAC最重要。 传输介质：双绞线、同轴电缆、光纤、无线电、红外 拓扑结构：星形、总线形、环形、树形,冲突(碰撞)Collision 以太网上由于多台计算机争用传输介质，两台或以上计算机发出的信号在同一段介质上叠加，而引起的信号错误。,局域网拓扑、传输介质与介质访问控制方法的分类,介质访问控制方法: 带有冲突检测的载波侦听多路访问CSMA/CD 令牌总线 token bus 令牌环 token ring,局域网拓扑、传输介质与介质访问控制方法的分类,知识点归纳,IEEE在1980年2月成立了局域网标准化委员会（简称IEEE 802 委员会），专门从事局域网的协议制订，形成了一簇的标准，称为IEEE 802标准。该标准已被国际标准化组织ISO采纳，作为局域网的国际标准系列，称为ISO 8802标准。在这些标准中，根据局域网的多种类型，规定了各自的拓朴结构、帧格式、媒体访问控制方法等内容。 IEEE 802.1是局域网的体系结构、网络管理和网际互连协议。 IEEE 802.2规范了数据链路层与媒体无关的部分，放在 LLC子层。 LLC（Logical Link Control） 逻辑链路控制子层，负责完成通常意义下的数据链路层功能，如差错控制、流量控制等。 MAC（Media Access Control） 介质访问控制子层，专门负责解决设备使用共享信道的问题。,涉及与媒体访问有关的放MAC子层，根据具体网络的媒体访问控制方法分别处理。其中主要的MAC协议有： IEEE 802.3载波监听多路访问/冲突检测CSMA/CD访问方法和物理层协议； IEEE 802.4令牌总线（Token Bus）访问方法和物理层的协议；其物理上是总线结构，逻辑上是令牌环； IEEE 802.5令牌环（Token Ring）访问方法和物理层协议； IEEE 802.11是无线局域网的介质访问方法和物理层协议；(WiFi),知识点归纳,知识点归纳,由于 Internet 发展很快， 而 TCP / IP 体系经常使用的局域网是 DIX Ethernet II 标准的网络，而不大用 IEEE 802.3 标准中的几种局域网，因此现在 IEEE 802 委员会制定的逻辑链路控制子层 LLC（即 802.2 标准）的作用已经不大， 只用于一些局域网体系结构分析的文章中， 很多厂商生产的网卡上就仅装有 MAC 协议而没有 LLC 协议，在分析实际的 TCP / IP 网络时要注意这一点。,具有冲突检测的载波监听多路访问 CSMA/CD： 工作原理： 1）先听后发 2）边听边发 3）冲突停止 4）随机重传,知识点归纳（ CSMA/CD ）,载波监听多点接入/碰撞检测CSMA/CD,“载波监听”是指每一个站在发送数据之前先要检测一下总线上是否有其他计算机在发送数据，如果有，则暂时不要发送数据，以免发生碰撞。 总线上并没有什么“载波”。因此， “载波监听”就是用电子技术检测总线上有没有其他计算机发送的数据信号。,碰撞检测,“碰撞检测”就是计算机边发送数据边检测信道上的信号电压大小。 当几个站同时在总线上发送数据时，总线上的信号电压摆动值将会增大（互相叠加）。 冲突检测方法： （1） 比较接收到的信号电压的大小 或（2） 检测曼彻斯特编码的过零点 或（3） 比较接收到的信号与刚发出的信号,检测到碰撞后,在发生碰撞时，总线上传输的信号产生了严重的失真，无法从中恢复出有用的信息来。 每一个正在发送数据的站，一旦发现总线上出现了碰撞，就要立即停止发送，免得继续浪费网络资源，然后等待一段随机时间后再次发送。,电磁波在总线上的 有限传播速率的影响,当某个站监听到总线是空闲时，也可能总线并非真正是空闲的。 A 向 B 发出的信息，要经过一定的时间后才能传送到 B。 B 若在 A 发送的信息到达 B 之前发送自己的帧(因为这时 B 的载波监听检测不到 A 所发送的信息)，则必然要在某个时间和 A 发送的帧发生碰撞。 碰撞的结果是两个帧都变得无用。,1 km,A,B,t,t = 0,单程端到端 传播时延记为,1 km,A,B,t,t = B 检测到信道空闲 发送数据,t = / 2 发生碰撞,A,B,A,B,t = 0 A 检测到 信道空闲 发送数据,A,B,t = 0,A,B,单程端到端 传播时延记为,重要特性,使用 CSMA/CD 协议的以太网不能进行全双工通信而只能进行双向交替通信（半双工通信）。 每个站在发送数据之后的一小段时间内，存在着遭遇碰撞的可能性。 这种发送的不确定性使整个以太网的平均通信量远小于以太网的最高数据率。,4. 争用期,最先发送数据帧的站，在发送数据帧后至多经过时间 2 （两倍的端到端往返时延）就可知道发送的数据帧是否遭受了碰撞。 以太网的端到端往返时延 2 称为争用期，或碰撞窗口。 经过争用期这段时间还没有检测到碰撞，才能肯定这次发送不会发生碰撞。,二进制指数类型退避算法 (truncated binary exponential type),发生碰撞的站在停止发送数据后，要推迟（退避）一个随机时间才能再发送数据。 确定基本退避时间，一般是取为争用期 2。 定义重传次数 k ，k 10，即 k = Min重传次数, 10 从整数集合0,1, (2k 1)中随机地取出一个数，记为 r。重传所需的时延就是 r 倍的基本退避时间(r 2)。 当重传达 16 次仍不能成功时即丢弃该帧，并向高层报告。,争用期的长度,以太网取 51.2 s 为争用期的长度。 对于 10 Mb/s 以太网，在争用期内可发送512 bit，即 64 字节。 以太网在发送数据时，若前 64 字节没有发生冲突，则后续的数据就不会发生冲突。,最短有效帧长,如果发生冲突，就一定是在发送的前 64 字节之内。 由于一检测到冲突就立即中止发送，这时已经发送出去的数据一定小于 64 字节。 以太网规定了最短有效帧长为 64 字节，凡长度小于 64 字节的帧都是由于冲突而异常中止的无效帧。,强化碰撞,当发送数据的站一旦发现发生了碰撞时，除了立即停止发送数据外，还要再继续发送若干比特的人为干扰信号(jamming signal)，以便让所有用户都知道现在已经发生了碰撞。,人为干扰信号,A,B,t,B 也能够检测到冲突，并立即停止发送数据帧，接着就发送干扰信号。这里为了简单起见，只画出 A 发送干扰信号的情况。,随机重传,退避算法：为截断的二进制指数退避算法，来决定重发时延：从 0, 1, 2, ., 2k-1 中随机取一个数r，重发时延 = r (2)，其中 k = min 重发次数，10 ,4.3 以太网的 MAC 层 4.3.1 MAC 层的硬件地址,在局域网中，硬件地址又称为物理地址，或 MAC 地址。 802 标准所说的“地址”严格地讲应当是每一个站的“名字”或标识符。 但鉴于大家都早已习惯了将这种 48 bit 的“名字”称为“地址”，所以本书也采用这种习惯用法，尽管这种说法并不太严格。,网卡上的硬件地址,路由器,1A-24-F6-54-1B-0E,00-00-A2-A4-2C-02,20-60-8C-C7-75-2A,08-00-20-47-1F-E4,20-60-8C-11-D2-F6,路由器由于同时连接到两个网络上， 因此它有两块网卡和两个硬件地址。,网卡检查 MAC 地址,网卡从网络上每收到一个 MAC 帧就首先用硬件检查 MAC 帧中的 MAC 地址. 如果是发往本站的帧则收下，然后再进行其他的处理。 否则就将此帧丢弃，不再进行其他的处理。 “发往本站的帧”包括以下三种帧： 单播(unicast)帧（一对一） 广播(broadcast)帧（一对全体） 多播(multicast)帧（一对多）,4.3.2 两种不同的 MAC 帧格式,常用的以太网MAC帧格式有两种标准 ： DIX Ethernet V2 标准 IEEE 的 802.3 标准 最常用的 MAC 帧是以太网 V2 的格式。,MAC 帧,物理层,MAC 层,IP 层,以太网 V2 的 MAC 帧格式,在帧的前面插入的 8 字节中的第一个字段共 7 个字节， 是前同步码，用来迅速实现 MAC 帧的比特同步。 第二个字段是帧开始定界符，表示后面的信息就是MAC 帧。,为了达到比特同步， 在传输媒体上实际传送的 要比 MAC 帧还多 8 个字节,因特网的点对点协议 PPP,现在全世界使用得最多的数据链路层协议是 点对点协议 PPP (Point-to-Point Protocol) 用户使用拨号电话线接入因特网时，一般都 是使用 PPP 协议； 两个路由器间的点到点链路上也可以使用PPP协议。,用户拨号入网的示意图,路由器,调制解调器,调制解调器,因特网服务提供者(ISP),用户家庭,拨号电话线,使用 TCP/IP 的 PPP 连接,路由选择 进程,至 因 特 网,PC 机,PPP 协议,1992 年制订了 PPP 协议。经过 1993 年和 1994 年的修订，现在的 PPP 协议已成为因特网的正式标准 RFC 1661 PPP协议有三个组成部分 一个将 IP 数据报封装到串行链路的方法 链路控制协议 LCP(Link Control Protocol) 网络控制协议 NCP(Network Control Protocol),PPP 协议的帧格式,PPP 有一个 2 个字节的协议字段。 当协议字段为 0x0021 时，PPP 帧的信息字段就是IP 数据报。 若为 0xC021, 则信息字段是 PPP 链路控制数据。 若为 0x8021，则表示这是网络控制数据。,IP 数据报,1,2,1,1,字节,1,2,不超过 1500 字节,PPP 帧,先发送,7E,FF,03,F,A,C,FCS,F,7E,协议,信 息 部 分,首部,尾部,PPP 透明传输问题,当 PPP 用在同步传输链路时，协议规定采用 硬件来完成0比特填充（和 HDLC 的做法一 样）； 当 PPP 用在异步传输时，就使用一种特殊的 字符填充法。,PPP 字符填充法,将信息字段中出现的每一个 0x7E 字节转变成 为 2 字节序列 (0x7D, 0x5E) 若信息字段中出现一个 0x7D 的字节, 则将其 变成为 2 字节序列 (0x7D, 0x5D) 若信息字段中出现 ASCII 码的控制字符（即 数值小于 0x20 的字符），则在该字符前面要 加入一个 0x7D 字节，同时将该字符的编码加 以改变,不提供使用序号和确认的可靠传输,PPP 协议之所以不使用序号和不使用确认机制是出于以下的考虑： 在数据链路层出现差错的概率不大时，使用比较简单的 PPP 协议较为合理 在因特网环境下，PPP 的信息字段放入的数据是 IP 数据报。数据链路层的可靠传输并不能够保证网络层的传输也是可靠的 帧检验序列 FCS 字段可保证无差错接受,PPP 协议的工作状态,当用户拨号接入 ISP 时，路由器的调制解调器对拨号 做出确认，并建立一条物理连接。 PC 机向路由器发送一系列的 LCP 分组（封装成多个 PPP 帧), 这些分组及其响应选择一些 PPP 链路参数 。 接着进行网络层配置，交互的NCP分组 给新接入的 PC机分配一个临时的 IP 地址，PC 机成为因特网上的一个主机。 通信完毕时，NCP 释放网络层连接，收回原来分配出去的 IP 地址。接着，LCP 释放数据链路层连接。最后 释放物理层连接。,PPP 协议的状态图,知识点归纳,（八）数据链路层设备： 网桥（透明网桥、源路径网桥）、 交换机 网桥的概念： 网桥是一种存储转发设备，用来连接类型相似的局域网。从协议层次看，网桥属于链路层范畴，该层对数据帧进行存储转发。它既不同于只作单纯信号放大、再生增强的转接器（中继器）,也不同于网络层进行转发的路由器。,(1) 在物理层扩展局域网,物理层扩展设备： 中继器（Repeater）和集线器（Hub）,中继器,作用 在物理层上实现局域网网段的扩展，主要起到信号再生、放大、延长网络距离的作用。 优点 安装简单、使用方便、价格便宜。 缺点 不能够无限制地扩展网络长度。 中继器处理的对象是数据比特，它不能识别数据链路层的帧格式或网络层的分组格式。不提供网段之间的隔离。 注意：中继器、放大器两者之间的