implementation.tex

xorp源码hg

In a pipeline structure, original routes are generally stored in a table at the
beginning of the pipeline. Pushing routes through the pipeline again will
involve iterating through the initial table and sending an add / replace / dump
downstream. In fact, which request should be sent down is the tricky bit. The
best solution is probably to have a specialized route dump for policies. The
temporary solution in BGP was to use the existing route dump which will be
intercepted by a policy filter which will then forward the request as an
appropriate add / replace / delete.

In a central database structure, routes may be scanned through directly and
modified right away. However the database must hold a pointer to the original
routes in order to re-filter original routes. Currently, route pushing in RIP is
a hack --- the database is flushed. Routes will only be re-filtered on
re-advertisements. There is however an attempt to refilter routes learned from
the RIB. In the static\_routes protocol, routes are simply re-filtered from the
database, and the modified copy is sent to the RIB (the database will always
contain originals).

Blindly sending a replace after re-filtering will not work. Consider the case
where a route has been rejected and now accepted. The replace will most likely
fail since the route to be replaced will not be found down stream.

Table~\ref{pushmatrix} illustrates the general case to what actions should be
taken on re-filtering.
\begin{table}
\begin{tabular}{l l l}
               & accepted & rejected \\
was accepted   & replace  & delete, then return \\
was rejected   & add      & return \\
\end{tabular}
\caption{\label{pushmatrix}Route pushing action matrix}
\end{table}
Consider the first case, where a replace is suggested. If there is a way to
check that the route was not modified compared to the previously added route,
then a replace would be superfluous (replacing the same route). This does occur
for example in BGP and there is a check for this condition. However, it is wise
to send the route downstream anyway (in a pipeline structure) because maybe a
filter later in the pipeline has changed its configuration and may affect the
route.

\section{Route redistribution interface}
Protocols may wish to be used for export. This is certainly not the case for
static routes, but probably the case for most, if not all, dynamic routing
protocols. Some protocols may support only IPv4 and others may have separate
processes for v4 and v6 implementations. For this reason two interfaces are
provided for IPv4 and IPv6 route redistribution based on policy.

The XRL interface is:
\begin{verbatim}
    add_route4      ? network:ipv4net & unicast:bool \
                    & multicast:bool  & nexthop:ipv4 \ 
                    & metric:u32 & policytags:list

    delete_route4   ? network:ipv4net & unicast:bool \
                    & multicast:bool
\end{verbatim}
This resembles the normal RIB interface, and a similar one is provided for IPv6.

Many protocols chose to emulate the RIB as a peer. Thus, the interface may be
readily implemented by making the simulated peer inject and delete routes. Care
must be taken however to make the simulated peer act as a real peer. For
example, the RIP process assumes that routes are re-advertised periodically. The
RIB will not send an add\_route periodically, thus it is RIP's responsibility to
ensure RIB routes are periodically updated in its internal database.

The PolicyTags class has a conversion constructor which will deal with
XrlAtomLists. An exception may be thrown if the list, or its atoms are invalid.

Currently, the protocol should not die if a delete is performed on a
non-existing route, or an add is performed on an already added route. It should
give a warning but discard the operation. This needs to be fixed in the future.

\section{\label{varmap}The variable map}
As stated earlier, the VarRW reads variables based on their string represented
name such as ``metric.'' There must be a mechanism to ensure that only valid
names are read and written. Furthermore, there must be a way to check that only
specific variables may be written to (read-only variables). All this is done by
the semantic checker in the policy manager. More precisely, the semantic checker
also needs to know which protocols exist.

All this is achieved through a VarMap (variable map). The VarMap reads a
configuration supplied by the routing protocols which describe who they are, 
what variables they support and whether they are read-only. The syntax for the
VarMap configuration is very crude at the moment. Here is an indicative sample:
\begin{verbatim}
bgp     nexthop6        ipv6    rw
bgp     nexthop4        ipv4    rw
bgp     aspath          str     rw
bgp     origin          u32     r

ripng   network6        ipv6net r
rip     network4        ipv4net r
\end{verbatim}
The first column identifies the protocol name which will be typed by the user in
the configuration. Currently this has to match the XRL target name (although
making it aliasable is trivial). The next column is the actual variable name.
Following that is the textual representation of the type. Finally, the access of
the variable where r is read-only and rw is read-write.

The allowed types are described in the elements section.

\section{\label{elems}Elements}
Elements are very similar to XrlAtoms. Perhaps their only difference is in their
design. XrlAtoms seem to have a fat interface which i did not use. The basic
element interface is:
\begin{verbatim}
    Element(const std::string& type);
    
    virtual std::string str() const = 0;

    const std::string& type() const;
\end{verbatim}
This ensures that every elements has a string representable type and its value
may be converted to a string. 

The decision of having every elements require a string representation simplified
the developing process but also had a practical need. Configurations are sent
via XRLs to the policy filters. This configuration is textual. The configuration
will contain elements, so therefore each element must be converted to a string
sooner or later. Also, if the user will match a route attribute with
``something'', that ``something'' will most likely be a textual representation
of the attribute he/she enters.

The element type must be unique per type. It may sound obvious, but it has to be
enforced. Many internal components rely on the uniqueness of elements types.

Elements may be created via their concrete implementations. However, to ensure
flexibility and allow this generic framework to work, an ElementFactory is
provided to simplify the creation of elements.

\subsection{The element factory}
An element factory creates an element based on its type and assigns to it an
initial value. The interface is:
\begin{verbatim}
    Element* create(const string& key, const char* arg);
\end{verbatim}
The caller is responsible for the deletion of the element. {\em Key} represents the
textual type of the element which wants to be created. {\em Arg} is the string
representation of the value with which the element should be initialized. If arg
is NULL, the element is assigned its default value.

This gives an additional constraint to elements which support the factory.
Indeed the factory is used through out the policy framework, so having a const
char* constructor in the element base type would be a good idea. The constraints
are that all elements must have a default initialization value and all elements
must be able to construct from a string representation.

The argument for why all elements need to be capable of initialization via
a string is similar to the previous one about why elements should be string
convertible.  Firstly, if the user enters an ``element'' in the configuration
file, there must be a way of parsing it. Also, if all elements may be converted
to a string, there probably should be a way of constructing an elements from
that string.

Because of these requirements, the factory may also used as a clone factory,
although it is not intended to. Consider the following code:
\begin{verbatim}
Element* clone = factory.create(elem.type(),elem.str().c_str());
\end{verbatim}

\subsection{Element types}
Currently, the element factory supports elements listed in
table~\ref{elemtypes}.
\begin{table}
\begin{tabular}{l l}
Type	& Description \\
i32	& 32 bit integer. \\
u32	& 32 bit unsigned integer. \\
str	& textual string. \\
bool	& boolean value. \\
ipv4	& IPv4 address. \\
ipv6	& IPv6 address. \\
ipv4net	& IPv4 network. \\
ipv6net & IPv6 network. \\
null	& NULL element. Represents nothing. \\
set	& a set of strings. (all elements promoted to string for now). \\
\end{tabular}
\caption{\label{elemtypes}Factory supported element types}
\end{table}

It now becomes evident that implementing a VarRW in a protocol becomes trivial.
Elements may be created via the element factory. On writes, elements may safely
be casted to their concrete type as the semantic checker will go through type
checking.

Recall however that in the previous VarMap configuration of BGP, support was
given both for IPv4 and IPv6 in the same process. What happens if the filter
attempts to read an ipv6net on an IPv4 route? The VarRW must return the null
element. BGP supports both v4 and v6 and the filter is expecting the VarRW to
reply correctly for all variables it supports, even if they are not present in
the currently examined route. The same applies for attributes which are present
only sometimes such as local pref. The NULL element must be returned for each
attribute not present, but supported. NULL elements will never be received for
writes.

If the SingleVarRW interface is used, a NULL pointer may be passed to the
initialize function if the variable is not present, without having to explicitly
create a NULL element (do not confuse the NULL element with a pointer to 0).

Also, PolicyTags may be converted to Element pointers to ease the read()
implementation of VarRW interfaces.



\section{Common policy component internals}
The ElementFactory was briefly discussed and it should be clear that elements
may be created with ease. Creating elements is only partially useful if there
is not way to manipulate them. 

ElementFactory will always return the base type of elements and operations will
have different semantics according to the concrete type of their arguments.  An
unary operation will depend only on the element itself so calling
element.unary() will suffice as a standard polymorphism technique. Consider the
more useful and frequent binary operations however. They depend on the types of
two elements. Standard polymorphism will not help here. 

I have implemented multi methods as explained by Alexandrescu and Meyers. The
solution lies in a dispatcher which takes an operation and two base elements,
and will execute the correct method based on the operation and the concrete type
of the elements.

\subsection{The dispatcher}
The client interface to the dispatcher is very simple:
\begin{verbatim}
    Element* run(const BinOper& op,
                 const Element& left, 
                 const Element& right) const;
		 
    Element* run(const UnOper& op, const Element& arg) const;

    Element* run(const Oper& op, const ArgList& args) const;
\end{verbatim}
It currently supports three ways of executing operations. The most generic way
is providing an operation and an argument list. An argument list is a vector of
Element pointers.

There are also two utility functions for executing explicit unary and binary
operations. If the magic occurs, the Element of the resulting operation is
obtained (caller is responsible for deletion). On error, an exception is thrown.

Being able to create elements from their string representation and being able to
perform operations on base elements makes the design of the policy filter
conceptually easy.