Transcript pptx - Caltech

cs/ee 143 Communication Networks
Chapter 3 Ethernet
Text: Walrand & Parakh, 2010
Steven Low
CMS, EE, Caltech
Warning
These notes are not self-contained,
probably not understandable,
unless you also were in the lecture
They are supplement to not replacement for class attendance
Agenda
Ethernet history/devices
Switch Ethernet forwarding table
Spanning tree protocol
Little’s theorem (informal proof)
Ethernet
Each (layer 2) network
• full connectivity: every node can reach every other node
• broadcast capable: every node (inc. router) can broadcast to all other nodes
• e.g. Ethernet, WiFi, cable network, etc.
Aloha network (1970)
Randomized multiple access
• Send on frequency f1; receive ack on frquency f2.
• If no ack after timeout, wait a random time and re-transmit
Aloha network (1970)
Randomized multiple access
• If an ack is not outstanding, transmit immediately
• If no ack, re-transmit after a random delay
Aloha network (1970)
Randomized multiple access
Max utilization (prob of success) ~ 1/e ~ 37%
Slotted Aloha utilization
Model
• Slotted time, fixed packet size, n stations
• 1 slot = 1 pkt transmission time
• In each slot, each station transmits
independently with probability p
Prob (slot t has a successful transmission)
R(p) = np (1- p)
n-1
Slotted Aloha utilization
max R( p) = np (1- p)
n-1
p
Þ 0 = R'( p ) = n (1- p
*
Þ
(1- p ) = (n -1)p
*
)
* n-1
*
- n(n -1)p (1- p
*
1
Þ p =
n
*
max utilization = R(p )
*
n-1
æ 1ö
= ç1- ÷
è nø
1
®
e
as n ® ¥
)
* n-2
Slotted Aloha utilization
max R( p) = np (1- p)
n-1
p
Þ 0 = R'( p ) = n (1- p
*
Þ
(1- p ) = (n -1)p
*
)
* n-1
*
- n(n -1)p (1- p
*
1
Þ p =
n
*
max utilization = R(p )
*
n-1
æ 1ö
= ç1- ÷
è nø
1
®
e
as n ® ¥
)
* n-2
Slotted Aloha utilization
max R( p) = np (1- p)
n-1
p
Þ 0 = R'( p ) = n (1- p
*
Þ
(1- p ) = (n -1)p
*
)
* n-1
*
- n(n -1)p (1- p
*
1
Þ p =
n
*
max utilization = R(p )
*
n-1
æ 1ö
= ç1- ÷
è nø
1
®
e
as n ® ¥
)
* n-2
Unslotted Aloha utilization
Model
• Fixed packet size, n stations
• Slotted time of duration t << 1.
• pkt transmission time lasts 1/t time slots
• In each t-slot, each station transmits
independently with probability p
• Small t => approximates unslotted operation
Prob (slot t has a successful transmission)
R(p) = np (1- p)
n-1
Unslotted ALOHA utilization
Prob (a pkt transmission started in an arbitrary
t-slot by station 1 is successful)
n-1
n-1
( n-1) K
S(p) = p (1- p)
(1- p)
2
K:= -1 time slots
t
= p (1- p)
Unslotted ALOHA utilization
Prob (a pkt transmission started in an arbitrary
t-slot by station 1 is successful)
n-1
n-1
( n-1) K
S(p) = p (1- p)
(1- p)
2
K:= -1 time slots
t
= p (1- p)
Unslotted ALOHA utilization
max S( p) = p (1- p)
( n-1) K
p
Þ
0 = S '( p ) = (1- p
*
*
)
( n-1) K
- (n -1)Kp (1- p
*
Þ
(1- p ) = (n -1)Kp
*
1
Þ p =
(n -1)K +1
*
*
*
)
( n-1) K-1
Unslotted ALOHA utilization
max S( p) = p (1- p)
( n-1) K
p
Þ
0 = S '( p ) = (1- p
*
*
)
( n-1) K
- (n -1)Kp (1- p
*
Þ
(1- p ) = (n -1)Kp
*
1
Þ p =
(n -1)K +1
*
*
)
( n-1) K-1
*
reduces to slotted case
If K=1
Unslotted ALOHA utilization
n
*
utilization := S( p )
t
( n-1) K
æ
ö
n
1
1
=
ç1÷
t (n -1)K +1 è (n -1)K +1 ø
( n-1) K
æ
ö
n
1
1
=
1ç
÷
n -1 t K + t è (n -1)K +1 ø
n -1
1
tk = 2 -t
®
as n ® ¥ and t ® 0
2e
Unslotted ALOHA utilization
n
*
utilization := S( p )
t
( n-1) K
æ
ö
n
1
1
=
ç1÷
t (n -1)K +1 è (n -1)K +1 ø
( n-1) K
æ
ö
n
1
1
=
1ç
÷
n -1 t K + t è (n -1)K +1 ø
n -1
1
t K = 2 -t
®
as n ® ¥ and t ® 0
2e
Unslotted ALOHA utilization
n
*
utilization := S( p )
t
( n-1) K
æ
ö
n
1
1
=
ç1÷
t (n -1)K +1 è (n -1)K +1 ø
( n-1) K
æ
ö
n
1
1
=
1ç
÷
n -1 t K + t è (n -1)K +1 ø
n -1
1
t K = 2 -t
®
as n ® ¥ and t ® 0
2e
Ethernet cable (1973-76)
CSMA/CD (carrier sensing multiple access/collision detection)
1. Wait till channel is idle; wait for a random time.
2. Transmit when the channel is idle following the random wait.
3. Abort if collision is detected, and goto 1.
Ethernet cable (1973-76)
Truncated binary exponential backoff
1. Pick X uniformly at random from {0, 1, ..., 2^n-1}, n = min (10, m), m =
#collisions. Give up & declare error when m = 16.
2. Wait X x 512 bit times (4,096 bits for 1G)
3. If collide, increment m and repeat.
Ethernet cable (1973-76)
Capture or winner-takes-all effect
• A station that collides is more likely to pick a larger random backoff
time.
• A station that successfully transmits is more likely to pick a smaller
backoff time and hence more likely to successfully transmit again
Ethernet hub (1980s)
CSMA/CD as in Ethernet cable
Ethernet hub (1980s)
• A station waits a random multiples of T = 2 PROP before transmitting
• When n stations transmit independently with prob p, then prob of success is
<= 1/e when n is large
• Hence avg time till first success = e T
• Utilization = TRANS / (TRANS + (e-1)T) = 1 / (1 + 3.4A), A = PROP/TRAN
Ethernet switch
Ethernet switch eliminates collision, provided
switch buffer is big enough.
Ethernet switch: forwarding table
(Ethernet) MAC address
1. 48 bit
2. Globally unique to MAC device, location independent (c.f. IP)
3. Broadcast address: 48 ones
Ethernet switch: forwarding table
x  y:
[ y | x | data ]
Agenda
Ethernet history/devices
Switch Ethernet forwarding table
Spanning tree protocol
Little’s theorem (informal proof)
Ethernet switch routing: STP
•
•
•
•
Goal
Operation
Example
Performance
x  y:
[ y | x | data ]
Spanning tree protocol
Goal: for all switches in a LAN to
compute a shortest-path tree
 used to route layer-2 packets
 one tree for entire LAN
 rooted at the switch with the smallest ID
(MAC address)
 decentralized, asynchronous, robust
computation
Spanning tree protocol
Three criteria
1. The root switch always forwards messages
on all its ports
2. Each switch computes its shortest path (in
#bridges) to root
3. All switches connected to a LAN elect a
designated switch for the LAN to send
packets towards root switch
 A switch that is not elected for any of the LANs it
is connected to will not receive nor forward any
data packet
Spanning tree protocol
 Switches send packets asynchronously with
[ my ID | current root ID | distance to root ]
 A switch relays packets whose “current root ID”
is the smallest it has seen so far (& smaller
than its own “current root ID”), and adds 1 to
“distance to root”
 If the “distances to root” on STP packets
received by a switch on all its ports are the
same or smaller than what it believes its
distance is, then the switch stops forwarding
 … until protocol converges
Completely decentralized, asynchronous, robust
STP: example
I’m 3
I think root is 3
my distance to root is 0
STP: example
I’m 3
I think root is 3
my distance to root is 0
STP: example
a new initiation
before previous
converges
STP: example
a new initiation
before previous
converges
STP: example
a new initiation
before previous
converges
STP: example
During transient, B5 may connect to root B1
either via B3 or B4 – which should B5 use?
Ans: use switch with a smaller ID (B3)
Spanning tree for all switches
x  y:
[ y | x | data ]
STP: designated switches
• B4 believes its distance to root B1 is 2
• The STP packets from both its ports have distances equal or less. So
it does not forward and is not a designated switch for neither LAN
• Neither B4 nor B5 will be involved in forwarding data packets
Spanning tree protocol
Performance
 Unique path between every sourcedestination path
 Can potentially be bad since 2 switches
may communicate only via root
 e.g. in a ring of switches, the switch with the
largest ID communicates with root via the
longest path
 Penalty is usually not too bad since it is
in a LAN
Agenda
Ethernet history/devices
Switch Ethernet forwarding table
Spanning tree protocol
Little’s theorem (informal proof)
Little’s law
L = T
capacity:
m pkts/s (>l )
arrival rate:
l pkts/s
L pkts
Little’s law
at
L (t )
Ti
bt
t
t
at : #packets arrived by t
bt : #packets departed by t
Ti : delay of packet i
Lt = a t - bt : #packets in system at t
Little’s law
at
L (t )
Ti
bt
t
t
ò L (t )dt
0
t
Little’s law
at
L (t )
Ti
bt
t
bt
åT
i
i=1
£
t
ò L (t )dt
0
t
Little’s law
at
L (t )
Ti
bt
t
bt
åT
i
i=1
t
£
t
ò L (t )dt
0
£
at
åT
i
i=1
Little’s law
at
L (t )
Ti
bt
t
bt
åT
i
£
i=1
bt
t
bt 1
Ti £
å
t bt i=1
t
ò L (t )dt
0
t
1
L (t )dt
ò
t 0
£
at
åT
i
i=1
at
at 1
£
Ti
å
t a t i=1
Little’s law
at
L (t )
Ti
bt
t
t
l
T
bt
£
bt 1
Ti £
å
t bt i=1
L
£ l
­ as t ® ¥
t
1
L (t )dt
ò
t 0
T
at
at 1
£
Ti
å
t a t i=1
Queueing system
random arrival
process with rate

with average
 pkts/s
 Little’s law
random service time
1

s/pkt
L = T
 Verifies directly for M/M/1, but holds
much more generally
 Extremely useful because of its
generality
M/M/1 queue
Poisson arrival
process with rate
Exponential service time

with average
 pkts/s
1
avg total delay T =
 -
/
avg waiting time Tq = T - =
  -
1
avg # pkts in system L =

 -
1

s/pkt
Queueing system
random arrival
process with rate
random service time

with average
 pkts/s
L
L = T
T
Tq = T -
Lq
Lq = Tq
Tq
1

1

s/pkt