Bit vector-based high-speed routing lookup apparatus and method

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

Active Publication Date: 2016-09-21
XIDIAN UNIV +1
View PDF4 Cites 8 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
  • Bit vector-based high-speed routing lookup apparatus and method
  • Bit vector-based high-speed routing lookup apparatus and method
  • Bit vector-based high-speed routing lookup apparatus and method

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 present invention discloses a bit vector-based high-speed routing lookup apparatus and method, which mainly solves problems in the existing routing lookup methods that a data structure and a lookup operation are complex, hardware is hard to realize, and lookup speed is low. The apparatus includes a routing table coding module, a routing lookup module and an advanced coder module. The method includes the steps of ranking all routing table items stored in a routing table in a descending manner according to lengths of network prefixes; segmenting the routing table into multiple routing table blocks; converting the routing table blocks into bit vector arrays and storing the bit vector arrays in a memory; reading bit vector ''AND'' by bit in a corresponding sub address in the memory; and finding a routing table item matching with the longest prefix. The method has the advantages that the data structure and the lookup operation are simple, the hardware is easy to realize, and the lookup speed is high.

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 lookup needs to realize the longest prefix matching and wire-speed forwarding of packets. The software lookup method can no longer meet the requirements. Among the various hardware lookup methods, the Ternary Content Addressable Memory (TCAM for short) ) and Trie tree structures are the most popular. Because TCAM i...

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/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