Method of simultaneously attempting parallel path connections in a multi-stage interconnection network

• US 6,034,956 A
• Filed: 06/29/1998
• Issued: 03/07/2000
• Est. Priority Date: 06/07/1995
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Jabusch, John David, Williams, Arthur Robert, Gould, Joel Mark, Bruck, Jehoshua, Olnowich, Howard Thomas, Fisher, Michael Hans
• Primary Examiner(s): HARPER, KEVIN C
• Assistant Examiner(s): Wilson, Jr., William H.
• Application Number:
  US09/106,960
• Time in Patent Office: 617 Days
• Field of Search: 340/825.79, 340/825.03, 340/825.8, 340/826, 340/825.89, 340/827, 370/388, 370/398, 370/397, 370/399, 370/381, 370/379, 370/359, 326/41, 326/38, 395/312, 395/311, 395/182.02, 379/219, 379/220, 379/221, 379/224, 379/268, 379/271, 379/272, 379/273, 379/291, 379/292, 379/306, 710/131, 710/132, 714/4
• US Class Current: 370/388
• CPC Class Codes: H04L 49/101 using crossbar or matrix
• CPC Class Codes: H04L 49/15 Interconnection of switching modules
• CPC Class Codes: H04L 49/1523 Parallel switch fabric planes
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/253 using establishment or release of connections between ports
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

The multi-stage interconnection network of the present invention includes the use of switches in the first stage that have parallel path seeking capabilities. With these switches, a directed flash-flood can be instigated from any one node wherein multiple paths through the network to a designated destination node are tried in parallel in an attempt to find a connection path therebetween. The switches in the first and second stages are interconnected such that each switch in the first stage is connected with every possible priority level to the switches of the second stage. The parallel path seeking switches and network are further configured to test for rejection of the flash-flood by monitoring all connections in combination.

Claims

1. A method for simultaneously attempting parallel path connections in a multi-stage interconnection network, the method comprising the steps of:

providing a first stage including a plurality of first self-routing switches, selected ones of said first self-routing switches including a plurality of input ports and a plurality of output ports;

providing a second stage including a plurality of second self-routing switches, selected ones of said second self-routing switches including a plurality of input ports and a plurality of output ports;

connecting the output ports of said selected ones of said first self-routing switches in the first stage, to the input ports of said selected ones of said second self-routing switches of the second stage to form a plurality of first paths therebetween;

providing a node connected between each of the network output ports and each of the network input ports, so that the switching network establishes direct connections between any of the network input ports and network output ports, each direct connection from one of the network input ports to one of the network output ports being comprised of an equal number of switch stages;

making and breaking connection on a self-routing basis between the plurality of input ports and the plurality of output ports;

holding the attempted connections between switches awaiting availability, utilizing a plurality of self-routing camp-on functionalities; and

,

attempting simultaneous parallel path connections over selected ones of the plurality of the first paths between certain output ports of said selected ones of said self-routing switches of the first stage and certain input ports of said selected ones of said second self-routing switches of the second stage.

2. The method of claim 1, further comprising the steps of:

providing a third stage including a plurality of third self-routing switches, selected ones of said third self-routing switches including a plurality of input ports and a plurality of output ports; and

connecting the output ports of said selected ones of said second self-routing switches in the second stage to the input ports of said selected ones of said third self-routing switches in the third stage to form a plurality of second paths therebetween.

3. The method of claim 2, further comprising the steps of:

camping on said selected ones of said first, second, and third self-routing switches to hold attempted parallel path connections between said first, second, and third self-routing switches; and

,

creating internally to said self-routing switches a reject signal for terminating attempted path connections between said first, second, and third self-routing switches when said attempted parallel path connections are blocked.

4. The method of claim 2 further comprising the steps of:

implementing a plurality of priority levels in said second stage by said selected ones of said second self-routing switches; and

connecting each of said selected ones of said first self-routing switches to said selected ones of said second self-routing switches at every possible priority level in said second stage.

5. The method of claim 1 further comprising the step of:

generating a plurality of REJECT signals for failed attempted path connections between said selected ones of said first self-routing switches and said selected ones of said second self-routing switches.

6. The method of claim 5 further comprising the step of:

combining said REJECT signals for all attempted parallel path connections to generate a combination REJECT signal indicative of the failure of each of said attempted parallel path connections.

7. The method of claim 6 further comprising the step of:

responding to said combination REJECT signal for terminating said attempted parallel path connections seeking connection to said first self-routing switch that attempted failed parallel path connections.

8. The method of claim 5 wherein said simultaneous parallel path connection attempts further comprise the steps of:

seeking a functional path in each of said self-routing first switches; and

,

assessing, in parallel, multiple output ports of said selected ones of said first self-routing switches for connection to input ports of said selected ones of said second self-routing switches, to establish parallel path connections with the second stage, over said selected ones of said plurality of first paths.

9. The method of claim 8 further comprising the steps of:

generating a path selection command between said input ports of said selected ones and said multiple output ports of said selected ones of said first self-routing switches;

responding to said path selection command for attempting to access in parallel each connection identified in said path selection command; and

,

eliminating from consideration each attempted parallel path connection defined in said path selection command that is not accessible.

10. The method of claim 9 further comprising the step of:

prioritizing the path connections identified in said path selection command.

11. The method of claim 10 further comprising the step of:

prioritizing, by round-robin prioritization, said path connections extending between said input ports and said multiple output ports of said selected ones of said first self-routing switches.

12. The method of claim 11 wherein said prioritization further comprises the step of:

determining whether any other input port of said first self-routing switches is requesting connection to any of the same multiple output ports of said first self-routing switches.

13. The method of claim 12 further comprising the step of:

prioritizing the input ports of said first self-routing switches requesting connection to said multiple output ports.

14. The method of claim 13 further comprising the step of:

responding to the prioritization for making path connections between said input ports and said output ports of said first self-routing switches.

15. A method for selectively coupling the input ports to the output ports of a self-routing switch in a switching network, comprising the steps of:

providing a self-routing switch having a plurality of input ports and a plurality of output ports;

providing connecting paths between said input ports and said output ports;

providing a path seeking functionality for controlling the operation of a means for selectively coupling;

simultaneously processing a plurality of commands received at certain ones of the input ports, each command identifying multiple connection paths from each certain input port to certain ones of the output ports;

evaluating the availability of said multiple connection paths identified in each command; and

establishing one and only one connection from each certain input port to one of the certain ones of the output ports.

16. The method of claim 15 further comprising the step of:

simultaneously establishing communications over each of said multiple connections identified by said command.

17. The method of claim 16 further comprising the steps of:

testing the completion of each of said multiple connections found to be available by processing said command; and

,

rejecting said communication if none of said multiple communications are completed.

18. The method of claim 15 further comprising the steps of:

prioritizing a plurality of more than two of said multiple connections found to be available by processing said command; and

establishing connection over the highest priority connection identified by said command.

19. The method of claim 18 further comprising the steps of:

testing for the completion of the highest priority connection; and

,

rejecting the communication if said highest priority connection is not completed.