RPIM: Inferring BGP Routing Policies in ISP Networks
BGP dictates routing between autonomous systems with rich policy mechanisms in today's Internet. Operators translate high level policy objectives into low level router configurations without a comprehensive understanding of the actual effects on the network behavior, leaving the routing management an error prone and time consuming procedure. A fundamental question is: how to verify the intended routing principles against the actual routing effects of an ISP? In this paper, we develop a Routing Policy Inference Model (RPIM) as the first step towards addressing this fundamental issue. RPIM extracts various policy patterns from the BGP routing tables and translates them into high level policy objectives of the ISP using a grouping and matching technique. Our work bridges the gap between the high level policy objectives and the actual routing effects, which provides network operators with a novel approach to verify their policy design principles, thus facilitating the routing management. We evaluate our approach by extensive simulations using the Internet AS level topology from CAIDA and the real routing data from the Abilene network. Simulation results show that RPIM achieves over 78.94% average inference accuracy in our suggested optimal threshold range. We also verify RPIM on several operating ISPs by the registered policies in an Internet Routing Registry (IRR) A representative case study on AS3292 demonstrates that RPIM effectively infers high level policy objectives from routing data.
2011 IEEE Global Telecommunications Conference GLOBECOM 2011