Performing network topology traces with minimal data collection

In one embodiment, a device in a network receives privatized network trace data that comprises round trip time information for hops along a communication path. The device groups the trace data into a plurality of network segments based on the round trip time information. The device calculates a segment trip time metric for one or more of the network segments based on the round trip time information associated with the one or more network segments.

TECHNICAL FIELD

The present disclosure relates generally to computer networks, and, more particularly, to performing network topology traces with minimal data collection.

BACKGROUND

Generally, network topology traces allow network administrators and other interested parties to obtain information about the path taken when data is communicated in a network. For example, such a trace may identify the individual devices and hops taken along the communication path, as well as performance metrics for each of the hops in terms of packet loss, transit time, etc. This information can then be aggregated and analyzed, to detect potential network problems.

While network topology traces can provide useful information to an interested party, there are many situations in which the operator of a network may not wish to reveal too much information regarding the inner workings of the operator's network. For example, a given service provider may not wish to reveal the network addresses of the various hops along the communication path being traced. In other words, a spectrum of trace information exists that spans from providing all available information in the trace results to blocking trace responses at the edge of the local network, entirely.

DESCRIPTION OF EXAMPLE EMBODIMENTS

Overview

According to one or more embodiments of the disclosure, a device in a network receives privatized network trace data that comprises round trip time information for hops along a communication path. The device groups the trace data into a plurality of network segments based on the round trip time information. The device calculates a segment trip time metric for one or more of the network segments based on the round trip time information associated with the one or more network segments.

DESCRIPTION

2.) Site Type B: a site connected to the network using two MPLS VPN links (e.g., from different Service Providers), with potentially a backup link (e.g., a 3G/4G/LTE connection). A site of type B may itself be of different types:

2a.) Site Type B1: a site connected to the network using two MPLS VPN links (e.g., from different Service Providers), with potentially a backup link (e.g., a 3G/4G/LTE connection).

2c.) Site Type B3: a site connected to the network using two links connected to the public Internet, with potentially a backup link (e.g., a 3G/4G/LTE connection).

Generally, trace analysis process248may be configured to analyze trace data that results from conducting a network trace. In some embodiments, trace analysis process248may be further configured to initiate and perform the actual network trace. In other embodiments, trace analysis process248may receive and analyze the trace data from another element or process that performs the actual trace.

In various embodiments, trace analysis process248may be operable to analyze trace results that include only minimal information regarding the network path. Notably, trace analysis process248may be configured to analyze and compute metrics for trace information that is limited to only round trip time (RTT) information.

In some embodiments, trace analysis process248may utilize machine learning techniques, to determine characteristics of the communication path and/or determine whether to initiate additional traces of the path (e.g., to assess whether the current trace results are of sufficient accuracy or sufficient detail, etc.). In general, machine learning is concerned with the design and the development of techniques that take as input empirical data (such as network statistics and performance indicators), and recognize complex patterns in these data. One very common pattern among machine learning techniques is the use of an underlying model M, whose parameters are optimized for minimizing the cost function associated to M, given the input data. For instance, in the context of classification, the model M may be a straight line that separates the data into two classes (e.g., labels) such that M=a*x+b*y+c and the cost function would be the number of misclassified points. The learning process then operates by adjusting the parameters a,b,c such that the number of misclassified points is minimal. After this optimization phase (or learning phase), the model M can be used very easily to classify new data points. Often, M is a statistical model, and the cost function is inversely proportional to the likelihood of M, given the input data.

Computational entities that rely on one or more machine learning techniques to perform a task for which they have not been explicitly programmed to perform are typically referred to as learning machines. In particular, learning machines are capable of adjusting their behavior to their environment. For example, a learning machine may dynamically make future predictions based on current or prior network measurements, may make control decisions based on the effects of prior control commands, etc.

For purposes of determining characteristics of a network path, a learning machine may construct a model of observed characteristics and compare newly observed information to the model. Example machine learning techniques that may be used to construct and analyze such a model may include, but are not limited to, nearest neighbor (NN) techniques (e.g., k-NN models, replicator NN models, etc.), statistical techniques (e.g., Bayesian networks, etc.), clustering techniques (e.g., k-means, etc.), neural networks (e.g., reservoir networks, artificial neural networks, etc.), support vector machines (SVMs), or the like.

One class of machine learning techniques that may be of particular use in the context of analyzing network trace data is clustering. Generally speaking, clustering is a family of techniques that seek to group data according to some typically predefined notion of similarity. For instance, clustering is a very popular technique used in recommender systems for grouping objects that are similar in terms of people's taste (e.g., because you watched X, you may be interested in Y, etc.). Typical clustering algorithms are k-means, density based spatial clustering of applications with noise (DBSCAN) and mean-shift, where a distance to a cluster is computed with the hope of reflecting a degree of anomaly (e.g., using a Euclidian distance and a cluster based local outlier factor that takes into account the cluster density).

Replicator techniques may also be used for purposes of analyzing network trace data. Such techniques generally attempt to replicate an input in an unsupervised manner by projecting the data into a smaller space (e.g., compressing the space, thus performing some dimensionality reduction) and then reconstructing the original input, with the objective of keeping the “normal” pattern in the low dimensional space. Example techniques that fall into this category include principal component analysis (PCA) (e.g., for linear models), multi-layer perceptron (MLP) ANNs (e.g., for non-linear models), and replicating reservoir networks (e.g., for non-linear models, typically for time series).

Performing Network Topology Traces with Minimal Data Collection

The techniques herein facilitate network troubleshooting through the analysis of trace data that includes only minimal information regarding the communication path. In some aspects, the techniques herein may be used to provide a network administrator or other interested party a rough estimate of where a problem may exist along the communication path, while not requiring network providers to return trace results that include sensitive information regarding the network. For example, the techniques herein may be used to determine whether a problem exists in the customer network, in the transport/backbone network, or in the network of the remote/cloud destination.

Specifically, according to one or more embodiments of the disclosure as described in detail below, a device in a network receives privatized network trace data that comprises round trip time information for hops along a communication path. The device groups the trace data into a plurality of network segments based on the round trip time information. The device calculates a segment trip time metric for one or more of the network segments based on the round trip time information associated with the one or more network segments.

Illustratively, the techniques described herein may be performed by hardware, software, and/or firmware, such as in accordance with the trace analysis process248, which may contain computer executable instructions executed by the processor220(or independent processor of interfaces210) to perform functions relating to the techniques described herein. For example, the techniques herein may be treated as extensions to conventional protocols, such as the various networking protocols or wireless communication protocols, and as such, may be processed by similar components understood in the art that execute those protocols, accordingly.

Operationally, a device in a network may obtain trace data for a communication path in any number of ways. One such example of a network trace is shown inFIG. 3, according to some embodiments. As shown, assume that a device200is connected to a remote system via a media socket302. For example, device200may be connected to a teleconference or other multimedia session via a Real Time Protocol (RTP) or Secure RTP (SRTP) connection using media socket302. Along the communication path for the media session may be any number of nodes, such as nodes A and B, also shown inFIG. 3.

Assume, for purposes of illustration, that an interested party/system wishes to obtain information regarding the communication path traversed by the packets associated with media socket302. However, as would be appreciated, many operating system-based traceroute routines would traverse a different path than that of the UDP packets associated with media socket302. Various techniques may be used to perform a trace of the actual communication path. For example, the Internet Engineering Task Force (IETF) draft entitled, “STUN Traceroute,” by Martinsen et al., which is hereby incorporated by reference, describes a traceroute mechanism that uses STUN packets and returned Internet Control Message Protocol (ICMP) replies, to perform a trace of an RTP or SRTP communication path.

As shown, device200may send probe packets304along the communication path of interest via media socket302. In various embodiments, device200may set and vary time to live (TTL) parameters in probe packets304, to garner information about the communication path. Notably, TTL parameters may define when a packet is considered “expired” by the receiving device. For example, node B along the communication path of interest may determine that a particular probe packet304is expired, based on the TTL of the packet.

When a device along the path determines that a packet is expired, it may notify the sender as to the expiration. For example, as shown, node B may send an ICMP reply306back to ICMP socket308of device200. In this way, the trace process can monitor sockets302and308, e.g., by using select( ) or poll( ) socket calls, to monitor the trace. By varying the TTL values of the probe packets306, device200will receive ICMP responses from different nodes along the path, thereby garnering information about the path of interest. For example, device200may receive an ICMP reply from node A when the TTL of the probe packets is set at a very low value, an ICMP reply from node B when the TTL of the probe packets is slightly increased, etc. Thus, by varying the TTL parameters of the probe packets, device200can obtain trace information from the different hops along the path of interest. In other embodiments, ICMP socket308may be replaced with an error handler that operates in a similar manner.

Referring now toFIG. 4, an example illustration400is shown of a network path divided into segments, based on network trace data. For example, each segment may correspond to different portions of the network path maintained by different network providers. Metrics associated with each segment and each hop can then be analyzed, to identify a source of problems along the path.

When full trace information is available, determining the topology and performance metrics of a path is relatively straightforward. In particular, full trace information may identify the network addresses of the hops along the path, their RTTs, loss metrics, and owner information for the various segments of the path (e.g., by performing a lookup of the IP addresses of the hops).

In some embodiments, a node/hop along a traced path may be configured with privacy controls, to ensure that the node does not reveal too much information about the node or the network itself. In particular, leaking IP addresses can reveal the network topology of an entity that the entity may wish to keep secret. At the most extreme, the entity may block ICMP responses or other messages at the edge of its network, in an effort to prevent trace information from being accessible. However, in various embodiments, the nodes/devices along a path may also be configured to provide privatized network trace data that includes only minimal or reduced trace information (e.g., as opposed to identifying the network addresses of the hops, etc.). In other words, as used herein, privatized network trace data refers to network trace data that withholds certain meta-information via a privacy mechanism, such as not including address information regarding hops along the path.

In situations in which the returned network trace data has been privatized, discerning information about the network path becomes increasingly challenging as the amount of trace information decreases. In turn, this may limit and/or prevent pinpointing a misbehaving hop along the path. However, using the techniques herein, at least some rough analysis and diagnostics can be performed on the minimized trace datasets. For example, the techniques herein may be used to determine roughly whether a source of problems along a path is located at the customer portion of the path, the transit portion of the path, or at the cloud/server portion of the path.

Referring now toFIG. 5, an example simplified procedure for calculating metrics for a network segment is shown, in accordance with various embodiments herein. Procedure500may begin at step505and continue on to step510where, as described in greater detail above, a device in a network may receive privatized network trace data. In other words, in some cases, the received trace data may include a reduced set of information regarding the network path. For example, the privatized network trace data may specifically exclude network address information regarding the hops along the path such as, e.g., public, private, and or local IP addresses. In one embodiment, the privatized network trace data may include only RTT information. In other embodiments, however, the privatized network trace data may include both RTT information, as well as HOP/TTL information.

At step515, the device may group the received trace data into segments based on the RTT information. In one embodiment, the device may use a predefined number of segments to which the trace responses may be associated. For example, the trace information may be grouped into three separate segments, to represent the local network of the client application, the transport network, and the server/cloud network. However, any number of different segments may be used. As noted previously, the trace responses may include only a minimal amount of information, such as the RTTs of the traces. In such cases, the device may sort the responses by RTTs, to group the response into segments. In another embodiment, the device may use a machine learning-based technique, such as classification or clustering, to associate the trace responses with different segments.

At step520, the device may compute one or more metrics for the one or more path segments. In one embodiment, the device may determine a segment trip time (STT) based on the RTTs of the response associated with the segments. For example, the STT for the first segment may be the RTT of the last hop/trace response associated with the segment, the STT for the second segment may be the difference between the RTTs of the last hop/response of the first segment and the second segment, etc. In various embodiments, the segment metric(s) may be used to detect and diagnose problems along the probed path. Procedure500then ends at step525.

Referring now toFIG. 6, an example simplified procedure is illustrated for assessing a network path, in accordance with various embodiments herein. Procedure600may be performed by a device in a network such as, e.g., device200described above. Procedure600may begin at step605and continue on to step610where the device may perform a network trace of a path in the network. Any number of different types of traces may be performed. In one embodiment, the device may perform a STUN-based trace of the path. For example, the device may perform a trace of a network path used by an RTP or SRTP session by sending STUN packets along the path with varying TTLs (or HOP limits if IPv6 is used) and analyze the corresponding ICMP responses.

In various embodiments, the trace data generated by performing the trace may be privatized trace information. In other words, the returned trace data may include only a limited amount of information about the path (e.g., is minimized in some way by the entity in control of that portion of the path). For example, the trace data may specifically exclude address information for a given hop along the path. In a further example, the trace data may also exclude TTL/hop information. In other cases, the returned trace data may only include RTT information, providing only a minimal amount of information regarding the path.

At step615, the device may determine whether the received trace data is acceptable in terms of accuracy. In various embodiments, the device may perform any number of traces along the path, to ensure that the received trace data is accurate. For example, the device may perform n-number of traces in step610and compare the results, to determine whether the results are consistent. In various embodiments, the device may use any or all of the following approaches, to determine whether the trace results are acceptable: statistical analysis (e.g., confidence intervals, etc.), machine learning-based outlier analysis, predefined thresholds (e.g., if the results differ by x %, etc.), or any other technique that may be used to assess whether the results from multiple traces acceptable. If the results are not acceptable, procedure600may return to step610and the traces repeated any number of times. Otherwise, procedure600may continue on to step620.

At step620, the device may determine whether the received trace data contains TTL/hop information. As noted previously, at minimum, the trace data may include RTT information. However, an intermediary approach to protect the privacy of the devices along the path may be to return RTT information with TTL/hop information (e.g., while still excluding network addresses, autonomous system information, etc.). As would be appreciated, the inclusion of TTL/hop information may improve the accuracy of the overall process, but is not a requirement to assess the path. If the received trace data include TTL/hop information, procedure600may continue on to step625. Otherwise, procedure600may proceed to step630.

At step625, the device may determine whether the received RTT and TTL/hop information is in ascending order by RTT. Notably, the RTT for each consecutive node along the path should increase with the hop count (e.g., the RTT to the third node should be greater than that of the second node, etc.). If not, procedure600may return to step610where one or more additional traces are performed. However, if the received information is in the expected order by RTT, procedure600may continue on to step635.

At step630, if the trace data does not include TTL/hop information, the device may sort the trace data by RTTs in ascending order. As noted above with respect to step625, if the received network trace data includes TTL/hop information, the device has information regarding the ordering of the nodes/hops along the path. In turn, the device can use this information to ensure that the RTTs are consistent with this ordering. However, in the case that the trace dataset has been even more privatized/minimized, even this ordering may not be available to the device. In such cases, the device may sort the returned RTT information in ascending order, under the assumption that the next consecutive RTT in the series is associated with the next hop along the path.

At step635, as described in greater detail above, the device may divide the received trace data by assigning the trace results to a plurality of segments. For example, the device may assign the trace results to two or more segments by evenly distributing the trace results, applying a machine learning-based classifier to the set of trace results, or in any other way. As would be appreciated, by assigning even the privatized/minimalized trace data to different segments, this may enable garnering at least a rough estimate of where a problem may exist along the network path.

At step640, as detailed above, the device may calculate an STT or other metric for one or more of the path segments. In doing so, this gives a rough estimate of the time a given trace packet and reply spent on any given segment of the path. In various embodiments, the calculated STT or other metrics may be used to diagnose a cause of delays along the path. In particular, an abnormally high STT may indicate that the node/hop that is the source of the delays is located in the path segment that exhibits the abnormal STT. For example, assume that the path of interest is divided into three segments, to represent the local network of the client application, the transit portion of the path (e.g., as operated by a service provider), and the cloud/server portion of the path. Further, assume that the segment that represents the network of the client/application is exhibiting an abnormally high STT. In such a case, the network administrator may be notified to initiate further analysis of the network (e.g., the device may issue an alert, etc.). Procedure600then ends at step645.

The techniques described herein, therefore, provide network trace analysis techniques for situations in which the returned trace data includes only a reduced amount of information regarding the probed path. In particular, the techniques herein allow for the rough analysis of trace data that has been privatized in some manner such as, e.g., by specifically excluding address information for hops along the traced path.

While there have been shown and described illustrative embodiments that provide for dynamic enabling of routing devices in a shared-media communication network, it is to be understood that various other adaptations and modifications may be made within the spirit and scope of the embodiments herein. For example, the embodiments have been shown and described herein with relation to certain network configurations. However, the embodiments in their broader sense are not as limited, and may, in fact, be used with other types of networks. In addition, while certain protocols are shown, other suitable protocols may be used, accordingly. Further, while certain embodiments herein have been described in conjunction with performing a STUN-based trace, it should be appreciated that the techniques herein may be applied to any other form of network trace and are not limited as such.