1 1 EE 122: Ethernet Ion Stoica TAs: Junda Liu, DK Moon, David Zats http://inst.eecs.berkeley.edu/~ee122/ (Materials with thanks to Vern Paxson, Jennifer Rexford, and colleagues at UC Berkeley) 2 Goals of Today’s Lecture MAC (Media Access Control) protocols, esp. CSMA/CD Carrier Sense Multiple Access / Collision Detection Ethernet: single segment Frame structure Length/timing constraints due to Collision Detection Ethernet: spanning multiple segments Repeaters and hubs Bridges and switches Self-learning (plug-and-play) Spanning trees (time permitting) 3 Three Ways to Share the Media Channel partitioning MAC protocols (TDMA, FDMA): 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 4 Key Ideas of Random Access Carrier sense 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 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 Don’t start talking again right away Waiting for a random time before trying again2 5 CSMA Collisions Collisions can still occur: propagation delay means two nodes may not hear each other’s transmission in time. 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. Collision: entire packet transmission time wasted 6 CSMA/CD (Collision Detection) CSMA/CD: carrier sensing, deferral as in CSMA 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 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 7 CSMA/CD Collision Detection 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 8 Ethernet: CSMA/CD Protocol 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 Mbps3 9 Minimum Packet Size 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? 10 Minimum Packet Size (more) propagation delay (d) a) Time = t; Host 1 starts to send frame Host 1 Host 2 propagation delay (d) Host 1 Host 2 b) Time = t + d; Host 2 starts to send a frame, just before it hears from host 1’s frame propagation delay (d) Host 1 Host 2 c) Time = t + 2*d; Host 1 hears Host 2’s frame detects collision LAN length = (min_frame_size)*(light_speed)/(2*bandwidth) = = (8*64b)*(2.5*108mps)/(2*107 bps) = 6400m approx What about 100 mbps? 1 gbps? 10 gbps? 11 Limits on CSMA/CD Network Length Latency depends on physical length of link Time to propagate a packet from one end to the other Suppose A sends a packet at time t And B sees an idle line at a time just before t+d … so B happily starts transmitting a packet B detects a collision, and sends jamming signal But A can’t see collision until t+2d latency d!A!B!12 Limits on CSMA/CD Network Length 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: Maximum length of the wire: 2,500 meters Minimum length of a frame: 512 bits (64 bytes) 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 latency d!A!B!4 13 Ethernet Frame Structure Sending adapter encapsulates packet in frame Preamble: synchronization Seven bytes with pattern 10101010, followed by one byte with pattern 10101011 Used to synchronize receiver & sender Type: indicates the higher layer protocol Usually IP (but also Novell IPX, AppleTalk, …) CRC: cyclic redundancy check Receiver checks & simply drops frames with errors 14 Ethernet Frame Structure (Continued) Addresses: 48-bit source and destination MAC addresses Receiver’s adaptor passes frame to network-level 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: Maximum: 1,500 bytes Minimum: 46 bytes (+14 bytes header
View Full Document
Unlocking...