The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
336 views

Two CSMA/CD stations are each trying to transmit long (multiframe) files. After each frame is sent, they contend for the channel, using the binary exponential backoff algorithm. What is the probability that the contention ends on round k?

  1. $\Sigma kP_k$
  2. $kP_k$
  3. $\Sigma P_k$
  4. none
asked in Computer Networks by Loyal (7.8k points)
edited by | 336 views
+1
I am getting following as the probability to end the contention on round k.

$\frac{1}{2^1}*\frac{1}{2^2}*\frac{1}{2^3}*......*\frac{1}{2^{k-1}}*\frac{2^k-1}{2^k}$

= $\left \{ \prod_{x=1}^{k-1}\left ( \frac{1}{2^x} \right ) \right \}*\frac{2^k-1}{2^k}$
0
Debashish is right.
0
What does round mean here?? does it mean round of application of backoff algorithm or round of transmission??

1 Answer

0 votes

After k consecutive collisions (with probability p), a station delays retransmission by a random interval uniformly distributed between 0 and 2k , (so the packet is transmitted k+1 times in total).
Number the attempts starting from 1. Attempt i is distributed among 2i−1 slots . Thus, the probability of a collision on attempt i is 1/(2i−1) or 2−(i−1). The probability that the first k-1 attempts will fail is then:
Pk = (1 − 2 −(k−1)) · $· \prod (i=1  to ( k-1)) $ 2 −(i−1) , which can be simplified to:
Pk = (1 − 2 −(k−1)) · 2 − ((k−1)·(k−2)) /2 ,
so, the expected number of rounds is simply: $\sum_{k}^{}$k.Pk

So, the answer is (A)
 

Ref: http://omikron.eit.lth.se/ETSN01/ETSN01/tutorials/Tutorial8.pdf

answered by Active (1.3k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,853 questions
47,514 answers
145,853 comments
62,275 users