Calculating probability of a node to transmit in Soltted ALOHA

Thread Starter

zulfi100

Joined Jun 7, 2012
656
Suppose four active nodes – nodes A, B, C and D – are competing for access to a channel using slotted ALOHA. Assume each node ha an infinite number of packets to send. Each node attempts to transmit in each slot with probability p. The first slot is numbered slot 1, the second slot is numbered slot 2, and so. What is the probability that node A succeeds for the first time in slot 5?

I found a solution which does something like that:

(1-p(A))^4 * P(A).

Can some body please explain me this solution?

Zulfi.
 

nsaspook

Joined Aug 27, 2009
13,079
I wish I could after decades of no usage of the information.

There is a detailed explanation of the probability in Computer-Networks A Tanenbaum. My old school book is the 1981 edition but there should be a section on ALOHA in all editions.
5-th edition pages.
 

WBahn

Joined Mar 31, 2012
29,976
Suppose four active nodes – nodes A, B, C and D – are competing for access to a channel using slotted ALOHA. Assume each node ha an infinite number of packets to send. Each node attempts to transmit in each slot with probability p. The first slot is numbered slot 1, the second slot is numbered slot 2, and so. What is the probability that node A succeeds for the first time in slot 5?

I found a solution which does something like that:

(1-p(A))^4 * P(A).

Can some body please explain me this solution?

Zulfi.
What the heck is p(A) and P(A)?

Don't use terms that you don't define -- and don't assume that some solution to some problem that you found somewhere is going to (1) be right, and (2) use the same terminology as the problem you were given.

Just think of what is required for Node A to succeed for the first time in Slot 5.

First, it had to NOT succeed in ALL of the prior nodes, AND then it has to succeed in this particular node.

Pay particular attention to the words that are emphasized.
 

Thread Starter

zulfi100

Joined Jun 7, 2012
656
Hi,
<Just think of what is required for Node A to succeed for the first time in Slot 5.>
It should have the highest probability.
If P(A) is the probability of success then (1-P(A)) is the probability of failure.

probability of not succeeding in last 4 slots = (1-P(A)) * (1-P(A)) * (1-P(A)) * (1-P(A)) = (1-P(A))^4.
probability of success = P(A) * probability of failure of other nodes
= P(A) * (1-P(B)) * (1-P(C)) * (1-P(D))

Probability of success for the first time in slot 5 = (1-P(A))^4 * P(A) * (1-P(B)) * (1-P(C)) * (1-P(D))
Please guide me.
 

WBahn

Joined Mar 31, 2012
29,976
Look carefully at what 'p' is defined as in the problem you are trying to solve. It is NOT the probability that A succeeds or that A fails, it is the probability that a given node will ATTEMPT to transmit in a given slot.

In any given slot, Node A succeeds if and only Node A attempts to use that slot AND every other node does NOT attempt to use that slot.
 

Thread Starter

zulfi100

Joined Jun 7, 2012
656
Hi,
I have provided you the equations. Kindly specifically point out the corrections w.r.t. the equations. Otherwise, I won't be able to reach to the correct answer.

Zulfi.
 

WBahn

Joined Mar 31, 2012
29,976
Hi,
<Just think of what is required for Node A to succeed for the first time in Slot 5.>
It should have the highest probability.
What is "it"? And "it" should have the highest probability of what?

How does having the highest probability of something somehow mean that it actually succeeds?

Either it succeeds for the first time in Slot 5 or it does not. It succeeds if certain criteria are met. The question asks for the probability that those criteria are met.

If P(A) is the probability of success then (1-P(A)) is the probability of failure.
Probability of success of what? Succeeding in a given slot? Succeeding in a given slot provided it attempted in that slot? Succeeding in Slot 5 for the first time? What?

How does P(A) relate to the probability 'p', that you are given in the problem?

probability of not succeeding in last 4 slots = (1-P(A)) * (1-P(A)) * (1-P(A)) * (1-P(A)) = (1-P(A))^4.
So this implies that you mean P(A) to be the overall probability of succeeding in a given slot. Don't make people figure out what your definitions are from reversing your work -- state them!

probability of success = P(A) * probability of failure of other nodes
= P(A) * (1-P(B)) * (1-P(C)) * (1-P(D))
And now this implies something different about what you mean P(A) to be. You said above that P(A) is the probability of success and now you are saying that the probability of success is P(A) multiplied by a bunch of other things.

Well, what is it?

Fully define your terms!

Probability of success for the first time in slot 5 = (1-P(A))^4 * P(A) * (1-P(B)) * (1-P(C)) * (1-P(D))
Please guide me.
So what are you saying the answer is? This? Or what you gave in the first post?
 

WBahn

Joined Mar 31, 2012
29,976
Hi,
I have provided you the equations. Kindly specifically point out the corrections w.r.t. the equations. Otherwise, I won't be able to reach to the correct answer.

Zulfi.
That defeats the purpose. Anyone can throw out a nearly random answer to a problem they haven't even attempted to answer and, if they get someone to "specifically point out the corrections", reach the correct answer without really putting forth any work.

I'm trying to help YOU actually WORK the problem from one end to the other so that YOU will actually UNDERSTAND how to solve the problem instead of just editing a wrong final equation to fix specific errors in order to end up with a correct answer that you don't understand.

If that's not of interest to you, that's fine. I'll wish you well and leave you to your own devices and move on.
 

Thread Starter

zulfi100

Joined Jun 7, 2012
656
Hi,
Total probability = ( probability that Node A will not attempt to transmit in Slots1-4) * (probability that node A will succeed for the first time in slot5)

probability that node A will succeed for the first time in slot5 = p(1-p) (1-p)(1-p)

( probability that Node A will not attempt to transmit in Slots1-4) = (1-p) * (1-p) (1-p) (1-p)

= (1-p)^4

Still I need correction in: ( probability that Node A will not attempt to transmit in Slots1-4)

Please guide me.

Zulfi.
 

WBahn

Joined Mar 31, 2012
29,976
Hi,
Total probability = ( probability that Node A will not attempt to transmit in Slots1-4) * (probability that node A will succeed for the first time in slot5)

probability that node A will succeed for the first time in slot5 = p(1-p) (1-p)(1-p)

( probability that Node A will not attempt to transmit in Slots1-4) = (1-p) * (1-p) (1-p) (1-p)

= (1-p)^4

Still I need correction in: ( probability that Node A will not attempt to transmit in Slots1-4)

Please guide me.

Zulfi.
You are moving in the right direction.

Total probability = ( probability that Node A will not attempt to transmit in Slots1-4) * (probability that node A will succeed for the first time in slot5)

The problem here is that we need Node A to simply not succeed in the first 4 slots. We don't need for it not to attempt to succeed.

In a given slot, Node A will not succeed if EITHER it does not attempt to transmit, OR, it attempts to transmit AND at least one of the other nodes ALSO attempts to transmit.
 

Thread Starter

zulfi100

Joined Jun 7, 2012
656
Hi,
<Node A will not succeed if EITHER it does not attempt to transmit>
Probability that node A will not succeed in first 4 attempts = probability that node will not transmit in each slot or probability that node A transmits in all slots and have collision or probability that node A transmits in some slots and have collision and does not transmit in some slots.

= (1-p)^4 or p(1-p)^4 or ??

I think the mathematical transformation is beyond my skills. So please show me the unfinished stuff.

Zulfi.
 

WBahn

Joined Mar 31, 2012
29,976
Hi,
I am still waiting for your answer.

Zulfi.
I have not been online since a couple minutes after I made my last post. I'm sorry that I don't live online in order to respond to your posts within a couple of hours, but I have this pesky thing known as a life, which include work, family, sleep, commuting, chores, and, admittedly, not a lot else.
 

WBahn

Joined Mar 31, 2012
29,976
Hi,
<Node A will not succeed if EITHER it does not attempt to transmit>
Probability that node A will not succeed in first 4 attempts = probability that node will not transmit in each slot or probability that node A transmits in all slots and have collision or probability that node A transmits in some slots and have collision and does not transmit in some slots.

= (1-p)^4 or p(1-p)^4 or ??

I think the mathematical transformation is beyond my skills. So please show me the unfinished stuff.

Zulfi.
You need to go back to the basics and learn how to determine probabilities when something can happen multiple ways.

When you have an OR relationship, you need to add the probabilities of each way that it can happen.

To do it directly, you have to account for all of the distinct ways that A can succeed.

p(A does NOT succeed in a given slot) = (A does not attempt) + (A does)(B does)(C does not)(D does not) + (A does)(B does)(C does)(D does not) + ......

This can be tricky because you need to account for each possibility exactly once.

It is often easier to find the probability of it not happening since that is an AND relationship, which is usually much easier.

The probability that Node A does NOT succeed in transmitting in a given time slot is (1 - the probability that Node A DOES succeed in transmitting in a given time slot).

The only way that Node A can succeed in transmitting in a given time slot is if (Node A attempts) AND (Node B does not attempt) AND (Node C does not attempt) AND (Node D does not attempt).

p(A does NOT succeed in a given slot) = [1 - (p)(1-p)(1-p)(1-p)] = 1 - p(1-p)^3

Can you take it from there?
 
Top