Signaling for decentralized routing in a queueing network

DOI10.1007/S10479-015-1850-4MaRDI QIDQ2095231zbMATH OpenOpenAlexFDO

Authors Yi Ouyang, Demosthenis Teneketzis

Publication date 9 November 2022

Published in Annals of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.0887

zbMATH Keywords

signalingqueueing networkscommon informationdecentralized systemnon-classical information structure

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Queues and service in operations research (90B22) Applications of Markov renewal processes (reliability, queueing networks, etc.) (60K20)

Abstract: A discrete-time decentralized routing problem in a service system consisting of two service stations and two controllers is investigated. Each controller is affiliated with one station. Each station has an infinite size buffer. Exogenous customer arrivals at each station occur with rate $lambda$. Service times at each station have rate $mu$. At any time, a controller can route one of the customers waiting in its own station to the other station. Each controller knows perfectly the queue length in its own station and observes the exogenous arrivals to its own station as well as the arrivals of customers sent from the other station. At the beginning, each controller has a probability mass function (PMF) on the number of customers in the other station. These PMFs are common knowledge between the two controllers. At each time a holding cost is incurred at each station due to the customers waiting at that station. The objective is to determine routing policies for the two controllers that minimize either the total expected holding cost over a finite horizon or the average cost per unit time over an infinite horizon. In this problem there is implicit communication between the two controllers; whenever a controller decides to send or not to send a customer from its own station to the other station it communicates information about its queue length to the other station. This implicit communication through control actions is referred to as signaling in decentralized control. Signaling results in complex communication and decision problems. In spite of the complexity of signaling involved, it is shown that an optimal signaling strategy is described by a threshold policy which depends on the common information between the two controllers; this threshold policy is explicitly determined.

Recommendations

• scientific article; zbMATH DE number 934840
• Optimal routing into two heterogeneous service stations with delayed information
• Decentralized control strategies for dynamic routing
• Optimal Routing Among ⋅/M/1 Queues with Partial Information
• Routing in queueing networks under imperfect information: stochastic dominance and thresholds

Cites work

• scientific article; zbMATH DE number 44107 (Why is no real title available?)
• scientific article; zbMATH DE number 934840 (Why is no real title available?)
• A decentralized routing control scheme for data communication networks
• A note on the hypercube model
• A simple dynamic routing problem
• Agreeing to disagree
• An approximate dynamic programming approach to decentralized control of stochastic systems
• Decentralized Stochastic Control with Partial History Sharing: A Common Information Approach
• Deciding Which Queue to Join: Some Counterexamples
• Join the shortest queue: Stability and exact asymptotics
• Markov Chains
• On Throughput Optimality With Delayed Network-State Information
• On distributed scheduling with heterogeneously delayed network-state information
• On the Assignment of Customers to Parallel Queues
• On the Optimality of the Generalized Shortest Queue Policy
• On the optimal assignment of customers to parallel servers
• On the optimal maintenance of systems and control of arrivals in queues
• Optimal Decentralized Control of Coupled Subsystems With Control Sharing
• Optimal control of a queueing system with two heterogeneous servers
• Optimal control of arrivals to queues with delayed queue length information
• Optimal control of service rates in networks of queues
• Optimal control of two interacting service stations
• Optimality of routing and servicing in dependent parallel processing systems
• Optimality of the shortest line discipline
• Routing in queueing networks under imperfect information: stochastic dominance and thresholds
• Understanding the marginal impact of customer flexibility

Cited in

(2)

• \(r\)-extreme signalling for congestion control
• Leveraging Indirect Signaling for Topology Inference and Fast Broadcast

This page was built for publication: Signaling for decentralized routing in a queueing network

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2095231)