The role of routing policies in the internet : stability, security and load-balancing

Abstract

In this thesis, we study the problem of computing a set of routing paths within a computer network (e.g., the Internet, and ISP network). In the first part of the thesis, we study the convergence and security problems that arise in real-world inter-domain routing protocols (i.e., the Border Gateway Protocol) from a computational complexity perspective. We show that the most interesting problems are computationally intractable, unless several constraints on routing protocol configuration languages and network topologies are enforced. In the last part of the thesis, we show that computing the best paths for achieving reasonable network utilization is a computational expensive task from an algorithmic perspective, unless the topology must satisfy certain constraints.