Abstract:
An NXN switch includes N input modules for receiving transmission cells from N input lines and N output modules connected to N output lines for selectively transmitting cells received at the input modules. A bus interconnects the individual input modules to all of the output modules in a predetermined sequence. The input modules store the received cells and a unique ID. When selected the input module places a cell and its ID on the bus along with a multicast vector which identifies which of the output modules is to process the cell on the bus. The output modules examine the multicast vector and process the cell (table lookup) if selected in the multicast vector. If an output cell is unable to process a required cell (successful table lookup) it sets a retry vector resident on the buss and the input module modifies the multicast vector to indicate only those output module(s) which failed to process a required cell. The cell, the ID and the modified multicast vector are placed on the bus in a subsequent selection of that input module.

Description:
FIELD OF THE INVENTION  
         [0001]    The invention relates to digital switches such as ATM switches in general and more particularly to digital switches which handle both unicast and multicast data cells or packets and a method for operating such a switch.  
         BACKGROUND  
         [0002]    Relaying incoming traffic from an input to an output is a classic switch function. Traditional switches typically support unicast traffic only. In order to support multicast traffic, switches often employ at least two stages:  
           [0003]    1) traffic replication, and  
           [0004]    2) traffic relaying.  
           [0005]    In an ATM switch for example, the protocol requires that a cell enters a hop with a header specifically assigned for the cell&#39;s connection over that hop and that the outgoing header is provided by a switch employing a cell header swapping function. To support multicast ATM traffic, ATM switch designers simply added a cell replication stage to the early unicast switch structure. Hence, unicast ATM switch architectures modified to accommodate multicast traffic often employ a three-stage switch (1. cell replication, 2. cell relaying and 3. cell header swapping).  
           [0006]    To facilitate the relaying function, a switch employs an addressing scheme with an explicit internal routing tag; also referred to as a label. Such an addressing scheme requires additional circuitry to encode a routing tag into an arriving cell, to decode the routing tag for relaying purposes and then to remove the routing tag after relaying the cell. The encoding function is primarily based on table lookup. In addition to the encoding routing function, switch designers also assign the replication function to the switch input. The table lookup at the entrance of a switch also provides the traffic filter function and encodes additional information for the cell replication function. These switches often consists of two paths: one for unicast traffic and another for multicast traffic. The unicast traffic cuts-though the replication circuitry but not the multicast. The replication circuitry relies on the multicast information in the label encoded by the input to replicate the multicast cell/packet and may require its own lookup table. Since each copy of a multicast cell leaves a switch with its own header cell, the cell header must be swapped after the cell is relayed. The header swapping function requires another layer of lookup tables. In short, an ATM switch consists of at least two layers of lookup tables: one at the input and another at the output. Depending on the complexity of a switch, it may require three or more layers of lookup tables.  
         SUMMARY OF THE INVENTION  
         [0007]    The invention contemplates a multicast buffered switch which includes a plurality of input modules each connected to a different one of a plurality of input lines over which transmission cells each including a payload are received, a plurality of output modules each connected to a different output line and a multiconductor bus for interconnecting the input and output modules. The input module receives cells and stores each of the received cells. Periodically a stored cell and control information are places on the bus. The output modules receives the bus contents and compares portions of the contents of the bus to stored routing information. If the routing information stored in the output module compares, the cell is queued for transmission over its connected output.  
           [0008]    An object of the invention is to reduce the complexity of multicast buffered switches.  
           [0009]    Another object of the invention is reduce the number of table lookups required in a multicast buffered switch. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0010]    [0010]FIG. 1 is a block diagram of an NxN digital switch constructed according to the invention;  
         [0011]    [0011]FIG. 2 is a block diagram of a single input port and common circuitry which is used by all of the input ports;  
         [0012]    [0012]FIG. 3 is a block diagram of a single output port and common circuitry which is used by all of the output ports; and,  
         [0013]    [0013]FIG. 4 is a detailed block diagram of a component included in FIG. 3. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0014]    The multicast buffered ATM switch, hereafter MBAS, is a single-stage switch in which all three functions (cell replication, cell relaying and header swapping) are executed concurrently. The MBAS utilizes the cell header as its unique addressing scheme (referred to as implicit routing-tag scheme). In an MBAS switch, all cells are served as multicast cells and each output has to filter and to copy its own cells. While a cell is copied into an output queue, the cell header is concurrently swapped. With this switching mechanism, the MBAS employs only a single layer of lookup tables.  
         [0015]    The MBAS switch illustrated in FIG. 1 includes a control module  10 . Control module  10  has an arbitration unit and a master clock which are distributed via a master bus  11  under control of an internal bus control unit. Master bus  11  also has a data or payload bus, a header bus, a multicast bus and a retry bus. N identical input modules  12  connect N input lines to the bus  11 . N identical output modules  14  are connected to the bus  11  and selectively transmit cells received over the bus  11  to connected output lines.  
         [0016]    [0016]FIG. 2 is a detailed block diagram of one of the N identical input modules  12 . The module includes an input line interface  20  which receives ATM cells from an input line  21 . Interface  20  checks the cell header for errors. If none are detected or can be corrected , the interface strips the header error correction (HEC) byte from the cell and adds a unique identification byte (ID) representing its own address in place of the HEC byte . It loads the ID byte stored in a register  23  and the remainder of the received cell (including the VPI/VCI fields and the payload) into a FIFO buffer  22 . A mulicast control signal or vector stored in a register  24  includes N bits, one assigned to each of the N output modules  14 . Register  24  is set to a predetermined state, such as all ones, each time FIFO buffer  22  advances a stored cell to the Head Of Line (HOL) position. The assigned bits on the multicast bus indicate to the respective output units that they have a cell to process. How this is accomplished will become apparent below in connection with the description of FIG. 3.  
         [0017]    A gate module  25  under control of the arbitration and clock units provided over a bus  4  of master bus  11 , connects FIFO  22  and register  24  to their respective multiconductor busses  0 - 3  of master bus  11 . Two bus cycles are utilized to transfer a cell from an input to the outputs. In the first cycle the header and the multicast vector are transmitted via their sub-busses. The payload and the retry vector are transmitted in the very next bus cycle along with the header and multicast vector for a cell from the next input in the arbitration scheme.  
         [0018]    The cell payload is connected to multiconductor bus  0 ; the five byte cell header which now includes the unique input port ID (in place of the HEC byte) is connected to multiconductor bus  1 ; the contents of multicast register  24  are connected to multiconductor bus  2 ; and, a multiconductor retry bus  3 , which is loaded by the output units  14 , is also connected to multicast register  24  and used by the logic controlling register  24  to modify the contents of the register and the multicast control bus  2  to reflect the successful transmission of the forwarded cells at the output modules  14 .  
         [0019]    The output module  14  illustrated in FIG. 3 operates as a two-stage pipeline under control of the control module  10  which provides a global clock for updating routing tables, receiving and processing cells. The global clock is used to synchronize operations of all entities. The first stage includes cell header and multicast bit reception and a table lookup. At the beginning of a bus or relay cycle or period, if the enable bit (the bit in the multicast bus  2  assigned to the output unit) is set, the routing table performs a single-cycle-memory lookup function and provides a match bit when the cell identified by the ID, VPI and VCI in the received header are found in the routing table. If the match bit is set, an outgoing VPI/VCI (and a QoS bitmap vector if used) are retrieved concurrently with the arrival of the cell payload. If a write-enable bit (described below) is set, the whole cell with its outgoing VPI/VCI is then written into the output buffer.  
         [0020]    During the first stage the contents of the five byte header bus  1  are loaded into a register  31 . The VPI/VCI and ID fields are applied to a look up table  32  via a controller  33 . If the bit assigned to this output unit in the multicast bus  2  is in the enable (set) state, a table lookup is performed on the ID,VPI/VCI fields by controller  33 . An enabled multicast bit conditions an AND gate  34  which provides an output if the routing table signals a match on conductor  35 . An output FIFO buffer  36  provides an output bit when it is full and cannot accept an additional cell. A pair of AND gates  37  and  38  receive the output bit from buffer  36  along with the output of AND gate  34 . If FIFO buffer  36  is full AND gate  37  will set its bit in the retry vector on bus  3 . If the buffer  36  is not full AND gate  38  will provide a write enable output bit to the buffer  36 .  
         [0021]    During the second stage (which takes place during a subsequent cycle of bus  11 ), the payload on bus  0 , the VPI/VCI for the outgoing cell from the routing table and those parts of the incoming cell which do not change (GFC, PT and CLP) stored in register  31  are loaded into an input register  39 . If FIFO buffer  36  receives a write enable from AND gate  38  the contents of register  39  are stored during the second stage. The cells stored in FIFO buffer  36  are transmitted in sequence by an output line interface  40 . If any output sends a retry bit over bus  3 , the input module will resend the cell, however the multicast vector will be modified to enable only those output modules requesting a retry.  
         [0022]    An NxN Multicast Buffered ATM Switch includes a switch fabric connecting N inputs to N outputs. The primary functions of an input are two-fold: 1) to recover the digital bit stream, and 2) to stamp a unique input ID into each incoming cell. An output has two primary functions: 1) to selectively receive cells from the bus, and 2) to retransmit outgoing cells. The primary objective of the switching fabric is to relay incoming cells from the inputs to the outputs.  
         [0023]    In the NxN MBAS switch, the switch fabric is a bus system and includes a bus control unit, a set of unidirectional buses including 1) a N-bit feedback retry bus, 2) a N-bit multicast bus, 3) a 5-byte header bus, and 4) a 48-byte payload bus. Input and output ports are connected to the buses in parallel. The header, multicast, and payload buses transmit the ATM cell header, the multicast vector, and the ATM cell payload, respectively. To maximize pipeline speed, the bus arbitration has to achieve zero switch-over time. Thus, the bus control logic has to arbitrate for the next input while the bus transfers the cell header of the current input and the cell payload for the previous input. This calls for a simple bus-arbitration scheme such as time division, round-robin, etc. Furthermore, bus arbitration is done for the header bus only. The input that currently controls the header bus also inherits the multicast bus in the same bus slot and the payload bus in the next bus slot. Each output port is assigned a unique bit in the multicast vector and also in the retry vector. A unique assigned bit of a multicast vector enables the output filtering function, while an associated bit in the retry vector is used to request a retry after the output detects its cell but has no buffer for reception. An output returns its retry bit off if its enable bit is off or the cell is not addressed to it. Hence, a retry vector is an ack of a multicast vector upon completion of a cell filtering.  
         [0024]    In the NxN MBAS switch, each input includes an input-link interface (ILI), a FIFO buffer, and a N-bit multicast register in which each bit is assigned to a specific output and is referred to as the output&#39;s enable bit. The ILI recovers the digital bit stream, performs cell delineation, cell rate decoupling, and error detection using HEC. A hardwired logic replaces an incoming cell&#39;s HEC field by the input ID while the cell is being stored in the input buffer. An input cell&#39;s relay logic is a two-stage pipeline: a cell-header stage and a payload stage The multicast vector is transmitted simultaneously with the header of the head-of-line (HOL) cell. The multicast register is set when a cell becomes the HOL cell, and its content is updated by a retry vector at the end of a relay cycle. After being updated, if the multicast register is reset, the HOL cell is removed from the input queue. The head register is updated at that time if the FIFO  22  is not empty and all bits of the multicast register are then set to start another cell transfer cycle. Otherwise, the multicast register remains reset.  
         [0025]    Each output module includes a cell-admission logic with its routing table, a FIFO buffer queue, and an output link interface (OLI) circuitry. The routing table employs two types of memory: a content-addressable memory module (CAM, also called associative memory) and a random-access memory module (RAM). The CAM stores the incoming portion of the routing table in two columns: input ID and VP/VCI. The RAM section stores the corresponding outgoing portion of the routing table, which has the outgoing VPI/VCI. The CAM allows single-cycle lookup in its table using access keys, each having an input ID and a cell&#39;s VPI/VCI. A lookup is performed only when the output&#39;s enable bit is set. The default state of the match bit is reset. It is only set when the enable bit is set, and a match is found. Upon the assertion of the match bit, the RAM delivers the outgoing VPI/VCI. An output queue is enabled by the write-enable bit and provides a full bit which is set when the queue becomes full. There are two sets of AND logic:  
         [0026]    a) the first set is a logical AND of the write-request bit and the full bit. The output of this AND logic is referred to as retry bit.  
         [0027]    b) the second set is a logical AND of the write-request bit and the inverse of the fill bit. The output of this AND logic is referred to as write-enable bit.  
         [0028]    An OLI is able to retransmit a cell from an output queue per cell slot.  
         [0029]    An output&#39;s cell admission logic is a two-stage pipeline: a table lookup stage and a cell-reception stage. At the beginning of a relay cycle, if the enable bit is set, the routing table performs its single-cycle-memory lookup function and produces a match bit if a match is found. If the match bit is set, a corresponding outgoing VCI/VPI is retrieved; concurrently with the arrival of the cell payload. If the write-enable bit is set, the whole cell with its outgoing VPI/VCI is then written into the output FIFO buffer.  
         [0030]    Thus, the two-stage arrangement allows an output to selectively turn off its second stage or the whole pipeline.  
         [0031]    The invention has been described above in conjunction with a two stage process in which a cell transfer spans two adjacent bus cycles or periods and in which the transfer rate or throughput averages one bus period per cell since two cells transfer over two adjacent bus periods. The described two stage process is more efficient than a single stage process and is the preferred embodiment. However, the invention is suitable for use in a single stage process in which a complete cell would be transferrd in one bus cycle or period. While such an arrangement is not as efficient it could be used in some situations.  
         [0032]    The invention has also been described and illustrated in a single QoS switch, however, it is suitable for use in a multi-class QoS switch. To support multi-class of QoS, the FIFO of each output is partitioned into multiple queues; one per class of QoS. A QoS column is then added in the RAM section of the routing table. Each QoS row is a bitmap vector in which each QoS class is preassigned a bit and in which there is only one bit set per QoS bitmap. A bit in a QoS bitmap is referred to as queue-enable bit and is used to enable its corresponding queue for enqueueing a cell. There are two sets of AND logics per queue:  
         [0033]    a) the first set is a logical AND of a write-request bit and each individual pair of a queue-enable bit and its full bit. The output of this AND logic is referred to as retry-request bit;  
         [0034]    b) the second set is a logical AND of the write-request bit and each individual pair of a queue enable and the inverse of its full bit. The output of this AND logic is referred to as write-enable bit. All retry bits constitutes the retry vector. An OLI is able to retransmit a cell from one of its QoS queues per cell slot.  
         [0035]    In the MBAS switch, the output is the master and its input is the slave. The input has no role in how a cell is going to be switched. An MBAS switch does not have any concern that an incoming cell is a unicast cell or multicast cell. If an output successfully filters a cell, it copies the cell and swaps the cell header concurrently. The cell is then ready for retransmission.  
         [0036]    The foregoing is illustrative of the present invention and is not to be construed as limiting the invention. While several embodiments of this invention have been described in detail, those skilled in this art will readily appreciate that many modifications are possible without materially departing from the novel teachings and advantages of this invention. Accordingly, all such modifications are intended to be included within the scope of this invention as defined by the claims. In the claims, means-plus-function clauses are intended to cover the structures described herein as performing the recited function and structural functional equivalents thereof. Therefore, it is to be understood that the foregoing is illustrative of the present invention and is not to be construed as limited to the specific embodiments disclosed, and that modifications to the disclosed embodiments, as well as other embodiments, are intended to be included within the scope of the claims appended hereto.