RE: Measurement bit(s) or not

[Mikkel Fahnøe Jørgensen <[e-mail]>]

Actually, since the half-period is 16*2048 so loss can be detected up to
32K packets, or typically 32MB worth of data. At the same time loss can be
detected within the first 16 bytes by trivially comparing the first 8 bits
with the next 8 bits. If these are not the same, something is off.

But it is perfect because all bits could be zero.

To improve on this, each transmitted bit could be spread over two packets,
0, 1 for sending a reset bit, and 1, 0 for sending a set bit. If we then
drop repeating the 8 bit pattern, the shortest half-period remains at 16
packets since an 8-bit Gray code requires 16 packets.

Now we can detect a single loss or swap already after two packets, although
this is probably not interesting since reordering could happen already in
multiple send queues.

On 11 February 2018 at 20.06.14, Mikkel Fahnøe Jørgensen ([e-mail])
wrote:

I already wrote this elsewhere, but the mail topic was a bit off, and I
think it might actually be a good alternative to the other approaches
balancing the simplicity of the square without the problem of having to
wait for the square half period to detect loss.

It is a fractal pattern in the form of grey code. For example an 8 bit code
that is transmitted one bit a time. Each bit represents a wave length and
changes at half the wave length. To simplify synchronisation, the same 8
bit pattern could be transmitted twice before a bit changes. This would
support half-periods of 16, 32, …, 2048 packets.

In addition, there is a lot of error correcting coding theory around this
with noise analysis and maximum likelihood decoders.

https://en.wikipedia.org/wiki/Gray_code
https://en.wikipedia.org/wiki/Constellation_diagram

The encoding is simple as per Wikipedia:

/* * This function converts an unsigned binary * number to reflected
binary Gray code. * * The operator >> is shift right. The operator ^
is exclusive or. */unsigned int binaryToGray(unsigned int num){
    return num ^ (num >> 1);}
/* * This function converts a reflected binary * Gray code number to a
binary number. * Each Gray code bit is exclusive-ored with all * more
significant bits. */unsigned int grayToBinary(unsigned int num){
    unsigned int mask = num;
    while (mask != 0)
    {
        mask = mask >> 1;
        num = num ^ mask;
    }
    return num;}
/* * A more efficient version, for Gray codes of 32 or fewer bits.
*/unsigned int grayToBinary32(unsigned int num){
    num = num ^ (num >> 16);
    num = num ^ (num >> 8);
    num = num ^ (num >> 4);
    num = num ^ (num >> 2);
    num = num ^ (num >> 1);
    return num;}



On 10 February 2018 at 22.41.51, Lubashev, Igor ([e-mail]) wrote:

I am a bit sceptical about the square. With TCP, packet trace shows loss of
any packet, except for SYN. The "square wave" whould show no loss at all
for short connections (fewer than a "wavelength" of packets). Moreover, the
square wave can only detect loss after up to the wave length of subsequent
packets has been transmitted. If there is an application pause in
transmission, loss may not become evident.

Basically, a spin bit or a bit pattern (like a square wave) may help in
troubleshooting, but it will be more uncertain and hokey than what people
come to expect of tcp. We have be very clear in acknowledging it.

-----Original Message-----
*From:* [e-mail] [[e-mail]]
*Received:* Saturday, 10 Feb 2018, 12:34PM
*To:* [e-mail] [[e-mail]]
*Subject:* Measurement bit(s) or not

On 07/02/2018 14:34, Brian Trammell (IETF) wrote:
 > hi Jana,
 >
 >> 3. Some sequencing information -- a few bits of the packet number
perhaps
 >> -- should be revealed (for monitoring. Number of bits TBD.)
 >
 > This is the crux of the argument. On one side we have the risk of misuse
and
 > ossification (well, not ossification -- these bits are *meant* for the
path
 > -- rather the risk that we'll figure out later that we specified the
wrong
 > thing), on the other side we have the loss of visibility into how QUIC
 > traffic interacts with the network as compared to TCP, with a side
question
 > of whether or not this visibility is really the transport layer's problem
 > despite the evolution the practice of diagnostics and troubleshooting
using
 > TCP information.
 >
 > If we can come to agreement on this question, everything else falls into
 > place. I have my arguments here, but as you said, this subthread is not
the
 > place for them. :)

The crux indeed. So what about settling it first ?

With the troubleshooting hat, I can only stress the need for measurement
bits,
for the benefit of everybody, since s**t happens, networks are imperfect,
and
nifty encapsulations-with-seqnum will simply not be where you need them.

Now to the exact nature of these measurement bits:

Thanks to the detailed exchanges on this thread, it is by now clear that a
simple gapless counter, even nonzero-based and XORed, is not acceptable. The
4-bit SSN comes pretty close but is not enough when things go really wrong
(and
they will - and that's where we need the tool).

Then Kazuho's square signal and Mikkel's Pi (or any other consensual
self-synchronizing sequence) ramification came up. They are both appealing
for
their elegance and low complexity on QUIC endpoints. Beyond their quirks
acknowledged here, here are a few considerations for troubleshooting:

  (1) Since reordering is less of a concern to QUIC than to TCP, it becomes
a
secondary goal. This is nice, because the square doesn't see it, and the
self-synchronizing sequence will only tolerate a mild one, and never see its
detail like cycle length etc.

  (2) There's of course a huge difference between them in complexity for the
midpoint: square is trivial, Pi is hefty.

Given these, a benevolent, troubleshooting-minded passive midpoint will
clearly
vote for the square. Now the obvious question is: is this acceptable, or
deemed
too easy for a Murphy, Inc. active middlebox to see upstream losses and
benevolently wreak havoc by delaying packets ?

_________________________________________________________________________________________________________________________

Ce message et ses pieces jointes peuvent contenir des informations
confidentielles ou privilegiees et ne doivent donc
pas etre diffuses, exploites ou copies sans autorisation. Si vous avez recu
ce message par erreur, veuillez le signaler
a l'expediteur et le detruire ainsi que les pieces jointes. Les messages
electroniques etant susceptibles d'alteration,
Orange decline toute responsabilite si ce message a ete altere, deforme ou
falsifie. Merci.

This message and its attachments may contain confidential or privileged
information that may be protected by law;
they should not be distributed, used or copied without authorisation.
If you have received this email in error, please notify the sender and
delete this message and its attachments.
As emails may be altered, Orange is not liable for messages that have been
modified, changed or falsified.
Thank you.