硬件路由轉(zhuǎn)發(fā)原理淺析

有人問(wèn)我，對(duì)于路由轉(zhuǎn)發(fā)，硬件轉(zhuǎn)發(fā)表的性能真的要超出軟件查表比如Linux系統(tǒng)很多嗎？
我怎么回答呢？給出數(shù)據(jù)嗎？我沒(méi)有數(shù)據(jù)，因?yàn)槲业谋韭毑?是做這一塊的。給出理論嗎？恐怕我也沒(méi)那口才。畫個(gè)圖？我發(fā)現(xiàn)我系統(tǒng)沒(méi)有安裝畫邏輯電路的工具。那怎么辦？這個(gè)問(wèn)題的答案我真真在心里，只是難于言表，于 是乎，我采用手繪圖手機(jī)拍照的方式，展示一下硬件轉(zhuǎn)發(fā)表的威力，由于沒(méi)有實(shí)際數(shù)據(jù)，我采用相對(duì)比較的方式，讓諸位看一下軟件轉(zhuǎn)發(fā)為什么是個(gè)垃圾。也順便介 紹一下專業(yè)的路由器交換機(jī)是怎么轉(zhuǎn)發(fā)數(shù)據(jù)包的。
       不過(guò)，手繪圖實(shí)在是不敢恭維，所以我就照著手繪圖用viso畫了一個(gè)。

我是一個(gè)送貨修路的

人生有多少十年？
我想成為一名送貨的，修路的。我送的是IP數(shù)據(jù)報(bào)，修的是全光網(wǎng)絡(luò)。
如今是一個(gè)浮躁的年代，大家都在爭(zhēng)先恐后往食物鏈頂端爬，搞什么Android app，iOS什么的，而我始終在我自己感興趣的領(lǐng)域，一混就是10年！而這個(gè)領(lǐng)域，就是食物鏈的底端。

開(kāi)始前的聲明

我假設(shè)你已經(jīng)知道了基本的門電路的工作原理，比如與門，非門，或門，鎖存器，電容存儲(chǔ)單元，存儲(chǔ)陣列等基本概念。接下來(lái)我用這些門來(lái)展示一下一個(gè)數(shù)據(jù)包實(shí)際的路由查詢過(guò)程到底是個(gè)什么樣子。在繼續(xù)閱讀之前請(qǐng)注意，
對(duì)于專家：本文不適合你，因?yàn)檫@是我自己想的，我為初學(xué)者著想，沒(méi)有遵循CAM，TCAM的規(guī)范，空間利用也不好，總之，跟你想象中的相比，我的做法很垃圾。
對(duì)于不知情者：本文十分適合你，可以讓你瞬間體會(huì)精髓，這也是我的心愿。

step by step

首先給出一幅圖：

給定一個(gè)目標(biāo)IPv4地址，經(jīng)過(guò)幾個(gè)門就可以找到下一跳的索引，是不是很奇妙啊。事實(shí)上真的就是這樣。
       如果你仔細(xì)看這個(gè)圖的話，你可能會(huì)發(fā)現(xiàn)，這有什么了不起的啊，你的譯碼器譯碼的是32bit的地址，也就是說(shuō)32位的全集，4G個(gè)地址，每一個(gè)前綴都必須 有4G個(gè)entry的空間，這可怎能受得了啊，但是我要說(shuō)的是，這里僅僅給出一個(gè)例子，我當(dāng)然知道用N路組相連的方式來(lái)組織，但是那樣會(huì)加入一些比較門電 路，不直觀，所以我就直接用32位地址鍵了。也許你還會(huì)反駁，即便用軟件，我建立一個(gè)4G大小的hash表，用IPv4地址本身作為hash值，不更加簡(jiǎn) 單嗎？不比硬件實(shí)現(xiàn)更加優(yōu)化嗎？我想說(shuō)的是，NO！Why？請(qǐng)看一個(gè)CPU cache的普通命中過(guò)程，以下是圖示：

跟 一個(gè)IPv4地址路由查找過(guò)程相比，少不了幾個(gè)門。注意，這只是在訪存之前的cache匹配的門電路，這還算是比較高效的，如果沒(méi)有命中，訪存的電路涉及 到的電路自不必說(shuō)，單單是CPU的執(zhí)行單元這些電路就夠了，如果你了解微結(jié)構(gòu)，那你就會(huì)知道，一條指令的執(zhí)行也是一個(gè)極其復(fù)雜的過(guò)程，CPU內(nèi)部有通用執(zhí) 行單元，流水線等，每一個(gè)步驟都是要花費(fèi)時(shí)鐘周期的，那么請(qǐng)問(wèn)，以下的代碼需要多少門電路呢？
entry = bucket[destIP];
nexthop = entry->nexthop;
先把它翻譯成匯編然后再看吧。更何況，你不可能創(chuàng)建一個(gè)如此龐大的hash表，常規(guī)的看，TRIE樹(shù)查找法算是高效的了，比它更高效的是我自己的DxR Pro++結(jié)構(gòu)，但是即便是DxR Pro++，和上述的硬件轉(zhuǎn)發(fā)相比，也是弱爆了的了。
       繼續(xù)看上面的硬件路由轉(zhuǎn)發(fā)原理圖，譯碼器后面的交叉網(wǎng)絡(luò)事實(shí)上應(yīng)該畫成黑盒子更加清爽些，但是我還是情不自禁地畫成了不倫不類的樣子，每一個(gè)交叉點(diǎn)上都存 著1bit的數(shù)據(jù)，它非0即1。譯碼器譯碼的結(jié)果選擇一根字線，然后該字線上的所有與之交叉的位線由于字線電平拉高，交叉點(diǎn)上的1bit數(shù)據(jù)就稀里嘩啦掉 下來(lái)了，這其實(shí)也是內(nèi)存訪問(wèn)的原理。在第一個(gè)譯碼器后面，有一個(gè)比較重要的操作，那就是“最長(zhǎng)前綴”的邏輯，我不知道標(biāo)準(zhǔn)的TCAM是怎么做的，但是我覺(jué) 得我的上述的方式也能說(shuō)明問(wèn)題。引入了兩個(gè)概念，反掩碼和消除位，其中反掩碼是掩碼按位取反的結(jié)果，而消除位是為了唯一取得匹配到的“最長(zhǎng)前綴”那一項(xiàng) 的。最終，我們得到了匹配到的最長(zhǎng)前綴的那一項(xiàng)對(duì)應(yīng)的下一跳索引地址，然后再來(lái)一個(gè)譯碼過(guò)程，通過(guò)地址得到下一跳索引，取得勝利。
       注意，所有的操作都是同時(shí)進(jìn)行的，在匹配28位前綴的同時(shí)，24位，16位，10位，8位前綴也在同步匹配，它們同時(shí)經(jīng)過(guò)同一組門。這就是優(yōu)勢(shì)！

硬件轉(zhuǎn)發(fā)和CPU轉(zhuǎn)發(fā)

我們發(fā)現(xiàn)，上面我描述的那個(gè)電路幾乎不能干別的，它只能為一個(gè)IPv4地址查詢下一跳(當(dāng)然還有寫入，刪除等電路邏輯，我沒(méi)有畫出來(lái))，然而就是這樣一個(gè)電路，比CPU那個(gè)復(fù)雜的東西效率高多了，所謂它是專業(yè)的，而CPU只是通用的。
       CPU作為一個(gè)通用執(zhí)行單元，它完全是傻瓜的，卻又什么都能做，具體要做什么，是通過(guò)從內(nèi)存中獲取的“指令”來(lái)指示的，也就是說(shuō)，指令本身就是數(shù)據(jù)的一種表現(xiàn)形式，編程的本質(zhì)是什么？編程的本質(zhì)就是從內(nèi)存中獲取的指令對(duì)CPU內(nèi)部電路的編程。
       然而，對(duì)于硬件轉(zhuǎn)發(fā)而言，它的輸入是一個(gè)IPv4地址，純粹一個(gè)數(shù)據(jù)！它沒(méi)有指令，指令就是電路本身。所以，它可以同時(shí)進(jìn)行這一切，就好像這條“指令”是 從外部輸入的一樣。CPU不能執(zhí)行這樣的“指令”是因?yàn)檫@個(gè)指令它特殊了，現(xiàn)代處理器越來(lái)越多地向RISC發(fā)展，由程序員和編譯器自己完全來(lái)決定要做什 么，而不是處理器的設(shè)計(jì)者猜測(cè)程序員會(huì)用到什么功能那樣子。我可以想得極端一點(diǎn)，如果在一款CISC處理器中，它為了對(duì)得起它的分類，它的設(shè)計(jì)者為其設(shè)計(jì) 了一條“路由查詢”的指令，那么該通過(guò)CISC處理器內(nèi)部的電路，真的有可能跟我上面的這個(gè)差不多。
       眼睛有點(diǎn)睜不開(kāi)了....