115-441 Computer NetworkingLecture 18 – Datalink and LANs10/31/2002Link layer 2Goals• Understand and services provided by the datalink layer and the the principles used to implement them.• Understand the design principles and tradeoffs of various implementations of link layer technologies.ApplicationApplicationTransportTransportNetworkNetworkDatalinkDatalinkPhysicalPhysical210/31/2002Link layer 3Outline••Physical Layer Recap.Physical Layer Recap.• Link Layer Overview.• Multiple Access Protocols.• Ethernet.• Bridges and Switches.10/31/2002Link layer 4Physical layer recap• Modulation.Put bits on the wire, i.e. convert bits into either a digital or analog signal.• Bit encoding.• Framing (Link layer).• Errors.• Detection.• Correction.310/31/2002Link layer 7e.g., switched Ethernet, ATM.Shared wire or medium; e.g., Ethernet, air (radio waves).Single wire; e.g., phone line, PPP, SLIP.SwitchedBroadcastPoint to pointLink Taxonomy10/31/2002Link layer 8Similar to point to point.Shared, resource contention.Dedicated. Half duplex or full duplexSwitchedBroadcastPoint to pointLink Speed10 Mbps10 Mbps10 Mbps10 Mbps10 Mbps56 Kbps410/31/2002Link layer 9• Channel partitioning.• Divide channel into smaller “pieces” (frequency, time slots).• Allocate piece to node for exclusive use.• “Taking turns”.• Tightly coordinate shared access to avoid collisions.• Random access.• Allow collisions.• “Recover” from collisions.Goal: efficient, fair, simple, decentralized.Sharing the media: MAC Protocols10/31/2002Link layer 10Time Division Multiple AccessTDMAWavelength Division Multiple AccessWDMAFrequency Division Multiple AccessFDMAChannel Partitioning MACProtocolsOpticalSplitterFrequencyFrequencyTimeBands510/31/2002Link layer 11Outline• Physical Layer Recap.• Link Layer.• Overview.• Services.• Multiple Access Protocols.• Ethernet.• Bridges and Switches.10/31/2002Link layer 12Link Layer: Overview• Two or more physically connected devices.• Implemented in the “adapter”.• E.g., Ethernet card, PCMCIA card.• Typically includes: RAM, DSP chips, host bus interface, and linkinterface + device driver software.HlHnHtMMHtMHnHtMMessageSegmentFramePacketHlHnHtMFramelinkapplicationtransportnetworkphysicallinknetworkphysicaldata linkprotocoladapter cardphysical link610/31/2002Link layer 13Link Layer Services• Framing and addressing. ( )• Link access. (this lecture)• Reliable delivery. ( )• Flow control. ( )• Error detection. ( )• Error correction. ( )10/31/2002Link layer 16Outline • Physical Layer Recap.• Link Layer.• Multiple Access Protocols.••“Taking Turns” (Token ring).“Taking Turns” (Token ring).• Random Access Protocol -- Ethernet CSMA/CD.• Ethernet.• Bridges and Switches.710/31/2002Link layer 17Multiple Access Protocols• Single shared communication channel.• Two or more simultaneous transmissions interference.• Only one node can send successfully at a time.• Multiple Access Protocol:• Distributed algorithm that determines how stations share channel, i.e., determine when station can transmit.• Communication about channel sharing must use channel itself!10/31/2002Link layer 19“Taking Turns”: Token Rings• Packets broadcast around ring.• Token “right to send” rotates around ring.• Every host holds token for limited time.• Fair, real-time bandwidth allocation.• Higher latency when only one sender.• High utilization: > 98%.• Higher bandwidth: Point to point links electrically simpler than bus.• Concerns:• Token overhead.• Latency.• Single point of failure (token).810/31/2002Link layer 20Outline • Physical Layer Recap.• Link Layer.• Multiple Access Protocols.• “Taking Turns” MAC and Other LANs.••Random Access Protocol Random Access Protocol -- Ethernet CSMA/CD.• Ethernet.• Bridges and Switches.10/31/2002Link layer 21Random Access Protocols• When node has packet to send:• Transmit at full channel data rate R.• No a priori coordination among nodes.• Two or more transmitting nodes “collision”.• Random access MAC protocol specifies:• How to detect collisions.• How to recover from collisions (e.g., via delayed retransmissions).• Examples of random access MAC protocols:• Slotted ALOHA.• ALOHA.• CSMA and CSMA/CD.910/31/2002Link layer 25Ethernet• First practical local area network, built at Xerox PARC in 70’s.• “Dominant” LAN technology: • Cheap $20 for 100Mbs!• Kept up with speed race: 10, 100, 1000 Mbps .Metcalfe’s Ethernetsketch.10/31/2002Link layer 26Ethernet MAC – Carrier SenseBasic idea:• Listen to wire before transmission.• Avoid collision with active transmission.1010/31/2002Link layer 28Collisions can occur:Propagation delay means two nodes may not yet hear each other’s transmission.Collision:Entire packet transmission time wasted.Note:Role of distance and propagation delay in determining collision prob.CSMA CollisionsSpatial layout of nodes along Ethernet.10/31/2002Link layer 29Ethernet MAC – Collision DetectionBasic idea:• Listen while transmitting.• If you notice interference thenassume collision.1110/31/2002Link layer 31Ethernet MAC – CSMA/CDPacket?Sense CarrierDiscard PacketSendDetect CollisionJam channel b=CalcBackoff(); wait(b);attempts++;NoYesattempts < 16attempts == 16• Carrier Sense Multiple Access/Collision Detection.10/31/2002Link layer 34Ethernet’s CSMA/CD (more)Jam Signal: Make sure all other transmitters are aware of collision; 48 bits.Exponential Backoff:• If deterministic delay after collision, collision will occur again in lockstep.• If random delay with fixed mean:• Few senders needless waiting.• Too many senders too many collisions.• Goal: Adapt retransmission attempts to estimated current load.• Under heavy load the random wait is longer.1210/31/2002Link layer 35Ethernet Backoff Calculation• Exponentially increasing random delay:• Infer senders from # of collisions.• More senders increase wait time.• First collision: choose K from {0,1}; delay is K x 512 bit transmission times.• After second collision: choose K from {0,1,2,3}.• After n <= 10 collisions: choose K from {0, …, 2n}.• After ten or more collisions, choose K from {0,1,2,3,4,…,1023}.10/31/2002Link layer 41Outline • Physical Layer Recap.• Link Layer.• Multiple Access Protocols.• Ethernet.••Minimum Packet
View Full Document
Unlocking...