Multi-stage interconnection network for high speed packet switching

• US 6,335,930 B1
• Filed: 05/26/1998
• Issued: 01/01/2002
• Est. Priority Date: 05/23/1997
• Status: Expired due to Fees

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Lee, Hee-choul
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): Pham, Brenda H.
• Application Number:
  US09/085,248
• Time in Patent Office: 1,316 Days
• Field of Search: 370/387, 370/388, 370/389, 370/392, 370/394, 370/411, 340/2.21, 340/2.23, 340/2.27, 379/221, 379/273
• US Class Current: 370/387
• CPC Class Codes: H04L 49/101 using crossbar or matrix
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling

Abstract

Disclosed is a multi-stage (NXN) interconnection network which has N input ports and N output ports, for transmitting packets from the input ports to the output ports. The network comprises a multi-stage packet switching network having at least log_MN switching stages; and each of the switching stages having N/2 MXM switching elements, where M is the number of input or output ports of each switching element. Each switching element at each stage comprises X bypassing input ports, M−X input routing ports, X bypassing output ports and M−X output routing ports, where X is 1 or integer of more than 1. The bypassing output ports of each switching element at each stage are connected to bypassing input ports of each of switching elements which are disposed in a same position of a next stage, respectively, and the output routing ports of each switching element at each stage are connected to input routing ports of each of the switching elements at the next stage by means of perfect shuffle connection.

Claims

1. A multi-stage (NXN) interconnection network having N input ports and N output ports, for transmitting packets from the input ports to the output ports, comprising:

a multi-stage packet switching network having at least log_MN switching stages; and

each of the switching stages having N/2 MXM switching elements, where M is the number of input or output ports of each switching element,

wherein each switching element at each stage comprises X bypassing input ports, M−

X input routing ports, X bypassing output ports and M−

X output routing ports, where X is an integer greater than 0, and

wherein each of the bypassing output ports of each switching element at each stage are connected to a corresponding bypassing input port of a corresponding switching element disposed in a same position of a next stage, and each of the output routing ports of each switching element at each stage are connected to one of the input routing ports of one of the switching elements of the next stage by means of a perfect shuffle connection scheme.

2. The multi-stage interconnection network as defined in claim 1, wherein each of said packets comprises a first information field indicative of a routed number of the packet in the network and a second information field indicative of a stayed time in the network.

3. The multi-stage interconnection network as defined in claim 2, wherein each of said switching elements increments the first information field of at least one packet.

4. The multi-stage interconnection network as defined in claim 3, further comprising means for generating information indicative of a minimal routing number related to each switching stage and supplying the information to the switching elements at each stage.

5. The multi-stage interconnection network as defined in claim 4, wherein each of said switching elements permits one packet having a greater value in one of the first and second information fields than another packet to be transmitted to the output routing port indicated by a destination address of the one packet.

6. The multi-stage interconnection network as defined in claim 1, wherein said multi-stage packet switching network includes S_total−

log_MN+1 output access points, where S_total is the number of the switching stages.

7. A packet switch system comprising:

an input module for receiving an original packet from a terminal and converting the original packet into a switching packet by adding to the original packet an information field related to routing;

a multi-stage packet switching network for performing the routing of the switching packet, said network having at least log_MN switching stages and each switching stage having N/2 MXM switching elements, where M is the number of input or output ports of each switching element;

logic circuitry for generating a minimal routing number related to each switching stage and supplying the minimal routing number to the switching elements of each stage; and

an output module for receiving the switching packet from the multistage packet switching network and converting the switching packet into the original packet by removing the information field from the switching packet;

wherein each switching element at each stage comprises X bypassing input ports, M−

X input routing ports, X bypassing output ports and M−

X output routing ports, where X is an integer greater than 0,

wherein each bypassing output port of each switching element at each stage is connected to a bypassing input port of a switching element disposed in a corresponding position in the next stage,

wherein the output routing ports of each switching element at each stage are connected to the input routing ports of each of the switching elements at the next stage of the network by means of a perfect shuffle connection scheme, and

wherein the input routing ports of each switching element at a first stage are connected to the input module.

8. The packet switch system as defined in claim 7, wherein each of the switching elements includes a FIFO buffer for storing a received switching packet.

9. The packet switch system as defined in claim 7, wherein the switching element and the output module are each configured to generate a back-pressuring signal to a switching element disposed at an immediately preceding stage of the network.

10. The packet switch system as defined in claim 7, wherein the output module includes a buffer for storing a switching packet received by the output module.

11. The packet switch system as defined in claim 10, wherein the input module includes a buffer for storing an original switching packet received by the input module.

12. A method for switching packets in a NXN multi-stage interconnection network, the method comprising:

providing a plurality of MXM switching elements, where each switching element has M routing input ports, M routing output ports, a bypass input port and a bypass output port;

organizing the plurality of MXM switching elements into log_MN stages;

connecting each of the routing input ports of the switching elements in a first stage of the log_MN stages to one of the N input ports of the NXN network;

connecting each of the routing output ports of the switching elements in a last stage of the log_MN stages to one of the N input ports of the NXN network;

interconnecting the log_MN stages through a perfect shuffle interconnection scheme of the routing input ports and routing output ports of the switching elements in adjacent stages; and

interconnecting the bypass output port of each switching element to the bypass input port of a corresponding switching element in the adjacent stage.

13. The method of claim 12, further including:

providing each of the packets with a routed number field and an elapsed time field;

incrementing the routed number field of each packet when the packet is routed through one of the switching elements; and

routing a packet having the highest value for one of the routed number field and the elapsed time field to the routing output port indicated by a destination field of the packet.

14. The method of claim 13, further including:

generating a minimum routing number for each stage of the network;

inputting the minimum routing number for each stage into each switching element in the stage; and

discarding each packet received by one of the switching elements where the value of the routed number field of the packet is less than the minimum routing number input to the switching element.

15. The method of claim 12, further including:

bypassing a first packet to the bypass output port of a given switching element in the event of a conflict between the first packet and a second packet for a given one of the routing output ports of the given switching element.

16. The method of claim 15, further including:

deflecting a third packet to another one of the routing output ports of the given switching element in the event of a conflict between the first, second and third packets for the given one of the routing output ports of the given switching element.

17. The method of claim 13, further including:

coupling output access points between each of the N output ports and the output routing ports of the switching elements of those stages having a stage number that is greater than or equal to the number of routing bits in the destination field of the packets; and

discarding packets received by switching elements where the value of the routed number field equals the number of routing bits in the destination field of the packet.

18. The method of claim 12, further including:

buffering packets at each of the N output ports.

19. The method of claim 12, further including:

buffering packets at each of N input ports.

20. The method of claim 12, further including:

buffering packets in each one of the switching elements.

21. The method of claim 20, further including:

coupling a backpressure signal from each one of the routing input ports and bypass input port of each switching element in a given switching stage to the corresponding one of the routing output ports and the bypass output port of switching elements in a preceding stage;

activating the backpressure signal for one of the routing input ports and bypass input port when a buffer corresponding to the port is full; and

delaying transmission of a packet from the corresponding one of the routing output ports and the bypass output port of switching elements in a preceding stage responsive to the activation of the backpressure signal.