Method for creating routing information in an ATM communications network

In an ATM communication network which operates in accordance with the principles of the PNNI protocol of the ATM Forum (ATM Forum Technical Committee Private Network Node Interface (PNNI) Specification, Version 1.0), an output switching node S (S as "source node") a connection setup message from a terminal connected to it must be in this for the entire route through the network up to the destination switching node D (D as "destination node"), to which the desired destination connection terminal is connected or to which a connection transition is to be made to another network, route information is determined and this is added in PNNI protocol in accordance with the form of the connection setup message before forwarding to the subsequent switching node.

Said ATM communication networks can be structured into numerous subnetworks ("peer groups") consisting of physical switching nodes ("nodes") and physical connecting lines ("physical links"). According to the PNNI protocol, the nodes of a (hierarchically lowest) peer group determine from their midst a so-called representative node ("peer group leader"), which the entire peer group in the form of a single, logical, model-like node ("logical group node" or also called "parent node") in a hierarchically higher peer group. A hierarchically higher peer group is formed from a plurality of such parent nodes and the connecting lines which network them, a connecting line ("logical link") representing a logically formed subset of all those physical connecting lines, which each connect two border nodes of the two neighboring (hierarchically lower - "child" -) peer groups and have been given an identical identifier (called an "aggregation token") by administration.

The hierarchy can continue recursively in further hierarchical levels: Even in the hierarchically higher peer group, a peer group leader election can take place again. The selected peer group leader again represents the entire hierarchy area built up below in a hierarchically higher peer group than if this hierarchy area were a single node. In this peer group there are again logical, model-like connecting lines between two neighboring nodes each, such a connecting line in turn representing a logically formed subset of all those physical connecting lines which are delimited by a physical switching node in the neighboring hierarchy areas.

The PNNI protocol-compliant hierarchical model network (for the view: 3-dimensional grid) is completed by the addition of further, purely logical connecting lines, the so-called "uplinks", which PNNI protocol according to two nodes (physically - if the node at the lower end of the uplink is a physical node - or logically) from hierarchically different peer groups.

Thus, from the border node of a hierarchically lowest peer group, which is connected to a border node in a neighboring peer group via a physical connection line, an uplink (also called "initial uplink") leads to a representative node, the so-called "upnode", ie that representative node "ancestor node" (ie parent node, or "grandparent node", or grand ... grandparent node) of the neighboring border node, which is a direct neighboring node in a common hierarchically higher peer group for exactly one specific ancestor node of this border node. Such an (initial) uplink has the consequence that all ancestor nodes (of the border node on this side), which, however, each belong to a hierarchically lower peer group than said common hierarchically higher peer group, each have an uplink (also called an “induced uplink”) ) contribute to the upnode to the hierarchy picture.

The hierarchical structuring, which is ultimately based on the corresponding configuration data of the individual nodes, can be handled very flexibly. In particular, the individual nodes of a grand ... grandparent peer group can have a different number of sub-hierarchy levels including related peer groups.

The PNNI protocol-compliant exchange of data packets, "Hello Packets" and PNNI topology status data packets ("Topology State Packets" - PTSPs) via so-called routing control channels ensures that every physical switching node a hierarchically lowest peer group has the same knowledge regarding the topology of this and all hierarchically higher peer groups in the hierarchy above, including all uplinks, furthermore acquires the same knowledge regarding the occupancy of all nodes and connecting lines contained therein as well as the same knowledge regarding their properties (accessibility, capabilities, characteristics, costs).

The acquired topology knowledge can be saved in the form of a graph G1 in a node. In it, the respective current switching node (the one that created this graph G1 for itself) is particularly marked as the output node S.

If a terminal connected to the output node now expresses the wish to be connected to the terminal of a certain target address, the data exchanged via PNNI routing protocol in graph G1 allow the target node D to be determined which proclaims the accessibility of the target terminal and thereby hierarchically lowest possible peer group.

However, the ATM Forum Technical Committee Private Network Node Interface (PNNI) in the Specification, Version 1.0, Appendix H does not provide the option to search for advantageous detours via one or more peer groups with a return to the previously passed peer group involved, so it is sometimes not possible to fulfill a mediation request accordingly.

The object of the method according to the invention is to determine the best possible connection path, taking into account the existing occupancy information relating to all nodes and connecting lines of this graph G1 and taking into account their properties, as well as the expressed claims of the present connection request, and to convert the determined information into route information in such a way that that this meets the PNNI protocol regulations, and therefore the connection setup message can be given on the way to the next connection node. The object is achieved by the method based on the preamble of claim 1 explained in the document "Topology Aggregation for Hierarchical Routing in ATM Networks" by Whay C. Lee XP570739 by its characterizing features.

A graph G2 is determined which emerges from the graph G1 by removing all those nodes and connecting lines from the graph G1 which do not withstand the conditions mentioned.

An optimal connection path is then determined in such a way that detours via hierarchically higher peer groups with subsequent return to hierarchically lower peer groups that have already passed are also taken into account. The exit nodes and re-entry nodes are different for one and the same peer group, otherwise such a detour would be a highly unnecessary loop and not an optimal connection route.

Even if everything following concentrates on detour-like routes ("routes"), it should not be overlooked that the method according to the invention also finds this for the normal case, in which a best, detour-free route is available, and is just as correct for it forms corresponding routing information.

The resulting optimal route can in principle contain any number of transitions from a hierarchically higher to a hierarchically lower peer group and vice versa from a hierarchically lower to a hierarchically higher peer group, with in principle any number, ie zero, one, two, ... or n <= 102 hierarchy levels may be skipped.

According to the PNNI protocol, the connection setup message is given the route information as a result of information elements, so-called "designated transit list information elements (DTLs)", with a preceding information element (repeat indicator) information element relating to the handling of the stack of these DTLs (push and pop operations). Each information element DTL contains the description of exactly one route through exactly one hierarchical peer group in the form of one or more node-link pairs and a pointer that points to one of these node-link pairs. The route described by the top information element DTL of the cellar store begins with the output node S and only contains information regarding nodes and connecting lines in the hierarchically lowest peer group and possibly ends with the specification of an uplink, which leads to an upnode, in which the route continues , as described in the next lower basement DTL. Each next lower DTL in the cellar memory contains information for a route through the hierarchically next higher peer group, starting with the relevant ancestor node of the output node, possibly followed by further node and connection line information from the same peer group and possibly Uplink specification as a conclusion. The deepest DTL contains information regarding a route through the hierarchically highest required peer group, starting with the specification of the relevant ancestor node of the starting node and ending with a node in whose hierarchy area the target node with the connected target terminal is located.

The described design of the DTL basement memory in accordance with the PNNI protocol initially gives the impression that routes which consist of any sequences of hierarchically higher and hierarchically lower nodes cannot be taken into account and that it would be advisable to search for the algorithm to design an optimal connection path in such a way that routes with such sequences (i.e. with detours via hierarchically higher peer groups) are eliminated from the outset, as is the case in the specification of the PNNI protocol, version 1.0, Appendix H.

However, the method according to the invention solves the display problem of such a detour route and also forms routing information for it which meets the regulations in accordance with the PNNI protocol.

It is characteristic of the solution according to the invention that an equivalent sequence of nodes and connecting lines is derived from a predetermined sequence of hierarchically higher and hierarchically lower nodes, in which uplinks would certainly also have to be passed in the downward direction, which sequence never descending in terms of the hierarchical levels of these nodes runs in which uplinks are never to be passed in the downward direction. As a tribute to what has been achieved in this way, one and the same hierarchically higher (logical) node can occur several times in the sequence (loops), but due to the specified connecting lines, it is clearly ensured that the exit and re-entry limit nodes in the relevant child peer groups are always different, which ultimately means that one and the same physical node is never passed more than once.

The determination of the best route in a switching node determining the route and the route information is explained below:

A graph G3 is derived from the above-mentioned graph G2, in that all ancestor nodes of the output node S are removed, as are all (horizontal) connecting lines leading away from these, which would lead from these ancestor nodes to their neighboring nodes in the corresponding hierarchically higher peer groups. as well as all induced uplinks leading away from these ancestor nodes in the upward direction.

According to the PNNI protocol, a Dijkstra routing algorithm, for example, is used to determine a best route from the starting node S to the destination node D in a known manner based on the graph G3, the uplinks remaining in the graph G3 being no different from all other (horizontal) Connection lines are to be treated.

The best route is a sequence F1 in general notation: node-n (= D), link-n-1, .., node-i + 1, link-i, .., link-1, node-1 ( = S).

It is in the nature of the Dijkstra routing algorithm that the best route is determined not only to a single, specific destination node D, but to all nodes of the network, from which the route of interest to the destination node D is subsequently sought out . The Dijkstra algorithm first determines this route in the form of the sequence F1.

Then you reverse the order and form the sequence F2: node-1 (= S), link-1, .., link-i, node-i + 1, .., link-n-1, node-n (= D).

The physical output node node-1 = S is naturally of the lowest hierarchical level. According to the invention, all other nodes may be hierarchically higher or hierarchically lower physical or logical nodes as often as required. In particular, the target node node-n = D need not necessarily be the hierarchically highest among the nodes occurring in the sequence.

A link link-i turns out to be horizontal if node-i and node-i + 1 are assigned to the same hierarchy level, i.e. belong to the same hierarchical peer group. A link link-i proves to be an uplink in the upward direction (or downward direction) if the hierarchical level of node node-i is smaller (or larger) than the hierarchical level of node node-i + 1.

According to the invention, a sequence F3 is derived from the sequence F2, in which the nodes never descend in the given sequence with regard to their hierarchical level. Switching nodes and links from F2 may be replaced or deleted by others. To do this, use an auxiliary variable, here called CurrentNodeLevel, which is initialized with the hierarchy level of the node node-1 = S, and a second Boolean auxiliary variable, here called Below-HighestReachedLevel, which is initialized with FALSE. In an iteration loop, starting with node node-1 = S, you go through all the components of sequence F2 (the left and the nodes) and sometimes make replacements or deletions - see the following algorithm:<img file="EP0781007B1_D0001.tif" /><img file="EP0781007B1_D0002.tif" />

Sub-task 1:

For a given uplink, the associated horizontal link must be determined in the higher hierarchical peer group:

The graph G1 has m links (horizontal links and uplinks taken together). The number k from the set 1,2, ..., m represents a pointer to the interesting information regarding exactly one link (eg its identity information). In particular, there is a table RelationTbl with m elements. The elements represent the assignment chain from the initial uplink to the possibly induced uplink, to the uplink which may be induced again, etc., to the horizontal link induced in a higher hierarchical peer group:<img file="EP0781007B1_D0003.tif" /> which does ______________ mean:<img file="EP0781007B1_D0004.tif" /><img file="EP0781007B1_D0005.tif" />

Suppose the link-i to be replaced corresponds to j_q-1 , the table RelationTbl is run through until you get to RelationTbl [j_s]: = hits. j_s indicates the horizontal link to be used.

Subtask 2:

There is a table of the type for all m links of the graph G1: LinkLevelTbl [k] = lowest hierarchical level of the two delimitation nodes of the link k; for all k = 1, .., m. link-i is through j_q-1 designated. The table RelationTbl from RelationTbl [j_q-1] to go from one link to the next link and it always compares CurrentNodeLevel with the entries in LinkLevelTbl. Assume that the value of CurrentNodeLevel is equal to the value of Link-LevelTbl [j_r-1], so j_r-1 the link you are looking for, which should replace link-i.

From sequence F3 you can create a sequence F4 as follows:<img file="EP0781007B1_D0006.tif" />

A sequence of DTLs is formed from F4 by fragmenting the sequence F3 behind each uplink and from each partial sequence generated in this way forms a DTL information element with PNNI protocol-compatible syntax - which completely describes the task according to the invention for the output node S.

According to the invention, the inclusion of a loop (in the sense of the method according to the invention, a detour via one or more peer groups with a return to an already passed peer group at a re-entry node that has not yet happened) can also be replenished when the information elements of the route information are replenished when the connection establishment message arrives in one physical switching nodes (transit nodes). This is illustrated below with the arrival of a connection setup message in the first physical switching node of a hierarchically lowest peer group:

If the current hierarchically lowest peer group is left when a connection setup message is forwarded, the relevant, stack-top DTL must first be removed. If a certain hierarchy area is left, all those information elements DTL on top of the stack that contain route sections through the respective peer groups of the hierarchy area to be left must be removed beforehand. If a hierarchically lowest peer group is re-entered when forwarding a connection setup message, new route sections must be determined and new DTLs relating to this must be formed. The pointers in the individual DTLs must always be set or be advanced that when a connection setup message is received, the pointers of all received DTLs each point to a node-link pair, which either contains the receiving physical, hierarchically lowest node or one of its ancestor nodes.

The boundary node (S '), as an entry node in a further peer group, determines a new best route section up to a destination node D'. The destination node D 'can be found in the node-link pair which follows the node-link pair in the uppermost stack of the received DTLs, to which the relevant pointer points.

If this is not possible because the pointer already points to the last pair of node-links, the same applies to the next DTL in the stack, etc. It is in the spirit of the invention that the PNNI protocol prescribes that the link information received, namely how to get to the node node D ', must also be fully complied with. Any attempt, for example, to get there even better could result in a better route section, but at the same time also result in the hierarchical area represented by the destination node D 'not being entered at the intended border node, from where the continuation of the connection setup could end in a dead end . This means that in addition to D ', the horizontal link link-to-D' is also determined. Link-to-D 'is taken from the node-link pair which belongs to the DTL in which D' is located and to which the relevant pointer points when the DTL is received.

The boundary node S ', which takes into account that it is only a transit node for the connection request and that the received DTL cellar memory is incomplete, therefore forms a possibly reduced graph G1' from its own graph G1 as follows:

All nodes - including adjacent links - with a hierarchy level greater than or equal to the hierarchy level of node D 'are removed from graph G1, but not D' itself and also not those uplinks for which D 'is upnode and thereby the link-to-D ' assigned. For all uplinks that have D 'as an upnode, do the following check:

As in task 1, an uplink is j_q-1 assignable. Run through the table RelationTbl starting from Relation-Tb1 [j_q-1] until an entry RelationTbl [j_s]: = hits. If j_s corresponds to the link-to-D ', the uplink may remain in graph G1'. Otherwise it will be removed.

Starting from G1 ', the graphs G2' and G3 'are formed, quite analogously to how the output node S formed the graphs G2' and G3 ', and as described above, a DTL stack is determined, where S' is the function of S and D. 'takes over the function of D (see description above).

All DTLs with the exception of the very last one (which contains D ') are taken over from the resulting DTL cellar storage and thus the DTL cellar storage to be forwarded is completed.

The inclusion of the abovementioned loops in the method according to the invention requires that connecting lines exist which are connected to different border switching nodes of the first subnetwork or different representatives of the subnetworks at a higher hierarchical level; This is the only way to find alternative routes.

If more economical alternatives to loopless routes for a connection with the desired properties could be determined, route information containing information about the checked connection lines was generated. In the method according to the invention, no knowledge of the network topology of the further subnetworks (peer groups) - that is to say outside of the own branch of the hierarchy in the switching node which carries out the routing - is required. However, it is essential that there are at least two connecting lines from different border switching nodes of the first subnet to at least one further subnet.

The method according to the invention can be implemented in the output switching node if the output switching node and the destination switching node belong to the same subnetwork and the routing information is formed with one or more loops to further subnetworks. For the first time, the output switching node for establishing a connection can be used to form routing information for a connection establishment message (setup). A1-alternatively, it is possible that the output switching node forming the route information in the sense of the method according to the invention is itself a transit communication system, so that the connection setup message (setup) is received and the route information contained therein is further processed and used for the following route to the destination. Switching node is trained.

Identifiable bottlenecks can also be avoided if loops are included in the route if the outgoing switching nodes belong to a first subnetwork and the target switching nodes belong to a further subnetwork.

It is possible not to include connecting lines between subnetworks of predeterminable higher order in the route search by using a common assignment symbol for several connecting lines. This means that the inclusion of further subnets in the route search is restricted to certain areas of the hierarchy of the ATM communication network. If one assumes that subnetworks are structured on the basis of geographical criteria, route searches over geographically distant subnetworks are prevented, whereby an upper limit for the resources and thus the economic effort for establishing a connection can be specified.

According to a further advantageous embodiment of the method according to the invention, further subnetworks can be included in such a way that a subnetwork is left several times or loops are permitted in further subnetworks, without which the connection would not have been possible under the same conditions. This extension of the test for the presence of connecting lines also enables connections to be implemented in which the routing resources and switching capacities of the first subnet are severely limited.

Further advantageous developments of the method according to the invention can be found in the remaining subordinate claims.

The formation of the route information in switching nodes of an ATM communication network is explained in more detail using FIGS. 1 to 3. Figures 1 to 3 show one and the same ATM communication network for a route search and formation of route information, but seen from different switching nodes.<dl id="dl0001" compact="compact"><dt>Figure 1</dt><dd>shows the ATM communication network from the point of view of the exit switching node A.1,</dd><dt>Figure 2</dt><dd>shows the ATM communication network from the point of view of the transit switching node B.2 and</dd><dt>Figure 3</dt><dd>shows the ATM communication network from the point of view of the further transit switching node C.1.</dd></dl>

The hierarchy of the ATM communication network shows three subnetworks TA, TB, TC by way of example. The first subnet TA comprises the physical nodes A.1..6. For the connection setup to be considered, node A.1 is the outgoing switching node and node A.6 is the destination switching node. However, these starting and destination nodes do not have to be in the same peer group (subnet), and detours can only be used by a transit node. Another subnet TB comprises the nodes B.1..5 and an additional further subnet TC the nodes C.1..4. The subnetworks TA, TB (peer groups of the lowest hierarchy level) are combined at a higher hierarchy level to form a network group TAB (peer group of the higher hierarchy level) and are each represented by a logical node A, B. At a higher hierarchical level, this network group TAB (peer group) with the further additional subnet TC is combined to form a network group TABC, with a logical node AB representing the network group higher hierarchical level TAB and a logical node C representing the further additional subnet TC.

The nodes are interconnected by physical connection lines (physical links). Links pb1,2,3 and pc1,2 between nodes of different subnets are assigned additional information.

Legend:

<dl id="dl0002" compact="compact"><dt>Initial letter</dt><dd>p = physical link, h = horizontal link, u = initial uplink, U = induced uplink</dd></dl> pb1, hb1, and ub1, or pb2, hb2, and ub2 or pb3, hb3, and ub3 or pc1, uc1, Uc1 and hc1 or pc2, uc2, Uc2 and hc2 are identified by way of example with an identical aggregation token .

The nodes in which the route information is formed according to FIGS. 1 to 3 only see the thickly outlined peer groups (the knowledge base stored in the respective node includes information about these peer groups). Instead of the physical connection lines that lead out of the hierarchically lowest peer group, you see the uplinks assigned in this regard. Only the respective border nodes themselves know about this assignment, but do not share this knowledge with the other nodes of the peer group.

We are looking for a route from the starting node A.1 to the destination node A.6. The connecting lines pa5, pa6 are blocked, which would allow a direct route from the output node A.1 to the destination node A.6. The physical path that the connection establishment should take is shown in bold.

Activity of the starting node A.1:

In the output node A.1 let the graph G1 be stored in the form of a list of links together with their delimiting nodes, ie G1 (A.1) - see FIG. 1: (pa2: A.2, A.1), (pa3: A.3, A.1), (pa4: A.4, A.5), (pa5: A.5, A.1), (pa6 : A.6, A.5), (ub1: A.2, B), (ub2: A.3, B), (ub3: A.4, B), (uc1: A.5, C), (uc2: A.6, C). (hb1: B, A), (hb2: B, A), (hb3: B, A), (Uc1: A, C), (Uc2: A, C), (hc1 C, AB), (hc2: C, AB),

The blocked lines are removed, namely (pa5: A.5, A.1), (pa6: A.6, A.5), and the graph G2 (A.1) is determined: (pa2: A.2, A.1), (pa3: A.3, A.1), (pa4: A.4, A.5), (ub1: A.2, B), (ub2: A .3, B), (ub3: A.4, B), (uc1: A.5, C), (uc2: A.6, C). (hb1: B, A), (hb2: B, A), (hb3: B, A), (Uc1: A, C), (Uc2: A, C), (hc1: C, AB), (hc2: C, AB),

All ancestor nodes including adjacent lines are removed, namely (hb1: B, A), (hb2: B, A), (hb3: B, A), (Uc1: A, C), (Uc2: A, C), (hc1: C, AB), (hc2: C, AB), and thus graph G3 (A.1) determines: (pa2: A.2, A.1), (pa3: A.3, A.1), (pa4: A.4, A.5), (ub1: A.2, B), (ub2: A .3, B), (ub3: A.4, B), (uc1: A.5, C), (uc2: A.6, C).

The application of the Dijkstra routing algorithm results in the sequence F1: Destination Node D = A.6, uc2, C, uc1, A.5, pa4, A.4, ub3, B, ub1, A.2, pa2, A.1 = Source Node S.

The reverse order = F2 is: Source Node S = A.1, pa2, A.2, ub1, B, ub3, A.4, pa4, A.5, uc1, C, uc2, A.6 = Destination Node D .

Sequence F3 is determined: A.1, pa2, A.2, ub1, B, hb3, A, Uc1, C, hc2, AB.

Sequence F4 is determined: A.1, pa2, A.2, ub1, A, hb1, B, hb3, A, Uc1, AB, hc1, C, hc2, AB.

From this, the information element of the DTL basement storage is derived. The sequence F4 is divided after each uplink and an information element DTL is formed from each of the resulting partial sequences as they are sent to the next physical node. The pointer points to the umpteenth bracketed node-link pair.<ul id="ul0001" list-style="none" compact="compact"><li>1.DTL: (A.1, pa2), (A.2, ub1), pointer = 2</li><li>2.DTL: (A, hb1), (B, hb3), (A, Uc1), pointer = 1</li><li>3.DTL: (AB, hc1), (C, hc2), (AB, x'00 00 00 00), pointer = 1</li></ul>

Activity of transit node B.2 (entry node in the further subnet TB):

The transit node B.2 receives the following route information ri:<ul id="ul0002" list-style="none" compact="compact"><li>1. DTL: (A, hb1), (B, hb3), (A, Uc1), pointer = 2</li><li>2nd DTL: (AB, hc1), (C, hc2), (AB, x'00 00 00 00), pointer = 1</li></ul>

Node B.2 has saved the network it sees as graph G1 (B.2) - see Figure 2 with a thick frame: (pb4: B.1, B.2), (pb5: B.1, B.5), (pb6: B.4, B.5), (pb7: B.3, B.4), (pb8: B.2, B.3), (ua1: B.2, A), (ua2: B.3, A), (ua3: B.4, A), (hb1: B, A), (hb2: B, A), (hb3: B, A), (Uc1: A, C), (Uc2: A, C), (hc1: C, AB), (hc2: C, AB).

Because it is a transit traffic, G1 '(B.2) is formed by initially D '(B.2) and Link-to-D' (B.2) is determined: D '(B.2) = A Link-to-D '(B.2) = hb3.

In the transit node, graph G1 (B.2) removes all nodes from the hierarchical level greater than or equal to logical node A, as well as the related links, except for D '(B.2) = A itself and excluding those uplinks for A is upnode and correlated with link-to-D '(B.2) = hb3. The graph G1 '(B.2) is created: (pb4: B.1, B.2), (pb5: B.1, B.5), (pb6: B.4, B.5), (pb7: B.3, B.4), (pb8: B.2, B.3), (ua3: B.4, A)

Since no blockings are known to the transit node B.1, graph G1 '(B.2) graph G2' (B.2) applies Since no ancestor nodes of B.1 can be removed from it, G1 '(B.2) = G2' (B.2) = G3 '(B.2) applies.

The Dijkstra routing algorithm applied results in a sequence F1: D '(B.2) = A, ua3, B.4, pb7, B.3, pb8, B.2 = S' (B.2)

In reverse order, this results in F2: S '(B.2) = B.2, pb8, B.3, pb7, B.4, ua3, A = D' (B.2)

The operation to form F3 does not result in any changes, ie sequence F2 = sequence F3. Sequence F4 is formed from sequence F3: S '(B.2) = B.2, pb8, B.3, pb7, B.4, ua3, B, hb3, A = D' (B.2)

The information elements DTLs of the route information ri are formed from sequence F4:<ul id="ul0003" list-style="none" compact="compact"><li>1. DTL: (B.2, pb8), (B.3, pb7), (B.4, ua3), pointer = 2</li><li>2nd DTL: (B, hb3), A = D '(B.2), pointer = 1</li></ul> of which one does not take over the last (= 2nd) DTL.

The following routing information ri is thus sent in DTL basement format from the entry node B.2 to the further node B.3 in the further subnet TB:<ul id="ul0004" list-style="none" compact="compact"><li>1. DTL, newly formed: (B.2, pb8), (B.3, pb7), (B.4, ua3), pointer = 2</li><li>2nd DTL, received and processed: (A, hb1), (B, hb3), (A,, Uc1), pointer = 2</li><li>3rd DTL, received and processed: (AB, hc1), (C, hc2), (AB, x'00 00 00 00), pointer = 1</li></ul>

<u>Activity of transit node A.4 in the first subnet TA:</u> The node A.4 receives the following routing information ri:<ul id="ul0005" list-style="none" compact="compact"><li>1. DTL: (A, hb1), (B, hb3), (A, Uc1), pointer = 3</li><li>2nd DTL: (AB, hc1), (C, hc2), (AB, x'00 00 00 00), pointer = 1</li></ul>

Node A.4 has saved the network it sees as graph G1 (A.4), which corresponds to graph G1 (A.1) stored by output node A.1, see above and see FIG. 1 (thickly outlined).

Because it is a transit traffic G1 '(A.4) is formed by initially D '(A.4) and Link-to-D' (A.4) is determined:    D '(A.4) = C    Link-to-D '(A.4) = hc1. From graph G1 (A.4) all nodes of the hierarchy level greater than or equal to the hierarchy level of D '(A.4) = C, as well as the related links are removed, except for D' (A.4) = C itself and excluded those uplinks for which D '(A.4) C is upnode and correlated with Link-to-D' (A.4) = hc1.

The result is graph G1 '(A.4): (pa2: A.2, A.1), (pa3: A.3, A.1), (pa4: A.4, A.5), (pa5: A.5, A.1), (pa6 : A.6, A.5), (ub1: A.2, B), (ub2: A.3, B), (ub3: A.4, B), (uc1: A.5, C), (hb1: B, A), (hb2: B, A), (hb3: B, A), (Uc1: A, C)

The blocked links are removed and the result is graph G2 '(A.4): (pa2: A.2, A.1), (pa3: A.3, A.1), (pa4: A.4, A.5), (ub1: A.2, B), (ub2: A.3, B), (ub3: A.4, B), (uc1 A.5, C), (hb1: B, A), (hb2: B, A), (hb3: B, A), (Uc1: A, C)

If all of the ancestor nodes and the adjacent connecting cables are still removed, the result is graph G3 '(A.4): (pa2: A.2, A.1), (pa3: A.3, A.1), (pa4: A.4, A.5), (ub1: A.2, B), (ub2: A.3, B), (ub3: A.4, B), (uc1: A.5, C).

Using Dijkstra routing algorithm, the following route F1 is determined as the best route from transit node A.4 to representative C of the additional further subnetwork TC: D '(A.4) = C, uc1, A.5, pa4, A.4 = S' (A.4) Reversing the order results in F2: S '(A.4) = A.4, pa4, A.5, uc1, C = D' (A.4)

Since the sequence F2 is never descending with regard to the hierarchical level of the nodes that occur, the operations for forming the sequence F3 do not result in any changes: F3 = F2.

Sequence F4 is obtained from sequence F3, namely: S '(A.4) = A.4, pa4, A.5, uc1, AB, hc1, C = D' (A.4)

The following information element DTLs of the routing information ri are derived from the sequence F4:<ul id="ul0006" list-style="none" compact="compact"><li>1. DTL: (A.4, pa4), (A.5, uc1), pointer = 2</li><li>2nd DTL: (AB, hc1), (C, x'00 00 00 00), pointer = 1</li></ul> of which one does not take over the last (= 2nd) DTL.

The following DTL cellar memory content is thus transmitted from transit node A.4 to node A.5:<ul id="ul0007" list-style="none" compact="compact"><li>1. DTL, newly formed: (A.4, pa4), (A.5, uc1), pointer = 2</li><li>2nd DTL, received and processed: (A, hb1), (B, hb3), (A, Uc1), pointer = 3</li><li>3rd DTL, received and processed: (AB, hc1), (C, hc2), (AB, x'00 00 00 00), pointer = 1</li></ul>

<u>Activity of transit node C.1 in the additional TC subnet:</u> The node C.1 receives the following routing information ri:<ul id="ul0008" list-style="none" compact="compact"><li>1.DTL: (AB, hc1), (C, hc2), (AB, x'00 00 00 00), pointer = 2.</li></ul>

The node C.1 has saved the network it sees as a graph G1 (C.1), see FIG. 3: (pc3: C.1, C.2), (pc4: C.2, C.3), (pc5: C.3, C.4), (pc6: C.1, C.4), (uab1: C.1, AB), (uab2: C.4, AB) (hc1: C, AB), (Hc2: C, AB)

Because it is a transit traffic, G1 '(C.1) is formed by first determining D' (C.1) and Link-to-D '(C.1):    D '(C.1) = AB    Link-to-D '(C.1) = hc2. Graph G1 (C.1) removes all nodes from a hierarchy level greater than or equal to the hierarchy level of D '(C.1) AB, as well as the related links, but excluding D' (C.1) = C itself and exempted those uplinks for which D '(C.1) = AB is upnode and correlated with link-to-D' (C.1) = hc2. The graph G1 '(C.1) results: (pc3: C.1, C.2), (pc4: C.2, C.3), (pc5: C.3, C.4), (pc6: C.1, C.4), (uab2: C.4, AB)

Since the node C.1 does not find any blocked connecting lines (these are located in the first subnet TA) G1 '(C.1) = G2' (C.1). Because no additional ancestor nodes with regard to node C.1 can be removed: G1 '(C.1) = G2' (C.1) = G3 '(C.1)

With the help of the Dijkstra routing algorithm, node C.1 will determine the sequence F1 as the best route: D '(C.1) = AB, uab2, C.4, pc6, C.1 = S' (C.1)

Reversing the order results in F2: S '(C.1), pc6, C.4, uab2, AB = D' (C.1)

Since sequence F2 is never descending with regard to the hierarchical level of the nodes that occur, the operations for forming sequence F3 do not result in any changes: F3 = F2.

Sequence F4 is obtained from sequence F3, namely: S '(C.1) = C.1, pc6, C.4, uab2, C, hc2, AB = D' (C.1)

The following information elements DTL of the routing information ri are derived from the sequence F4:<ul id="ul0009" list-style="none" compact="compact"><li>1. DTL: (C.1, pc6), (C.4, uab2), pointer = 2</li><li>2nd DTL: (C, hc2), (AB, x'00 00 00 00), pointer = 1</li></ul> of which one does not take over the last (= 2nd) DTL.

The following DTL stack is thus transmitted from node C.1 to further node C.4 in the additional further subnetwork TC:<ul id="ul0010" list-style="none" compact="compact"><li>1. DTL, newly formed: (C.1, pc6), (C.4, uab2), pointer = 2</li><li>2nd DTL, received and processed: (AB, hc1), (C, hc2), (AB, x'00 00 00 00), pointer = 2.</li></ul>

<u>Activity of the re-entry node A.6 for the second re-entry into the first subnet TA:</u>The node A.6 receives the following routing information ri:<ul id="ul0011" list-style="none" compact="compact"><li>1. DTL: (AB, hc1) (C, hc2), (AB, x'00 00 00 00), pointer = 3.</li></ul>

Insofar as node A.6 recognizes that the target terminal is directly connected to it, it sends the connection setup message (setup) along the relevant UNI interface (no longer a PNNI interface) to it, whereby, according to the UNI protocol, none Information elements DTLs are given. The route is complete.