Carlos Ferreira wrote:
> 1 - There a data type named IPV6 Address. 2 - there is a table where
> this data type must be in. ( can be a set of fields, one blob, one string
> ...)
>
> You want to:
>
> Given a certain IPV6, find in the database the existent IPV6 record with
> the longest equal prefix to the given IPV6 value.
Not quite. Perhaps you were confused by my (probably unclear) use of
the word "prefix".
The data structure contains a set of IPv6 *network prefixes*. A prefix
is the first N bits of an IPv6 address and is denoted as an IP address
with a suffix of (128-N) bits of zeros, along with the length of the
prefix:
feed:beef::/32
(here N==32).
An IPv6 address is inside this prefix iff its first 32 bits are equal to
feed:beef.
Note that one prefix can be contained within another:
feed:beef:f00d::/48 is fully contained within feed:beef::/32. We say
that feed:beef:f00d::/48 is "more specific" than feed:beef::/32.
The problem (one that comes up quite often, e.g. in routers) is this:
given an IP address, find the longest-length prefix containing the
address. I.e. find the most specific prefix containing the address.
This is different from the problem you stated. One key thing to note is
that the two prefixes feed:beef::/32 and feed:beef::/48 are different,
even though the bits in the address parts are identical.
> Again, if the problem is as I understood, the simplest solution is (
> again I am discussing it as if it could be implemented or available in
> SQLite..I do not know..)
>
> 1 - encode the IPV6 field as a unique blob 2 - Implement an index to
> this field so that this particular field can be ordered 3 - Make sure that
> the ordering compare function is a binary incremental compare counting
> from the left ( in terms of the data...not sure how you will represent
> it in the field ) 4 - Each time you want to find the closed and longest
> prefix, you just need to simulate an insert command. Try to insert the
> given value. Instead of inserting, just return the ordered position where
> it would be inserted. Check what is the record actually standing in that
> ordered position...That would be your result!!
The problem has many solutions outside of SQL. The most common data
structure is a "trie" (pronounced "tree" and short for "reTRIEval
tree"), though it turns out that in many subsets of this problem space
other data structures turn out to be more efficient.
The present motivation, however, is to see if we can leverage all
the ancillary sexiness of SQLite while still getting reasonably fast
searches within this problem space. Turns out we can do pretty darn
well with SQLite in this regard.
The key part is coming up with an isomorphism between overlapping
IPv6 prefixes and the overlapping geometric boxes represented in a
5-dimensional R*Tree. Not just any isomorphism, but one with the
property that for prefixes P1 and P2, P1 contains P2 if and only if
bbox(P1) fully contains bbox(P2). (It follows that the volume of
bbox(P1) is larger than the volume of bbox(P2), so you can sort by the
volumes of all the covering bboxes to find the most specific prefix.
Though my SQL had a bug in that regard, so treat it with care if you use
it.:-)
Again, the 5 dimensions are only needed because the R*Tree's integers
are only 32 bits wide. If they were 128 bits wide, you could just
represent an IPv6 prefix as an interval on the line segment [0,
2^128-1], and store those intervals in a 1-dimensional R*Tree (which
works great for IPv4, btw).
--
Eric A. Rubin-Smith
I still maintain the point that designing a monolithic kernel in
1991 is a fundamental error. Be thankful you are not my student.
You would not get a high grade for such a design.
-- Andrew Tanenbaum, to Linus Torvalds
_______________________________________________
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
