Method for selecting hash function, and method and device for storing and searching routing table

A hash function and routing table technology, applied in digital transmission systems, data exchange networks, special data processing applications, etc., can solve problems such as wasting memory resources

Active Publication Date: 2010-03-10
HUAWEI TECH CO LTD
View PDF4 Cites 10 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

[0029] Each node needs to apply for a fixed-size storage space, and most of the entries of these nodes do not have lower-level nodes, that is, most of the Ptr entries are empty. figure 1 For example, a total of 29 Ptr entries are empty, which is a waste of memory resources. Most of the time, memory resources are very scarce resources. In practice, there may be hundreds, thousands, or more routing table nodes. More waste of memory resources

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
  • Method for selecting hash function, and method and device for storing and searching routing table
  • Method for selecting hash function, and method and device for storing and searching routing table
  • Method for selecting hash function, and method and device for storing and searching routing table

Examples

Experimental program
Comparison scheme
Effect test

Embodiment 1

[0313] Embodiment 1 of the device for storing the routing table provided by the embodiment of the present invention includes:

[0314] a first match unit for storing the match part of the routing table;

[0315] The first next-level node pointer unit is used to store root node data and first-level node data;

[0316] Wherein, the root node data includes the root node matching item with the next-level node pointer, the root node hash function of the matching item, the next-level node pointer of the root node, and the matching item pointer of the root node. The node hash function is the officially used hash function selected by the method for selecting a hash function as claimed in claim 1; the matching item pointer of the root node points to the matching item part;

[0317] Use the hash function of the root node of the matching item to hash the IP address within the step size range of the first-level node of the matching item, and use the hash result as the offset address in t...

Embodiment 2

[0326] The second embodiment of the device for storing the routing table provided by the embodiment of the present invention includes:

[0327] a second matching item unit for storing the matching item part of the routing table;

[0328] The second next-level node pointer unit is used to store root node data and first-level node data;

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 method for selecting a hash function, and a method and a device for storing and searching a routing table. The method for selecting the hash function comprises the followingsteps: using the current alternative hash function to hash data to be hashed; decoding a hashed result; and accumulating an encoding result until a carry is not generated in the process of the accumulation, and selecting the alternative hash function as a hash function for normal use. The method for storing the routing table comprises the following steps: dividing the routing table into a next-stage node pointer part and a matching item part for storage; and selecting the hash function by using the method provided by the embodiment of the invention to select the hash function. The method for searching the routing table comprises the following steps: taking an IP address to be checked to carry out searching directly according to the directly-stored length of the next-stage node pointer partfor storing the routing table; and reading a matching item code according to a searching result. The method can avoid hash conflict, and effectively reduce the storage resources occupied by the routing table.

Description

technical field [0001] The invention relates to the field of communication technology, in particular to a method for selecting a hash function, a method and a device for storing and searching a routing table. Background technique [0002] In order to complete the routing from one address to another in the Internet network with many users, the relevant data of various transmission paths are usually stored together to form a routing table for query during routing. [0003] Classless Inter-Domain Routing (CIDR) is a commonly used routing table structure. When using the CIDR structure to form a routing table, an Internet Protocol (IP, Internet Protocol) network is represented by a prefix, which is usually represented by the IP address of the IP network and a mask that identifies its effective bits, such as "111*" The IP address is "111", and the effective digits are three digits. It is usually stored in the form of a Multi-Bit Tire, and the integer power of 2 subnets that are a...

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/56H04L1/00
CPCH04L45/54H04L45/00G06F17/30628H04L45/745G06F16/325
Inventor 龚钧詹翀陈洪飞胡睿张健赵鸿翔苏皓王小忠孙团会
Owner HUAWEI TECH CO LTD
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