System for estimating unknown attributes of interest in the under-determined inverse problem and a process of accomplishing the same

9,832,085

15/002376

January 20, 2016

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.

Malboubi, Mehdi (San Ramon, CA, US)

1. 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; given an original observation matrix, the method comprising: (a) establishing the computer network having a plurality of nodes wherein the per-flow size, the delay, the loss and the throughput inferences are unknown; wherein an original routing matrix determines a contribution of each flow size on each link-load; (b) performing a learning phase by: (1) measuring a set of quantities which are combinations of unknowns creating a first set of measurements; (2) measuring at least some of a set of unknowns creating a second set of measurements; (3) using functions of the first set of measurements and functions of the second set of measurements, computing an optimal observation matrix or pseudo-optimal observation matrix; (c) performing a computer controlled adaptive measurement and inference phase by: (1) measuring the set of quantities which are the combinations of the unknowns creating measurement quantities; (2) identifying a partial set of most informative unknown network flows that must be re-measured and updated; (3) re-measuring a partial set of unknowns; (4) re-computing and updating the optimal observation matrix to form an updated optimal observation matrix; (5) estimating 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; wherein, the under-determined inverse problem is a traffic matrix estimation problem and a set of unknown network flows are estimated by: a) measuring SNMP link loads as measured quantities which are linear combinations of a size of unknown network flows; b) measuring a set of unknown network flow sizes using counters associated with one of the set consisting of: flow-table entries, TCAM entries or both; c) computing the optimal observation matrix as a replacement of the original routing matrix; and d) inferring a set of unknown flows using specific estimation techniques and using SNMP link load measurements, and the function of one of the set consisting of the optimal observation matrix, the original routing matrix, or both.

2. The method of claim 1 , further comprising: (d) determining a starting time of the learning phase and a duration of the learning phase by detecting sequential significant changes in measurements during the computer controlled adaptive measurement and inference phase.

3. The method of claim 1 , further comprising: (f) determining the set of most informative unknown network flows using at least one learning algorithm; wherein the at least one learning algorithm includes a multi-bandit algorithm.

4. The method of claim 1 , further comprising generating the optimal observation matrix using one of the set consisting of: (a) a regularized optimization technique including a least square estimation technique with constraints; and (b) the regularized optimization technique including the least square estimation technique without the constraints.

5. The method of claim 1 , further comprising generating the optimal observation matrix using one of the set consisting of: (a) a non-regularized optimization technique including a least square estimation technique with constraints; and (b) the non-regularized optimization technique including the least square estimation technique without the constraints.

6. The method of claim 1 , generating an estimation of unknowns using a specified estimation technique using one of the set consisting of: (a) a regularized optimization technique including a least square estimation technique with constraints; and (b) the regularized optimization technique including the least square estimation technique without the constraints.

7. The method of claim 1 , generating an estimation of unknowns using a specified estimation technique using one of the set consisting of: (a) a non-regularized optimization technique including a least square estimation technique with constraints; and (b) the non-regularized optimization technique including the least square estimation technique without the constraints.

8. The method of claim 1 , wherein, measurements of the set of unknowns, in both learning phase and computer controlled adaptive measurement and inference phases, are approximated using: 1) mathematical, statistical, heuristic and experimental models, 2) auxiliary information, and 3) information from network topology, distance between nodes, the size of queues, buffers in nodes, and any combination of these.

9. The method of claim 1 , wherein, a function of the optimal observation matrix is used for routing a set of network flows.

10. The method of claim 1 , wherein, in the learning phase, several vectors of measurement quantities and unknown attributes of interest are available, and the optimal observation matrix or pseudo-optimal observation matrix is calculated using a least mean squares algorithm; wherein, in the computer controlled adaptive measurement and inference phase, a set of new measurements are provided using a function of the optimal observation matrix; wherein the unknowns of interest is estimated using a specific estimation technique.

11. The method of claim 1 , wherein, the under-determined inverse problem is constructed by converting one of the set consisting of: a square inverse problem, over-determined inverse problem or both to an under-determined inverse problem, wherein, the optimal observation matrix is computed and used for the estimation of unknowns of interest in one of the set consisting of: a square inverse problem, an over-determined inverse problem or both.

12. The method of claim 1 , wherein, the under-determined inverse problem is a system identification in the under-determined multi-input and multi-output systems, and a realization of parameters of a model of the system are estimated by computing an optimal observation matrix.

13. The method of claim 12 , wherein, the system is an under-determined multi-input and multi-output communication system wherein: a) in the learning phase, for all possible vectors of communication symbols, the optimal observation matrix is computed as follows: 1) transmitting a vector of known symbols at multiple transmitters; 2) measuring the vector of known symbols at multiple receivers; creating vectors of measurements; 3) computing the optimal observation matrix for each vector of known symbols and a corresponding vector of measurements, creating a plurality of optimal observation matrixes; 4) saving the vector of known symbols and the plurality of optimal observation matrixes at a receiver device; b) in the computer controlled adaptive measurement and inference phase: 1) transmitting an unknown vector of symbols from multiple transmitters; 2) creating a measurement vector from multiple measurements at multiple receivers; 3) estimating vectors of symbols using the measurement vector and all optimal observation matrices creating estimated vectors of symbols; 4) computing a distance between the estimated vectors of symbols, and the vectors of known symbols; 5) decoding a minimum distance vector of known symbols as an ultimate estimate of the unknown vector of symbols.

14. A system useful for displaying a solution to an under-determined inverse problem in per-flow size, delay, loss and throughput inference in a computer network; the system comprising: (a) the computer network having a plurality of nodes where the per-flow size, the delay, the loss and throughput estimates inference are unknown; (b) a computer store configured to store data for at least two or more nodes; (c) a display configured to display the per-flow size, the delay, the loss and throughput estimates in the computer network; (d) a computer controller connected to each of the plurality of nodes, wherein the computer controller is coupled to the computer store and programmed to: (1) perform a learning phase by: (i) measuring a set of quantities which are combinations of unknowns creating a first set of measurements; (ii) measuring at least some of a set of unknowns creating a second set of measurements; (iii) using functions of the first set of measurements and functions of the second set of measurements, and computing an optimal or pseudo-optimal observation matrix; (2) perform an adaptive measurement and inference phase by: (i) measuring the set of quantities which are the combinations of the unknowns creating measurement quantities; (ii) identifying a partial set of most informative unknown network flows that must be re-measured and updated; (iii) re-measuring the partial set of most informative unknown network flows; (iv) re-computing and updating an optimal observation matrix to form an updated optimal observation matrix; (v) estimating the set of unknowns using the measurement quantities, and a function of one of the set consisting of: the optimal observation matrix, an original observation matrix, or both; and (3) display the unknowns; wherein, the under-determined inverse problem is a traffic matrix estimation problem and a set of unknown network flows are estimated by: a) measuring SNMP link loads as measured quantities which are linear combinations of a size of unknown network flows; b) measuring a set of unknown network flow sizes using counters associated with one of the set consisting of: flow-table entries, TCAM entries or both; c) computing the optimal observation matrix as a replacement of the original routing matrix; and d) inferring a set of unknown flows using specific estimation techniques and using SNMP link load measurements, and the function of one of the set consisting of the optimal observation matrix, the original routing matrix, or both.

15. A computer-readable memory adapted for use by a computer network in determining a solution to an under-determined inverse problem in per-flow size, delay, and throughput inference, the computer-readable memory used to direct a computer of the network to perform the steps of: (a) the computer network having a plurality of nodes where the per-flow size, the delay, the loss and throughput estimates inference are unknown; (b) a computer store configured to store data for at least two or more nodes; (c) a display configured to display the per-flow size, the delay, the loss and throughput estimates in the computer network; (d) a computer controller connected to each of the plurality of nodes, wherein the computer controller is coupled to the computer store and programmed to: (1) perform a learning phase by: (i) measure a set of quantities which are combinations of unknowns creating a first set of measurements; (ii) measure at least some of a set of unknowns creating a second set of measurements; (iii) use functions of the first set of measurements and functions of the second set of measurements, and computing an optimal or pseudo-optimal observation matrix; (2) perform an adaptive measurement and inference phase by: (i) measuring the set of quantities which are the combinations of the unknowns creating measurement quantities; (ii) identifying a partial set of most informative unknown network flows that must be re-measured and updated; (iii) re-measuring a partial set of most informative unknowns; (iv) re-computing and updating an optimal observation matrix to form an updated optimal observation matrix; (v) estimating the set of unknowns using the measurement quantities, and a function of one of the set consisting of: the optimal observation matrix, an original observation matrix, or both; and (3) display the unknowns; wherein, the under-determined inverse problem is a traffic matrix estimation problem and a set of unknown network flows are estimated by: a) measuring SNMP link loads as measured quantities which are linear combinations of a size of unknown network flows; b) measuring a set of unknown network flow sizes using counters associated with one of the set consisting of: flow-table entries, TCAM entries or both; c) computing the optimal observation matrix as a replacement of the original routing matrix; and d) inferring a set of unknown flows using specific estimation techniques and using SNMP link load measurements, and the function of one of the set consisting of the optimal observation matrix, the original routing matrix, or both.

6785240 August 2004 Cao
7746784 June 2010 de Heer
7836201 November 2010 Kotrla
8125911 February 2012 Patel
8248925 August 2012 Allan
8711676 April 2014 Bhat
9083627 July 2015 Vasseur
9641452 May 2017 Lu
9646253 May 2017 Kankar
2007/0177506 August 2007 Singer
2012/0127029 May 2012 Rachlin
2012/0191843 July 2012 Ding
2013/0262661 October 2013 Malboubi

M. Malboubi. L. Wang, C. Chuah, and P. Sharma, “Intelligent sdn based traffic (de)aggregation and measurement paradigm (istamp),” IEEE INFOCOM, 2014. cited by applicant
M. Moshref, M. Yu, R. Govindan, and A. Vandat, “Dream: Dynamic resource allocation for software-defined measurement,” ACM SIGCOMM (HozSDN), 2014. cited by applicant
A. Soule, K. Salamatian, and N. Taft, “Combining filtering and statistical methods for anomaly detection,” ACM SIGCOMM, 2005. cited by applicant
M. Roughan, M. Thorup, and Y. Zhang, “Traffic engineering with estimated traffic matrices,” ACM-IMC, 2003. cited by applicant
“Cisco netflow,” At: http://en.wikipedia.org/wiki/Netflow. cited by applicant
“Sampled netflow,” At: http://www.cisco.com/en/US/docs/ios/12\0s/feature/guide/12s\sanf.html. cited by applicant
A. Kumar and J. Xu, “Sketch guided sampling—using on-line estimates of flow size for adaptive data collection,” in INFOCOM, 2006. cited by applicant
M. Roughan, “A case study of the accuracy of snmp measurements,” JECE, vol. 2010, pp. 33:1-33:7, Jan. 2010. cited by applicant
A. Medina and et al., “Traffic matrix estimation:existing techniques and new directions,” in ACM SIGCOMM, 2002. cited by applicant
R. M, Y. Zhang, W. Willinger, and L. Qiu, “Spatio-temporal compressive sensing and internet traffic matrices,” IEEE/ACM Transactions on Networking, vol. 20, pp. 662-676, 2012. cited by applicant
Q. Zhao, Z. Ge, J. Wang, and J. Xu, “Robust traffic matrix estimation with imperfect information: Making use of multiple data sources,” ACM-SIGMETRICS, 2006. cited by applicant
J. Cao, D. Davis, S. Wiel, and B. Yu, “Time varying network tomography: Router link data,” JNL of American Stat. Association, 2000. cited by applicant
G. Huang, A. Lall, C.-N. Chuah, and J. Xu, “Uncovering global icebergs in distributed streams: Results and implications,” J. Network Syst. Manage, vol. 19, No. 1, pp. 84-110, 2011. cited by applicant
A. Tootoonchian, M. Ghobadi, and Y. Ganjali, “Opentm: traffic matrix estimator for openfiow networks,” 2010. cited by applicant
N. van Adrichen, C. Doerr, and F. Kuipers, “OpenNetMon: Network monitoring in openflow sdn networks,” IEEE, INFOCOM, 2014. cited by applicant
M. Yu, L. Jose, and R. Miao. “Software defined traffic measurement with opensketch,” ACM-USENIX, 2013. cited by applicant
L. Jose. M. Yu, and J. Rexford, “Online measurement of large traffic aggregates on commodity switches,” ACM-Hot-ICE, 2011. cited by applicant
M. C. A.P. Lakhina. E. K. C.M. Diot, and N. Taft, “Structural analysis of network traffic flows,” ACM Sigmetrics, 2004. cited by applicant
A. Israel and T. E Greville in Generalized Inverses: Theory and Applications, Springer, 2003. cited by applicant
H. Nguyen and P. Thiran, “Network loss inference with second order statistics of end-to-end flows,” ACM-IMC, 2007. cited by applicant
M. Basseville and I. Nikiforov in Detection of Abrupt Changes: Theory and Application, Prentice-Hall, 1993. cited by applicant
“Geant network:.” http://totem.info.ucl.ac.be/dataset.html. cited by applicant
“Miniet,” At: http://mininet.org/. cited by applicant

edspgr.09832085