[quagga-dev 4311] Re: can you please help me with information on Quagga
paul at clubi.ie
Sun Aug 20 19:45:51 BST 2006
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.:
(trie index for IP prefixes)
(interface and IP address abstractions)
(abstraction around IP and other prefixes)
(co-operative threads used in Quagga for events, signals, timers,
(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
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
- 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
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"
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
> so that it could turn out to be a final year
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