Common Data Structures, Routines and Global Variables (IPv6 Unicast Routing Protocols)

This section introduces data structures that are commonly used in the route6d implementation and are frequently referred to in subsequent sections. The description in this section will also provide a run-time image about how a particular network configuration and command line options map to these data structures.

Structures for RIPng Messages

Listing 1-10 defines the rip6{} structure, the common leading part of RIPng messages.

Listing 1-10

TABLE 1-8

Name	Description
-N if1[,if2...]	Do not listen to or advertise route information from/to interfaces specified by the parameter.
-L prefix/prefixlen,if1[,if2...]	Accept route information specified as prefix/prefixlen from interface if1 and other interfaces if any other interfaces are specified. The prefix information ::/0 is treated as a default route, that is, it means the default route, rather than any route information, is accepted.
-T if1[,if2...]	Advertise only the default route toward if1 and other interfaces if specified.
-t tag	Bind the route tag tag to originated route entries. tag can be a decimal, octal prefixed by 0 or hexadecimal value prefixed by 0x.
-A prefix/prefixlen,if1[,if2...]	Aggregate route entries covered by prefix/prefixlen and advertise the prefix when sending route information toward the specified network interfaces.
-S, -s	Advertise statically defined routes that exist in the kernel routing table before the route6d daemon is launched. -s is the same as -S except that the split horizon algorithm does not apply.
-h	Disable the split horizon algorithm.
-l	Exchange site-local prefixes. With this switch, route6d daemon exchanges site-local prefixes, assuming all of the prefixes belong to the same site.

Refer to Figure 1-9 rip6_cmd maps to the command field; rip6_vers maps to the version field; rip6_res1 maps to the "must be zero" field. The rip6un{} union, in particular, the rip6_nets macro definition maps to the first RTE contained in the message. This makes sense because a valid RIPng message has at least one RTE. If a request message asks for specific routes, then there would be one or more RTEs corresponding to the required routes; if it asks for the entire routing table, then there will be exactly one RTE, with the destination prefix being ::/0 and the metric being 16, meaning infinity. Also, a valid response message must have at least one RTE.

The netinfo6{} structure used in rip6{} as a single RTE is shown in Listing 1-11.

Listing 1-11

This structure is a straightforward representation of the RTE format as shown in Figure 1-10: rip6_dest maps to the IPv6 prefix field; rip6_tag maps to the route tag field; rip6_plen maps to the prefix length field; and rip6_metric maps to the metric field.

route6d’s Routing Table

The riprt{} structure, as defined in Listing 1-12, is a single route entry of route6d’s internal routing table (i.e., RIB).

Listing 1-12

The current route6d implementation manages its routing table using a simple linked list(*) whose head is pointed to by a global variable riprt. rrt_next links the routing table entries. rrt_same is an unused member. rrt_info is a netinfo6{} structure that contains the actual route information (Listing 1-11). rrt_gw holds the next hop address. rrt_flags contains the kernel routing entry flags such as RTF_UP and RTF_HOST. rrt_rflags may take on one of the RRTF_???? flags described in Listing 1-13 below. rrt_t stores the time when the route was created or refreshed; for a static route entry rrt_t is set to 0. How the route lifetime and hold-down times are manipulated based on rrt_t is covered in detail in Section 1.13.5. rrt_index has the index of the interface on which the route was obtained.

(*) This singly linked list is inefficient when performing a route search with a moderate number of route entries. The simple list also makes route aggregation difficult to accomplish. Although the overhead may be negligible for the typical scale of network where RIPng is performed, it would generally be better to use more efficient data structures such as a tree-based table.

Listing 1-13

RRTF_AGGREGATE marks a route entry as the aggregate route to be advertised. RRTF_NOADVERTISE marks a route entry not to be advertised. RRTF_NH_NOT_LLADDR notes that a route entry contains a next hop address that is not a link-local address. RRTF_SENDANYWAY is not set in the rrt_rflags field of the riprt{} structure. Instead, when necessary, this flag is specified as an argument to the ripsend() function (Section 1.13.4) to indicate that a response message is generated in answer to a request and the split horizon algorithm should be disabled. RRTF_CHANGED marks a route entry as having been modified recently. A triggered update includes only routes that have the RRTF_CHANGED flag set.

Figure 1-46 shows an example image of route6d’s routing table for the network topology given in Figure 1-41. It is assumed all routers exchange routes using RIPng; router A advertised the default route (::/0) with a metric of 1 at 15:32; router B advertised the network prefix of the lower-most link (2 001:db8:0:2000::/64) with a metric of 1 two minutes later. Also assume the FreeBSD router, running route6d, is processing the RIPng response message from router B.

The first riprt{} entry is for the route being processed. The route6d daemon adds the metric of the receiving link to the advertised metric, and sets the rip6_metric member to the result value. Since this route is newly advertised, the RRTF_CHANGED flag is set in the rrt_rflags member, prompting a triggered update. The rrt_t member is set to the current time, 15:32.4 It should also be noted that the gateway address (rrt_gw) embeds the link identifier (2) in the address. This is necessary because this address is passed to the kernel via the routing socket, which requires the embedded form as explained in Section 1.8.1.

The second entry is for the default route advertised by router A. The same description for the first entry naturally applies to this entry, but the rrt_rflags member is cleared because this route entry has already been installed and advertised as an update.

The last entry is the interface direct route for the local link prefix of 2001:db8:0:1000::/64. The route6d daemon makes this entry on startup time by examining each local address and its prefix (this procedure is not described in this topic). The rrt_gw member is set to the local address for the daemon’s convenience. The metric of this route is set to 1 by default, which is used as the metric of the route in RIPng response messages sent from this router. An interface direct route is considered a static route, so the rrt_t member is set to 0.

Structures for Local Interfaces

The route6d daemon builds a list of local network interfaces at startup time and uses the parameters of each interface in the RIPng protocol operations. The ifc{} structure, as defined in Listing 1-14, describes the per interface data structure maintained in route6d for this purpose.

FIGURE 1-46

A routing table snapshot of route6dfor the topology shown in Figure 1-41. The RTF_ and RRTF_prefixes for the values of the rrt_flags and rrt_rflags members are omitted for brevity.

Listing 1-14

The ifc_name member contains the name of the interface, e.g., fxp0. ifc_index contains the interface index that was assigned by the kernel at the time when it was installed into the system. ifc_mtu contains the link MTU value, for example, 1500 is the typical value for Ethernet interfaces.

The ifc_next member points to the next ifc{} entry of the interface list. The head entry is pointed to by a global variable named ifc.

The ifc_metric member contains the additional cost of accessing the network; in the route6d implementation, the metric for a route is calculated as the sum of the hop count and the value of ifc_metric.

The ifc_flags member contains the interface flags, such as IFF_UP, indicating the interface is operational. IFF_MULTICAST indicates the interface is capable of receiving and transmitting multicast packets. On the other hand, ifc_cflags defines implementation-specific attributes of this interface. The only flag defined for ifc_cflags is IFC_CHANGED, which is used to indicate that a route associated with the interface (e.g., a direct route corresponding to a local address) has been modified recently and a RIPng update may need to be sent.

The ifc_mylladdr member stores a link-local address of the interface. This is used to detect the case where an incoming RIPng message is sent from this local router. ifc_ripsin is a template socket address structure of the all-rip-routers multicast group address (ff02::9)

and is used to send a RIPng response message to this group. Since this address has a link-local scope and different interfaces usually belong to different links, this structure is maintained per interface basis. The link index is set in this structure on initialization.

The ifc_filter member contains a list of filters that are configured for this interface. Section 1.11.4 explains the iff{} structure in more detail. ifc_addr contains a list of IPv6 addresses configured on this interface. ifc_joined is a flag variable. When set, it indicates route6d has joined the all-rip-routers multicast group on the given interface.

The ifac{} structure constructs the address list linked in the ifc{} structure. The definition of this structure is shown in Listing 1-15.

Listing 1-15

Each ifac{} structure holds one interface address. ifa_conf is a back pointer to ifc{} to which it belongs. ifa_next points to the next interface address. ifa_addr contains the actual interface address. ifa_raddr contains the address of the remote node if the interface referenced by ifa_conf is a point-to-point interface. ifa_plen has the prefix length for ifa_addr.

Figure 1-47 depicts the relationship among these data structures for the FreeBSD router shown in Figure 1-41. It is assumed in this figure that both the ne0 and ne1 interfaces have a link-local address fe80::2. This configuration is valid because these interfaces belong to different links.

It should also be noted that the interface list contains an ifc{} structure for a loopback interface lo0. This interface is not used for normal RIPng protocol operation, so most of the structure members are omitted in the figure. But it may be used as the imaginary outgoing interface for route aggregation (which is not described in this topic), and must be configured in this list.

route6d Route Filter Entry

The iff{} structure, shown in Listing 1-16, describes a route filter configured for a given interface.

Listing 1-16

The iff_type member specifies the type of filter, which is described by a single ASCII character corresponding to a command line option shown in Table 1-8; the supported filter types are summarized in Table 1-9.

FIGURE 1-98

Interface and address list structures for the router shown in Figure 1-41. Some flags of the ifc_flags member are omitted for brevity.

TABLE 1-9

iff_type	route6d option	Description
A	-A	Route aggregation filter
L	-L	Inbound route filter
O	-O	Outbound route filter

The iff_addr and iff_plen members define the IPv6 prefix to which this filter entry applies. iff_next points to the next filter.

For example, consider in Figure 1-41 that the administrator wants to apply the following route filtering policies:

• Only the default route is accepted on interface ne0.

• Only routes that belong to prefix 2001:db8::/48 are advertised on interface ne0. Then the route6d daemon would be invoked as follows:

Figure 1-48 shows the internal data structures for this configuration.

Subroutines and Global Variables

The route6d implementation relies on various utility functions and global variables, and some of them are frequently referred to in the code narrations in the next couple of sections. This subsection provides a short summary of these for convenience. Table 1-10 summarizes subroutines commonly used in the implementation; Table 1-11 summarizes some major global variables; Table 1-12 provides the description of supporting macro functions.

FIGURE 1-48

TABLE 1-10

Function name	Function prototype and description
addroute()	int addroute(struct riprt rrt, const struct in6_addr gw, struct ifc *ifcp);
	Installs a route6d’s route entry pointed to by rrt into the kernel via a routing socket. gw actually points to rrt->gw but is passed as a separate constant parameter so that it not modified in this function. ifcp is only used for logging. Returns 0 on success; otherwise returns —1.
delroute()	int delroute(struct netinfo6 np, struct in6_addr gw);
	Deletes a route for the prefix identified by np from the kernel via a routing socket command. gw is also passed to the kernel as a hint, but it does not have any effect because the BSD kernel does not use this information to delete a route. Returns 0 on success; otherwise returns —1.
applyplen()	void applyplen(struct in6_addr *ia, int plen); Zero-clears the rightmost 128—plen bits of the given IPv6 address ia. For example, if ia is 2001:db8:1:2::abcd and plen is 64, ia is modified to 2001:db8:1:2:: in this function.