1DataLink Layer 1EE 122 Housekeeping Welcome back. This is 122. Schedule has been changed. Check website. Project phase 2 due on Apr 11 Our journey through the layers: Application Transport Network Link Physical (Wireless)DataLink Layer 2The Data Link LayerOur goals: understand principles behind data link layer services: error detection, correction sharing a common medium: multiple access link layer addressing discussion of various link layer technologies, particularly the Ethernet 802.11 Wi-Fi and other wireless technologies will be discussed in greater detail later.2DataLink Layer 3Link Layer Introduction and services Error detection and correction Multiple access protocols Link-Layer Addressing EthernetDataLink Layer 4Link Layer: IntroductionSome terminology: 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 datagram“link”data-link layer has responsibility of transferring datagram from one node to adjacent node over a link3DataLink Layer 5Link 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 rdt over linkDataLink Layer 6Link Layer Services Framing, link access: encapsulate datagram into frame, adding header, trailer channel access if shared medium “MAC” addresses used in frame headers to identify source, dest • different from IP address! Reliable delivery between adjacent nodes we learned how to do this already (chapter 3)! 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?4DataLink Layer 7Link Layer Services (more)Error Detection and Correction: errors caused by signal attenuation, noise. receiver detects presence of errors: • signals sender for retransmission or drops frame 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 timeDataLink Layer 8Adaptors Communicating link layer implemented in “adaptor” (aka NIC) Ethernet card, PCMCI card, 802.11 card sending side: encapsulates datagram in a frame adds error checking bits, rdt, flow control, etc. receiving side looks for errors, rdt, flow control, etc extracts datagram, passes to rcving nodesendingnodeframercvingnodedatagramframeadapteradapterlink layer protocol5DataLink Layer 9Link Layer Introduction and services Error detection and correction Multiple access protocols Link-Layer Addressing EthernetDataLink Layer 10Error 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, but rarely• larger EDC field yields better detection and correction6DataLink Layer 11Parity CheckingSingle Bit Parity:Detect how many errors?Two Dimensional Bit Parity:Detect how many bit errors?Correct how many errors?00DataLink Layer 12General Parity-Check Codes A general parity check code adds k parity checks to n data bits Data rate = n/(n+k) information bits per code bits Minimum Hamming distance d is the minimum number of bit flips to get from one possible transmitted sequence (codeword) to another. Can detect if there are less than d errors. Can correct if there are less than d/2 errors. Performance under burst errors also important7DataLink Layer 13Another example: checksumSender: 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?More later ….Goal: detect “errors” (e.g., flipped bits) in transmitted segment (note: used at transport layeronly)DataLink Layer 14Cyclic Redundancy Check (CRC) view data bits, D, as a binary number choose r+1 bit pattern (generator), G (leftmost and rightmost bits are both 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 how many burst errors? widely used in link layer technologies8DataLink Layer 15CRC ExampleWant:D.2rXOR R = nGequivalently:D.2r= nG XOR R equivalently:if we divide D.2rby G, want remainder RR = remainder[
View Full Document
Unlocking...