[quagga-dev 4311] Re: can you please help me with information on Quagga

Paul Jakma paul at clubi.ie
Sun Aug 20 19:45:51 BST 2006

Hi Prachi,

On Sun, 20 Aug 2006, prachi gaikwad wrote:

> I am a student of final year engineering(computers). I have to do a 
> project for the final year.i am interested in developing a part of 
> the Quagga routing software and would like to know the latest 
> additions and updates .

See the ChangeLogs :). Follow links on http://www.quagga.net, the 
download directory generally has a changelog file for each release.

> also a list of protocols that are yet to be developed for this 
> particular software would be helpful.

Some obvious ones:


Perhaps others might suggest further protocols.

> information on how to i could help develop this software would also 
> be of great help.

Have a look at http://www.quagga.net/resources.php, browse through 
some of the papers and the 'ZHH', then have a look at the sources 
under the lib/ directory, and familiarise yourself with the data 
structures and methods used throughout Quagga, e.g.:

- table
   (trie index for IP prefixes)
- if
   (interface and IP address abstractions)
- prefix
   (abstraction around IP and other prefixes)
- thread/sigevent
   (co-operative threads used in Quagga for events, signals, timers,
    high-level IO)
- stream
   (safe buffer abstraction for network IO)

There's other stuff too, some is cruft though (e.g. 'sockunion' is 
obsolete and should be torn-out in favour of since standardised 
sockaddr_storage), so be careful ;).

> Can you please give me information on how to find what is yet to be 
> developed for quagga for example is there any protocol that is yet 
> not fully supported

Following protocols are implemented to a degree but could use 
additional work:

- OSPFv3

Protocols that would be /really/ nice to have:

   (see also http://mpls-linux.sourceforce.net/, which might already
    have an LDP implementation, though using some LDP toolkit by and

> or are there any bugs that would be large enough to be solved over 
> a period of 6 months..

Well, fixing bugs tends not to make for an interesting academic 
paper. I guess what you'd want instead are things which need to be 
overhauled. E.g:

- the 'table' data-structure:
   - space-inefficient, node for every bit of depth of prefixes which
     is wasteful, a sparse trie would be better.
   - a stride-index to 'shortcut' into deeper parts of the index would
     be neat (e.g. its highly unusual to see prefixes shorter than /8
     in the wild, yet we index each of those first 8 bits
   - IPv6 addresses are trie-indexed right down to the 128th bit,
     which is utterly inefficient as really only the first N bits need a
     hierarchical index - the remaining least-significant bits of
     a prefix/address would be more efficiently indexed via a hash. N,
     at present, is 64.
   - lots of room here for exploring the implementation of an
     efficient trie index data structures and algorithm analysis
     which might make for a good paper.
     - e.g. a hybrid index, using different types of indices optimised
       to different parts of the address space might perform well.

- the zebra "RIB" could do with an overhaul
   - the "database" of all best protocol routes, from which
     best route to install to kernel is picked
   - route "colouring" would be neat, i.e. given two routes A and B
     where both have X as the nexthop:

 	A via X
 	B via X

     and B is included by A, and there are no intervening routes in
     the tree, we /need/ only install A. However at present we install
     both routes, even though B via X is quite redundant.
   - recursion for nexthops would be nice, it's been discussed before
     but no one has implemented in a generalised way

I guess it all depends on what kind of paper you want to write, which 
depends on your course a bit, i.e. is your course more "computer 
science" (where ideally you want some meaty algorithm analysis) or 
more "engineering" (where some meaty implementation work might be 
more suitable).

Other potential ideas, in addition to above:

- Research 'constrained SPF'.

   At present there are forms of "CSPF", mostly to use
   available-bandwidth as a constraint on SPF and work out inverse
   best-paths for input to LDP (MPLS).

   You could research other forms of constrained SPF, including ones
   that could work with OSPF and normal IP forwarding. E.g.
   "link reliability" would be an interesting constraint on SPF.

   There's some meaty combinatorial topology CS work here to try
   prove/disprove the compatibility of any such a modified SPF with
   normal OSPF SPF.


- Implement "link-reliability constrained SPF" for ospfd

   If you're more interested in engineering, you could go ahead and
   implement it using "Opaque LSAs" and/or "Link-Local Signaling"
   extensions to OSPF to propogate link-reliability information. Then
   extend SPF (see ospf_spf.c) to avoid links determined to be
   unreliable as much as possible.

   You can avoid the compatibility issues and the heavy topology
   proof work simply by requiring that all routers within an area must
   support the modified form of SPF.

- Investigate "Ordered Updates"

   See http://www.info.ucl.ac.be/people/OBO/papers/pfr-infocom05.pdf

   It's really interesting stuff, but there are few implementations
   (though the "Graceful Shutdown" / "Stub-router" support in Quagga
    0.99 ospfd provides a very very rough approximation of /some/
    aspects of it).

   Implementing this for OSPF would be neat. (E.g. by propogating the
   LSDB checksums via Opaque LSAs and using that as a constrain on
   SPF and route installation so as to achieve ordered updates of
   routes in the manner described in the paper to avoid micro-loops
   and micro-blackholes).

> so that it could turn out to be a final year 
> project.

Hope above helps.

Don't hesitate to ask for further advice :).

Paul Jakma	paul at clubi.ie	paul at jakma.org	Key ID: 64A2FF6A
It's amazing how many people you could be friends with if only they'd
make the first approach.

More information about the Quagga-dev mailing list