Interview Question

Senior Systems Engineer Interview

-San Diego, CA

Qualcomm

Given a wireless channel with loss rate 0.1, what's the throughput one can get with retransmission.

AnswerAdd Tags

Interview Answers

8 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

0

10/(1.23456...)=8.1 packets per sec

Feng on

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.

aa on

1

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

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

Anonymous on

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

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.

Dmytro on

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

Eugene on

Add Answers or Comments

To comment on this, Sign In or Sign Up.