r|^{8/3}N_{f}^{8/3}r_{h}^{6}},$ $\displaystyle
v_{141}(r)=\frac{256\sqrt[3]{\frac{2}{3}}\pi^{5/3}\left(3840r^{2}-6480rr_{h}-24r_{h}^{2}\left(87w^{2}-110\right)-455\right)}{19683g_{s}|\log
r|^{8/3}NN_{f}^{8/3}r_{h}^{4}},$ $\displaystyle
v_{142}(r)=-\frac{512\sqrt[3]{\frac{2}{3}}\pi^{5/3}\left(16r^{2}-438rr_{h}+1307r_{h}^{2}\right)}{6561g_{s}|\log
r|^{8/3}NN_{f}^{8/3}r_{h}^{5}},\ \ \ \ \ \
v_{143}(r)=-\frac{1024i\sqrt[3]{2}\pi^{13/6}\sqrt{\frac{1}{N}}(209r+657r_{h})}{6561\
3^{5/6}\sqrt{g_{s}}|\log r|^{8/3}N_{f}^{8/3}r_{h}^{5}},$ $\displaystyle
v_{144}(r)=\frac{1024i\sqrt[3]{\frac{2}{3}}\pi^{5/3}w\left(-64r^{2}+119rr_{h}+989r_{h}^{2}\right)}{19683g_{s}|\log
r|^{8/3}NN_{f}^{8/3}r_{h}^{4}},\ \ \ \ \
v_{145}(r)=\frac{35840i\sqrt[3]{2}\pi^{13/6}\sqrt{\frac{1}{N}}w(r-11r_{h})}{6561\
3^{5/6}\sqrt{g_{s}}|\log r|^{8/3}N_{f}^{8/3}r_{h}^{5}},$ $\displaystyle
v_{146}(r)=\frac{327680i\sqrt[3]{\frac{2}{3}}\pi^{5/3}(r-2r_{h})(r-r_{h})}{6561g_{s}|\log
r|^{8/3}NN_{f}^{8/3}r_{h}^{4}},\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
v_{147}(r)=\frac{35840i\sqrt[3]{2}\pi^{13/6}\sqrt{\frac{1}{N}}w(r-11r_{h})}{6561\
3^{5/6}\sqrt{g_{s}}|\log r|^{8/3}N_{f}^{8/3}r_{h}^{5}},$ $\displaystyle
v_{148}(r)=\frac{35840i\sqrt[3]{2}\pi^{13/6}\sqrt{\frac{1}{N}}w(r-11r_{h})}{6561\
3^{5/6}\sqrt{g_{s}}|\log r|^{8/3}N_{f}^{8/3}r_{h}^{5}},\ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \
v_{149}(r)=-\frac{13312\sqrt[3]{\frac{2}{3}}\pi^{5/3}}{6561g_{s}|\log
r|^{8/3}NN_{f}^{8/3}r_{h}^{3}},$ $\displaystyle
v_{150}(r)=\frac{512\sqrt[3]{\frac{2}{3}}\pi^{5/3}\left(-64r^{2}+119rr_{h}+989r_{h}^{2}\right)}{19683g_{s}|\log
r|^{8/3}NN_{f}^{8/3}r_{h}^{4}},\ \ \ \ \ \ \ \ \ \ \ \
v_{151}(r)=-\frac{73472\sqrt[3]{\frac{2}{3}}\pi^{2/3}r_{h}(r-r_{h})}{59049g_{s}^{2}|\log
r|^{8/3}N^{2}N_{f}^{8/3}},$ $\displaystyle
v_{152}(r)=-\frac{512\sqrt[3]{\frac{2}{3}}\pi^{5/3}(480r-1033r_{h})(r-r_{h})}{19683g_{s}|\log
r|^{8/3}NN_{f}^{8/3}r_{h}^{4}},\ \ \ \ \ \ \ \ \
v_{153}(r)=-\frac{512\sqrt[3]{\frac{2}{3}}\pi^{5/3}(384r-1345r_{h})(r-r_{h})}{19683g_{s}|\log
r|^{8/3}NN_{f}^{8/3}r_{h}^{4}},$ $\displaystyle
v_{154}(r)=-\frac{512\sqrt[3]{\frac{2}{3}}\pi^{5/3}(288r-841r_{h})(r-r_{h})}{19683g_{s}|\log
r|^{8/3}NN_{f}^{8/3}r_{h}^{4}}.$

## References

  * [1] A. Misra and V. Yadav, On ${\cal M}$-Theory Dual of Large-$N$ Thermal QCD-Like Theories up to ${\cal O}(R^{4})$ and $G$-Structure Classification of Underlying Non-Supersymmetric Geometries, Adv. Theor. Math. Phys. 26, 10 (2022) [arXiv:2004.07259 [hep-th]].
  * [2] M. Mia, K. Dasgupta, C. Gale and S. Jeon, Five Easy Pieces: The Dynamics of Quarks in Strongly Coupled Plasmas, Nucl. Phys. B 839, 187 (2010) [arXiv:hep-th/0902.1540].
  * [3] A. Misra and C. Gale, Eur. Phys. J. C 80, no.7, 620 (2020) doi:10.1140/epjc/s10052-020-8174-5 [arXiv:1909.04062 [hep-th]].
  * [4] S. He, S. Y. Wu, Y. Yang and P. H. Yuan, JHEP 1304, 093 (2013) [arXiv:1301.0385 [hep-th]].
  * [5] M. Fromm, J. Langelage, S. Lottini and O. Philipsen, The QCD deconfinement transition for heavy quarks and all baryon chemical potentials, JHEP 1201 (2012) 042 [arXiv:1111.4953 [hep-lat]].
  * [6] J. Maldacena, The Large N Limit of Superconformal Field Theories and Supergravity, Adv.Theor.Math.Phys.2:231-252,1998 [arXiv:hep-th/9711200].
  * [7] T. Sakai, S. Sugimoto, Low energy hadron physics in holographic QCD, Prog.Theor.Phys.113:843-882,2005 [arXiv:hep-th/0412141]; T. Sakai, S. Sugimoto, More on a holographic dual of QCD, Prog.Theor.Phys.114:1083-1118,2005 [arXiv:hep-th/0507073].
  * [8] R. Heise and H. G. Svendsen, A note on fermions in holographic QCD, JHEP 08 (2007) 065 [arXiv:0706.2253[hep-th]].
  * [9] A. Misra and G. Yadav, QCD-Compatible Supermassive Inert Top-Down Holographic Mesinos at Intermediate Coupling, to appear in PRD [arXiv:2308.05033 [hep-th]].
  * [10] M. Dhuria and A. Misra, Towards MQGP, JHEP 1311 (2013) 001 [arXiv:hep-th/1306.4339].
  * [11] K. Sil and A. Misra, On Aspects of Holographic Thermal QCD at Finite Coupling, Nucl. Phys. B 910, 754 (2016) [arXiv:1507.02692 [hep-th]].
  * [12] J. Maldacena, S. H. Shenker and D. Stanford, A bound on chaos, JHEP 08, 106 (2016) [arXiv:1503.01409 [hep-th]].
  * [13] S. H. Shenker and D. Stanford, Black holes and the butterfly effect, JHEP 03, 067 (2014) [arXiv:1306.0622 [hep-th]].
  * [14] S. H. Shenker and D. Stanford, Multiple Shocks, JHEP 12, 046 (2014) [arXiv:1312.3296 [hep-th]].
  * [15] D. A. Roberts, D. Stanford and L. Susskind, Localized shocks, JHEP 03, 051 (2015) [arXiv:1409.8180 [hep-th]].
  * [16] S. H. Shenker and D. Stanford, Stringy effects in scrambling, JHEP 05, 132 (2015) [arXiv:1412.6087 [hep-th]].
  * [17] M. Blake, R. A. Davison, S. Grozdanov and H. Liu, Many-body chaos and energy dynamics in holography, JHEP 10, 035 (2018) [arXiv:1809.01169 [hep-th]].
  * [18] M. Blake, R. A. Davison and D. Vegh, Horizon constraints on holographic Greenquoterights functions, JHEP 01, 077 (2020) [arXiv:1904.12883 [hep-th]].
  * [19] M. Natsuume and T. Okamura, Nonuniqueness of Greenquoterights functions at special points, JHEP 12, 139 (2019) [arXiv:1905.12015 [hep-th]].
  * [20] M. Natsuume and T. Okamura, Holographic chaos, pole-skipping, and regularity, PTEP 2020, no.1, 013B07 (2020) [arXiv:1905.12014 [hep-th]].
  * [21] M. Natsuume and T. Okamura, Pole-skipping and zero temperature, Phys. Rev. D 103, no.6, 066017 (2021) [arXiv:2011.10093 [hep-th]].
  * [22] E. Rabinovici, A. Sánchez-Garrido, R. Shir and J. Sonner, Krylov complexity from integrability to chaos, JHEP 07, 151 (2022) [arXiv:2207.07701 [hep-th]].
  * [23] A. Altland, B. Post, J. Sonner, J. van der Heijden and E. P. Verlinde, Quantum chaos in 2D gravity, SciPost Phys. 15, no.2, 064 (2023) [arXiv:2204.07583 [hep-th]].
  * [24] S. Grozdanov, T. Lemut and J. F. Pedraza, Reconstruction of the quasinormal spectrum from pole skipping, Phys. Rev. D 108, no.10, L101901 (2023) [arXiv:2308.01371 [hep-th]].
  * [25] J. de Boer, E. Llabrés, J. F. Pedraza and D. Vegh, Chaotic strings in AdS/CFT, Phys. Rev. Lett. 120, no.20, 201604 (2018) [arXiv:1709.01052 [hep-th]].
  * [26] W. Fischler, V. Jahnke and J. F. Pedraza, Chaos and entanglement spreading in a non-commutative gauge theory, JHEP 11, 072 (2018) [erratum: JHEP 02, 149 (2021)] [arXiv:1808.10050 [hep-th]].
  * [27] S. Das, B. Ezhuthachan, A. Kundu, S. Porey, B. Roy and K. Sengupta, Out-of-Time-Order correlators in driven conformal field theories, JHEP 08, 221 (2022) [arXiv:2202.12815 [hep-th]].
  * [28] S. Das, B. Ezhuthachan, A. Kundu, S. Porey and B. Roy, Critical quenches, OTOCs and early-time chaos, JHEP 07, 046 (2022) [arXiv:2108.12884 [hep-th]].
  * [29] J. R. David, T. J. Hollowood, S. Khetrapal and S. P. Kumar, Chaos bound in Bershadsky-Polyakov theory, JHEP 10, 077 (2019) [arXiv:1906.00667 [hep-th]].
  * [30] R. Karlsson, A. Parnachev and P. Tadić, Thermalization in large-N CFTs, JHEP 09, 205 (2021) [arXiv:2102.04953 [hep-th]].
  * [31] D. M. Ramirez, Chaos and pole skipping in CFT2, JHEP 12, 006 (2021) [arXiv:2009.00500 [hep-th]].
  * [32] M. A. G. Amano, M. Blake, C. Cartwright, M. Kaminski and A. P. Thompson, Chaos and pole-skipping in a simply spinning plasma, JHEP 02, 253 (2023) [arXiv:2211.00016 [hep-th]].
  * [33] N. Abbasi and K. Landsteiner, Pole-skipping as order parameter to probe a quantum critical point, JHEP 09, 169 (2023) [arXiv:2307.16716 [hep-th]].
  * [34] M. Blake and R. A. Davison, Chaos and pole-skipping in rotating black holes, JHEP 01, 013 (2022) [arXiv:2111.11093 [hep-th]].
  * [35] K. Jensen, Chaos in AdS2 Holography, Phys. Rev. Lett. 117, no.11, 111601 (2016) [arXiv:1605.06098 [hep-th]].
  * [36] X. L. Qi and Z. Yang, Butterfly velocity and bulk causal structure, [arXiv:1705.01728 [hep-th]].
  * [37] M. Mezei and D. Stanford, On entanglement spreading in chaotic systems, JHEP 05, 065 (2017) [arXiv:1608.05101 [hep-th]].
  * [38] K. Sil, Pole skipping and chaos in anisotropic plasma: a holographic study, JHEP 03, 232 (2021) [arXiv:2012.07710 [hep-th]].
  * [39] M. Blake, H. Lee and H. Liu, A quantum hydrodynamical description for scrambling and many-body chaos, JHEP 10, 127 (2018) [arXiv:1801.00010 [hep-th]].
  * [40] D. S. Ageev, Chaotic nature of holographic QCD, Phys. Rev. D 104, no.12, 126013 (2021).
  * [41] N. Losacco, Holographic Study of the $Q\bar{Q}$ Chaotic Dynamics in General Thermal Background, EPJ Web Conf. 270, 00025 (2022) [arXiv:2211.16840 [hep-ph]].
  * [42] K. Hashimoto, K. Murata and K. Yoshida, Chaos in chiral condensates in gauge theories, Phys. Rev. Lett. 117, no.23, 231602 (2016) [arXiv:1605.08124 [hep-th]].
  * [43] T. Akutagawa, K. Hashimoto, K. Murata and T. Ota, Chaos of QCD string from holography, Phys. Rev. D 100, no.4, 046009 (2019) [arXiv:1903.04718 [hep-th]].
  * [44] E. Witten, Anti-de Sitter space, thermal phase transition, and confinement in gauge theories, Adv. Theor. Math. Phys. 2, 505-532 (1998) [arXiv:hep-th/9803131 [hep-th]].
  * [45] A. Misra and G. Yadav, (Almost) Contact (3) (Metric) Structure(s) and Transverse $SU(3)$ Structures Associated with ${\cal M}$-Theory Dual of Thermal QCD at Intermediate Coupling, [arXiv:2211.13186[hep-th]].
  * [46] V. Yadav, G. Yadav and A. Misra,(Phenomenology/Lattice-Compatible) $SU(3)$ M$\chi$PT HD up to ${\cal O}(p^{4})$ and the ${\cal O}\left(R^{4}\right)$-Large-$N$ Connection, JHEP 2108 (2021) 151 [arXiv:2011.04660 [hep-th]].
  * [47] M. Ionel and M. Min-Oo, Cohomogeneity One Special Lagrangian 3-Folds in the Deformed and the Resolved Conifolds, Illinois Journal of Mathematics, Vol. 52, Number 3 (2008).
  * [48] M. Becker, K. Dasgupta, A. Knauf and R. Tatar, Geometric transitions, flops and nonKahler manifolds. I., Nucl. Phys. B 702, 207 (2004) [hep-th/0403288].
  * [49] V. Yadav and A. Misra, M-Theory Exotic Scalar Glueball Decays to Mesons at Finite Coupling, JHEP 09, 133 (2018) [arXiv:1808.01182 [hep-th]].
  * [50] M. Kruczenski, D. Mateos, R. C. Myers and D. J. Winters, Towards a holographic dual of large-$N_{c}$ QCD, JHEP 0405 (2004) 041 [arXiv:hep-th/0311270].
  * [51] M. Dhuria and A. Misra, Transport Coefficients of Black MQGP M3-Branes, Eur. Phys. J. C 75, 16 (2015) [arXiv:1406.6076[hep-th]].
  * [52] R. Argurio, A. Armoni, M. Bertolini, F. Mignosa and P. Niro, Vacuum structure of large N QCD3 from holography, JHEP 07, 134 (2020) [arXiv:2006.01755[hep-th]].
  * [53] K. Becker and M. Becker, Supersymmetry Breaking, M-Theory and Fluxes, JHEP 07, 038 (2001) [arXiv:hep-th/0107044].
  * [54] A. Czajka, K. Dasgupta, C. Gale, S. Jeon, A. Misra, M. Richard and K. Sil, Bulk Viscosity at Extreme Limits: From Kinetic Theory to Strings, JHEP 1907, 145 (2019) [arXiv:1807.04713 [hep-th]].
  * [55] A. A. Tseytlin, R**4 terms in 11 dimensions and conformal anomaly of (2,0) theory, Nucl. Phys. B bf584, 233-250 (2000) doi:10.1016/S0550-3213(00)00380-1 [arXiv:hep-th/0005072 [hep-th]].
  * [56] G. Yadav, V. Yadav and A. Misra, $\mathscr{M}$cTEQ ($\mathscr{M}$ chiral perturbation theory-compatible deconfinement Temperature and Entanglement entropy up to terms Quartic in curvature) and FM (Flavor Memory), JHEP 10 (2021) 220, arXiv:2108.05372 [hep-th].
  * [57] G. Yadav and A. Misra, Entanglement entropy and Page curve from the M-theory dual of thermal QCD above $T_{c}$ at intermediate coupling, Phys. Rev. D 107 (2023) 10, 106015 [arXiv:2207.04048[hep-th]].
  * [58] G. Yadav, Deconfinement temperature of rotating QGP at intermediate coupling from M-theory, Phys. Lett. B 841 (2023) 137925 [arXiv:2203.11959 [hep-th]].
  * [59] G. Yadav, Aspects of Thermal QCD Phenomenology at Intermediate Gauge/’t Hooft Coupling from String/M-Theory, (HD) Gravity Islands, and Multiverse, [arXiv:2310.06042 [hep-th]].
  * [60] M. Natsuume and T. Okamura, Pole skipping in a non-black-hole geometry, Phys. Rev. D 108, no.4, 046012 (2023) [arXiv:2306.03930 [hep-th]].
  * [61] G. Policastro, D. T. Son and A. O. Starinets, From AdS / CFT correspondence to hydrodynamics, JHEP 09, 043 (2002) [arXiv:hep-th/0205052 [hep-th]].
  * [62] K. Sil and A. Misra, New Insights into Properties of Large-N Holographic Thermal QCD at Finite Gauge Coupling at (the Non-Conformal/Next-to) Leading Order in N, Eur. Phys. J. C 76, no.11, 618 (2016) [arXiv:1606.04949 [hep-th]].
  * [63] P. K. Kovtun and A. O. Starinets, Quasinormal modes and holography, Phys. Rev. D 72, 086009 (2005) [arXiv:hep-th/0506184 [hep-th]].
  * [64] A. Czajka, K. Dasgupta, C. Gale, S. Jeon, A. Misra, M. Richard and K. Sil, Bulk Viscosity at Extreme Limits: From Kinetic Theory to Strings, JHEP 07, 145 (2019)[arXiv:1807.04713 [hep-th]].
  * [65] V. Yadav, A. Misra and K. Sil, Eur. Phys. J. C 77, no.10, 656 (2017) [arXiv:1707.02818 [hep-th]].


11institutetext: Univ. Grenoble Alpes, CNRS, Grenoble INP111Institute of
Engineering Univ. Grenoble Alpes, VERIMAG, 38000 Grenoble, France
22institutetext: National Institute of Standards and Technology, Gaithersburg,
MD, 20899, USA.

# Performance Evaluation of the NDN Data Plane Using Statistical Model
Checking

Siham Khoussi 1122 Ayoub Nouri 11 Junxiao Shi
James Filliben 2222 Lotfi Benmohamed 22 Abdella Battou 22 Saddek Bensalem 11

###### Abstract

Named Data Networking (NDN) is an emerging internet architecture that
addresses weaknesses of the Internet Protocol (IP). Since Internet users and
applications have demonstrated an ever-increasing need for high speed packet
forwarding, research groups have investigated different designs and
implementations for fast NDN data plane forwarders and claimed they were
capable of achieving high throughput rates. However, the correctness of these
statements is not supported by any verification technique or formal proof. In
this paper, we propose using a formal model-based approach to overcome this
issue. We consider the NDN-DPDK prototype implementation of a forwarder
developed at the National Institute of Standards and Technology (NIST), which
leverages concurrency to enhance overall quality of service. We use our
approach to improve its design and to formally demonstrate that it can achieve
high throughput rates.

###### Keywords:

NDN SMC Model-based design Networking

##  1 Introduction

††The identification of any commercial product or trade name does not imply
endorsement or recommendation by the National Institute of Standards and
Technology, nor is it intended to imply that the materials or equipment
identified are necessarily the best available for the purpose.

With the ever growing number of communicating devices, their intensive
information usage and the increasingly critical security issues, research
groups have recognized the limitations of the current Internet architecture
based on The internet protocol (IP) [15]. Information-Centric Networking (ICN)
is a new paradigm that transforms the Internet from a host-centric paradigm,
as we know it today, to an end-to-end paradigm focusing on the content, hence
more appropriate to our modern communication practices. It promises better
security, mobility and scalability.

Several research projects grew out of ICN. Examples include content-centric
architecture, Data Oriented Network Architecture and many others [21], but one
project stood out the most and was sponsored by the National Science
Foundation (NSF) called Named Data Networking (NDN) [23]. NDN is gaining
rapidly in popularity and has even started being advertised by major
networking players [2].

IP was designed to answer a different challenge, that is of creating a
communication network, where packets named only communication endpoints. The
NDN project proposes to generalizes this setting, such that packets can name
other objects, i.e. _“NDN changes the semantics of network services from
delivering the packet to a given destination address to fetching data
identified by a given name. The name in an NDN packet can name anything - an
endpoint, a data chunk in a movie or a book, a command to turn on some lights,
etc.“_ [23]. This simple change has deep implications in term of routers
forwarding performance since data needs to be fetched from an initially
unknown location.

Being a new concept, NDN (Section 2) has not undergone any formal verification
work yet. The initial phase of the project was meant to come up with proof-of-
concept prototypes for the proposed architecture. This has lead to a plethora
of less performing implementations in terms of packets’ forwarding rates
(throughput). A lot of effort was then directed to optimizing NDN forwarders’
performances by trying different data structures (Hash maps) and targeting
different hardware (GP-GPU). Unfortunately, validation was mainly carried
using pure simulation and testing techniques.

In this work, we take a step back and try to tackle the performance problem
differently. We consider a model-based approach that allows for rigorous
reasoning and formal verification (Section 3). In particular, we rely on the
$\mathcal{S}\text{BIP}$ framework [14, 20] offering a stochastic component-
based modeling formalism and Statistical Model Checking (SMC) engine.
$\mathcal{S}\text{BIP}$ is used along an iterative and systematic design
process which consists of four phases (1) building a parameterized functional
system model, which does not include performance (2) run a corresponding
implementation in order to collect context information and performance
measurements, characterized as probability distribution functions, (3) use
these distributions to create a stochastic timed performance model and (4) use
SMC to verify that the obtained model satisfies requirements of interest.

This approach is applied to verify that the NDN Data Plane Development Kit
(NDN-DPDK) (an effort to develop a high performance forwarder for NDN networks
at the National Institute of Standards and Technology (NIST)) can perform at
high packet forwarding rates (Section 4). We investigate different design
alternatives regarding concurrency (number of threads), system dimensioning
(queues sizes) and deployment (mapping threads to multi-core). Using our
approach, we were able to figure out what are the best design parameters to
achieve higher performances (Section 5). These were taken into account by the
NDN developers at NIST to enhance the ongoing design and implementation. To
the best of our knowledge, this is the first work using formal methods in the
context of the NDN project.

##  2 Named Data Networking

This section describes the NDN protocol and introduces the NDN-DPDK forwarder
being designed and implemented at NIST.

###  2.1 Overview

NDN is a new Internet architecture different from IP. Its core design is
exclusively based on naming contents rather than end points (IP addresses in
the case of IP) and its routing is based on name prefix lookups [13].

The protocol supports three types of packets, namely _Interest, Data_ and
_Nack_. Interests are consumer requests sent to a network and Data packets are
content producers replies. The Nack lets the forwarder know of the network’s
inability to forward Interests further. One of NDN’s advantages is its ability
to cache content (Data) everywhere the Data packet propagates, making the NDN
router stateful. Thus, future Interests are no longer required to fetch the
content from the source, instead Data could be retrieved directly from a
closer node that has a cached copy.

Packets in NDN travel throughout a network as follow: first a client
application sends an Interest with a name prefix that represents the requested
content. Names in NDN are hierarchical (e.g., /YouTube/Alex/video1.mpg denotes
a YouTube video called Video1.mpg by a Youtuber Alex). Then, this packet is
forwarded by the network nodes based on its name prefix. Finally, this
Interest is satisfied with Data by the original source that produced this
content or by intermediate routers that cached it due to previous requests. It
is also crucial to note that consecutive transmissions of Interest packets
with similar name prefix might not lead to the same path each time, but could
rather be forwarded along different paths each time a request is made,
depending on the forwarding strategy in place. This means that the same Data
could originate from different sources (producers or caches).

The NDN forwarding daemon (NFD) [6], has three different data structures:
_Pending Interest Table (PIT), Content Store (CS)_ and _Forwarding Interest
Base (FIB)_. The packet processing, according to the NDN protocol, is as
follows (fig 1):

Figure 1: NDN Data Plane

[4]

  1. 1 –

For Interests, the forwarder, upon receiving an Interest, starts off by
querying the CS for possible copies of the Data, if a CS match is found during
this operation, the cached Data is returned downstream towards the client.
Otherwise, an entry is created in the PIT with its source and destination
faces (communication channels that the forwarder uses for packet forwarding)
for record keeping. Using the PIT, the forwarder determines whether the
Interest is looped in the network by checking a global unique number called
Nonce in the Interest against existing previous PIT entries. If a duplicate
nonce is found the Interest is dropped and a Nack of reason _Duplicate_ is
sent towards the requester. Otherwise, the FIB is queried for a possible next
hop to forward the Interest towards an upstream node; if there is no FIB
match, the Interest is immediately dropped and replied with a Nack of reason
_No Route_.

  2. 2 –

For Data, the forwarder starts off by querying the PIT. If a PIT entry is
found, the Data is sent to downstream nodes listed in the PIT entry, then the
PIT arms a timer to signal the deletion of this entry and a copy of the Data
is immediately stored in the CS for future queries. If no record is found in
the PIT, the Data is considered malicious and discarded.

###  2.2 The NDN-DPDK Forwarder

NDN-DPDK is a forwarder developed at NIST to follow the NDN protocol and to
leverage concurrency. In this paper, we evaluate its capacity to achieve high
throughput using Statistical Model Checking (SMC).

The NDN-DPDK forwarder’s data plane has three stages: input, forwarding, and
output (Fig. 2). Each stage is implemented as one or more threads pinned to
CPU cores, allocated during initialization. Input threads receive packets from
a Network Interface Card (NIC) through faces, decode them, and dispatch them
to forwarding threads. The forwarding thread processes Interest, Data, or Nack
packets according to the NDN protocol. Output threads send packets via faces
then queue them for transmission on their respective NIC.

Figure 2: Diagram of the NDN-DPDK forwarder

During forwarder initialization, each hardware NIC is provided with a large
memory pool to place incoming packets. The input thread continuously polls the
NIC to obtain bursts of $64$ received packets. Then decodes, reassembles
fragmented packets, and drops malformed ones. Then, it dispatches each packet
to the responsible forwarding thread which is determined as follows:  (a) For
an Interest, the input thread computes SipHash of its first two name
components and queries the last 16 bits of the hash value in the Name Dispatch
Table (NDT), a $65536$ entry lookup table configured by the operator, to
select the forwarding thread.  (b) Data and Nack carry a 1-byte field in the
packet header which indicates the forwarding thread that handled the
corresponding Interest. Once identified, Data (or Nack) will be dispatched to
the same one.

The forwarding thread receives packets dispatched by input threads through a
queue. It processes each packet according to the NDN protocol, using two data
structures both implemented as hash tables:  (a) The FIB records where the
content might be available and which forwarding strategy is responsible for
the name prefix.  (b) The PIT-CS Composite Table (PCCT) records which
downstream node requested a piece of content, and also serves as a content
cache; it combines the PIT and CS found in a traditional NDN forwarder.

The output thread retrieves outgoing packets from forwarding threads through a
queue. Packets are fragmented if necessary and queued for transmission on a
NIC. The NIC driver automatically frees the memory used by packets after their
transmission, making it available for newly arrived packets.

##  3 Formal Model-based Approach

In this section, we describe the methodology used in this study which includes
the underlying modeling formalism as well as the associated analysis
technique.

###  3.1 Overview

Our methodology (Fig. 3) is based on a formal model. In order to evaluate a
system’s performance, its model must be faithful, i.e. it must reflect the
real characteristics and behavior of this system. Moreover, to allow for
exhaustive analyses, this model needs to be formally defined and the technique
used for analysis needs to be trustworthy and scalable. Our approach adheres
to these principles in two ways. First, by relying on the
$\mathcal{S}\text{BIP}$ formal framework (introduced below) that encompasses a
stochastic component-based modeling formalism and an SMC engine for analysis
[14]. Second, by providing a method for systematically building formal
stochastic models for verification that combine accurate performance
information with the functional behavior of the system.

Figure 3: Performance evaluation approach for NDN data plane.

This approach takes a functional system model and a set of requirements to
verify. The functional model could be obtained from a high-level specification
or an existing implementation (we use the latter in this paper). The system’s
implementation which could also be obtained by automatic code generation, is
instrumented and used to collect performance measurements regarding the
requirements of interest, e.g. throughput. These measurements are analyzed and
characterized in the form of probability density functions with the help of
statistical techniques such as sensitivity analysis and distribution fitting.
The obtained probability density functions are then introduced in the
functional model using a well defined calibration procedure [19]. The latter
produces a stochastic timed model (when measurements concern time), which will
be analyzed using the SMC engine depicted in fig 4 [17].

Figure 4: SBIP engine [17]

Note that the considered models in this approach or workflow can be
parameterized with respect to different aspects that we want to analyze and
explore. Basically, the defined components types are designed to be
instantiated in different context, e.g. with different probability density
functions thus showing different performance behaviors. While, the model
considered for analysis using SMC is a specific instance for which all the
parameters are fixed, some degree of parameterization is still allowed on the
verified requirements.

###  3.2 Stochastic Component-based Modeling in BIP

BIP (Behavior, Interaction, Priority) is a highly expressive component based
framework for rigorous system design [10]. It allows the construction of
complex, hierarchically structured models from atomic components characterized
by their behavior and their interfaces. Such components are transition systems
enriched with variables. Transitions are used to move from a source to a
destination location. Each time a transition is taken, component variables may
be assigned new values, computed by user-defined C/C++ functions. Composition
of BIP components is expressed by layered application of interactions and
priorities. Interactions express synchronization constraints between actions
of the composed components while priorities are used to filter among possible
interactions e.g. to express scheduling policies.

The stochastic semantics of BIP were initially introduced in [18] and recently
extended for real-time systems in [20]. They enable the definition of

$s_{0}$$s_{1}$$t=0$$p\vartriangleright$$\mathbf{recv}$$[t=p]$$\mathbf{snd}$$[t<p]$$\mathbf{tick}$$t++$$\mathbf{recv}$

Figure 5: A stochastic BIP component; client behavior issuing requests each
time unit $p$.

stochastic components encompassing probabilistic variables updated according
to user-defined probability distributions. The underlying mathematical model
behind this is a Discrete Time Markov Chain. These are modeled as classical
BIP components augmented with probabilistic variables as shown in Fig. 5 and
depicts a client behavior in a client-server setting where the client issues a
request (snd) each p time units. The period p is set probabilistically by
sampling a distribution function ($p\vartriangleright$) given as a parameter
of the model. Time is introduced by explicit tick transitions and waiting is
modeled by exclusive guards on the tick and snd transitions with respect to
time (captured in this example by the variable $t$).

###  3.3 Statistical Model Checking in a Nutshell

Statistical model-checking (SMC) [12, 22] is a formal verification method that
combines simulation with statistical reasoning to provide quantitative answers
on whether a stochastic system satisfies some requirements. It was
successfully used in various domains such as biology [11], communication [8]
and avionics [9]. It has the advantage to be applicable to models and
implementations (provided that they meet specific assumptions) in addition to
capturing rare events. The $\mathcal{S}\text{BIP}$ SMC engine [14] implements
well-known statistical algorithms for stochastic systems verification, namely,
Hypothesis Testing [22], Probability Estimation [12] and Rare Events. In
addition, it provides an automated parameters exploration procedure. The tools
take as inputs a stochastic BIP model, a Linear-time/Metric Temporal Logic
(LTL/MTL) property to check and a set of confidence parameters required by the
statistical test.

##  4 NDN-DPDK Modeling

In this section we present the modeling process of the NDN-DPDK from a
functional to a stochastic timed model for throughput evaluation.

###  4.1 A Parameterized Functional BIP Model

Fig. 6 depicts the BIP model of the NDN-DPDK forwarder introduced in Section 2
which shows its architecture in terms of interacting BIP components that can
easily be matched to the ones in Fig. 2. The presented model is parameterized
with respect to the number of components, their mapping into specific CPU
cores, FIFOs sizes, etc. Due to space limitation, we present in [5] the
behaviors of all the components of the NDN-DPDK forwarder in Fig. 6. It is
worth mentioning that the model is initially purely functional and untimed.
Time is introduced later through the calibration procedure.

Figure 6: A functional BIP model of the NDN-DPDK forwarder

###  4.2 Building the Performance Model

(a) Bloc diagram

(b) BIP model

Figure 7: Considered network topology for the use case

To build the performance model that will be the subject of this analysis, we
consider the network topology shown in Figure 7a.

The latter has a traffic generator client (consumer), a forwarder (NDN-DPDK),
and a traffic generator server (producer), arranged linearly. Fig 7b
corresponds to the BIP model of the topology where the green line indicates
Interest packets’ path from the client to the producer through the forwarder
and the red line indicates Data packets’ path towards the client. Fig 4.2
shows the behavior of the consumer component in the BIP model of the topology
(fig 7b) which is to send Interests at each time interval $\delta$ and receive
Data then count the number of satisfied Interests in packets per second (pps).
Whereas fig 4.2 shows the behavior of the producer component which is to
simply generate and send a Data packet each time an Interest arrives.

$s_{0}$$s_{1}$$s_{2}$$t=0$$\mathbf{recv\\_D}$$[t=\delta]$$\mathbf{send\\_I}$$[t<\delta]$$\mathbf{tick}$$t++$$Sat\\_I++$

figureConsumer Model

$s_{0}$$s_{1}$$s_{2}$$t=0$$\mathbf{tick}$$t++$$\mathbf{recv\\_I}$$\mathbf{gen\\_D}$$\mathbf{send\\_D}$

figureProducer model

The structure of the NDN-DPDK model (Figure 6) calls for four distribution
functions to characterize performance:  a) Interest dispatching latency in
input threads.  b) Data dispatching latency in input threads.  c) Interest
forwarding latency in forwarding threads.  d) Data forwarding latency in
forwarding threads.  Notice that Nack packets are out of the scope of these
experiments. We identified the following factors that can potentially affect
the system’s performance:

  1. 1.

Number of forwarding threads. Having more forwarding threads distributes
workload onto more CPU cores. The cores can compete for the shared L3 cache,
and potentially increase forwarding latency of individual packets.

  2. 2.

Placement of forwarding threads onto Non Uniform Memory Access nodes (NUMA).
Input threads and their memory pools are always placed on the same NUMA node
as the Ethernet adapter whereas the output threads and the forwarding threads
can be moved across the two nodes. If a packet is dispatched to a forwarding
thread on a different node, the forwarding latency is generally higher because
memory access is crossing NUMA boundaries.

  3. 3.

Packet name length measured by the number of its components. A longer name
requires more iterations during table lookups, potentially increasing Interest
forwarding latency.

  4. 4.

Data payload length. Although the Data payloads are never copied, a higher
payload length increases demand for memory bandwidth, thus potentially
increasing latencies.

  5. 5.

Interest sending rate from the client. Higher sending rate requires more
memory bandwidth, thus potentially increasing latencies. It may also lead to
packet loss if queues between input and forwarding threads overflow.

  6. 6.

Number of PIT entries. Although the forwarder’s PIT is a hash table that
normally offers $O(1)$ lookup complexity, a large number of PIT entries
inevitably leads to hash collisions, which could increase forwarding latency.

  7. 7.

Forwarding thread’s queue capacity. the queues are suspected to impact the
overall throughput of the router through packet overflow and loss rates.
However, it does not influence packets individual latencies.

After identifying the factors with potential influence on packet latency, we
instrument the real forwarder to collect latency measurements. Then, perform
statistical analysis to identify which factors are more significant. This
narrows down the number of factors used and associated distribution functions.

####  4.2.1 Forwarder Instrumentation.

Factors 1, 2, 3, 4, 5 and 7 can be controlled by adjusting the forwarder and
traffic generator configuration, while factor 6 is a result of network traffic
and is not in our control. To collect the measurement, we modified the
forwarder to log packets latencies as well as the PIT size after each burst of
packets. We minimized the extra work that input threads and forwarding threads
have to perform to enable instrumentation, leaving the measurement collection
to a separate logging thread or post-processing scripts. It is important to
mention that this task does in fact introduce timing overhead. Therefore, the
values obtained will have a bias (overestimate) that translates into
additional latency but the trends observed remain valid.

We conducted the experiment on a Supermicro server equipped with two Intel
E5-2680V2 processors, $512$ GB DDR4 memory in two channels, and four Mellanox
ConnectX-5 100 Gbit/s Ethernet adapters. The hardware resources are evenly
divided into two NUMA nodes. To create the topology in Fig. 7b, we connected
two QSFP28 passive copper cables to connect the four Ethernet adapters and
form two point-to-point links. All forwarders and traffic generator processes
were allocated with separate hardware resources and could only communicate
over Ethernet adapters.

In each experiment, the consumer transmitted either at sending intervals of
one Interest per $700$ ns or per $500$ ns under 255 different name prefixes.
There were 255 FIB entries registered in the NDN-DPDK forwarder at runtime
(one for each name prefix used by the consumer), all of which pointed to the
producer node. The producer would reply to every Interest with a Data packet
of the same name. The forwarder’s logging thread was configured to discard the
first $67\,108\,864$ samples (either latency trace or PIT size) during warm-up
period, and then collect the next $16\,777\,216$ samples and ignore the cool
down session. Each experiment represents about 4 million Interest-Data
exchanges.

Table 1: Factors used. NUMA mapping is described below. Factors | forwarding threads | Name length | Payload length | Sending intervals
---|---|---|---|---
Values | {1, 2, 3, 4, 5, 6, 7, 8} | {3, 7, 13} | {0, 300, 600, 900, 1200} | {500 ns, 700 ns}

We repeated the experiment using different combinations of the factors in
Table 1 and the following NUMA arrangements:

  * (P1) Client and server faces and forwarding threads are all on the same NUMA,

  * (P2) Client face and forwarding threads on one NUMA, server face on the other,

  * (P3) Client face on one NUMA, forwarding threads and server face on the other,

  * (P4) Client face and server face on one NUMA, forwarding threads on the other.

In P1, packet latency is expected to be the smallest because all processes are
placed on the same NUMA therefore, no inter-socket communication and no
overhead are introduced. In P4, both Interests and Data packets are crossing
NUMA boundaries twice since the forwarding threads are pinned to one NUMA
whereas the client and the server faces, connected to the Ethernet adapters,
reside on another. This is suspected to increase packet latency tremendously
as opposed to P1, P2 and P3. These suspicions predict that placement P1 is the
best case scenario and placement P4 is obviously the worst. However, we aim at
getting more insight and confidence through quantitative formal analysis. This
will provide a recommendation as to which placement is better suited based on
the remaining parameters combinations.

####  4.2.2 Model Fitting.

Before calibrating our functional BIP model with multiple distinctive
probability distributions representing each combination of the factors, we
choose to reduce the number of used distributions by performing a sensitivity
analysis. This analysis examines the impact of several factors on the response
(packet latency) and discovers the ones that are more important. In this
paper, we use DataPlot [7] to produce the Main Effect Plot (Fig. 8) for
factors 1 to 5.

Figure 8: Main Effects Plot for Interest and Data packets

The plot shows steeper line slopes for the packet type (packet type is not a
factor. We intend to show how the NDN-DPDK forwarder processes both Interest
and Data differently) as well as factors (1), (2), (3), and (5) which
indicates a greater magnitude of the main effect on the latency. However, it
shows almost a horizontal line for factor 4 inducing an insignificant impact
on the latency. The latter is explained by the fact that the forwarder
processes packet names (headers) only and doesn’t read Data payloads. As for
the PIT size (factor 6), it is expected to heavily increase packet latency
when it is full. However, because this table’s implementation is optimized for
high performance and entries are continuously removed when Data packets arrive
(PIT entries being satisfied), we confirmed through a correlation analysis
that we can ignore this factor’s impact.

Based on the analysis above, we build distribution functions for each of the
factors that have greater impacts on packet latency in this study. These
factors are:  (1) the number of forwarding threads,  (2) NUMA placement,  (3)
packet name size (header),  (5) sending rate and,  (7) FIFO capacity (FIFO
impacts the loss rates and not individual packet latency.  We refer the reader
to [5] to understand how we obtained the probability distributions for these
factors.

####  4.2.3 Probability distribution fitting.

In order to determine a best fit distribution to a data set we follow the
general procedure below using DataPlot [7]:

  1. 1.

Determine if a normal distribution fits the data via a histogram or a normal
probability plot or a normal probability plot correlation coefficient (ppcc);

  2. 2.

If the normal probability plot is not linear ”enough” (that is, the normal
probability plot correlation coefficient is not close enough to 1), we check
the data against popular distributional families (e.g. Weibull ppcc plot,
Gamma ppcc plot, Lognormal ppcc plot, etc);

  3. 3.

If none of the distributional families provide a ppcc value which is close
”enough” to 1, then we apply a box-cox transformation to determine the best
power that will make the transformed data normal, then we note the best power
(lambda);

  4. 4.

Confirm the normality of the transformed data by a histogram, a normal
probability plot or by a normal probability plot correlation coefficient
(ppcc) [3];

  5. 5.

Identify the best location and scale parameter estimates for the transformed
data using the transformed data’s mean $\bar{y}$ and standard deviation
$\bar{s}$;

  6. 6.

Generate the normal probability N(0,1) of a random sample (Z) of size n;

  7. 7.

Transform the N(0,1) random sample to a N($\bar{y}$,$\bar{s}$) random sample
of the transformed data;

  8. 8.

Transform $ZT$ the random sample to the actual data random sample [1];

  9. 9.

Finally, reaffirm the similarity between $Y$ and $\bar{Y}$ by using a
Bihistogram for example.

####  4.2.4 Model Calibration.

Calibration is a well defined model transformation that transforms functional
components into stochastic timed ones [16]. In this section, we use the
probability distributions obtained to calibrate the functional BIP model of
the NDN-DPDK forwarder shown in Fig. 6.

Figs. 9, 4.2.4 and 4.2.4 respectively show the calibrated behaviors of a
forwarding thread, an input thread customized to send traffic towards two
forwarding threads (fwd=1, fwd=2) and an output thread. The forwarding time of
Interest and Data packets is modeled using two probability distributions,
$f_{I}$ and $f_{D}$ respectively. Whereas, the input threads’ processing time
of packets is modeled with the probability distribution $f_{p}$ which refers
to either Interests or Data depending on where the component is located.

In the next section, we perform SMC on the calibrated model of the NDN-DPDK
forwarder and explain the results.

$f_{0}$$f_{1}$$f_{2}$$f_{3}$$t=0$$\mathbf{fetch}$$\mathbf{tick}$$[pkt=D]$$f_{D}\vartriangleright$$fwd_{D}()$$[pkt=I]$$f_{I}\vartriangleright$$fwd_{I}()$$[t=f_{D}]$$\mathbf{fw\\_D}$$[t<f_{D}]$$\mathbf{tick}$$t++$$[t=f_{I}]$$\mathbf{fw\\_I}$$[t<f_{I}]$$\mathbf{tick}$$t++$

Figure 9: Forwarding thread; forwarding time of Interest and Data is modeled
using two distributions, resp. $f_{I}$, $f_{D}$.

$f_{0}$$f_{1}$$f_{2}$$f_{3}$$t=0$$\mathbf{recv}$$\mathbf{tick}$$t++$$[fwd=1]$$fp\vartriangleright$$in()$$[fwd=2]$$fp\vartriangleright$$in()$$[t=fp]$$\mathbf{to\\_fwd1}$$[t<fp]$$\mathbf{tick}$$t++$$[t=fp]$$\mathbf{to\\_fwd2}$$[t<fp]$$\mathbf{tick}$$t++$

figureInput thread: processing time of packets is modeled using the
distribution $f_{p}$ (p refers to Interests or data

$s_{0}$$s_{1}$$t=0$$\mathbf{recv\\_pkt}$$\mathbf{tick}$$t++$$\mathbf{send\\_pkt}$$\mathbf{tick}$$t++$

figureOutput thread mode

##  5 Performance Analysis using SMC

###  5.1 Experimental Settings

We run the SMC tests using the probability estimation algorithm (PE) with
precision parameters $\alpha=0.1$ and $\delta=0.1$. Each test is configured
with a different combination of values for the factors previously presented.
And each execution of a test with a single set of parameters generates a
single trace. The property evaluated with the SMC engine is: _Estimate the
probability that all the issued Interests are satisfied, i.e. a Data is
obtained in return for each Interest_. Thus, if PE concludes that the
probability is 100 %, then the verdict is positive.

###  5.2 Analyses Results

####  5.2.1 Queues Dimensioning.

First, we explore the impact of sizing forwarding threads queues. Each
forwarding thread has an input queue. Initially, we consider a model with a
single forwarding thread and vary its queue capacity with $128$, $1024$ or
$4096$ (in packets). Then set the client’s sending rate to: $10^{5}$ packets
per second (pps), $10^{6}$ pps or $10^{7}$ pps. The results are shown in Fig.
17a. The Y-axis represents the Interest satisfaction rate such that 100 %
(resp. 0 %) indicates no loss (resp. 100 % loss) and the x axis represents the
queue capacity under different sending rates.

(a) One Forwarding thread with different sending rates.

(b) Many Forwarding threads with a sending rate set to $10^{6}$ pps.

Figure 10: Exploration results of the Forwarding threads queues sizes.

Fig. 17a indicates that at $10^{5}$ pps (blue), the Interest satisfaction rate
is 100 %. This means that the forwarder (with one forwarding thread) is
capable of handling all packets at this sending rate ($10^{5}$ pps of packet
size $1500$ bytes is equivalent to $1.2$ Gbps), under any queue size. However,
under a faster sender rate (where a single forwarder shows signs of packet
loss) we unexpectedly observed a better Interest satisfaction rate with a
smaller queue (Q=$128$). After a thorough investigation of the real
implementation, we found out that the queues don’t have proper management in
terms of insertion and eviction policies that would give priority to Data over
Interest packets. In the absence of such policy, more Interests would be
queued while Data packets would be dropped resulting in Interests not being
satisfied, thus lower performance (Interest satisfaction rate). _It is thus
advised for the final implementation of the NDN-DPDK forwarder, to use a queue
capacity smaller than $128$ packets when the forwarder has a single forwarding
thread and packets are sent at a fast rate._

Similarly, we explore whether this observation remains true with more
forwarding threads. In order to do that, we run SMC again on eight different
models each with a different number of forwarding threads ($1$ to $8$) under a
sending rate of $10^{6}$ pps ($1$ Interest per $1$ us) where a loss rate was
observed in Fig. 17a. Then, we experimented with two queue capacities, namely
$128$ and $4096$ packets. The results are reported in Fig. 17b. The x Axis
represents the number of forwarding threads while the y axis depicts the
Interest satisfaction rate.

We observe that the queue size matters mainly in the case of a model with one
and two forwarding threads. In fact, for a two threads model, a bigger queue
size is preferred to maximize the performance, unlike when a single thread is
used. As for the other six models, both sizes achieve almost 100 % Interest
satisfaction. This is due to the fact that three forwarding threads or more
are capable of splitting the workload at $10^{6}$ pps and can pull enough
packets from each queue with a minimum loss rate of 0.02 % . _This result
stresses that, to avoid being concerned about a proper queue size, more
threads are needed for handling a faster sending rate with minimum Interest
loss._

####  5.2.2 NUMA placement, number of forwarding threads and packet name
length.

Another aspect to explore, is the impact of mapping the forwarding threads
and/or NDN Faces to the two NUMA nodes (0, 1) under different sending rates
and for multiple name lengths where Face 0 exchanges packets with the client
and Face 1 with the server. To do that, we consider the four NUMA arrangements
(P1), (P2), (P3) and (P4) in section 4 as well as the factors in Table 1 in
the SMC analysis.

In Figs. 23 to 23, each row represents experiments with similar packet name
lengths {small=3, medium=7, large=13} and a queue capacity of 4096. The right-
hand column indicates results for a faster sending rate of $2*10^{6}$ pps (500
ns interval) while the left-hand one shows results for a slower sending rate
of $1.42*10^{6}$ pps (700 ns interval). The six figures includes four curves
where each corresponds to the four NUMA arrangement options: P1 to P4.

Figure 11: small names, 700 ns

Figure 12: small names, 500 ns

Figure 13: medium names, 700 ns

Figure 14: medium names, 500 ns

Figure 15: large names, 700 ns

Figure 16: large names, 500 ns

The six Figs. 23 to 23 show that Interest satisfaction rates scale up with the
increase of forwarding threads then reach a saturation plateau where adding
more threads can no longer improve the performances. Furthermore, with fewer
forwarding threads, the loss rate is unavoidable and exceeds 80 %. This is
because the sending rate is faster than the forwarding threads processing
capabilities causing their FIFO queues to saturate and start dropping packets
frequently. However, under a slower sending rate and packets with small,
medium and large name lengths (3, 7, 13), Figs. 23, 23 and 23 show that a
maximum satisfaction rate of over 90 % is achievable with only five forwarding
threads. Whereas when the client is generating packets faster at 2 Mpps, a
saturation plateau of over $90$ % is reached at six threads or more for small
and medium names (Figs. 23 and 23) and a plateau of slightly over $70$ %, with
five threads, for larger names (Fig. 23). Also, Figs. 23 and 23 demonstrate
that placing all processes (threads and faces) on a single NUMA (placement P1)
outperforms the other three options. This observation is explained by the
absence of inter-socket communication thus less timing overhead added such as
in the case of the purple plot where packets are crossing NUMA boundaries
twice from Face 0 to the forwarding threads then through Face 1 and back
(placement P4).

Figs. 23 and 23 show the impact of increasing the sending rate on packets with
smaller names. In this case, it is preferred to also position all the
processes on one NUMA such as the case of the yellow plot of the P1 series
because NUMA boundary crossing usually downgrades the performance. In fact,
the difference between no NUMA crossing and the double crossing (yellow and
purple series respectively) is approximately 30 % loss rate with more than
five threads. The second best option P2 which is placing the forwarding
threads on the NUMA receiving Interest packets with Face 0 (NUMA hosting the
Ethernet adapter that receives Interests from the Client). However, when the
number of threads is not in the saturation zone and the threads get overworked
and start to loose packets, it is recommended to opt for placement P3. _Based
on these results, we recommend that for small to medium names, to use a
maximum of eight threads but no less than five arranged as in placement P1 for
optimum performances under a slower or a faster sending rate_.

With a larger name however, Fig. 23 depicts an unexpected behaviour when using
three threads or less. In this case, placing the forwarding threads on the
same NUMA as Face 1 (which is the Ethernet adapter connected to the server and
receives Data packets), surpasses the other three options. Our explanation is
that since forwarding threads take longer times to process incoming packets
due to their longer name and timely lookup, particularly for Interests as they
are searched by names inside the two tables (PCCT and FIB) rather than a token
such as the case for Data packets. Placing the forwarding threads with the
Data receiving Ethernet adapter connected to Face 1, has the potential to
yield better results by quickly processing packets after a quick token search
especially when the workload is bigger than the threads’ processing capacity.
When the sending rate is increased, the same results are observed in Fig. 23
for a similar name length but with a decrease in performance. _Thus, we
recommend for larger names to use NUMA arrangement P3 only when the number of
forwarding threads is less than three regardless of the sending rate (not
advised due to high loss rate)._

##  6 Lessons learned and future work

###  6.1 Experimental Settings

We run the SMC tests using the probability estimation algorithm (PE) with
precision parameters $\alpha=0.1$ and $\delta=0.1$. Each test is configured
with a different combination of values for the factors previously presented.
And each execution of a test with a single set of parameters generates a
single trace. The property evaluated with the SMC engine is: _Estimate the
probability that all the issued Interests are satisfied, i.e. a Data is
obtained in return for each Interest_. Thus, if PE concludes that the
probability is 100 %, then the verdict is positive.

###  6.2 Analyses Results

####  6.2.1 Queues Dimensioning.

First, we explore the impact of sizing forwarding threads queues. Each
forwarding thread has an input queue. Initially, we consider a model with a
single forwarding thread and vary its queue capacity with $128$, $1024$ or
$4096$ (in packets). Then set the client’s sending rate to: $10^{5}$ packets
per second (pps), $10^{6}$ pps or $10^{7}$ pps. The results are shown in Fig.
17a. The Y-axis represents the Interest satisfaction rate such that 100 %
(resp. 0 %) indicates no loss (resp. 100 % loss) and the x axis represents the
queue capacity under different sending rates.

(a) One Forwarding thread with different sending rates.

(b) Many Forwarding threads with a sending rate set to $10^{6}$ pps.

Figure 17: Exploration results of the Forwarding threads queues sizes.

Fig. 17a indicates that at $10^{5}$ pps (blue), the Interest satisfaction rate
is 100 %. This means that the forwarder (with one forwarding thread) is
capable of handling all packets at this sending rate ($10^{5}$ pps of packet
size $1500$ bytes is equivalent to $1.2$ Gbps), under any queue size. However,
under a faster sender rate (where a single forwarder shows signs of packet
loss) we unexpectedly observed a better Interest satisfaction rate with a
smaller queue (Q=$128$). After a thorough investigation of the real
implementation, we found out that the queues don’t have proper management in
terms of insertion and eviction policies that would give priority to Data over
Interest packets. In the absence of such policy, more Interests would be
queued while Data packets would be dropped resulting in Interests not being
satisfied, thus lower performance (Interest satisfaction rate). _It is thus
advised for the final implementation of the NDN-DPDK forwarder, to use a queue
capacity smaller than $128$ packets when the forwarder has a single forwarding
thread and packets are sent at a fast rate._

Similarly, we explore whether this observation remains true with more
forwarding threads. In order to do that, we run SMC again on eight different
models each with a different number of forwarding threads ($1$ to $8$) under a
sending rate of $10^{6}$ pps ($1$ Interest per $1$ us) where a loss rate was
observed in Fig. 17a. Then, we experimented with two queue capacities, namely
$128$ and $4096$ packets. The results are reported in Fig. 17b. The x Axis
represents the number of forwarding threads while the y axis depicts the
Interest satisfaction rate.

We observe that the queue size matters mainly in the case of a model with one
and two forwarding threads. In fact, for a two threads model, a bigger queue
size is preferred to maximize the performance, unlike when a single thread is
used. As for the other six models, both sizes achieve almost 100 % Interest
satisfaction. This is due to the fact that three forwarding threads or more
are capable of splitting the workload at $10^{6}$ pps and can pull enough
packets from each queue with a minimum loss rate of 0.02 % . _This result
stresses that, to avoid being concerned about a proper queue size, more
threads are needed for handling a faster sending rate with minimum Interest
loss._

####  6.2.2 NUMA placement, number of forwarding threads and packet name
length.

Another aspect to explore, is the impact of mapping the forwarding threads
and/or NDN Faces to the two NUMA nodes (0, 1) under different sending rates
and for multiple name lengths where Face 0 exchanges packets with the client
and Face 1 with the server. To do that, we consider the four NUMA arrangements
(P1), (P2), (P3) and (P4) in section 4 as well as the factors in Table 1 in
the SMC analysis.

In Figs. 23 to 23, each row represents experiments with similar packet name
lengths {small=3, medium=7, large=13} and a queue capacity of 4096. The right-
hand column indicates results for a faster sending rate of $2*10^{6}$ pps (500
ns interval) while the left-hand one shows results for a slower sending rate
of $1.42*10^{6}$ pps (700 ns interval). The six figures includes four curves
where each corresponds to the four NUMA arrangement options: P1 to P4.

Figure 18: small names, 700 ns

Figure 19: small names, 500 ns

Figure 20: medium names, 700 ns

Figure 21: medium names, 500 ns

Figure 22: large names, 700 ns

Figure 23: large names, 500 ns

The six Figs. 23 to 23 show that Interest satisfaction rates scale up with the
increase of forwarding threads then reach a saturation plateau where adding
more threads can no longer improve the performances. Furthermore, with fewer
forwarding threads, the loss rate is unavoidable and exceeds 80 %. This is
because the sending rate is faster than the forwarding threads processing
capabilities causing their FIFO queues to saturate and start dropping packets
frequently. However, under a slower sending rate and packets with small,
medium and large name lengths (3, 7, 13), Figs. 23, 23 and 23 show that a
maximum satisfaction rate of over 90 % is achievable with only five forwarding
threads. Whereas when the client is generating packets faster at 2 Mpps, a
saturation plateau of over $90$ % is reached at six threads or more for small
and medium names (Figs. 23 and 23) and a plateau of slightly over $70$ %, with
five threads, for larger names (Fig. 23). Also, Figs. 23 and 23 demonstrate
that placing all processes (threads and faces) on a single NUMA (placement P1)
outperforms the other three options. This observation is explained by the
absence of inter-socket communication thus less timing overhead added such as
in the case of the purple plot where packets are crossing NUMA boundaries
twice from Face 0 to the forwarding threads then through Face 1 and back
(placement P4).

Figs. 23 and 23 show the impact of increasing the sending rate on packets with
smaller names. In this case, it is preferred to also position all the
processes on one NUMA such as the case of the yellow plot of the P1 series
because NUMA boundary crossing usually downgrades the performance. In fact,
the difference between no NUMA crossing and the double crossing (yellow and
purple series respectively) is approximately 30 % loss rate with more than
five threads. The second best option P2 which is placing the forwarding
threads on the NUMA receiving Interest packets with Face 0 (NUMA hosting the
Ethernet adapter that receives Interests from the Client). However, when the
number of threads is not in the saturation zone and the threads get overworked
and start to loose packets, it is recommended to opt for placement P3. _Based
on these results, we recommend that for small to medium names, to use a
maximum of eight threads but no less than five arranged as in placement P1 for
optimum performances under a slower or a faster sending rate_.

With a larger name however, Fig. 23 depicts an unexpected behaviour when using
three threads or less. In this case, placing the forwarding threads on the
same NUMA as Face 1 (which is the Ethernet adapter connected to the server and
receives Data packets), surpasses the other three options. Our explanation is
that since forwarding threads take longer times to process incoming packets
due to their longer name and timely lookup, particularly for Interests as they
are searched by names inside the two tables (PCCT and FIB) rather than a token
such as the case for Data packets. Placing the forwarding threads with the
Data receiving Ethernet adapter connected to Face 1, has the potential to
yield better results by quickly processing packets after a quick token search
especially when the workload is bigger than the threads’ processing capacity.
When the sending rate is increased, the same results are observed in Fig. 23
for a similar name length but with a decrease in performance. _Thus, we
recommend for larger names to use NUMA arrangement P3 only when the number of
forwarding threads is less than three regardless of the sending rate (not
advised due to high loss rate)._

#####

## References

  * [1] Box cox normality plot, https://www.itl.nist.gov/div898/software/dataplot/refman1/auxillar/boxcoxno.htm
  * [2] Brown, b. (2019). cisco, ucla & more launch named data networking consortium. [online] network world., https://www.networkworld.com/article/2602109/ucla-cisco-more-join-forces-to-replace-tcpip.html
  * [3] Filliben, j. j. (february 1975), the probability plot correlation coefficient test for normality, technometrics, pp. 111-117
  * [4] L. zhang et al., “named data networking,” ndn, tech. rep. ndn-0001, no. october, 2010.
  * [5] NDN Performance evaluation using SMC (technical report). Tech. rep., http://www-verimag.imag.fr/~nouri/ndn-tech-report.pdf
  * [6] NFD Developer’s Guide. Tech. rep., http://named-data.net/techreports.html
  * [7] Nist.gov. Dataplot homepage, https://www.itl.nist.gov/div898/software/dataplot/homepage.htm
  * [8] Basu, A., Bensalem, S., Bozga, M., Caillaud, B., Delahaye, B., Legay, A.: Statistical Abstraction and Model-Checking of Large Heterogeneous Systems. In: Forum for fundamental research on theory, FORTE’10. LNCS, vol. 6117, pp. 32–46. Springer
  * [9] Basu, A., Bensalem, S., Bozga, M., Delahaye, B., Legay, A., Siffakis, E.: Verification of an AFDX infrastructure using simulations and probabilities. In: Runtime Verification, RV’10. LNCS, vol. 6418. Springer (2010)
  * [10] Basu, A., Bozga, M., Sifakis, J.: Modeling heterogeneous real-time components in bip. In: Proceedings of the Fourth IEEE International Conference on Software Engineering and Formal Methods. pp. 3–12. SEFM’06, IEEE Computer Society, Washington, DC, USA (2006)
  * [11] David, A., Larsen, K.G., Legay, A., Mikucionis, M., Poulsen, D.B., Sedwards, S.: Statistical model checking for biological systems. Int. J. Softw. Tools Technol. Transf. 17(3), 351–367 (Jun 2015)
  * [12] Hérault, T., Lassaigne, R., Magniette, F., Peyronnet, S.: Approximate Probabilistic Model Checking. In: International Conference on Verification, Model Checking, and Abstract Interpretation, VMCAI’04. pp. 73–84 (January 2004)
  * [13] Jacobson, V., Smetters, D.K., Thornton, J.D., Plass, M.F., Briggs, N.H., Braynard, R.L.: Networking Named Content (2009), https://named-data.net/wp-content/uploads/Jacob.pdf
  * [14] Mediouni, B.L., Nouri, A., Bozga, M., Dellabani, M., Legay, A., Bensalem, S.: $\mathcal{S}\text{BIP}$ 2.0: Statistical model checking stochastic real-time systems. In: Automated Technology for Verification and Analysis - 16th International Symposium, ATVA 2018, Los Angeles, CA, USA, October 7-10, 2018, Proceedings. pp. 536–542 (2018)
  * [15] Named data networking project. Tech. rep., USA (Oct 2010), http://named-data.net/techreport/TR001ndn-proj.pdf
  * [16] Nouri, A.: Rigorous System-level Modeling and Performance Evaluation for Embedded System Design. Ph.D. thesis, Grenoble Alpes University, France (2015)
  * [17] Nouri, A.: Bip-smc : A statistical model checking engine for the bip framework (Dec 2017), http://www-verimag.imag.fr/BIP-SMC-A-Statistical-Model-Checking.html
  * [18] Nouri, A., Bensalem, S., Bozga, M., Delahaye, B., Jegourel, C., Legay, A.: Statistical model checking QoS properties of systems with SBIP. Int. J. Softw. Tools Technol. Transf. (STTT) 17(2), 171–185 (April 2015)
  * [19] Nouri, A., Bozga, M., Molnos, A., Legay, A., Bensalem, S.: _ASTROLABE_ : A rigorous approach for system-level performance modeling and analysis. ACM Trans. Embedded Comput. Syst. 15(2), 31:1–31:26 (2016)
  * [20] Nouri, A., Mediouni, B.L., Bozga, M., Combaz, J., Bensalem, S., Legay, A.: Performance evaluation of stochastic real-time systems with the sbip framework. International Journal of Critical Computer-Based Systems 8(3-4), 340–370 (2018)
  * [21] Xylomenos, G., Ververidis, C.N., Siris, V.A., Fotiou, N., Tsilopoulos, C., Vasilakos, X., Katsaros, K.V., Polyzos, G.C.: A survey of information-centric networking research. IEEE Communications Surveys Tutorials 16(2), 1024–1049 (2014)
  * [22] Younes, H.L.S.: Verification and Planning for Stochastic Processes with Asynchronous Events. Ph.D. thesis, Carnegie Mellon (2005)
  * [23] Zhang, L., Afanasyev, A., Burke, J., Jacobson, V., claffy, k., Crowley, P., Papadopoulos, C., Wang, L., Zhang, B.: Named data networking. SIGCOMM Comput. Commun. Rev. 44(3), 66–73 (Jul 2014)