=Paper=
{{Paper
|id=Vol-1727/ssn16-final14
|storemode=property
|title=Twin Graphs for Designing Resilient Optical Backbone Networks
|pdfUrl=https://ceur-ws.org/Vol-1727/ssn16-final14.pdf
|volume=Vol-1727
|authors=Kamilla Silva,Marcia Paiva,Marcelo Segatto
|dblpUrl=https://dblp.org/rec/conf/ssn/SilvaPS16
}}
==Twin Graphs for Designing Resilient Optical Backbone Networks==
https://ceur-ws.org/Vol-1727/ssn16-final14.pdf
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.