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

• US 8,214,876 B2
• Filed: 11/30/2006
• Issued: 07/03/2012
• Est. Priority Date: 04/19/2006
• Status: Active Grant

• Current Assignee: Perspecta Labs Inc. (Perspecta, Inc.)
• Original Assignee: Telcordia Technologies Incorporated (Telefonaktiebolaget LM Ericsson)
• Inventors: Vaidyanathan, Ravichander
• Primary Examiner(s): MOORTHY, ARAVIND K
• Application Number:
  US11/606,687
• Publication Number:
  US 20070250902A1
• Time in Patent Office: 2,042 Days
• Field of Search: 726/1, 726/4, 726 11- 13, 726/23, 713/153, 713/161, 713/166, 713/168, 713/188, 713/189, 709/224, 709/238
• 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 from multiple network elements forming an autonomous system;

parsing the router configuration data into low level policy representations;

inputting a first set of criteria;

grouping together a plurality of similar policies within an autonomous system;

inputting a second set of criteria;

detecting anomalies in network configurations by determining if a group of similar policies is valid for statistical variance analysis;

if there are insufficient similarities in the statistical variance analysis the method ends;

if there are sufficient similarities in the statistical variance analysis, decomposing the policies into configlets;

if there are non-zero variants in the statistical variance analysis, the method ends; and

if there are no non-zero variants in the statistical variance analysis, 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 from multiple network elements forming an autonomous system;

parsing the configuration data into low level policy representations;

inputting a first set of criteria;

grouping together a plurality of similar policies within an autonomous system;

inputting a second set of criteria;

detecting anomalies in network configurations by determining if a group of similar policies is valid for statistical variance analysis;

if there are insufficient similarities in the statistical variance analysis the method ends;

if there are sufficient similarities in the statistical variance analysis, decomposing the policies into configlets;

if there are non-zero variants in the statistical variance analysis, the method ends; and

if there are no non-zero variants in the statistical variance analysis, 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.