DTN Research Group W. Moreira
Internet-Draft P. Mendes
Expires: April 25, 2013 SITI, Universidade Lusofona
R. Ferreira
E. Cerqueira
ITEC, Universidade Federal do Para
October 22, 2012
Opportunistic Routing based on Users Daily Life Routine
draft-moreira-dlife-01
Abstract
This document is written in the context of the Delay Tolerant
Networking Research Group and will be presented for reviewing by that
group. This document defines dLife, an opportunistic routing protocol
that takes advantage of time-evolving social structures. dLife
belongs to the family of social-aware opportunistic routing protocols
for intermittently connected networks. dLife operates based on a
representation of the dynamics of social structures as a weighted
contact graph, where the weights (i.e., social strengths) express how
long a pair of nodes is in contact over different period of times. It
considers two complementary utility functions: Time-Evolving Contact
Duration (TECD) that captures the evolution of social interaction
among pairs of users in the same daily period of time, over
consecutive days; and TECD Importance (TECDi) that captures the
evolution of user's importance, based on its node degree and the
social strength towards its neighbors, in different periods of time.
It is intended for use in wireless networks where there is no
guarantee that a fully connected path between any source -
destination pair exists at any time, a scenario where traditional
routing protocols are unable to deliver bundles. Such networks can be
sparse mesh, in which case intermittent connectivity is due to lack
of physical connections, or dense mesh, in which case intermittent
connectivity may be due to high interference or shadowing. In any
case, intermittent connectivity can also be due to the availability
of devices (e.g., unavailable due to power saving rules). The
document presents an architectural overview followed by the protocol
specification.
Status of this Memo
This Internet-Draft is submitted to IETF in full conformance with the
provisions of BCP 78 and BCP 79.
Moreira, et al. Expires April 25, 2013 [Page 1]
Internet-Draft dLife October 22, 2012
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on April 25, 2012.
Copyright and License Notice
Copyright (c) 2012 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1. Applicability of the Protocol . . . . . . . . . . . . . . . 5
1.1.1. Protocol Stack . . . . . . . . . . . . . . . . . . . . 5
1.1.2. Applicability scenarios . . . . . . . . . . . . . . . . 6
1.1.2.1. Urban Areas Networks . . . . . . . . . . . . . . . 6
1.1.2.2. Mission-critical Networks . . . . . . . . . . . . . 7
1.2. Relation with the DTN Architecture and Networking Model . . 7
1.3. Differentiation to other Opportunistic Routing Proposal . . 9
1.4. Requirements notation . . . . . . . . . . . . . . . . . . . 10
2. Node Architecture . . . . . . . . . . . . . . . . . . . . . . . 10
2.1. dLife Components . . . . . . . . . . . . . . . . . . . . . 11
2.2. Routing Algorithm . . . . . . . . . . . . . . . . . . . . . 12
2.2.1. Time-Evolving Contact Duration (TECD) . . . . . . . . . 13
2.2.2. TECD Importance (TECDi) . . . . . . . . . . . . . . . . 14
2.3. Forwarding strategy . . . . . . . . . . . . . . . . . . . . 15
2.3.1. Basic Strategy . . . . . . . . . . . . . . . . . . . . 15
2.3.2. Prioritized Strategy . . . . . . . . . . . . . . . . . 15
Moreira, et al. Expires April 25, 2013 [Page 2]
Internet-Draft dLife October 22, 2012
2.4. Interfaces . . . . . . . . . . . . . . . . . . . . . . . . 15
2.4.1. Bundle Agent . . . . . . . . . . . . . . . . . . . . . 16
2.4.2 Lower Layers . . . . . . . . . . . . . . . . . . . . . . 16
3. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . . 17
3.1. Neighbor Sensing Phase . . . . . . . . . . . . . . . . . . 18
3.2. Information Exchange Phase . . . . . . . . . . . . . . . . 19
3.2.1. EID Dictionary . . . . . . . . . . . . . . . . . . . . 20
3.2.2. Operation in the presence of multiples neighbors . . . 21
3.3. Bundle Reception Policies . . . . . . . . . . . . . . . . . 21
3.3.1. Queueing policy . . . . . . . . . . . . . . . . . . . . 21
3.3.2. Custody Policy . . . . . . . . . . . . . . . . . . . . 22
3.3.3. Destination Policy . . . . . . . . . . . . . . . . . . 23
4. Message Formats . . . . . . . . . . . . . . . . . . . . . . . . 23
4.1. Header . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.2. TLV Structure . . . . . . . . . . . . . . . . . . . . . . . 27
4.3. TLVs . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.3.1. Hello TLV . . . . . . . . . . . . . . . . . . . . . . . 28
4.3.2. ACK TLV . . . . . . . . . . . . . . . . . . . . . . . . 30
4.3.3. EID Dictionary TLV . . . . . . . . . . . . . . . . . . 31
4.3.4. Social TLV . . . . . . . . . . . . . . . . . . . . . . 33
5. Detailed Operation . . . . . . . . . . . . . . . . . . . . . . 35
5.1. High Level State Tables . . . . . . . . . . . . . . . . . . 35
5.2. High Level Meta-Data Table . . . . . . . . . . . . . . . . 38
5.3 Hello Procedure . . . . . . . . . . . . . . . . . . . . . . 40
5.4 Information Exchange Phase . . . . . . . . . . . . . . . . . 42
6. Security Considerations . . . . . . . . . . . . . . . . . . . . 43
7. Implementation Experience . . . . . . . . . . . . . . . . . . . 45
8. Deployment Experience . . . . . . . . . . . . . . . . . . . . . 47
9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 48
9.1 Normative References . . . . . . . . . . . . . . . . . . . 48
9.2 Informative References . . . . . . . . . . . . . . . . . . 49
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 50
Moreira, et al. Expires April 25, 2013 [Page 3]
Internet-Draft dLife October 22, 2012
1. Introduction
The pervasive deployment of wireless personal devices is creating the
opportunity for the development of novel applications. The
exploitation of such applications with a good performance-cost
tradeoff is possible by allowing devices to use free spectrum to
exchange data whenever they are within wireless range, specially in
scenarios where it is difficult to find an end-to-end path between
any pair of nodes at any moment. In such scenarios every contact is
an opportunity to forward data. Hence, there is the need to develop
networking solutions able to buffer messages at intermediate nodes
for a longer time than normally occurs in the queues of conventional
routers (cf. Delay-Tolerant Networking [RFC4838]), and routing
algorithms able to bring such messages close to a destination, with
high probability, low delay and costs.
Most of the proposed routing solutions focus on inter-contact times
alone [Chaintreau06], while there is still significant investigation
to understand the nature of such statistics (e.g., power-law,
behavior dependent on node context). Moreover, the major drawback of
such approaches is the instability of the created proximity graphs
[Hui11], which changes with users' mobility.
A recent trend is investigating the impact that more stable social
structures (inferred from the social nature of human mobility) have
on opportunistic routing [Hui11], [Daly07]. Such social structures
are created based on social similarity metrics that allow the
identification of the centrality that nodes have in a
cluster/community. This allows forwarders to use the identified hub
nodes to increase the probability of delivering messages inside
(local centrality) or outside (global centrality) a community, based
on the assumption that the probability of nodes to meet each other is
proportional to the strength of their social connection.
A major limitation of approaches that identify social structures,
such as communities, is the lack of consideration about the dynamics
of networks, which refers to the evolving structure of the network
itself, the making and braking of network ties: over a day a user
meets different people at every moment. Thus, the user's personal
network changes, and so does the global structure of the social
network to which he/she belongs.
When considering dynamic social similarity, it is imperative to
accurately represent the actual daily interaction among users: it has
been shown [Hossmann10] that social interactions extracted from
proximity graphs must be mapped into a cleaner social connectivity
representation (i.e., comprising only stable social contacts) to
improve forwarding. This motivates us to specify a routing protocol
Moreira, et al. Expires April 25, 2013 [Page 4]
Internet-Draft dLife October 22, 2012
aware of the network dynamics, represented by users' daily life
routine. We focus on the representation of daily routines, since
routines can be used to identify future interaction among users
sharing similar movement patterns, interests, and communities
[Eagle09].
Existing proposals [Costa08], [Hui11], [Daly07] succeed in
identifying similarities (e.g., interests) among users, but their
performance is affected as dynamism derived from users' daily
routines is not considered. To address this challenge, we propose
dLife that uses time-evolving social structures to reflect the
different behavior that users have in different daily periods of
time: dLife represents the dynamics of social structures as a
weighted contact graph, where the weights (i.e., social strengths)
express how long a pair of nodes is in contact over different period
of times.
dLife considers two complementary utility functions: Time-Evolving
Contact Duration (TECD) that captures the evolution of social
interaction among pairs of users in the same daily period of time,
over consecutive days; and TECD Importance (TECDi) that captures the
evolution of user's importance, based on its node degree and the
social strength towards its neighbors, in different periods of time.
1.1. Applicability of the Protocol
This section describes the applicability of the dLife protocol in
terms of the networking protocol stack and in terms of the usage
scenarios that are representative of the daily life experience of
most people. The latter aims to check which are the communication
challenges that can be mitigated by deploying a delay-tolerant
routing protocol. The focus goes to scenarios involving mission-
critical environments that represent sporadic situations that require
a spontaneous and efficient exchange of information, as well as
communications in urban environments, which can also benefit from the
existence of a DTN.
This document does not focus on scenarios such as space networks and
rural area networks, since space networks rely on the usage of single
links with extreme long delay, while most of the potential rural area
scenarios will require a store-and-carry system (ferry type) and not
so much a store-carry-forward system.
1.1.1. Protocol Stack
The dLife protocol is expected to interact with the Bundle Protocol
agent for retrieving information about available bundles and for
requesting bundles to be sent to another node (cf. section 2.4.1). It
Moreira, et al. Expires April 25, 2013 [Page 5]
Internet-Draft dLife October 22, 2012
is expected that the associated bundle agents are then able to
establish a link, over the TCP convergence layer [I-D.irtf-dtnrg-tcp-
clayer]) or the UDP convergence layer [I-D.irtf-dtnrg-udp-clayer]) to
perform this bundle transfer.
In what concerns information needed for the operation of dLife, dLife
does not impose any requirements for data reliability transfer to
avoid restricting its applicability. Hence, data exchange may take
place over transport protocols that do not provide neither message
segmentation or reliability, nor in order delivery. Hence, dLife
provides itself the capability to segment protocol messages into
submessages. Submessages are provided with sequence numbers, and
this, together with the capability for positive acknowledgements
allows dLife to operate over an unreliable protocol such as UDP or
potentially directly over IP. As said for the bundle agent, the
communication medium used to send dLife messaged can include
different technologies such as Bluetooth and Wi-Fi.
Moreover, dLife expects to be able to use bidirectional links for
information exchange; this allows information exchange to take place
in both directions over the same link, avoiding the need to establish
a second link for information exchange in the reverse direction.
1.1.2. Applicability scenarios
The identified scenarios aim to illustrate the applicability of dLife
in real scenarios. In technical terms, dLife aims to target networks
where we may not find any end-to-end path between any pair of nodes
at some moment in time. The lack of end-to-end path may be due to
node mobility and availability (e.g., switching off radios), aspects
that create connectivity patterns that are correlated with the daily
habits of citizens. Human behavior patterns (often containing daily
or weekly periodic activities) provide one example where dLife is
expected to be applicable, independently of the type of personal
device: it can be of explicit usage (e.g., smartphones) or of
implicit usage (e.g., embedded devices).
Scientific results [Moreira12a] [Moreira12b] show that dLife is able
to benefit from the predictability of human behavior in daily periods
of time even in the presence of few contacts. However, the behavior
predictability can be estimated more accurately with a higher number
of events.
1.1.2.1. Urban Areas Networks
This seems to be the most challenging scenario to analyze the
applicability of DTN employing dLife as the store-carry-forward
routing protocol. A study of DTN routing for urban scenarios may
Moreira, et al. Expires April 25, 2013 [Page 6]
Internet-Draft dLife October 22, 2012
bring a coherent understanding about the advantages and challenges of
using a DTN system in the daily life of millions of people. A study
of the applicability of DTN routing in urban scenarios may benefit
from a good understanding of the per-person bit density (available
capacity per second/hour/day) in a major metropolitan area.
In a urban area there are several examples of networking scenario
that can gain from the applicability of dLife, such as: Urban " dark"
places due to high mobility (e.g., fast trains), indoors (e.g.,
subway systems, in-building) and outdoor (e.g., areas with closed
APs, areas with significant interference); Off-load of cellular
networks, since cellular operators do not like to have data traffic
unrelated to services provided in their networks; The cost of
cellular wireless data, which decreases the relation quality/price of
cellular data communications; Networks of embedded objects, which
will require delay-tolerant communications over short-distance
wireless interfaces and not over cellular ones.
1.1.2.2. Mission-critical Networks
At any point, natural catastrophes can happen and such type of
network can be deployed in order to facilitate rescue and medical
operations. Another type of situation that a mission-critical network
may be formed is in hostile environment such as war scenarios.
Independently of the scenario for its application, this type of
networks must be readily available through any sort of Wi-Fi enabled
equipment (PDAs, cell phones, laptops, APs) which are expected to
cooperate with the aim of helping the dissemination of information.
Information must reach the interested parties as quickly as possible
to achieve fast results for the actions being taken.
In mission-critical networks there are several examples of networking
scenario that can gain from the applicability of dLife, such as:
Disaster networks where no (maybe very few) infrastructure is
available since it may have been destroyed; Military networks, where
communications can be established using devices carried by soldiers
as well as other military vehicles and easily deployed equipments.
1.2. Relation with the DTN Architecture and Networking Model
The DTN architecture introduces the bundle protocol [RFC5050], which
provides a way for applications to "bundle" an entire session,
including both data and meta-data, into a single message, or bundle,
that can be sent as a unit. The bundle protocol provides end-to-end
addressing and acknowledgments. Hence, dLife is intended to provide
routing services in a network environment that uses bundles as its
data transfer mechanism, but could also be used in other intermittent
environments.
Moreira, et al. Expires April 25, 2013 [Page 7]
Internet-Draft dLife October 22, 2012
From a networking model perspective, a DTN is a network of self-
organizing wireless nodes connected by multiple time-varying links,
and where end-to-end connectivity is intermittent. Even in urban
scenarios, it is possible to face intermittent connectivity due to
dark areas, such as inside buildings and metropolitan systems, as
well as public areas with closed access points or even places
overcrowded with wireless access points. Unavailability of wireless
connectivity can be also a result of power-constrained nodes that
frequently shut down their wireless cards to save energy.
From a conceptual point of view, a DTN consists of a node meeting
schedule and workload. A node meeting schedule is a directed
multigraph where each direct edge between two nodes represents a
meeting opportunity between them, and it is annotated with a starting
time of the meeting, the ending time of the meeting, if known, the
size of the transfer opportunity (i.e., contact capacity), and the
contact type. The workload is a set of messages. Each message can be
represented by the source, destination, size, time of creation at the
source, and priority. In dLife, a contact is defined by the tuple
<starting time, end time, contact duration> and a message by the
tuple <source, destination, size>.
A DTN model encompasses the notion of type of contact or
connectivity. In current networks, the connectivity of a link or path
is generally given as a binary state (i.e., connected or
disconnected). In DTNs, a richer set of connectivity options is
required to make efficient routing decisions. Most importantly, links
(and paths, by extension) may provide a scheduled, predicted or
opportunistic communication.
Scheduled contacts imply some a priori knowledge about adjacent nodes
regarding future availability of links for message forwarding.
Scheduled links are the most typical cases for today's Internet and
satellite networks. Predicted contacts correspond to communication
opportunities wherein the probability of knowing whether a link will
be available at a future point in time is strictly above zero and
below one. Such links are the result of observed behavior (e.g., a
person may use its home Internet connection with significant
probability for any given time period) being characterized using
statistical estimation. Predicted links are only becoming of serious
concern recently, namely in ad-hoc wireless networks where node
mobility may be significant.
In more challenging environments, such as mission-critical networks
for instance, the future location of communicating entities may be
neither known nor predictable. These types of contacts are known as
opportunistic. Such opportunistic contacts are defined as a chance to
forward messages towards a specific destination or a group of
Moreira, et al. Expires April 25, 2013 [Page 8]
Internet-Draft dLife October 22, 2012
destinations. In such unpredictable scenario, it is important to take
into account the time that a node must wait until it meets another
node again (i.e., inter-contact time), the duration of these contacts
(i.e., contact duration), and the quality of the contact in terms of
the set of information that can be transferred (i.e., contact
volume).
Independently of the type of connectivity, a contact in a DTN is
direction-specific. For example, a dial-up connection originating at
a customer's home to an Internet Service Provider (ISP) may be
scheduled from the point of view of the customer but unscheduled from
the point of view of the ISP. In what concerns contacts, dLife
assumes direction-specific opportunistic contacts (starting time, end
time, contact duration) which occur with some probability in pre-
defined daily time periods.
Another concept that must be introduced is that of network behavior.
As networks can be formed on-the-fly, their behavior can either be
deterministic or stochastic, depending on the type of used links. In
this draft, we focus on dynamic scenarios where the behavior of the
network is described in stochastic terms, based on users' mobility
and social behavior. In a dynamic scenario, users move around
carrying their personal devices, which opportunistically come into
contact with each other, resulting in topology changes.
1.3. Differentiation to other Opportunistic Routing Proposal
Due to intermittent connectivity, routing protocols based on the
knowledge of end-to-end paths perform poorly, and numerous
opportunistic routing algorithms have been proposed instead. Some
opportunistic routing protocols use replicas of the same message to
combat the inherent uncertainty of future communication opportunities
between nodes. In order to carefully use the available resources and
reach short delays, many protocols perform forwarding decisions using
locally collected knowledge about node behavior to predict which
nodes are likely to deliver a content or bring it closer to the
destination.
We previously identified [Moreira11] that most of the opportunistic
routing prior-art considered the replication-based forwarding scheme,
while only 15% were based on single-copy and flooding-based
forwarding schemes. Among the replication based solutions,
approximately 69% consider a contact-based approach (e.g., frequency
of encounters) and 31% (the latest ones) investigate a new trend
based on social similarity metrics (e.g., community detection).
Contact-based proposals consider every contact among nodes to update
the proximity graph and implement metrics such as the number of times
nodes meet, contact frequency and the last time a contact occurs.
Moreira, et al. Expires April 25, 2013 [Page 9]
Internet-Draft dLife October 22, 2012
Besides PROPHET [Lindgren04], the most cited replication-based
proposal, other examples based on contact metric are Prediction
[Song07], and Encounter -Based Routing [Nelson09].
Most of the existing opportunistic routing solutions are based on
some level of replication. Among these proposals, emerge solutions
based on different representations of social similarity: i) labeling
users according to their social groups (e.g., Label [Hui07]); ii)
looking at the importance (i.e., popularity) of nodes (e.g.,
PeopleRank [Mtibaa10]); iii) combining the notion of community and
centrality (e.g., SimBet [Daly07] and Bubble Rap [Hui11]); iv)
considering interests that users have in common (e.g., SocialCast
[Costa08]). Such prior-art shows that social-based solutions are more
stable than those which only consider node mobility. However, they do
not consider the dynamism of users' behavior (i.e., social daily
routines) and use centrality metrics, which may create bottlenecks in
the network. Moreover, such approaches assume that communities remain
static after creation, which is not a realistic assumption. On the
other hand, prior-art also shows that users have routines that can be
used to derive future behavior. It has been proven that mapping real
social interactions to a clean (i.e., more stable) connectivity
representation is rather useful to improve delivery. With dLife,
users' daily routines are considered to quantify the time-evolving
strength of social interactions and so to foresee more accurately
future social contacts than with proximity graphs inferred directly
from inter-contact times.
1.4. Requirements notation
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [RFC2119].
2. Node Architecture
In this section we describe the architecture of a dLife node, which
performs its routing decisions based on two utility functions: TECD
to forward messages to nodes that have a stronger social relationship
with the destination than the carrier; TECDi to forward messages to
nodes that have a higher importance than the carrier.
With TECD each node computes the average of its contact duration with
other nodes during the same set of daily time periods over
consecutive days. Our assumptions is that contact duration can
provide more reliable information than contact history, or frequency
when it comes to identifying the strength of social relationships.
The reason for considering different daily time periods relates to
Moreira, et al. Expires April 25, 2013 [Page 10]
Internet-Draft dLife October 22, 2012
the fact that users present different behavior during their daily
routines. If the carrier and encountered node have no social
information towards the destination, forwarding takes place based on
a second utility function, TECDi.
We start this section by describing the different components of the
node architecture, followed by an explanation of how to route
information based on the dynamics of the network that dLife is able
to capture by computing TECD and TECDi. Finally, we describe the
implemented forwarding strategy and the needed interfaces.
2.1. dLife Components
In order to perform forwarding based on the social daily behavior of
users, dLife comprises the following main computational elements:
Social Information Gatherer (SIG) - responsible for: i) keeping
track of the contact duration of each encounter between nodes; and,
ii) obtaining the social weights and importance of encountered
nodes (i.e., potential next forwarders). As dLife considers
different daily samples, corresponding to different periods of
time, it is imperative to keep track of nodes' contacts in each
sample. Thus, the contact duration tracker maintains a list of the
encountered nodes in every daily sample. Additionally, upon the
need to replicate a bundle, SIG will obtain the social weight
between the encountered node and nodes it has met as well as the
importance of such node.
Social Weighter (SW) - responsible for determining the social
weight between nodes according to their social interaction
throughout their daily routines. At the end of every daily sample,
SW will interact with SIG to determine the total contact time nodes
spent together and the average duration of contacts in order to
compute the social weight between nodes.
Importance Assigner (IA) - responsible for computing the importance
of a node taking into account the importance of encountered nodes
and its social weight to such nodes. At the end of every daily
sample, IA will interact with SW and SIG in order to compute the
importance of a node in the system.
Social Information Repository (SIR) - responsible for storing a
list with encountered nodes and contact duration to such nodes. At
the end of every daily sample, SIR will also store social weights
and importance of the encountered nodes computed by SW and IA.
Additionally, SIR will temporarily store the social weight and
importance of an encountered node when the need for replicating a
bundle arises.
Moreira, et al. Expires April 25, 2013 [Page 11]
Internet-Draft dLife October 22, 2012
Decision Maker (DM) - responsible for deciding whether replication
should occur. DM will interact with SIR to obtain relevant
information in order to take decisions.
2.2. Routing Algorithm
The dLife protocol applies the social opportunistic contact paradigm
to decider whether bundle replication is feasible. Its decision is
based on social weight (w_(x,y)) towards the bundle's destination or
on the importance (I(x)) of the encountered node (i.e., potential
next forwarder) in the system.
If the encountered node has better relationship with the bundle
destination than the carrier in a given daily sample, it receives a
bundle copy, since there is a much greater chance for the encountered
node to meet the destination in the future. If relationship to the
bundle destination is unknown, replication happens only if the
encountered node has higher importance than the carrier.
In order to compute the social weight between nodes and their
importance, dLife uses parameters that are determined as nodes
interact in the system. A brief explanation of the parameters is
given below.
CD_(x,y)
Refers to the contact duration between nodes, i.e., time nodes
spent in the range of one another, which would allow them to
exchange information. Within a given daily sample, there could
happen different contacts with varied lengths.
TCT_(x,y)
Refers to the total contact time between nodes within a given
daily sample. It is given by the sum of all CD_(x,y) in that
specific daily sample.
AD_(x,y)
Refers to the average duration of contacts for the same daily
sample over different days. It is a Cumulative Moving Average
(CMA) of the average duration, considering the TCT_(x,y) of the
current daily sample and average duration in the same daily
sample of the previous day, AD_(x,y)_old.
w_(x,y)
Refers to the social weight between nodes at a given daily
sample. It reflects the level of social interaction among such
nodes throughout their daily routines.
Moreira, et al. Expires April 25, 2013 [Page 12]
Internet-Draft dLife October 22, 2012
I_(x)
Refers to the importance of a node in the system. The importance
is influenced by how well a node is socially related to other
important nodes.
N_(x)
Refers to the neighbor set of a node x, which it encountered in
the current daily sample.
dumping factor (d)
Refers the level of randomness considered by the forwarding
algorithm.
daily sample (Ti)
Refers to the time period in which the contact duration will be
measured to determine social weight and node importance.
As nodes interact, their CD_(x,y) is collected and then used to
determine TCT_(x,y), AD_(x,y), w_(x,y), and I_(x) at the end of every
daily sample. The more samples, the more refined the social weight
and node importance will be. Thus, it is recommended the usage of
twenty-four (24) daily samples representing each hour of the day.
2.2.1. Time-Evolving Contact Duration (TECD)
The TECD utility function considers the duration of contacts
(representing the intensity of social ties among users) and time-
evolving interactions (reflecting users' habits over different daily
samples).
Regarding the notations used in the equations presented in this sub-
section: sumk(...) denotes summation for k from 1 to n; sumj(...)
denotes summation for j from i to i+t-1; sumy denotes summation from
all y belonging to N(x).
Two nodes may have a social weight, w_(x,y), that depends on the
average total contact duration they have in that same period of time
over different days. Within a specific daily sample Ti, node x has n
contacts with node y, having each contact k a certain contact
duration, CD_(x,y). At the end of each daily sample, the total
contact time, TCT_(x,y), between nodes x and y is given by the
equation below where n is the total number of contacts between the
two nodes.
TCT_(x,y) = sumk(CD_(x,y)) (1)
The Total Contact Time between users in the same daily sample over
consecutive days can be used to estimate the average duration of
Moreira, et al. Expires April 25, 2013 [Page 13]
Internet-Draft dLife October 22, 2012
their contacts for that specific daily sample: the average duration
of contacts between users x and y during a daily sample Ti in a day
j, denoted by AD_(x,y) is given by a cumulative moving average of
their TCT in that same daily sample, TCT_(x,y), and the average
duration of their contacts during the same daily sample Ti on the
previous day, denoted by AD_(x,y)_old, as shown in the equation
below.
AD_(x,y) = (TCT_(x,y) + (j-1)*AD(x,y)_old)/j (2)
The social strength between users in a specific daily sample Ti may
also provide some insight about their social strength in consecutive
k samples in the same day, i+k. This is what we call Time Transitive
Property. This property increases the probability of nodes being
capable of transmitting large data chunks, since transmission can be
resumed in the next daily sample with high probability.
TECD is able to capture the social strength w_(x,y) between any pair
of users x and y in a daily sample Ti based on the average duration
AD_(x,y) of contacts between them in such daily sample and in
consecutive t-1 samples, where t represents the total number of daily
samples. When k>t, the corresponding AD_(x,y) value refers to the
daily sample k-t. In the equation below the time transitive property
is given by the weight t/(t+k-i), where the highest weight is
associated to the average contact duration in the current daily
sample, being it reduced in consecutive samples.
TECD = w_(x,y) = sumj(t/(t+k-i)*AD_(x,y)) (3)
2.2.2. TECD Importance (TECDi)
As social interaction may also be modeled to consider the node
importance, TECDi computes the importance, I_(x), of a node x (cf.
equation below), considering the weights of the edges between x and
all the nodes y in its neighbor set, N_(x), at a specific daily
sample Ti along with their importance.
TECDi = I_(x) = (1-d)+d*sumy(w_(x,y) * I_(y) / N_(x)) (4)
TECDi is based on the PeopleRank function. However, TECDi considers
not only node importance, but also the strength of social ties
between bundle holder and potential next hops. Another difference is
that with TECDi the neighbor set of a node x only includes the nodes
which have been in contact with node x within a specific daily sample
Ti, whereas in PeopleRank the neighbor set of a node includes all the
nodes that ever had a link to node x. Note that the dumping factor
(d) in the formula is the same used in PeopleRank and represents the
level of randomness considered by the forwarding algorithm.
Moreira, et al. Expires April 25, 2013 [Page 14]
Internet-Draft dLife October 22, 2012
2.3. Forwarding strategy
Independently of application scenario, each node MUST employ a
forwarding strategy. However, if the encountered node is the final
destination of a bundle, the carrier SHOULD prioritize such bundles
by employing the prioritized forwarding strategy, described below.
We use the following notation in our descriptions below. Nodes A and
B are the nodes that encounter each other, and the strategies are
described as they would be applied by node A.
2.3.1. Basic Strategy
Forward the bundle only if w_(B,D) > w_(A,D) or I_(B) > I_(A)
When two nodes A and B meet in any daily sample Ti, node A gets from
node B the latest list of all neighbors of B, with the weights that B
has towards each neighbor, as well as the importance of B. To avoid
unwanted replication, node B also sends a list of the bundles it
already carries (bundle identifier, plus EID of the destination) in
addition to a second list of the BUNDLE_DELIVERED set of the latest
delivered bundles, where BUNDLE_DELIVERED is a threshold configured
accordingly with the node storage capacity. The information about the
social weight, importance, bundle list, and acknowledged bundles,
received from node B are referenced in node A as w_(B,x)_recv,
I_(B)_recv, bundleList(IDn, destinationEIDx)_recv, and
ackedBundleList(IDn, destinationEIDx)_recv, respectively.
For every bundle that A carries in its buffer, and are neither
carried by B nor previously acknowledged by B, node A sends a copy to
B if B has already encountered the bundle's destination D and its
weight in w_(B,D)_recv is greater than A's weight towards this same
destination D. Otherwise, bundles are replicated if I_(B)_recv is
greater than A's importance in the current daily sample Ti.
Finally, node A will update its own ackedBundleList and discard
bundles which have already been acknowledged as described in Section
3.3.3.
2.3.2. Prioritized Strategy
Similar to the basic forwarding strategy, being the only difference
the fact that prior to sending bundles, node A will first send those
bundles that have node B has destination.
2.4. Interfaces
This section provides a specification of the two major interfaces
Moreira, et al. Expires April 25, 2013 [Page 15]
Internet-Draft dLife October 22, 2012
required for dLife operation: the interface between the dLife routing
agent and the bundle agent, and the interface between dLife and the
lower layers.
2.4.1. Bundle Agent
The bundle protocol [RFC5050] introduces the concept of a "bundle
agent" that manages the interface between applications and the
"convergence layers" that provide the transport of bundles between
nodes during communication opportunities. This draft extends the
bundle agent with a routing agent that controls the actions of the
bundle agent during communication opportunities.
This section defines the interface to be implemented between the
bundle agent and the dLife routing agent. The defined interface
follows the general definition that was defined for the PRoPHET
proposal.
In this document we assume that functions in a complete bundle agent
supporting dLife are distributed in such a way that reception and
delivery of bundles are not carried out directly by the dLife agent,
being the bundles placed in a queue available and managed by the
dLife agent. In this case this interface allows the dLife routing
agent to be aware of the bundles placed at the node, and allows it to
inform the bundle agent about the bundles to be sent to a neighbor
node. Therefore, the bundle agent needs to provide the following
interface/functionality to the routing agent:
Get Bundle List
Returns a list of the stored bundles and their attributes to the
routing agent.
Send Bundle
Makes the bundle agent send a specified bundle.
Drop Bundle Advice
Advises the bundle agent that a specified bundle may be dropped
by the bundle agent if appropriate.
2.4.2 Lower Layers
To accommodate dLife operation on different types of wireless
technology, the lower layers SHOULD provide the following
functionality and interfaces.
Neighbor discovery and maintenance
A dLife node needs to: i) know the identity of its neighbors;
ii) when new neighbors appear; iii) when old neighbors
disappear. Some wireless networking technologies might already
contain mechanisms for detecting neighbors and maintaining state
Moreira, et al. Expires April 25, 2013 [Page 16]
Internet-Draft dLife October 22, 2012
about them. Hence, neighbor discovery is not included as a part
of dLife. The lower layers MUST provide the two functions listed
below.
New Neighbor
Signals the dLife agent that a new node has become a neighbor (a
node that is currently within communication range of the current
node, based on the used wireless networking technology). At this
point dLife should start the Neighbor Sensing procedure as
mentioned in section 3.1.
Neighbor Gone
Signals the dLife agent that one of its neighbors has left.
Local Address
An address used by the underlying communication layer (e.g., an
IP or MAC address) that identifies the address of the sender of
the current bundle. This address and its format is dependent on
the communication layer that is being used by the dLife layer.
If the underlying networking technology does not support
neighbor discovery and maintenance services, a simple neighbor
discovery scheme using local broadcasts of beacon messages COULD
be used, assuming that the underlying layer supports broadcast
messages. The operation of the protocol is as follows:
1. Periodically a dLife node does a local broadcast of a
beacon that contains its identity and address.
2. Upon reception of a beacon, the following can happen:
o The sending node is already in the list of active
neighbors. Update its entry in the list with the current
time. At this point dLife should start the Neighbor
Sensing procedure as mentioned in section 3.1.
o The sending node is not in the list of active neighbors.
Add the node to the list of active neighbors and record
the current time.
3. If a beacon has not been received from a node in the list
of active neighbors within a predefined time period, it should
be assumed that this node is no longer a neighbor. The entry
for this node should be removed from the list of active
neighbors.
3. Protocol Overview
Moreira, et al. Expires April 25, 2013 [Page 17]
Internet-Draft dLife October 22, 2012
This section provides a description of the three operational phases
of dLife, namely: neighbor sensing, information exchange, and bundle
reception policies
3.1. Neighbor Sensing Phase
The operation of dLife depends on how nodes interact, i.e.,
considering all the potential contact opportunities to exchange
information. Thus, all nodes running dLife MUST employ a mechanism
for neighbor discovery (cf. section 2.4.2) and neighbor sensing.
If the underlying networking technology does not support neighbor
discovery and maintenance services, a simple neighbor discovery
scheme using local broadcasts of beacon messages CAN be activated
during the Neighbor Sensing phase, assuming that the underlying layer
supports broadcast messages.
When a node (new or already met) is discovered, dLife performs the
following operation:
Start Contact Duration Counting
dLife starts counting the contact duration for the purpose of
later computing social weights and importance.
Hello Procedure
dLife sets up a link with the neighbor node through the Hello
message exchange as described in Section 5.3. The Hello message
exchange allows nodes to exchange information about their End
Point Identifier (EID) and storage capacity. Once the link has
been set up the protocol may continue to the Information
Exchange Phase (cf. Section 3.2), where Hello SYN messages
should be sent periodically to allow peering nodes to detect
broken links.
Stop Contact Duration Counting
dLife stops counting the contact duration after detecting that
the neighbor is gone, due to the lack of periodic Hello SYN
messages.
In order to make use of this time dependence, dLife maintains a list
of recently encountered nodes identified by the Endpoint Identifier
(EID), as described in section 5.2. Each entry of such list includes
information that the node uses to update the status of the current
communication session and to gather information about previous
contacts. The size of this list is controlled, because due to low
storage capacity of nodes, the information related to neighbors that
are not in contact and towards which the current node has a social
weight lower than a predefined threshold SOCIAL_DROP can be dropped
Moreira, et al. Expires April 25, 2013 [Page 18]
Internet-Draft dLife October 22, 2012
from the list.
3.2. Information Exchange Phase
The Information Exchange phase comprises the transfer of two types of
meta-data between connected nodes, through different messages
described in Section 4:
o EID Dictionary
o Social Weights and Node Importance (SWNI)
Upon a communication opportunity, different sets of each type of
meta-data must be sent in each direction as explained further in this
section. Each set may be transferred in one or more messages. In case
a set of meta-data needs more than one message to be completely
transferred, it may be partitioned by the dLife protocol engine. The
specification of dLife provides a sub-message mechanism and
retransmission that allows large messages to be transmitted in
smaller chunks.
Each node running dLife is responsible for computing and updating
their social weights towards previously encountered nodes as well as
their own importance. Thus, in this operational phase, Social TLVs
(Type-Length-Value messages), as defined in section 4.3.4, are
expected to reflect the latest updates regarding SWNI meta-data, as
well as to include the list of bundles carried by the peering node
(bundleList) and the list of the latest bundles delivered by the
peering node (ackedBundleList). Social TLVs are generated throughout
the information exchange phase upon updates of the SWNI information
at the end of a daily sample.
As first step in the Information Exchange Phase one or more messages
containing EID Dictionary meta-data, EID Dictionary TLVs as defined
in section 4.3.3, MUST be sent to the peering node, if the list of
encountered nodes in not empty. Such meta-data contains a dictionary
of the EIDs of the nodes that will be listed in the Social TLVs (cf.
Section 3.2.1 for more information about this dictionary).
As a second step, one or more messages containing social meta-data,
Social TLVs, MUST be sent to the peering node, if the list of
encountered nodes in not empty. This set of messages contains: i) a
list with the EIDs of the nodes that the peering nodes have
encountered so far and their respective social weights towards these
nodes; ii) the importance of the peering nodes; iii) a list with the
identifiers of the bundles that the node currently carries and
respective destinations EIDs; and iv) a list with the latest
acknowledged bundles identifiers and respective destinations EIDs.
Moreira, et al. Expires April 25, 2013 [Page 19]
Internet-Draft dLife October 22, 2012
As a third step, upon reception and acknowledgment of the complete
set of these messages, nodes MUST use one of the defined forwarding
strategies (see Section 2.3) to decide which of the stored bundles
(cf. Get Bundle List on section 2.4.1) will be transferred to the
peer, assuming that there are stored bundles.
The bundles to be sent to the peering node MUST be selected based
upon the exchanged SWNI, bundleList and ackedBundleList information,
as well as the available storage capacity on the receiving peering
node. The bundles to be send by the Bundle Agent (cf. Send Bundle on
section 2.4.1) SHOULD NOT exceed the peering node capacity that MUST
be indicated by the peer during the Hello procedure. The information
to be passed to the Bundle Agent includes the number of bundles to be
send, where each bundle has an ID to be used for acknowledging their
receipt.
3.2.1. EID Dictionary
The EID Dictionary, as used in PRoPHET, is a mapping between variable
length EIDs [RFC4838] and String IDs coded as Self-Delimiting Numeric
Values (SDNVs - see Section 4.1. of RFC 5050 [RFC5050]).
This dictionary is used by peering nodes to synchronize the EIDs of
the nodes that they have encountered before. Each peer MAY add to the
dictionary by sending a EID Dictionary TLV to its peer. To allow
either peer to add to the dictionary at any time, the identifiers
used by each peer are taken from disjoint sets: identifiers
originated by the node that started the Hello procedure have the
least significant bit set to 0 (i.e., are even numbers) whereas those
originated by the other peer have the least significant bit set to 1
(i.e., are odd numbers). This means that the dictionary can be
expanded by either node at any point of the information exchange
phase and the new identifiers can then be used in subsequent TLVs
until the dictionary is reinitialized.
The dictionary that is established only persists through a single
encounter with a node (i.e., while the same link set up by the Hello
procedure, with the same instance numbers, remains open).
Having more than one identifier for the same EID does not cause any
problems. This means that it is possible for the peers to create
their dictionary entries independently if required by an
implementation, but this may be inefficient as a dictionary entry for
an EID might be sent in both directions between the peers. It may be
required to inspect entries sent by the node that started the Hello
procedure and thereby eliminate any duplicates before sending the
dictionary entries from the other peer. Whether postponing sending
the other peer's entries is more efficient depends on the nature of
Moreira, et al. Expires April 25, 2013 [Page 20]
Internet-Draft dLife October 22, 2012
the physical link technology and the transport protocol used. With a
genuinely full duplex link it may be faster to accept possible
duplication and send dictionary entries concurrently in both
directions. If the link is effectively half-duplex (e.g., Wi-Fi),
then it will generally be more efficient to wait and eliminate
duplicates.
If a node receives EID Dictionary meta-data containing an identifier
that is already in use, the node MUST confirm that the corresponding
EID is identical to the EID in the existing entry. Otherwise, the
node MUST send an ACK TLV (i.e., EID ACK - identifier/EID
discrepancy) and ignore the EID Dictionary TLV containing the error.
If a node receives EID Dictionary meta-data that uses an unknown
identifier (i.e., not in the dictionary), the node MUST send an ACK
TLV (i.e., EID ACK - unknown EID) message and ignore the TLV
containing the error.
3.2.2. Operation in the presence of multiples neighbors
As a node may find itself in the range of more than one potential
next forwarder, the neighbor sensing mechanism may establish multiple
information exchanges with each of them.
If these simultaneous contacts persist for some time, then the
information exchange process will be periodically rerun for each
contact according to the configured timer interval, which means that
different Hello TLVs will be exchanged at different times.
Based on the receipt time of these Hello TLVs at the sending node, it
will establish the order for sending out the bundles, considering the
storage capacity of the different neighbors.
3.3. Bundle Reception Policies
3.3.1. Queueing policy
Because of limited buffer resources, bundles may need to be dropped
at some nodes. Although dLife evaluation based on simulations have
shown little consumption due to limiting replication based on social
strength, a scheme MUST be used upon an exhaustion of buffer space.
Hence, each node MUST operate a queueing policy that determines which
bundles should be available for forwarding.
This section defines a few basic queueing policies, inline with what
was proposed for PRoPHET. However, nodes MAY use other policies if
desired. If not chosen differently due to the characteristics of the
deployment scenario, nodes SHOULD choose FIFO as the default queueing
policy.
Moreira, et al. Expires April 25, 2013 [Page 21]
Internet-Draft dLife October 22, 2012
FIFO
Handle the queue in a First In First Out (FIFO) order. The
bundle that was first entered into the queue is the first bundle
to be dropped.
FLNT
The bundle that has been forwarded the largest number of times
is the first to be dropped. For this effect, dLife keeps track
of the number of times each bundle has been forwarded to other
nodes.
STTL
The bundle that has shortest time-to-live is dropped first. As
described in [RFC5050], each bundle has a timeout value
specifying when it no longer is meaningful to its application
and should be deleted. Since bundles with short remaining time
to live will soon be dropped anyway, this policy decides to drop
the bundle with the shortest remaining life time first. To
successfully use a policy like this, there needs to be some form
of time synchronization between nodes so that it is possible to
know the exact lifetimes of bundles.
DLSW
The bundle that has a destination with low social weight is
dropped first. A low social weight means that the carrier may
not be the best forwarder to this bundle. However, such bundle
can only be dropped if it was already forwarded for at least a
Minimum Bundle Forward (MBF) times, which is a minimum number of
forwards that a bundle must have been forwarded before being
dropped (if such a bundle exists).
More than one queueing policy MAY be combined in an ordered set,
where the first policy is used primarily, the second only being used
if there is a need to tie-break between bundles given the same
eviction priority by the primary policy, and so on. It is worth
noting that obviously nodes MUST NOT drop bundles for which it has
custody unless the lifetime expires.
3.3.2. Custody Policy
The concept of custody transfer can be found in [RFC4838]. In general
terms, the transmission of bundles with the Custody Transfer
Requested option involves moving bundles "closer" (in terms of some
routing metric) to their ultimate destination(s) with reliability.
The nodes receiving these bundles along the way (and agreeing to
accept the reliable delivery responsibility) are called "custodians".
The movement of a bundle (and its delivery responsibility) from one
node to another is called a "custody transfer".
Moreira, et al. Expires April 25, 2013 [Page 22]
Internet-Draft dLife October 22, 2012
The reliability requirement that a custodian accepts can be
instantiated in different ways: i) deleting the bundle after getting
a confirmation of a successful custody transfer, which may require
retransmissions over a reliable transport protocol, such as TCP. In
this case a bundle has normally one custodian in a moment in time;
ii) deleting the bundle only after getting an acknowledgment that the
bundle was delivered to the destination. In this case a bundle can
have more than one custodian, being the bundle replicated among
custodians over a non-reliable transport protocol, such as UDP.
dLife takes no responsibilities for making custody decisions. Such
decisions should be made by a higher layer. However, dLife insures
that custodian nodes do not drop bundles for which it has custody
unless the lifetime expires, or an acknowledge message is received
for that bundle.
3.3.3. Destination Policy
When a bundle reaches its destination, a Bundle ACK for that bundle
is issued. A Bundle ACK is a confirmation that a bundle has been
delivered to its destination, being that information stored in the
local bundle queue manageable by the routing agent. When nodes
exchange Social message TLVs, bundles that have been ACKed are also
listed. The node that receives this list updates its own list of
ACKed bundles to be the union of its previous list and the received
list. To prevent the list of ACKed bundles growing indefinitely, each
Bundle ACK should have a timeout that MUST NOT be longer than the
timeout of the bundle to which the ACK corresponds. When a node
receives a Bundle ACK for a bundle it is carrying, it MUST delete
that bundle from its queue, since the Bundle ACK indicates that a
bundle has been delivered to its destination.
Nodes MAY keep track of which nodes they have sent Bundle ACKs for
certain bundles to, and MAY in that case refrain from sending
multiple Bundle ACKs for the same bundle to the same node.
4. Message Formats
This section defines the message formats of the dLife routing
protocol. In order to allow for variable length fields, many numeric
fields are encoded as SDNVs, defined in [RFC5050], as in PRoPHET.
Since many of the fields are coded as SDNVs, the size and alignment
of fields indicated in many of the specification diagrams below are
indicative rather than prescriptive.
The basic message format shown in Figure 1 consists of a header (see
Section 4.1) followed by a sequence of one or more Type-Length-Value
components (TLVs) taken from the specifications in Section 4.2.
Moreira, et al. Expires April 25, 2013 [Page 23]
Internet-Draft dLife October 22, 2012
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ Header ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ TLV 1 ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| . |
~ . ~
| . |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ TLV n ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 1: Basic message format
4.1. Header
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Prot_Number |Version| Flags | Result | Code |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Sender | Receiver |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Message Identifier |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|S| SubMessage Number | Length (SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ Message Body ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 2: dLife Message Header
Prot_Number (Protocol Number)
The DTN Routing Protocol Number encoded as 8-bit unsigned
integer in network bit order. The value of this field is 0. The
dLife header is organized in this way so that dLife messages MAY
be sent as the Protocol Data Unit of an IP packet if an IP
protocol number was allocated for dLife. In its current version
Moreira, et al. Expires April 25, 2013 [Page 24]
Internet-Draft dLife October 22, 2012
dLife is only specified to use UDP transport for dLife messages
so that the protocol number serves only to identify the dLife
protocol within DTN. Transmitting dLife packets directly as an
IP protocol on a public IP network such as the Internet would
generally not work well because middle boxes such as firewalls
and NAT boxes would be unlikely to allow the protocol to pass
through and the protocol does not provide any congestion
control. However, it could be so used on opportunistic wireless
networks, which is the goal of dLife. The use of a light
transport protocol such as UDP, in opposition to TCP, ensures a
better exploitation of the presumable short contact
opportunities between peers in a DTN. Due to the lack of
reliability of UDP, dLife specify an acknowledgement procedure
to transmit meta-data.
Version
The Version of the dLife Protocol. Encoded as a 4-bit unsigned
integer in network bit order. This document defines version 1.
Flags
Reserved field of 4 bits.
Result
Since the exchange of dLife messages does not rely on the a
reliable link (e.g., based on TCP), as a default behavior, the
controller will acknowledge responses. Hence, dLife messages
implement the result field that in a response message can have
two values: "Success," and "Failure". The former indicates a
success response that may be contained in a single message or
the final message of a success response spanning multiple
messages.
The result field is encoded as a 8-bit unsigned integer in
network bit order with 7 unused and reserved bits, which were
included to allow future extension of the protocol . The
following values are currently defined:
o Success: Result = 1
o Failure: Result = 2
Code
This field gives further information concerning the result in a
response message. It is mostly used to pass an error code in a
failure response, but can also be used to give further
information in a success response message. In a request message,
the code field is not used and is set to zero.
If the Code field indicates that the ACK TLV is included in the
Moreira, et al. Expires April 25, 2013 [Page 25]
Internet-Draft dLife October 22, 2012
message, further information on the successful or failure of the
message will be found in the ACK TLV, which MUST be the first
TLV after the header.
The Code field is encoded as an 8-bit unsigned integer in
network bit order with 6 unused and reserved bits, which were
included to allow future extension of the protocol . The
following values are defined:
o Generic Response 0x00
o Submessage Received 0x01
o ACK TLV in message 0x02
The "generic response" and the "submessage receiver" values tell us
that the success or failure indicated in the Result field is related
to the all message or a submessage, respectively.
Sender
This field is the instance number for the link of the sender of
the dLife message. This instance number identifies a link
between peering nodes and lasts until the link goes down or when
the identity of the entity at the other end of the link changes.
It is randomly generated. This number is a 16-bit number that is
guaranteed to be unique within the recent past and to change
when the link or node comes back up after going down. Zero is
not a valid instance number. Messages sent after the Hello phase
should use the sender's instance number. The Sender Instance is
encoded as a 16-bit unsigned integer in network bit order.
Receiver
This field is the instance number for the link of the receiver
of the dLife message. If the sender of the message does not know
the current number of the receiver, this field MUST be set to
zero. Messages sent after the Hello procedure should use the
receiver's instance number. The receiver number is encoded as a
16-bit unsigned integer in network bit order.
Message Identifier
Used to associate a message with its response message. This
should be set in request messages to a value that is unique for
the sending host within the recent past. Response messages
contain the Message Identifier of the request they are
responding to. The Message Identifier is a 32 bit pattern.
S-flag
If S is set (value 1) then the SubMessage Number field indicates
the total number of SubMessage segments that compose the entire
message. If it is not set (value 0) then the SubMessage Number
Moreira, et al. Expires April 25, 2013 [Page 26]
Internet-Draft dLife October 22, 2012
field indicates the sequence number of this SubMessage segment
within the whole message. The S field will only be set in the
first sub-message of a sequence.
SubMessage Number
When a message is segmented because it exceeds the MTU of the
link layer or otherwise, each segment will include a SubMessage
Number to indicate its position. Alternatively, if it is the
first sub-message in a sequence of sub-messages, the S flag will
be set and this field will contain the total count of SubMessage
segments. The SubMessage Number is encoded as a 15-bit unsigned
integer in network bit order. The SubMessage number is
zerobased, i.e., for a message divided into n sub-messages, they
are numbered from 0 to (n - 1). For a message that it is not
divided into sub-messages the single message has the S-flag
cleared (0) and the SubMessage Number is set to 0 (zero).
Length
Length in octets of this message including headers and message
body. If the message is fragmented, this field contains the
length of this SubMessage. The Length is encoded as an SDNV.
Message Body
The Message Body consists of a sequence of one or more of the
TLVs specified in Section 4.2.
The protocol requires information about the link that the
underlying communication layer MUST provide. This information is
used in the Hello procedure. Since this information is available
from the underlying layer, there is no need to carry it in dLife
messages. The following values are defined to be provided by the
underlying layer:
Sender Local Address
An address used by the underlying communication layer that
identifies the sender address of the current message. This
address must be unique among the nodes that can currently
communicate.
Receiver Local Address
An address used by the underlying communication layer that
identifies the receiver address of the current message. This
address must be unique among the nodes that can currently
communicate.
4.2. TLV Structure
All TLVs have the following format, and can be nested.
Moreira, et al. Expires April 25, 2013 [Page 27]
Internet-Draft dLife October 22, 2012
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| TLV Type | TLV Flags | TLV Length (SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ TLV Data ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 3: TLV Format
Type
Specific TLVs are defined in Section 4.3. The TLV Type is
encoded as an 8-bit unsigned integer in network bit order.
TLV Flags
These are defined per TLV type. Any flags which are specified as
reserved in specific TLVs SHOULD be transmitted as 0 and ignored
on receipt.
TLV Length
Length of the TLV in octets, including the TLV header and any
nested TLVs. Encoded as an SDNV.
4.3. TLVs
This section describes the various TLVs that can be used in dLife
messages.
4.3.1. Hello TLV
The Hello TLV is used to set up and maintain a link between two dLife
nodes. Hello messages are the first TLVs exchanged between nodes when
they are within range of communication and are used to inform
neighbors about the EID and storage capacity of the node.
The Hello sequence must be completed so other TLVs can be exchanged.
Then, dLife nodes will store the information about each other
capacities and acknowledge such action, signaling that the
communication has been established. If during the Hello procedure, an
ACK is failed to be received, disconnection occurred and link should
be assumed broken.
Once a communication link is established between two dLife nodes, the
Hello TLV will be sent once for each interval with the SYN function
as defined in the interval timer. If a node experiences the lapse of
Moreira, et al. Expires April 25, 2013 [Page 28]
Internet-Draft dLife October 22, 2012
Hello intervals without receiving a Hello TLV on a connection in the
EXCHANGE state (cf. Section 5), the connection SHOULD be assumed
broken.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| TLV type=0x01 |Flags| TLV Length (SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|EIDLength(SDNV)| Sender EID (SDNV) | Timer (SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Storage (SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 4: Hello TLV Format
TLV Flags
The TLV Flags field contains a three bit Hello Function (HF)
number that specifies one of three functions for the Hello TLV.
The encoding of the Hello Function is:
o HEL: HF = 1
o SYN: HF = 2
o ACK: HF = 3
The HEL function is used by a node to send meta-data needed for the
dLife operation, namely the storage capacity of the node and its EID.
The SYN function is used to inform both devices that the
communication link is still up. The ACK function in used by a node to
acknowledge the reception of an HEL Hello TLV.
TLV Data
EID Length
The EID Length field is used to specify the length of the
Sender EID field in octets. If the EID has already been sent
at least once in a message with the current Sender Instance,
a node MAY choose to set this field to zero, omitting the
Sender EID from the Hello TLV. The EID Length is encoded as
an SDNV and the field is thus of variable length.
Sender EID
The Sender EID field specifies the EID of the sender that is
to be used in updating routing information and making
forwarding decisions. If a node has multiple EIDs, one
should be chosen for dLife routing. This field is of
variable length.
Moreira, et al. Expires April 25, 2013 [Page 29]
Internet-Draft dLife October 22, 2012
Timer
The Timer field is used to inform the receiver of the timer
value used in the Hello processing of the sender. The timer
specifies the nominal time between periodic Hello messages.
It is a constant for the duration of a session. The timer
field is specified in units of 100 ms and is encoded as an
SDNV.
Storage
This field indicated what is the node's storage capacity.
Used to inform the potential senders of the node's
limitations in terms of successful reception of bundles.
This field is encoded as an SDNV.
4.3.2. ACK TLV
This ACK TLV can be used by itself or nested in Hello TLV.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| TLV type=0x02 | Flags | TLV Length (SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ACK Data |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 5: ACK TLV Format
TLV Flags
The TLV Flags field carries an identifier for the ACK TLV type
as an 8-bit unsigned integer encoded in network bit order. A
range of values is available for private and experimental use in
addition to the values defined here. The following ACK TLV types
are defined:
o Break ACK 0x00
Used when a node wants to break the connection due to
the fact that the neighbor has a storage capacity lower
that its threshold to send bundles.
o Social ACK 0x01
Report on the reception of Social TLVs (SWNI, bundleList
and ackedBundleList).
o EID ACK (identifier/EID discrepancy) 0x02
Report on the identifier/EID discrepancy error as
mentioned in Section 3.2.1.
o EID ACK (unknown EID) 0x03
Report on the unknown EID error as mentioned in Section
3.2.1.
o Reserved 0x04 - 0x7F
Moreira, et al. Expires April 25, 2013 [Page 30]
Internet-Draft dLife October 22, 2012
o Private/Experimental Use 0x80 - 0xFF
TLV Data
The contents and interpretation of the TLV Data field are
specific to the type of ACK TLV. The ACK Type is defined as
follows:
EID ACK (identifier/EID discrepancy)
o String ID causing the discrepancy. o EID string that
differs the previous value.
EID ACK (unknown EID)
o String ID not found in the dictionary.
4.3.3. EID Dictionary TLV
The EID Dictionary TLV includes the list of EIDs used in making
routing decisions and is a shared resource (cf. Section 3.2.1) built
in each of the paired peers. The dictionary can be updated as more
EID Dictionary TLVs are received.
Moreira, et al. Expires April 25, 2013 [Page 31]
Internet-Draft dLife October 22, 2012
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| TLV type=0xA0 | Reserved | TLV Length (SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| String/EID Count (SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ~
~ Variable Length Routing Address Strings ~
~ ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ Routing Address String 1 ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| String ID 1 (SDNV) | Length (SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ Endpoint Identifier 1 (variable length) ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| . |
~ . ~
| . |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ Routing Address String n ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| String ID n (SDNV) | Length (SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ Endpoint Identifier n (variable length) ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 6: EID Dictionary TLV Format
Reserved
8 unused and reserved bits, which were included to allow future
extension of the protocol
String/EID Count
Number of strings corresponding to the nodes' EIDs the sender
node has encountered so far. Encoded as SDNV.
String ID n
SDNV identifier that is constant for the duration of a session.
String ID zero is predefined as the node initiating the session
through sending the Hello message, and String ID one is
predefined as the node responding with the Hello ACK message.
These entries do not need to be sent explicitly as the EIDs are
exchanged during the Hello procedure.
In order to ensure that the String IDs originated by the two
peers do not conflict, the String IDs generated in the node that
Moreira, et al. Expires April 25, 2013 [Page 32]
Internet-Draft dLife October 22, 2012
sent the Hello SYN message MUST have their least significant bit
set to 0 (i.e., are even numbers) and the String IDs generated
in the node that responded with the Hello ACK message must have
their least significant bit set to 1 (i.e., they are odd
numbers).
Length
Length of Endpoint Identifier in this entry. Encoded as SDNV.
Endpoint Identifier n
Text string representing the Endpoint Identifier. Note that it
is NOT null terminated as the entry contains the length of the
identifier.
4.3.4. Social TLV
This TLV provides the SWNI, bundleList and ackedBundleList
information, i.e., a list of the nodes that the neighbor node has
encountered up to that moment along with its social weight towards
them, the importance of the neighbor node, as well as the lists
containing bundles being carried by the peering nodes and
acknowledgements for already delivered bundles (limited to the latest
BUNDLE_DELIVERED number of bundles). This TLV allows dLife nodes to
choose the bundles to be sent according to the forwarding strategies
explained in Section 2.3.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| TLV type=0xA1 | Flags | TLV Length (SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Importance Value |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| SWNI String Count (SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| String ID 1 (SDNV) | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| SW value 1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ . ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| String ID n (SDNV) | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| SW value n |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Carried Bundle Count (SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Moreira, et al. Expires April 25, 2013 [Page 33]
Internet-Draft dLife October 22, 2012
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Carried Bundle ID 1 | Dest String ID 1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ . ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Carried Bundle ID n | Dest String ID n |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Acked Bundle Count (SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Acked Bundle ID 1 | Dest String ID 1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ . ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Acked Bundle ID n | Dest String ID n |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 7: Social message TLV Format
TLV Flags
The encoding of the Header flag field relates to the
capabilities of the Source node sending the Social message.
Flag 0: More Social TLVs
Flag 1 - 7: Reserved
The "More Social TLVs" flag is set to 1 if the Social
message requires more TLVs to be sent in order to be fully
transferred. This flag is set to 0 if this is the final TLV.
TLV Data
Importance
Importance of the node sending the Social message as a 32-
bit unsigned integer encoded in network bit order.
SWNI String Count
Number of entries regarding the SWNI information in the
TLV. Encoded as SDNV.
String ID
String ID of the endpoint identifier of the encountered
node for which this entry specifies the social weight as
predefined in a dictionary TLV. This field is of variable
length. This field is followed by 16 unused and reserved
bits, which were included to allow future extension of the
protocol
SW value
Social weight between peering node and that specific
encountered node n as a 32-bit unsigned integer encoded in
network bit order.
Moreira, et al. Expires April 25, 2013 [Page 34]
Internet-Draft dLife October 22, 2012
Carried Bundle Count
Number of entries regarding the carried bundle information
in the TLV. Encoded as SDNV.
Carried Bundle ID
Identifiers of the bundles that the sender is currently
carrying.
Acked Bundle Count
Number of entries regarding the acknowledged bundle
information in the TLV. Encoded as SDNV.
Acked Bundle ID
Identifiers of the bundles that the sender has received
acknowledgements for. This field is of variable length.
Dest String ID
String ID of the endpoint identifier of the destination
for a carried or acknowledged bundle. This field is of
variable length.
5. Detailed Operation
This section provides further details about the operation of dLife,
including state tables . As explained before dLife aims to release
any assumption about the reliability of the transport protocol, and
so positive acknowledgements would be necessary to signal successful
delivery of (sub)messages. In this section the phrase "send a
message" should be read as *successful* sending of a message,
signaled by receipt of the appropriate "Success" response. Hence the
state descriptions below do not explicitly mention positive
acknowledgements, whether they are being sent or not.
5.1. High Level State Tables
This section provides the high level state tables for the operation
of dLife. The next section provides a more detailed view of each part
of the protocol's operation. The following states are used to define
the dLife operation:
SENSING
This is the state all nodes start in. Nodes remain in this state
until a new contact opportunity arises. Once a node has sensed
the presence of a peer (through the Service Discovery Protocol
(SDP) implemented in the BCL in the current implementation as
mentioned in Section 7), it will trigger the Hello procedure by
switching to the HELLO state. Since multiple contacts may
happen, the node should also remain in the SENSING state in
Moreira, et al. Expires April 25, 2013 [Page 35]
Internet-Draft dLife October 22, 2012
order to detect new contact opportunities. This is handled by
creating a new thread or process during the transition to the
HELLO state, which then takes care of the communication with the
new peer while the parent process remains in state SENSING
waiting for additional peer to communicate with. In this case
when the neighbor is no longer available (described as
'disconnected' in the tables below), the thread or process
created is destroyed.
HELLO
Nodes remain in the HELLO state from when a new contact
opportunity arises until the Hello procedure is done and nodes
are connected (which happens when the Hello procedure reaches
the LINK_UP state as described in Section 5.3 - during this
procedure, the state LINK_UP and WAIT_HELLO_HEL are used, but
are not presented here since they are internal to the Hello
procedure). Once the Hello procedure is done, the node starts
the information exchange phase and transitions to the EXCHANGE
state. If while in the HELLO state the node is notified that the
neighbor is no longer in range, it returns to the SENSING state
and, if appropriate, MAY destroys any additional process or
thread created to handle the neighbor.
EXCHANGE
With the communication link set, nodes enter the EXCHANGE state
in which the transmission of dLife meta-data between peers is
done. The node remains in this state as long as Information
Exchange Phase TLVs (EID Dictionary, Social, ACK, Hello) are
being sent and received. If the node is notified that the
neighbor is no longer in range (through the Service Discovery
Protocol (SDP) implemented in the BCL (cf. Section 7) before
all information have been exchanged, the node returns to the
SENSING state to await new neighbors.
In the EXCHANGE state both nodes are able to exchange their EID
dictionaries and SWNI information. With dLife the exchange of
information about dictionary, social weight and node importance
MAY be carried out independently but concurrently with the
messages multiplexed on a single bidirectional link, or
alternatively, the exchanges MAY be carried out partially or
wholly sequentially if appropriate for the implementation. The
information exchange process is explained in more detail in
Section 3.2.
When a Social TLV is received the node MUST notify the Bundle
Agent about the bundles that SHOULD be forwarded to the peer
node. If the "More Social TLV" flag is set to zero (i.e., no
more bundles to send), the node restarts the exchange timer.
Moreira, et al. Expires April 25, 2013 [Page 36]
Internet-Draft dLife October 22, 2012
When this timer expires, the node checks if the neighbor is
still connected by sending a Hello message with the SYN flag.
Otherwise (i.e., disconnection), the node switches to the
SENSING state and, if appropriate, MAY destroy any additional
process or thread created to handle the neighbor.
If the neighbor is still connected after the exchange timer
expires, the next information exchange phase MAY have the effect
of further increasing the probability of selecting this node as
a forwarder (based on the TECD and TECDi update). If there is
more than one neighbor connected or other communication
opportunities have happened since the previous information
exchange occurred, then the SWNI information changes resulting
from these other encounters SHALL be passed to the connected
peer after upon the end of new daily sample. The exchange timer
is restarted once the information exchange has completed again.
If one or more new bundles are received by this node while
waiting for the exchange timer to expire and the TECD and TECDi
metrics indicate that it would be appropriate to forward some or
all of the bundles to the connected node, the bundles SHOULD be
immediately transferred to the connected neighbor.
State: SENSING
+======================================================================+
| Condition | Action | New State |
+==============+=========================================+=============+
| | Start Hello procedure for new contact | HELLO |
+ New Contact +-----------------------------------------+-------------+
| | Keep sensing for more contacts | SENSING |
+======================================================================+
State: HELLO
+======================================================================+
| Condition | Action | New State |
+======================+===================================+===========+
| Hello TLV rcvd | | HELLO |
+----------------------+-----------------------------------+-----------+
| Hello procedure done | Start Information Exchange Phase | EXCHANGE |
+----------------------+-----------------------------------+-----------+
| Disconnected | | SENSING |
+======================================================================+
Moreira, et al. Expires April 25, 2013 [Page 37]
Internet-Draft dLife October 22, 2012
State: EXCHANGE
+===================================================================+
| Condition | Action | New State |
+===================+===================================+===========+
| On entry | Start exchange timer | EXCHANGE |
| | Use Hello Timer interval | |
+-------------------+-----------------------------------+-----------+
| Disconnected | | SENSING |
+-------------------+-----------------------------------+-----------+
| EID Dict TLV rcvd | Update local EID Dictionary | EXCHANGE |
+-------------------+-----------------------------------+-----------+
| Social TLV rcvd | Inform Bundle Agent | EXCHANGE |
+-------------------+-----------------------------------+-----------+
| More Social TLV | Restart exchange timer | EXCHANGE |
| flag = 0 | | |
+-------------------+-----------------------------------+-----------+
| Exchange timer | Send Hello with SYN flag | EXCHANGE |
| expires | | |
+-------------------+-----------------------------------+-----------+
| New bundle | | EXCHANGE |
+===================================================================+
5.2. High Level Meta-Data Table
During its operation, dLife makes use of metadata locally stored as a
consequence of the the exchange of Social TLVs, Hello TLVs and local
operations. The stored meta-data is used in the computation of social
weight towards other nodes and its own importance as well as to
identify itself (cf. Section 2.2). Metadata can be persistent or
temporary: the former MUST be kept for longer times and the latter is
replaced as a new daily sample starts.
Persistent metadata includes the node's own EID, storage capacity
(StoCap), importance (Imp), EID Dictionary , Average Duration
(AD_peer) of contacts to peers, and social weight to peer (w_peer).
Since nodes receive information from neighbors, they must also store
the peer's EID (EID_peer), peer's storage capacity (StoCap_peer), the
social weight list of that peer towards other nodes (SocList_peer),
and the importance of that peer (Imp_peer). Additionally, nodes must
keep track of number of times the bundles were forwarded (fwd_times)
as to employ the queueing FLNT policy describe in section 3.3.1.
The temporary metadata includes contact duration (CD_peer) and total
Moreira, et al. Expires April 25, 2013 [Page 38]
Internet-Draft dLife October 22, 2012
contact time (TCT_peer) for a given peer. This two variables are
needed since two nodes can be in contact more than once in the same
daily sample, being CD used to count the duration of the active
contact, and TCT used to add the time of all contacts in the same
daily sample.
In the SENSING state, each node MUST have its own EID and storage
capacity ready for exchange in the case of a contact. When a contact
is sensed, a node creates an entry for this potential peer (EID_peer)
in meta-data table and start counting the duration of this contact
(CD_peer). Note that the peer EID will only be known in the HELLO
state.
If the HELLO state is successfully concluded, the EID_peer is now
known and new entries for the encountered peer are created (TCT_peer,
AD_peer, w_peer, and StoCap_peer) in the meta-data table.
When the EXCHANGE state starts, a node will receive from its peer its
EID Dictionary, SocList_peer and Imp_peer, which must be stored for
later deciding in bundle forwarding.
+------------------------+----------------+
| EID_own | StoCap | Imp | EID Dictionary |
+------------------------+----------------+
|
+----------+---------+----------+---------+--------+
| EID_peer | CD_peer | TCT_peer | AD_peer | w_peer |
+----------+---------+----------+---------+--------+
| | |
| +-----+-----+-----+ +------+------+------+
| | CD1 | ... | CDn | | AD11 | ... | AD1i |
| +-----+-----+-----+ +------+------+------+
|
+-------------+--------------+----------+-----------+
| StoCap_peer | SocList_peer | Imp_peer | fwd_times |
+-------------+--------------+----------+-----------+
Figure 8: Meta-data Information
This meta-data varies in size according to the type of information it
stores:
o EID and EID_peer are coded as strings of variable size.
o StoCap, Stop_peer, Imp, Imp_peer and w_peer are coded as floats
(32 bits).
o CD_peer, TCT_peer and AD_peer are coded as long (64 bits).
o Fwd_times are coded as int (32 bits).
o EID Dictionary is coded as a HashMap tuple with String ID
Moreira, et al. Expires April 25, 2013 [Page 39]
Internet-Draft dLife October 22, 2012
encoded as SDNV (16 bits) and its equivalent EID of variable
length (up to 32 bits).
5.3 Hello Procedure
The hello procedure consists of the exchange of messages comprising
the header TLV and a single Hello TLV (see Section 4.3.1) with the HF
(Hello Function) field set to the specified value (HEL, SYN or ACK).
The rules and state tables for this procedure are shown below with
the main states and actions to be taken upon the receipt of the
required information:
o A timer is required for the periodic generation of Hello SYN and
ACK messages. The value for this timer is obtained from the timer
field in the Hello message.
o The link between peers is only considered available when the
LINK_UP state is reached.
o No more than one Hello message with the SYN flag SHOULD be sent
within the time period specified in the Hello message with the HEL
flag.
o Hello messages MAY be exchanged concurrently, but also in a
sequential manner, depending on the nature of the communication
medium (full- or half-duplex). In the case of the latter, the
process MUST be completed in one direction prior to initiating in
the other one.
Upon a contact, nodes exchange a Hello HEL message. At this point
nodes will have information about each other's EID and storage
capacity. Additionally, a timer value is exchanged so nodes know the
periodicity of next hello messages in order to signal the arrival of
the Hello HEL message and to keep the link active.
At this moment, nodes MUST start counting the duration of contact
between them. This also implies creating entries for the peer
(EID_peer) where the contact duration (CD_peer), total connected time
(TCT_peer), average duration (AD_peer), social weight (w_peer),
storage capacity (StoCap_peer), social weight list (SocList_peer),
and the importance (Imp_peer) towards this specific peer are going to
be maintained and updated. Additionally, a timer for receiving the
Hello ACK message MUST be started. Up to this point, nodes are in the
WAIT_HELLO_HEL state.
A second hello message with the ACK flag MUST be issued to inform
nodes of the successful receipt of the Hello HEL message. If Hello
Moreira, et al. Expires April 25, 2013 [Page 40]
Internet-Draft dLife October 22, 2012
ACK message does not arrive within the specified time (Hello ACK
timeout), the link is assumed lost, nodes are disconnected, contact
duration count MUST stop and variables SHOULD be saved. After this,
the start of a new hello procedure is required and the nodes remain
at the WAIT_HELLO_HEL state.
The link is assumed active upon the receipt of the Hello ACK message.
This means nodes are connected and ready to shift to the exchange
information phase. At this point values should be saved in created
entries and nodes move to the LINK_UP state.
The Hello SYN message is exchanged in order to keep track of the
activity in the link, and as long as this message is being received
the nodes will remain at the LINK_UP state. If the Hello SYN message
is not received within the specified time (Hello SYN timeout), the
link is assumed lost and nodes are disconnected. At this point nodes
MUST stop the contact duration count with the value being saved to
CD_peer (CD1 ... CDn) variables of each disconnected peer.
State: WAIT_HELLO_HEL
+====================================================================+
| Condition | Action | New State |
+===============+===================================+================+
| | Start contact duration count | |
+ +-----------------------------------+ +
| Hello HEL | Start timer for Hello ACK receipt | WAIT_HELLO_HEL |
+ rcvd +-----------------------------------+ +
| | Initialize variables | |
+---------------+-----------------------------------+----------------+
| Hello ACK rcvd| Save variables | LINK_UP |
+---------------+-----------------------------------+----------------+
| Hello ACK | Stop contact duration count | WAIT_HELLO_HEL |
+ timeout +-----------------------------------+ +
| | Save variables | |
+===============+===================================+================+
Moreira, et al. Expires April 25, 2013 [Page 41]
Internet-Draft dLife October 22, 2012
State: LINK_UP
+===========================================================================+
| Condition | Action | New State |
+======================+===================================+================+
| Hello SYN timeout | Stop contact duration count | WAIT_HELLO_HEL |
+ +-----------------------------------+ +
| | Save variables | |
+----------------------+-----------------------------------+----------------+
| Hello SYN rcvd | | LINK_UP |
+======================+===================================+================+
5.4 Information Exchange Phase
After the exchange of hello messages, the nodes are in the LINK_UP
state which will allow the exchange of information. dLife is
bidirectional and the information exchange processes between a pair
of nodes (from A to B and vice-versa) are independent and expected to
run almost entirely concurrently. This is because EID Dictionaries
MUST be synchronized to allow better performance of the protocol.
The information exchange phase consists of messages comprising the
dLife header and EID Dictionary and Social TLVs (see Sections 4.3.3
and 4.3.4). The rules and state tables are shown below with the main
states and actions to be taken upon the receipt of the required
information.
o No information SHALL be exchanged prior to the hello procedure.
o An exchange timer MUST be set to keep track whether the link is
still active for information exchange.
o Information messages MAY be exchanged concurrently, but also in
a sequential manner, depending on the nature of the communication
medium (full- or half-duplex). In the case of the latter, the
process MUST be completed in one direction prior to initiating in
the other one.
Once in the information exchange phase, as soon as nodes enter the
WAIT_INFO state and they MUST set an information exchange timer and
send the EID Dictionary in order to synchronize the mapping between
their identifiers (String ID) and EIDs of nodes they have
encountered. As the EID dictionary is received, the node will shift
to the BUILD_SOCIAL_TLV state whether or not problems with the
Moreira, et al. Expires April 25, 2013 [Page 42]
Internet-Draft dLife October 22, 2012
mapping are detected. In the case of EID errors, an ACK TLV with EID
ACK flag MUST be sent to inform the peer node about problems (cf.
Sections 3.2.1 and 4.3.2) with the received identifiers (String ID).
Still in the WAIT_INFO state, if a node gets a Social TLV, it will
obtain the SWNI, bundleList and ackedBundleList information from its
peer node. With such information, the node will decide which bundles
SHOULD be exchanged based on the forwarding strategies (cf. Section
2.3) and will inform the Bundle Agent about the list of bundles that
SHOULD be forwarded to its peering node.
The node will remain in the WAIT_INFO state after receiving an ACK
TLV with the Bundle ACK flag, which means that the bundles forwarded
by the Bundle Agent arrived at the peer node, and the sending node
can wait until new bundles are ready to be sent; and also when
receiving an ACK TLV with the Break ACK flag, which signals that the
peering node decided to disconnect given its lack of storage
capacity, and the sending node will wait for information coming from
other peers.
As soon as entering the BUILD_SOCIAL_TLV state, the node MUST build
and send its Social TLV to the peering node and will remain in this
state until it receives an ACK TLV with the Social ACK flag. The node
will shift to the WAIT_INFO state upon the receipt of the Social ACK.
Since dLife updates SWNI information at every daily sample, this can
influence in the next forwarding decisions. Thus, the node should
report such updates to its peering node and shift to the
BUILD_SOCIAL_TLV state.
State: WAIT_INFO
+==============================================================================+
| Condition | Action | New State |
+======================+===================================+===================+
| On entry | Send EID Dictionary TLV | WAIT_INFO |
+ +-----------------------------------+ +
| | Set exchange timer | |
+----------------------+-----------------------------------+-------------------+
| EID Dictionary rcvd | Check identifier/EID mapping | BUILD_SOCIAL_TLV |
+----------------------+-----------------------------------+-------------------+
| EID error | Report problem | BUILD_SOCIAL_TLV |
| | ACK TLV flag EID ACK | |
+----------------------+-----------------------------------+-------------------+
| | Get SWNI, bundleList | |
| Social TLV rcvd | and ackedBundleList information | WAIT_INFO |
+ +-----------------------------------+ +
| | Inform Bundle Agent | |
Moreira, et al. Expires April 25, 2013 [Page 43]
Internet-Draft dLife October 22, 2012
+----------------------+-----------------------------------+-------------------+
| Bundle ACK rcvd | Wait for new bundles | WAIT_INFO |
+----------------------+-----------------------------------+-------------------+
| Break ACK rcvd | Disconnect | WAIT_INFO |
+----------------------+-----------------------------------+-------------------+
| SWNI updated | Report peer | BUILD_SOCIAL_TLV |
+======================+===================================+===================+
State: BUILD_SOCIAL_TLV
+==============================================================================+
| Condition | Action | New State |
+======================+===================================+===================+
| On entry | Build and send Social TLV | BUILD_SOCIAL_TLV |
+----------------------+-----------------------------------+-------------------+
| Social ACK rcvd | | WAIT_INFO |
+======================+===================================+===================+
6. Security Considerations
Currently, dLife does not specify any special security measures.
However, as a routing protocol for opportunistic networks, dLife may
be a target for various attacks. Such attacks may not be problematic
if all nodes in the network can be trusted and are working towards a
common goal. If there is such a set of nodes, but there are also
malicious nodes, consequent security problems can be solved by
introducing an authentication mechanism when two nodes meet, for
example using a Pretty Good Privacy (PGP) system. Thus, only nodes
that are known to be members of the trusted group of nodes are
allowed to participate in the dLife routing. This of course
introduces the additional problem of key distribution, which is out-
of-scope of this document.
Examples of possible vulnerabilities are:
Black Hole Attack
A malicious node sets its social weights for all
Moreira, et al. Expires April 25, 2013 [Page 44]
Internet-Draft dLife October 22, 2012
destinations to a very high value. This has two effects,
both causing messages to be drawn towards the black hole,
instead of to its correct destination: i) depending on
queueing policy, this might lead to premature dropping of
the bundle; ii) the social weights reported by the malicious
node will affect the computation of the node importance.
This could place the malicious use as the center of any
communication.
In this case, a node should raise alert if the social
weights and node importance that it receives from a new
neighbor is much higher than the cumulative moving average
of the information received from all previous nodes. This
situation can be handle by implementing a trustworthy
authentication mechanism for pervasive computing, allowing a
node to get extra confidence that a neighbor will handle
social weights and node importance in a trustworthy manner.
Identity Spoofing
With identity spoofing, a malicious node claims to be
someone else. This could be used to "steal" the data that
should be going to a particular node. This will cause these
bundles to be removed from the network, reducing the chance
that they will reach their real destination.
This can be prevented by using authentication between
pervasive nodes.
Bundle Store Overflow
After encountering and receiving the social weights and node
importance information from the victim, a malicious node may
generate a large number of fake bundles to the destination
for which the victim has the social weights. This will cause
the victim to fill up its bundle storage, possibly at the
expense of other, legitimate, bundles. This problem is
transient as the messages will be removed when the victim
meets the destination and delivers the messages.
This attack can be prevented by requiring sending nodes to
sign all bundles they originate. This will allow
intermediate nodes to verify the integrity of the messages
before accepting them.
There are some typical vulnerabilities that are not
potential problems with dLife such as:
Fake ACKS
In this typical situation a malicious node may issue fake
Moreira, et al. Expires April 25, 2013 [Page 45]
Internet-Draft dLife October 22, 2012
ACKs for all bundles (or only bundles for a certain
destination if the attack is targeted at a single node)
carried by nodes it meets. The affected bundles will be
deleted from the network, greatly reducing their probability
of being delivered to the destination.
This situation does not occur with dLife since a node can
only send an ACK to bundles that the current carrier decided
to forward to it (based on local forwarding policies) and
not for bundles that the potential malicious node asked to
be forwarded.
7. Implementation Experience
The initial implementation of dLife is written in Java for the
version 1.4.1 of the Opportunistic Network Emulator (ONE), named
Dlife.java [Moreira12d], which implements the RoutingDecisionEngine
interface to be used with the DecisionEngineRouter class. The
implementation contains all the major mechanisms described in this
document to ensure proper protocol operation. There are however some
parts that are only specified, such as the queuing policies, and
other that still need specification, such as the security
considerations. The implementation considered nodes with limited
storage resources (2 MB) and restricted communication: WiFi and
Bluetooth.By running on ONE, the goal of this first implementation
wast to enable dLife to be tested in different scalable large
pervasive scenarios (some based on real traces such as the one from
Cambridge University) with other protocols: PRoPHET and Bubble Rap.
The three key performance indicators that were studied were average
message delay, probability of message delivery and protocol cost
(number of duplicate messages in the network at the time of
delivery). Experience and feedback from the implementers on early
versions of the protocol have been incorporated into the current
version.
A second implementation of dLife was done in Java using the Android
API development. The class responsible for routing is known as
dLifeRouter.java, responsible for making routing decisions based on
information from other components, such as Social Information
Gatherer (GIS), Social Weighter (SW), Importance Assigner (IA),
Social Information Repository (SIR), and Decision Maker (DM),
abstracted as methods and data structures. The goal was to construct
a modular design, since its inception, for operation over multiple
platforms. So far this implementation comprises Android devices.
Additionally, other classes have been implemented to provide nodes
with DTN core functionality, direct wireless communication, generic
Moreira, et al. Expires April 25, 2013 [Page 46]
Internet-Draft dLife October 22, 2012
routing capabilities, and secure communications. To implement the
core of the DTN architecture, a Bundle class was implemented as in
RFC 5050, based on the DTN2, IBR-DTN and Bytewalla frameworks for
Linux and Android devices. To allow direct wireless communication a
common communication medium, Bluetooth Convergence Layer (BCL), was
created and implemented allowing direct exchange of bundles through
the Bluetooth interface without the need of a structured WiFi
network. Generic routing functionalities are provided by the
implementation of a generic routing class, GenericRouting, that can
be extended to represent a specific protocol. Secure communications
are supported by the implementation of a security layer,
BundleSecurity, implemented according to RFC 6257 Bundle security
Protocol Specification.
Regarding the new BCL, which is not present in the current DTN
available architectures, it was implemented as general as possible to
allow the interfacing between the Bundle Agent and the communication
medium regardless of the used routing protocol and operational system
running on the the devices. However, the current implementation was
first developed for Android devices and thus the BCL takes advantages
of some native Bluetooth functionality already implemented in this
platform, such as the discovery of neighbors and the possibility of
storing information about them. The implemented BCL
(BluetoothConvergenceLayer.java) includes the Service Discovery
Protocol (SDP) for sensing the medium and the Serial Port Profile
(SPP) for data exchange. It has the RFCOMM as transport protocol and
run on top on the Logical link control and adaptation protocol
(L2CAP) which interfaces with the Host Controller Interface (HCI).
Additionally, the BCL provides a simple reliable data stream and
supports multiple connections as this is expected to happen in the
real world. Hence, in the current dLife implementation, messages are
not transported based on UDP, mas mentioned in Section 4.1, but via
an interface with the RFCOMM and L2CAP protocol.
The goal of having two implementations of dLife (for the ONE
simulator and for the Android platform) is to compare the real-world
behavior of dLife implemented in real-world devices running a DTN
implementation regarding the same performance metrics used in the
simulation settings in ONE. The envisioned scenario refers to a
collection of mobile wireless nodes carried by people who move
throughout their daily routines.
For further details regarding the DTN platform implementation are
under way, which describes the DTN2, IBR-DTN and Bytewalla
implementations, together with the extra classes that were
implemented to provide nodes with DTN core functionality, direct
wireless communication, generic routing capabilities, and secure
communications, as well as details on the implementation of BCL and
Moreira, et al. Expires April 25, 2013 [Page 47]
Internet-Draft dLife October 22, 2012
the social-aware opportunistic routing protocol, dLife.
8. Deployment Experience
Since the beginning of 2012, a DTN test-bed is being created in the
Amazon region for testing of DTN routing solutions, in the context of
the DTN-Amazon project, having the University Lusofona and University
Federal of Para as current partners. The test-bed has currently 10
devices (3 personal computers with Ubuntu 10.10 Maverick, 3
smartphones Android 2.3.6 Gingerbread, 4 wireless routers with
OpenWrt 10.03.1) and will grow until 16 devices (5 WiFi tablets, 5
smartphones, 2 personal computers and 4 wireless routers).
The test-bed was initially used to test two different DTN
implementations: IBR-DTN, organized in a modular form, with a focus
on embedded systems for easy portability; DTN2, incorporating all
components of the DTN architecture, divided into modules such as
Convergence Layers Persistent Store, Bundle Router and more.
Communication between the modules is based on IPC mechanism (Inter
Process Communication). DTN2 also has some concern with the issue of
multi-platform, although its organization is not as modular.
The two DTN implementations were tested with two applications that
were able to communicate based on two different routing protocols via
WiFi interfaces configured in infrastructured mode: i) whisper chat
application over PRoPHET (IBR-DTN test-bed); and the DTN-AMAZON
Android security application for surveillance of university campus
over Epidemic and PRoPHET routing (DTN2).
The DTN2 implementation was also used to analyze the behavior of a
network environment with mobility, while the mules were carried by a
vehicle to enable the exchange of information between two hosts,
information that was also accessed by an application on a Smartphone
at one of sides. There were also attempts to deliver the message at a
speed of 60 km/h, the limit considered by the scientific community so
that the communication Wi-Fi still works.
Bytewalla was also deployed to allow the understanding of its
functionalities. For this, version 3 (version 5 was not yet fully
functional with sporadic crashes) was installed in the Android
devices with communication happening through a wireless router among
such devices. It is important to mention that the bundle would only
be sent from one device to another, if both were connected to the
same router. At this moment, the wireless router could not interpret
bundles, being only used to relay information.
Then, IBR-DTN was loaded into a wireless router to check whether the
Moreira, et al. Expires April 25, 2013 [Page 48]
Internet-Draft dLife October 22, 2012
bundle would only be sent to the router if the second device were
also connected. The same behavior was detected showing no
interoperability whatsoever between the different implementations.
At the moment the DTN module is fully functional on Android 2.3.6
Gingerbread (kernel version 2.6.35.7) devices which are able to
exchange information through their Bluetooth interfaces and based on
the dLife implementation. For a proof of concept and basic
operations, initial tests of the dLife implementation are being
carried out in a controlled test-bed with Android devices using a
text messaging application for operation testing, where each node
sent messages alternating destinations. These tests aim to analyze
the performance of the dLife, when compared to behavior of other
social-oblivious opportunistic routing solutions such as Epidemic and
PROPHET, based on the following metrics: average message delay,
probability of message delivery and the number of duplicate messages
in the network at the time of delivery.
In a later phase, the DTN module with routing functionality will be
made available for download, allowing its deployment in personal
devices. In terms operating systems, the intention is to later extend
the module to Linux nodes and wireless routers.
9. References
9.1 Normative References
[Moreira12a] Moreira, W., Mendes, P., and Sargento, S.,
"Opportunistic Routing Based on Daily Routines," in
Proceedings of the Sixth IEEE WoWMoM Workshop on Autonomic
and Opportunistic Communications (AOC 2012), (San
Francisco, California, USA), June, 2012.
[Moreira12b] Moreira, W., Souza, M., Mendes, P., and Sargento, S.,
"Study on the Effect of Network Dynamics on Opportunistic
Routing" in Proceedings of the Eleventh International
Conference on Ad-Hoc Networks and Wireless (AdHoc Now
2012), (Belgrade, Serbia), July, 2012.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC4838] Cerf, V., Burleigh, S., Hooke, A., Torgerson, L., Durst,
R., Scott, K., Fall, K., and H. Weiss, "Delay-Tolerant
Networking Architecture", RFC 4838, April 2007.
[RFC5050] Scott, K. and S. Burleigh, "Bundle Protocol Specification",
RFC 5050, November 2007.
Moreira, et al. Expires April 25, 2013 [Page 49]
Internet-Draft dLife October 22, 2012
9.2 Informative References
[Chaintreau06] A. Chaintreau, P. Hui, J. Crowcroft, C. Diot, R. Gass,
and J. Scott, "Impact of human mobility on the design of
opportunistic forwarding algorithms," in Proceedings of
INFOCOM, (Barcelona, Spain), April, 2006.
[Costa08] P. Costa, C. Mascolo, M. Musolesi, and G. P. Picco,
"Socially-aware routing for publish-subscribe in delay-
tolerant mobile ad hoc networks," Selected Areas in
Communications, IEEE Journal on, vol. 26, pp. 748- 760,
June, 2008.
[Daly07] E. M. Daly and M. Haahr, "Social network analysis for
routing in disconnected delay-tolerant manets," in
Proceedings of ACM MobiHoc, (Montreal, Canada), September,
2007.
[Eagle09] N. Eagle and A. Pentland, "Eigenbehaviors: identifying
structure in routine," Behavioral Ecology and
Sociobiology, vol. 63, pp. 1057-1066, May, 2009.
[Hossmann10] T. Hossmann, T. Spyropoulos, and F. Legendre, "Know thy
neighbor: Towards optimal mapping of contacts to social
graphs for dtn routing," in Proceedings of IEEE INFOCOM,
(San Diego, USA), March, 2010.
[Hui07] P. Hui and J. Crowcroft, "How small labels create big
improvements," in Proceedings of IEEE PERCOM Workshops,
(White Plains, USA), March, 2007.
[Hui11] P. Hui, J. Crowcroft, and E. Yoneki, "Bubble rap: social-
based forward- ing in delay tolerant networks," Mobile
Computing, IEEE Transactions on, vol. 10, pp. 1576-1589,
November, 2011.
[I-D.irtf-dtnrg-tcp-clayer] Demmer, M. and J. Ott, "Delay Tolerant
Networking TCP Convergence Layer Protocol", draft-irtf-
dtnrg-tcp-clayer-02 (work in progress), November 2008.
[I-D.irtf-dtnrg-udp-clayer] H. Kruse, S. Ostermann, "UDP Convergence
Layers for the DTN Bundle and LTP Protocols", draft-irtf-
dtnrg-udp-clayer-00 (work in progress), November 2008.
[Lindgren04] A. Lindgren, A. Doria, and O. Schelen, "Probabilistic
routing in intermittently connected networks," in Service
Assurance with Partial and Intermittent Resources, vol.
3126 of Lecture Notes in Computer Science, pp. 239--254,
Moreira, et al. Expires April 25, 2013 [Page 50]
Internet-Draft dLife October 22, 2012
Springer Berlin / Heidelberg, 2004.
[Lindgren06] Lindgren, A. and K. Phanse, "Evaluation of Queueing
Policies and Forwarding Strategies for Routing in
Intermittently Connected Networks", Proceedings of
COMSWARE 2006 , January 2006.
[Moreira11] W. Moreira and P. Mendes, "Survey on Opportunistic
Routing for Delay/Disruption Tolerant Networks ," Tech.
Rep. SITI-TR-11-02, SITI, University Lusofona, February
2011.
[Moreira_12c] Waldir Moreira, Paulo Mendes, Susana Sargento,
"Assessment Model for Opportunistic Routing", IEEE Latin
America Transactions, Vol 10 Issue 3 April 2012
[Mtibaa10] A. Mtibaa, M. May, M. Ammar, and C. Diot, "Peoplerank:
Combining social and contact information for opportunistic
forwarding," in Proceedings of INFOCOM, (San Diego, USA),
March, 2010.
[Nelson09] S. Nelson, M. Bakht, and R. Kravets, "Encounter-based
routing in DTNs," in Proceedings of INFOCOM, (Rio de
Janeiro, Brazil), April, 2009.
[RFC6257] Symington, S., Farrell, S., Weiss, H., and P. Lovell,
"Bundle Security Protocol Specification", RFC 6257, May
2011.
[Song07] L. Song and D. F. Kotz, "Evaluating opportunistic routing
protocols with large realistic contact traces," in
Proceedings of ACM MobiCom CHANTS, (Montreal, Canada),
September, 2007.
[Vahdat00] Vahdat, A. and D. Becker, "Epidemic Routing for Partially
Connected Ad Hoc Networks", Duke University Technical
Report CS-200006, April 2000..in 3
Authors' Addresses
Waldir Moreira
SITI, Universidade Lusofona
Campo Grande, 376, Ed. U
1749-024 Lisboa
Portugal
Phone:
Email: waldir.junior@ulusofona.pt
Moreira, et al. Expires April 25, 2013 [Page 51]
Internet-Draft dLife October 22, 2012
URI: http://siti2.ulusofona.pt/~wjunior
Paulo Mendes
SITI, Universidade Lusofona
Campo Grande, 376, Ed. U
1749-024 Lisboa
Portugal
Phone:
Email: paulo.mendes@ulusofona.pt
URI: http://siti2.ulusofona.pt/~pmendes
Ronedo Ferreira
ITEC, Universidade Federal do Para
Rua Augusto Correa, 01, Guama
66075-110 Belem-PA
Brasil
Phone:
Email: ronedo@aitinet.com
URI:
Eduardo Cerqueira
ITEC, Universidade Federal do Para
Rua Augusto Correa, 01, Guama
66075-110 Belem-PA
Brasil
Phone:
Email: cerqueira@ufpa.br
URI: http://www.gercom.ufpa.br/eduardo/
Moreira, et al. Expires April 25, 2013 [Page 52]