[Bloat] Packet reordering and RACK (was The "Some Congestion Experienced" ECN codepoint)

[Sebastian Moeller]

Dear Carsten,

please excuse my tortured logic, being from outside the field it seems I routinely misuse the nomenclature and sow confusion.

> On Mar 17, 2019, at 18:09, Carsten Bormann <cabo at tzi.org> wrote:
> 
>>> 
>>>>> The end-to-end argument applies:  Ultimately, there needs to be resequencing at the end anyway, so any reordering in the network would be a performance optimization.  It turns out that keeping packets lying around in some buffer somewhere in the network just to do resequencing before they exit an L2 domain (or a tunnel) is a pessimization, not an optimization.
>>>> 
>>>> 	I do not buy the end to end argument here, because in the extreme why do ARQ on individual links anyway, we can just leave it to the end-points to do the ARQ and TCP does anyway.
>>> 
>>> The optimization is that the retransmission on a single link (or within a path segment, which is what I’m interested in) does not need to span the entire end-to-end path.  That is strictly better than an end-to-end retransmission.  
>> 
>> 	I agree, and by the same logic local resequencing is also better,
> 
> Non sequitur.  The same logic simply does not apply.  A resequenced packet consumes the same transmission resources.  (It also consumes more buffer resources.  So it is strictly worse when just looking at network resources expended, which is the basis for the kind of logic applied here.)

In my tortured example the latency cost of resequencing at the re-ordering fast link was much smaller than the latency cost of resequencing after traversing the bottleneck link, the typical situation for end users. My focus is on the latency visible at that point, I agree that for the intermediate hop it will be simpler to just forward those packets that traversed the link intact.

> 
>> unless the re-ordering event happened at the bottleneck link.
> 
> Not sure how this comes in now.

	This comes from my vantage point from the edge, I really am sympathetic to what the core network needs to do to maintain the illusion of temporal ordering, but I do really care for end to end latency more than allowing core routers to get away with less buffer memory.

> 
>>> Also, a local segment may allow faster recovery by not implicating the entire e2e latency, which allows for strictly better latency.
>>> So, yes, there are significant optimizations in doing local retransmissions, but there are also interesting interactions with end-to-end retransmission that need to be taken care of.  This has been known for a long time, e.g., see https://tools.ietf.org/html/rfc3819#section-8 which documents things that were considered to be well known in the early 2000s.
>> 
>> 	Thanks, but my understanding of this is basically that a link should just drop a packet unless it can be retransmitted with reasonable effort (like the G.INP retransmissiond on dsl-links will give up); sure we can argue about what "reasonable effort" is in reality, but I fear if we move away from 3 dupACKs to say X ms all transport links will assume they have leewway to allow re-ordering close to X, that will certainly be worse than today. And since I am an end-user and do not operate a transport network, I know what I prefer here…
> 
> I’m sorry, I grew up as transport layer guy, so “transport” means L4 (transport layer) for me, not “transport network”.
> You may want to re-read my sentences with that knowledge; they might make more sense.

	Sorry for my misuse of the nomenclature, will try to stick to transport network.


> 
>>> Resequencing (which is the term I prefer for putting things back in sequence again, after they have been reordered) requires storing packets that are ahead of later packets.
>> 
>> 	Obviously.
>> 
>>> This is strictly suboptimal if these packets could be delivered instead (in contrast, it *is* a good idea to resequence packets that are in a queue waiting for a transmission opportunity).
>> 
>> 	Fair enough, but that basically expects the bottleneck link that actually accumulates a queue to do the heavy lifting, not sure that the economic incentives are properly aligned here.
> 
> It can actually do so more easily, because the speeds are lower.

	Tell that to the person paying for the CMTS/BNG, the issue is that queueing here sees to happen not directly at the edge but at centralized places, that will need to queue traffic for 10s of thousands of end-users. This still might be easier than in core.

> But deployment economy arguments are interesting as well; I was making theoretical arguments first.
> 
>>> So *requiring*(*) local path segments to resequence is strictly suboptimal.
>>> 
>>> (*) even if this is not a strict requirement, but just a statement of the form “the transport will be much more efficient if you deliver in order”.
>> 
>> 	My point is the transport will much more useful if if undertakes (reasonable) effort to deliver in-order,
> 
> Please re-read as advised above.
> 
>> that is slight;y different, and I understand that those responsible for transport networks have a different viewpoint on this.
>> 
>>> 
>>>> To put numbers to my example, assume I am on a 1/1 Mbps link and I get TCP data at 1 Mbps rate and MTU1500 packets (I am going to keep the numbers approximate) and I get a burst of say 10 packets containing say 10 individual messages for my application telling the position of say an object in 3d space
>>>> 
>>>> each packet is going to "hog" the link for: 1000 ms/s * (1500 * 8 b/packet ) / (1000 * 1000 b/s)  = 12 ms
>>>> So I get access to messages/new positions every 12 ms and I can display this smoothly
>>> 
>>> That is already broken by design.
>> 
>> 	Does not matter much, a well designed network should also allow to do stupid things…
> 
> Sure, but it won’t work very well then (and there is no point in optimizing for that — remember: all in-network work is just an optimization under the end-to-end principle).
> 
>>> If you are not accounting for latency variation (“jitter”), you won’t be able to deal with it.
>> 
>> 	Which would just complicate the issue a bit if we would introduce a say 25 ms de-jitter buffer without affecting the gist of it.
> 
> That buffer increases the total latency but also the (useful) packet delivery rate in the presence of reordering.

	Yes, but IMHO it does not change the problem in a qualitative way.

> 
>>> Your example also makes sure it does not work well by being based on 100 % utilization.
>> 
>> 	Same here, access links certainly run closer to 100% utilization than core links, so operation at full saturation is not completely unrealistic, but I really just set it up that way for clarity.
> 
> Please use an example that is more realistic.

	Why? Unless your argument is an additional 100ms of latency does not matter, I fail to see how the "realness" of my example is relevant. TCP will only pass data to the application after (internal) resequencing, and if we allow extreme out-of-order delivery that will show up as additional extreme latency for the TCP-using application. Now one can claim that TCP might be the wrong "transport" ( I assume that is the correct use of the term), but that effectively demotes TCP to a bulk transport while clearly it does a reasonable job even for mild real-time requirements (I note that even "once a day" is a real-time requirement, one that should be easily achievable with TCP).

> 
>>>> Now if the first packet gets r-odered to be last, I either drop that packet
>>> 
>>> …which is another nice function the network could do for you before expending further resources on useless delivery; see e.g. draft-ietf-6lo-deadline-time for one way to do this.
>> 
>> 	Yes, but typically I do not want the network to do this, as I would be quite interested in knowing how much too late the packet arrived.
> 
> I don’t know how to make use of that knowledge, do you?

	Well in a packet capture, seeing a packet out-of-sequence with a delay has more value than not seeing a packet at all, was that culled due to the deadline or was it lost for other reasons, and do I really care? In the first case it can be used for diagnosis in the second it can not.

> Early discarding of a late packet (e.g., by not retransmitting it in the first place) is so much better.

	This seems to be a) pretty cool and b) restricted to a number of quite special use-caeses, no? This might be okay for real time packets (where the consumer needs to react with tight timing constraints), but even just for VoIP  (a mild RT application) it might be better to be able to reconstruct intelligible speech with a massive delay than getting something garbled beyond recognition by dropped packets in a timely fashion. But I am sure there are examples where a deadline drop might be advantageous, it is just that none of my use-cases fall into that category. 
And I naively see only use for that if the bandwidth/tx-slot advantage gained from dropping instead of transmitting a packet is larger than the loss incurred from not getting the information at all, I would guess real-time control with lots of redundant sensors to be such a case, assuming we talk about rarely dropping a packet.

> 
>>>> and accept a 12 ms gap or if that is not an option I get to wait 9*12 = 108ms before positions can be updated, that IMHO shows why re-ordering is terrible even if TCP would be more tolerant. 
>>> 
>>> You are assuming that the network can magically resequence a packet into place that it does not have.
>> 
>> 	All I expect is that the network makes a reasonable effort to undo re-ordering close to where re-ordering happened.
> 
> All I’m trying to say is that this is bad engineering, apparently perpetuated by bad transport layer implementations.

	??? Now I am confuzed, to me engineering is all about balancing trade-offs, and this is all about how to evaluate different dimensions. I believe we agree that a network should not re-order packets artificially without some justification and we also agree that some level of re-ordering might be un-avoidable, we basically haggle over how much is acceptable. I also believe, and correct me if I am wrong, that we agree that with TCP endpoints prefer less over more en-passage re-ordering. So why is it bad for a transport layer to aim for pleasing its users (in my book the transport network only exists to allow end-to-end communication)?

> 
>>> Now I do understand that forwarding an out-of-order packet will block the output port for the time needed to serialize it.  So if you get it right before what would have been an in-order packet, the latter incurs additional latency.  Note that this requires a bottleneck configuration, i.e., packets to be forwarded arrive faster than they can be serialized out.  Don’t do bottlenecks if you want ultra-low latency.  (And don’t do links where you need to retransmit, either.)
>> 
>> 	I agree, but that is live with a home internet access link, the bottleneck is there. This also points out a problem with the L4S argument for end-users, as the ultra-low latency (their words, not mine) will not realize for end-users close to what the project seems to promise.
> 
> I think reordering is not really a problem for ultra-low latency, or more specifically, once reordering happens, you are no longer in the ultra-low latency domain,

	In this thread it has been mentioned that L4S will allow more reordering by mandating participating hosts to implement RACK, so from a transport network's perspective the L4S identifier can be seen as a license to allow more re-ordering. This runs afoul of L4S's claim of ultra-low latency, I agree, but I do not have to square that circle. 
But in the context of this discussion we have the transport network that re-orders packets simply because this apparently makes the network more efficient and L4S allows it, which according to your argument would break the L4S stated goal of low latency. I can not believe that this is the L4S position in regards to re-ordering (reading https://tools.ietf.org/html/draft-ietf-tsvwg-ecn-l4s-id-06#page-23 A.1.7.  Measuring Reordering Tolerance in Time Units tells me they fail to actually make the connection between reordering and increased latency for the affected flow).

> 
>>>> Especially in the context of L4S something like this seems to be totally unacceptable if ultra-low latency is supposed to be anything more than marketing. 
>>> 
>>> Dropping packets that can’t be used anyway is strictly better than delivering them.
>> 
>> 	Well, not for L4S, as TCP Praque is supposed to fall back to legacy congestion control behavior upon encountering packet drops…
> 
> L4S is for reliable transport, which is a different scenario than the one that benefits a lot from deadlines for packets.  (Well, deadlines might be used to make sure there is no dual retransmission, both local and end-to-end, but again, this is not where you would use L4S.)
> 
>>> But apart from that, forwarding packets that I have is strictly better for low latency than leaving the output port idle and waiting for previous-in-order packets to send them out in sequence.
>> 
>> 	It really depends what we mean when we talk about latency here, as shown for and end-user that might be quite different…
> 
> Apart from the port blocking effect I talked about (which is mostly relevant for highly scheduled transmission schemes), I really have no idea how the end-to-end latency would benefit from sitting on packets while the port is idle.

	Because as demonstrated with my toy example above that decision to send intact packets immediately might incur a visible delay-increse by 108 ms, so from the end-points perspective transmitting before re-sequencing can have a noticeable effect.


> 
>>>>> For three decades now, we have acted as if there is no cost for in-order delivery from L2 — not because that is true, but because deployed transport protocol implementations were built and tested with simple links that don’t reorder.  
>>>> 
>>>> 	Well, that is similar to the argument for performing non-aligned loads fast in hardware, yes this comes with a considerable cost in complexity and it is harder to make this go fast than just allowing aligned loads and fixing up unaligned loads by trapping to software, but from a user perspective the fast hardware beats the fickle only make aligned loads go fast approach any old day.
>>> 
>>> CPUs have an abundance of transistors you can throw at this problem so the support of unaligned loads has become standard practice for CPUs with enough transistors.
>>> I’m not sure this argument transfers, because this is not about transistors (except maybe when we talk about in-queue resequencing, which would be a nice feature if we had information in the packets to allow it).
>> 
>> Like the 5-tuple in TCP and UDP?
> 
> That doesn’t help.  I need a sequence number for resequencing,

	If you do ARQ on your link, you will in all likelihood have something equivalent as you need to identify the packets that need to be retransmitted. As my proposed goal is not generic re-sequencing, but simply not to introduce any additional re-ordering, that should be sufficient, no?

> and I can’t use the transport layer one because that is being encrypted.  Again, this is mostly theoretical as I don’t see people rushing to do in-queue resequencing any time soon.

	I guess you are right, but then please do not complain that you need to stay idle while waiting for retransmit, if that is a conscious trade-off you engineered into your system ;)

> 
> (Skipping some text that is not relevant to my argument here.)
> 
>>> Where does this number come from?  100 ms is pretty long as a reordering maximum for most paths outside of satellite links. Instead, you would do something based on an RTT estimate.
>> 
>> 	I just made that number up as the exact N does not matter, the argument is what ever we set as the new threshold will be approached by transport characteristics. Then again havin something that inversely scales with bandwidth is certainly terrible from a transport perspective, so I can understand the argument for a fixed temporal threshold.
> 
> I don’t follow at all here.

	Well the RACK RFC makes the same point, as I discovered later (https://tools.ietf.org/html/draft-ietf-tcpm-rack-04):

"From a network or link designer's viewpoint, parallelization (eg. link bonding) is
   the easiest way to get a network to go faster.  Therefore their main
   constraint on speed is reordering, and there is pressure to relax
   that constraint.  If RACK becomes widely deployed, the underlying
   networks may introduce more reordering for higher throughput.  But
   this may result in excessive reordering that hurts end to end
   performance:

   1.  End host packet processing: extreme reordering on high-speed
       networks would incur high CPU cost by greatly reducing the
       effectiveness of aggregation mechanisms, such as large receive
       offload (LRO) and generic receive offload (GRO), and
       significantly increasing the number of ACKs.

   2.  Congestion control: TCP congestion control implicitly assumes the
       feedback from ACKs are from the same bottleneck.  Therefore it
       cannot handle well scenarios where packets are traversing largely
       disjoint paths.

   3.  Loss recovery: Having an excessively large reordering window to
       accommodate widely different latencies from different paths would
       increase the latency of loss recovery."

I note that the benefit of reordering is all in the transport network, while the costs are all carried by the endpoints. With this kind of skewed incentives, what outcome do you expect. 


> 
>>>>> at least within some limits that we still have to find.
>>>>> That probably requires some evolution at the end-to-end transport implementation layer.  We are in a better position to make that happen than we have been for a long time.
>>>> 
>>>> 	Probably true, but also not very attractive from an end-user perspective…. unless this will allow transport innovations that will allow massively more bandwidth at a smallish latency cost.
>>> 
>>> The argument against in-network resequencing is mostly a latency argument (but, as a second order effect, that reduced latency may also allow more throughput), so, again, I don’t quite understand.
>> 
>> 	As I tried to show for TCP the flow with re-ordered packets certainly pays a latency cost that especially if re-ordering does not happen on the bottleneck link but at a faster link could be smaller.
> 
> I can’t parse this sentence, but my main point remains:
> 
> In-network resequencing increases latency (with a potential impact on throughput, too), unless it happens within a queue.  

	But this latency is not necessarily end-point visible latency, if a tree falls in a wood and no one is there to hear it, does it make a sound? 

> We wouldn’t want to do that, unless forced by a transport protocol that can’t cope.  If we can fix the transport protocols to enable (out-of-order) immediate forwarding, then let’s do it; this might also enable doing more in-network recovery, with the attendant performance improvements.

	If all of this does not increase the end-point visible latency and latency variation (too much) I am all for it, but if it does I maintain that the network should serve its users not the other way around (easy to say if one's position is pure end-user, and the complexity of making it happen falls onto others). 
Anyway, thanks for your time and arguments and information, that gives me something to think about.

Beste Gruesse
	Sebastian

> 
> Grüße, Carsten
>