Advanced search
Start date

Evolving Graphs in the Modeling and Analysis of Dynamic Networks

Full text
Paulo Henrique Floriano
Total Authors: 1
Document type: Master's Dissertation
Press: São Paulo.
Institution: Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI)
Defense date:
Examining board members:
Alfredo Goldman Vel Lejbman; Raquel Aparecida de Freitas Mini; Jose Coelho de Pina Junior
Advisor: Alfredo Goldman Vel Lejbman

Lately, several networks with dynamic properties (for instance MANETs, DTNs, opportunistic networks, etc) are functioning. In this work, we studied a model for these networks called Evolving Graphs, which allows the expression of the dynamicity of the conections between nodes through a simple extension of the common graph structure. This model is used by the framework proposed by Casteigts et al. to define distributed algorithms in dynamic networks, which uses evolving graphs to represent the network topology and graph relabelling to express the communication between nodes. Using this approach, we study the distributed mutual exclusion problem in dynamic networks and several algorithms proposed to solve it, in order to define and validate their necessary and sufficient connectivity conditions. Apart from the formalization of algorithms, the evolving graphs model can also be used to analyze dynamic networks. Dynamic network traces are widely used in the literature in order to study algorithms, as they generate better results than simulated networks with movement patterns. From the details of every connection between nodes in a trace, it is possible to build an evolving graph, from which a large amount of information can be extracted, such as optimal journeys between nodes, variation of the conectivity over time, stability and periodicity. With the aforementioned information, a researcher might observe the characteristics of a trace more precisely, which facilitates the process of choosing the most appropriate trace for his needs. Furthermore, the early knowledge of such characteristics of a network helps in the study of the behavior of the algorithms exected over it and provides a validation for the assumptions usually made by the researchers. In order to provide this information, we developed a web tool which analyzes dynamic network traces and aggregates the data in an easily readable format. In this work, we describe the implementation and usefulness of every service in the tool. (AU)

FAPESP's process: 09/13201-9 - A Distributed Computing Model for Dynamic Networks
Grantee:Paulo Henrique Floriano
Support type: Scholarships in Brazil - Master