Keywords

1 Introduction

The widespread use of low-cost sensing and actuating devices along with their inevitable connection to the Internet has led to the emergence of Internet of Things (IoT). IoT brings together a wide range of tiny smart devices, called “things”, that have sensing, communication and computing capabilities but are often limited in processing, memory and energy, and use low-power communication technologies such as IEEE 802.15.4 [1] and 6LoWPAN [2]. Such systems are known as Low Power & Lossy Networks (LLNs).

Data communication in constrained LLNs poses a number of challenging issues. For instance, in large-scale deployment of IoT systems, careful consideration should be devoted to ensuring reliable communication given the limited capabilities of LLNs. Moreover, applications must be able to adapt to highly dynamic network topologies which may be produced by disconnections caused by lossy links of LLNs. This is in addition to the mobility of ”things” which is a prevalent feature of numerous IoT applications found in e-health, smart grids, smart cities, transportation, and agriculture [3].

A number of researchers [4,5,6,7,8] have advocated the adoption of the Information-Centric Networking (ICN) paradigm [9] as a clean slate alternative to IP for satisfying the communication requirements of IoT applications. ICN is a new networking approach where “data” is fetched by “name” instead of host IP address. Since ICN is a data-driven model it can naturally support user mobility and data sharing which are important features prevalent in IoT environments.

One of the most prominent implementations of ICN is Named-Data Networking (NDN) [10, 11]. NDN is a promising networking architecture for the emergent IoT due to its inherent salient features such as caching, naming and stateful forwarding. In NDN, pieces of contents are named independently of their location, following a URL-like naming structure. Applications request contents from the network by sending interest packets that pull back data packets. Native features come along with this principle such as communication without establishing end-to-end connections and a name-to-address resolution. In addition, it is not necessary to maintain consumer-producer paths, thus providing native support of connection disruption resulting from mobility.

Most NDN strategies employ a broadcasting (or flooding) mechanism for interest forwarding [4]. However, in wireless NDN where nodes possess one communication interface, the broadcast storm problem [12] could cause serious degradation to system performance due to excessive channel contention, redundant packet retransmissions and collisions. As a consequence, much research efforts have been devoted to developing interest forwarding strategies that can mitigate the effects of this problem. For instance, Deferred Blind Flooding (DBF) [7] has been suggested for NDN over IEEE802.11 [13]. Furthermore, a number of similar lightweight mechanisms have been proposed for wireless devices [5,6,7]. However, such mechanisms cannot be used directly over IEEE802.15.4 due to their data-rate and resource limitations.

In this paper, we will argue that probabilistic broadcast owing to its simplicity and ease of implementation is an attractive alternative to blind flooding as well as existing forwarding strategies as the rebroadcast probability can be adjusted to reduce the number of retransmissions, and consequently mitigate the effects of the broadcast storm problem. Moreover, it suits the limited capabilities of LLNs as far as computation, communication, and energy are concerned. Our research has been motivated by the fact that probabilistic solutions have been widely explored in the context of wireless ad hoc network (MANETs) [14], vehicular networks (VANETs) [15], sensor networks (WSNs) [16], and more recently in IoT networks [17] assuming a traditional IP setting. However, there has been hardly any research that has investigated the merits of probabilistic interest forwarding for NDN over LLNs. As an effort towards filling this gap in the current literature, the objective of the present study is to explore the performance merits of probabilistic interest forwarding for NDN over LLNs using extensive simulations considering different network configurations for static as well as mobile scenarios.

The rest of this paper is organized as follows. Section 2 presents briefly the NDN paradigm. Section 3 describes some of the related research work on interest forwarding strategies that have been suggested for wireless NDN. Section 4 describes probabilistic broadcast which has been discussed mainly for the conventional wireless IP networks. Section 5 describes the simulation model along with the system parameters used in our performance evaluation study. Section 5 also presents and discusses the obtained performance results. Finally, Sect. 6 concludes this paper and offers possible extensions of this research in the future.

2 Named Data Networking (NDN)

In NDN consumers acquire data from producers by means of data names instead of IP addresses, without any need for establishing a prior connection between consumers and producers. To do so, NDN uses two types of packets: interest and data (please refer to Fig. 1 for the format of such packets) [11]. To request data, a consumer sends out interest packets denoted with a specified name prefix. Data packets, however, are only transmitted in response to received interest packets. Data packets can be transmitted by any network node which holds the corresponding data item, whether it is the original producer holding it in memory or an intermediate node holding it in its cache.

Fig. 1.
figure 1

Packet types in NDN.

Full size image

The structure of a node in wireless NDN is shown in Fig. 2. The network layer traditionally occupied by IP is replaced with an NDN layer [10]. A given node employs three data structures, notably the Content Store (CS), Pending Interest Table (PIT), and Forwarding Information Base (FIB). A node uses the CS to cache data packets temporarily, allowing them to be stored closer to consumers, and thus enabling them to satisfy interest packets quickly and with fewer transmissions to reach a consumer. A node uses the PIT to keep track of forwarded interest packets whose corresponding data packets have not yet reached the node. As a consequence, the PIT permits data packets to follow the reverse path to consumers. Moreover, the PIT permits nodes to identify and drop duplicate interest packets (i.e., interests with the same name prefix) in order to avoid routing loops that might be present in the network. Lastly, the FIB is populated by a routing protocol, as is the case with traditional routing tables, and contains name prefixes with the corresponding output faces leading towards potential data producers.

Data in NDN is identified by names possessing a hierarchical sub-name structure, with each sub-name component separated by a slash similar to web addresses [10, 11]. For instance, country/city/town1/temperature would identify the temperature of town1 whereas country/city/town1/wind would correspond to the wind speed in town1.

Fig. 2.
figure 2

The typical node architecture in NDN.

Full size image

Data retrieval in NDN occurs as follows. A consumer sends out an interest packet with a specified name prefix in order to request data. Each node through which the interest packet passes first checks its CS for the corresponding data. If a match is found the data is sent back to the consumer without transmitting the interest any further. Otherwise, the node verifies if an interest corresponding to this name has already been registered in the PIT. If a match is found the interest is dropped. Otherwise a new entry is created in the PIT for this name prefix along with the incoming interface. The FIB is then used to determine the interface through which the interest is forwarded in the network. Upon arriving at a node that possesses the data (be it the original producer or an intermediate node), the node sends back a data packet, containing the requested content following the reverse path of the interest using the “breadcrumb trail” in the PIT at the intermediate nodes. It is worth noting that if the consumer does not receive a data packet within a time interval it re-transmits the interest. A consumer may have to perform several retransmissions before a data packet is received.

3 Related work

It is crucial to develop forwarding strategies that can help alleviate the broadcast storm problem while preserving the limited scarce resources (e.g., battery power) of wireless NDN. This section reviews some existing forwarding methods suggested for wireless NDN. We will primarily assess the suitability of these methods in meeting the constraints of LLNs, most notably their communication, memory, and energy requirements.

Deferred Blind Flooding (DBF) [7] uses a simple method to reduce broadcasts by means of delays. Prior to transmitting an interest, a node waits for a fixed period of time to listen to surrounding broadcasts. If the same name prefix is heard above a specific threshold, the transmission is cancelled. Due to the extensive use of time delays, this scheme may not be suitable for time-critical applications.

The authors of [8] have described a Geographic Interest Forwarding (GIF) approach. GIF involves a neighbor discovery phase using control HELLO packets, and a producer discovery phase which is initiated by data producers in order to announce their presence to consumers. GIF uses geo-coordinates of nodes in addition to HELLO control packets which may result in a large amount of transmissions. As a consequence, GIF may put too much strain on the scarce resources of constrained wireless networks such as LLNs.

The study of [5] have proposed Reactive Optimistic Name-based Routing (RONR). Initially, interest packets are blindly flooded through the network. Once a consumer receives a data packet all subsequent interests are sent using the reverse path followed by the initial data packet. This method does little to support mobility or failure of nodes as any path breakage causes the scheme to default to blind flooding.

In Neighborhood-Aware Interest Forwarding (NAIF) [6] the forwarding rate of a given node is adjusted for each name prefix based on the amount of overheard interest packets with the same name prefix. If the number of packets heard is above a certain threshold, the forwarding rate for that name is lowered. Similar to BDF, this method may also not be suitable for time-critical applications due to listening periods. It also requires large memory capacity due to nodes having to store information for each name prefix.

Dual Mode Interest Forwarding (DMIF) [18] relies on two alternating interest forwarding modes; flooding and directed. If the name prefix for the interest to be forwarded is present in the FIB, the interest is forwarded in the directed mode to the next hop. Otherwise this method defaults to blind flooding. DMIF requires memory bandwidth as information in the FIB has to be stored for each name prefix.

The work of [19] has recently described a Learning-based Adaptive Forwarding Strategy (LAFS) for NDN-based IoT systems. Initially, interest packets are forwarded using a mechanism similar to DBF. The next phase in LAFS is started when producers respond with data packets. Upon receiving a data packet, each intermediate node stores information about the previous node, namely its ID and distance (in hop count) to the data producer for each name prefix. The name prefix is then considered as marked, and every subsequent received interest packet is transmitted without delay, while unmarked interests are transmitted after a delay period as in DBF. While this method does succeed in reducing the amount of flooded interest packets, it requires storing information related to each name prefix.

In Reinforced Learning (R-LF) [20] nodes use a reinforcement learning technique to adjust the amount of delay prior to transmitting an interest packet. Initially, interest packets are flooded until a producer node receives a copy of the flooded interest. The producer then responds with a data packet containing an initial cost based on the distance to the data producer and each subsequent node on the path then updates the cost until reaching the consumer. The nearby nodes that overhear the packet can also perform an update to learn their eligibility to the data producer. The cost is then constantly updated in the reinforcement phase and is used to compute the delay at each node. This method has been shown to exhibit a good interest satisfaction rate and low control overhead. However, nodes have to keep cost values for each name prefix which may result in high memory requirements.

Listen First Broadcast Later (LFBL) [21] is an improvement of DBF whereby instead of having nodes delay for a random period of time, each node determines whether it is an eligible forwarder or not based on its distance to the data source. If a node is an eligible forwarder, it delays for a time period that is proportional to its distance to the producer. LFBL requires holding distance tables which can be a problem in a setting such as LLNs due to their memory limitations.

4 Probabilistic Broadcast

Probabilistic broadcast schemes have been widely reported in the literature [14] due to their attractive features as they have been shown to manage to strike balanced energy usage, reduced communication overhead and reliability toward failures and network dynamism. The survey study of [14] has classified the existing probabilistic broadcast schemes into fixed schemes where all the network nodes have the same fixed forwarding probability, and adaptive schemes where the forwarding probability is adaptively adjusted depending on some system parameter(s) such as network density, node energy, or the number of received packets.

Most existing probabilistic broadcast schemes have been developed for the IEEE 802.11 technology [13], and as a result they may prove inadequate for LLN-based IoT systems. Moreover, broadcast schemes proposed for 6LoWPAN-RPL such those in [22, 23] suffer from a number of shortcomings as they rely on the RPL DODAG structure, and thus they have little support for network mobility, and can be affected by the “energy hole” problem [24] since closest nodes to the root, where traffic is heavy, are prone to wasting much of their energy.

In the fixed probabilistic scheme, a node retransmits a packet with a probability p for the first time a packet is received. In the present study, we assume that all nodes have the same probability of retransmitting a packet. This scheme turns into blind flooding when p = 1. Although probabilistic broadcast schemes have been discussed for wireless networks including MANETs [14], VANETs [15], and WSNs [16], their performance properties have not yet been explored for interest forwarding in the recently-emerging IoT systems based on NDN over LLNs.

The main challenge in probabilistic broadcast is the mechanism by which the optimal forwarding probability is decided. It has been demonstrated that a probability between p = 0.59 and p = 0.65 [14] can be considered as ideal for fixed probabilistic schemes in MANETs and WSNs. However, it is not obvious if such values are still valid for IoT environments and in particular for those based on NDN over LLNs since the operating principle of NDN is entirely different from that of traditional IP networks. Furthermore, the optimal forwarding probability may depend not only on the graph-theoretic properties of network topologies including node density and distance but also on the used transmission technologies. We say this because most existing research studies have investigated the performance of probabilistic broadcast schemes assuming IEEE 802.11 technology [14,15,16]. In contrast, LLNs are based on IEEE 802.15.4, and thus have different characteristics in terms of communication and battery power. More importantly, in order to prolong their battery lifetime, IEEE 802.15.4 devices employ a duty cycle mechanism that allows them to sleep by completely switching-off radio transceivers for predefined time periods and waking up for short time intervals to check for eventual communication. Such a mechanism undoubtedly would affect broadcast communication [24].

5 Performance Evaluation

We have performed an extensive performance evaluation in order to determine the optimal forwarding probability in the context of NDN over LLNs. To do so, we have implemented probabilistic broadcast in ndnSIM 2.8 [25]. The IEEE 802.15.4 communication standard has been employed providing a data link service to the NDN layer which is responsible for forwarding interest and data packets. We have considered square grid topologies where the distance between a given pair of nodes is fixed at 50 m. Table 1 provides a summary of the main parameters which have been used in our present study. It is worth noting that such parameters have also widely been adopted in existing research work [4,5,6,7, 17, 18].

Table 1. Summary of the simulation parameters.
Full size table

We have used the following performance metrics, which have been widely adopted in similar evaluation studies [4,5,6,7,8].

  • Interest satisfaction rate: the total number of data packets successfully received by the consumer over the total number of interest packets transmitted by the consumer.

  • Number of sent interest packets: the total number of interest packets that have been forwarded in the network.

  • Interest satisfaction latency: defined as the time taken by an interest packet to reach the producer, plus the processing time of the interest at the producer, and the time taken by the data packet to reach the consumer.

It is worth noting that the number of sent data packets is in general lower than the total of sent interest packets as the former are not flooded but rather follow the reverse path of interest packets to reach consumers. We have collected the statistics for the number of data packets. However, we have not included them in the discussion below due firstly to space constraints.

In what follows, we will present simulation results which have been gathered when the forwarding probability p has been varied in order to assess the impact of this crucial factor on system performance. After that, we have selected the values of p which produce the best performance outcome for the probabilistic forwarding and compared it against that of blind flooding, DBF proposed in [7] and LAFS which has been recently proposed in [19].

5.1 Static Scenario

We have considered three network sizes of 10 × 10, 8 × 8, and 6 × 6 nodes arranged in a square grid topology. In our experiments, the consumer is located at the corner whose coordinates are (0, 0) while the producer is the opposite corner along the diagonal. The consumer issues interest packets each with a different name prefix with a rate of 1 packet/second. We have varied the forwarding probability p from 0.3 to 1; probabilities below 0.3 have been found not to permit any interests to reach the producer.

As depicted in Fig. 3, system performance in terms of the interest satisfaction rate improves as the forwarding probability increases. A similar performance trend for the probabilistic broadcast has been reported when applied in other contexts such as MANETs and WSNs [14]. However, while in existing studies have found that the probability values between p = 0.59 to p = 0.65 provide the best performance results and that any further increase in the forwarding probability yields diminishing returns; i.e., very little improvement in performance. In our case we have noticed the best probability value is p≈0.85 which is higher than that reported in [14]. When p ≈ 0.85, the interest satisfaction rate reaches 75% which is comparable to that achieved by higher probability values including p = 0.90 and p = 1 (i.e., blind flooding).

In order to provide justification as to why the forwarding probability is found to be higher in our considered scenario than in MANETs or WSNs, we should mention first that communication between adjacent nodes has been found to always occur along the X or Y dimension and not along the diagonal as the signal loses much of its power due to the longer distance along the diagonal. This results in the consumer and producer being separated by the longest distance in the network (i.e., the network diameter). The higher p value also results from a higher chance for packet collisions due to the presence of the hidden and exposed node problems in the square grid topology. Moreover, the consumer and producer are both located at the opposite corners of the grid, and thus packets always encounter fewer alternative paths as they approach these corners compared to other network regions such as the center of the network.

Figure 4 presents the results for the interest satisfaction latency (in µseconds). In contrast to the results above, the results reveal that the forwarding probability p = 0.70 results in a huge decrease in latency, and further increase in p decreases latency. Latency is found to always decrease with p. This is because as the forwarding probability increases the likelihood of an interest packet reaching the producer quickly increases since most intermediate nodes transmit the interest packets instead of dropping them and thus avoid the need for interest retransmissions by the consumer.

Figure 5 shows that as the forwarding probability increases the number of sent interest packets increases. This results in more traffic load on the network and therefore increased competition for network resources (i.e., channel access). Such competition increases the chance of packet collisions, resulting in the interest satisfaction rate reaching a plateau at 75%, and not increasing even if p is increased further.

Fig. 3.
figure 3

Interest satisfaction rate versus forwarding probability for different network sizes.

Full size image
Fig. 4.
figure 4

Interest satisfaction latency (in µs) versus forwarding probability for different network sizes.

Full size image
Fig. 5.
figure 5

Number of sent interest packets versus forwarding probability for different network sizes.

Full size image

5.2 Mobile Scenario

In this set of experiments, the location of the consumer is fixed at the coordinate (0, 0) whereas the producer is allowed to freely move across a square grid according to the random way point model with a speed of 20m/s and no pause time.

Figure 6 which depicts results for the interest satisfaction rate indicates that the interest satisfaction rate increases with increased forwarding probability as in the static scenario case. However, we have noticed the interest satisfaction rate can reach up to 85% which is higher than that achieved in the static case. This is because due to producer mobility interest packets have to often travel shorter distances in order to reach the producer. Similarly, data packets have to travel a shorter distance to reach the consumer.

Figure 7 presents the interest satisfaction latency as a function of the forwarding probability. The forwarding probability p = 0.60 as opposed to p = 0.70 (for the static case) results in a considerable decrease in latency, and again further increase in p always decreases latency. Examining Fig. 8 for the number of sent interest packets reveals that similar performance trends are observed as in the static case.

Fig. 6.
figure 6

Interest satisfaction ratio versus forwarding probability for different network sizes.

Full size image
Fig. 7.
figure 7

Interest satisfaction latency (in µs) versus forwarding probability for different network sizes.

Full size image
Fig. 8.
figure 8

Number of sent interest packets versus forwarding probability for different network sizes.

Full size image

5.3 Performance Comparison

We have compared the performance of probabilistic interest forwarding against that of blind flooding, DBF and LAFS; we will limit our discussion to the static scenario due to space limitations and also due to the fact that the relative performance merits of these competing schemes have been found not to change much in the mobile scenario. Again, the consumer and producer are located at the opposite corners of the square grid. The consumer generates interest packets at a rate of 1 packet/second.

Figure 9 depicts the interest satisfaction rates. We notice that setting p = 0.85 enables probabilistic forwarding to achieve a similar performance to that of that blind flooding and LAFS. DBF has been found to exhibit the lowest interest satisfaction rate. This is due to the fact in DBF intermediate nodes may drop interest packets if certain number of duplicate packets are heard regardless of the fact these packets may happen to be close to the consumer or producer nodes.

Fig. 9.
figure 9

Interest satisfaction rate in different forwarding schemes. Network size =  8 × 8.

Full size image
Fig. 10.
figure 10

Interest satisfaction latency (in µs) in different forwarding schemes. Network size = 8 × 8.

Full size image
Fig. 11.
figure 11

Number of sent interest packet in different forwarding schemes. Network size = 8 × 8.

Full size image

We notice in Fig. 10 which presents the interest satisfaction latency that whereas latency in the probabilistic scheme is comparable to that of blind flooding, it is slightly higher compared to DBF and LAFS. On the other hand, examining Fig. 11 reveals that in probabilistic forwarding with p = 0.85 the number of sent interest packets is lower by 15% than the other competing forwarding methods. BDF manages to lower the number of sent interest packets but at the expense of severely degrading the interest satisfaction rate (see Fig. 9).

6 Conclusions

Probabilistic broadcast has been widely explored for various classes of wireless networks including ad hoc, vehicular, and sensor networks. However, there has been hardly any research that has investigated the performance merits of such a scheme in the context of Named Dated Networking (NDN) over low-power and lossy networks (LLNs) which are based on the IEEE 802.15.4 standard. In an attempt to fill this gap, this paper has suggested the adoption of probabilistic broadcast for interest forwarding in NDN over LLNs. The simplicity and ease of implementation of probabilistic broadcast schemes make them suitable for NDN over LLNs as they do not impose any additional requirement in terms of computation, communication, or storage on such constrained devices. Furthermore, probabilistic broadcast schemes do not need any topology specifications, and consequently enable NDN to operate alongside any routing protocol and can easily adapt to mobile scenarios and help mitigate network dynamics.

Our simulation results have revealed that for our examined scenarios setting the forwarding probability at around p ≈ 0.85 can yield good system performance in terms of the interest satisfaction rate. Moreover, such forwarding probability have been shown to achieve comparable interest satisfaction rate to that of the well-known blind flooding, DBF and LAFS while requiring a lower number of sent interest packets, and consequently resulting in lower energy consumption.

In the future, we plan to introduce enhancements to probabilistic forwarding by allowing nodes to dynamically adjust the forwarding probability in response to varying network conditions such as traffic congestion and node mobility. Moreover, we plan to extend our performance comparison to include other forwarding schemes such as R-LF and DMIF.