資源描述：
《一種基于哈希表和Trie樹(shù)的快速內(nèi)容路由查找算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、第２６卷第１０期計(jì)算機(jī)應(yīng)用與軟件Ｖｏｌ２６Ｎｏ．１０２００９年１０月ＣｏｍｐｕｔｅｒＡｐｐｌｉｃａｔｉｏｎｓａｎｄＳｏｆｔｗａｒｅＯｃｔ．２００９一種基于哈希表和Ｔｒｉｅ樹(shù)的快速內(nèi)容路由查找算法汪志莉沈富可（華東師范大學(xué)信息學(xué)院上海２００２４１）摘要內(nèi)容分發(fā)網(wǎng)絡(luò)ＣＤＮ（ＣｏｎｔｅｎｔＤｅｌｉｖｅｒｙＮｅｔｗｏｒｋ）是一個(gè)建立并覆蓋在互聯(lián)網(wǎng)之上的一層特殊網(wǎng)絡(luò)，專門用于通過(guò)互聯(lián)網(wǎng)高效傳遞豐富的多媒體內(nèi)容。與傳統(tǒng)的網(wǎng)絡(luò)一樣，要求核心路由器每秒能轉(zhuǎn)發(fā)幾百萬(wàn)個(gè)以上的分組，而實(shí)現(xiàn)高速分組轉(zhuǎn)發(fā)的關(guān)鍵是路由表的組織和快速的路由查找算法。首先概述了內(nèi)容路由網(wǎng)絡(luò)的背景，羅列出了幾種常見(jiàn)
2、的路由查找算法，并在此基礎(chǔ)上，引入基于Ｈａｓｈ和Ｔｒｉｅ樹(shù)的路由查找算法，最后在試驗(yàn)的基礎(chǔ)上對(duì)平均查找時(shí)間、平均查找次數(shù)以及最大匹配次數(shù)進(jìn)行了比較分析，試驗(yàn)結(jié)論顯示該算法縮短了查找時(shí)間，提高了系統(tǒng)性能。關(guān)鍵詞 ?。茫模危▋?nèi)容分發(fā)網(wǎng)絡(luò)）最長(zhǎng)后綴匹配哈?！。裕颍椋鍢?shù)ＡＦＡＳＴＣＯＮＴＥＮＴＲＯＵＴＩＮＧＬＯＯＫＵＰＡＬＧＯＲＩＴＨＭＯＮＨＡＳＨＡＮＤＴＲＩＥＴＲＥＥＢＡＳＩＳＷａｎｇＺｈｉｌｉ ＳｈｅｎＦｕｋｅ（ＳｃｈｏｏｌｏｆＩｎｆｏｒｍａｔｉｏｎ，ＥａｓｔＣｈｉｎａＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ２００２４１，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ ?。茫铮睿?/p>
3、ｅｎｔＤｅｌｉｖｅｒｙＮｅｔｗｏｒｋ（ＣＤＮ）ｉｓａｌａｙｅｒｏｆｓｐｅｃｉａｌｎｅｔｗｏｒｋ，ｗｈｉｃｈｉｓｂｕｉｌｔａｎｄｃｏｖｅｒｅｄｏｎｔｈｅＩｎｔｅｒｎｅｔａｎｄｄｅｖｏｔｅｓｔｏｄｅｌｉｖｅｒｉｎｇｒｉｃｈｍｕｌｔｉｍｅｄｉａｃｏｎｔｅｎｔｅｆｆｅｃｔｉｖｅｌｙｖｉａｔｈｅＩｎｔｅｒｎｅｔ．Ｌｉｋｅｔｈｅｔｒａｄｉｔｉｏｎａｌｎｅｔｗｏｒｋ，ＣＤＮｒｅｑｕｉｒｅｓｔｈｅｃｏｒｅｒｏｕｔｅｒｔｏｂｅａｂｌｅｔｏｆｏｒｗａｒｄｍｏｒｅｔｈａｎｏｎｅｍｉｌｌｉｏｎｐａｃｋｅｒｓｐｅｒｓｅｃｏｎｄ．Ａｎｄｔｈｅｋｅｙｏｆｆｏｒｗａｒｄｉｎｇｐａｃｋｅｒｓｉｎｈｉ
4、ｇｈｓｐｅｅｄｉｓｔｈｅｏｒｇａｎｉｚａｔｉｏｎｏｆｒｏｕｔｉｎｇｔａｂｌｅｓａｎｄｈｉｇｈｓｐｅｅｄＩＰａｄｄｒｅｓｓｌｏｏｋｕｐａｌｇｏｒｉｔｈｍ．Ｉｎｔｈｉｓｐａｐｅｒ，ｔｈｅｂａｃｋｇｒｏｕｎｄｏｆｔｈｅＣＤＮｗａｓｆｉｒｓｔｌｙｉｎｔｒｏｄｕｃｅｄｔｏｇｅｔｈｅｒｗｉｔｈｅｎｕｍｅｒａｔｉｎｇｓｅｖｅｒａｌｃｏｍｍｏｎｒｏｕｔｉｎｇａｌｇｏｒｉｔｈｍｓ．Ｏｎｔｈｉｓｂａｓｉｓ，ｔｈｅｐａｐｅｒｉｎｔｒｏｄｕｃｅｄａｎｅｗｒｏｕｔｉｎｇｌｏｏｋｕｐａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎＨａｓｈａｎｄＴｒｉｅＴｒｅｅ．Ａｔｌａｓｔ，ｔｈｅａｖｅｒａｇｅｓｅａｒｃｈｔｉ
5、ｍｅ，ａｖｅｒａｇｅｎｕｍｂｅｒｏｆｓｅａｒｃｈａｎｄｔｈｅｌａｒｇｅｓｔｍａｔｃｈｔｉｍｅｗｅｒｅｃｏｍｐａｒａｔｉｖｅｌｙａｎａｌｙｚｅｄｔｈｒｏｕｇｈｔｈｅｅｘｐｅｒｉｍｅｎｔｓ．Ｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｎｔｈａｔｔｈｉｓａｌｇｏｒｉｔｈｍｓｈｏｒｔｅｎｓｔｈｅｓｅａｒｃｈｔｉｍｅａｎｄａｌｓｏｉｍｐｒｏｖｅｓｔｈｅｓｙｓｔｅｍｐｅｒｆｏｒｍａｎｃｅ．Ｋｅｙｗｏｒｄｓ ?。茫模危ǎ茫铮睿簦澹睿簦洌澹欤椋觯澹颍睿澹簦鳎铮颍耄。蹋铮睿纾澹螅簦穑铮螅簦妫椋恚幔簦悖琛。龋幔螅琛。裕颍椋澹簦颍澹寰W(wǎng)站的內(nèi)容發(fā)布到最接近用戶的網(wǎng)絡(luò)０ 引言“邊緣”，
6、使用戶能以最快的速度、從最接近用戶的地方獲得所需的信息，從目前，互聯(lián)網(wǎng)整體帶寬過(guò)剩和局部帶寬不足的矛盾日漸突技術(shù)上全面解決了由于網(wǎng)絡(luò)帶寬小、出，ＣＤＮ技術(shù)的廣泛應(yīng)用為緩解這一矛盾作出了突出的貢獻(xiàn)。用戶訪問(wèn)量大、網(wǎng)點(diǎn)分布不均等對(duì)用其基本思路就是盡可能避開(kāi)互聯(lián)網(wǎng)上有可能影響數(shù)據(jù)傳輸速度戶訪問(wèn)效果的影響，大大提高網(wǎng)絡(luò)的和穩(wěn)定性的瓶頸和環(huán)節(jié)，使內(nèi)容傳輸?shù)酶?、更穩(wěn)。響應(yīng)速度。ＣＤＮ的網(wǎng)絡(luò)層次如圖１圖１?。茫模尉W(wǎng)絡(luò)層次圖本文在深入了解ＣＤＮ的基礎(chǔ)上，著重研究了基于名字的內(nèi)所示。容路由查找算法。名字路由選路的大小取決于互聯(lián)網(wǎng)中內(nèi)容服１．２ 基于名字的ＣＤＮ路由務(wù)器的數(shù)量。當(dāng)內(nèi)容服
7、務(wù)器的數(shù)量很大時(shí)，選路表將變得很龐基于名字的ＣＤＮ路由不同于傳大。路由查找算法的效率將影響名字路由的往返時(shí)間。本文在統(tǒng)的基于ＩＰ地址的路由思想，它是基于用戶需求的內(nèi)容的名字經(jīng)典的Ｈａｓｈ算法的基礎(chǔ)上，引入基于Ｈａｓｈ和Ｔｒｉｅ樹(shù)的查找算（通常是一個(gè)ＵＲＬ）進(jìn)行路由，如圖２所示。法，對(duì)原有的查找算法進(jìn)行了改進(jìn)，將原來(lái)的Ｈａｓｈ表按頂級(jí)域名劃分成多個(gè)Ｈａｓｈ表，大大減少了沖突的次數(shù)，節(jié)約了查找時(shí)間。１ 幾個(gè)重要的概念１．１?。茫模蔚母拍睿茫模问且粋€(gè)經(jīng)策略性部署的整體系統(tǒng)，能夠幫助用戶解決圖２ 基于名字的內(nèi)容路由的用戶訪問(wèn)流程圖分布式存儲(chǔ)、負(fù)載均衡、網(wǎng)絡(luò)請(qǐng)
