|
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
1.
Introduction
The
diffusion of open software implementing routing protocols, together with
the big computing power of normal PCs, have been raising a big interest
towards the possibility of developing a complete routing system based on
open software and standard low-cost hardware [1]. What still lacks is to
verify if and when actually the performances of these PC-based-routers can
compare to dedicated commercial systems.
We have
developed a set of tests to analyze the routing performances of a router running
the OSPF protocol [2][3][4], according to the IETF specifications
[5][6][7]. In particular we have taken Black Box measures [8] of the time
needed to perform the Shortest Path First (SPF) computation on a Personal Computer (PC) equipped with
Operating System Linux and Quagga 0.97.3 Routing Software [9]. The obtained
measures have been compared to the ones performed on a Cisco 2621 router
[10].
The evaluation of the Shortest Path First (SPF) computation time raises the evidence of a lack of
optimization in the Dijsktra’s algorithm implemented in Quagga
0.97.3. A deep analysis of the code evidenced that the data structures used
to implement the Candidate List [11] during the SPF calculation were not optimized. So we have modified the
code and have implemented a binary heap data structure [12]. The new
implementation allows a router based on the PC hardware and Quagga 0.97.3
routing software to have performance better than commercial OSPF routers.
|
