信道分配策略105047.pptx

《信道分配策略105047.pptx》由会员分享，可在线阅读，更多相关《信道分配策略105047.pptx（101页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、n刘联海刘联海WELCOMETOCOMPUTER NETWORKS1Information&Communication CollegeChapter 4.The Medium Access Control SublayerChapter 4.The Medium Access Control SublayerReviewSpecificFunctionsServicesFramingErrorControlFlowControlCRCElementaryDataLinkProtocolsSlidingWindowProtocolsHDLC2Chapter 4.The Medium Access

2、 Control SublayerChapter 4.The Medium Access Control SublayerSofar:WehavediscussedtheDataLinkLayersfunctionalityandsomeprotocolsrelatedtopoint-to-pointcommunication.Alargeclassofnetworksisbuiltontopofbroadcastchannels:anumberofstationssharethesame“wire.”Ifonestationsends,alltheothersgettohearit.What

3、stheproblem:ifyouresharingachannel,thentwostationsmaydecidetostartframetransmissionatthesametime=framecollisionChapter 4.The Medium Access Control Sublayer3Chapter 4.The Medium Access Control SublayerChapter 4.The Medium Access Control SublayerSolution:Allocatethechanneltooneofthecompetingstations.P

4、roblem:Youllhavetousethatsamechanneltofigureoutthecompetitionandtheallocation.TheprotocolsusedtodeterminewhogoesnextonamultiaccesschannelbelongtoasublayerofthedatalinklayercalledtheMAC(MediumAccessControl)sublayer.Chapter 4.The Medium Access Control Sublayer4Chapter 4.The Medium Access Control Subla

5、yerChapter 4.The Medium Access Control SublayerMain topics:MULTIPLE ACCESS PROTOCOLSALOHA CSMA/CD ETHERNET WIRELESS LANS DATA LINK LAYER SWITCHINGChapter 4.The Medium Access Control Sublayer5Chapter 4.The Medium Access Control SublayerChapter 4.The Medium Access Control Sublayer信道分配策略信道分配策略随机访问随机访问(

6、争用争用)-负载较轻时负载较轻时控制访问控制访问(负载较重时负载较重时)静态分配静态分配(将频带或时间片等将频带或时间片等固定分给各站点固定分给各站点)站点少且固定，数据量大时站点少且固定，数据量大时频分多路复用频分多路复用同步时分多路复用同步时分多路复用波分多路复用波分多路复用码分多路复用码分多路复用动态分配动态分配(异步时分多路复用异步时分多路复用)仅当有数据发时仅当有数据发时,才才占信道发数据占信道发数据 。轮转轮转 (每个站轮流获得发送机会每个站轮流获得发送机会)预约预约 (各站先声明有数据要发送各站先声明有数据要发送,然后按预约顺序发送然后按预约顺序发送)6Chapter 4.The

7、 Medium Access Control SublayerChapter 4.The Medium Access Control SublayerThree strategies for channel allocation:1.Exercise no control at all:simply let a station try to use the channel,and do something when a collision happens.Applied in contention（竞争）竞争）systems.2.Employ a round-robin technique:e

8、ach station in turn is allowed to use the channel.Applied in token-based systems the station that has the token may use the channel.3.Let a station place a reservation（预约）预约）for the channel.Used in slotted systems.The problem is how to make a reservation.4.1 The Channel Allocation Problem7Chapter 4.

9、The Medium Access Control SublayerChapter 4.The Medium Access Control Sublayer4.2.1 ALOHA4.2.2 Carrier Sense Multiple Access Protocols4.2.5 Wavelength Division Multiple Access Protocols4.2.6 Wireless LAN Protocols4.2 Multiple Access Protocols8Chapter 4.The Medium Access Control SublayerChapter 4.The

10、 Medium Access Control Sublayer4.2.1 ALOHA:Pure ALOHAPrinciple:ifyouwanttosendaframe,justdoit.Ifacollisionoccurs,finishyourcurrenttransmissionandretrylater.9Chapter 4.The Medium Access Control SublayerChapter 4.The Medium Access Control Sublayer纯纯ALOHA冲突重发冲突重发10Chapter 4.The Medium Access Control Su

11、blayerChapter 4.The Medium Access Control SublayerFigure4-2.Vulnerableperiodfortheshadedframe.4.2.1 ALOHA11Chapter 4.The Medium Access Control SublayerChapter 4.The Medium Access Control Sublayer1,LetS（吞吐量）吞吐量）betheaveragenumberofnewframessubmittedduringaframetimeTframe(timeneededtotransmitafullfram

12、e).Poissondistributed（泊松分布）泊松分布）.2,LetG（载荷）载荷）bethenumberofoldandnewframesubmissionsduringaframetime(GS).AlsoPoissondistributed.在给定的一帧时间共生成在给定的一帧时间共生成k帧的概率如下：帧的概率如下：Pkframessubmitted=GK*e-G/k!3,LetP0(传输成功的概率传输成功的概率)betheprobabilitythatframedoesnotsufferfromcollision=S=GP0.4,生成生成0帧的概率为帧的概率为e-G，而两个帧时间

13、长的间隔所生成的帧平而两个帧时间长的间隔所生成的帧平均数是均数是2G，所以：所以：ProbabilitythataframewillnotbedamagedisP0=e-2G5,S=Ge-2G,当当G0.5时，吞吐量最大，为时，吞吐量最大，为S0.184，即信道利即信道利用率为用率为18。4.2.1 ALOHA:Pure ALOHA12Chapter 4.The Medium Access Control SublayerChapter 4.The Medium Access Control Sublayer原理：由于采用时槽技术，所以冲突危险周期被减少了一原理：由于采用时槽技术，所以冲突危险

14、周期被减少了一半，所以在同一个时槽中没有其他流量的概率是半，所以在同一个时槽中没有其他流量的概率是e-G，于是于是S=Ge-G，由此可以得出当由此可以得出当G1时，其信道利用率最高，可时，其信道利用率最高，可达到达到36。4.2.1 ALOHA:slotted ALOHA13Chapter 4.The Medium Access Control SublayerChapter 4.The Medium Access Control SublayerPure ALOHA vs.Slotted ALOHAFigure 4-3.Throughput versus offered traffic fo

15、r ALOHA systems.14Chapter 4.The Medium Access Control SublayerChapter 4.The Medium Access Control SublayerCarrier Sense Multiple Access Protocols do better than ALOHA:you monitor the channel before and/or during transmission.Persistent CSMA Nonpersistent CSMA CSMA/CD4.2.2 Carrier Sense Multiple Acce

16、ss Protocols15Chapter 4.The Medium Access Control SublayerChapter 4.The Medium Access Control Sublayer1,1-persistent（持续的持续的CSMA）:Listen whether the channel is free before transmitting.If busy,wait until it becomes free and then immediately start your transmission.If a collision occurs,the station wa

17、its a random amount of time and starts all over again.2,Nonpersistent（非持续的非持续的CSMA）:Less greedy（至少没有至少没有贪婪）贪婪）when the channel is busy,wait a random period of time before trying again.If you wait too long,the channel utilization drops.3,p-Persistent:Used with slotted systems.If you find the channel

18、idle during the current slot,you transmit with probability p,and defer until next slot with probability 1-p.p1is not really good,p0makes you really polite.对对ALOHA的改进之处的改进之处：1，保证了当检测到信道忙时，所有的站，保证了当检测到信道忙时，所有的站都不再传送数据；都不再传送数据；2，每个站检测到由冲突，它就放弃它当前的传，每个站检测到由冲突，它就放弃它当前的传送任务。送任务。PersistentandNonpersistentC

19、SMA16Chapter 4.The Medium Access Control SublayerChapter 4.The Medium Access Control SublayerImprovement:sense the channel,but immediately stop transmission when you detect a collision.Ethernet works like this.1.Listen to see whether the channel is free.Transmission is delayed until the channel is n

20、o longer used.2.During transmission,keep listening in order to detect a collision.If a collision occurs,transmission immediately stops.3.If a collision occured,wait a random period of time,and proceed with the first step again.CSMA with Collision Detection17Chapter 4.The Medium Access Control Sublay

21、erChapter 4.The Medium Access Control SublayerFigure 4-5.CSMA/CD can be in one of three states:contention,transmission,or idle.CSMA with Collision Detection18Chapter 4.The Medium Access Control SublayerChapter 4.The Medium Access Control SublayerBasic idea:Often,there are a number of base stations c

22、onnected through guided media.A base station can communicate with a mobile computer.The mobile computers use radio/infrared signals for communication.Problem:There can be subtle interference.Figure 4-11.A wireless LAN.(a)A transmitting.(b)B transmitting.4.2.6 Wireless LAN Protocols19Chapter 4.The Me

23、dium Access Control SublayerChapter 4.The Medium Access Control SublayerIssue(a):How can C be prevented from trying to transmit something to B?In that case it will ruin any receipt by B(hidden station problem).Issue(b):How can we tell C that it is allowed to transmit to D,because this will not inter

24、fere with the communication from B to A?(exposed station problem).（注解：（注解：B向向A传输数据，则传输数据，则C可检测到正传输可检测到正传输数据，所以它认为现在不可向数据，所以它认为现在不可向D发送数据）发送数据）MACA(Multiple Access with Collision Avoidance)：The basic idea is for the sender to stimulate the receiver into outputting a short frame,so stations nearby can

25、 detect this transmission and avoid transmitting for the duration of the upcoming(large)data frame.4.2.6 Wireless LAN Protocols20Chapter 4.The Medium Access Control SublayerChapter 4.The Medium Access Control SublayerFigure 4-12.The MACA protocol.(a)A sending an RTS to B.(b)B responding with a CTS t

26、o A.1.A first sends a Request To Send(RTS).2.B answers with a Clear To Send(CTS).3.C hears only RTS and can freely transmit,knowing it will not interfere with As transmission.4.D hears only the CTS and keeps still for otherwise it would interfere with Bs reception.4.2.6 Wireless LAN Protocols21Chapt

27、er 4.The Medium Access Control SublayerChapter 4.The Medium Access Control SublayerEthernetisbasedonCSMA/CD(sensethechannel,waituntilidle,andbackoffwhenyoudetectacollision)：4.3.1EthernetCabling4.3.2ManchesterEncoding4.3.3TheEthernetMACSublayerProtocol4.3.4TheBinaryExponentialBackoffAlgorithm4.3.6Swi

28、tchedEthernet4.3.7FastEthernet4.3.8GigabitEthernet4.3.9IEEE802.2:LogicalLinkControl4.3 Ethernet22Chapter 4.The Medium Access Control SublayerChapter 4.The Medium Access Control SublayerFigure 4-13.The most common kinds of Ethernet cabling.4.3.1 Ethernet Cabling23Chapter 4.The Medium Access Control S

29、ublayerChapter 4.The Medium Access Control Sublayer具有三种接口的以太网卡具有三种接口的以太网卡n 10BASE5(粗缆)n 10BASE2(细缆)n 10BASET(3类双绞线)24Chapter 4.The Medium Access Control SublayerChapter 4.The Medium Access Control Sublayer10BASE-525Chapter 4.The Medium Access Control SublayerChapter 4.The Medium Access Control Subla

30、yer10BASE-226Chapter 4.The Medium Access Control SublayerChapter 4.The Medium Access Control Sublayer10BASE-T27Chapter 4.The Medium Access Control SublayerChapter 4.The Medium Access Control SublayerHUBHUB就像是一根缩短的总线就像是一根缩短的总线28Chapter 4.The Medium Access Control SublayerChapter 4.The Medium Access C

31、ontrol Sublayer10BASE-T网卡、网卡、UTP电缆与电缆与HUB29Chapter 4.The Medium Access Control SublayerChapter 4.The Medium Access Control Sublayer10Mbps以太网卡结构以太网卡结构 数据缓冲区 2-32KRAM 站地址 PROM数据链路控 制器(EDLC)编码译码器(MCC)主机接口 控制电路 内部收发器 BOOT ROM DIXBNC主 机 系 统 总 线BNCRJ-4530Chapter 4.The Medium Access Control SublayerChapter

32、 4.The Medium Access Control Sublayer以太网卡（以太网卡（NIC）的结构的结构1、编码译码器编码译码器（MCC）：）：编码译码器对数字信号进行编码编码译码器对数字信号进行编码和解码。和解码。2 2、内部收发器内部收发器：收发器是网卡和传输介质之间的接口，：收发器是网卡和传输介质之间的接口，它它在两者间实现电气隔离，并在收发器电缆和同轴或在两者间实现电气隔离，并在收发器电缆和同轴或 UTP UTP 电电缆之间提供信号电平转换。收发器的主要功能有：从缆之间提供信号电平转换。收发器的主要功能有：从 MCCMCC接接收信号并把信号发送到介质电缆上；从介质电缆上接收信

33、号收信号并把信号发送到介质电缆上；从介质电缆上接收信号并传送到并传送到 MCCMCC；收发器的碰撞电路具有检测碰撞信号的功能。收发器的碰撞电路具有检测碰撞信号的功能。1010BASE-2,-TBASE-2,-T使用网卡上的内部收发器，不需收发器电缆，使用网卡上的内部收发器，不需收发器电缆，1010BASE-5BASE-5使用外部收发器，需要收发器电缆。使用外部收发器，需要收发器电缆。3 3、数据缓冲区数据缓冲区：数据缓冲区用于缓存计算机与网卡之间交数据缓冲区用于缓存计算机与网卡之间交换的数据，缓冲区的存储量一般为换的数据，缓冲区的存储量一般为2 2K K至至32K32K字节之间，存储字节之间，

34、存储量越大网卡性能越好。量越大网卡性能越好。31Chapter 4.The Medium Access Control SublayerChapter 4.The Medium Access Control Sublayer4 4、主机接口控制电路主机接口控制电路：主要完成网卡与主机的接口控制和数：主要完成网卡与主机的接口控制和数据交换。主机接口控制电路主要由主机与网卡相接的接口部据交换。主机接口控制电路主要由主机与网卡相接的接口部件匹配电路和网卡内部控制电路两部分组成。网卡能够提供件匹配电路和网卡内部控制电路两部分组成。网卡能够提供 ISAISA、EISAEISA、VESAVESA、PCIP

35、CI等多种总线类型的地址、控制、数据等多种总线类型的地址、控制、数据线接口。线接口。5 5、数据链路控制器数据链路控制器（EDLCEDLC）：）：EDLCEDLC是实现数据链路层的大部是实现数据链路层的大部分功能的逻辑功能部件。如以太网的分功能的逻辑功能部件。如以太网的EDLCEDLC芯片专门完成数据芯片专门完成数据链路层的链路层的MACMAC子层的功能，包括：子层的功能，包括：介质访问控制功能、实现介质访问控制功能、实现CSMA/CDCSMA/CD协议；协议；数据帧的封装与拆装、数据帧的封装与拆装、发送与接收；发送与接收；地址地址校验与数据的校验与数据的CRCCRC校验；数据的串、校验；数据

36、的串、并行转换功能；并行转换功能；控制控制EDLCEDLC与数据缓冲区快速交换数据的功能等。与数据缓冲区快速交换数据的功能等。6 6、介质连接装置介质连接装置：介质连接装置是网卡与介质相连的接口部：介质连接装置是网卡与介质相连的接口部件，又称介质连接器。介质连接器负责将网卡与传输电缆连件，又称介质连接器。介质连接器负责将网卡与传输电缆连接在一起。每一种连接器都需要符合相应物理层的标准。接在一起。每一种连接器都需要符合相应物理层的标准。以太网卡（以太网卡（NIC）的结构的结构32Chapter 4.The Medium Access Control SublayerChapter 4.The M

37、edium Access Control Sublayer Problem:We cant just send straight binary codes across the wire,because stations cant distinguish a 0 from an idle line.Solution:use an encoding scheme in which a voltage transition occurs during every bit time(Manchester Encoding)1 1为前高后低为前高后低,0为前低后高为前低后高0变变1不变不变4.3.2

38、Manchester Encoding33Chapter 4.The Medium Access Control SublayerChapter 4.The Medium Access Control SublayerPreamble:10101010isusedtosynchronizethereceiversclockwiththatofthesender.Start:Justadelimitertotellthattherealinfoisnowcoming.Address:Generally48-bitfields.Leftmostbitindicatesordinary（0）orgr

39、oupaddresses（1）.Secondbitindicatesglobalorlocaladdress.4.3.3 The Ethernet MAC Sublayer ProtocolFigure 4-17.Frame formats.(a)DIX Ethernet.(b)IEEE 802.3.34Chapter 4.The Medium Access Control SublayerChapter 4.The Medium Access Control SublayerLength:Rangesfrom0-1500.Framesshouldalwaysbeatleast64bytes.

40、Pad:因为以太网要求有效帧必须至少因为以太网要求有效帧必须至少64字节，从目标地字节，从目标地址算起一直到校验和，也包括这两个域本身。如果一帧的址算起一直到校验和，也包括这两个域本身。如果一帧的数据部分少于数据部分少于46字节的话，使用该域填充，以达到最小长字节的话，使用该域填充，以达到最小长度。度。Checksum:Calculated over the data field（CRC）4.3.3 The Ethernet MAC Sublayer ProtocolFigure 4-17.Frame formats.(a)DIX Ethernet.(b)IEEE 802.3.35Chapte

41、r 4.The Medium Access Control SublayerChapter 4.The Medium Access Control SublayerFigure 4-18.Collision detection can take as long as 2t.Ifastationtriestotransmitaveryshortframe,itisconceivablethatacollisionoccurs,butthetransmissioncompletesbeforethenoiseburstgetsbackat2t t.为什么要限制最小帧的长度？为什么要限制最小帧的长度

42、？36Chapter 4.The Medium Access Control SublayerChapter 4.The Medium Access Control SublayerFor a 10-Mbps LAN with a maximum length of 2500 meters and four repeaters(from the 802.3 specification),the round-trip time(including time to propagate through the four repeaters)has been determined to be near

43、ly 50 sec in the worst case,including the time to pass through the repeaters,which is most certainly not zero.37Chapter 4.The Medium Access Control SublayerChapter 4.The Medium Access Control SublayerTherefore,the minimum frame must take at least this long to transmit.At 10 Mbps,a bit takes 100 nsec

44、,so 500 bits is the smallest frame that is guaranteed to work.To add some margin of safety,this number was rounded up to 512 bits or 64 bytes.Frames with fewer than 64 bytes are padded out to 64 bytes with the Pad field.38Chapter 4.The Medium Access Control SublayerChapter 4.The Medium Access Contro

45、l Sublayer In general,after i collisions,a random number between 0 and 2i-1 is chosen,and that number of slots is skipped.However,after ten collisions have been reached,the randomization interval is frozen at a maximum of 1023 slots.After 16 collisions,the controller throws in the towel and reports

46、failure back to the computer.Further recovery is up to higher layers.Slotslength4.3.4 The Binary Exponential Backoff Algorithm39Chapter 4.The Medium Access Control SublayerChapter 4.The Medium Access Control SublayerCSMA/CD流程流程介质忙？介质忙？载波监听载波监听冲突窗口内检冲突窗口内检 测到冲突？测到冲突？发送完？发送完？发送发送JamJamN16N16?YesYesNoN

47、oNoNoYesYes发送成功发送成功YesYes发送失败发送失败NoNo二进制指数退避，二进制指数退避，延迟一随机时间延迟一随机时间NoNoYesYes发送帧发送帧冲突次数冲突次数N+N+40Chapter 4.The Medium Access Control SublayerChapter 4.The Medium Access Control Sublayer4.3.6 Switched EthernetProblem:Asmorestationsareadded,trafficwillgoup,andsowillthepossibilityofcollisions.（thenetwo

48、rkwillsaturate）Solution:Dividethenetworkintoseparatesub-LANsandconnectthemthroughahigh-speedswitch.Figure 4-20.A simple example of switched Ethernet.41Chapter 4.The Medium Access Control SublayerChapter 4.The Medium Access Control SublayerWhenastationwantstotransmitanEthernetframe,itoutputsastandard

49、frametotheswitch.Theplug-incardgettingtheframemaychecktoseeifitisdestinedforoneoftheotherstationsconnectedtothesamecard.Ifso,theframeiscopiedthere.Ifnot,theframeissentoverthehigh-speedbackplanetothedestinationstationscard.ThebackplanetypicallyrunsatmanyGbps,usingaproprietaryprotocol.4.3.6 Switched E

50、thernet42Chapter 4.The Medium Access Control SublayerChapter 4.The Medium Access Control SublayerProblem:Ethernetbyitselfwastooslow,andnewalternativeslikeFDDIwerejusttooexpensive(theywereokayforbackbones,butnotforbasicLANsegments).Solution:UpgradeexistingbaseofLANs(i.e.Ethernets)insuchawaythattheint