Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing
Reexamination Certificate
1996-04-01
2001-05-01
Follansbee, John A. (Department: 2154)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Reexamination Certificate
active
06226683
ABSTRACT:
These applications and the present application are owned by one and the same assignee, International Business Machines Corporation of Armonk, New York.
The descriptions set forth in the previous applications and the concurrently filed applications are incorporated by reference. These applications and the present application are owned by one and the same assignee, namely, International Business Machines Corporation of Armonk, New York.
FIELD OF THE INVENTIONS
The present invention relates to digital computer systems comprised of several or many computing and/or input/output elements, and the ability of the said individual elements to perform high speed, low-latency communications with each other in a parallel fashion over a multi-stage, switching interconnection network.
The present invention further relates to mutli-stage, circuit-switched networks without central clocking, and the ability to transfer digital data over the network quickly and accurately.
GLOSSARY OF TERMS
Adaptive
The ability of each switching element to determine for itself which of several optional alternate paths to try at each stage of the network based on availability.
Alternate Path
One of a plurality of connection paths that can be used to from a connection between a sending node and a receiving node through a multi-stage network.
Blocking
The characteristics of multi-stage networks which sometimes prevent a sending node from establishing a connection to an available receiving node due to the properties of the network.
Circuit-switched network
A network where the individual switching elements comprising the network do not buffer the data messages, but pass them immediately as a direct connection from input to output.
Data Message
A format for sending information between nodes of a parallel system incorporating the further ability to check the said information for accuracy using cyclic redundancy coding methods.
Data
Another term for Data Message
Idle
The state of a switch interface where it is not presently involved in the process of connecting two nodes.
Message
Another term for Data Message
Node
A functional element of the system comprised of one or more processors or input/output devices interconnected by a network.
Nodal element
Another term for node, which has the same meaning.
NRZ
Abbreviation for non-return to zero.
Port
A single bi-directional entry and exit point to a switching netwrok.
Receiving Node
A functional element which is receiving data transmitted over a network.
Sending Node
A functional element which is transmitting data over a network.
BACKGROUND OF THE INVENTIONS
Parallel computing systems consist of a plurality of processors that communicate via an interconnection network. One popular network for providing the interconnection for a plurality of processors is the circuit-switched network comprised of multiple circuit switches. The state-of-the-art unbuffered circuit switch is the ALLNODE Switch (Asynchronous, Low Latency, inter-NODE switch), which is disclosed in U.S. Ser. No. 07/677,543 and continued as U.S. Ser. No. 08/457,789 filed Jun. 2, 1995. The Allnode switch as disclosed in U.S. Ser. No. 07/677,543 (now continued as U.S. Ser. No. 08/457,789) provides excellent low latency characteristics because it implements a minimum amount of circuitry at each switch stage of a multi-stage interconnection network. The latency across the switch is extremely fast because the equivalent of a straight wire connection is provided across each switch stage. The Allnode Switch supports a totally asynchronous transmission that does not require relatching or buffering at the individual switch elements. Therefore, the Allnode Switch delivers data messages being transmitted through the switch as quickly as possible avoiding the delays of any buffering.
As the field of parallel processing advances, the need for better preforming interconnection networks comprised of multiple stages becomes of prime importance. To date, one of the highest performing circuit switch networks has been described in U.S. Ser. No. 07/799,497, Filed Nov. 27, 1991 and continued as U.S. Ser. No. 08/216,789 filed Mar. 23, 1994, and continued as U.S. Ser. No. 08/606,232 filed Feb. 23, 1996, Multi-Function Network” by H. T. Olnowich et al. The said network uses multiple paths through the network, called alternate paths, and searches for an open path to make a network connection. The said network uses the “Dual Priority Switching Apparatus for Simplex Networks” described by H. T. Olnowich et al. in U.S. Ser. No. 07/799,262 and continued as U.S. Ser. No. 08/318,578 filed Oct. 5, 1994, which is a two mode switch capable of performing two different switching modes based on the presence of different types of traffic patterns in the network. The first mode causes connections in the network to be broken if “cold” or random traffic encounters blockage in the network, and then path establishment is retried over a different alternate path in the network as controlled by the node trying to establish the connection. The second mode causes traffic into the network which has been classified as “hot” traffic to experience a different network capability of camp-on (previously won connections in the network are not broken when hot spot congestion is experienced in the network). In the camp-on mode, the request for a connection is placed into a priority queue at the switch experiencing blockage and serviced as soon as the blockage dissapates on a fairness basis to prevent the starvation of any node encountering a hot spot.
The existing methods have some disadvantages. The alternate paths are chosen randomly and blindly by the sending nodes and their network adapters before entering the network. This approach leads to choosing a fixed path to be tried. If the fixed path is blocked for random traffic, the network adapter picks another path blindly and tries again to establish connection. The blind selection problem is solved by the co-pending application, U.S. Ser. No. 07/947,023 now issued as U.S. Pat. No. 5,345,229, Adaptive Switching Apparatus” by H. T. Olnowich etal. The adaptive switch permits each switching element to determine for itself which of several optional alternate paths to try at each stage of the network based on availability. This is a better approach because it brings the decision directly to the switching apparatus involved, which has the data required to make an intelligent decision, as opposed to being commanded blindly from a distance.
A further problem exists in multi-stage networks, especially in circuit switched multi-stage networks, where a path must be won simultaneously at every stage through the entire network. This is necessary in order to establish a direct circuit connection through the network for sending a data message from a sending node to a receiving node. In traditional circuit switched networks experiencing heavy loading, it becomes difficult to win resources across the entire network. In IBM DOCUMENT NO. AAA92A000597, “Experimental Comparison of Multistage Interconnection Networks”, published in November 1991 by S. Konstantinidou and E. Upfal extensive simulation results comparing the routing performance of various multistage communication networks. These simulations of traditional networks have shown that such networks tend to clog at about a 20% loading factor. The clogging has been shown to occur mainly at the later stages of the network.
The clogging at later stages presents a problem because this is the worst place for networks to clog. As a transfer starts into the network, it must win each network stage in succession. It wins the first stage and then tries to win the second stage while holding and tying up the resources at the first stage. After winning the second stage, it tries to win the third stage while tying up the resources at the first and second stages. Thus, the establishment of a connection works its way through the network forming a path to the desired receiving node. If other connections want to use a resource being held, they cannot and this effect adds to the clogging of the network.
Bruck Jehoshua
Feeney James William
Olnowich Howard Thomas
Upfal Eli
Follansbee John A.
International Business Machines - Corporation
Samodovitz Arthur J.
LandOfFree
Increasing probability multi-stage network does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Increasing probability multi-stage network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Increasing probability multi-stage network will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2464435