Slotted Aloha

• synchronous system: time divided into slots
• slot siz equals fixed packet transmission time
• when Packet ready for transmission, wait until start of next slot
• packets overlap completely or not at all

Slotted Aloha performance

S = G*prob[no other transmissions overlap]

= G*prob[0 other attempted transmissions]

= G*prob[0 other arrivals in previous slot]

= Ge**(-G)

·        Aloha is inefficient (and rude!): doesn't listen before talking!

·        Carrier Sense Multiple Access: CSMA

In our analysis the access methods to control multichannel system and the data multichannel system is based on slotted ALOHA protocol. Both control and data channels use the same time reference which we call cycle. We define as cycle, the time interval that includes one time unit for control packet transmission followed by a data packet transmission period. Thus the cycle time duration is T=L+1 time units as Figure 2 shows. The stations are synchronized for the transmission on the control and data packet during a cycle. A station generating or retransmitting a data packet, waits the beginning of the next cycle, selects randomly one of the v wavelengths

_c1,..., and sends a control packet over the _cm control channel at the first time unit of the
cycle. The control packet, as Figure 2 displays, is consisting of the transmitter address, the receiver address and the wavelength, _dk, of the data channel. Immediately after transmission of the control packet the data packet is ransmitted over _dk wavelength data channel.

Figure 2. Structure of the control packet and the control multislot

TOP

If more than one data packets in a cycle use the same _dk, a collision occurs and all overlapping data packets are destroyed. In case of unsuccessful (re)transmissions on a control or a data channel of the system, the stations participating in it defer their retransmissions for a random time until successful retransmission. The random time delay introduced between two consecutive retransmissions is uniformly distributed from 1 to K cycle times. In the receiving mode a station's fixed tuned receivers monitor the control multichannel system to listen its address. When the destination station recognizes its address on a control channel of the system, it tunes its tuneable receiver over wavelength _dk of data channel for data packet reception. If two or more successfully (re)transmitted data packets have the same destination during a cycle, a receiver collision occurs which is ignored in our analysis. We also assume that the average propagation delay is negligible.

Analysis

Let G = the mean offered traffic over (v-channel) control multichannel system in a control slot time, that obeys to Poisson statistics.

G_v = G/v, the traffic to j-th control channel j {1,2,...,v} given that each control channel is chosen with equal and constant probability pj = 1/v

P_c = the probability of one Poisson arrival in a control channel during a time unit. Then

P_c = G/v e^-G/v (1)

A_v = random variable representing the number of successfully (re)transmitted control packets in a control slot time. Thus the probability of finding A_v=k control channels everyone with one Poisson arrival during a time unit, obeys to binomial probability low.

Pr[ A_v=k ] = [ v! / (v-k)! k! ] ( P_c )^k [ 1 - P_c ]^{( v-k )} (2)

S_c = the average successful (re)transmission rate of control packets during a control slot time in steady state.
S_c = E( A_v = k) = k Pr[ A_v = k] = Ge ^-G/v (3)

P_s = the probability of successful (re)transmission of a control packet over the control multichannel system. From (3) we take

P_s = S_c / G = exp[-G / v ] (4)

Consider that A_v=k data packets are (re)transmitted over data multichannel system in the data slot time of the ith cycle. The

random distribution of the k data packets in N data channels gives N^k arrangements each with probability N^-k.

P_d(k) = the conditional probability that only one from k data packets are destined to a given data channel n, n{1,2,...,N} in

the data slot time of the i_th cycle.

Thus the remaining k-1 packets are destined to the remaining (N-1) data channels in (N-1)^k-1 different ways. 

The P_d(k) can be expressed as follows.

P_d(k) = ( k/N ) [ 1 - 1/N ]^k-1 (5)

Using the approximation (1 - x )^y ÷ exp(-xy) for small x in (5), we take

P_d(k) ( k/N ) exp[-(k-1)/N] (6)

P_d = the probability that a data packet is (re)transmitted without collisions in a data slot of a cycle time in steady state,

regardless of successful (re)transmission of the corresponding control packet on control multichannel system. Then according (6) we take

P_d =( G / N ) exp[-G / N] (7)

P_suc = the probability of success of a data packet over a data channel, given that the

corresponding control packet has successful (re)transmitted.

P_suc = P_s P_d = ( G / N ) exp[-G / v ] exp[-G / N] (8)

A_N = random variable representing the number of successfully (re)transmitted data packets in a data slot time of a cycle. The

probability of finding A_N = r successfully (re)transmitted data packets can be evaluated as follows.

Pr[ A_N = r ] = [ N! / (N-r)! r! ] ( P_suc )^r [ 1 - P_suc ]^(N-r) (9)

S_N = the average number of successful (re)transmissions of data packets in a data slot time of a cycle in steady state.

S_N = E( A_N=r ) = r Pr[ A_N=r ] = G exp[-G / v ] exp[-G / N] (10)

From the above equation results that the S_N is a function of G, v and N. Thus for N=1 and v=1 we have

S_N = G exp(-2G). This value coincides to the unslotted ALOHA throughput. The explanation is that a successful transmission

from the system requires successful transmission from both control and data channel.

S = the throughput of the system is defined as the average number of successful (re)transmissions of data packets during a cycle time in steady state.

S = [ L / (L+1) ] S_N = [ L / (L+1) ] G e^-G/v e^-G/N (11)

S_nor = S / N, the throughput per data channel in steady state.

D = the interval between the time a data packet is generated and the moment that has been successfully (re)transmitted from a data channel. Data packet delay D, is composed from three parts as follows:

D = D_w + D_r + T (12)

D_w = the interval between the time a data packet is generated till the beginning of the next cycle.

D_r = the delay from the transmission of a control packet, to the successful reception of the corresponding data packet from a

data channel.

F_r = the probability of successful (re)transmission of a data packet over a data channel. From (10) we take

F_r = S_N / G = e^-G/v e^-G/N (13)

Q_r(n) = the probability of successful retransmission of a data packet after n trials.

Assuming that the probability of success is the same on any try, n has a geometric distribution, i.e.

Q_r(n) = F_r (1 - F_r)^n-1 (14)

R = the average number of trials for successful transmission of a data packet. So

R = E[ n ] = n Q_r(n) = 1 / F_r = e^G/v e^G/N (15)

D_b = (K+1) / 2, t he average delay between successive retransmissions

The average packet delay D, is

E [ D ] = E [ D_w ] + E [ D_r ] + T = T / 2 + (R-1)(1 + D_b)T + T = (L+1) [ 1.5 + [e^G/v e^G/N- 1 ][ (K+3)/2)] (16)

TOP

Numerical Results

In Figure 3, we assume a multichannel system with fix number of data channels, N=10, and several control channels v=5,10,15. The Figure illustrates the average delay E[D] versus the throughput per data channel S_nor. It is evident from the figure that the system performance measures improves as v increases for fix values of N. The performance behaviour can be explained as follows:

Figure 3The average delay E[D] versus the throughput per data channel S_nor for v=5,10,15( control channel) systems and N=10 data channels with L=100 and K=10

If we set the first derivative of equation (11) with respect of G equal to zero, we find the optimal value of G_opt that maximize the throughput of the system. After some calculations we take

G_opt = v N / ( v + N ) (17)

S_max = [ L / (L+1) ] 1/e v N / ( v + N ) (18)

The corresponding S_nor is

S_nor(max) = [ L / (L+1) ] 1/e [ 1 / ( 1 + N/v ) ] (19)

From the above results we observe that for fix values of N as v increases S_nor(max) increases and for large values of v , S_nor(max) approaches 1/e.

Figure 4 The average delay E[D] versus the throughput per data channel S_nor for N=5,10,15( data channel) systems and v=10 control channels with L=100 and K=10

Figure 4 present the average delay E[D] versus the throughput per data channel S_nor fix number of control channels, v=10,

and several data channels N=5,10,15. It is obvious from the figure that as N increases the performance behaviour is getting

worse. Also equation (19) denotes for fix value of v as N increases S_nor(max) deteriorates. Also Figures 3,4 show that the

system is unstable because there are two different values of average delay associated with a given throughput.

Figure 5 shows the average delay E[D] versus the throughput per data channel S_nor for v=10,N=5 (channel) system with K=10,30,50. For fix value of K, and in the lower part of the curves the delay increases very slowly with the throughput showing the high throughput and low delay desirable regions. As traffic increases approaching its optimum value G_opt=vN/(v+N) which corresponds to S_max=[L/(L+1)]1/evN/(v+N), and the average number of retransmissions, R, becomes significant, then the average delay, D_b=(K+1)/2, between successive retransmissions begins to make a noticeable difference in the average delay E[D] as Figure 5 shows.

Figure 5 The average delay E[D] versus the throughput per data channel S_nor for v=10,N=5 (channel) system with K=10,30,50

TOP