Ouroboros Tutorial 09
In Tutorial 08, FRCT repaired a lossy flow, end to end, in the oping processes. This tutorial looks at the other half: how a Layer keeps its flows from overrunning the links it uses. That is the job of congestion avoidance, and in Ouroboros it does not run in the processes at the ends of a flow, but in the unicast IPCP, inside the Layer.
We use the setup and debug build of Tutorial 04, with both IPCPs on lo, and turn lo into a 10 Mbit/s link with tc. To load the link, we use ocbr, the Ouroboros constant bit rate tool, which can also send as fast as the Layer lets it.
Congestion avoidance in the IPCP
The flow allocator of a unicast IPCP keeps one controller per path: per destination address and QoS cube. Every flow to the same destination, in the same cube, shares it. The controller holds one rate for the path, and the packet scheduler of the IPCP holds each flow back until the moment the rate allows its next packet. Within the path, a fair-queueing tag per flow divides the rate between the flows.
The controller learns about congestion from the queue it fills. When the IPCP sends a packet, it writes the depth of its queue towards the next hop into the ecn byte of the DTP header, on a logarithmic scale. Along the path, each IPCP keeps the largest value, so the byte that arrives says how bad the worst queue was. The receiving IPCP averages the byte over a short window and reports it back to the sender in a flow update. The default policy, mb-ecn (multi-bit ECN), turns that report into a rate: it increases the rate while the queue is short, and decreases it in proportion to the congestion when it is not.
The policy is chosen per Layer when it is bootstrapped, with congestion in the configuration file or on the irm ipcp bootstrap command line. mb-ecn is the default, none turns congestion avoidance off.
The setup
Save the configuration file below as /etc/ouroboros/tut09.conf. It is the configuration of Tutorial 04, with the name ocbr instead of oping-server:
### Ouroboros Tutorial 09
[name.ocbr]
prog=["/usr/bin/ocbr"]
[unicast.uni-1]
bootstrap="unicast-layer"
autobind=true
eth=["lo"]
reg=["ocbr"]
[unicast.uni-2]
enrol={dst="unicast-layer", eth={}}
autobind=true
eth=["lo"]
conn=[{dst="uni-1", eth={}}]
The name has a program, but no args: we start the ocbr server ourselves, so that we can see its output. Create the client security configuration for the three names, and start the IRMd:
$ for n in unicast-layer uni-1 ocbr; do
> sudo mkdir -p /etc/ouroboros/security/client/$n
> printf 'auth=optional\nencryption=none\n' | sudo tee /etc/ouroboros/security/client/$n/sec.conf > /dev/null
> done
$ sudo irmd --stdout --config /etc/ouroboros/tut09.confIn another terminal, start the ocbr server as root, so that the client, which runs as a regular user, reaches it over the Layer:
$ sudo ocbr --listen
Server started, interval is 1 s, timeout is 1 s.Now limit lo to 10 Mbit/s with a hierarchical token bucket (HTB):
$ sudo tc qdisc replace dev lo root handle 1: htb default 1
$ sudo tc class replace dev lo parent 1: classid 1:1 htb rate 10mbitHTB does not drop a frame that comes in faster than the rate: it holds it back in the queue in front of lo. The Ethernet point of attachment of the sending IPCP reports that queue as its own, so the queue that builds up is one that the IPCP can measure. A shaper that drops frames instead would hide the queue from the controller.
One flow
Start an ocbr client that sends 1400-byte packets as fast as it can (--flood) for 20 seconds:
$ ocbr -n ocbr -f -s 1400 -d 20
Client started, duration 20, rate 1000000 b/s, size 1400 B.
sent statistics: 16406 packets, 22968400 bytes in 20002 ms, 9.1864 Mb/sThe rate in the first line is the default for the constant bit rate mode, and is not used with --flood. The client cannot send faster than the IPCP lets it: when the packet scheduler holds the flow back, the client's next write waits. The server prints what arrives every second:
Flow 64: 854 packets ( 1195600 bytes) in 1001 ms => 852.9287 pps, 9.5528 Mbps
Flow 64: 856 packets ( 1198400 bytes) in 1001 ms => 854.4560 pps, 9.5699 Mbps
Flow 64: 858 packets ( 1201200 bytes) in 1002 ms => 856.2199 pps, 9.5897 MbpsThat is 9.6 Mbit/s of payload. On the wire, every packet of 1400 bytes is a frame of 1435 bytes, with the Ethernet, PoA and DTP headers, so the flow fills the 10 Mbit/s link. The client's average is a little lower, because it includes the first second, in which the controller looks for the capacity of the path (slow start). The shaper shows the other half of the result:
$ tc -s qdisc show dev lo
qdisc htb 1: root refcnt 2 r2q 10 default 0x1 direct_packets_stat 0 direct_qlen 1000
Sent 23647864 bytes 17338 pkt (dropped 0, overlimits 10138 requeues 0)
backlog 0b 0p requeues 0overlimits counts the frames that HTB held back because the link was busy: the link was full. dropped is zero: the flow never sent more than the queue could hold.
Two flows, one controller
Now start two clients, each in its own terminal, for 30 seconds:
$ ocbr -n ocbr -f -s 1400 -d 30They split the link evenly. The two clients report:
Client started, duration 30, rate 1000000 b/s, size 1400 B.
sent statistics: 12876 packets, 18026400 bytes in 30003 ms, 4.8066 Mb/s
Client started, duration 30, rate 1000000 b/s, size 1400 B.
sent statistics: 13158 packets, 18421200 bytes in 30002 ms, 4.9120 Mb/sand the server, every second:
Flow 64: 430 packets ( 602000 bytes) in 1001 ms => 429.2754 pps, 4.8079 Mbps
Flow 65: 430 packets ( 602000 bytes) in 1003 ms => 428.5716 pps, 4.8000 Mbps
Flow 64: 428 packets ( 599200 bytes) in 1002 ms => 427.0992 pps, 4.7835 Mbps
Flow 65: 428 packets ( 599200 bytes) in 1001 ms => 427.3594 pps, 4.7864 MbpsBoth flows go to the same destination, uni-1, in the same QoS cube, so they share one controller in uni-2. The flow allocator of uni-2 has a file for each flow in the RIB, and the state of the controller shows up in both. While the clients run:
$ sudo grep -E 'Upstream|Paced|regime|capacity' /tmp/ouroboros/uni-2/flow-allocator/*
/tmp/ouroboros/uni-2/flow-allocator/66:Upstream congestion level: 246
/tmp/ouroboros/uni-2/flow-allocator/66:Paced rate (bytes/s): 1151180
/tmp/ouroboros/uni-2/flow-allocator/66:Current congestion regime: Proportional dec
/tmp/ouroboros/uni-2/flow-allocator/66:Path capacity (bytes/s): 1245184
/tmp/ouroboros/uni-2/flow-allocator/67:Upstream congestion level: 246
/tmp/ouroboros/uni-2/flow-allocator/67:Paced rate (bytes/s): 1149777
/tmp/ouroboros/uni-2/flow-allocator/67:Current congestion regime: Proportional dec
/tmp/ouroboros/uni-2/flow-allocator/67:Path capacity (bytes/s): 1245184The two flows show the same congestion level and the same regime, and, read a moment apart, the same paced rate: it is the state of the one controller of the path, seen from each flow. The paced rate is the rate of the path, 1.15 MB/s or 9.2 Mbit/s, and the fair-queueing tags give each flow half of it. The path capacity is the controller's estimate of the link, 1245184 bytes per second, or 9.96 Mbit/s. A controller per flow, as in TCP, would give each flow its own loop, and a source that opens more flows would get more of the link; here, more flows to the same destination share the same rate.
The congestion regime is one of five: slow start while it looks for the capacity, then additive inc while the queue is short, proportional dec when the flow updates report congestion, source limited when the flows do not use their rate, and increase held when the queue reaches the point where the controller only decreases. With greedy flows, it alternates between increase and decrease.
What the controller sees
Capture a few seconds of the traffic on lo while the two clients run:
$ sudo tcpdump -i lo -s 128 -x ether proto 0xa000Most frames are 1435-byte data frames from uni-2. This is one of them, cut at 128 bytes:
16:24:40.142193 de:83:23:2e:c8:9b > 36:76:86:e3:9f:06, ethertype Unknown (0xa000), length 1435:
0x0000: 0002 0588 8619 7b24 bc00 3c0a 5142 0000
0x0010: 00fb 5e91 a200 0000 0000 0000 0000 0000
...After the 5-byte PoA header comes the DTP header of Tutorial 04: the address of uni-1 (19 7b 24 bc), the QoS cube (00) and the TTL (3c), and then two bytes that were zero in Tutorial 04. The ecn byte is 0a, 10. It is the depth of the queue in front of the link, as a quarter-log2 of the number of packets: each step up is a factor of 21/4, about 1.19, in queue depth, so 10 means a queue of about 210/4, 5.7 packets. The cap byte, 51 or 81, is the capacity of the link in the same kind of code: 81 is 1245184 bytes per second, the path capacity in the RIB.
Every 67 ms or so, a 113-byte frame comes back from uni-1. This is a flow update:
16:24:40.234485 36:76:86:e3:9f:06 > de:83:23:2e:c8:9b, ethertype Unknown (0xa000), length 113:
0x0000: 0002 005e f384 bd30 3800 3c18 0000 0000
0x0010: 0000 0000 0000 0000 0000 0000 00b6 c836
0x0020: 4b00 0000 4300 0000 0000 0000 0000 0000
0x0030: 0000 0000 0000 0000 0000 0000 0000 0000
0x0040: 0000 0000 0000 0000 0000 0000 0001 3751
0x0050: 0200 0000 0000 0000 0000 0000 0000 0000
0x0060: 0000 00It travels over the same data transfer flow, but its DTP header carries EID 0, which here belongs to the flow allocator of uni-2: the message is for the flow allocator itself, not for a flow. Its body is a 78-byte flow allocator message. Near the end, 01 37 is the ece field, 311: the average of the ECN byte over the last window, in units of 1/32, so 9.72. Then come the capacity code, 51 again, and the message code, 02, a flow update. Between the flow updates, you will also see the heartbeats of uni-2 and their acknowledgments, which the controller uses to measure the round-trip time of the path.[1]
The receiver averages over a window of about 16 packets, so the controller reacts to how the queue evolves, not to a single packet. A higher ece leads to a larger cut in the rate, up to half of it, instead of the fixed cut of a controller that only learns that a packet was lost. That is also why the shaper never drops: the controller sees the queue grow before it overflows.
A raw flow cannot opt out
The ocbr flows so far were raw flows: no FRCT, no retransmission, no flow control. Set the OCBR_QOS environment variable to msg to make the second client's flow reliable, and run two clients again:
$ ocbr -n ocbr -f -s 1400 -d 30
Client started, duration 30, rate 1000000 b/s, size 1400 B.
sent statistics: 12804 packets, 17925600 bytes in 30004 ms, 4.7795 Mb/s$ OCBR_QOS=msg ocbr -n ocbr -f -s 1400 -d 30
Client started, duration 30, rate 1000000 b/s, size 1400 B.
OCBR_QOS=msg
sent statistics: 12602 packets, 17642800 bytes in 30002 ms, 4.7044 Mb/sFlow 64: 426 packets ( 596400 bytes) in 1001 ms => 425.5056 pps, 4.7657 Mbps
Flow 65: 411 packets ( 575400 bytes) in 1002 ms => 410.0025 pps, 4.5920 Mbps
Flow 64: 426 packets ( 596400 bytes) in 1003 ms => 424.6208 pps, 4.7558 Mbps
Flow 65: 410 packets ( 574000 bytes) in 1001 ms => 409.1992 pps, 4.5830 MbpsThe raw flow (flow 64 at the server) and the reliable flow (flow 65) share the link evenly. The reliable flow is a little slower, because each of its packets also carries the 16-byte FRCT header of Tutorial 08, and its acknowledgments use part of the link in the other direction. The raw flow has no end-to-end transport to hold it back, and it does not need one: it goes through the packet scheduler of uni-2 like any other flow. Both flows are in the best-effort QoS cube, so they share one controller, and get one share each.
This is the difference with the Internet, where congestion control lives in TCP, in the sender. A UDP flow does not take part, and a sender that does not want to back off does not have to. In a Layer, every packet goes through the IPCP, and the IPCP paces all of them.
The panels below show the three runs so far in Grafana, from the metrics exporter, with the flows named after the clients:
Flows arriving and leaving
A controller is judged on what happens when the number of flows changes. Start three clients, 15 seconds apart, that run for 75, 45 and 15 seconds:
$ ocbr -n ocbr -f -s 1400 -d 75
$ ocbr -n ocbr -f -s 1400 -d 45
$ ocbr -n ocbr -f -s 1400 -d 15The number of flows on the link goes from one, to two, to three, and back down to one, 15 seconds each. The clients report their average over their whole run:
sent statistics: 42151 packets, 59011400 bytes in 75001 ms, 6.2945 Mb/s
sent statistics: 17184 packets, 24057600 bytes in 45003 ms, 4.2766 Mb/s
sent statistics: 4303 packets, 6024200 bytes in 15005 ms, 3.2118 Mb/sThese are close to the averages of a fair split of 9.6 Mbit/s: the first client had the link to itself for 30 of its 75 seconds, half of it for 30 seconds and a third for 15, which averages to 6.4 Mbit/s. The second client had half for 30 seconds and a third for 15, 4.3 Mbit/s on average, and the third client had a third, 3.2 Mbit/s. And the shaper, at the end of all the runs of this tutorial:
$ tc -s qdisc show dev lo
qdisc htb 1: root refcnt 2 r2q 10 default 0x1 direct_packets_stat 0 direct_qlen 1000
Sent 266715968 bytes 241536 pkt (dropped 0, overlimits 178312 requeues 0)
backlog 0b 0p requeues 0Not a single drop, in 267 MB.
The link stays full through every change. A new flow does not have to push the others down by causing losses: it joins the controller of the path, and the fair-queueing tags give it its share at once. The Jain index in the last panel measures how evenly the flows share the path, from 1/n for a single flow taking everything to 1 for an even split. The exporter only computes it while more than one flow uses the path.
When you are done, remove the shaper:
$ sudo tc qdisc del dev lo rootTwo controllers
So far, every flow went from uni-2 to uni-1, in the best-effort cube, and all of them shared one controller. What divided the link between them was the fair-queueing tags inside that one path. The more interesting case is two controllers on the same link: two sources, each with its own path, to the same destination. Between two IPCPs there is only one path. For more, you need more IPCPs on more machines, or the namespace testbed of the integration test suite, which runs every node in its own network namespace, with its own IRMd, and connects the nodes with veth pairs.
The suite has a test for exactly this case, test_fairness_2src_asymmetric_counts. It builds four nodes in a fork: a and b send to d, through c, and the link from c to d is shaped to 10 Mbit/s with 1 ms of delay, with HTB on the sending side as in this tutorial. Source a opens one flow. Twenty seconds later, source b opens five.
With a controller per connection, as in TCP, b's five flows would take five sixths of the link: more connections, more bandwidth. With a controller per path, a and b each have one controller, and each gets half of the link; b's controller divides its half between its five flows. Run the test from a clone of the integration suite:
$ ./run_tests.sh --keep-state=~/testing --timeseries-poll-rate=500 "tests/ca/test_mb_ecn.py::test_fairness_2src_asymmetric_counts" -vIt takes about ten minutes: 30 seconds for the Layer to settle and 480 seconds of traffic, of which the test measures each flow between 120 and 400 seconds into its run. The per-test directory under ~/testing holds the logs, the RIB of every node halfway through and at the end, and the verdict, in asym_counts.json:
{
"qos": "raw",
"per_flow_mbps": {
"64": 4.821,
"65": 0.965,
"66": 0.966,
"67": 0.966,
"68": 0.966,
"69": 0.965
},
"source_a_mbps": 4.821,
"source_b_mbps": 4.827,
"aggregate_mbps": 9.648,
"per_source_jain": 1.0,
"per_flow_jain": 0.556
}Source a gets 4.82 Mbit/s with one flow, source b 4.83 Mbit/s with five, 0.97 Mbit/s each. The Jain index per source is 1.0. The Jain index per flow, 0.556, is low on purpose: the link is shared per path, not per flow. The two controllers do not know about each other. They only share the queue in front of the link at c, and each reads it from the ECN byte of its own packets, which c raises to the depth of its queue. Halfway through, their RIB shows each controller with a state of its own:
/tmp/ouroboros/n1.a/flow-allocator/66:Current congestion regime: Proportional dec
/tmp/ouroboros/n1.a/flow-allocator/66:Paced rate (bytes/s): 647779
/tmp/ouroboros/n1.a/flow-allocator/66:Upstream congestion level: 32
/tmp/ouroboros/n1.b/flow-allocator/66:Current congestion regime: Proportional dec
/tmp/ouroboros/n1.b/flow-allocator/66:Paced rate (bytes/s): 606796
/tmp/ouroboros/n1.b/flow-allocator/66:Upstream congestion level: 128and the shaper on c's link to d, at the end:
qdisc htb 1: root refcnt 33 r2q 10 default 0x1 direct_packets_stat 0 direct_qlen 1000
Sent 596739367 bytes 433107 pkt (dropped 0, overlimits 385357 requeues 0)
backlog 0b 0p requeues 0No drops, in 597 MB.
Watching it live
With the exporter and the Grafana dashboard of the Ouroboros Metrics page, the IPCP Congestion avoidance row shows the congestion regime, the congestion levels, the paced rate, the path capacity and the Jain index of every path, and the IPCP N+1 flows row the traffic of every flow. The flows are named after their flow ID, a 64-bit number; the panels in this tutorial name them after the clients instead.
Notes
- ↑ On lo, the frames in both directions share the same HTB queue, so the flow updates and the acknowledgments wait behind the data, and their own ECN byte is high (18, 24, in the flow update above). Over a real link, each direction has its own queue.