論內(nèi)容可尋址存儲器CAM在交換機(jī)中的應(yīng)用

1、論內(nèi)容可尋址存儲器CAM在交換機(jī)中的應(yīng)用            關(guān)鍵詞：CAM 數(shù)據(jù)檢索 嵌入式實(shí)時控制系統(tǒng) MAC RTOS內(nèi)容可尋址存儲器（ 是一種特殊的存儲陣列。它具有將輸入數(shù)據(jù)與中存儲的所有數(shù)據(jù)項(xiàng)同時進(jìn)行比較，迅速判斷輸入數(shù)據(jù)是否與中存儲的數(shù)據(jù)項(xiàng)相匹配，并給出數(shù)據(jù)項(xiàng)對應(yīng)地址和匹配信息的特點(diǎn)，因而被廣泛地應(yīng)用于通信、模式識別等領(lǐng)域。在某型號交換機(jī)的設(shè)計(jì)中，筆者應(yīng)用公司的芯片實(shí)現(xiàn)數(shù)據(jù)檢索功能，既提高了系統(tǒng)資源的利用率，又保障了系統(tǒng)性能，大大縮短開發(fā)周期。 功能簡述是一種基

2、于技術(shù)的存儲器，數(shù)據(jù)項(xiàng)存儲在內(nèi)部的陣列中。每個數(shù)據(jù)項(xiàng)的位數(shù)叫字寬，陣列內(nèi)所有數(shù)據(jù)項(xiàng)的條數(shù)叫做的深度，的容量通過字寬和深度來表征。可存儲條寬度為 位的數(shù)據(jù)項(xiàng)。圖所示為的結(jié)構(gòu)框圖。有兩個數(shù)據(jù)端口：控制端口（ ）和匹配端口（ ）。控制端口用于表（ ）的操作，除用于數(shù)據(jù)項(xiàng)的增加刪除、校驗(yàn)、統(tǒng)計(jì)外，還可以讀取芯片內(nèi)部狀態(tài)寄存器的信息。數(shù)據(jù)的檢索通過匹配端口完成。盡管基于技術(shù)，的存儲機(jī)制卻與大相徑庭。如圖所示，沒有用于確定內(nèi)容存儲地址的地址總線，地址線用于對片內(nèi)控制寄存器的尋址。在寫模式下，從控制端口數(shù)據(jù)線讀取需要寫入的數(shù)據(jù)項(xiàng)，數(shù)據(jù)項(xiàng)的存儲地址由芯片內(nèi)部邏輯控制。用戶可對的匹配規(guī)則進(jìn)行編程，在讀模式（查找

3、匹配）時，直接從匹配口數(shù)據(jù)線讀入數(shù)據(jù)，并按照預(yù)先定義的匹配規(guī)則將輸入數(shù)據(jù)項(xiàng)與陣列中的所有數(shù)據(jù)項(xiàng)進(jìn)行并行比較。如果數(shù)據(jù)項(xiàng)存在，匹配口輸出該數(shù)據(jù)項(xiàng)的索引值，且為；如果數(shù)據(jù)項(xiàng)不存在，為。由于比較過程只需一個時鐘周期，所以速度極快。的最長匹配時間為。有兩種工作模式：模式和基本模式。模式主要用于交換機(jī)中對信元的處理?；灸Ｊ降膽?yīng)用十分靈活，由于匹配規(guī)則可編程，用戶可根據(jù)不同的應(yīng)用場合實(shí)現(xiàn)檢索功能。 應(yīng)用實(shí)例 設(shè)計(jì)要求某型號交換機(jī)根據(jù)產(chǎn)品定義用于網(wǎng)絡(luò)和基于以態(tài)網(wǎng)的城域網(wǎng)（ ）的連接。其端口工作速率為，以太網(wǎng)端口工作速率為。系統(tǒng)數(shù)據(jù)流如圖所示。圖2 交換機(jī)系統(tǒng)數(shù)據(jù)流圖上行方向，交換機(jī)首先在系統(tǒng)內(nèi)嵌的通道表內(nèi)

4、檢查每一個信元內(nèi)的虛通路值虛鏈接值（ ，標(biāo)識一條虛通道虛鏈接）是否存在。如果存在，獲得該的配置信息，準(zhǔn)備下一步的協(xié)議處理。如果輸入信元的不存在，則丟棄該信元。輸入的信元經(jīng)協(xié)議處理后，包含在信元中的以太網(wǎng)幀被提取出來。交換機(jī)接著對以太網(wǎng)幀的源地址進(jìn)行檢索，判斷該以太網(wǎng)幀是否來自已知的用戶。如果在系統(tǒng)內(nèi)嵌的表中檢索到該地址，則表明該以太網(wǎng)幀來自已知的用戶，系統(tǒng)隨即刷新老化標(biāo)記，將其轉(zhuǎn)發(fā)至以太網(wǎng)接口；如果不存在，則系統(tǒng)將在表中添加該地址并設(shè)置老化標(biāo)記，而后交換機(jī)將該以太網(wǎng)幀轉(zhuǎn)發(fā)1 2 3 4 下一頁      

5、   至以太網(wǎng)接口。下行方向，系統(tǒng)首先以輸入以太網(wǎng)幀的目的地址為關(guān)鍵字在表中進(jìn)行檢索，該地址就是上文提到的源地址。如果目的地址不存在，則將輸入的以太網(wǎng)幀轉(zhuǎn)換為信元，向所有用戶端口廣播；如果匹配成功，交換機(jī)獲得與該地址對應(yīng)的，將以太網(wǎng)幀轉(zhuǎn)換為信元，并根據(jù)通道表，從指定的用戶端口轉(zhuǎn)發(fā)至終端，最后送達(dá)用戶主機(jī)。嵌入式實(shí)時控制系統(tǒng)的性能主要取決于兩方面：硬件平臺的運(yùn)算性能和算法的優(yōu)越性。其中硬件平臺的運(yùn)算性能最為關(guān)鍵，這一點(diǎn)在交換機(jī)中表現(xiàn)得由為突出。按照設(shè)計(jì)要求，信元的檢索必須在的信元接收時間內(nèi)完成，即，以太網(wǎng)幀的地址的檢索時間不能超過。因此首先要保證數(shù)據(jù)檢索任務(wù)的響應(yīng)速

6、度；其次，由于交換機(jī)數(shù)據(jù)流量大，對于本系統(tǒng)的端口，系統(tǒng)每秒必須處理約，幀信元，數(shù)據(jù)檢索任務(wù)十分繁重；另外，除了業(yè)務(wù)數(shù)據(jù)的雙向協(xié)議處理外，交換機(jī)還必須完成（ ）協(xié)議處理、命令行處理等任務(wù)，所以還必須解決數(shù)據(jù)檢索對系統(tǒng)資源的占用問題。提高性能的方法一般有兩種，最直接的方法就是采用高性能的硬件平臺，如采用分布式控制系統(tǒng)，一個用于協(xié)議處理，另一個用于網(wǎng)管等事務(wù)處理；或者協(xié)議處理部分由完成，事務(wù)處理部分由實(shí)現(xiàn)。但這些方案會帶來硬件成本的大幅提高。另外一種方案就是采用更優(yōu)化的算法。通過分析發(fā)現(xiàn)，盡管利用軟件實(shí)現(xiàn)對信元的和以太網(wǎng)幀的地址檢索并不復(fù)雜，但由于檢索次數(shù)頻繁，大量的系統(tǒng)資源被占用，系統(tǒng)的響應(yīng)速度大

7、大降低，滿足不了大流量數(shù)據(jù)通信的要求。因此純軟件算法解決不了數(shù)據(jù)檢索部分對資源占用的問題。為提高系統(tǒng)的響應(yīng)速度，必須將這兩部分?jǐn)?shù)據(jù)檢索的任務(wù)分離出來由硬件實(shí)現(xiàn)，協(xié)議處理部分還由完成。數(shù)據(jù)檢索模塊和協(xié)議處理模塊并行工作，兩部分通過數(shù)據(jù)耦合，既可以提高模塊的內(nèi)聚度，又增強(qiáng)了算法的健壯性；并且利用硬件實(shí)現(xiàn)數(shù)據(jù)檢索還可以提高檢索速度，降低系統(tǒng)資源的占用率。利用硬件進(jìn)行數(shù)據(jù)檢索，通常采用兩種策略一種是利用或等可編程邏輯器件定制數(shù)據(jù)檢索單元。本系統(tǒng)兩種地址的數(shù)據(jù)結(jié)構(gòu)并不復(fù)雜，定制簡單數(shù)據(jù)結(jié)構(gòu)的檢索單元體現(xiàn)不了可編程邏輯器件功能強(qiáng)大、靈活性強(qiáng)等優(yōu)越性，并且這類器件的開發(fā)難度相對較大，完成后還需要相當(dāng)長一段時

8、間進(jìn)行測試。另一種策略是選擇實(shí)現(xiàn)數(shù)據(jù)檢索。兩者比較，本系統(tǒng)采用。根據(jù)系統(tǒng)設(shè)計(jì)，本交換機(jī)采用兩塊實(shí)現(xiàn)數(shù)據(jù)檢索功能，用于以太網(wǎng)幀的地址檢索，用于信元的檢索，如圖所示。 檢索算法設(shè)計(jì)下面根據(jù)系統(tǒng)設(shè)計(jì)方案，以表為例說明以太網(wǎng)側(cè)數(shù)據(jù)檢索功能的實(shí)現(xiàn)。如圖所示，表由硬件、軟件兩個子模塊構(gòu)成。表實(shí)現(xiàn)地址到偏移地址的查詢，這部分由硬件實(shí)現(xiàn)；表實(shí)現(xiàn)偏移地址到配置信息的查詢，這部分由軟件實(shí)現(xiàn)；兩者通過偏移地址耦合。本系統(tǒng)將每一個認(rèn)為是一個用戶端口，的值保存在用戶端口域。當(dāng)進(jìn)行地址檢索時，首先以地址為關(guān)鍵字通過表的檢索得到對應(yīng)的偏移地址，然后再根據(jù)公式（）得到表中該地址的存儲位置，并由此地址獲得相關(guān)配置信息。表中標(biāo)志

9、域、標(biāo)志域分別表示用戶地址的狀態(tài)信息，限于篇幅這里不詳述了。地址基地址 × （）公式（）中，基地址是表的起始地址；是通過表查詢得到的偏移量，即地址的索引值；表示表中的一個表項(xiàng)上一頁  1 2 3 4 下一頁         的寬度為多少字節(jié)。與表的實(shí)現(xiàn)基本相同，通道表的實(shí)現(xiàn)也分為兩部分，一部分由硬件實(shí)現(xiàn)，另一部分由軟件實(shí)現(xiàn)。執(zhí)行檢索時，先通過得到某的偏移地址，然后再根據(jù)該偏移地址得到表中保存的具體配置。正是通過表和通道表，本系統(tǒng)實(shí)現(xiàn)了網(wǎng)絡(luò)與的交換

10、。 檢索算法的實(shí)現(xiàn)按協(xié)議規(guī)定地址占位，表示為字節(jié)的數(shù)組。圖和圖分別表示了表中地址的高位數(shù)據(jù)和低位數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。圖所示為地址索引項(xiàng)的數(shù)據(jù)結(jié)構(gòu)，它分為兩部分：最高位為匹配標(biāo)志（），表示匹配成功，表示匹配失??；匹配輸出的低位為地址的索引（），用戶可按需要對其進(jìn)行定義，如地址的索引值為。不同的協(xié)議要求，表的數(shù)據(jù)結(jié)構(gòu)與表的數(shù)據(jù)結(jié)構(gòu)并不相同。但由于處理方式相近，這里就不贅述了。的匹配規(guī)則由通用屏蔽字（ ）制定。進(jìn)行檢索時，將檢索內(nèi)容與通用屏蔽字進(jìn)行按位或運(yùn)算，表示屏蔽該位的值，表示對該位敏感。從上文可看到，兩種數(shù)據(jù)檢索的數(shù)據(jù)結(jié)構(gòu)大不相同，因此需要不同的匹配規(guī)則。根據(jù)本系統(tǒng)設(shè)計(jì)要求，信元的檢索只對敏感，因

11、此通用屏蔽字為，即忽略字段和地址標(biāo)識段。對于地址的匹配操作，通用屏蔽字為，即位匹配。通用屏蔽字的設(shè)定必須在初始化時完成。在執(zhí)行匹配操作前，須進(jìn)行初始化。由于和的工作模式不同，因此兩者的初始化過程亦不盡相同。下面以為例，用偽碼形式說明初始化過程。（） ； ； ； ； ；對于，首先必須設(shè)定工作模式，工作于模式；然后對通用屏蔽字進(jìn)行設(shè)置，以保證正確的匹配規(guī)則；緊接著，將設(shè)為快速輸入模式（ ，當(dāng)需要將大量數(shù)據(jù)寫入時，該模式能加快輸入速度），將預(yù)先定義好的 表寫入；最后執(zhí)行表初始化指令。至此，能夠正常工作了。前面已提到，表的形成是通過自學(xué)習(xí)得到的，因此的初始化并不需要該過程。另外，工作在基本模式，上電后

12、，默認(rèn)工作模式為基本模式。因此的初始化只需要兩步，通用屏蔽字的設(shè)置和表初始化。圖4、圖5和圖6匹配操作通過對匹配口讀寫完成。匹配口數(shù)據(jù)線只有位。由于地址占位，因此需要兩次寫操作才能完整地將一個地址表達(dá)出來；而只占位，因此只需一次寫操作就可以了。下面以地址的檢索為例說明的匹配操作過程。當(dāng)進(jìn)行地址檢索時，先向匹配口寫入如圖所示的低位數(shù)據(jù)，其中高位有效，低位可以為任意值；緊接著向匹配口寫入如圖所示的高位數(shù)據(jù)；隨后讀匹配口，就可得到如圖所示的結(jié)果。如果被查詢的地址存在，則位為，為有效輸出；如果被查詢的地址不存在，則位為，為輸出無效。上述過程可通過偽碼表示如下： 上一頁  1 2 3 4 下