Large-scale Network Analysis on Distributed Architectures

Questa dissertazione esamina le sfide e i limiti che gli algoritmi di analisi di grafi incontrano in architetture distribuite costituite da personal computer. In particolare, analizza il comportamento dell'algoritmo del PageRank così come implementato in una popolare libreria C++ di analisi di grafi distribuiti, la Parallel Boost Graph Library (Parallel BGL). I risultati qui presentati mostrano che il modello di programmazione parallela Bulk Synchronous Parallel è inadatto all'implementazione efficiente del PageRank su cluster costituiti da personal computer. L'implementazione analizzata ha infatti evidenziato una scalabilità negativa, il tempo di esecuzione dell'algoritmo aumenta linearmente in funzione del numero di processori. Questi risultati sono stati ottenuti lanciando l'algoritmo del PageRank della Parallel BGL su un cluster di 43 PC dual-core con 2GB di RAM l'uno, usando diversi grafi scelti in modo da facilitare l'identificazione delle variabili che influenzano la scalabilità. Grafi rappresentanti modelli diversi hanno dato risultati differenti, mostrando che c'è una relazione tra il coefficiente di clustering e l'inclinazione della retta che rappresenta il tempo in funzione del numero di processori. Ad esempio, i grafi Erdős–Rényi, aventi un basso coefficiente di clustering, hanno rappresentato il caso peggiore nei test del PageRank, mentre i grafi Small-World, aventi un alto coefficiente di clustering, hanno rappresentato il caso migliore. Anche le dimensioni del grafo hanno mostrato un'influenza sul tempo di esecuzione particolarmente interessante. Infatti, si è mostrato che la relazione tra il numero di nodi e il numero di archi determina il tempo totale.

Analisi di grafi su architetture a memoria distribuita

Questo lavoro di tesi tratta il tema delle reti complesse, mostrando i principali modelli di rete complessa quali: il modello Random, il modello Small-World ed il modello Scale-free; si introdurranno alcune metriche usate per descrivere le reti complesse quali la Degree centrality, la Closeness centrality e la Betweenness centrality; si descriveranno i problemi da tenere in considerazione durante la definizione e l’implementazione di algoritmi su grafi; i modelli di calcolo su cui progettare gli algoritmi per risolvere i problemi su grafi; un’analisi prestazionale degli algoritmi proposti per calcolare i valori di Beweenness centrality su grafi di medio-grandi dimensioni. Parte di questo lavoro di tesi è consistito nello sviluppo di LANA, LArge-scale Network Analyzer, un software che permette il calcolo e l’analisi di varie metriche di centralità su grafo.

Data dissemination over complex networks through gossip

This thesis offers a practical and theoretical evaluations about gossip-epidemic algorithms, comparing those most common in the literature with new proposed algorithms and analyzing their behavior. Tests have been executed using one hundred graphs that has been randomly generated by Large Unstructured NEtwork Simulator (LUNES), a simulation software provided by Parallel and Distributed Simulation Research Group (PADS), of the Department of Computer Science, Università di Bologna and simulated using Advanced RTI System (ARTÌS), based on the High Level Architecture standard. Literatures algorithms have been analyzed and taken as base for new algorithms.

Stationary states in random walks on networks

In this thesis we dealt with the problem of describing a transportation network in which the objects in movement were subject to both finite transportation capacity and finite accomodation capacity. The movements across such a system are realistically of a simultaneous nature which poses some challenges when formulating a mathematical description. We tried to derive such a general modellization from one posed on a simplified problem based on asyncronicity in particle transitions. We did so considering one-step processes based on the assumption that the system could be describable through discrete time Markov processes with finite state space. After describing the pre-established dynamics in terms of master equations we determined stationary states for the considered processes. Numerical simulations then led to the conclusion that a general system naturally evolves toward a congestion state when its particle transition simultaneously and we consider one single constraint in the form of network node capacity. Moreover the congested nodes of a system tend to be located in adjacent spots in the network, thus forming local clusters of congested nodes.

Decrescita sostenibile applicata alla mobilità nelle aree urbane.

La mobilità nelle aree urbane di medie e grandi dimensioni risente di molte criticità e spesso è causa di numerose discussioni. L'utilizzo sempre crescente del mezzo di trasporto privato ha prodotto conseguenze negative: l'aumento del traffico e degli incidenti stradali, dell'inquinamento atmosferico e del rumore sono accompagnati da un forte spreco energetico. Dall'altra parte, il trasporto pubblico locale (TPL) non è riuscito a costruirsi canali preferenziali all'interno dell'immaginario cittadino, poiché sottomesso da un modello economico e un mercato fortemente dipendenti dall'automobile. Una via d'uscita dalla mobilità non sostenibile basata sull'utilizzo di combustibili fossili porta a concepire un trasporto pubblico locale gratuito, fruibile dal cittadino in qualsiasi momento della giornata. Attraverso un'analisi dell'azienda del trasporto pubblico bolognese (ATC) e dei dati provenienti dalla sanità regionale, questa tesi intende mostrare che vi sarà un miglioramento della qualità di vita in aree urbane nel momento in cui la teoria della decrescita venga condivisa da tutti i cittadini. Così sarà possibile liberare i centri urbani dai mezzi privati e quindi dagli alti livelli di inquinamento acustico e atmosferico, e dare ai cittadini la vera libertà di movimento. Mobility in medium and large sized urban areas is critical and often a cause for numerous debates. The use of private transport is in constant increase and has generated negative consequences: congestion and road accidents, air and noise pollutio as well as a considerable waste of energy. On the other hand, the local public transport (LPT) has not succeeded in representing the preferred choice by citizens in the urban imaginary. Its potential has been subdued by economic models and markets that are largely dependant on the production of vehicles. An alternative to the current non sustainable mobility based on the combustion of fossil fuels could be the provision of a free local transport network available to the citizen from anywhere at any time. This dissertation's objective is to show how an improvement of the quality of life in urban areas is connected to a collective awareness on the degrowth theory. I intend to achieve this by analysing thoroughly the system of the public transportation agency in Bologna (ATC) and considering data from the local health department. Only then we will be able to limit private vehicles from city centres and as a result of that drastically decrease air and noise pollution whilst providing a true service for a free moving citizen.

Transportation theory and planning

The aim of this research is to analyze the transport system and its subcomponents in order to highlight which are the design tools for physical and/or organizational projects related to transport supply systems. A characteristic of the transport systems is that the change of their structures can recoil on several entities, groups of entities, which constitute the community. The construction of a new infrastructure can modify both the transport service characteristic for all the user of the entire network; for example, the construction of a transportation infrastructure can change not only the transport service characteristics for the users of the entire network in which it is part of, but also it produces economical, social, and environmental effects. Therefore, the interventions or the improvements choices must be performed using a rational decision making approach. This approach requires that these choices are taken through the quantitative evaluation of the different effects caused by the different intervention plans. This approach becomes even more necessary when the decisions are taken in behalf of the community. Then, in order to understand how to develop a planning process in Transportation I will firstly analyze the transport system and the mathematical models used to describe it: these models provide us significant indicators which can be used to evaluate the effects of possible interventions. In conclusion, I will move on the topics related to the transport planning, analyzing the planning process, and the variables that have to be considered to perform a feasibility analysis or to compare different alternatives. In conclusion I will perform a preliminary analysis of a new transit system which is planned to be developed in New York City.

Performance of LTE-V2V for Cooperative Awareness

The large scale development of an Intelligent Transportation System is very close. The main component of such a smart environment is the network that provides connectivity for all vehicles. Public safety is the most demanding application because requires a fast, reliable and secure communication. Although IEEE 802.11p is presently the only full wireless standard for vehicular communications, recent advancements in 3GPP LTE provide support to direct communications and the ongoing activities are also addressing the vehicle to vehicle case. This thesis focuses on the resource allocation procedures and performance of LTE-V2V. To this aim, a MATLAB simulator has been implemented and results have been obtained adopting different mobility models for both in-coverage and out-of-coverage scenarios.