Architecture for high performance management of multiple circular FIFO storage means

• US 5,519,701 A
• Filed: 03/29/1995
• Issued: 05/21/1996
• Est. Priority Date: 03/29/1995
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Krug, Robert W., Smith, Alexander A., Colmant, Michel M.
• Primary Examiner(s): Chin, Wellington
• Application Number:
  US08/412,812
• Time in Patent Office: 419 Days
• Field of Search: 370/60, 370/60.1, 370/61, 370/85.1, 370/85.2, 370/85.3, 370/85.4, 370/85.5, 370/85.6, 370/85.15, 370/94.1, 370/94.2
• US Class Current: 370/412
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A queue manager manages multiple interfaces among a network, a host bus and a storage means including multiple circular FIFO'"'"'s in a data communication system handling packet and multimedia data transferred, in either direction, between the host bus and the network. The queue manager includes a programmable parameter RAM interface, computation logic and status means. An efficient queue management algorithm dynamically manages storage of data in the circular multiple FIFO'"'"'s as data is transferred, in either direction, between the host bus and the network. System bandwidth is allocated by the queue manager to the queues which have the most activity thereby improving the speed of transferring data while reducing the amount of bandwidth that would otherwise be required by prior systems. The programmable interface permits a user to define and dynamically configure the multiple circular FIFO storage means to include other parameters useful in the management of data transferred between the host bus and the network.

Claims

1. In a data communication system handling packet and multimedia data transferred in either direction between a host bus and a network, a queue manager for managing multiple circular FIFO storage means included in the system, comprising:

(a) a programmable parameter RAM including a base pointer array, a threshold array, a read pointer array and a write pointer array;

each array having two sides, one side of each array coupled to an input selector, the other side of each array coupled to a first output selector, the read and write pointer arrays being further coupled to a second output selector;

(b) computation logic means coupled to the first and second output selectors and including a first calculating means, a second calculating means, and logic means, the first calculating means calculating a queue limit that is the top location of the queue and providing an output signal "qatlim";

the second calculating means calculating the amount of space remaining in a queue and providing a queue empty signal or a queue at or above threshold signal;

(c) the logic means coupled to the second calculating means for providing a queue almost full or queue full signal;

(d) means coupled to the first selector for programming the parameter RAM; and

(e) status means coupled to the computation logic means for receiving the empty, full, wrapped, almost full, and threshold signals for use by an application running in the system in receiving data from or sending data to the multiple circular FIFO storage means.

2. A method of generating signals useful in a queue manager for managing multiple circular FIFO storage means in handling incoming/outgoing data in a data communication system comprising the steps of:

(a) providing to a first calculating means a selected pointer address in the circular FIFO storage means;

(b) providing as a first output from the first calculating means an incremented selected pointer address;

(c) providing to the first calculating means a base and size signal and providing as a second output signal a queue limit signal or the top location of a queue;

(d) providing to a second calculating means a read pointer signal, a write pointer signal, a wrapped signal, and a memory access signal to generate a queue empty signal from the second calculating means;

(e) providing as inputs to a third calculating means a threshold signal, a write pointer and a read pointer signal to generate as an output an at/above threshold signal; and

(f) providing as an input to a logic means a data signal from each queue and generating as output signals a queue full or queue almost full signal, the signals generated in steps (c)-(f) used by the queue manager in managing incoming/outgoing data in the data communication system.

3. In a data communications system handling packet data and multimedia data transferred in either direction between a host bus and a network, a queue manager for managing multiple circular FIFO queue storage means included in the system, comprising:

a programmable parameter RAM having as programmable parameters (i) a base pointer for each queue storage means identifying the starting location in the storage means;

(ii) queue size or quantity of data;

(iii) a threshold value indicative of when data can be transferred out of a queue;

an "almost full" control indication of the amount of space or room left in a queue and used to set an "almost full" status line;

(iv) a read pointer initially set to the base pointer; and

(v) a write pointer initially set to the base pointer;

computation logic exercising the programmable parameters to generate control signals used to update status bits for a queue being serviced by the queue manager;

and status means coupled to the computation logic for receiving an "empty", "full", "wrapped", "almost full", and threshold signals used in receiving data from or sending data to the multiple circular FIFO queue storage means.

4. In the data communication system of claim 3, the computation logic including a first three input adder for calculating the one'"'"'s complement of the data filed in the winning queue;

a two input adder for generating a carry signal when the winning queue is "empty"; and

a second three input adder generating a signal when the data in the winning queue is equal to or greater than a threshold value set by the winning queue.

5. In the data communication system of claim 4, the queue manager adapted to simultaneously store data from the host or network interfaces in a receive queue while transmitting data to the host or network interface from the transmit queue.

6. In the data communication system of claim 4, the queue manager adapted to store data transferred between the host and network interfaces in local storage before transferring data to or from the multiple circular FIFO queue storage means.

7. In a data communications system handling packet data and multimedia data transferred in either direction between a host bus and a network, a queue manager for managing multiple circular FIFO queue storage means included in the system, comprising:

a priority control circuit responsive to a packet data source/sink and an isochronous data source/sink for selecting the data having the highest priority and providing an output to a programmable parameter RAM indicating a winning queue for storing the data;

a programmable parameter RAM providing a plurality of parameters descriptive of the winning queue;

computation logic receiving the parameters from the programmable parameter RAM and calculating the space or room available in the winning queue for storing the data having the highest priority; and

status means coupled to the computation logic for providing signals to an application running in the system for handling data to and from the multiple storage queues.

8. In the data communications system of claim 7, the storage means further divided into receive and transmit queues and both the host and network interfaces including local storage.

9. In the data communication system of claim 7 further including a local processor for programming the parameter RAM in response to a user input.

10. In a data communications system handling packet data and multimedia data transferred in either direction between a host bus and a network, a queue manager for managing data transferred among a host interface, a network interface and a storage interface including multiple queue storage means, comprising:

a programmable parameter RAM for generating signals indicative of the data storage status of each queue included in the storage means;

computation logic coupled to the progarammable parameter RAM for receiving signal descriptive of a queue selected for storing data;

the computation logic generating computed signals determining when a queue is "full", "empty", "almost full", or "at/above threshold"; and

status means for receiving the computed signals for controlling an application running in the system to receive data from or sending data to a multiple queue storage means.

11. In a data communications system handling packet data and multimedia data transferred in either direction between a host bus and a network bus, a queue manager for managing the transfer of data among a plurality of interfaces coupled to the host, the network and a storage means including multiple queues, comprising the steps of:

(a) reading a word out of the storage interface comprising the steps (i) writing the corresponding queue number into a request queue for a word to be passed to a destination interface;

(ii) transferring the data word to the destination interface if the corresponding queue is "empty" and if there is room in a destination interface queue;

(iii) storing the word in a local storage queue if the destination interface queue is "full" or if the corresponding queue and local storage is "empty"; and

(iv) asserting an acknowledge signal to a request pool when the request to service or if the request cannot be serviced due to special conditions such as queue overflow or queue disabled;

(b) writing a word into a host or network interface comprising the steps of;

(i) operating a direct transfer between the interfaces via asserting a "load" line and appropriate "close queue NUM" line to the destination interface independently of a request being presented by the interfaces;

(ii) writing the corresponding queue number into a request pool for an interface that is transmitting a word to another device; and

(c) servicing the request if the corresponding queue in local storage is "not empty" and if the interface data is "not full";

asserting an acknowledge signal when the request at the top of the pool corresponds to local storage that is "empty" or if the interface data queue is "full" or if the queue has been "disabled".