Home > Table of Contents


Proceedings of 2009 International Symposium on Computer Science and Computational Technology (ISCSCT 2009)

Huangshan, China, December 26-28, 2009

Editors: Fei Yu, Guangxue Yue, Jian Shu, Yun Liu

AP Catalog Number: AP-PROC-CS-09CN005

ISBN: 978-952-5726-07-7 (Print), 978-952-5726-08-4 (CD-ROM)

Page(s): 418-422

On Memory Management of Tree-bitmap Algorithm for IP Address Lookup

        Yagang Wang, Huimin Du, and Kangping Yang

Full text:  PDF


A Memory Management Unit (MMU) is adopted in the implementation of the Tree-bitmap algorithm for IP address lookup, and its memory allocation policy is vital to the performance of incremental update of Routing Information Base (RIB). Using the RIB database of active routers, a Tree-bitmap based IP address lookup table is constructed, and the memory allocation pattern of the incremental update scheme is analyzed. Based on the analysis, a reference free memory arrangement model is proposed. This model serves as a practical guide for the implementing the MMU for an incremental update version of the Tree-bitmap algorithm. Experimental results show that the proposed model is of good quality and its steady distribution can be applied to most RIBs in today’s routers, and can be used to reduce the amount of memory copying by as much as 85%.

Index Terms

tree bitmap, IP address lookup, memory management, routing information base, incremental update

Copyright @ 2009 ACADEMY PUBLISHER — All rights reserved