NDLI: Range Tries for scalable address lookup

Please wait, while we are loading the content...

CacheCard: caching static and dynamic content on the NIC

Evaluating regular expression matching engines on network and general purpose processors

A NFA-based programmable regular expression match engine

Design and performance analysis of a DRAM-based statistics counter array architecture

Weighted random oblivious routing on torus networks

Divide and discriminate: algorithm for deterministic and fast hash lookups

SPC-FA: synergic parallel compact finite automaton to accelerate multi-string matching with low memory

An ultra high throughput and memory efficient pipeline architecture for multi-match packet classification without TCAMs

Software radio: a broad change in RF communications systems design

Simplifying data path processing in next-generation routers

LaFA: lookahead finite automata for scalable regular expression detection

High throughput architecture for packet classification using FPGA

Motivating future interconnects: a differential measurement analysis of PCI latency

Design of a scalable nanophotonic interconnect for future multicores

Range Tries for scalable address lookup

Memory optimization for packet classification algorithms

Co-match: fast and efficient packet inspection for multiple flows

Networking hardware: what drives innovation?

Exploitation and threat analysis of open mobile devices

An adaptive hash-based multilayer scheduler for L7-filter on a highly threaded hierarchical multi-core server

A block-based reservation architecture for the implementation of large packet buffers

A novel 3D layer-multiplexed on-chip network

Progressive hashing for packet processing using set associative memory

ISP managed peer-to-peer

Experience with high-speed automated application-identification for network-management

Revisiting the internet hourglass: core strength vs. middle-age spread

OASis: towards extensible open-architecture services platforms

Interfacing to a virtualized network infrastructure through network service abstractions

EINIC: an architecture for high bandwidth network I/O on multi-core processors

Implementing URL-based forwarding on a network processor-based router platform

Accelerating OpenFlow switching with network processors

Parallelization of Snort on a multi-core platform

Multiplexing endpoints of HCA to achieve scalability for MPI applications: design, implementation and performance evaluation with uDAPL

Testbed for evaluating worm containment systems

Micro Secure Socket Layer (MSSL) for micro server

External storage middleware for wireless devices with limited resources

A path combinational method for multiple pattern matching

Designing high-speed packet processing tasks at arbitrary levels of abstraction: implementation and evaluation of a MIXMAP system

A lock-free, cache-efficient shared ring buffer for multi-core architectures

SANS: a scalable architecture for network intrusion prevention with stateful frontend

Hash-based routing for scalable datacenters

A novel hybrid SRAM/DRAM memory architecture for fast packet buffers

Theoretic analysis of finite automata for memory-based pattern matching

Binary search on levels using a Bloom filter for IPv6 address lookup

A mobile healthcare system using IMS and the HL7 framework

Range Tries for scalable address lookup

Content Provider	ACM Digital Library
Author	de Smet, Ruben Sourdis, Ioannis Gaydadjiev, Georgi N. Stefanakis, Georgios
Abstract	In this paper we introduce the Range Trie, a new multiway tree data structure for address lookup. Each Range Trie node maps to an address range $[N_{a},$ $N_{b})$ and performs multiple comparisons to determine the subrange an incoming address belongs to. Range Trie improves on the existing Range Trees allowing shorter comparisons than the address width. The maximum comparison length in a Range Trie node is $[log_{2}$ $(N_{b}$ -- $N_{a})]$ bits. Address parts can be shared among multiple concurrent comparisons or even omitted. Addresses can be properly aligned to further reduce the required address bits per comparison. In so doing, Range Tries can store in a single tree node more address bounds to be compared. Given a memory bandwidth, more comparisons are performed in a single step reducing lookup latency, memory accesses per lookup, and overall memory requirements. Latency and memory size scale better than related works as the address width and the number of stored prefixes increase. Considering memory bandwidth of 256-bits per cycle, five to seven Range Trie levels are sufficient to store half a million IPv4 or IPv6 prefixes, while memory size is comparable and in many cases better than linear search. We describe a Range Trie hardware design and evaluate our approach in terms of performance, area cost and power consumption. Range Trie 90-nm ASIC implementations, storing 0.5 million IPv4 and IPv6 prefixes, perform over 500 million lookups per second (OC-3072) and consume 3.9 and 11.4 Watts respectively.
Starting Page	143
Ending Page	152
Page Count	10
File Format	PDF
ISBN	9781605586304
DOI	10.1145/1882486.1882520
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2009-10-19
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Ip lookup Address lookup Internet router
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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