IPC분류정보
국가/구분 |
United States(US) Patent
등록
|
국제특허분류(IPC7판) |
|
출원번호 |
US-0638180
(2000-07-31)
|
발명자
/ 주소 |
- Jain, Bijendra N.
- McCloghrie, Keith
|
출원인 / 주소 |
|
대리인 / 주소 |
Campbell Stephenson Ascolese LLP
|
인용정보 |
피인용 횟수 :
14 인용 특허 :
21 |
초록
▼
A method and apparatus for determining a network performance metric in a network is described. The network includes a number of network elements and a number of links. Each of the network elements is coupled to at least one other of the network elements by at least one of the links. The method inclu
A method and apparatus for determining a network performance metric in a network is described. The network includes a number of network elements and a number of links. Each of the network elements is coupled to at least one other of the network elements by at least one of the links. The method includes forming a first set of network element pairs, ordering a first number of network element pairs, forming a second set of network element pairs, measuring a measured network performance metric between a first network element pair and computing a computed network performance metric.
대표청구항
▼
1. A method of determining a network performance metric in a network, wherein said network comprises a plurality of network elements and each one of said network elements is coupled to at least one other of said network elements by at least one of a plurality of links, comprising:forming a first set
1. A method of determining a network performance metric in a network, wherein said network comprises a plurality of network elements and each one of said network elements is coupled to at least one other of said network elements by at least one of a plurality of links, comprising:forming a first set of network element pairs, said first set of network element pairs comprising a plurality of pairs of said network elements; ordering a first plurality of network element pairs comprising ones of network element pairs in said first set of network element pairs; forming a second set of network element pairs, wherein said second set of network element pairs comprises ones of said network element pairs in said first set of network element pairs; measuring a measured network performance metric between a first network element pair, wherein said first network element pair comprises a first network element and a second network element of one of said network element pairs in said second set of network element pairs; and computing a computed network performance metric between a second network element pair using said measured network performance metric, wherein said second network element pair comprises a first network element and a second network element of said network element pair in said first set of network element pairs. 2. The method of claim 1, wherein said computed network performance metric is computed using a relationship between said first and said second network element pairs.3. The method of claim 1, wherein said ordering comprises:identifying a plurality of network elements, wherein each one of said plurality of network elements is one of a network element pair in said first set of network element pairs; assigning one of a plurality of preferences to each one of said plurality of network elements; and sorting said network element pairs in said first set of network element pairs based on said plurality of preferences. 4. The method of claim 3, wherein said sorting comprises:for each one of said network element pairs in said first set of network element pairs, swapping a first network element and a second network element in said each one of said network element pairs in said first set of network element pairs, if a preference of said first network element in said each one of said network element pairs in said first set of network element pairs is less than a preference of said second network element in said each one of said network element pairs in said first set of network element pairs; sorting said network element pairs in said first set of network element pairs based on a preference of a present first network element of said each one of said network element pairs in said first set of network element pairs; and sorting said network element pairs in said first set of network element pairs based on a preference of a present second network element of said each one of said network element pairs in said first set of network element pairs. 5. The method of claim 1, further comprising:forming a first matrix, wherein each row in said first matrix corresponds to a network element pair of said first set of network element pairs; and determining a set of independent rows of said first matrix. 6. The method of claim 5, wherein said set of independent rows of said first matrix is a maximal set of independent rows of said first matrix.7. The method of claim 5, wherein said forming said second set of network element pairs comprises:including independent network element pairs in said second set of network element pairs, wherein said independent network element pairs are ones of said network element pairs in said first set of network element pairs corresponding to rows of said first matrix in said set of independent rows of said first matrix. 8. The method of claim 1, further comprising:forming a delay components vector, forming a first matrix, wherein said first matrix describes a relationship between said delay components vector and a delay between each of said network element pairs of said first set of network element pairs, each row in said first matrix corresponds to a network element pair of said first set of network element pairs; and determining a set of independent rows of said first matrix, wherein said forming said second set of network element pairs comprises including independent network element pairs in said second set of network element pairs, and said independent network element pairs are ones of said network element pairs in said first set of network element pairs corresponding to rows of said first matrix in said set of independent rows of said first matrix. 9. The method of claim 8, wherein said delay components vector comprises:a representation of a delay within each network element of each network element pair of said first set of network element pairs for said each network element pair of said first set of network element pairs, and a representation of a delay between network elements of said each network element pair of said first set of network element pairs for said each network element pair of said first set of network element pairs. 10. The method of claim 8, further comprising:forming a second matrix, wherein said second matrix describes a relationship between a plurality of independent delays and a non-independent delay, said plurality of independent delays comprise a delay between network elements in each network element pair of said second set of network element pairs, and said non-independent delay comprises a delay between network elements in a network element pair of said first set of network element pairs that is not in said second set of network element pairs. 11. The method of claim 10, wherein said forming said second matrix comprises performing a Gaussian elimination using said first and said second matrices.12. The method of claim 10, wherein said computing said computed network performance metric comprises:multiplying said measured performance metric by an element of said second matrix. 13. A computer system comprising:a processor; a network interface, coupled to said processor and to a network, wherein said network comprises a plurality of network elements and each one of said network elements is coupled to at least one other of said network elements by at least one of a plurality of links; computer readable medium coupled to said processor; and computer code, encoded in said computer readable medium, configured to cause said processor to: form a first set of network element pairs, said first set of network element pairs comprising a plurality of pairs of said network elements; order a first plurality of network element pairs comprising ones of network element pairs in said first set of network element pairs; form a second set of network element pairs, wherein said second set of network element pairs comprises ones of said network element pairs in said first set of network element pairs; measure a measured network performance metric between a first network element pair, wherein said first network element pair comprises a first network element and a second network element of one of said network element pairs in said second set of network element pairs; and compute a computed network performance metric between a second network element pair using said measured network performance metric, wherein said second network element pair comprises a first network element and a second network element of said network element pair in said first set of network element pairs. 14. The computer system of claim 13, wherein said computed network performance metric is computed using a relationship between said first and said second network element pairs.15. The computer system of claim 13, wherein said computer code configured to cause said processor to order said first plurality of network element pairs, is further configured to cause said processor to:identify a plurality of network elements, wherein each one of said plurality of network elements is one of a network element pair in said first set of network element pairs; assign one of a plurality of preferences to each one of said plurality of network elements; and sort said network element pairs in said first set of network element pairs based on said plurality of preferences. 16. The computer system of claim 15, wherein said computer code configured to cause said processor to sort said network element pairs in said first set of network element pairs based on said plurality of preferences, is further configured to cause said processor to:for each one of said network element pairs in said first set of network element pairs, swap a first network element and a second network element in said each one of said network element pairs in said first set of network element pairs, if a preference of said first network element in said each one of said network element pairs in said first set of network element pairs is less than a preference of said second network element in said each one of said network element pairs in said first set of network element pairs; sort said network element pairs in said first set of network element pairs based on a preference of a present first network element of said each one of said network element pairs in said first set of network element pairs; and sort said network element pairs in said first set of network element pairs based on a preference of a present second network element of said each one of said network element pairs in said first set of network element pairs. 17. The computer system of claim 13, wherein said computer code is further configured to cause said processor to:form a first matrix, wherein each row in said first matrix corresponds to a network element pair of said first set of network element pairs; and determine a set of independent rows of said first matrix. 18. The computer system of claim 17, wherein said set of independent rows of said first matrix is a maximal set of independent rows of said first matrix.19. The computer system of claim 17, wherein said computer code configured to cause said processor to form said second set of network element pairs, is further configured to cause said processor to:include independent network element pairs in said second set of network element pairs, wherein said independent network element pairs are ones of said network element pairs in said first set of network element pairs corresponding to rows of said first matrix in said set of independent rows of said first matrix. 20. The computer system of claim 13, wherein said computer code is further configured to cause said processor to:form a delay components vector; form a first matrix, wherein said first matrix describes a relationship between said delay components vector and a delay between each of said network element pairs of said first set of network element pairs, each row in said first matrix corresponds to a network element pair of said first set of network element pairs; and determine a set of independent rows of said first matrix, wherein said forming said second set of network element pairs comprises including independent network element pairs in said second set of network element pairs, and said independent network element pairs are ones of said network element pairs in said first set of network element pairs corresponding to rows of said first matrix in said set of independent rows of said first matrix. 21. The computer system of claim 20, wherein said delay components vector comprises:a representation of a delay within each network element of each network element pair of said first set of network element pairs for said each network element pair of said first set of network element pairs, and a representation of a delay between network elements of said each network element pair of said first set of network element pairs for said each network element pair of said first set of network element pairs. 22. The computer system of claim 20, wherein said computer code is further configured to cause said processor to:form a second matrix, wherein said second matrix describes a relationship between a plurality of independent delays and a non-independent delay, said plurality of independent delays comprise a delay between network elements in each network element pair of said second set of network element pairs, and said non-independent delay comprises a delay between network elements in a network element pair of said first set of network element pairs that is not in said second set of network element pairs. 23. The computer system of claim 22, wherein said computer code configured to cause said processor to form said second matrix, is further configured to cause said processor to:perform a Gaussian elimination using said first and said second matrices. 24. The computer system of claim 22, wherein said computer code configured to cause said processor to compute a computed network performance metric, is further configured to cause said processor to:multiply said measured performance metric by an element of said second matrix. 25. A computer program product encoded in computer readable media, said computer program product comprising:a first set of instructions, executable on a computer system, configured to form a first set of network element pairs, said first set of network element pairs comprising a plurality of pairs of said network elements; a second set of instructions, executable on said computer system, configured to order a first plurality of network element pairs comprising ones of network element pairs in said first set of network element pairs; a third set of instructions, executable on said computer system, configured to form a second set of network element pairs, wherein said second set of network element pairs comprises ones of said network element pairs in said first set of network element pairs; a fourth set of instructions, executable on said computer system, configured to measure a measured network performance metric between a first network element pair, wherein said first network element pair comprises a first network element and a second network element of one of said network element pairs in said second set of network element pairs; and a fifth set of instructions, executable on said computer system, configured to compute a computed network performance metric between a second network element pair using said measured network performance metric, wherein said second network element pair comprises a first network element and a second network element of said network element pair in said first set of network element pairs. 26. The computer program product of claim 25, wherein fifth set of instructions cause said computer system to compute said computed network performance metric using a relationship between said first and said second network element pairs.27. The computer program product of claim 25, wherein said second set of instructions comprises:a sixth set of instructions, executable on said computer system, configured to identify a plurality of network elements, wherein each one of said plurality of network elements is one of a network element pair in said first set of network element pairs; a seventh set of instructions, executable on said computer system, configured to identify a plurality of network elements, wherein each one of said plurality of network elements is one of a network element pair in said first set of network element pairs; and a eighth set of instructions, executable on said computer system, configured to identify a plurality of network elements, wherein each one of said plurality of network elements is one of a network element pair in said first set of network element pairs. 28. The computer program product of claim 27, wherein said eighth set of instructions comprises:a first sub-set of instructions, executable on said computer system, configured to, for each one of said network element pairs in said first set of network element pairs, swap a first network element and a second network element in said each one of said network element pairs in said first set of network element pairs, if a preference of said first network element in said each one of said network element pairs in said first set of network element pairs is less than a preference of said second network element in said each one of said network element pairs in said first set of network element pairs; a second sub-set of instructions, executable on said computer system, configured to sort said network element pairs in said first set of network element pairs based on a preference of a present first network element of said each one of said network element pairs in said first set of network element pairs; and an third sub-set of instructions, executable on said computer system, configured to sort said network element pairs in said first set of network element pairs based on a preference of a present second network element of said each one of said network element pairs in said first set of network element pairs. 29. The computer program product of claim 25, further comprising:a sixth set of instructions, executable on said computer system, configured to form a first matrix, wherein each row in said first matrix corresponds to a network element pair of said first set of network element pairs; and a seventh set of instructions, executable on said computer system, configured to determine a set of independent rows of said first matrix. 30. The computer program product of claim 29, wherein said set of independent rows of said first matrix is a maximal set of independent rows of said first matrix.31. The computer program product of claim 29, wherein said third set of instructions comprises:a first sub-set of instructions, executable on said computer system, configured to include independent network element pairs in said second set of network element pairs, wherein said independent network element pairs are ones of said network element pairs in said first set of network element pairs corresponding to rows of said first matrix in said set of independent rows of said first matrix. 32. The computer program product of claim 25, further comprising:a sixth set of instructions, executable on said computer system, configured to form a delay components vector; a seventh set of instructions, executable on said computer system, configured to form a first matrix, wherein said first matrix describes a relationship between said delay components vector and a delay between each of said network element pairs of said first set of network clement pairs, each row in said first matrix corresponds to a network element pair of said first set of network element pairs; and a eighth set of instructions, executable on said computer system, configured to determine a set of independent rows of said first matrix, wherein said forming said second set of network element pairs comprises including independent network element pairs in said second set of network element pairs, and said independent network element pairs are ones of said network element pairs in said first set of network element pairs corresponding to rows of said first matrix in said set of independent rows of said first matrix. 33. The computer program product of claim 32, wherein said delay components vector comprises:a representation of a delay within each network element of each network element pair of said first set of network element pairs for said each network element pair of said first set of network element pairs, and a representation of a delay between network elements of said each network element pair of said first set of network element pairs for said each network element pair of said first set of network element pairs. 34. The computer program product of claim 32, further comprising:a ninth set of instructions, executable on said computer system, configured to form a second matrix, wherein said second matrix describes a relationship between a plurality of independent delays and a non-independent delay, said plurality of independent delays comprise a delay between network elements in each network element pair of said second set of network element pairs, and said non-independent delay comprises a delay between network elements in a network element pair of said first set of network element pairs that is not in said second set of network clement pairs. 35. The computer program product of claim 34, wherein said ninth set of instructions comprises:a first sub-set of instructions, executable on said computer system, configured to perform a Gaussian elimination using said first and said second matrices. 36. The computer program product of claim 34, wherein said fifth set of instructions comprises:a first sub-set of instructions, executable on said computer system, configured to multiply said measured performance metric by an element of said second matrix. 37. A computer system comprising:a network interface, coupled to said processor and to a network, wherein said network comprises a plurality of network elements and each one of said network elements is coupled to at least one other of said network elements by at least one of a plurality of links; means for forming a first set of network element pairs, said first set of network element pairs comprising a plurality of pairs of said network elements; means for ordering a first plurality of network element pairs comprising ones of network element pairs in said first set of network element pairs; means for forming a second set of network element pairs, wherein said second set of network element pairs comprises ones of said network element pairs in said first set of network element pairs; means for measuring a measured network performance metric between a first network element pair, wherein said first network element pair comprises a first network element and a second network element of one of said network element pairs in said second set of network element pairs; and means for computing a computed network performance metric between a second network element pair using said measured network performance metric, wherein said second network element pair comprises a first network element and a second network element of said network element pair in said first set of network element pairs. 38. The computer system of claim 37, wherein said computed network performance metric is computed using a relationship between said first and said second network element pairs.39. The computer system of claim 37, further comprising:means for identifying a plurality of network elements, wherein each one of said plurality of network elements is one of a network element pair in said first set of network element pairs; means for assigning one of a plurality of preferences to each one of said plurality of network elements; and means for sorting said network element pairs in said first set of network element pairs based on said plurality of preferences. 40. The computer system of claim 39, wherein said sorting means comprises:means, for each one of said network element pairs in said first set of network element pairs, for swapping a first network element and a second network element in said each one of said network element pairs in said first set of network element pairs, if a preference of said first network element in said each one of said network element pairs in said first set of network clement pairs is less than a preference of said second network element in said each one of said network element pairs in said first set of network element pairs; means for sorting said network element pairs in said first set of network element pairs based on a preference of a present first network element of said each one of said network element pairs in said first set of network element pairs; and means for sorting said network element pairs in said first set of network element pairs based on a preference of a present second network element of said each one of said network element pairs in said first set of network element pairs. 41. The computer system of claim 37, further comprising:means for forming a first matrix, wherein each row in said first matrix corresponds to a network element pair of said first set of network element pairs; and means for determining a set of independent rows of said first matrix. 42. The computer system of claim 41, wherein said set of independent rows of said first matrix is a maximal set of independent rows of said first matrix.43. The computer system of claim 41, wherein said means for forming said second set of network element pairs comprises:means for including independent network element pairs in said second set of network element pairs, wherein said independent network element pairs are ones of said network element pairs in said first set of network element pairs corresponding to rows of said first matrix in said set of independent rows of said first matrix. 44. The computer system of claim 37, further comprising:means for forming a delay components vector; means for forming a first matrix, wherein said first matrix describes a relationship between said delay components vector and a delay between each of said network element pairs of said first set of network element pairs, each row in said first matrix corresponds to a network element pair of said first set of network element pairs; and means for determining a set of independent rows of said first matrix, wherein said forming said second set of network element pairs comprises including independent network element pairs in said second set of network element pairs, and said independent network element pairs are ones of said network element pairs in said first set of network element pairs corresponding to rows of said first matrix in said set of independent rows of said first matrix. 45. The computer system of claim 44, wherein said delay components vector comprises:a representation of a delay within each network element of each network element pair of said first set of network element pairs for said each network element pair of said first set of network element pairs, and a representation of a delay between network elements of said each network element pair of said first set of network element pairs for said each network element pair of said first set of network element pairs. 46. The computer system of claim 44, further comprising:means for forming a second matrix, wherein said second matrix describes a relationship between a plurality of independent delays and a non-independent delay, said plurality of independent delays comprise a delay between network elements in each network element pair of said second set of network element pairs, and said non-independent delay comprises a delay between network elements in a network element pair of said first set of network element pairs that is not in said second set of network element pairs. 47. The computer system of claim 46, wherein said means for forming said second matrix comprises means for performing a Gaussian elimination using said first and said second matrices.48. The computer system of claim 46, wherein said means for computing said computed network performance metric comprises:means for multiplying said measured performance metric by an element of said second matrix.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.