3com Corporation

Atrica Israel Ltd.

Golan Schzukin

Ilan Shimony

Zvika Bronstein

Opher Yaron

Yoav Honig

Haim Rochberger

Eytan Mann

Lior Shabtay

Sarit Shani Natanson

Yaron Raz

Ronit Aizicovich

Gennady Dosovitsky

Doron Vider

Roni Elran

Ari Halpern

A novel policer mechanism that incorporates randomization of the rate threshold which prevents 'lockup' and 'synchronization' problems associated with prior art policers that employ fixed rate thresholds. In one embodiment, a policer machine utilizes the well known sliding window technique to implement traffic control. In a second embodiment, a policer machine utilizes the well known token bucket technique to implement traffic control. In both embodiments, a random dimension is added to the rate threshold used by each policer algorithm. For the sliding window embodiment, the effect of randomization of the rate threshold is that the policer machine applies a scattering of rate values centered around the desired rate to the incoming traffic. For the token bucket embodiment, a random dimension is added to the empty bucket (i.e. zero tokens) threshold. The effect of randomization of the empty bucket threshold is that the policer machine applies a scattering of token values above the empty bucket threshold value of zero.

Policing machine incorporating randomization of rate threshold

An apparatus for and method of enforcing precedence of committed traffic over excess traffic that overcomes the difficulty in supporting committed over excess traffic and has particular application to distributed queuing systems. Queue control messages are generated and transmitted to other line cards to guarantee that committed traffic is not dropped when sent from multiple sources such as line interface cards to a single destination. When the level of a queue exceeds a threshold and flow control is received for the corresponding destination, the queue starts dropping excess traffic and messages indicating the queue status are sent to all other lines cards. When a line card receives a queue control message that another line card started dropping excess traffic to a specific destination, it also starts dropping excess traffic to that destination as well.

Apparatus for and method of support for committed over excess traffic in a distributed queuing system

A forwarding table comprising a combination of a hash table and a content addressable memory (CAM). The forwarding table combines a one way hash table and a small CAM to perform the forwarding information retrieval function. The CAM is used when an address cannot be found in the hash table. When MAC addresses are being added to the forwarding table, they are first tried in the hash table. The address is applied to the hash function and a resulting index input to the hash table. If a hit occurs, it indicates that an entry at that index already exists and a location in the CAM is then allocated for that address. As long as the CAM does not become full, a 100% hit rate is guaranteed. During retrieval, the hash table or the CAM forms the forwarding information output to the next processing stage. If an entry is not found in the hash table, it will typically be found in the CAM. If no entry is found in either, the received frame is flooded to all the ports of the network device.

Forwarding table incorporating hash table and content addressable memory

A dynamic queuing system wherein a single memory is shared among a plurality of different queues. A single memory, termed a queue memory, is by ally shared by one or more queue. The queue memory is divided into a plurality of memory blocks that we initially empty. An empty list functions to track which memory blocks are empty and available for use in a queue. Each queue constructed utilizes one or more memory blocks. When a queue becomes full, an additional memory block is allocated to it. Conversely, as memory blocks of a queue are read, i.e. emptied, they are returned to the pool of empty memory blocks for use by other queued.

Dynamic queuing system incorporating multiple queues sharing a single memory

An apparatus for and a method of locating and releasing stuck virtual circuits in an ATM network device. Memory resources are freed that would otherwise be lost due to the last cell of a frame not being received on a particular virtual circuit. Two flags: a sticky first_cell flag and a last_cell flag, track the status of the receipt of a frame over a virtual circuit. The software periodically examines the two flags and if both the first_cell flag and last_cell flags are found cleared then a 'stuck' virtual circuit is identified indicating that the hardware did not detect a first cell of a frame on this particular virtual circuit since the last time the software cleared this bit to '0'. In response to the identification of a stuck virtual circuit, the software releases the memory resources consumed by the incomplete frame.

Apparatus for and method of releasing stuck virtual circuits in an asynchronous transfer mode network

An apparatus for and a method of learning MAC addresses in a Local Area Network (LAN) Emulation (LANE) network implemented over an Asynchronous Transfer Mode (ATM) network. The LEC or LES is adapted to detect when the ATM address associated with a MAC address is no longer valid. Once an invalid ATM address is detected the existing entry can be updated or deleted. A LEC_ID table holding LEC_ID to ATM address bindings is created. Each frame received by the LEC is sniffed in order to find mismatches between the ATM address and the LEC_ID. Optionally, an LE_ARP request message can be forwarded to the LES for learning the new binding. If the MAC address is not found in the LE_ARP table, an entry can be created and added to the table. In another embodiment, the LES is adapted to detect when the MAC to ATM address binding stored in the internal LE_ARP cache is no longer valid. The LE_ARP table is populated by examining LE_ARP request and response sent and received by the LEC. Upon detection of a mismatch in LEC_ID, the LES can delete or update the entry. The LES generates and sends a LE_NARP or targetless LE_ARP request message which finctions to notify the LEC in the ELAN of a changed MAC to ATM address binding.

Apparatus for and method of learning MAC addresses in a LAN emulation network

A queue having a 'duplicate' counter associated with each entry whereby duplicate data is not stored in the queue. Before data is placed in the queue, the queue is searched for an entry matching the data to be written. If a match is found, the duplicate counter associated with the entry is incremented. Further, if a match is found and the data stored therein is inconsistent with the current data, the contents of the queue are updated and the duplicate counter associated with the entry is reset to one. If a match is not found, the data is written to the queue and the duplicate counter associated with the entry is initialized to one.

Queue incorporating a duplicate counter per entry

A system for appending data to a packet whereby the original CRC calculated by the transmitting station is not modified and is retained in order to determine the occurrence of transmission errors at the receiver. The invention is applicable in communication systems whereby the data to be appended to the packet comprises a fixed length. The invention appends the data in the form of a tag to the tail of the packet after the original CRC and, in addition, determines and appends a tag CRC to the tail of the packet following the tag data. The tag CRC has a value such that the CRC machine in the receiver generates a constant CRC value even though the packet length was increased. A tag CRC is generated that when appended to the packet produces the same result as if the packet was processed through the CRC machine without any data appended.

Packet expansion with preservation of original cyclic redundancy code check indication

A method of synthesizing a CRC generator circuit for generating optimized code written in a high level hardware description language such as VHDL. The hardware description language code for implementing a CRC generator circuit has significantly less delay and utilizes fewer gates than prior art CRC generator circuit synthesis techniques. The method is operative to generate VHDL code which is then used to synthesize the circuit. The method iteratively generates the remainder equations for a CRC generator given the generator polynomial. During each iteration of the software, duplicate terms in each remainder equation are eliminated. The number of iterations is equal to the number of data bits the CRC generator is to process during each clock cycle. Once all the duplicate terms in the remainder equations are removed, the equations are sorted, rebuilt and translated into hardware description language code such as VHDL. The resulting optimized code may then be synthesized.

Method of synthesizing a cycle redundancy code generator circuit using hardware description language

An apparatus for and a method of compressing the forwarding decision for a frame within a network device. A forwarding decision is compressed yielding a forwarding pointer that occupies far less memory space than the corresponding output port vector. The compressed forwarding pointers are stored in a forwarding table that is accessed using a hash function. A forwarding CAM is used to resolve conflicts in the hash table. The output port vectors are stored in an output port vector table that comprises a relatively small number of possible combinations of the port vector. A forwarding decision is made for each received frame by a forwarding processor in the device. The forwarding decision is represented by a compressed forwarding pointer that is stored in a table and associated with the received frame. At some later point in time, the frame is output to one or more destination ports in accordance with a corresponding output port vector. At this time, the compressed forwarding decision is expanded to an output port vector using the relatively small port vector table. In this fashion, large memories to store the actual output port vector are not needed since only a relatively short pointer to the port vector is stored rather than the port vector itself.

Growing community of inventors

Tel Aviv, Israel

Golan Schzukin