Two articles ago in this series, we began discussing the Neighbor Discovery Protocol for IPv6. We listed the nine functions performed by this protocol and also mentioned the five ICMPv6 packet types that it makes use of. We then began looking at the address resolution function which we completed in the last article. Finally, we looked at the Duplicate Address Detection in IPv6 as performed by ND. In this article, we will continue looking at the ND functions by focusing on the Next-Hop Determination process.

Before we begin looking at these functions, we first need to become familiar with some terms used in ND. These terms are under the conceptual data structures that every host must maintain for each interface.

Neighbor cache

This is where neighbors to which traffic have been sent recently are stored. Basically, it will include a mapping of the neighbor’s IP address to its link-layer address. It could also contain information about whether the neighbor is a router or host, and also the reachability state of the neighbor. To view the Neighbor Cache on a Windows PC, issue the netsh interface ipv6 show neighbors command in command prompt. An example snapshot is shown below:

On a Cisco router, this neighbor cache is available through the show ipv6 neighbors command.

Destination Cache

This is where destinations to which traffic have been sent recently are stored. Note the difference between the neighbor cache and the destination cache: the former stores information about direct neighbors while the latter stores information about destinations that could be on-link (directly reachable) or off-link (reachable through a router). The destination cache will contain a mapping of the destination IP address to the IP address of a next-hop neighbor and it may also contain other information like Path MTU (PTMU).

We can view the destination cache on a Windows PC by issuing the netsh interface ipv6 show destinationcache command in command prompt.

Prefix List

This contains a list of prefixes, each defining destination IP addresses that are directly reachable, i.e. on-link. This list is formed by the information received in Router Advertisements. We will see this again in a future article.

Default Router List

This contains a list of on-link routers to which traffic can be sent.

Like I mentioned above, these terms are “conceptual,” meaning that they can be implemented in different ways as long as the same goal is achieved. For example, in Windows OS, the prefix list and default router list are maintained in a routing table.

We will now look at how all these pieces fit together in the next-hop determination algorithm.

Next-Hop Determination Process

I have been referring to the next-hop determination as a process or algorithm throughout this article because it is in fact just a set of steps and not necessarily something “tangible” that requires sending/receiving of messages though it can trigger the address resolution function. We will discuss those steps now.

Step 1: Check destination cache

When a host wants to send a unicast packet to a destination, the first thing it will do is check if that destination IP address is in the destination cache. It is efficient to do this since the destination cache contains information about destinations to which traffic have recently been sent. If an entry is found in the destination cache, the host will obtain the next-hop address from this cache and go to step 3. If not, it will proceed to step 2.

We will use our network setup here again so that we can see the process happen.

The details of the interface on the host connected to the link are shown below. Notice it has an interface index of 39. This will help us in matching output from other commands that reference the interface index. Refresh your memory of zone indices here.

The plan is to initiate ping traffic from this host to R1, but before we do that, let’s check the destination cache. This host has not recently sent traffic to R1; therefore, the destination cache should not contain any entry for R1, i.e. notice that there is no entry for “fe80::1” under the Destination Address column.

Step 2: On-link or Off-link?

In this step, the host will consult its Prefix list to determine if the destination address is on-link or off-link. If the address is on-link, then the next-hop address is the same as the destination address. If the address is not on-link, then the host should select a router from the Default Router List. This is equivalent to saying “Send traffic to default gateway.” In both cases, proceed to step 3.

Note: Link-local addresses are always treated as being on-link. Also, for multicast packets, the multicast destination address is always treated as being on-link, so the next-hop address is the destination address.

Remember that I said Microsoft’s implementation of the prefix list and default router list is contained in a routing table which can be viewed by issuing the netsh interface ipv6 show route command. We can see the link-local prefix corresponding to our interface highlighted below:

In our scenario, since there was no entry in the destination cache, an entry will also be created at this point.

Step 3: Check Neighbor Cache

The host now has the next-node address to which it should send the traffic to; therefore, it will consult its neighbor cache to determine the link-layer address (e.g. MAC address) of the next-hop address. If an entry exists, then the host will use the link-layer address to forward the traffic. Otherwise, an entry will be created in the neighbor cache and address resolution will be performed as discussed in the last two articles.

In our scenario, my host has received unsolicited neighbor discovery messages from the router and so R1 already has an entry in the Neighbor cache with a state of “STALE” as highlighted below. We will discuss the different state types when discussing the Neighbor Unreachability Detection in a future article.

This is the result of my ping session:

While the traffic was being sent, I checked the neighbor cache of the host. Notice that the entry for R1 now has a state of “REACHABLE.”

It will remain in this reachable state while traffic is being sent to that neighbor. However, 30 seconds (as stated by the RFC) after traffic stops being sent to that neighbor, it reverts back to the stale state.

Summary

In this article, we have discussed the Next-hop determination function as performed by the ND protocol. We introduced the conceptual data structures that every IPv6 host must maintain including the neighbor cache and the destination cache. We then went on to use our network scenario to explain the steps performed by a host in determining the next-hop of a destination address.

In the next article, we will move on to the Router Discovery function. I hope you have found this article helpful.

References and further reading

  1. RFC 4861: Neighbor Discovery for IP version 6 (IPv6): http://tools.ietf.org/html/rfc4861