ch3：直接连接的网络课件

知识回顾知识回顾（5）数据通信基础数据通信模型传输媒体编码和复用交换技术PCM接入网1第第3章章直连连接的网络直连连接的网络2一个大规模的网络可以看作是由这些直接连接的网络通过路由器连接而成的。直接连接的网络就是大规模网络中的某“一跳”。本章关注：直接连接的网络直接连接的网络3学习提示学习提示目的理解数据链路层服务，掌握可靠数据传输和多路访问原理，熟练掌握各种链路层协议与设备重要知识点成帧差错检测可靠数据传输多路访问技术学习方法以基础性问题为中心展开学习MAC地址CSMA/CD以太网交换机IEEE 802.114直连连接的网络直连连接的网络中的机制和设备中的机制和设备5成帧差错检测和纠错可靠数据传输多路访问以太网局域网交换机机制设备在其他层可用什么是链路什么是链路?6通信媒体通信媒体网网络适配器适配器工作场景工作场景最简单网络：用某种传输媒体连接所有主机涉及数据链路层技术单段链路使用点到点点到点通信协议或广播多路访问协议为大型网络提供某“一跳”的低层通信支撑以太网无线局域网路由器IP网络通信网7第第3章章 内容提要内容提要3.1 链路层概述链路层概述3.2 成帧成帧3.3 差错检测和纠正技术差错检测和纠正技术3.4 可靠数据传输原理可靠数据传输原理3.5 多路访问协议多路访问协议3.6 以太网以太网3.7 链路层交换机链路层交换机3.8 802.11无线局域网无线局域网3.9 小结小结83.1数据链路层概述数据链路层概述数据链路层使用的信道主要有以下两种类型：数据链路层使用的信道主要有以下两种类型：点对点信道。这种信道使用一对一的点对点通信方。这种信道使用一对一的点对点通信方式。式。广播信道。这种信道使用一对多的广播通信方式，。这种信道使用一对多的广播通信方式，因此过程比较复杂。广播信道上连接的主机很多，因此过程比较复杂。广播信道上连接的主机很多，因此必须使用专用的共享信道协议来协调这些主机因此必须使用专用的共享信道协议来协调这些主机的数据发送。的数据发送。9数据链路层的简单模型数据链路层的简单模型局域网广域网主机 H1主机 H2路由器 R1路由器 R2路由器 R3电话网局域网主机 H1 向 H2 发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2从层次上来看数据的流动10数据链路层的简单模型数据链路层的简单模型(续）续）局域网广域网主机 H1主机 H2路由器 R1路由器 R2路由器 R3电话网局域网主机 H1 向 H2 发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2仅从数据链路层观察帧的流动11IP 数据报1010 0110帧取出数据链路层网络层链路结点 A结点 B物理层数据链路层结点 A结点 B帧(a)(b)发送帧接收链路IP 数据报1010 0110帧装入数据链路层传送的是帧12数据链路层像个数字管道数据链路层像个数字管道 常常在两个对等的数据链路层之间画出常常在两个对等的数据链路层之间画出一个数字管道，而在这条数字管道上传一个数字管道，而在这条数字管道上传输的数据单位是输的数据单位是帧帧。早期的数据通信协议曾叫作通信规程早期的数据通信协议曾叫作通信规程(procedure)。因此在数据链路层，规程。因此在数据链路层，规程和协议是同义语。和协议是同义语。结点结点帧帧13链路层环境链路层环境链路层协议通过单段链路，点到点传送上层数据报链路两端结点间交互的帧格式，发送和接收帧时的操作两种网络链路类型点对点链路和广播链路链路层环境重要特点一条路径上的不同链路可运行不同的链路层协议链路层协议提供的服务可能不同通信环境较为简单14利用不同交通工具旅游的例子利用不同交通工具旅游的例子北京杭州黄山15首都机场杭州机场黄山火车站链路层协议的任务：将上层交付的数据报通过单段链路从一个结点传输到相邻的结点。链路层的服务链路层的服务16链路层服务的设计问题链路层服务的设计问题1.成帧将数据报封装进帧，加上首部和尾部确定帧的边界用媒体访问控制(MAC)地址标识源、目的地问题：使用物理地址而不是IP地址!2.媒体访问点到点链路：简单多点共享：需要进行协调173.相连结点间的可靠交付是网络中基础性问题在比特差错低的链路很少使用(光纤，双绞线)无线链路:高差错率则需要问题:何时使用?链路层服务的设计问题链路层服务的设计问题(续续)18链路层服务的设计问题链路层服务的设计问题(续续)4.流量控制相邻发送和接收结点间的步调一致5.差错检测差错由信号衰减、噪声所致接收方检测出差错，将帧丢弃发送方负责重传6.纠错接收方识别和纠正比特差错，而不采取重传19网络适配器及其与协议栈功能的关系网络适配器及其与协议栈功能的关系问题：链路层功能在哪里？网络适配器驱动程序发送结点帧接收结点数据报帧适配器适配器链路层协议20第第3章章 内容提要内容提要3.1 链路层概述3.2 成帧成帧3.3 差错检测和纠正技术差错检测和纠正技术3.4 可靠数据传输原理可靠数据传输原理3.5 多路访问协议多路访问协议3.6 以太网以太网3.7 链路层交换机链路层交换机3.8 802.11无线局域网无线局域网3.9 小结小结213.2 成帧成帧成帧(framing)就是在一段数据的前后分别添加首部和尾部，然后就构成了一个帧。确定帧的界限。首部和尾部的一个重要作用就是进行帧定界。帧结束帧首部IP 数据报帧的数据部分帧尾部数据链路层的帧长开始发送帧开始22面向比特的协议把帧看成比特的集合面向比特的协议把帧看成比特的集合开始序列和结束序列：开始序列和结束序列：01111110（7EH）（1）面向比特的协议面向比特的协议23为区分开始序列（结束序列）与其他地方的01111110比特填充(bit stuffing)法(用于发送前/接收后)发送方：报文中5个连续1，插入0接收方：收到5个连续1：后为0，去掉；为1，后为0，则帧结束；否则出错24（1）面向比特的协议面向比特的协议用户到用户到 ISP 的链路使用的链路使用 PPP 协议协议 用户至因特网已向因特网管理机构申请到一批 IP 地址ISP接入网PPP 协议（2）PPP协议协议25（2）PPP协议协议点对点协议(PPP)家庭主机到第一跳路由器的点对点链路点对点链路的链路层协议26协议代码 上层协议标志字段 F=0 x7E（符号“0 x”表示后面的字符是用十六进制表示。十六进制的 7E 的二进制表示是 01111110），表示一个帧的开始或结束。地址字段 A 只置为 0 xFF。地址字段实际上并不起作用。控制字段 C 通常置为 0 x03。帧校验序列FCS。27PPP 有一个 2 个字节的协议字段。当协议字段为 0 x0021 时，PPP 帧的信息字段就是IP 数据报。若为 0 xC021,则信息字段是 PPP 链路控制协议LCP的数据。若为 0 x8021，则表示这是网络层的控制数据。28透明传输问题透明传输问题 当 PPP 用在异步传输时，使用一种特殊的字符填充法。29字符填充字符填充 将信息字段中出现的每一个 0 x7E 字节转变成为 2 字节序列(0 x7D,0 x5E)。若信息字段中出现一个 0 x7D 的字节,则将其转变成为 2 字节序列(0 x7D,0 x5D)。若信息字段中出现 ASCII 码的控制字符（即数值小于 0 x20 的字符），则在该字符前面要加入一个 0 x7D 字节，同时将该字符的编码加以改变。30零比特填充零比特填充 PPP 协议用在 SONET/SDH 链路时，是使用同步传输（一连串的比特连续传送）。这时 PPP 协议采用零比特填充方法来实现透明传输。具体做法：在发送端，只要发现有 5 个连续 1，则立即填入一个 0，从而保证在信息字段中不会出现6个连续1。接收端对帧中的比特流进行扫描。每当发现 5 个连续1时，就把这 5 个连续 1 后的一个 0 删除，310 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 比特零比特填充32（3）面向字节的协议面向字节的协议每帧都看成是字节的集合保留一组字符为控制字符效率较低，目前已很少使用DLE字符的“转义”作用33第第3章章 内容提要内容提要3.1 链路层概述3.2 成帧3.3 差错检测和纠正技术差错检测和纠正技术差错检测和纠正技术差错检测和纠正技术奇偶校验奇偶校验检验和方法检验和方法循环冗余检测循环冗余检测(CRC)3.4 可靠数据传输原理可靠数据传输原理3.5 多路访问协议多路访问协议3.6 以太网以太网3.7 链路层交换机链路层交换机3.8 802.11无线局域网无线局域网3.9 小结小结343.3 差错检测和纠错技术差错检测和纠错技术 比特差错检测和纠错是链路层可以提供比特差错检测和纠错是链路层可以提供的两种重要服务：从一个结点发送一个链路的两种重要服务：从一个结点发送一个链路层帧到另一个相邻结点，检测和纠正该帧中层帧到另一个相邻结点，检测和纠正该帧中的比特差错。的比特差错。35处理处理帧差错两种方法帧差错两种方法方法方法1：检错：检错重重发发(detect and retransmission)检测到发送方报文受损，则通知发送方重传副本差错率低效果好方法方法2：前向纠错前向纠错(Forward Error Correction,FEC)纠错通过额外信息“预先”进行时效性好适用场合检错重发适合链路差错率很低的场合，如有线通信前向纠错适合对时间要求很高的场合，如航天和实时控制36差错检测差错检测EDC=差错检测和纠错比特(冗余)D =数据由差错校验保护，可能包括首部字段 差错检测不是100%可靠!协议可能漏掉某些差错，但是非常少 较大的EDC字段产生更好的检测和纠正37 易出现比特错链路 （1）奇偶校验）奇偶校验单比特奇偶校验:检测单个比特差错检测单个比特差错二维比特奇偶校验:检测和纠正单个比特差错检测和纠正单个比特差错00奇偶比特奇偶差错奇偶差错可纠正的单比特差错无差错38数据比特（2）互联网检验和）互联网检验和发送方:将段内容作为16比特整数序列来处理检验和:段内容相加(补码和)发送方将检验和的值放入 UDP 检验和字段接收方:计算接收到段的检验和检查是否计算的检验和等于 检验和字段的值:NO 检测到差错YES 没有检测到差错，仍可能有错目标：检测传输段中的“差错”(如比特翻转)(注意:通常用于网络层和传输层，不是链路层)3940互联网互联网检验和例子检验和例子注意：当作加法时，最高位进比特位的进位需要加到结果中例子:3个16 bit的整数1100011001100110，1111010101010101，1000111100001100相加1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 11 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 11 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 0 0 0 1 1 0 01 1 0 1 1 0 1 0 0 1 0 1 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 0 11 0 1 0 0 1 0 1 1 0 1 0 0 1 1 1 0回卷 和检查和(求反)和回卷 41互联网检验和检错效果互联网检验和检错效果 对不同的报文，容易找到具有相同检验和的另一段报文:I O U 10 0.99 B O B49 4F 55 3130 30 2E 3939 42 D2 42messageASCII formatB2 C1 D2 ACI O U 90 0.19 B O B49 4F 55 3930 30 2E 3139 42 D2 42messageASCII formatB2 C1 D2 AC不同的报文但相同的检验和!效果不好!报文 报文 ASCII形式 ASCII形式（3）循环冗余码校验）循环冗余码校验(Cyclic Redundancy Check)将数据比特D看作一个二进制数选择r+1比特模式(生成式)G 目标：选择r个CRC 比特R,使得 被G整除(以2为模)接收方知道G,用G除以。如果有非零余数：检测到差错!能够检测所有小于r+1比特的突发差错广泛用于以太网,HDCL中比特模式数学公式被发送的数据比特42冗余码的计算举例冗余码的计算举例 现在 k=6,M=101001。设 n=3,除数 P=1101，被除数是 2nM=101001000。模 2 运算的结果是：商 Q=110101，余数 R=001。把余数 R 作为冗余码添加在数据 M 的后面发送出去。发送的数据是：2nM+R 即：101001001，共(k+n)位。43 110101 Q(商)P(除数)1101 101001000 2nM(被除数)1101 1110 1101 0111 0000 1110 1101 0110 0000 1100 1101 001 R(余数)，作为 FCS 循环冗余检验的原理说明循环冗余检验的原理说明 44CRC例子例子希望:D.2r XOR R=nG等价为:D.2r=nG XOR R 等价为:如果用G除以D.2r,余数为 RR=余数 D.2rG45知识回顾（知识回顾（6）链路层的服务成帧差错检测与纠错46第第3章章 内容提要内容提要3.1 链路层概述3.2 成帧3.3 差错检测和纠正技术3.4 可靠数据传输原理可靠数据传输原理可靠数据传输原理可靠数据传输原理设计可靠数据传输协议设计可靠数据传输协议流水线可靠数据传输协议流水线可靠数据传输协议回退回退N步协议步协议选择重传协议选择重传协议3.5 多路访问协议多路访问协议3.6 以太网以太网3.7 链路层交换机链路层交换机3.8 802.11无线局域网无线局域网3.9 小结小结47可靠数据传输：服务模型与服务实现可靠数据传输：服务模型与服务实现可靠数据传输是互联网中最为重要的问题之一该问题在多层协议中出现48（1）设计可靠数据传输协议设计可靠数据传输协议 基本思路：在传输过程中进行差错检测，一旦接收方发现错误，就告知发送方，由发送方重传学习方法：研究一系列协议，一步解决一个问题，直至实用49设计可靠数据传输协议设计可靠数据传输协议：SW0协议协议前提：信道不丢包解决方案：接收方：收到正确PKT，发送一个肯定确认肯定确认(ACK)，收到错误PKT，发送一个否定确认否定确认(NAK)发送方：发送分组PKT后，等待确认，收到ACK,接着发送下一个PKT；收到NAK，重传原PKT停止等待停止等待(stop-and-wait,SW)协议50 思考思考 实际的信道是存在丢包的，这时，实际的信道是存在丢包的，这时，SW0会出会出现什么问题？现什么问题？互相等待而死锁。互相等待而死锁。设计可靠数据传输协议设计可靠数据传输协议：SW0协议协议51设计可靠数据传输协议设计可靠数据传输协议：SW1协议协议信道丢包若分组或ACK丢失，SW0的发送方会一直等待ACK，引起协议死锁SW1的解决方案：增加超时定时器每发PKT，启动超时定时器，称为超时重传机制重传时间略大于RTT52发送方：每当发送完一个分组发送方：每当发送完一个分组PKT，就启动，就启动一个超时计时器，若到了超时计时器所设置一个超时计时器，若到了超时计时器所设置的时间仍未收到接收方的确认，就重传。的时间仍未收到接收方的确认，就重传。简化：接收方不再发送简化：接收方不再发送NAK，当收到错误的分，当收到错误的分组，就简单丢弃，无需发送组，就简单丢弃，无需发送NAK，只等待发，只等待发送方的超时重传。送方的超时重传。设计可靠数据传输协议设计可靠数据传输协议：SW1协议协议53 思考思考 1.当数据分组丢失时，当数据分组丢失时，SW1会出现问题吗？什么问题？会出现问题吗？什么问题？无无 2.当确认分组丢失时，当确认分组丢失时，SW1会出现问题吗？什么问题？会出现问题吗？什么问题？接收到重复帧接收到重复帧设计可靠数据传输协议设计可靠数据传输协议：SW1协议协议54设计可靠数据传输协议设计可靠数据传输协议：SW2协议协议若确认分组丢失SW1问题:出现了分组冗冗余余的差错SW2解决方案：增加一种新机制：发送发送序号序号55发方：每发送一个新的分组就将其发送序号加发方：每发送一个新的分组就将其发送序号加1收方：收到冗余的分组，就丢弃，并且发送收方：收到冗余的分组，就丢弃，并且发送ACK设计可靠数据传输协议设计可靠数据传输协议：SW2协议协议56问题问题1 在在SW2中，接收方收到重复的分组，就丢弃，中，接收方收到重复的分组，就丢弃，但是为什么还要发送但是为什么还要发送ACK呢？呢？设计可靠数据传输协议设计可靠数据传输协议：SW2协议协议57问题问题2SW2中发送序号需要几位二进制中发送序号需要几位二进制?1位即可。又称交替比特协议位即可。又称交替比特协议设计可靠数据传输协议设计可靠数据传输协议：SW2协议协议58思考思考 对于对于SW2，如果过早超时，会出现什么问题？，如果过早超时，会出现什么问题？接收方：收到重复的分组接收方：收到重复的分组 发送方：收到重复的确认发送方：收到重复的确认设计可靠数据传输协议设计可靠数据传输协议：SW2协议协议59设计可靠数据传输协议设计可靠数据传输协议：SW3协议协议若发送方过早超时SW2问题：收到重复的确认，无法分辨对应哪个分组SW3解决方案：增加确认序号机制，分辨出确认对应哪个分组综合以上机制为综合以上机制为SW协议，协议，或或自动重传请求自动重传请求(ARQ)设计可靠数据传输协议机制设计可靠数据传输协议机制：差错检测、接收方确认差错检测、接收方确认(肯定/否定)、重、重传、定时器和序号传、定时器和序号(数据和确认)60总结归纳：总结归纳：设计可靠数据传输协议要使用的机制：设计可靠数据传输协议要使用的机制：差错检测差错检测接收方确认接收方确认重传重传定时器定时器序号序号设计可靠数据传输协议设计可靠数据传输协议61有限状态机有限状态机(FSM)用形式化技术和数学方法来描述和验证协议FSM是一种描述和验证协议的形式化技术箭头指示协议从一个状态变迁到另一个状态引起变迁的事件事件显示在表示变迁的横线上方上方，事件发生时所采取的动作动作显示在横线下方下方如果对一个事件没有动作，或没有就事件发生而采取了一个动作，横线上方或下方使用符号 发送方和接收方有各自的FSM62SW协议协议的的有限状态机有限状态机(发送方发送方)63第第3章章 内容提要内容提要3.1 链路层概述3.2 成帧3.3 差错检测和纠正技术3.4 可靠数据传输原理可靠数据传输原理可靠数据传输原理可靠数据传输原理设计可靠数据传输协议设计可靠数据传输协议流水线可靠数据传输协议流水线可靠数据传输协议回退回退N步协议步协议选择重传协议选择重传协议3.5 多路访问协议多路访问协议3.6 以太网以太网3.7 链路层交换机链路层交换机3.8 802.11无线局域网无线局域网3.9 小结小结64流水线流水线:提高协议利用率提高协议利用率65流水线协议例子流水线协议例子2.5Gbps光传输系统，RTT为35ms。分组长L1,500 byte，发送时延信道的利用率实际的协议一次至少允许连续发送256个分组，协议效率至少提高256倍!66（2）流水线可靠数据传输协议）流水线可靠数据传输协议流水线:发送方允许发送多个、传输中、未应答的分组必须增加序号范围发送方和/或接收方设有缓冲67如何处理流水线差错？如何处理流水线差错？当流水线差错时，对所需序号窗口和缓冲的要求取决于数据传输协议处理丢失、损坏及时延过大分组的方式恢复流水线差错的两种基本方法回退回退N步步(Go-Back-N，GBN)选择重传选择重传(Selective Repeat,SR)68第第3章章 内容提要内容提要3.1 链路层概述3.2 成帧3.3 差错检测和纠正技术3.4 可靠数据传输原理可靠数据传输原理可靠数据传输原理可靠数据传输原理设计可靠数据传输协议流水线可靠数据传输协议回退回退N步协议步协议选择重传协议选择重传协议3.5 多路访问协议多路访问协议3.6 以太网以太网3.7 链路层交换机链路层交换机3.8 802.11无线局域网无线局域网3.9 小结小结69允许发方可以连续发送多个一定数量的分组，允许发方可以连续发送多个一定数量的分组，而无需等待确认。而无需等待确认。维持一个发送窗口维持一个发送窗口发送窗口：允许发送方已经发送但还没有收发送窗口：允许发送方已经发送但还没有收到确认的分组序号的范围。到确认的分组序号的范围。（3）回退回退N步协议步协议(Go-Back-N)70（3）回退回退N步协议步协议(Go-Back-N)基序号：最早发送的未确认的分组序号。下个序号：最小的未使用的序号（即下一个待发分组的序号）0，基序号-1：已经发送而且已经确认的分组基序号，下个序号-1：已经发送但是未被确认下个序号，基序号+N-1：可以发送的分组=基序号+N：不能用的。71（3）回退回退N步协议步协议(Go-Back-N)发送方发送方:在分组首部需要K比特序号，2k=N“发送窗口”最大为N,允许N个连续的没有应答分组滑动窗口(流水线)已确认已发送但未确认可用但未发送不可用窗口长度N发送基序号 下一个序号 当收到确认后，窗口向右滑动。随着协议的运行，发送窗口在序号空间不断滑动，GBN协议也被称为“滑动窗口协议滑动窗口协议”72（3）回退回退N步协议步协议(Go-Back-N)ACK(n):确认所有的（包括序号n）的分组-“累计累计ACK”ACK”表示表示n n以及以及n n之前的分组都正确收到。之前的分组都正确收到。可能收到重复的ACK对每个传输中的分组用同一个计时器timeout(n):若超时，重传窗口中的分组n及所有以后高序号的分组73GBN协议协议例子例子发送窗口为3，序号范围为0，374GBN协议协议注意点注意点接收方根据滑动窗口的序号按序接收分组窗口中失序分组及后面将被丢弃发送方采用超时机制来重传出现丢失或差错的分组接收方采用累积确认的方式GBN协议的接收窗口的长度为1计算机网络：原理与实践75窗口内连续后面可能正确收到多个可以不一一确认第第3章章 内容提要内容提要3.1 链路层概述3.2 成帧3.3 差错检测和纠正技术3.4 可靠数据传输原理可靠数据传输原理可靠数据传输原理可靠数据传输原理设计可靠数据传输协议流水线可靠数据传输协议回退N步协议选择重传协议选择重传协议3.5 多路访问协议多路访问协议3.6 以太网以太网3.7 链路层交换机链路层交换机3.8 802.11无线局域网无线局域网3.9 小结小结76（4）选择重传）选择重传(Selective Repeat)接收方分别确认所有正确接收的报文段缓存分组,以便最后按序交付给上层发送方只需要重传没有收到ACK的分组发送方定时器对每个没有确认的分组计时发送窗口N个连续的序号也需要限制已发送但尚未应答分组的序号77问题：GBN是否还能够改善？(单一差错可能导致大量不必要重传)选择重传选择重传:发送方发送方/接收方窗口接收方窗口a.发送方看到的序号b.接收方看到的序号已经确认可用，还未发送发送，还未确认不可用可接受（窗口内）失序(已缓存)但未被确认期待，还未收到不可用 窗口长度N窗口长度N78发送基序号接收基序号下一个序号 选择重传算法选择重传算法上层传来数据上层传来数据:r如果窗口中下一个序号可用,发送报文段timeout(n):r重传分组n,重启其计时器ACK(n)在在发送基,发送基+N:r标记分组 n 已经收到r如果n 是最小未收到应答的分组，向前滑动窗口基指针到下一个未确认序号发送方分组分组n在在 接收基接收基,接收基接收基+N-1r发送 ACK(n)r失序:缓存r按序:交付(也交付所有缓存的按序分组),向前滑动窗口到下一个未收到报文段的序号分组分组n在在接收基接收基-N,接收基接收基-1rACK(n)其他其他:r忽略 接收方79选择重传的例子选择重传的例子8081SR:窗口长度问题窗口长度问题例子:序号:0,1,2,3窗口长度=3接收方：在(a)和(b)两种情况下，接收方没有发现两者间的差别!在(a)中不正确地将冗余的当新的，而(b)中不正确地将其当作冗余的问题:序号长度与窗口长度有什么关系?回答：窗口长度小于等于序号空间的一半可靠数据传输机制及用途小结可靠数据传输机制及用途小结机制机制用途和说明用途和说明检验和检验和用于检测在一个传输分组中的比特错误。定时器定时器用于检测超时/重传一个分组，可能因为该分组（或其ACK）在信道中丢失了。由于当一个分组被时延但未丢失（过早超时），或当一个分组已被接收方收到但从接收方到发送方的ACK丢失时，可能产生超时事件，所以接收方可能会收到一个分组的多个冗余拷贝。序号序号用于为从发送方流向接收方的数据分组按顺序编号。所接收分组的序号间的空隙可使该接收方检测出丢失的分组。具有相同序号的分组可使接收方检测出一个分组的冗余拷贝。确认确认接收方用于告诉发送方一个分组或一组分组已被正确地接收到了。确认报文通常携带着被确认的分组或多个分组的序号。确认可以是逐个的或累积的，这取决于协议。否定确认否定确认接收方用于告诉发送方某个分组未被正确地接收。否定确认报文通常携带着未被正确接收的分组的序号。窗口、流水线窗口、流水线发送方也许被限制仅发送那些序号落在一个指定范围内的分组。通过允许一次发送多个分组但未被确认，发送方的利用率可在停等操作模式的基础上得到增加。窗口长度可根据接收方接收和缓存报文的能力或网络中的拥塞程度，或两者情况来进行设置。8283第第3章章 内容提要内容提要3.1 链路层概述3.2 成帧3.3 差错检测和纠正技术3.4 可靠数据传输原理3.5 多路访问协议多路访问协议多路访问协议多路访问协议信道划分协议信道划分协议轮流协议轮流协议随机接入协议随机接入协议3.6 以太网以太网3.7 链路层交换机链路层交换机3.8 802.11无线局域网无线局域网3.9 小结小结84多路访问多路访问(multiple access)链路和协议链路和协议多路访问多路访问：多个发送/接收结点同时使用广播信道，协调它们共享一个信道的方式。85应用场景：信道资源紧缺，大量端系统或者频繁访问网络，或者以较小概率访问网络局域网环境，密集端系统通常使用多路访问方式多路访问协议：要求多路访问协议：要求共享单一广播信道两个或更多结点并行传输相互干扰碰撞：如果结点同时接收到两个或更多信号多路访问协议决定结点怎样共享信道的分布式算法，如决定何时结点能够传输？出现碰撞时如何分解？共享信道的通信必须使用信道本身!不能用带外信道来协调86理想的多路访问协议理想的多路访问协议速率R bps的广播信道1.当只有一个结点时，能够以速率R发送2.当有M个结点时，每个能以平均速率R/M发送3.分布式:无特殊结点来协调传输无同步时钟、时隙4.简单87多路访问多路访问MAC协议协议:分类分类有3种类型:信道划分将信道划分为较小的“段”(时隙，频率，编码)为每个结点分配一部分专用轮流结点轮流，信息较多的轮流发送的时间较长随机访问不划分信道，允许碰撞设法从“碰撞”恢复88问题：协议应用场景不同，设计协议的方法是否有所不同？信道划分信道划分MAC协议协议:TDMATDMA:时分多路访问“循环”访问信道每个站点在每个循环中获得固定长度时隙(长度=分组传输时间)不使用的时隙则空闲例子：6个站点的LAN,时隙1、3、4 有分组,时隙2、5、6 空闲(浪费)计算机网络：原理与实践89信道划分信道划分 MAC协议协议:FDMAFDMA:频分多路访问 信道频谱划分为频带每个站点分配固定的频带频带中未使用的传输时间空闲例子：6个站点的LAN,频带1、3、4 有分组,频带2、5、6 空闲(浪费)计算机网络：原理与实践90FDM和和TDM特点特点消除了碰撞且公平结点在每个帧时间内得到了专用的传输速率R/N bps若系统仅有少数几个有大量分组要发送的结点分配的频率或时隙被浪费适合场合所有结点都持续有大量数据发送CDMA是另一种信道划分协议2.3.2节91第第3章章 内容提要内容提要3.1 链路层概述3.2 成帧3.3 差错检测和纠正技术3.4 可靠数据传输原理3.5 多路访问协议多路访问协议多路访问协议多路访问协议信道划分协议轮流协议轮流协议随机接入协议随机接入协议3.6 以太网以太网3.7 链路层交换机链路层交换机3.8 802.11无线局域网无线局域网3.9 小结小结92两种轮流两种轮流 MAC协议协议轮询(有中心):主结点“邀请”从结点依次传输关注问题:轮询开销时延单点故障(主结点)令牌传递(无中心):控制令牌从一个结点顺序地传递到下一个令牌报文关注问题:令牌开销 时延单点故障(令牌消失)适用于希望共享信道但却无法预测访问结点的数量的场景93第第3章章 内容提要内容提要3.1 链路层概述3.2 成帧3.3 差错检测和纠正技术3.4 可靠数据传输原理3.5 多路访问协议多路访问协议多路访问协议多路访问协议信道划分协议轮流协议随机接入协议随机接入协议3.6 以太网以太网3.7 链路层交换机链路层交换机3.8 802.11无线局域网无线局域网3.9 小结小结94随机访问协议随机访问协议大量结点以小概率发送分组以信道全部速率R传输结点间无优先权协调两个或更多传输结点发送“碰撞”(小概率)随机访问MAC协议定义了:如何检测碰撞如何从碰撞中恢复(例如，经延迟后重新传输)随机访问MAC协议的实例:ALOHA时隙ALOHACSMA,CSMA/CD,CSMA/CA95ALOHA 一种用于解决在分组无线通信系统中分配广播信道的分布式方法。基本思想：当一个帧首次到达某结点时，立即广播；碰撞后，相关结点将以概率p重传该帧，否则，该结点以概论1-p等待一个帧的传输时间，等待后，再以概率p传输该帧，或者等待另一个帧的传输时间。96纯纯ALOHA非时隙ALOHA:无同步要求结点i的帧成功传输的条件在t0 发送与在t0-1,t0+1发送的其他帧无碰撞其他结点不传输的概率和不开始传输新帧概率均为给定结点i成功传输一帧的概率N个活跃结点时，ALOHA的效率是取 极限，得协议最大效率为 1/(2e)=0.18597增加一个条件:所有结点只能在时隙起点开始传输帧。时隙时隙ALOHA98时隙时隙ALOHA优点单个活跃结点能够连续地以信道的全速传输结点中的时隙需要同步简单缺点碰撞，浪费时隙空闲时隙结点能以小于传输分组的时间检测到碰撞结点时钟同步困难99时隙时隙ALOHA效率效率假定N个有许多帧要发送结点，每个时隙以概率p发送结点1在一个时隙中成功发送的概率=p(1-p)N-1任何结点成功发送的概率=Np(1-p)N-1对N结点为使效率最大化，求p*,使得Np(1-p)N-1最大化对许多结点，当N趋近无穷大，取Np(1-p)N-1 极限,得到1/e=0.37效率：效率：当有许多结点，且每个都有许多帧要发送时，成功时隙与总时隙的长期比值最多:信道用于有用传输的时间是37%！100ALOHA载荷与吞吐量关系载荷与吞吐量关系101效率载荷CSMA(载波侦听多路访问载波侦听多路访问)CSMA:发前先听（采用“载波侦听”）如果侦听到信道忙,推迟传输 如果侦听到信道空闲:传输整个帧边发边听（采用“碰撞检测”）发送时侦听到信道忙,立即停止；转发强化冲突信号人类类比:不要打断他人说话!难免两人同时讲话!问题：CSMA用于有线，ALOHA用于无线，CSMA能否用于无线环境？CSMA协议效率能否提高？102问题：既然发送前已经监听到信道空闲，为什么发送时还要继续监听信道？103电磁波在总线上的电磁波在总线上的有限传播速率的影响有限传播速率的影响 当某个站监听到总线是空闲时，也可能总线并非真正是空闲的。A 向 B 发出的信息，要经过一定的时间后才能传送到 B。B 若在 A 发送的信息到达 B 之前发送自己的帧(因为这时 B 的载波监听检测不到 A 所发送的信息)，则必然要在某个时间和 A 发送的帧发生碰撞。碰撞的结果是两个帧都变得无用。1041 kmABt碰撞t=2 A 检测到发生碰撞 t=B 发送数据B 检测到发生碰撞 t=t=0单程端到端传播时延记为 传播时延对载波监听的影响 1051 kmABt碰撞t=B 检测到信道空闲发送数据t=/2发生碰撞t=2 A 检测到发生碰撞 t=B 发送数据B 检测到发生碰撞 t=ABABAB t=0 A 检测到信道空闲发送数据ABt=0t=B 检测到发生碰撞停止发送STOPt=2 A 检测到发生碰撞STOPAB单程端到端传播时延记为 106CSMA碰撞碰撞发前先听，仍可出现碰撞:传播时延意味着两个结点也许不能听到其他结点传输碰撞:整个分组传输时间被浪费注意:距离与传播时延在决定碰撞概率中的作用107CSMA/CD(碰撞检测碰撞检测)CSMA/CD:载波侦听在短时间内检测到碰撞碰撞的传输尽快结束，以减少信道浪费碰撞检测:在有线的LAN中容易:测量信号强度，比较传输的和接收的信号在无线LAN中困难：碰撞可能听不到人类类比:礼貌的交谈者 问题：能否进一步提高CSMA效率？108数据帧干扰信号 TJ人为干扰信号人为干扰信号 ABTBt B 发送数据A 检测到冲突开始冲突信道占用时间A 发送数据B 也能够检测到冲突，并立即停止发送数据帧，接着就发送干扰信号。这里为了简单起见，只画出 A 发送干扰信号的情况。109CSMA/CD 碰撞检测碰撞检测110信道传播时延起关键作用 ,a越小，网络性能越好多路访问协议比较多路访问协议比较信道划分MAC协议在高负载时高效、公平地共享信道低负载时低效：信道访问中延时，当1个活跃结点时，甚至仅有分配了 1/N 带宽!随机访问MAC协议低负载是有效：单个结点能够全面利用信道高负载：碰撞开销大轮流协议兼有两方面的优点!111多路访问协议小结多路访问协议小结问题：对共享媒体你需要做些什么?信道划分,通过时间、频率或编码时分,频分轮流从中心站点轮询，令牌传递随机划分(动态的),ALOHA,S-ALOHA,CSMA,CSMA/CD载波侦听:在某些技术(有线)中容易，在另一些(无线)中困难CSMA/CD 用在以太网中CSMA/CA 用在 802.11中112第第3章章 内容提要内容提要3.1 链路层概述3.2 成帧3.3 差错检测和纠正技术3.4 可靠数据传输原理3.5 多路访问协议3.6 以太网以太网MAC地址地址CSMA/CD以太网技术标准以太网技术标准3.7 链路层交换机链路层交换机3.8 802.11无线局域网无线局域网3.9 小结小结113以太网以太网(Ethernet)占统治地位的有线LAN技术:100Mbs网卡低于$10!率先广泛使用的LAN技术比令牌LAN和ATM等更简单、便宜在速率竞赛中取胜:10 Mbps 10 Gbps Metcalfe的以太网草图114115以太网的广播方式发送以太网的广播方式发送 总线上的每一个工作的计算机都能检测到 B 发送的数据信号。由于只有计算机 D 的地址与数据帧首部写入的地址一致，因此只有 D 才接收这个数据帧。其他所有的计算机（A,C 和 E）都检测到不是发送给它们的数据帧，因此就丢弃这个数据帧。具有广播特性的总线上实现了一对一的通信。116从总线拓扑到星型拓扑从总线拓扑到星型拓扑直到20世纪90年代，总线拓扑流行目前星型拓扑流行，可靠性提高中心为有源交换机每段单独运行以太网协议，此时结点相互没有碰撞(?)交换机总线：同轴电缆星形117以太网帧结构以太网帧结构发送适配器在以太网帧(或其他网络层协议分组)中封装IP数据报前导码（preamble）:模式为10101010 的7个字节，后跟模式为 10101011 的一个字节用于同步接收方，发送方时钟速率118以太网帧结构以太网帧结构(续续)地址:6字节如果适配器接收具有匹配的目的地址或广播地址(如ARP分组)的帧,它将帧中的数据提交给网络层协议否则,适配器丢弃帧类型:指示较高层协议(大多数为IP但也可以支持其他类型如 Novell IPX和AppleTalk)CRC:在接收方核对;如果检测到差错，该帧被丢弃119MAC地址地址LAN地址地址=物理地址物理地址=MAC地址地址，通常用6字节16进制表示如1a-03-65-3F-2e-46共有248个LAN地址IEEE地址分配方式：固定前24 bit，公司生成后24 bit，每个适配器具有唯一MAC地址适配器的MAC地址具有扁平(没有层次)结构，且保持不变120提供不可靠、无连接服务提供不可靠、无连接服务无连接:在发送和接收适配器之间没有握手不可靠:接收适配器不向发送适配器发送应答或否定应答传送给网络层的数据报流可能有丢包如果应用程序使用TCP，将能弥补丢包否则，应用程序将发现丢包以太网的MAC协议：无时隙的CSMA/CD121第第3章章 内容提要内容提要3.1 链路层概述3.2 成帧3.3 差错检测和纠正技术3.4 可靠数据传输原理3.5 多路访问协议3.6 以太网以太网MAC地址CSMA/CD以太网技术标准以太网技术标准3.7 链路层交换机链路层交换机3.8 802.11无线局域网无线局域网3.9 小结小结122以太网协议以太网协议(CSMA/CD)1.适配器从网络层接收数据报并生成帧2.如果适配器感知信道空闲，它开始传输帧；如果它感知信道忙，等待信道空闲再传输3.当适配器传输整个帧时，一直检测另一个帧的传输4.如果适配器传输过程中检测到另一次传输,中止并发送强化冲突信号5.中止后,适配器进入指数指数回退回退:在第m次碰撞后,适配器随机地从0,1,2,2m-1选择一个K值。适配器等待K512 比特时间并返回到第2步123以太网协议以太网协议(CSMA/CD)(续续)强化冲突信号:确保所有的其他传输方都知道碰撞;48 bit长比特时间:对10 Mbps 以太网传每比特需 0.1 s;对K=1023,等待时间约为50 msec 指数回退:目标：估计当前负载，适应重传尝试重负载:随机等待时间更长首次碰撞后:从0,1 中 选择K；时延是K*512 bit 传输时间第二次碰撞后:从0,1,2,3选择 K 10次碰撞后,从0,1,2,3,4,1023 选择K124CSMA/CD效率效率=LAN中的2站点之间的最大传播时间T0=传输最长帧的时间随着趋于0,效率趋于1随着T0趋于无穷大，效率趋于1比ALOHA好得多,而且分布、简单且便宜当a=/T0，效率 125第第3章章 内容提要内容提要3.1 链路层概述3.2 成帧3.3 差错检测和纠正技术3.4 可靠数据传输原理3.5 多路访问协议3.6 以太网以太网MAC地址CSMA/CD以太网技术标准以太网技术标准3.7 链路层交换机链路层交换机3.8 802.11无线局域网无线局域网3.9 小结小结126802.3 以太网标准以太网标准:链路链路&物理层物理层许多不同的以太网标准共同的MAC协议和帧格式不同的速率:2 Mbps,10 Mbps,100 Mbps,1Gbps,10G bps不同的物理层媒体应用层运输层网络层链路层物理层MAC协议和帧格式100BASE-TX100BASE-T4100BASE-FX100BASE-T2100BASE-SX100BASE-BX光纤物理层光纤物理层铜铜(双绞线双绞线)物理层物理层127第第3章章 内容提要内容提要3.1 链路层概述3.2 成帧3.3 差错检测和纠正技术3.4 可靠数据传输原理3.5 多路访问协议3.6 以太网3.7 链路层交换机链路层交换机转发和过滤转发和过滤自学习自学习链路层交换机的性质链路层交换机的性质3.8 802.11无线局域网无线局域网3.9 小结小结128集线器（集线器（Hub）是物理层“哑”中继器:来自一条链路的比特从其他所有链路出去与集线器连接的所有结点相互碰撞无帧缓存集线器无CSMA/CD:适配器检测碰撞129交换机交换机(Switch)链路层设备：比集线器智能化存储并转发以太网帧当帧在网段上转发时，检查帧首部并基于MAC目的地址，选择性地向一个或多个出链路转发帧当帧在网段上转发时，使用CSMA/CD 访问网段透明性主机不知道交换机的存在即插即用,自学习交换机不必配置130交换机交换机:并行传输扩大容量并行传输扩大容量端系统与交换机有专门的直接连接交换机缓存分组在入链路上使用以太协议：全双工，无碰撞每条链路是一个碰撞域交换:A到A和B到B能够同时无碰撞地进行而集线器无法办到!AABBCC具有6个接口的交换机(1,2,3,4,5,6)123456131交换机表交换机表问题:交换机如何知道经接口4可达A,经接口5可达B?交换机具有一个交换机表，每表项:(MAC地址,接口,时戳)问题:这些表项是如何创建的，谁维护交换机表?AABBCC123456具有6个接口的交换机(1,2,3,4,5,6)132交换机交换机:自学习自学习问题：交换机如何学习主机能够从哪个接口可达？当收到帧时，交换机“学习”发送方的位置：入LAN段在交换机表中记录下发送方/位置对AABBCC123456A ASource:ADest:AMAC地址 接口 TTL交换机表(初始为空)A160133交换机：帧过滤交换机：帧过滤/转发算法转发算法当交换机收到帧:1.记录与发送主机关联的链路2.使用MAC目的地址索引交换机表3.if 找到目的地项then if 目的地位于帧到达的段 then 丢弃帧(过滤)else 在指示的接口转发该帧(转发)else 洪泛向所有接口(除了该帧到达的)转发该帧134自学习、转发的例子自学习、转发的例子AABBCC123456A A源:A目的地:AMAC addr interface TTLA160A AA AA AA AA A帧目的地位置:洪泛A A目的地A位置已知：A460选择性发送交换机表(初始为空)135问题：多台端系统同时发送，它们之间是否使用了CSMA/CD?交换机互联交换机互联交换机能够连接在一起AB问题:从A 向G发送，S1 怎样知道要经过S4 和向G转发帧呢?回答:自学习!(进行与单交换机场合完全一样的过程!)S1CDEFS2S4S3HIG136多交换机自学习例子多交换机自学习例子假定C向I发送帧，I对C响应问题:显示在S1,S2,S3,S4中的交换机表和转发的分组？每个端口可能对应多个MAC地址ABS1CDEFS2S4S3HIG12137交换机交换机:流量隔离流量隔离交换机将子网分割成LAN段交换机过滤分组:相同LAN段的帧通常不在其他ALN段上转发段成为分离的碰撞域集线器集线器集线器交换机碰撞域碰撞域碰撞域138集线器集线器集线器交换机园区网园区网到外部网络路由器IP子网邮件服务器Web服务器139问题：交换机能否隔离广播帧？隔离：无法自学习？不隔离：广播帧是否会太多？交换机的其他问题交换机的其他问题直通交换:帧从输入端口到输出端口无需先收集整个帧少量地减少了时延共享/专用的结合,10/100/1000 Mbps接口140链路层交换机的特点链路层交换机的特点无碰撞无碰撞异质的链路异质的链路便于管理便于管理更安全更安全不能隔离广播报文不能隔离广播报文141生成树协议生成树协议起因：由于预留冗余路径形成环路，造成不断转发，很多重复帧，引发雪崩效应。生成树协议（STP）：当网络中存在备份链路时，仅允许主链路激活，只有主链路失效时，才激活备份链路。见:数据结构中图的生成树。142虚拟局域网虚拟局域网(VLAN)143第第3章章 内容提要内容提要3.1 链路层概述3.2 成帧3.3 差错检测和纠正技术3.4 可靠数据传输原理3.5 多路访问协议3.6 以太网3.7 链路层交换机3.8 802.11无线局域网无线局域网802.11体系结构体系结构802.11 MAC协议协议IEEE 802.11帧帧蓝牙蓝牙和和WiMAX3.9 小结小结144IEEE 802.11 无线无线 LAN：WiFi802.11b2.4-5 GHz无执照无线电频谱高达11 Mbps在物理层的直接序列扩频(DSSS)所有主机使用相同的码片速率序列 广泛设置，使用基站802.11a 5-6 GHz范围高达 54 Mbps802.11g 2.4-5 GHz范围高达54 Mbps对多路访问都使用CSMA/CA各标准有基站/自组织版145802.11 LAN 体系结构体系结构无线主机使用基站通信基站=接入点(AP)基本服务集(BSS)(又称为“单元”)在基础设施模式中包含:无线主机接入点(AP):基站自组织(Ad Hoc)模式:仅有主机BSS 1有唯一SSIDBSS 2因特网交换机或路由器APAP146802.11 LAN 体系结构体系结构147自组织模式无基站结点仅能传输到链路覆盖范围内的其他结点结点自行组织成为一个网络：经它们自身选路802.11:信道关联信道关联802.11b:2.4GHz-2.485GHz频谱划分为11个不同的频率 的信道AP管理为AP选择频率 可能干扰：与临近AP选择相同的信道!主机:必须与AP关联扫描信道，监听包括该AP的SSID和MAC地址的信标帧选择AP去关联可能执行鉴别 148第第3章章 内容提要内容提要3.1 链路层概述3.2 成帧3.3 差错检测和纠正技术3.4 可靠数据传输原理3.5 多路访问协议3.6 以太网3.7 链路层交换机3.8 802.11无线局域网无线局域网802.11体系结构802.11 MAC协议协议IEEE 802.11帧帧蓝牙蓝牙和和WiMAX3.9 小结小结149IEEE 802.11:多路访问多路访问避免碰撞:2+节点同时传输802.11:CSMA 在传输前感知不与正传输的其他节点碰撞而检测所有碰撞存在困难(即未检测到不代表无碰撞)!当传输时由于接收的信号变弱(衰减)，难以接收(感知碰撞)不能感知所有场合的碰撞：隐藏终端，信号衰减目标:避免碰撞 CSMA/C(ollision)A(voidance)ABCABCA的信号强度空间C的信号强度150隐藏终端现象信号衰减现象IEEE 802.11 MAC协议协议:CSMA802.11发送方1 如感知信道空闲则 在DIFS(Distributed Inter-帧 Space)后，传输整个帧(无碰撞检测)2 如感知信道忙，则启动随机回退时间：当信道空闲递减，忙则不变当定时器为0，发送数据帧3 如收ACK,跳转1；如未收ACK，增加随机回退间隔，跳转2802.11接收方-如果接收帧OK 在SIFS后返回后返回ACK 发送方接收方DIFSdataSIFSACK151避免碰撞避免碰撞CA(续续)思想:在数据帧访问之前，允许发送方“预约”信道：避免长数据帧的碰撞发送方首先使用CSMA向BS传输短请求发送(RTS)分组RTS仍可能与其他碰撞(但它们很短，浪费少!)BS响应RTS广播允许发送CTS所有站点听到该RTS，从而发送方传输数据帧其他站点推迟传输使用短预约分组，避免长数据帧碰撞降低效率!152问题：如何解决可能的碰撞问题？碰撞避免碰撞避免:RTS/CTS预约信道预约信道APAB时间RTS(A)RTS(B)RTS(A)CTS(A)CTS(A)DATA(A)ACK(A)ACK(A)预约碰撞推迟153第第3章章 内容提要内容提要3.1 链路层概述3.2 成帧3.3 差错检测和纠正技术3.4 可靠数据传输原理3.5 多路访问协议3.6 以太网3.7 链路层交换机3.8 802.11无线局域网无线局域网802.11体系结构802.11 MAC协议IEEE 802.11帧帧蓝牙蓝牙和和WiMAX3.9 小结小结154帧控制 持续