|
OPTIMIZATION IN THE SHORTEST PATH FIRST COMPUTATION
FOR THE QUAGGA SOFTWARE
ROUTING
V. Eramo, M. Listanti, G. Gasparro, A.
Cianfrani
University of Roma “La Sapienza”, INFOCOM Dept.
Via Eudossiana, 18 – 00184 Roma, Italy
Tel: +39 6 44585458; Fax: +39 6 4744481
E-mail: eramo@infocom.uniroma1.it
3.
Performance
Comparison between Cisco 2621 and Quagga
All performed tests are based on fully meshed network topologies,
with each router connected to each other through a different transit
network. Figure 4 shows an example of emulated fully meshed topology with 4
routers. It is important to remark that in representing the emulated
network as a directed weighted graph [2], each router and each transit
network of the emulated network topology becomes a vertex of the graph, and
each network-router link becomes an edge. Each edge is labelled with a cost
representing the interface cost of the link connecting a router to a
network [2]. In the following the cost of all the edges will be chosen to
be equal. When the Update LSA is sent as mentioned in Section 2, an interface
cost is varied so that the SPF
computation procedure is primed.
Figure 4 The emulated network
topology considered in the test-bed is fully meshed. Each router is
connected to each other through a different transit network
The SPF
computation complexity will depend on the number of vertexes and edges in
the graph representing the emulated network. Now let us denote with N, M the number of vertexes and the number of edges of the
directed graph representing the emulated network topology reported in
Figure 4. If we consider an emulated network topology composed by R routers, we have that:
 (3.1)
 (3.2)
It is important to notice that the number of edges M is almost proportional to the
number of vertexes N. In
particular from (3.1) and (3.2) we can assume that M=O(N).
The computational cost of the Dijsktra’s
algorithm depends on both the number of vertexes N and the number of edges M.
It is known that the SPF
computation time complexity is O((M+N)logN) or O(M+NlogN) depending on the data structure chosen
[11][12]. Experimental values taken on a Cisco 2621 and a PC based router
are reported in Figure 5.
Figure 5 The SPF Computation Time as a function
of the number of vertexes (N) of
the emulated network topology in a Cisco 2621 router and a PC based router.
The PC used is equipped with a 2.4Ghz processor, a 512Mbyte memory and Quagga 0.97.3 routing software.
We report the SPF
computation time as a function of the number of network topology vertexes.
The PC used is equipped with a 2.4Ghz processor, a 512Mbyte memory and Quagga 0.97.3 routing software. Notice as the
experimental values taken on a Cisco 2621 router perfectly agree with the
trend foreseen by the Dijsktra’s algorithm.
In fact as shown in Figure 5 we notice as the experimental measure curve of
the Cisco2621 fits the curve 0.041(M+NlogN) very well. On the contrary the results
obtained on a router based on the PC hardware and equipped with Quagga 0.97.3 routing software are quite different. The
computation time quickly increases up to 16 sec as the number of vertexes
reaches 5000 and measured values fit on the 6.06 10-4 N2 interpolating curve, as
shown in Figure 5.
Comparing the two curves, it appears that the Quagga
performance is better than the one of the Cisco 2621 only when the number
of routers R in the emulated
topology is smaller than 45 corresponding to N=700 vertexes. With more than 45 routers, instead, the Cisco
2621 performance becomes better, because Quagga
obviously pays the fees of a sub-optimal implementation of the SPF algorithm. On the basis of these
results we retain that some changes are needed inside the Quagga code, to obtain performances comparable to top
level commercial routers. Next section therefore is dedicated to the
analysis of the SPF algorithm and
to its optimisation.
|
