原貼:
廣東省LINUX公共服務技術支持中心
Linux路由表的結構與算法分析
黃日文
路由是網絡棧的核心部分。路由表本身的設計很大情度上影響著路由的性能，並且好的設計能減少系統資源的消耗，這兩方面尤其體現在路由表的查找上。目前的內核路由存在兩種查找算法，一種為HASH算法，另一種為LC-trie算法，前者是目前內核使用的缺省算法，而後者更適用在超大路由表的情況，它在這種情況提高查找效率的同時，大大地增加了算法本身的復雜性和內存的消耗。綜上，這兩種算法各有其適用的場合，本文分析了基於2.6.18內核路由部分的代碼在HASH算法上路由表結構的實現，並且在文章最後給出了一個簡單的策略路由的應用。
一、路由表的結構
為了支持策略路由，Linux使用了多個路由表而不是一個，即使不使用策略路由，Linux也使用了兩個路由表，一個用於上傳給本地上層協議，另一個則用於轉發。Linux使用多個路由表而不是一個，使不同策略的路由存放在不同的表中，有效地被免了查找龐大的路由表，在一定情度上提高了查找了效率。
路由表本身不是由一個結構表示，而是由多個結構組合而成。路由表可以說是一個分層的結構組合。在第一層，它先將所有的路由根據子網掩碼（netmask）的長度（0~32）分成33個部分（struct fn_zone），然後在同一子網掩碼（同一層）中，再根據子網的不同（如10.1.1.0/24和10.1.2.0/24），劃分為第二層(struct fib_node)，在同一子網中，有可能由於TOS等屬性的不同而使用不同的路由，這就是第三層（struct fib_alias），第三層結構表示一個路由表項，而每個路由表項又包括一個相應的參數，如協議，下一跳路由地址等等，這就是第四層(struct fib_info)。分層的好處是顯而易見的，它使路由表的更加優化，邏輯上也更加清淅，並且使數據可以共享（如struct fib_info），從而減少了數據的冗余。
圖1為一個路由表的總體結構。自上而下由左向右看，它首先為一個fib_table結構指針的數組，它被定義為：
每個fib_table結構在內核中表示一個路由表：
圖1（引自[1]）
這個結構中包括這個表的ID，以及主要的一些用於操作路由表的函數指針，這裡我們只關心最後一個域――tb_data[0]，這是一個零長的數組，它在內核中也較為常見，它表示
指向這個結構的末尾。由圖1可以看到，這個結構的末尾接著便是一個struct fn_hash結構，這個結構是隨著fib_table結構一起分配的，所以fib_table->tb_data就是fn_hash。
這個fn_zone域就是我們上面提前的結構，用於將路由根據子網掩碼的長度分開成33個部分，其中fn_zones[0]用於默認網關。而fn_zone_list域就是將正在使用的fn_zone鏈成一個鏈表。接著再深入到struct fn_zone結構中：
這個結構中有兩個域比較重要，一個為fz_hash域，它指向一個HASH表的表頭，這個HASH的長度是fz_divisor。並且這個HASH表的長度是可變的，當表長達到一個限定值時，將重建這個HASH表，被免出現HASH沖突表過長造成查找效率降低。
為了提高查找的效率，內核使用了大量的HASH表，而路由表就是一個例子。在圖1中可以看到，等長子網掩碼的路由存放在同一個fn_zone中，而根據到不同子網（fib_node）的路由鍵值（fn_key），將它HASH到相應的鏈表中。
這個鍵值其實就是這個子網值了（如10.1.1.0/24，則子網值為10.1.1），得到這個鍵值通過n = fn_hash()函數HASH之後就是這個子網對應的HASH值，然後就可以插入到相應的fz_hash[n]鏈表中了。沖突的fib_node由fn_hash域相鏈，而fn_alias則是指向到達這個子網的路由了。
當到達這個子網的路由由於TOS等屬性的不同可存在著多個路由時，它們就通過fib_alias中fa_list域將這些路由表項鏈成一個鏈表。這個結構中的另一個域fa_info指向一個fib_info結構，這個才是存放真正重要路由信息的結構。
這個結構裡面是一個用於路由的標志和屬性，其中最重要的一個域是fib_nh[0]，在這裡，我們再次看到了零長數組的應用，它是通過零長來實現變長結構的功能的。因為，我們需要一個定長的fib_info結構，但是在這個結構末尾，我們需要的fib_nh結構的個數是不確定的，它在運行時確定。這樣，我們就可以通過這種結構組成，在運行時為fib_info分配空間的時候，同時在其末尾分配所需的若干個fib_nh結構數組，並且這個結構數組可以通過fib_info->fib_nh[n]來訪問，在完成fib_info的分配後將fib_nhs域置為這個數組的長度。
另一方面，fib_info也是HASH表的一個應用，結構中存在著兩個域，分別是fib_hash 和fib_lhash，它們都用於HASH鏈表。這個結構在完成分配後，將被用fib_hash域鏈入fib_info_hash表中，如果這個路由存在首選源地址，這個fib_info將同時被用fib_lhash鏈入fib_info_laddrhash表中。這樣，就可以根據不同目的實現快速查找了。
Struct fib_nh也是一個重要的結構。它存放著下一跳路由的地址（nh_gw）。剛剛已經提到，一個路由（fib_alias）可能有多個fib_nh結構，它表示這個路由有多個下一跳地址，即它是多路徑（multipath）的。下一跳地址的選擇也有多種算法，這些算法都是基於nh_weight，nh_power域的。nh_hash域則是用於將nh_hash鏈入HASH表的。
二、路由的查找
路由的查找速度直接影響著路由及整個網絡棧的性能。路由的查找當然首先發生在路由緩存中，當在緩存中查找失敗時，它再轉去路由表中查找，這是本文所關注的地方。
上一節已經詳細地描述了路由表的組成。當一個主要的IP層將要發送或接收到一個IP數據包時，它就要調用路由子系統完成路由的查找工作。路由表查找就是根據給定的參數，在某一個路由表中找到合適的下一跳路由的地址。
上面已提到過，當一個主機不支持策略路由時，它只使用了兩個路由表，一個是ip_fib_local_table，用於本地，另一個是ip_fib_main_table，用於接發。只有在查找ip_fib_local_table表時沒有找到匹配的路由（不是發給本地的）它才會去查找ip_fib_main_table。當一個主機支持策略路由時，它就有可能存在著多個路由表，因而路由表的選擇也就是查找的一部分。路由表的選擇是由策略來確定的，而策略則是由應用（用戶）來指定的，如能過ip rule命令：
如上，第一條命令創建了基於源地址路由的一條策略，這個策略使用了RT1這個路由表，第二條命令創建了基於數據包入口的一個策略，這個策略使用了RT2這個路由表。當被指定的路由表不存在時，相應的路由表將被創建。
第二步就是遍歷這個路由表的fn_zone，遍歷是從最長前綴（子網掩碼最長）的fn_zone開始的，直到找到或出錯為止。因為最長前綴才是最匹配的。假設有如下一個路由表：
它會先找到第二條路由，然後選擇10.1.0.1作為下一跳地址。但是，如果由第二步定位到的子網(fib_node)有多個路由，如下：
到達同一個子網有兩個可選的路由，僅憑目的子網無法確定，這時，它就需要更多的信息來確定路由的選擇了，這就是用於查找路由的鍵值（struct flowi）還包括其它信息（如TOS）的原因。這樣，它才能定位到對應一個路由的一個fib_alias實例。而它指向的fib_info就是路由所需的信息了。
最後一步，如果內核被編譯成支持多路徑(multipath)路由，則fib_info中有多個fin_nh，這樣，它還要從這個fib_nh數組中選出最合適的一個fib_nh，作為下一跳路由。
三、路由的插入與刪除
路由表的插入與刪除可以看看是路由查找的一個應用，插入與刪除的過程本身也包含一個查找的過程，這兩個操作都需要檢查被插入或被刪除的路由表項是否存在，插入一個已經存在的路由表項要做特殊的處理，而刪除一個不存在的路由表項當然會出錯。
下面看一個路由表插入的例子：
這個命令在內核中建立一條新的路由。它首先查找路由表RT3中的子網掩碼長為24的fn_zone，如果找不到，則創建一個fn_zone。接著，繼續查找子網為10.0.1的fib_node，同樣，如果不存在，創建一個fib_node。然後它會在新建一個fib_info結構，這個結構包含2個fib_nh結構的數組（因為有兩個nexthop），並根據用戶空間傳遞過來的信息初始化這個結構，最後內核再創建一個fib_alias結構（如果先前已經存在，則出錯），並用fib_nh來創始化相應的域，最後將自己鏈入fib_node的鏈中，這樣就完成了路由的插入操作。
路由的刪除操作是插入操作的逆過程，它包含一系列的查找與內存的釋放操作，過程比較簡單，這裡就不再贅述了。
四、策略路由的一個簡單應用
Linux系統在策略路由開啟的時候將使用多個路由表，它不同於其它某些系統，在所有情況下都只使用單個路由表。雖然使用單個路由表也可以實現策略路由，但是如本文之前所提到的，使用多個路由表可以得到更好的性能，特別在一個大型的路由系統中。下面只通過簡單的情況說明Linux下策略路由的應用。
如圖2，有如下一個應用需求，其中網關服務器上有三個網絡接口。接口1的IP為172.16.100.1，子網掩碼為255.255.255.0，網關gw1為a.b.c.d，172.16.100.0/24這個網段的主機可以通過這個網關上網；接口2的IP是172.16.10.1，子網掩碼同接口一，網關gw2為e.f.g.h，172.16.10.0/24這個網段的主機可以通過這個網關上網；接口0的IP為192.168.1.1，這個網段的主機由於網絡帶寬的需求需要通過e.f.g.h這個更快的網關路由出去。
圖 2
步驟一：設置各個網絡接口的IP，和默認網關：
其它接口IP的設置和第一個接口一樣，這時，如果沒有其它設置，則所有的數據通過這個默認網關路由出去。
步驟二：使子網172.16.10.0/24可以通過gw2路由出去
步驟三：添加一個路由表
步驟四：使用策略路由使192.168.1.0/24網段的主機可以通過e.f.g.h這個網關上網
步驟五：刷新路由cache，使新的路由表生效
這樣就可以實現了以上要求的策略路由了，並且可以通過traceroute工具來檢測上面的設置是否能正常工作。
參考資料：
[1] Understanding Linux Network Internals ,Christian Benvenuti
[3]http://heuristic.kaist.ac.kr/paper/full-paper/24.%20IP%20Lookup%20Table%20Design%20Using%20LC-Trie%20with%20Memory%20Constraint.pdf
[4] iproute2 man page
[5] iptables howto
原貼:
廣東省LINUX公共服務技術支持中心
