数据链路层与局域网,1,第5章链路层与局域网LinkLayerandLANs,计算机网络：自顶向下方法(原书第三版)陈鸣译，机械工业出版社，2005年ComputerNetworking:ATopDownApproachFeaturingtheInternet,3rdedition.JimKurose,KeithRossAddison-Wesley,July2004.,数据链路层与局域网,2,第5章链路层和局域网,我们的目标:理解支撑数据链路层服务的原则:差错检测,纠正共享广播信道:多路访问链路层编址可靠数据传输,流量控制:前面已分析过各种链路层技术实例与实现,数据链路层与局域网,3,第5章链路层,5.1概述与服务5.2差错检测和纠错5.3多路访问协议5.4链路层编址,5.5以太网5.6集线器和交换机5.7PPP5.8链路虚拟化:ATM和MPLS,数据链路层与局域网,4,链路层:概述,某些术语:主机和路由器是节点连接沿通信路径的相邻节点的路径是链路有线链路无线链路局域网第二层的分组叫帧,封装数据报,数据链路层具有经一条链路从一个节点传输数据到相邻节点的能力,数据链路层与局域网,6,链路层Services,帧,链路访问:将数据报封装进帧，加上首部和尾部如果共享媒体，信道访问位于帧首部的“MAC”地址标识源、目的地不同于IP地址!相连节点间的可靠交付我们已经知道如何做了(第三章)!在比特差错低的链路很少使用(光纤，某些双绞线)无线链路:高差错率问题:为什么同时使用链路级和端到端可靠性?,数据链路层与局域网,7,链路层服务(续),流量控制:相邻发送和接收节点间的步调一致差错检测:差错由信号衰减、噪声所致接收方检测差错的存在信号发送方负责重传或丢弃帧纠错:接收方识别和纠正比特差错，而不采取重传半双工and全双工使用半双工,链路的两端节点能够传输，但不能同时,数据链路层与局域网,8,适配器通信,在“适配器”(又称为NIC)中实现链路层以太网卡，PCMCI卡,802.11卡发送侧:将数据报封装在帧中增加差错检测比特，可靠数据传输，流量控制,等,接收侧查找差错，可靠数据传输，流量控制,等提取数据报，传递到接收节点适配器是半自治的链路和物理层,发送节点,接收节点,数据报,适配器,适配器,链路层协议,数据链路层与局域网,9,第5章链路层,5.1概述与服务5.2差错检测和纠错5.3多路访问协议5.4链路层编址,5.5以太网5.6集线器和交换机5.7PPP5.8链路虚拟化:ATM和MPLS,数据链路层与局域网,10,差错检测,EDC=差错检测和纠错bits(冗余)D=数据由差错校验保护，可能包括首部字段差错检测不是100%可靠!协议可能漏掉某些差错，但是非常少较大的EDC字段产生更好的检测和纠正,数据链路层与局域网,11,奇偶校验,单比特奇偶校验:检测单个比特差错,二维比特奇偶校验:检测和纠正单个比特差错,0,0,奇偶比特,奇偶差错,奇偶差错,可纠正的单比特差错,无差错,数据链路层与局域网,12,互联网检查和,发送方:将段内容作为16比特整数序列来处理检查和:段内容相加(补码和)发送方将检查和的值放入UDP检查和字段,接收方:计算接收到段的检查和检查是否计算的检查和等于检查和字段的值:NO检测到差错YES没有检测到差错.尽管如此，还可能有错。详情见后.,目标：检测传输段中的“差错”(如比特翻转)(注意:仅用于运输层),数据链路层与局域网,13,检查和:循环冗余码校验,将数据比特D看作一个二进制数选择r+1比特模式(生成式),G目标：选择r个CRC比特R,使得被G整除(以2为模)接收方知道G,用G除以.如果有非零余数：检测到差错!能够检测所有小于r+1比特的突发差错广泛用于实践中(ATM,HDCL),比特模式,数学公式,被发送的数据比特,数据链路层与局域网,14,CRC例子,希望:D.2rXORR=nG等价为:D.2r=nGXORR等价为:如果我们用G除以D.2r,余数为R,R=余数,D.2rG,数据链路层与局域网,15,第5章链路层,5.1概述与服务5.2差错检测和纠错5.3多路访问协议5.4链路层编址,5.5以太网5.6集线器和交换机5.7PPP5.8链路虚拟化:ATM和MPLS,数据链路层与局域网,16,多路访问链路和协议,两类“链路”:点对点用于拨号接入的PPP在以太网交换机和主机之间的点对点链路广播(共享线路或媒体)传统的以太网向上游的HFC802.11无线LAN,数据链路层与局域网,17,多路访问协议,单一共享广播信道节点的两个或更多的并行传输：干扰碰撞如果节点同时接收到两个或更多信号多路访问协议决定节点怎样共享信道的分布式算法，如决定何时节点能够传输有关信道共享的通信必须使用信道本身!不用带外信道来协调,数据链路层与局域网,18,理想的多路访问协议,速率Rbps的广播信道1.当一个节点可传输，它能够以速率R发送2.当M节点要传输，每个能以平均速率R/M发送3.全分散:无特殊节点来协调传输无同步时钟、时隙4.简单,数据链路层与局域网,19,MAC协议:分类,三大类:信道划分将信道划分为较小的“段”(时隙，频率，编码)为节点分配一部分专用随即访问不划分信道，允许碰撞从“碰撞”恢复“轮流”节点轮流，但有更多信息要发送的能够轮流的较长时间,数据链路层与局域网,20,信道划分MAC协议:TDMA,TDMA:时分多路访问”循环“访问信道每个站点在每个循环中获得固定长度时隙(长度=分组传输时间)不使用的时隙空闲例子：6个站点的LAN,时隙1、3、4有分组,时隙2、5、6空闲TDM(TimeDivisionMultiplexing):channeldividedintoNtimeslots,oneperuser;inefficientwithlowdutycycleusersandatlightload.FDM(FrequencyDivisionMultiplexing):frequencysubdivided.,数据链路层与局域网,21,信道划分MAC协议:FDMA,FDMA:频分多路访问信道频谱划分为频带每个站点分配固定的频带频带中未使用的传输时间空闲例子：6个站点的LAN,频带1、3、4有分组,频带2、5、6空闲TDM(TimeDivisionMultiplexing):channeldividedintoNtimeslots,oneperuser;inefficientwithlowdutycycleusersandatlightload.FDM(FrequencyDivisionMultiplexing):frequencysubdivided.,frequencybands,time,数据链路层与局域网,22,随即访问协议,当站点有分组要发送以信道全部速率R传输节点间无优先权协调两个或更多传输节点“碰撞”,随即访问MAC协议定义了:如何检测碰撞如何从碰撞中恢复(例如，经延迟的重新传输)随即访问MAC协议的例子:时隙ALOHAALOHACSMA,CSMA/CD,CSMA/CA,数据链路层与局域网,23,时隙ALOHA,假定所有帧有相同长度时间划分为等长时隙，能够传输1个帧节点仅在时隙开始时开始传输帧节点是同步的如果2个或多个节点在时隙中传输，所有节点检测碰撞,操作当节点获得新帧，将在下一个时隙中传输无碰撞，节点能够在下一个时隙中发送新帧如果碰撞，节点在每个后继时隙中以概率p重传帧知道成功,数据链路层与局域网,24,时隙ALOHA,优点单个活跃节点能够连续地以信道的全速传输高速分散：仅节点中的时隙需要同步简单,缺点碰撞，浪费时隙空闲时隙节点可能能够以小于传输分组的时间检测到碰撞时钟同步,数据链路层与局域网,25,时隙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%！,数据链路层与局域网,26,纯(非时隙)ALOHA,非时隙Aloha:更简单，无同步要求当帧首个到达立即传输碰撞的概率增加:在t0发送与在t0-1,t0+1发送的其他帧碰撞,将于i帧起始部分重叠,将于i帧结束部分重叠,数据链路层与局域网,27,纯Aloha效率,P(给定节点成功)=节点传输).P(在p0-1,p0中无其他节点传输)=p.(1-p)N-1.(1-p)N-1=p.(1-p)2(N-1)选择最适合的p并令n-infty.=1/(2e)=0.18,甚至更差!,数据链路层与局域网,28,CSMA(载波侦听多路访问),CSMA:在传输前侦听:如果侦听到信道空闲:传输整个帧如果侦听到信道忙,推迟传输人类类比:不要打断他人说话!,数据链路层与局域网,29,CSMA碰撞,碰撞还是会出现:传播时延意味着两个节点也许不能听到其他节点传输,碰撞:整个分组传输时间被浪费,节点的空间设置,注意:距离与传播时延在决定碰撞概率岁的作用,空间,数据链路层与局域网,30,CSMA/CD(碰撞检测),CSMA/CD:载波侦听,如同在CSMA在短时间内检测到碰撞碰撞的传输流产，减少信道浪费碰撞检测:在有线的LAN中容易:测量信号强度，比较传输的和接收的信号在无线LAN中困难：传输中接收方切断人类类比:礼貌的交谈者,数据链路层与局域网,31,CSMA/CD碰撞检测,a=/T0,a越小，网络性能越好,空间,数据链路层与局域网,32,“轮流”MAC协议,信道划分MAC协议:在高负载时高效、公平地共享信道低负载时低效：信道访问中延时，当1个活跃节点时，甚至仅有分配了1/N带宽!随机访问MAC协议低负载是有效：单个节点能够全面利用信道高负载：碰撞开销“轮流”协议兼有这方面的优点!,数据链路层与局域网,33,“轮流”MAC协议,轮询:主节点“邀请”从节点依次传输关注问题:轮询开销时延单点故障(主节点),令牌传递:控制令牌从一个节点顺序地传递到下一个.令牌报文关注问题:令牌开销时延单点故障(令牌),数据链路层与局域网,34,MAC协议小结,对共享媒体你需要做些什么?信道划分,通过时间、频率或编码时分,频分随机划分(动态的),ALOHA,S-ALOHA,CSMA,CSMA/CD载波侦听:在某些技术(有线)中容易，在另一些(无线)中困难CSMA/CD用在以太网中CSMA/CA用在802.11中轮流从中心站点轮询，令牌传递,数据链路层与局域网,35,LAN技术,数据链路层前面讲过:服务,差错检测/纠正,多路访问下面:LAN技术编制以太网集线器,交换机PPP,数据链路层与局域网,36,第5章链路层,5.1概述与服务5.2差错检测和纠错5.3多路访问协议5.4链路层编址,5.5以太网5.6集线器和交换机5.7PPP5.8链路虚拟化:ATM和MPLS,数据链路层与局域网,37,地址转换问题,两台机器A和B,它们IP地址分别是IA、IB，物理地址分别是PA和PB高层程序仅希望与IP地址交往，而实际通信必须使用物理地址,IP4,IA,PA,HA4,HA3,HA2,HA5,PB,IP5,A,B,IP2,R1,R2,以太网2,以太网1,FDDI网,IP层上的互联网,IP数据报,MAC帧,IB,IP3,MAC帧,MAC帧,问题：A如何从B的IP地址得到它的物理地址PB？,数据链路层与局域网,38,MAC地址和ARP,32-bitIP地址:网络层地址用于使数据报到达目的IP子网MAC(或LAN或物理或以太网)地址:用于使数据报从一个接口到达另一个物理连接的接口(同一个网络内)48bitMAC地址(对多数LAN)烧在了适配器ROM中,数据链路层与局域网,39,LAN编制和ARP,在L