Patent Description:
The terms wide area network (WAN) and local area network (LAN) identify communications networks of different geographic scope. For a LAN, the geographic area can range from a residence or office to a university campus. For a WAN, the geographic area can be defined with respect to a LAN - greater than the area of a LAN. In the context of telecommunications, a circuit refers to a discrete path that carries a signal through a network between two remote locations. A circuit through a WAN can be a physical circuit or a virtual/logical circuit. A physical WAN circuit refers to a fixed, physical path through a network. A dedicated or leased line arrangement uses a physical WAN circuit. A logical WAN circuit refers to a path between endpoints that appears fixed but is one of multiple paths through the WAN that can be arranged. A logical circuit is typically implemented according to a datalink and/or network layer protocol, although a transport layer protocol (e.g., transmission control protocol (TCP)) can support a logical circuit.

The Software-defined Network (SDN) paradigm decouples a network management control plane from the data plane. A SDN controller that implements the control plane imposes rules on switches and routers (physical or virtual) that handle Internet Protocol (IP) packet forwarding in the data plane. The limitations of managing traffic traversing a WAN invited application of the SDN paradigm in WANs.

<CIT> discloses a communication system that allocates uplink transmit power to a user equipment based on a fractional power control scheme and on a path loss threshold. In another embodiment, since the cell-edge users are also likely to be power limited, the communication system may implement a minimized uplink transmission bandwidth resource allocation scheme that may work with the fractional power control scheme to achieve a level of performance desired for uplink transmissions in 3GPP and 3GPP2 Evolution communication systems.

Embodiments of the disclosure may be better understood by referencing the accompanying drawings.

The description that follows includes example systems, methods, techniques, and program flows that embody aspects of the disclosure. However, it is understood that this disclosure may be practiced without these specific details. For instance, this disclosure refers to scoring a path based on circuit data in illustrative examples. Data used for scoring a path will depend upon configuration of the measuring network devices. Aspects of this disclosure can also be applied to tunnels provisioned on a circuit. In other instances, well-known instruction instances, protocols, structures and techniques have not been shown in detail in order not to obfuscate the description. Generally, the method described relates to a computer-implemented method.

A network path scoring system is disclosed herein that scores "health" of network paths in terms of packet loss. The system scores health of a network path based on packet loss of the network path, bandwidth capacity ("bandwidth") of a corresponding SD-WAN circuit ("network circuit" or "circuit"), and bandwidth utilization ("load") of the circuit. The scoring is done for the ingress and egress packet loss and occurs in nearly real-time to aid with detection of network problems, including transient or ephemeral problems which can impact application performance and possibly violate a service level agreement.

The scoring uses a "dynamic packet loss threshold" that is based on benchmarks of "good" packet loss behavior of network paths associated with circuits of different bandwidths and recent behavior of the path being scored. The observations for good packet loss behavior are bucketized by corresponding circuit load. For the path being scored, observations are also bucketized and aggregated into a moving average per load bucket. The moving averages represent recent behavior of the path by load bucket. The scoring system scores a path as a function of the current time interval packet loss of the network path being scored and the dynamic packet loss threshold of the current time interval. The dynamic packet loss threshold of the current time interval is a function of a good packet loss benchmark and the packet loss moving average for the load of the current time interval.

<FIG> depicts a diagram of a network appliance scoring a network path of a software-defined wide area network in nearly real-time based on network path packet loss and a good packet loss behavior benchmark. A network path may traverse circuits between customer edge devices at different sites and provider edge devices and a multi-protocol label switching underlay of a provider(s) or even different underlays of different providers. A network path may be a tunnel provisioned between the endpoints. A network path may be a point-to-point or point-to-multi-point circuit between sites. Regardless of the particular nodes and infrastructure being traversed, the communication quality of the network path is measured based on probes transmitted between the endpoints. Bandwidth utilization is determined with respect to bandwidth capacity as defined at the endpoint devices. Despite the myriad incarnations of a network path, the bandwidth capacity is typically expressed as a setting or configuration of a circuit corresponding to a network path. Due to the multitude of connection options, layouts/configurations (e.g., overlay, underlay, etc.), and technologies in network communications, this example illustration illustrates a single, relatively simple scenario that includes three customer edge devices <NUM>, <NUM>, <NUM>. The edge device <NUM> is at a data center hosted on a network <NUM>, which may be on-premise or off-premise data center. The edge device <NUM> is at a branch office network <NUM> and the edge device <NUM> is at a branch office network <NUM>. The edge device <NUM> is communicatively coupled with the edge device <NUM> via a network path that traverses a network <NUM> that provides a multi-protocol label switching service. The edge device <NUM> connects to the network <NUM> via a circuit <NUM> and the edge device <NUM> connects to the network <NUM> via a circuit <NUM>. The edge device <NUM> is communicatively coupled with the edge device <NUM> via a network path <NUM> (illustrated as a tunnel) provisioned on a circuit <NUM> which traverses a private WAN <NUM>. The edge device <NUM> is communicatively coupled with the edge device <NUM> via a network path which traverses a public WAN <NUM> along a direct internet connection <NUM>. The edge device <NUM> connects to the public WAN <NUM> via a circuit <NUM>. The network paths form part of an overlay (e.g., a secure network fabric or virtual private network (VPN)) that securely interconnects geographically disparate sites/networks of an organization.

<FIG> is annotated with a series of letters A - D which represent operational stages of the scoring system. Although these stages are ordered for this example, the stages illustrate one example to aid in understanding this disclosure and should not be used to limit the claims. Subject matter falling within the scope of the claims can vary with respect to the order and some of the operations. In addition, each stage can involve one operation or multiple operations.

At stage A, the edge device <NUM> obtains packet loss data of a network path for a current time interval. A "current" time interval refers to a time interval that has most recently elapsed. A NRT scoring system can be implemented as a network appliance with a hardware or software form factor. In <FIG>, the edge device <NUM> implements the NRT circuit scoring system. The edge devices <NUM>, <NUM>, <NUM> or another system(s) in communication with the edge devices send probes per network path at a time interval smaller than a time interval that will be used to score the network paths (e.g., sending probes at sub-second time intervals for minute granularity scoring). The edge device <NUM> may obtain the packet loss data directly (e.g., compute packet loss based on the probe measurements over the scoring time interval), access the percent packet loss for the scoring time interval from a data structure, interact with another process that computes the packet loss from the probes, etc. The edge device <NUM> updates a visualization of time-series percent packet loss for the network path ("path") with the packet loss data. To score the network path defined by the edge device <NUM>, <NUM> as path endpoints, the edge device obtains packet loss data based on probes transmitted between the edge devices <NUM>, <NUM>.

At stage B, the edge device <NUM> selects a good behavior benchmark for a circuit load bucket of the current time interval from a benchmark table <NUM>. The benchmark table <NUM> is a structure that associates defined good behavior benchmarks with buckets of circuit bandwidth utilization ("circuit load"). The edge device <NUM> computes or retrieves the circuit load over the time interval. Circuit load is determined based on the circuit capacity, which is defined/configured, and amount of received data over the time interval for scoring based on ingress circuit data. For egress scoring, the circuit load will be based on amount of transmitted data. The time granularity for determining circuit load aligns with the scoring time interval. Use of circuit load as a percent of capacity allows scoring to be agnostic with respect to circuit capacity, which allows the scoring to be with respect to the good behavior benchmark. Assuming the network path being scored is the network path <NUM>, then the scoring system would determine ingress load for the circuit <NUM> for ingress scoring and egress load for the circuit <NUM> for egress scoring. The packet loss data would be based on probes transmitted between the path endpoints <NUM>, <NUM>.

<FIG> is a table of example good behavior benchmarks defined across circuit load buckets. Packet loss data for numerous network paths corresponding to circuits of varying capacities are analyzed. This analysis correlates packet loss across circuits of different capacity by circuit loads. Experts and/or people with relevant domain knowledge identify packet loss percentages across the different loads of circuits corresponding to network paths considered as having good performance. As an example, packet loss data can be evaluated for "good" network paths and, for each circuit load bucket, percent packet loss at the 90th percentile (for example) of the packet loss data across the good network paths is chosen as an upper threshold for packet loss. This will eliminate the worst <NUM>% of packet loss from consideration, effectively filtering it out as noise. A table <NUM> of <FIG> includes <NUM> columns from left to right: Load Bucket (%), Lower Threshold, and Upper Thresholds. Each load bucket is associated with lower and upper thresholds. The lower threshold is a fraction of the upper threshold (or the upper threshold is a multiple of the lower threshold). Expert knowledge and/or experience (and possibly user preference) configure the fraction (or multiple) to be applied for setting the lower threshold with respect to the upper threshold. In this illustration, the lower threshold is half the upper threshold. The load buckets in table <NUM> progress in <NUM>% increments from <NUM>% to <NUM>%, then in <NUM>% increments to <NUM>%, <NUM>% increments to <NUM>%, and finally in <NUM>% increments to the <NUM>% load bucket. A few entries from table <NUM> will be described. At the <NUM>% and <NUM>% load buckets, the lower threshold for packet loss is <NUM>% and the upper threshold for packet loss is <NUM>%. At <NUM>% load, the lower threshold for packet loss is <NUM>% and the upper threshold is <NUM>%. At <NUM>% load, the lower threshold is defined as <NUM>% and the upper threshold is defined as <NUM>%. Implementations can vary the bucket sizes and progression from that illustrated. Embodiments do not necessarily maintain both the upper and lower thresholds since the coefficient that relates them is specified and can be used to compute the other. In addition, embodiments can choose the lower thresholds based on the percentiles of packet loss of the good network paths. For example, the lower thresholds can be defined as the <NUM>th percentile of packet loss of the good paths across the different loads.

Returning to <FIG>, the edge device <NUM> determines a dynamic packet loss upper threshold at stage C. The edge device <NUM> calculates the dynamic packet loss upper threshold as a sum of the lower threshold defined for the load of the current interval and the packet loss moving average as updated for the current time interval. The edge device <NUM> maintains a packet loss moving average over time. The dynamic upper threshold is "dynamic" because it adjusts to the dynamic behavior of a network path as represented by the moving average. However, the dynamic upper threshold is capped at the upper threshold. If the dynamic upper threshold exceeds the upper threshold, then the dynamic upper threshold is replaced with the upper threshold. Assuming the current time interval has a load corresponding to the <NUM>% load bucket and the thresholds table <NUM> of <FIG> is being used, the edge device <NUM> computes the dynamic packet loss upper threshold as a sum of the moving average and <NUM>%. Table <NUM> below provides example dynamic packet loss upper thresholds for different example packet loss moving averages.

As shown above, the dynamic packet loss upper threshold when the moving average is <NUM>% is capped at the upper threshold of <NUM>% when the load is <NUM>%. Embodiments can compute the dynamic packet loss upper threshold differently with the constraints that the dynamic upper threshold not exceed the upper threshold and not fall below the lower threshold and that the dynamic upper threshold capture the dynamic behavior of the network path being scored. As an example, the dynamic packet loss upper threshold can be computed as a sum of the lower threshold defined for the current load and a square of the moving average. This is expressed as <MAT>.

At stage D, the edge device <NUM> computes a NRT network path score based on the packet loss of the current time interval and the dynamic packet loss upper threshold. The edge device <NUM> computes the NRT score according to the expression: <MAT> Table <NUM> below indicates the scores that would result from the example dynamic packet loss upper thresholds in Table <NUM>.

The scoring is on a scale of <NUM> - <NUM> with allowance for negative scores depending upon implementation. As shown above in Table <NUM>, the NRT circuit scores get worse with the increasing packet loss at the <NUM>% load.

The edge device <NUM> can then update a visual representation <NUM> of a NRT score series with the path score for the current time interval. The circuit score visual representation <NUM> depicts, at each scored time, a smoothed NRT score as a descending line with the NRT score as a dot. The smoothed score smooths out dips and identifies intervals with sustained low scores. <FIG> and <FIG> are example visual representations of the NRT packet loss based circuit scoring.

<FIG> is a visual representation of the health of a tunnel A in terms of smoothed NRT scores and NRT scores. A visualization or graph <NUM> charts the NRT scores and smoothed NRT scores tunnel A based on ingress packet loss. The tunnel corresponds to a circuit having <NUM> megabits/second (mbps) download/downstream bandwidth and <NUM> mbps upload/upstream bandwidth. The graph <NUM> includes scoring per minute over a <NUM> day period from March <NUM> to March <NUM>. With the graph <NUM>, a performance impacting issue was indicated on March <NUM> that yielded NRT scores of <NUM>. These low scores would have triggered an alarm or notification to facilitate investigation of the transient issue. Another condition or state occurs on March <NUM>. On March 17th, the moving average score didn't fall to <NUM> which indicates that there were enough samples greater than <NUM> interleaved with samples at <NUM> to pull up the moving average score. This is in contrast to March <NUM> where the samples were almost continuously close to <NUM> and the moving average score held close to <NUM>. Depending on the thresholds defined for alerts, the March 17th incident may not raise an alert but the March 15th incident will raise an alert.

<FIG> is a visual representation of the health of a tunnel B in terms of smoothed NRT scores and NRT scores. A visualization or graph <NUM> charts the NRT scores and smoothed NRT scores for the tunnel B based on ingress packet loss data. The tunnel B corresponds to a circuit having <NUM> mbps download bandwidth and <NUM> mbps upload bandwidth. The graph <NUM> includes scoring per minute over a <NUM> day period from August <NUM> to August <NUM>. While there was packet loss experienced on tunnel B, the scores reflect that the packet loss fell within an expected range for the tunnel.

<FIG> is a flowchart of example operations for determining a nearly real-time score for a network path based on packet loss data. The scoring is nearly real-time due to the delay that occurs between an event (elapse of a time interval) and both determining and using (e.g., display, feedback, and/or control) a NRT path score. The operations are presumed to be ongoing since the scoring can be used to identify transient/ephemeral issues that can repeat and impact performance of applications. The example operations are described with reference to a scoring system for consistency with <FIG>. The name chosen for the program code is not to be limiting on the claims. Structure and organization of a program can vary due to platform, programmer/architect preferences, programming language, etc. In addition, names of code units (programs, modules, methods, functions, etc.) can vary for the same reasons and can be arbitrary.

At block <NUM>, a scoring system detects packet loss for a current time interval for a network path. The scoring system can detect the packet loss for the current time interval by various means depending upon the monitoring infrastructure and application organization. A process or thread of the scoring system can detect that packet loss for a time interval is written to a monitored location or receive the percent packet loss over the time interval as calculated by another entity (e.g., program, process, etc.) collecting packet loss data and calculating statistical information. At time interval elapse, the scoring system can query a repository or application for the percent packet loss of the last minute or at a specified time for an identified path.

At block <NUM>, the scoring system determines a percent utilization of circuit bandwidth ("load") of a circuit corresponding to the network path for the current time interval. As with the percent packet loss for a time interval, the scoring system can interact or query another system or application to obtain the current load on the circuit. Implementations of the scoring system may include functionality for computing load on the circuit for the currently elapsed time interval.

At block <NUM>, the scoring system selects a packet loss lower threshold defined for the determined load. The scoring system accesses a structure that associates circuit load buckets with defined packet loss lower thresholds. The structure is not unique to the network path being scored and has been determined based on observations of packet loss of numerous network paths with good application performance. The scoring system will identify a circuit load bucket of the structure that encompasses the determined circuit load and select the packet loss lower threshold defined for the circuit load bucket.

At block <NUM>, the scoring system updates a packet loss moving average for the determined load based on the packet loss of the current time interval. As previously discussed, the scoring system maintains a packet loss moving average for each circuit load bucket indicated in the benchmark structure. The scoring system reads the packet loss moving average of the bucket corresponding to the current circuit load and updates the moving average to incorporate current packet loss (i.e., packet loss of the most recently elapsed time interval). The moving average may be a weighted or smoothed moving average, for example an exponential moving average with a defined alpha (e.g., <NUM> - <NUM>, exclusive of <NUM>).

At block <NUM>, the scoring system computes a sum of the updated packet loss moving average and the packet loss lower threshold. The packet loss lower threshold was selected based on the current circuit load (<NUM>).

At block <NUM>, the scoring system determines whether the computed sum exceeds a packet loss upper threshold defined for the load bucket. The scoring system can retrieve the packet loss upper threshold defined for the bucket of the current circuit load from the benchmark structure. The scoring system can instead use the coefficient that relates the upper and lower thresholds to determine the packet loss upper threshold. If the sum exceeds the packet loss upper threshold, then operational flow continues to block <NUM>. If the sum does not exceed the packet loss upper threshold, then operational flow continues to block <NUM>.

At block <NUM>, the scoring system sets the dynamic packet loss upper threshold as the packet loss upper threshold. The scoring system uses the packet loss upper threshold as a cap to reduce the impact of packet loss that can be considered noise or extreme deviations. Operational flow continues to block <NUM>.

At block <NUM>, the scoring system sets the dynamic packet loss upper threshold as the computed sum of the updated packet loss moving average and the packet loss lower threshold. This allows the circuit to be scored based on a range of acceptable packet loss below an upper threshold that accounts for recent behavior of the network path as represented by the moving average. Operational flow continues to block <NUM>.

At block <NUM>, the scoring system computes a NRT packet loss score for the network path based on the current packet loss and the dynamic packet loss upper threshold. The score corresponds to where current packet loss for the network path falls within a range of acceptable packet loss defined from <NUM> to the dynamic upper threshold. The expression used in <FIG> is one example for computing the score using a linear relationship between packet loss and the score. Embodiments can compute score based on a non-linear relationship.

Embodiments can compare each score against a configurable threshold for alarm or notification. For example, a threshold can be defined at <NUM>. If a score falls below the threshold (or is less than or equal to the threshold), then a notification can be generated (e.g., text message sent, graphical display updated with an indication of a low score, etc.) and/or an alarm triggered. Different thresholds can be set for different levels of urgency.

While the above examples refer to scoring a network path with ingress packet loss data, a network path score can be based on one of the egress and ingress scores (e.g., the lowest of the two scores) or based on both the ingress and egress scores (e.g., a sum of the scores). Accordingly, the example operations of <FIG> would be run/executed with ingress packet loss and the corresponding downstream load and with egress packet loss and the corresponding upstream load. Combining or aggregating the ingress and egress scores may be summing with the use of a <NUM>-<NUM> scale, for example, averaging the scores, etc..

The flowcharts are provided to aid in understanding the illustrations and are not to be used to limit scope of the claims. The flowcharts depict example operations that can vary within the scope of the claims. Additional operations may be performed; fewer operations may be performed; the operations may be performed in parallel; and the operations may be performed in a different order. For example, the operations depicted in <FIG> can cap the moving average instead of the sum of the moving average and the lower threshold. Assuming the lower threshold is half of the upper threshold, the moving average can be capped by the lower threshold and added to the lower threshold. This prevents the sum from exceeding the upper threshold. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by program code. The program code may be provided to a processor of a general purpose computer, special purpose computer, or other programmable machine or apparatus.

As will be appreciated, aspects of the disclosure may be embodied as a system, method or program code/instructions stored in one or more machine-readable media. Accordingly, aspects may take the form of hardware, software (including firmware, resident software, micro-code, etc.), or a combination of software and hardware aspects that may all generally be referred to herein as a "circuit," "module" or "system. " The functionality presented as individual modules/units in the example illustrations can be organized differently in accordance with any one of platform (operating system and/or hardware), application ecosystem, interfaces, programmer preferences, programming language, administrator preferences, etc..

Any combination of one or more machine readable medium(s) may be utilized. The machine readable medium may be a machine readable signal medium or a machine readable storage medium. A machine readable storage medium may be, for example, but not limited to, a system, apparatus, or device, that employs any one of or combination of electronic, magnetic, optical, electromagnetic, infrared, or semiconductor technology to store program code. More specific examples (a non-exhaustive list) of the machine readable storage medium would include the following: a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or Flash memory), a portable compact disc read-only memory (CD-ROM), an optical storage device, a magnetic storage device, or any suitable combination of the foregoing. In the context of this document, a machine readable storage medium may be any tangible medium that can contain, or store a program for use by or in connection with an instruction execution system, apparatus, or device. A machine readable storage medium is not a machine readable signal medium.

A machine readable signal medium may include a propagated data signal with machine readable program code embodied therein, for example, in baseband or as part of a carrier wave. A machine readable signal medium may be any machine readable medium that is not a machine readable storage medium and that can communicate, propagate, or transport a program for use by or in connection with an instruction execution system, apparatus, or device.

Program code embodied on a machine readable medium may be transmitted using any appropriate medium, including but not limited to wireless, wireline, optical fiber cable, RF, etc., or any suitable combination of the foregoing.

The program code/instructions may also be stored in a machine readable medium that can direct a machine to function in a particular manner, such that the instructions stored in the machine readable medium produce an article of manufacture including instructions which implement the function/act specified in the flowchart and/or block diagram block or blocks.

<FIG> depicts an example computer system with a NRT packet loss based score calculator. The computer system includes a processor <NUM> (possibly including multiple processors, multiple cores, multiple nodes, and/or implementing multi-threading, etc.). The computer system includes memory <NUM>. The memory <NUM> may be system memory or any one or more of the above already described possible realizations of machine-readable media. The computer system also includes a bus <NUM> and a network interface <NUM>. The system also includes a NRT packet loss based score calculator <NUM>. The NRT packet loss based score calculator <NUM> scores ingress/egress packet loss based health of a network path at regular time intervals. The NRT packet loss based score calculator <NUM> determines a range of acceptable packet loss for the path based on a dynamic upper threshold (the moving average of the path and a lower threshold for the current circuit load or an upper threshold for the circuit load). The NRT packet loss based score calculator <NUM> scores the path as a function of the current packet loss relative to the dynamic upper threshold. Any one of the previously described functionalities may be partially (or entirely) implemented in hardware and/or on the processor <NUM>. For example, the functionality may be implemented with an application specific integrated circuit, in logic implemented in the processor <NUM>, in a co-processor on a peripheral device or card, etc. Further, realizations may include fewer or additional components not illustrated in <FIG> (e.g., video cards, audio cards, additional network interfaces, peripheral devices, etc.). The processor <NUM> and the network interface <NUM> are coupled to the bus <NUM>. Although illustrated as being coupled to the bus <NUM>, the memory <NUM> may be coupled to the processor <NUM>.

Plural instances may be provided for components, operations or structures described herein as a single instance. Finally, boundaries between various components, operations and data stores are somewhat arbitrary, and particular operations are illustrated in the context of specific illustrative configurations. In general, structures and functionality presented as separate components in the example configurations may be implemented as a combined structure or component.

Claim 1:
A method for detecting network problems comprising:
determining (<NUM>) first packet loss over a first time interval for a first network path;
characterized by further comprising:
determining (<NUM>) a percent utilization of a bandwidth corresponding to the first network path over the first time interval;
based on the first packet loss over the first time interval for the first network path, updating (<NUM>) a packet loss moving average for a first bandwidth utilization bucket that corresponds to the percent bandwidth utilization of the first time interval;
selecting (<NUM>) a packet loss lower threshold defined for the first bandwidth utilization bucket;
determining (<NUM>) a first packet loss upper threshold based, at least in part, on the updated packet loss moving average and the defined packet loss lower threshold; and
scoring (<NUM>) the first network path based, at least in part, on the first packet loss over the first time interval for the first network path and the first packet loss upper threshold.