Scaleable multicast ATM switch

A switch for routing cells from a plurality of input ports to a plurality of output ports, the switch comprising:

• a) a plurality of input port controllers, each of the plurality of input port controllers
• i) having a cell input for receiving cells from an associated one of the plurality of input ports,
• ii) having a plurality of feedback inputs,
• iii) having a cell output,
• iv) terminating a line of the associated one of the plurality of input ports,
• v) buffering a cell received at the associated one of the plurality of input ports,
• vi) storing a local priority value based on information included in the cell received at the associated one of the plurality of input ports,
• vii) storing a multicast pattern based on information included in the cell received at the associated one of the plurality of input ports,
• viii) comparing each of a plurality of feedback priority values, provided at the plurality of feedback inputs, with the stored local priority value to form a set of comparison results,
• ix) updating the multicast pattern based on the set of comparison results, and
• x) applying a next one of cells received at the associated one of the plurality of input ports and the cell buffered, to the cell output based on the updated multicast pattern;
• b) a plurality of multicast grouping networks, each of the plurality of multicast grouping networks including a plurality of inputs coupled with the cell output of a corresponding one of the plurality of input port controllers, a plurality of outputs, and a plurality of routing modules for routing cells to one of a plurality of outputs, each of the plurality of routing modules
• i) having a plurality of inputs, each of the plurality of inputs coupled with a corresponding one of the plurality of inputs of an associated one of the plurality of multicast grouping networks,
• ii) having an address generator for generating addresses corresponding to a group of associated output ports,
• iii) having an array of switch elements, each of the switch elements having a first input, a second input, a first output and a second output,
• wherein the array of switch elements includes an first row of switch elements, a last row of switch elements, a first column of switch elements, a last column switch elements, and an internal array of switch elements not belonging to any one of the first row, the last row, the first column, and the last column,
• each of the switch elements of the first row having its second input provided with one of the addresses generated by the address generator and having its second output coupled with the second input of a corresponding switch element in an adjacent row,
• each of the switch elements of the first column having its first input coupled with the cell output of an associated input port controller and having its first output coupled with the first input of a corresponding switch element in an adjacent column,
• each of the switch elements of the last row having its second output coupled, via an associated one of the outputs of the routing module, with an associated one of the plurality of outputs of the associated one of the plurality of multicast grouping networks, and having its second input coupled with the second output of an associated switch element in an adjacent row,
• each of the switch elements of the last column having its first input coupled with the first output of an associated switch element in an adjacent column,
• each of the switch elements belonging to the internal array having
• its first input coupled with the first output of an adjacent switch element of a preceding column, and
• its second input coupled with the second output of an adjacent switch element of a preceding row,
• wherein each of the switch elements have a toggle state in which its first input is coupled with its second output and its second input is coupled with its first output, and have a cross state in which its first input is coupled with its first output and its second input is coupled with its second output, and
• wherein each of the switch elements assume the toggle state when address information of a cell applied at its first input matches address information applied to its second input and priority information of the cell applied at its first input is higher than priority information applied at its second input, and otherwise assumes the cross state;
• and
• c) a plurality of concentration modules each of the plurality of concentration modules
• i) including a plurality of inputs coupled with associated ones of the outputs of each of the multicast grouping networks,
• ii) having an array of switch elements, each of the switch elements having a first input, a second input, a first output and a second output,
• wherein the array of switch elements includes an first row of switch elements, a last row of switch elements, a first column of switch elements, a last column switch elements, and an internal array of switch elements not belonging to any one of the first row, the last row, the first column, and the last column,
• each of the switch elements of the first row having its second output coupled with the second input of a corresponding switch element in an adjacent row,
• each of the switch elements of the first column having its first input coupled with an associated one of the plurality of inputs of that concentration module and having its first output coupled with the first input of a corresponding switch element in an adjacent column,
• each of the switch elements of the last row having its second output coupled with an associated one of the plurality of outputs of the concentration module, and having its second input coupled with the second output of an associated switch element in an adjacent row,
• each of the switch elements of the last column having its first input coupled with the first output of an associated switch element in an adjacent column,
• the second output of a switch element in both the last row and last column applying a feedback priority signal to an associated one of the plurality of feedback inputs in each of the plurality of input port controllers,
• each of the switch elements belonging to the internal array having
• its first input coupled with the first output of an adjacent switch element of a preceding column, and
• its second input coupled with the second output of an adjacent switch element of a preceding row,
• wherein each of the switch elements have a toggle state in which its first input is coupled with its second output and its second input is coupled with its first output, and have a cross state in which its first input is coupled with its first output and its second input is coupled with its second output, and
• wherein each of the switch elements assume the toggle state when priority information of the cell applied at its first input is higher than priority information applied at its second input, and otherwise assumes the cross state.

In a multicast switch having a plurality of input port controllers for receiving cells, the cells having an associated priority value and a multicast bit pattern, for buffering a head-of-line cell, and for transmitting the cells, and a plurality of routing modules for routing incoming cells, transmitted from each of the plurality of input port controllers, to an associated one of K groups of output ports and for providing a feedback priority value based on a priority value associated with a lowest priority cell passed to the associated group of output ports, a method for resolving output port contention comprising steps of:

• a) setting an output group index to one and setting a resend bit to a low state;
• b) determining whether the output group index is less than or equal to the total number K of output groups;
• c) if the output group index is determined to be less than or equal to the total number of output groups in step b), performing sub-steps of
• i) determining whether a bit of the multicast pattern of the head-of-line cell, associated with the output group index, is set to a high state,
• ii) if the bit of the multicast pattern of the head-of-line cell, associated with the output group index, is not set to the high state
• incrementing the output group index by one, and
• repeating step (b);
• iii) if the bit of the multicast pattern of the head-of-line cell, associated with the output group index, is set to the high state,
• determining whether a the priority value of the head-of-line cell is less than or equal to the feedback priority value from a routing module associated with the output group index,
• if the priority value of the head-of-line cell is less than or equal to the feedback priority value from the routing module associated with the output group index,
• setting the bit of the multicast pattern of the head-of-line cell, associated with the output group index, to the low state,
• incrementing the output group index by one, and
• repeating step (b),
• if the priority value of the head-of-line cell is not less than or equal to the feedback priority value from the routing module associated with the output group index,
• setting the resend bit to the high state,
• incrementing the output group index by one, and
• repeating step (b);
• and
• d) if the output group index was not determined to be less than or equal to the total number K of output groups in step (b),
• i) determining whether the resend bit is set to the high state or the low state,
• ii) if the resend bit is determined to be set to the high state in step (d)(i), retransmitting the head-of-line cell with the multicast pattern, and
• iii) if the resend bit is determined to be set to the low state in step (d)(i), clearing the head-of-line cell from the buffer, and transmitting and buffering a next in line cell.