implementation.tex

xorp源码hg

is instantiated. If the policy is an import, then the Import code generator is
used.

For export policies two passes need to be done. The source match code
generation and the export part. The export part acts much like import policy
code generation but the source block matches policy tags.

The source match code generation will match the source block, ignore the dest
block and set policy tags as actions. However, the code generated may be for
multiple {\em targets} where a target is a protocol and filter pair. Consider
the following policy fragment:
\begin{verbatim}
term a {
    source {
        protocol static_routes;
        metric == 4;
    }
}
term b {
    source {
        protocol rip;
        metric == 3;
    }
}    
\end{verbatim}
The source match will generate two code fragments of which one will need to be
sent to static\_routes and one to RIP.


\subsection{Tracking configuration changes}
Source match may generate code fragments for different targets.  Suppose policy
A generates a source match for RIP and static routes. Suppose a policy B is now
added which also generates a source match for RIP. No problem, just append the
code. 

If policy B is deleted, the source match dependency for RIP has to be tracked
down. Then, somehow, the code relevant to B has to be deleted. If the code was
kept as ``a whole'' it would not be possible, so policy A would have to be
re-compiled, and possibly any other policies which generate source match for
RIP.

For this reason, generated code is always kept fragmented. There is a close
resemblance to what a compiler does by keeping separated object files and
linking them when needed. The same occurs with the policy manager.

In the previous example, the code fragment of policy A would be deleted, and the
source match filter for RIP would be re-linked and the configuration would be
sent off.

Policies are instantiated via the export / import list of a protocol. This list
is managed via the PolicyList which will also contain all the code fragments
generated by the instantiation.

\subsubsection{Policy lists}
A policy list is what instantiates policies. Each policy list will have its
independent generated code for the policies which it refers to. A policy list is
either an export or import list, depending on user configuration.

Internally a list of the policy names will be stored and for each policy there
will be a code list associated with it. A code list is simply a collection of
code fragments. The code list will be all code generated for the instantiation
of that policy. If it were an export policy list, the code list will contain all
the source match code, even if it was destined to a different protocol.
Thus, the code fragments in a policy list may be for many different targets.

Keeping code fragments this way allows tracking affected targets on policy
changes easier.  For example if policy A changes, each Policy list which
contains policy A is tracked. The policy lists found will then extract all the
targets in the code list for policy A. These are the affected targets.

When a target changes, the code fragments are re-linked and sent to the filter
manager. The filter manager is responsible with keeping backend filters synchronized
with the latest configuration.

\subsection{Filter manager}
The Configuration class always contains the most up to date configuration for
all targets. It is the responsibility of the filter manager to ensure that
backend filters are synchronized with the configuration.

Normally the filter manager will receive update requests from the configuration
class. The filter manager will then queue a configuration request for the
target. These requests are queued in order to try and aggregate configuration
changes and especially route pushing. Particularly, on boot-up of the XORP router,
many small configuration changes will occur in a short period of time.
Currently, updates are flushed 2 seconds after the last update.

The filter manager closely works with the process watcher. If a protocol dies,
then no updates are longer sent to that protocol. Conversely, if a protocol is
born, any configuration present must be sent to it.

Upon configuration changes, the filter manager tracks down which protocols need
to have their routes pushed. These are also queued and flushed with a delay to
attempt aggregation.

There currently is a problem with the whole implementation structure. If
redistribution from protocol A to B is requested and only A is alive, the
routes will reach the RIB. When B come to life, it will never receive the
routes. As a hack, the filter manager will cause routes of A will to pushed when
B comes to life.

\subsection{RIB redistribution map}
The RIB redistribution map is trivially implemented. A route table is present
before the register table in the RIB. As a route flows through, the table checks the
policy tags and determines where route should be redistributed.

It is configured via the filter manager which tracks down which tags are
associated to which protocol.


\section{Current XORP integration}
Currently, some degree of policy support is implemented in:
\begin{description}
\item[BGP] Import, source match, export, IPv4/6 redistribution.
\item[RIP] Import, source match, export, IPv4/6 redistribution.
\item[static routes] Import, source match.
\item[connected] source match.
\end{description}
If source match filtering is supported, then the protocol may be used as the
source for a route redistribution.

Following is an outline of the current implementation in the various routing protocols.

\subsection{BGP}
A generic route policy table is implemented. It suffices for export filtering.
The import and source match filters are specialized because they contain other
functionality needed to allow route pushing.

The import policy filter table is placed in each branch for every peering just
after the standard filter in table. The source match filter is placed right
before the fan out table. Finally, the export filter table is placed in each
branch for ever peering just after the filter out table.

The BGPVarRW implementation supports a subset of the most important attributes
which need to be examined. For example, variables that indicate which peering
the route came from still need to be added.

The route pushing interface of BGP has to be redesigned.

\subsubsection{BGP route push}
Route pushing in BGP is a proof of concept and should not be used. It uses dump
iterators but is not a background task. The dump to peer is set to NULL to
differentiate it from normal route dumps. 

The source match filter initiates the route dump for its strategical position
--- it has access to peerinfo from the fanout table, and may use the decision
table to spread the route dump request to all branches. It will try to dump all
routes in one go, and will not check if routes are flowing in the pipeline as
the dump is initiated.  The RibIn table will dump all routes if the dump to peer
is set to NULL (even routes which are not winners).

The policy import filter will intercept route dumps with the dump peer set to NULL. It
will recognize them as policy route dumps. It will then transform the request to
either an add, replace or delete according to the matrix in table~\ref{pushmatrix}.
For this reason, import filters need to be present in each branch, even though
filtering may not desired such as the RIB peer branch.

The routes will then flow through the pipeline most likely causing unnecessary
updates. It is important to have the routes flow all the way down, even if
nothing changed, as maybe the export filter lower in the pipeline will change them.


\subsection{RIP}
RIP has the worse policy implementation. 

For import filtering, All the RIP ``magic'' occurs in the update\_route routine
of the RouteDB. An attempt is made to try to filter routes and modify them.

Output filtering is slightly better and occurs both for the route table outputs
and the updates output.

Because of reference counting, I was not able to find a clean way to copy a RIP
route without having to create a new structure containing the same data. As a
result, I ended up copying routes by setting a NULL origin to force reference
counting not to occur. For this reason, the current RIPVarRW has no information
about origin, so matching may only be done on a subset of what is possible.

Route pushing in RIP does not exist. The route database will be flushed, as
copies of original routes are not stored. For the filters to take effect,
new advertisements have to come in. An attempt is made to re-filter routes
learned from the RIB.


\subsection{Static routes}
Static routes probably has the most correct and safe policy implementation due
to its simplicity. Filtering may occur only on the import branch. The route
database will always contain original routes, and routes are possibly modified
by filters as they are sent to the RIB.

Route pushing should be safe and should work correctly.


\subsection{Connected routes}
Connected routes may only be used as a source for route redistribution. They may
not be modified nor filtered. Notice that modifying policy tags on a route, does
not modify the route itself. It is pure meta-data used exclusively by the policy
framework.

Route pushing is implemented by having the connected route filter table in the
RIB store all the routes itself. This is a waste of space, as the Origin table
will have the same exact information. On a push request, the filter table will
initiate a replace\_policytags call which should only be used by the policy
redist table. The policy redist table will then decide which protocols should
stop advertising the route and which should start.

Changes only to the policy tags should be propagated in a similar way in all
routing protocols, as it will not cause route adds / deletes inside the process
(in this case the RIB), which is desirable. 

Currently, the user has to specify rib as the protocol instead of connected due
to a lack of protocol to process mapping in the VarMap (which may be used by the
filter manager).


\section{General problems}
The XORP integration should be fixed as stated in the above sections. The
biggest problem is route pushing. Other problems may arise due to race
conditions. The following list are issues which should be considered:
\begin{itemize}
\item What happens if the source protocol is alive, but the export is dead.
\item How to configure VarMap ?
\item Configuration integration with rtrmgr for source / action / dest block.
\item ElemSet --- do not treat everything as a string!
\item Route pushing propagate only real route changes, and propagate policy tags
changes with another mechanism.
\item Counters in filters indicating how many times a term was matched.
\end{itemize}


\section{Conclusion}
I believe that the overall idea of having generic filters was good. If it works,
and works well, it will make life easy for protocol developers which would
like to support policy in their implementations. There are considerations to
make about how fast these filters run as flexibility does come with a
cost. The work is still under development and un-stable. The ``real-life''
testing was basically null, possibly due to bad time management on my part.

Hopefully this work will give an idea to what are the problems and possible
solutions in implementing a policy framework for XORP. I belive however the
current implementation reached a good starting point for it to be extended. If
this design is accepted and kept, the major components and ideas are deployed.
It is now a question of correcting, extending and optimizing them.

\end{document}