System and method for verifying the validity of a path in a network environment

• US 7,626,948 B1
• Filed: 09/12/2003
• Issued: 12/01/2009
• Est. Priority Date: 09/12/2003
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Cook, David A., White, Russell I., Retana, Alvaro E., Ng, James L.
• Primary Examiner(s): Ton; Dang T
• Assistant Examiner(s): O CONNOR, BRIAN T
• Application Number:
  US10/661,326
• Time in Patent Office: 2,272 Days
• Field of Search: 370400-408, 370/250, 370/244, 370/248, 370/255, 370/411, 370/256, 370/219, 370/220, 370/236, 370/389, 370/473, 709223-224, 709/230, 709/239
• US Class Current: 370/256
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

A method for verifying a validity of a path is provided that includes receiving an advertisement communication at a first autonomous system from a second autonomous system, the advertisement communication including a list of one or more connected autonomous systems. The method also includes identifying whether the first autonomous system claims a connection to the second autonomous system and whether the second autonomous system claims a connection to the first autonomous system such that two-way connectivity is established between the autonomous systems. In response to the establishment of the two-way connectivity, a directed graph is constructed that includes two nodes representing the first and second autonomous systems respectively. An edge may be formed that connects the two nodes.

Claims

1. An apparatus for verifying a validity of a path, comprising:

a network element included in a first autonomous system that;

constructs a directed graph comprising a plurality of nodes and a plurality of edges, a node representing an autonomous system, an edge representing a connection between two autonomous systems, the edges marked tentative;

receives an advertisement communication from each respective autonomous system within an internetwork, the advertisement comprising a list of all autonomous systems connected to the respective autonomous system;

for each advertisement received;

determines from the respective received advertisement whether the respective autonomous system claims a connection to any of the other autonomous systems within the internetwork;

determines from any other received advertisements whether any of the other autonomous systems within the internetwork claim a connection to the respective autonomous system;

for each connection claimed by the respective autonomous system with another autonomous system within the internetwork that is reciprocated by the other autonomous system, establishes that there is two-way connectivity between the two autonomous systems;

if there is two-way connectivity between the two autonomous systems, marks the edge representing the connection between the two autonomous systems as verified in the directed graph; and

if there is no two-way connectivity between the two autonomous systems, removes the edge representing the connection between the two autonomous systems from the directed graph.

2. The apparatus of claim 1, wherein the network element receives an update message from a second autonomous system, the update message including an autonomous system path, and wherein the network element verifies the autonomous system path by referencing the directed graph.

3. The apparatus of claim 1, wherein the network element is a selected one of a group of elements consisting of:

(a) a router;

(b) a switch;

(c) a bridge;

(d) a gateway;

(e) a loadbalancer; and

(f) a processor.

4. The apparatus of claim 1, wherein the network element includes a table operable to store the directed graph and to be referenced in order to verify one or more autonomous system paths that are received by the network element in one or more update messages.

5. The apparatus of claim 1, wherein the advertisement communication is encapsulated in a border gateway protocol (BGP).

6. The apparatus of claim 1, wherein the network element communicates the directed graph to an administrator element that is operable to communicate information included within the directed graph to one or more additional network elements.

7. A method for verifying a validity of a path, comprising:

constructing a directed graph comprising a plurality of nodes and a plurality of edges, a node representing an autonomous system, an edge representing a connection between two autonomous systems, the edges marked tentative;

receiving an advertisement communication at a first autonomous system from each respective autonomous system within an internetwork, the advertisement comprising a list of all autonomous systems connected to the respective autonomous system;

for each advertisement received;

determining from the respective received advertisement communication whether the first autonomous system claims a connection to the respective autonomous system;

determining from the advertisement communication whether the respective autonomous system claims a connection to any of the other autonomous systems within the internetwork, including the first autonomous system;

for each connection claimed by the respective autonomous system with another autonomous systems within the internetwork that is reciprocated by the other autonomous system, establishing that there is two-way connectivity between the two autonomous systems;

if there is two-way connectivity between the two autonomous systems, marking the edge representing the connection between the two autonomous systems as verified; and

if there is no two-way connectivity between the two autonomous systems, removing the edge representing the connection between the two autonomous systems from the directed graph.

8. The method of claim 7, further comprising:

receiving an update message from a second autonomous system, the update message including an autonomous system path, wherein a network element included in the first autonomous system verifies the autonomous system path by referencing the directed graph.

9. The method of claim 7, wherein the first autonomous system includes a network element that includes a table operable to store the directed graph and to be referenced in order to verify one or more autonomous system paths that are received by the network element in one or more update messages.

10. The method of claim 7, wherein the advertisement communication is encapsulated in a border gateway protocol (BGP).

11. The method of claim 7, wherein a network element included in the first autonomous system is operable to communicate the directed graph to an administrator element that is operable to communicate information included within the directed graph to one or more additional network elements.

12. A system for verifying a validity of a path, comprising:

means for constructing a directed graph comprising a plurality of nodes and a plurality of edges, a node representing an autonomous system, an edge representing a connection between two autonomous systems, the edges marked tentative;

means for receiving an advertisement communication at a first autonomous system from each respective autonomous system within an internetwork, the advertisement comprising a list of all autonomous systems connected to the respective autonomous system;

for each advertisement received;

means for determining from the respective received advertisement communication whether the first autonomous system claims a connection to the respective autonomous system;

means for determining from the advertisement communication whether the respective autonomous system claims a connection to any of the other autonomous systems within the internetwork, including the first autonomous system;

means for, for each connection claimed by the respective autonomous system with another autonomous systems within the internetwork that is reciprocated by the other autonomous system, establishing that there is two-way connectivity between the two autonomous systems;

means for, if there is two-way connectivity between the two autonomous systems, marking the edge representing the connection between the two autonomous systems as verified; and

means for, if there is no two-way connectivity between the two autonomous systems, removing the edge representing the connection between the two autonomous systems from the directed graph.

13. The system of claim 12, further comprising:

means for receiving an update message from a second autonomous system, the update message including an autonomous system path, wherein a network element verifies the autonomous system path by referencing the directed graph.

14. The system of claim 12, wherein the first autonomous system includes a network element that includes a table operable to store the directed graph and to be referenced in order to verify one or more autonomous system paths that are received by the network element in one or more update messages.

15. The system of claim 12, wherein the advertisement communication is encapsulated in a border gateway protocol (BGP).

16. The system of claim 12, wherein a network element included in the first autonomous system is operable to communicate the directed graph to an administrator element that is operable to communicate information included within the directed graph to one or more additional network elements.

17. Software embodied in a computer readable medium, the software comprising computer code such that when executed is operable to:

construct a directed graph comprising a plurality of nodes and a plurality of edges, a node representing an autonomous system, an edge representing a connection between two autonomous systems, the edges marked tentative;

receive an advertisement communication at a first autonomous system from each respective autonomous system within an internetwork, the advertisement comprising a list of all autonomous systems connected to the respective autonomous system;

for each advertisement received;

determine from the respective received advertisement communication whether the first autonomous system claims a connection to the respective autonomous system;

determine from the advertisement communication whether the respective autonomous system claims a connection to any of the other autonomous systems within the internetwork, including the first autonomous system;

for each connection claimed by the respective autonomous system with another autonomous systems within the internetwork that is reciprocated by the other autonomous system, establish that there is two-way connectivity between the two autonomous systems;

if there is two-way connectivity between the two autonomous systems, mark the edge representing the connection between the two autonomous systems as verified; and

if there is no two-way connectivity between the two autonomous systems, remove the edge representing the connection between the two autonomous systems from the directed graph.

18. The medium of claim 17, wherein the code is further operable to:

receive an update message from a second autonomous system, the update message including an autonomous system path, wherein a network element verifies the autonomous system path by referencing the directed graph.

19. The medium of claim 17, wherein the first autonomous system includes a network element that includes a table operable to store the directed graph and to be referenced in order to verify one or more autonomous system paths that are received by the network element in one or more update messages.

20. The medium of claim 17, wherein the advertisement communication is encapsulated in a border gateway protocol (BGP).

21. The medium of claim 17, wherein a network element included in the first autonomous system is operable to communicate the directed graph to an administrator element that is operable to communicate information included within the directed graph to one or more additional network elements.