化身OLSR協定進化版　BATMAN路由巧妙運作

BATMAN路由協定簡介

BATMAN是Better Approach To Mobile Ad-hoc Networking的英文縮寫，縮寫剛好與蝙蝠俠一模一樣，但是卻完全沒有任何關聯，當然可能也因為縮寫剛好與蝙蝠俠一樣，在官方網站中也放上了蝙蝠的圖示。

BATMAN路由協定最主要的設計概念是，希望把整個路由資訊散布在整個網路的各個角落，也就是將路由資訊「去中心化」，所以沒有任何一個網路節點擁有所有的路由資訊。這樣設計的好處是，再也不需要把所有網路上的改變一直想辦法同步到整個網路的每一個節點。當收到一個網路封包的時候，每一個網路節點只需要知道要把封包送到哪個方向就可以。整個設計的主軸概念圍繞著Collective Intelligence出發，也就是「集體智慧」。

BATMAN設計的目的在於改善並取代原本的OLSR路由協定，由於其優異的設計表現，Linux作業系統在2.6.38版時就已經支援BATMAN路由協定。BATMAN路由協定是由一個德國Freifunk社群所開發以及維護，目前最新的版本是今年四月所推出的2018.1版本。

何謂OLSR路由協定

在講解BATMAN網路協定之前，先來了解它所要取代的OLSR協定到底是什麼，而為什麼又要取代OLSR協定。

小標OLSR運作方式說明

OLSR全名是Optimized Link State Routing，基本上，OLSR協定使用Hello封包以及拓撲控制（Topology Control）封包，來查找可能的網路路徑。行動Ad Hoc網路中的每一個網路節點用這樣的方式來決定如何轉發網路封包。

Hello封包用途是連結狀態偵測、附近節點偵測等等，這種封包會用來偵測當前節點開始往外算兩個節點的距離，同時也會用於選擇MPR。而拓撲控制封包，則是用來傳送網路拓撲的資訊。

OLSR路由協定必須在眾多節點中，選出幾個所謂的Multipoint Relays（簡稱MPR）。只有這些MPR才可以發送及轉發拓撲控制封包。這也是OLSR協定的特別之處，因為這個協定把這種拓撲控制封包限定在MPR節點上，以便於減少網路上封包數量，降低廣播所帶來的影響。

也只有MPR知道如何去計算最佳路由，所以剛才提到的拓撲控制資料只需要在MPR之間做分享即可。當然，OLSR也可以使用預設路由，藉由HNA網路封包放入OLSR MANET雲端即可。

在2014年時，已經公布了OLSR第二版，主要的差異在於NHDP（用於Neighborhood Discovery）以及更彈性化的模組設計方式。而原本的MPR選擇方式與運作模式沒有什麼改變。

進化版Link-State路由協定

剛才提到OLSR全名是Optimized Link State Routing，顧名思義，它是一種進化版本的Link-State路由協定，而進化的緣由就是為了行動Ad Hoc網路。

什麼是Link-State路由協定呢？路由協定有很多種分類方式，依據所影響範圍可以分成內部路由協定（Interior Gateway Protocol，IGP）和外部路由協定（Exterior Gateway Protocol，EGP）兩大類型。對內部路由協定而言，依據所採用的路由演算法來區分的話，有三種主要的類型，包括Distance Vector、Link State以及混合前面兩種的方法。

簡單來說，Link-State路由演算方式是，網路上每一個節點（也就是路由器）都會擁有自己一份的「網路地圖」，這份網路地圖顯示著從自己這個節點到網路上任何一個節點的最佳路線，而這些最佳路線都是計算出來的，所以每個節點的地圖不見得相同，也不彼此分享，這份網路地圖就是Routing Table。

所謂路由演算法，就是如何選擇網路路徑以便於發送網路封包。而Link-State路由演算法，其實就是使用所謂的最短路徑優先（Shortest Path First，SPF）演算法來決定網路路徑。顧名思義，就是以最短的網路路徑為最佳網路路徑的優先考量，Link-State路由演算法就是用這種方式來維護其存放網路路徑的資料庫內容。

為什麼說OLSR是Link-State網路協定的進化版本呢？從稍早的解釋可以看得出來，OLSR透過MPR的設計來盡量減少網路廣播對網路所帶來的影響，而網路廣播的目的就是在於分享並且學習網路拓撲和路由資訊。

而原本比較初期的Link-State路由協定，例如OSPF協定或是IS-IS協定，都會使用Flooding方式來大量廣播封包，以便於將拓撲資料庫做更新的動作。雖然OSPF協定只有當網路變化的時候，才會開始觸動更新動作（透過所謂的LSA網路封包），而且其實是透過群播（Multicast）的方式來對整個所在網路做發送的動作。

但是，OSPF協定與OLSR相比，還是多送了許多網路封包，因為所有的Link-State路由器都會觸動這樣的更新動作，OLSR則只有MPR才會需要負責這樣的更新。

OLSR協定的缺點

雖然OLSR協定已經改善了一般Link-State路由協定的缺點，但是用在變化性高的無線Ad Hoc網路時，卻不是那麼地完美。

舉例來說，OLSR的MPR節點需要花不少電力來計算最佳路徑，而這件事情在有線網路中不會是什麼太大的問題，因為一般有線網路的節點設備一定都會持續連接著電力，CPU運算能力也比較高。可是無線網路，尤其是移動Ad Hoc網路的移動式設備，不會持續接著電力來源，所以極有可能因為扮演著MPR而快速地喪失電力。

另外，OLSR協定預設上其實根本沒有考慮連線品質這件事情。雖然有使用Hello訊息來確認是否收得到，但是卻沒有考慮中間的品質如何，尤其是當無線網路的品質沒有有線網路品質來得穩定的時候。

當然，如果是在封包丟失率很高的無線網路環境內，還會因為網路的不穩定，導致一直花很多心力在重選MPR，然後MPR之間又要一直同步拓撲控制資料，整個就會造成不少問題。

所以整體來說MPR似乎在OLSR協定之中算是一個雙面刃，它的設計解決了原本一些問題，但是同時也造成新的問題。但是並不是說OLSR協定沒有它的好處，OSLR會比較適用於穩定性高的網路環境，而在MPR的設備可能需要稍微好一點。

BATMAN協定的運作方式

由於OLSR協定可能的缺點，在2007年，開始產生了BATMAN協定的發想。現在新版本的BATMAN協定運作在網路七層協定的第二層（原本運作在第三層）。如果去搜尋的話，或是去官方網站查看，會發現BATMAN模組會在後面加上-adv這樣的字眼，就是代表BATMAN的Advanced版本。BATMAN不只是單純去發送UDP而已，這個路由協定會建立並且使用虛擬介面，當然網路封包在真正傳送出去的時候，還是必須與實際的網路介面做綁定（Binding）。

另外，較早版本的BATMAN協定並沒有好好考量到有些網路連線只是單方向，並非雙向可通的情況。後續版本已經將單向網路的情況摒除在外。比較新的版本也可以在比較高的程度之中，與其他非BATMAN的網路做整合。

在BATMAN協定的網路中，各個節點會定期發送OMG封包進行網路訊息的交換，而這樣的封包只會傳送給附近節點，因為BATMAN主要設計是在無線網路的環境內，所以這代表節點之間的網路連線不像是有線網路那樣地穩定，因此這些OMG封包有時效性，以便於分辨哪些資訊是比較新，哪些比較舊。

每個節點其實算是只知道自己附近節點的路由資訊，而不用收集整個網路的路由資訊。所以一旦要發送網路封包的時候，重點是要知道方向在哪裡，要往哪邊送，然後把封包傳送給下一個節點，再重複一樣的過程，直到處理的節點就是目的地為止，這概念其實就像是Distance-Vector路由協定一樣。

有一種實驗性質的路由系統稱之為Netsukuku，其目的和BATMAN路由協定頗為類似，之後有機會筆者再為各位介紹。

集體智慧的表現

在BATMAN協定的網路中，因為其去中心化的設計，讓各個網路節點透過提供部分路由資訊來完成整個網路路由動作。十幾年前甚至更久以前，網路世界中充斥著許多Server-Client架構的設計，也就是中心化設計，無論是軟體的設計，到網站的概念（例如大多網站都是以伺服器提供服務為主，例如各大入口網站，比較缺少網路社群一同提供內容服務的力量）都是一樣，在網路協定中，也是差不多。而BATMAN路由協定則透過所謂的「集體智慧」讓各個節點一同努力，去中心化地完成整體所需要的服務。

集體智慧，英文稱之為Collective Intelligence，其概念就是集結眾人的力量完成特定的目標或是做出決策，或是提供特定的服務。維基百科就是一個很好的範例，當然這篇所提到的BATMAN網路協定也是一樣。

BATMAN網路協定除了使用Collective Intelligence的概念之外，另外一個就是使用最近很紅的「區塊鏈」之中心思想：「去中心化」的概念。由於無線網路的連線品質不確定性，以及高度網路變化性，BATMAN去除了中心管理路由資料的概念，讓整個路由資訊透過剛才所提到的集體智慧來呈現，是一種非常有趣的設計理念，至於網路效率為何，那就等大家實際去體驗了。

結語

看過這篇文章後，相信大家已經大略了解BATMAN路由協定的背景，明白它的定位、緣由與設計理念、運作方式等等。本文同時介紹了OLSR路由協定的好壞，可以用來比較。在無線Ad Hoc網路中，充斥著許多在有線網路中沒有意料到的問題，尤其是網路的高度變化性，當然還有各個設備的電力與計算能力等問題。透過這裡的介紹，希望能讓大家有更多的了解。之後還有機會的話，再為各位介紹ABR，甚至於相關的Netsukuku路由系統等等。

＜本文作者：胡凱智，目前在Solera Holdings Inc.擔任亞太區首席技術長，曾於美商Mozilla擔任全球技術專案總監，並在趨勢科技任職七年多，有兩年美國矽谷工作經驗，在美國專利局擁有軟體專利。讀者交流建議：https://www.facebook.com/khu.page＞