交換技術(shù)基于CAM的路由查找算法

　在線輔導(dǎo)　面授招生　考試大綱　指定教材　試題匯總

1.基于CAM的路由查找算法
1）CAM及TCAM路由查找原理
目前路由查找使用最多的硬件實(shí)現(xiàn)方法是使用內(nèi)容尋址存儲(chǔ)器（ContentAddressableMemory,CAM)來進(jìn)行快速路由查找，CAM能夠在一個(gè)硬件時(shí)鐘周期內(nèi)完成關(guān)鍵字的精確匹配查找。常用的隨機(jī)存儲(chǔ)器（RAM)通過輸人地址來返回該地址處所對(duì)應(yīng)的表項(xiàng)信息，但是CAM的訪問方式不同，因?yàn)橐粋€(gè)CAM表項(xiàng)包含兩部分：査找域（Seareh-Field)和返回域（Retum-Field)。查找域是和查找內(nèi)容相匹配的部分（一般含有已知的目的地址）；返回域含有相關(guān)信息或一個(gè)索引。這樣，CAM就會(huì)將輸人分組關(guān)鍵字與CAM中的所有表項(xiàng)同時(shí)進(jìn)行匹配比較，最后返回匹配表項(xiàng)返回域所包含的信息。
CAM的主要操作有3種：在空閑位置寫人新表項(xiàng)；査找四配表項(xiàng)；讀取匹配表項(xiàng)包含的相關(guān)信息。
如果相關(guān)信息童很小，可以直接存儲(chǔ)在CAM表項(xiàng)返回域中。這種直接訪問速度快，復(fù)雜度低，但是因?yàn)槌杀疽蛩?，CAM表項(xiàng)不能太大，所以相關(guān)信息量必須盡量小。當(dāng)相關(guān)信息量很大時(shí)，CAM表項(xiàng)不能直接存儲(chǔ)，而是存儲(chǔ)一個(gè)索引號(hào)，可以直接訪問該索引號(hào)，用來讀取索引號(hào)所指示的RAM表項(xiàng)中的信息。這種間接訪問比直接訪問速度慢，復(fù)雜度髙，但是對(duì)相關(guān)信息量沒有限制。
傳統(tǒng)CAM只能執(zhí)行精確匹配，一般不適用于IP路由表。如果要使用CAM來進(jìn)行最長(zhǎng)前綴匹配路由查找，可以讓每一類可能的地址前綴長(zhǎng)度使用一個(gè)CAM,每個(gè)CAM保存對(duì)應(yīng)長(zhǎng)度的所有前綴的集合。對(duì)于IPv4來說，則一共需要使用32個(gè)CAM。這種方法有一個(gè)明顯缺點(diǎn)，即在對(duì)地址前綴長(zhǎng)度具體分布沒有準(zhǔn)確了解之前，為了保證能夠存儲(chǔ)"個(gè)前綴的表項(xiàng)，每個(gè)CAM都需要有W個(gè)表項(xiàng)的空間，因此，CAM存儲(chǔ)空間的利用率較低。

為了克服上述方法的缺點(diǎn)，提出了另一種CAM實(shí)現(xiàn)機(jī)制TCAM(TernaryCAM)0TCAM-242-與傳統(tǒng)CAM的區(qū)別是，后者表項(xiàng)的各個(gè)比特位只能是0或1，而前者的則有三個(gè)狀態(tài)：0，1或X。X是一種無關(guān)態(tài)，可以是“0”或“1”，它由局部掩碼來實(shí)現(xiàn)，而且可以表示可變長(zhǎng)前綴。TCAM中前綴表示如圖7-46所示，當(dāng)局部掩碼的某位為“0”時(shí)，則對(duì)應(yīng)的前綴位為無關(guān)位，如前5位為“11111”或“11110”的關(guān)鍵字將匹配圖7-46中的第0項(xiàng)（項(xiàng)0)。TCAM的另外一個(gè)非常有用的特點(diǎn)是不要求掩碼中的“1”和“0”連續(xù)，如圖7-46中的第n-m,其中前綴的第2位因?yàn)榫植垦诖a為0而表示為無關(guān)位，則前3位為“110”和“100”的關(guān)鍵字都可以匹配第1項(xiàng)?？梢岳么诵再|(zhì)對(duì)路由表進(jìn)行壓縮，減少對(duì)TCAM的占用。

返回目錄： 通信專業(yè)交換技術(shù)非連接型快速分組交換匯總

編輯推薦

通信專業(yè)實(shí)務(wù)考試終端與業(yè)務(wù)教程匯總

通信專業(yè)實(shí)務(wù)考試設(shè)備與環(huán)境教程匯總

通信工程師考試培訓(xùn)交換理論基確匯總