Internet DRAFT - draft-moreira-dlife

draft-moreira-dlife



 



DTN Research Group                                            W. Moreira
Internet-Draft                                                 P. Mendes
Expires: November 9, 2014                COPELABS, Universidade Lusofona
                                                            E. Cerqueira
                                      ITEC, Universidade Federal do Para
                                                             May 8, 2014


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


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 periods of time. 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.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute 
 


Moreira, et al.         Expires November 9, 2014                [Page 1]

Internet-Draft                   dLife                       May 8, 2014


   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 November 9, 2014.

Copyright and License Notice

   Copyright (c) 2014 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) . . . . . . . . . 14
       2.2.2. TECD Importance (TECDi) . . . . . . . . . . . . . . . . 15
     2.3. Forwarding strategy . . . . . . . . . . . . . . . . . . . . 15
       2.3.1. Basic Strategy  . . . . . . . . . . . . . . . . . . . . 15
       2.3.2. Prioritized Strategy  . . . . . . . . . . . . . . . . . 16
     2.4. Interfaces  . . . . . . . . . . . . . . . . . . . . . . . . 16
       2.4.1. Bundle Agent  . . . . . . . . . . . . . . . . . . . . . 16
       2.4.2. Lower Layers and Interface  . . . . . . . . . . . . . . 17
   3. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . . 18
 


Moreira, et al.         Expires November 9, 2014                [Page 2]

Internet-Draft                   dLife                       May 8, 2014


     3.1. Neighbor Sensing Phase  . . . . . . . . . . . . . . . . . . 18
     3.2. Information Exchange Phase  . . . . . . . . . . . . . . . . 20
       3.2.1. EID Dictionary  . . . . . . . . . . . . . . . . . . . . 21
       3.2.2. Operation in the presence of multiples neighbors  . . . 22
     3.3. Bundle Reception Policies . . . . . . . . . . . . . . . . . 22
       3.3.1. Queueing policy . . . . . . . . . . . . . . . . . . . . 22
       3.3.2. Custody Policy  . . . . . . . . . . . . . . . . . . . . 23
       3.3.3. Destination Policy  . . . . . . . . . . . . . . . . . . 24
   4. Message Formats . . . . . . . . . . . . . . . . . . . . . . . . 24
     4.1. Header  . . . . . . . . . . . . . . . . . . . . . . . . . . 25
     4.2. TLV Structure . . . . . . . . . . . . . . . . . . . . . . . 28
     4.3. TLVs  . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
       4.3.1. Hello TLV . . . . . . . . . . . . . . . . . . . . . . . 29
       4.3.2. ACK TLV . . . . . . . . . . . . . . . . . . . . . . . . 30
       4.3.3. EID Dictionary TLV  . . . . . . . . . . . . . . . . . . 31
       4.3.4. Social TLV  . . . . . . . . . . . . . . . . . . . . . . 33
   5. Detailed Operation  . . . . . . . . . . . . . . . . . . . . . . 36
     5.1. High Level State Tables . . . . . . . . . . . . . . . . . . 36
     5.2. High Level Meta-Data Table  . . . . . . . . . . . . . . . . 39
     5.3 Hello Procedure  . . . . . . . . . . . . . . . . . . . . . . 41
     5.4 Information Exchange Phase . . . . . . . . . . . . . . . . . 42
   6. Security Considerations . . . . . . . . . . . . . . . . . . . . 45
   7. Implementation Experience . . . . . . . . . . . . . . . . . . . 46
   8. Deployment Experience . . . . . . . . . . . . . . . . . . . . . 48
   10.  References  . . . . . . . . . . . . . . . . . . . . . . . . . 50
     10.1  Normative References . . . . . . . . . . . . . . . . . . . 50
     10.2  Informative References . . . . . . . . . . . . . . . . . . 50
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 52




















 


Moreira, et al.         Expires November 9, 2014                [Page 3]

Internet-Draft                   dLife                       May 8, 2014


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 reduced associated 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 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 November 9, 2014                [Page 4]

Internet-Draft                   dLife                       May 8, 2014


   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 periods
   of time. 

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

   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 November 9, 2014                [Page 5]

Internet-Draft                   dLife                       May 8, 2014


   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 its operation, dLife does not
   impose any requirements for data reliability transfer to avoid
   restricting its applicability. Hence, data exchange may take place
   over transport protocols that do not provide neither message
   segmentation or reliability, nor in order delivery. Hence, dLife
   provides itself the capability to segment protocol messages into
   submessages. Submessages are provided with sequence numbers, and
   this, together with the capability for positive acknowledgements
   allows dLife to operate over an unreliable protocol such as UDP or
   potentially directly over IP. As said for the bundle agent, the
   communication medium used to send dLife messages can include
   different technologies such as Bluetooth and Wi-Fi.

   Moreover, dLife expects to be able to use bidirectional links for
   information exchange; this allows information exchange to take place
   in both directions over the same link, avoiding the need to establish
   a second link for information exchange in the reverse direction.

1.1.2. Applicability scenarios

   The identified scenarios aim to illustrate the applicability of dLife
   in real scenarios. In technical terms, dLife aims to target networks
   where we may not find any end-to-end path between any pair of nodes
   at some moment in time. The lack of end-to-end path may be due to
   node mobility and availability (e.g., switching off radios), aspects
   that create connectivity patterns that are correlated with the daily
   habits of citizens. Human behavior patterns (often containing daily
   or weekly periodic activities) provide one example where dLife is
   expected to be applicable, independently of the type of personal
   device: it can be of explicit usage (e.g., smartphones) or of
   implicit usage (e.g., embedded devices).

   Scientific results [Moreira12a] [Moreira12b] show that dLife is able
   to benefit from the predictability of human behavior in daily periods
   of time even in the presence of few contacts. However, the behavior
   predictability can be estimated more accurately with a higher number
   of events.

1.1.2.1. Urban Areas Networks

   This seems to be the most challenging scenario to analyze the
   applicability of DTN employing dLife as the store-carry-forward
   routing protocol. A study of DTN routing for urban scenarios may
 


Moreira, et al.         Expires November 9, 2014                [Page 6]

Internet-Draft                   dLife                       May 8, 2014


   bring a coherent understanding about the advantages and challenges of
   using a DTN system in the daily life of millions of people. A study
   of the applicability of DTN routing in urban scenarios may benefit
   from a good understanding of the per-person bit density (available
   capacity per second/hour/day) in a major metropolitan area.

   In a urban area, there are several examples of networking scenarios
   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 scenarios 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 metadata, 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
 


Moreira, et al.         Expires November 9, 2014                [Page 7]

Internet-Draft                   dLife                       May 8, 2014


   environments.

   From a networking model perspective, a DTN is a network of self-
   organizing wireless nodes connected by multiple time-varying links,
   and where end-to-end connectivity is intermittent. Even in urban
   scenarios, it is possible to face intermittent connectivity due to
   dark areas, such as inside buildings and metropolitan systems, as
   well as public areas with closed access points or even places
   overcrowded with wireless access points. Unavailability of wireless
   connectivity can be also a result of power-constrained nodes that
   frequently shut down their wireless cards to save energy. 

   From a conceptual point of view, a DTN consists of a node meeting
   schedule and workload. A node meeting schedule is a directed
   multigraph, where each direct edge between two nodes represents a
   meeting opportunity between them, and it is annotated with a starting
   time of the meeting, the ending time of the meeting, if known, the
   size of the transfer opportunity (i.e., contact capacity), and the
   contact type. The workload is a set of messages. Each message can be
   represented by the source, destination, size, time of creation at the
   source, and priority. In dLife, a contact is defined by the tuple
   <starting time, end time, contact duration> and a message by the
   tuple <source, destination, size>.

   A DTN model encompasses the notion of type of contact or
   connectivity. In current networks, the connectivity of a link or path
   is generally given as a binary state (i.e., connected or
   disconnected). In DTNs, a richer set of connectivity options is
   required to make efficient routing decisions. Most importantly, links
   (and paths, by extension) may provide a scheduled, predicted or
   opportunistic communication.

   Scheduled contacts imply some a priori knowledge about adjacent nodes
   regarding future availability of links for message forwarding.
   Scheduled links are the most typical cases for today's Internet and
   satellite networks. Predicted contacts correspond to communication
   opportunities wherein the probability of knowing whether a link will
   be available at a future point in time is strictly above zero and
   below one. Such links are the result of observed behavior (e.g., a
   person may use its home Internet connection with significant
   probability for any given time period) being characterized using
   statistical estimation. Predicted links have gained attention due to
   ad-hoc wireless networking, where node mobility may be significant. 

   In more challenging environments, such as mission-critical networks,
   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
 


Moreira, et al.         Expires November 9, 2014                [Page 8]

Internet-Draft                   dLife                       May 8, 2014


   messages towards a specific destination or a group of destinations.
   In such unpredictable scenario, it is important to take into account
   the time that a node must wait until it meets another node again
   (i.e., inter-contact time), the duration of these contacts (i.e.,
   contact duration), and the quality of the contact in terms of the set
   of information that can be transferred (i.e., contact volume). 

   Independently of the type of connectivity, a contact in a DTN is
   direction-specific. For example, a dial-up connection originating at
   a customer's home to an Internet Service Provider (ISP) may be
   scheduled from the point of view of the customer but unscheduled from
   the point of view of the ISP. In what concerns contacts, dLife
   assumes direction-specific opportunistic contacts (starting time, end
   time, contact duration) which occur with some probability in pre-
   defined daily time periods.

   Another concept that must be introduced is that of network behavior.
   As networks can be formed on-the-fly, their behavior can either be
   deterministic or stochastic, depending on the type of used links. In
   this draft, we focus on dynamic scenarios, where the behavior of the
   network is described in stochastic terms, based on users' mobility
   and social behavior. In a dynamic scenario, users move around
   carrying their personal devices, which opportunistically come into
   contact with each other, resulting in rather frequent 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 have identified [Moreira13] 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 the 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,
 


Moreira, et al.         Expires November 9, 2014                [Page 9]

Internet-Draft                   dLife                       May 8, 2014


   contact frequency and the last time a contact occurs. Besides PROPHET
   [Lindgren04], the most cited replication-based proposal, other
   examples based on contact metric are Prediction [Song07], and
   Encounter-Based Routing [Nelson09].

   Most of the existing opportunistic routing solutions are based on
   some level of replication. Among these proposals, emerge solutions
   based on different representations of social similarity: i) labeling
   users according to their social groups (e.g., Label [Hui07]); ii)
   looking at the importance (i.e., popularity) of nodes (e.g.,
   PeopleRank [Mtibaa10]); iii) combining the notion of community and
   centrality (e.g., SimBet [Daly07] and Bubble Rap [Hui11]); iv)
   considering interests that users have in common (e.g., SocialCast
   [Costa08]). Such prior-art shows that social-based solutions are more
   stable than those which only consider node mobility. However, they do
   not consider the dynamism of users' behavior (i.e., social daily
   routines) and use centrality metrics, which may create bottlenecks in
   the network. Moreover, such approaches assume that communities remain
   static after creation, which is not a realistic assumption. On the
   other hand, prior-art also shows that users have routines that can be
   used to derive future behavior. It has been proven that mapping real
   social interactions to a clean (i.e., more stable) connectivity
   representation is rather useful to improve delivery. With dLife,
   users' daily routines are considered to quantify the time-evolving
   strength of social interactions and so to foresee more accurately
   future social contacts than with proximity graphs inferred directly
   from inter-contact times.

1.4. Requirements notation 

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in RFC 2119 [RFC2119].


2. Node Architecture

   In this section, we describe the architecture of a dLife node, which
   performs its routing decisions based on two utility functions: TECD
   to forward messages to nodes that have a stronger social relationship
   with the destination than the carrier; TECDi to forward messages to
   nodes that have a higher importance than the carrier.

   With TECD each node computes the average of its contact duration with
   other nodes during the same set of daily time periods over
   consecutive days. Our assumption 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
 


Moreira, et al.         Expires November 9, 2014               [Page 10]

Internet-Draft                   dLife                       May 8, 2014


   for considering different daily time periods relates to the fact that
   users present different behavior during their daily routines. If the
   carrier and encountered nodes have no social information towards the
   destination, forwarding takes place based on a second utility
   function, TECDi.

   We start this section by describing the different components of the
   node architecture, followed by an explanation of how to route
   information based on the dynamics of the network that dLife is able
   to capture by computing TECD and TECDi. Finally, we describe the
   implemented forwarding strategy and the needed interfaces.

2.1. dLife Components

   In order to perform forwarding based on the social daily behavior of
   users, dLife comprises the following main computational elements:

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

   o 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 (see
   below). Additionally, SIR will temporarily store the social weight
   and importance of an encountered node when the need for replicating a
   bundle arises.

   o 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 SIR to determine the total contact time nodes spent
   together and the average duration of contacts in order to compute the
   social weight between nodes.

   o Importance Assigner (IA) - responsible for computing the importance
   of a node taking into account the importance of encountered nodes and
   its social weight towards such nodes. At the end of every daily
   sample, IA will interact with SIR in order to compute the importance
   of a node in the system.

 


Moreira, et al.         Expires November 9, 2014               [Page 11]

Internet-Draft                   dLife                       May 8, 2014


   o 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 decide 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's
   destination than the carrier in a given daily sample, it receives a
   bundle copy, since there is a much greater chance for the encountered
   node to meet the destination in the future. If relationship to the
   bundle's destination is unknown, replication happens only if the
   encountered node has higher importance than the bundle's current
   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 these parameters is
   given below:

   CD_(x,y) 
      Refers to the contact duration between nodes, i.e., time nodes
      spent in the communication range of one another, which would allow
      them to exchange information. Within a given daily sample,
      different contacts can happen 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 November 9, 2014               [Page 12]

Internet-Draft                   dLife                       May 8, 2014


   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 used to determine
   TCT_(x,y), AD_(x,y), w_(x,y), and I_(x) at the end of every daily
   sample. If dLife is configured with a high number of daily samples,
   the social weight and node importance will be more refined. Thus, it
   is recommended the usage of twenty-four (24) daily samples
   representing each hour of the day: the first daily sample refers
   always to the zero hour of the day when the node is started.

   Being able to identify the current daily sample allows a proper
   computation of social weights and importance. Hence, in the case of
   node failure (e.g., node crash) or node shutdown (e.g., lack of
   battery), nodes need to know exactly in which daily sample they
   stopped interaction, and more importantly how many daily samples have
   elapsed since then (elapsed_ds). To guarantee that, the equation
   below is used:

   elapsed_ds = cnds * (ed - 1) + (cds - 1) + (cnds - lds)      (1)

   where:

   cnds
      is the configured number of daily samples.

   ed
      refers to the number of elapsed days.

   cds
      refers to the current daily sample (the one in which the node came
      back on).

   lds
 


Moreira, et al.         Expires November 9, 2014               [Page 13]

Internet-Draft                   dLife                       May 8, 2014


      refers to last daily sample (in which the node failed or shut
      down).

   With this, the node knows how many daily samples have elapsed and can
   proceed with the update of social weights and importance to reflect
   the lack of interaction that happen in reality.

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 had 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))    (2)

   The Total Contact Time between users in the same daily sample over
   consecutive days can be used to estimate the average duration of
   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    (3)

   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. 
 


Moreira, et al.         Expires November 9, 2014               [Page 14]

Internet-Draft                   dLife                       May 8, 2014


   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))     (4)

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))    (5)

   TECDi is based on the PeopleRank function [Mtibaa10]. However, TECDi
   considers not only node importance, but also the strength of social
   ties between bundle's current carrier 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 level of randomness may vary with the application scenario.
   Unless previously experimented, it is suggested that dumping factor
   be set to 0.8.

2.3. Forwarding strategy

   Independently of the application scenario, each node MUST employ a
   forwarding strategy. The first rule is that 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 for the description provided in this
   section. 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)
 


Moreira, et al.         Expires November 9, 2014               [Page 15]

Internet-Draft                   dLife                       May 8, 2014


   When two nodes A and B meet in any daily sample Ti, node A gets from
   node B: a) the updated list of all neighbors of B, including the
   social weights that B has towards each of its neighbors, as well as
   the importance of B; b) the list of the bundles that B is carrying
   (bundle identifier, plus Endpoint Identifier (EID) of the
   destination); c) the list of the latest set of bundles acknowledged
   to B (the size of the list of acknowledged bundles returned by B
   depends on the local cache size and policy). 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 i) is not carried
   by B, ii) has not been previously acknowledged to B, and iii) B has
   enough buffer space to store it, 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 that have already been acknowledged to node B 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 as destination.

2.4. Interfaces

   This section provides a specification of the two major interfaces
   required for dLife operation: a) the interface between the dLife
   routing agent and the bundle agent; b) the interface between the
   dLife routing agent and the lower layers.

2.4.1. Bundle Agent

   The bundle protocol [RFC5050] introduces the concept of a "bundle
   agent" that manages the interface between applications and the
   "convergence layers" that provide the transport of bundles between
   nodes during communication opportunities. This draft extends the
   bundle agent with a routing agent that controls the actions of the
   bundle agent during communication opportunities. 

   This section defines the interfaces to be implemented between the
 


Moreira, et al.         Expires November 9, 2014               [Page 16]

Internet-Draft                   dLife                       May 8, 2014


   bundle agent and the dLife routing agent. The defined interfaces
   follow the general definition that was defined for the PRoPHET
   proposal.

   In this document, we assume that functions in a complete bundle agent
   supporting dLife are distributed in such a way that reception and
   delivery of bundles are not carried out directly by the dLife agent,
   being the bundles placed in a queue available and managed by the
   dLife agent. In this case, this interface allows the dLife routing
   agent to be aware of the bundles placed at the node, and allows it to
   inform the bundle agent about the bundles to be sent to a neighbor
   node. Therefore, the bundle agent needs to provide the following
   interface/functionality to the routing agent:

   Get Bundle List 
      Returns a list of the stored bundles and their attributes to the
      routing agent.

   Send Bundle 
      Notifies the bundle agent to send a specified bundle.

   Drop Bundle Advice 
      Advises the bundle agent that a specified bundle may be dropped by
      the bundle agent if appropriate.

   Acked Bundle Notification
      Bundle agent informs routing agent whether a bundle has been
      delivered to its final destination and time of delivery.

2.4.2. Lower Layers and Interface

   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 about them. Hence,
      neighbor discovery is not a mandatory part of dLife. However, 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
 


Moreira, et al.         Expires November 9, 2014               [Page 17]

Internet-Draft                   dLife                       May 8, 2014


          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.

      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.

   Sender/Receiver Local Address 
      An address used by the underlying communication layer (e.g., an IP
      or MAC address) that identifies the address of the sender and
      receiver nodes. This address and its format is dependent on the
      communication layer that is being used by the dLife layer. This
      address must be unique among the nodes that can currently
      communicate.


3. Protocol Overview

   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

 


Moreira, et al.         Expires November 9, 2014               [Page 18]

Internet-Draft                   dLife                       May 8, 2014


   The operation of dLife depends on how nodes interact, i.e.,
   considering all the potential contact opportunities to exchange
   information. Thus, 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 mechanism as described in
   Section 2.4.2 can be provided. 

   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. In the case the
      peer node has been encountered before within the same daily
      sample, dLife checks if there were any changes in the metadata
      (e.g., Social Weights and Node Importance list, ackedBundleList)
      of the current node since the last encounter. If so, the current
      node will start the Hello Procedure.

   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 EID,
      storage capacity, current time, and timer value. Once the link has
      been set up, the protocol may continue to the Information Exchange
      Phase (cf. Section 3.2) during which the lower layer is
      responsible for detecting broken links.

   Stop Contact Duration Counting
      dLife stops counting the contact duration after detecting that the
      neighbor is gone, through the notification received from the lower
      layer (cf. Section 2.4.2).

   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
   from the list. It is suggested that such threshold be initially set
   at 0.2, which is equivalent to the initial social weight towards
   recently encountered nodes.

 


Moreira, et al.         Expires November 9, 2014               [Page 19]

Internet-Draft                   dLife                       May 8, 2014


3.2. Information Exchange Phase

   The Information Exchange phase comprises the transfer of two types of
   metadata between connected nodes, through different messages
   described in Section 4:

   o EID Dictionary
   o Social Weights and Node Importance (SWNI)

   Upon a communication opportunity, different sets of each type of
   metadata must be sent in each direction as explained further in this
   section. Each set may be transferred in one or more messages. In case
   a set of metadata needs more than one message to be completely
   transferred, it may be partitioned by the dLife protocol engine. The
   specification of dLife provides a submessage mechanism and
   retransmission that allows large messages to be transmitted in
   smaller chunks.

   Each node running dLife is responsible for computing and updating
   their social weights towards previously encountered nodes as well as
   their own importance. Thus, in this operational phase, Social TLVs
   (Type-Length-Value messages), as defined in Section 4.3.4, are
   expected to reflect the latest updates regarding SWNI metadata, as
   well as to include the list of bundles carried by the peering node
   (bundleList) and the list of the latest bundles with acknowledged
   delivery (ackedBundleList). Social TLVs are generated throughout the
   information exchange phase upon updates of the SWNI information at
   the end of a daily sample.

   As first step in the Information Exchange Phase one or more messages
   containing EID Dictionary metadata, EID Dictionary TLVs as defined in
   Section 4.3.3, MUST be sent to the peering node, if the list of
   encountered nodes is not empty. Such metadata contains a dictionary
   of the EIDs of the nodes that will be listed in the Social TLVs (cf.
   Section 3.2.1 for more information about this dictionary). 

   As a second step, one or more messages containing social metadata,
   Social TLVs, MUST be sent to the peering node, if the list of
   encountered nodes is not empty. This set of messages contains: i) a
   list with the EIDs of the nodes that the peering node has encountered
   so far and its social weights towards these nodes; ii) the importance
   of the peering node; iii) a list with the identifiers of the bundles
   that the node currently carries and respective destinations EIDs; and
   iv) a list with the latest acknowledged bundles identifiers and
   respective destinations EIDs. 

   As a third step, upon reception and acknowledgment of the complete
   set of these messages, nodes MUST use one of the defined forwarding
 


Moreira, et al.         Expires November 9, 2014               [Page 20]

Internet-Draft                   dLife                       May 8, 2014


   strategies (see Section 2.3) to decide which of the stored bundles
   (cf. Get Bundle List on Section 2.4.1) will be transferred to the
   peer, assuming that there are stored bundles.

   The bundles to be sent to the peering node MUST be selected based
   upon the exchanged SWNI, bundleList and ackedBundleList information,
   as well as the available storage capacity on the receiving peering
   node. The bundles to be sent by the Bundle Agent (cf. Send Bundle on
   Section 2.4.1) SHOULD NOT exceed the peering node's capacity that
   MUST be indicated by the peer during the Hello procedure. The
   information to be passed to the Bundle Agent includes the number of
   bundles to be sent, where each bundle has an ID to be used for
   acknowledging their receipt.

3.2.1. EID Dictionary

   The EID Dictionary, as used in PRoPHET, is a mapping between variable
   length EIDs [RFC4838] and String IDs coded as Self-Delimiting Numeric
   Values (SDNVs - see Section 4.1. of RFC 5050 [RFC5050]).

   This dictionary is used by peering nodes to synchronize the EIDs of
   the nodes that they have encountered before. Each peer MAY add to the
   dictionary by sending a EID Dictionary TLV to its peer. To allow
   either peer to add to the dictionary at any time, the identifiers
   used by each peer are taken from disjoint sets: identifiers
   originated by the node that started the Hello procedure have the
   least significant bit set to 0 (i.e., are even numbers) whereas those
   originated by the other peer have the least significant bit set to 1
   (i.e., are odd numbers). This means that the dictionary can be
   expanded by either node at any point of the information exchange
   phase and the new identifiers can then be used in subsequent TLVs
   until the dictionary is reinitialized.

   The dictionary that is established only persists through a single
   encounter with a node (i.e., while the same link set up by the Hello
   procedure, with the same instance numbers, remains open).

   Having more than one identifier for the same EID does not cause any
   problems. This means that it is possible for the peers to create
   their dictionary entries independently if required by an
   implementation, but this may be inefficient as a dictionary entry for
   an EID might be sent in both directions between the peers. It may be
   required to inspect entries sent by the node that started the Hello
   procedure and thereby eliminate any duplicates before sending the
   dictionary entries from the other peer. Whether postponing sending
   the other peer's entries is more efficient depends on the nature of
   the physical link technology and the transport protocol used. With a
   genuinely full duplex link it may be faster to accept possible
 


Moreira, et al.         Expires November 9, 2014               [Page 21]

Internet-Draft                   dLife                       May 8, 2014


   duplication and send dictionary entries concurrently in both
   directions. If the link is effectively half-duplex (e.g., Wi-Fi),
   then it will generally be more efficient to wait and eliminate
   duplicates.

   If a node receives EID Dictionary metadata containing an identifier
   that is already in use, the node MUST confirm that the corresponding
   EID is identical to the EID in the existing entry. Otherwise, the
   node MUST send an ACK TLV (i.e., EID ACK - identifier/EID
   discrepancy) and ignore the EID Dictionary TLV containing the error.
   If a node receives EID Dictionary metadata that uses an unknown
   identifier (i.e., not in the dictionary), the node MUST send an ACK
   TLV (i.e., EID ACK - unknown EID) message and ignore the TLV
   containing the error.

3.2.2. Operation in the presence of multiples neighbors

   As a node may find itself in the range of more than one potential
   next forwarder, the neighbor sensing mechanism may establish multiple
   information exchanges with each of them. 

   If these simultaneous contacts persist for some time, then the
   information exchange process will be periodically rerun for each
   contact according to the configured timer interval, which means that
   different Hello TLVs will be exchanged at different times.

   Based on the receipt time of these Hello TLVs at the sending node, it
   will establish the order for sending out the bundles, considering the
   storage capacity of the different neighbors.

3.3. Bundle Reception Policies 

3.3.1. Queueing policy

   Because of limited buffer resources, bundles may need to be dropped
   at some nodes. Although dLife evaluation based on simulations have
   shown little consumption due to limiting replication based on social
   strength, a scheme MUST be used upon an exhaustion of buffer space.
   Hence, each node MUST operate a queueing policy that determines which
   bundles should be available for forwarding. 

   This section defines a few basic queueing policies, inline with what
   was proposed for PRoPHET. However, nodes MAY use other policies if
   desired. If not chosen differently due to the characteristics of the
   deployment scenario, nodes SHOULD choose FIFO as the default queueing
   policy.

   FIFO
 


Moreira, et al.         Expires November 9, 2014               [Page 22]

Internet-Draft                   dLife                       May 8, 2014


      Handles the queue in a First In First Out (FIFO) order. The bundle
      that has 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 SHOULD keep track
      of the number of times each bundle has been forwarded to other
      nodes.

   STTL
      The bundle that has shortest time-to-live is dropped first. As
      described in [RFC5050], each bundle has a timeout value specifying
      when it no longer is meaningful to its application and should be
      deleted. Since bundles with short remaining time to live will soon
      be dropped anyway, this policy decides to drop the bundle with the
      shortest remaining life time first. To successfully use a policy
      like this, there needs to be some form of time synchronization
      between nodes so that it is possible to know the exact lifetimes
      of bundles.

   DLSW
      The bundle that has a destination with low social weight is
      dropped first. A low social weight means that the carrier may not
      be the best forwarder to this bundle. However, such bundle can
      only be dropped if it was already forwarded for at least a Minimum
      Bundle Forward (MBF) times, which is a minimum number of forwards
      that a bundle must have been forwarded before being dropped (if
      such a bundle exists).

   More than one queueing policy MAY be combined in an ordered set,
   where the first policy is used primarily, the second only being used
   if there is a need to tie-break between bundles given the same
   eviction priority by the primary policy, and so on. It is worth
   noting that obviously nodes MUST NOT drop bundles for which it has
   custody unless the lifetime expires.

3.3.2. Custody Policy

   The concept of custody transfer can be found in [RFC4838]. In general
   terms, the transmission of bundles with the Custody Transfer
   Requested option involves moving bundles "closer" (in terms of some
   routing metric) to their ultimate destination(s) with reliability.
   The nodes receiving these bundles along the way (and agreeing to
   accept the reliable delivery responsibility) are called "custodians".
   The movement of a bundle (and its delivery responsibility) from one
   node to another is called a "custody transfer".

 


Moreira, et al.         Expires November 9, 2014               [Page 23]

Internet-Draft                   dLife                       May 8, 2014


   The reliability requirement that a custodian accepts can be
   instantiated in different ways: i) deleting the bundle after getting
   a confirmation of a successful custody transfer, which may require
   retransmissions over a reliable transport protocol, such as TCP. In
   this case, a bundle has normally one custodian in a moment in time;
   ii) deleting the bundle only after getting an acknowledgment that the
   bundle was delivered to the destination. In this case, a bundle can
   have more than one custodian, being the bundle replicated among
   custodians over a non-reliable transport protocol, such as UDP.

   dLife takes no responsibilities for making custody decisions. Such
   decisions should be made by a higher layer. However, dLife insures
   that custodian nodes do not drop bundles for which it has custody
   unless the lifetime expires, or an acknowledge message is received
   for that bundle.

3.3.3. Destination Policy

   When a bundle reaches its final destination, the Bundle Agent sends a
   notification to the routing agent (cf. Acked Bundle Notification in
   Section 2.4.1), being that information (e.g., Bundle, deliveryTime)
   stored in the ackedBundleList 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, the
   ackedBundleList is periodically checked and bundles are removed
   following the configured queueing policy (c.f. Section 3.3.1) if the
   size of the list is bigger than a predefined threshold. When a node
   receives a notification for a bundle it is carrying, it MUST delete
   that bundle from its queue, since the notification indicates that a
   bundle has been delivered to its final destination.

   Nodes MAY keep track of which nodes they have sent Bundle ACKs for
   certain bundles to, and MAY in that case refrain from sending
   multiple Bundle ACKs for the same bundle to the same node.


4. Message Formats

   This section defines the message formats of the dLife routing
   protocol. In order to allow for variable length fields, many numeric
   fields are encoded as SDNVs, defined in [RFC5050], as in PRoPHET.
   Since many of the fields are coded as SDNVs, the size and alignment
   of fields indicated in many of the specification diagrams below are
   indicative rather than prescriptive. 

   The basic message format shown in Figure 1 consists of a header (see
 


Moreira, et al.         Expires November 9, 2014               [Page 24]

Internet-Draft                   dLife                       May 8, 2014


   Section 4.1) followed by a sequence of one or more Type-Length-Value
   components (TLVs) taken from the specifications in Section 4.2.

    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 dLife 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 |              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 is encoded as 8-bit unsigned
      integer in network bit order. The value of this field is 0. The
 


Moreira, et al.         Expires November 9, 2014               [Page 25]

Internet-Draft                   dLife                       May 8, 2014


      dLife header is organized in this way so that dLife messages MAY
      be sent as the Protocol Data Unit of an IP packet if an IP
      protocol number was allocated for dLife. Transmitting dLife
      packets directly as an IP protocol on a public IP network such as
      the Internet would generally not work well because middle boxes
      such as firewalls and NAT boxes would be unlikely to allow the
      protocol to pass through and the protocol does not provide any
      congestion control. However, it could be so used on opportunistic
      wireless networks, which is the goal of dLife. The use of a light
      transport protocol such as UDP, in opposition to TCP, ensures a
      better exploitation of the presumable short contact opportunities
      between peers in a DTN. Due to the lack of reliability of UDP,
      dLife specify an acknowledgement procedure to transmit metadata.
      Hence, dLife is prepared to use UDP over Wi-Fi, while over
      Bluetooth, dLife uses the RFCOMM and L2CAP protocols. In both
      cases, message acknowledgement is made by the dLife mechanism.

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

   Flags
      The flags field is encoded as a 4-bit unsigned integer in network
      bit order. The following values are currently defined: 

      o Success 0 
      o Failure 1

   Code
      This field gives further information concerning the flag in a
      response message. It is mostly used to pass an error code in a
      failure response, but it 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 with 5 unused and reserved bits, which were included to
      allow future extension of the protocol. The following values are
      defined:

      o Generic Response 0x00 
      o Submessage Received 0x01
      o ACK TLV in message 0x02
 


Moreira, et al.         Expires November 9, 2014               [Page 26]

Internet-Draft                   dLife                       May 8, 2014


      o Unexpected Error 0x03

      The "generic response" and the "submessage received" values tell
      us that the success or failure indicated in the Flag field is
      related to all the message or a submessage, respectively.

   Sender
      This field is the instance number for the link of the sender of
      the dLife message. This instance number identifies a link between
      peering nodes and lasts until the link goes down or when the
      identity of the entity at the other end of the link changes. It is
      randomly generated. This number is a 16-bit number that is
      guaranteed to be unique within the recent past and to change when
      the link or node comes back up after going down. Zero is not a
      valid instance number. Messages sent throughout all the
      communication phases (i.e., Sensing, Hello, Information exchange)
      should use the sender's instance number. The Sender Instance is
      encoded as a 16-bit unsigned integer in network bit order.

   Receiver
      This field is the instance number for the link of the receiver of
      the dLife message. If the sender of the message does not know the
      current number of the receiver, this field MUST be set to zero.
      Messages sent throughout all the communication phases (i.e.,
      Sensing, Hello, Information exchange) should use the receiver's
      instance number. The receiver number is encoded as a 16-bit
      unsigned integer in network bit order.

   Message Identifier 
      Used to associate a message with its response message. This
      identifier 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 submessages, the S flag will be set and
 


Moreira, et al.         Expires November 9, 2014               [Page 27]

Internet-Draft                   dLife                       May 8, 2014


      this field will contain the total count of SubMessage segments.
      The SubMessage Number is encoded as a 15-bit unsigned integer in
      network bit order. The SubMessage number is zerobased, i.e., for a
      message divided into n submessages, they are numbered from 0 to (n
      - 1). For a message that it is not divided into submessages, 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.

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

   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

 


Moreira, et al.         Expires November 9, 2014               [Page 28]

Internet-Draft                   dLife                       May 8, 2014


   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 of one another, and are used
   to inform neighbors about the EID, storage capacity, and current time
   of the node and a timer value.

   The Hello sequence must be completed so other TLVs can be exchanged.
   After the Hello procedure, dLife nodes will store the information
   about each other EIDs, capacities, and considered timer. Such action
   is acknowledged by signaling that the communication has been
   established. If during the Hello procedure, an ACK is failed to be
   received, disconnection occurred and link should be assumed broken.

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | TLV type=0x01 |Flags|               TLV Length (SDNV)         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |EIDLength(SDNV)|        Sender EID (SDNV)      | Timer (SDNV)  |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                          Storage  (SDNV)                      |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                     Current time  (SDNV)                      |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   Figure 4: Hello TLV Format

   TLV Flags
      The TLV Flags field contains a three bit Hello Function (HF)
      number that specifies one of two functions for the Hello TLV. The
      encoding of the Hello Function is: 

      o HEL: HF = 1 
      o ACK: HF = 2

      The HEL function is used by a node to send metadata needed for the
      dLife operation, namely the storage capacity of the node, its EID,
      current time, and a timer value. 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
 


Moreira, et al.         Expires November 9, 2014               [Page 29]

Internet-Draft                   dLife                       May 8, 2014


         Sender EID field in octets. If the EID has already been sent at
         least once in a message, a node MAY choose to set this field to
         zero, omitting the Sender EID from the Hello TLV. The EID
         Length is encoded as an SDNV and the field is thus of variable
         length.

      Sender EID 
         The Sender EID field specifies the EID of the sender that is to
         be used in updating routing information and making forwarding
         decisions. If a node has multiple EIDs, one should be chosen
         for dLife routing. This field is of variable length.

      Timer 
         The Timer field is used to inform the receiver of the timer
         value used in the Hello processing of the sender. The timer
         specifies the nominal time between periodic Hello messages. It
         is a constant for the duration of a session. The timer field is
         specified in units of 100 ms and is encoded as an SDNV. 

      Storage 
         This field indicates 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.

      Current Time
         This field specifies the current time in the peering node. It
         is given in seconds and counting starts in the year 2000. This
         field is encoded as an SDNV. 



4.3.2. ACK TLV 

   This ACK TLV can be used by itself or nested in Hello TLV.

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | TLV type=0x02 |     Flags     |       TLV Length (SDNV)       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                             ACK Data                          |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   Figure 5: ACK TLV Format

   TLV Flags 
      The TLV Flags field carries an identifier for the ACK TLV type as
 


Moreira, et al.         Expires November 9, 2014               [Page 30]

Internet-Draft                   dLife                       May 8, 2014


      an 8-bit unsigned integer encoded in network bit order. A range of
      values is available for private and experimental use in addition
      to the values defined here. The following ACK TLV types are
      defined:

      o Break ACK 0x00
         Used when a node wants to break the connection due to the fact
         that the neighbor has a storage capacity lower that its
         threshold to send bundles.

      o Social ACK 0x01
         Reports on the reception of Social TLVs (SWNI, bundleList, and
         ackedBundleList).

      o EID ACK (identifier/EID discrepancy) 0x02
         Reports on the identifier/EID discrepancy error as mentioned in
         Section 3.2.1.

      o EID ACK (unknown EID) 0x03
         Reports on the unknown EID error as mentioned in Section 3.2.1.

      o Reserved 0x04 - 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 ACK Type is defined as follows:

      Break ACK
         This field is set to zero.

      Social ACK
         This field is set to zero.

      EID ACK (identifier/EID discrepancy)
         String ID causing the discrepancy and the EID string that
         differs the previous value.

      EID ACK (unknown EID)
         String ID not found in the dictionary.

4.3.3. EID Dictionary TLV

   The EID Dictionary TLV includes the list of EIDs used in making
   routing decisions and is a shared resource (cf. Section 3.2.1) built
   in each of the paired peers. The dictionary can be updated as more
   EID Dictionary TLVs are received.
 


Moreira, et al.         Expires November 9, 2014               [Page 31]

Internet-Draft                   dLife                       May 8, 2014


    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | TLV type=0xA0 |    Reserved   |       TLV Length (SDNV)       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                    String/EID Count (SDNV)                    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                                                               |
   ~           Variable Length Routing Address Strings             ~
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                   Routing Address String 1                    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |        String ID 1 (SDNV)     |         Length (SDNV)         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |            Endpoint Identifier 1 (variable length)            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   ~                               ...                             ~   
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                   Routing Address String n                    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |        String ID n (SDNV)     |         Length (SDNV)         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |            Endpoint Identifier n (variable length)            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   Figure 6: EID Dictionary TLV Format

   Reserved
      8 unused and reserved bits, which were included to allow future
      extension of the protocol

   TLV Data
      String/EID Count 
         Number of strings corresponding to the nodes' EIDs the sender
         node has encountered so far. Encoded as SDNV.

      String ID n 
         SDNV identifier that is constant for the duration of a session.
         String ID zero is predefined as the node initiating the session
         through sending the Hello message, and String ID one is
         predefined as the node responding with the Hello ACK message.
         These entries do not need to be sent explicitly as the EIDs are
         exchanged during the Hello procedure.

         In order to ensure that the String IDs originated by the two
         peers do not conflict, the String IDs generated in the node
         that sent the Hello HEL message MUST have their least
 


Moreira, et al.         Expires November 9, 2014               [Page 32]

Internet-Draft                   dLife                       May 8, 2014


         significant bit set to 0 (i.e., are even numbers) and the
         String IDs generated in the node that responded with the Hello
         ACK message must have their least significant bit set to 1
         (i.e., they are odd numbers).

      Length 
         Length of Endpoint Identifier in this entry. Encoded as SDNV.

      Endpoint Identifier n
         Text string representing the Endpoint Identifier. Note that it
         is NOT null terminated as the entry contains the length of the
         identifier.

4.3.4. Social TLV

   This TLV provides the SWNI, bundleList, and ackedBundleList
   information, i.e., a list of the nodes that the peer node has
   encountered up to that moment along with its social weight towards
   them, the importance of the peer node, as well as the lists
   containing bundles being carried by the peering node and
   acknowledgements for already delivered bundles (limited to the latest
   BUNDLE_DELIVERED number of bundles). This TLV allows dLife nodes to
   choose the bundles to be sent according to the forwarding strategies
   explained in Section 2.3.
























 


Moreira, et al.         Expires November 9, 2014               [Page 33]

Internet-Draft                   dLife                       May 8, 2014


    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | TLV type=0xA1 |      Flags    |        TLV Length (SDNV)      |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                       Importance Value                        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                   SWNI String Count (SDNV)                    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |       String ID 1 (SDNV)      |           Reserved            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                           SW value 1                          |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   ~                               ...                             ~   
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |       String ID n (SDNV)      |           Reserved            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                           SW value n                          |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                   Carried Bundle Count (SDNV)                 |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                     Carried Bundle ID 1                       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                      Dest String  ID 1                        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   ~                               ...                             ~   
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                     Carried Bundle ID n                       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                      Dest String  ID n                        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                    Acked Bundle Count (SDNV)                  |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                      Acked Bundle ID 1                        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                      Dest String  ID 1                        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   ~                               ...                             ~   
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                      Acked Bundle ID n                        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                      Dest String  ID n                        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   Figure 7: Social message TLV Format



 


Moreira, et al.         Expires November 9, 2014               [Page 34]

Internet-Draft                   dLife                       May 8, 2014


   TLV Flags 
      The encoding of the Header flag field relates to the capabilities
      of the Source node sending the Social message.

         o Flag 0: More Social TLVs 
         o Flag 1: Reserved
         o Flag 2: Reserved
         o Flag 3: Reserved
         o Flag 4: Reserved
         o Flag 5: Reserved
         o Flag 6: Reserved
         o 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 as a 32-bit
         unsigned integer encoded in network bit order. 

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

      String ID n
         String ID of the endpoint identifier of the encountered node n
         for which this entry specifies the social weight as predefined
         in a dictionary TLV. This field is of variable length. This
         field is followed by 16 unused and reserved bits, which were
         included to allow future extension of the protocol (e.g., use
         of another metric such as contact volume or signal strength to
         improve the forwarding choice). Encoded as SDNV.

      SW value
         Social weight between the peering node and that specific
         encountered node n as a 32-bit unsigned integer encoded in
         network bit order.

      Carried Bundle Count 
         Number of entries regarding the carried bundle information in
         the TLV. Encoded as SDNV.

      Carried Bundle ID n
         Identifier of the bundle n that the sender is currently
         carrying as a 32-bit unsigned integer. 

 


Moreira, et al.         Expires November 9, 2014               [Page 35]

Internet-Draft                   dLife                       May 8, 2014


      Acked Bundle Count 
         Number of entries regarding the acknowledged bundle information
         in the TLV. Encoded as SDNV.

      Acked Bundle ID n
         Identifier of the bundle n that the sender has received
         acknowledgements for as a 32-bit unsigned integer.

      Dest String ID n
         String ID of the endpoint identifier of the destination n for a
         carried or acknowledged bundle. This field is of variable
         length. Encoded as SDNV.

5. Detailed Operation

   This section provides further details about the operation of dLife,
   including state tables. As explained before dLife aims to release any
   assumption about the reliability of the transport protocol, and so
   positive acknowledgements would be necessary to signal successful
   delivery of (sub)messages. In this section, the phrase "send a
   message" should be read as *successful* sending of a message,
   signaled by receipt of the appropriate "Success" response. Hence, the
   state descriptions below do not explicitly mention positive
   acknowledgements, whether they are being sent or not. 

5.1. High Level State Tables

   This section provides the high level state tables for the operation
   of dLife. The next section provides a more detailed view of each part
   of the protocol's operation. The following states are used to define
   the dLife operation:

   SENSING
      This is the state all nodes start in. Nodes remain in this state
      until a new contact opportunity arises. Once the routing agent has
      sensed the presence of a peer, via notification of the lower
      layer, it will start counting the contact duration. The Hello
      procedure will be triggered depending if the peer is a new contact
      or an already encountered peer (as explained in Section 3.1) 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 is handled by creating a
      new thread or process during the transition to the HELLO state,
      which then takes care of the communication with the new peer while
      the parent process remains in state SENSING waiting for other
      peers to communicate with. In the case when the neighbor is no
      longer available (described as 'neighbor gone notification rcvd'
      in the tables below), the thread or process created is destroyed.
 


Moreira, et al.         Expires November 9, 2014               [Page 36]

Internet-Draft                   dLife                       May 8, 2014


   HELLO
      Nodes remain in the HELLO state from when a new contact
      opportunity arises until the Hello procedure is done and nodes are
      connected (which happens when the Hello procedure reaches the
      LINK_UP state as described in Section 5.3 - during this procedure,
      the state LINK_UP and WAIT_HELLO_HEL are used, but are not
      presented here since they are internal to the Hello procedure).
      Once the Hello procedure is done, the node starts the information
      exchange phase and transitions to the EXCHANGE state. If while in
      the HELLO state the node is notified that the neighbor is no
      longer within communication range by the lower layer, it returns
      to the SENSING state and, if appropriate, MAY destroys any
      additional process or thread created to handle the neighbor.

   EXCHANGE 
      With the communication link set, nodes enter the EXCHANGE state in
      which the transmission of dLife metadata between peers is done.
      The node remains in this state as long as Information Exchange
      Phase TLVs (EID Dictionary, Social and ACK) are being exchanged. 

      In the EXCHANGE state both nodes are able to exchange their EID
      dictionaries and SWNI information. With dLife, the exchange of
      information about dictionary, social weight, and node importance
      MAY be carried out independently but concurrently with the
      messages multiplexed on a single bidirectional link, or
      alternatively, the exchanges MAY be carried out partially or
      wholly sequentially if appropriate for the implementation. The
      information exchange process is explained in more detail in
      Section 3.2.

      When a Social TLV is received, the node MUST notify the Bundle
      Agent about the bundles that SHOULD be forwarded to the peer node.
      If the "More Social TLV" flag is set to zero (i.e., no more
      bundles to send), the node returns to the SENSING state. If the
      routing agent is notified by the lower layer that the neighbor is
      no longer in range, the node switches to the SENSING state and, if
      appropriate, MAY destroy any additional process or thread created
      to handle the neighbor.

      If one or more new bundles are received by this node and the TECD
      and TECDi metrics indicate that it would be appropriate to forward
      some or all of the bundles to the connected node(s), the bundles
      SHOULD be immediately transferred to the connected peer(s). As
      mentioned earlier, the lower layer is responsible in notifying the
      routing agent whether peers are still within communication range
      (cf. Section 2.4.2).


 


Moreira, et al.         Expires November 9, 2014               [Page 37]

Internet-Draft                   dLife                       May 8, 2014


      State: SENSING
      +==============================================================+
      | Condition       |             Action             | New State |
      +=================+================================+===========+
      |                 | Start contact duration count   |           |
      +                 +--------------------------------+   HELLO   |
      | New Contact     | Start Hello procedure          |           |
      +                 +--------------------------------+-----------+
      |                 | Keep sensing for more contacts |  SENSING  |
      +-----------------+--------------------------------+-----------+
      | Neighbor gone   |                                |           |
      | notification    |                                |  SENSING  |
      | rcvd            |                                |           |
      +==============================================================+

      State: HELLO
      +==============================================================+
      | Condition       |             Action             | New State |
      +=================+================================+===========+
      | Hello TLV rcvd  |                                |   HELLO   |
      +-----------------+--------------------------------+-----------+
      | Hello procedure |  Start Information             | EXCHANGE  |
      | done            |  Exchange Phase                |           |
      +-----------------+--------------------------------+-----------+
      | Neighbor gone   |                                |           |
      | notification    |                                |  SENSING  |
      | rcvd            |                                |           |
      +==============================================================+

      State: EXCHANGE
      +==============================================================+
      | Condition       |             Action             | New State |
      +=================+================================+===========+
      | On entry        | Send metadata                  | EXCHANGE  |
      +-----------------+--------------------------------+-----------+
      |EID Dict TLV rcvd| Update local EID Dictionary    | EXCHANGE  |
      +-----------------+--------------------------------+-----------+
      | Social TLV rcvd | Inform Bundle Agent            | EXCHANGE  |
      +-----------------+--------------------------------+-----------+
      | More Social TLV |                                |  SENSING  |
      | flag = 0        |                                |           |
      +-----------------+--------------------------------+-----------+
      | New bundle      |                                | EXCHANGE  |
      +-----------------+--------------------------------+-----------+
      | Neighbor gone   |                                |           |
      | notification    |                                |  SENSING  |
      | rcvd            |                                |           |
      +==============================================================+
 


Moreira, et al.         Expires November 9, 2014               [Page 38]

Internet-Draft                   dLife                       May 8, 2014


5.2. High Level Meta-Data Table

   During its operation, dLife makes use of metadata locally stored as a
   consequence of the exchange of Social TLVs, Hello TLVs and local
   operations. The stored metadata is used in the computation of social
   weight towards other nodes by the current node 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 importance (Imp), Average
   Duration (AD_peer) of contacts to peers, social weight to peer
   (w_peer), and last daily sample in the case of failure/shutdown (see
   Section 2.2). Since nodes receive information from neighbors, they
   must also store the peer's EID (EID_peer), importance of that peer
   (Imp_peer), and peer's current time (currTime_peer) (cf. Section
   4.3.1). 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 the node's own EID, storage capacity
   (StoCap), current time (currTime), EID Dictionary (EIDDict), contact
   duration (CD_peer) and total contact time (TCT_peer) for a given
   peer, and Last Encounter (LastEnc_peer). Temporary metadata received
   from peers are storage capacity (StoCap_peer), EID Dictionary
   (EIDDict_peer), and social weight list of that peer towards other
   nodes (SocList_peer).

   In the SENSING state, each node MUST have its own EID, storage
   capacity, and current time 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 metadata 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, StoCap_peer, and currTime_peer) in the metadata
   table. LastEnc_peer is also initialized in the HELLO state and
   receives the time nodes encountered. This variable will tell a node
   if the social information to be exchanged is up-to-date.

   When the EXCHANGE state starts, a node will receive from its peer its
   EIDDict_peer, SocList_peer, and Imp_peer, which must be stored for
   later deciding in bundle forwarding.



 


Moreira, et al.         Expires November 9, 2014               [Page 39]

Internet-Draft                   dLife                       May 8, 2014


   +------------------------+---------+----------+
   | EID_own | StoCap | Imp | EIDDict | currTime |
   +------------------------+---------+----------+
   | |
   | +----------+---------+----------+---------+--------+--------------+
   | | EID_peer | CD_peer | TCT_peer | AD_peer | w_peer | LastEnc_peer |
   | +----------+---------+----------+---------+--------+--------------+
   |     |            |                    |
   |     |            +-----+-----+-----+  +------+------+------+
   |     |            | CD1 | ... | CDn |  | AD11 | ...  | AD1i | 
   |     |            +-----+-----+-----+  +------+------+------+
   |     | 
   |     +-----------+------------+--------+-------------+------------+
   |     |StoCap_peer|SocList_peer|Imp_peer|currTime_peer|EIDDict_peer|
   |     +-----------+------------+--------+-------------+------------+
   |
   +--------------------+
   | Bundle n fwd_times |
   +--------------------+

   Figure 8: Meta-data Information

   This metadata varies in size according to the type of information it
   stores:

      o EID and EID_peer are coded as strings of variable size.

      o StoCap and StoCap_peer are coded as int (32 bits).

      o currTime, currTime_peer, and LastEnc_peer are coded as int (32
      bits).

      o Imp, Imp_peer, AD_peer, and w_peer are coded as floats (32
      bits).

      o CD_peer and TCT_peer are coded as long (64 bits).

      o Fwd_times is coded as int (32 bits).

      o EIDDict and EIDDict_peer are coded as a HashMap tuple with
      String ID encoded as SDNV and its equivalent EID of variable
      length (up to 32 bits).

      o SocList_peer is coded as a HashMap tuple with String ID of the
      encountered nodes, encoded as SDNV, and the social weight of the
      peer towards these nodes. 


 


Moreira, et al.         Expires November 9, 2014               [Page 40]

Internet-Draft                   dLife                       May 8, 2014


5.3 Hello Procedure

   The hello procedure consists of the exchange of messages comprising
   the header TLV and a single Hello TLV (see Section 4.3.1) with the HF
   (Hello Function) field set to the specified value (HEL or ACK). 

   The rules and state tables for this procedure are shown below with
   the main states and actions to be taken upon the receipt of the
   required information:

      o Hello HEL messages MUST always be issued first, and SHOULD be
      followed by a Hello ACK.

      o The link between peers is only considered available when the
      LINK_UP state is reached.

      o Hello messages MAY be exchanged concurrently, but also in a
      sequential manner, depending on the nature of the communication
      medium (full- or half-duplex). In the case of the latter, the
      process MUST be completed in one direction prior to initiating in
      the other one.

   Upon a contact, nodes exchange a Hello HEL message. After that, nodes
   will have information about each other's EID, storage capacity, and
   current time. The current time is used to determine in which daily
   sample the peer is in order to facilitate any required updates
   concerning social weights and importances that may have happened
   since last encounter between them. Additionally, a timer value is
   exchanged so nodes know the periodicity of next hello messages in
   order to signal the arrival of the Hello HEL message.

   At this moment, nodes MUST create entries for the peer (EID_peer)
   where the contact duration (CD_peer), total connected time
   (TCT_peer), average duration (AD_peer), social weight (w_peer),
   storage capacity (StoCap_peer), current time (currTime_peer),
   LastEnc_peer (initialized with currTime_peer), social weight list
   (SocList_peer), and the importance (Imp_peer) towards this specific
   peer are going to be maintained and updated. Additionally, a timer
   for receiving the Hello ACK message MUST be started. Up to this
   point, nodes are in the WAIT_HELLO_HEL state.

   A second hello message with the ACK flag MUST be issued to inform
   nodes about the successful reception of the Hello HEL message. If
   Hello ACK message does not arrive within the specified time (Hello
   ACK timeout), the link is assumed lost, nodes are disconnected,
   contact duration count MUST stop and variables SHOULD be saved. After
   this, the start of a new hello procedure is required and the nodes
   remain at the WAIT_HELLO_HEL state.
 


Moreira, et al.         Expires November 9, 2014               [Page 41]

Internet-Draft                   dLife                       May 8, 2014


   The link is assumed active upon the receipt of the Hello ACK message.
   This means nodes are connected and ready to shift to the exchange
   information phase. At this point values should be saved in created
   entries and nodes move to the LINK_UP state.

   Nodes will remain at the LINK_UP state until the routing agent
   receive a notification from the lower layer reporting that the peer
   is no more within communication range (cf. neighbor gone in Section
   2.4.2). At this point nodes MUST stop the contact duration count with
   the value being saved to CD_peer (CD1 ... CDn) variables of each
   disconnected peer.

   State: WAIT_HELLO_HEL
   +===================================================================+
   | Condition      |              Action             |   New State    |
   +================+=================================+================+
   |                | Start timer for                 |                |
   | Hello HEL      | Hello ACK receipt               |                |
   + rcvd           +                                 + WAIT_HELLO_HEL +
   |                | Initialize variables            |                |
   +----------------+---------------------------------+----------------+
   | Hello ACK rcvd | Save variables                  | LINK_UP        |
   +----------------+---------------------------------+----------------+
   |                |                                 |                |
   + Hello ACK      +                                 +                +
   | timeout        | Stop contact duration count     |                |
   +----------------+                                 + WAIT_HELLO_HEL +
   | Neighbor gone  | Save variables                  |                |
   + notification   +                                 +                +
   | rcvd           |                                 |                |
   +================+=================================+================+

   State: LINK_UP
   +===================================================================+
   | Condition      |              Action             |   New State    |
   +================+=================================+================+
   | Neighbor gone  | Stop contact duration count     |                |
   + notification   +                                 + WAIT_HELLO_HEL +
   | rcvd           | Save variables                  |                |
   +================+=================================+================+

5.4 Information Exchange Phase

   After the exchange of hello messages, the nodes are in the LINK_UP
   state, which allows the exchange of information. dLife is
   bidirectional and the information exchange processes between a pair
   of nodes (from A to B and vice-versa) are independent and expected to
   run almost entirely concurrently. This is because EID Dictionaries
 


Moreira, et al.         Expires November 9, 2014               [Page 42]

Internet-Draft                   dLife                       May 8, 2014


   SHOULD be synchronized to allow better performance of the protocol.

   The information exchange phase consists of messages comprising the
   dLife header, and EID Dictionary and Social TLVs (see Sections 4.3.3
   and 4.3.4). The rules and state tables are shown below with the main
   states and actions to be taken upon the receipt of the required
   information.

      o No information SHALL be exchanged prior to the hello procedure.

      o Information messages MAY be exchanged concurrently, but also in
      a sequential manner, depending on the nature of the communication
      medium (full- or half-duplex). In the case of the latter, the
      process MUST be completed in one direction prior to initiating in
      the other one.

   Once in the information exchange phase, as soon as nodes enter the
   WAIT_INFO state, they SHOULD send the EID Dictionary in order to
   synchronize the mapping between their identifiers (String ID) and
   EIDs of nodes they have encountered. As the EID dictionary is
   received, the node will shift to the BUILD_SOCIAL_TLV state and check
   whether or not problems with the mapping are detected. In the case of
   EID errors, an ACK TLV with EID ACK flag MUST be sent to inform the
   peer node about problems (cf. Sections 3.2.1 and 4.3.2) with the
   received identifiers (String ID).

   Still in the WAIT_INFO state, if a node gets a Social TLV, it will
   obtain the SWNI, bundleList, and ackedBundleList information from its
   peer node. With such information, the node will decide which bundles
   SHOULD be exchanged based on the forwarding strategies (cf. Section
   2.3), will update its ackedBundleList, and will inform the Bundle
   Agent (cf. Send Bundle in Section 2.4.1) about the list of bundles
   that SHOULD be forwarded to its peering node.

   The node will remain in the WAIT_INFO state after receiving an Acked
   Bundle Notification (cf. Section 2.4.1), which means that the bundles
   forwarded by the Bundle Agent arrived at the destination node, and
   the sending node can update its ackedBundleList; and also when
   receiving an ACK TLV with the Break ACK flag, which signals that the
   peering node decided to disconnect given its lack of storage
   capacity, and the sending node will stop the contact duration count
   and wait for information coming from other peers. 

   As soon as entering the BUILD_SOCIAL_TLV state, the node MUST build
   and send its Social TLV to the peering node and will remain in this
   state until it receives an ACK TLV with the Social ACK flag. The node
   will shift to the WAIT_INFO state upon the receipt of the Social ACK.

 


Moreira, et al.         Expires November 9, 2014               [Page 43]

Internet-Draft                   dLife                       May 8, 2014


   Since dLife updates SWNI information at every daily sample, this can
   influence in the next forwarding decisions. Thus, the node should
   report such updates to its peering node and shift to the
   BUILD_SOCIAL_TLV state.

   Independently of the state the node finds itself, if receiving a
   notification from the lower layer reporting that the peer is no
   longer within communication range (cf. neighbor gone in Section
   2.4.2), it MUST stop the contact duration count and wait for
   information coming from other peers.

   State: WAIT_INFO
   +===================================================================+
   | Condition      |            Action            |   New State       |
   +================+==============================+===================+
   | On entry       | Send EID Dictionary TLV      | WAIT_INFO         |
   +----------------+------------------------------+-------------------+
   | EID Dictionary | Check identifier/EID mapping | BUILD_SOCIAL_TLV  |
   | rcvd           |                              |                   |
   +----------------+------------------------------+-------------------+
   | EID error      | Report problem               | BUILD_SOCIAL_TLV  |
   |                | ACK TLV flag EID ACK         |                   |
   +----------------+------------------------------+-------------------+
   |                | Get SWNI, bundleList         |                   |
   |                | and ackedBundleList          |                   |
   | Social TLV     | information                  | WAIT_INFO         |
   + rcvd           +------------------------------+                   +
   |                | Update ackedBundleList       |                   |
   +                +------------------------------+                   +
   |                | Inform Bundle Agent          |                   |
   |                | (Send Bundle)                |                   |
   +----------------+------------------------------+-------------------+
   | Acked Bundle   |                              |                   |
   | Notification   | Update ackedBundleList       | WAIT_INFO         |
   | rcvd           |                              |                   |
   +----------------+------------------------------+-------------------+
   | Break ACK      | Disconnect                   | WAIT_INFO         |
   + rcvd           +------------------------------+                   +
   |                | Stop contact duration count  |                   |
   +----------------+------------------------------+-------------------+
   | SWNI updated   | Report peer                  | BUILD_SOCIAL_TLV  |
   +----------------+------------------------------+-------------------+
   | Neighbor gone  |                              |                   |
   | notification   | Stop contact duration count  | WAIT_INFO         |
   | rcvd           |                              |                   |
   +================+==============================+===================+


 


Moreira, et al.         Expires November 9, 2014               [Page 44]

Internet-Draft                   dLife                       May 8, 2014


   State: BUILD_SOCIAL_TLV
   +===================================================================+
   | Condition      |            Action            |   New State       |
   +================+==============================+===================+
   | On entry       | Build and send Social TLV    | BUILD_SOCIAL_TLV  |
   +----------------+------------------------------+-------------------+
   | Social ACK     |                              | WAIT_INFO         |
   | rcvd           |                              |                   |
   +----------------+------------------------------+-------------------+
   | Neighbor gone  |                              |                   |
   | notification   | Stop contact duration count  | WAIT_INFO         |
   | rcvd           |                              |                   |
   +================+==============================+===================+

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

 


Moreira, et al.         Expires November 9, 2014               [Page 45]

Internet-Draft                   dLife                       May 8, 2014


   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 be forwarded.

7. Implementation Experience

   The initial implementation of dLife is written in Java for the
   version 1.4.1 of the Opportunistic Network Emulator (ONE), named
   Dlife.java [Moreira12a], which implements the RoutingDecisionEngine
   interface to be used with the DecisionEngineRouter class. This
   implementation, which can be downloaded from the ONE web site,
   contains all the major mechanisms described in this document to
   ensure proper protocol operation. There are however some parts that
 


Moreira, et al.         Expires November 9, 2014               [Page 46]

Internet-Draft                   dLife                       May 8, 2014


   are only specified, such as the queuing policies, and others 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 was to enable dLife to be
   tested in different scalable large pervasive scenarios (some based on
   real traces such as the one from Cambridge University) with other
   protocols: PRoPHET and Bubble Rap. The three key performance
   indicators that were studied were average message delay, probability
   of message delivery and protocol cost (number of duplicate messages
   in the network at the time of delivery). Experience and feedback from
   the implementers on early versions of the protocol have been
   incorporated into the current version.

   A second implementation of dLife was done in Java using the Android
   API development. The class responsible for routing is known as
   dLifeRouter.java. This implementation follows a modular design to
   allow operation over multiple platforms. For that, a dLife library is
   being developed in Java (version 1.6+). This library comprises
   different classes that in turn include the components, messages,
   interfaces, and functionalities specified in this draft. The
   implemented classes are:

   The SocialInformation class 
      Comprises the SIG, SW, and IA components which are responsible for
      keeping track of the different contact between devices, computing
      the social weight among them, and determining their importance. 

   The DlifeNeighbor class 
      Include peer-specific information (e.g., EID_peer, Imp_peer,
      SocList_peer).

   The DlifeTLV class 
      Provides all TLVs and methods used by dLife to create and
      interpret such TLVs. 

   The main class (dLifeRouter)
      Includes the DM component that works along with other classes
      (i.e., components) based on the exchanged metadata and computed
      information to take routing decisions. 

   The dLifeRouter class includes the interfaces to the DTN
   architecture/Bundle Agent (e.g., get bundle list, send bundle) and to
   the Bluetooth Convergence Layer (e.g., neighbor sensing). The
   implementation of the Bundle Agent, Bluetooth Convergence Layer and
   dLife are presented as an Opportunistic Networking Module to the DTN
   architecture.

 


Moreira, et al.         Expires November 9, 2014               [Page 47]

Internet-Draft                   dLife                       May 8, 2014


   The DTN architecture/Bundle Agent class was implemented based on RFCs
   4838 and 5050. At the time of this work, available implementations
   for Linux and Android devices such as DTN2, IBR-DTN and Bytewalla
   were studied to obtain enough implementation background. This class
   provides nodes with DTN core functionality, direct wireless
   communication, generic routing capabilities, and secure
   communications. Generic routing functionalities are provided by the
   implementation of a generic routing class, GenericRouting, which was
   extended to represent the dLife protocol. Secure communications are
   supported by the implementation of a security layer, BundleSecurity,
   implemented according to RFC 6257 - Bundle security Protocol
   Specification.

   To allow direct wireless communication a common communication medium,
   the Bluetooth Convergence Layer (BCL), was created and implemented
   allowing direct exchange of bundles through the Bluetooth interface
   without the need of a structured WiFi network. The BCL class, which
   is not present in the available DTN architecture implementations, was
   implemented as general as possible to allow the interfacing between
   the Bundle Agent and the communication medium regardless of the used
   routing protocol and operational system running on the the devices.
   However, the current implementation was first developed for Android
   devices and thus the BCL takes advantages of some native Bluetooth
   functionality already implemented in this platform, such as the
   discovery of neighbors and the possibility of storing information
   about them. The implemented BCL (BluetoothConvergenceLayer.java)
   includes the Service Discovery Protocol (SDP) for sensing the medium
   and the Serial Port Profile (SPP) for data exchange. The BCL class
   uses the RFCOMM as transport protocol and runs on top on the Logical
   Link Control and Adaptation Protocol (L2CAP), which interfaces with
   the Host Controller Interface (HCI). Additionally, the BCL provides a
   simple reliable data stream and supports multiple connections as this
   is expected to happen in the real world. 

   At the moment the Opportunistic Networking Module is partially
   functional on Android 2.3.6 Gingerbread (kernel version 2.6.35.7)
   devices, which are able to exchange information through their
   Bluetooth interfaces based on the current dLife specification.
   Currently, devices can only manage one simultaneous Bluetooth
   connection. Actually the code is under revision to be improved in
   order to support multiple connections, as this is a common situation
   in urban scenarios. Version 1.0 of the Opportunistic Networking
   Module for Android devices will be made available for download once
   concluded.

8. Deployment Experience

   In order perform implementation tests of the dLife protocol, a DTN
 


Moreira, et al.         Expires November 9, 2014               [Page 48]

Internet-Draft                   dLife                       May 8, 2014


   testbed was created in the context of the DTN-Amazon project, having
   COPELABS/University Lusofona and Federal University of Para as
   current partners. The testbed has currently 10 devices (3 personal
   computers with Ubuntu 10.10 Maverick, 3 smartphones Android 2.3.6
   Gingerbread, 4 wireless routers with OpenWrt 10.03.1). 

   The testbed was initially used to test three 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;
   Bytewalla (version 3, since version 5 was not yet fully functional
   with sporadic crashes). 

   This initial set of tests aimed to identify which implementation
   could be adopted in the DTN-Amazon project. 

   Both IBR-DTN and DTN2 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 testbed); and ii) the DTN-Amazon
   Android security application for surveillance of university campus
   over Epidemic and PRoPHET routing (DTN2).

   Bytewalla was also deployed to allow the understanding of its
   functionalities. It was installed in Android devices with
   communication taking place through a wireless router, which could not
   interpret bundles and was only used to relay information.

   Additionally, The DTN2 implementation was also used to analyze the
   behavior of a network environment with mobility, while the mule
   (wireless router) were carried by a vehicle to enable the exchange of
   information between two hosts. 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.

   As the idea was to exploit physical proximity (key aspect of dLife to
   determine different levels of social interaction among devices)
   between DTN-Amazon nodes, this initial set of tests showed that none
   of these available implementations were enough for the scenario of
   the project. Thus, they were studied to provide enough implementation
   knowledge to the project's designers resulting in the Opportunistic
   Networking Module.

   For a proof of concept, initial deployment tests of the stable dLife
   implementation over the Opportunistic Networking Module were carried
   out based on seven Android devices carried by students during their
   daily routine activities in the Federal University of Para campus for
 


Moreira, et al.         Expires November 9, 2014               [Page 49]

Internet-Draft                   dLife                       May 8, 2014


   five days. A traffic generator was installed in each device to create
   a load of 6 messages/hour, towards the other six nodes used in the
   experience. Node storage was defined at 10MB and message size varied
   between 1KB and 1MB. 

   These tests aimed to: i)evaluate the BCL implementation and generate
   the first contact traces based on it; and ii) test the behavior of
   dLife in terms of calculating the social weights between nodes and
   their importances.

   Currently, the Opportunistic Networking Module is being finetuned and
   the next set of tests will analyze the performance of the dLife, when
   compared to behavior of other social-oblivious opportunistic routing
   solutions such as Epidemic and PROPHET, based on the following
   metrics: average message delay, probability of message delivery and
   the number of duplicate messages in the network at the time of
   delivery.

10.  References

10.1  Normative References

   [Moreira12a] W. Moreira, P. Mendes, and S. Sargento, "Opportunistic
              Routing Based on Daily Routines," in Proceedings of the
              Sixth IEEE WoWMoM Workshop on Autonomic and Opportunistic
              Communications (AOC 2012), (San Francisco, California,
              USA), June, 2012.

   [Moreira12b] W. Moreira, M. de Souza, P. Mendes, and S. Sargento,
              "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] S. Bradner, "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119, March 1997.

   [RFC4838] V. Cerf, S. Burleigh, A. Hooke, L. Torgerson, R. Durst, K.
              Scott, K. Fall, and H. Weiss, "Delay-Tolerant Networking
              Architecture", RFC 4838, April 2007.

   [RFC5050] K. Scott and S. Burleigh, "Bundle Protocol Specification",
              RFC 5050, November 2007.

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


Moreira, et al.         Expires November 9, 2014               [Page 50]

Internet-Draft                   dLife                       May 8, 2014


              opportunistic forwarding algorithms," in Proceedings of
              INFOCOM, (Barcelona, Spain), April, 2006. 

   [Costa08] P. Costa, C. Mascolo, M. Musolesi, and G. P. Picco,
              "Socially-aware routing for publish-subscribe in delay-
              tolerant mobile ad hoc networks," Selected Areas in
              Communications, IEEE Journal on, vol. 26, pp. 748- 760,
              June, 2008.

   [Daly07] E. M. Daly and M. Haahr, "Social network analysis for
              routing in disconnected delay-tolerant manets," in
              Proceedings of ACM MobiHoc, (Montreal, Canada), September,
              2007.

   [Eagle09] N. Eagle and A. Pentland, "Eigenbehaviors: identifying
              structure in routine," Behavioral Ecology and
              Sociobiology, vol. 63, pp. 1057-1066, May, 2009. 

   [Hossmann10] T. Hossmann, T. Spyropoulos, and F. Legendre, "Know thy
              neighbor: Towards optimal mapping of contacts to social
              graphs for dtn routing," in Proceedings of IEEE INFOCOM,
              (San Diego, USA), March, 2010. 

   [Hui07] P. Hui and J. Crowcroft, "How small labels create big
              improvements," in Proceedings of IEEE PERCOM Workshops,
              (White Plains, USA), March, 2007.

   [Hui11] P. Hui, J. Crowcroft, and E. Yoneki, "Bubble rap: social-
              based forward- ing in delay tolerant networks," Mobile
              Computing, IEEE Transactions on, vol. 10, pp. 1576-1589,
              November, 2011.

   [I-D.irtf-dtnrg-tcp-clayer] M. Demmer 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 and 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] A. Lindgren and K. Phanse, "Evaluation of Queueing
 


Moreira, et al.         Expires November 9, 2014               [Page 51]

Internet-Draft                   dLife                       May 8, 2014


              Policies and Forwarding Strategies for Routing in
              Intermittently Connected Networks", Proceedings of
              COMSWARE 2006 , January 2006.

   [Moreira13] W. Moreira and P. Mendes, "Social-aware Opportunistic
              Routing: The New Trend." In: Woungang, I, Dhurandher, S.,
              Anpalagan, A., Vasilakos, A. V. (Eds.), Routing in
              Opportunistic Networks, Springer Verlag, June, 2013.

   [Moreira_12c] W. Moreira, P. Mendes, and S. 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] S. Symington, S. Farrell, H. Weiss, and P. Lovell, "Bundle
              Security Protocol Specification", RFC 6257, May 2011.

   [Song07] L. Song and D. F. Kotz, "Evaluating opportunistic routing
              protocols with large realistic contact traces," in
              Proceedings of ACM MobiCom CHANTS, (Montreal, Canada),
              September, 2007.

   [Vahdat00] A. Vahdat and D. Becker, "Epidemic Routing for Partially
              Connected Ad Hoc Networks", Duke University Technical
              Report CS-200006, April 2000.


Authors' Addresses

   Waldir Moreira
   COPELABS, Universidade Lusofona
   Campo Grande, 376
   1749-024 Lisboa
   Portugal 
   Phone: 
   Email: waldir.junior@ulusofona.pt
   URI: http://siti2.ulusofona.pt/~wjunior

   Paulo Mendes
   COPELABS, Universidade Lusofona
 


Moreira, et al.         Expires November 9, 2014               [Page 52]

Internet-Draft                   dLife                       May 8, 2014


   Campo Grande, 376
   1749-024 Lisboa
   Portugal 
   Phone: 
   Email: paulo.mendes@ulusofona.pt
   URI: http://siti.ulusofona.pt/~pmendes 

   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 November 9, 2014               [Page 53]