面向虛擬化路由器的多步長特里樹快速重構(gòu)技術(shù)研究.pdf

1、虛擬路由器(Virtual Router)，是指在一個(gè)物理設(shè)備上通過虛擬化技術(shù)實(shí)現(xiàn)多個(gè)邏輯路由器的新型路由設(shè)備。每個(gè)邏輯路由器都具有獨(dú)立的路由表和轉(zhuǎn)發(fā)表，這樣就使不同虛擬網(wǎng)絡(luò)間的地址空間可以重用，并保證了其內(nèi)部路由和轉(zhuǎn)發(fā)的隔離性。虛擬路由器能更充分地利用軟、硬件資源，卻加劇了原本就頻繁的路由更新問題。另一方面，路由查找（或稱IP查找）是路由器轉(zhuǎn)發(fā)、過濾數(shù)據(jù)包的核心功能，其性能的優(yōu)劣直接影響到路由器的整體吞吐率，而頻繁的更新往往會影響查詢

2、的性能。因此，高效的更新機(jī)制，是設(shè)計(jì)高性能虛擬路由器的重中之重。目前的路由的更新方法一般包括線下更新和片上生效兩大部分。而本文主要考慮基于多步長特里樹（Multi-bit Trie）結(jié)構(gòu)的路由表組織及查找方案。因此，加快重構(gòu)過程，降低更新對查找過程的影響是提升更新效率的關(guān)鍵所在。
　　 本文首先提出了一種面向虛擬路由器的多步長特里樹的快速重構(gòu)技術(shù):通過挖掘存儲塊的對應(yīng)規(guī)則，將實(shí)時(shí)更新的單步長特里樹上的信息直接映射到相應(yīng)的多步長特

3、里樹，使得更新過程中不再需要重新讀入數(shù)據(jù)進(jìn)行前綴擴(kuò)展，大大加快了更新速度。實(shí)驗(yàn)結(jié)果表明:對于IPv4和IPv6路由表，本方法分別提高了至少45.2％和23.1％的更新效率。
　　 基于上述方法，本文還提出了一種新的片上更新方式:在構(gòu)建多步長特里樹的過程中，每完成一個(gè)存儲塊，就利用查找的間隙將該存儲塊部署到片上，化整為零的進(jìn)行更新以加快更新生效的過程。實(shí)驗(yàn)結(jié)果表明:對于IPv4和IPv6路由表，本方法分別至少提高了34％和44％的