Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 26Slide 28Slide 29Slide 30Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 58Slide 63Slide 65Slide 66Slide 67Slide 68Slide 69Slide 70Slide 72Slide 73Slide 74115-441 Computer NetworksLecture 6Link-Layer (2) Dave Eckhardt1Hui Zhang, Dave EckhardtRoadmapWhat's a link layer?EthernetThings which aren't EthernetToken Bus, Token Ring, FDDI, Frame Relay802.11PPP, DSL, cable modemsA word on approachWe will discuss many "obsolete" technologiesThis can be a good way to grasp the underlying ideas–...which keep turning up in different contexts–A good arrangement of ideas is an easier advance than a genuinely new thing1Hui Zhang, Dave EckhardtReminder: Medium Access Control (MAC)Share a communication medium among multipleArbitrate between connected hostsGoals:High resource utilizationAvoid starvationSimplicity (non-decentralized algorithms)ApproachesTaking turns, random access, really-random access (SS)Random access = allow collisions–Manage & recover from them1Hui Zhang, Dave EckhardtOutlineEthernetConceptual historyCarrier sense, Collision detectionEthernet history, operation (CSMA/CD)Packet sizeEthernet evolutionConnecting EthernetsNot EthernetFDDI, wireless, ...1Hui Zhang, Dave EckhardtEthernet in ContextALOHAWhen you're ready, transmitDetect collisions by waiting (a long time)Recover from collision by trying again–...after a random delay...»Too short, entire network collapses»Too long, every user gets boredThings to trySlotted ALOHA – reduce collisions (some, not enough)Listen before transmitTrue collision detection1Hui Zhang, Dave EckhardtListen Before TransmitBasic ideaDetect, avoid collisions – before they happenListen before transmit (officical name: "Carrier Sense")–Don't start while anybody else is already goingWhy didn't ALOHA do this?"Hidden terminal problem"1Hui Zhang, Dave EckhardtHidden Terminal ProblemA and B are deaf to each otherCan't sense each other's carrierCarrier sense "needs help" in this kind of environmentBut CS can work really well in an enclosed environment (wire)ACB1Hui Zhang, Dave EckhardtCollision DetectionIs Carrier sense enough?Sometimes there is a “race condition”–Two stations listen at the same time–Both hear nothing, start to transmit–Result: collision»Could last “for a while”»Can we detect it while it's happening?Collision DetectionListen while you transmitIf your signal is “messed up”, assume it's due to a collisionGreat idea! Why didn't ALOHA do it?1Hui Zhang, Dave EckhardtCollision DetectionCollision detection difficult for radios“Inverse-square law” relates power to distance–At A, A's transmission drowns out B's–At B, B's transmission drowns out A's–Neither can hear each other, C hears mixture (collision)Many radios disable receiver while transmitting–Huge power of local transmitter may damage receiverCollision detection can be done inside a wire1Hui Zhang, Dave EckhardtOriginal Xerox PARC Ethernet DesignMedium – one long cable snaked through your buildingTransceiver – fancy radio with collision detection“Vampire tap”Drill hole into cable (carefully!)Insert pin to touch center connector (carefully!!)Coaxial cablewww.ethermanage.com/ethernet1Hui Zhang, Dave EckhardtOriginal Xerox PARC Ethernet DesignCarrier-sense multiple access with collision detection (CSMA/CD). MA = multiple accessCS = carrier senseCD = collision detectionPARC Ethernet parameters3 Mb/s (to match Xerox Alto workstation RAM throughput)256 stations (1-byte destination, source addresses)1 kilometer of cable1Hui Zhang, Dave Eckhardt802.3 EthernetBroadcast technologyDEC/Intel/Xerox (“DIX”) Ethernet standardized by IEEE3 Mb/s 10 Mb/sStation addresses 1 byte 6 bytesGrowth over the yearsHubs, bridges, switches100Mbps, 1Gbps, 10GbpsThin coax, twisted pair, fiber, wirelesshost host host hosthost host host hostHub1Hui Zhang, Dave EckhardtCSMA/CD AlgorithmListen for carrierIf carrier sensed, wait until carrier ends.Sending would force a collision and waste timeSend packet and listen for collision.If no collision detected, consider packet delivered.OtherwiseAbort immediately–Transmit "jam signal" (32 bits) to fill cable with errorsPerform “exponential back-off” to try packet again.1Hui Zhang, Dave EckhardtExponential Back-offBasic ideaChoose a random interval (e.g., 8 small-frame times)–Delay that long, try againHow long should interval be?–...roughly 1 time per station contending for medium...–...can't tell, must guess1Hui Zhang, Dave EckhardtExponential Back-offExponential Back-offFirst collision: delay 0 or 1 periods (512 bits)–50/50% probability–Appropriate if two stations contending for mediumSecond collision: delay 0...3 periods–Will work well if “roughly 4” stations contendingThird collision: delay 0...7 timesTen collisions?–Give up, tell device driver “transmission failed”1Hui Zhang, Dave EckhardtCollision DetectionTimeA B C1Hui Zhang, Dave EckhardtCollision Detection: ImplicationsGoal: every node detects collision as it's happendingAny node can be senderSo: need short wires, or long packets.Or a combination of bothCan calculate length/distance based on transmission rate and propagation speed.Messy: propagation speed is medium-dependent, low-level protocol details, ..Minimum packet size is 64 bytesCable length ~256 bit timesExample: maximum coax cable length is 2.5 kmA B C1Hui Zhang, Dave EckhardtMinimum Packet SizeWhy put a minimum packet size?Give a host enough time to detect collisionsIn 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 bytesWhat is the relationship between minimum packet size and the length of the LAN?1Hui Zhang, Dave EckhardtMinimum Packet Size (more)propagation delay (d)a) Time = t; Host 1 starts to send frameHost 1 Host 2propagation delay (d)Host 1 Host 2b) Time = t + d; Host 2 starts to send a frame just before it hears fromhost 1’s framepropagation delay (d)Host 1 Host 2c) Time = t + 2*d; Host 1 hears Host 2’s frame detects collisionLAN length = (min_frame_size)*(light_speed)/(2*bandwidth) = =
View Full Document
Unlocking...