摘? 要: 介紹了內容可尋址存儲器CAM MCM69C233的特點及使用。通過某交換機應用表明,可大幅度提高數據檢索" title="數據檢索">數據檢索速度,增強系統可靠性。

　　關鍵詞: CAM? 數據檢索? 嵌入式實時控制系統

?

　　內容可尋址存儲器CAM(Content Addressable Memory)是一種特殊的存儲陣列。它具有將輸入數據與CAM中存儲的所有數據項同時進行比較,迅速判斷輸入數據是否與CAM中存儲的數據項相匹配,并給出數據項對應地址和匹配信息的特點,因而被廣泛地應用于通信、模式識別等領域。在某型號交換機的設計中,筆者應用MOTOROLA公司的CAM芯片——MCM69C233實現數據檢索功能,既提高了系統資源的利用率,又保障了系統性能,大大縮短開發周期。

1 MCM69C233功能簡述

　　CAM是一種基于RAM技術的存儲器,數據項存儲在CAM內部的陣列中。每個數據項的位數叫字寬,陣列內所有數據項的條數叫做CAM的深度,CAM的容量通過字寬和深度來表征。MCM69C233可存儲4096條寬度為64 位的數據項。圖1所示為MCM69C233的結構框圖。

?

?

　　MCM69C233有兩個數據端口:控制端口(Control Port)和匹配端口(Match Port)?？刂贫丝谟糜贑AM表(CAM Table)的操作,除用于數據項的增加/刪除、校驗、統計外,還可以讀取芯片內部狀態寄存器的信息。數據的檢索通過匹配端口完成。盡管基于RAM技術,CAM的存儲機制卻與RAM大相徑庭。如圖1所示,MCM69C233沒有用于確定內容存儲地址的地址總線,地址線A0～A2用于對片內控制寄存器的尋址。在寫CAM模式下,MCM69C233從控制端口數據線DQ0~DQ15讀取需要寫入的數據項,數據項的存儲地址由芯片內部邏輯控制。

　　用戶可對MCM69C233的匹配規則進行編程,在讀CAM模式(查找匹配)時,MCM69C233直接從匹配口數據線MQ0~MQ31讀入數據,并按照預先定義的匹配規則將輸入數據項與陣列中的所有數據項進行并行比較。如果數據項存在,匹配口輸出該數據項的索引值,且MS為0;如果數據項不存在,/MS為1。由于比較過程只需一個時鐘周期,所以速度極快。MCM69C233的最長匹配時間為210ns。

MCM69C233有兩種工作模式:ATM模式和基本模式。ATM模式主要用于ATM交換機中對ATM信元" title="信元">信元的處理?；灸Ｊ降膽檬朱`活,由于匹配規則可編程,用戶可根據不同的應用場合實現檢索功能。

2 應用實例

2.1 設計要求

　　某型號交換機根據產品定義用于ATM網絡和基于以態網的城域網E-MAN(Ethernet Metropolitan Area Network)的連接。其ATM端口工作速率為155Mbps,以太網端口工作速率為100Mbps。系統數據流如圖2所示。

?

?

　　上行方向,交換機首先在系統內嵌的VP/VC通道表內檢查每一個ATM信元內的虛通路值/虛鏈接值VPI/VCI(Virtual Path Index/Virtual Connection Index,標識一條虛通道/虛鏈接VP/VC)是否存在。如果存在,CPU獲得該VP/VC的配置信息,準備下一步的協議處理。如果輸入信元的VPI/VCI不存在,則丟棄該信元。

　　輸入的ATM信元經協議處理后,包含在ATM信元中的以太網幀被提取出來。交換機接著對以太網幀的源MAC地址進行檢索,判斷該以太網幀是否來自已知的用戶。如果在系統內嵌的MAC-VP/VC表中檢索到該MAC地址,則表明該以太網幀來自已知的用戶,系統隨即刷新老化標記,將其轉發至以太網接口;如果不存在,則系統將在MAC-VP/VC表中添加該MAC地址并設置老化標記,而后交換機將該以太網幀轉發至以太網接口。

　　下行方向,系統首先以輸入以太網幀的目的MAC地址為關鍵字在MAC-VP/VC表中進行檢索,該地址就是上文提到的源MAC地址。如果目的MAC地址不存在,則將輸入的以太網幀轉換為ATM信元,向所有用戶端口廣播;如果匹配成功,交換機獲得與該MAC地址對應的VPI/VCI,將以太網幀轉換為ATM信元,并根據VPI/VCI通道表,從指定的用戶端口轉發至ADSL終端,最后送達用戶主機。

嵌入式實時控制系統的性能主要取決于兩方面:硬件平臺的運算性能和算法的優越性。其中硬件平臺的運算性能最為關鍵,這一點在交換機中表現得由為突出。按照設計要求" title="設計要求">設計要求,ATM信元的VPI/VCI檢索必須在1/4～1/2的信元接收時間內完成,即684ns～1.37μs,以太網幀的MAC地址的檢索時間不能超過5.12μs。因此首先要保證數據檢索任務的響應速度" title="響應速度">響應速度;其次,由于交換機數據流量大,對于本系統的ATM端口,系統每秒必須處理約365,566幀ATM信元,數據檢索任務十分繁重;另外,除了業務數據的ATM-Ethernet雙向協議處理外,交換機還必須完成SNMP(Simple Network Management Protocol)協議處理、命令行處理等任務,所以還必須解決數據檢索對系統資源的占用問題。

　　提高性能的方法一般有兩種,最直接的方法就是采用高性能的硬件平臺,如采用分布式控制系統,一個CPU用于協議處理,另一個CPU用于網管等事務處理;或者協議處理部分由ASIC完成,事務處理部分由CPU實現。但這些方案會帶來硬件成本的大幅提高。另外一種方案就是采用更優化的算法。通過分析發現,盡管利用軟件實現對ATM信元的VPI/VCI和以太網幀的MAC地址檢索并不復雜,但由于檢索次數頻繁,大量的系統資源被占用,系統的響應速度大大降低,滿足不了大流量數據通信的要求。因此純軟件算法解決不了數據檢索部分對資源占用的問題。為提高系統的響應速度,必須將這兩部分數據檢索的任務分離出來由硬件實現,協議處理部分還由CPU完成。數據檢索模塊和協議處理模塊并行工作,兩部分通過數據耦合,既可以提高模塊的內聚度,又增強了算法的健壯性;并且利用硬件實現數據檢索還可以提高檢索速度,降低系統資源的占用率。

　　利用硬件進行數據檢索,通常采用兩種策略:一種是利用FPGA或CPLD等可編程邏輯器件定制數據檢索單元。本系統兩種地址的數據結構" title="數據結構">數據結構并不復雜,定制簡單數據結構的檢索單元體現不了可編程邏輯器件功能強大、靈活性強等優越性,并且這類器件的開發難度相對較大,完成后還需要相當長一段時間進行測試。另一種策略是選擇CAM實現數據檢索。兩者比較,本系統采用CAM。根據系統設計,本交換機采用兩塊CAM實現數據檢索功能,MAC-CAM用于以太網幀的MAC地址檢索,ATM-CAM用于ATM信元的VPI/VCI檢索,如圖2所示。

2.2 檢索算法設計

　　下面根據系統設計方案,以MAC-VP/VC表為例說明以太網側數據檢索功能的實現。如圖3所示,MAC-VP/VC表由硬件、軟件兩個子模塊構成。MAC-CAM表實現MAC地址到偏移地址的查詢,這部分由硬件實現;RAM表實現偏移地址到配置信息的查詢,這部分由軟件實現;兩者通過偏移地址耦合。本系統將每一個VP/VC認為是一個用戶端口,VP/VC的值保存在用戶端口域。

?

?

　　當進行MAC地址檢索時,CPU首先以MAC地址為關鍵字通過MAC-CAM表的檢索得到對應的偏移地址a,然后再根據公式(1)得到RAM表中該MAC地址的存儲位置,并由此地址獲得相關配置信息。RAM表中標志域1、標志域2分別表示用戶MAC地址的狀態信息,限于篇幅這里不詳述了。

　　RAM地址=基地址 + a×b?? (1)

　　公式(1)中,基地址是RAM表的起始地址;a是通過MAC-CAM表查詢得到的偏移量,即MAC地址的索引值;b表示RAM表中的一個表項的寬度為多少字節。

　　與MAC-VP/VC表的實現基本相同,VPI/VCI通道表的實現也分為兩部分,一部分由硬件CAM實現,另一部分由軟件實現。執行VPI/VCI檢索時,CPU先通過CAM得到某VPI/VCI的偏移地址,然后再根據該偏移地址得到RAM表中保存的具體配置。

正是通過MAC-VP/VC表和VPI/VCI通道表,本系統實現了ATM網絡與E-MAN的交換。

2.3 檢索算法的實現

　　按協議規定MAC地址占48位,表示為6字節的數組。圖4和圖5分別表示了MAC-CAM表中MAC地址的高32位數據和低16位數據的數據結構。

?

?

　　圖6所示為MAC地址索引項的數據結構,它分為兩部分:最高位為匹配標志(MS),0表示匹配成功,1表示匹配失敗;匹配輸出的低16位為MAC地址的索引(macIndex),用戶可按需要對其進行定義,如MAC地址00-3C-CD-17-65-AB的索引值為0x03EF。

不同的協議要求,VPI/VCI表的數據結構與MAC表的數據結構并不相同。但由于處理方式相近,這里就不贅述了。

　　MCM69C233的匹配規則由通用屏蔽字(Global Mask)制定。進行檢索時,MCM69C233將檢索內容與通用屏蔽字進行按位或運算,1表示屏蔽該位的值,0表示對該位敏感。從上文可看到,兩種數據檢索的數據結構大不相同,因此需要不同的匹配規則。根據本系統設計要求,ATM信元的檢索只對VPI/VCI敏感,因此通用屏蔽字為0xFF00_0000_FFFF_FFFF,即忽略GFC字段和PHY地址標識段。對于MAC地址的匹配操作,通用屏蔽字為0x0000_0000_0000_FFFF,即48位匹配。通用屏蔽字的設定必須在CAM初始化時完成。

　　在執行匹配操作前,CAM須進行初始化。由于ATM-CAM和MAC-CAM的工作模式不同,因此兩者的初始化過程亦不盡相同。下面以ATM-CAM為例,用偽碼形式說明初始化過程。

　　atmCamInit()

　　{　

????????????? Set ATM_CAM working on ATM mode;

????????????? Set the Global mask register for VPI/VCI translation;

????????????? Set the ATM_CAM to fast entry mode;

????????????? Input VPC table;

????????????? Initialize VPC table;

　　}

　　對于ATM-CAM,首先必須設定工作模式,ATM-CAM工作于ATM模式;然后對通用屏蔽字進行設置,以保證正確的匹配規則;緊接著,將ATM-CAM設為快速輸入模式(Fast entry mode,當需要將大量數據寫入CAM時,該模式能加快輸入速度),將預先定義好的VPI/VCI-Channel Code表寫入CAM;最后執行表初始化指令。至此,ATM-CAM能夠正常工作了。前面已提到,MAC表的形成是通過自學習得到的,因此MAC-CAM的初始化并不需要該過程。另外,MAC-CAM工作在基本模式,MCM69C233上電后,默認工作模式為基本模式。因此MAC-CAM的初始化只需要兩步,通用屏蔽字的設置和表初始化。

　　匹配操作通過對匹配口讀/寫完成。匹配口數據線只有32位。由于MAC地址占48位,因此需要兩次寫操作才能完整地將一個MAC地址表達出來;而VPI/VCI只占24位,因此只需一次寫操作就可以了。下面以MAC地址的檢索為例說明CAM的匹配操作過程。

當進行MAC地址檢索時,CPU先向匹配口寫入如圖4所示的低32位數據,其中高16位有效,低16位可以為任意值;緊接著CPU向匹配口寫入如圖5所示的高32位數據;隨后CPU讀匹配口,就可得到如圖6所示的結果。如果被查詢的MAC地址存在,則MS位為0,macIndex為有效輸出;如果被查詢的MAC地址不存在,則MS位為1,macIndex為輸出無效。上述過程可通過偽碼表示如下:

　　STATUS macCamCheckEntry( )

　　{

? 　　Write low 32-bit word to match port in first cycle；

?　　 Write high 32-bit word to match port in second cycle；

? 　　Read 32-bit result from match port；

?　 　If MS flag is “1”

??　??There is no such Entry；

? 　　Else return macIndex；

　　{

3 運行結果

　　某交換機的運行結果表明， 采用CAM， 交換機的以太網端口能工作在100Mbps,基本滿足設計要求;如采用軟件搜索方法， 則只能達到30Mbps。

?

參考文獻

1 嚴蔚敏,吳偉民. 數據結構(第二版). 北京:清華大學出版社,1996

2 張海藩. 軟件工程導論(第三版). 北京:清華大學出版社,1998

3 Robert L. Kruse， Clovis L. Tondo， Bruce P. Leung.Data?Structures & Program Design In C. 2nd， Edition. Prentice-Hall International， Inc. 1997

4 Motorola，Inc.MCM69C233 Data Sheet. 2001