Subject: [Icnrg-harmonization] Types of discovery queries

From: <[email-masked]>
Date: Tue, 30 Aug 2016 19:14:20 +0000

Here’s a list of things one could try to discover.  These are independent of the algorithm used to return the result or the protocol used to implement the algorithm.  I believe one could construct different algorithms and protocols with different time and message complexities.  This is an initial list I whipped up the other week and is not meant to be exhaustive.   I’d welcome other contributions to the list or revisions of them.

I have also not considered specific network use cases (IoT mesh vs IoT gateway vs vehicular no infrastructure vs vehicular with infrastructure vs carrier network vs Internet vs etc…).

I think another important question is “what is the required discovery in the network layer for the network layer to operate?”  My opinion is it is “none” and the bootstrapping is an application or transport level concern.

As per our call today, I do not have a specific answer to what are the “necessary” queries to bootstrap an application.  I think by looking at the possible queries and application use cases, one might be able to find a reduction in some queries to other queries (e.g. #5 below might be expressible in terms of other queries).

====

Given a name prefix P with |P| components and constraints {MinSuffixComponents, MaxSuffixComponents}.  A discovered name must satisfy the constraints.  Define the term “next name component” to mean the (|P|+1)-th name component.

A name P’ is a suffix of P iff the first |P| name components of P’ equal those in P and |P| <= |P’|.

Only the consumer can make the trust decision if a Data/Content Object is valid, which goes beyond if it satisfies the name component conditions.  This restriction could be relaxed if the consumer knows the specific signing key and can distribute that as part of the query and each potential responder validates the signature (though this obviously has its own downsides).  Depending on how one handles this requirement could lead to exclusions.

One should make normal distributed algorithm assumptions about byzantine faults, message loss, etc.

1) [Least upper bound] A name P’ that is a suffix of P and whose next name component is greater than value V.  If there are multiple options, return the maximum of the next name component and the minimum  for the remainder.

2) [Greatest upper bound] As in (1), but return the maximum of the remainder of the name.

3) [Greatest lower bound] A name P’ that is a suffix of P and whose next name component is less than value V..  If there are multiple options, return the minimum of the next name component and the maximum for the remainder.

4) [Least lower bound] As in (3), but return the minimum of the remainder of the name.

5) All names P* that are a suffix of P.

6) All names P* that allow wildcards or regex in P (e.g. P = ‘/foo/*/bar/*’ or ‘/foo/{car,bus}/bar/*’).

Marc