快速路由查找的方法和系統的製作方法

2024-02-16 10:30:15

><![CDATA[　　*/　　typedefstructmentry{　　unit16mask；/*16位模式(最低位總是被置位！)*/　　unit16len；/*8位長度(值1～16)*/　　MAPVECmap；/*4組中16個4位偏移*/　　}MENTRY，*MP；　　voidmentry2mcompact(MENTRY*from，MCOMPACT*to)　　/*將變換部分從「from」存入「to」*/　　{　　inti；　　for(i＝0；i＜MAPVECLEN；i++){　　(*to)[i]＝from-＞map[i]；　　}　　}　　externvoidmtable_compact　　/*從mtable對mt初始化*/　　{　　registerinti；for(i＝0；i＜TMAX；i++){　　mentry2mcompact(mtable[i]，mt[i])；　　}　　}]]>數據結構的第二層和第三層包括字節片。一個字節片覆蓋高度為8的一棵子樹，最多可以包括28＝256個頭。第n-1層的一個根頭指向第n層的一個字節片。有三種字節片，依賴於想像的位矢量包含幾個頭。有1～8個頭時，字節片是稀疏的(sparse)，用頭的8位下標數組，再加上8個16位指針表示，總共有24位。有9～64個頭時，字節片是稠密的(dense)。它同樣用第一層表示，基址下標號除外。差別是所有16個代碼字只需要一個基址下標，因為6位偏移可以覆蓋所有64個指針。總共需要34個字節，再加上給指針的18～128個字節。有65～256個頭時，字節片非常稠密(verydense)。同樣用第一層表示。16個代碼字和4個基址下標總共40個字節。此外，這65～256個指針需要130～512個字節。稠密和非常稠密的字節片都用第一層搜索。用一個專用於8個單元的專用對分搜索來搜索稀疏的字節片。這比線性搜索和通用對分搜索要快得多。另外，實現這一搜索可以不用處理器體系結構上的條件轉移，這一條件轉移指令有一個條件傳送指令。<![CDATA[　　/*係數字節片的搜索函數*/　　staticinlineunit16findsparse(SPARSECHUNK*chu，unit32val)　　/*chu-＞vals是一個排好序的8位指數組0～7　　chu-＞rinfo是指針的對應數組0～7　　val是搜索關鍵字*/　　{　　unit8*p，*q；　　p＝q＝(chu-＞vals)；　　p+＝(*(p+3)＞val)＜＜2；　　p+＝(*(p+1)＞val)＜＜1；　　p+＝(*p＞val)；　　return(chu-＞rinfo[p-q])；　　}]]>如上所述，稠密和非常稠密的字節片都用第一層進行優化。在稀疏字節片中，如果下一跳相同，兩個連續的頭就可以合併，用較小的一個表示。判斷一個字節片是稀疏字節片還是稠密字節片的時候，要將這一合併考慮在內，這樣，當合併的頭數是8或者更少時，這一字節片肯定是稀疏的。為了使這棵樹成為滿二叉樹而添加的許多樹葉將按順序出現，而且它們的下一跳都相同。對應於這些樹葉的頭將合併到係數字節片中去。這一優化過程將字節片分布從較稠密的字節偏移向較稀疏的字節片。對於很大的表，轉發表的大小一般都能縮減5～15％。這種數據結構能夠支持路由條目數顯著增長。當前設計中有兩個極限1.每一層中每一種字節片的個數最多為214，也就是16384。表1說明這比當前採用的要多大約16倍。如果超過這一極限，就可以修改這一數據結構，採用另一種方式對指針編碼從而給下標更多的空間，或者增大指針的尺寸。2.第二層和第三層的指針數受到基址下標大小的限制。當前的實施方案使用16位基址下標，可以支持的增長係數為3～15。如果超過了極限，就將基址指針的大小直接增加到3個字節。此時對於稠密字節片，字節片的尺寸增加3％，對於非常稠密的字節片來說增加10％。稀疏字節片不受影響。顯然路由選擇條目增加很多時這種數據結構仍然可以使用。它的大小將隨著路由條目的個數幾乎線性地增長。為了研究轉發表的性能，收集了許多IP路由選擇表。當前可以從網際網路性能測量和分析(IPMA)計劃站點(http//www.ra.net/statistics/)獲得網際網路路由選擇表，在此以前由現在已經終止了的路由判定器計劃提供(http//www.ra.net/statistics/)。收集的這些路由表是各種大型網際網路互連點使用的路由表的每日快照。這些表的路由條目中有一些有多個下一跳。在這種情況下，轉發表從它們中間隨機地選擇一個作為下一跳使用。圖8中的表1給出的是從多個路由選擇表構成的轉發表裡的數據。對於每一個站點，它給出了產生最大轉發表的路由選擇表的數據和結果。「路由條目」是路由選擇表中路由選擇條目的個數，「下一跳」是從表中找到的不同的下一跳個數。「樹葉」是添加了樹葉使它成為一棵滿二叉樹後前綴樹中的樹葉數。表1中「建立時間」是從路由表二叉樹的存儲器表述生成轉發表所需要的時間。時間是在一臺運行DECOSF1的330MHz阿爾法21164上測得的。隨後的那些列是生成的表中稀疏、稠密和非常稠密字節片的總個數，以及數據結構最低層裡字節片的個數。從表1可以看出，新的轉發表可以很快地生成。在1Hz的再生成頻率下，只佔用了阿爾法容量的不到十分之一。如上所述，比1Hz更高的再生成頻率是不必要的。表1中較大的表無法全部裝入阿爾法的96kB二級高速緩存。但是，可以很靈活地將無法裝進二級高速緩存的那部分裝入三級高速緩存中非常快的SRAM的一小部分中，從而減少二級高速緩存中出現故障的代價。對於局域性的通信量模式，多數存儲器引用都是針對二級高速緩存進行的。一個有趣的現象是這些表的大小可以跟所有前綴都存入一個數組相比。對於這些較大的表，每一個前綴只需要5.6位元組以下。這些字節中有一半以上是由指針佔用的。在Sprint表中，有33469個指針，需要65kB以上的存儲空間。顯然，進一步縮小轉發表的尺寸可以通過減少指針個數來實現。對查找例行程序的測量是用一個C函數進行的，這一C函數是用GNUC-編譯器gcc編譯的(由「使用和一致gnucc.手冊」公開，免費軟體基金會，1995年11月，ISBN1-882114-66-3)。報告的時間不包括函數調用和對下一跳表進行存儲器訪問的時間。gcc產生一個程序，在最壞情況下，它使用大約50條阿爾法指令來搜索數據結構的一層。在一塊高能奔騰晶片上，gcc產生一段程序，最壞的情況下，它每一層使用35～45條指令。下面的C函數給出了測量過程中使用的查找函數的程序。第一層代碼字數組叫做int1，基址下標數組叫做base1。第一層裡的指針儲存在數組htab1中。字節片儲存在數組cis、cid、cidd中，其中的i是層數。稠密和非常稠密字節片的基地址和指針都分別儲存在數組baseid、baseidd和htabid、htabidd中。<![CDATA[　　/*轉發表的查找函數*/　　#include「conf.h」　　#include「forward.h」　　#include「mtentry.h」　　#include「mtable.h」　　#include「bit2index.h」　　#defineTABLE_LOOKUP　　#include「sparse.h」　　#include「timing.h」　　#include「lookup.h」　　/*只有在ip是一個32位的無符號整數(uint32)時這些宏才會工作*/　　#defineEXTRACT(start，bits，ip)(((ip)＜＜(start))＞＞(32-(bits)))　　#defineGETTEN(m)(((m)＜＜22)＞＞22)#defineGETSIX(m)((m)＞＞10)#definebit2o(ix，bit)((mt[(ix)][(bit)＞＞2]＞＞(((bit)0x3)＜＜2))0xf)/*lookup(ipaddr)--ipaddr得到路由表條目的下標*/unsignedintlookup(unit32ipaddr){uint32ix；/*代碼字數組的下標*/uint32code；/*16位代碼字*/int32diff；/*跟TMAX的差*/uint32ten；/*mt的下標*/uint32six；/*六個「額外的」代碼位*/int32nhop；/*指向下一跳的指針*/uint32off；/*指針偏移*/uint32hbase；/*散列表(hashtable)的基址*/uint32pntr；/*散列表條目*/int32kind；/*pntr的種類*/uint32位元組片；/*字節片下標*/uint8*p，*q；/*搜索稀疏字節片的指針*/uint32key；/*搜索稀疏字節片裡的關鍵字*//*從這裡開始計時*/ix＝EXTRACT(0，12，ipaddr)；code＝int1[ix]；ten＝GETTEN(code)；six＝GETSIX(code)；if((diff＝(ten-TMAX))＞＝0){nhop＝(six|(diff＜＜6))；gotoend；}off＝bit2o(ten，EXTRACT(12，4，ipaddr))；hbase＝base1[ix＞＞2]；pntr＝htba1[hbase+six+off]；if((kind＝(pntr0x3))){chunk＝(pntr＞＞2)；if(--kind){if(--kind){　　key＝EXTRACT(16，8，ipaddr)；　　p＝q＝c2s[chunk].vals；　　if(*(p+3)＞key){　　P+＝4；　　}；　　while(*p＞key){　　p++；　　}　　pntr＝c2s[chunk].rinfo[p-g]；　　}else{　　ix＝EXTRACT(16，4，ipaddr)；　　code＝c2dd[chunk][ix]；　　ten＝GETTEN(code)；　　six＝GETSIX(code)；　　if((diff＝(ten-TMAX))＞＝0){　　nhop＝(six|(diff＜＜6))；　　gotoend；　　}　　hbase＝htab2ddbase[(chunk＜＜2)|(ix＞＞2)]；　　off＝bit2o(ten，EXTRACT(20，4，ipaddr))；　　pntr＝htab2dd[hbase+six+off]；}}else{ix＝EXTRACT(16，4，ipaddr)；code＝c2d[chunk][ix]；ten＝GETTEN(code)；six＝GETSIX(code)；　　if((diff＝(ten-TMAX))＞＝0){　　nhop＝(six|(diff＜＜6))；　　gotoend；　　}hbase＝htab2dbase[chunk]；off＝bit2o(ten，EXTRACT(16，4，ipaddr))；　　pntr＝htab2d[hbase+six+off]；}if((kind＝(pntr0x3))){　　chunk＝(pntr＞＞2)；if(--kind){　　if(--kind){　　key＝EXTRACT(24，8，ipaddr)；　　p＝q＝c3s[chunk].vals)；　　if(*(p+3)＞key){　　p+＝4；　　}；　　while(*p＞key){　　p++；　　}；　　pntr＝c3s[chunk].rinfo[p-q]；　　}else{　　ix＝EXTRACT(24，4，ipaddr)；　　code＝c3dd[chunk][ix]；　　ten＝GETTEN(code)；six＝GETSIX(code)；　　if((diff＝(ten-TMAX))＞＝0){　　nhop＝(six|(diff＜＜6)；　　}　　off＝bit2o(ten，EXTRACT(28，4，ipaddr))；　　hbase＝htab3ddbase[(chunk＜＜2)|(ix＞＞2)]；　　pntr＝htab3dd[hbase+six+off]；　　}　　}else{　　ix＝EXTRACT(24，4，ipaddr)；　　code＝c3d[chunk][ix]；　　ten＝GETTEN(code)；　　six＝GETSIX(code)；　　if((diff＝(ten-TMAX))＞＝0){　　nhop＝(six|(diff＜＜6))；　　gotoend；　　}　　off＝bit2o(ten，EXTRACT(28，4，ipaddr))；　　hbase＝htab3dbase[chunk]；　　pntr＝htab3d[hbase+six+off]；　　}　　}　　}　　nhop＝(pntr＞＞2)；　　end；　　/*在這裡停止計時*/　　returnnhop；　　}]]>讀取阿爾法和高能奔騰時鐘周期計數器的當前值是可能的。這一裝置用來高精度地測量查找時間在200MHz時一個時鐘周期是5ns，在333MHz時是3ns。理想情況下，將把整個轉發表裝入高速緩存中，這樣查找時將使用不受幹擾的高速緩存。這將能夠模仿專用轉發引擎高速緩存的性能。但測量只是在普通的通用工作站上完成的，在這種系統裡很難控制高速緩存的內容。無論什麼時候，只要有輸入/輸出、發生中斷或者另一個過程開始運行，高速緩存就會受到幹擾。在不幹擾高速緩存的情況下，甚至無法列印出測量數據，也無法從一個文件中讀出新的IP位址。採用的這一方法對每一查找進行兩次，並測量第二次查找的查找時間。這樣，第一次查找時使用的是受到幹擾的高速緩存，而進行第二次查找時所有必需的數據已經被第一次查找逼進了主高速緩存中。然後將每一對查找測量數據列印出來，取出一個新地址，這一過程又一次幹擾了高速緩存。第二次查找比轉發引擎裡的查找進行得更好，因為數據和指令已經搬入最靠近處理器的主高速緩存。為了得到查找時間的上限，測量時間必需加上對二級高速緩存進行存儲器訪問所需要的額外時間。為了測試轉發表中的所有路徑，針對路由表中的每一個條目，包括為了擴展成一棵滿二叉樹而添加的條目，測量了查找時間。從這些實驗得不到平均查找時間，因為真實通信中訪問每一個路由選擇條目的概率都一樣是不可能的。此外，通信量模式中的局域性將會使數據結構中頻繁訪問的部分保留在主高速緩存中，從而減少平均查找時間。下面計算出來的性能數據是比較保守的，因為其中假定了在主高速緩存裡的所有存儲器訪問都失敗了，而且最壞的情況總是發生。真實的查找速度應當更快。表1說明在數據結構的第三層上很少有字節片。這使得大多數查找都只需要搜索不超過兩層就能找到下一跳。因此，計算了8次而不是最壞的12次存儲器訪問中對二級高速緩存進行存儲器訪問的額外時間。如果大部分查找都要訪問那些很少的字節片，它們就會遷移到主高速緩存中來，所有12次存儲器訪問都不會再那麼費時。在時鐘頻率為333MHz的一臺阿爾法21164上進行了一次實驗；一個時鐘周期有3ns。對8kB數據高速緩存的訪問在2個時鐘周期內完成，對96kB二級高速緩存的訪問則需要8個時鐘周期。見圖9中的表2。圖10給出了從1月1日起在阿爾法計算機上對Sprint路由選擇表進行第二次查找所經歷的時鐘周期的分布情況。觀察到的最快查找速度為17個時鐘周期。這是第一層裡的代碼字直接給出了下一跳表的下標這種情況。這種路由條目非常少。但由於每一個這種路由條目覆蓋了許多IP位址，實際的通信量可能會包含許多這種目的地地址。一些查找用了22個時鐘周期，這肯定跟前一種情況一樣。實驗證明當讀取時鐘周期計數器需要兩條連續指令時，這種差別有時是5個時鐘周期，而不是預期的0個。圖10中下一個尖峰出現在41個時鐘周期處，在這種情況中，在第一層找到的指針就是下一跳表的一個下標。傳統的B類地址就屬於這一類型。52～53、57、62、67和72個時鐘周期處的尖峰對應於在稀疏第二層字節片中檢查了1、2、3、4或者5個值以後才找到指針。75和83個時鐘周期處出現很高的尖峰，分別是因為搜索稠密和非常稠密的字節片需要許多時鐘周期。少部分查找超過83個時鐘周期，這種現象對應於搜索了一個稀疏第三層字節片以後才找到指針，也許是因為執行時間的變化。二級高速緩存中出現的高速緩存衝突，或者在查找之前管線和高速緩存系統的狀態之間的差別，都會導致這種變化。超過100個時鐘周期的那部分分布或者是因為這種變化，或者是因為高速緩存故障。當所有數據都在主高速緩存中時，300ns足以完成一次查找。主高速緩存中的數據訪問跟二級高速緩存中的訪問的差別是8-2＝6個時鐘周期。因此在最壞的情況下搜索數據結構中的兩層需要比圖10所示的多8×6＝48個時鐘周期。也就是說當兩層足夠時，在最壞的情況下，完成查找最多需要100+48＝148個時鐘周期，也就是444ns。這樣，利用二級高速緩存，阿爾法每秒鐘至少能夠完成2200000次路由查找。在時鐘頻率為200MHz的高能奔騰上進行了另一次實驗；一個時鐘周期為5ns。8kB的主高速緩存有2個時鐘周期的等待時間，256kB的二級高速緩存有6個時鐘周期的等待時間。見表2。圖11給出了採用跟阿爾法21164一樣的轉發表時，利用高能奔騰進行第二次查找經歷的時鐘周期的分布情況。讀取時鐘周期計數器的指令序列需要33個時鐘周期。當兩次讀取接連進行時，計數器值的差別是33。因此，所有報告的時間都減去了33。觀察到的最快查找時間是11個時鐘周期，這跟阿爾法21164的速度差不多。這一尖峰對應於第一層出現在25個時鐘周期以後就立即找到下一跳下標這種情形。對應於稀疏第二層字節片的那些尖峰集中在36～40個時鐘周期的範圍內。處理線性掃描時，高能奔騰中不同的高速緩存結構似乎比阿爾法的高速緩存結構要快。如果第二層字節片是稠密的和非常稠密的，完成查找就分別需要48和50個時鐘周期。一直到69個時鐘周期，另外還有一些不規則的尖峰，在69個時鐘周期以上，則很少見到。顯然，當所有數據都在主高速緩存中時，69個時鐘周期(345ns)足以完成查找。訪問主高速緩存和二級高速緩存的時間差是20ns(4個時鐘周期)。於是，需要查找兩層時，最壞情況下高能奔騰的查找時間是69+8×4＝101個時鐘周期，也就是505ns。轉發表在二級高速緩存中時，高能奔騰每秒鐘至少能進行二百萬次路由查找。顯然，本發明提供了一種改進了的IP路由查找方法和系統，它能完全實現前面給出的目標優點。雖然是針對具體的實施方案來介紹本發明的，但對於本領域裡的技術人員來說，顯然可以對以上實施方案進行替換、改進。在上述實施方案裡，查找功能是用C程式語言實現的。對於編程這一領域裡的技術人員來說，顯然可以採用其它的程式語言。或者，可以採用標準的數字設計技術用硬體來實現查找功能，對於硬體設計這一領域裡的技術人員來說，這也是顯而易見的。例如，本發明還可以用於除了阿爾法21164和高能奔騰以外的其它計算機系統結構，可以採用其它的方式來分割前綴樹，樹中可以有不同的層數，可以採用其它的方式來表述變換表，採用其它的方式對代碼字編碼。此外，本發明還可以用於防火牆路由查找。權利要求1.在路由選擇表中查找IP路由的一種方法，包括任意長度前綴的條目，這些條目有下一跳表中有關的下一跳信息，用來確定IP數據報要轉發往什麼地方，其特徵在於以下步驟在存儲裝置裡儲存路由表的一個表達，其形式是一棵完整的前綴樹(7)，由所有路由選擇表條目的前綴定義，這棵樹是完整的，其中每一個節點要麼沒有孩子，要麼有兩個孩子，添加的所有孩子都是樹葉，它們跟最接近的有下一跳信息的祖先一樣有相同的下一跳信息，或者一個未定義的下一跳，如果沒有這樣的祖先存在，在一個存儲裝置裡儲存位矢量(8)的一個表達，在當前深度處(D)，這一位矢量包括前綴樹(7)的一個分割的數據，在這一當前深度處每一個可能的節點都有一位，其中當前綴樹(7)裡有一個節點時，就將這一位置位，在所述存儲裝置中儲存一個指針數組，對於真頭，它們是指向下一跳表的一個下標，對於根頭，它們是下一層字節片的一個下標，將所述位矢量(8)分成特定長度的位掩碼，在所述存儲裝置裡儲存一個轉換表中可能的位掩碼的一個表示，在所述存儲裝置裡儲存一個代碼字數組，每一個代碼字都表示指向轉換表的一個行下標，和一個指針偏移，在所述存儲裝置裡儲存一個基地址數組，訪問代碼字數組中對應於IP位址第一個下標部分(ix)的位置處的代碼字，訪問轉換表中對應於IP位址的一個列下標部分(bit)和代碼字的一個行下標部分(ten)的位置上的轉換表條目部分，訪問基地址數組中IP位址的第二個下標部分(bix)的位置上的基地址，以及訪問對應於代碼字的基地址加指針偏移(six)的位置上的指針加上指針數組裡的轉換表條目部分。2.在路由選擇表裡查找IP路由的一種系統，包括任意長度前綴的條目，這些條目有下一跳表中有關的下一跳信息，用來確定IP數據報要轉發往什麼地方，其特徵在於一個路由選擇表，其形式是一棵完整的前綴樹(7)，由所有路由選擇表條目的前綴定義，每一個節點要麼沒有孩子，要麼有兩個孩子，添加的所有孩子都是樹葉，它們跟最接近的有下一跳信息的祖先一樣有相同的下一跳信息，或者有一個未定義的下一跳，如果沒有這樣的祖先存在，位矢量(8)的一種表達，在當前深度處(D)，這一位矢量包括前綴樹(7)一個分割的數據，在這一當前深度處每一個可能的節點都有一位，其中當前綴樹(7)裡有一個節點時，就將這一位置位，一個指針數組，對於真頭，它是下一跳表的下標，對於根頭，它是下一層字節片的一個下標，將所述位矢量(8)分成特定長度的位掩碼，包括可能的位掩碼一個表示的一個轉換表，一個代碼字數組，每一個代碼字都表示轉換表的一個行下標，和一個指針偏移，以及一個基地址數組。全文摘要從路由選擇表查找IP路由的一種方法,包括有任意長度前綴的條目,這些條目有下一跳表中有關的下一跳信息,以確定IP數據報要發往哪裡,儲存了路由選擇表的一個表示,其形式是一棵完成的前綴樹(7),由所有路由選擇表條目的前綴定義。此外,儲存了在當前深度(D)處位矢量(8)的一個表示,包括前綴樹(7)的一個分割,和一個指針數組,包括到下一跳表和下一層字節片的下標。所述位矢量(8)被分成位掩碼並將位掩碼的一個表示儲存在一個轉換表裡。然後,儲存一個代碼字數組,每一個都表示指向這一轉換表的一個行下標和一個指針偏移,以及一個基地址數組。最後,完成查找。文檔編號H04L12/56GK1270728SQ9880914公開日2000年10月18日申請日期1998年5月11日優先權日1997年9月15日發明者A·布洛德尼克,M·德格馬克,S·卡爾松,S·平克申請人:埃弗內特集團股份有限公司