High-speed routing search device and method based on bit vector

A bit vector and routing technology, applied in the field of communication, can solve the problems of complex data structure and search operation, related to routing table prefix distribution, hardware implementation difficulty, etc., to overcome the complex data structure and search operation, and the simple data structure and search operation , the effect of high-performance routing lookup

Active Publication Date: 2019-01-15
XIDIAN UNIV +1
View PDF4 Cites 0 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

[0004] The object of the present invention is to overcome above-mentioned deficiencies in the prior art, provide a kind of high-speed route search device and method based on bit vector with higher search speed, to solve the complex data structure and search operation of the spanning tree method, the difficulty of hardware implementation, and the Problems related to the prefix distribution of the routing table

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
  • High-speed routing search device and method based on bit vector
  • High-speed routing search device and method based on bit vector
  • High-speed routing search device and method based on bit vector

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0033] The present invention will be further described below in conjunction with the accompanying drawings.

[0034] Refer to attached figure 1 , the device of the present invention includes: a routing table encoding module, a routing search module and a priority encoder module, each module is connected by a bus, the output end of the routing table encoding module is connected to the input end of the routing search module, and the output of the routing search module The terminal is connected to the input terminal of the priority encoder module. in:

[0035] The routing table encoding module is used to sort the routing table entries of the routing table in descending order according to the prefix length, divide the sorted routing table into multiple sub-addresses according to the address, and divide it into multiple groups according to the routing table items, and each routing table block contains A sub-address of a group adopts a bit vector coding method to convert each rout...

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 invention discloses a high-speed route search device and method based on bit vectors, which mainly solve the problems of complex data structure and search operation, difficult hardware implementation and low search speed in the existing route search method. The device includes a routing table coding module, a routing lookup module and a priority encoder module. The steps of the method include: sorting all routing table items stored in the routing table in descending order according to the length of the network prefix; dividing the routing table into multiple routing table blocks; converting the routing table block into a bit vector array and storing it in the memory; Read out the bit vector in the corresponding sub-address in bit-wise "AND"; find out the routing table entry that matches the longest prefix. The invention has the advantages of simple data structure and search operation, easy hardware realization and high search speed.

Description

technical field [0001] The invention belongs to the technical field of communication, and further relates to a high-speed route search device and method based on bit vectors in the technical field of communication network. The invention is suitable for high-speed search of network node routing table in communication network. Background technique [0002] With the increasing development and wide application of communication technology, people's requirements for data transmission rate are getting higher and higher. As an important network device, a router is mainly responsible for Internet Protocol (Internet Protocol, IP for short) processing and route lookup. IP search needs to realize the longest prefix matching and wire-speed forwarding of packets. The software search method can no longer meet the requirements. Among the various hardware search methods, the Ternary Content Addressable Memory (TCAM for short) is used. And Trie tree structure is the most popular. Because T...

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/745H04L45/748
CPCH04L45/748
Inventor 潘伟涛刁卓郑凌张之义赵海峰刘春锐邱智亮鲍民权
Owner XIDIAN UNIV
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Try Eureka
PatSnap group products

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

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap