Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2002-10-31
2004-04-06
Sam, Phirin (Department: 2661)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S389000
Reexamination Certificate
active
06717946
ABSTRACT:
FIELD OF THE INVENTION
This invention especially relates to scheduling of packets, processes and/or other entities used in communications, computer systems and/or other systems; and more particularly, the invention relates to mapping ranges of values into unique values of particular use for range matching operations using an associative memory.
BACKGROUND OF THE INVENTION
The communications and computer industries are rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Increasingly, public and private communications networks are being built and expanded using various packet technologies, such as Internet Protocol (IP).
A network device, such as a switch or router, typically receives, processes, and forwards or discards a packet based on one or more criteria, including the type of protocol used by the packet, addresses of the packet (e.g., source, destination, group), and type or quality of service requested. Additionally, one or more security operations are typically performed on each packet. But before these operations can be performed, a packet classification operation must typically be performed on the packet.
Known approaches of packet classification include using custom application-specific integrated circuits (ASICs), custom circuitry, software or firmware controlled processors, binary and ternary content-addressable memories (CAMs). A ternary CAM (TCAM) is a special type of fully associative memory which stores data with three logic values: ‘0’, ‘1’ or ‘*’ (don't care). Each TCAM entry includes a value and a mask. These entries are stored in the TCAM in decreasing order of priority, such as in a decreasing order of the length of prefixes. For a given input, the TCAM compares it against all of the entries in parallel, and returns the entry with the highest priority that matches the input lookup word. An entry matches the input lookup word if the input and the entry value are identical in the bits that are not masked out. A TCAM provides a fast mechanism for performing a longest matching prefix of a particular value, but natively does not provide a mechanism for directly performing operations on ranges.
In performing packet classification, a determination is often made whether a field of a packet matches a range of values. For example, a router may need to filter or only allow packets having a source or destination port number within a particular range of port numbers. Especially when processing packets, this operation typically needs to be performed very efficiently at typically at a line speed rate. Another application that typically relies on range search operations includes coordinating access to computer-readable medium, such a disk or memory. In this exemplary application, the processing of the packet or data may be limited by the rate at which a range operation is performed.
A known implementation uses a TCAM to maintain a range, and a lookup operation is performed on the TCAM with a value provided in a lookup word to identify whether the value matches the range. However, for a field having w bits, this implementation requires (2w−2) TCAM entries. Thus, for a common sixteen bit field (e.g., for storing a port number), up to thirty TCAM entries are required. And if a lookup operation must be performed to determine if both a source port and destination port are matched, then up to thirty times thirty or 900 TCAM entries are required. This implementation is quite expensive and is limiting in the number of ranges that can be maintained in a TCAM. Needed are methods and apparatus for maintaining sets of ranges and for determining whether a value matches a range.
SUMMARY OF THE INVENTION
Methods and apparatus are disclosed for maintaining one or more ranges and identifying whether a value matches one of the ranges and optionally which range is matched. One embodiment includes a range programming engine for generating one or more mapped subtrie values identifying a range, each of the mapped subtrie values identifying a different subset of the range. An associative memory stores the mapped subtrie ranges. A mapping engine receives a particular value and generates a lookup word including a mapped representation of the particular value. The associative memory performs a lookup operation based on the lookup word to identify whether or not the particular value is within one of the stored ranges (or the only stored range). If more than one ranges are stored in the set of associative memory entries on which the lookup operation is performed, then particular range matching the value can be identified by manipulating the lookup result, such as, but not limited to a data structure lookup operation or calculation based on the lookup result, a read operation based on the address of the matching entry in an adjunct memory, etc.
In one embodiment, the mapped representation of the particular value includes a bitmap with a single set bit, the position of the single set bit within the bitmap corresponding to the particular value. In one embodiment, each of the multiple mapped subtrie values includes no bits of value one. In one embodiment, the mapped particular value includes a value bitmap, the value bitmap including a bit transition, the position of the bit transition corresponding to the particular value. In one embodiment, a subset of the multiple mapped subtrie values each include a contiguous set of one or more wildcards, the position of the contiguous set of one or more wildcards identifying values within the range. In one embodiment, the mapped representation of the particular value includes a bitmap with a single set bit, the position of the single set bit within the bitmap corresponding to the particular value. In one embodiment, a subset of the multiple mapped subtrie values each include a contiguous set of one or more ones, the position of the contiguous set of one or more ones identifying values within the range. In one embodiment, the mapped representation of the particular value includes a bitmap with a single set bit, the position of the single set bit within the bitmap corresponding to the particular value. In one embodiment, the associative memory includes multiple associative memory entry cells, each of the multiple associative memory cells including multiple bit comparator cells coupled to an OR gate to generate a hit or miss indication.
REFERENCES:
patent: 5088032 (1992-02-01), Bosack
patent: 5319763 (1994-06-01), Ho et al.
patent: 5481540 (1996-01-01), Huang
patent: 5515370 (1996-05-01), Rau
patent: 5740171 (1998-04-01), Mazzola et al.
patent: 5842040 (1998-11-01), Hughes et al.
patent: 5852569 (1998-12-01), Srinivasan et al.
patent: 5898689 (1999-04-01), Kumar et al.
patent: 5920886 (1999-07-01), Feldmeier
patent: 5930359 (1999-07-01), Kempke et al.
patent: 6000008 (1999-12-01), Simcoe
patent: 6061368 (2000-05-01), Hitzelberger
patent: 6091725 (2000-07-01), Cheriton et al.
patent: 6097724 (2000-08-01), Kartalopoulos
patent: 6141738 (2000-10-01), Munter et al.
patent: 6148364 (2000-11-01), Srinivasan et al.
patent: 6181698 (2001-01-01), Hariguchi
patent: 6219748 (2001-04-01), Srinivasan et al.
patent: 6236658 (2001-05-01), Essbaum et al.
patent: 6237061 (2001-05-01), Srinivasan et al.
patent: 6240485 (2001-05-01), Srinivasan et al.
patent: 6243667 (2001-06-01), Kerr et al.
patent: 6285378 (2001-09-01), Duluk, Jr.
patent: 6289414 (2001-09-01), Feldmeier et al.
patent: 6295576 (2001-09-01), Ogura et al.
patent: 6307855 (2001-10-01), Hariguchi
patent: 6308219 (2001-10-01), Hughes
patent: 6374326 (2002-04-01), Kansal et al.
patent: 6377577 (2002-04-01), Bechtolsheim et al.
patent: 6389506 (2002-05-01), Ross et al.
patent: 6430190 (2002-08-01), Essbaum et al.
Hariguchi Yoichi
Nagaraj Ashwath
Panigrahy Rina
Sharma Samar
Cisco Technology Inc.
Sam Phirin
The Law Office of Kirk D. Williams
LandOfFree
Methods and apparatus for mapping ranges of values into... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for mapping ranges of values into..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for mapping ranges of values into... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3245327