Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-06-30
2004-08-03
Ngo, Ricky (Department: 2662)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S412000, C370S252000, C370S352000, C709S223000, C711S119000
Reexamination Certificate
active
06771646
ABSTRACT:
BACKGROUND
There has long been a need for network activity monitors. This need has become especially acute, however, given the recent popularity of the Internet and other interconnected networks. In particular, there is a need for a real-time network monitor that can provide details as to the application programs being used. Such a monitor should enable non-intrusive, remote detection, characterization, analysis, and capture of all information passing through any point on the network (i.e., of all packets and packet streams passing through any location in the network). Not only should all the packets be detected and analyzed, but for each of these packets the network monitor should determine the protocol (e.g., http, ftp, H.323, VPN, etc.), the application/use within the protocol (e.g., voice, video, data, real-time data, etc.), and an end user's pattern of use within each application or the application context (e.g., options selected, service delivered, duration, time of day, data requested, etc.). Also, the network monitor should not be reliant upon server resident information such as log files. Rather, it should allow a user such as a network administrator or an Internet service provider (ISP) the means to measure and analyze network activity objectively; to customize the type of data that is collected and analyzed; to undertake real time analysis; and to receive timely notification of network problems.
Related and incorporated by reference U.S. Pat. No. 6,51,099 for METHOD AND APPARATUS FOR MONITORING TRAFFIC IN A NETWORK, to inventors Dietz, et al, describes a network monitor that includes carrying out protocol specific operations on individual packets including extracting information from header fields in the packet to use for building a signature for identifying the conversational flow of the packet and for recognizing future packets as belonging to a previously encountered flow. A parser subsystem includes a parser for recognizing different patterns in the packet that identify the protocols used. For each protocol recognized, a slicer extracts important packet elements from the packet. These form a signature (i.e., key) for the packet. The slicer also preferably generates a hash for rapidly identifying a flow that may have this signature from a database of known flows.
The flow signature of the packet, the hash and at least some of the payload are passed to an analyzer subsystem. In a hardware embodiment, the analyzer subsystem includes a unified flow key buffer (UFKB) for receiving parts of packets from the parser subsystem and for storing signatures in process, a lookup/update engine (LUE) to lookup a database of flow records for previously encountered conversational flows to determine whether a signature is from an existing flow, a state processor (SP) for performing state processing, a flow insertion and deletion engine (FIDE) for inserting new flows into the database of flows, a memory for storing the database of flows, and a cache for speeding up access to the memory containing the flow database. The LUE, SP, and FIDE are all coupled to the UFKB, and to the cache.
Each flow-entry includes one or more statistical measures, e.g., the packet count related to the flow, the time of arrival of a packet, the time differential.
In the preferred hardware embodiment, each of the LUE, state processor, and FIDE operate independently from the other two engines. The state processor performs one or more operations specific to the state of the flow.
Because of the high speed that packets may be entering the system, it is desirable to maximize the hit rate in a cache system. Typical prior-art cache systems are used to expediting memory accesses to and from microprocessor systems. Various mechanisms are available in such prior art systems to predict the lookup such that the hit rate can be maximized. Prior art caches, for example, can use a lookahead mechanism to predict both instruction cache lookups and data cache lookups. Such lookahead mechanisms are not available for a cache subsystem for the packet monitoring application. When a new packet enters the monitor, the next cache access, for example from the lookup engine, may be for a totally different conversational flow than the last cache lookup, and there is no way ahead of time of knowing what flow the next packet will belong to.
Thus there is a need in the art for a cache subsystem suitable for use in a packet monitor. One desirable property of such a cache system is a least recently used (LRU) replacement policy that replaces the LRU flow-entry when a cache replacement is needed. Replacing least recently used flow-entries is preferred because it is likely that a packet following a recent packet will belong to the same flow. Thus, the signature of a new packet will likely match a recently used flow record. Conversely, it is not highly likely that a packet associated with the least recently used flow-entry will soon arrive.
A hash is often used to facilitate lookups. Such a hash may spread entries randomly in a database. In such a case, a associative cache is desirable.
There thus is a need for a associative cache subsystem that also includes a LRU replacement policy.
SUMMARY
Described herein is an associative cache system for looking up one or more elements of an external memory. The cache system comprises a set of cache memory elements coupled to the external memory, a set of content addressable memory cells (CAMs) containing an address and a pointer to one of the cache memory elements, and including a matching circuit having an input such that the CAM asserts a match output when the input is the same as the address in the CAM cell. The cache memory element which a particular CAM points to changes over time. In the preferred implementation, the CAMs are connected in an order from top to bottom, and the bottom CAM points to the least recently used cache memory element.
REFERENCES:
patent: 3949369 (1976-04-01), Churchill, Jr.
patent: 4458310 (1984-07-01), Chang
patent: 4559618 (1985-12-01), Houseman et al.
patent: 4736320 (1988-04-01), Bristol
patent: 4891639 (1990-01-01), Nakamura
patent: 4910668 (1990-03-01), Okamoto et al.
patent: 4972453 (1990-11-01), Daniel, III et al.
patent: 5101402 (1992-03-01), Chiu et al.
patent: 5247517 (1993-09-01), Ross et al.
patent: 5247693 (1993-09-01), Bristol
patent: 5315580 (1994-05-01), Phaal
patent: 5339268 (1994-08-01), Machida
patent: 5351243 (1994-09-01), Kalkunte et al.
patent: 5365514 (1994-11-01), Hershey et al.
patent: 5375070 (1994-12-01), Hershey et al.
patent: 5394394 (1995-02-01), Crowther et al.
patent: 5414650 (1995-05-01), Hekhuis
patent: 5414704 (1995-05-01), Spinney
patent: 5430709 (1995-07-01), Galloway
patent: 5432776 (1995-07-01), Harper
patent: 5493689 (1996-02-01), Waclawsky et al.
patent: 5500855 (1996-03-01), Hershey et al.
patent: 5511215 (1996-04-01), Terasaka et al.
patent: 5530834 (1996-06-01), Colloff et al.
patent: 5530958 (1996-06-01), Agarwal et al.
patent: 5535338 (1996-07-01), Krause et al.
patent: 5568471 (1996-10-01), Hershey et al.
patent: 5574875 (1996-11-01), Stansfield et al.
patent: 5586266 (1996-12-01), Hershey et al.
patent: 5606668 (1997-02-01), Shwed
patent: 5608662 (1997-03-01), Large et al.
patent: 5634009 (1997-05-01), Iddon et al.
patent: 5651002 (1997-07-01), Van Seters et al.
patent: 5684954 (1997-11-01), Kaiserswerth et al.
patent: 5703877 (1997-12-01), Nuber et al.
patent: 5720032 (1998-02-01), Picazo, Jr. et al.
patent: 5732213 (1998-03-01), Gessel et al.
patent: 5740355 (1998-04-01), Watanabe et al.
patent: 5749087 (1998-05-01), Hoover et al.
patent: 5761424 (1998-06-01), Adams et al.
patent: 5764638 (1998-06-01), Ketchum
patent: 5781735 (1998-07-01), Southard
patent: 5784298 (1998-07-01), Hershey et al.
patent: 5787253 (1998-07-01), McCreery et al.
patent: 5802054 (1998-09-01), Bellenger
patent: 5805808 (1998-09-01), Hasani et al.
patent: 5812529 (1998-09-01), Czarnik et al.
patent: 5819028 (1998-10-01), Manghirmalani et al.
patent: 5825774 (1998-10-01), Ready et al.
patent: 5835726 (1998-11-01), Shwed et al.
patent: 5835963
Dietz Russell S.
Sarkissian Haig A.
Hi/fn Inc.
Inventek
Ngo Ricky
Nguyen Alan V.
Rosenfeld Dov
LandOfFree
Associative cache structure for lookups and updates of flow... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Associative cache structure for lookups and updates of flow..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Associative cache structure for lookups and updates of flow... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3271143