Skip to main content

Opportunistic Routing based on Users Daily Life Routine
draft-moreira-dlife-00

The information below is for an old version of the document.
Document Type
This is an older version of an Internet-Draft whose latest revision state is "Expired".
Authors Waldir Moreira, Paulo Mendes , Ronedo Ferreira, Eduardo Cerqueira
Last updated 2012-07-07
RFC stream (None)
Formats
Additional resources
Stream Stream state (No stream defined)
Consensus boilerplate Unknown
RFC Editor Note (None)
IESG IESG state I-D Exists
Telechat date (None)
Responsible AD (None)
Send notices to (None)
draft-moreira-dlife-00
DTN Research Group                                            W. Moreira
Internet-Draft                                                 P. Mendes
Expires: January 8, 2013                     SITI, Universidade Lusofona
                                                             R. Ferreira
                                                            E. Cerqueira
                                      ITEC, Universidade Federal do Para
                                                            July 7, 2012

        Opportunistic Routing based on Users Daily Life Routine
                         draft-moreira-dlife-00

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 January 8, 2013                 [Page 1]
Internet-Draft                   dLife                      July 7, 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 MONTH DAY, 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 January 8, 2013                 [Page 2]
Internet-Draft                   dLife                      July 7, 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. Operation in the presence of multiples neighbors  . . . 20
     3.3. Bundle Reception Policies . . . . . . . . . . . . . . . . . 20
       3.3.1. Queueing policy . . . . . . . . . . . . . . . . . . . . 20
       3.3.2. Custody Policy  . . . . . . . . . . . . . . . . . . . . 21
       3.3.3. Destination Policy  . . . . . . . . . . . . . . . . . . 22
   4. Message Formats . . . . . . . . . . . . . . . . . . . . . . . . 22
     4.1. Header  . . . . . . . . . . . . . . . . . . . . . . . . . . 23
     4.2. TLV Structure . . . . . . . . . . . . . . . . . . . . . . . 26
     4.3. TLVs  . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
       4.3.1. Hello TLV . . . . . . . . . . . . . . . . . . . . . . . 27
       4.3.2. ACK TLV . . . . . . . . . . . . . . . . . . . . . . . . 29
       4.3.3. Social TLV  . . . . . . . . . . . . . . . . . . . . . . 30
   5. Detailed Operation  . . . . . . . . . . . . . . . . . . . . . . 32
     5.1. High Level State Tables . . . . . . . . . . . . . . . . . . 32
     5.2. High Level Meta-Data Table  . . . . . . . . . . . . . . . . 35
   6. Security Considerations . . . . . . . . . . . . . . . . . . . . 36
   7. Implementation Experience . . . . . . . . . . . . . . . . . . . 38
   8. Deployment Experience . . . . . . . . . . . . . . . . . . . . . 38
   9.  References . . . . . . . . . . . . . . . . . . . . . . . . . . 39
     9.1  Normative References  . . . . . . . . . . . . . . . . . . . 39
     9.2  Informative References  . . . . . . . . . . . . . . . . . . 40
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 40

 

Moreira, et al.         Expires January 8, 2013                 [Page 3]
Internet-Draft                   dLife                      July 7, 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 January 8, 2013                 [Page 4]
Internet-Draft                   dLife                      July 7, 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 January 8, 2013                 [Page 5]
Internet-Draft                   dLife                      July 7, 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 in
   order not to restrict 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.

   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
   bring a coherent understanding about the advantages and challenges of
   using a DTN system in the daily life of millions of people. A study
 

Moreira, et al.         Expires January 8, 2013                 [Page 6]
Internet-Draft                   dLife                      July 7, 2012

   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.

   From a networking model perspective, a DTN is a network of self-
 

Moreira, et al.         Expires January 8, 2013                 [Page 7]
Internet-Draft                   dLife                      July 7, 2012

   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
   destinations. In such unpredictable scenario, it is important to take
 

Moreira, et al.         Expires January 8, 2013                 [Page 8]
Internet-Draft                   dLife                      July 7, 2012

   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.
   Besides PROPHET [Lindgren04], the most cited replication-based
 

Moreira, et al.         Expires January 8, 2013                 [Page 9]
Internet-Draft                   dLife                      July 7, 2012

   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
   the fact that users present different behavior during their daily
 

Moreira, et al.         Expires January 8, 2013                [Page 10]
Internet-Draft                   dLife                      July 7, 2012

   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/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 January 8, 2013                [Page 11]
Internet-Draft                   dLife                      July 7, 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 that the
   encountered node will 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 January 8, 2013                [Page 12]
Internet-Draft                   dLife                      July 7, 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 January 8, 2013                [Page 13]
Internet-Draft                   dLife                      July 7, 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 January 8, 2013                [Page 14]
Internet-Draft                   dLife                      July 7, 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 January 8, 2013                [Page 15]
Internet-Draft                   dLife                      July 7, 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 an (opportunistic) communications opportunity. 

   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 module,
   being the bundles placed in a queue available and manage 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 January 8, 2013                [Page 16]
Internet-Draft                   dLife                      July 7, 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 January 8, 2013                [Page 17]
Internet-Draft                   dLife                      July 7, 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 January 8, 2013                [Page 18]
Internet-Draft                   dLife                      July 7, 2012

   from the list.

3.2. Information Exchange Phase

   The Information Exchange phase comprises the transfer of sets of two
   type of information between the connected nodes:

        o Social message
        o Social Acknowledgment message

   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 phase, the Social message is
   expected to reflect the latest updates regarding both Social Weight
   Lists and Node Importance (SWLNI) information as well as include the
   lists of carried bundles (bundleList) by the peering node and of the
   latest delivered bundles (ackedBundleList).

   Upon a communication opportunity, one set of 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 needs more than
   one message to be completely transferred, it may be partitioned by
   the higher layer above the dLife protocol engine. The specification
   of dLife provides a sub-message mechanism and retransmission that
   allows large messages specified by the higher level to be transmitted
   in smaller chunks.

   The first step in the Information Exchange Phase is for dLife to send
   one or more Social messages containing the SWLNI, bundleList and
   ackedBundleList information. This set of messages contains: i) a list
   with the Endpoint Identifiers (EIDs) of the nodes that the neighbor
   nodes have encountered so far and their respective weights towards
   these nodes; ii) the importance of the peering nodes; iii) a list
   with the identifiers of the carried bundles and respective
   destinations EIDs; and iv) a list with the BUNDLE_DELIVERED latest
   acknowledged bundles identifiers and respective destinations EIDs.
   Upon reception and acknowledgment of the complete set of these
   messages, nodes apply any of the 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.

   The bundles are built based on the exchanged SWLNI, bundleList and
   ackedBundleList information and the available storage capacity on the
   receiving peering node. The bundles to be send to the Bundle Agent
   (cf. Send Bundle on section 2.4.1) shall not exceed the peering node
   capacity if it were specified. 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.
 

Moreira, et al.         Expires January 8, 2013                [Page 19]
Internet-Draft                   dLife                      July 7, 2012

   As the receiving node may have constraints regarding storage
   capacity, during the Hello phase neighbor nodes MUST inform the
   current node about their storage availability.

3.2.1. 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.

   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
 

Moreira, et al.         Expires January 8, 2013                [Page 20]
Internet-Draft                   dLife                      July 7, 2012

        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".

   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
 

Moreira, et al.         Expires January 8, 2013                [Page 21]
Internet-Draft                   dLife                      July 7, 2012

   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 Self-Delimiting Numeric Values (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 January 8, 2013                [Page 22]
Internet-Draft                   dLife                      July 7, 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 |  Res  |     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 in principle dLife
        messages could be sent as the Protocol Data Unit of an IP packet
        if an IP protocol number was allocated for dLife. At present
 

Moreira, et al.         Expires January 8, 2013                [Page 23]
Internet-Draft                   dLife                      July 7, 2012

        dLife is only specified to use UDP transport for dLife packets
        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.

   Version
        The Version of the dLife Protocol. Encoded as a four bit
        unsigned integer in network bit order. This document defines
        version 1.

   Flags
        Reserved field of 4 bits.

   Res (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 4 bit unsigned integer in
        network bit order. The following values are currently defined: 

            o Success: Result = 1 
            o Failure: Result = 2
            o 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
   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. The following values are defined:
 

Moreira, et al.         Expires January 8, 2013                [Page 24]
Internet-Draft                   dLife                      July 7, 2012

            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 identifies the sender EID of the dLife message. It is
        used to detect when the link comes back up after going down or
        when the identity of the entity at the other end of the link
        changes. This number is guaranteed to be unique within the
        recent past. Messages sent after the Hello phase should use the
        sender's number. The Sender Instance is encoded as a 16 bit
        unsigned integer in network bit order.

   Receiver
        This field identifies the receiver EID 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 phase should use the receiver's 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
        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
 

Moreira, et al.         Expires January 8, 2013                [Page 25]
Internet-Draft                   dLife                      July 7, 2012

        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.

   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                            ~
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   

 

Moreira, et al.         Expires January 8, 2013                [Page 26]
Internet-Draft                   dLife                      July 7, 2012

   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 which signals that the
   communication has been established. If during the Hello procedure 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
   Hello intervals without receiving a Hello TLV on a connection in the
   EXCHANGE state (cf. Section 5), the connection SHOULD be assumed
   broken.

 

Moreira, et al.         Expires January 8, 2013                [Page 27]
Internet-Draft                   dLife                      July 7, 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 |Flags|                     Length              |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  EID Length (SDNV)  |   Sender EID  |    Timer  |   Storage   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   Figure 4: Hello TLV Format

   TLV Flags
        The TLV Flags field contains a three bit Hello Function (HF)
        number that specifies one of four 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 information needed for the
   dLife operation, namely the storage capacity of the node. 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 Endpoint Identifier (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 DTN endpoint identifier
            (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.

        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.
 

Moreira, et al.         Expires January 8, 2013                [Page 28]
Internet-Draft                   dLife                      July 7, 2012

            It is a constant for the duration of a session. The timer
            field is specified in units of 100ms 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=0xA0 |     Flags     |           Length              |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                             ACK Type                          |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   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 Hello ACK 0x00 
            o Social Acknowledgement message 0x01 
            o Bundle ACK 0x02
            o Reserved 0x03 - 0x7F 
            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 TLV Data is defined as
        follows:

            Hello ACK
              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.

            Social Acknowledgement message

 

Moreira, et al.         Expires January 8, 2013                [Page 29]
Internet-Draft                   dLife                      July 7, 2012

              Report on the reception of Social messages (SWLNI,
              bundleList and ackedBundleList).

            Bundle ACK
              Provide positive or negative feedback regarding the
              receipt of bundles (e.g., reporting the identifier of the
              last bundle successfully received) as indicated on the
              Social TLVs.

4.3.3. Social TLV

   This TLV provides the SWLNI, 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
   build the social bundles 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=0xA0 |   Flags       |           Length              |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                       Importance Value                        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                      SWLNI Count (SDNV)                       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |              EID n            |   SWL value                   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                   Carried Bundle Count (SDNV)                 |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |       Carried Bundle ID n     |   Destination EID             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                    Acked Bundle Count (SDNV)                  |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |        Acked Bundle ID n      |   Destination EID             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   Figure 6: 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.

 

Moreira, et al.         Expires January 8, 2013                [Page 30]
Internet-Draft                   dLife                      July 7, 2012

              Flag 0: More Social TLVs 
              Flag 1: Reserved
              Flag 2: Reserved
              Flag 3: Reserved
              Flag 4: Reserved
              Flag 5: Reserved
              Flag 6: Reserved
              Flag 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

            SWLNI Count
              Number of entries regarding the SWLNI information in the
              TLV. Encoded as SDNV

            EID n
              String ID of the endpoint identifier of the destination
              for which this entry specifies the delivery predictability
              as predefined in a dictionary TLV. Encoded as SDNV.

            SWL value
              Social weight between peering node and that specific
              encountered node

            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.

            Destination EID 
 

Moreira, et al.         Expires January 8, 2013                [Page 31]
Internet-Draft                   dLife                      July 7, 2012

              EID of the destination for a carried or acknowledged
              bundle.

5. Detailed Operation

   This section provides more details on the operation of dLife,
   including state tables to help in implementing the protocol. 

   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 in the state tables:

   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, it will start counting the duration of
        this contact and 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 order to detect new
        contact opportunities. This could be handled by creating a new
        thread or process during the transition to the HELLO state that
        then takes care of the communication with the new neighbor while
        the parent remains in state SENSING waiting for additional
        neighbors to communicate. 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 neighbor is
        detected until the Hello procedure is completed, which occur
        after both nodes acknowledge the reception of Hello messages.
        Upon receiving a Hello message, the node stores the information
        about the peer capacity. Once the Hello procedure is done, the
        node starts the information exchange phase and transitions to
 

Moreira, et al.         Expires January 8, 2013                [Page 32]
Internet-Draft                   dLife                      July 7, 2012

        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 where it stops counting the contact duration
        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 information exchange is done. The node remains in
        this state as long as Information Exchange Phase TLVs (Social,
        Social Acknowledgment) are being received. If the node is
        notified that the neighbor is no longer in range before all
        information have been exchanged, the node returns to the SENSING
        state to await new neighbors and stops counting contact duration
        for that specific peer.

        In the EXCHANGE state both nodes are able to update their social
        weight and node importance information using data from the
        neighbor peer. With dLife the exchange of information about
        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 with a "More Social TLV" flag set
        to zero (i.e., no more bundles to send), the node starts the
        next_exchange timer. When this timer expires, the node reruns
        the information exchange if the neighbor is still connected.
        Otherwise, nodes switch to the SENSING state, where they stop
        counting contact duration and, if appropriate, MAY destroys any
        additional process or thread created to handle the neighbor. 

        If the neighbor is still connected after the next_exchange timer
        expires, this new information exchange phase will have the
        effect of further increasing the probability of selecting this
        node as a forwarder. If there is more than one neighbor
        connected or other communication opportunities have happened
        since the previous information exchange occurred, then the
        changes resulting from these other encounters will be passed on
        the connected neighbor. The next_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 next_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
 

Moreira, et al.         Expires January 8, 2013                [Page 33]
Internet-Draft                   dLife                      July 7, 2012

        SHOULD be immediately transferred to the connected neighbor.

State: SENSING
+===================================================================+
|     Condition    |           Action              |    New State   |
+==================+===============================+================+
|   New Contact    | Start counting duration       |                |
|                  | Start Hello for new contact   |      HELLO     |
|                  | Keep sensing for new contacts |     SENSING    |
+===================================================================+

State: HELLO
+====================================================================+
|     Condition        |              Action             | New State |
+======================+=================================+===========+
|   Hello TLV rcvd     |  Store peer capacity            |   HELLO   |
+----------------------+---------------------------------+-----------+
| Hello procedure done |  Start Information Exchange     | EXCHANGE  |
+----------------------+---------------------------------+-----------+
|   Disconnected       |  Stop contact duration count    |  SENSING  |
+====================================================================+

State: EXCHANGE
+===================================================================+
|    Condition      |               Action              | New State |
+===================+===================================+===========+
| SWL/NI TLV rcvd   | Create and send Social Bundle TLV | EXCHANGE  |
+-------------------+-----------------------------------+-----------+
|   Disconnected    | Stop contact duration count       |  SENSING  |
+-------------------+-----------------------------------+-----------+
|   More Social TLV |                                   |           |
|    flag = 0       | Start next exchange timer         | EXCHANGE  |
+-------------------+-----------------------------------+-----------+
|   exchange timer  | Check if peer is still connected  | EXCHANGE  |
|     expires       +-----------------------------------+-----------+    
|                   | Stop contact duration count       |  SENSING  |
+-------------------+-----------------------------------+-----------+
|    New bundle     |                                   | EXCHANGE  |
+===================================================================+
 

Moreira, et al.         Expires January 8, 2013                [Page 34]
Internet-Draft                   dLife                      July 7, 2012

5.2. High Level Meta-Data Table

   During its operation, dLife makes use of metadata (cf. Figure 7)
   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), 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
   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
   SocList_peer and Imp_peer, which must be stored for building the
   social bundles.

 

Moreira, et al.         Expires January 8, 2013                [Page 35]
Internet-Draft                   dLife                      July 7, 2012

    +------------------------+
    | EID_own | StoCap | Imp |
    +------------------------+
         |
         +----------+---------+----------+---------+--------+
         | EID_peer | CD_peer | TCT_peer | AD_peer | w_peer |
         +----------+---------+----------+---------+--------+
         |            |                    |
         |            +-----+-----+-----+  +------+------+------+
         |            | CD1 | ... | CDn |  | AD11 | ...  | AD1i | 
         |            +-----+-----+-----+  +------+------+------+
         |
         +-------------+--------------+----------+-----------+
         | StoCap_peer | SocList_peer | Imp_peer | fwd_times |
         +-------------+--------------+----------+-----------+

   Figure 7: Meta-data Information

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
            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
 

Moreira, et al.         Expires January 8, 2013                [Page 36]
Internet-Draft                   dLife                      July 7, 2012

            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
            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
 

Moreira, et al.         Expires January 8, 2013                [Page 37]
Internet-Draft                   dLife                      July 7, 2012

            be forwarded.

7. Implementation Experience

   The current implementation of dLife is written in Java for the
   version 1.4.1 of the Opportunistic Network Emulator (ONE), , named
   Dlife.java, 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 is being done in C# using the
   Monodroid development environment, aiming to construct a modular
   design, since its inception, for operation over multiple platforms:
   Windows, Linux, Android and iOS. Among the most important classes
   being implemented we can mention: Bundle class, which represents the
   implementation of RFC 5050; BluetoothConvergenceLayer, which allows
   direct exchange of bundles through the Bluetooth interface without
   the need of a structured WiFi network; GenericRouting, a class-based
   routing that can be extended to represent a specific protocol;
   BundleSecurity, which constitutes the security layer implemented
   according to RFC 6257 Bundle security Protocol Specification.

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, 3 smartphones, 4 wireless routers) and
   will grow until 16 devices (5 wifi tablets, 5 smartphones, 2 personal
   computers and 4 wireless routers). In a later phase, the DTN package
 

Moreira, et al.         Expires January 8, 2013                [Page 38]
Internet-Draft                   dLife                      July 7, 2012

   with routing functionality will be made available for download,
   allowing its deployment in personal devices from local citizens. In
   terms operating systems, the deployment is being tested with Linux
   Ubuntu 10.10 Maverick and Android 2.3.6 Gingerbread (kernel version
   2.6.35.7) devices, as well as OpenWrt 10.03.1 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.

   Initial tests of the dLife implementation, as described in this
   document, will be made in a controlled test-bed with 4 Android
   devices using a text messaging application for operation testing,
   where each node sent messages alternating destinations. These tests
   aimed to analyze the performance of the dLife, when compared to
   behavior of 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.

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.
 

Moreira, et al.         Expires January 8, 2013                [Page 39]
Internet-Draft                   dLife                      July 7, 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.

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-
 

Moreira, et al.         Expires January 8, 2013                [Page 40]
Internet-Draft                   dLife                      July 7, 2012

              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,
              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),
 

Moreira, et al.         Expires January 8, 2013                [Page 41]
Internet-Draft                   dLife                      July 7, 2012

              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
              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 January 8, 2013                [Page 42]
Internet-Draft                   dLife                      July 7, 2012

Moreira, et al.         Expires January 8, 2013                [Page 43]