prog-intro.sgml 7.96 KB
Newer Older
1
<chapt>BIRD Design
2

3
<sect>Introduction
4

Martin Mareš's avatar
Martin Mareš committed
5
<p>This document describes the internal workings of BIRD, its architecture,
6 7 8
design decisions and rationale behind them. It also contains documentation on
all the essential components of the system and their interfaces.

9
<p>Routing daemons are complicated things which need to act in real time
Martin Mareš's avatar
Martin Mareš committed
10
to complex sequences of external events, respond correctly even to the most erroneous behavior
11 12 13 14 15 16 17 18 19
of their environment and still handle enormous amount of data with reasonable
speed. Due to all of this, their design is very tricky as one needs to carefully
balance between efficiency, stability and (last, but not least) simplicity of
the program and it would be possible to write literally hundreds of pages about
all of these issues. In accordance to the famous quote of Anton Chekhov "Shortness
is a sister of talent", we've tried to write a much shorter document highlighting
the most important stuff and leaving the boring technical details better explained
by the program source itself together with comments contained therein.

20
<sect>Design goals
21 22 23

<p>When planning the architecture of BIRD, we've taken a close look at the other existing routing
daemons and also at some of the operating systems used on dedicated routers, gathered all important
Martin Mareš's avatar
Martin Mareš committed
24
features and added lots of new ones to overcome their shortcomings and to better match the requirements
25 26 27 28 29 30 31 32 33 34 35 36 37 38
of routing in today's Internet: IPv6, policy routing, route filtering and so on. From this
planning, the following set of design goals has arisen:

<itemize>

<item><it>Support all the standard routing protocols and make it easy to add new ones.</it>
This leads to modularity and clean separation between the core and the protocols.

<item><it>Support both IPv4 and IPv6 in the same source tree, re-using most of the code.</it>
This leads to abstraction of IP addresses and operations on them.

<item><it>Minimize OS dependent code to make porting as easy as possible.</it>
Unfortunately, such code cannot be avoided at all as the details of communication with
the IP stack differ from OS to OS and they often vary even between different
Martin Mareš's avatar
Martin Mareš committed
39 40
versions of the same OS. But we can isolate such code in special modules and
do the porting by changing or replacing just these modules.
41 42 43 44 45 46 47 48 49
Also, don't rely on specific features of various operating systems, but be able
to make use of them if they are available.

<item><it>Allow multiple routing tables.</it>
Easily solvable by abstracting out routing tables and the corresponding operations.

<item><it>Offer powerful route filtering.</it>
There already were several attempts to incorporate route filters to a dynamic router,
but most of them have used simple sequences of filtering rules which were very inflexible
50
and hard to use for non-trivial filters. We've decided to employ a simple loop-free
51 52 53 54 55 56 57 58 59 60 61 62 63 64
programming language having access to all the route attributes and being able to
modify the most of them.

<item><it>Support easy configuration and re-configuration.</it>
Most routers use a simple configuration language designed ad hoc with no structure at all
and allow online changes of configuration by using their command-line interface, thus
any complex re-configurations are hard to achieve without replacing the configuration
file and restarting the whole router. We've decided to use a more general approach: to
have a configuration defined in a context-free language with blocks and nesting, to
perform all configuration changes by editing the configuration file, but to be able
to read the new configuration and smoothly adapt to it without disturbing parts of
the routing process which are not affected by the change.

<item><it>Be able to be controlled online.</it>
Martin Mareš's avatar
Martin Mareš committed
65
In addition to the online reconfiguration, a routing daemon should be able to communicate
66 67
with the user and with many other programs (primarily scripts used for network maintenance)
in order to make it possible to inspect contents of routing tables, status of all
68
routing protocols and also to control their behavior (disable, enable or reset a protocol without restarting all the others). To achieve
69 70 71 72
this, we implement a simple command-line protocol based on those used by FTP and SMTP
(that is textual commands and textual replies accompanied by a numeric code which makes
them both readable to a human and easy to recognize in software).

Martin Mareš's avatar
Martin Mareš committed
73
<item><it>Respond to all events in real time.</it>
74 75 76 77 78
A typical solution to this problem is to use lots of threads to separate the workings
of all the routing protocols and also of the user interface parts and to hope that
the scheduler will assign time to them in a fair enough manner. This is surely a good
solution, but we have resisted the temptation and preferred to avoid the overhead of threading
and the large number of locks involved and preferred a event driven architecture with
79 80 81
our own scheduling of events. An unpleasant consequence of such an approach
is that long lasting tasks must be split to more parts linked by special
events or timers to make the CPU available for other tasks as well.
82 83 84

</itemize>

85
<sect>Architecture
86 87 88 89 90 91

<p>The requirements set above have lead to a simple modular architecture containing
the following types of modules:

<descrip>

Martin Mareš's avatar
Martin Mareš committed
92
<tagp>Core modules</tagp> implement the core functions of BIRD: taking care
93 94 95 96 97 98
of routing tables, keeping protocol status, interacting with the user using
the Command-Line Interface (to be called CLI in the rest of this document)
etc.

<tagp>Library modules</tagp> form a large set of various library functions
implementing several data abstractions, utility functions and also functions
Martin Mareš's avatar
Martin Mareš committed
99
which are a part of the standard libraries on some systems, but missing on other
100 101 102
ones.

<tagp>Resource management modules</tagp> take care of resources, their allocation
Martin Mareš's avatar
Martin Mareš committed
103
and automatic freeing when the module having requested shuts itself down.
104 105 106 107 108 109

<tagp>Configuration modules</tagp> are fragments of lexical analyzer,
grammar rules and the corresponding snippets of C code. For each group
of code modules (core, each protocol, filters) there exist a configuration
module taking care of all the related configuration stuff.

110
<tagp>The filter</tagp> implements the route filtering language.
111 112 113 114 115 116 117 118 119 120 121

<tagp>Protocol modules</tagp> implement the individual routing protocols.

<tagp>System-dependent modules</tagp> implement the interface between BIRD
and specific operating systems.

<tagp>The client</tagp> is a simple program providing an easy, though friendly
interface to the CLI.

</descrip>

122
<sect>Implementation
123

Martin Mareš's avatar
Martin Mareš committed
124
<p>BIRD has been written in GNU C. We've considered using C++, but we've
125 126 127 128
preferred the simplicity and straightforward nature of C which gives us fine
control over all implementation details and on the other hand enough
instruments to build the abstractions we need.

129 130 131
<p>The modules are statically linked to produce a single executable file
(except for the client which stands on its own).

132 133 134 135 136 137
<p>The building process is controlled by a set of Makefiles for GNU Make,
intermixed with several Perl and shell scripts.

<p>The initial configuration of the daemon, detection of system features
and selection of the right modules to include for the particular OS
and the set of protocols the user has chosen is performed by a configure
138
script generated by GNU Autoconf.
139 140 141 142

<p>The parser of the configuration is generated by the GNU Bison.

<p>The documentation is generated using <file/SGMLtools/ with our own DTD
143 144
and mapping rules which produce both an online version in HTML and
a neatly formatted one for printing (first converted
145
from SGML to &latex; and then processed by &tex; and <file/dvips/ to
146
get a PostScript file).
147 148 149 150 151

<p>The comments from C sources which form a part of the programmer's
documentation are extracted using a modified version of the <file/kernel-doc/
tool.

152 153 154 155
<p>If you want to work on BIRD, it's highly recommended to configure it
with a <tt/--enable-debug/ switch which enables some internal consistency
checks and it also links BIRD with a memory allocation checking library
if you have one (either <tt/efence/ or <tt/dmalloc/).
156 157 158 159 160

<!--
LocalWords:  IPv IP CLI snippets Perl Autoconf SGMLtools DTD SGML dvips
LocalWords:  PostScript
 -->