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, Sattish

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.

Included in

Mathematics Commons

Share

COinS