TY - JOUR
T1 - Seeing through black boxes
T2 - Tracking transactions through queues under monitoring resource constraints
AU - Anandkumar, Animashree
AU - He, Ting
AU - Bisdikian, Chatschik
AU - Agrawal, Dakshi
N1 - Funding Information:
Ting He is a Research Staff Member at IBM T. J. Watson Research Center, Yorktown Heights, NY. She received the Ph.D. degree and the M.S. degree, both in Electrical Engineering from the School of Electrical and Computer Engineering, Cornell University, in 2007 and the B.S. degree in Computer Science from Peking University, China, in 2003. At IBM, Ting works in the Network Analytics Research Group and has acted as task lead in the ITA program funded by ARL and MoD and the NIST ARRA program funded by NIST. Previously at Cornell (2003–2007), Ting was a member of the Adaptive Communications & Signal Processing Group (ACSP) under the supervision of Prof. Lang Tong. Before joining Cornell, she worked as an undergraduate research assistant in Micro Processor Research & Development Center of Peking University from 2001 to 2003, during which period she participated in the development of Unicore System as part of the National 863 Plan of China.
Funding Information:
Animashree Anandkumar is a faculty at the EECS Dept. at U.C.Irvine. Her research interests are in the area of large-scale machine learning and high-dimensional statistics with a focus on learning probabilistic graphical models and latent variable models. She is the recipient of the Microsoft Faculty Fellowship, ARO Young Investigator Award, NSF CAREER Award, IBM Fran Allen Ph.D. fellowship, and paper awards from the ACM SIGMETRICS and IEEE Signal Processing societies. She has been a visiting faculty at Microsoft Research New England and a postdoctoral researcher at the Stochastic Systems Group at MIT. She received her B.Tech in Electrical Engineering from IIT Madras and her Ph.D. from Cornell University.
PY - 2013
Y1 - 2013
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84887313259&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84887313259&partnerID=8YFLogxK
U2 - 10.1016/j.peva.2013.08.003
DO - 10.1016/j.peva.2013.08.003
M3 - Article
AN - SCOPUS:84887313259
SN - 0166-5316
VL - 70
SP - 1090
EP - 1110
JO - Performance Evaluation
JF - Performance Evaluation
IS - 12
ER -