Copyright © (2008) by Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distrubuted for profit or commericial advantage. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee.
The problem of tracking end-to-end service-level transactions in the absence of instrumentation support is considered. The transaction instances are assumed to transition according to a state-transition model and the goal is to track individual transactions using footprints they generate. The footprints contain the state and time-stamp information, but not necessarily any tokens uniquely identifying the transaction instance that generated the footprint. Assuming a semiMarkov process model for the state transitions, the transaction instances are tracked probabilistically by matching them to the available footprints according to the maximum-likelihood (ML) criterion. For the special case of a two-state system, it is shown that the optimal tracking rule reduces to a minimum weight bipartite matching. Under the ML-rule, it is shown that the probability that all the instances are matched correctly is the minimum when the transition times are i.i.d. exponentially or uniformly distributed. For a general SMP with an acyclic state-transition digraph, a constructive proof shows that the ML-rule reduces to decentralized matching in two-state systems constructed through a recursive one-step reachability state decomposition and conducting independent matching in these two-state systems. The tightness of the theoretical tracking bounds, the influence of the number of interleaving instances on the tracking probability and the robustness of the proposed solutions to variations in the underlying probability distributions are explored through simulations.
By: Animashree Anandkumar; Chatschik Bisdikian; Dakshi Agrawal
Published in: ACM Performance Evaluation Review, volume 36, (no 1), pages 133-44 in 2008
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .