DE102006034771B4 - System and method for routing connection requests - Google Patents

Abstract

A method for routing connection requests between nodes of an optical layer (OS) based multi-layer network comprising the steps of:
(a) determining possible signal paths (p, q) between the end nodes of the connections to be established for the different layers of the multi-layer network, the signal paths (p, q) being composed of links each connecting two nodes of the multi-layer network ;
(b) calculating a conflict graph for the detected signal paths (p) of the optical layer (OS);
(c) assigning a possible signal path (q) of a higher layer (HS) to each higher layer connection request (HS);
(d) determining a number for each link of the higher layer (HS) assigned signal path (Q) indicating how many times the respective higher link (HL) is contained in the higher layer (HS) assigned signal paths (Q);
(e) calculating for each higher link (HL) of a number (Z _OL ) indicating how many optical links (OL) to provide for the necessary higher link (HL) respectively ...

Description

The The invention relates to a system and method for routing connection requests between Nodes of an optical layer-based multilayer network.

The desired Bandwidth for data transmission takes constantly to. Therefore, data, especially in wide area networks (WANs), increasingly over Fiber optic networks transmitted. By means of WDM (Wavelength Division Multiplexing), the transmission capacity between Switching node increased. Many networks use point-to-point transmission optoelectronic, although the transmission of the data optically via optical fibers, however, the mediation between the nodes is done electronically. Increasingly, networks are also used in which, in addition to optical transmission also an optical mediation takes place. These networks are based mostly on an extension of conventional Networks to an optical layer. fiber optic networks form the backbone for the core networks Virtually all network operators, with the usual transfer rate 2.5 GBit / sec. or 10 Gbps. Per wavelength channel and per fiber.

1 shows an example of a WDM data network with fiber optic links. In a WDM network, the end users or end nodes of a connection to be established communicate via a WDM optical path. A lightwave path may extend over multiple fiber links. A lightwave path must have the same wavelength on all fiber connections it travels. WDM is a special multiplexing technique in which concurrently or temporally nested signals or packets of multiple messages are transmitted. Physically speaking, WDM is a special variant of the frequency multiplexing method, the frequencies being in the optical range. In WDM systems, several different wavelengths λ can be transmitted over a fiber because the individual wavelengths do not interfere with each other. This makes it possible to increase the overall bit rate to a multiple, without therefore higher transmission rates would be required for the individual channels. Each channel can thus operate with a relatively slow electronics, for example, a processing rate of 2.5 Gbit / sec. having. Since the individual transmission channels are independent of each other, the realization of so-called transparent channels is made possible. Here, the transmission format and the transmission rate on the different wavelengths λ can be selected independently. Thus, for example, it is possible to have a 2.5 Gbit / s SDH signal on a first wavelength λ ₁ , a 26.25 Mbit / sec ATM cell stream on another wavelength λ _2, and a third wavelength λ ₃ Any proprietary signal, for example, 5 Gbps. to transport or transfer. In addition, the scaling unit of WDM systems is significantly better than that of conventional TDM systems (TDM: Time Division Multiplexing).

At the in 1 As shown in the conventional WDM network, optical signal paths exist between the access nodes (access nodes A) A1 and A2 via the lightwave channel λ2, and exemplarily between the access nodes A3 and A4 via the lightwave channel λ1. A basic requirement for a WDM network is that only channels of different wavelengths can be multiplexed on a fiber. In a flexible optical switching node, when signals of the same wavelength are routed from different input fibers of the node to the same output fiber, a wavelength conflict occurs that makes multiplexing of the two channels impossible. Although there is the possibility of a wavelength conversion with the help of so-called wavelength converter, but these represent a considerable technical effort.

at The so-called Wavelength Routing (WR) networks eliminate the costly converter. Indeed make such wavelength routing networks much higher demands to the routing of the transmission links, about wavelength conflicts to avoid.

On the network protocols has the increasing spread of photonic techniques also big impact. conventional W-LAN networks mainly use SDH as a basic transmission technology for the Transport of different services, such as the transport of ATM cells, of IP data packets or of voice channels. Due to the increasing importance of IP as well as the fact that Many network operators already use SDH-based ATMs different mechanisms for the Transport of IP packets via ATM into consideration. this leads to to a protocol stack IP over ATM over SDH over WDM. such Networks that use data logs of different layers will become also referred to as multi-layer networks.

• – Routing über eine beliebige Anzahl von Network-Schichten;
• – Hardwarekonfigurationen in allen Schichten;
• – Topologie und Link-Konfigurationsentscheidungen in allen Schichten, und
• – Aufrechterhaltung von End-zu-Ende-Verbindungen.

An Integer Programming Model for Multi-Bearing Network Design, by S. Orlowski and R. Wessly, ZIB Report 04-49, December 2004, describes a linear inter-programming model for integrated cost optimization for multi-layer telecommunications networks that addresses the following issues:

• - Routing over any number of Net work-layers;
• - Hardware configurations in all layers;
• - topology and link configuration decisions in all layers, and
• - Maintaining end-to-end connections.

2 shows an example of a multi-layer network with MPLS / ATM over SDH over WDM. The MPLS (Multi-Protocol Label Switching) communication protocol is used to route IP data packets in connection-oriented networks using so-called Label-Switch-Paths LSP. ATM (Asynchronous Transfer Mode) uses virtual data paths VPs to provide the necessary Quality of Service in packet-oriented data networks. SDH (Synchronous Digital Hierarchy) uses standardized bandwidths, so-called Virtual Containers (VCs) for the transport of MPLS, ATM or other data traffic. WDM (Wavelength Division Multiplexing) combines many light paths of different wavelengths in a single optical fiber to increase data transmission capacity.

At different nodes of the network, different data streams are merged, i. H. multiplexed. Between two nodes where the traffic is multiplexed or demultiplexed, the aggregated data streams are routed together. A so-called grooming signal path corresponds to a signal path, where no signals are input between the access or the output or be removed. All signals are on the grooming signal path bundled together at the beginning multiplexed and you do not have access to these signals up to the end of the grooming path, where at the end the signals are demultiplexed become. Grooming refers to the network-wide dynamic or static configuration at multiplexer / demultiplexer level. The routes denotes the routing of physical and logical connections between a start and an end node of a connection.

The grooming and routing is conventionally done before the wave assignment, as in 3 shown. Grooming serves to establish a connection between two end nodes, minimizing the number of resources or components required, including the required fiber links, while maintaining the same end user data transmission rate.

conventional However, routing or grooming procedures often lead to or signal path configurations, which are followed by a wavelength assignment without wavelength conflict do not allow.

It is therefore the object of the present invention, a method and a system for routing connection requests between Nodes of an optical layer-based multilayer network to create a wavelength assignment to the optical Connections or links without wavelength conflict is possible.

These The object is achieved by a Method solved by the features specified in claim 1.

• – Ermitteln von möglichen Signalpfaden zwischen den Endknoten der aufzubauenden Verbindungen für die verschiedenen Schichten des Mehrschicht-Netzes, wobei die Signalpfade aus Links, welche jeweils zwei Knoten des Mehrschicht-Netzes verbinden, zusammengesetzt sind;
• – Berechnen eines Konfliktgraphens für die ermittelten Signalpfade der optischen Schicht;
• – Zuweisen eines möglichen Signalpfades einer höheren Schicht zu jeder Verbindungsanforderung der höheren Schicht;
• – Ermitteln einer Anzahl für jedes Link des zugewiesenen Signalpfades der höheren Schicht, die angibt, wie oft das jeweilige höhere Link in dem zugewiesenen Signalpfad der höheren Schicht enthalten ist;
• – Berechnen für jedes höhere Link einer Anzahl, die angibt, wie viele optische Links für das notwendige höhere Link jeweils bereitzustellen sind in Abhängigkeit von dem Verhältnis von Granularitäten der höheren Schicht und der optischen Schicht;
• – Zuweisen eines Signalpfades der optischen Schicht für jedes bereitzustellende optische Link;
• – Ermitteln eines Flussvariablen-Wertes für jeden Signalpfad der optischen Schicht, der angibt, wie oft der jeweilige Signalpfad zum Bereitstellen der optischen Links zugewiesen ist; und
• – Berechnen eines ersten Vergleichswertes für jeden Signalpfad der optischen Schicht, der von dem jeweils ermittelten Flussvariablen-Wert des Signalpfades und von einer Summe der Flussvariablen-Werte aller in dem Konfliktgraph zu dem Signalpfad benachbart liegenden Signalpfade abhängt, wobei, wenn ein aus den berechneten ersten Vergleichswerten ermittelter maximaler erster Vergleichswert kleiner oder gleich einem zweiten Vergleichswert ist, der von der Anzahl von gleichzeitig über ein optisches Link übertragbaren Lichtsignalwellen abhängt, eine anschließende Wellenlängenzuordnung zu den optischen Links sicher durchführbar ist.

The invention provides a method for routing connection requests between nodes of an optical layer-based multi-layer network, comprising the following steps:

• - determining possible signal paths between the end nodes of the connections to be set up for the different layers of the multi-layer network, the signal paths being composed of links each connecting two nodes of the multi-layer network;
• Calculating a conflict graph for the determined signal paths of the optical layer;
• Assigning a possible higher layer signal path to each higher layer connection request;
• - determining a number for each link of the higher layer signal path assigned, indicating how many times the respective higher link is contained in the higher layer signal path assigned;
• Calculating for each higher link of a number indicating how many optical links to provide for the necessary higher link, respectively, depending on the ratio of granularities of the higher layer and the optical layer;
• Assigning a signal path of the optical layer for each optical link to be provided;
• - determining a flow variable value for each signal path of the optical layer indicating how many times the respective signal path has been assigned to provide the optical links; and
• Calculating a first comparison value for each signal path of the optical layer, which depends on the respectively determined flow variable value of the signal path and on a sum of the flow variable values of all signal paths adjacent to the signal path in the conflict graph, wherein if one of the computed first Comparative values determined maximum first comparison value is less than or equal to a second comparison value, which depends on the number of simultaneously transmissible via an optical link light signal waves, a subsequent wavelength assignment to the optical links is safely feasible.

In a preferred embodiment of the According to the method of the invention, the second comparison value is equal to the number of light signal waves which can be transmitted simultaneously via an optical link.

at an alternative embodiment the method according to the invention the second comparison value is equal to the number of simultaneously over one optical link transferable Light signal waves minus one.

In a further embodiment of the method according to the invention, another possible signal path p is assigned to the optical links if the calculated first maximum comparison value V _{max is} greater than the second comparison value.

In a preferred embodiment of the method according to the invention, the number of optical links to be provided in each case is calculated as follows, depending on a granularity of the optical layer OS, a granularity of the higher layer HS and the number Z _HL of necessary higher links of the higher layer: Z OIL = ceil (Z HL /(G OS /G HS )) where ceil x is a round-up function that specifies for a fractional value x the lowest integer value that is greater than or equal to x.

In a preferred embodiment of the method according to the invention, the comparison value V _i for each signal path p _{i of} the optical layer OS is calculated as follows: V i = f (p i ) - 1 + Σ f (p j ) wherein the sum fp _{j represents} the sum of the flow variable values of all the signal paths adjacent to the signal path p _i in the conflict graph.

at a preferred embodiment the method according to the invention routes this connection requests adaptively.

at an alternative embodiment the method according to the invention the route is static.

at The multi-layer network is preferably a two-layer network.

at a preferred embodiment the method according to the invention becomes the higher one Layer through an MPLS layer educated.

at an alternative embodiment the method according to the invention becomes the higher layer formed by an SDH layer.

• – einer Einrichtung zum Ermitteln von möglichen aus Links zusammengesetzten Signalpfaden p, q zwischen den Endknoten der aufzubauenden Verbindungen für die verschiedenen Schichten des Mehrschicht-Netzes;
• – einer Einrichtung zum Berechnen eines Konfliktgraphens für die ermittelten Signalpfade p der optischen Schicht OS;
• – einer Einrichtung zum Zuweisen eines möglichen Signalpfades q einer höheren Schicht HS zu jeder Verbindungsanforderung der höheren Schicht HS;
• – einer Einrichtung zum Ermitteln einer Anzahl für jedes Link des zugewiesenen Signalpfades q der höheren Schicht HS, die angibt, wie oft das jeweilige höhere Link HL in dem zugewiesenen Signalpfad q der höheren Schicht HS enthalten ist;
• – einer Einrichtung zum Berechnen für jedes höhere Link HL einer Anzahl Z_OL, die angibt, wie viele optische Links OL für das notwendige höhere Link HL jeweils bereitzustellen sind in Abhängigkeit von dem Verhältnis von Granularitäten G_HS, G_OS der höheren Schicht HS und der optischen Schicht OS;
• – einer Einrichtung zum Zuweisen eines Signalpfades p der optischen Schicht OS für jedes bereitzustellende optische Link OL;
• – einer Einrichtung zum Ermitteln eines Flussvariablen-Wertes f(p) für jeden Signalpfad p der optischen Schicht OS, der angibt, wie oft der jeweilige Signalpfad p zum Bereitstellen der optischen Links OL zugewiesen ist; und mit
• – einer Einrichtung zum Berechnen eines ersten Vergleichswertes V_i für jeden Signalpfad p_i der optischen Schicht OS, der von dem jeweils ermittelten Flussvariablen-Wert f(p_i) des Signalpfades p_i und von einer Summe Σf(p_j) der Flussvariablen-Werte f(p_j) aller in dem Konfliktgraph zu dem Signalpfad p_i benachbart liegenden Signalpfade p_j abhängt, wobei, wenn ein aus den berechneten ersten Vergleichswerten V_i ermittelter maximaler erster Vergleichswert V_max kleiner oder gleich einem zweiten Vergleichswert ist, der von der Anzahl von gleichzeitig über ein optisches Link übertragbaren Lichtsig nalwellen λ abhängt, eine anschließende Wellenlängenzuordnung zu den optischen Links OL sicher durchführbar ist.

The invention also provides a system for routing connection requests between nodes of an optical layer OS-based multi-layer network

• - means for determining possible link signal paths p, q between the end nodes of the connections to be established for the different layers of the multi-layer network;
• A means for calculating a conflict graph for the detected signal paths p of the optical layer OS;
• - means for assigning a possible signal path q of a higher layer HS to each higher layer connection request HS;
• - means for determining a number for each link of the assigned signal path q of the higher layer HS indicating how many times the respective higher link HL is contained in the assigned signal path q of the higher layer HS;
• A means for calculating for each higher link HL a number Z _OL indicating how many optical links OL to provide for the necessary higher link HL, respectively, depending on the ratio of granularities G _HS , G _{OS of} the higher layer HS and optical layer OS;
• - means for assigning a signal path p of the optical layer OS for each optical link OL to be provided;
• - means for determining a flow variable value f (p) for each signal path p of the optical layer OS indicating how many times the respective signal path p has been assigned to provide the optical links OL; and with
• - A device for calculating a first comparison value V _i for each signal path p _{i of} the optical layer OS, of the respectively determined flow variable value f (p _i ) of the signal path p _i and of a sum Σf (p _j ) of the flow variable values f (p _j ) of all in the conflict graph to the signal path p _i adjacent signal paths p _j depends, wherein, if one of the calculated first comparison values V _i determined maximum first comparison value V _{max is} less than or equal to a second comparison value of the number from simultaneously transmissible via an optical link Lichtsig nalwellen λ, a subsequent wavelength assignment to the optical links OL is safely feasible.

in the Other preferred embodiments the process of the invention and of the system according to the invention with reference to the attached Figures for explanation essential to the invention Features described.

It demonstrate:

1 : an example of a WDM-based data network;

2 : an example of a multi-layer data network;

3 : a simple flow chart illustrating a wavelength assignment following a routing process;

4 a flow chart of a possible embodiment of the method according to the invention for routing connection requests;

5A . 5B an example for explaining the method step for calculating a conflict graph;

6A . 6B a first diagram for explaining the method according to the invention;

7A . 7B a further diagram for explaining the method according to the invention;

8th : one at the in 6 . 7 illustrated example conflict graph for explaining the method according to the invention;

9A . 9B a possible wavelength assignment for the routes calculated for the method according to the invention.

How to get out 4 can recognize, the inventive method is suitable for routing connection requests between nodes of an optical layer OS based multi-layer network.

After a starting step S ₀ , in a step S ₁ first possible signal paths p, q between the terminal nodes of the connections to be set up for the different layers of the multi-layer network are determined. In this case, the signal paths p, q are composed of links which each connect two nodes of the multi-layer network.

6A . 6B show an example of a multi-layer network consisting of two layers, namely a higher layer HS and a lower optical layer OS. The network layers each comprise four nodes A, B, C, D. Connection requirements exist between the nodes of the higher layer HS. For example, a first network operator wants to establish two data connections between node A and node D, and a second network operator also wants to establish a data connection between nodes A, D. How to get in 6A can recognize exist between the two nodes A, D accordingly three connection requests. The connection requests can be statically fixed in advance or they can change dynamically over time. In the 6A The higher layer HS shown is, for example, an SDH or an MPLS data protocol layer. This higher layer HS is based on a lower optical layer OS where nodes, as in FIG 6B represented, are interconnected via glass fibers. At the in 6B not all nodes are connected to each other via glass fibers, but via a ring structure.

For candidate signal paths Q of the higher layer HS are for all node pairs possible Signal paths q between the end nodes of the connections to be established calculated. Further, the candidate signal paths P for the under optical layer OS between all node pairs for the determination of potential Signal paths p determined.

An example can be found in the 7A . 7B , The signal paths q form the group q of possible signal paths.

In the 7B represented signal paths p form a group of possible signal paths P.

The group of possible signal paths Q consists in the in 7A Example shown from the signal paths q = {q1, q2, q3, q4, q5}

The group P of possible signal paths p for the low optical layer OS comprises in the in 7B illustrated example P = {p1, p2, p3, p4, p5, p6}.

For example the higher layer signal path q5 connects the end nodes D and C together.

In In the same way, for example, the signal path p6 connects the optical Layer OS nodes A, B with each other.

After determination of the possible signal paths p, q for the different layers OS, HS of the multi-layer network, the calculation of a conflict graph for the determined signal paths p of the optical layer OS takes place in step S2. The calculation of a conflict graph is based on the example in 5 explained.

At the in 5A . 5B As shown, a network comprises a plurality of nodes 0, 1, 2, 3, 4 which are interconnected via data links. The data connections are, for example, glass fibers. Consist between the nodes in the 5A represented signal paths connecting two end nodes of a connection. For example, there is a first signal path between the nodes 4, 1 and a second signal path between the nodes 4, 0 above the node 1. For each signal path, in the in 5B plotted a node, wherein two nodes of the conflict graph are interconnected when two signal paths in the data network via a common fiber or a common data connection run. Two adjacent nodes in the conflict graph must be assigned different wavelengths for data transmission in order to avoid a wavelength conflict. The wavelength assignment is made such that two interconnected nodes in the conflict graph do not have the same wavelength λ, and further, as few different wavelengths λ are used as possible. The minimum number of wavelengths λ used in a conflict graph is also called a chromatic number.

At the in 7B shown example of possible signal paths p is obtained after the calculation in step S2 to the in 8th illustrated conflict graph, in which the various signal paths p _{i form} the nodes.

In a further step S _{3 of} the method according to the invention, a possible signal path q of the set Q, a first signal path q of this set, which connects the end nodes of the connection request, is allocated for each connection request of the higher layer HS.

This leads to the in 7A Example shown for the following assignment:
A-B: q2
A-B: q2
A-B: q2
B-C: q3
C-D: q4
C-D: q5
D-A: q1
D-A: q1
D-A: q1

Between the nodes A, B of the higher layer exist in the illustrated example, as in 7A shown three connection requests, wherein the first possible signal path q2 of the set Q, which connects the nodes A, B, respectively, a connection request is assigned.

Between the node B, C is merely a connection request, wherein the signal path q3 this connection request is assigned.

Between the node C-D There are two connection requirements in the higher layer, wherein in the illustrated example, the first possible signal path q4 for the first Connection request and the other possible signal path q5 for the second Connection request is assigned.

Between the node D-A finally persist three connection requests, this being the first possible signal path q1 is assigned to the set Q.

In a further step S4 is then in the inventive method a number for determines each link of the assigned signal path q of the higher layer HS, which indicates how many times the respective higher link HL in the assigned Signal path q of the higher Layer is included.

For example, the link A-B in the assigned signal paths of the higher layer HS is contained four times in the illustrated example, namely three times in the signal path q2 and once in the signal path q5. In the same way, the link B-C of the higher layer HS is contained twice in the assigned signal paths q, namely once in the signal path q3 and in the signal path q5. The link C-D is contained only once in the assigned signal paths q of the higher layer HS, namely in the signal path q4. Furthermore, the link D-A is contained four times in the assigned signal paths q, namely in the three assigned signal paths q1 and in the assigned signal paths q5.
FROM 4
B-C: 2
C-D: 1
D-A: 4

After the number which indicates how many times the respective higher link HL is contained in the assigned higher-level signal paths is determined for each link of the assigned signal path 9 of the higher layer HS, a number Z _OL is then calculated in a step S5, which indicates how many optical links OL are to be respectively provided for the necessary higher link HL, this number Z _{OL being} calculated as a function of the respective ratio of the granularities G _HL , G _{OL of} the higher layer HS and the optical lower layer OS.

In one embodiment, the number Z _OL of each optical link to be provided is calculated as follows, depending on the granularity G _{OS of} the optical layer OS, the granularity G _{HS of} the higher layer HS, and the number of higher HL links required for the higher layer : Z OIL = ceil (Z HL /(G OS /G HS )), where Z _OL (x) is a rounding function that is used for the fractional value x indicates the lowest integer value that is greater than or equal to x.

For example, if the ratio of granularity to optical layer of the higher layer is two, the following values are obtained for the different links:
A-B: Z _OL = 2
B-C: Z _OL = 1
C-D: Z _OL = 1
D-A: Z _OL = 2

The Set L therefore consists of two links A-B, a link B-C, one Link C-D and two links D-A the optical layer OS or physical layer.

Subsequently, in a step S _{6 of} the method according to the invention, a signal path p of the optical layer OS is allocated for each optical link OL to be provided. In this case, the assignment can take place randomly from the set of possible signal paths p or, for example, the first signal path can be selected from the set P.

One possible assignment I in the example shown is:
A-B: p3
A-B: p3
B-C: p4
C-D: p5
D-A: p2
D-A: p2

For example, signal path p4 must be assigned for link B-C, since it represents the only signal path between the two nodes, as in FIG 7B shown.

In a further step S ₇ , the flow variable values f (p) for each signal path p of the optical layer OS are subsequently determined, the flow variable value indicating how often the respective signal path p is assigned for providing the optical link OL.

In the given example, the two signal paths p1, p2 are not assigned to the optical layer at all, so that the flow variable values for this result to zero: f (p1) = f (p6) = 0

The example also applies f (p4) = f (p5) = 1 and f (p5) = f (p3) = 2

The calculation of a first comparison value V ₁ for each signal path p _{i of} the optical layer OS is carried out from the determined flow variable values f (p) in a further calculation step S ₈ of the method according to the invention. This first comparison value V ₁ depends on the respectively determined flow variable value f (p _i ) of the signal path p _i and on a sum Σ f (p _j ) of the flow variable values f (p _j ) of all in the conflict graph relating to the signal path p _i adjacent signal paths p _j from.

Preferably, the first comparison value V ₁ for a signal path p _{i of} the optical layer OS results as follows: f i = f (p i ) - 1 + Σ f (p j )

From all calculated first comparison values V ₁ , a maximum comparison value V _{max is} determined and it is checked whether it is smaller than or equal to a second comparison value V ₂ , which depends on the number of light signal waves λ transmissible simultaneously via an optical link OL.

In the given example, the first comparison values V _{1 are given} as a function of the flow variable values as follows: p1: [0 - 1 + f (p3)] = 1 p2: [2 - 1 + f (p3) + f (p4) + f (p5) + f (p6)] = 5 p3: [2 - 1 + f (p1) + f (p2) + f (p4) + f (p5)] = 5 p4: [1 - 1 + f (p2) + f (p3)] = 4 p5: [1 - 1 + f (p2) + f (p3)] = 4 p6: [0 - 1 + f (p2)] = 1

The maximum first comparison value V _max is thus 5.

The second comparison value V ₂ depends on the number W _max of light signal waves which can be transmitted simultaneously via an optical link. In a first embodiment, the second comparison value V _{2 is} equal to the number W _max of light signal wavelengths λ that can be transmitted simultaneously via an optical link OL.

In a second embodiment, the second comparison value V _{2 is} equal to the number W _max of simultaneously translatable via a optical link OL light signal wavelengths λ minus one.

If, for example, a transmission of four lightwave signals can occur simultaneously via a glass fiber of the optical layer, W _{max is} equal to four.

In the example shown is thus the first comparison value V _1max = five greater than the second comparison value W _max = four.

Thus, in this example, the condition that the maximum first comparison value V _{max is} less than or equal to a second comparison value is not satisfied. Therefore, in the example given, a new signal path assignment must take place until this condition is met.

For this will be first checked, if all possibilities an assignment of signal paths to the links are exhausted or not. If a different assignment is possible, this is done.

In the example shown, the following assignment takes place (assignment II):
A-B: p3
A-B: p6
B-C: p4
C-D: p5
D-A: p2
D-A: p1,
where the flow variable values are each one: f (p1) = f (p2) = f (p3) = f (p4) = f (p5) = f (p6) = 1

This is followed by the calculation of the first comparison value V ₁ .

In the given example: p1: [1 - 1 + f (p3)] = 1 p2: [1 - 1 + f (p3) + f (p4) + f (p5) + f (p6)] = 4 p3: [1 - 1 + f (p1) + f (p2) + f (p4) + f (p5)] = 4 p4: [1 - 1 + f (p2) + f (p3)] = 2 p5: [1 - 1 + f (p2) + f (p3)] = 2 p6: [1 - 1 + f (p2)] = 1

The maximum of the first comparison values V _max is therefore equal to W _max equal to four and thus fulfills the condition that V _{max is} less than or equal to the number of light signal waves W _{max that} can be transmitted simultaneously via an optical link.

By the fulfillment the condition is ensured that the assigned signal paths p a subsequent Wavelength allocation allow, without causing a wavelength conflict.

With signal path assignment II, a wave assignment is possible, such as this by the Groom or routing method is guaranteed.

For example, one possible wavelength assignment is as follows:
A-B: p3 → wavelength number 2
A-B: p6 → wavelength number 2
B-C: p4 → wavelength number 3
C-D: p5 → wavelength number 3
D-A: p2 → wavelength number 1
D-A: p1 → wavelength number 1

This will be graphically in 9 shown. For example, the signal path p3 receives the wavelength λ2 and connects the nodes A, B with each other.

As can be seen from the corresponding conflict graph, have adjacent Node or signal paths p always different wavelengths λ.

• 1. Compute candidate paths Q for higher layer HS between all nodepairs, e. g., by complete enumeration;
• 2. Compute candidate paths P for lower layer (optical layer) OS; between all nodepairs, e. g., by complete enumeration
• 3. Compute conflict graph CG from P;
• 4. For each higher-layer demand assign the first path 9 in the Q list connecting the demand's end nodes. The used paths are Q';
• 5. The set of all links in Q' is L. For each end node pair np a. n is the number of links in L that each connect np b. reduce the number of links in L (that each connect np) to ceil (n/G_OS/G_HS), where ceil (x) denotes the lowest integer value that is greater than or equal to x;
• 6. For each L assign the first path p in the P list connecting the link's end nodes. The used paths are in set P' and the number of the individual paths used for the demand counted by f(p_i).
• 7. Check if max_{ni in G} [f(pi) – 1 + sum_{nodes nj which are adjacent to ni in G} f(pi)] <= Wmax a. If yes, stop and go to Wavelength Assignment) with the found P'. b. If no, are selections P' from P exhausted? i. If yes, if selections Q' from Q exhausted goto 8 otherwise select new set Q' from Q and goto 5. ii. If no, select new set P' from P and goto 7.
• 8. Return no solution and stop fully. The step „select new set Q' from Q'' (also for P) can be done, e. g., by going through all possible combinations of a set Q' from a set Q.

The method according to the invention can be described algorithmically with the following pseudocode:

• 1. Compute candidate paths Q for higher layer HS between all nodepairs, eg, by complete enumeration;
• 2. Compute candidate paths P for lower layer (optical layer) OS; between all nodepairs, eg, by complete enumeration
• 3. Compute conflict graph CG from P;
• 4. For each higher-layer demand assign the first path 9 in the Q list connecting the demand's end nodes. The used paths are Q ';
• 5. The set of all links in Q 'is L. For each end node pair np a. n is the number of links in L that each connect np b. reduce the number of links in L (that is, connect each other) to ceil (n / G _OS / G _HS ), where ceil (x) denotes the lowest integer value that is greater than or equal to x;
• 6. For each L assign the first path in the P list connecting the link's end nodes. The used paths are in set P 'and the number of the individual paths used for the demand counted by f (p _i ).
• 7. Check if max_ {n i in G} [f (p i ) - 1 + sum_ {nodes n j which are adjacent to n i in G} f (p i )] <= W Max a. If yes, stop and go to Wavelength Assignment) with the found P '. b. If no, are selections P 'from P exhausted? i. If yes, if selections Q 'from Q exhausted goto 8 otherwise select new set Q' from Q and goto 5. ii. If no, select new set P 'from P and goto 7.
• 8. Return no solution and stop fully. The step "select new set Q 'from Q''(ie for P) can be done, eg, by going through all possible combinations of a set Q' from a set Q.

Claims (20)

A method for routing connection requests between nodes of an optical layer (OS) based multi-layer network comprising the steps of: (a) determining possible signal paths (p, q) between the end nodes of the connections to be established for the different layers of the multi-layer network wherein the signal paths (p, q) are composed of links each connecting two nodes of the multi-layer network; (b) calculating a conflict graph for the detected signal paths (p) of the optical layer (OS); (c) assigning a possible signal path (q) of a higher layer (HS) to each higher layer connection request (HS); (d) determining a number for each link of the higher layer (HS) assigned signal path (Q) indicating how many times the respective higher link (HL) is contained in the higher layer (HS) assigned signal paths (Q); (e) calculating for each higher link (HL) of a number (Z _OL ) indicating how many optical links (OL) are to be provided for the necessary higher link (HL), depending on the ratio of granularities (G _HS , G _OS ) of the higher layer (HS) and the optical layer (OS); (f) assigning a signal path (p) of the optical layer (OS) for each optical link (OL) to be provided; (g) determining a flow variable value f (p) for each signal path (p) of the optical layer (OS) indicating how many times the respective signal path (p) is assigned to provide the optical links (OL); and (h) calculating a first comparison value (V _i ) for each signal path (p _i ) of the optical layer (OS) from the respective determined flow variable value f (p _i ) of the signal path (p _i ) and from a sum Σf (p _j ) of the flow variable values f (p _j ) of all in the conflict graph to the signal path (p _i ) adjacent signal paths (p _j ) depends, in which method, if one of the calculated first comparison values (V _i ) determined maximum first comparison value (V _max ) is less than or equal to a second comparison value, which depends on the number of light signal waves (λ) which can be transmitted simultaneously via an optical link, a subsequent wavelength assignment to the optical links (OL) can be carried out safely. Method according to Claim 1, in which the second comparison value is equal to the number (W _max ) of light signal waves (λ) which can be transmitted simultaneously via an optical link. The method of claim 1, wherein the second comparison value is equal to the number (W _max ) of light signal waves (λ) simultaneously transmissible over an optical link minus one. Method according to Claim 1, in which, if the calculated first maximum comparison value (V _max ) is greater than the second comparison value, another possible signal path (p) is assigned to the optical links. Method according to Claim 1, in which the number (Z _OL ) of the optical links to be respectively provided depends on a granularity (G _OS ) of the optical layer (OS), a granularity (G) of the higher layer (HS), and the number (Z _OL ). Z _HL ) of higher level HL (HL) necessary links of the higher layer (HL) is calculated as follows: Z OIL = ceil (Z HL /(G OS /G HS )), which ceil (x) is a round-up function that specifies, for a fractional value x, the lowest integer value that is greater than or equal to x. Method according to Claim 1, in which the first comparison value (V _i ) for each signal path (p _i ) of the optical layer (OS) is calculated as follows: V i = f (p i ) - 1 + Σ f (p j ) which sum f (p _j ) represents the sum of the flow variable values of all the signal paths (p _j ) adjacent to the signal path (p _i ) in the conflict graph. The method of claim 1, which determines the connection requirements adaptively routes. The method of claim 1, which determines the connection requirements static routes. The method of claim 1, wherein the multi-layer network as higher Layer an MPLS layer having. The method of claim 1, wherein the multi-layer network as higher Layer an SDH layer having. A system for routing connection requests between nodes of an optical layer (OS) based multi-layer network comprising (a) means for determining possible link signal paths (p, q) between the end nodes of the connections to be established for the different layers of the multi-layer -Netzes; (b) means for calculating a conflict graph for the detected signal paths (p) of the optical layer (OS); (c) means for assigning a possible signal path (q) of a higher layer (HS) to each Higher layer connection requirement (HS); (d) means for determining a number for each higher-level (HS) signal path link (q) which indicates how many times the respective higher link (HL) in the higher-level (HS) assigned signal paths (q) is included; (e) means for calculating for each higher link (HL) a number (Z _OL ) indicating how many optical links (OL) for the necessary higher link (HL) are to be provided, depending on the ratio of granularities ( G _HS , G _OS ) of the higher layer (HS) and the optical layer (OS); (f) means for assigning a signal path (p) of the optical layer (OS) for each optical link (OL) to be provided; (g) means for determining a flow variable value f (p) for each signal path (p) of the optical layer (OS) indicating how many times the respective signal path (p) is assigned to provide the optical links (OL); and (h) means for calculating a first comparison value (V _i ) for each signal path (p _i ) of the optical layer (OS) determined by the respectively determined flow variable value f (p _i ) of the signal path (p _i ) and from a sum Σf (p _j) of the flow variable values f (p _j) depend all signal paths adjacent in the conflict graph to the signal path (p _i) lying (p _j), in which system when a (from the calculated first comparison values V _i ) determined maximum first comparison value (V _max ) is less than or equal to a second comparison value, which depends on the number of simultaneously transmissible via an optical link light signal waves (λ), a subsequent wavelength assignment to the optical links (OL) is safely feasible. A system according to claim 11, wherein the second comparison value is equal to the number (W _max ) of light signal waves (λ) simultaneously transmissible via an optical link. The system of claim 11, wherein the second comparison value is equal to the number (W _max ) of optical signal waves (λ) simultaneously transmissible via an optical link minus one. The system of claim 11, wherein when the calculated first maximum comparison value (V _max ) is greater than the second comparison value, the optical links are assigned another possible signal path (p). The system according to claim 11, _wherein the number (Z _OL ) of the respective optical links to be provided depends on a granularity (G _OS ) of the optical layer (OS), a granularity (G) of the higher layer (HS) and the number (Z). Z _HL ) of higher level HL (HL) necessary links of the higher layer (HL) is calculated as follows: Z OIL = ceil (Z HL /(G OS /G HS )), which ceil (x) is a round-up function that specifies, for a fractional value x, the lowest integer value that is greater than or equal to x. A system according to claim 11, wherein the first comparison value (V _i ) for each signal path (p _i ) of the optical layer (OS) is calculated as follows: V i = f (p i ) - 1 + Σ f (p j ) which sum f (p _j ) represents the sum of the flow variable values of all the signal paths (p _j ) adjacent to the signal path (p _i ) in the conflict graph. The system of claim 11, which determines the connection requirements adaptively routes. The system of claim 11, which determines the connection requirements static routes. The system of claim 11, wherein the multi-layer network as higher Layer an MPLS layer having. The system of claim 11, wherein the multi-layer network as higher Layer an SDH layer having.