MULTI-PLANE CELL SWITCH FABRIC SYSTEM

• US 20090129393A1
• Filed: 11/19/2008
• Published: 05/21/2009
• Est. Priority Date: 11/21/2007
• Status: Active Grant

• Current Assignee: Alaxala Networks Corporation (Fortinet Inc.)
• Original Assignee: Alaxala Networks Corporation (Fortinet Inc.)
• Inventors: Kimura, Isao, Yamamoto, Mitsuo, OKUNO, Michitaka
• Granted Patent: US 7,907,606 B2
• Time in Patent Office: Days
• US Class Current: 370/395.600
• CPC Class Codes: H04L 49/1523 Parallel switch fabric planes
• CPC Class Codes: H04L 49/252 Store and forward routing
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/3072 Packet splitting
• CPC Class Codes: H04L 49/503 Policing
• CPC Class Codes: H04L 49/552 by ensuring the integrity of packets received through redundant connections

Abstract

Cells which arrive in random sequence from the asynchronously operating exchange parts are restored into the original by a small amount of hardware. Distributing parts as inputs of a switch fabric manage serial numbers continuous for each destination. The distributing part divides an inputted variable length packet into fixed length cells, adds serial numbers corresponding to destinations to the cells, and outputs the cells to the exchange parts. The respective exchange parts deliver the cells to the objected destinations. Alignment parts as outputs of the switch fabric classify the reception cells by the number of the distributing part, and compare an expected serial number managed by the alignment part with a serial number of the destination (alignment part) of the reception cell. An identical one is stored in an aligned FIFO queue, and cells of from a packet start cell to a packet end cell are taken out.

Claims

1. A multi-plane cell switch fabric system comprising:

a plurality of distributing parts as inputs of the multi-plane cell switch fabric system;

a plurality of alignment parts as outputs of the multi-plane cell switch fabric system; and

a plurality of exchange parts to respectively and asynchronously perform data exchange from the distributing parts to the alignment parts,

wherein the distributing part includes;

a mechanism that divides an inputted variable length packet into fixed length cells, adds a head to a packet start cell, adds a tail to a packet end cell, and adds, to all the cells, transmission source identifiers to indicate its own distributing parts and destination information indicating one or a plurality of alignment parts as destinations;

a mechanism of managing that manages, for each of the alignment parts as the destinations, serial numbers to indicate sequence of the cells for restoring the packet from the cells;

a mechanism of adding that refers to the managing mechanism based on destination information, and adds the one or the plurality of serial numbers corresponding to the destinations to the cells; and

a mechanism that distributes and outputs the cells to the plurality of exchange parts,

further wherein the alignment part includes;

a mechanism that classifies the received cells for the respective distributing parts of the transmission sources in accordance with the transmission source identifiers of the cells received through the plurality of exchange parts;

a mechanism of aligning that aligns, with respect to the cells classified for the respective distributing parts, the cells in accordance with the serial numbers added to the cells and corresponding to its own destination;

aligned queues that are for the respective distributing parts and store the aligned cells in sequence; and

a mechanism that selects, among the aligned cues, the aligned queue storing the packet end cell to which the tail is added, takes out cells of from the packet start cell to which the head is added to the packet end cell to restore the packet, and outputs the packet.

3. The multi-plane cell switch fabric system according to claim 1, wherein the mechanism of aligning includes:

queues that store cells and are provided for the respective distributing parts and the respective exchange parts;

an expected serial number manager that is for aligning cells in accordance with serial numbers, stores a previously set initial value, and manages expected serial numbers for the respective distributing parts as the transmission sources; and

a comparison section that compares, with respect to cells stored in each of the queues, serial numbers included in the cells with expected serial numbers of the expected serial number manager, takes out identical cells from the queue, stores them in the aligned queue, increases the expected serial number of the expected serial number manager, and returns the expected serial number to zero or the initial value when it reaches a maximum value.

4. The multi-plane cell switch fabric system according to claim 3, wherein

each of the exchange parts includes a mechanism to adjust an output for each destination in cell units while sequence of cells from the same distributing part is kept, and

the comparison section of the alignment part compares, with respect to the start cell of the queue of each of the exchange parts, the serial number of the start cell with the expected serial number of the expected serial number manager.

5. The multi-plane cell switch fabric system according to claim 1, wherein the plural serial numbers are added to divided cells.

6. The multi-plane cell switch fabric system according to claim 1, wherein

the destination information is a destination bitmap in which each bit corresponds to the alignment part, and which indicates that the cell is to be transmitted to the alignment part corresponding to an effective bit, and

a relative position relation of effective bits corresponds to a storage position of plurality of serial numbers added to the cells.

7. The multi-plane cell switch fabric system according to claim 1, wherein

the number of serial numbers capable of being added to one cell is previously determined,

when the number of destinations in a multicast packet exceeds the number of serial numbers capable of being added, the distributing part divides the destination information to make the number of destinations of one cell not larger than the number of serial numbers capable of being added, makes copies of the cell, the number of which is the division number of the destination information, and adds, to each of the cells after copying, the divided destination information and the serial number corresponding to each destination after the division.

8. The multi-plane cell switch fabric system according to claim 1, wherein

when the destination is congested and the cell divided by the distributing part can not transmitted in the middle of transmission to the alignment part of the destination, the distributing part divides a packet to another destination not including the destination into cells and starts transmission.

10. The multi-plane cell switch fabric system according to claim 1, wherein

the mechanism of managing in the distributing part further manages, with respect to packets which destination information including plural destinations is previously specified pattern, serial numbers for the specified pattern indicating sequence of cells for restoring the packet,

the mechanism of adding which adds the serial number to the cell in the distributing part refers to, when the destination information of the inputted packet is the previously specified pattern, the mechanism of managing and adds the serial number for the specified pattern to the cell,

the alignment part separately manages the expected value of the serial number when the destination is the specified pattern and the expected value of the serial number when the destination is not the specified pattern, and aligns the cells in accordance with the serial number added to the cell separately according to whether the destination is the specified pattern or not.

11. The multi-plane cell switch fabric system according to claim 10, wherein the mechanism of aligning includes:

queues that stores cells and are provided correspondingly to the respective distributing parts and the respective exchange parts;

an expected serial number manager that stores a previously set initial value, and manages an expected serial number for a first flow and an expected serial number for a second flow, which are for aligning the cells in accordance with the serial numbers, and

a comparison section that determines whether destination information of the cell stored in each of the queues is the previously specified pattern or not, and (a) in a case of the pattern, compares the serial number included in the cell with the expected serial number for the first flow in the expected serial number manager, takes out the identical cell from the queue, stores it in the aligned queue for the first flow, increases the expected serial number for the first flow in the expected serial number manager, and returns the expected serial number to zero or the initial value when it reaches a maximum value, and (b) in a case of not the pattern, compares the serial number included in the cell with the expected serial number for the second flow in the expected serial number manager, takes out the identical cell from the queue, stores it in the aligned queue for the second flow, increases the expected serial number for the second flow in the expected serial number manager, and returns the expected serial number to zero or the initial value when it reaches a maximum value.

13. The multi-plane cell switch fabric system according to claim 11, wherein

each of the exchange parts includes a mechanism to adjust an output for each destination in cell units while sequence of cells from the same distributing part is kept, and

the comparison section of the alignment part compares, with respect to the start cell of the queue of each of the exchange parts, the serial number of the start cell with the expected serial number for the first or the second flow in the expected serial number manager.

2. A multi-plane cell switch fabric system comprising:

a plurality of distributing parts as inputs of the multi-plane cell switch fabric system;

a plurality of alignment parts as outputs of the multi-plane cell switch fabric system; and

a plurality of exchange parts to respectively and asynchronously perform data exchange from the distributing parts to the alignment parts,

wherein the distributing part includes;

a mechanism that divides an inputted variable length packet into fixed length cells, adds a head to a packet start cell, adds a tail to a packet end cell, and adds, to all the cells, transmission source identifiers to indicate its own distributing part and destination information indicating one or a plurality of alignment parts as destinations;

a mechanism of managing serial numbers that, with respect to a destination bitmap in which each bit corresponds to the alignment part, a cell is transmitted to the alignment part whose bit value 1, and the cell is not transmitted to the alignment part whose bit value is 0, combines two bits corresponding to previously determined two destinations, previously defines three kinds of combination patterns of 01, 10 and 11 among combination patterns of the two bits as flows to the two destinations, and manages serial numbers indicating sequence of cells corresponding to the three kinds of flows for each of the combinations of the two destinations,

a mechanism that combines two bits corresponding to the previously determined two destinations of the destination bitmap, refers to the mechanism of managing serial numbers to add the one or the plurality of serial numbers corresponding to the flows defined by the combination of the two destinations and the combination pattern of the two bits to the cell, and

a mechanism that distributes and outputs the cells to the plurality of exchange parts,

further wherein the alignment part includes;

a mechanism that classifies the received cells for the respective distributing parts of the transmission sources in accordance with the transmission source identifiers of the cells received through the plurality of exchange parts;

a mechanism of aligning that refers to the destination bitmap, determines, based on the previously determined combination of two bits including a bit corresponding to its own alignment part, whether a flow is a first flow of the combination pattern of 01 or 10 or a second flow of the combination pattern of 11, and aligns the cells in accordance with the serial numbers added to the cells for each of the first flow and the second flow,

aligned queues that stores the aligned cells in sequence and is for the respective distributing parts and the respective flows, and

a mechanism that selects the aligned queue storing the packet end cell among the aligned queues, takes out cells of from the packet start cell to the packet end cell, restores the packet, and outputs the packet.

9. The multi-plane cell switch fabric system according to claim 2, wherein

in the alignment part, after a cell other than the packet end including an expected serial number arrives from an arbitrary distributing part, when a cell including an expected subsequent serial number does not arrive from the same distributing part even when a previously determined period elapses, or a cell other than the expected subsequent serial number arrives from all the exchange parts with respect to the same distributing part, the expected subsequent serial number is neglected, the expected serial number is increased, and when the expected serial number reaches a maximum value, the expected serial number is returned to zero or an initial value, and a packet in which the cell of the neglected serial number drops out is processed as an error packet.

12. The multi-plane cell switch fabric system according to claim 2, wherein the mechanism of aligning includes:

queues that stores cells and are provided correspondingly to the respective distributing parts and the respective exchange parts;

an expected serial number manager that stores a previously set initial value, and manages an expected serial number for a first flow and an expected serial number for a second flow, which are for aligning the cells in accordance with the serial numbers, and

a comparison section refers to the destination bitmap stored in each of the queues, determines whether a flow is the first flow or the second flow based on the previously determined combination of the two bits including the bit corresponding to its own alignment part, and (a) in a case of the first flow, compares the serial number included in the cell with the expected serial number for the first flow in the expected serial number manager, takes out the identical cell from the queue, stores it in the aligned queue for the first flow, increases the expected serial number for the first flow in the expected serial number manager, and returns the expected serial number to zero or the initial value when it reaches a maximum value, and (b) in a case of the second flow, compares the serial number included in the cell with the expected serial number for the second flow in the expected serial number manager, takes out the identical cell from the queue, stores it in the aligned queue for the second flow, increases the expected serial number for the second flow in the expected serial number manager, and returns the expected serial number to zero or the initial value when it reaches a maximum value.

14. The multi-plane cell switch fabric system according to claim 2, wherein

each of M (M is an integer of 2 or more) distributing parts includes j (j is an integer of 2 or more) input ports,

each of N (N is an integer of 2 or more) alignment parts includes i (i is an integer of 2 or more) output ports,

the distributing part inputs a packet including first destination bitmap of N×

i bits indicating the alignment part as the destination and the output port, takes a logical sum of the first destination bitmap for every i bits corresponding to the alignment part to generate an N-bit second destination bitmap, adds the second destination bitmap to the divided cell and outputs it to the exchange part,

the exchange part transmits the cell to the alignment part in accordance with the second destination bitmap, and

the alignment part aligns the received cells to restore the packet, refers to the first destination bitmap of N×

i bits included in the restored packet, determines one or a plurality of output destinations among the i output ports of its own alignment part, and outputs the restored packet.

15. A multi-plane cell switch fabric system including a plurality of exchange parts to respectively and asynchronously perform data exchange, wherein

a distributing part as an input of the multi-plane cell switch fabric system includes:

a mechanism that divides a variable length packet into fixed length cells and adds a destination bitmap indicating an identifier of the distributing part and an alignment part of a destination to the cell;

a mechanism that manages serial numbers indicating sequence of the cells for each of destinations;

a mechanism that refers to the managing mechanism and adds a plurality of serial numbers corresponding to the destinations to the cells within a specified range; and

a mechanism that outputs the cells to the exchange part,

further wherein

in the alignment part receiving the cells via the respective exchange parts of the multi-plane cell switch fabric system, among the plurality of serial numbers added to the cells, the serial number corresponding to its own alignment part is identified, and the cells are aligned in accordance with the serial number.

16. A multi-plane cell switch fabric system including a plurality of exchange parts to respectively and asynchronously perform data exchange, wherein

a distributing part as an input of the switch fabric includes:

a mechanism that divides a variable length packet into fixed length cells and adds a destination bitmap indicating an identifier of the distributing part and an alignment part of a destination to the cell;

a mechanism that, with respect to the destination bitmap in which each bit corresponds to the alignment part and a cell is transmitted to the alignment part whose bit value 1, represents two arbitrary destinations in two bits, defines three kinds of 01, 10 and 11 as combinations of the two bits as flows to the two destinations, and manages serial numbers indicating sequence of cells for each of the flows;

a mechanism that adds a plurality of serial numbers corresponding to the destinations within a specified range; and

a mechanism that outputs the cells to the exchange part,

further wherein

each of the exchange parts of the multi-plane cell switch fabric system includes a mechanism that adjusts an output for each of the destinations in cell units while transmission sequence between cell groups of the same transmission source is kept, and

in the alignment part receiving the cells via the respective exchange parts of the multi-plane cell switch fabric system, the cells are aligned in accordance with the serial numbers.