Issue 2 - duplicate entries in the flows table

[danieledc]

Hello everyone, I am Daniele De Cicco, master student of Computer Engineering at University of Naples (Italy). Since November I have been working on my master thesis at the Catholic University of Louvain (Belgium). I am developing my project with Pyretic and recently I have run into three different anomalies:

• ISSUE 2

When I run the following code

def main():
    return (match(dstmac="00:00:00:00:00:02")>>match(switch=2,dstmac="00:00:00:00:00:02")>>fwd(2))

this is what I find in the flows table of switch 2

*** s2 ------------------------------------------------------------------------
NXST_FLOW reply (xid=0x4):
cookie=0x0, duration=3.131s, table=0, n_packets=0, n_bytes=0, priority=59999,in_port=2,vlan_tci=0x0000,dl_dst=00:00:00:00:00:02 actions=IN_PORT
cookie=0x0, duration=3.131s, table=0, n_packets=0, n_bytes=0, priority=59996,vlan_tci=0x0000 actions=drop
cookie=0x0, duration=3.131s, table=0, n_packets=0, n_bytes=0, priority=59998,vlan_tci=0x0000,dl_dst=00:00:00:00:00:02 actions=output:2
cookie=0x0, duration=3.131s, table=0, n_packets=0, n_bytes=0, priority=59997,vlan_tci=0x0000,dl_dst=00:00:00:00:00:02 actions=drop
cookie=0x0, duration=3.131s, table=0, n_packets=0, n_bytes=0, priority=60000,vlan_tci=0x0000,dl_type=0x88cc actions=CONTROLLER:65535
cookie=0x0, duration=3.131s, table=0, n_packets=0, n_bytes=0, priority=0 actions=CONTROLLER:65535

Although the two sequenced policies are the same, there are actually two different entries installed in the flow table. Is it normal?

I hope I was clear enough. Thanks in advance, Daniele

[joshreich]

This isn't a correctness issue, but it does indicate that one of our compilation optimizations (shadow deletion) is missing a corner-case. I'm assigning this to @SiGe as well, though it's lower priority.

[SiGe]

Hello @danieledc,

Thanks for posting these issues!

Which two entries that are installed on the flow table are redundant? Are you referring to the two drop rules (priority:59996, 59997)? Or do you have something else in mind?

This policy:

def main():
    return match(switch=2,dstmac="00:00:00:00:00:02")>>fwd(2))

would generate the same flow table with the exception of one drop rule (priority: 59997).

priority=60000,dl_type=0x88cc,actions=CONTROLLER:65535
priority=59999,in_port=2,dl_dst=00:00:00:00:00:02,actions=IN_PORT
priority=59998,dl_dst=00:00:00:00:00:02,actions=output:2
priority=59997,actions=
priority=0    ,actions=CONTROLLER:65535

If this is the case, one solution would be to delete rules that are immediately followed by lower priority rules that 1. cover them and 2. have the same action? Any thoughts @joshreich ?

[SiGe]

I am just reposting the two different tables, so it would be easier to compare them.

priority=60000,dl_type=0x88cc                     actions=CONTROLLER:65535
priority=59999,in_port=2,dl_dst=00:00:00:00:00:02 actions=IN_PORT
priority=59998,dl_dst=00:00:00:00:00:02           actions=output:2
priority=59997,                                   actions=drop
priority=0    ,                                   actions=CONTROLLER:65535

Second table with the extra rule:

priority=60000,dl_type=0x88cc                     actions=CONTROLLER:65535
priority=59999,dl_dst=00:00:00:00:00:02,in_port=2 actions=IN_PORT
priority=59998,dl_dst=00:00:00:00:00:02           actions=output:2
priority=59997,dl_dst=00:00:00:00:00:02           actions=drop
priority=59996                                    actions=drop
priority=0                                        actions=CONTROLLER:65535

[joshreich]

@SiGe the pair of rules in the second table that I'd focus on are

priority=59998,dl_dst=00:00:00:00:00:02           actions=output:2
priority=59997,dl_dst=00:00:00:00:00:02           actions=drop

The higher priority rule completely covers the lower priority rule in matching space, so it doesn't matter what action the lower priority rule has, it can never be hit and thus is redundant/shadowed/unecessary.

[mcanini]

@SiGe, as @joshreich said this is not really a correctness issue as the second rule is completely shadowed by the first. As such this is not a show stopper for us, but we thought the behavior is not exactly what we expected out of pyretic and wanted to make sure you are aware of it. I believe it is a corner case condition.

[SiGe]

@joshreich, @mcanini

That makes sense, but the problem is that the first rule has (switch=2) in it while it is being sequenced while the second one doesn't. So while the sequential compilation is taking place the two rules are different:

dl_dst=..02,switch=2, actions=output:2
dl_dst=..02,actions=drop

They are not shadowed in sequential composition stage. This needs to be addressed in switchify method in runtime.py. Thoughts?

[mcanini]

Well, the seq composition says:

match(dstmac="00:00:00:00:00:02")>>match(switch=2,dstmac="00:00:00:00:00:02")>>fwd(2)

The second match is more specific but completely contained in the first. Once this policy is compiled for switch=2, I'd expect that only one rule is produced.

[joshreich]

@mcanini exactly right. @SiGe that's pretty much correct, though I'd suggest adding a final shadow elimination pass right before classifier installation occurs (e.g., after switchify and other related transformations).

[SiGe]

@joshreich That makes sense. I'll start working on it. For now I'll just add the remove_shadowed_cover_single, which I believe would take care of this case, and down the road, we can expand it with other shadow removal algorithms.

[joshreich]

good plan!

[SiGe]

@joshreich @danieledc @mcanini

I just pushed a new branch with fixes to this issue and https://github.com/frenetic-lang/pyretic/issues/28. The new branch is at:

https://github.com/frenetic-lang/pyretic/tree/issues-daniele