在Linux3.5版本(包括)之前，存在一個路由cache，這個路由cache的初衷是美好的，但是現實往往是令人遺憾的。以下是陳列得出的兩個問題：
1.面臨針對hash算法的ddos問題(描述該問題的文章已經汗牛充棟，不再贅述)；
2.緩存出口設備是p2p設備的路由項會降低性能。
這些問題本質上是由於路由cache的查找方式和路由表的查找方式互不相容引起的。路由cache必須是精確的元組匹配，因此它必須設計成一維的hash表，而路由表查找算法是最前前綴匹配，因此它可以是多維的。路由查找最終會找到路由項，在不考慮策略路由的前提下，我們來看一下把出口設備為p2p設備的路由項塞進路由cache是多麼的沒有意義。
p2p設備的鄰居集合裡只有一個下一跳，那就是它的對端，因此對於p2p設備，甚至都不需要進行鄰居綁定的過程！然而如果將這類路由塞進路由cache的話，將會占據巨量的內存，試想如果有10w個IP地址需要通信，源IP集合中同樣有10w個IP地址，將有可能會建立100w條路由cache項，極端一點，如果此時系統中只有不多的幾條路由表項的話，查找路由表的開銷可能會反而低於查找路由cache的開銷，特別地，如果路由結果是p2p設備，事實上只要想辦法cache這唯一的一個條目即可。這就是一和多的區別，這次，我們發現不光零到一有意義，一到多也同樣不可小觑。
如果系統中有一塊以太網卡eth0，由於同一網段會有多個鄰居，不同的目標IP地址，其下一跳可能會有所不同，我們不得不cache每一個與eth0相關的路由項，然後針對每一個數據包進行精確匹配，然而如果系統中有一塊p2p網卡，它的鄰居只有一個，對於點對點設備而言，其對端邏輯上只有一個設備，它是唯一的且確定的，它是該點對點設備的鄰居集合中的唯一一個鄰居，因此事實上無需進行鄰居綁定過程，只要從點對點設備將數據包發出，該數據包就一定會到達唯一的對端，在這種情況下，如果我們還cache每一個與該p2p網卡相關的路由項，意義就不大了，然而，對於Linux的路由cache機制而言，這是無法做的的，因為在查找路由cache以及查找路由表之前，我們無從知道這個數據包就是最終要從一個p2p網卡發送出去的。
一個解決方案是，如果查找路由表的結果表明其出口設備是p2p設備，則設置一個NOCACHE標志，表示不cache它，待到數據包發送完畢即釋放，我想這個實現是簡單而明了的，本來去年9月份想實現掉它，也是為了我們的一個網關產品可以提高性能，但是後面我離職了，此事也就不了了之，直到最近，我再次面臨了此問題。然而我有了更好的建議，那就是升級內核到3.6+，不過這是後話，事實上，如果你必須維護基於低版本內核的老產品的話，修改代碼就是避不開的，幸運的是，不管是老公司，還是新公司，我與2.6.32版本的代碼打交道已經6年了。
擴大點說，路由查找這東西確實很尴尬，可以肯定，一台設備上可能會有數十萬條的路由，然而與其相連的鄰居集合內的節點數卻可以用一個字節來表示，而且大多數節點的鄰居可能只有不超過10個！我們消耗了大量的精力，什麼cache查詢，什麼最長前綴匹配，最終就是為了在數十萬數量級的大海中撈出幾根針，所以說，這一直都是一個比較有挑戰性的領域，與TCP加速相比，這個領域更加閉環，它不受其它影響，只有算法本身影響它！事實上，不光p2p設備，就連ethX設備，結局也是悲哀的，配置幾十條路由，最終的下一跳可能只有五六個，p2p設備只是更加極端一些罷了，對於p2p設備，我們一般這麼寫路由即可：
route add -host/net a.b.c.d/e dev tunlX
然而對於ethX設備而言，一般來說我們必須寫路由：
route add -host/net a.b.c.d/e gw A.B.C.D
也就是說，p2p設備直接告知了數據包從設備發出去即可，然而對於ethX設備(或者所有的廣播網絡設備以及NBMA設備)，必須進行地址解析或者下一跳解析才會知道從哪裡發出去。不光如此，路由cache還會對鄰居子系統造成影響，簡單的說，就是路由項引用鄰居，路由項釋放之前，鄰居不能被釋放，即便p2p設備不需要鄰居解析，在代碼層面也必須特殊處理，不幸的是，Linux內核中並沒有看到這種特殊處理，p2p設備的路由項依然會塞進路由cache。
以上就是路由查找的困境。困境在於多對一或者多對少的映射過程，這種情況下，營造一個精確匹配的cache可能使結局更加悲哀，因此，用一種統一的方式進行調優可能更加符合人之常情。Linux3.6以後，去除了路由cache的支持，所有的數據包要想發送出去，必須查找路由表！如今的過程可能會變成以下的邏輯：
dst=lookup_fib_table(skb);
dst_nexthop=alloc_entry(dst);
neigh=bind_neigh(dst_nexthop);
neigh.output(skb);
release_entry(dst_nexthop);
這是一個完美的過程，然而在協議棧的實現層面，出現了新的問題，即alloc/release會帶來巨大的內存抖動，我們知道，內存分配與釋放是一個必須要在CPU外部完成的事務，它的開銷是巨大的，雖然在Linux中有slab cache，但是我們同樣也知道，cache是分層的。事實上，Linux在3.6以後，實現了新的路由cache，不再緩存一個路由項，因為那需要skb的元組精確匹配，而是緩存下一跳，找到這個cache必須經過lookup_fib_table這個例程。
這是個創舉，因為緩存的東西是唯一的，除非發生一些例外！這就破解了解決多對一以及多對少的問題，在找到緩存之前，你必須先查找路由表，而查找完畢之後，理論上你已經知道了下一跳，除非一些例外(再次重申！)這個新的下一跳緩存只是為了避免內存的分配/釋放！偽代碼如下：
dst=lookup_fib_table(skb);
dst_nexthop=lookup_nh_cache(dst);
if dst_nexthop == NULL;
then
dst_nexthop=alloc_entry(dst);
if dst_nexthop.cache == true;
then
insert_into_nh_cache(dst_nexthop);
endif
endif
neigh=bind_neigh(dst_nexthop);
neigh.output(skb);
if dst_nexthop.cache == false
then
release_entry(dst_nexthop);
endif
就這樣，路由cache不再緩存整個路由項，而是緩存路由表查找結果的下一跳。
鑒於一般而言，一個路由項只有一個下一跳，因此這個緩存是極其有意義的。這意味著，在大多數時候，當路由查找的結果是一個確定的dst時，其下一跳緩存會命中，此時便不再需要重新分配新的dst_nexthop結構體，而是直接使用緩存中的即可，如果很不幸，沒有命中，那麼重新分配一個dst_nexthop，將其盡可能地插入到下一跳緩存，如果再次很不幸，沒有成功插入，那麼設置NOCACHE標志，這意味著該dst_nexthop使用完畢後將會被直接釋放。
上述段落說明的是下一跳緩存命中的情況，那麼在什麼情況下會不命中呢，這很簡單，無非就是在上述的lookup_nh_cache例程中返回NULL的時候，有不多的幾種情況會導致其發生，比如某種原因將既有的路由項刪除或者更新等。這個我隨後會通過一個p2p虛擬網卡mtu問題給予說明，在此之前，我還要闡述另外一種常見的情形，那就是重定向路由。
所謂的重定向路由，它會更新本節點路由表的一個路由項條目，要注意的是，這個更新並不是永久的，而是臨時的，所以Linux的做法並不是直接修改路由表，而是修改下一跳緩存！這個過程是異步的，偽代碼如下：
# IP_OUT例程執行IP發送邏輯，它首先會查找標准路由表，然後在下一跳緩存中查找下一跳dst_nexthop，以決定是否重新分配一個新的dst_nexthop，除非你一開始指定NOCACHE標志，否則幾乎都會在查找下一跳緩存失敗進而創建新的dst_nexthop之後將其插入到下一跳緩存，以留給後續的數據包發送時使用，這樣就避免了每次重新分配/釋放新的內存空間。
func IP_OUT：
dst=lookup_fib_table(skb);
dst_nexthop = loopup_redirect_nh(skb.daddr, dst);
if dst_nexthop == NULL;
then
dst_nexthop=lookup_nh_cache(dst);
endif
if dst_nexthop == NULL;
then
dst_nexthop=alloc_entry(dst);
if dst_nexthop.cache == true;
then
insert_into_nh_cache(dst_nexthop);
endif
endif
neigh=bind_neigh(dst_nexthop);
neigh.output(skb);
if dst_nexthop.cache == false
then
release_entry(dst_nexthop);
endif
endfunc
# IP_ROUTE_REDIRECT例程將創建或者更新一個dst_nexthop，並將其插入到一個鏈表中，該鏈表由數據包的目標地址作為查找鍵。
func IP_ROUTE_REDIRECT:
dst=lookup_fib_table(icmp.redirect.daddr);
dst_nexthop = new_dst_nexthop(dst, icmp.redirect.newnexthop);
insert_into_redirect_nh(dst_nexthop);
endfunc
以上就是3.6以後內核的下一跳緩存邏輯，值得注意，它並沒有減少路由查找的開銷，而是減少了內存分配/釋放的開銷！路由查找是繞不過去的，但是路由查找結果是路由項，它和下一跳結構體以及鄰居結構體之間還有層次關系，其關系如下：
路由項-下一跳結構體-鄰居項
一個數據包在發送過程中，必須在路由查找結束後綁定一個下一跳結構體，然後綁定一個鄰居，路由表只是一個靜態表，數據通道沒有權限修改它，它只是用來查找，協議棧必須用查找到的路由項信息來構造一個下一跳結構體，這個時候就體現了緩存下一跳的重要性，因為它減少了構造的開銷！
最後，我們可以看一下效果，如果你只是看代碼，那麼當你看到input或者output路徑中的rt_dst_alloc調用時，你可能會很灰心喪氣，但是如果你使用下面的命令看一下實際結果：
watch -d -n 1 “cat /proc/net/stat/rt_cache”
的時候，你就會發現，in_slow_tot和out_slow_tot兩個字段的計數器增加十分緩慢，甚至停滯！這意味著絕大多數的數據包在接收和發送過程中都命中了下一跳cache！如果你發現了異常，也就是說不是這種情況，它們中的其一或者兩者增長的很快，那麼可能是兩方面的原因：
1.你的內核可能沒有升級到足夠高的版本
這意味著你的內核有bug，在3.10的最初版本中，RT_CACHE_STAT_INC(in_slow_tot);的調用是發生在下列代碼之前的：
if (res.fi) {
if (!itag) {
rth = rcu_dereference(FIB_RES_NH(res).nh_rth_input);
if (rt_cache_valid(rth)) {
skb_dst_set_noref(skb, &rth->dst);
err = 0;
goto out;
}
do_cache = true;
}
}
rth = rt_dst_alloc(net->loopback_dev,
IN_DEV_CONF_GET(in_dev, NOPOLICY), false, do_cache);
...
也就是說它遺留了路由cache存在的年代的代碼，錯誤的將下一跳緩存當成了路由cache！只需要將RT_CACHE_STAT_INC(in_slow_tot)移植到rt_dst_alloc之後即可。
2.你可能使用了p2p設備，但是並沒有正確的設置MTU
我們知道ipip隧道設備在Linux上是一個虛擬網卡設備，數據包要真正發送出去要經過重新封裝一個IP頭部的過程，如果最終是經由ethX發送數據，其MTU默認是1500，如果ipip隧道設備的MTU也是1500或者小於1500減去必要頭部開銷的話，就到導致重新更新MTU的操作，而一個下一跳緩存中包含MTU信息，如果MTU需要重新更新，就意味著下一跳緩存需要更新。
在一般的物理設備中，這不是問題，因為往往在IP層發送數據前，MTU就是已經確知的，但是對於ipip隧道設備而言，在數據發送的時候，協議棧在實際往隧道發送數據前並不知道最終數據包需要再次封裝，因此也就對MTU過大導致數據無法發送這件事不知情，特別是遇到gso，tso這種情況，事情會更加復雜。此時我們有兩個解決方案：
1).適當調低ipip隧道的MTU值，保證即使經過再次封裝，也不過長度過載。這樣就不會導致重新更新MTU進而釋放更新下一跳cache。
2).從代碼入手！
根據代碼的rt_cache_valid來看，不要讓下一跳緩存的標志變成DST_OBSOLETE_KILL即可，而這也是和MTU相關的，而在__ip_rt_update_pmtu中，只要保證下一跳緩存的初始mtu不為0即可，這可以加入一個判斷，在rt_dst_alloc之後，初始化rth字段的時候：
if (dev_out->flags&(IFF_LOOPBACK|IFF_POINTOPOINT))
rth->mtu = dev_out->mtu;
else
rth->mtu = 0;
經過測試，效果良好！
BTW,和很多的安全協議一樣，路由表項以及下一跳緩存也使用了版本號來管理其有效性，只有表項的ID和全局ID一致的時候，才代表該表項有效，這簡化了刷新操作，當刷新發生的時候，只需要遞增全局版本號ID即可。
現在，可以總結一下了。在Linux3.6以後，路由cache被去除了，取而代之的是下一跳緩存，這裡面有很多的蹊跷，比如有重定向路由的處理等...這主要是有效減少了內存管理的開銷而不是查找本身的開銷。在此要說一下內存的開銷和查找的開銷。二者並不是一個層次的，內存的開銷主要跟內存管理數據結構以及體系結構有關，這是一個復雜的范疇，而查找的開銷相對簡單，只是跟算法的時間空間復雜度以及體系結構相關，然而為什麼用查找的開銷換內存的開銷，這永遠是一個無解的哲學問題！
