Modelling of a WDM Network Using Graph Theory and Dijkstra Algorithm for Traffic Redirection ()
1. Introduction
The rapid evolution of telecommunications networks is mainly driven by two main factors: technological advances in telecommunications systems, and the increase in Internet traffic due to the emergence of new real-time Internet applications such as video-conferencing, IP telephony, e-commerce, HD TV broadcasting, interactive games, IoT, etc… All this has contributed to the need to increase the bandwidth capacity of transport networks. As a result, operators have adopted a large-scale deployment of a high-speed transmission system: WDM (Wavelength Division Multiplexing). The major advantage of this transport network is that it exploits a fiber optic infrastructure and can reach speeds of up to 1.6 Tbps. It’s this revolutionary difference in transmission capacity that has prompted some operators to gradually migrate (given the enormous cost of all-optical equipment) from previous transport networks such as SDH to DWDM, in order to accommodate the rising broadband demand with the available resources [1].
The bandwidth demands are not necessarily allocated correctly, due to the lack of inherent flexibility in large-scale, manually-provisioned optical networks. This problem can be solved by using a control plane that performs call and connection control functions in real time. One of the most promising solutions is based on the concept of automatic switched optical network (ASON), i.e. an “intelligent” optical network that can automatically manage the signaling and routing through the network. The purpose of the automatically switched optical network control plane is firstly to facilitate fast and efficient configuration of connections in a transport layer network to support permanent switched and flexible connections; and secondly to perform a restoration function.
The automatic optical switched network is both a framework and a technological capability. As a framework, it describes a control and management architecture for an optical transport network. As a technology, it refers to the routing and signaling protocols applied to an optical network that enables dynamic path configuration [2].
In view of the ever-increasing number of problems to be addressed, mathematical objects offering a high level of abstraction (such as graphs or automata) have become indispensable. Graph theory enables us to simplify a given problem and better study the relationships between some of its elements. A graph is defined by a set of elements called nodes, the node being an abstraction of an object (e.g., city, person or machine), and a set of links between these nodes. These links, called arcs or edges, are also abstract (e.g., railway connections, romantic encounters, networks). Graphs are formal mathematical objects for which numerous properties have been characterized. As well as being much more than a mathematical object, a graph is a catalyst for ideas, boiling down to basic concepts. This rise in abstraction makes intuitions easy to come by, leading to extremely efficient algorithms for solving problems involving a large number of nodes [3].
The development of ICT in Cameroon was based on the development of the national broadband Network where the optical transport component was a key point with the installation of a total of about 12,000 km of fiber all around the country with a SDH and WDM networks with a set of Huawei OADM (OSM series). For the various services on the WDM network to be efficient and with a lack of Automatic Switched Optical Network (ASON) license, an efficient redirection solution should be found to reduce the downtime and improve the network availability and for that a solution using Dijkstra Algorithm was proposed and developed.
The aim of our study is to provide an automatic network traffic management technology similar to ASON which can help to improve the maintenance efficiency and network availability. For this reason, we have opted for the use of graph theory to overcome this problem. It is in this context that the following question arises: How can we model the local network operator’s WDM network using graph theory with a traffic redirection algorithm? In the same vein relating to the improvement of the maintenance of optical networks, Eric Deussom et al. have proposed the usage of machine learning for alarm classification and correlation to improve the network maintenance of optical network [4] and 4G mobile network [5], fraud detections [6] [7] and so on. Eric Deussom has also proposed the development of a tool for the dimensioning of the capacity of a submarine optical network [8].
This paper is intended as a response to the problem presented above. In particular, we shall be using the WDM backbone network of a local network operator in Cameroon and then present the automatic switching technology in optical networks, the tools offered by graph theory, and finally traffic management algorithms, focusing on the routing and redirection algorithm Djikstra. This paper summarizes the work that has been carried out and is structured around three main sections. In section 1, we present the scope of study, the problem, the objectives to be attained and the expected results; in the second, we present the literature review on the graph theory, WDM and ASON while in the third section, the methodology used to solve the problem will be presented. This will be followed by the main results obtained and comments in section four and this paper ends with a general conclusion.
1.1. Scope of the Study
Optical transport networks are made up of nodes interconnected by optical fibers. The nodes provide multiplexing/demultiplexing, transmission, reception and cross-connect functions for traffic flows. Optical fibers are used to transport traffic between interconnection nodes in the form of an optical signal. SDH networks send a single optical channel, carrying the STM-N frame, on each fiber. This sometimes means having to multiply the number of fibers between two nodes to obtain the capacity needed to transport new requests. Technological advances have led to the emergence of wavelength-division multiplexing (WDM), which enables multiple channels to be combined on the same optical signal, with each channel using a different wavelength. The bandwidth available in a fiber can then be considerably extended: each wavelength enables a throughput of several gigabits, and dozens of wavelengths can be used. This development means that a much wider bandwidth can be exploited in optical fiber with WDM than that used by a single optical transmitter in SDH.
1.2. Problem
Cameroon’s optical transport network (backbone) can be seen as a set of resources put together to transport a range of high bandwidth demanded services. To meet the needs of its customers, the local network operator routes most of its traffic via optical fiber (with SDH and DWDM implemented). It is therefore necessary to ensure continuity of traffic even in the event of a network incident. However, the backbone network as it is currently deployed, without the ASON technology, requires the intervention of an agent in the NMS (Network Management System) office, in order to redirect traffic. This procedure, which requires human intervention, is very tedious and sometimes takes a very long time to restore traffic flow. Hence the need for an automatic network management solution which can act as a technology similar to ASON. The local operator’s current problem faced with the full deployment of ASON is mainly financial due to the fact that ASON is a licensed service that requires hardware and software upgrades, not to mention the purchase of new cards and licenses for every optical Add Drop Multiplexer (OADM). We have therefore opted to use graph theory in this work to overcome this problem by modeling the optical network of the local operator by a graph, modeling the algorithm for identification of a redirection path and developing a software tool which can identify and output a redirection path when a fiber is cut between one or more OADM.
From the problem explained above, an essential question arises, which is: How can we model the local operator’s WDM backbone network, and define a traffic redirection algorithm using graph theory?
1.3. Objectives
Here, the objectives to be attained by this work are presented:
1.4. Expected Results
The results expected at the end of this study are as follows:
Network modeled in the form of graphs (nodes + links).
Carry out communication routing.
Simulate an incident.
Visualize traffic redirection.
Propose the solution obtained after the implementation of the solution as a software tool.
2. State of the Art
This section presents the state of the problem posed in the previous chapter. It will present in detail the tools offered by graph theory in order to model THE LOCAL OPERATOR’s WDM network by a graph and to define traffic routing algorithms: the case of traffic redirection.
This work is not the first to focus on the WDM network, ASON technology and graph theory. Indeed, several other people from different backgrounds have already tackled these topics, each tackling a specific aspect or part of the problem.
2.1. Graph Theory
A grip on the notions about graph theory were gotten by reading the following works:
Soichiro Araki and Itaru Nishioka from NEC Corporation Limited in Japan: For ASON/GMPLS multi-domain networks, three routing models, such as per-domain routing, ASON hierarchical routing, and PCE-based routing, have been standardized. We compare these three routing models in terms of path-computation capabilities, online path-planning capabilities and inter-domain confidentiality [9].
Docteur Didier Müller: Introduction to graph theory, published in 2011, is a book designed to introduce high school students to graph theory. Its ambition is not to master the complete theory, but to show how graphs can be an interesting method of solving interesting problems. It is divided into two main parts: undirected graphs and directed graphs. The exercises are essentially of two types: Theoretical exercises on graphs, which are often fairly simple demonstrations, generally by induction or by the absurd; there are also reflective exercises to see whether you’ve understood a concept correctly or not; Practical exercises using Grin 4.0 software, where it can be advantageous to use graphs to model and solve a problem [10].
2.2. Wavelength Division Multiplex (WDM) Related Topics
Holger Höller, Stefan Voß: A heuristic approach for combined equipment-planning and routing in multi-layer SDH/WDM networks, a paper dealing with a multi-layer network design problem for a high-speed telecommunications network based on synchronous digital hierarchy (SDH) and wavelength division multiplexing (WDM) technology. The network must meet a number of requirements, the aim being to minimize investment in equipment. The different layers are the fiber layer, 2.5 Gbps-, 10 Gbps- and WDM systems layers. Several variations of the problem, including path-protected requests and specific types of cross-connect equipment, are considered. The problem is described as a mixed integer linear programming model and some results for small networks are presented. Two greedy heuristics, one start-up heuristic. Two greedy heuristics, a random-start heuristic and a GRASP-type approach are implemented to solve large real problems [11].
Dr Sami BARAKETI: SDH and WDM Optical Network Engineering and IP/MPLS Multilayer Study on OTN over DWDM PhD theses defended in 2015 having as objective firstly, studied the problem of circuit routing in SDH networks with the main objective of minimizing bandwidth fragmentation. Secondly, studied two planning problems for WDM network optimization. The first problem is that of logical topology design, i.e. the definition of optical circuits (paths) enabling a set of traffic requests to be routed with minimum transponder cost. The second is routing and wavelength assignment [1].
2.3. ASON Technology Topics
SYLWESTER KACZMAREK and MAGDALENA MŁYNARCZUK: Simulator for Performance Evaluation of ASON/GMPLS Network. The authors gave an overview of the Automatically Switched Optical Network, focusing on its control plane. They describe the ASON architecture based on control and management transport planes the types of connections supported by ASON, including permanent switched and permanent flexible connections, as well as the drivers of auto-switched optical networks. The authors propose a simulator for the hierarchical control plane networks in an open source OMNeT++ environment, in order to evaluate network architecture performance for different network structures and traffic parameters [12].
Ram Krishna and Avadhesh: Automatically Switched Optical Network (ASON) [13]. The authors gave an overview of the Automatically Switched Optical Network, focusing on its control plane. They describe the ASON architecture based on control and management transport planes the types of connections supported by ASON, including permanent switched and permanent flexible connections, as well as the drivers of auto-switched optical networks. Different types of internal and external interfaces and various ASON control plane issues, such as control plane requirements, modeling and functions, were also presented and discussed. These functions include: discovery, routing, signaling, call and connection control.
2.4. The Dijkstra’s Algorithm
In graph theory, Dijkstra’s algorithm is used to solve the shortest path problem. It calculates the shortest paths from a source to all other vertices in a directed or undirected graph weighted by positive reals. It can also be used to calculate the shortest path between a starting vertex and an ending vertex. The algorithm is named after its inventor, Dutch computer scientist Edsger Dijkstra, and was published in 1959 [14] [15].
The algorithm takes as input a directed or unweighted graph weighted by positive reals and a source vertex. It progressively builds a sub-graph in which the various vertices are ranked in ascending order of their minimum distance from the starting vertex. The distance corresponds to the sum of the weights of the arcs used.
Initially, the distances from each vertex to the starting vertex are assumed to be infinite, except for the starting vertex, for which the distance is zero. The starting subgraph is the empty set. During each iteration, a vertex of minimum distance is chosen outside the subgraph and added to the subgraph. We then update the distances of the vertices adjacent to the added vertex. The update is performed as follows: the new distance of the neighboring vertex is the minimum between the existing distance and the distance obtained by adding the weight of the arc between neighboring vertex and added vertex to the distance of the added vertex. This process continues until all the vertices have been added (or until the destination vertex has been selected).
3. Methodology
3.1. Proposed Flowchart
This flowchart in Figure 1 below details the methodology of this study. Starting from a network graph, the routes to every destination of the graph are discovered, to which we apply Dijkstra’s traffic routing algorithm to determine the shortest path to every destination. During the routing of traffic, it may happen that the link in use is cut (route failure), leading to a modification of the network, resulting in a new route discovery. Using these new routes, we determine a new path to reach the destination, while making good use of network resources.
Figure 1. Flow chat of intended methodology.
To implement the proposed solution a software tool has been developed following the procedure presented.
3.2. Modeling and Design of the Software Tool
The UML language, also called Unified Modeling Language which is a graphical modeling language has been used to develop the present tool through a use cases diagram and classes diagram. NetBeans IDE has been used for an integrated development environment and JavaFX Scene Builder which is an interactive visual layout tool for designing JavaFX application user interfaces, and quickly building user interfaces; this thanks to its technique of dragging and dropping components.
After all these, the software tool Graphic Networks has been developed and the results of all these will be presented in the next part of the paper.
4. Results Obtained
4.1. Presentation of the Tool Developed
The methodology used to resolve the problem posed allowed us to obtain results which will be presented in this part. However, it is appropriate to recall the expected results.
The present work must deliver the following results:
A representation of the WDM network in the form of graphs (nodes + links).
Perform communications routing.
Simulate an incident (route or node failure).
Traffic redirection.
The platform built is called “Graphic Network”. The presentation of its different interfaces and its operation are the subject of the following sections.
1) The home page
Figure 2 presents the first interface that opens when launching the application.
Figure 2. Home page of Graphic network.
Once the application is launched, the user has the possibility of choosing the properties of the graph according to the type of network. For our case here we have:
The first column:
The second column is based more on the properties of the links between the nodes.
In this case we will click on Undirected and Weighted once this makes an arrow indicating to us that we can move on to the next interface which appears clickable.
By clicking on the button where we see the “arrow”, the user accesses the main interface of the application. Figure 3 presents the main interface of the proposed application.
Figure 3. Main interface of Graphic network.
In the next point we will present the modeling of the optical network of the local operator in the developed tool and the results obtained after implementing the proposed algorithm.
4.2. Modeling of the WDM Network and New Paths Identification
In this section we have an image of the WDM backbone of the local operator network. We’ve numbered it to make it easier to find your way around the model. Figure 4 shows the network as deployed by the local operator. The image is a capture from the network management system U2000 Transmission provided by the vendor Huawei Technologies.
Figure 4. The local network operator’s WDM network was captured from Huawei U2020 NMS.
In the following Figure 5, we show the screenshot of this network model, setting the cost of all links to 10. In fact, the real DWM network has been reproduced in our proposed tool for testing purposes.
Figure 5. Modeled WDM network.
4.2.1. Calculation of the Shortest Path from 1 to the Other Nodes
Figure 6 below shows node 1’s complete knowledge of routes to other nodes. From this discovery, node 1 knows which path to use to carry traffic to its different destinations.
Figure 6. Route discovery from node 1 to all the others.
4.2.2. Traffic Route Display from 1 to 51
Figure 7 shows the equipment used to route traffic from node 1 to node 51, through the nodes 2, 3, 4, 5, 11, 12, 13, 26, 25, 24, 23, 22, 27, 28, 29, 30, 31, 32, 33, 34 and 52.
Figure 7. Traffic route from node 1 to 51.
4.2.3. Traffic Route Display from 1 to 53
Figure 8 shows the equipment used to route traffic from node 1 to node 53, via nodes 2, 3, 4, 5, 11, 12, 13, 26, 25, 24, 46, 45, 43, 42, 41, 40, 39, 57, 56 and 55.
Figure 8. Traffic route display from 1 to 53.
4.2.4. Route Failure
Figure 9 below simulates a common incident in the optical backbone network, which is the cutting of an optical fiber cable. In our case, this is represented by the removal of the link between nodes 55 and 56.
Figure 9. Route failure between nodes 55 and 56.
4.2.5. Automatic Traffic Redirection after Route Failure
Once the link has been removed, traffic must be automatically redirected between node 1 and 53. For this, deleting the link automatically calculates the new path, which in this case is: 2, 3, 4, 5, 11, 12, 13, 26, 25, 24, 23, 22, 27, 28, 29, 30, 31, 32, 33, 34, 52 and 51. We have the illustration in Figure 10.
Figure 10. Automatic traffic redirection from 1 to 53.
4.2.6. Node Failure
Node 52 will be unable to route traffic, this can be either due to congestion on the node or a failure related to the outgoing port.
Figure 11 shows that an incident on a network node results in the deletion of that node, which automatically implies the deletion of the links attached to it. This incident modifies the graph matrix, automatically calculating the new path.
Figure 11. Failure of node 52.
4.2.7. Automatic Traffic Redirection after Node Failure
Figure 12 below shows the automatic redirection of traffic between nodes 1 and 53, taking into consideration the events of link failure between nodes 55 and 56 and the node 52 failure. The nodes involved in the redirected route are 2, 3, 4, 5, 11, 12, 13, 26, 25, 24, 23, 22, 27, 28, 29, 30, 31, 32, 33, 34, 47, 48, 49, 50 and 51.
Figure 12. New automatic traffic redirection from 1 to 53.
In this section, we have demonstrated the contribution of graph theory to the automatic redirection of traffic in the local operator’s WDM backbone. The “Graphic Network” tool developed is used to visualize how Dijkstra’s algorithm works to automatically route and reroute traffic from a source node to a destination. The usage of such tool can help optical network operator to easily identify redirection routes, reduce the down time and improve the availability of their network which will improve their customer’s satisfaction.
5. Conclusions
This work focused on graph-theoretic modeling of THE LOCAL OPERATOR’s WDM network and efficient traffic redirection algorithm. The aim was to propose an alternative in the management of automatic traffic redirection as done with ASON technology.
In view of the constraints observed in the deployment of ASON technology throughout THE LOCAL OPERATOR’s WDM network, we turned to the use of graph theory tools to provide a solution.
To put our research into practice, we have developed a Java-based application application that models the network and then, depending on link constraints, routes traffic along the best path. After an incident, either on the link (fiber optic cut) or congestion or failure on a node port (node deletion), it automatically redirects traffic to the destination. In this way, end-to-end service configuration can be envisaged using graph theory to perform all the functions offered by ASON.