115-441 Computer NetworkingLecture 5 – EthernetBrainstorming• One of class goals: learning how to design systemssystems• Take a look at problem and come up with your own solutions first Æ look at actual designs later• Learn to appreciate solution tradeoffsLecture 7: 9-13-07 2pp• Build confidence in your skillsProblem 1 – Sharing a WireBhif h?Learned how to connect hosts• … But what if we want more hosts?SwitchesWires for everybody!Lecture 7: 9-13-07 3• Expensive! How can we share a wire?SwitchesWires for everybody!Problem 2 – Listen and Talkyak yak…• Natural scheme – listen before you talk…• Works well in practiceLecture 7: 9-13-07 4p2Problem 2 – Listen and Talkyada yada…• Natural scheme – listen before you talk…• Works well in practiceLecture 7: 9-13-07 5pProblem 2 – Listen and Talkyada yada…yak yak…• Natural scheme – listen before you talk…• Works well in practiceLecture 7: 9-13-07 6p• But sometimes breaks down• Why? How do we fix/prevent this?Prob. 3 – Who is this packet for?• Need to put an address on the packet• What should it look like?• How do you determine your own address?•How do you know what address you want toLecture 7: 9-13-07 7How do you know what address you want to send it to?Outline • Aloha• Ethernet MAC• CollisionsLecture 7: 9-13-07 8• Ethernet Frames• “Taking Turns” MAC and Other LANs3MAC Protocols: A TaxonomyThree broad classes:• Channel partitioning• Divide channel into smaller “pieces” (time slots, frequency)• Allocate piece to node for exclusive use• Random access• Allow collisions•“Recover”from collisionsLecture 7: 9-13-07 9•Recover from collisions• “Taking turns”• Tightly coordinate shared access to avoid collisionsGoal: efficient, fair, simple, decentralizedRandom Access Protocols• When node has packet to send• Transmit at full channel data rate RTransmit 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 tii)Lecture 7: 9-13-07 10retransmissions)• Examples of random access MAC protocols:• Slotted ALOHA• ALOHA• CSMA and CSMA/CDAloha – Basic Technique• First random MAC developed•For radio-based communication in Hawaii (1970)•For radio-based communication in Hawaii (1970)• Basic idea:• When you’re ready, transmit• Receiver’s send ACK for data• Detect collisions by timing out for ACK•Recover from collision by trying after random delayLecture 7: 9-13-07 11Recover from collision by trying after random delay• Too short Æ large number of collisions• Too long Æ underutilizationSlotted Aloha• Time is divided into equal size slots (= pkt trans. time)• Node (w/ packet) transmits at beginning of next slot (p ) g g• If collision: retransmit pkt in future slots with probability p, until successfulLecture 7: 9-13-07 12Success (S), Collision (C), Empty (E) slots4Pure (Unslotted) ALOHA• Unslotted Aloha: simpler, no synchronization• Pkt needs transmission:• Send without awaiting for beginning of slot• Collision probability increases:• Pkt sent at t0collide with other pkts sent in [t0-1, t0+1]Lecture 7: 9-13-07 13Outline • Aloha• Ethernet MAC• CollisionsLecture 7: 9-13-07 14• Ethernet Frames• “Taking Turns” MAC and Other LANsEthernet• First practical local area network, built at Xerox PARC in 70’s• “Dominant” LAN technology: • Cheap• Kept up with speed race: 10, 100, 1000 Mbps Lecture 7: 9-13-07 15Metcalfe’s EthernetsketchEthernet MAC – Carrier Sense• Basic idea:• Listen to wire before HiddEdste to e be o etransmission• Avoid collision with active transmission• Why didn’t ALOHA have this?•In wireless, relevantNYCMUSt.LouisChicagoCMUHiddenExposedLecture 7: 9-13-07 16In wireless, relevant contention at the receiver, not sender• Hidden terminal• Exposed terminalChicagoNY5Ethernet MAC – Collision Detection• Note: ALOHA has collision detection also, should really be called “Fast Collision Detection”y• Basic idea:• Listen while transmitting• If you notice interference Æ assume collision• Why didn’t ALOHA have this?• Very difficult for radios to listen and transmitLecture 7: 9-13-07 17• Signal strength is reduced by distance for radio• Much easier to hear “local, powerful” radio station than one in NY• You may not notice any “interference”Ethernet MAC (CSMA/CD)• Carrier Sense Multiple Access/Collision DetectionPacket?Sense CarrierDiscardSendDetect CollisionNoYesLecture 7: 9-13-07 18Discard PacketJam channel b=CalcBackoff(); wait(b);attempts++;attempts < 16attempts == 16Ethernet’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• Why not random delay with fixed mean?• Few senders Æ needless waitingLecture 7: 9-13-07 19• Too many senders Æ too many collisions• Goal: adapt retransmission attempts to estimated current load• heavy load: random wait will be longerEthernet Backoff Calculation• Exponentially increasing random delay•Infer senders from # of collisions•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 {0123}Lecture 7: 9-13-07 20{0,1,2,3}…• After ten or more collisions, choose K from {0,1,2,3,4,…,1023}6Outline • Aloha• Ethernet MAC• CollisionsLecture 7: 9-13-07 21• Ethernet Frames• “Taking Turns” MAC and Other LANsCollisionsABCTimeLecture 7: 9-13-07 22Minimum Packet Size• What if two people sentpeople sent really small packets• How do you find collision?Lecture 7: 9-13-07 23Ethernet Collision Detect• Min packet length > 2x max prop delayIf A B t it id f li k d B t t•If A, B are at opposite sides of link, and B starts one link prop delay after A• Jam network for 32-48 bits after collision, then stop sending• Ensures that everyone notices collisionLecture 7: 9-13-07 24y7End to End Delay• c in cable = 60% * c in vacuum = 1.8 x 10^8 m/s•Modern 10Mb Ethernet {•Modern 10Mb Ethernet {• 2.5km, 10Mbps • ~= 12.5us delay• +Introduced repeaters (max 5 segments)• Worst case – 51.2us round
View Full Document