Announcements Homework 2 out due Tuesday Oct 9 11PM MUST be turned in by deadline o Turn in via hardcopy to drop box in 240 Cory Links No late homeworks accepted because we want to send out the solutions the next day so you have time to absorb them for the Midterm on Friday Oct 12 EE 122 Intro to Communication Networks Note for the midterm material covered only in section is in scope Fall 2007 WF 4 5 30 in Cory 277 I will be away Oct 9 11 Vern Paxson So won t have office hours on Weds Oct 10 TAs Lisa Fowler Daniel Killebrew Jorge Ortiz No lecture Weds Oct 10 http inst eecs berkeley edu ee122 Materials with thanks to Jennifer Rexford Ion Stoica and colleagues at Princeton and UC Berkeley I will have extra office hours Friday Oct 12 12 30 2 30PM 1 2 Goals of Today s Lecture Message Segment Packet and Frame host host Link layer services Encoding framing error detection transmission control Error correction and flow control HTTP message HTTP TCP segment TCP Arbitrating access to a shared medium router Channel partitioning Taking turns Random access IP o Carrier sense o Collision detection Adaptors Communicating datagram sending node adapter Ethernet interface Ethernet frame TCP router IP packet IP SONET interface SONET interface SONET frame IP IP packet Ethernet interface IP Ethernet interface Ethernet frame 4 Link Layer Services Encoding link layer protocol frame IP packet Ethernet interface 3 HTTP Representing the 0s and 1s Framing frame Encapsulating packet into frame adding header trailer Using MAC addresses rather than IP addresses adapter receiving node Link layer implemented in adaptor network interface card NIC Ethernet card 802 11 card Errors caused by signal attenuation noise Receiver detects presence may ask for repeat ARQ Sending side Encapsulates datagram in a frame Determines local addressing adds error checking controls transmission Resolving contention Deciding who gets to transmit when multiple senders want to use a shared media Receiving side Recognizes arrival looks for errors possibly acknowledges Extracts datagram and passes to receiving node Error detection 5 Flow control pacing between sender receiver 6 1 Encoding Non Return to Zero NRZ Signals propagate over physical links 1 high signal 0 low signal How do we represent the bits Physical layer issue Actual signals are of course not so sharp How does receiver know where one bit stops and another begins 0 Simplify some electrical engineering details Assume two discrete signals high and low E g could correspond to two different voltages 0 1 0 1 0 1 1 0 NRZ non return to zero Basic approach High for a 1 low for a 0 How hard can it be Clock o Sender receiver agree what s high what s low o And when to read the signal 7 Clock Coordination Receiver reads the signal on the clock s leading edge Sender begins to transmit signal on clock s falling edge 8 Clock Drift How do the sender and receiver agree on the running of the clock 0 Problem without explicit synchronization receiver s clock can drift with respect to sender s 0 0 1 0 1 0 1 1 0 1 0 1 0 1 1 0 0 NRZ Sender s Clock NRZ Clock Receiver s Clock can drift Here we slip a bit reading a 0 on leading edge rather than the correct 1 10 Clock 9 Clock Recovery Non Return to Zero Inverted NRZI To avoid clock drift we use the signal itself to coordinate 1 make transition 0 stay at same level Fixes previous problem for long sequences of 1 s Whenever see a transition 0 1 or 1 0 we know that corresponds to sender clock s trailing edge But not for 0 s So pull our clock in phase towards it 0 0 1 0 1 0 1 1 0 Problem with NRZ long strings of 0s or 1s Quite common No transitions from low to high or high to low Clock recovery fails and receiver s clock begins to drift NRZI non return to zero inverted 11 Clock read on falling edge 12 2 Manchester Encoding 4 bit 5 bit 100Mb s Ethernet 1 high to low transition 0 low to high transition Goal address inefficiency of Manchester encoding while avoiding long periods of no transition Addresses clock recovery problems Solution Use 5 bits to encode every sequence of four bits such that o No 5 bit code has more than one leading 0 or two trailing 0 s But physical signaling must be twice as fast Use NRZI to then encode the 5 bit codes Efficiency is 80 To support 2 transitions cycle Efficiency of 50 0 0 1 0 1 0 1 1 0 Manchester Clock read on each rising edge 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 13 14 Framing Specify how blocks of data are transmitted between two nodes connected on the same physical media 5 Minute Break Service provided by the data link layer Implemented by the network adaptor Challenges Decide when a frame starts ends How hard can that be Questions Before We Proceed 15 16 Framing Sentinels Simple Approach to Framing Counting Delineate frame with special pattern Sender begin frame with byte s giving length e g 01111110 start 01111111 end Receiver extract this length and count 01111110 53 Frame contents 21 Solution escape the special characters E g sender always inserts a 0 after five 1s receiver always removes a 0 appearing after five 1s On occasion the count gets corrupted Frame contents 01111111 Problem what if sentinel occurs within frame 21 bytes of data 53 bytes of data How can this go wrong 58 Frame contents Frame contents 21 Frame 94 contents Similar to escaping special characters in C programs Bogus new frame length 58 bytes of data misdelivered desynchronization 17 18 3 Clock Based Framing SONET Error Detection SONET Synchronous Optical NETwork Errors are unavoidable Electrical interference thermal noise etc SONET endpoints maintain clock synchronization Error detection Frames have fixed size e g 125 sec Transmit extra redundant information Use redundant information to detect errors Extreme case send two copies of the data Trade off accuracy vs overhead 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 Techniques for detecting errors Parity checking Checksum Cyclic Redundancy Check CRC 19 Error Detection Parity Error Detection Techniques con t Add an extra bit to a 7 bit code Internet Checksum Treat data as a sequence of 16 bit words Compute ones complement sum of all the 16 bit words Intermingles
View Full Document
Unlocking...