Transcript CS3502-LANs
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.
LANs : ALOHA (pure)
works
for when transmissions are rare; but
quickly degenerates as load increases
performance
analysis, based on assumed Poisson
distribution, shows max throughput of 18%.
(following slides)
throughput
(aka utilization) is the fraction of time
that the network is transmitting data.
load,
or offered load, is the amount of traffic
attempting to get through the network
LANs : Aloha performance analysis
based
on several assumptions:
1. offered load is infinite number of users.
2. total offered load (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 represent the throughput (utilization), and G
the offered load. Then,
S = G x P[successful transmission]
= G x P[no other transmissions]
= G x P[X=0]
= G x e -2G, pure Aloha
Q : what is the maximum throughput? (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., throughput 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 throughput 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?
specify
CSMA formally as a Comm.Finite State
Machine, then analyze it.
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
exercise:
alter the CSMA specification (CFSM) to
handle p-persistence
throughput:
will this improve throughput?
for
low values of p, maximum throughput is
highest; what about user friendliness?
nonpersistent
CSMA: when carrier is busy, wait a
random time. Rewrite the specification for this
change.
LANs : CSMA
when
collisions occur, how much time is wasted?
what
is approximate likelihood of repeating the
collision, with
CSMA,
1-persistent
CSMA, 0.1 persistent
CSMA, nonpersistent
How
can time wasted be reduced?