美国麻省理工大学：《Communication Systems Engineering（通讯系统工程）》Packet Multiple access ll Local Area Networks(LANs)

Packet Multiple access ll Local Area Networks(LANs) Eytan Modiano Massachusetts Institute of Technology Department of Aeronautics and Astronautics Eytan Modiano

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 wsws Ws W 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 Eytan Modiano Waits a random delay and tries again

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 T= prop WS /s 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 t is the maximum propagation delay on the cable then if a collision occurs, it can take up to 2t seconds for all nodes involved in the collision to detect and stop transmission Eytan Modiano

τ τ τ = 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

A pproximate model for cSMA/CD Simplified approximation for added insight ● Consider a s| otted system with“mini- slots” of duration2τ 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

τ Approximate model for CSMA/CD • Simplified approximation for added insight • Consider a slotted system with “mini-slots” of duration 2τ −> 2τ 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 P(i users attempt)=.P(1-P) Plexactly 1 attempt=P(success)=NP(1-P) To maximize P(success), NP(1-P)1]=N(1P)-N(N-1)P(1-P 3 Average attempt rate of one per slot Notice the similarity to slotted Aloha Eytan Modiano

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 P(success)=NP(1-p)=(1 N s= limit(N>oo)P(success) et X Average number of slots per succesful transmission P(X=)=(1P)1 EⅨX 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

Analysis of CSMA/CD, continued 1 P(success) =NP(1 - p)N-1 = (1− N) N −1 1 Ps = limit (N → ∞) P(success) = e Let X = Average number of slots per succesful transmission − P(X = i) = (1 - Ps )i 1 Ps 1 ⇒ E[X] = = e Ps • 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+t t Ave time until start of next Mini-slot dle/collision Mini-slots Packet transmission time Efficiency =D /S= Dn / D +t+ 2i(e-1) °Let阝=tDn=> Efficiency=1(1+445)=≤11t24) Eytan Modiano

τ τ τ τ β τ ≈ β λ β Analysis of CSMA/CD, continued • Let S = Average amount of time between successful packet transmissions S = (e-1)2τ + DTp + τ Ave time until start of next Mini-slot Idle/collision Mini-slots Packet transmission time • Efficiency = DTp/S = DTp / (DTp + τ + 2τ(e-1)) • Let β = τ/ DTp => 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

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 o=10-4sec Cable distance =1 mile, t= 5x10- sec B=5x102andE=80% Example(GEO Satellite)-propagation delay 1/4 second B=2,500andE~0% CSMA/CD only suitable for short propagation scenarios! How is Ethernet extended to 100 Mbps? How is Ethernet extended to 1 Gbps?

τ β β CSMA/CD examples • Example (Ethernet) – Transmission rate = 10 Mbps – Packet length = 1000 bits, DTp = 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 1980s Token: a bit sequence Token circulates around the ring Busy token: 01111111 Free token :01111110 Token Ring 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 Slide 10

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 10