Subject: RE: Comments to "Advice for Internet Subnetwork Designers"

From: "Michael Meyer (EED)" <[email-masked]>
Date: Mon, 31 Jul 2000 14:42:20 +0200

Hi Phil,

In general I like your proposal to provide more information to the link layer. 

>
>>I (as a link layer designer) would like to use a flow's DSCP 
>*not only* to 
>>control scheduling and/or queue management algorithms at the 
>network layer, 
>>but *also* to control link layer error control algorithms.
>
>Exactly. Information theory says there are fundamental tradeoffs
>between delay and throughput, and it would be nice for the link layer
>to have some guidance in making these tradeoffs.
>
>The main parameter is the FEC interleaver blocksize. Larger blocksizes
>yield better performance, especially over fading channels, but they
>increase delay. So something that can tell the physical layer what
>size FEC block to use would be very helpful.
>

There are some more parameters like e.g. FEC code rate and transmission power.

>[The idea that larger blocks perform better over noisy channels may
>seem strange to those unfamiliar with coding theory. If you think that
>larger blocks would have a larger probability of at least one error,
>you're right. That's why, on *uncoded* channels, high error rates
>dictate smaller blocks. But with interleaved FEC, it's not whether
>there are *any* errors in the block, but whether their number exceeds
>some correction limit. With uncorrelated channel errors, the number of
>errors in any given block follows a binomial distribution; as
>blocksize is increased, this becomes a gaussian distribution. Thanks
>to the law of large numbers, the standard deviation of this
>distribution increases only as the square root of the blocksize. So
>the probability that the code will fail, i.e., be overwhelmed by
>errors, goes to zero as the blocksize approaches infinity *provided*
>that the expected number of errors in a block is within the code's
>error correction capability.]

I think that your explanation regarding the coding theory might lead some into the wrong direction. What you describe in your "tutorial" is an ideal scenario. The mobile radio channel is different and therefore infinite blocks lenghts are far from ideal.

The mobile radio channel can be described by a so-called coherence time, which is a measure for the duration during which the channel is correlated. Interleaving is trying to move coded bits describing the same info bit further apart than the coherence time. If that is achieved there is no further gain by increasing the interleaving. 

Interleaving does help to reduce the bit error rate for a channel, but for a given bit error rate, the block error rate is increasing with increasing block length. Thus, there exists an optimal block size. It has to be large enough for efficient interleaving, but small enough for a low block error rate.
>
>This has gotten me thinking about how TOS should really work in a
>wireless link. When you think about it, the old-style qualitative TOS
>bits that meant "low delay" "high throughput" or "high reliability"
>are really not that orthogonal. Ultimately the *only* link/subnet
>characteristic that ever really matters is LATENCY. "High throughput"
>is important only insofar as it reduces latency due to queuing delay,
>and "high reliability" is important only as it decreases (or avoids)
>the latency of an end-to-end retransmission scheme.  In every
>situation, the goal is the same: to complete a "transaction" as
>quickly as possible.
>
>This suggests that all the link layer ever *really* wants to know is
>the application transaction size. Two examples:
>
>A bulk file transfer is a single "large" transaction, i.e., one that
>will take many packets to complete.  We assume that just having part
>of the file is useless, so we want to finish the whole thing as
>quickly as possible. And we assume the file to be much larger than the
>bandwidth*delay product of the available network path, so propagation
>delays have a small effect on the transaction latency.
>
>Here the link can be allowed to operate on the data in large chunks,
>e.g, by using large FEC code blocks that could possibly span many IP
>packets. This will increase throughput on a noisy channel and allow
>the transaction to complete more quickly -- thus reducing "latency" by
>this particular application's definition.

Besides the negative impacts of increased delays for TCP slow start, increasing the interleaving delay might be harmful, because TCP has this bias for connections with a large RTT. This is for me another reason for not having large interleaving blocks.

I don't see big advantages of having many IP packets in one FEC code block for the reasons I explained above. But I do completely agree that the link layer needs more information to perform its job in the best possible way.

/Michael

******************
Michael Meyer
Ericsson Research

---

From: Phil Karn <[email-masked]>
Date: Mon, 31 Jul 2000 07:54:32 -0700

>There are some more parameters like e.g. FEC code rate and transmission power.

Correct. I was assuming these were held constant.

>The mobile radio channel can be described by a so-called coherence
>time, which is a measure for the duration during which the channel is
>correlated. Interleaving is trying to move coded bits describing the
>same info bit further apart than the coherence time. If that is
>achieved there is no further gain by increasing the interleaving.

You got me -- I was oversimplifying too much. I should have said
"channel code block size" rather than "interleaving block size". The
channel code can be a layered combination of one or more FEC code
elements and interleaving. The interleaving may be 1) explicit, 2) an
internal element of a particular code (e.g., a turbo code), or 3) an
implicit property of a large block code, e.g., Reed-Solomon. All that
matters is that the user data bits are effectively "spread" over the
entire channel code block to effectively deal with channel burst
errors.

So assuming that the parameters of each element making up the channel
code are optimally chosen, you can always do better with a larger
channel code block size.

Yes, you do reach a point of diminishing returns with increasing
channel block size, both against Gaussian noise and against fading.
But the improvement is always monotonically increasing with block size.

The diminishing returns point usually occurs first against Gaussian
noise. For modern codes, this is on the order of one or more
kilobits. (The turbo code in the Qualcomm HDR forward link uses a 128
byte block size).

This leaves channel fading. Here the point of diminishing returns
depends heavily on the channel, specifically the coherence time just
as you say. The usual rule of thumb is that you want a code block
transmission time that is at least 10x the coherence time. This can be
a *very* large number when you're transmitting at high speed on a
slowly fading channel. At some point, it's more practical to layer ARQ
above the FEC and just keep trying until the channel fade ends and the
FEC can again deal with it.

The FEC/ARQ tradeoff point depends on factors like the round trip
delay of the channel and the per-packet ARQ overhead. The larger the
FEC channel block size, the lower the overhead of the ARQ header.
Also, if a larger FEC block size can reduce the ARQ retransmission
rate, the higher layer protocols reap the benefit of decreased delay
variance.

What I'm saying is that it would be nice to at least give the physical
layer the opportunity to aggregate relatively large chunks of user
data, possibly comprising several IP packets, if the physical layer
decides that would improve performance over a slow fading channel, and
if the application can deal with the increased short-term latency.

>Besides the negative impacts of increased delays for TCP slow start,
>increasing the interleaving delay might be harmful, because TCP has
>this bias for connections with a large RTT. This is for me another
>reason for not having large interleaving blocks.

I don't quite understand this. My experience is that TCP adapts quite
well to large RTTs, especially if the RTTs are stable and the packet
loss rate is low. TCP window scaling is now pretty widely deployed,
although it may have to be enabled.

What you really want to avoid are the nasty interactions between TCP
and link/physical layer retransmissions that can occur in certain link
operating regions. Consider a physical layer with a long latency and
link layer ARQ. Most packets go through without link level ARQ, so
most of the time the RTT is consistent and TCP shrinks its RTO to just
above the RTT. But whenever the link layer retransmits, the RTT spikes
and there's a spurious TCP retransmission.

If link level retransmissions are rare, then spurious TCP
retransmissions are also rare and their effect on performance is
minimal.  If link level retransmissions are very frequent, TCP sees a
high RTT variance and sets an RTO that is well above the average
value. Again, spurious TCP retransmissions are rare. But things can
degrade badly in the intermediate region, say, every 10th packet. Just
when TCP has dropped its RTO to just above the average RTT, another
link level retransmission occurs and causes TCP to spuriously
retransmit.

Perhaps we could build a better (higher order) RTT model into TCP, or
tune its existing parameters better. But I think it would be better to
fix the physical layers to work better with TCP as it currently
stands.

Phil

---

From: Lloyd Wood <[email-masked]>
Date: Mon, 31 Jul 2000 16:28:47 +0100 (BST)

> >reason for not having large interleaving blocks.

bias _against_ connections with a large RTT when they're competing in
a pipe against connections with smaller RTTs which adapt faster to
changes.

Up the overall RTT of your TCP connections by interleaving, and
expect them to do less well against other connections.

> although it may have to be enabled.

L.

<[email-masked]>PGP<http://www.ee.surrey.ac.uk/Personal/L.Wood/>