This preview shows page 1-2-3-18-19-37-38-39 out of 39 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 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 39 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 39 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 39 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 39 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 39 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 39 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 39 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Links Reading: Chapter 2Goals of Today’s LectureMessage, Segment, Packet, and FrameLink Layer Protocol for Each HopAdaptors CommunicatingLink-Layer ServicesEncodingProblem With Simple ApproachFramingFraming (Continued)Error DetectionError Detection TechniquesPoint-to-Point vs. Broadcast MediaMultiple Access ProtocolChannel Partitioning: TDMAChannel Partitioning: FDMA“Taking Turns” MAC protocolsRandom Access ProtocolsKey Ideas of Random AccessSlotted ALOHASlide 21CSMA (Carrier Sense Multiple Access)CSMA CollisionsCSMA/CD (Collision Detection)CSMA/CD Collision DetectionThree Ways to Share the MediaEthernetEthernet Uses CSMA/CDLimitations on Ethernet LengthSlide 30Ethernet Frame StructureEthernet Frame Structure (Continued)Unreliable, Connectionless ServiceHubs: Physical-Layer RepeatersInterconnecting with HubsSwitchSwitch: Traffic IsolationBenefits of EthernetConclusions1LinksReading: Chapter 2COS 461: Computer NetworksSpring 2006 (MW 1:30-2:50 in Friend 109)Jennifer RexfordTeaching Assistant: Mike Wawrzoniak http://www.cs.princeton.edu/courses/archive/spring06/cos461/2Goals of Today’s Lecture•Link-layer services–Encoding, framing, and error detection–Error correction and flow control•Sharing a shared media–Channel partitioning–Taking turns–Random access•Ethernet protocol–Carrier sense, collision detection, and random access–Frame structure–Hubs and switches3Message, Segment, Packet, and FrameHTTPTCPIPEthernetinterfaceHTTPTCPIPEthernetinterfaceIP IPEthernetinterfaceEthernetinterfaceSONETinterfaceSONETinterfacehosthostrouterrouterHTTP messageTCP segmentIP packetIP packetIP packetEthernet frameEthernet frameSONET frame4Link Layer Protocol for Each Hop•IP packet transferred over multiple hops–Each hop has a link layer protocol–May be different on different hops•Analogy: trip from Princeton to Lausanne–Limo: Princeton to JFK–Plane: JFK to Geneva–Train: Geneva to Lausanne•Refining the analogy–Tourist == packet–Transport segment == communication link–Transportation mode == link-layer protocol–Travel agent == routing algorithm5Adaptors Communicating•Link layer implemented in adaptor (network interface card)–Ethernet card, PCMCI card, 802.11 card•Sending side:–Encapsulates datagram in a frame–Adds error checking bits, flow control, etc.•Receiving side–Looks for errors, flow control, etc.–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 detecting presence of errors•Error correction–Receiver correcting errors without retransmission•Flow control–Pacing between adjacent sending and receiving nodes7Encoding•Signals propagate over physical links–Source node encodes the bits into a signal–Receiving node decodes the signal back into bits•Simplify some electrical engineering details–Assume two discrete signals, high and low–E.g., could correspond to two different voltages•Simple approach–High for a 1, low for a 00 0 1 1 0 0 1 1 0 0 0 1 1 1 1 1 0 08Problem With Simple Approach•Long strings of 0s or 1s introduce problems–No transitions from low-to-high, or high-to-low•Receiver keeps average of signal it has received–Uses the average to distinguish between high and low–Long flat strings make receiver sensitive to small change•Transitions also necessary for clock recovery–Receiver uses transitions to drive its own clock–Long flat strings do not produce any transitions–Can lead to clock drift at the receiver•Alternatives (see Section 2.2)–Non-return to zero inverted, and Manchester encoding9Framing•Break sequence of bits into a frame–Typically implemented by the network adaptor•Sentinel-based–Delineate frame with special pattern (e.g., 01111110)–Problem: what if special patterns occurs within frame?–Solution: escaping the special charactersE.g., sender always inserts a 0 after five 1s… and receiver always removes a 0 appearing after five 1s–Similar to escaping special characters in C programs01111110 01111110Frame contents10Framing (Continued)•Counter-based–Include the payload length in the header–… instead of putting a sentinel at the end–Problem: what if the count field gets corrupted?Causes receiver to think the frame ends at a different place–Solution: catch later when doing error detectionAnd wait for the next sentinel for the start of a new frame•Clock-based–Make each frame a fixed size–No ambiguity about start and end of frame–But, may be wasteful11Error 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)12Error Detection Techniques•Parity check–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•Checksum–Treat data as a sequence of 16-bit words–Compute a sum of all the 16-bit words, with no carries–Transmit the sum along with the packet•Cyclic Redundancy Check (CRC)–See Section 2.4.313Point-to-Point vs. Broadcast Media•Point-to-point–PPP for dial-up access–Point-to-point link between Ethernet switch and host•Broadcast (shared wire or medium)–Traditional Ethernet–802.11 wireless LAN14Multiple Access Protocol•Single shared broadcast channel–Avoid having multiple nodes speaking at once–Otherwise, collisions lead to garbled data•Multiple access protocol–Distributed algorithm for sharing the channel–Algorithm determines which node can transmit•Classes of techniques–Channel partitioning: divide channel into pieces–Taking turns: passing a token for the right to transmit–Random access: allow collisions, and then recover15Channel Partitioning: TDMATDMA: time division multiple access •Access to channel in "rounds" –Each station gets fixed length slot in each round•Time-slot length is packet transmission time –Unused slots go idle


View Full Document

Princeton COS 461 - Links

Documents in this Course
Lecture

Lecture

76 pages

Switches

Switches

35 pages

Lecture

Lecture

42 pages

Links

Links

39 pages

Lecture

Lecture

34 pages

Topology

Topology

42 pages

Lecture

Lecture

42 pages

Overview

Overview

42 pages

Sockets

Sockets

45 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?