Re: search algorithm
- From: fenwayfool <peterson.russell@xxxxxxxxx>
- Date: Wed, 7 Jan 2009 06:00:51 -0800 (PST)
On Jan 6, 10:54 pm, Richard Heathfield <r...@xxxxxxxxxxxxxxx> wrote:
fenwayfool said:
I need to create a database that has a fairly long key. Consider
the key a bitstring. My problem is that this key also has an
associated mask. All bits that we "care" about in the key have a
mask value of '1' while the don't care bits are marked with a
zero.
[...]
For example let's assume the key/mask is 32 bits. If I have the
following in my database:
key: 0xA0A000001
(I'm guessing this was supposed to be 0xA0A00001)
mask: 0xFFFF000F
Should match a key such as 0xA0A00007 (the lookup does not specify
a key).
Here's your example in binary:
key: 1010 1010 0000 0000 0000 0000 0000 0001
mask: 1111 1111 1111 1111 0000 0000 0000 1111
I'm guessing that you mean by this that any match for the search key
must look like this:
1010 1010 0000 0000 xxxx xxxx xxxx 0001
where x indicates "any bit value will do for this position".
But your indicated match has the pattern
1010 1010 0000 0000 0000 0000 0000 0111
which does NOT match the required bit pattern (two mandatory bits
are different).
So I'm puzzled as to whether I have understood your requirements
correctly.
Anyway, this whole question smacks very much of secondary analysis.
"I have a problem X. Ah! I have thought of a solution Y. Oh! I have
a problem Z with solution Y. Hm! How can I solve Z?" whereas
perhaps you ought really to be asking "How can I best solve X?"
--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
You are correct. In my haste I did not get the example right.
No idea what secondary analysis is... but problem X is how to simulate
a TCAM in software and do it in a manner that does not involve brute
force... i.e. a linear search of key/mask (or maybe data/mask is more
correct?) values applied to a specified key that returns some
associated data on a match. The real application here is IP flow
identification in an embedded system.
For example, the key is a 5-tuple (IP source addr, IP dest addr,
source port, dest port, protocol). Each member of the tuple has an
associated mask... but I believe I can assume the mask is contiguous
(i.e. the source IP address mask would be 0xffffff00 and never
something like 0x0f0f0f0f). I'm starting to think the easiest way to
do this might be to break this problem up. Maybe use 5 different
databases where the lookup result of 1 returns another database...
until the last lookup returns my result data? In that case, I think
this is just a longest prefix match problem... but I would love to
hear other, better solutions.
.
- Follow-Ups:
- Re: search algorithm
- From: Ben Pfaff
- Re: search algorithm
- References:
- search algorithm
- From: fenwayfool
- Re: search algorithm
- From: Richard Heathfield
- search algorithm
- Prev by Date: Re: search algorithm
- Next by Date: Re: search algorithm
- Previous by thread: Re: search algorithm
- Next by thread: Re: search algorithm
- Index(es):
Relevant Pages
|
