Method for modifying a multicast tree in a switching network

The present invention relates to a method of modifying a multi-address tree or multicast tree in a switch network having a plurality of network inlets and network outlets and a plurality of interconnected switch nodes having node inputs and node outputs each having addresses, wherein a first set of the network outlets to which directing a cell stream from one of the network inlets, is modified to a second set of network outlets to which the cell stream is to be routed, the addresses of the node outputs of each of the switching nodes from which the cell stream is output being stored in a routing table in the respective node.

Such a method is already known in the art, e.g. From the article "An ATM Switching Architecture with Intrinsic Multicast Capabilities for the Belgian Broadband Experiment" by M. De Prycker et. al., Proceedings ISS 1990, Stockholm, May 1990, Volume V, pages 111 to 118. Therein, the switching network is part of a local exchange, via the connections z. B. between an audio / television distribution center and subscriber stations can be made. The switching nodes are referred to as switching elements and operate according to the asynchronous transfer mode (ATM) protocol.

The cell stream routed from the above one network inlet to the first set of network outlets, ie, each network outlet from that first set, is thus routed through a cluster of branches, each of which passes through various of the above-mentioned switching elements such clusters in the above article and hereafter referred to as a multi-address tree or multicast tree. The modification of the first set of network outlets is to add network outlets to obtain the second set, ie, adding branches to the existing multiple address tree. For this purpose, whereby the switching network is a so-called connection-oriented switching network, so-called setup cells are set up via this tree with the widest possible use of its branches. Once the setup cell can no longer use such branches in a switch node and therefore has to exit the multiple address tree, the needed resources are allocated in this switch node and a new branch is added to the existing multiple address tree, thereby modifying the first set to a second set ,

In a so-called connectionless switching network, this latter method of modifying a multiple address tree can not be applied because it does not establish a connection to a setup cell but directs cells therein to their respective destination indicated by a routing tag. In this case, a central controller may be provided which controls all the switching nodes which direct cells of the cell stream to their respective destinations, the addition of a network outlet then requiring elaborate processing in this central controller. Namely, this central controller must control all the latter routing switches and notify them of the information necessary to modify the multi-address tree.

An object of the present invention is to provide a method of the above known type in which the modification of the first set of network outlets requires only a reduced processing overhead.

Another object of the present invention is to provide a method of the above known type which is also applicable to so-called connectionless switching networks.

According to the invention, this object is achieved in that the method comprises the following steps:

- transmitting a modification request message to the network inlets of each network outlet belonging to one but not both of said sets

in each switching node, receiving the modification request message at one of its node outputs, selectively transmitting the modification request message to the network inlets in case the node routing table lacks other addresses of node outputs than the one node output, or transmitting an acknowledgment message to said each network outlet in case: in the node routing table, there are other addresses of node outputs than said one node output.

In this way, a network outlet is easily added to or deleted from the first set because the modification request message is propagated to the network inlets until it reaches a branch of the above-mentioned multiple address tree that is at least to a different network outlet of the first set than the one to be added or deleted leads, ie until it reaches a switching node via which the cell stream is routed to at least one such other network outlet. Namely, if the routing table of the switching node encountered by the modification request message does not contain any other addresses of node outputs than that of the node output on which the message was received, then the cell stream over that switching node will not be routed to such other network outlet. If, on the other hand, the routing table contains the address of another output node than that of the originating node on which the message was received, then the cell stream is routed via that switching node to such other network outlet that the modification can be completed as indicated by the acknowledgment message.

Thus, when the modification request message reaches a switching node, it only needs to be checked whether its routing table contains addresses from node outputs other than the node output on which the message was received, such testing requiring only a reduced amount of processing, not central but decentralized. that is done at a switching node.

From the above, it will be apparent that the method is also applicable to a connectionless switching network, since it does not use a setup cell for modifying the multiple address tree. In addition, the method is also applicable for setting up a multiple address tree, ie, when the modification request message does not reach a branch of an already existing multiple address tree, or for deleting an existing multiple address tree, ie if all outputs are deleted from the first set and thus an empty second set is obtained.

Another feature of the present invention is that when the modification request message requests the addition of a network outlet to the first set of network outlets, it is propagated to the network inlets from the added network outlet and further propagated to the network inlets by a switching node that receives them if its routing table does not contain node output addresses.

In this way, a network outlet is added to the first set of network outlets to obtain the second set. Note that, in this case, the address of the output receiving node is obviously not included in the above routing table because the adding request message is only forwarded until the existing multiple address tree is found, after which the modification is completed, and before this multiple address tree is found , the add request message encounters only switch nodes by which the cell stream is not yet routed.

Another characteristic feature of the present invention is that, upon transmitting the acknowledgment message, each switching node receiving the modification request message further transmits a control message to control means included in the switching network, whereupon the control means transmits abort messages to the switching nodes for stopping the propagation of the modification request message.

In this way, once the addition is completed, the spread of the add request message is also aborted by other switch nodes, whereby the load on the switch network is completely terminated by the modification and the load in it is minimized.

Another feature of the present invention is that the modification request message requests deletion of a network outlet from the first set of network outlets and is directed from the deleted network outlet to the network inlets via a path established from the one network inlet to the deleted network outlet via which the cell stream is directed until it is received by a switching node, whose routing table contains at least two node output addresses.

This deletes a network outlet from the first set, thus preserving the second set. In this case, the deletion request message must be forwarded only through the surviving branch of the multicast tree to be deleted until a switch node is encountered where the multiple address tree divides into multiple branches. The address of the receiving node output is then obviously always included in the above routing table.

Yet another feature of the present invention is that each of the network outlets from the first set of network outlets are each selected from a group of network outlets, and that the modification of the first set of network outlets is to modify all said groups, each network outlet the second set of network outlets is thus selected from each of the modified groups of network outlets.

Thus, the cells of the cell stream are each routed through a number of different multiple address trees, each consisting of a cluster of branches between the one network inlet and the network outlets of the first set of network outlets, thereby distributing the load of the switching network caused by the cell flow over this switching network the likelihood of cell loss is reduced. In this case, in order to modify the first set of network outlets, a plurality of modification request messages must be transmitted equal to the plurality of multiple address trees.

In a further embodiment of the present invention, the set of network outlets has a set address, which is also stored in the table of switching nodes over which the cell stream is routed.

In this way, diverse multiple address trees can be set up simultaneously in the switch network, ie, various clusters of paths between one of the network inlets and a set of the network outlets, such as said first set, can co-exist in the switch network. Each such multiple address tree or cluster of paths is then identified by the set address, and only the node output addresses included in the routing table and concerning the respective multiple address tree, ie those with the respective set address, are checked to determine if the modification request message is still on the network inlets must be transmitted or not.

The above-mentioned and other objects and features of the invention will become more apparent and the invention itself will be better understood by reference to the following description of an embodiment taken in conjunction with the accompanying drawings. Show it:

Fig. 1 shows a routing part of a switching network arrangement in which a method according to the invention for modifying a multiple address tree is applied; and

FIG. 2 shows a switching node used in the arrangement of FIG. 1. FIG.

In front of the switching part of the switching network arrangement shown in Fig. 1, there is a distribution part constructed in a similar manner as the routing part. This routing part comprises four stages of eight switching nodes, a first stage with switching nodes SN11 to SN18, a second stage with switching nodes SN21 to SN28, a third stage with switching nodes SN31 to SN38 and a fourth stage with switching nodes SN41 to SN48, wherein the switching nodes such in Fig. 1 are interconnected. The switching part has sixteen network inlets IN1 to IN16 and sixteen network outlets OUT1 to OUT16. The fourth stage of the distribution part is connected to the first stage of the routing part, so that the switching network arrangement comprises eight stages with eight switching nodes each. It should be noted, however, that the four stages shown in Figure 1 can be used simultaneously as a distribution part and as a routing part of the switching network arrangement if its switching nodes are bidirectional. In this case, the inlets IN1 to IN16 are inlets of the switching part and outlets of the routing part, while the outlets OUT1 to OUT16 are a mirror plane where cells are reflected back into the switching network arrangement. The cells are then distributed in transmission from the inlets of the distribution part to the reflection plane and, when transmitting from this routing plane, are directed back to the outlets of the routing part.

The arrangement further comprises a control device CTRL. Note that in front of and behind the array are Termination Link Boards (not shown) that interface with the device and the participants.

Each of the switching nodes SN11 to SN48 has two node inputs 11 and 12 and two node outputs O1 and O2 as shown in Fig. 2 and includes a routing table RT for relating multiple address tree or set addresses MTI to node outputs of the respective switching node, ie each entry of the routing table has an address MTI and comprises two bits, one for each of the node outputs O1 and O2, which, when set to 1, indicate that a copy of the cell stream identified by the respective address MTI will be forwarded to the corresponding node output should. Thus, in the case of FIG. 2 given example, the cell stream with the address MTI arrives at the node input 11 or 12, forwarded to the node output O1, but not to the node output O2.

Such a switching network arrangement and switching nodes are known in the art and e.g. For example, in the article "Multicast Handling in an Self-routing Switch Architecture" by KJ Schrodi et. al., Proceedings ISS92, October 1992, pages 156-160. As described therein, multiple address or multicast connections directing a cell stream from a network ingress of the switch network arrangement to a plurality of its network outlets are required for various broadband ISDN (BISDN) services, e.g. For video conferencing, video retrieval for pay-TV, private virtual networks. Another important application is the video-on-demand service. For each of these services, a multiple address tree need not only be set up in the switch network arrangement, but it must also be easily customizable. Thus, it should be possible for a video-on-demand service to provide an additional subscriber with a video signal already being supplied to a plurality of other users; ie connecting this additional subscriber to an existing multiple address tree should be easy to do. Accordingly, it should also be possible to easily separate a subscriber from an existing multiple address tree.

An inventive method for modifying an existing multiple address tree, ie for adding or deleting a subscriber from a group of subscribers served via this multi-address tree, will now be described. This method is also applicable to building a new multiple address tree and deleting an existing multiple address tree.

First, it is assumed that a multiple address tree is set up with addresses MT1 in the switching network arrangement, e.g. With the method described in the above cited Schrodi article. This multicast tree is set up by the network inlets INS to network outlets OUT1, OUT2, OUT4, OUT8 and OUT14, ie Cells of a cell stream, which is assumed to be identified by the multi-address tree address MT1 and distributed via the switch network arrangement in its distribution stage (not shown), are supplied to the network inlets IN1 to IN16 and directed from there to each of the latter network outlets. For this purpose, z. B. for cells of the latter cell stream supplied to inlet IN5, the routing table of SN13 contains a 1 corresponding to both the address MT1, so that two copies of each cell are generated, one at the node output O1 of SN13 and the other at Node output O2 is output from SN13. Similarly, two copies of each cell are generated in switching node SN23, switching node SN31 and switching node SN41, with each node output relaying one of the two copies to these switching nodes. For each of the switching nodes over which the multiple address tree is established, the bits of the Routing Table entry with address MT1 are set to 1 if a copy of the cells of the cell stream is to be forwarded to the corresponding node output, otherwise set to 0, whereas the routing tables the other switching node have no entry with address MTI.

If the cell current MT1 z. For example, if also needs to be provided at the network outlet OUT9, an add request message is transmitted from the termination link to the switching node SN45. Such an add request message has the following form:

It is

REA an identifier indicating that the message is an add request message;

MTI an address field containing the address of the multiple address tree to which the node output specified in the node output field OUT is to be connected, ie the field MTI contains the addresses of the cell stream to be routed to this node output;

- OUT is the node output field mentioned above.

Consequently, the add request message transmitted to SN45 has the form:

Since the multiple address tree with addresses MT1 is not yet routed via SN45, which is indicated by the fact that both entries for the addresses MT1 in the routing table of SN45 are 0, this add request message is propagated from the network outlet OUT9 to the network inlets, ie it is transmitted by the switching node SN45 to which the network outlet OUT9 is connected, transmitted to both switching nodes SN33 and SN37. The routing tables of both these switching nodes are then checked, whereupon it is determined in both cases that the cell stream MT1 is not yet routed through any of these switching nodes. Therefore, the add request message is further distributed to the network inlets, ie to the switch nodes SN22 and SN24 through SN33 and to the switch nodes SN26 and SN28 through SN37.

Then, a check of the routing table of the switching node SN22 and of SN24, SN26 and SN28 leads to the conclusion that they already contain an entry for the address MT1 indicating that the cell stream MT1 is already being transmitted to one of their respective node outputs. Since the add request message z. B. is received at the node output O1 of the switching node SN24, the entry for the address MTI is adapted to the routing table of SN24 so that it now contains a 1 for both node outputs of SN24. The routing tables of SN22, SN26 and SN 28 are adjusted accordingly.

Further, SN24 sends a control message to the controller CTRL indicating that a connection has been made to the multiple address tree with addresses MT1, and therefore that further propagation of the corresponding add request message by other switching nodes may be discontinued. This control message must obviously contain the multiple address tree address MT1. The controller CTRL then transmits abort messages to all switching nodes of the switching network arrangement indicating that a further transmission of the corresponding add request message can be set. Each such abort message must obviously contain the multiple address tree address MT1. It should be noted that in the embodiment described herein, the transmission of the abort messages to the switching nodes of the same level can be restricted as the switching node from which the above control message originates, ie in the present case to the switching nodes SN121 to SN28, and that this transmission can even be limited to the switching nodes SN22, SN26 and SN28, since it can easily be verified that, with the exception of SN24, only these switching nodes of the second stage originated at a network outlet OUT9 and network infor- mation. It is also clear that in the latter case the control message must also contain the address of this network outlet, ie OUT9.

It should be noted that since the add request messages reach the existing multiple address tree at an equal level, the transmission of the control message to CTRL and the transmission of abort messages by CTRL is then not necessary, ie CTRL may be omitted.

The switching nodes SN22, SN24, SN26 and SN28 then also transmit a confirmation message to the network outlet OUT9, which is routed over the path followed by the corresponding add request message from OUT9 to SN24. This confirmation message has the following form:

It is

CNA, an identifier indicating that the message is an acknowledgment message confirming the addition of a network outlet to a multiple address tree;

MTI an address field containing the multiple address tree to which the node output specified in the node output field OUT is connected, ie the field MTI contains the address of the cell stream, which is now routed to this node output;

- OUT is the node output field mentioned above.

The confirmation messages transmitted to OUT9 thus have the following form:

When this acknowledgment message reaches the network outlet OUT 9, the multiple address tree is modified, and each cell of the cell stream MT1 is now also routed to the network outlet OUT9.

Thus, a simple and effective method of adding branches to a multi-address tree is provided which requires only a minimal amount of processing.

Similarly, if the cell stream routed via the multiple address tree with addresses MT1 z. For example, if the network outlet OUT8 is no longer to be supplied, then a deletion request message is transmitted from the termination link to the switching node SN44. Such a delete request message has the following form:

It is

RED an identifier indicating that the message is a delete request message;

MTI contains an address field containing the address of the multiple address tree from which the node specified in the node output field OUT is to be disconnected, ie the field MTI contains the address of the cell stream which is no longer to be routed to this node output;

- OUT is the node output field mentioned above.

The deletion request message transmitted to SN44 thus has the following form:

This deletion request message is transmitted from the node outlet OUT8 to the network inlets via the branches of the multiple address tree with addresses MT1 connected to OUT8, ie it is transmitted from the switching node SN44 to which the network outlet OUT8 is connected to the switching nodes SN32 and SN36. The routing tables of these switching nodes are then checked to find that the cell stream MT1 is transmitted only from SN32 and SN36 to SN44, but not to another switching node. Therefore, the cancellation request message from SN32 and SN36 is relayed via the branches of the multiple address tree to the network inlets, ie to the switching nodes SN21, SN23, SN25 and SN27.

Then, the routing tables of these switching nodes SN21, SN23, SN25 and SN27 are checked, leading to the conclusion that they transmit the cell stream not only to the switching node SN32 and SN36, but also to another switching node. Therefore, the entry for the MT1 addresses of the routing tables of SN21, SN23, SN25 and SN27 is adjusted to now include a 1 for the corresponding node outputs connected to SN32 and SN36.

The switching node SN32 then transmits an acknowledgment message to the network outlet OUT8, which is transmitted along the branch of the original multi-address tree leading to OUT8. This confirmation message according to the following form:

It is

- CND an identifier indicating that the message is an acknowledgment message confirming deletion of a network outlet from a multi-address tree;

MTI an address field containing the address of the multiple address tree from which the node output specified in the node output field OUT is disconnected, ie the field MTI contains the address of the cell stream which may no longer be routed to that node output;

- OUT is the node output field mentioned above.

The confirmation message transmitted to OUT8 thus has the following form:

When this acknowledgment message reaches the network outlet OUT8, the multiple address tree is modified and the cells of the cell stream MT1 are no longer routed to this network outlet OUT8.

Thus, a simple and effective method for deleting branches from a multiple address tree is provided which requires minimal processing overhead.

It should be noted that a distinction may be made between a multiple address tree identifier MTI identifying the multiple address tree and a multiple address connection identifier MCI identifying the connection, ie, the cell stream directed by the multiple address tree. In this way, different cell streams identified by different multi-address connection identifiers MCI can be routed through a same multi-address tree identified by a multiple address tree identifier MITI. In this case, it is obvious that the above description applies mutatis mutandis when changes to a multiple address connection are requested instead of a multiple address tree.

It should be noted that the method described above also applies to multiple address trees in so-called connection-oriented switching network arrangements in which different cells of a cell stream follow a similar path from a network inlet to a network outlet or network outlets. In this case, to minimize the load of the network when adding a branch to an existing multiple address tree, abort messages must be sent to cancel the further propagation of modification request messages once the addition has been made.