Amar Abane
email: amar.abane@inria.fr

Paul Muhlethaler
email: paul.muhlethaler@inria.fr

Samia Bouzefrane
email: samia.bouzefrane@lecnam.net

Modeling and Improving Named Data Networking over IEEE 802.15.4

Keywords: NDN, ICN, IoT, IEEE 802.15.4, Mathematical Model, CSMA, Low-power wireless

Named Data Networking (NDN) is a promising architecture that aims to natively satisfy emerging applications such as the Internet of Things (IoT). Therefore, enabling NDN in realworld IoT deployments is becoming essential in order to benefit from Information Centric Networking (ICN) features. To design realistic NDN-based communication solutions for IoT, revisiting mainstream technologies such as low-power wireless standards may be the key. In this paper, we explore NDN forwarding over IEEE 802.15.4 following two steps. First, we mathematically model a broadcast-based forwarding strategy for NDN over constrained networks with the IEEE 802.15.4 technology in mind. The model estimates the number of frames transmitted and the mean round-trip time per request, under content popularity considerations. Second, based on mathematical and experimental observations of the broadcast-based forwarding at network level, we elaborate Named-Data Carrier-Sense Multiple Access (ND-CSMA), an adaptation of the Carrier-Sense Multiple Access (CSMA) algorithm used in IEEE 802.15.4.

Results show that adaptations such as ND-CSMA may be reasonably envisioned to improve NDN efficiency with current IoT technologies.

I. INTRODUCTION

IoT systems are built with battery-powered devices that have limited computational power and memory capacity. These devices are often mobile and massively deployed through houses, fields of crops, etc. Device interconnection is achieved with low-rate wireless technologies that allow communication with a satisfactory data rate, payload size and distance range, all with a long-lasting battery lifetime. One of these technologies, the IEEE 802.15.4 [START_REF]Ieee standard for information technology-telecommunications and information exchange between systems local and metropolitan area networks-specific requirements -part 11: Wireless lan medium access control (mac) and physical layer (phy) specifications[END_REF], greatly contributes to make IoT possible. Sensors and wireless equipment use 802.15.4capable modules to exchange data in most IoT systems. The wide adoption of this standard proves its suitability for the IoT.

It was then necessary to create 6LoWPAN [START_REF] Montenegro | Transmission of IPv6 Packets over IEEE 802.15.4 Networks[END_REF] to support IPv6 communication over the IEEE 802.15.4 standard, and the Constrained Application Protocol (CoAP) [START_REF] Shelby | The Constrained Application Protocol (CoAP)[END_REF] to handle data exchange in constrained environments. More generally, Internet Engineering Task Force (IETF) Working Groups are devoting great efforts to adapt the TCP/IP stack to suit IoT systems. These efforts have extended the TCP/IP stack and created various other protocols acting as middleware between the application layer and the network layer. Nevertheless, the limits of IP-based protocols are still a reality [START_REF] Shang | Challenges in IoT networking via TCP/IP architecture[END_REF]. For example, host-based IP addressing can not express device identity, data naming and content security within the same network layer protocol. Important requirements such as caching, mobility and multicast further complicate the IoT support. Therefore, IP-based solutions support the IoT at application level using the Representational State Transfer (REST) architecture, which indicates that the TCP/IP stack has reached its limit to support these new requirements. Moreover, most of these solutions are converging to the principles of the Information Centric Networking (ICN) [START_REF] Ahlgren | A Survey of Information-Centric Networking[END_REF] paradigm; by considering data names and object-based security as design principles.

Unlike host-based networking, Named Data Networking (NDN) [START_REF] Zhang | Named Data Networking[END_REF] operates with named content. In NDN, every piece of content is identified by a unique name which applications use to request data. Content names are independent from the host location; that is, each content item keeps the same name everywhere at producers, caches and consumers. This feature is combined with cryptographic operations to provide self-secured packets. Since packets are independent from their source and destination hosts, NDN natively supports in-network caching. NDN is an evolved L3 protocol, as it includes some of the relevant operations traditionally provided by higher network layers such as security and flow control. With these features, NDN can match most IoT applications that focus on the content regardless of where it is located or how it is transported. Current efforts regarding NDN for the IoT consist in supporting applications in a simpler, more efficient, and more elegant way [START_REF] Shang | Named Data Networking of Things[END_REF]. Lightweight design in constrained wireless networks can be considered as a major step towards enabling NDN in IoT. However, in NDN's journey to real-world IoT deployments, we believe that adaptations of current IoT-related technologies will be required. One of these adaptations concerns link-layer technologies, and particularly the IEEE 802.15.4, as investigated in this paper.

In this context, we first model a broadcast-based NDN forwarding strategy for wireless constrained networks. The model estimates the average number of frames transmitted per request (i.e., Interest-Data exchange) and the mean roundtrip time (RTT) under content popularity considerations. After that, based on mathematical and experimental observations, we consider an adaptation of the Carrier-Sense Multiple Access (CSMA) algorithm to achieve a trade-off between the Interest satisfaction, the number of transmissions, and the round-trip time. The designed adaptation, Named-Data CSMA (ND-CSMA), is derived from the CSMA algorithm to provide a better support for the broadcast-based forwarding approach.

The rest of the paper is organized as follows. Section II briefly reports on some ICN/NDN models formulated so far and some NDN-802.15.4 related studies. Section III gives an overview of the basic NDN forwarding in wired networks. In Section IV, the deployment of NDN in wireless networks is discussed through different approaches. Section V details the wireless forwarding strategy considered in this study, and Section VI presents the model formulation and evaluation. Section VII describes and evaluates the proposed ND-CSMA scheme. Section VIII concludes the paper with some future perspectives.

II. RELATED WORK

Most of the models on ICN/NDN are conducted exclusively around caching, such as cache deployment, cache decision and cache replacement. Some studies manage to model ICN/NDN transport and routing performance, with comparison to TCP/IP [START_REF] Carofiglio | From content delivery today to information centric networking[END_REF].

Only few analytical models consider the interaction between caching and transport in ICN/NDN protocols. Furthermore, these models exclusively consider wired networks [START_REF] Wang | Modeling in-network caching and bandwidth sharing performance in information-centric networking[END_REF]- [START_REF] Udugama | Analytical characterisation of multi-path content delivery in content centric networks[END_REF]. In the cache modeling area, some studies have been presented in the context of Web caching with ICN under the Least Recently Used (LRU) replacement policy. A noticeable work [START_REF] Carofiglio | Modeling data transfer in content-centric networking[END_REF] is used as a basis in our model to compute cache miss rate probabilities.

To the best of our knowledge, no model has been explicitly formulated on NDN in wireless networks with cache consideration, whether for constrained or traditional wireless networks such as MANETs.

We also believe that no proposals do exist for adapting the CSMA algorithm to improve wireless forwarding with ICN/NDN.

Concerning real-world deployments, an NDN integration with IEEE 802.15.4 (ZigBee) is proposed in [START_REF] Abane | Ndn-overzigbee: A zigbee support for named data networking[END_REF] and other aspects of IEEE 802.15.4 have been investigated before, such as addressing and name-to-address mapping [START_REF] Kietzmann | The Need for a Name to MAC Address Mapping in NDN: Towards Quantifying the Resource Gain[END_REF].

III. NAMED DATA NETWORKING

NDN protocol operates using Interest and Data packets that carry content names instead of source and destination addresses. To forward packets based on names, each node maintains two data structures: the Forwarding Information Base (FIB) and the Pending Interest Table (PIT). Optionally, a Content Store (CS) is used to provide in-network caching.

In wired networks, a typical NDN communication operates according to the following steps (see Figure 1):

1) The communication is initiated by the consumer that requests a content item by sending an Interest carrying the corresponding name (e.g. /build-ing1/room1/temperature). of the Interest(s) until the consumer(s). When the Data reaches a router, it is forwarded to every interface from which a corresponding Interest was received. Then, the router discards the PIT entry and caches a copy of the Data in its CS. 7) When a Data packet is received and no matching Interest is present in the PIT, its considered unsolicited by the node and the packet is discarded.

IV. NAMED DATA NETWORKING IN WIRELESS NETWORKS Some wireless network features, particularly in ad hoc networks, can be intuitively related to ICN/NDN principles. Therefore, the following benefits can be expected from a deployment of NDN in wireless environments [START_REF] Amadeo | Content-centric wireless networking: A survey[END_REF]- [START_REF] Amadeo | Named data networking: A natural design for data collection in wireless sensor networks[END_REF]. First, with a connection-less and consumer-driven communication model, NDN can cope well with intermittent connectivity and dynamic topologies of wireless environments. Moreover, satisfactory data delivery can be expected thanks to native caching and location-independent data security. Second, NDN does not require any logical identification of nodes, since content items are retrieved using their names. This is more natural regarding current applications where the content (i.e., its name) is more relevant than the host address. Third, in emerging applications, content is usually published from servers (e.g., news, weather information) or it can be shared between groups of consumers (e.g., road traffic and safety) or it can be created by one user and published into a group of consumers (e.g., social media). These communication scenarios can be efficiently supported with multicast and broadcast data delivery. With Interest aggregation and Data caching, NDN natively supports multicast and has a powerful data dissemination capability. This helps NDN to take advantage of the broadcast nature of wireless and support these required communication patterns.

To design an NDN-based wireless network, an overlay of NDN on top of IP should be avoided for three main reasons [START_REF] Amadeo | Content-centric wireless networking: A survey[END_REF]: First, discover and maintain end-to-end routes between nodes require recurrent communications; which may lead to high control overhead due to the multiple protocols involved. Second, using IP as the underlying protocol forces point-topoint communications, without exploiting broadcast, multicast, and in-network caching. Third, the protocol stack becomes larger, requiring more device resources which is already a constraint in the IP stack itself.

Therefore, the most efficient approach for deploying NDN in wireless networks is to run NDN directly over the link layer.

However, the forwarding decision in wireless networks is slightly different than in wired networks. The main reason is that a wireless radio corresponds to only one network interface; thus a node cannot distinguish between different next-hops using network interfaces. Thus, without a mechanism such as source/destination address to control packet transmissions, only broadcast communication is available at the link layer. This basic approach is designated here as Blind Flooding (BF). BF is the simplest way to forward packets with broadcast in NDN wireless networks. It is straightforward and efficient in finding content, even with node mobility and intermittent connectivity. However, flooding packets on a wireless medium generates large network overhead, and high resource consumption, which is not acceptable in IoT environments.

To attenuate the broadcast effect, a mapping between NDN names and MAC addresses can be envisioned [START_REF] Kietzmann | The Need for a Name to MAC Address Mapping in NDN: Towards Quantifying the Resource Gain[END_REF]. The purpose is to use unicast communications when a destination address is available. For example, when an Interest is forwarded (using broadcast), the relay node stores the MAC address of the source node in the PIT alongside the Interest. When the Data is received, it is forwarded to the source node only, using the unicast address corresponding to the Interest. Similarly, the relay node can store the MAC address of the Data source in its FIB, which will be used as a next-hop for the corresponding content name to forward further Interests.

That being said, mapping NDN names to MAC addresses may achieves different performances regarding Data availability, memory usage, network overhead, and packet redundancy. An experimental comparison of these mappings is reported in [START_REF] Kietzmann | The Need for a Name to MAC Address Mapping in NDN: Towards Quantifying the Resource Gain[END_REF]. In short, unicast usually improves the battery lifetime of devices by keeping CPU usage and control overhead to a minimum, and can benefit from MAC layer acknowledgment and frame retransmission. However, additional memory is required to maintain the name-to-MAC mappings, and a mechanism to extract and aggregate prefixes from names is also needed [START_REF] Shi | On broadcast-based self-learning in named data networking[END_REF]. Furthermore, using unicast (i.e., point-to-point) is not inline with the NDN vision, which uses content naming alone.

To keep using broadcast while reducing resource consumption and network overhead is to enhance the Network Interface Controller (NIC) with an appropriate frame filtering mechanism. Therefore, the NIC hardware can be adapted consequently to support frame filtering based on names rather than MAC addresses [START_REF] Shi | Ndn-nic: Name-based filtering on network interface card[END_REF]. Although good improvements can be expected, the solution implies re-engineering a part of the hardware, which makes it non realistic regarding current IoT equipment.

One software-based approach to efficiently use broadcast is to reduce the risks of collision and packet redundancy [START_REF] Wang | Rapid traffic information dissemination using named data[END_REF]. This is achieved by delaying its own transmissions and overhearing neighbors' communications, as detailed in the next section. This approach is designated here as Controlled Flooding (CF). Although this approach is not always efficient for IoT devices and wireless technologies, it is simple to implement and is one of the most realistic solutions.

The approaches described above are summarized in Table I.

V. CONTROLLED FLOODING STRATEGY

As mentioned above, using host addresses to transmit NDN packets decreases its data dissemination power, and limits the NDN benefits expected in mobile wireless networks. Moreover, mapping names to addresses requires transmission overhead to discover and maintain routes in resource-constrained environments, and needs more memory for the FIB.

To keep the benefits of flooding/broadcast while reducing overhead and redundancy, Controlled Flooding (CF) can be envisioned. With CF, relay-nodes exploit broadcast communications to overhear neighbors' communications and possibly avoid forwarding some packets. To do so, every relay node defers its transmissions with a random delay during which it keeps listening on the shared wireless medium. While waiting, if the node overhears a communication (i.e., Interest or Data) with the same name, it cancels its transmission.

In practice, Interest and Data transmissions are deferred for ∆ I and ∆ D periods of time respectively. Both ∆ I and ∆ D are computed based on an interval, defer window (dw), from which an integer value is randomly chosen to generate the waiting delays as follows [START_REF] Amadeo | Forwarding strategies in named data wireless ad hoc networks: Design and evaluation[END_REF]:

∆ D = rand[0, dw -1] × Def erSlotT ime (1) ∆ I = rand[dw, 2dw] × Def erSlotT ime (2)
where Def erSlotT ime is a short period of time.

Here, ∆ I and ∆ D are selected in disjoint intervals with ∆ I > ∆ D to give higher priority to Data packet transmissions and avoid useless Interest broadcasts. During the ∆ I waiting time, the node listens to the channel: if it overhears an Interest or a Data with the same name, it cancels its own transmission. Although the CF strategy is designed for IEEE 802.11 technologies, it can be envisioned over IEEE 802.15.4 when low latency is not required.

In order to study the applicability of CF over constrained wireless networks such as IEEE 802.15.4, in the next section, we formulate an analytical model of the CF strategy considering content popularity.

VI. CONTROLLED FLOODING MODEL

A. Assumptions and Notation

We consider a typical IoT deployment with consumer applications requesting content produced by end-devices. Consumers requests are transmitted through a gateway. The gateway and the end-devices have a single IEEE 802.15.4 interface.

We assume a wireless physical layer with no transmission errors. The network topology is a full binary tree of depth N , in which the root corresponds to the gateway, and the leaves represent the end-devices. The other nodes in the tree act as relay-nodes (see Figure 2). Nodes are not mobile. Sibling nodes overhear each other's communications but no packet is actually forwarded between them. Hence, only one path is possible to reach an end-device (i.e., producer) from the gateway.

We consider that relay-nodes located at the same level in the tree have caches of the same size. The gateway has the largest cache among all nodes, and end-devices have the smallest cache size. We believe that such configuration is a realistic IoT scenario. Nodes manage their caches according to the LRU replacement policy.

The following metrics are considered in the model:

• Cost-per-request (CPR). The number of packets transmitted to retrieve a content requested by the gateway. • Round-trip time per request (RPR). The mean delay time (in ms) measured by the gateway from sending an Interest to receiving a matching Data.

B. Content Popularity

We consider a set of M content items equally divided into K classes, each one containing m = M/K content items. Each class represents a different popularity, and has a probability q k to be requested, where k = 1, 2, ..., K.

The content consumed in our scenario can be considered as Web content, which typically follows Zipf distribution [START_REF] Breslau | Web caching and zipf-like distributions: evidence and implications[END_REF]. q k = c/k α with α > 1 and c = 1/ K k=1 1/k α . We consider that each content item is transmitted in one Data packet. For the sake of simplicity, we assume that each end-device produces the same amount of content items of each class.

The Interest arrival process is modeled using a Markov Modulated Rate Process (MMRP) of intensity λ. Hence, Interest packets for class k content are issued following a Poisson process of intensity λ k = λq k . Within each class, the content item to request is uniformly chosen among the m different content items in the given class. Consequently, a content item in class k is requested with probability q k /m. The notations and their meanings are summarized in Table II.

C. Model Formulation

We first define p k , p k (i) and p t as follows. According to the above assumptions, there is no data duplication among caches at the same level. This allows us to consider all the caches at each level i as one cache. Given this, at the first level (i.e., gateway), the stationary miss probability p k , for content of class k, is defined and proven in [START_REF] Carofiglio | Modeling data transfer in content-centric networking[END_REF] as follows:

p k ≡p k (1)≈exp -λ m q k gx α (3)
for relatively large x, where 1/g = λcσ α m α-1 Γ(1 -1 α ) α . Considering a tree with N levels, an MMRP content request process with rate λ(i), and under the popularity distribution given above, the miss probability at level i ∈ [2, N ) is also defined and proven in [START_REF] Carofiglio | Modeling data transfer in content-centric networking[END_REF] as follows:

log p k (i)=log p k (1) i-1 l=1 p k (l) . (4)
For more details on Equations 3 and 4, including proof and discussions, readers may refer to [START_REF] Carofiglio | Modeling data transfer in content-centric networking[END_REF].

When none of the two sibling nodes has the requested content item, both of them try to forward the Interest according to the CF strategy described in Section V.

According to the random delays computation (see Equation 1), an Interest is forwarded by both nodes if they choose random numbers with a difference smaller than s = r I /τ . Hence, the probability that two sibling nodes transmit the same Interest is equivalent to the probability that two random numbers chosen from the interval of length S = dw + 1 have a difference smaller than s. This can be formulated as follows:

pt=1-( S-2s S ) 2 +2 s-1 i=0 ( S-(i+s) S 2
) .

Here, we can define the CPR for retrieving a class k content item as follows:

CP R k = N i=1 ((1-pk(i)) i-1 j=1 p k (j))×(2(i-1)+ i-1 l=2 ptC k (l)) , (6) where:
C k (l)=1+p f ((N-l-1)+ N -1 n=l+1 ptC k (n)) . (7)
Note that Equation 6 models the CPR only for the requests that have been satisfied. That is, p k (N ) = 0. Equation 6 is obtained based on the following approach. As the content can be found at any level from 1 to N , the cost is defined as a weighted sum of the transmitted packets associated to each level i. The weights correspond to the cache hit probability (1 -p k (i)) at level i given that a cache miss occurred at all the previous levels. For every possible level i, the number of packets is composed of two parts: 2(i -1) corresponds to the number of packets transmitted along the path from the gateway to the level-i device, plus the number of packets transmitted if the sibling of each previous node (from level 2 to i -1) has also transmitted the Interest, which has a probability p t of occurring for each pair of siblings.

Here, Equation 7 assumes that when the sibling of a node (at level l) transmits an Interest, the cost can be recursively computed using the same approach as Equation 6 in its sub-tree (from level l+1 to N ). The only difference is that, on this side of the network, we directly consider the path from level l to the leaf level N , since the requested content has already been found elsewhere and there is no data duplication. However, in each sub-tree, the first Interest is always transmitted, but the number of transmissions recursively computed is subject to the probability that no collision occurs between the first sibling nodes of the sub-tree (p f ).

Following the same approach, we define the mean RPR for a class k content item as follows:

RP R k = N i=1 ((1-pk(i)) i-1 j=1 p k (i))Ri , (8)
where

R i = (i -1)(r I + r D + δ I + δ D ).
Similarly to CPR, as the content can be found at any level from 1 to N , the mean RPR is a weighted sum of the total time R i required to send the Interest and get the Data associated to each level i. The weights correspond to the cache hit probability (1 -p k (i)) at level i given that a cache miss occurred at all the previous levels (i.e., 1 to i -1).

Here, R i is obtained by multiplying the number of hops (i -1) for level i by the total delay needed to send an Interest and get Data; which includes waiting delays (δ I + δ D ) and time-on-air (r I + r D ).

When two sibling nodes delay their transmissions, the node with the shortest delay will transmit the packet first. Furthermore, the round-trip delay measured by the consumer (e.g., gateway) will be affected by the shortest waiting delay computed at each level. Hence, the global estimation of δ I and δ D is not halfway between the lowest and the highest values (e.g., dw/2τ ). To approximate the values of δ I and δ D , we consider the mean of the lowest half of [dw, 2dw] and [0, dw-1] intervals respectively. This gives us δ I = (9dw/8)τ and δ D = ((dw -1)/8)τ .

D. Model Evaluation

To evaluate our model, we use the CF strategy implemented by the NDNOMNeT++ simulation framework [START_REF] Abane | Towards evaluating named data networking for the iot: A framework for omnet++[END_REF]. In the following evaluation we consider a tree of depth N = 4. The gateway requests content from a total of M = 3000 items, distributed in K = 50 classes of decreasing popularity, each one with m = 60 items. The request rate at the gateway is λ = 1 request/s. We set up a cache of size x = 300 packets at each level of the tree. Interest and Data packets have a size of 30 bytes and 90 bytes respectively.

Three content popularity distributions are tested with α ∈ {1.5, 2, 2.5}. Two configurations of the CF strategy are tested with dw = 127 and dw = 255.

Preliminary simulations have been used to set τ = 0.032 µs. We also measured r I = 1.36ms, r D = 3r I and p f = 0.8 with preliminary simulations.

Every simulation has run for 10 hours. Results are reported and discussed in the following.

First, the Interest satisfaction rate is reported in Table III. We observe that dw = 127 always achieves better Interest satisfaction rate than 255. The reason is that 127 is low enough to make relay nodes transmit more packets and explore the network without being too low to create a lot of collisions. However, the remaining results show that this Interest satisfaction rate is achieved at the cost of many more transmissions than dw = 255. This is confirmed in both simulation results and model.

Figures 3a, 3b and3c show the CPR for dw = 127, under α = 1.5, 2 and 2.5 respectively. Similarly, Figures 3d,3e and 3f show the CPR for dw = 255, with α = 1.5, 2 and 2.5 respectively. According to the results, the value of α has in impact on the efficiency of NDN. In fact, small values of α reduce the popularity difference between classes, which introduces more diversity in the requests, increases the cache miss rate and thus the CPR. Inversely, when α is high (e.g., > 2) applications frequently request content items of the most popular classes, which takes advantage of caching and reduces the CPR.

We observe that CPR becomes better when a higher value of dw is used. For example, up to two transmissions per request are saved for the least popular content when using dw = 255 instead of dw = 127.

The model fits well for the different values of dw and α, and accurately predicts the CPR according to the content popularity. However, higher discrepancies between the model and simulations are observed when the value of α increases. The reason is that a cache miss is more likely to occur when α is higher which leads to more transmissions. The behavior of the nodes becomes then more dependent on the link layer, which is not included in the model.

To study the efficiency of CF, we represent the CPR for a perfect-unicast scenario. Perfect-unicast refers to the best CPR expected if a host-based routing protocol with unicast is used instead of NDN. We note that NDN with CF outperforms perfect-unicast for the most popular content. This shows that transmission overhead induced by broadcast can be attenuated by small caches in the presence of popular content.

Figures 3g,3h, and 3i report on the RPR for dw = 127, under α = 1.5, 2 and 2.5 respectively. Figures 3j,3k, and 3l report on the RPR for dw = 255, under α = 1.5, 2 and 2.5 respectively. The model catches the simulation behaviour, and the same observations can be made as for CPR. However, a higher dissimilarity is observed between the model and simulations. The reasons are the same as for CPR with an additional fact related to medium access time. As dw values are not high enough to avoid redundant packet transmissions, the link-layer has to resolve more medium access contentions, leading to less accuracy in our model. This can be confirmed by observing raw simulation results (i.e., blue dots) which present higher scatter as α gets higher.

RPR performance show that the CPR attenuation observed above with dw = 255 comes at the cost of a higher RPR. The reason is that random waiting delays also increase when dw increases. For example, with dw = 255 an increase of 15ms of round-trip delay per request is observed for the least popular content than with dw = 127.

Overall, we find that a trade-off between cost and roundtrip delays is difficult to achieve with the CF mechanism. On the one hand, trying to reduce waiting delays by reducing dw increases the number of transmissions and collisions as the nodes do not have enough time to listen to each other. We should note that this situation becomes even worse in a complex topology when more than two forwarders are available. On the other hand, reducing cost with higher values of dw will induce higher waiting delays. Moreover, the nodes are still listening to transmissions when waiting, which is not helpful for energy consumption.

An ideal improvement one may look for is to reduce the round-trip time and energy consumption by eliminating waiting delays while keeping the lowest number of frame transmissions (i.e., CPR). Since eliminating waiting delays will significantly impact the CPR, we have to question whether a trade-off theoretically exists that may achieve reasonable CPR, low RTT and a reasonable Interest satisfaction rate.

According to the CF strategy, the tree is explored depending on whether both sibling-nodes forward the Interest or only one of them does. In the model evaluation, we find that the best overall performance for CF is achieved with dw = 127. Let the corresponding forwarding probability for each sibling node-pair be p * t . Then, we can easily observe that there is no value of p t lower than p * t that can achieve the same or better satisfaction rate, which is confirmed by Table III. That is, a compromise at L3 level that achieves optimal performance is not possible in our configuration. In fact, overhearing transmissions at L3 requires packets to be entirely received in order to access the name. Moreover, in our configuration every node can overhear only its siblingnode transmissions. Therefore, by shifting the forwarding decision to the L2 level (with some modifications) instead of using deferred transmissions, one may expect better performances since the CSMA algorithm natively considers multiple-access contention. The following section presents the design and evaluation of our L2-based approach. VII. A NAMED-DATA CSMA FOR IEEE 802.15.4 As mentioned before, eliminating waiting delays will inevitably increase the number of unnecessary packet transmissions and channel access contention. To handle that, we consider p t = 1, which corresponds to dw = 0, and we modify the CSMA algorithm of the IEEE 802.15.4 in such a way that the number of attempts to access the channel is lower when transmitting an Interest than when transmitting a Data. In practical terms, we replace the waiting delays by a priority-based CSMA scheme designed for NDN. In this section, we describe the legacy CSMA algorithm followed by the design and evaluation of the ND-CSMA scheme. [START_REF]Ieee standard for local and metropolitan area networks-part 15.4: Low-rate wireless personal area networks (lr-wpans)[END_REF] defines a standard for the physical and MAC layers of low-rate wireless networks. The standard uses slotted or unslotted CSMA as a medium access mechanism. In this section, we consider the unslotted version of CSMA.

The CSMA algorithm works with a set of default parameters and each node maintains two values when running the algorithm: Number of Back-offs (NB) and Back-off Exponent (BE). NB is always initialized to 0 for a new packet transmission, and it denotes the number of access attempts for the current packet transmission. BE is used to compute the random back-off period that a device should wait before attempting to assess the channel. Default parameter values are shown in Table IV.

The CSMA algorithm operates as follows:

1)

Step 1. The values of N B and BE are initialized according to the IEEE 802.15.4 standard. 2) Step 2. The delay of the random back-off period is selected in the range from 0 to 2 BE-1 . 3) Step 3. After the waiting time, the node performs a Clear Channel Assessment (CCA). If the channel is idle, the node starts transmission. If the channel is busy, the algorithm increments N B by 1 and updates BE as follows: BE = min(BE + 1, aM axBE). Then, if N B is lower than the maximum number of back-offs (i.e., macMaxCSMABackoffs) the algorithm goes to Step 2; if not, the transmission is canceled and considered to have failed.

B. The Named-Data CSMA Scheme

In legacy CSMA, all the nodes access the shared channel with a fair chance. However, priority-based CSMA [START_REF] Zhao | Priority-based ieee 802[END_REF] uses the difference in traffic type to introduce differentiated channel access for nodes. Therefore, the priority-based CSMA mechanism is designed to make nodes with high priority traffic have a greater chance of accessing the channel. The ND-CSMA algorithm we propose is inspired by the priority-based CSMA approach.

The frames are classified into two priority classes according to the packet type they transmit: (i) frames that contain a Data packet at any node, and frames that contain a locally issued Interest (i.e., consumer node) are assigned a priority 0. (ii) frames that contain an Interest packet to forward (i.e., at relay nodes) are assigned a priority 1. The other CSMA parameters and values are kept the same in ND-CSMA.

By distinguishing between Interest and Data frames, the ND-CSMA algorithm operates in the same way as legacy CSMA described above, but with one difference. When the Fig. 4: ND-CSMA algorithm channel is assessed to be busy, retrying another back-off depends on the priority class of the frame to transmit. If the frame has a priority 1, the number of back-off attempts is limited by a threshold value th. Then, the transmission is canceled if the number of attempts reaches th. The algorithm operates as usual for the frames of priority 0. According to the number of back-offs allowed by the CSMA parameters, the values of th should be between 1 and 4, while th = 5 makes ND-CSMA equivalent to the legacy CSMA.

ND-CSMA scheme is summarized in Figure 4.

C. Evaluation

To evaluate the ND-CSMA scheme, we simulate three scenarios.

• CF. The Controlled Flooding strategy as described in Section V with the legacy CSMA algorithm. • BF. The Blind Flooding approach presented in Section IV, also using the legacy CSMA. Notice that this scenario is equivalent to the CF strategy without waiting delays. • ND-CSMA-x. The BF strategy using the ND-CSMA mechanism with th = x ∈ {1, 2, 3, 4}. In the BF strategy, upon receiving an Interest or Data, a node immediately tries to forward the packet and lets the link-layer medium access algorithm (i.e., legacy CSMA or ND-CSMA) resolve the contention.

All the scenarios are simulated under the same conditions and parameters as those used in Section VI: a tree topology with depth N = 4, M = 3000 content items distributed in K = 50 classes, each one with m = 60 items, and a cache of size x = 300 packets at each level. For the CF strategy, we use dw = 127 and τ = 0.032µs. Two content popularity configurations are evaluated: a low popularity difference with α = 1.2, and a high popularity difference with α = 2.0.

The following metrics are measured in the simulation:

• Mean round-trip time. The mean time needed for the gateway to retrieve a content item from a device. • Transmitted frames. The total number of frames successfully transmitted. We also refer to this metric as the cost.

• Interest satisfaction rate. This corresponds to the number of Data packets received by the gateway over the number of Interests it sent. • Mean back-off time. The average time the nodes spent in back-off to access the wireless medium. This is also used as an indicator for energy consumption.

Figure 5 shows the results obtained for the low (α = 1.2) and the high (i.e., α = 2.0) popularity rate respectively.

We observe that for both popularity configurations, ND-CSMA-1 achieves better RPR compared to the CF and BF scenarios. The mean back-off time with ND-CSMA-1 is the smallest among the evaluated scenarios, while BF achieves the highest back-off time due to the large number of forwarding decisions generated after eliminating waiting delays. This means that legacy CSMA without delays has to resolve medium access contention with more back-off periods whereas ND-CSMA has the possibility to cancel some Interest transmissions when the channel is busy rather than waiting for other back-off periods. For this reason, the round-trip time achieved in with BF is slightly higher than ND-CSMA.

The CF strategy is also capable of canceling scheduled transmissions using deferred transmissions. However, it achieves that with a wait-and-listen mechanism which induces higher round-trip delays, and a relatively high back-off time is required when the chosen random delays are not different enough.

Moreover, the results show that ND-CSMA-1 can ensure necessary packet transmissions while keeping the total cost at a minimum compared to the two other schemes.

For content with high popularity differences (i.e., α = 2.0), the Interest satisfaction rate is quite similar for all the approaches. This indicates that even with a reduced medium access attempts, ND-CSMA does not reduce the efficiency of the broadcast. When content items have quite similar popularity (i.e., α = 1.2), ND-CSMA-1 achieves lower Interest satisfaction rate. This means that more medium access attempts are needed to provide a good Interest satisfaction rate. This is achieved by ND-CSMA-2. ND-CSMA-2 has a higher frame transmission and back-off time than ND-CSMA-1, but it is the second best scenario after ND-CSMA-1. That is, ND-CSMA-2 may be more suitable than ND-CSMA-1 in some situations.

Overall, ND-CSMA-1 and ND-CSMA-2 seem to be the best compromise in the evaluated configuration. For the same value of α, ND-CSMA-3 and ND-CSMA-4 achieve merely the same results. This is because 3 or 4 attempts to access the medium does not prevent nodes from transmitting Interests as they would do it in legacy CSMA. The behaviour of ND-CSMA becomes then close to the legacy CSMA where the number of attempts to access the medium is 5.

To return to our theoretical expectations, the results confirm that a link-layer adaptation is able to keep the benefits of a broadcast-based forwarding strategy in terms of satisfaction rate, while reducing medium access contention and frame transmissions. It then achieves the trade-off we were looking for.

VIII. CONCLUSION AND FUTURE WORK

In this paper, we modeled Controlled Flooding, a simple broadcast-based forwarding strategy for NDN in wireless networks. One objective of the model is to show that caching can attenuate the number of transmissions generated by broadcast while keeping the data dissemination power of NDN. The second objective dealt with in the second part of the paper is to study the relevance of investigating the link layer to design a forwarding strategy that achieves a satisfactory compromise. Based on a simple modification of the IEEE 802.15.4 MAC layer, preliminary results shed light on the need to rethink typical link-layer schemes for ICN/NDN such as the CSMA algorithm.

However, we can easily foresee that the ND-CSMA adaptation is specific to the topology and scenario under consideration, and thus can not be applied as a general solution to all network configurations. As future work, we aim to explore more complex CSMA adaptations for lightweight forwarding to take the most of NDN and design a general-purpose Named-Data CSMA. Another envisioned direction for future work is to formulate a more realistic model based on the one presented in this paper.

IX. ABBREVIATIONS

ICN

Fig. 1 :

 1 Fig. 1: Interest and Data processing at an NDN node

Fig. 2 :

 2 Fig. 2: Tree topology example with N = 3

5 Fig. 3 :

 53 Fig. 3: Model evaluation results

Fig. 5 :

 5 Fig. 5: ND-CSMA evaluation

) Using the PIT, the Data packet follows the reverse path

  the CS, the router checks the PIT.3) If an Interest for the same content item is present, the new Interest is not forwarded but its originating interface is added to the existing PIT entry. The new Interest is forwarded only if no similar Interest is already waiting in the PIT. 4) Interest packets are forwarded according to the FIB using the longest prefix match (LPM). After that, the router records the Interest and its originating interface in the PIT until a matching Data is received or the Interest expires. 5) When the Interest reaches the producer of the content item or an intermediate cache, the corresponding Data packet is sent back. 6

2) Upon receiving an Interest, a router (relay node) checks its local CS. If a corresponding Data exists, it is sent back without forwarding the Interest any further. If there is no matching content in

TABLE I :

 I Broadcast support in NDN

	Approach	Description	Target network
	Unicast mapping [18]	Mapping between NDN names and MAC addresses	IEEE 802.15.4
	Name filtering [20]	Names filtered at NIC	Ethernet
	Broadcast reduction [21]	Delayed transmissions and neighbors' communication overhearing	IEEE 802.11

TABLE II :

 II Model variables Notation Meaning p k , p k (i) Cache miss probability for class k content at the gateway, at level i > 1. p t Probability that two sibling nodes transmit the same Interest given that a cache miss has occurred in both nodes.

	N	Tree depth.
	K	Number of popularity classes.
	M	Number of total content items (m = M/K in each class k).
	x	Cache size in each level in number of chunks.
	λ, λ(i)	Content request rate at the gateway, at level i > 1.
	λ k	Content request rate at the gateway for class k.
	σ	Average content size in number of chunks.
	q k , q k (i)	Content popularity distribution of requests at the gateway, at level i.
	dw	Defer window.
	r I	Time needed to send an Interest over one hop (excluding waiting delays).
	r D	Time needed to send a Data over one hop (excluding waiting delays).
	τ	Defer slot-time.
	p f	Probability that the link-layer avoids a collision given that two nodes transmitted an Interest.

TABLE III :

 III Interest satisfaction rate

		dw = 127	dw = 255
	α = 1.5	87.8%	84.1%
	α = 2.0	95.1%	93.2%
	α = 2.5	98.2%	97.4%

TABLE IV :

 IV Default values for IEEE 802.15.4 CSMA

	Parameters	Value
	AMaxBE	5
	MacMaxCSMABackoffs	4
	MacMinBE	3
	A. Legacy CSMA
	IEEE 802.15.4

  Information Centric Networking NDN Named Data Networking RTT Round-Trip Time CSMA Carrier-Sense Multiple Access ND-CSMA Named-Data Carrier-Sense Multiple Access LRU Least Recently Used MANET Mobile Ad hoc Network FIB Forwarding Information Base PIT Pending Interest Table CS Content Store BF Blind Flooding NIC Network Interface Controller CF Controlled Flooding dw defer window CPR Cost-per-request RPR Round-trip time per request NB Number of Back-offs BE Back-off Exponent CCA Clear Channel Assessment


Andrea Aparicio

Jorge Velasco-Hernández

Claude H Moog

Yang-Yu Liu

Marco Tulio Angulo

Structure-based identification of sensor species for anticipating critical transitions

come   L'archive ouverte pluridisciplinaire


Pierrick Pochelu
email: pierrick.pochelu@totalenergies.com

Serge G Petiton
email: serge.petiton@univ-lille.fr

Bruno Conche
email: bruno.conche@totalenergies.com

An efficient and flexible inference system for serving heterogeneous ensembles of deep neural networks

is still adapted to optimize and to serve ensembles.

Two different software layers have been proposed to infer efficiently individual DNNs but does not propose to combine them: the inference servers (Triton [START_REF] Xu | deep into triton inference server: Bert practical deployment on nvidia gpu[END_REF], Ray Serve 1 [START_REF] Moritz | Ray: A Distributed Execution Engine for the Machine Learning Ecosystem[END_REF] , Tensorflow Serving [START_REF] Olston | Tensorflow-serving: Flexible, highperformance ml serving[END_REF] and TorchServe [START_REF] Devito | Using python for model inference in deep learning[END_REF]) serve the inference systems (such TensorRT [START_REF] Davoodi | tensorrt inference with tensorflow[END_REF], OpenVINO [START_REF] Ge | Inference with intel[END_REF], ONNX [START_REF] Sarah | ONNX[END_REF] and TFLite [START_REF] Lee | On-device neural net inference with mobile gpus[END_REF]) predictions. Our work attempt to fill this gap between the current inference system technologies and the ensembles of deep neural networks.

The question we attempt to answer is simple but the solution is challenging "How to systematically allocate an ensemble of DNNs to a given set of devices?". The systematic procedure must be endowed with two main qualities. Firstly, the flexibility, the systematic procedure aims to fit the ensemble in memory to be ready to answer requests, even if the number of devices is lower than the ensemble size. An ideal flexible solution must be able to allocate heterogeneous DNNs (such ResNet, Inception, EfficientNet, ...) on modern clusters containing heterogeneous devices (such CPUs, GPUs, TPUs, ...). Secondly, the efficiency, when an ensemble fits in memory it should optimize the usage of underlying multi-cores devices with minimum overhead due to data transfer.

We design the answer in three points.

• First we propose the allocation matrix as the formalism of the decision space in an innovative way. It designs how DNNs are allocated into the devices including colocalization (multiple DNNs instances into the same device), data-parallelism (one DNN multi-threaded on multiple devices), and the batch size of each DNN instance (which controls devices cores usage, memory consumption, data exchange). • We propose an allocation matrix optimizer. It runs successively a worst-fit-decreasing algorithm to fit DNNs in memory and a bounded greedy algorithm to speed up the allocation.

• Finally, we propose a design of the inference system. To avoid overhead, it asynchronously runs: data batching, 1 https://docs.ray.io/en/master/serve/index.html

Abstract-Ensembles of Deep Neural Networks (DNNs) has achieved qualitative predictions but they are computing and memory intensive. Therefore, the demand is growing to make them answer a heavy workload of requests with available computational resources. Unlike recent initiatives on inference servers and inference frameworks, which focus on the prediction of single DNNs, we propose a new software layer to serve with flexibility a nd e fficiency en sembles of DNNs.

Our inference system is designed with several technical innovations. First, we propose a novel procedure to found a good allocation matrix between devices (CPUs or GPUs) and DNN instances. It runs successively a worst-fit t o a llocate D NNs into the memory devices and a greedy algorithm to optimize allocation settings and speed up the ensemble. Second, we design the inference system based on multiple processes to run asynchronously: batching, prediction, and the combination rule with an efficient internal communication scheme to avoid overhead.

Experiments show the flexibility a nd e fficiency un der extreme scenarios: It successes to serve an ensemble of 12 heavy DNNs into 4 GPUs and at the opposite, one single DNN multi-threaded into 16 GPUs. It also outperforms the simple baseline consisting of optimizing the batch size of DNNs by a speedup up to 2.7X on the image classification task.

Index Terms-Neural network, ensemble learning, inference system Ensembles of deep neural networks are now well-known for producing qualitative predictions. First, ensembles of deep neural networks significantly i mprove g eneralization accuracy compared to one single model [START_REF] Sollich | Learning with ensembles: How overfitting can be useful[END_REF]. Second, they generally produce well-calibrated uncertainty estimates [START_REF] Lakshminarayanan | Simple and scalable predictive uncertainty estimation using deep ensembles[END_REF].

Today, multiple researchers and practitioners have well understood the benefit o f e nsembling D NNs. F or e xample, in cyber-attack detection [START_REF] Haider | A deep cnn ensemble framework for efficient ddos attack detection in software defined networks[END_REF], time series classification [START_REF] Pathak | Ensemble deep timenet: An ensemble learning approach with deep neural networks for time series[END_REF], medical image analysis [START_REF] Cea | Pneumoperitoneum detection in chest x-ray by a deep learning ensemble with model explainability[END_REF], semi-supervision [START_REF] Sun | Deep learning for industrial kpi prediction: When ensemble learning meets semi-supervised data[END_REF] and unbalanced text classification [START_REF] Sun | An ensemble classification algorithm for imbalanced text data streams[END_REF]. F urther, s everal w inners a nd t op performers on challenges routinely use ensembles to improve accuracy.

It is also of common knowledge that a machine learning model creates value only in the inference phase. That is to say when the model is hosted on hardware and ready to receive input data samples from a client application and return their prediction. However, ensembles of DNNs are memory, time and computational resources expensive and no inference system DNNs predictions, and the combination rule with an efficient internal communication scheme.

Our paper follows this structure: (1) we show the recent progress in inference software. [START_REF] Lakshminarayanan | Simple and scalable predictive uncertainty estimation using deep ensembles[END_REF] We introduce our inference server for ensembles DNNs, how to use it and its internal mechanisms. (3) We perform multiple benchmarks and discuss the flexibility and the efficiency of our inference system.

I. INFERENCE SOFTWARE

A. Inference frameworks

The inference frameworks contain generally two main functions, the "load" function to load a trained DNN from the disk to a targeted device and the prediction function f (x) → y with x the data samples and y the associated predictions. The most sophisticated inference frameworks [START_REF] Davoodi | tensorrt inference with tensorflow[END_REF], [START_REF] Ge | Inference with intel[END_REF], [START_REF] Sarah | ONNX[END_REF], [START_REF] Lee | On-device neural net inference with mobile gpus[END_REF] perform post-training optimization such operations optimization and device-specific optimization with low or no impact on the accuracy. We use here the Tensorflow deployment ("pb files") as the underlying format and focus our work on the allocation challenge.

A critical part of optimizing the performance of a DNN model is its batch size. It controls the internal cores utilization, the memory consumption, and the data exchange between the CPU containing input data and the device supporting the DNN (if different). That is why some tools2 scans multiple batch size values of a given DNN. Then, the batch size offering the best performance is used. This Best Batch Strategy (or BBS) is a relevant mechanism to optimize a single DNN on one device, but it is a naive and rigid method to optimize multiple DNNs predicting ensemble. Due to the lack of efficient technique to handle ensemble of DNNs in inference mode, we design an allocation matrix optimizer that we compare to BBS.

B. Inference servers

The last few years, we show the emergence of software [START_REF] Crankshaw | Clipper: A low-latency online prediction serving system[END_REF] [8], [START_REF] Moritz | Ray: A Distributed Execution Engine for the Machine Learning Ecosystem[END_REF], [START_REF] Olston | Tensorflow-serving: Flexible, highperformance ml serving[END_REF], [START_REF] Devito | Using python for model inference in deep learning[END_REF] to serve inference framework predictions as a service. Most of them wrap predictions in a REST service but other technologies exist such database management service [START_REF] Agrawal | Cloudy with high chance of DBMS: a 10-year prediction for enterprise-grade ML[END_REF]. They implement often the same features. Ensemble selection allows the client application to choose the model which will answer among multiple applications or the same application but different trade-offs between accuracy and speed. To improve performance under redundant requests, caching allows avoiding recomputing similar requests. When the amount of requests is low and irregular, adaptative batching allows triggering prediction before the buffered batch is full to improve the latency.

Our work benefits from those inference server technologies. The novelty is that we handle heterogeneous ensemble of DNNs by adding an intermediate software layer between low level DNN inference frameworks and inference servers.

II. THE WORKFLOW

Once an ensemble has been trained and built, we need to serve it efficiently on the available computing resources. We design an efficient inference pipeline illustrated in figure 1.

In the following sections, we will describe first how the inference server is used. Then, the allocation matrix which drives performance. Finally, main components of our inference server is presented one-by-one: the inference system core, the worker-pool and the allocation optimizer.

A. Using our inference server

The engineer who is responsible for managing the inference server provides to the matrix allocation optimizer the ensemble of DNNs, the CPUs, and the GPUs to use. Sometimes, the engineer does not want to give all available devices into its cluster to deploy an ensemble, so he can keep GPUs for other applications. The matrix allocation optimizer will automatically optimize the allocation of the ensemble for the given devices.

Once the allocation matrix is computed, the inference system is deployed online. It implements the usual inference server features such as an HTTP/HTTPS wrapper and adaptative batching. To be more precise, the term "adaptative batching" can now lead to confusion. The buffer waiting request is now defined by the size of segments and not the batch size of the individual DNNs.

B. The allocation matrix data structure

The allocation matrix is a data structure describing with high flexibility the design of the worker-pool used by the inference system. It designs how DNNs are allocated into the devices including co-localization (multiple DNNs instances into the same device), data-parallelism (one DNN multi-threaded on multiple devices), and the batch size.

In this matrix, element 0 means an absence of a worker process in the given device, while other values represent the batch size. The workers co-localized into the same device are readable as non-zero values in the row of the allocation matrix. The workers which are instances of the same DNN are dataparallel, they are readable as the non-zero values in a given column.

Finally, some devices may not be used, so we can observe rows containing only zero values. But it is illicit to have a column with only zero values. In other words, all DNNs must be represented in the ensemble.

1) Co-localization: Co-localization allows fitting more DNNs than the number of devices (the pigeon-hole principle). It may allow also maximize the utilization of internal cores into a device too.

It is well known that the batch size is an important setting. However, optimal batch size values in the context of multiple DNNs co-localized into one GPU are challenging to find. In general, the larger batch may increase cores utilization and it consumes more memory. Due to those complex relationships between multiple DNNs co-localized and hardware, only benchmarks allow knowing the performance of co-localized models. And more, only multiple benchmarks allow finding good settings such as which DNNs should be put together and their optimal batch size values.

2) Data-parallelism: Data-parallelism allows to speed up a prediction of one DNN using multiple devices. The workers run the same DNN but in different instances. They take data samples to predict from the same input FIFO queue.

Ideally, n threads should multiply the number of images predicted per second by n. Yet, because we use multiple shared data structures: one segment ids FIFO queue, the shared data memory, and the prediction FIFO queue, perfect scalability is not ensured. Only benchmarks allow to compute the performance and if increasing the number of workers is worth it.

C. The inference system

The inference system is the core component of the server. It is a function f (X, A) → {Y, S} with X data samples to predict and Y the associated predictions of the ensemble of DNNs. A is the allocation matrix driving the worker-pool construction and S is the performance score.

The inference system can be run with 2 modes. In "Deploy Mode" it is deployed online to serve client requests, A is fixed and S is ignored. In "Benchmark Mode" it measures the performance S provided by the allocation matrix A on the data calibration samples X, and Y is ignored.

To accelerate the inference system we design it with multiple processes. The segment identifiers broadcaster which splits the incoming workload of requests into segments, the worker pool containing DNNs instance and return segments of predictions in the combination accumulator FIFO queue, the combination accumulator combines segments of predictions and returns to the client the final prediction: the prediction of the ensemble.

1) The segment ids broadcaster: The inference system contains thread-safe FIFO queues allowing to broadcast and gather information with the workers. It contains also the X shared memory, this is a heavy buffer of data readable by all the workers. All those data structures are stored in the RAM.

To avoid transmitting heavy messages and stressing threadsafe FIFO queues, all images information passing through queues are gathered into segments. All segments contain N samples, except the last segment which contains the information of the remaining samples.

After getting a segment identifier s, such as s ≥ 0, a worker knows he is responsible to predict the images from start(s) = s * N position to the end(s) = min((s + 1) * N, nb images) position with nb images the number of images in the X shared memory. The segment ids broadcaster can also put special values like s = -1 to ask workers to shut down before terminating the overall inference system.

For example, in the figure 1 if the user requests the prediction for 300 images with N = 128, they are represented internally as 3 segments, two are size 128 and one is size 44. Then, the segment ids broadcaster put 6 messages: 0, 1, 2 integers into A queue and B queue.

2) The prediction accumulator: This process combines efficiently predictions from workers and when it is finished it returns them to the client. After predicting a segment of data, a worker puts a message in the prediction queue. Each of these messages is a triplet {s, m, P } with s the segment identifier, m the model identifier and P the prediction matrix of dimension (end(s) -start(s)) × C and C the prediction length for each image e.g., the number of classes. To combine predictions, the prediction accumulator first allocates a buffer Y of dimension nb data×C zeroed. Then, it updates the cumulative prediction each time it receives a message triplet {s, m, P }. The Python code using Numpy arrays of the averaging accumulation is simply:

Y[start(s):end(s)]+=P/M
With M the number of DNNs in the ensemble. Other combination rules can be easily implemented such as majority voting or weighted averaging. Furthermore, other applications can require specific combination rules such as those applied in object detection [START_REF] Solovyev | Weighted boxes fusion: Ensembling boxes from different object detection models[END_REF]. Any combination rule code must be developed by keeping in mind that predictions come into messages to be asynchronous with the neural network predictions.

To go into further details, the workers can send special messages to the prediction accumulator. The special message {-1, None, None} allows notifying that a device has not enough memory to load or initialize a DNN. This triggers the shutdown of the inference system and every process into it. The special message {-2, None, None} allows notifying that one worker is ready to serve after its initialization. Starting the inference system takes a few seconds, we know the inference system is fully initialized and ready to receive the user requests when all workers send {-2, None, None} to the prediction accumulator.

D. The worker pool

The worker pool gets segments from FIFO queues, predicts them, and returns the predictions to the prediction accumlator.

All workers are designed the same, they are illustrated in figure 2. To be performant it contains 3 asynchronous threads: the batcher, the predictor and the prediction sender.

• The batcher waits for incoming segment identifiers from the input FIFO queue. When it receives one, it splits the segment into a batch of data and gives them to the predictor. Each worker has its batch size described in the allocation matrix. • The predictor persists the DNN into the device memory.

When it receives a segment identifier, first it loads the segment of data. Then it runs the prediction on each batch and finally, it gives the batch of predictions to the prediction sender. • The prediction sender gathers predictions batch by batch to build segments of prediction. When a segment is completed, this process puts the segment of prediction into the prediction FIFO queue.

E. The allocation optimizer

The allocation matrix optimizer goal is first to fit DNNs into the memory and then optimize their performance. That is why it runs first a worst-fit-decreasing algorithm to solve the binpacking problem to fit DNNs into the memory of the device. Second, a greedy algorithm assesses thousands of matrices to find the faster one based on offline benchmarks. Finally, the best matrix is cached to avoid recomputing it again when the server will be restarted. These two algorithms are next detailed.

1) Algorithm 1 -Worst-Fit-Decreasing with priority to GPUs: It solves a bin packing problem to put objects (DNNs) into a finite number of bins (devices). All DNNs are set with the minimum batch size value (8 in our experiments). It is more exactly a bin packing with offline heuristics problem because the DNNs are known before execution and can be sorted in decreasing order. We attempt to find a feasible solution with the already known Worst-Fit Decreasing algorithm.

This algorithm has the already known properties to optimize memory allocation. At each step of the worst-fit algorithm, it chooses to allocate a DNN into the device with the largest available memory. Therefore it may remain large memory space into the GPU after a DNN allocation. This remaining memory space can be big enough so that other smaller DNNs can also be placed in that remaining memory and therefore maximize the memory filling. Second, ordering the input list by decreasing DNNs size has been proved [19] to maximize the memory filling compared to a non-ordered version. Finally, Worst-Fit prioritizes an equitable workload between homogeneous devices based on the memory criterion. On the opposite, First-Fit, Best-Fit and Next-Fit, attempt to fill the first devices and keep the last devices empty.

To improve significantly the speed up of the allocation, we hard code a rule to allocate in priority the GPUs rather than CPUs. It is of common knowledge that GPUs can run DNNs an order of magnitude faster than CPUs. Indeed, the CPUs start to be used by algorithm 1 only when no more space is available on the GPUs.

Algorithm 1 Worst-fit-decreasing with a priority to GPUs end if 26: end for 27: return A more_remaining_memory function returns the device with the most remaining memory. fit_mem returns if the allocation matrix is feasible in terms of memory availability.

2) Algorithm 2 -Bounded greedy optimization: The algorithm 2 goal is to refine the starting allocation matrix and return a faster allocation matrix. Before explaining this algorithm, we will first provide a detailed analysis of the complexity of its decision space which drives our choices to design it.

The number of matrices is given by equation 1 with D devices, B batch size values and M DNN models in the ensemble.

total matrices = ((B + 1) D -1) M (1)
The number of possible element values is (B + 1) all possible batch size values plus the 0 elements for no worker. The number of possible values in a single column is described by (B + 1) D -1. The term (B + 1) D allows to brute-force all possible values in a column minus the zero columns which are forbidden. Note the two power terms which show the explosion number of combinations. For example, if we have 8 DNNs, 4 GPUs, and 1 CPU total matrices ≈ 1.3E31, this is much more than the number of stars in the observable universe. To put the problem into perspective, one allocation matrix takes an average of 40 seconds to be assessed. It includes the construction of the inference system time plus the offline benchmark time. That is why only a few hundred matrices can be reasonably assessed by an optimizer.

A greedy algorithm provides an often effective solution to many combinatorial optimization problems. When applied to our case, it starts with the matrix given by algorithm 1 and at each iteration, it assesses all neighborhood matrices and replaces the current matrix with the best-assessed matrix. We consider that two matrices are neighborhoods if they are both valid (again, no 0 columns) and if there is only one different element between them. The greedy algorithm is stopped when no neighborhood improves the current matrix.

The greedy algorithm breaks down the overall complexity described in equation 1 into a succession of combinations (or neighbors) measured by equation 2 to assess. With F the number of forbidden matrices we cannot explore such

0 ≤ F ≤ D. total neighs = (B + 1) * (D * M ) -F (2)
Let's take our previous example, 8 DNNs, 4 GPUs, and 1 CPU. The total number of combinations is total matrices ≈ 1.3E31 but the greedy algorithm needs to assess only between 232 and 240 neighbors at each iteration.

Greedy algorithms are well-known approximation algorithms. However, the number of neighbors can still be very computingintensive to evaluate in some cases, and more the number of required iterations can be large before finding an optimum. To limit the computing cost of the greedy we propose two bounds. First, each iteration evaluates at most max neighs randomly drawn neighbors (line 9). We also limit the number of iterations to max iter (line 6).

Despite that our algorithm is an approximation of a greedy algorithm, we have the guarantee that in the worst-case scenario a solution as good as the starting one is returned. This characteristic is inherited from the greedy algorithm. Line 18 can be read "if we do not improve strictly the performance, the algorithm is stopped".

The rate of visited neighbours is measured with max neighs total neighs . If it is close to zero it means the final performance may be very volatile. At the opposite, max neighs total neighs ≥ 1 means all neighbours are visited and does not introduce volatility. Another source of volatility is the benchmark function (lines 4 and 11) but in practice, when the amount of calibration data samples is large enough, the measurement is stable.

The pseudo-code is presented in bloc code 2. bench function instantiates the pipeline with the given allocation settings (first argument) on the calibration data samples (second argument) and returns the performance to maximize or 0 if a DNN instance does not fit in memory.

Algorithm 2 Bounded greedy algorithm This section provides a detailed description of our experimental settings. Reading this section is not needed to understand the next sections.

The performance metric. The transmission of online messages with the client and their characteristics is application dependant and thus we rather perform offline benchmarks to evaluate the core prediction performance. This allows us to stay focused on the specificity to deploy ensembles under a heavy workload of requests. Therefore, our metric will be the throughput measured by the number of data samples predicted per second.

Code and framework. All the asynchronous objects are implemented with the "Multiprocessing" built-in Python 3.6 package. Our FIFO queues, shared memory, and processes are respectively implemented with Queue class, Manager class, and Process class.

Additionally, we use two well-known external packages: the Numpy numerical library and Tensorflow 1.14 to deploy models widely supported by GPUs and CPUs.

The hardware. All results reported are performed into an HGX cluster containing 16 Tesla-V100 GPUs. The flexibility and efficiency of our server are analyzed by varying the number of GPUs to use from 1 to 16.

We also performed a few benchmarks on a computing node identical to the Oak Ridge Summit node. Both clusters have the same GPUs but different CPUs and different operating systems. The measured results are very similar to HGX so we decided do not to report the performances.

The ensembles of DNNs. To assess the efficiency and the flexibility of the inference system, we benchmark 5 heterogeneous ensembles named according to the number of models and the name of the database they learned from.

First, we build arbitrary 3 ensembles of present or past stateof-art DNNs. They have also been chosen for reproducibility purposes and they are easily implementable for any deep learning framework. IMN1 contains only ResNet152 and it allows us to show our workflow is general enough to optimize one single DNN. IMN4 contains 4 DNNs {ResNet50, ResNet101, DenseNet121 and VGG19}. IMN12 contains all DNNs from IMN1 and IMN2 plus {ResNet18, ResNet34, ResneXt50, InceptionV3, Xception, VGG16, MobilNetV2}.

Then, we generate 2 other ensembles named FOS14 and CIF36. FOS14 contains 14 DNNs and is used for our in-house applications with 224x224 RGB images as input and predict among 91 classes. CIF36 is an ensemble of 36 DNNs to classify the images from the CIFAR100 dataset taking 32x32 RGB images and 100 classes.

FOS14 and CIF36 have been built with an in-house AutoML [START_REF] Pochelu | A deep neural networks ensemble workflow from hyperparameter search to inference leveraging gpu clusters[END_REF] with a posthoc ensembling method to automatically build ensembles to maximize the prediction quality. FOS14 and CIF36 are built around the Resnet skeleton from 10 to 132 layers and the number of filters in each convolution is multiplied from 0.5 to 3 compared to the usual ResNet architectures. We do not provide further details on their construction and training to stay focused on the inference phase.

Calibration data samples. The meaning of the data has no impact on any performance measured on the classification task. However, applying this server to other DNN methods may need a few realistic data samples to measure a relevant performance time. For example, in the Faster-RCNN [START_REF] Girshick | Fast R-CNN[END_REF] architectures the RPN module iterates on some region of interest for each input image.

The possible batch size values. We fixed {8, 16, 32, 64, 128} as possible batch size values. More values increase significantly the number of possible allocation matrices and make the exploration of combinations more difficult. Fewer values reduce the degree of freedom to control internal parallelism, memory consumption, and data exchange.

The segment size. We evaluate multiple segment sizes and we observe that smaller values reduce the granularity of the workload and improve its distribution between processes. In all this work the segment size is fixed to 128. It should generally be equal to or greater than the maximum batch size.

Algorithm 2 -Greedy allocation. We choose max neighs = 100 and max iter = 10. This is a total of at most 1000 combinations to assess. On average, one matrix evaluation takes 40 seconds therefore those two chosen values limit the computing cost to 12 hours.

When D -M > max iter with M DNNs and D devices. The max iter is replaced with D -M . It allows getting a chance of using all devices when the number of devices is large. In all our benchmarks, it is used only three times with IMN1 ensemble on 12 GPUs and 16 GPUs and IMN4 on 16 GPUs.

IV. OFFLINE BENCHMARKS

This section describes 3 performance analyses of our system. The first one estimates the overhead introduced by the inference system. Then we analyze the performance varying the ensembles and the number of GPUs. Finally, we will compare our allocation matrix optimizer to a simple baseline named "Best Batch Size".

A. Overhead of the inference system

In all our benchmarks, the inference system overhead is measured at most 2% of the total inference time. To estimate this overhead, we temporarily replace all the DNNs calls with a fake prediction containing only zero values, thus the prediction accumulator still gathers predictions but returns zero values.

We perform multiple offline benchmarks of this fake inference system and we report it takes at most 0.035 seconds in the case of IMN12 ensemble on 16 GPUs, in this case, allocation matrix optimizer producing 22 workers. In comparison, the true inference system (without faking predictions), takes 2.528 seconds to predict 1024 images (i.e., throughput=405 in the table I).

B. Varying GPUs and ensembles

Table I shows the performance in terms of prediction performance of the 5 ensembles. The first major observation is that to serve efficiently an ensemble of DNNs we do not need systematically as much as GPUs as DNNs, but more GPUs generally improve performance.

The allocation optimizer successes in automatically constructing allocation matrices in the majority of assessed scenarios. It found a feasible solution to store 12 DNNs into only 4 GPUs. On the opposite, it also shows success to leverage multiple GPUs, for example, the Resnet152 model alone gets a Weak Scaling Efficiency of 87% with 16 GPUs. Finally, when we compare algorithm 1 (Worst-Fit Decreasing) alone and algorithm 1 followed by algorithm 2 (Bounded Greedy) throughput, we observe also that the second algorithm produces generally a significant speed-up confirming the usefulness of this second algorithm.

IMN1 IMN4 IMN12 FOS14 CIF36 #G A1 A2 A1 A2 A1 A2 A1 A2 A1 A2
We observe from the different matrices produced. To illustrate the decision making of the matrix allocation optimizer, we show an example of a matrix allocation in figure II.

In general, slower DNNs responsible for the performance bottleneck of the ensemble are multi-threaded in priority and their batch size optimized. Furthermore, we observe that when some models are co-localized their batch size is often chosen smaller. Finally, when we increase the number of GPUs, algorithm 2 automatically stops using the CPU. Indeed, the CPU is only used by Algorithm 1 and Algorithm 2 when the GPUs memories are full.

In addition to measuring the throughput, we also measure the good stability of this throughput for any allocation matrix. This is a desirable property for some industrial applications where the server must guarantee a certain quality of service. More formally, the function bench(A,f ake data) (algorithm 2) returned values varies to a relative standard deviation (RSD) below 2% for any A. We also measure that when the rate max neighs/total neighs is low (e.g., inferior to 0.2) the bounded greedy algorithm can return diverse matrices performance at different run-time until RSD=16%.

C. Baseline comparison

We compare in table III our allocation matrix optimizer with the commonly used strategy we named BBS as baseline. The BBS uses n GPUs for n models and for each model it searches for the optimum batch size. It requires the same amount of GPUs as DNNs, this is a major limitation that requires small ensembles or it requires large hardware investment.

BBS baseline

Our server img/sec #bench img/sec #bench

IMN1

CONCLUSION

This work answers this missing piece of pipeline between DNNs built by machine learning practitioners and serves them efficiently with any hardware investment. We propose a solution to the complex allocation problem of multiple heterogenous DNNs in multiple heterogeneous GPUs. This flexibility relies on the formalism of the allocation matrix allowing dataparallelism, co-localization, and batch size optimization.

To target efficiency, hundreds of allocation matrices are assessed before selecting the best one and instantiating it. And more, the inference system is built with many asynchronous processes to avoid overhead and accelerate the predictions. In our benchmarks, we observe the smart decision of our allocation optimizer. When the number of GPUs is superior to the number of DNNs, the heavier DNN are automatically multithreaded to avoid bottleneck performance. On the opposite, when the number of GPUs is lower, we observe automatically co-localization and smaller batch size to fit all DNNs into the memory.

Finally, each part of the proposed pipeline is well identified to guarantee easy code adaptation to facilitate introduction in current inference servers. For example, Object Detection and classification require different combination rules. To benefit from hardware-specific optimization, changing the inference framework requires localized updates into the predictor process.

Fig. 1 .

 1 Fig.1. Illustration of our inference server on a toy example of allocation of 2 DNNs into 3 devices. The DNN model B is run by 2 data-parallel workers on device J and device K. The DNN instances A1 and B1 are co-localized in device J. The corresponding allocation matrix is described in the bottom left corner. Threads inside a worker are not fully described for visibility purposes (see figure2).

Fig. 2 .

 2 Fig.2. Anatomy of a worker. The meaning of arrows is the same than figure1

1 :

 1 input: M the list of DNN models in the ensemble, D the device set, def ault batch size 2: output: A the allocation matrix containing all models placed 3: start 4: A m,d ← 0, m = 1...card(M ) and d = 1...card(D) 5: M sorted in desc. order of memory size 6: for m in M do 7: 8: // AG is the matrix where m is put on the GPU-side 9:g ← more remaining memory(A,def ault batch size,'GPU') is the matrix where m is put on the CPU-side 14:c ← more remaining memory(A,def ault batch size,'CPU') no device have enough memory 25:

1 :

 1 input: max iter maximum number of greedy iteration, max neighs maximum number of neighboors to evaluate at each iteration, A is the zeroed allocation matrix, calib data contains calibration data to perform offline benchmarks 2: output: The optimized allocation matrix A 3: start 4: A speed ← bench(A,calib data) 5: iter ← 0 6: while iter < max iter do best A, best speed ← for all n in neighs return the best one and its score based on the bench(n,calib data) criterion

	7:	neighs ← neighborhood(A)
	8:	if length(neighs) > max neighs then
	9:	neighs ← draw randomly max neighs samples
		from neighs A
	10:	end if
	11:
	12:	if best speed > A speed then
	13:	A ← best A
	14:	A speed ← best speed
	15:	iter ← iter + 1
	16:	else
	17:	// local maxima (or plateau) detected
	18:	iter ← max iter greedy
	19:	end if
	20: end while
	21: return A
		III. OFFLINE BENCHMARK SETTINGS

TABLE I WE

 I BENCHMARK THE THROUGHPUT OF 5 ENSEMBLES ON DIFFERENT NUMBERS OF GPUS (+1 CPU). THE MENTION '-' MEANS OUT OF MEMORY ERROR IS RETURNED. BECAUSE A2 IS A STOCHASTIC ALGORITHM, EACH RUN TIME WAS PERFORMED 3 TIMES AND THE MEDIAN VALUE IS REPORTED.

		ResNet50 ResNet101 DenseNet121 VGG19
	CPU	0	0	0	0
	GPU1	8	8	0	0
	GPU2	0	128	0	0
	GPU3	0	0	8	0
	GPU4	0	0	0	8
			TABLE II
	ALLOCATION MATRIX OF IMN4 ON 4 GPUS RETURNED BY OUR
			ALLOCATION MATRIX OPTIMIZER

TABLE III COMPARISON

 III BETWEEN TWO ALLOCATION STRATEGIES: THE SIMPLE PREFERRED BATCH SIZE STRATEGY AND OUR PROPOSED ALLOCATION MATRIX OPTIMIZER WITH DIFFERENT ENSEMBLES (FROM IMN1 TO IMN12) AND DIFFERENT GPUS (+1 CPU EACH TIME). THOSE TWO STRATEGIES PRODUCE AN ALLOCATION MATRIX FOR THE INFERENCE SYSTEM AND BENEFIT FROM THE HIGHLY ASYNCHRONOUS INFERENCE SYSTEM DESIGN AND LOW BOTTLENECK. THE LAST LINE WE SET max iter = 20.

"https://github.com/triton-inference-server/model analyzer/blob/main/ docs/config search.md"

Acknowledgement: We would like to thank TotalEnergies SE and its subsidiaries for allowing us to share this material and make available the needed resources.