《3rd Edition, Chapter 5 - EE&T Lecture Notes第三版- EE &；T讲义.ppt》由会员分享，可在线阅读，更多相关《3rd Edition, Chapter 5 - EE&T Lecture Notes第三版- EE &；T讲义.ppt（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、DataLink Layer2-12021 session 1TELE3118:Network TechnologiesWeek 2:Data Link LayerFraming,Error Control,Multiple AccessSome slides have been taken from:rComputer Networking:A Top Down Approach Featuring the Internet,3rd edition.Jim Kurose,Keith Ross.Addison-Wesley,July 2004.All material copyright 19
2、96-2004.J.F Kurose and K.W.Ross,All Rights Reserved.rComputer Networks,4th edition.Andrew S.Tanenbaum.Prentice-Hall,2003.DataLink Layer2-2Link Layer:IntroductionSome terminology:rhosts and routers are nodesrcommunication channels that connect adjacent nodes along communication path are linksmwired l
3、inksmwireless linksmLANsrlayer-2 packet is a frame,encapsulates datagram“link”data-link layer has responsibility of transferring datagram from one node to adjacent node over a linkDataLink Layer2-3Link Layer FunctionsrFramingrError controlrAddressing and Multiple-access controlrFlow controlrReliable
4、 transferDataLink Layer2-4FramingA character stream.(a)Without errors.(b)With one error.DataLink Layer2-5Framing(2)(a)A frame delimited by flag bytes.(b)Four examples of byte sequences before and after stuffing.DataLink Layer2-6Framing(3)Bit stuffing(a)The original data.(b)The data as they appear on
5、 the line.(c)The data as they are stored in receivers memory after destuffing.DataLink Layer2-7Error Detection and CorrectionEDC=Error Detection and Correction bits(redundancy)D =Data protected by error checking,may include header fields Error detection not 100%reliable!protocol may miss some errors
6、,but rarely larger EDC field yields better detection and correctionDataLink Layer2-8Theory:Hamming DistancesrHamming distance of two codewords:mThe number of bit positions in which they differmExample:10001001 and 10110001 have Hamming distance 3rHamming distance of a code:mMinimum distance between
7、any two valid codewordsmE.g.the code:0000000000,0000011111,1111100000,1111111111 has Hamming distance 5rmessage size n=data bits m+redundant bits rmOf 2n codewords,only 2m are validrHow many redundant bits needed for 1-bit error correction?mShould satisfy:(n+1)2m 2n:why?DataLink Layer2-9Error Detect
8、ion:Parity CheckingSingle Bit Parity:Detect single bit errorsTwo Dimensional Bit Parity:Detect and correct single bit errors00DataLink Layer2-10Checksumming:Cyclic Redundancy Checkrview data bits,D,as a binary numberrchoose r+1 bit pattern(generator),G rgoal:choose r CRC bits,R,such thatm exactly di
9、visible by G(modulo 2)mreceiver knows G,divides by G.If non-zero remainder:error detected!mcan detect all burst errors less than r+1 bitsrwidely used in practice(ATM,HDCL)DataLink Layer2-11CRC ExampleWant:D.2r XOR R=nGequivalently:D.2r=nG XOR R equivalently:if we divide D.2r by G,want remainder RR=r
10、emainder D.2rGDataLink Layer2-12Multiple Access Links and ProtocolsTwo types of“links:point-to-pointPPP for dial-up accesspoint-to-point link between Ethernet switch and hostbroadcast(shared wire or medium)traditional Ethernetupstream HFC802.11 wireless LANDataLink Layer2-13Multiple Access protocols
11、rsingle shared broadcast channel rtwo or more simultaneous transmissions by nodes:interference mcollision if node receives two or more signals at the same timemultiple access protocolrdistributed algorithm that determines how nodes share channel,i.e.,determine when node can transmitrcommunication ab
12、out channel sharing must use channel itself!mno out-of-band channel for coordinationDataLink Layer2-14Ideal Multiple Access ProtocolBroadcast channel of rate R bps1.When one node wants to transmit,it can send at rate R.2.When M nodes want to transmit,each can send at average rate R/M3.Fully decentra
13、lized:mno special node to coordinate transmissionsmno synchronization of clocks,slots4.SimpleDataLink Layer2-15MAC Protocols:a taxonomyThree broad classes:Channel Partitioningdivide channel into“pieces(TDM,FDM,CDM,WDM)allocate piece to node for exclusive useRandom Accesschannel not divided,allow col
14、lisions“recover from collisions“Taking turnsNodes take turns,but nodes with more to send can take longer turnsDataLink Layer2-16Random Access ProtocolsrWhen node has packet to sendrtransmit at full channel data rate R.rno a priori coordination among nodesrtwo or more transmitting nodes “collision,rr
15、andom access MAC protocol specifies:rhow to detect collisionsrhow to recover from collisions(e.g.,via delayed retransmissions)rExamples of random access MAC protocols:rslotted ALOHArALOHArCSMA,CSMA/CD,CSMA/CADataLink Layer2-17Slotted ALOHAAssumptionsrall frames same sizertime is divided into equal s
16、ize slots,time to transmit 1 framernodes start to transmit frames only at beginning of slotsrnodes are synchronizedrif 2 or more nodes transmit in slot,all nodes detect collisionOperationrwhen node obtains fresh frame,it transmits in next slotrno collision,node can send new frame in next slotrif col
17、lision,node retransmits frame in each subsequent slot with prob.p until successDataLink Layer2-18Slotted ALOHAProsrsingle active node can continuously transmit at full rate of channelrhighly decentralized:only slots in nodes need to be in syncrsimpleConsrcollisions,wasting slotsridle slotsrnodes may
18、 be able to detect collision in less than time to transmit packetrclock synchronizationDataLink Layer2-19Slotted Aloha efficiencyrSuppose N nodes with many frames to send,each transmits in slot with probability prprob that node 1 has success in a slot =p(1-p)N-1rprob that any node has a success=Np(1
19、-p)N-1 rFor max efficiency with N nodes,find p*that maximizes Np(1-p)N-1rFor many nodes,take limit of Np*(1-p*)N-1 as N goes to infinity,gives 1/e=.37Efficiency is the long-run fraction of successful slots when there are many nodes,each with many frames to sendAt best:channelused for useful transmis
20、sions 37%of time!DataLink Layer2-20Pure(unslotted)ALOHArunslotted Aloha:simpler,no synchronizationrwhen frame first arrivesm transmit immediately rcollision probability increases:mframe sent at t0 collides with other frames sent in t0-1,t0+1DataLink Layer2-21Pure Aloha efficiencyP(success by given n
21、ode)=P(node transmits).P(no other node transmits in t0-1,t0.P(no other node transmits in t0,t0+1 =p.(1-p)N-1.(1-p)N-1 =p.(1-p)2(N-1)choosing optimum p and then letting n-infty.=1/(2e)=.18 Even worse!DataLink Layer2-22CSMA(Carrier Sense Multiple Access)CSMA:listen before transmit:If channel sensed id
22、le:transmit entire framerIf channel sensed busy,defer transmission rHuman analogy:dont interrupt others!DataLink Layer2-23CSMA collisionscollisions can still occur:propagation delay means two nodes may not heareach others transmissioncollision:entire packet transmission time wastedspatial layout of
23、nodes note:role of distance&propagation delay in determining collision probabilityDataLink Layer2-24CSMA/CD(Collision Detection)CSMA/CD:carrier sensing,deferral as in CSMAmcollisions detected within short timemcolliding transmissions aborted,reducing channel wastage rcollision detection:measy in wir
24、ed LANs:measure signal strengths,compare transmitted,received signalsmdifficult in wireless LANs:receiver shut off while transmittingrhuman analogy:the polite conversationalist DataLink Layer2-25CSMA/CD collision detectionDataLink Layer2-26“Taking Turns MAC protocolschannel partitioning MAC protocol
25、s:share channel efficiently and fairly at high loadinefficient at low load:delay in channel access,1/N bandwidth allocated even if only 1 active node!Random access MAC protocolsefficient at low load:single node can fully utilize channelhigh load:collision overhead“taking turns protocolslook for best
26、 of both worlds!DataLink Layer2-27“Taking Turns MAC protocolsPolling:master node“invites slave nodes to transmit in turnconcerns:polling overhead latencysingle point of failure(master)Token passing:rcontrol token passed from one node to next sequentially.rtoken messagerconcerns:mtoken overhead mlate
27、ncymsingle point of failure(token)DataLink Layer2-28 Summary of MAC protocolsrWhat do you do with a shared media?mChannel Partitioning,by time,frequency or codeTime Division,Frequency DivisionmRandom partitioning(dynamic),ALOHA,S-ALOHA,CSMA,CSMA/CDcarrier sensing:easy in some technologies(wire),hard in others(wireless)CSMA/CD used in EthernetCSMA/CA used in 802.11mTaking Turnspolling from a central site,token passing