System and method for statistical analysis of border gateway protocol (BGP) configurations

• US 20070250902A1
• Filed: 11/30/2006
• Published: 10/25/2007
• Est. Priority Date: 11/20/2008
• Status: Active Grant

• Current Assignee: Perspecta Labs Inc. (Perspecta, Inc.)
• Original Assignee: Telcordia Technologies Incorporated (Telefonaktiebolaget LM Ericsson)
• Inventors: Vaidyanathan, Ravichander
• Granted Patent: US 8,214,876 B2
• Time in Patent Office: Days
• US Class Current: 726/1
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 41/0894 Policy-based network configuration management
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing

Abstract

Routing and connectivity in the Internet is largely governed by the dynamics and configuration of the Border Gateway Protocol (BGP). A configuration analysis toolkit enables network operators to discover, analyze and diagnose their BGP configuration, policies and peering relationships. Statistical variance analysis in such a toolkit exploits the recurrence of policies in large networks for analysis. In a large network, policies that have similar functions are examined, e.g. all inbound route maps associated with customer autonomous systems. For n occurrences of similar policy P, it is possible to flag k deviant configurations, and evaluate the probability that the deviant configurations are in error. Analysis and policy visualization of implemented BGP configurations enable service providers to move from checking of low-level configuration to extracting analyzable BGP level policy information across a multitude of BGP routers in order to validate consistency of policies and operator intent across distributed BGP configurations using a flexible, customizable analysis engine

Claims

1. A method for statistical analysis of Border Gateway Protocol configurations comprising the steps of:

obtaining router configuration data;

parsing the router configuration data into low level policy representations;

inputting a first set of criteria;

grouping together similar policies within an autonomous system;

inputting a second set of criteria;

determining if a group of similar policies is valid for statistical analysis;

if there are insufficient similarities the method ends;

if there are sufficient similarities, decomposing the policies into configlets;

if there are non-zero variants, the method ends; and

if there are no non-zero variants, variants with probabilities of error are flagged.

2. A method as set forth in claim 1 wherein said obtaining router configuration data is achieved by inputting router configuration data.

3. A method as set forth in claim 1, wherein said obtaining router configuration data is achieved by discovering router configuration data.

4. A method for statistical analysis of network/router configurations comprising the steps of:

obtaining network/router configuration data;

parsing the configuration data into low level policy representations;

inputting a first set of criteria

grouping together similar policies within an autonomous system;

inputting a second set of criteria;

determining if a group of similar policies is valid for statistical analysis;

if there are insufficient similarities the method ends;

if there are sufficient similarities, decomposing the policies into configlets;

if there are non-zero variants, the method ends; and

if there are no non-zero variants, variants with probabilities of error are flagged.

5. A method as set forth in claim 4 wherein said obtaining network/router configuration data is achieved by inputting router configuration data.

6. A method as set forth in claim 4, wherein said obtaining network/router configuration data is achieved by discovering router configuration data.

7. A system for statistical analysis of Border Gateway Protocol configurations comprising the steps of:

means for obtaining router configuration data;

means for parsing the router configuration data into low level policy representations;

means for inputting a first set of criteria;

means for grouping together similar policies within an autonomous system;

means for inputting a second set of criteria;

means for determining if a group of similar policies is valid for statistical analysis;

means for decomposing the policies into configlets if there are sufficient similarities; and

means for flagging variants with probabilities of error if there are no non-zero variants.