Paper
Paper (online)
Presentation
BGP is the de facto protocol used to manage a network’s reachabilityon the Internet. Network operators announce and withdraw theirprefixes on BGP to enable or to prevent communication towardstheir origin network, respectively. However, the withdrawal of aprefix could fail to propagate totally in the Internet and routestowards withdrawn prefixes could remain in the routing tablesof routers. These routes are called stuck or zombie BGP routes,and their persistence can lead to performance degradation, or evenpartial or complete outage. In this paper, we first revisit existingwork on BGP zombies using RIPE RIS beacons, identify the double-counting discrepancy, and revise the methodology to address thisproblem and detect zombies more accurately. Second, we point outlimitations of the RIPE RIS beacons with respect to their periodicity,lack of diversity, and noise, and introduce and deploy our ownbeacons, which address these limitations. Using our beacons andthe revised methodology, we analyze the lifespan of BGP zombies.We show that zombie routes can persist in RIBs for days, weeks,or even months. Furthermore, we document that BGP zombies canbe announced months after their original withdrawal, affectingnew ASes. Finally, we discuss interesting cases of long-lived zombieoutbreaks that affected large ISPs with hundreds of ASes in theircustomer cones.
Diploma Thesis (in Greek)
Presentation
In my thesis I studied the problem of Cautious Misinformation Minimization (CMM) which is defined as minimizing the spread of false information while minimizing the decrement of the spread of true information by limiting the interactions between the users, i.e., by removing a limited number of edges in the graph representing the network. The known Independent Cascade (IC) and Deterministic Linear Threshold (DLT) models are modified in this Thesis, in order to take into account the user’s specialization in the thematic category to which the disseminated information belongs. Under these models as well as the probabilistic Linear Threshold model (LT), the CMM problem is proved to be NP-Hard. Thus, to solve it under the LT and DLT models, greedy iterative algorithms are employed whose criterion for selecting the edge to be removed in each iteration is the maximum reduction of the sum of the difference between true information’s current spread and its initial one, and false information’s current spread.
The experimental evaluation of the proposed algorithms is carried out using real social networks. Their results are compared with the ones of the methods that utilize mainly topological features and partly the dynamic evolution of information dissemination. Based on these, the superiority of the proposed methods is highlighted since they achieve through the removal of a small number of edges the significant reduction of the spread of misinformation without greatly affecting the dissemination of true information.
The Minimum Linear Arrangement problem has been proven to be NP-complete for arbitrary graphs. However, it can be simplified by specifying the type of graph. There have been found efficient algorithms by applying restrictions to the input or the output, and there exist approximation techniques trying to achieve the optimal.