|
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
2.
Description of the test-bed for the
evaluation of the SPF computation
time
The test aims at determining how long it takes for a Device Under
Test (DUT) to complete the computation of the SPF. The DUT can be either a CISCO 2621 or a PC based router.
To achieve this result we use the test configuration reported in Figure 1.
The network topology is made up of two real routers (a testing PC and the
DUT) and a variable number of fictitious routers and networks, so that the
DUT will have to find the shortest path to all the vertexes of the emulated
network, a vertex being either a network or a router. In particular the
emulated network topology is generated by means of the software BRITE
illustrated and available in [13][14][15]. So that the DUT
“sees” the emulated network topology it is needed that the
testing PC sends to the DUT some appropriate Link State Advertisements (LSAs)
describing the emulated network topology. For this reason the PC has been
equipped with the LSA generator software SPOOF illustrated and available in
[16].
Figure 1 Test-bed for the
evaluation of the SPF computation time in a Device Under Test (DUT). The
DUT can be either a Cisco2621 router or a PC based router. The emulated
network topology is generated by the testing PC equipped with BRITE
software. The testing PC is also equipped with the SPOOF software that
allows the LSAs describing the emulated network topology to be sent to the
DUT
The IETF has been defining the
measure methodology for the SPF
computation [5][6][7][8]. Next we describe the procedure allowing the SPF to be computed. To understand the
test methodology proposed, we remember that OSPF routers use to schedule
the instant in which the SPF
computation starts to avoid to perform the calculation too many times when
receiving Update LSAs [2]. So, when an Update LSA arrives,, notifying for example
a cost variation in an emulated network link, the SPF computation start time is scheduled with a fixed delay, a
timer is set and the SPF
calculation starts only when the timer expires. Moreover, another timer
enforces a lag between two consecutive SPF
computations. In particular the following two timers are defined in [2]:
-spf_delay: time between receiving an Update LSA and starting
the SPF computation;
-spf_hold_time: time between two consecutive SPF computations.
The SPF computation time
measurement consists of two different steps, with different settings of
these two timers. First as shown in Figure 2 we set both the timers to 0,
so forcing the DUT to immediately start the SPF computation when it receives an Update LSA. In Figure 2 we
denote with RTT the Round Trip
Time and further we assume that the propagation time is the same for the
two directions Testing PC-DUT and DUT-Testing PC.
Figure 2 Time measure TtotalSPF . The spf_delay and spf_hold_time router timers are set to zero and the SPF computation is performed.
The first step of
the test consists in loading the emulated network into the DUT and in
sending an Update LSA at time tsend_u
followed after a little delay by a Duplicate LSA at time tsend_d. The DUT
processes the Update LSA in the time interval Tu_LSA and starts to execute the SPF algorithm. Once begun, the SPF process cannot be interrupted,
and goes on till its end. Then the DUT processes the Duplicate LSA in the
time interval Td_LSA
and sends back immediately, according to the OSPF protocol rules, its
Acknowledge LSA. Thus we can use the Acknowledge LSA of the Duplicate LSA
to understand when the SPF
computation ends. In particular in this first test we measure the time TtotalSPF, which represents the time difference
between the sending of the Update LSA at time tsend_u and the receiving of the
Acknowledge LSA of the Duplicate LSA at time tack_d. As shown in Figure 2, the TtotalSPF time can be
expressed as follows:
 (2.1)
wherein
- RTT
is the Round Trip Time between the Testing PC and the DUT;
- Tu_LSA
is the Update LSA processing time;
- Td_LSA
is the Duplicate LSA processing time;
- TSPF
is the SPF computation time
- ToverheadºRTT+Tu_LSA+ Td_LSA
Hence in the performed measure
we are able to evaluate TtotalSPF
but we are interested in evaluating TSPF.
In order to make this we evaluate Toverhead
and subtract it from TtotalSPF
obtaining TSPF, that
is:
 (2.2)
So in order to obtain TSPF
we estimate Toverhead
by performing a second test where we set both the SPF spf_delay and spf_hold_time timers to high values
(60 sec). This time the DUT receives the Update LSA and schedules the SPF computation start time but does
not execute it because the timers are too high. Instead the DUT goes on
processing the Duplicate LSA and sends back the Acknowledge LSA of the
Duplicate LSA as illustrated in Figure 3. The time difference between the
sending of the Update LSA and the receiving of the Duplicate LSA
Acknowledge is exactly Toverhead.
Figure 3 Time measure Toverhead. The spf_delay and spf_hold_time router timers are set to high values (60 sec.)
and the SPF computation is not
performed.
|
