Disruption Tolerant Networking (DTN) is a network architecture that enables communication between devices in challenging environments that may never have a contemporaneous end-to-end path. Routing in DTN is challenging since every node decides autonomously, based on local information, which bundles should be forwarded when two devices have a contact opportunity (i.e., when they meet). Frequently, devices exchange locally and transitively collected information (properties) during contact opportunities to support their routing algorithms. In the context of Public Transport Networks (PTN), devices may be vehicles (e.g., tram, bus) or stations that use vehicular mobility as a data carrier. Vehicles in a PTN tend to move back and forth, creating repetitive patterns. We assumed that routing algorithms capable of exploring those characteristics would likely maximize the desired metric, e.g., increasing delivery probability (DP) or minimizing latency. In the event of unexpected mobility changes, routing algorithms that perform well under normal mobility may perform poorly during this period. In this case, property exchange can provide context awareness, supporting a device in choosing the right moment to adapt the routing algorithm or tuning it at runtime. However, mobility adaptation and adaptive parametrization were not investigated in the context of DTN for PTN. This thesis proposes an adaptive routing module that supports multiple routing algorithms chosen independently, per bundle, at runtime.
Our literature research revealed that many adaptive algorithms had been proposed. Still, only a few provided routing adaptation, and those approaches have not been addressed in the context of PTNs. From an extensive review of property exchange in DTN, we classified properties that algorithms exchanged at runtime. Finally, we provided an overview of the current DTN frameworks, showing that at least one allows the choice of the routing algorithm independently; however, the high coupling between routing and information exchange precludes the usage of multiple routing algorithms concurrently in practice.
Therefore, our novel approach decouples property exchange from the routing algorithm, i.e., exchanging a set of properties consistently during contact opportunities independently of the routing algorithm used. From the different classes identified in the literature research, resource class is the most suitable for PTN as exchanging its properties enables reproducing the most common routing algorithms and providing context-awareness. The history of contacts is stored together with information about devices resources' state during each contact opportunity and spread transitively in the network. Since this information is immutable, it incrementally allows every device to improve its understanding of network behavior over time. Another improvement in our approach is exchanging raw information as an ordered list of the instantaneous information about the device state, allowing every device to derive the needed information to the routing support locally.Commonly, devices exchange summarized information (e.g., frequency of contacts, centrality, delivery predictability): an interesting approach for single routing, as it allows the exchange of the minimal amount of information; however, it is less attractive for a multi routing approach due to the high coupling between routing and property exchange.
Creating an adaptative mechanism for a routing algorithm at runtime claims a careful choice considering multiple aspects of the development cycle: modeling, dynamic adaptation, and system extension. Runtime adaptability and extensibility support have been integrated into some programming languages. In some cases, it is also possible to provide those capabilities through development techniques and design patterns. However, at the modeling level, conceptual modeling languages, as the Entity-Relationship Model (ER) or the Unified Modeling Language (UML) cannot express the dynamics that arise from the context changes and behavioral interaction at runtime (e.g., the influence of congestion control techniques in the outcome of the routing algorithm according to a set of goals or intent of the network). Therefore, we used Role-based modeling languages to express the behavioral and relational nature of the proposed system. In a PTN, the router (vehicle or station) plays the role \textit{route} (executes an objective function) depending on the sensed context. The \textit{route} role can be further influenced by roles that encapsulate routing strategies, as congestion control (limiting the number of replication) or fairness. Routing algorithms are grouped in compartments and selected based on rules that determine what routing algorithm should be selected for a given context and how to tune the routing algorithm. A proof of concept was developed using SCROLL and integrated into the ONE simulator, allowing adaptive simulations. On the one hand, this solution is flexible, allowing algorithms to be designed independently. On the other hand, the integration between Java and SCALA reduced the system's flexibility due to the impossibility of using implicit types and the simulation time increased considerably.
The potential performance improvement caused by routing adaptation depends on several variables, e.g., the scenario, the vehicular mobility, and the routing algorithms.
Based on the evaluation of common routing algorithms proposed in DTN that can be reproduced by exchanging information about resources, we show that algorithms should be compared under average load.
On the one hand, if the network load is low, all routing algorithms perform similarly, since all bundles are delivered; On the other hand, the network is congested regardless of the routing algorithm if the load is too high. Our experiments also indicate that routing algorithms able to explore the runtime behavior of the network are likely to achieve higher DP for an average load and highlighted the importance of proper tuning of each routing algorithm for the target scenario.
The adaptive simulations showed that adapting the routing algorithm at runtime could increase the desired metric. Our simulations considered 24 hours of the tram PTN of Freiburg, in which we changed the mobility for a specific period of the day. In both experiments, we compare a historically based non-adaptive algorithm (PRoPHET) with an adaptive algorithm that modifies the behavior (PRoPHET and Epidemic) according to the context. In the first scenario, we simulate the effect of a disaster in which vehicular mobility is replaced by first aid vehicles. The adaptive variant resulted in a DP increase of up to 9.85\% at the end of the adaptation period. In the second scenario, we simulated mobility adaptation due to an accident that split two tramlines. Also, in this use case, the adaptation at runtime allowed the DP to increase up to 11.12\%. In both cases, the ability to perceive the context modification and adapt accordingly is essential. We evaluated the overhead of information exchange based on a concrete example for PTN and found that, for the chosen scenarios and multiple communication technologies, the network overhead caused by information exchange at runtime would be less than 1.2\%.
The main contributions of this thesis are summarized as follows:
we developed tools to support the creation and simulation of DTN in PTN scenarios; provided a classification of properties exchanged in the DTN literature to provide context awareness and support routing algorithms; pointed out a design decision in current frameworks (coupling between routing and property exchange) that precludes the adoption of current routing algorithms at runtime; reinforced, based on extensive simulations, the importance of tuning each routing algorithm to the target use-case; proposed a method to exchange and store properties that could enable nodes to collect historical data according to its resources (computing and storage space); demonstrated, for a specific property group how to break information into basic units and how to derive complex metrics for multiple purposes; last but not least, we demonstrated that, in scheduled networks, such as PTN, adaptive algorithms can increase the desired metric by adapting the routing algorithm at runtime. As future work remains the following question: how to effectively provide context awareness through the exchange of properties at runtime?
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:76310 |
| Date | 15 October 2021 |
| Creators | Irigon de Irigon, José |
| Contributors | Schill, Alexander, Campos Nobre, Jéferson, Strufe, Thorsten, Technische Universität Dresden |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, doc-type:doctoralThesis, info:eu-repo/semantics/doctoralThesis, doc-type:Text |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0222 seconds