[Ecn-sane] [tsvwg] per-flow scheduling

[David P. Reed]

Good point, but saturation is not congestion, in my view. Optimal state of a single bottleneck link is a queue of length <= 1. This can be maintained even under full load, by endpoint rate control. (Note that the "Little's Law" result in queueing theory is for a special case of queuing due to uncontrolled Poisson random arrivals. The traffic you refer to, downloading an update, is about as far from Poisson-random as possible. It's neither random nor Poisson).
 
But I take your point that there will be bottlenecked links that are special, and thus congestion control comes into play on those links.
 
per-flow scheduling is appropriate on a shared link. However, the end-to-end argument would suggest that the network not try to divine which flows get preferred.
And beyond the end-to-end argument, there's a practical problem - since the ideal state of a shared link means that it ought to have no local backlog in the queue, the information needed to schedule "fairly" isn't in the queue backlog itself.  If there is only one packet, what's to schedule?
 
In fact, what the ideal queueing discipline would do is send signals to the endpoints that provide information as to what each flow's appropriate share is, and/or how far its current share is from what's fair. A somewhat less optimal discipline to achieve fairness might also drop packets beyond the fair share. Dropping is the best way to signal the endpoint that it is trying to overuse the link.
 
Merely re-ordering the packets on a link is just not very effective at achieving fairness.
 
Now what to do to determine fair share if the average number of packets in a saturated link's queue is <= 1?
 
Well, presumably the flows have definable average rates. So  good statistical estimators of the average rate of each flow exist. For example a table with a moving average of the rate of bytes on each flow can be maintained, which provides wonderful information about the recent history of capacities used by each flow. This allows signalling of overuse to the endpoints of each flow, either by dropping packets or by some small number of bits (e.g. ECN marking). Underuse can also be signalled.
 
We know (from pragmatic observation) that flows defined as source-host, dest-host pairs, have relatively stable demand over many packets, and many RTT's.  More specific flows (say, defined using TCP and UDP ports, the "extended header" that maybe should have been included in the IP layer) are less stable in some protocol usages we see.
 
However, what's clear is that something like fq_codel can be created that does not need to accumulate long queues on links to have an effect - obviously queues still result from transient overload, but one wants to avoid requiring queueing to build up in order to balance traffic fairly.
 
Ideally, in a situation where some definition of fairness needs to be implemented among flows competing for a limited resource, the queueing should build up at the source endpoint as much as possible, and yet the point where the conflict occurs may be deep within the network of networks.  However, once we start being able to balance loads across many independent paths (rather than assuming that there is exactly one path per flow), the definition of "fairness" becomes FAR more complicated, because the competing flows may not be between a particular source and destination pair - instead the traffic in each flow can be managed across different sets of multipaths.
 
So the end-to-end approach would suggest moving most of the scheduling back to the endpoints of each flow, with the role of the routers being to extract information about the competing flows that are congesting the network, and forwarding those signals (via drops or marking) to the endpoints. That's because, in the end-to-end argument that applies here - the router cannot do the entire function of managing congestion or priority.
 
The case of the "uplink" from a residential network is a common, but not general case. Once a residence has multiple uplinks (say in a Mesh neighborhood network or just in a complex wireless situation where multiple access points are reachable) the idea of localizing priority or congestion management in one box below the IP layer no longer works well at all.
 
On Saturday, June 22, 2019 4:47pm, "Jonathan Morton" <chromatix99 at gmail.com> said:



> > On 22 Jun, 2019, at 10:50 pm, David P. Reed <dpreed at deepplum.com>
> wrote:
> >
> > Pragmatic networks (those that operate in the real world) do not choose to
> operate with shared links in a saturated state. That's known in the phone business
> as the Mother's Day problem. You want to have enough capacity for the rare
> near-overload to never result in congestion.
> 
> This is most likely true for core networks. However, I know of several real-world
> networks and individual links which, in practice, are regularly in a saturated
> and/or congested state.
> 
> Indeed, the average Internet consumer's ADSL or VDSL last-mile link becomes
> saturated for a noticeable interval, every time his operating system or game
> vendor releases an update. In my case, I share a 3G/4G tower's airtime with
> whatever variable number of subscribers to the same network happen to be in the
> area on any given day; today, during midsummer weekend, that number is
> considerably inflated compared to normal, and my available link bandwidth is
> substantially impacted as a result, indicating congestion.
> 
> I did not see anything in your argument specifically about per-flow scheduling for
> the simple purpose of fairly sharing capacity between flows and/or between
> subscribers, and minimising the impact of elephants on mice. Empirical evidence
> suggests that it makes the network run more smoothly. Does anyone have a concrete
> refutation?
> 
> - Jonathan Morton
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.bufferbloat.net/pipermail/ecn-sane/attachments/20190622/f1ae48ac/attachment-0001.html>