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

在前幾天寫的一篇文字中，我描述了一次失敗的經(jīng)歷，對于很在乎過程的我，描述下來就是成功。然而，我不得不回退到DxR，研究一下它的本質(zhì)而不是其算法思 想。之所以失敗，是因?yàn)槲业哪娣葱睦碓谧鞴?，我真的沒有研究DxR的本質(zhì)就開始動手，無疑于打一場毫無準(zhǔn)備且對對手完全不了解的惡仗，如果不適可而止，其 結(jié)果必然和當(dāng)初死磕Bloom一樣悲慘！

DxR的本質(zhì)

DxR并沒有發(fā)明什么新的算法，它之所以高效是因?yàn)樗蛛x了路由項(xiàng)中的路由前綴和下一跳這兩個基本元素。在這個的基礎(chǔ)上，它就可以采用三張表來實(shí)現(xiàn)自己的既高效又占用空間小的目的。我來總結(jié)一下：

DxR算法的前提：分離了路由前綴和下一跳。

這 個前提及其重要！分離前綴和下一跳可以消除數(shù)據(jù)冗余，構(gòu)建查找表的目標(biāo)就從構(gòu)建單純的查找匹配表轉(zhuǎn)換成了構(gòu)建IPv4地址的某一段區(qū)間和下一跳表的映射關(guān) 系，這就直接導(dǎo)致了區(qū)間查找。我們來看一下很類似的Trie樹查找算法，這個算法中路由前綴和下一跳是作為一個“路由項(xiàng)”綁定在一起的，因此查找的過程就 是一個精確匹配+回溯的過程。而DxR算法則消除了回溯的過程。

DxR算法的設(shè)施：直接索引表，區(qū)間表，下一跳表。

這個我后面還會說，但記住，這不是核心，這只是一種實(shí)現(xiàn)方式。

DxR算法表設(shè)計：直接索引表的意義

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

用路由前綴將IPv4地址空間分割成區(qū)間

如 果到此為止你還不知道DxR算法是什么，那也無所謂，其實(shí)它的思想很簡單。路由表的最終結(jié)果就是將某個連續(xù)地址段對應(yīng)到某個下一跳(不允許不連續(xù)掩碼 了...)，因此路由表實(shí)際上是將整個IPv4地址空間分割成了若干個區(qū)間，每個區(qū)間只和一個下一跳關(guān)聯(lián)。我把那篇關(guān)于記錄失敗經(jīng)歷的文章中一個正確的圖 貼如下：

拿 著目標(biāo)IP地址當(dāng)索引，向右走，碰到的第一個路由項(xiàng)就是結(jié)果。最長掩碼的邏輯完全體現(xiàn)在插入/刪除過程中，即從左到右前綴依次變短，長前綴的路由項(xiàng)會蓋在 短前綴的路由項(xiàng)的前面，這就是核心思想。雖然我現(xiàn)在已經(jīng)否定了拿IPv4地址直接去做索引，但是核心思想并沒有變，即“拿XX映射到具體的下一跳”，在那 篇失敗記錄中，XX是IPv4地址索引，而在正確的做法中，XX是區(qū)間。其實(shí)在HiPac防火墻中，也正是使用了這個思想，即區(qū)間查找。在HiPac算法 中，區(qū)間就是match域，而下一跳對應(yīng)Rule。
       那么，DxR算法就是針對上述圖示的一步步優(yōu)化。為了更好的說明DxR，我再次給出上圖的變換形式：

區(qū)間查找

如 果按照上面的圖示，整個IPv4地址空間被分割成了N個區(qū)間，路由查找的最終目標(biāo)是將某個IPv4地址對應(yīng)到某個區(qū)間中！到此為止，其實(shí)工作已經(jīng)完成了。 但是有個前提，那就是你要找出或者自己實(shí)現(xiàn)一個高性能的“區(qū)間匹配算法”！，即建立一個區(qū)間表，內(nèi)部保存N個區(qū)間項(xiàng)，每個區(qū)間項(xiàng)對應(yīng)一個下一跳索引，比如 區(qū)間m對應(yīng)下一跳C，我們的目標(biāo)是給定一個IPv4地址，判斷它屬于哪個區(qū)間。這樣的算法比比皆是，自己實(shí)現(xiàn)一個似乎也不難，比如二分法，哈希算法等，所 以本文不關(guān)注這些。然而DxR似乎并不滿足這個發(fā)現(xiàn)，當(dāng)然我也不滿足。DxR似乎希望找到一種更加優(yōu)化的方式實(shí)現(xiàn)這個區(qū)間匹配。
       在給出DxR的框架之前，到此為止，我們發(fā)現(xiàn)，DxR實(shí)質(zhì)上就是使用了區(qū)間匹配來將一個目標(biāo)IPv4地址對應(yīng)到一個區(qū)間，然后取出該區(qū)間對應(yīng)的下一跳！

劃分子區(qū)間

如 果針對每一個到來數(shù)據(jù)包的目標(biāo)IPv4地址都要在N個區(qū)間中做匹配，似乎不太優(yōu)雅。如果能將這N個區(qū)間劃分為若干個子區(qū)間，那么每次匹配時匹配的區(qū)間數(shù)量 將會大大減少，比如N為100，如果能將整個IPv4地址空間劃分為20個相等的子區(qū)間，那么每次匹配的區(qū)間數(shù)量將會是5個，而不是100個！！但是這里 又有一個前提，那就是劃分子區(qū)間的開銷一定要能被由于減少區(qū)間數(shù)量而帶來的收益抵消掉，并且收益要更大！
       這個時候，如果你深入理解二級頁表就好辦了，一個頁目錄項(xiàng)包含1024個頁表項(xiàng)，一個頁表項(xiàng)指向一個4096字節(jié)大小的頁面。其中頁目錄就把整個32位虛 擬地址空間分割成了1024個相同大小的區(qū)間段，每一個區(qū)間段的大小為4096*1024，32位虛擬地址對應(yīng)32位IPv4地址，事情不就是這樣嗎？不 過，二級頁表或多級頁表解決的是稀疏地址的問題，如果是一級的頁表，那么中間會有很多的“洞”，這是因?yàn)檫M(jìn)程如何安排虛擬地址在內(nèi)核和MMU看來是管不了 的。而對于目前我們遇到的問題，采用類似的分級方式是為了劃分子區(qū)間從而提高每次區(qū)間匹配的效率，注意，這并不是以索引為目的的，我錯誤的將索引作為了目 的而不是手段，于是跌到了萬劫不復(fù)的深淵！
       但是，對于IPv4地址，并不采用10bit(這是考慮到虛擬地址尋址的特點(diǎn)以及頁面的大小而設(shè)定的)這樣的劃分法，而是采用k bit劃分法，注意，路由表并不存在頁面的概念！如果k等于16，那么就把IPv4地址的高16位就成了一個索引，由于低16位的存在且自由取值，那么每 一個索引表項(xiàng)包括16位涵蓋的IPv4地址數(shù)量，即65535個IPv4地址。目前的區(qū)間查找表變成了下面的樣子：

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

子區(qū)間布局

如何將子區(qū)間布局成緊湊的結(jié)構(gòu)事關(guān)重大，因?yàn)榫o湊的數(shù)據(jù)結(jié)構(gòu)意味著可以載入CPU Cache！
       以上面最后一幅圖為例子，我們當(dāng)然希望所有的區(qū)間依然連續(xù)存放，這樣似乎是緊湊的唯一方式。我們把這個緊湊的合并后的子區(qū)間表叫做區(qū)間表，如下圖所示：

這個時候，IPv4地址的高16位索引表怎么可以區(qū)分出自己索引的那囊括65535個地址的區(qū)間到底要分割為哪些子區(qū)間呢？答案當(dāng)然是指示一個起始位置和區(qū)間數(shù)量了。如果我們把所有的圖示展示成一種最終的方式，那么請看下圖：

以 上的圖僅僅包含三個表，一個索引表，一個區(qū)間表，另外還有一個下一跳表。關(guān)于下一跳表圖中沒有畫出，這是因?yàn)樗膬?nèi)容不固定，可以僅僅是一個IP地址，也 可以有設(shè)備信息以及狀態(tài)信息等，也可以是一個鏈表，用于負(fù)載均衡，當(dāng)然，也可以指向別的東西。其中最關(guān)鍵的就是前兩個表，即索引表和區(qū)間表。這兩張表都可 以放在很緊湊的空間中，占用很小的內(nèi)存，這兩張表將以最大的能力毛遂自薦以被載入CPU Cache。

DxR到底是個什么樣子的

有點(diǎn)不好意思。因?yàn)樯厦嬲f著說著就把該說的全部說了。
       其實(shí)，DxR就是上面的那幅圖所表達(dá)的！只是在DxR中：

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

2.圖中索引表的第三部分，即編碼優(yōu)化數(shù)據(jù)，這部分可以優(yōu)化定義，使得這些表更加緊湊。

3.如果索引表中定位的區(qū)間表的區(qū)間數(shù)量為1，那么索引表可以直接指向下一跳索引。

總 的來講，k值越大，索引表占據(jù)的空間越大，如果k值取32，那就不好意思了，索引表項(xiàng)為4G個，區(qū)間表不復(fù)存在，因?yàn)樗械腎P地址到下一跳的映射都明細(xì) 化了，這就是我自己那次模擬MMU的設(shè)計最終的結(jié)果，總之，索引表越大，就有越多的IP地址到下一跳的映射明細(xì)化，區(qū)間表的大小在統(tǒng)計意義上就會越小，這 也是空間換時間的體現(xiàn)...固定索引表大小的時候，區(qū)間表的大小是不固定的，取決于你的路由表的路由項(xiàng)布局，因此要想好好使用DxR，沒有一點(diǎn)路由規(guī)劃能 力是不行的，比如你要盡量使用諸如匯總之類的技巧，為了使得路由可以匯總，你可能會還需要重新布線，讓可以匯總的路由可以共用同一接口相連的下一跳，這又 涉及到了一些路由分發(fā)的能力，特別是你在混用動態(tài)路由和靜態(tài)路由的時候?？傊?，IP路由是比較復(fù)雜的，涉及到了綜合的能力，算法，IP地址的理解，地址規(guī) 劃，路由分發(fā)，動態(tài)路由，配置命令，甚至綜合布線...
       我并沒有說這個表如何增刪改，這個我覺得是可以自己分析的，它主要受到動態(tài)路由的影響，畢竟，如果線路狀態(tài)不是經(jīng)常變化，路由表一般也是穩(wěn)定的。