History is repeating itself. Just as with IPv4, the first dynamic routing protocol to reach productivity is RIP, in this instance called RIPng. RIPng is a routing protocol based on a distance-vector algorithm known as the Bellman-Ford algorithm. I outline the theory and math behind this algorithm briefly in this section. Most of the concepts for RIPng have been taken from RIPv1 and RIPv2, which have been implemented for IPv4 for quite some time.
8.2.1. Distance-Vector Algorithm for RIPng
RIPng uses a simple mechanism to determine the metric (cost) of a route. It basically counts the number of routers (hops) to the destination. Each router counts as one hop. Routes with a distance greater than or equal to 16 are considered to be unreachable. The router periodically distributes information about its routes to its directly connected neighbors using RIPng response messages. Upon receiving RIPng response messages from its neighbor, the router adds the distance between the neighbor and itself (usually one, as in one hop) to the metric of each route received. The router then processes the newly received route entry using the Bellman-Ford algorithm.
Figure 8-2 provides a closer look at the Bellman-Ford algorithm, and its implementation for RIPng is explained below.
Figure 8-2. The Bellman-Ford algorithm
The RIPng process within each router maintains specific RIPng parameters for each route. To illustrate the distance vector algorithm, two of these parameters are briefly explained here. They are the route change flag, indicating a change of information of the corresponding route, and the time-out timer, indicating the lifetime of the route. The periodic updates prevent the route from expiring. Let's assume Router A and Router B are running RIPng. Router A receives a routing update from Router B and has already added the distance of 1 to each route ri advertised by B. The next hop address for route ri is Router B. For each route ri, the router steps through the algorithm depicted in Figure 8-2. According to Figure 8-2, the routing table will be updated if the following criteria are true; otherwise, route ri is discarded:
The next hop address of ri is taken either from the information within the routing update message or from the source IPv6 address of the RIPng packet. In this case it was Router B. See the "Next Hop Information" section for more information.
When the routers are first initialized, they know only their directly connected routes. This information is passed to all neighbors, processed, and then distributed to their neighbors. Eventually, all IPv6 routes are known by all routers. The routers keep sending response messages periodically to prevent valid routes from expiring. The time it takes for all routers to learn about the new routes is called convergence time.
8.2.2. Limitations of the Protocol
RIPng, like the earlier versions of RIP, is primarily designed for use as an IGP in networks of moderate size. The limitations specified for RIP versions 1 and 2 apply to RIPng as well. They are described in the following list:
8.2.3. Changes in Topology and Preventing Instability
A change in topology happens when a route is newly added or has gone down. Newly added routes are advertised within the next response message sent by the router having the direct connection to that route. Its neighbors process the route and pass it on to their neighbors. Eventually, all routers know about the newly added route.
What happens if a route goes down or a router crashes? These routes will eventually time out, as they are no longer being advertised. The questions are just how long this process will take and whether this time is acceptable for the network. To keep the convergence time to a minimum, several measures can be introduced.
18.104.22.168. Route poisoning and the hold-down timer
If an interface goes down on a router, the router does not remove the route(s) associated with that interface immediately. Instead, the router keeps the route in the routing table and raises the metric to 16 (unreachable). A garbage-collection timer, also known as a hold-down timer, determines how long the router keeps this unreachable route in the routing table. The route is now advertised to the neighbors with a metric of 16. The neighbors are running a hold timer as well, so they keep the route in the routing table to inform their respective neighbors about the invalidity of the route. This process is called route poisoning .
22.214.171.124. Split horizon, with or without poison reverse
Let's assume route r1 is directly connected to router A, as shown in Figure 8-3.
Figure 8-3. Convergence of route r1 without split horizon
Router A advertises r1 to its neighbor, Router B, with a cost of 1. Router B adds 1 to the cost and lists r1 in its routing table using Router A as the next hop. Now r1 goes down. Router A poisons r1 and waits for the update timer to expire before advertising r1 to B with a cost of 16. In the meantime, however, Router B advertises r1 back to A with a cost of 2. Router A changes the entry for r1 using B as the next hop with a metric of 3. Now Router A advertises r1 with a cost of 3 (not 16) to Router B. Router B adds 1 to the cost and lists r1 in its routing table with a cost of 4. The routers send r1 back and forth, each time raising the cost by 1 until counting to infinity strikes and both reach a cost of 16, declaring r1 invalid. This will take quite some time, however. The core problem lies in the fact that Router B advertises routes learned from A back to A.
Split horizon prevents this scenario from happening. With split horizon, a router never advertises a route back over its next hop interface. An additional option is split horizon with poison reverse. With this option, a router always advertises a route back over its next hop interface with a metric of 16. In the very unlikely situation that both Routers A and B have the same route pointing to each other, the routers don't have to wait for a timeout to eliminate this route, because poison reverse invalidates each of them immediately. Poison reverse can, however, have the disadvantage of increasing the size of routing messages, especially if many destinations have to be advertised back as poisoned.
There are very few situations in which split horizon (with or without poison reverse) cannot be used at all. If there is a point-to-multipoint (also called hub-and-spoke) topology using a single common IPv6 network, split horizon prevents the spoke routers from learning routes advertised by other spoke routers. Split horizon must be turned off at the central router (the hub router).
126.96.36.199. Triggered updates
Any changes in the routing table have to wait to be advertised until the update timer has expired. Triggered updates speed up the process by allowing the changed route entry to be advertised almost immediately. A very small hold timer is introduced before sending the update. Because only the changes are advertised, regular periodic updates need to stay in place.
All these measures speed up convergence, but the world is not perfect. Erroneous information may always come back over larger loops, especially within a large network with a topology containing many loops. The process of counting to infinity with a maximum metric will, however, always prevail to eliminate the erroneous information.
8.2.4. RIPng Message Format
RIPng is a UDP-based protocol using UDP port number 521; let's call it the RIPng port. The RIPng routing process always listens to messages arriving on this port. With the exception of specific requests, all RIPng messages set the source and destination port to the RIPng port. Specific requests are discussed later in this chapter.
The RIPng message format is shown in Figure 8-4.
Figure 8-4. RIPng message format
The fields of the RIPng message are explained in the following list:
Figure 8-5. Format of a Route Table Entry
Each RTE describes the route to be advertised by using the IPv6 Prefix (16 bytes) and its Prefix Length (1 byte). The metric field (1 byte) contains the metric used by the sender for this route. A valid metric has a value between 1 and 15. A metric of 16 describes the route as unreachable by the sending router.
Each RTE contains a Route Tag field as well. It may be used to carry additional information about a route learned from another routing protocole.g., BGP. A router importing external routes into RIPng may set this tag. RIPng will preserve and redistribute this tag within its routing domain. Information within this tag can be used to redistribute the route out of the RIP domain. RIPng itself makes no use of this tag.
The number of RTEs within a single RIPng message depends on the physical MTU (Maximum Transfer Unit) of the medium between two neighboring routers. The formula is as follows:
8.2.5. Next Hop Information
If you are familiar with RIPv2, you probably miss the field for the next hop address. Not to worry: RIPng provides this feature too. With RIPv2, each entry has a designated field specifying the Next Hop address. This would not be very economical for RIPng because it would nearly double the size of each RTE. As shown in Figure 8-6, a specially constructed RTE, the Next Hop RTE, is introduced. It contains the next hop's IPv6 address. All subsequent RTEs use this IPv6 address for the next hop identification until the end of the message has been reached or another next hop RTE is encountered.
Figure 8-6. The Next Hop RTE
The Next Hop RTE is identified by a value of 0xFF in the metric field of the RTE. The IPv6 address within the RTE is now identified as the Next Hop IPv6 address to be used by the subsequent RTE. The route tag and the prefix length are set to 0 on sending and ignored on reception.
Specifying a value of 0:0:0:0:0:0:0:0 (or simply ::) in the prefix field of the Next Hop RTE indicates that the Next Hop IPv6 address should be set to the source IPv6 address of the RIPng message. The purpose of naming a specific next hop is to eliminate unnecessary routing hops. For example, Routers A, B, and C are directly connected on a common subnet. Router C does not run RIPng. Assume that Router A somehow knows a route ri using Router C as its next hop. Router A could advertise ri to B with the Next Hop address of Router C. Router B can now forward traffic for ri directly to Router C, therefore avoiding the unnecessary hop through Router A.
The next hop IPv6 address must always be a link-local address (starting with a prefix of FE80). If there is no Next Hop RTE, or if the received next hop address is not link-local, it should be considered 0:0:0:0:0:0:0:0 (or simply ::).
RIPng implements different timers to control updates of the routing information. The name and purpose of these timers are specified in the following list:
8.2.7. Packet Processing
Let's look at how the router processes incoming and outgoing RIPng messages.
188.8.131.52. Request message
A request message asks a router to respond with all or part of its routing table by specifying the requested RTE. The incoming request is processed as follows.
If there is exactly one RTE with a prefix of zero, a prefix length of zero, and a metric of 16, the request is for the entire routing table, and the router responds by sending the entire routing table. Figure 8-7 shows a trace of such a request message.
Figure 8-7. RIPng request message asking for the entire routing table
Otherwise, the request message is processed one RTE at a time. If the RTE's corresponding prefix is found in the routing table, the RTE's metric is placed into the metric field of the RTE; otherwise, a metric of 16 is placed into the metric field, indicating that the route is unknown. Once all RTEs have been processed, the command field in the RIPng header is changed to "response," and the newly formed response message is sent back to the requestor.
There are two types of request messages, General and Specific, which are handled differently by the receiving router.
A General Request is sent by a router that has just come up and wants to fill its routing table quickly. The router sends out a General Request message asking all directly connected neighbors to send their entire routing tables. The neighbors each reply with a response message that contains their entire routing tables using the split horizon rule.
A Specific Request message is sent by a monitoring station asking for all or part of the routing table. The queried router replies to the requestor by sending the requested information from its routing table. Split horizon is not used, because it is assumed that the requestor is using the requested information for diagnostic purposes only.
Table 8-1 summarizes the characteristics of the two types of requests.
184.108.40.206. Response message
A response message carries routing information to be processed by the receiving router using the Bellman-Ford Algorithm (see the earlier section "Distance-Vector Algorithm for RIPng"). A response message is accepted by a router only if the IPv6 Source address is a link-local address of a directly connected neighbor and the UDP source and destination ports are set to the RIPng port. In addition, the hop limit value must be equal to 255. This indicates that the response message has not traveled over any intermediate node.
Once the response message is accepted, each RTE must be checked for its validity. The test includes the prefix itself (not a multicast or link-local address), the prefix length (between 0 and 128), and the metric (between 1 and 16). If the RTE is accepted, the metric of the incoming interface is added to the metric of the RTE. The RTE is now passed to the Bellman-Ford process, as described in the earlier section "Distance-Vector Algorithm for RIPng." Figure 8-8 shows a trace of a response message.
Figure 8-8. RIPng response message
These rules for receiving and validating a response message do not apply for a response to a specific query. The hop limit value may be less than 255, and the source IPv6 address is not a link-local address. The diagnostic station uses the received RTE(s) not for routing, but to provide input into its diagnostic software. It is entirely up to the implementer of such software to determine the validity of a response message.
There are two types of response messages: Unsolicited and Solicited. An Unsolicited Response message is sent by a periodic or triggered update process. The periodic update process examines the entire routing table on expiration of the Update Timer on any given interface. The triggered update process wakes up as soon as the Route Change flag is raised and examines only routes with the Route Change flag set. Both processes then proceed with the following: if the examined route entry has a link-local address or should not be used because of split horizon processing, skip it. Otherwise, put the prefix, prefix length, and metric into the RTE, and put the RTE into the response message. If the maximum MTU has been reached, send the packet and build a new packet.
A Solicited Response message is sent as a response to a request message.
Table 8-2 summarizes the characteristics of the two types of responses.
Sending the Unsolicited Response message to the multicast address ensures that the response message reaches all neighbors on any particular directly connected network. There are cases in which this may not worke.g., on a non-broadcast-capable network. A static list of all neighbors on such a network must be configured to send the messages directly to each neighbor.
8.2.8. Control Functions and Security
RIPng does not provide specifications for administrative control. However, experience with existing RIP implementations suggests that such controls may be important. Administrative controls are filters that allow or disallow certain routes to be advertised or received. In addition, a list of valid neighbors could be specified, and a router would accept or announce routes only to neighbors on this list. These filters can be used to change the update behavior so it complies with routing policies set within an autonomous system. Again, RIPng does not need such controls to function, but it is strongly recommended that the implementer provide such controls. Cisco Systems, for example, implements RIPng distribution lists, and Nortel implements RIPng Announce and Accept Policies.
RIPng provides no encryption option. To ensure integrity and authentication of routing exchanges, it must rely on the IP Authentication Header and the IP Encapsulating Security Payload. In practice, this method is hardly ever used.