Re: TCP and Loss (inherently lossy nets)

Gregory Lauer (glauer@SURAN.BBN.COM)
05 Oct 87 15:40:34 EDT (Mon)

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

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

This archive was generated by hypermail 2.0b3 on Thu Mar 09 2000 - 14:39:34 GMT