在最近幾年當中，路由器虛擬化的議題已經引起了學界人士很多的關注。路由器虛擬化允許多個虛擬路由器同時運行在一個實體的路由器上。因此，支援虛擬化的路由器要能夠處理來自不同虛擬網路的封包。在合併多個虛擬路由表後，由於不同的虛擬路由表中有共同的條目，所以可以藉此減少記憶體使用量。許多以前的方法是使用基於trie的方法來合併多個虛擬路由表。在此論文中，我們提出了兩種基於範圍的合併方法。我們的資料結構是基於動態多維區段樹（DMST），是一個用B樹實現出來的方法。我們的實驗結果表示，我們所提出的兩種方法在lookup speed和更新能力上優於基於trie的方法，在記憶體使用量上則是有相似的表現。

Recently, research community has drawn lots of attentions in the router virtualization that allows multiple virtual router instances running on the same physical router platform. Thus, the virtualized router should be able to handle packets from different virtual networks. Once the multiple virtual routing tables are merged, memory requirement can be reduced due to the common entries among virtual routing tables. Many previous works use trie-based methods to merge the virtual routing tables. In this thesis, we propose two range-based merging methods. The data structures are based on the dynamic multiway segment tree (DMST) that is implemented with standard B-tree structure. As our experimental results show, the two proposed methods perform much better than the trie-based ones in lookup speed, update performance, scalability, and have similar memory consumption.

[1] Yeim-Kuan Chang, Yung-Chieh Lin, “Dynamic Segment Trees for Ranges and Prefixes,” IEEE Transactions on Computers, vol. 56, no. 6, pp. 769-784, June 2007.
[2] Yeim-Kuan Chang, Yung-Chieh Lin, and Cheng-Chien Su, “Dynamic Multiway Segment Tree for IP Lookups and the Fast Pipelined Search Engine,” IEEE Transactions on Computers, VOL. 59, NO. 4, pp. 492-506, APRIL 2010.
[3] N.M. Chowdhury, Kabir Mosharaf and Raouf Boutaba, “A Survey of Network Virtualization,” The International Journal of Computer and Telecommunications Networking, pp. 862 - 876, 2010.
[4] Jing Fu and Jennifer Rexford, “Efficient IP-address lookup with a shared forwarding table for multiple virtual routers,” in proc. ACM CoNEXT, pp. 1-12, 2008.
[5] Thilan Ganegedara, Weirong Jiang, Viktor K. Prasanna, “FRuG: A Benchmark for Packet Forwarding in Future Networks,” IEEE IPCCC, 2010.
[6] Thilan Ganegedara, Weirong Jiang, Viktor K. Prasanna, “Multiroot: Towards Memory-Efficient Router Virtualization”, IEEE International Conference on Communications (ICC 2011), Kyoto, Japan, June 2011.
[7] H. Le, T. Ganegedara, and V. Prasanna, “Memory-efficient and scalable virtual routers using fpga,” Field Programmable Gate Arrays (FPGA), 2011 International Symposium on, 20.
[8] E. Rosen and Y. Rekhter, “RFC 2547: BGP/MPLS VPNs,” http://www.ietf.org/rfc/rfc2547.txt, 1999.
[9] “Route Views project,” Univ. Oregon, Eugene, OR, 2013 [Online].[http://www.routeviews.org].
[10] RIS RAW DATA [Online]. [http://data.ris.ripe.net].

[11] Haoyu Song, M. Kodialam, Fang Hao, T.V. Lakshman, “Building Scalable Virtual Routers with Trie Braiding,” in proc. IEEE INFOCOM, pp. 1-9, 2010.
[12] Deepak Unnikrishnan and Ramakrishna Vadlamani, Yong Liao and Abhishek Dwaraki Jeremie Crenne, Lixin Gao, Russell Tessier, “Scalable network virtualization using FPGAs”, in proc. ACM/SIGDA FPGA, pp. 219 – 228, 2010.