计算机网络英文课件

Chapter 5 The Link Layer and LANComputer Networking:A Top Down Approach Featuring the Internet3rd edition.Jim Kurose,Keith Ross.1Chapter 5:The Data Link LayerOur goals:lunderstand principles behind data link layer services:lerror detection&correctionlsharing a broadcast channel:multiple accessllink layer addressinglreliable data transfer,flow control:done!linstantiation and implementation of various link layer technologieslEthernet：broadcast channellPPP：point to point channel.2Link Layer Roadmapl5.1 Introduction and servicesl5.2 Error detection and correction l5.3Multiple access protocolsl5.4 Link-Layer Addressingl5.5 Ethernetl5.6 Hubs and switchesl5.7 PPPl5.8 Link Virtualization:ATM and MPLS.3Link Layer:IntroductionSome terminology:lhosts and routers are nodeslcommunication channels that connect adjacent nodes along communication path are linkslwired linkslwireless linkslLANsllayer-2 packet is a frame,encapsulates datagram“link”data-link layer has responsibility of transferring datagrams from one node to adjacent node over a link.4Link layer:contextlDatagram transferred by different link protocols over different links:le.g.,Ethernet on first link,frame relay on intermediate links,802.11 on last linklEach link protocol provides different servicesle.g.,may or may not provide rdt(reliable data transfer)over a linktransportation analogyltrip from Princeton,New Jersey to Lausanne,Switzerlandllimo:Princeton to JFKlplane:JFK to Genevaltrain:Geneva to Lausanneltourist=datagramltransport segment=communication linkltransportation mode=link layer protocolltravel agent=routing algorithm.5Link Layer ServiceslFraming,link access:lencapsulate datagram into frame,adding header,trailerlchannel access if shared mediuml“MAC”addresses used in frame headers to identify source,dest lMAC Medium Access Controlldifferent from IP address!lReliable delivery between adjacent nodeslwe learned how to do this already(chapter 3)!lseldom used on low bit error link(fiber,some twisted pair)lwireless links:high error rateslQ:why both link-level and end-end reliability?.6Link Layer Services(more)lFlow Control:lpacing between adjacent sending and receiving nodeslError Detection:lerrors caused by signal attenuation,noise.lreceiver detects presence of errors:lsignals sender for retransmission or drops frame lError Correction:lreceiver identifies and corrects bit error(s)without resorting to retransmissionlFull-duplex,Half-duplex,Simplexlwith half duplex,nodes at both ends of link can transmit,but not at same time.7Adapters Communicatingllink layer implemented in“adapter”(aka NIC)lEthernet card,PCMCIA card,802.11 cardlsending side:lencapsulates datagram in a frameladds error checking bits,rdt,flow control,etc.lreceiving sidellooks for errors,rdt,flow control,etclextracts datagram,passes to rcving nodeladapter is semi-autonomousllink&physical layerssendingnodeframercvingnodedatagramframeadapteradapterlink layer protocol.8Link Layer Roadmapl5.1 Introduction and servicesl5.2 Error detection and correction l5.3Multiple access protocolsl5.4 Link-Layer Addressingl5.5 Ethernetl5.6 Hubs and switchesl5.7 PPPl5.8 Link Virtualization:ATM.9Error DetectionEDC=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,but rarely larger EDC field yields better detection and correction.10Parity CheckingSingle Bit Parity:Detect single bit errorsTwo Dimensional Bit Parity:Detect and correct single bit errors001Forward Error Correction,FEC.11Internet checksumSender:ltreat segment contents as sequence of 16-bit integerslchecksum:addition(1s complement sum)of segment contentslsender puts checksum value into checksum fieldReceiver:lcompute checksum of received segmentlcheck if computed checksum equals checksum field value:lNO-error detectedlYES-no error detected.But maybe errors nonetheless?More later.Goal:detect“errors”(e.g.,flipped bits)in transmitted segment(note:used at transport layer only).12Checksumming:Cyclic Redundancy Checklview data bits,D,as a binary numberlchoose r+1 bit pattern(generator),G lgoal:choose r CRC bits,R,such thatl exactly divisible by G(modulo 2)lreceiver knows G,divides by G.If non-zero remainder:error detected!lcan detect all burst errors less than r+1 bitslwidely used in practice(ATM,HDCL).13CRC ExampleWant:D.2r XOR R=nGequivalently:D.2r XOR R XOR R=nG XOR RD.2r=nG XOR Requivalently:if we divide D.2r by G,want remainder RR=remainder D.2rGCRC-32(international standard)GCRC-32=100000100110000010001110110110111.14Link Layerl5.1 Introduction and servicesl5.2 Error detection and correction l5.3Multiple access protocolsl5.4 Link-Layer Addressingl5.5 Ethernetl5.6 Hubs and switchesl5.7 PPPl5.8 Link Virtualization:ATM.15Multiple Access Protocols and LinksTwo types of“links”:lpoint-to-pointlPPP for dial-up accesslpoint-to-point link between Ethernet switch and hostlbroadcast(shared wire or medium)ltraditional Ethernetlupstream HFCl802.11 wireless LAN.16Multiple Access protocolslsingle shared broadcast channel ltwo or more simultaneous transmissions by nodes:interference lcollision if node receives two or more signals at the same timemultiple access protocolldistributed algorithm that determines how nodes share channel,i.e.,determine when node can transmitlcommunication about channel sharing must use channel itself!lno out-of-band channel for coordination.17Ideal 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 decentralized:lno special node to coordinate transmissionslno synchronization of clocks,slots4.Simple.18MAC Protocols:a taxonomyThree broad classes:lChannel Partitioningldivide channel into smaller“pieces”(time slots,frequency,code)lallocate piece to node for exclusive uselRandom Accesslchannel not divided,allow collisionsl“recover”from collisionsl“Taking turns”lNodes take turns,but nodes with more to send can take longer turns.19Channel Partitioning MAC protocols:TDMATDMA:time division multiple access lTDM divides time into Time Frames and further divides each time frame into N time slots,each slot time is then assigned to one of the N nodeslaccess to channel in rounds leach station gets fixed length slot(length=pkt trans time)in each round,unused slots go idle lTDM eliminates collisions and is perfectly fair,but has two drawbacksleach node gets a dedicated transmission rate of R/Nla node is limited to an average rate of R/Nla node must always wait for its turn in transmission sequencelexample:6-station LAN,1,3,4 have pkt,slots 2,5,6 idle.20Channel Partitioning MAC protocols:FDMAFDMA:frequency division multiple access lchannel spectrum divided into frequency bandsleach station assigned fixed frequency bandlunused transmission time in frequency bands go idle lexample:6-station LAN,1,3,4 have pkt,frequency bands 2,5,6 idle ladvantages and drawbackslavoids collisionslshare the channel fairlyla node is limited to a bandwidth of R/Nla node need not waits for its turnCDMA:Code division Multiple Accessfrequency bandstime.21Random Access ProtocolslWhen node has packet to sendltransmit at full channel data rate R.lno a priori coordination among nodesltwo or more transmitting nodes “collision”,lrandom access protocol specifies:lhow to detect collisionslhow to recover from collisions(e.g.,via delayed retransmissions)lExamples of random access MAC protocols:lslotted ALOHAlALOHAlCSMA,CSMA/CD,CSMA/CA.22Slotted ALOHAAssumptionslall frames same size:L bitsltime is divided into equal size slots(time to transmit 1 frame):L/Rlnodes start to transmit frames only at beginning of slotslnodes are synchronizedlif 2 or more nodes transmit in slot,all nodes detect collisionOperationlwhen node obtains fresh frame,it transmits in next slotlno collision,node can send new frame in next slotlif collision,node retransmits frame in each subsequent slot with prob.p until success.23Slotted ALOHAProslsingle active node can continuously transmit at full rate of channellhighly decentralized:only slots in nodes need to be in synchronizationlsimpleConslcollisions,wasting slotslidle slotslnodes may be able to detect collision in less than time to transmit packetlclock synchronization.24Slotted Aloha efficiencylSuppose N nodes with many frames to send,each transmits in slot with probability plprob that node 1 has success in a slot =p(1-p)N-1lprob that any node has a success=Np(1-p)N-1lFor max efficiency with N nodes,find p*that maximizes Np(1-p)N-1lFor 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:channel used for useful transmissions 37%of time!.25Slotted Aloha efficiencylsupposelN nodesleach node attempts to transmit a frame in each slot with probability p any frame .26Pure(unslotted)ALOHAlunslotted Aloha:simpler,no synchronizationlwhen frame first arrivesl transmit immediately lcollision probability increases:lframe sent at t0 collides with other frames sent in t0-1,t0+1.27Pure Aloha efficiencyP(success by given node)=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)Even worse!.28CSMA(Carrier Sense Multiple Access)CSMA:listen before transmit:If channel sensed idle:transmit entire framelIf channel sensed busy,defer transmission lHuman analogy:dont interrupt others!.29CSMA collisionscollisions can still occur:propagation delay means two nodes may not heareach others transmissioncollision:entire packet transmission time wastedspatial layout of nodes note:role of distance&propagation delay in determining collision probability.30CSMA/CD(Collision Detection)CSMA/CD:carrier sensing,deferral as in CSMAlcollisions detected within short timelcolliding transmissions aborted,reducing channel wastage lcollision detection:leasy in wired LANs:measure signal strengths,compare transmitted,received signalsldifficult in wireless LANs:receiver shut off while transmittinglhuman analogy:the polite conversationalist.31CSMA/CD collision detection.32“Taking Turns”MAC protocolschannel partitioning MAC protocols:lshare channel efficiently and fairly at high loadlinefficient at low load:delay in channel access,1/N bandwidth allocated even if only 1 active node!Random access MAC protocolslefficient at low load:single node can fully utilize channellhigh load:collision overhead“taking turns”protocolslook for best of both worlds!.33“Taking Turns”MAC protocolsPolling:lmaster node“invites”slave nodes to transmit in turnlconcerns:lpolling overhead llatencylsingle point of failure(master)Token passing:lcontrol token passed from one node to next sequentially.ltoken messagelconcerns:ltoken overhead llatencylsingle point of failure(token)lFDDI lIEEE 802.5(Token Ring).34 Summary of MAC protocolslWhat do you do with a shared media?lChannel Partitioning,by time,frequency or codelRandom partitioning(dynamic),lALOHA,S-ALOHA,CSMA,CSMA/CDlcarrier sensing:easy in some technologies(wire),hard in others(wireless)lCSMA/CD used in EthernetlCSMA/CA used in 802.11 WLAN(Wireless LAN)lTaking Turnslpolling from a central site,token passing.35LAN technologieslCategories of NetworkslLAN-Local Area NetworklWAN-Wide Area NetworklMAN-Metropolitan Area NetworklData Link layer so far:lservices,error detection/correction,multiple access lNext:LAN technologiesladdressinglEthernetlhubs,switcheslPPP.36Link Layerl5.1 Introduction and servicesl5.2 Error detection and correction l5.3Multiple access protocolsl5.4 Link-Layer Addressingl5.5 Ethernetl5.6 Hubs and switchesl5.7 PPPl5.8 Link Virtualization:ATM.37MAC Addresses and ARPl32-bit IP address:lnetwork-layer addresslused to get datagram to destination IP subnet lMAC(or LAN or physical or Ethernet)address:lused to get datagram from one interface to another physically-connected interface(same network)l48 bit MAC address(for most LANs)burned in the NIC ROMlfor example,1A-2F-BB-76-09-AD.38LAN Addresses and ARPEach adapter on LAN has unique LAN addressBroadcast address=FF-FF-FF-FF-FF-FF=adapter1A-2F-BB-76-09-AD58-23-D7-FA-20-B00C-C4-11-6F-E3-9871-65-F7-2B-08-53 LAN(wired orwireless).39LAN Address(more)lMAC address allocation administered by IEEElmanufacturer buys portion of MAC address space(to assure uniqueness)lAnalogy:(a)MAC address:like Social Security Number (b)IP address:like postal addressl MAC flat address portability lcan move LAN card from one LAN to anotherlIP hierarchical address NOT portablel depends on IP subnet to which node is attached.40ARP:Address Resolution ProtocollEach IP node(Host,Router)on LAN has ARP tablelARP Table:IP/MAC address mappings for some LAN nodes l TTL(Time To Live):time after which address mapping will be forgotten(typically 20 min)Question:how to determineMAC address of Bknowing Bs IP address?1A-2F-BB-76-09-AD58-23-D7-FA-20-B00C-C4-11-6F-E3-9871-65-F7-2B-08-53 LAN237.196.7.23237.196.7.78237.196.7.14237.196.7.88.41ARP protocol:Same LAN(network)lA wants to send datagram to B,and Bs MAC address not in As ARP table.lA broadcasts ARP query packet,containing Bs IP address lDest MAC address=FF-FF-FF-FF-FF-FFlall machines on LAN receive ARP query lB receives ARP packet,replies to A with its(Bs)MAC addresslframe sent to As MAC address(unicast)lwhy?lA caches(saves)IP-to-MAC address pair in its ARP table until information becomes old(times out)lsoft state:information that times out(goes away)unless refreshedlARP is“plug-and-play”:lnodes create their ARP tables without intervention from net administrator.42Routing to another LANwalkthrough:send datagram from A to B via R assume A knows B IP addresslTwo ARP tables in router R,one for each IP network(LAN)ARB.43lA creates datagram with source A,destination B lA uses ARP to get Rs MAC address for 111.111.111.110lA creates link-layer frame with Rs MAC address as dest,frame contains A-to-B IP datagramlAs adapter sends frame lRs adapter receives frame lR removes IP datagram from Ethernet frame,sees its destined to BlR uses ARP to get Bs MAC address lR creates frame containing A-to-B IP datagram sends to BRouting to another LAN.44Dynamic Host Configuration ProtocollDHCP is a Client/Server protocollThe client is typically a newly arriving host wanting to obtain network configuration informationleach subnet will have a DHCP server.lOperationlserver discoveryldiscovery mesg.lDest.IP:255.255.255.255,Source IP:0.0.0.0lDest.MAC:FF-FF-FF-FF-FF-FFlserver offerlDHCP offer mesg.including IP address,Subnet Mask,Address lease time,DNS Server,Default Gateway/Router,etc.lDHCP requestlchoose one from multiple offers,may be come from different DHCP serverslDHCP ACKlserver ack.45Link Layerl5.1 Introduction and servicesl5.2 Error detection and correction l5.3Multiple access protocolsl5.4 Link-Layer AddressinglDHCPl5.5 Ethernetl5.6 Hubs and switchesl5.7 PPPl5.8 Link Virtualization:ATM.46Ethernet“dominant”wired LAN technology:lcheap$20 for 100Mbs!lfirst widely used LAN technologylSimpler,cheaper than token LANs and ATMlKept up with speed race:10 Mbps 10 Gbps Metcalfes Ethernetsketch.47Star topologylBus topology popular through mid 90slNow star topology prevailslConnection choices:hub or switch(more later)hub orswitch.48Ethernet Frame StructureSending adapter encapsulates IP datagram(or other network layer protocol packet)in Ethernet framePreamble(8 bytes):l7 bytes with pattern 10101010 followed by one byte with pattern 10101011l used to synchronize receiver,sender clock rates.49Ethernet Frame StructurelAddresses:6 byteslif adapter receives frame with matching destination address,or with broadcast address(eg ARP packet),it passes data in frame to net-layer protocollotherwise,adapter discards framelType:indicates the higher layer protocol(mostly IP but others may be supported such as Novell IPX and AppleTalk)lCRC:checked at receiver,if error is detected,the frame is simply dropped.50Manchester Encoding.51Unreliable,connectionless servicelConnectionless:No handshaking between sending and receiving adapter.lUnreliable:receiving adapter doesnt send acks or nacks to sending adapterlstream of datagrams passed to network layer can have gapslgaps will be filled if app is using TCPlotherwise,app will see the gaps.52Ethernet uses CSMA/CDlNo slotsladapter doesnt transmit if it senses that some other adapter is transmitting,that is,carrier senseltransmitting adapter aborts when it senses that another adapter is transmitting,that is,collision detectionlBefore attempting a retransmission,adapter waits a random time,that is,random access.53Ethernet CSMA/CD algorithm1.Adaptor receives datagram from net layer&creates frame2.If adapter senses channel idle,it starts to transmit frame.If it senses channel busy,waits until channel idle and then transmits3.If adapter transmits entire frame without detecting another transmission,the adapter is done with frame!4.If adapter detects another transmission while transmitting,aborts and sends jam signal5.After aborting,adapter enters exponential backoff:after the nth collision,adapter chooses a K at random from 0,1,2,2m-1.Adapter waits K512 bit times and returns to Step 2.54Ethernets CSMA/CD(more)Jam Signal:make sure all other transmitters are aware of collision;48 bitsBit time:.1 microsec for 10 Mbps Ethernet;for K=1023,wait time is about 50 msec Exponential Backoff:lGoal:adapt retransmission attempts to estimated current loadlheavy load:random wait will be longerlfirst collision:choose K from 0,1;delay is K 512 bit transmission timeslafter second collision:choose K from 0,1,2,3lafter ten collisions,choose K from 0,1,2,3,4,1023See/interact with Javaapplet on AWL Web site:highly recommended!.55Ethernet(CSMA/CD)efficiencylTprop=max prop between 2 nodes in LANlttrans=time to transmit max-size framelEfficiency goes to 1 as tprop goes to 0lGoes to 1 as ttrans goes to infinitylMuch better than ALOHA,but still decentralized,simple,and cheap.56Ethernet Technologies:10BaseT and 100BaseTl10/100 Mbps rate;latter called“fast ethernet”lT stands for Twisted PairlNodes connect to a hub:“star topology”;100 m max distance between nodes and hubtwisted pairhub.57HubsHubs are essentially physical-layer repeaters:lbits coming from one link go out all other linkslat the same ratelno frame bufferinglno CSMA/CD at hub:adapters detect collisionslprovides net management functionalitytwisted pairhub.58Manchester encodinglUsed in 10BaseTlEach bit has a transitionlAllows clocks in sending and receiving nodes to synchronize to each otherlno need for a centralized,global clock among nodes!lHey,this is physical-layer stuff!.59GE(IEEE 802.3z)and 10G Ethernetluses standard Ethernet frame formatlallows for point-to-point links(switch)and shared broadcast channels(hub)lin shared mode,CSMA/CD is used;short distances between nodes required for efficiencyluses hubs,called here“Buffered Distributors”lFull-Duplex at 1 Gbps for point-to-point linksl10 Gbps(IEEE 802.3ae)now!.60Link Layerl5.1 Introduction and servicesl5.2 Error detection and correction l5.3Multiple access protocolsl5.4 Link-Layer Addressingl5.5 Ethernetl5.6 Interconnections:Hubs and switchesl5.7 PPPl5.8 Link Virtualization:ATM.61Interconnecting with hubslBackbone hub interconnects LAN segmentslExtends max distance between nodeslBut individual segment collision domains become one large collision domainlCant interconnect 10BaseT&100BaseThubhubhubbackbone hub.62SwitchlLink layer devicelstores and forwards Ethernet frameslexamines frame header and selectively forwards frame based on MAC dest addresslwhen frame is to be forwarded on segment,uses CSMA/CD to access segmentltransparentlhosts are unaware of presence of switcheslplug-and-play,self-learninglswitches do not need to be configured.63Forwarding/Filtering How do determine onto which LAN segment to forward frame?Looks like a routing problem.hubhubhubswitch123.64Forwarding/FilteringlA switch has a switch t