| The Internet is a critical communications infrastructure servicing billions of end-users world-wide. Due to its large scale and increasing complexity, many weaknesses have been discovered. For example, several exist in its policy-based inter-domain routing protocol BGP. Accordingly, solutions have been proposed, but few have experienced widespread adoption. Assuming most have merit, why are these solutions not being deployed? It is thought that unacceptable tradeoffs between field-based testing, performance gains, risk, cost, and necessity has led to a development/deployment impasse. To resolve this deadlock and incentivize deployments that address known Internet issues, two alternatives to large-scale field-based testing are promoted.;However, the AS Path Solver does not demonstrate the interactions between a path-vector routing protocol and other network activities (i.e., data transport protocols, application traffic). As such, a second technique is proposed to lower the resource consumption (i.e., memory and run-time) required by discrete-event network simulation of policy-based path-vector routing protocols. This technique is called the Scale-Down Transformation. Developed using Thevenin equivalence, Gaussian elimination, and several heuristics, the Scale-Down Transformation produces a modified network topology model that is reduced in its number of ASs. This reduction can lead to more efficient simulation in terms of lower runtime and memory usage. The Scale-Down Transformation also preserves several characteristics (e.g., length) of the path vectors stored in the simulated routing tables. It follows that simulated traffic flows entering/exiting the ASs are preserved over the topology reduction. Such scaled-down modeling can decompose large-scale experimentation into more manageable sub-experiments.;To determine if these two proposed techniques have practical use, their runtime and memory usage are measured over network topologies ranging in scale from tens to thousands of ASs. The AS Path Solver shows gains of at least a magnitude relative to discrete-event network simulation. The Scale-Down Transformation also has some gains, however, its gains can be dependent on certain characteristics of the topology reduction (e.g., removal of ASs having a minimal number of connected neighbors). In terms of fidelity, the Scale-Down Transformation's routing tables will contain a lesser number of path vectors than full-scale network simulation (or equivalently the AS Path Solver); however, neither technique exhibits path vector loss associated with the data forwarding operation. This is demonstrated via an example scale-down testing methodology which recreates and measures the spread of a large-scale Multiple Origin Autonomous System (i.e., MOAS) conflict over a network topology containing several thousands ASs.;Performance and validation assessment of BGP, a policy-based path-vector routing protocol, is difficult. Its testing methodologies have limited credibility due to small experimental scales and/or insufficient modeling support (e.g., lack of routing policy). To address these limitations, two new testing techniques are proposed herein. The first technique models a policy-based path-vector routing protocol using a group theoretic structure called a path algebra. This provides an algebraic framework which supports the use of Jacobi iteration to solve for an experimental topology's steady-state routing tables. This technique is called the AS Path Solver (where AS denotes an autonomous system). The AS Path Solver's output routing tables can be used to expose connectivity or traffic engineering problems caused by the routing protocol, network topology, and/or routing policy. It also possesses a straightforward algorithmic form which should be less difficult to implement than that needed for discrete-event network simulation. |
