Subject: [icnrg] Question on the NIST NDN forwarder

From: "David R. Oran" <[email-masked]>
Date: Wed, 22 Apr 2020 10:29:35 -0400

This may be a misunderstanding, or an NDN architecture question rather 
than a forwarder question. My knowledge of the current state of the NDN 
architecture is somewhat weak, so please excuse the noise if this is 
flat out wrong.

It relates to the CS prefix matching shown on slide 9.

I thought that NDN semantics said that an Interest with prefix match 
would match the CS entry with the longest prefix match, independent of 
how many name components the CS name entry had, or how many name 
components were expressed in the Interest. Your example shows just a 
single level of prefix indirection in the CS (which is of course fine 
for an example to illustrate the design).

But…

What if I have a named object of, for example, /a/b/c/d/e.
In order to match any interest asking for prefix match, e.g. /a/, would 
I not have to create indirect entries for /a/, /a/b/, and /a/b/c/ as 
well as the indirect entry for /a/b/c/d/ ?

If true, this seems a really sub-optimal situation for objects with long 
multi-component names, as the number of CS entries and consequent writes 
would multiply rapidly. A secondary effect might also require both a 
“real” CS entry and an indirect CS entry if an application actually 
has an object, like /a/b/c as well as one named /a/b/c/d/e.

Did something change in the NDN architecture to explicitly restrict the 
number of up-levels that are allowed in prefix matching?

Thanks for enlightening me!!

DaveO

---

From: Junxiao Shi <[email-masked]>
Date: Wed, 22 Apr 2020 10:59:16 -0400

Hi Dave

No. In the expected case, the consumers should be using a consistent name
prefix to perform name discovery. The CS only needs 1 indirect entry in
this case. Occasionally, a small number of different consumer applications
could be using several name prefixes to perform name discovery of the same
Data packet, and the CS supports up to 4 indirect entries per direct entry.

More information on
https://github.com/usnistgov/ndn-dpdk/tree/master/container/cs , copied
below:

In addition to exact match lookups, CS supports a limited form of non-exact
match lookups: a cached Data can be found when the new Interest name is
same as the previous Interest name that retrieved the Data. This allows CS
matching with a prefix name, under the assumption that a consumer
application would use a consistent prefix to perform name discovery. It
also allows matching with a full name including implicit digest.

When an incoming Data satisfies an Interest with a prefix name or a full
name, the CS inserts two entries: a direct entry with the Data name as its
key, contains the Data, and can match future Interests with the same name
as the Data; an indirect entry with the Interest name as its key, points to
the direct entry, and can match future Interests with the same name as the
previous Interest.

A direct entry keeps track of dependent indirect entries. When CS evicts or
erases a direct entry, dependent indirect entries are erased automatically.
Each direct entry can track up to four indirect entries; no more indirect
entries could be inserted after this limit is reached.

Yours, Junxiao

On Wed, Apr 22, 2020 at 10:29 AM David R. Oran <[email-masked]> wrote:

> External Email

---

From: "David R. Oran" <[email-masked]>
Date: Wed, 22 Apr 2020 11:10:49 -0400

Thanks! This helps a lot. I’m somewhat surprised to see this a bit 
buried in a forwarder API description - is there something in an 
architecture document that explains to applications what the allowable 
semantics are?

One quick followup, since I’m clearly missing something in the 
explanation it says: “When an incoming Data satisfies an Interest with 
a prefix name or a full name…”. I don’t understand how you can 
tell whether the PIT for an interest with a prefix name is satisfied by 
that data without either already having the indirect entry somewhere, or 
doing a full LNPM into the PIT or CS to discover the Data object 
matches. Cluebat please?

Also - we can take this offline if others aren’t interest in this 
narrow question…

DaveO.

> name, the CS inserts two entries

DaveO

---

From: Junxiao Shi <[email-masked]>
Date: Wed, 22 Apr 2020 11:38:42 -0400

Hi Dave

Thanks! This helps a lot. I’m somewhat surprised to see this a bit buried
> in a forwarder API description - is there something in an architecture
> document that explains to applications what the allowable semantics are?
>
The NDN forwarding behavior in Chapter 2 and 3 of NDN in Local Area Networks
<https://hdl.handle.net/10150/625652> says the following for the Content
Store:

When an Interest arrives, the node queries the CS to see if there is a
cached Data that can satisfy the Interest. Given an Interest, the CS is
expected to return a Data that satisfy the Interest, i.e. the Data name
must start with the Interest name, and the Data must not violate any
selectors in the Interest. If the CS finds a Data that satisfies
the Interest, the Data is returned to the downstream, and the Interest is
not forwarded further. This saves upstream bandwidth, and shortens data
retrieval delay.

Note: this was written in 2017 so some terminology is outdated. "selectors"
has been replaced by "CanBePrefix and MustBeFresh".

While the CS is "expected" to return a Data that satisfies the Interest, it
is not required to do so.
The network as a whole would still be functional even if the CS on some or
all nodes are reporting MISS when the Data actually exists.

One quick followup, since I’m clearly missing something in the explanation
> it says: “When an incoming Data satisfies an Interest with a prefix name or
> a full name…”. I don’t understand how you can tell whether the PIT for an
> interest with a prefix name is satisfied by that data without either
> already having the indirect entry somewhere, or doing a full LNPM into the
> PIT or CS to discover the Data object matches. Cluebat please?
>
NDN-DPDK inserts a PIT token on the hop-by-hop header of every outgoing
Interest. The upstream node MUST put the same PIT token when they send back
Data/Nack in reply to the Interest. The PIT token not only indicates which
forwarding thread processed the Interest, but also contains an index of the
PIT entry.
For an incoming Data, the forwarder knows exactly which PIT entry is being
satisfied. It does not need to perform any name matching in the PIT.

NDN-DPDK design is influenced by Network Algorithmics
<https://books.google.com/books/about/Network_Algorithmics.html?id=fnZ9WWpVK7oC>.
Chapter 3.3 gives some implementation principles. The relevant ones are:

P3 relax system requirements - P3c shift computation in time

The CS cannot find cached Data if an Interest is using a prefix name that
has not been used before. This improves forwarding speed, at the cost of
shifting the computation of such name discovery to the producer node or an
edge forwarder (note that NDN-DPDK is not an edge forwarder).

P7 avoid unnecessary generality

Although consumers may use any prefix name to perform name discovery, this
is a rarely used feature. A well-designed application would use a
consistent prefix name to perform name discovery.

P10 pass hints in protocol headers

PIT token is passed in the hop-by-hop header, so that PIT lookup can be
greatly simplified.

P11 optimize the expected case

The expected case is that the application is using a consistent prefix name
to perform name discovery. The network as a whole optimizes for this
expected case.

Yours, Junxiao

---

From: "David R. Oran" <[email-masked]>
Date: Wed, 22 Apr 2020 11:44:14 -0400

Ah, that clears things up. Many thanks.

I assume the L2 (or whatever tunneling protocol used) is 
cryptographically protected or of course all hell can break loose by 
believing crafted hop-by-hop PIT tokens.

On 22 Apr 2020, at 11:38, Junxiao Shi wrote:

> buried
> explanation

DaveO

---

From: Junxiao Shi <[email-masked]>
Date: Wed, 22 Apr 2020 12:00:48 -0400

Hi Dave

> I assume the L2 (or whatever tunneling protocol used) is cryptographically
> protected or of course all hell can break loose by believing crafted
> hop-by-hop PIT tokens.
>
No, L2 is not cryptographically protected.
NDN-DPDK runs over native Ethernet and only supports point-to-point
connections. Each connection is a direct attach cable or a pair of fiber.
If someone runs NDN-DPDK using a tunneling protocol, it's their
responsibility to setup site-to-site VPN with encryption.

NDN-DPDK has protection against "outdated" PIT tokens.
First, PIT entry index portion of the PIT token is not a memory address,
but a 48-bit index number assigned by the PIT-CS Composite Table (PCCT).
PCCT maintains in a hash table of token to entry mappings. If the upstream
sends back a packet with an old PIT token (i.e. PIT entry removed), chances
are, the PIT token would not be found in the hash table.
Second, even if a PIT entry is found by the PIT token, the forwarder MUST
still verify that the Data satisfies the Interest, through name comparison.
The forwarder cannot blindly trust the PIT token without verifying the name.

PIT token cannot solve all cache poisoning problems, but the hazard is no
worse than doing name lookups everywhere.

Yours, Junxiao