Efficient IP address retrieval using a novel octet based encoding technique for high speed lookup to improve network...

Area of Science:

• Computer Science
• Networking
• Algorithms

Background:

• The increasing popularity of the Internet necessitates faster packet processing in network systems like routers.
• Internet Protocol (IP) lookup, crucial for routing, involves finding the longest prefix match in the Forwarding Information Base (FIB).
• Existing methods like binary tries face challenges in time and space complexity for IP lookups.

Purpose of the Study:

• To propose an efficient deterministic approach for encoding IP prefixes.
• To reduce the storage complexity of IP lookup tables.
• To enhance the performance of IP lookup operations in network systems.

Main Methods:

• Developed a deterministic encoding technique to generate unique indices for IP prefixes.
• Implemented an encoder for efficient prefix representation.
• Focused on reducing both time and space complexity for IP lookups.

Main Results:

• Achieved constant time searches for IP prefixes.
• Improved lookup time by 73% (binary trie), 65% (path-compressed trie), and 66% (multibit trie).
• Realized approximately 63% memory savings compared to existing techniques.

Conclusions:

• The proposed deterministic encoding method offers significant performance improvements for IP lookups.
• This technique effectively reduces memory footprint in network devices.
• The approach enhances overall network system efficiency through faster and more space-efficient IP prefix handling.