Address lookup in packet data communications link, using hashing and content-addressable memory
AssigneeDigital Equipment Corporation
InventorBarry A. Spinney
Life of this patent
Estimating the term…
Abstract
A way of doing source address and destination address lookups is described, as may be used in a packet data communication system. A way of searching a relatively large database is described, using a combination of programmable hash algorithms, binary search algorithms, and a small content-addressable memory (CAM). The technique is efficient in space, time and cost, compared to prior methods. For example, prior methods using conventional binary reads may have used thirteen reads, whereas this technique requires on average two reads, with a worst case of four reads.
Claims22
A method of performing an address lookup for an N-bit input address in a data communication system, comprising the steps of
- hashing said N-bit input address by a known hash function to produce an N-bit input hashed address;
- indexing into a hash table to select a hash bucket using an index part of said hashed address, the hash bucket containing a pointer and a size value;
- indexing into a translation table to select a binary tree of records at a location identified by said pointer, the selected binary tree having a size specified by said size value;
- and
- searching said records of said selected binary tree to obtain a stored hashed address from each one of said records, including
- comparing said stored hashed address from each one of said records with a remainder part of said input hashed address, and when a one of said records with a matching remainder part is found, retrieving a stored address from said one of said records with a matching remainder part.
Apparatus for performing an address lookup for an N-bit input address in a data communication system, comprising:
- means for hashing said N-bit input address by a known hash function to produce an N-bit input hashed address;
- a hash table, and means for indexing into said hash table to select a hash bucket using an index part of said hashed address, the hash bucket containing a pointer and a size value;
- a translation table, and means for indexing into said translation table to select a binary tree of records at a location identified by said pointer, the selected binary tree having a size specified by said size value;
- means for searching said records of said selected binary tree to obtain a stored hashed address from each one of said records, including
- means for comparing said stored hashed address from each one of said records with a remainder part of said input hashed address, and when a one of said records with a matching remainder part is found, retrieving a stored address from said one of said records with a matching remainder part.
Dependencies are inferred from the claim text.