Back to search

NJIT

An algorithm for fast route lookup and update

Abstract

dc:description.abstract

Increase in routing table sizes, number of updates, traffic, speed of links and migration to IPv6 have made IP address lookup, based on longest prefix matching, a major bottleneck for high performance routers. Several schemes are evaluated and compared based on complexity analysis and simulation results. A trie based scheme, called Linked List Cascade Addressable Trie (LLCAT) is presented. The strength of LLCAT comes from the fact that it is easy to be implemented in hardware, and also routing table update operations are performed incrementally requiring very few memory operations guaranteed for worst case to satisfy requirements of dynamic routing tables in high speed routers. Application of compression schemes to this algorithm is also considered to improve memory consumption and search time. The algorithm is implemented in C language and simulation results with real-life data is presented along with detailed description of the algorithm.

Degree

thesis:*
Name thesis:degree_name
Master of Science in Computer Engineering - (M.S.)
Discipline thesis:degree_discipline
Electrical and Computer Engineering

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Yilmaz, Pinar Altin
Contributors dc:contributor
  • Necdet Uzun
  • Sirin Tekinay
  • Nirwan Ansari

Subjects

dc:subject × 3

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.njit.edu/theses/772

Chain of custody

source
Harvested from
NJIT
Base URL
digitalcommons.njit.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Yilmaz, Pinar Altin. An algorithm for fast route lookup and update. https://digitalcommons.njit.edu/theses/772