# WF-UNet: Weather Fusion UNet for Precipitation Nowcasting

Christos Kaparakis2, Siamak Mehrkanoon 231
<EMAIL_ADDRESS><EMAIL_ADDRESS>*Corresponding author. 2 Department of Advanced Computing Sciences, Maastricht
University, Maastricht, Netherlands  3 Department of Information and Computing
Sciences, Utrecht University, Utrecht, Netherlands

###### Abstract

Designing early warning systems for harsh weather and its effects, such as
urban flooding or landslides, requires accurate short-term forecasts
(nowcasts) of precipitation. Nowcasting is a significant task with several
environmental applications, such as agricultural management or increasing
flight safety. In this study, we investigate the use of a UNet core-model and
its extension for precipitation nowcasting in western Europe for up to 3 hours
ahead. In particular, we propose the Weather Fusion UNet (WF-UNet) model,
which utilizes the Core 3D-UNet model and integrates precipitation and wind
speed variables as input in the learning process and analyze its influences on
the precipitation target task. We have collected six years of precipitation
and wind radar images from Jan 2016 to Dec 2021 of 14 European countries, with
1-hour temporal resolution and 31 square km spatial resolution based on the
ERA5 dataset, provided by Copernicus, the European Union’s Earth observation
programme. We compare the proposed WF-UNet model to persistence model as well
as other UNet based architectures that are trained only using precipitation
radar input data. The obtained results show that WF-UNet outperforms the other
examined best-performing architectures by 22%, 8% and 6% lower MSE at a
horizon of 1, 2 and 3 hours respectively.

###### Index Terms:

UNet, Precipitation Nowcasting, Cloud Cover Nowcasting, Deep Learning

##  I Introduction

Heavy rainstorms can impact people’s daily lives negatively. In 2017, the WMO
(World Meteorological Organization)investigated the impact of precipitation
extremes, in terms of both excess and deficient rainfall
111https://public.wmo.int/en/media/news/rainfall-extremes-cause-widespread-
socio-economic-impacts. Thousands of people died and were displaced due to
flooding and landslides in many countries worldwide. These disruptions had
widespread socio-economic impacts. Therefore, it would be advantageous to
forecast these weather events in advance so that decision-makers can take
steps to safeguard lives, properties and wealth.

Computational weather forecasting is an integral feature of modern,
industrialized societies. It is used for planning, organization and managing
many personal and economic aspects of life. Many industries such as
agriculture [1], mining [2] and construction [3] rely on weather forecasts to
make decisions, and if climatological events occur that are unexpected, this
can lead to significant economic losses. Similarly, accurate weather forecasts
improve flight and road safety and help foresee potential natural disasters.
In precipitation nowcasting, one attempts to provide a short-range forecast of
rainfall intensity based on radar echo maps, rain gauges and other observation
data [4]. Precipitation nowcasting is an important task because of its immense
impact, for instance, in predicting road conditions [5] and enhancing flight
safety by providing weather guidance for regional aviation [6]. Furthermore,
it can help with flood mitigation, water resource management [7] and avoiding
casualties by issuing citywide rainfall alerts [8].

Forecasting weather generally relies on Numerical Weather Prediction (NWP)
[9], methods based on mathematical formulations using several atmospheric
features. Although NWP is a powerful method for such forecasting tasks, it
also has drawbacks as it requires too much computational power [10]. In
addition, forecasting with NWP may be sensitive to noise present in the
measurements of weather variables [11, 12]. NWP models may take hours to run
and are also less accurate than persistence-based forecasts on less than 4
hour predictions [13, 14]. In recent years, the enormous amount of ever-
increasing weather data has stimulated research interest in data-driven
machine learning techniques for nowcasting tasks [15, 16, 17, 18, 19, 20].
Unlike the model-driven methods, data-driven models do not base their
prediction on the calculations of the underlying physics of the atmosphere.
Instead, they analyze and learn from historical weather data such as past wind
speed and precipitation maps to predict the future. By taking advantage of
available historical data, data-driven approaches have shown better
performance than classical ones in many forecasting tasks [13, 14].

Recent advances in Artificial Neural Network architectures (ANNs) have
demonstrated great potential in precipitation nowcasting tasks [21, 22, 23,
24]. The critical difference between NWP and ANNs is that the former is model-
driven, and the latter is a data-driven approach [25, 20, 26]. While classical
machine learning techniques rely on handcrafted features and domain knowledge,
deep learning techniques automatize the extraction of those features [27].
Deep learning techniques have demonstrated remarkable results in several
domains such as biomedical signal analysis, healthcare, neuroscience and
dynamical systems, among others [28, 18, 29, 30, 31]. Due to underlying
complex dynamics of weather data, ensuring accurate nowcasting at several
temporal-spatial levels is a challenging task. Deep learning based models have
recently received much attention in this area because of their powerful
abilities to learn spatiotemporal feature representations in an end-to-end
fashion [20, 32, 33, 21]. UNet, one of the successful deep learning
architectures, which was originally proposed for image segmentation task, have
shown promising results in various domains such as precipitation nowcasting,
background detection in video analysis and image super-resolution [20, 34, 32,
35, 36, 33]. It consists of a contracting path to extract features, and an
expanding path, to reconstruct a segmented image, with a set of residual
connections between them to enable precise localization.

Most of the current state-of-the-art deep learning based models use only the
past precipitation radar images to predict the future precipitations [21, 25,
20, 32]. However, classical weather forecasting which generally rely on
Numerical Weather Prediction (NWP), uses several atmospheric features (weather
variables). Generally, it is common for measurements from different modalities
to carry complementary information about various aspects of a particular
activity [37]. Therefore, data-driven models that combine data from multiple
sources can potentially provide more accurate inferences. This research aims
to develop a novel architecture that can incorporate multiple weather
variables such as past precipitation together with wind speed, as input to
more accurately forecast the precipitation. This paper is organized as
follows. A brief overview of the related research works is given in Section 2.
Section 3 introduces the proposed WF-UNet model. The data description and used
preprocessing steps are explained in Section 4. The experimental setup and and
evaluation of the models are given in Section 5. The obtained results are
discussed in Section 6 and the conclusion is drawn in Section 7.

##  II Related Work

In recent years, data-driven models have gained much attention for predicting
weather elements such as temperature, wind speed and precipitation [32, 38,
28, 12]. Due to the vast amount of available weather data and the fact that
weather element forecasting can be formulated as a sequence prediction
problem, deep neural networks architectures such as Recurrent Neural Network
(RNN) [17], Long Short-Term Memory (LSTM) [21] and Convolutional Neural
Network (CNN) [39] among others are suitable candidates to address various
problems in this field. In particular, CNN architectures have shown their
excellent ability to handle 2D and 3D images. Moreover, thanks to the
versatility of CNNs, nowcasting problems can be tackled in different fashions.
For instance, the authors in [40] and [15] treated the multiple timesteps as
multiple channels in the network. This way, they could apply a 2D-CNN to
perform the predictions. The authors in [25] also treated the multiple
timesteps as depth in the samples and applied a 3D-CNN and approximate more
complex functions. The authors in [21], introduced an architecture that
combines both CNN’s and RNN’s strengths to be able to more efficiently work
with image data as well as capturing long-range dependencies for the
precipitation nowcasting task. Hybrid models like in [41] replace the fully-
connected LSTM with ConvLSTM to better capture the spatiotemporal
correlations. In [21], the network predicted raw pixels directly rather than
predicting the transformation of the input frame whereas [42] predicted
transformed pixels instead. In [4, 20, 15], the authors show the successful
application of UNet model in precipitation task due to its autoencoder-like
architecture and ability to tackle image-to-image translation problems.

Figure 1: The Core UNet encoder-decoder network. A multi-channel feature map
is represented by each cube in the figure. Numbers on the top-right of a cube
indicate the number of channels, while numbers on the left of a cube indicate
the resolution. Note that at each level of the architecture, the feature maps
have the same resolution. The input is the ground truth of a sequence of
precipitation maps, whereas the output is the corresponding prediction map
produced by the model.

The SmaAt-UNet model, an extension of the UNet model, which significantly
reduces the UNet parameters without compromising its performance, is
introduced in [20]. Finally, the authors in [18] introduced Broad-UNet by
equipping the UNet model with asymmetric parallel convolutions and the Atrous
Spatial Pyramid Pooling (ASPP) module. Despite its many advantages, UNet can
still result in limited abilities when modelling long-range dependencies due
to the intrinsic locality of the convolution-based operations.

In [19], the researchers propose another variation of the UNet model, the
TransUNet. CNN-Transformer is used as an encoder in TransUNet, whereas the
original UNet decoder is used as a decoder. There has been success in applying
this model to medical image segmentation tasks. Finally, in [33], the
researchers propose another variation of the UNet model, the AA-TransUNet. A
pair of key elements are added to extend TransUNet: Convolutional Block
Attention Modules (CBAM) and Depthwise-separable Convolutions (DSC).
Therefore, the model can explore the inter-channel and inter-spatial
relationships of features by performing both channel-wise and spatial-wise
attention.

##  III Proposed Model

This section introduces our proposed WF-UNet model which adopts a variation of
the original UNet architecture as its core building block and combines it with
a data fusion strategy in order to incorporate two different weather
variables.

###  III-A Core UNet model

Compared to the original UNet [43], here 3D Convolution layers are used. These
convolutions can not only capture the spatial information contained within one
radar image, but the spatial information of an image with its previous
timesteps, i.e., the temporal information. Fig. 1 outlines the architecture of
the used Core UNet model which consists of the encoder and an decoder paths.
As shown in Fig. 1, the model includes five consecutive levels in each path
with the following operations: double 3D convolution (blue arrows), dropout
and spatial pooling (pink arrows), upsampling (yellow arrows) and finally
feature concatenation (dotted rectangles). The last layer of the model is a
$1\times 1$ 3D convolution (green arrow), which produces a single feature map
that represents the prediction results.

###  III-B Weather Fusion UNet (WF-UNet)

We propose the Weather Fusion UNet (WF-UNet) model for the precipitation
nowcasting task. In contrast to other UNet based model which use only
precipitation maps as input for precipitation nowcasting, here the proposed
model utilizes past precipitation as well as wind speed radar images as input.
In particular, the proposed WF-UNet architecture, shown in Fig. 2, is composed
of two separate core UNet streams. Two different weather variable inputs,
i.e., precipition and wind speed radar images, pass through the two streams.
Here, the network processes the precipitation and wind speed images separately
and then fuse the extracted features from both streams at the later decision-
making stage. This architectural design is intended to address intrinsic
differences between information captured in precipitation and additional radar
data by encouraging each stream to learn informative features from the
respective sensor separately before combining the features. The fusion is
implemented via concatenating along the depth axis of the Core UNet outputs,
followed by a convolutional layer. Similar to UNet, WF-UNet outputs values
between 0 and 1 by applying a 3D convolution with a 1x1 kernel and a
subsequent linear activation function in the final layer.

Figure 2: The architecture of WF-UNet. Two different inputs (i.e. precipition
and wind speed radar images) pass through two separate but identical Core UNet
streams. The outputs of those streams are then concatenated (late/decision-
level fusion). Lastly, a final 3D convolution with a 1x1 kernel and a linear
activation function are applied to produce the final output.

##  IV Data description and preprocessing

Here, we provide an overview of the dataset adopted for this research. we have
selected a subset of the ERA5 dataset [44], which includes observations of
total precipitation and wind speed at the same resolution, coordinates and
measurement interval.

Figure 3: The study area framed in red.

The ERA5 dataset is provided by the European Centre for Medium-Range Weather
Forecasts (ECMWF) through the Copernicus Climate Change Service (C3S). Through
C3S, scientists combine observations of the climate system with the latest
scientific findings to produce authoritative, quality-assured information
about Europe’s past, present, and future meteorologic conditions. The
measurements of the selected weather variables come in grid radar images with
31 square kilometres per pixel resolution. Images from this region cover much
of the western part of Europe within the given latitude and longitude
coordinates. More specifically the study area includes all or part of 14
countries: Andorra, Belgium, Denmark, France, Germany, Ireland, Italy, Monaco,
the Netherlands, Portugal, Spain, Switzerland, Luxembourg and the United
Kingdom.

Figure 4: The dataset radar images for the different weather variable. The
countries and coast outlines are included for visualization purposes only.

The collected dataset covers a six-year period, from 2016 to 2021, with hourly
measurements. Fig. 3 and 4 display the geographical area we are considering
and image examples of the two selected variables respectively. The Total
Precipitation is the accumulated liquid and frozen water that falls to the
Earth’s surface, comprising rain and snow. The values of each pixel represent
the accumulated amount of rainfall in the last hour one 31 square kilometer.
The ERA5 dataset provides the $u$ and $v$ components of wind, i.e., eastward
and northward components, measured at a height of 100 metres above the surface
of the Earth, in metres per second. Given the $u$ and $v$ components, the wind
speed of the wind vector $V$ is determined by $\sqrt{u^{2}+v^{2}}$.

The collected raw radar maps have a dimension of $105\times 173$ and one pixel
corresponds to the accumulated rainfall or mean wind speed in the last hour on
31 square kilometers. As a data preparation step, we divided the values
(separately for each weather variable) of both the training and testing set by
the highest occurring value in the training set to normalize the data.
Furthermore, we cropped the images to $96\times 96$.

Dataset | Rain Pixels | Training | Validation | Test | Subset
---|---|---|---|---|---
Original | No Extraction | 39,463 | 4,384 | 8,760 | 100%
EU-20 | 20% pixels | 38,906 | 4,322 | 8,677 | 98%
EU-50 | 50% pixels | 25,832 | 2,870 | 3,731 | 65%

TABLE I: Comparison of the dataset sizes. The original dataset has a lot of
images with little to no rain. (The Subset percentages are calculated based on
the Training Set sizes. Figure 5: Example of the EU-50 dataset over 6
timesteps. The first row displays Total Precipitation radar images while the
second row Wind Speed radar images.

There is a contrast in the number of pixels showing rainfall compared to those
not. Therefore, following the lines of [20] and [18], we created two
additional datasets, i.e., EU-50 and EU-20, whose images have at least 50% and
20% of rain in the pixels respectively. We split the dataset into a training
set (years 2016-2020) and a testing set (year 2021). Additionally, for every
training iteration, a validation set is created by randomly selecting 10% of
the training set. A comparison of different sample sizes of the three datasets
can be found in Table I. The EU-50 dataset is used to train and test the
models. Additionally we used the test set of EU-20 to compare the
generalization performance of the trained models. Fig. 5 shows an example of
EU-50 dataset over 6 hours.

##  V Experimental setup and evaluation

The data is arranged so that the resulting inputs of total precipitation
$I_{tp}$ and wind speed $I_{ws}$ are three dimensional array, i.e.,
$I_{tp},I_{ws}\in R^{TxHxW}$. Here, $T$ is the number of lags or previous time
steps corresponding to the time dimension. $H$ and $W$ refer to the size of
the image and make up the spatial dimensions. TensorFlow is used to implement
the models and train and evaluate them on the given dataset.

We aim at nowcasting precipitation map for one to three hours ahead. The
number of previous time-steps (lag) is set to 12, which is empirically found
to be the best among the tested lag values. The height and width of the images
are 96 and 96. The model receives $I_{tp}$ and $I_{ws}$ inputs of shape
$(12,96,96)$ and output of shape $(1,96,96)$. The Mean Squared Error (MSE) is
used as the loss function and is optimized using Adam optimizer with an
initial learning rate of 0.0001. In addition, the batch size and the dropout
rate are set to 2 and 0.5, respectively. All previously described models were
trained for a maximum of 200 epochs. We employed an early stopping criterion
which stopped the training process when the validation loss did not increase
in the last 15 epochs. Additionally, we used a learning rate scheduler that
reduced the learning rate to a half of the previous learning rate when the
validation loss did not increase for four epochs. Here, we use MSE as the
primary metric to assess the model performance. Furthermore, we also include
additional metrics such as accuracy, precision and recall. Following the lines
of [20], we first create a binarized mask of the image according to a
threshold to calculate these new metrics. This threshold is the mean value of
the training set from the EU-50 dataset. Hence, any value equal to or above
the threshold (0.0047) is replaced by 1, and any value below it is replaced by
0. The models are trained on a single NVIDIA Tesla V100 with 32Gb of VRAM.

##  VI Results and Discussion

We compare the performance of our WF-UNet model with four other models, i.e.,
the persistence model, core UNet [43], AsymmetricInceptionRes3DDR-UNet [32]
and Broad-UNet [20]. The models all trained using training set of EU-50 data
and tested over the test sets of both EU-50 and EU-20 datasets. The MSE is the
main metric used for this comparison and is calculated over the denormalized
data. Three additional metrics , i.e., accuracy, precision and recall are also
computed over the binarized data, as described in section 5. The performance
of different models on the EU-50 and EU-20 test datasets are shown in Table II
and III respectively.

TABLE II: Test MSE and additional metrics values for the precipitation
nowcasting obtained using the EU-50 dataset.

Model | MSE | Accuracy | Precision | Recall
---|---|---|---|---
1-hour ahead prediction |  |  |  |
Persistence | 7.68e-03 | 0.916 | 0.803 | 0.8
Core UNet | 3.18e-04 | 0.862 | 0.698 | 0.833
AsymmInceptionRes-3DDR-UNet | 3.28e-04 | 0.859 | 0.710 | 0.781
BroadU-Net | 3.24e-04 | 0.86 | 0.705 | 0.795
WF-UNet | 2.50e-04 | 0.921 | 0.803 | 0.849
2-hour ahead prediction |  |  |  |
Persistence | 1.56e-02 | 0.876 | 0.704 | 0.697
Core UNet | 5.02e-04 | 0.813 | 0.609 | 0.796
AsymmInceptionRes-3DDR-UNet | 5.11e-04 | 0.821 | 0.639 | 0.728
BroadU-Net | 5.05e-04 | 0.819 | 0.638 | 0.712
WF-UNet | 4.62e-04 | 0.877 | 0.684 | 0.813
3-hour ahead prediction |  |  |  |
Persistence | 2.19e-02 | 0.861 | 0.680 | 0.672
Core UNet | 6.71e-04 | 0.800 | 0.612 | 0.657
AsymmInceptionRes-3DDR-UNet | 6.45e-04 | 0.787 | 0.583 | 0.678
BroadU-Net | 6.55e-04 | 0.806 | 0.637 | 0.609
WF-UNet | 6.31e-04 | 0.855 | 0.647 | 0.743

TABLE III: The obtained MSE and additional metrics values for the
precipitation nowcasting on the EU-20 test dataset.

Model | MSE | Accuracy | Precision | Recall
---|---|---|---|---
1-hour ahead prediction |  |  |  |
Persistence | 1.85e-02 | 0.932 | 0.787 | 0.787
Core UNet | 2.97e-04 | 0.863 | 0.698 | 0.837
AsymmInceptionRes-3DDR-UNet | 3.07e-04 | 0.861 | 0.710 | 0.786
BroadU-Net | 3.05e-04 | 0.861 | 0.706 | 0.803
WF-UNet | 2.67e-04 | 0.933 | 0.790 | 0.847
2-hour ahead prediction |  |  |  |
Persistence | 3.71e-02 | 0.897 | 0.680 | 0.680
Core UNet | 5.02e-04 | 0.813 | 0.609 | 0.796
AsymmInceptionRes-3DDR-UNet | 5.11e-04 | 0.821 | 0.639 | 0.728
BroadU-Net | 5.05e-04 | 0.819 | 0.638 | 0.712
WF-UNet | 4.87e-04 | 0.895 | 0.664 | 0.807
3-hour ahead prediction |  |  |  |
Persistence | 4.99e-02 | 0.874 | 0.605 | 0.606
Core UNet | 6.71e-04 | 0.800 | 0.612 | 0.657
AsymmInceptionRes-3DDR-UNet | 6.45e-04 | 0.787 | 0.583 | 0.678
BroadU-Net | 6.55e-04 | 0.806 | 0.637 | 0.609
WF-UNet | 6.34e-04 | 0.877 | 0.626 | 0.736

Figure 6: Average test MSE over all three timesteps ahead.

From the obtained results, one can observe that our proposed WF-UNet model
performs consistently better than all the other models for both EU-50 and
EU-20 datasets and over different timestep ahead. From Table II, one can
notice that the largest difference in performance of WF-UNet compared to the
next best performing model is for the 1-hour ahead prediction. As the number
of step-ahead increases, the gap between the performance of the proposed WF-
UNet and the other examined models decreases. Fig. 6, shows the average MSE
obtained using the ground truth and the nowcasts for all three timesteps
ahead. One can note that the proposed WF-UNet outperforms the other tested
models.

Figure 7: WF-UNet precipitation nowcasts examples. The images in the left side
are generated with the test set from the dataset containing at least 20% of
rain pixels (EU-20). The images in the right side are generated with the test
set from the dataset containing at least 50% of rain pixels (EU-50). Figure 8:
Feature maps outputted from the two streams before they are concatenated in
the Decision-level Fusion stage. The first row represents the output of the
Precipitation stream, while the second row the output of the Wind Speed
stream.

Two precipitation nowcasting examples are shown in Fig. 7. The example on the
left side is taken from the test set of the EU-20 dataset. The example on the
right side is taken from the test set of the EU-50 dataset. As can be seen,
the sample image of EU-50 has significantly more rain pixels than that of
EU-20. Following the results from Tables II and III, the 1-hour ahead
predictions in Fig. 7 appear to be the most similar to the ground truth image
and as the hours ahead prediction increases the similarity between the
nowcasts and the ground truth image decreases. Fig. 8 shows an example of the
learned feature maps for the two streams of WF-UNet model. The image fed to
the network is the ground truth image previously shown in Figure 7. We can
observe that different features have been extracted, some with more details
than others. The obtained results show that the inclusion of multiple features
such as precipitation and wind speed maps allows the WF-UNet to obtain more
precise nowcasts. Furthermore, the decision-level fusion approach allows the
network to process the two images separately and then fuse the extracted
features from both streams at the later decision-making stage. With this
approach, we can observe a 22% and an 11% improvement to the core UNet on both
datasets for the 1-hour ahead predictions. The binarized predictions of the
WF-UNet are 6% more accurate than the core UNet for 1-hour and 2-hour ahead
predictions and 5% more accurate for 3-hours ahead predictions. This means
that WF-UNet is better than current state-of-the-art models at predicting the
position of precipitation pixels in the image. Since the model aims to perform
a regression of each pixel with a wide range of values, achieving accurate
forecasting or equivalently lower MSE values is more desirable than having
good binary accuracy only. That is where our approach shows superior
performance to the previous state-of-the-art models.

##  VII Conclusion

The WF-UNet, an extension of the UNet architecture, is introduced for
precipitation nowcasting up to three hours ahead. The model incorporates and
learns from wind speed and precipitation variables using two streams. The
learned features of both streams are then fused before reaching to the output
of the model. The use of decision-level fusion helps to capture the
spatiotemporal information of past radar images better than the classical UNet
model. Compared to other tested UNet-based models, WF-UNet extracts features
more efficiently, making its predictions more accurate in short-term
nowcasting.

## References

  * [1] M. Bendre, R. Thool, and V. Thool, “Big data in precision agriculture: Weather forecasting for future farming,” in _2015 1st International Conference on Next Generation Computing Technologies (NGCT)_. IEEE, 2015, pp. 744–750.
  * [2] S. Bag, M. S. Rahman, G. Srivastava, H.-L. Chan, and D. J. Bryde, “The role of big data and predictive analytics in developing a resilient supply chain network in the south african mining industry against extreme weather events,” _International Journal of Production Economics_ , vol. 251, p. 108541, 2022.
  * [3] I. Hazyuk, C. Ghiaus, and D. Penhouet, “Optimal temperature control of intermittently heated buildings using model predictive control: Part i–building modeling,” _Building and Environment_ , vol. 51, pp. 379–387, 2012.
  * [4] V. Lebedev, V. Ivashkin, I. Rudenko, A. Ganshin, A. Molchanov, S. Ovcharenko, R. Grokhovetskiy, I. Bushmarinov, and D. Solomentsev, “Precipitation nowcasting with satellite imagery,” in _Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining_, 2019, pp. 2680–2688.
  * [5] M. Kilpeläinen and H. Summala, “Effects of weather and weather forecasts on driver behaviour,” _Transportation research part F: traffic psychology and behaviour_ , vol. 10, no. 4, pp. 288–299, 2007.
  * [6] J. Van Belle, J. Shamoun-Baranes, E. Van Loon, and W. Bouten, “An operational model predicting autumn bird migration intensities for flight safety,” _Journal of applied ecology_ , vol. 44, no. 4, pp. 864–874, 2007.
  * [7] D. Schwanenberg, F. M. Fan, S. Naumann, J. I. Kuwajima, R. A. Montero, and A. Assis dos Reis, “Short-term reservoir optimization for flood mitigation under meteorological and hydrological forecast uncertainty,” _Water Resources Management_ , vol. 29, no. 5, pp. 1635–1651, 2015.
  * [8] J. Thielen, J. Bartholmes, M.-H. Ramos, and A. De Roo, “The european flood alert system–part 1: concept and development,” _Hydrology and Earth System Sciences_ , vol. 13, no. 2, pp. 125–140, 2009.
  * [9] P. Bauer, A. Thorpe, and G. Brunet, “The quiet revolution of numerical weather prediction,” _Nature_ , vol. 525, no. 7567, pp. 47–55, 2015.
  * [10] S. Al-Yahyai, Y. Charabi, and A. Gastli, “Review of the use of numerical weather prediction (nwp) models for wind energy assessment,” _Renewable and Sustainable Energy Reviews_ , vol. 14, no. 9, pp. 3192–3198, 2010.
  * [11] B. C. Ancell, A. Bogusz, M. J. Lauridsen, and C. J. Nauert, “Seeding chaos: The dire consequences of numerical noise in nwp perturbation experiments,” _Bulletin of the American Meteorological Society_ , vol. 99, no. 3, pp. 615–628, 2018.
  * [12] S. Mehrkanoon, “Deep shared representation learning for weather elements forecasting,” _Knowledge-Based Systems_ , vol. 179, pp. 120–128, 2019.
  * [13] K. Dragoon, _Valuing wind generation on integrated power systems_. William Andrew, 2010.
  * [14] S. P. Ashok and S. Pekkat, “A systematic quantitative review on the performance of some of the recent short-term rainfall forecasting techniques,” _Journal of Water and Climate Change_ , 2022.
  * [15] S. Agrawal, L. Barrington, C. Bromberg, J. Burge, C. Gazen, and J. Hickey, “Machine learning for precipitation nowcasting from radar images,” _arXiv preprint arXiv:1912.12132_ , 2019.
  * [16] E. Camporeale, “The challenge of machine learning in space weather: Nowcasting and forecasting,” _Space Weather_ , vol. 17, no. 8, pp. 1166–1207, 2019\.
  * [17] J. Jing, Q. Li, X. Peng, Q. Ma, and S. Tang, “Hprnn: A hierarchical sequence prediction model for long-term weather radar echo extrapolation,” in _ICASSP 2020 - 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2020, pp. 4142–4146.
  * [18] J. G. Fernández and S. Mehrkanoon, “Broad-unet: Multi-scale feature learning for nowcasting tasks,” _Neural Networks_ , vol. 144, pp. 419–427, 2021.
  * [19] J. Chen, Y. Lu, Q. Yu, X. Luo, E. Adeli, Y. Wang, L. Lu, A. L. Yuille, and Y. Zhou, “Transunet: Transformers make strong encoders for medical image segmentation,” _arXiv preprint arXiv:2102.04306_ , 2021.
  * [20] K. Trebing, T. Stanczyk, and S. Mehrkanoon, “SmaAt-UNet: Precipitation nowcasting using a small attention-UNet architecture,” _Pattern Recognition Letters_ , vol. 145, pp. 178–186, 2021.
  * [21] X. Shi, Z. Chen, H. Wang, D.-Y. Yeung, W.-K. Wong, and W.-c. Woo, “Convolutional lstm network: A machine learning approach for precipitation nowcasting,” _Advances in neural information processing systems_ , vol. 28, 2015.
  * [22] Y. Wang, M. Long, J. Wang, Z. Gao, and P. S. Yu, “Predrnn: Recurrent neural networks for predictive learning using spatiotemporal lstms,” _Advances in neural information processing systems_ , vol. 30, 2017.
  * [23] Q.-K. Tran and S.-k. Song, “Multi-channel weather radar echo extrapolation with convolutional recurrent neural networks,” _Remote Sensing_ , vol. 11, no. 19, p. 2303, 2019.
  * [24] C. K. Sønderby, L. Espeholt, J. Heek, M. Dehghani, A. Oliver, T. Salimans, S. Agrawal, J. Hickey, and N. Kalchbrenner, “Metnet: A neural weather model for precipitation forecasting,” _arXiv preprint arXiv:2003.12140_ , 2020\.
  * [25] X. Shi, Z. Gao, L. Lausen, H. Wang, D.-Y. Yeung, W.-k. Wong, and W.-c. Woo, “Deep learning for precipitation nowcasting: A benchmark and a new model,” _Advances in neural information processing systems_ , vol. 30, 2017.
  * [26] I. Bilionis, E. M. Constantinescu, and M. Anitescu, “Data-driven model for solar irradiation based on satellite observations,” _Solar energy_ , vol. 110, pp. 22–38, 2014.
  * [27] F. Shaheen, B. Verma, and M. Asafuddoula, “Impact of automatic feature extraction in deep learning architecture,” in _2016 International conference on digital image computing: techniques and applications (DICTA)_. IEEE, 2016, pp. 1–8.
  * [28] D. Aykas and S. Mehrkanoon, “Multistream graph attention networks for wind speed forecasting,” in _Proceedings of IEEE Symposium Series on Computational Intelligence (IEEE-SSCI)_ , 2021, pp. 1–8.
  * [29] I. A. Abdellaoui, J. G. Fernández, C. Sahinli, and S. Mehrkanoon, “Enhancing brain decoding using attention augmented deep neural networks,” in _29th Proceedings of European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning (ESANN)_ , 2021, pp. 183–188.
  * [30] R. Zemouri, N. Zerhouni, and D. Racoceanu, “Deep learning in the biomedical applications: Recent and future status,” _Applied Sciences_ , vol. 9, no. 8, p. 1526, 2019.
  * [31] A. H. Marblestone, G. Wayne, and K. P. Kording, “Toward an integration of deep learning and neuroscience,” _Frontiers in computational neuroscience_ , p. 94, 2016.
  * [32] J. G. Fernández and S. Mehrkanoon, “Broad-UNet: Multi-scale feature learning for nowcasting tasks,” _Neural Networks_ , vol. 144, pp. 419–427, 2021.
  * [33] Y. Yang and S. Mehrkanoon, “AA-TransUNet: Attention augmented transunet for nowcasting tasks,” in _Proceedings of International Joint Conference on Neural Networks (IEEE-IJCNN)_ , 2022, pp. 01–08.
  * [34] Y. Tao, P. Palasek, Z. Ling, and I. Patras, “Background modelling based on generative unet,” in _2017 14th IEEE International Conference on Advanced Video and Signal Based Surveillance (AVSS)_. IEEE, 2017, pp. 1–6.
  * [35] D. Tran, L. Bourdev, R. Fergus, L. Torresani, and M. Paluri, “Learning spatiotemporal features with 3d convolutional networks,” in _Proceedings of the IEEE international conference on computer vision_ , 2015, pp. 4489–4497.
  * [36] X. Hu, M. A. Naiel, A. Wong, M. Lamm, and P. Fieguth, “Runet: A robust unet architecture for image super-resolution,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops_ , 2019, pp. 0–0.
  * [37] J. Ngiam, A. Khosla, M. Kim, J. Nam, H. Lee, and A. Y. Ng, “Multimodal deep learning,” in _ICML_ , 2011.
  * [38] O. Bilgin, P. Mąka, T. Vergutz, and S. Mehrkanoon, “TENT: Tensorized encoder transformer for temperature forecasting,” _arXiv preprint arXiv:2106.14742_ , 2021.
  * [39] A. Moraux, S. Dewitte, B. Cornelis, and A. Munteanu, “A deep learning multimodal method for precipitation estimation,” _Remote Sensing_ , vol. 13, no. 16, 2021. [Online]. Available: https://www.mdpi.com/2072-4292/13/16/3278
  * [40] G. Ayzel, M. Heistermann, A. Sorokin, O. Nikitin, and O. Lukyanova, “All convolutional neural networks for radar-based precipitation nowcasting,” _Procedia Computer Science_ , vol. 150, pp. 186–192, 2019.
  * [41] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 770–778.
  * [42] C. Finn, I. Goodfellow, and S. Levine, “Unsupervised learning for physical interaction through video prediction,” _Advances in neural information processing systems_ , vol. 29, 2016.
  * [43] O. Ronneberger, P. Fischer, and T. Brox, “U-net: Convolutional networks for biomedical image segmentation,” in _Medical Image Computing and Computer-Assisted Intervention–MICCAI 2015: 18th International Conference, Munich, Germany, October 5-9, 2015, Proceedings, Part III 18_. Springer, 2015, pp. 234–241.
  * [44] H. Hersbach, B. Bell, P. Berrisford, S. Hirahara, A. Horányi, J. Muñoz-Sabater, J. Nicolas, C. Peubey, R. Radu, D. Schepers, A. Simmons, C. Soci, S. Abdalla, X. Abellan, G. Balsamo, P. Bechtold, G. Biavati, J. Bidlot, M. Bonavita, G. De Chiara, P. Dahlgren, D. Dee, M. Diamantakis, R. Dragani, J. Flemming, R. Forbes, M. Fuentes, A. Geer, L. Haimberger, S. Healy, R. J. Hogan, E. Hólm, M. Janisková, S. Keeley, P. Laloyaux, P. Lopez, C. Lupu, G. Radnoti, P. de Rosnay, I. Rozum, F. Vamborg, S. Villaume, and J.-N. Thépaut, “The era5 global reanalysis,” _Quarterly Journal of the Royal Meteorological Society_ , vol. 146, no. 730, pp. 1999–2049, 2020.


# Piece of CAKE: A Comprehensive Queue Management Solution for Home Gateways

Toke Høiland-Jørgensen  Dept. of Computer Science
Karlstad University, Sweden
<EMAIL_ADDRESS>Dave Täht  Teklibre
Los Gatos, California
<EMAIL_ADDRESS>Jonathan Morton<EMAIL_ADDRESS>
Somero, Finland
<EMAIL_ADDRESS>
###### Abstract

The last several years has seen a renewed interest in smart queue management
to curb excessive network queueing delay, as people have realised the
prevalence of bufferbloat in real networks.

However, for an effective deployment at today’s last mile connections, an
improved queueing algorithm is not enough in itself, as often the bottleneck
queue is situated in legacy systems that cannot be upgraded. In addition,
features such as per-user fairness and the ability to de-prioritise background
traffic are often desirable in a home gateway.

In this paper we present Common Applications Kept Enhanced (CAKE), a
_comprehensive network queue management system_ designed specifically for home
Internet gateways. CAKE packs several compelling features into an integrated
solution, thus easing deployment. These features include: bandwidth shaping
with overhead compensation for various link layers; reasonable DiffServ
handling; improved flow hashing with both per-flow and per-host queueing
fairness; and filtering of TCP ACKs.

Our evaluation shows that these features offer compelling advantages, and that
CAKE has the potential to significantly improve performance of last-mile
internet connections.

##  I Introduction

Eliminating bufferbloat has been recognised as an important component in
ensuring acceptable performance of internet connections, especially as
applications and users demand ever lower latencies. The last several years
have established that Active Queue Management and Fairness Queueing are
effective solutions to the bufferbloat problem, and several algorithms have
been proposed and evaluated (e.g., [1, 2, 3]).

However, while modern queueing algorithms can effectively control bufferbloat,
effective deployment presents significant challenges. The most immediate
challenge is that the home gateway device is often not directly in control of
the bottleneck link, because queueing persists in drivers or firmware of
devices that cannot be upgraded [1]. In addition, other desirable features in
a home networking context (such as per-user fairness, or the ability to
explicitly de-prioritise background applications) can be challenging to
integrate with existing queueing solutions. To improve upon this situation, we
have developed Common Applications Kept Enhanced (CAKE), which is a
_comprehensive network queue management_ system designed specifically for the
home router use case.

As outlined below, each of the issues that CAKE is designed to handle has been
addressed separately before. As such, the compelling benefit of CAKE is that
it takes state of the art solutions and integrates them to provide:

  * •

a high-precision rate-based bandwidth shaper that includes overhead and link
layer compensation features for various link types.

  * •

a state of the art fairness queueing scheme that simultaneously provides both
host and flow isolation.

  * •

a Differentiated Services (DiffServ) prioritisation scheme with rate limiting
of high-priority flows and work-conserving bandwidth borrowing behaviour.

  * •

TCP ACK filtering that increases achievable throughput on highly asymmetrical
links.

CAKE is implemented as a _queueing discipline_ (qdisc) for the Linux kernel.
It has been deployed as part of the OpenWrt router firmware for the last
several years and is in the process of being submitted for inclusion in the
mainline Linux kernel.111We include links to the source code, along with the
full evaluation dataset, in an online appendix [4].

The rest of this paper describes the design and implementation of CAKE and is
organised as follows: Section II outlines the desirable features of a
comprehensive queue management system for a home router, and recounts related
work in this space. Section III describes the design and implementation of
CAKE in more detail, and Section IV evaluates the performance of the various
features. Finally, Section V concludes.

##  II Background and Related Work

As mentioned initially, CAKE is designed to run on a home network gateway. We
have gathered significant experience with implementing such a system in form
of the Smart Queue Management (SQM) system shipped in the OpenWrt router
firmware project, which has guided the design of CAKE.

In this section we provide an overview of the problems CAKE is designed to
address. We are not aware of any previous work addressing the home gateway
queue management challenges as a whole. However, several of the issues that
CAKE addresses have been subject of previous work, and so the following
subsections serve as both an introduction to the design space and an overview
of related work.

The four problems we seek to address are bandwidth shaping, queue management
and fairness, DiffServ handling and TCP ACK filtering. These are each treated
in turn in the following sections.

###  II-A Bandwidth Shaping

A queue management algorithm is only effective if it is in control of the
bottleneck queue. Thus, queueing in lower layers needs to be eliminated, which
has been achieved in Linux for Ethernet [5] and WiFi [6]. However, eliminating
queueing at the link layer is not always possible, either because the driver
source code is unavailable, or because the link-layer is implemented in
inaccessible hardware or firmware (either on the same device or a separate
device, such as a DSL modem).

As an alternative, queueing in the lower layers can be avoided by deploying a
bandwidth shaper as part of the queue management system. By limiting the
traffic traversing the bottleneck link to a bandwidth that is slightly less
than the physical capacity of the link itself, queueing at the physical
bottleneck can be eliminated and bufferbloat avoided. Such bandwidth shaping
can be performed by a token bucket-based shaper (as is well-known from ATM
networks, e.g., [7]), or by a rate-based shaper (which is known from video
streaming applications, e.g., [8]).

The use of a shaper to move the link bottleneck wastes the bandwidth that is
the difference between the actual physical link capacity, and the set-point of
the shaper. To limit this waste, the shaper needs to be set as close to the
actual link bandwidth as possible, while avoiding sending bursts of packets at
a rate that is higher than the actual capacity. To achieve this, accurate
timing information on a per-packet basis is needed. In addition, the shaper
must account for link-layer framing and overhead. For instance, DSL links
using ATM framing split up data packets into an integer number of fixed-size
cells, which means that the framing overhead is a step function of packet
size, rather than a fixed value.

###  II-B Queue Management

Having control of the bottleneck queue makes it possible to implement
effective queue management that can all but eliminate bufferbloat. Such a
queue management scheme usually takes the form of an Active Queue Management
(AQM) algorithm, combined with a form of fairness queueing (FQ). Several such
schemes exist, and extensive evaluation is available in the literature (e.g.,
[1, 2, 3, 9, 10, 11]).

Among the state of the art algorithms in modern queue management, is the FQ-
CoDel algorithm [12]. FQ-CoDel implements a hybrid AQM/fairness queueing
scheme which isolates flows using a hashing scheme and schedules them using a
Deficit Round-Robin (DRR) [13] scheduler. In addition, FQ-CoDel contains an
optimisation that provides implicit service differentiation for sparse (low-
bandwidth) flows, similar to [14, 15]. Evaluations of FQ-CoDel have shown that
it achieves low queueing latency and high utilisation under a variety of
scenarios [1, 3].

However, while the FQ-CoDel scheduler provides flow isolation and fairness,
the transport layer flow is not always the right level of fairness in the home
gateway use case. Often, additional isolation between _hosts_ on the network
is desirable; and indeed this per-host isolation was the most requested
feature of the SQM system. Host isolation is straight-forward to implement in
place of flow fairness in any fairness queueing based scheme (by simply
changing the function that maps packets into different queues), but we are not
aware of any practical schemes prior to CAKE that implement _both_ host and
flow fairness.

###  II-C DiffServ Handling

Even though flow-based fairness queueing offers a large degree of separation
between traffic flows, it can still be desirable to explicitly treat some
traffic as higher priority, and to have the ability to mark other traffic as
low priority. Since a home network generally does not feature any admission
control, any prioritisation scheme needs to be robust against attempts at
abuse (so, e.g., a strict priority queue does not work well). In addition,
enabling prioritisation should not affect the total available bandwidth in the
absence of marked traffic, as that is likely to cause users to turn the
feature off.

Prioritisation of different traffic classes can be performed by reacting to
DiffServ markings [16]. This is commonly used in WiFi networks, where DiffServ
code points map traffic into four priority levels [17]. For the home gateway
use case, various schemes have been proposed in the literature (e.g., [18]),
but as far as we are aware, none have seen significant deployment.

###  II-D TCP ACK Filtering

TCP ACK filtering is an optimisation that has seen some popularity in highly
asymmetrical networks [19], and especially in cable modem deployments [20].
The technique involves filtering (or _thinning_) TCP acknowledgement (ACK)
packets by inspecting queues and dropping ACKs if a TCP flow has several
consecutive ACKs queued. This can improve performance on highly asymmetrical
links, where the reverse path does not have sufficient capacity to transport
the ACKs produced by the forward path TCP flow. However, ACK filtering can
also have detrimental effects on performance, for instance due to cross layer
interactions [21].

##  III The Design of CAKE

The design of CAKE builds upon the basic fairness scheduler design of FQ-
CoDel, but adds features to tackle the areas outlined in the previous section.
The following sections outline how CAKE implements each of these features.

###  III-A Bandwidth Shaping

CAKE implements a rate-based shaper, which works by scheduling packet
transmission at precise intervals using a virtual transmission clock. The
clock is initialised by the first packet to arrive at an empty queue, and
thereafter is incremented by the calculated serialisation delay of each
transmitted packet. Packets are delayed until the system time has caught up
with the virtual clock. If the clock schedule is reached while the queue is
empty, the clock is reset and the link goes idle.

This shaper handles bandwidth ranging over several orders of magnitude, from
several Kbps to several Gbps. In addition, the rate-based shaper does not
require a burst parameter, which simplifies configuration as compared to a
token-bucket shaper. It also eliminates the initial burst observed from token-
bucket shapers after an idle period. This is important for controlling the
bottleneck queue, as this initial burst would result in queueing at the real
bottleneck link.

####  III-A1 Overhead and Framing Compensation

As mentioned in Section II-A above, the shaper accounts for the actual size of
a packet on the wire, including any encapsulation and overhead, which allows
the rate to be set closer to the actual bottleneck bandwidth, thus eliminating
waste. We believe it is safe to set a rate within 0.1% of the actual link rate
when the overhead compensation is configured correctly, with a margin mainly
required to accommodate slight variations in the actual bottleneck link
bandwidth, caused by, e.g., clock drift in the hardware.

CAKE implements an overhead compensation algorithm which begins by determining
the size of the network-layer packet, stripped of any MAC layer encapsulation.
Having determined the network-layer packet size, the configured overhead can
be added to yield the correct on-the-wire packet size, followed optionally by
a specialised adjustment for ATM or PTM framing. This algorithm is shown in
Algorithm 1.

Using the network-layer packet size and adding a manually configured overhead
value is required because the values reported by the kernel are often wrong
due to idiosyncrasies of the CPE unit. While this does make configuration a
bit more complex, we seek to alleviate this by providing keywords for commonly
used configurations.

As part of the overhead compensation, CAKE also optionally splits "super
packets" generated by hardware offload features. These super packets are
essential for operating at high bandwidths, as they help amortise fixed
network stack costs over several packets. However, at lower bandwidths they
can hurt latency, in particular when a link with a high physical bandwidth is
shaped to a lower rate. For this reason, we conditionally split super packets
when shaping at rates lower than 1 Gbps. This allows CAKE to ensure low
latency at lower rates, while still scaling to full line rate on a 40Gbps
link.

Algorithm 1 Shaping and overhead compensation algorithm. _T_next_ is the time
at which the next packet is eligible for tranmission.

1:function enqueue(_pkt_)

2: $\textit{net\\_len}\leftarrow\textit{pkt.len}\,-\,$network_offset(pkt)

3: $\textit{adj\\_len}\leftarrow\textit{net\\_len}+\textit{overhead}$

4: if ATM framing is enabled then

5: $\textit{adj\\_len}\leftarrow$ ceiling(adj_len / 48) * 53

6: else if PTM framing is enabled then

7: $\textit{adj\\_len}\leftarrow$ ceiling(adj_len / 64) * 65

8: $\textit{pkt.adj\\_len}\leftarrow\textit{adj\\_len}$

9: if  _backlog_ is zero and _T_next_ is after _Now_ then

10: $\textit{T\\_next}\leftarrow\textit{Now}$

11:function dequeue

12: if  _T_next_ is after _Now_ then

13: Schedule interrupt at T_next

14: return Nil

15: $\textit{pkt}\leftarrow$ Choose Packet

16:
$\textit{T\\_next}\leftarrow\textit{T\\_next}+\textit{pkt.adj\\_len}*\textit{time\\_per\\_byte}$

17: return pkt

###  III-B Flow Isolation and Hashing

CAKE replaces the direct hash function used in FQ-CoDel with an 8-way set-
associative hash. While set-associative hashing has been well-known for
decades as a means to improve the performance of CPU caches [22], it has not
seen much use in packet scheduling. Conceptually, a $k\mathrm{-way}$ set-
associative hash with $n$ total buckets can be thought of as a plain hash with
$n/k$ buckets that is only considered to have a collision if more than $k$
items hash into the same bucket. As can be seen in Figure 1, this
significantly reduces the hash collision probability up to the point where the
number of flows is larger than the number of queues.222See how we computed
these probabilities in the online appendix.

Figure 1:  Probability that a new flow will experience a hash collision, as a
function of the number of active flows. 1024 total queues.

####  III-B1 Host Isolation

With flow fairness, hosts can increase their share of the available bandwidth
by splitting their traffic over multiple flows. This can be prevented by
providing host fairness at the endpoint IP address level, which CAKE can do in
addition to flow fairness.

The host isolation is simple in concept: The effective DRR quantum is divided
by the number of flows active for the flow endpoint. This mechanism can be
activated in three different modes: source address fairness, in which hosts on
the local LAN receive equal share, destination address fairness, in which
servers on the public internet receive an equal share, or "triple isolate"
mode, in which the maximum of the source and destination scaling is applied to
each flow. CAKE also hooks into the Linux kernel Network Address Translation
(NAT) subsystem to obtain the internal host address of a packet, which would
otherwise be obscured since packets are queued after NAT is applied.

Algorithm 2 Host isolation algorithm.

1:function enqueue(_pkt_)

2: $\textit{flow\\_hash}\leftarrow$ hash(pkt.hdr)

3: $\textit{src\\_hash}\leftarrow$ hash(pkt.src_ip)

4: $\textit{dst\\_hash}\leftarrow$ hash(pkt.dst_ip)

5: $\textit{flow}\leftarrow\textit{flows[flow\\_hash]}$

6: if  _flow_ is not active then

7: hosts[src_hash].refcnt_src++

8: hosts[dst_hash].refcnt_dst++

9: $\textit{flow.active}\leftarrow 1$

10: $\textit{flow.src\\_id}\leftarrow\textit{src\\_hash}$

11: $\textit{flow.dst\\_id}\leftarrow\textit{dst\\_hash}$

12:function get_quantum(_flow_)

13:
$\textit{refcnt\\_src}\leftarrow\textit{hosts[flow.src\\_id].refcnt\\_src}$

14:
$\textit{refcnt\\_dst}\leftarrow\textit{hosts[flow.dst\\_id].refcnt\\_dst}$

15: $\textit{host\\_load}\leftarrow$ max(refcnt_src, refcnt_dst, 1)

16: return $\textit{flow.quantum}/\textit{host\\_load}$

CAKE accomplishes this scaling as shown in Algorithm 2: When a packet is
enqueued it is hashed into a queue using the transport layer port numbers
along with the source and destination IP addresses. In addition, two separate
hashes are performed on the packet destination IP address and source IP
address. A separate set of hash buckets is kept for these address hashes.
These buckets do not contain a queue of packets, but instead a data structure
that keeps two reference counts for each IP address, which track the number of
active flows with the given address as source and destination, respectively.

The per-IP reference counts are used to modify the quantum for each active
flow. When a flow is scheduled, its "host load" is calculated as the maximum
of the reference counts for its source and destination IP addresses. The
effective quantum of the flow is simply divided by this load value, which
achieves the desired scaling.

###  III-C DiffServ handling

CAKE provides a small number of preset configurations, which map each DiffServ
code point into a priority tier. If the shaper is in use, each priority tier
gets its own virtual clock, which limits that tier’s rate to a fraction of the
overall shaped rate. When dequeueing a packet, the algorithm simply picks the
highest-priority tier which both has queued traffic and whose schedule is due,
if one exists. To allow tiers to borrow excess bandwidth from one another, the
dequeue algorithm also tracks the earliest schedule time of all non-empty
tiers, and if no other eligible tier is available, that tier is picked instead
(within the overall shaper limits).

When the shaper is not in use, CAKE instead uses a simple weighted DRR
mechanism to schedule the different priority tiers, with the same weights as
the shaper fractions mentioned above. This has weaker precedence guarantees
for high-priority traffic, but provides the same proportional capacity
reservation and the ability to borrow spare capacity from less than fully
loaded tiers.

CAKE defaults to a simple, three-tier mode that interprets most code points as
"best effort", but places CS1 traffic into a low-priority "bulk" tier which is
assigned $1/16$ of the total rate, and a few code points indicating latency-
sensitive or control traffic (specifically TOS4, VA, EF, CS6, CS7) into a
"latency sensitive" high-priority tier, which is assigned 1/4 rate. The other
DiffServ modes supported by CAKE are a 4-tier mode matching the 802.11e
precedence rules [17], as well as two 8-tier modes, one of which implements
strict precedence of the eight priority levels.

###  III-D ACK filtering

CAKE contains an ACK filtering mechanism that drops _redundant_ ACKs from a
TCP flow. The mechanism takes advantage of the per-flow queueing by scanning
the queue after every packet enqueue, to identify a pure ACK (i.e., an ACK
with no data) that was made redundant by the newly enqueued packet. An ACK is
only filtered if the newly enqueued packet contains an acknowledgement of
_strictly more_ bytes than the one being filtered. In particular, this means
that duplicate ACKs are not filtered, so TCP’s fast retransmit mechanism is
not affected. In addition, the filter parses TCP headers and only drops a
packet if that will not result in loss of information at the sender; and
packets with unknown headers are never dropped, to avoid breaking future TCP
extensions. The filter has two modes of operation: a conservative mode that
will always keep at least two redundant ACKs queued, and an aggressive mode,
that only keeps the most recently enqueued ACK.

##  IV Performance Evaluation

In this section, we present a performance evaluation of CAKE. All tests are
performed on a testbed that emulates a pair of hosts communicating through a
low-bandwidth link. We use the Flent testing tool [23] to run the tests, and
the data files are available on the companion web site.1 Unless otherwise
stated below, all tests are run on a symmetrical 10 Mbps link with 50 ms
baseline latency. Our basic test is the Real-Time Response Under Load test,
which consists of running four TCP flows in each traffic direction, along with
three different latency measurement flows [24].

Figure 2:  Baseline throughput and latency of CAKE and FQ-CoDel on a 10 Mbps
link.

As can be seen in Figure 2, the baseline performance of CAKE is comparable to
that of FQ-CoDel: both achieve low latency and high throughput in the baseline
test. This is expected, since CAKE is derived from FQ-CoDel. For a more
comprehensive comparison of FQ-CoDel with other queue management algorithms,
we refer the reader to [1]. Instead, the remainder of this evaluation focuses
on the features outlined in the previous sections.

###  IV-A Host Isolation

To evaluate the host isolation feature of CAKE, we run a varying number of TCP
flows between two source hosts and four destination hosts. Source host A runs
one flow to each of destination hosts A and B, and two flows to destination
host C, while source host B runs one flow to each of destination hosts C and
D. This makes it possible to demonstrate the various working modes of CAKE’s
host isolation feature.

Figure 3:  Host isolation performance with TCP flows from two source hosts to
four destination hosts. The columns show different algorithms; each bar shows
the average flow goodput.

The result of this test is shown in Figure 3. It shows four configurations of
CAKE (no host isolation, source host isolation, destination host isolation and
triple isolation) and a test with FQ-CoDel as the queue management algorithm.
As can be seen in the figure, both FQ-CoDel and CAKE with no host isolation
provide complete fairness between all six flows.

The figure also clearly shows the various modes of flow isolation supported by
CAKE: In destination fairness mode (second column), the four destination hosts
get the same total share, which results in each of the three flows to
destination host C getting $1/3$ of the bandwidth of the three other hosts
(which only have one flow each). Similarly, in source fairness mode (third
column), the two source hosts share the available capacity, which results in
the two flows from source B getting twice the share each compared to the four
flows from host A.

In the triple isolation case, we see the flow bandwidths correspond to the
quantum scaling outlined in Algorithm 2: The first four flows get their
quantum scaled by $1/4$ since there are four flows active from host A. The
fifth flow gets its quantum scaled by $1/3$ since there are three flows active
to host C. And finally, the last flow gets its quantum scaled by $1/2$ as
there are two flows active from host B.

###  IV-B DiffServ Handling

To demonstrate the DiffServ prioritisation features of CAKE we perform two
tests: An RRUL test with each flow marked with a different DiffServ priority,
and another test where a high-priority fixed-rate flow competes with several
TCP flows.

The result of the former test is seen in Figure 4. This shows that when
DiffServ mode is not enabled, all four flows get the same share of the
available bandwidth, while in the DiffServ-enabled case, the Best Effort (BE)
flow gets most of the bandwidth. This latter effect is important for two
reasons: First, it shows that a flow marked as background (BK) is successfully
de-prioritised and gets less bandwidth. Secondly, it shows that the high-
priority flows (CS5 and EF) are limited so as to not use more than the share
of the bandwidth allocated to the high-priority DiffServ classes.

Figure 4:  TCP flows on different DiffServ code points.

To look at the latency performance of a high-priority flow, we turn to Figure
5. This shows the latency over time of a fixed-rate 2 Mbps flow, which marks
its packets with the high-priority EF DiffServ marking. This is meant to
represent a real-time video conversation. In the test, the flow competes with
32 bulk TCP flows. As can be seen in the figure, both FQ-CoDel and CAKE with
DiffServ prioritisation disabled fail to ensure low latency for the high-
priority flow. Instead, when the bulk flows start after five seconds, a large
latency spike is seen, since the real-time flow has to wait for the initial
packets of the 32 TCP flows. This causes the real-time flow to build a large
queue for itself (since it does not respond to congestion signals), which then
drains slowly back to a steady state around 200 ms (for CAKE) or oscillating
between 50 and 500 ms (for FQ-CoDel). In contrast, the DiffServ-enabled CAKE
keeps the real-time flow completely isolated from the bulk TCP flows, ensuring
it sees no added latency over the duration of the test.

Figure 5:  Latency over time of a 2 Mbps fixed-rate flow with 32 competing
bulk flows on a 10 Mbps link. The Y-axis shows additional latency above the
base latency of 50 ms. The bulk flows start after 5 seconds.

###  IV-C ACK Filtering

Figure 6 shows the performance of ACK filtering on a highly asymmetrical link
with 30 Mbps download capacity and only 1 Mbps upload capacity. On this link,
we run four simultaneous TCP uploads and four simultaneous TCP downloads. The
results of this are shown in Figure 6, which shows the aggregate throughput of
all four flows in each direction, along with the added latency of a separate
measurement flow. Values are normalised to the baseline without ACK filtering
to be able to fit on a single graph. As the figure shows, we see a goodput
improvement of around 15% in the downstream direction caused by either type of
ACK filtering, which shows that insufficient bandwidth for ACKs can impact
transfers in the other direction. For upload, the conservative filtering
increases goodput by about 10%, while the aggressive filtering increases
throughput by as much as 40%, simply by reducing the bandwidth taken up by ACK
packets. We attribute the increase in latency to increased congestion in the
downlink direction, which is alleviated somewhat by fewer ACKs being queued in
the upstream direction in the aggressive case. The absolute magnitude of the
latency increase is only 5 ms.

Figure 6:  ACK filtering performance on a 30/1 Mbps link. The graph scales are
normalised to the "No filtering" case. The download and upload value ranges
are 24.5-27.5 Mbps and 0.45-0.7 Mbps, respectively. The latency range is
2.6-7.5 ms.

##  V Conclusions

CAKE is a comprehensive queue management system for home gateways, that packs
several compelling features into an integrated solution, with reasonable
defaults to ease configuration. These features include: bandwidth shaping with
overhead compensation for various link layers; reasonable DiffServ handling;
improved flow hashing with both per-flow and per-host queueing fairness; and
filtering of TCP ACKs.

Our evaluation shows that these features offer compelling advantages, and we
believe CAKE has the potential to significantly improve the performance of
last-mile internet connections. CAKE is open source and ready for deployment,
and already ships in the OpenWrt router firmware distribution.

## Acknowledgements

The authors would like to thank the Bufferbloat and OpenWrt communities for
their work on the implementation and testing of CAKE. In particular, Kevin
Darbyshire-Bryant was instrumental in enabling NAT-awareness, Ryan Mounce
contributed the original ACK filtering code, Sebastian Moeller helped get the
overhead compensation right and Anil Agarwal helped with the hash collision
probability calculations.

## References

  * [1] T. Høiland-Jørgensen, P. Hurtig, and A. Brunstrom, “The Good, the Bad and the WiFi: Modern AQMs in a Residential Setting,” _Computer Networks_ , vol. 89, pp. 90 – 106, 2015.
  * [2] I. Järvinen and M. Kojo, “Evaluating CoDel, PIE, and HRED AQM techniques with load transients.” IEEE, 2014.
  * [3] N. Khademi, D. Ros, and M. Welzl, “The new AQM kids on the block: Much ado about nothing?” _Technical Report, Oslo University_ , 2013.
  * [4] T. Høiland-Jørgensen, D. Täht, and J. Morton, “Piece of CAKE: A Comprehensive Queue Management Solution for Home Gateways,” Apr. 2018. [Online]. Available: https://doi.org/10.5281/zenodo.1226887
  * [5] J. Corbet, “Network transmit queue limits,” LWN Article, August 2011. [Online]. Available: https://lwn.net/Articles/454390/
  * [6] T. Høiland-Jørgensen, M. Kazior, D. Täht, P. Hurtig, and A. Brunstrom, “Ending the Anomaly: Achieving Low Latency and Airtime Fairness in WiFi,” in _2017 USENIX Annual Technical Conference (USENIX ATC 17)_. Santa Clara, CA: USENIX Association, 2017, pp. 139–151.
  * [7] G. Niestegge, “The ‘leaky bucket’policing method in the atm (asynchronous transfer mode) network,” _International Journal of Communication Systems_ , vol. 3, no. 2, pp. 187–197, 1990.
  * [8] A. Eleftheriadis and D. Anastassiou, “Constrained and general dynamic rate shaping of compressed digital video,” in _International Conference on Image Processing_ , vol. 3. IEEE, 1995, pp. 396–399.
  * [9] V. P. Rao, M. P. Tahiliani, and U. K. K. Shenoy, “Analysis of sfqCoDel for active queue management,” in _ICADIWT 2014_. IEEE, 2014.
  * [10] R. Adams, “Active queue management: A survey,” _IEEE Communications Surveys & Tutorials_, vol. 15, no. 3, pp. 1425–1476, 2013.
  * [11] N. Benameur, F. Guillemin, and L. Muscariello, “Latency reduction in home access gateways with shortest queue first,” in _Proc. ISOC Workshop on Reducing Internet Latency_ , 2013.
  * [12] T. Hoeiland-Joergensen, P. McKenney, D. Taht, J. Gettys, and E. Dumazet, “The Flow Queue CoDel Packet Scheduler and Active Queue Management Algorithm,” RFC 8290, RFC Editor, Jan. 2018.
  * [13] M. Shreedhar and G. Varghese, “Efficient fair queuing using deficit round-robin,” _IEEE/ACM Transactions on Networking_ , Jun. 1996.
  * [14] A. Kortebi, S. Oueslati, and J. Roberts, “Implicit service differentiation using deficit round robin,” _ITC19_ , 2005.
  * [15] S. O. Abdesselem Kortebi, “Cross-Protect: Implicit Service Differentiation and Admission Control,” pp. 56 – 60, 2004.
  * [16] J. Babiarz, K. Chan, and F. Baker, “Configuration Guidelines for DiffServ Service Classes,” RFC 4594 (Informational), RFC Editor, Aug. 2006, updated by RFC 5865.
  * [17] T. Szigeti, J. Henry, and F. Baker, “Mapping Diffserv to IEEE 802.11,” RFC 8325 (Proposed Standard), RFC Editor, Feb. 2018.
  * [18] W.-S. Hwang and P.-C. Tseng, “A qos-aware residential gateway with bandwidth management,” _IEEE Transactions on Consumer Electronics_ , vol. 51, no. 3, pp. 840–848, 2005.
  * [19] H. Wu, J. Wu, S. Cheng, and J. Ma, “Ack filtering on bandwidth asymmetry networks,” in _APCC/OECC’99_ , vol. 1. IEEE, 1999.
  * [20] L. Storfer, “Enhancing cable modem tcp performance,” _Texas Instruments Inc. white paper_ , 2003.
  * [21] H. Kim, H. Lee, S. Shin, and I. Kang, “On the cross-layer impact of tcp ack thinning on ieee 802.11 wireless mac dynamics,” in _64th Vehicular Technology Conference_. IEEE, 2006.
  * [22] A. J. Smith, “A comparative study of set associative memory mapping algorithms and their use for cache and main memory,” _IEEE Transactions on Software Engineering_ , no. 2, pp. 121–130, 1978.
  * [23] T. Høiland-Jørgensen, C. A. Grazia, P. Hurtig, and A. Brunström, “Flent: The FLExible Network Tester,” in _VALUETOOLS_ , 2017.
  * [24] D. Taht, “Realtime response under load (rrul) test,” November 2012. [Online]. Available: https://www.bufferbloat.net/projects/bloat/wiki/RRUL_Spec/


[type=, title=LIST OF ABBREVIATIONS]