ScholarLens Back to search
2017•DEStech Transactions on Computer Science and EngineeringRequires access

A Multi-stage IPv6 Routing Lookup Algorithm Based on Hash Table and Multibit Trie

Xing-ya HE, Yun Tao Yang

Open publisher page 1 citations

Abstract

The address length of IPv6 is 128 and it has no classification addressing, which makes routing lookup processing burden of core router is heavier and the requirements are higher. As many existing algorithms cannot adapt to new requirements after expanding to IPv6, it is necessary to propose a new routing lookup algorithm based on IPv6. After thorough analysis of the IPv6 address prefix distribution regularity, this paper proposes a new scheme based on simple data structure: Hash Table and Multibit Trie (retrieval). This algorithm first classifies the prefix value and then starts its first lookup by using the first 48bits prefix of the IPv6 Address. Simulation results show that in most cases, the algorithm needs only one memory access to find the next hop routing information. This algorithm has high lookup speed and can be easily implemented with hardware.

About this research paper

What this paper is about

The address length of IPv6 is 128 and it has no classification addressing, which makes routing lookup processing burden of core router is heavier and the requirements are higher. As many existing algorithms cannot adapt to new requirements after expanding to IPv6, it is necessary to propose a new routing lookup algorithm based on IPv6. After thorough analysis of the IPv6 address prefix distribution regularity, this paper proposes a new scheme based on simple data structure: Hash Table and Multibit Trie (retrieval). This algorithm first classifies the prefix value and then starts its first lookup by using the first 48bits prefix of the IPv6 Address. Simulation results show that in most cases, the algorithm needs only one memory access to find the next hop routing information. This algorithm has high lookup speed and can be easily implemented with hardware.

Why it matters

OpenAlex reports 1 citations for this work. Citation counts describe recorded attention and do not establish research quality.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

The address length of IPv6 is 128 and it has no classification addressing, which makes routing lookup processing burden of core router is heavier and the requirements are higher. As many existing algorithms cannot adapt to new requirements after expanding to IPv6, it is necessary to propose a new routing lookup algorithm based on IPv6. After thorough analysis of the IPv6 address prefix distribution regularity, this paper proposes a new scheme based on simple data structure: Hash Table and Multibit Trie (retrieval). This algorithm first classifies the prefix value and then starts its first lookup by using the first 48bits prefix of the IPv6 Address. Simulation results show that in most cases, the algorithm needs only one memory access to find the next hop routing information. This algorithm has high lookup speed and can be easily implemented with hardware.

Key concepts: Trie, Computer science, Routing table, IPv6, Prefix, Router, Hash function, Lookup table

Related papers

Related paper 1Related paper 2Related paper 3
Back to paper searchBrowse research topicsOriginal source
A Multi-stage IPv6 Routing Lookup Algorithm Based on Hash Table and Multibit Trie — Research Paper | ScholarLens