RFC 6693
Probabilistic Routing Protocol for Intermittently Connected Networks
🎀 RFC 6693: Probabilistic Routing Protocol for Intermittently Connected Networks 🦋
Title block tea ☕
- RFC number: 6693 💖
- Title: Probabilistic Routing Protocol for Intermittently Connected Networks
- Stream: Internet Research Task Force (IRTF) 🧚
- Authors: A. Lindgren (SICS), A. Doria (Technicalities), E. Davies (Folly Consulting), S. Grasic (Lulea University of Technology) 👯♀️
- Category: Experimental 🧪
- ISSN: 2070-1721
- Date: August 2012 📅
- Obsoletes / Updates: the title block doesn't list any, so this RFC doesn't claim to replace or update anything 🙅♀️
Abstract ✨
okay so first things first, this doc is a product of the Delay Tolerant Networking Research Group, and that group has reviewed it. No objections to publishing it as an RFC were raised. 🫶
so what even is PRoPHET? 🤔 It stands for Probabilistic Routing Protocol using History of Encounters and Transitivity, and it's giving main character energy for intermittently connected networks 💅. It's a variant of epidemic routing (where messages get passed around to everyone they can reach) 🌸. The twist is that PRoPHET prunes the epidemic distribution tree, so it doesn't waste resources on copying everything everywhere, and it still goes for the best-case routing results that epidemic routing can get 🔥.
it's meant for sparse mesh networks, where there's no guarantee that a fully connected path between source and destination exists at any given moment. In that situation, traditional routing protocols just can't deliver messages between hosts 💀. These are examples of networks where the latency needs of applications don't match what the underlying network can actually do (these are often called delay and disruption tolerant networks) 🌈.
the doc goes in two parts: an architectural overview first, then the actual protocol spec 🎀.
Status of This Memo ✨
okay, the vibe check on status: this document is not an Internet Standards Track specification 🙅♀️. It's published so people can examine it, implement it experimentally, and evaluate it 🧪.
it defines an Experimental Protocol for the Internet community 🦋, and it's a product of the Internet Research Task Force (IRTF) 🧚. The IRTF shares the results of Internet-related research and development, and those results might not be suitable for deployment 💜. This RFC represents the consensus of the Delay Tolerant Networking Research Group of the IRTF 👑.
Documents approved for publication by the IRSG are not a candidate for any level of Internet Standard. See Section 2 of RFC 5741 for the details 💀.
want the latest status, errata, or a way to give feedback? Check out http://www.rfc-editor.org/info/rfc6693 🔗.
Copyright Notice 🌸
Copyright (c) 2012 IETF Trust and the persons identified as the document authors. All rights reserved 💖.
this document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) as they stand on the publication date. Please read these carefully, bestie, because they spell out your rights and restrictions for this document 📜🫶.
Table of Contents 📚
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1. Relation to the Delay-Tolerant Networking Architecture . 7
1.2. Applicability of the Protocol . . . . . . . . . . . . . . 8
1.3. PRoPHET as Compared to Regular Routing Protocols . . . . 10
1.4. Requirements Notation . . . . . . . . . . . . . . . . . . 11
2. Architecture . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1. PRoPHET . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1.1. Characteristic Time Interval . . . . . . . . . . . . 12
2.1.2. Delivery Predictability Calculation . . . . . . . . . 12
2.1.3. Optional Delivery Predictability Optimizations . . . 17
2.1.4. Forwarding Strategies and Queueing Policies . . . . . 18
2.2. Bundle Protocol Agent to Routing Agent Interface . . . . 19
2.3. PRoPHET Zone Gateways . . . . . . . . . . . . . . . . . . 20
2.4. Lower-Layer Requirements and Interface . . . . . . . . . 21
3. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . 22
3.1. Neighbor Awareness . . . . . . . . . . . . . . . . . . . 22
3.2. Information Exchange Phase . . . . . . . . . . . . . . . 23
3.2.1. Routing Information Base Dictionary . . . . . . . . . 25
3.2.2. Handling Multiple Simultaneous Contacts . . . . . . . 26
3.3. Routing Algorithm . . . . . . . . . . . . . . . . . . . . 28
3.4. Bundle Passing . . . . . . . . . . . . . . . . . . . . . 32
3.4.1. Custody . . . . . . . . . . . . . . . . . . . . . . . 33
3.5. When a Bundle Reaches Its Destination . . . . . . . . . . 33
3.6. Forwarding Strategies . . . . . . . . . . . . . . . . . . 34
3.7. Queueing Policies . . . . . . . . . . . . . . . . . . . . 36
4. Message Formats . . . . . . . . . . . . . . . . . . . . . . . 38
4.1. Header . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.2. TLV Structure . . . . . . . . . . . . . . . . . . . . . . 44
4.3. TLVs . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.3.1. Hello TLV . . . . . . . . . . . . . . . . . . . . . . 45
4.3.2. Error TLV . . . . . . . . . . . . . . . . . . . . . . 47
4.3.3. Routing Information Base Dictionary TLV . . . . . . . 48
4.3.4. Routing Information Base TLV . . . . . . . . . . . . 50
4.3.5. Bundle Offer and Response TLVs (Version 2) . . . . . 51
5. Detailed Operation . . . . . . . . . . . . . . . . . . . . . 55
5.1. High-Level State Tables . . . . . . . . . . . . . . . . . 56
5.2. Hello Procedure . . . . . . . . . . . . . . . . . . . . . 59
5.2.1. Hello Procedure State Tables . . . . . . . . . . . . 61
5.3. Information Exchange Phase . . . . . . . . . . . . . . . 62
5.3.1. State Definitions for the Initiator Role . . . . . . 66
5.3.2. State Definitions for the Listener Role . . . . . . . 71
5.3.3. Recommendations for Information Exchange Timer
Periods . . . . . . . . . . . . . . . . . . . . . . . 77
5.3.4. State Tables for Information Exchange . . . . . . . . 78
5.4. Interaction with Nodes Using Version 1 of PRoPHET . . . . 92
6. Security Considerations . . . . . . . . . . . . . . . . . . . 93
6.1. Attacks on the Operation of the Protocol . . . . . . . . 94
6.1.1. Black-Hole Attack . . . . . . . . . . . . . . . . . . 94
6.1.2. Limited Black-Hole Attack / Identity Spoofing . . . . 95
6.1.3. Fake PRoPHET ACKs . . . . . . . . . . . . . . . . . . 95
6.1.4. Bundle Store Overflow . . . . . . . . . . . . . . . . 96
6.1.5. Bundle Store Overflow with Delivery Predictability
Manipulation . . . . . . . . . . . . . . . . . . . . 96
6.2. Interactions with External Routing Domains . . . . . . . 97
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 97
7.1. DTN Routing Protocol Number . . . . . . . . . . . . . . . 98
7.2. PRoPHET Protocol Version . . . . . . . . . . . . . . . . 98
7.3. PRoPHET Header Flags . . . . . . . . . . . . . . . . . . 99
7.4. PRoPHET Result Field . . . . . . . . . . . . . . . . . . 99
7.5. PRoPHET Codes for Success and Codes for Failure . . . . . 99
7.6. PRoPHET TLV Type . . . . . . . . . . . . . . . . . . . . 100
7.7. Hello TLV Flags . . . . . . . . . . . . . . . . . . . . . 101
7.8. Error TLV Flags . . . . . . . . . . . . . . . . . . . . . 101
7.9. RIB Dictionary TLV Flags . . . . . . . . . . . . . . . . 102
7.10. RIB TLV Flags . . . . . . . . . . . . . . . . . . . . . . 102
7.11. RIB Flags . . . . . . . . . . . . . . . . . . . . . . . . 103
7.12. Bundle Offer and Response TLV Flags . . . . . . . . . . . 103
7.13. Bundle Offer and Response B Flags . . . . . . . . . . . . 104
8. Implementation Experience . . . . . . . . . . . . . . . . . . 104
9. Deployment Experience . . . . . . . . . . . . . . . . . . . . 105
10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 105
11. References . . . . . . . . . . . . . . . . . . . . . . . . . 105
11.1. Normative References . . . . . . . . . . . . . . . . . . 105
11.2. Informative References . . . . . . . . . . . . . . . . . 106
Appendix A. PRoPHET Example . . . . . . . . . . . . . . . . . . 108
Appendix B. Neighbor Discovery Example . . . . . . . . . . . . . 110
Appendix C. PRoPHET Parameter Calculation Example . . . . . . . 110the TOC is a whole roadmap, and we're just getting started 🗺️💜
1. Introduction ✨
okay bestie, welcome to the PRoPHET era 💖 The Probabilistic Routing Protocol using History of Encounters and Transitivity (PRoPHET) algorithm lets nodes talk to each other in an intermittently connected network, where at least some of the nodes are mobile 🦋
Here's the tea. One of the most basic rules of "traditional" (IP) networking is that a fully connected path has to exist between the two endpoints for the whole session, or else communication just isn't possible 🙈 But there are plenty of situations where connectivity keeps dropping out. In those cases, end-to-end traditional protocols can't work at all, and we still really want the nodes to be able to communicate 😭
Picture a network of mobile nodes using wireless communication with a limited range. That range is smaller than the distances the nodes travel. Two nodes can only talk at a given moment if the distance between them is less than the wireless range. So even if messages get forwarded through other nodes as intermediate routes, there's no guarantee you'll find a working continuous path at the moment you need to send something 💀
One way to make this work is to let messages sit in buffers on intermediate nodes for much longer than normal router queues would hold them (cf. Delay-Tolerant Networking [RFC4838]) 🧚 Then you can use the movement of some of the nodes to carry messages closer to their destination, handing them off to other nodes whenever they meet. Figure 1 shows how node mobility in this kind of scenario can eventually deliver a message to its destination 🌸 The four sub-figures (a) - (d) show the physical positions of four nodes (A, B, C, and D) at four time instants, going from (a) to (d). The outline around each letter is the range of the radio that node uses to communicate, and communication is only possible when those ranges overlap. At the start, node A has a message (the asterisk (*) next to it) that needs to reach node D. There's no path between A and D because the wireless range is so limited. As you can see in sub-figures (a) - (d), the nodes move around so the message first gets transferred to node B, then to node C, and finally, when node C moves within range of node D, C can hand the message over to its final destination. This technique is known as "transitive networking" 👑
+----------------------------+ +----------------------------+
| ___ | | ___ |
| ___ / \ | | / \ |
| / \ ( D ) | | ( D ) |
| ( B ) \___/ | | ___ \___/ |
| \___/ ___ | | /___\ ___ |
|___ / \ | | (/ B*\) / \ |
| \ ( C ) | | (\_A_/) ( C ) |
| A* ) \___/ | | \___/ \___/ |
|___/ | | |
+----------------------------+ +----------------------------+
(a) Time t (b) Time (t + dt)
+----------------------------+ +----------------------------+
| _____ ___ | | ___ ___ |
| / / \ \ / \ | | / \ /___\ |
| ( (B C* ) ( D ) | | ( B ) (/ D*\) |
| \_\_/_/ \___/ | | \___/ (\_C_/) |
| ___ | | ___ \___/ |
| / \ | | / \ |
| ( A ) | | ( A ) |
| \___/ | | \___/ |
| | | |
+----------------------------+ +----------------------------+
(c) Time (t + 2*dt) (d) Time (t + 3*dt)
Figure 1: Example of transitive communicationNow, real application scenarios are likely to be non-random, and that's the good part 🎀 The mobility and contact patterns tend to be predictable, because they come from the underlying activities of the higher-level application. For example, human mobility often follows regular traffic patterns built on repeating behaviors, like going to work or the market and then heading home, plus social interactions. Other node mobility situations work the same way: a proportion of the nodes are mobile, and they move in ways that aren't completely random over time but still have some predictability 🌈 So if a node has visited a location or been in contact with a certain node several times before, it's likely to visit that location or meet that node again. Main character energy for patterns 💅
PRoPHET can also be used in some networks where this kind of mobility doesn't happen. Predictable contact patterns can show up among static nodes too, when varying radio conditions or power-saving sleep schedules make connections between nodes intermittent 🍓
Earlier mechanisms for communicating in intermittently connected networks, like Epidemic Routing [vahdat_00], took very general approaches to the problem 🧐 In an environment where buffer space and bandwidth are infinite, epidemic routing gives an optimal solution for routing in an intermittently connected network, in terms of message delivery ratio and latency. The catch is that in most cases neither bandwidth nor buffer space is infinite. They're scarce resources, especially in sensor networks 😭
PRoPHET is fundamentally an epidemic protocol with strict pruning ✨ An epidemic protocol works by transferring its data to every node it meets. As data gets passed from node to node, it eventually reaches all nodes, including the target node. The big advantage is that by trying every path, it's guaranteed to try the best path. The big disadvantage is the heavy use of resources, since every node has to carry every packet and deal with the associated transmission costs. PRoPHET wants the advantages of an epidemic protocol without paying the storage and communication price that basic epidemic protocols pay 💜 In other words, PRoPHET is an alternative to basic epidemic routing. It has lower demands on buffer space and bandwidth, equal or better performance where those resources are limited, and no loss of generality in scenarios where it's suitable to use PRoPHET 🫶
When PRoPHET applies, the patterns are expected to have a characteristic time (for example, the expected time between encounters between mobile stations). That characteristic time is related to how long traffic is expected to take to reach its destination in the part of the network that's using PRoPHET. This characteristic time guides how to configure PRoPHET in a network 🎀 When it's configured properly, PRoPHET effectively builds a local model of the expected patterns in the network. It then uses that model to optimize resource usage, by cutting down the traffic sent to nodes that are unlikely to lead to eventual delivery to the destination 💖
This document presents a framework for probabilistic routing in intermittently connected networks. It assumes non-random mobility of nodes in order to improve the delivery rate of messages, while keeping buffer usage and communication overhead low 🦋 First, it defines a probabilistic metric called delivery predictability. Then it goes on to define a probabilistic routing protocol that uses this metric ⭐
1.1. Relation to the Delay-Tolerant Networking Architecture
The Delay-Tolerant Networking (DTN) architecture [RFC4838] defines an architecture for communication in environments where traditional communication protocols can't be used because of excessive delays, link outages, and other extreme conditions 🌸 The intermittently connected networks discussed here are a subset of the ones covered by the DTN architecture. The DTN architecture computes routes based on a collection of "contacts," which indicate the start time, duration, endpoints, forwarding capacity, and latency of a link in the topology graph. Those contacts can be deterministic or derived from estimates. The architecture also defines several different types of intermittent contacts, and the ones called "opportunistic" and "predicted" are the ones this protocol addresses 🧚
Opportunistic contacts aren't scheduled. They just show up unexpectedly, and they frequently arise because of node mobility 👑 Predicted contacts are like opportunistic contacts, but based on some information, it might be possible to draw a statistical conclusion about whether a contact will be present soon 🔥
The DTN architecture also introduces the bundle protocol [RFC5050]. It gives applications a way to "bundle" an entire session, including data and metadata, into a single message (a bundle) that can be sent as one unit 🎁 The bundle protocol also provides end-to-end addressing and acknowledgments. PRoPHET is specifically meant to provide routing services in a network environment that uses bundles as its data transfer mechanism, though it could also be used in other intermittent environments 💅
1.2. Applicability of the Protocol ✨
okay so PRoPHET is mainly built for situations where at least some nodes are mobile in a way that creates connectivity patterns that aren't totally random over time 🦋 but actually have a degree of predictability. Nodes that switch off their radios to save power can make these patterns too. Human movement is a great example, since people tend to have daily or weekly routines, and PRoPHET is expected to apply there. It's not limited to humans though, so don't put it in a box 💅
For PRoPHET to actually benefit from that predictability in contacts between nodes, the network is expected to exist under similar circumstances over a longer timescale (in terms of node encounters). That way the predictability can be estimated accurately 🎀
The PRoPHET protocol expects nodes to be able to set up a local TCP link so they can swap the info PRoPHET needs. The signaling happens out-of-band over this TCP link, so the bundle protocol agent isn't involved [RFC5050]. BUT, PRoPHET is expected to talk to the bundle protocol agent to grab info about available bundles and to ask that a bundle get sent to another node. The associated bundle protocol agents are then expected to set up their own link (probably over the TCP convergence layer [CLAYER]) to actually move that bundle 🚚✨
TCP gives you a reliable, bidirectional channel between two peers and guarantees in-order delivery of whatever you send. Because of that guarantee, each category of information can be spread across several messages without the PRoPHET layer needing to wait until everything has arrived before starting the next category. At most, the last message of a category needs to be marked as such. This lets the receiver process earlier messages while it's still waiting for more, and it lets implementations keep messages small so IP fragmentation gets avoided and memory use can be tuned if needed 💖 That said, implementations MAY choose to build one message per category that's as big as it needs to be, and then rely on TCP to chop it up.
Now, PRoPHET is only defined to run over TCP for now, but future versions might send info over other transports. Those might not offer message segmentation or reliable, in-order delivery, and that's a whole different vibe 😭 The simple message division used with TCP MUST NOT be used when the underlying transport doesn't offer reliable, in-order delivery, because there would be no way to verify that all the messages arrived. So the protocol gives you a way to split protocol messages into submessages right in the PRoPHET layer. Submessages get sequence numbers, and together with a capability for positive acknowledgments, PRoPHET could run over an unreliable protocol like UDP or potentially straight over IP 🌈
Since TCP already offers reliable delivery, it is RECOMMENDED that the positive acknowledgment capability is not used when PRoPHET runs over TCP or a similar protocol. When running over TCP, implementations MAY safely ignore positive acknowledgments 🙈
Whatever transport is used, PRoPHET expects a bidirectional link for the information exchange. That means the exchange can happen in both directions over the same link, so nobody has to set up a second link just for the reverse direction 🔁
In a large Delay- and Disruption-Tolerant Network (DTN), network conditions can vary a lot, and different parts of the network might need different routing protocols. This specification only looks at routing within a single "PRoPHET zone", which is a set of nodes among which messages get routed using PRoPHET. Often a PRoPHET zone won't span the whole DTN, and other parts of the network with other characteristics will run other routing protocols. To handle that, there may be nodes inside the zone that act as gateways to other nodes that are destinations for bundles generated within the zone, or that insert bundles into the zone. So PRoPHET isn't necessarily used end-to-end, just within the regions of the network where it makes sense 🧚
1.3. PRoPHET as Compared to Regular Routing Protocols 💜
PRoPHET uses a way of pruning the epidemic forwarding tree that's similar to what metric-based vector routing protocols do (where the metric might be distance or cost). But it should NOT be confused with a metric vector protocol, okay? Different beast 🦋
In a traditional metric-based vector routing protocol, the info passed from node to node gets used to build a single non-looping path from source to destination that's optimal for the metric being used. That path is a set of directed edges picked from the complete graph of communication links between the nodes.
In PRoPHET, that info is used to prune the epidemic tree of paths by removing paths that look less likely to be an effective route for getting data to its intended destination. One result of this difference is that the regular notions of split horizon, as described in [RFC1058], do NOT apply to PRoPHET. Split horizon exists to stop a distance vector protocol from ever passing a packet back to the node that sent it, because the source is well known not to lie in that direction, as determined when the directed path was computed.
In an epidemic protocol, if the previous node already has the data, passing it back is redundant. The protocol can easily figure out that the transfer isn't needed 🙄 Also, given the mobility and constant churn of encounters in a DTN that's dominated by opportunistic encounters, it's quite possible that on a future encounter, that same node has become a better option for reaching the destination. A later encounter like that might need a re-transfer of the data if resource constraints caused the data to get deleted from the original carrier between encounters.
The logic of metric routing protocols doesn't map directly onto the family of epidemic protocols. In particular, it's inappropriate to assess epidemic protocols against the criteria used for conventional routing protocols like the metric vector protocols. That doesn't mean the epidemic family has no weaknesses, though. They just have to be considered on their own terms, separate from traditional protocols ✨
1.4. Requirements Notation 🎀
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119].
2. Architecture 🌸
2.1. PRoPHET 💅
This section gives an overview of the main architecture of PRoPHET, which is a Probabilistic Routing Protocol using History of Encounters and Transitivity. The protocol takes advantage of the fact that mobility patterns in lots of application scenarios aren't random, and uses that to improve routing performance. Instead of doing blind epidemic replication of bundles through the network like earlier protocols did, it uses "probabilistic routing" 🔥
To make this work, a metric called "delivery predictability", 0 <= P_(A,B) <= 1, is established at every node A for each known destination B. The metric is calculated so that a node with a higher value for a certain destination is estimated to be a better candidate for delivering a bundle to that destination. In other words, if P_(A,B)>P_(C,B), bundles for destination B are preferable to forward to A rather than C. It's used later when making forwarding decisions. Routes in a DTN are likely to be asymmetric, so the delivery predictability calculation reflects that, and P_(A,B) may be different from P_(B,A) 🦋
The delivery predictability values in each node change over time. They change because the metrics decay between encounters, and they also change during encounters, when the metric info for the encountered node gets updated to reflect the encounter and metric info about other nodes gets exchanged 🌈
When two PRoPHET nodes get a communication opportunity, they first go into a two-part Information Exchange Phase (IEP). In the first part, the delivery predictabilities for all destinations each node knows about get shared with the encountered node. Each node uses that exchanged info to update its internal delivery predictability vector, as described below. After that, the nodes exchange info (including destination and size) about the bundles each node is carrying. That info is used together with the updated delivery predictabilities to decide which bundles to request from the other node, based on the forwarding strategy in use (as discussed in Section 2.1.4). The bundles are actually forwarded in the latter part of the Information Exchange Phase 💖
2.1.1. Characteristic Time Interval ⏱️
When an application scenario makes PRoPHET applicable, the mobility pattern will show a characteristic time interval that reflects the distribution of time intervals between encounters between nodes. The evolution of the delivery predictabilities reflects this mobility pattern, so it should reflect that same characteristic time interval too. That means the parameters used in the equations that specify how delivery predictability evolves (see Section 2.1.2) need to be configured appropriately, so the evolution actually models the mobility pattern 🫶
2.1.2. Delivery Predictability Calculation ✨
okay so PRoPHET basically runs on a number that estimates how likely it is to bump into a certain node 🔮 and it uses that number to decide whether to forward a bundle to that node. 💖 this section is the math for how those numbers get updated whenever two nodes meet. in the equations, node A is the one doing the updating. P_(A,B) is the value node A will have stored for destination B after the encounter, and P_(A,B)_old is what it had stored before. if node A has nothing stored for B, then P_(A,B) is treated as zero. 🫶
there's also a special case: a node's value for itself is always 1 (P_(A,A)=1). 👑
the equations have a bunch of tunable parameters so they can match the mobility pattern of the PRoPHET zone the node lives in (see Section 2.1.1). recommended settings are in Section 3.3, and what happens when two nodes have different parameter settings is covered in Section 2.1.2.1. 🦋
the update during an encounter has three parts. 🌈
first up, when two nodes meet, they immediately update each other's delivery predictability, so that nodes you keep bumping into end up with a high value. 💅 if node B hasn't met node A in a long time, or has never met it, so that P_(A,B) < P_first_threshold, then P_(A,B) should be set to P_encounter_first. PRoPHET usually has no idea whether this is a one-off or the start of a regular thing, so P_encounter_first SHOULD be set to 0.5, unless the node has extra information from outside PRoPHET about how likely future encounters are. 🔥 otherwise, P_(A,B) gets calculated with Equation 1. here 0 <= P_encounter <= 1 is a scaling factor that sets how fast the predictability grows on encounters after the first one, and delta is a small positive number that effectively puts a ceiling on P_(A,B). the whole point is that predictabilities between different nodes stay strictly less than 1. 🧚 delta should normally be really tiny (like 0.01) so it doesn't squash the range of possible predictabilities, though you can pick a different value if it makes the calculations faster and that matters for you. ⭐
P_(A,B) =
P_(A,B)_old + ( 1 - delta - P_(A,B)_old ) * P_encounter (Eq. 1)okay, now the messy real-life part 🙈 sometimes one logical encounter (as in, the devices are close together and the humans think of it as one meeting) actually shows up as a bunch of communication opportunities squished together in time. for example, mobile nodes talking over Wi-Fi ad hoc mode can produce multiple "encounters" a short time apart, and that's usually just the wireless link being weird. transmission hiccups or tiny movements can make the devices reconnect over and over. 💀 in that case, it would be wrong to bump the delivery predictability up by the same amount for every single opportunity, the way you would for encounters spaced out across the normal mobility pattern.
to stop that from skewing things, P_encounter depends on the interval since the last encounter that actually updated the predictabilities. the shape of that function is in Figure 2. 🎀
P_encounter
^
|
P_encounter_max + - - .-------------------------------------
| /
| / .
| /
| / .
| /
| / .
|/
+-------+-------------------------------------> I
I_typ
Figure 2: P_encounter as function of time interval, I,
between updatesthe function is built so that both the increase from Equation 1 and the decrease from Equation 2 depend on the interval for short intervals. for intervals longer than the "typical" time between encounters (I_typ), P_encounter is fixed at P_encounter_max. that breakpoint is where the "normal" opportunities (from the overall mobility pattern) give way to the closely spaced ones (basically local side effects of the wireless tech). 🦋
P_encounter_max is picked so that the boost from Equation 1 clearly beats the decay from Equation 2 over a typical interval between encounters. 💜
this dependence on the interval also stops extra boosts from sneaking in when node A is talking to several other nodes at the same time. updates from each of those nodes have to be passed around, which can mean several updates land in a short window. this situation gets a closer look in Section 3.2.2. 😭
now, if a pair of nodes doesn't meet during an interval, they're less likely to be good forwarders for each other, so their predictability values need to age and go down. that's the second part of the update, and it uses the aging equation (Equation 2). here 0 <= gamma <= 1 is the aging constant, and K is the number of time units since the metric was last aged. the time unit can be different, and it should be defined based on the application and the delays you expect in the network you're targeting. 🍓
P_(A,B) = P_(A,B)_old * gamma^K (Eq. 2)the values get aged with Equation 2 before being handed to the node you just met, so they reflect how much time has gone by since that node last met anyone at all. 🌸 the aged results go to the encountered peer for the next step. on the receiving end, the aged values that node A got from node B are called P_(B,x)_recv. 🫶
last one: transitivity! 🧠 the idea is that if node A keeps meeting node B, and node B keeps meeting node C, then C is probably a solid node to forward bundles for A to. Equation 3 shows how this affects the delivery predictability, where 0 <= beta <= 1 is a scaling constant that controls how much impact transitivity has on the value. 👑
P_(A,C) = MAX( P_(A,C)_old, P_(A,B) * P_(B,C)_recv * beta ) (Eq. 3)node A uses Equation 3, plus the values it got from the encountered node B (for example P_(B,C)_recv), in the third part of updating its stored metric values. ✨
2.1.2.1. Impact of Encounters between Nodes with Different Parameter Settings 🎀
each node sets the parameters for the three equations from Section 2.1.2 on its own, so nodes configured with different values can absolutely meet each other. this section looks at whether that could be a problem for PRoPHET in a given zone. 🌈
it's ideal for every node in a PRoPHET zone to use closely matched values, and for those values to suit the zone they're operating in. more on picking good values is in Section 3.3. closely matched values mean the predictabilities evolve the same way on every node, which keeps decisions about which bundles to swap during encounters consistent. 💅
before getting into reasonable-but-different settings, a heads up: malicious nodes can use bad parameter settings to mess up bundle delivery in a PRoPHET zone, as described in Section 6. 🙈
the big, important takeaway is this: using different but legitimate settings on encountering nodes won't break the protocol itself. apart from P_encounter_first, the other parameters only control how fast the metric values change or limit the range of values that a node will store. none of the calculations in a node get invalidated or produce illegal values just because the values it received were calculated with different parameters. 🧚 on top of that, the protocol is designed so delivery predictabilities can't escape the allowed range of 0 to 1. 💖
a node MAY consider setting received values greater than (1 - delta) to (1 - delta) if that would make things simpler. 🍓 there are some special cases, though, where it can make sense for another node's delivery predictability to be 1. for example, if a DTN using PRoPHET has multiple gateways to the continuously connected Internet, then from one gateway's point of view, the other gateway nodes can be treated as 1, because they're permanently connected through the Internet. 🦋 that lets traffic get pushed into the DTN through the most advantageous gateway, even if it first shows up at a different gateway. 👑
simulation work shows the update calculations are pretty stable when the rate parameters change, so small differences won't have a big effect on how the protocol performs. ⭐ the protocol is specifically built to handle the randomness of opportunistic encounters, and that randomness is bigger than the parameter differences. 🌈
bigger differences might cause suboptimal behavior, because certain paths could be preferred or deprecated when they shouldn't be. 😭 still, since the protocol is epidemic overall, this won't usually stop bundles from being delivered. they also get passed on to other nodes and still arrive, just maybe not via the optimal path. 🫶
2.1.3. Optional Delivery Predictability Optimizations 🦋
2.1.3.1. Smoothing ✨
okay so, to give delivery predictability a smoother rate of change, a node MAY apply one of the following methods 🫶
- bestie, keep a list of
NUM_Pvalues for each destination instead of just one single value 📝 The recommended value is 4, which simulations showed gives a really good balance between smoothness and how fast it reacts to changes 🦋 The list is kept in order of acquisition. When a delivery predictability gets updated, the value sitting in the "newest" position is used as input to the equations in Section 2.1.2. Then the oldest value gets tossed out and the new value is written into the "newest" position 🗑️ When a delivery predictability value is needed (either to send to a peering PRoPHET node, or to make a forwarding decision), the average of the values in the list is calculated, and that average is what gets used 📊 If fewer thanNUM_Pvalues have been entered so far, only the positions that have actually been filled should be used for the averaging. no cap, that's a very fair rule 🙈 - in addition to keeping the delivery predictability the way Section 2.1.2 describes, a node MAY also keep an exponential weighted moving average (EWMA) of it 🌈 The EWMA is what gets used to make forwarding decisions and to report to peering nodes. BUT the value from Section 2.1.2 is still the thing that feeds into the calculations for new delivery predictabilities, so don't mix them up 💅 The EWMA is calculated with Equation 4, where
0 <= alpha <= 1is the weight of the most current value ✨
P_ewma = P_ewma_old * (1 - alpha) + P * alpha (Eq. 4)the right alpha can vary depending on the application scenario, periodt 💖 Unless you already know something about the scenario, it's suggested that alpha is set to 0.5 🎀
2.1.3.2. Removal of Low Delivery Predictabilities 🧹
so, to cut down on the data that has to be transferred between two nodes, a node MAY treat delivery predictabilities smaller than P_first_threshold as if they were zero 🫧 P_first_threshold is a small number, and those tiny values don't need to be stored or included in the list sent during the Information Exchange Phase. If you use this optimization, care must be taken to pick a P_first_threshold that is smaller than the delivery predictability values normally found in the network for destinations this node is a forwarder for 🚨 It's possible that P_first_threshold could be calculated from the delivery predictability ranges and how much they've changed historically, but nobody has looked into that yet 🌸
2.1.4. Forwarding Strategies and Queueing Policies 🚀
in traditional routing protocols, picking where to forward a message is usually super simple: the message goes to the neighbor with the lowest-cost path to the destination (often the shortest path) 🛣️ The message also normally goes to just one node, since paths are pretty reliable. BUT in the settings we're imagining here, things are totally different, it's giving chaos 😭 The first thing to consider when a bundle shows up at a node is that there might not be a path to the destination available, so the node has to buffer the bundle. Then, every time it meets another node, it has to decide whether or not to transfer a particular bundle 🧳 Also, having duplicates (on different nodes, since the bundle offer/request mechanism in Section 4.3.5 makes sure a node never receives a bundle it already carries) may be a smart move, because forwarding a bundle to multiple nodes can increase its delivery probability 💜
these decisions are not trivial to make, honestly 🥲 In some cases it might make sense to pick a fixed threshold and only hand a bundle to nodes whose delivery predictability for the bundle's destination is over that threshold. On the other hand, when you meet a node with a low delivery predictability, there's no guarantee you'll meet a node with a higher one in a reasonable amount of time. So there are also situations where you might want to be less strict about who gets bundles 🙃 And then there's the question of how many nodes should get a certain bundle. Giving it to a large number of nodes will of course increase the chance of delivering that bundle to its destination, but it costs more system resources for bundle storage and might reduce the chance of other bundles getting delivered 📦 On the flip side, giving a bundle to only a few nodes (maybe even just one) uses fewer resources, but the chance of delivery is lower and the delay is high 🐢
when resources are tight, nodes can run into storage shortages and may have to drop bundles before they've reached their destinations 💔 They may also want to check the length of a bundle an encountered node is offering before accepting it, either to avoid dropping the new bundle right away, or to make sure there's enough space to hold the offered bundle (which might mean other bundles have to be dropped) 🫣 Just like the decision about whether to forward a bundle, deciding which bundles to accept and/or drop while still keeping good performance might need different policies in different scenarios 🎯
Nodes MAY define their own forwarding strategies and queueing policies that take the special conditions of the node and its local resource constraints into account 👑 Some default strategies and policies that should be suitable for most normal operations are defined in Section 3.6 and Section 3.7 🌟
2.2. Bundle Protocol Agent to Routing Agent Interface 🎀
the bundle protocol [RFC5050] introduces the idea of a "bundle protocol agent," which manages the interface between applications and the "convergence layers" that transport bundles between nodes during communication opportunities 🧚 This spec extends the bundle protocol agent with a routing agent that controls what the bundle protocol agent does during an (opportunistic) communication opportunity 🦋
this spec defines the details of the PRoPHET routing agent, but the interface is more general, so it also works for other routing protocols too ✨
so the PRoPHET routing agent can operate properly, it has to know about the bundles stored at the node, and it has to be able to tell the node's bundle protocol agent to send a bundle to a peering node 💅 That means the bundle protocol agent needs to provide the following interface and functionality to the routing agent:
- Get Bundle List: returns a list of the stored bundles and their attributes to the routing agent 📋
- Send Bundle: makes the bundle protocol agent send a specified bundle 📤
- Accept Bundle: gives the bundle protocol agent a new bundle to store 📥
- Bundle Delivered: tells the bundle protocol agent that a bundle was delivered to its destination 🎉
- Drop Bundle Advice: advises the bundle protocol agent that a specified bundle shouldn't be offered for forwarding in future, and may be dropped by the bundle protocol agent if appropriate 🗑️
- Route Import: can be used by a gateway node in a PRoPHET zone to import reachability information about endpoint IDs (EIDs) that are external to the PRoPHET zone 🌍 Translation functions that depend on the external routing protocol will be used to set the appropriate delivery predictabilities for imported destinations, as described in Section 2.3 🔁
- Route Export: can be used by a gateway node in a PRoPHET zone to export reachability information (destination EIDs and their corresponding delivery predictabilities) for use by routing protocols in other parts of the DTN 📤✨
Implementation Note: depending on how the functions are distributed in a complete bundle protocol agent that supports PRoPHET, reception and delivery of bundles may not be carried out directly by the PRoPHET module 🧩 In that case, PRoPHET can tell the bundle protocol agent about bundles that have been requested from communicating nodes. Then the Accept Bundle and Bundle Delivered functions can be implemented as notifications to the PRoPHET module when the relevant bundles arrive at the node or get delivered to local applications 💌
2.3. PRoPHET Zone Gateways 🌐
PRoPHET is designed to handle routing mainly within a "PRoPHET zone," which is a set of nodes that all implement the PRoPHET routing scheme 💖 We know a PRoPHET routing zone is unlikely to cover an entire DTN, though, so there may be nodes inside the zone that act as gateways to other nodes. Those other nodes might be destinations for bundles generated within the zone, or they might insert bundles into the zone 🚪
PRoPHET MAY elect to export and import routes across a bundle protocol agent interface 🫶 The delivery predictability used for imported routes depends on the routing protocol used to manage those routes. If a translation function exists between the external routing protocol and PRoPHET, it SHOULD be used to set the delivery predictability 🧮 If no such translation function exists, the delivery predictability SHOULD be set to 1 💯 For routes that are exported, the current delivery predictability is exported along with the route 🎁
2.4. Lower-Layer Requirements and Interface 🎀
okay so PRoPHET can run on a huge range of underlying networking technologies, bestie 🌈 which means it needs the lower layers to hand it some specific functionality and interfaces. no cap, this is the part where PRoPHET says "hey, you gotta provide these for me" 💅
Neighbor discovery and maintenance
PRoPHET needs to know who its neighbors are, and when new neighbors show up or old ones disappear 👀 some wireless technologies already have mechanisms for detecting neighbors and keeping track of that state, so PRoPHET doesn't want to redo the work and create redundancies and inefficiencies 🙈 so neighbor discovery is NOT part of PRoPHET itself. instead, PRoPHET relies on that mechanism sitting in the lower layers. the lower layers MUST provide the two functions below. 🫶
if the underlying networking technology doesn't support these services, a simple neighbor discovery scheme using local broadcasts of beacon messages could be run in between PRoPHET and the underlying layer ✨ there's an example of a simple neighbor discovery mechanism in Appendix B, so go check it out, it's giving helpful 🧚
- New Neighbor: this signals to the PRoPHET agent that a new node has become a neighbor 💖 a neighbor here means another node that is currently within communication range of the wireless networking technology in use. once this happens, the PRoPHET agent should now start the Hello procedure described in Section 5.2 🦋
- Neighbor Gone: this signals to the PRoPHET agent that one of its neighbors has left 🌸
Local Address
this is an address used by the underlying communication layer (think an IP or Media Access Control (MAC) address 💜) that identifies the sender address of the current message. it's lowkey important: this address must be unique among the nodes that can currently communicate, and it's only used together with an Instance Number to identify a communicating pair of nodes, as described in Section 4.1 ✨ the address and its format depend on whichever communication layer the PRoPHET layer is using, so it's not one-size-fits-all 🌈
3. Protocol Overview 🦋
okay the PRoPHET protocol has two principal phases and honestly they're both giving main character energy 👑
- becoming aware of new neighbors that implement the protocol and setting up a point-to-point connection between each pair of encountering nodes, and
- using that connection for the information exchange needed to establish PRoPHET routing and to exchange bundles 💅
3.1. Neighbor Awareness 👀
so the whole protocol depends on nodes running PRoPHET actually encountering each other, which means the nodes have to be able to detect when a new neighbor is present 🫶 PRoPHET can run over several different networking technologies, and some of them already have ways to detect neighbors, so PRoPHET does NOT include its own neighbor discovery mechanism 🙅 instead, it requires the underlying layer to provide a way to notify the protocol when neighbors appear and disappear, as described in Section 2.4 🔥
when a new neighbor is detected, the protocol starts setting up a link with that node through the Hello message exchange described in Section 5.2 💖 this exchange lets neighbors negotiate capabilities. right now there's only one capability: a request that the offering node should or should not include bundle payload lengths with all offered bundles, rather than just for fragments 🎀 once the link is set up, the protocol may continue to the Information Exchange Phase (see Section 3.2) ✨ after that's done, the nodes will normally recalculate the delivery predictabilities using the equations and mechanisms in Sections 2.1.2 and 2.1.3 🌸
now here's the tea 🍓 as described in Section 2.1.2, one logical encounter can sometimes turn into several actual communication opportunities. to stop the delivery predictability of the encountered node from getting boosted excessively in that situation, the value of P_encounter depends on the interval time between delivery predictability updates when that interval is shorter than the typical interval between encounters. for longer intervals, it's just a constant 💜
to make use of this time dependence, PRoPHET keeps a list of recently encountered nodes. each entry is identified by the Endpoint Identifier (EID) the node uses to identify the communication session, and holds the start time of the last communication session with that node 🦋 the size of this list is controlled: nodes that aren't in contact and whose last connection started more than a time I_typ before the present can be dropped from the list 🧚 PRoPHET also keeps a record of the time at which the decay function (Equation 2) was last applied to the delivery predictabilities in the node 💅
3.2. Information Exchange Phase 🫶
the Information Exchange Phase has two parts 🔥
- establishing the Router Information Base (RIB Exchange Sub-Phase), and
- exchanging bundles using this information (Bundle Passing Sub-Phase) ✨
there are four types of information exchanged during this process 🌈
- Routing Information Base Dictionary (RIB Dictionary or RIBD) 📖
- Routing Information Base (RIB) 📚
- Bundle Offers 🎁
- Bundle Responses 💌
during a communication opportunity, several sets of each type of information may be transferred in each direction, as the rest of this section explains 💖 each set can go in one or more messages. when (and only when) using a connection-oriented reliable transport protocol such as TCP, as this document envisages, a set can be partitioned across messages by the software layer above the PRoPHET protocol engine 🦋
in that case, the last message in a set is flagged in the protocol 🚩 this lets the higher-level software keep its buffer memory needs low, since it doesn't have to build super large messages in one go, and it lets the message size be controlled outside of PRoPHET 🙌 BUT this scheme is only usable if the transport protocol provides reliable, in-order delivery of messages. the messages aren't explicitly sequence numbered, and the overall size of the set isn't passed explicitly, so it needs that guarantee 😭
PRoPHET also has a submessage mechanism and retransmission that lets large messages specified by the higher level be sent in smaller chunks 🧩 this was originally provided so PRoPHET could work over unreliable transport protocols such as UDP, but it can also be used with reliable transports if the higher-level software doesn't want to handle message fragmentation itself 🎀 the catch is that the sequencing and length add overhead that's redundant when the transport protocol already provides reliable, in-order delivery 🙈
the first step in the Information Exchange Phase is for the protocol to send one or more messages containing a RIB Dictionary TLV (Type-Length-Value message component) to the node it's peering with 📖 this set of messages contains a dictionary of the Endpoint Identifiers (EIDs) of the nodes that will be listed in the Routing Information Base (RIB). see Section 3.2.1 for more about this dictionary 💜 after that, one or more messages containing a Routing Information Base TLV are sent 📚 this TLV contains a list of the EIDs the node has knowledge of, the corresponding delivery predictabilities for those nodes, and flags describing the capabilities of the sending node 🌸
when a complete set of these messages is received, the peer node updates its delivery predictability table according to the equations in Section 2.1.2 🧠 then the peer node applies its forwarding strategy (see Section 2.1.4) to decide which of its stored bundles it wants to offer the node that sent the RIB 💅 that node will then be the receiver for any bundles to be transferred 🦋
after making that decision, one or more Bundle Offer TLVs are prepared, listing the bundle identifiers and their destinations for all bundles the peer node wishes to offer to the receiver node that sent the RIB 🎁 as described in [RFC5050], a bundle identifier is made of up to five component parts 🔍 for a complete bundle, the identifier consists of:
- source EID,
- creation timestamp - time of creation, and
- creation timestamp - sequence number.
for a bundle fragment, the identifier also contains:
- offset within the payload at which the fragment payload data starts, and
- length of the fragment payload data. 🧩
if any Bundle Offer TLV lists a bundle whose source or destination EID wasn't included in the previous set of RIBD information sent, one or more new RIBD TLVs get sent next with an incremental update of the dictionary 📖 once the receiver node has a dictionary with all the EIDs it needs, the Bundle Offer TLVs get sent to it 💌 the Bundle Offer TLVs also contain a list of PRoPHET ACKs (see Section 3.5) 🙌 if the receiver node requested it during the Hello phase, the Bundle Offer TLV will also specify the payload length for all bundles, not just for fragments 📏 this helps the receiving node pick which offered bundles to accept, especially when its available bundle storage is limited 🫶
the receiving node then looks through the list of offered bundles and selects the ones it will accept according to its own policies, taking into account the bundles already in the node and the current availability of resources 💅 the list gets sorted by the priority the policies assign to the selected bundles, with the highest priority bundle first, and the offering node forwards the selected bundles in that order ✨ the prioritized list is sent back to the offering node in one or more Bundle Response TLVs, using the same EID dictionary as the Bundle Offer TLV 🎀
when a new bundle arrives at a node, the node MAY inspect its list of available neighbors. if one of them is a candidate to forward the bundle, a new Bundle Offer TLV MAY be sent to that node 🦋 and if two nodes stay connected for a longer period of time, the Information Exchange Phase gets periodically re-initiated so new delivery predictability information can spread through the network and new bundle exchanges can happen 🌈
the Information Exchange Phase is described in more detail in Section 5.3 🧚
3.2.1. Routing Information Base Dictionary 📖✨
okay bestie, so to keep the protocol lean and not waste bandwidth 🦋, the Routing Information Base and Bundle Offer/Response TLVs use an EID dictionary. ngl it's so smart. It maps variable-length EIDs (as defined in [RFC4838]), which can get pretty long 😭, to shorter numerical identifiers. Those identifiers are coded as Self-Delimiting Numeric Values (SDNVs -- see Section 4.1. of RFC 5050 [RFC5050]), and then the short IDs get used in place of the full EIDs in later TLVs 💅.
The dictionary is a shared resource between the two peering nodes 🫶. Either node can add to it by sending a RIB Dictionary TLV to its peer. To let either one add at any time without stepping on each other, the identifiers come from disjoint sets. IDs originated by the node that started the Hello procedure have the least significant bit set to 0 (aka even numbers), and IDs originated by the other peer have it set to 1 (aka odd numbers) 🌈. So the dictionary can grow at any point in the Information Exchange Phase, and the new IDs can be used in later TLVs until the dictionary is re-initialized ✨.
The dictionary only lasts through a single encounter with a node (i.e., while the same link set up by the Hello procedure, with the same instance numbers, stays open) 🎀.
Having more than one ID for the same EID is totally fine 🙈. It's possible for the peers to build their dictionary entries independently if an implementation needs that, but it may be inefficient, since an entry for an EID might get sent in both directions 🤷♀️. Implementers can choose to inspect entries sent by the node that started the Hello procedure and eliminate any duplicates before sending the other peer's entries. Whether postponing the other peer's entries is more efficient depends on the physical link technology and the transport protocol used. With a genuinely full-duplex link, it may be faster to accept possible duplication and send dictionary entries concurrently in both directions ⚡. If the link is effectively half-duplex (e.g., Wi-Fi), it will generally be more efficient to wait and eliminate duplicates 📶.
If a node receives a RIB Dictionary TLV containing an identifier that is already in use, the node MUST confirm that the EID referred to is identical to the EID in the existing entry. Otherwise, the node must send an error response to the message with the TLV containing the error and ignore the TLV containing the error. If a node receives a RIB, Bundle Offer, or Bundle Response TLV that uses an identifier that is not in its dictionary, the node MUST send an error response and ignore the TLV containing the error. 🚨
3.2.2. Handling Multiple Simultaneous Contacts 🌸
From time to time, a mobile node may, for example, be in wireless range of more than one other mobile node 📱. The PRoPHET neighbor awareness protocol will establish multiple simultaneous contacts with these nodes and kick off information exchanges with each of them 🤝.
When updating the delivery predictabilities as described in Section 2.1.2 using the values passed from each of the contacts in turn, a few special considerations apply when multiple contacts are in progress 👀:
- SC1: When aging the delivery predictabilities according to Equation 2, the value of K to be used in each set of calculations is always the amount of time since the last aging was done. For example, if node Z makes contact with node A and then with node B, the value of K used when the delivery predictabilities are aged in node Z for the contact with node B will be the time since the delivery predictabilities were aged for the contact with node A ⏰.
- SC2: When a new contact starts, the value of P_encounter used when applying Equation 1 for the newly contacted node is always selected according to the time since the last encounter with that node. Thus, the application of Equation 1 to update P_(Z,A) when the contact of nodes Z and A starts (in the aging example just given) and the updating of P_(Z,B) when the contact of nodes Z and B starts will use the appropriate value of P_encounter according to how long it has been since node Z previously encountered node A and node B, respectively 💖.
- SC3: If, as with the contact between nodes Z and B, there is another active contact in progress, such as with node A when the contact with node B starts, Equation 1 should also be applied to P_(z,x) for all the nodes "x" that have ongoing contacts with node Z (i.e., node A in the example given). However, the value of P_encounter used will be selected according to the time since the previous update of the delivery predictabilities as a result of information received from any other node. In the example given here, P_(Z,A) would also have Equation 1 applied when the delivery predictabilities are received from node B, but the value of P_encounter used would be selected according to the time since the updates done when the encounter between nodes Z and A started, rather than the time since the previous encounter between nodes A and Z 🧩.
If these simultaneous contacts persist for some time, then, as described in Section 3.2, the Information Exchange Phase will be periodically rerun for each contact according to the configured timer interval ⏲️. When the delivery predictability values are recalculated during each rerun, Equation 1 will be applied as in special consideration SC3 above, but it will be applied to the delivery predictability for each active contact using the P_encounter value selected according to the time since the last set of updates were performed on the delivery predictabilities, irrespective of which nodes triggered either the previous or current updates. This means that, in the example discussed here, P_(Z,A) and P_(Z,B) will be updated using the same value of P_encounter whether node A or node B initiated the update while the three nodes remain connected 🫧.
The interval between reruns of the information exchange will generally be set to a small fraction of the expected time between independent encounters of pairs of nodes 🕰️. This ensures that, for example, the delivery predictability information obtained by node Z from node A will be passed on to node B whether or not nodes A and B can communicate directly during this encounter. This avoids problems that may arise from peculiarities of radio propagation during this sort of encounter 📡. The scaling of the P_encounter factor according to the time between updates of the delivery predictabilities means that the predictabilities for the nodes that are in contact are not increased excessively, as would be the case if each information exchange were treated as a separate encounter with the value of P_encounter_max used each time 🛑. When several nodes are in mutual contact, the delivery predictabilities in each node stabilize after a few exchanges, due to the scaling of P_encounter as well as the form of Equation 3, where a "max" function is used 📈. This has been demonstrated by simulation 🧪.
The effect of the updates of the delivery predictabilities when there are multiple simultaneous contacts is that the information about good routes on which to forward bundles is correctly passed between sets of nodes that are simultaneously in contact, through the transitive update of Equation 3 during each information exchange. But the delivery predictabilities for the direct contacts are not exaggerated 👑.
3.3. Routing Algorithm 🦋
okay so the basic routing algorithm is explained back in Section 2.1 💅 It uses a bunch of parameter values to calculate the delivery predictability metric. You can tune these based on your usage scenario, but Figure 3 has some recommended defaults 🎀 Below is a quick rundown of each parameter and some tips on picking good values.
I_typ
I_typ is the fundamental timescale for the mobility pattern in the PRoPHET scenario you're using 🕰️ It's the typical or mean time between encounters for a pair of nodes during normal movement. The interval should reflect the "logical" time between encounters, and it shouldn't give much weight to multiple connection events, as Section 2.1.2 explains 🙈 I_typ sets up a lot of the other parameters, but you don't usually plug it in directly.
You also need to think beyond the mean. The higher statistical moments (like standard deviation) matter, and so does the shape of the distribution of intervals between encounters, like how close it is to a normal distribution 📊 We dig into this more later in this section and in Appendix C, so stay tuned 💜
P_encounter_max
P_encounter_max is the upper limit of a scaling factor that boosts the delivery predictability for a destination when you encounter that destination node 🚀 A bigger value means predictability climbs faster, so you need fewer encounters to hit a certain level. Since the forwarding mechanisms care about relative predictabilities and not absolute ones, PRoPHET is super robust to different P_encounter values, as long as every node uses the same value 🫶 Pick a value where the bump from P_encounter_max in Equation 1 more than makes up for the decay from Equation 3 over a time interval of I_typ 💖
P_encounter(intvl)
Section 2.1.2 explains that the P_encounter used in Equation 1 is a function of the time interval intvl 🧚 The function should approximate this:
P_encounter(intvl) =
P_encounter_max * (intvl / I_typ) for 0<= intvl <= I_typ
P_encounter_max for intvl > I_typYou can quantize it and tweak it to fit your mobility pattern, which also makes implementation easier 🍓 The big idea is this: if you apply Equation 1 a bunch of times during one long communication opportunity that lasts I_typ, the total boost to delivery predictability should be roughly the same as if there had been two separate encounters spaced I_typ apart. That second case means one application of Equation 1 using P_encounter_max ✨
P_first_threshold
As Section 2.1.2 describes, delivery predictability for a destination slowly fades over time unless direct encounters or the transitive property bump it back up 🌸 If it drops below P_first_threshold, the node MAY throw out the predictability info for that destination and treat future encounters like it never met that node before 🗑️ This keeps storage small and cuts down on how much info gets swapped between nodes. Without it, the decay would leave tiny but nonzero predictabilities hanging around for nodes that were last seen ages ago, which is just clutter 🙄
P_encounter_first
Here's the thing, PRoPHET doesn't assume anything by default about whether an encountered node will show up again 🤷♀️ Maybe it'll be a regular, maybe it's a one-off chance meeting. So when an encountering node has no predictability info for the encountered destination, which happens either on a true first meeting or because the old info decayed below P_first_threshold and got discarded, it sets the predictability to P_encounter_first 🎯 The suggested value is 0.5. That's RECOMMENDED as the sensible default when you don't have any extra (like out-of-band) info about whether future encounters with that node will be regular 💅
alpha
alpha is used in the optional smoothing of delivery predictabilities from Section 2.1.3.1 🧈 It sets how much weight the most current P-value gets when calculating an EWMA.
beta
beta controls how much weight the transitive property of PRoPHET gets. In other words, how much you trust info about destinations that came from nodes you've encountered 🤝 If beta is zero, the transitive property is basically switched off, and only direct encounters count toward delivery predictability 🚫 The higher beta is, the faster encounters bump up predictabilities through the transitive rule ⚡
gamma
gamma decides how quickly delivery predictabilities age 🥀 A lower gamma means predictabilities age faster. You should choose it based on your scenario and environment. If encounters are expected to be super frequent, go with a lower gamma than you would if encounters are rare 🌧️
delta
delta sets the maximum delivery predictability for any destination other than the node itself (so P_(A,B) for every case except P_(A,A)) as (1 - delta) 👑 You want delta to be small so you get the widest possible range for predictabilities, though you can bump it up if you need to make the calculations more efficient 🧮
To pick a good gamma, think about the "average expected delivery" time I_aed in the PRoPHET zone where you're deploying the protocol, plus the time unit you're using (the resolution at which delivery predictability gets updated) ⏱️ You can estimate I_aed from the average number of hops bundles need to take and the average interval between encounters, I_typ 🧠 Here's the catch: if a bundle's TTL (the time left until the expiry time stored in the bundle) is less than I_aed, it's unlikely to survive long enough to reach a node in this zone 💀 Still, don't set TTLs for bundles created in this zone based on that alone, because those bundles might travel through other networks 🌍
Once you've got I_aed, pick how much you want predictability to age over one I_aed period (call that A). Then work out K, the number of time units in one I_aed, using K = (I_aed / time unit). Finally, compute gamma = K'th-root( A ) 🎉
Now I_typ, I_aed, K, and gamma can help you set P_encounter_first, P_encounter_max, P_first_threshold, delta, and the detailed form of the P_encounter(intvl) function 🧩
Let's start with one encounter. After a single meeting between nodes A and B, P_(A,B) gets set to P_encounter_first and then steadily decays until it hits P_first_threshold 📉 Pick the ratio between those two so P_first_threshold is reached after a small multiple (say 3 to 5) of I_aed. That way, a follow-up encounter will likely happen before P_(A,B) drops below P_first_threshold 🤞 If you know the statistics of the time between encounters, a small multiple of the standard deviation could be used instead of a multiple of I_aed 📐
Next up, a second encounter between A and B. P_encounter_max should be high enough to undo the decay that would've happened over I_typ, and push P_(A,B) above P_encounter_first 💪 After several more encounters, P_(A,B) reaches (1 - delta), its upper limit 🏆 Just like with P_first_threshold, you want that upper limit reached after a small number of encounters spaced I_typ apart. But it should generally take more than 2 or 3 of them 🙌
Last but not least, beta can be picked to smooth out how much transitivity influences things 🌊
Heads up: these instructions are only one possible way to pick values, and network operators can set parameters however they want 🫡 Appendix C goes deeper into linking the parameters here with the more conventional ways of describing a mobility model, using distributions of times between events of different types 📚
If you haven't done specific network measurements yet, here are the recommended starting values. There's no "one size fits all," and the ideal numbers depend on your network 🙅♀️ The parameters don't have to match at every node, but it's recommended that similar values are used at all nodes within a PRoPHET zone, as Section 2.1.2.1 covers 🫶
+========================================+
| Parameter | Recommended value |
+========================================+
| P_encounter_max | 0.7 |
+----------------------------------------+
| P_encounter_first | 0.5 |
+----------------------------------------+
| P_first_threshold | 0.1 |
+----------------------------------------+
| alpha | 0.5 |
+----------------------------------------+
| beta | 0.9 |
+----------------------------------------+
| gamma | 0.999 |
+----------------------------------------+
| delta | 0.01 |
+========================================+
Figure 3: Default parameter settings3.4. Bundle Passing ✨
okay so once a node gets the Bundle Offer TLV, it looks through the list and decides which bundles it's willing to hold onto for later forwarding, or which ones it can deliver to their destinations right now 📦. That call is made with local policies, and it takes stuff like free buffer space into account, plus the lengths of the offered bundles if the node asked for lengths. For every bundle it likes, the node sends a Bundle Response TLV back to its peering node, and the peer replies by sending the bundle it asked for 💌. If there are some bundles the node would rather get first (say, ones it can deliver straight to the final destination), it MAY request them in that priority order 👑. This is super useful because there's no guarantee the two nodes stay in contact long enough to move every acceptable bundle 🥺. If the node doesn't have its own preference, it SHOULD assume the bundles are already listed in the priority order set by the peering node's forwarding strategy, and request them in that order 🧚.
3.4.1. Custody
okay custody is the vibe where a node can hand off responsibility for a bundle to another node that offers custody 🎀. A node might do this to free up its own local resources, and the goal is to push the retransmission duty closer to the destination 🌸. The whole concept of custody transfer, plus the motivation behind it, is explained in [RFC4838] 📚. PRoPHET takes zero responsibility for custody decisions 🙅♀️. Those choices belong to a higher layer, bestie 💅.
3.5. When a Bundle Reaches Its Destination
a PRoPHET ACK is only a confirmation that a bundle got delivered to its destination inside the PRoPHET zone 🦋. (Bundles can travel through a bunch of different network types running different routing protocols, so that zone destination might not actually be the final destination 🫠.) When nodes swap Bundle Offer TLVs, the bundles that have already been ACKed show up too, with the "PRoPHET ACK" flag set ✨. The receiving node updates its own ACKed list so it becomes the union of its old list and the new one 🤝. And to stop that list from growing forever, each PRoPHET ACK should have a timeout that MUST NOT be longer than the timeout of the bundle it's ACKing ⏳. no notes, just a hard rule 💀.
When a node gets a PRoPHET ACK for a bundle it's carrying, it MAY delete that bundle from storage, unless the node is holding custody of it 🗑️. Remember, a PRoPHET ACK only means the bundle reached its destination within the PRoPHET zone, so getting one is NOT a guarantee the bundle reached its final destination 🙈. (Very important, iykyk.)
Nodes MAY keep track of which nodes they've sent PRoPHET ACKs to for certain bundles, and in that case they MAY skip sending the same PRoPHET ACK to the same node more than once 🧾.
If a node needs to save system resources, it MAY drop PRoPHET ACKs early, but it SHOULD hold off on that whenever it can 🫶.
It's really important to keep these two things straight: PRoPHET ACKs and bundle ACKs [RFC5050] are not the same thing 😭. PRoPHET ACKs only count inside the PRoPHET part of the network, while bundle ACKs are end-to-end acknowledgments that can go way beyond the PRoPHET zone 🌈.
3.6. Forwarding Strategies
during the Information Exchange Phase, nodes have to figure out which bundles they want to swap with the peering node 🔄. PRoPHET gets used in a ton of different scenarios on a huge range of devices, so it's not guaranteed that every node makes this call with the same strategy 🌍. That's why each node MUST operate a _forwarding strategy_ to make the decision 💖. Nodes may come up with their own strategies, but this section lists a few basic ones they can use 🍓. Note: if the node being encountered is the destination for any of the bundles being carried, those bundles SHOULD be offered to it, even if that breaks the forwarding strategy 🚨. Some of the strategies here were tested through simulations (along with a bunch of queueing policies), and you can find more info, plus recommendations on which strategies fit which situations, in [lindgren_06] 📊. Unless the deployment scenario's characteristics call for something else, nodes SHOULD go with GRTR as their default forwarding strategy 👑.
The short names for these strategies are just mnemonic handles, not acronyms for any specific set of words in the spec 🧸.
Here's the notation we use below 📝. A and B are the nodes meeting each other, and each strategy is described the way node A would apply it. The destination node is D. P_(X,Y) is the delivery predictability stored at node X for destination Y, and NF is the number of times node A has given the bundle to some other node 🔢.
GRTR Forward the bundle only if P_(B,D) > P_(A,D).
When two nodes meet, a bundle gets sent to the other node if the bundle's destination has a higher delivery predictability there 🚀. The first node doesn't delete the bundle after sending it, as long as there's enough buffer space, since it might run into a better node or even the final destination later on 🌟.
GTMX Forward the bundle only if P_(B,D) > P_(A,D) && NF < NF_max.
This one's basically the same as the last, except each bundle can only be handed to at most NF_max other nodes, on top of the destination 🎯.
GTHR Forward the bundle only if P_(B,D) > P_(A,D) OR P_(B,D) > FORW_thres, where FORW_thres is a threshold value above which a bundle should always be given to the node, unless it's already there 💫.
It's similar to GRTR, but among nodes with really high delivery predictability, bundles for that destination get spread epidemically 🦠✨.
GRTR+ Forward the bundle only if Equation 5 holds, where P_max is the largest delivery predictability reported by a node the bundle has been sent to so far.
P_(B,D) > P_(A,D) && P_(B,D) > P_max (Eq. 5)This is like GRTR, but every node forwarding a bundle keeps track of the highest delivery predictability among the nodes it has already sent that bundle to 📈. It only forwards the bundle again if the node it's currently meeting has a predictability higher than that previous max 🧠.
GTMX+ Forward the bundle only if Equation 6 holds.
P_(B,D) > P_(A,D) && P_(B,D) > P_max && NF < NF_max (Eq. 6)This is GTMX, but nodes also track P_max the way GRTR+ does 💜.
GRTRSort Select bundles in descending order of the value of P_(B,D) - P_(A,D). Forward the bundle only if P_(B,D) > P_(A,D).
This is like GRTR, except instead of just walking through the bundle queue in a straight line, it looks at the difference in delivery predictability for each bundle between the two nodes and sends the ones with the biggest gap first 🏃♀️💨. Since bandwidth limits or dropped connections can mean not every desirable bundle gets swapped, it can make sense to send the bundles that get the biggest boost in delivery predictability first 🎀.
GRTRMax Select bundles in descending order of P_(B,D). Forward the bundle only if P_(B,D) > P_(A,D).
This one starts by looking at the bundles for which the encountered node has the highest delivery predictability 👑. The reasoning is the same as GRTRSort, but the idea is that it's better to hand bundles to nodes with high absolute delivery predictabilities, rather than chasing the biggest improvement 🌹.
3.7. Queueing Policies 🎀
Okay so, nodes only have so much buffer space, which means they sometimes have to drop bundles 🥺 And just like with forwarding strategies, which bundle gets dropped depends on the scenario 💅 That's why every node MUST also operate a queueing policy that decides how its bundle queue gets handled ✨ This section defines a few basic queueing policies, but nodes MAY use other policies if they want 🦋
Some of these have been tested in simulations, together with a bunch of forwarding strategies 📊 If you want the full tea and some recommendations on which policies to use in which situations, check out [lindgren_06] 📚 Unless the characteristics of the deployment scenario push you somewhere else, nodes SHOULD choose FIFO as their default queueing policy 🌸
The short names below are mnemonic handles, not secret acronyms for specific words in the spec 🤫
FIFO - First In First Out. 🚪 The bundle that got into the queue first is the first one to be dropped. Literally first come, first dropped 😭
MOFO - Evict most forwarded first. 🔁 To try to maximize the delivery rate of bundles, this policy has the routing agent keep track of how many times each bundle has been forwarded to some other node. The bundle that's been forwarded the largest number of times is the first to get the boot 👢
MOPR - Evict most favorably forwarded first. 💜 Keep a variable FAV for each bundle in the queue, starting at zero. Every time the bundle gets forwarded, update FAV using Equation 7, where P is the predictability metric that the node the bundle is forwarded to has for its destination 🧮
FAV_new = FAV_old + ( 1 - FAV_old ) * P (Eq. 7)The bundle with the highest FAV value is the first to be dropped ✨
Linear MOPR - Evict most favorably forwarded first; linear increase. 📈 Same vibe as MOPR, but the update is linear 🌈 Keep a variable FAV for each bundle in the queue, initialized to zero. Each time the bundle is forwarded, update FAV using Equation 8, where P is the predictability metric that the node the bundle is forwarded to has for its destination 💖
FAV_new = FAV_old + P (Eq. 8)The bundle with the highest FAV value is the first to be dropped 👑
SHLI - Evict shortest life time first. ⏳ As described in [RFC5050], each bundle has a timeout value that says when it stops being meaningful to its application and should be deleted. Bundles with a short remaining Time To Live are going to get dropped soon anyway, so this policy drops the one with the shortest remaining lifetime first 💀 To make this work, nodes need some form of time synchronization so they can actually know the exact lifetimes of bundles. But honestly that's not specific to this routing protocol, it's a more general DTN problem 🙈
LEPR - Evict least probable first. 🎯 A node is least likely to deliver a bundle it has a low delivery predictability for, so this policy drops the bundle for which the node has the lowest delivery predictability, and that has already been forwarded at least MF times. MF is the minimum number of forwards a bundle must have been forwarded before it can be dropped (if such a bundle exists) 🧠
You're allowed to stack queueing policies into an ordered set 🧚 More than one queueing policy MAY be combined this way, where the first policy does the main work, the second one only gets involved if the primary policy needs a tie-break between bundles with the same eviction priority, and so on 🫶 For example, you could pick {MOFO; SHLI; FIFO}. That would start by dropping the bundle that's been forwarded the largest number of times 🔥 If more than one bundle has been forwarded that same number of times, the one with the shortest remaining lifetime gets dropped. And if that's also a tie, FIFO kicks in and drops the bundle that was received first 🎀
⚠️ Important, bestie: a node MUST NOT drop bundles for which it has custody unless the bundle's lifetime expires. Custody bundles are off-limits until their time is up 🫢
4. Message Formats 💌
This section defines the message formats of the PRoPHET routing protocol 💅 To allow for variable-length fields, a lot of the numeric fields are encoded as Self-Delimiting Numeric Values (SDNVs) 🧮 The format of SDNVs is defined in [RFC5050]. Since so many fields are coded as SDNVs, the sizes and alignment of fields shown in many of the diagrams below are indicative rather than prescriptive 📐 Wherever SDNVs and/or text strings are used, the octets of the fields get packed as closely as possible, with no padding in between fields 🧩
Explicit-length fields are specified for every variable-length string field 🌷 So strings are not null terminated. They just contain the exact set of octets in the string 🫧
The basic message format shown in Figure 4 is a header (see Section 4.1) followed by one or more Type-Length-Value components (TLVs) taken from the specifications in Section 4.2 🎁
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ Header ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ TLV 1 ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| . |
~ . ~
| . |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ TLV n ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 4: Basic PRoPHET Message Format4.1. Header 💖
okay so the header is literally the first thing every PRoPHET message shows up with, so it's giving main character energy 👑 Here's the layout:
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|Protocol Number|Version| Flags | Result | Code |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Receiver Instance | Sender Instance |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Transaction Identifier |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|S| SubMessage Number | Length (SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ Message Body ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 5: PRoPHET Message HeaderProtocol Number 🧚
The DTN Routing Protocol Number is an 8-bit unsigned integer in network bit order, and its value is 0. The PRoPHET header is laid out this way so that, in principle, PRoPHET messages could be sent as the Protocol Data Unit of an IP packet, if an IP protocol number ever got allocated for PRoPHET. 🦋
right now PRoPHET is only specified to ride over a TCP transport, so the protocol number just identifies PRoPHET inside DTN. Sending PRoPHET packets straight as an IP protocol on a public network like the Internet would generally not work well 💀 Middleboxes (firewalls and NAT boxes) would be unlikely to let it through, and the protocol doesn't provide any congestion control. It could be done on private networks for experiments, or where everything is between isolated pairs of nodes. And later on, other protocols that need to carry metadata between DTN nodes could potentially reuse the same format and state machinery, just with a different Protocol Number ✨
Version 🎀
The version of the PRoPHET Protocol, encoded as a 4-bit unsigned integer in network bit order. This document defines version 2. Iconic 👑
Flags 🫶
Reserved field of 4 bits. Nothing to see here, bestie 🙈
Result 💅
This field says whether a response is needed for a request message when the outcome is successful. A value of "NoSuccessAck" means the request doesn't expect a response if things go well, while "AckAll" means a response is expected when things go well. In both cases, a failure response MUST be generated if the request fails. Not optional, periodt 🔥
If you're running over TCP or a similar protocol that already offers reliable, in-order delivery, deployments MAY choose not to send "Success" responses when an outcome is successful. To do that, the Result field gets set to the "NoSuccessAck" value in all request messages 🌈
In a response message, the Result field can have two values: "Success" and "Failure". "Success" marks a success response. Every message that belongs to the same success response has the same Transaction Identifier. "Success" can show up in a single message, or in the final message of a success response that spans multiple messages ⭐
ReturnReceipt is the Result value that says an acknowledgement is required for the message. By default, the controller will not acknowledge responses. If an acknowledgement is required, it sets the Result field to ReturnReceipt in the header of the Message 💜
The Result field is an 8-bit unsigned integer in network bit order. Currently defined values:
NoSuccessAck: Result = 1
AckAll: Result = 2
Success: Result = 3
Failure: Result = 4
ReturnReceipt Result = 5Code 🍓
This field gives extra info about the result in a response message. It's mostly used to carry an error code in a failure response, but it can also add detail to a success response or an event message. In a request message, the Code field isn't used and is set to zero 🌸
If the Code field says the Error TLV is included in the message, the details of the error live in the Error TLV, which MUST be the first TLV after the header. Iykyk 🫶
The Code field is an 8-bit unsigned integer in network bit order. Success and failure responses each get their own number space. In both, a range is reserved for use in specifications and another range is for private and experimental use. For success messages, these values are defined:
Generic Success 0x00
Submessage Received 0x01
Unassigned 0x02 - 0x7F
Private/Experimental Use 0x80 - 0xFFSubmessage Received is used to acknowledge reception of a message segment. Generic Success is used to acknowledge receipt of a complete message and successful processing of its contents ✨
For failure messages, these values are defined:
Reserved 0x00 - 0x01
Unspecified Failure 0x02
Unassigned 0x03 - 0x7F
Private/Experimental Use 0x80 - 0xFE
Error TLV in message 0xFFUnspecified Failure can be used to report a failure when there's no more specific code or Error TLV value defined for it 💀
Sender Instance 🌈
During the Hello phase, for the Hello SYN, Hello SYNACK, and Hello ACK functions (explained in Section 5.2), this is the sender's instance number for the link. It's how you detect when the link comes back up after going down, or when the entity at the other end of the link changes. The instance number is a 16-bit number that's guaranteed to be unique within the recent past, and that changes when the link or node comes back up after going down. Zero is not a valid instance number 🙅♀️
For the RSTACK function (also explained in detail in Section 5.2), the Sender Instance field is set to whatever the Receiver Instance field was in the incoming message that triggered the RSTACK. Messages sent after the Hello phase is complete should use the sender's instance number for the link. It's a 16-bit unsigned integer in network bit order 🦋
Receiver Instance 💜
During the Hello phase, for the Hello SYN, Hello SYNACK, and Hello ACK functions, this is what the sender believes the current instance number for the link is, as allocated by the entity at the far end. If the sender doesn't know the current instance number at the far end, this field MUST be set to zero. Non-negotiable 🔥
For the RSTACK message, the Receiver Instance field is set to whatever the Sender Instance field was in the incoming message that caused the RSTACK message to be generated. Messages sent after the Hello phase is complete should use what the sender believes is the current instance number for the link, as allocated by the far end. (The text describes this field as encoded as a 16-bit unsigned integer in network bit order, too 🙈)
Transaction Identifier 🧚
This is how a message gets matched up with its response. It should be set in request messages to a value that's unique for the sending host within the recent past. Reply messages carry the Transaction Identifier of the request they're answering. It's a 32-bit bit pattern 💖
S-flag 🌸
If S is set (value 1), the SubMessage Number field tells you the total number of SubMessage segments that make up the entire message. If S is not set (value 0), the SubMessage Number field is the sequence number of this SubMessage segment within the whole message. The S field is only set in the first submessage of a sequence 🎀
SubMessage Number 🍓
When a message gets segmented because it's bigger than the MTU of the link layer (or for other reasons), each segment includes a SubMessage Number to show its position. If it's the first submessage in a sequence, the S-flag is set and this field holds the total count of SubMessage segments instead. The SubMessage Number is a 15-bit unsigned integer in network bit order. It's zero-based, so a message split into n submessages is numbered from 0 to (n - 1). A message that isn't divided into submessages has the S-flag cleared (value 0), and its SubMessage Number is set to 0 (zero) ✨
Length 🌈
The length in octets of this message, headers and message body included. If the message is fragmented, this field holds the length of this SubMessage instead. The Length is encoded as an SDNV 💅
Message Body 👑
As specified in Section 4, the Message Body is a sequence of one or more of the TLVs specified in Section 4.2. Main character era 💖
The protocol also needs some extra info about the link, and the underlying communication layer MUST provide it. This info is used in the Hello procedure described in more detail in Section 5.2. Since the underlying layer already has it, there's no need to carry it in PRoPHET messages. These values are defined to be provided by the underlying layer 🫶
Sender Local Address 🦋
An address used by the underlying communication layer, as described in Section 2.4, that identifies the sender address of the current message. It must be unique among the nodes that can currently communicate, and it's only used together with the Receiver Local Address, Receiver Instance, and Sender Instance to identify a communicating pair of nodes ✨
Receiver Local Address 🌸
An address used by the underlying communication layer, as described in Section 2.4, that identifies the receiver address of the current message. It must be unique among the nodes that can currently communicate, and it's only used together with the Sender Local Address, Receiver Instance, and Sender Instance to identify a communicating pair of nodes 💜
When PRoPHET is run over TCP, the IP addresses of the communicating nodes are used as the Sender and Receiver Local Addresses. 🌈
4.2. TLV Structure 💖
okay so every TLV follows this exact same format, and they can be nested inside each other 🪆 iykyk
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| TLV Type | TLV Flags | TLV Length (SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ TLV Data ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 6: TLV FormatTLV Type 🎀 Specific TLVs are defined in Section 4.3. The TLV Type is an 8-bit unsigned integer, encoded in network bit order. Each TLV has fields that are specific to what that TLV does. so cute, right?
TLV Flags 🌸 These are defined per TLV type. Flag n lives at bit 15-n in the TLV. Any flags that are marked as reserved in a specific TLV SHOULD be transmitted as 0 and ignored on receipt.
TLV Length 🦋 This is the length of the TLV in octets, including the TLV header and any nested TLVs. It's encoded as an SDNV. TLVs are not padded to any particular alignment unless the TLV's own description says so, and no TLVs in this document specify any padding. no random padding, no drama 🧚
4.3. TLVs 🍓
okay this section is the menu of all the TLVs you can use in PRoPHET messages 🍽️
4.3.1. Hello TLV 👑
the Hello TLV is what sets up and keeps alive a link between two PRoPHET nodes ✨ Hello messages with the SYN function go out periodically as beacons or keep-alives. It's the very first TLV two PRoPHET nodes swap when they meet, and nothing else gets exchanged until that first Hello sequence is finished. rude to skip the hello, literally 💀
Once a link is up, the Hello TLV gets sent once per interval, as defined by the interval timer. If a node misses HELLO_DEAD Hello intervals without getting a Hello TLV on a connection that's in the INFO_EXCH state (see the state machine in Section 5.1), the connection SHOULD be assumed broken. 🚨
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| TLV Type=0x01 |L| Resv | HF | TLV Length (SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Timer (SDNV) |EID Length,SDNV| Sender EID (variable length) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 7: Hello TLV FormatTLV Flags 🌈 The TLV Flags field holds two 1-bit flags (S and L) and a 3-bit Hello Function (HF) number. The HF picks one of four functions for the Hello TLV. The other 3 bits (Resv) are unused and reserved:
HF 🧁 TLV Flags bits 0, 1, and 2 are read as an unsigned 3-bit integer in network bit order, and that value is the Hello Function. Four functions are defined for the Hello TLV, encoded like this:
SYN: HF = 1
SYNACK: HF = 2
ACK: HF = 3
RSTACK: HF = 4The remaining values (0, 5, 6 and 7) are unused and reserved. If a Hello TLV with any of these values shows up, the link should be reset. 🙈
Resv 🫧 TLV Flags bits 3, 4, 5, and 6 are reserved. They SHOULD be set to 0 on transmission and ignored on reception. these bits are just vibes, no meaning yet 🌙
L 🔥 The L bit (TLV Flags bit 7) is set to 1 to ask that the Bundle Offer TLV sent during the Information Exchange Phase carry bundle payload lengths for all bundles. When L is cleared (value 0), that Bundle Offer TLV only carries lengths for bundle fragments. This only applies when the flag is carried in a Hello TLV with Hello Function SYN or SYNACK. For any other Hello Function values, the flag is ignored. 💅
TLV Data 💜
Timer ⏱️ The Timer field tells the receiver what timer value the sender uses for Hello processing. It's the nominal time between periodic Hello messages, and it stays the same for the whole session. The Timer is in units of 100 ms and is encoded as an SDNV. 🎶
EID Length 🪪 The EID Length field gives the length of the Sender EID field, in octets. If the Endpoint Identifier (EID) has already been sent at least once in a message with the current Sender Instance, a node MAY choose to set this field to zero, which leaves the Sender EID out of the Hello TLV. The EID Length is an SDNV, so the field is variable length too. flexible, bestie 🍑
Sender EID 🦋 The Sender EID is the DTN endpoint identifier (EID) of the sender. Routing info gets updated with it and forwarding decisions are made using it. If a node has several EIDs, one should be picked for PRoPHET routing. This field is variable length. ✨
4.3.2. Error TLV 🚨
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| TLV type=0x02 | TLV Flags | TLV Length (SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ TLV Data ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 8: Error TLV FormatTLV Flags 🫶 For Error TLVs, the TLV Flags field holds an identifier for the Error TLV type, as an 8-bit unsigned integer in network bit order. There's a range set aside for private and experimental use on top of the values defined here. These Error TLV types are defined:
Dictionary Conflict 0x00
Bad String ID 0x01
Reserved 0x02 - 0x7F
Private/Experimental Use 0x80 - 0xFFTLV Data 🍭 What the TLV Data field contains depends on the type of Error TLV. For the Error TLVs defined in this document, the TLV Data works like this:
Dictionary Conflict 💥 The TLV Data is the String ID causing the conflict, encoded as an SDNV, followed by the EID string that clashes with the value installed before. The Endpoint Identifier is NOT null terminated. To figure out the EID's length, subtract the TLV Header length and the length of the SDNV holding the String ID from the TLV Length. no null terminator, so do the math, bestie 🧮
Bad String ID 🙅♀️ The TLV Data is the String ID that isn't found in the dictionary, encoded as an SDNV.
4.3.3. Routing Information Base Dictionary TLV ✨
okay bestie, the Routing Information Base Dictionary is basically the guest list 💅 It holds the list of endpoint identifiers that get used when making routing decisions 🦋 The referents stay constant for the whole session over a link, as long as the instance numbers stay the same, and both the Routing Information Base messages and the bundle offer/response messages can use them 🫶 It's a shared resource (see Section 3.2.1) that each of the paired peers builds from one or more incoming TLVs of this type, plus whatever info they used to make their outgoing ones 🔥
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| TLV type=0xA0 | TLV Flags | TLV Length (SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RIBD Entry Count (SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ~
~ Variable-Length Routing Address Strings ~
~ ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ Routing Address String 1 ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| String ID 1 (SDNV) | Length (SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ Endpoint Identifier 1 (variable length) ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| . |
~ Routing Address String n . ~
| . |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| String ID n (SDNV) | Length (SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ Endpoint Identifier n (variable length) ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 9: Routing Information Base Dictionary TLV FormatTLV Flags 🌸
The encoding of the Header flag field relates to the capabilities of the source node sending the RIB Dictionary:
Flag 0: Sent by Listener 0b1
Flag 1: Reserved 0b1
Flag 2: Reserved 0b1
Flag 3: Unassigned 0b1
Flag 4: Unassigned 0b1
Flag 5: Unassigned 0b1
Flag 6: Unassigned 0b1
Flag 7: Unassigned 0b1The "Sent by Listener" flag is set to 0 if this TLV was sent by a node in the Initiator role, and set to 1 if this TLV was sent by a node in the Listener role (see Section 3.2 for explanations of these roles) 💜
TLV Data 🎀
- RIBD Entry Count: the number of entries in the database, encoded as SDNV 🍓
- String ID: an SDNV identifier that stays constant for the duration of a session ✨ String ID zero is predefined as the node that initiates the session by sending the Hello SYN message, and String ID one is predefined as the node that responds with the Hello SYNACK message 🧚 These entries don't need to be sent explicitly, since the EIDs are exchanged during the Hello procedure 🙈
- Length: the length of the Endpoint Identifier in this entry, encoded as SDNV 🦋
- Endpoint Identifier: a text string representing the Endpoint Identifier. Note that it is NOT null terminated, because the entry already contains the length of the identifier 💀
String ID drama alert 🚨 To make sure the String IDs from the two peers don't clash, the String IDs generated by the node that sent the Hello SYN message MUST have their least significant bit set to 0 (so they're even numbers), and the String IDs generated by the node that responded with the Hello SYNACK message MUST have their least significant bit set to 1 (so they're odd numbers). Even and odd, no fighting, periodt 👑
4.3.4. Routing Information Base TLV 🌈
The Routing Information Base lists the destinations (endpoints) a node knows about, plus the delivery predictabilities it has associated with them 🧚 PRoPHET needs this info to make its routing and forwarding decisions, so it's literally the main character of this whole TLV 👑
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| TLV Type=0xA1 | TLV Flags | TLV Length (SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RIB String Count (SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RIBD String ID 1 (SDNV) | P-value |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RIB Flags 1 | . ~
+-+-+-+-+-+-+-+-+ . ~
~ . ~
~ . ~
~ . ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RIBD String ID n (SDNV) | P-value |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RIB Flags n |
+-+-+-+-+-+-+-+-+
Figure 10: Routing Information Base TLV FormatTLV Flags 🦋
The encoding of the Header flag field relates to the capabilities of the Source node sending the RIB:
Flag 0: More RIB TLVs 0b1
Flag 1: Reserved 0b1
Flag 2: Reserved 0b1
Flag 3: Unassigned 0b1
Flag 4: Unassigned 0b1
Flag 5: Unassigned 0b1
Flag 6: Unassigned 0b1
Flag 7: Unassigned 0b1The "More RIB TLVs" flag is set to 1 if the RIB needs more TLVs sent before it's fully transferred 📦 It's set to 0 if this is the final TLV of this RIB, so the receiver knows the party's over 🥳
TLV Data 🍓
- RIB String Count: the number of routing entries in the TLV, encoded as an SDNV 🌸
- RIBD String ID: the String ID of the endpoint identifier for the destination this entry describes the delivery predictability for, as predefined in a dictionary TLV. Encoded as an SDNV 🧚
- P-value: the delivery predictability for this entry's destination, calculated from previous encounters according to the equations in Section 2.1.2 and encoded as a 16-bit unsigned integer. The encoding is a linear mapping from [0,1] to [0, 0xFFFF]. For example, for a P-value of 0.75, the mapping would be 0.75*65535=49151=0xBFFF, so the P-value would be encoded as 0xBFFF ✨
- RIB Flag: the encoding of the 8-bit RIB Flag field is:
Flag 0: Unassigned 0b1
Flag 1: Unassigned 0b1
Flag 2: Unassigned 0b1
Flag 3: Unassigned 0b1
Flag 4: Unassigned 0b1
Flag 5: Unassigned 0b1
Flag 6: Unassigned 0b1
Flag 7: Unassigned 0b14.3.5. Bundle Offer and Response TLVs (Version 2) 🎀
okay so once the routing info has been passed around, the node asks the other node to look at the bundles it has and decide which ones it wants to accept for relay 📦✨ the source relay picks which bundles to offer based on relative delivery predictabilities, as explained in Section 3.6 💅
🫶 Note: the original versions of these TLVs (TLV Types0xA2and0xA3) from version 1 of the PRoPHET protocol are deprecated now 😭 they didn't have enough info to uniquely identify bundles, and they couldn't handle bundle fragments, so they had to go 💀
depending on what's stored in the offering node, the Bundle Offer TLV might describe complete bundles AND bundle fragments 🧩 to identify fragments properly, a bundle fragment descriptor MUST contain the offset of the payload fragment in the bundle payload, plus the length of that payload fragment 🔥 if the receiving node asked for it by setting the L flag in the SYN or SYNACK message during the neighbor awareness phase, the offering node MUST include the payload length in the descriptor for complete bundles too 🌸 the right flags MUST be set in the B_flags for the descriptor so everyone knows whether the payload length field is there (it's always there for fragments, and for complete bundles only if the L flag was set) and whether there's a payload offset field (fragments only) 🍓
the Bundle Offer TLV also lists the bundles that got a PRoPHET acknowledgement 🙌 those bundles have the PRoPHET ACK flag set in their entry. when a node gets a PRoPHET ACK for a bundle, it SHOULD, if possible, tell the bundle protocol agent that this bundle doesn't need to be sent by PRoPHET anymore 🦋 even though it stops transmitting the bundle, it SHOULD keep an entry for the acknowledged bundle so it can keep passing the PRoPHET ACK along ✨
the Response TLV is basically the same as the Offer TLV, except for the TLV Type field 💖 bundles that are being accepted from the matching Offer get explicitly marked with a B_flag. for bundles that aren't being accepted, you MAY either leave them out or keep them in without marking them as accepted 🧚 the payload length field MAY be omitted for complete bundles in the Response message, even if it was in the Offer message 🫠 but the B_flags payload length flag MUST be set correctly so people can tell whether the length field is included or not 🎯 the Response message MUST include both the payload offset and payload length fields for bundle fragments, and the B_flags MUST be set to show that both are there 👑
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| TLV Type | TLV Flags | TLV Length (SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Bundle Offer Count (SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| B_flags | Bundle Source | Bundle Destination |
| | String ID 1 (SDNV) | String ID 1 (SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Bundle 1 Creation Timestamp Time |
| (SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Bundle 1 Creation Timestamp Sequence Number |
| (SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Bundle 1 Payload Offset - only present if bundle is a fragment|
| (SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Bundle 1 Payload Length - only present if bundle is a fragment|
| or transmission of length requested (SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ . ~
~ . ~
~ . ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| B_flags | Bundle Source | Bundle Destination |
| | String ID n (SDNV) | String ID n (SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Bundle n Creation Timestamp Time |
| (SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Bundle n Creation Timestamp Sequence Number |
| (SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Bundle n Payload Offset - only present if bundle is a fragment|
| (SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Bundle n Payload Length - only present if bundle is a fragment|
| or transmission of length requested (SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 11: Bundle Offer and Response TLV FormatTLV Type 🏷️ the TLV Type for a Bundle Offer is 0xA4, and for a Bundle Response it's 0xA5 💜
TLV Flags 🌈 the Header flag field encoding depends on what the source node sending the RIB can do ✨
Flag 0: More Offer/Response
TLVs Following 0b1
Flag 1: Unassigned 0b1
Flag 2: Unassigned 0b1
Flag 3: Unassigned 0b1
Flag 4: Unassigned 0b1
Flag 5: Unassigned 0b1
Flag 6: Unassigned 0b1
Flag 7: Unassigned 0b1if the Bundle Offers or Bundle Responses get split across several TLVs, the "More Offer/Response TLVs Following" flag MUST be set to 1 in every TLV except the last one in the sequence, and in that last one it MUST be set to 0 🫶
TLV Data 📚
Bundle Offer Count 🔢 this is the number of bundle offer/response entries, encoded as an SDNV. 0 is totally allowed! 😌 in fact, a Bundle Response TLV with 0 entries is how you signal that a cycle of info exchange and bundle passing is done 🎉
B Flags 🚩 here's how the B Flags are encoded:
Flag 0: Bundle Accepted 0b1
Flag 1: Bundle is a Fragment 0b1
Flag 2: Bundle Payload Length
included in TLV 0b1
Flag 3: Unassigned 0b1
Flag 4: Unassigned 0b1
Flag 5: Unassigned 0b1
Flag 6: Unassigned 0b1
Flag 7: PRoPHET ACK 0b1Bundle Source String ID 🌷 the String ID of the bundle's source EID, as predefined in a dictionary TLV. encoded as an SDNV ✨
Bundle Destination String ID 🎯 same deal, but for the destination EID. also an SDNV, predefined in a dictionary TLV 💅
Bundle Creation Timestamp Time ⏰ the Time component of the Bundle Creation Timestamp, encoded as an SDNV 🦋
Bundle Creation Timestamp Sequence Number 🔁 the Sequence Number component of the Bundle Creation Timestamp, also an SDNV 🧁
Bundle Payload Offset 📍 only included if the bundle is a fragment AND the fragment bit is set (value 1) in the bundle B Flags. it's the offset of the start of the fragment payload within the complete bundle payload, encoded as an SDNV 🧩
Bundle Payload Length 📏 only included if the bundle length included bit is set (value 1) in the bundle B Flags. it's the length of the payload in the bundle specified. this is either the total payload length for a complete bundle, or the fragment payload length if it's a fragment. encoded as an SDNV 🍓
5. Detailed Operation ✨
in this section we get into more detail about how PRoPHET operates, with state tables to help you implement it 🧠💖
as explained in Section 1.2, it is RECOMMENDED that "Success" responses should not be requested or sent when you're running over a reliable, in-order transport protocol like TCP 🫶 if PRoPHET ever runs over an unreliable transport in the future, positive acknowledgements would be necessary to signal successful delivery of (sub)messages 😭 in this section, "send a message" should be read as successful sending of a message. that's signaled by receiving the matching "Success" response if you're on an unreliable protocol, but it's guaranteed by TCP or another reliable protocol otherwise 🔒 so the state descriptions below don't explicitly mention positive acknowledgements, whether they're being sent or not 🌈
5.1. High-Level State Tables ✨
okay so this section is the big-picture map 🗺️ of how PRoPHET moves through its states. the sections after it zoom in on each part of the operation, including the internal state tables for those procedures 💅
these are the main (high-level) states used in the tables:
WAIT_NB: every node starts out here 🧘 and stays until it's told a new neighbor is available. at that point the Hello procedure should be started with the new neighbor, and the node moves into HELLO. Nodes SHOULD be able to handle multiple neighbors in parallel, keeping a separate state machine for each neighbor 👯. one way to do this is to spin up a new thread or process when moving to HELLO. that thread handles the chat with the new neighbor while the parent stays in WAIT_NB, waiting for more friends. when the neighbor can't be communicated with anymore (that's the "Neighbor Gone" in the tables below), the thread or process gets destroyed. if a connection-oriented protocol is being used to talk to the neighbor, the connection gets closed too 🚪. the current version of the protocol is specified to use TCP for neighbor connections, so those connections get closed once the neighbor isn't accessible anymore 💜
HELLO: nodes are in HELLO from the moment a new neighbor is detected until the Hello procedure is finished and a link is established 🔗. that happens when the Hello procedure enters the ESTAB state (see Section 5.2). during this procedure the states ESTAB, SYNSENT, and SYNRCVD get used, but they're internal to the Hello procedure, so they aren't listed here 🤫. if the node is told the neighbor is out of range before a link has been established, it goes back to WAIT_NB. and if it makes sense, any extra process or thread created to handle that neighbor MAY be destroyed 🗑️
INFO_EXCH: once the Hello procedure has set up a link, the node moves into INFO_EXCH, where the Information Exchange Phase happens 📬. the node stays here as long as Information Exchange Phase TLVs (Routing RIB, Routing RIB Dictionary, Bundle Offer, Bundle Response) keep arriving. if the neighbor goes out of range before all the info and bundles have been swapped, any connection gets closed and the node goes back to WAIT_NB to wait for new neighbors. the Timer(keep_alive) is what keeps the connection alive 💖
inside INFO_EXCH, the nodes at both ends of the link can update their delivery predictability info using data from the peer. then they make bundle offers, which the peer can accept or not 🎁. to manage all this, each node acts as both an Initiator and a Listener for the Information Exchange Phase, with subsidiary state machines for the two roles. the Initiator and Listener names refer to sending the Routing RIB information. it's kind of counterintuitive that the Listener ends up being the bundle offeror and the Initiator ends up being the bundle acceptor during the bundle passing part 🙃
the protocol is designed so the two exchanges MAY be carried out independently but concurrently, with the messages multiplexed onto a single bidirectional link (like the one a TCP connection provides) 🧵. or, if that suits the implementation better, the exchanges MAY be carried out partially or wholly sequentially 🪜
when an empty Bundle Response TLV shows up (meaning there are no more bundles to send), the node starts the Timer(next_exchange) ⏰. when that timer expires, and the neighbor is still connected, the Initiator reruns the Information Exchange Phase. if only one neighbor is connected at that point, this further increases the delivery predictability for this node in that neighbor, and it also changes the delivery predictabilities through the transitive property (Equation 3) 🧠. if there's more than one neighbor connected, or other communication opportunities have happened since the last exchange, then the changes from those other encounters get passed along to the connected neighbor 🌸. the next_exchange timer restarts once the information exchange has finished again.
and if one or more new bundles arrive while the node is waiting for Timer(next_exchange) to expire, and the delivery predictabilities say it would be appropriate to forward some or all of them to the connected node, the bundles SHOULD be immediately offered to that neighbor and transferred if accepted 🚀
State: WAIT_NB
+==================================================================+
| Condition | Action | New State |
+==================+===================================+===========+
| New Neighbor | Start Hello procedure for neighbor| HELLO |
| | Keep waiting for more neighbors | WAIT_NB |
+==================================================================+State: HELLO
+==================================================================+
| Condition | Action | New State |
+==================+===================================+===========+
| Hello TLV rcvd | | HELLO |
+------------------+-----------------------------------+-----------+
| Enter ESTAB state| Start Information Exchange Phase | INFO_EXCH |
+------------------+-----------------------------------+-----------+
| Neighbor Gone | | WAIT_NB |
+==================================================================+State: INFO_EXCH
+==================================================================+
| Condition | Action | New State |
+==================+===================================+===========+
| On entry | Start Timer(keep-alive) | |
| | Uses Hello Timer interval | INFO_EXCH |
+------------------+-----------------------------------+-----------+
|Info Exch TLV rcvd| (processed by subsidiary state | |
| | machines) | INFO_EXCH |
+------------------+-----------------------------------+-----------+
| No more bundles | Start Timer(next_exchange) | INFO_EXCH |
+------------------+-----------------------------------+-----------+
| Keep-alive expiry| Send Hello SYN message | INFO_EXCH |
+------------------+-----------------------------------+-----------+
| Hello SYN rcvd | Record reception | |
| | Restart Timer(keep-alive) | INFO_EXCH |
+------------------+-----------------------------------+-----------+
| Neighbor Gone | | WAIT_NB |
+==================================================================+last bit of this section: the keep-alive messages (the ones carrying a Hello SYN TLV) get handled by the high-level state machine while in INFO_EXCH 💜. every other message gets handed off to the subsidiary state machines of the Information Exchange Phase (see Section 5.3). the receipt of keep-alives gets recorded, and the subsidiary machines can use that to check whether the peer is still functioning 👀. if several keep-alive messages go missing, the connection gets aborted, as described in Section 4.3.1. yikes, so keep an eye on those keep-alives 🫶
5.2. Hello Procedure ✨
okay bestie, the Hello procedure is where the two ends get to know each other 🫶 It's described by the rules and state tables below. In this section, the messages you send are the PRoPHET header plus a single Hello TLV (see Figure 4 and Section 4.3.1) with the HF (Hello Function) field set to the value you want (SYN, SYNACK, ACK or RSTACK). 🎀
The L flag from the latest SYN or SYNACK message gets recorded by the node that receives it 📝 If the L flag is set (value 1), the receiving node MUST send the payload length for each bundle it offers to the peer during the Information Exchange Phase. no skipping this, it's giving very strict 💅
These are the operations the rules and state tables use:
- The "Update Peer Verifier" operation is just storing the Sender Instance and Sender Local Address fields from a Hello SYN or Hello SYNACK function message you got from the entity at the far end of the link. 🌸
- The procedure "Reset the link" is defined as follows.
When using TCP or other reliable connection-oriented transport: Close the connection and terminate any separate thread or process managing the connection.
Otherwise:
- Generate a new instance number for the link.
- Delete the peer verifier (set to zero the values of Sender Instance and Sender Local Address previously stored by the Update Peer Verifier operation).
- Send a SYN message.
- Transition to the SYNSENT state.
- The state tables use these Boolean terms and operators:
A: the Sender Instance in the incoming message matches the value stored from a previous message by the "Update Peer Verifier" operation. 🧚B: the Sender Instance and Sender Local Address fields in the incoming message match the values stored from a previous message by the "Update Peer Verifier" operation. 💜C: the Receiver Instance and Receiver Local Address fields in the incoming message match the values of the Sender Instance and Sender Local Address used in your outgoing Hello SYN, Hello SYNACK, and Hello ACK messages. 🦋SYN: a Hello SYN message has been received.SYNACK: a Hello SYNACK message has been received.ACK: a Hello ACK message has been received.&&: the logical AND operation.||: the logical OR operation.!: the logical negation (NOT) operation.
A timer is required for the periodic generation of Hello SYN, Hello SYNACK, and Hello ACK messages 💖 The value of the timer is announced in the Timer field. To avoid synchronization effects, uniformly distributed random jitter of +/-5% of the Timer field SHOULD be added to the actual interval used for the timer. ✨
There are two independent events: the timer expires, and a packet arrives. Here's how each one gets processed 👑
Timer Expires: Reset Timer
If state = SYNSENT Send SYN message
If state = SYNRCVD Send SYNACK message
If state = ESTAB Send ACK message
Packet Arrives:
If incoming message is an RSTACK message:
If (A && C && !SYNSENT) Reset the link
Else discard the message.
If incoming message is a SYN, SYNACK, or ACK message:
Response defined by the following State Tables.
If incoming message is any other PRoPHET TLV and
state != ESTAB:
Discard incoming message.
If state = SYNSENT Send SYN message(Note 1)
If state = SYNRCVD Send SYNACK message(Note 1)Note 1: No more than two SYN or SYNACK messages should be sent within any time period of length defined by the timer. 🙈
A connection across a link is considered achieved once the protocol reaches the ESTAB state 🥹 All TLVs, other than Hello TLVs, that are received before synchronization is achieved will be discarded. so don't send your fancy data early, bestie 💅
5.2.1. Hello Procedure State Tables
State: SYNSENT 🌈
+==================================================================+
| Condition | Action | New State |
+==================+===================================+===========+
| SYNACK && C | Update Peer Verifier; | ESTAB |
| | Send ACK message | |
+------------------+-----------------------------------+-----------+
| SYNACK && !C | Send RSTACK message | SYNSENT |
+------------------+-----------------------------------+-----------+
| SYN | Update Peer Verifier; | SYNRCVD |
| | Send SYNACK message | |
+------------------+-----------------------------------+-----------+
| ACK | Send RSTACK message | SYNSENT |
+==================================================================+State: SYNRCVD 🦋
+==================================================================+
| Condition | Action | New State |
+==================+===================================+===========+
| SYNACK && C | Update Peer Verifier; | ESTAB |
| | Send ACK message | |
+------------------+-----------------------------------+-----------+
| SYNACK && !C | Send RSTACK message | SYNRCVD |
+------------------+-----------------------------------+-----------+
| SYN | Update Peer Verifier; | SYNRCVD |
| | Send SYNACK message | |
+------------------+-----------------------------------+-----------+
| ACK && B && C | Send ACK message | ESTAB |
+------------------+-----------------------------------+-----------+
| ACK && !(B && C) | Send RSTACK message | SYNRCVD |
+==================================================================+State: ESTAB 💜
+==================================================================+
| Condition | Action | New State |
+=================+====================================+===========+
| SYN || SYNACK | Send ACK message (notes 2 and 3) | ESTAB |
+-----------------+------------------------------------+-----------+
| ACK && B && C | Send ACK message (note 3) | ESTAB |
+-----------------+------------------------------------+-----------+
| ACK && !(B && C)| Send RSTACK message | ESTAB |
+==================================================================+Note 2: No more than two ACK messages should be sent within any time period of length defined by the timer. Thus, one ACK message MUST be sent every time the timer expires. In addition, one further ACK message may be sent between timer expirations if the incoming message is a SYN or SYNACK. This additional ACK allows the Hello functions to reach synchronization more quickly. ⏰✨
Note 3: No more than one ACK message should be sent within any time period of length defined by the timer. 🫶
5.3. Information Exchange Phase ✨
Okay bestie, the Hello messages are done and both nodes are chilling in the ESTAB state 💅 Now the Information Exchange Phase kicks off 🦋. It's made of two sub-phases, the RIB Exchange and Bundle Passing Sub-Phases. This section walks through the procedure and the state transitions for those, and the next sections go deep on each TLV that gets passed around. Once you hit ESTAB in the high-level HELLO state, there's an automatic transition to the INFO_EXCH high-level state. No waiting, it just happens 🔥
PRoPHET runs over a bidirectional transport (see Section 1.2), so when nodes A and B reach ESTAB, they can do the Information Exchange Phase for both the A-to-B and B-to-A directions over the link that was just set up. In principle those two processes don't depend on each other, so they can run concurrently. But full concurrency isn't always the most efficient move 🤔 As Section 3.2.1 explains, the Routing Information Base Dictionary is a shared resource, built from info generated locally on each node plus info passed from the peer. The overlap in that info (and so how much has to be sent between the nodes) can be minimized by running the dictionary generation and update processes sequentially instead of concurrently. It might also be possible to cut down the number of bundles the second offeror has to offer, by checking the offers from the first offeror. There's no reason for the second offeror to offer a bundle that's already on the first offeror's offer list, because it's going to get refused anyway 🙃
Real talk: every implementation MUST be able to run in a fully concurrent manner 💖 Each one also needs a policy, which SHOULD be configurable, that decides whether it runs concurrently or sequentially during the Information Exchange Phase. If it goes sequential, there are more choices to make: interleave the dictionary, offer, and response parts, or finish all parts in one direction before starting the other direction 🎀
Sequential operation generally minimizes the amount of data sent across the PRoPHET link, and it's especially good if the link is half-duplex 🌸 But it's probably not desirable to hold off starting the second direction until the bundle exchange is totally finished. If the contact ends before every possible bundle has been swapped, delaying the second direction's bundle exchange can skew bundle exchange toward one direction over the other 😭 So it may be preferable to share the available contact time and bandwidth between directions, by overlapping the Information Exchange Phases and running the actual bundle exchanges concurrently when that's possible. Also, if encounters expected in the current PRoPHET zone are relatively short, it MAY not be appropriate to use sequential operation 💀
One possible interleaving strategy is to alternate between sending from the two nodes 🧚 For example, if the Hello SYN node sends its initial dictionary entries while the Hello SYNACK node waits until that's complete, the Hello SYNACK node can then prune its proposed dictionary entries before sending, so nothing gets duplicated. This can be repeated for the second tranche of dictionary entries needed for the Bundle Offers and Responses, and also for the Bundle Offers themselves. Any bundles the Hello SYN node offers that are already in the Hello SYNACK node don't need to be offered to the Hello SYN node. This approach is super well suited to a transport protocol and physical medium that's effectively half-duplex 🫶
Right now, the decision to operate concurrently or sequentially is purely a matter of local policy in each node. If nodes have inconsistent policies, the behavior at each encounter depends on which node takes the SYN role, and that's a matter of chance based on the random timing of when communications start during the encounter 🎲
To manage the information transfer, two subsidiary state machines get created in each node to control the stages of the RIB Exchange Sub-Phase and Bundle Passing Sub-Phase processes within the INFO_EXCH high-level state, as shown in Figure 12 ✨ Each subsidiary state machine has two essentially independent components, called the "Initiator role" and the "Listener role". One of these components is instantiated in each node. The Initiator role starts the Information Exchange Phase in each node, and the Listener role responds to the initial messages. But it's not a passive listener, because it also originates messages 👀 The transition from the ESTAB state is a "forking" transition, since it starts both subsidiary state machines. The two run in parallel for as long as the neighbor stays in range and connected 🌈
+ - - - - - - - - + + - - - - - - - - +
| SYN node | PRoPHET messages with: | SYNACK node |
| +-------------+ | A. Delivery Predictabilities | +-------------+ |
| Subsidiary |--->---->---->---->---->---->---->| Subsidiary |
| | State | | C. Bundle Responses | | State | |
| Machine 1: | | Machine 1: |
| | Initiator | | B. Bundle Offers | | Listener | |
| Role |<----<----<----<----<----<----<---| Role |
| +-------------+ | D. Requested Bundles | +-------------+ |
| +-------------+ | A. Delivery Predictabilities | +-------------+ |
| Subsidiary |<----<----<----<----<----<----<---| Subsidiary |
| | State | | C. Bundle Responses | | State | |
| Machine 2: | | Machine 2: |
| | Listener | | B. Bundle Offers | | Initiator | |
| Role |--->---->---->---->---->---->---->| Role |
| +-------------+ | D. Requested Bundles | +-------------+ |
+ - - - - - - - - + + - - - - - - - - + The letters (A - D) indicate the sequencing of messages.
Figure 12: Information Exchange Phase Subsidiary State MachinesThese subsidiary state machines are basically mirror images 🪞 For each state machine, one node takes on the Initiator role while the other takes on the Listener role. TLVs sent by a node from the Initiator role get processed by the peer node in the Listener role, and vice versa. As Figure 12 shows, the Initiator role handles sending that node's current set of delivery predictabilities for known destinations to the Listener role node. The Listener role node uses those values to update its delivery predictabilities, following the update algorithms described in Section 2.1.2. Then it decides which bundles it has in store should be offered for transfer to the Initiator role node, by comparing its local predictabilities with the ones supplied by the Initiator node. When those offers get delivered to the Initiator role node, it decides which ones to accept and gives the Listener role node a prioritized list of the bundles it wants. Then the Listener role node sends the requested bundles 📦
These exchanges repeat periodically for as long as the nodes stay in contact. And if new bundles arrive from other sources, they may be offered, accepted, and sent in between these exchanges 💌
PRoPHET is designed so that, in most cases, the TLV type determines the role it gets processed in on reception 🔍 The only exception is that both roles may send RIB Dictionary TLVs. The Initiator role sends dictionary entries for use in the subsequent RIB TLV(s), and the Listener role may send additional dictionary entries for use in subsequent Bundle Offer TLVs. The two cases are told apart by a TLV flag, so they get processed in the right role context on reception. If that flag weren't provided, there are states where both roles could accept the RIB Dictionary TLV, which makes it impossible to make sure the correct role state machine accepts it 😵 The correct updates would still be made to the dictionary whichever role processed the TLV, though. And the ambiguity wouldn't arise if the roles are adopted completely sequentially, i.e., if the RIB Exchange Sub-Phase and its associated Bundle Passing Sub-Phase run to completion in one direction before the process for the reverse direction starts.
If sequential operation is selected, the node that sent the Hello SYN function message MUST be the node that sends the first message in the Information Exchange Phase process 🥇 This ensures a well-defined order of events, with the Initiator role in the Hello SYN node (the node identified by String ID 0) starting first. The Hello SYNACK node MAY then postpone sending its first message until the Listener role state machine in the Hello SYNACK node has reached any of a number of points in its state progression, according to locally configured policy and the nature of the physical link for the current encounter, as described above. If concurrent operation is selected, the Hello SYNACK node can start sending messages immediately without waiting to receive messages from the peer 🏃
The original PRoPHET design let it operate over unreliable datagram-type transports, as well as over the reliable, in-order delivery transport of TCP that's currently specified 🧦 When running over TCP, protocol errors and repeated timeouts during the Information Exchange Phase SHOULD result in the connection being terminated 🚪 Bye bye, no drama 💅
5.3.1. State Definitions for the Initiator Role 🎀
The state machine component with the Initiator role in each node starts the transfer of information from one node to its peer during the Information Exchange Phase. From the Initiator's point of view, the process goes like this:
- The Initiator role determines the set of delivery predictabilities to be sent to the peer node, and sends the RIB dictionary entries needed to interpret the set of RIB predictability values that get sent after the dictionary updates. On second and subsequent executions of this state machine during a single session with the same peer, there may be no RIB Dictionary entries to send. Either an empty TLV can be sent, or the TLV can be omitted ✨
- The Initiator then waits to receive any RIB Dictionary updates, followed by bundle offers, from the Listener role on the peer node 🫧
- The Initiator determines which of the bundle offers should be accepted and, if necessary, reorders the offers to suit its own priorities. The possibly reordered list of accepted bundles is sent to the peer node using one or more bundle responses 📝
- The peer then sends the accepted bundles to the Initiator in turn 📦
- Assuming the link remains open during the bundle sending process, the Initiator signals that the Bundle Passing Sub-Phase is complete by sending a message with an empty Bundle Response TLV (i.e, with the Bundle Offer Count set to 0 and no bundle offers following the TLV header) 🎉
When the bundle transfer is done, the Initiator starts the Timer(next_exchange) 💖 If the connection to the neighbor is still open when that timer goes off, the Initiator restarts the Information Exchange Phase. In the meantime, Hello SYN messages get passed back and forth as keep-alives, so everyone can check that the neighbor is still around 🫶 The keep-alive mechanism is shared by the Initiator and Listener machines and is handled in the high-level state machine (see Section 5.1.
Okay, there's also a timer that restarts the Initiator role state machine if Bundle Offers don't show up after the RIB gets sent 🦋 And if this node gets a Hello ACK with an Error TLV saying there's been a protocol problem, the connection MUST be terminated 💀
The states we use are:
CREATE_DR 🌸 The first move into this state from the ESTAB state is immediate and automatic for the node that sent the Hello SYN message. For the peer (the Hello SYNACK sender), it might be immediate if the node runs a fully concurrent process, or it might be postponed until the matching Listener reaches a certain state, if the node policy says to run a sequential process 🧚
The local dictionary gets initialized the first time this state is entered from the ESTAB state. The starting dictionary has two entries: the EID of the node that sent the Hello SYN (String ID 0) and the EID of the node that sent the Hello SYNACK (String ID 1). If the peer reports a Dictionary Conflict or Bad String ID error in a Hello ACK message containing an Error TLV, the connection MUST be terminated 😭
The CREATE_DR state gets entered the same way from the REQUEST state when the Timer(next_exchange) expires, which is the signal to start a fresh round of information exchange and bundle passing 🔥
When you're in this state:
- Figure out which destination EIDs get delivery predictabilities sent to the peer in a RIB TLV, if any. Save the prior state of the local dictionary (if String IDs are numbers handed out in sequence, all you need to remember is the highest ID used before this process started) so the process can be restarted if it has to be ✨ Update the local dictionary if any new EIDS are needed, then format one or more RIB Dictionary TLVs and one or more RIB TLVs and send them to the peer. If there are no dictionary entries to send, TLVs with zero entries MAY be sent, or the TLV can be left out. But an empty RIB TLV MUST be sent if there's no data to send 🍓 The RIB Dictionary TLVs made here MUST have the Sent by Listener flag set to 0 to show that the Initiator sent them 👑
- If an Error TLV reporting a Dictionary Conflict or Bad String ID shows up during or after sending the RIB Dictionary TLVs and/or the RIB TLVs, cancel any in-progress Initiator or Listener process and terminate the connection to the peer 🙈
- Start a timer (called Timer(info)) and move to the SEND_DR state 💅
Note that (and only when) running over a transport protocol such as TCP, both the RIB Dictionary and RIB information MAY be spread across multiple TLVs and messages if the transport protocol's known constraints call for it, or to keep memory buffers small 🌈 Otherwise, you can format the info using a single RIB Dictionary TLV and a single RIB TLV. These TLVs can get pretty big, so you might need to segment the message, either with the PRoPHET submessage capability or, if the transport protocol has suitable capabilities, with those built-in ones 🫶 This segmentation talk applies to the other states and to the bundle offer and bundle response messages too, and we won't repeat it.
If you're using more than one RIB TLV, every one except the last gets the "More RIB TLVs" flag set to 1 in the TLV flags. The last RIB Dictionary TLV doesn't need to be told apart, because the receiver just records what it gets, and the sequence ends when the first RIB TLV gets sent 🦋
SEND_DR 🎀 In this state, the Initiator node expects to receive Bundle Offers and send Bundle Responses. The Initiator builds a list of the bundles the peer offered while it's in this state:
- Clear the set of bundles offered by the peer when you enter the state 🧹
- If the Timer(info) expires, re-send the RIB Dictionary and RIB information that got sent in the previous CREATE_DR state, using the stored state to rebuild it. The RIB dictionary update in the peer is idempotent as long as the mappings between EID and String ID in the re-sent RIB Dictionary TLVs match the originals. So it doesn't matter if some RIB Dictionary TLVs were already processed in the peer. Re-sending RIB TLVs won't cause a problem either 💜
- If a message with a RIB Dictionary TLV marked as sent by a Listener comes in, update the local dictionary based on that TLV. If any entry in the RIB Dictionary TLV conflicts with an existing one (meaning an entry uses the same String ID as a previously received entry, but its EID is different), send a Response message with an Error TLV carrying a Dictionary Conflict indicator, cancel any in-progress Initiator or Listener process, and terminate the connection to the peer 😤 Note that in some cases no dictionary updates are needed, and the first message received in this state will carry a Bundle Offer TLV ✨
- If a message with a Bundle Offer TLV is received, restart the Timer(info) if the "More Offer/Response TLVs Following" flag is set in the TLV. Otherwise, stop the Timer(info). Then process any PRoPHET ACKs in the TLV by telling the bundle protocol agent, and add the bundles offered in the TLV to the set of bundles offered. If the "More Offer/Response TLVs Following" flag is set in the TLV, wait for more Bundle Offer TLVs. If a Bundle Offer TLV arrives with a String ID that isn't in the dictionary, send a message with an Error TLV containing a Bad String ID indicator, cancel any in-progress Initiator or Listener process, and terminate the connection to the peer 🙅♀️
- If the "More Offer/Response TLVs Following" flag is clear in the last Bundle Offer TLV received, look at the set of bundles offered and work out which ones to accept using the configured queueing policy. Record the set of accepted bundles so reception can be checked in the Bundle Passing Sub-Phase. Format one or more Bundle Response TLVs flagging the accepted offers and send them to the peer. If more than one Bundle Response TLV gets sent, all but the last one should have the "More Offer/Response TLVs Following" flag set to 1. At least one Bundle Response TLV MUST be sent, even if the node doesn't want to accept any of the offers. In that case, the Bundle Response TLV contains an empty set of acceptances 🥺
- If an Error TLV indicating a Bad String ID shows up during or after sending the Bundle Response TLVs, cancel any in-progress Initiator or Listener process, re-initialize the local dictionary, and terminate the connection to the peer 💀
- Restart the Timer(info) in case the peer doesn't start sending the requested bundles 🕰️
- Move to the REQUEST state 🏃♀️
REQUEST 🍒 In this state, the Initiator node expects to receive the bundles accepted in the Bundle Response TLV(s):
- Keep track of the bundles received, and delete them from the set of accepted bundles 📦
- If the Timer(info) expires while it's still waiting for bundles, format and send one or more Bundle Response TLVs listing the bundles that were accepted but haven't arrived yet. If more than one Bundle Response TLV gets sent, all but the last one should have the "More Offer/Response TLVs Following" flag set to 1 🫧
- If an Error TLV indicating a Bad String ID shows up during or after sending the Bundle Response TLVs, cancel any in-progress Initiator or Listener process, re-initialize the local dictionary, and terminate the connection to the peer 🙈
- Restart the Timer(info) after each bundle arrives, in case the peer doesn't keep sending the requested bundles 🌸
- When all the requested bundles have arrived, format a Bundle Response TLV with the Bundle Offer Count set to zero and the "More Offer/Response TLVs Following" flag cleared to 0, to tell the peer node that it's done. Also, signal the Listener in this node that the Initiator has finished. If the peer node is using a sequential policy, the Listener might still be in its initial state. In that case, it needs to start a timer so it can notice if the peer fails to start the Initiator state machine ⏰ After that, coordinate with the Listener state machine in the same node. Once the Listener has gotten the completion notification from the peer node and this Initiator has sent its completion notification, start the Timer(next_exchange) 🎉
- If the Timer(next_exchange) expires, move to the CREATE_DR state to restart the Information Exchange Phase 🔁
Note that if the Timer(info) times out a number of times (configurable, typically 3) without any bundles being received, this SHOULD generally be interpreted as the link to the peer no longer working, and the session should be terminated. However, some bundles can be very large and take a long time to transmit. Before terminating the session, this state machine needs to check whether a large bundle is actually being received, even though no new completed bundles have arrived since the timer last expired. In that case, the timer should be restarted without sending the Bundle Response TLV. Also, if the bundles are being exchanged over a transport protocol that can detect link failure, then the session MUST be terminated if the bundle exchange link is shut down because it has failed 🚨
5.3.2. State Definitions for the Listener Role ✨
The state machine component with the Listener role in each node starts out waiting to receive a RIB Dictionary update, followed by a set of RIB delivery predictabilities, during the Information Exchange Phase. From the Listener's point of view, the process does the following:
- Receive RIB Dictionary updates and RIB values from the peer. Note that in some cases no dictionary updates are needed, and the RIBD TLV will contain no entries or may be left out completely 🦋
- ✨ okay so once all the RIB messages have been received, we run the delivery predictability update algorithms (see Section 2.1.2) using the values from the Initiator node, and we apply any of the optional optimizations configured for this node (see Section 2.1.3). 💖
- 🧚 next, we take the updated delivery predictabilities plus the queueing policy and forwarding strategy configured for this node (see Section 2.1.4), and we look through the bundles already stored in the Listener node. That tells us which bundles to offer the Initiator, and we put them in order based on the forwarding strategy in use. The Bundle Offer TLVs also let the peer know about any PRoPHET ACKs the Listener role node has received. 🦋
- 🎀 send the list in one or more bundle offers, with one or more RIB dictionary updates in front if needed to add any EIDs required for the source or destination EIDs of the offered bundles. These updates MUST be marked as being sent by the Listener role, so the Initiator role in the peer processes them. 💅
- 🌸 wait for the Initiator to send bundle responses saying which bundles should be sent, plus a possibly modified order for sending. Send the accepted bundles in the specified order. The bundle sending will normally happen over a separate connection using a suitable DTN convergence layer. 🫶
- 🍓 once the sending is done, wait for a message with an empty Bundle Response TLV, which means the process finished correctly. 🎀
- 👑 the Listener process gets notified if any new bundles or PRoPHET ACKs show up at the node after the bundle sending from this information exchange is finished. The forwarding policy and the current delivery predictabilities then decide whether that info should go to the peer. If one or more bundles and/or ACKs ought to be forwarded, a new set of bundle offers gets sent. If the peer accepts them by sending bundle responses, the bundles and/or ACKS get transferred just like before. 🔥
- 🌈 periodically, the Initiator in the peer restarts the whole information exchange by sending a RIB TLV, which may optionally be preceded by RIB Dictionary entries if the updated RIB needs them. ⭐
Timers are there so the Listener doesn't lock up if messages don't arrive from the Initiator on time. The Listener restarts if the RIB isn't received, and it sends a Hello ACK message to force the Initiator to restart. If bundle response messages don't come in on time, the Listener re-sends the bundle offers and the associated dictionary updates. These are the states being used:
WAIT_DICT
The Listener subsidiary state machine moves into this state automatically and immediately from the state ESTAB in both peers. It also gets entered the same way if the Timer(next_exchange) expires in the peer, which signals the start of a new round of information exchange and bundle passing. This leads to one or more RIB TLVs being sent to the Listener by the peer node's Initiator. 💜
- 🧸 when a RIB Dictionary TLV comes in, use it to update the local dictionary, start (or restart, if it's already running) the
Timer(peer), and move to stateWAIT_RIB. If any entries in the RIB Dictionary TLV conflict with existing entries (meaning an entry uses the same String ID as a previously received entry, but its EID is different), send a Response message with an Error TLV containing a Dictionary Conflict indicator, abort any in-progress Initiator or Listener process, and terminate the connection to the peer. 🚨 - 🌷 if a Hello ACK message is received from the peer node, move to state
WAIT_DICTand restart the process. 🦋
If multiple timeouts happen (configurable, typically 3), assume the link is broken and terminate the session. 💀 Note that the RIB Dictionary and RIB TLVs may be combined into a single message. The RIB TLV should be passed on so it can be processed in the WAIT_RIB state. 🫧
WAIT_RIB
In this state, the Listener expects to receive one or more RIB TLVs and possibly some extra RIB Dictionary TLVs. 🌟
- 🧁 when entering this state, clear the set of received delivery predictabilities. 🧹
- 🕰️ whenever a new message arrives, restart the
Timer(peer)timer. ⏱️ - 📖 if a RIB dictionary TLV is received, use it to update the local dictionary and stay in this state. If any entries in the RIB Dictionary TLV conflict with existing entries (meaning an entry uses the same String ID as a previously received entry, but its EID is different), send a message with an Error TLV containing a Dictionary Conflict indicator, abort any in-progress Initiator or Listener process, and terminate the connection to the peer. 🙅♀️
- 💌 if a RIB TLV is received, record the received delivery predictabilities so they can be used when recalculating the local delivery predictabilities. If a delivery predictability value is received for an EID that's already in the set of received delivery predictabilities, overwrite the old value with the latest one. If a delivery predictability value comes in with a String ID that isn't in the dictionary, send a message with an Error TLV containing a Bad String ID indicator, abort any in-progress Initiator or Listener process, and terminate the connection to the peer. 🚫
- 🏁 when a RIB TLV arrives with the "More RIB TLVs" flag cleared, start recalculating the delivery predictabilities and stop the
Timer(peer). Use the revised delivery predictabilities plus the configured queueing and forwarding strategies to make a list of bundles to offer the peer node. 🎯 - 📦 record the state of the local dictionary in case the offer procedure has to restart. Figure out whether any new dictionary entries are needed for the Bundle Offer TLV(s). If so, record them in the local dictionary, then format and send RIB Dictionary entries in zero or more RIB Dictionary TLV messages to update the dictionary in the peer if necessary. 🗂️
- 🎁 format and send Bundle Offer TLV(s) carrying the identifiers of the bundles to be offered, along with any PRoPHET ACKs received or generated by this node. If more than one Bundle Offer TLV is sent, all but the last Bundle Offer TLV sent MUST have the "More Offer/Response TLVs Following" flag set to 1. 🌺
- 🚀 when all the Bundle Offer TLVs have been sent, start the
Timer(info)and move to stateOFFER. 🛫 - ⌛ if the
Timer(peer)expires, send a Hello ACK TLV to the peer, restart the timer, and move to stateWAIT_DICT. 🔁 - 🧯 if an Error TLV indicating a Dictionary Conflict or Bad String ID is received during or after sending the RIB Dictionary TLVs and/or the Bundle Offer TLVs, abort any in-progress Initiator or Listener process and terminate the connection to the peer. 🛑
- 👋 if a Hello ACK message is received from the peer node, move to state
WAIT_DICTand restart the process. 💫
OFFER
In this state, the Listener expects to receive one or more Bundle Response TLVs detailing the bundles the Initiator node accepted. The ordered list of accepted bundles gets handed to the bundle protocol agent, which controls sending them to the peer node over a separate connection. 📬
- 🥳 when a Bundle Response TLV comes in with a non-zero count of Bundle Offers, pull out the list of accepted bundles and send it to the bundle protocol agent so it can start transmission to the peer node. Keep the order of offers from the TLV intact. Restart the
Timer(info)unless the last Bundle Response TLV received has the "More Offer/Response TLVs Following" flag set to 0. If a Bundle Response TLV is received with a String ID that isn't in the dictionary, send a message with an Error TLV containing a Bad String ID indicator, abort any in-progress Initiator or Listener process, and terminate the connection to the peer. 🧾 - 🎉 after receiving a Bundle Response TLV with the "More Offer/Response TLVs Following" flag set to 0, stop the
Timer(info)and move to stateSND_BUNDLE. 🏃♀️ - ⏰ if the
Timer(info)expires, send a Hello ACK TLV to the peer, restart the timer, and move to stateWAIT_DICT. 🔄 - 🤝 if a Hello ACK message is received from the peer node, move to state
WAIT_DICTand restart the process. 🌙
SND_BUNDLE
In this state, the Listener keeps an eye on the sending of bundles to the Initiator peer node. If transmission gets disrupted, the Initiator node will, if possible, re-send the list of bundles that were accepted but haven't been received yet. The bundle protocol agent has to be told about any updates to the list of bundles to send (this will likely mean re-sending one or more bundles). Otherwise, the Listener just chills in this state. 😌
- 🌊 when a Bundle Response TLV is received with a non-zero count of Bundle Offers, pull out the list of accepted bundles and update the list previously passed to the bundle protocol agent, so it can (re)start transmission to the peer node. Keep the order of offers from the TLV as much as is possible. Restart the
Timer(info)unless the last Bundle Response TLV received has the "More Offer/Response TLVs Following" flag set to 0. If a Bundle Response TLV is received with a String ID that isn't in the dictionary, send a message with an Error TLV containing a Bad String ID indicator, abort any in-progress Initiator or Listener process, re-initialize the local dictionary, and restart the Information Exchange Phase as if theESTABstate had just been reached. 🔧 - 🎈 after receiving a Bundle Response TLV with the "More Offer/Response TLVs Following" flag set to 0, stop the
Timer(info)and wait for the bundle sending to complete. ⏸️ - 🕒 if the
Timer(info)expires, send a Hello ACK TLV to the peer, restart the timer, and move to stateWAIT_DICT. 🔔 - 🙌 if a Hello ACK message is received from the peer node, move to state
WAIT_DICTand restart the process. 🌼 - 🥂 when a Bundle Response TLV is received with a zero count of Bundle Offers, the Bundle Passing Sub-Phase is complete. Notify the Initiator that the Listener process is complete and move to state
WAIT_MORE. 🏆
As explained in the Initiator state REQUEST description, depending on the transport protocol (convergence layer) used to send the bundles to the peer node, it may be necessary during the bundle sending process to keep an eye on the liveness of the connection to the peer node in the Initiator process, using a timer. ⏲️💕
WAIT_MORE 👀 okay so in this state the Listener is basically on lookout, watching for new bundles to show up. 🦋 They can come from a few places:
- local applications on the node,
- other mobile nodes that connect to the node while this connection is open, and
- permanent connections such as might occur at an Internet gateway.
When the Listener hears that bundles have arrived, it decides whether they should be offered to the peer. ✨ The peer can also re-initiate the Information Exchange Phase periodically, so this isn't a one-and-done situation 🔁.
- When the bundle protocol agent tells the Listener that new bundles and/or new PRoPHET ACKs have been received, the Listener checks the selected forwarding policy and the current delivery predictabilities to see if any of the items ought to be offered to the connected peer. 💅 If so, it does the same operations described in
WAIT_RIBto build and send any necessary RIB Dictionary TLVs and RIB TLVs to the Initiator in the peer. - When all Bundle Offer TLVs have been sent, it starts the
Timer(info)and transitions to stateOFFER. ⏱️ - If a RIB dictionary TLV is received, the Listener uses it to update the local dictionary and transitions to state
WAIT_RIB. 🌸 If any of the entries in the RIB Dictionary TLV conflict with existing entries (i.e., an entry is received that uses the same String ID as some previously received entry, but the EID in the entry is different), it sends a message with an Error TLV containing a Dictionary Conflict indicator, aborts any in-progress Initiator or Listener process, and terminates the connection to the peer. 💀 Big yikes, no notes.
Note that the RIB Dictionary and RIB TLVs may be combined into a single message. 🧚 The RIB TLV should be passed on to be processed in the WAIT_RIB state.
5.3.3. Recommendations for Information Exchange Timer Periods
okay bestie, so the Information Exchange Phase (IEP) state definitions have a bunch of timers 🕰️, and this section is basically the cheat sheet for picking good periods for them. 🍓
Both Timer(info) and Timer(peer) exist so the state machines don't get stuck in the wrong state when the peer doesn't seem to respond in time. 🫶 That could be because a message got lost in the network, or because the peer just isn't answering. The best values depend on how fast the connection between the nodes is and how powerful the nodes running the PRoPHET implementations are. Values in the range 1 to 10 seconds SHOULD be used, with a value of 5 seconds RECOMMENDED as default. ✨ Don't set the period too low, though, because that can cause restarts you didn't need if the hardware is slow or there's a huge pile of information to process before responding. 🐢 When you're using a reliable transport like TCP, these timers basically act as a keep-alive 💖, so a dead connection gets caught as fast as possible. That way remedial action can happen (if it's possible) or the connection can be shut down tidily if the peer has wandered out of range. 👋
Timer(next_exchange) controls how often the information exchange state machines can be re-run during a single session between a pair of nodes. 🦋 Picking its period SHOULD reflect the trade-off between load on the node's processor and wanting bundles from other nodes forwarded in a timely way. 💜 It is RECOMMENDED that the timer periods be randomized over a range from 50% to 150% of the base value, so multiple nodes don't all end up synchronized 🌈. Consideration SHOULD be given to how long typical encounters last and how likely it is for groups of nodes to meet when you set this period. ⭐ Base values in the range of 20 to 60 seconds are RECOMMENDED. 🎀
5.3.4. State Tables for Information Exchange
Okay, this section shows the state transitions nodes go through during the Information Exchange Phase. 🌸 There are state tables for the Initiator role and for the Listener role of the subsidiary state machines. Both nodes run machines in each role during the Information Exchange Phase 👯, and they can do that concurrently or sequentially, depending on the implementation, as explained in Section 5.3. 🔥 The state tables in this section should be read alongside the state descriptions in Sections 5.3.1 and 5.3.2, so keep those open too 📖.
5.3.4.1. Common Notation, Operations and Events
The following notation is used:
nS Node that sent the Hello SYN message.
nA Node that sent the Hello SYNACK message.Now the events that both the Initiator and Listener state tables share 💅:
ErrDC Dictionary Conflict Error TLV received.
ErrBadSI Bad String ID Error TLV received.
HelloAck Hello ACK TLV received. This message is delivered to
both Initiator and Listener roles in order to cause a
restart of the Information Exchange Phase in the event
of message loss or protocol problems.
InitStart Sent by Listener role to Initiator role to signal the
Initiator role to commence sending messages to peer.
If the Listener instance is running in the node that
sent the Hello SYN (nS), then InitStart is signaled
immediately when the state is entered. For the node
that sent the Hello SYNACK (nA), InitStart may be
signaled immediately if the operational policy requires
concurrent operation of the Initiator and Listener
roles or postponed until the Listener role state
machine has reached a state defined by the configured
policy.
RIBnotlast RIB TLV received with "More RIB TLVs" flag set to 1.
RIBlast RIB TLV received with "More RIB TLVs" flag set to 0.
REQnotlast Bundle Response TLV received with More Offer/Response
TLVs Following flag set to 1.
REQlast Bundle Response TLV received with More Offer/Response
TLVs Following flag set to 0.
RIBDi RIBD TLV received with Sent by Listener flag set to 0
(i.e., it was sent by Initiator role).
RIBDl RIBD TLV received with Sent by Listener flag set to 1
(i.e., it was sent by Listener role).
Timeout(info) The Timer(info) has expired.
Timeout(peer) The Timer(peer) has expired.Both the Initiator and Listener state tables use these common operations too 🛠️:
- The "Initialize Dictionary" operation empties any existing local dictionary and then inserts the two starter entries: the EID of the node that sent the Hello SYN (String ID 0) and the EID of the node that sent the Hello SYNACK (String ID 1). 🌱
- The "Send RIB Dictionary Updates" operation goes like this 📨:
- Figure out what dictionary updates are needed for any extra EIDs in the previously selected RIB entries set that aren't already in the dictionary, and update the local dictionary with those EIDs. The set of dictionary updates may be empty if no extra EIDs are needed. ✨ It may even be empty on the first run if sequential operation was chosen, this is the second node to start, and the EIDs it needed were already in the set the first node sent 🫠.
- Format zero or more RIBD TLVs for the set of dictionary updates identified in the "Build RIB Entries" operation and send them to the peer. The RIBD TLVs MUST have the "Sent by Listener" flag set to 0 if the updates are sent by the Initiator role and to 1 if sent by the Listener role. 🎯 In the case of the Initiator role, an empty RIBD TLV MUST be sent even if the set of updates is empty, in order to trigger the Listener state machine. 🔔
- The "Update Dictionary" operation uses received RIBD TLV entries to update the local dictionary. 🧩 The received entries get checked against the existing dictionary. If the String ID in an entry is already in use, the entry is accepted only if the EID in the received entry is identical to the one stored in the dictionary before. If it is identical, the entry stays unchanged. But if it isn't, an Error Response message carrying an Error TLV that indicates Dictionary Conflict is sent to the peer, the whole received RIBD TLV gets ignored, and the Initiator and Listener processes are restarted as if the ESTAB state has just been reached. 😭
- The "Abort Exchange" operation means aborting any in-progress information exchange state machines and terminating the connection to the peer. 🚪
- The "Start TI" operation means (re)starting the Timer(info) timer. ▶️
- The "Start TP" operation means (re)starting the Timer(peer) timer. ▶️
- The "Cancel TI" operation means canceling the Timer(info) timer. ⏹️
- The "Cancel TP" operation is defined as canceling the Timer(info) timer. 🙈
5.3.4.2. State Tables for the Initiator Role 🎀
okay so the Initiator role runs on a bunch of operations, and they're literally the building blocks for the whole state machine 💅 here they are:
- The "Build RIB Entries" operation is:
- Recording the state of the local dictionary.
- Figuring out which EIDs get RIB entries sent during this run of the Initiator role state machine component. If this is a second or subsequent run of the state machine on this node during the current session with the connected peer, the set of EIDs may be empty if nothing has changed since the previous run 🦋
- Working out and pulling out the current delivery predictability information for the set of EIDs that got selected ✨
- The "Send RIB Entries" operation formats one or more RIB TLVs using the set of RIB entries from "Build RIB Entries" and sends them to the peer. If the set is empty, one RIB TLV with zero entries gets sent. If more than one RIB TLV is sent, all but the last one MUST have the "More RIB TLVs" flag set to 1, and the last or only one MUST have the flag set to 0 🌸
- The "Clear Bundle Lists" operation is just emptying the lists of bundles offered by the peer and the bundles requested from the peer 🧹
- The "Notify ACKs" operation tells the bundle protocol agent that PRoPHET ACKs have been received for one or more bundles in a Bundle Offer TLV, using the Bundle Delivered interface (see Section 2.2) 📬
- The "Record Offers" operation records every bundle offered in a Bundle Offer TLV in the list of bundle offers 📝
- The "Select for Request" operation prunes and sorts the list of offered bundles into the list of requested bundles, according to policy and the resources available for sending to the offering node 🍓
- The "Send Requests" operation formats one or more non-empty Bundle Response TLVs and sends them to the offering node. If more than one Bundle Offer TLV is sent, all but the last one MUST have the "More Offer/Response TLVs Following" flag set to 1, and the last or only one MUST have the flag set to 0 💖
- The "Record Bundle Received" operation deletes a successfully received bundle from the list of requests 🗑️
- The "All Requests Done" operation formats and sends an empty Bundle Offer TLV to the offering node, with the "More Offer/Response TLVs Following" flag set to 0 🫶
- The "Check Receiving" operation checks with the node's bundle protocol agent whether bundle reception from the peer node is in progress right now. This is needed in case a timeout hits while waiting for bundle reception and a very large bundle is being processed 🐢
- The "Start NE" operation (re)starts the Timer(next_exchange) ⏰
The following events are specific to the Initiator role state machine:
LastBndlRcvd: a bundle is received from the peer and it's the only remaining bundle in the Bundle Requests List 🌟NotLastBndlRcvd: a bundle is received from the peer and it's not the only remaining bundle in the Bundle Requests List 🌷OFRnotlast: a Bundle Offer TLV is received with the "More Offer/Response TLVs Following" flag set to 1 🧁OFRlast: a Bundle Offer TLV is received with the "More Offer/Response TLVs Following" flag set to 0 🎯Timeout(next_exch): the Timer(next_exchange) has expired ⌛
Here are the state tables, bestie 👑
State: CREATE_DR
+==================================================================+
| Condition | Action | New State |
+==================+===================================+===========+
| On Entry | If previous state was ESTAB: | |
| | Initialize Dictionary | |
| | Always: | |
| | Build RIB Entries | |
| | Wait for Init Start | CREATE_DR |
+------------------+-----------------------------------+-----------+
| InitStart | Send RIB Dictionary Updates | |
| | Send RIB Entries | |
| | Start TI | SEND_DR |
+------------------+-----------------------------------+-----------+
| ErrDC | Abort Exchange |(finished) |
+------------------+-----------------------------------+-----------+
| ErrBadSI | Abort Exchange |(finished) |
+------------------+-----------------------------------+-----------+
| HelloAck | Abort Exchange | CREATE_DR |
+==================================================================+State: SEND_DR
+==================================================================+
| Condition | Action | New State |
+==================+===================================+===========+
| On Entry | Clear Bundle Lists | SEND_DR |
+------------------+-----------------------------------+-----------+
| Timeout(info) | Send RIB Dictionary Updates | |
| | Send RIB Entries (note 1) | SEND_DR |
+------------------+-----------------------------------+-----------+
| RIBDl received | Update Dictionary (note 2) | |
| | If Dictionary Conflict found: | |
| | Abort Exchange | CREATE_DR |
| | Else: | |
| | Start TI | SEND_DR |
+------------------+-----------------------------------+-----------+
| OFRnotlast | Notify ACKs | |
| | Record Offers | |
| | Start TI | SEND_DR |
+------------------+-----------------------------------+-----------+
| OFRlast | Cancel TI | |
| | Notify ACKs | |
| | Record Offers | |
| | Select for Request | |
| | Send Requests | |
| | Start TI | REQUEST |
+------------------+-----------------------------------+-----------+
| ErrDC | Abort Exchange |(finished) |
+------------------+-----------------------------------+-----------+
| ErrBadSI | Abort Exchange |(finished) |
+------------------+-----------------------------------+-----------+
| HelloAck | Abort Exchange | CREATE_DR |
+==================================================================+State: REQUEST
+==================================================================+
| Condition | Action | New State |
+==================+===================================+===========+
| Timeout(info) | Check Receiving | |
| | If bundle reception in progress: | |
| | Start TI | REQUEST |
| | Otherwise: | |
| | Send Requests | |
| | Start TI (note 3) | REQUEST |
+------------------+-----------------------------------+-----------+
| NotLastBndlRcvd | Record Bundle Received | |
| | Start TI | REQUEST |
+------------------+-----------------------------------+-----------+
| LastBndlRcvd | Cancel TI | |
| | All Requests Done | |
| | Start NE | REQUEST |
+------------------+-----------------------------------+-----------+
|Timeout(next_exch)| | CREATE_DR |
+------------------+-----------------------------------+-----------+
| HelloAck | Abort Exchange | CREATE_DR |
+==================================================================+Note 1: no response to the RIB has arrived before the timer expired, so we re-send the dictionary and RIB TLVs. If the timeout keeps happening, communication has probably failed, and the connection MUST be terminated. 🚨
Note 2: if a Dictionary Conflict error has to be sent, the state machine gets aborted. If this keeps happening, it's likely there's either a serious software problem or a security issue. The connection MUST be terminated. 😱
Note 3: the remaining requested bundles haven't arrived before the timer expired, so we re-send the list of outstanding requests. If the timeout keeps happening, communication has probably failed, and the connection MUST be terminated. 💀
5.3.4.3. State Tables for the Listener Role 🧚
the Listener role has its own set of rules and state tables, and it uses these operations:
- The "Clear Supplied RIBs" operation sets up an empty container to hold the set of RIBs supplied by the peer node 🫧
- The "Record RIBs Supplied" operation is:
- Taking the RIB entries out of a received RIB TLV.
- Checking that the String ID used in each entry is in the dictionary. If it isn't, an Error TLV containing the offending String ID gets sent to the peer, and the Initiator and Listener processes get aborted and restarted as if the ESTAB state had just been reached 🙈
- If all the String IDs are in the dictionary, recording the delivery predictabilities for each EID in the entries 🔥
- The "Recalc Dlvy Predictabilities" operation uses the algorithms defined in Section 2.1.2 to update the local set of delivery predictabilities, using the using the set of delivery predictabilities supplied by the peer in RIB TLVs 🧮
- The "Determine Offers" operation figures out the set of bundles to offer to the peer. The local delivery predictabilities and the ones supplied by the peer get compared, and a prioritized choice of the bundles stored in this node gets made for the offer, according to the configured queueing policy and forwarding strategy 🌈
- The "Determine ACKs" operation gets the set of PRoPHET ACKs recorded by the bundle protocol agent that need to be forwarded to the peer. The list of PRoPHET ACKs is maintained internally by the PRoPHET protocol implementation rather than the main bundle protocol agent (see Section 3.5) 🗂️
- The "Determine Offer Dict Updates" operation works out any extra EIDs that aren't already in the dictionary, records the previous state of the local dictionary, and then adds the required extra entries to the dictionary ✨
- okay so the "Send Offers" operation 💌 formats one or more non-empty Bundle Offer TLVs, stuffs in the sets of Offers and PRoPHET ACKs we already figured out, and sends them to the peer node. If more than one Bundle Offer TLV goes out, every one except the last MUST have the
More Offer/Response TLVs Followingflag set to 1, and the last or only one MUST have that flag set to 0. 🎀 - the "Record Requests" operation 📝 records every bundle offered in a Bundle Offer TLV into the list of bundles offers. Duplicates MUST be ignored. The order of requests in the TLVs MUST be maintained as much as is possible, bestie. It's possible a bundle has to be re-sent, and that can lead to out-of-order delivery, so keep that in mind 🌸
- the "Send Bundles" operation 🚀 sends the bundles in the requested list, in the order they were requested. To pull this off, the list has to be communicated to the bundle protocol agent (see Section 2.2). 🦋
- the "Check Initiator Start Point" operation 👑 checks the configured sequential operation policy to see if the Listener role has reached the point where the Initiator role should start. If it has, the InitStart notification gets sent to the Initiator role in the same node. ✨
The following events are specific to the Listener role state machine, and they're giving main character energy 🎬
RIBnotlast: a RIB TLV comes in with theMore RIB TLVsflag set to 1. 🌈RIBlast: a RIB TLV comes in with theMore RIB TLVsflag set to 0 and a non-zero count of RIB Entries. 💜REQnotlast: a Bundle Response TLV comes in with theMore Offer/Response TLVs Followingflag set to 1. 🧚REQlast: a Bundle Response TLV comes in with theMore Offer/Response TLVs Followingflag set to 0 and a non-zero count of bundle offers. 🍓REQempty: a Bundle Response TLV comes in with theMore Offer/Response TLVs Followingflag set to 0 and a zero count of bundle offers. 🙈
State: WAIT_DICT
+==================================================================+
| Condition | Action | New State |
+==================+===================================+===========+
| On Entry | Check Initiator Start Point | WAIT_DICT |
+------------------+-----------------------------------+-----------+
| RIBDi | Update Dictionary (note 1) | |
| | If Dictionary Conflict found: | |
| | Abort Exchange |(finished) |
| | Else: | |
| | Start TP | WAIT_RIB |
+------------------+-----------------------------------+-----------+
| HelloAck | Abort Exchange | WAIT_DICT |
+==================================================================+State: WAIT_RIB
+==================================================================+
| Condition | Action | New State |
+==================+===================================+===========+
| On Entry | Clear Supplied RIBS | WAIT_RIB |
+------------------+-----------------------------------+-----------+
| RIBDi | Update Dictionary (note 1) | |
| | If Dictionary Conflict found: | |
| | Abort Exchange |(finished) |
| | Else: | |
| | Start TP | WAIT_RIB |
+------------------+-----------------------------------+-----------+
| RIBnotlast | Record RIBS Supplied (note 2) | |
| | If EID missing in dictionary: | |
| | Abort Exchange |(finished) |
| | Else: | |
| | Start TP | WAIT_RIB |
+------------------+-----------------------------------+-----------
| RIBlast | Check Initiator Start Point | |
| | Record RIBS Supplied (note 2) | |
| | If EID missing in dictionary: | |
| | Abort Exchange |(finished) |
| | Otherwise | |
| | Recalc Dlvy | |
| | Predictabilities | |
| | Cancel TP | |
| | Determine Offers | |
| | Determine ACKs | |
| | Determine Offer | |
| | Dict Updates | |
| | Send RIB Dictionary | |
| | Updates | |
| | Send Offers | |
| | Start TI | OFFER |
+------------------+-----------------------------------+-----------+
| HelloAck | Abort Exchange | WAIT_DICT |
+------------------+-----------------------------------+-----------+
|Any Other TLV rcvd| Abort Exchange |(finished) |
+------------------+-----------------------------------+-----------+
| Timeout(peer) | Send RIB Dictionary Updates | |
| | Send Offers | |
| | Start TI (note 3) | OFFER |
+==================================================================+State: OFFER
+==================================================================+
| Condition | Action | New State |
+==================+===================================+===========+
| REQnotlast | Send Bundles | |
| | Start TI | OFFER |
+------------------+-----------------------------------+-----------+
| REQlast | Cancel TI | |
| | Check Initiator Start Point | |
| | Send Bundles | SND_BUNDLE|
+------------------+-----------------------------------+-----------+
| REQempty | Cancel TI | |
| | Check Initiator Start Point | WAIT_MORE|
+------------------+-----------------------------------+-----------+
| HelloAck | Abort Exchange | WAIT_DICT |
+------------------+-----------------------------------+-----------+
| Timeout(info) | Send RIB Dictionary Updates | |
| | Send Offers | |
| | Start TI (note 3) | OFFER |
+==================================================================+State: SND_BUNDLE
+==================================================================+
| Condition | Action | New State |
+==================+===================================+===========+
| REQnotlast | Send Bundles | |
| | Start TI | SND_BUNDLE|
+------------------+-----------------------------------+-----------+
| REQlast | Cancel TI | |
| | Send Bundles | SND_BUNDLE|
+------------------+-----------------------------------+-----------+
| REQempty | Cancel TI | |
| | Check Initiator Start Point | WAIT_MORE|
+------------------+-----------------------------------+-----------+
| HelloAck | Abort Exchange | WAIT_DICT |
+------------------+-----------------------------------+-----------+
| Timeout(info) | Send RIB Dictionary Updates | |
| | Send Offers | |
| | Start TI (note 3) | OFFER |
+==================================================================+State: WAIT_MORE
+==================================================================+
| Condition | Action | New State |
+==================+===================================+===========+
| More Bundles | Determine Offers | |
| | Determine ACKs | |
| | Determine Offer | |
| | Dict Updates | |
| | Send RIB Dictionary | |
| | Updates | |
| | Send Offers | |
| | Start TI | OFFER |
+------------------+-----------------------------------+-----------+
| RIBDi | Update Dictionary (note 1) | |
| | If Dictionary Conflict found: | |
| | Abort Exchange |(finished) |
| | Else: | |
| | Start TP | WAIT_RIB |
+------------------+-----------------------------------+-----------+
| REQnotlast | Send Bundles | |
| | Start TI | SND_BUNDLE|
+------------------+-----------------------------------+-----------+
| REQlast | Cancel TI | |
| | Send Bundles | SND_BUNDLE|
+------------------+-----------------------------------+-----------+
| REQempty | Cancel TI | |
| | Check Initiator Start Point | SND_BUNDLE|
+------------------+-----------------------------------+-----------+
| HelloAck | Abort Exchange | WAIT_DICT |
+------------------+-----------------------------------+-----------+
| Timeout(info) | Send RIB Dictionary Updates | |
| | Send Offers | |
| | Start TI (note 3) | OFFER |
+==================================================================+Note 1: Both the dictionary and the RIB TLVs may come in the same PRoPHET message. 🧩 When that happens, the state changes to WAIT_RIB, and then the RIB gets processed right away. ⚡
Note 2: Send an ACK if the timer for the peering node expires. 💌 Either the link has been broken, in which case the link setup restarts, or it triggers the Information Exchange Phase to restart. 🔄
Note 3: okay so when the RIB shows up, the PRoPHET agent is allowed to update its delivery predictabilities using Section 2.1.2 🦋 Then the delivery predictabilities and the RIB get used together with whatever forwarding strategy is in use to cook up a bundle offer TLV. That offer then gets sent off to the peering node 💌
Note 4: no more bundles are being requested by the other node, so the transfer is complete ✅ bestie, we did it 🎀
Note 5: the timer ran out and no response to the bundle offer ever came back, so we re-send the bundle offer 🔁 persistence is a whole vibe 💅
5.4. Interaction with Nodes Using Version 1 of PRoPHET ✨
There are already implementations of PRoPHET out there that are based on earlier draft versions of this spec and use version 1 of the protocol 🕰️ There are a bunch of big differences between version 1 and version 2 as described in this document, and honestly they're kind of a lot:
- In version 1, the delivery predictability update equations were totally different. The transitivity equation (Equation 3) could lead to degraded performance or non-delivery of bundles in some circumstances 😭
- In the current version , constraints were placed on the String IDs generated by each node 🆔 The goal is that it's impossible for there to be a conflict if the IDs get generated concurrently and independently in the two nodes. Iconic engineering, no notes 🫶
- In the current version, a flag was added to the Routing Information Base Dictionary TLV so you can tell apart dictionary updates sent by the Initiator role and the ones sent by the Listener role 🚩
- In the current version, the Bundle Offer and Response TLVs got a major glow-up 💖 The version 2 TLVs were given brand new TLV Type numbers, and the version 1 TLVs (types
0xA2and0xA3) are now deprecated 🥀 For each bundle specifier, version 2 sends the source EID along with the creation timestamp, so the bundle is uniquely identified 🔍 Version 2 also transmits the fragment payload offset and length when the offered bundle is a bundle fragment 🧩 The payload length can optionally be transmitted for each bundle, whether or not it's a fragment, which gives the receiver extra info that can help when deciding which bundle offers to accept 🤔 - The behavior of the system after the first Information Exchange Phase got better defined 📚 The state machine was altered to better describe how the ongoing operations work. This involved removing the high-level state WAIT_INFO and adding two states in the Listener role subsidiary state machine, SND_BUNDLE and WAIT_MORE 🪄 The protocol on the wire was not changed by this update to how the state machine is described 🙌 That said, the spec for the later stages of operation was kinda vague, and different implementers might have read it in different ways 🙈
A node implementing version 2 of the PRoPHET protocol as defined in this document MAY ignore a communication opportunity with a node that sends a HELLO message saying it uses version 1 🚫 Or it MAY partially downgrade and respond to messages as if it were a version 1 node 🌗 This means that the version field in all message headers MUST contain 1 📌
It is RECOMMENDED that the version 2 node use the metric update equations defined in this document, even when it's talking to a version 1 node 💅 Doing this will partially inhibit the problems with the transitivity equation in version 1 🙌 The version 2 node should also modify any received metrics that are greater than (1 - delta) so they become (1 - delta), so it doesn't turn into a "sink" for bundles that aren't destined for this node 🕳️ Also, version 1 nodes cannot be explicitly offered bundle fragments, and an exchange with a node supporting version 1 MUST use the, now deprecated, previous versions of the Bundle Offer and Response TLVs 📦
Generally, nodes using version 1 should be upgraded if at all possible, because problems have been identified 🆙 Literally go upgrade them 💀
6. Security Considerations 🔐
Currently, PRoPHET does not specify any special security measures 😬 As a routing protocol for intermittently connected networks, PRoPHET is a target for various attacks 🎯 The various known possible vulnerabilities are discussed in this section, so buckle up 🎢
The attacks described here are not problematic if all nodes in the network can be trusted and are working towards a common goal ✨ If there exists such a set of nodes, but there also exist malicious nodes, these security problems can be solved by introducing an authentication mechanism when two nodes meet. For example, a public key system could be used 🗝️ Thus, only nodes known to be members of the trusted group of nodes are allowed to participate in the routing 🫂 This of course introduces the additional problem of key distribution, but that is not addressed here 🙃
Where suitable, the mechanisms (such as key management and bundle authentication or integrity checks) and terminology specified by the Bundle Security Protocol [RFC6257] are to be used 🔏
6.1. Attacks on the Operation of the Protocol ⚠️
There are a number of kinds of attacks on the operation of the protocol that it would be possible to stage on a PRoPHET network 👀 The attacks and possible remedies are listed here, one by one 📝
6.1.1. Black-Hole Attack 🕳️
A malicious node sets its delivery predictabilities for all destinations to a value close to or exactly equal to 1, and/or requests all bundles from nodes it meets, and then does not forward any bundles 💀 This has two effects, and both cause messages to be drawn towards the black hole instead of to their correct destinations 😱
- A node encountering a malicious node will try to forward all its bundles to the malicious node, creating the belief that the bundle has been very favorably forwarded 🤥 Depending on the forwarding strategy and queueing policy in use, this might hamper future forwarding of the bundle and/or lead to premature dropping of the bundle 🗑️
- Due to the transitivity, the delivery predictabilities reported by the malicious node will affect the delivery predictabilities of other nodes 🌀 This will create a gradient for all destinations, with the black hole as the "center of gravity" that all bundles traverse towards 🧲 This should be particularly severe in connected parts of the network 🚨
6.1.1.1. Attack Detection 🔎
A node receiving a set of delivery predictabilities that are all at or close to 1 should be suspicious 🤨 Similarly, a node that accepts all bundles and offers none might be considered suspicious 👀 However, these conditions are not impossible in normal operation, so don't panic 🫠
6.1.1.2. Attack Prevention/Solution 🛡️
To prevent this attack, authentication between nodes that meet needs to be present 🔑 Nodes can also inspect the received metrics and bundle acceptances/offers for suspicious patterns, and terminate communications with nodes that appear suspicious 🚫 The natural evolution of delivery predictabilities should mean that a genuine node would not be permanently ostracized, even if the values lead to termination of a communication opportunity on one occasion 💜 The epidemic nature of PRoPHET would mean that such a termination rarely leads to non-delivery of bundles 🦠
6.1.2. Limited Black-Hole Attack / Identity Spoofing 🎭
A malicious node misrepresents itself by claiming to be someone else 🥸 The effects of this attack are:
- The effects of the black-hole attack listed above hold for this attack as well, with the exception that only the delivery predictabilities and bundles for one particular destination are affected. This could be used to "steal" the data that should be going to a particular node 🦹
- In addition to the above problems, PRoPHET ACKs will be issued for the bundles that are delivered to the malicious node 📤 This will cause these bundles to be removed from the network, reducing the chance that they will reach their real destination 📉
6.1.2.1. Attack Detection 🔍
The destination can detect that this kind of attack has occurred (but it cannot prevent the attack) when it receives a PRoPHET ACK for a bundle destined to itself, but for which it did not receive the corresponding bundle 🕵️♀️
6.1.2.2. Attack Prevention/Solution 🛡️
To prevent this attack, authentication between nodes that meet needs to be present 🔐
6.1.3. Fake PRoPHET ACKs 🎣
A malicious node may issue fake PRoPHET ACKs for all bundles carried by nodes it met, or only bundles for a certain destination if the attack is targeted at a single node 🪤 The affected bundles will be deleted from the network, greatly reducing their probability of being delivered to the destination 😵
6.1.3.1. Attack Prevention/Solution 🛡️
If a public key cryptography system is in place, this attack can be prevented by mandating that all PRoPHET ACKs be signed by the destination ✍️ Similarly to other solutions using public key cryptography, this introduces the problem of key distribution 🔁
6.1.4. Bundle Store Overflow 🌊
After encountering and receiving the delivery predictability information from the victim, a malicious node may generate a large number of fake bundles for the destination for which the victim has the highest delivery predictability 🫣 This will cause the victim to most likely accept these bundles, filling up its bundle storage, possibly at the expense of other, legitimate, bundles 📦 This problem is transient, as the messages will be removed when the victim meets the destination and delivers the messages 🫡
6.1.4.1. Attack Detection 🔎
If it is possible for the destination to figure out that the bundles it is receiving are fake, it could report that malicious actions are underway 🚨
6.1.4.2. Attack Prevention/Solution 🛡️
This attack could be prevented by requiring sending nodes to sign all bundles they send 🖊️ By doing this, intermediate nodes could verify the integrity of the messages before accepting them for forwarding ✅
6.1.5. Bundle Store Overflow with Delivery Predictability Manipulation 🧨
A more sophisticated version of the attack in the previous section can be attempted 😈 The effect of the previous attack was lessened, since the destination node of the fake bundles existed. That caused fake bundles to be purged from the network when the destination was encountered 🧹 The malicious node may now use the transitive property of the protocol to boost the victim's delivery predictabilities for a non-existent destination 🪄 After this, it creates a large number of fake bundles for this non-existent destination and offers them to the victim 🎁 As before, these bundles will fill up the bundle storage of the victim 📦 The impact of this attack will be greater, as there is no probability of the destination being encountered and the bundles being acknowledged 😩 Thus, they will remain in the bundle storage until they time out (the malicious node may set the timeout to a large value) or until they are evicted by the queueing policy ⏳
The delivery predictability for the fake destination may spread in the network due to the transitivity, but this is not a problem, as it will eventually age and fade away 🌫️
The impact of this attack could be increased if multiple malicious nodes collude, as network resources can be consumed at a greater speed and at many different places in the network simultaneously 🚀💀
6.2. Interactions with External Routing Domains 🌸
okay so bestie, users can totally choose to connect two regions of sparsely connected nodes through a connected network like the Internet, where some other routing protocol is already running 🌐. To that network, PRoPHET traffic just looks like any other application-layer data, no cap. So extra care has to go into setting up these gateway nodes and their interconnections, so malicious nodes can't use them to attack the infrastructure of the connected network 🚧. The traffic generated should not be significantly more than what a single regular user end host could create on the network. Main character energy is being a normal user, not a flood machine 💅
7. IANA Considerations 📋
okay, the IANA part is where we get organized 🗂️ Following the policies in "Guidelines for Writing an IANA Considerations Section in RFCs" (RFC 5226 [RFC5226]), these are the name spaces PRoPHET defines:
- For fields in the PRoPHET message header (Section 4.1):
- DTN Routing Protocol Number
- PRoPHET Protocol Version
- PRoPHET Header Flags
- PRoPHET Result Field
- PRoPHET Codes for Success and Codes for Failure
- Identifiers for TLVs carried in PRoPHET messages:
- PRoPHET TLV Type (Section 4.2)
- Definitions of TLV Flags and other flag fields in TLVs:
- Hello TLV Flags (Section 4.3.1)
- Error TLV Flags (Section 4.3.2)
- Routing Information Base (RIB) Dictionary TLV Flags (Section 4.3.3)
- Routing Information Base (RIB) TLV Flags (Section 4.3.4)
- Routing Information Base (RIB) Flags per entry (Section 4.3.4)
- Bundle Offer and Response TLV Flags (Section 4.3.5)
- Bundle Offer and Response B Flags per offer or response (Section 4.3.5)
The following subsections list the registries that have been created. Initial values for the registries are given below. Future assignments for unassigned values are to be made through the Specification Required policy. Where specific values are defined in the IANA registries according to the specifications in the subsections below, the registry refers to this document as defining the allocation ✨
7.1. DTN Routing Protocol Number 🔢
The encoding of the Protocol Number field in the PRoPHET header (Section 4.1) is:
+--------------------------+-----------+---------------+
| Protocol | Value | Reference |
+--------------------------+-----------+---------------+
| PRoPHET Protocol | 0x00 | This document |
| Unassigned | 0x01-0xEF | |
| Private/Experimental Use | 0xF0-0xFF | This document |
+--------------------------+-----------+---------------+7.2. PRoPHET Protocol Version 🎀
The encoding of the PRoPHET Version field in the PRoPHET header (Section 4.1) is:
+----------------------------+-----------+---------------+
| Version | Value | Reference |
+----------------------------+-----------+---------------+
| Reserved (do not allocate) | 0x00 | This document |
| PRoPHET v1 | 0x01 | This document |
| PRoPHET v2 | 0x02 | This document |
| Unassigned | 0x03-0xEF | |
| Private/Experimental Use | 0xF0-0xFE | This document |
| Reserved | 0xFF | |
+----------------------------+-----------+---------------+7.3. PRoPHET Header Flags 🚩
The following Flags are defined for the PRoPHET Header (Section 4.1):
+------------+--------------+-----------+
| Meaning | Bit Position | Reference |
+------------+--------------+-----------+
| Unassigned | Bit 0 | |
| Unassigned | Bit 1 | |
| Unassigned | Bit 2 | |
| Unassigned | Bit 3 | |
+------------+--------------+-----------+7.4. PRoPHET Result Field 🦋
The encoding of the Result field in the PRoPHET header (Section 4.1) is:
+--------------------------+-------------+---------------+
| Result Value | Value | Reference |
+--------------------------+-------------+---------------+
| Reserved | 0x00 | This document |
| NoSuccessAck | 0x01 | This document |
| AckAll | 0x02 | This document |
| Success | 0x03 | This document |
| Failure | 0x04 | This document |
| ReturnReceipt | 0x05 | This document |
| Unassigned | 0x06 - 0x7F | |
| Private/Experimental Use | 0x80 - 0xFF | This document |
+--------------------------+-------------+---------------+7.5. PRoPHET Codes for Success and Codes for Failure 🌈
The encoding for Code field in the PRoPHET header (Section 4.1) for "Success" messages is:
+--------------------------+-------------+---------------+
| Code Name | Values | Reference |
+--------------------------+-------------+---------------+
| Generic Success | 0x00 | This document |
| Submessage Received | 0x01 | This document |
| Unassigned | 0x02 - 0x7F | |
| Private/Experimental Use | 0x80 - 0xFF | This document |
+--------------------------+-------------+---------------+The encoding for Code in the PRoPHET header (Section 4.1) for "Failure" messages is:
+----------------------------+-------------+---------------+
| Code Name | Values | Reference |
+----------------------------+-------------+---------------+
| Reserved (do not allocate) | 0x00 - 0x01 | This document |
| Unspecified Failure | 0x02 | This document |
| Unassigned | 0x03 - 0x7F | |
| Private/Experimental Use | 0x80 - 0xFE | This document |
| Error TLV in Message | 0xFF | This document |
+----------------------------+-------------+---------------+7.6. PRoPHET TLV Type 🧚
The TLV Types defined for PRoPHET (Section 4.2) are:
+------------------------------+-------------+---------------+
| Type | Value | Reference |
+------------------------------+-------------+---------------+
| Reserved (do not allocate) | 0x00 | This document |
| Hello TLV | 0x01 | This document |
| Error TLV | 0x02 | This document |
| Unsassigned | 0x03 - 0x9F | |
| RIB dictionary TLV | 0xA0 | This document |
| RIB TLV | 0xA1 | This document |
| Bundle Offer (deprecated) | 0xA2 | This document |
| Bundle Response (deprecated) | 0xA3 | This document |
| Bundle Offer (v2) | 0xA4 | This document |
| Bundle Response (v2) | 0xA5 | This document |
| Unassigned | 0xA6 - 0xCF | |
| Private/Experimental Use | 0xD0 - 0xFF | This document |
+------------------------------+-------------+---------------+7.7. Hello TLV Flags 💜
The following TLV Flags are defined for the Hello TLV (Section 4.3.1). Flag numbers 0, 1, and 2 are treated as a 3-bit unsigned integer with 5 of the 8 possible values allocated, and the other 3 reserved. The remaining bits are treated individually:
+----------------------------+---------------------+---------------+
| Meaning | Value | Reference |
+----------------------------+---------------------+---------------+
| | (Flags 0, 1, and 2) | |
| Reserved (do not allocate) | 0b000 | This document |
| SYN | 0b001 | This document |
| SYNACK | 0b010 | This document |
| ACK | 0b011 | This document |
| RSTACK | 0b100 | This document |
| Unassigned | 0b101 - 0b111 | |
| | (Flags 3 - 7) | |
| Unassigned | Flag 3 | |
| Unassigned | Flag 4 | |
| Unassigned | Flag 5 | |
| Unassigned | Flag 6 | |
| L Flag | Flag 7 | This document |
+----------------------------+---------------------+---------------+7.8. Error TLV Flags ⭐
The TLV Flags field in the Error TLV (Section 4.3.2) is treated as an unsigned 8-bit integer encoding the Error TLV number. The following values are defined:
+--------------------------+------------------+---------------+
| Error TLV Name | Error TLV Number | Reference |
+--------------------------+------------------+---------------+
| Dictionary Conflict | 0x00 | This document |
| Bad String ID | 0x01 | This document |
| Unassigned | 0x02 - 0x7F | |
| Private/Experimental Use | 0x80 - 0xFF | This document |
+--------------------------+------------------+---------------+7.9. RIB Dictionary TLV Flags 🍓
The following TLV Flags are defined for the RIB Base Dictionary TLV (Section 4.3.3):
+----------------------------+--------------+---------------+
| Meaning | Bit Position | Reference |
+----------------------------+--------------+---------------+
| Sent by Listener | Flag 0 | This document |
| Reserved (do not allocate) | Flag 1 | This document |
| Reserved (do not allocate) | Flag 2 | This document |
| Unassigned | Flag 3 | |
| Unassigned | Flag 4 | |
| Unassigned | Flag 5 | |
| Unassigned | Flag 6 | |
| Unassigned | Flag 7 | |
+----------------------------+--------------+---------------+7.10. RIB TLV Flags 🫶
The following TLV Flags are defined for the RIB TLV (Section 4.3.4):
+----------------------------+--------------+---------------+
| Meaning | Bit Position | Reference |
+----------------------------+--------------+---------------+
| More RIB TLVs | Flag 0 | This document |
| Reserved (do not allocate) | Flag 1 | This document |
| Reserved (do not allocate) | Flag 2 | This document |
| Unassigned | Flag 3 | |
| Unassigned | Flag 4 | |
| Unassigned | Flag 5 | |
| Unassigned | Flag 6 | |
| Unassigned | Flag 7 | |
+----------------------------+--------------+---------------+7.11. RIB Flags ✨
okay so the RIB Flags are the little bit-flags that go on each entry inside the RIB TLV (Section 4.3.4) 🎀 right now every single bit, Flag 0 through Flag 7, is still unassigned 🦋 so there's a whole empty table just waiting for its main character moment 💅
+------------+--------------+-----------+
| Meaning | Bit Position | Reference |
+------------+--------------+-----------+
| Unassigned | Flag 0 | |
| Unassigned | Flag 1 | |
| Unassigned | Flag 2 | |
| Unassigned | Flag 3 | |
| Unassigned | Flag 4 | |
| Unassigned | Flag 5 | |
| Unassigned | Flag 6 | |
| Unassigned | Flag 7 | |
+------------+--------------+-----------+7.12. Bundle Offer and Response TLV Flags 🌸
okay this one is giving real plot 🔥 these are the TLV Flags for the Bundle Offer and Response TLV (Section 4.3.5). Flag 0 is More Offer/Response TLVs Following and it's defined right here in this document 💜 the other seven are still unassigned, so they're just sitting there looking cute 🧚
+------------------------------------+--------------+---------------+
| Meaning | Bit Position | Reference |
+------------------------------------+--------------+---------------+
| More Offer/Response TLVs Following | Flag 0 | This document |
| Unassigned | Flag 1 | |
| Unassigned | Flag 2 | |
| Unassigned | Flag 3 | |
| Unassigned | Flag 4 | |
| Unassigned | Flag 5 | |
| Unassigned | Flag 6 | |
| Unassigned | Flag 7 | |
+------------------------------------+--------------+---------------+7.13. Bundle Offer and Response B Flags 🍓
bestie, these are the B Flags. They get defined for each Bundle Offer inside the Bundle Offer and Response TLV (Section 4.3.5) 😭 Flag 0 is Bundle Accepted, Flag 1 is Bundle is a Fragment, and Flag 2 is Bundle Payload Length Included in TLV, all defined in this document ✨ Flag 7 is PRoPHET ACK (also this document) 👑 and Flags 3 through 6 are unassigned 🌈
+------------------------------------+--------------+---------------+
| Meaning | Bit Position | Reference |
+------------------------------------+--------------+---------------+
| Bundle Accepted | Flag 0 | This document |
| Bundle is a Fragment | Flag 1 | This document |
| Bundle Payload Length Included in | Flag 2 | This document |
| TLV | | |
| Unassigned | Flag 3 | |
| Unassigned | Flag 4 | |
| Unassigned | Flag 5 | |
| Unassigned | Flag 6 | |
| PRoPHET ACK | Flag 7 | This document |
+------------------------------------+--------------+---------------+8. Implementation Experience 🧚
okay the implementation stories are literally so iconic 🦋 there are multiple independent implementations of PRoPHET out there, bestie, which is the ultimate proof that the spec actually works 💅
The first one is written in Java and was optimized to run on the Lego MindStorms platform, which has very limited resources 🤖 because of that, some parts of the protocol were simplified or omitted, but the implementation still has all the important mechanisms needed for proper protocol operation 🫶 it's also highly modular, so it can run on another system with only minor modifications. It has been shown to run on the Lego MindStorms platform and on regular laptops 💻
Another implementation is written in C++ and runs in the OmNet++ simulator, so people can test and evaluate the protocol and new features 🔬 the implementers who worked with early versions gave feedback, and that feedback got folded into the current version 💖
An implementation compliant with an Internet-Draft (posted in 2006, which eventually evolved into this RFC) was written at Baylor University 🎓 and it has been integrated into the DTN2 reference implementation ✨
Then there's a C++ implementation developed by one of the authors, Samo Grasic, at Lulea University of Technology (LTU) as part of the Saami Networking Connectivity project (see Section 9) 🌍 it keeps tracking the development of the protocol, and it's now part of the Networking for Communications Challenged Communities (N4C) project and used in N4C testbeds 🌈
9. Deployment Experience 🏔️
so during a week in August 2006, there was a proof-of-concept deployment of a DTN system using the LTU PRoPHET implementation for routing 😭 it happened in the Swedish mountains, which was the target area for the Saami Network Connectivity project [ccnc07] [doria_02] 🏔️ they deployed four fixed camps with application gateways, one Internet gateway, and seven mobile relays 🎀
The deployment showed that PRoPHET could route bundles generated by different applications, like email and web caching 💌 which is honestly so slay 💅
Within the SNC and N4C projects, there were a bunch more deployments, in both summer and winter conditions, at various scales during 2007-2010 [winsdr08] ❄️☀️
There's also an Android implementation for mobile phones made in the Bytewalla project [bytewalla] 📱💜
10. Acknowledgements 🫶
the authors wanted to thank Olov Schelen and Kaustubh S. Phanse for their super valuable feedback on different parts of the protocol 💖 they also thanked all the other reviewers and the DTNRG chairs for helping develop it 🌸 The Hello TLV mechanism is loosely based on the Adjacency message from RFC 3292 ✨ and Luka Birsa and Jeff Wilson gave feedback from building implementations off earlier drafts 🍓 that feedback made the document easier for implementers to read and improved the protocol itself, so they're total legends 👑
11. References 📚
11.1. Normative References 🌟
- [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997.
- [RFC5050] Scott, K. and S. Burleigh, "Bundle Protocol Specification", RFC 5050, November 2007.
11.2. Informative References 🦋
- [CLAYER] Demmer, M., Ott, J., and S. Perreault, "Delay Tolerant Networking TCP Convergence Layer Protocol", Work in Progress, August 2012.
- [RFC1058] Hedrick, C., "Routing Information Protocol", RFC 1058, June 1988.
- [RFC4838] Cerf, V., Burleigh, S., Hooke, A., Torgerson, L., Durst, R., Scott, K., Fall, K., and H. Weiss, "Delay-Tolerant Networking Architecture", RFC 4838, April 2007.
- [RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an IANA Considerations Section in RFCs", BCP 26, RFC 5226, May 2008.
- [RFC6257] Symington, S., Farrell, S., Weiss, H., and P. Lovell, "Bundle Security Protocol Specification", RFC 6257, May 2011.
- [bytewalla] Prasad, M., "Bytewalla 3: Network architecture and PRoPHET implementation", Bytewalla Project, KTH Royal Institute of Technology, Stockholm, Sweden, October 2010,
http://www.bytewalla.org/sites/bytewalla.org/files/Bytewalla3_Network_architecture_and_PRoPHET_v1.0.pdf. - [ccnc07] Lindgren, A. and A. Doria, "Experiences from Deploying a Real-life DTN System", Proceedings of the 4th Annual IEEE Consumer Communications and Networking Conference (CCNC 2007), Las Vegas, Nevada, USA, January 2007.
- [doria_02] Doria, A., Uden, M., and D. Pandey, "Providing connectivity to the Saami nomadic community", Proceedings of the 2nd International Conference on Open Collaborative Design for Sustainable Innovation (dyd 02), Bangalore, India, December 2002.
- [lindgren_06] Lindgren, A. and K. Phanse, "Evaluation of Queueing Policies and Forwarding Strategies for Routing in Intermittently Connected Networks", Proceedings of COMSWARE 2006, January 2006.
- [vahdat_00] Vahdat, A. and D. Becker, "Epidemic Routing for Partially Connected Ad Hoc Networks", Duke University Technical Report CS-200006, April 2000.
- [winsdr08] Lindgren, A., Doria, A., Lindblom, J., and M. Ek, "Networking in the Land of Northern Lights - Two Years of Experiences from DTN System Deployments", Proceedings of the ACM Wireless Networks and Systems for Developing Regions Workshop (WiNS-DR), San Francisco, California, USA, September 2008.
Appendix A. PRoPHET Example ✨
okay so bestie, this appendix is the walkthrough that makes PRoPHET click 💖 It shows how the transitive property of delivery predictability works and how the basic operation goes. In Figure 13 we're back in the scenario where node A has a message for node D 📦 The delivery predictability tables sit in the bottom right corner of subfigures a-c 🍓
Picture this. Nodes C and D keep running into each other (Figure 13a), so their delivery predictability values for each other go high 🔥 Then node C also keeps meeting node B (Figure 13b). B and C end up with high values for each other, and the transitive property bumps B's value for D up to a medium level 🧚 Finally node B meets node A (Figure 13c), and A is holding a message for D 👀 Figure 13d shows the exchange between A and B. They swap summary vectors and delivery predictability info, the predictabilities get updated, and node A realises that P_(b,d) > P_(a,d). So A forwards the message for D to node B 🦋 iykyk, it's giving teamwork 🫶
+----------------------------+ +----------------------------+
| | | |
| C | | D |
| D | | |
| B | | B C |
| | | |
| | | |
| | | |
| | | |
| A* | | A* |
+-------------+--------------+ +-------------+--------------+
| A | B | C | D | | A | B | C | D |
|B:low |A:low |A:low |A:low | |B:low |A:low |A:low |A:low |
|C:low |C:low |B:low |B:low | |C:low |C:high|B:high |B:low |
|D:low |D:low |D:high |C:high| |D:low |D:med |D:high |C:high|
+-------------+--------------+ +-------------+--------------+
(a) (b)
+----------------------------+ A B
| | | |
| D | |Summary vector&delivery pred|
| | |--------------------------->|
| C | |Summary vector&delivery pred|
| | |<---------------------------|
| | | |
| B* | Update delivery predictabilities
| A | | |
| | Packet for D not in SV |
+-------------+--------------+ P(b,d)>P(a,d) |
| A | B | C | D | Thus, send |
|B:low |A:low |A:low |A:low | | |
|C:med |C:high|B:high |B:low | | Packet for D |
|D:low+|D:med |D:high |C:high| |--------------------------->|
+-------------+--------------+ | |
(c) (d)
Figure 13: PRoPHET exampleAppendix B. Neighbor Discovery Example 🎀
this one is a little neighbor-finding protocol 🏡 You can run it between PRoPHET and the layer below if the lower layers don't already do neighbor discovery for you. It assumes the layer below supports broadcast messages, which is what you'd get with a wireless infrastructure 📡
Every node needs to keep a list of its active neighbors 💜 Here's how it goes:
- Every
BEACON_INTERVALmilliseconds, the node does a local broadcast of a beacon. The beacon holds its identity and address, plus theBEACON_INTERVALvalue the node is using 📣 - When a beacon comes in, one of two things can happen 👀
- A. The sending node is already in the list of active neighbors. Update its entry with the current time, and update the node's
BEACON_INTERVALif it has changed ✨ - B. The sending node is not in the list yet. Add it to the list of active neighbors, record the current time and the node's
BEACON_INTERVAL, and tell the PRoPHET agent that a new neighbor showed up ("New Neighbor", as described in Section 2.4) 🥰
- A. The sending node is already in the list of active neighbors. Update its entry with the current time, and update the node's
- If no beacon has come from a node on the active list within a period of
NUM_ACCEPTED_LOSSES*BEACON_INTERVAL(using theBEACON_INTERVALthat node uses), it should be assumed that the node is no longer a neighbor 💀 Then its entry comes off the list, and the PRoPHET agent gets told that a neighbor has left ("Neighbor Gone", as described in Section 2.4) 👋
Appendix C. PRoPHET Parameter Calculation Example 🧮
okay this is the math-brain appendix and I'm obsessed 🤓 The way delivery predictabilities evolve in a PRoPHET node is controlled by three main equations, defined in Section 2.1.2. Those equations use a bunch of parameters, and they need to be set properly so the predictabilities mirror the mobility model of the PRoPHET zone the node is working in 🌈
Here's the thing: a mobility model is more likely to be described in terms of statistical distributions, like the times between encounters and the times to deliver a bundle in the zone 📊 This section shows one possible way to get the PRoPHET parameters from that more usual description. Just remember it might not be the only solution, and how well it fits depends on the overall mobility model and on the distribution of the times involved 🫠 There's an implicit assumption here that these distributions can be characterised by a normal-type distribution with a well-defined first moment (mean). The exact form of the distribution isn't considered here, but more detailed models might want to use more specific knowledge about the distributions to refine how the parameters are derived 🧠
To characterise the model, we look at these parameters:
P1: The time resolution of the model.P2: The average time between encounters between nodes,I_typ, where the identity of the nodes is not taken into account.P3: The average number of encounters that a node has between meeting a particular node and meeting the same node again.P4: The average number of encounters needed to deliver a bundle in this zone.P5: The multiple of the average number of encounters needed to deliver a bundle (P4) after which it can be assumed that a node is not going to encounter a particular node again in the foreseeable future, so the delivery predictability ought to be decayed belowP_first_threshold.P6: The number of encounters between a particular pair of nodes that should result in the delivery predictability of the encountered node getting close to the maximum possible delivery predictability (1 - delta).
We can use these parameters to work out good values for gamma and P_encounter_max. Those are the key parameters in how the delivery predictabilities evolve 💅 The other parameters, P_encounter_first (0.5), P_first_threshold (0.1), and delta (0.01), come with the default values suggested in Figure 3. They generally aren't specific to the mobility model, although in special cases P_encounter_first might be different if extra information is available ✨
Selecting a value for gamma 🌸
After a single, unrepeated encounter, the delivery predictability of the encountered node should decay from P_encounter_first to P_first_threshold in the expected time for P4 * P5 encounters. So:
P_first_threshold = P_encounter_first * gamma ^ ((P2 * P4 * P5)/P1)which can be rearranged as:
gamma =
exp(ln(P_first_threshold/P_encounter_first) * P1 / (P2* P4 * P5)).Typical values of gamma will be less than 1, but very close to 1 (usually greater than 0.99) 🥹 The value has to be stored to several decimal places of accuracy. Implementations can make a table of values for specific intervals, though, which cuts down on the on-the-fly calculation needed 🙌
Selecting a value for P_encounter_max 💖
Once gamma is determined, the decay factor for the average time between encounters between a specific pair of nodes can be calculated:
Decay_typ = gamma ^ ((P2 * P3)/P1)Starting with P_encounter_first, use Decay_typ and apply Equation 1 from Section 2.1.2 (P6 - 1) times. That gives you the typical delivery predictability for the encountered node after P6 encounters 🧁 Equation 1 isn't easy to turn into a closed form that spits out P_encounter_max from the parameter values. But using a spreadsheet to apply the equation over and over and tabulate the results makes it super simple to pick a suitable P_encounter_max 📊 The evolution isn't very sensitive to P_encounter_max, and values in the range 0.4 to 0.8 will generally be appropriate. A value of 0.7 is recommended as a default 🫶
Once a PRoPHET zone has been running for a while, the logs of actual encounters can and should be used to check that the selected parameters were appropriate and to tune them as needed 🔍 In the longer term, it may be possible to install a learning mode in nodes, so the parameters can be adjusted dynamically to keep the best congruence with a mobility model that may itself change over time 🤖🦋
Authors' Addresses 🌷
Anders F. Lindgren
Swedish Institute of Computer Science
Box 1263
Kista SE-164 29
SE
Phone: +46707177269
EMail: andersl@sics.se
URI: http://www.sics.se/~andersl
Avri Doria
Technicalities
Providence RI
US
EMail: avri@acm.org
URI: http://psg.com/~avri
Elwyn Davies
Folly Consulting
Soham
UK
EMail: elwynd@folly.org.uk
Samo Grasic
Lulea University of Technology
Lulea SE-971 87
SE
EMail: samo.grasic@ltu.seThat's the whole RFC, bestie 🌈✨ we made it 👑
📦 where this page comes from
- ietf: rfc6693 2012-08
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms