Dynamic Control of Coding for

Progressive Packet Arrivals in DTNs

ABSTRACT

In Delay Tolerant Networks (DTNs) the core challenge is to cope with lack of persistent

connectivity and yet be able to deliver messages from source to destination. In particular, routing

schemes that leverage relays’ memory and mobility are a customary solution in order to improve

message delivery delay. When large files need to be transferred from source to destination, not

all packets may be available at the source prior to the first transmission. This motivates us to

study general packet arrivals at the source, derive performance analysis of replication based

routing policies and study their optimization under two hop routing. In particular, we determine

the conditions for optimality in terms of probability of successful delivery and mean delay and

we devise optimal policies, so-called piecewise-threshold policies. We account for linear block-

codes and rate less random linear coding to efficiently generate redundancy, as well as for an

energy constraint in the optimization. We numerically assess the higher efficiency of piecewise-

threshold policies compared with other policies by developing heuristic optimization of the

thresholds for all flavors of coding considered.

 Dynamic Control of Coding for
Progressive Packet Arrivals in DTNs

1. PREAMBLE

1.1 GENERAL INTRODUCTION

What is networking?

Networking is the word basically relating to computers and their connectivity. It is very often

used in the world of computers and their use in different connections. The term networking

implies the link between two or more computers and their devices, with the vital purpose of

sharing the data stored in the computers, with each other. The networks between the computing

devices are very common these days due to the launch of various hardware and computer

software which aid in making the activity much more convenient to build and use.

Structure of Networking between the different computers

 Dynamic Control of Coding for
Progressive Packet Arrivals in DTNs

How networking works?

General Network Techniques - When computers communicate on a network, they send out data

packets without knowing if anyone is listening. Computers in a network all have a connection to

the network and that is called to be connected to a network bus. What one computer sends out

will reach all the other computers on the local network.

 Dynamic Control of Coding for
Progressive Packet Arrivals in DTNs

Above diagrams show the clear idea about the networking functions

For the different computers to be able to distinguish between each other, every computer has a

unique ID called MAC-address (Media Access Control Address). This address is not only unique

on your network but unique for all devices that can be hooked up to a network. The MAC-

address is tied to the hardware and has nothing to do with IP-addresses. Since all computers on

the network receives everything that is sent out from all other computers the MAC-addresses is

primarily used by the computers to filter out incoming network traffic that is addressed to the

individual computer.

When a computer communicates with another computer on the network, it sends out both the

other computers MAC-address and the MAC-address of its own. In that way the receiving

computer will not only recognize that this packet is for me but also, who sent this data packet so

a return response can be sent to the sender.

On an Ethernet network as described here, all computers hear all network traffic since they are

connected to the same bus. This network structure is called multi-drop.

One problem with this network structure is that when you have, let say ten (10) computers on a

network and they communicate frequently and due to that they sends out there data packets

randomly, collisions occur when two or more computers sends data at the same time. When that

happens data gets corrupted and has to be resent. On a network that is heavy loaded even the

resent packets collide with other packets and have to be resent again. In reality this soon

becomes a bandwidth problem. If several computers communicate with each other at high speed

they may not be able to utilize more than 25% of the total network bandwidth since the rest of
 Dynamic Control of Coding for
Progressive Packet Arrivals in DTNs

the bandwidth is used for resending previously corrupted packets. The way to minimize this

problem is to use network switches.

Characteristics of Networking:

The following characteristics should be considered in network design and ongoing maintenance:

1) Availability is typically measured in a percentage based on the number of minutes that

exist in a year. Therefore, uptime would be the number of minutes the network is

available divided by the number of minutes in a year.

2) Cost includes the cost of the network components, their installation, and their ongoing

maintenance.

3) Reliability defines the reliability of the network components and the connectivity

between them. Mean time between failures (MTBF) is commonly used to measure

reliability.

4) Security includes the protection of the network components and the data they contain

and/or the data transmitted between them.

5) Speed includes how fast data is transmitted between network end points (the data rate).

6) Scalability defines how well the network can adapt to new growth, including new users,

applications, and network components.

7) Topology describes the physical cabling layout and the logical way data moves between

components.
 Dynamic Control of Coding for
Progressive Packet Arrivals in DTNs

Types of Networks:

Organizations of different structures, sizes, and budgets need different types of networks.

Networks can be divided into one of two categories:

 peer-to-peer

 server-based networks

1. Peer-to-Peer Network:

A peer-to-peer network has no dedicated servers; instead, a number of workstations are

connected together for the purpose of sharing information or devices. Peer-to-peer networks are

designed to satisfy the networking needs of home networks or of small companies that do not

want to spend a lot of money on a dedicated server but still want to have the capability to share

information or devices like in school, college, cyber cafe

2. Server-Based Networks:

In server-based network data files that will be used by all of the users are stored on the one

server. With a server-based network, the network server stores a list of users who may use

network resources and usually holds the resources as well.

This will help by giving you a central point to set up permissions on the data files, and it will

give you a central point from which to back up all of the data in case data loss should occur.

Network Communications:

 Computer networks use signals to transmit data, and protocols are the languages computers

use to communicate.

 Protocols provide a variety of communications services to the computers on the network.

 Dynamic Control of Coding for
Progressive Packet Arrivals in DTNs

 Local area networks connect computers using a shared, half-duplex, baseband medium, and

wide area networks link distant networks.

 Enterprise networks often consist of clients and servers on horizontal segments connected by a

common backbone, while peer-to-peer networks consist of a small number of computers on a

single LAN.

Advantages of Networking:

1. Easy Communication:

It is very easy to communicate through a network. People can communicate efficiently using a

network with a group of people. They can enjoy the benefit of emails, instant messaging,

telephony, video conferencing, chat rooms, etc.

2. Ability to Share Files, Data and Information:

This is one of the major advantages of networking computers. People can find and share

information and data because of networking. This is beneficial for large organizations to

maintain their data in an organized manner and facilitate access for desired people.

3. Sharing Hardware:

Another important advantage of networking is the ability to share hardware. For an example, a

printer can be shared among the users in a network so that there’s no need to have individual

printers for each and every computer in the company. This will significantly reduce the cost of

purchasing hardware.

4. Sharing Software:
 Dynamic Control of Coding for
Progressive Packet Arrivals in DTNs

Users can share software within the network easily. Networkable versions of software are

available at considerable savings compared to individually licensed version of the same software.

Therefore large companies can reduce the cost of buying software by networking their

computers.

5. Security:

Sensitive files and programs on a network can be password protected. Then those files can only

be accessed by the authorized users. This is another important advantage of networking when

there are concerns about security issues. Also each and every user has their own set of privileges

to prevent those accessing restricted files and programs.

6. Speed:

Sharing and transferring files within networks is very rapid, depending on the type of network.

This will save time while maintaining the integrity of files.

1.2 STATEMENT OF THE PROBLEM

In Delay Tolerant Networks (DTNs) the core challenge is to cope with lack of persistent

connectivity and yet be able to deliver messages from source to destination. Since many
 Dynamic Control of Coding for
Progressive Packet Arrivals in DTNs

relay nodes (and thus network resources) may be involved in ensuring successful delivery, it

becomes crucial to design efficient resource allocation and data storage protocols.

1.3 OBJECTIVE

The main objective of the project is derive performance analysis of replicationbased routing

policies and study their optimization under twohop routing. we determine the conditions for

optimality in terms of probability of successful delivery and mean delay and we devise optimal

policies, so-called piecewise-threshold policies.

1.4 SCOPE

In the basic scenario, the source has initially all the packets. Under this assumption it was shown

in [2] that the transmission policy has a threshold structure: it is optimal to use all opportunities

to spread packets till some time σ depending on the energy constraint, and then stop. This policy

resembles the well-known “Spray-and-Wait” policy [3]. In this work we assume a more general

arrival process of packets: they need not to be simultaneously available for transmission initially,

i.e., when forwarding starts, as assumed in [2]. This is the case when large multimedia files are

recorded at the source node (from, e.g., a cellular base station) that sends them out (in a DTN

fashion) without waiting for the whole file reception. Contributions. This paper focuses on

general packet arrivals at the source and two-hop routing.

 Dynamic Control of Coding for
Progressive Packet Arrivals in DTNs

1.5 LIMITATIONS

For work-conserving policies (i.e., the source sends systematically before stopping completely),

we derive the conditions for optimality in terms of probability of successful delivery and mean

delay.

• In the case of non-overwriting, we prove that the best policies, in terms of delivery probability,

are piecewisethreshold. For the overwriting case, work-conserving policies are the best without

energy constraint, but are outperformed by piecewise-threshold policies when there is an energy

constraint.

• We extend the above analysis to the case where copies are coded packets, generated both with

linear blockcodes and rateless coding. We also account for an energy constraint in the

optimization.

• We illustrate numerically, in the non-overwriting case, the higher efficiency of piecewise-

threshold policies compared with work-conserving policies by developing a heuristic

optimization of the thresholds for all flavors of coding considered. As well, in the overwriting

case, we show that work-conserving policies are the best without any energy constraint.

1.6 REVIEW OF LITERATURE

 Dynamic Control of Coding for
Progressive Packet Arrivals in DTNs

1) Dynamic control of coding in delay tolerant networks

AUTHORS: E. Altman, F. De Pellegrini, and L. Sassatelli

We study replication mechanisms that include Reed-Solomon type codes as well as network

coding in order to improve the probability of successful delivery within a given time limit. We

propose an analytical approach to compute these and study the effect of coding on the

performance of the network while optimizing parameters that govern routing.

 Dynamic Control of Coding for
Progressive Packet Arrivals in DTNs

2) Forward correction and Fountain codes in delay tolerant networks

AUTHORS: E. Altman and F. De Pellegrini

Delay-tolerant ad hoc networks leverage the mobility of relay nodes to compensate for lack of

permanent connectivity and thus enable communication between nodes that are out of range of

each other. To decrease delivery delay, the information to be delivered is replicated in the

network. Our objective in this paper is to study a class of replication mechanisms that include

coding in order to improve the probability of successful delivery within a given time limit. We

propose an analytical approach that allows to quantify tradeoffs between resources and

performance measures (energy and delay). We study the effect of coding on the performance of

the network while optimizing parameters that govern routing. Our results, based on fluid

approximations, are compared to simulations that validate the model.

 Dynamic Control of Coding for
Progressive Packet Arrivals in DTNs

3) Efficient routing in intermittently connected mobile networks: the multi-copy case

AUTHORS: T. Spyropoulos, K. Psounis, and C. Raghavendra

Intermittently connected mobile networks are wireless networks where most of the time there

does not exist a complete path from the source to the destination. There are many real networks

that follow this model, for example, wildlife tracking sensor networks, military networks,

vehicular ad hoc networks, etc. In this context, conventional routing schemes fail, because they

try to establish complete end-to-end paths, before any data is sent.

To deal with such networks researchers have suggested to use flooding-based routing schemes.

While flooding-based schemes have a high probability of delivery, they waste a lot of energy and

suffer from severe contention which can significantly degrade their performance. Furthermore,

proposed efforts to reduce the overhead of flooding-based schemes have often been plagued by

large delays. With this in mind, we introduce a new family routing schemes that "spray" a few

message copies into the network, and then route each copy independently towards the

destination. We show that, if carefully designed, spray routing not only performs significantly

fewer transmissions per message, but also has lower average delivery delays than existing

schemes; furthermore, it is highly scalable and retains good performance under a large range of

scenarios.
 Dynamic Control of Coding for
Progressive Packet Arrivals in DTNs

Finally, we use our theoretical framework proposed in our 2004 paper to analyze the

performance of spray routing. We also use this theory to show how to choose the number of

copies to be sprayed and how to optimally distribute these copies to relays.

4) Optimal monotone forwarding policies in delay tolerant mobile ad-hoc networks

AUTHORS: E. Altman, T. Bas¸ar, and F. De Pellegrini

In this paper we describe a framework for the optimal control of delay tolerant mobile ad hoc

networks where multiple classes of nodes co-exist. We specialize the description of the energy-

delay tradeoffs as an optimization problem based on a fluid approximation. We then adopt two

product forms to model message diffusion and show that optimal controls are of bang-bang type.

Under this general framework, we analyze some specific cases of interest for applications.
 Dynamic Control of Coding for
Progressive Packet Arrivals in DTNs

5) Parity-based loss recovery for reliable multicast transmission

AUTHORS: J. Nonnenmacher, E. Biersack, and D. Towsley

We investigate how forward error correction (FEC) can be combined with automatic repeat

request (ARQ) to achieve scalable reliable multicast transmission. We consider the two scenarios

where FEC is introduced as a transparent layer underneath a reliable multicast layer that uses

ARQ, and where FEC and ARQ are both integrated into a single layer that uses the

retransmission of parity data to recover from the loss of original data packets. To evaluate the

performance improvements due to FEC, we consider different loss rates and different types of

loss behavior (spatially or temporally correlated loss, homogeneous or heterogeneous loss) for up

to 106 receivers. Our results show that introducing FEC as a transparent layer below ARQ can

improve multicast transmission efficiency and scalability. However, there are substantial

additional improvements when FEC and ARQ are integrated.