This preview shows page 1-2-3-4-5-6-7-8-53-54-55-56-57-58-59-107-108-109-110-111-112-113-114 out of 114 pages.
Data Link Layer 5-1Chapter 5Link Layer and LANsA note on the use of these ppt slides:We’re making these slides freely available to all (faculty, students, readers). They’re in PowerPoint form so you can add, modify, and delete slides (including this one) and slide content to suit your needs. They obviously represent a lot of work on our part. In return for use, we only ask the following: If you use these slides (e.g., in a class) in substantially unaltered form, that you mention their source (after all, we’d like people to use our book!) If you post any slides in substantially unaltered form on a www site, that you note that they are adapted from (or perhaps identical to) our slides, and note our copyright of this material.Thanks and enjoy! JFK/KWRAll material copyright 1996-2010J.F Kurose and K.W. Ross, All Rights ReservedComputer Networking: A Top Down Approach 5thedition. Jim Kurose, Keith RossAddison-Wesley, April 2009.Data Link Layer 5-2Link Layer5.1 Introduction and services5.2 Error detection and correction 5.3Multiple access protocols5.4 Link-layer Addressing5.5 Ethernet5.6 Link-layer switches5.7 PPP5.8 Link virtualization: MPLS5.9 A day in the life of a web requestData Link Layer 5-3Link Layer: IntroductionTerminology: hosts and routers are nodes communication channels that connect adjacent nodes along communication path are links wired links wireless links LANs layer-2 packet is a frame,encapsulates datagramdata-link layer has responsibility of transferring datagram from one node to physically adjacentnode over a linkData Link Layer 5-4Link layer: context datagram transferred by different link protocols over different links: e.g., Ethernet on first link, frame relay on intermediate links, 802.11 on last link each link protocol provides different services e.g., may or may not provide reliable delivery over linkData Link Layer 5-5Link Layer Servicesframing: encapsulate datagram into frame, adding header, trailer “MAC” addresses used in frame headers to identify source, destreliable delivery between adjacent nodes seldom used on low bit-error link (fiber, some twisted pair) wireless links: high error rates• Q: why both link-level and end-end reliability?Link access: Medium Access Control (MAC) protocol specifies the rules by which a frame is transmitted onto a link• Different for point-to-point, wireless, and ethernet linksData Link Layer 5-6Link Layer Services (more)flow control: pacing between adjacent sending and receiving nodeserror detection: errors caused by signal attenuation, noise. receiver detects presence of errors: • signals sender for retransmission or drops frame error correction: receiver identifies and correctsbit error(s) without resorting to retransmissionhalf-duplex and full-duplex with half duplex, nodes at both ends of link can transmit, but not at same timeData Link Layer 5-7Where is the link layer implemented? in each and every host link layer implemented in “adaptor” (aka network interface cardNIC) Ethernet card, PCMCI card, 802.11 card implements link, physical layer attaches into host’s system buses combination of hardware, software, firmwarecontrollerphysicaltransmissioncpumemoryhost bus (e.g., PCI)network adaptercardhost schematicapplicationtransportnetworklinklinkphysicalData Link Layer 5-8Adaptors Communicating sending side: encapsulates datagram in frame adds error checking bits, rdt, flow control, etc. receiving side looks for errors, rdt, flow control, etc extracts datagram, passes to upper layer at receiving sidecontrollercontrollersending hostreceiving hostdatagramdatagramdatagramframeData Link Layer 5-9Link Layer5.1 Introduction and services5.2 Error detection and correction5.3Multiple access protocols5.4 Link-layer Addressing5.5 Ethernet5.6 Link-layer switches5.7 PPP5.8 Link virtualization: MPLS5.9 A day in the life of a web requestData Link Layer 5-10Error 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 correctionotherwiseData Link Layer 5-11Parity CheckingSingle Bit Parity:Detect single bit errorsTwo Dimensional Bit Parity:Detect and correctsingle bit errors00Forward Error Correction(FEC):Ability to both detect and correct errors Problem:Rather than occuringindependently, errors often occur in “burts” – multiple errors may go undetectedData Link Layer 5-12Internet checksum (review)Sender: treat segment contents as sequence of 16-bit integers checksum: addition (1’s complement sum) of segment contents sender puts checksum value into UDP checksum fieldReceiver: compute checksum of received segment check if computed checksum equals checksum field value: NO - error detected YES - no error detected. But maybe errors nonetheless?Goal: detect “errors” (e.g., flipped bits) in transmitted packet (note: used at transport layeronly)P3 Suppose the information portion of a packet contains 10 bytes consisting of the 8-bit unsigned binary ASCII representation of string “Link Layer”. Compute the Internet checksum for this dataData Link Layer 5-13Data Link Layer 5-14Checksumming: Cyclic Redundancy Check view data bits, D, as a binary number choose r+1 bit pattern (generator), G The left-most (most significant bit of G) is assumed to be 1 Goal: choose r CRC bits, R, such that <D,R> exactly divisible by G (modulo 2) receiver knows G, divides <D,R> by G. If non-zero remainder: error detected! can detect all burst errors less than r+1 bits Widely used in practice (Ethernet, 802.11 WiFi, ATM)CRC Calculations Done in modulo-2 arithmetic without carries in addition or borrows in subtraction Addition and subtraction are identical and equivalent to the bitwise exclusive-or (XOR) of the operands:• Example: – 1011 XOR 0101– 1011 – 0101– 1011 + 0101Data Link Layer 5-15Data Link Layer 5-16CRC ExampleWant:D.2rXOR R = nGequivalently:D.2r= nG XOR R equivalently:if we divide D.2rby G, want remainder RR = remainder[ ]D.2rGP5 Consider the 5-bit generator G=10011 and suppose that D has the value 1010101010. What is the value of R?Data Link Layer 5-17Question Why is check summing done for errors at the transport
View Full Document
Unlocking...