Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

IP route search method and device

A technology of IP routing and routing, applied in digital transmission systems, electrical components, transmission systems, etc., can solve the problem of large routing table entries, and achieve the effect of simplifying the search process and improving search efficiency

Active Publication Date: 2017-01-11
NEW H3C TECH CO LTD
View PDF2 Cites 2 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

[0010] In addition, because the network device needs to support multiple VPN instances, each VPN instance needs to maintain an independent routing table. When the network device supports more VPN instances, the overall routing table entries of the network device will be very large.

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • IP route search method and device
  • IP route search method and device
  • IP route search method and device

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0039] Tree Bitmap (tree bitmap) is a classic routing lookup algorithm based on Multibit Trie (multibit dictionary tree), which is applied to CRS series high-end routers. In order to gain an in-depth understanding of Tree Bitmap, first introduce Unibit Trie (unit dictionary tree) and Multibit Trie.

[0040] image 3 An example diagram for Unibit Trie, such as image 3 As shown, there are 9 IPv4 prefixes P1-P9 distributed. Among them, the highest prefix node P1 of the Unibit Trie represents the prefix *, after that, the prefix Q1 represented by the left branch of the lower level of P1 is 0*, the prefix P2 represented by the right branch of the lower level of P1 is 1*, and the lower level of Q1 The prefix P3 represented by the left branch of the first level is 00*, the prefix Q2 represented by the left branch of the next level of P2 is 01*, the prefix Q3 represented by the right branch of the next level of P2 is 11*, and so on; That is to say, for any node P in the Unibit Tri...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

Abstract

The present invention proposes an IP route search method and device. The method includes the following steps that: a Multibit Trie tree is constructed for the distribution of IP prefixes in each VPN; routes on high 1-to-m-level IP prefixes of the Multibit Trie tree are expanded onto (m+1)-level IP prefixes through adopting a prefix expansion method, wherein m is an integer larger than 1; each branch of the (m+1)-level IP prefixes of the Multibit Trie tree is adopted as one Branch_Tree, and the data structure information of each Branch_Tree is stored; and when route search is carried out for one IP address in one VPN, a corresponding Branch_Tree is searched out in a Multibit Trie tree corresponding to the VPN according to the high m+1 bit of the IP address, and a corresponding route is searched out in the Branch_Tree. With the IP route search method and device adopted, IP route search efficiency can be improved.

Description

technical field [0001] The present application relates to the technical field of routing lookup, in particular to an IP routing lookup method and device. Background technique [0002] Communication between networks requires data transmission and forwarding, so one of the main functions of network equipment is to perform efficient data forwarding, and its function in the basic data plane of the Internet protocol is routing lookup, that is, according to the routing table. Prefix information, for each incoming data packet determines its next hop and outgoing port. Due to the wildcards in the routing table and the LPM (Longest Prefix Matching, longest prefix matching) problem of CIDR (Classless Inter-Domain Routing, based on Classless Inter-Domain Routing), routing lookup becomes very complicated. In addition to high performance, the LPM-based routing lookup algorithm also needs to meet the following requirements: [0003] 1. IPv4 and IPv6 dual stack [0004] Most existing al...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
Patent Type & Authority Applications(China)
IPC IPC(8): H04L12/745H04L12/741H04L45/748H04L45/74H04L45/741
CPCH04L45/745H04L45/748H04L45/48H04L45/74H04L45/741H04L63/0272
Inventor 任凯葛长忠安绍亮
Owner NEW H3C TECH CO LTD
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic, Popular Technical Reports.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap|About US| Contact US: help@patsnap.com