ndp — Neighbor Discovery Protocol, NDP
Neighbor Discovery Protocol (NDP)
is a protocol used by hosts and routers to:
Find the link-layer address of the
neighbors known to be attached to the
Find the neighboring routers that
are willing to forward packets on
Actively keep track of which
neighbors are reachable and which
Search for alternate routers when
the path to a router fails.
To accomplish the above mentioned tasks,
NDP defines the following processes:
Router and Prefix Discovery
Router discovery is a process through
which hosts locate the neighboring
routers and learn prefix plus other
parameters necessary for address
Prefix discovery is used by the hosts
to learn the range of IPv6 addresses
that reside on-link and can be reached
without going through a router.
Routers send Router Advertisements
which will make the hosts treat them
as the default routers.
The Router Advertisements will also contain
prefix information options that will
identify the range of IPv6 addresses
that are on-link (Subnet prefix).
Router and Host Requirements
Router requirements in NDP specify a
set of rules for host to act as a router.
These rules include:
Router configuration variables.
These configuration variables include
intervals between successive unsolicited
router advertisements, etc.
How to make an interface an advertising interface.
When an interface is made an
advertising interface, it means that the
node is going to send periodic router
advertisements and is willing to forward
packets on behalf of hosts on that link.
Message content for router advertisements.
A router will send periodic as well as
solicited Router Advertisements on an
NDP specifies the format of these messages.
Sending unsolicited router advertisements.
Apart from sending solicited router advertisements
in response to router solicitations, routers
can send unsolicited router advertisements.
For example, unsolicited router advertisements
can be sent to expire a prefix or to
advertise a new prefix, etc.
Stopping router advertisements on an interface.
A router can stop advertising prefixes on an
This can happen due to system
management decisions when a router may be stopped
from being one.
NDP specifies what the router
should be doing under these circumstances.
Processing router solicitation messages.
Hosts as part of the stateless autoconfiguration process
will send Router Solicitations.
Routers should respond to such solicitations with a router
Steps to be taken when the link-local address for the router changes.
Normally the link-local address of a Router should
However, NDP still defines the steps
should be taken by the router when its link-local
address changes for any of its interfaces.
Host requirements are a set of rules
that apply for a IPv6 host.
IPv6 variables that have to be maintained.
These variables include the time between
retransmissions of neighbor solicitations,
link MTU for each interface, etc.
Processing router advertisements.
This rule discusses what actions should be
taken on receipt of router advertisements.
Timing out prefixes and default routers.
Whenever routers send router advertisements,
they include the lifetime of the router as well
as the prefixes that they advertise.
NDP specifies what actions the host should take
when these lifetimes expire.
Selecting a default router.
When there is more than one router in the
link, the default router
selection algorithm comes into effect.
This algorithm helps select the default
router based on factors like reachability, etc.
Sending a router solicitation.
When an interface is enabled, a host need not
wait for the unsolicited router advertisement.
Instead, it can send a router solicitation and
get a router advertisement as a response.
This will help in receiving the default router and prefix
information as soon as the interface is enabled.
Algorithm for Sending a Packet
Any IPv6 host is required to maintain
some data structures that will be used
by the algorithm for sending a packet.
These data structures are:
- Neighbor Cache
A set of entries that will maintain
IPv6 Address to link-layer address
mappings for neighbors to which
a packet has been sent recently.
In addition to that it maintains information
needed for neighbor unreachability detection
like the reachability state, etc.
- Destination Cache
A set of entries for hosts to whom
packets have been sent recently.
This includes hosts which are both on-link
It contains a level
of indirection to the neighbor cache.
- Prefix List
This is a list of prefixes which define
the set of IPv6 address that are on-link.
This information is maintained on a per
Typically this list is built from Router
Advertisements received from the router.
- Default Router List
A list of routers which will forward
packets on behalf of this host.
This list will again have a pointer to a neighbor
cache entry for the respective router.
A host will use the above data structures
while sending a packet to a host.
Following is the conceptual algorithm for sending
a packet to a unicast destination.
Before a packet is sent out, the next
hop should be determined.
Normally, next hop determination is not done on all packets.
The results of a next hop determination
are stored in the destination cache.
The host should first check the destination
cache for any entry that matches with
the current destination address.
If it finds a match, then it proceeds to step c, below.
If there is no entry for the destination
in the destination cache, a longest prefix match
is made with all prefixes in the prefix list.
If there is a match, the destination
is determined to be on-link and the destination
address will be considered as the next hop.
Otherwise, the next hop is determined from the routing table.
Once the next hop is determined, the
address resolution process and neighbor
unreachability detection are done for the
This process is explained in the next section.
Once the neighbor is known to be reachable,
the packet is sent to that destination.
Address Resolution and Neighbor Unreachability Detection
Address resolution is a process used to
determine the link-layer address of a neighbor.
The IPv6 Address to link-layer
address mapping found through this process
is cached in the Neighbor Cache.
Following are the steps involved in Address Resolution.
First, the neighbor cache is checked for
an entry which matches the current destination
If the entry is not present, the host
sends a Neighbor Solicitation Message to
the solicited-node multicast group.
This multicast address is derived based on the
destination IPv6 address and all nodes with
the particular IPv6 address are required to
join that group.
If a host with the specified IPv6 address
is present in the network, it will reply
this solicitation with a Neighbor Advertisement Message.
On receiving the Neighbor Advertisement,
the node will search for an entry in the neighbor
cache for the sender's IPv6 address.
A new entry is created in the neighbor cache and the
reachability flag is set to REACHABLE.
Once the Address resolution is completed,
neighbor unreachability detection will be performed.
This process depends on the
reachability field of the neighbor cache.
An entry in the neighbor cache can have
any of the following states:
The address resolution is in progress and the link-layer
address of the destination is yet to be determined.
The destination is reachable until recently.
The destination is no longer
known to be reachable, but reachability
detection need not be made until a packet
has to be sent to that destination.
This state is an optimization
that gives additional time for the
upper layer protocols to provide the
A reachability confirmation is actively
requested by repeatedly sending
During neighbor unreachability detection,
the node checks for the state in the
If the state for the destination is REACHABLE,
the packet is sent.
Otherwise, the following steps are taken:
When an address resolution is made
on a destination, an entry is created
in the neighbor cache for that destination
and the reachability state will be set to
If the address resolution fails, the entry is deleted.
When the address resolution passes,
the entry will be filled with the destination's
link-layer address and the state will be set
There is a timer maintained called
the Reachability timer which will expire
the state of an entry in the neighbor cache.
Once this timer expires, the reachability
state changes from REACHABLE to STALE.
When a packet is being sent to a destination
whose state is STALE in the neighbor cache,
the node sets the state to DELAY and starts
a timer associated with that state.
By the time the timer expires if the node received
reachability confirmation, the state is set to
Otherwise, it is set to PROBE.
Once the entry's state is in PROBE, the
node sends unicast neighbor solicitations
to the link-layer address specified in the
If it receives a neighbor advertisement
in response the state is set to REACHABLE.
This solicitation will be sent
repeatedly; the maximum number of times
If the reachability
confirmation is not received after maximum
solicitations, the entry is deleted from
the neighbor cache and the address resolution
is done again.
Entries in the neighbor cache can
also be created as a result of node receiving
unsolicited Neighbor Advertisements, Router
Advertisements and Router Solicitations, etc.
However, for the entry created under these
circumstances the reachability state will
always be set to STALE.
A router will send a host a redirect message
when it finds that there is a better next-hop
router on the same link.
This is a requirement for a router.
On receiving a router redirect message,
a host should update its destination cache
with the new next hop address.
NDP was developed by the IPng Working Group of
the Internet Engineering Task Force.