Lectures 15 & 16 Local Area Networks Eytan Modiano Eytan Modiano Slide 1 Carrier Sense Multiple Access (CSMA) ? In certain situations nodes can hear each other by listening to the channel - “Carrier Sensing” ? CSMA: Polite version of Aloha – Nodes listen to the channel before they start transmission Channel idle => Transmit Channel busy => Wait (join backlog) – When do backlogged nodes transmit? When channel becomes idle backlogged nodes attempt transmission with probability q r = 1 Persistent protocol, q r = 1 Non-persistent protocol, q r < 1 Eytan Modiano Slide 2 CSMA ? Let τ = the maximum propagation delay on the channel – When a node starts/stops transmitting, it will take this long for all nodes to detect channel busy/idle ? For initial understanding, view the system as slotted with "mini- slots" of duration equal to the maximum propagation delay – Normalize the mini-slot duration to β = τ/D tp and packet duration = 1 β ?> minislots packet <----------- <? ----------------> 1 ? Actual systems are not slotted, but this hypothetical system simplifies the analysis and understanding of CSMA Eytan Modiano Slide 3 Rules for slotted CSMA ? When a new packet arrives – If current mini-slot is idle, start transmitting in the next mini-slot – If current mini-slot is busy, node joins backlog – If a collision occurs, nodes involved in collision become backlogged ? Backlogged nodes attempt transmission after an idle mini-slot with probability q r < 1 (non-persistent) – Transmission attempts only follow an idle mini-slot – Each”busy-period” (success or collision) is followed by an idle slot before a new transmission can begin ? Time can be divided into epochs: – A successful packet followed by an idle mini-slot (duration = β+1) – A collision followed by an idle mini-slot (duration = β+1) – An idle minislot (duration = β) Eytan Modiano Slide 4 ?Analysis of CSMA ? Let the state of the system be the number of backlogged nodes ? Let the state transition times be the end of idle slots – Let T(n) = average amount of time between state transitions when the system is in state n T(n) = β + (1 - e -λβ (1-q r ) n ) When qr is small (1-q r ) n ~ e -q r n => T(n) = β + (1 - e -λβ?nq r ) ? At the beginning of each epoch, each backlogged node transmits with probability q r ? New arrivals during the previous idle slot are also transmitted ? With backlog n, the number of packets that attempt transmission at the beginning of an epoch is approximately Poisson with rate g(n) = λβ + nq r Eytan Modiano Slide 5 Analysis of CSMA ? The probability of success (per epoch) is P s = g(n) e -g(n) ? The expected duration of an epoch is approximately T(n) ~ β + (1 - e -g(n) ) ? Thus the success rate per unit time is g(n)e ? g( n) λ < departurerate= β + 1? e ? g( n) Eytan Modiano Slide 6 Maximum Throughput for CSMA ? The optimal value of g(n) can again be obtained: 1 g(n) ≈ 2β λ < 1 + 2β ? Tradeoff between idle slots and time wasted on collisions ? High throughput when β is small ? Stability issues similar to Aloha (less critical) 1-|2 β Arrival rate Departure rate g(n) = λβ r + nq Eytan Modiano |2 β Slide 7 Unslotted CSMA ? Slotted CSMA is not practical – Difficult to maintain synchronization – Mini-slots are useful for understanding but not critical to the performance of CSMA ? Unslotted CSMA will have slightly lower throughput due to increased probability of collision ? Unslotted CSMA has a smaller effective value of β than slotted CSMA – Essentially β becomes average instead of maximum propagation delay Eytan Modiano Slide 8 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 Waits a random delay and tries again Eytan Modiano Slide 9 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 10 Approximate model for CSMA/CD ? Simplified approximation for added insight ? Consider a slotted system with “mini-slots” of duration 2τ 2τ ?> <----------- 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 11 ? ? 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 ? P(i users attempt) = ? ? i ? ? P i (1? P) N ?i 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 12 Analysis of CSMA/CD, continued P(success) =NP(1- p) N-1 = (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 ) i ?1 P s 1 ? E[X] = P s = e ? 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 13 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 Packet transmission time Mini-slots ? Efficiency = D Tp /S = D Tp / (D Tp + τ + 2τ(e-1)) ? Let β = τ/ D Tp => Efficiency ≈ 1/(1+4.4β) = λ < 1/(1+4.4β) 1 ? Compare to CSMA without CD where λ < 1 + 2β Eytan Modiano Slide 14 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 15 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 16 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 17 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 18 PACKET TRANSMISSION (release after transmission) ? When not transmitting their own packets nodes relay whatever they receive ? After receiving an idle token a node can start sending a new packet (discard incoming bits) ? After a node sends a packet and the idle token, it sends idle fill until: – The packet followed by idle, or – busy token, returns around the ring BT BTPacket return BT Packet Idle fillBT New packet IT Packet BT Packet IT Idle fill Packet Transmitted bits Received bits <-one time unit-> BT Eytan Modiano Slide 19 PACKET TRANSMISSION (release after reception) ? In many implementations (including IEEE802.5, but not including FDDI), a node waits to check its packet return before sending the idle token. This increases packet transmission time by one round trip delay. BTBT Packet IT Idle fill Packet returnBT Idle fill BT Packet BT Idle fill Idle fill IT Idle fill Idle fill BT New packet Eytan Modiano Slide 20 Delay analysis ? System can be analyzed using multi-user reservation results ? Exhaustive system - nodes empty their queue before passing token on to the next node ? Assume m nodes and each with Poisson arrivals of rate λ/m ? Let v = average propagation and token transmission delay ? System can be viewed as a reservation system with m users and average reservation interval (see reservation system results) W = λE[ X 2 ] + v( m ?ρ) , ρ = m(λ/ m)E[ X] = λE[ X ] 2(1? ρ) ? Notice that 100% throughput can be achieved for exhaustive system Eytan Modiano Slide 21 Throughput analysis (non-exhaustive) ? Gated system with limited service - each node is limited to sending one packet at a time – When system is heavily loaded nodes are always busy and have a packet to send ? 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 22 Throughput analysis (token 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 23 Delay Analysis ? Release after transmission – Partially gated limited service system (sec. 3.5.2) W = λE[ X 2 ] + v( m +λE[ X]) 2(1 ?λE[ X ] ? λv) ? Release after reception – Homework problem 4.27 – Additional round-trip time can be added to the packet transmission time W = λ( E[ X 2 ] + 2 mv + m 2 v 2 ) + v( m +λ (E[ X] + mv)) 2(1 ?λ( E[ X] + ( m + 1)v)) Eytan Modiano Slide 24 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 25 FDDI ? Fiber distributed data interface (FDDI) is a 100 Mbps Fiber Optic Token Ring local area network standard ? FDDI uses two counter-rotating rings – Single faults can be isolated by switching from one ring to the other on each side of (distance between nodes, number of nodes) 1 2 4 5 6 7 fault. ? Token release after transmission ? Limit on token hold time ? Upper-bound on time between token visits at a node – Support for guaranteed delays – Imposes a limit on the size of a ring ? FDDI designed to be a metro or campus area network technology 3 Eytan Modiano Slide 26 TOKEN BUSES WS WS WS WS WS WS ? Special control packet serves as a token ? Nodes must have token to transmit ? Token is passed from node to node in some order – Conceptually, a token bus is the same as a token ring – When one node finishes transmission, it sends an idle token to the next node (by addressing the control packet properly) – Similar to a polling system ? Issues – Efficiency lower than token rings due to longer transmission delay for the packets and longer propagation delays – Need protocol for joining and leaving the bus Eytan Modiano Slide 27 IMPLICIT TOKENS ? The idle tokens on a token bus can be replaced with silence ? The next node starts to transmit a packet after hearing the bus become silent ? If the next node has no packet, successive nodes start with successively greater delay ? If the bus propagation delay is much smaller than the time to transmit a token, this can reduce delay ? This scheme is used for wireless LANs (IEEE 802.11) and it goes by the name of CSMA/CA (collision avoidance) Eytan Modiano Slide 28 DISTRIBUTED QUEUE DUAL BUS (DQDB) ? Metropolitan area network using two oppositely directed unidirectional 150 Mbps buses ? All frames are the same length (53 bytes); empty frames are generated at the head ends of the buses and are filled by the nodes "on the fly" ? A node uses the right moving bus to send frames to nodes on the right and the left moving bus for nodes on its left ? DQDB was standardized as IEEE 802.6 and was intended to be compatible with ATM Eytan Modiano Slide 29 DQDB Reservations ? Greedy algorithm: Each node uses a free slot when it has something to send – Thus an efficiency of 100% is possible ? The trouble with this trivial approach is unfairness - nodes at the tail of the bus can be “starved” ? DQDB uses a reservations systems whereby nodes send requests upstream so that empty slots can be reserved – If a node has a frame to send on the right bus, it sets the request bit in a frame on the left bus – Nodes maintain an “implicit” queue of requests that can be served on a FCFS basis (hence the name distributed queue) Eytan Modiano Slide 30 Large propagation delay (satellite networks) A = mv 1 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 31 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 32 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 2 frame 1 2 frame 2 idle frame 3 6 frame 4 6 frame 5 15 3 20 15 7 9 7 9 7 9 18 7 5 9 18 idle idle idle 3 3 3 13 Eytan Modiano Slide 33 Packet multiple access summary ? Latency: Ratio of propagation delay to packet transmission time – GEO example: Dp = 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, 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 34 Migration to switched LANs ? Traditional Ethernet – Nodes connected with coax Long “runs” of wire everywhere – CSMA/CD protocol WS WS WS WS WS WS ? “Hub” Ethernet – Nodes connected to hub Hub acts as a broadcast repeater Shorted cable “runs”, Useful for 100 Mbps – CSMA/CD protocol – Easy to add/remove users – Easy to localize faults – Cheap cabling (twisted pair, 10baseT) WS WS WS WS WS WS ? Switched Ethernet – No CSMA/CD Easy to increase data rate (e.g., Gbit Ethernet) – Nodes transmit when they want WS WS WS WS WS WS Packet Switch Connect – Switch queues the packets and transmits to To other destination Switchs – Typical switch capacity of 20-40 ports – Each node can now transmit at the full rate of 10/100/Gbps – Modularity: Switches can be connected to each other using high rate ports Eytan Modiano Slide 35