Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published December 2013 | Submitted
Journal Article Open

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

Abstract

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.

Additional Information

© 2013 Elsevier B.V. Received 10 February 2010, Revised 1 August 2011, Accepted 3 August 2013, Available online 24 August 2013. The authors thank R. Nunez Queija for discussions on the processor-sharing queue and Varun Gupta for discussions on the notion of convex order at the MAMA 2009 workshop.

Attached Files

Submitted - 1006.1674.pdf

Files

1006.1674.pdf
Files (386.6 kB)
Name Size Download all
md5:011d09880bad0858325226bacf60a12c
386.6 kB Preview Download

Additional details

Created:
August 22, 2023
Modified:
October 17, 2023