GSoC/GCI Archive
Google Summer of Code 2010 Freifunk

Implementation of a Bounded Incremental Shortest Path Algorithm for olsrd

by SauloQueiroz for Freifunk

olsrd uses Dijkstra's as shortest path (SP) algorithm, i.e., SPs are calculated from scratch for all known destinations upon incoming routing information that changes topology sets. Bounded Incremental Computation (BIC) shortest path algorithms aims at saving computation running time by bounding its complexity to the number of routers that were affected by topology changes. This proposal aims at implementing and performing comprehensive evaluation of a BIC shortest path algorithm for the olsrd.