<commit_before>CCNx Interest Message
=====================

== Source references
link:xsd.html[ccnx.xsd] is the xml schema that describes what the xml rendition of ccn data (including Interest messages) should look like.

link:dtd.html[ccnx.dtd] is a dtd that should describe the same, in a less strongly-typed fashion.

link:DTAG.html[tagname.csvdict] contains the mapping between the DTAG values used in the binary encoding and the element names used in the XML representation.

Below we will use a less formal abstract syntax to indicate how the pieces fit together.

== Interest
.......................................................
Interest ::= Name
             MinSuffixComponents?
             MaxSuffixComponents?
             PublisherPublicKeyDigest?
             Exclude?
             ChildSelector?
             AnswerOriginKind?
             Scope?
             InterestLifetime?
             Nonce?
.......................................................

The hierarchical *Name* is the only required element in an Interest message.
The remaining elements fall into several categories:

1. those that further qualify the ContentObjects that may match the Interest *MinSuffixComponents*, *MaxSuffixComponents*, *PublisherPublicKeyDigest*, *Exclude*)
2. those that limit where the answer might come from (*AnswerOriginKind*, *Scope*)
3. those that advise the selection of what to send when there are multiple ContentObjects that match (*ChildSelector*)
4. duplicate suppression (*Nonce*)

See the xref:example[Example] for encodings of a minimal Interest
Message.

== Name

See the link:Name.html[CCNx Name Specification].

The Name element in an interest is synonymous with the term 'prefix'.


The Name of every piece of content includes as its final component a link:DigestComponent.html[derived digest] that serves to make the entire name unique. This may occur in an Interest Name as an ordinary Component (the last).  However, this final component is never included explicitly in the ContentObject as it appears on the wire.

== MinSuffixComponents, MaxSuffixComponents
...........................................................
MinSuffixComponents ::= nonNegativeInteger
MaxSuffixComponents ::= nonNegativeInteger
...........................................................

A client may need to say that the Name in the interest is either the full name including the digest, or the full name except for the digest, or that the content it is seeking has a known range of legitimate component counts.  To encode this there are two parameters, named *MinSuffixComponents* and *MaxSuffixComponents*, that specify these limits.  These refer to the number of name components beyond those in the prefix, and counting the implicit digest, that may occur in the matching ContentObject.  The default for *MinSuffixComponents* is 0 and for *MaxSuffixComponents* is effectively infinite.  Often only one of these will be needed to get the desired effect.

== PublisherPublicKeyDigest
...........................................................
PublisherPublicKeyDigest ::= BLOB
...........................................................
If the PublisherPublicKeyDigest element is present in the Interest, the associated value (a SHA-256 digest) must be equal to the value of the PublisherPublicKeyDigest of the ContentObject for there to be a match.
(The Interest schema admits some other possibilities, but only this form of publisher selection is currently implemented.)

== Exclude
...........................................................
Exclude ::= (Any | Bloom)? ( Component (Any | Bloom)? )*
Any ::= (empty)
Bloom ::= BLOB
...........................................................
The Exclude element embodies a description of name components that should not appear as a continuation of the Name prefix in the response to the interest.
The Components in the exclusion list must occur in strictly increasing order according to the link:CanonicalOrder.html[canonical CCNx ordering].  Call the pieces in the exclude list B[0], C[1], B[1], C[2], B[2], ... C[m], B[m].  (Here the B[i] are the Bloom elements and the C[i] are the Component elements.  The omission of a Bloom element is equivalent to a bloom filter that describes the empty set.) Furthermore, take C[0] as negative infinity and C[m+1] as infinity. Then a component C is a member of the exclusion set iff C = C[k] for some k in [1..m] or if C[k] < C < C[k+1] for some k in [0..m] and C matches B[k].

A client could choose to simply enumerate the elements of the exclusion set if that is sufficiently compact (using no Bloom filters at all).  At the other extreme, it could simply supply a single Bloom filter to describe the exclusion set.

A seed value is used for the hash functions of the bloom filters.  By using different seeds on different expressions of its interests, an application may minimize the impact of the false positives inherent with bloom filters.
...........................................................
Bloom ::= BLOB
...........................................................
The Bloom's BLOB is of length 8 + ceiling(n/8) bytes, where n is the number of bits in the bloom filter.  We restrict n to be a power of two or zero.  The first 8 bytes of the BLOB contains a header:
...........................................................
    unsigned char lg_bits;  /* 13 maximum (8 kilobits), 3 minimum (one byte) */
    unsigned char n_hash;   /* number of hash functions to employ */
    unsigned char method;   /* allow for various hashing algorithms */
    unsigned char reserved; /* must be 0 for now */
    unsigned char seed[4];  /* can seed hashes differently */
...........................................................
and the remaining bytes hold the bits of the bloom filter.  The bits in the filter itself are packed little-endian by byte.  Note that a Bloom filter with 0 hash functions is one way to match everything, and a filter with all ones is another.  But these are not very compact, so the *All* element is provided as a better way to encode this common case.

**TODO - The the calculation of the hash functions must also be specified.  At present, referring to the c code is the best option; it should be quite easy to port to other languages.**

== ChildSelector
...........................................................
ChildSelector ::= nonNegativeInteger
...........................................................
Often a given interest will match more than one ContentObject within a given content store. The *ChildSelector* provides a way of expressing a preference for which of these should be returned.  If the (low order bit of) the value is 0, the leftmost child is preferred. If 1, the rightmost child is preferred. Here leftmost and rightmost refer to the least and greatest components according to the link:CanonicalOrder.html[canonical CCNx ordering].  This ordering is only done at the level of the name hierarchy one past the name prefix.

== AnswerOriginKind
...........................................................
AnswerOriginKind ::= nonNegativeInteger
...........................................................
*AnswerOriginKind* encodes several bitfields that alter the usual response to interest. There is a do-not-answer-from-content-store bit, which also implies a passive bit.  There will eventually need to be some security aspects to this, limiting it by scope and/or by interest signing, but we are choosing to ignore these for now. There is also utility in the passive bit alone - it means do not generate any newly-signed content in response to this interest.
Wire representation: the AnswerOriginKind element holds a nonNegativeInteger with bitmasks having the following interpretation:

* 1 = Answer from existing content store
* 2 = Answers may be generated
* 4 = Answer may be "stale"
* 16 = Mark as stale in content store (must have Scope 0) __Status:__ _hack_
* The default is 3, giving normal behavior.  The two low-order bits in combination mean:
** 0 = do-not-answer-from-content-store
** 1 = passive
** 2 is disallowed
** 3 = normal

== Scope
...........................................................
Scope ::= nonNegativeInteger
...........................................................
This limits where the Interest may propagate. Scope 0 prevents propagation beyond the local ccnd (even to other applications on the same host).  Scope 1 limits propagation to the applications on the originating host. Scope 2 limits propagation to no further than the next host. Other values are not currently defined, and will cause the Interest message to be dropped.

Note that this is not a hop count - the value is not decremented as the interest is forwarded.

== InterestLifetime
...........................................................
InterestLifetime ::= BLOB
...........................................................
InterestLifetime indicates the (approximate) time remaining before the interest times out.  The value is encoded as an unsigned big-endian binary number, and is allowed to have leading zero bytes. The time unit is the same as used for the Timestamp in ContentObject, 1/4096 second.  The timeout is relative to the arrival time of the interest at the current node.

Although this format allows for high precision, the values that appear on the wire should be quantized to a small set of possibilities so that the suppression of similar interests from various sources can be done effectively.  It is recommended that the value be either a positive integral number of seconds (low order 12 bits all 0), or a power of two (1/2 sec, 1/4 sec, etc.).

Nodes that forward interests may decrease the lifetime to account for time spent in the node before forwarding, but are not required to do so.  It is recommended that these adjustments be done only for relatively large delays (measured in seconds).

If the InterestLifetime element is omitted, the value of 4 seconds is used (0x4000).  The missing element may be added before forwarding.

It is the application that chooses the value for InterestLifetime.

== Nonce
...........................................................
Nonce ::= BLOB
...........................................................
The Nonce carries a randomly-genenerated bytestring that is used to detect and discard duplicate Interest messages.  Applications generally do not need to generate or check the Nonce.  Note that the Nonce is not the only basis for detecting and discarding duplicate Interest messages that arrive at a node, but can be used to improve the efficiency of the detection.

[[example]]
== Example

Here is an example of an Interest containing a name prefix with 2
 components.

In the link:URI.html[CCNx URI scheme] the name for this example is
`ccnx:/PARC/%00%01%02`.

In XML, the Interest Message is:

...........................................................
<Interest>
  <Name>
    <Component ccnbencoding="base64Binary">UEFSQw==</Component>
    <Component ccnbencoding="base64Binary">AAEC</Component>
  </Name>
</Interest>
...........................................................
or, equivalently,
...........................................................
<Interest>
  <Name>
    <Component ccnbencoding="text">PARC</Component>
    <Component ccnbencoding="base64Binary">AAEC</Component>
  </Name>
</Interest>
...........................................................

The link:BinaryEncoding.html[ccnb binary encoding] for this message would appear
in hexdump form as 

..............................................................................
00000000  01 d2 f2 fa a5 50 41 52  43 00 fa 9d 00 01 02 00  |.....PARC.......|
00000010  00 00                                             |..|
..............................................................................

This is the form that actually appears on the wire.
<commit_msg>refs #100250  Update the description of Exclude to say what the Any element is about. Hint at directions for future changes.<commit_after>CCNx Interest Message
=====================

== Source references
link:xsd.html[ccnx.xsd] is the xml schema that describes what the xml rendition of ccn data (including Interest messages) should look like.

link:dtd.html[ccnx.dtd] is a dtd that should describe the same, in a less strongly-typed fashion.

link:DTAG.html[tagname.csvdict] contains the mapping between the DTAG values used in the binary encoding and the element names used in the XML representation.

Below we will use a less formal abstract syntax to indicate how the pieces fit together.

== Interest
.......................................................
Interest ::= Name
             MinSuffixComponents?
             MaxSuffixComponents?
             PublisherPublicKeyDigest?
             Exclude?
             ChildSelector?
             AnswerOriginKind?
             Scope?
             InterestLifetime?
             Nonce?
.......................................................

The hierarchical *Name* is the only required element in an Interest message.
The remaining elements fall into several categories:

1. those that further qualify the ContentObjects that may match the Interest (*MinSuffixComponents*, *MaxSuffixComponents*, *PublisherPublicKeyDigest*, *Exclude*)
2. those that limit where the answer might come from (*AnswerOriginKind*, *Scope*, *InterestLifetime*)
3. those that advise the selection of what to send when there are multiple ContentObjects that match (*ChildSelector*)
4. duplicate suppression (*Nonce*)

See the xref:example[Example] for encodings of a minimal Interest
Message.

== Name

See the link:Name.html[CCNx Name Specification].

The Name element in an interest is synonymous with the term 'prefix'.


The Name of every piece of content includes as its final component a link:DigestComponent.html[derived digest] that serves to make the entire name unique. This may occur in an Interest Name as an ordinary Component (the last).  However, this final component is never included explicitly in the ContentObject as it appears on the wire.

== MinSuffixComponents, MaxSuffixComponents
...........................................................
MinSuffixComponents ::= nonNegativeInteger
MaxSuffixComponents ::= nonNegativeInteger
...........................................................

A client may need to say that the Name in the interest is either the full name including the digest, or the full name except for the digest, or that the content it is seeking has a known range of legitimate component counts.  To encode this there are two parameters, named *MinSuffixComponents* and *MaxSuffixComponents*, that specify these limits.  These refer to the number of name components beyond those in the prefix, and counting the implicit digest, that may occur in the matching ContentObject.  The default for *MinSuffixComponents* is 0 and for *MaxSuffixComponents* is effectively infinite.  Often only one of these will be needed to get the desired effect.

== PublisherPublicKeyDigest
...........................................................
PublisherPublicKeyDigest ::= BLOB
...........................................................
If the *PublisherPublicKeyDigest* element is present in the Interest, the associated value (a SHA-256 digest) must be equal to the value of the *PublisherPublicKeyDigest* of the ContentObject for there to be a match.
(The Interest schema admits some other possibilities, but only this form of publisher selection is currently implemented.)

== Exclude
...........................................................
Exclude ::= (Any | Bloom)? ( Component (Any | Bloom)? )*
Any ::= (empty)
Bloom ::= BLOB
...........................................................
The *Exclude* element embodies a description of name components that should not appear as a continuation of the Name prefix in the response to the interest.
The Components in the exclusion list must occur in strictly increasing order according to the link:CanonicalOrder.html[canonical CCNx ordering].
Call the pieces in the exclude list B[0], C[1], B[1], C[2], B[2], ... C[m], B[m].
(Here the B[i] are the *Bloom* (or *Any*) elements and the C[i] are the *Component* elements.
An *Any* element is equivalent to a fully-saturated Bloom filter.
The omission of a Bloom/Any element is equivalent to a Bloom filter that describes the empty set.)
Furthermore, take C[0] as negative infinity and C[m+1] as infinity.
Then a component C is a member of the exclusion set iff C = C[k] for some k in [1..m] or if C[k] < C < C[k+1] for some k in [0..m] and C matches B[k].

A client could choose to simply enumerate the elements of the exclusion set if that is sufficiently compact (using no Bloom filters at all).  At the other extreme, it could simply supply a single Bloom filter to describe the exclusion set.

A seed value is used for the hash functions of the Bloom filters.  By using different seeds on different expressions of its interests, an application may minimize the impact of the false positives inherent with Bloom filters.
...........................................................
Bloom ::= BLOB
...........................................................
The *Bloom* element's BLOB is of length 8 + ceiling(n/8) bytes, where n is the number of bits in the Bloom filter.  We restrict n to be a power of two or zero.  The first 8 bytes of the BLOB contains a header:
...........................................................
    unsigned char lg_bits;  /* 13 maximum (8 kilobits), 3 minimum (one byte) */
    unsigned char n_hash;   /* number of hash functions to employ */
    unsigned char method;   /* allow for various hashing algorithms */
    unsigned char reserved; /* must be 0 for now */
    unsigned char seed[4];  /* can seed hashes differently */
...........................................................
and the remaining bytes hold the bits of the Bloom filter.  The bits in the filter itself are packed little-endian by byte.  Note that a Bloom filter with 0 hash functions is one way to match everything, and a filter with all ones is another.  But these are not very compact, so the *All* element is provided as a better way to encode this common case.

**TODO - The the calculation of the hash functions must also be specified.  At present, referring to the c code or java code in the libraries is the best option.**

**NOTE - New applications should avoid the use of the Bloom form of exclusion.  Support for this will be phased out in future revisions.**

== ChildSelector
...........................................................
ChildSelector ::= nonNegativeInteger
...........................................................
Often a given interest will match more than one ContentObject within a given content store. The *ChildSelector* provides a way of expressing a preference for which of these should be returned.  If the (low order bit of) the value is 0, the leftmost child is preferred. If 1, the rightmost child is preferred. Here leftmost and rightmost refer to the least and greatest components according to the link:CanonicalOrder.html[canonical CCNx ordering].  This ordering is only done at the level of the name hierarchy one past the name prefix.

== AnswerOriginKind
...........................................................
AnswerOriginKind ::= nonNegativeInteger
...........................................................
*AnswerOriginKind* encodes several bitfields that alter the usual response to interest. There is a do-not-answer-from-content-store bit, which also implies a passive bit.  There will eventually need to be some security aspects to this, limiting it by scope and/or by interest signing, but we are choosing to ignore these for now. There is also utility in the passive bit alone - it means do not generate any newly-signed content in response to this interest.
Wire representation: the *AnswerOriginKind* element holds a nonNegativeInteger with bitmasks having the following interpretation:

* 1 = Answer from existing content store
* 2 = Answers may be generated
* 4 = Answer may be "stale"
* 16 = Mark as stale in content store (must have Scope 0) __Status:__ _hack_
* The default is 3, giving normal behavior.  The two low-order bits in combination mean:
** 0 = do-not-answer-from-content-store
** 1 = passive
** 2 = bypass intermediate caches, and inform applications that they may generate new content (currently this combination is disallowed, but later revisions of the protocol will allow it).
** 3 = normal

== Scope
...........................................................
Scope ::= nonNegativeInteger
...........................................................
This limits where the Interest may propagate. Scope 0 prevents propagation beyond the local ccnd (even to other applications on the same host).  Scope 1 limits propagation to the applications on the originating host. Scope 2 limits propagation to no further than the next host. Other values are not defined, and will cause the Interest message to be dropped.

Note that this is not a hop count - the value is not decremented as the interest is forwarded.

== InterestLifetime
...........................................................
InterestLifetime ::= BLOB
...........................................................
*InterestLifetime* indicates the (approximate) time remaining before the interest times out.  The value is encoded as an unsigned big-endian binary number, and is allowed to have leading zero bytes. The time unit is the same as used for the Timestamp in ContentObject, 1/4096 second.  The timeout is relative to the arrival time of the interest at the current node.

Although this format allows for high precision, the values that appear on the wire should be quantized to a small set of possibilities so that the suppression of similar interests from various sources can be done effectively.  It is recommended that the value be either a positive integral number of seconds (low order 12 bits all 0), or a power of two (1/2 sec, 1/4 sec, etc.).

Nodes that forward interests may decrease the lifetime to account for time spent in the node before forwarding, but are not required to do so.  It is recommended that these adjustments be done only for relatively large delays (measured in seconds).

If the *InterestLifetime* element is omitted, the value of 4 seconds is used (0x4000).  The missing element may be added before forwarding.

It is the application that chooses the value for *InterestLifetime*.

== Nonce
...........................................................
Nonce ::= BLOB
...........................................................
The Nonce carries a randomly-genenerated bytestring that is used to detect and discard duplicate Interest messages.  Applications generally do not need to generate or check the Nonce.  Note that the Nonce is not the only basis for detecting and discarding duplicate Interest messages that arrive at a node, but can be used to improve the efficiency of the detection.

[[example]]
== Example

Here is an example of an Interest containing a name prefix with 2
 components.

In the link:URI.html[CCNx URI scheme] the name for this example is
`ccnx:/PARC/%00%01%02`.

In XML, the Interest Message is:

...........................................................
<Interest>
  <Name>
    <Component ccnbencoding="base64Binary">UEFSQw==</Component>
    <Component ccnbencoding="base64Binary">AAEC</Component>
  </Name>
</Interest>
...........................................................
or, equivalently,
...........................................................
<Interest>
  <Name>
    <Component ccnbencoding="text">PARC</Component>
    <Component ccnbencoding="base64Binary">AAEC</Component>
  </Name>
</Interest>
...........................................................

The link:BinaryEncoding.html[ccnb binary encoding] for this message would appear
in hexdump form as 

..............................................................................
00000000  01 d2 f2 fa a5 50 41 52  43 00 fa 9d 00 01 02 00  |.....PARC.......|
00000010  00 00                                             |..|
..............................................................................

This is the form that actually appears on the wire.

{'fraction_non_alphanumeric': 0.187052726824052, 'fraction_numerical': 0.010035370568396809, 'mean_word_length': 2.2497995188452284, 'pattern_counts': {'":': 0, '<': 39, '<?xml version=': 0, '>': 35, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 4}, 'pii_count': 0, 'substrings_counts': 2, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3289912', 'n_tokens_mistral': 5511, 'n_tokens_neox': 5176, 'n_words': 3044}