The Gated policy module provides a mechanism for storing Gated policy descriptions. The gated configuration mechanism enables specification of import and export policy; the policy module stores these specifications in a manner that enables quick policy conformance testing.
Abstractly, for a given protocol, Gated allows the import and export policies to each be specified by a set of policy elements (route parameter, (destination/mask, preference), (destination/mask, preference),...). Route parameter is protocol dependent: for example, BGP policy statements can be expressed in terms of AS number and an AS path regular expression, RIP policy statements can be expressed in terms of an interface list or router address list, and OSPF policy statements can be expressed in terms of route tags. The semantics of a policy element are as follows: if a route contains the route parameter specified in the policy element (e.g., the AS path matches the regular expression specified, or the AS number matches the peer from which the route was received), then the route is assigned the preference associated with the destination/mask that it best matches.
The policy module implements these policy rules in a time and space efficient manner. A detailed description of the data structures, macros and functions used in the policy module may be found here.
The fundamental data structure in the Gated policy module is the adv_entry. The adv_entry is used to represent both a single policy element and the list of (destination/mask, preference) tuples within a policy element. The dest_mask structure within an adv_entry is used to store the destination address and mask in a tuple. A discriminator field is used to distinguish what the adv_entry contains.
To faster match a route's destination address and mask with the list of destination address mask pairs in a policy element, Gated builds a radix tree from this list. An internal node of this radix tree is the dest_mask_internal structure.
An import or export list is an ordered list of these policy elements. Import or export lists are stored in the protocol descriptor blocks. For instance, BGP maintains a per peer policy list in the gw_entry data structure associated with the peer. In addition, for BGP policy statements restricting importation of routes based on AS path regular expression, BGP maintains a global policy list.
This figure pictorially depicts the relationship between these different data structures.
To compute route preferences based on policy or to filter route announcements, protocol modules use the import() and export() entry points. Given a policy list, these functions find the first (if any) policy element in the list which matches one of the given routes' parameters. It then finds out the best match destination/mask in the corresponding policy element's list of (destination/mask, preference) tuples.
Gated creates the radix trees from the list of (destination/mask, preference) tuples when the configuration files are parsed. To insert an element of this list into the radix tree formed, the parser code adv_destmask_insert(). After the entire tree is built for a given policy element, the parser calls adv_destmask_finish() to adjust tree pointers for fast tree traversal.
Given a destination address and mask, the tree traversal function adv_destmask_match(). finds the corresponding (destination/mask, preference) tuple in the specified list of such tuples. This is used both in the import() and export() functions.