Targate 2260 - Q. no. - 27 - Exponential backoff algorithm

Enter "Paper ID, Question Number" in subject line for query! Start a new thread for every question.

Moderators: karthrags, arun_kumar, CS Moderators Team

Targate 2260 - Q. no. - 27 - Exponential backoff algorithm

Postby browseand » Sun Jan 27, 2013 8:47 am

Let P and Q be two stations arrempting to transmit on an thernet. Each has a steady queue of frames to send. After wach frame is sent(from both sides), they collide for the first time(round 1) and contend for the channel, using the binary exponential backoff algorithm.
What is the probability tha the contention ends on round 4?


Required probability = P(collision at round 1) * P(collision at round 2) * P(collision at round 3) P(No collision at round 4)
= 1/2 + 4/16 + 8/64 + (1 - 16/256)
= 1/2 + 1/4 + 1/8 + 15/16 = 15/1024
The individuals probabilities are calculated based on the fact that, after the i'th collision, a station picks a waiting slot from the interval [0 - (2^i )- 1]

In the given solution they have calculated the required probability as follows
Required probability = 1 * 1/2 * 1/4 * (1-1/8) = 7/64
Looks like here they are assuming that a station picks a waiting slot from the interval [0 - 2^(i-1)], which is wrong, of course.

Am I overlooking something here??
-Abhijith
browseand
 
Posts: 23
Joined: Mon Oct 04, 2010 2:49 pm
My College/Company:: -
Roll Number: 99999

Re: Targate 2260 - Q. no. - 27 - Exponential backoff algorit

Postby amitmandal03 » Sun Jan 27, 2013 4:02 pm

all events are dependent events. collision at second round is dependent on collision at first round..
and you need to find intersection of all events

p(B/A)=P(A intersection B)/p(A)

hence P(A intersection B)= P(A)*P(B/A)
where p(a) = collision at first round and p(B/A)=collision at second round given collision at first round has already occurred
~Amit
User avatar
amitmandal03
Gatementor Guru
Gatementor Guru
 
Posts: 1539
Joined: Sat Sep 22, 2012 3:19 pm
Currently what are you doing?: Am Studying
My College/Company:: GATE
Roll Number: 0
City: Bangalore


Return to CS Paper Question

Who is online

Users browsing this forum: No registered users and 3 guests
cron