The routing socket interface to the kernel forwarding table was introduced in BSD 4.3 Reno, widely distributed in BSD 4.3 Net/2 and improved in BSD 4.4. This interface is simply a socket, similar to a UDP socket, on which the kernel and GATED exchange messages. It has several advatages over the ioctl() interface:

• Variable subnet masks
  The network mask is passed to the kernel explicitly. This allows different masks to be used on subnets of the same network. It also allows routes with masks that are more general than the natural mask to be used. This is known as classless routing.
• Two way interface
  Not only is GATED able to change the kernel forwarding table with this interface, but the kernel can also report changes to the forwarding table to GATED. The most interesting of these is an indication that a redirect has modified the kernel forwarding table; this means that GATED no longer needs to monitor ICMP messages to learn about redirects. Plus, there is an indication of whether the kernel processed the redirect, GATED can safely ignore redirect messages that the kernel did not process.
• Updates visible
  Changes to the routing table by other processes, including the route command are received via the routing socket. This allows GATED to insure that the kernel forwarding table is in sync with the routing table. Plus it allows the system administrator the ability to do some operations with the route command while GATED is running.
• Changes supported
  There is a functioning change message that allows routes in the kernel to be atomically changed. Some early verions of the routing socket code had bugs in the change message processing. There are compilation time and configuration time options that cause delete and add sequences to be used in lieu of change messages.
• Expandable
  New levels of kernel/GATED communications may be added by adding new message types.

When GATED starts up it reads the kernel forwarding table and installs corresponding routes in the routing table. These routes are called remnants and are timed out after a configured interval (which defaults to 3 minutes), or as soon as a more attractive route is learned. This allows forwarding to occur during the time it takes the routing protocols to start learning routes.

There are three main methods for reading the forwarding table from the kernel:

• Reading forwarding table via kmem
  On many systems, especially those based on BSD 4.3, GATED must have knowledge of the kernel's data structures and poke around in the kernel to read the current state of forwarding table. This method is slow and subject to error if the kernel forwarding table is updated while GATED is in the middle of reading it. This can happen if the system administrator uses the route command, or an ICMP redirect message is received while GATED is starting up.
  Due to an oversight some systems, such as OSF/1, which are based on BSD 4.3 Reno or later, do not have the getkerninfo() system call described below which allows GATED to read routes from the kernel without know about kernel internal structures. On these systems it is necessary to read the kernel radix tree from the kernel by poking around in kernel memory. This is even more error prone than reading the hash based forwding table.
• Reading the forwarding table via getkerninfo or sysctl
  Besides the routing socket, BSD 4.3 Reno introduced the getkerninfo() system call. This call allows a user process (of which GATED is one) to read various information from the kernel without knowledge of the kernel data structures. In the case of the forwarding table, it is returned to GATED atomically as a series of routing socket messages. This prevents the problem associated with the forwarding table changing while GATED is in the process of reading it.
  BSD 4.4 changed the getkerninfo() interface into the sysctl() interface, which takes different parameters, but otherwise functions identically.
• Reading the forwarding table via OS specific methods
  Some operating systems define their own method of reading the kernel forwarding table.

The kernel support subsystem of GATED is resposible for reading the status of the kernel's physical and protocl interfaces periodically. GATED detects changes in the interface list and notifies the protocols so they can start or stop instances or peers. The interface list is read one of two ways:

• Reading the interface list with SIOCGIFCONF
  On systems based on BSD 4.3, 4.3 Reno and 4.3 Net/2 the SIOCGIFCONF ioctl interface is used to read the kernel interface list. Using this method a list of interfaces and some basic information about them is return by the SIOCGIFCONF call. Other information must be learned by issuing other ioctls to learn the interface network mask, flags, MTU, metric, destination address (for point-to-point interfaces) and broadcast address (for broadcast capable interfaces).
  GATED reads re-reads this list every 15 second looking for changes. When the routing socket is in use, it also re-reads it whenever a messages is received indicating a change in routing configuration. Receipt of a SIGUSR2 signal also causes GATED to re-read the list. This interval may be explicitly configured in the interface configuration.
• Reading the interface list with sysctl
  BSD 4.4 added the ability to read the kernel interface list via the sysctl system call. The interface status is returned atomically as a list of routing socket messages which GATED parses for the required information.
  BSD 4.4 also added routing socket messsages to report interface status changes immediately. This allows GATED to react quickly to changes in interface configuration.
  When this method is in use, GATED re-reads the interface list only once a minute. It also re-reads it on routing table changes indications and when a SIGUSR2 is received. This interval may be explicitly configured in the interface configuration.

Later version of the getkerninfo() and sysctl() interfaces return the interface physical addresses as part of the interface information. On most systems where this information is not returned, GATED scans the kernel physical interface list for this information for interfaces with IFF_BROADCAST set, assuming that their drivers are handled the same as Ethernet drivers. On some systems, system specific interfaces are used to learn this information.

The interface physical addresses are useful for IS-IS, for IP protocols, they are not currently used, but may be in the future.

B.16.6 Reading Kernel Variables

At startup, GATED reads some special variables out of the kernel. This is usually done with the nlist (or kvm_nlist) system call, but some systems use different methods.

The variables read include the status of UDP checksum creation and generation, IP forwarding and kernel version (for informational purposes). On systems where the routing table is read directly from kernel memory, the root of the hash table or radix tree routing table is read. On systems where interface physical addresses are not supplied by other means, the root of the interface list is read.

B.16.7 Special Route Flags

The later BSD based kernel support the special route flags described here:

• RTF_REJECT
  Instead of forwarding a packet like a normal route, routes with RTF_REJECT cause packets to be dropped and unreachable messages to be sent to the packet originators. This flag is only valid on routes pointing at the loopback interface.
• RTF_BLACKHOLE
  Like the RTF_REJECT flag, routes with RTF_BLACKHOLE cause packets to be dropped, but unreachable messages are not sent. This flag is only valid on routes pointing at the loopback interface. )
• RTF_STATIC
  When GATED starts, it reads all the routes currently in the kernel forwarding table. Besides interface routes, it usually marks everything else as a remnant from a previous run of GATED and deletes it after a few minutes. This means that routes added with the route command will not be retained after GATED has started.
  To fix this the RTF_STATIC flag was added. When the route command is used to install a route that is not an inteface route it sets the RTF_STATIC flag. This signals to GATED that said route was added by the systems administrator and should be retained.

kernel { options [ nochange ] [ noflushatexit ] [ remnantholdtime time] ; routes number ; flash [ limit number ] [ type interface | interior | all ] ; background [ limit number ] [ priority flash | higher | lower ] ; traceoptions trace_options ; } ;

Here,

• options
  Specifies kernel options. Valid options are:

  nochange	On systems supporting the routing socket this insures that changes operations will not be performed, only deletes and adds. This is useful on early versions of the routing socket code where the change operation was broken.
  noflushatexit	During normal shutdown processing GATED deletes all routes from the kernel forwarding table that do not have a retain indication. The noflushatexit option prevents route deletions at shutdown. Instead, routes are changed and added to make sure that all the routes marked with retain get installed. This is handy on systems with thousands of routes. Upon startup GATED will notice which routes are in the kernel forwarding table and not have add them back.
  remnantholddimte time	Normally remnant routes read from the kernel forwarding table at startup are timed out in three minutes or as soon as they are overridden. This option allows the interval to be configured to a value between zero and 15 minutes. Setting it to zero causes these routes to be deleted immediately.

• routes
  Specifies the routes number. On some systems kernel memory is at a premium. With this parameter a limit can be placed on the maximum number of routes GATED will install in the kernel. Normally GATED adds/changes/deletes routes in interface/internal/external order, i.e. it queues interface routes first, followed by internal routes, followed by external routes, and processes the queue from the beginning. If a this parameter is specified and the limit is hit, GATED does two scans of the list instead. On the first scan it does deletes, and also deletes all changed routes, turning the queued changes into adds. It then rescans the list doing adds in interface/internal/external order until it hits the limit again. This will tend to favor internal routes over external routes. The default is not to limit the number of routes in the kernel forwarding table.
• flash
  Specifies that a route has changed. The process of notifying the protocols is called a flash update. The kernel forwarding table interface is the first to be notified. Normally a maximum of 20 interface routes may be processed during one flash update. The flash command allows tuning of these parameters.

  limit number

  Specifies the maximum number of routes which may be processed during one flash update. The default is 20. A value of -1 will cause all pending route changes of the specified type to be processed during the flash update.

  type interface | interior | all

  Specifies the type of routes that will be processed during a flash update. Interior specifies that interior routes (See the definition of interior gateway protocols) will also be installed. All specifies the inclusion of exterior routes (See the definition of exterior gateway protocols) as well. The default is interface which specifies that only interface routes will be installed during a flash update. Specifying flash limit -1 all causes all routes to be installed during the flash update; this mimics the behavior of previous versions of GATED.

• background
  Specifies that the remaining routes are processed in batches in the background, that is, when no routing protocol traffic is being received. Normally, 120 routes are installed at a time to allow other tasks to be performed and this background processing is done at lower priority than flash updates the following parameters allow tuning of these parameters:

  limit	Specifies the number of route which may be processed at during one batch. The default is 120.
  priority	Specifies the priority of the processing of batches of kernel updates in relationship to the flash update processing. The default is lower which means that flash updates are processed first. To process kernel updates at the same priority as flash updates, specify flash; to process them at a lower priority, use lower.

While the kernel interface isn't technically a routing protocol, in many cases it is handled as one. The following two symbols make sense when entered from the command line since the code that uses them is executed before the trace file is parsed.

symbols	Symbols read from the kernel, by nlist() or similar interface.
iflist	Interface list scan. This option is useful when entered from the command line as the first interface list scan is performed before the configuration file is parsed.

The following tracing options may only be specified in the configuration file. They are not valid from the command line.

remnants	Routes read from the kernel when GATED starts.
request	Requests by GATED to Add/Delete/Change routes in the kernel forwarding table.

The following general option and packet-tracing options only apply on systems that use the routing socket to exchange routing information with the kernel. They do not apply on systems that use the old BSD4.3 ioctl() interface to the kernel.

info

Informational messages received from the routing socket, such as TCP lossage, routing lookup failure, and route resolution requests. GATED does not currently do processing on these messages, just logs the information if requested. Packet tracing options (which may be modified with detail, send and recv): routes Routes exchanged with the kernel, including Add/Delete/Change messages and Add/Delete/Change messages received from other processes. redirect Redirect messages received from the kernel. interface Interface status messages received from the kernel. These are only supported on systems with networking code derived from BSD 4.4. other Other messages received from the kernel, including those mentioned in the info type above.

B.17 Control Statements

B.17.1 Route Filtering

The action taken when no match is found is dependent on the context, for instance import and export route filters assume an all reject ; at the end a list.

A route will match the most specific filter that applies. Specifying more than one filter with the same destination, mask and modifiers will generate an error.

Filtering syntax

network [ exact | refines ] network mask mask [ exact | refines ] network masklen number [ exact | refines ] all default host host

These are all the possible formats for a route filter. Not all of these formats are available in all places, for instance the host and default formats are not valid for martians.

In most cases it is possible to specify additional parameters relevent to the context of the filter. For example, on a martian statement it is possible to specify the allow keyword, on an import statement you can specify a preference, and on a export you can specify a metric.

• network [ exact | refines ]
  network mask mask [ exact | refines ] network masklen number [ exact | refines ]
  Matching usually requires both an address and a mask, although the mask is implied in the shorthand forms listed below. These three forms vary in how the mask is specified. In the first form, the mask is implied to be the natural mask of the network. In the second, the mask is explicitly specified. In the third, the mask is specified by the number of contiguous one bits.
  If no additional parameters are specified, any destination that falls in the range given by the network and mask is matched, the mask of the destination is ignored. If a natural network is specified, the network, any subnets, and any hosts will be match. The two optional modifiers cause the mask of the destination to be considered also:

  exact	This parameter specifies that the mask of the destination must match the supplied mask exactly. This is used to match a network, but no subnets or hosts of that network.
  refines	Specifies that the mask of the destination must be more specified (i.e. longer) than the filter mask. This is used to match subnets and/or hosts of a network, but not the network.

• all
  This entry matches anything. It is equivalent to:

  0.0.0.0 mask 0.0.0.0

• default
  Matches the default route. To match, the address must be the default address and the mask must be all zeros. This is equivalent to:

  0.0.0.0 mask 0.0.0.0 exact

• host host
  Matches the specific host. To match, the address must exactly match the specified host and the network mask must be a host mask (i.e. all ones). This is equivalent to:

  host mask 255.255.255 exact

An AS path is a list of autonomous_systems that routing information has passed through to get to this router, and an indicator of the origin of the AS path. This information can be used to prefer one path to a destination network over another. The primary method for doing this with GATED is to specify a list of patterns to be applied to AS paths when importing and exporting routes.

Each autonomous system that a route passed through prepends it's AS number to the beginning of the AS path.

The origin information details the completeness of AS path information. An origin of igp indicates the route was learned from an interior routing protocol and is most likely complete. An origin of egp indicates the route was learned from an exterior routing protocol that does not support AS paths (EGP for example) and the path is most likely not complete. When the path information is definitely not complete, an origin of incomplete is used.

AS path regular expressions are defined in RFC 1164 section 4.2.

B.17.2.1 AS Path-Matching Syntax

An AS path is matched using the following syntax.

aspath aspath_regexp origin any | ( [ igp ] [egp ] [ incomplete ] )

This specifies that an AS matching the aspath_regexp with the specified origin is matched.

B.17.2.2 AS Path Regular Expressions

Technically, an AS path regular expression is a regular expression with the alphabet being the set of AS numbers. An AS path regular expression is composed of one or more AS paths expressions. An AS path expressions is composed of AS path terms and AS path operators.

B.17.2.3 AS Path Terms

An AS path term is one of the following three objects:

• autonomous_system
  Is any valid autonomous system number, from one through 65534 inclusive.
• dot (.)
  Matches any autonomous system number.
• ( aspath_regexp )
  parentheses group subexpressions--an operator, such as * or ? works on a single element or on a regular expression enclosed in parentheses.

An AS path operator is one of the following:

aspath_term {m,n}(1) aspath_term {m}(2) aspath_term {m,}(3) aspath_term *(4) aspath_term +(5) aspath_term ?(6) aspath_term | aspath_term(7)

1. aspath_term {m,n}
   a regular expression followed by {m,n} (where m and n are both non-negative integers and m <= n) means at least m and at most n repetitions.
2. aspath_term {m}
   a regular expression followed by {m} (where m is a positive integer) means exactly m repetitions.
3. aspath_term {m,}
   a regular expression followed by {m,} (where m is a positive integer) means m or more repetitions.
4. aspath_term *
   an AS path term followed by * means zero or more repetitions. This is shorthand for {0,}.
5. aspath_term +
   a regular expression followed by + means one or more repetitions. This is shorthand for {1,}.
6. aspath_term ?
   a regular expression followed by ? means zero or one repetition. This is shorthand for {0,1}.
7. aspath_term | aspath_term
   matches the AS term on the left, or the AS term on the right.