System and methods for network path detection

• US 20060171331A1
• Filed: 02/01/2005
• Published: 08/03/2006
• Est. Priority Date: 02/01/2005
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Ward, David D., Guichard, James N., Vasseur, Jean-Philippe, Previdi, Stefano
• Granted Patent: US 7,433,320 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04L 43/0811 by checking connectivity
• CPC Class Codes: H04L 45/026 Details of "hello" or keep-alive messages
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 63/0272 Virtual private networks

Abstract

Customer edge (CE) to CE device verification checks initiate routes from available CEs as a set of path verification messages, destined for remote CE routes serving a remote VPN. An extended community attribute, included among the attributes of the path verification message, stores the identity of the originating CE router. The path verification message propagates across the network, and transports the identity of the originating CE router because the originator identity is not overwritten by successive routing. Upon receipt by the remote CE, the originator is determinable from the extended community attribute. A further reachability field is also included in the extended community attribute and indicates whether per CE or per prefix is appropriate for the particular route in question. In this manner, CE-CE connectivity checks identify CEs which are reachable from other CEs. Accordingly, such a mechanism allows for route reachability aggregation on a per-CE or per-prefix reachability basis.

Claims

1. A method of identifying network paths comprising:

building a path verification message operable for transmission from an originator to a destination;

storing the identity of the originator in the path verification message, the message being stored in a nonvolatile manner undisturbed by successive routing operations;

transmitting the path verification message to the destination via at least one intermediate switching device;

receiving, if the transmitting was successful, the path verification message at the destination; and

recovering, from the received path verification message, the identity of the transmitting originator by recovering the stored identity.

2. The method of claim 1 further comprising designating a path between the destination and the originator as a verified path based on the recovered identity of the originator.

3. The method of claim 2 further comprising identifying, if the transmitting to the destination was not successful, the originator as an invalid routing path to the destination.

4. The method of claim 3 wherein the originator is a local customer edge (CE) router and the destination is a remote CE router, the originator and destination interconnected by a path including at least one provider edge (PE) router, the PE router coupled to a plurality of PE routers collectively defining a core network, the core network operable to employ the path verification message for transmitting the identity of the originator to the destination.

5. The method of claim 4 wherein the path verification message further comprises attributes operable to transport control information between the switching devices, the attributes including an extended community field indicative of the originator of the path verification message.

6. The method of claim 5 wherein the path verification message further includes a reachability flag, the reachability flag indicative of a prefix based or CE based reachability check.

7. The method of claim 1 wherein the path verification messages include attributes according to a predetermined protocol, storing further comprising:

identifying a preserved attribute in the path verification message, the preserved attribute operable to propagate to each router during the transmission;

storing an address of the originator as the identity in the preserved attribute;

storing a reachability indicator indicative of prefix or path routes in the preserved attribute; and

identifying the origination router of the routing message.

8. The method of claim 7 wherein the devices are edge routers, including customer edge and provider edge, wherein the customer edge routers identify an ingress point to an autonomous system demarcated by a customer VPN boundary, and the provider edge routers identify an ingress point to a core network demarcating internet service providers.

9. The method of claim 8 wherein the path verification message is transported according to one of an intranetwork-border protocol and an internetwork-border protocol, and:

assigning, if the internetwork-border protocol is employed, a reachability indicator to a loopback self-route, and propagating the self-route to other switching devices via the intranetwork- border protocol; and

assigning, if the intranetwork-border protocol is employed, the originator indicator to successive path verification messages to other routing devices.

10. The method of claim 9 wherein the preserved attribute further comprises:

a 4 octet IP address field operative to identify the originator; and

1 octet reachability flag field indicative of whether a path or prefix reachability check is performed.

11. A method for identifying reliable routes between edge-node switching devices in a computer network comprising:

identifying a customer edge (CE) node indicative of an ingress point to a subnetwork;

identifying at least one of an internetwork routing protocol and an intranetwork routing protocol employed between the subnetwork and a service provider edge (PE) node indicative of an ingress point to a core network, the core network operable to interconnect a plurality of other PE nodes corresponding to ingress points to alternate subnetworks;

establishing, if the internetwork protocol is employed to the PE node, a path verification message including a self-route indicative of a loopback interface route to the CE node, further comprising;

populating an extended community attribute in the path verification message indicative of the identity of the CE node;

advertising the path verification message to the PE, advertising operable to enable the PE to further advertise the path verification message to other CEs in the network;

determining if the other CEs receiving the path verification message are to employ a per CE reachability check or a per-prefix reachability check; and

setting a reachability indicator in the path verification message accordingly based on the determining, the receiving PE responsive to the reachability indicator such that;

if the reachability flag is set to a per prefix check, associating a prefix of the path verification message to the identity of the CE node based on the extended community attribute, each receiving CE operable to associate a prefix indicative of the received route with the originating CE; and

if the reachability flag is set to a per-CE check, associating recipient CEs of the path verification message with the identity of the CE node based on the extended community attribute;

establishing, if the internetwork protocol is employed between to the PE, a path verification message having the extended community attribute, establishing further comprising;

populating the extended community attribute with the identity of the CE node, the PE nodes responsive to the extended community attribute for receiving the extended community attribute from the CE and advertising it to successive nodes in the network.

12. A data communications device comprising:

a path verification processor operable to build a path verification message operable for transmission from an originator to a destination;

at least one attribute in the path verification message adapted to store the identity of the originator in the path verification message, the message being stored in a nonvolatile manner undisturbed by successive routing operations; and

a network interface operable to transmit the path verification message to the destination via at least one intermediate switching device, the path verification message operable to be received, if the transmitting was successful, at the destination, the destination operable to recover, from the received path verification message, the identity of the transmitting originator by recovering the stored identity.

13. The data communications of claim 12 wherein the destination is operable to designate a path between the destination and the originator as a verified path based on the recovered identity of the originator.

14. The data communications of claim 13 further comprising an alternate recipient node, the alternate recipient node operable to identify, if the transmitting to the destination was not successful, the originator as an invalid routing path to the destination.

15. The data communications of claim 14 wherein the originator is a local customer edge (CE) router and the destination is a remote CE router, the originator and destination interconnected by a path including at least one provider edge (PE) router, the PE router coupled to a plurality of PE routers collectively defining a core network, the core network operable to employ the path verification message for transmitting the identity of the originator to the destination.

16. The data communications of claim 15 wherein the path verification message further comprises attributes operable to transport control information between the switching devices, the attributes including an extended community field indicative of the originator of the path verification message.

17. The data communications of claim 16 wherein the path verification message further includes a reachability flag, the reachability flag indicative of a prefix based or CE based reachability check.

18. The data communications of claim 12 wherein the path verification messages include attributes according to a predetermined protocol, storing further comprising:

identifying a preserved attribute in the path verification message, the preserved attribute operable to propagate to each router during the transmission;

storing an address of the originator as the identity in the preserved attribute;

storing a reachability indicator indicative of prefix or path routes in the preserved attribute; and

identifying the origination router of the routing message.

19. The data communications of claim 18 wherein the devices are edge routers, including customer edge and provider edge, wherein the customer edge routers identify an ingress point to an autonomous system demarcated by a customer VPN boundary, and the provider edge routers identify an ingress point to a core network demarcating internet service providers.

20. A computer program product having a computer readable medium operable to store computer program logic embodied in computer program code encoded thereon for identifying network paths comprising:

computer program code for building a path verification message operable for transmission from an originator to a destination;

computer program code for storing the identity of the originator in the path verification message, the message being stored in a nonvolatile manner undisturbed by successive routing operations;

computer program code for transmitting the path verification message to the destination via at least one intermediate switching device, the path verification message further including a reachability flag, the reachability flag indicative of a prefix based or CE based reachability check;

computer program code for receiving, if the transmitting was successful, the path verification message at the destination;

computer program code for recovering, from the received path verification message, the identity of the transmitting originator by recovering the stored identity;

computer program code for transporting the path verification message is according to one of an intranetwork-border protocol and an internetwork-border protocol;

computer program code for assigning, if the internetwork-border protocol is employed, a reachability indicator to a loopback self-route, and propagating the self-route to other switching devices via the intranetwork- border protocol; and

computer program code for assigning, if the intranetwork-border protocol is employed, the originator indicator to successive path verification messages to other routing devices.