1
$\begingroup$

Consider 2 stations that share the same bus. Both stations are perfect synchronized each other and when they have packets to transmit, they are starting the transmission in the beginning of a same slot. Transmission is as follows: when base $i$ has a packet to transmit attempts with probability $p_i, i=1,2$. Different stations make the random selection independently and corresponding probabilities are $p_1=0.5, p_2=0.25$. Initially the station 1 has 2 packets for station 2, while the other has no package.

What is the average number of slots in order all packets reach their destinations? Then if station 1 has 1 packet for station 2 and station 2 has 1 packet for station 1, what is the average number of slots? We are using slotted-Aloha.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

The protocol you are describing is most probably CSMA or slotted ALOHA.

As @wece mentioned, you need also to specify what you do in case of conflict (this is also the main difference between the above mentioned protocols). I would assume that a station sends regardless of the link-status and that a station will retransmit in the next slot with same probability $p_{i}$ in case of collision. This is basically what happens in slotted ALOHA, just that you have individual transmission probabilities for you stations.

You would not refer to the specified protocol as TDM (time division multiplexing), because the channel access is non-deterministic and non-repetitive, although you do have fixed time slots.

To your calculative questions:

1) Station 1 has 2 packets to send:
The probability that 1 successfully transmits to 2 is:

$$P(transmit_{1,2})=P(send_{1})*(1-P(send_{2}))$$

Since we have no packets at station 2, $P(send_{2})$ is zero. This is repeated over potentially many slots, always with probability $p_{1}=0.5$ that 1 will send in a slot. Note that this is the same problem as a simple coin toss. The expected number of sends in n tries (if we had infinite packets at 1) is $E=n*p$. Let's look at only one packet: We only want to know how many tries it takes on average. We can therefore write: $n=E/p$. This yields 2 tries on average for station 1. We can thereafter reason exactly the same way for the second package, because there is no statistical dependence between the events. We thereby obtain #tries = 4. (The same problem for station two would yield 4 + 4 tries.)

2) Now two stations want to send. We therefore have ($\neg$ means not):

$$ P(send_{1}\&send_{2}) = \frac{1}{2}*\frac{1}{4}=\frac{1}{8} $$ $$ P(send_{1}\&\neg send_{2}) = \frac{1}{2}*\frac{3}{4}=\frac{3}{8} $$ $$ P(\neg send_{1}\&send_{2}) = \frac{1}{2}*\frac{1}{4}=\frac{1}{8} $$ $$ P(\neg send_{1}\&\neg send_{2}) = \frac{1}{2}*\frac{3}{4}=\frac{3}{8} $$

Only the middle two give a first correct transmission. As in the previously calculation we see that we need 2 tries (or time slots) on average for this to happen. Once this happened, we are back to the first problem, sending one packet with the other station being quiet.

However, at this point it could have been the first or the second station which sent the first packet. We therefore need to account for it: We have 3/4 cases where it was station 1 and 1/4 cases where it was station 2 which transmitted correctly in the first step. This means we can simply add up the number of tries as: $$\#tries_{first-packet} + \#tries_{second-packet-from-1}*p_{second-packet-at-1} + \#tries_{second-packet-from-2}*p_{second-packet-at-2}$$ $$= 2 + 2 * \frac{1}{4} + 4 * \frac{3}{4} = 5.5$$

Improve this answer
$\endgroup$
4
  • $\begingroup$ I expanded the answer. Basically just take a step back, the calculation is in fact simple once you see it. :) $\endgroup$
    – Karl Hardr
    Commented Jul 31, 2013 at 8:49
  • $\begingroup$ @AdaselPomik very sorry about the E=1 in part I). That is for one packet only, and as you saw correctly, the total will be n=4 tries with E=2. $\endgroup$
    – Karl Hardr
    Commented Jul 31, 2013 at 18:37
  • $\begingroup$ @AdaselPomik I have again further expanded, hope it helps. It sometimes helps me to forget about the 'mathematically correct' formulation, and simply think about what really happens... ;) $\endgroup$
    – Karl Hardr
    Commented Jul 31, 2013 at 18:58
  • $\begingroup$ Well, at first I said that if we don't care who sends the packet, we have 3/8 + 1/8 = 1/2 successful transmission probability, hence 2 tries. $$$$ Then we are left with only 1 packet in the system but dont know where it is. So we consider both cases, packet at station one, and packet at station two. We know the #tries these stations would need from the first question. The probability for the second packet at station 2 is 3/4 because in 3/4 of the successful transmissions in the first round, it was station 1 that sent. $$$$ A bit long, lets see if it helps :) $\endgroup$
    – Karl Hardr
    Commented Jul 31, 2013 at 20:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.