Performance Evaluation of Dynamic Networks using an Evolving Graph Combinatorial Model

Alfredo Goldman

USP-SP Bresil


The highly dynamic behavior of wireless networks make them very difficult to evaluate, e.g. as far as the performance of routing algorithms is concerned. However, some of them have a predictable dynamics, as the temporal variations in the network topology are somehow deterministic. Recently, a graph theoretic model -- the evolving graphs -- was proposed to help capture the dynamic behavior of these networks, in view of the construction of least cost routing and other algorithms. Thus we used the NS2 network simulator to first implement an evolving graph based routing protocol, and then to evaluate such protocol compared to three major ad-hoc protocols (DSDV, DSR, AODV). Our experiments showed that evolving graphs have all the potentials to be an effective and powerful tool in the development of algorithms for dynamic networks, with predictable dynamics at least. In order to make this model widely applicable, however, some practical issues still have to be addressed and incorporated into the model, like stochastically predictable behavior and adaptive routing. (Authors: Afonso Ferreira, Alfredo Goldman and Julian Monteiro)

[Alfredo Goldman]
[USP-SP Bresil]