Μελέτη του Φαινομένου της Χιονοστιβάδας σε Διάφορους Τύπους Τοπολογιών
Date Issued
September 23, 2021
Type
Μεταπτυχιακή Διπλωματική Εργασία
Abstract
In the world of social networks, the diffusion of innovation, ideas and technologies, is studied under Cascade Models, which captures the way in which individuals adopt these new behaviours by observing the actions of their peers in their social circle. In network theory, the term information cascade describes a process, in which the spread of information is modelled as a new behaviour entering a network. This behaviour is adopted by the network nodes based on the number of nodes already following the new behaviour.
Meanwhile, information dissemination in traditional dynamic routing protocols is accomplished using flooding algorithms, which guarantees that the knowledge regarding changes in the topology is received by all nodes participating in the routing process. However, the overhead produced by blindly flooding the network with messages contributes to the storm problem, and many variations to classic routing propose more resource-conservative techniques for the dissemination of routing updates.
The main idea of this Thesis focuses on incorporating a variation of a cascade model, namely the Linear Threshold Model, in a dynamic routing algorithm, in order to minimise overhead. The Linear Threshold Model captures the influence node's link differently, and also assigns a different adoption threshold to each node. Thus, these metrics can represent the importance of the links and the nodes to the routing process, when derived based on traffic and structure related properties, respectively. Consequently, link loads are used to derive the weights of the model, while degree centrality is used to define individual adoption thresholds. Link load indicates the frequency of communication with the node on the end of that link and the degree to which the node participates in the routing process through that link. Degree centrality is used based on the idea that central nodes need to be informed about the network, due to them participating in the routing of network traffic with high probability.
This cascade-based approach is experimentally evaluated in a simulation environment across random geometric graphs of varying sizes and densities. Its performance is evaluated with respect to its ability to accurately route traffic after a link in the network fails, and is compared to the performance achieved by informing all (through flooding) and none of the network's nodes, which correspond to the best and worst-case scenarios, respectively. Two different traffic distributions are generated prior to testing the cascade model, uniform traffic distribution and Poisson traffic distribution. Additionally, two different link weight assignment methods are considered under these traffic approaches, with one of them taking into account only load from incoming traffic, and the second one both incoming and outgoing traffic. Ideally, the desired model would maximise routing accuracy, while minimising overhead in the dissemination of routing updates.
Through experimentation, it is shown that the cascade-based model is highly capable of spreading routing updates to few, but important nodes. In particular, it achieves close to 100% routing accuracy, delivering almost all of the traffic as effectively as flooding and significantly outperforming the worst-case scenario. In contrast, this close-to-optimal routing accuracy is achieved by covering a fairly small fraction of the network's nodes, which is inversely proportional to the network's size. The results are consistent with both uniform and Poisson traffic patterns in the network. However, the two link weight assignment methods do not differ much in their performance across the experiments.
Based on the acquired results, it is concluded that the proposed approach incorporating cascading behaviours to spread routing updates accomplishes its intended goal of minimising overhead without sacrificing routing accuracy, under the considered scenarios. Nonetheless, more thorough experimentation needs to take place under more diverse scenarios, before these results can be generalised. In particular, more extreme traffic distributions could highlight differences between the two link weight assignment methods, or indicate that more sophisticated adoption thresholds need to be considered. Last but not least, the structural properties that different topologies would present could likely affect performance, which is not investigated here.
Subjects