One-dimensional Service Networks and Batch Service Queues

Philippe Nain (1) , Nitish K Panigrahy (2) , Prithwish Basu (3) , Don Towsley (2)

1 DANTE - Dynamic Networks : Temporal and Structural Capture Approach
2 UMass Amherst - University of Massachusetts [Amherst]
3 Raytheon BBN Technologies

A proliferation of smart devices, computational and storage resources is predicted to continue aggressively in the near future. Such "networked" devices and resources which are distributed in a physical space and provide services are collectively referred to as a distributed service network. Assigning users or applications to available resources is important to sustain high performance of the distributed service network. In this work, we consider a one-dimensional service network where both users and resources are located on a line, and analyze a unidirectional assignment policy Move To Right (MTR), which sequentially assigns users to resources available to their right. We express the communication cost for a user-resource assignment as an increasing function of the distance traveled by the user request (request distance) and analyze the expected communication cost for the service network when locations of users and resources are modeled by different spatial point processes. We use results from literature that map the request distance of an assigned user in a one-dimensional service network to the sojourn time of a customer in an exceptional service accessible batch queueing system. We compute the Laplace-Stieltjes transform of the sojourn time distribution for this queueing system for Poisson distributed users with general inter-resource distance distributions and in the process also generate new results for batch service queues. Unlike previous work [32] our framework not only captures the first-order moment of the request distance, but also the request distance distribution itself, thus allowing us to compute the expected communication cost under different cost models.

Domaines: Réseaux et télécommunications [cs.NI]; Performance et fiabilité [cs.PF]

Philippe Nain, Nitish K Panigrahy, Prithwish Basu, Don Towsley. One-dimensional Service Networks and Batch Service Queues. Queueing Systems, 2021, ⟨10.1007/s11134-021-09703-0⟩. ⟨hal-03066179v2⟩