Goals of Today s Lecture MAC Media Access Control protocols esp CSMA CD EE 122 Ethernet Ethernet single segment Ion Stoica TAs Junda Liu DK Moon David Zats Materials with thanks to Vern Paxson Jennifer Rexford and colleagues at UC Berkeley 1 Three Ways to Share the Media 3 Repeaters and hubs Bridges and switches Self learning plug and play Spanning trees time permitting Key Ideas of Random Access Channel partitioning MAC protocols TDMA FDMA Carrier sense Share channel efficiently and fairly at high load Inefficient at low load where load senders 1 N bandwidth allocated even if only 1 active node Taking turns protocols discussed in Section Eliminates empty slots without causing collisions Overhead in acquiring the token Vulnerable to failures e g failed node or lost token Random access MAC protocols Efficient at low load single node can fully utilize channel High load collision overhead Listen before speaking and don t interrupt Checking if someone else is already sending data and waiting till the other node is done Collision detection 2 Frame structure Length timing constraints due to Collision Detection Ethernet spanning multiple segments http inst eecs berkeley edu ee122 Carrier Sense Multiple Access Collision Detection If someone else starts talking at the same time stop Realizing when two nodes are transmitting at once by detecting that the data on the wire is garbled Randomness 4 Don t start talking again right away Waiting for a random time before trying again 1 CSMA Collisions Collisions can still occur propagation delay means two nodes may not hear each other s transmission in time CSMA CD Collision Detection CSMA CD carrier sensing deferral as in CSMA At time t1 D still hasn t heard B s signal sent at the earlier time t0 so D goes ahead and transmits failure of carrier sense Collisions detected within short time Colliding transmissions aborted reducing wastage Collision detection Easy in wired LANs measure signal strengths compare transmitted received signals Difficult in wireless LANs Collision entire packet transmission time wasted 5 6 CSMA CD Collision Detection Ethernet CSMA CD Protocol Both B and D can tell that collision occurred This lets them 1 know that they need to resend the frame and 2 recognize that there s contention and adopt a strategy for dealing with it Note for this to work we need restrictions on minimum frame size and maximum distance 7 Reception shut off while transmitting Even if on might not be able to hear the other sender even though the receiver can Leads to use of collision avoidance instead 8 Carrier sense wait for link to be idle Collision detection listen while transmitting No collision transmission is complete Collision abort transmission send jam signal Random access exponential back off After collision wait a random time before trying again After mth collision choose K randomly from 0 2m 1 and wait for K 512 bit times before trying again The wired LAN technology Hugely successful 3 10 100 1000 10000 Mbps 2 Minimum Packet Size Minimum Packet Size more a Time t Host 1 starts to send frame Why enforce a minimum packet size Give a host enough time to detect collisions In Ethernet minimum packet size 64 bytes two 6 byte addresses 2 byte type 4 byte CRC and 46 bytes of data If host has less than 46 bytes to send the adaptor pads adds bytes to make it 46 bytes What is the relationship between minimum packet size and the length of the LAN b Time t d Host 2 starts to send a frame just before it hears from host 1 s frame c Time t 2 d Host 1 hears Host 2 s frame detects collision Host 1 Host 2 propagation delay d Host 1 Host 2 propagation delay d Host 1 Host 2 propagation delay d LAN length min frame size light speed 2 bandwidth 8 64b 2 5 108mps 2 107 bps 6400m approx 9 10 What about 100 mbps 1 gbps 10 gbps Limits on CSMA CD Network Length Limits on CSMA CD Network Length B A B A latency d Latency depends on physical length of link And B sees an idle line at a time just before t d so B happily starts transmitting a packet A needs to wait for time 2d to detect collision So A should keep transmitting during this period and keep an eye out for a possible collision Imposes restrictions E g for 10 Mbps Ethernet B detects a collision and sends jamming signal 11 Time to propagate a packet from one end to the other Suppose A sends a packet at time t latency d Maximum length of the wire 2 500 meters Minimum length of a frame 512 bits 64 bytes But A can t see collision until t 2d 12 512 bits 51 2 sec at 10 Mbit sec For light in vacuum 51 2 sec 15 000 meters vs 5 000 meters round trip to wait for collision 3 Ethernet Frame Structure Sending adapter encapsulates packet in frame Ethernet Frame Structure Continued Addresses 48 bit source and destination MAC addresses Receiver s adaptor passes frame to network level protocol Preamble synchronization 13 Usually IP but also Novell IPX AppleTalk CRC cyclic redundancy check Receiver checks simply drops frames with errors Ethernet con t Connectionless No handshaking between sending and receiving adapter Unreliable Receiving adapter doesn t send ACKs or NACKs Packets passed to network layer can have gaps Gaps will be filled if application is using TCP Otherwise application will see the gaps 2 700 page IEEE 802 3 standardization http standards ieee org getieee802 802 3 html Note classical Ethernet has no length field instead sender pauses 9 2 sec when done 802 3 shoehorns in a length field 15 Seven bytes with pattern 10101010 followed by one byte with pattern 10101011 Used to synchronize receiver sender Type indicates the higher layer protocol If destination address matches the adaptor s Or the destination address is the broadcast address ff ff ff ff ff ff Or the destination address is a multicast group receiver belongs to Or the adaptor is in promiscuous mode Addresses are globally unique Assigned by NIC vendors top three octets specify vendor During any given week 500 vendor codes seen at LBNL Data 14 Maximum 1 500 bytes Minimum 46 bytes 14 bytes header 4 byte trailer 512 bits Benefits of Ethernet Easy to administer and maintain Inexpensive Increasingly higher speed Evolved from shared media to switches And from electrical signaling to also optical Changes everything except the frame format A good general lesson for evolving the Internet The right interface service model can often accommodate unanticipated changes 16 4 Shuttling Data at Different Layers Different devices switch different things Physical Layer
View Full Document
Unlocking...