Towards Large-Scale Testing of Policy-Based Routing via Path Algebraic and Scaled-Down Topological Modeling

Open Access
Carl, Glenn
Graduate Program:
Electrical Engineering
Doctor of Philosophy
Document Type:
Date of Defense:
February 19, 2008
Committee Members:
  • George Kesidis, Committee Chair
  • John Metzner, Committee Member
  • David Jonathan Miller, Committee Member
  • Peng Liu, Committee Member
  • policy-based routing
  • network testing and evaluation
  • large-scale simulation
  • path algebras
  • topological scale-down
Due to the Internet's large scale and increasing complexity, many weaknesses have been discovered in its policy-based inter-domain routing protocol BGP. Accordingly, solutions have been proposed, but few have experienced widespread adoption. It is thought that unacceptable tradeoffs between field-based testing, performance gains, risk, and other factors are causing 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. Performance and validation assessment of BGP, a policy-based path vectoring routing protocol, is difficult. Its testing methodologies are generally limited to small experimental scales and/or contain insufficient modeling detail (e.g., lack of routing policy). To address these limitations, two new testing techniques are proposed herein. The first technique, the AS Path Solver (where AS denotes an autonomous system), models a policy-based path vectoring routing protocol using a group theoretic structure called a path algebra. This approach develops an algebraic framework which supports the use of Jacobi iteration to solve for an experimental topology's steady-state routing tables. As such, the AS Path Solver possesses a straightforward algorithmic form which should be less difficult to implement than that needed for discrete-event network simulation. However, the AS Path Solver does not demonstrate the interactions between a path-vector routing protocol and other network activities (i.e., non-routing protocols, application traffic). As such, a second technique called the Scale-Down Transformation is proposed to lower the resource consumption (i.e., memory and run-time) required by discrete-event network simulation of path-vector routing protocols. 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. The Scale-Down Transformation also preserves several characteristics (e.g., length) of the path vectors such that simulated traffic flows entering/exiting the ASs are preserved over the topology reduction. To determine if these two proposed techniques are practical, their performance (i.e., run-time and memory usage) are measured over network topologies ranging in scale from tens to thousands of ASs.