%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Globally Distributed Content (Using BGP to Take Over the World)
% Paper based on work on Super Sparrow - http://superpsparrow.org/
%
% November 2000
% Copyright (C) 2000 Horms <horms@vergenet.net>
% 
% This program is free software; you can redistribute it and/or
% modify it under the terms of the GNU General Public License as
% published by the Free Software Foundation; either version 2 of the
% License, or (at your option) any later version.
% 
% This program is distributed in the hope that it will be useful, but
% WITHOUT ANY WARRANTY; without even the implied warranty of
% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
% General Public License for more details.
% 
% You should have received a copy of the GNU General Public License
% along with this program; if not, write to the Free Software
% Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
% 02111-1307  USA
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Implementation: Super~Sparrow}

Super~Sparrow is an implementation of global load balancing written in
C\cite{c} and released under the GNU~General~Public~Licence and
GNU~Lesser~General~Public~Licence\cite{fsf}.  Super~Sparrow is available
from \emph{http://supersparrow.org/} and is supplied with source and
RPM\cite{maximum_rpm}\footnote{RPM: Red Hat Package Manager} packages with
comprehensive online documentation.  Super~Sparrow is able to load balance
traffic by using BGP to find the peer closest to a client.

\subsection{Route Servers}

To avoid the need for yet another BGP implementation, Super~Sparrow
accesses BGP information by querying route servers.  A route server is a
router, or host running a routing daemon, that may be queried for the
preferred prefix for a IP address. The current implementation supports three
different route servers: GNU~Zebra\cite{zebra} and
GateD\cite{gated}, routing daemons that run on a variety
of platforms including Linux\footnote{Linux is a trademark of Linus
Torvalds}, and Cisco~IOS\cite{CiscoNetwork}, the operating system
that runs on Cisco routers and is synonymous with BGP and routing in
general.

The current implementation uses telnet access to route servers to query 
the preferred prefix for an IP address. The tenet interface to
route servers is generally intended for manual interaction with
the route server but provides a reasonably fast and portable
way of other programmes accessing the route server. A sample
session with GNU~Zebra to determine the preferred prefix for
\texttt{192.168.193.15} from a route server running on
\texttt{192.168.192.13} is given in figure~\ref{zebra-figure}.

The results shown in the figure indicate that there are two prefixes
for the query made and that the second prefix listed is preferred. The AS
path for the preferred prefix is \texttt{64702}. It is the AS path of the
preferred prefix that Super Sparrow uses to determine if a point of presence
in the Super~Sparrow network is closer to the address begin queried than
the route server being queried as described in section~\ref{bgp-algorithm}.


\begin{figure}
\small
\begin{verbatim}
$ telnet 192.168.192.13 bgpd
Trying 192.168.192.13...
Connected to 192.168.192.13.
Escape character is '^]'.

Hello, this is zebra (version 0.89.horms.pre.2)
Copyright 1996-2000 Kunihiro Ishiguro


User Access Verification

Password: 
jasmine> sho ip bgp 192.168.193.15
BGP routing table entry for 192.168.193.0/24
Paths: (2 available, best #2, table Default-IP-Routing-Table)
  64600 64601 64602
    192.168.192.12 from 192.168.192.12 (192.168.192.12)
      Origin IGP, metric 1, localpref 100, valid, external
      Last update: Fri Oct  6 15:47:28 2000
                                           
  64702
    192.168.193.11 from 192.168.193.11 (192.168.193.11)
      Origin IGP, metric 1, localpref 100, valid, external, best
      Last update: Fri Oct  6 15:44:05 2000


jasmine> exit
Connection closed by foreign host.
\end{verbatim}
\normalsize
\caption{Determining The Prefered Prefix Using GNU~Zebra}
\label{zebra-figure}
\end{figure}

\subsection{libsupersparrow}

The core functionality of Super~Sparrow, including the ability to
communicate with route servers is encapsulated as a library,
\emph{libsupersparrow}.  Breaking this code out into a library allows
flexibility to make the algorithm available to a variety of applications.

The library is able to manage connections to multiple route servers and
multiple connections to a single route server. In the latter case,
connections are cached such that if multiple connections to a route server
are requested a single connection will be opened and shared.  This avoids
the possibility of exceeding the maximum number of connections a route server
will accept.

Results read from route servers may be cached to increase performance and
avoid placing excessive load on route servers.  The
implementation of this is quite simple. Results are stored in a self
reordering linked list. Queries to the cache search through the list
sequentially and if a result is found it is moved to the front of the list.
The number elements and the timeout for elements in the cache is
configurable. Though simple, the cache yields a significant performance
increase, if successive queries are received for the same IP address. 

The library also manages the relationship between the AS numbers of POP and
their IP addresses or hostnames. This enables the library to determine if
the prefered prefix for an address, as returned by a route server, includes
the AS number of a peer and if so the IP addresses or hostnames that should
be returned accordingly.


Two aplications that link against libsupersparrow have
been written: \emph{mod\-\_super\-sparrow} a driver module for
Dents to allow Super~Sparrow to be tied to the DNS for a domain,
and \emph{supersparrow} a standalone utility that may be used for
testing and tying Super~Sparrow to aplications that can communicate
over standard I/O. The latter may be used in conjunction with 
Apache's \emph{mod\_rewrite} to tie Super~Sparrow directly to Apache.


\subsection{mod\_supersparrow (DNS)}

Dents\cite{dents} is a modular DNS
server that is intended as a drop in replacement for BIND\cite{isc_bind}.

Dents allows zones to be mounted in the name space much in the same way
that UNIX allows partitions to be mounted in a directory
structure. Just as different mounted partitions in a directory structure
may have different file systems controlled by different portions
of code in the kernel, Dents allows different zones types, controlled by
driver modules. 

Access to a the root name server is analogous to the root (/) directory in
a UNIX directory structure. Dents allows this zone to be mounted and
resolved using the driver module mod\_recursive. BIND for one uses
RFC~1035\cite{rfc1035} style zone files. This is supported in Dents by
mounting a zone using the \emph{mod\_stddb} driver module.

One advantage of being able to use different driver modules is that
arbitrary modules may be defined. Driver modules that access zone
information stored in a relational data base or produce standard mappings
from an IP address to a hostname for dialup pools are two
example applications.

Super~Sparrow implements a Dents driver module, \emph{mod\_supersparrow},
that allows Dents to return results based on information from BGP speaking
route-servers. In this way the IP address returned for a hostname lookup
may be governed by the BGP-based global loadbalancing algorithm implemented
by Super~Sparrow. Details of how client-server interactions work in such a
setup are described in section~\ref{directing-dns}.



\subsection{supersparrow}

\emph{supersparrow} is a stand-alone application that is linked against
lib\_\-super\-sparrow. The primary intention of
this application is to act as a debugging tool during development of
lib\_supersparrow.  As it turns out, supersparrow may be
used in conjunction with applications that are able to commumicate with
other programmes using standard I/O a useful example of which is Apache's
mod\_rewrite.


\subsection{supersparrow with Apache (HTTP)}

One of the most apealing aspects of
The~Apache~HTTP~Server\cite{ApacheGuide} is its flexibility afforded to
a large extent by its modular architecture. An excellent
example of this is \emph{mod\_rewrite} which is part of the
standard Apache distribition. mod\_rewrite allows arbitary
rewriting of requests received by Apache to other URLs at run time.
The rewrite is done by a map and one of the map types supported is
running an external programme.

mod\_rewrite communicates with the external programme via
standard I/O. The external programme is run once when apache starts,
requests are written to the programme's standard~in and results are
read from the programme's starndard~out. The 
\emph{supersparrow} stand-alone application supports a batch mode,
which allows it to be used as a map for mod\_rewrite. In this
way Apache may be tied directly to Super~Sparrow to achieve the
semantics described in section~\ref{directing-http}.
