idnits 2.17.1 draft-moreira-dlife-04.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) == There are 1 instance of lines with non-RFC6890-compliant IPv4 addresses in the document. If these are example addresses, they should be changed. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (May 8, 2014) is 3641 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Unused Reference: 'I-D.irtf-dtnrg-tcp-clayer' is defined on line 2379, but no explicit reference was found in the text == Unused Reference: 'Lindgren06' is defined on line 2394, but no explicit reference was found in the text == Unused Reference: 'RFC6257' is defined on line 2417, but no explicit reference was found in the text == Unused Reference: 'Vahdat00' is defined on line 2425, but no explicit reference was found in the text -- Possible downref: Non-RFC (?) normative reference: ref. 'Moreira12a' -- Possible downref: Non-RFC (?) normative reference: ref. 'Moreira12b' ** Downref: Normative reference to an Informational RFC: RFC 4838 ** Downref: Normative reference to an Experimental RFC: RFC 5050 == Outdated reference: A later version (-09) exists of draft-irtf-dtnrg-tcp-clayer-02 Summary: 3 errors (**), 0 flaws (~~), 8 warnings (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 DTN Research Group W. Moreira 3 Internet-Draft P. Mendes 4 Expires: November 9, 2014 COPELABS, Universidade Lusofona 5 E. Cerqueira 6 ITEC, Universidade Federal do Para 7 May 8, 2014 9 Opportunistic Routing based on Users Daily Life Routine 10 draft-moreira-dlife-04 12 Abstract 14 This document is written in the context of the Delay Tolerant 15 Networking Research Group and will be presented for reviewing by that 16 group. This document defines dLife, an opportunistic routing protocol 17 that takes advantage of time-evolving social structures. dLife 18 belongs to the family of social-aware opportunistic routing protocols 19 for intermittently connected networks. dLife operates based on a 20 representation of the dynamics of social structures as a weighted 21 contact graph, where the weights (i.e., social strengths) express how 22 long a pair of nodes is in contact over different periods of time. It 23 considers two complementary utility functions: Time-Evolving Contact 24 Duration (TECD) that captures the evolution of social interaction 25 among pairs of users in the same daily period of time, over 26 consecutive days; and TECD Importance (TECDi) that captures the 27 evolution of user's importance, based on its node degree and the 28 social strength towards its neighbors, in different periods of time. 29 It is intended for use in wireless networks where there is no 30 guarantee that a fully connected path between any source - 31 destination pair exists at any time, a scenario where traditional 32 routing protocols are unable to deliver bundles. Such networks can be 33 sparse mesh, in which case intermittent connectivity is due to lack 34 of physical connections, or dense mesh, in which case intermittent 35 connectivity may be due to high interference or shadowing. In any 36 case, intermittent connectivity can also be due to the availability 37 of devices (e.g., unavailable due to power saving rules). The 38 document presents an architectural overview followed by the protocol 39 specification. 41 Status of this Memo 43 This Internet-Draft is submitted to IETF in full conformance with the 44 provisions of BCP 78 and BCP 79. 46 Internet-Drafts are working documents of the Internet Engineering 47 Task Force (IETF). Note that other groups may also distribute 48 working documents as Internet-Drafts. The list of current Internet- 49 Drafts is at http://datatracker.ietf.org/drafts/current/. 51 Internet-Drafts are draft documents valid for a maximum of six months 52 and may be updated, replaced, or obsoleted by other documents at any 53 time. It is inappropriate to use Internet-Drafts as reference 54 material or to cite them other than as "work in progress." 56 This Internet-Draft will expire on November 9, 2014. 58 Copyright and License Notice 60 Copyright (c) 2014 IETF Trust and the persons identified as the 61 document authors. All rights reserved. 63 This document is subject to BCP 78 and the IETF Trust's Legal 64 Provisions Relating to IETF Documents 65 (http://trustee.ietf.org/license-info) in effect on the date of 66 publication of this document. Please review these documents 67 carefully, as they describe your rights and restrictions with respect 68 to this document. Code Components extracted from this document must 69 include Simplified BSD License text as described in Section 4.e of 70 the Trust Legal Provisions and are provided without warranty as 71 described in the Simplified BSD License. 73 Table of Contents 75 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 76 1.1. Applicability of the Protocol . . . . . . . . . . . . . . . 5 77 1.1.1. Protocol Stack . . . . . . . . . . . . . . . . . . . . 5 78 1.1.2. Applicability scenarios . . . . . . . . . . . . . . . . 6 79 1.1.2.1. Urban Areas Networks . . . . . . . . . . . . . . . 6 80 1.1.2.2. Mission-critical Networks . . . . . . . . . . . . . 7 81 1.2. Relation with the DTN Architecture and Networking Model . . 7 82 1.3. Differentiation to other Opportunistic Routing Proposal . . 9 83 1.4. Requirements notation . . . . . . . . . . . . . . . . . . . 10 84 2. Node Architecture . . . . . . . . . . . . . . . . . . . . . . . 10 85 2.1. dLife Components . . . . . . . . . . . . . . . . . . . . . 11 86 2.2. Routing Algorithm . . . . . . . . . . . . . . . . . . . . . 12 87 2.2.1. Time-Evolving Contact Duration (TECD) . . . . . . . . . 14 88 2.2.2. TECD Importance (TECDi) . . . . . . . . . . . . . . . . 15 89 2.3. Forwarding strategy . . . . . . . . . . . . . . . . . . . . 15 90 2.3.1. Basic Strategy . . . . . . . . . . . . . . . . . . . . 15 91 2.3.2. Prioritized Strategy . . . . . . . . . . . . . . . . . 16 92 2.4. Interfaces . . . . . . . . . . . . . . . . . . . . . . . . 16 93 2.4.1. Bundle Agent . . . . . . . . . . . . . . . . . . . . . 16 94 2.4.2. Lower Layers and Interface . . . . . . . . . . . . . . 17 95 3. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . . 18 96 3.1. Neighbor Sensing Phase . . . . . . . . . . . . . . . . . . 18 97 3.2. Information Exchange Phase . . . . . . . . . . . . . . . . 20 98 3.2.1. EID Dictionary . . . . . . . . . . . . . . . . . . . . 21 99 3.2.2. Operation in the presence of multiples neighbors . . . 22 100 3.3. Bundle Reception Policies . . . . . . . . . . . . . . . . . 22 101 3.3.1. Queueing policy . . . . . . . . . . . . . . . . . . . . 22 102 3.3.2. Custody Policy . . . . . . . . . . . . . . . . . . . . 23 103 3.3.3. Destination Policy . . . . . . . . . . . . . . . . . . 24 104 4. Message Formats . . . . . . . . . . . . . . . . . . . . . . . . 24 105 4.1. Header . . . . . . . . . . . . . . . . . . . . . . . . . . 25 106 4.2. TLV Structure . . . . . . . . . . . . . . . . . . . . . . . 28 107 4.3. TLVs . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 108 4.3.1. Hello TLV . . . . . . . . . . . . . . . . . . . . . . . 29 109 4.3.2. ACK TLV . . . . . . . . . . . . . . . . . . . . . . . . 30 110 4.3.3. EID Dictionary TLV . . . . . . . . . . . . . . . . . . 31 111 4.3.4. Social TLV . . . . . . . . . . . . . . . . . . . . . . 33 112 5. Detailed Operation . . . . . . . . . . . . . . . . . . . . . . 36 113 5.1. High Level State Tables . . . . . . . . . . . . . . . . . . 36 114 5.2. High Level Meta-Data Table . . . . . . . . . . . . . . . . 39 115 5.3 Hello Procedure . . . . . . . . . . . . . . . . . . . . . . 41 116 5.4 Information Exchange Phase . . . . . . . . . . . . . . . . . 42 117 6. Security Considerations . . . . . . . . . . . . . . . . . . . . 45 118 7. Implementation Experience . . . . . . . . . . . . . . . . . . . 46 119 8. Deployment Experience . . . . . . . . . . . . . . . . . . . . . 48 120 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 50 121 10.1 Normative References . . . . . . . . . . . . . . . . . . . 50 122 10.2 Informative References . . . . . . . . . . . . . . . . . . 50 123 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 52 125 1. Introduction 127 The pervasive deployment of wireless personal devices is creating the 128 opportunity for the development of novel applications. The 129 exploitation of such applications with a good performance-cost 130 tradeoff is possible by allowing devices to use free spectrum to 131 exchange data whenever they are within wireless range, specially in 132 scenarios where it is difficult to find an end-to-end path between 133 any pair of nodes at any moment. In such scenarios, every contact is 134 an opportunity to forward data. Hence, there is the need to develop 135 networking solutions able to buffer messages at intermediate nodes 136 for a longer time than normally occurs in the queues of conventional 137 routers (cf. Delay-Tolerant Networking [RFC4838]), and routing 138 algorithms able to bring such messages close to a destination, with 139 high probability, low delay, and reduced associated costs. 141 Most of the proposed routing solutions focus on inter-contact times 142 alone [Chaintreau06], while there is still significant investigation 143 to understand the nature of such statistics (e.g., power-law, 144 behavior dependent on node context). Moreover, the major drawback of 145 such approaches is the instability of the created proximity graphs 146 [Hui11], which changes with users' mobility. 148 A trend is investigating the impact that more stable social 149 structures (inferred from the social nature of human mobility) have 150 on opportunistic routing [Hui11], [Daly07]. Such social structures 151 are created based on social similarity metrics that allow the 152 identification of the centrality that nodes have in a 153 cluster/community. This allows forwarders to use the identified hub 154 nodes to increase the probability of delivering messages inside 155 (local centrality) or outside (global centrality) a community, based 156 on the assumption that the probability of nodes to meet each other is 157 proportional to the strength of their social connection. 159 A major limitation of approaches that identify social structures, 160 such as communities, is the lack of consideration about the dynamics 161 of networks, which refers to the evolving structure of the network 162 itself, the making and braking of network ties: over a day, a user 163 meets different people at every moment. Thus, the user's personal 164 network changes, and so does the global structure of the social 165 network to which he/she belongs. 167 When considering dynamic social similarity, it is imperative to 168 accurately represent the actual daily interaction among users: it has 169 been shown [Hossmann10] that social interactions extracted from 170 proximity graphs must be mapped into a cleaner social connectivity 171 representation (i.e., comprising only stable social contacts) to 172 improve forwarding. This motivates us to specify a routing protocol 173 aware of the network dynamics, represented by users' daily life 174 routine. We focus on the representation of daily routines, since 175 routines can be used to identify future interaction among users 176 sharing similar movement patterns, interests, and communities 177 [Eagle09]. 179 Existing proposals [Costa08], [Hui11], [Daly07] succeed in 180 identifying similarities (e.g., interests) among users, but their 181 performance is affected as dynamism derived from users' daily 182 routines is not considered. To address this challenge, we propose 183 dLife that uses time-evolving social structures to reflect the 184 different behavior that users have in different daily periods of 185 time: dLife represents the dynamics of social structures as a 186 weighted contact graph, where the weights (i.e., social strengths) 187 express how long a pair of nodes is in contact over different periods 188 of time. 190 dLife considers two complementary utility functions: Time-Evolving 191 Contact Duration (TECD) that captures the evolution of social 192 interaction among pairs of users in the same daily period of time, 193 over consecutive days; and TECD Importance (TECDi) that captures the 194 evolution of user's importance, based on its node degree and the 195 social strength towards its neighbors, in different periods of time. 197 1.1. Applicability of the Protocol 199 This section describes the applicability of the dLife protocol in 200 terms of the networking protocol stack and in terms of the usage 201 scenarios that are representative of the daily life experience of 202 most people. The latter aims to check which are the communication 203 challenges that can be mitigated by deploying a delay-tolerant 204 routing protocol. The focus goes to scenarios involving mission- 205 critical environments that represent sporadic situations that require 206 a spontaneous and efficient exchange of information, as well as 207 communications in urban environments, which can also benefit from the 208 existence of a DTN approach. 210 This document does not focus on scenarios such as space networks and 211 rural area networks, since space networks rely on the usage of single 212 links with extreme long delay, while most of the potential rural area 213 scenarios will require a store-and-carry system (ferry type) and not 214 so much a store-carry-forward system. 216 1.1.1. Protocol Stack 218 The dLife protocol is expected to interact with the Bundle Protocol 219 agent for retrieving information about available bundles and for 220 requesting bundles to be sent to another node (cf. Section 2.4.1). It 221 is expected that the associated bundle agents are then able to 222 establish a link, over the TCP convergence layer [I-D.irtf-dtnrg-tcp- 223 clayer]) or the UDP convergence layer [I-D.irtf-dtnrg-udp-clayer]) to 224 perform this bundle transfer. 226 In what concerns information needed for its operation, dLife does not 227 impose any requirements for data reliability transfer to avoid 228 restricting its applicability. Hence, data exchange may take place 229 over transport protocols that do not provide neither message 230 segmentation or reliability, nor in order delivery. Hence, dLife 231 provides itself the capability to segment protocol messages into 232 submessages. Submessages are provided with sequence numbers, and 233 this, together with the capability for positive acknowledgements 234 allows dLife to operate over an unreliable protocol such as UDP or 235 potentially directly over IP. As said for the bundle agent, the 236 communication medium used to send dLife messages can include 237 different technologies such as Bluetooth and Wi-Fi. 239 Moreover, dLife expects to be able to use bidirectional links for 240 information exchange; this allows information exchange to take place 241 in both directions over the same link, avoiding the need to establish 242 a second link for information exchange in the reverse direction. 244 1.1.2. Applicability scenarios 246 The identified scenarios aim to illustrate the applicability of dLife 247 in real scenarios. In technical terms, dLife aims to target networks 248 where we may not find any end-to-end path between any pair of nodes 249 at some moment in time. The lack of end-to-end path may be due to 250 node mobility and availability (e.g., switching off radios), aspects 251 that create connectivity patterns that are correlated with the daily 252 habits of citizens. Human behavior patterns (often containing daily 253 or weekly periodic activities) provide one example where dLife is 254 expected to be applicable, independently of the type of personal 255 device: it can be of explicit usage (e.g., smartphones) or of 256 implicit usage (e.g., embedded devices). 258 Scientific results [Moreira12a] [Moreira12b] show that dLife is able 259 to benefit from the predictability of human behavior in daily periods 260 of time even in the presence of few contacts. However, the behavior 261 predictability can be estimated more accurately with a higher number 262 of events. 264 1.1.2.1. Urban Areas Networks 266 This seems to be the most challenging scenario to analyze the 267 applicability of DTN employing dLife as the store-carry-forward 268 routing protocol. A study of DTN routing for urban scenarios may 269 bring a coherent understanding about the advantages and challenges of 270 using a DTN system in the daily life of millions of people. A study 271 of the applicability of DTN routing in urban scenarios may benefit 272 from a good understanding of the per-person bit density (available 273 capacity per second/hour/day) in a major metropolitan area. 275 In a urban area, there are several examples of networking scenarios 276 that can gain from the applicability of dLife, such as: Urban "dark" 277 places due to high mobility (e.g., fast trains), indoors (e.g., 278 subway systems, in-building) and outdoor (e.g., areas with closed 279 APs, areas with significant interference); Off-load of cellular 280 networks, since cellular operators do not like to have data traffic 281 unrelated to services provided in their networks; The cost of 282 cellular wireless data, which decreases the relation quality/price of 283 cellular data communications; Networks of embedded objects, which 284 will require delay-tolerant communications over short-distance 285 wireless interfaces and not over cellular ones. 287 1.1.2.2. Mission-critical Networks 289 At any point, natural catastrophes can happen and such type of 290 network can be deployed in order to facilitate rescue and medical 291 operations. Another type of situation that a mission-critical network 292 may be formed is in hostile environment such as war scenarios. 293 Independently of the scenario for its application, this type of 294 networks must be readily available through any sort of Wi-Fi enabled 295 equipment (PDAs, cell phones, laptops, APs) which are expected to 296 cooperate with the aim of helping the dissemination of information. 297 Information must reach the interested parties as quickly as possible 298 to achieve fast results for the actions being taken. 300 In mission-critical networks, there are several examples of 301 networking scenarios that can gain from the applicability of dLife, 302 such as: Disaster networks where no (maybe very few) infrastructure 303 is available since it may have been destroyed; Military networks, 304 where communications can be established using devices carried by 305 soldiers as well as other military vehicles and easily deployed 306 equipments. 308 1.2. Relation with the DTN Architecture and Networking Model 310 The DTN architecture introduces the bundle protocol [RFC5050], which 311 provides a way for applications to "bundle" an entire session, 312 including both data and metadata, into a single message, or bundle, 313 that can be sent as a unit. The bundle protocol provides end-to-end 314 addressing and acknowledgments. Hence, dLife is intended to provide 315 routing services in a network environment that uses bundles as its 316 data transfer mechanism, but could also be used in other intermittent 317 environments. 319 From a networking model perspective, a DTN is a network of self- 320 organizing wireless nodes connected by multiple time-varying links, 321 and where end-to-end connectivity is intermittent. Even in urban 322 scenarios, it is possible to face intermittent connectivity due to 323 dark areas, such as inside buildings and metropolitan systems, as 324 well as public areas with closed access points or even places 325 overcrowded with wireless access points. Unavailability of wireless 326 connectivity can be also a result of power-constrained nodes that 327 frequently shut down their wireless cards to save energy. 329 From a conceptual point of view, a DTN consists of a node meeting 330 schedule and workload. A node meeting schedule is a directed 331 multigraph, where each direct edge between two nodes represents a 332 meeting opportunity between them, and it is annotated with a starting 333 time of the meeting, the ending time of the meeting, if known, the 334 size of the transfer opportunity (i.e., contact capacity), and the 335 contact type. The workload is a set of messages. Each message can be 336 represented by the source, destination, size, time of creation at the 337 source, and priority. In dLife, a contact is defined by the tuple 338 and a message by the 339 tuple . 341 A DTN model encompasses the notion of type of contact or 342 connectivity. In current networks, the connectivity of a link or path 343 is generally given as a binary state (i.e., connected or 344 disconnected). In DTNs, a richer set of connectivity options is 345 required to make efficient routing decisions. Most importantly, links 346 (and paths, by extension) may provide a scheduled, predicted or 347 opportunistic communication. 349 Scheduled contacts imply some a priori knowledge about adjacent nodes 350 regarding future availability of links for message forwarding. 351 Scheduled links are the most typical cases for today's Internet and 352 satellite networks. Predicted contacts correspond to communication 353 opportunities wherein the probability of knowing whether a link will 354 be available at a future point in time is strictly above zero and 355 below one. Such links are the result of observed behavior (e.g., a 356 person may use its home Internet connection with significant 357 probability for any given time period) being characterized using 358 statistical estimation. Predicted links have gained attention due to 359 ad-hoc wireless networking, where node mobility may be significant. 361 In more challenging environments, such as mission-critical networks, 362 the future location of communicating entities may be neither known 363 nor predictable. These types of contacts are known as opportunistic. 364 Such opportunistic contacts are defined as a chance to forward 365 messages towards a specific destination or a group of destinations. 366 In such unpredictable scenario, it is important to take into account 367 the time that a node must wait until it meets another node again 368 (i.e., inter-contact time), the duration of these contacts (i.e., 369 contact duration), and the quality of the contact in terms of the set 370 of information that can be transferred (i.e., contact volume). 372 Independently of the type of connectivity, a contact in a DTN is 373 direction-specific. For example, a dial-up connection originating at 374 a customer's home to an Internet Service Provider (ISP) may be 375 scheduled from the point of view of the customer but unscheduled from 376 the point of view of the ISP. In what concerns contacts, dLife 377 assumes direction-specific opportunistic contacts (starting time, end 378 time, contact duration) which occur with some probability in pre- 379 defined daily time periods. 381 Another concept that must be introduced is that of network behavior. 382 As networks can be formed on-the-fly, their behavior can either be 383 deterministic or stochastic, depending on the type of used links. In 384 this draft, we focus on dynamic scenarios, where the behavior of the 385 network is described in stochastic terms, based on users' mobility 386 and social behavior. In a dynamic scenario, users move around 387 carrying their personal devices, which opportunistically come into 388 contact with each other, resulting in rather frequent topology 389 changes. 391 1.3. Differentiation to other Opportunistic Routing Proposal 393 Due to intermittent connectivity, routing protocols based on the 394 knowledge of end-to-end paths perform poorly, and numerous 395 opportunistic routing algorithms have been proposed instead. Some 396 opportunistic routing protocols use replicas of the same message to 397 combat the inherent uncertainty of future communication opportunities 398 between nodes. In order to carefully use the available resources and 399 reach short delays, many protocols perform forwarding decisions using 400 locally collected knowledge about node behavior to predict which 401 nodes are likely to deliver a content or bring it closer to the 402 destination. 404 We have identified [Moreira13] that most of the opportunistic routing 405 prior-art considered the replication-based forwarding scheme, while 406 only 15% were based on single-copy and flooding-based forwarding 407 schemes. Among the replication based solutions, approximately 69% 408 consider a contact-based approach (e.g., frequency of encounters) and 409 31% (the latest ones) investigate the trend based on social 410 similarity metrics (e.g., community detection). Contact-based 411 proposals consider every contact among nodes to update the proximity 412 graph and implement metrics such as the number of times nodes meet, 413 contact frequency and the last time a contact occurs. Besides PROPHET 414 [Lindgren04], the most cited replication-based proposal, other 415 examples based on contact metric are Prediction [Song07], and 416 Encounter-Based Routing [Nelson09]. 418 Most of the existing opportunistic routing solutions are based on 419 some level of replication. Among these proposals, emerge solutions 420 based on different representations of social similarity: i) labeling 421 users according to their social groups (e.g., Label [Hui07]); ii) 422 looking at the importance (i.e., popularity) of nodes (e.g., 423 PeopleRank [Mtibaa10]); iii) combining the notion of community and 424 centrality (e.g., SimBet [Daly07] and Bubble Rap [Hui11]); iv) 425 considering interests that users have in common (e.g., SocialCast 426 [Costa08]). Such prior-art shows that social-based solutions are more 427 stable than those which only consider node mobility. However, they do 428 not consider the dynamism of users' behavior (i.e., social daily 429 routines) and use centrality metrics, which may create bottlenecks in 430 the network. Moreover, such approaches assume that communities remain 431 static after creation, which is not a realistic assumption. On the 432 other hand, prior-art also shows that users have routines that can be 433 used to derive future behavior. It has been proven that mapping real 434 social interactions to a clean (i.e., more stable) connectivity 435 representation is rather useful to improve delivery. With dLife, 436 users' daily routines are considered to quantify the time-evolving 437 strength of social interactions and so to foresee more accurately 438 future social contacts than with proximity graphs inferred directly 439 from inter-contact times. 441 1.4. Requirements notation 443 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 444 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 445 document are to be interpreted as described in RFC 2119 [RFC2119]. 447 2. Node Architecture 449 In this section, we describe the architecture of a dLife node, which 450 performs its routing decisions based on two utility functions: TECD 451 to forward messages to nodes that have a stronger social relationship 452 with the destination than the carrier; TECDi to forward messages to 453 nodes that have a higher importance than the carrier. 455 With TECD each node computes the average of its contact duration with 456 other nodes during the same set of daily time periods over 457 consecutive days. Our assumption is that contact duration can provide 458 more reliable information than contact history, or frequency when it 459 comes to identifying the strength of social relationships. The reason 460 for considering different daily time periods relates to the fact that 461 users present different behavior during their daily routines. If the 462 carrier and encountered nodes have no social information towards the 463 destination, forwarding takes place based on a second utility 464 function, TECDi. 466 We start this section by describing the different components of the 467 node architecture, followed by an explanation of how to route 468 information based on the dynamics of the network that dLife is able 469 to capture by computing TECD and TECDi. Finally, we describe the 470 implemented forwarding strategy and the needed interfaces. 472 2.1. dLife Components 474 In order to perform forwarding based on the social daily behavior of 475 users, dLife comprises the following main computational elements: 477 o Social Information Gatherer (SIG) - responsible for: i) keeping 478 track of the contact duration of each encounter between nodes; and, 479 ii) obtaining the social weights and importance of encountered nodes 480 (i.e., potential next forwarders). As dLife considers different daily 481 samples, corresponding to different periods of time, it is imperative 482 to keep track of nodes' contacts in each sample. Additionally, upon 483 the need to replicate a bundle, SIG will obtain the social weight 484 between the encountered node and nodes it has met as well as the 485 importance of such node. 487 o Social Information Repository (SIR) - responsible for storing a 488 list with encountered nodes and contact duration to such nodes. At 489 the end of every daily sample, SIR will also store social weights and 490 importance of the encountered nodes computed by SW and IA (see 491 below). Additionally, SIR will temporarily store the social weight 492 and importance of an encountered node when the need for replicating a 493 bundle arises. 495 o Social Weighter (SW) - responsible for determining the social 496 weight between nodes according to their social interaction throughout 497 their daily routines. At the end of every daily sample, SW will 498 interact with SIR to determine the total contact time nodes spent 499 together and the average duration of contacts in order to compute the 500 social weight between nodes. 502 o Importance Assigner (IA) - responsible for computing the importance 503 of a node taking into account the importance of encountered nodes and 504 its social weight towards such nodes. At the end of every daily 505 sample, IA will interact with SIR in order to compute the importance 506 of a node in the system. 508 o Decision Maker (DM) - responsible for deciding whether replication 509 should occur. DM will interact with SIR to obtain relevant 510 information in order to take decisions. 512 2.2. Routing Algorithm 514 The dLife protocol applies the social opportunistic contact paradigm 515 to decide whether bundle replication is feasible. Its decision is 516 based on social weight (w_(x,y)) towards the bundle's destination or 517 on the importance (I(x)) of the encountered node (i.e., potential 518 next forwarder) in the system. 520 If the encountered node has better relationship with the bundle's 521 destination than the carrier in a given daily sample, it receives a 522 bundle copy, since there is a much greater chance for the encountered 523 node to meet the destination in the future. If relationship to the 524 bundle's destination is unknown, replication happens only if the 525 encountered node has higher importance than the bundle's current 526 carrier. 528 In order to compute the social weight between nodes and their 529 importance, dLife uses parameters that are determined as nodes 530 interact in the system. A brief explanation of these parameters is 531 given below: 533 CD_(x,y) 534 Refers to the contact duration between nodes, i.e., time nodes 535 spent in the communication range of one another, which would allow 536 them to exchange information. Within a given daily sample, 537 different contacts can happen with varied lengths. 539 TCT_(x,y) 540 Refers to the total contact time between nodes within a given 541 daily sample. It is given by the sum of all CD_(x,y) in that 542 specific daily sample. 544 AD_(x,y) 545 Refers to the average duration of contacts for the same daily 546 sample over different days. It is a Cumulative Moving Average 547 (CMA) of the average duration, considering the TCT_(x,y) of the 548 current daily sample and average duration in the same daily sample 549 of the previous day, AD_(x,y)_old. 551 w_(x,y) 552 Refers to the social weight between nodes at a given daily sample. 553 It reflects the level of social interaction among such nodes 554 throughout their daily routines. 556 I_(x) 557 Refers to the importance of a node in the system. The importance 558 is influenced by how well a node is socially related to other 559 important nodes. 561 N_(x) 562 Refers to the neighbor set of a node x, which it encountered in 563 the current daily sample. 565 dumping factor (d) 566 Refers the level of randomness considered by the forwarding 567 algorithm. 569 daily sample (Ti) 570 Refers to the time period in which the contact duration will be 571 measured to determine social weight and node importance. 573 As nodes interact, their CD_(x,y) is collected and used to determine 574 TCT_(x,y), AD_(x,y), w_(x,y), and I_(x) at the end of every daily 575 sample. If dLife is configured with a high number of daily samples, 576 the social weight and node importance will be more refined. Thus, it 577 is recommended the usage of twenty-four (24) daily samples 578 representing each hour of the day: the first daily sample refers 579 always to the zero hour of the day when the node is started. 581 Being able to identify the current daily sample allows a proper 582 computation of social weights and importance. Hence, in the case of 583 node failure (e.g., node crash) or node shutdown (e.g., lack of 584 battery), nodes need to know exactly in which daily sample they 585 stopped interaction, and more importantly how many daily samples have 586 elapsed since then (elapsed_ds). To guarantee that, the equation 587 below is used: 589 elapsed_ds = cnds * (ed - 1) + (cds - 1) + (cnds - lds) (1) 591 where: 593 cnds 594 is the configured number of daily samples. 596 ed 597 refers to the number of elapsed days. 599 cds 600 refers to the current daily sample (the one in which the node came 601 back on). 603 lds 604 refers to last daily sample (in which the node failed or shut 605 down). 607 With this, the node knows how many daily samples have elapsed and can 608 proceed with the update of social weights and importance to reflect 609 the lack of interaction that happen in reality. 611 2.2.1. Time-Evolving Contact Duration (TECD) 613 The TECD utility function considers the duration of contacts 614 (representing the intensity of social ties among users) and time- 615 evolving interactions (reflecting users' habits over different daily 616 samples). 618 Regarding the notations used in the equations presented in this sub- 619 section: sumk(...) denotes summation for k from 1 to n; sumj(...) 620 denotes summation for j from i to i+t-1; sumy denotes summation from 621 all y belonging to N(x). 623 Two nodes may have a social weight, w_(x,y), that depends on the 624 average total contact duration they have had in that same period of 625 time over different days. Within a specific daily sample Ti, node x 626 has n contacts with node y, having each contact k a certain contact 627 duration, CD_(x,y). At the end of each daily sample, the total 628 contact time, TCT_(x,y), between nodes x and y is given by the 629 equation below where n is the total number of contacts between the 630 two nodes. 632 TCT_(x,y) = sumk(CD_(x,y)) (2) 634 The Total Contact Time between users in the same daily sample over 635 consecutive days can be used to estimate the average duration of 636 their contacts for that specific daily sample: the average duration 637 of contacts between users x and y during a daily sample Ti in a day 638 j, denoted by AD_(x,y) is given by a cumulative moving average of 639 their TCT in that same daily sample, TCT_(x,y), and the average 640 duration of their contacts during the same daily sample Ti on the 641 previous day, denoted by AD_(x,y)_old, as shown in the equation 642 below. 644 AD_(x,y) = (TCT_(x,y)+(j-1)*AD(x,y)_old)/j (3) 646 The social strength between users in a specific daily sample Ti may 647 also provide some insight about their social strength in consecutive 648 k samples in the same day, i+k. This is what we call Time Transitive 649 Property. This property increases the probability of nodes being 650 capable of transmitting large data chunks, since transmission can be 651 resumed in the next daily sample with high probability. 653 TECD is able to capture the social strength w_(x,y) between any pair 654 of users x and y in a daily sample Ti based on the average duration 655 AD_(x,y) of contacts between them in such daily sample and in 656 consecutive t-1 samples, where t represents the total number of daily 657 samples. When k>t, the corresponding AD_(x,y) value refers to the 658 daily sample k-t. In the equation below the time transitive property 659 is given by the weight t/(t+k-i), where the highest weight is 660 associated to the average contact duration in the current daily 661 sample, being it reduced in consecutive samples. 663 TECD = w_(x,y) = sumj(t/(t+k-i)*AD_(x,y)) (4) 665 2.2.2. TECD Importance (TECDi) 667 As social interaction may also be modeled to consider the node 668 importance, TECDi computes the importance, I_(x), of a node x (cf. 669 equation below), considering the weights of the edges between x and 670 all the nodes y in its neighbor set, N_(x), at a specific daily 671 sample Ti along with their importance. 673 TECDi = I_(x) = (1-d)+d*sumy(w_(x,y)*I_(y)/N_(x)) (5) 675 TECDi is based on the PeopleRank function [Mtibaa10]. However, TECDi 676 considers not only node importance, but also the strength of social 677 ties between bundle's current carrier and potential next hops. 678 Another difference is that, with TECDi, the neighbor set of a node x 679 only includes the nodes which have been in contact with node x within 680 a specific daily sample Ti, whereas in PeopleRank the neighbor set of 681 a node includes all the nodes that ever had a link to node x. Note 682 that the level of randomness may vary with the application scenario. 683 Unless previously experimented, it is suggested that dumping factor 684 be set to 0.8. 686 2.3. Forwarding strategy 688 Independently of the application scenario, each node MUST employ a 689 forwarding strategy. The first rule is that if the encountered node 690 is the final destination of a bundle, the carrier SHOULD prioritize 691 such bundles by employing the prioritized forwarding strategy, 692 described below. 694 We use the following notation for the description provided in this 695 section. Nodes A and B are the nodes that encounter each other, and 696 the strategies are described as they would be applied by node A. 698 2.3.1. Basic Strategy 700 Forward the bundle only if w_(B,D) > w_(A,D) or I_(B) > I_(A) 701 When two nodes A and B meet in any daily sample Ti, node A gets from 702 node B: a) the updated list of all neighbors of B, including the 703 social weights that B has towards each of its neighbors, as well as 704 the importance of B; b) the list of the bundles that B is carrying 705 (bundle identifier, plus Endpoint Identifier (EID) of the 706 destination); c) the list of the latest set of bundles acknowledged 707 to B (the size of the list of acknowledged bundles returned by B 708 depends on the local cache size and policy). The information about 709 the social weight, importance, bundle list, and acknowledged bundles 710 received from node B are referenced in node A as w_(B,x)_recv, 711 I_(B)_recv, bundleList(IDn, destinationEIDx)_recv, and 712 ackedBundleList(IDn, destinationEIDx)_recv, respectively. 714 For every bundle that A carries in its buffer, and i) is not carried 715 by B, ii) has not been previously acknowledged to B, and iii) B has 716 enough buffer space to store it, node A sends a copy to B if B has 717 already encountered the bundle's destination D and its weight in 718 w_(B,D)_recv is greater than A's weight towards this same destination 719 D. Otherwise, bundles are replicated if I_(B)_recv is greater than 720 A's importance in the current daily sample Ti. 722 Finally, node A will update its own ackedBundleList and discard 723 bundles that have already been acknowledged to node B as described in 724 Section 3.3.3. 726 2.3.2. Prioritized Strategy 728 Similar to the basic forwarding strategy, being the only difference 729 the fact that prior to sending bundles, node A will first send those 730 bundles that have node B as destination. 732 2.4. Interfaces 734 This section provides a specification of the two major interfaces 735 required for dLife operation: a) the interface between the dLife 736 routing agent and the bundle agent; b) the interface between the 737 dLife routing agent and the lower layers. 739 2.4.1. Bundle Agent 741 The bundle protocol [RFC5050] introduces the concept of a "bundle 742 agent" that manages the interface between applications and the 743 "convergence layers" that provide the transport of bundles between 744 nodes during communication opportunities. This draft extends the 745 bundle agent with a routing agent that controls the actions of the 746 bundle agent during communication opportunities. 748 This section defines the interfaces to be implemented between the 749 bundle agent and the dLife routing agent. The defined interfaces 750 follow the general definition that was defined for the PRoPHET 751 proposal. 753 In this document, we assume that functions in a complete bundle agent 754 supporting dLife are distributed in such a way that reception and 755 delivery of bundles are not carried out directly by the dLife agent, 756 being the bundles placed in a queue available and managed by the 757 dLife agent. In this case, this interface allows the dLife routing 758 agent to be aware of the bundles placed at the node, and allows it to 759 inform the bundle agent about the bundles to be sent to a neighbor 760 node. Therefore, the bundle agent needs to provide the following 761 interface/functionality to the routing agent: 763 Get Bundle List 764 Returns a list of the stored bundles and their attributes to the 765 routing agent. 767 Send Bundle 768 Notifies the bundle agent to send a specified bundle. 770 Drop Bundle Advice 771 Advises the bundle agent that a specified bundle may be dropped by 772 the bundle agent if appropriate. 774 Acked Bundle Notification 775 Bundle agent informs routing agent whether a bundle has been 776 delivered to its final destination and time of delivery. 778 2.4.2. Lower Layers and Interface 780 To accommodate dLife operation on different types of wireless 781 technology, the lower layers SHOULD provide the following 782 functionality and interfaces. 784 Neighbor discovery and maintenance 785 A dLife node needs to: i) know the identity of its neighbors; ii) 786 when new neighbors appear; iii) when old neighbors disappear. Some 787 wireless networking technologies might already contain mechanisms 788 for detecting neighbors and maintaining state about them. Hence, 789 neighbor discovery is not a mandatory part of dLife. However, if 790 the underlying networking technology does not support neighbor 791 discovery and maintenance services, a simple neighbor discovery 792 scheme using local broadcasts of beacon messages COULD be used, 793 assuming that the underlying layer supports broadcast messages. 794 The operation of the protocol is as follows: 796 1. Periodically a dLife node does a local broadcast of a 797 beacon that contains its identity and address. 799 2. Upon reception of a beacon, the following can happen: 801 o The sending node is already in the list of active neighbors. 802 Update its entry in the list with the current time. At this 803 point dLife should start the Neighbor Sensing procedure as 804 mentioned in Section 3.1. 806 o The sending node is not in the list of active neighbors. Add 807 the node to the list of active neighbors and record the 808 current time. 810 3. If a beacon has not been received from a node in the list 811 of active neighbors within a predefined time period, it should 812 be assumed that this node is no longer a neighbor. The entry 813 for this node should be removed from the list of active 814 neighbors. 816 The lower layers MUST provide the two functions listed below: 818 New Neighbor 819 Signals the dLife agent that a new node has become a neighbor 820 (a node that is currently within communication range of the 821 current node, based on the used wireless networking 822 technology). At this point dLife should start the Neighbor 823 Sensing procedure as mentioned in Section 3.1. 825 Neighbor Gone 826 Signals the dLife agent that one of its neighbors has left. 828 Sender/Receiver Local Address 829 An address used by the underlying communication layer (e.g., an IP 830 or MAC address) that identifies the address of the sender and 831 receiver nodes. This address and its format is dependent on the 832 communication layer that is being used by the dLife layer. This 833 address must be unique among the nodes that can currently 834 communicate. 836 3. Protocol Overview 838 This section provides a description of the three operational phases 839 of dLife, namely: neighbor sensing, information exchange, and bundle 840 reception policies. 842 3.1. Neighbor Sensing Phase 843 The operation of dLife depends on how nodes interact, i.e., 844 considering all the potential contact opportunities to exchange 845 information. Thus, nodes running dLife MUST employ a mechanism for 846 neighbor discovery (cf. Section 2.4.2) and neighbor sensing. 848 If the underlying networking technology does not support neighbor 849 discovery and maintenance services, a mechanism as described in 850 Section 2.4.2 can be provided. 852 When a node (new or already met) is discovered, dLife performs the 853 following operation: 855 Start Contact Duration Counting 856 dLife starts counting the contact duration for the purpose of 857 later computing social weights and importance. In the case the 858 peer node has been encountered before within the same daily 859 sample, dLife checks if there were any changes in the metadata 860 (e.g., Social Weights and Node Importance list, ackedBundleList) 861 of the current node since the last encounter. If so, the current 862 node will start the Hello Procedure. 864 Hello Procedure 865 dLife sets up a link with the neighbor node through the Hello 866 message exchange as described in Section 5.3. The Hello message 867 exchange allows nodes to exchange information about their EID, 868 storage capacity, current time, and timer value. Once the link has 869 been set up, the protocol may continue to the Information Exchange 870 Phase (cf. Section 3.2) during which the lower layer is 871 responsible for detecting broken links. 873 Stop Contact Duration Counting 874 dLife stops counting the contact duration after detecting that the 875 neighbor is gone, through the notification received from the lower 876 layer (cf. Section 2.4.2). 878 In order to make use of this time dependence, dLife maintains a list 879 of recently encountered nodes identified by the Endpoint Identifier 880 (EID), as described in section 5.2. Each entry of such list includes 881 information that the node uses to update the status of the current 882 communication session and to gather information about previous 883 contacts. The size of this list is controlled, because due to low 884 storage capacity of nodes, the information related to neighbors that 885 are not in contact and towards which the current node has a social 886 weight lower than a predefined threshold SOCIAL_DROP can be dropped 887 from the list. It is suggested that such threshold be initially set 888 at 0.2, which is equivalent to the initial social weight towards 889 recently encountered nodes. 891 3.2. Information Exchange Phase 893 The Information Exchange phase comprises the transfer of two types of 894 metadata between connected nodes, through different messages 895 described in Section 4: 897 o EID Dictionary 898 o Social Weights and Node Importance (SWNI) 900 Upon a communication opportunity, different sets of each type of 901 metadata must be sent in each direction as explained further in this 902 section. Each set may be transferred in one or more messages. In case 903 a set of metadata needs more than one message to be completely 904 transferred, it may be partitioned by the dLife protocol engine. The 905 specification of dLife provides a submessage mechanism and 906 retransmission that allows large messages to be transmitted in 907 smaller chunks. 909 Each node running dLife is responsible for computing and updating 910 their social weights towards previously encountered nodes as well as 911 their own importance. Thus, in this operational phase, Social TLVs 912 (Type-Length-Value messages), as defined in Section 4.3.4, are 913 expected to reflect the latest updates regarding SWNI metadata, as 914 well as to include the list of bundles carried by the peering node 915 (bundleList) and the list of the latest bundles with acknowledged 916 delivery (ackedBundleList). Social TLVs are generated throughout the 917 information exchange phase upon updates of the SWNI information at 918 the end of a daily sample. 920 As first step in the Information Exchange Phase one or more messages 921 containing EID Dictionary metadata, EID Dictionary TLVs as defined in 922 Section 4.3.3, MUST be sent to the peering node, if the list of 923 encountered nodes is not empty. Such metadata contains a dictionary 924 of the EIDs of the nodes that will be listed in the Social TLVs (cf. 925 Section 3.2.1 for more information about this dictionary). 927 As a second step, one or more messages containing social metadata, 928 Social TLVs, MUST be sent to the peering node, if the list of 929 encountered nodes is not empty. This set of messages contains: i) a 930 list with the EIDs of the nodes that the peering node has encountered 931 so far and its social weights towards these nodes; ii) the importance 932 of the peering node; iii) a list with the identifiers of the bundles 933 that the node currently carries and respective destinations EIDs; and 934 iv) a list with the latest acknowledged bundles identifiers and 935 respective destinations EIDs. 937 As a third step, upon reception and acknowledgment of the complete 938 set of these messages, nodes MUST use one of the defined forwarding 939 strategies (see Section 2.3) to decide which of the stored bundles 940 (cf. Get Bundle List on Section 2.4.1) will be transferred to the 941 peer, assuming that there are stored bundles. 943 The bundles to be sent to the peering node MUST be selected based 944 upon the exchanged SWNI, bundleList and ackedBundleList information, 945 as well as the available storage capacity on the receiving peering 946 node. The bundles to be sent by the Bundle Agent (cf. Send Bundle on 947 Section 2.4.1) SHOULD NOT exceed the peering node's capacity that 948 MUST be indicated by the peer during the Hello procedure. The 949 information to be passed to the Bundle Agent includes the number of 950 bundles to be sent, where each bundle has an ID to be used for 951 acknowledging their receipt. 953 3.2.1. EID Dictionary 955 The EID Dictionary, as used in PRoPHET, is a mapping between variable 956 length EIDs [RFC4838] and String IDs coded as Self-Delimiting Numeric 957 Values (SDNVs - see Section 4.1. of RFC 5050 [RFC5050]). 959 This dictionary is used by peering nodes to synchronize the EIDs of 960 the nodes that they have encountered before. Each peer MAY add to the 961 dictionary by sending a EID Dictionary TLV to its peer. To allow 962 either peer to add to the dictionary at any time, the identifiers 963 used by each peer are taken from disjoint sets: identifiers 964 originated by the node that started the Hello procedure have the 965 least significant bit set to 0 (i.e., are even numbers) whereas those 966 originated by the other peer have the least significant bit set to 1 967 (i.e., are odd numbers). This means that the dictionary can be 968 expanded by either node at any point of the information exchange 969 phase and the new identifiers can then be used in subsequent TLVs 970 until the dictionary is reinitialized. 972 The dictionary that is established only persists through a single 973 encounter with a node (i.e., while the same link set up by the Hello 974 procedure, with the same instance numbers, remains open). 976 Having more than one identifier for the same EID does not cause any 977 problems. This means that it is possible for the peers to create 978 their dictionary entries independently if required by an 979 implementation, but this may be inefficient as a dictionary entry for 980 an EID might be sent in both directions between the peers. It may be 981 required to inspect entries sent by the node that started the Hello 982 procedure and thereby eliminate any duplicates before sending the 983 dictionary entries from the other peer. Whether postponing sending 984 the other peer's entries is more efficient depends on the nature of 985 the physical link technology and the transport protocol used. With a 986 genuinely full duplex link it may be faster to accept possible 987 duplication and send dictionary entries concurrently in both 988 directions. If the link is effectively half-duplex (e.g., Wi-Fi), 989 then it will generally be more efficient to wait and eliminate 990 duplicates. 992 If a node receives EID Dictionary metadata containing an identifier 993 that is already in use, the node MUST confirm that the corresponding 994 EID is identical to the EID in the existing entry. Otherwise, the 995 node MUST send an ACK TLV (i.e., EID ACK - identifier/EID 996 discrepancy) and ignore the EID Dictionary TLV containing the error. 997 If a node receives EID Dictionary metadata that uses an unknown 998 identifier (i.e., not in the dictionary), the node MUST send an ACK 999 TLV (i.e., EID ACK - unknown EID) message and ignore the TLV 1000 containing the error. 1002 3.2.2. Operation in the presence of multiples neighbors 1004 As a node may find itself in the range of more than one potential 1005 next forwarder, the neighbor sensing mechanism may establish multiple 1006 information exchanges with each of them. 1008 If these simultaneous contacts persist for some time, then the 1009 information exchange process will be periodically rerun for each 1010 contact according to the configured timer interval, which means that 1011 different Hello TLVs will be exchanged at different times. 1013 Based on the receipt time of these Hello TLVs at the sending node, it 1014 will establish the order for sending out the bundles, considering the 1015 storage capacity of the different neighbors. 1017 3.3. Bundle Reception Policies 1019 3.3.1. Queueing policy 1021 Because of limited buffer resources, bundles may need to be dropped 1022 at some nodes. Although dLife evaluation based on simulations have 1023 shown little consumption due to limiting replication based on social 1024 strength, a scheme MUST be used upon an exhaustion of buffer space. 1025 Hence, each node MUST operate a queueing policy that determines which 1026 bundles should be available for forwarding. 1028 This section defines a few basic queueing policies, inline with what 1029 was proposed for PRoPHET. However, nodes MAY use other policies if 1030 desired. If not chosen differently due to the characteristics of the 1031 deployment scenario, nodes SHOULD choose FIFO as the default queueing 1032 policy. 1034 FIFO 1035 Handles the queue in a First In First Out (FIFO) order. The bundle 1036 that has first entered into the queue is the first bundle to be 1037 dropped. 1039 FLNT 1040 The bundle that has been forwarded the largest number of times is 1041 the first to be dropped. For this effect, dLife SHOULD keep track 1042 of the number of times each bundle has been forwarded to other 1043 nodes. 1045 STTL 1046 The bundle that has shortest time-to-live is dropped first. As 1047 described in [RFC5050], each bundle has a timeout value specifying 1048 when it no longer is meaningful to its application and should be 1049 deleted. Since bundles with short remaining time to live will soon 1050 be dropped anyway, this policy decides to drop the bundle with the 1051 shortest remaining life time first. To successfully use a policy 1052 like this, there needs to be some form of time synchronization 1053 between nodes so that it is possible to know the exact lifetimes 1054 of bundles. 1056 DLSW 1057 The bundle that has a destination with low social weight is 1058 dropped first. A low social weight means that the carrier may not 1059 be the best forwarder to this bundle. However, such bundle can 1060 only be dropped if it was already forwarded for at least a Minimum 1061 Bundle Forward (MBF) times, which is a minimum number of forwards 1062 that a bundle must have been forwarded before being dropped (if 1063 such a bundle exists). 1065 More than one queueing policy MAY be combined in an ordered set, 1066 where the first policy is used primarily, the second only being used 1067 if there is a need to tie-break between bundles given the same 1068 eviction priority by the primary policy, and so on. It is worth 1069 noting that obviously nodes MUST NOT drop bundles for which it has 1070 custody unless the lifetime expires. 1072 3.3.2. Custody Policy 1074 The concept of custody transfer can be found in [RFC4838]. In general 1075 terms, the transmission of bundles with the Custody Transfer 1076 Requested option involves moving bundles "closer" (in terms of some 1077 routing metric) to their ultimate destination(s) with reliability. 1078 The nodes receiving these bundles along the way (and agreeing to 1079 accept the reliable delivery responsibility) are called "custodians". 1080 The movement of a bundle (and its delivery responsibility) from one 1081 node to another is called a "custody transfer". 1083 The reliability requirement that a custodian accepts can be 1084 instantiated in different ways: i) deleting the bundle after getting 1085 a confirmation of a successful custody transfer, which may require 1086 retransmissions over a reliable transport protocol, such as TCP. In 1087 this case, a bundle has normally one custodian in a moment in time; 1088 ii) deleting the bundle only after getting an acknowledgment that the 1089 bundle was delivered to the destination. In this case, a bundle can 1090 have more than one custodian, being the bundle replicated among 1091 custodians over a non-reliable transport protocol, such as UDP. 1093 dLife takes no responsibilities for making custody decisions. Such 1094 decisions should be made by a higher layer. However, dLife insures 1095 that custodian nodes do not drop bundles for which it has custody 1096 unless the lifetime expires, or an acknowledge message is received 1097 for that bundle. 1099 3.3.3. Destination Policy 1101 When a bundle reaches its final destination, the Bundle Agent sends a 1102 notification to the routing agent (cf. Acked Bundle Notification in 1103 Section 2.4.1), being that information (e.g., Bundle, deliveryTime) 1104 stored in the ackedBundleList by the routing agent. When nodes 1105 exchange Social message TLVs, bundles that have been ACKed are also 1106 listed. The node that receives this list updates its own list of 1107 ACKed bundles to be the union of its previous list and the received 1108 list. To prevent the list of ACKed bundles growing indefinitely, the 1109 ackedBundleList is periodically checked and bundles are removed 1110 following the configured queueing policy (c.f. Section 3.3.1) if the 1111 size of the list is bigger than a predefined threshold. When a node 1112 receives a notification for a bundle it is carrying, it MUST delete 1113 that bundle from its queue, since the notification indicates that a 1114 bundle has been delivered to its final destination. 1116 Nodes MAY keep track of which nodes they have sent Bundle ACKs for 1117 certain bundles to, and MAY in that case refrain from sending 1118 multiple Bundle ACKs for the same bundle to the same node. 1120 4. Message Formats 1122 This section defines the message formats of the dLife routing 1123 protocol. In order to allow for variable length fields, many numeric 1124 fields are encoded as SDNVs, defined in [RFC5050], as in PRoPHET. 1125 Since many of the fields are coded as SDNVs, the size and alignment 1126 of fields indicated in many of the specification diagrams below are 1127 indicative rather than prescriptive. 1129 The basic message format shown in Figure 1 consists of a header (see 1130 Section 4.1) followed by a sequence of one or more Type-Length-Value 1131 components (TLVs) taken from the specifications in Section 4.2. 1133 0 1 2 3 1134 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 1135 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1136 | | 1137 ~ Header ~ 1138 | | 1139 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1140 | | 1141 ~ TLV 1 ~ 1142 | | 1143 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1144 | . | 1145 ~ . ~ 1146 | . | 1147 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1148 | | 1149 ~ TLV n ~ 1150 | | 1151 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1153 Figure 1: Basic dLife Message Format 1155 4.1. Header 1157 0 1 2 3 1158 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 1159 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1160 | Prot_Number |Version| Flags | Code | 1161 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1162 | Sender | Receiver | 1163 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1164 | Message Identifier | 1165 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1166 |S| SubMessage Number | Length (SDNV) | 1167 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1168 | | 1169 ~ Message Body ~ 1170 | | 1171 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1173 Figure 2: dLife Message Header 1175 Prot_Number (Protocol Number) 1176 The DTN Routing Protocol Number is encoded as 8-bit unsigned 1177 integer in network bit order. The value of this field is 0. The 1178 dLife header is organized in this way so that dLife messages MAY 1179 be sent as the Protocol Data Unit of an IP packet if an IP 1180 protocol number was allocated for dLife. Transmitting dLife 1181 packets directly as an IP protocol on a public IP network such as 1182 the Internet would generally not work well because middle boxes 1183 such as firewalls and NAT boxes would be unlikely to allow the 1184 protocol to pass through and the protocol does not provide any 1185 congestion control. However, it could be so used on opportunistic 1186 wireless networks, which is the goal of dLife. The use of a light 1187 transport protocol such as UDP, in opposition to TCP, ensures a 1188 better exploitation of the presumable short contact opportunities 1189 between peers in a DTN. Due to the lack of reliability of UDP, 1190 dLife specify an acknowledgement procedure to transmit metadata. 1191 Hence, dLife is prepared to use UDP over Wi-Fi, while over 1192 Bluetooth, dLife uses the RFCOMM and L2CAP protocols. In both 1193 cases, message acknowledgement is made by the dLife mechanism. 1195 Version 1196 The Version of the dLife Protocol. Encoded as a 4-bit unsigned 1197 integer in network bit order. This document defines version 1. 1199 Flags 1200 The flags field is encoded as a 4-bit unsigned integer in network 1201 bit order. The following values are currently defined: 1203 o Success 0 1204 o Failure 1 1206 Code 1207 This field gives further information concerning the flag in a 1208 response message. It is mostly used to pass an error code in a 1209 failure response, but it can also be used to give further 1210 information in a success response message. In a request message, 1211 the code field is not used and is set to zero. 1213 If the Code field indicates that the ACK TLV is included in the 1214 message, further information on the successful or failure of the 1215 message will be found in the ACK TLV, which MUST be the first TLV 1216 after the header. 1218 The Code field is encoded as an 8-bit unsigned integer in network 1219 bit order with 5 unused and reserved bits, which were included to 1220 allow future extension of the protocol. The following values are 1221 defined: 1223 o Generic Response 0x00 1224 o Submessage Received 0x01 1225 o ACK TLV in message 0x02 1226 o Unexpected Error 0x03 1228 The "generic response" and the "submessage received" values tell 1229 us that the success or failure indicated in the Flag field is 1230 related to all the message or a submessage, respectively. 1232 Sender 1233 This field is the instance number for the link of the sender of 1234 the dLife message. This instance number identifies a link between 1235 peering nodes and lasts until the link goes down or when the 1236 identity of the entity at the other end of the link changes. It is 1237 randomly generated. This number is a 16-bit number that is 1238 guaranteed to be unique within the recent past and to change when 1239 the link or node comes back up after going down. Zero is not a 1240 valid instance number. Messages sent throughout all the 1241 communication phases (i.e., Sensing, Hello, Information exchange) 1242 should use the sender's instance number. The Sender Instance is 1243 encoded as a 16-bit unsigned integer in network bit order. 1245 Receiver 1246 This field is the instance number for the link of the receiver of 1247 the dLife message. If the sender of the message does not know the 1248 current number of the receiver, this field MUST be set to zero. 1249 Messages sent throughout all the communication phases (i.e., 1250 Sensing, Hello, Information exchange) should use the receiver's 1251 instance number. The receiver number is encoded as a 16-bit 1252 unsigned integer in network bit order. 1254 Message Identifier 1255 Used to associate a message with its response message. This 1256 identifier should be set in request messages to a value that is 1257 unique for the sending host within the recent past. Response 1258 messages contain the Message Identifier of the request they are 1259 responding to. The Message Identifier is a 32 bit pattern. 1261 S-flag 1262 If S is set (value 1), then the SubMessage Number field indicates 1263 the total number of SubMessage segments that compose the entire 1264 message. If it is not set (value 0), then the SubMessage Number 1265 field indicates the sequence number of this SubMessage segment 1266 within the whole message. The S field will only be set in the 1267 first sub-message of a sequence. 1269 SubMessage Number 1270 When a message is segmented because it exceeds the MTU of the link 1271 layer or otherwise, each segment will include a SubMessage Number 1272 to indicate its position. Alternatively, if it is the first sub- 1273 message in a sequence of submessages, the S flag will be set and 1274 this field will contain the total count of SubMessage segments. 1275 The SubMessage Number is encoded as a 15-bit unsigned integer in 1276 network bit order. The SubMessage number is zerobased, i.e., for a 1277 message divided into n submessages, they are numbered from 0 to (n 1278 - 1). For a message that it is not divided into submessages, the 1279 single message has the S-flag cleared (0) and the SubMessage 1280 Number is set to 0 (zero). 1282 Length 1283 Length in octets of this message including headers and message 1284 body. If the message is fragmented, this field contains the length 1285 of this SubMessage. The Length is encoded as an SDNV. 1287 Message Body 1288 The Message Body consists of a sequence of one or more of the TLVs 1289 specified in Section 4.2. 1291 4.2. TLV Structure 1293 All TLVs have the following format, and can be nested. 1295 0 1 2 3 1296 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 1297 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1298 | TLV Type | TLV Flags | TLV Length (SDNV) | 1299 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1300 | | 1301 ~ TLV Data ~ 1302 | | 1303 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1305 Figure 3: TLV Format 1307 Type 1308 Specific TLVs are defined in Section 4.3. The TLV Type is encoded 1309 as an 8-bit unsigned integer in network bit order. 1311 TLV Flags 1312 These are defined per TLV type. Any flags which are specified as 1313 reserved in specific TLVs SHOULD be transmitted as 0 and ignored 1314 on receipt. 1316 TLV Length 1317 Length of the TLV in octets, including the TLV header and any 1318 nested TLVs. Encoded as an SDNV. 1320 4.3. TLVs 1321 This section describes the various TLVs that can be used in dLife 1322 messages. 1324 4.3.1. Hello TLV 1326 The Hello TLV is used to set up and maintain a link between two dLife 1327 nodes. Hello messages are the first TLVs exchanged between nodes when 1328 they are within range of communication of one another, and are used 1329 to inform neighbors about the EID, storage capacity, and current time 1330 of the node and a timer value. 1332 The Hello sequence must be completed so other TLVs can be exchanged. 1333 After the Hello procedure, dLife nodes will store the information 1334 about each other EIDs, capacities, and considered timer. Such action 1335 is acknowledged by signaling that the communication has been 1336 established. If during the Hello procedure, an ACK is failed to be 1337 received, disconnection occurred and link should be assumed broken. 1339 0 1 2 3 1340 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 1341 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1342 | TLV type=0x01 |Flags| TLV Length (SDNV) | 1343 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1344 |EIDLength(SDNV)| Sender EID (SDNV) | Timer (SDNV) | 1345 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1346 | Storage (SDNV) | 1347 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1348 | Current time (SDNV) | 1349 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1351 Figure 4: Hello TLV Format 1353 TLV Flags 1354 The TLV Flags field contains a three bit Hello Function (HF) 1355 number that specifies one of two functions for the Hello TLV. The 1356 encoding of the Hello Function is: 1358 o HEL: HF = 1 1359 o ACK: HF = 2 1361 The HEL function is used by a node to send metadata needed for the 1362 dLife operation, namely the storage capacity of the node, its EID, 1363 current time, and a timer value. The ACK function in used by a 1364 node to acknowledge the reception of an HEL Hello TLV. 1366 TLV Data 1367 EID Length 1368 The EID Length field is used to specify the length of the 1369 Sender EID field in octets. If the EID has already been sent at 1370 least once in a message, a node MAY choose to set this field to 1371 zero, omitting the Sender EID from the Hello TLV. The EID 1372 Length is encoded as an SDNV and the field is thus of variable 1373 length. 1375 Sender EID 1376 The Sender EID field specifies the EID of the sender that is to 1377 be used in updating routing information and making forwarding 1378 decisions. If a node has multiple EIDs, one should be chosen 1379 for dLife routing. This field is of variable length. 1381 Timer 1382 The Timer field is used to inform the receiver of the timer 1383 value used in the Hello processing of the sender. The timer 1384 specifies the nominal time between periodic Hello messages. It 1385 is a constant for the duration of a session. The timer field is 1386 specified in units of 100 ms and is encoded as an SDNV. 1388 Storage 1389 This field indicates the node's storage capacity. Used to 1390 inform the potential senders of the node's limitations in terms 1391 of successful reception of bundles. This field is encoded as an 1392 SDNV. 1394 Current Time 1395 This field specifies the current time in the peering node. It 1396 is given in seconds and counting starts in the year 2000. This 1397 field is encoded as an SDNV. 1399 4.3.2. ACK TLV 1401 This ACK TLV can be used by itself or nested in Hello TLV. 1403 0 1 2 3 1404 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 1405 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1406 | TLV type=0x02 | Flags | TLV Length (SDNV) | 1407 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1408 | ACK Data | 1409 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1411 Figure 5: ACK TLV Format 1413 TLV Flags 1414 The TLV Flags field carries an identifier for the ACK TLV type as 1415 an 8-bit unsigned integer encoded in network bit order. A range of 1416 values is available for private and experimental use in addition 1417 to the values defined here. The following ACK TLV types are 1418 defined: 1420 o Break ACK 0x00 1421 Used when a node wants to break the connection due to the fact 1422 that the neighbor has a storage capacity lower that its 1423 threshold to send bundles. 1425 o Social ACK 0x01 1426 Reports on the reception of Social TLVs (SWNI, bundleList, and 1427 ackedBundleList). 1429 o EID ACK (identifier/EID discrepancy) 0x02 1430 Reports on the identifier/EID discrepancy error as mentioned in 1431 Section 3.2.1. 1433 o EID ACK (unknown EID) 0x03 1434 Reports on the unknown EID error as mentioned in Section 3.2.1. 1436 o Reserved 0x04 - 0x7F 1438 o Private/Experimental Use 0x80 - 0xFF 1440 TLV Data 1441 The contents and interpretation of the TLV Data field are specific 1442 to the type of ACK TLV. The ACK Type is defined as follows: 1444 Break ACK 1445 This field is set to zero. 1447 Social ACK 1448 This field is set to zero. 1450 EID ACK (identifier/EID discrepancy) 1451 String ID causing the discrepancy and the EID string that 1452 differs the previous value. 1454 EID ACK (unknown EID) 1455 String ID not found in the dictionary. 1457 4.3.3. EID Dictionary TLV 1459 The EID Dictionary TLV includes the list of EIDs used in making 1460 routing decisions and is a shared resource (cf. Section 3.2.1) built 1461 in each of the paired peers. The dictionary can be updated as more 1462 EID Dictionary TLVs are received. 1464 0 1 2 3 1465 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 1466 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1467 | TLV type=0xA0 | Reserved | TLV Length (SDNV) | 1468 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1469 | String/EID Count (SDNV) | 1470 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1471 | | 1472 ~ Variable Length Routing Address Strings ~ 1473 | | 1474 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1475 | Routing Address String 1 | 1476 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1477 | String ID 1 (SDNV) | Length (SDNV) | 1478 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1479 | Endpoint Identifier 1 (variable length) | 1480 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1481 ~ ... ~ 1482 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1483 | Routing Address String n | 1484 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1485 | String ID n (SDNV) | Length (SDNV) | 1486 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1487 | Endpoint Identifier n (variable length) | 1488 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1490 Figure 6: EID Dictionary TLV Format 1492 Reserved 1493 8 unused and reserved bits, which were included to allow future 1494 extension of the protocol 1496 TLV Data 1497 String/EID Count 1498 Number of strings corresponding to the nodes' EIDs the sender 1499 node has encountered so far. Encoded as SDNV. 1501 String ID n 1502 SDNV identifier that is constant for the duration of a session. 1503 String ID zero is predefined as the node initiating the session 1504 through sending the Hello message, and String ID one is 1505 predefined as the node responding with the Hello ACK message. 1506 These entries do not need to be sent explicitly as the EIDs are 1507 exchanged during the Hello procedure. 1509 In order to ensure that the String IDs originated by the two 1510 peers do not conflict, the String IDs generated in the node 1511 that sent the Hello HEL message MUST have their least 1512 significant bit set to 0 (i.e., are even numbers) and the 1513 String IDs generated in the node that responded with the Hello 1514 ACK message must have their least significant bit set to 1 1515 (i.e., they are odd numbers). 1517 Length 1518 Length of Endpoint Identifier in this entry. Encoded as SDNV. 1520 Endpoint Identifier n 1521 Text string representing the Endpoint Identifier. Note that it 1522 is NOT null terminated as the entry contains the length of the 1523 identifier. 1525 4.3.4. Social TLV 1527 This TLV provides the SWNI, bundleList, and ackedBundleList 1528 information, i.e., a list of the nodes that the peer node has 1529 encountered up to that moment along with its social weight towards 1530 them, the importance of the peer node, as well as the lists 1531 containing bundles being carried by the peering node and 1532 acknowledgements for already delivered bundles (limited to the latest 1533 BUNDLE_DELIVERED number of bundles). This TLV allows dLife nodes to 1534 choose the bundles to be sent according to the forwarding strategies 1535 explained in Section 2.3. 1537 0 1 2 3 1538 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 1539 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1540 | TLV type=0xA1 | Flags | TLV Length (SDNV) | 1541 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1542 | Importance Value | 1543 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1544 | SWNI String Count (SDNV) | 1545 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1546 | String ID 1 (SDNV) | Reserved | 1547 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1548 | SW value 1 | 1549 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1550 ~ ... ~ 1551 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1552 | String ID n (SDNV) | Reserved | 1553 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1554 | SW value n | 1555 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1556 | Carried Bundle Count (SDNV) | 1557 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1558 | Carried Bundle ID 1 | 1559 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1560 | Dest String ID 1 | 1561 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1562 ~ ... ~ 1563 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1564 | Carried Bundle ID n | 1565 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1566 | Dest String ID n | 1567 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1568 | Acked Bundle Count (SDNV) | 1569 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1570 | Acked Bundle ID 1 | 1571 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1572 | Dest String ID 1 | 1573 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1574 ~ ... ~ 1575 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1576 | Acked Bundle ID n | 1577 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1578 | Dest String ID n | 1579 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1581 Figure 7: Social message TLV Format 1582 TLV Flags 1583 The encoding of the Header flag field relates to the capabilities 1584 of the Source node sending the Social message. 1586 o Flag 0: More Social TLVs 1587 o Flag 1: Reserved 1588 o Flag 2: Reserved 1589 o Flag 3: Reserved 1590 o Flag 4: Reserved 1591 o Flag 5: Reserved 1592 o Flag 6: Reserved 1593 o Flag 7: Reserved 1595 The "More Social TLVs" flag is set to 1 if the Social message 1596 requires more TLVs to be sent in order to be fully transferred. 1597 This flag is set to 0 if this is the final TLV. 1599 TLV Data 1600 Importance 1601 Importance of the node sending the Social message as a 32-bit 1602 unsigned integer encoded in network bit order. 1604 SWNI String Count 1605 Number of entries regarding the SWNI information in the TLV. 1606 Encoded as SDNV. 1608 String ID n 1609 String ID of the endpoint identifier of the encountered node n 1610 for which this entry specifies the social weight as predefined 1611 in a dictionary TLV. This field is of variable length. This 1612 field is followed by 16 unused and reserved bits, which were 1613 included to allow future extension of the protocol (e.g., use 1614 of another metric such as contact volume or signal strength to 1615 improve the forwarding choice). Encoded as SDNV. 1617 SW value 1618 Social weight between the peering node and that specific 1619 encountered node n as a 32-bit unsigned integer encoded in 1620 network bit order. 1622 Carried Bundle Count 1623 Number of entries regarding the carried bundle information in 1624 the TLV. Encoded as SDNV. 1626 Carried Bundle ID n 1627 Identifier of the bundle n that the sender is currently 1628 carrying as a 32-bit unsigned integer. 1630 Acked Bundle Count 1631 Number of entries regarding the acknowledged bundle information 1632 in the TLV. Encoded as SDNV. 1634 Acked Bundle ID n 1635 Identifier of the bundle n that the sender has received 1636 acknowledgements for as a 32-bit unsigned integer. 1638 Dest String ID n 1639 String ID of the endpoint identifier of the destination n for a 1640 carried or acknowledged bundle. This field is of variable 1641 length. Encoded as SDNV. 1643 5. Detailed Operation 1645 This section provides further details about the operation of dLife, 1646 including state tables. As explained before dLife aims to release any 1647 assumption about the reliability of the transport protocol, and so 1648 positive acknowledgements would be necessary to signal successful 1649 delivery of (sub)messages. In this section, the phrase "send a 1650 message" should be read as *successful* sending of a message, 1651 signaled by receipt of the appropriate "Success" response. Hence, the 1652 state descriptions below do not explicitly mention positive 1653 acknowledgements, whether they are being sent or not. 1655 5.1. High Level State Tables 1657 This section provides the high level state tables for the operation 1658 of dLife. The next section provides a more detailed view of each part 1659 of the protocol's operation. The following states are used to define 1660 the dLife operation: 1662 SENSING 1663 This is the state all nodes start in. Nodes remain in this state 1664 until a new contact opportunity arises. Once the routing agent has 1665 sensed the presence of a peer, via notification of the lower 1666 layer, it will start counting the contact duration. The Hello 1667 procedure will be triggered depending if the peer is a new contact 1668 or an already encountered peer (as explained in Section 3.1) by 1669 switching to the HELLO state. Since multiple contacts may happen, 1670 the node should also remain in the SENSING state in order to 1671 detect new contact opportunities. This is handled by creating a 1672 new thread or process during the transition to the HELLO state, 1673 which then takes care of the communication with the new peer while 1674 the parent process remains in state SENSING waiting for other 1675 peers to communicate with. In the case when the neighbor is no 1676 longer available (described as 'neighbor gone notification rcvd' 1677 in the tables below), the thread or process created is destroyed. 1679 HELLO 1680 Nodes remain in the HELLO state from when a new contact 1681 opportunity arises until the Hello procedure is done and nodes are 1682 connected (which happens when the Hello procedure reaches the 1683 LINK_UP state as described in Section 5.3 - during this procedure, 1684 the state LINK_UP and WAIT_HELLO_HEL are used, but are not 1685 presented here since they are internal to the Hello procedure). 1686 Once the Hello procedure is done, the node starts the information 1687 exchange phase and transitions to the EXCHANGE state. If while in 1688 the HELLO state the node is notified that the neighbor is no 1689 longer within communication range by the lower layer, it returns 1690 to the SENSING state and, if appropriate, MAY destroys any 1691 additional process or thread created to handle the neighbor. 1693 EXCHANGE 1694 With the communication link set, nodes enter the EXCHANGE state in 1695 which the transmission of dLife metadata between peers is done. 1696 The node remains in this state as long as Information Exchange 1697 Phase TLVs (EID Dictionary, Social and ACK) are being exchanged. 1699 In the EXCHANGE state both nodes are able to exchange their EID 1700 dictionaries and SWNI information. With dLife, the exchange of 1701 information about dictionary, social weight, and node importance 1702 MAY be carried out independently but concurrently with the 1703 messages multiplexed on a single bidirectional link, or 1704 alternatively, the exchanges MAY be carried out partially or 1705 wholly sequentially if appropriate for the implementation. The 1706 information exchange process is explained in more detail in 1707 Section 3.2. 1709 When a Social TLV is received, the node MUST notify the Bundle 1710 Agent about the bundles that SHOULD be forwarded to the peer node. 1711 If the "More Social TLV" flag is set to zero (i.e., no more 1712 bundles to send), the node returns to the SENSING state. If the 1713 routing agent is notified by the lower layer that the neighbor is 1714 no longer in range, the node switches to the SENSING state and, if 1715 appropriate, MAY destroy any additional process or thread created 1716 to handle the neighbor. 1718 If one or more new bundles are received by this node and the TECD 1719 and TECDi metrics indicate that it would be appropriate to forward 1720 some or all of the bundles to the connected node(s), the bundles 1721 SHOULD be immediately transferred to the connected peer(s). As 1722 mentioned earlier, the lower layer is responsible in notifying the 1723 routing agent whether peers are still within communication range 1724 (cf. Section 2.4.2). 1726 State: SENSING 1727 +==============================================================+ 1728 | Condition | Action | New State | 1729 +=================+================================+===========+ 1730 | | Start contact duration count | | 1731 + +--------------------------------+ HELLO | 1732 | New Contact | Start Hello procedure | | 1733 + +--------------------------------+-----------+ 1734 | | Keep sensing for more contacts | SENSING | 1735 +-----------------+--------------------------------+-----------+ 1736 | Neighbor gone | | | 1737 | notification | | SENSING | 1738 | rcvd | | | 1739 +==============================================================+ 1741 State: HELLO 1742 +==============================================================+ 1743 | Condition | Action | New State | 1744 +=================+================================+===========+ 1745 | Hello TLV rcvd | | HELLO | 1746 +-----------------+--------------------------------+-----------+ 1747 | Hello procedure | Start Information | EXCHANGE | 1748 | done | Exchange Phase | | 1749 +-----------------+--------------------------------+-----------+ 1750 | Neighbor gone | | | 1751 | notification | | SENSING | 1752 | rcvd | | | 1753 +==============================================================+ 1755 State: EXCHANGE 1756 +==============================================================+ 1757 | Condition | Action | New State | 1758 +=================+================================+===========+ 1759 | On entry | Send metadata | EXCHANGE | 1760 +-----------------+--------------------------------+-----------+ 1761 |EID Dict TLV rcvd| Update local EID Dictionary | EXCHANGE | 1762 +-----------------+--------------------------------+-----------+ 1763 | Social TLV rcvd | Inform Bundle Agent | EXCHANGE | 1764 +-----------------+--------------------------------+-----------+ 1765 | More Social TLV | | SENSING | 1766 | flag = 0 | | | 1767 +-----------------+--------------------------------+-----------+ 1768 | New bundle | | EXCHANGE | 1769 +-----------------+--------------------------------+-----------+ 1770 | Neighbor gone | | | 1771 | notification | | SENSING | 1772 | rcvd | | | 1773 +==============================================================+ 1775 5.2. High Level Meta-Data Table 1777 During its operation, dLife makes use of metadata locally stored as a 1778 consequence of the exchange of Social TLVs, Hello TLVs and local 1779 operations. The stored metadata is used in the computation of social 1780 weight towards other nodes by the current node and its own importance 1781 as well as to identify itself (cf. Section 2.2). Metadata can be 1782 persistent or temporary: the former MUST be kept for longer times and 1783 the latter is replaced as a new daily sample starts. 1785 Persistent metadata includes the node's own importance (Imp), Average 1786 Duration (AD_peer) of contacts to peers, social weight to peer 1787 (w_peer), and last daily sample in the case of failure/shutdown (see 1788 Section 2.2). Since nodes receive information from neighbors, they 1789 must also store the peer's EID (EID_peer), importance of that peer 1790 (Imp_peer), and peer's current time (currTime_peer) (cf. Section 1791 4.3.1). Additionally, nodes must keep track of number of times the 1792 bundles were forwarded (fwd_times) as to employ the queueing FLNT 1793 policy describe in Section 3.3.1. 1795 The temporary metadata includes the node's own EID, storage capacity 1796 (StoCap), current time (currTime), EID Dictionary (EIDDict), contact 1797 duration (CD_peer) and total contact time (TCT_peer) for a given 1798 peer, and Last Encounter (LastEnc_peer). Temporary metadata received 1799 from peers are storage capacity (StoCap_peer), EID Dictionary 1800 (EIDDict_peer), and social weight list of that peer towards other 1801 nodes (SocList_peer). 1803 In the SENSING state, each node MUST have its own EID, storage 1804 capacity, and current time ready for exchange in the case of a 1805 contact. When a contact is sensed, a node creates an entry for this 1806 potential peer (EID_peer) in metadata table and start counting the 1807 duration of this contact (CD_peer). Note that the peer EID will only 1808 be known in the HELLO state. 1810 If the HELLO state is successfully concluded, the EID_peer is now 1811 known and new entries for the encountered peer are created (TCT_peer, 1812 AD_peer, w_peer, StoCap_peer, and currTime_peer) in the metadata 1813 table. LastEnc_peer is also initialized in the HELLO state and 1814 receives the time nodes encountered. This variable will tell a node 1815 if the social information to be exchanged is up-to-date. 1817 When the EXCHANGE state starts, a node will receive from its peer its 1818 EIDDict_peer, SocList_peer, and Imp_peer, which must be stored for 1819 later deciding in bundle forwarding. 1821 +------------------------+---------+----------+ 1822 | EID_own | StoCap | Imp | EIDDict | currTime | 1823 +------------------------+---------+----------+ 1824 | | 1825 | +----------+---------+----------+---------+--------+--------------+ 1826 | | EID_peer | CD_peer | TCT_peer | AD_peer | w_peer | LastEnc_peer | 1827 | +----------+---------+----------+---------+--------+--------------+ 1828 | | | | 1829 | | +-----+-----+-----+ +------+------+------+ 1830 | | | CD1 | ... | CDn | | AD11 | ... | AD1i | 1831 | | +-----+-----+-----+ +------+------+------+ 1832 | | 1833 | +-----------+------------+--------+-------------+------------+ 1834 | |StoCap_peer|SocList_peer|Imp_peer|currTime_peer|EIDDict_peer| 1835 | +-----------+------------+--------+-------------+------------+ 1836 | 1837 +--------------------+ 1838 | Bundle n fwd_times | 1839 +--------------------+ 1841 Figure 8: Meta-data Information 1843 This metadata varies in size according to the type of information it 1844 stores: 1846 o EID and EID_peer are coded as strings of variable size. 1848 o StoCap and StoCap_peer are coded as int (32 bits). 1850 o currTime, currTime_peer, and LastEnc_peer are coded as int (32 1851 bits). 1853 o Imp, Imp_peer, AD_peer, and w_peer are coded as floats (32 1854 bits). 1856 o CD_peer and TCT_peer are coded as long (64 bits). 1858 o Fwd_times is coded as int (32 bits). 1860 o EIDDict and EIDDict_peer are coded as a HashMap tuple with 1861 String ID encoded as SDNV and its equivalent EID of variable 1862 length (up to 32 bits). 1864 o SocList_peer is coded as a HashMap tuple with String ID of the 1865 encountered nodes, encoded as SDNV, and the social weight of the 1866 peer towards these nodes. 1868 5.3 Hello Procedure 1870 The hello procedure consists of the exchange of messages comprising 1871 the header TLV and a single Hello TLV (see Section 4.3.1) with the HF 1872 (Hello Function) field set to the specified value (HEL or ACK). 1874 The rules and state tables for this procedure are shown below with 1875 the main states and actions to be taken upon the receipt of the 1876 required information: 1878 o Hello HEL messages MUST always be issued first, and SHOULD be 1879 followed by a Hello ACK. 1881 o The link between peers is only considered available when the 1882 LINK_UP state is reached. 1884 o Hello messages MAY be exchanged concurrently, but also in a 1885 sequential manner, depending on the nature of the communication 1886 medium (full- or half-duplex). In the case of the latter, the 1887 process MUST be completed in one direction prior to initiating in 1888 the other one. 1890 Upon a contact, nodes exchange a Hello HEL message. After that, nodes 1891 will have information about each other's EID, storage capacity, and 1892 current time. The current time is used to determine in which daily 1893 sample the peer is in order to facilitate any required updates 1894 concerning social weights and importances that may have happened 1895 since last encounter between them. Additionally, a timer value is 1896 exchanged so nodes know the periodicity of next hello messages in 1897 order to signal the arrival of the Hello HEL message. 1899 At this moment, nodes MUST create entries for the peer (EID_peer) 1900 where the contact duration (CD_peer), total connected time 1901 (TCT_peer), average duration (AD_peer), social weight (w_peer), 1902 storage capacity (StoCap_peer), current time (currTime_peer), 1903 LastEnc_peer (initialized with currTime_peer), social weight list 1904 (SocList_peer), and the importance (Imp_peer) towards this specific 1905 peer are going to be maintained and updated. Additionally, a timer 1906 for receiving the Hello ACK message MUST be started. Up to this 1907 point, nodes are in the WAIT_HELLO_HEL state. 1909 A second hello message with the ACK flag MUST be issued to inform 1910 nodes about the successful reception of the Hello HEL message. If 1911 Hello ACK message does not arrive within the specified time (Hello 1912 ACK timeout), the link is assumed lost, nodes are disconnected, 1913 contact duration count MUST stop and variables SHOULD be saved. After 1914 this, the start of a new hello procedure is required and the nodes 1915 remain at the WAIT_HELLO_HEL state. 1917 The link is assumed active upon the receipt of the Hello ACK message. 1918 This means nodes are connected and ready to shift to the exchange 1919 information phase. At this point values should be saved in created 1920 entries and nodes move to the LINK_UP state. 1922 Nodes will remain at the LINK_UP state until the routing agent 1923 receive a notification from the lower layer reporting that the peer 1924 is no more within communication range (cf. neighbor gone in Section 1925 2.4.2). At this point nodes MUST stop the contact duration count with 1926 the value being saved to CD_peer (CD1 ... CDn) variables of each 1927 disconnected peer. 1929 State: WAIT_HELLO_HEL 1930 +===================================================================+ 1931 | Condition | Action | New State | 1932 +================+=================================+================+ 1933 | | Start timer for | | 1934 | Hello HEL | Hello ACK receipt | | 1935 + rcvd + + WAIT_HELLO_HEL + 1936 | | Initialize variables | | 1937 +----------------+---------------------------------+----------------+ 1938 | Hello ACK rcvd | Save variables | LINK_UP | 1939 +----------------+---------------------------------+----------------+ 1940 | | | | 1941 + Hello ACK + + + 1942 | timeout | Stop contact duration count | | 1943 +----------------+ + WAIT_HELLO_HEL + 1944 | Neighbor gone | Save variables | | 1945 + notification + + + 1946 | rcvd | | | 1947 +================+=================================+================+ 1949 State: LINK_UP 1950 +===================================================================+ 1951 | Condition | Action | New State | 1952 +================+=================================+================+ 1953 | Neighbor gone | Stop contact duration count | | 1954 + notification + + WAIT_HELLO_HEL + 1955 | rcvd | Save variables | | 1956 +================+=================================+================+ 1958 5.4 Information Exchange Phase 1960 After the exchange of hello messages, the nodes are in the LINK_UP 1961 state, which allows the exchange of information. dLife is 1962 bidirectional and the information exchange processes between a pair 1963 of nodes (from A to B and vice-versa) are independent and expected to 1964 run almost entirely concurrently. This is because EID Dictionaries 1965 SHOULD be synchronized to allow better performance of the protocol. 1967 The information exchange phase consists of messages comprising the 1968 dLife header, and EID Dictionary and Social TLVs (see Sections 4.3.3 1969 and 4.3.4). The rules and state tables are shown below with the main 1970 states and actions to be taken upon the receipt of the required 1971 information. 1973 o No information SHALL be exchanged prior to the hello procedure. 1975 o Information messages MAY be exchanged concurrently, but also in 1976 a sequential manner, depending on the nature of the communication 1977 medium (full- or half-duplex). In the case of the latter, the 1978 process MUST be completed in one direction prior to initiating in 1979 the other one. 1981 Once in the information exchange phase, as soon as nodes enter the 1982 WAIT_INFO state, they SHOULD send the EID Dictionary in order to 1983 synchronize the mapping between their identifiers (String ID) and 1984 EIDs of nodes they have encountered. As the EID dictionary is 1985 received, the node will shift to the BUILD_SOCIAL_TLV state and check 1986 whether or not problems with the mapping are detected. In the case of 1987 EID errors, an ACK TLV with EID ACK flag MUST be sent to inform the 1988 peer node about problems (cf. Sections 3.2.1 and 4.3.2) with the 1989 received identifiers (String ID). 1991 Still in the WAIT_INFO state, if a node gets a Social TLV, it will 1992 obtain the SWNI, bundleList, and ackedBundleList information from its 1993 peer node. With such information, the node will decide which bundles 1994 SHOULD be exchanged based on the forwarding strategies (cf. Section 1995 2.3), will update its ackedBundleList, and will inform the Bundle 1996 Agent (cf. Send Bundle in Section 2.4.1) about the list of bundles 1997 that SHOULD be forwarded to its peering node. 1999 The node will remain in the WAIT_INFO state after receiving an Acked 2000 Bundle Notification (cf. Section 2.4.1), which means that the bundles 2001 forwarded by the Bundle Agent arrived at the destination node, and 2002 the sending node can update its ackedBundleList; and also when 2003 receiving an ACK TLV with the Break ACK flag, which signals that the 2004 peering node decided to disconnect given its lack of storage 2005 capacity, and the sending node will stop the contact duration count 2006 and wait for information coming from other peers. 2008 As soon as entering the BUILD_SOCIAL_TLV state, the node MUST build 2009 and send its Social TLV to the peering node and will remain in this 2010 state until it receives an ACK TLV with the Social ACK flag. The node 2011 will shift to the WAIT_INFO state upon the receipt of the Social ACK. 2013 Since dLife updates SWNI information at every daily sample, this can 2014 influence in the next forwarding decisions. Thus, the node should 2015 report such updates to its peering node and shift to the 2016 BUILD_SOCIAL_TLV state. 2018 Independently of the state the node finds itself, if receiving a 2019 notification from the lower layer reporting that the peer is no 2020 longer within communication range (cf. neighbor gone in Section 2021 2.4.2), it MUST stop the contact duration count and wait for 2022 information coming from other peers. 2024 State: WAIT_INFO 2025 +===================================================================+ 2026 | Condition | Action | New State | 2027 +================+==============================+===================+ 2028 | On entry | Send EID Dictionary TLV | WAIT_INFO | 2029 +----------------+------------------------------+-------------------+ 2030 | EID Dictionary | Check identifier/EID mapping | BUILD_SOCIAL_TLV | 2031 | rcvd | | | 2032 +----------------+------------------------------+-------------------+ 2033 | EID error | Report problem | BUILD_SOCIAL_TLV | 2034 | | ACK TLV flag EID ACK | | 2035 +----------------+------------------------------+-------------------+ 2036 | | Get SWNI, bundleList | | 2037 | | and ackedBundleList | | 2038 | Social TLV | information | WAIT_INFO | 2039 + rcvd +------------------------------+ + 2040 | | Update ackedBundleList | | 2041 + +------------------------------+ + 2042 | | Inform Bundle Agent | | 2043 | | (Send Bundle) | | 2044 +----------------+------------------------------+-------------------+ 2045 | Acked Bundle | | | 2046 | Notification | Update ackedBundleList | WAIT_INFO | 2047 | rcvd | | | 2048 +----------------+------------------------------+-------------------+ 2049 | Break ACK | Disconnect | WAIT_INFO | 2050 + rcvd +------------------------------+ + 2051 | | Stop contact duration count | | 2052 +----------------+------------------------------+-------------------+ 2053 | SWNI updated | Report peer | BUILD_SOCIAL_TLV | 2054 +----------------+------------------------------+-------------------+ 2055 | Neighbor gone | | | 2056 | notification | Stop contact duration count | WAIT_INFO | 2057 | rcvd | | | 2058 +================+==============================+===================+ 2059 State: BUILD_SOCIAL_TLV 2060 +===================================================================+ 2061 | Condition | Action | New State | 2062 +================+==============================+===================+ 2063 | On entry | Build and send Social TLV | BUILD_SOCIAL_TLV | 2064 +----------------+------------------------------+-------------------+ 2065 | Social ACK | | WAIT_INFO | 2066 | rcvd | | | 2067 +----------------+------------------------------+-------------------+ 2068 | Neighbor gone | | | 2069 | notification | Stop contact duration count | WAIT_INFO | 2070 | rcvd | | | 2071 +================+==============================+===================+ 2073 6. Security Considerations 2075 Currently, dLife does not specify any special security measures. 2076 However, as a routing protocol for opportunistic networks, dLife may 2077 be a target for various attacks. Such attacks may not be problematic 2078 if all nodes in the network can be trusted and are working towards a 2079 common goal. If there is such a set of nodes, but there are also 2080 malicious nodes, consequent security problems can be solved by 2081 introducing an authentication mechanism when two nodes meet, for 2082 example using a Pretty Good Privacy (PGP) system. Thus, only nodes 2083 that are known to be members of the trusted group of nodes are 2084 allowed to participate in the dLife routing. This of course 2085 introduces the additional problem of key distribution, which is out- 2086 of-scope of this document. Examples of possible vulnerabilities are: 2088 Black Hole Attack 2089 A malicious node sets its social weights for all destinations to a 2090 very high value. This has two effects, both causing messages to be 2091 drawn towards the black hole, instead of to its correct 2092 destination: i) depending on queueing policy, this might lead to 2093 premature dropping of the bundle; ii) the social weights reported 2094 by the malicious node will affect the computation of the node 2095 importance. This could place the malicious use as the center of 2096 any communication. 2098 In this case, a node should raise alert if the social weights and 2099 node importance that it receives from a new neighbor is much 2100 higher than the cumulative moving average of the information 2101 received from all previous nodes. This situation can be handle by 2102 implementing a trustworthy authentication mechanism for pervasive 2103 computing, allowing a node to get extra confidence that a neighbor 2104 will handle social weights and node importance in a trustworthy 2105 manner. 2107 Identity Spoofing 2108 With identity spoofing, a malicious node claims to be someone 2109 else. This could be used to "steal" the data that should be going 2110 to a particular node. This will cause these bundles to be removed 2111 from the network, reducing the chance that they will reach their 2112 real destination. 2114 This can be prevented by using authentication between pervasive 2115 nodes. 2117 Bundle Store Overflow 2118 After encountering and receiving the social weights and node 2119 importance information from the victim, a malicious node may 2120 generate a large number of fake bundles to the destination for 2121 which the victim has the social weights. This will cause the 2122 victim to fill up its bundle storage, possibly at the expense of 2123 other, legitimate, bundles. This problem is transient as the 2124 messages will be removed when the victim meets the destination and 2125 delivers the messages. 2127 This attack can be prevented by requiring sending nodes to sign 2128 all bundles they originate. This will allow intermediate nodes to 2129 verify the integrity of the messages before accepting them. 2131 There are some typical vulnerabilities that are not potential 2132 problems with dLife such as: 2134 Fake ACKS 2135 In this typical situation, a malicious node may issue fake ACKs 2136 for all bundles (or only bundles for a certain destination if the 2137 attack is targeted at a single node) carried by nodes it meets. 2138 The affected bundles will be deleted from the network, greatly 2139 reducing their probability of being delivered to the destination. 2141 This situation does not occur with dLife since a node can only 2142 send an ACK to bundles that the current carrier decided to forward 2143 to it (based on local forwarding policies) and not for bundles 2144 that the potential malicious node asked to be forwarded. 2146 7. Implementation Experience 2148 The initial implementation of dLife is written in Java for the 2149 version 1.4.1 of the Opportunistic Network Emulator (ONE), named 2150 Dlife.java [Moreira12a], which implements the RoutingDecisionEngine 2151 interface to be used with the DecisionEngineRouter class. This 2152 implementation, which can be downloaded from the ONE web site, 2153 contains all the major mechanisms described in this document to 2154 ensure proper protocol operation. There are however some parts that 2155 are only specified, such as the queuing policies, and others that 2156 still need specification, such as the security considerations. The 2157 implementation considered nodes with limited storage resources (2 MB) 2158 and restricted communication: WiFi and Bluetooth. By running on ONE, 2159 the goal of this first implementation was to enable dLife to be 2160 tested in different scalable large pervasive scenarios (some based on 2161 real traces such as the one from Cambridge University) with other 2162 protocols: PRoPHET and Bubble Rap. The three key performance 2163 indicators that were studied were average message delay, probability 2164 of message delivery and protocol cost (number of duplicate messages 2165 in the network at the time of delivery). Experience and feedback from 2166 the implementers on early versions of the protocol have been 2167 incorporated into the current version. 2169 A second implementation of dLife was done in Java using the Android 2170 API development. The class responsible for routing is known as 2171 dLifeRouter.java. This implementation follows a modular design to 2172 allow operation over multiple platforms. For that, a dLife library is 2173 being developed in Java (version 1.6+). This library comprises 2174 different classes that in turn include the components, messages, 2175 interfaces, and functionalities specified in this draft. The 2176 implemented classes are: 2178 The SocialInformation class 2179 Comprises the SIG, SW, and IA components which are responsible for 2180 keeping track of the different contact between devices, computing 2181 the social weight among them, and determining their importance. 2183 The DlifeNeighbor class 2184 Include peer-specific information (e.g., EID_peer, Imp_peer, 2185 SocList_peer). 2187 The DlifeTLV class 2188 Provides all TLVs and methods used by dLife to create and 2189 interpret such TLVs. 2191 The main class (dLifeRouter) 2192 Includes the DM component that works along with other classes 2193 (i.e., components) based on the exchanged metadata and computed 2194 information to take routing decisions. 2196 The dLifeRouter class includes the interfaces to the DTN 2197 architecture/Bundle Agent (e.g., get bundle list, send bundle) and to 2198 the Bluetooth Convergence Layer (e.g., neighbor sensing). The 2199 implementation of the Bundle Agent, Bluetooth Convergence Layer and 2200 dLife are presented as an Opportunistic Networking Module to the DTN 2201 architecture. 2203 The DTN architecture/Bundle Agent class was implemented based on RFCs 2204 4838 and 5050. At the time of this work, available implementations 2205 for Linux and Android devices such as DTN2, IBR-DTN and Bytewalla 2206 were studied to obtain enough implementation background. This class 2207 provides nodes with DTN core functionality, direct wireless 2208 communication, generic routing capabilities, and secure 2209 communications. Generic routing functionalities are provided by the 2210 implementation of a generic routing class, GenericRouting, which was 2211 extended to represent the dLife protocol. Secure communications are 2212 supported by the implementation of a security layer, BundleSecurity, 2213 implemented according to RFC 6257 - Bundle security Protocol 2214 Specification. 2216 To allow direct wireless communication a common communication medium, 2217 the Bluetooth Convergence Layer (BCL), was created and implemented 2218 allowing direct exchange of bundles through the Bluetooth interface 2219 without the need of a structured WiFi network. The BCL class, which 2220 is not present in the available DTN architecture implementations, was 2221 implemented as general as possible to allow the interfacing between 2222 the Bundle Agent and the communication medium regardless of the used 2223 routing protocol and operational system running on the the devices. 2224 However, the current implementation was first developed for Android 2225 devices and thus the BCL takes advantages of some native Bluetooth 2226 functionality already implemented in this platform, such as the 2227 discovery of neighbors and the possibility of storing information 2228 about them. The implemented BCL (BluetoothConvergenceLayer.java) 2229 includes the Service Discovery Protocol (SDP) for sensing the medium 2230 and the Serial Port Profile (SPP) for data exchange. The BCL class 2231 uses the RFCOMM as transport protocol and runs on top on the Logical 2232 Link Control and Adaptation Protocol (L2CAP), which interfaces with 2233 the Host Controller Interface (HCI). Additionally, the BCL provides a 2234 simple reliable data stream and supports multiple connections as this 2235 is expected to happen in the real world. 2237 At the moment the Opportunistic Networking Module is partially 2238 functional on Android 2.3.6 Gingerbread (kernel version 2.6.35.7) 2239 devices, which are able to exchange information through their 2240 Bluetooth interfaces based on the current dLife specification. 2241 Currently, devices can only manage one simultaneous Bluetooth 2242 connection. Actually the code is under revision to be improved in 2243 order to support multiple connections, as this is a common situation 2244 in urban scenarios. Version 1.0 of the Opportunistic Networking 2245 Module for Android devices will be made available for download once 2246 concluded. 2248 8. Deployment Experience 2250 In order perform implementation tests of the dLife protocol, a DTN 2251 testbed was created in the context of the DTN-Amazon project, having 2252 COPELABS/University Lusofona and Federal University of Para as 2253 current partners. The testbed has currently 10 devices (3 personal 2254 computers with Ubuntu 10.10 Maverick, 3 smartphones Android 2.3.6 2255 Gingerbread, 4 wireless routers with OpenWrt 10.03.1). 2257 The testbed was initially used to test three different DTN 2258 implementations: IBR-DTN, organized in a modular form, with a focus 2259 on embedded systems for easy portability; DTN2, incorporating all 2260 components of the DTN architecture, divided into modules such as 2261 Convergence Layers, Persistent Store, Bundle Router and more; 2262 Bytewalla (version 3, since version 5 was not yet fully functional 2263 with sporadic crashes). 2265 This initial set of tests aimed to identify which implementation 2266 could be adopted in the DTN-Amazon project. 2268 Both IBR-DTN and DTN2 were tested with two applications that were 2269 able to communicate based on two different routing protocols via WiFi 2270 interfaces configured in infrastructured mode: i) whisper chat 2271 application over PRoPHET (IBR-DTN testbed); and ii) the DTN-Amazon 2272 Android security application for surveillance of university campus 2273 over Epidemic and PRoPHET routing (DTN2). 2275 Bytewalla was also deployed to allow the understanding of its 2276 functionalities. It was installed in Android devices with 2277 communication taking place through a wireless router, which could not 2278 interpret bundles and was only used to relay information. 2280 Additionally, The DTN2 implementation was also used to analyze the 2281 behavior of a network environment with mobility, while the mule 2282 (wireless router) were carried by a vehicle to enable the exchange of 2283 information between two hosts. There were also attempts to deliver 2284 the message at a speed of 60 km/h, the limit considered by the 2285 scientific community so that the communication Wi-Fi still works. 2287 As the idea was to exploit physical proximity (key aspect of dLife to 2288 determine different levels of social interaction among devices) 2289 between DTN-Amazon nodes, this initial set of tests showed that none 2290 of these available implementations were enough for the scenario of 2291 the project. Thus, they were studied to provide enough implementation 2292 knowledge to the project's designers resulting in the Opportunistic 2293 Networking Module. 2295 For a proof of concept, initial deployment tests of the stable dLife 2296 implementation over the Opportunistic Networking Module were carried 2297 out based on seven Android devices carried by students during their 2298 daily routine activities in the Federal University of Para campus for 2299 five days. A traffic generator was installed in each device to create 2300 a load of 6 messages/hour, towards the other six nodes used in the 2301 experience. Node storage was defined at 10MB and message size varied 2302 between 1KB and 1MB. 2304 These tests aimed to: i)evaluate the BCL implementation and generate 2305 the first contact traces based on it; and ii) test the behavior of 2306 dLife in terms of calculating the social weights between nodes and 2307 their importances. 2309 Currently, the Opportunistic Networking Module is being finetuned and 2310 the next set of tests will analyze the performance of the dLife, when 2311 compared to behavior of other social-oblivious opportunistic routing 2312 solutions such as Epidemic and PROPHET, based on the following 2313 metrics: average message delay, probability of message delivery and 2314 the number of duplicate messages in the network at the time of 2315 delivery. 2317 10. References 2319 10.1 Normative References 2321 [Moreira12a] W. Moreira, P. Mendes, and S. Sargento, "Opportunistic 2322 Routing Based on Daily Routines," in Proceedings of the 2323 Sixth IEEE WoWMoM Workshop on Autonomic and Opportunistic 2324 Communications (AOC 2012), (San Francisco, California, 2325 USA), June, 2012. 2327 [Moreira12b] W. Moreira, M. de Souza, P. Mendes, and S. Sargento, 2328 "Study on the Effect of Network Dynamics on Opportunistic 2329 Routing" in Proceedings of the Eleventh International 2330 Conference on Ad-Hoc Networks and Wireless (AdHoc Now 2331 2012), (Belgrade, Serbia), July, 2012. 2333 [RFC2119] S. Bradner, "Key words for use in RFCs to Indicate 2334 Requirement Levels", BCP 14, RFC 2119, March 1997. 2336 [RFC4838] V. Cerf, S. Burleigh, A. Hooke, L. Torgerson, R. Durst, K. 2337 Scott, K. Fall, and H. Weiss, "Delay-Tolerant Networking 2338 Architecture", RFC 4838, April 2007. 2340 [RFC5050] K. Scott and S. Burleigh, "Bundle Protocol Specification", 2341 RFC 5050, November 2007. 2343 10.2 Informative References 2345 [Chaintreau06] A. Chaintreau, P. Hui, J. Crowcroft, C. Diot, R. Gass, 2346 and J. Scott, "Impact of human mobility on the design of 2347 opportunistic forwarding algorithms," in Proceedings of 2348 INFOCOM, (Barcelona, Spain), April, 2006. 2350 [Costa08] P. Costa, C. Mascolo, M. Musolesi, and G. P. Picco, 2351 "Socially-aware routing for publish-subscribe in delay- 2352 tolerant mobile ad hoc networks," Selected Areas in 2353 Communications, IEEE Journal on, vol. 26, pp. 748- 760, 2354 June, 2008. 2356 [Daly07] E. M. Daly and M. Haahr, "Social network analysis for 2357 routing in disconnected delay-tolerant manets," in 2358 Proceedings of ACM MobiHoc, (Montreal, Canada), September, 2359 2007. 2361 [Eagle09] N. Eagle and A. Pentland, "Eigenbehaviors: identifying 2362 structure in routine," Behavioral Ecology and 2363 Sociobiology, vol. 63, pp. 1057-1066, May, 2009. 2365 [Hossmann10] T. Hossmann, T. Spyropoulos, and F. Legendre, "Know thy 2366 neighbor: Towards optimal mapping of contacts to social 2367 graphs for dtn routing," in Proceedings of IEEE INFOCOM, 2368 (San Diego, USA), March, 2010. 2370 [Hui07] P. Hui and J. Crowcroft, "How small labels create big 2371 improvements," in Proceedings of IEEE PERCOM Workshops, 2372 (White Plains, USA), March, 2007. 2374 [Hui11] P. Hui, J. Crowcroft, and E. Yoneki, "Bubble rap: social- 2375 based forward- ing in delay tolerant networks," Mobile 2376 Computing, IEEE Transactions on, vol. 10, pp. 1576-1589, 2377 November, 2011. 2379 [I-D.irtf-dtnrg-tcp-clayer] M. Demmer and J. Ott, "Delay Tolerant 2380 Networking TCP Convergence Layer Protocol", draft-irtf- 2381 dtnrg-tcp-clayer-02 (work in progress), November 2008. 2383 [I-D.irtf-dtnrg-udp-clayer] H. Kruse and S. Ostermann, "UDP 2384 Convergence Layers for the DTN Bundle and LTP Protocols", 2385 draft-irtf-dtnrg-udp-clayer-00 (work in progress), 2386 November 2008. 2388 [Lindgren04] A. Lindgren, A. Doria, and O. Schelen, "Probabilistic 2389 routing in intermittently connected networks," in Service 2390 Assurance with Partial and Intermittent Resources, vol. 2391 3126 of Lecture Notes in Computer Science, pp. 239--254, 2392 Springer Berlin / Heidelberg, 2004. 2394 [Lindgren06] A. Lindgren and K. Phanse, "Evaluation of Queueing 2395 Policies and Forwarding Strategies for Routing in 2396 Intermittently Connected Networks", Proceedings of 2397 COMSWARE 2006 , January 2006. 2399 [Moreira13] W. Moreira and P. Mendes, "Social-aware Opportunistic 2400 Routing: The New Trend." In: Woungang, I, Dhurandher, S., 2401 Anpalagan, A., Vasilakos, A. V. (Eds.), Routing in 2402 Opportunistic Networks, Springer Verlag, June, 2013. 2404 [Moreira_12c] W. Moreira, P. Mendes, and S. Sargento, "Assessment 2405 Model for Opportunistic Routing", IEEE Latin America 2406 Transactions, Vol 10 Issue 3 April 2012 2408 [Mtibaa10] A. Mtibaa, M. May, M. Ammar, and C. Diot, "Peoplerank: 2409 Combining social and contact information for opportunistic 2410 forwarding," in Proceedings of INFOCOM, (San Diego, USA), 2411 March, 2010. 2413 [Nelson09] S. Nelson, M. Bakht, and R. Kravets, "Encounter-based 2414 routing in DTNs," in Proceedings of INFOCOM, (Rio de 2415 Janeiro, Brazil), April, 2009. 2417 [RFC6257] S. Symington, S. Farrell, H. Weiss, and P. Lovell, "Bundle 2418 Security Protocol Specification", RFC 6257, May 2011. 2420 [Song07] L. Song and D. F. Kotz, "Evaluating opportunistic routing 2421 protocols with large realistic contact traces," in 2422 Proceedings of ACM MobiCom CHANTS, (Montreal, Canada), 2423 September, 2007. 2425 [Vahdat00] A. Vahdat and D. Becker, "Epidemic Routing for Partially 2426 Connected Ad Hoc Networks", Duke University Technical 2427 Report CS-200006, April 2000. 2429 Authors' Addresses 2431 Waldir Moreira 2432 COPELABS, Universidade Lusofona 2433 Campo Grande, 376 2434 1749-024 Lisboa 2435 Portugal 2436 Phone: 2437 Email: waldir.junior@ulusofona.pt 2438 URI: http://siti2.ulusofona.pt/~wjunior 2440 Paulo Mendes 2441 COPELABS, Universidade Lusofona 2442 Campo Grande, 376 2443 1749-024 Lisboa 2444 Portugal 2445 Phone: 2446 Email: paulo.mendes@ulusofona.pt 2447 URI: http://siti.ulusofona.pt/~pmendes 2449 Eduardo Cerqueira 2450 ITEC, Universidade Federal do Para 2451 Rua Augusto Correa, 01, Guama 2452 66075-110 Belem-PA 2453 Brasil 2454 Phone: 2455 Email: cerqueira@ufpa.br 2456 URI: http://www.gercom.ufpa.br/eduardo/