Altera Corporation

Alcatel Canada Inc.

Alcatel-lucent Canada Inc.

Netlogic Microsystems, Inc

Paul Nadj

David Walter Carr

Edward D Funnekotter

Jason T Sterne

Steve Driediger

Andre Poulin

Robert Morton

Steven Douglas Margerm

Sandra Stark

Subramani Kengeri

Cristian Lambiri

Randall Allan Law

Jaya Prakash Samala

Allan Randall Law

A method for high-speed scheduling and arbitration of events for computing and networking is disclosed. The method includes the software and hardware implementation of a unique data structure, known as a pile, for scheduling and arbitration of events. According to the method, events are stored in loosely sorted order in piles, with the next event to be processed residing in the root node of the pile. The pipelining of the insertion and removal of events from the piles allows for simultaneous event removal and next event calculation. The method's inherent parallelisms thus allow for the automatic rescheduling of removed events for re-execution at a future time, also known as event swapping. The method executes in O() time.

System and method for scheduling and arbitrating events in computing and networking

A method for high-speed scheduling and arbitration of events for computing and networking is disclosed. The method includes the software and hardware implementation of a unique data structure, known as a pile, for scheduling and arbitration of events. According to the method, events are stored in loosely sorted order in piles, with the next event to be processed residing in the root node of the pile. The pipelining of the insertion and removal of events from the piles allows for simultaneous event removal and next event calculation. The method's inherent parallelisms thus allow for the automatic rescheduling of removed events for re-execution at a future time, also known as event swapping. The method executes in O(1) time.

A search engine searches a database for key candidates having a longest matching prefix with a search key. The search engine includes first stage decoders each having a matrix of interconnected cells for identifying preliminary candidate keys in the database. The search engine also includes a second stage decoder having a matrix of interconnected cells for identifying secondary candidate keys from the preliminary candidate keys. Additionally, the search engine includes a longest candidate prefix module to determine whether one of the secondary candidate keys matches the search key. In some embodiments, the search engine includes a longest prefix match module for identifying the secondary candidate key having a longest matching prefix with the search key.

Longest matching prefix search engine with hierarchical decoders

An improved data structure is provided by modifying a public-domain data structure known as a 'heap'. When these improvements are applied, the resultant data structure is known as a 'pile.' This invention further describes a pipelined hardware implementation of a pile. Piles offer many advantages over heaps: they allow for fast, pipelined hardware implementations with increased throughput, making piles practical for a wide variety of new applications; they remove the requirement to track and update the last position in the heap; they reduce the number of memory reads accesses required during a delete operation; they require only ordinary, inexpensive RAM for storage in a fast, pipelined implementation; and they allow a random mixture of back-to-back insert, remove, and swap operations to be performed without stalling the pipeline.

Data structure and method for pipeline heap-sorting

A method and apparatus for segmenting and forwarding data packets received in a communication switch is presented. The method begins by receiving a packet that includes a destination that determines forwarding parameters. As the packet is being received, segmentation cells are created from portions of the packet received where each segmentation cell is provided to a switching fabric as soon as creation of the segmentation cell is completed. When an end portion of the packet is received, verification of proper receipt of the packet is performed. When it is determined that the packet has been received successfully, a verification data set is generated based on segmentation cells that have been utilized to forward the packet. If it is determined that the packet has not been successfully received, a purging data set is generated instead of the verification data set.

Method and apparatus for segmentation and reassembly of data packets in a communication switch

An improved data structure is provided by modifying a public-domain data structure known as a 'heap'. When these improvements are applied, the resultant data structure is known as a 'pile.' This invention further described a pipelined hardware implementation of a pile. Piles offer many advantages over heaps: they allow for fast, pipelined hardware implementations with increased throughput, making piles practical for a wide variety of new applications; they remove the requirement to track and update the last position in the heap; they reduce the number of memory reads accesses required during a delete operation; they require only ordinary, inexpensive RAM for storage in a fast, pipelined implementation; and they allow a random mixture of back-to-back insert, remove, and swap operations to be performed without stalling the pipeline.

Data structure and method for sorting using heap-supernodes

A method for identifying faulty modules within telecommunication devices, such as ATM switches, involves generating and attaching verification codes, such as a CRC or checksum codes, to data packets at an upstream location determining the integrity of the verification codes at each of multiple downstream location within a telecommunication device; and signaling an error condition where a corrupted data packet has been detected. A verification code may be written to a field of a data packet which is not used while the packet is in transit through the telecommunication device.

Method and apparatus for providing integral cell payload integrity verification and detecting defective modules in telecommunication devices

Error checking and correcting (ECC) is performed on data held in a content addressable memory. An error check circuit receives words from a memory circuit or circuits, generates an error status and generates a corrected value when appropriate. A control circuit sequences through each of the words of the memory circuit(s), periodically reads from the memory circuit the next word in the sequence and provides the next word to the error check circuit. The bandwidth consumed by the periodic error check phase can be controlled by adjusting the interval between reads.

Error checking and correcting for content addressable memories (CAMs)

A method and apparatus for segmenting and forwarding data packets received in a communication switch is presented. The method begins by receiving a packet that includes a destination that determines forwarding parameters. As the packet is being received, segmentation cells are created from portions of the packet received where each segmentation cell is provided to a switching fabric as soon as creation of the segmentation cell is completed. When an end portion of the packet is received, verification of proper receipt of the packet is performed. When it is determined that the packet has been received successfully, a verification data set is generated based on segmentation cells that have been utilized to forward the packet. The verification data set is then included in a final segmentation cell that is provided to the switching fabric. Such a verification data set can then be used by an egress line card that receives the segmentation cells to verify proper receipt of the segmentation cells. If it is determined that the packet has not been successfully received, a purging data set is generated instead of the verification data set. Such a purging data set is then included in the final segmentation cell that is provided to the switching fabric, where the purging data set preferably causes any egress line card to purge the corrupted packet rather than forwarding it.

A method for identifying faulty modules within telecommunication devices, such as ATM switches, involves generating and attaching verification codes, such as CRC or checksum codes, to data packets, such as ATM cells, at an upstream location, determining the integrity of the verification codes at each of multiple downstream location within a telecommunication device; and signaling an error condition where a corrupted data packet has been detected. A verification code may be written to a filed of a data packet which is not used while the ATM cell is in transit through the telecommunication device, thereby identifying a faulty module device without adversely affecting throughput.

A method and apparatus for packet classification stores rules or parameters for classifying the packets in a memory structure. The memory structure receives a set of rule selection signals, where the memory provides a selected set of rules in response to the rule selection signals. A comparison block operably coupled to the memory receives a key, which is also preferably derived from the header information for the packet. The key includes the relevant information for classifying the packet according to the rules stored in the memory. The comparison block compares the key with each of the rules in the selected set of rules, and when a favorable comparison is determined, the comparison block provides an indication of the favorable comparison. A prioritization block operably coupled to the comparison block prioritizes the rules that resulted in a favorable comparison to determine a preferred rule, where the preferred rule includes the resulting classification information for the packet.

Growing community of inventors

Ottawa, Canada

Paul Nadj