Multiplex communications – Pathfinding or routing – Through a circuit switch
Reexamination Certificate
1999-10-27
2001-06-05
Hsu, Alpus H. (Department: 2662)
Multiplex communications
Pathfinding or routing
Through a circuit switch
C370S411000, C340S870030, C379S220010
Reexamination Certificate
active
06243378
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field of the Invention
This invention relates to digital parallel processing systems, wherein a plurality of nodes communicate via messages over an interconnection network. In particular, this invention deals with networks including circuit switches which do not store and forward the message within the network. This invention further relates to performance improvement techniques for unbuffered networks comprising self-routing switches which include intelligence for minimizing contention problems.
2. Background Art
In parallel systems, a plurality of nodes communicate via messages sent over an interconnection network. Each node usually interfaces to the network via a network adapter.
For self-routing circuit-switched networks, as described in U.S. Pat. No. 5,654,695, issued Aug. 5, 1997, for “Multi-Function Network”, a network adapter sending a message (the sending adapter) searches for a non-blocked alternate path through the network. This search is conducted by trying one alternate path at a time until a successful connection is made across the network to a receiving adapter at another node. An unsuccessful attempt to find a path results in the network returning a rejection signal to the sending adapter to indicate that the attempt has failed. The sending adapter responds by selecting a different alternate path and attempting again to send the message.
The path searching approach for establishing a connection across the network is improved by the dual priority switches in U.S. Pat. No. 5,444,705, “Dual Priority Switching Apparatus for Simplex Networks” by Olnowich et al. The dual priority switch permits the “Multi-Function Network” to make a connection across the network by either path searching or using the camp-on method. The camp-on method uses a high priority path through the network, which proceeds to make connections at each stage of the network until blockage is encountered. Thereupon, the high priority connection command being blocked is stored at the switch stage at the point of blockage and held pending until the blockage ends. Thus, the desired connection to a switch output port that is busy is camped-on until the desired output port becomes available.
Further network performance enhancements featuring non-blocking networks are disclosed in U.S. Pat. No. 5,933,428, issued Aug. 3, 1999, for “TWO-TAILED ADAPTER FOR SCALABLE, NON-BLOCKING NETWORKS” by Olnowich. Non-blocking means that the network will never prevent the connection of two idle nodes attached to the network. That is, when a non-blocking network searches for a path across the network, it will always find at least 1 available path. Thus, the problem of the network preventing a connection from being made is solved.
However, further problems exist which can prevent connections from being successful across the network. The prime problem for a non-blocking network is contention. Contention means that two or more users are competing for the same resource at the same time. In relation to networks, contention means that two or more sending adapters are competing to make a connection to the same receiving adapter on the other side of the network at the same time. In a non-blocking network, any sending adapter will find a path across the network to any receiving adapter; but, if there is contention, even if that path is found across the network, the connection still cannot be made. In a typical example, node
1
is sending a message to node
20
, and node
2
also wants to send a message to node
20
. Node
2
makes it across the network, but cannot connect because node
20
is busy being connected to node
1
.
A good solution for resolving contention, if the message is short, is the camp-on approach discussed-above. This means that the path node
2
found across the network will be held active, and node
2
will wait for node
1
to finish its message. Then node
2
will proceed. However, the use of the camp-on method can defeat the non-blocking characteristic of the network. If two or more paths across the network are being held active waiting to make connection to the same contended destination, a possibility is created in the network where some other sending adapter might no longer be able to find a path across the network to an idle node. This is because more than one path is being dedicated to the node in contention. These periods of possible in the network, will probably go unnoticed if the messages being transferred are short.
However, a problem arises for long messages, such as movie segments or data bases. The camp-on approach then becomes self-defeating in that it solves the contention problem in the best way possible (wait for the contended node to become available), but it creates blocking problems in the network for long periods of time.
Consequently, it as an object of this invention to provide a system which minimizes the losses due to contention in non-blocking networks. It is a further object of the invention to minimize such losses when transmitting long messages.
SUMMARY OF THE INVENTION
The apparatus of the invention is a switching network, comprising a plurality of switch stages including a first stage, at least one middle stage, and a last stage. A send adapter is provided for routing a data message through the plurality of switch stages to the last stage. The data message selectively includes a camp-on command to the last stage. The last stage includes logic responsive to the camp-on command for selectively accepting or rejecting the camp-on command.
The method of the invention provides for transferring data messages across an unbuffered switching network including a plurality of switch stages from a sending adapter to a last stage output port. The sending adapter selects an alternative path through the plurality of switch stages and selectively issues a camp-on command to the last stage. The last stage is operated selectively to accept or reject the camp-on command.
Other features and advantages of this invention will become apparent from the following detailed description of the presently preferred embodiment of the invention, taken in conjunction with the accompanying drawings.
REFERENCES:
patent: 4663620 (1987-05-01), Paul et al.
patent: 4991168 (1991-02-01), Richards
patent: 4991203 (1991-02-01), Kakizawa
patent: 5099509 (1992-03-01), Morganstein et al.
patent: 5099511 (1992-03-01), Matsumoto
patent: 5345229 (1994-09-01), Olnowich et al.
patent: 5404537 (1995-04-01), Olnowich et al.
patent: 5444705 (1995-08-01), Olnowich et al.
patent: 5451936 (1995-09-01), Yang et al.
patent: 5654695 (1997-08-01), Olnowich et al.
patent: 5754120 (1998-05-01), Argentati
patent: 5835024 (1998-11-01), Olnowich et al.
patent: 5933428 (1999-08-01), Olnowich
patent: 5945922 (1999-08-01), Gao et al.
patent: 2-237335 (1990-09-01), None
patent: 5-344146 (1993-12-01), None
NEC Corp.,Camp-on system for data communication between terminal and computer. WPAT AN 90-331157/44 JP J02237335-A Sep. 19, 1990. No abstract.
NEC Corp.,Camp-on system for stored programme electronic swithcing. WPAT AN 88-170557/25 JP J63107264-A May 12, 1988. No abstract.
Beckstrand Shelley M.
Hsu Alpus H.
International Business Machines - Corporation
Qureshi Afsar M.
LandOfFree
Method and apparatus for minimizing contention losses in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for minimizing contention losses in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for minimizing contention losses in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2475487