EE5412 Random_Access_0.doc

Random_Access_0.doc Local Area Network by Gerd E. Keiser
LAN ACCESS - user Share Tx link
simultaneous access – collision
control mechanism to resolve conflict – protocol

General technique - Syn/Asyn TDM
contention (ie random ) access
deterministic (ie. controlled ) access

Random Access scheme- ALOHA (ground based radio packet broadcast network)
CSMA, CSMA/CD, registered insertion

Controlled Access Scheme - centralized - eg. polling - master node determine the right
distributed - eg. token passing, slotted ring

Performance Measurment
1. Throughput characteristic
2. Transfer delay characteristic

Parameter
 = mean packet arrival rate
 = mean service rate
1/ = average length or service time\,

M/G/1 queue - Poisson distribution packet arrival, general service distribution and one server

S = throughput in bits/sec
R = channel transmission rate in bit/sec
K = packet length in bits

S = [ dimensionless ; normalized to channel transmission rate or bandwidth]

G = offered load
T = total offered traffic
= packets delivered on first attempt + repetition

G =(TK)/R

Random Access method - ALOHA
No control mechanism for contention - collide and retransmit
max. achievable channel utilization - = 18%
Slotted ALOHA - channel divided into time slots
Tx only at the beginning of a time slot eliminate partial overlapping of message
[ie. collide at the beginning ]
channel utilization = 37%
CSMA - carrier sense or listen before talk
further improve the utilization


Pure ALOHA
Transmit immediately whenever there is data to send.
Waits for an acknowledgement from the receiver for a time period equal to one propagation time.
If no acknowledgement - retransmit
tp = packet transmission time or propagation time
= time slot ( ~ service time 1/)

assume packet length fixed
transmission time = 1 time slot

Hence to transmit 1 packet the channel will be busy for 2 x tp sec. ( ie. propagation + transmission) If another user attempt to transmit during the 2 x tp sec, the packets will collide and both packets will be corrupted.

G = no. of packet transmission attempt in one time slot tp.
S = mean no. of successful transmission per time slot tp,

From 5.2 probability of k transmission per time slot

pk = [Gke-G]/[k!]


throughput = p1 (prob. of 1 transmission in one slot )
p0 (prob. of no transmission in the next slot)

S = p1 p0
= G e-G e-G = G e-2G

max. S  0.184 at G = 0.5

ie max channel utilization  18% for pure ALOHA


Slotted Aloha
The channel is divided into time slots which are exactly equal to a packet transmissin time. All users are synchronized to the time slot for packet transmission so that the vulnerable period for collision is limited to one time slot. ( all user attempt to transmit only at the start of the time slot )

The throughput of the channel becomes

S = p1 = G e-G

max. S  0.386 at G = 1

max. channel utilization is twice that of pure Aloha.

fig6.2 comparsion of throughput for pure and slotted ALOHA (infinite no. of users)

If you want to send a test packet, then the
probability of no collision = p0 = e-G
probability of collision = 1- p0 = 1- e-G
Probability of successful transmission requiring k attempts = Pk = e-G(1- e-G)k-1

The expected number of transmission required Pk
= e-G(1- e-G)k-1
= eG
exponential function implies small increase in G will drastically reduce its performance

Stability of Slotted ALOHA ** for detail, refer to text 6.3.3

assume N stations each can hold 1 packet only
assume each station generate new packets according to Poisson distribution with mean transfer probability p<<1 packet per slot when the station is not blocked

assume collided packet retransmitted with probability  in every successive time slot until successful [normally wait for a random no. of slots]

Problem is to find the number of stations backlogged.
let state k = k out of N stations backlogged
each station retransmitt with probability 
delay or skip the slot with prob. (1- )

ie. total of k retransmission per slot - blocked terminals
(N-k)p new packets per slot - unblocked terminals

let n = new packets from unblocked stations
r = retransmitted packets from blocked stations

[ 0  n  N-k; 0  r  k ]


Probability of a successful transmission at state k

Pk = P(k=1).P(n=0) + P(n=1).P(k=0)

[ie. (one retransmit)(no new) + (one new)(no retransmit) ]
( collide if more than one )

Pk = [k(1-)k-1][(1-p)N-k] + [(1-)k][(N-k)p(1-p)N-k-1]
= Sout,k
= rate packet leave the system with k backlogged stations

Rate packet enter the system = S = (N-k)p ....…..………………………. (6.15)

For large N and small p Sout,k = k(1-)k-1 e-S + (1-)kSe-S…………...(6.16)

For equilibrium, input = output [ 6.15 = 6.16]
Fig 6.4 shows the equilibrium throughput curve

Fig 6.5 shows the variation of  ( ie. retransmit probability)
Decrease in  achieve a finite throughput even with heavy backlog. This also results in long retransmission intervals.

----------------------------
Max Throughput for IEEE 802.3

Collisions occur if more than one station sensed idle and transmit simultaneously
Collisions => retransmission => increased delay and reduced throughput
Normal condition for LANs : propagation delay << message length or τ << m

a = τ/m << 1
max throughput : ρmax = λmax m = 1/[1 + ( 1 +2e)a] = 1/[1 + 6.436a]

example :
With bit rate =10mbps, length = 2500m, propagation speed = 2 x 108 m/s

Propagation delay in Bit length = [10 x 106 x 2500 ]/ [2x 108] = 125 bits

If frame length = 72 octets (min) = 72 x 8 bits = 576 bits
a = τ/m = 125 / 576 = 0.217
max throughput , ρmax = 1/[1 + 6.436a] = 0.417

if frame length is 1526 octets (max)
 a = 0.010239
 max throughput, ρmax = 1/[1 + 6.436a] = 0.938

-------------------------------