IP在路由表選路的過程？

01-14

寫個程序，輸入一個IP，在/proc/net/route里查詢得出下一跳地址。按我的理解，IP選路就是三個步驟，1、先檢查路由表裡是否有目的地址相等的 2、若沒有則將輸入的IP與路由表裡的掩碼相與，看與目的地址是否有相等的 3、若沒有則輸出最後一條默認的。
但似乎我理解的不對，朋友說第二步就錯了，而且還要考慮metric。請問有沒有比較完整的IP選路流程可以參考的？

貌似對題目的表述理解有些不是很清楚，後面所進行的動作更似轉發的動作。故這裡選路沒定義好，是來一個數據包，具體如何選則哪條路進行轉發？還是在路由演算法的計算中，如何獲得一張最優的路由表？

按照我的理解，路由選路實際上可以定義為通過不同的路由演算法，最終獲得一張最優路由表的過程，即最終獲得的就是RIB。而來了一個數據包，如何轉發，是通過RIB或者直接通過FIB進行查錶轉發的過程。

首先是控制過程，即生成RIB的過程

在RIB過程中，我們可以抽象成兩個部分。其一是收集完整的拓撲結構，比如通過hello包這樣的方法，如果看一些SDN的抽象設計中，都會把這個部分定義成distribution system。在這個部分就是用來發現，維護全網拓撲的，比如OSPF中的鄰居表和拓撲表。其二就是所指定的路由演算法，通常情況下，主要就是包含最短路徑的計算演算法，以及一些相對的選路規則。在SDN中，這些相對的路由演算法就是相對的APP。路由計算的演算法比如SPF，比如bellman-ford。而選路的規則則相對比較多，比如BGP，其選路規則，換言之就是BGP內的路由表決定基本都是來自於規則，而不是最短路徑計算的方法。通過相關的路由演算法，最後所計算出的最優路由即放在該路由協議的路由表中，而metric則是用來在該路由演算法中計算最優路由的。最後不同的路由演算法中對應的路由表還需要進行相互比較，主要就是比較其對應的AD值，從而得到最終的一張路由表，這張總的路由表則是RIB表。以上的過程都是在控制階段完成的。然後具體的數據轉發環節，初始是通過RIB來進行轉發，即一個軟體的過程，而為了提高速率，大部分都是通過硬體進行加速轉發，即通過RIB生成FIB，從而利用FIB進行高速轉發（從cisco的cef轉發的角度理解）。

轉發過程（轉發過程的前提是有了RIB）：

轉發過程更類似在題目中所述。「1、先檢查路由表裡是否有目的地址相等的 2、若沒有則將輸入的IP與路由表裡的掩碼相與，看與目的地址是否有相等的 3、若沒有則輸出最後一條默認的。」這樣的過程。首先1,2可以連在一起來看，實際上是最長掩碼匹配規則，選擇最精確的一個作為匹配。

實際上在正式轉發過程之前，來了一個數據包，首先順序是如介面ACL（看看要不要直接丟包），然後PBR（策略路由，有沒有實現指定的轉發策略，或者QOS策略），然後才落到查錶轉發的過程。

這張圖則抽象一些，不過可以更好的理解這個即這裡策略，查錶轉發，實際上都是單獨是數據包頭部進行的一個處理。然後我們關注的是轉發的過程，如果在一般軟體操作中，我們可以認為題目中所提到的「其匹配是加上子網掩碼做按位與的操作」，不過在實際高速路由環節，這樣的操作很慢，所以一般看硬體都可以看到TCAM這個東西，在TCAM中所增加的第三態，"don"t care"實際上都是對應與這樣的操作，比如下圖

簡單來看，實際上TCAM的第三態don"t care就是在原有的CAM上，增加了一個與mask相與的過程。通過這個方法，可以進行高速的路由匹配，同時該匹配是並行的，可以理解成，在一個匹配周期內，一次性和整張路由表進行路由匹配，並選擇最長匹配結果。匹配完了之後，則對應ARP表，修改下一跳MAC地址，然後就把數據包丟著轉發了，如下圖

其中CEF表實際上就是FIB表（在cisco中，FIB中包含了CEF表，不過按照通常FIB的說法，在概念上其兩者是等價的），然後後面的鄰居表，是採用DDR DRAM所做，其放的就是ARP的結果。以上內容，僅僅做為一個框架性的表述，很多地方僅僅點了下，故不是很嚴謹，如有錯誤，還請見諒。