Ben April
Fri, 04 Apr 2003 15:20:46 -0800
On Fri, Apr 04, 2003 at 02:26:27PM -0800, Joshua Kuo wrote: > hi all: > > i have installed FreeIPdb-0.1.4 and used it to keep track of some > address space. i am curious in how FreeIPdb handles the ip address > space. > > i.e. how is the script keeping track of which /27 belongs to which /24?
Good Question (Apologizing in advance for the long answer)
First we need to throw out the Old block format (e.g. Class A,B, & C)
It worked for a while but we're in CIDR land now.
It all starts with 0.0.0.0/0 one CIDR block that contains every IP
address known to man. You will see that used for a default route alot
(and I can see why). We get smaller (more manageable) block by splitting
that in half (e.g. 0.0.0.0/0 splits into 0.0.0.0/1 and 128.0.0.0/1).
Every "Legal" IP block is derived by this method.
This is how FreeIPdb works :-) You give an allocation and basicly all we do
to is is keep splitting it in half. (example:
10.0.0.0/24
10.0.0.0/25
10.0.0.0/26
10.0.0.0/27
10.0.0.0/28
10.0.0.0/29
10.0.0.0/30
10.0.0.4/30
10.0.0.8/29
10.0.0.16/28
10.0.0.32/27
10.0.0.64/26
10.0.0.128/25
each level is a new block. FreeIPdb keeps a block in the db for every
step in this split that's where the childr,childl and parent come in.
We use a doubly linked list where the children point at their parent
and the parent has record of both children.
> i am impressed with how space-efficient the database is, but all i could
> really figure out from looking at the database structure is that it's
> using a left-child and right-child. i try to dig into admin.cgi but my
> poor perl skills get in the way of me understanding the code.
FreeIPdb uses what I call a "Best-fit Truck Packing algorithm".
We look for the smallest block of sufficient size to use for the
next allocation. (Find the smallest hole that I can stuff this into).
The goal is to leave the highest possible number of large(r) block free.
So when you reclaim a block we look at it's sibling and if it is also free
we remove both children and mark the parent free (working up the tree).
> if possible, could someone explain to me a little on how this is setup,
> and perhaps add the comments into the code itself so it would be easier
> to read?
Whelp, I hope that helps some. Let me know if you have any further questions.
I'll see what I can do about some comments.
--
Our doubts are traitors,
And make us lose the good that we oft may win,
By fearing to attempt --William Shakespeare