..

SDN Exp#4 log

第四次實驗和之前的不太相同，並無真正自己需要實現的東西，主要是針對开源的一個實現 Veriflow 的項目進行閱讀理解。

在實際網絡中，由於人為因素添加或删除流表常常出錯，Veriflow 的大致思想就是在下發流表前對其進行檢驗，並予以反饋，遮樣錯誤的規則被提前找到後就可避免其下發造成網絡故障。

其原理主要依賴兩個思想：

等價類：雖然網絡中數據包的種類有很多，但若對於兩個不同的數據包，其在所有交換機上的轉發行為都相同，那么就可將其視為同一類，遮樣網絡中「不同數據包」的數量暫時就不会太多。具體維護用的 Trie 樹。

增量算法：每次增加或者删除規則時，並不會有太多等價類受影響，於是祗要處理受影響的那些等價類即可。

實驗源碼的思路，每增删一條規則：

  1. 先計算受影響的等價類；
  2. 對每個等價類生成轉發圖；
  3. 遍歷轉發圖以進行對規則的檢驗。

基础實驗

基础實驗要求打印一些信息量，而後解釋補丁的作用。對信息量的輸出要求，簡單模仿一下就行。

該實驗並非完全在原項目中执行，學校給出了一個補丁。

雖然補丁相較於源碼有七没八的修改很多，但關鍵在於在 Rule 中加入新成員 in_port 而後在 VeriFlow::traverseForwardingGraph() 中加入了上一跳的信息進行轉發驗證。

要理解為何如此處理首先得理解未打補丁前代碼的邏輯：在同一個等價類中，對于遍歷過程中的每個點，都按照流表規則中優先級最髙者轉發至下一個點。在中間過程處理網絡故障。

遮樣的思路我覺得並没有問題，那麽實驗中補丁何用？關鍵在於實驗中流表下發的方式，如其在 shortest_path 中：

for node in port_path:
    in_port, dpid, out_port = node
    self.send_flow_mod(parser, dpid, pkt_type, "10.0.0.0/24", "10.0.0.0/24", in_port, out_port)
    self.send_flow_mod(parser, dpid, pkt_type, "10.0.0.0/24", "10.0.0.0/24", out_port, in_port)

可以看到流表來回的路上都發了，但是請注意，其 ip 均相同，簡單來說在該實驗中遮两者被劃到同一等價類。那麽在此等價類，對於路徑上的某个點 $B$，其有兩條優先級相同的規則，那麽它會選擇其中某一條，那麽此時在遍歷等價類過程中，$A$ 由規則轉移至 $B$，那麽 $B$ 是有可能再發回 $A$ 的，那麽可能一下子就有環路了。

所以補丁就是為了解決該問題，解決的思路亦很簡單，如果剛从 $A$ 走到 $B$，$B$ 就不再走回 $A$。具體方法就是對規則選擇進一步的限制，限制 in_port，在 in_port 為接收上一交換機數據包的端口的規則選擇優先級最高的作為當前的轉發規則。但遮樣的思路一旦被加入，則可能出現新的黑洞，遮是由於匹配上該 in_port 的規則可能一條都没有。

需要注意的是，由於當前轉發依賴了 in_port，那麽路徑中如果出現重復點將不意味著一般的環路，遮是由於重復點後由於 in_port 不同下一跳會脫離遮個環。另外要注意發現重復點不意味該路徑上所有點都在環路上，要過濾掉之前的點：

if(visited.find(currentLocation) != visited.end())
{
    // Found a loop.
	...
    int idx = 0;
    for (; idx < seq.size(); ++idx) {
        if (seq[idx] == currentLocation) break;
    }
    for (; idx < seq.size(); ++idx) fprintf(fp, "%s -> ", seq[idx].c_str());
    fprintf(fp, "%s\n", currentLocation.c_str());

    ...

    return false;
}

拓展實驗

拓展實驗在兩部分，一是性能優化，二是修複細節問題。

對於遮個性能優化我覺得真的無意義。因為實驗中提供另外的一個規則下發文件，使規則數大增，最後速度變慢了上百倍，由於每次影響的等價類僅有三，我本已為是增量算法寫掛了，但是發現不是。是因為一个用於記錄錯誤等價類的名為 faults 的 vector 每次都遍歷了一遍，而 $\vert faults\vert$ 最後增到 $25k+$…也就是說本來應當是每次花費差不多的時間，而後優化其它部分，但在該實驗，faults 成為了瓶頸，無論怎麽優化，最後時間都在此被限制。

修複問題，前幾天考天才的無意義機器學習，没時間認真看源碼並且也懶得混分了（主要原因），就做了指導書上提示有問題的部分，也是 faults。

faults 用於記錄出錯的等價類，每當規則加入或者删除時，等價類發生了改變，需要將無效的先從 faults 中删去，遮些就是當前受影響等價類的子集和超集。在遍歷中找到問題加進去就好了。

實現中我用了 set，需重載全序的半序关系。複雜度仍不佳，$O(n\log n)$，$n$ 為 faults 大小。關鍵在於找不到好的方法去實現超集子集的快速檢索，實驗中的等價類劃分依據十四維的偏序。如果是一維的那確實可做，然而…

參考

SDN 實驗至此悉數完成，課程也落下帷幕，實驗還是很有意義的，值得嘗試。代碼放在了 github 倉庫中，歡迎交流。