15-441 Computer NetworkingMAC Protocols: A TaxonomyOutlineRandom Access ProtocolsAloha – Basic TechniqueSlotted AlohaPure (Unslotted) ALOHASlide 8EthernetEthernet MAC – Carrier SenseEthernet MAC – Collision DetectionEthernet MAC (CSMA/CD)Ethernet’s CSMA/CD (more)Ethernet Backoff CalculationSlide 15Slotted Aloha EfficiencyPure Aloha (cont.)Simple Analysis of EfficiencyEthernet ProblemsSlide 20Minimum Packet SizeEthernet Collision DetectEnd to End DelayPacket SizeEthernet Frame StructureEthernet Frame Structure (cont.)Slide 27Addressing AlternativesSlide 29Ethernet Technologies: 10Base210BaseT and 100BaseT10BaseT and 100BaseT (more)Gbit EthernetSlide 34LAN SwitchingSwitched Network AdvantagesSlide 37“Taking Turns” MAC Protocols“Taking Turns” MAC protocolsToken RingsWhy Did Ethernet Win?15-441 Computer NetworkingLecture 5 – EthernetLecture 5: 9-11-01 2MAC 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 collisions•“Taking turns”•Tightly coordinate shared access to avoid collisionsGoal: efficient, fair, simple, decentralizedLecture 5: 9-11-01 3Outline •Random Access MAC Protocols•Ethernet MAC•Random Access Analysis•Other Ethernet Issues•“Taking Turns” MAC and Other LANsLecture 5: 9-11-01 4Random 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/CDLecture 5: 9-11-01 5Aloha – Basic Technique•First random MAC developed•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 delay•Too short large number of collisions•Too long underutilizationLecture 5: 9-11-01 6Slotted Aloha•Time is divided into equal size slots (= pkt trans. time)•Node (w/ packet) transmits at beginning of next slot •If collision: retransmit pkt in future slots with probability p, until successfulSuccess (S), Collision (C), Empty (E) slotsLecture 5: 9-11-01 7Pure (Unslotted) ALOHA•Unslotted Aloha: simpler, no synchronization•Pkt needs transmission:• Send without awaiting for beginning of slot•Collision probability increases:•Pkt sent at t0 collide with other pkts sent in [t0-1, t0+1]Lecture 5: 9-11-01 8Outline •Random Access MAC Protocols•Ethernet MAC•Random Access Analysis•Other Ethernet Issues•“Taking Turns” MAC and Other LANsLecture 5: 9-11-01 9Ethernet•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 EthernetsketchLecture 5: 9-11-01 10Ethernet MAC – Carrier Sense•Basic idea:•Listen to wire before transmission•Avoid collision with active transmission•Why didn’t ALOHA have this?•In wireless, relevant contention at the receiver, not sender•Hidden terminal•Exposed terminalABCABCDHidden ExposedLecture 5: 9-11-01 11Ethernet MAC – Collision Detection•Note: ALOHA has collision detection also, should really be called “Fast Collision Detection”•Basic idea:•Listen while transmitting•If you notice interference assume collision•Why didn’t ALOHA have this?•Very difficult for radios to listen and transmit•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”Lecture 5: 9-11-01 12Ethernet MAC (CSMA/CD)Packet?Sense CarrierDiscard PacketSendDetect CollisionJam channel b=CalcBackoff(); wait(b);attempts++;NoYesattempts < 16attempts == 16•Carrier Sense Multiple Access/Collision DetectionLecture 5: 9-11-01 13Ethernet’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•heavy load: random wait will be longerLecture 5: 9-11-01 14Ethernet 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 ten or more collisions, choose K from {0,1,2,3,4,…,1023}Lecture 5: 9-11-01 15Outline •Random Access MAC Protocols•Ethernet MAC•Random Access Analysis•Other Ethernet Issues•“Taking Turns” MAC and Other LANsLecture 5: 9-11-01 16Slotted Aloha EfficiencyQ: What is max fraction slots successful?A: Suppose N stations have packets to send•Each transmits in slot with probability p•Prob. successful transmission S is:by single node: S = p (1-p)(N-1)by any of N nodes S = Prob (only one transmits) = N p (1-p)(N-1) … choosing optimum p as N -> infty ... … p = 1/N = 1/e = .37 as N -> inftyAt best: channeluse for useful transmissions 37%of time!Lecture 5: 9-11-01 17Pure Aloha (cont.)P(success by given node) = P(node transmits) X P(no other node transmits in [p0-1,p0] X P(no other node transmits in [p0-1,p0] = p X (1-p)(N-1) X (1-p)(N-1)P(success by any of N nodes) = N p X (1-p)(N-1) X (1-p)(N-1) = 1/(2e) = .18 … choosing optimum p as N infty p = 1/2N …S = throughput = “goodput” (success rate)G = offered load = N X p0.5 1.01.52.00.10.20.30.4Pure AlohaSlotted Alohaprotocol constrainseffective channelthroughput!Lecture 5: 9-11-01 18Simple Analysis of Efficiency•Key assumptions •All packets are same, small size•Packet size = size of contention slot•All nodes always have pkt to send•p is chosen carefully to be related to N•p is actually chosen by exponential backoff•Takes full slot to detect collision (I.e. no “fast collision detection”)Lecture 5: 9-11-01 19Ethernet Problems•Key concern: Ethernet
View Full Document
Unlocking...