# FInC Flow: Fast and Invertible $k\times k$ Convolutions for Normalizing
Flows

Aditya Kallappa1, Sandeep Nagar1 and Girish Varma1
1International Institute of Information Technology, Hyderabad, India
{aditya.kallappa<EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

Invertible convolutions have been an essential element for building expressive
normalizing flow-based generative models since their introduction in Glow.
Several attempts have been made to design invertible $k\times k$ convolutions
that are efficient in training and sampling passes. Though these attempts have
improved the expressivity and sampling efficiency, they severely lagged behind
Glow which used only $1\times 1$ convolutions in terms of sampling time. Also,
many of the approaches mask a large number of parameters of the underlying
convolution, resulting in lower expressivity on a fixed run-time budget. We
propose a $k\times k$ convolutional layer and Deep Normalizing Flow
architecture which i.) has a fast parallel inversion algorithm with running
time O$(nk^{2})$ ($n$ is height and width of the input image and k is kernel
size), ii.) masks the minimal amount of learnable parameters in a layer. iii.)
gives better forward pass and sampling times comparable to other $k\times k$
convolution-based models on real-world benchmarks. We provide an
implementation of the proposed parallel algorithm for sampling using our
invertible convolutions on GPUs. Benchmarks on CIFAR-10, ImageNet, and CelebA
datasets show comparable performance to previous works regarding bits per
dimension while significantly improving the sampling time.

##  1 Introduction

Normalizing flow is an important subclass of Deep Generative Models that
offers distinctive benefits (Kobyzev et al.,, 2020). In comparison to GANs
(Goodfellow et al., 2014a, ) and VAEs (Kingma et al.,, 2019), they are trained
using a very intuitive Maximum Likelihood loss function. Images and the
_latent vector_ , which is required to have a Gaussian distribution,
correspond one-to-one in flow models. Despite these intriguing
characteristics, GANs and VAEs are utilized more frequently. This is due to
the need for the Normalizing Flows transformations to be invertible, which
significantly restricts the neural network types employed. For deployment in a
real-world scenario, the invertible transformations must be efficiently
calculable in the forward and sample stages.

A significant breakthrough came with Glow (Kingma and Dhariwal,, 2018) which
used $1\times 1$ invertible convolutions to design normalizing flows. If it
exists, the inverse function for a $1\times 1$ convolution also happens to be
a $1\times 1$ convolution. Since computing $1\times 1$ convolution has fast
parallel algorithms for which running time does not depend on the spatial
dimensions, they are also highly efficient in forward pass (i.e. computing
_latent vector_ from an image) as well as the sampling passes (i.e. computing
image from a sampled _latent vector_). Extending Glow to use invertible
$k\times k$ convolutions promises to improve the expressivity further,
allowing it to model more complex datasets. However, this is a challenging
problem since the inverse function for a $k\times k$ convolution, in general,
is given by a $n^{2}\times n^{2}$ matrix where $n=H=W$ (i.e. the spatial
dimensions). Hence, while the forward pass can be fast, the trivial approach
for the sampling pass will cost $O(n^{4})$ operations per convolutional layer.

Figure 1: Convolution of a $3\times 3$ _TL_ (Top Left) padded image with a
$2\times 2$ filter viewed as a linear transform of vectorized input($x$) by
the convolution matrix M. The _TL_ padding on the input results in the making
matrix M lower triangular, and all diagonal values correspond to $w_{k,k}$ of
the filter. Each row of M can be used to find a pixel value. The rows or
pixels with the same color can be inverted in parallel since all the other
values required for computing them will already be available at a step of our
inversion algorithm 1.

CInC Flow (Nagar et al.,, 2021) introduced a padded $3\times 3$ convolution
layer design and gave it the necessary and sufficient conditions to make it
invertible. They showed that the convolution matrix is lower triangular by
ensuring padding in only two sides of the input. Furthermore, all the diagonal
entries of the convolution matrix are equal to a single weight parameter. By
setting this parameter to 1, they ensured that the convolutions are
invertible, and Jacobian is always 1.

We build on their work by proposing a parallel inversion algorithm for their
convolution design. The parallel algorithm only uses O$(nk^{2})$ sequential
operations, unlike O$(n^{2}k^{2})$ operations used by most previous works. We
also build a normalizing flow architecture, where channel-wise splitting is
further used to parallelize operations.

#### Our Contributions.

  1. 1.

We design a $k\times k$ invertible convolutional layer with a fast and
parallel invertible sampling algorithm (see Sections 4.1, 4.2).

  2. 2.

We build a normalizing flow architecture based on the fast invertible
convolution, which uses channel wise splitting to improve the parallelism
further (see Sections 4.3, 4.4).

  3. 3.

We provide a fast GPU implementation of our parallel inversion algorithm and
benchmark the sampling times of the model (see Section 5). We show greatly
improved sampling times due to our parallel inversion algorithm, while giving
similar bits per dimensions as compared to other works.

Method | # of ops | # params / CNN layer | Complexity of Jacobian | Inverse
---|---|---|---|---
FInC Flow (our) | $(2n-1)k^{2}$ | $k^{2}-1$ | 1 | exact
Woodbury (Lu and Huang,, 2020) | $cn^{2}$ | $k^{2}$ | O$(d^{2}(c+n)+d^{3})$ | exact
MaCow (Ma et al.,, 2019) | $4nk^{2}$ |  $k(\lceil\frac{k}{2}\rceil-1$) | O$(n^{3})$ | exact
Emerging (Hoogeboom et al.,, 2019) | $2n^{2}k^{2}$ |  $k(\lceil\frac{k}{2}\rceil-1$) | O$(n)$ | exact
CInC Flow (Nagar et al.,, 2021) | $n^{2}k^{2}$ | $k^{2}-1$ | 1 | exact
MintNet (Song et al.,, 2019) | $3n$ | $\frac{k^{2}}{3}$ | O$(n)$ | approx
SNF (Keller et al.,, 2021) | $k^{2}$ | $k^{2}$ | approx | approx
Table 1: Comparison of the learnable parameters. where $n\times n$ is input
size, $k\times k$ is filter size which is constant, $c$ is number of
input/output channels. $d$ is the number of latent dimensions. # of ops:
required number of operations for the inversion of convolutional layers. The
complexity of Jacobian: Time complexity for calculating the Jacobian of a
single convolution layer. For FInC Flow and CInC Flow, the Jacobian is 1,
since the Convolution matrix is lower triangular with diagonal entries being
1.

##  2 Related Work

#### Generative Modeling.

The idea of generative modeling stems from training a generative model whose
sample comes from the same distribution as the training data distribution.
Most of the generative models can be grouped as Generative adversarial
networks (GANs) (Goodfellow et al., 2014b, ; Brock et al.,, 2019), Energy-
based models (EBMs) (Zhang et al.,, 2022; Song et al., 2021a, ), Variational
autoencoders (VAEs) (Kingma and Welling,, 2013; Kingma et al.,, 2019; Hazami
et al.,, 2022), Autoregressive models (Oord et al.,, 2016; Nash et al.,,
2020), Diffusion models (Ho et al.,, 2020; Song et al., 2021b, ; Song and
Ermon,, 2019) and Flow-based models (Dinh et al.,, 2014, 2017; Hoogeboom et
al.,, 2019; Kingma and Dhariwal,, 2018; Ho et al.,, 2019; Ma et al.,, 2019;
Nagar et al.,, 2021).

#### Normalizing Flows.

Flows-based models construct complex distributions by transforming a
probability density through a series of invertible mappings (Rezende and
Mohamed,, 2015). At the end of these invertible mapping, we obtain a valid
distribution; hence, this type of flow is referred to as a Normalizing Flow
model. Flow models apply the rule for change of variables; the initial density
‘flows’ through the sequence of invertible mappings (Dinh et al.,, 2017).
Flow-based models generalize a dataset distribution into a latent space
(Kobyzev et al.,, 2020).

#### Invertible kxk Convolutions.

An invertible neural network requires the inverse of the network with fast and
efficient computation of the Jacobian determinant (Song et al.,, 2019). An
invertible neural network can be used for generation and classification with
more interpretability. (Kingma and Dhariwal,, 2018) proposed an invertible
$1\times 1$ convolution building on top of NICE (Dinh et al.,, 2014) and
RealNVP (Dinh et al.,, 2017) consisting a series of flow step combined in a
multi-scale architecture. Each flow step consists of actnorm followed by an
invertible $1\times 1$ convolution, followed by a coupling layer (see Sec
4.3). Emerging (Hoogeboom et al.,, 2019) presented method to generalized
$1\times 1$ convolution to invertible $k\times k$ convolutions. Emerging
chains two specific auto regressive convolutions (Kingma and Welling,, 2013)
to form a single convolutional layer following the associativity of the
convolution operation. Each of these autoregressive convolutions is chosen
such that the resulting convolution matrix $\mathbf{M}$ is triangular with an
inverse time of each of the convolutions is O$(n\times n\times k^{2})$.
MintNet (Song et al.,, 2019) presented a method for designing invertible
neural networks by combining building blocks with a set of composition rules.
The inversion of the proposed blocks necessitates a sequence of dependent
computations that increase the network’s sampling time. SNF (Keller et al.,,
2021) proposed a method to reduce the computation complexity of the Jacobian
determinant by replacing the gradient term with a learned approximate inverse
for each layer. This method avoids the determinant of Jacobian and makes it
approximate, and requires an additional backward pass for inversion of
convolution. MaCow (Ma et al.,, 2019) while many other papers make use of the
invertibility of triangular matrix to reduce inversion time, MaCow outperforms
all of them by performing the inverse in O$(nk^{2})$ by carefully masking $4$
kernels at the top, left, bottom, right to achieve a full convolution, but
this flow model use four autoregressive convolutions to make an effective
standard convolution. Woodbury (Lu and Huang,, 2020) this paper employs the
_Woodbury transformation_ for invertible convolution, which is a generalized
permutation layer that models dimension dependencies along the channel and
spatial axes using the channel and spatial transformation. ButterflyFlow (Meng
et al.,, 2022) introduced a new family of an invertible layer that works for
special underlying structures and needs a sequence of layers for an effective
invertible convolution.

#### Fast Algorithms for Invertible Convolutions.

CInC Flow (Nagar et al.,, 2021), derive necessary and sufficient conditions on
a padded CNN for it to be invertible and require a single CNN layer for every
effective invertible CNN layer. The padded CNN can leverage the advantage of
parallel computation for inversion, resulting in faster and more efficient
computation of Jacobian determinants.

The distinguishing feature of our invertible convolutions as compared to
previous works is that we have a parallel inversion algorithm that does only
$(2n-1)k^{2}$ operations where $n$ is input size and $k$ is kernel size. MaCow
is the closest approach that takes twice the number of operations. Some of the
approaches, like MintNet and SNF, do achieve a lesser number of operations.
However, they are not proper normalizing flows as they compute only an
approximate inverse. We use the convolution design from CInC Flow but give a
parallel inversion algorithm for it. Furthermore, our FInC Flow _Unit_ is
designed to efficiently parallelize the operations by splitting the
convolution operations channel-wise. In Table 1, we compare our proposed flow
model with the existing model in terms of the receptive fields/number of
learnable parameters, complexity of computing the inverse of convolution layer
for sampling.

##  3 Preliminaries

#### Normalizing Flows.

Formally, Normalizing Flows is a series of transformations of a known simple
probability density into a much more complex probability density using
invertible and differentiable functions. These invertible function allows to
write the probability of the output as a differentiable function of the model
parameters. As a result, the models can be trained using backpropagation with
the negative log likelihood loss function.

Let $\mathbf{X}\in\mathbb{R}^{d}$ be a random variable with tractable density
$p_{\mathbf{X}}$. Let $f:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$ be a
differentiable and invertible function. If $\mathbf{Y}=f(\mathbf{X})$ then the
density of $Y$ can be calculated as

$p_{X}(x)=p_{Y}(y)\left|\det J_{f}\right|\qquad\text{ where }\qquad
J_{f}=\frac{\partial f(x)}{\partial x}.$

Note that $J_{f}$ is a $d\times d$ matrix called the Jacobian. If $X$ is
transformed using a sequence of functions $f_{i}$’s. That is $f=f_{1}\circ
f_{2}\circ f_{3}\circ\cdots\circ f_{r}$. Now probability density, $p_{Y}(y)$
can be expressed as

$p_{Y}(y)=p_{X}(f^{-1}(y))\cdot\displaystyle\prod_{i=r}^{1}|J_{f_{i}^{-1}}(y_{i})|.$
(1)

where $y_{i}=f_{i}^{-1}\circ\cdots\circ f_{r}^{-1}(x)$. The log-probability of
$p_{Y}$ which will be used to model the complex image distribution is given
by,

$\log p_{Y}(y)=\log p_{X}(f^{-1}(y_{r}))+\displaystyle\sum_{i=1}^{r}\log|\det
J_{f^{-1}_{i}}(y_{i})|.$ (2)

The functions $f_{i}^{-1}$ will be given by neural network layers and the
above function can be computed during the forward pass of the neural network.
The negative of this function called the negative log likelihood (NLL) is
minimized when images in the dataset are given highest probabilities. Hence it
gives a simple, interpretable loss function for training the model.

Figure 2: (a) FInC Flow unit: to utilize the independence of convolution on
channels the input channels are sliced into four equal parts and then padded
(1. top-left, 2. top-right, 3. bottom-right, 4. bottom-left) to keep the input
size and output size same. Next, parallelly convoluted each sliced channel
with the corresponding masked kernel (masked corner of kernels: 1. bottom-
right, 2. bottom-left, 3. top-left, 4. top-right). Finally, concatenate the
output from each convolution. (b) We propose a FInC Flow architecture 4.3
where each FInC Flow _Step_ consists of an actnorm step, followed by an
invertible 1 × 1 convolution, followed by coupling layer. (c) Flow is combined
with a multi-scale architecture 4.4.

#### Invertible Convolutions.

The convolution of an input $X$ with shape $H\times W\times C$ with a kernel
$K$ with shape $k\times k\times C\times C$ is $Y=X\times K$ of shape
$(H-(k+1))\times(W-(k+1))\times C$ which is equal to

$Y_{i,j,c_{o}}=\sum_{l,h<k}\sum_{c_{i}=1}^{C}X_{i+l,j+k,c_{i}}K_{l,k,c_{i},c_{o}}$
(3)

Notice that the dimensions of $X$ and $Y$ are not necessarily the same. To
ensure that the $X$ and $Y$ are the same size, we apply padding to the input
$X$. For an input image $X$ with shape $H\times W\times C$, the $(t,b,l,r)$
padding of $X$ is the image $\hat{X}$ of shape $(H+t+b)\times(W+l+r)\times C$
is defined as

$\hat{X}_{i,j,c}=\begin{cases}X_{i-t,j-l,c}&\text{if }i-t<H\text{ and
}j-l<W\\\ 0&\text{otherwise}\end{cases}$ (4)

The convolution operation is a linear transformation of the input. For the
vectored (flattened) input $X$, denoted by $x$, the output vector $y$ can be
written as $y=\mathbf{M}x$. Matrix $\mathbf{M}$ is the called as the
_Convolution Matrix_ and the dimensions of this matrix is $HWC\times HWC$. As
long as matrix $\mathbf{M}$ is invertible, the convolutional layer can be
included as a part of the Normalizing Flows. The common approach to building
invertible convolutions is by making $M$ upper triangular and ensuring
invertibility by making diagonal entries to be nonzero.

#### Algorithms for Computing Inverse of Convolutions.

For normalizing flows built using invertible convolutions, the sampling pass
will involve computing the inverse of the convolution matrix. This involves
solving a linear systems of equations $\textbf{M}x=y$.

For a general square matrix of size $n\times n$, the time complexity for
inversion is $O(n^{3})$. For a lower triangular matrix of size $n\times n$,
the time complexity for inversion is $O(n^{2})$ because of back-substitution
method. Notice that the size of convolution matrix, M) is $n^{2}\times n^{2}$
(refer Figure 1) and also that row of the matrix has only $k^{2}$ entries at
the maximum, results in an inversion time of $O(n^{2}k^{2})$ which is used in
many of the previous works like Emerging and CInC Flows. We show that this
method can be parallelized for carefully designed convolutions giving a
complexity of only $O(nk^{2})$.

##  4 FInC Flow: Our Approach

In this section we describe our approach including convolution layer design
which has a fast parallel inversion algorithm with running time O$(nk^{2})$.
For more clarity, we refer to height of the image as $H$, width as $W$ and
channels as $C$ in this section.

###  4.1 Convolution Design

As it is obvious from equation $x=\textbf{M}^{-1}y$, the inverse timings
depends on $\mathbf{M}$. Emerging (Behrmann et al.,, 2019) masks almost half
of the convolution kernel values to ensure M is a Lower Triangular Matrix.
However, we follow the method followed in CInC Flow, where only a few values
of the convolution kernel are masked. For an input image $X$ with shape
$H\times W\times C$, the top-left(_TL_) i.e., $(t,0,l,0)$ padding of $X$ is
the image $X^{\text{(TL)}}$ of shape $(H+t)\times(W+l)\times C$ is defined in
equation 5 and similarly for the top-right (_TR_) as equation 6, bottom-left
(_BL_) as equation 7, bottom-right (_BR_) as equation 8.

$\displaystyle X^{\text{(TL)}}_{i,j,c}$
$\displaystyle=\begin{cases}X_{i-t,j-l,c}&i-t>0~{}\wedge~{}j-l>0\\\
0&\text{otherwise}\end{cases}$ (5) $\displaystyle X^{\text{(TR)}}_{i,j,c}$
$\displaystyle=\begin{cases}X_{i-t,j,c}~{}~{}~{}&i-t>0~{}\wedge~{}j-r<W\\\
0&\text{otherwise}\end{cases}$ (6) $\displaystyle X^{\text{(BL)}}_{i,j,c}$
$\displaystyle=\begin{cases}X_{i,j-l,c}~{}~{}~{}~{}&i-b<H~{}\wedge~{}j-l>0\\\
0&\text{otherwise}\end{cases}$ (7) $\displaystyle X^{\text{(BR)}}_{i,j,c}$
$\displaystyle=\begin{cases}X_{i,j,c}~{}~{}~{}~{}~{}~{}~{}~{}&i-b<H~{}\wedge~{}j-r<W\\\
0&\text{otherwise}\end{cases}$ (8)

Figure 1 shows the convolution of a _TL_ padded $3\times 3$ image with a
$2\times 2$ filter is equivalent to a matrix multiplication between
convolution matrix M and vectored input $x$. We leverage this to find the
inverse faster. We discuss this in more detail in the subsequent sections.
Also padded input $X^{\text{(TR)}}$, $X^{\text{(BL)}}$ and $X^{\text{(BR)}}$
are equivalent to $X^{\text{(TL)}}$ once they are flipped along corresponding
dimension(s).

Input: $K$: Kernel of shape $(C,C,k_{H},k_{W})$

$Y$: output of the conv of shape $(C,H,W)$

Result: $X$: inverse of the conv. with shape $(C,H,W)$.

1 Initialization: $X\leftarrow Y$ ;

2 for  _$d\leftarrow 0,H+W-1$_ do

3 for  _$c\leftarrow 0,C-1$_ do

/* The below lines of code executes parallelly on different threads on GPU for
every index $(c,h,w)$ of $X$ on the $d$th diagonal. */

4

5 for  _$k_{h}\leftarrow 0,k_{H}-1$_ do

6 for  _$k_{w}\leftarrow 0,k_{W}-1$_ do

7 for  _$k_{c}\leftarrow 0,C-1$_ do

8 if  _pixel $(k_{c},h-k_{h},w-k_{w})$ not out of bounds_ then

9 $X[c,h,w]\leftarrow
X[c,h,w]-X[k_{c},h-k_{h},w-k_{w}]*K[c,k_{c},k_{H}-k_{h}-1,k_{W}-k_{w}-1];$

10 end if

11

12 end for

13

14 end for

15

16 end for

/* synchronize all threads */

17

18 end for

19

20 end for

Algorithm 1 Fast Parallel Inversion Algorithm of _TL_ padded convolution
block(PCB)

###  4.2 Parallel Inversion Algorithm

We have presented our algorithm in Algorithm 1. The algorithm can be
understood using Figure 1.

######  Definition 1 (Diagonal Elements).

Two pixels $x_{i,j}$ and $x_{i^{\prime},j^{\prime}}$ are said to be secondary
diagonal elements if $i+i^{\prime}=j+j^{\prime}$ . For brevity, we refer to
these elements from here on simply as Diagonal Elements.

Theorem 1 proves that every element of on the diagonal can be computed
parallelly and Line 2 of the algorithm takes care of that. We initialize $X$
to $Y$ in Line 1 and compute $X$ in Line 8 which is given in Equation 10. It
is important that we wait for the threads to synchronize before we move to the
next diagonal, as they are needed for computing the elements of the next
diagonal. The _not out of bounds_ in Line 7 means we are remaining in the
$k\times k$ convolution window and also we are not including pixel $(i,j)$
while computing $x_{i,j}$ as given in Equation 10

######  Theorem 1.

The inverse of the pixels on the diagonals of a TL padded convolution can be
computed independently and parallelly.

###### Proof.

The $(i,j)^{th}$ pixel value of the output $Y$ with shape $H\times W$ can be
calculated as

$y_{i,j}=(\textbf{M}_{iW+j,:})^{T}\cdot x$

which means $y_{i,j}$ is the dot product of $\textbf{M}_{iW+j,:}$ i.e., the
corresponding row of matrix M and the vectored input $x$. Because it is a _TL_
padded convolution, $y_{i,j}$ depends only on the values of $k\times k$ window
of $x_{\leq i,\leq j}$ pixels where $x_{\leq i,\leq j}$ are the pixels that
are on the top and left side of the pixel $x_{i,j}$ including $x_{i,j}$.
Because all the diagonal values are $w_{k,k}$, we have,

$\displaystyle y_{i,j}$ $\displaystyle=w_{k,k}x_{i,j}+f(x_{<i,<j})$
$\displaystyle x_{i,j}$ $\displaystyle=\frac{y_{i,j}-f(x_{<i,<j})}{w_{k,k}}$

where $x_{<i,<j}$ are the pixels which are strictly top and left side of
$(i,j)$. Following the masking pattern of CInC Flow, we have $w_{k,k}=1$ and
$f$ is a linear function which is given by weighted sum of the given pixels
weighed by the filter values. So,

$x_{i,j}=y_{i,j}-f(x_{<i,<j})$ (9)
$x_{i,j}=y_{i,j}-\sum_{p=0}^{k}\sum_{q=0}^{k}x_{i-p,j-q}K_{p,q}\text{ where
}p=q\neq 0$ (10)

Let two pixels $x_{i,j}$ and $x_{i^{\prime},j^{\prime}}$ be on the same
diagonal. This also means that only one of the following settings is true a)
$i<i^{\prime}$ and $j>j^{\prime}$ or b) $i>i^{\prime}$ or $j<j^{\prime}$.
Either way, we can conclude that computation of $x_{i,j}$ is not dependent on
$x_{i^{\prime},j^{\prime}}$ and vice versa following the result in Equation 9.
Hence they can be computed independently. Once $x_{i,j}$ is computed,
following the Equation 9 and the above result, we can compute $x_{i+1,j}$ and
$x_{i,j+1}$. Since, the sets of pixels $x_{<i+1,<j}$ and $x_{<i,<j+1}$ both
include the elements of $x_{<i,j}$ and also $x_{i,j}$, we can write

$\displaystyle x_{i+1,j}$ $\displaystyle=y_{i+1,j}-f(x_{<i+1,<j})$
$\displaystyle=y_{i+1,j}-\alpha x_{i,j}-f_{1}(x_{<i,<j})$ (11) $\displaystyle
x_{i,j+1}$ $\displaystyle=y_{i,j+1}-f(x_{<i,<j+1})$
$\displaystyle=y_{i,j+1}-\beta x_{i,j}-f_{2}(x_{<i,<j})$ (12)

where $\alpha$ and $\beta$ are kernel weights.

From Equations 11 and 12, we can conclude that $x_{i+1,j}$ and $x_{i,j+1}$
which are on the same diagonal can be calculated parallelly in a single step.
∎

######  Theorem 2.

Algorithm 1 uses only $(H+W-1)k^{2}$ sequential operations.

###### Proof.

We have proved in Theorem 1 that the inverse pixels on a single diagonal can
be computed parallelly in one iteration of Algorithm 1. Since there are
$H+W-1$ number of diagonals in a matrix and there are at maximum $k^{2}$
entries in a row of the convolutional matrix, the number of sequential
operations needed will be $(H+W-1)k^{2}$. ∎

Thus the running time of our algorithm is O$(nk^{2})$ where $n=H=W$

Table 2: Comparison of the bits per dimension (BPD), forward pass time (FT)
and sampling time (ST) on standard benchmark datasets of various $k\times k$
convolution based Normalizing Flow models. FT and ST are presented in seconds.

Model | MNIST | CIFAR-10 | Imagenet-32x32 | Imagenet-64x64
---|---|---|---|---
| BPD | FT | ST | BPD | FT | ST | BPD | FT | ST | BPD | FT | ST
Emerging | – | 0.16 | 0.62 | 3.34 | 0.49 | 17.19 | 4.09 | 0.73 | 25.79 | 3.81 | 1.71 | 137.04
MaCow | – | – | – | 3.16 | 1.49 | 3.23 | – | – | – | 3.69 | 2.91 | 8.05
CInC Flow | – | – | – | 3.35 | 0.42 | 7.91 | 4.03 | 0.62 | 11.97 | 3.85 | 1.57 | 55.71
MintNet | 0.98 | 0.16 | 17.29 | 3.32 | 2.09 | 230.17 | 4.06 | 2.08 | 230.44 | – | – | –
FInC Flow (our) | 1.05 | 0.14 | 0.09 | 3.39 | 0.37 | 0.41 | 4.13 | 0.48 | 0.52 | 3.88 | 1.43 | 2.11

###  4.3 FInC Flow Unit

Figure 2a visualizes our $k\times k$ convolution block. We call this block as
FInC Flow _Unit_. We use all the $4$ padding techniques mentioned before to
different channels of the image. For this purpose, we split the input into
four equal parts along the channel axis. We do _TL_ padding to the first part,
_TR_ to the second part, _BL_ to the third part and _TR_ to the fourth part.
Then we use a masked filter on each of these parts to perform the convolution
operation parallelly. We call each of this padded image along with it’s
corresponding kernel as Padded Convolution Block (PCB).

###  4.4 Architecture

Figure 2c shows the complete architecture of our model. Our model architecture
resembles the architecture of Glow. The multi-scale architecture involves a
block of a Squeeze layer, FInC Flow _Step_ repeated $K$ number of times and a
Split layer. The whole block is repeated $L-1$ number of times. A Squeeze
layer follows this and finally FInC Flow _Step_ repeated $K$ times. At the end
of each split layer, half of the channels are ’split’ (taken away) and modeled
as Gaussian distribution samples. These splited half channels are _latent
vectors_. The same is done for the output channels. These are denoted as
$z_{L}$ in Figure 2(c). Each _FInC Flow Step_ consists of a _FInC Flow Unit_ ,
an Actnorm Layer, a $1\times 1$ Convolutional Layer, followed by a coupling
layer.
Actnorm Layer: Acts as an activation normalization layer similar to that of a
batch normalization layer. Introduced in Glow, this layer performs the affine
transformation using scale and bias parameters per channel.
$1\times 1$ Convolutional Layer: This layer introduced in Glow does a $1\times
1$ convolution for a given input. Its log determinant and inverse are very
easy to compute. It also improves the effectiveness of coupling layers.
Coupling Layer: RealNVP introduced a layer in which the input is split into
two half. The first half remains unchanged, and the second half is transformed
and parameterized by the first half. The output is concatenation of first half
and the affine transformation, by functions parameterized by the first, of
second half. The inverse and log determinant of coupling layer are computed in
a straightforward manner. Coupling layer consists of $3\times 3$ convolution
followed by a $1\times 1$ and a modified $3\times 3$ convolution used in
Emerging.
Squeeze: This layer takes features from spatial to channel dimension (Behrmann
et al.,, 2019), i.e., it reduces the feature dimension by total four, two
across the height dimension and two across the width dimension resulting in
increases the channel dimension by four. As used by (Dinh et al.,, 2017), we
use squeeze layer to reshape the feature maps to have smaller resolution but
more channels.
Split: Input is splited into two halves across the channel dimension. We
retain the first half, and a function parameterized by first half transform
the second half. The transformed second half is modeled as Gaussian samples,
are the _latent vectors_. We do not use the checkerboard pattern used in
RealNVP (Dinh et al.,, 2017) and many others to keep the architecture simple.

Table 3: CIFAR-10: comparison of learnable parameters and the sampling time. FInC Flow has less number of learnable parameters with the same receptive field and fast layers (all the times are averaged over ten loops for n = 100 sample images in seconds). ST = Sample time, FT = Forward Time. MaCow-FG is the fine-grained MaCow model and MaCow-org stands for MaCow model utilizes the original multi-scale architecture which is the same as Glow. MaCow and our method is closely similar in term of the convolutional design. So, here we show that our proposed method do fast sampling while maintaining the faster forward time . Models | Setting (K and L) | Learnable params (M = million) | FT(n=100) | ST(n=100)
---|---|---|---|---
MaCow-FG | [4, [12, 12], [12, 12], 12] | 37.19M | 0.88 | 2.64
MaCow-org | [4, [12, 12], [12, 12], 12], [4, 4] | 38.4M | 1.48 | 3.23
FInC Flow (our) | [28, 28, 28] | 39.46M | 0.37 | 0.41

##  5 Results

#### Bits Per Dimension (BPD):

BPD is closely related to NLLLoss given in equation 2. BPD of $H\times W\times
C$ image is given by

$\text{bpd}=\frac{\text{NLLLoss}\times\log_{2}{e}}{HWC}$ (13)

Table 2 shows the BPD comparative results of various models with our model. We
present the results of MaCow-var which uses Variational Dequantization which
was introduced in Flow++ (Ho et al.,, 2019). BPDs recorded are the reported
numbers from the respective model papers.

#### Sampling Time:

Figure 3: Sampling Times for four models - our, Emerging, CInC Flow, MaCow.
Each plot gives the $95\%$ Confidence Interval (CI) time of the ten runs to
sample $100$ images. X-axis represents the sizes of the image sampled starting
from $16\times 16\times 2$ ($H\times W\times C$) all the way to $128\times
128\times 2$.  Figure 4: Comparison of (a) original and (b) reconstructed
image samples for the $64\times 64$ CelebA dataset after FInC Flow model for
$100$ epochs. From the images, we can conclude our model reconstruct original
image.

Table 2 shows the comparative results of our model with other models. For
MaCow, we use the official code released by the authors. We use the code for
Emerging, which was implemented in PyTorch by the authors of SNF.. We have
implemented CInC Flow in PyTorch and used it to generate results. The FTs and
STs are recorded by averaging ten runs on untrained models (including our
model).

Figure 5: Uncurated generated samples images from our flow model.

In Figure 3, we plot the relationship between the input image size and inverse
sampling time. As the input image size increase, our _Parallel Inversion
Algorithm_ improve by utilizing the independence in the convolution matrix
$M$. If we input a single image (batch size = $1$), our model performs
similarly to the CInC Flow and Emerging. MaCow is far slower because it does
the masking of four kernels to maintain the receptive field. To do one
convolution, it needs four convolutions to complete one standard convolution,
making it slower. Emerging requires two consecutive autoregressive
convolutions to have the same receptive field as standard convolution and
solver compared to FInC Flow. For batch size = $4$ and larger, FInC Flow beats
the Emerging, MaCow , and CInC Flow by a big difference (see Figure 3) while
maintaining the same receptive field.

#### Scaling sampling time with spatial dimensions:

Table 3 shows the comparison among the invertible convolution-based models. To
keep it fair, we restrict the total parameters across all the models to be
close to $5$ M. We note down the average sampling time (ST) to generate $100$
images over ten runs while doubling the size of the sampled image from
$16\times 16$ all the way to $128\times 128$ and also doubling our batch size
from $1$ all the way to $128$. Our model outperforms all the other models in
most, if not all, the settings. All the models were untrained and run on a
single NVIDIA GTX 1080Ti GPU.

#### Image reconstruction and generation:

In Figure 4, we present the effectiveness of the FInC Flow model in the
reconstruction (sampling) of the images. First, we feed the input image to
forward flow and get the _latent vector_ ($z_{L}$). To reconstruct the images
from the _latent vector_ ($z_{L}$), give the $z$ as input to the inverse flow.
Figure 4 present the reconstructed face images for the CelebA dataset after
training our model for $100$ epochs. The model takes a random sample from the
Gaussian distribution for the _latent vector_ to generate sample images. This
_latent vector_ is used to generate images by going backward in the flow
model. In Figure 5, we present generated sample by our model on the MNIST,
CIFAR-10, and ImageNet-64x64 dataset.

##  6 Conclusion

With a parallel inversion approach, we present a $k\times k$ invertible
convolution for Normalizing flow models. We utilize it to develop a model with
highly efficient sampling pass, normalizing flow architecture. We implement
our parallel algorithm on GPU and presented benchmarking results, which show a
significant enhancement in forward and sampling speeds when compared to
alternative methods for $k\times k$ invertible convolution.

## REFERENCES

  * Behrmann et al., (2019) Behrmann, J., Grathwohl, W., Chen, R. T., Duvenaud, D., and Jacobsen, J.-H. (2019).  Invertible residual networks.  In International Conference on Machine Learning, pages 573–582. PMLR.
  * Brock et al., (2019) Brock, A., Donahue, J., and Simonyan, K. (2019).  Large scale GAN training for high fidelity natural image synthesis.  In International Conference on Learning Representations.
  * Deng, (2012) Deng, L. (2012).  The mnist database of handwritten digit images for machine learning research.  IEEE Signal Processing Magazine, 29(6):141–142.
  * Dinh et al., (2014) Dinh, L., Krueger, D., and Bengio, Y. (2014).  Nice: Non-linear independent components estimation.  arXiv preprint arXiv:1410.8516.
  * Dinh et al., (2017) Dinh, L., Sohl-Dickstein, J., and Bengio, S. (2017).  Density estimation using real nvp.  In International Conference on Learned Representations.
  * (6) Goodfellow, I., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., and Bengio, Y. (2014a).  Generative adversarial nets.  In Ghahramani, Z., Welling, M., Cortes, C., Lawrence, N., and Weinberger, K., editors, Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc.
  * (7) Goodfellow, I., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., and Bengio, Y. (2014b).  Generative adversarial nets.  Advances in neural information processing systems, 27.
  * Hazami et al., (2022) Hazami, L., Mama, R., and Thurairatnam, R. (2022).  Efficient-vdvae: Less is more.  arXiv preprint arXiv:2203.13751.
  * Ho et al., (2019) Ho, J., Chen, X., Srinivas, A., Duan, Y., and Abbeel, P. (2019).  Flow++: Improving flow-based generative models with variational dequantization and architecture design.  In International Conference on Machine Learning, pages 2722–2730. PMLR.
  * Ho et al., (2020) Ho, J., Jain, A., and Abbeel, P. (2020).  Denoising diffusion probabilistic models.  Advances in Neural Information Processing Systems, 33:6840–6851.
  * Hoogeboom et al., (2019) Hoogeboom, E., Van Den Berg, R., and Welling, M. (2019).  Emerging convolutions for generative normalizing flows.  In International Conference on Machine Learning, pages 2771–2780. PMLR.
  * Keller et al., (2021) Keller, T. A., Peters, J. W., Jaini, P., Hoogeboom, E., Forré, P., and Welling, M. (2021).  Self normalizing flows.  In International Conference on Machine Learning, pages 5378–5387. PMLR.
  * Kingma and Ba, (2015) Kingma, D. P. and Ba, J. (2015).  Adam: A method for stochastic optimization.  In Bengio, Y. and LeCun, Y., editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings.
  * Kingma and Dhariwal, (2018) Kingma, D. P. and Dhariwal, P. (2018).  Glow: Generative flow with invertible 1x1 convolutions.  Advances in neural information processing systems, 31.
  * Kingma and Welling, (2013) Kingma, D. P. and Welling, M. (2013).  Auto-encoding variational bayes.  arXiv preprint arXiv:1312.6114.
  * Kingma et al., (2019) Kingma, D. P., Welling, M., et al. (2019).  An introduction to variational autoencoders.  Foundations and Trends® in Machine Learning, 12(4):307–392.
  * Kobyzev et al., (2020) Kobyzev, I., Prince, S. J., and Brubaker, M. A. (2020).  Normalizing flows: An introduction and review of current methods.  IEEE transactions on pattern analysis and machine intelligence, 43(11):3964–3979.
  * Krizhevsky, (2009) Krizhevsky, A. (2009).  Learning multiple layers of features from tiny images.
  * Liu et al., (2015) Liu, Z., Luo, P., Wang, X., and Tang, X. (2015).  Deep learning face attributes in the wild.  In Proceedings of the IEEE international conference on computer vision, pages 3730–3738.
  * Lu and Huang, (2020) Lu, Y. and Huang, B. (2020).  Woodbury transformations for deep generative flows.  Advances in Neural Information Processing Systems, 33:5801–5811.
  * Ma et al., (2019) Ma, X., Kong, X., Zhang, S., and Hovy, E. (2019).  Macow: Masked convolutional generative flow.  Advances in Neural Information Processing Systems, 32.
  * Meng et al., (2022) Meng, C., Zhou, L., Choi, K., Dao, T., and Ermon, S. (2022).  Butterflyflow: Building invertible layers with butterfly matrices.  In International Conference on Machine Learning, pages 15360–15375. PMLR.
  * Nagar et al., (2021) Nagar, S., Dufraisse, M., and Varma, G. (2021).  CInc flow: Characterizable invertible 3$\times$3 convolution.  In The 4th Workshop on Tractable Probabilistic Modeling.
  * Nash et al., (2020) Nash, C., Ganin, Y., Eslami, S. A., and Battaglia, P. (2020).  Polygen: An autoregressive generative model of 3d meshes.  In International conference on machine learning, pages 7220–7229. PMLR.
  * Oord et al., (2016) Oord, A. v. d., Dieleman, S., Zen, H., Simonyan, K., Vinyals, O., Graves, A., Kalchbrenner, N., Senior, A., and Kavukcuoglu, K. (2016).  Wavenet: A generative model for raw audio.  arXiv preprint arXiv:1609.03499.
  * Rezende and Mohamed, (2015) Rezende, D. and Mohamed, S. (2015).  Variational inference with normalizing flows.  In International conference on machine learning, pages 1530–1538. PMLR.
  * Russakovsky et al., (2015) Russakovsky, O., Deng, J., Su, H., Krause, J., Satheesh, S., Ma, S., Huang, Z., Karpathy, A., Khosla, A., Bernstein, M., et al. (2015).  Imagenet large scale visual recognition challenge.  International journal of computer vision, 115(3):211–252.
  * (28) Song, Y., Durkan, C., Murray, I., and Ermon, S. (2021a).  Maximum likelihood training of score-based diffusion models.  Advances in Neural Information Processing Systems, 34:1415–1428.
  * Song and Ermon, (2019) Song, Y. and Ermon, S. (2019).  Generative modeling by estimating gradients of the data distribution.  Advances in Neural Information Processing Systems, 32.
  * Song et al., (2019) Song, Y., Meng, C., and Ermon, S. (2019).  Mintnet: Building invertible neural networks with masked convolutions.  Advances in Neural Information Processing Systems, 32.
  * (31) Song, Y., Sohl-Dickstein, J., Kingma, D. P., Kumar, A., Ermon, S., and Poole, B. (2021b).  Score-based generative modeling through stochastic differential equations.  In International Conference on Learning Representations.
  * Zhang et al., (2022) Zhang, D., Malkin, N., Liu, Z., Volokhova, A., Courville, A., and Bengio, Y. (2022).  Generative flow networks for discrete probabilistic modeling.  In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S., editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 26412–26428. PMLR.

## Additional details

Code to our implementation is available here: https://github.com/aditya-v-
kallappa/FInCFlow

#### Datasets

We train our model on standard benchmark datasets MNIST (Deng,, 2012),
CIFAR-10 (Krizhevsky,, 2009), and ImageNet (Russakovsky et al.,, 2015) sampled
down to $32\times 32$ and $64\times 64$. We also train our model on CelebA
(Liu et al.,, 2015) sampled down to $64\times 64$. Figure 4a present the
CelebA-$64\times 64$ reconstructed samples and Figure 5b for the CIFAR-10 and
ImageNet-64x64 generated samples.

#### Hyperparameters

To train our model, we use Adam optimizer (Kingma and Ba,, 2015) with learning
rate of 0.001 with an exponential decay of 0.99997 per epoch. For training on
Imagenet, we also make sure that the gradients stay between $-1$ and $+1$ by
clipping them.

#### Masking

To make sure the masked values in the Padded Conv Blocks, we ensure they are
not affected by back propagation. To achieve this, we reset the gradients of
the masked values to zero after every training iteration.

#### Cuda code details

To run CUDA code, we use PyTorch-LTS 1.8.2 and cudatoolkit 10.2. While we can
implement Algorithm 2 to find inverse of each padded block individually, we
can take advantage of the fact that all 4 Padded Conv Blocks are equivalent
after proper flipping of padded inputs and kernels. This is done by using
Algorithm 2 on GPU.

First we split $Y$ into 4 parts across channel dimension following the
architecture shown in 2. This is given in Line 1. Then we flip $Y$ and kernels
to match TL-padding which is given in Line 2. Then we concatenate them to get
the final $Y$ and $K$ respectively which are given in Lines 3 and 4. Then we
apply Algorithm 2 to find the inverse. We do the reverse process of the above
to get the correct $X$. The steps are given in Lines 5, 6, 7, 8.

We fix the number of threads of each grid of the GPU to be 1024, the number of
$grids_{x}$ to be the batch size and $grids_{y}$ to be 4 which is the number
of Padded Conv Blocks in a single FInC Flow Unit. This ensures that not only
GPU inverts the whole FInC Flow Unit at once but also on a batch of images.

Input: $K_{1},K_{2},K_{3},K_{4}$ \- Convolution Kernels of different PCB, $Y$
\- Output of the FInC Flow _Unit_

Result: $X$ \- Input to the FInC Flow Unit / Inverse of the FInC Flow Unit

  1. 1.

$Y_{1},Y_{2},Y_{3},Y_{4}\leftarrow split(Y)$

  2. 2.

Flip $Y_{2},Y_{3},Y_{4},K_{2},K_{3},K_{4}$ (inplace) appropriately to match
_TL_ padding

  3. 3.

$X\leftarrow concat(Y_{1},Y_{2},Y_{3},Y_{4})$

  4. 4.

$K\leftarrow concat(K_{1},K_{2},K_{3},K_{4})$

  5. 5.

Apply Algorithm 1 with input $K,Y$ to get $X$

  6. 6.

$X_{1},X_{2},X_{3},X_{4}\leftarrow split(X)$

  7. 7.

Flip $X_{2},X_{3},X_{4}$ appropriately to get the correct output

  8. 8.

$X\leftarrow concat(X_{1},X_{2},X_{3},X_{4}$)

Algorithm 2 Fast Parallel Inversion Algorithm for FInC Flow _Unit_

#### Running MaCow, Emerging, CInC Flow, SNF

For MaCow and SNF, we use the official code released by the authors. Emerging
was implemented in PyTorch by the authors of SNF. We make use of that. We have
implemented CInC Flow on PyTorch to get the results.

#### Computing Run-time and Confidence Intervals

We run the model (both forward and sampling) $11$ times and ignore the
$1^{\text{st}}$ run as it includes the initialization time. We calculate the
mean, standard deviation and $95\%$ confidence interval and plot the numbers.
To calculate forward time, we pass $100$ images, as for sampling times, we
sample $100$ images. We present these numbers in Table-3.
For sampling time comparison of different models shown in Figure 3, we set the
total number of parameters for all the models to be close to $5\mathbf{M}$ to
make it a fair comparison.

#### Hardware/Training Time

Our hardware setup consists of Intel Xeon E5-2640 v4 processor providing 40
cores, 80 GB of DDR4 RAM, 4 Nvidia GeForce GTX 1080 Ti GPUs each with $12$ GB
of VRAM. We train our model on all GPUs using PyTorch’s Data Parallel class.
We implement early stopping mechanism for smaller datasets like MNIST,
CIFAR-10. For others we train the model for a maximum epochs. To evaluate
Forward Time and Sampling Time, we use only one of the GPUs.We evaluate our
FInC Flow model on MNIST, CIFAR-10, Imagenet-32x32, and Imagenet-64x64
datasets for three metrics - (a) Loss expressed in Bits per Dimension (BPD),
(b) Forward Pass Time (FT): Time taken for 100 images to be passed through the
model and (c) Sampling Time(ST): Time taken by the model to generate 100
images. To do this, we train our model with Adam Optimizer with a learning
rate ($lr$) of $0.001$ and exponentially reduce the $lr$ by $0.99997$ after
each epoch. We have used 4 NVIDIA GTX 1080 Ti GPUs to train our model.
Evaluation(FT/ST) is done on a single GPU.


#  From Monolith to Microservices: Software Architecture for Autonomous UAV
Infrastructure Inspection

Lea Matlekovic and Peter Schneider-Kamp<EMAIL_ADDRESS><EMAIL_ADDRESS>Department of Mathematics and Computer Science,
University of Southern Denmark, Odense, Denmark

###### Abstract

Linear-infrastructure Mission Control (LiMiC) is an application for autonomous
Unmanned Aerial Vehicle (UAV) infrastructure inspection mission planning
developed in monolithic software architecture. The application calculates
routes along the infrastructure based on the users’ inputs, the number of UAVs
participating in the mission, and UAVs’ locations. LiMiC1.0 is the latest
application version migrated from monolith to microservices, continuously
integrated, and deployed using DevOps tools to facilitate future features
development, enable better traffic management, and improve the route
calculation processing time. Processing time was improved by refactoring the
route calculation algorithm into services, scaling them in the Kubernetes
cluster, and enabling asynchronous communication in between. In this paper, we
discuss the differences between the monolith and microservice architecture to
justify our decision for migration. We describe the methodology for the
application’s migration and implementation processes, technologies we use for
continuous integration and deployment, and we present microservices improved
performance results compared with the monolithic application.

###### keywords:

autonomous UAV, mission planning, microservices, Docker, Kubernetes, CI/CD

##  1 Introduction

Infrastructure inspection is a dangerous, expensive, and time-consuming task.
Falls from inspection sites are the leading cause of death among construction
workers [1]. It is not the only risk construction workers face. They may also
come into contact with toxic chemicals, moving machinery, speeding traffic, or
high-voltage equipment. The risks increase when the infrastructure is in
disrepair. Deploying UAVs to inspection eliminates the safety risks. Defects
can be detected from the UAV camera and construction workers can see the state
of an inspection site before they climb and start repairing the
infrastructure. The UAV technology reduces the costs of inspection since it
does not require special inspection equipment, helicopters nor airplanes [2].
Nowadays, many companies use UAVs for visual infrastructure inspection, but
they still control them manually or use automated flying. By increasing the
degree of UAVs’ autonomy, we expect to reduce the costs even more and save
time on process optimization. To develop an autonomous system for
infrastructure inspection, we need to plan the inspection mission and schedule
tasks for each UAV participating in the mission.

The preliminary system design for autonomous UAV infrastructure inspection was
described in [3]. The system was designed in three layers: cloud services,
UAVs, and communication between them. Global mission planning and scheduling
software is deployed in the cloud. When the mission is calculated, the route
coordinates are sent to the UAVs. Message exchange between UAVs and cloud
services is through the HTTP (Hypertext Transfer Protocol). Robot Operating
System (ROS) runs on UAVs where high-level control software is deployed. PX4
open-source software is used as a low-level flight controller.

Linear-infrastructure Mission Control (LiMiC) is presented in [4]. It is a
software application for global mission planning and scheduling developed in a
monolithic architecture. Monolithic means that all the application logic was
composed into a single program. To facilitate further development and improve
the route calculation processing time, we decided to redesign the architecture
and compare the performance.

The paper is structured as follows. In Section 2, we compare monolithic
architecture to microservices, justifying our choice for a redesign. We
describe DevOps practices that facilitate microservices deployment to the
production. Related work, concerning monolith decoupling is presented in
Section 3. In Section 4, we describe LiMiC application logic, architecture
redesign based on LiMiC functionalities, migration and implementation
processes, technologies we used as well as the deployment strategy. In Section
5, we compare performance between the application developed in monolith and
microservice architecture. We conclude in Section 6 discussing possible
improvements and future work.

##  2 Preliminaries

In this section, we describe software architecture styles relevant for this
article and present their benefits as well as challenges. Software
architecture in general describes application organization and structure.
Architectural decisions impact application quality, performance,
maintainability, and usability. Software architecture chosen at the beginning
of the application development can have a high impact on the application’s
future and affect its success. Architecture should be considered and planned
if the application needs to be scalable, maintainable, and easily upgradable.
When developing the application from scratch, the focus is usually on having a
working product as soon as possible. However, that approach can become
unsustainable when the number of application features grows fast. If the
architecture is not reconsidered, the development slows down and application
becomes difficult to maintain.

###  2.1 Monolithic Architecture

Monolithic applications encompass several tightly coupled functions and tend
to have a big codebase. The development does not require advanced architecture
planning since the application is developed, packaged, and deployed as a
standalone instance. The packaged application can be deployed to the server
and scaled horizontally by running multiple instances behind a load balancer.
The load balancer distributes the traffic across the instances deployed on the
different servers. Testing the monolith applications can be performed end-to-
end by launching the application and using existing testing framework e.g.,
Selenium [5]… However, when the code base grows and many developers work on
the same application, monolith applications face challenges. The application
can become too complex and difficult to understand. That prevents quick
updates and development slows down. On each update, the entire application
must redeploy and it can be difficult to track update impacts. It leads to
extensive and time-consuming manual testing. A bug in any module can
potentially bring the whole system down since all instances rely on the same
code base. Even though the application can be scaled, the load is usually not
equally distributed to all the modules i.e., the traffic is directed to only
one application module, but they are all scaled equally. When application
modules have different resource requirements, like they often do, it can lead
to unnecessary CPU (Central Processing Unit) and memory consumption. Monoliths
are not robust to changes and adopting a new framework or technology would
lead to rewriting of the entire code base which is both expensive and time-
consuming [6]. Development in monolithic architecture could be a good choice
if the application will not need to be further extended or as a starting point
when the main goal is to have a simple, working end-product. However, when the
development slows down as the codebase grows, it is recommended to reconsider
the architecture [13].

###  2.2 Microservice Architecture

Microservice architecture, also known as Microservices, is a software
architecture that structures an application as a collection of small, loosely
coupled services. The services are independently deployable, highly
maintainable, and testable [7]. The concept was developed to overcome the
downsides of monolithic architecture. Microservices have clear boundaries
between each other and communicate through the HTTP protocol, usually by
exposing a REST API and sending requests. Each service represents one
capability that makes it easier to understand and locate the code. It also
makes them robust to changes. Since they are small and deployed independently,
they are easy to update and maintain. Services can be scaled independently and
automatically, depending on the load. They can use different technology
stacks, including programming language and data storage. That gives high
flexibility to the development teams. However, there are some drawbacks of
microservice architecture. The fact that a microservices application is a
distributed system requires handling of fallacies the distributed computing
carries. It means that developers must deal with the additional complexity.

There are opinions suggesting to start application development in monolith
architecture first and then migrate to microservices [8]. As monolithic
systems become too large to deal with, many enterprises are drawn to breaking
them down into microservices. On the other side, others recommend starting
with microservices if that architectural style is the goal [9]. However, most
large scale websites including Netflix, Amazon, and eBay have evolved from a
monolithic architecture to microservices [10].

###  2.3 DevOps

Microservices, since they are independent, bring more complexity in
application deployment than monolithic applications. There are many practices
and tools developed to facilitate testing, integration, and deployment of
microservices [11]. DevOps is a combination of practices and tools designed to
facilitate the delivery of applications. It aims to increase an organization’s
ability to deploy applications faster by removing the barriers between
development and operations teams [12]. DevOps practices automatize the
delivery process and are implemented as a part of a production pipeline.
Applied tools and practices depend on the application delivery requirements
and goals. Continuous integration is the practice of merging changes to the
main branch as often as possible. When developers commit local changes to the
remote repository, automated build and tests can run there before proceeding
to production. Remote repository platforms with built-in version control, like
GitLab and GitHub, facilitate the collaboration between developers and enable
continuous integration. These platforms also integrate with different DevOps
tools to enable continuous delivery and deployment. The practice of continuous
delivery includes continuous integration and after a successful build,
automatically propagates the application to staging. In staging, the
application is deployed to the testing environment. There, the application
including all services can be run and tested. Continuous delivery requires
manual approval for release into production. However, the continuous
deployment includes all the steps described in continuous integration and
delivery, but instead of manual, the release process is also automated.
Described process can vary in complexity depending on the number of services,
test requirements, and in general, the deployment strategy.

##  3 Related work

The concept of microservices arose around ten years ago and today is a widely
used concept for large enterprises to develop their software systems.
According to IDC (International Data Corporation), by 2022, 90% of all new
applications will be based on microservices architectures [13]. Adopting
microservices improves agility and flexibility, enabling enterprises to bring
their products and services to market faster.

Although the benefits of microservices are evident, adopting it is not an easy
task as it usually involves refactoring the monolithic application. There are
many critical questions to ask before deciding to refactor the monolith. Will
the refactoring bring value? How to re-architect an existing system without
having to stop all other work on it? How big should a microservice be? What
are some of the migration patterns you could adopt when splitting up a
monolith? [13] There is some research tackling these questions in the latest
years. Most of the previous research on microservices either identifies
challenges when splitting the monolith like in [14], or proposes refactoring
methods. Classification of refactoring approaches is presented in [15]. There
are four notable approaches identified. Static Code Analysis approaches
require the application’s source code analysis and derive a decomposition from
it through possible intermediate stages. Meta-Data aided approaches require
more abstract input data, like architectural descriptions in form of UML
(Unified Modeling Language) diagrams, use cases, interfaces, or historical VCS
(Version Control System) data. Workload-Data aided approaches aim to find
suitable service cuts by measuring the application’s operational data (e.g.
communication, performance) on module or function level and use this data to
determine a fitting decomposition and granularity. Dynamic Microservice
Composition approaches try to solve the problem more holistically by
describing a microservices runtime environment. Other than the previously
mentioned categories, the resulting set of services is permanently changing in
each iteration of re-calculating the best-fitting composition (based on e.g.
workload). Static and dynamic analysis of the monolith is further described
and used for refactoring in [16]. The authors used dynamic software
visualization to identify appropriate microservice boundaries for a real-world
application. A Dataflow-driven approach is proposed in [17]. The article
presents a semi-automatic mechanism to break business logic into microservices
and visualize services with data flows. Although the refactoring algorithm
could save some time in splitting the monolith, it still requires
identification and description of monolith application business logic. All the
research work we encountered based refactoring on application logic and we
followed the same approach. Another interesting work is proposed in [18] where
the focus is on profitability depending on the number of refactored services
and deployment. The article shares lessons learned on an industrial migration
to a web-oriented microservice architecture. The services are refactored based
on capabilities and the decision on service size is based on the company
organization and profitability. For deployment tools, Docker is emphasized as
a widely used container technology for achieving service isolation. The
article presents the return of investment from refactoring the monolith and
concludes by presenting the benefits of the transition for a given company.

Even though the previous research literature guided us in choosing the most
suitable approaches, each application is different and requires an individual
approach bringing new challenges when splitting it into microservices.

##  4 Methodology

In this section, we describe processes leading to LiMiC migration from
monolith to microservice architecture. Migration from monolith to
microservices is not an easy task [19]. There are many different approaches to
splitting the monolith. The code should be studied before decoupling into the
logical components. Dependencies should be identified and isolated. Even
though our monolithic application was not deployed in the production and it
did not have users depending on it, we encountered difficulties while
refactoring, and parts of the code had to be rewritten instead of reused.

Main processes leading to LiMiC1.0 implementation from monolith to
microservices are as follows:

  * •

Identification \- identification of features in monolithic application

  * •

Isolation \- isolation of features where each isolated feature is one
meaningful and standalone unit

  * •

Implementation \- implementation of isolated features withing framework
enabling the communication between them

For application deployment we developed a strategy and used DevOps tools
described in this section to implement and automatize processes leading to
deployment. By enabling continuous integration and continuous deployment, we
tremendously benefited from the microservice architecture, i.e. better
codebase organization, faster development, easier integration and deployment.

###  4.1 Identification & Isolation

Linear-infrastructure Mission Control (LiMiC) is an application software for
autonomous Unmanned Aerial Vehicle (UAV) infrastructure inspection. It is a
mission planner for calculating the near-optimal routes for power line
inspection using UAVs. The user can choose the mission targets, i.e. power
towers for inspection, calculate the order of visiting and generate waypoints.
Waypoints represent the coordinates sent to the UAVs for navigation to the
inspection targets.

We used data from the OpenStreetMap [20] to represent the power towers on the
web interface and to build a graph using NetworkX Python package [21]. The web
interface shows UAVs and towers on a 2D map. We used graph structure to
describe and store path data. Nodes in the graph represent power towers. Nodes
contain the tower’s unique identifier and geographical location. Edges between
the nodes contain distances between the neighboring towers which we used to
describe the costs of flying from one tower to another. We used Google OR-
Tools [22] to find the near-optimal visiting schedule for multiple vehicles
visiting a set of inspection targets stored in the graph. When a user selects
inspection targets, the vehicle scheduling algorithm generates a distance
matrix using the A* algorithm. A* finds the shortest path, based on the
distance data stored in the graph, for each combination of UAVs and towers
participating in the mission and returns it to the vehicles scheduler.
Calculated paths are used for determining the visiting schedule, i.e. which
UAV will inspect which tower. The result is visualized on the map and paths
are stored to be sent to the UAVs. Paths are represented as a set of waypoints
containing geographical locations.

We developed the application in monolithic architecture structured as Python
modules situated in a folder. The frontend communicates with the backend
through HTTP requests using Flask Python framework [23]. As the application
was growing and many developers started contributing, we started thinking
about redesigning the structure. We downloaded the data from the OpenStreetMap
and saved the graph locally. If we wanted to update the graph we would need to
run the graph generation manually and save a new one. Since we plan to grow
the application and deploy it to production, it was necessary to redesign the
graph creation and update it automatically in defined time intervals. The
codebase was not organized in a logical structure and it was difficult to
navigate. Addition of a new feature required searching through the codebase to
understand the processes before contributing to the code. A lot of time that
could be spent on the development was invested in understanding the existing
implementation. We wanted to facilitate the feature addition and reduce the
time spent on understanding the code. That required a fixed structure, but
flexible and adaptive to feature addition. In order to grow the application
and deploy it to production, we decided to restructure it. Another concern was
the load distribution. Some parts of the application are more static while
others are heavily used. If deployed to the production, some parts of the
application would have to be unnecessarily scaled. Therefore, we structured
the application in microservices based on the application’s capabilities. The
proposed structure is shown in Figure 1. The arrows determine the
communication flow between the services, e.g. the graph service sends a
request to the towers service while the towers service provides power tower
information needed to create a graph. The tower service should contain the
capability to extract the data from the OpenStreetMap, organize it in a
suitable form and save it to the database. The same capabilities should exist
for other infrastructures like bridges and railways. Bridges can be reached by
calculating the route near the power lines or railways leading to the bridge
location. Depending on the infrastructure we want to inspect, we would build
the graph containing nodes with locations of power towers, railway towers, or
bridges as defined in the OpenStreetMap. The data is used by the web interface
to visualize the inspection targets. Graph service would then use available
data to create a graph. Inspection targets chosen on the web interface would
be sent to the vehicle routing problem (VRP) solver service, which uses the A*
algorithm to find the shortest path between the targets and UAVs and
determines the routing schedule. A* calculates the shortest path based on the
graph created in the graph service.

Figure 1: Application structure based on capabilities

###  4.2 Implementation

In the previous subsection, we identified services logically, based on the
capabilities of the monolithic application. In this subsection, we describe
the process of monolith decoupling and implementation in detail.

The decoupling process was divided into two parts. First was the graph
creation based on the data stored in a database created in railways, towers,
and bridges services. That way, we were able to test the generated graph file
with a monolithic application. The second part was splitting the routing
solver and A* pathfinder into independent components. Every time the request
comes to the routing solver, it requests the shortest path for each set of
targets and UAV locations from the A*. A* requests a graph from the graph
service only on the first request. All the services use FastAPI [24] web
framework for exposing APIs (Application Programming Interfaces) to the web
interface or other services. FastAPI enables input validation where we define
how the input is structured. It facilitates the input usage in the code
without installing additional packages. FastAPI provides interactive,
automatically generated documentation which we find very useful for endpoint
visualization and testing. When looking into the performance comparison,
FastAPI is much faster than Flask which was used for LiMiC monolith
development [25]. It also provides asynchronous support crucial for taking
advantage of microservice architecture. Asynchronous requests make the
communication between routing solver and A* pathfinder much faster, especially
when A* pathfinder is scaled. It enables concurrent computation of the
shortest path.

Services are developed as follows:

  * •

Towers service \- the service uses Overpass API [26] to get the power towers
and power lines data from OpenStreetMap. Service connects to the MongoDB Atlas
database service and creates a database if it already does not exist. MongoDB
Atlas provides a cloud database service for MongoDB databases. We chose
MongoDB because it stores data in JSON-like documents and can be easily
queried. Furthermore, it provides a geo-based search we use for finding
indirect towers’ neighbors needed for creating edges in the graph. Power
towers are stored as a collection of objects with a unique identifier and
location containing the tower’s coordinates. Power lines are extracted using
the same method and stored as a collection of objects with unique identifiers
and an array of unique identifiers representing the nodes the line is passing
through. Most of the nodes’ unique identifiers are also towers’, but they can
also be a line intersections. For that reason, we created another collection
of nodes contained in the power line arrays. Nodes’ objects are defined the
same as towers. Power line collection also contains tags with useful
information on the number of cables, frequency, and voltage. The need for
storing the power line information emerged because we want to find towers’
direct neighbors. Tower’s direct neighbor is the closest tower, or more of
them, laying on the same power line. When creating the graph we want to give a
higher cost to the paths between the indirect neighbors than direct since we
want the UAVs to fly close to the infrastructure whenever that is possible.
Such a strategy is implemented for UAV flight regulations reasons. Tower
service exposes two endpoints. One is providing the tower data and another one
the data containing power lines. The data is used by the web interface to
visualize the inspection targets. Graph service requests the data to create
nodes and edges in the graph.

  * •

Railways service \- the service extracts railways location in the same way
described in the towers service. It saves the data to the MongoDB database and
sends it to the graph service on request.

  * •

Bridges service \- the service extracts polygons around the bridges and saves
them to the database. Polygons are stored as the way types containing unique
identifiers for nodes in the polygon. The nodes are stored in the same
database containing the node’s location. Bridges locations than can be
combined with power line locations to create a graph and enable the UAVs to
reach a bridge.

  * •

Graph service \- the service creates a graph based on the data received from
either towers service or railways and bridges. The towers’ locations represent
the nodes in the graph while a pair of neighboring towers represent edges. The
edge’s cost is set up as the calculated distance between the neighboring
towers. All the data for building the graph is requested from the towers
service. The graph is created only once and it is used by A* pathfinder to
determine the shortest path between the set of inspection targets and UAVs.

  * •

Routing solver service \- the service receives inspection targets and UAV
locations and uses OR-Tools to determine which UAV should inspect which
target. It creates asynchronous requests to the A* service to get the shortest
path for each combination of UAV and target. Then, it builds the distance
matrix and, based on path length, finds a near-optimal solution to the vehicle
routing problem. It returns the path for each UAV as a set of waypoints
containing locations in latitude and longitude.

  * •

A* pathfinder service \- the service requests a graph from the graph service
and performs the A* algorithm on the targets and UAVs locations received from
the routing solver service. A* algorithm is implemented from the NetworkX
library. It returns the shortest path between a target and a UAV and returns
the total path distance as well as the distance between each path segments
with corresponding node locations.

###  4.3 Deployment Pipeline and DevOps tools

In order to deploy the application automatically every time the changes are
made, we set up a pipeline using DevOps tools and technologies. Deployment
pipeline consists of different stages for application building, deploying, and
testing. We also enabled security scanning for code vulnerabilities and
monitoring. To store the code, enable collaboration, and configure the
pipeline, we used GitLab [27].

Microservices tend to be independent and isolated from each other. The most
used and convenient way to isolate services is using container technology.
Containers package up the application code and all its dependencies so the
application can run quickly and reliably in any computing environment. Docker
is the most popular and widely used container technology. Containers run from
Docker images configured in Dockerfile. Docker image is a lightweight,
standalone, executable package of software that includes everything needed to
run an application: code, runtime, system tools, system libraries, and
settings. Containers always run the same, regardless of the operating system
and infrastructure. Compared with virtual machines, containers isolate
application software from its environment but do not include a full copy of an
operating system. Therefore, they take up less space and are much faster [28].
Each LiMiC1.0 service is a Python package containing multiple modules and the
Dockerfile. Docker images are built on the Python base image and run the
application in a virtual environment after installing all the dependencies.

In LiMiC1.0, each service runs in a separated container and contains its
Dockerfile. The whole process is configured using GitLab. Gitlab has built-in
tools for software continuous integration and continuous deployment (CI/CD)
which are used to run the pipeline. The codebase is hosted in the GitLab
repository and contains a gitlab-ci.yml file describing the pipeline stages.
Each service contains its yml file where the deployment and service port is
configured. Every time the changes are pushed to the repository, GitLab
runners execute scripts defined in the gitlab-ci.yml file and create a cluster
deployments based on the service’s yml file. We decided to automatize the
LiMiC1.0 deployment to the server in the Kubernetes cluster as a staging
environment. Figure 2 shows the application deployed to the Kubernetes
cluster.

Figure 2: Application deployment in Kubernetes cluster

Kubernetes is an open-source system for automating deployment, scaling, and
management of containerized applications. Kubernetes cluster consists of
master and worker machines. Worker machines, also called nodes, run
containerized applications in pods while the master manages workers and makes
sure that the cluster is working in a configured way. The master node contains
an API server which is the cluster entry point. API server 1 runs a process
that enables communication with the cluster. To visualize and manage all the
cluster applications we can use the dashboard, as a web user interface,
communicating with the API server. Otherwise, we can use API to communicate
with the API server from the script or simply we can manage the cluster by
writing commands in the terminal using a command-line tool. The master node
keeps track of a cluster by running a controller manager. Controller manager 2
is responsible for checking if all the nodes and pods are running and, if one
goes down, the controller manager replaces it with a new one. Scheduler 3
decides on which node a newly created pod will run, based on the available and
required resources. Etcd key-value storage 4 in the master node keeps status
data about the nodes. Master nodes and worker nodes communicate through a
virtual network. The virtual network assigns an internal IP address to each
pod. Pods communicate through the services 5 which contain permanent IP
addresses. In case a pod restarts it will keep the service with the same
address. Each service also provides a load balancing. Network rules for
allowing the communication through the services are maintained by Kube proxy 6
running on each worker node. Kubelet 7 agent runs on each node assuring that
containers run in pods as described in pods specifications. Container runtime
is responsible for running the containers [29].

We decided to set up a Kubernetes cluster on a server running Linux Ubuntu
18.04.5 LTS using Minikube. Minikube allows you to set up a local cluster with
the master process and worker process running on one node. We use it as a
staging environment to deploy and test our application since the application
development is still in an early stage and does not have any end users.
Minikube creates a virtual machine VirtualBox on a local machine and the node
runs in the VirtualBox. Kubectl is a command-line tool we use to interact with
the cluster.

To automatize the deployment, we integrated the cluster with GitLab by
providing a cluster API and token. To be able to run the CI/CD jobs, we
installed the GitLab runner on the cluster. In the yml file, we configured
three pipeline stages. In the first stage, the Gitlab runner runs a Docker
container for each service based on the Docker image. Inside that container,
we build a new image based on the corresponding service’s Dockerfile and push
it to the Gitlab container registry. The processes run in parallel for each
service to speed up the creation of images. In the second stage, we create the
deployments and services in the cluster based on the configuration file for
each service. In the configuration file, we provide the path to the container
registry where the images are stored in the previous stage and set the desired
number of pod replicas for each deployment. We configure the ports where the
services can be reached. We also enable monitoring through GitLab using
Prometheus. The third stage is testing. We test if the services are responsive
and if the returned result is correct. The test contains several inspection
targets and UAV locations with calculated paths in between. The same targets
and UAV locations are sent to the deployed system and the solution is compared
with the correct one. The test is delayed for a minute after the deployment
stage finishes successfully, to allow the Kubernetes to run all the pods
following the yml configuration. The pipeline configuration file also includes
a GitLab template for code vulnerability scanning i.e., Static Application
Security Testing (SAST). The SAST checks for potentially dangerous attributes
in a class, or unsafe code that can lead to unintended code execution and
searches for vulnerabilities to cross-site scripting attacks that can be
leveraged to unauthorized access to session data. The report can be downloaded
after the pipeline executes correctly and the results are sorted by the
priority of the vulnerability. In case we are merging changes from another
branch to the master branch, GitLab will find the vulnerabilities in the new
code that are different from the code in the master branch and report them.
GitLab also offers visualization of the pipeline stages where we can see the
progress and check the logs for the executed processes. The successful
pipeline execution is shown in Figure 3. On every push to the GitLab
repository, the code is scanned for the vulnerabilities, the services are
containerized, automatically deployed to the Kubernetes cluster, and tested.
The controller manager assures that desired number of pods is always running.
Pod logs are available in GitLab for both GitLab-managed applications and
services.

Figure 3: Application deployment pipeline

For monitoring the cluster and the application, we installed an open-source
monitoring system Prometheus [30] through GitLab. For each service, we expose
metrics endpoint using Prometheus middleware. In GitLab, we configured a
custom dashboard to monitor the number of requests coming to the services. The
number of requests coming to the A* pathfinder is visualized in Figure 4.
Requests visualized in red are coming from the routing solver while requests
in blue are Prometheus requests for scraping metrics. We also monitor the
percentage of failed requests. Since GitLab deprecated Prometheus and
scheduled it for removal, it was not possible to add alerts. Otherwise, we
would be able to add an alert to notify us when there is a certain percentage
of failed requests. With Prometheus integration, we also monitor the cluster’s
CPU and memory usage as well as CPU, memory, and network metrics for each pod
in the cluster. That dashboard is set up automatically with the installation
of Prometheus.

Figure 4: Requests to the A* path finder service

##  5 Performance Evaluation

To evaluate our application performance, we deployed it automatically through
the GitLab CI/CD to the Minikube Kubernetes cluster. We compared the
performance with the monolithic version of the application. To assure the same
running environment, we created a Docker image for our monolith application
and deployed it to the same cluster within a new namespace. We tested the
performance by sending requests with different sets of sources and targets and
measuring the time to process the requests. Sources represent UAV locations
and targets are power tower locations. We chose the locations contained in the
graph randomly. The data contains power tower locations in Denmark and we
suppose that UAVs are located on the power tower locations on their start. We
exponentially increment the number of sources from 1 to 16, and the number of
targets from 1 to 64. One hundred requests were generated for each combination
of sources and targets, thus 3500 requests in total. The same requests were
made to both systems. Requests to LiMiC1.0 were made for a different number of
pod deployments. First, we deployed only one pod per service and measured the
processing time. Then we scaled the deployment with ten A* pathfinder pod
replicas to take the advantage of asynchronous communication between vehicle
routing solver and A* pathfinder services. The processing time comparison
between monolithic LiMiC and microservices LiMiC1.0 is shown in graphs in
Figures 5 to 16. Processing time for microservices application without scaling
is shown in green, with ten A* pathfinder pod replicas is shown in yellow, and
the monolithic application processing time is shown in blue. Figures 5 to 9
show processing time for a different number of sources, i.e. UAVs, while
altering the number of targets. Figures 10 to 16 show processing time for a
different number of targets while altering the number of sources. Both options
were visualized to provide a better analysis of the system’s performance.

Figure 5: Processing time comparison between monolith and microservice
application with 1 source and altering number of targets

Figure 6: Processing time comparison between monolith and microservice
application with 2 sources and altering number of targets

Figure 7: Processing time comparison between monolith and microservice
application with 4 sources and altering number of targets

Figure 8: Processing time comparison between monolith and microservice
application with 8 sources and altering number of targets

Figure 9: Processing time comparison between monolith and microservice
application with 16 sources and altering number of targets

Figure 10: Processing time comparison between monolith and microservice
application with 1 target and altering number of sources

Figure 11: Processing time comparison between monolith and microservice
application with 2 targets and altering number of sources

Figure 12: Processing time comparison between monolith and microservice
application with 4 targets and altering number of sources

Figure 13: Processing time comparison between monolith and microservice
application with 8 targets and altering number of sources

Figure 14: Processing time comparison between monolith and microservice
application with 16 targets and altering number of sources

Figure 15: Processing time comparison between monolith and microservice
application with 32 targets and altering number of sources

Figure 16: Processing time comparison between monolith and microservice
application with 64 targets and altering number of sources

In all figures, we see that with the monolithic application, the processing
time extends proportionally with the number of sources and targets while with
microservices the processing time stabilizes and stops raising. For the
microservices application, the overhead of internal communication between the
services adds in processing time for two to eight sources visiting one target,
which is best visible in Figure 10, where both scaled and not scaled
microservice application performs slower than the monolith. The same is
visible in Figures 6 to 8, where the path is calculated for sources to reach
only one target. For a high number of sources, as in Figure 9, microservices
perform faster for each number of targets. As the number of targets is
raising, monolithic application processing time slows down, and microservices
start outperforming the monolith, especially when scaled, as seen in Figures
11, 12, and 13. For 16 targets, LiMiC1.0 performs significantly better as
shown in 14. By increasing the number of targets even more the processing time
becomes near constant as seen in Figures 15 and 16. If we take the highest
number of sources and targets and calculate the average time it takes to find
near-optimal paths for 16 UAVs to visit 64 towers, we calculate that LiMiC1.0,
when scaled, can process the request and serve the solution in about 5,32
seconds. Compared with LiMiC which takes 1 minute and 13 seconds on average.
When scaled, LiMiC1.0 is slower than the monolithic LiMiC only when two, four,
or eight UAVs are chosen for inspection of one target. However, it is unlikely
for a user to pick either of the combinations mentioned, since most of the
time it is intuitive when visualized, which UAV is the most suitable for the
mission inspecting only one target. We also have to take into account that
sources and targets are chosen randomly over the country of Denmark. Therefore
they do not always represent a realistic set and sometimes it was not even
possible for the solver to find a solution. We expect that the average
processing time for a realistic set of sources and targets is slightly better.
However, this experiment provided an insight into applications’ performance
and showed a positive impact of migrating the route calculation algorithm to
microservices. The performance of the microservices application could be
further improved by deploying to a more powerful cluster and taking the
advantage of automatic scaling.

##  6 Conclusion & Future Work

To increase safety and reduce costs while inspecting the infrastructure, we
developed an application for routing and scheduling UAVs to fly near the
infrastructure. In this paper, we redesigned the application architecture to
speed up future development, enable collaboration between developers, automate
the deployment, and most important to speed up the route calculation. We
implemented the application in microservice architecture and configured
deployment pipeline stages using GitLab. We automatically trigger the Docker
image creation, push the images to the container registry, scan the code for
security vulnerabilities, deploy the application to the Minikube Kubernetes
cluster and test the services’ responsiveness. Also, we check if the results
calculated are correct. We test the performance by comparing monolithic
application and microservice application processing times. Microservices
process requests faster, having the advantage of pod scaling and asynchronous
communication between the services. Monolith application processing time
exponentially rises when calculating paths for an increasing number of UAVs
and power towers to inspect. By refactoring the calculation algorithm, the
processing time is shorter and stabilizes after reaching a certain number of
sources and targets.

To have a fully operational application for infrastructure inspection, we aim
at implementing the additional services. In some areas, UAV flights are not
permitted and we want to avoid these zones. While creating the graph, we will
detect the infrastructure locations laying in the forbidden areas and reroute
around them to assure flight safety. The application has to be able to
communicate with UAV and send the navigation waypoints calculated in the
routing solver service. Therefore, we aim at implementing a message broker
service to manage the communication between UAVs and the application. UAVs
should be able to send data, including inspection images, through the same
message broker. One of the additional services would estimate the UAVs’
location to visualize their location on the web interface in every moment
while the mission is in progress, even if the connectivity is not constant. We
will implement storage for planned and executed missions to be able to
retrieve the mission data after its execution. The application would also
contain image analysis services to detect faulty infrastructure using machine
learning models as well as image storage. Another important feature is a
service for 3D infrastructure reconstruction which would be used for path
planning around the power towers and bridges. An idea worth considering for
future work would be to implement the weather prediction service and use it to
determine if the weather in the area allows a safe flight. The microservice
architecture we implemented and presented in this paper will allow us to add
mentioned features easily as independent services. Concerning the deployment
strategy, we aim at deploying the application to production to a multi-node
Kubernetes cluster in the public cloud and test the application’s load.

##  7 Acknowledgements

This project has received funding from European Union’s Horizon 2020 Research
and Innovation Programme under Grant Agreement No 861111, Drones4Safety.

## References

  * [1] Danielak M. Drones improve safety of infrastructure inspections. [Online] Available: https://www.roadsbridges.com/drones-improve-safety-infrastructure-inspections
  * [2] Jordan S, Moore J, Hovet S, Box J, Perry J, Kirsche K, Lewis D, Tse ZT. State-of-the-art technologies for UAV inspections. IET Radar, Sonar & Navigation. 2018 Feb 8;12(2):151-64.
  * [3] Mehrooz G, Ebeid E, Schneider-Kamp P. System design of an open-source cloud-based framework for internet of drones application. In 2019 22nd Euromicro Conference on Digital System Design (DSD) 2019 Aug 28 (pp. 572-579). IEEE.
  * [4] Mehrooz G, Schneider-Kamp P. Optimal Path Planning for Drone Inspections of Linear Infrastructures. In GISTAM 2020 May 9 (pp. 326-336).
  * [5] Selenium. [Online] Available: https://www.selenium.dev/
  * [6] ul Haq S. Introduction to Monolithic Architecture and MicroServices Architecture. [Online] Available: https://medium.com/koderlabs/introduction-to-monolithic-architecture-and-microservices-architecture-b211a5955c63
  * [7] Richardson C. What are microservices? [Online] Available: https://microservices.io/
  * [8] Fowler M. Monolith first. [Online] Available: https://martinfowler.com/bliki/MonolithFirst.html
  * [9] Tilkov S. Don’t start with a monolith. [Online] Available: https://martinfowler.com/articles/dont-start-monolith.html
  * [10] Richardson C. Pattern: Microservice Architecture. [Online] Available: https://microservices.io/patterns/microservices.html
  * [11] Newman S. Building Microservices. O’Reilly Media, Inc. 2015
  * [12] Synopsys, Inc. DevOps. [Online] Available: https://www.synopsys.com/glossary/what-is-devops.html
  * [13] Newman S. Monolith to Microservices: Evolutionary Patterns to Transform Your Monolith. O’Reilly Media, Inc. 2019
  * [14] Kalske M, Mäkitalo N, Mikkonen T. Challenges when moving from monolith to microservice architecture. In International Conference on Web Engineering 2017 Jun 5 (pp. 32-47). Springer, Cham.
  * [15] Fritzsch J, Bogner J, Zimmermann A, Wagner S. From monolith to microservices: A classification of refactoring approaches. In International Workshop on Software Engineering Aspects of Continuous Development and New Paradigms of Software Production and Deployment 2018 Mar 5 (pp. 128-141). Springer, Cham.
  * [16] Krause A, Zirkelbach C, Hasselbring W, Lenga S, Kröger D. Microservice decomposition via static and dynamic analysis of the monolith. In 2020 IEEE International Conference on Software Architecture Companion (ICSA-C) 2020 Mar 16 (pp. 9-16). IEEE.
  * [17] Chen R, Li S, Li Z. From monolith to microservices: A dataflow-driven approach. In 2017 24th Asia-Pacific Software Engineering Conference (APSEC) 2017 Dec 4 (pp. 466-475). IEEE.
  * [18] Gouigoux JP, Tamzalit D. From monolith to microservices: Lessons learned on an industrial migration to a web oriented architecture. In 2017 IEEE International Conference on Software Architecture Workshops (ICSAW) 2017 Apr 5 (pp. 62-65). IEEE.
  * [19] Fowler M. How to break a Monolith into Microservices. [Online] Available: https://martinfowler.com/articles/break-monolith-into-microservices.html
  * [20] OpenStreetMap. [Online] Available: https://www.openstreetmap.org
  * [21] NetworkX. [Online] Available: https://networkx.org/
  * [22] Google OR-Tools. Vehicle Routing Problem. [Online] Available: https://developers.google.com/optimization/routing/vrp
  * [23] Flask. [Online] Available: https://flask.palletsprojects.com/en/2.0.x/
  * [24] FastAPI. [Online] Available: https://fastapi.tiangolo.com/
  * [25] TechEmpower. Web Framework Benchmarks. [Online] Available: https://www.techempower.com/benchmarks/#section=test&runid=7464e520-0dc2-473d-bd34-dbdfd7e85911&hw=ph&test=query&l=v2qiv3-db&a=2&f=zik0zj-zik0zj-zhxjwf-zik0zi-zik0zj-zik0zj-zik0zj-zik0zj-zik0zj-zik0zj-zik0zj-1kv
  * [26] Overpass API. [Online] Available: http://overpass-api.de/
  * [27] GitLab. [Online] Available: https://docs.gitlab.com/ee/ci/
  * [28] Docker. What is a Container? [Online] Available: https://www.docker.com/resources/what-container
  * [29] Kubernetes. Kubernetes Components. [Online] Available: https://kubernetes.io/docs/concepts/overview/components/
  * [30] Prometheus. [Online] Available: https://prometheus.io/