Piece of CAKE: A Comprehensive Queue Management Solution for Home Gateways
This web site contains the data files and test scripts for the paper “T. Høiland-Jørgensen et al. Piece of CAKE: A Comprehensive Queue Management Solution for Home Gateways”, which is under submission to the IEEE LANMAN 2018 conference.
Test setup
The tests are run in a controlled environment consisting of five regular desktop computers, equipped with Intel 82571EB ethernet controllers, and networked together in a daisy-chain configuration, corresponding to a common dumbbell scenario (here multiple senders correspond to the individual flows established between the endpoint nodes). The middle machine adds latency by employing the Linux ‘netem’ qdisc. The bottleneck routers both run CAKE, in bandwidth shaping mode set according to the bandwidths reported in the dataset.
For all tests, the default Linux CUBIC TCP implementation is used. The endpoints and latency inducing box run a vanilla Linux 4.11 kernel from kernel.org, while the bottleneck routers run Linux 4.14. The 16d7fed7ea0ef528d138cb7295aa51f55680ceef commit was used for CAKE.
Test utilities
The tests are run through the Flent testing tool and its batch mode. The batch file is included in the data file below.
A recent version (2.6 or newer) of Netperf is required to run the tests. The IRTT tool is used for the VoIP and UDP latency measurements.
Hash collision probabilities
The graph of hash collision probabilities shown in the paper was computed from an analytical expression derived by Anil K Agarwal. The analysis is replicated below. The numerical example is included in the following spreadsheet:
- hash-analysis.ods (44 KiB; sha1sum da2ddb2a6d348d12fd5d79ec1713fdbb74dfb608)
Hash Collission Analysis
Anil K Agarwal
ViaSat Inc.
Problem Description
Consider a hash table organized as an array of N bins (or buckets),
with hash chaining, i.e., each bin contains a list of items that hash
to that array position.
Let H(k) be a hash function, which maps a key k to an index value 0 to N-1.
Consider M items with key values k[i], i = 0 to M-1,
that are added to the hash table, by computing index = H(k[i]) and
adding the item to the bin at index H(k[i]).
Compute the expected number of bins with x items in the bin chain,
(i.e., bin chain size = x), x = 0, 1, 2, ... M
Analysis
1. x = 0
Probability that any item does not hash to bin i = (1 - 1/N)
Probability that none of the M items hash to bin i = (1 - 1/N) ^ M
Probability that bin i contains 0 items = (1 - 1/N) ^ M
Expected number of bins with 0 items = N * (1 - 1/N) ^ M
2. x = 1
Probability that a specific item hashes to index i = 1/N
Probability that no other item hashes to index i = (1 - 1/N) ^ (M - 1)
Number of choices of items that is selected to be in bin i = C(M, 1) = M
Probability that bin i contains 1 item = 1/N * (1 - 1/N) ^ (M - 1) * C(M, 1)
Expected number of bins with 1 item = N * 1/N * (1 - 1/N) ^ (M - 1) * C(M, 1)
C(M, x) is the combinatorial function = M! / (x! * (M-x)!)
3. x = 2
Probability that 2 specific items hash to index i = (1/N)^2
Probability that no other item hashes to index i = (1 - 1/N) ^ (M - 2)
Number of choices of items that are selected to be in bin i = C(M, 2) = M * (M - 1)/2
Probability that bin i contains 2 items = (1/N)^2 * (1 - 1/N) ^ (M - 2) * C(M, 2)
Expected number of bins with 2 items = N * (1/N)^2 * (1 - 1/N) ^ (M - 2) * C(M, 2)
4. x = x
Generalizing the previous set of equations, we get -
Expected number of bins with x items = N * (1/N)^x * (1 - 1/N) ^ (M - x) * C(M, x)
bins(x) = N * (1/N)^x * (1 - 1/N) ^ (M - x) * C(M, x) (1)
Data files
The following file contains the Flent data files for all tests, as well as the batch file used to run them:
- cake-paper-20180420-flent-data.tar.gz (450 MiB; sha1sum 48ca2beabc9a117ba93cafe6d5928fbec3aca25c).
CAKE Source code
The CAKE source code is available on Github and builds as a standalone module for Linux. The companion user-space iproute2 tool is in its own repository.
Contact
This page written and maintained by Toke Høiland-Jørgensen. Questions, comments, etc. are very welcome on toke AT toke DOT dk.