About Delay Tolerant Network Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Delay tolerant network is the network that operates with intermittent and highly delayed connections and low degree of interactivity, but the flexibility of the Network architecture allows them to be connected to each other. In past few years, delay tolerant networking is very challenging research area, which can shape future technological applications.

Internet is interconnection of communication devices around the world. To provide communication between different types of devices several homogeneous set of communication protocol used like TCP/IP protocol suite. The task of such protocol suite is: routing data and ensuring reliability of message exchange. Connectivity on internet relies on wired links (wired telephone network) as well as wireless technology (short range mobile links, satellite links).

Delay tolerant network is a network of regional networks which shows interplanetary internet [1]. Nowadays communication devices are rapidly growing and operate on limited power. This is applicable to interplanetary space and common to all mobile communication wireless devices on earth.

When communication devices are in motion connection can be obstructed by several reasons like battery power and as a result devices can be shut down. As a result of this, connections between different devices may shutdown. This type of events causes intermittent connectivity. Because of this shutdown there may not be direct path available between source and destination. So network partition occurs.

Network partition/intermittent connectivity causes loss of data on the internet. In this case if packet is not immediately forwarded then packet drop occurs of packet discards. In case of TCP, it transmits packet in slower transmission rate. And if packet dropping situation continues for long time then TCP ends the session. This can fail the application.

Here for above scenario delay/disruption tolerant network support communication between intermittently connected nodes by isolating delay with store and forward technique.

1.1.1 Characteristics of DTN

Unique connectivity concepts

Very long or variable delay

Asymmetric data rate

Different network architectures

High link error rates

1.2 Routing in Delay Tolerant Network

Routing is the process of moving packets across a network from one host to another. Packets are the fundamental unit of information transport in all recent computer networks, and increasingly in other communications networks as well. They proceed through packet switched networks, which are networks on which each message (i.e., data that is sent) is cut up into a set of small segments before broadcast. Each packet is then transferred independently and can follow the same path or a different path to the common endpoint. Once all of the packets have arrived at the endpoint, they are automatically reunited to reconstruct the original message.

Routing is a important feature of the Internet. Each midway router performs routing by passing along the message to the subsequent router. Part of this procedure includes analyzing self-configuring routing tables to decide the best (i.e., optimal) path.

Different routing schemes for delay tolerant networks [2] are as below.

1.2.1 Epidemic Routing

The goal of Epidemic routing [3] is to deliver messages with high probability even when there is never a fully connected path.

Maximize message delivery rate

Minimize message delivery latency

Minimizing the aggregate system resources consumed in message delivery

In epidemic routing, when a message arrives at an intermediate node, the node floods the message to all its neighbors. It is flooding based scheme of DTN routing. If a route to a destination is unavailable, a node performs a controlled local broadcast (a relay) to its immediate neighbors. All nodes that receive this packet store it and enter the relaying mode. It is a multicopy scheme.

1.2.2 Spray and Wait Routing

Spray and Wait [4][5] routing consists of the following two phases:

Spray Phase: For every message originating at a source node, L message copies are initially spread - forwarded by the source and possibly other nodes receiving a copy - to L distinct "relays".

Wait Phase: If the destination is not found in the spraying phase, each of the L nodes carrying a message copy performs direct transmission (i.e. will forward the message only to its destination).

Its goal is to significantly reduce transmissions by bounding the total no. of copies/transmissions per message.

Under low traffic: minimal penalty on delay (close to optimal).

Under high traffic: reduce the delay of existing flooding and utility based schemes thanks to less contention.

Source node 'sprays' a number of copies into the network, and then 'waits' till one of these nodes meets the destination. There is no direct path from source to destination. In this case all the conventional protocols would fail. However, this does not mean that packets can never be delivered in such networks. Over time, different links come up and down due to node mobility. If the sequences of connectivity graphs over a time interval are overlapped, then an end to end path might exist.

This suggests that a message could be transmitted over a current link, get buffered at the subsequent hop up to the next link in the path comes up, and so on, until it reaches its destination. This approach imposes a new model for routing. Routing consists of a sequence of independent, local forwarding decisions, based on current connectivity information and predictions of future connectivity information. It is a multicopy scheme.

1.2.3 Encounter Based Routing

Encounter-Based Routing (EBR)[6] uses an encounter-based metric for optimization of message passing that maximizes message delivery ratio while minimizing overhead both in terms of extra traffic injected into the network and control overhead, as well as minimizing latency as a second order metric.

A quota based DTN routing protocol that achieves high delivery ratios comparable to flooding based protocols, while maintaining low network overhead. Since EBR is a quota-based routing protocol, it limits the number of replicas of any message in the system, minimizing network resource usage. Additionally, EBR bases routing decisions on node's rates of encounters, showing preference to message exchanges with nodes that have high encounter rates. These routing decisions result in higher probability of message delivery, avoiding routes that may never result in delivery and so reducing the total number of message exchanges.

1.2.4 PRoPHET Routing

In the Probabilistic Routing Protocol using History of Encounters and Transitivity[7], the selection of the best neighbor node is based on how frequently a node encounter another. Prophet uses a probabilistic metric called delivery predictability that indicates how likely it is that A will meet B, and thus that will be able to deliver a message to B. When two nodes meet, they exchange their summary vectors, which contain their delivery predictability information. If two nodes do not meet for a while, the delivery predictability reduces. When the sender wants to send a message to the destination D, it will look for the neighbor node that has the highest amount of time encountering D, meaning that has the highest delivery predictability to D [7]. This property is further transitive.

1.2.5 Direct Transmission and First Contact

Direct Delivery/Transmission [8] and First Contact [8] are single copy routing protocols where only one copy of each message exists in the network.

In Direct Delivery, the node carries messages until it meets their final destination. In First Contact routing the nodes forward messages to the first node they encounter, which results in a "random walk" search for the destination node.

1.3 Mobility Models

The mobility model [9] is designed to describe the movement pattern of transportable users, and how their position, speed and acceleration change over time. Since mobility patterns may play a significant role in determining the protocol performance, it is desirable for mobility models to emulate the movement pattern of targeted real life applications in a reasonable way. Otherwise, the observations made and the conclusions drawn from the simulation studies may be misleading. Thus it is necessary to choose the proper underlying mobility model. Mobility management schemes for mobile communication systems make use of mobility models for forecasting upcoming user locations.

1.3.1 Synthetic Models

1. Random Walk Mobility Model

Fig. 1.1 Example of Node Movement in the Random Walk Model

The simplest mobility model is the Random Walk mobility model also called Brownian motion. It is a widely used model to represent purely random movements of the entities of a system in various disciplines from physics to meteorology. However, it cannot be considered as a suitable model to simulate wireless environments, since human movements do not present the continuous changes of direction that characterize this mobility model.

2. Random Way-Point Mobility Model

Fig. 1.2 Example of Node Movement in the Random Waypoint Model

Another example of random mobility model is the Random Way-Point mobility model. This can be considered as an extension of the Random Walk mobility model, with the addition of pauses between changes in direction or speed. However, also in this case, the realism of the model in terms of geographical movement is far from being realistic.

1.3.2 Trace-Based Models

Trace Based Mobility Model, captures the history of the movement patterns of the nodes, and identifies regularity in these movements. It is this regularity in movement that is used to predict the stability of the nodes. This model as the following assumptions:

Each node is location aware, using GPS.

The network is mapped to a virtual grid structure. This can be done based up on the transmission region and the area network.

1.4 Social Network Analysis

A social network is a social assembly made up of a set of actors (such as individuals or organizations) and the dyadic bonds between these actors. The social network viewpoint delivers a clear way of analyzing the assembly of total social entities. The study of these assemblies uses social network analysis to recognize local and global arrangements, locate important entities, and observe network dynamics.

1.4.1 Centrality

Centrality in graph theory and network analysis is a quantification of the relative significance of a vertex in the graph (e.g., how important a person is within a social network). The centrality of a node in a network is a measure of the structural importance of the node. A central node, typically, has a stronger capability of connecting other network members. There are several ways to measure centrality. The three most widely used centrality measures are Freeman's degree, closeness, and betweenness measures [10][11].

1. Degree Centrality

'Degree' centrality is measured as the number of direct ties that involve a given node [11]. A node with high degree centrality maintains contacts with numerous other network nodes. Such nodes can be seen as popular nodes with large numbers of links to others. As such, a central node occupies a structural position (network location) that may act as a conduit for information exchange.

2. Closeness Centrality

'Closeness' centrality measures the reciprocal of the mean geodesic distance , which is the shortest path between a node and all other reachable nodes [11]. Closeness centrality can be stared as a measure of how long it will take information to spread from a given node to other nodes in the network [12].

3. Betweenness Centrality

'Betweenness' centrality measures the extent to which a node lies on the paths linking other nodes. Betweenness centrality can be regarded as a measure of the extent to which a node has control over information flowing between others [12]. A node with a high betweenness centrality has a capacity to facilitate interactions between the nodes that it links.

1.5 Temporal Centrality

The representation of a time-varying network by means of the associated static graph can convey misleading information about the network itself [13]. For instance, a static aggregated network usually has far more links than the network has at each time instant (or if the aggregation is performed over short time windows).

In order to overcome these problems, the definitions of temporal closeness and temporal betweenness centrality by employing temporal shortest paths, which do take into account time information.

1.5.1 Temporal Closeness

Two nodes of a static graph are said to be close to each other if their geodesic distance is small. In a static graph an estimation of the global closeness of a node i is obtained as the average static shortest path length to all other nodes in the graph. Similarly, we can extend the definition of closeness to temporal graphs using the temporal shortest path length between nodes, which is a measure of how early a source node can deliver a message to all other nodes.

Given the shortest temporal distance , the temporal closeness centrality can be expressed as Eq. (1.1)

Where, = Window size

= Number of nodes in network and

= The shortest temporal distance between node and

So that nodes that have, on average, shorter temporal distances to the other nodes are considered more central.

Example: If there are 6 nodes in time window of size 3 at present, as shown in Fig. 1.4. Nodes are reachable from the source node A than closeness centrality of source node A can be calculated as mean of the paths from source node to remaining reachable nodes (i.e. 5) in network.








Fig. 1.3 Closeness Centrality

As the time change, due to node movement, this closeness centrality is also changed. This has motivated us to describe temporal closeness centrality and use it to find network density to choose better routing method.

1.6 Thesis Organization

Chapter 1 is Introduction containing about information of DTN and other metrics used in the thesis. Chapter 2 is Literature Survey, which discusses about current research. Chapter 3, Problem Identification presents the outcomes and identifies the problem. Chapter 4, Proposed Solution proposes adaptive forwarding replication (AFR) routing protocol based on temporal closeness centrality. In chapter 5 presents Performance Analysis and Simulations of AFR. Chapter 6 presents the Conclusion and chapter 7 discusses about Future Work.