Mobile Network Environment Using Dtn Computer Science Essay

Published:

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

A communications network that withstands long delays or outages and is capable of storing packets temporarily stationed in intermediate nodes, until the time as an end-to-end route can be re-established or regenerated are known as delay tolerant networks or DTN. This paper aims to collectively detail all the general & basic aspects relating to information needs in DTN routing. We also include, evolution of important routing protocols since their inception, discuss in some detail routing types, groups and classifications, network environment, efficiency parameters, advantage, and disadvantage including possible and proposed future extensions. All this is accomplished by capturing the same in metrics. At the end of this study, we identify schemes and techniques that will help us to exploit the delay and utilize the time judiciously to improve the efficiency of information exchange in a DTN network. The basic objective is to utilize efficiently this temporal period by opportunistically establishing connectivity - in a strategic manner, to exchange information across locally distributed resources, thus making optimal use of available network resources and enhancing the efficiency of information exchange.

General Terms

Routing techniques, routing efficiencies, protocol

Keywords: forwarding, replication, single copy, multicopy , relay, delivery ratio, delay, throughput

Introduction

Delay Tolerant Networking is a networking architecture that is designed to provide communications under unstable and stressed environments, where the network would normally be subject to frequent and long lasting delays, higher bit error rates that severely affect & degrade normal communications.

DTN works that use different kind of approach other than TCP/IP for packet delivery, is more resilient to disruption than TCP/IP. Today's, DTN is based on a new experimental protocol called the Bundle Protocol (RFC 5050). BP resides conveniently at the application layer protocol of OSI in a constituent network - internets, forming a store-and-forward overlay network. The Bundle Protocol (BP) operates as an overlay protocol that links together multiple subnets (such as Ethernet-based LANs) into a single network.

The basic idea behind DTN network is that endpoints connectivity is not constant - for other obvious reasons as well. But, as a specific situation, in order to facilitate data transfer, DTN uses "store-and-forward" approach across routers that are more disruption-tolerant (delay) compared to TCP/IP, particularly in case of network-routing. However, DTN approach does not necessarily mean that all DTN routers on a network would require large storage capacity instantaneously or otherwise to maintain end-to-end data integrity. Disruption Tolerant Networks are frequently used in disaster relief missions, peace-keeping missions, and in vehicular networks or most data exchanges, this additional delay is acceptable and could even be an advantage as well. The reason for this is the fact that nodes are actually silent processors that not only help channel data packets ("Throwboxes [1] or "Data mule [2]" or relay nodes) to destination but can also provide higher bandwidth - through judicious use and processing. Higher bandwidth attribute of the node will eventually contribute in reducing the number of hops.

Several proposals for efficient routing mechanisms have been devised [3,4,5,6,7], claiming superiority based upon experimental and software simulated data results. In this paper, we aim to inspect what are the different techniques available [4,5]. Techniques & strategies that recognize: who, whom, & when [8] for routing. We inspect keeping mobility in mind, and consider mobility models and work towards designing routing algorithm/s keeping the aspects of mobility in mind.

In Section-2, we address and discuss general aspects relating to DTN routing, followed by Section-3 discusses routing objectives, Section-4 routing challenges, Section 5 discusses Proactive routing Vs Reactive routing, Section 6 discusses Routing types Section discusses Routing groups, Section 8 Classification criteria : DTN routing Section 9 discusses various routing techniques, network environment and efficiency metrics, and finally, Section-10 concludes by presenting an executive summary of routing techniques & conclusions we arrive at.

Routing in DTN

Routing in a lay man terms, means, finding a good path to a designated endpoint - but concurrently to a network engineer, working in a real world situation, it means optimization of resources leading to efficiencies of network and information and economies of scale in terms of usage, the data can be delivered and the protocol finds the fastest and shortest path between the two involved nodes. Depending on the application using the DTN, it can be useful to drop packets and free buffers quite early paving way to newly sent packets, and a good chance to deliver in time, while, on the other hand, it may be important to deliver as many packets as possible, no matter how long it lasts.

In the next few sections, we briefly introduce routing, its objectives, parameters, challenges and other related aspects including some discussions on currently popular techniques in DTN's. This is followed by some analysis comparing the different techniques introduced and studied.

Routing Objective

For any routing algorithm, a basic objective is to maximize the probability of delivering messages. In addition, we define the routing efficiency of an algorithm as the ratio between the total amount of delivered messages and the total amount of traffic generated in the network. This metric measures how efficient a routing algorithm is in utilizing resources.

In this paper, we study several classes of routing algorithms that are expected to achieve different balance of delivery ratio and routing efficiency. For each class of algorithms, we focus on minimizing the delay for each intended receiver. Goals of Routing Protocols

A lot of Routing protocols [1,2,3] have been developed for this purpose they all vary in the way they accomplish the task, but they all have more or less common goals.

The main goals are [4,5]:

Low latency :Latency is the time taken by the packet to reach its destination from its source.

Low latency jitter: Latency jitter is the variation in latency, for real time applications such as streaming video, the requirement for low latency jitter is more important than the requirement of low latency.

High throughput :. Throughput can be defined as the number of data packets delivered per second. Throughput is affected by packets being dropped, and protocol data units that are used by protocols to set up communication with peers.

Low packet loss or High Reliability. Packet loss causes decrease in throughput and increases latency.

Low convergence time in case of changes in network topology. It is necessary for routing algorithm to adapt to changes in network as quickly as possible, so that utilization of network resources is maximized.

Low routing overhead: Routing overhead is caused by the update packets that are exchanged by routing protocols to convey network information to its peers.

Routing overhead decreases throughput.

It is not possible for a routing protocol to achieve all the goals. As some of the above stated goals are conflicting in nature, for example to achieve Low convergence time in case of change in topology certainly requires high routing overhead which in turn reduces the throughput for end to end communication.

ROUTING Challenges

Routing is with no doubt the most challenging issue within a DTN. Many restrictions have to be taken into account and traditional network routing protocols will not satisfy the expectations. Links become available without any previous knowledge and the destination node may never be reachable immediately with a contemporaneous end-to-end path. Nodes change their routes randomly or may follow a predictable path, buffer and bandwidth restrictions force the protocol to send its discovery and topology information as sparingly as possible and avoid resource consuming mechanisms.

The routing algorithm further needs to know

When to send/forward a message,

Where to send a message,

Which message to send/forward,

Which message to delete,

If it follows a single- or multi-copy strategy,

If it acts in a pro- or reactive manner

Proactive Routing vs. Reactive Routing

In proactive routing, routes are computed automatically and independently of traffic arrivals. Most Internet standard routing protocols and some ad-hoc protocols such as DSDV (Destination Sequenced Distance Vector) and OLSR (Optimized Link-State Routing) are examples of this style [6]. In a DTN, these protocols are capable of computing routes for a connected sub graph of the overall DTN topology graph. They fail when asked to provide paths to nodes, which are not currently reachable. Despite this drawback, proactive network-layer routing protocols may provide useful input to DTN routing algorithm by providing the set of currently reachable nodes from which DTN routing may select preferred next hops. In reactive routing, routes are discovered on-demand when traffic must be delivered to an unknown destination. Ad-hoc routing protocols such as AODV (Ad-hoc On-demand Distance Vector) and DSR (Dynamic Source Routing) are examples of this style [6]. In these systems, a route discovery protocol is employed to determine routes to destinations on demand, incurring additional delay. These protocols work best when communication patterns are relatively sparse. For a DTN, as with the proactive protocols, these protocols work only for finding routes in a connected sub graph of the overall DTN routing graph. However, they fail in a different way than the proactive protocols. In particular, they will simply fail to return a successful route (from a lack of response), whereas the proactive protocols can potentially fail more quickly (by determining that the requested destination is not presently reachable). In a DTN, routes may vary with time in predictable ways and can be pre-computed using knowledge about future topology dynamics. Employing a proactive approach would likely involve computing several sets of routes and indexing them by time. The associated resource requirements would be prohibitive unless the traffic demand is large and a large percentage of the possible network nodes exchange traffic. Reactive routing will fail to discover a complete path, while proactive protocols will fail to converge, resulting in a deluge of topology update messages.

A related issue is route stability, a measure of how long the currently known routes are valid. Route stability depends on the rate of topological change. With relatively stable routes one can employ route caching to avoid unnecessary routing protocol exchanges. With future knowledge about topology changes, caching could be especially effective in a DTN because it may be possible to know ahead of time exactly when to evict existing cached route entries.

Routing Types

Unicast Routing

Source will send a copy of the message to intended receiver.

2. Broadcast Routing

Messages will be flooded throughout the network in order to reach all nodes.

3. Tree-Based Routing

Messages are forwarded along a tree in the DTN graph that is rooted at the source and reaches all receivers. Messages are duplicated only at nodes that have more than one outgoing path.

4. Group-Based Routing.

It uses the concept of forwarding group [6] which is a set of nodes that are responsible for forwarding the message. Messages will be flooded within the forwarding group to increase the chance of delivery.

ROUTING GROUPS

Source Routing: is where the source specifies the path a packet should traverse to reach its destination. This requires each node in the network to have a precise knowledge of the network, which seems almost impossible to accomplish on the networks, which are dynamic in nature, and hence hampers the adaptability.

Destination Routing: is where each node knows in which direction to forward a packet for a given destination. Here the source node has no control over the path a packet traverses. The Internet works on this kind of routing.

In dynamically changing networks Source Routing is not deployed and Destination Routing is the obvious choice.

Per-contact Routing:

In this routing protocol, the routing table is recomputed each time a contact is available, instead of computing the next hop for a message. It ensures that each routing decision is made with most recent information [5]. However to guarantee the loop freedom is a big problem.

Per-Hope routing:

In this routing protocol, the intermediate node makes the forwarding decision when a message arrives at the node. The node determines the next hop for the destination and places it in a queue for that contact [7]

Source routing Versus Per-hop Routing

In source routing the complete path of a message is determined at the source node, and encoded in some way in the message. The route is therefore determined once and does not change as the message traverses the network. In contrast, in per-hop routing the next-hop of a message is determined at each hop along its forwarding path. Per-hop routing allows a message to utilize local information about available contacts and queues at each hop, which is typically unavailable at the source. Thus, per-hop routing may lead to better performance. Unfortunately, due to its local nature, it may lead to loops when nodes have different topological views (e.g. due to incomplete or delayed routing information.

Classification criteria - DTN routing

1. Stateless

Most propositions are based on a stateless routing algorithm, meaning in general no further (past or future) location or contact data is needed to make the forwarding decisions.

2. History-based Algorithms

These algorithms use data of the past to find an efficient route to the destination node. Logged data can be a history of recent encounters with other contacts as well as for example contact-time, contact-frequency, and contact-time-location tuples. History-based algorithms usually need some time to warm up, but in return often are more adaptive to topology and mobility changes.

3. Movement-based Algorithm

Some routing ideas are based on feeding the probability function to determine forwarding decisions with movement and velocity data. In simulations purely movement-based algorithms perform quite poor, but can add valuable infor­mation in combination with other approaches

4. Scheduling-based Algorithm

Approaches based on scheduling are mainly of supportive nature and so far no routing algorithm is purely based on scheduling principles.

5. Beacons-less Routing

Most routing protocols require knowledge of a node's neighbors to make their routing decisions. This information is generally gathered by the use of beacons, messages broadcasted regularly that will be heard by all nodes within communication distance. Knowledge of your neighbors makes more informed routing decisions possible, but beacons have their drawbacks.

6. Topological routing protocols : Set of protocols that use information about the links (metrics such as next-hop bandwidth, etc) to perform packet forwarding. Proactive Algorithms (such as DSDV or OLSR) build the routing table obtaining information about the links, even when these links are not used. DSDV is a distance-vector protocol, while OLSR is a link-state protocol.

7. Position-based routing protocols:

Set of protocols that need the position (e.g. via GPS) of the participating nodes. In general, these algorithms look the position of the destination nodes using a Location Server and add this position in the packet header. Nodes that receive the packet apply a forwarding strategy to retransmit the packet. Each node stores a node ID, the direction and distance to the node, as well as an age time. Forwarding Strategies decide towards which node or area the packet is forwarded. Greedy Packet Forwarding forwards the packet to a neighbor lying in the direction of the destination. Some examples (see [21]) are:

Forwarding strategies:

(i) Most forward

within r (MFR) that forwards packets towards the node that makes more progress towards destination.

(ii) Nearest with forward progress (NFP) that forwards packets towards the node that is nearest the source and closer to destination.

(iii)Compass routing selects the neighbor closest to the straight line between sender and destination.

(iv) Random forwarding chooses randomly one among the neighbors closer to the destination than the sender.

8. Opportunistic routing protocols:

New routing techniques have to be devised to take into account sparse and intermittent networks in which nodes communicate either scheduled over time or randomly. Pelusi et al in paper [22] give a review of opportunistic techniques in ad hoc networks. In an opportunistic network, each node decides locally to which next hop the packet will be forwarded. This next-hop may decide to store the packet until a new opportunity to forward the packet appears.

9. Oracle based :

Although most approaches use some kind of probability function or metric to decide whether to forward or not the data-packet, they highly differ in which values and properties have been taken into account. We decided to classify algorithms based on their source of routing knowledge. We can distinguish between five types of approaches. Many algorithms combine two or more approaches but focus on one specific topic to optimize.

Knowledge Oracles { Reference : S.Jain, K.Fall, R. Patra " Routing in a Delay Tolerant Network

The DTN routing problem has many input variables such as dynamic topology characteristics and traffic demand. Complete knowledge of these variables facilitates the computation of optimal routes. However, with partial knowledge, the ability to compute optimal routes is hampered, and the performance of the resultant routing is expected to be inferior. To understand this fundamental trade-of between performance and knowledge, we create a set of abstract knowledge oracles, each able to answer questions we ask of them. These oracles are notational elements used to encapsulate particular knowledge

about the network required by different algorithms. A key objective of our study is to understand the relationship between algorithm performance and the use of these oracles.

Figure 3 illustrates this conceptually by showing the expected performance and oracle requirements for each proposed routing algorithm:

Contacts Summary Oracle: This oracle can answer questions about aggregate statistics of the contacts. In particular, the contacts summary oracle provides the average waiting time until the next contact for an edge. Thus, the contacts summary oracle can only respond with time-invariant or summary characteristics about contacts.

Contacts Oracle:

This oracle can answer any question regarding contacts between two nodes at any point in time. This is equivalent to knowing the time-varying DTN multi-graph. The contacts summary oracle can be constructed using the contacts oracle, but not vice versa.

Queuing Oracle:

This oracle gives information about instantaneous buffer occupancies (queuing) at any node at any time, and can be used to route around congested nodes. Unlike the other oracles, the queuing oracle is affected by both new messages arriving in the system and the choices made by the routing algorithm itself. We expect it to be the most difficult oracle to realize in a distributed system.

Traffic Demand Oracle This oracle can answer any question regarding the present or future traffic demand. It is able to provide the set of messages injected into the system at any time.

We now present different routing algorithms (Table 1 gives an overview). They fall into the following three classes, based upon the amount of knowledge they need to compute routes.

Routing classification based on Knowledge :

Zero knowledge:

These algorithms do not utilize any oracles. Not surprisingly, they perform poorly. They define the minimal extreme of the knowledge-performance relationship in Figure 3.

Complete knowledge:

This class consists of algorithms that utilize all the oracles (contacts, queuing and traffic demand).The Linear Programming formulation of the DTN routing problem falls into this category

Partial knowledge:

These algorithms route in the absence of the traffic demand oracle and use one or more of the other oracles (congestion, queuing). Messages are routed independently of the future traffic demand. This is a more practical assumption from an implementation perspective.

Routing techniques

Direct delivery:

In this technique [9, 10], the source waits until it comes into contact with the destination before forwarding the data. This technique uses minimal resources since each message is transmitted at most once.

Figure: 1 [11] Example scenario direct delivery and first contact

In figure: 1, node A can only deliver messages to nodes B and D, as shown in Figure 4. Additionally, it is faster for node A to deliver a message to node D via the path A-B-C-D, which it cannot do.

General Specs

Remarks

Network Environment

MANET

Application

Info station Architecture

Algorithm1

[9,10]

Efficiency Parameters

Hop Count

Single

Resource Consumption

Very less

Network Knowledge

Not Required

Delivery Ratio

Inversely proportional to no. of nodes

Advantage

Optimal resource usage, No contention

Disadvantage

Higher delivery delay

Future extensions

-

First contact:

In this technique [8], a message is forwarded along an edge chosen randomly among all the current contacts. If all edges are currently unavailable, the message waits for an edge to become available and is assigned to the first available contact.

1 refer original author paper

In figure: 1, node A may handover messages to nodes B or D to deliver destination E. further, D may forward to C or E upon link availability.

General Specs

Remarks

Network Environment

Remote Village & City connectivity, non trivial network topology

Application

Scientific

Algorithm1

[8]

Efficiency Parameters

Delivery Ratio

Poor

Hop Count

Many

Path Loop

Present, if frequent contacts between node pair

Network Knowledge

Local

Advantage

Lesser forwarding overhead

Disadvantage

Loop back transmissions

Future extensions

Use forwarding strategies like utility based

Message ferries [MF]:

In this technique [12], MF, the network devices are classified as message ferries (or ferries for short) or regular nodes based on their roles in communication. Ferries are devices which take responsibility of carrying messages among other nodes, while regular nodes are devices without such responsibility. With knowledge about ferry routes, nodes can adapt their trajectories to meet the ferries as shown in figure: 2 and transmit or receive messages. By using ferries as relays, nodes can communicate with distant nodes that are out of range.

General Specs

Remarks

Network Environment

Sparse mobile network

Application

Battlefield, Disaster, Wide area sensing, Surveillance , Metro-area messaging, Service-driven

Algorithm1

[12]

Efficiency Parameters

Delivery Rate

Proportional to buffer size

Delay (sec)

Proportional to buffer size

Energy Efficiency

better energy efficiency, by 8 to 30 times than epidemic

Node mobility

Impacts greatly on delivery rate

Advantage

Connectivity in very sparse network

Disadvantage

Needs deterministic path, path calculate over head

Future extensions

Use of multiple message ferries

Throwboxes:

In this technique [1], small and inexpensive devices equipped with wireless interfaces and storage is used. Throwboxes are stationary, thus when two nodes pass by the same location at different times, the throwbox acts as a relay, creating a contact opportunity where none existed before. Figure: 3(a). Shows an example of using throwboxes in a mobile DTN. In Fig. - Node S sends data to a throwbox. At a later time when node R moves close to the throwbox, it receives S's data from the throwbox, shown in Figure: 3(b).

Figure: 3 Throwboxes

Throwboxes are most useful for routing algorithms that use multi-path routing and when nodes follow structured mobility patterns. Throwbox deployment that incorporates knowledge about contact opportunities performs better than deployment that ignores this knowledge.

General Specs

Remarks

Network Environment

Diesel Net Test bed

Application

Vehicular Networks

Algorithm+

[1]

Efficiency Parameters

Throughput

High for regular path

Total Contact duration(sec)

Increase by factor of 20

Average Capacity(Kbps)

Increase by factor of 19

Delay Improvement

High for regular path with high traffic

Advantage

Improve s contact opportunity

Disadvantage

Limited battery life, static node

Future extensions

Energy efficient routing protocol design

Forwarding approach:

In this technique, single copy of the message packet is routed and transmitted during the communication process. The message packet is forwarded by routing towards a reliable relay node, avoiding duplication of message packets. As shown in figure 4. The representative protocols using single copy are Mobyspace [13] and Seek and Focus [4] .

Seek and Focus:

In this technique [4], adopts utility-based/application based as well as randomized routing. By this, they can overcome the slow-start phase and routing jamming by local maximization of utility. The initial step involves discovery of a potential relay neighbor by using the utility-based approach. This helps to avoid being struck for a long time at local maximum of utility, randomized routing is applied in the re-seek phase.

General Specs

Remarks

Network Environment

50 x 50 grid with 40 nodes, transmission range 2-7 meters

Application

General routing protocol for DTN

Algorithm1

[4]

Efficiency Parameters

Expected Delay

Function of Transmission range

Efficiency

Function of Transmission range

Advantage

Lesser transmission

Disadvantage

Homogeneous nodes with IID movements , computational over head

Future extensions

Investigation of performance on real trace base test bed

MobySpace:

This technique [13], utilizes a generic routing scheme using high-dimensional Euclidean space. The main routing idea is that the packet should be forwarded to the node having mobility pattern similar/matching to packet's destination. Since in the MobySpace, the mobility pattern of a node provides its coordinates, its MobyPoint, routing is done by forwarding bundles toward nodes that have their MobyPoint closer and closer to the MobyPoint of the destination.

General Specs

Remarks

Network Environment

Virtual contact space & mobility pattern with power law distribution. Source with full knowledge and partial knowledge of destination mobility pattern

Application

Generic DTN Routing

Algorithm1

[13]

Efficiency Parameters

Average Bundle Delay

Lower

Average Route Length

Lower

Advantage

Lower communication cost

Disadvantage

Poor resource utilization and overhead in extracting important properties of mobility pattern per node

Future extensions

Impact of different mobility patterns on performance

Epidemic Routing:

In this technique [6], when a message is sent, it is placed in the local buffer and tagged with a unique ID. When two nodes connect, they send each other the list of all the messages IDs they have in their buffers, called the summary vector. Using the summary vector, the nodes exchange the messages they do not have. When this operation completes, the nodes have the same messages in their buffers. This provides a large amount of redundancy since all nodes receive every message, making this strategy extremely robust to node and network failures. Additionally, since it tries every path, it delivers each message in the minimum amount of time if there are sufficient resources.

Figure: 5 [11] Example scenarios for epidemic

In example above, the message will be delivered from A to E via the fastest path (A-B-C-E), as shown in figure: 5. all nodes will receive the message except node F because node E does not replicate messages that are destined for it.

General Specs

Remarks

Network Environment

Adhoc Network

Application

Mobile sensor network, Smart Dust, Military deployment

Algorithm1

[6]

Efficiency Parameters

Delivery Rate

Function of Transmission range & Buffer size

Hop Count

Average 3

Latency

Inversely proportional to Transmission range

Buffer Utilization

Function of Buffer size

Advantage

Lower delivery delays, Higher throughput

Disadvantage

Contention, High network resource wastage

Future extensions

Replicating limited copies, use history for spreading messages

PROPHET (Probabilistic Routing Protocol using a History of Encounters and Transitivity):

In this technique [3], when a message arrives at a node which does not have an available contact with other node, it must be stored in the buffer until the node encounters with another node. It only admits that a node can receive the message when its delivery probability exceeds the threshold.

General Specs

Remarks

Network Environment

Partitioned network

Application

Generic Routing for DTN

Algorithm1

[3]

Efficiency Parameters

Message Delivery

Function of buffer size

Message Delivery delay

Larger queue size shorter delay

Message Exchanges

Less compared to Epidemic. Only sends to selected node.

Advantage

Lower communication overhead

Disadvantage

Future extensions

Queuing management policies, purging delivered messages

Spray and Wait:

In this technique [14], in spray phase, spread L message copies to L distinct relays and in wait phase; wait until one of the L relay finds the destination(i.e. direct transmission). It significantly reduces the transmission overhead of flooding-based scheme. The minimum number of copies needed for Spray and Wait to achieve an expected delay is independent of network size and transmission range and depends on number of nodes.

General Specs

Remarks

Network Environment

Intermittently connected mobile networks

Application

Generic routing scheme

Algorithm1

[14]

Efficiency Parameters

Effect of traffic load

Performs less transmission, faster

Delivery Ratio

Above 90 %

Effect of Connectivity

Delay decreases as connectivity increases

Advantage

Lower resource utilization, higher delivery ratio

Disadvantage

Determining number of copies of message (L)

Future extensions

Investigating under more realistic mobility scenario, Forwarding strategies

Spray and Focus:

In this technique [15], aims at improving the protocol of Spray and Wait for mobile users with localized mobility. The difference between them is that the message carrier in Spray and Focus will forward the copy to another suitable neighbor if they have not encountered the destination for a long time.

General Specs

Remarks

Network Environment

Intermittently connected mobile networks

Application

Generic routing scheme

Algorithm1

[15]

Efficiency Parameters

No. of transmission

Function of transmission range

Average delay

Advantage

Improves the performance by 20x than spray & wait

Disadvantage

Computational overhead

Future extensions

Finding optimal distribution strategy

Simple replication:

In this technique [11], identical copies of the message are sent over the first r contacts, with r known as the replication factor. Only the source of the message is permitted to transmit/sends multiple copies, while the relay nodes are allowed to send /forward only to the destination; they cannot forward it to another relay. This makes a mixture between direct delivery and flooding.

Figure: 6 [11]Example scenario for simple replication

If node A has a message for node E, it would send copies to both nodes B and D, as shown in Figure. When node B connects with node C, it would not send it the message, since node C is not the destination. Finally, the message would be delivered at time 7 when node B connects with node E. At the end, nodes A, B, D and E have all received the message. Node A can reach all other nodes via two-hop relay except node F, since it is a minimum of three hops away.

General Specs

Remarks

Network Environment

Zebra net using GPS collars

Application

Wildlife monitoring

Algorithm1

[11]

Efficiency Parameters

Data success rate

Lower

Data latency

Lower the replication factor higher delay

Routing overhead

Constant

Advantage

Lower no. of hops, limited message copies

Disadvantage

Higher delivery delays

Future extensions

Investigating efficient forwarding strategies and performance analysis in real network scenarios

History based simple replication:

In this technique [11,16], the source creates "r" identical copies of a message, which are then delivered to the "best" r nodes, where quality is determined by history. The intermediate nodes will then individually carry out Direct Delivery.

General Specs

Remarks

Network Environment

Zebra net using GPS collars

Application

Wildlife monitoring

Algorithm1

[11,16]

Efficiency Parameters

Data success rate

Lower

Data latency

Lower the replication factor higher delay

Routing overhead

Constant

Advantage

Improved delivery rates

Disadvantage

Buffer management policies , overhead

Future extensions

Efficient predictors for message replication

Erasure Coding:

In this technique [17], first encode the message at the source and generate a large number of code blocks. The generated code blocks are then equally split among the first kr relays, for some constant k, r is replication factor. The message can be decoded at the destination if 1/r of the generated code blocks is received. Since code blocks are divided equally among kr relays, the message can be decoded as soon as any k relays deliver their data if we assume that no code blocks are lost during transmissions to and from a relay.

General Specs

Remarks

Network Environment

Zebra net using GPS collars

Application

Generic routing scheme

Algorithm+

[17]

Efficiency Parameters

Data success rate

Function of deadlines

(days)

Data latency

Lowest

Routing overhead

Lower

Advantage

Reliable, higher delivery rates

Disadvantage

Computational overhead

Future extensions

Needs to make energy efficient

EBEC (Estimation-based erasure coding)

In this technique [18], message is divided into K blocks. For each message, the source takes a replication factor R and erasure codes R x K equal sized blocks. When two nodes encounter, these message blocks are re-dispatched between them according to their estimation values. The message can be fully decoded at the destination if at least K generated blocks is received. Note that since each message block is 1/K of the size of the original message, hence it generates the same overhead as simply replicating R copies of the message.

General Specs

Remarks

Network Environment

Intermittently connected mobile networks

Application

Generic routing scheme

Algorithm1

[18]

Efficiency Parameters

Contact Frequency

Proportional to number of simulation rounds

Message delivery delay

Lower , dependent on R and K

Effect of Connectivity

Delay decreases as connectivity increases

Advantage

Good throughput for higher encounter times

Disadvantage

Larger computational overhead

Future extensions

Investigating efficient estimators

Island Hopping:

In this technique [19], routing protocol relies on the clusters in network. Through the analysis of mobility trace, the authors introduce a novel model with stable Concentration Points (CP) in which the nodes are assumed to communicate only in same CP. The routing algorithm first discovers the whole graph collaboratively in order to employ a sequence of CPs to forward message. The discovery of such a graph consists of two steps: vertex labeling, which can identify each CP that needs to be stitched and edge discovery that can estimate the edge, sets of possible CP graph. After each node knows the graph and respective position - trace or connecting-the-dot, an approach called Last Encounter Table is used to estimate the position of destination. Then the next CP is decided by taking advantage of the shortest path between the source and destination. During the message forwarding, message copies at each CP followed by one-hop acknowledgment scheme makes sure the reliability of transmission. At the same time, the suppression mechanism works when an earlier copy appears in the same CP. The foundation of this algorithm is based upon a stable topology of concentration points (CP's). In an unstable topology or where group movement of nodes is involved, the performance of such algorithm suffers.

General Specs

Remarks

Network Environment

Environment Monitoring, Self organized pocket switched network. Needs stable topology of CP and heterogeneous partitioned network

Application

Routing in regions where mobile nodes have a much higher chance of encountering other

nodes than elsewhere

Algorithm1

[19]

Efficiency Parameters

Delivery Rate

Low

Delay

1.5 times higher

Number of transmission per message

Significantly lesser

Advantage

Fewer transmissions

Disadvantage

Network must be stable and containing heterogeneous nodes

Future extensions

Model of concentration graph, where each vertex is a CP a-priori, and where nodes en-route between CPs cannot communicate with any other node

Mobile vehicle routing:

In this technique [20], the routing decision is based on finding a peer having maximum probability of visiting the region of the destination. Both the source and the selected node try to perform Direct Delivery to the destination, this act results in slightly higher resource consumption than Direct Delivery alone.

General Specs

Remarks

Network Environment

Vehicular area network

Application

Generic routing

Algorithm1

[20]

Efficiency Parameters

Message delivery rate

Above Average

Message Latency

Refer [14]

Duplication of delivered message

Peer Latency

Advantage

Improve delivery rates as optimal

Disadvantage

Deterministic movement pattern

Future extensions

Analyze with more real and complex trace dataset

Maxprop:

This technique [7], attempts to forward the message to any device in the network having maximum probability of delivering the message to destination. Maxprop process involves calculating the path for each message at each transfer opportunity using a modified Dijkstra algorithm with history as pivotal criterion. Maxprop defines its own way of computing history to dictate the channel path computation, further it assumes that the network topology on which it is operating does not consume bandwidth. It also incorporates a fancy mechanism of message queuing at peer level that prefers the newly born messages and degrades the priority of messages based on the number of hops they have traveled and the delivery probability [13]. Even without the computational complexity of erasure coding, Maxprop is hungry for processing resources, as the maintenance of the local queue is expensive for mobile devices under high message counts.

General Specs

Remarks

Network Environment

Vehicular area disruption tolerant network

Application

Business

Algorithm1

[7]

Efficiency Parameters

Delivery rate

Function of transmission range

Delivery delay

Inversely proportional to transmission range

Advantage

Lower latency

Disadvantage

-

Future extensions

-

Earliest Delivery:

In this technique [8], path of a message is computed using modified Dijkstra algorithm, where the link costs represent the waiting time for the next contact between the vertices. It assumes a contact oracle, which has perfect foresight of future node encounters, equivalent to knowing the time-varying DTN multi-graph. This algorithm is bound to perform better than all of the others because it has the unrealistic knowledge of the future, BUT NOT NECESSARILY TRUE. A message may still fail to reach the destination due to complete lack of a path to destination or congestion.

X Sumarry & conclusion

This paper introduces the basics of routing, its objectives & purpose, types, classification groups and collectively discusses 18 different routing techniques; leading to identification of critical & explicit parameters of each of the technique studied.

Mobility model based on simulation depicts the movement patterns of mobile nodes; data utilized for the purpose of software based simulation and analysis have been used by other researchers earlier and predict by simulation, with fair accuracy the real situations existing while evaluating the model functions - protocol. Moreover, parameter-items relating to application environment express the limitations of protocol as mentioned by the author(s) under respective titles in this paper. As detailed under table-1, several schemes can be applied to general mobile network, followed by some assumptions and approximations that steer towards a near optimal routing solution and a possible optimal network topology - to be evolved in due course.

Further, the essence of the 18 techniques studied along with quantifiable parameter and details like mobility models, application environment and protocols etc., is captured and showcased under table-1.

Writing Services

Essay Writing
Service

Find out how the very best essay writing service can help you accomplish more and achieve higher marks today.

Assignment Writing Service

From complicated assignments to tricky tasks, our experts can tackle virtually any question thrown at them.

Dissertation Writing Service

A dissertation (also known as a thesis or research project) is probably the most important piece of work for any student! From full dissertations to individual chapters, we’re on hand to support you.

Coursework Writing Service

Our expert qualified writers can help you get your coursework right first time, every time.

Dissertation Proposal Service

The first step to completing a dissertation is to create a proposal that talks about what you wish to do. Our experts can design suitable methodologies - perfect to help you get started with a dissertation.

Report Writing
Service

Reports for any audience. Perfectly structured, professionally written, and tailored to suit your exact requirements.

Essay Skeleton Answer Service

If you’re just looking for some help to get started on an essay, our outline service provides you with a perfect essay plan.

Marking & Proofreading Service

Not sure if your work is hitting the mark? Struggling to get feedback from your lecturer? Our premium marking service was created just for you - get the feedback you deserve now.

Exam Revision
Service

Exams can be one of the most stressful experiences you’ll ever have! Revision is key, and we’re here to help. With custom created revision notes and exam answers, you’ll never feel underprepared again.