Seeing through black boxes: Tracking transactions through queues under monitoring resource constraints

Animashree Anandkumar, Ting He, Chatschik Bisdikian, Dakshi Agrawal

Research output: Contribution to journalArticlepeer-review


The problem of optimal allocation of monitoring resources for tracking transactions progressing through a distributed system, modeled as a queueing network, is considered. Two forms of monitoring information are considered, viz., locally unique transaction identifiers, and arrival and departure timestamps of transactions at each processing queue. The timestamps are assumed to be available at all the queues but in the absence of identifiers, only enable imprecise tracking since parallel processing can result in out-of-order departures. On the other hand, identifiers enable precise tracking but are not available without proper instrumentation. Given an instrumentation budget, only a subset of queues can be selected for the production of identifiers, while the remaining queues have to resort to imprecise tracking using timestamps. The goal is then to optimally allocate the instrumentation budget to maximize the overall tracking accuracy. The challenge is that the optimal allocation strategy depends on accuracies of timestamp-based tracking at different queues, which has complex dependencies on the arrival and service processes, and the queueing discipline. We propose two simple heuristics for allocation by predicting the order of timestamp-based tracking accuracies of different queues. We derive sufficient conditions for these heuristics to achieve optimality through the notion of the stochastic comparison of queues. Simulations show that our heuristics are close to optimality, even when the parameters deviate from these conditions.

Original languageEnglish (US)
Pages (from-to)1090-1110
Number of pages21
JournalPerformance Evaluation
Issue number12
StatePublished - 2013

All Science Journal Classification (ASJC) codes

  • Software
  • Modeling and Simulation
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'Seeing through black boxes: Tracking transactions through queues under monitoring resource constraints'. Together they form a unique fingerprint.

Cite this