For stop-and-wait protocols,how many retransmissions on average are
needed when packet loss is 20%. assume ack are not lost. ( X sends msg
to Y; if ack not received by timeout, resend the message. Persist
until the ack is received. Then go to next msg.)

Hello Sean07,

The short answer an average of 25% retransmissions.

The explanation for the short answer begins with a brief look at the
situation. I will refer to the packet loss rate as PLR which you say
is 20% (or 0.2). The probability a message is sent in a single attempt
is 80% (1-PLR). The probability a message is sent in two attempts is
PLR*(1-PLR) - the first attempt failed and the second succeeded or
16%. You can solve for the power series but instead I did a quick
table in Excel using the recursion formula for a dozen rows to get the
answer posted above. The values in the table are what Excel
calculated.

attempts  probability  att x prob  cum packets
 1         0.800000     0.800000    0.800000
 2         0.160000     0.320000    1.120000
 3         0.032000     0.096000    1.216000
 4         0.006400     0.025600    1.241600
 5         0.001280     0.006400    1.248000
 6         0.000256     0.001536    1.249536
 7         0.000051     0.000358    1.249894
 8         0.000010     0.000082    1.249976
 9         0.000002     0.000018    1.249995
10         0.000000     0.000004    1.249999
11         0.000000     0.000001    1.250000
12         0.000000     0.000000    1.250000
Totals     1.000000     1.250000
(the last row is a cross check
  total probability = 1 - check
  total att x prob = last row of cum packets - check)

So, the total "average" is 1.25 x (packets to send) or 25%
retransmission rate. If some part of this answer is unclear or you
need a more complete answer, please make a clarification request.

  --Maniac

---

Request for Answer Clarification by sean07-ga on 06 Oct 2004 22:30 PDT

Hi,
   please send the clarification of answer using the power series and
a brief explanation. I need this within another 3-4 hours.

Thanks,

Sean07

---

Clarification of Answer by maniac-ga on 07 Oct 2004 15:42 PDT

Hello Sean07,

Let me explain the formulas a little more clearly using the table already provided.

The first column is simply the number of messages necessary to
transmit to send a message. For the first row - it is one, no
retransmissions necessary. Each row following has N-1 failures before
the message was successfully sent (or N total messages sent). In a
similar way, we will subtract 1 from the average number of message
sent to get the percentage of retransmissions.

The second column can be computed as:
  =0.8*(0.2^(N-1))
[N refers to the value in the first column]. This is the first power
series and as you can see from the values in the table, it rapidly
converges to zero. The total at the bottom of this column confirms
that the total probability is 1 (within accuracy of the values shown)
as a cross check.

The third column is
  =N*Probability
[the product of the first two columns]. This is the second power
series and you can see this converges to zero as well. It converges to
zero because the number of messages sent grows much more slowly than
the probability of this occurance. The total at the bottom of this
column is 1.25 and represents the average number of messages sent
assuming the stated failure rate. Subtracting 1 gets 0.25 or 25% as
the average number of retransmissions.

The fourth column is a running subtotal of the third column. This also
demonstrates convergence to the final (1.25) value shown as the total
of the third column.

  --Maniac