Skip to main content

5. Conceptual Model of a Host

Although it is not required that implementations conform to a specific conceptual model of a host, this section describes a conceptual model that can be used by hosts to help understand Neighbor Discovery. A host conceptually maintains a number of data structures:

Neighbor Cache - A set of entries about individual neighbors to which traffic has been sent recently. Entries are keyed on the neighbor's on-link unicast IP address and contain such information as its link-layer address, a flag indicating whether the neighbor is a router or a host (called IsRouter in this document), a pointer to any queued packets waiting for address resolution to complete, etc. A Neighbor Cache entry also contains information used by the Neighbor Unreachability Detection algorithm, including the reachability state, the number of unanswered probes, and the time the next Neighbor Unreachability Detection event is scheduled to take place.

Destination Cache - A set of entries about destinations to which traffic has been sent recently. The Destination Cache includes both on-link and off-link destinations and provides a level of indirection into the Neighbor Cache; the Destination Cache maps a destination IP address to the IP address of the next-hop neighbor. Unlike the Neighbor Cache, the Destination Cache contains entries for both on-link and off-link destinations. Maintaining a Destination Cache separate from the Neighbor Cache serves multiple purposes. First, the Destination Cache can contain entries for destinations that are not adjacent on the link. Second, the Destination Cache can contain entries that are subject to Path MTU Discovery, Redirect messages, etc.

Prefix List - A list of the prefixes that define a set of addresses that are on-link. Prefix List entries are created from information received in Router Advertisements. Each entry has an associated invalidation timer value (extracted from the advertisement) used to expire prefixes. A Prefix List entry also contains a flag indicating whether the prefix can be used for on-link determination and/or address autoconfiguration, as specified in [ADDRCONF].

Default Router List - A list of routers to which packets may be sent. Default Router List entries point to entries in the Neighbor Cache; the algorithm for selecting a default router favors routers known to be reachable over those whose reachability is suspect. Each entry also has an associated invalidation timer value (extracted from Router Advertisements) used to delete entries that are no longer advertised.

The conceptual data structures described above are functionally separate; implementations are free to combine some or all of them in whatever way is most convenient. The requirements of this protocol can be met in a straightforward manner through the use of the above data structures in the pseudocode in the following sections. However, an implementation is free to use alternative data structures as long as the external behavior of the implementation remains unchanged.

5.1. Conceptual Data Structures​

Although it is not necessary for hosts to maintain all the data structures described below, this section describes a set of data structures that are sufficient for implementing Neighbor Discovery.

5.2. Conceptual Sending Algorithm​

When a node has a packet to send, it first examines the Destination Cache. If no entry exists for the destination, the node creates one and initializes its next-hop address by invoking the next-hop determination algorithm (Section 5.2). Once a Destination Cache entry has been created, the node then examines the state of the Neighbor Cache entry for the next hop.

A Neighbor Cache entry can be in one of five states:

INCOMPLETE - Address resolution is currently being performed on the entry. Specifically, a Neighbor Solicitation has been sent to the solicited-node multicast address of the target, but the corresponding Neighbor Advertisement has not yet been received.

REACHABLE - The entry is known to have been reachable recently (within tens of seconds ago). Positive confirmation was received within the last ReachableTime milliseconds that the forward path to the neighbor was functioning properly. While REACHABLE, no special action takes place as packets are sent.

STALE - The entry is known to have been reachable recently, but no confirmation was recently received. While STALE, no action takes place until a packet is sent. When a packet is sent, a node transitions the entry to either DELAY or PROBE, depending on the implementation.

DELAY - The entry is known to have been reachable recently, and a packet was sent within the last DELAY_FIRST_PROBE_TIME seconds. If no reachability confirmation is received within DELAY_FIRST_PROBE_TIME seconds of entering the DELAY state, send a Neighbor Solicitation and change the state to PROBE. Delaying the transmission of the probe gives an opportunity for upper-layer protocols to provide reachability confirmation.

PROBE - A reachability confirmation is actively sought by retransmitting Neighbor Solicitations every RetransTimer milliseconds until a reachability confirmation is received.

The Neighbor Cache also holds information needed to run the Neighbor Unreachability Detection algorithm, including various timers, counters, etc.

When sending a packet to a neighbor, a node uses the state information contained in the Neighbor Cache entry to determine what, if anything, needs to be done before sending traffic to that neighbor. The following pseudocode illustrates the sending algorithm:

if (Destination Cache entry exists) {
    next hop = Destination Cache next_hop;
} else {
    next hop = Next-hop determination (Section 5.2);
    create Destination Cache entry;
}

if (Neighbor Cache entry exists for next hop) {
    if (Neighbor Cache entry state == INCOMPLETE) {
        queue packet on Neighbor Cache entry;
        /* Address resolution already in progress */
    }
    if (Neighbor Cache entry state == REACHABLE) {
        send packet;
    }
    if (Neighbor Cache entry state == STALE) {
        send packet;
        set Neighbor Cache entry state to DELAY;
        set Neighbor Cache entry timer to DELAY_FIRST_PROBE_TIME;
    }
    if (Neighbor Cache entry state == DELAY) {
        send packet;
        /* timer is already set */
    }
    if (Neighbor Cache entry state == PROBE) {
        send packet;
        /* Neighbor Unreachability Detection is in progress */
    }
} else {
    create Neighbor Cache entry;
    set Neighbor Cache entry state to INCOMPLETE;
    if (link layer address is readily available) {
        set link-layer address;
        set Neighbor Cache entry state to STALE;
        send packet;
    } else {
        queue packet on Neighbor Cache entry;
        start address resolution;
    }
}

5.3. Garbage Collection and Timeout Requirements​

The Neighbor Cache, Destination Cache, and Prefix List must be garbage collected and timed out. However, the specific timeout periods are deliberately not specified. Timeout periods must be chosen to provide a reasonable balance between maintaining stale information and the cost of updating that information. In general, timeout periods should be generous enough to prevent thrashing of the cache contents but short enough to prevent long-term staleness.

A conceptual implementation might use the following rules:

  • Neighbor Cache entries should remain for at least a time specified by ReachableTime after they transition to the STALE state. However, they can remain longer if the implementation uses some form of garbage collection algorithm to reclaim entries. Entries in the INCOMPLETE state do not need to remain for such an extended period of time.

  • Destination Cache entries should remain in the cache as long as possible (i.e., indefinitely). However, the specific time period is implementation dependent. Implementations SHOULD invalidate a Destination Cache entry if a Redirect message specifying a better route to the destination is received.

  • Entries in the Prefix List time out in accordance with the lifetime specified in Router Advertisements. The lifetime of an entry is updated when a new Router Advertisement arrives.

  • Entries in the Default Router List time out in accordance with the Router Lifetime specified in Router Advertisements. Received Router Advertisements with a Router Lifetime of zero indicate that the router should be removed from the Default Router List immediately.

Last updated on