1DataLink Layer 1Lecture Today slotted vs unslotted ALOHA Carrier sensing multiple access EthernetDataLink Layer 2Random Access Protocols When node has packet to send transmit at full channel data rate R. no a prioricoordination 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, CSMA/CD, CSMA/CA2DataLink Layer 3Slotted ALOHAAssumptions all frames same size time is divided into equal size slots, time to transmit 1 frame nodes start to transmit frames only at beginning of slots nodes are synchronized if 2 or more nodes transmit in slot, all nodes detect collisionOperation when node obtains fresh frame, it transmits in next slot no collision, node can send new frame in next slot if collision, node retransmits frame in each subsequent slot with prob. p until successDataLink Layer 4Slotted ALOHAPros single active node can continuously transmit at full rate of channel highly decentralized: only slots in nodes need to be in sync simpleCons collisions, wasting slots idle slots nodes may be able to detect collision in less than time to transmit packet3DataLink Layer 5Slotted Aloha efficiency N nodes with many frames to send, each transmits in slot with probability q (new arrival or re-Tx) prob that node 1 has success in a slot= q(1-q)N-1 Total expected utilization = Nq(1-q)N-1 For max efficiency with N nodes, find q* that maximizes Nq(1-q)N-1 For many nodes, take limit of Nq*(1-q*)N-1 as N goes to infinity, gives 1/e = .37Efficiency is the long-run fraction of successful slots when there are many nodes, each with many frames to sendAt best:channelused for useful transmissions 37%of time!DataLink Layer 6Pure (unslotted) ALOHA unslotted Aloha: simpler, no synchronization when frame first arrives transmit immediately collision probability increases: frame sent at t0collides with other frames sent in [t0-1,t0+1]4DataLink Layer 7Pure Aloha efficiencyP(success by given node) = P(node transmits at to) .P(no other node transmits in [t0-1,t0]) .P(no other node transmits in [t0,t0+1])= q . (1-q)N-1. (1-q)N-1= q. (1-q)2(N-1)… choosing optimum q and then letting N -> infty ...= 1/(2e) = .18 Even worse !DataLink Layer 8CSMA (Carrier Sense Multiple Access)CSMA: listen before transmit:If channel sensed idle: transmit entire frame If channel sensed busy, defer transmission Human analogy: don’t interrupt others! Do we then get effective channel partitioning, with no collisions possible?5DataLink Layer 9CSMA collisionscollisions canstill occur:propagation delay means two nodes may not heareach other’s transmissioncollision:entire packet transmission time wastedspatial layout of nodes note:role of propagation delay in determining collision probabilityDataLink Layer 10CSMA Efficiency Key parameters: Propagation delay (in seconds): tprop packet transmission time ttrans Efficiency depends only on tprop/ttran, and decreases with this parameter.6DataLink Layer 11CSMA Efficiency Decreases with tprop/ttrans Decreases with increasing distance between nodes. t_{trans} = R/L, where R is the link speed in bits/s and L is the frame length in bits. So efficiency decreases with increasing link speed R.DataLink Layer 12CSMA/CD (Collision Detection)CSMA/CD: carrier sensing, deferral as in CSMA collisions detectedwithin short time colliding transmissions aborted, reducing channel wastage collision detection: easy in wired LANs: measure signal strengths, compare transmitted, received signals difficult in wireless LANs: receiver shut off while transmitting human analogy: the polite conversationalist7DataLink Layer 13CSMA/CD collision detectionDataLink Layer 14Ethernet“dominant” wired LAN technology: cheap $20 for 100Mbs! first widely used LAN technology Simpler, cheaper than token LANs and ATM Kept up with speed race: 10 Mbps – 10 GbpsMetcalfe’s Ethernetsketch8DataLink Layer 15Star topology Bus topology popular through mid 90s Now star topology prevailshub DataLink Layer 16Unreliable, connectionless service Connectionless: No handshaking between sending and receiving adapter. Unreliable: receiving adapter doesn’t send acks or nacks to sending adapter stream of datagrams passed to network layer can have gaps gaps will be filled if app is using TCP otherwise, app will see the gaps9DataLink Layer 17Ethernet uses CSMA/CD No slots adapter doesn’t transmit if it senses that some other adapter is transmitting, that is, carrier sense transmitting adapter aborts when it senses that another adapter is transmitting, that is, collision detection Before attempting a retransmission, adapter waits a random time, that is, random accessDataLink Layer 18Ethernet CSMA/CD algorithm1. Adaptor receives datagram from net layer & creates frame2. If adapter senses channel idle, it starts to transmit frame. If it senses channel busy, waits until channel idle and then transmits3. If adapter transmits entire frame without detecting another transmission, the adapter is done with frame !4. If adapter detects another transmission while transmitting, aborts and sends jam signal5. After aborting, adapter enters exponential backoff: after the mthcollision, adapter chooses a K at random from {0,1,2,…,2m-1}. Adapter waits K·512 bit times and returns to Step
View Full Document
Unlocking...