Flexible IP addressing method and device based on single Hash Bloom filter

Abstract

The invention discloses a Flexible IP addressing method and device based on a single Hash Bloom filter, and the method comprises the steps: dividing the prefixes of all IP addresses in a routing table into N types according to the length, correspondingly setting one Bloom filter for each prefix length, and dividing the bit vector of each Bloom filter into k partitions; mapping each prefix length to each partition of the corresponding Bloom filter, and storing IP prefix information in a hash table; when addressing operation is carried out, W prefixes being taken out from a destination address, the intercepted prefixes being sent into the corresponding Bloom filters, and a matching vector being returned; and addressing according to a hash table and the matching vector to obtain a storage space of the destination address. According to the method, the calculation amount of the Bloom Filter is effectively reduced to the original calculation amount, the addressing calculation cost is greatly reduced, the addressing efficiency of mass communication subjects is improved, and the expandability of Flexible IP under multiple semantics is supported.

Description

technical field [0001] The invention belongs to the field of routing algorithms of computer networks, in particular to a Flexible IP addressing method and device based on a single hash Bloom filter. Background technique [0002] IP addressing has been at the heart of the Internet since its invention. With the rapid development of the Internet, more and more emerging application requirements and scenarios continue to emerge, and the current IP address system is facing more and more problems. On the one hand, the network is rapidly extending towards the Internet of Everything, and the requirements for address length may vary greatly in different scenarios. Since IoT devices are limited by hardware and wireless links, shorter addresses or device IDs are preferable to IPv6 addresses for efficiency. Moreover, the future network needs to connect more communication entities besides traditional hosts, such as services, content, resources, network addresses, people, etc., and there...

AI Technical Summary

Problems solved by technology

Bloom Filter is an efficient hash lookup solution, flexibility and cost-effectiveness are its biggest advantages, but its deployment requires a large number of hash functions, and needs to perform the same amount of memory access, in order to achieve the theory of Bloom Filter Performance, the hash function used must meet the requirements of good randomness and uniformity and be independent of each other, which makes it difficult to find a hash function with excellent performance

And the hash calculation of Bloom Filter needs to consume a lot of CPU clock cycles and cause too much delay, which becomes the bottleneck of system performance

Images