Abstract:
An input processor recognizes and accepts a wide variety of protocols and formats. Queue management stores the uniform cells in a dual balanced bank memory system, which provides for utilizing an available bank of memory when the other bank of memory is in use, and otherwise balancing the use of the banks of memory, thereby maintaining equal free lists. Queue management apparatus and logic also ascertains and appends routing data to the stored data and transmits the data according to its priority.

Description:
BACKGROUND OF THE INVENTION 
     This invention relates to communication switches and data storage systems for use therewith, and more particularly, to a multiple queue bank balanced queue control system, architecture, and methodology. 
     Most current network switches utilize a single queuing memory control structure, where data in and out from one or more sources (e.g., Ethernet, ATM, etc.) and one or more output sources of the same or different types can be served by the single queue memory and control structure. One problem with the single queue memory and queue control system is that the queue system becomes a bottleneck, so that data flow can only be in to or out of the queue, that is the queue controller and queue memory provide for only unidirectional data transfer. 
     In accordance with the present invention, there is provided a balanced, shared multiple bank queue memory architecture with a queue control and management architecture providing for balanced queue memory utilization to prevent queue congestion and overflow problems, and to provide for queue control management providing for bidirectional simultaneous data flow permitting both input and output queuing to be performed concurrently. 
     SUMMARY OF THE INVENTION 
     In accordance with one aspect of the invention, an input processor recognizes and accepts a wide variety of protocols and formats including fast ATM and fast Ethernet to produce prioritized uniform cells for internal use within the dual balanced queues, for effective queue management. A queue management subsystem stores the uniform cells in a memory subsystem, and maintains a dual free linked list for both memory banks, and two individual in use link lists, one for each memory bank. 
     A queue usage subsystem determines at defined points in time whether and which of the first and second queue memory banks are in use, and a queue selection subsystem responsive to the usage subsystem determines which queue memory bank is in use and which is available, and selects a memory bank not in use, and a second queue select subsystem responsive to the usage subsystem determines when neither first nor second queue memory bank is in use and determines selection of one of the first and second queue memory banks, preferably based on which is less full in capacity. 
     These and other aspects and attributes of the present invention will be discussed with reference to the following drawings and accompanying specification. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1A shows a dual memory bank buffer embodiment of the hybrid queue switch of the present invention; 
     FIG. 1B is a block diagram of an input subsystem directed to received Ethernet data; 
     FIG. 1C is a block diagram of an input subsystem directed to received ATM data; 
     FIG. 2 is a block diagram of a queue controller with link list management; 
     FIGS. 3A and 3B are flow diagrams of the dual bank embodiment hybrid queue switch of the invention; 
     FIG. 4 is a block diagram of the queue controller with link lists for each queue memory; 
     FIG. 5 is a queue storage state flow chart; 
     FIG. 6 is a queue output state flow chart; and 
     FIG. 7 is a block diagram of the link list pointers and the associated data storage location showing how input data is stored in the dual memory queue banks of the illustrated embodiment of the invention. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     While this invention is susceptible of embodiment in many different forms, there is shown in the drawings, and will be described herein in detail, specific embodiments thereof with the understanding that the present disclosure is to be considered as an exemplification of the principles of the invention and is not intended to limit the invention to the specific embodiments illustrated. 
     In the preferred embodiment, a dual bank balanced queue system is provided. In the preferred embodiment, the queue memory banks described hereinbelow are physically separated. However, any memory system which can implement the memory management functions as taught herein (single or multiple banks) can be used as one of ordinary skill can readily appreciate in accordance with the following disclosure. 
     Referring now to FIG. 1A, the basic elements which comprise the dual bank queue system (10) are shown. Input subsystems (1, 2) accept corresponding incoming data or cells source (60, 70) for coupling to the queue controller (140). The queue controller (140) is coupled to input subsystems (1, 2), via input multiplexers (120, 121), and is coupled to output demultiplexers (150, 151) and therefrom to output processors (160, 161) to provide respective output (60, 61). The queue controller (140) is also coupled to the queue memory (banks 1 and 2) (130, 131). The queue controller processes, stores, and transmits data between input subsystems and output subsystems using the queue memory. The queue controller establishes, maintains, and provides management of the balanced operation (providing both optimal free space usage and concurrent simultaneous input and output processing) dual bank queue operation. 
     Incoming packet (e.g., Ethernet) data frames of varying length (e.g., from 108 bits to 1582 bits) or ATM cells having a fixed cell length (e.g., of 53 bytes) enter the input subsystems (1, 2), respectively. In a preferred embodiment, there are eight input subsystems, each controlling four channels, to provide for thirty-two channel capacity. For example, each input subsystem (2 and 1, respectively) can support up to four ATM interfaces at 155 Mbps or four fast Ethernet interfaces at 100 Mbps. In an alternate embodiment, the four ATM interfaces may be replaced by one 622 Mbps ATM interface or by a multiple of ATM interfaces at lower speeds. 
     In the illustrated example as shown in FIG. 1A, input signal source (1) is Ethernet data, and input signal source (2) is ATM data. Alternatively, the input subsystems (1, 2) can be uniprotocol, that is ATM or Ethernet. 
     The input subsystems (1, 2) establish a connection and terminate the physical network layer for the data communication. The media access control (MAC) layer of the incoming data is part of the received header which establishes a connection. Processing the MAC data layer of ATM and Ethernet is very similar. MAC layer processing is modeled on well known industry standards. (See, for example, IEEE 802.3 [CSMA/CD], IEEE 802.4 [token bus], IEEE 802.5 [token ring], IEEE 802.6 [Metropolitan Are Network]). 
     Referring to FIG. 1B, received Ethernet packets (60) (normally coming from a conventional Media Access Control (MAC) device (116a), in this example having input ports 1-4) are buffered in a MAC interface (116). As soon as a minimum packet length is received, a lookup function is implemented by the input processor (101) with lookup memory (100m) to gather routing information. After the lookup and routing appendage is complete, a segmentation function is executed by the input processor (101). The segmentation function splits the variable length Ethernet packets (60) into internal cells processable as DTM cells. Housekeeping and encapsulation (such as ensuring packet size and producing parity) is then performed. After this conversion and preparation, the internal cells are then ready to be sent to multiplexers (120, 121) over input buses (600, 601) under the control of the queue controller (140). 
     As shown in FIG. 1C, ATM cell data source (70) (having header nd payload portions) is received at the input port A-D (106) of input subsystem (2). By appending a header with the value from a lookup memory (102m) based on the VP/VC (Virtual Path/Virtual Channel) number in the header portion, a lookup function is executed by the queue controller (140). The result of the lookup is then appended to the internal cell by the input processor (102) (FIG. 1C). The queue controller (140) supplies queue management information which is also appended to the cell header by the input processor (102). The appended cell is then buffered in buffer memory (111). the appended cell is then ready to be sent to the multiplexer (121) to the queue controller (140) which provides for the queue memory selection, management, and control of storage. 
     In the preferred embodiment, the queue controller (14) supplies data routing information which consists of Queue number, Control number, Multicast mask, and Port (priority) number. In the preferred embodiment, the Queue number is a 14 bit tag indicating which queue memory (130, 131) the packet will be stored in. The Control number is a 2-bit tag that indicate start of packet, end of packet, normal cell in a packet, and abort (flush the queue). The Multicast Mask is a 46 bit attachment to a packet for indicating that the packet can be transmitted or routed anywhere. The queue controller (140) uses a two stage multicast mask, the second stage utilizing geographically distributed bits for geographically designating that a packet of interest is geographically limited as to transmission. The first stage multicast mask is used to select an output processor (160, 161). 
     Referring to FIGS. 1A and 2, port or priority is a number used by the queue controller (140) in its control memory (145) to associate an input processor subsystem (1, 2), and indicate to which output port (61, 71) and what priority the queue memory (130, 131) is assigned. Each queue memory (130, 131) is assigned a set of linkage and mapping and at a processing components by the queue controller (140). Examples of these components include a queue write pointer (19 bits), a queue read pointer (19 bits), a cell counter, a differential counter, and a maximum queue length. 
     Each input subsystem (1, 2) feeds a corresponding data multiplexer (120, 121), respectively. In the preferred embodiment, each multiplexer (120, 121) selectively receives incoming internal cells from associated input processors (101, 102) and sends those cells to the queue controller (140) which provides for storage of these cells to a specified location in one of the queue memory banks (130, 131) via the input bus (600, 601). In a preferred embodiment, the associated input bus (600, 601) between the multiplexers (120, 121) and input processors (101, 102) is a 16-bit bus running at 50 Mhz. Thus, the present invention provides the simultaneous reading and writing from different queue banks (130, 131) in real time, thus permitting double channel bandwidth including continuous bidirectional queue input and output, simultaneously. 
     In the preferred embodiment, the queue controller (140) is constructed on an ASIC and performs numerous additional functions as follows. The queue controller (140) organizes each of the queue memory banks (130, 131) into a number of logical queues (211-215, and 221-225 (FIG. 4)). In a preferred embodiment, the maximum number of queues supported by the system is 16,348. Each internal cell as output by the input processors (101, 102) is assigned such a queue number by the queue controller (140). This queue number is appended to the respective cells by the input processor (101, 102) as stated above. The queue number is placed in the routing tag field within each cell. In one embodiment, the memory consists of Synchronous Dynamic Random Access Memory (SDRAM) which SDRAM requires lower power consumption than non-synchronous DRAM. 
     In an alternate preferred embodiment, only a single physical memory bank is used, with a single input bus, but structured with two logical queue memory banks therein. 
     After data enters the buffer (FIG. 1A 110, 111) of the input processors (101, 102), the queue controller (140) arbitrates between the input processors to determine processing priorities, that is determined by the input processor with the highest priority. Priorities are set according to FIFO principles, organized by a link list, described below. The ;multiplexers (120, 121) sends prepared cells to the queue memory banks (130, 131) responsive to the queue controller (140). 
     Turning to the flow diagram of FIG. 5, the queue controller also defines the memory location where the prepared cell will be sent based on current queue memory bank (130, 131) availability, and if both banks are available, the bank chosen is that having the most available free memory space. If a memory bank (130 or 131) is currently in use, the queue controller (140) sends the prepared cell to the idle bank not in use, queue memory bank (130, 131) for the write operation. This dual bank queue memory system of the present invention allows for concurrent reading and writing to memory. This novel switch fabric thus provides for simultaneously writing to one queue bank (e.g., 130) while the other queue bank (e.g., 131) is being read from (FIG. 3). and can also provide for two concurrent simultaneous read or writes. 
     Continuing to refer to FIG. 5, a dual free-cells list mechanism in the queue controller (140) ensures load balancing between the two queue banks (130, 131). If neither queue memory bank (130, 131) is in use, the queue controller (140) loads the queue memory bank that has the most unused memory. By so doing, the queue controller (140) balances the amount of available memory in each queue bank. Data in the memory banks (130, 131) is maintained in the form of queues on a FIFO basis, organized by a link list (102) maintained by the queue controller (140) (FIG. 2) with the control memory (145). 
     A cell in queue memory consists essentially of two parts, data and control (header). The control portion is established by the queue controller and contains the link list pointers (or address) of the data (FIG. 7). 
     As shown in FIG. 7, detailing control memory (145), the header portion (Q1, F1), etc. of a data cell, may be stored in one queue memory location and the tail portion may be stored in another queue memory. The link list is used to enable this operation, and keeps track of the mapping relationships. 
     Subsequent to writing to a queue memory location, the queue controller (14) manages the link list subsystem (102) for the cell buffer (110, 111) and the location therein. Link list memory is provided by control memory (145) and is assigned on a per cell basis, to maintain the queues as described. The control memory (145) is addressed under the control of the input arbitrator (201) and the output arbitrator (202) to prepare each read/write cycle. Each of cell queue buffer controllers (104, 105) is assigned to a respective one of the queue memory banks (130, 131) to maintain a free link list for chaining all of the unoccupied queue memory in each bank and also creates a link listing for every queue which is so defined (FIG. 7). This dual free link list subsystem thereby provides for the simultaneous read and/or write from the balanced, shared queue memory upon demand. 
     The queue controller (140) further performs cell measurement for monitoring and policing the actual status of data transmission, so as to be aware of actual queue memory space available. 
     As shown in the flow diagram of FIG. 6, to ready data for final transmission out, the queue controller&#39;s output arbitration subsystem (202) (under the control of the queue controller (140)) functions as a queue serve, arbitrating data output functions. This is accomplished in the illustrated embodiment, using a round robin routine considering weighted priorities subsequent to choosing an available queue memory bank (130, 131). The same round-robin weighted process is used to provide for storing incoming data, utilizing the link list (420) with the highest priority (425). The output arbitration subsystem (202) coordinates the output demultiplexers (150, 151) to buffer and resegment the data from a chosen queue memory (130, 131) into an acceptable concatenated form for output, and sends it to the proper, respective output processors (160, 161) via a respective output bus )163, 166) for transmission (460). 
     From the foregoing, it will be observed that numerous variations and modifications may be effected without departing from the spirit and scope of the invention. It is to be understood that no limitation with respect to the specific apparatus illustrated herein is intended or should be inferred. It is, of course, intended to cover by the appended claims all such modifications as fall within the scope of the claims.