User login

Weekly Report

03

May

2016

Spent the better part of this week reviewing literature and thinking about the best starting point and the first issue to tackle.

CacheFlow gives a good outline of building dependency graphs, and the header space work it builds it's solution upon seems like a good approach. That is to look at packet headers as a series of bits rather than a set of fields. If I take this approach I will have to extend the solution to deal with multiple tables. Alternatively the FlowAdapter of normalising to a single table is still a possibility (some type of dependency graph is part 1 of this step anyway). My current thinking is that a dependency graph is likely to result in better optimisations than one big table, which would essentially have to be undone when placed back onto a multi-table switch.

I looked at the state of the art of minimising TCAM entries, most work particularly in the past have been on prefix based optimisation (as is seen in routes etc). More recently OpenFlow has sparked interest in generic TCAM rule optimisation (with out the prefix restriction), currently there appears to be only a single online solution currently. I don't think this is going to be a main area of my research, however if I have the time I could try an existing solution at in the pipeline directly before installing on the switches.

I read a few related papers which focused on spreading rules amongst multiple switches. These tend to be limited to only spreading the policy not the forwarding, and tend to construct subset of rules in such a way that order does not matter. Allowing the rules to be placed in any table along a packets path. This restriction is not needed within the bounds of a single switch as the order of tables is known and there is essentially only a single path. As such while interesting and useful as inspiration for algorithms, without the order restriction it is actually easy to move rules around, lower priority rules can be moved to a later table.