Multicast buffered switch and method for operating a multicast buffered switch

• US 6,940,856 B2
• Filed: 03/05/2001
• Issued: 09/06/2005
• Est. Priority Date: 03/05/2001
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Vu, Chien Dinh
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): Fox, Jamal A.
• Application Number:
  US09/799,854
• Publication Number:
  US 20040202162A1
• Time in Patent Office: 1,646 Days
• Field of Search: 370/124, 370/489, 370/427, 370/398, 370/387, 370/388, 370/390, 370/389, 370/351, 370/360, 370/362, 370/363, 370/364, 370/365, 370/366, 370/471, 370/412, 370/413, 370/419, 370/420, 370/395.1, 370/396, 370/400, 370421-423, 370/440, 370/438, 370/67, 370/85.9, 370/85.13, 370/85.1
• US Class Current: 370/390
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• CPC Class Codes: H04L 49/203 ATM switching fabrics with multicast or broadcast capabilities
• CPC Class Codes: H04L 49/309 Header conversion, routing tables or routing tags

Abstract

In an NXN switch a plurality of buses interconnect 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 selected ones of the buses along with a multicast vector which identities which of the output modules is to process the cell on a bus. The output modules examine the multicast vector and process the cell (table lookup) if selected In the multicast vector. If an output module is unable to process a required cell (successful table lockup) it sets a retry vector resident on the bus 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 a bus in a subsequent selection of that input module.

Claims

1. A multicast buffered switch comprising:

plurality of separate buses;

a plurality of input modules each connected between a different one of a plurality of input lines, over which transmission cells including a payload are received;

a common controller coupled to the plurality of buses and managing the plurality of buses in such a way that control information and a received cell inserted by an input module is sequentially transmitted on different ones of the plurality of separate buses; and

a plurality of output modules each connected to a different output line and the plurality of separate buses for receiving a bus contents and comparing portions thereof to stored routing information to determine if the cell payload is to be retransmitted over its connected output line.

2. A multicast buffered switch as set forth in claim 1 in which the control information includes unique information identifying the input module which placed the cell and control information on the bus.

3. A multicast buffered switch comprising:

a multiconductor bus;

a plurality of input modules each connected between a different one of a plurality of input lines, over which transmission cells including a payload are received, and the multiconductor bus for sequentially transferring, a received cell and control information inserted by the input module, to the bus; and

,

a plurality of output modules each connected to a different output line and the multiconductor bus for receiving the bus contents and comparing portions thereof to stored routing information to determine if the cell payload is to be retransmitted over its connected output line wherein said control information includes unique information identifying the input module which placed the cell and control information on the bus and a multicast vector identifying which of the output modules are required to process the cell on the bus.

4. A multicast buffered switch as set forth in claim 3 in which the multicast vector identifies all of the output modules the first time an input module places a cell on the bus.

5. A multicast buffered switch as set forth in claim 3 in which each of the output modules sets a unique assigned position in a retry vector resident on the bus for indicating the successful processing of a cell received on the bus.

6. A multicast buffered switch as set forth in claim 5 in which a selected input module examines the retry vector to determine if any output modules failed to successfully process a cell, modifies the multicast vector to indicate only those output modules which failed to successfully process the cell and retransmits the cell with the modified retry vector when the input module is selected at a subsequent time and discards the cell if no output modules indicate a failure to process the cell.

7. A multicast buffered switch comprising:

a plurality of input modules each connected to an input line over which transmission cells including a payload are received;

a plurality of output modules each connected to an output line over which selected cells received at the input modules are to be transmitted;

a multiconductor bus interconnecting the input and output modules;

each of the input modules including a first means for storing received cells, a second means for placing, in a predetermined sequence, a received transmission cell, an ID identifying the input module and a multicast vector which includes an indicia indicating to each of the outputs when a transmission cell requires processing on the multiconductor bus; and

,

each of the output modules includes means for examining the multicast vector to determine if the output module is to process the cell on the bus and comparing selected portions of the bus contents including the ID placed on the multiconductor bus by the input modules to stored routing information for determining if the cell being processed is to be retransmitted by the output module over its connected output.

8. A multicast buffered switch as set forth in claim 7 in which the multicast vector identifies all of the output modules the first time an input module places a specific cell on the bus.

9. A multicast buffered switch as set forth in claim 8 in which each of the output modules includes a second means for setting a unique assigned position in a retry vector resident on the bus for indicating the successful processing of a cell received on the bus.

10. A multicast buffered switch as set forth in claim 9 in which a selected input module includes a third means for examining the retry vector to determine if any output modules failed to successfully process a specific cell, modifies the multicast vector to indicate only those output modules which failed to successfully process the specific cell and retransmits the specific cell, the input modules ID and the modified retry vector when the input module is selected at a subsequent time and discards the cell if no output modules indicate a failure to process the cell.

11. A multicast buffered switch comprising:

a plurality of input modules each connected to an input line over which transmission cells including data are received;

a plurality of output modules each connected to an output line over which selected cells received at the input modules are to be transmitted;

a multiconductor bus interconnecting the input and output modules;

each of the input modules including first means responsive to a unique selection signal on the bus for placing on the bus a received transmission cell, an ID identifying the input module and a multicast vector which includes an indicia for indicating to each of the output modules when a transmission cell on the multiconductor bus requires processing;

each of the output modules including means responsive to the multicast vector for comparing selected portions of the transmission cell and the ID placed on the multiconductor bus by the input modules to stored routing information for determining if the cell is to be transmitted by the output module over its connected output, queuing the cell for transmission over the connected output and setting a unique assigned position in a retry vector resident on the bus for indicating the successful or unsuccessful processing of a cell received on the bus; and

,

each selected input module including second means for examining the retry vector to determine if any output modules failed to successfully process a specific cell, for modifying the multicast vector to indicate only those output modules which failed to successfully process the specific cell and for retransmitting the specific cell, the input modules ID and the modified retry vector when the input module is selected at a subsequent time.

12. In 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 a method for operating the switch including:

providing a single stage switching system including a plurality of independent buses for interconnecting components of said switch;

at the input module, receiving cells and storing each of the received cells and periodically placing a stored cell on a selected one of the plurality of buses and control information on another of the plurality buses wherein the control information and the stored cell are being placed sequentially on respective buses; and

at each output module, receiving the control information, comparing portions of the control information to stored routing information and queuing the received cell for transmission over its connected output when there is a successful comparison.

13. The method set forth in claim 12 in which the control information includes unique information identifying the input module which placed the cell and control information on the bus.

14. In 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 a method for operating the switch including the following steps;

at the input module receiving cells and storing each of the received cells and periodically placing a stored cell and control information on the bus; and

at each output module receiving the bus contents, comparing portions of the contents to stored routing information and queuing the received cell for transmission over its connected output when there is a successful comparison, wherein the control information includes unique information identifying the input module which placed the cell and control information on the bus and a multicast vector identifying which of the output modules are required to process the cell on the bus.

15. The method set forth in claim 14 in which the multicast vector identifies all of the output modules the first time an input module places a cell on the bus.

16. The method set forth in claim 14 in which each of the output modules sets a unique assigned position in a retry vector resident on the bus for indicating the successful processing of a cell received on the bus.

17. The method set forth in claim 16 in which a selected input module examines the retry vector to determine if any output modules failed to successfully process a cell, modifies the multicast vector to indicate only those output modules which failed to successfully process the cell, retransmits the cell with the modified multicast vector when the input module is selected at a subsequent time and discards the cell if no output module indicates a failure to process the cell.

18. In a multicast buffered switch which includes a plurality of input modules each connected to an input line over which transmission cells including data are received, a plurality of output modules each connected to an output line over which selected cells received at the input modules are to be retransmitted, and a multiconductor bus interconnecting the input and output modules a method of operating the switch including the following steps:

selecting each of the input modules in a predetermined sequence, placing a received transmission cell, an ID identifying the input module and a multicast vector which includes an indicia indicating to each of the outputs when a transmission cell on the multiconductor bus requires processing; and

,

at each of the output modules examining the multicast vector to determine if the cell is to be processed, comparing selected portions of the transmission cell and the ID placed on the multiconductor bus by the input modules to stored routing information to determining if the cell is to be transmitted by the output module over its connected output.

19. The method set forth in claim 18 in which the multicast vector identifies all of the output modules the first time an input module places a specific cell on the bus.

20. The method set forth in claim 19 in which at each of the output modules a unique assigned bit position in a retry vector resident on the bus is set to indicate the successful processing of a cell received on the bus.

21. The method set forth in claim 20 in which at a selected input module the retry vector is examined to determine if any output modules failed to successfully process a specific cell, the multicast vector is modified to indicate only those output modules which failed to successfully process the specific cell, and the specific cell, the input modules ID and the modified retry vector are transmitted over the bus when the input module is selected at a subsequent time and discards the cell if no output module indicated a failure to process the cell.

22. In a multicast buffered switch including a plurality of input modules each connected to an input line over which transmission cells including data are received, a plurality of output modules each connected to an output line over which selected cells received at the input modules are to be retransmitted and a multiconductor bus interconnecting the input and output modules a method of transferring transmission cells received at an input module to selected output modules including the following steps:

at each of the input modules in a predetermined sequence placing on the bus a received transmission cell, an ID identifying the input module and a multicast vector which includes an indicia indicating to each of the outputs when a transmission cell on the multiconductor bus requires processing;

at each of the output modules examining the multicast vector and in response thereto comparing selected portions of the transmission cell and the ID placed on the multiconductor bus by the input modules to stored routing information for determining if the cell is to be transmitted by the output module over its connected output, queuing the cell for transmission over the connected output if selected and setting a unique assigned bit in a retry vector resident on the bus for indicating the successful or unsuccessful processing of a cell received on the bus; and

,

at each selected input module examining the retry vector to determine if any output modules failed to successfully process a specific cell, modifying the multicast vector to indicate only those output modules which failed to successfully process the specific cell and retransmitting the specific cell, the input modules ID and the modified retry vector when the input module is selected at a subsequent time and discarding the cell if no output modules indicate a failure to process the cell.

23. The method set forth in set forth in claim 22 in which the transmitted multicast vector identifies all of the output modules the first time a specific cell is transmitted on the bus.

24. In 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 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 a method for operating the switch including the following steps:

at each said input module;

receiving transmission cells, adding a unique ID to the received cells and storing the updated received cells,

sequentially selecting the input modules and at each selected input module placing a stored received cell and a multicast vector which includes a unique indicia indicating when a cell requires processing by an output module on the bus,

At each said output module;

examining the multicast vector to determine if the output module is required to process the cell, if required comparing a portion of the cell to a locally stored routing table to determine if the cell is to be routed to the connected output line and entering a predetermined status indicia in a retry vector resident on the bus when the output module is unable to process a cell required to be transmitted on its connected output; and

,

at said input module;

examining said retry vector, modifying the multicast vector to indicate only those output modules which set a predetermined status in the retry vector, and placing that cell and the modified multicast vector on the bus when selected at a later time and discarding the cell when no output modules have set the predetermined status in the retry vector.

25. In a multicast buffered switch including a plurality of input modules (IM'"'"'s) each connected to an input line over which transmission cells each including a header and a payload are received, a plurality of output modules (OM'"'"'s) each connected to an output line over which selected cells received at the input modules are to be re transmitted with a modified header, and a multiconductor bus interconnecting the IM and OM modules and having an arbitration means for periodically generating unique bus selection signals for sequentially selecting the IM'"'"'s a method for operating the switch including the following steps;

at each of the IMs receiving the cells, adding a unique ID identifying the input module to the header and storing the modified cells in a FIFO buffer, and responsive to a predetermined periodic selection signal from the arbitration means generating a multicast vector which includes an indicia indicating to each of the outputs when a transmission cell requires processing on the multiconductor bus and placing the multicast vector and the modified cell header of the oldest stored cell in the FIFO buffer on the bus when selected and the payload associated with that cell on the bus in the next subsequent bus period; and

,

at each of the OM'"'"'s examining the multicast vector to determine if the OM is to process the cell on the bus and comparing selected portions of the header to stored routing information to determine if the cell being processed is to be retransmitted by the OM over its connected output and selecting and storing the payload on the bus in the next period and a new header for retransmission at a later time when the cell is selected for processing.

26. The method set forth in claim 25 in which the multicast vector identifies all of the OM'"'"'s the first time a specific cell is placed on the bus.

27. The method set forth in claim 26 in which each of the OM'"'"'s sets a unique assigned position in a retry vector resident on the bus in the bus period immediately following the period including the header for indicating the successful processing of a cell received on the bus.

28. The method set forth in claim 27 in which a selected IM examins the retry vector in the bus period which includes the cell payload to determine if any output modules failed to successfully process a specific cell, modifies the multicast vector to indicate only those output modules which failed to successfully process the specific cell and retransmits the specific cell and the modified retry vector when the input module is selected at a subsequent bus period and discards the cell if no output modules indicate a failure to process the cell.

29. In a multicast buffered ATM switch including a plurality of input modules each connected to an input line over which transmission cells each including a header and a payload are received, a plurality of output modules each connected to an output line over which selected cells received at the input modules are to be retransmitted a multiconductor bus interconnecting the input and output modules and a bus arbitration means for periodically generating unique bus selection signals for sequentially selecting the input modules a method for operating the switch including the following steps:

at each of the input modules storing received transmission cells in a FIFO buffer and replacing the header error correction (HEC) byte included in the received ATM cell header with a unique ID identifying the input module, generating a multicast vector which includes a unique indicia for indicating to each of the output modules when a transmission cell on the multiconductor bus requires processing, and responsive to a predetermined unique periodic bus selection signal placing the modified header and the multicast vector on predetermined positions in the multiconductor bus and the cell payload in predetermined positions in the bus in the very next bus period; and

,

At each of the output modules examining the multicast vector in each bus period to determine if the output module is required to process the cell, comparing selected portions of the modified header on the multiconductor bus to stored routing information for determining if that cell is to be retransmitted by the output module over its connected output, swapping the cell header if the output module is required to retransmit the cell over the connected output, setting a unique assigned position in a retry vector resident on the bus for indicating the successful or unsuccessful processing of a cell received on the bus, and inserting the swapped header and the payload on the bus in the next bus period in a retransmission queue for subsequent transmission; and

at each selected input module examining the retry vector to determine if any output modules failed to successfully process a specific cell, modifying the multicast vector to indicate only those output modules which failed to successfully process the specific cell and resubmitting the specific cell with the modified multicast vector on the bus when the input module is next selected.

30. The method Set forth in claim 29 in which the input module sets the multicast vector to indicate all output modules the first time a received cell is placed on the bus and discards the cell when the retry vector indicates that no output modules signaled an inability to successfully process a cell and selects the next cell in the FIFO buffer for retransmission.

31. A multicast buffered switch comprising:

a plurality of input modules (IM'"'"'s) each connected to an input line over which transmission cells each including a header and a payload are received;

a plurality of output modules (OM'"'"'s) each connected to an output line over which selected cells received at the IM'"'"'s are to be re transmitted with a modified header;

a multiconductor bus interconnecting the IM and OM modules, said bus including an arbitration means for periodically generating unique bus selection signals for sequentially selecting the IM'"'"'s;

each of the IM'"'"'s including a first IM means for receiving the cells, adding a unique ID identifying the input module to the header and storing the modified cells in a FIFO buffer, and second IM means responsive to a predetermined periodic selection signal from the arbitration means for placing the modified cell header of the oldest stored cell in the FIFO buffer and a multicast vector which includes an indicia indicating to each of the outputs when a transmission cell on the multiconductor bus requires processing and the payload associated with that cell on the bus in the next subsequent bus period; and

,

each of the OM'"'"'s includes first OM means for examining the multicast vector to determine if the OM is to process the cell on the bus and second OM means for comparing selected portions of the header to stored routing information for determining if the cell being processed is to be retransmitted by the OM over its connected output and third OM means responsive to the second OM means for selecting and storing the payload on the bus in the next period and a new header for retransmission at a later time.

32. A multicast buffered switch as set forth in claim 31 in which the multicast vector identifies all of the OM'"'"'s the first time an input module places a specific cell on the bus.

33. A multicast buffered switch as set forth in claim 32 in which each of the OM'"'"'s includes a fourth OM means for setting a unique assigned position in a retry vector resident on the bus in the bus period immediately following the period including the header for indicating the successful processing of a cell received on the bus.

34. A multicast buffered switch as set forth in claim 33 in which a selected IM includes a third IM means for examining the retry vector in the bus period which includes the cell payload to determine if any output modules failed to successfully process a specific cell, modifies the multicast vector to indicate only those output modules which failed to successfully process the specific cell and retransmits the specific cell and the modified retry vector when the input module is selected in a subsequent bus period and discards the cell if no output modules indicate a failure to process the cell.

35. A multicast buffered ATM switch comprising:

a plurality of input modules each connected to an input line over which transmission cells including data are received;

a plurality of output modules each connected to an output line over which selected cells received at the input modules are to be retransmitted;

a multiconductor bus interconnecting the input and output modules, said bus including an arbitration means for periodically generating unique bus selection signals for sequentially selecting the input modules;

each of the input modules including first means for storing received transmission cells each of which includes a header and a payload in a FIFO buffer and for replacing the header error correction (HEC) byte included in the received ATM cell header with a unique ID identifying the input module, second means for generating a multicast vector which includes an indicia for indicating to each of the output modules when a transmission cell on the multiconductor bus requires processing, and third means responsive to a predetermined unique bus selection signal for placing the modified header and the multicast vector on predetermined positions in the multiconductor bus when selected by the arbitration means arid the cell payload in predetermined positions in the bus in the very next bus period; and

,

each of the output modules including first means responsive to the multicast vector in each bus period for comparing selected portions of the modified header on the multiconductor bus to stored routing information for determining if that cell is to be retransmitted by the output module over its connected output, second means for swapping the cell header if the output module is required to retransmit the cell over the connected output, third means for setting a unique assigned position in a retry vector resident on the bus for indicating the successful or unsuccessful processing of a cell received on the bus, and fourth means inserting the swapped header and the payload on the bus in the next bus period in a retransmission queue for subsequent transmission; and

,

each selected input module second means examining the retry vector to determine if any output modules failed to successfully process a specific cell, modifying the multicast vector to indicate only those output modules which tailed to successfully process the specific cell and resubmitting the specific cell with the modified multicast vector on the bus when the input module is next selected.

36. The multicast buffered ATM switch set forth in claim 35 in which the second means of the input module sets the multicast vector to indicate all output modules the first time a received cell is placed on the bus and discards the cell when the retry vector indicates that no output modules signaled an inability to successfully process a cell and selects the next cell in the FIFO buffer for retransmission.