NFD

# Prefix Insertion

The prefix insertion protocol is used to securely provide routing entities with new route entries from end nodes, adhering to the principle of separating routing and forwarding.

## Background & Motivation

To become a data producer, applications need to make their prefixes known to the network.

A Named Data Network has *routing* and *forwarding* entities. 

Forwarding entities are responsible for delivering packets to the next hop based on some forwarding strategy based on its prefix.

A routing entity, co-located with a forwarding entity, is concerned with receiving, propagating, verifying, and applying policies for route information.

When a data-producing entity is ready to produce data, it sends a command to one of these entities so that its prefix is added into a routing table.

(For traditional NFD, this entity is the forwarder. For prefix insertion, this entity is the router.)

In ndnd, forwarding is handled by the`fw` module while routing is handled by the `dv` module. 

Usually, nodes on the network run both modules, as the forwarders must be informed of prefixes by the router. 

However, end nodes may run a forwarder only, sending outbound interests through a default route and inbound interests to a local face.

Existing protocols do not properly separate routing and forwarding. 

End nodes often must communicate with the forwarding entity instead of the routing entity.

For example, the popular prefix registration protocol is designed for end nodes to add a prefix into a forwarding entity.

This requires the forwarding entity to have its own RIB (Routing Information Base) additional to the routing entity's RIB.

This also requires the forwarding entity to inform the routing entity of the new prefix in order for the prefix to be propagated, the reverse of the ideal direction of communication.

## Design

The prefix insertion protocol facilitates direct communication between data producers on an end node and a routing entity.

The communication pattern is as follows:

1. A data producer expresses an interest under a certain prefix that is sent to the closest routing entity. The interest contains signed data whose name contains the desired prefix to insert.

2. The local forwarder sends the interest to the local routing entity (if there is one running on the machine) or otherwise the routing entity of a neighboring forwarder. 

3. The routing entity verifies the data inside the interest according to a trust schema. If valid, it parses the information and adds it to its RIB (routing information base) with metadata such as the expiration or cost for the single link back to the producer. An acknowledgement (or application-level NACK) is sent to the data producer as data in response to the interest.

4. Changes to the RIB are reflected in the co-located forwarding entity's FIB (forwarding information base) through a synchronization procedure. These changes are also encoded in the distance vector and sent to neighboring routing entities as part of the distance vector algorithm to propagate routes.

Note that the data producer, upon desiring to produce data, always sends a prefix registration to the local forwarder in addition to the prefix insertion interest.

This is so that if there is no local routing entity running on the machine, the new prefix is still known to the local forwarder.

If the data producer has no desire for the prefix to be known beyond the local forwarder, it will send the prefix registration only.

### Routing Security

Prefix Insertion interests contain signed data encoded using the standard wire format in the Application Parameters field.

As the signed portion of the data includes the name, and the desired prefix to insert is a prefix of the name, routing entities can encode insertion authorization over the NDN namespace as an arbitrary trust schema.

For example, a trust schema can express the fact that the entity with identity `/ucla.edu/alice` (Alice) is authorized to produce data under the prefix `/example.com/blog/alice/`. 

Similarly, the trust schema used by prefix insertion can express that only Alice is authorized to insert any name beginning with `/example.com/blog/alice/` into the routing entity.

Different routing entities can have different trust policies and domains and therefore different trust schema. 

Typically, however, a data producer is knowingly connected to a specific network and therefore a specific group of routing entities. 

The necesity of data verification for routing security also necesitates some trust relation between the network service provider and the data producer or application. 

This trust relation is usually some certificate; the prefix insertion's signing certificate may trace back to this certificate.

When a data producer roams to another network with a different trust domain, it may be able to continue inserting its prefix provided inter-domain trust relations exist, i.e., certificates and policy exist to trace the signing certificate to a trust anchor in the roaming domain.

Certificates used in the verification chain that may not be found in the network should be stapled to the Prefix Insertion data. 

This ensures that, if any certificate in the chain is only located on the data producer, the routing entity has access to it before the data producer has inserted the certificate's prefix.

### Interaction with Forwarding Entity

The routing entity should have a procedure to synchronize the forwarding entity's FIB (forwarding information base) with its own RIB (routing information base) upon any changes. 

This usually occurs through the traditional prefix register (and unregister) protocol--i.e., by the routing entity sending a command interest to the forwarding entity through the localhost prefix. 

(To ensure routing security, while the forwarding entity should still work with the older prefix registration protocol, it should be selective about the origin of commands--for example, allowing localhost only.)

Communication must also occur in the opposite direction--from forwarding entity to routing entity--to inform of a change in a face's status (i.e., a face that goes down).

Upon receiving this information, the routing entity removes any row with that face from the RIB.

Note that the specifics of this internal communication paradigm are not dictated by the Prefix Insertion protcol.

### Removing a Prefix

Prefix insertions must have an expiration (a time delta which, upon receipt by the routing entity, is added to the current time to find the time after which the route is no longer valid). 

A data producer should also remove the prefix from the routing table if it no longer desires to produce the data.

To do so, the data producer should send another prefix insertion with an expiration set to a flag value. 

When the routing entity receives the command, it will remove the route from its RIB, thus also causing the route to be removed from the forwarding entity's FIB. An updated distance vector is sent to neighboring routing entities, eventually removing the route from all routers in the network.

## Protocol Specification & Wire Format

### Outer Interest

Prefix insertions are sent by data producers as interests with the name in the format `/routing/insert/<params-sha256>`, where `<params-sha256>` is the Parameters Digest Component computed according to the specification of a standard NDN interest.

The interest carries the prefix announcement object inside the Application Parameters of the interest as a wire-encoded block.

The interest may be signed; however, this protocol does not define how verification of the outer interest signature occurs.

Thus, applications may opt to sign the inner Prefix Announcement object only.

The MustBeFresh option must be set in the interest.

### ApplicationParameters

The value ApplicationParameters of the interest encapsulates multiple blocks. A layout of the Prefix Insertion interest with ApplicationParameters is shown below:

```

Interest

  Name /routing/insert/<params-sha256>

  MustBeFresh

  ApplicationParameters

    Data (Prefix Announcement Object)

    StapledCertificates

      Certificate

      Certificate

      (...)

```

The Prefix Announcement Object (described in the next section) is a signed Data block containing parameters of the desired insertion. A valid Prefix Insertion contains exactly one such objects. 

The sequential TLV blocks for the object containing parameters and StapledCertificates are order-agnostic and can be wire encoded in any order.

To provide the routing entity with certificates needed to verify the Prefix Announcement Object,  necessary certificates in the signing chain (usually those not obtainable by the routing entity otherwise) should be appended as additional blocks within a StapledCertificates block.

The StapledCertificates block is optional if there are no certificates to be stapled.

Conversely, when the routing entity parses the value of the ApplicationParameters block, any inner TLV blocks inside the StapledCertificates block are a certificates in no particular order which may be used to validate the Prefix Announcement Object.

### Parameters Object

We use the Prefix Announcement object to convey parameters as a signed Data within the interest's Application Parameters containing the necessary information for a prefix insertion.

#### Name

The name of the data starts with the prefix to insert followed by a fixed keyword component with value 'PA', a version component, and then a segment component.

Two distinct prefix insert commands for the same prefix sent to the routing entity should not have the same value in the version component. A prefix insertion interest for the same prefix sent after another must have the higher value.

The segment component must have a value of 0; non-zero segment components are reserved for future use.

For example, if `/example.com/blog/alice` is the desired prefix to announce, the name of the (first version of the) object would be `/example.com/blog/alice/32=PA/54=1`.

#### Data Layout

The standard data wire format (with a content type of 5) is used.

An example and description of fields in the content are as follows.

```

Data

  Name /example.com/blog/alice/32=PA/54=1/50=0

  MetaInfo

    ContentType 5 (Prefix Announcement)

  Content

    ExpirationPeriod 3600000

    ValidityPeriod

      NotBefore 20181030T000000

      NotAfter  20181124T235959

    Cost 2

  SignatureInfo

  SignatureValue 

```

The content contains a sequence of TLV elements, including at least an ExpirationPeriod element. 

The ordering of these TLV elements is insignificant. Unrecognized non-critical TLV elements are permitted and must be ignored.

* `ExpirationPeriod`: the duration (time delta) for which the route information should remain in the RIB of the routing entity. The duration begins when the routing entity receives the prefix announcement. This element is required.

    * An ExpirationPeriod greater than zero and less than or equal to the maximum allowable duration (configured on the routing entity) represents a duration in **milliseconds**.

    * An ExpirationPeriod of 0 represents the data producer's desire to remove the route. 

    * Any other ExpirationPeriod value is an error condition.

* `Cost`: The route cost from the data producer to the forwarding entity co-located with the routing entity. This element is optional; when not included, the routing entity must interpret the cost as 0.

    * A Cost greater than or equal to zero and less than the 'infinity' cost (defined by the network) represents a valid route cost.

    * Any other Cost value is an error condition.

* `ValidityPeriod`: The absolute time range in which the prefix insertion remains valid. It is ignored if the receiving node does not have a UnixTime clock. This element is optional.

  * This element conforms to the syntax and semantics of the [standard `ValidityPeriod` element](https://docs.named-data.net/NDN-packet-spec/current/certificate.html#signatureinfo).

  * When both ExpirationPeriod and ValidityPeriod are present, the most restrictive constraint applies.

### Stapled Certificates Format

The Stapled Certificates Format defines the format of TLV blocks used to provide routing entities with certificates before they are available in the network by including them in the value field of the ApplicationParameters block.

The purpose of these StapledCertificate blocks is to nest certificates inside its value while having a type that distinguishes them from the Prefix Announcement Object:

```abnf

StapledCertificates = STAPLED-CERTIFICATE-TYPE TLV-LENGTH Certificate

```

The TLV type number for StapledCertificates is 534 (0x216).

### Routing Entity Response

The routing entity will, upon normal operation, send an acknowledgement or negative acknowledgement depending on whether the prefix insertion could be verified, has valid values, and can be handled by the RIB.

The Control Command Response [format](https://redmine.named-data.net/projects/nfd/wiki/ControlCommand#Response-format) should be used for the response.

Negative acknowledgements are those with a StatusCode other than 200; they do not have Control Parameters in the body. For acknowledgements, the following elements must be included in the Control Command Response body's Control Parameters:

* Name

* ExpirationPeriod

* Cost

The Name and ExpirationPeriod must be identical to the user-supplied values in the Prefix Announcement object. The Cost must be the user-supplied cost value, if provided, or 0 otherwise.