從模擬MMU設計一個路由表的失敗到DxR的回歸

在頭幾天寫的1篇文字中，我描寫了1次失敗的經歷，對很在意進程的我，描寫下來就是成功。但是，我不能不回退到DxR，研究1下它的本質而不是其算法思想。之所以失敗，是由于我的逆反心理在作怪，我真的沒有研究DxR的本質就開始動手，無疑于打1場毫無準備且對對手完全不了解的惡仗，如果不適可而止，其結果必定和當初死磕Bloom1樣悲慘！

DxR的本質

DxR并沒有發明甚么新的算法，它之所以高效是由于它分離了路由項中的路由前綴和下1跳這兩個基本元素。在這個的基礎上，它就能夠采取3張表來實現自己的既高效又占用空間小的目的。我來總結1下：

DxR算法的條件：分離了路由前綴和下1跳。

這個條件及其重要！分離前綴和下1跳可以消除數據冗余，構建查找表的目標就從構建單純的查找匹配表轉換成了構建IPv4地址的某1段區間和下1跳表的映照關系，這就直接致使了區間查找。我們來看1下很類似的Trie樹查找算法，這個算法中路由前綴和下1跳是作為1個“路由項”綁定在1起的，因此查找的進程就是1個精確匹配+回溯的進程。而DxR算法則消除回溯的進程。

DxR算法的設施：直接索引表，區間表，下1跳表。

這個我后面還會說，但記住，這不是核心，這只是1種實現方式。

DxR算法表設計：直接索引表的意義

直接索引表合并了巨大的IPv4地址區間，以便區間表在合并后的少的多的區間中更快速地進行搜索，兩個表的目的都是指向下1跳表的索引。這就建立了區間到下1跳的映照。

用路由前綴將IPv4地址空間分割成區間

如果到此為止你還不知道DxR算法是甚么，那也無所謂，其實它的思想很簡單。路由表的終究結果就是將某個連續地址段對應到某個下1跳(不允許不連續掩碼了...)，因此路由表實際上是將全部IPv4地址空間分割成了若干個區間，每一個區間只和1個下1跳關聯。我把那篇關于記錄失敗經歷的文章中1個正確的圖貼以下：

拿著目標IP地址當索引，向右走，碰到的第1個路由項就是結果。最長掩碼的邏輯完全部現在插入/刪除進程中，即從左到右前綴順次變短，長前綴的路由項會蓋在短前綴的路由項的前面，這就是核心思想。雖然我現在已否定了拿IPv4地址直接去做索引，但是核心思想并沒有變，即“拿XX映照到具體的下1跳”，在那篇失敗記錄中，XX是IPv4地址索引，而在正確的做法中，XX是區間。其實在HiPac防火墻中，也正是使用了這個思想，即區間查找。在HiPac算法中，區間就是match域，而下1跳對應Rule。
       那末，DxR算法就是針對上述圖示的1步步優化。為了更好的說明DxR，我再次給出上圖的變換情勢：

區間查找

如果依照上面的圖示，全部IPv4地址空間被分割成了N個區間，路由查找的終究目標是將某個IPv4地址對應到某個區間中！到此為止，其實工作已完成了。但是有個條件，那就是你要找出或自己實現1個高性能的“區間匹配算法”！，即建立1個區間表，內部保存N個區間項，每一個區間項對應1個下1跳索引，比如區間m對應下1跳C，我們的目標是給定1個IPv4地址，判斷它屬于哪一個區間。這樣的算法比比皆是，自己實現1個仿佛也不難，比如2分法，哈希算法等，所以本文不關注這些。但是DxR仿佛其實不滿足這個發現，固然我也不滿足。DxR仿佛希望找到1種更加優化的方式實現這個區間匹配。
       在給出DxR的框架之前，到此為止，我們發現，DxR實質上就是使用了區間匹配來將1個目標IPv4地址對應到1個區間，然后取出該區間對應的下1跳！

劃份子區間

如果針對每個到來數據包的目標IPv4地址都要在N個區間中做匹配，仿佛不太優雅。如果能將這N個區間劃分為若干個子區間，那末每次匹配時匹配的區間數量將會大大減少，比如N為100，如果能將全部IPv4地址空間劃分為20個相等的子區間，那末每次匹配的區間數量將會是5個，而不是100個！！但是這里又有1個條件，那就是劃份子區間的開消1定要能被由于減少區間數量而帶來的收益抵消掉，并且收益要更大！
       這個時候，如果你深入理解2級頁表就好辦了，1個頁目錄項包括1024個頁表項，1個頁表項指向1個4096字節大小的頁面。其中頁目錄就把全部32位虛擬地址空間分割成了1024個相同大小的區間段，每個區間段的大小為4096*1024，32位虛擬地址對應32位IPv4地址，事情不就是這樣嗎？不過，2級頁表或多級頁表解決的是稀疏地址的問題，如果是1級的頁表，那末中間會有很多的“洞”，這是由于進程如何安排虛擬地址在內核和MMU看來是管不了的。而對目前我們遇到的問題，采取類似的分級方式是為了劃份子區間從而提高每次區間匹配的效力，注意，這其實不是以索引為目的的，我毛病的將索引作為了目的而不是手段，因而跌到了萬劫不復的深淵！
       但是，對IPv4地址，其實不采取10bit(這是斟酌到虛擬地址尋址的特點和頁面的大小而設定的)這樣的劃分法，而是采取k bit劃分法，注意，路由表其實不存在頁面的概念！如果k等于16，那末就把IPv4地址的高16位就成了1個索引，由于低16位的存在且自由取值，那末每個索引表項包括16位涵蓋的IPv4地址數量，即65535個IPv4地址。目前的區間查找表變成了下面的模樣：

要知道，IPv4地址高16位地址可以1下子索引出子區間，這是1個瞬間的操作！然后下面的問題就是“如何公道布局這些子區間”。

子區間布局

如何將子區間布局成緊湊的結構事關重大，由于緊湊的數據結構意味著可以載入CPU Cache！
       以上面最后1幅圖為例子，我們固然希望所有的區間仍然連續寄存，這樣仿佛是緊湊的唯1方式。我們把這個緊湊的合并后的子區間表叫做區間表，以下圖所示：

這個時候，IPv4地址的高16位索引表怎樣可以辨別出自己索引的那包括65535個地址的區間到底要分割為哪些子區間呢？答案固然是唆使1個起始位置和區間數量了。如果我們把所有的圖示展現成1種終究的方式，那末請看下圖：

以上的圖僅僅包括3個表，1個索引表，1個區間表，另外還有1個下1跳表。關于下1跳表圖中沒有畫出，這是由于它的內容不固定，可以僅僅是1個IP地址，也能夠有裝備信息和狀態信息等，也能夠是1個鏈表，用于負載均衡，固然，也能夠指向別的東西。其中最關鍵的就是前兩個表，即索引表和區間表。這兩張表都可以放在很緊湊的空間中，占用很小的內存，這兩張表將以最大的能力毛遂自薦以被載入CPU Cache。

DxR究竟是個甚么模樣的

有點不好意思。由于上面說著說著就把該說的全部說了。
       其實，DxR就是上面的那幅圖所表達的！只是在DxR中：

1.DxR中的x指的就是上文中的k，在我的例子中，我取的是16，實際上它可以取別的值。但是1般而言，大于等于16吧。

2.圖中索引表的第3部份，即編碼優化數據，這部份可以優化定義，使得這些表更抓緊湊。

3.如果索引表中定位的區間表的區間數量為1，那末索引表可以直接指向下1跳索引。

總的來說，k值越大，索引表占據的空間越大，如果k值取32，那就不好意思了，索引表項為4G個，區間表不復存在，由于所有的IP地址到下1跳的映照都明細化了，這就是我自己那次摹擬MMU的設計終究的結果，總之，索引表越大，就有越多的IP地址到下1跳的映照明細化，區間表的大小在統計意義上就會越小，這也是空間換時間的體現...固定索引表大小的時候，區間表的大小是不固定的，取決于你的路由表的路由項布局，因此要想好好使用DxR，沒有1點路由計劃能力是不行的，比如你要盡可能使用諸如匯總之類的技能，為了使得路由可以匯總，你可能會還需要重新布線，讓可以匯總的路由可以共用同1接口相連的下1跳，這又觸及到了1些路由分發的能力，特別是你在混用動態路由和靜態路由的時候。總之，IP路由是比較復雜的，觸及到了綜合的能力，算法，IP地址的理解，地址計劃，路由分發，動態路由，配置命令，乃至綜合布線...
       我并沒有說這個表如何增刪改，這個我覺得是可以自己分析的，它主要遭到動態路由的影響，畢竟，如果線路狀態不是常常變化，路由表1般也是穩定的。