Exploratory linktrace operations in a computer network

Patent metadata

Field	Value
Publication number	US-10812367-B2
Application number	US-201816127078-A
Country	US
Kind code	B2
Filing date	Sep 10, 2018
Priority date	Jan 21, 2009
Publication date	Oct 20, 2020
Grant date	Oct 20, 2020

Abstract

In one embodiment, an exploratory linktrace is initiated from an initiating network device with an exploratory linktrace message (ELM) having a target address. Each network device receiving the ELM may then propagate the ELM on a plurality of its ports to a plurality of downstream network devices based on the target address. In addition, each receiving network device returns an exploratory linktrace reply (ELR) for each of the plurality of ports, where each ELR is returned according to one or more mechanisms to mitigate stormed replies to the initiating network device.

First claim

What is claimed is:

1. A non-transitory computer-readable storage media having stored therein instructions which, when executed by a processor, cause the processor to perform operations comprising:
receiving, at a network device, a linktrace protocol message having a unicast target network address;
determining that the unicast target network address is unknown;
converting the linktrace protocol message into an exploratory linktrace message (ELM), the ELM instructing a plurality of downstream network devices to propagate the ELM to a second plurality of downstream network devices;
flooding the ELM on a plurality of ports of the network device to the plurality of downstream network devices;
obtaining an exploratory linktrace reply (ELR) for each of the plurality of ports; and
sending a plurality of ELRs to an initiating network device.

2. The media of claim 1 , wherein the sending comprises:
concatenating each of the ELRs into one or more concatenated ELRs; and
returning the one or more concatenated ELRs to the initiating network device.

3. The media of claim 2 , wherein the initiating network device provided the linktrace protocol message received during the receiving.

4. The media of claim 1 , wherein the ELM comprises a maximum time that the plurality of downstream network devices are expected to wait before responding to the ELM.

5. The media of claim 1 , the operations further comprising generating a network topology based on the obtained ELRs.

6. The media of claim 1 , wherein the sending occurs via periodic intervals in which a predetermined maximum number of ELMs can be sent during each interval.

7. A method comprising:
receiving, at a network device, a linktrace protocol message having a unicast target network address;
determining that the unicast target network address is unknown;
converting the linktrace protocol message into an exploratory linktrace message (ELM), the ELM instructing a plurality of downstream network devices to propagate the ELM to a second plurality of downstream network devices;
flooding the ELM on a plurality of ports of the network device to the plurality of downstream network devices;
obtaining an exploratory linktrace reply (ELR) for each of the plurality of ports; and
sending a plurality of ELRs to an initiating network device.

8. The method of claim 7 , wherein the sending comprises:
concatenating each of the ELRs into one or more concatenated ELRs; and
returning the one or more concatenated ELRs to the initiating network device.

9. The method of claim 8 , wherein the initiating network device provided the linktrace protocol message received during the receiving.

10. The method of claim 8 , wherein the sending occurs via periodic intervals in which a predetermined maximum number of ELMs can be sent during each interval.

11. The method of claim 7 , wherein the ELM comprises a maximum time that the plurality of downstream network devices are expected to wait before responding to the ELM.

12. The method of claim 7 , further comprising generating a network topology based on the obtained ELRs.

13. A system comprising:
a memory storing instructions;
a processor programmed to execute the instructions to perform operations comprising:
receiving, at a network device, a linktrace protocol message having a unicast target network address;
determining that the unicast target network address is unknown;
converting the linktrace protocol message into an exploratory linktrace message (ELM), the ELM instructing a plurality of downstream network devices to propagate the ELM to a second plurality of downstream network devices;
flooding the ELM on a plurality of ports of the network device to the plurality of downstream network devices;
obtaining an exploratory linktrace reply (ELR) for each of the plurality of ports; and
sending a plurality of ELRs to an initiating network device.

14. The system of claim 13 , wherein the sending comprises:
concatenating each of the ELRs into one or more concatenated ELRs; and
returning the one or more concatenated ELRs to the initiating network device.

15. The system of claim 14 , wherein the initiating network device provided the linktrace protocol message received during the receiving.

16. The system of claim 13 , wherein the ELM comprises a maximum time that the plurality of downstream network devices are expected to wait before responding to the ELM.

17. The system of claim 13 , the operations further comprising generating a network topology based on the obtained ELRs.

Assignees

• Cisco Tech Inc

Inventors

• Finn Norman W
• Salam Samer
• Monaghan John
• Mcdade Iain
• Ball David Alexander
• Chatterjee Simon

Classifications

• H04L41/12

  Discovery or management of network topologies · CPC title

• H04L45/02 Primary

  Topology update or discovery · CPC title

• H04L12/462 Primary

  LAN interconnection over a bridge based backbone · CPC title

• H04L45/26

  Route discovery packet · CPC title

• H04L43/10

  Active monitoring, e.g. heartbeat, ping or trace-route · CPC title