GATE CS 2004 Q No. 54

ISO/OSI stack, LAN technologies (Ethernet, Token ring), Flow and error control techniques, Routing algorithms, Congestion control, TCP/UDP and sockets, IP(v4), Application layer protocols (icmp, dns, smtp, pop, ftp, http); Basic concepts of hubs, switches, gateways, and routers.

GATE CS 2004 Q No. 54

Postby champion » Tue Jan 10, 2012 3:02 pm

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
Ankur Gupta
Student, ME - CSE, 1st Year
Department of Computer Science & Automation
Indian Institute of Science, Bangalore
http://www.ankurgupta.net
User avatar
champion
Gatementor Regular
Gatementor Regular
 
Posts: 224
Joined: Tue Jan 03, 2012 12:09 am
Location: Bangalore
Currently what are you doing?: Am Studying
My College/Company:: IISc Bangalore
Roll Number: 12125097
Packages: Test Series (TS)
City: Bangalore

Re: GATE CS 2004 Q No. 54

Postby HimaMehta » Wed Jan 11, 2012 12:47 am

champion wrote: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

Answer is B ) 0.625
at the time of 1st collision both A & B will have 1st collision but A wins,,,
So A's s collision counter will be reinitialized to 0 .. at 2nd collision A & B will have 1 st & 2nd collision resply ...
so A will have to select random # from [0,1]
But B Will have to select from [0,1,2,3]
so mapping it
the following are total favouring cases to A 's winning
0-1
0-2
0-3
1-2
1-3
so probability is 5/8 = 0.625
God is REAL, unless explicitly declared INTEGER.!!!
HimaMehta
Gatementor Senior Member
Gatementor Senior Member
 
Posts: 441
Joined: Sat Jul 09, 2011 9:39 pm
My College/Company:: AIR 3997 GAte 2012
Roll Number: 9999999
Packages: Previous Student

Re: GATE CS 2004 Q No. 54

Postby champion » Wed Jan 11, 2012 10:30 am

HimaMehta wrote:Answer is B ) 0.625
at the time of 1st collision both A & B will have 1st collision but A wins,,,
So A's s collision counter will be reinitialized to 0 .. at 2nd collision A & B will have 1 st & 2nd collision resply ...
so A will have to select random # from [0,1]
But B Will have to select from [0,1,2,3]
so mapping it
the following are total favouring cases to A 's winning
0-1
0-2
0-3
1-2
1-3
so probability is 5/8 = 0.625


Thanks a lot for this reply. I have been searching for it's solution for a long time. :)
Ankur Gupta
Student, ME - CSE, 1st Year
Department of Computer Science & Automation
Indian Institute of Science, Bangalore
http://www.ankurgupta.net
User avatar
champion
Gatementor Regular
Gatementor Regular
 
Posts: 224
Joined: Tue Jan 03, 2012 12:09 am
Location: Bangalore
Currently what are you doing?: Am Studying
My College/Company:: IISc Bangalore
Roll Number: 12125097
Packages: Test Series (TS)
City: Bangalore

Re: GATE CS 2004 Q No. 54

Postby Alchemist » Thu Nov 13, 2014 9:54 am

This question is based on Ethernet's exponential backoff algorithm.
After experiencing nth collision in a row for a frame, the adapter chooses a value for K at random from {0,1,2,....,2^m-1}
where m = min(n,10).
The adapter then waits K*512 bit times and then senses the channel whether it is busy or idle.

Note that if a frame is destroyed in the collision, then only it's collision counter increases.

So, backoff race is won by a frame for which this waiting time (K*512 bit times) is less.

After first collision,
n (for A) = 1
n (for B) = 1
both A and B chooses from a random number {0,1}, and given that A wins the race, i.e. A must have been chosen 0 and B have 1.

As A wins the race,
n (for A) = 0
n (for B) = 1
now.

After second collision,
n (for A) = 1
n (for B) = 2
Now, A chooses from a random number {0,1}, and B chooses from a random number {0,1,2,3}
Since waiting time for a frame is directly proportional to this random number (i.e. K*512 bit times), For A to win the race, value of K must be less than than that of K for B.

So, favorable cases :
0-1
0-2
0-3
1-2
1-3

Number of favorable cases = 5
and total number cases = 2*4 = 8

Probability of A to win = 5/8 = 0.625

_________________________________________

"Live Free or Die Hard"
Alchemist
 
Posts: 1
Joined: Thu Nov 13, 2014 9:11 am
My College/Company:: none
Roll Number: 9999999


Return to Computer Networks

Who is online

Users browsing this forum: Google [Bot] and 5 guests
cron