路由表實作的一些想法

Trie樹路由表其實不是很複雜，沒有必要看懂linux代碼，了解思想就可以了，如果想要簡單一點的，就找找最新BSD的實作，就是去掉了 linux-trie樹的動态維護，對于ipv4就是将位址分為按照8位分為四個段，然後按照每個段查找，如果你的機器有多個處理器或者處理器核心，這樣可以充分利用多處理器的優勢，如果你了解MMU的“頁目錄->頁中間目錄->頁表”方式，我想這個對每個人了解不是很難，MMU不就是将32位的虛拟位址分解為“高10位，中10位，低12位”，然後按照三部分查表的嗎？效率沒得說吧，如果你把ip位址也按照一些規則分成不同的部分，用類似于MMU的方式不就可以了嗎？另外MMU中還有倒排表，cache查詢等等都可以借鑒啊。如果ip位址數量很大，這樣的話用hash就會帶來很多的碰撞，一般的大型路由器都是用上述的trie樹實作的，隻不過它們trie樹的實作都不同，在硬體中就是固定的分段(類比MMU硬體的位址轉化時的查表)，軟體中可以采用動态方式，比如linux的trie的方式。另外，即使用位圖實作精确查找，在機器不支援向量指令的情況下，比較也還是一位一位進行的，充其量可以利用緩存，大型向量機的處理方式就是分段然後多處理實作的，隻不過那是硬體。對于trie樹實作的路由表，可以降低樹高，不必非要8位一層，另外可以用多處理器，比如8位一層，系統有6個cpu，對于處理ipv6位址每個cpu算8位，最後它們簡單的一組合就成了，再者說不用這麼多層，不是還有hash麼，trie的作用僅僅是使資料分布更均勻；另外就是不能絕對的兼顧時間複雜性和空間複雜性，有時候必須有所取舍，總之可以讓hash和trie合二為一，trie樹實作ip位址的均勻分布，避免由于分布不均造成hash碰撞，然後在各個trie節點下面用hash實作精确比對，其實這就是hash-tree。

 本文轉自 dog250 51CTO部落格，原文連結:http://blog.51cto.com/dog250/1274142