Twin Graphs for Designing Resilient Optical Backbone Networks K.F. Silva LabTel at Federal University of Espı́rito Santo - UFES kamilla.f.silva@aluno.ufes.br M.H.M. Paiva LabTel at Federal University of Espı́rito Santo - UFES marcia.paiva@ufes.br M.E.V. Segatto LabTel at Federal University of Espı́rito Santo - UFES segatto@ele.ufes.br Abstract In this work, we investigate the use of twin graphs as an alternative to model optical backbone networks, as recently proposed in the literature [PCS13]. Twin graphs are suit- able for resilient and cost-effective optical net- works, because of the following property: any Figure 1: After any single node removal in a twin single node failure causes no impact on the topology, there is always a backup path which has the pairwise hopcounts in the remaining network; same length of the working path. In a ring topology, and no other graphs with fewer links satisfy the backup path can be much larger than the working this property [FP97]. path, since the length of both these paths have always to sum up the length of the ring. In recent works, a special family of 2-connected graphs called twin graphs has been proposed to model optical backbone topologies due to interesting proper- to other 2-connected topologies, such as rings, twin ties with respect to fault tolerance, resilience, cost (in graphs can tolerate single failures more efficiently, number of links) and scalability [PCS13]. Twin graphs without drastic changes in network performance (see belong to the class of 2-geodetically-connected graphs, Fig. 1). In addition to their topological characteristics, which means that each of them provides at least two the feasibility of twin graphs as optical backbone net- node-disjoint geodesics (i.e., shortest paths with re- work topologies should be assessed by considering their spect to the number of links), for all non-adjacent node wavelength requirements [BB97]. The minimum num- pairs. Moreover, no other graphs with fewer links sat- ber of wavelengths required to support a given traffic isfy this property [FP97]. demand corresponds to the solution of the Routing Thus, in topologies modeled as twin graphs, the sur- and Wavelength Assignment (RWA) problem [MG02], vivable routing through shortest paths ensures that which is one of the most important problems in the both the working and the backup paths are geodesics optical network design. for any pair of non-adjacent nodes. So, compared In this work, we analyze the modelling of optical Copyright c held by the author(s). Copying permitted for pri- backbone networks as twin graphs in comparison with vate and academic purposes. real-world optical backbone networks, in order to ver- ify the advantages and disadvantages of this new model compared to existing networks. For this purpose, we through a link e ∈ E and σuv the total number of have considered two sets of networks: the set of all geodesics from u to v. Then, the betweenness of link twin graphs with 9 up to 17 nodes, which totalizes B e , is given by [GN02]: 742 graphs, and a set of real-world optical backbone networks (reported in Pavan et al. [PMRP10]) with X σuv (e) Be = (1) number of nodes also in the range from 9 up to 17. σuv u6=v These sets of networks and their number of nodes (n) and average degree are presented in Tables 1 and 2, and the maximum link betweenness is maxe∈E B e . respectively. Furthermore, we have computed the number of Table 1: Set of twin graphs (all twin graphs from 9 to wavelengths for each network in these sets. This 17 nodes). computation was carried out using the methodology present in Cousineau et al. [CPC+ 12]. These results are shown in Fig. 2. n Amount by n Average degree The results were analyzed as function of the graph 9 5 3.11 theory metrics in order to infer correlation between 10 9 3.20 these data. Among all metrics considered, the max- 11 13 3.27 imum link betweenness showed the best linear corre- 12 23 3.33 lation with the number of wavelengths. For this rea- 13 35 3.38 son, and also for lack of space, we only present here 14 63 3.43 the results obtained for the number of nodes and the 15 102 3.47 maximum link betweenness, which are shown in Fig. 3. 16 182 3.50 Assuming that the number of wavelengths is a way 17 310 3.53 to evaluate the network cost, twin graphs appeared as a viable alternative to model networks that have cost at least as good as real-world networks. As shown in Table 2: Set of real-world networks with 9 up to 17 Fig. 2, twin graphs tend to require fewer wavelengths nodes. than real-world networks with same order. Network n Average degree VIA Network 9 2.67 Bren 10 2.20 40 twin graphs RNP 10 2.40 real networks CESNET 12 3.17 Number of wavelengths 30 vBNS 12 2.83 Italy 14 4.14 NSFNET 14 3.00 20 Austria 15 2.93 Mzima 15 2.53 ARNES 17 2.35 10 Germany 17 3.06 Spain 17 3.29 0 For each network in these sets, we have computed 10 12 14 16 the following topological characteristics, which corre- Number of nodes spond to metrics from graph theory: number of nodes, maximum degree, minimum degree, average degree, Figure 2: Number of wavelengths given the number of link density, diameter, average distance, link connec- nodes for twin graphs and real-world networks. tivity, node connectivity, algebraic connectivity, aver- age link betweenness, maximum link betweenness, and minimum link betweenness. All these computations For twin graphs the linear correlation coefficient (ρ) where performed using the IGRAPH package avail- between the number of wavelengths and the maximum able for the software R. The definition of maximum link betweenness was 99.5%, confirming the positive link betweenness is given as follows. association suggested by Fig. 3. This result high- Let G = G(V, E) be a graph with u, v ∈ V . Denote lights a strong influence of the maximum congestion by σuv (e) the number of geodesics from u to v that go on a physical topology link with the number of wave- lengths. Real-world networks also showed similar be- [GN02] M. Girvan and M. E. J. Newman. Com- havior, with ρ = 98.3%. munity structure in social and biologi- cal networks. Proceedings of the National Academy of Sciences, 99(12):7821–7826, 2002. 40 twin graphs real networks [MG02] C.S.R. Murthy and M. Gurusamy. WDM optical networks: concepts, design, and al- Number of wavelengths 30 gorithms. Prentice Hall, New Jersey, 2002. [PCS13] M.H.M Paiva, G. Caporossi, and M.E.V. 20 Segatto. Twin graphs for OTN physical topology design. Les Cahiers du GERAD, 48:1–12, 2013. 10 [PMRP10] C. Pavan, R.M. Morais, R.F. Rocha, and A.N. Pinto. Generating realistic optical transport network topologies. IEEE/OSA 0 0 10 20 30 40 50 Journal of Optical Communications and Maximum link betweenness Networking, 2(1):80–90, 2010. Figure 3: Number of wavelengths given the maximum link betweenness for twin graphs and real-world net- works. In summary, our studies have pointed out some ad- vantages of using twin graphs as a model for design- ing optical backbone networks. This graph class has proved to be efficient in terms of resilience and cost, including the use of wavelengths. The correlation be- tween the maximum link betweenness and the num- ber of wavelengths observed in twin graphs can be ex- ploited in algorithms for solving the RWA problem. For future work, we are working on lower and upper bounds for the number of wavelengths based on the maximum link betweenness. We will also explore the behavior of twin graphs in the presence of multiple failures. References [BB97] Stefano Baroni and Polina Bayvel. Wave- length requirements in arbitrarily con- nected wavelength-routed optical net- works. Journal of lightwave technology, 15(2):242–251, 1997. [CPC+ 12] M. Cousineau, S. Perron, G. Caporossi, M.H.M Paiva, and M.E.V. Segatto. RWA problem with geodesics in realistic OTN topologies. Optical Switching and Net- working, pages 74–80, 2012. [FP97] A. Farley and A. Proskurowski. Minimum self-repairing graphs. Graphs and Combi- natorics, 13:345–351, 1997.