Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
1999-07-15
2002-07-02
Pan, Daniel H. (Department: 2183)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C712S023000, C712S024000, C712S245000, C711S216000, C711S169000
Reexamination Certificate
active
06415354
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to pipelined circuits, and more particularly to pipelined methods and apparatus for weight selection and content addressable memory searches.
Content addressable memories (CAMs) can be used in network routers to perform address translation, filtering, and quality of service (QoS) determination. See PCT Publication WO 98/41922, “Accelerated Hierarchical Address Filtering and Translation”, Music Semiconductors, Inc., Sep. 24, 1998. See also A. J. McAuley and P. Francis, “Fast Routing Table Lookup Using CAMs”, Proceedings of the Conference on Computer Communications, IEEE INFOCOM '93, pages 1382-1391. Address translation involves examining a packet destination address or connection identifier to determine the router port or ports on which the packet should be transmitted. Filtering involves examining source or destination addresses, or both, and possibly other information, to determine if the packet should be discarded. Determining the quality of service may involve examination of the source and/or destination addresses, and possibly other information, to determine delay parameters, loss priority, or other service parameters for the packet.
Today's primary application is address translation in network routers. QoS determination, however, is becoming increasingly important in each network element (e.g. each router), and has to be enforced end-to-end across the network. This is driven by the following paradigm shifts in network infrastructure requirements:
1. With the convergence of voice, video, and data onto a common network infrastructure, rigorous QoS guarantees have to be upheld for real-time applications.
2. Through e-commerce and mission-critical applications, high priority delivery has to be guaranteed.
When a packet arrives at a router, the source or destination address or other information in the packet is used to form a key for searching the CAM. If the key matches a CAM entry, the data corresponding to the entry provides the needed information such as the output port on which the packet should be transmitted, or a flag indicating whether or not the packet should be discarded, or a quality of service parameter.
A key can match several entries in the CAM. An entry may have “don't care” bits. For example, an entry may have the form “1101 1001 XX...X”, where X means “don't care”. Another CAM entry may have the form “1101 XXXX XX...X”. If the first eight bits of the key are “1101 1001”, the key will match both entries. Therefore, the best matching entry (the highest priority entry) has to be determined.
In some circuits, the entries' priorities are defined by the order of the entries in the CAM. The entries are ordered in the order of descending priorities. The first matching entry is the best match. A disadvantage of this scheme is that the entries have to be rearranged when an entry is added or deleted. Adding and deleting entries in routers can be a frequent occurrence as routers and communication links are put in and out of service.
Another approach is to allocate a separate block of memory for entries of each priority. Adding and deleting of entries becomes easier. However, memory use is inefficient. If a memory block allocated for some priority gets full, additional entries destined for the block cannot be placed in other blocks even if the other blocks have memory available.
Another solution is to store the priority of each entry explicitly. Only the entries of the highest priority are searched. If no matching entry is found, the entries of the next highest priority are searched, and so on. Disadvantageously, the CAM may have to be searched many times before the best match is determined.
The aforementioned PCT Publication WO 98/41922 describes a technique requiring only two CAM searches. In that technique, each priority has only one bit set (i.e., only one bit has a value 1). When the CAM is searched for the first time, the search is performed among all the entries. The priorities of the matching entries are ORed. The most significant bit of the result of the OR operation defines the highest priority for which a match has occurred. When the CAM is searched for the second time, the search covers only the entries of the highest priority determined from the OR operation.
Improvements on these techniques are desirable.
SUMMARY
According to the present invention, the priority of each CAM entry is stored explicitly, and is indicated by a number that we will call a “weight” of the CAM entry. Selection of the highest priority entry is pipelined. For example, the selection process includes “N” pipeline stages, where N≧2. We will call these pipeline stages “stage 0”, “stage 1”, and so on.
When the CAM has been searched, the pipeline stage
0
selects one or more of the weights based on one or more bits of each weight participating in the selection. Each pipeline stage i (i≧1) selects one or more of the weights from the weights selected at the pipeline stage i-
1
.
In some embodiments, pipeline stage
0
selects weights based on the most significant bit of each weight. Pipeline stage
1
selects weights based on the next most significant bit (e.g., bit “1” if the most significant bit is denoted bit “0”). If the pipeline stage
2
is present, it selects weights based on the next most significant bit (bit
2
), and so on.
Since a pipeline stage performed for one key can overlap with other pipeline stages performed for other keys, high throughput is achievable.
In some embodiments, the CAM can be searched only once, so the CAM searches for different keys can be easily pipelined.
In some network applications the CAM of the present invention provides fixed single clock cycle search throughput, independent of the network loading or traffic characteristics. Some embodiments also provide fixed time single-entry insertion table updates (adding a single entry with its associated weight takes a fixed amount of time) because the entries do not have to be ordered in the CAM. High throughput (e.g. single clock cycle throughput) allows the QoS determination for each incoming packet to be performed before the packet is queued in the network element. Fixed time QoS packet processing before the first queuing point in the network element facilitates guaranteeing QoS levels to the end user.
The invention is not limited to the number of weight bits examined at each pipeline stage, the number of CAM searches per key, or even to CAM searches. For example, the pipelined weight selection techniques of the invention are used to arbitrate access to a shared resource. Each entity sharing the resource has a priority defined based on a corresponding weight. Pipelined weight selection is performed to select the highest priority entities requesting access to the resource.
Other features and advantages of the invention are described below. The invention is defined by the appended claims.
REFERENCES:
patent: 5414704 (1995-05-01), Spinney
patent: 5771010 (1998-06-01), Masenas
patent: 5842025 (1998-11-01), Joffe
patent: 5999435 (1999-12-01), Henderson
patent: WO 98/41922 (1998-09-01), None
Anthony J. McAuley et al., Fast Routing Table Lookup Using CAMs, IEEE INFOCOM '93, Conference on Computer Communications (1993), Proceedings, vol. 3, pp. 1382-1391.
S. Deering et al., Internet Protocol, Version 6 (IPv6) Specification, Network Working Group, (http://www.ietf.cnri.reston.va.us/rfc/rfc1883.txt), May 28, 1999, pp. 1-33.
Willibald Doeringer et al., Routing on Longest-Matching Prefixes, IEEE/ACM Transactions on Networking, vol. 4, No. 1, Feb. 1996, pp. 86-97.
Stefan Nilsson et al., Fast Address Lookup for Internet Routers, Broadband Communications, Fourth International Conference on Broadband Communications, 1998, pp. 11-22.
V. Srinivasan et al., Fast and Scalable Layer Four Switching, Computer Communication Review, ACM SIGCOMM '98 Proceedings, Oct. 1998, vol. 28, No. 4, pp. 191-202.
John McQuillan, Routers and Switches Converge, Data Communications, Oct. 21, 1997, pp. 120-124.
T.V. Lakshman et al., High-Speed Policy-
Joffe Alexander
Milner Simon H.
Uzrad-Nali Oran
Applied Micro Circuits Corporation
Pan Daniel H.
Shenker Michael
LandOfFree
Pipelined methods and apparatus for weight selection and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Pipelined methods and apparatus for weight selection and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pipelined methods and apparatus for weight selection and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2826236