Interviewer was correct. With probability 0.1 you have one retransmission, with probability (0.1)^2 you have two, etc., since you can also lose the retransmitted packets, reducing the throughput to approximately 0.89.

8 Answers

* This post has been removed. Please see our Community Guidelines or Terms of Service for more information.*

▲

1

▼

Interviewer was correct. With probability 0.1 you have one retransmission, with probability (0.1)^2 you have two, etc., since you can also lose the retransmitted packets, reducing the throughput to approximately 0.89.

▲

0

▼

It is equivalent to simply a binary erasure channel with erasure probability 0.1, whose capacity is 1-0.1 = 0.9.

aa should re-learn information theory and stochastic process

▲

0

▼

First of all I don't think it has anything to do with the capacity of BSC. Note that h(0.1) = 0.46 and that means 1 - h(0.1) is roughly 0.5. If the packet error rate is 10% then BER is in the order of 0.1 / N where N is the length of the packet in bits. For that, the capacity of BSC is almost 1.

In any case, in the non-ergodic case I believe the throughput is less than 0.9.

Assume you want to send packets p_1, p_2, ..., p_k and each one takes N_1, N_2, ..., N_k time slots. Then, define the k-Packet Throughput (I made it up) as follows

k-packet Throughput = (k / (N_1 + N_2 + ... + N_k)).

Note that this throughput is a random variable. We can define the throughput based on this as the expected value of k-packet Throughput with respect to random variables N_1 , N_2, ...

E[k-packet throughput] = E[ k / (N_1 + N_2 + ... +N_k)] 8' from the law of large numbers we have N_1 + N_2 + ... + N_k -> k E[N] = 1 / 0.9 * k.

This suggests that k-packet throughput is a random variable which converges to its mean for large k, but for a finite k, its average is less than 0.9

All in all, I would have answered the question the way you did. In the long run, out of N transmissions you have 0.9 received and therefore the throughput should be 0.9

▲

0

▼

Model the problem based on the average number of transmissions it takes to deliver a packet. Let N be the number of transmissions. Then:

Pr[N=1] = 0.9

Pr[N=2] = 0.1*0.9

Pr[N=3] = 0.1*0.1*0.9

...

and so on. The expected number of transmissions per packet is:

E[N] = Sum{ k*Pr[N=k] }

= 1*Pr[N=1] + 2*Pr[N=2] + 3*Pr[N=3] + ...

where the summation index k goes from 1 to infinity.

Then the throughput is 1/E[N] packets per transmission, which is 0.896...

▲

0

▼

In the last solution, the number is calculated incorrectly. Accurate calculation gives the expected number of transmissions per packet E[N] = 1.11111, so that 1/E(N)=0.9, which corresponds to the reduction of transmission rate by exactly 10%, as suggested earlier.

▲

0

▼

p=0.1 - probability of a packet transmission failure

If we transmit a sequence of N packets with retransmission then an expected number of successfully transmitted packets will be E[N]=p*E[N-1]+(1-p)*(E[N-1]+1)=(1-p)+E[N-1], and as E[0]=0 it easy to solve the recursion: E[N]=N*(1-p)

Expected number of successfully transmitted packets per one transmitted packet will be C[N]=E[N]/N=(1-p).

The channel capacity is limit of C[N] as N approaching to infinity that is clearly equal to 1-p=0.9

To comment on this, Sign In or Sign Up.

Would you like us to review something? Please describe the problem with this {0} and we will look into it.

Your feedback has been sent to the team and we'll look into it.

It can modeled as binary symmetric channel.

As to my understanding, channel capacity can be acheived with perfect feedback and simple retransmission scheme, so i guess the answer is 1-H(0.1).