Links EE 122 Intro to Communication Networks Fall 2006 MW 4 5 30 in Donner 155 Vern Paxson TAs Dilip Antony Joseph and Sukun Kim http inst eecs berkeley edu ee122 Materials with thanks to Jennifer Rexford Ion Stoica and colleagues at Princeton and UC Berkeley 1 Announcements Feedback received extra credit too prevalent weighted too heavily Risks becoming mandatory rather than optional I concur For remaining assignments Extra credit points will be reduced And some of it moved into main part of assignment instead 2 1 Goals of Today s Lecture Link layer services Encoding framing error detection transmission control Error correction and flow control Arbitrating access to a shared medium Channel partitioning Taking turns Random access Ethernet protocol Carrier sense collision detection and random access Frame structure 3 Message Segment Packet and Frame host host HTTP message HTTP TCP segment TCP router IP Ethernet interface HTTP IP packet Ethernet interface Ethernet frame IP TCP router IP packet SONET interface SONET interface SONET frame IP IP packet Ethernet interface IP Ethernet interface Ethernet frame 4 2 Adaptors Communicating datagram sending node link layer protocol frame frame adapter adapter receiving node Link layer implemented in adaptor network interface card NIC Ethernet card 802 11 card Sending side Encapsulates datagram in a frame Determines addressing adds error checking controls transmission Receiving side Recognizes arrival looks for errors possibly acknowledges Extracts datagram and passes to receiving node 5 Link Layer Services Encoding Representing the 0s and 1s Framing Encapsulating packet into frame adding header trailer Using MAC addresses rather than IP addresses Error detection Errors caused by signal attenuation noise Receiver detects presence may ask for repeat ARQ Resolving contention Deciding who gets to transmit when multiple senders want to use a shared media Flow control pacing between sender receiver 6 3 Encoding Signals propagate over physical links How do we represent the bits Physical layer issue Simplify some electrical engineering details Assume two discrete signals high and low E g could correspond to two different voltages Basic approach High for a 1 low for a 0 How hard can it be Sender receiver agree what s high what s low And when to read the signal 7 Non Return to Zero NRZ 1 high signal 0 low signal Actual signals are of course not so sharp 0 0 1 0 1 0 1 1 0 NRZ non return to zero Clock Receiver reads the signal on the clock s leading edge 8 4 Problem With NRZ Long strings of 0s or 1s quite common No transitions from low to high or high to low Receiver maintains average of signals received Uses the average to distinguish between high and low Long flat strings make average drift low or high Receiver becomes sensitive to small unintended signal differences Transitions also necessary for clock recovery Receiver uses transitions to keep its clock in sync w sender s Long flat strings do not produce any transitions Can lead to clock drift at the receiver 9 Non Return to Zero Inverted NRZI 1 make transition 0 stay at same level Solves previous problems for long sequences of 1 s But not for 0 s 0 0 1 0 1 0 1 1 0 NRZI non return to zero intverted Clock 10 5 Manchester Encoding 1 high to low transition 0 low to high transition Addresses clock recovery and baseline wander problems Disadvantage clock must be twice as fast Efficiency of 50 0 0 1 0 1 0 1 1 0 Manchester Clock 11 4 bit 5 bit 100Mb s Ethernet Goal address inefficiency of Manchester encoding while avoiding long periods of low signals Solution Use 5 bits to encode every sequence of four bits such that No 5 bit code has more than one leading 0 or two trailing 0 s Use NRZI to then encode the 5 bit codes Efficiency is 80 4 bit 5 bit 4 bit 5 bit 0000 0001 0010 0011 0100 0101 0110 0111 11110 01001 10100 10101 01010 01011 01110 01111 1000 1001 1010 1011 1100 1101 1110 1111 10010 10011 10110 10111 11010 11011 11100 11101 12 6 Framing Specify how blocks of data are transmitted between two nodes connected on the same physical media Service provided by the data link layer Implemented by the network adaptor Challenges Decide when a frame starts ends How hard can that be 13 Simple Approach to Framing Counting Sender begin frame with byte s giving length Receiver extract this length and count 53 Frame contents 21 Frame contents 21 bytes of data 53 bytes of data How can this go wrong On occasion the count gets corrupted 58 Frame contents 21 Frame 94 contents Bogus new frame length 58 bytes of data misdelivered desynchronization 14 7 Framing Sentinels Delineate frame with special pattern e g 01111110 01111110 Frame contents 01111110 Problem what if sentinel occurs within frame Solution escape the special characters E g sender always inserts a 0 after five 1s receiver always removes a 0 appearing after five 1s Similar to escaping special characters in C programs 15 Clock Based Framing SONET SONET Synchronous Optical NETwork SONET endpoints maintain clock synchronization Frames have fixed size e g 125 sec No ambiguity about start stop of frame But may be wasteful NRZ encoding To avoid long sequences of 0 s or 1 s payload is XOR ed with special 127 bit pattern w many 0 1 1 0 transitions What problem can that lead to 16 8 Error Detection Errors are unavoidable Electrical interference thermal noise etc Error detection Transmit extra redundant information Use redundant information to detect errors Extreme case send two copies of the data Trade off accuracy vs overhead Techniques for detecting errors Parity checking Checksum Cyclic Redundancy Check CRC 17 Error Detection Parity Add an extra bit to a 7 bit code Odd parity ensure an odd number of 1s E g 0101011 becomes 01010111 Even parity ensure an even number of 1s E g 0101011 becomes 01010110 Overhead 1 7th Power Detects all 1 bit errors Doesn t detect an even number of bit errors in a word 18 9 Error Detection Techniques con t Internet Checksum Treat data as a sequence of 16 bit words Compute and transmit a sum of all the 16 bit words Using ones complement arithmetic Intermingles integrity of a large group of data Overhead 16 bits Power Catches 1 bit errors most other errors But not for example same bit flipped in two different words Cyclic Redundancy Check CRC Family of quite powerful principled algorithms Used by most modern link layers See Peterson Davie Section 2 4 3 19 5 Minute Break Questions Before We Proceed 20 10 Point to Point vs Broadcast Media
View Full Document
Unlocking...