초록 ▼

A delay measurement technique according to an embodiment according to the present invention is based on the precept, ascertained by the inventors, that a link between network nodes will often contribute to the delay encountered between several different pairs of network nodes. Such a technique ident

A delay measurement technique according to an embodiment according to the present invention is based on the precept, ascertained by the inventors, that a link between network nodes will often contribute to the delay encountered between several different pairs of network nodes. Such a technique identifies the path between each pair of nodes by a list of links that form the path. Paths that are orthogonal are treated as being necessary for describing the delays encountered between nodes, and, once the requisite set of orthogonal paths has been derived, all other paths can be described in terms of one or more of these orthogonal paths. Such a technique also lends itself to matrix representation of the paths, and the use of matrix manipulation techniques in deriving delay and jitter.

대표청구항 ▼

1. A method comprising:identifying a first set of network element pairs from a plurality of network elements, each of said network elements being coupled to another of said network elements by at least one of a plurality of links, by: identifying a first plurality of network element pairs from said

1. A method comprising:identifying a first set of network element pairs from a plurality of network elements, each of said network elements being coupled to another of said network elements by at least one of a plurality of links, by: identifying a first plurality of network element pairs from said network elements, wherein each of said first plurality of network element pairs corresponds to a one of said links, and identifying a network element pair from said network elements, wherein each of a first and a second network element of said network element pair is adjacent to a one of said network elements, a path between a first and a second network element of said network element pair comprises said one of said network elements, and said first set of network element pairs comprises said first plurality of network element pairs and said network element pair. 2. The method of claim 1, further comprising:identifying another network element pair from said network elements, wherein every path between a first network element and a second network element of said another network element pair, if any, comprises a plurality of said network elements. 3. The method of claim 2, further comprising:measuring a measured network performance metric over said first set of network element pairs; and using said measured network performance metric to estimate an estimated network performance metric over said another network element pair. 4. The method of claim 3, whereina second set of network element pairs comprises said another network element pair. 5. The method of claim 4, wherein said using comprises:computing said estimated network performance metric between said first network element and said second network element of said another network element pair. 6. The method of claim 5, further comprising:identifying pairs of said network elements as being in said second set of network element pairs; and identifying pairs of said network elements in said second set of network element pairs as being in said first set of network element pairs. 7. The method of claim 6, further comprising:generating a first matrix using said second set of network element pairs, wherein each row in said first matrix corresponds to a corresponding network element pair in said second set of network element pairs, said first matrix comprises independent rows and non-independent rows, said first set of network element pairs contains independent network element pairs in said second set of network element pairs, and each one of said independent pairs of network element corresponds to a one of said independent rows of said first matrix. 8. The method of claim 7, wherein said measured network performance metric is measured between a first network element and a second network element of each network element pair in said first set of network element pairs.9. The method of claim 7, said method further comprising:computing a number, wherein said number is equal to a rank of said first matrix; determining if a first said number of rows of said first matrix are independent; and if said first said number of said rows of said first matrix are not independent, re-arranging said rows of said first matrix such that said first said number of said rows of said first matrix are independent. 10. The method of claim 9, further comprising: identifying a maximal set of independent rows of said first matrix based on said number.11. The method of claim 9, wherein said rearranging further comprises:re-arranging said pairs of said network elements in said second set of network element pairs such that said correspondence between each row of said first matrix and said corresponding network element pair in said second set of network element pairs is maintained. 12. The method of claim 11, wherein said forming said first set of network element pairs comprises:copying a first said number of pairs of said network elements in said second set of network element pairs into said first set of network element pairs. 13. The method of claim 7, whereinsaid network element pair in said second set of network element pairs is a remaining network element pair in said second set of network element pairs, and said remaining network element pair corresponds to a non-independent row of said first matrix. 14. The method of claim 8, wherein said computing said estimated network performance metric between said first network element and said second network element of said remaining network element pair comprises:forming a second matrix, wherein each row of said second matrix corresponds to a corresponding one of said non-independent rows of said first matrix, and said each row of said second matrix is such that said corresponding one of said non-independent rows of said first matrix can be expressed in terms of said independent rows using said each row of said second matrix; organizing said measured network performance metrics into a vector; and computing said estimated network performance metric between said first network element and said second network element of said remaining network element pair by multiplying said vector by a row of said second matrix corresponding to said remaining network element pair. 15. The method of claim 8, wherein said computing said estimated network performance metric between said first network element and said second network element of said remaining network element pair comprises:creating a vector equivalent to said non-independent row of said first matrix by combining a plurality of said independent rows of said first matrix; and computing said estimated network performance metric by combining a measured network performance metric of each network element pair of said first set of network element pairs corresponding to one of said plurality of said independent rows of said first matrix. 16. A method comprising:identifying a first set of router pairs from a plurality of network elements, each of said network elements being coupled to another of said network elements by at least one of a plurality of links; forming a second set of network element pairs by identifying a first plurality of network element pairs from said first set of router pairs, wherein each of said first plurality of network element pairs corresponds to a one of said links, and identifying a network element pair from said first set of router pairs, wherein each of a first and a second network element of said network element pair is adjacent to a one of said network elements, a path between a first and a second network element of said network element pair comprises said one of said network elements, and said first set of network element pairs comprises said first plurality of network element pairs and said network element pair; and identifying another network element pair from said network elements, wherein every path between a first network element and a second network element of said another network element pair, if any, comprises a plurality of said network elements, and said second set of network element pairs comprises said first set of network element pairs and said another network element pair. 17. The method of claim 16, further comprising:generating a first matrix from said second set of network element pairs, wherein each row in said first matrix corresponds to a corresponding network element pair in said second set of network element pairs. 18. The method of claim 17, further comprising:measuring a measured network performance metric between a first network element and a second network element of each network element pair in said second set of network element pairs. 19. The method of claim 18, further comprising:generating a second matrix from said second set of network element pairs, wherein each row in said second matrix stores a measured network performance metric corresponding to a network element pair in said second set of network element pairs. 20. The method of claim 19, further comprising:computing an estimated network performance metric between a first network element and a second network element of said another network element pair using at least one of said measured network performance metrics. 21. The method of claim 19, wherein said first set of network element pairs is a requirements set.22. The method of claim 21, wherein said second set of network element pairs is a measurements set.23. The method of claim 22, wherein each one of said network elements is a router.24. The method of claim 19, whereinsaid first matrix is a matrix H, and said second matrix is a matrix x. 25. The method of claim 24, further comprising:re-arranging columns of said matrix H such that a column corresponding to a delay through said one of said elements is positioned after all columns corresponding to a delay over said one of said links; and re-arranging components of said matrix x to maintain correspondence between said columns of said matrix H and said components of said matrix x. 26. The method of claim 25, further comprising:re-arranging said matrix H such that said matrix H appears as 27. The method of claim 26, further comprising:constructing a matrix B and a matrix C from said matrix H such that said matrix B appears as ?and said matrix C appears as 28. The method of claim 26, further comprising:computing a matrix product D=BC. 29. The method of claim 28, further comprising:construct a matrix F from said matrix product D. 30. A computer program product encoded in a computer readable media which when executed causes a computer to perform a method comprising:identifying a first set of network element pairs from a plurality of network elements, each of said network elements being coupled to another of said network elements by at least one of a plurality of links, by: identifying a first plurality of network element pairs from said network elements, wherein each of said first plurality of network element pairs corresponds to a one of said links, and identifying a network element pair from said network elements, wherein each of a first and a second network element of said network element pair is adjacent to a one of said network elements, a path between a first and a second network element of said network element pair comprises said one of said network elements, and said first set of network element pairs comprises said first plurality of network element pairs and said network element pair. 31. The computer program product of claim 30, said method further comprising:identifying another network element pair from said network elements, wherein every path between a first network element and a second network element of said another network element pair, if any, comprises a plurality of said network elements. 32. The computer program product of claim 31, said method further comprising:measuring a measured network performance metric over said first set of network element pairs; and using said measured network performance metric to estimate an estimated network performance metric over said another network element pair. 33. The computer program product of claim 32, whereina second set of network element pairs comprises said another network element pair. 34. The computer program product of claim 33, wherein said using comprises:computing said estimated network performance metric between said first network element and said second network element of said another network element pair. 35. The computer program product of claim 34, said method further comprising:identifying pairs of said network elements as being in said second set of network element pairs; and identifying pairs of said network elements in said second set of network element pairs as being in said first set of network element pairs. 36. The computer program product of claim 35, said method further comprising:generating a first matrix using said second set of network element pairs, wherein each row in said first matrix corresponds to a corresponding network element pair in said second set of network element pairs, said first matrix comprises independent rows and non-independent rows, said first set of network element pairs contains independent network element pairs in said second set of network element pairs, and each one of said independent pairs of network element corresponds to a one of said independent rows of said first matrix. 37. The computer program product of claim 36, wherein said measured network performance metric is measured between a first network element and a second network element of each network element pair in said first set of network element pairs.38. The computer program product of claim 36, said method further comprising:computing a number, wherein said number is equal to a rank of said first matrix; determining if a first said number of rows of said first matrix are independent; and if said first said number of said rows of said first matrix are not independent, re-arranging said rows of said first matrix such that said first said number of said rows of said first matrix are independent. 39. The computer program product of claim 38, said method further comprising:identifying a maximal set of independent rows of said first matrix based on said number. 40. The computer program product of claim 38, wherein said rearranging further comprises:re-arranging said pairs of said network elements in said second set of network element pairs such that said correspondence between each row of said first matrix and said corresponding network element pair in said second set of network element pairs is maintained. 41. The computer program product of claim 40, wherein said forming said first set of network element pairs comprises:copying a first said number of pairs of said network elements in said second set of network element pairs into said first set of network element pairs. 42. The computer program product of claim 36, whereinsaid network element pair in said second set of network element pairs is a remaining network element pair in said second set of network element pairs, and said remaining network element pair corresponds to a non-independent row of said first matrix. 43. The computer program product of claim 37, wherein said computing said estimated network performance metric between said first network element and said second network element of said remaining network element pair comprises:forming a second matrix, wherein each row of said second matrix corresponds to a corresponding one of said non-independent rows of said first matrix, and said each row of said second matrix is such that said corresponding one of said non-independent rows of said first matrix can be expressed in terms of said independent rows using said each row of said second matrix; organizing said measured network performance metrics into a vector; and computing said estimated network performance metric between said first network element and said second network element of said remaining network element pair by multiplying said vector by a row of said second matrix corresponding to said remaining network element pair. 44. The computer program product of claim 37, wherein said computing said estimated network performance metric between said first network element and said second network element of said remaining network element pair comprises:forming a second matrix, wherein each row of said second matrix corresponds to a corresponding one of said non-independent rows of said first matrix, and said each row of said second matrix is such that said corresponding one of said non-independent rows of said first matrix can be expressed in terms of said independent rows using said each row of said second matrix; organizing said measured network performance metrics into a vector; and computing said estimated network performance metric between said first network element and said second network element of said remaining network element pair by multiplying said vector by a row of said second matrix corresponding to said remaining network element pair. 45. An apparatus comprising:means for identifying a first set of network element pairs from a plurality of network elements, each of said network elements being coupled to another of said network elements by at least one of a plurality of links, said means for identifying said first set of network element pairs comprising: means for identifying a first plurality of network element pairs from said network elements, wherein each of said first plurality of network element pairs corresponds to a one of said links, and means for identifying a network element pair from said network elements, wherein each of a first and a second network element of said network element pair is adjacent to a one of said network elements, a path between a first and a second network element of said network element pair comprises said one of said network elements, and said first set of network element pairs comprises said first plurality of network element pairs and said network element pair. 46. The apparatus of claim 45, further comprising:means for identifying another network element pair from said network elements, wherein every path between a first network element and a second network element of said another network element pair, if any, comprises a plurality of said network elements. 47. The apparatus of claim 46, further comprising:means for measuring a measured network performance metric over said first set of network element pairs; and means for using said measured network performance metric to estimate an estimated network performance metric over said another network element pair. 48. The apparatus of claim 47, whereina second set of network element pairs comprises said another network element pair. 49. The apparatus of claim 48, wherein said means for using comprises:means for computing said estimated network performance metric between said first network element and said second network element of said another network element pair. 50. The apparatus of claim 49, further comprising:means for identifying pairs of said network elements as being in said second set of network element pairs; and means for identifying pairs of said network elements in said second set of network element pairs as being in said first set of network element pairs. 51. The apparatus of claim 50, further comprising:means for generating a first matrix using said second set of network element pairs, wherein each row in said first matrix corresponds to a corresponding network element pair in said second set of network element pairs, said first matrix comprises independent rows and non-independent rows, said first set of network element pairs contains independent network element pairs in said second set of network element pairs, and each one of said independent pairs of network element corresponds to a one of said independent rows of said first matrix. 52. A data processing system comprising:a plurality of network elements, each of said network elements being coupled to another of said network elements by at least one of a plurality of links; and a computer system configured to identify a first set of network element pairs from said plurality of network elements by virtue of being configured to identify a first plurality of network element pairs from said network elements, wherein each of said first plurality of network element pairs corresponds to a one of said links, and identify a network element pair from said network elements, wherein each of a first and a second network element of said network element pair is adjacent to a one of said network elements, a path between a first and a second network element of said network element pair comprises said one of said network elements, and said first set of network element pairs comprises said first plurality of network element pairs and said network element pair.