Rootless Router(Part: 3) EtherGuard

前篇: Rootless Router (Part2): BIRD-vpp
前情提要: 總之BIRD確定了要用python糊以後,我就來決定來搞多節點互連了

Mesh VPN

我決定弄一個layer 2 的mesh VPN,用於我之後會架設的多個節點之間的互聯。

至於為什麼我要自己弄這個VPN呢? 
首先,因為幾乎沒見到別的VPN軟體支援VPP
VPP雖然有內建VPN,但是沒有一個支援udp打洞

我想要有一個VPN能夠用在VPP上,又能夠udp打洞,似乎只能些修改/重寫了

比較過幾個,最後還是決定以go語言為基礎
因為之前弄wireguard-go-vpp的時候,go語言下的libmemif環境都弄好了

如果要基於C++的改成memif後端,不知道環境又要搞多久

順帶一提,go語言的環境設計,真的太神了,不得不吹
不像C++有各種路徑要設定,ld_library_path,還有gcc加上LDFLAGS之類的設定
還有namespace的問題,C++的include真的就只是單純把那段code貼到#include的地方
這個設計,簡單是很簡單,但是各種變數汙染也是不好弄

go語言就方便多了。go get XXX,go mod vender,所有需要的檔案通通搬去vender子資料夾
mod之間也不會互相汙染,真是太神奇了! go語言萬歲!

EtherGuard

花了半個月,我終於寫完了!
最後我決定把新弄得VPN取名叫做Etherguard。為什麼叫做Etherguard呢?
是因為code是從wireguard-go改來的,所以加密方法,header之類都和wireguard一樣,就取guard部分
又是二層VPN,layer 2又叫Ethernet。就取Etger的部分。組合再一起變成Etherguard

而且我想順便引入單向延遲選路的功能

OSPF能夠根據cost自動選路
但是實際上,我們偶爾會遇到去程/回程不對等的問題
之前我就在想,能不能根據單向延遲選路呢?
例如我有2條線路,一條去程快,一條回程快。就自動過去回來各自走快的?

而且市面上也完全沒有類似的VPN軟體能做到這點(或是我不知道)
因為這個我開始擔心了。因為測量單向延遲是不可能的
難道要做出有上述效果(根據單向延遲選路)的VPN是不可能的?

單向延遲選路

於是我又在想了,有時鐘誤差下的單向選路會work嗎?

我又左思右想,我想通了!
就算時鐘有誤差,而且是任意誤差,選路結果永遠是對的!
也就是這個做法可行!

證明:

首先我們知道「選路」的定義是
「在一張有向有負權,但無負環的圖中,選定起點和終點。
在所有的可能路徑中,找出cost最短的路徑」
然後我們使用單向延遲作為邊的cost。

單向延遲的測量很簡單
我們把我們發送訊息的時間送出去,對面收到訊息的時候和她的時間相減,就能知道時間差了
比如我8/25送出訊息,把寄件日寫在信裡。
對面收到的時候看到自己是8/30,就知道運送過程花了5天

難點是如果雙方時鐘不同步,算出來的結果就不準了。
例如我8/25送信,但與此同時對方日歷還在8/19。那她8/30收到信的時候,日歷還是8/24!
現在是8/24,看著8/25送出,相減花了-1天抵達,這郵差還真快啊!

首先

我們假設以下情況,中間時鐘不準確,起點&終點時鐘都是準的,如圖所示

圖(一)
假設我們只考慮
A→B→E
ACE
A→D→E
這三條路徑。選路會從這三條路徑中選出cost最少的

然而C的時鐘是錯誤的,假設慢了n毫秒
這就會導致所有的紅色邊的測量結果減少n毫秒
但是與此同時,藍色邊的測量結果會增加n毫秒

我們可以看到,ACE經過一紅一籃,測量延遲剛好抵銷
不難推廣A→E,不管是任意路徑,經過紅藍的次數一定一樣,因為有進就有出嘛
無論中間節點的時鐘怎麼誤差,最後選出的路徑並不因此影響

再來

我們考慮這種情況,起點和終點時間不準,中間的時鐘都是準的


圖(二)
一樣我們只考慮
A→B→E
A→C→E
A→D→E
這三條路徑。選路會從這三條路徑中選出cost最少的

會發現無論m和n是多少,排名永遠不會發生變化
雖然每條路徑的測量結果都不正確,但cost最少的還是最少,最多的還是最多
不難推廣A→E,不管是任意路徑,一定只會經過一紅一藍,造成等量的影響

為什麼只會經過一紅一藍呢?
因為可以證明,任意不只一紅一藍(例如二紅一藍)的路徑,必定存在更佳路徑。
你想嘛,要出現這種情況,一定是封包繞一圈回原點,再前往目的。
怎麼可能有繞一圈比不繞更好的?除非圖中出現了負環
所以這個證明就差一點,就是證明這種情況不可能出現負環。
我想到了一個非常美妙的證明,可惜這裡空白處太小,寫不下

因此無論起點終點的時鐘怎麼誤差,最後選出的路徑都是同一條

結論

不會因為中間的時鐘錯誤發生變化 + 不會受到起點終點的時鐘誤差影響 = 時鐘可以亂跑不重要
我覺得這個理論很完美!!

如果有任何bug,麻煩盡快告訴我!!!
我都弄完了才發現不能用的話,我會很難過的

EtherGuard介紹

所以我就開始弄我的Etherguard,目前完成度已經差不多了。
我這個etherguard,設計上有3種模式

1: Static模式

Stati模式下,最類似於原本的wireguard。
沒有自動選路,沒有握手伺服器。
一切都要提前配置好

使用前要先手動計算轉發表。也可以用工具來算
etherguard也能幫忙算,請先準備類似這樣的文字檔
path.txt
就能輸出etherguard要的轉發表了
NextHopTable

這張表其實蠻好懂得對吧?就是map[起點][終點]=嚇一跳。

2: Super模式

受到n2n的啟發,分為super node和edge node。
全部節點會和supernode建立連線,藉由supernode交換其他節點的資訊,以及udp打洞

但是我這個和n2n不一樣
super node不負責轉發封包,單純負責
  1. 分發其他edge node的資訊,幫忙互相udp打洞
  2. 接收edge node發來的延遲資訊,計算轉發表,再分發給全部的edge node
如果妳很多機器都是Symmetric NAT,想要同時負責握手和打洞
請在那台VPS裡面同時運行super node和edge node
而且注意中轉VPS的edge node不要用127.0.0.1去連線super node,請用真實ip
不然super node看到封包來自127.0.0.1,就會把連線地址127.0.0.1分發給其他edge node,造成連線不到

3. P2P模式

受到tinc的啟發。每個節點都類似super node
會定期廣播自己所有已連線節點的連線ip:port,公鑰和preshared key。
每個節點會計算自己的轉發表,以及廣播延遲之訊讓其他節點也能計算轉發表
但是這個模式還沒測試過就是了,穩定性不知如何。有興趣的話可以幫忙測試

程式邏輯

上面那些是大致的運作原理,具體的程式邏輯目前如下
Edge node:
啟動:
  if Super==true =>發送register(NodeID)
  if P2p==true => 發送queryPeer(NodeID)
  
Loop定時執行:
  發送Ping(time.Now())
  if Super==true => 發送register(NodeID) 讓super node知道自己活著
  if P2P==true =>   發送BoardcastPeer(0) ,交換節點資訊。
                    如果多人有共同節點,就會因為封包長一模一樣,觸發Dup節省流量
  NTP更新時間
  
接收封包事件:
  封包類型:
    Boardcast   -> 跑根據轉發表,不重複路徑廣播
    
    ControlMsg  -> 如果P2P=true,就flood廣播,讓所有節點都收到
       |           廣播完以後,還會根據類型作對應處理
       |           如果P2P=false,直接丟棄不理
       |           會紀錄hash。之後hash重複就觸發Dup丟棄,避免環路
       |
       ├有以下3種類型,對應處理如下
       ├Pong      -> 更新延遲轉表,跑floyd warshall,重新計算轉發表
       ├QueryPeer -> 發送BoardcastPeer(req.NodeID),把自己全部的已有節點都廣播一遍
       └BoardcastPeer->自己peer list沒有她就加入,同時發送一個ping給對方來打洞
       
    Ping   -> 和自己的時間相減,計算timediff。,也就是單向延遲
              產生一個pong(p.ID, MyID, time.Now().Sub(p.Time))封包。裡面夾帶了時間差
              ├ 如果Super==true => 發給super node
              └ 如果P2P == true => flood廣播發給全部人
              
    SuperMsg  -> 僅限Super=true有效 else 丟棄
        ├UpdatePeer   => 用HTTP API(u.state_hash)去下載全部的node資訊。自己沒有就加入,自己有的就更新
        └UpdateNhTable=> 用HTTP API(u.state_hash)去下載轉發表,覆蓋掉自己的轉發表
    NormalPacket
        ├ dstID == MyID => 接收,丟給tap網卡
        └ dstID != MyID => 根據轉發表來轉發
        
Super node:
  HTTP API:
    ├---get_neighbor(state_hash) 給她全部的peer資訊 更新該節點的state_hash
    └---get_route(state_hash) 給她轉發表 更新該節點的state_hash
  Loop定時執行:
   └檢查全部節點的state_hash,和自己不一樣就發給她UpdatePeer(state_hash)或是UpdateNhTable(state_hash)
       等她呼叫HTTP API來要資訊
    
接收封包事件:
  封包類型:
    Pong:
      ├---跑floyd warshall,更新轉發表
      └---如果轉發表有變動,發布UpdatePeer(state_hash)
    Register
      └---如果peerlist發生變動,發布UpdateNhTable(state_hash)還還有些可以

花了半個月,我終於搞定了!
有興趣朋友的可以去我的github下載來玩
還有些可以改進的地方,而且也還沒有大規模測試,可能有bug。
不過先暫時就這樣吧

要完成我的Rootless Router計畫,還有別的東西要搞。

還缺少自動peer,python寫的路由同步腳本,還有基於git的設定檔同步腳本之類

不然節點太多,設定檔還要一個一個調不太現實

留言