[ovs-discuss] OVS Tuple Space Searching Algorithm

pei Jikui jkpei at hotmail.com
Wed Jun 12 03:57:51 UTC 2019


HI,

I am trying to understand how the Tuple Space Searching works in vswitchd when it tries to search an openflow rule for the upcall packets.

Following is my understanding about the procedure. I am not sure if the understanding is right or not since I couldn't understand well how the tss hash tables work together with the trie trees.


1)    The data structures.



[cid:113ac556-883d-4c04-9d0d-25083c406333]

     *   For every openflow table, there are several sub-tables each one has the same mask for rules.
     *   For staged search purpose, in each sub-table, there are 4 hash tables which are built based on the meta, meta+l2, meta+l2+l3, meta+l2+l3+l4 respectively.
     *   For prefix tracking purpose, in each sub-table, there are 2 or 3? Prefix trees which are used to track the source-ip, dest-ip fields? ( from the source code, it seems we have 3 trie trees? What's the other items is tracking by the trie tree besides the source ip and dest ip?)


2)    The rule search procedure of each table.

The routine will first search the four hash tables and find the rule. Then use the prefix trees for the prefix tracking purpose which will potentially reduce the flow entries in datapath?  Is this right or not? What's the right procedure of the matching if the answer is no?


Thanks


Jikui

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openvswitch.org/pipermail/ovs-discuss/attachments/20190612/71864a55/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Screen Shot 2019-06-12 at 11.40.45 AM.png
Type: image/png
Size: 102030 bytes
Desc: Screen Shot 2019-06-12 at 11.40.45 AM.png
URL: <http://mail.openvswitch.org/pipermail/ovs-discuss/attachments/20190612/71864a55/attachment-0001.png>


More information about the discuss mailing list