# PGD-VIO: An Accurate Plane-Aided Visual-Inertial Odometry with Graph-Based
Drift Suppression

Yidi Zhang1,2, Fulin Tang2∗, Zewen Xu2, Yihong Wu2,1∗ and Pengju Ma3 ∗This
work was supported by the National Natural Science Foundation of China under
Grant No. 62202468 and a SINOPEC Research Project. The corresponding authors
are Fulin Tang and Yihong Wu. E-mail: {fulin.tang<EMAIL_ADDRESS>of
Artificial Intelligence, University of Chinese Academy of Sciences, Beijing,
China.2State Key Laboratory of Multimodal Artificial Intelligence Systems,
Institute of Automation, Chinese Academy of Science, Beijing, China.3Sinopec
Shengli Oilfield, Shandong, China.

###### Abstract

Generally, high-level features provide more geometrical information compared
to point features, which can be exploited to further constrain motions. Planes
are commonplace in man-made environments, offering an active means to reduce
drift, due to their extensive spatial and temporal observability. To make full
use of planar information, we propose a novel visual-inertial odometry (VIO)
using an RGB-D camera and an inertial measurement unit (IMU), effectively
integrating point and plane features in an extended Kalman filter (EKF)
framework. Depth information of point features is leveraged to improve the
accuracy of point triangulation, while plane features serve as direct
observations added into the state vector. Notably, to benefit long-term
navigation, a novel graph-based drift detection strategy is proposed to search
overlapping and identical structures in the plane map so that the cumulative
drift is suppressed subsequently. The experimental results on two public
datasets demonstrate that our system outperforms state-of-the-art methods in
localization accuracy and meanwhile generates a compact and consistent plane
map, free of expensive global bundle adjustment and loop closing techniques.

##  I INTRODUCTION

Visual-inertial odometry (VIO) and simultaneous localization and mapping
(SLAM) are key problems in the field of mobile robotics [23]. Most existing
VIO/SLAM systems rely on sparse point features for the sake of efficiency and
robustness [8, 1]. RGB-D cameras simplify the tasks of triangulating point
features and extracting high-level features. Compared with point features,
plane features can provide complementary information to boost the performance,
especially when points degenerate in challenging scenes [4]. Moreover, plane
features exist prevalently in man-made environments and are more interpretable
and usable in providing a structural representation. Therefore, combining
point and plane features has been investigated in many studies [24].

Figure 1: Illustration of the proposed PGD-VIO on the CID-SIMS sequence
Floor3_1. Attributed to the drift suppression strategy, the system can detect
overlapping and identical configurations in the plane map and align them to
cope with cumulative errors, resulting in an accurate trajectory and a more
consistent plane map.

One of the critical problems for investigating planes as landmarks in RGB-D
VIO/SLAM systems is the data association. Different from point features that
are tracked on 2D images, planes are typically associated according to their
parameters in a unified coordinate system. Broadly, two planes are considered
as a matching pair when their angle and separation are within the defined
thresholds. In some researches, planar covariance and the Mahalanobis distance
are also employed [24]. As these ideas firmly depend on initial poses, planes
cannot be associated successfully once drift occurs, thus submerging their
value in providing long-term constraints. To tackle this issue and fully
exploit the longstanding planes, we propose a novel plane-aided RGB-D VIO
system with a graph-based drift suppression strategy. The key idea is to
understand the structural regularity of a given scene and perform drift
detection by identifying duplicate planar structures in the map. In other
words, if a set of planes overlaps another to some extent and their spatial
configurations are similar, the map becomes inconsistent, indicating potential
drift. Once drift is detected, we attempt to suppress it and correct the poses
accordingly. As shown in Fig. 1, our system can cope with large drift and
robustly associate repetitive planes to improve the localization performance
as well as the map consistency in a corridor environment. The main
contributions of this work are summarized as follows:

  * •

We construct an RGB-D VIO system, called PGD-VIO, within an extended Kalman
filter (EKF) framework and derive how to update the state properly using plane
and point features.

  * •

We present a novel graph-based strategy for drift detection using planar
structures. Then, cumulative errors are suppressed through a de-drift update.
By investigating similarities between plane patches, our method can detect
repetitive structures in the global map and correct their drift, thereby
better constraining the motions.

  * •

We validate the proposed system extensively on two public datasets,
demonstrating that our system performs well in localization and builds a
consistent plane map by fusing depth and planar properties.

Figure 2: Overview of the proposed PGD-VIO system.

##  II RELATED WORK

Nowadays, several methods have combined RGB-D and inertial measurements for
navigation [1, 22, 3]. Planes are predominant primitives in man-made
environments, which contain prolific geometrical information and structural
regularities for gaining in improvement. As their parameters can be computed
from RGB-D cameras [11, 24] or 3D LiDARs [9], multiple researchers leverage
planes as direct observations. Additionally, some studies enforce dependencies
on coplanar regularities. [24] introduces plane measurements adopting closest
point (CP) for parameterization and distinguishes planar point features from
non-planar point features to permit point-on-plane constraints. VIP-SLAM [3]
exploits point-to-plane and homography constraints in a tightly coupled
system, which significantly reduces the complexity of bundle adjustment. [2]
is a monocular VIO system regularized by point-on-plane constraints within a
lightweight multi-state constraint Kalman filter (MSCKF).

Recently, cross-plane constraints have received attention to support camera
pose estimation in structured environments. For example, DPI-SLAM [11] forces
orthogonality and parallelism constraints on nearby planes in global graph
optimization. Besides, some approaches have been developed in conjunction with
Manhattan world (MW) [16] or Atlanta world [15] assumption. By recognizing the
dominant directions of frames and estimating drift-free rotations followed by
the translation-only BA, rotations and translations are decoupled in [17].
Based on the understanding of environmental assumptions, [14] detects planes
that are aligned with the dominant directions to estimate drift-free rotations
and update translations and 1D representations of the structure-aware planes
in a linear EKF framework.

In light of these attempts, geometric structures are taken into account for
plane association. [7] constructs graphs using plane patches and relies on an
interpretation tree to search matches for real-time place recognition. Such
correspondences with prior maps help with error correction for VIO/SLAM
systems. LiPMatch [13] detects loop closures by evaluating plane similarities
of two keyframes with a graph matching method in a LiDAR SLAM. Combining
objects and planes, [5] generates a semantic topological graph, in which node
descriptors are extracted based on the graph propagation theory. Then, a
relocalization system is developed for pose optimization. Moreover, [21]
proposes a novel graph-to-graph matching method to relate SLAM maps with
architectural plans and achieve global robot localization. Similarly, PPM-VIO
[12] is a filter-based VIO system that exploits a prior point-plane map to
correct drift in the local pose estimates.

Inspired by the above researches, to further exploit the structure of planes,
we propose a novel RGB-D VIO system, incorporating point and plane
measurements, along with a graph-based drift suppression strategy, which can
significantly improve performance in long-term navigation. As distinct from
those relying on prior maps to optimize poses, our method detects drift from
the incremental plane map and updates the system state in a filtering
framework.

##  III PROPOSED SYSTEM

Built upon the EKF framework, our system incorporates depth information into
point features and utilizes plane measurements in the EKF update with camera-
IMU calibration. Moreover, to further exploit the structure of scenes, we
investigate a graph-based method to detect drift from the global plane map and
suppress the errors in long-term localization. Fig. 2 shows the overview of
the proposed system. PGD-VIO contains four procedures: IMU integration and
propagation (Sec. III-B), feature detection and association (Sec. III-C), EKF
state update (Sec. III-D and III-E), and drift suppression (Sec. III-F). Given
an input RGB-D and inertial sequence, we first apply IMU measurements to
propagate the system state and the covariance. Then, we detect and associate
both points and planes in parallel and update them during the EKF update
process. If needed, drift is detected based on a novel graph matching strategy
and suppressed with a de-drift update. After that, small and short-tracked
planes are delayed marginalized when they are lost for a period of time.

###  III-A State Vector

At time $t_{k}$, the system state is defined as follows:

$\mathbf{x}_{k}=\begin{bmatrix}\mathbf{x}_{I_{k}}^{\mathsf{T}}&\mathbf{x}_{calib}^{\mathsf{T}}&\mathbf{x}_{C}^{\mathsf{T}}&\mathbf{x}_{P}^{\mathsf{T}}&\mathbf{x}_{\Pi}^{\mathsf{T}}\end{bmatrix}^{\mathsf{T}}$
(1)
$\mathbf{x}_{I_{k}}=\begin{bmatrix}{}^{I_{k}}_{G}\bar{\mathbf{q}}^{\mathsf{T}}&{}^{G}{\mathbf{p}}_{I_{k}}^{\mathsf{T}}&{}^{G}{\mathbf{v}}_{I_{k}}^{\mathsf{T}}&{}^{I_{k}}{\mathbf{b}}_{g}^{\mathsf{T}}&{}^{I_{k}}{\mathbf{b}}_{a}^{\mathsf{T}}\end{bmatrix}^{\mathsf{T}}$
(2)
$\mathbf{x}_{calib}=\begin{bmatrix}{}^{C}_{I}\bar{\mathbf{q}}^{\mathsf{T}}&{}^{C}{\mathbf{p}}_{I}^{\mathsf{T}}&{}_{I}^{C}t&\mathbf{\lambda}_{C}^{\mathsf{T}}\end{bmatrix}^{\mathsf{T}}$
(3)
$\mathbf{x}_{C}=\begin{bmatrix}{}^{I_{k}}_{G}\bar{\mathbf{q}}^{\mathsf{T}}&{}^{G}\mathbf{p}_{I_{k}}^{\mathsf{T}}&...&{}^{I_{k-c}}_{G}\bar{\mathbf{q}}^{\mathsf{T}}&{}^{G}\mathbf{p}_{I_{k-c}}^{\mathsf{T}}\end{bmatrix}^{\mathsf{T}}$
(4) $\mathbf{x}_{P}=\begin{bmatrix}{}^{G}\mathbf{f}_{1}^{\mathsf{T}}\ ...\
^{G}\mathbf{f}_{h}^{\mathsf{T}}\end{bmatrix}^{\mathsf{T}},\
\mathbf{x}_{\Pi}=\begin{bmatrix}{}^{G}\mathbf{\Pi}_{1}^{\mathsf{T}}\ ...\
^{G}\mathbf{\Pi}_{n}^{\mathsf{T}}\end{bmatrix}^{\mathsf{T}}.$ (5)

For current IMU state $\mathbf{x}_{I_{k}}$ and historical IMU pose clones
$\mathbf{x}_{C}$, ${}^{I}_{G}\bar{\mathbf{q}}$ is the unit quaternion
representing the rotation from the global frame $\\{G\\}$ to the IMU frame
$\\{I\\}$, ${}^{G}{\mathbf{p}}_{I}$ and ${}^{G}{\mathbf{v}}_{I}$ are the
position and velocity of IMU with respect to $\\{G\\}$, and
${}^{I}{\mathbf{b}}_{g}$ and ${}^{I}{\mathbf{b}}_{a}$ are the gyroscope and
accelerometer biases, respectively. $\mathbf{x}_{calib}$ is calibration
parameters consisting of camera-IMU rigid transformation
$\\{{}^{C}_{I}\bar{\mathbf{q}},\ {}^{C}{\mathbf{p}}_{I}\\}$, time offset
${}^{C}_{I}t$ and camera intrinsic parameters $\mathbf{\lambda}_{C}$.
$\mathbf{x}_{P}$ and $\mathbf{x}_{\Pi}$ are point and plane features in
$\\{G\\}$. To simplify subsequent expressions, we clarify that throughout the
paper, ${}_{A}^{B}\mathbf{R}$ is the rotation matrix from frame $\\{A\\}$ to
frame $\\{B\\}$ and ${}^{B}\mathbf{p}_{A}$ is the position of frame $\\{A\\}$
in frame $\\{B\\}$.

###  III-B IMU Propagation

The system state evolves from time $t_{k}$ to $t_{k+1}$ through IMU
integration and forward propagation. Details about the generic nonlinear IMU
kinematics and the evolution process can be found in [18, 8].

###  III-C Feature Detection and Association

In our case, FAST corners are extracted on color images as keypoints and
sparse KLT optical flow is employed to track them between frames. Meanwhile,
planes are detected from depth maps using agglomerative hierarchical
clustering (AHC) algorithm [6] and then associated with map planes by
comparing their distances and normal vector angles in {G}.

###  III-D Point Feature Update

In the first step we need to obtain initial 3D position estimations of points.
To this end, we take all the camera poses provided by the IMU propagation to
be of known quantity and fuse depth information into the 3D Cartesian
Triangulation. In particular, when a point ${}^{G}\mathbf{f}_{i}$ is observed
by a camera $C_{m}$, we have an observation

$\displaystyle{}^{C_{m}}\mathbf{f}_{i}={}^{C_{m}}{z_{f}}{}^{C_{m}}\mathbf{b}_{f},$
(6)

where ${}^{C_{m}}{z_{f}}$ represents the depth of this point from the image
plane and ${}^{C_{m}}\mathbf{b}_{f}$ is the bearing vector. With the knowledge
of ${}^{C_{m}}{z_{f}}$, we can directly transform the 3D observation
${}^{C_{m}}{\mathbf{f}}_{i}$ to $\\{G\\}$ via

$\displaystyle{}^{G}\mathbf{f}_{i}$
$\displaystyle={}^{C_{m}}_{G}\mathbf{R}^{\mathsf{T}}{}^{C_{m}}{\mathbf{f}}_{i}+{}^{G}\mathbf{p}_{C_{m}}.$
(7)

Otherwise, if ${}^{C_{m}}{z_{f}}$ is not available due to noise or exceeding
the range, ${}^{G}\mathbf{f}_{i}$ can be written as

$\displaystyle{}^{G}\mathbf{f}_{i}$
$\displaystyle={}^{C_{m}}{z_{f}}^{G}\mathbf{b}_{f}+{}^{G}\mathbf{p}_{C_{m}}.$
(8)

By defining vectors orthogonal to ${}^{G}\mathbf{b}_{f}$ in $\mathbf{N}_{m}$
($\mathbf{N}_{m}{}^{G}\mathbf{b}_{f}=\mathbf{0}_{3\times 3}$) and substituting
it to (8), we can obtain:

$\displaystyle\mathbf{N}_{m}{}^{G}\mathbf{f}_{i}$
$\displaystyle=\mathbf{N}_{m}{}^{G}\mathbf{p}_{C_{m}}.$ (9)

After stacking all the hybrid points:

$\displaystyle\underbrace{\begin{bmatrix}\vdots\\\ \mathbf{N}_{m_{1}}\\\
\vdots\\\ \mathbf{I}_{3\times 3}\\\
\vdots\end{bmatrix}}_{\mathbf{A}}{}^{G}\mathbf{f}_{i}$
$\displaystyle=\underbrace{\begin{bmatrix}\vdots\\\
\mathbf{N}_{m_{1}}{}^{G}\mathbf{p}_{C_{m_{1}}}\\\ \vdots\\\
{}^{C_{m_{2}}}_{G}\mathbf{R}^{\mathsf{T}}{{}^{C_{m_{2}}}\mathbf{f}_{i}}+{}^{G}\mathbf{p}_{C_{m_{2}}}\\\
\vdots\end{bmatrix}}_{\mathbf{b}},$ (10)

the position ${}^{G}\mathbf{f}_{i}$ can be calculated by solving the linear
system
$\mathbf{A}^{\top}\mathbf{A}~{}{}^{G}\mathbf{f}_{i}=\mathbf{A}^{\top}\mathbf{b}$.

Then, a point feature ${}^{G}\mathbf{f}_{i}$ is updated using the following
measurement function:

$\displaystyle\mathbf{z}_{b}=h(\mathbf{x}_{k})+\mathbf{n}_{b},$ (11)

where $h(\cdot)$ projects ${}^{G}\mathbf{f}_{i}$ onto an observed image
$C_{m}$ with the state $\mathbf{x}_{T_{m}}$, including the observing pose
$\mathbf{x}_{C_{m}}$ and the calibration parameters $\mathbf{x}_{calib}$, and
$\mathbf{n}_{b}\sim\mathcal{N}(\mathbf{0}_{2\times 2},\mathbf{I}_{2\times 2})$
denotes the measurement noise.

Linearizing the equations yields the following system:

$\tilde{\mathbf{z}}_{b}=\mathbf{H}_{T_{b}}\tilde{\mathbf{x}}_{T_{m}}+\mathbf{H}_{f_{b}}{}^{G}\tilde{\mathbf{f}}_{i}+\mathbf{n}_{b},$
(12)

where $\tilde{\mathbf{z}}_{b}$ is the projected 2D residual, $\mathbf{n}_{b}$
is the white Gaussian noises, $\mathbf{H}_{T_{b}}$ and $\mathbf{H}_{f_{b}}$
are the measurement Jacobians in respect to the current state
$\mathbf{x}_{T_{m}}$ and the 3D point feature ${}^{G}\mathbf{f}_{i}$,
respectively.

After stacking all the measurements from different timesteps, we perform an
EKF update for point features, which are divided into SLAM features and MSCKF
features based on their track lengths. Since only SLAM features are in the
state vector, SLAM points are updated using standard EKF while feature
dependency will be removed from (12) through nullspace projection for MSCKF
points. For more details please refer to [8].

Figure 3: Distinctive relative positions of two plane patches, viewed from a
common perpendicular direction to their normal vectors. In each figure, the
yellow dot is the closest point on plane $i$ to plane $j$ and the
corresponding line depicts the distance $d_{ij}$, the blue dot and the blue
line measure the distance $d_{ji}$ from plane $j$ to plane $i$ oppositely, and
the green line marks their overlapping region, which is negative implying the
parallel distance in (d) and (f).

###  III-E Plane Feature Update

Observations of environmental planes can be obtained directly from depth
images provided by the RGB-D camera. Here, closet point (CP) [9] is adopted to
represent a plane feature:

$\displaystyle{}^{G}\mathbf{\Pi}={}^{G}\mathbf{n}{}^{G}d,\
\begin{bmatrix}{}^{G}\mathbf{n}\\\
{}^{G}d\end{bmatrix}=\begin{bmatrix}{}^{G}\mathbf{\Pi}/||{}^{G}\mathbf{\Pi}||\\\
||{}^{G}\mathbf{\Pi}||\end{bmatrix},$ (13)

where ${}^{G}\mathbf{n}$ and ${}^{G}d$ are the unit normal vector and the
distance scalar of the plane, respectively. To fit a plane, we minimize point-
to-plane distances by solving a maximum likelihood estimation (MLE) problem
with RANSAC on the basic of AHC [6]. Once a plane ${}^{C}\mathbf{\Pi}$ is
observed by a camera $C_{m}$, we recover the initial guess for it. Afterwards,
a plane feature ${}^{G}\mathbf{\Pi}$ can be updated using the following
measurement function:

$\displaystyle{}^{C_{m}}\mathbf{\Pi}=$
$\displaystyle({}_{G}^{C_{m}}\mathbf{R}{}^{G}\mathbf{n})({}^{G}d-{}^{G}\mathbf{p}_{C_{m}}^{\mathsf{T}}{}^{G}\mathbf{n})+\mathbf{n}_{m},$
(14)

where $\mathbf{n}_{m}$ is the plane measurement noise, whose covariance is
given by [24]. We linearize this equation and obtain the following residual
and Jacabians:

$\displaystyle\tilde{\mathbf{\Pi}}_{m}$
$\displaystyle=\mathbf{H}_{T_{\Pi}}\tilde{\mathbf{x}}_{T_{m}}+\mathbf{H}_{f_{\Pi}}{}^{G}\tilde{\mathbf{\Pi}}+\mathbf{n}_{m},$
(15)

where $\tilde{\mathbf{\Pi}}_{m}$ is the 3D plane measurement residual,
$\mathbf{H}_{T_{\Pi}}$ and $\mathbf{H}_{f_{\Pi}}$ are the measurement
Jacobians in respect to the current state $\mathbf{x}_{T_{m}}$ and the plane
feature ${}^{G}\mathbf{\Pi}$, respectively.

With initial estimations and an adequate amount of measurements, we perform an
EKF update for plane features. Normally, planes are tracked long but
discontinuously between frames due to the instability of detecting them from
noisy depth maps. Thus, for planes, it is unreasonable to classify the long-
term and short-term features based on the number of consecutive tracks.
Different from point features, all the planes are regarded as SLAM features
and added to the state vector as soon as there are sufficient observations.
Moreover, to improve computational efficiency, small and short-tracked planes
are delayed marginalized from the state when they are lost for an extended
period (greater than 200 frames in our experiments). Other planes will be
maintained in the state as permanent landmarks providing long-term
constraints. In this way, we retain reliable and dominant planes in the state
for overcoming cumulative drift.

###  III-F Drift Suppression

To suppress potential drift, we introduce a novel graph-based strategy that
fully exploits the spatial relations of plane patches to detect drift,
followed by a de-drift update to correct the error. More concretely, planes
are organized as a graph that encodes geometric information of the scene. By
matching two graphs, we search overlapping and identical structures in the
global map, which are assumed to be inconsistencies caused by drift. The error
is then corrected by aligning the detected structural ‘ghosting’. In what
follows, we will elaborate on the process.

####  III-F1 Problem Formulation

Considering two graphs $\mathcal{G}_{A}=(\mathcal{V}_{A},\mathcal{E}_{A})$ and
$\mathcal{G}_{M}=(\mathcal{V}_{M},\mathcal{E}_{M})$, the problem of graph
matching can be formulated as determining an assign matrix $\mathbf{X}^{*}$:

$\displaystyle\mathbf{X}^{*}=\arg\max\sum_{i\in\mathcal{V}_{A},j\in\mathcal{V}_{M}}\mathbf{X}_{ij}\mathbf{K}^{P}_{ij}+$
(16)
$\displaystyle\sum_{(i_{1},i_{2})\in\mathcal{E}_{A},(j_{1},j_{2})\in\mathcal{E}_{M}}\mathbf{X}_{i_{1}j_{1}}\mathbf{X}_{i_{2}j_{2}}\mathbf{K}^{Q}_{(i_{1},i_{2})(j_{1},j_{2})}$
$\displaystyle s.t.$ $\displaystyle\mathbf{X}_{ij}\in\\{0,\ 1\\},\
\mathbf{X}\mathbf{1}_{n_{M}}\leq\mathbf{1}_{n_{A}},\
\mathbf{X}^{\mathsf{T}}\mathbf{1}_{n_{A}}\leq\mathbf{1}_{n_{M}},$

where $\mathcal{V}$ and $\mathcal{E}$ stand for the vertex set and the edge
set, and $n$ is the number of vertices. $\mathbf{K}^{P}$ and $\mathbf{K}^{Q}$
are affinity matrices representing the similarity of vertices and edges,
respectively. Based on defined affinity matrices, the problem can be solved by
factorized graph matching (FGM) [27].

####  III-F2 Graph Construction

In the context of graph matching, a plane $i$ is treated as a finite patch
with several geometric attributes:

  * •

${I}_{i}$: plane identity in the global map.

  * •

$\mathbf{n}_{i}$: plane normal vector.

  * •

$d_{i}$: distance from the origin to the plane.

  * •

$\mathcal{L}_{i}$: list of convex hull points, which is computed in the plane
detection thread after projecting all the fitted inliers onto the plane.

  * •

$a_{i}$: area of the convex hull.

And four attributes are defined to describe the relation between two plane
patches $(i,j)$:

  * •

$\theta_{ij}$: angle of their normal vectors,
$\theta_{ij}=\arccos(|\mathbf{n}_{i}^{\mathsf{T}}\mathbf{n}_{j}|),\
0\leq\theta_{ij}\leq\frac{\pi}{2}$.

  * •

$d_{ij}$: minimum distance from all points on patch $i$ to patch $j$.

  * •

$c_{ij}$: category of the relation. There are three types: a) If
$\theta_{ij}\leq\delta_{\theta}$, the category is ‘parallel’. b) Else if patch
$j$ is separated from patch $i$ ($d_{ji}>0$), the category is ‘separation’. c)
Otherwise, the category is ‘intersection’ that means patch $j$ is split by
infinite plane $i$ ($d_{ji}=0$).

  * •

$o_{ij}$: overlapping area after projecting patch $i$ onto patch $j$
($o_{ij}\geq 0$). When they are not overlapping, $-o_{ij}$ indicates the
minimum parallel distance along patch $j$ between their convex hull points
($o_{ij}<0$).

Note that the relations are asymmetrical because $c_{ij}\neq c_{ji}$,
$d_{ij}\neq d_{ji}$, and $o_{ij}\neq o_{ji}$. Fig. 3 exhibits possible
relative spatial positions of two plane patches.

Based on these attributes, a scene can be represented as a directed graph,
whose vertices and edges are plane patches and their geometric relationships.
The angle and the distance are used to define the aforementioned affinity
matrices and other attributes serve for validation. In particular, for
vertices, the affinity matrix is defined as:

$\displaystyle\mathbf{K}^{P}_{ij}$
$\displaystyle=\mathcal{S}(\theta_{ij},d_{ij}),$ (17)

and for edges it is:

$\displaystyle\mathbf{K}^{Q}_{({i_{1}},{i_{2}})({j_{1}},{j_{2}})}$
$\displaystyle=\mathcal{S}(\Delta\theta,\Delta d)$ (18)
$\displaystyle\Delta\theta=|\theta_{{i_{1}}{i_{2}}}-\theta_{{j_{1}}{j_{2}}}|,$
$\displaystyle\ \Delta d=|d_{{i_{1}}{i_{2}}}-d_{{j_{1}}{j_{2}}}|,$

where $\mathcal{S}(\cdot,\cdot)$ is a score function mapping variables to
$[0,\ 1]$, as plotted in Fig. 4.

Figure 4: Pipeline of the drift suppression.

We emphasize that the suggested graph differs from others because instead of
considering the size and the center distance as comparisons, we model the
planes using convex hulls and fully explore the relative positional
relationships at the plane boundaries to form directed edges, under the
influence of the partial observation problem in the incremental plane map that
the sizes of planes continue to expand during observation.

Algorithm 1 Graph-Based Drift Detection

Unary Check:

  * •

Retrieve candidate matches as constraints $\mathbf{Ct}$: ($\mathbf{Ct}_{ij}=1$
means that plane $i$ in the local map can be matched with plane $j$ in the
global map, otherwise it cannot.)

    * –

If $\theta_{ij}<\delta_{\theta}$, $d_{ij}<\delta_{d}$, and $o_{ij}<\delta_{o}$
then $\mathbf{Ct}_{ij}=1$.

    * –

Else $\mathbf{Ct}_{ij}=0$.

  * •

Set active planes to be unmatched as priors:

    * –

If $I_{j}==I_{i}$ then $\mathbf{Ct}_{:j}=0$.

  * •

Take all candidate planes that satisfy $\sum{\mathbf{Ct}}_{i:}>0$ and
$\sum{\mathbf{Ct}}_{:j}>0$ to build two subgraphs
${}^{G}\mathcal{G}_{A}^{\prime}$ and ${}^{G}\mathcal{G}_{M}^{\prime}$ with
subconstraints $\mathbf{Ct}^{\prime}$.

Graph Matching:

  * •

Compute affinity matrices $\mathbf{K}^{P}$ and $\mathbf{K}^{Q}$ for
${}^{G}\mathcal{G}_{A}^{\prime}$ and ${}^{G}\mathcal{G}_{M}^{\prime}$.

  * •

Get matches using the FGM algorithm:

    * –

Input:  ${}^{G}\mathcal{G}_{A}^{\prime}$, ${}^{G}\mathcal{G}_{M}^{\prime}$,
$\mathbf{Ct}^{\prime}$, $\mathbf{K}^{P}$, $\mathbf{K}^{Q}$

    * –

Output:  $\mathbf{X}^{\prime}$

  * •

Convert $\mathbf{X}^{\prime}$ to the original assign matrix $\mathbf{X}$.

Overlap Check:

  * •

Compute the overall overlap of the matched vertices:

    * –

Project the matched planes onto the ground (with known gravity) and calculate
the overlap between convex hulls of each set, as illustrated in Fig. 4.

  * •

If
$o_{\mathcal{A}\mathcal{M}}/(a_{\mathcal{A}}+a_{\mathcal{M}}-o_{\mathcal{A}\mathcal{M}})<\delta_{o}^{\prime\prime}$
then reject the matches.

Binary Check:

  * •

Compare edge pairs for the matches:

    * –

$\Delta\theta=|\theta_{{i_{1}}{i_{2}}}-\theta_{{j_{1}}{j_{2}}}|$

    * –

$\Delta d=|d_{{i_{1}}{i_{2}}}-d_{{j_{1}}{j_{2}}}|$

    * –

$\Delta o=|o_{{i_{1}}{i_{2}}}-o_{{j_{1}}{j_{2}}}|$

  * •

If $\Delta\theta<\delta_{\theta}^{\prime}$, $\Delta d<\delta_{d}^{\prime}$,
and $\Delta o<\delta_{o}^{\prime}$ then accept it.

  * •

Else $\mathbf{X}_{i_{1}j_{1}}=0,\mathbf{X}_{i_{2}j_{2}}=0$ and reject the two
matches.

####  III-F3 Drift Detection

The objective of drift detection is to search for similar and overlapping
plane configurations from the global map, which is addressed as a problem of
graph matching. Algorithm 1 and Fig. 4 outline the process. Firstly, planes
observed in the latest ten frames are considered as currently active planes
(local map), and their nearest observations are constructed into a fully-
connected graph. Then we remove them from the global map and match them with
the rest planes leveraging the FGM algorithm with the above defined affinity
matrices. In order to improve efficiency and robustness, we perform a unary
check on the vertices to limit the number of candidate matches. The thresholds
here are relatively weak constraints to avoid rejecting correct matches under
large drift. In addition, since FGM may encounter failure modes, we adopt an
overlap metric to quantify the overlap degree between the two configurations
and employ a binary check to validate if the matched edges have similar
relative spatial positions. There may be occlusions between planes due to
changes in viewpoints. Therefore, instead of requiring the edges to be of the
same category (as in Fig. 3), we only constrain their relative positions
$\Delta\theta$, $\Delta d$, and $\Delta o$ within strict thresholds. If all
the constraints are satisfied, we accept the matches and consider that drift
happens as the two graphs encode the same information. The drift detection
strategy requires at least three planes in the local map.

####  III-F4 De-Drift Update

Once drift is detected, we fix the previously created landmark
$\mathbf{\Pi}_{r}$ that is considered drift-free and enforce a pair-wise
equality constraint to update the drifting plane landmark $\mathbf{\Pi}_{d}$:

$\mathbf{z}_{r}={}^{G}{\mathbf{\Pi}}_{d}-{}^{G}{\mathbf{\Pi}}_{r}+\mathbf{n}_{r},$
(19)

where $\mathbf{z}_{r}$ is the drift residual and $\mathbf{n}_{r}$ is a random
noise. Following that, the system state is refined with fixed plane landmarks.
Eventually, similar planes will be merged in delayed marginalization.

TABLE I: Evaluation on the CID-SIMS Dataset (RMSE ATE ($\downarrow$) in
Meters)

Sequence | Length [m] | ORB-SLAM3 [1] | VINS-Mono [20] | OpenVINS [8] | ov_plane [2] | PlanarSLAM [17] | PGD w/o P. | PGD w/o G. | PGD-VIO
---|---|---|---|---|---|---|---|---|---
Office_1 | 42.01 | 0.104 | 0.120 | 0.155 | 0.133 | 0.228 | 0.097 | 0.030 | 0.030
Office_2 | 90.31 | 0.496 | 0.158 | 0.079 | 0.102 | 0.275 | 0.091 | 0.030 | 0.029
Office_3 | 95.25 | 0.062 | / | 0.112 | 0.110 | 0.311 | 0.123 | 0.033 | 0.039
Floor14_1 | 103.7 | 0.260 | 0.412 | 0.728 | 0.408 | 0.265 | 0.229 | 0.173 | 0.132
Floor14_2 | 106.4 | 3.569 | 2.627 | 1.750 | 1.704 | / | 0.325 | 0.367 | 0.163
Floor14_3 | 180.43 | 0.415 | / | 0.494 | 0.345 | 5.303 | 0.382 | 0.399 | 0.645
14-13-14 | 249.96 | 0.416 | / | 1.510 | 1.518 | / | 0.992 | 0.861 | 0.824
14-13-12 | 21.89 | 3.042 | 0.773 | 0.118 | 0.106 | 1.878 | 0.119 | 0.108 | 0.108
Floor3_1 | 85.61 | 0.283 | / | 0.833 | 0.655 | 1.037 | 0.547 | 0.476 | 0.112
Floor3_2 | 150.55 | 4.877 | 0.525 | 1.336 | 1.591 | 0.886 | 0.799 | 0.426 | 0.396
Floor3_3 | 196.46 | 0.323 | 2.073 | 2.127 | 3.026 | / | 0.733 | 1.372 | 0.692
Floor13_1 | 130.43 | 0.921 | / | / | 1.721 | / | 0.912 | 0.434 | 0.380
Floor13_2 | 135.10 | 0.494 | 2.655 | 1.415 | / | / | 2.009 | 0.498 | 0.403
Apartment1_1 | 66.01 | 0.187 | 0.397 | / | 0.476 | 0.135 | 0.139 | 0.050 | 0.049
Apartment1_2 | 77.18 | / | / | 0.185 | 0.074 | 0.212 | 0.129 | 0.085 | 0.136
Apartment1_3 | 154.00 | 0.688 | 0.355 | 0.224 | 0.261 | / | 0.234 | 0.163 | 0.138
Apartment2_1 | 68.50 | 2.221 | 0.216 | / | / | 0.199 | 0.114 | 0.045 | 0.050
Apartment2_2 | 85.88 | 0.739 | 0.146 | 0.181 | 0.272 | / | 0.107 | 0.053 | 0.051
Apartment2_3 | 100.04 | 0.096 | 0.252 | 0.144 | / | / | 0.104 | 0.049 | 0.041
Apartment3_1 | 73.22 | 0.111 | 0.508 | 0.122 | 0.145 | 0.747 | 0.115 | 0.076 | 0.065
Apartment3_2 | 84.42 | 0.292 | / | 1.068 | 0.097 | / | 0.076 | 0.090 | 0.097
Apartment3_3 | 147.96 | 2.689 | 0.346 | 0.144 | 0.137 | 0.174 | 0.119 | 0.074 | 0.089

  * •

* The best results for each sequence are boldfaced and the next best results are underlined.

Figure 5: Comparative trajectories of the evaluated methods on the CID-SIMS
dataset. For visualization, the first 500 frames are used to align the
trajectories with the ground truth.

##  IV EXPERIMENTS

In this section, we evaluate the overall performance of the proposed PGD-VIO
on two public RGB-D inertial datasets: the CID-SIMS dataset [26] and the VCU-
RVI dataset [25].

We make comparisons with well-known point-based systems (ORB-SLAM3 [1], VINS-
Mono [20], and OpenVINS [8]) and two plane-aided systems (ov_plane [2] and
PlanarSLAM [17]). All the experiments are performed on an Intel i9-13900KS CPU
with suggested configurations. The root mean square error (RMSE) of the
absolute trajectory error (ATE) is considered as the quantitative evaluation
criterion. We disable the global bundle adjustment module of ORB-SLAM3 and
adopt the online poses for a fair comparison. Additionally, considering the
randomness of pose estimation, we run each system five times and report the
median results. / indicates the method fails in all five tests when the
estimated trajectory is less than 50% complete or drifts larger than 10 m. We
also perform ablation studies considering two variants of our method. PGD w/o
P. is the RGB-D-inertial mode after introducing depth information. On this
basis, PGD w/o G. adds plane measurements into the state vector to provide a
baseline for PGD-VIO, which is the full version with the proposed graph-based
drift suppression.

###  IV-A CID-SIMS Dataset

The CID-SIMS dataset [26] is a challenging indoor dataset for wheeled robots
with abundant real environments and provides the whole ground truth for long
sequences. According to the results from Table I, PGD-VIO achieves the lowest
or the second-lowest ATE in most sequences, free of expensive global bundle
adjustment (BA) and loop closing techniques, exhibiting superior performance
to ORB-SLAM3, which performs poorly in several challenging sequences because
the tracking is lost in weakly textured regions and fast motions. PlanarSLAM
is an RGB-D system built on ORB-SLAM2 [19] that estimates rotations based on
the Manhattan structure assumption and optimizes translations in the BA.
Suffering from the same issues with ORB-SLAM3, PlanarSLAM easily collapses.
Specially, without the assistance of IMU measurements, PlanarSLAM fails in
more sequences than other methods. In long-term sequences, the degenerate
movement of a wheeled robot, such as moving along straight lines, makes VINS-
Mono and OpenVINS fail to observe the scale information, which brings about
large locating errors. ov_plane extends OpenVINS by adding planes, in which
points and planes are treated as combinations of SLAM features and MSCKF
features for different updates. Although it surpasses OpenVINS on average
owing to the exploitation of point-on-plane constraints, the improvement is
limited as few planes are successfully tracked in the clustered environments
in this dataset. Exemplary trajectories estimated by these methods and the
corresponding ground truth are displayed in Fig. 5. Overall, PGD-VIO has a
tendency to show more complete trajectories with low localization errors
compared to the other algorithms, benefiting from the proposed novelties.

Figure 6: Results on sequence corridor4 (210 m) of the VCU_RVI dataset. The
left two figures show the plane maps without and with drift suppression,
respectively, and planes are visualized in different colors. The right figure
displays the comparison trajectories, in which the first 500 frames are used
to align the estimated trajectories with the ground truth trajectories and the
end points marked as stars reflect their cumulative drift. Before the first
drift is detected, PGD w/o G. and PGD-VIO are completely coincident. The error
of PGD w/o G. gradually increases over time, whereas PGD-VIO effectively
reduces the final cumulative error and enhances the consistency of the final
map with the help of drift suppression.

Regarding the influence of different modules, the absolute scale is
supplemented after integrating depth information and thus PGD w/o P. has
reasonable performance in all sequences, better than VINS-Mono and OpenVINS.
Compared with it, deploying plane landmarks for state updating brings an
improvement for PGD w/o G. in 82% sequences. The performance degrades in some
sequences, for example, sequence Floor14_3 and Floor3_3, as it detects
inaccurate plane measurements because of the reflective mirrors throughout the
long corridors. For short-term sequences that are full of rotations, e.g.
sequences in office and apartment environments, the proposed drift suppression
strategy slightly affects the system as no substantial drift occurs. In
contrast, PGD-VIO exhibits obvious advantages in long-term sequences, e.g.
sequences in floor environments, by aligning the structural ‘ghostings’ in the
scenes, which effectively proves that the drift suppression strategy is
helpful to ease cumulative errors.

TABLE II: Evaluation on the VCU-RVI Dataset (RMSE ATE ($\downarrow$) in
Meters)

Method | corridor1 | corridor2 | corridor3 | corridor4
---|---|---|---|---
ORB-SLAM3 [1] | 0.488 | / | 5.652 | 4.089
VINS-Mono [20] | 4.390 | 1.610 | 3.970 | 4.330
VINS-RGBD [22] | 5.130 | 1.810 | 6.810 | 1.950
OpenVINS [8] | 1.039 | 1.639 | 0.435 | 0.706
ov_plane [2] | 1.298 | 3.226 | 0.922 | 1.262
PlanarSLAM [17] | 0.073 | / | / | /
S-VIO [10] | 0.580 | 1.490 | 0.910 | 0.200
PGD w/o P. | 1.411 | 1.423 | 0.809 | 0.379
PGD w/o G. | 0.223 | 0.285 | 0.418 | 0.945
PGD-VIO | 0.192 | 0.075 | 0.404 | 0.121

  * •

* The best results for each sequence are boldfaced and the next best results are underlined.

###  IV-B VCU-RVI Dataset

Furthermore, pose estimation accuracy and map consistency are evaluated on the
VCU-RVI dataset [25], which provides ground truth trajectories at the
beginning and the ending to manifest cumulative drift for long-term sequences.
VINS-RGBD [22] and S-VIO [10] are further included in the comparison using
results from the original papers [25, 10]. We list the RMSE ATE for the
corridor sequences in Table II. As evident, PGD-VIO achieves the lowest ATE
except on sequence corridor1, where PlanarSLAM performs well. However,
PlanarSLAM fails in other sequences because point feature tracking is lost
under conditions of insufficient textures and imperfect Manhattan structures.
Also, we observe that ov_plane struggles with detecting planes in most images
and therefore does not effectively improve the accuracy of OpenVINS. We hope
that plane measurements in PGD w/o G. contribute to localization as in
sequence corridor1, corridor2, and corridor3. However, if the system
experiences drift, there is a certain probability of erroneously associating
unrelated planes, so that the system state is updated towards the wrong
direction, and ultimately resulting in low accuracy, as in sequence corridor4.
The proposed drift suppression strategy helps address the problem as early as
possible to avoid large drift. By virtue of it, PGD-VIO obtains a 45%
improvement on average compared to PGD w/o G. in these long corridor
sequences. Intuitively, Fig. 6 illustrates the effectiveness of the drift
suppression module.

##  V CONCLUSIONS

In this paper, we propose an RGB-D VIO system, named PGD-VIO, effectively
integrating depth information and plane measurements within the naive EKF
framework. More importantly, we fully exploit different spatial relations of
boundary plane patches and apply a graph-based strategy for drift suppression.
The proposed system is assessed on two real-world datasets with experimental
results proving that PGD-VIO greatly enhances the performance against
cumulative drift, enables robust and accurate localization without loop
closures and produces highly consistent plane maps, especially in long-term
navigation. However, PGD-VIO struggles when planar structures are few or
indistinguishable due to the repetitiveness of the scenes. In the future, we
aim to take into account the structure regularities in the process of plane
association and EKF update to better explore the available geometrical
information in planar environments.

## References

  * [1] C. Campos, R. Elvira, J. J. G. Rodríguez, J. M. Montiel, and J. D. Tardós, “Orb-slam3: An accurate open-source library for visual, visual–inertial, and multimap slam,” _IEEE Transactions on Robotics_ , vol. 37, no. 6, pp. 1874–1890, 2021.
  * [2] C. Chen, P. Geneva, Y. Peng, W. Lee, and G. Huang, “Monocular visual-inertial odometry with planar regularities,” in _2023 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2023, pp. 6224–6231.
  * [3] D. Chen, S. Wang, W. Xie, S. Zhai, N. Wang, H. Bao, and G. Zhang, “Vip-slam: An efficient tightly-coupled rgb-d visual inertial planar slam,” in _2022 International Conference on Robotics and Automation (ICRA)_. IEEE, 2022, pp. 5615–5621.
  * [4] H. M. Cho, H. Jo, and E. Kim, “Sp-slam: Surfel-point simultaneous localization and mapping,” _IEEE/ASME Transactions on Mechatronics_ , vol. 27, no. 5, pp. 2568–2579, 2021.
  * [5] Z. Deng, Y. Zhang, Y. Wu, Z. Ge, X. Hu, and W. Sun, “Object-plane co-represented and graph propagation-based semantic descriptor for relocalization,” _IEEE Robotics and Automation Letters_ , vol. 7, no. 4, pp. 11 023–11 030, 2022.
  * [6] C. Feng, Y. Taguchi, and V. R. Kamat, “Fast plane extraction in organized point clouds using agglomerative hierarchical clustering,” in _2014 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2014, pp. 6218–6225.
  * [7] E. Fernández-Moral, P. Rives, V. Arévalo, and J. González-Jiménez, “Scene structure registration for localization and mapping,” _Robotics and Autonomous Systems_ , vol. 75, pp. 649–660, 2016.
  * [8] P. Geneva, K. Eckenhoff, W. Lee, Y. Yang, and G. Huang, “Openvins: A research platform for visual-inertial estimation,” in _2020 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2020, pp. 4666–4672.
  * [9] P. Geneva, K. Eckenhoff, Y. Yang, and G. Huang, “Lips: Lidar-inertial 3d plane slam,” in _2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2018, pp. 123–130.
  * [10] P. Gu and Z. Meng, “S-vio: Exploiting structural constraints for rgb-d visual inertial odometry,” _IEEE Robotics and Automation Letters_ , 2023.
  * [11] M. Hsiao, E. Westman, and M. Kaess, “Dense planar-inertial slam with structural constraints,” in _2018 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2018, pp. 6521–6528.
  * [12] J. Hu, K. Ren, X. Xu, L. Zhou, X. Lang, Y. Mao, and G. Huang, “Efficient visual-inertial navigation with point-plane map,” in _2023 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2023, pp. 10 659–10 665.
  * [13] J. Jiang, J. Wang, P. Wang, P. Bao, and Z. Chen, “Lipmatch: Lidar point cloud plane based loop-closure,” _IEEE Robotics and Automation Letters_ , vol. 5, no. 4, pp. 6861–6868, 2020.
  * [14] K. Joo, P. Kim, M. Hebert, I. S. Kweon, and H. J. Kim, “Linear rgb-d slam for structured environments,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 44, no. 11, pp. 8403–8419, 2021.
  * [15] K. Joo, T.-H. Oh, F. Rameau, J.-C. Bazin, and I. S. Kweon, “Linear rgb-d slam for atlanta world,” in _2020 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2020, pp. 1077–1083.
  * [16] P. Kim, B. Coltin, and H. J. Kim, “Linear rgb-d slam for planar environments,” in _Proceedings of the European Conference on Computer Vision (ECCV)_ , 2018, pp. 333–348.
  * [17] Y. Li, R. Yunus, N. Brasch, N. Navab, and F. Tombari, “Rgb-d slam with structural regularities,” in _2021 IEEE international conference on Robotics and automation (ICRA)_. IEEE, 2021, pp. 11 581–11 587.
  * [18] A. I. Mourikis and S. I. Roumeliotis, “A multi-state constraint kalman filter for vision-aided inertial navigation,” in _Proceedings 2007 IEEE international conference on robotics and automation_. IEEE, 2007, pp. 3565–3572.
  * [19] R. Mur-Artal and J. D. Tardós, “Orb-slam2: An open-source slam system for monocular, stereo, and rgb-d cameras,” _IEEE transactions on robotics_ , vol. 33, no. 5, pp. 1255–1262, 2017.
  * [20] T. Qin, P. Li, and S. Shen, “Vins-mono: A robust and versatile monocular visual-inertial state estimator,” _IEEE Transactions on Robotics_ , vol. 34, no. 4, pp. 1004–1020, 2018.
  * [21] M. Shaheer, J. A. Millan-Romera, H. Bavle, J. L. Sanchez-Lopez, J. Civera, and H. Voos, “Graph-based global robot localization informing situational graphs with architectural graphs,” _arXiv preprint arXiv:2303.02076_ , 2023.
  * [22] Z. Shan, R. Li, and S. Schwertfeger, “Rgbd-inertial trajectory estimation and mapping for ground robots,” _Sensors_ , vol. 19, no. 10, p. 2251, 2019.
  * [23] Y. Wu, F. Tang, and H. Li, “Image-based camera localization: an overview,” _Visual Computing for Industry, Biomedicine, and Art_ , vol. 1, no. 1, pp. 1–13, 2018.
  * [24] Y. Yang, P. Geneva, X. Zuo, K. Eckenhoff, Y. Liu, and G. Huang, “Tightly-coupled aided inertial navigation with point and plane features,” in _2019 International conference on robotics and automation (ICRA)_. IEEE, 2019, pp. 6094–6100.
  * [25] H. Zhang, L. Jin, and C. Ye, “The vcu-rvi benchmark: Evaluating visual inertial odometry for indoor navigation applications with an rgb-d camera,” in _2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2020, pp. 6209–6214.
  * [26] Y. Zhang, N. An, C. Shi, S. Wang, H. Wei, P. Zhang, X. Meng, Z. Sun, J. Wang, W. Liang _et al._ , “Cid-sims: Complex indoor dataset with semantic information and multi-sensor data from a ground wheeled robot viewpoint,” _The International Journal of Robotics Research_ , p. 02783649231222507, 2023.
  * [27] F. Zhou and F. De la Torre, “Factorized graph matching,” _IEEE transactions on pattern analysis and machine intelligence_ , vol. 38, no. 9, pp. 1774–1789, 2015.


# Count-Min sketches for Telemetry: analysis of performance in P4
implementations

J. A. Hernández1, D. Scano2, F. Cugini3, G. Martínez1, N. Koneva1, A. Sánchez-
Macián1, Ó. González de Dios4  1Dept. Ing. Telematica, Universidad Carlos III
de Madrid, Spain.  2Scuola Superiore Sant’Anna, Italy  3CNIT, Italy
4Telefonica I+D Spain

###### Abstract

Monitoring streams of packets at 100 Gb/s and beyond requires using compact
and efficient hashing-techniques like HyperLogLog (HLL) or Count-Min Sketch
(CMS). In this work, we evaluate the uses and applications of Count-Min Sketch
for Metro Networks employing P4-based packet-optical nodes. We provide
dimensioning rules for CMS at 100 Gb/s and 400 Gb/s and evaluate its
performance in a real implementation testbed.

##  I Introduction

Packet-optical nodes employing open operating systems like SONiC featuring
high-speed long-reach coherent optical pluggables (e.g., 400G ZR+) have
appeared in the optical arena to challenge classical transponder-based
systems.

In addition to having high-speed pluggables, such packet-optical boxes may
include programmable ASICs leveraging P4 technology [1]. P4 has demonstrated
its potential in a wide range of scenarios, including advanced monitoring and
telemetry, latency-aware scheduling and forwarding, 5G function acceleration,
cyber-security, in-network AI, etc. A broad summary of these use cases can be
found in [2, 3].

However, monitoring packet streams at line rates equal or above 100 Gb/s is
extremely challenging, especially given the fact that flow size typically
follow a Pareto distribution. This means that a few minor flows (the
elephants) contribute with the majority of packets and traffic in general and
viceversa, most of the flows (the mice) contain only a few packets [4, 5].

Indeed, the authors in [6] examine a large number of flows in a university
campus in Polland, and show that almost two thirds of flows contain only 1 or
2 packets. This means that sampling packets randomly will very likely not
observe a great portion of the packet flows, thus very inaccurate to identify
flow cardinality or estimate heavy hitters. Well-known hash-based algorithms
include: HyperLogLog (HLL) for estimating cardinality, Count-Min Sketch (CMS)
for detecting heavy hitters, Bloom Filters (BF) for detecting whether a flow
belongs to a set or not, etc. The authors in [7] have implemented many of
these hash-based algorithms in P4 and made the code open-source (SketchLib)
for further experimentation by the research community.

This article briefly reviews the use cases and applications of CMS in the
context of IP over Wavelength DIvision Multiplexing (IPoWDM) optical networks
with P4-based packet-optical nodes. Section II briefly reviews CMS and network
traffic characteristics. Section III provides a number of simulation
experiments and CMS design rule of thumbs for network scenarios at 100 Gb/s
and some real experiments using Sketchlib on an Intel-based P4 Tofino
scenario. Finally, section IV concludes this work with its main findings and
conclusions.

##  II Preliminars

###  II-A Traffic statistics review

In 2021, the authors in [6] released detailed statistics for the research
community regarding packet traces collected at a university campus in Poland
in year 2021 [6]. Some of the results observed include: (1) average packet
size of 870.6 Bytes, (2) Average flow size 68410 Bytes (78.5 packets), (3)
Flows with only 1 packet: 47.8%, and (4) Flows with only 1 or 2 packets: 65%.
Another important observation is that flow size follows a Pareto-like
distribution, where the majority of flows contain very few packets, while very
few heavy hitter flows comprise most of the traffic (in terms of packets),
confirming past observations in different scenarios [4, 5].

Following these numbers, Table I summarises both flow and packet rates per
switch port for a packet-optical node whose ports operate at line rates of 100
Gb/s and 400 Gb/s at different loads.

|  | 100 Gb/s |
---|---|---|---
| 10% | 40% | 70%
Flow rate | 18.25 K flow/s | 73 K flow/s | 127.75 K flow/s
Packet rate | 1.54 M packet/s | 6.17 M packet/s | 10.8 M packet/s
|  | 400 Gb/s |
| 10% | 40% | 70%
Flow rate | 73 K flow/s | 292 K flow/s | 511 K flow/s
Packet rate | 6.16 M packet/s | 24.64 M packet/s | 43.12 M packet/s
TABLE I: Flow and packet rate per port at 100 and 400 Gb/s

###  II-B Overview of CMS

The CMS is a data-structure that allows to store the frequencies of each
flowID in a compact manner [8]. It is very similar to having multiple Counting
Bloom Filters. The challenge is again to store the frequencies of flows
(especially the heavy hitters) where most of them are unique.

Figure 1: Example of a CMS structure, d=3 hash functions and W columns

To do this, the CMS comprises a matrix with $d$ rows (one per hash function)
and $w$ columns, as shown in Fig. 1. When an element arrives (a packet in this
scenario), the CMS computes all $d$ hash functions (one per row) and increases
by one each position in the appropriate column. For instance, in the example
of Fig. 1 with $d=3$ rows and $w=20$ columns, let us assume that the hashing
of packet $e$ gives the following results: $h_{1}(e)=10$, $h_{2}(e)=5$ and
$h_{3}(e)=14$. These values imply that the positions $[1,10]$, $[2,5]$ and
$[3,14]$ in the CMS matrix should be increased by one, as shown in the figure.
Thus, every single packet traversing the port requires computing $d$ different
hash functions of it and increasing the corresponding positions $[d,h_{d}(e)]$
of the CMS sketch.

After all elements (packets) are introduced, the CMS can be queried to get an
approximate of frequency for a particular element. Consider we want to
estimate the popularity of element $y$. To do this, the procedure is to hash
element $y$ and take the minimum value. Consider for example, that the CMS
array returns the following results: $h_{1}(y)=6$, $h_{2}(y)=7$ and
$h_{3}(y)=2$, and looking at positions $[1,6]$, $[2,7]$ and $[3,2]$ of the CMS
matrix, we observe values 5, 7, and 5 again. The number of packets arrived so
far with flowID = $y$ would then be $\min(5,7,5)=5$ packets. This is an
estimate and some errors may have occurred due to hash collisions (as it is
probably the second counter $[2,7]$ since the other two counters output 5
packets). For this reason, it is necessary to accurately dimension the CMS
structure for a given expected number of elements, that is, sufficient rows
and columns.

In general, CMS is an $(\epsilon,\delta)$ probabilistic data structure, where
the result returned is bounded to at most $\epsilon\|Count\|$ with probability
$1-\delta$, while both $\epsilon$ and $\delta$ can be obtained from the CMS
design parameters $d$ and $w$ as it follows:

$d=\left\lceil\ln(1/\delta)\right\rceil\quad\text{and}\quad
w=\left\lceil\frac{e}{\epsilon}\right\rceil$ (1)

where $e$ is the estimation error.

##  III Scenario and experiments

###  III-A Network setting and CMS dimensioning

Let us consider a monitoring time window of 0.1 seconds, where a blank CMS is
zeroed at time $t_{0}=0$ and is populated with the number of packet arrivals
until $t_{w}=0.1~{}s$. Following Table I (100 Gb/s, 40% load), we should
expect around 7,000 different flows whose size follows a zipf distribution. In
this regard, we have simulated a packet trace with $N=7,000$ different flow
IDs and packet sizes following a zipf distribution with scale $\alpha=1.1$
(following the examples of [9]). This means that the $k$-th flow has a
frequency $f_{k}$ following:

$f_{k}=\frac{\frac{1}{k^{\alpha}}}{\sum_{n=1}^{N}\frac{1}{n^{\alpha}}},\quad
k=1,\ldots,N$ (2)

Figure 2: Flow-size distribution: Zipf-like CDF

As shown in Fig. 2, the largest flow contributes with 15% of the total traffic
while the top-20 heaviest hitters comprises 49% of the total traffic (almost
the same as the other 6,980 flows). In this scenario, identifying the top-20
flows allows operators to take decisions regarding their treatment, i.e. using
different optical bands or alternative routes for load balancing and QoS
guarantees.

Figure 3: CMS accuracy at estimating top-20 heavy-hitter flows for different
configurations of CMS sketch: (top) $d=\\{3,5,7\\}$ hashes and $w=64$ columns,
and (bottom) $d=\\{3,5,7\\}$ hashes and $w=256$ columns

Fig. 3 further shows the estimated flow size (in no. of packets) for the
top-20 heaviest hitters for different CMS configurations, i.e. values of
$d\in\\{3,5,7\\}$ hashes and $w=\in\\{64,256\\}$ columns (simulation code
available in Github [10]).

###  III-B Experimental validation

The CMS-based solution has been validated using a network switch, equipped
with P4 ASIC, designed for data center operations and potentially suitable for
IPoWDM implementations (as shown in Fig. 4).

The traffic flows have been generated using a Spirent N4U. The P4
implementation uses five hash functions on the IP source address, each one
producing a result between 0 and 4,096 bit ($=2^{12}$), while the total CMS
occupies one register of size 65,536 bit.

Figure 4: Experimental setup in lab

In a first experiment, with the aim of collecting baseline performance, the
traffic is sent from one source to one destination host, at a maximum rate of
9.85 Gb/s over a 10G port with fixed packet size of 512 bytes. The experienced
latency to traverse the switch (including hashing and CMS processing) is
$0.95~{}\mu s$.

Then, traffic is generated by 5 different sub-networks each one comprising 256
hosts (i.e 1,280 IP source addresses) that send traffic to another destination
sub-network comprising 256 hosts. The average latency to traverse the switch
interconnecting both source and destination subnetworks is again $0.95~{}\mu
s$. This values slightly increases to $1.35~{}\mu s$ for packet size values of
1,024 bytes.

##  IV Conclusions

This work has evaluated the use of open-source implementation of Count-Min
Sketches (CMS) in a testbed encompassing a real P4 ASIC switch. We implemented
different versions of CMS sketches, suitable for ports at 100 and 400 Gb/s and
evaluated its performance in terms of latency introduced to the packets and
memory consumption of the P4 ASIC. As observed, every single packet must
traverse all the stages in the pipeline of the P4 implementaion, resulting in
a total latency that varies between $0.95$ and $1.35~{}\mu s$ of processing
time.

## Acknowledgments

The authors would like to acknowledge EU H2020 project B5G-OPEN (grant no.
101016663), the Spanish project ENTRUDIT (grant no. TED2021-130118B-I00) and
project FuN4Date-Redes Project under Grant PID2022-136684OB-C21 funded by
Agencia Estatal de Investigacion of Spain.

## References

  * [1] P. Bosshart, D. Daly, G. Gibb, M. Izzard, N. McKeown, J. Rexford, C. Schlesinger, D. Talayco, A. Vahdat, G. Varghese, and D. Walker, “P4: Programming protocol-independent packet processors,” _SIGCOMM Comput. Commun. Rev._ , vol. 44, no. 3, p. 87–95, jul 2014. [Online]. Available: https://doi.org/10.1145/2656877.2656890
  * [2] F. Cugini, D. Scano, A. Giorgetti, A. Sgambelluri, F. Paolucci, J. J. Vegas Olmos, and P. Castoldi, “Applications of p4-based network programmability in optical networks,” in _2022 Optical Fiber Communications Conference and Exhibition (OFC)_ , 2022, pp. 1–3.
  * [3] F. Cugini, D. Scano, A. Giorgetti, A. Sgambelluri, L. D. Marinis, P. Castoldi, and F. Paolucci, “Telemetry and ai-based security p4 applications for optical networks (invited),” _J. Opt. Commun. Netw._ , vol. 15, no. 1, pp. A1–A10, Jan 2023. [Online]. Available: https://opg.optica.org/jocn/abstract.cfm?URI=jocn-15-1-A1
  * [4] W. Fang and L. Peterson, “Inter-as traffic patterns and their implications,” in _Seamless Interconnection for Universal Services. Global Telecommunications Conference. GLOBECOM’99. (Cat. No.99CH37042)_ , vol. 3, 1999, pp. 1859–1868 vol.3.
  * [5] S. Molnar and Z. Moczar, “Three-dimensional characterization of internet flows,” in _2011 IEEE International Conference on Communications (ICC)_ , 2011, pp. 1–6.
  * [6] P. Jurkiewicz, G. Rzym, and P. Boryło, “Flow length and size distributions in campus internet traffic,” _Computer Communications_ , vol. 167, pp. 15–30, 2021. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0140366420320223
  * [7] H. Namkung, D. Kim, V. Sekar, and P. Steenkiste, “Sketchlib: Enabling efficient sketch-based monitoring on programmable switches,” in _USENIX NSDI 2022_. USENIX, April 2022. [Online]. Available: https://www.microsoft.com/en-us/research/publication/sketchlib-enabling-efficient-sketch-based-monitoring-on-programmable-switches/
  * [8] G. Cormode and S. Muthukrishnan, “An improved data stream summary: the count-min sketch and its applications,” _Journal of Algorithms_ , vol. 55, no. 1, pp. 58–75, 2005. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0196677403001913
  * [9] J. A. Hernandez, R. Sanchez, I. Martin, and D. Larrabeiti, “Meeting the traffic requirements of residential users in the next decade with current ftth standards: How much? how long?” _IEEE Communications Magazine_ , vol. 57, no. 6, pp. 120–125, 2019.
  * [10] J. A. Hernández, “Count-min sketch dimensioning examples for p4-based telemetry scenarios,” https://github.com/B5G-OPEN/countminsketch_P4telemetry, Jan 2023.