命題作文：Dimension Tree區(qū)間查找與IP數(shù)據(jù)包分類

這個(gè)題目有點(diǎn)大，而且我要嚴(yán)格控制字?jǐn)?shù)，不能像《命題作文：在一棵IPv4地址樹中徹底理解IP路由表的各種查找過(guò)程》那樣扯得那么開了。事實(shí)上，這篇作文是上 一篇作文中關(guān)于區(qū)間查找小節(jié)的擴(kuò)展。

1.IP數(shù)據(jù)包分類

根據(jù)IP數(shù)據(jù)包協(xié)議頭的若干字段，也叫匹配域，將數(shù)據(jù)包劃分到某個(gè)類別，這就是IP數(shù)據(jù)包分類的核心。
       事實(shí)上，IP路由查找的過(guò)程就是IP數(shù)據(jù)包分類的一個(gè)特例，一個(gè)極其簡(jiǎn)單的特例，此時(shí)的匹配域就是目標(biāo)IP地址，而類別就是路由項(xiàng)或者說(shuō)更簡(jiǎn)單一點(diǎn)，下一 跳。此時(shí)考慮一下源地址Policy routing，隨即又增加了一個(gè)匹配域，即源IP地址，這時(shí)整個(gè)過(guò)程應(yīng)該怎么做呢？本文關(guān)注一種多維區(qū)間匹配方案，不談其它的比如HASH匹配，也不談 硬件算法。

2.區(qū)間查找

我希望我寫的《HiPAC高性能規(guī)則匹配算法之查找過(guò)程》以及《玩轉(zhuǎn)高性能超猛防火墻nf-HiPAC》可以帶來(lái)些幫助，其實(shí)，IP數(shù)據(jù)包分類的過(guò)程可以看成是多個(gè)匹配域的區(qū)間查找的結(jié)果的合并。
       在HiPAC一般算法中，雖然在執(zhí)行效率上講是非常好的，但是卻可能浪費(fèi)大量的內(nèi)存?？赡苄枰捎肎rid of Tries數(shù)據(jù)結(jié)構(gòu)的優(yōu)化方式對(duì)其存儲(chǔ)空間進(jìn)行優(yōu)化，去除冗余數(shù)據(jù)。
       雖然我要說(shuō)的關(guān)于IP數(shù)據(jù)包分類的核心算法到此應(yīng)該就結(jié)束了，但是數(shù)據(jù)包分類背后的理論，才剛剛開始。后面我會(huì)用一個(gè)實(shí)例來(lái)做盡可能明晰的圖解，而不是用一個(gè)統(tǒng)一的數(shù)學(xué)推導(dǎo)來(lái)說(shuō)明問(wèn)題，目的在于提供一個(gè)感性的畫面。

3.問(wèn)題的提出

往往只知道如何在多維連續(xù)區(qū)間集合里讓一個(gè)IP數(shù)據(jù)包是遠(yuǎn)遠(yuǎn)不夠的，其實(shí)不懂這些也沒(méi)關(guān)系。如果確實(shí)懂這個(gè)，那么就要知其然亦知其所以然。
       現(xiàn)在，我假設(shè)通過(guò)上面提到的兩篇關(guān)于nf-HiPAC的文章，你已經(jīng)知道了多維區(qū)間匹配的過(guò)程，那么我們可以脫離具體場(chǎng)景了，將其抽象成一個(gè)一般問(wèn)題，先 看一下抽象后的示意圖，在這個(gè)圖中，我忽略了區(qū)間的大小，忽略了Rule的排列問(wèn)題(最終我將會(huì)回到這個(gè)問(wèn)題)：

在這個(gè)圖中，我們看到了很多的“?”號(hào)，意思是說(shuō)，我們此時(shí)并不知道和該區(qū)間相關(guān)的Ruleset是什么？這是為什么呢？
       我們來(lái)看第二層，也就是Dimension 2的那一層，該層中有4個(gè)節(jié)點(diǎn)，對(duì)應(yīng)Dimension 1分裂出來(lái)的4個(gè)區(qū)間，如果想讓匹配繼續(xù)下去，即繼續(xù)匹配Dimension 3那一層的節(jié)點(diǎn)，對(duì)應(yīng)的Ruleset中必須要有交集才可以，因此我們得到了下面這個(gè)更加清晰的圖示，雖然，它有點(diǎn)亂。。。。在寫這個(gè)文章時(shí)，我不知怎么 想起了哈爾濱，想哭...：

我們依照這個(gè)圖，發(fā)現(xiàn)了下面重要的三個(gè)關(guān)鍵點(diǎn)：

1).關(guān)鍵操作：Ruleset需要取交集

當(dāng) 前區(qū)間的Ruleset與下一個(gè)維度的各個(gè)區(qū)間的Ruleset并集取交集，該結(jié)果集合不為空時(shí)才會(huì)擴(kuò)展該分支成一個(gè)孩子節(jié)點(diǎn)。我加入了一些與場(chǎng)景相關(guān)的 約束，比如每一個(gè)區(qū)間起碼要有一個(gè)Default Rule，因此所有的取交集的結(jié)果均不會(huì)為空，所以上面的這句話應(yīng)該是，如果結(jié)果集合的元素個(gè)數(shù)為1，且該元素為Default Rule的話，則該當(dāng)前區(qū)間對(duì)應(yīng)的下一個(gè)匹配維度孩子擴(kuò)展為葉子節(jié)點(diǎn)。這意味著，下下一個(gè)維度將不會(huì)再擴(kuò)展該子樹，也就是說(shuō)匹配沒(méi)有必要繼續(xù)下去了，直接 取Default Rule即可。

2).關(guān)鍵權(quán)衡：快速成功與快速失敗

如關(guān)鍵操作所示，只要匹配會(huì)繼續(xù)進(jìn)行下去，即相關(guān)的當(dāng)前 區(qū)間剩余的Ruleset中Rule數(shù)量不為1或者為1但是不是Default Rule，那么我們就不能確定最終結(jié)果，因此，這意味著快速成功是不可能的。但是我們卻可以很快確定什么情況下會(huì)失敗，即當(dāng)前區(qū)間的Ruleset中只剩 下了1個(gè)Default Rule。這就是快速失敗。

3).關(guān)鍵問(wèn)題：這棵樹如何布局

通過(guò)上面的圖示可以看出，由于 Ruleset是取交集，Dimension 1/2/3誰(shuí)在前誰(shuí)在后其實(shí)最終并不影響結(jié)果，但是這個(gè)排序的不同卻可以影響空間的占用，從上圖可以看出，只要Ruleset有交集，就要在下層創(chuàng)建一個(gè) 孩子節(jié)點(diǎn)，其實(shí)就是創(chuàng)建一個(gè)區(qū)間查找樹，而我們?cè)诳焖偈≈兄?，所有的子樹可能由于Ruleset布局的不同而導(dǎo)致其高度并不相同。問(wèn)題是，我們?nèi)绾蝸?lái) 排列維度的查找順序？

4.困難的所在

不要指望在上面的那棵樹上作什么平衡操作，因?yàn)橛绊懫渥訕涓叨纫约皩挾鹊囊蛩厥窍嗷リP(guān)聯(lián)的，它們是Rule的數(shù)量，每一個(gè)維度的區(qū)間數(shù)量，Ruleset的內(nèi)部布局等。這棵樹的任意“旋轉(zhuǎn)”將會(huì)導(dǎo)致其稱為一團(tuán)亂麻，它不是三角架。
       由于根本就沒(méi)有好的辦法去計(jì)算如何最優(yōu)化排列這些維度匹配順序，倒不如按照統(tǒng)計(jì)的意義，尋找一種“讓這棵樹”更加平衡的方式。

5.從M叉樹到2叉樹

到 此為止，我們一直覺(jué)得所謂的多維區(qū)間匹配就是一個(gè)M叉樹，其中M是每層由該層，即該維度所被劃分的區(qū)間數(shù)量。通過(guò)以上的分析，我們發(fā)現(xiàn)在一個(gè)如此胖的且每 個(gè)分支的高度還不確定的樹中尋找一種最佳的構(gòu)建方式是一件困難的事情，因?yàn)樽兞刻嗔?，Ruleset中Rule的數(shù)量是一個(gè)變參，區(qū)間數(shù)量也是一個(gè)變 參，各個(gè)維度的每一個(gè)區(qū)間的Ruleset都要取并集，這涉及到一個(gè)笛卡爾積的問(wèn)題。這里面涉及太多的數(shù)學(xué)計(jì)算，又沒(méi)有一個(gè)簡(jiǎn)單的公式。
       難道多維區(qū)間匹配樹一開始就必須如此構(gòu)造成M叉樹嗎？
       在繼續(xù)之前，我來(lái)用一種更加直觀的方式展示上述的多維匹配問(wèn)題，然后從0開始，直到我們遇到KD樹為止，剩下的內(nèi)容，數(shù)據(jù)結(jié)構(gòu)，算法相關(guān)的書上就都有了。

5.1.多維匹配立方體

幸虧我以三維域匹配為例，要不然我真不知道四維立方體怎么畫出來(lái)。
       我把上面的三維域匹配問(wèn)題以一個(gè)立方體來(lái)描述：

注 意到，每一個(gè)黑色的點(diǎn)沿著坐標(biāo)軸連接成的線段進(jìn)而由這些線段形成的面將這個(gè)立方體分割成了4*3*2個(gè)子立方體，我們的問(wèn)題就是，最終匹配完成后，我們會(huì) 落入一個(gè)子立方體中，而這個(gè)子立方體里面當(dāng)前的Ruleset就是結(jié)果集，我們?nèi)?yōu)先級(jí)最大的，就是最終結(jié)果，值得注意的是，這些子立方體中的 Ruleset是在構(gòu)造這個(gè)立方體的時(shí)候放進(jìn)去的，和那篇講路由查找的命題作文一樣，我并不考慮相對(duì)稀有的數(shù)據(jù)結(jié)構(gòu)構(gòu)造事件的時(shí)間復(fù)雜度。因此，我將 Ruleset示意圖放入子立方體，如下圖所示：

那么現(xiàn)在問(wèn)題來(lái)了。我要怎么切割這個(gè)立方體，然后最后得到那個(gè)期望的子立方體呢？第一刀怎么切？沿著D1軸？D2軸？D3軸？如果確定了D1軸，那么第二刀呢？繼續(xù)D1軸？還是換一個(gè)方向切？...

5.2.切割方式

這不禁讓人想到切西瓜，但是事實(shí)上卻完全不同，這個(gè)和你用一大塊木頭塊取中心的小塊比較類似。你有兩種方式，先把它削成片，再把它削成棍，最后把棍剁成小塊；還有一種方式比較類似機(jī)床×××那般，始終不斷變換方向切割。對(duì)于多維匹配問(wèn)題，我們面臨了同樣的選擇。

5.2.1.逐維度深度優(yōu)先

這種方式類似片-棍-塊的方式，如下圖所示：

5.2.2.逐維度廣度優(yōu)先

這個(gè)比較類似機(jī)器加工的方式，如下圖所示：

那么，是時(shí)候給出數(shù)據(jù)結(jié)構(gòu)了。我在講路由查找的作文中的區(qū)間查找小節(jié)給出了區(qū)間二叉查找樹的結(jié)構(gòu)以及構(gòu)造方式，本文中對(duì)此前提作了基本假設(shè)。

5.3.深度優(yōu)先查找樹

深度優(yōu)先的查找樹結(jié)構(gòu)如下：

可見，這是一種直接的方式，特別適合精確匹配。以下我提到Dimension Tree或者Dimtree的時(shí)候，指的就是這棵樹。

5.4.廣度優(yōu)先查找樹

廣度優(yōu)先的查找樹結(jié)構(gòu)如下：

可 見，這是一種碰運(yùn)氣的方式，在各個(gè)維度上逐步(以盡可能細(xì)的粒度，小心翼翼地)接近最終要落到的子立方體空間。當(dāng)然這種方式其實(shí)就是Dimension Tree的逐層旋轉(zhuǎn)后展開的結(jié)果，最終也可以得到答案，碰到某個(gè)維度的葉子節(jié)點(diǎn)后，將其中的Ruleset壓入一個(gè)棧中，最終在這棵樹游歷結(jié)束后，將棧里 面的Ruleset取出后求交集，然后取最佳的即可。當(dāng)然，也可以用快速失敗來(lái)剪掉枝干，比如到達(dá)了一個(gè)只包含Default Rule的葉子節(jié)點(diǎn)。但是，第一次發(fā)現(xiàn)葉子節(jié)點(diǎn)的時(shí)刻要等多久呢？如果第一個(gè)維度的查找樹有3層，第二維度有2層，第三維度有2層，那么廣度優(yōu)先樹的層則 為：第一維度-第二維度-第三維度-第一維度-第二維度(首次碰到葉子)-第三維度(葉子節(jié)點(diǎn))-第一維度....不管怎么說(shuō)，即便從第二維度開始切割， 也不可能在第二層碰到葉子...這就說(shuō)明，即便是快速失敗的檢測(cè)，也要比深度優(yōu)先延后。

5.5.比較

對(duì)于數(shù)據(jù)包精確匹配分類來(lái) 講，深度優(yōu)先的方式好于廣度優(yōu)先的方式，這不僅僅是在說(shuō)如果沒(méi)有精確區(qū)間匹配，那么再接近的匹配也不算(比如精確匹配192.168.1.18，那么 192.168.1.19顯然是不符合要求的，雖然它很接近)，還包括這種方式可以最大限度的利用系統(tǒng)Cache。
       注意，不要認(rèn)為數(shù)據(jù)包的掩碼匹配就不是精確匹配，本文是嚴(yán)格基于區(qū)間來(lái)匹配的，掩碼將一個(gè)域劃分成了多個(gè)精確的區(qū)間，而最終的目的是定位一個(gè)數(shù)據(jù)包的某個(gè)域精確落到了哪個(gè)區(qū)間中，注意，這是一種精確匹配。
       KD樹，即k-dimension樹就采用了上述逐維度廣度優(yōu)先的匹配方式。然而它的維度排序思想可以被借鑒，從而用于深度優(yōu)先匹配，最終目標(biāo)是構(gòu)建一棵“若不匹配則快速失敗”的樹！

注解：k-dimension樹

看起來(lái)，這像極了一棵B-樹，但它不是！
KD樹的資料網(wǎng)上實(shí)在太多。我要說(shuō)的是它的遞歸構(gòu)建中是如何使用方差的?，F(xiàn)在讓我們回答第一刀從哪里切割的問(wèn)題。
       我將區(qū)間長(zhǎng)度作為基準(zhǔn)，那么每個(gè)維度均可以計(jì)算出一個(gè)區(qū)間長(zhǎng)度的方差數(shù)值，即：



取這個(gè)值最大的維度為第一維度，然后使用樸素的二分構(gòu)建，取該維度區(qū)間全集中最接近中點(diǎn)的那個(gè)點(diǎn)作為根，開始遞歸構(gòu)建二叉樹。每一層都要計(jì)算該子域的方差，從而根據(jù)這個(gè)最大方差原則選出子樹的二分根。通過(guò)上面的廣度優(yōu)先匹配可以看出，那個(gè)圖應(yīng)該就是一棵樸素的KD樹。
       采用最小方差的思想的目的是，讓這棵樹平衡一些，方差比較大說(shuō)明這個(gè)維度上的區(qū)間分布比較均勻，標(biāo)示點(diǎn)并沒(méi)有集中在平均值附近，這樣切割的時(shí)候就不會(huì)一下 子切掉一大塊，從而錯(cuò)過(guò)了可能比較接近最終答案的那些區(qū)域(最終結(jié)果的逼近原則：切割粒度盡可能小，一定要小心翼翼，類似削梨或者削鉛筆那樣的)。注 意，KD樹的目標(biāo)并不是精確匹配，而是模糊最佳匹配，比如經(jīng)典的尋找K個(gè)最接近的點(diǎn)。

6.Dimension Tree的維度排序

由 于深度優(yōu)先匹配并不是遞歸構(gòu)建的，因此不需要每一步都去計(jì)算方差從而確定切割的維度，對(duì)于深度優(yōu)先匹配而言，只要確定了某個(gè)維度，那么將在這個(gè)維度上直接 切割完畢，對(duì)于三維情況而言，就是直接切成一個(gè)片，對(duì)于二維而言就是切成一根棍...對(duì)于接下來(lái)的切割就不需要再考慮這個(gè)維度了，因?yàn)樵谶@個(gè)維度，它已經(jīng) 精確到達(dá)它的區(qū)間了。因此，我們只需要找出一個(gè)維度序列就可以了。
       還是像KD樹一樣基于方差嗎？不一定。此時(shí)我們希望的是，讓Rule在各個(gè)區(qū)間分布最不平均的維度作為第一維，依次類推。這是因?yàn)?，Rule分布不平均在 和下一維的Ruleset并集取交集的時(shí)候，對(duì)應(yīng)區(qū)間在經(jīng)過(guò)取交集計(jì)算后，出現(xiàn)唯一Default Rule從而導(dǎo)致快速失敗的可能性比較大，這就會(huì)減少孩子節(jié)點(diǎn)的數(shù)量，對(duì)于一棵M叉樹而言，越是剪掉靠近根的節(jié)點(diǎn)的孩子，越能抑制下層節(jié)點(diǎn)的瘋長(zhǎng)。我們判 斷是否擴(kuò)展該孩子的公式為：
 當(dāng)前維度區(qū)間Ruleset & (next維度各個(gè)Ruleset的并集)
我們不好控制next 維度的各個(gè)區(qū)間Ruleset的并集，我們甚至不知道next維度是哪個(gè)，但是我們可以找到當(dāng)前維度的Ruleset分布情況。舉一個(gè)最簡(jiǎn)單的例子，有一 個(gè)維度劃分了4個(gè)區(qū)間，第一個(gè)區(qū)間的Ruleset中有10條，后三個(gè)區(qū)間中均是2條，那么僅有2條Rule的區(qū)間和別人取交集時(shí)很可能是空，這就為我們 找到了一個(gè)計(jì)算的依據(jù)，很顯然，我們這次不用KD樹的方差，而是將權(quán)值表示成一個(gè)區(qū)間數(shù)量，區(qū)間Rule的分布情況(這個(gè)變量可以用方差也可以不用)的函 數(shù)，從而算出最終的排序。最樸素的計(jì)算還是使用方差，計(jì)算每個(gè)維度區(qū)間中Rule數(shù)量的方差，取最小值為最高權(quán)值，這說(shuō)明Rule在某個(gè)區(qū)間的分布比其它 區(qū)間更加集中，從而有更高的可能切掉孩子的臍帶導(dǎo)致“快速失敗”！

7.區(qū)間覆蓋問(wèn)題

這是個(gè)問(wèn)題嗎？不是問(wèn)題。
       本文中，我們以區(qū)間為基準(zhǔn)，因此就可以把Ruleset進(jìn)行拆分。舉一個(gè)最簡(jiǎn)單的例子，設(shè)置Rule1，2的區(qū)間192.168.1.0/24被設(shè)置Rule1，3區(qū)間192.168.0.0/16覆蓋，但是這不是問(wèn)題，解決如下圖所示：

8.Dimension Tree并行匹配

不要在一棵樹上吊死！
       我們非要將整個(gè)匹配數(shù)據(jù)結(jié)構(gòu)塞到一棵樹中嗎？如果非要這么做，我們就失去了并行操作的可能性，因?yàn)橐豢脴涞膹母饺~子的路徑只有一條路徑，鑒于下層分支巨 量，瞎猜只是掰扯，你幾乎不可能猜對(duì)分支。那么怎么辦呢？由于最終的結(jié)果是N個(gè)維度(在我們的例子中，N為3)的匹配區(qū)間Ruleset取交集，那么就好 辦了，N個(gè)維度分別構(gòu)建N棵樹，N個(gè)處理進(jìn)程同時(shí)運(yùn)算，最終取交集。讓我們回到最初的那幅圖，點(diǎn)一下題：