Electrical computers and digital processing systems: multicomput – Star or tree computer networking
Reexamination Certificate
1995-09-19
2001-12-25
Follansbee, John A. (Department: 2154)
Electrical computers and digital processing systems: multicomput
Star or tree computer networking
C709S238000, C709S240000, C710S041000, C370S351000, C370S389000
Reexamination Certificate
active
06334156
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a method of configuring a network used in communications among processes in, for example, a parallel computer system, and more specifically to a node grouping method and data transmitting method in a network for efficiently transmitting data in, for example, an irregular network.
As the scale of networks become larger, the volume of the routing information held by each node for routing the data to be transmitted in a network, that is, the volume of routing data, becomes correspondingly larger. In this situation, a packet transferred between, for example, parallel computers, needs transmission at a high speed even if it is small in size, and it is desirable to have the smallest possible size of routing data when it is added to the packet.
In some methods, a packet is transferred by adding required routing data to the packet for specifying a particular route. In this case, the routing data to be added to the packet should also be of the smallest size possible.
If plural pieces of data are simultaneously input from a plurality of input ports in each node and are to be output from an output port, control to prioritize the output of the input data through an input port, that is, exclusive control, is required. In this case, if only input data from a specific input port is prioritized, there arises a bias in the entire communications. Therefore, technology for realizing control of prioritizing an output from an input port storing input data which has a long output wait time is demanded through the smallest possible circuit.
2. Description of the Related Art
In a communications network between processors in a conventional parallel computer system, a regular topology such as, for example, a torus network, is normally adopted because a destination can be calculated in routing a packet to any destination node without assigning a large volume of destination information to each node when communications are established among nodes forming part of the network. However, since the topology of a network is restricted to a regular format, nodes are connected under tight restrictions, and packets cannot be optionally routed through specific nodes.
With the parallel computer system, the technology disclosed by Tokkaihei-05-028122 is used to broadcast data transfer as a method of simultaneously transmitting the same data to all nodes in a limited area. In this method, broadcast communications can be realized by initially storing transfer control information for data transfer in a plurality of nodes in a network without transferring routing data, etc.
In an inter-computer network such as Internet, an irregular network is normally adopted, and each node stores a large volume of destination information. Unlike telephone lines, a packet should be normally transferred as a plurality of packets and information about packet destinations and transmission routes should be added to the packet.
Furthermore, in a relay node, packets from an input port which should be prioritized, have been determined with the probability that packets are simultaneously input from a plurality of input ports and output to the same output port. The technology disclosed by, for example, Tokkaihei 05-342178, is used to dynamically control the priority order. In this method, packets are assigned priority levels and priority level information is stored for each input port to obtain priority levels using an adder and a comparator.
As described above, the topology should be of a regular type and the number of ports in a node is fixed in the inter-processor network of the conventional parallel computers, thereby causing the problem that a specific part of the network that is congested cannot be exclusively reinforced even if a biased communications pattern is required because, for example, communications concentrate on one part of the network. There arises another problem that the failure of a node also prevents the entire system from working normally.
The conventional technology disclosed by Tokkaihei-05-028122 for realizing the broadcast data transfer needs initially storing transfer control information in a plurality of nodes. Therefore, it is difficult to completely transfer data to an optional combination of destinations, thereby causing the problem that the volume of transfer control information becomes too large. Furthermore, a network such as Internet which stores a large volume of destination data in each node becomes too big for a node of a parallel computer network. If data transfer information is added to a packet itself when broadcast data is transferred, the size of routing data is too large for the data to be transferred, thereby lowering the efficiency of transfer. When the routing information is added to a packet to transfer it through an optional relay node, the size of the added routing information is also relatively large for the data to be transferred. Thus, the efficiency of data transfer is unfavorably lowered.
Additionally, when the priority levels of packets simultaneously entered from one input port and output from one output port are determined, there are too many circuits required to store the priority levels for each input port and to use an adder and comparator for use in dynamically controlling the priority levels.
SUMMARY OF THE INVENTION
The present invention aims at transferring data efficiently by reducing the volume of stored routing information in a network having an irregular topology.
According to the present invention, network nodes are grouped such that nodes forming the network are classified into a plurality of highest-order hierarchical groups in a communicable format only through intra-group nodes, such that nodes in each of the highest-order hierarchical groups are classified into a plurality of second-highest-order hierarchical groups in a communicable format only through intra-group nodes, and such that nodes in each of the higher-order hierarchical groups are classified into a plurality of next-order hierarchical groups in a communicable format only through intra-group nodes. A hierarchical address is added to a node forming the network corresponding to the hierarchical group to which the node belongs.
Thus, the routing information required to transfer data can be reduced and data can be transferred efficiently.
REFERENCES:
patent: 4017840 (1977-04-01), Schild et al.
patent: 4330857 (1982-05-01), Alvarez, III et al.
patent: 4823111 (1989-04-01), Tsuchiya et al.
patent: 5058051 (1991-10-01), Brooks
patent: 5434977 (1995-07-01), Zapisek
patent: 5453978 (1995-09-01), Sethu et al.
patent: 5-28122 (1993-02-01), None
patent: 5-342178 (1993-12-01), None
Hirose Fumiyasu
Matsuoka Hidetoshi
Shimogori Shintaro
Takayama Koichiro
Follansbee John A.
Fujitsu Limited
Staas & Halsey , LLP
LandOfFree
Node grouping method and data transmitting method in a 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 Node grouping method and data transmitting method in a network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Node grouping method and data transmitting method in a network will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2566511