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. filter, in which the bit vector of each bloom filter is divided into k partitions; each prefix length is mapped to each partition of the corresponding bloom filter, and the IP prefix information is stored in the hash table; the addressing operation is performed When , W kinds of prefixes are intercepted to the destination address, and the intercepted prefixes are sent to the corresponding Bloom filter, and a matching vector is returned; according to the hash table and the matching vector, the storage space of the destination address is obtained. The invention effectively reduces the calculation amount of Bloom Filter to the original calculation amount, greatly reduces the calculation cost of addressing, improves the addressing efficiency of massive communication subjects, and supports the scalability of Flexible IP under multiple semantics.

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] Since the invention of the Internet, IP addressing has been a central issue of the Internet. With the rapid development of the Internet, more and more emerging application requirements and scenarios continue to emerge, and the current IP address system faces more and more problems. On the one hand, the network is rapidly expanding 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,...

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