Project

General

Profile

NDNLPv2 » History » Version 45

Davide Pesavento, 05/09/2019 08:01 PM

1 1 Junxiao Shi
# NDNLPv2
2 2 Alex Afanasyev
3 45 Davide Pesavento
{{>toc}}
4
5 16 Junxiao Shi
NDNLPv2 is a link protocol for [Named Data Networking](https://named-data.net/).
6 2 Alex Afanasyev
7
## Goals
8
9
NDNLPv2 provides the following **features**:
10
11
* fragmentation and reassembly: fragment a network layer packet to fit in link MTU
12
* failure detection: rapidly detect link failure and recovery
13
* reliability: reduce packet loss
14
* integrity: prevent packet injection
15
* forwarding instruction: NACK, nexthop choice, cache control, etc
16
* packet information: for management and monitoring
17
18
NDNLPv2 is designed to be a **unified protocol** that can be used on all kinds of links, including but not limited to: UNIX sockets, Ethernet unicast/multicast, UDP unicast/multicast, TCP connections, WebSockets, etc.
19
20
NDNLPv2 protocol operates as a **link adaptation layer**; it is above link layer and below network layer.
21
Please, do not call this "layer 2.5": there is no such notion in RFC protocols.
22
23
Different links need different features, or different designs of a feature.
24 1 Junxiao Shi
NDNLPv2 ensures **all features are optional** and can be turned on or off per-link.
25 2 Alex Afanasyev
NDNLPv2 also allows different designs of a feature to be adopted per-link.
26
27 16 Junxiao Shi
NDNLPv2 deprecates and replaces: [original NDNLP (aka NDNLPv1)](https://named-data.net/publications/techreports/trlinkprotocol/), [NDNLPv1 multicast extension](https://github.com/NDN-Routing/NDNFD/blob/master/docs/NDNLP.md), [NDNLPv1-TLV](https://redmine.named-data.net/projects/nfd/wiki/NDNLP-TLV/7), [NDNLP-BFD](https://redmine.named-data.net/attachments/download/231/NDNLP-BFDSummaryReport.pdf), [NFD LocalControlHeader](https://redmine.named-data.net/projects/nfd/wiki/LocalControlHeader/25).
28 2 Alex Afanasyev
29
## NDNLP Packet Format
30
31 16 Junxiao Shi
NDNLPv2 packet adopts a Type-Length-Value (TLV) structure similar to [NDN Packet Format](https://named-data.net/doc/ndn-tlv/tlv.html).
32 2 Alex Afanasyev
33 1 Junxiao Shi
    LpPacket ::= LP-PACKET-TYPE TLV-LENGTH
34 2 Alex Afanasyev
                   LpHeaderField*
35
                   Fragment?
36
37 17 Davide Pesavento
    LpHeaderField ::= .. | Sequence
38
39
    Sequence ::= SEQUENCE-TYPE TLV-LENGTH
40
                   fixed-width unsigned integer
41
42
    Fragment ::= FRAGMENT-TYPE TLV-LENGTH
43
                   byte+
44
45 2 Alex Afanasyev
Outermost packet transmitted on a NDNLPv2 link is LpPacket.
46 16 Junxiao Shi
In addition, a host MUST also accept bare network packets (Interest and Data) on a NDNLPv2 link, which SHOULD be interpreted as an LpPacket with the bare network packet as its Fragment. However, such packets could be dropped later in processing if the link configured to require a certain NDNLPv2 feature but a field is missing.
47 2 Alex Afanasyev
48
**LpHeaderField** is a repeatable optional structure in LpHeader.
49
NDNLPv2 features MAY add new header fields by extending the definition of LpHeaderField.
50
Unless otherwise specified, the same field shall appear at most once.
51
Unless otherwise specified, fields MUST appear in the order of increasing TLV-TYPE codes.
52
53
If an incoming LpPacket contains an unknown LpHeaderField, the following rules apply:
54
55 27 Davide Pesavento
1. if the unknown field is in the range `[800, 959]` and the two least significant bits are both zero, the receiver SHOULD ignore the field and continue processing the packet;
56 2 Alex Afanasyev
2. otherwise, the receiver MUST drop the packet, but SHOULD NOT consider the link has an error.
57
58 27 Davide Pesavento
Note: if a field is recognized but the relevant feature is disabled, it's not considered "unknown".
59 2 Alex Afanasyev
60
**Sequence** contains a sequence number that is useful in multiple features.
61
This field is REQUIRED if any enabled feature is using sequence numbers, otherwise it's OPTIONAL.
62
Bit width of the sequence is determined on a per-link basis; 8-octet is recommended for today's links.
63
A host MUST generate consecutive sequence numbers for outgoing packets on the same face.
64
65
**Fragment** contains a fragment of one or more network layer packets.
66 1 Junxiao Shi
The fragmentation and reassembly feature defines how Fragment field is constructed and interpreted.
67 2 Alex Afanasyev
When fragmentation and reassembly feature is disabled, the Fragment field contains a whole network layer packet.
68 14 Davide Pesavento
Fragment is OPTIONAL; an LpPacket without Fragment is an **IDLE packet**.
69 1 Junxiao Shi
70 2 Alex Afanasyev
## Indexed Fragmentation
71
72 14 Davide Pesavento
Indexed fragmentation provides fragmentation and reassembly feature on datagram links that do not guarantee in-order delivery.
73 2 Alex Afanasyev
74
This feature defines two header fields:
75
76
    LpHeaderField ::= .. | FragIndex | FragCount
77
78
    FragIndex ::= FRAG-INDEX-TYPE TLV-LENGTH
79
                    nonNegativeInteger
80 1 Junxiao Shi
81
    FragCount ::= FRAG-COUNT-TYPE TLV-LENGTH
82 2 Alex Afanasyev
                    nonNegativeInteger
83
84 14 Davide Pesavento
The sender slices a network layer packet into one or more fragments.
85
The size of each fragment MUST be small enough so that the LpPacket carrying every fragment is below the link MTU.
86 2 Alex Afanasyev
It is RECOMMENDED that all except the last fragments have the same size.
87
88
**FragCount** field indicates the number of fragments belonging to the same network layer packet.
89
It MUST be the same in all fragments belonging to the same network layer packet.
90
91
**FragIndex** field indicates the zero-based index of the current packet.
92
It MUST be assigned consecutively for fragments belonging to the same network layer packet, starting from zero.
93
The feature is named "indexed fragmentation" because every fragment is given an index in this field.
94
95
**Sequence** field is REQUIRED when this feature is enabled.
96
Fragments belonging to the same network layer packet MUST be assigned consecutive sequence numbers, in the same order with FragIndex.
97
98
For example, a 5000-octet network layer packet may be sliced as illustrated:
99
100
    +-------------+-------------+    +-------------+-------------+
101
    | LpPacket    | Fragment    |    | LpPacket    | Fragment    |
102
    | seq=8801    |             |    | seq=8802    |             |
103
    | FragIndex=0 | [0:1400]    |    | FragIndex=1 | [1400:2800] |
104
    | FragCount=4 |             |    | FragCount=4 |             |
105
    +-------------+-------------+    +-------------+-------------+
106
107
    +-------------+-------------+    +-------------+-------------+
108 1 Junxiao Shi
    | LpPacket    | Fragment    |    | LpPacket    | Fragment    |
109 2 Alex Afanasyev
    | seq=8803    |             |    | seq=8804    |             |
110
    | FragIndex=2 | [2800:4200] |    | FragIndex=3 | [4200:5000] |
111
    | FragCount=4 |             |    | FragCount=4 |             |
112
    +-------------+-------------+    +-------------+-------------+
113 1 Junxiao Shi
114 14 Davide Pesavento
The receiver stores fragments in a *PartialMessageStore* data structure, which is a collection of PartialMessages, indexed by MessageIdentifier=Sequence-FragIndex.
115 1 Junxiao Shi
Since both Sequence and FragIndex are assigned consecutively, MessageIdentifier would be the sequence number of the first fragment of a network layer packet.
116 14 Davide Pesavento
After collecting all fragments belonging to a network layer packet, the receiver stitches them together, and delivers the complete network layer packet to the upper layer.
117 2 Alex Afanasyev
118 14 Davide Pesavento
The receiver SHOULD maintain a reassembly timer for each PartialMessage, which is reset each time a new fragment is received.
119 2 Alex Afanasyev
If this timer expires, the PartialMessage is dropped.
120 14 Davide Pesavento
The default duration of this timer is 500ms.
121 2 Alex Afanasyev
122 14 Davide Pesavento
If this feature is enabled but FragIndex is missing, it is assumed to be 0 (zero).
123
If this feature is enabled but FragCount is missing, it is assumed to be 1 (one).
124 2 Alex Afanasyev
If this feature is disabled but either header field is received, the packet MUST be dropped.
125
126 14 Davide Pesavento
Unless otherwise specified, header fields from other features MUST appear only in the first fragment.
127
If a header field appears on a subsequent fragment, it MUST be ignored, unless otherwise specified.
128 2 Alex Afanasyev
129
## Network NACK
130
131
A network NACK is a forwarding instruction from upstream to downstream that indicates the upstream is unable to satisfy an Interest.
132
133
This feature defines a header field:
134
135
    LpHeaderField ::= .. | Nack
136
137
    Nack ::= NACK-TYPE TLV-LENGTH
138
               NackReason?
139
140
    NackReason ::= NACK-REASON-TYPE TLV-LENGTH
141
                     nonNegativeInteger
142
143
**Nack** header field indicates an Interest is a NACK, and is not a normal Interest.
144
The receiver MUST NOT process the packet as an Interest.
145
146
**NackReason** element MAY be included to indicate why the NACK is transmitted.  
147
The following NackReason values are defined:
148
149
Code  | Reason       | Description
150
----- | ------------ | --------------------------------------------------------------
151
0     | None         | (reserved)
152
50    | Congestion   | there is a congestion in the link between upstream and downstream, or on the best-known path between upstream and content source
153
100   | Duplicate    | the upstream has detected a duplicate Nonce in the Interest sent by the downstream
154
150   | NoRoute      | the upstream has no path to reach a content source due to routing problem or link failure
155
156
A receiver MUST be prepared to process a NACK without a reason.  
157
If NackReason element contains an unrecognized reason, the receiver MUST treat this NACK as a NACK without reason, and MUST NOT drop the packet.
158
159
Example of NACK of an Interest for `/example` with NACK reason "Duplicate":
160
161
    +--------------------------+---------------+
162
    | LpPacket                 | Interest      |
163
    |                          | Name=/example |
164
    | +-Nack-----------------+ | Nonce=35      |
165
    | | NackReason=Duplicate | |               |
166
    | +----------------------+ |               |
167
    +--------------------------+---------------+
168
169
It's RECOMMENDED to enable this feature on every link.  
170
If this feature is disabled but Nack is received, the packet MUST be dropped.
171
172
Nack header field is permitted only on an LpPacket carrying an Interest.  
173
When Nack appears on an LpPacket carrying a network layer packet other than an Interest, the packet MUST be dropped.
174
175 13 Davide Pesavento
## Consumer-Controlled Forwarding
176 2 Alex Afanasyev
177 13 Davide Pesavento
Consumer-controlled forwarding allows a local consumer application to explicitly specify the nexthop face to forward an Interest.
178 2 Alex Afanasyev
179
This feature defines a header field:
180
181
    LpHeaderField ::= .. | NextHopFaceId
182
183
    NextHopFaceId ::= NEXT-HOP-FACE-ID-TYPE TLV-LENGTH
184
                        nonNegativeInteger
185
186
**NextHopFaceId** indicates the nexthop FaceId to which an Interest should be forwarded.
187
A local consumer application MAY add this field to an LpPacket carrying an Interest.
188
The local forwarder SHOULD follow this instruction and forward the Interest to the specified nexthop, after ContentStore lookup does not find a match.
189
190
This feature is designed to be used on local faces only.
191 1 Junxiao Shi
It SHOULD NOT be enabled on non-local faces.
192 2 Alex Afanasyev
If this feature is enabled but NextHopFaceId refers to a non-existent face, the Interest SHOULD be processed as if there is no available route.
193
If this feature is disabled but NextHopFaceId is received, the packet SHOULD be dropped, or this field MUST be ignored.
194
195
NextHopFaceId header field is permitted only on an LpPacket carrying an Interest, from an application to the forwarder.
196
When NextHopFaceId appears on an LpPacket carrying a network layer packet other than an Interest, the packet MUST be dropped.
197 16 Junxiao Shi
When NextHopFaceId appears on an LpPacket that has a Nack header field, the packet SHOULD be dropped.
198 2 Alex Afanasyev
When NextHopFaceId is received by an application from a forwarder, this field MUST be ignored.
199
200
## Local Cache Policy
201
202
Local cache policy feature allows a local producer application to instruct ContentStore on whether and how to cache a Data packet.
203
204
This feature defines a header field:
205
206
    LpHeaderField ::= .. | CachePolicy
207
208
    CachePolicy ::= CACHE-POLICY-TYPE TLV-LENGTH
209
                      CachePolicyType
210
211
    CachePolicyType ::= CACHE-POLICY-TYPE-TYPE TLV-LENGTH
212
                          nonNegativeInteger
213
214
**CachePolicy** header field gives a suggestion to the ContentStore.
215
The ContentStore MAY follow this suggestion.
216
217
**CachePolicyType** element MUST be included to indicate the suggestion.
218
The following CachePolicyType values are defined:
219
220
Code | Policy  | Description
221
-----|---------|--------------------------------
222
0    | None    | (reserved)
223
1    | NoCache | ContentStore SHOULD NOT admit the Data packet
224
225
If CachePolicyType field contains an unknown policy code, the forwarder SHOULD drop the packet.
226
227
The design places the policy code in the CachePolicyType element nested under CachePolicy, instead of having the code appear directly in CachePolicy header field, because in the future other policies that require additional arguments can be defined, and those arguments can appear as elements after CachePolicyType.
228
229
Example for a Data packet with "NoCache" policy:
230
231
    +-----------------------------+---------------+
232
    | LpPacket                    | Data          |
233
    |                             | Name=/example |
234
    | +-CachePolicy-------------+ | Content=xxxx  |
235
    | | CachePolicyType=NoCache | | Signature=xx  |
236
    | +-------------------------+ |               |
237
    +-----------------------------+---------------+
238
239
This feature is designed to be used on local faces only.
240
It SHOULD NOT be enabled on non-local faces.
241
If this feature is disabled but CachePolicy is received, this field MUST be ignored.
242
243
CachePolicy header field is permitted only on an LpPacket carrying a Data packet, from an application to the forwarder.
244
When CachePolicy header field appears on an LpPacket carrying a network layer packet other than a Data packet, the packet MUST be dropped.
245
When CachePolicy is received by an application from a forwarder, this field MUST be ignored.
246
247
## Incoming Face Indication
248
249
Incoming face indication feature allows the forwarder to inform local applications about the face on which a packet is received.
250
251
This feature defines a header field:
252
253
    LpHeaderField ::= .. | IncomingFaceId
254
255
    IncomingFaceId ::= INCOMING-FACE-ID-TYPE TLV-LENGTH
256
                         nonNegativeInteger
257
258
**IncomingFaceId** contains the FaceId from which the network layer packet is received.
259
When this feature is enabled, the forwarder SHOULD attach this field to every network layer packet going to a local application, and indicate the FaceId on which this network layer packet is received by the forwarder.
260
If a Data packet comes from the ContentStore, IncomingFaceId SHOULD contain a special FaceId that represents the ContentStore, rather than the FaceId on which this Data packet was originally received.
261
Even if this feature is enabled, the application MUST be prepared to receive a packet without IncomingFaceId field.
262
263
This feature is designed to be used on local faces only.
264
It SHOULD NOT be enabled on non-local faces.
265
266
IncomingFaceId header field is permitted only on an LpPacket from the forwarder to an application.
267 1 Junxiao Shi
When IncomingFaceId is received by the forwarder from an application, this field MUST be ignored.
268
269 45 Davide Pesavento
## Congestion Marking
270 5 Eric Newberry
271 7 Anonymous
A host can signal the current congestion state to other hosts using the **CongestionMark** field. A value of 0 indicates *no congestion*; a value greater than 0 indicates some level of congestion. The exact meaning of the bits in this field is left up to the congestion control strategy in use.
272 5 Eric Newberry
273
This features defines a header field:
274 1 Junxiao Shi
275 5 Eric Newberry
    LpHeaderField ::= .. | CongestionMark
276
277 1 Junxiao Shi
    CongestionMark ::= CONGESTION-MARK-TYPE TLV-LENGTH
278 5 Eric Newberry
                         nonNegativeInteger
279
280 9 Eric Newberry
## Link Layer Reliability
281
282 10 Eric Newberry
To provide increased reliability and indicate potential congestion on a unicast link, a sender can expect frames successfully received by another host to be acknowledged.
283 9 Eric Newberry
284 11 Eric Newberry
After sending a link-layer frame (potentially fragmented, as described above), a host will expect an Ack field to be received on a frame returned in the opposite direction. This field will contain the TxSequence of the acknowledged frame. TxSequence numbers are assigned sequentially on the link, and are independent of the sequence number of the stored fragment. If the host does not receive this acknowledgement within the RTO (determined using the formula described below) and the frame has not been retransmitted more than a pre-determined number of times (the maximum number of retransmissions), the frame will be retransmitted on the link with the same sequence number, but a new TxSequence. In addition, if a configurable number of Acks (three by default) for greater TxSequences are received by the sender of the frame, the frame will be considered lost and the previously discussed retransmission logic will be followed.
285 9 Eric Newberry
286 14 Davide Pesavento
To facilitate the retransmission of frames, each frame will be cached on the sender until it is acknowledged, at which point it can be deleted from the cache. The sender also keeps track of which frames were fragmented from which network-layer packet (if fragmentation occurred) and which unacknowledged TxSequences reference which transmitted frame. If one fragment of a network-layer packet exceeds the maximum number of retransmissions, the RTO timers of all fragments in the packet will be cancelled, all fragments of the packet will be deleted from the frame cache, and the entire packet will be considered lost. The sender will keep track of which sequence numbers are associated with which network-layer packets.
287 9 Eric Newberry
288 15 Eric Newberry
The receiver will extract the TxSequence of every received frame and will insert these numbers into a queue of pending Acks destined for the sender. When a frame is being transmitted in the opposite direction, any excess space under the MTU will be filled with TxSequences removed from this queue. An idle Ack timer is used to handle links that have gone idle. If a packet with a TxSequence is received and the packet has not been started, or has expired, the timer is started with a period of 5ms (or another configurable non-zero time period). Upon expiration of the timer, all Acks in the queue will be sent in IDLE packets.
289 9 Eric Newberry
290 14 Davide Pesavento
The RTO is determined using the standard TCP formula: `RTO = SRTT + 4 * RTTVAR`. The round-trip time (RTT) of a packet is measured as the difference between the time the frame was transmitted and when an Ack was received for it. Frames that have been retransmitted are not taken into account by this formula.
291 9 Eric Newberry
292 11 Eric Newberry
Multiple Ack fields can be sent in one LpPacket. If an Ack is received for an unknown TxSequence, the Ack will be ignored.
293 9 Eric Newberry
294 12 Eric Newberry
    LpHeaderField ::= .. | TxSequence | Ack
295
296
    TxSequence ::= TX-SEQUENCE-TYPE TLV-LENGTH
297
                     fixed-width unsigned integer
298 1 Junxiao Shi
299
    Ack ::= ACK-TYPE TLV-LENGTH
300 9 Eric Newberry
              fixed-width unsigned integer
301 1 Junxiao Shi
302
**Modified from "Hop-By-Hop Best Effort Link Layer Reliability in Named Data Networking" by S. Vusirikala, et al.**
303 9 Eric Newberry
304 45 Davide Pesavento
## Self-Learning Forwarding Support
305 1 Junxiao Shi
306 23 Junxiao Shi
[NDN self-learning](https://named-data.net/publications/on_broadcast-based_self-learning_ndn/) is a forwarding protocol that can automatically discover contents and forwarding paths in local area networks. This feature adds two hop-by-hop headers to support this forwarding protocol.
307 1 Junxiao Shi
308 23 Junxiao Shi
    LpHeaderField ::= .. | NonDiscovery | PrefixAnnouncement
309
310
    NonDiscovery ::= NON-DISCOVERY-TYPE TLV-LENGTH(=0)
311 1 Junxiao Shi
                       // no value
312
313 23 Junxiao Shi
    PrefixAnnouncement ::= PREFIX-ANNOUNCEMENT-TYPE TLV-LENGTH
314 34 Davide Pesavento
                             Data
315 28 Teng Liang
316 23 Junxiao Shi
Self-learning distinguishes an Interest as either "discovery" or "non-discovery". A node transmits a discovery Interest to explore new forwarding paths, or transmits a non-discovery Interest to exploit existing forwarding paths. The **NonDiscovery** field indicates an Interest is "non-discovery"; otherwise, an Interest without this field is "discovery".
317
This field can only appear on an Interest. If this field appears on a Data or a Nack, the LpPacket MUST be dropped. If the self-learning forwarding protocol support feature is disabled or the chosen forwarding strategy does not support self-learning, this field SHOULD be ignored.
318
319 43 Teng Liang
When replying to a discovery Interest, the upstream node SHOULD transmit the Data with a **PrefixAnnouncementHeader** field. This field indicates what name prefix the producer is serving, and assists the downstream node in updating its FIB. A PrefixAnnouncement contains a single Data TLV element, and the Data format follows the [[PrefixAnnouncement]] Protocol.
320 42 Davide Pesavento
321 43 Teng Liang
 
322 41 Teng Liang
This field can only appear on a Data. If this field appears on an Interest or a Nack, the LpPacket MUST be dropped. If the self-learning forwarding protocol support feature is disabled or the chosen forwarding strategy does not support self-learning, this field SHOULD be ignored.
323 22 Teng Liang
324 16 Junxiao Shi
## TLV-TYPE Number Assignments
325 2 Alex Afanasyev
326 26 Davide Pesavento
type                     | number (dec)     | number (hex)
327
-------------------------|------------------|------------------
328 25 Junxiao Shi
Fragment                 | 80               | 0x50
329
Sequence                 | 81               | 0x51
330 1 Junxiao Shi
FragIndex                | 82               | 0x52
331
FragCount                | 83               | 0x53
332 25 Junxiao Shi
HopCount (ndnSIM)        | 84               | 0x54
333 26 Davide Pesavento
PitToken (NIST, #4432)   | 98               | 0x62
334
LpPacket                 | 100              | 0x64
335 25 Junxiao Shi
Nack                     | 800              | 0x0320
336
NackReason               | 801              | 0x0321
337
NextHopFaceId            | 816              | 0x0330
338
IncomingFaceId           | 817              | 0x0331
339
CachePolicy              | 820              | 0x0334
340
CachePolicyType          | 821              | 0x0335
341
CongestionMark           | 832              | 0x0340
342
Ack                      | 836              | 0x0344
343
TxSequence               | 840              | 0x0348
344 20 Davide Pesavento
NonDiscovery             | 844              | 0x034C
345 2 Alex Afanasyev
PrefixAnnouncement       | 848              | 0x0350
346 1 Junxiao Shi
347 2 Alex Afanasyev
### Reserved Blocks
348
349 45 Davide Pesavento
Two blocks of TLV-TYPEs have been reserved by link protocols:
350 2 Alex Afanasyev
351 27 Davide Pesavento
* `[80, 100]`: 1-octet encoding
352
* `[800, 1000]`: 3-octet encoding
353 2 Alex Afanasyev
354 16 Junxiao Shi
TLV-TYPE numbers for LpHeaderField SHOULD be assigned according to the following rules:
355 2 Alex Afanasyev
356 27 Davide Pesavento
1. if the field can be safely ignored by a receiver that doesn't understand the field, pick an unused number in the range `[800, 959]` whose two least significant bits are `00`.
357
2. if the field would occur frequently, pick an unused number in the range `[81, 99]`.
358
3. otherwise, pick an unused number in the range `[800, 959]` whose two least significant bits are `01`.
359 2 Alex Afanasyev
360 16 Junxiao Shi
Note: number assignment for a TLV-TYPE nested within a LpHeaderField is not restricted by the above rules.