As of 2003-12-02, this is a bit out of date, since major enhancements
have been introduced in the meantime.  This should be taken care of
shortly.

Qolyester's internals
---------------------

  This implementation follows RFC 3626 which can be found on the
  following page:

    http://www.ietf.org/rfc/rfc3626.txt

  or in the doc/ directory.

  Nevertheless, it differs from the specification on the following
  points:

    - Support for sections 13 (Link Layer Notification) and 20
      (Security Considerations) are not implemented.

    - Routing table calculation differs from the description in
      section 10.  Qolyester maintains an actual representation of the
      topology graph at any time.  Routing table calculation is done
      using the Dijkstra algorithm on the topology graph.  This allowa
      for future simple modifications to introduce more routing
      metrics and a modified version of the Dijkstra algorithm.

  For the time being, the reason why only Linux 2.4 kernels are
  supported is that we primarily needed IPv6 support and thus all the
  system interface for network interface information retrieval and
  routing table management need support for the IPv6 protocol family.
  The netlink socket interface is a good way to cope with those two
  points but is specific to Linux kernels starting from 2.4 AFAIK.  Of
  course, *BSD hackers are welcome to help us with *BSD porting.


General model layout
--------------------

  . The scheduler

    The core of Qolyester is event-driven (arrival of a packet, time to
    send a packet, etc) and is thus built around a simple scheduler
    that takes care of timed and input/output events.  Hence, most of
    the time, the daemon waits for a packet to arrive or a timer to
    expire.  So a packet is processed as soon as it arrives and the
    internal data structures are modified immediately.  New message
    generation and message forwarding are processed as soon as their
    scheduled timer expires.  On the other hand, operations like routing
    table calculation, packet sending, MPR set calculation, they are
    processed at the end of the event processing loop:

      +-----+
      |     |
      |     V
      |  [ wait for packet input or timer expiration ]
      |
      |  [ process active input/output events ]
      |
      |  [ process active timed events ]
      |
      |  [ process once-per-iteration events ]
      |     |
      +-----+

    Routing table and MPR set calculation are "once-per-iteration"
    events triggered by markers (i.e. boolean variables).  This way,
    these events are processed once every other timed and i/o events
    have been processed if some of them requested it.

    Packet sending is also a "once-per-iteration" event.  It is triggered
    by a non-empty "pending messages" queue.  This way as much messages
    generated simultaneously as possible are put into the same packet

  . The sets

    Qolyester needs to process sets of tuples which elements have
    implicit processing requirements.  The simplest example is a set with
    elements of limited lifetime, i.e. onces that need to be removed after
    some time has passed since their insertion.  Other sets' elements need
    to be modified after some time etc.  For all these sets, there is a
    concept of "updatable" elements: each time an element is inserted into
    the set, a special timed event is registered into the scheduler and
    attached to the element.  The timed event keeps a reference to the
    element inside the set, in order to be able to modify it at expiration
    time.

  . IP address family

    With the use of extremely simple metaprogramming C++ techniques
    and a bit of conditional preprocessing, we have kept all the code
    independent of the IP family used.  The needed family is
    selectable at configure time before compilation with the use of
    the --enable-ipv4 flag.  This should be enough for many uses as
    there is no sense in supporting both families in one OLSR network.

  . System interface

    An effort has been made to separate OS interface from the core of
    the system.  There remain some OS-dependent code in the scheduler
    code, but that should be fairly easy to fix by now.

Documentation
-------------

  Usage information can be printed on standard output using the -h or
  --help command line flag.  In addition, the qolsrd(8) man page
  describes each command line option in details.

  Developer information comprises documentation generated from special
  comments in the source code using the Doxygen system and comments
  themselves.  HTML documentation generated by Doxygen is available in
  the doc/ directory.  This documentation is very useful to understand
  the relations between classes and hierarchies.

  Unfortunately, there are comments that do not fit into the Doxygen
  way of presenting things and thus remained in the code for
  developers and curious users to read.  To help them find their way
  out, here is a brief description of the file hierarchy:

    daemon/  : code specific for the qolsrd daemon
    switch/  : code specific for the qswitchd daemon
    include/ : common generic (thus reusable) code

  Once step deeper, in any of the three main directories, there are
  subdirectories:

    alg/ : the general algorithms (Dijkstra, MPR selection, etc)
    cst/ : constant parameters definitions
    gra/ : graph definitions
    msg/ : message class definitions
    net/ : network-level definitions
    pkt/ : packet class definitions
    prs/ : parser definitions
    sch/ : scheduler definitions
    set/ : sets definitions
    sys/ : system interface
    sys/linux/ : Linux kernel dependent code
    sys/virtual/ : low-level networking code for virtual mode
    utl/ : miscellaneous utility definitions
    /    : main definitions

  For any additional information, please send an email to qolsr@lri.fr
  or refer to the Qolyester page at http://qolsr.lri.fr/code .

Include files scheme
--------------------

  For the sake of run-time performance, we want the compiler to be
  able to inline as much small methods as possible, while keeping just
  one implementation of large methods.  One way to achieve that,
  though not without drawbacks, is to use as few compilation units as
  possible.  This translates into as much code as possible into header
  files and as few .cc files as possible.

  Then each component of the project (let's call them _modules_ even
  if it may sound strange for C++) is in fact a file included into
  some main source code file.  In fact, as we shall see shortly, a
  module is split into two, three or maybe even four separate header
  files.  The reason for that are module dependencies.

  C++ supports several kinds of inter-class dependencies and offers
  several ways to resolve them.

  The definition of one class may require that the compiler knows that
  some other class exists, but yet does not know any detail about it.
  This is the case for any type of a method's arguments and when some
  class' attribute has the type of reference or pointer to another
  class.  This is solved by class predeclaration.

  Sometimes the definition of one class may require that the compiler
  knows another class completely (not only that it exists).  This is
  the case for the types of a class' attributes, for example.  This is
  solved by simply declaring the class after all the classes it
  depends on.

  Lastly, a class' method definitions need that some other classes be
  already declared.  This again is solved by correct ordering of class
  declaration.

  For simplicity of maintenance and ease of use, we want each module
  to be composed of a .hh file containing declarations and a .hxx file
  containing definitions (i.e. implementations).  Each .hh and .hxx
  file includes (using #include cpp directives) .hh files of each
  module it depends on, thus ensuring that someone wanting to use that
  module will also use all the modules it depends on.

  As it occured to us quite soon is that this scheme works fine as
  long as you don't have cyclic dependencies between modules.
  Although truly cyclic dependencies between classes are forbidden in
  C++ (you cannot have class A with attribute of type B and class B
  with attribute of type A), because a module is a class' declarations
  _and_ definitions, you have cyclic module dependencies as soon as
  one class' declaration depends on another class whose definitions
  depend on the former class.  Let's take a look at the following
  example:

  -------------------------------
    // a.hh
    #ifndef A_HH
    # define A_HH 1
    struct A {
      void meth();
    };
    # include "a.hxx"
    #endif
  -------------------------------
    // a.hxx
    #ifndef A_HXX
    # define A_HXX 1
    # include "b.hh"
    void A::meth() {
      B	b;
    }
    #endif
  -------------------------------
    // b.hh
    #ifndef B_HH
    # define B_HH 1
    # include "a.hh"
    struct B {
      A	a_;
    };
    # include "b.hxx"
    #endif
  -------------------------------
    // b.hxx
    #ifndef B_HXX
    # define B_HXX 1
    // no definitions required
    #endif
  -------------------------------

  If someone starts including a.hh, she ends up with the following
  order of inclusion:

    a.hh
    b.hh
    b.hxx
    a.hxx

  This order is okay, since B's declaration depends on A's declaration
  and A's definitions depend on B's declaration.

  On the other hand, if she starts with b.hh, she has the following order:

    a.hh
    a.hxx
    b.hh
    b.hxx

  This is wrong, since A's definitions depend on B's declaration and
  the latter comes _after_ the former.  The problem is that when b.hh
  includes a.hh, it has already armed the include protection and we
  are sure that no one can include b.hh again.  But still, we would
  like to include B's declarations before A's definitions which is
  impossible since, when including a.hxx, we already begun including
  b.hh.

  Thomas Claveirole found an elegant solution (a dirty trick according
  to him): circumvent b.hh's include protection in a.hxx's inclusion
  by including a.hh in b.hh _before_ arming the include protection:

  -------------------------------
    // b.hh
    #include "a.hh"
    #ifndef B_HH
    # define B_HH 1
    struct B {
      A	a_;
    };
    # include "b.hxx"
    #endif
  -------------------------------

  Since a.hh has its own include protection, the multiple inclusion is
  still avoided, while allowing a.hxx to include B's declaration, even
  if this file is ultimately included from b.hh.  At the time the
  preprocessor returns from b.hh's inclusion of a.hh, B's body has
  already been included and thus preprocessing jumps to the end of
  b.hh.

  More complicated dependency problems can be solved analogously with
  the following technique.  Let's look at the problem we just solved:

         +--------------+
         |              |
         v              |
    --> b.hh --> a.hh   |
         ^        ^     |
         |        |     |
        b.hxx    a.hxx -+

  The arrows represent the "depends on" property.  As you can see,
  this graph has no cycle, which clearly means that the dependency is
  solvable.  The only exotic requirement is that the .hh includes the
  .hxx.  To solve that dependency, simply walk on the graph vertices
  using the arcs in the way a preprocessor should include the files:

    begin parsing b.hh,
      begin parsing a.hh,
        include A's declarations,
        begin parsing a.hxx,
          parse b.hh again but skip a.hh's inclusion,
            include B's declarations,
          begin parsing b.hxx,
            include B's definitions,
        resume parsing of a.hxx,
          include A's definitions.

  As you see, we have crossed the arc between b.hh and a.hh twice, but
  the second time, we have not parsed a.hh again because all its
  dependencies have already been satisfied before.  We can mark that
  arc with some special color, indicating that this inclusion should
  be performed before b.hh's protection.  Indeed, the second time we
  are to parse b.hh, we include a.hh again, but the latter's
  protection makes us skip it and go back parsing the rest of b.hh
  (including B's declarations).

  This technique has been applied on all dependency cycles and now any
  module should be compilable separately, including all its required
  modules.

