Transcript lans-1-wb
CS3502:
Data and Computer Networks
Local Area Networks - 1
introduction and early broadcast
protocols
CS3502 , LANs. Objectives
1. describe LAN topologies/transmission media
2. describe MAC protocols -> in detail
3. compare/contrast different LANs
4. verify basic LAN protocols
5. describe and compare LAN throughputs
6. describe and analyze bridges/LAN switches
7. describe basic router function, differentiate
from bridge.
local area networks : general info
limited geographical area
relatively
high transmission rates
simple topologies and routing
mostly
baseband -- single channel
usually owned by 1 organization
characterized by topology, medium, and MAC
protocol
LANs : classes, topologies
broadcast
(contention); bus or wireless
Aloha,
CSMA, CSMA/CD (802.3) *,
wireless LANs (802.11)
broadcast
bit
(controlled)
map protocol, token bus
ring
802.5
token ring *, FDDI (token), slotted rings
star
ATM
LAN
local area networks : broadcast
all
nodes connected by ONE channel
if more than 1 node transmits simultaneously,
signals interfere (collision): the message is lost
thus, the transmission medium is always in 1 out
of 3 possible states:
(1)
(2)
(3)
example: classroom? .... 2 channels
LANs : ALOHA (pure)
radio
frequencies OR any broadcast medium
U
of Hawaii, early 1970s. Prof.. N. Abramson,
funded by ARPA.
simplest
a
possible protocol
station with a message simply transmits it to
completion. If no collision, message gets through,
otherwise wait random time and retransmit.
works
LANs : ALOHA (pure)
for when transmissions are rare; but
quickly degenerates as load increases
performance
analysis, based on assumed Poisson
distribution, shows max utilization of 18%.
(following slides) .
User
Load- the amount of traffic attempting to get
through the channel
Throughput
channel
Utilization
- amount of traffic getting through the
- is the fraction of time that the channel
is transmitting data (throughput/max
throughput)
LANs : Aloha performance analysis
based
on several assumptions:
1. Transmission attempts are generated by an
infinite number of users.
2. transmission attempts follows a Poisson
distribution.
3. fixed packet size
Def: Let X be a random variable, representing a
nonnegative integer. X is a poisson random
variable if
p(i) = P[X=i] = (e - i )/i!
LANs : Aloha performance analysis
note:
Poisson distribution (discrete RVs) and
exponential distribution (continuous RVs) are
closely related.
the mean, or “average” of the poisson dist. is
E [X]
lso note -P[X=0] = p(0) = e - , and P[X=1] = p(1) = e -
( come from plugging 0, 1 into the formula)
LANs : Aloha performance analysis
Let S = number of successful packet transmissions
per packet time (equals channel utilization)
G = average number of attempted transmissions
per packet time(user load+retransmissions).Then,
S = P[successful transmission]
= P[1 attempt] P[no other attempts]
= P[X=1] P[X=0]
= G x e -2G, pure Aloha
Q : what is the maximum utilization? (take the
derivative, set to 0, plug back in)
LANs : performance analysis
derivative :
( G x e -2G)’ = (1)(e -2G ) + G(e -2G )(-2)
setting to 0, e -2G - 2G e -2G = 0
=> 1 - 2G = 0 => G = 0.5
I.e., utilization is max at G = 0.5. Plugging this into
the original formula,
S = G x e -2G
yields a max value of 0.18.
LANs : ALOHA (slotted)
how
can ALOHA be improved?
need
to reduce collisions
slotted
slots
ALOHA : restrict transmissions to time
divide
time into “slots”
station waits until next time slot to transmit
slots must be synchronized, somehow
how
much will utilization improve?
LANs: ALOHA
when
should station retransmit after a collision?
show
why throughput should double with
slotted Aloha over pure Aloha
what
is the worst-case time a station will have to
wait until getting a successful transmission?
how
can Aloha be improved?
hint:
what if we could use 2 power levels?
LANs : ALOHA, 2 power levels
idea:
when station transmits, flip a coin. Heads,
use low power level. Tails, used high power level.
high
power clobbers lower power; if same
power, collision as before.
can
be added to either pure or slotted. Improves
max throughput to 26% (pure) or 52% (slotted)
under same Poisson assumptions.
LANs : ALOHA summary
simple communications (simple is good)
relatively
good
not
cheap, simple to implement
for sparse, intermittent communication.
a good LAN protocol because of
poor
utilization
potentially
stations
utilize it
infinite delay
have listening capability, but don’t fully
LANs: CSMA
corrects
the obvious flaw in Aloha (blindly
transmitting without first checking the medium)
CSMA(carrier
sense multiple access) protocol:
(1)sense the carrier; {LISTEN}
if no signal detected
then transmit message to end; {TALK}
if collision occurred,
then wait random time, go to (1) else END.
else {carrier is busy} go to (1).
LANs: CSMA
basic
CSMA is “persistent,” or “1-persistent” -it transmits as soon as it detects the open carrier.
suppose
another station is transmitting; when
will the station start to transmit?
what
effect does propagation delay have on this
protocol?
note
that whenever transmission occurs, the
whole message is sent: no way to abort
LANs: CSMA
what
are 2 ways that collisions can occur in
CSMA? What is their likelihood?
Will
CSMA improve throughput over Aloha?
nonpersistent
CSMA: when carrier is busy, wait a
random time.
Will
this improve utilization?
LANs : CSMA, p-persistent
variation
of CSMA; generalization
for parameter p : real, in (0,1], --(1)sense the carrier;
if no signal detected
then transmit message to end with probability p ;
else {probability 1- p} wait random time, goto (1);
if collision occurred,
then wait random time, go to (1) else END;
else {carrier busy} go to (1).
LANs : CSMA
will
this improve utilization?
for
low values of p, maximum utilization is
highest; what about user friendliness?
Since even if the channel is free one defers
transmission
with p=> 0
the average wait time =>
LANs : Aloha/CSMA , summary
Compare
approximate utilization of the protocols
pure Aloha
slotted
Aloha
1-persistent CSMA
p-persistent CSMA
nonpersistent CSMA
Compare the throughput as a function of user
Load