Dynamic virtual routers using multiway segment tree

Yeim Kuan Chang, Zi Yang Ou

Research output: Contribution to journalConference articlepeer-review


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 paper, we propose a range-based merging method. The data structure is based on the dynamic multiway segment tree (DMST) that is implemented with standard B-tree structure. As our experimental results show, faster lookup speed and incremental update can be achieved. The proposed method performs much better than the trie-based ones in lookup speed and scalability, and has similar memory consumption.

Original languageEnglish
Article number6602308
Pages (from-to)171-176
Number of pages6
JournalIEEE International Conference on High Performance Switching and Routing, HPSR
Publication statusPublished - 2013 Dec 9
Event2013 IEEE 14th International Conference on High Performance Switching and Routing, HPSR 2013 - Taipei, Taiwan
Duration: 2013 Jul 82013 Jul 11

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Electrical and Electronic Engineering


Dive into the research topics of 'Dynamic virtual routers using multiway segment tree'. Together they form a unique fingerprint.

Cite this