Patent Description:
Unfortunately, traditional systems for discovering network paths may be unable to provide comprehensive and/or complete traceroutes. For example, to increase the efficiency and/or bandwidth of a particular network connection, multiple network paths may be configured to forward packets between two nodes. A conventional traceroute technology may return only a single possible path. As such, network administrators may be unable to analyze and/or assess many of the network devices that forward packets between two nodes, thereby hindering the detection of errors within network paths between the nodes.

The instant disclosure, therefore, identifies and addresses a need for improved apparatuses, systems, and methods for discovering network paths.

Existing prior art includes<CIT>, which relates to systems and methods for determining a topology of a network comprising a plurality of intermediary devices and intermediary paths; and <CIT>, which relates to a system that identifies network switches along a path.

The present application provides a method according to claim <NUM> and a corresponding system according to claim <NUM>.

As another example, a system for implementing the above-described method may include various modules stored in memory. The system may also include at least one hardware processor that executes these modules. For example, the system may include (<NUM>) a receiving module that receives, at a source node, a request to discover a plurality of network paths that each lead from the source node to a destination node and (<NUM>) a discovery module that simultaneously discovers the plurality of network paths that lead from the source node to the destination node by (A) identifying each next hop that resides between the source node and the destination node, (B) sending, from the source node to each next hop, a path-request probe that prompts the next hop to (i) determine each next-closest hop that resides between the next hop and the destination node and (ii) return, to the source node, a path-response probe that identifies the next-closest hops as residing between the next hop and the destination node, (C) receiving, at the source node, the path-response probes from the next hops, (D) determining, at the source node based at least in part on the path-response probes, that one or more of the plurality of network paths include (i) the next hops that reside between the source node and the destination node and (ii) the next-closest hops that reside between the next hops and the destination node, and then (E) iteratively discovering any subsequent hops that reside between the next-closest hops and the destination node by sending a subsequent path-request probe to each next-closest hop.

As a further example, an apparatus for implementing the above-described method may include at least one storage device that stores information that identifies next hops of a source node within a network. In this example, the apparatus may also include at least one physical processing device communicatively coupled to the storage device at the source node, wherein the physical processing device (<NUM>) receives, at the source node, a request to discover a plurality of network paths that each lead from the source node to a destination node and (<NUM>) simultaneously discovers the plurality of network paths that lead from the source node to the destination node by (A) identifying each next hop that resides between the source node and the destination node, (B) sending, from the source node to each next hop, a path-request probe that prompts the next hop to (i) determine each next-closest hop that resides between the next hop and the destination node and (ii) return, to the source node, a path-response probe that identifies the next-closest hops as residing between the next hop and the destination node, (C) receiving, at the source node, the path-response probes from the next hops, (D) determining, at the source node based at least in part on the path-response probes, that one or more of the plurality of network paths include (i) the next hops that reside between the source node and the destination node and (ii) the next-closest hops that reside between the next hops and the destination node, and then (E) iteratively discovering any subsequent hops that reside between the next-closest hops and the destination node by sending a subsequent path-request probe to each next-closest hop.

Features from any of the above-mentioned embodiments may be used in combination with one another in accordance with the general principles described herein. These and other embodiments, features, and advantages will be more fully understood upon reading the following detailed description in conjunction with the accompanying drawings and claims.

Throughout the drawings, identical reference characters and descriptions indicate similar, but not necessarily identical, elements. While the examples described herein are susceptible to various modifications and alternative forms, specific embodiments have been shown by way of example in the drawings and will be described in detail herein. However, the examples described herein are not intended to be limited to the particular forms disclosed. Rather, the instant disclosure covers all modifications, equivalents, and alternatives falling within the scope of the appended claims.

The present disclosure describes various apparatuses, systems, and methods for discovering network paths. As will be explained in greater detail below, embodiments of the instant disclosure may identify multiple network paths that each lead from a source node to a destination node. In some examples, the disclosed embodiments may identify each possible (e.g., each existing) network path between two nodes. In other examples, these embodiments may identify one or more paths that are suitable and/or configured for specific packets.

To accomplish the task of identifying multiple network paths between a source node and a destination node, embodiments of the instant disclosure may identify at least one hop that resides immediately downstream from the source node. The disclosed embodiments may then send, to this first hop, a probe that prompts the first hop to identify the next hop within each network path that leads from the first hop to the destination node. The first hop may then return the network addresses of these next hops to the source node. In response, the source node may send similar probes to each network address identified by the first hop. Embodiments of the instant disclosure may facilitate this iterative process of discovering next hops within the network paths until each subsequent hop has been identified. Accordingly, these embodiments may efficiently provide network administrators with multi-path traceroutes that describe all or a portion of the network paths that lead between two nodes.

By providing such multi-path traceroutes, the disclosed embodiments may enable network administrators to quickly and accurately troubleshoot malfunctions within network connections that utilize multiple network paths. Moreover, such multi-path traceroutes may facilitate discovering and recording comprehensive and/or complete network topologies. In contrast, traditional traceroute technologies may identify only a single potential network path between two nodes (even if multiple paths exist between the nodes).

The following will provide, with reference to <FIG> and <FIG>, detailed descriptions of example systems for discovering network paths. Detailed descriptions of example network paths between a source node and a destination node will be provided in connection with <FIG>. Detailed descriptions of example packets for discovering network paths will be provided in connection with <FIG>. Detailed descriptions of corresponding computer-implemented methods will be provided in connection with <FIG>. In addition, detailed descriptions of an example computing system for carrying out these methods will be provided in connection with <FIG>.

<FIG> is a block diagram of an example system <NUM> for discovering network paths. As illustrated in this figure, example system <NUM> may include one or more modules <NUM> for performing one or more tasks. As will be explained in greater detail below, modules <NUM> may include a request module <NUM> and a discovery module <NUM>. Although illustrated as separate elements, one or more of modules <NUM> in <FIG> may represent portions of a single module or application.

In certain embodiments, one or more of modules <NUM> in <FIG> may represent one or more software applications or programs that, when executed by a computing device, cause the computing device to perform one or more tasks. For example, and as will be described in greater detail below, one or more of modules <NUM> may represent modules stored and configured to run on one or more computing devices, such as the devices illustrated in <FIG> (e.g., source node <NUM> and/or destination node <NUM>). In addition, one or more of modules <NUM> may perform any of the functionality described herein in connection with any of the devices illustrated in <FIG>. One or more of modules <NUM> in <FIG> may also represent all or portions of one or more special-purpose computers configured to perform one or more tasks.

As illustrated in <FIG>, system <NUM> may also include one or more memory devices, such as memory <NUM>. Memory <NUM> generally represents any type or form of volatile or non-volatile storage device or medium capable of storing data and/or computer-readable instructions. In one example, memory <NUM> may store, load, and/or maintain one or more of modules <NUM>. Examples of memory <NUM> include, without limitation, Random Access Memory (RAM), Read Only Memory (ROM), flash memory, Hard Disk Drives, (HDDs), Solid-State Drives (SSDs), optical disk drives, caches, variations or combinations of one or more of the same, and/or any other suitable storage memory.

As illustrated in <FIG>, system <NUM> may also include one or more physical processors, such as physical processor <NUM>. Physical processor <NUM> generally represents any type or form of hardware-implemented processing unit capable of interpreting and/or executing computer-readable instructions. In one example, physical processor <NUM> may access and/or modify one or more of modules <NUM> stored in memory <NUM>. Additionally or alternatively, physical processor <NUM> may execute one or more of modules <NUM> to facilitate discovering network paths within a network. Examples of physical processor <NUM> include, without limitation, microprocessors, microcontrollers, Central Processing Units (CPUs), Field-Programmable Gate Arrays (FPGAs) that implement softcore processors, Application-Specific Integrated Circuits (ASICs), portions of one or more of the same, variations or combinations of one or more of the same, and/or any other suitable physical processor.

As illustrated in <FIG>, example system <NUM> may also include information that identifies one or more network paths, such as path information <NUM>. In some examples, path information <NUM> may represent and/or identify a series of hops that leads between two network nodes. For example, path information <NUM> may identify each node (e.g., each router or other network device) that is capable of and/or configured to forward a packet between a particular source node and destination node.

In one embodiment, path information <NUM> may identify one or more distinct network paths that lead between a source node and a destination node. For example, path information <NUM> may collectively describe all or a portion of the equal-cost network paths that exist between the source node and the destination node. The term "equal-cost network paths," as used herein, generally refers to any group or set of network paths between two nodes that involve and/or require the same number of hops. In some examples, each equal-cost network path between a source node and a destination node may involve the minimum number of hops required to reach the destination node.

Additionally or alternatively, path information <NUM> may describe all or a portion of the network paths that a packet with one or more particular characteristics may potentially traverse between a source node and a destination node. For example, path information <NUM> may describe each network path that is configured to and/or capable of forwarding a packet of a specific protocol (e.g., a User Datagram Protocol (UDP) packet). In another example, path information <NUM> may describe each possible network path for a packet that is to be forwarded in accordance with a particular network policy (e.g., a security policy or a load-balancing policy).

As will be explained in greater detail below, the disclosed systems may discover all or a portion of the network paths described by path information <NUM>. In some examples, the disclosed systems may identify path information <NUM> based at least in part on sending one or more path-request probes, such as a path-request probe <NUM> shown in <FIG>. The term "path-request probe," as used herein, generally refers to any type or form of packet, message, or other unit of formatted data that a source node may send in order to identify additional nodes within network paths that lead between the source node and a destination node.

In some examples, path-request probe <NUM> may prompt a node that receives path-request probe <NUM> to identify all or a portion of the next hops within network paths that lead from the node to a particular destination node. The term "next hop," as used herein, generally refers to any node that resides immediately and/or directly downstream from another node within a network path. In some examples, a node within a network path may have more than one next hop (e.g., the node may be part of multiple network paths that each lead from a source node and a destination node).

In some examples, path-request probe <NUM> may also prompt a node to generate and return a path-response probe, such as a path-response probe <NUM> shown in <FIG>. The term "path-response probe," as used herein, generally refers to any type or form of packet, message, or other unit of formatted data that identifies and/or lists each next hop discovered by a node that received a path-request probe. As will be explained in greater detail below, receiving a path-response probe at a source node may prompt the source node to send subsequent path-request probes to each node listed within the path-response probe. Accordingly, the disclosed systems may utilize path-request probes and path-response probes to iteratively discover multiple network paths that lead from a source node to a destination node.

Example system <NUM> in <FIG> may be implemented in a variety of ways. For example, all or a portion of example system <NUM> may represent portions of example system <NUM> in <FIG>. As shown in <FIG>, system <NUM> may include a source node <NUM> in communication with a destination node <NUM> via a network <NUM>. In one example, all or a portion of the functionality of modules <NUM> may be performed by source node <NUM>, destination node <NUM>, and/or any other suitable computing system. As will be described in greater detail below, one or more of modules <NUM> from <FIG> may, when executed by at least one processor of source node <NUM>, enable source node <NUM> to discover all or a portion of the network paths that lead from source node <NUM> to destination node <NUM>.

Source node <NUM> and destination node <NUM> each generally represent any type or form of physical computing device that facilitates communication within a network and/or across networks. In one embodiment, source node <NUM> may represent a node that is upstream relative to destination node <NUM>. In some examples, source node <NUM> and destination node <NUM> may each include and/or represent a router (such as a customer edge router, a provider edge router, a hub router, a spoke router, an autonomous system boundary router, and/or an area border router). Additional examples of source node <NUM> and destination node <NUM> include, without limitation, switches, hubs, modems, bridges, repeaters, gateways, multiplexers, network adapters, network interfaces, servers, portions of one or more of the same, combinations or variations of one or more of the same, and/or any other suitable network nodes.

Network <NUM> generally represents any medium or architecture capable of facilitating communication or data transfer. In one example, network <NUM> may facilitate communication between source node <NUM> and destination node <NUM>. In particular, network <NUM> may facilitate this communication via one or more intermediate nodes (e.g., hops) between source node <NUM> and destination node <NUM>. These intermediate nodes may represent and/or include any type or form of suitable network device.

Network <NUM> may facilitate communication or data transfer using wireless and/or wired connections. Examples of network <NUM> include, without limitation, an intranet, a Wide Area Network (WAN), a Local Area Network (LAN), a Personal Area Network (PAN), the Internet, Power Line Communications (PLC), a cellular network (e.g., a Global System for Mobile Communications (GSM) network), an MPLS network, a resource RSVP-TE network, portions of one or more of the same, variations or combinations of one or more of the same, and/or any other suitable network. Although illustrated as being external to network <NUM> in <FIG>, source node <NUM> and destination node <NUM> may each represent a portion of network <NUM> and/or be included in network <NUM>.

<FIG> is a flow diagram of an example computer-implemented method <NUM> for discovering network paths. The steps shown in <FIG> may be performed by any suitable computer-executable code and/or computing system, including system <NUM> in <FIG> and/or system <NUM> in <FIG>. In one example, each of the steps shown in <FIG> may represent an algorithm whose structure includes and/or is represented by multiple sub-steps, examples of which will be provided in greater detail below.

As illustrated in <FIG>, at step <NUM> one or more of the apparatuses and/or systems described herein may receive, at a source node, a request to discover a plurality of network paths that each lead from the source node to a destination node. For example, receiving module <NUM> may, as part of source node <NUM> in <FIG>, receive a request to discover a plurality of network paths that each lead from source node <NUM> to destination node <NUM>.

<FIG> illustrates example network paths that each lead from source node <NUM> to destination node <NUM>. Specifically, this example shows a network path <NUM> that consists of source node <NUM>, a node <NUM>, a node <NUM>, a node <NUM>, and destination node <NUM>. <FIG> also illustrates a network path <NUM> that consists of source node <NUM>, a node <NUM>, node <NUM>, node <NUM>, and destination node <NUM>. In one embodiment, network paths <NUM> and <NUM> may represent equal-cost network paths.

The systems described herein may perform step <NUM> in a variety of different ways and/or contexts. In some examples, receiving module <NUM> may receive a request to perform a multi-path traceroute for network paths between source node <NUM> and destination node <NUM>. The term "traceroute," as used herein, generally refers to any type or form of tool, technique, and/or process that identifies a network address of each hop within a network path. Accordingly, the term "multi-path traceroute," as used herein, generally refers to any type of traceroute that identifies the network address of each hop within all or a portion of the existing network paths between two network nodes.

In some embodiments, receiving module <NUM> may receive a request to perform a general and/or comprehensive multi-path traceroute. For example, receiving module <NUM> may receive a request to perform a multi-path traceroute that returns each equal-cost network path between source node <NUM> and destination node <NUM>. Additionally or alternatively, receiving module <NUM> may receive a request to perform a multi-path traceroute for a particular type of packet. For example, receiving module <NUM> may receive a request to identify each possible network path for packets that are to be forwarded via a particular protocol. As another example, receiving module <NUM> may receive a request to identify each possible network path for a packet that is to be forwarded in accordance with one or more network policies (such as a security policy and/or a load-balancing policy). In a further example, receiving module <NUM> may receive a request to identify the precise path that a particular packet is expected to traverse while traveling between source node <NUM> and destination node <NUM>.

Receiving module <NUM> may receive a request to perform a multi-path traceroute from any type or form of user, administrator, application, network device, and/or other type of entity. In one example, receiving module <NUM> may receive a request from a traceroute application (e.g., an application that initiates performing traceroutes and/or provides the results of a traceroute to an administrator). In one embodiment, this traceroute application may reside and/or operate within source node <NUM>. In other embodiments, receiving module <NUM> may receive a request from a traceroute application that operates external to and/or remotely from source node <NUM>.

Returning to <FIG>, at step <NUM> one or more of the apparatuses and/or systems described herein may simultaneously discover the plurality of network paths that lead from the source node to the destination node. For example, discovery module <NUM> may, as part of source node <NUM> in <FIG>, simultaneously discover the plurality of network paths that lead from source node <NUM> to destination node <NUM>. In one embodiment, step <NUM> may include one or more sub-steps, such as steps <NUM>(A-E). At step <NUM>(A), discovery module <NUM> may identify each next hop that resides between source node <NUM> and destination node <NUM>.

The systems described herein may perform step <NUM>(A) in a variety of different ways and/or contexts. In some examples, discovery module <NUM> may identify each next hop that resides between source node <NUM> and destination node <NUM> by searching a routing table utilized by source node <NUM>. The term "routing table," as used herein, generally refers to any type or form of data structure that stores one or more network paths to facilitate forwarding packets to various network destinations. For example, a routing table within a node may list the network addresses (e.g., Internet protocol (IP) addresses) of hops within one or more network paths that include the node. In some examples, discovery module <NUM> may, while operating as part of and/or within source node <NUM>, identify one or more next hops that reside between source node <NUM> and destination node <NUM> by querying and/or analyzing the routing table of source node <NUM>.

Additionally or alternatively, discovery module <NUM> may identify one or more next hops that reside between source node <NUM> and destination node <NUM> by sending a path-request probe to source node <NUM>. For example, discovery module <NUM> may, while operating as part of a traceroute application within source node <NUM>, send a path-request probe to a network stack of source node <NUM>. In another example, discovery module <NUM> may send a path-request probe to the network stack of source node <NUM> while operating within an external and/or remote node.

<FIG> illustrates an example path-request probe <NUM> that discovery module <NUM> may send to the network stack of source node <NUM>. In this example, path-request probe <NUM> may include an IP header <NUM> and an Internet Control Message Protocol (ICMP) header <NUM>. Path-request probe <NUM> may include any additional headers and/or data fields not illustrated in <FIG>.

As shown in <FIG>, IP header <NUM> may include a probe source address <NUM> that identifies the IP address of the node that generated path-request probe <NUM>. IP header <NUM> may also include a probe destination address <NUM> that identifies the IP address of a node to which path-request probe <NUM> is at least intermediately destined. In the example of <FIG>, both probe source address <NUM> and probe destination address <NUM> may correspond to the IP address of source node <NUM>. IP header <NUM> may include any additional information (such as an IP version number and/or properties of path-request probe <NUM>) that facilitates routing and/or forwarding path-request probe <NUM>.

In the example of <FIG>, ICMP header <NUM> may include one or more data fields that prompt and/or enable source node <NUM> to identify the next hop within at least one network path that leads from source node <NUM> to destination node <NUM>. In some examples, at least one of these data fields may be encoded by a type-length-value (TLV) encoding scheme.

In one embodiment, ICMP header <NUM> may include a data field that indicates path-request probe <NUM> is a "multipath-request" packet. This indication may prompt source node <NUM> to generate and return a path-response probe to the network stack of source node <NUM>.

ICMP header <NUM> may also include a next-hop address <NUM> that identifies the IP address of the final destination of path-request probe <NUM>. In the example of <FIG>, this IP address may match probe destination address <NUM>. After receiving path-request probe <NUM>, source node <NUM> may compare next-hop address <NUM> with its own (e.g., local) IP address. In response to determining that next-hop address <NUM> corresponds to its own IP address, source node <NUM> may determine that path-request probe <NUM> was destined for source node <NUM>. In the event that source node <NUM> (or any additional node) receives a path-request probe with a next-hop address that does not match the node's own IP address, the node may forward the path-request probe to the next-hop address listed within the path-request probe.

ICMP header <NUM> may additionally include a destination node address <NUM> that identifies the IP address of destination node <NUM>. Based at least in part on this IP address, source node <NUM> may identify the IP address of each next hop that resides between source node <NUM> and destination node <NUM> within the routing table of source node <NUM>. For example, source node <NUM> may search the routing table to identify previously established network paths that lead to destination node <NUM>.

In some examples, source node <NUM> may search this routing table based on additional information included within ICMP header <NUM>, such as a packet header flag. In the event that this flag is set (as illustrated in <FIG>), source node <NUM> may identify next hops within network paths that are suitable and/or designed for packets with properties indicated by the headers of path-request probe <NUM>. For example, IP header <NUM> and/or ICMP header <NUM> may include one or more settings and/or characteristics indicative of packets that are to be forwarded via a specific protocol and/or in accordance with a specific network policy. Specifically, IP header <NUM> and/or ICMP header <NUM> may include and/or represent the headers of a specific packet that is to be forwarded (or has already been forwarded) to destination node <NUM>.

In some examples, source node <NUM> may identify next hops within network paths that are appropriate and/or suitable for settings and/or characteristics indicated by path-request probe <NUM> (while disregarding next hops within inappropriate and/or unsuitable network paths). In one embodiment, source node <NUM> may identify these hops by providing information from the headers of path-request probe <NUM> to a hash function that is utilized by the routing table of source node <NUM> to select equal-cost network paths. By searching for next hops based on such information, the disclosed systems may facilitate performing multi-path traceroutes for specific packets and/or specific types of packets.

After source node <NUM> identifies each suitable and/or appropriate next hop, source node <NUM> may add the IP addresses of these next hops to a path-response probe. <FIG> illustrates an example path-response probe <NUM> that may be generated by source node <NUM>. Similar to path-request probe <NUM>, path-response probe <NUM> may contain an IP header <NUM> and an ICMP header <NUM>. In this example, IP header <NUM> may include a probe source address <NUM> and a probe destination address <NUM>. As shown in <FIG>, both of these IP addresses may correspond to the IP address of source node <NUM> (shown in <FIG>).

ICMP header <NUM> may include one or more data fields that indicate and/or describe each next hop discovered by source node <NUM>. In some examples, at least one of these data fields may be encoded via a TLV encoding scheme.

In one example, a data field within ICMP header <NUM> may indicate that path-response probe <NUM> is a "multipath-reply" packet. This indication may inform discovery module <NUM> that path-response probe <NUM> contains the IP addresses of one or more recently discovered next hops. ICMP header <NUM> may also include downstream hop addresses <NUM> that list the IP addresses of each next hop discovered by source node <NUM>. In one embodiment, downstream hops addresses <NUM> may correspond to node <NUM> of network path <NUM> and node <NUM> of network path <NUM> illustrated in <FIG>.

In some embodiments, discovery module <NUM> may receive path-response probe <NUM> at source node <NUM> after source node <NUM> forwards path-response probe <NUM> to its own network stack. In response to receiving path-response probe <NUM>, discovery module <NUM> may identify downstream hop addresses <NUM> within ICMP header <NUM>. Discovery module <NUM> may then record and/or store these addresses. For example, discovery module <NUM> may add downstream hop addresses <NUM> to a map, tree, table, and/or other data structure that indicates the nodes within each discovered network path. In some embodiments, discovery module <NUM> may continue to update this data structure as new hops are discovered.

In some examples, discovery module <NUM> may identify a particular network path in which a next hop resides based on information included within the path-response probe that identified the next hop. For example, as shown in <FIG>, ICMP header <NUM> may include an identification number and/or a sequence number. These numbers may enable discovery module <NUM> to determine that path-response probe <NUM> was sent in response to path-request probe <NUM>. Specifically, discovery module <NUM> may compare the identification number and/or sequence number of path-response probe <NUM> with an identification number and/or sequence number of path-request probe <NUM>. In response to determining that these numbers match and/or correspond, discovery module <NUM> may determine that the next hops listed in path-response probe <NUM> are next hops in network paths that begin at source node <NUM>.

Returning to <FIG>, at step <NUM>(B) discovery module <NUM> may send, from source node <NUM> to each next hop, a path-request probe that prompts the next hop to (<NUM>) determine each next-closest hop that resides between the next hop and the destination node and (<NUM>) return, to the source node, a path-response probe that identifies the next-closest hops as residing between the next hop and the destination node. The systems described herein may perform step <NUM>(B) in a variety of different ways and/or contexts. In some examples, discovery module <NUM> may send a path-request probe to each next hop that was identified during step <NUM>(A). Continuing the example of <FIG>, discovery module <NUM> may send a path-request probe to each of downstream hop addresses <NUM>. Such path-request probes may be generally similar to path-request probe <NUM>.

<FIG> illustrates an example path-request probe <NUM> that discovery module <NUM> may send to one of downstream hop addresses <NUM>. As shown in <FIG>, an IP header <NUM> of path-request probe <NUM> may include a probe source address <NUM> that identifies the IP address of source node <NUM>. IP header <NUM> may also include a probe destination address <NUM> that identifies an IP address of a node to which path-request probe <NUM> is at least intermediately destined. In the example of <FIG>, an ICMP header <NUM> of path-request probe <NUM> may also include a next-hop address <NUM> that identifies the IP address of the final destination of path-response probe <NUM>. In addition, ICMP header <NUM> may include destination node address <NUM> (i.e., the IP address of destination node <NUM>). Path-request probe <NUM> may contain any additional information (such as an identification number, a sequence number, and/or a packet header flag) that facilitates discovering subsequent hops within one or more network paths.

In some examples, probe destination address <NUM> may correspond to a node that resides immediately upstream from the final destination of path-request probe <NUM>. For example, probe destination address <NUM> may correspond to the IP address of the node that discovered next-hop address <NUM>. Accordingly, as shown in <FIG>, probe destination address <NUM> may correspond to the IP address of source node <NUM>. In this example, discovery module <NUM> may forward path-request probe <NUM> to next-hop address <NUM> by way of source node <NUM>. For example, discovery module <NUM> may forward path-request probe <NUM> to the network stack of source node <NUM>. The network stack of source node <NUM> may then identify next-hop address <NUM> within ICMP header <NUM> and determine whether source node <NUM> is capable of forwarding path-request probe <NUM> to next-hop address <NUM>. For example, source node <NUM> may determine whether next-hop address <NUM> is currently available to and/or reachable from source node <NUM>. In the event that source node <NUM> is capable of forwarding path-request probe <NUM> to next-hop address <NUM>, source node <NUM> may replace, within IP header <NUM>, probe destination address <NUM> with next-hop address <NUM>. Source node <NUM> may then forward path-request probe <NUM> to next-hop address <NUM>. Source node <NUM> may perform a variety of alternative actions in the event that source node <NUM> is not capable of forwarding path-request probe <NUM> to next-hop address <NUM>, such as dropping path-request probe <NUM> and/or returning an error message to discovery module <NUM>.

In one embodiment, discovery module <NUM> may send a similar path-request probe to the other IP address within downstream hop addresses <NUM>. In this embodiment, discovery module <NUM> may include, within this path-request probe, a new identification number and/or sequence number (e.g., compared to the numbers within path-request probe <NUM>). In this way, discovery module <NUM> may establish and/or indicate that the node at this IP address resides within a different network path than the node at probe destination address <NUM>.

In some examples, next-hop address <NUM> may correspond to node <NUM> within network path <NUM>. In these examples, the other IP address within downstream hop addresses <NUM> may correspond to node <NUM> within network path <NUM>. In response to receiving a path-request probe from source node <NUM>, nodes <NUM> and <NUM> may both identify each next-closest hop between themselves and destination node <NUM>. For example, nodes <NUM> and <NUM> may search their routing tables for IP addresses of each next-closest downstream hop. Nodes <NUM> and <NUM> may then each list these IP addresses within a path-response probe and forward the path-response probes to source node <NUM>.

Returning to <FIG>, at step <NUM>(C) discovery module <NUM> may receive, at the source node, the path-response probes from the next hops. The systems described herein may perform step <NUM>(C) in a variety of different ways and/or contexts. In some examples, discovery module <NUM> may determine that source node <NUM> receives a path-response probe in response to each path-request probe that was sent in step <NUM>(B). Continuing with the example of <FIG>, discovery module <NUM> may receive a path-response probe from node <NUM> in response to path-request probe <NUM>. Discovery module <NUM> may also receive a path-response probe from node <NUM> in response to the path-request probe sent to node <NUM>.

<FIG> illustrates an example path-response probe <NUM> that discovery module <NUM> may receive from node <NUM>. As shown in <FIG>, an IP header <NUM> of path-response probe <NUM> may include a probe source address <NUM> that identifies the IP address of node <NUM>. IP header <NUM> may also include a probe destination address <NUM> that identifies the IP address of source node <NUM>. In addition, path-response probe <NUM> may include an ICMP header <NUM> that identifies a downstream hop address <NUM>. In one embodiment, downstream hop address <NUM> may correspond to the IP address of node <NUM> in <FIG>. As shown in <FIG>, node <NUM> may reside within both network path <NUM> and network path <NUM>. Accordingly, discovery module <NUM> may receive, from node <NUM>, a path-response probe that also identifies node <NUM> as a next-closest hop. Although <FIG> illustrates a single next-closest hop for both node <NUM> and node <NUM>, in some examples node <NUM> and/or <NUM> may discover one or more additional next-closest hops (and then list the IP addresses of these next-closest hops within the path-response probes sent to source node <NUM>).

Returning to <FIG>, at step <NUM>(D) discovery module <NUM> may determine, at the source node based at least in part on the path-response probes, that one or more of the plurality of network paths include (<NUM>) the next hops that reside between the source node and the destination node and (<NUM>) the next-closest hops that reside between the next hops and the destination node. The systems described herein may perform step <NUM>(D) in a variety of different ways and/or contexts. In some examples, discovery module <NUM> may determine, for each next hop listed within a path-response probe received at source node <NUM>, all of the network paths that include the next hop. As described above in connection with step <NUM>(A), discovery module <NUM> may determine a specific network path in which a next hop resides based at least in part on identification numbers and/or sequence numbers included within the path-response probe that identified the next hop.

Continuing with the example of <FIG>, discovery module <NUM> may determine that nodes <NUM> and <NUM> reside within network path <NUM> based on the identification numbers and/or sequence numbers of path-request probe <NUM>, path-response probe <NUM>, path-request probe <NUM>, and path-response probe <NUM>. Similarly, discovery module <NUM> may determine that node <NUM> and node <NUM> reside within network path <NUM> based on the identification numbers and/or sequence numbers of path-request probe <NUM>, path-response probe <NUM>, the path-request probe sent to node <NUM>, and the path-response probe received from node <NUM>.

Returning to <FIG>, at step <NUM>(E) discovery module <NUM> may iteratively discover any subsequent hops that reside between the next-closest hops and the destination node by sending a subsequent path-request probe to each next-closest hop. The systems described herein may perform step <NUM>(E) in a variety of different ways and/or contexts. In some examples, discovery module <NUM> may send a path-request probe to each next-closest hop identified in step <NUM>(C). Continuing with the example of <FIG>, discovery module <NUM> may send a path-request probe to node <NUM> in response to path-response probe <NUM>. In some examples, discovery module <NUM> may send an additional path-request probe to node <NUM> in response to the path-response probe received from node <NUM>.

In one example, discovery module <NUM> may forward a path-request probe from source node <NUM> to node <NUM> via node <NUM>. Specifically, discovery module <NUM> may send, to node <NUM>, a path-request probe that contains the IP address of node <NUM>. In this example, node <NUM> may receive the path-request probe and then determine whether the IP address of node <NUM> is currently available to and/or reachable from node <NUM>. In the event that node <NUM> determines that node <NUM> is available and/or reachable, node <NUM> may forward the path-request probe to node <NUM>. In other examples, discovery module <NUM> may send a path-request probe directly to node <NUM>.

In response to receiving a path-request probe, node <NUM> may repeat the process of returning a path-response probe to source node <NUM>. This path-response node may identify node <NUM> (and any additional node not illustrated in <FIG>) as a subsequent hop between node <NUM> and destination node <NUM>.

In some examples, discovery module <NUM> may facilitate the cycle of sending path-request probes and receiving path-response nodes until every hop within each possible (e.g., requested) network path between source node <NUM> and destination node <NUM> has been discovered. This iterative process may involve any number of cycles, path-request probes, and/or path-response probes. For example, whenever a network path branches (e.g., whenever a hop has multiple next-closest hops), an additional so-called chain of path-request and path-response probes may be generated for each new branch. Discovery module <NUM> may continue to discover subsequent hops within each branch until determining that the branch reaches and/or converges at destination node <NUM>.

In some examples, discovery module <NUM> may determine that a network path branch has reached destination node <NUM> in response to discovery module <NUM> receiving a path-response probe from destination node <NUM>. Such a path-response probe may indicate that each hop within one or more particular network paths has been discovered. In some embodiments, discovery module <NUM> may conclude that each network path between source node <NUM> and destination node <NUM> has been discovered in response to determining that each chain of path-request and path-response probes includes a path-response probe from destination node <NUM>.

<FIG> illustrates an example path-response probe <NUM> that may be generated by destination node <NUM>. In this example, an IP header <NUM> of path-response probe <NUM> may include a probe source address <NUM> that identifies the IP address of destination node <NUM>. IP header <NUM> may also include a probe destination address <NUM> that identifies the IP address of source node <NUM>. In addition, path-response probe <NUM> may include an ICMP header <NUM> that contains a flag <NUM>. In the event that this flag is set (as illustrated in <FIG>), discovery module <NUM> may determine that path-response probe <NUM> originated from destination node <NUM>. Accordingly, discovery module <NUM> may not send any path-request probes in response to path-response probe <NUM>.

The systems described herein may perform a variety of actions after discovering one or more network paths that lead between source node <NUM> and destination node <NUM>. In some examples, request module <NUM> may provide each discovered network path to an application, user, administrator, device, and/or other entity that initiated the request to discover the network paths. For example, request module <NUM> may provide the entity that initiated the request a network path map that lists each discovered hop.

Such a network path map may be used in a variety of ways to improve the performance, security, and/or functionality of one or more network devices and/or network paths. In one embodiment, a network-troubleshooting application may utilize a network path map to detect and then fix a failure or malfunction within a particular node. For example, in response to detecting a potential error within one or more network paths (e.g., determining that at least a portion of the packets addressed to a destination node do not reach the destination node), the application may request the disclosed systems to provide a network path map that identifies network paths that lead to the destination node. The application may then assess the functionality of each node listed within the map to identify a particular node that is malfunctioning. In another embodiment, a network-mapping application may utilize a network path map to track and/or record the topology of a network. This action may enable network devices to more efficiently route and/or forward packets within a network.

<FIG> is a block diagram of an example computing system <NUM> capable of implementing and/or being used in connection with one or more of the embodiments described and/or illustrated herein. In some embodiments, all or a portion of computing system <NUM> may perform and/or be a means for performing, either alone or in combination with other elements, one or more of the steps described in connection with <FIG>. All or a portion of computing system <NUM> may also perform and/or be a means for performing and/or implementing any other steps, methods, or processes described and/or illustrated herein. In one example, computing system <NUM> may include and/or store all or a portion of modules <NUM> from <FIG>.

Computing system <NUM> broadly represents any type or form of electrical load, including a single or multi-processor computing device or system capable of executing computer-readable instructions. Examples of computing system <NUM> include, without limitation, workstations, laptops, client-side terminals, servers, distributed computing systems, mobile devices, network switches, network routers (e.g., backbone routers, edge routers, core routers, mobile service routers, broadband routers, etc.), network appliances (e.g., network security appliances, network control appliances, network timing appliances, SSL VPN (Secure Sockets Layer Virtual Private Network) appliances, etc.), network controllers, gateways (e.g., service gateways, mobile packet gateways, multi-access gateways, security gateways, etc.), and/or any other type or form of computing system or device.

Computing system <NUM> may be programmed, configured, and/or otherwise designed to comply with one or more networking protocols. According to certain embodiments, computing system <NUM> may be designed to work with protocols of one or more layers of the Open Systems Interconnection (OSI) reference model, such as a physical layer protocol, a link layer protocol, a network layer protocol, a transport layer protocol, a session layer protocol, a presentation layer protocol, and/or an application layer protocol. For example, computing system <NUM> may include a network device configured according to a Universal Serial Bus (USB) protocol, an Institute of Electrical and Electronics Engineers (IEEE) <NUM> protocol, an Ethernet protocol, a T1 protocol, a Synchronous Optical Networking (SONET) protocol, a Synchronous Digital Hierarchy (SDH) protocol, an Integrated Services Digital Network (ISDN) protocol, an Asynchronous Transfer Mode (ATM) protocol, a Point-to-Point Protocol (PPP), a Point-to-Point Protocol over Ethernet (PPPoE), a Point-to-Point Protocol over ATM (PPPoA), a Bluetooth protocol, an IEEE <NUM>. XX protocol, a frame relay protocol, a token ring protocol, a spanning tree protocol, and/or any other suitable protocol.

Computing system <NUM> may include various network and/or computing components. For example, computing system <NUM> may include at least one processor <NUM> and a system memory <NUM>. Processor <NUM> generally represents any type or form of processing unit capable of processing data or interpreting and executing instructions. For example, processor <NUM> may represent an application-specific integrated circuit (ASIC), a system on a chip (e.g., a network processor), a hardware accelerator, a general purpose processor, and/or any other suitable processing element.

Processor <NUM> may process data according to one or more of the networking protocols discussed above. For example, processor <NUM> may execute or implement a portion of a protocol stack, may process packets, may perform memory operations (e.g., queuing packets for later processing), may execute end-user applications, and/or may perform any other processing tasks.

System memory <NUM> generally represents any type or form of volatile or non-volatile storage device or medium capable of storing data and/or other computer-readable instructions. Examples of system memory <NUM> include, without limitation, Random Access Memory (RAM), Read Only Memory (ROM), flash memory, or any other suitable memory device. Although not required, in certain embodiments computing system <NUM> may include both a volatile memory unit (such as, for example, system memory <NUM>) and a non-volatile storage device (such as, for example, primary storage device <NUM>, as described in detail below). System memory <NUM> may be implemented as shared memory and/or distributed memory in a network device. Furthermore, system memory <NUM> may store packets and/or other information used in networking operations.

In certain embodiments, example computing system <NUM> may also include one or more components or elements in addition to processor <NUM> and system memory <NUM>. For example, as illustrated in <FIG>, computing system <NUM> may include a memory controller <NUM>, an Input/Output (I/O) controller <NUM>, and a communication interface <NUM>, each of which may be interconnected via communication infrastructure <NUM>. Communication infrastructure <NUM> generally represents any type or form of infrastructure capable of facilitating communication between one or more components of a computing device. Examples of communication infrastructure <NUM> include, without limitation, a communication bus (such as a Serial ATA (SATA), an Industry Standard Architecture (ISA), a Peripheral Component Interconnect (PCI), a PCI Express (PCle), and/or any other suitable bus), and a network.

Memory controller <NUM> generally represents any type or form of device capable of handling memory or data or controlling communication between one or more components of computing system <NUM>. For example, in certain embodiments memory controller <NUM> may control communication between processor <NUM>, system memory <NUM>, and I/O controller <NUM> via communication infrastructure <NUM>. In some embodiments, memory controller <NUM> may include a Direct Memory Access (DMA) unit that may transfer data (e.g., packets) to or from a link adapter.

I/O controller <NUM> generally represents any type or form of device or module capable of coordinating and/or controlling the input and output functions of a computing device. For example, in certain embodiments I/O controller <NUM> may control or facilitate transfer of data between one or more elements of computing system <NUM>, such as processor <NUM>, system memory <NUM>, communication interface <NUM>, and storage interface <NUM>.

Communication interface <NUM> broadly represents any type or form of communication device or adapter capable of facilitating communication between example computing system <NUM> and one or more additional devices. For example, in certain embodiments communication interface <NUM> may facilitate communication between computing system <NUM> and a private or public network including additional computing systems. Examples of communication interface <NUM> include, without limitation, a link adapter, a wired network interface (such as a network interface card), a wireless network interface (such as a wireless network interface card), and any other suitable interface. In at least one embodiment, communication interface <NUM> may provide a direct connection to a remote server via a direct link to a network, such as the Internet. Communication interface <NUM> may also indirectly provide such a connection through, for example, a local area network (such as an Ethernet network), a personal area network, a wide area network, a private network (e.g., a virtual private network), a telephone or cable network, a cellular telephone connection, a satellite data connection, or any other suitable connection.

In certain embodiments, communication interface <NUM> may also represent a host adapter configured to facilitate communication between computing system <NUM> and one or more additional network or storage devices via an external bus or communications channel. Examples of host adapters include, without limitation, Small Computer System Interface (SCSI) host adapters, Universal Serial Bus (USB) host adapters, IEEE <NUM> host adapters, Advanced Technology Attachment (ATA), Parallel ATA (PATA), Serial ATA (SATA), and External SATA (eSATA) host adapters, Fibre Channel interface adapters, Ethernet adapters, or the like. Communication interface <NUM> may also enable computing system <NUM> to engage in distributed or remote computing. For example, communication interface <NUM> may receive instructions from a remote device or send instructions to a remote device for execution.

As illustrated in <FIG>, example computing system <NUM> may also include a primary storage device <NUM> and/or a backup storage device <NUM> coupled to communication infrastructure <NUM> via a storage interface <NUM>. Storage devices <NUM> and <NUM> generally represent any type or form of storage device or medium capable of storing data and/or other computer-readable instructions. For example, storage devices <NUM> and <NUM> may represent a magnetic disk drive (e.g., a so-called hard drive), a solid state drive, a floppy disk drive, a magnetic tape drive, an optical disk drive, a flash drive, or the like. Storage interface <NUM> generally represents any type or form of interface or device for transferring data between storage devices <NUM> and <NUM> and other components of computing system <NUM>.

In certain embodiments, storage devices <NUM> and <NUM> may be configured to read from and/or write to a removable storage unit configured to store computer software, data, or other computer-readable information. Examples of suitable removable storage units include, without limitation, a floppy disk, a magnetic tape, an optical disk, a flash memory device, or the like. Storage devices <NUM> and <NUM> may also include other similar structures or devices for allowing computer software, data, or other computer-readable instructions to be loaded into computing system <NUM>. For example, storage devices <NUM> and <NUM> may be configured to read and write software, data, or other computer-readable information. Storage devices <NUM> and <NUM> may be a part of computing system <NUM> or may be separate devices accessed through other interface systems.

Many other devices or subsystems may be connected to computing system <NUM>. Conversely, all of the components and devices illustrated in <FIG> need not be present to practice the embodiments described and/or illustrated herein. The devices and subsystems referenced above may also be interconnected in different ways from those shown in <FIG>. Computing system <NUM> may also employ any number of software, firmware, and/or hardware configurations. For example, one or more of the example embodiments disclosed herein may be encoded as a computer program (also referred to as computer software, software applications, computer-readable instructions, or computer control logic) on a computer-readable medium. The term "computer-readable medium" generally refers to any form of device, carrier, or medium capable of storing or carrying computer-readable instructions. Examples of computer-readable media include, without limitation, transitory media including transmission-type media, such as carrier waves, and non-transitory-type media, such as magnetic-storage media (e.g., hard disk drives and floppy disks), optical-storage media (e.g., Compact Disks (CDs) and Digital Video Disks (DVDs)), electronic-storage media (e.g., solid-state drives and flash media), and other distribution systems. Combinations of the above may also be included within the scope of such computer-readable media.

Further examples of feature combinations taught by the present disclosure are set out in the following numbered examples.

Example <NUM>. A method comprising: receiving, at a source node, a request to discover a plurality of network paths that each lead from the source node to a destination node; and simultaneously discovering the plurality of network paths that lead from the source node to the destination node by: identifying each next hop that resides between the source node and the destination node; sending, from the source node to each next hop, a path-request probe that prompts the next hop to: determine each next-closest hop that resides between the next hop and the destination node; and return, to the source node, a path-response probe that identifies the next-closest hops as residing between the next hop and the destination node; receiving, at the source node, the path-response probes from the next hops; determining, at the source node based at least in part on the path-response probes, that one or more of the plurality of network paths include: the next hops that reside between the source node and the destination node; and the next-closest hops that reside between the next hops and the destination node; and iteratively discovering any subsequent hops that reside between the next-closest hops and the destination node by sending a subsequent path-request probe to each next-closest hop.

Example <NUM>. The method of example <NUM>, wherein receiving the request to discover the plurality of network paths comprises receiving a request to discover each equal-cost network path between the source node and the destination node.

Example <NUM>. The method of example <NUM> or <NUM>, wherein receiving the request to discover the plurality of network paths comprises receiving a request to discover each network path between the source node and the destination node for a packet with at least one particular characteristic.

Example <NUM>. The method of any of examples <NUM>-<NUM>, wherein receiving the request to discover the plurality of network paths comprises receiving the request from a traceroute application running within the source node.

Example <NUM>. The method of example <NUM>, wherein identifying each next hop that resides between the source node and the destination node comprises sending an initial path-request probe from the traceroute application to a network stack maintained by the source node.

Example <NUM>. The method of any of examples <NUM>-<NUM>, wherein the path-request probe prompts the next hop to determine each next-closest hop that resides between the next hop and the destination node by directing the next hop to identify, within a routing table of the next hop, an Internet protocol address of each next-closest hop based at least in part on an Internet protocol address of the destination node.

Example <NUM>. The method of example <NUM>, wherein the path-request probe prompts the next hop to return the path-response probe that identifies the next-closest hops by directing the next hop to list the internet protocol address of each next-closest hop within a type-length-value field of the path-response probe.

Example <NUM>. The method of any of examples <NUM>-<NUM>, wherein sending the subsequent path-request probe to the next-closest hop comprises: including, within the subsequent path-request probe, a network address of the next-closest hop; sending the path-request probe to a next hop that resides between the source node and the next-closest hop; determining, by the next hop, that the next hop is capable of forwarding the subsequent path-request probe to the network address of the next-closest hop; and forwarding, by the next hop, the subsequent path-request probe to the network address of the next-closest hop.

Example <NUM>. The method of any of examples <NUM>-<NUM>, wherein iteratively discovering the subsequent hops that reside between the next-closest hops and the destination node comprises sending subsequent path-request probes in response to one or more subsequent path-response probes received at the source node until receiving at least one final path-response probe from the destination node.

Example <NUM>. The method of any of examples <NUM>-<NUM>, further comprising enabling an application that initiated the request to discover the plurality of network paths to detect a malfunction within at least one node within the plurality of network paths by providing, to the application, a network path map that identifies nodes within each of the plurality of network paths.

Example <NUM>. A system comprising: a request module, stored in memory, that receives, at a source node, a request to discover a plurality of network paths that each lead from the source node to a destination node; a discovery module, stored in memory, that simultaneously discovers the plurality of network paths that lead from the source node to the destination node by: identifying each next hop that resides between the source node and the destination node; sending, from the source node to each next hop, a path-request probe that prompts the next hop to: determine each next-closest hop that resides between the next hop and the destination node; and return, to the source node, a path-response probe that identifies the next-closest hops as residing between the next hop and the destination node; receiving, at the source node, the path-response probes from the next hops; determining, at the source node based at least in part on the path-response probes, that one or more of the plurality of network paths include: the next hops that reside between the source node and the destination node; and the next-closest hops that reside between the next hops and the destination node; and iteratively discovering any subsequent hops that reside between the next-closest hops and the destination node by sending a subsequent path-request probe to each next-closest hop; and at least one hardware processor configured to execute the request module and the discovery module.

Example <NUM>. The system of example <NUM>, wherein the request module receives a request to discover each equal-cost network path between the source node and the destination node.

Example <NUM>. The system of example <NUM> or <NUM>, wherein the request module receives a request to discover each network path between the source node and the destination node for a packet with at least one particular characteristic.

Example <NUM>. The system of any of examples <NUM>-<NUM>, wherein the request module receives the request from a traceroute application running within the source node.

Example <NUM>. The system of example <NUM>, wherein the discovery module identifies each next hop that resides between the source node and the destination node by sending an initial path-request probe from the traceroute application to a network stack maintained by the source node.

Example <NUM>. The system of any of examples <NUM>-<NUM>, wherein the path-request probe prompts the next hop to determine each next-closest hop that resides between the next hop and the destination node by directing the next hop to identify, within a routing table of the next hop, an Internet protocol address of each next-closest hop based at least in part on an Internet protocol address of the destination node.

Example <NUM>. The system of example <NUM>, wherein the path-request probe prompts the next hop to return the path-response probe that identifies the next-closest hops by directing the next hop to list the internet protocol address of each next-closest hop within a type-length-value field of the path-response probe.

Example <NUM>. The system of any of examples <NUM>-<NUM>, wherein the discovery module sends the subsequent path-request probe to the next-closest hop by: including, within the subsequent path-request probe, a network address of the next-closest hop; and sending the path-request probe to a next hop that resides between the source node and the next-closest hop, wherein the next hop: determines that the next hop is capable of forwarding the subsequent path-request probe to the network address of the next-closest hop; and forwards the subsequent path-request probe to the network address of the next-closest hop.

Example <NUM>. The system of any of examples <NUM>-<NUM>, wherein the discovery module iteratively discovers the subsequent hops that reside between the next-closest hops and the destination node by sending subsequent path-request probes in response to one or more subsequent path-response probes received at the source node until receiving at least one final path-response probe from the destination node.

Example <NUM>. An apparatus comprising: at least one storage device that stores information that identifies next hops of a source node within a network; and at least one physical processing device communicatively coupled to the storage device at the source node, wherein the physical processing device: receives, at the source node, a request to discover a plurality of network paths that each lead from the source node to a destination node; and simultaneously discovers the plurality of network paths that lead from the source node to the destination node by: identifying, based at least in part on the information stored in the storage device, each next hop that resides between the source node and the destination node; sending, from the source node to each next hop, a path-request probe that prompts the next hop to: determine each next-closest hop that resides between the next hop and the destination node; and return, to the source node, a path-response probe that identifies the next-closest hops as residing between the next hop and the destination node; receives, at the source node, the path-response probes from the next hops; determines, at the source node based at least in part on the path-response probes, that one or more of the plurality of network paths include: the next hops that reside between the source node and the destination node; and the next-closest hops that reside between the next hops and the destination node; and iteratively discovers any subsequent hops that reside between the next-closest hops and the destination node by sending a subsequent path-request probe to each next-closest hop.

While the foregoing disclosure sets forth various embodiments using specific block diagrams, flowcharts, and examples, each block diagram component, flowchart step, operation, and/or component described and/or illustrated herein may be implemented, individually and/or collectively, using a wide range of hardware, software, or firmware (or any combination thereof) configurations. In addition, any disclosure of components contained within other components should be considered examples since many other architectures can be implemented to achieve the same functionality.

In some examples, all or a portion of system <NUM> in <FIG> may represent portions of a cloud-computing or network-based environment. Cloud-computing and network-based environments may provide various services and applications via the Internet. These cloud-computing and network-based services (e.g., software as a service, platform as a service, infrastructure as a service, etc.) may be accessible through a web browser or other remote interface. Various functions described herein may also provide network switching capabilities, gateway access capabilities, network security functions, content caching and delivery services for a network, network control services, and/or and other networking functionality.

In addition, one or more of the modules described herein may transform data, physical devices, and/or representations of physical devices from one form to another. Additionally or alternatively, one or more of the modules recited herein may transform a processor, volatile memory, non-volatile memory, and/or any other portion of a physical computing device from one form to another by executing on the computing device, storing data on the computing device, and/or otherwise interacting with the computing device.

The process parameters and sequence of the steps described and/or illustrated herein are given by way of example only and can be varied as desired.

The preceding description has been provided to enable others skilled in the art to best utilize various aspects of the examples disclosed herein. This description is not intended to be exhaustive or to be limited to any precise form disclosed. Many modifications and variations are possible. The embodiments disclosed herein should be considered in all respects illustrative and not restrictive. Reference should be made to the appended claims in determining the scope of the instant disclosure.

Unless otherwise noted, the terms "connected to" and "coupled to" (and their derivatives), as used in the specification and claims, are to be construed as permitting both direct and indirect (i.e., via other elements or components) connection. In addition, the terms "a" or "an," as used in the specification and claims, are to be construed as meaning "at least one of. " Finally, for ease of use, the terms "including" and "having" (and their derivatives), as used in the specification and claims, are interchangeable with and have the same meaning as the word "comprising.

Claim 1:
A method comprising:
receiving, at a source node, a request to discover a plurality of network paths that each lead from the source node to a destination node; and
simultaneously discovering the plurality of network paths that lead from the source node to the destination node by:
identifying each next hop that resides between the source node and the destination node;
sending, from the source node to each next hop, a path-request probe that prompts the next hop to:
determine each next-closest hop that resides between the next hop and the destination node; and
return, to the source node, a path-response probe that identifies the next-closest hops as residing between the next hop and the destination node;
receiving, at the source node, the path-response probes from the next hops;
determining, at the source node based at least in part on the path-response probes, that one or more of the plurality of network paths include:
the next hops that reside between the source node and the destination node; and
the next-closest hops that reside between the next hops and the destination node; and
iteratively discovering any subsequent hops that reside between the next-closest hops and the destination node by sending a subsequent path-request probe to each next-closest hop.