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 suitable for resilient and cost-e ective optical networks, because of the following property: any single node failure causes no impact on the pairwise hopcounts in the remaining network; and no other graphs with fewer links satisfy this property [FP97].
In recent works, a special family of 2-connected graphs called twin graphs has been proposed to model optical backbone topologies due to interesting properties with respect to fault tolerance, resilience, cost (in number of links) and scalability [PCS13]. Twin graphs belong to the class of 2-geodetically-connected graphs, which means that each of them provides at least two node-disjoint geodesics (i.e., shortest paths with respect to the number of links), for all non-adjacent node pairs. Moreover, no other graphs with fewer links satisfy this property [FP97].
Thus, in topologies modeled as twin graphs, the survivable routing through shortest paths ensures that both the working and the backup paths are geodesics for any pair of non-adjacent nodes. So, compared Copyright c held by the author(s). Copying permitted for private and academic purposes. to other 2-connected topologies, such as rings, twin graphs can tolerate single failures more e ciently, without drastic changes in network performance (see Fig. 1). In addition to their topological characteristics, the feasibility of twin graphs as optical backbone network topologies should be assessed by considering their wavelength requirements [BB97]. The minimum number of wavelengths required to support a given tra c demand corresponds to the solution of the Routing and Wavelength Assignment (RWA) problem [MG02], which is one of the most important problems in the optical network design.
In this work, we analyze the modelling of optical backbone networks as twin graphs in comparison with real-world optical backbone networks, in order to verify the advantages and disadvantages of this new model compared to existing networks. For this purpose, we have considered two sets of networks: the set of all twin graphs with 9 up to 17 nodes, which totalizes 742 graphs, and a set of real-world optical backbone networks (reported in Pavan et al. [PMRP10]) with number of nodes also in the range from 9 up to 17. These sets of networks and their number of nodes (n) and average degree are presented in Tables 1 and 2, respectively. through a link e 2 E and uv the total number of geodesics from u to v. Then, the betweenness of link Be, is given by [GN02]:
Be = X u6=v uv(e) uv (1) and the maximum link betweenness is maxe2E Be.
Furthermore, we have computed the number of wavelengths for each network in these sets. This computation was carried out using the methodology present in Cousineau et al. [CPC+12]. These results are shown in Fig. 2.
The results were analyzed as function of the graph theory metrics in order to infer correlation between these data. Among all metrics considered, the maximum link betweenness showed the best linear correlation with the number of wavelengths. For this reason, and also for lack of space, we only present here the results obtained for the number of nodes and the maximum link betweenness, which are shown in Fig. 3.
Assuming that the number of wavelengths is a way 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 Fig. 2, twin graphs tend to require fewer wavelengths than real-world networks with same order.
0 4
For each network in these sets, we have computed the following topological characteristics, which correspond to metrics from graph theory: number of nodes, maximum degree, minimum degree, average degree, link density, diameter, average distance, link connectivity, node connectivity, algebraic connectivity, average link betweenness, maximum link betweenness, and minimum link betweenness. All these computations where performed using the IGRAPH package available for the software R. The de nition of maximum link betweenness is given as follows.
Let G = G(V; E) be a graph with u; v 2 V . Denote by uv(e) the number of geodesics from u to v that go 10
12 14 Number of nodes 16
For twin graphs the linear correlation coe cient ( ) between the number of wavelengths and the maximum link betweenness was 99.5%, con rming the positive association suggested by Fig. 3. This result highlights a strong in uence of the maximum congestion on a physical topology link with the number of wavelengths. Real-world networks also showed similar behavior, with = 98.3%.
0 4 10 20 30 40 Maximum link betweenness 50
In summary, our studies have pointed out some advantages of using twin graphs as a model for designing optical backbone networks. This graph class has proved to be e cient in terms of resilience and cost, including the use of wavelengths. The correlation between the maximum link betweenness and the number of wavelengths observed in twin graphs can be exploited 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.