Network apparatus and network managing apparatus

First-stage switches (B1 to B9), second-stage switches (M1 to M9), and third-stage switches (T1 to T9) include a bottom connection path that configure to interchange a connection point of one or more second signal transmitting units and a connection point of another one or more second signal transmitting units, in a Fat Tree configuration between the first-stage switches (B1 to B9) and the second-stage switches (M1 to M9) constituting a one-set Fat Tree with the third-stage switches (T1 to T9).

CROSS-REFERENCE TO RELATED APPLICATION

This application is based upon and claims the benefit of priority of the prior Japanese Patent Application No. 2011-158460, filed on Jul. 19, 2011, the entire contents of which are incorporated herein by reference.

FIELD

The embodiments discussed herein are directed to a network apparatus and a network managing apparatus.

BACKGROUND

In recent years, cluster systems connecting a large number of nodes, for example, servers by a high-speed network have been widely used in the field of HPC (high performance computer). In many cases, such cluster systems perform parallel computation processing. In communication for the parallel computation processing, it is recommended to achieve a low delay and secure a wide band in signal transmission. To this end, InfiniBand-based Fat Tree connections have been widely used, particularly in large-scale cluster systems.

For example, the Fat Tree is a topology having a multiplexed tree-type network configuration such as a configuration illustrated inFIG. 13.FIG. 13is a diagram illustrating a configuration of a network apparatus having a three-stage Fat Tree. In the Fat Tree, since the number of connection links in each switch is equal in the upper side and the lower side except for the top, a sufficiently wide band can be secured even when transmission is made in either the upward direction or the downward direction.

Herein, switches B1to B9illustrated inFIG. 13will be referred to as first-stage switches. Further, switches M1to M9will be referred to as second-stage switches. Further, switches T1to T9will be referred to as third-stage switches. In the Fat Tree illustrated inFIG. 13, each of the first-stage switches is connected to three second-stage switches. Further, the switches B1to B3are connected to the same second-stage switch. Further, the switches B4to B6are connected to the same second-stage switch. Further, the switches B7to B9are connected to the same second-stage switch. For example, each of the switches B1to B3is connected to the switches M1, M4, and M7.

Further, each of the switches B1to B9is connected to three nodes. InFIG. 13, circles connected to the switches B1to B9represent nodes. Also, a number marked under each node represents each node number. This node number serves as an address for signal transmission between the nodes. For example, the nodes denoted by node numbers1to3are connected to the switch B1. Further, the nodes denoted by node numbers4to6are connected to the switch B2. Hereinafter, the node denoted by a node number P will be referred to as a node P.

Each of the nodes1to27transmits a signal destined for another node, to the first-stage switch connected to the node itself. Herein, each of the nodes1to27designates a node number as a destination address of a signal transmitted to another node.

Each of the switches B1to B9receives a signal transmitted from the node connected to the switch itself to another node. Then, the switches B1to B9transmit signals destined for node numbers of 1 mod 3, to the switches M1to M3. Further, the switches B1to B9transmit signals destined for node numbers of 2 mod 3, to the switches M4to M6. Further, the switches B1to B9transmit signals destined for node numbers of 3(0) mod 3, to the switches M7to M9. For example, the switch B1transmits a signal of 1 mod 3 among the signals received from the nodes1to3, to the switch M1as indicated by an arrow901. Further, the switch B1transmits a signal of 2 mod 3 among the signals received from the nodes1to3, to the switch M4as indicated by an arrow902. Further, the switch B1transmits a signal of 3(0) mod 3 among the signals received from the nodes1to3, to the switch M7as indicated by an arrow903.

Each of the switches M1to M9receives signals that are equal in the remainder of a signal destination node number divided by 3, from the first-stage switches connected thereto. For example, the switch M1receives a signal having a destination node number of 1 mod 3, from each of the switches B1to B3. Further, the switch M2receives a signal having a destination node number of 1 mod 3, from each of the switches B4to B6. Further, the switch M3receives a signal having a destination node number of 2 mod 3, from each of the switches B7to B9. Further, the switch M4receives a signal having a destination node number of 2 mod 3, from each of the switches B1to B3. Further, the switch M7receives a signal having a destination node number of 3(0) mod 3, from each of the switches B1to B3.

Further, the switches M1to M3and the switches T1to T3are combined with each other, the switches M4to M6and the switches T4to T6are combined with each other, and the switches M7to M9and the switches T7to T9are combined with each other. Then, the switches M1to M3transmit signals having a destination node number of 1 mod 9, to the switch T1as indicated by an arrow904, for example. Further, the switches M1to M3transmit signals having a destination node number of 4 mod 9, to the switch T2as indicated by an arrow905, for example. Further, the switches M1to M3transmit signals having a destination node number of 7 mod 9, to the switch T3as indicated by an arrow906, for example. Further, the switches M4to M6transmit signals having a destination node number of 2 mod 9 to the switch T4, transmit signals having a destination node number of 5 mod 9 to the switch T5, and transmit signals having a destination node number of 8 mod 9 to the switch T6. Further, the switches M7to M9transmit signals having a destination node number of 3 mod 9 to the switch T7, transmit signals having a destination node number of 6 mod 9 to the switch T8, and transmit signals having a destination node number of 0 mod 9 (=9 mod 9) to the switch T9.

Then, the switches T1to T9transmit signals to the second-stage switches connected to the first-stage switches connected to the nodes having the destination node numbers of the signals received from the switches M1to M9. Further, the switches M1to M9transmit signals to the first-stage switches connected to the nodes having the destination node numbers of the signals received from the switches T1to T9. Thereafter, the switches B1to B9transmit signals to the nodes having the destination node numbers of the signals received from the switches M1to M9.

In this way, a signal is transmitted from a node to another node in the Fat Tree.

Further, a communication scheme called a shift communication pattern is widely used in all-to-all communication that transmits messages from all nodes to all nodes in Fat Tree connection. If the number of nodes is N, the shift communication pattern is configured by N number of communication phases. Then, in the i-th communication phase, each node transmits a message with respect to a node number that is previous by “i” to its own node number. Thus, if each node number is p (p=1, 2, . . . , N), ((i+p) mod N) is a message destination of each node in the i-th communication phase. That is, in the shift communication pattern, the destinations of signals transmitted from the respective nodes do not overlap with each other in each phase.

FIG. 14is a diagram illustrating a shift communication pattern.FIG. 14illustrates the 9th communication phase in a case where a shift communication pattern is performed in the same configuration as illustrated inFIG. 13. Numerals enclosed by a box910represent the destination node numbers of respective nodes. In the 9th communication phase, the destination node number of each node is equal to 9 plus the node number of each node. In the shift communication pattern, the node numbers of signals received by the first-stage switches B1to B9from subordinate nodes are serial numbers. Thus, the first-stage switches receive three signals having destination node numbers of 1 mod 3, 2 mod 3, and 3(0)mod 3. Accordingly, the first-stage switches transmit the received signals to the different second-stage switches. Each of the second-stage switches receives signals that are equal in the remainder of division by 3 among 9 serial destination node numbers. Then, the numbers that are equal in the remainder of division by 3 among 9 serial destination node numbers are different in the remainder of division by 9. For example, the switch M1receives three signals having destination node numbers of 1 mod 9, 4 mod 9, and 7 mod 9. Accordingly, the switch M1transmits the received signals to the different third-stage switches. Likewise, each of the switches M2to M9transmits the each received signals to the different third-stage switches.

Accordingly, two or more signals may not flow through any path. Hereinafter, when two or more signals flow through the same path, it will be referred to as a path contention. While a description has been given of the 9th communication phase as an example, the relation between the destinations of signals received by each switch is also the same in other communication phases. That is, when the shift communication pattern is used, a path contention does not occur in any communication phase. Accordingly, the use of the shift communication pattern in the Fat Tree can achieve a high throughput in all-to-all communication and can secure a wide band in signal transmission.

In the description ofFIGS. 13 and 14, for the convenience in description, it has been described that all signals are transmitted to the destination nodes through the first-stage to third stage switches. However, when the network connection state in each switch is stored and a signal can be transmitted to a destination node even without transmitting the signal to the upper stage, each of the first-stage switches and the second-stage switches directly transmits a signal to the lower-stage switch or a subordinate node. For example, when a node with a node number of 1 transmits a signal to a node with a node number of 2, the first-stage switch directly transmits the signal received from the node with a node number of 1, to the node with a node number of 2.

In the Fat Tree, for example, a second-stage Fat Tree, there has been proposed a conventional technology of the Fat Tree connected to transmit one-hop signals to all other nodes.

Non-patent Literature 1: Using Fat-Trees to Maximize the Number of Processors in a Massively Parallel Computer, M. Valerio, L. E. Moser and P. M. Melliar-Smith, Department of Electrical and Computer Engineering University of California, Santa Barbara

However, in the Fat Tree topology illustrated inFIG. 13, when the scale of a network increases, the average number of hops between nodes increases. Therefore, it is difficult to reduce a delay in signal transmission.

Further, in the Fat Tree connected to transmit one-hop signals to all other nodes, it is difficult to perform all-to-all communication by shift communication, and it is difficult to secure a wide band for signal transmission.

SUMMARY

According to an aspect of an embodiment of the invention, a network apparatus, in which one of n2combinations of signal transmitting/receiving devices classified to have n sequential addresses from the minimum address is connected in one-to-one correspondence with n3signal transmitting/receiving devices having n3addresses of serial numbers (n is a natural number equal to or greater than 2), the network apparatus comprising: n2first signal transmitting units configured to receive n signals, which are different in terms of the remainder of a destination address divided by n, from the signal transmitting/receiving device and transmit the received signals to n different destinations; n2second signal transmitting units configured to receive n signals, which are equal in terms of the remainder of a destination address divided by n, from the different first signal transmitting units and transmit the received signals to a destination corresponding to the remainder of a destination address of each of the received signals divided by n2; n2third signal transmitting units configured to have a Fat Tree configuration with respect to the second signal transmitting unit, receive n signals, which are equal in terms of the remainder of a destination address divided by n2, from n different second signal transmitting units, and output the received signal, which is received from the second signal transmitting unit, to the second signal transmitting unit connected to the first signal transmitting unit connected to the signal transmitting/receiving device having a destination address of the received signal; and a bottom connection path disposed between the first signal transmitting units and the second signal transmitting units constituting the Fat Tree together with the third signal transmitting units and configured to interchange a connection point of one or more second signal transmitting units and a connection point of another one or more second signal transmitting units in a Fat Tree configuration between the first signal transmitting units and the second signal transmitting units.

DESCRIPTION OF EMBODIMENTS

However, the network apparatus and the network managing apparatus according to the invention are not limited to the embodiments. In particular, while the case of using 6-port switches or 8-port switches will be described as an example, the invention is not limited thereto, and the switches may be as follows. That is, in the first-stage switch, the number of ports connected to nodes is equal to the number of ports connected to the second-stage switches. Further, in the second-stage switch, the number of ports connected to the first-stage switches is equal to the number of ports connected to the third-stage switches. Further, the third-stage switches may have the same number of ports connected to the second-stage switches, as the number of ports of the second-stage switch connected to the third-stage switches.

[a] First Embodiment

FIG. 1is a diagram illustrating a configuration of a network apparatus according to a first embodiment. As illustrated inFIG. 1, the network apparatus according to the first embodiment includes switches B1to B9, switches M1to M9, and switches T1to T9. Herein, the switches B1to B9may be referred to collectively as the first-stage switches. Further, the switches M1to M9may be referred to collectively as the second-stage switches. Further, the switches T1to T9may be referred to collectively as the third-stage switches. Further, a numeral allocated to each of the first-stage switches, the second-stage switches, and the third-stage switches will be referred to as a number of the switch. For example, the switch B1is the first first-stage switch, and the switch M3is the third second-stage switch.

Further, three nodes are connected to each of the first-stage switches. That is, as illustrated inFIG. 1, a total of 27 nodes are connected to the network apparatus. Each node is represented by a circle connected to the first-stage switch. A numeral marked under each node is a node number allocated to each node. Hereinafter, the node with a node number P will be referred to as a node P. In this embodiment, the nodes1to3are connected to the switch B1, the nodes4to6are connected to the switch B2, and the nodes7to9are connected to the switch B3. Further, the nodes10to12are connected to the switch B4, the nodes13to15are connected to the switch B5, and the nodes16to18are connected to the switch B6. Further, the nodes19to21are connected to the switch B7, the nodes22to24are connected to the switch B8, and the nodes25to27are connected to the switch B9.

Next, a description will be given of a method of connecting the first-stage switches B1to B9and the second-stage switches M1to M9.FIG. 2is a diagram illustrating the preparation of connections between the first-stage switches and the second-stage switches.

First, as illustrated inFIG. 2, the first-stage switches B1to B9according to this embodiment are classified into three groups. The switches B1to B9are classified into groups according to the remainders of the minimum node numbers of the connected nodes divided by 9. That is, the switches B1to B9are classified into three groups of the switches B1, B4, and B7, the switches B2, B5, and B8, and the switches B3, B6, and B9. InFIG. 2, the boxes of the switches B1, B4, and B7are represented by solid lines to indicate that the switches B1, B4, and B7belong to the same group, which will be referred to as the group1-1. Further, inFIG. 2, the boxes of the switches B2, B5, and B8are represented by dotted lines to indicate that the switches B2, B5, and B8belong to the same group, which will be referred to as the group1-2. Further, inFIG. 2, the boxes of the switches B3, B6, and B9are represented by dashed dotted lines to indicate that the switches B3, B6, and B9belong to the same group, which will be referred to as the group1-3. This group classification may also be performed according to the remainders of the switch numbers of the first-stage switches divided by 3.

In addition to this group classification, the switches B1to B9are classified into the switches B1to B3enclosed by a box204, the switches B4to B6enclosed by a box205, and the switches B7to B9enclosed by a box206.

Further, the second-stage switches M1to M9are classified into groups connected to the same third-stage switches. That is, the switches M1to M9are classified into three groups of the switches M1to M3enclosed by a box201, the switches M4to M6enclosed by a box202, and the switches M7to M9enclosed by a box203. Herein, the switches M1to M3will be referred to as the group2-1, the switches M4to M6will be referred to as the group2-2, and the switches M7to M9will be referred to as the group2-3.

The connection may be requested to satisfy the following conditions. The first condition is as follows. The switches M1to M3included in the group2-1receive signals having destination node numbers of 1 mod 9, 4 mod 9, and 7 mod 9, from the first-stage switches. The switches M4to M6included in the group2-2receive signals having destination node numbers of 2 mod 9, 5 mod 9, and 8 mod 9, from the first-stage switches. The switches M7to M9included in the group2-3receive signals having destination node numbers of 3 mod 9, 6 mod 9, and 0 mod 9, from the first-stage switches.

Further, the second condition is that all of the switches M1to M9receive three signals that are different in terms of the remainder of division by 9.

Further, the third condition is that the connection between the switches M1to M9and the switches B1to B9is different from the connection in the conventional Fat Tree illustrated inFIG. 13. That is, the connection between the first-stage switches and any one of the groups2-1,2-2, and2-3is different from the connection illustrated inFIG. 13.

First, the switches M1to M3of the group2-1will be described. The switches M1to M3can receive only a signal of 1 mod 3 according to the first condition. Since 1 mod 3 is only one in each of the switches B1to B9, all of the switches B1to B9are connected to one of the switches M1to M3. Further, according to the second condition, the switches M1to M3select one first-stage switch from each of the groups1-1,1-2, and1-3. In other words, the switches M1to M3may not select a connection point from the same group, among the groups1-1,1-2, and1-3.

Thus, the switch M1selects one of the switches B1, B4, and B7of the group1-1. The switch M2selects one of the switches other than the switch selected from the switches B1, B4, and B7of the group1-1by the switch M1. Further, the switch M3selects one of the switches other than the switches selected from the switches B1, B4, and B7of the group1-1by the switches M1and M2. The switches M1to M3receive signals of 1 mod 3 from the selected switches. Herein, in this embodiment, among the outputs of the first-stage switches, a signal of 1 mod 3 is output to the leftmost path toward the paper plane of the drawings. Thus, when the connection is illustrated by the drawings, the leftmost path of the first-stage switches are connected to the switches M1to M3, thereby satisfying the condition of receiving a signal of 1 mod 3.

Likewise, the switches M1to M3select a connection combination of the switches B2, B5, and B7of the group1-2. Further, the switches M1to M3select a connection combination of the switches B3, B6, and B9of the group1-3. Then, the switches M1to M3receive signals of 1 mod 3 from the selected switches.

Further, the switches M4to M6make a similar switch selection from the groups1-1to1-3. Then, the switches M4to M6receive signals of 2 mod 3 from the selected switches. Herein, in this embodiment, among the outputs of the first-stage switches, a signal of 1 mod 3 is output to the central path toward the paper plane of the drawings. Thus, when the connection is illustrated by the drawings, the leftmost path of the first-stage switches are connected to the switches M1to M3, thereby satisfying the condition of receiving a signal of 2 mod 3.

Further, the switches M7to M9make a similar switch selection from the groups1-1to1-3. Then, the switches M7to M9receive signals of 0 mod 3 from the selected switches. Herein, in this embodiment, among the outputs of the first-stage switches, a signal of 0 mod 3 is output to the central path toward the paper plane of the drawings. Thus, when the connection is illustrated by the drawings, the leftmost path of the first-stage switches are connected to the switches M1to M3, thereby satisfying the condition of receiving a signal of 2 mod 3.

However, in order to reduce the average number of hops as compared to the Fat Tree configuration illustrated inFIG. 13, the connection between the first-stage switches and any one of the groups2-1,2-2, and2-3is different from the connection illustrated inFIG. 13. That is, any one of the groups2-1,2-2, and2-3is discontinuous in terms of the node numbers of nodes connected to the first-stage switches connected to one of the second-stage switches. The switches B1to B9correspond to an example of a “first transmitting unit”. Further, the switches M1to M9correspond to an example of a “second transmitting unit”.

Next, the signal transmission and the connection between the switches B1to B9and the switches M1to M9according to this embodiment will be described in detail with reference toFIG. 1.

The switch M1is connected to the switches B1to B3. Further, the switch M2is connected to the switches B4to B6. Further, the switch M3is connected to the switches B7to B9. That is, the connection between the first-stage switches and the switches M1to M3according to this embodiment are the same as in the case ofFIG. 13.

The switch M4is connected to the switches B2to B4. Further, the switch M5is connected to the switches B5to B7. Further, the switch M6is connected to the switches B8, B9, and B1. That is, the connection between the first-stage switches and the switches M4to M6according to this embodiment corresponds to an increase of a factor of 1 in the number of each of the first-stage switches connected to the M4to M6in the case ofFIG. 13. However, when the switch number exceeds B9, it returns to B1.

The switch M7is connected to the switches B3to B5. Further, the switch M8is connected to the switches B6to B8. Further, the switch M9is connected to the switches B9, B1, and B2. That is, the connection between the first-stage switches and the switches M7to M9according to this embodiment corresponds to an increase of a factor of 2 in the number of each of the first-stage switches connected to the M7to M9in the case ofFIG. 13. However, when the switch number exceeds B9, it returns to B1.

Herein, in this embodiment, the first-stage switches are classified into three groups including three first-stage switches in ascending order of switch number, and the second-stage switches are classified into three groups including three second-stage switches in ascending order of switch number. Then, the first-stage switches grouped as illustrated inFIG. 13are connected to the same second-stage switch, and the connected first-stage switches are increasingly shifted in number by 1 and connected to each of the grouped second-stage switches. When the switches having a different number of ports are used, the same method may be used to determine the connection. That is, the first-stage switches and the second-stage switches are classified into the group including the half of the number of switch ports. Then, the grouped first-stage switches are connected to the same second-stage switch, and the connected first-stage switches are delayed and connected by increasing the number by a factor of 1 for each of the grouped second-stage switches.

Then, in the network apparatus according to this embodiment, all-to-all communication is performed using a shift communication pattern. Herein, a signal transmission through a signal transmission path in the network apparatus according to this embodiment will be described by exemplifying the case of a phase9of the shift communication pattern.

In the phase9, a signal is transmitted from each node, with respect to a node having a node number marked under each node, as a node number marked in a region enclosed by a box101. For example, the node1transmits a signal to the node10. Further, the node2transmits a signal to the node11.

The switches B1to B9receive a signal transmitted from each of the connected nodes to another node. Then, the switches B1to B9transmit a signal having a destination node number of 1 mod 3, to the second-stage switch having the smallest number among the second-stage switches connected thereto. Further, the switches B1to B9transmit a signal having a destination node number of 2 mod 3, to the second-stage switch having the second-smallest number among the connected second-stage switches. Further, the switches B1to B9transmit a signal having a destination node number of 0 mod 3, to the second-stage switch having the greatest number among the second-stage switches connected thereto. However, when each of the switches B1to B9stores a node number of a node connected thereto and the destination node number corresponds to the node connected thereto, it transmits a signal to the corresponding node without transmitting a signal to the second-stage switch. For example, when the switch B1receives a signal transmitted to the node2, from the node1, it transmits the received signal to the node2without transmitting a signal to the switch M6.

Herein, the signal transmission from the switches B1to B9to the switches M1to M9will be described in detail. When the destination node number satisfies 1 mod 3, the switch B1transmits a signal to the switch M1. When the destination node number satisfies 2 mod 3, the switch B1transmits a signal to the switch M6. When the destination node number satisfies 0 mod 3, the switch B1transmits a signal to the switch M9. For example, in the case of the phase9, the switch B1receives a signal transmitted from the node1to the node10, receives a signal transmitted from the node2to the node11, and receives a signal transmitted from the node3to the node12. Then, among the received signals, the switch B1transmits a signal transmitted to the node10having a destination node number of 1 mod 3, to the switch M1. Further, among the received signals, the switch B1transmits a signal transmitted to the node11having a destination node number of 2 mod 3, to the switch M6. Further, among the received signals, the switch B1transmits a signal transmitted to the node12having a destination node number of 0 mod 3, to the switch M9.

When the destination node number satisfies 1 mod 3, the switch B2transmits a signal to the switch M1. When the destination node number satisfies 2 mod 3, the switch B2transmits a signal to the switch M4. When the destination node number satisfies 0 mod 3, the switch B2transmits a signal to the switch M9. For example, in the case of the phase9, the switch B2receives a signal transmitted from the node4to the node13, receives a signal transmitted from the node5to the node14, and receives a signal transmitted from the node6to the node15. Then, among the received signals, the switch B2transmits a signal transmitted to the node13having a destination node number of 1 mod 3, to the switch M1. Further, among the received signals, the switch B2transmits a signal transmitted to the node14having a destination node number of 2 mod 3, to the switch M4. Further, among the received signals, the switch B2transmits a signal transmitted to the node15having a destination node number of 0 mod 3, to the switch M9.

When the destination node number satisfies 1 mod 3, the switch B3transmits a signal to the switch M1. When the destination node number satisfies 2 mod 3, the switch B3transmits a signal to the switch M4. When the destination node number satisfies 0 mod 3, the switch B3transmits a signal to the switch M7. For example, in the case of the phase9, the switch B3receives a signal transmitted from the node7to the node16, receives a signal transmitted from the node8to the node17, and receives a signal transmitted from the node9to the node18. Then, among the received signals, the switch B3transmits a signal transmitted to the node16having a destination node number of 1 mod 3, to the switch M1. Further, among the received signals, the switch B3transmits a signal transmitted to the node17having a destination node number of 2 mod 3, to the switch M4. Further, among the received signals, the switch B3transmits a signal transmitted to the node18having a destination node number of 0 mod 3, to the switch M7.

When the destination node number satisfies 1 mod 3, the switch B4transmits a signal to the switch M2. When the destination node number satisfies 2 mod 3, the switch B4transmits a signal to the switch M4. When the destination node number satisfies 0 mod 3, the switch B4transmits a signal to the switch M7. For example, in the case of the phase9, the switch B4receives a signal transmitted from the node10to the node19, receives a signal transmitted from the node11to the node20, and receives a signal transmitted from the node12to the node21. Then, among the received signals, the switch B4transmits a signal transmitted to the node19having a destination node number of 1 mod 3, to the switch M2. Further, among the received signals, the switch B4transmits a signal transmitted to the node20having a destination node number of 2 mod 3, to the switch M4. Further, among the received signals, the switch B4transmits a signal transmitted to the node21having a destination node number of 0 mod 3, to the switch M7.

When the destination node number satisfies 1 mod 3, the switch B5transmits a signal to the switch M2. When the destination node number satisfies 1 mod 2, the switch B5transmits a signal to the switch M5. When the destination node number satisfies 0 mod 3, the switch B5transmits a signal to the switch M7. For example, in the case of the phase9, the switch B5receives a signal transmitted from the node13to the node22, receives a signal transmitted from the node14to the node23, and receives a signal transmitted from the node15to the node24. Then, among the received signals, the switch B5transmits a signal transmitted to the node21having a destination node number of 1 mod 3, to the switch M2. Further, among the received signals, the switch B5transmits a signal transmitted to the node23having a destination node number of 2 mod 3, to the switch M5. Further, among the received signals, the switch B5transmits a signal transmitted to the node24having a destination node number of 0 mod 3, to the switch M7.

When the destination node number satisfies 1 mod 3, the switch B6transmits a signal to the switch M2. When the destination node number satisfies 1 mod 2, the switch B6transmits a signal to the switch M5. When the destination node number satisfies 0 mod 3, the switch B6transmits a signal to the switch M8. For example, in the case of the phase9, the switch B6receives a signal transmitted from the node16to the node25, receives a signal transmitted from the node17to the node26, and receives a signal transmitted from the node18to the node27. Then, among the received signals, the switch B6transmits a signal transmitted to the node24having a destination node number of 1 mod 3, to the switch M2. Further, among the received signals, the switch B6transmits a signal transmitted to the node26having a destination node number of 2 mod 3, to the switch M5. Further, among the received signals, the switch B6transmits a signal transmitted to the node27having a destination node number of 0 mod 3, to the switch M8.

When the destination node number satisfies 1 mod 3, the switch B7transmits a signal to the switch M3. When the destination node number satisfies 2 mod 3, the switch B7transmits a signal to the switch M5. When the destination node number satisfies 0 mod 3, the switch B7transmits a signal to the switch M8. For example, in the case of the phase9, the switch B7receives a signal transmitted from the node19to the node1, receives a signal transmitted from the node20to the node2, and receives a signal transmitted from the node21to the node3. Then, among the received signals, the switch B7transmits a signal transmitted to the node1having a destination node number of 1 mod 3, to the switch M3. Further, among the received signals, the switch B7transmits a signal transmitted to the node2having a destination node number of 2 mod 3, to the switch M5. Further, among the received signals, the switch B7transmits a signal transmitted to the node3having a destination node number of 0 mod 3, to the switch M8.

When the destination node number satisfies 1 mod 3, the switch B8transmits a signal to the switch M3. When the destination node number satisfies 1 mod 2, the switch B8transmits a signal to the switch M6. When the destination node number satisfies 0 mod 3, the switch B8transmits a signal to the switch M8. For example, in the case of the phase9, the switch B8receives a signal transmitted from the node22to the node4, receives a signal transmitted from the node23to the node5, and receives a signal transmitted from the node24to the node6. Then, among the received signals, the switch B8transmits a signal transmitted to the node4having a destination node number of 1 mod 3, to the switch M3. Further, among the received signals, the switch B8transmits a signal transmitted to the node5having a destination node number of 2 mod 3, to the switch M6. Further, among the received signals, the switch B8transmits a signal transmitted to the node6having a destination node number of 0 mod 3, to the switch M8.

When the destination node number satisfies 1 mod 3, the switch B9transmits a signal to the switch M3. When the destination node number satisfies 1 mod 2, the switch B9transmits a signal to the switch M6. When the destination node number satisfies 0 mod 3, the switch B9transmits a signal to the switch M9. For example, in the case of the phase9, the switch B9receives a signal transmitted from the node25to the node7, receives a signal transmitted from the node26to the node8, and receives a signal transmitted from the node27to the node9. Then, among the received signals, the switch B9transmits a signal transmitted to the node7having a destination node number of 1 mod 3, to the switch M3. Further, among the received signals, the switch B9transmits a signal transmitted to the node8having a destination node number of 2 mod 3, to the switch M6. Further, among the received signals, the switch B9transmits a signal transmitted to the node9having a destination node number of 0 mod 3, to the switch M9.

Herein, the numbers marked under the switches M1to M9ofFIG. 1represent the destination node numbers of the signals received from the first-stage switches of the respective switches M1to M9in the phase9. In this way, each of the second-stage switches receives three signals transmitted from the different first-stage switches. That is, if the shift communication pattern is used, when signals are transmitted from the first-stage switches to the second-stage switches, since two or more signals may not flow through the same path, a wide band can be secured in signal transmission.

Further, when each of the switches B1to B9receives a signal transmitted from the switches M1to M9to the node connected thereto, it transmits the signal to the node having the destination node number. However, each of the switches M1to M9stores the number of the node connected to the first-stage switch connected thereto. Then, when the destination node number of the received signal is the number of node connected to the first-stage switch connected thereto, each of the switches M1to M9transmits the signal to the first-stage switch connected to the node having the node number.

The number of first-stage switches reaching one hop from the switches B1to B9increases as compared to the case ofFIG. 13. Hereinafter, when a switch reaches one hop from another switch, the switch may be referred to as an “adjacent connection switch”. For example, inFIG. 13, the adjacent connection switches for the switch B1are only two switches B2and B3. On the other hand, inFIG. 1, the adjacent connection switches for the switch B1are four switches B2, B3, B8, and B9. In this manner, the average number of hops in the network apparatus according to this embodiment is smaller than the average number of hops in the conventional configuration illustrated inFIG. 13. Accordingly, a signal transmission delay can be reduced as compared to the configuration illustrated inFIG. 13.

Each of the switches M1to M3is connected to all of the switches T1to T3. Further, each of the switches M4to M7is connected to all of the switches T4to T6. Further, each of the switches M8and M9is connected to all of the switches T7to T9. That is, the second-stage switches and the third-stage switches are connected in the same manner as in the conventional Fat Tree illustrated inFIG. 13.

The switches M1to M9receive signals from the switches B1to B9.

The switches M1to M3transmit a signal having a destination node number of 1 mod 9, to the switch T1. Further, the switches M1to M3transmit a signal having a destination node number of 4 mod 9, to the switch T2. Further, the switches M1to M3transmit a signal having a destination node number of 7 mod 9, to the switch T3.

The switches M4to M6transmit a signal having a destination node number of 2 mod 9, to the switch T4. Further, the switches M4to M6transmit a signal having a destination node number of 5 mod 9, to the switch T5. Further, the switches M4to M6transmit a signal having a destination node number of 8 mod 9, to the switch T6.

The switches M7to M9transmit a signal having a destination node number of 3 mod 9, to the switch T7. Further, the switches M7to M9transmit a signal having a destination node number of 6 mod 9, to the switch T8. Further, the switches M7to M9transmit a signal having a destination node number of 0 mod 9, to the switch T9.

Each of the switches T1to T9memorizes the path from it to each node. In the phase9, the switches T1to T9receive signals having a destination node number of 1 mod 9. Then, the switches T1to T9specify the second-stage switch connected to the first-stage switch connected to the node having the destination node number of the received signal, and transmit a signal to the specified second-stage switch. The switches T1to T9correspond to an example of a “third transmitting unit”.

In this manner, when the first-stage to third-stage switches are connected and the shift communication pattern is used to perform communication, a path contention of transmission signals does not occur in each path. Accordingly, a wide band can be secured in signal transmission.

Further, when the first-stage to third-stage switches are connected in this manner, the number of adjacent connection switches for the switches B1to B9can be increased as compared to the case ofFIG. 13. That is, the network apparatus according to this embodiment can reduce the average number of hops, as compared to the conventional configuration illustrated inFIG. 13. Accordingly, the network apparatus according to this embodiment can reduce a signal transmission delay as compared to the conventional configuration illustrated inFIG. 13.

Next, in this embodiment, the signal transmission from the switches M1to M9to the switches T1to T9will be described in detail with reference toFIG. 1.

In the phase9, the switch M1receives signals transmitted to the nodes10,13, and16. Thus, the switch M1transmits a signal transmitted to the node10, to the switch T1, transmits a signal transmitted to the node13, to the switch T2, and transmits a signal transmitted to the node16, to the switch T3. Further, the switch M2receives signals transmitted to the nodes19,22, and25. Thus, the switch M2transmits a signal transmitted to the node19, to the switch T1, transmits a signal transmitted to the node22, to the switch T2, and transmits a signal transmitted to the node25, to the switch T3. Further, the switch M3receives signals transmitted to the nodes1,4, and7. Thus, the switch M3transmits a signal transmitted to the node1, to the switch T1, transmits a signal transmitted to the node4, to the switch T2, and transmits a signal transmitted to the node7, to the switch T3.

Further, in the phase9, the switch M4receives signals transmitted to the nodes20,14, and17. Thus, the switch M4transmits a signal transmitted to the node20, to the switch T4, transmits a signal transmitted to the node14, to the switch T5, and transmits a signal transmitted to the node17, to the switch T6. Further, the switch M5receives signals transmitted to the nodes2,23, and26. Thus, the switch M5transmits a signal transmitted to the node2, to the switch T4, transmits a signal transmitted to the node23, to the switch T5, and transmits a signal transmitted to the node26, to the switch T6. Further, the switch M6receives signals transmitted to the nodes11,5, and8. Thus, the switch M6transmits a signal transmitted to the node11, to the switch T4, transmits a signal transmitted to the node5, to the switch T5, and transmits a signal transmitted to the node8, to the switch T6.

Further, in the phase9, the switch M7receives signals transmitted to the nodes21,24, and18. Thus, the switch M7transmits a signal transmitted to the node21, to the switch T7, transmits a signal transmitted to the node24, to the switch T8, and transmits a signal transmitted to the node18, to the switch T9. Further, the switch M8receives signals transmitted to the nodes3,6, and27. Thus, the switch M8transmits a signal transmitted to the node3, to the switch T7, transmits a signal transmitted to the node6, to the switch T8, and transmits a signal transmitted to the node27, to the switch T9. Further, the switch M9receives signals transmitted to the nodes12,15, and9. Thus, the switch M9transmits a signal transmitted to the node12, to the switch T7, transmits a signal transmitted to the node15, to the switch T8, and transmits a signal transmitted to the node9, to the switch T9.

Herein, the numbers marked under the switches T1to T9ofFIG. 1represent the destination node numbers of the signals received from the second-stage switches in the phase9. Further, the MOD functions marked on top of the switches T1to T9represent the condition satisfied by the destination of the signals received by the second-stage switches of the switches T1to T9in the phase9. In this way, each of the third-stage switches receives three signals transmitted from the different second-stage switches. That is, if the shift communication pattern is used, when signals are transmitted from the second-stage switches to the third-stage switches, since two or more signals may not flow through the same path, a wide band can be secured in signal transmission.

The case of the phase9of the shift communication pattern has been described above. However, also in other phases, two or more signals are not transmitted through the same path. Accordingly, the network apparatus according to this embodiment can secure a wide band in signal transmission when communication is performed using the shift communication pattern.

Second Embodiment

FIG. 3is a diagram illustrating a configuration of a network apparatus according to a second embodiment. The second embodiment is different from the first embodiment in terms of the connection between the first-stage switches and the second-stage switches in the network apparatus. Thus, the following description will be made on the connection between the first-stage switches and the second-stage switches. In particular, the connection and the signal flow after the second-stage switches are identical to those of the first embodiment, and thus the redundant description will not be repeated.

Thus, a description will be given of a method of connecting the first-stage switches and the second-stage switches in the network apparatus according to the second embodiment.

In addition to the above group classification, the first-stage switches are selected and classified on a three-by-three basis in ascending order of number as illustrated inFIG. 2. That is, the switches B1to B9are classified into the switches B1to B3enclosed by a solid line204, the switches B4to B6enclosed by a dotted line205, and the switches B7to B9enclosed by a dashed dotted line206. Then, the group enclosed by the solid line204will be referred to as the group A, the group enclosed by the dotted line205will be referred to as the group B, and the group enclosed by the dashed dotted line206will be referred to as the group C. Further, the groups1-1to1-3will be referred to collectively as “other groups”. Further, the groups A to C will be referred to collectively as the “first-stage group”. Further, the group B is next to the group A, the group C is next to the group B, and the group A is next to the group C.

First, the switches M1to M3are connected in the same way as in the Fat Tree configuration illustrated inFIG. 13. That is, the switch M1is connected to the switches B1, B2, and B3. The switch M2is connected to the switches B4, B5, and B6. Further, the switch M3is connected to the switches B7, B8, and B9.

Thereafter, the switch M4selects the switch B1corresponding to the group1-1of the group A. Further, the switch M4selects the switch B5corresponding to the group1-2from the group B next to the group A. Further, the switch M4selects the switch B9corresponding to the group1-3from the group C next to the group B.

Then, the switch M5selects the switch included in the other group identical to that selected by the switch M4, from the first-stage group next to the first-stage group from which the switch M4selects the switch included in each of the other groups. Further, the switch M6selects the switch included in the other group identical to that selected by the switch M5, from the group next to the first-stage group from which the switch M5selects the switch included in each of the other groups.

Thereafter, the switch M7selects the switch B1corresponding to the group1-1of the group A. Further, the switch M7selects the switch B8corresponding to the group1-2from the group C that is second-next to the group A. Further, the switch M7selects the switch B6corresponding to the group1-3from the group B that is second-next to the group C.

Then, the switch M8selects the switch included in the other group identical to that selected by the switch M4, from the first-stage group next to the first-stage group from which the switch M7selects the switch included in each of the other groups. Further, the switch M9selects the switch included in the other group identical to that selected by the switch M5, from the group next to the first-stage group from which the switch M8selects the switch included in each of the other groups.

When the connection points are selected as above, the connection state illustrated inFIG. 3is obtained. Thus, a description will be given of the communication in the phase9in the case where the shift communication pattern is used to perform all-to-all communication in the connection state ofFIG. 3.

The switch B1transmits the signal received from the node1and transmitted to the node10, to the switch M1, because the destination node number is 1 mod 3. Further, the switch B1transmits the signal received from the node2and transmitted to the node11, to the switch M4, because the destination node number is 2 mod 3. Further, the switch B1transmits the signal received from the node3and transmitted to the node12, to the switch M7, because the destination node number is 0 mod 3.

The switch B2transmits the signal received from the node4and transmitted to the node13, to the switch M1, because the destination node number is 1 mod 3. Further, the switch B2transmits the signal received from the node5and transmitted to the node14, to the switch M4, because the destination node number is 2 mod 3. Further, the switch B2transmits the signal received from the node6and transmitted to the node15, to the switch M8, because the destination node number is 0 mod 3.

The switch B3transmits the signal received from the node7and transmitted to the node16, to the switch M1, because the destination node number is 1 mod 3. Further, the switch B3transmits the signal received from the node8and transmitted to the node17, to the switch M5, because the destination node number is 2 mod 3. Further, the switch B3transmits the signal received from the node9and transmitted to the node18, to the switch M9, because the destination node number is 0 mod 3.

The switch B4transmits the signal received from the node10and transmitted to the node19, to the switch M2, because the destination node number is 1 mod 3. Further, the switch B4transmits the signal received from the node11and transmitted to the node20, to the switch M5, because the destination node number is 2 mod 3. Further, the switch B4transmits the signal received from the node12and transmitted to the node21, to the switch M8, because the destination node number is 0 mod 3.

The switch B5transmits the signal received from the node13and transmitted to the node22, to the switch M2, because the destination node number is 1 mod 3. Further, the switch B5transmits the signal received from the node14and transmitted to the node23, to the switch M4, because the destination node number is 2 mod 3. Further, the switch B5transmits the signal received from the node15and transmitted to the node24, to the switch M9, because the destination node number is 0 mod 3.

The switch B6transmits the signal received from the node16and transmitted to the node25, to the switch M2, because the destination node number is 1 mod 3. Further, the switch B6transmits the signal received from the node17and transmitted to the node26, to the switch M6, because the destination node number is 2 mod 3. Further, the switch B6transmits the signal received from the node18and transmitted to the node27, to the switch M7, because the destination node number is 0 mod 3.

The switch B7transmits the signal received from the node19and transmitted to the node1, to the switch M3, because the destination node number is 1 mod 3. Also, the switch B7transmits the signal received from the node20and transmitted to the node2, to the switch M6, because the destination node number is 2 mod 3. Also, the switch B7transmits the signal received from the node21and transmitted to the node3, to the switch M8, because the destination node number is 0 mod 3.

The switch B8transmits the signal received from the node22and transmitted to the node4, to the switch M3, because the destination node number is 1 mod 3. Further, the switch B8transmits the signal received from the node23and transmitted to the node5, to the switch M5, because the destination node number is 2 mod 3. Further, the switch B8transmits the signal received from the node24and transmitted to the node6, to the switch M7, because the destination node number is 0 mod 3.

The switch B9transmits the signal received from the node25and transmitted to the node7, to the switch M3, because the destination node number is 1 mod 3. Further, the switch B9transmits the signal received from the node26and transmitted to the node8, to the switch M4, because the destination node number is 2 mod 3. Further, the switch B9transmits the signal received from the node27and transmitted to the node9, to the switch M8, because the destination node number is 0 mod 3.

Further, each of the switches B1to B9stores the number of the node connected thereto. When receiving the signal transmitted from the switches M1to M9to the node connected thereto, each of the switches B1to B9transmits the signal to the node having the destination node number. Further, each of the switches M1to M9stores the number of the node connected to the first-stage switch connected thereto. When the destination node number of the received signal is the number of the node connected to the first-stage switch connected thereto, each of the switches M1to M9transmits the signal to the first-stage switch connected to the node having the node number.

Herein, the numbers marked under the switches M1to M9ofFIG. 3represent the destination node numbers of the signals received from the first-stage switches of the respective switches M1to M9in the phase9. As illustrated inFIG. 3, each of the second-stage switches receives three signals transmitted from the different first-stage switches. That is, if the shift communication pattern is used, when signals are transmitted from the first-stage switches to the second-stage switches, since two or more signals may not flow through the same path, a wide band can be secured in signal transmission.

Further, the destination of the received signal of each of the switches M1to M9is the node number transmitted to the different third-stage switches. Thus, if the shift communication pattern is used, when signals are transmitted from the second-stage switches to the third-stage switches, since two or more signals may not flow through the same path, a wide band can be secured in signal transmission.

Further, the number of adjacent connection switches for the switches B1to B9is increased, as compared to the case ofFIG. 13. For example, inFIG. 13, the adjacent connection switches for the switch B1are only two switches B2and B3. On the other hand, inFIG. 3, the adjacent connection switches for the switch B1are six switches B2, B3, B5, B6, B8and B9. In this manner, the network apparatus according to this embodiment reduces the average number of hops, as compared to the conventional configuration illustrated inFIG. 13.

Further, while all of n3nodes are provided in this configuration example, the first-stage switch and some nodes frequently used in the conventional Fat Tree configuration may be removed. For example, in the conventional Fat Tree, a path contention can be avoided even when the switch B8or B9and the subordinate node thereof are removed from the configuration ofFIG. 13.

Further, when the subordinate nodes20and21of the switch B7are removed from the configuration, some path contention occurs in all-to-all communication. However, the degree of the path contention is about the same as in the conventional Fat Tree configuration, and it is practically no problem.

FIG. 4is a configuration diagram of a network apparatus according to a modification of the second embodiment. The case of using 8-port switches will now be described as the modification of the second embodiment. The network apparatus according to the modification includes 16 switches B1to B16as the first-stage switches, 16 switches M1to M16as the second-stage switches, and 16 switches T1to T16as the third-stage switches.

Further, provided are 64 nodes allocated node numbers of 1 to 64. Numerals marked in a region enclosed by a solid line300represent the numbers of nodes connected to the corresponding first-stage switches. In particular, nodes4(i−1)+1 to4iare connected to the switch Bi (i=1, 2, . . . , 16).

Herein, the switches B1to B16are selected on a four-by-four basis in ascending order of number and are classified into four groups. The group of switches B1to B4is the group301, the group of switches B5to B8is the group302, the group of switches B9to B12is the group303, and the group of switches B13to B16is the group304. The groups301to304will be referred to collectively as the “first-stage group”.

The switch M1selects four switches from the group301. Then, the switch M2selects the switch included in the other group identical to that selected by the switch M1, from the first-stage group next to the first-stage group from which the switch M1selects the switch included in each of the other groups. Further, the switch M3selects the switch included in the other group identical to that selected by the switch M2, from the group next to the first-stage group from which the switch M2selects the switch included in each of the other groups. Further, the switch M4selects the switch included in the other group identical to that selected by the switch M3, from the first-stage group next to the first-stage group from which the switch M3selects the switch included in each of the other groups.

Thereafter, the switch M5sequentially selects the next group sequentially from the group301, and selects the first-stage switches having switch numbers of 1 mod 4, 2 mod 4, 3 mod 4, and 0 mod 4, corresponding to the order of the sequentially-selected groups. In this case, the switch M5selects the groups in the order of groups301,302,303, and304. Then, the switches M6to M8select the first-stage switches, like the switches M2to M4with respect to the switch M1.

Thereafter, the switch M9sequentially selects the second-next group sequentially from the group301, and selects the first-stage switches having switch numbers of 1 mod 4, 2 mod 4, 3 mod 4, and 0 mod 4, corresponding to the order of the sequentially-selected groups. In this case, the switch M9selects the groups in the order of groups301,303,301, and303. Then, the switches M10to M12select the first-stage switches, like the switches M2to M4with respect to the switch M1.

Thereafter, the switch M13sequentially selects the third-next group sequentially from the group301, and selects the first-stage switches having switch numbers of 1 mod 4, 2 mod 4, 3 mod 4, and 0 mod 4, corresponding to the order of the sequentially-selected groups. In this case, the switch M13selects the groups in the order of groups301,304,303, and302. Then, the switches M14to M16select the first-stage switches, like the switches M2to M4with respect to the switch M1.

When the switches B1to M16connected to the switches M1to M16are selected, the connection between the switches M1to M16and the switches B1to B16is identical to the connection illustrated inFIG. 4.

A description will now be given of a signal flow in the phase9in the case where all-to-all communication is performed by the shift communication pattern when the connection is made as illustrated inFIG. 4. In the phase9, the node number of a signal transmitted by each node is the number corresponding to each node marked in a region enclosed by a solid line305.

When a signal is transmitted from each node with respect to the node number enclosed by the solid line305, the switches M1to M16receive signals having destination node numbers corresponding to numbers marked thereunder. These numbers are different, and a signal path contention does not occur in the path connecting the switches M1to M16and the switches B1to B16. Accordingly, a wide band can be secured in signal transmission between the first-stage switches and the second-stage switches.

Signals having destination node numbers corresponding to numbers marked under the switches M1to M16are transmitted to the different third-stage switches connected respectively to the switches M1to M16. Therefore, a signal path contention does not occur in the path connecting the switches M1to M16and the switches T1to T16. Accordingly, a wide band can be secured in signal transmission between the second-stage switches and the third-stage switches.

Further, the number of adjacent connection switches for the switches B1to B9is increased as compared to the case of using the conventional Fat Tree configuration. In the conventional Fat Tree configuration, the adjacent connection switches for the switch B1are only switches B2to B6. On the other hand, inFIG. 4, for example, the adjacent connection switches for the switch B1include not only the switches B2to B6but also the switches B6, B8, B10to B12, and B14to B16. In this way, the network apparatus according to this embodiment reduces the average number of hops, as compared to the conventional configuration illustrated inFIG. 13.

As described above, in this embodiment, for the connection, the number of the first-stage groups, from which the first-stage switches connected to the second-stage switch of each of the second-stage groups are selected, is sequentially increased like ‘first-next’ and ‘second-next’. In the three-stage network apparatus using 2n-port switches, if n is a prime number, the same connection method as described in this embodiment may be used to maximize the number (n(n−1)) of adjacent connection switches for each of the first-stage switches. In the connection method described in this embodiment, if n is not a prime number, when the first-stage switch is selected, some of the common first-stage switches are selected from the second-stage switches connected to the selected switch.

Third Embodiment

A network apparatus according to a third embodiment will be described below.FIG. 5is a configuration diagram of a network apparatus according to the third embodiment. The network apparatus according to this embodiment uses a different method from the second embodiment, thereby maximizing the number of adjacent connection switches for the first-stage switches when n is not a prime number. Thus, a description will now be given of a connection method that maximizes the number of adjacent connection switches for the first-stage switches when n is not a prime number.

A description will now be given of a method that maximizes the number of adjacent connection switches for the first-stage switches in the case of a three-stage network apparatus using 8-port switches in the modification according to the first embodiment.

FIG. 6Ais a diagram illustrating the connection relation between the second-stage switches and the first-stage switches in the connections ofFIG. 4. The squares501to504ofFIG. 6Aindicate that the second-stage switches having numbers marked to the left toward the paper plane of squares and the first-stage switches having numbers arranged in a row have a connection relation. For example, B1to B4arranged in the M1row of the square501indicate that the switches B1to B4and the switch M1have a connection relation. Further, the column of each square indicates that the switches have node numbers of 1 mod 4, 2 mod 4, 3 mod 4, and 0 mod 5 sequentially from the left toward the paper plane.

FIG. 6Bis a diagram illustrating the connection relation between the second-stage switches and the first-stage group in the connections ofFIG. 4.FIG. 6Billustrates changing the first-stage switches ofFIG. 4into the last numeral of the number of the first-stage group to which the first-stage switches belong to.

InFIG. 6A, it can be seen that the switches B1and B3are connected to the switch M1in lattices511and512. Further, it can be seen that the switches B1and B3are connected to the switch M9in lattices531and532. That is, the switches B1and B3have two paths connected to the common second-stage switches. When this overlap is eliminated, the number of adjacent connection switches is further increased. Thus, B3may not appear in the row of M9in order to eliminate an overlap between the lattices511and512and the lattices531and532. Thus, an aligned Latin square may be constructed such that a square503is not identical in both of the horizontal direction and the vertical direction.

A description will now be given of the elimination of an overlap between the lattices521and522and the lattices541and542in the squares502and504. InFIG. 6B, a square506and a square508are together a Latin square. However, an overlap occurs between the lattices561and562and the lattices581and582. Thus, each of the squares505to508is mutually-orthogonal Latin square (hereinafter referred to as “mutually-orthogonal Latin square”), thereby eliminating the overlap.

In the mutually-orthogonal Latin square, for example, if the length of one side is n, when n is the power of a prime number, n−1 mutually-orthogonal Latin squares are present and each of them can be calculated. This calculation may be performed by a known mutually-orthogonal Latin square derivation method.

Thus, the length of one side of each square ofFIG. 6Bis 4, which is the square of a prime number of 2. Thus, a known mutually-orthogonal Latin square derivation method may be used to calculate a mutually-orthogonal Latin square for each square ofFIG. 6B.FIG. 7Ais a diagram illustrating the connection between the second-stage switches and the first-stage group according to mutually orthogonal Latin squares. Each of the squares601to604is the conversion of each of the squares505to508ofFIG. 6Binto a mutually orthogonal Latin square. Each of the squares601to604is a mutually orthogonal Latin square.

Next, switches, which are included in the first-stage group of the last number corresponding to the squares601to604and respectively have node numbers of 1 mod 4, 2 mod 4, 3 mod 4, and 0 mod 5 sequentially from the left toward the paper plane of each square, are allocated to generate the squares605to608illustrated inFIG. 7B.FIG. 7Bis a diagram illustrating the connection between the second-stage switches and the first-stage switches according to orthogonal Latin squares. That is, the second-stage switches and the first-stage switches may be connected to form the connection illustrated inFIG. 7B, thus generating a network apparatus maximizing the number of adjacent connection switches. When the second-stage switches and the first-stage switches are connected to form the connection illustrated inFIG. 7B, it is possible to generate a network apparatus having the connection illustrated inFIG. 5.

In the network apparatus illustrated inFIG. 5, the number of adjacent connection switches becomes 12 with respect to any of the first-stage switches, and it is maximized.

As described above, in the network apparatus according to this embodiment, when the first-stage switches, which are connected vertically to the respective second-stage switches in each of the second-stage groups, are arranged in a row and squares, in which the remainders of columns divided by 4 are 1, 2, 3, and 0, are generated, each of the squares becomes a mutually-orthogonal Latin square. Accordingly, the number of adjacent connection switches for the first-stage switches can be maximized, and the average number of hops can be minimized.

A description will now be given of the number of adjacent connection switches in the case where the connection is made by the connection method of the second and third embodiments when the number of switch ports used is changed.FIG. 8is a diagram illustrating the number of adjacent connection switches corresponding to the number of switch ports. Further,FIG. 9is a diagram illustrating the ratio of adjacent connection switches corresponding to the number of switch ports.

InFIG. 8, the vertical axis represents the number of adjacent connection switches, and the horizontal axis represents the number of switch ports. A graph701ofFIG. 8represents a change in the number of adjacent connection switches in the case where the connection method of the second embodiment is used. Further, a triangular dot represents the number of adjacent connection switches in the case where the connection method of the third embodiment is used to change the connection method of the second embodiment. Further, a graph702represents a change in the number of adjacent connection switches in the case where the conventional Fat Tree connection method is used.

InFIG. 9, the vertical axis represents the theoretical maximum ratio of adjacent connection switches to all of the other switches, and the horizontal axis represents the number of switch ports. A graph703ofFIG. 9represents a change in the ratio of adjacent connection switches in the case where the connection method of the second embodiment is used. Further, a triangular dot represents the ratio of adjacent connection switches in the case where connection method of the third embodiment is used to change the connection method of the second embodiment.

It can be seen from the graph702ofFIG. 8that the conventional connection method suppresses an increase in the number of adjacent connection switches even when the number of switch ports is increased. On the other hand, it can be seen from the graph701that the connection method of the second embodiment greatly increases the number of adjacent connection switches with an increase in the number of switch ports. Further, according to the conventional connection method, the ratio of adjacent connection switches is reduced because the ratio of an increase in the number of adjacent connection switches to an increase in the number of switch ports is low. On the other hand, as represented by the graph703, the ratio of adjacent connection switches in several ports can be increased by the connection method of the second embodiment. That is, the connection method of the second embodiment can greatly reduce the average number of hops, as compared to the conventional connection method.

Further, as represented by the triangular dots ofFIG. 8, when the number of ports is the power of a prime number, the connection method of the third embodiment can increase and maximize the number of adjacent connection switches, as compared to the case of the second embodiment. Further, as represented by the triangular dots ofFIG. 9, when the number of ports is the power of a prime number, the connection method of the third embodiment can increase the ratio of adjacent connection switches to the theoretical maximum value.

Fourth Embodiment

A network managing apparatus according to a fourth embodiment will be described below.FIG. 10is a block diagram of a network managing apparatus according to the fourth embodiment. The network managing apparatus according to the fourth embodiment is an apparatus that obtains the connections between first-stage to third-stage switches using one of the first to third embodiments and presents the obtained connection states to an operator. The case of obtaining the connections using the method of the first embodiment will be described below.

An input controlling unit801receives the number of switch ports that is input using a keyboard by an operator. For example, when 6-port switches are used, the input controlling unit801receives 6 as the number of ports. Herein, the input controlling unit801outputs the received number of ports to a switch arranging unit802.

The switch arranging unit802calculates the number of first-stage to third-stage switches, respectively, by squaring the half of the received number of ports. For example, in the case of 6-port switches, the switch arranging unit802includes first-stage to third-stage switches, each of which is provided with 9 switches. The switch arranging unit802notifies a display controlling unit805such that the first-stage switches are arranged in parallel at the very bottom of a screen. Thereafter, the switch arranging unit802notifies the display controlling unit805such that the second-stage switches are arranged in parallel above the first-stage switches on the screen. Further, the switch arranging unit802notifies the display controlling unit805such that the third-stage switches are arranged in parallel above the second-stage switches on the screen.

Further, the switch arranging unit802waves the numbers of B1, B2, . . . , from left to right toward the screen with respect to the first-stage switches arranged in the screen. Further, the switch arranging unit802waves the numbers of M1, M2, . . . , from left to right toward the screen with respect to the second-stage switches arranged in the screen. Further, the switch arranging unit802waves the numbers of T1, T2, . . . , from left to right toward the screen with respect to the third-stage switches arranged in the screen.

Thereafter, the switch arranging unit802outputs the number of switch ports and each switch number to a first interconnecting unit803and a second interconnecting unit804.

The first interconnecting unit803receives the number of switch ports and each switch number from the switch arranging unit802.

The first interconnecting unit803classifies the second-stage switches into groups in ascending order of number corresponding to the half of the number of ports. Further, the first interconnecting unit803classifies the third-stage switches into groups in ascending order of number corresponding to the half of the number of ports.

The first interconnecting unit803obtains the connections that connect the switches included in each group of the second-stage switches to all switches included in the group of the third-stage switches located on a position corresponding to the screen. Thereafter, the first interconnecting unit803outputs the obtained connections to the display controlling unit805.

The second interconnecting unit804receives the number of switch ports and each switch number from the switch arranging unit802.

Thereafter, the second interconnecting unit804obtains the connections that connect the first-stage switches to the second-stage switches using the connecting method of the first embodiment. Thereafter, the second interconnecting unit804outputs the obtained interconnections to the display controlling unit805.

The display controlling unit805displays the first-stage to third-stage switches on the screen according to an instruction from the switch arranging unit802. Thereafter, the display controlling unit805displays the connection between the second-stage switches and the third-stage switches on the screen according to the interconnections received from the first interconnecting unit803. Thereafter, the display controlling unit805displays the connection between the first-stage switches and the second-stage switches on the screen according to the interconnections received from the second interconnecting unit804.

A flow of determining the connections between the first-stage switches and the second-stage switches will be described below with reference toFIG. 11.FIG. 11is a flow chart illustrating the determination of the connections between the first-stage switches and the second-stage switches. A three-stage configuration using the 6-port switches illustrated inFIG. 1will be described below as an example. Further, in the following description, when each switch is illustrated, each switch is described with names to which the switch numbers illustrated inFIG. 1are added. That is, each switch is represented by switches B1to B9, M1to M9, and T1to T9. Further, each node is described with names to which the node numbers illustrated inFIG. 1are added. That is, each node is represented by nodes1to27.

Thereafter, the first interconnecting unit803classifies the second-stage and third-stage switches into groups in numerical order by number corresponding to the half of the number of ports of the second-stage switches. Thereafter, in step S2, the first interconnecting unit803mutually connects all switches of the second-stage switch groups to all switches of the third-stage switch groups, which vertically correspond to one another.

In step S3, the second interconnecting unit804classifies the second-stage switches into three second-stage groups i (i=1, 2, 3) in order of switch number. In the second-stage groups, the group number is sequentially increased from the group1, and the group number is returned to the group1when the group number becomes the group3. That is, the second-stage group4becomes the second-stage group1.

In step S4, the second interconnecting unit804classifies the first-stage switches into three first-stage groups j (j=1, 2, 3) in order of switch number. In the first-stage groups, the group number is sequentially increased from the group1, and the group number is returned to the group1when the group number becomes the group3. That is, the first-stage group4becomes the first-stage group1.

Further, the second interconnecting unit804classifies the switches of the first-stage switches, which have the same remainders when the minimum node numbers of the connected nodes are divided by 9, into the same groups. That is, the switches B1to B9are classified into three groups of the switches B1, B4, and B7, the switches B2, B5, and B8, and the switches B3, B6, and B9. In step S5, the switches B1, B4, and B7will be referred to as the group1-1. Further, the switches B2, B5, and B8will be referred to as the group1-2. Further, the switches B3, B6, and B9will be referred to as the group1-3.

In step S6, the second interconnecting unit804sets i=1.

In step S7, the second interconnecting unit804selects the switch of the group1-1from the first-stage group1with respect to the first switch whose switch number of the second-stage group i is minimum.

Thereafter, in step S8, the second interconnecting unit804selects the switch of the group1-2from the first-stage group1+(i−1) with respect to the first switch of the second group i.

Further, in step S9, the second interconnecting unit804selects the switch of the group1-3from the first-stage group1+2(i−1) with respect to the first switch of the second group i.

In step S10, the second interconnecting unit804determines whether i=3. If not i=3 (NO in step S10), the second interconnecting unit804sets i=i+1 in step S11and returns to step S7.

On the contrary, if i=3 (YES in step S10), the second interconnecting unit804extracts the group adjacent to the first-stage group selected relative to the first switch in each selection of the groups1-1to1-3, with respect to the switch adjacent to the first switch of the second-stage group. Thereafter, in step S12, the second interconnecting unit804selects the switch of the same group, from which the first switches of the groups1-1to1-3are selected, from the extracted first-stage group, with respect to the first switch adjacent from the first switch.

Further, the second interconnecting unit804extracts the second group adjacent from the first-stage group selected relative to the first switch in each selection of the groups1-1to1-3, with respect to the second switch adjacent from the first switch of each second-stage group. Thereafter, in step S13, the second interconnecting unit804selects the switch of the same group, from which the first switches of the groups1-1to1-3are selected, from the extracted first-stage group, with respect to the second switch adjacent from the first switch.

In the exemplary embodiment, although the case of the connecting method of the first embodiment has been described, the cases of the second and third embodiments are equally applied.

As described above, the network managing apparatus according to the exemplary embodiment provides the connection state that can minimize the average number of hops and secure a wide bandwidth in signal transmission. Therefore, a user can easily know the connection state that can minimize the average number of hops and secure a wide bandwidth in signal transmission, and can rapidly construct an appropriate network.

Further, another example of a flow of determining connections between the first-stage switches and the second-stage switches will be described with reference toFIG. 12.FIG. 12is a flow chart illustrating another example of the determination of connections between the first-stage switches and the second-stage switches. A three-stage configuration using the 6-port switches illustrated inFIG. 1will be described as an example. Further, in the following description, when each switch is illustrated, each switch is described with names to which the switch numbers illustrated inFIG. 1are added. That is, each switch is represented by switches B1to B9, M1to M9, and T1to T9. Further, each node is described with names to which the node numbers illustrated inFIG. 1are added. That is, each node is represented by nodes1to27.

Thereafter, the first interconnecting unit803classifies the second-stage and third-stage switches into groups in numerical order by number corresponding to the half of the number of ports of the second-stage switches. Thereafter, in step S22, the first interconnecting unit803mutually connects all switches of the second-stage switch groups to all switches of the third-stage switch groups, which vertically correspond to one another.

Thereafter, the second interconnecting unit804classifies the switches of the first-stage switches, which have the same remainders when the minimum node numbers of the connected nodes are divided by 9, into the same groups. That is, the switches B1to B9are classified into three groups of the switches B1, B4, and B7, the switches B2, B5, and B8, and the switches B3, B6, and B9. In step S23, the switches B1, B4, and B7will be referred to as the group1-1. Further, the switches B2, B5, and B8will be referred to as the group1-2. Further, the switches B3, B6, and B9will be referred to as the group1-3.

Further, in step S24, the second interconnecting unit804sets j=0.

Further, in step S25, the second interconnecting unit804sets i=1.

In step S26, the second interconnecting unit804selects the first-stage switch, which is connected to a switch M(3j+1), from the group (1−i).

Thereafter, in step S27, the second interconnecting unit804selects the first-stage switch, which is connected to a switch M(3j+2), from the remaining switches of the group (1−i).

Thereafter, in step S28, the second interconnecting unit804selects the first-stage switch, which is connected to a switch M(3j+3), from the remaining switches of the group (1−i).

In step S29, the second interconnecting unit804determines whether i=3. If not i=3 (NO in step S29), the second interconnecting unit804sets i=i+1 in step S30, and returns to step S26.

On the contrary, if i=3 (YES in step S29), the second interconnecting unit804determines whether 3j+3=27 in step S31. If not 3j+3=27 (NO in step S31), the second interconnecting unit804sets j=j+1 in step S32and returns to step S25.

On the contrary, if 3j+3=27 (YES in step S31), the second interconnecting unit804determines whether the average of the adjacent connection switches for the first-stage switch is greater than 3 in step S33. If the average of the adjacent connection switches is 3 or less (NO in step S33), the second interconnecting unit804returns to step S24.

On the contrary, if the average of the adjacent connection switches is greater than 3 (YES in step S33), the second interconnecting unit804determines a connection state between the first-stage switch and the second-stage switch. Thereafter, in step S34, the display controlling unit805displays, on a displaying unit, a state in which each switch arranged by the switch arranging unit802is connected by an interconnection determined by the first interconnecting unit803and the second interconnecting unit804.

It has been described above that a connection is computed because the number of adjacent connection switches is larger than that of the conventional Fat Tree configuration. However, this may be implemented by any other methods. For example, the second interconnecting unit802may perform the process of steps S4to S9with respect to the combination of all the first-stage switches, memorize the average of the number of adjacent connection switches in each case, and determine an interconnection that maximizes the average value.

According to an aspect of the network apparatus and the network managing apparatus, a wide band can be secured and a delay can be reduced in all-to-all signal transmission.