Google Answers Logo
View Question
 
Q: Urgent: Small problem on stop-and-wait protocol ( Answered 4 out of 5 stars,   0 Comments )
Question  
Subject: Urgent: Small problem on stop-and-wait protocol
Category: Computers > Wireless and Mobile
Asked by: sean07-ga
List Price: $5.00
Posted: 06 Oct 2004 11:59 PDT
Expires: 05 Nov 2004 10:59 PST
Question ID: 411131
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.)
Answer  
Subject: Re: Urgent: Small problem on stop-and-wait protocol
Answered By: maniac-ga on 06 Oct 2004 16:17 PDT
Rated:4 out of 5 stars
 
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
sean07-ga rated this answer:4 out of 5 stars

Comments  
There are no comments at this time.

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  


Google Home - Answers FAQ - Terms of Service - Privacy Policy