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.

DOI

Test setup

Physical test setup.

Figure 1

Physical 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 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 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.