DOC PREVIEW
Berkeley ELENG 122 - Links

This preview shows page 1-2-20-21 out of 21 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

11LinksEE 122: Intro to Communication NetworksFall 2006 (MW 4-5:30 in Donner 155)Vern PaxsonTAs: Dilip Antony Joseph and Sukun Kimhttp://inst.eecs.berkeley.edu/~ee122/Materials with thanks to Jennifer Rexford, Ion Stoica,and colleagues at Princeton and UC Berkeley2Announcements• 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 assignmentinstead23Goals 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 structure4Message, Segment, Packet, and FrameHTTPTCPIPEthernetinterfaceHTTPTCPIPEthernetinterfaceIP IPEthernetinterfaceEthernetinterfaceSONETinterfaceSONETinterfacehosthostrouterrouterHTTP messageTCP segmentIP packetIP packetIP packetEthernet frameEthernet frameSONET frame35Adaptors Communicating• 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 nodesendingnodeframereceivingnodedatagramframeadapteradapterlink layer protocol6Link-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 senderswant to use a shared media• Flow control (pacing between sender & receiver)47Encoding• 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 signal8Non-Return to Zero (NRZ)• 1  high signal; 0  low signal• (Actual signals are of course not so sharp)00 1 0 1 0 1 1 0NRZ(non-return to zero)ClockReceiver reads the signal onthe clock’s leading edge59Problem 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) signaldifferences• 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 receiver10Non-Return to Zero Inverted (NRZI)• 1  make transition; 0  stay at same level• Solves previous problems for long sequencesof 1’s– But not for 0’s00 1 0 1 0 1 1 0ClockNRZI(non-return to zero intverted)611Manchester 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%00 1 0 1 0 1 1 0ClockManchester124-bit/5-bit (100Mb/s Ethernet)• Goal: address inefficiency of Manchester encoding, whileavoiding 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%0000 111100001 010010010 101000011 101010100 010100101 010110110 011100111 011111000 100101001 100111010 101101011 101111100 110101101 110111110 111001111 111014-bit 5-bit 4-bit 5-bit713Framing• Specify how blocks of data are transmittedbetween two nodes connected on the samephysical 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?14Simple Approach to Framing: Counting• Sender: begin frame with byte(s) giving length• Receiver: extract this length and count• How can this go wrong?• On occasion, the count gets corrupted53 Frame contents53 bytes of data21Frame contents21 bytes of data58Frame contents 21 Frame contents58 bytes of data misdelivered94Bogus new frame length;desynchronization815Framing: Sentinels• Delineate frame with special pattern– e.g., 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 Cprograms01111110 01111110Frame contents16Clock-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-edwith special 127-bit pattern w/ many 0-1/1-0 transitions– What problem can that lead to?917Error 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)18Error 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 word1019Error Detection Techniques, con’t• Internet Checksum– Treat data as a sequence of 16-bit words– Compute and transmit


View Full Document

Berkeley ELENG 122 - Links

Documents in this Course
Lecture 6

Lecture 6

22 pages

Wireless

Wireless

16 pages

Ethernet

Ethernet

10 pages

routing

routing

11 pages

Links

Links

7 pages

Switches

Switches

30 pages

Multicast

Multicast

36 pages

Switches

Switches

18 pages

Security

Security

16 pages

Switches

Switches

18 pages

Lecture 1

Lecture 1

56 pages

OPNET

OPNET

5 pages

Lecture 4

Lecture 4

16 pages

Ethernet

Ethernet

65 pages

Models

Models

30 pages

TCP

TCP

16 pages

Wireless

Wireless

48 pages

Load more
Download Links
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Links and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Links 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?