NDLI: Range Trees with variable length comparisons

Content Provider	IEEE Xplore Digital Library
Author	Sourdis, I. de Smet, R. Gaydadjiev, G.N.
Copyright Year	2009
Description	Author affiliation: Computer Engineering, EEMCS, TU Delft, The Netherlands (Sourdis, I.; de Smet, R.; Gaydadjiev, G.N.)
Abstract	In this paper we introduce a new data structure for address lookup, a new tree structure which improves on the existing Range Trees allowing shorter comparisons than the address width. The proposed scheme shares among multiple concurrent comparisons common address prefixes and suffixes and also omits address parts not required for computing a next node branch. In so doing, for a given memory bandwidth, we achieve a larger number of concurrent comparisons than the original Range Tree. This results in less memory accesses and lower latency per lookup. Performance scales better as the address width and the number of address ranges increase. We describe the rules employed to construct the proposed structure and offer two heuristics which generate the “configuration” of the decision tree given a set of address ranges. The proposed Range Tree with variable-length comparisons (RT-VLC) has up to 50% less tree-levels than the original Range Tree and its memory requirements are 50% to 2× that of a linear search approach.
Starting Page	1
Ending Page	6
File Size	12056890
Page Count	6
File Format	PDF
ISBN	9781424451746
DOI	10.1109/HPSR.2009.5307427
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2009-06-22
Publisher Place	France
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Delay Tree data structures Bandwidth Scalability Decision trees Pattern matching Internet Data engineering Concurrent computing Routing Range Tree Address Lookup IP Lookup
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A Heuristic and Hybrid Hash-based approach to fast lookup

Multiway range trees: scalable IP lookup with fast updates

IP address lookup using a dynamic hash function

IP address lookup for internet routers using balanced binary search with prefix vector

NXG06-1: An Efficient IP Address Lookup Algorithm Using a Priority Trie

IP lookup in software for large routing tables using DMP-tree data structure

A parallel multiple hashing architecture for IP address lookup

IP address lookup using GPU

A Fast and Memory Efficient Dynamic IP Lookup Algorithm Based on B-Tree

Range Trees with variable length comparisons

Similar Documents

A Heuristic and Hybrid Hash-based approach to fast lookup

Multiway range trees: scalable IP lookup with fast updates

IP address lookup using a dynamic hash function

IP address lookup for internet routers using balanced binary search with prefix vector

NXG06-1: An Efficient IP Address Lookup Algorithm Using a Priority Trie

IP lookup in software for large routing tables using DMP-tree data structure

A parallel multiple hashing architecture for IP address lookup

IP address lookup using GPU

A Fast and Memory Efficient Dynamic IP Lookup Algorithm Based on B-Tree

Range Trees with variable length comparisons