Use-case for helpers: existentials vs. universals

[tnelson]

Suppose we have a relation:

TABLE needsnat(ipaddr, int);

such that if needsnat(a,b) then the subnet a/b needs to be natted.

We'd want separate Flowlog rules for both cases: when NAT is needed, and when it isn't. The first rule would have something like:

needsnat(addr, mask) AND p.nwSrc IN addr/mask

That works fine. The problem is with the complement rule. We need to cover the case where NOT p.nwSrc IN addr/mask for every tuple in the table. That is, we can't write:

needsnat(addr, mask) AND NOT p.nwSrc IN addr/mask

since that will use addr and mask existentially, not universally.

When we added ALL, we said that we'd keep an eye out for other places we needed universal behavior, and here one is.

[tnelson]

In XSB, this is a classic helper use-case:

NOT helper(p.nwSrc).
invokes the helper:
helper(nsrc) :- needsnat(addr, mask), nsrc IN a/m.
The key here is that helpers bind variables inside negations. So the addr and mask variables would be implicitly universal here.

The challenge is compiling this to NetCore. At the moment in the Flowlog compiler, all variables are treated as existential.

[adferguson]

if we writing this in pure NetCore, we probably would have done something like:

ITE(<needs NAT>, <NAT actions>, <regular actions>)

or for the just not-NAT case:

ITE(<needs NAT>, pass, <regular actions>)

since we can write down <needs NAT> already. of course, <needs NAT> can become large, so eventually we'd want to be clever enough to convert a giant list of the form "!a && !b && !c" etc. into just "d || e" since we completely understand the universe of IPv4 addresses.

on that note, providing "hints" about the size of the IPv4 address space we expect (eg, we will only see the following address ranges on this network: a, b, c, d) would be a great flow table optimization for these sorts of procedures. of course, we then need a rule somewhere to handle addresses outside that range (eg, notify controller on first packet and black-hole after that) but the hint could still be useful.

hope this helps,
Andrew

[tnelson]

I think that for January, we're going to have to take the ITE route (via
generated Flowlog code). This is what the compiler is built to give us
anyway (although I will need to modify the code). But now the use-case will
not get forgotten for February.

On Tue, Jan 14, 2014 at 10:54 AM, Andrew Ferguson
notifications@github.comwrote:

if we writing this in pure NetCore, we probably would have done something
like:

ITE(, , )

or for the just not-NAT case:

ITE(, pass, )

since we can write down already. of course, can
become large, so eventually we'd want to be clever enough to convert a
giant list of the form "!a && !b && !c" etc. into just "d || e" since we
completely understand the universe of IPv4 addresses.

on that note, providing "hints" about the size of the IPv4 address space
we expect (eg, we will only see the following address ranges on this
network: a, b, c, d) would be a great flow table optimization for these
sorts of procedures. of course, we then need a rule somewhere to handle
addresses outside that range (eg, notify controller on first packet and
black-hole after that) but the hint could still be useful.

hope this helps,
Andrew

—
Reply to this email directly or view it on GitHubhttps://github.com//issues/45#issuecomment-32276600
.