Method for Routing Messages

The invention relates to a method for transmitting messages in packet switching networks.

In packet switching networks, a message is not transmitted between a transmitter and a receiver in that a permanent connection is established between the transmitter and the receiver via which information is transmitted between transmitter and receiver. Instead, the information is transmitted in the form of packets which consist of an address header and an actual message component possibly of variable length which independently seek out their path to the receiver through the network. For this purpose, at each network node there is a switching element which evaluates the address information of each packet and passes on the packet along a suitable path.

Such packet switching networks are used in various fields of communication and data technology, especially in the field of parallel-computer connection networks. With the aid of such packet switching networks, considerably more information can be transmitted with the same line capacity than in conventional networks in which between each transmitter and each receiver a line which is reserved for this transmitter-receiver pair has to be established. Especially in parallel-computer connection networks, this method is based on the highest possible network throughput since the computing power of a parallel-computer system depends in a sensitive manner on the network throughput of its connection network. In such packet switching networks, when the switching units are involved in corresponding activity blockages occur repeatedly and greatly reduce the network throughput. These blockages can be avoided by correspondingly increasing the number of outputs per switching element or by controlling the network centrally, which, however generally would lead to unacceptably high costs or would involve a central control of the network, which is not desired.

An output of a switching element is blocked if at any time two or more packets require the same output to continue their path. Except for one, all these packets must be buffered. This can take place either completely within the switching element in question or be distributed over several switching elements.

From the literature, distributed methods are known which are used to transmit messages in packet switching networks. The common feature of these methods is that precisely one output is associated with each transmission node of the network at each receiver address. With correspondingly high capacity utilization of a network in parallel-computer connection networks, considerable blockages can occur at individual outputs, during which blockages a large number of packets have to be buffered. As a result of these blockages and the reduction of the network throughput associated with these blockages, perceptible degradations in performance can occur in parallel-computer systems.

The invention is based on the object of disclosing a method for routing messages in packet switching networks which avoids the described disadvantages of known methods and which is suitable for bringing about an increased network throughput in such networks. This object is achieved with the aid of a method for routing messages whereby

--each destination address at each switching element has a group of outputs of this switching element assigned to it,

--a free output is sought within this group,

--the message is delayed as long as no output is free within the group, and

--the individual outputs of a group are connected to different transmission paths.

Advantageous developments of the method include providing that the of a group of outputs takes place in such a way that each destination address has a sub-set of all the destination addresses allocated to it and each of these sub-sets has a group of outputs assigned to it. Further, in method may include:

--the set of all destination addresses has an address interval assigned to it which is subdivided into address sub-intervals,

--the set of all outputs has an output interval assigned to it which is subdivided into output sub-intervals and

--each address sub-interval has an output sub-interval allocated to it.

FIG. 1 shows a parallel-computer network.

FIG. 2 shows a network node of the network in FIG. 1, which comprises a transputer with a switching element (router).

FIG. 3 shows the improvement in interval routing according to the invention .

The invention is described in greater detail below with reference to a preferred exemplary embodiment and to the figures.

A typical area of application of the invention is connection networks in parallel-computer systems since, in such systems, intensive communication is required between the system elements, which communication generally leads to high network loading. The effects of the invention are more advantageous the higher the network loading. For this reason, the invention is described below with reference to an exemplary embodiment from the field of parallel-computer networks.

So-called transputer systems form an important class of parallel-computer systems. The technical foundations of these systems are described in the publication by D. May and P. Thompson, "Transputers and Routers: Components for Concurrent Machines", Proceedings of Japanese Occam User-Group, 1990. The publication by D. Pountain, "Virtual Channels; The next generation of Transputers", BYTE April 90, Europe and World: 3-12, Apr. 1990, contains a comprehensive presentation of the new transputer generation which operates with virtual addresses. The specialized terms used in this description from the field of parallel-computer systems are generally known and taken from the technical articles that have been cited.

FIG. 1 shows a typical connection network with six network nodes NN1, . . . , NN6. Each connection node here has for example the form indicated in FIG. 2 which consists of a connection element (router) and a processor element (transputer). Each network node is connected via a number of network connections SL to further network nodes, as can be seen in FIG. 1. Each network node contains, as illustrated in FIG. 2, a processor element, for example a transputer, which is connected via a number of transputers on the left to the connection element. During operation of such a transputer element, the individual processor elements T generally have to exchange information intensively. In this process, information must generally be transmitted from any processor element of a network node NNi to any other network node NNj. For reasons of cost, a direct networking of all these transputer elements is generally not possible.

With the aid of transputer elements and switching elements, very different network types with different processor numbers and different network topologies can be built up. The transmitting transputer T1 transmits a message to the receiving transputer T2 in the form of a packet (of variable length) which consists of an address header and the actual message. This packet is sent by the transmitting transputer via one of its connections TL to the switching component connected to it, which component subsequently carries out the further switching of the message. The switching component subsequently assigns the destination address of the message to a group of outputs which is suitable for transmitting the message to this destination address. The switching component carries out a search for a free output from this group of outputs. If the component finds a free output, it then transmits the message to this free output. If there is no free output in the group, the message to be transmitted is buffered in a waiting queue until an output within the group has become free.

The assignment of a group of outputs to a destination address can take place in various ways. A preferred method is based on known interval routing. The method of interval routing is described in the publication by J. van Leeuwen, R. B. Tan: "Interval-Routing", The Computer Journal, Vol. 30, Nov. 4, 1987, pp. 298-307. In this method, the entire address space, that is to say the set of all destination addresses is mapped onto an address interval AI, as can be seen in FIG. 3. This address interval is subdivided into a plurality of sub-intervals AI1 . . . , AI4. Each destination address is assigned an address sub-interval. In the known interval routing, each address sub-interval AIn is unambiguously assigned one output. According to the invention, instead, each address sub-interval AIn is assigned an interval of outputs.

If the destination address of a packet falls within an address sub-interval AIn, there is then a search for a free output in the group. If there is such a free output, the packet is then passed on via the output. Otherwise, the packet has to be buffered and placed in a waiting queue. The search for a free output can proceed here as follows (see attached Modula 2 program):

A local pointer (nextout) which is assigned to the group of network connections points, before the search process, to the successor of that output via which a packet of this group was last passed on. The pointer now runs from this position successively over all the outputs of the group until a free output is found. This can be indicated in this case for example via an appropriate signal (flag) at the outputs. If a free output is found, the packet is passed on via the output and the pointer remains at the subsequent position. Otherwise, the packet is placed in the waiting queue of that output to which the pointer pointed before the search process and the pointer is set to the subsequent output of this group.

Apart from the method of interval routing, any deterministic routing method can be generalized in this manner. Instead of an unambiguous network connection, according to the invention a group of network connections can be associated here with every destination address. In this way, not only is the optimum network connection for routing a message to a destination address used but also further (possibly) almost optimum network connections are used. In this way, the probability of blockage of a network connection is considerably reduced. The principle of operation of the invention is based on this idea.

Simulation results indicate that, with high network capacity utilization, the throughput of a binary cube network can be increased with the aid of the invention by more than 20%. A representative example of program subroutines for routing according to the present invention is set forth in Appendix 1.

Although other modifications and changes may be suggested by those skilled in the art, it is the intention of the inventors to embody within the patent warranted hereon all changes and modifications as reasonably and properly come within the scope of their contribution to the art.