# First results from the ENTOTO neutron monitor: Quantifying the waiting time
distribution

R. D. Strauss<EMAIL_ADDRESS>Nigussie M. Giday,
<EMAIL_ADDRESS>Ephrem B. Seba<EMAIL_ADDRESS>Daniel A.
Chekole<EMAIL_ADDRESS>Gemechu F. Garuma<EMAIL_ADDRESS>Bereket H. Kassa<EMAIL_ADDRESS>Teshome Dugassa<EMAIL_ADDRESS>C. Diedericks<EMAIL_ADDRESS>Center for Space Research, North-West
University, Potchefstroom Campus, Private Bag X6001, 2520 Potchefstroom, South
Africa  Department of Space Science and Applications Research, Ethiopian Space
Science and Technology Institute, P.O. Box 33679, Addis Ababa, Ethiopia
Department of electrical engineering, Addis Ababa Science and Technology
University, Addis Ababa, Ethiopia

###### Abstract

We discuss a newly established neutron monitor station installed at the ENTOTO
Observatory Research Center outside of Addis Ababa, Ethiopia. This is a
version of a mini-neutron monitor, recently upgraded to detect individual
neutrons and able to calculate the waiting time distribution between neutron
pulses down to $\sim 1$ $\mu$s. From the waiting time distribution we define
and calculate a new quantity, the correlation ratio, as the ratio of
correlated to uncorrelated neutrons measured inside the monitor. We propose
that this quantity can, in future, be used as a proxy for spectral index of
atmospheric particles incident on the monitor and show that this quantity has
a weak pressure dependence. We believe that future measurements from the
ENTOTO mini-neutron monitor will contribute towards the understanding of
cosmic ray acceleration and transport in the heliosphere.

###### keywords:

cosmic rays , neutron monitor , space weather

††journal: Advances in Space Research

##  1 Introduction

When primary cosmic rays interact with atmospheric molecules, showers of
secondary atmospheric particles are created that can be registered, on ground-
level, by neutron monitors (NMs, Simpson, 2000). The detectors integrate the
energy-dependent atmospheric particle flux into a single count rate

$\mathcal{C}(P_{c},t)=\sum_{i}\int_{P_{c}}^{\infty}j_{i}(P,t)Y_{i}(P,t,\ldots)dP,$
(1)

where $P_{c}$ is the cutoff rigidity (minimum rigidity particle that can reach
the detector), $i$ represents the particle distribution under consideration
(e.g. protons and heavier nuclei), and $Y_{i}(P,t,\ldots)$ is the so-called
yield function that represents the response of the instrument on the unit flux
of primary cosmic rays with rigidity $P$, including atmospheric and
instrumental effects (e.g. Clem & Dorman, 2000; Mishev et al., 2020).

NMs are increasingly used for several space weather applications, including
the routine monitoring of the cosmic ray flux for dosimetric purposes, as well
as environmental applications such as sensing the soil moisture content (e.g.
Zreda et al., 2012). With the expanding role of NMs, it is becoming
increasingly important to fill the gaps in the international NM network (e.g.
Mishev & Usoskin, 2020), especially over the African continent where NM
stations are only located in Southern Africa. In order to address this issue,
we have recently installed a NM at the ENTOTO Observatory Research Center
(EORC) outside of Addis Ababa, Ethiopia, jointly operated by the Ethiopian
Space Science and Technology Institute (ESSTI) and the Centre for Space
Research of the North-West University in South Africa.

First conceived as a mobile calibration monitor (Krüger et al., 2008), mini-
neutron monitors (MNMs) have become an increasingly popular alternative to
larger traditional (and much more expensive) NMs. The MNMs are cost-effective,
relatively easy to transport and be installed, and features updated
electronics. Due to their limited size MNMs, however, have a much lower count
rate as traditional NMs but under the correct conditions (e.g. when installed
at high altitudes), can still provide valuable measurements, even in a real-
time setting (Usoskin et al., 2015; Poluianov et al., 2015; Heber et al.,
2015). Additionally, the updated electronics of the MNMs allow for the
digitization of individually observed neutron pulses and the calculation of
the waiting time distribution of the monitor down to $\sim 1$ $\mu$s (Strauss
et al., 2020, 2021). In this work we consider three versions of the MNM. The
first is a leaded version with a BF3-filled proportional counter as installed
at ENTOTO, the second a similar leaded version with a 3He gas-filled
proportional counter, and the last version a BF3-filled counter but with the
lead producer removed.

A long-term goal for the global NM network has been to inter-calibrate
individual NM stations in order to derive a proxy for the spectral shape of
the incident cosmic ray particles. While much progress regarding this has been
made in recent years (e.g. Mishev et al., 2020) there are examples where even
very simplistic calculations, such as the ratio of two NMs at different cut-
off rigidities, lead to spurious changes most likely related to environmental
changes at the local NM stations (Ruffolo et al., 2016). This can be overcome
by using two NMs, at the same station, which are sensitive to different
rigidities, usually a traditional NM with lead as well as a lead-free version
(Stoker, 1985) or by deriving a proxy for the incident spectra by examining
the waiting time distribution of a single monitor (Bieber et al., 2004). Here
we discuss how the waiting time distribution, as observed by the ENTOTO MNM
can be used to derive such a proxy by calculating a new quantity, the
correlation ratio, which we define as the ratio of correlated to uncorrelated
neutrons measured by the detector.

Fig. 1: Rear panoramic (top), front (bottom left), and back (bottom right)
views of the ENTOTO Observatory Research Center currently undergoing major
construction. The red arrows indicate the room where the MNM is currently
installed.

Fig. 2: The asymptotic cones of vertically incident primary particles reaching
each monitor in the African neutron monitor network.

Fig. 3: The top panel shows the minute-averaged (blue) and hourly-averaged
(red) count rate as a function of time. The middle and bottom panels show the
measured temperature and pressure, respectively.

Fig. 4: A zoom in of time interval 2 as identified in Fig. 3.

##  2 The ENTOTO neutron monitor station

Table 1: Details of the newly established ENTOTO MNM, along with existing NM stations forming the African NM network. Station | Local time | Latitude | Longitude | Altitude | Cut-off rigidity
---|---|---|---|---|---
ENTOTO, Ethiopia | UTC + 3 hr | 9∘ 6’ N | 38∘ 48’ E | 3175 m.a.s.l. | 16 GV
Tsumeb, Namibia | UTC + 2 hr | 19∘ 12’ S | 17∘ 35’ E | 1240 m.a.s.l. | 9.2 GV
Potchefstroom, South Africa | UTC + 2 hr | 26∘ 41.9’ S | 27∘ 5.6’ E | 1351 m.a.s.l. | 7.2 GV
Hermanus, South Africa | UTC + 2 hr | 34∘ 25.5’ S | 19∘ 13.5’ E | 26 m.a.s.l. | 4.9 GV
SANAE, Antarctica | UTC | 71∘ 40’ S | 2∘ 51’ W | 856 m.a.s.l. | 0.8 GV

A BF3 version of the MNM, recently reviewed in detail by Strauss et al.
(2020), donated from the North-West University of South Africa to the Space
Science and Applications Research and Development department of the Ethiopian
Space Science and Technology Institute (ESSTI) of Ethiopia, was recently
installed at the premises of the ENTOTO Observatory Research Center (EORC)
located in the outskirts of Addis Ababa, the capital city of Ethiopia. Fig. 1
shows recent pictures of this site which is currently undergoing major
construction. The red arrows indicate the position where the MNM is currently
installed. ENTOTO is in a mountainous landscape that reaches an
altitude/elevation of 3200 m.a.s.l. In fact, the peak altitude of 3200 m.a.s.l
is reached at the EORC premises. Since the name ENTOTO is associated with the
vast and mountainous terrain that surrounds most of the northern and north-
western outskirts of Addis Ababa, we have decided to refer to this MNM station
as the “ENTOTO Neutron Monitor”, abbreviated as ENTO. Fig. 2 shows the
asymptotic cones of acceptance for the African NM network using the model of
Smart et al. (2000). The highest rigidity particle considered is 30 GV (the
data point closest to the station), decreasing linearly until the cut-off
rigidity is reached (data point furthest away from the station). The ENTOTO
MNM, being installed very close to the magnetic equator, primarily measures
particles incident along the Earth’s equatorial regions. Details of the ENTOTO
NM station is summarized in Tab. 1, along with existing NM stations forming
the African NM network.

###  2.1 Unprocessed results

The raw data from the ENTOTO MNM is shown in Fig. 3. The top panel shows the
minute-averaged (blue) and hourly-averaged (red) count rate as a function of
time with two time intervals identified. These are discussed further in later
sections. The average (uncorrected for pressure changes) count rate of the
monitor is $\sim 290$/min. The middle and bottom panels show the measured
temperature and pressure, respectively. The data gaps is caused by power
outages at the installation site.

###  2.2 Construction noise

During early 2022, major construction unfortunately started at the ENTOTO
observatory site. Mechanical vibration and possible electrical interference
from these activities are believed to contribute to the higher levels of noise
present during time interval 2, identified in Fig. 3. The count rate data from
this time interval is shown again in Fig. 4, where the shaded regions indicate
times where the majority of the construction occurs: 9:00 - 17:00 local time.
Unfortunately this additional noise component cannot be corrected for and the
data from time interval 2 is not used for further analysis in the rest of the
work.

##  3 The Neutron monitor waiting time distribution

###  3.1 Origin of neutron monitor multiplicities

For either of the 3He or BF3 filling gases, an electrical pulse is produced
via a neutron capture process (Knoll, 2010), i.e.

${}^{10}\mathrm{B}+\mathrm{n}$ $\displaystyle\rightarrow$
$\displaystyle\left\\{\begin{array}[]{ccc}^{7}\mathrm{Li}+\alpha+2.78\,\mathrm{MeV}\\\
^{7}\mathrm{Li}^{*}+\alpha+2.30\,\mathrm{MeV}\end{array}\right.$ (4)

or

${}^{3}\mathrm{He}+\mathrm{n}\rightarrow\,^{3}\mathrm{H}+\mathrm{p}+0.76\,\mathrm{MeV}$
(5)

that ionizes a small portion of the filling gas. The pulse-height measured in
the NM is therefore independent of energy of the incident atmospheric
particles. Low- and high-energy atmospheric hadrons, however, interact with
the lead producer in different ways. Low energy protons and neutrons interact
with the monitor, and thus the proportional gas, in a random fashion and their
detected pulse show a stochastic nature with subsequent pulses unrelated to
each other. A high energy neutron or proton, on the other hand, can interact
with the lead producer to form a number of low energy evaporation neutrons
(e.g. Bieber et al., 2004). These neutrons are observed as a number of pulses
over a short period of time, showing a high level of temporal correlation.
This is usually expressed in terms of the waiting time distribution (i.e. the
time between subsequent pulses observed in the monitor) as the level of
multiplicity (i.e. the number of pulses observed in a certain time increment).
By thus looking at the waiting time distribution observed by the monitor
(examples are shown in the next section) these two components can be
distinguished; a low multiplicity component at long waiting times and a high
multiplicity, highly correlated, component at short waiting times. By
examining the ratio of these components, which we refer to as the correlation
ratio, some information of the incident particle spectrum can, in principle,
be reconstructed (see e.g. Ruffolo et al., 2016; Mangeard et al., 2016;
Banglieng et al., 2020).

###  3.2 An illustrative example: Lead vs. lead-free neutron monitors

Fig. 5: The waiting time distribution (left panel) and integrated waiting time
distribution (right panel) for two identical BF3-filled mini-NMs; one operated
with lead (blue curves) and one without (red curves). In the left panel, the 1
and 10 counts limits are shown (gray and green dashed curves), while the low
multiplicity portions of the distributions are fitted with exponential
distributions (blue and red dashed curves). The vertical dashed line on the
right panel indicates the approximate change from high to low multiplicities
observed in the detector with lead at $\sim 1$ms.

To illustrate how the waiting time distribution is formed by different neutron
populations, we performed the following test: Two identical BF3 filled MNMs
were placed next to each other in the physics laboratory in Potchefstroom. The
MNMs were operated for a number of days to confirm that the electronics were
also identical, with identical count rates (within statistical variations)
obtained from both monitors. The lead in one monitor was then removed and both
MNMs operated for a day. The resulting waiting time distributions (simply
calculated as the probability distribution of the time elapsed between
successive counts in the detector) are shown in the left panel of Fig. 5,
where the low multiplicity (long waiting time) distribution is fitted with the
following exponential distribution

$\mathcal{D}(\Delta t)=\mathcal{D}_{0}\exp\left(\frac{\Delta t-\,^{0}\Delta
t}{\tau}\right),$ (6)

where $\mathcal{D}_{0}$, ${}^{0}\Delta t$, and $\tau$ are fit constants and
$\Delta t$ is the waiting time between successive counts (see also the
discussion by Ruffolo et al., 2016).

Clearly, the monitor with the lead producer (blue curve in Fig. 5) shows the
high multiplicity (high level of temporal correlation) distribution which is
absent in the lead-free monitor (red curve in Fig. 5). However, the low
multiplicity distributions are also significantly different with a higher
count rate observed, even at longer waiting times, for the monitor with lead
(roughly a factor of 2). A higher count rate also changes the low multiplicity
exponential distribution (see Eq. 6), with the lead monitor well described
with a $\tau$ parameter roughly twice that of the lead-free monitor. The low
multiplicity part (at longer waiting times) are detected neutrons that are
therefore consistent with particles interacting randomly with the detector
with the resulting counts unrelated.

In the right panel of Fig. 5, we calculated, using measurements presented in
the left panel, the total number of counts measured by these detectors as a
function of simulated dead time of the detector, $\Delta T$,

$\mathcal{C}(\Delta T)=\int_{\Delta T}^{\infty}\mathcal{D}(\Delta t)\Delta t,$
(7)

which is essentially an integration of the waiting time distribution over all
possible waiting times. The vertical dashed line at 1 ms indicates the
changeover from the low to the high multiplicity distribution. The leaded
monitor has an average count rate of $\sim 95$/min. From the integrated
multiplicity distribution we estimate that the low multiplicity (long waiting
time) distribution of the monitor with lead has an average count rate of
$\sim$80/min while the high multiplicity (short waiting time) distribution
contributes at a rate of $\sim$15/min. This suggests that, for the leaded
monitor, $\sim$20% of the measured neutrons are high multiplicity neutrons
produced in the lead producer by high energy protons and/or neutrons, while
the remaining $\sim$80% are low multiplicity neutrons produced either in the
lead producer or in the atmosphere. The monitor without lead gives an average
count rate of $\sim$40/min which are presumably due to neutrons produced in
the atmosphere. This suggests that, for the BF3 version of the mini-NM located
in Potchefstroom, about half of low multiplicity neutrons measured by the
leaded monitor are already formed in the atmosphere, contributing with a rate
of $\sim$40/min towards the total count rate. It is also instructive to
remember that $\sim 90\%$ of the atmospheric particles detected by a typical
NM are atmospheric neutrons (Mangeard et al., 2016). Also note that these
estimates will be different for different NM designs and will depend on the
local environment and incident particle spectrum.

##  4 Measuring and quantifying the waiting time distribution

###  4.1 Correlated and uncorrelated count rates

Fig. 6: Similar to Fig. 5, but now calculate using a hour’s measurements of
the ENTOTO MNM.

Fig. 7: The top panel shows hourly averaged count rates for the low
multiplicity (blue), high multiplicity (green, multiplied by a factor of 4),
and the total distributions. The middle panel shows the hourly averaged
pressure and the bottom panel the ratio of the high multiplicity to low
multiplicity count rates, the so-called correlation ratio.

The waiting time distribution as measured by the ENTOTO MNM is shown in Fig.
6, with a similar format as Fig. 5. As expected, the uncorrelated low
multiplicity (long waiting times, $>2$ ms) and correlated high multiplicity
(short waiting times, $<2$ ms) distributions can be identified. The vertical
red dashed line in Fig. 6, at $\Delta T^{\prime}=2$ ms, indicates the assumed
change in distribution and used for the rest of the work to separate the two
distributions.

We now calculate the hourly waiting time distribution, similar to Fig. 6, for
each hour in time interval 1 (as defined in Fig. 3). From these distributions,
we calculate the hourly count rate of the high multiplicity component as

$\mathcal{C}_{\mathrm{high}}(t,\Delta T^{\prime})=\int_{0}^{\Delta
T^{\prime}}\mathcal{D}(t,\Delta t)\Delta t,$ (8)

the count rate of the low multiplicity component as

$\mathcal{C}_{\mathrm{low}}(t,\Delta T^{\prime})=\int_{\Delta
T^{\prime}}^{\infty}\mathcal{D}(t,\Delta t)\Delta t,$ (9)

and the total count rate as

$\mathcal{C}_{\mathrm{total}}(t)=\mathcal{C}_{\mathrm{low}}(t,\Delta
T^{\prime})+\mathcal{C}_{\mathrm{high}}(t,\Delta
T^{\prime})=\int_{0}^{\infty}\mathcal{D}(t,\Delta t)\Delta t.$ (10)

These different count rates are shown as a function of time in the top panel
of Fig. 7 with the hourly averaged pressure in the middle panel. Note that for
these calculations we only use complete hourly intervals with a full 60
minutes of measurements. The data is therefore much more sparse than the
minute-averaged measurements shown in Fig. 3 which contains a large number of
data gaps. In the bottom panel we calculate the so-called correlation ratio,
as

$\mathcal{R}(t,\Delta T^{\prime})=\frac{\mathcal{C}_{\mathrm{high}}(t,\Delta
T^{\prime})}{\mathcal{C}_{\mathrm{low}}(t,\Delta T^{\prime})}\times 100\%,$
(11)

which we expect to be a proxy for the spectral index of the incident
atmospheric particles. The data presented here gives a ratio of $\sim 27\%$
when using a value of $\Delta T^{\prime}=$ 2ms. As this is essentially the
ratio of correlated to uncorrelated counts in the monitor, we expect the ratio
to increase (more correlated, high multiplicity counts) as the spectrum of
incident particles become harder (more high energy particles). We test for any
pressure dependence of the different count rates, and the ratio thereof, in
the next section.

Fig. 8: The left panel shows the barometric correction applied separately for
the 3 different count rates identified in Sec. 4.1, while the right panel
shows the same calculation for the correlation ratio.

###  4.2 Pressure corrections

Assuming the standard exponential correlation between the count rate and
atmospheric pressure, the hourly count rate is expected to vary with varying
atmospheric pressure, $P$, as

$\mathcal{C}_{\mathrm{x}}=\langle\mathcal{C}_{\mathrm{x}}\rangle\exp\left(-\beta_{\mathrm{x}}\Delta
P\right),$ (12)

where $x$ refers to either the low, high, or total count rate, $\Delta
P=P-\langle P\rangle$, and $\langle\cdot\rangle$ indicates long-term
averaging. The barometric coefficients, $\beta_{\mathrm{x}}$, for the
different count rates are calculated in the left panel of Fig. 8 as the
gradient of a linear regression, with resulting values included in the legend
where the colour of the regresion line corresponds to that of the data points.
As the high multiplicity counts are produced by higher energy atmospheric
particles, we expect the corresponding barometric coefficient to be smaller
than of the low multiplicity component, based on the work of Tirado-Bueno et
al. (2021). While there might be an indication of this, the different
coefficients are the same within the (relatively large) fit errors.

The correlation ratio is expected to have a pressure dependence of the form,

$\mathcal{R}=\frac{\mathcal{C}_{\mathrm{high}}}{\mathcal{C}_{\mathrm{low}}}=\frac{\langle\mathcal{C}_{\mathrm{high}}\rangle}{\langle\mathcal{C}_{\mathrm{low}}\rangle}\exp\left[-\left(\beta_{\mathrm{high}}-\beta_{\mathrm{low}}\right)\Delta
P\right],$ (13)

with an effective pressure coefficient of
$\beta=\beta_{\mathrm{high}}-\beta_{\mathrm{low}}$. The pressure dependence of
$\mathcal{R}$ is therefore expected to be weaker than that of the individual
count rates. This is confirmed in the right panel of Fig. 8 where we apply a
similar pressure correction to the correlation ratio. Within the fit errors we
find the correlation ratio to be independent of pressure changes.

Fig. 9: Similar to Figs. 6 and 7, but now for a 3He (top panels) and a BF3
(bottom panels) MNM housed in the laboratory in Potchefstroom.

###  4.3 Comparison with other monitors

We end the analysis presented here with a comparison between the ENTOTO
waiting time distribution and the time distributions measured by a 3He and BF3
leaded MNM housed in the laboratory in Potchefstroom. The results for these
MNMs are shown in Fig. 9. Of course, the waiting time distributions show
similarities with that of ENTOTO, with the change between high and low
multiplicity distributions again occurring close to $\sim 2$ ms. The right
panels of the figure show the behaviour of the different count rates, and the
correlation ratio, as a function of time. For the 3He tube, the ratio is $\sim
18\%$, and for the BF3 tube it is $\sim 14\%$. It should be kept in mind that
the 3He version of the MNM has a thicker lead producer (due to a thinner tube)
than the BF3 version which might explain the additional $\sim 3\%$ of high-
multiplicity neutrons detected.

##  5 Summary, conclusions, and outlook

We have discussed a newly established MNM station installed at the ENTOTO
Observatory Research Center outside of Addis Ababa, Ethiopia. Preliminary data
from the ENTOTO MNM is shown and discussed, with a special focus on
characterising the waiting time distribution.

Using the waiting time distribution, as observed by this new station, we
calculated the ratio of correlated to uncorrelated counts as a proxy for the
spectral index of the incident atmospheric particles. While similar proxies
were used in the past, e.g. the leader fraction of Ruffolo et al. (2016), our
correlation ratio, as defined here, is a natural characterization of the
waiting time distribution as measured by our MNMs. We hope to also calculate
the correlation ratio for other NMs in future, as well track how this ratio
changes during temporal events such as ground level enhancement and Forbush
decreases.

We calculated the pressure dependence of different count rates of the ENTOTO
MNM, and found very similar values for both the correlated and uncorrelated
count rates. This suggests that the pressure dependence of correlation ratio
will be rather weak and, for typical MNM count rates, probably negligible as
the uncertainty in the measurements is dominated by the statistical errors
associated with low count rates.

The ENTOTO MNM, at a cut-off rigidity of $\sim 16$ GV, has a current
correlation ratio of $\sim 27\%$. We also calculated this quantity for two
MNMs (with a BF3 and 3He tube) currently undergoing testing at the laboratory
in Potchefstroom. These MNMs recorded ratios of $\sim 14\%$ and $\sim 18\%$,
respectively. Given the fact that Potchefstroom has an approximate cut-off
rigidity of only $\sim 7$ GV, the higher ENTOTO correlation ratio can be
explained by the fact that the ENTOTO MNM measures higher rigidity particles,
resulting in a higher ratio of correlated neutrons being detected inside the
monitor, partially validating our proposal that this ratio will serve as a
proxy for the spectral shape of the incident atmospheric particles. We will
continue to investigate the use of the correlation ratio for this purpose,
especially during transient phenomena such as Forbush decreases, and report
such results in due course.

## Acknowledgement

Figures prepared with Matplotlib (Hunter, 2007) and certain calculations done
with NumPy (Harris et al., 2020). This work is based on the research supported
in part by the National Research Foundation of South Africa (NRF grant
numbers: 119424, 120847, and 120345). Similarly the authors would like to
acknowledge the Ethiopian Space Science and Technology Institute (ESSTI) for
hosting, maintaining, and monitoring the instrument. Opinions expressed and
conclusions arrived at are those of the authors and are not necessarily to be
attributed to either the NRF or the ESSTI. We acknowledge support provided by
the North-West University (NWU) Instrument Making Department.

## References

  * Banglieng et al. (2020) Banglieng, C., Janthaloet, H., Ruffolo, D., Sáiz, A., Mitthumsiri, W., Muangha, P., Evenson, P., Nutaro, T., Pyle, R., Seunarine, S., Madsen, J., Mangeard, P. S., & Macatangay, R. (2020).  Tracking Cosmic-Ray Spectral Variation during 2007-2018 Using Neutron Monitor Time-delay Measurements.  The Astrophysical Journal, 890(1), 21. doi:10.3847/1538-4357/ab6661.
  * Bieber et al. (2004) Bieber, J. W., Clem, J. M., Duldig, M. L., Evenson, P. A., Humble, J. E., & Pyle, R. (2004).  Latitude survey observations of neutron monitor multiplicity.  Journal of Geophysical Research (Space Physics), 109(A12), A12106. doi:10.1029/2004JA010493.
  * Clem & Dorman (2000) Clem, J. M., & Dorman, L. I. (2000).  Neutron Monitor Response Functions.  Space Science Reviews, 93, 335–359. doi:10.1023/A:1026508915269.
  * Harris et al. (2020) Harris, C. R., Millman, K. J., van der Walt, S. J., Gommers, R., Virtanen, P., Cournapeau, D., Wieser, E., Taylor, J., Berg, S., Smith, N. J., Kern, R., Picus, M., Hoyer, S., van Kerkwijk, M. H., Brett, M., Haldane, A., del Río, J. F., Wiebe, M., Peterson, P., Gérard-Marchant, P., Sheppard, K., Reddy, T., Weckesser, W., Abbasi, H., Gohlke, C., & Oliphant, T. E. (2020).  Array programming with NumPy.  Nature, 585, 357–362. doi:10.1038/s41586-020-2649-2.
  * Heber et al. (2015) Heber, B., Galsdorf, D., Gieseler, J., Herbst, K., Walter, M., Stoessl, A., Moraal, H., Krüger, H., & Benade, G. (2015).  Mini neutron monitor measurements at the Neumayer III station and on the German research vessel Polarstern.  In 34th International Cosmic Ray Conference (ICRC2015) (p. 122).  volume 34 of International Cosmic Ray Conference.
  * Hunter (2007) Hunter, J. D. (2007).  Matplotlib: A 2d graphics environment.  Computing in Science & Engineering, 9(3), 90–95. doi:10.1109/MCSE.2007.55.
  * Knoll (2010) Knoll, G. F. (2010).  Radiation Detection and Measurement, 4th ed..  New York, NY: Wiley.
  * Krüger et al. (2008) Krüger, H., Moraal, H., Bieber, J. W., Clem, J. M., Evenson, P. A., Pyle, K. R., Duldig, M. L., & Humble, J. E. (2008).  A calibration neutron monitor: Energy response and instrumental temperature sensitivity.  Journal of Geophysical Research (Space Physics), 113(A8), A08101. doi:10.1029/2008JA013229.
  * Mangeard et al. (2016) Mangeard, P. S., Ruffolo, D., Sáiz, A., Nuntiyakul, W., Bieber, J. W., Clem, J., Evenson, P., Pyle, R., Duldig, M. L., & Humble, J. E. (2016).  Dependence of the neutron monitor count rate and time delay distribution on the rigidity spectrum of primary cosmic rays.  Journal of Geophysical Research (Space Physics), 121(12), 11,620–11,636. doi:10.1002/2016JA023515.
  * Mishev & Usoskin (2020) Mishev, A., & Usoskin, I. (2020).  Current status and possible extension of the global neutron monitor network.  Journal of Space Weather and Space Climate, 10, 17. doi:10.1051/swsc/2020020. arXiv:2005.12621.
  * Mishev et al. (2020) Mishev, A. L., Koldobskiy, S. A., Kovaltsov, G. A., Gil, A., & Usoskin, I. G. (2020).  Updated Neutron-Monitor Yield Function: Bridging Between In Situ and Ground-Based Cosmic Ray Measurements.  Journal of Geophysical Research (Space Physics), 125(2), e27433. doi:10.1029/2019JA027433.
  * Poluianov et al. (2015) Poluianov, S., Usoskin, I., Mishev, A., Moraal, H., Kruger, H., Casasanta, G., Traversi, R., & Udisti, R. (2015).  Mini Neutron Monitors at Concordia Research Station, Central Antarctica.  Journal of Astronomy and Space Sciences, 32(4), 281--287. doi:10.5140/JASS.2015.32.4.281.
  * Ruffolo et al. (2016) Ruffolo, D., Sáiz, A., Mangeard, P. S., Kamyan, N., Muangha, P., Nutaro, T., Sumran, S., Chaiwattana, C., Gasiprong, N., Channok, C., Wuttiya, C., Rujiwarodom, M., Tooprakai, P., Asavapibhop, B., Bieber, J. W., Clem, J., Evenson, P., & Munakata, K. (2016).  Monitoring Short-term Cosmic-ray Spectral Variations Using Neutron Monitor Time-delay Measurements.  Astrophysical Journal, 817(1), 38. doi:10.3847/0004-637X/817/1/38.
  * Simpson (2000) Simpson, J. A. (2000).  The Cosmic Ray Nucleonic Component: The Invention and Scientific Uses of the Neutron Monitor - (Keynote Lecture).  Space Science Reviews, 93, 11--32. doi:10.1023/A:1026567706183.
  * Smart et al. (2000) Smart, D. F., Shea, M. A., & Flückiger, E. O. (2000).  Magnetospheric Models and Trajectory Computations.  Space Science Reviews, 93, 305--333. doi:10.1023/A:1026556831199.
  * Stoker (1985) Stoker, P. H. (1985).  Spectra of Solar Proton Ground Level Events Using Neutron Monitor and Neutron Moderated Detector Recordings.  In 19th International Cosmic Ray Conference (ICRC19), Volume 4 (p. 114).  volume 4 of International Cosmic Ray Conference.
  * Strauss et al. (2020) Strauss, R. D., Poluianov, S., van der Merwe, C., Krüger, H., Diedericks, C., Krüger, H., Usoskin, I., Heber, B., Nndanganeni, R., Blanco-Ávalos, J., García-Tejedor, I., Herbst, K., Caballero-Lopez, R., Moloto, K., Lara, A., Walter, M., Giday, N. M., & Traversi, R. (2020).  The mini-neutron monitor: a new approach in neutron monitor design.  Journal of Space Weather and Space Climate, 10, 39. doi:10.1051/swsc/2020038.
  * Strauss et al. (2021) Strauss, R. D., van der Merwe, C., Diedericks, C., Krüger, H., Krüger, H. G., Moloto, K. D., Lotz, S., & Mosotho, G. M. (2021).  The updated SANAE neutron monitor.  Advances in Space Research, 68(6), 2661--2675. doi:10.1016/j.asr.2021.05.032. arXiv:2107.14289.
  * Tirado-Bueno et al. (2021) Tirado-Bueno, E., Mendoza-Torres, J. E., & de Mendonça, R. R. S. (2021).  Barometric coefficient dependence on the geomagnetic cutoff rigidity of neutron monitors.  Advances in Space Research, 68(6), 2631--2642. doi:10.1016/j.asr.2021.04.034.
  * Usoskin et al. (2015) Usoskin, I., Poluianov, S., Moraal, H., Krüger, H., Casasanta, G., Traversi, R., & Udisty, R. (2015).  A mini neutron monitor in Central Antarctica (Dome Concordia).  In 34th International Cosmic Ray Conference (ICRC2015) (p. 217).  volume 34 of International Cosmic Ray Conference.
  * Zreda et al. (2012) Zreda, M., Shuttleworth, W. J., Zeng, X., Zweck, C., Desilets, D., Franz, T., & Rosolem, R. (2012).  Cosmos: the cosmic-ray soil moisture observing system.  Hydrology and Earth System Sciences, 16(11), 4079--4099. URL: https://hess.copernicus.org/articles/16/4079/2012/. doi:10.5194/hess-16-4079-2012.


# Utility-Aware Load Shedding for Real-time Video Analytics at the Edge

Enrique Saurez∗<EMAIL_ADDRESS>Georgia Institute of Technology  Harshit
Gupta∗<EMAIL_ADDRESS>Georgia Institute of Technology  Henriette Röger
<EMAIL_ADDRESS>University of Stuttgart  Sukanya
Bhowmik<EMAIL_ADDRESS>University of Stuttgart
Umakishore Ramachandran<EMAIL_ADDRESS>Georgia Institute of Technology  Kurt
Rothermel<EMAIL_ADDRESS>University of Stuttgart

###### Abstract

Real-time video analytics typically require video frames to be processed by a
query to identify objects or activities of interest while adhering to an end-
to-end frame processing latency constraint. Such applications impose a
continuous and heavy load on backend compute and network infrastructure
because of the need to stream and process all video frames. Video data has
inherent redundancy and does not always contain an object of interest for a
given query. We leverage this property of video streams to propose a
lightweight Load Shedder that can be deployed on edge servers or on
inexpensive edge devices co-located with cameras and drop uninteresting video
frames. The proposed Load Shedder uses pixel-level color-based features to
calculate a utility score for each ingress video frame, which represents the
frame’s utility toward the query at hand. The Load Shedder uses a minimum
utility threshold to select interesting frames to send for query processing.
Dropping unnecessary frames enables the video analytics query in the backend
to meet the end-to-end latency constraint with fewer compute and network
resources. To guarantee a bounded end-to-end latency at runtime, we introduce
a control loop that monitors the backend load for the given query and
dynamically adjusts the utility threshold. Performance evaluations show that
the proposed Load Shedder selects a large portion of frames containing each
object of interest while meeting the end-to-end frame processing latency
constraint. Furthermore, the Load Shedder does not impose a significant
latency overhead when running on edge devices with modest compute resources.

###### Index Terms:

video analytics, edge computing, load shedding

**footnotetext: These authors contributed equally to this work.††footnotetext:
This work was supported by the German Research Foundation (DFG) under the
research grant ”PRECEPT II” (RO 1086/19-2 and BH 154/1-2).

##  I Introduction

Real-time video analytics has been gaining rapid popularity due to its utility
in applications such as surveillance[1], driving assistance and safety[2], and
factory automation[3]. Such applications are typically structured as a
pipeline of operators with the first operator consuming a stream of video
frames from cameras and feeding its output to the next operator, and so on.
Each operator executes a piece of the overall application logic, for instance,
object detection, classification, activity recognition, etc., and extracts
relevant insights from camera frames. We specifically focus on video analytics
pipelines with stringent end-to-end latency constraints, such that the
extracted insight from video processing could be used to trigger a real-time
response, e.g., alert to car driver. The increasing availability of high
quality and high frame rate cameras put significant pressure on the backend
compute and networking resources. Although the use of edge resources for
running geo-distributed video analytics has been proposed to minimize backhaul
bandwidth usage [4], the resource capacity of edge sites is typically limited
due to space and power constraints [5]. Oftentimes complex operators like
object detection pose heavy compute requirements, such as access to a GPU,
which imposes limitations on the number of cameras that can be served at a
given edge site.

Video streams possess two key characteristics that enable serving more number
of cameras with limited resources. Firstly, the appearance of the object-of-
interest for a given analytics query is not frequent[6], implying that a large
fraction of camera frames do not contain useful information. Secondly, when an
object-of-interest exists in a video stream, due to the high frame rate of
cameras it usually is present in multiple frames. Dropping a small portion of
the frames that an object-of-interest appear in does not affect the overall
fidelity of the results. These characteristics motivate the use of load
shedding techniques to shed irrelevant frames, to reduce the workload on the
application pipeline. Previous work in load shedding has focused on using
linear selectivities [7, 8] and work with structured queries and data [9, 10,
11]. Such techniques haven’t been explored for content-based shedding of
unstructured data such as video. Previous work in early-discard of video
frames either require expensive hardware for feature extraction [12, 13] or do
not tune the filtering parameters according to the processing load on the
backend video analytics pipeline [14].

In this work, we present a lightweight load shedding technique that uses a
per-query content-based utility function to determine if a frame should be
shed. The utility of a frame is calculated as a function of its color
distribution. Each query undergoes a learning phase during which the utility
function is built. The Load Shedder receives all ingress frames and it drops
those whose utility is below the baseline utility threshold. Due to inherent
variations in video streams’ contents, the utility threshold needs to be
dynamically tuned so that the load on backend analytics pipeline is within
manageable levels, and the end-to-end processing latency constraint of the
query is continuously met. The Load Shedder includes a feedback control-loop
that dynamically updates the utility threshold based on the current load on
the later stages of the video processing pipeline. This feedback from the
later stages ensures that the overall query processing pipeline functions
correctly despite differences in the content of the video stream compared to
the training set. We incorporate the proposed load shedding technique on a
video analytics platform and perform extensive evaluations with real-world
analytics queries and video datasets. Our contributions can be summarized as
follows:

  1. 1.

A workflow for building the per-frame utility function given a query and a
labeled training data set. The utility function should be lightweight, i.e.,
it should be able to process a high rate of ingress frames without imposing
significant latency overhead.

  2. 2.

A control loop that dynamically tunes the utility threshold based on the
current load on the query operators. The objective of the control loop is to
keep the end-to-end latency under a query-specific bound.

  3. 3.

Performance evaluation of the proposed load shedding approach to demonstrate
its efficacy.

The rest of the paper is structured as follows. Section II discusses the
context of this work and Section III presents the related work in the space of
load shedding for video analytics queries. Section IV presents the system
architecture and the load shedding approach in detail, including the training
phase and the dynamic tuning of utility thresholds. Section V presents the
design and results of experimental evaluation of the proposed approach.
Section VI presents a discussion of relevant questions stemming from this
research. Section VII ends the paper with conclusion and a discussion of
future work.

##  II Background and Problem Statement

We describe the context in which our proposed approach is to be employed,
followed by a formal definition of the problem statement.

###  II-A Context

Figure 1: Query model.

We target real-time video analytics queries that perform detection of target
objects of a specific color. Such queries are common in the domains of
surveillance (e.g, tracking red cars in response to an AMBER alert [15]),
traffic control (e.g., detecting if an emergency vehicle is stuck in traffic
[16]), search and rescue (e.g., locating humans in open water using drones
[17]), etc. Such queries typically process multiple frames containing a given
target object (e.g., a suspicious red car in first example) to extract
insights about the object (such as its direction of motion, or which street it
went to from an intersection). The query could be designed to process frames
containing target objects of a single color (e.g., red suspicious vehicle),
frames containing at least one object from the target colors (e.g., white
ambulance or red fire truck) or frames containing objects of all target
colors.

Fig. 1 shows the query model at a high level, which is composed of three
components: a filter, a sequence of one or more video processing operators
(e.g., Deep Neural Network based object detection), and a sink. The filter
discards frames with no useful information - for instance, filtering out
frames with contiguous groups of pixels (blobs) of a certain color larger than
a certain size. The video processing operators form the core of the query
logic. Finally, the sink analyzes the output labels of the video processing
operators and sends information to the relevant parties. Depending on the
dynamic content of video streams, the fraction of frames processed by the
video processing operators (e.g., heavyweight DNNs) and the sink varies with
time. This variation in processing load causes significant variation in end-
to-end latency of the system as well. To ensure real-time response, the
queries have a constraint on end-to-end latency of processing a frame
containing a target object. The end-to-end processing latency of a frame is
the total time taken between the generation of the frame by the camera to the
time when it is executed completely by the application query (including
communication delay).

(a)

(b)

(c)

Figure 2: Three deployment scenarios for a connected camera system in which
the proposed load shedding approach can be employed.

We consider a connected camera deployment which could (but not necessarily) be
assisted by an edge compute node available in proximity. We assume cameras to
contain limited compute capability for running background subtraction and
feature extraction (to be discussed in Section IV-B). Cameras send the
foreground of frames along with the associated features downstream. The
possible scenarios of the deployment of downstream components, i.e., the Load
Shedder and Application Query, are shown in Fig. 2. In each such scenario,
either the compute resource on the edge or the network bandwidth between edge
and cloud or between camera and cloud is the bottleneck resource, whose over-
utilization results in excessive queuing of video frames, eventually resulting
in violation of the end-to-end processing latency constraint. Hence, the Load
Shedder’s effective operation is crucial to make sure that the bottleneck
resource is not overloaded. The objective of the Load Shedder is to maximize
the fraction of frames containing each target object that are sent downstream
to the application query after shedding. The Load Shedder optimizes this
objective with the constraint of end-to-end processing latency being below the
query-specific bound.

###  II-B Problem Statement

We now formally define the problem statement to be solved by the Load Shedder
by mathematically expressing the objective function and latency constraint. We
define video streams as a continuous sequence of frames. Therefore, the source
video stream generated from a camera is denoted by
$V=[f_{1},f_{2},\cdots,f_{m}]$. We define an application query as
$Q=[q_{1},\cdots,q_{n}]$, where $q_{i}$ denotes a video processing operator
(including filtering), which reads input from the output of $q_{i-1}$ and
feeds into the input of $q_{i+1}$. The first operator in a query always reads
the combined video stream coming from the multiple cameras it is serving, as
shown in Fig. 1. We denote the output stream of operator $q_{i}$ with input
stream $v$ as $q_{i}\left(v\right)$. We define the set of target objects
detected by a query $Q$ in video $V$ as $T_{Q}\left(V\right)$ as in Eq. 1. We
represent frame $f$ containing target object $o$ by the relation $o\in f$.

$T_{Q}\left(V\right)=\\{\text{target objects in }V\text{ detected by }Q\\}$
(1)

Now, introducing the Load Shedder component into the video query $Q$, we
construct a query $Q^{\prime}$ of the form $[q_{0},q_{1},\cdots,q_{n}]$, where
$q_{0}$ is the Load Shedder component, also denoted by $LS$. The Quality of
Result (QoR) metric we use in this work is designed to measure the number of
frames for each target object that are sent downstream by the Load Shedder
$LS$ in query $Q^{\prime}$, i.e., belonging to the output stream
$LS\left(V\right)$. We define the per-target-object QoR for target object $o$
in Eq. 2. QoR metric has a value between 0 and 1.

$QoR_{Q}\left(o,LS,V\right)=\dfrac{|f\in LS\left(V\right):o\in f|}{|f\in
V:o\in f|}$ (2)

The overall QoR metric for query $Q$ with the Load Shedder $LS$ against source
video $V$ encompassing all target objects of interest is defined in Eq. 3.
This metric calculates the average per-object QoR metric over all target
objects. Thus, this metric quantitatively measures the aggregate performance
of the Load Shedder for a given source video.

$QoR_{Q}\left(LS,V\right)=\dfrac{\sum_{o\in
T_{Q}\left(V\right)}QoR_{Q}\left(o,LS,V\right)}{|T_{Q}\left(V\right)|}$ (3)

For a given video stream $V=[f_{1},f_{2},\cdots,f_{m}]$, we define the end-to-
end delay experienced by frame $f$ of video $V$ when processed by query
$Q^{\prime}$ as $E2E_{V,Q^{\prime}}\left(f\right)$ which is expressed as shown
in Eq. 4, where $q_{k}$ is the last operator in $Q^{\prime}$ that processes
frame $f$.

$E2E_{V,Q^{\prime}}\left(f\right)=\sum_{i=0}^{k}queue\left(q_{i},f\right)+exec\left(q_{i},f\right)$
(4)

The objective is to maximize the Quality of Result (QoR), while dropping
frames such that the given end-to-end latency bound $LB$ is met. More
formally, the objective is defined as follows.

$\displaystyle Maximize$ $\displaystyle\ QoR_{Q}\left(LS,V\right)$ (5) s.t.
$\displaystyle\ E2E_{V,Q^{\prime}}\left(f\right)\leq LB\quad\forall~{}f\in V$

##  III Related Work

Resource Management in Online Video Analytics: Live video analytics is an
extremely compute and network resource intensive application. Prior art has
adopted two main approaches for managing the high resource requirements of
this application - tuning the configuration of the input stream and video
processing operators (e.g., frame rate, resolution, etc.) and early discard of
uninteresting frames. Online adaptation of camera streams and video processing
operators has been explored in several prior works [18, 19, 20]. These works
target scenarios where end-to-end latency of the order of sew seconds can be
tolerated. Their primary objective is to optimize cost of resources needed for
supporting all video streams while also maintaining high accuracy. Although
these works differ from our proposed approach in terms of objectives, their
technique can be adopted to work complementary to our proposed approach.

Early-Discard Filtering of Video: Multiple approaches have been taken for
performing early discard of unnecessary video frames so that compute and
network costs of streaming and processing them can be avoided. Glimpse [21]
proposed a hardware-software add-on that could use low-powered coarse-grained
vision modalities to filter out frames irrelevant to the query at hand. The
system uses specialized hardware for motion detection, temperature
measurement, etc., which are not available on the cameras in our scenarios.
Zhang, et al., [22] use a multi-stage pipeline of operators to determine
whether a frame is relevant to a query, wherein the operators are implemented
using GPUs and impose significant latency overhead to the video processing
pipeline’s performance. FilterForward [12] consists of a base DNN whose
intermediate layers’ outputs are used by a per-application binary classifier
that decides whether to filter out a frame or not. However, in that system,
the execution latency of the base model itself is very high (¿200ms) and the
cost of performing early discard amortizes only when running at least 4
concurrent application queries per base model. The EarlyDiscard strategy
proposed in Wang, et al., [23] uses an inexpensive DNN to perform filtering of
frames. However, there is no way to tune the filter so as to ensure end-to-end
latency guarantee of video processing. Reducto [14] makes use of difference in
low-level visual features (such as pixels, edges, etc.) across consecutive
frames to determine if processing the new frame would result in a difference
in the query’s result. However, it operates at 1-second granularity, meaning
that it cannot guarantee end-to-end latency less than that. Additionally, it
does not support tuning of the filtering based on load experienced by backend
application query.

In summary, previous work on early discard of frames either use expensive
filters that add significant latency overhead to the video processing
pipeline, or do not support the fine-tuning of the filter to ensure end-to-end
latency.

##  IV Utility-Aware Load-shedding

In this section, we present a high-level architecture of the proposed load
shedding system, highlighting the interactions between different components.
Then we describe the design and functionality of each individual component in
isolation.

###  IV-A System Architecture

Figure 3: Architecture of the proposed load-shedding approach.

We extend real-time video analytics systems which are equipped with edge-
computing capability (referring to both edge sites and compute capability co-
located with cameras) with our proposed load shedding system that sheds a
portion of the input frames to maintain the given latency bound ($LB$) during
overload. Figure 3 shows the main components involved in performing the
aforementioned tasks and their interactions—the Load Shedder, the application
query, and the Control Loop. Each operator (including Load Shedder) reads from
an ingress queue which is (populated by the upstream operator or source
cameras) and pushes the output data to the egress queue.

The load shedding system must perform two primary tasks—(1) decide when to
shed and how much to shed, and (2) decide which frames to shed. We describe
the latter task first, for which the Load Shedder computes a utility/
importance value for each video frame that denotes the probability of the
frame being useful for the application query. The utility is calculated using
the color content of the frame and the application query at hand. The
intuition behind the design of the Load Shedder is to discard video frames
that have a low probability of being useful for the given application query
(see Section IV-B). The Load Shedder can be dynamically configured with a
utility threshold, such that it drops frames with utility less than the
threshold.

The Control Loop component dynamically computes the utility threshold and
updates the Load Shedder. The utility threshold calculation is done so as to
sustain the current load on the application query, while meeting the end-to-
end latency bound ($LB$) (see Section IV-D). More specifically, the Control
Loop component monitors the queue lengths of each operator in the query, and
estimates the current observed end-to-end latency. Based on the observed end-
to-end latency and the query’s latency requirement, the Control Loop computes
the fraction of frames that should be dropped by the Load Shedder, which is
then transformed into a utility threshold (see Section IV-C). Transforming the
desired frame drop rate to a utility threshold is done on the basis of the
utility distribution of frames observed in the past.

The subsequent sections describe the per-frame utility calculation function
(exploration of color features for its design), the calculation of utility
threshold for a given target drop rate, and the control loop in more detail.

Notation | Description
---|---
$\mathcal{D}$ | Training data set
f | Frame
l | Label $\in\\{0,1\\}$
C | Color as a range of Hue
$HF_{C}\left(f\right)$ | Hue Fraction of frame $f$ for color $C$
$PF_{C}^{\left(i,j\right)}\left(f\right)$ | Pixel Fraction of frame $f$ for color $C$
| and saturation-value bin $\left(i,j\right)$
$M_{C,+ve}^{\left(i,j\right)}$ | Correlation metric of saturation-value
| bin $\left(i,j\right)$ of color $C$ with +ve frames
$U_{C}\left(f\right)$ | Utility value of frame $f$ for color $C$
TABLE I: Notations used in the formulation.

###  IV-B Building the utility function

The Load Shedder makes the decision of whether to discard a frame or not based
on each frame’s utility value - which is calculated by the utility function.
It takes as input the frame’s color-based features and computes a scalar
utility value.

####  IV-B1 Hue-Saturation-Value Color Model

We use the Hue-Saturation-Value (HSV) model for representing the color of
pixels, which represents how colors appear under light (Fig. 4). The HSV model
is widely used in computer vision applications over the Red-Green-Blue (RGB)
model because HSV separates the color information from intensity information
(which helps deal with situations like lighting changes or shadows). We use
the HSV triplet of each pixel to calculate the distribution of colors in each
frame, which forms the input feature set for the utility function (described
in detail in subsequent sections). The developer of the Application Query
specifies the color of the target objects in terms of a hue range $C$ as input
to the Load Shedder. For instance, the color red is represented using the hue
ranges $[0,10)\cup[170,180)$.

Figure 4:  HSV Color Model [24]. Hue represents the color itself (or the
dominant wavelength), Saturation represents the brilliance and intensity of
the color, while Value defines the lightness or darkness of the color. The
ranges of Hue, Saturation and Value we use are $[0,180)$, $[0,256)$, and
$[0,256)$ respectively.

####  IV-B2 Training data

To train the utility function, we use a labeled stream of videos from multiple
cameras as training data set. Each element of the training data set
$\mathcal{D}$ is of the form $\left(f,l\right)$, where $f$ represents the
frame and $l$ represents the label. Each frame $f$ is described by a list of
pixels, with each pixel being represented by a triplet $\left(h,s,v\right)$.
The $h,s,v$ elements of a pixel’s notation denote the pixel’s Hue, Saturation
and Value fields respectively. The label $l$ tells whether the frame contains
an object of interest, i.e., whether the frame was a match for the given
query. Henceforth, we use the term positive to denote frames which contain one
or more target objects, and negative to denote frames which do not contain
them.

The goal of the utility function is to be able to separate the computed
utilities of positive and negative frames, such that using a utility threshold
would result in effective load shedding. In the remaining part of this
section, we first outline our observations from the training data on how to
separate positive and negative frames using the HSV model. Based on these
observations, we build our utility function.

####  IV-B3 Hue as feature for separating positive and negative frames

We first explore the use of the Hue field of pixels to calculate whether the
given frame contains a target object of the given color. We do so by computing
a metric Hue Fraction for the color $C$, denoted by $HF_{C}$.

$HF_{C}\left(f\right)=\dfrac{|\text{pixel }p\in f:hue\left(p\right)\in
C|}{|\text{pixel }p\in f|}$ (6)

A higher Hue Fraction would imply higher likelihood for the frame to contain a
target object of a given color. Hence, a threshold-based approach on $HF_{C}$
is a candidate for the Load Shedder. However, our analysis of hue fractions of
frames in our dataset showed that the distribution of $HF_{C}$ for negative
frames overlaps significantly with positive frames across all videos. For
instance, Fig. 5(a) shows the hue fractions of the color Red of all frames
across all videos in the dataset; it can be seen that the hue fraction
distribution of positive frames overlaps with negative frames. This overlap
would prevent a threshold-based approach on the hue fraction from effectively
differentiating between positive and negative frames. This effect is captured
in Fig. 5(b), where the per-object QoR metric drops steeply with hue fraction
thresholds without achieving a significant frame drop rate. We posit that this
overlap in distribution is because both positive and negative frames contain
red-colored pixels; however, the saturation and value fields of those pixels
in the positive and negative frames would have distinctly discernible
distributions for the two.

(a) Distribution of Hue Fraction of color RED over videos in the training
dataset.

(b) QoR and Drop Rate (both ranging from 0 to 1) vs. HF threshold for RED
color.

Figure 5: Results of Hue Fraction as a feature for discriminating between
positive and negative frames. Fig. 5(a) shows that Hue Fraction of negative
frames has significant overlap with positive frames. Fig. 5(b) shows that high
frame drop rate cannot be achieved without a significant drop in QoR metric.

####  IV-B4 Using Saturation and Value fields for differentiating frames

In order to separate positive frames from negative ones, we analyze the
distribution of Saturation and Value fields for Red pixels across videos. We
discretize the range of pixel saturation and value into bins of size $s$ and
$v$ respectively. We define two functions $sat\\_bin$ and $val\\_bin$ that map
a pixel’s saturation $sat\left(p\right)$ and value $val\left(p\right)$
respectively to their corresponding bins.

$sat\\_bin\left(p\right)=i\iff i\cdot s\leq
sat\left(p\right)<\left(i+1\right)\cdot s$ (7) $val\\_bin\left(p\right)=j\iff
j\cdot v\leq val\left(p\right)<\left(j+1\right)\cdot v$ (8)

We leverage the division of the saturation and value range into bins to
transform each frame $f$ into a two-dimensional matrix for a given color $C$,
such that each element of the 2D matrix denotes the fraction of pixels
belonging to a particular saturation and value bin.

$PF_{C}\left(f\right)=\begin{pmatrix}PF_{C}^{\left(0,0\right)}\left(f\right)&PF_{C}^{\left(0,1\right)}\left(f\right)&\cdots&PF_{C}^{\left(0,n\right)}\left(f\right)\\\
PF_{C}^{\left(1,0\right)}\left(f\right)&PF_{C}^{\left(1,1\right)}\left(f\right)&\cdots&PF_{C}^{\left(1,n\right)}\left(f\right)\\\
\vdots&\vdots&\ddots&\vdots\\\
PF_{C}^{\left(m,0\right)}\left(f\right)&PF_{C}^{\left(m,1\right)}\left(f\right)&\cdots&PF_{C}^{\left(m,n\right)}\left(f\right)\end{pmatrix}$

(9)

Where $PF_{C}^{\left(i,j\right)}$ is the fraction of pixels whose hue falls in
the range $C$ and their saturation and value fall into the $i^{th}$ and
$j^{th}$ bin respectively. The number of bins for saturation and value are
$B_{S}$ and $B_{V}$ respectively.

$PF_{C}^{\left(i,j\right)}\left(f\right)=\dfrac{|\text{pixel }p\in
f:hue\left(p\right)\in C\land in\\_bin(p,i,j)|}{|\text{pixel }p\in
f:hue\left(p\right)\in C|}$

(10)

$in\\_bin(p,i,j)=\left(bin_{sat}\left(p\right)=i\land
bin_{val}\left(p\right)=j\right)$ (11)

Figure 6: Distribution of Saturation and Value fields for positive
($M_{C,true}$) and negative frames ($M_{C,false}$) across all videos in the
dataset. Bins with high saturation are better differentiators of positive
frames.

Using the per-frame distribution of pixels in various saturation-value bins,
we quantify how useful each such bin is in classifying a frame as positive or
negative. We compute a metric for each saturation-value bin using the pixel
distribution of positive and negative frames that denotes the correlation of
the bin with the particular label (positive or negative) for a given frame.

$M_{C,+ve}^{\left(i,j\right)}=\text{AVG
}PF_{C}^{\left(i,j\right)}\left(f\right)\forall\left(f,1\right)\in\mathcal{D}$
(12)

$M_{C,-ve}^{\left(i,j\right)}=\text{AVG
}PF_{C}^{\left(i,j\right)}\left(f\right)\forall\left(f,0\right)\in\mathcal{D}$
(13)

The distribution of above utility for the color Red, i.e., $M_{C,true}$ and
$M_{C,false}$ is shown in Fig. 6. The bins with higher saturation value are
much stronger indicators of whether a frame is positive.

####  IV-B5 Computing per-frame utility

We use the utility of each saturation-value bin (from Eq. 12 and Eq. 13) to
compute the utility value for a frame. The utility is a weighted sum of the
$M_{C,+ve}^{\left(i,j\right)}$ value for each saturation-value bin, weighted
by the pixel fraction of the frame in that bin.

$U_{C}\left(f\right)=M_{C,+ve}^{\left(i,j\right)}\cdot
PF_{C}^{\left(i,j\right)}\left(f\right)$ (14)

Figure 7: A schematic description of the proposed utility-based load shedding
approach. The figure shows both training and testing/runtime stages, and the
steps involved for both. Equations referring to specific computations in the
figure have been referenced.

Fig. 7 schematically describes the approach of building the utility function
using training data and using the function to calculate utility value for
frames at runtime.

####  IV-B6 Computing per-frame utility for composite color queries

Computing the utility of a frame for composite queries requires using the
utility function computed for the component colors.

$U_{C_{1}\lor
C_{2}}\left(f\right)=max\left(\overline{U_{C_{1}}}\left(f\right),\overline{U_{C_{2}}}\left(f\right)\right)$
(15)

$\overline{U_{C_{1}}}$ represents the utility function for color $C_{1}$
normalized over the training data, such that the maximum utility is 1.0.
Normalization of per-color utility functions allows their effective
composition. Similarly for computing the utility of a query looking for both
colors $C_{1}$ AND $C_{2}$ in a frame, we use the minimum of
$\overline{U_{C_{1}}}$ and $\overline{U_{C_{2}}}$ as the composite utility.

###  IV-C Computing Utility Threshold

The utility threshold to be used at any given point of time by the Load
Shedder is computed using the target frame drop rate that is currently
desired. This mapping is learned using the distribution of utility values for
a set of frames $\mathcal{H}$ in recent history. Using the utility function
$U_{C}$, we build a cumulative distribution function (CDF) of utility values
over frames in the history $\mathcal{H}$, as shown in equation Eq. 16.

$CDF\left(u\right)=\dfrac{|\\{f:U_{C}\left(f\right)\leq
u\,\forall\left(f,l\right)\in\mathcal{H}\\}|}{|\mathcal{H}|}$ (16)

Note that using a CDF-based approach allows incorporating utility values of
more recent frames into $\mathcal{H}$ to update the CDF with changing video
content. Initially, the training data set $\mathcal{D}$ itself can be used as
the set $\mathcal{H}$ of historical frames. To determine the utility threshold
for a given target drop rate $r$, we use the inverse of the $CDF$ function
iteratively to compute the minimum utility value $u_{th}$ such that

$CDF\left(u_{th}\right)\geq r.$ (17)

The intuition behind this approach is that for the utility threshold $u_{th}$,
the Load Shedder will drop a fraction $r$ from $\mathcal{H}$. Since the
utility distribution of recent historical frames is expected to be similar to
new frames in the near term, the Load Shedder is expected to drop $r$ fraction
of new incoming frames. However, the observed frame drop rate of new incoming
frames might not equal the target drop rate $r$ because it’s transformation to
utility threshold depends entirely on the distribution of frame utilities in
$\mathcal{H}$. Both the target drop rate and observed drop rate have a range
from 0 to 1.

###  IV-D Design of Control Loop

The utility and threshold calculation described in Section IV-A are used by a
Load Shedder to control the end-to-end (E2E) latency of the execution of a
video processing query. The Load Shedder requires a control loop (as shown in
Fig. 3) to define the target drop rate to keep the E2E latency within the
specified bound.

####  IV-D1 Control Loop mechanisms

The developer of the video query defines the required E2E latency, which
guides the execution of the Load Shedder. Besides this requirement, the Load
Shedder uses as inputs both the frames per second (FPS), the (current)
processing latency of backend query execution, and the (current) network
latency between camera and Load Shedder, and between Load Shedder and the
backend running the query. The Load Shedder uses two main mechanisms to
control the end-to-end latency: admission control and dynamic queue sizing.
These mechanisms differ primarily in how quickly they adapt the target drop
rate based on changes in backend execution load.

Admission Control. The admission control decides which frames are considered
for further processing. To do so, it monitors the execution and queuing delays
of a frame for all operators of the Application Query and thereby computes the
processing latency of each frame by the query. It uses the average perceived
query processing latency ($proc_{Q}$) to calculate the currently supported
throughput (ST) by the backend query as:

$ST=\dfrac{1}{proc_{Q}}$ (18)

The ST is then compared against the FPS (frame per second) coming into the
Load Shedder to calculate the required target drop rate as follows:

$Target~{}Drop~{}Rate=max(0,1-\dfrac{ST}{FPS}),$ (19)

which prescribes the fraction of frames that need to be dropped to match the
ingress frame rate going into the backend query with the available processing
throughput, such that the system is stable. As described in Section IV-C, we
transform the target drop rate to a utility threshold by using the utility
distribution of historical frames, to filter new ingress frames based on their
utility value.

Dynamic Queue Sizing.  Internally, the Load Shedder (as shown in Fig. 3) also
manages a queue that it uses to ensure that the the end-to-end latency of any
frame accepted by admission control is met. The expected E2E latency for the
$N^{th}$ frame in the Load Shedder queue is shown in Eq. 20. $net_{cam,LS}$
and $net_{LS,Q}$ represent the average of continuously monitored network
latencies between cameras and Load Shedder and between Load Shedder and query
backend respectively. $proc_{CAM}$ denotes the average latency incurred in
processing frames on the camera (including background subtraction, feature
extraction, etc.) (analyzed in Section V-F).

$\begin{split}Expected~{}E2E~{}Latency=(N+1)\cdot proc_{Q}+\\\
net_{cam,LS}+net_{LS,Q}+proc_{CAM}\end{split}$ (20)

If one of the component latencies increases, later frames in the Load
Shedder’s internal queue could violate the E2E latency requirement. Dynamic
queue sizing helps reduce the likelihood of a frame with a high utility
violating the query’s latency requirement.

Dynamic queue sizing updates the size of the Load Shedder’s queue and drops
the frames with the lowest utility when the size is reduced. This design
allows the frames with highest utilities to be processed instead of following
other policies (e.g., LIFO - that blindly drop older frames). Dynamic queue
sizing reacts faster than updates to the utility threshold (that guides
admission control) and reduces the likelihood of an E2E latency violation. The
queue is always at least of size one to avoid starving the downstream
operators.

Dynamic queue sizing can also be seen as a second layer of admission control.
Even if a new frame has a utility higher than the current threshold, it will
be dropped if the queue is full and it has the lowest utility of all frames
currently in the queue. Similarly, if an incoming new frame has a greater
utility than the lowest utility frame that is already in the queue, then the
latter will be dropped and the new frame added to the queue. This queue
shedding keeps the latency requirement valid even for new incoming frames.

Both mechanisms allow the Load Shedder to fine-tune the admission of new
frames to extract the most utility out of the video stream while still
maintaining the required E2E latency.

##  V Evaluations

In this section, we present the results of experimental evaluations carried
out to test the efficacy of the proposed utility-based load shedding approach.
Our experiments are tailored to validate the following hypotheses.

  1. 1.

The proposed utility function is able to compute utility value for frames from
an unseen video (not in training set) and effectively differentiate between
positive and negative frames.

  2. 2.

The proposed control loop adapts to changing workload pattern and is able to
meet application performance requirements without sacrificing QoR metric.

  3. 3.

The utility value calculation is light-weight and imposes low overhead on edge
devices.

###  V-A Data Set

We generated a benchmark of synthetic videos with VisualRoad [25], which is a
benchmark to evaluate video database management systems. VisualRoad uses the
autonomous driving CARLA simulator [26] to generate videos from CCTV cameras
located in a realistic city-like environment, including pedestrians, bicycles,
different types of vehicles, and all the surroundings (roads and buildings).
Additionally, it allows perturbing the locations of cameras (by specifying a
seed parameter) and weather conditions, thereby generating a number of
different scenarios.

We evaluate our proposed color-based Load Shedder and associated control loop
with 25 videos from 7 seeds value (3 or 4 videos from each seed value) using
sunny weather. Each video represents 15 minutes of a camera video stream
facing a road or highway in a city, with a frame rate of 10 fps. Different
cameras have different distributions of cars, varying from cars always
presents to rarely appearing. In our results, we report metrics for videos
that contained a decent number of target objects for the given query.

###  V-B Implementation

Figure 8: The components used in the evaluation setup. The Application Query
shows all the components in the considered query.

In order to evaluate the aforementioned hypotheses, we implement the video
processing system along with the Load Shedder. The system being evaluated has
three main components: the Video Streamer, the Load Shedder, and the Backend
Query executor, as shown in Fig. 8. All the components exchange messages using
the communication library ZeroMQ [27], with the messages serialized using
Cap’n Proto [28]. The Load Shedder is implemented in Python 3 and all the
other components in C++. The Video Streamer reads the video files generated
with VisualRoad, performs background subtraction, extracts the color features
for each frame (as described in Fig. 7) and streams them to the Load Shedder.
The Video Streamer component is capable of emulating multiple cameras sending
their frames’ features to the Load Shedder by interleaving their frames. Next,
the Load Shedder implements the utility calculation and load shedding
described in Section IV-A. The utility function we use in our evaluations uses
8 bins for both saturation and value, meaning that the bin sizes $s$ and $v$
are equal to 32. Through preliminary experiments (not shown in this paper) we
found that these bin sizes offer the best separation of positive from negative
frames. Finally, the Backend Query Executor runs the video analytics query to
be executed on the video stream. The Load Shedder and Backend Query Executor
run on a NC6 Virtual Machine on Microsoft Azure with 6 Intel Xeon E5-2690 v3
vCPUs, 56 GiB of RAM and an NVIDIA Tesla K80.

There are two additional components to implement the control loop: the Metrics
Collector and a Transmission Control Mechanism. The Metrics Collector measures
the end-to-end latency in the Backend Query Executor, aggregates it, and
forwards it to the Load Shedder. The Metrics Collector also monitors the total
incoming frames per second. The Load Shedder uses this information to define
the target drop rate. The Transmission Control Mechanism implements a
backpressure algorithm using tokens between the Load Shedder and the Backend
Query Executor. The latter has a queue that allows the Load Shedder to send
frames to be processed when a token is freed (i.e., when a frame processing is
completed). The tokens allow the Load Shedder to control which frames will be
processed by the Backend Query Executor when they are running in different
machines and balance the trade-off between waiting for a better frame to
arrive at the Load Shedder and sending the currently best. In addition, the
tokens give feedback to the load shedder on when to send the current best next
frame to process. If no tokens are remaining, the load shedder should keep
analyzing the incoming frames and drop frames with the lower utility if
required. On the other hand, if the Backend Query Executor is empty, the load
shedder should immediately send something to be processed.

###  V-C Video queries

Our evaluations consider object detection and tracking queries that need to
look at multiple frames of target objects. The model query we use consists of
(1) a filter component that groups together spatially adjacent pixels into
blobs and drops frames that do not have at least one blob of a certain minimum
size, (2) a second filter that ignores frames that do not have a blob(s) of
the target object’s color, (3) a DNN that performs object detection, (4) a
filter that looks for the detected objects’ color and label before sending the
information to the sink. The object detection DNN we use is efficientdet-d4
[29], which forms the most computationally intensive components of these
components and incurs a bulk of processing latency. As described earlier in
Section II-A, the end-to-end latency of a frame depends on which operators of
the query it traverses, which depends on the frame’s content. We evaluate
simple queries for target objects of a single color (e.g., red) and composite
queries for objects of multiple colors (e.g., red or yellow).

###  V-D Performance on Unseen Videos

We evaluate the performance of the Load Shedder on unseen videos using a
cross-validation study. We use the video dataset described above and
iteratively split it into training and testing set, changing the split in each
iteration. In each iteration, we build train the Load Shedder’s utility
function using the training set and compute the utility and correctness
metrics for the test videos.

####  V-D1 Single-color query: Red

(a) Utility values for positive and negative frames of unseen video frames.
For a given video in the figure, the utility function used to compute its
frames’ utility values is trained using data that does not contain the given
video.

(b) Variation of target object based QoR metric and frame drop rate with
utility threshold for a Load Shedder tuned to detect red vehicles.

Figure 9: Performance of the utility-based Load Shedder on a query looking for
Red cars as target objects.

We begin by evaluating a query looking for target objects of a single color,
which in this are red cars. Fig. 9(a) shows the utility of positive and
negative frames for the videos in our dataset. The results show that the
utility function computes significantly higher utility value for positive
frames than negative ones. This result is significant because it shows the
performance of the utility function on unseen videos.

We demonstrate how such a separation in utility values between positive and
negative frames is useful in being able to detecting target objects and
maintaining a high QoR value while also shedding a significant fraction of
(useless) frames. In Fig. 9(b), we show the variation of frame drop rate and
QoR metric with respect to utility threshold. As expected, an increasing
utility threshold results in an increase in the frame drop rate, which also
includes a small portion of useful frames containing target objects, and hence
results in a drop in the QoR metric.

(a) Impact of target drop rate on QoR rate and frame drop rate for utility-
based approach.

(b) Impact of target drop rate on QoR and frame drop rate for content-agnostic
approach.

(c) Comparison of tradeoff between QoR and frame drop rate for utility-based
and content-agnostic load shedding approaches.

Figure 10: Comparison of proposed utility-based load-shedding approach with a
content-agnostic probability-based approach (random). Fig. 10(a) and Fig.
10(b) show the impact of target drop rate on the QoR metric and observed frame
drop rate for utility-based and the content-agnostic approach respectively.
Tradeoffs between the aforementioned two metrics are shown for both approaches
in Fig. 10(c).

Comparison against Content-agnostic load shedding.  We now compare the
performance of the proposed utility-based load shedding approach against a
content-agnostic approach that sheds a fixed rate of incoming frames using a
uniform probability. Firstly, Fig. 10(a) shows the variation of frame drop
rate and the associated fraction of objects detected against the target drop
rate of the Load Shedder. As we have seen in Fig. 9(a), there is a significant
portion of negative frames that have a low utility. Hence, a low target drop
rate results in the selection of a utility threshold that drops many more
frames than the target drop rate. However, since those frames are low-utility
ones, the QoR remains at 1.0 until the target drop rate becomes so high that
higher-utility frames (containing target objects) need to be dropped. That is
when the QoR metric dips. Next, Fig. 10(b) shows the variation of observed
frame drop rate and QoR against target drop rate for the Content-agnostic
shedding approach. Since the shedding is based on a uniform random probability
distribution, we repeat each setting 20 times. Even though the observed frame
drop rate is roughly equal to the target drop rate, the QoR falls sharply
because content-agnostic shedding often sheds frames containing target
objects. Finally, Fig. 10(c) compares the QoR that the proposed load shedding
approach can achieve for a given observed frame drop rate with the content-
agnostic shedding approach. Although the QoR of the content-agnostic approach
continuously falls with increasing drop rate, the QoR for utility-based
approach has a visible drop only when the observed frame drop rate gets close
to 1.0. The result shows that the utility-based approach is highly selective
in picking frames to send to Backend Query Executor, and one can achieve a
much higher QoR with it for a given observed frame drop rate compared to a
content-agnostic shedding approach.

####  V-D2 Composite-color query: Red OR Yellow

(a) Utility values for positive and negative frames of unseen video frames.
For a given video in the figure, the utility function used to compute its
frames’ utility values is trained using data that does not contain the given
video.

(b) Variation of target object detection rate and frame drop rate with utility
threshold for a Load Shedder tuned to detect red or yellow cars.

Figure 11: Performance of utility-based Load Shedder on query looking for Red
OR Yellow cars as target objects. Figure 12: Utility values for positive and
negative frames of unseen video frames. The given query is looking for frames
containing both Red and Yellow cars.

We perform a similar analysis for a composite queries - those that are tasked
with (1) detecting target objects that are either Red or Yellow in color (we
refer to this as the OR query), and (2) detecting all frames containing both
Red and Yellow target objects (we refer to this as the AND query). As before,
we iteratively select a set of videos as the training set and the
complementary set as the test set.

The utility value of frames for the OR query is shown in Fig. 11(a). Similar
to the results for the single-color query, the utility value of positive
frames is significantly higher than that of negative frames. Note that for the
composite OR query, a positive frame is one that contains either a Red or
Yellow target car. Fig. 11(b) shows the frame drop rate and QoR metric against
the utility threshold. The QoR remains stagnant at 1.0 (selecting all frames
containing target objects) with a high frame drop rate, until the utility
threshold becomes high enough to start dropping positive frames. Fig. 12 shows
the utility value of frames for the AND query, and the differentiation between
positive and negative frames is visible here as well. Note that for the
composite AND query, a positive frame is one that contains both a Red or
Yellow car.

###  V-E Application Evaluations

The microbenchmarks evaluated the soundness of our utility calculation and
compared it against a content-agnostic approach. In this subsection, we detail
an E2E evaluation of running both the utility calculation and the Load Shedder
control loop using a real-time video stream and show how it can timely control
the latency of frame processing and avoid overloading the backend.

####  V-E1 Synthetic scenario

First, we evaluate a synthetic worst-case scenario in which a sudden burst of
high-processing activity occurs in the ingress video. The video comprises
three segments: one low-utility frames with no target object, high-utility
frames containing target object(s), and high-utility frames with no target
object. To create such a tailored video, we obtain segments from the videos
generated with Visual Road that are known a-priori to have those properties,
and stitch them together to form a 15 minutes long video with each of the
above three segments being 5 minutes long.

The expectation in this experiment is that during the video’s first low-
utility no-object segment, the Load Shedder will allow frames to be processed
by the filter-stage in the backend query, even when the frame utility is low.
This is because the the filter operator would drop these frames as they don’t
contain large blobs of the specific color that the query is looking for
(because there are no target objects). Hence, the processing latency
$proc_{Q}$ is low, leading to the throughput that can be handled by the
backend higher than the incoming frame rate (Eq. 18), and thereby a low target
drop rate (Eq. 19). Next, in the second segment of the video, the Load Shedder
will start shedding frames because all frames would be processed by the
expensive DNN as they contain target objects. Thus, the Load Shedder increases
the utility threshold so that the backend query executor can keep the end-to-
end latency latency bounded for the frames that are processed. Finally, in the
third segment with no target objects, the Load Shedder would stop shedding
again and have an execution profile similar to the first segment.

(a) Synthetic Scenario each segments highlighted

(b) Realistic Scenario

Figure 13: Analysis of both a synthetic and a realistic scenario. The upper
graph of both figures shows in the y-axis the average processing latency
grouped in five-second intervals, with the x-axis being the time in the video,
highlighting the end-to-end latency requirement. The lower graph shows a
breakdown of the number of frames that reached each query component (from Fig.
8); it shares the x-axis with the upper graph and uses the same five-second
time intervals.

Fig. 13(a) shows the time-varying behavior of the query execution. The x-axis
shows time, the y-axis in upper graph of Fig. 13(a) shows the max end-to-end
latency in milliseconds for each 5 minutes time window, along with with the
end-to-end latency requirement. The lower graph in Fig. 13(a) shows the number
of frames processed at each stage group every 5 seconds. The upper graph in
Fig. 13(a) shows how the latency is always less than the required end-to-end
latency. Similarly, the lower graph in Fig. 13(a) portrays how the Load
Shedder decides the frame drop rate at each segment, with no shedding required
in the first and third segment and plenty of shedding in the high-processing
segment. Both these results match our expectations, and go on to show that the
proposed Load Shedder can almost instantly react to changes and have a low
number of violations even with extreme changes, that too for real-time video
processing, where the input has usual a frame rate of 24 fps or less. There
was only 1 latency violation during the peak in the second segment, while the
Load Shedder was recalculating the queue size and the utility threshold.

####  V-E2 Realistic smart-city scenario

Figure 14: Comparison of per-object QoR metric of the proposed utility-based
load shedding approach against a content-agnostic approach with fixed frame
drop rate. The number of concurrent video streams fed into the Load Shedder is
the control variable along the x-axis.

The previous sub-section analyzed the worst-case scenario for the Load
Shedder. This sub-section analyzes the Load Shedder running directly on a
subset of the videos generated using Visual Road. The Video Streamer generates
a stream of frame features interleaved from multiple videos, thereby emulating
the Load Shedder receiving frames from multiple cameras. We show the end-to-
end latency and the distribution of frames processed at each stage, along with
the variation the QoR metric with an increasing number of concurrent video
streams.

Similarly to Fig. 13(a), Fig. 13(b) shows that the Load Shedder can keep the
processing latency bounded by shedding some of the frames. There are more
spikes than in the synthetic scenario because the DNN is invoked unpredictably
by frames from different videos at different time periods. The Load Shedder is
effective in minimizing the latency violations caused due to these sudden
surges in load. Fig. 13(b) shows the latency and elements being processed for
five concurrent videos. Additionally, Fig. 14 shows that the proposed utility-
based load shedding approach can exploit the statistical multiplexing between
multiple cameras’ video streams and achieve a high QoR. On the other hand, a
content-agnostic approach (that sheds frames with uniform probability) has
poor QoR. We compute the target drop ratio for the latter approach using Eq.
18 and assuming that $proc_{Q}$ is 500 ms, which is a rather lenient
assumption for the baseline.

###  V-F Runtime Overhead Analysis

We evaluate the additional latency incurred by a video analytics system that
includes the proposed load shedding approach as compared to executing the
backend query without load shedding. We assume that cameras have colocated
compute capability on them, which they use to do three tasks: (1) converting
the color space of the source video stream from RGB to HSV, (2) subtracting
the background from the frame to extract the foreground, and (3) extracting
color features from the foreground which serves as the input to the Load
Shedder. We evaluate the time taken to perform these tasks on a Nvidia Jetson
TX1 with a quad-core ARM Cortex-A57 processor and 4 GB of RAM, which we use to
represent the typical co-located compute power with cameras. We use a video
stream with continuously high activity to stress test the above operations and
obtain worst-case delay numbers. Fig. 15 shows the median latency incurred by
each of the component tasks.

Figure 15: Breakdown of the additional latency incurred by the proposed load
shedding approach. All reported values are median latencies. The utility
calculation component is not shown here because its latency was negligible
compared to the other components.

The overall additional latency remains below 35 ms which can support the video
streams of multiple cameras operating at 10 frames per second (and even higher
rates like the common 24 fps). With composite queries needing features
calculated for multiple colors, the feature extraction portion of the overhead
would be multiplied by the number of colors considered, while the other
components’ latencies would not change (as they are computed once per frame).

##  VI Discussion

Automatic selection of Hue ranges for a query. The proposed load shedding
approach requires minimal intervention of the application query developer,
except having to provide the Hue range for the target objects. This task can
also be automated by the analysis of bounding boxes of target objects
available in the training data. Techniques such as dominant color detection
[30] can be used to automatically extract the Hue ranges in target objects and
fed into the utility calculation function.

Feature calculation vs utility calculation on camera. We could further improve
the efficiency of the network by pushing the utility calculation itself to the
camera. This decision will incur a tradeoff between the overhead of
maintaining a distributed utility model versus a higher communication cost of
sending all frames than those with a high utility value. When the cameras can
calculate the utility, the load shedder can let them know what utility
threshold to use to reduce unnecessary frames sent. However, when the model is
updated due to either new data available or drift from the previous model, it
needs to be updated at each camera, incurring additional bandwidth
requirements. Therefore, this decision should be taken considering the
connectivity scenario of the camera network.

##  VII Conclusion

In this paper we have shown how a low-cost Load Sheddercan be built for real-
time video processing on edge devices. The goal of the proposed Load Shedder
is to shed frames such that the end-to-end processing latency of each video
frame is under the latency bound for the query, while maximizing the quality
of result (QoR). The Load Shedder uses color features of ingress video frames
to compute a utility value, that denotes how likely a given frame is to
contain a target object of the query at hand. We show how the proposed utility
function is able to differentiate between video frames that do contain target
objects from frames that don’t. We propose a utility threshold based approach
for the Load Shedder to enforce a target rate of dropping frames. The Load
Shedder also consists of a control-loop component that continuously monitors
the execution of frames and detects overload in the backend query. In the case
of overload, it adjusts the target frame drop rate, which in turn sets a new
utility threshold for frames to be compared against.

Through our evaluations we have shown that the proposed Load Shedder is able
to differentiate between frames containing target objects from those that
don’t. It is able to attain a high frame drop rate, wherein it drops as many
”useless” frames as possible - thereby maintaining a high QoR metric. We show
this result for queries looking for target objects of a single-color as well
as composite queries looking for target objects of two possible colors. We
show that the proposed Load Shedder is able to adjust the utility threshold
dynamically according to the observed load on the backend query to meet the
end-to-end latency constraint. Finally, we show that the overhead of executing
the operations of the load shedding approach is not significant on edge
devices.

## References

  * [1] Z. Xu, S. Sinha, S. Harshil S, and U. Ramachandran, “Space-time vehicle tracking at the edge of the network,” in _Proceedings of the 2019 Workshop on Hot Topics in Video Analytics and Intelligent Edges_. Los Cabos, Mexico: ACM, 2019, pp. 15–20.
  * [2] T. T. Le, S. T. Tran, S. Mita, and T. D. Nguyen, “Real time traffic sign detection using color and shape-based features,” in _Asian Conference on Intelligent Information and Database Systems_. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010, pp. 268–278.
  * [3] Wobot.ai. (2021) Team Wobot how is video analytics driving industry 4.0. Wobot Intelligence. [Online]. Available: https://wobot.ai/video-analytics/how-is-video-analytics-driving-industry-4-0/
  * [4] G. Ananthanarayanan, P. Bahl, P. Bodík, K. Chintalapudi, M. Philipose, L. Ravindranath, and S. Sinha, “Real-time video analytics: The killer app for edge computing,” _computer_ , vol. 50, no. 10, pp. 58–67, 2017.
  * [5] U. Ramachandran, H. Gupta, A. Hall, E. Saurez, and Z. Xu, “A case for elevating the edge to be a peer of the cloud,” _GetMobile: Mobile Computing and Communications_ , vol. 24, no. 3, pp. 14–19, 2021.
  * [6] M. Zhang, F. Wang, Y. Zhu, J. Liu, and Z. Wang, “Towards cloud-edge collaborative online video analytics with fine-grained serverless pipelines,” in _Proceedings of the 12th ACM Multimedia Systems Conference_. Istanbul, Turkey: ACM, 2021, pp. 80–93.
  * [7] N. Tatbul and S. Zdonik, “Window-aware load shedding for aggregation queries over data streams,” in _Proc. of the 32nd Int. Conf. on Very Large Data Bases_ , 2006.
  * [8] N. Tatbul, U. Çetintemel, S. Zdonik, M. Cherniack, and M. Stonebraker, “Load shedding in a data stream manager,” in _Proc. of the 29th Int. Conf. on Very Large Data Bases_ , 2003.
  * [9] A. Slo, S. Bhowmik, and K. Rothermel, “espice: Probabilistic load shedding from input event streams in complex event processing,” in _Proceedings of the 20th International Middleware Conference_ , ser. Middleware ’19. ACM, 2019.
  * [10] A. Slo, S. Bhowmik, A. Flaig, and K. Rothermel, “pspice: partial match shedding for complex event processing,” in _2019 IEEE International Conference on Big Data (Big Data)_. IEEE, 2019, pp. 372–382.
  * [11] B. Zhao, N. Q. V. Hung, and M. Weidlich, “Load shedding for complex event processing: Input-based and state-based techniques,” in _2020 IEEE 36th International Conference on Data Engineering (ICDE)_. IEEE, 2020, pp. 1093–1104.
  * [12] C. Canel, T. Kim, G. Zhou, C. Li, H. Lim, D. G. Andersen, M. Kaminsky, and S. R. Dulloor, “Scaling video analytics on constrained edge nodes,” _CoRR_ , vol. abs/1905.13536, 2019. [Online]. Available: http://arxiv.org/abs/1905.13536
  * [13] C. Zhang, Q. Cao, H. Jiang, W. Zhang, J. Li, and J. Yao, “A fast filtering mechanism to improve efficiency of large-scale video analytics,” _IEEE Transactions on Computers_ , vol. 69, no. 6, pp. 914–928, 2020.
  * [14] Y. Li, A. Padmanabhan, P. Zhao, Y. Wang, G. H. Xu, and R. Netravali, “Reducto: On-camera filtering for resource-efficient real-time video analytics,” in _Proceedings of the Annual conference of the ACM Special Interest Group on Data Communication on the applications, technologies, architectures, and protocols for computer communication_. Virtual: ACM, 2020, pp. 359–376.
  * [15] U. K. Pillai and D. Valles, “Vehicle type and color classification and detection for amber and silver alert emergencies using machine learning,” in _2020 IEEE International IOT, Electronics and Mechatronics Conference (IEMTRONICS)_. IEEE, 2020, pp. 1–5.
  * [16] S. Roy and M. S. Rahman, “Emergency vehicle detection on heavy traffic road from cctv footage using deep convolutional neural network,” in _2019 International Conference on Electrical, Computer and Communication Engineering (ECCE)_. IEEE, 2019, pp. 1–6.
  * [17] L. A. Varga, B. Kiefer, M. Messmer, and A. Zell, “Seadronessee: A maritime benchmark for detecting humans in open water,” in _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , 2022, pp. 2260–2270.
  * [18] H. Zhang, G. Ananthanarayanan, P. Bodik, M. Philipose, P. Bahl, and M. J. Freedman, “Live video analytics at scale with approximation and delay-tolerance,” in _14th $\\{$USENIX$\\}$ Symposium on Networked Systems Design and Implementation ($\\{$NSDI$\\}$ 17)_. Boston, MA: USENIX, 2017, pp. 377–392.
  * [19] J. Jiang, G. Ananthanarayanan, P. Bodik, S. Sen, and I. Stoica, “Chameleon: scalable adaptation of video analytics,” in _Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication_. Budapest, Hungary: ACM, 2018, pp. 253–266.
  * [20] K. Wu, Y. Jin, W. Miao, Z. Zeng, Z. Qian, J. Wang, M. Zhou, and T. Cao, “Soudain: Online adaptive profile configuration for real-time video analytics,” in _2021 IEEE/ACM 29th International Symposium on Quality of Service (IWQOS)_ , IEEE. Virtual: IEEE/ACM, 2021, pp. 1–10.
  * [21] S. Naderiparizi, P. Zhang, M. Philipose, B. Priyantha, J. Liu, and D. Ganesan, “Glimpse: A programmable early-discard camera architecture for continuous mobile vision,” in _Proceedings of the 15th Annual International Conference on Mobile Systems, Applications, and Services_. Niagara Falls, NY: ACM, 2017, pp. 292–305.
  * [22] C. Zhang, Q. Cao, H. Jiang, W. Zhang, J. Li, and J. Yao, “A fast filtering mechanism to improve efficiency of large-scale video analytics,” _IEEE Transactions on Computers_ , vol. 69, no. 6, pp. 914–928, 2020.
  * [23] J. Wang, Z. Feng, Z. Chen, S. George, M. Bala, P. Pillai, S.-W. Yang, and M. Satyanarayanan, “Bandwidth-efficient live video analytics for drones via edge computing,” in _2018 IEEE/ACM Symposium on Edge Computing (SEC)_ , IEEE. Bellevue, WA: IEEE/ACM, 2018, pp. 159–173.
  * [24] HSL and HSV, “Hsv cylinder,” https://en.wikipedia.org/wiki/HSL_and_HSV#/media/File:HSV_color_solid_cylinder_saturation_gray.png, 2010, [Online; accessed 2022-01-14].
  * [25] B. Haynes, A. Mazumdar, M. Balazinska, L. Ceze, and A. Cheung, “Visual road: A video data management benchmark,” in _SIGMOD_. Amsterdam, NL: ACM, 2019, pp. 972–987.
  * [26] A. Dosovitskiy, G. Ros, F. Codevilla, A. Lopez, and V. Koltun, “CARLA: An open urban driving simulator,” in _Conference on robot learning_. Mountain View, CA: PMLR, 2017, pp. 1–16.
  * [27] ZeroMQ, “Zeromq,” https://zeromq.org/, 2022, [Online; accessed 2022-01-14].
  * [28] Cap’n Proto, “Cap’n proto: Serialization protocol,” https://capnproto.org/, 2022, [Online; accessed 2022-01-14].
  * [29] M. Tan, R. Pang, and Q. V. Le, “Efficientdet: Scalable and efficient object detection,” in _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , 2020, pp. 10 781–10 790.
  * [30] PyPi, “Dominant color detection,” https://pypi.org/project/dominant-color-detection/, 2020, [Online; accessed 2022-01-31].