Packet Multiple Access II: Local Area Networks (LANs) Eytan Modiano Massachusetts Institute of Technology Department of Aeronautics and Astronautics Eytan Modiano Slide 1 CSMA/CD and Ethernet Two way cable WS WS WS WS WS WS ? CSMA with Collision Detection (CD) capability – Nodes able to detect collisions – Upon detection of a collision nodes stop transmission Reduce the amount of time wasted on collisions ? Protocol: – All nodes listen to transmissions on the channel – When a node has a packet to send: Channel idle => Transmit Channel busy => wait a random delay (binary exponential backoff ) – If a transmitting node detects a collision it stops transmission Slide 2 Eytan Modiano Waits a random delay and tries again τττ τττ τττ === Time to detect collisions WS WS τ τ = prop delay ? A collision can occur while the signal propagates between the two nodes ? It would take an additional propagation delay for both users to detect the collision and stop transmitting ? If τ is the maximum propagation delay on the cable then if a collision occurs, it can take up to 2 τ seconds for all nodes involved in the collision to detect and stop transmission Eytan Modiano Slide 3 τττ Approximate model for CSMA/CD ? Simplified approximation for added insight ? Consider a slotted system with “mini-slots ” of duration 2 τ 2222 ττττ <<<< ???? ???? >>>> <----------- ----------------> 1 packet minislots ? If a node starts transmission at the beginning of a mini-slot, by the end of the mini-slot either – No collision occurred and the rest of the transmission will be uninterrupted – A collision occurred, but by the end of the mini-slot the channel would be idle again ? Hence a collision at most affects one mini-slot Eytan Modiano Slide 4 Analysis of CSMA/CD ? Assume N users and that each attempts transmission during a free “mini-slot ” with probability p – P includes new arrivals and retransmissions ? N ? i N ? i P (i users attempt) = ? ? i ? ? P( 1 ? P ) P(exactly 1 attempt) = P(success) = NP(1 - P ) N- 1 To maximize P(success), d dp [NP(1 - P ) N- 1 ] = N(1 - P ) N - 1 ? N(N ? 1)P(1 ? P) N ? 2 = 0 1 ? P = opt N ? Average attempt rate of one per slot ? Notice the similarity to slotted Aloha Eytan Modiano Slide 5 Analysis of CSMA/CD, continued 1 P(success) = NP(1 - p ) N- 1 = ( 1 ? N ) N ? 1 1 P s = limit (N →∞ ) P(success) = e Let X = Average number of slots per succesful transmission ? P(X = i) = (1 - P s ) i1 P s 1 ? E[X] = = e P s ? Once a mini-slot has been successfully captured, transmission continues without interruption ? New transmission attempts will begin at the next mini-slot after the end of the current packet transmission Eytan Modiano Slide 6 τττ τττ τττ τττ βββ τττ ≈≈≈ βββ λλλ βββ Analysis of CSMA/CD, continued ? Let S = Average amount of time between successful packet transmissions S = (e-1)2 τ + D Tp + τ Ave time until start of next Mini-slot Idle/collision Mini-slots Packet transmission time ? Efficiency = D Tp /S = D Tp / (D Tp + τ + 2 τ (e-1)) ? Let β = τ / D Tp => Efficiency ≈ 1/(1+4.4 β ) = λ < 1/(1+4.4 β ) Eytan Modiano Slide 7 Notes on CSMA/CD ? Can be viewed as a reservation system where the mini-slots are used for making reservations for data slots ? In this case, Aloha is used for making reservations during the mini-slots ? Once a users captures a mini-slot it continues to transmit without interruptions ? In practice, of course, there are no mini-slots – Minimal impact on performance but analysis is more complex Eytan Modiano Slide 8 τττ ββββ ββ CSMA/CD examples ? Example (Ethernet) – Transmission rate = 10 Mbps – Packet length = 1000 bits, D Tp = 10 -4 sec – Cable distance = 1 mile, τ = 5x10 -6 sec – β = 5x10-2 and E = 80% ? Example (GEO Satellite) - propagation delay 1/4 second – β = 2,500 and E ~ 0% ? CSMA/CD only suitable for short propagation scenarios! ? How is Ethernet extended to 100 Mbps? ? How is Ethernet extended to 1 Gbps ? Eytan Modiano Slide 9 Token rings ? Token rings were developed by IBM in early 1980 ’ s ? Token: a bit sequence – Token circulates around the ring Busy token: 01111111 Free token: 01111110 ? When a node wants to transmit – Wait for free token – Remove token from ring (replace with busy token) – Transmit message – When done transmitting, replace free token on ring – Nodes must buffer 1 bit of data so that a free token can be changed to a busy token ? Token ring is basically a polling system Token does the polling Token Ring Eytan Modiano Slide 1 0 Release of token ? Release after transmission – Node replaces token on ring as soon as it is done transmitting the packet – Next node can use token after short propagation delay ? Release after reception – Node releases token only after its own packet has returned to it Serves as a simple acknowledgement mechanism Eytan Modiano Slide 1 1 λλλ Throughput analysis (Release after transmission) ? Suppose each node transmits one packet and then releases the token to the next node – V i = propagation and transmission time for token between two nodes (transmission time is usually negligible) ? The amount of time to transmit N packets T N = N*E[X] + V 1 + V 2 + …+ V N = N*E[X] + N*E[V] λ < N*E[X]/(N*E[X] + N*E[V]) = 1/(1+E[V]/E[X]) ? Compare to CSMA/CD, but notice that V is the delay between two nodes and not the maximum delay on the fiber Eytan Modiano Slide 1 2 λλλ Throughput analysis (release after reception) ? Nodes release token only after it has returned to it ? Again assume each node sends one packet at a time ? Total time to send ONE packet Time to send token to next node ? T = E[X] + V 1 + V 2 +…+ V m + V i M nodes on the ring ? T = E[X] + (m+1)E[V] => λ < E[X]/T = 1/(1+(m+1)E[V]/E[X]) Eytan Modiano Slide 1 3 Token ring issues ? Fairness: Can a node hold the token for a long time – Solution: maximum token hold time ? Token failures: Tokens can be created or destroyed by noise – Distributed solution: Nodes are allowed to recognize the loss of a token and create a new token Collision occurs when two or more nodes create a new token at the same time => need collision resolution algorithms ? Node failures: Since each node must relay all incoming data, the failure of a single node will disrupt the operation of the ring ? Token ring standard: IEEE 802.5 Eytan Modiano Slide 1 4 Large propagation delay (satellite networks) 1 A = mv 5 4 3 2 Reservation Data Reservation Interval Interval Interval Frame Res Data Res Data Data Res Res Arrival Propagation Delay Transmit Wait for Reser- Wait for Assigned vation Interval Data Slot ? Satellite reservation system – Use mini-slots to make reservation for longer data slots – Mini-slot access can be inefficient (Aloha, TDMA, etc.) ? To a crude approximation, delay is 3/2 times the propagation delay plus ideal queueing delay. Eytan Modiano Slide 1 5 Satellite Reservations ? Frame length must exceed round-trip delay – Reservation slots during frame j are used to reserve data slots in frame j+1 – Variable length: serve all requests from frame j in frame j+1 Difficult to maintain synchronization Difficult to provide QoS (e.g., support voice traffic) – Fixed length: Maintain a virtual queue of requests ? Reservation mechanism – Scheduler on board satellite – Scheduler on ground – Distributed queue algorithm All nodes keep track of reservation requests and use the same algorithm to make reservation ? Control channel access – TDMA: Simple but difficult to add more users – Aloha: Can support large number of users but collision resolution can be difficult and add enormous delay Eytan Modiano Slide 1 6 Aloha Reservations ? Use Aloha to capture a slot ? After capturing a slot user keeps the slot until done – Other users observe the slot busy and don ’t attempt ? When done other users can go after the slot – Other users observe the slot idle and attempt using Aloha ? Method useful for long data transfers or for mixed voice and data Slot 1 2 3 4 5 6 frame 1 frame 2 frame 3 frame 4 frame 5 15 3 2 0 2 15 7 3 9 7 9 7 9 18 7 3 15 9 6 18 idle idle idle idle 2 3 3 6 Eytan Modiano Slide 1 7 ααα ααα Packet multiple access summary ? Latency: Ratio of propagation delay to packet transmission time – GEO example: D p = 0.5 sec, packet length = 1000 bits, R = 1Mbps Latency = 500 => very high – LEO example: Dp = 0.1 sec Latency = 100 => still very high – Over satellite channels data rate must be very low to be in a low latency environment ? Low latency protocols – CSMA/CD, Polling, Token Rings, etc. – Throughput ~ 1/(1+ a α ), α = latency, a = constant ? High latency protocols – Aloha is insensitive to latency, but generally low throughput Very little delays – Reservation system can achieve high throughput Delays for making reservations – Protocols can be designed to be a hybrid of Aloha and reservations Aloha at low loads, reservations at high loads Eytan Modiano Slide 1 8 Comparison of MAC protocols Load (packets/second) Delay in seconds 0 2 4 6 8 10 12 14 16 18 20 0 0.2 0.4 0.6 0.8 ALOHA SCHEMES TDMA (10 USERS) Perfect Scheduling (M/M/1) Reservation with 20% overhead packet length 2400 bits transmission rate 2400 bps GEO Satellite with 0.5 second round-trip delay Eytan Modiano Slide 1 9