第五章数据链路层

第五章数据链路层第1页，课件共83页，创作于2023年2月链路层:工作环境第2页，课件共83页，创作于2023年2月链路层:工作环境两个物理上连接的设备:主机-路由器,路由器-路由器,主机-主机数据单元:frame（帧）applicationtransportnetworklinkphysicalnetworklinkphysicalMMMMHtHtHnHtHnHlMHtHnHlframe物理链路数据链路协议接口卡第3页，课件共83页，创作于2023年2月链路层的服务成帧,链路访问:

将分组封装入帧,加上帧头,帧尾如果是共享介质，则需实现信道的访问,‘物理地址’放在帧首用来确定信源、信宿

不同于IP地址!在两台物理上连接的设备之间实现可靠传递:

可靠传递是什么概念，回顾一下学过的知识!不太用在误码率低的场合(光纤,某些双绞线)无线链路:误码率相当高Q:为什么在链路层和端到端之间都要做可靠性的校验?第4页，课件共83页，创作于2023年2月链路层的服务(续)流量控制:

保持收发双方的同步错误检测:

信号衰减和噪声会导致出错.接收端检测到错误时:给发送端信号要求重发或丢弃出错帧

错误校正:

接受端检测多个位错并加以校正而无需要求发送端重发第5页，课件共83页，创作于2023年2月链路层:实现通过“adapter（网卡或适配器）”实现e.g.,PCMCIA卡,以太网卡一般适配器都含有:RAM,DSP芯片,主机的总线接口,和链路接口applicationtransportnetworklinkphysicalnetworklinkphysicalMMMMHtHtHnHtHnHlMHtHnHlframephys.linkdatalinkprotocoladaptercard第6页，课件共83页，创作于2023年2月错误检测EDC=错误检测校正（ErrorDetectionandCorrection(冗余数据)）位D=由检验位保护的数据,可包括首部字段

错误检测不可能达到100%可靠!

协议算法可能会忽略了某些错误,但比例极小

较大的EDC字段可以产生较好的检错和纠错效果第7页，课件共83页，创作于2023年2月奇偶校验单比特校验:检测一位错误两维单比特校验:检测和校正单比特错误00第8页，课件共83页，创作于2023年2月因特网校验和发送端:把数据段的内容看成一系列16-bit的整数校验和:对内容进行累加(1’scomplementsum)发送端将校验和放入UDP的checksum字段接收端:对接收到的数据段进行校验和计算检查计算所得的校验和与接收到值的是否相等:NO–出错了YES–没查出错误.但有可能存在错误?….目的:

检测数据段在传输过程中出现的错误(注意:仅用在传输层)第9页，课件共83页，创作于2023年2月校验计算:循环校验码把数据比特串,D,看成二进制数据选择一个r+1bit型(generator),G

目的:选择r个CRC位,R,这样<D,R>可为G整除(modulo2)接收端已知G,用G来除<D,R>.如果余数不为0:查出错误!可以查出所有长度不超过r+1位的突发错误在实践中被广泛应用(ATM,HDCL)第10页，课件共83页，创作于2023年2月CRC举例如果要:D.2rXORR=nG则等于:D.2r=nGXORR也就等于:

如果要让D.2r被G整除,则需要余数RR=remainder[]D.2rG第11页，课件共83页，创作于2023年2月多点访问链路和协议有三种类型的“链路”:点对点(e.g.PPP,SLIP)广播式

(共享线路或介质;e.g,以太网,无线网,etc.)交换式(e.g.,交换式以太网,ATMetc)第12页，课件共83页，创作于2023年2月多点访问协议一条共享的通信信道两个或多个结点可同时发送信号:相互干扰在某一时刻只有一个结点可以成功地发送信号

多点访问协议:分布式的算法来决定如何共享信道,i.e.,决定工作站何时可以发送注意：有关共享通道的通信（协商）也必须在该通道自身上解决!我们希望多点访问协议能够解决什么问题:同步还是异步

了解其他站点的信息健壮性(e.g.如何对待信道错误)性能第13页，课件共83页，创作于2023年2月多点访问协议断言:人类在许多场合都使用多点访问协议classcan"guess"multipleaccessprotocolsmultiaccessprotocol1:multiaccessprotocol2:multiaccessprotocol3:multiaccessprotocol4:第14页，课件共83页，创作于2023年2月MAC协议:分类通道分割将信道分割成较小的“片”(时隙,频率)将小片分给各站点使用随机访问允许冲突从冲突中“恢复”“排队”严格协调访问来避免冲突目标:

高效,公平,简单,分散控制第15页，课件共83页，创作于2023年2月信道分割的MAC协议:TDMATDMA:timedivisionmultipleaccess

（时分多路）“依次”访问信道每次每个站点分得固定长度的时隙(时长=分组的单位传输时间)未用的时隙被闲置和浪费例如:6个站点的LAN,1,3,4有分组发送,而2,5,6的时隙则被闲置

第16页，课件共83页，创作于2023年2月

信道分割的MAC协议:FDMAFDMA:frequencydivisionmultipleaccess（频分复用）

信道按频谱分成若干频段每个站点分得固定的频段在频段不用时该部分信道被闲置和浪费例如:6各站点的LAN,1,3,4发送分组,而2,5,6的频段被闲置frequencybandstime第17页，课件共83页，创作于2023年2月信道分割(CDMA)CDMA：CodeDivisionMultipleAccess（码分多路）

每个用户分得具有唯一性的“code”;ie,代码集合的分割大部分应用在无线通信的场合(cellular,satellite,etc)所有用户共享相同的频道,但每个用户用自己的“码片”序列(ie,code)对数据编码编码信号

=(原始数据)X(码片序列)解码:

编码信号的内积和码片序列允许多个用户共存和发送信号,且相互的干扰极小(假设信号码呈“正交”状)第18页，课件共83页，创作于2023年2月CDMA编码/解码第19页，课件共83页，创作于2023年2月CDMA:两个用户互扰的情况第20页，课件共83页，创作于2023年2月随机访问协议当结点有数据要发送时：使用信道全部的传输速率R.在诸多结点中不存在“预先”协商的机制可能发生两个以上结点同时传输->“冲突”随机访问的MAC协议定义了:如何检测冲突如何从冲突中恢复(e.g.,通过延迟重发)随机访问MAC协议的实例:时隙ALOHAALOHACSMAandCSMA/CD第21页，课件共83页，创作于2023年2月时隙Aloha时间划分成等长的时隙(=分组单元传送的时长)对待新近到达的分组结点要:在下一个时隙开始时传输

如果冲突:以p的概率再后继的时隙重发分组，直到成功为止.(S)成功,(C)冲突,(E)空闲的时隙第22页，课件共83页，创作于2023年2月时隙Aloha的效率Q:

时隙的利用情况如何?A:

假设有N站点有数据发送每个站点以p的概率在时隙中传输数据传输成功的概率S为:

对单个结点来说:S=p(1-p)(N-1)

对N个节点中的任何一个：

S=概率(仅有一个站点传输的)

=Np(1-p)(N-1)…选择最佳的p当n->infty...

=1/e=.37最佳情况:

信道的

使用率为37%!第23页，课件共83页，创作于2023年2月纯(无时隙)ALOHA无时隙Aloha:简单,没有同步信号需要传输分组时:

立即发送而不必等待时隙的开始冲突的概率增加了:在t0时刻发送的分组与在[t0-1,t0+1]时刻发送的分组冲突第24页，课件共83页，创作于2023年2月纯Aloha(续)P(给定节点的成功率)=P(节点传输).P(无其他节点在[p0-1,p0]时刻传输）.P(无其他节点在[p0-1,p0]时刻传输）=p.(1-p).(1-p)

P(在N结点中任意结点的成功率)=Np.(1-p).(1-p)

…选择最佳的p当n->infty...=1/(2e)=.18

S=throughput=“goodput”(successrate)G=offeredload=Np0.51.01.52.00.10.20.30.4PureAlohaSlottedAloha协议限制了信道吞吐

量的有效利用!第25页，课件共83页，创作于2023年2月CSMA:CarrierSenseMultipleAccessCSMA:

（载波检测多路访问）发送前侦听:如果信道闲置:发送整个分组如果信道忙,推迟发送坚持性CSMA:

当信道闲置时，以p的概率立即重试(可能导致不稳定)非坚持性CSMA:

在某个随机间隔以后再试为人处事的规则之一:不要打断别人的发言!第26页，课件共83页，创作于2023年2月CSMA的冲突冲突可能发生在:由于传播延迟两个节点可能听不到对方的发送冲突:整个分组的传输时间被浪费以太网结点间的时空图注意:这里的冲突概率是由距离和传播延迟来决定的第27页，课件共83页，创作于2023年2月CSMA/CD

(CollisionDetection，冲突检测)CSMA/CD:在冲突发生后，短时间内可探测到立即中断传输,减少信道的时间浪费坚持性或非坚持性重传冲突检测:

在有线LAN中简便易行:检测信号强度,比较收、发的信号在无线LAN比较困难:传输时接收器是关闭的人类社会的范例:彬彬有礼的交谈者第28页，课件共83页，创作于2023年2月CSMA/CD冲突检测第29页，课件共83页，创作于2023年2月“轮转式”MAC协议信道分割的MAC协议:在重负荷时共享信道的效率高在轻负荷时效率低:延迟了信道访问,当只有一个结点激活时，分到的带宽只有信道带宽的1/N!随机访问MAC协议在轻负荷时有效率:单个节点可以充分利用信道的带宽在重负荷下:冲突的开销“轮转式”协议在两个方面寻求最佳的解决方案!第30页，课件共83页，创作于2023年2月“轮转式”MAC协议轮询（Polling）:

由主结点“邀请”从结点依次传输RequesttoSend,CleartoSend报文关注:轮询的开销等待时间单点失效(主结点)令牌传递（Tokenpassing）:控制令牌依次通过各个结点令牌报文关注:令牌的开销等待时间单点失效(token)

第31页，课件共83页，创作于2023年2月基于预留的协议分布式轮询（DistributedPolling）:

将时间划分成时隙开始时使用N个较短的预留时隙

预留时隙的时长等于信道端对端的传播延迟

需发报文的站点先发预留信息预留信息被所有其他站点接收到在预留时隙后,报文传输按已知的优先顺序进行

第32页，课件共83页，创作于2023年2月MAC协议小结对于共享介质可以做些什么?信道分割,按时间,频率或编码时分、码分、频分随机分割(动态)ALOHA,S-ALOHA,CSMA,CSMA/CD载波检测:有线“易行”、无线“困难”CSMA/CD被用在以太网中轮转分割从主结点发出轮询,令牌传递（tokenpassing）第33页，课件共83页，创作于2023年2月LAN技术已经提到的数据链路层的内容有:服务,错误检测/校正,多点访问下面:讨论LAN技术编址以太网（Ethernet）集线器、网桥、交换机802.11无线LAN协议PPP（点对点协议）ATM第34页，课件共83页，创作于2023年2月LAN地址和ARP32位的IP地址:

网络层地址用于从目的网络获取分组(参见IP地址定义)LAN(或MAC或物理)地址:用来(在同一网络中)物理上互相连接的接口之间获取分组（或帧）

48位MAC地址(绝大部分LANs)

烧制在适配器的ROM中第35页，课件共83页，创作于2023年2月LAN地址和ARP每个LAN上的网卡都有具唯一性的LAN地址第36页，课件共83页，创作于2023年2月LAN地址(续)MAC分配由IEEE管理制造商购买部分MAC地址空间(以保证唯一性)比方:(a)MAC地址:身份证号(b)IP地址:类似邮政地址MAC平面地址=>可以迁移可以将LAN卡从一个LAN换到另一个IP层次性地址不可迁移

取决于某个站点接入的网络第37页，课件共83页，创作于2023年2月有关路由选择的讨论223.1.1.1223.1.1.2223.1.1.3223.1.1.4223.1.2.9223.1.2.2223.1.2.1223.1.3.2223.1.3.1223.1.3.27ABEA站点要给B站点发送IP分组：查找B站点的网络地址,发现B站点与其在同一网络中给B站点发送的分组是通过链路层的帧来传送的

B’sMACaddrA’sMACaddrA’sIPaddrB’sIPaddrIPpayload分组帧帧的源、宿地址分组的源、宿地址第38页，课件共83页，创作于2023年2月ARP:地址解析协议（AddressResolutionProtocol）每个LAN上的IP结点(主机,路由器)都有

ARP模块,和表ARP表:是某些LAN结点的IP/MAC地址映射<IP地址;MAC地址;TTL><…………..>TTL(TimeToLive):超过TTL的地址映射会被删除(一般为20分钟)Q:

若已知B站点的IP地址，

如何确定其MAC地址?第39页，课件共83页，创作于2023年2月ARP协议A知道B的IP地址,需要了解B的物理地址

A广播

ARP查询帧,包含了B的IP地址

所有LAN的主机都收到ARP查询

B接收到ARP帧,将其物理地址返回给AA对收到的IP/MAC地址对进行缓存直到信息过期(超时)软状态:除非定期刷新，否则超时信息将被删除第40页，课件共83页，创作于2023年2月LAN之间的路由选择穿越:经由R将A的数据传输到B在源主机的配置表中发现了路由器111.111.111.110在源主机的ARP表中,发现MAC地址E6-E9-00-17-BB-4B,etcARB第41页，课件共83页，创作于2023年2月A创建了IP分组，源地址为A,宿地址为BA使用ARP来获取R的与111.111.111.110对应的物理地址A创建了以R的物理地址为宿地址的以太网帧，该帧包含的A-to-B的IP分组A的数据链路层发送以太网的帧

R的数据链路层接收到以太网的帧

R从以太网帧中取出IP分组,知道该分组的信宿为BR使用ARP来取得B的物理层地址

R创建了包含了A-to-BIP分组的帧并发给BARB第42页，课件共83页，创作于2023年2月以太网（Ethernet）“统治”LAN的技术:便宜，

￥50for100Mbs!最早被广泛应用的LAN技术较为简单,比tokenLANs和ATM便宜赶上了速率竞赛的步伐:10,100,1000MbpsMetcalfe’sEtheretsketch第43页，课件共83页，创作于2023年2月以太网帧结构发送适配器将IP分组封装在以太网帧中(或其他网络层协议分组)Preamble（前序）:

7个10101010字节尾随一个10101011字节

用来同步收发双方的时钟速率第44页，课件共83页，创作于2023年2月以太网帧结构(续)地址:6个字节,帧为某个LAN上的所有适配器接收，，但只要地址不匹配就被丢弃类型:说明其上层协议,大部分为IP，但其他协议如NovellIPX和AppleTalk也支持CRC:

在接收端校验,如果出错，则将该帧丢弃第45页，课件共83页，创作于2023年2月802.3/Ethernetv2帧格式PA：前同步码-10101010序列，用于使接收方与发送方同步SFD：帧首定界--10101011DA：目的MAC地址；SA：源MAC地址LEN：数据长度（数据部分的字节数）（0-1500B）Type：类型。高层协议标识LLCPDU+pad--最少46字节,最多1500字节Pad：填充字段，保证帧长不少于64字节(若Data域≥46字节，则无Pad)FCS：帧校验序列（CRC-32）866246-15004字节FCSSATypePADADataPadEthernetIEEE802.3

712/62/6246-15004字节FCSPASALENSFDDALLCPDUPad校验区间64-1518字节第46页，课件共83页，创作于2023年2月以太网帧的最短长度问题以太网帧的最短长度为64个字节，或者帧中的数据不得少于46个字节小于以上长度的帧或数据需要在帧中加入“填充数据(pad)”按以太网的标准最大长度2.5km计算，802.3标准将长度达到最大值的以太网两倍往返时延取为51.2μs保证最短长度的帧在发送完毕之前，必须能够监测到可能最晚来到的冲突信号第47页，课件共83页，创作于2023年2月以太网:应用CSMA/CDA:检测信道,if

闲置then{

发送并检测信道;If

检测到了其他站点传输

then{

中止传输并发送冲突信号;更新冲突#;按指数退避算法延迟发送;gotoA}

else{帧发送结束;将冲突次数置0}}else{等待正在进行的传输结束并gotoA}第48页，课件共83页，创作于2023年2月以太网的CSMA/CD(续)冲突信号（JamSignal）:

保证所有其他的收发器能够意识到发生的冲突;48bits;指数退避（ExponentialBackoff）:

Goal目的:使得重发的企图能够与推测出的当前负载相适应在重负荷下:随机等待的时间将更长些首次冲突:从{0,1}中选择K；延迟的时长为Kx512bit传输时间第二次冲突后:从{0,1,2,3}选择K…在10次或更多的冲突发生后：从{0,1,2,3,4,…,1023}选择K第49页，课件共83页，创作于2023年2月以太网技术规范举例:10Base210:10Mb/s;Base:

基带传输2:

最大电缆长度在200米以下在总线拓扑结构中使用细同轴电缆中继器用来连接多个网段(4中继器，5个网段)中继器为物理层设备：将其在一个接口上收到的位流复制到所有其他接口上发送!第50页，课件共83页，创作于2023年2月以太网技术:10Base5粗同轴电缆，可靠性好，抗干扰能力强收发器:发送/接收,冲突检测,电气隔离AUI:连接件单元接口总线型拓扑用于网络骨干连接最大段长度500米每段最多站点数100两站点间最小距离2.5米

粗缆VampiretapBNC端子收发器AUI电缆NIC网络最大跨度2.5公里

第51页，课件共83页，创作于2023年2月以太网技术:10Base2细同轴电缆，可靠性稍差BNCT型接头连接总线型拓扑用于办公室LAN细缆BNC接头NIC每段最大长度185m每段最多站点数30两站点间最短距离0.5m网络最大跨度925m

网络最多5个段第52页，课件共83页，创作于2023年2月以太网技术:10BaseTNICHUB段最大长度100m双绞线介质（UTP）以Hub（集线器）为中心节点。Hub－多端口转发器。拓扑结构为星形，逻辑上仍然是总线形。转发器/中继器的作用：将信号放大并整形后再转发，消除信号传输的失真和衰减。转发器/中继器/HUB——物理层设备(工作在物理层)。用于小型LAN。第53页，课件共83页，创作于2023年2月10BaseT/100BaseT自适应网络10/100Mb/s传输速率;后者被称为“快速以太网”T:

代表双绞线（TwistedPair）所有结点通过双绞线连接到集线器（Hub）,物理上呈现出“星型拓扑”CSMA/CD算法在集线器（Hub）中实现从结点到集线器的最长距离为100米集线器可以与发生故障的适配器断开而不影响其他100BaseT保持以太网最短帧格式不变，但是一个网段的最大缆长减小到100米需要注意：网卡、网线规格、集线器技术参数的匹配第54页，课件共83页，创作于2023年2月千兆以太网（GbitEthernet）使用标准以太网帧格式,与10Mb/100Mb技术兼容可以应用在点对点链路和广播式信道上在共享模式下,使用CSMA/CD;结点间的最长距离为100米在最短帧的基础上增加了“载波延伸”使用集线器,在这里称为“缓冲式分配器（BufferedDistributors）”在点对点链路中可采用1Gb/s全双工通信方式第55页，课件共83页，创作于2023年2月扩展的局域网：集线器（Hubs）物理层设备:本质上是工作在位流层面上的中继器:将接收到的位流在所有其他接口上复制发送集线器可以按照层次结构“级联”,把骨干（backbone）集线器置顶端第56页，课件共83页，创作于2023年2月集线器(续)每个被连接的LAN称为LAN网段（segment）集线器不隔离冲突域:任意LAN网段中的结点都可能与其他网段中的结点发生冲突集线器的优点:简单,廉价设备多层结构提供了一个性能略微降低较大的互联LAN:即使一个集线器故障，部分LAN结点仍可以继续工作扩展了结点间的距离(每个Hub100m)

第57页，课件共83页，创作于2023年2月集线器的局限单一的冲突域导致了最大吞吐量不可能增加多层结构的吞吐量实际与单个网段相同对单个LAN中同样的冲突域的限制也强加到了所有新近加入到这个互联LAN的结点上不能连接不同类型的以太网(e.g.,10BaseT和100baseT)

第58页，课件共83页，创作于2023年2月扩展的局域网：网桥(Bridge)链路层设备:

使用以太网帧工作,检查帧的首部的信宿地址后，选择性的进行转发由于网桥可以缓存帧，网桥可以隔离碰撞域

当在网段间转发帧时,网桥使用CSMA/CD方式访问网段并进行传输

第59页，课件共83页，创作于2023年2月扩展的局域网：网桥(续)网桥优点:隔离冲突域使得网络的最大总吞吐量提高,对接入的结点数和地理覆盖的范围没有限制由于是存储转发设备，所以可以连接不同的以太网透明:不需要改变主机的LAN网络接口适配器第60页，课件共83页，创作于2023年2月网桥:帧的过滤,转发网桥过滤帧

同LAN网段内传输的帧不转发到其他的LAN网段

转发:如何知道那个LAN网段在哪，如何转发?看起来好像是路由选择问题(只不过距离短一点!)第61页，课件共83页，创作于2023年2月主干网桥（BackboneBridge）第62页，课件共83页，创作于2023年2月不使用主干方式的互联不推荐的两个理由:-在ComputerSciencehub故障可能引出的问题-所有在EE和SE之间传输的数据必须通过CS网段第63页，课件共83页，创作于2023年2月网桥过滤网桥可以通过自学了解某台主机可以从哪个接口到达:维护过滤表当帧到达时,网桥“得知”发送方的位置:信号进入的LAN网段在过滤表中记录发送方的位置过滤表的条目:(结点的LAN地址,网桥的接口,时间戳-TimeStamp)过滤表中过期的条目会被丢弃(TTL可以为60分钟)第64页，课件共83页，创作于2023年2月过滤filteringprocedure:If信宿LAN地址与接收到的帧处于同一网段then

丢弃该帧；else

{

查询过滤表

if

发现了信宿的条目then

按条目所指的接口进行转发;else

泛洪（flood）;/*在除了接收该帧的接口以外的所有接口上进行转发*/}

第65页，课件共83页，创作于2023年2月网桥自学过程:举例假设C给D发送帧，D再用帧对C进行应答C发送帧,网桥没有D的资料,因此在两个LAN进行泛洪

网桥注意C是在1#端口位处上部的LAN将该帧忽略LAND接收到了该帧第66页，课件共83页，创作于2023年2月网桥的自学过程:举例D产生了给C的应答,并发送

网桥注意到了D发出的帧网桥查出D处在2#接口上网桥已知C在1#接口上,所以有选择的

通过1#接口转发第67页，课件共83页，创作于2023年2月忽略同网段通信的帧自学源地址转发异网段的帧广播未知帧网桥工作原理小结第68页，课件共83页，创作于2023年2月网桥支撑树(SpanningTree)为增强可靠性,一般希望有一些冗余,比如在信源、信宿间设立具有可替换的路径如果同时有了多条路经，就有可能产生循环–网桥会产生成倍的帧并永远转发下去解决办法:将网桥组织成为生成树，其具体做法是把将部分网桥的部分接口暂时加以封锁Disabled第69页，课件共83页，创作于2023年2月多端口网桥：以太网交换机使用LAN地址在链路层转发、过滤帧(frame)交换:可同时实现A-to-B和A’-to-B’的数据传输,不会产生冲突接口数量较多一般情况:各个主机,呈星状同交换机连接是以太网（Ethernet）,但不会冲突!第70页，课件共83页，创作于2023年2月以太网交换机直通交换（cut-throughswitching）:

在帧头地址确认后，帧被从输入直接导向输出端口，而不必等到整个帧接收完毕后在转发可以减少等待时间可以将共享/专用的10/100/1000Mb/s接口集于一身第71页，课件共83页，创作于2023年2月以太网交换机(续)DedicatedShared第72页，课件共83页，创作于2023年2月交换机的用法(以100/10Mbps网络交换机为例)：

(1)

端口下接站点：站点独占10Mb/s带宽

(2)

端口下接网段：网段中所有站点共享10Mb/s带宽

(3)上行端口：连接主要共享资源-服务器100Mb/s共享10M独享10M共享10M独享100M网络交换机SwitchHUBHUB第73页，课件共83页，创作于2023年2月虚拟局域网VLAN什么是VLAN？

VLAN是一个广播域，是由一些局域网网段构成的与物理位置无关的逻辑组为什么要使用VLAN？

便于进行网络的管理

增强了网络安全性

抑制广播数据的泛滥

减少了处理用户站点移动所带来的开销一个VLAN就好像是一个孤立的网段，VLAN间不能直接通信，实现VLAN间互联必须借助于路由器。VLAN建立在网络交换机基础上第74页，课件共83页，创作于2023年2月两个分离的广播域HUBHUBHUBHUBSwitch财务室开发部财务室开发部合并广播域既有好处，但也带来了问题。不必要的