## Interview Question

## Interview Answer

6 Answers

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

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.

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

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)] < k / (E[N_1] + E[N_2] + .. .+ E[N_k]) = 1 / E[N_1] = 0.9.

This comes from Jensen's inequality. However, for large 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

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...

## Add Answers or Comments

To comment on this question, Sign In with Facebook or Sign Up

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).

JunonApr 29, 2012