On Friday 17 October 2008 02:26:01 Eddie Kohler wrote:
> Hi Harald,
>
> We have a problem. It looks like this is a bug in DirectIPLookup.
> If I use RadixIPLookup instead of Direct, everything works fine. I
> did not write DirectIPLookup; I have ccd Marko Zec, who did. Maybe
> he can help.
Hmm it's both a bug and a feature, depending on how you look at it...
The short answer to Harald: in your particular test case, pls. bump
SEC_SIZE_MAX from 4096 to 32768 in elements/ip/directiplookup.hh
Somewhat longer elaboration: DirectIPLookup lookups are performed by
using the 24 most significant bits of the target IP address as an index
into array of uint16_t numbers. If the result has the most significant
bit cleared, it is interpreted as an index into a table of possible
{dst_IP, dst_port} pairs (called vports in DirectIPLookup
implementation). Alternatively, if the result has the MSbit set, an
index into a secondary table is constructed by combining 15 LS bits
from the result of the first lookup, shifted left by 8 places, with the
8 LS bits of the target IP address.
So, as long as the primary table stores 16-bit values, as it was
proposed in the original paper by McKeown et. al., the DirectIPLookup
will be limited to covering a maximum of 32768 /24 ranges in the
secondary table (and those ranges containing prefixes that are more
specific than /24). This limit was further reduced by setting the
SEC_SIZE_MAX to 4096, given that the actual size of the secondary
lookup table will be SEC_SIZE_MAX * 256.
In Harald's particular example the distribution of prefixes is such that
each /32 prefix allocates a full 256-entry chunk in the secondary
table, so the whole secondary table gets quickly populated, and further
attempts to add prefixes to the table get silently ignored.
The same issue is observable with the RangeIPLookup table which
essentially derives a smaller lookup structure based on the contents of
a DirectIPLookup lookup table. It is of course possible to implement
RangeIPLookup element independent of DirectIPLookup structures and thus
not suffer from the limitations described above, but this isn't a
trivial change...
Hope that helps,
Marko
> Harald Schiöberg wrote:
> > -----BEGIN PGP SIGNED MESSAGE-----
> > Hash: SHA1
> >
> > Eddie Kohler wrote:
> >> Harald,
> >>
> >> I guess a couple people have run in to this limit. I thought it
> >> was a string length problem, but now I think maybe it is a bug.
> >> Can you send a URL (not an attachment) to a sample user elvel
> >> config? Thank you.
> >
> > sure, the "real" config with 20000 routes
> > http://www.net.t-labs.tu-berlin.de/~harald/click/hugetable.click
> >
> > and here is the output of
> > echo "read rt.table" | nc -q 1 localhost 5000 > hugetable.out
> >
> > http://www.net.t-labs.tu-berlin.de/~harald/click/hugetable.out
> >
> > $wc -l hugetable.out
> > 4102 hugetable.out
> >
> > thanks
> > Harald
> > - --
> > Harald Schiöberg
> > Technische Universität Berlin | T-Laboratories | FG INET
> > www: http://www.net.t-labs.tu-berlin.de
> > Phone: +49-(0)30-8353-58476 | Fax: +49-(0)391 534 783 47
> > -----BEGIN PGP SIGNATURE-----
> > Version: GnuPG v1.4.6 (GNU/Linux)
> > Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
> >
> > iD8DBQFI9iqBy8wrZ9OvkU0RAmFvAJ46qz5r9dBmrvPzUGvzOtRdTNMUgwCffHOJ
> > 6BMnKluuKBn0r0pBfHt1Swc=
> > =nfDN
> > -----END PGP SIGNATURE-----
_______________________________________________
click mailing list
click@amsterdam.lcs.mit.edu
https://amsterdam.lcs.mit.edu/mailman/listinfo/click
