{'fraction_non_alphanumeric': 0.02115338212820719, 'fraction_numerical': 0.008485482184508968, 'mean_word_length': 4.98339749759384, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An Anycast Communication Model for Data Offloading in Intermittently-Connected Hybrid Networks

For billions of people, mobile phones have become essential communication means to produce and share multimedia contents. Most current sharing solutions rely on centralized online solutions, requiring a permanent Internet connectivity, with the consequence of increasing –and sometimes of overloading– the networks of mobile operators. This paper presents an anycast communication model allowing to ofﬂoad data in wide intermittently-connected hybrid networks, using a peer-to-peer approach. Such networks combine an infrastructure part that relies on ﬁxed equipments with intermittently or partially connected parts formed by mobile devices. This model has been implemented in a middleware platform called Nephila. Simulation results conﬁrm that, with Nephila, thousands of people roaming a medium-size city center can share multimedia contents, using a combination of stable and transient transmission links.


Introduction
Mobile phones and tablets have undoubtedly become the preferred -and sometimes the exclusive-communication means for billions of people. With the generalization of 4G networks, people are prone to share an ever growing volume of multimedia contents (e.g., photos, videos), usually using centralized social-based online platforms. In some circumstances, such as during peak times in crowded metropolitan environments, people may experience long latencies, low throughput, and even network outages due to congestion induced notably by the simultaneous production and consumption of large amount of multimedia content. To cope with these problems, mobile operators usually resort to mesh networking techniques and deploy numerous base stations providing small communication cells (i.e., Wi-Fi access points, femtocell devices). Mesh networking projects, such as RoofNet 1 , Serval 2 and OpenGarden, have shown that it is possible to provide nomadic users in cities with broadband multi-hop connectivity to the Internet, thanks to a set of Wi-Fi access points acting as mesh routers and forming a backbone infrastructure with a limited number of wired links to the Internet. However, several issues must be addressed to relieve the mobile operator networks using such mesh networks. Indeed, the mobility of people, the short communication range of wireless interfaces, radio interferences and the volatility of the devices -which are frequently switched off in order to reduce their power consumption-can yield frequent and unpredictable disruptions in communication links, thus entailing the creation of connectivity islands in the ad hoc segments of the network. Maintaining end-to-end connectivity between all network nodes then becomes quite a challenge, as solutions relying on the IEEE 802.11s standard or on dynamic routing protocols designed for MANETs (Mobile Ad hoc NETworks), such as RoofNet and OpenGarden, prove unable to ensure message forwarding in such conditions. They indeed assume that the network is dense enough, so it can be viewed as a fully connected graph over which end-to-end paths can always be established. Such an assumption proves unrealistic in many real situations.
In their inventory of offloading techniques in cellular networks 3 , Passarella et al. underline the same issues and conclude that non-cooperative models relying exclusively on cellular base stations or Wi-Fi access points, such as 4,5 , do not efficiently work in sparse networks where devices may be disconnected for a long time, and so that offloading solutions exploiting both available infrastructures and opportunistic device-to-device communications, and implementing a cooperative data diffusion, must instead be used. Opportunistic communications help tolerate the absence of end-to-end connectivity in an intermittently-connected networks 6 . The communications rely on the "store, carry and forward" principle. The basic idea is to take advantage of radio contacts between devices to exchange messages, while exploiting the mobility of these devices to carry messages between different parts of the network. Two devices can thus communicate even if there never exists any temporaneous end-to-end path between them. Recent experiments conducted in real conditions have shown that applications such as voice-messaging, e-mail, or data sharing can indeed perform quite satisfactorily in networks that rely on the "store, carry and forward" principle 7,8,9,10 . Based on this observation, we argue that an interesting alternative and cost-effective solution may be to resort to new kind of hybrid networks combining an infrastructure part with intermittently or partially connected parts formed by mobile devices communicating in ad hoc mode. Figure 1 illustrates a worthwhile hybrid configuration that involves 1) mobile ad hoc networks formed spontaneously by the devices carried by people, 2) mesh routers deployed by mobile operators in locations where significant data transfers are expected (e.g., transportation hubs, shopping malls, campuses, homes, offices, etc.), 3) Wi-Fi access points installed and operated by volunteers. Some of these fixed equipments can be interconnected using logical links in order to form a backbone, and to support mesh networking. Such a hybrid configuration allows mobile devices to share data with one another without resorting to the network infrastructure (nodes N1, N2, N3 in Figure 1), to forward data from a mobile operator's network to the mobile ad hoc parts (node N4 in Figure 1), and conversely to forward data from the ad hoc parts to the infrastructure-based network. Additionally, mobile devices connected directly (node N5) or via an intermediate node (node N3) to a mesh router or to an access point can communicate with a remote mobile device (node N6) or with a fixed host (host H1) thanks to a backbone.
In this paper, we present an anycast communication model and a network healing mechanism that offer, in intermittently-connected hybrid networks, enhanced data exchanges between mobile devices and remote hosts accessible through standard access points. This communication model and this mechanism have been implemented in a middleware platform, called Nephila, with which we investigate communication and data offloading in wide ICHNs, using a peer-to-peer approach 11 .
The remainder of the paper is organized as follows. Section 2 gives a brief description of the Nephila platform. Sections 3 and 4 present the new mechanisms we have introduced in Nephila in order to support communications between mobile devices and remote hosts connected to the Internet, and compare our solution with existing related works. Section 5 presents evaluation results. Section 6 summarizes our contribution, and gives perspectives for future work.

Overview of the Nephila middleware platform
Nephila 11 is a middleware platform we have designed to support communications and data offloading in intermittentlyconnected hybrid networks (ICHNs) such as that described in Section 1. Nephila allows to build dynamically a decentralized and unstructured peer-to-peer overlay network to support the communication between mobile devices in a wide ICHNs. It also provides users of mobile devices with an enhanced Internet access in ICHNs thanks to an anycast communication model. This model permits to identify the standard access points with the same ID. It aims at reducing the message delivery delay while at increasing the delivery ratio, and therefore the quality of service provided to the end-users. This communication model is combined with a "healing" mechanism devised to stop the opportunistic dissemination of message copies in the network. This anycast communication model and this healing mechanism are detailed in the next sections.
Nephila performs a proactive discovery of fixed and mobile neighbor devices. This discovery relies on both a beaconing mechanism and a Cyclon-based service 12 . Based on this service, Nephila creates and maintains logical links between fixed devices so as to form a backbone. This backbone helps cover a wide area and support communications between remote mobile devices. The scalability of our system results from the existence of this backbone.
The messages emitted by the local applications, and those forwarded by neighbor devices, are stored by Nephila in a local cache until they expire, or until they are delivered directly to their destination. When two devices discover that they are neighbors, they exchange the messages they have in their local cache, thus implementing the "store, carry and forward" principle. In order to perform an efficient message forwarding, each device equipped with Nephila computes a list of so-called "trail values" (TV) and shares these values with its neighbors. A trail value computed by a device for a given destination reflects its capacity to forward a message to this destination, either directly or through intermediate devices. Disseminating such pieces of information can be costly because each device can maintain trail values for a large number of devices, even in the worst case for all the devices present in the network. In order to address this issue, we have implemented in Nephila a modified version of the Exponential Decay Bloom Filter (EDBF 13 ), which is itself an extension of the traditional Bloom filter that encodes probabilistic forwarding tables in a highly compressed manner. This modified version of EDBF is called TBF (for Trail Bloom Filter). It allows to store and disseminate efficiently the trail values of each device in the overlay system.
Nephila implements a forwarding algorithm called BTSA for "Best Trail Selection Algorithm (BTSA)". This algorithm uses the transitive property of the TBFs and promotes, while forwarding a message, the devices that met the destination of the message the most recently. To do so, each device takes a local decision based on its own TBF and on those sent by its neighbors. When a device receives a message from a neighbor or from a local application, it forwards this message to the neighbor that has the greatest trail value for the destination, provided that this value is greater than its own value. When a device receives a TBF from one of its neighbors, it looks for all the messages it maintains in its local cache, and it sends to this neighbor copies of the messages for which it considers the neighbor as a better forwarder than itself. More details about the BTSA algorithm can be found in 11 , together with simulation results that confirm its efficiency.

Anycast message delivery
In contrast of the anycast message delivery system proposed in 14 , the system we have designed is meant to be as simple and as generic as possible. It does not make assumptions about the mobility of the people. In 14 , each node computes its message delivery probability to the destination anycast group. Three different forwarding algorithms exploiting historical node encounter information are considered to guide the transmission of messages. Like in Nephila, the Group Forwarding Metric treats the entire group as a whole. It is defined as the probability of meeting any of group members to deliver message. The Probability Forwarding Metric is defined as the probability of encountering at least one anycast group member and delivering the message to the member. Finally, the Distance Forwarding Metric estimates the delivery probability to a group member as the distance to that member. In this anycast routing algorithm, a single-copy of a message is forwarded to the destination anycast group. So, it is suited for relatively dense opportunistic networks, where nodes have regular mobility patterns. Like in Nephila, the anycast routing algorithm presented in 15 does not make assumptions regarding the mobility of the nodes. Nevertheless, it supposes that messages can initially be sent only by stationary nodes, the mobile nodes only acting as message carriers. Obviously such a supposition is not realistic, because in practice contents are produced by users of mobile devices.
The anycast communication model implemented in Nephila does not impose a specific naming convention. For example, it can be used by mobile or fixed devices to announce that they provide a specific service (see Figure 2). Messages would then be indifferently forwarded by Nephila toward these mobile devices, thus improving the delivery delay and ratio of these messages. This system is used in Nephila to identify with an unique ID the fixed devices that offer an "Internet access". A message can thus be received, stored, carried and forwarded by several intermediate mobile devices, and be transferred to the destination through the same, or different, access point(s). Nephila does not include any coordination mechanism allowing mobile devices connected to standard access points to decide which one must forward a given message, or allowing them to announce to the other connected devices that they sent a particular message. Therefore, several copies of a message could be received by the destination. We assume that this feature is tolerated by the application.
As standard access points do not run the Nephila platform, the mobile devices connected to these access points will automatically add them in their list of neighbors, and identify these access points by their anycast common ID. This ID is obtained by applying a hash function on the name of the anycast group, and is disseminated like the ID of devices using trail Bloom filters.
When running in ad hoc mode, mobile devices can advertise the anycast groups they belong to in their beacon messages (as a hash value). Like for the access points, the ID of these anycast groups will be automatically added by the neighbor devices to their TBF. An example is shown in Figure 2. In this figure, the results of the hash function applied to anycast groups "Internet Access" and "Service#2" are respectively 12 and 13. In this example, node 3 can add 12 in its neighbor list, and node 2 can add both 5 and 13. Node 5 can thus be reached by node 2, using either its own identity (i.e., 5) or its anycast group identity (i.e., 13). Application-level messages that must be sent to remote hosts on the Internet will be encapsulated by the emitters in Nephila's messages, with the anycast group ID of access points as destination address (i.e., 12 in our example). These messages will be extracted from Nephila's messages by the mobile devices connected to the access points, in order to invoke the appropriated remote host on the Internet. These mobile devices will perform the reverse operation when they must forward a response back to the client mobile node. The Best Trail Selection Algorithm (BTSA) is let unmodified as anycast groups are transparent for it.

Healing mechanism
The "Best Trail Selection Algorithm" (BTSA) implemented in Nephila creates multiple copies of messages, and replicates these copies on intermediate nodes that are considered as good relays to deliver these messages to their destination. Some of these copies of messages can be disseminated in the network, while one of them has already been delivered to the recipient, because the deadline assigned to the message has not expired yet. To reduce the number of copies forwarded in the ICHN, we have implemented in Nephila a simple healing mechanism. This mechanism indicates to intermediate nodes that a message has been delivered, and therefore that they can remove any copy of this message from their local cache and thus stop forwarding it. This healing mechanism relies on the periodic broadcast of healing tables containing the IDs of the messages and their deadline. A mobile node also sends its healing table when it encounters a new neighbor. When the deadline of a message is reached, the mobile nodes remove the corresponding entry from their healing

Simulation and results
The first part of this section describes the scenario and the simulation environment we consider, and it enumerates the simulation parameters we used. The second part of this section presents the results we obtained, and discusses these results, mainly regarding message delivery delay and ratio. These simulation experiments were conducted using The One simulator 1 . One of the main objectives of this evaluation was to assess if data can efficiently be shared by mobile devices using Nephila in an ICHN.  The simulation environment is intended to be as realistic as possible. It involves a variable number of users of mobile devices that move freely in the streets of the French city of Vannes, which is a mediumsize city of about 50 000 inhabitants and whose area is about 25 km 2 . A variable number of access points are assumed to be distributed in the city. These access points are connected to the Internet. For the sake of realism, we have divided this set of access points in four distinct groups. These groups are managed by different mobile operators. Mobile devices carried by people and running Nephila can communicate directly together (in ad hoc mode) when they are in the communication range of each other, using either their Bluetooth or their Wi-Fi interface. They also can forward the messages they received opportunistically towards their destination, thanks to the Nephila middleware. We assume that mobile devices are configured to discover Wi-Fi access points, and to automatically connect to those managed by the operator of their respective owner. The mobile devices that are connected to access points can act as gateways between the mobile ad hoc parts and the infrastructure part of the network, thanks to their different wireless interfaces. In our simulation, only 100 pedestrians emit messages (requests) towards fixed host located on the Internet. The responses generated by these hosts are forwarded back to the emitters of the requests by Nephila.

Scenario and simulation setup
The duration of the simulations is 1 hour and 43 minutes. During the first 3 minutes, both fixed and mobile devices perform a discovery of their neighbors, and compute and disseminate Trail Bloom Filters (TBFs). After this warm-up period, mobile devices start a client/server application that sends messages during 1 hour. The application, and thus the emission of messages, is stopped 40 minutes before the end of the simulation in order to be able to evaluate how many requests and responses are really received by their final recipients, and how many messages are dropped. In our simulations, we assume that pedestrians move at a speed that varies between 1 m/s and 1.6 m/s. We performed simulations with 1000, 2000, 3000 and 4000 pedestrians. The environment is additionally populated by either 100, 200, 400 and 800 fixed access points. The lifetime of messages is set to 20 minutes. The communication range of the wireless interfaces is limited to 50 meters, and their bitrate to 10 Mbit/s. The bitrate of wired links is limited to 20 Mbit/s. The Nephila's parameters used for the simulations are defined in Figure 3 and Table 1. They were determined empirically through extensive experiments. Figure 4 presents the results we obtained for the delivery of messages (requests and responses) in terms of delivery ratio and delay. Requests are forwarded using the anycast forwarding mechanism we have implemented in Nephila, while the responses are sent back to the emitters of requests using a unicast forwarding mechanism. When the number of access points and pedestrians increase, both the delay and the ratio of delivered requests increase. A peak of 98% of delivered requests is reached for 800 access points and 4000 pedestrians. These results are consistent with what can be expected in such circumstances. Indeed, the probability of both encountering an access point and finding a forwarding path is higher in a dense network than in a sparse one. This is confirmed by results shown in Figures 4a and 4b. When the number of mobile devices is low (100), most of the requests are delivered directly, and this proportion gets higher as the number of access points increases. When the number of mobile devices and access points increases, we observe that most requests are delivered with a number of hops lower or equal to 4. For example, for 4000 pedestrians and 800 access points, 80% of the requests are delivered in at most 4 hops. Moreover, for 800 access points, the delivery time of most requests ranges between 0 and 200 seconds (see Figure 4b). The number of requests delivered in a short time increases significantly with the number of mobile devices. Figure 4c provides a comparison between the anycast forwarding mechanism implemented in Nephila and a traditional unicast forwarding mechanism considering the delivery ratio of requests for 800 access points. The results confirm the efficiency of our anycast forwarding mechanism, since 98% of requests are delivered in similar conditions with this mechanism, while only 20% are delivered with the unicast forwarding mechanism. Therefore, the forwarding mechanisms implemented in Nephila can be considered as efficients as they allow to forward messages towards both access points and mobile devices with a small number of hops, a high delivery ratio and a short delay.

Simulation results
As for the forwarding of responses, it can be observed that about 90% of them are delivered in a population of 100 mobile devices, and that this percentage decreases drastically for 500 mobile devices, before increasing slightly for larger populations of devices (see Figure 4d). The explanation resides in the fact that in an ICHN composed of only 100 mobile devices, the delivery of requests and responses is achieved almost exclusively by direct transmissions (i.e., 1 hop). This is why the delivery delay of responses is relatively short for 100 mobile devices, and why this delay increases when more intermediate devices are involved in the transport of a message (see Figures 4a and 4f). This delay increases more significantly when the number of access points is low, because forwarding paths between mobile devices and access points are more discontinuous than in an ICHN including many access points.
The impact of the healing mechanism on the volume of messages disseminated in the mobile parts of the ICHN is shown in Figures 4g and 4h. The efficiency of this mechanism depends on the number of messages that have been delivered, on the number of copies of messages stored on devices, and on the number of contacts between devices (since each contact is an opportunity for devices to exchange their healing tables). The efficiency gets higher as the number of devices increases. It allows to save up to 175 GBytes for 4000 pedestrians and 800 access points. The additional average load generated by this mechanism is shown in Figure 4h. In the worst case, the average cost per node is about 8.5kbit/s which is relatively low in comparison of the capacity of Wi-Fi links.

Conclusion and future work
Intermittently Connected Hybrid Networks (ICHNs) represent a specific class of intermittently connected networks, in which fixed equipments are interconnected together in order to form a backbone. In this paper, we have shown how ICHNs and a peer-to-peer overlay system such as Nephila could be used by mobile operators to offload data from their mobile network in order to improve the quality of service they provide to end-users. Nephila computes message forwarding paths based on information about past contacts between nodes, and using both utility-based functions and specific Bloom filters called trail Bloom filters. It forwards messages towards access points using an anycast communication model in order to improve both the message delivery delay and ratio. Finally, it implements a healing mechanism in order to reduce drastically the number of messages that are disseminated in the ad hoc parts of the ICHN. Simulation results confirm the efficiency of both the anycast communication model and the healing mechanism.
The current implementation of Nephila does not support 3G and 4G communications. Cellular technologies should be integrated in the platform in the near future. We also consider implementing QoS metrics regarding content delivery. Nephila will thus be able to exploit simultaneously multiple communication channels, and to select automatically the interface that allows to provide end-users with the best quality of service in terms of content delivery ratio and delay. It will also permit to offload traffic from mobile operator networks transparently whenever it is possible. Indeed, when neighbor users want to share content, or when the network of the mobile operator is overloaded, the system can automatically choose opportunistic communications if this type of communication is deemed to provide better quality of service.