1 Media Access (MAC) Protocols Lecture 10 6.02 Fall 2010 October 13, 2010 • Shared-medium networks • Time-Division Multiple Access (TDMA) • Contention protocols (Aloha) • Analysis of utilization Shared Media Networks Satellite'Ethernet'Wireless'local''area'networks'Wireless'LANs'Cellular''wireless'The Problem: Share Medium Efficiently • Want high channel utilization • Throughput = Useful bit rate (in bits/s or pkts/s) • U = Throughput / Channel Rate • Suppose node k gets n_k bits through in time T, over medium of maximum rate R bits/s • Then utilization = (Σn_k /T) / R • Easy to achieve: just allow one node to send all the time • So… want fairness also • Example: All nodes with data to send should get equal share over time (simple view of fairness) Many Media Access (MAC) Protocols • Aka “multiple access” protocols • Frequency Division Multiple Access (FDMA) • Time Division Multiple Access (TDMA) • Used in some cellular networks, Bluetooth • Poor performance with burst traffic • Contention-based protocols • Aloha • Carrier Sense Multiple Access (CSMA) used in Ethernet, WiFi • Channel reservation schemes • Topic of active research in wireless networks Time Division (TDMA) • Simple version: Time is slotted, each packet (“frame”) is one slot in length, nodes are numbered 0, 1, …, N-1 • Nodes take turns in round-robin order • If current time-slot is t, then node #(t mod N) gets to send, where N is the maximum number of nodes • Extend to handle packets that are larger than one slot (in lab) Our Aloha Protocol • Model: time increases in multiples of a “slot time” • All packets are an integral number of slots long; sender sends at start of a time slot • Sender: Send packet with probability p • Receiver: if received successfully, send ACK feedback • Sender: If no ACK within small timeout, sender believes packet was lost (“collision”) • Now sender has two choices: • Drop this packet and move to next packet • Or, retry packet2 Aloha in Pictures: Collisions • A collision occurs when multiple transmissions overlap in time (even partially) • Throughput = Uncollided packets per second • Utilization = Throughput / Channel Rate Packet is 5 slots long in this picture Collisions! Slotted Aloha Each Packet is Exactly One Time Slot Long • Throughput = Uncollided packets per second • Utilization = Throughput / Channel Rate Utilization of Slotted Aloha • Each packet = 1 slot • Note: Node sends packets only at slot boundaries • N backlogged nodes (nodes with data) Then,&U&=&Np(1-p)(N-1)&Stabilization: Selecting the right p • Use absence of ACK from receiver as hint that collision has occurred • If pkt lost, decrease p Multiplicative decrease: p p/2 Binary Exponential Backoff • If pkt received, increase p p 2*p • Such increase/decrease thinking used widely distributed network protocols • How well does it work? Performance: Severely Unfair! Y-axis is per-node transmission probability Bottom panel: per-node throughput Performance with Fixes: Much Better Y-axis is per-node transmission probability Bottom panel: per-node
View Full Document