implementation.tex

xorp源码hg

\documentclass{article}
\title{XORP Policy filters\\implementation v0.00}
\author{ab $<$[e-mail]$>$}


\begin{document}
\maketitle

\section{Introduction}
At the highest level of abstraction, the overall policy framework in XORP is
divided into two components: the back end filters and the front end policy
manager. Developers wishing to support policy based filtering in their routing
protocols, including route redistribution, will only have to know a minimum
about the framework to do so. The addition of basic functionality to the filters
should not be problematic as well. A high level overview of how a user may
implement policy filtering in his/her protocol, followed by a more detailed
description of implementation issues and choices made both in the back end and
front end is presented.


\section{Overview of XORP policy framework}
The main goal of the policy framework in XORP was flexibility. The user should
be able to express complex concepts in the configuration. This may result in
complex semantic checking and parsing which is undesirable to have replicated in
all routing protocols which wish to support filtering. Thus, the task has been
divided between a smart front end {\em policy manager} and a relatively dumb
back end generic filter.

The user configuration is sent from the rtrmgr to the policy manager. Currently,
the rtrmgr only parses the high level structure, sending the actual policy
expressions as un-parsed strings to the policy process. Hence, the first step of
the policy manager is to terminate the parsing. On a successful configuration,
the policies are semantically checked for validity. If all goes well,
configuration of relevant filters residing inside the various routing protocols
may begin.

The back end filters are able to interpret an intermediate language. They know
nothing about user configuration syntax. The policy manager will ``compile'' the
expressions in the configuration and send a simple assembly language style
program to the back end filters. The parsing and interpretation of this language
is trivially done in the back end with the use of a simple stack machine. The
back end does no semantic checking and run time errors will occur if a bogus
program is being executed.

There is a special component residing in the RIB which also is controlled by the
policy manager. It is the policy redistribution table which regulates the route
flows from the origin protocol to the protocol being used for export.  This is
accomplished via policy tags.

\section{Policy tags}
Policy tags mark routes in the input branch of routing protocols. These tags are
then used to send the relevant routes to export protocols which requested them,
ultimately allowing route redistribution.

The RIB XRL interface has now changed to support policy tags:
\begin{verbatim}
        add_route4      ? protocol:txt & unicast:bool      \
                        & multicast:bool & network:ipv4net \ 
                        & nexthop:ipv4 & metric:u32        \
                        & policytags:list

        replace_route4  ? protocol:txt & unicast:bool    \
                        & multicast:bool network:ipv4net \
                        & nexthop:ipv4 metric:u32        \
                        & policytags:list

\end{verbatim}
The same changes occur for add\_route6 and replace\_route6. They also occur in
add / replace of interface\_route. The delete family does not use tags as
deletion is done based on the network, and not on tags.

These tags are merely a set of unsigned integers. In the most simple case, where
a protocol wishes to not support filtering, supplying an empty XrlAtomList will
suffice. This is currently seen in the OSPF implementation.

Other routing protocols must add a PolicyTags entry in all their routes. The
PolicyTags class is provided by the policy back end library. These tags should
not be altered other than from within filters. The interface provides two
useful utility methods:
\begin{verbatim}
    XrlAtomList xrl_atomlist() const;
    string str() const;
\end{verbatim}
Thus, when an XRL needs to be sent to the RIB, calling the xrl\_atomlist()
method on the tags will be enough to convert them. If curious about how tags look
in real-life, then the str() method may be invoked.



\section{Implementation of filtering in protocols}
A developer wishing to implement policy filtering in a routing protocol may
safely ignore all the details and internals of the policy framework. The overall
work that needs to be done is:
\begin{enumerate}
\item implement the policy\_backend XRL interface.
\item implement a VarRW compatible interface.
\item have a mechanism to push routes through filters when requested.
\item if the protocol may be used to redistribute routes, implement the relevant
IPv6 / IPv4 policy\_redist XRL interface.
\item provide a varmap configuration.
\end{enumerate}
The only task which may lead to complications is the third one. Thus when
designing new protocols where filtering is desired, a design which will aid the
simplicity of route pushing will help greatly.  All these tasks will now be
examined in detail.

\subsection{Policy backend XRL interface}
There are three routines which need to be implemented in order to use the
generic policy filters. These may be found in policy\_backend.xif:
\begin{verbatim}
        configure ? filter:u32 & conf:txt
	
        reset ? filter:u32

        push_routes
\end{verbatim}
The first two need no implementation at all, as they are directly handled by the
policy filter interface. The last one will be discussed separately in
section~\ref{rpush}.

A routing protocol must have a single instantiation of a PolicyFilters class.
This class is a container which supports 3 filters:
\begin{description}
\item[import filter] Deals with import policies.
\item[source match filter] Allows route redistribution, used in export
policies. It basically adds tags to routes.
\item[export filter] Deals with export policies.
\end{description}
The interface for the class is:
\begin{verbatim}
    void configure(const uint32_t& type, const string& conf);
    
    void reset(const uint32_t& type);
    
    bool run_filter(const uint32_t& type, 
                    VarRW& varrw, 
                    ostream* os);
\end{verbatim}
The first two methods directly map the XRL interface, so the XRL call may be
simply forwarded to the filters.

The last method actually does the filtering. It returns true or false depending
on whether a route was accepted. Here is a summary of the arguments:
\begin{description}
\item[type] Identifies which filter needs to be run. This will depend on where
filtering is being applied, whether it is the input or output branch of a
protocol. The valid values are filter::IMPORT, filter::EXPORT\_SOURCEMATCH and
filter::EXPORT as defined in the filter namespace.

\item[varrw] The VarRW to use. This will become clear in the next section.
\item[os] If not NULL, the filter will output an execution trace to the stream.
It may be useful to point os to an ostringstream for debugging.
\end{description}

\subsection{The VarRW interface}
VarRW stands for Variable Read Write. It may be thought of as a symbol table. The
policy filter will request to read a variable and sometimes will request to
write one. In this case, a variable will be an attribute of a route such as the
next-hop address or metric. This interface allows the generic filter to match
routes and to modify them without knowing what attributes routes have in a
specific routing protocol and how they are stored internally.

The interface to VarRW is:
\begin{verbatim}
    virtual const Element& read(const string& id) = 0;
    
    virtual void write(const string& id, const Element& e) = 0;

    virtual void sync() = 0;
\end{verbatim}
The id parameter is the textual representation of the requested attribute, such
as ``metric'' or ``ipnet4''. The protocol knows about these, and in fact it
supplies all the variables it supports to the policy manager via a configuration
file as explained in section~\ref{varmap}. Elements will be explained in
section~\ref{elems}, but
they act similarly
to XrlAtoms. 

Elements obtained via read() must be accessible even after read() returns (they
must be available for the whole execution of the policy), thus storing them on
the heap is usually a solution. The VarRW implementation is responsible for
deleting elements created on the heap. On the other hand, elements passed on a
write must not be deleted or modified.

Sync will be called when all writes need to be executed in case the VarRW
implementation chooses to delay writes by caching them. If pointers to elements
passed by write are held, they will become invalid after a sync. Sync is usually
called once when the policy execution has terminated.

Policy filtering may now be achieved by associating a VarRW to a route and
running a filter with that VarRW. This will result in the route being accepted
or rejected, and possibly modified.

A more ``easy to use'' VarRW interface is provided which may be used by routing
protocols. It is the SingleVarRW.

\subsubsection{SingleVarRW}
With a normal VarRW many writes and reads for the same variable may be requested
per policy, depending on its complexity. A wise solution would be to cache and
re-use elements instead of creating new ones each time. Also, care must be taken
to garbage collect elements created.

To simplify this process, a VarRW is provided which will assure that each write
will be executed only once per variable if necessary. Also, all memory
management is done by the VarRW. This implementation is called SingleVarRW. The
interface follows:
\begin{verbatim}
    void initialize(const string& id, Element* e);

    virtual void single_start() = 0;
    
    virtual void single_write(const string& id, 
                              const Element& e) = 0;

    virtual void single_end() = 0;
\end{verbatim}
The first action an implementor of SingleVarRW will do is to initialize all the
variable the protocol supports. This will be done by calling the initialize
method once per variable. The SingleVarRW owns the Element pointer, so the
implementation does not need to worry about deleting the created element. The
element must be a heap object. All this will normally be done in the
implementation's constructor.

If the filter modifies the route, the SingleVarRW will then start to mark the
beginning of writes. It will call write once per each variable modified and
finally call end to indicate the termination of writes.

Writes must be done right away, if a pointer to an element passed by a write is
held, it may become invalid after single\_write returns.


\subsection{\label{rpush}Route pushing}
When the configuration of a filter changes, routes need to be re-filtered. The
complexity of passing the routes through the filter greatly depends on the
design of the protocol. In general, there were two design styles in XORP:
\begin{enumerate}
\item Pipeline: as seen in BGP and the RIB.
\item Central database / queues: present in RIP and static routes.
\end{enumerate}

When routes need to be re filtered, there must be an indication whether the
route was previously filtered (i.e. if the route was previously rejected by a
filter). Also, original routes need to be re-filtered, not the possibly modified
``current'' routes. This adds a requirement for protocols to have a {\em
is\_filtered} flag and keep the original copy of the route somewhere.