[Click] Large argument lists

[Marko Zec]

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-----