Exponential backoff race.... amitmandal03 please have a look

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

Moderators: karthrags, arun_kumar, CS Moderators Team

Exponential backoff race.... amitmandal03 please have a look

Postby ankushgaur » Mon Feb 04, 2013 1:38 pm

The question is:
A and B are the only two stations on an Ethernet. Each has a steady queue of frames to send. Both A and B attempt to transmit a frame, collide, and A wins the first backoff race. At the end of this successful transmission by A, both A and B attempt to transmit and collide. The probability that A wins the second backoff race is
A) 0.5
B) 0.625
C) 0.75
D) 1.0

The solution given: 0.625

p(A wins the second backoff race)
=(A chooses 0)*(B chooses 1or2or3)+
(A chooses 1)*(B chooses 2or3)

=(1/2)(3/4)+(1/2)(2/4)
=5/8
=0.625

but my question is, when A chooses 1, why cant B choose 0 along with 2 and 3? Why are there only 2 choices for B ?

Is it given in the algorithm that B has to choose a value greater than B?
ankushgaur
 
Posts: 29
Joined: Sun Jun 27, 2010 6:36 am
My College/Company:: KC Tech
Roll Number: 0

Re: Exponential backoff race.... amitmandal03 please have a

Postby ankushgaur » Mon Feb 04, 2013 1:52 pm

.................
ankushgaur
 
Posts: 29
Joined: Sun Jun 27, 2010 6:36 am
My College/Company:: KC Tech
Roll Number: 0

Re: Exponential backoff race.... amitmandal03 please have a

Postby amitmandal03 » Mon Feb 04, 2013 2:15 pm

have a look at this - "The probability that A wins the second backoff race "
[first doubt] ---if B will choose 0 and A will choose 1, then B will win the backoff race as there won't be any collision.. !

[second doubt]
After c collisions, a random number of slot times between 0 and 2^c - 1 is chosen. For the first collision, each sender will wait 0 or 1 slot times. After the second collision, the senders will wait anywhere from 0 to 3 slot times (inclusive). After the third collision, the senders will wait anywhere from 0 to 7 slot times (inclusive), and so forth.

For A ,value of c is still 1 but for B value is 2

[refer exponential backoff algorithm for better understanding]
~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

Re: Exponential backoff race.... amitmandal03 please have a

Postby ankushgaur » Mon Feb 04, 2013 3:22 pm

Oh ok i get it now.
A has to win.. so if B chose 0 , that would have meant that B won, that's why it can't choose 0.

Thanks Amit.
ankushgaur
 
Posts: 29
Joined: Sun Jun 27, 2010 6:36 am
My College/Company:: KC Tech
Roll Number: 0


Return to CS Paper Question

Who is online

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