US 11,388,073 B1Granted

Estimating end-to-end loss distributions in computer networks

AssigneeAmazon Technologies, Inc.

InventorsFabien Chraim, John William Evans

Life of this patent

Estimating the term…

Loading patent…

Abstract

In computing networks, end-to-end loss distributions are estimated according to the present disclosure. The loss distributions may be calculated based on loss values reported by nodes in the network along an end-to-end communication path, which may be identified by a route tracing process. The loss values for each node in the path for a given time window may be reduced by a rounding process, and the reduced values for adjacent nodes in the path may be iteratively multiplied with one another in a pairwise manner to generate an end-to-end loss value vector, where the resulting product from each iteration may be reduced by the rounding process. A graphical or other representation of the values in the end-to-end loss value vector indicating a distribution of losses experienced along the path may be output via a user interface.

Claims16

Dependent claims

A system comprising:

a network monitoring system coupled to a network comprising a plurality of nodes including end points of an end-to-end communication path, the network monitoring system comprising:
one or more processors, and
one or more non-transitory computer-readable storage media storing instructions executable by the one or more processors to:
receive, from an automated route tracing process, aggregated paths between the end points of the path corresponding to an end-to-end path through the network;
receive, from each node along the path, interface loss values indicating interface losses experienced over time for each connection point of the node;
round the interface loss values for each node in the path according to an adaptive mesh refinement process to generate respective vectors of loss values;
determine a Cartesian product of the respective vectors of loss values of a first pair of adjacent nodes in the path to generate a combined loss vector;
round values in the combined loss vector according to the adaptive mesh refinement process;
iteratively generate subsequent combined loss vectors by stepping pairwise through adjacent nodes along the path, determining Cartesian products for the respective vectors of loss values for each node along the path with a previous combined loss vector for an associated adjacent node along the path, and rounding values in the subsequent combined loss vectors, to generate an end-to-end path loss vector;
generate a graphical representation of the end-to-end path loss vector;
and
output, via a graphical user interface, the generated graphical representation.

9 more elements

A method comprising:

receiving packet loss data for each interface of each node in an end-to-end communication path through a network, the packet loss data including loss values indicating a respective amount of lost packets at each interface of each node in the path;
in a stepwise manner for each node along the path, combining respective node loss vectors of the nodes to generate an end-to-end loss vector, each respective node loss vector indicating a distribution of the loss values received for the respective node;
and
generating an output corresponding to the end-to-end loss vector, the output configured to control a targeted system to perform an action relating to an estimation of a percentage of users or network communication sessions experiencing end-to-end losses along the path,
wherein combining the respective node loss vectors comprises iteratively determining respective Cartesian products of the respective loss vectors or combinations of the respective loss vectors in the stepwise manner, and, in each iteration, rounding loss values in a result of the determined Cartesian product according to an adaptive mesh refinement algorithm.

2 more elements

One or more non-transitory computer-readable storage media storing computer-executable instructions for causing a computing system to perform a method, the method comprising:

receiving packet loss data for each interface of each node in an end-to-end communication path through a network, the packet loss data including loss values indicating a respective amount of lost packets at each interface of each node in the path;
in a stepwise manner for each node along the path:
iteratively combining respective node loss vectors corresponding to the loss values for adjacent nodes in the path to generate a respective combined loss vector, and
rounding the loss values for the respective combined loss vectors, wherein a last respective combined loss vector determined for a last pair of adjacent nodes along the path is rounded to generate an end-to-end path loss vector;
determining an end-to-end path availability by aggregating end-to-end path loss vectors generated over a time window;
and
generating an output corresponding to the end-to-end path availability for transmission to or presentation by a target system,
wherein determining the end-to-end path availability comprises calculating a per-pairing compliance for which loss rate is below a threshold target for all pairings of nodes in the end-to-end path, and wherein the threshold target is based on a Service Level Agreement (SLA) for services provided by the network.

5 more elements

Dependencies are inferred from the claim text.