Linked list traversal with reduced memory accesses
AssigneeJuniper Networks, Inc.
InventorsXiangdong Jin, Dongping Luo, Wen Wei
Life of this patent
Estimating the term…
Abstract
A linked list traversal system identifies when a linked list has become inefficient, either through attack or an undue multiplicity of collisions. A data unit is parsed to extract a key. A first hash result associated with the key is calculated based on a first hash function. A first linked list is identified based on the first hash result. It is determined whether the first linked list has been compromised. A second hash result associated with the key is calculated based on a second hash function when the first linked list has been compromised. A second linked list is established based on the second hash result, where the second hash result is different from the first hash result.
Claims17
A system, comprising:
- one or more memory units to store instructions and a number of linked lists of entries relating to a plurality of stored keys;
- a first processor to:
- receive a key,
- access data in a first linked list associated with the received key,
- identify a number of links in the first linked list,
- identify that the first linked list has at least a predetermined number of links, and
- assert a link stop bit associated with the data indicating that the first linked list has been compromised when the identified number of links exceeds a predetermined value, and
- a second processor to:
- receive the key from the first processor when the first processor identifies that the first linked list associated with the received key has at least the predetermined number of links, and
- establish a second linked list based on the received key.
A method, performed by a device, comprising:
- parsing, by a processor of the device, a data unit to extract a key;
- calculating, by the processor, a first hash result associated with the extracted key based on a first hash function;
- identifying, by the processor, a first linked list based on the first hash result;
- determining, by the processor, that the first linked list has been compromised by determining that a total number of links in the first linked list exceeds a predetermined threshold;
- calculating, by the processor, a second hash result associated with the key based on a second hash function when it is determined that the first linked list has been compromised;
- and
- establishing, by the processor, a second linked list based on the second hash result, where the second hash result is different from the first hash result.
A method, performed by a device, comprising:
- storing a first linked list in a memory associated with the device based on a first hash value;
- receiving, at a processor of the device, a data unit having a key that hashes to the first hash value;
- accessing, by the processor, the first linked list to search for the key;
- determining, by the processor, that the first linked list has been potentially compromised by determining that a total number of links in the first linked list exceeds a predetermined threshold;
- and
- generating, by the processor, a second linked list based on a second hash value calculated using the key when it is determined that the first linked list has been potentially compromised.
A system, comprising:
- hardware means for traversing a first linked list to locate data from the first linked list associated with a key,
- where the hardware means:
- identifies a total number of links in the first linked list,
- determines whether a total number of links in the first linked list exceeds a predetermined threshold, and
- asserts a link stop bit indicating that the first linked list has been compromised when the total number of links exceeds the predetermined threshold;
- and
- software means for receiving the key from the hardware means when the hardware means determines that the total number of links in the first linked list exceeds the predetermined threshold,
- where the software means generates a second linked list different from the first linked list.
Dependencies are inferred from the claim text.