Dual key controlled content addressable memory for accessing...

Details Dual key controlled content addressable memory for accessing... Dual key controlled content addressable memory for accessing...

1999-09-09

2003-08-12

Marcelo, Melvin (Department: 2663)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S432000, C370S395710, C711S108000

Reexamination Certificate

active

06606317

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to communication systems, and is particularly directed to a new and improved output port centric digital data management architecture for a high speed packet switch, that employs a dual key-based content addressable memory (CAM)-based buffer access control mechanism to effect high efficiency storage of (relatively long) data packets, and distribution of an individually stored packet to one or more output ports of the switch.
BACKGROUND OF THE INVENTION
Continuing improvements in speed and bandwidth efficiency of digital signal processing components have enabled telecommunication service providers to supply multiple types of signalling channels from one or more sourcing sites to a switching interface serving a number of destination equipments. Accompanying these improvements has been the need for increased storage and data delivery capacity of the data switching and distribution elements that make up the switching interface. In a high data rate/capacity terrestrial system this has typically been accomplished in a brute force fashion, by using a very large (e.g., room-sized) data buffering subsystem, having separate (maximal capacity) data stores dedicated to each port being serviced. Because of its extraordinarily large size and considerable power requirements, this type of a data storage and distribution subsystem is not only impractical, but effectively impossible to deploy in an airborne or spaceborne environment, where payload power consumption parameters must comply with very limited specifications.
SUMMARY OF THE INVENTION
In accordance with the present invention, this problem is successfully addressed by a new and improved output centric packet switch architecture that employs a dual key content addressable memory (CAM)-based data storage management mechanism, which is configured to control, in a highly efficient manner, the storage and distribution of received data packets to one or more output ports of a P input port, M output port packet switch. The respective P input ports of the switch are coupled to asynchronous data links that transport packetized digital data from a variety of data sources from upstream modulation and demodulation and associated carrier interface components, such as, but not limited to those employed at the front end of a satellite communication system. As will be described, the size of a nominal data packet is presumed to be relatively long (e.g., in excess of 300 bytes, as a non-limiting example).
The P input ports of the switch are coupled to an input packet buffer that serves as a temporary holding queue, to allow for analysis/decoding of header information in each received packet, and thereby determine whether a respective packet is to be distributed to one or more of the M output ports of the switch or discarded. The packet header is coupled to a look-up table, which is interfaced with the switch's host processor and a packet buffer access controller, which supplies control and timing signals to the various components of the switch. If the header of a received packet indicates that the packet is to be supplied to one or more of the switch output ports, the packet is coupled through a P:
1
‘packet’-multiplexer and loaded into an output packet buffer. A packet record is stored in only a single storage location of the output packet buffer. This enables the capacity of the packet output buffer to be reduced considerably relative to the capacity of conventional data memories, which store a separate copy of the data for each output port to which the packet is to be delivered. This storage space reduction is particularly significant for multicasting relatively long packets.
When a packet is written to the output packet buffer, the header information is mapped by the look-up table and packet tag generator—controller into a multi-field buffer address pointer word, that is written to one or more (for multicasting) addresses of a dual key controlled content addressable memory (CAM). A significant aspect of the present invention is the fact that each output packet buffer address pointer word stored in the CAM contains two key fields:—a K bit ‘key’ field and a companion N bit ‘address association’ field. The K bit ‘key’ field is defined in accordance with a destination output port, quality of service information and the age of the packet and is generated by the packet tag generator—controller. The N bit ‘address association’ field points to the address within the output packet buffer where that packet is stored. Because the length of a respective buffer address pointer word is considerably smaller than that of a packet, the amount of memory required to implement the CAM is considerably less than that of the output packet buffer.
When a packet is to be written into the output packet buffer, the address of a free storage location within the output packet buffer is obtained from a free address table (FAT), which tracks the addresses of the output packet buffer that are ‘available’ or ‘free’ to store a new packet. The FAT contains a list of addresses for the free or available packet storage locations in the output packet buffer. As a new packet arrives, a free address is retrieved from the FAT. Once the packet has egressed through all appropriate output ports, the address in the location where the packet was stored will be returned to the FAT.
Since each key field stored in the CAM identifies the address within the output packet buffer where the requested packet is stored, an associative search of the CAM using that key will access the contents of the address association field that point to the address of the output packet buffer where the requested packet is stored. In response to a match of the K bit key field, the contents of its companion N bit address association field are read out and used to access the packet from the output packet buffer, for delivery to a switch output port.
The N-bit address association field is then used to search for other instances of the same address in the CAM to determine if the packet is required for pending egress to a multi-cast destination on a different output port. If no other instances of the same address are found in the CAM, the address is returned to the FAT as a free address.
Within the CAM itself, the dual key buffer address pointer words are organized as an array of words, similar to random access memories, which reduces the complexity of address decoders for read/write access and data association. All of the key match outputs of a respective row of words are coupled to a respective row OR gate, and all of the key match outputs of a respective column of words are coupled to a respective column OR gate, so as to form row and column addresses.
Within the CAM, the K+N bit words are physically organized as an array similar to random access memories. This reduces the complexity of address decoders for read, write, and compare operations. Each K+N bit word contributes data lines to indicate matches to its respective fields. The K-bit field contributes a “match” output to row and column decoders. Typically these decoders take the form of “or-gates”. The decoded row and column from the K-bit field is used directly to access the associated N-bit data field. When the N-bit associated data field is used as the “key” for the second search, (i.e. to determine multi-cast), only a single indication of multiple instances of the address in the other association field is necessary. Hence, the N-bit association fields can be “or-ed” by either row or column since we only need to know if there are other instances of the same address or not.


REFERENCES:
patent: 4065756 (1977-12-01), Panigrahi
patent: 4219883 (1980-08-01), Kobayashi et al.
patent: 4959811 (1990-09-01), Szczepanek
patent: 5010516 (1991-04-01), Oates
patent: 5018099 (1991-05-01), Burrows
patent: 5455784 (1995-10-01), Yamada
patent: 5528588 (1996-06-01), Bennett et al.
patent: 5566170 (1996-10-01), Bakke et al.
patent: 5689505 (1997-11-01), Chiussi et al.
patent: 5732087 (1998-03-01), Lauer et al.
pa

Affiliated with

Also associated with

Rating

Dual key controlled content addressable memory for accessing... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Dual key controlled content addressable memory for accessing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dual key controlled content addressable memory for accessing... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3084041