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

IP routing lookup method and device

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

Active Publication Date: 2019-09-17
NEW H3C TECH CO LTD
View PDF2 Cites 0 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 routing lookup method and device
  • IP routing lookup method and device
  • IP routing lookup 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

This application proposes an IP route lookup method and device. The method includes: constructing a Multibit Trie for the route distribution of IP prefixes in each VPN; using the method of prefix expansion to extend the routes on the IP prefixes of the Multibit Trie higher than 1~m to the m+1 IP prefixes , m is an integer greater than 1; each branch of the m+1 level IP prefix of the Multibit Trie is used as a Branch_Tree, and the data structure information of each Branch_Tree is preserved; when a routing search is performed to an IP address in a VPN According to the upper m+1 bits of the IP address, the corresponding Branch_Tree is found in the Multibit Trie corresponding to the VPN, and the corresponding route is found in the Branch_Tree. The application improves the efficiency of IP routing lookup.

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 (LongestPrefix Matching, longest prefix matching) problem of CIDR (Classless Inter-Domain Routing, based on Classless Inter-Domain Routing), routing search 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 alg...

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 Patents(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