Resource allocation in one-dimensional distributed service networks with applications
File(s)1901.02414v4.pdf (796.43 KB)
Accepted version
Author(s)
Type
Journal Article
Abstract
We consider assignment policies that allocate resources to users, where both resources and users are located on
a one-dimensional line [0, ∞). First, we consider unidirectional
assignment policies that allocate resources only to users located
to their left. We propose the Move to Right (MTR) policy, which
scans from left to right assigning nearest rightmost available
resource to a user, and contrast it to the Unidirectional GaleShapley (UGS) matching policy. While both policies among all
unidirectional policies, minimize the expected distance traveled
by a request (request distance), MTR is fairer. Moreover, we
show that when user and resource locations are modeled by
statistical point processes, and resources are allowed to satisfy
more than one user, the spatial system under unidirectional
policies can be mapped into bulk service queueing systems, thus
allowing the application of many queueing theory results that
yield closed form expressions. As we consider a case where
different resources can satisfy different numbers of users, we
also generate new results for bulk service queues. We also
consider bidirectional policies where there are no directional
restrictions on resource allocation and develop an algorithm for
computing the optimal assignment which is more efficient than
known algorithms in the literature when there are more resources
than users. Finally, numerical evaluation of performance of
unidirectional and bidirectional allocation schemes yields design
guidelines beneficial for resource placement.
a one-dimensional line [0, ∞). First, we consider unidirectional
assignment policies that allocate resources only to users located
to their left. We propose the Move to Right (MTR) policy, which
scans from left to right assigning nearest rightmost available
resource to a user, and contrast it to the Unidirectional GaleShapley (UGS) matching policy. While both policies among all
unidirectional policies, minimize the expected distance traveled
by a request (request distance), MTR is fairer. Moreover, we
show that when user and resource locations are modeled by
statistical point processes, and resources are allowed to satisfy
more than one user, the spatial system under unidirectional
policies can be mapped into bulk service queueing systems, thus
allowing the application of many queueing theory results that
yield closed form expressions. As we consider a case where
different resources can satisfy different numbers of users, we
also generate new results for bulk service queues. We also
consider bidirectional policies where there are no directional
restrictions on resource allocation and develop an algorithm for
computing the optimal assignment which is more efficient than
known algorithms in the literature when there are more resources
than users. Finally, numerical evaluation of performance of
unidirectional and bidirectional allocation schemes yields design
guidelines beneficial for resource placement.
Date Issued
2020-09-01
Date Acceptance
2020-05-19
Citation
Performance Evaluation, 2020, 142, pp.1-25
ISSN
0166-5316
Publisher
Elsevier
Start Page
1
End Page
25
Journal / Book Title
Performance Evaluation
Volume
142
Copyright Statement
© 2020 Elsevier Ltd. All rights reserved. This manuscript is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International Licence http://creativecommons.org/licenses/by-nc-nd/4.0/
Sponsor
IBM United Kingdom Ltd
Identifier
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000563537600004&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=1ba7043ffcc86c417c072aa74d649202
Grant Number
4603317662
Subjects
Science & Technology
Technology
Computer Science, Hardware & Architecture
Computer Science, Theory & Methods
Computer Science
Resource allocation
1-D service network
Queueing theory
Distributed network
Dynamic programming
QUEUE
Publication Status
Published
Article Number
ARTN 102110
Date Publish Online
2020-06-01