[發(fā)明專利]一種基于閾值的自適應(yīng)路由緩存方法

無效

• 申請?zhí)枺?/td>: 200910162054.7
• 申請日: 2009-08-10
• 公開（公告）號: CN101631085A
• 公開（公告）日: 2010-01-20
• 發(fā)明（設(shè)計(jì)）人: 朱國勝
• 申請（專利權(quán)）人: 武漢烽火網(wǎng)絡(luò)有限責(zé)任公司
• 主分類號: H04L12/56
• 分類號: H04L12/56
• 代理公司: 北京匯澤知識產(chǎn)權(quán)代理有限公司
• 代理人: 黃 挺

技術(shù)領(lǐng)域

本發(fā)明涉及高速互聯(lián)網(wǎng)的IP路由查找技術(shù)，尤其涉及一種基于閾值的自適應(yīng)路由緩存方法。

背景技術(shù)

緩存技術(shù)廣泛應(yīng)用于計(jì)算科學(xué)領(lǐng)域用以提高系統(tǒng)性能，其基本原理是基于內(nèi)容訪問的局部性特征，包括時(shí)間局部性特征和空間局部性特征。所謂時(shí)間局部性是指剛剛訪問的內(nèi)容在很短的時(shí)間內(nèi)很可能被再次訪問；空間局部性是指剛剛訪問的內(nèi)容的存放位置附近的內(nèi)容很可能被再次訪問。CPU高速緩存同時(shí)利用了程序執(zhí)行的時(shí)間局部性特征和數(shù)據(jù)存取的空間局部性特征來提高程序的執(zhí)行效率。例如，WEB緩存就主要利用WEB訪問的時(shí)間局部性特征來提高WEB訪問的響應(yīng)速度。

互聯(lián)網(wǎng)IP分組轉(zhuǎn)發(fā)同樣存在局部性特征。IP分組轉(zhuǎn)發(fā)要根據(jù)報(bào)文的目的IP地址查找路由表，并選擇最長匹配前綴作為匹配結(jié)果，從而得到下一跳IP和出接口信息，然后將報(bào)文從相應(yīng)的接口轉(zhuǎn)發(fā)出去。互聯(lián)網(wǎng)IP分組轉(zhuǎn)發(fā)基于目的地址緩存技術(shù)，其主要利用分組轉(zhuǎn)發(fā)的時(shí)間局部性特征，也就是剛剛查找的目的IP地址在很短的時(shí)間內(nèi)可能會被再次查找，其原因在于一個(gè)連接或者會話過程需要發(fā)送多個(gè)報(bào)文。文獻(xiàn)[B.Talbot，T.Sherwood，and?B.Lin，“IP?caching?forterabit?speed?routers”，Proc.GLOBECOM′99，1999，P1565-1569]提取9臺互聯(lián)網(wǎng)路由器1個(gè)小時(shí)的跟蹤(Trace)數(shù)據(jù)進(jìn)行分析，發(fā)現(xiàn)每個(gè)獨(dú)立IP包含報(bào)文個(gè)數(shù)平均為3696，10％的主機(jī)占據(jù)了90％的流量。其查找過程中，CPU高速緩存需要在Cache中將內(nèi)存地址和內(nèi)存數(shù)據(jù)進(jìn)行關(guān)聯(lián)，基于目的IP地址的路由緩存需要在Cache中將目的IP地址和下一跳信息進(jìn)行關(guān)聯(lián)。文獻(xiàn)[B.Talbot，T.Sherwood，and?B.Lin，“IP?caching?for?terabit?speedrouters”，Proc.GLOBECOM′99，1999，P1565-1569]選取Trace文件目的IP地址比特為1或者為0的概率接近0.5的比特位作為Cache的索引，文獻(xiàn)[劉禎，劉斌，鄭凱，“基于軟件的網(wǎng)絡(luò)處理器的路由高速緩存算法研究”，Vol.18，No.12，December?2007，P3115-3123]中，將比特16和比特24異或的結(jié)果和富于變化的8到15比特進(jìn)行組合作為緩存索引，這樣待查的目的IP可以在Cache中均勻分布了。地址緩存存在的主要問題是比特位的選擇和具體的Trace文件相關(guān)，硬件實(shí)現(xiàn)卻無法適應(yīng)流量環(huán)境的變化。另外，地址緩存的空間局部性特征不明顯，導(dǎo)致緩存空間利用率不高。由于光通信技術(shù)的發(fā)展促使通信鏈路的速率越來越高，100Gbps以太網(wǎng)標(biāo)準(zhǔn)將在2010年發(fā)布，高速分組轉(zhuǎn)發(fā)時(shí)會引起頻繁的緩存置換導(dǎo)致緩存命中率下降，或者為保證緩存命中率需要加大緩存空間。

通過分析發(fā)現(xiàn)，基于目的IP地址的路由緩存只考慮了流量和路由匹配的部分信息，只是將路由查找返回下一跳IP、出接口和待查的目的IP地址進(jìn)行緩存，匹配的路由前綴信息并沒有使用。相比目的IP地址來說，路由表前綴體現(xiàn)出更明顯的局部性特征，反映在時(shí)間局部性方面：一個(gè)前綴會覆蓋多個(gè)IP地址，在很短的時(shí)間內(nèi)，前綴被再次匹配的概率比目的IP地址再次匹配的概率要大。互聯(lián)網(wǎng)知名服務(wù)器大多放置在數(shù)據(jù)中心集中存放，具有不同的IP地址，但是具有相同的前綴；ISP的地址前綴分配具有地域特征，而不同地域的峰值流量特征和時(shí)間密切相關(guān)；反映在空間局部性方面：路由前綴的個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于可能的主機(jī)數(shù)目，目前骨干網(wǎng)路由器路由表接近30萬條，互聯(lián)網(wǎng)主機(jī)數(shù)量超過15.8億，主機(jī)數(shù)量超過路由前綴5000倍以上。采用無類別域間路由(CIDR)的前綴聚合將會減少路由器中存放的路由前綴的個(gè)數(shù)，而基于目的IP地址的緩存無法利用這種路由聚合帶來的好處。