Method and apparatus for automatic determination of performance problem locations in a network
View Patent ↗A network monitoring and analysis system is configured to include a root cause analysis function that permits the automatic determination of performance problem locations in a network of a communication system comprising a plurality of endpoint devices. Test communications are generated in the system in accordance with a selected pattern, which may be based on a flow matrix, and end-to-end path measurement data is collected utilizing the generated test communications. The end-to-end path measurement data is transformed to produce a plurality of performance indicators comprising a performance indicator for each of a plurality of non-end-to-end paths defined at least in part by the selected pattern.
1. A method for determining the location of a performance problem in a network-based communication system comprising a plurality of endpoint devices, the method comprising the steps of:
generating test communications in the system in accordance with a selected pattern;
collecting end-to-end path measurement data utilizing the generated test communications; and
transforming the end-to-end path measurement data to produce a plurality of performance indicators comprising a performance indicator for each of a plurality of non-end-to-end paths defined at least in part by the selected pattern;
wherein the selected pattern is determined at least in part utilizing a flow matrix selection algorithm; and
wherein the flow matrix selection algorithm maintains a list of end-to-end paths and processes said list such that a plurality of non-end-to-end paths for which performance indicators can be generated are determined.
2. The method of claim 1 wherein a given one of the test communications is directed between a first one of the endpoint devices and a second one of the endpoint devices.
3. A method for determining the location of a performance problem in a network-based communication system comprising a plurality of endpoint devices, the method comprising the steps of:
generating test communications in the system in accordance with a selected pattern;
collecting end-to-end path measurement data utilizing the generated test communications; and
transforming the end-to-end path measurement data to produce a plurality of performance indicators comprising a performance indicator for each of a plurality of non-end-to-end paths defined at least in part by the selected pattern;
wherein for a given time interval the collected end-to-end path measurement data is characterized by the equation:
y=Ax
where y is a vector of end-to-end path measurements, A is a flow matrix defining the selected pattern, and x is a vector of performance indicators.
4. The method of claim 3 wherein the transforming step comprises utilizing y and A to solve the equation for x.
5. The method of claim 1 further comprising repeating the generating, collecting and transforming steps for each of a plurality of time intervals.
6. The method of claim 5 wherein the end-to-end path measurement data corresponding to the one or more test communications generated for an ith time interval t i is of the form:
Y i =A i x i
where y i is a vector of end-to-end path measurements collected for the ith time interval, A i is a flow matrix defining the selected pattern for the ith time interval, and x i is a vector of performance indicators for the ith time interval.
7. The method of claim 1 wherein at least one of the performance indicators comprises a binary indicator, the binary indicator taking on a first value to indicate that a corresponding link is not associated with a performance problem, and taking on a second value to indicate that the corresponding link is associated with a performance problem.
8. The method of claim 1 wherein a network of the network-based communication system has a topology characterized by a connected network topology graph G=(D, L) where D is a set of nodes and L is a set of links, and where a given path in G comprises a sequence of links from the set L.
9. The method of claim 8 wherein a node in G having an endpoint device associated therewith is designated as a leaf, and a set E⊂D denotes the set of leaves in G, and further wherein a path in G that lies between leaves comprises an end-to-end path, and a set P for a given G and E denotes the set of all end-to-end paths in G between endpoint devices in E.
10. A method for determining the location of a performance problem in a network-based communication system comprising a plurality of endpoint devices, the method comprising the steps of:
generating test communications in the system in accordance with a selected pattern;
collecting end-to-end path measurement data utilizing the generated test communications; and
transforming the end-to-end path measurement data to produce a plurality of performance indicators comprising a performance indicator for each of a plurality of non-end-to-end paths defined at least in part by the selected pattern;
wherein the selected pattern is defined by a flow matrix having rows representing end-to-end paths for which measurement data is collected in the collecting step, and columns representing single-link or multiple-link non-end-to-end paths for which performance indicators are determined in the transforming step.
11. The method of claim 10 wherein the flow matrix comprises an n×m matrix wherein for 0<i≦n and 0<j≦m, m i,j denotes the number of times the end-to-end path in row i traverses the non-end-to-end path in column j.
12. The method of claim 10 wherein the flow matrix comprises a singular matrix.
13. The method of claim 10 wherein the flow matrix comprises a non-singular matrix.
14. The method of claim 1 wherein the selected pattern is determined at least in part based on a reduced network topology generated by applying a network topology reduction process to a graph representative of a topology of a network of the network-based communication system, the network topology reduction process determining one or more non-end-to-end paths within the network which carry the same traffic flow.
15. A method for determining the location of a performance problem in a network-based communication system comprising a plurality of endpoint devices, the method comprising the steps of:
generating test communications in the system in accordance with a selected pattern;
collecting end-to-end path measurement data utilizing the generated test communications; and
transforming the end-to-end path measurement data to produce a plurality of performance indicators comprising a performance indicator for each of a plurality of non-end-to-end paths defined at least in part by the selected pattern;
wherein the selected pattern is determined at least in part utilizing a flow matrix selection algorithm;
wherein the flow matrix selection algorithm is configurable to accept one or more constraints on selection of particular paths in generating a given flow matrix.
16. An apparatus for use in determining the location of a performance problem in a network-based communication system, the system comprising a plurality of endpoint devices, the apparatus comprising:
a controller comprising a processor coupled to a memory; the controller being associated with one or more of the endpoint devices, and being operative to control: (i) generation of test communications in the system in accordance with a selected pattern, (ii) collection of end-to-end path measurement data utilizing the generated test communications, and (iii) transformation of the end-to-end path measurement data to produce a plurality of performance indicators comprising a performance indicator for each of a plurality of non-end-to-end paths defined at least in part by the selected pattern;
wherein the selected pattern is determined at least in part utilizing a flow matrix selection algorithm; and
wherein the flow matrix selection algorithm maintains a list of end-to-end paths and processes said list such that a plurality of non-end-to-end paths for which performance indicators can be generated are determined.
17. The apparatus of claim 16 wherein the controller comprises a centralized controller which communicates with the plurality of endpoint devices over a network.
18. The apparatus of claim 16 wherein the controller comprises a distributed controller which is implemented at least in part utilizing one or more of the endpoint devices.
19. An article of manufacture comprising a machine-readable storage medium containing software code for use in determining the location of a performance problem in a network-based communication system comprising a plurality of endpoint devices, wherein the software code when executed implements the steps of:
generating test communications in the system in accordance with a selected pattern;
collecting end-to-end path measurement data utilizing the generated test communications; and
transforming the end-to-end path measurement data to produce a plurality of performance indicators comprising a performance indicator for each of a plurality of non-end-to-end paths defined at least in part by the selected pattern;
wherein the selected pattern is determined at least in part utilizing a flow matrix selection algorithm; and
wherein the flow matrix selection algorithm maintains a list of end-to-end paths and processes said list such that a plurality of non-end-to-end paths for which performance indicators can be generated are determined.