Address lookup in packet data communications link, using hashing and content-addressable memory
US5414704A · kind A · utility
426Cited by
14References
22Claims
0Family size
Assignee
Inventor
Key dates
| Filing date | Apr 5, 1994 |
| Grant date | May 9, 1995 |
| Priority date | — |
| Expiry date | Apr 5, 2014 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99931
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.