Interview Question

Senior Systems Engineer Interview San Diego, CA

Given a wireless channel with loss rate 0.1, what's the

  throughput one can get with retransmission.
Answer

Interview Answer

6 Answers

0

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

Jun on Apr 29, 2012

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

0

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.

aa on Aug 2, 2012
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

chris on Aug 8, 2012
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)] < 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

Anonymous on Dec 17, 2012
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...

Eric on Jul 16, 2014

Add Answers or Comments

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