Distributed Medium Access ControlENEE 426 | Communication Networks | Spring 2008 Lecture 5Medium Access Control• Problem:– Single shared communications resource• RF spectrum, electrical cable, etc– Multiple users– How do you decide who communicates when?• Two approaches:– Infrastructure• Central controller handles all packet scheduling– Distributed• Distributed algorithm for determining who communicates whenENEE 426 | Communication Networks | Spring 2008 Lecture 5Infrastructure Duplexing• Each device needs to both send and receive data -> two channels• Uplink: channel from user to network• Downlink: channel from network to user• Time-Division Duplex (TDD)– Alternate sending and receiving in same channel– Half duplex– Example: voice communications• Frequency-Division Duplex (FDD)– Transmit on one frequency, receive on another– Full duplex– Example: cell phones• Space-Division Duplex– Isolated mediums for transmission– Full duplex– Example: fiber optic cable, modern Ethernet cableUP DOWN UPDOWNUPDOWNUPDOWN DOWNUPDOWNUPTimeENEE 426 | Communication Networks | Spring 2008 Lecture 5Multiple Access• Infrastructure: – Control access to uplink• Distributed: – Control access to shared medium– Distributed networks are half-duplex– No central controller -> users = networkENEE 426 | Communication Networks | Spring 2008 Lecture 5Early MAC Example• In the 1970s, University of Hawaii constructed a packet radio network to interconnect Hawaiian islands• In 1972 it was connected to ARPANET• Basic MAC approach:– If you have data to send, send it– If the message you send interferes with someone else, try againENEE 426 | Communication Networks | Spring 2008 Lecture 5ALOHA• Performance very poor• Introduced slotted Aloha• Time broken up into slots, transmissions aligned to slots• Successful if only one transmission during slotENEE 426 | Communication Networks | Spring 2008 Lecture 5ALOHA Performance• Per-user rate as a function of users• Total rate converges to 0.368ENEE 426 | Communication Networks | Spring 2008 Lecture 5ALOHA Performance• Poor performance due to statistical independence of time slots• If collision occurs– Wait before retransmitting• How long?– Probability of retransmitting in next slot decreases exponentially– Exponential backoffENEE 426 | Communication Networks | Spring 2008 Lecture 5ALOHA’s impact• Foundation of modern CSMA/CD– Carrier Sense Multiple Access / Collision Detection• Steps:– Carrier present?• If busy, restart• if idle transmit– Packet received without errors?• If yes, done• If no, transmit jamming signal so others know a packet collision occurred and wait random amount of time and restart• Protocol used in Ethernet 10 Mbps MACENEE 426 | Communication Networks | Spring 2008 Lecture 5Hidden Terminal Problem• In RF, range of shared medium is limited• Result: Hidden Terminal Problem• Scenario:– User A starts transmitting to user B– User C listens, hears idle– User C starts transmitting to user B– Packet collisionUser A User B User CENEE 426 | Communication Networks | Spring 2008 Lecture 5Exposed Terminal Problem• Nodes may determine medium is busy when it is in fact idleENEE 426 | Communication Networks | Spring 2008 Lecture 5CSMA/CD Improvements• CSMA/CD insufficient for wireless broadcast channels• CSMA/CA– Carrier Sense Multiple Access / Collision Avoidance• Add new management messages– Request to Send (RTS)– Clear to Send (CTS)• RTS is transmitted and CTS is received before data is transmitted• RTS and CTS are small packets, so their overhead and probability of interfering is