Neighbor Discovery in IPv6
Hosts and routers (nodes) use Neighbor Discovery (ND) in IPv6 to determine link-layer addresses of neighbors attached to the link. Hosts use ND to find neighboring routers that can act as a default-gateway.
The ND protocol performs the following tasks and solves the problems faced in IPv4-
1. Router Discovery- hosts locate routers that reside on an attached link.
2. Prefix Discovery- hosts discover the set of address prefixes that define which destinations are on-link (same subnet) for an attached link. Nodes use prefixes to determine if destinations are present on-link, or are reachable through a router.
3. Parameter Discovery- Nodes learn about link-MTU, hop-limit, etc
4. Address Autoconfiguration- Nodes automatically configure an address for an interface
5. Address Resolution- Nodes determine the link-layer address of the destination on-link; no need for ARP
6. Next-hop Determination- Nodes can determine the next-hop to the destination
7. Neighbor Unreachability Detection- Nodes can determine if a neighbor is unreachable
8. Duplicate Address Detection- Nodes can determine that an address it wishes to use is not already in use by another node
9. Redirect- A router can notify a host about a better first-hop router/node to reach a particular destination
Important Definition:
Solicited-node multicast address- A link-local scope multicast address that is computed as a function of the solicited target's address. The function is chosen so that IP addresses that differ only in the high-order bits will map to the same solicited-node address thereby reducing the number of multicast addresses a node must join. The Neighbor Solicitation messages are sent to this multicast address.
Neighbor Discovery (ND) defines 5 different types of ICMPv6 packet types-
1. Router Solicitation (RS)-
IPv6 hosts send RS messages when they want to receive Router Advertisements immediately without waiting for the next interval. The host sends this message so that it can quickly learn the information it needs for configuration.
An RS is an ICMP packet with Type 133. If the host already has an IP address, the source address of RS message is the host address. If the host has no IP address, it uses the unspecified address 0:0:0:0:0:0:0:0 as the source address. The destination is the IPv6 multicast address of "all routers on this subnet" i.e. FF02 :: 2.
2. Router Advertisement (RA)-
Each router periodically multicasts an RA packet advertising its availability. The RA could also be sent in response to an RS message.
An RA is an ICMP packet with Type 134. The source address is the link-local address assigned to the outgoing interface. The destination address is either the source address of the RS message, or multicast address of all nodes on the link FF02 :: 1. The Hop Limit is set to 255. If a node receives an RA with Hop-Limit less than 255, the packet is deemed invalid. Hence, the Hop-Limit of 255 ensures the packet has not traversed through a router.
An RA message has a 1-bit "M" flag known as Managed Address Configuration flag. When set, the hosts use stateful (using a server) protocol for address autoconfiguration in addition to stateless address autoconfiguration.
An RA message also has a 1-bit "O" flag known as Other Stateful Configuration flag. When set, the hosts use stateful protocol for other (non-address) information viz DNS information, etc.
An RA also has a Router Lifetime. It is the lifetime associated with the default router. The maximum value corresponds to 18.2 hours. The lifetime of 0 indicates the hosts should not use this router as a default router. A host receives RAs from multiple routers and builds a list of default routers. If a received RA has lifetime set to 0, the host does not put that router in its default router list.
An RA also contains Reachable Time and Retrans Timer. The Reachable Time (in milliseconds) is the time a node assumes a neighbor is reachable after having received a reachability confirmation. Reachable time 0 means unspecified by this router. The Retrans Timer (in milliseconds) is the time between retransmitted Neighbor Solicitation messages. It is used by address resolution and neighbor unreachability detection algorithms.
Optionally, an RA may also contain Source link-layer address, MTU and Prefix Information. The Source link-layer address is the link-layer address of the outgoing interface through which an RA message is sent. The MTU is sent mainly for links with variable MTUs. The Prefix Information option specify the prefixes that are on-link &/or are used for address autoconfiguration. A router includes all its on-link prefixes, except the link-local prefixes.
3. Neighbor Solicitation (NS)-
NS messages are sent to obtain link-layer addresses of the neighbor, as well as to provide link-layer addresses and to verify reachability to the neighbors. NS messages are multicast when a node needs to resolve an address and unicast when a node needs to verify reachability.
An NS is an ICMP packet with Type 135. The source address is either the address assigned to the outgoing interface, or the unspecified address. The destination address is either the solicited-node multicast address corresponding to the target address, or the unicast address of the neighbor for reachability verification. The Hop-Limit is set to 255 to ensure the packet has not crossed a router. The Target Address field is set to the IP address of the destination.
Optionally, the Source link-layer address may be included in the NS message.
4. Neighbor Advertisement (NA)-
NA messages are sent in response to NS messages, or unsolicited to immediately propagate the new information, such as change in node's link-layer address.
An NA is an ICMP packet with Type 136. The source address is address assigned to the outgoing interface. The destination address is source address of the NS message, or all-nodes multicast address FF02 :: 1. The Hop-Limit is set to 255. The Target Address field is set to the IP address of the NS message originator.
Optionally, an NA message may include Target Link-layer address.
5. Redirect message-
A router sends Redirect message to inform a host of a better first-hop node on the path to a destination. The better first-hop could be a different router, or the destination itself.
A Redirect message is an ICMP packet with Type 137. The source address is the link-local address of the outgoing interface. The destination address is the source address of the packet that triggered the redirect. The Hop-Limit is set to 255.
The Target Address is the IP address of the better first-hop to use for destination address. If the better first-hop is the actual destination, the Target Address is set to the destination IP address itself.
The Destination Address field contains the IP address of the destination which is redirected to the target.
Optionally, a Redirect message may contain Target link-layer address and Redirected Header.
Next-Hop Determination:
The Next-hop determination for a given unicast destination operates as follows-
When sending a packet to a destination, the sender performs the longest prefix match against the prefix list (a list of on-link prefixes) to determine whether the destination is on-link or off-link. If the destination is on-link, the packet's next-hop address is the destination address itself. If the destination is off-link, the sender selects the best default-router from the Default-router list. If the Default-router list is empty, the sender assumes the destination is on-link. The results of next-hop determination are saved in the Destination Cache.
Once the next-hop is determined, its link-layer address is required. The sender checks its Neighbor Cache to find the link-layer address of the next-hop.
Address Resolution:
If the Neighbor Cache has no entry for the neighbor/next-hop, the sender initiates Address Resolution. The sender creates an entry and marks the state to INCOMPLETE. The packets are queued meanwhile. The sender sends Neighbor Solicitation message to the solicited-node multicast address for the IP address in question to obtain the link-layer address. It also sends its link-layer address with the message. The neighbor responds with the link-layer address using the Neighbor Advertisement message. It updates its Neighbor Cache with this link-layer address and marks the state to REACHABLE. The queued packet is transmitted then.
Neighbor Unreachability Detection:
Communication to or through a neighbor may fail due to many reasons like hardware failure, etc. Neighbor Unreachability Detection is used for all paths between hosts and neighboring nodes, including host-to-host, host-to-router and router-to-host communication. It can also be used between router-to-router but usually, the routing protocol does the job.
A neighbor is considered to be reachable if the node has recently received the confirmation that packets sent directly to the neighbor were received by its IP layer. This can be done in one of two ways- 1) hint from upper-layer protocol that the connection is making "forward progress" or 2) receipt of a Neighbor Advertisement in response to a Neighbor Solicitation message.
A connection makes "forward progress" if the packets received from a remote peer can only be arriving if the packets sent to that peer is actually reaching it. For example, in TCP connections, for every packet received, the receiver sends an acknowledgment indicating reachability. If the destination is off-link, the forward progress implies the next-hop router is reachable.
However, in case of UDP where no acknowledgments are sent, the nodes probe the neighbors by sending Neighbor Solicitation messages. If in response they receive Neighbor Advertisement messages, reachability is confirmed. The probes are sent in conjunction with traffic; if no traffic is to be sent, no probes are sent.
Neighbor Cache Entry States-
Duplicate Address Detection:
All nodes perform duplicate address detection before assigning a unicast IP address to an interface. It is performed regardless the IP address is assigned stateful (using a DHCPv6 server), stateless (autoconfiguration using information from a router) or manual configuration. The address to be assigned is called "tentative" while the duplicate address detection mechanism is in progress.
The node sends Neighbor Solicitation message with tentative IP address as the target. The source address of the NS message is the unspecified address, and the destination is the tentative address's solicited-node multicast address.
Any neighbor that is already assigned the address receives the solicited message and replies with a Neighbor Advertisement message. The tentative address is the target of the NA message. The destination is the solicited-node multicast address of the tentative address. If the node receives this NA message, and if the target address is the tentative address of this node's interface address, there is a duplicate address and hence the address should not be used.
Further reading:
1. RFC 2461- Neighbor Discovery in IPv6 http://www.faqs.org/ftp/rfc/pdf/rfc2461.txt.pdf