Re: Measurement bit(s) or not

["Brian Trammell (IETF)" <[e-mail]>]

hi Mikkel, Igor, Alexandre, all,

Engineering is fun, but let's step back a bit. :)

It looks like we're exploring a space of proposals that have different tradeoffs for the patterns of loss and reordering they can easily make visible, tradeoffs for sender (endpoint) versus observer (midpoint) complexity, and tradeoffs for fidelity versus overhead.

In any case, it seems like it is possible to design a signal that would be a vast improvement (from the measurement utility standpoint) over no signal and no discernible pattern in the packet number that will fit in bits scavenged from the Type field of the short header, i.e., the bandwidth overhead will be *zero*, because otherwise in an encrypted-PN world we just have to grease those bits anyway.

Back to Alexandre's question:

Do we want to do this?

Rephrased: Is the passive measurability of loss, reordering (and, if we consider the spin bit as one of the measurement bits, latency) of QUIC important to us, or do we decide we can live with the negative pressure a complete loss of visibility and an vast increase in diagnostic complexity will place on deployment?

Note, of course, that all the proposals we have so far represent a decrease in visibility and an increase in complexity of measurement compared to passive measurement of TCP. New tools will have to be developed. But the loss of visibility is minimal compared to blackout, and the deployability and feasibility of all of these is far, far better than an SSLKEYLOGFILE-based debugging approach, especially in the interdomain case.

I've heard at least one dismissal of this whole space as being too abstract to take seriously. (I'm not concerned, but maybe I've been staring at network measurement both passive and active for too long to know what's intuitive anymore.) Let me then suggest a way forward:

I've announced a table at the London hackathon for "Transport Measurability" (see https://trac.ietf.org/trac/ietf/meeting/wiki/101hackathon), which we intend to set up in the vicinity of QUIC. This was originally intended as the "Spin Bit" table, and we (from ETH) will be there working on scalable, open-source passive measurement tools both for the spin bit as well as for the current TCP TSOPT and SEQ/ACK methodologies (as a basis of comparison, mainly; at least in the case of the spin bit we so far believe the explicit signalœ to have superior usability compared to current TCP measurement). I suggest we expand the scope of table to hack on various signals for loss and reordering, and to compare their complexity and fidelity against the loss and reordering patterns we want visibility into. One output of this work could be a (smaller) set of suggestion(s) for which signal(s) to add, so that those who want to have concrete proposals to evaluate can do so.

Cheers,

Brian


> On 11 Feb 2018, at 20:25, Mikkel Fahnøe Jørgensen <[e-mail]> wrote:
> 
> 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.