hi,
we've been working on trying to replace the FIB from its current hashing
scheme to a trie, as part of an attempt to implement 'Routing With A Clue'
by Bremler-Barr et all (SIGCOMM '99). it's not as involved as the patricia
tries in *BSD, but of course our trie implementation is very basic right
now, and can be improved upon.
i have a couple of questions:
1. is this replacement (current scheme w/tries) likely to cause speedups
overall? would the networking folks be interested in having a look at
the patch?
2. is someone trying to do something similar? i've tried searching a lot
for it, but couldn't find any leads.
in the process of actually implementing the above (it's close to completion
btw), i read the existing code, and constructed the following diagram for my own
understanding. i figured it figures this figure find a better place than my home
directory: i'm guessing (after corrections/ modifications/additions), this
figure might be useful to more people! :-)
Thanks!
Arun Raghunath
(PS: this page has more information about the project itself:
http://www-scf.usc.edu/~raghunat
thanks due to Tomas Abrahamsson for the neat artist.el pkg for emacs!)
struct fn_zone *fn_zones[33]
+---------------+---------+---------+- - - - - - - +----------+
Zones | address=<def> | 1 bit | 2 bits | | 32 bits |
+---------------+---+-----+---------+ -+ - - - - - +----+-----+
| | |
+--------------+ | | |
| fn_zone_list +-+ V V V
+--------------+ | +-------------+ +-------------+ +-------------+
+->| fz_next +-->| fz_next +--->| fz_next |
+-------------fz_hash | | ... | | ... |
| | # of entries| | ... | | ... |
| | hash_divisor| | | | |
| | hash_mask | | | | |
| | zone order | | | | |
| | | | | | |
| | <<fn_zone>> | | <<fn_zone>> | | <<fn_zone>> |
| +-------------+ +-------------+ +-------------+
| (( Zones chained in descending order of address prefix length ))
|
|
|
Level 2 | Hashtable
V (( Hash bucket of nodes in ascending order of
+----------+ [key, tos, priority] ))
| | +--------------+ +------------+ +------------+
| +----->| next +------>| next +->| next |
+----------+ | info -----------+ | ... | | ... |
| | | key | | | | | |
| +--+ | tos | | | | | |
+----------+ | | scope | | |<<fib_node>>| |<<fib_node>>|
| | | | state | | +------------+ +------------+
| | | | | |
+----------+ | | <<fib_node>> | |
| | | +--------------+ |
| | | | +--------------+ +-----------+
+----------+ +--> ( more hash- | | next +-->| next |
| | buckets ) +--->| prev |<--+ ... |
| +-----> | refcnt | | ... |
+----------+ +----------->| metrics | | |
| | nextHop | | |
| +- - - - - - - + | |
| | nextHop2 | |<<fib_info>|
| +- - - - - - - + +-----------+
| | nextHop3 |
| +- - - - - - - +
| | |
| | <<fib_info>> |
| +--------------+
+---------------+ |
| fib_info_list +-----------+ (( Many hops if multipath
+---------------+ routing enabled ))
(( All fib_info entries chained
in one list (Used to mark
fib_info nodes when an i/f
goes up/down ))
__________________________________________________
Do You Yahoo!?
Send instant messages & get email alerts with Yahoo! Messenger.
http://im.yahoo.com/
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/
This archive was generated by hypermail 2b29 : Sun May 07 2000 - 21:00:14 EST