Media Access Control 7 Chapter 6 MAC 1 MAC 2 Outline Why use MAC protocols General classes of MAC protocols Standard LAN protocols Broadband Access Deterministic Random Access Cable DSL Other Satellite Networks Media Access Control Protocols provide Direct access to the media Distributed control over resource allocation Typically broadcast real or virtual MAC 3 MAC 4 Media Access Control Advantages High data rates open new applications Low cost Local organizational control Wireless is a broadcast media and efficient use of resources is important Enable sharing of resources Mobility via Wireless Media Access Control MAC protocols establish a set of rules that govern who gets to use the shared transmission media in an efficient manner Obstacle to perfect channel utilization Finite propagation delay means that each users knowledge of the state of the system is imperfect and thus they can not perfectly schedule transmissions i e some time will be wasted attempting to learn the state of the system and or learning the fate of transmissions Lost messages MAC 5 Media Access Control Perfect Knowledge would lead to FIFO performance Performance of MAC protocols will be compared to FIFO performance Ideal MAC Performance MAC 6 Impact of MAC Overhead MAC Protocol 2 E T E X Transfer Delay MAC Protocol 1 1 Load Smax 1 Smax 2 1 Adapted from Leon Garcia Widjaja Communication Networks MAC 7 MAC 8 Alternative Media Access Control Strategies Static Allocation FDM TDM Problems Management not easy to add users Requires signaling Wasteful in resources for bursty traffic Example A transmission media has a rate of 10 Mb s and supports 50 users The system uses static allocation A user has a 1 Mbyte file to transmit The file transfer time is Alternative Media Access Control Strategies Suppose you send a message to all the other 49 users saying I need the whole channel for about 1sec do not use it please As long as the overhead incurred in sending the message is less than 39 sec the user will get better performance MAC 9 Alternative Media Access Control Strategies Deterministic Polling Token networks Random Access ALOHA Carrier sense multiple access CSMA CSMA with collision detection CSMA CD MAC 10 Alternative Media Access Control Strategies Dynamic allocation of resources Deterministic Polling Token Ring Token Bus Advantage the maximum time between users chances to transmit is bounded assuming a limit on the token holding time Disadvantage Time is wasted polling other users if they have no data to send The technology does not scale MAC 11 MAC 12 Deterministic Protocols Roll Call Polling Master slave arrangement Master polls each node Do you have data to send If the polled node has data it is sent otherwise next node is polled Deterministic Protocols Node Node Master Node Node Maximum token holding time Maximum time a station is allowed to transmit before passing on the permission to transmit the token MAC 13 MAC 14 Deterministic Protocols Hub Polling No master station Each nodes polls the next node in turn Node Node Node Node Node Deterministic Protocols Example nodes 10 Link rate 1 Mb s Packet Size 1000 bits Assume Low load no queueing 0 1 ms between nodes 30 km 3x108m s 0 1ms Find the effective transmission rate and efficiency Repeat for link rate 10 Mb s On average destination is 5 nodes away 5 ms Time to transmit 1000 bits 0 5 ms 1 ms 1 5 ms Effective transmission rate 1000 bits 1 5 ms 666Kb s Efficiency 666 Kb s 1000 Kb s 0 66 On average destination is 5 nodes away 5 ms Time to transmit 1000 bits 0 5 ms 1 ms 6 ms Effective transmission rate 1000 bits 6 ms 1 67 Mb s Efficiency 1 67 Mb s 10 Mb s 16 7 Conclusion Polling does not scale with link rate MAC 15 Alternative Media Access Control Strategies Random Access Each node sends data with limited coordination between users No explicit permission to transmit Total chaos Send data as soon as ready Limited chaos Listen before sending data if the channel is busy do not send Further Limiting chaos Listen before sending data continue listening after sending and if collision with another transmission stop sending Carrier Sense Multiple Access with Collision Detection CSMA CD MAC 16 Alternative Media Access Control Strategies Random Access Advantage Simple Disadvantage No guarantee that you will ever get to send The MAC protocol technology does not scale MAC 17 MAC 18 Random Access Protocols Assumptions Overlap in time and space of two or more transmissions causes a collision and the destruction of all packets involved No capture effects One channel For analysis no station buffering Random Access Protocols Assumptions Time Alternatives Synchronization between users Slotted time No synchronization between users unslotted time Knowledge of the channel stateAlternatives Carrier sensing Listen before talk LBT Collision detection MAC 19 MAC 20 Random Access Protocols Strategies ALOHA Backoff No coordination between users Send a PDU wait for acknowledgment if no acknowledgment ASSUME collision then backoff and try again Select random time to attempt another transmission Slotted ALOHA Same as ALOHA only time is slotted Random Access Protocols Strategies p persistent CSMA Listen to channel on transition from busy to idle transmit with probability p After sending the PDU wait for acknowledgment if no acknowledgment then backoff and retransmit Non persistent if channel busy then reschedule transmission 1 persistent Transmit as soon as idle MAC 21 Random Access Protocols Strategies CSMA CD 1 persistent but continue to sense the channel if collision detected then stop transmission CSMA CD is used in 10 100 Mb s and 1 Gb s Ethernet MAC 22 Limitations on Random Access Protocols Distance Time to learn channel state Propagation time Speed Time to learn channel state Clocking speed MAC 23 Random Access Protocols Analysis of ALOHA Goal Find Smax Protocol Operation Packet of length L sec arrives at station i Station i transmits immediately Station i starts an acknowledgment timer If no other station transmits while i is transmitting then success Else a collision occurred Station i learns that a collision occurred if the acknowledgment timer fires before the acknowledgment arrives MAC 24 Random Access Protocols Analysis of Aloha collision detected then station i retransmitts at a later time this time is pseudo random and is determined by a backoff algorithm If Design Issue Determine the maximum normalized throughput for an Aloha system MAC 25 Random Access Protocols Analysis of