Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!necntc!ames!sdcsvax!ucbvax!SURAN.BBN.COM!glauer
From: glauer@SURAN.BBN.COM (Gregory Lauer)
Newsgroups: comp.protocols.tcp-ip
Subject: Re: TCP and Loss (inherently lossy nets)
Message-ID: <8710051957.AA20006@ucbvax.Berkeley.EDU>
Date: Mon, 5-Oct-87 15:40:34 EDT
Article-I.D.: ucbvax.8710051957.AA20006
Posted: Mon Oct  5 15:40:34 1987
Date-Received: Thu, 8-Oct-87 05:35:09 EDT
Sender: daemon@ucbvax.BERKELEY.EDU
Distribution: world
Organization: The ARPA Internet
Lines: 90

Hop-by-hop retransmission is needed in networks with high loss and long routes
if we are to have a reasonable chance of getting anything through the network.
If the link loss probability is p, then the probability of getting a packet
through N hops without hop-by-hop retransmissions is (1-p)**N.  In a lossy
network (p = .50), with a path length of N=10 hops, the probability of getting
a packet through without hop-by-hop retransmissions is thus ~.001.  On the
other hand, end-to-end retransmissions are needed since a node can crash after
having acked a packet and before having forwarded it.

How many packets get sent in each case?

In the following we assume that p**N is approximately 0 and that 1/p<<N (it
lets us sum from 0 to infinity instead of from 0 to N).

Without hop-by-hop retransmission it takes on average 1/(1-p)**N end-to-end
retransmission before the packet will reach the destination.  Each unsuccessful
end-to-end transmission (obviously) doesn't reach the destination, but goes (on
average) 1/p hops, thus the total traffic generated is 1/[p(1-p)**N] packets.
For p=.5 and N=10, this implies ~2000 packets are generated to get the packet
to the destination.  Of course, an end-to-end ack is also needed, which will
generate another 2000 packets (and, unless the retransmission timers are set
"appropriately", the source will continue to transmit while it is waiting for
the ack to get through).

With hop-by-hop retransmission it takes, on average, 1/(1-p) transmissions to
get a packet over a link.  If the hop-by-hop retransmission timers are set
appropriately (so that a packet is retransmitted only if it didn't get across
the link), then a packet is transmitted 1/(1-p)**2 times before the
acknowledgement is received.  Thus the number of transmissions required to get
the packet to the destination is N/(1-p)**2, which for p=.5 and N=10, is 40
packets.  Another 40 packets are required for the end-to-end ack (during which
time the source may continue to send if the end-to-end retransmission timer is
set inappropriately).  Note that in addition to transmissions of the original
packet, there are 1/(1-p) hop-by-hop acks transmitted on each link, adding
N/(1-p) packets to the overhead of getting a packet to a destination.  (For
p=.5, and N=10, this yields another 20 packets each way.) 

Thus ignoring "spurious" end-to-end retransmissions, we have the following
comparison:

with hop-by-hop acks:
   40 transmissions of the original packet
   20 hop-by-hop acks of the original packet
   40 transmissions of the end-to-end ack
   20 hop-by-hop acks of the end-to-end ack
  ---
  120 packets

without hop-by-hop acks:
   2000 transmissions of the original packet
   2000 transmissions of the end-to-end ack
   ----
   4000 packets

Finally, a note about the variance of the round trip time.  Ignoring the impact
of missing hop-by-hop acks, the variance in the number of transmissions
required to get a packet across a link is (I think) q=2[1/(1-p)+{p/(1-p)}**2],
and the variance in the time required to get it to the destination is Nq.  For
our example, this implies a standard deviation in the number of transmission
required to get a packet to the destination of ~24.5 transmissions.  For the
case with no hop-by-hop acks, the number of end-to-end transmissions required
has a variance given by the formula for q above with p replaced by
1-1/(1-p)**N.  For our example this yields a standard deviation of ~1447
transmissions.  Thus in this example, hop-by-hop acks not only reduce the
number of transmissions required but also reduce the variance in the number of
transmissions required (making it easier to have a good estimate of the
round-trip time, and thus reducing the number of unnecessary retransmissions).

For networks with lower losses, the overhead of the hop-by-hop acks will
outway the reduction in number of transmissions required.  We can get an upper
bound on when hop-by-hop acks help as follows.  An upper bound on the number of
transmissions required without hop-by-hop acks is N/(1-p)**N (i.e. each failed
transmission takes the maximum number of hops plus 1).  A lower bound on the
number required with hop-by-hop acks is 2N/(1-p) (i.e. never retransmit a
packet once it has been received...even if you don't know it's been received).
Equating these yields the fact that hop-by-hop acks don't help if
p<1-(.5)**[1/(N-1)], which for N=10 corresponds to p<.074.

This type of analysis is perhaps appropriate for a packet radio network, where
there may be a significant probability that a radio just doesn't receive the
packet and one can (maybe) argue that the probability of loss is independent
from node to node and from transmission to transmission.  This type of analysis
is less useful in networks where packet loss is due to congestion (and
corresponding buffer shortages), where acks have a higher priority, where there
is likly to be significant correlation between the probability that nodes are
congested and where packet (re)transmission is due mainly to timers going off
before a node has a chance to ack a packet that it correctly received.


Greg