US-20260128977-A1 - METHODS, SYSTEMS, AND COMPUTER READABLE MEDIA DISCOVERING EQUAL COST MULTI-PATH (ECMP) ROUTING PATHS IN NETWORK TOPOLOGY USING ENHANCED TRACEROUTE

US20260128977A1US 20260128977 A1US20260128977 A1US 20260128977A1US-20260128977-A1

Abstract

A method for discovering network paths using an enhanced traceroute procedure includes generating probe request packets addressed to a destination node and each being associated with an entropy value that is unique to a packet flow and a signature value that is unique to the probe request packet within the packet flow. The TTL values in the probe request packets for the packet flow are set to incrementally increasing values. The probe request packets are transmitted to a next-hop, where multiple probe request packets with different TTL are outstanding for a given flow. The method further includes receiving probe response packets that each encapsulate one of the probe request packets. The method further includes reading, from the probe response packets, the signature values and using the signature values to determine a topology of hops including positions of the hops in a path from the source node to the destination node.

Inventors

Manomugdha Biswas
Ajay Ramamurthy
Anirban Bhattacharya

Assignees

KEYSIGHT TECHNOLOGIES, INC.

Dates

Publication Date: 20260507
Application Date: 20250128
Priority Date: 20241107

Claims (20)

1 . A method for discovering network paths using an enhanced traceroute procedure, the method comprising: generating, by a source node, a plurality of probe request packets, the probe request packets being addressed to a destination node and each being associated with an entropy value that identifies a packet flow; including, in each of the probe request packets, a signature value that is unique to the probe request packet within the packet flow; setting time to live (TTL) values in the probe request packets for the packet flow to incrementally increasing values; transmitting the probe request packets to a next-hop node in the network topology, wherein transmitting the probe request packets includes, for a first packet flow, transmitting a first probe request packet having a first TTL value and, prior to receiving a probe response packet corresponding to the first probe request packet, transmitting, for the first packet flow, a second probe request packet having a second TTL value different from the first TTL value; receiving, by the source node, probe response packets in response to the probe request packets, the probe response packets each encapsulating one of the probe request packets, including the signature value; reading, by the source node and from the probe response packets, the signature values; and determining, by the source node and using the signature values read from the probe response packets, a topology of hops including positions of the hops in a path from the source node to the destination node.
2 . The method of claim 1 wherein generating the probe request packets includes generating Internet control management protocol (ICMP) packets.
3 . The method of claim 1 comprising generating the entropy value from a combination of source Internet protocol (IP) address, source user datagram protocol (UDP) port, destination IP address, and destination UDP port.
4 . The method of claim 3 comprising varying the entropy values associated with different ones of the probe request packets to generate probe request packets associated with different packet flows.
5 . The method of claim 4 wherein varying the entropy values includes varying source and destination UDP port values in the probe request packets.
6 . The method of claim 1 wherein including the signature value in each of the probe request packets comprises inserting the signature value in a user datagram protocol (UDP) payload of each of the probe request packets.
7 . The method of claim 1 wherein determining the topology of hops in the path includes: storing, by the source node and in a network topology database, the signature values and the time to live values of each of the probe request packets; using the signature values read from the probe response packets to locate corresponding records in the network topology database; reading the time to live values from the records in the network topology database; and determining hop positions of originators of the probe response packets using the time to live values read from the records in the network topology database.
8 . The method of claim 1 comprising generating a report indicating a number of paths between a source and a destination, IP addresses and hop indices for the hops in each path, entropy values for flows that use each path, and a roundtrip time for each of the hops.
9 . The method of claim 1 wherein the source node comprises a network endpoint or a test tool and wherein generating the probe request packets includes generating the probe request packets from a plurality of different Internet protocol addresses.
10 . The method of claim 1 wherein the source node comprises a router.
11 . A system for discovering network paths using an enhanced traceroute procedure, the system comprising: a source node including at least one processor and a memory; and a network topology discoverer implemented by the at least one processor for generating a plurality of probe request packets, the probe request packets being addressed to a destination node and each being associated with an entropy value that identifies a packet flow, the network topology discoverer for including, in each of the probe request packets, a signature value that is unique to the probe request packet within the packet flow, setting time to live (TTL) values in the probe request packets for the packet flow to incrementally increasing values, transmitting the probe request packets to a next-hop node in the network topology, receiving, by the source node, probe response packets in response to the probe request packets, the probe response packets each encapsulating one of the probe request packets, including the signature value, reading, by the source node and from the probe response packets, the signature values, and determining, by the source node and using the signature values read from the probe response packets, a topology of hops including positions of the hops in a path from the source node to the destination node, wherein the network topology discoverer is configured to, in transmitting the probe request packets, for a first packet flow, transmit a first probe request packet having a first TTL value and, prior to receiving a probe response packet corresponding to the first probe request packet, transmit, for the first packet flow, a second probe request packet having a second TTL value different from the first TTL value.
12 . The system of claim 11 wherein the probe request packets comprise Internet control management protocol (ICMP) packets.
13 . The system of claim 11 wherein the network topology discoverer is configured to generate the entropy value from a combination of source Internet protocol (IP) address, source user datagram protocol (UDP) port, destination IP address, and destination UDP port.
14 . The system of claim 13 wherein the network topology discoverer is configured to vary the entropy values associated with different ones of the probe request packets to generate probe request packets associated with different packet flows.
15 . The system of claim 14 wherein the network topology discoverer is configured to vary the entropy values by varying source and destination UDP port values in the probe request packets.
16 . The system of claim 11 wherein the network topology discoverer is configured to insert the signature value in a user datagram protocol (UDP) payload of each of the probe request packets.
17 . The system of claim 11 wherein the network topology discoverer is configured to determine the topology of hops in the path by: storing, in a network topology database, the signature values and the time to live values of each of the probe request packets; using the signature values read from the probe response packets to locate corresponding records in the network topology database; reading the time to live values from the records in the network topology database; and determining hop positions of originators of the probe response packets using the time to live values read from the records in the network topology database.
18 . The system of claim 11 wherein the network topology discoverer is configured to generate a report indicating a number of paths between a source and a destination, IP addresses and hop indices for the hops in each path, entropy values for flows that use each path, and a roundtrip time for each of the hops.
19 . The system of claim 11 wherein the source node comprises a network endpoint, a test tool, or a router and wherein generating the probe request packets includes generating the probe request packets from a plurality of different Internet protocol addresses.
20 . A non-transitory computer readable medium having stored thereon executable instructions that when executed by a processor of a computer control the computer to perform steps comprising: generating, by a source node in a network topology, a plurality of probe request packets, the probe request packets being addressed to a destination node and each being associated with an entropy value identifying a packet flow; including, in each of the probe request packets, an entropy value that is unique to a packet flow and a signature value that is unique to the probe request packet within the packet flow; setting time to live (TTL) values in the probe request packets for the packet flow to incrementally increasing values; transmitting the probe request packets to a next-hop node in the network topology, wherein transmitting the probe request packets includes, for a first packet flow, transmitting a first probe request packet having a first TTL value and, prior to receiving a probe response packet corresponding to the first probe request packet, transmitting, for the first packet flow, a second probe request packet having a second TTL value different from the first TTL value; receiving, by the source node, probe response packets in response to the probe request packets, the probe response packets each encapsulating one of the probe request packets, including the signature value; reading, by the source node and from the probe response packets, the signature values; and determining, by the source node and using the signature values read from the probe response packets, a topology of hops including positions of the hops in a path from the source node to the destination node.

Description

PRIORITY CLAIM This application claims the priority benefit of Indian Patent Application Number 202411085452, filed Nov. 7, 2024, the disclosure of which is incorporated herein by reference in its entirety. TECHNICAL FIELD The subject matter described herein relates to network topology discovery. More particularly, the subject matter described herein relates to methods, systems, and computer readable media for discovering ECMP paths in a network topology using an enhanced traceroute procedure BACKGROUND ECMP is a routing strategy where multiple equal cost routing paths exist between a source and a destination. In an ECMP routing strategy, routers between the source and the destination are referred to as hops. At each hop between the source and the destination, a router must make a per-hop routing decision as to which path to use to forward traffic. Mapping and debugging network topologies with increasing numbers of ECMP paths at each router can be complex. Traceroute is a utility available in most computer operating systems that can be used to discover network hops between a source and a destination by sending Internet control management protocol (ICMP) echo request packets with incrementally increasing time to live values (TTL) towards the destination. When a router receives an ICMP echo request packet, the router determines if the TTL value is greater than 1. If the TTL value is greater than 1, the router decrements the TTL value in the packet and forwards the packet to a next-hop router in a path towards the destination or to the destination if the destination is the next hop. If the TTL value in a received ICMP echo request packet is equal to 1, the router responds to the ICMP echo request packet with an ICMP time exceeded in transit message indicating that the TTL value in the packet became zero before the packet reached the destination. By incrementally increasing the TTL values in successive ICMP messages, a sending node can discover a number of hops between a source and a destination. However, while conventional traceroute gives hop information, it does not provide information as to how hops are connected to each other. As a result, conventional traceroute does not provide a complete view of a network topology. In addition, in some conventional traceroute implementations, a probe request is sent, and the sender waits for a probe response before sending the next probe request with an incremented TTL value. Such an implementation may result in unacceptable delays in discovering network topologies in networks with large numbers of hops and/or paths. Accordingly, in light of these and other difficulties, there exists a need for improved methods, systems, and computer readable media for network topology discovery. SUMMARY A method for discovering network paths using an enhanced traceroute procedure is described. Although the method is referred to as an enhanced traceroute procedure, in one implementation, the method may not use any native traceroute code on the sending node. Instead, the method uses code that generates ICMP echo request packets and receives ICMP response packets (like traceroute) but uses a unique per packet, per flow signature value in the ICMP echo request packets that are encapsulated in ICMP response packets to rapidly and accurately match requests and responses. In one example, the method includes generating, by a source node, a plurality of probe request packets, the probe request packets being addressed to a destination node and being associated with an entropy value that identifies as packet flow and including, in each of the probe request packets, a signature value that is unique to the probe request packet within the packet flow. The method further includes setting TTL values in the probe request packets for the packet flow to incrementally increasing values. The method further includes transmitting the probe request packets to a next-hop node in the network topology where transmitting the probe request packets includes, for a first packet flow, transmitting a first probe request packet having a first TTL value and, prior to receiving a probe response packet corresponding to the first probe request packet, transmitting, for the first packet flow, a second probe request packet having a second TTL value different from the first TTL value. The method further includes receiving, by the source node, probe response packets in response to the probe request packets, the probe response packets each encapsulating one of the probe request packets, including the signature value. The method further includes reading, by the source node and from the probe response packets, the signature values. The method further includes determining, by the source node and using the signature values read from the probe response packets, a topology of hops including positions of the hops in a path from the source node to the destination node. In another example, if there are “n” hosts, which may or may not ex