System and methods for network reachability detection

• US 7,990,888 B2
• Filed: 03/04/2005
• Issued: 08/02/2011
• Est. Priority Date: 03/04/2005
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Sayeed, Azhar Mohammed, Piecuch, Michael T., Vasseur, Jean-Phillipe, Guichard, James N., Nadeau, Thomas D., Swallow, George L.
• Primary Examiner(s): Shah; Chirag G
• Assistant Examiner(s): Kang; Suk Jin
• Application Number:
  US11/072,082
• Publication Number:
  US 20060198321A1
• Time in Patent Office: 2,342 Days
• Field of Search: None
• US Class Current: 370/254
• CPC Class Codes: H04L 43/50 Testing arrangements
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/36 Backward learning
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]

Abstract

A mechanism for ASBRs to identify the originating node, or router, in an LSP conversant autonomous system (AS), such as an MPLS VPN environment, maintains the identity of the originating node and successive nodes in subsequent autonomous systems along the path to the node to be pinged. The identity of the transporting nodes is stored in a stack or other object associated with the ping request (ping), such that the pinged node may employ the stored identity as a set of return path routing information. Successive ASBRs store their identity on the stack, in an ordered manner, along the path to the destination. Upon reaching the destination (ping) node, the destination node employs the identity of the first node on the stack to send the acknowledgment, or ping response. Each successive ASBR, therefore, pops (retrieves) the next node identity from the stack and redirects (sends) the ping response to the retrieved node.

Claims

1. A method of assessing a state of a remote node via a label switched path, the method comprising:

receiving a response request message from an originator node at an autonomous system border router, the autonomous system border router included in a plurality of autonomous system border routers on the label switched path between the originator node and the remote node;

transmitting the response request message to each successive one of the autonomous system border routers as the response request message traverses the autonomous system border routers on the label switched path to the remote node;

accumulating, in a nondestructive manner at each successive one of the autonomous system border routers, an entry indicative of an identity of each successive one of the autonomous system border routers traversed on the label switched path to the remote node, wherein accumulating the entry indicative of the identity of each successive one of the autonomous system border routers further comprises building a stack of accumulated entries indicative of identities of the autonomous system border routers in the response request message;

traversing the label switched path back to the originator node based on the stack of accumulated entries included in the acknowledgement response message; and

forwarding messages at each respective one of the autonomous system border routers according to forwarding rules, the forwarding rules directing the respective one of the autonomous system border routers to;

transmit the response request message, if the response request message is received, to a next route toward the remote node;

redirect the acknowledgment response message, if the acknowledgment response message is received, to a next address on the stack of accumulated entries; and

identify, if the response request message cannot reach the remote node, an autonomous system or the respective one of the autonomous system border routers encountering a condition of the response request message being unable to reach the remote node.

2. The method of claim 1 further comprising traversing a plurality of subnetworks defined by the autonomous system border routers indicative of ingress points to a respective one of the subnetworks, each one of the subnetworks being an autonomous system having an independent routing policy.

3. The method of claim 2 wherein the label switched path is defined through each of the subnetworks via a predetermined label switched path label, the predetermined label switched path label operable to be recognized by the autonomous system border routers within the subnetworks.

4. The method of claim 3 wherein the nondestructive manner avoids overwriting successive accumulated entries such that retrieval of the accumulated entries is performable in a reverse order from which the accumulated entries were written.

5. The method of claim 1 wherein building the stack of accumulated entries further comprises storing the accumulated entries as a stack of return addresses, the stack including a first address and successive addresses indicative of an ordered set of border nodes traversed by the response request message.

6. The method of claim 5 wherein the accumulated entries are written to the stack in an ordered manner indicative of the label switched path, further comprising:

receiving, at the remote node, the response request message;

building the acknowledgment response message by including the stack of accumulated entries in the acknowledgment response message; and

transmitting the acknowledgment response message to a first return address on the stack.

7. The method of claim 6 further comprising forwarding the acknowledgment response message to the originator node, forwarding further comprising:

retrieving the first return address on the stack, such that a second return address placed on the stack previous to the first return address is a current first return address on the stack;

transmitting the acknowledgment response message to the current first return address; and

repeating the retrieval and transmitting for each successive address on the return address stack until the originator node receives the acknowledgment response message.

8. The method of claim 6 further comprising, upon traversing an autonomous system, transmitting at least one of the response request message and the acknowledgment response message, erasing a routing history indicative of the label switched path;

and

selectively, if an error condition is encountered, sending the response request message to a last address on the stack.

9. The method of claim 8 wherein multiple paths exist between a first subnetwork and a second subnetwork, and the accumulated addresses are indicative of a path of the response request message such that the same path is traversed for the acknowledgment response message.

10. The method of claim 9 wherein successive return path routing information are stored by the autonomous system border routers, the autonomous system border routers retaining an identity of the previous autonomous system border router indicative of a last hop in a previous autonomous system traversed by the response request message.

11. The method of claim 1 wherein the forwarding rules directing the respective one of the autonomous system border routers further comprises the forwarding rules directing the respective one of the autonomous system border routers to transmit the response request message by setting a time-to-live (TTL) value of the response request message to a value of 1.

12. A data communications device for performing ping operations between autonomous system border routers (ASBRs) using label switched path (LSP) routing comprising:

a network interface operable to identify a remote node from which an acknowledging response is requested, the remote node corresponding to a label switched path, wherein the label switched path includes the ASBRs;

a return address stack operable to store an entry indicative of an identity of an originator node of a response request message;

a routing processor operable to forward messages in accordance with forwarding rules, wherein the forwarding rules direct the routing processor to;

to transmit the response request message, if the response request message is received, from any one of the ASBRs to a next respective one of the ASBRs on the label switched path toward the remote node;

accumulate, in a nondestructive manner at each successive one of the ASBRs, a stack of accumulated entries indicative of an identity of each successive one of the ASBRs traversed on the label switched path to the remote node by the response request message, wherein the stack of accumulated entries is for inclusion in an acknowledgement response message;

forward the acknowledgement response message, if the acknowledgement response message is received, toward the originator node based on the stack of accumulated entries; and

identify, if the response request message cannot reach the remote node, an autonomous system or one of the ASBRs encountering a condition of the response request message being unable to reach the remote node.

13. The data communications device of claim 12, wherein the network interface couples a plurality of subnetworks defined by ASBRs indicative of ingress points to the respective subnetwork, each of the subnetworks being a corresponding autonomous system having an independent routing policy.

14. The data communications device of claim 13 wherein the label switched path is defined through each of the subnetworks via a predetermined label, the predetermined label operable to be recognized by the ASBRs within a respective subnetwork.

15. The data communications device of claim 14 wherein the return address stack is operable to accumulate entries in an non destructive manner which avoids overwriting successive accumulated entries such that retrieval of the entries is performable in a reverse order from which they were written.

16. The data communications device of claim 12 wherein the router processor is operable to store the accumulated entries as a stack of return address, the stack having a first address and successive addresses indicative of an ordered set of border nodes traversed by the response request message.

17. The data communications device of claim 16 wherein the accumulated entries are written to the stack of return addresses in an ordered manner indicative of the label switched path, the remote node further operable to:

receive, at the remote node, the response request message;

build the acknowledgment response message to include the stack of return addresses; and

transmit the acknowledgment response message to the first return address on the stack of return address.

18. The data communications device of claim 17 wherein each receiver of the acknowledgement response further comprises forwarding rules, wherein the forwarding rules, in order to forward the acknowledgment response message to the originator, are further operable to:

retrieve the first address on the stack of return address, such that the return address placed on the stack previous to the first address is the current first return address on the stack of return address;

transmit the acknowledgment response message to the retrieved first address; and

repeat the retrieval and transmission at each receiver until the originator receives the acknowledgement response message.

19. The data communications device of claim 16 wherein the stack of accumulated entries is operable to preserve an original IP source address of the response request message across autonomous system (AS) boundaries, and further operable to avoid modification of existing structures of an LSP ping routing history.

20. The data communications device of claim 19 wherein the routing processor is further operable to maintain a list of the ASBRs that the acknowledgement response message has passed through such that the acknowledgment response message delivers to the originator node the path of the ASBRs that the response request message reached.

21. The data communications device of claim 16 wherein the routing processor is further operable to set, at each one of the ASBRs traversed by the response request message, a router alert label, operable to trigger an interrupt response and examination by at least one successive one of the ASBRs, such that label switch routing avoids ignoring the response request message.

22. The data communications device of claim 21 wherein the routing processor is further operable to append additional routing identifiers corresponding to the return addresses operable to identify an appropriate routing table for routing the acknowledgement response message.

23. A computer program product having a non-transitory computer readable medium operable to store computer program logic embodied in computer program code encoded thereon for assessing the state of a remote node via a labeled switch path comprising:

computer code for receiving a response request message from an originator node at an autonomous system border router, the autonomous system border router included in a plurality of autonomous system border routers on the label switched path between the originator node and the remote node;

computer code for transmitting the response request message to each successive one of the autonomous system border routers as the response request message traverses the autonomous system border routers on the label switched path to the remote node;

computer code for accumulating, in a nondestructive manner at each successive one of the autonomous system border routers, an entry indicative of an identity of each successive one of the autonomous system border routers traversed on the label switched path to the remote node, wherein accumulating the entry indicative of the identity of each successive one of the autonomous system border routers further comprises building a stack of accumulated entries indicative of identities of the autonomous system border routers in the response request message;

computer code for traversing the label switched path back to the originator node based on the stack of accumulated entries included in the acknowledgement response message; and

computer code for forwarding messages at each respective one of the autonomous system border routers according to forwarding rules, the forwarding rules directing the respective one of the autonomous system border routers to;

transmit the response request message, if the response request message is received, to a next route toward the remote node;

redirect the acknowledgment response message, if the acknowledgment response message is received, to a next address on the stack of accumulated entries; and

identify, if the response request message cannot reach the remote node, an autonomous system or the respective one of the autonomous system border routers encountering a condition of the response request message being unable to reach the remote node.

24. A data communications device for performing ping operations between autonomous system border routers (ASBRs) using label switched path (LSP) routing comprising:

means for identifying a remote node from which an acknowledging response is requested, the remote node corresponding to a label switch path, the label switched path including a sequence of border routers;

means for storing an entry indicative of an identity of an originator node of an acknowledging response request in a response request message;

means for receiving, from the originator node, the response request message at a border router included on the label switched path to the remote node;

means for transmitting the response request message to successive border routers on the label switched path to the remote node, wherein each one of the successive border routers forwards the response request message to a next one of the successive border routers;

means for accumulating, in a nondestructive manner at each successive border router, an entry indicative of an identity of each one of the successive border routers on the label switched path to the remote node, the accumulated entries indicative of the successive border routers stored on a stack;

means for coupling to a plurality of subnetworks defined by border routers indicative of ingress points to the respective subnetwork, each of the subnetworks being an autonomous system having an independent routing policy;

means for forwarding to the plurality of subnetworks, the forwarding occurring according to forwarding rules, the forwarding rules further including rules to;

transmit, if an acknowledgment request is received, to a next route toward the remote node defining a ping destination;

redirect toward the originator node, if an acknowledgment response is received, to the next address on the stack of the accumulated entries, the acknowledgement response; and

identify, if the remote node cannot be reached, an autonomous system encountering a condition of the response request message being unable to reach the remote node.