End-to end route tracing over a named-data network

• US 9,374,304 B2
• Filed: 01/24/2014
• Issued: 06/21/2016
• Est. Priority Date: 01/24/2014
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Solis, Ignacio, Scott, Glenn C., Plass, Michael F., Crabtree, Ian B.
• Primary Examiner(s): Yao, Kwang B
• Assistant Examiner(s): CASTANEYRA, RICARDO H
• Application Number:
  US14/163,669
• Publication Number:
  US 20150215206A1
• Time in Patent Office: 879 Days
• Field of Search: 370/252, 370/351
• US Class Current: 1/1
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/50 Testing arrangements
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context

Abstract

A route-tracing application can measure the performance of a path in a named-data network using trace agents deployed across various network nodes. During operation, a network node can process a route-tracing Interest by performing a lookup operation in a forwarding information base (FIB) using the Interest'"'"'s name, in which a respective FIB entry may map the name to a forwarding rule. If the FIB does not include an entry for the Interest'"'"'s route-tracing name, a trace agent at the network node determines one or more outbound interfaces for the route-tracing operation based on the Interest'"'"'s name, and creates new route-tracing FIB entries that each maps the Interest'"'"'s name to a forwarding rule for the determined interfaces. The network node returns a Content Object that satisfies the Interest, in which the Content Object includes the names of the new FIB entries, as well as performance information for the path.

Claims

1. A computer-executable method for measuring the performance of a path in a named-data network, the method comprising:

receiving, at a network node, a first Interest generated by a source node that includes a name that corresponds to a route-tracing operation;

determining, by the network node, that a received Interest includes a name that corresponds to a route-tracing operation;

in response to determining that the first Interest includes the name matching the route-tracing operation, determining one or more outbound interfaces for the route-tracing operation based on the first Interest'"'"'s name;

creating one or more new forwarding information base (FIB) entries for the outbound interfaces, wherein a respective FIB entry maps the first Interest'"'"'s name to a forwarding rule that includes a corresponding outbound interface;

generating a Content Object that includes at least the names of the new FIB entries and trace information that facilitates path performance measurement;

returning, to the source node, the Content Object;

receiving, at the network node, a second Interest generated by the source node that includes at least one FIB entry name matching a FIB entry name previously returned to the source node from the network node; and

performing a lookup in the FIB table with the FIB entry name in the second Interest to determine a next node for forwarding the second Interest; and

forwarding the second interest to the next node.

2. The method of claim 1, further comprising determining trace information for the network node, wherein the trace information includes one or more of:

a node identifier;

a timestamp;

a total path transit time;

a transit time to each neighbor;

a name and number of content objects cached under a traced prefix;

average reply times for Interests issued by a node under a namespace;

a set of links to neighboring nodes;

an amount of free space or churn;

congestion information;

power status information;

location information; and

a number of pending Interests for the namespace.

3. The method of claim 1, further comprising:

responsive to determining that the Interest'"'"'s name also corresponds to a namespace that is provided by the network node, generating a second Content Object to include at least trace information associated with a second route-tracing operation.

4. The method of claim 1, wherein determining that the Interest'"'"'s name is associated with the route-tracing operation involves determining that a component of the Interest'"'"'s name matches a predetermined name for the route-tracing operation or application.

5. The method of claim 1, wherein creating the new FIB entry involves:

determining an interface identifier for the outbound interface;

generating a trace name that includes the Interest'"'"'s name and the interface identifier; and

creating the FIB entry to map the trace name to the forwarding rule that includes the outbound interface.

6. The method of claim 1, further comprising removing a FIB entry in response to one or more of:

determining that a corresponding timeout period has been reached;

detecting that a corresponding route-tracing operation has completed; and

receiving, from a trace program, a message that includes instructions to remove the FIB entry.

7. The method of claim 1, wherein the name includes a set of one or more name components, wherein each name component indicates one or more of:

a traceroute application for processing the Interest;

a name for a piece of data for which to perform the route-tracing operation;

an outgoing interface for one or more nodes along a path; and

a forwarding rule to enter into the FIB.

8. The method of claim 1, further comprising determining whether the Interest'"'"'s name is associated with a namespace provided by the network node, which involves performing a lookup operation in the FIB using the Interest'"'"'s name, wherein a respective FIB entry maps a name to a forwarding rule.

9. A non-transitory computer-readable storage medium storing instructions which when executed by a computer cause the computer to perform a method for measuring the performance of a path in a named-data network, the method comprising:

receiving, at a network node, a first Interest generated by a source node that includes a name that corresponds to a route-tracing operation;

determining that a received Interest includes a name that corresponds to a route-tracing operation;

in response to determining that the first interest includes the name matching the route-tracing operation, determining one or more outbound interfaces for the route-tracing operation based on the first Interest'"'"'s name;

creating one or more new forwarding information base (FIB) entries for the outbound interfaces, wherein a respective FIB entry maps the first Interest'"'"'s name to a forwarding rule that includes a corresponding outbound interface;

generating a Content Object that includes at least the names of the new FIB entries and trace information that facilitates path performance measurement;

returning, to the source node, the Content Object;

receiving, at the network node, a second Interest generated by the e source node that includes at least one FIB entry name matching a FIB entry name previously returned to the source node from the network node; and

performing a lookup in the FIB table with the FIB entry name in the second Interest to determine a next node for forwarding the second Interest; and

forwarding the second Interest to the next node.

10. The storage medium of claim 9, wherein the method further comprises determining trace information for the network node, wherein the trace information includes one or more of:

a node identifier;

a timestamp;

a total path transit time;

a transit time to each neighbor;

a name and number of content objects cached under a traced prefix;

average reply times for Interests issued by a node under a namespace;

a set of links to neighboring nodes;

an amount of free space or churn;

congestion information;

power status information;

location information; and

a number of pending Interests for the namespace.

11. The storage medium of claim 9, wherein the method further comprises:

responsive to determining that the Interest'"'"'s name also corresponds to a namespace that is provided by the network node, generating a second Content Object to include at least trace information associated with a second route-tracing operation.

12. The storage medium of claim 9, wherein determining that the Interest'"'"'s name is associated with the route-tracing operation involves determining that a component of the Interest'"'"'s name matches a predetermined name for the route-tracing operation or application.

13. The storage medium of claim 9, wherein creating the new FIB entry involves:

determining an interface identifier for the outbound interface;

generating a trace name that includes the Interest'"'"'s name and the interface identifier; and

creating the FIB entry to map the trace name to the forwarding rule that includes the outbound interface.

14. The storage medium of claim 9, wherein the method further comprises removing a FIB entry in response to one or more of:

determining that a corresponding timeout period has been reached;

detecting that a corresponding route-tracing operation has completed; and

receiving, from a trace program, a message that includes instructions to remove the FIB entry.

15. The storage medium of claim 9, wherein the name includes a set of one or more name components, wherein each name component indicates one or more of:

a traceroute application for processing the Interest;

a name for a piece of data for which to perform the route-tracing operation;

an outgoing interface for one or more nodes along a path; and

a forwarding rule to enter into the FIB.

16. The storage medium of claim 9, wherein the method further comprises determining whether the Interest'"'"'s name is associated with a namespace provided by the network node, which involves performing a lookup operation in the FIB using the Interest'"'"'s name, wherein a respective FIB entry maps a name to a forwarding rule.

17. A computing system for measuring the performance of a path in a named-data network, the system comprising:

one or more processors;

a memory; and

a non-transitory computer-readable medium coupled to the one or more processors storing instructions stored that, when executed by the one or more processors, cause the computing system to perform a method comprising;

receiving, at a network node, a first Interest generated by a source node that includes a name that corresponds to a route-tracing operation;

determining that a received Interest includes a name that corresponds to a route-tracing operation;

in response to determining that the first Interest includes the name matching the route-tracing operation, determining one or more outbound interfaces for the route-tracing operation based on the first Interest'"'"'s name;

creating one or more new forwarding information base (FIB) entries for the outbound interfaces, wherein a respective FIB entry maps the first Interest'"'"'s name to a forwarding rule that includes a corresponding outbound interface;

generating a Content Object that includes at least the names of the new FIB entries and trace information that facilitates path performance measurement;

returning, to the source node. the Content Object;

receiving, at the network node, a second Interest generated by the source node that includes at least one FIB entry name matching a FIB entry name previously returned to the source node from the network node; and

performing a lookup in the FIB table with the FIB entry name in the second Interest to determine a next node for forwarding the second Interest; and

forwarding the second Interest to the next node.

18. The computing system of claim 17, wherein the method further comprises:

determining trace information for the network node, wherein the trace information includes one or more of;

a node identifier;

a timestamp;

a total path transit time;

a transit time to each neighbor;

a name and number of content objects cached under a traced prefix;

average reply times for Interests issued by a node under a namespace;

a set of links to neighboring nodes;

an amount of free space or churn;

congestion information;

power status information;

location information; and

a number of pending Interests for the namespace.

19. The computing system of claim 17, wherein the method further comprises:

responsive to determining that the Interest'"'"'s name also corresponds to a namespace that is provided by the network node, generating a second Content Object to include at least trace information associated with a second route-tracing operation.

20. The computing system of claim 17, wherein determining that the Interest'"'"'s name is associated with the route-tracing operation involves determining that a component of the Interest'"'"'s name matches a predetermined name for the route-tracing operation or application.