Path Preserving Scale Down for Validation of Internet Inter-Domain Routing Protocols

New solutions have been proposed to address problems with the Internet's interdomain routing protocol, BGP. Before their deployment, validation of incremental performance gains and backwards compatibility is necessary. For this task, the Internet's large size and complexity make all techniques but simulation infeasible. When performing large scale network simulations, memory requirements for routing table storage can become a limiting factor. This work uses model reduction to mitigate this problem, with reduction defined in terms of the number of routers. Our framework uses path properties specific to interdomain routing to define the conditions of a path-preserving scale-down transformation. For implementation, vertex contraction and deletion were used to remove routers from a preliminary nominal network model. Vertex contraction was seen to violate the conditions of the transformation. A small subgraph from a measured topology is used for experimental validation. Routing tables are compared to show equivalence under the model reduction

1 Introduction

Problems with the Internet's de facto interdomain routing protocol, BGP, have been well-documented (Feamster, Balakrishnan, and Rexford 2004a[5]). Such issues have led to proposal of new or improved networking architectures (Feamster et al. 2004b[6], Li et al. 2005[17], Greenberg et al. 2005[9]), but in today's conservative investment climate, even limited deployments of may incur excessive cost. Thus, a need exists to demostrate incremental performance gains and backwards compatibility before deployment of network technologies.