Root cause analysis of network performance based on exculpation or inculpation sets
View Patent ↗Performance problems or other conditions are analyzed in a system comprising a plurality of endpoint devices and an associated centralized or distributed controller. End-to-end measurements are obtained for respective paths through the network, for example, using communications between the endpoint devices. For a given end-to-end measurement obtained for a particular one of the paths, a value of a performance indicator for the path is determined and the performance indicator value is assigned to each of a plurality of links of the path. The determining and assigning operations are repeated for additional ones of the end-to-end measurements, the links are grouped into one or more exculpation or inculpation sets based on how many times a particular performance indicator value has been assigned to each of the links, and the one or more sets are utilized to determine, for example, the location of a performance problem in the network.
1. A method comprising:
receiving by a system:
i. a first end-to-end measurement of a first path in a network that comprises a first plurality of links, and
ii. a second end-to-end measurement of a second path in the network that comprises a second plurality of links;
processing by the system:
i. the first end-to-end measurement to obtain one of a first value and a second value, and
ii. the second end-to-end measurement to obtain one of the first value and the second value,
iii. wherein the first value is indicative of adequate performance and the second value is indicative of inadequate performance;
assigning by the system:
i. the first value to each link in the first plurality of links after processing the first end-to-end measurement, and
ii. the second value to each link in the second plurality of links, after processing the second end-to-end measurement;
determining, by the system, whether a link common to both the first plurality of links and the second plurality of links satisfies a range [x, y], wherein x and y are real numbers;
obtaining, by the system, a third end-to-end measurement of a third path in the network that includes the link, wherein the third end-to-end measurement is obtained when the link fails to satisfy the range [x, y] after assigning the first value and the second value;
grouping, by the system, the link into at least one of a first group and a second group based on the third end-to-end measurement satisfying the range [x, y]; and
identifying, by the system, a network problem based on at least one of the first group and the second group.
2. The method of claim 1 wherein obtaining the third end-to-end measurement of the third path further comprises the task of:
processing, by the system, the third end-to-end measurement, wherein the first value is obtained as a result of processing the third end-to-end measurement; and
assigning, by the system, the first value to the link after processing the third end-to-end measurement, wherein the link is in:
i. the first path,
ii. the second path, and
iii. the third path.
3. The method of claim 2 wherein the link is grouped into the first group when the link satisfies the range x; and
wherein the link satisfies the range x after assigning the first value to the link based on the third end-to-end measurement.
4. The method of claim 3 wherein grouping the link into the first group indicates that the link has n times as many adequate performance than inadequate performance in end-to-end measurements that include the link, and wherein n is a real number.
5. The method of claim 2 wherein the task of assigning comprises incrementing a counter each time the first value is assigned to the link.
6. The method of claim 5 wherein the link is grouped into the first group when the counter satisfies the range x.
7. The method of claim 1 further comprising:
adjusting the range [x, y]to control whether the link is grouped into at least one of the first group and the second group.
8. The method of claim 1 wherein obtaining the third end-to-end measurement of the third path further comprises the task of:
processing, by the system, the third end-to-end measurement, wherein the second value is obtained as a result of processing the third end-to-end measurement; and
assigning, by the system, the second value to the link after processing the third end-to-end measurement, wherein the link is in:
i. the first path,
ii. the second path, and
iii. the third path.
9. The method of claim 8 wherein the link is grouped into the second group when the link satisfies the range y; and
wherein the link satisfies the range y after assigning the second value to the link based on the third end-to-end measurement.
10. The method of claim 9 wherein grouping the link into the second group indicates that the link has n times as many inadequate performance than adequate performance in end-to-end measurements that include the link, and wherein n is a real number.
11. The method of claim 8 wherein the task of assigning comprises incrementing a counter each time the second value is assigned to the link.
12. The method of claim 11 wherein the link is grouped into the second group when the counter satisfies the range y.
13. The method of claim 8 further comprising:
adjusting the range [x, y]before processing the second value based on the third end-to-end measurement, wherein the link is grouped into the second group after:
i. adjusting the range [x, y], and
ii. assigning the second value to the link based on the third end-to-end measurement.
14. The method of claim 1 , wherein the network problem is identified by the system based on a complement of the first group.
15. The method of claim 1 , wherein the network problem is identified by the system based on a complement of the second group.
16. The method of claim 1 , wherein the network problem is identified by the system based on a combination of the second group and a complement of the first group.
17. The method of claim 1 , wherein the network problem is identified by the system based on a union of the first group and the second group.
18. The method of claim 1 wherein the first end-to-end measurement, the second end-to-end measurement, and the third end-to-end measurement are obtained from Voice over Internet Protocol (VOIP) communications between endpoint devices in the network.
19. A method comprising:
collecting, by a system, end-to-end measurements for a plurality of paths that comprises one or more links j;
computing, by the system, a ratio r j =s j /f j for the one or more links j, wherein:
i. s j is the number of end-to-end measurements that have adequate performance, and
ii. f j is the number of end-to-end measurements that have inadequate performance;
establishing, by the system, a range [x, y] for collecting end-to-end measurements, wherein:
i. the one or more links j have inadequate performance when r j =x, and
ii. the one or more links j have adequate performance when r j =y; and
identifying, by the system, a network problem based on the ratio r j =s j /f j ;
wherein j, s j , and f j are positive integers; and
wherein r j , x, and v are real numbers.
20. The method of claim 19 wherein the system ceases to collect end-to-end measurements when r j =x.
21. The method of claim 19 wherein the system ceases to collect end-to-end measurements when r j =y.