- Patent Number:
11063,848
- Appl. No:
16/551583
- Application Filed:
August 26, 2019
- نبذة مختصرة :
A method for solving an under-determined inverse problem or network inference/tomography problem in per-flow size, delay, loss and throughput inference in a computer network, through a system is presented. The method includes the following steps, which are not necessarily in order. First, establishing the computer network having a plurality of nodes wherein the per-flow size, the delay, the loss and the throughput inference are unknown. An original observation or routing matrix determines how flows are appeared on the links and construct the measurements. Next, performing a learning phase to obtain an optimal observation matrix or pseudo-optimal observation matrix. After that, performing a computer controller adaptive measurement and inference phase to estimate the set of unknowns using the measurement quantities, and a function of one of the set consisting of: the optimal observation matrix, the original observation matrix, or both.
- Inventors:
Malboubi, Mehdi (San Ramon, CA, US)
- Claim:
1. A method for determining unknowns of interest in under-determined inverse problems in a network through a system; the method comprising: (a) providing the network having a plurality of nodes connected through a plurality of links, wherein each path is a set of connected links; (b) measuring a set of measurements which are a combination of the unknowns of interest, creating a first set of measurements (c) forming an under-determined inverse problem using an original observation matrix and a vector representation of the unknowns of interest; (d) measuring a set of unknowns of interest, creating a second set of measurements; (e) computing an optimal observation matrix using a function of the first set of measurements and the second set of measurements, wherein, the optimal observation matrix is computed by a following equation: H o =YX T (XX T) † wherein: H o is the optimal observation matrix; Y is a column-wise vector representation of the first set of measurements, X is a column-wise vector representation of the second set of measurements; T denotes one member of a variable set consisting of: a transpose operator and a complex-conjugate transpose operator; † denotes a pseudo inverse operator; and (f) processing and estimating the unknowns of interest using the optimal observation matrix, the first set of measurements and the second set of measurements.
- Claim:
2. The method of claim 1 , wherein after computing the optimal observation matrix, an unknown of interest is estimated using another function of the optimal observation matrix and at least one member of a measurement set consisting of: the first set of measurements and the second set of measurements.
- Claim:
3. The method of claim 1 , wherein an unknown of interest is estimated by a following equation: {circumflex over (X)} =(H o) † Y wherein: Y is a column-wise vector representation of the first set of measurements; (H o) † is a pseudo-inverse of the optimal observation matrix; and {circumflex over (X)} is a column-wise vector representation of unknown of interests that are estimated.
- Claim:
4. The method of claim 1 , wherein the plurality of nodes is selected from a node set consists of: a physical network device, a physical network element, a virtual network device, a virtual network element, a computer host, a virtual machine, a physical network switch, a virtual network switch and a physical network router, a virtual network router, a physical network interface, and a virtual network interface.
- Claim:
5. The method of claim 1 , wherein the plurality of links are selected from a link set consists of: a physical link, a virtual link, a wired physical link, and a wireless physical link; and wherein the path is the set of connected links.
- Claim:
6. The method of claim 1 , wherein the first set of measurements is at least one member selected from a measurement set consisting of: at least one of network link-loads, at least one of network path-delays, at least one of network path-losses, and at least one of network path throughputs; wherein the set of unknowns of interest includes at least one member of an unknown set consisting of: at least one of flow-sizes, at least one of link-delays, at least one of link-losses, and at least one of link throughputs.
- Claim:
7. The method of claim 1 , wherein measurements of the set of unknowns of interest that creates the second set of measurements are approximated using: 1) mathematical, statistical, heuristic and experimental models, 2) auxiliary information, and 3) information from at least one member of an information set consisting of a network topology, a distance between nodes, a size of a queue, and a buffer in a node.
- Claim:
8. The method of claim 1 wherein, measuring the first set of measurements, and the second set of measurements, an adjusted set of measurements and computing the optimal observation matrix are performed in both a learning phase and in a measurement and inference phase, and estimating the unknowns of interest are performed in the measurement and inference phase.
- Claim:
9. The method of claim 1 , wherein measuring the set of measurements further comprises adaptively measuring the set of measurements and adjusted measurements, in a learning phase and in a measurement and inference phase.
- Claim:
10. The method of claim 1 , wherein computing the optimal observation matrix further comprises adaptively computing the optimal observation matrix, in a learning phase and in a measurement and inference phase.
- Claim:
11. The method of claim 1 , wherein estimating the unknowns of interest further comprises adaptively estimating the unknowns of interest in a learning phase and in a measurement and inference phase.
- Claim:
12. The method of claim 1 , wherein nodes and at least one controller communicate via networking protocols for exchanging network measurements, controlling commands and management instructions.
- Claim:
13. The method of claim 1 , wherein the plurality of nodes are selected from a node set consists of: a network transceiver, a network transmitter, and a network receiver; wherein the first set of measurements are provided using at least one member of a measurement set consisting of: another function of inputs of network receivers, and another function of inputs of network transceivers; wherein the second set of measurements are provided using at least one member of another measurement set consisting of: another function of outputs of network transmitters, and another function of outputs of network transceivers; wherein the set of unknowns of interest are at least one member from a set consisting of: network transmitted information, and another function of network transmitted information.
- Claim:
14. The method of claim 1 , wherein the optimal observation matrix is computed using a function of a processed version of the first set of measurements, and a function of a processed version of the second set of measurements.
- Claim:
15. The method of claim 1 , wherein after computing the optimal observation matrix, processing is applied on another function of the optimal observation matrix and one of a set consisting of: a processed version of the first set of measurements and a processed version of the second set of measurements or both.
- Claim:
16. The method of claim 1 , wherein the optimal observation matrix is used to produce informative attributes for the second set of measurements.
- Claim:
17. The method of claim 1 , wherein measurements of the first set of measurements and the second set of measurements are provided by at least one member of a measurement set consisting of: counting using counters, using counters associated with content-addressable memories, using counters associated with memories, using counters associated with table entries, sampling using samplers, sampling using analog-to-digital converters, querying databases, querying data stores, acquisition from data storage systems, and data streaming systems.
- Claim:
18. A non-transitory computer-readable medium storing instructions which, when executed by a processing system including at least one processor, cause the processing system to perform operations for determining unknowns of interest in under-determined inverse problems, the operations comprising: (a) measuring a set of measurements which are a combination of the unknowns of interest, creating a first set of measurements (b) forming an under-determined inverse problem using an original observation matrix and a vector representation of the unknowns of interest; (c) measuring a set of unknowns of interest, creating a second set of measurements; (d) computing an optimal observation matrix using a function of the first set of measurements and the second set of measurements, wherein, the optimal observation matrix is computed by a following equation: H o =YX T (XX T) † wherein: H o is the optimal observation matrix; Y is a column-wise vector representation of the first set of measurements, X is a column-wise vector representation of the second set of measurements; T denotes one member of a variable set consisting of: a transpose operator and a complex-conjugate transpose operator; † denotes a pseudo inverse operator; and (e) processing and estimating the unknowns of interest using the optimal observation matrix, the first set of measurements and the second set of measurements.
- Claim:
19. A processing system compromising: at least one processor; and a computer-readable medium storing instructions which, when executed by the processing system, cause the processing system to perform operations for determining unknowns of interest in under-determined inverse problems, the operations comprising: (a) measuring a set of measurements which are a combination of the unknowns of interest, creating a first set of measurements (b) forming an under-determined inverse problem using an original observation matrix and a vector representation of the unknowns of interest; (c) measuring a set of unknowns of interest, creating a second set of measurements; (d) computing an optimal observation matrix using a function of the first set of measurements and the second set of measurements, wherein, the optimal observation matrix is computed by a following equation: H o =YX T (XX T) † wherein: H o is the optimal observation matrix; Y is a column-wise vector representation of the first set of measurements, X is a column-wise vector representation of the second set of measurements; T denotes one member of a variable set consisting of: a transpose operator and a complex-conjugate transpose operator; † denotes a pseudo inverse operator; and (e) processing and estimating the unknowns of interest using the optimal observation matrix, the first set of measurements and the second set of measurements.
- Claim:
20. A set of virtualized computing environments instantiated for performing operations for determining unknowns of interest in under-determined inverse problems, the operations comprising: (a) measuring a set of measurements which are a combination of the unknowns of interest, creating a first set of measurements (b) forming an under-determined inverse problem using an original observation matrix and a vector representation of the unknowns of interest; (c) measuring a set of unknowns of interest, creating a second set of measurements; (d) computing an optimal observation matrix using a function of the first set of measurements and the second set of measurements, wherein, the optimal observation matrix is computed by a following equation: H o =YX T (XX T) † wherein: H o is the optimal observation matrix; Y is a column-wise vector representation of the first set of measurements, X is a column-wise vector representation of the second set of measurements; T denotes one member of a variable set consisting of: a transpose operator and a complex-conjugate transpose operator; † denotes a pseudo inverse operator; and (e) processing and estimating the unknowns of interest using the optimal observation matrix, the first set of measurements and the second set of measurements.
- Patent References Cited:
6785240 August 2004 Cao
7746784 June 2010 de Heer
7836201 November 2010 Kotrla
8036601 October 2011 Prasad
8125911 February 2012 Patel
8248925 August 2012 Allan
8711676 April 2014 Bhat
9083627 July 2015 Vasseur
9641452 May 2017 Lu
9646253 May 2017 Kankar
9832085 November 2017 Malboubi
9893742 February 2018 Noma
2005/0192024 September 2005 Sheynblat
2007/0177506 August 2007 Singer
2009/0022369 January 2009 Satoh
2010/0074358 March 2010 Khojastepour
2012/0127029 May 2012 Rachlin
2012/0191843 July 2012 Ding
2013/0135489 May 2013 Lee
2013/0262661 October 2013 Malboubi
2015/0253150 September 2015 Guillet
2016/0179190 June 2016 Lee
- Primary Examiner:
Li, Guang W
- Attorney, Agent or Firm:
Law Office of Michael O'Brien
O'Brien, Michael
- الرقم المعرف:
edspgr.11063848
Processing Request
No Comments.