40 results about "Cuckoo hashing" patented technology

Methods and apparatus to support multiple-writer/multiple-reader concurrency for software flow/packet classification on general purpose multi-core systems. A flow table with rows mapped to respective hash buckets with multiple entry slots is implemented in memory of a host platform with multiple cores, with each bucket being associated with a version counter. Multiple writer and reader threads are run on the cores, with writers providing updates to the flow table data. In connection with inserting new key data, a determination is made to which buckets will be changed, and access rights to those buckets are acquired prior to making any changes. For example, under a flow table employing cuckoo hashing, access rights are acquired to buckets along a full cuckoo path. Once the access rights are obtained, a writer is enabled to update data in the applicable buckets to effect entry of the new key data, while other writer threads are prevented from changing any of these buckets, but may concurrently insert or modify key data in other buckets.

The invention relates to the technical field of security, and discloses an intersection calculation method for private data, which is applied to a client and comprises the following steps: receiving a data filter sent by a server, filtering client data by using the data filter to obtain client filtered data, performing cuckoo hash processing on the client filtered data, constructing a client hash table according to the obtained hash value, performing casual transmission with the server by using the client hash table to obtain a client comparison sequence, calculating intersection data of the client comparison sequence and a server encrypted sequence sent by the server, and taking all the intersection data as a privacy intersection. The invention further provides a private data intersection calculation device, electronic equipment and a computer readable storage medium. According to the invention, the problem of low efficiency of data intersection calculation can be solved.

The invention provides an OpenFlow flow table energy-saving storage architecture supporting QoS (Quality of Service) and application of the OpenFlow flow table energy-saving storage architecture. Thearchitecture comprises three layers, namely a priority flow/elephant flow layer, a mouse flow layer and an active connection cache layer, wherein the priority flow/elephant flow layer adopts a TCAM and a DRAM as storage media, the mouse flow layer adopts an SRAM and a DRAM as storage media, the active connection cache layer adopts an SRAM as a storage medium, and a Cuckoo hash structure is adoptedto cache a mapping relationship between active connection and flow table entries in the TCAM. According to the architecture, the TCAM is adopted to preferentially store the identification fields of the priority flow table entries, and quick flow table lookup of priority data packets is realized, so that the network service quality is guaranteed. Meanwhile, a Cuckoo cache is designed to dynamically store the current active connection and the corresponding TCAM flow entry index value in the elephant flow; the cache is hit by most of the data packets, and the corresponding flow table item is found according to the address of the hit cache item, so that a TCAM flow table lookup process is bypassed, and the flow table lookup energy consumption overhead is greatly reduced.

The invention relates to a data packet forwarding method based on software table look-up. The method is based on Intel DPDK, and adopts hardware to extract a data packet header, rapid data transmission software to transmit data in batch efficiently, and software to look up table flexibly so as to realize a data packet forwarding function of a switch. A table look-up algorithm realizes the effects of storing enough items and improving table look-up speed by combining a cuckoo hash table and an open addressing method. Network equipment is allowed to have the following characteristics of multiport wire-speed forwarding, flexible high-capacity table look-up and low cost. The method combines the high-speed packet forming capability of the hardware, the mass data packet processing and forwarding capability of the rapid data transmission software and the high-speed flexible look-up capability of the software; compared with the conventional hardware switch, the method has better extendibility and programmability; and compared with a conventional software switch, the method can provide larger throughput rate and smaller time delay.

The invention provides an elastic Key-Value pair data storage method based on RDMA (Remote Direct Memory Access) and HTM (High Temperature Modulation). A server-client architecture mode is designed and followed, and the method comprises the steps that at a server side, an improved G-Cuckoo Hash data management mode is given in combination with a Hashmap; the kick-out infinite loop between Hash tables caused by searching for idle positions in the data insertion process is avoided. the bottleneck problem of key value pair storage performance caused by round response required by the traditional network message transmission between the client and the server is analyzed; an Infiniband remote direct memory access RDMA technology is used, an RDMA network communication engine is designed, a data access request is received, and a data request result is sent back; a hardware transaction memory HTM technology is utilized to realize a two-section lock protocol lock operation and ensure the atomiccharacteristics of data operation; and a key value is used for self-verifying the check code of the data to guarantee data consistency. The basic operation speed of the key value on the data can be greatly improved.

The invention discloses a private data hiding and sharing method. The method comprises the following steps: an initiator distributes each data in an ID data set A to a storage position in a corresponding Hash bucket for storage by adopting a cuckoo Hash algorithm, and a participant distributes each data in an ID data set B to a storage position in a corresponding Hash bucket for storage by adopting a simple Hash algorithm; the initiator and the participant cooperatively use a secret sharing algorithm to compare data stored in each hash bucket of the cuckoo hash with all data stored in the hash bucket with the same serial number of the simple hash, and the initiator and the participant obtain comparison results respectively; the initiator calculates a shared value fragment G1 corresponding to each hash bucket, and the participant calculates a shared value fragment G2 corresponding to each hash bucket; according to the invention, the participant can share one part of the feature data corresponding to the intersection ID data of the initiator to the initiator, and the ID data of both parties are not leaked, so that the privacy and security of private data of both parties are protected.

The invention discloses a QoS (Quality of Service)-aware OpenFlow flow table hierarchical storage architecture and application, and the architecture provided by the invention stores a high-priority flow in a TCAM (Ternary Content Addressable Memory), so that the grouping search performance of the high-priority flow is ensured; a Cuckoo hash structure is adopted to design an accurate flow cache mechanism and store low-priority and non-priority active accurate flows, so that data packets in the accurate flows directly hit caches, corresponding SRAM flow table entries are quickly found, the average flow table search time is remarkably shortened, and the performance of the OpenFlow switch is improved. According to the method, corresponding flow table searching speeds are provided for network flows with different priorities, wherein network packets in a high-priority flow directly hit a TCAM flow table, and corresponding flow table entries are quickly found; a hit Cuckoo cache is searched by a network packet in the low-priority flows, and a corresponding SRAM flow table entry is directly positioned; most of the groups in the priority-free flows can directly hit the Cuckoo cache, and a tuple space search method needs to be further adopted for searching the SRAM flow table for a small part of the groups, and therefore the overall searching efficiency is high.

The invention discloses a label cuckoo filter which comprises a cuckoo hash table, the cuckoo hash table comprises a plurality of storage buckets, each data member corresponds to two label fingerprints, and the two label fingerprints are respectively stored in the two storage buckets; and when the tag cuckoo filter receives a data member management operation, determining two candidate storage buckets and two tag fingerprints corresponding to a preset data member based on the exclusive-OR operation, and executing the data member management operation based on the two candidate storage buckets and the two tag fingerprints obtained through determination. According to the method, two label fingerprints and two storage buckets are configured for each data member, the candidate storage buckets corresponding to the data members are determined by adopting the exclusive-OR operation based on the label fingerprints, and the number of the storage buckets is not required to be the power of 2, so that the storage space overhead of each data member is reduced.

The invention relates to a method for efficiently and quickly solving hash conflicts. The invention relates to a method for efficiently and quickly solving hash conflicts, which realizes a hybrid hashtable searching method by combining a cuckoo hash idea with a chain address method algorithm and introducing an LRU algorithm for optimization, can optimize hash table construction and searching efficiency, and meanwhile, improves the utilization rate of hash tables. And the indexing process of the hash addressing key can be greatly accelerated.

The embodiment of the invention provides a method for determining the same service data of multiple service parties based on privacy protection. Four hash tables are respectively set in each service party according to the same rule; the cuckoo hash and the hash value storage position coincidence principle of the same service data are adopted, so that the data comparison frequency between every twoservice parties is greatly reduced, for example, the data comparison frequency is reduced to the product of 8 (the number of sub-tables) and the number of service data owned by a service party with more service data; and on the other hand, an equality comparison mode based on secret sharing is adopted to carry out two-party data comparison at a corresponding position, and a method of randomly extracting a part of bits for comparison is adopted in the data comparison process, so that the calculation amount in the security comparison process is reduced, and the comparison efficiency is improved. In a word, the technical concept of the specification can improve the efficiency of determining the same service data of a plurality of service parties on the basis of privacy protection.

The invention relates to an efficient dynamic set management method and system, a dynamic set is provided with a plurality of data blocks, each data block is provided with a plurality of data buckets, each data bucket is provided with a plurality of data slots, and the data slots are used for storing fingerprint information of elements. Obtaining a to-be-inserted element and fingerprint information thereof; obtaining a first hash function, and obtaining insertion candidate data blocks according to the first hash function, the offset and the total number of the data blocks; determining insertion candidate data buckets from the insertion candidate data blocks by adopting a cuckoo Hash algorithm according to the to-be-inserted elements and the fingerprint information of the to-be-inserted elements; obtaining a second hash function, and obtaining insertion candidate data slots according to the second hash function, the offset and the number of the data buckets in each data block; and inserting the element to be inserted into the candidate data slot. According to the technical scheme, the space efficiency of the dynamic set can be improved, and the false positive probability is reduced.

The invention discloses a data processing method in multi-party privacy intersection, which is applied to a receiver device. M keywords of the receiver device are mapped to a hash table with the size of L by adopting cuckoo hash. The method comprises the following steps: receiving L groups of calculation data sent by a sender device for the m keywords; using m groups of calculation data in the L groups of calculation data to respectively correspond to each keyword in the hash table, and calculating an OPPRF result corresponding to the keyword; for each OPPRF result in the m OPPRF results, taking the serial number of the keyword corresponding to the OPPRF result as a packet header, and combining the packet header with the OPPRF result to form a processed result; sorting the obtained m processed results according to packet headers, and storing the m processed results in a result file according to a sequence; and sequentially obtaining each processed result from the result file according to a sequence, and carrying out data fusion on the OPPRF result contained in the processed result and the corresponding local pseudo-random number. By adopting the scheme, the multi-party privacy intersection efficiency is improved.