Tracking in a spaghetti bowl: monitoring transactions using footprints

ABSTRACT

The problem of tracking end-to-end service-level transactions in the absence of instrumentation support is considered. The transaction instances progress through a state-transition model and generate time-stamped footprints on entering each state in the model. The goal is to track individual transactions using these footprints even when the footprints may not contain any tokens uniquely identifying the transaction instances that generated them. Assuming a semi-Markov process model for state transitions, the transaction instances are tracked probabilistically by matching them to the available footprints according to the maximum likelihood (ML) criterion. Under the ML-rule, for a two-state system, it is shown that the probability that all the instances are matched correctly is minimized when the transition times are i.i.d. exponentially distributed. When the transition times are i.i.d. distributed, the ML-rule reduces to a minimum weight bipartite matching and reduces further to a first-in first-out match for a special class of distributions. For a multi-state model with an acyclic state transition digraph, a constructive proof shows that the ML-rule reduces to splicing the results of independent matching of many bipartite systems.

REFERENCES

• 1: ARM. http://www.opengroup.org/tech/management/arm/.
• 2: A. Aggarwal , A. Bar-Noy , S. Khuller , D. Kravets , B. Schieber, Efficient minimum cost matching using quadrangle inequality, Proceedings of the Proceedings., 33rd Annual Symposium on Foundations of Computer Science, p.583-592, October 24-27, 1992 [doi>10.1109/SFCS.1992.267793]
• 3: Rakesh Agrawal , Dimitrios Gunopulos , Frank Leymann, Mining Process Models from Workflow Logs, Proceedings of the 6th International Conference on Extending Database Technology: Advances in Database Technology, p.469-483, March 23-27, 1998
• 4: Marcos K. Aguilera , Jeffrey C. Mogul , Janet L. Wiener , Patrick Reynolds , Athicha Muthitacharoen, Performance debugging for distributed systems of black boxes, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 5: A. Anandkumar, C. Bisdikian, and D. Agrawal. Tracking in a Spaghetti Bowl: Monitoring Transactions Using Footprints. Technical Report RC24422 (W0711-107), IBM Research, Yorktown Heights, NY 10598, November 2007. http://domino.watson.ibm.com/library/CyberDig.nsf/home.
• 6: Paul Barham , Austin Donnelly , Rebecca Isaacs , Richard Mortier, Using magpie for request extraction and workload modelling, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.18-18, December 06-08, 2004, San Francisco, CA
• 7: A. Benveniste, S. Haar, E. Fabre, and C. Jard. Distributed monitoring of concurrent and asynchronous systems. In ATPN-Workshop on Discrete Event Sys. Control, 2004.
• 8: Andrea J. Borr, Transaction monitoring in ENCOMPASS: reliable distributed transaction processing, Proceedings of the seventh international conference on Very Large Data Bases, p.155-165, September 09-11, 1981, Cannes, France
• 9: Rainer E. Burkard, Selected topics on assignment problems, Discrete Applied Mathematics, v.123 n.1-3, p.257-302, 15 November 2002 [doi>10.1016/S0166-218X(01)00343-2]
• 10: K. Mani Chandy , Leslie Lamport, Distributed snapshots: determining global states of distributed systems, ACM Transactions on Computer Systems (TOCS), v.3 n.1, p.63-75, Feb. 1985 [doi>10.1145/214451.214456]
• 11: Mike Y. Chen , Anthony Accardi , Emre Kiciman , Jim Lloyd , Dave Patterson , Armando Fox , Eric Brewer, Path-based faliure and evolution management, Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation, p.23-23, March 29-31, 2004, San Francisco, California
• 12: Mike Y. Chen , Emre Kiciman , Eugene Fratkin , Armando Fox , Eric Brewer, Pinpoint: Problem Determination in Large, Dynamic Internet Services, Proceedings of the 2002 International Conference on Dependable Systems and Networks, p.595-604, June 23-26, 2002
• 13: Jonathan E. Cook , Alexander L. Wolf, Discovering models of software processes from event-based data, ACM Transactions on Software Engineering and Methodology (TOSEM), v.7 n.3, p.215-249, July 1998 [doi>10.1145/287000.287001]
• 14: R. Gallagher. Discrete Stochastic Processes. Springer, 1996.
• 15: D. Goossens and F. Spieksma. The Transportation Problem with Exclusionary Side Constraints. 4OR, 2007.
• 16: Mark Jerrum , Alistair Sinclair , Eric Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries, Journal of the ACM (JACM), v.51 n.4, p.671-697, July 2004 [doi>10.1145/1008731.1008738]
• 17: G. Lamperti and M. Zanella. Diagnosis of Active Systems: Principles and Techniques. Kluwer Academic Publishers, 2003.
• 18: E. Lawler. Combinatorial Optimization: Networks and Matroids. Dover Publications, 2001.
• 19: H. Liu, H. Zhang, R. Izmailov, G. Jiang, and X. Meng. Real-time Application Monitoring and Diagnosis for Service Hosting Platforms of Black Boxes. In IEEE Intl. Symposium on Integrated Network Management, pages 216--225, 2007.
• 20: K. Magoutis, M. Devarakonda, and K. Muniswamy-Reddy. Galapagos: Automatically Discovering Application-Data Relationships in Networked Systems. In IEEE Intl. Symposium Integrated Network Management, pages 701--704, 2007.
• 21: M. Mansouri-Samani and M. Sloman. Monitoring distributed systems. Network, IEEE, 7(6):20--30, 1993.
• 22: Celso L. Mendes , Daniel A. Reed, Monitoring Large Systems Via Statistical Sampling, International Journal of High Performance Computing Applications, v.18 n.2, p.267-277, May 2004 [doi>10.1177/1094342004038958]
• 23: P. Ostrand. Systems of distinct representatives, II. J. Math. Anal. Appl, 32:1--4, 1970.
• 24: Yannick Pencolé , Marie-Odile Cordier , Laurence Rozé, A decentralized model-based diagnostic tool for complex systems, Proceedings of the 13th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'01), p.95, November 07-09, 2001
• 25: Wei Peng , Tao Li , Sheng Ma, Mining logs files for data-driven system management, ACM SIGKDD Explorations Newsletter, v.7 n.1, p.44-51, June 2005 [doi>10.1145/1089815.1089822]
• 26: John P. Rouillard, Refereed Papers: Real-time Log File Analysis Using the Simple Event Correlator (SEC), Proceedings of the 18th USENIX conference on System administration, November 14-19, 2004, Atlanta, GA
• 27: M. Schmid, M. Thoss, T. Termin, and R. Kroeger. A Generic Application-Oriented Performance Instrumentation for Multi-Tier Environments. In IEEE Intl. Symposium on Integrated Network Management, pages 304--313, 2007.
• 28: B. Sengupta, N. Banerjee, A. Anandkumar, and C. Bisdikian. Non-Intrusive Transaction Monitoring Using System Logs. In Proc. of IEEE/IFIP Network Operations & Management Symposium (NOMS), Salvador, Brazil, April 2008.
• 29: R. Vaarandi and T. Tehnikaülikool. Tools and Techniques for Event Log Analysis. Tallinn Univ. of Technology Press, 2005.
• 30: L. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8(2):189--201, 1979.
• 31: Wil M. P. van der Aalst , B. F. van Dongen, Discovering Workflow Performance Models from Timed Logs, Proceedings of the First International Conference on Engineering and Deployment of Cooperative Information Systems, p.45-63, September 17-20, 2002

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Distributed systems

General Terms:
Performance, Theory

Keywords:
bipartite matching, maximum-likelihood tracking, semi-markov process, transaction monitoring