INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL ISSN 1841-9836, 12(1):131-147, February 2017. Delay/Disruption Tolerant Networking-Based Routing for Rural Internet Connectivity (DRINC) C. Velásquez-Villada, Y. Donoso Carlos Velásquez-Villada*, Yezid Donoso Systems and Computing Engineering Department Universidad de los Andes Bogotá D.C., Colombia, South America *Corresponding author: ce.velasquez917@uniandes.edu.co ydonoso@uniandes.edu.co Abstract: Rural networking connectivity is a very dynamic and attractive research field. Nowadays big IT companies and many governments are working to help connect all these rural, disconnected people to Internet. This paper introduces a new routing algorithm that can bring non-real-time Internet connectivity to rural users. This solution is based on previously tested ideas, especially on Delay/Disruption Tolerant Networking technologies, since they can be used to transmit messages to and from difficult to access sites. It introduces the rural connectivity problem and its context. Then, it shows the proposed solution with its mathematical model used to describe the problem, its proposed heuristic, and its results. The advantage of our solution is that it is a low-cost technology that uses locally available infrastructure to reach even the most remote towns. The mathematical model describes the problem of transmitting messages from a rural, usually discon- nected user, to an Internet connected node, through a non-reliable network using estimated delivery probabilities varying through time. The forwarding algorithm uses local knowledge gathered from interactions with other nodes, and it learns which nodes are more likely to connect in the future, and which nodes are more likely to deliver the messages to the destination. Our algorithm achieves an equal or better performance in delivery rate and delay than other well-known routing protocols for the rural scenarios tested. This paper adds more simulation results for the proposed rural scenarios, and it also extends the explanation of the mathematical model and the heuristic algorithm from the conference paper "Delay/Disruption Tolerant Networks Based Message Forward- ing Algorithm for Rural Internet Connectivity Applications" [1] (doi: 10.1109/IC- CCC.2016.7496732).a Keywords: dtn routing, opportunistic forwarding, rural connectivity, rural internet, non-real-time communications. aReprinted (partial) and extended, with permission based on License Number 3958950667073 ©[2016] IEEE, from "Computers Communications and Control (ICCCC), 2016 6th International Conference on". 1 Introduction The United Nations declared access to Internet as a human right in 2011 [2]; however, around 60% of the world population [3], especially in rural and underdeveloped regions does not have any Internet access. Access to Internet can improve life quality through access to more information, education and applications that will ease the life of citizens in remote areas [2]. Giving access to Internet to these communities is not an easy task. There are many technical and social challenges, such as a reliable supply of electricity, access to electronic devices, network coverage, education and training, that have to be overcome before a complete solution can be given. Copyright © 2006-2017 by CCC Publications 132 C. Velásquez-Villada, Y. Donoso Internet connectivity around the world is estimated at 43.4% (individuals using the Internet) for 2015 [3] and it is even lower for developing countries (35.3%) and population in rural areas (see Figure 1). Many benefits of Internet connectivity for rural communities in areas such as education, health-care, agriculture, economics and politics, among others, have already been dis- cussed in one of our previous papers [4]. There are also benefits based on the local infrastructure deployed, since users can create contents and share them with neighbors or other local users, local news can be reported on a local website, and people can share their music, documents, videos or libraries. In some communities, people have created local websites for their businesses and even local radio stations over the infrastructure that also allows them to connect to Internet. These applications depend on a strong deployment of a local infrastructure and the presence of people willing to train and educate local users. Internet connectivity, then, seems associated with more possibilities of bridging the social divide and reducing the social and economic gaps around the world. Figure 1: Individuals using the Internet. a) Developed Countries, Developing Countries and the World. b) Statistics by World Region. Information taken from [3] How to connect world’s rural population to Internet is a current and important global issue. Many big companies in Information Technologies, like Google and Facebook, are testing tech- niques and methods to help connect these currently disconnected rural users. Governments are trying to cover more of their territories, through contracts to deploy the necessary infrastructure and pushing local Telecommunications Companies to cover more towns. Networking equipment providers also expect an increase in coverage through more energy efficient equipment. Google has recently launched an initiative to use stratospheric balloons to connect the whole world at low costs, and Facebook is developing a model of free restricted internet access in partnership with governments and cellular carriers. These and other initiatives for rural connectivity, will be discussed in more detail in Section 2. This paper proposes a routing and forwarding algorithm for a low cost technology that can be used over local user devices for non-real-time communications. This solution will allow people to ask for and retrieve information from Internet, for non-real-time applications, using transportation vehicles to carry their requests and replies. Figure 2 offers a schematic view of the possible scenario for this connectivity problem. The proposed solution will need an additional infrastructure that can be installed on buses or other mechanical transportation means to remote towns, and a device that can be installed at the main building in the town to serve as a request center. It will also need an application for people to install on their devices so they could be able to send requests to the request center or to the transportation device, and obtain their answers when the transportation returns to town; however, there will be no guarantees about delivery times or even deliveries at all. Users will be connected in a non-real-time fashion to Internet. This technology uses Delay and Disruption Tolerant Networks (DTN) to connect Delay/Disruption Tolerant Networking-Based Routing for Rural Internet Connectivity (DRINC) 133 everyone to Internet using non real-time communications based on the DTN Architecture [5] and inspired on Daknet [6]. Daknet is a technology used to interconnect rural communities in India using mechanical transportation means. Daknet uses PROPHET [7] as its routing protocol to deliver and receive messages between users and Internet. However, as far as we know, there are not publications about its performance on field. We tested the official implementation of PROPHET in The ONE (Opportunistic Network Environment) Simulator [8] and compared our proposal against it and other well-known DTN routing protocols, in rural connectivity scenarios for developing countries. Figure 2: Proposed scenario for the rural connectivity problem This paper extends the conference paper [1]. The key additions of this journal version are as follows. First, Figure 4, has a small correction. It has an additional device in the Internet Connected town, to receive user’s requests and Internet replies. Section 2 includes and describes more related works, and DTN implementations for rural solutions. Besides, this paper contains an extended explanation of the mathematical model and of the heuristic algorithm from Section 3. Finally, this paper contains additional results for the simulated scenarios. This document is divided as follows: Section 2 presents a review about rural internet network- ing. It reviews some connectivity technologies and initiatives that are currently being tested and developed around the world for rural internet connectivity. It also contains a brief description of the most important protocols in the state-of-the-art of DTN routing protocols that can be used for rural connectivity. Section 3 gives a detailed description of our proposed mathematical model, solution architecture, and forwarding algorithm developed in this research. Section 4 analyses the simulation results, including the comparison with other protocols. Finally, Section 4 presents general conclusions, highlighting the most important achievements of this research, and it also states some possible directions for future work. 2 Delay/Disruption tolerant networks and rural networking 2.1 Delay/Disruption tolerant networks Delay/Disruption Tolerant Networks (DTN) are a recent kind of networking technology for environments with difficult conditions. DTN were developed for spatial communications to over- 134 C. Velásquez-Villada, Y. Donoso come the long distances (long delays) and frequent disruptions that are usual for this environment. From this research, the DTN Architecture [5] and the Bundle Protocol [9] were developed. The DTN Architecture describes a networking technology that has to be able to work on environ- ments with long delay and frequent disruptions. It relaxes several assumptions of the traditional Internet, including the ideas that there exists an end to end path between source and destination, that error correction based on acknowledgements is effective, that packet switching is the most appropriate abstraction for interoperability and performance, and that endpoint-based security mechanisms are enough. The Bundle protocol is the technical implementation of the DTN ar- chitecture. It proposes a new intermediate layer between the application layer and the transport layer. The Bundle protocol is independent of the networking and network access technologies, and it allows DTN nodes to exchange messages between neighbors as a relay for a transmission between distant DTN nodes. Figure 3 shows a graphical explanation of the bundle protocol position in the networking layered model. It shows that bundles can communicate between intermediate DTN nodes or between end DTN nodes. It also shows that transmitting a bundle from a DTN node to another is made via lower layer protocols, starting with the transport layer and finishing in the other node’s transport layer, and that this communication can be made over TCP/IP protocols or any other networking stack. It also shows that transmitting a single bundle between two DTN nodes can require the exchange of several segments, datagrams and frames between the inferior layers. Figure 3: Bundle layer as middleware between DTN applications and traditional networking protocols [10] 2.2 Rural internet networking Recently, there have been many initiatives to connect the unconnected part of the world. These unconnected citizens are, primarily, located at rural areas in developing countries. Main players in the IT world, like Google, and Facebook, are heading these initiatives. The next paragraphs summarize a review of a couple of their projects and a DTN-Based, rural connectivity Delay/Disruption Tolerant Networking-Based Routing for Rural Internet Connectivity (DRINC) 135 technology, the DakNet project. Google’s Loon [11] and Link [12] projects are some of Google initiatives to connect people to internet. These projects are focused on rural users in developing countries, but they are part of a Google’s initiative to connect more users to Internet and expand its business. The Loon project uses aero-static balloons that create a mesh network between them and several earth- based stations. These earth-based stations have internet connectivity via satellital internet or wireless links. The Loon project allows local users to send request to the balloon network (via LTE technology) and obtain a response in almost real time through the connection at the earth- based station. The Link project deploys optical fiber networks in metropolitan regions, and it builds Wi-Fi networks as last-mile solution for potential users. Google started the Link project in Uganda and it is expanding it in Ghana. It has installed or is currently installing five fiber optical networks in these two countries. They report that these networks have increased Internet connectivity availability and bandwidth. They allow users to access educational information, share medical results, expand the impact of their businesses and build cooperation networks between universities. Facebook’s Internet.org [13] and ARIES [14] projects are some of Facebook initiatives to connect rural people to internet. The Internet.org project, also called Free Basics, is an initiative in developing countries and rural areas where local users with a mobile phone can access a limited version of Internet via a local mobile carrier. Facebook, in agreement with local governments and mobile carriers, give this limited internet access free of charge. The ARIES project is one of the Facebook’s initiatives to bring connectivity to areas where there is not networking infrastructure available. ARIES is an antenna array that uses Multiple Input - Multiple Output (MIMO) technology to transmit up to 24 simultaneous streams over the same spectrum. It is a base station with 96 antennas that tries to improve the spectral efficiency of wireless communications, working at different frequencies and reaching 71 bps/Hz. Facebook is developing this technology with the idea to reduce deployment costs of networking in urban areas; besides, it is aiming at connecting, through this antenna, rural population living in a radius of 40 km. of urban centers. Facebook estimates that 97% of the world’s population live inside these areas. Governments are also investing in rural internet connectivity. In Colombia, the ICT Ministry created in 2011 the Proyecto Nacional de Fibra Óptica (National Optical Fiber Project) with the aim to connect to Internet all Colombian municipalities. This governmental contract had a cost of around 230 million USD. It was planned to be executed between 2012 and 2014 [15]. In recent declarations from the Colombian ICT Minister, he stated that the project currently covers around 90% of the Colombian municipalities. Although this is a big investment, it covers the main urban developments in Colombia; rural areas, near these municipalities, are not being covered by this project. DakNet [6], [16] is a rural connectivity solution based on DTN. DakNet has been in use for several years in India. DakNet installs kiosks in rural towns, where users can go and use a computer to communicate with other rural users or with Internet servers in a non-real-time fashion. Messages are stored in the local computer until a motorcycle or a bus stops by the town, collecting the messages via an access point installed on it. The vehicle will carry the messages to an Internet connected spot, where they will be delivered and the desired answers retrieved. DakNet uses PROPHET [7] as its routing protocol. DakNet is the main inspiration for the present work. 2.3 DTN routing protocols Epidemic routing [17] is the most known routing protocol for opportunistic networks. It replicates the messages it wants to deliver giving copies to every node it meets until the message 136 C. Velásquez-Villada, Y. Donoso gets to its destination. Epidemic guarantees the delivery of a message if enough resources, including time, are given. Spray and Wait routing [18] is the evolution of epidemic routing. It also is a replication-based routing protocol. It works in two phases, a replication phase where the node creates copies of the messages it wants to deliver, and give the copies to every node it meets, just like epidemic routing. The second phase is the delivery phase, in this phase the nodes stop the replication of messages and they will only pass the message to the destination node. PROPHET [7] is a probabilistic routing protocol based on the history of contacts between the nodes and transitivity. PROPHET estimates a delivery probability for every node it meets and decreases it by a constant factor over a constant time interval. It also can calculate the delivery probability for nodes it has not met, using intermediary nodes to deliver the messages (transitivity). A more detailed classification and comparison of DTN routing protocols can be found in reviews [19], [20] and [21]. The heuristic proposed in this paper uses ideas from some of the protocols described in this section. 3 DTN for rural internet connectivity 3.1 Proposed architecture This section presents a rural networking connectivity scenario, where communication requests will be originated from nodes in an usually disconnected rural area, to other nodes or towards Internet servers. The originating rural nodes make a mobile, sparsely distributed network. They will be able to communicate with each other and they could serve as relays to deliver messages to a static, always-on node in the nearest town, the Access Point (AP). The AP can store users’ requests until a Mobile Access Point (MAP) comes to the town and retrieves them. The MAP will store the requests from the small, disconnected towns it visits and it will deliver them at the drop point, an Internet Connected Node (IC) in a bigger, Internet connected town. The IC is the connection between the DTN for rural users and the usual Internet. The IC can deliver the rural users’ messages to the respective Internet Servers and retrieve their replies. All users’ replies will be stored in the IC until a MAP comes by and collects the replies for the users in any of the towns in its route. See Figure 4, for a general scheme of the proposed architecture. DTN nodes representing rural users are expected to get more sparsely distributed as they are located farther away from the town’s AP. They can use other DTN nodes to convey requests to the AP and to deliver replies from Internet to the final user. 3.2 Optimization Model for the Rural Internet Connectivity Problem This subsection introduces a new bidirectional, multiobjective, non-linear mathematical model for a DTN in a rural networking connectivity scenario. This model is extended and corrected from our previous models in [4] and [22]. This mathematical model maximizes the delivery prob- abilities over the paths that may exist through time, and at the same time it tries to minimize the mean delivery time for each message. This model optimizes through time the routing of mes- sages based on the availability probability of each link in a possible path. A path from a source node to a destination may not exist at a single moment but over various intervals. Also, the mathematical model will try to deliver all messages to their destinations, restricted to the links and buffers capacities and nodes’ availability probabilities given by their movements. See Figure 5 for a graphical representation of the mathematical abstraction. The mathematical model is presented in equations (1) to (7). Delay/Disruption Tolerant Networking-Based Routing for Rural Internet Connectivity (DRINC) 137 Figure 4: Proposed architecture for the rural internet connectivity solution The mathematical model assumes that there is a set of rural nodes (N), with intermittent connections (E) between a subset of them and the local AP. These connections are modeled through time dependant availability probabilities (aij(t)). If the availability probability at any given time for a couple of nodes is bigger than zero, a path can be formed using them. The set P represents the possible paths that can exist in the network through time. Delivery probabilities (dij(t)) are calculated using availability probabilities of neighboring nodes and their knowledge of a path to, or a node with previous contacts with, the destination. Nodes and links have capacities that should be respected. We assume that these capacities do not change over time, then, parameters cij and cii represent the link capacity from node i to node j and the node i capacity to store messages through time, respectively. Parameter bi(t) is a time based vector with demands and supplies for node i through time. All b vectors are grouped together in matrix B, representing the desired flow of information for the system. The model uses discrete times t. Table 1: Mathematical notation for the Rural Internet Connectivity problem Var./Param. Definition N Set of nodes, i ∈ N E Set of links, (i,j) ∈ E T Set of discrete time intervals t ∈ T P Set of paths, (i,j) ∈ P , aij(t) > 0 B Matrix of information demands and supplies, bi(t) ∈ B aij(t) Availability Probability of (i,j) ∈ E at time t dij(t) Delivery Probability of node i through node j at time t cij Capacity of link (i,j) ∈ E cii Storage capacity of node i δt Time interval duration xij(t) Data flow through link (i,j) ∈ E at time t 138 C. Velásquez-Villada, Y. Donoso Figure 5: Mathematical abstraction for the Rural Internet Connectivity problem Each of them represents a moment lasting long enough for a node to reliably transfer a message to a neighbor. The lasting of each time interval is modeled through the parameter δt. Forwarding decisions are made based on links’ availability probabilities, the size and the delivery time of the message. These decisions are represented by the positive integer variable xij(t), which represents how much information should flow over a link at any given time. Table 1 summarizes all the model’s parameters and variables. Objective Functions max ∏ (i,j)∈P dij(t)xij(t) (1) min ∑ t∈T δt∑ i∈N |bi(t)| (2) Constraints∑ j∈N xij(t) − ∑ j∈N xji(t) + xii(t) −xii(t− 1) = bi(t) ∀(i,j) ∈ E,i 6= j,t ≥ 1 (3) ∑ j∈N xij(t) − ∑ j∈N xji(t) + xii(t) = bi(t) ∀(i,j) ∈ E,i 6= j,t = 0 (4) xij(t) + xji(t) ≤ cijδt ∀(i,j) ∈ E,i 6= j (5) xii(t) ≤ cii ∀i ∈ N (6) xij(t) ∈ Z≥0 ∀(i,j) ∈ E,p ∈ P,t ∈ T (7) Equations (1) and (2) represent the objective functions intended to maximize the delivery probability of messages over all paths through time, and to minimize the mean time taken to Delay/Disruption Tolerant Networking-Based Routing for Rural Internet Connectivity (DRINC) 139 deliver all messages. Equations (3) to (7) state the mathematical model constraints. Equations (3) and (4) are data flow constraints, requiring all messages to be delivered to their destinations. Equations (5) and (6) are capacity constraints, requiring all transmission to be in the limits of buffers and links capacities. Finally, equation (7) states that the decision variable is a positive integer variable defined over all available paths through time and representing the data flow over an edge for a time interval. 3.3 Heuristic approach of the proposed solution for the rural internet con- nectivity problem Every user in the rural networking connectivity scenario, shown in Figure 4, should use a distributed routing algorithm to deliver all its messages to their destinations. The proposed algorithm introduced in this subsection works with limited and local information. A node only knows where it is based on a general location abstraction given by a Uniform Resource Identifier (URI) described in the DTN Architecture [5]. Based on this general location it can direct its requests to the nearest AP. Each node must create two tables that it should save to a non-volatile memory. One table is for saving the name, address, availability probability, last contact time, average time between contacts and centrality of every node it meets (neighbors’ table). The centrality is a measure of how many nodes a neighbor has met, and it can be used to make forwarding decisions. Nodes with better centrality metrics will be preferred when no delivery probability to a destination is known. Delivery probabilities (d) are calculated from nodes that have a path to the destination. They can give a delivery probability based on previous contacts with the destination, and neighboring nodes of these nodes can have a delivery probability through them. Delivery probabilities are kept at a deliveries table. When a node wants to send a message to another node or to Internet (through the AP), it will create an entry in its deliveries table with the information about the neighbors with paths to the destination, the average time between contacts for each one of these neighbors, the delivery probability to the destination through the neighbors, and the estimated time to deliver the message given by the neighbor. DTN nodes will store in memory these tables, so they can forward messages in an effective way, minimizing time and maximizing the delivery probability. Nodes should have enough capacity to store own’s and neighbors’ messages. Since the com- munication model is not a real time one, this should not be a problem. Nodes will communicate using wireless links (IEEE 802.11g/n/ac or a similar technology) that will give them at least 50 Mbps, so a contact of a few minutes (a MAP visiting the location of an AP in the rural town) should be enough for a couple of nodes to exchange the messages (requests and replies) that they have for each other. The AP should have a significantly bigger memory capacity, since it is the bottleneck for all messages leaving the rural network and going to Internet. The memory size should depend on the frequency of delivery and reception of messages. If MAPs pass frequently by the AP’s position, the memory could be smaller than the memory requirement for APs where MAPs pass once a day or even less frequently. Figure 6 depicts a flow diagram representing the routing and forwarding algorithm for each DTN node. 4 Results for Rural Internet Connectivity Scenarios This section presents the results for different Rural Internet connectivity scenarios. These scenarios have several rural users distributed over a map, one AP, one IC, and one or more mobile APs, connecting the AP to the IC. These proposed scenarios are located around a small and remote town in Colombia, called La Macarena. It is a small community of about 500 inhabitants, with difficult access conditions. 140 C. Velásquez-Villada, Y. Donoso Figure 6: Flow diagram for the proposed algorithm for the Rural Internet Connectivity Solution There are currently three different ways to reach the town, a road to the nearest town (5 hours), two daily flights in small airplanes (for 5 to 10 people), and small canoes by the Guayabero river. This town also has a military base, where communication antennas work all day long. Rural users, then, have to go to the town in order to communicate to the capital or any other part of the country. We scaled the map around La Macarena using OpenJump [23] to use the mobility models of The ONE simulator. Rural DTN users are scattered around the town and they move around from the town to small farms nearby. There are roads from the town to most farms, also, the river is a very popular way of transportation. For our simulations, DTN users can generate messages at any time and they can receive replies from Internet (through the static node at the military base or from a MAP). Messages have to get to the center of the town, at the military base, to be transmitted to Internet. There are DTN nodes moving in their farms, neighboring farms and the town, MAPs going from the farms to the town and viceversa over roads and the river, and the AP in the military base in the center of the town. This simulation scenario can be seen in Figure 7. We created several scenarios changing the number of nodes (from 10 to 100 rural users), the size of messages (from 2 kB to 2 MB), and the time between messages (from 1 to 12 hours). These scenarios are described in Table 2. Messages are generated from rural DTN user nodes and the AP. These messages can be sent from user node to user node, from user node to AP or from AP to user node. MAPs only serve as relays to carry the messages from one location to another. Every scenario was tested for 3 simulated days (72 hours) with 5 different random seeds. The simulation results were obtained by changing the nodes’ buffers and changing the user nodes movement model from random to MapRoute (a model where nodes follow a predefined path at a constant speed defined randomly at the beginning of the simulation). We changed the nodes’ buffers from 10MB to 2000MB, but the results were always the same, they were not affected by the buffer size. We also changed the number of message replicas that our proposed algorithm uses; however, results were neither affected by replication number changes. At the end, our algorithm does not use replication. Results are shown in Figures 8 to 15. They show the delivery rate, delay, overhead, and hop count of our DRINC algorithm against PROPHET, Epidemic, and SprayAndWait routing protocols. It can be seen that DRINC achieves the same delivery rate or even a better one in some cases than Epidemic routing and PROPHET for the proposed scenarios, and that all Delay/Disruption Tolerant Networking-Based Routing for Rural Internet Connectivity (DRINC) 141 Figure 7: Scenario for the Rural Internet Connectivity problem based on La Macarena town in OpenJump Table 2: Simulation scenarios the Rural Internet Connectivity problem based on La Macarena town Scenario Parameters Number DTN nodes AP MAPs Message size Frequency 1 10 1 3 2 MB 1-2 hours 2 10 1 3 2 kB 1-2 hours 3 10 1 3 2 MB 1-12 hours 4 10 1 3 2 kB 1-12 hours 5 100 1 3 2 MB 1-12 hours 6 100 1 3 2 kB 1-12 hours protocols deliver more messages with the random movement of the user nodes than they do with the MapRoute movement model of the nodes. This could be due to the size of the scenario and that the random movement model gives more contact opportunities in this scenario. The 95% confidence intervals were calculated for every result and they appear in the figures. Figures 8 and 9 show simulation results for Epidemic, PROPHET, and SprayAndWait routing protocols against our DRINC algorithm. See Table 2 for a summary of the scenarios. Figure 8 shows delivery results for scenarios 1 to 4, these are scenarios with 10 nodes as rural users, generating messages every 1 to 2 hours or every 1 to 12 hours. Figure 9 shows delivery results for scenarios 5 and 6, these scenarios are the big ones, with 100 nodes as rural users, and they are generating new messages every 1 to 12 hours. When nodes have enough opportunities to communicate (random movement of the nodes), almost all messages are delivered by all protocols; however, when nodes are kept apart most of the time, by using MapRoute movement, all protocols deliver between a 50% to 60% of the messages, with SprayAndWait performing a little bit below this percentage. Figures 10 and 11 show simulation results for delivery delay for Epidemic, PROPHET, and SprayAndWait routing protocols against our DRINC algorithm. See Table 2 for a summary of 142 C. Velásquez-Villada, Y. Donoso Figure 8: Delivery rate for the Rural Internet Connectivity scenarios with 10 nodes. The scenarios change the message size between 2 MB and 2 KB, and the frequency of message generation from 1 to 2 hours or from 1 to 12 hours Figure 9: Delivery rate for the Rural Internet Connectivity scenarios with 100 nodes. The scenarios change the message size between 2 MB and 2 KB Figure 10: Delay in thousands of seconds for the Rural Internet Connectivity scenarios with 10 nodes. The scenarios change the message size between 2 MB and 2 KB, and the frequency of message generation from 1 to 2 hours or from 1 to 12 hours Delay/Disruption Tolerant Networking-Based Routing for Rural Internet Connectivity (DRINC) 143 Figure 11: Delay in thousands of seconds for the Rural Internet Connectivity scenarios with 100 nodes. The scenarios change the message size between 2 MB and 2 KB Figure 12: Overhead (messages generated/messages delivered) for the Rural Internet Connectiv- ity scenarios with 10 nodes. The scenarios change the message size between 2 MB and 2 KB, and the frequency of message generation from 1 to 2 hours or from 1 to 12 hours Figure 13: Overhead (messages generated/messages delivered) for the Rural Internet Connec- tivity scenarios with 100 nodes. The scenarios change the message size between 2 MB and 2 KB 144 C. Velásquez-Villada, Y. Donoso Figure 14: Hop Count for the Rural Internet Connectivity scenarios with 10 nodes. The scenarios change the message size between 2 MB and 2 KB, and the frequency of message generation from 1 to 2 hours or from 1 to 12 hours Figure 15: Hop Count for the Rural Internet Connectivity scenarios with 100 nodes. The sce- narios change the message size between 2 MB and 2 KB the scenarios. Figure 10 shows delay results for scenarios 1 to 4. And, Figure 11 shows delay results for scenarios 5 and 6. These results show that all protocols have similar performance regarding delay when the movement model is random. SprayAndWait has the best delay and PROPHETv2 has the worst. DRINC is tied in second place with Epidemic. Figures 12 and 13 show simulation results for messages generated over messages delivered (overhead) for Epidemic, PROPHET, and SprayAndWait routing protocols against our DRINC algorithm. See Table 2 for a summary of the scenarios. Figure 12 shows overhead results for scenarios 1 to 4. And, Figure 13 shows overhead results for scenarios 5 and 6. These results show that in small sized scenarios (Scenarios 1 to 4, with 10 rural nodes) PROPHETv2 has the best overhead when the movement model is MapRoute, and SprayAndWait has the best overhead when the movement model is Random. SprayAndWait has also the best performance in overhead when the scenario has 100 nodes. Our DRINC algorithm has the same overhead as Epidemic. Figures 14 and 15 show simulation results for the number of hops used to deliver the messages for Epidemic, PROPHET, and SprayAndWait routing protocols against our DRINC algorithm. See Table 2 for a summary of the scenarios. Figure 14 shows hop count results for scenarios 1 to 4. And, Figure 15 shows hop count results for scenarios 5 and 6. These results show that all protocols have a similar performance regarding hop count for small sized scenarios (Scenarios 1 to 4, with 10 rural nodes). SprayAndWait has the best performance regarding hop count when Delay/Disruption Tolerant Networking-Based Routing for Rural Internet Connectivity (DRINC) 145 the scenario has 100 nodes. Our DRINC algorithm has the same hop count as Epidemic. Results suggest that our proposed algorithm uses more messages to find paths and gather knowledge from the network than other protocols. This can be seen in a higher overhead metric for our DRINC algorithm than it is for other known protocols. DRINC delivers the same or more messages than all protocols used for comparison and it does it in the same time or less, with exception of SprayAndWait that has the best delay performance for nodes using the MapRoute movement model; although, it delivers less messages. Conclusions and future work Conclusions • Delay/Disruption Tolerant Networking is a technically feasible way to bring Internet con- nectivity to remote rural areas in the world. Simulation results in section 4 show promising results for several DTN routing protocols. They also show that a new protocol, specifically tailored for rural connectivity scenarios, based on the ideas presented in this paper can enhance the performance of current DTN routing protocols, delivering more messages with less delay. To get to a product solution that could be deployed in rural areas, an imple- mentation on an electronic platform should be done. A development with electronics and software will be very useful for tuning to obtain a robust solution. • The DRINC algorithm presented in Section 3 combines the best characteristics of some of the most known DTN routing protocols. From results in Section 4, it can be seen that our DRINC algorithm performs as well as these protocols. Simulation results show that our DRINC algorithm solution delivers almost all messages when the mobility model given by the simulator allows rural nodes to interact more frequently. When the simulator is configured to use a mobility model that keeps rural nodes apart from each other most of the time, the delivery rate of all protocols drops significantly. This effect is minimized when there are 100 rural nodes, creating more contact opportunities. It can also be seen that in this scenario, all protocols have a very similar performance regarding all metrics. Only Spray and Wait differentiates from the others by delivering less messages with less delay and having less overhead in general. Future work This paper provides the basic research to test the feasibility of a technological solution based on DTN technologies for Rural Internet Connectivity for non-real-time applications. Technology development, implementation and testing is necessary before a complete solution can be given. Simulation results for our DRINC algorithm suggest that it improves the delivery rate and delay when compared with well known DTN routing protocols for rural connectivity scenarios; however, more tuning should be done regarding the updating of delivery probabilities, in a way that faster routes or newly discovered routes can be fairly compared with previous ones, reducing the number of hops, and the overhead, in the network. Also, it is necessary to perform tests in real implementations and tune the inner working of the DRINC algorithm in electronic platforms and in real life conditions, taking into account errors and disruptions given by the physical world, and network access’ technologies. 146 C. Velásquez-Villada, Y. Donoso Acknowledgment I would like to thank the Colombian “Departamento Administrativo de Ciencia, Tecnología e Innovación - Colciencias Conv. 528/2011” for the funding of the research leading to this paper. It was also partially funded by: • Systems and Computing Engineering Department, Universidad de los Andes in Colombia; • European Union Seventh Framework Programme (FP7/2007-2013) under grant agreement no. 269985. Bibliography [1] Velásquez-Villada, C.; Donoso, Y. (2016); Delay/Disruption Tolerant Networks Based Mes- sage Forwarding Algorithm for Rural Internet Connectivity Applications, Computers Com- munications and Control (ICCCC), 2016 6th International Conference on, IEEE Xplore, e-ISSN 978-1-5090-1735-5, doi: 10.1109/ICCCC.2016.7496732, 16-22. [2] La Rue, F. (2011); Report of the Special Rapporteur on the promotion and protection of the right to freedom of opinion and expression Special Procedures of the Human Rights Council, United Nations. [3] International Telecommunication Union. (2016); Measuring the Information Society. http://www.itu.int/en/ITUD/Statistics/Pages/stat/default.aspx [4] Velásquez-Villada, C.; Solano, F.; Donoso Y. (2015); Routing Optimization for Delay Toler- ant Networks in Rural Applications Using a Distributed Algorithm. International Journal of Computers, Communications and Control. 10(1):100-111. [5] Cerf, V. et al. (2007); RFC4838-Delay-Tolerant Networking Architecture. IETF RFC 4838. [6] Pentland, A. S.; Fletcher, R.; Hasson, A. (2004); Daknet: Rethinking connectivity in devel- oping nations. Computer, 37(1):78-83. [7] Lindgren, A. et al. (2012); Probabilistic routing protocol for intermittently connected net- works. Technical report, IETF RFC 6693, Experimental. [8] Keranen, A.; Ott, J.; Karkkainen T. (2009); The ONE simulator for DTN protocol evalua- tion, Proc. of the 2nd intl. conf. on simulation tools and techniques, ICST, art.55, 1-10. [9] Scott, K.; Burleigh, S. (2007); RFC5050: Bundle protocol specification. IETF RFC 5050. [10] Warthman, F. (2015); Delay and Disruption-Tolerant Networks (DTNs) A Tutorial. Based on Technology Developed by the DTN Research Group (DTN-RG), Version 3.2, 1-35. [11] Google Inc. (2016); Loon Project. https://www.google.com/loon/ [12] Google Inc. (2016); Link Project. https://www.google.com/get/projectlink/ [13] Facebook Inc. (2016); Internet.org. https://www.internet.org/projects [14] Choubey, N.; Panah, A. Y. (2016); Introducing Facebook’s new terrestrial connectivity systems Terragraph and Project ARIES. Delay/Disruption Tolerant Networking-Based Routing for Rural Internet Connectivity (DRINC) 147 [15] Ministerio de Tecnologías de la Información y las Comunicaciones, Gobierno de Colombia. (2011); Proyecto Nacional de Fibra Óptica. [16] Watkins, J.; Tacchi, J.; Kiran, M.S. (2009); The role of intermediaries in the development of asynchronous rural access. In Universal Access in Human-Computer Interaction. Appli- cations and Services, 451-459. Springer. [17] Vahdat, A.; Becker, D. (2000); Epidemic routing for partially connected ad hoc networks. [18] Spyropoulos, T.; Psounis, K.; Raghavendra, C. S. (2005); Spray and wait: an efficient routing scheme for intermittently connected mobile networks. Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, 252-259. [19] Khabbaz, M. J.; Assi, C. M.; Fawaz, W. F. (2012); Disruption-tolerant networking: A comprehensive survey on recent developments and persisting challenges. Communications Surveys & Tutorials, IEEE, 14(2):607-640. [20] Cao, Y.; Sun, Z. (2013); Routing in delay/disruption tolerant networks: A taxonomy, survey and challenges. Communications Surveys & Tutorials, IEEE, 15(2):654-677. [21] Psaras, I.; Wood, L.; Tafazolli, R. (2010); Delay-/disruption-tolerant networking: State of the art and future challenges. University of Surrey, Technical Report. [22] Velásquez-Villada C; Donoso Y. (2016); Delay/Disruption Tolerant Network-Based Message Forwarding for a River Pollution Monitoring Wireless Sensor Network Application. Sensors, 16:1-25. [23] OpenJUMP GIS (2016) http://www.openjump.org/