# SimQ-NAS: Simultaneous Quantization Policy and Neural Architecture Search

Sharath Nittur Sridhar
Intel Labs, Intel Corporation
<EMAIL_ADDRESS>
&Maciej Szankin ∗
Intel Labs, Intel Corporation
<EMAIL_ADDRESS>
&Fang Chen
University of California, Merced
<EMAIL_ADDRESS>
&Sairam Sundaresan
Intel Labs, Intel Corporation
<EMAIL_ADDRESS>
&Anthony Sarah
Intel Labs, Intel Corporation
<EMAIL_ADDRESS>
Authors have equal contribution.

###### Abstract

Recent one-shot Neural Architecture Search algorithms rely on training a
hardware-agnostic super-network tailored to a specific task and then
extracting efficient sub-networks for different hardware platforms. Popular
approaches separate the training of super-networks from the search for sub-
networks, often employing predictors to alleviate the computational overhead
associated with search. Additionally, certain methods also incorporate the
quantization policy within the search space. However, while the quantization
policy search for convolutional neural networks is well studied, the extension
of these methods to transformers and especially foundation models remains
under-explored. In this paper, we demonstrate that by using multi-objective
search algorithms paired with lightly trained predictors, we can efficiently
search for both the sub-network architecture and the corresponding
quantization policy and outperform their respective baselines across different
performance objectives such as accuracy, model size, and latency.
Specifically, we demonstrate that our approach performs well across both uni-
modal (ViT and BERT) and multi-modal (BEiT-3) transformer-based architectures
as well as convolutional architectures (ResNet). For certain networks, we
demonstrate an improvement of up to $4.80x$ and $3.44x$ for latency and model
size respectively, without degradation in accuracy compared to the fully
quantized INT8 baselines.

##  1 Introduction

Recently, using Neural Architecture Search (NAS) to generate optimal Deep
Neural Network (DNN) architectures for both computer vision (CV) and Natural
Language Processing (NLP) applications has become a popular solution to
increase inference efficiency of deployed models [1][2]. This trend reflects
the increasing demand for highly specialized and efficient DNNs. NAS
methodologies offer a systematic approach to exploring the vast search spaces
of possible architectures, with the goal of identifying the optimal network
structure for a specific task. In CV, NAS has been instrumental in developing
architectures like EfficientNet [3] and NASNet [4], which have set new high
scores in benchmarks for image classification and object detection tasks.
Similarly in NLP, NAS-based models like Evolved Transformer [5] have
demonstrated improvement in language understanding and translation tasks.
However, the growing complexity and cost of model’s design and deployment
necessitate an additional focus on model efficiency, especially in scenarios
with computational and/or energy use constraints. This need has brought model
efficiency techniques like quantization into focus.

One of the methods to achieve competitive accuracy in a quantized network is
Post Training Quantization. This has been a deeply studied subject, but most
of the research focuses on a quantization policy alone ([6]) and a single
optimization objective, which may lead to a sub-optimal solutions.

On the other hand, the joint neural architecture and quantization policy
search introduces significant challenges. The task of jointly optimizing both
the model’s structure and numerical precision not only adds complexity but
also increases computational demand, further expanding the already extensive
search space. This has been to some extent addressed by Once For All (OFA)[7],
showcasing the potential benefits of comprehensive optimization strategies.
One of OFA’s key contributions is the introduction of super-networks - large
neural networks that can be dynamically adjusted to create smaller,
specialized models without retraining. This is done with a novel weight-
sharing approach that decouples the model training and architecture search
stage to mitigate the computational overhead of sub-network architecture
evaluation during NAS caused by training and validation cycles.

The one-shot super-network allows for flexible changes in depth, width, kernel
size, and resolution without retraining, ideal for deployment on devices with
varying computational capabilities. However, training these versatile OFA
super-networks is complex and resource-intensive.

This idea has been extended to include quantization embedding in a joint
Architecture, Pruning, and Quantization (APQ) [8] work. This facilitates the
transfer of insights from the full-precision architecture predictor to the
quantization-aware predictor and use it in conjunction with evolutionary
search algorithm to identify best architecture and quantization policy.
However, this approach is not cost effective due to complex training procedure
of the FP32 super-network and need to generate a large dataset of
architecture, quantization policy and network’s accuracy data points to train
the predictors. Additionally, this method was designed with convolutional
neural networks(CNNs) in mind and is not yet proven to be transferable to
Transformer-based models.

In the methods described above, there are some limitations, two of which we
address in this work by proposing a systematic 2-step approach. The first
problem is the search space that is tied to the super-network model. These
models are hard to train and are both resource and time-consuming. To this
end, this work leverages super-networks created with InstaTune [9]. The second
problem is search efficiency, which this work addresses by leveraging LINAS
search algorithm [10].

##  2 Related Work

Currently, many joint quantization policy and neural architecture search
methods have been proposed, which can be roughly categorized into two groups:
quantization-aware training (QAT) and post-training quantization (PTQ).

QAT methods generally incorporate quantization policy into the search space
during the model training. For example, the bitwidth adaptive QAT [11]
proposes to redefine a meta-leaning task with bit widths to be applied in QAT.
FLIQS [12] employs a reinforcement learning (RL) controller to propose per-
layer formats and channel widths in quantization and NAS space during model
training.

Other efforts combine QAT with NAS using super-networks and differentiable
NAS. For instance, DNAS [13] proposes a differentiable super-network for QAT
in which each layer contains several parallel quantized weights and
activations with different precisions. EDMIPS [14] creates linear combination
of branches for each bit-width, and then alternates training the layer weights
and the branch weights. Q-BERT [15] simultaneously conducts quantization and
pruning at the subgroup-wise levels, and leverages differentiable NAS to
assign scale and precision for parameters in each subgroup automatically.
BatchQuant [16] employs batch statistics to adjust to changes in the
activation distribution caused by the selection of quantized sub-networks.
However, training QAT based super-networks can be extremely time consuming and
computationally expensive.

PTQ methods decouple the model training and quantization, which enables
efficient transfer of the pre-trained model into a low-precision floating
point or integer representation. ReLeQ [17] performs PTQ quantization searches
that utilize RL to allocate bit widths based on the model accuracy and cost
estimates. HAWQ [18] further explores PTQ searches to automatically select the
relative quantization precision of each layer based on the Hessian spectrum.
Recently, transformer-based models have been impressive in the computer vision
field, which requires a lot of compute resources due to the self-attention
module with quadratic time complexity. PTQ for transformer [19] presents an
efficient algorithm for quantization policy search to reduce the memory
storage and computation costs of the vision transformer. PTQ4ViT [6] proposes
the twin uniform quantization method to reduce the quantization error on
activation values by using a Hessian-guided metric to improve the accuracy of
calibration. However, these PTQ based approaches for Transformers mainly focus
on finding the best quantization policy and do not perform a joint search with
the network architecture. In contrast to these approaches, we propose a PTQ
based technique using multi-objective evolutionary search algorithms
incorporated with lightly trained predictors to search for sub-network
architecture and corresponding quantization policy. Our method performs well
across transformer-based architectures as well as CNN architectures.

##  3 Methodology

Most one-shot NAS approaches involve the creation of a trained super-network
followed by a multi-objective evolutionary search to find optimal sub-
networks. Training super-networks often requires a manual specification of
architectural elastic parameters and time-consuming and computationally
intensive training methods like progressive shrinking [7], which becomes in-
feasible especially for large models. Techniques like InstaTune[9] leverage
off-the-shelf pre-trained models and creates the elastic super-network during
the downstream fine-tuning stage and improves the overall efficiency. Our
approach is flexible and leverages super-networks generated by both InstaTune
and other conventional methods like OFA. InstaTune offers two options based on
compute resources to train the super-network. We employ the high cost option
involving the use of a fully fine-tuned teacher network for knowledge
distillation during fine-tuning.

Table 1: Search space size comparison for architecture ($S^{A}$), quantization policy ($S^{Q}$) and joint architecture and quantization policy ($S^{J}$) optimizations. Model | $S^{A}$ | $S^{Q}$ | $S^{J}$
---|---|---|---
BEiT-3 | $10^{13}$ | $10^{21}$ | $10^{34}$
ViT | $10^{13}$ | $10^{22}$ | $10^{35}$
BERT | $10^{13}$ | $10^{23}$ | $10^{36}$
OFA ResNet50 | $10^{13}$ | $10^{37}$ | $10^{50}$

For multi-objective search on super-networks, we use the Lightweight Iterative
NAS (LINAS) algorithm proposed in [10]. LINAS uses an iterative predictor-
based approach to accelerate the search towards a near-optimal Pareto
frontier, which is especially useful for vast search spaces defined by the
joint architecture and quantization policy parameters (Table 1).LINAS uses
simple predictors such as ridge regression or support vector machine
regression (SVR) and requires minimal data samples for accurate prediction as
demonstrated in [10].

Joint Architecture and Quantization Policy Search: Our proposed approach
performs a joint architecture and quantization policy search to simultaneously
optimize for network architecture and a corresponding quantization policy. We
employ the LINAS search algorithm to explore a combined search space that
includes both the network parameters and quantization bit widths for weights
and activations. The combined search space size shown in Table 1 ranges from
$10^{34}$ to $10^{50}$ for different models. We then perform post-training
static quantization (PTQ static) for sub-networks with the selected mixed
precision quantization policy - namely INT8 and FP32 - using the Intel Neural
Compressor library. Static PTQ quantizes weights and activations of the model
and requires a small representative calibration dataset to determine optimal
quantization parameters for the activations. While a variety of numerical
precisions, such as BFloat16 [20] or INT4 could theoretically be considered
for weights and activations to further extend set of possible solutions, the
absence of readily accessible hardware platforms that natively support these
format necessitated the limitation of our exploration to the combination of
INT8 and FP32. This decision aligns our research with the capabilities of
widely available hardware, ensuring the applicability and relevance of our
findings.

Table 2: Parameters used to define architecture of the Transformer-based super-networks: number of layers ($L^{A}$), number of attention heads ($H^{A}$),intermediate sizes ($Dffn^{A}$). $S^{A}$ is the approximated search space size for architecture-only optimization. Model | $L^{A}$ | $H^{A}$ | $Dffn^{A}$
---|---|---|---
BEiT-3 | 1x[11, 12] | 12x[6, 8, 10, 12] | 12x[2048, 2560, 3072]
ViT | 1x[10, 11, 12] | 12x[6, 8, 10, 12] | 12x[1024. 2048, 3072]
BERT | 1x[6, 7, 8, 9, 10, 11, 12] | 12x[6, 8, 10, 12] | 12x[1024, 2048, 3072]
Table 3: Parameters used to define architecture of the OFA ResNet50 super-network: depth ($D^{A}$), expand ratio ($E^{A}$) and width multiplier ($W^{A}$). Model | $D^{A}$ | $E^{A}$ | $W^{A}$
---|---|---|---
OFA ResNet50 | 5x[0, 1, 2] | 18x[0.2, 0.25, 0.35] | 6x[0.65, 0.8, 1.0]

In this work, we explore unimodal and multimodal Transformer models like
BEiT-3 [21], ViT [22], and BERT [23]. For Transformer-based architectures, we
mainly use an elastic architecture search space with the number of layers, the
number of attention heads, and the intermediate MLP dimensions (Table 2). For
completeness, we also include results on the pre-trained OFA [7] ResNet50 [24]
super-network, with the architecture defined with a set of parameters
presented in Table 3.

##  4 Experiments

(a) BERT model size

(b) BEiT-3 model size

(c) ViT model size

(d) OFA ResNet50 model size

(e) BERT latency

(f) BEiT-3 latency

(g) ViT latency

(h) OFA ResNet50 latency

Figure 1:  Joint architecture and quantization policy search Pareto front on
BERT Base, BEiT-3 Base, ViT Base and OFA ResNet50 super-networks using model
size and normalized latency as the search objectives.Each point shown on the
Pareto front represents a discovered sub-network architecture and a
corresponding quantization policy.

This section evaluates the proposed approach through experiments on diverse
models suited for various tasks and domains. We tested ResNet50 and ViT for
image classification, BERT for sentiment analysis in NLP, and BEiT-3, a multi-
modal foundation model, also for image classification. These models were
selected to demonstrate the applicability of our approach across different
domains and architectural designs. In our experiments, we showcased our
method’s flexibility through different super-network creation techniques. For
BEiT-3 and BERT super-networks were built using InstaTune, involving elastic
fine-tuning of pre-trained models on ImageNet-1K [25] for image classification
and SST2 [26] for sentiment classification, respectively. Conversely, the ViT
super-network was fully trained from scratch on ImageNet-1K to diversify
super-net methodology, as it shares common elements with BEiT and BERT. For
ResNet50, we used the OFA super-network trained on ImageNet-1K, demonstrating
our approach’s adaptability to various super-network training methods. For
each super-network a pair of multi-objective search experiments was performed.
The primary metric was model accuracy on respective dataset, supplemented by
either latency (single batch size) or model size (total memory occupancy).
Latency measurement was performed on different Intel Xeon platforms (8280,
8360Y, 8380 and 8480) and was normalized. Fig. 1 presents results in form of
Pareto optimal fronts, showcasing performance enhancements from architectural
and numerical optimizations. Each set of results includes reference point
based on a baseline model with all linear layers in INT8.

The BERT model demonstrates a notable $2.20x$ speed increase at the same
accuracy level compared to the INT8 baseline (Fig. 1(e)). Even the slowest
identified configuration surpasses the baseline by $1.23x$ in speed, coupled
with a $1.70\%$ absolute accuracy improvement. In terms of model size, our
approach achieves a $1.83x$ reduction at equivalent accuracy levels. The
highest accuracy network shows a $1.06x$ size improvement (Fig. 1(a)).

For the BEiT-3 model, iterative improvements were noted. A model $1.02x$
smaller than the baseline was found, maintaining the same accuracy (Fig 1(b).
The highest-scoring model showed $0.64\%$ accuracy improvement but was $1.22x$
larger than the baseline. Regarding latency, we found a model $1.12x$ faster
than the baseline with comparable accuracy (Fig. 1(f)). Sub-model with the
highest accuracy, improving by $0.69\%$, was $1.06x$ slower than the baseline.

For the ViT the biggest improvement can be seen with the latency objective
(Fig. 1(c)). Without sacrificing accuracy the search was able to identify a
configuration that achieves 1.97x improvement over baseline. Sub-network with
the highest top1 accuracy $78.77\%$ ($2.30\%$ absolute improvement over the
baseline) also offers improvements in latency ($1.20x$). For the model size
objective (Fig. 1(g)) the improvement between reference baseline and on-par
accuracy-wise sub-network is $42.40\%$, and when considering fixed model size,
the identified sub-model yields improved accuracy by $2.03\%$ over the
baseline.

Joint search on OFA ResNet50 offers significant improvements for both
performance objectives. Specifically, without accuracy loss model size was
reduced by $2x$, $3.06x$ and $3.44x$ for ResNet50, ResNet101 and ResNet152
baselines (Fig. 1(d)). Similarly, for the latency objective, an improvement of
$2.30x$, $4.36x$ and $4.8x$ was observed (Fig. 1(h)).

###  4.1 Ablations on Quantization only search

(a) BERT SST-2 model size

(b) OFA ResNet50 model size

(c) BERT SST-2 hypervolume

Figure 2: Search progression using LINAS for BERT Base (2(a)) and OFA ResNet50
(2(b)) super-networks. A clear progression towards the near-optimal Pareto
front can be seen with an increase in evaluation count. Additionally, a
significant improvement in model size is observed when compared to the FP32
baselines. Figure2(c) represents the BERT Base hypervolume progression for
different search algorithms is presented in 2(c) Figure 3: Comparison of
quantization policy only search and joint architecture and quantization policy
search with accuracy and model size on BERT Base fine-tuned with InstaTune on
SST2 dataset.

Fig. 3 shows the comparison between quantization policy only search and joint
sub-network and quantization policy search on the BERT SST2 super-network. The
results indicate that performing joint search using our approach significantly
improves the model size for similar accuracy, when compared to quantization
policy only search. Figures 2(a) and 2(b) demonstrates a drastic improvement
in the search progression using LINAS with increasing evaluation counts.
Additionally, multiple search experiments were performed with various search
algorithms - LINAS, NSGA-2 and Random Search - to validate efficiency of the
selected search algorithm. Averaged results with standard deviation as a plane
prove efficacy of LINAS on the joint search space and are presented as a
hypervolume in Fig. 2(c) for BERT SST2.

##  5 Conclusions

In this work we demonstrate the effectiveness of a joint architecture and
quantization policy search in optimizing DNN models for varied tasks. Our
approach, which simultaneously optimizes the network architecture and
quantization policy has shown considerable improvements in efficiency without
compromising on the accuracy. Specifically, for models like BERT, BEiT3, ViT
and ResNet50, we observed a substantial enhancement in terms of latency, model
size and classification accuracy. By focusing on widely supported numerical
precisions, like INT8 and FP32, we ensured that our findings are applicable
and relevant to a broad range of real-world scenarios. Future research in this
area could explore integrating a broader range of numerical precisions, such
as BFloat16 and INT4, as hardware becomes more readily available to
researchers. Another avenue for future work involves researching applicability
of the optimization methodology described in this work across a broader set of
domains, extending beyond image and sentiment classification. Investigating
these optimizations to current frontiers of research like large language
models is also an important research vector for this work.

## References

  * [1] Hadjer Benmeziane, Kaoutar El Maghraoui, Hamza Ouarnoughi, Smail Niar, Martin Wistuba, and Naigang Wang.  A comprehensive survey on hardware-aware neural architecture search.  arXiv preprint arXiv:2101.09336, 2021.
  * [2] Krishna Teja Chitty-Venkata, Murali Emani, Venkatram Vishwanath, and Arun K Somani.  Neural architecture search for transformers: A survey.  IEEE Access, 10:108374–108412, 2022.
  * [3] Mingxing Tan and Quoc Le.  Efficientnet: Rethinking model scaling for convolutional neural networks.  In International conference on machine learning, pages 6105–6114. PMLR, 2019.
  * [4] Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoc V Le.  Learning transferable architectures for scalable image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 8697–8710, 2018.
  * [5] David So, Quoc Le, and Chen Liang.  The evolved transformer.  In International conference on machine learning, pages 5877–5886. PMLR, 2019.
  * [6] Zhihang Yuan, Chenhao Xue, Yiqi Chen, Qiang Wu, and Guangyu Sun.  Ptq4vit: Post-training quantization for vision transformers with twin uniform quantization.  In European Conference on Computer Vision, pages 191–207. Springer, 2022.
  * [7] Han Cai, Chuang Gan, Tianzhe Wang, Zhekai Zhang, and Song Han.  Once-for-all: Train one network and specialize it for efficient deployment.  arXiv preprint arXiv:1908.09791, 2019.
  * [8] Tianzhe Wang, Kuan Wang, Han Cai, Ji Lin, Zhijian Liu, Hanrui Wang, Yujun Lin, and Song Han.  Apq: Joint search for network architecture, pruning and quantization policy.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2078–2087, 2020.
  * [9] Sharath Nittur Sridhar, Souvik Kundu, Sairam Sundaresan, Maciej Szankin, and Anthony Sarah.  Instatune: Instantaneous neural architecture search during fine-tuning.  In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV) Workshops, pages 1523–1527, October 2023.
  * [10] Daniel Cummings, Anthony Sarah, Sharath Nittur Sridhar, Maciej Szankin, Juan Pablo Munoz, and Sairam Sundaresan.  A hardware-aware framework for accelerating neural architecture search across modalities.  arXiv preprint arXiv:2205.10358, 2022.
  * [11] Jiseok Youn, Jaehun Song, Hyung-Sin Kim, and Saewoong Bahk.  Bitwidth-adaptive quantization-aware neural network training: A meta-learning approach.  In European Conference on Computer Vision, pages 208–224. Springer, 2022.
  * [12] Jordan Dotzel, Gang Wu, Andrew Li, Muhammad Umar, Yun Ni, Mohamed S Abdelfattah, Zhiru Zhang, Liqun Cheng, Martin G Dixon, Norman P Jouppi, et al.  Fliqs: One-shot mixed-precision floating-point and integer quantization search.  arXiv preprint arXiv:2308.03290, 2023.
  * [13] Bichen Wu, Yanghan Wang, Peizhao Zhang, Yuandong Tian, Peter Vajda, and Kurt Keutzer.  Mixed precision quantization of convnets via differentiable neural architecture search.  arXiv preprint arXiv:1812.00090, 2018.
  * [14] Zhaowei Cai and Nuno Vasconcelos.  Rethinking differentiable search for mixed-precision neural networks.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2349–2358, 2020.
  * [15] Changsheng Zhao, Ting Hua, Yilin Shen, Qian Lou, and Hongxia Jin.  Automatic mixed-precision quantization search of bert.  In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-2021. International Joint Conferences on Artificial Intelligence Organization, August 2021.
  * [16] Haoping Bai, Meng Cao, Ping Huang, and Jiulong Shan.  Batchquant: Quantized-for-all architecture search with robust quantizer.  Advances in Neural Information Processing Systems, 34:1074–1085, 2021.
  * [17] Ahmed T Elthakeb, Prannoy Pilligundla, FatemehSadat Mireshghallah, Amir Yazdanbakhsh, and Hadi Esmaeilzadeh.  Releq: A reinforcement learning approach for deep quantization of neural networks.  arXiv preprint arXiv:1811.01704, 2018.
  * [18] Zhen Dong, Zhewei Yao, Amir Gholami, Michael W Mahoney, and Kurt Keutzer.  Hawq: Hessian aware quantization of neural networks with mixed-precision.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 293–302, 2019.
  * [19] Zhenhua Liu, Yunhe Wang, Kai Han, Wei Zhang, Siwei Ma, and Wen Gao.  Post-training quantization for vision transformer.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 28092–28103. Curran Associates, Inc., 2021.
  * [20] Dhiraj Kalamkar, Dheevatsa Mudigere, Naveen Mellempudi, Dipankar Das, Kunal Banerjee, Sasikanth Avancha, Dharma Teja Vooturi, Nataraj Jammalamadaka, Jianyu Huang, Hector Yuen, et al.  A study of bfloat16 for deep learning training.  arXiv preprint arXiv:1905.12322, 2019.
  * [21] Wenhui Wang, Hangbo Bao, Li Dong, Johan Bjorck, Zhiliang Peng, Qiang Liu, Kriti Aggarwal, Owais Khan Mohammed, Saksham Singhal, Subhojit Som, et al.  Image as a foreign language: Beit pretraining for vision and vision-language tasks.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 19175–19186, 2023.
  * [22] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  arXiv preprint arXiv:2010.11929, 2020.
  * [23] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  arXiv preprint arXiv:1810.04805, 2018.
  * [24] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition. corr abs/1512.03385 (2015), 2015.
  * [25] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei.  ImageNet Large Scale Visual Recognition Challenge.  International Journal of Computer Vision (IJCV), 115(3):211–252, 2015.
  * [26] Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D. Manning, Andrew Ng, and Christopher Potts.  Recursive deep models for semantic compositionality over a sentiment treebank.  In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 1631–1642, Seattle, Washington, USA, October 2013. Association for Computational Linguistics.


# Experimental Analysis of Communication Relaying Delay in Low-Energy Ad-hoc
Networks

Taichi Miya1, Kohta Ohshima2, Yoshiaki Kitaguchi1 and Katsunori Yamaoka1
1Tokyo Institute of Technology, Ookayama 2–12–1–S3–68, Meguro-ku, Tokyo,
152–8552 Japan
E-mail<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>2Tokyo University of Marine Science and
Technology, Etchujima 2–1–6, Koto-ku, 135–8533 Japan
E-mail<EMAIL_ADDRESS>
###### Abstract

In recent years, more and more applications use ad-hoc networks for local M2M
communications, but in some cases such as when using WSNs, the software
processing delay induced by packets relaying may not be negligible. In this
paper, we planned and carried out a delay measurement experiment using
Raspberry Pi Zero W. The results demonstrated that, in low-energy ad-hoc
networks, processing delay of the application is always too large to ignore;
it is at least ten times greater than the kernel routing and corresponds to
30% of the transmission delay. Furthermore, if the task is CPU-intensive, such
as packet encryption, the processing delay can be greater than the
transmission delay and its behavior is represented by a simple linear model.
Our findings indicate that the key factor for achieving QoS in ad-hoc networks
is an appropriate node-to-node load balancing that takes into account the CPU
performance and the amount of traffic passing through each node.

###### Index Terms:

Ad-hoc network, processing delay, measurement experiment, Raspberry Pi Zero W

##  I Introduction and Related Works

An ad-hoc network is a self-organizing network that operates independently of
pre-existing infrastructures such as wired backbone networks or wireless base
stations by having each node inside the network behave as a repeater. It is a
kind of temporary network that is not intended for long-term operation. Every
node of an ad-hoc network needs to be tolerant of dynamic topology changes and
have the ability to organize the network autonomously and cooperatively.

Because of these specific characteristics, since the 1990s, ad-hoc networks
have played an important role as a mean for instant communication in
environments where the network infrastructure is weak or does not exist, such
as developing countries, disaster areas, and battle fields. However, in recent
years, the ad-hoc network is also a hot topic in urban areas where the
broadband mobile communication systems are well developed and always
available. More and more applications use ad-hoc networks for local M2M
communications, especially in key technologies that are expected to play a
vital role in future society, such as intelligent transportation systems (ITS)
supporting autonomous car driving, cyber-physical systems (CPS) like smart
grids, wireless sensor networks (WSN), and applications like the IoT platform.

These days, communication entities are shifting from humans to things; the
network infrastructures tend to require a more strict delay guarantee, and the
ad-hoc network is no exception. There have been many prior studies about
delay-aware communication in the field of ad-hoc networks[1, 2, 3, 4]. Most of
these focus on the link delay and only a few consider both node and link
delays[1, 2]. However, in some situations where the power consumption is
severely limited (e.g., with WSN), the communication relaying cost of small
devices with low-power processors may not be negligible for the end-to-end
delay of each communication.

It is necessary to discuss, on the basis of actual data measured on wireless
ad-hoc networks, how much the link and node delays account for the end-to-end
delay. In the field of wired networks, there have been many studies reporting
measurement experiments of packet processing delay as well as various
proposals for performance improvement[5, 6, 7, 8, 9, 10]. In addition, the
best practice of QoS measurement has been discussed in the IETF[11]. In the
past, measurement experiments on ASIC routers have been carried out for the
purpose of benchmarking routers working on ISP backbones[5, 6, 7]; in
contrast, since the software router has emerged as a hot topic in the last few
years, recent studies mainly concentrate on the bottleneck analysis of the
Linux kernel’s network stack[8, 10, 9]. There has also been a study focusing
on the processing delay caused by the low-power processor assuming
interconnection among small robots[12]. However, as far as we know, no similar
measurement exists in the field of wireless ad-hoc networks. Therefore, many
processing delay models have been considered so far, e.g., simple linear
approximation [13] or queueing model-based nonlinear approximation [14], but
it is hard to determine which one is the most reasonable for wireless ad-hoc
networks.

In this work, we analyze the communication delay in an ad-hoc network through
a practical experiment using Raspberry Pi Zero W. We assume an energy-limited
ad-hoc network composed of small devices with low-power processors. Our goal
is to support the design of QoS algorithms on ad-hoc networks by clarifying
the impact of software packet processing on the end-to-end delay and
presenting a general delay model to which the measured delay can be adapted.
This is an essential task for future ad-hoc networks and their related
technologies.

First, we briefly describe the structure of the Linux kernel network stack in
Sect. II. We explain the details of our measurement experiment in Sects. III
and IV, and report the results in Sect. V. We conclude in Sect. VI with a
brief summary and mention of future work.

##  II Network Stack of Linux Kernel

In this section, we present a brief description of the Linux kernel’s standard
network stack from the viewpoints of the packet receiving and sending
sequences.

Figure 1: Packet queueing in the Linux network stack.

###  II-A Generic Packet Receiving Sequence

Figure 1 shows the flow of packets in the network stack from the perspective
of packet queueing.

First, as the preparation for receiving packets, the NIC driver allocates
memory resources in RAM that can store a few packets, and has packet
descriptors (Rx descriptors) hold these addresses. The Rx ring buffer is a
descriptor ring located in RAM, and the driver notifies the NIC of the head
and tail addresses of the ring. The NIC then fetches some unused descriptors
by direct memory access (DMA) and waits for the packets to arrive. The
workflow after the packet arrival is as follows. As a side note, the below
sequence is a receiving mechanism called new API (NAPI) supported in Linux
kernel 2.6 or later.

  1. i)

Once a packet arrives, NIC writes the packet out as an sk_buff structure to
RAM with DMA, referring to the Rx descriptors cached beforehand, and issues a
HardIRQ after the completion.

  2. ii)

The IRQ handler receiving HardIRQ pushes it by napi_schedule() to the
poll_list of a specific CPU core and then issues SoftIRQ so as to get the CPU
out of the interrupt context.

  3. iii)

The soft IRQ scheduler receiving SoftIRQ calls the interrupt handler
net_rx_action() at the best timing.

  4. iv)

net_rx_action() calls poll(), which is implemented in not the kernel but the
driver, for each poll_list.

  5. v)

poll() fetches sk_buff referring to the ring indirectly and pushes it to the
application on the upper layer. At this time, packet data is transferred from
RAM to RAM; that is, the data is copied from the memory in the kernel space to
the receiving socket buffer in the user space by memcpy(). Repeat this memory
copy until the poll_list becomes empty.

  6. vi)

The application takes the payload from the socket buffer by calling recv().
This operation is asynchronous with the above workflows in the kernel space.
The packet receiving sequence is completed when all the payloads have been
retrieved.

###  II-B Generic Packet Sending Sequence

In the packet sending sequence, all the packets basically follow the reverse
path of the receiving sequence, but they are stored in a buffer called QDisc
before being written to the Tx ring buffer (Fig. 1).

The ring buffer is a simple FIFO queue that treats all arriving packets
equally. This design simplifies the implementation of the NIC driver and
allows it to process packets fast. QDisc corresponds to the abstraction of the
traffic queue in the Linux kernel and makes it possible to achieve a more
complicated queueing strategy than FIFO without modifying the existing codes
of the kernel network stack or drivers.

QDisc supports many queueing strategies; by default, it runs in pfifo_fast
mode. If the packet addition fails due to a lack of free space in QDisc, the
packet is pushed back to the upper layer socket buffer.

##  III Experimental Design

As discussed in Sect. I, the goal of this study is to evaluate the impact of
software packet processing, induced by packet relaying, to the end-to-end
delay, on the basis of an actual measurement assuming an ad-hoc network
consisting of small devices with low-power processors. Figure 2 shows our
experimental environment, whose details are described in Sect. IV.

###  III-A Definitions of Delays in Network

We define the classification of communication delays as below. Both processing
delay and queueing delay correspond to the application delay in a broad sense.

  * •

End-to-end delay: Total of node delays and link delays

  * •

Node delay: Sum of processing delay, queueing delays, and any processing
delays occurring in the network stack

  * •

Link delay: Sum of all other delays occurring under the NIC driver, such as
queueing delay of the NIC internal buffer, transmission delay and propagation
delay at the communication medium

  * •

Processing delay: Processing delay for packet relaying generated by the
application in user space

  * •

Queueing delay: Queueing delay at the socket buffer

###  III-B Proxy: How to Relay Packets

The proxy node (Fig. 2) relays packets with the three methods below, and we
evaluate the effect of each in terms of the end-to-end delay. By comparing the
results of OLSR and AT, we can clarify the delay caused by packets passing
through the network stack.

  * •

Kernel routing (OLSR): Proxy relays packets by kernel routing based on the
OLSR routing table. In this case, the relaying process is completed in kernel
space because all packets are wrapped in L3 of the network stack. Accordingly,
both processing delay and queueing delay defined above become zero, and node
delay is purely equal to the processing delay on the network stack in the
kernel space.

  * •

Address translation (AT): Proxy works as a TCP/UDP proxy, and all packets are
raised to the application running in the user space. The application simply
relays packets by switching sockets, which is equivalent to a fixed-length
header translation.

  * •

Encryption (Enc): Proxy works as a TCP/UDP proxy. Besides AT, the application
also encrypts payloads using AES 128-bit in CTR mode so that the relaying load
depends on the payload size.

###  III-C Measurement Conditions

For each relaying method, we conduct measurements with variations of the
following conditions. We express all the results as multiple percentile values
in order to remove delay spikes. Because the experiment takes several days, we
record the RSSI of the ad-hoc network including five surrounding channels.

  * •

Payload size

  * •

Packets per second (pps)

  * •

Additional CPU load (stress)

##  IV Measurement Methods

In this section, we explain the technical details of the experimental
environment and measurement programs.

###  IV-A Building OLSR Ad-hoc Network

We use three Raspberry Pi Zero Ws (see Table I for the hardware specs). The
Linux distributions installed on the Raspberry Pis are Raspbian and the kernel
version is 4.19.97+.

We use OLSR (RFC3626), which is a proactive routing protocol, and adopt olsrd
as its actual implementation. Since all three of the nodes are location fixed,
even if we used a reactive routing protocol like AODV instead of OLSR, only
the periodic Hello in OLSR will change the periodic RREQ induced by the route
cache expiring; that is, in this experiment, whether the protocol is proactive
or reactive does not have a significant impact on the final results.

Figure 2: Three Raspberry Pis connected logically inline. TABLE I: Hardware specs of Raspberry Pi Zero W. SoC | Broadcom BCM2835
---|---
CPU | ARM1176JZF-S (ARMv6) 1core 1GHz
RAM | LPDDR2 SDRAM 512MB
Wi-Fi | IEEE 802.11b,g,n 2.4GHz
Power | 150mA (0.75W)
Size | 65mm x 30mm (9g)

The ad-hoc network uses channel 9 (2.452 GHz) of IEEE 802.11n, transmission
power is fixed to –31 dBm, and bandwidth is 20 MHz. As WPA (TKIP) and WPA2
(CCMP) do not support ad-hoc mode, the network is not encrypted.

Figure 3: Format of UDP probe generated by iperf.

Although the three nodes can configure an OLSR mesh, as they are located
physically close to each other, we have the sender/receiver drop OLSR Hello
from the receiver/sender as well as the ARP response by Netfilter so that the
network topology becomes a logically inline single-hop network, as show in
Fig. 2.

###  IV-B Preparation of Traffic Generator

We use iperf as a traffic generator and measure the UDP performance as it
transmits packets from sender to receiver via proxy. The iperf embeds two
timestamps and a packet ID in the first 12 bytes of the UDP data section (Fig.
3), and the following measurement programs we implement use this ID to
identify each packet. Random data are generated when iperf starts getting
entropy from /dev/urandom, and the same series is embedded in all packets.

###  IV-C Implementation of the Kernel Module for Measurement

We create a loadable kernel module using Netfilter and measure the queueing
delay in receiving and sending UDP socket buffers. The workflow is summarized
as follows: the module hooks up the received packets with NF_INET_PRE_ROUTING
and the sent packets with NF_INET_POST_ROUTING (Fig. 1), retrieves the packet
IDs iperf marked by indirectly referencing the sk_buff structure, and then
writes them out to the kernel ring buffer via printk() with a timestamp
obtained by ktime_get().

###  IV-D Implementation of the Proxy

The proxy program is the application running in the user space. It creates
AF_INET sockets between sender and proxy as well as between proxy and receiver
and then translates IP addresses and port numbers by switching sockets.
Furthermore, it records the timestamps obtained by clock_gettime() immediately
after calling recv() and sendto(), and encrypts every payload data protecting
the first 12 bytes of metadata marked by iperf so as not to be rewritten. The
above refers to the UDP proxy; the TCP proxy we prepare simply using socat.

###  IV-E Additional CPU Load at Proxy

We execute a dummy process whose CPU utilization rate is limited by cpulimit
as a controlled noise of the user space in order to investigate and clarify
its impact on the node delay.

##  V Results and Discussion

We performed the delay measurement experiments under the conditions shown in
Table II using the methods described in the previous section. Due to the space
constraints, we omit the results of the preliminary experiment. Note that all
experiments were carried out at the author’s home; due to the Japanese
government’s declaration of the COVID-19 State of Emergency, we have had to
stick to the “Stay home” initiative unless absolutely necessary.

###  V-A Time Variation of Received Signal Strength Indicator

The experiment was divided into nine measurements. Figure 4 shows the time
variation of RSSI during a measurement. We were unable to obtain SNRs owing to
the specifications of the Wi-Fi driver, and thus the noise floors were
unknown, but the ESSIDs observed in the five surrounding channels were all
less than –80 dBm. The RSSI variabilities were also within the range that did
not affect the modulation and coding scheme (MCS)[15]; therefore, it appears
that the link quality was sufficiently high throughout all measurements.

(a) RSSI: Average scores for sender, proxy, and receiver.

(b) Node delay (OLSR): 1000 bytes, 200 pps, 0% stress

(c) Node delay (AT): 1000 bytes, 200 pps, 0% stress

(d) Node delay (Enc): 1000 bytes, 200 pps, 0% stress

Figure 4: Timelines: Average time variation of RSSI and 100th percentile node
delays during the measurement.

###  V-B Time Variation of Node Delay and Coffee-break Effect

Figures 4, 4, and 4 shows the average time variations of node delay, which
were the results under the condition of 1000 bytes, 200 pps, and 0% stress.
The blue highlighted bars indicate upper outliers (delay spikes) detected with
a Hampel filter ($\sigma=3$). There were 53 outliers in OLSR, 115 in AT, and 9
in Enc.

In general, when the CPU receives periodic interrupts (e.g., routing updates,
SNMP requests, GCs of RAM), packet forwarding is paused temporarily so that
the periodic delay spikes can be observed in the end-to-end delay. This
phenomenon is called the “coffee-break effect”[7] and has been mentioned in
several references[9, 5, 8].

For this experiment, as seen in the results of AT (Fig. 4), in the low-energy
ad-hoc networks, it is evident that the CPU-robbing by other processes like
coffee-break had a significant impact on the communication delay.
Incidentally, there were fewer spikes under both 1) OLSR and 2) Enc than under
AT. 1) Since the packet forwarding was completed within the kernel space, node
delay was less susceptible to applications running in the user space. 2) Since
the payload encryption was overwhelmingly CPU-intensive, the influence of
other applications was hidden and difficult to observe from the node delay.

(a) Jitter (AT)

(b) Jitter (Enc)

(c) Packet loss rate (Enc)

Figure 5: Jitter and packet loss rates: 100th percentile values under several
conditions.

(a) Node delay (OLSR): Only in-kernel delays

(b) Processing delay (AT)

(c) Processing delay (Enc)

Figure 6: Node and processing delays: 95th percentile delays under the several
conditions.

(a) Node delay (OLSR): Only in-kernel delays

(b) Processing and queueing delays (AT)

(c) Node delay (Enc)

Figure 7: Empirical Cumulative Distribution Function: Several percentile node delays under 1000 bytes, 200 pps and 0% stress. TABLE II: Parameter settings for measurement experiments. Payload size | 100, 200, 300, …, 1400 [bytes]
---|---
Packets per second | 200, 400, 600, …, 1200 [pps]
Packets per second (Enc) | 20, 40, 60, …, 400 [pps]
Additional CPU load (stress) | 0, 50, 90 [%]
Transmission duration | 5 [sec]
Number of samples | 50

###  V-C Jitter and Packet Loss Rate

Figures 5 and 5 shows the jitter of one-way communication delay. Lines
represent the average values, and we filled in the areas between the minimum
and the maximum. There were no significant differences between OLSR and AT,
which suggests that lifting packets to the application layer does not affect
jitter. Jitter increased in proportion to the payload size only in the case of
Enc.

Similarly, only in the case of Enc with 200 pps or more, the packet loss rate
tended to increase with payload size, drawing a logarithmic curve as seen in
Fig. 5; in all other cases, no packet loss occurred regardless of the
conditions.

###  V-D Node Delay

Figure 6 shows the tendency of the node delay variation against several
conditions, and Fig. 7 shows the likelihood of occurrence as empirical CDF.

According to these figures, in the cases of OLSR and AT, the delay was nearly
constant irrespective of pps and stress. There was a correlation between the
variation and pps in OLSR, while in AT there was not; this suggests that the
application-level packet forwarding is less stable than kernel routing from
the perspective of node delay. In the case of Enc, the processing delay
increased to the millisecond order and increased approximately linearly with
respect to the payload size, and the delay variance became large overall. In
addition, the graph tended to be smoothed as the pps increased; this arises
from the fact that packet encryption takes up more CPU time, which makes the
influence of other processes less conspicuous.

It appears that the higher the pps, the lower the average delay (Fig. 6 and
6), and the delay variance decreases around 1200 bytes (Fig. 6), but the
causes of these remain unknown, and further investigation is required. One
thing is certain: on the Raspberry Pi, pulling the packets up to the
application through the network stack results in a delay of more than 100
microseconds.

###  V-E Link Delay vs. Node Delay

Figure 8 shows the breakdown of the end-to-end delay and also describes the
node delay link delay ratio (NLR). As we saw in Fig. 2, for this experimental
environment, the end-to-end delay included two link delays, and the link delay
shown in Fig. 8 is the sum of them. The link delay was calculated from the
effective throughput reported in iperf. As iperf does not support pps as its
option, we achieved it by adjusting the amount of transmitted traffic, as

$bandwidth=pps\times size\times 8.$ (1)

The results showed that, in the cases of OLSR and AT, the NLR was almost
constant with respect to the payload size, while in Enc, it showed an
approximately linear increase. The NLR was less than 5% in OLSR, while in AT,
it was around 30%, which cannot be considered negligible. Furthermore, node
delay was greater than link delay when the payload size was over 1200 bytes in
Enc.

(a) E2E delay (OLSR): 400 pps, 0% stress

(b) E2E delay (AT): 400 pps, 0% stress

(c) E2E delay (Enc): 100 pps, 0% stress

Figure 8: End-to-end delay: 95th percentile end-to-end delays including node
and link delays.

##  VI Conclusion and Future Work

In this work, we have designed and conducted an experiment to measure the
software processing delay caused by packets relaying. The experimental
environment is based on an OLSR ad-hoc network composed of Raspberry Pi Zero
Ws. The results were qualitatively explainable, and suggested that, in low-
energy ad-hoc networks, there are some situations where the processing delay
cannot be ignored.

  * •

The relaying delay of kernel routing is usually negligible, but when it is
handled by application, the delay can be more than ten times greater, however
simple the task is.

  * •

If an application performs CPU-intensive tasks such as encryption or full
translation of protocol stacks, the delay increases according to the linear
model and can be greater than the link’s transmission delay.

For this reason, node-to-node load balancing considering the CPU performance
or amount of passing traffic could be extremely useful for achieving delay-
guaranteed routing in ad-hoc networks. Particularly in heterogeneous ad-hoc
networks (HANETs), where each node’s hardware specs are different from each
other, the accuracy of passing node selection would have a significant impact
on the end-to-end delay.

As we did not take any noise countermeasures in this experiment, our future
work will involve similar measurements in an anechoic chamber to reduce the
noise from external waves and an investigation of the differences in results.

## References

  * [1] T. Miya, K. Ohshima, Y. Kitaguchi, and K. Yamaoka, “The upper limit of flow accommodation under allowable delay constraint in hanets,” in 2019 16th IEEE Annual Consumer Communications & Networking Conference (CCNC). IEEE, 2019, pp. 1–2.
  * [2] Y. Miao, S. Vural, Z. Sun, and N. Wang, “A unified solution for gateway and in-network traffic load balancing in multihop data collection scenarios,” IEEE Systems Journal, vol. 10, no. 3, pp. 1251–1262, 2015.
  * [3] L. Chen and W. B. Heinzelman, “Qos-aware routing based on bandwidth estimation for mobile ad hoc networks,” IEEE Journal on selected areas in communications, vol. 23, no. 3, pp. 561–572, 2005.
  * [4] M. A. Gawas, K. Modi, P. Hurkat, and L. J. Gudino, “Qos based multipath routing in manet: A cross layer approach,” in 2017 International Conference on Communication and Signal Processing (ICCSP). IEEE, 2017, pp. 1806–1812.
  * [5] K. Papagiannaki, S. Moon, C. Fraleigh, P. Thiran, and C. Diot, “Measurement and analysis of single-hop delay on an ip backbone network,” IEEE Journal on Selected Areas in Communications, vol. 21, no. 6, pp. 908–921, 2003.
  * [6] C. Lee, C. Park, K. Jang, S. Moon, and D. Han, “Dx: Latencybased congestion control for datacenters,” IEEE/ACM Transactions on Networking, vol. 25, no. 1, pp. 335–348, 2016.
  * [7] D. Sanghi, A. K. Agrawala, O. Gudmundsson, and B. N. Jain, “Experimental assessment of end-to-end behavior on internet,” in IEEE INFOCOM’93 The Conference on Computer Communications, Proceedings. IEEE, 1993, pp. 867–874.
  * [8] L. Angrisani, G. Ventre, L. Peluso, and A. Tedesco, “Measurement of processing and queuing delays introduced by an open-source router in a single-hop network,” IEEE transactions on instrumentation and measurement, vol. 55, no. 4, pp. 1065–1076, 2006.
  * [9] A. Beifuß, D. Raumer, P. Emmerich, T. M. Runge, F. Wohlfart, B. E. Wolfinger, and G. Carle, “A study of networking software induced latency,” in 2015 International Conference and Workshops on Networked Systems (NetSys). IEEE, 2015, pp. 1–8.
  * [10] K. M. Salehin, R. Rojas-Cessa, C.-b. Lin, Z. Dong, and T. Kijkanjanarat, “Scheme to measure packet processing time of a remote host through estimation of end-link capacity,” IEEE Transactions on Computers, vol. 64, no. 1, pp. 205–218, 2013.
  * [11] G. Almes, S. Kalidindi, M. J. Zekauskas, and A. Morton, “A One-Way Delay Metric for IP Performance Metrics (IPPM),” RFC 7679, Jan. 2016. [Online]. Available: https://rfc-editor.org/rfc/rfc7679.txt
  * [12] C. S. V. Gutiérrez, L. U. S. Juan, I. Z. Ugarte, and V. M. Vilches, “Real-time linux communications: an evaluation of the linux communication stack for real-time robotic applications,” arXiv preprint arXiv:1808.10821, 2018.
  * [13] R. Ramaswamy, N. Weng, and T. Wolf, “Characterizing network processing delay,” in IEEE Global Telecommunications Conference, 2004. GLOBECOM’04., vol. 3. IEEE, 2004, pp. 1629–1634.
  * [14] S. Yashkov, “Processor-sharing queues: Some progress in analysis,” Queueing systems, vol. 2, no. 1, pp. 1–17, 1987.
  * [15] Y. Daldoul, D.-E. Meddour, and A. Ksentini, “Ieee 802.11 n/ac data rates under power constraints,” in 2018 IEEE International Conference on Communications (ICC). IEEE, 2018, pp. 1–6.