Multiplex communications – Pathfinding or routing – Through a circuit switch
Reexamination Certificate
1998-01-26
2001-10-16
Holloway, III, Edwin C. (Department: 2635)
Multiplex communications
Pathfinding or routing
Through a circuit switch
Reexamination Certificate
active
06304568
ABSTRACT:
CLAIM OF PRIORITY
This application makes reference to, incorporates the same herein, and claims all benefits accruing under 35 U.S.C. §119 from an application entitled Interconnection Network Extendable Bandwidth And Method of Transferring Data Therein earlier filed in the Korean Industrial Property Office on Jan. 27, 1997, and there duly assigned Serial No. 97-2281 by that Office.
BACKGROUND OF THE INVENTION
Field of the Invention
The present invention relates to an interconnection network in a multicomputer system, and more particularly, to an interconnection network in which a control plane and a data plane are included and the bandwidth of the data plane is extendable and a method of transferring data in the interconnection network.
DESCRIPTION OF RELATED ART
The performance of a Von Nuemann computer is limited, due to structural problems and physical restrictions. Various computers are interconnected to allow parallel processing in order to overcome such restrictions. Namely, a plurality of single processors or a plurality of symmetric multiprocessors (SMP) are connected to process in parallel and to realize a high performance computer system. A system using this multicomputer parallel processing method includes a predetermined number of nodes and an interconnection network for a message transfer between the nodes.
In this case, the overall performance of the system is dependent on the performance of each node and the performance of the interconnection network which connects the nodes. The performance of the interconnection network is quantified by the bandwidth between the nodes and a latency time. Therefore, in order to transmit a great amount of data from a source node to a destination node in a short time, the interconnection network must provide a large bandwidth and a short latency time. In particular, new fields such as decision support systems (DSS) and multimedia systems require high amounts of data to be transferred between nodes. These applications create a need for improving the performance of interconnection networks.
In an interconnection network and nodes in a multicomputer system, the interconnection network provides a path through which the nodes can communicate with each other. They can have various structures such as a ring, a Banyan, a tree, a hypercube, a mesh, and a torus. The above-mentioned structures each have advantages and disadvantages. Common characteristics of earlier interconnection networks will be described with reference to the mesh structure.
In a network having a two-dimensional mesh structure, each crossing point denotes a node. The node includes a computing unit (CU) and a router. The router is connected to other adjacent nodes and forms part of the interconnection network when the interconnection network and the CU are considered as dependent elements.
A path must first be set when a message is to be transferred between nodes. An appropriate method selected from among a circuit switching method, a packet switching method, a wormhole routing method, and virtual cut-through method can be used for setting the path. In general, the path setting method is determined when the router is designed. Various matters such as the end use of the system, the size of messages, and a transfer frequency must be fully considered before the method for setting the path is selected, since setting the path is important in determining the latency time of the interconnection network.
In general, a router needs to exchange information of a special purpose with other adjacent routers, for setting paths, managing the interconnection network, and detecting network errors. In an earlier interconnection network, such information shares the same link of the interconnection network with the general data. However, the link of the interconnection network can not be effectively constructed in such a situation. Namely, in the earlier interconnection network, when large amounts of data must often be transferred, a control signal for setting the path or managing the interconnection network shares the link of the network with data to be transferred, thus inevitably causing interference between them. Accordingly, the effective bandwidth and the latency time deteriorate. Also, the design of the router becomes complicated and the time required for determining the path becomes longer, since the control signal and the transfer data must be simultaneously processed.
Furthermore, the bandwidth of the link between routers is determined when the router is designed in the interconnection network in the earlier interconnection network such as BYNET of NCR, the SERVERNET of Tandem, and the HPS of IBM. Therefore, in case the bandwidth and latency time of the interconnection network must be improved in order to be used for a next generation application, earlier interconnection networks do not provide a convenient mechanism for making the improvement.
In general, in order to increase the bandwidth, high speed semiconductor technology must used or the number of pins of a semiconductor chip must be increased. However, such methods are costly, and, in many cases, the uppermost limit of semiconductor integration technology has already been reached. A method of overlapping multiple interconnection networks in parallel is an alternative for increasing the effective overall bandwidth. It is possible to increase the throughput of standard data simultaneously transferable through the interconnection network by this method. However, this fails to gain various advantages which can be obtained by increasing the bandwidth of the link in the router. Namely, in the case of using two overlapped interconnection networks, it is possible to simultaneously transfer two messages, however, it is impossible to reduce the time required for transferring a message.
In the case of overlapping the interconnection networks according to earlier technology as compared was a case of increasing the bandwidth at the link, assume the size of a message to be sent is M and bandwidth of the earlier interconnection network is W. The message transmission time becomes M/W since either one network or another network is selected in the case of two independent interconnection networks. In the case of doubling the bandwidth, it is possible to reduce the message transmission time to M/2W. Therefore, an important reason to overlap interconnection networks is actually to provide error tolerance through redundancy rather than to extend the bandwidth. Also, the router must be newly designed in order to extend the bandwidth since the earlier interconnection network can not generally provide the effect of doubling the bandwidth.
In the earlier interconnection network, when the header of the message is blocked by other messages, the latency time becomes longer due to the processes for setting the path since other nodes can not set paths until the source and destination nodes release the blocking path.
The following patents each disclose features in common with the present invention:
U.S. Pat. No. 4,706,150 to Lebizay et al., entitled
a Switching Protocal for Multiple Autonomous Switching Planes
, U.S. Pat. No. 5,430,442 to Kaiser et al., entitled
a Cross Point Switch with Distributed Control
, U.S. Pat. No. 5,444,700 to Martikainen et al., entitled
a Switching Element and Method for Controlling the Same
, U.S. Pat. No. 5,377,333 to Nakagoshi et al., entitled
a Parallel Processor System Having Computing Clusters and Auxiliary Clusters Connected with Network of Partial Networks and Exchanges
, U.S. Pat. No. 5,396,231 to Hein, entitled
a Modular Communications Interconnection
, U.S. Pat. No. 5,617,539 to Ludwig et al., entitled
a Multimedia Collaboration System with Separate Data Network and A/V Network Controlled by Information Transmitting on the Data Network
, U.S. Pat. No. 5,659,784 to Inaba et al., entitled
a Multi
-
processor System Having Communication Register Modules Using Test
-
and
-
Set Request Operation for Synchronizing Communications
, U.S. Pat. No. 5,603,044 to Annapareddy et al., entitled
an Interconnection Network f
Bushnell , Esq. Robert E.
Holloway III Edwin C.
Samsung Electronics Co,. Ltd.
LandOfFree
Interconnection network extendable bandwidth and method of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Interconnection network extendable bandwidth and method of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interconnection network extendable bandwidth and method of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2612664