IP Route Lookup using Compressed Trie

An IP route lookup implementation using the compressed trie (Patricia trie) algorithm. This program efficiently searches for the longest prefix match in a routing table for given IP addresses.

Project Description

This project implements an IP route lookup system designed for network routing applications. The core functionality includes:

• Trie Generation: Builds a binary trie data structure from a Forwarding Information Base (FIB) file
• Trie Compression: Optimizes the trie by removing redundant intermediate nodes, reducing memory footprint and improving lookup speed
• Longest Prefix Match: Performs efficient IP address lookups to find the best matching route
• Performance Metrics: Measures and reports execution time, memory usage, and node access statistics

The compressed trie algorithm provides O(W) lookup time complexity, where W is the address width (32 bits for IPv4), making it significantly faster than linear search for large routing tables.

Installation

1. Clone the repository:

git clone https://github.com/dalouc/compressed-trie-route-lookup.git
cd compressed-trie-route-lookup

2. Compile the project:

make compile

This creates the executable at bin/my_route_lookup.

3. Verify the build:

./bin/my_route_lookup

You should see: Not enough arguments

Execution / Usage

Basic Usage

./bin/my_route_lookup <routing_table_file> <input_file>

Parameters:

Parameter	Description
routing_table_file	Path to the FIB file containing routing prefixes
input_file	Path to the file containing IP addresses to look up

Example

./bin/my_route_lookup data/routing_tables/routing_table.txt data/test_inputs/prueba1.txt

Using Make Targets

Run predefined tests:

make test1    # Run test with prueba1.txt
make test2    # Run test with prueba2.txt
make test3    # Run test with prueba3.txt
make test     # Run all tests

Memory leak detection with Valgrind:

make valgrind1    # Check test 1 for memory leaks
make valgrind2    # Check test 2 for memory leaks
make valgrind3    # Check test 3 for memory leaks

View all available targets:

make help

Input File Formats

Routing Table Format (routing_table.txt):

<IP_ADDRESS>/<PREFIX_LENGTH>	<OUTPUT_INTERFACE>

Example:

192.168.1.0/24	1
10.0.0.0/8	2
0.0.0.0/0	3

Input IP File Format (prueba*.txt):

<IP_ADDRESS>

Example:

192.168.1.100
10.20.30.40
8.8.8.8

Output

The program generates:

1. Console output: Real-time lookup results
2. Output file: <input_file>.out with detailed results

Output format per IP:

<IP_ADDRESS>;<OUTPUT_INTERFACE|MISS>;<NODE_ACCESSES>;<TIME_NS>

Summary statistics include:

• Number of nodes in the compressed trie
• Total packets processed
• Average node accesses per lookup
• Average processing time per packet
• Memory usage (KB)
• CPU time (seconds)

Project Structure

route-lookup-project/
├── src/                                 # Source code files
│   ├── my_route_lookup.c                # Main program logic and trie implementation
│   ├── io.c                             # Input/output operations
│   └── utils.c                          # Utility functions
│
├── include/                             # Header files
│   ├── my_route_lookup.h                # Main program declarations
│   ├── io.h                             # I/O function declarations
│   └── utils.h                          # Utility function declarations
│
├── data/                                # Data files
│   ├── routing_tables/                  # FIB routing table files
│   │   └── routing_table.txt            # Main routing table
│   │   └── routing_table_simple.txt     # Simple routing table
│   └── test_inputs/                     # Test IP address files
│       ├── prueba1.txt                  # Test case 1
│       ├── prueba2.txt                  # Test case 2
│       └── prueba3.txt                  # Test case 3
│
├── bin/                                 # Compiled binaries (generated)
│   └── my_route_lookup                  # Main executable
│
├── reference/                           # Reference implementations
│   └── linear_search                    # Linear search for comparison
│
│
├── Makefile                             # Build configuration
├── .gitignore                           # Git ignore rules
└── README.md                            # This file

Source File Descriptions

File	Description
my_route_lookup.c	Core trie operations: generation, compression, lookup, traversal
io.c	File handling, output formatting, performance measurement
utils.c	Helper functions: netmask generation, hash utilities

Algorithm Overview

Trie Construction

1. Parse each entry from the routing table
2. Insert prefixes bit-by-bit into the trie
3. Store output interface at leaf nodes

Trie Compression

The compression phase removes nodes with a single child that have no associated prefix, merging paths to reduce tree depth and improve lookup efficiency.

Lookup Process

1. Start at the root node
2. For each bit position, traverse left (0) or right (1)
3. Track the most recent matching prefix
4. Return the output interface of the longest prefix match

Notes

Performance Considerations

• The compressed trie significantly outperforms linear search for large routing tables
• Memory usage scales with the number of unique prefixes
• Lookup time is bounded by the maximum prefix length (32 bits for IPv4)

Limitations

• Currently supports IPv4 addresses only
• Routing table must be well-formed (see input format above)

Error Handling

The program handles various error conditions:

Error	Description
Routing table not found	FIB file does not exist
Input file not found	IP address file does not exist
Bad routing table structure	Malformed routing table entry
Bad input file structure	Malformed IP address entry
Memory allocation failed	Insufficient memory
MISS in output	No matching route found for IP

Testing

Ensure all tests pass without memory leaks:

make test           # Functional tests
make valgrind1      # Memory leak check

Authors

Noel Andolz Aguado and Daniel Lozano Uceda