ROUTING METHOD FOR DYNAMIC WDM OPTICAL NETWORKS WITH WAVELENGTH CONTINUITY RESTRICTIONS

Abstract

The invention relates to a novel method for determining the set of routes that allow each network user to transmit. The method is more efficient than the existing methods, in terms of number of wavelengths, and due to the fixed routing strategy used, its implementation is simple, and its online operation is very fast.

Claims

1. A routing method for a dynamic wavelength division multiplexing (WDM) optical network having wavelength continuity constraints, CHARACTERIZED in that the method comprises: obtaining, by means of a processor, the topology of said dynamic WDM optical network having wavelength continuity constraints, stored in a topology database, said dynamic WDM optical network being represented by N network nodes and L links connecting said N nodes; obtaining, by means of said processor, a plurality of users of said network, wherein a user of said plurality is defined as a source node, a destination node, and a traffic load associated with said user; obtaining, by means of said processor, a plurality of non-operational routes, said plurality of non-operational routes corresponding to said plurality of users; and storing said plurality of non-operational routes in a non-operational routes database, wherein said non-operational routes are stored in said non-operational routes database sorted from shorter to longer length and, for those of equal length, from lowest to highest traffic load; storing, in an operational routes database, the routes having length equal to 1 and removing said route from said non-operational routes database; calculating, by means of said processor, the cost of each link of said network using the information from said operational routes database; calculating, by means of said processor, a cheapest route corresponding to the user of the first non-operational route of said non-operational routes database, using the information corresponding to the cost of each link; storing said cheapest route in said operational routes database and removing said non-operational route corresponding to said user of said non-operational routes database; repeating the above two steps until there are no non-operational routes in said non-operational routes database; and transmitting information through said network using said routes stored in said operational routes database. wherein said processor calculates the cost of each link by the formula:
= wherein is the traffic load of the link and ρ is the average traffic load of said Network.

2. The method of claim 1, CHARACTERIZED in that said non-operational routes are obtained by means of the Dijkstra algorithm.

3. The method of claim 1, CHARACTERIZED in that said cheapest paths are obtained by means of the Dijkstra algorithm weighted by the cost of each link.

4. The method of claim1, CHARACTERIZED in that the traffic load of each link , , is obtained by the formula: ${\rho }_{\ell }=\underset{u_{\ell }}{.Math.}{\rho }_u$ wherein is the set of users whose operational routes use the link and ρ.sub.u is the traffic load of a user u.

5. The method of claim1, CHARACTERIZED in that said average traffic load, ρ, is obtained by the formula $\overline{\rho }=\frac{{.Math.}_{\ell }{\rho }_{\ell }}{L}.$

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0021] FIG. 1 is a diagram depicting, in a general manner, the type of environment in which the invention is implemented, identifying the main subsystems involved in its operation.

[0022] FIG. 2 is a diagram depicting the topology of the provider network of FIG. 1.

[0023] FIG. 3A is a diagram depicting the structure of the network topology information system of FIG. 1.

[0024] FIG. 3B is a diagram depicting a table for storing the nodes information of FIG. 2.

[0025] FIG. 3C is a diagram depicting a table for storing the links information of FIG. 2.

[0026] FIG. 4A is a diagram depicting the structure of the users information system of FIG. 1.

[0027] FIG. 4B is a diagram depicting a table for storing network users information pertaining to the users database of FIG. 4A.

[0028] FIG. 5A is a diagram depicting the structure and functional components of the cheapest path by layers calculator system of FIG. 1.

[0029] FIG. 5B is a diagram depicting the table of non-operational routes calculated and stored in the non-operational routes database of FIG. 5A.

[0030] FIG. 5C is a diagram depicting the table of operational routes calculated and stored in the operational routes database of FIG. 5A.

[0031] FIG. 5D is a diagram depicting the table of routes calculated and stored in the routes database of FIG. 5A.

DETAILED DESCRIPTION OF THE INVENTION

[0032] The diagrams presented in the attached figures describe the environment of the invention.

[0033] The method that is object of the present invention implements a cheapest path by layers algorithm (hereinafter referred to in the text as CPL), which is based on the cheapest path connecting a source node 210 to a destination node 210 in the provider network 110, while, simultaneously, the traffic load on the links in the network is as balanced as possible. Each pair of nodes 210 represents a user u, which communicates via a route r.sub.u. It is assumed that the cost C.sub.r.sub.u of the route r.sub.u is equal to the cost of the user u, and is given by the sum of the cost of each link, , assigned to each link belonging to the user's route. Specifically, is calculated by the equation (1) and C.sub.r.sub.u is calculated by the equation (2).

=  (1)

C.sub.r.sub.u=  (2)

[0034] In equation (1), is the traffic load of the link 220, which is equal to the sum of the traffic load ρ.sub.u provided by each user u, belonging to the set of users , using the link in their route, as described in equation (3):

=ρ.sub.u   (3)

[0035] It should be noted that the traffic load of each user is stored in the users database 430 of the users information system 130.

[0036] On the other hand, referring again to equation (1), ρ is the average of the traffic load of all links 220 of the provider network 110, as presented in equation (4), wherein is the set of the links 220 in the provider network 110, and L the number of links in .

[00003]$\begin{array}{cc}\overline{\rho }=\frac{{.Math.}_{\ell \in ℒ}{\rho }_{\ell }}{L}& \left(4\right)\end{array}$

[0037] The operation of the CPL method can be performed in the environment 100 as shown in FIG. 1. The configuration may be comprised of a provider network 110 and a network topology information system 120, which contains the structure of the network topology of the provider 110. It may also contain a users information system 130, which contains the set of users (pair of source and destination nodes) using the provider network 110 and the traffic load of each user. In addition, the environment 100 has a cheapest path by layers calculator system 150, responsible for calculating the cheapest route for each user, which is connected to the network topology information system 120 and the users information system 130 through the communication system 140.

[0038] The provider network 110 is an optical network, which can be modeled as a graph =(,), composed of a set of nodes interconnected by a set of optical fiber links 220. A network node 210 may be any type of optical network (that is, an optical cross-connect—OXC) without wavelength conversion capabilities.

[0039] The network topology information system 120 may be a server or network device within or outside the provider network 110. The network topology information system 120 is stored in a topology database 330 and may be comprised of an input interface 310 that receives a request or data from the communication system 140 that are processed by a processor 320. Topology database 330 includes the node information 210 and the link information 220 in the provider network 110, using a nodes table 350 to store the nodes 210 and another links table 360 to store the links 220, as described in FIGS. 3B and 3C, respectively. To communicate with other systems or devices, the network topology information system 120 may send messages using the output interface 340.

[0040] The users information system 130 may be a server or network device outside the provider network 110 and may be comprised of an input interface 410 that receives information requests from the communication system 140. This information is processed by the processor 420 and may be stored in the users database 430. The users database 430 contains all users data (pairs of nodes) in the provider network 110, and the traffic load associated with each of them, as presented in the users table 450 shown in FIG. 4B. To interact with other systems and devices, the users information system 130 may send messages using the output interface 440.

[0041] The cheapest path by layers calculator system 150 may be a server or a computer device capable of communicating with other devices, for example, a desktop computer or laptop computer, outside the provider network 110. The cheapest path by layers calculator system may be composed of an input interface 510, which accepts requests or information from the communication system 140. During execution of the CPL algorithm, the cheapest path by layers calculator system 150 may request data regarding the network topology and users to the network topology information system 120 and users information system 130, respectively. Said information is stored in the device's own databases, either in the topology database 520 with topology information, or in the users database 530 with the users data. The link cost calculator 540 and the route calculator 550 use the information stored in the non-operational routes database 560 and the operational routes database 570 to calculate the costs of each link and each route, respectively. The operational routes database 570 contains all those users and their routes, having their definitive routes calculated during execution of the CPL algorithm. On the other hand, the non-operational routes database 560 contains the other users, that is, those who do not possess a definitive route defined during execution of the CPL algorithm. The link cost calculator 540 uses the topology database 520 information, the users database 530, and the operational routes database to calculate the cost associated with each link 220. At the same time, the routes calculator 550 is in charge of calculating the route for each user. For delivery, the results of the CPL algorithm execution may be stored in the routes database 580, or sent to another system or device using the output interface 590, as a routs table 630, as shown in FIG. 5D.

[0042] The structure of the non-operational routes table 610, the operational routes table 620, and the routes table 630 are shown in FIGS. 5B, 5C and 5D, respectively.

[0043] The communication system 140 may be any network system that allows to connect two or more devices, such as the cellular network, the public land mobile network (PLMN), a second generation (2G) network, a third generation (3G) network, a fourth generation (4G), a long-term evolution (LTE) network, a fifth generation (5G), a code division multiple access (CDMA) network, a global system for mobile communications (GSM) network, a general packet radio service (GPRS), a local area network (LAN), a wide area network (WAN), a metropolitan area network (MAN), an ad hoc network, an Intranet, the Internet, a fiber optic based network, a satellite network, television network, or a mixture of one or more of these systems.

[0044] The CPL method is executed in the cheapest path by layers calculator system 150 and its operation is described below: [0045] 1. The cheapest path by layers calculator system 150 requests the network topology information from the network topology information system 120 and stores it in its own topology database 520. [0046] 2. The cheapest path by layers calculator system 150 requests the users information and their traffic loads from the users information system 130, storing them in the non-operational routes database 560. [0047] 3. The link cost calculator 540 defines all link costs equal to 1.

[0048] 14. The route calculator 550 calculates the initial set of routes (for each user of the network), using any cheapest route algorithm (for example, Dijkstra), based on the network topology and in the cost of the links previously stored in step 3. [0049] 5. The route calculator 550 stores the initial set of the users route in the non-operational routes database 560. [0050] 6. The routes calculator 550 classifies the routes of the non-operational routes database 560 according to their length (that is, the number of links comprising the route), from shortest to longest. The routes with the same length are ordered by their traffic load (from lowest to highest). In the case of tie, the order is arbitrarily chosen. [0051] 7. The routes calculator 550 moves all users with a route length equal to 1, from the non-operational routes database 560 to the operational routes database 570. [0052] 8. The link cost calculator 540 calculates the cost in each link, using the cost algorithm (CA) (described below), considering only the routes of all users stored in the operational routes database 570. [0053] 9. The routes calculator 550 calculates the cheapest path using Dijkstra, considering the cost of the link evaluated in step 8. [0054] 10. The routes calculator 550 moves the user (only one) associated with the selected route in step 9 from the non-operational routes database 560 to the operational routes database 570. [0055] 11. Steps 9, 10 and 11 are repeated until there is no user stored in the non-operational routes database 560. [0056] 12. Finally, when all users are transferred to the operational routes database 570, this database is sent to the routes database 580.

[0057] A network manager may use this routing table (called R) to transfer it and copy it in a centralized or distributed manner to the nodes 210 of the provider network 110.

CA: Cost Algorithm:

[0058] The link cost calculator 530 performs the following operations for each link stored in topology database 520:

[0059] The traffic load from the link is calculated using equation (3) (The set considered in this step is composed of all users stored in the operational routes database 570).

[0060] A cost is set to using equation (1).

[0061] The link cost calculator 530 calculates the average traffic load of the links by equation (4).

[0062] The cheapest routing method can be used in two different ways: [0063] a) It can be used to generate a route per user, valid for all wavelengths of the network. [0064] b) Alternatively, it can be used to generate a route per user, for each different wavelength (or a set of consecutive wavelengths). In this case, the traffic load offered by each user at each wavelength can be evaluated using the method published in “Blocking Evaluation and Wavelength Dimensioning of Dynamic WDM Networks without Wavelength Conversion” by Jara et.al. in Journal of Optical Communications and Networking, vol. 9, no. 8, pp. 625-634, 2017, or by any other method available in the literature.