Shortest Path First
David Young
30 November 2004
The Shortest Path First (SPF) Library computes the "best" nexthop to every destination on the community wireless network, by applying Dijkstra's Shortest Path First algorithm to the link-states and metrics in the link-state database.
The name "Shortest Path First Library" (SPF Library) is not quite right: before implementation began, we decided that programming an abstract SPF library would needlessly complicate the HSLS daemon, without adding a meaningful potential for code re-use. The SPF library is deeply integrated with the daemon, its data structures, and its subroutine library.
Our HSLS daemon implements SPF efficiently using a heap---for N the number of link-states, our implementation finds shortest paths to all destinations in O(N log N) time. The efficiency is important, since the testbed computers are not very powerful, but a dynamic wireless network will cause many SPF re-calculations. The daemon computes shortest paths once for each address family. That is, on a multi-protocol network, it will compute shortest paths once for IPv4, and a second time for IPv6. The output of the SPF computation is a set of (destination, nexthop) pairs. When the daemon completes an SPF computation, it compares the output with the output from the last SPF computation, indicating added/deleted/changed pairs to Quagga/Zebra using the Routing Information Base abstraction. Then the daemon discards the old pairs. New pairs are stored with the address family object (hsls_af) for comparison against the next SPF result. In tests on our indoor testbed, the SPF library computes correct destination/nexthop pairs from the link-state database and inserts them into Zebra using the HSLS RIB abstraction.
Some work remains to be done on the SPF library. Routes to individual hosts are computed; routes to subnets (sets of hosts) are not. It will be necessary to modify the SPF calculation to match destinations by both IP number and mask length. Also, before updating the RIB, it will be necessary to post-process destination/nexthop pairs in order to filter-out hosts and subnets that are fully contained by subnets with lower metrics.
