Date of Award
Spring 2022
Document Type
Dissertation
Degree Name
Doctor of Philosophy (PhD)
Department
Mathematics, Statistics and Computer Science
Program
Computational Mathematical and Statistical Sciences
First Advisor
Madiraju, Praveen
Second Advisor
Puri, Satish
Third Advisor
Pantone, Jay
Abstract
Enumerating all routing paths among Autonomous Systems (ASes) at an Internet-scale is an intractable problem. The Border Gateway Protocol (BGP) is the standard exterior gateway protocol through which ASes exchange reachability information. Building an efficient path enumeration tool for a given network is an essential step toward estimating the resiliency of the network to cyber security attacks, such as routing origin and path hijacking. In our work, we use the matrix Latin multiplication method to compute all possible paths among all pairs of nodes. We parallelize this computation through the domain decomposition for matrix multiplication and implement our solution in the Julia high-performance programming language. We also compare our method with the classical Monte Carlo method. Our results provide positive evidence for the applicability of the method.