EE 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 1 The Data Link Layer Our 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 DataLink Layer 2 1 Link Layer Introduction and services Error detection and correction Multiple access protocols Link Layer Addressing Ethernet DataLink Layer Link Layer Introduction 3 link Some 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 data link layer has responsibility of transferring datagram from one node to adjacent node over a link DataLink Layer 4 2 Link 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 link DataLink Layer 5 Link 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 DataLink Layer 6 3 Link 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 corrects bit error s without resorting to retransmission Half duplex and full duplex with half duplex nodes at both ends of link can transmit but not at same time DataLink Layer 7 Adaptors Communicating datagram frame frame adapter adapter link layer implemented in receiving side adaptor aka NIC looks for errors rdt flow rcving node link layer protocol sending node Ethernet card PCMCI card 802 11 card sending side control etc extracts datagram passes to rcving node encapsulates datagram in a frame adds error checking bits rdt flow control etc DataLink Layer 8 4 Link Layer Introduction and services Error detection and correction Multiple access protocols Link Layer Addressing Ethernet DataLink Layer 9 Error Detection and Correction EDC 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 DataLink Layer 10 5 Parity Checking Single Bit Parity Detect how many errors Two Dimensional Bit Parity Detect how many bit errors Correct how many errors 0 0 DataLink Layer 11 General 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 important DataLink Layer 12 6 Another example checksum Goal detect errors e g flipped bits in transmitted segment note used at transport layer only 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 field Receiver 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 DataLink Layer 13 Cyclic 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 technologies DataLink Layer 14 7 CRC Example Want D 2r XOR R nG equivalently D 2r nG XOR R equivalently if we divide D 2r by G want remainder R R remainder D 2r G DataLink Layer 15 8
View Full Document