資訊專欄INFORMATION COLUMN
摘要：目前版本的采用的是第三種查詢方式，也就是結合和，其中作為一級，作為二級，此時中存放的不再是多級流表返回的結果，而是上一次在中命中的索引。
背景
在ovs交換機中，報文的處理流程可以劃分為一下三個步驟：協議解析，表項查找和動作執行，其中最耗時的步驟在于表項查找，往往一個流表中有數目巨大的表項，如何根據數據報文的信息快速的查找到對應的流表項是ovs交換機的一個重要的功能。
在openflow協議中，支持多級流表的形式，可以類比于將一個復雜的功能進行打散，分解成過個小的功能，實現一個流水線的功能，具體見下圖：
上圖中可以看到，一個數據報文進入后，會經過多個流表，每個流表負責特定的功能，比如上圖中table 1中的流表項只會與數據報文中L2層的信息進行匹配，多個流表的處理使得整個數據報文的查詢形成一種流水線的處理方式。
ovs流cache設計首先需要明確的是，ovs中的多級流表存放在用戶空間，內核態存放的是流表的緩存，數據報文進入ovs的時候，首先會查詢內核態的緩存信息，如果命中則直接執行相應的動作，否則通過netlink的方式發送到用戶空間，用戶空間查找多級流表，如果用戶態命中則將對應的信息丟給內核態進行緩存，否則查詢不到，用戶態還要繼續將報文的信息丟給控制器，由控制器下發對應的規則，有關ovs和控制器之間的關系可以參見我的上一個博客。
ovs中關于流表的查詢經歷了三個過程：
microflow cachemicroflow cache的思想十分簡單，具體見下圖：
多級流表的查詢過程中，會將報文與每個流表的每個流表項進行匹配，這個過程中耗費的時間是很大的，microflow cache的想法就是將多級流表查詢之后的結果按照一定的表項格式直接緩存到內核態中，然后下次同樣的數據報文到達時，直接通過hash的方法在內核態中命中，第二次的時間復雜度為$O(1)$，
microflow cache的缺點也很明顯：
實際存在很多short-lived類型的流量，導致命中率低
由于Mircroflow Cache 基于Hash的精確匹配查表，數據頭中微小的改動都會導致無法命中cache（如TTL）
Megaflow Cache雖然基于microflow cache的流表查詢方式，能讓數據報文第二次命中的時間復雜度達到$O(1)$，但是其真正的性能瓶頸在于用戶空間的查詢，如何減少數據報文進入用戶態，是一個很重要的問題。
為了解決精確匹配的問題，減少數據報文進入用戶態，ovs采用了megaflow cache代替了microflow cache的匹配方式，megaflow cache是一種基于TTS（元組空間搜索算法）的實現方式，采用了模糊匹配取代microflow cache的精確匹配，通過增加在內核態中查詢的時間（從1次hash查找到k次，仍然是常數時間內，跟TTS算法中表的數量有關），減少數據報文進入用戶態的次數，具體會在TTS算法中解釋。
一種樸素的megaflow cache實現方式就是，將所有多級流表的級聯結果存放在內核態中，如下圖：
內核態中存放著一張所有流表級聯之后的大表，顯而易見，這種做法簡單粗暴，但是內存的開銷也是巨大的。
一種好的做法是，采用’Lazy‘的方式，如下圖所示，數據報文首先通過模糊匹配的方式檢索內核中的表，如果所有的表都無法命中，則查詢用戶態，然后將用戶態的查詢出的所有表項合并成一條表項，再插入到內核態的表中。
需要注意的是，上圖中megaflow cache是一張表，在實際的ovs實現中，因為采用了TTS，所以megaflow cache是多張表形成的鏈表。
microflow cache+Megaflow Cache目前版本的ovs采用的是第三種查詢方式，也就是結合microflow cache和Megaflow Cache，其中microflow cache作為一級cache，Megaflow Cache作為二級cache，此時microflow cache中存放的不再是多級流表返回的結果，而是上一次在Megaflow Cache中命中的索引。
數據報文到達時，首先通過對報文信息hash，查詢microflow cache中是否存放著對應的hash值，如果存在則查詢對應hash值所指向的索引，這個索引用來定位對應的Megaflow鏈表中的某一個元素表，然后再在這個元素表中進行查找。
整體的解釋起來可能有點拗口，本人也是第一次寫博客，對ovs了解的也不夠深入，其中涉及到很多細節也不是很清楚，希望通過分享的形式同大家交流。
參考資料
[Pfaff B, Pettit J, Koponen T, et al. The Design and Implementation of Open vSwitch[C]//NSDI. 2015, 15: 117-130.](https://www.usenix.org/system...
Open vSwitch流表查找分析
The Design and Implementation of Open vSwitch 作者演講ppt
作者：yearsj
轉載請注明出處：https://segmentfault.com/a/11...
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/25238.html
摘要：需要修改數據包的二層源目地址以及三層包頭的因為路由是逐跳轉發的，每一跳都需要做這些工作，即使是現在通過流表轉發，中間的轉發器直接轉發報文，到達倒數第一跳的時候還是需要把數據包的目的地址修改為接受端的地址。 前言 熟悉這款設備的同學，應該也快到不惑之年了吧！這應該是Cisco最古老的路由器了。上個世紀80年代至今，路由交換技術不斷發展，但是在這波瀾壯闊的變化之中，總有一些東西在嘈雜的機房...
摘要：需要修改數據包的二層源目地址以及三層包頭的因為路由是逐跳轉發的，每一跳都需要做這些工作，即使是現在通過流表轉發，中間的轉發器直接轉發報文，到達倒數第一跳的時候還是需要把數據包的目的地址修改為接受端的地址。 前言 熟悉這款設備的同學，應該也快到不惑之年了吧！這應該是Cisco最古老的路由器了。上個世紀80年代至今，路由交換技術不斷發展，但是在這波瀾壯闊的變化之中，總有一些東西在嘈雜的機房...
摘要：需要修改數據包的二層源目地址以及三層包頭的因為路由是逐跳轉發的，每一跳都需要做這些工作，即使是現在通過流表轉發，中間的轉發器直接轉發報文，到達倒數第一跳的時候還是需要把數據包的目的地址修改為接受端的地址。 前言 熟悉這款設備的同學，應該也快到不惑之年了吧！這應該是Cisco最古老的路由器了。上個世紀80年代至今，路由交換技術不斷發展，但是在這波瀾壯闊的變化之中，總有一些東西在嘈雜的機房...
閱讀 2089·2021-11-24 10:34
閱讀 3064·2021-11-22 11:58
閱讀 3723·2021-09-28 09:35
閱讀 1736·2019-08-30 15:53
閱讀 2788·2019-08-30 14:11
閱讀 1561·2019-08-29 17:31
閱讀 548·2019-08-26 13:53
閱讀 2151·2019-08-26 13:45
