In the context of network Trafic Engineering (TE), the Open Shortest Path First (OSPF) configuration of a communication network is optimized based on the maximum link utilization or the average link utilization of the network. In this paper, we introduce an OSPF Interior Gateway Protocol (IGP) weight optimization technique using a Digital Twin (DT) of the network that optimizes the weights based on Quality of Service (QoS) metrics, specifically the average End-to-End (E2E) trafic delay. Our results show that we can significantly minimize the average trafic delay of a network by optimizing the OSPF configuration using a DT.
We take inspiration from their work to introduce an OSPF optimization technique that considers QoS metrics. Using a Network Digital Twin (NDT) model, such as TwinNet, one can produce architectures capable of optimizing the OSPF configuration of a network for the QoS metrics of their choice.
To optimize the OSPF configuration of a network based on QoS metrics, we propose using a NDT: a Digital Twin (DT) of a communication network that is capable of optimizing the network and reflecting the behavior of the network [ 9]. Digital Twins (DT) are recently emerging in the ifeld of communication networks and there is a work-in-progress Internet Research Task Force (IRTF) draft on a reference architecture of a NDT [10]. The NDT takes information about the topology (including the OSPF configuration) and trafic flows going through its physical twin (the physical network we are optimizing) and updates the OSPF configuration of its physical twin based on the predicted optimal configuration.
We implement our NDT by combining RouteNet-F [11], a GNN model that predicts QoS metrics for a given network and its trafic flows, with a genetic algorithm designed to minimize trafic delays of an OMNeT++ simulated network (the physical twin) [ 12]. We show how our method improves the trafic delays of randomly generated network topologies by optimizing their OSPF configuration.
In Section 2, we summarize the state-of-the-art TE methods for OSPF optimization. In Section 3, we introduce some background which we base our NDT implementation on. In Section 4, we describe the method we propose to perform OSPF optimization using a NDT. In Section 5, we show how our OSPF optimization method using NDT was able to optimize the simulated network topologies. Lastly, we provide a concluding paragraph with the future work in Section 6.
OSPF weight optimization is the process of setting the Interior Gateway Protocol (IGP) metric of each link in the network to optimize for some metric of the network, such as maximum link utilization, average End-to-End (E2E) loss, etc. The IGP metric of a link in the OSPF protocol, also referred to as the weight of the link, is the cost of taking this link. Trafic flowing to a destination node from a source node is routed through the minimal-cost path.
Current methods in the literature only optimize for bottleneck link utilization or average link
utilization [
IGP Weight Optimization was proposed by Fortz and Thorup [
The neighbors of the current candidate OSPF configuration of a given network topology are defined as the following: • Single link weight change. • Splitting trafic to a destination node evenly across a random number of neighbors at a transit node (refer to Figure 1).
To prevent looping through visited OSPF configurations, they maintain a hash table of
all visited OSPF configurations. This algorithm can be terminated at any point during the
search to find a better OSPF configuration; however, it is not guaranteed that it will find the
global optimum configuration. Rusek et al. [
Dynamic IGP Weight Optimization was proposed by Brun and Garcia [
In addition to those diferences, Dynamic IGP Weight Optimization estimates the sourcedestination demand matrix from a time series of link demands rather than having prior knowledge of those demands. The resulting OSPF configuration recommendation is then based on the worst-case demand scenario out of the set of possible demands inferred from the link demands. However, this makes it much more computationally expensive than IGP Weight Optimization.
Routing by Back-propagation (RBB) is the latest OSPF optimization technique proposed by
Rusek et al. [
While the methods we listed in this section can find much better OSPF configurations in a short period, none of them consider any variable beyond link utilization for OSPF configuration. Before introducing our NDT for OSPF optimization, we introduce some of the related work used in our NDT implementation in the next section.
RouteNet-Fermi, also known as RouteNet-F, is a GNN model of a communication network proposed by the same authors of TwinNet, Ferriol-Galmés et al. [11] It takes the topology of the network (which includes link bandwidths, queuing policy of each interface, the number of bufers at each interface and their respective sizes), the trafic flows between each sourcedestination node (including the average bandwidth used, the packet size distribution and time distribution), and the route each trafic flow takes in the topology as input. The resulting output of RouteNet-F is the predicted delay, jitter, and loss of each trafic flow. Their results show that RouteNet-F can generalize and accurately predict QoS metrics on unseen topologies and trafic lfows. It serves as a ML based network model that is capable of predicting QoS metrics much faster than tools such as OMNeT++ [12]. For those reasons, we chose to use RouteNet-F as our digital network model in our NDT implementation in Section 4.
In the following section, we introduce genetic algorithms, the optimization technique that is coupled with RouteNet-F for our NDT implementation of QoS based OSPF optimization.
Genetic algorithms are search and optimization algorithms proposed by Holland [17]. They are inspired by the process of natural selection and evolution. They are characterized by the following seven steps: • Initialization where a population of potential solutions for an optimization problem is randomly generated. • Evaluation where each solution is evaluated using a fitness function. • Selection where solutions with a higher score are selected for “reproduction”. • Recombination where a pair or pairs of the highest-scoring solutions are randomly combined to create the new “population”. • Mutation where solutions in the new population are randomly modified to prevent the algorithm from converging early. • Replacement where new solutions replace the old solutions in the population when creating the next generation.
• Termination where the algorithm terminates at a specified stopping criterion.
Genetic algorithms are very simple to implement and are applicable to any fitness function rather than being specialized such as heuristic local search techniques. They are also less likely to be stuck in a local optimum due to the mutation step. However, they come at a computational expense. When using a ML digital model such as RouteNet-F to provide the metrics for our iftness function, we can aford to use genetic algorithms and find a much better solution than the current solution within a short period. We decided to use genetic algorithms for their simplicity and generalization as our goal is to show how we can use a NDT for optimizing OSPF configuration based on QoS metrics. While using a local search technique with heuristics such as those mentioned in Section 2 can improve the time it takes to find a better solution, using a genetic algorithm gives us the flexibility to choose our fitness function. In the following section, we describe the architecture of our NDT for OSPF optimization and the genetic algorithm we use.
Our proposed NDT architecture for OSPF optimization is shown in Figure 3. We use RouteNet-F as the model to predict the QoS metrics of the current trafic flows going through the network and couple it with a genetic algorithm to find an OSPF configuration that minimizes the average trafic delay in the network. Our genetic algorithm is initialized by mutating the current OSPF configuration to create a population of 2000 solutions in our experiments. Mutations have a 20% chance of occurring on each link in all generations. The solution with the minimum average trafic delay is then recombined with itself to create a new population. If no solution from the new generation has a lower average trafic delay than the previous generation for 4 generations our algorithm terminates. The population size and mutation probability as well as our termination criteria are hyper-parameters of our model and were selected based on our intuition. Algorithm 1 summarizes the implementation of our NDT for OSPF optimization.
To evaluate our implementation, we randomly generated three topologies, a 6-node topology, a 10-node topology, and a 20-node topology with randomly generated Poisson trafic flows ranging from 200 bits per second to 2000 bits per second for each source-destination pair. The link capacity of each link was set to 100kbps and all queuing policies were set to FIFO with a single 32kbits queue. We used the RouteNet-F model trained on the fat-tree = 128 dataset provided in the RouteNet-F paper [11]. For our networks (i.e. the “physical” twin) we used the same OMNeT++ simulation used to train RouteNet-F. The OSPF weights were also randomly initialized to either have a weight of 5 or 1 in our simulated networks. The genetic algorithm was also constrained to this set of weights to minimize its search space. In the following section, we report and discuss the results of our experiments.
In Figure 4, we plot the Cumulative Distribution Function (CDF) of the trafic flow delays going through each of our simulated topologies before and after optimization. We obtained the delays Algorithm 1: Digital Twin for Trafic Engineering
Input: , (where is the real network, and is the digital model) Parameter : generations without improvement before termination, size of generation ← retrieve topology and features of ← retrieve estimated distribution of each flow in ← ← predicted average flow delay of using ℎ ← 0 while True do ← generate weight configurations from using genetic algorithm and recompute routes ← predict the average flow delay of using ℎ ← ℎ + 1 if min(predictedDelays) < bestDelay then ← () ← [.()]
ℎ ← 0 end if generationsWithoutImprovement ≥ then
break end end ←
Apply to and retrieve average flow delays from from the OMNeT++ simulated topology (i.e. our “network physical twin”) in our experiments. Our results show that our technique successfully reduced the average trafic delay in all our randomly generated networks. Our method shifts the distribution of trafic delays closer to lower delays and consistently reduced the maximum trafic delay in the network in all our topologies. All our NDTs found a solution within 5 minutes on a GTX1080Ti GPU and an Intel i7 7700k CPU. Our promising results indicate that our NDT for OSPF optimization based on QoS metrics is viable and more importantly, allows us to optimize for other QoS metrics beyond delay with ease. We can optimize for other metrics by simply changing the fitness function. For instance, to optimize trafic loss or link utilization, we can change the fitness function to be negatively proportional to the maximum trafic loss or the maximum link utilization in the network without modifying the architecture.
Coupling our NDT architecture for optimizing a network with a smarter optimization algorithm and a desired optimization criteria opens the door for new methods of automating TE and network optimization.
(a) 6 Node topology. (b) 10 Node topology.
(c) 20 Node topology.
In this paper, we showed how one can use our NDT architecture to perform OSPF optimization based on QoS metrics. Our NDT was able to find OSPF configurations that significantly reduced the trafic delays in the twinned networks. However, our genetic algorithm was limited to a set of two weights and may take longer to terminate when the set of weights is large as it increases the search space. A better termination criterion in this case would be the percentage improvement in the last generations.
Using a smarter optimization algorithm such as a local search heuristic can also improve performance and the speed of finding a solution. However, the genetic algorithm provides a baseline implementation that can be extended further.
Our future work would include comparing our NDT for OSPF optimization to the state-of-theart OSPF optimization techniques using the average trafic delay, maximum link utilization and the time to arrive at a solution. Moreover, applying this architecture to a real network rather than a simulated network would show how well the NDT for OSPF optimization performs in practice and if changes are required to adjust for a real network.
We acknowledge the support of Ciena and the Natural Sciences and Engineering Research Council of Canada (NSERC). [9] P. Almasan, M. Ferriol-Galmés, J. Paillisse, J. Suárez-Varela, D. Perino, D. López, A. A. P.
Perales, P. Harvey, L. Ciavaglia, L. Wong, et al., Digital twin network: Opportunities and challenges, arXiv preprint arXiv:2201.01144 (2022). [10] C. Zhou, H. Yang, X. Duan, D. Lopez, A. Pastor, Q. Wu, M. Boucadair, C. Jacquenet, Digital Twin Network: Concepts and Reference Architecture, Internet-Draft draft-irtfnmrg-network-digital-twin-arch-03, Internet Engineering Task Force, 2023. URL: https:// datatracker.ietf.org/doc/draft-irtf-nmrg-network-digital-twin-arch/03/, work in Progress. [11] M. Ferriol-Galmés, J. Paillisse, J. Suárez-Varela, K. Rusek, S. Xiao, X. Shi, X. Cheng, P. BarletRos, A. Cabellos-Aparicio, Routenet-fermi: Network modeling with graph neural networks, IEEE/ACM Transactions on Networking (2023). [12] A. Varga, Omnet++, Modeling and tools for network simulation (2010) 35–59. [13] F. Francois, N. Wang, K. Moessner, S. Georgoulas, K. Xu, On igp link weight optimization for joint energy eficiency and load balancing improvement, Computer Communications 50 (2014) 130–141. [14] A. Nucci, S. Bhattacharyya, N. Taft, C. Diot, Igp link weight assignment for operational tier-1 backbones, IEEE/ACM Transactions on Networking 15 (2007) 789–802. [15] F. Giroire, S. Pérennes, I. Tahiri, On the hardness of equal shortest path routing, Electronic
Notes in Discrete Mathematics 41 (2013) 439–446. [16] E. W. Dijkstra, A note on two problems in connexion with graphs, Numerische mathematik 1 (1959) 269–271. [17] J. H. Holland, Genetic algorithms, Scientific American (1992).