Section 8.2. RIPng

8.2. RIPng

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.

RIPv1 is defined in RFC 1058, RIPv2 in RFC 2453. RIPng is defined in RFC 2080 (January 1997).

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 r_i advertised by B. The next hop address for route r_i is Router B. For each route r_i, 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 r_i is discarded:

Route r_i is new and reachable.: The route is added as a new entry to the routing table. The time-out timer is set to zero, and the Route Change flag is raised.
Route r_i is already in the routing table, and the next hop address corresponds to the one in the routing table.: The route has just been refreshed. The time-out timer is reset to zero. If the metric has changed, it is updated and the Route Change flag is raised.
Route r_i is already in the routing table, but the next hop address is different and the metric is smaller than the one in the routing table.: A different path to the route has been found. The metric and next hop address are updated. The time-out timer is set to zero, and the Route Change flag is raised.
Route r_i is already in the routing table, but the next hop address is different and the metric is equal to the one in the routing table.: If the routing process allows for multiple equal-cost paths to the same destination in the routing table, the route is treated as a new entry (see earlier item). If the routing process does not provide for multiple equal-cost paths, route r_i is discarded. Multiple equal-cost paths allow for load sharing of IPv6 traffic among multiple paths. The algorithm for distributing traffic among these paths is at the discretion of the routing process itself, normally based on the source and destination IPv6 addresses to ensure that datagrams between two particular systems always take the same path.

The next hop address of r_i 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:

The RIPng diameter is limited.: The longest path to any IPv6 route is limited to a metric of 15 when propagated with RIPng. Normally this corresponds with a path over a maximum of 15 hops. The protocol allows for larger costs to be assigned to any link, limiting the number of hops even further. Routes with a metric of 16 or greater are unreachable.
Routing loops can cause high convergence time.: When IPv6 routes that are no longer valid are being propagated in a looped environment, RIPng continues to increase the metric by one. The routes would be passed around indefinitely ("counting to infinity"). The mechanism of limiting the metric to 16 prevents this from happening. The routes will circle until they reach the maximum metric and are eventually eliminated.
The metric does not reflect line speed.: RIPng uses a fixed metric normally set to one for each link crossed. A route cannot be chosen based on bandwidth or real-time parameters such as measured delay, load, or reliability.

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.

8.2.3.1. 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 .

8.2.3.2. Split horizon, with or without poison reverse

Let's assume route r₁ is directly connected to router A, as shown in Figure 8-3.

Figure 8-3. Convergence of route r₁ without split horizon

Router A advertises r₁ to its neighbor, Router B, with a cost of 1. Router B adds 1 to the cost and lists r₁ in its routing table using Router A as the next hop. Now r₁ goes down. Router A poisons r₁ and waits for the update timer to expire before advertising r₁ to B with a cost of 16. In the meantime, however, Router B advertises r₁ back to A with a cost of 2. Router A changes the entry for r₁ using B as the next hop with a metric of 3. Now Router A advertises r₁ with a cost of 3 (not 16) to Router B. Router B adds 1 to the cost and lists r₁ in its routing table with a cost of 4. The routers send r₁ back and forth, each time raising the cost by 1 until counting to infinity strikes and both reach a cost of 16, declaring r₁ 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).

8.2.3.3. 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:

Command (1 byte): 1 = Request: A request message is asking the responding system to send all or part of its routing table.
2 = Response: A response message containing all or part of the sender's routing table. It may be sent as a response to a previous request or as an unsolicited response used in periodic or triggered routing updates.
Version (1 byte): The version field is set to a value of 1.
Route Table Entry (RTE) (20 bytes each): The RIPng header is followed by one or more Route Table Entries using the format depicted in Figure 8-5.

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:

number of RTEs = Integer value ((MTU - length of IPv6 headers - length of UDP header - length of RIPng header) / size of RTE)

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 r_i using Router C as its next hop. Router A could advertise r_i to B with the Next Hop address of Router C. Router B can now forward traffic for r_i 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 ::).

8.2.6. Timers

RIPng implements different timers to control updates of the routing information. The name and purpose of these timers are specified in the following list:

Update timer: By default, every 30 seconds the RIPng process wakes up on each interface to send an unsolicited response message to the neighboring routers. This response contains the entire routing table known to the RIP process, except for routes that follow the split horizon rule. One or more response messages may be needed. This timer is kept for each router interface.
Timeout timer: Each time a route entry is updated, the timeout time for this route entry is reset to zero. If the route entry reaches 180 seconds (default value) without another update, it is considered to have expired. The metric is set to 16, and the garbage collection process begins. In addition, the Route Change flag is raised to indicate a change. The output process uses this flag to trigger an update. This timer is kept for each routing table entry.
Garbage-collection timer (sometimes referred to as hold-down timer): This timer is set for 120 seconds for each route entry that has timed out (see timeout timer) or has been received with a metric of 16. Only upon expiration of this timer will the route entry finally be removed from the routing table. If a new update to this route arrives before the garbage collection timer expires, the route is replaced and the garbage collection timer is cleared. This timer is kept for each routing table entry.

8.2.7. Packet Processing

Let's look at how the router processes incoming and outgoing RIPng messages.

8.2.7.1. 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.

Table 8-1. RIPng request messages
Request type	IPv6 Source address	IPv6 Destination address	Source UDP port	Destination UDP port	Use split horizon in response?
General	Link-local address of the requestor's sending interface	`ff02::9` (multicast)	RIPng port (521)	RIPng port (521)	Yes
Specific	Global or local unicast address of the requestor	Global or local unicast address of the queried router	Any except the RIPng port	RIPng port (521)	No

RFC 2080 still uses the term "site-local address" instead of "local address." Site-local addresses have been deprecated in the meantime. For more information, refer to the sections in Chapter 3 about IPv6 addressing.

8.2.7.2. 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.

Table 8-2. RIPng response messages
Request type	IPv6 Source address	IPv6 Destination address	Source UDP port	Destination UDP port
Unsolicited (periodic update or triggered update)	Link-local address of the sending interface	`ff02::9` (multicast)	RIPng port (521)	RIPng port (521)
Solicited (answer a request)	Link-local address (general request), global or local address (specific request)	Source IPv6 address of the request message	RIPng port (521)	Source UDP port of the request message

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.