华中科技大学计算机网络课件-第5章-链路层和局域网(8)

计算机网络第5章链路层和局域网第五章链路层和局域网2020年4月7日2目录链路层：概述和服务差错检测和纠错技术多路访问协议链路层编址以太网链路层和交换机PPP：点对点协议第五章链路层和局域网2020年4月7日35.1链路层:概述和服务术语节点：主机和路由器链路：沿着通信路径连接相邻节点的通信信道有线链路无线链路帧：数据链路层的分组单元链路层的主要功能负责将数据报通过链路从一个节点传输到相邻的节点“链路”第五章链路层和局域网2020年4月7日45.1链路层:概述和服务链路层的简单模型局域网广域网主机H1主机H2路由器R1路由器R2路由器R3电话网局域网主机H1向H2发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2从层次上来看数据的流动第五章链路层和局域网2020年4月7日55.1链路层:概述和服务链路层的简单模型局域网广域网主机H1主机H2路由器R1路由器R2路由器R3电话网局域网主机H1向H2发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2仅从数据链路层观察帧的流动第五章链路层和局域网2020年4月7日65.1链路层:概述和服务几点特别说明数据报在不同链路上可能由不同的链路层协议进行处理例如：第一段链路上由PPP处理，最后一段链路上由以太网处理，中间链路上由广域链路层协议处理不同的链路层协议可能提供不同的服务例如：可靠传递、不可靠传递第五章链路层和局域网2020年4月7日75.1链路层:概述和服务链路层提供的服务成帧、链路介质访问将数据加上头部和尾部，封装成数据帧共享介质的信道访问帧头部用MAC地址标识源和目的（不同于IP地址）可靠交付很少用于误码率低的链路（光纤、双绞线链路）用于误码率高的链路（无线链路）流量控制在相邻的收发节点间限制流量第五章链路层和局域网2020年4月7日85.1链路层:概述和服务链路层提供的服务（续）差错检测信号衰减和电磁干扰噪声导致出错接收方若检测到错误存在：给发送方发送信号要求重传或丢弃该数据帧差错纠正接收方检测和纠正帧中错误，不用重传半双工和全双工半双工时，链路两端的节点都能传输分组，但不能同时传输第五章链路层和局域网2020/4/79适配器通信发送方帧接收方网络层数据报帧适配器卡适配器卡链路层协议链路层协议在适配器中实现(akaNIC)以太网卡,PCMCI卡,802.11卡发送方NIC:在一个帧内封装数据报增加差错检测位，可靠交付，流量检测等接收方NIC查找错误,可靠交付,流量控制等取出数据报，交给网络层适配器是半自治单元实现了链路层和物理层的功能第五章链路层和局域网2020年4月7日105.2差错检测和纠错技术差错检测模型EDC=ErrorDetectionandCorrectionbits差错检测和纠错比特D=Data差错检测位保护的数据，可包括首部数据报d数据比特数据报检测到差错易出现比特差错的链路在D’中的所有比特正确吗？第五章链路层和局域网2020年4月7日115.2差错检测和纠错技术单比特奇偶校验:检测单个比特错误二维奇偶校验:d个比特数据被划分为i行j列，产生i+j+1个奇偶比特可检测和纠正单个比特错误d个数据比特附加的一个比特使得d+1个比特中1的总数是偶数（偶校验）附加的一个比特使得d+1个比特中1的总数是奇数（奇校验）第五章链路层和局域网2020年4月7日125.2差错检测和纠错技术因特网检验和发送方将数据段的内容作为16比特的整数序列检验和：累加求和，计算和的反码发送方将得到的校验和值放入PDU校验和字段接收方计算收到的数据（包括检验和）的检验和检查计算出的结果是否为全1：NO–检测到错误YES–没有错误特别注意：仅用于TCP、UDP和IPv4协议中第五章链路层和局域网2020年4月7日135.2差错检测和纠错技术循环冗余校验码d比特的数据，D选择r＋1比特模式(生成多项式)，表示为G目标：选择r个CRC比特-R，以便D,R恰好能被G整除（模2计算）接收方已知G，用G去除D,R，若余数非0，则检测到错误能检测到所有少于r+1比特的错误在实践中被广泛应用（ATM，HDLC)等数据链路层协议，并用硬件实现D:被发送的数据比特R:CRC比特第五章链路层和局域网2020年4月7日145.2差错检测和纠错技术如果要:D*2rXORR=nG两边都异或R，得到:D*2r=nGXORR即:D*2r除以G,得到余数R第五章链路层和局域网2020年4月7日155.3多路访问协议两种链路点到点链路PPP广播链路(共享线路或介质)传统以太网802.11无线局域网第五章链路层和局域网2020年4月7日165.3多路访问协议广播链路的特点单个共享广播信道两个或多个节点同时传输：相互干扰碰撞：一个节点同时收到两个或多个信号多路访问协议：解决共享信道的访问控制分布式算法决定节点如何共享信道，如节点何时可以传输数据特别注意：有关共享信道的通信（协商）需使用信道本身没有额外的信道来进行协调第五章链路层和局域网2020年4月7日175.3多路访问协议理想的多路访问协议需满足（假定：信道为速率为Rb/s的广播信道）：当只有一个节点有数据发送时，该节点的吞吐量为R当M个节点有数据发送时，每个节点吞吐量为R/M分散没有特定节点用于调整传输没有时钟同步简单第五章链路层和局域网2020年4月7日185.3多路访问协议多路访问协议分类信道划分协议将信道划分成小的“片”（时隙、频率、CDMA编码）将“片”分配给节点使用随机访问协议信道没有被分割，允许碰撞碰撞恢复轮流协议节点轮流传送，但数据量大的节点轮流更长时间第五章链路层和局域网2020年4月7日195.3多路访问协议信道划分协议TDMA(TimeDivisionMultipleAccess)循环访问信道每个节点在每次循环中得到固定长度的时隙（时隙长度＝传输单个帧时间）没有数据发送的时隙空闲例如：6-节点LAN,时隙1,3,4有数据发送,2,5,6的时隙空闲第五章链路层和局域网2020年4月7日205.3多路访问协议信道划分协议FDMA(FrequenceDivisionMultipleAccess)信道按频谱分成若干频段每个节点分配固定频段在频段不用时该部分信道被闲置和浪费frequencybands第五章链路层和局域网5.3多路访问协议码分多址访问（CDMA）CDMA(CodeDivisionMutipleAccess):就是每个用户可以在同样的时间内用相同的频带进行通信。由于各用户使用经过特殊挑选的不同编码，因此不会造成干扰。这种通信信号具有很高的抗干扰能力。发送方发送的每个比特都通过乘以信号（编码片序列）比特进行编码每个用户被指派一个惟一的mbit码片序列。所有用户共享相同的频道,但每个用户用自己的“码片”序列对数据编码当站点发送比特“1”时，就发送指定给该站点的mbit码片序列；发送比特“0”时，发送此mbit码片序列的二进制反码习惯上，将码片序列中的“0”写成“-1”，“1”写成“+1”允许多个用户共存和发送信号,且相互的干扰极小2020年4月7日21第五章链路层和局域网5.3多路访问协议CDMA码片序列的特点：每一个站的码片序列各不相同，互相正交。即任何两个站点（如S和T站点）的码片向量的规格化内积为0。任何码片向量和自己的规格化内积为1。任何码片向量和其反码的规格化内积为－1。01iitsmTS11iissmSS1)(1)(iissmSS2020年4月7日22第五章链路层和局域网5.3多路访问协议数据码元比特tttttttS站的码片序列SS站发送的信号SxT站发送的信号Tx总的发送的信号Sx＋Tx规格化内积S＊Sx规格化内积S＊Tx发送端接收端110S站的码片序列是（-1-1-1+1+1-1+1+1），发送的数据是110T站的码片序列是（-1-1+1-1+1+1+1-1），发送的数据是110设有S站和T站均以相同频率发送数据，且接收站希望收到S站的数据，如下图所示。2020年4月7日23第五章链路层和局域网2020年4月7日245.3多路访问协议随机访问协议当节点有数据发送时以信道全部速率R传输没有主节点起协调作用两个或多个节点传送时——碰撞随机访问协议解决如何检测碰撞如何从碰撞中恢复（如：延时后重传）随机访问协议举例：ALOHA、时隙ALOHACSMA,CSMA/CD,CSMA/CA第五章链路层和局域网2020年4月7日255.3多路访问协议ALOHAALOHA的由来ALOHA乃AdditiveLinkOn-LineHAwaiisystem简写，ALOHA恰好还是夏威夷方言的“你好”。ALOHA网是计算机网络早期发展中一个著名的网络，也是第一个无线计算机网络，现仍在运行之中。ALOHA网的特征因群岛位置的散布，网络拓扑采用了星型结构；为节省费用和易于组网，网络中各站点的通信采用了无线传输介质。由于采用无线电信道，考虑到无法申请更多的频率点，因而所有站点都使用统一的频率通过主机交换信息。接口ALOHA系统的一般模型站1站2站n-1站n•••总线信道第五章链路层和局域网2020年4月7日265.3多路访问协议纯ALOHA站1t站2t站N-1t站Nt1234567t纯ALOHA系统的工作原理1234567冲突重发冲突重发冲突再重发发送成功冲突重发发送成功发送成功T0T0T0一个节点收到网络层的数据立即发送。如果传输的帧发生了碰撞，该节点在全部传输完碰撞帧后以概率p重传该帧，否则等待一帧的传输时间。等待时间结束后再以概率p重传该帧，或以概率1-p等待另一帧的传输时间。第五章链路层和局域网2020年4月7日275.3多路访问协议纯ALOHA的工作效率在任何给定的时间，一个节点传输一帧的概率是p，假设该帧在t0时刻发送，假设时间单位是一帧的发送时间。P(给定节点成功概率)=P(给定节点传送)*P(在[t0-1,t0]没有其它节点传送)*P(在[t0,t0+1]没有其它节点传送)=p.(1-p)N-1.(1-p)N-1=p.(1-p)2(N-1)任意一个节点传输成功的概率：Np.(1-p)2(N-1)…选择最合适p*，使任意一个节点传输成功的概率最大。当N趋于无穷时，求Np*.(1-p*)2(N-1)的极限=1/(2e)=0.184第五章链路层和局域网2020年4月7日285.3多路访问协议时隙ALOHA帧到达帧到达帧到达帧到达冲突重发冲突重发T01：所有帧正好由L比特组成2：带宽为R，一帧传输时间=L/R3:以L/R为单位划分时隙4：节点只在每个时隙的开始传输帧5:节点时钟同步，因此每个节点知道时隙什么时候开始6：如果一个节点发送的帧产生碰撞，该节点以概率p在后续的每个时隙重发该帧，直到该帧无碰撞地传输成功。第五章链路层和局域网2020年4月7日295.3多路访问协议时隙ALOHA的工作效率P(给定节点成功概率)=P(给定节点传送).P(没有其它节点传送)=p.(1-p)N-1任意一个节点传输成功的概率为Np.(1-p)N-1选择最合适p*，使任意一个节点传输成功的概率最大。当N趋于无穷时，求p*.(1-p*)N-1的极限=1/(e)=0.386。是纯ALOHA的2倍，因为同步机制，使得发生碰撞的可能性比纯ALOHA小。第五章链路层和局域网2020年4月7日305.3多路访问协议CSMA(CarrierSenseMultipleAccess)传输前监听如果信道空闲，传送整个帧如果信道忙，推迟传送为人处事的原则之一：不要打