Marianna Belotti

Sofiane Kirati

Stefano Secci

Bitcoin Pool-Hopping Detection

In the Bitcoin blockchain, rewarding methods for remunerating miners participating in a pool have to meet certain requirements in order to guarantee the proper functioning of the cryptocurrency ecosystem. In particular, these allocation rules reward pool participants in proportion to their contribution in the transaction validation process. Deployed rewarding methods met fairness concerns at the expense of vulnerability to miners exploiting pools' attractiveness for deciding when to mine for a pool and when to 'hop' to another one resulting more attractive: a phenomenon called pool-hopping. The most used score-based methods are designed to prevent this practice, but are not completely hopping proof.

In this work, we propose a methodology to analyze the pool-hopping phenomenon, focusing on the detection of poolhoppers. Analyzing those Bitcoin transactions that pools create for rewarding its participants, it is possible to determine time epochs where miners worked. Thus, we analyze those miners that have worked intermittently for pools adopting a rewarding system which pays out for each validated block. This evaluation leads us qualifying the miners that have hopped along with their hopping behavior and financial performance.

I. INTRODUCTION

In the Bitcoin network, mining is the procedure through which miners can earn crypto coins by finding solutions to a computationally hard puzzle which validates a block of bitcoin transactions [START_REF] Nakamoto | Bitcoin: A peer-to-peer electronic cash system[END_REF]. In order to be rewarded on a regular basis, miners can decide to cooperate reducing the uncertainty of the remunerations over time. Cooperation results in the formation of pools, which receive a reward for the validated block and split it among the participants.

The Bitcoin monetary policy establishes the reward amount one receives once it validates a block (12.5 BTC, valid until the third halving scheduled for 29 May 2020 when the block mining reward is decreasing to 6.25 BTC) -noting that a block can contain more than 2000 transactions, while respecting the block size limit of 1 MB. There exist several functions which reallocate block-validation bitcoins inside a pool for remunerating its miners. These rewarding methods have to meet certain requirements in order to guarantee the proper functioning of the ecosystem. The aim of forming pools is to share efforts and rewards thus, participants should be rewarded in a fair manner with respect to their contribution to the pool, i.e., proportionally to the hashing power invested in the pool. Original simple rewarding methods met this fairness criterion at the expense of vulnerability to some miners strategic behaviors. Schrijvers et al. describe in [START_REF] Schrijvers | Incentive compatibility of bitcoin mining pool reward functions[END_REF] weaknesses of pools' remuneration systems to withholding strategies [START_REF] Bag | Bitcoin block withholding attack: Analysis and mitigation[END_REF].

We do address in this work the miners' strategy of exploiting pools' attractiveness to decide when to mine for a pool and when to leave it for joining another one. This practice, known as pool-hopping, has been deeply studied in [START_REF] Rosenfeld | Analysis of bitcoin pooled mining reward systems[END_REF], showing new (score-based) methods specifically designed to prevent the phenomenon. The most used ones are not completely hopping proof since pool participants may take advantage of changes in system or pool parameters for their own benefit. The gain of using such a strategy is a higher reward than the fair share for a miner's contribution. Since a pool with a given computational power receives a constant reward, such a behavior benefits pool-hoppers to the detriment of those miners who mine continuously. Thus, hoppers detection might be as useful for pool-operators as it is for the miners themselves (mining pools are managed by a pool manager, also known as pool operator).

Bitcoin public nature provides us with both generation transactions [START_REF] Antonopoulos | Mastering Bitcoin: unlocking digital cryptocurrencies[END_REF] and transactions used by pools to remunerate their participants. The first are those transactions by means of which new bitcoins are generated and issued in the system. The second are the so called "rewarding transactions" which are transferring the funds received through the generation process to pool participants in a chain of ownership [START_REF] Ametrano | Hayek Money: The Cryptocurrency Price Stability Solution[END_REF], i.e., new minted bitcoins are transferred from pools' addresses (input) to miners' ones (output) in the form of Unspent Transaction Output, UTXO [START_REF]Transaction[END_REF]. Proper analysis of the public ledger can reveal a lot of information on the network users. Deanonymization techniques applied on a selected set of users do contribute in enhancing the quality of the extracted information. In our analysis, the Bitcoin actors we are interested in are the ones involved in the rewarding transactions, i.e., pools and miners, remunerated according to pools policies; the first step of our work is determining the related user network [START_REF] Koshy | An analysis of anonymity in bitcoin using p2p network traffic[END_REF].

Rewarding methods with direct correspondences between block validation and miners' payout do help in hoppers detection. Through a targeted analysis of the transactions ledger, it is possible to place a miner -intent on working for a pool -within a time interval denoted as epoch. This time period is nothing more than an estimate of a miner's working time for a given pool. Hoppers detection consists in comparing miners' epochs in different pools. All the actors in a pool have full knowledge of the internal mining activities carried out over time, which is not the case for any user external to pool. Once pool-hoppers have been identified among all the miners interacting with multiple pools, it is possible to describe the hopping evolution over time.

The paper is organized as follows: Section II provides an overview on the rewarding systems used in the Bitcoin blockchain network and addresses pool-hopping practice -we focus our analysis on those score-based methods that are not completely hopping proof. In Section III we present the procedure for determining the user sub-network resulting from the analysis of the generation, transferring and rewarding transactions -the sub-network we are interested in is the one showing direct connections between pools and users that are receiving new minted bitcoins. Section IV is devoted to hoppers detection. Section V presents the measurement results. We conclude the work in Section VI.

II. REWARDING METHODS AND POOL-HOPPING

The Bitcoin validation procedure consists in computing hashes from a given input data-string until the hash value meets a predefined threshold. The latter, known as difficulty target -we refer to as D -represents the value at which all transactions blocks are validated every 10 minutes, on average. The difficulty D is adjusted every 2016 blocks in accordance with Bitcoin policies. Whenever a valid hash is found, the miner or the pool which release the valid block is rewarded with an amount of coins denoted by B. This amount halves approximately every 4 years.

Concerning mining pools, the pool operator pays out poolmembers based on how much qualified work they perform. This work is quantified with the number of submitted shares, which are near to valid solutions: for getting a share, miners participating in a pool try to solve the original cryptopuzzle, but with a looser constraint on the hash they have to compute. Therefore, the pool manager redistributes B among miners according to the number of submitted shares. A variety of rewarding methods have been designed to fairly remunerate miners in proportion to their work. However, some methods are more vulnerable than others to miners' attempts of achieving a higher reward than the fair allocation.

A. Rewarding Methods

Original no-longer used rewarding methods [START_REF] Rosenfeld | Analysis of bitcoin pooled mining reward systems[END_REF] were paying out according to a division into rounds, where a round is the time elapsed between two different block validations performed by the same pool. Thus, pool distributes the block reward among miners at round end, in proportion to their contribution within the round. New methods replace such a round-based remuneration opting for the attribution of a score to each share. Score-based methods register the time of a share submission, assign a value to the share according to a scoring function and remunerate the submitter correspondingly. Thus, rewards calculation is no more linked to the concept of round but it is based on the scoring systems in use. However, payouts are still executed on a round basis.

Besides rewarding fairness, score-based methods also offer pool-hopping resistance. Meni Rosenfeld lists in [START_REF] Rosenfeld | Analysis of bitcoin pooled mining reward systems[END_REF] several score-based rewarding systems. We describe in the following the two most popular methods in use nowadays.

1) Pay-Per-Last-N-Shares (PPLNS) method [START_REF] Rosenfeld | Analysis of bitcoin pooled mining reward systems[END_REF]: It represents an allocation rule rewarding miners for their recently submitted shares -eventually computed at different rounds. The block reward B, instead of being distributed only among actual round participants, can also be assigned to those miners that have submitted shares in a previous round.

Then, for short actual rounds, the rewarding calculation may consider also shares submitted in previous rounds. Note that, with the PPLNS system it can happen that some submitted shares may not be considered for the reward calculation (i.e., shares in long actual rounds). N varies with the difficulty parameter D; it can be up to twice D (rounded down to integer), as an upper-bound threshold. More accurate implementations tend to set N < 2D; e.g., the author in [START_REF] Rosenfeld | Analysis of hashrate-based double spending[END_REF] proposes to score shares as the inverse of D, and determines N as a given portion of the score, hence N ≤ D.

2) Slush method: Slush pool [START_REF] Pool | Reward System[END_REF] has been the first mining pool developing a rewarding method aimed at combating pool-hopping. Block rewards are divided in proportion to the score miners obtained with their reported share(s) in the rounds. Slush's scoring system dynamically calculates a score for a specified share according to its submission time. More precisely, the score at time t 0 for a share s submitted at time t s is given by:

score(s, t 0 ) = exp t s -t 0 Λ ( 1
)
where Λ is a constant value representing the speed at which the score decreases over time. An exponentially decreasing scoring is well suited due to its invariance to time shift.

B. Pool-Hopping

Pool-hopping is a strategic behavior influenced by the attractiveness of mining in terms of expected payoffs [START_REF] Raulo | Optimal pool abuse strategy[END_REF]. In other words, pool-hopping consists in mining for a pool only when its attractiveness is high and leaving it when it is not (i.e., directing computing power towards another pool).

Meni Rosenfeld shows in [START_REF] Rosenfeld | Analysis of bitcoin pooled mining reward systems[END_REF] that pools using proportional systems encourage this practice in the sense that poolhopping results more profitable than mining continuously. Since for proportional methods each share is paid out according to the total number of submitted shares in the round, the longer is the round the less is the reward per share. Each share payoff corresponds to B S , where S is the total number of shares submitted to the pool during a round. Thus, submitting shares to a pool as long as the rounds are short and then hopping elsewhere results in a higher gain than the fair share [START_REF] Schrijvers | Incentive compatibility of bitcoin mining pool reward functions[END_REF]. What makes this practice, known as early mining, feasible is the miners' knowledge of the round start time and the number of shares taken into account for the reward calculation. PPLNS and Slush methods propose scoring functions that do not encourage early mining practice, thus the pools are preventing hopping behaviors on round length basis.

However, as the Slush score is a function of the time elapsed since a share submission, pools' attractiveness is eventually affected by the hash-rate fluctuations over time. Pools' hashing power directly influences the number of shares found and the round length. In addition, both PPLNS and Slush systems' 'hoppability' is affected by difficulty (D) and reward (B) adjustments. Therefore, advanced poolhopping strategies are possible for both Slush and basic PPLNS implementations. Nevertheless, the two methods present different levels of hoppability as described in [START_REF] Rosenfeld | Analysis of hashrate-based double spending[END_REF].

III. USER SUB-NETWORK INFERENCE PROCESS

Bitcoin transactions move funds from one or more 'inputs' to one or more 'outputs' containing all the references of previous and next owners. Users receive bitcoins in the form of unspent transaction output (UTXO) in their addresses, i.e., strings identifying sources and destinations for bitcoin payments. In order to be spent, funds contained in the output of a transaction must turn into the input of a new one. Inputs and outputs must match in the sense that the entire value of the previous transaction(s) has to be transferred. Thus, whenever a user aims at sending an amount lower than the UTXO value, a second output containing a changing address is added. That is, a bitcoin address held by the sender appears as an output with the purpose of transferring funds back.

A. Coinbase, rewarding and transferring transactions

Each transactions block contains a generation transaction remunerating the pool or the miner that validates it. These type of transactions does not specify any previous UTXO to spend, its input field (denoted as coinbase) contains arbitrary data; generation transactions, also known as coinbase transactions, provide funds that cannot be spent for at least 100 confirmed blocks. Due to this requirement, Bitcoin system rewards only for valid blocks in the longest chain (i.e., the longest blockchain branch). While mining pools are financed by coinbase transactions, miners are remunerated through ordinary transactions we denote as rewarding transactions. Ideally, they should transfer the coinbase UTXO, however this is not always the case. Some pools use additional transactions -we refer to as transferring transactions -that move funds to specified addresses within the pool, which reward miners later on.

All these transactions are publicly readable from the blockchain ledger and can be easily gathered through Bitcoin-Core [START_REF]BTC Core[END_REF]. This information leads to construct the transaction sub-network [START_REF] Koshy | An analysis of anonymity in bitcoin using p2p network traffic[END_REF] representing the flow of bitcoins between a specific subset of transactions -of coinbase, rewarding and transferring types -over time. Fig. 1 example shows pool-miners interactions where coinbase transactions are inputs of transferring transactions whose outputs consist in rewarding ones. Arrows represent the funds flow.

The topology of Fig. 1 example synthesizes a generic view of the Bitcoin network, where one may detect the relationships between various input and output addresses. For coinbase, rewarding and transferring transactions, the addresses involved certainly belong to pools and miners however, it is not known to which user they belong exactly since each of them can have multiple addresses. Moreover, it is considered a good practice for confidentiality to generate and use new addresses for each operation on the network. As hoppers detection requires the analysis of the interactions among Bitcoin specific users, it is necessary to map each bitcoin actor with its associated addresses.

B. Address-User Mapping Procedure

The address-user mapping problem can be solved using two basic heuristics introduced in [START_REF] Reid | An analysis of anonymity in the bitcoin system[END_REF], which derive from the expert knowledge of Bitcoin protocols and common practices. The mapping procedure we use is based on the concatenated application of the two heuristics. The first heuristic, addressing transaction inputs only, exploits the concept of multi-input transactions: it assumes that all the inputs in a transaction belong to the same bitcoin user. This heuristic results reasonable in its simplicity since (i) different users likely very rarely collaborate in a single transaction, and (ii) very often it happens that users move funds from their multiple addresses to one or multiple deposit accounts. The second heuristic deals with changing addresses: it associates input addresses with output ones when they result to be completely new (i.e., they never appeared in the blockchain before).

Therefore, applying the mapping procedure one can derive the user sub-network from the address sub-network. The relationship between addresses can be easily inferred from the transactions sub-network; Fig. 2 shows the address subnetwork corresponding to the Fig. 1 example. Once the address sub-network is derived, addresses are associated with their users following the two heuristics; Fig. 3 shows an instance of user sub-network for the given example.

It is not possible to obtain a perfectly true user subnetwork, since heuristics are not perfect and addresses do not contain any information about their owners. In order to maximize the precision, due to the limited number of coinbase, transferring and rewarding transactions with respect to the overall volume of transactions, we have applied the mapping procedure to the entire transaction network (including ordinary transactions as well). Doing so, we can provide an accurate representation of miners and pools interactions, since we are associating with these specific users the highest possible number of employed addresses. The application of such deanonymization techniques for the mapping allows us building an interaction network between pools and miners. Pool-hopping consists in mining for two or more pools during a round, thus hoppers submitting shares to multiple pools are remunerated accordingly by multiple pools. Hoppers detection requires the analysis of those miners who are connected to several pools.

IV. HOPPERS DETECTION

The previous section provides us with those network pre-processing steps for detecting pool-hoppers. From the constructed user sub-network it is possible to select those miners that are remunerated from multiple pools. In order to determine whether a miner that submits shares to more than one pool is really implementing a hopping strategy, it is necessary to focus on its rewarding transactions. Our analysis addresses those pools adopting rewarding methods which are paying out miners on a round basis.

A. Simplistic case

For pools using per-round rewarding systems, rewarding transactions should be ideally linked to the corresponding rounds they are paying for. This link could be found in their inputs, namely in the coinbase transactions providing pools with the rewards that have to be redistributed. It would then be possible, by analyzing the rewarding transactions, to place a miner in a certain round. In Fig. 4 we show how to identify miners' working period: a miner rewarded at time A is associated with the corresponding round of pool A that is marked in yellow. Then, considering multiple pools and their rounds, it would be enough to check if the same miner is present in two overlapping rounds of different pools. The procedure results quite trivial once pools' rewarding transactions are ordered according to their corresponding rounds, that is, in accordance with the corresponding coinbase transactions.

In a 2-pool case, if the same miner is present in two consecutive (ordered) rewarding transactions belonging one to a pool and one to another one, we can declare it as a hopper. There may be doubtful situations whenever the same miner is found in two rewarding transactions of different pools which are not directly consecutive (i.e., after ordering we could have two transactions created by pool A, one created by pool B and the same miner present in the first and third transaction). In this cases it is mandatory to analyze the rounds length to establish if the miner adopted or not a hooping strategy.

B. Realistic case

In reality, pools do not associate exactly a paying transaction to each round. Miners receive their payouts once they cross a predefined sending threshold (Slush pool adopts a threshold of 0.001 BTC [START_REF] Pool | Reward System[END_REF]). This means that in reality pools pay for miners' work on multiple rounds with a single rewarding transaction. In Fig. 5 pool A is rewarding a miner for its work in two rounds. Rewarding transactions no longer use the reward provided by a single coinbase but they have several generation transactions as inputs. In this way, it is no longer possible to place a miner in its working round.

Miners paid out with the rewarding transactions can be placed within a time interval that we denote as "epoch". This time period can coincide with one or more rounds. We set the beginning of an epoch with the oldest coinbase used as an input in the rewarding transaction. The epoch ends with the round allowing miners to reach the sending threshold, namely the round closing about 100 blocks before the one in which the rewarding transaction takes place. As shown in Fig. 5 the epoch end coincides with the last round end. The epoch start depends on the coinbase transactions used in the rewarding transaction. Pools may pay out miners with funds generated during the rounds they work for or they may use older coinbase transaction as in Fig. 5. Note that we assume payments are executed as soon as funds are available (after 100 confirmations), which results in neglecting the processing time for the rewarding transactions.

By positioning miners in epochs, we cannot identify the exact rounds they work for. They may have worked continuously in all the rounds within the epoch or they could have worked intermittently. The idea is always to check if a miner is present in two overlapping time periods, however it can be defined as a hopper with a certain probability depending on epochs' length. As for the ideal case, Rewarding transactions can be sorted by membership blocks, that is, ordering procedure refers to the coinbase transactions corresponding to epoch ends. For the 2-pool case in which a miner is found in two consecutive rewarding transactions with different creators, we can conclude with any doubt that the miner is a pool-hopper. This is due to epoch definition, since it ends with that round in which miners submitted the number of shares necessary to reach the threshold value. Hence, there is the certainty of miners' presence in the epochs' final rounds.

By considering only consecutive transactions, other cases where hopping is possible are overlooked. First of all, this approach detect only hoppers in epochs' final rounds without considering the other rounds within them. Moreover, as in the simplistic case, we can have hoppers paid out in two rewarding transactions that are not adjacent. Epochs length could help us in detecting miners who are likely to hop, thus in this cases we are talking about potential hoppers.

V. MEASUREMENT RESULTS

We analyze the user sub-network involving miners interacting with the two most popular mining pools adopting score-based rewarding methods: Slush pool [START_REF] Pool | Reward System[END_REF] and Kano pool [START_REF] Btc | Statistics[END_REF]. Since these pools opt for a per-round rewarding system, we can apply the hopping detection technique showed in Section IV. We aim at capturing real-hoppers (i.e., miners that have definitely hopped) and the result of their behavior. Thanks to the user sub-network, we can describe the phenomenon evolution over a predetermined time window.

The analyzed period is April 6-20, 2016, chosen for its massive transactions flow (over 5 millions transactions) such that Kano pool recorded its maximum hashing power [START_REF] Btc | Statistics[END_REF]: with a substantial number of miners attracted in joining the pool it has been a remarkable period for hopping opportunities.

First, we detect all the miners, interacting with the two pools, that can potentially adopt a hopping strategy. Afterward, we capture the real-hoppers among them. Moreover, we perform a daily analysis on the number of hoppers and the number of 'hops' made, both globally and individually. Fig. 6 captures the interactions of the miners with Kano and Slush pools (represented by blue nodes). Overall, 43 pool-hoppers were detected within a population of 69 miners active with the two pools (26 miners are not hopping within the time period, thus they are mining continuously for one of the two pools), and an approximate global population of 150.000 miners. Fig. 7 shows the trend of the number of pool-hoppers and their hops during the considered 15 days. Fig. 8 further characterizes the phenomenon on a daily basis, showing for each of the identified hoppers the number of hops per day. We can roughly spot 3 different types of hopper: (i) frequent hoppers, miners that opt for a hopping strategy more than 10 times (e.g., #0, #3, #4), (ii) occasional hoppers, performing a limited number of hops, less than 10 times (e.g., #6, #7, #14), and (iii) changing-pool hoppers, miners that hop just once in the time window (e.g., #19, #20, #21). Changing-pool hoppers may have simply changed the pool to work for, since they do not present an intermittent behavior. Frequent and occasional hoppers represent together the 46.4% of the hopping miners, while 11 miners perform only a single hop. In addition we quantify the hopping frequency for those miners that are changing pool more than 5 times in the observed period. Fig. 9 presents the distribution of the inter-hopping times (i.e., the time elapsing between two successive hops performed by the same hopper), with boxplots (reporting a quartile box, minimum and maximum) indicating over the number of hops. Roughly half of the miners shows a median time less than 12 hours, with small variance, while the other half shows a higher median with an inter-quartile range of many hours. There is no evidence of the adoption of a strict hard-coded frequency, hence the hopping decision appears to be event-based as expectable.

Moreover, we are interested in quantifying the advantage in hopping. The distribution of hoppers' revenues over the time window is presented in Fig. 10 with boxplots; the hoppers' order is the same than the one in Fig. 8; for some hoppers, only few transactions exist and in that case instead of the boxplot only few points are plotted. The last two boxplots on the right-side of Fig. 10 cover all hoppers together and all static miners (that mine continuously without hopping) in the time period; we find a median transaction reward 3 times higher for hopping miners than for static ones. This highlights a very important gain justifying poolhopping; note that miners' computational power cannot be inferred from the ledger, and in practice for pool-hoppers it may significantly differ from that of the 'typical' miner.

Finally, we report in Fig. 11 the correlation between the number of hops and the Bitcoin (USD) price evolution over the 15 days; we compute the average Bitcoin price and the number of hops performed within a time window of two hours. No evident correlation between the two distributions emerges, i.e., we find here a confirmation that pool-hopping strategies do not appear to be hard-coded in miners behavior as a function of the Bitcoin actual value.

VI. SUMMARY

This paper addresses the issue of pool-hopping phenomena detection for round base rewarding systems adopted by the Slush and Kano pools. For this purpose we use known deanonymization techniques in order to identify miners and pools type of users of the Bitcoin blockchain. We propose a particular hoppers detection technique based on rewarding transactions ordering.

Our analysis determines that the hopping phenomenon is relatively limited in a time window which could have led to a high hopping propensity (only 0.02% of the miners did perform pool-hopping between the two selected pools). We show that hoppers' rewards significantly exceed those of static miners.

Besides these facts, we have also determined that poolhoppers have disparate behaviors, likely not correlated, and not dependent on the actual value of the cryptocurrency. This suggests that there may not be a shared methodology to implement a hopping strategy, and that pool-hoppers do proceed on a do-it-in-your-own, manual, fashion.

Fig. 1 :

 1 Fig. 1: Transaction sub-network. Each arrow is labeled with sender's address. CBtx, Trtx, Rewtx are respectively coinbase, transferring and rewarding transactions.

Fig. 2 :

 2 Fig. 2: Address sub-network related to Fig. 1 example.

Fig. 3 :

 3 Fig. 3: User sub-network related to Fig. 1 example.

Fig. 4 :

 4 Fig. 4: Simplistic miners' positioning. Blocks are indicated with gray boundaries. Vertical lines associate each round end with the corresponding rewarding transaction.

Fig. 5 :

 5 Fig. 5: Realistic miners' positioning.

Fig. 6 :

 6 Fig. 6: Pool-miners graph representation. The left blue node is Kano pool and the right blue node is Slush pool. Detected pool-hoppers are highlighted in red. Edge thickness and color depend on the frequency of users interactions.

Fig. 7 :

 7 Fig. 7: Daily number of hoppers and hops. transaction ordering should simplify the detection procedure.Rewarding transactions can be sorted by membership blocks, that is, ordering procedure refers to the coinbase transactions corresponding to epoch ends. For the 2-pool case in which a miner is found in two consecutive rewarding transactions with different creators, we can conclude with any doubt that the miner is a pool-hopper. This is due to epoch definition, since it ends with that round in which miners submitted the number of shares necessary to reach the threshold value. Hence, there is the certainty of miners' presence in the epochs' final rounds.By considering only consecutive transactions, other cases where hopping is possible are overlooked. First of all, this approach detect only hoppers in epochs' final rounds without considering the other rounds within them. Moreover, as in the simplistic case, we can have hoppers paid out in two rewarding transactions that are not adjacent. Epochs length could help us in detecting miners who are likely to hop, thus in this cases we are talking about potential hoppers.

Fig. 8 :

 8 Fig. 8: Heat map: daily hopping intensity per hopper.

Fig. 9 :

 9 Fig. 9: Inter-hopping time boxplot distributions (logscale).

Fig. 10 :

 10 Fig. 10: Boxplot distributions of rewarding transactions BTC values (logscale).

Fig. 11 :

 11 Fig. 11: Correlation plot: BTC price vs number of hops.


Nitish K Panigrahy
email: nitish@cs.umass.edu

Prithwish Basu
email: prithwish.basu@raytheon.com

Philippe Nain N
email: philippe.nain@inria.fr

Don Towsley
email: towsley@cs.umass.edu

Ananthram Swami
email: ananthram.swami@mail.mil

Kevin S Chan
email: kevin.s.chan.civ@mail.mil

Kin K Leung
email: kin.leung@imperial.ac.uk

Resource Allocation in One-dimensional Distributed Service Networks

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 the nearest available resource located to the right of a user, and contrast it to the Unidirectional Gale-Shapley (UGS) matching policy. While both policies among all unidirectional policies, minimize the expected distance traveled by a request, 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.

I. INTRODUCTION

The past few years have witnessed significant growth in the use of distributed network analytics involving agile code, data and computational resources. In many such networked systems, for example, Internet of Things [START_REF] Atzori | The Internet of Things: A Survey[END_REF], a large number of computational and storage resources are widely distributed in the physical world. These resources are accessed by various end users/applications that are also distributed over the physical space. Assigning users or applications to resources efficiently is key to sustained high-performance operation of the system.

In some systems, requests are transferred over a communication network to a server that provides a needed resource. In other systems, servers are mobile and physically move to the user making a request. Examples of the former type of service include accessing storage resources over a wireless network to store files and requesting computational resources to run image processing tasks; an example of the latter type of service is the arrival of ride-sharing vehicles to the user's location over a road transportation network.

Not surprisingly, the spatial distribution of resources and users 1 in the network is an important factor in determining the overall performance of the service. A key measure of performance is expected request distance, that is average of the pairwise distances between each user and its allocated resource/server (where distance is measured on the network). This directly translates to latency incurred by a user when accessing the service, which is arguably among the most important criteria in distributed service applications. For example, in wireless networks, signal attenuation is strongly coupled to request distance, therefore developing allocation policies to minimize request distance can help reduce energy consumption, an important concern in battery-operated wireless networks. Another important practical constraint in distributed service networks is service capacity. For example, in network analytics applications, a networked storage device can only support a finite number of concurrent users; similarly, a computational resource can only support a finite number of concurrent processing tasks. Likewise, in physical service applications like ride-sharing, a vehicle can pick up a finite number of passengers at once. Therefore, a primary problem in such distributed service networks is to efficiently assign each user to a suitable resource so as to minimize expected request distance and ensure no resource is allocated to more users than its capacity. If the entire system is being managed by a single administrative entity such as a ride sharing service, or a datacenter network where analytics tasks are being assigned to available CPUs, there are economic benefits in minimizing the expected request distance across all (user, resource) pairs, which is tantamount to minimizing the average delay in the system.

The general version of this capacitated assignment problem can be solved by modeling it as a minimum cost flow problem on graphs [START_REF] Ahuja | Network Flows: Theory, Algorithms, and Applications[END_REF] and running the network simplex algorithm [START_REF] Orlin | A Polynomial Time Primal Network Simplex Algorithm for Minimum Cost Flows[END_REF]. However, if the network has a low-dimensional structure and some assumptions about the spatial distributions of users and resources hold, more efficient methods can be developed [START_REF] Jawhar | Linear Wireless Sensor Networks: Classification and Applications[END_REF].

In this paper, we consider two one-dimensional network scenarios that motivate the study of this special case of the user-to-resource assignment problem.

The first scenario is ride-hailing on a one-way street where vehicles move right to left. If the vehicles of a ride-sharing company are distributed along the street at a certain time, and users equipped with smartphone ride-hailing apps request service, the system attempts to assign vehicles with spare capacity located towards the right of the users so as to minimize expected "pick up" distance. Abadi et al. [START_REF] Abadi | Stable Matchings in Metric Spaces: Modeling Real-World Preferences using Proximity[END_REF] introduced this problem and presented a policy known as Unidirectional Gale-Shapley2 matching (UGS) to minimize expected pick up distance. In this policy, all users concurrently emit rays of light toward their right and each user is matched with the vehicle that first receives its emitted ray. While the well-known Gale-Shapley matching algorithm [START_REF] Gale | College Admissions and Stability of Marriage[END_REF] matches user-resource pairs that are mutually nearest to each other, its unidirectional variant, UGS, matches a user to the nearest resource on its right. Note that, this one-dimensional network setting also applies to vehicular wireless ad-hoc networks on a one-lane roadway [START_REF] Ho | Stochastic Model and Connectivity Dynamics for VANETs in Signalized Road Systems[END_REF], [START_REF] Leung | Traffic Models for Wireless Communication Networks[END_REF] 3 , where users are in vehicles and servers are attached to fixed infrastructure such as lamp posts. Users attempt to allocate their computation tasks over the wireless network to servers located to their right so that they can retrieve the results with little effort while driving by.

In this paper, we propose another policy "Move to Right" policy (or MTR) which has the same "expected distance traveled by a request" (request distance) as UGS but has a lower variance. MTR sequentially allocates users to the geographically nearest available vehicle located to his/her right. When user and resource locations are modeled by statistical point processes, the one-dimensional unidirectional space behaves similar to time and notions from queueing theory can be applied. In particular, when user and vehicle locations are modeled by independent Poisson processes, expected request distance can be characterized in closed form by considering inter-user and inter-server distances as parameters of a bulk service M/M/1 queue where the bulk service capacity denotes the maximum number of users that can be handled by a server. We equate request distance in the spatial system to the expected sojourn time in the corresponding queuing model 4 . This natural mapping allows us to use well-known results from queueing theory and in some cases to propose new queueing theoretic models to characterize request distances for a number of interesting situations beyond M/M/1 queues.

The second scenario involves a convoy of vehicles traveling on a one-dimensional space, for example, trucks on a highway or boats on a river. Some vehicles have expensive camera sensors (image/video) but have inadequate computational stor-age or processing power. On the other hand, cheap storage and processing is easily available on several other vehicles. The cameras periodically take photos/videos as they move through space and want them processed / stored. In such cases, bidirectional assignment schemes are more suitable. Since no directionality restrictions are imposed on the allocation algorithms, computing the optimal assignment is not as simple as in the unidirectional case.

We explore the special structure of the one-dimensional topology to develop an optimal algorithm that assigns a set of requesters R to a set of resources S such that the total assignment cost (and hence the expected request distance) is minimized. This problem has been recently solved for |R| = |S| [START_REF] Bukac | Matching On a Line[END_REF] with time complexity O(|R|). Note that other assignment algorithms in literature such as the Hungarian primal-dual algorithm and Agarwal's variant [START_REF] Agarwal | Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications[END_REF] Our contributions are summarized below:

1) Analysis of simple unidirectional allocation policies MTR and UGS yielding closed form expressions for expected request distance.

• When inter-requester and inter-resource distances are exponentially distributed, we model unidirectional policies as a bulk service M/M/1 queue. • When inter-requester distances are generally distributed but the inter-resource distances are exponentially distributed, we model the situation using an accessible batch service G/M/1 queue. • When inter-requester distances are exponentially distributed but inter-resource distances are generally distributed, we model the spatial system as an accessible batch service M/G/1 queue with the first batch having exceptional service time. To the best of our knowledge this system has not been studied previously in the queueing theory literature. • We include several generalizations of our framework. In the first place we discuss a simulation driven conjecture for evaluating request distance for general distance distributions under heavy traffic. We also investigate the heterogeneous server capacity scenario where server capacity is a random variable and to the best of our knowledge this system has not been studied previously in the queueing theory literature. We derive expressions for expected request distance when servers have infinite capacity. 2) A novel algorithm for optimal (bidirectional) assignment with time complexity O(|R|(|S| -|R| + 1)). 3) A numerical and simulation study of different assignment policies: UGS , MTR, a bi-directional heuristic allocation policy (Gale-Shapley) and the optimal policy.

The paper is organized as follows. The next section dis-cusses related work. Section III contains technical preliminaries. We show the equivalence of UGS and MTR w.r.t expected request distance in Section IV, and present results associated with the case when servers are Poisson distributed in Section V. In Section VI, we develop formulations for expected request distance when either user or server placements are described by Poisson processes. We include some generalizations of our framework such as analysis under general distance distributions, results for heterogeneous server capacity and uncapacitated allocation in Section VII. The optimal bidirectional allocation strategy is presented in Section VIII. We compare the performance of various local allocation strategies in Section IX. We conclude the paper in Section X.

II. RELATED WORK

Poisson Matching: Holroyd et al. [START_REF] Holroyd | Poisson Matching[END_REF] first studied translation invariant matchings between two d-dimensional Poisson processes with equal densities. Their primary focus was obtaining upper and lower bounds on expected matching distance for stable matchings. Abadi et al. [START_REF] Abadi | Stable Matchings in Metric Spaces: Modeling Real-World Preferences using Proximity[END_REF] introduced "Unidirectional Gale-Shapley" matching (UGS) and derived bounds on the expected matching distance for stable matchings between two one-dimensional Poisson processes with different densities.

In this paper, we propose another unidirectional allocation policy: "Move To Right" policy (MTR) and provide explicit expressions for the expected matching distance for both MTR and UGS when either requesters or servers are distributed according to a renewal process and the other according to a Poisson process.

Exceptional Queueing Systems and Accessible Batches: Welch et al. [START_REF] Welch | On a Generalized m/g/1 Queuing Process in Which The First Customer of Each Busy Period Receives Exceptional Service[END_REF] first studied an M/G/1 queue where a customer arriving when the server is idle has a different service time than the others. Bulk service M/G/1 queues has been studied in [START_REF] Bailey | On Queueing Processes with Bulk Service[END_REF]. Authors in [START_REF] Goswami | A Renewal Input Single and Batch Service Queues with Accessibility to Batches[END_REF] analyzed a bulk service G/M/1 queue with accessible or non-accessible batches where an accessible batch is a batch in service allowing subsequent arrivals, while the service is on. In this work, we model the spatial system using an accessible batch service queue with the first batch having exceptional service time. To the best of our knowledge this system has not been studied previously in queueing theory literature.

Euclidean Bipartite Matching: The optimal user-server assignment problem can be modeled as a minimum-weight matching on a weighted bipartite graph where weights on edges are given by the Euclidean distances between the corresponding vertices [START_REF] Mezard | The Euclidean Matching Problem[END_REF]. Well-known polynomial time solutions exist for this problem, such as the modified Hungarian algorithm proposed by Agarwal et al. [START_REF] Agarwal | Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications[END_REF] with a running time of O(|R| 2+ ), where |R| is the total number of users. In the case of an equal number of users and servers, the optimal userserver assignment on a real line is known [START_REF] Bukac | Matching On a Line[END_REF]. In this paper, we consider the case when there are fewer users than servers.

III. TECHNICAL PRELIMINARIES

Consider a set of users R and a set of servers S. Each user makes a request that can be satisfied by any server. Assume that each server j ∈ S has capacity c j ∈ Z + corresponding to the maximum number of requests that it can process. Suppose users and servers are located on a line L. Formally, let r : R → L and s : S → L be the location functions for users and servers, respectively, such that a distance d L (r, s) is well defined for all pairs (r, s) ∈ R × S. Initially we assume that all servers have equal capacities i.e. c j = c ∀j ∈ S. Later in Section VII-B we extend our analysis to a case in which server capacities are integer random variables.

A. User and server spatial distributions

Let 0 ≤ r 1 ≤ r 2 ≤ • • • represent user locations and 0 ≤ s 1 ≤ s 2 ≤ • • • be the server locations. Let X j = s j -s j-1 , j ≥ 1, s 0 = 0, denote the inter-server distances and Y i = r i -r i-1 , i ≥ 1, r 0 = 0, the inter-user distances.
We assume {X j } j≥1 to be a renewal process with cumulative distribution function (cdf)

P(X j ≤ x) = F X (x). (1)
We also assume {Y i } i≥1 to be a renewal process with cdf F Y (x), i.e.,

P(Y i ≤ x) = F Y (x). (2)
We denote α X = 1/µ and σ 2 X to be the mean and variance associated with F X . Similarly let α Y = 1/λ and σ 2 Y be the mean and variance associated with F Y . We let ρ = λ/µ and assume that ρ < c. Denote by

F * X (s) = ∞ 0 e -sx dF X (x) and F * Y (s) the Laplace-Stieltjes transform (LST) of F X and F Y with s ≥ 0.
In our paper, we consider various inter-server and inter-user distance distributions, including exponential, deterministic, uniform and hyperexponential.

B. Allocation policies

One of our goals is to analyze the performance of various request allocation policies using expected request distance as a performance metric. We define various allocation policies as follows.

• Unidirectional Gale-Shapley (UGS): In UGS, each user simultaneously emits a ray to their right. Once the ray hits an unallocated server s, the user is allocated to s. • Move To Right (MTR): In MTR, starting from the left, each user is allocated sequentially to the nearest available server to its right. • Gale-Shapley (GS) [START_REF] Gale | College Admissions and Stability of Marriage[END_REF]: In this matching, each user selects the nearest server and each server selects its nearest user. Remove reciprocating pairs, and continue. • Optimal Matching: This matching minimizes average request distance among all feasible allocation policies.

IV. UNIDIRECTIONAL ALLOCATION POLICIES

In this Section, we establish the equivalence of UGS and MTR w.r.t number of requests that traverse a point and expected request distance. Define N P

x and D P i to be random variables for the number of requests that traverse point x ∈ L and distance between user i and its allocated server under Fig. 1: Allocation of users to servers on the one-dimensional network. Top: UGS, Bottom: MTR allocation policy. policy P , respectively. Thus N U

x and N M x denote the number of requests that traverse point x ∈ L under UGS and MTR, respectively, as shown in Figure 1. Consider the following definition of busy cycle in a service network.

Definition 1. A busy cycle for a policy P is an interval

I = [a, b] ⊂ L such that ∃ i, j with r i = a, s j = b for which N P
x > 0, ∀x ∈ I and N P x = 0 for x = aand x = b + with being an infinitesimal positive value.

We have the following theorem.

Theorem 1. N U x = N M x , x ≥ 0. Proof. See [18]. Corollary 1. E[D U ] = E[D M ] i.e.
the expected request distances are the same for both UGS and MTR under steady state.

Proof. Under steady state both N U

x and N M x converge to a random variable. Applying Little's law we have

E[D U ] = E[D M ].
Remark 1. Note that Theorem 1 applies to any inter-server or inter-user distance distribution. It also applies to the case where servers have capacity c > 1.

Remark 2. Although MTR and UGS are equivalent w.r.t. the expected request distance, MTR tends to be fairer, i.e., has low variance 5 for expected request distance.

V. UNIDIRECTIONAL POISSON MATCHING

In this section, we characterize request distance statistics under unidirectional policies when both users and servers are distributed according to two independent Poisson processes. We first analyze MTR as follows.

A. MTR

Under this allocation policy, the service network can be modeled as a bulk service M/M/1 queue. A bulk service M/M/1 queue provides service to a group of c or fewer customers. The server serves a bulk of at most c customers whenever it becomes free. Also customers can join an existing service if there is room which is an example of accessible batch. In Section VI we describe the notion of accessible batches in greater detail. The service time for the group is exponentially distributed and customer arrivals are described by a Poisson process. The distance between two consecutive users in the service network can be thought of as inter-arrival time between customers in the bulk service M/M/1 queue. The distance between two consecutive servers maps to a bulk service time.

Having established an analogy between the service network and the bulk service M/M/1 queue, we now define the state space for the service network. Consider the definition of N x as the number of requests 6 that traverse point X ∈ L under MTR. In steady state, N x converges to a random variable

N provided λ < cµ. Let π k denote Pr[N = k] with k ≥ 0.
Following the procedure in [START_REF] Kleinrock | Queueing Systems[END_REF], we obtain the steady state probability vector π = [π i , i ≥ 0]. In the service network, request distance corresponds to the sojourn time in the bulk service M/M/1 queue. By applying Little's formula, we obtain the following expression for the expected request distance

E[D] = r 0 λ(1 -r 0 ) , (3)
where r 0 is the only root in the interval (0, 1) of the following equation (with r as the variable)

µr c+1 -(λ + µ)r + λ = 0. (4)
1) When server capacity: c = 1: When c = 1, r 0 = ρ is a solution of (4). Thus we can evaluate the expected request distance as

E[D] = ρ λ(1 -ρ) = 1 µ -λ . (5)
Note that, when server capacity is one, the service network can be modeled as an M/M/1 queue. In such a case, (5) is the mean sojourn time for an M/M/1 queue.

B. UGS

When both users and servers are Poisson distributed and servers have unit capacity, the request distance in UGS has the same distribution as the busy cycle in the corresponding Last-Come-First-Served Preemptive-Resume (LCFS-PR) queue having the density function [START_REF] Abadi | Stable Matchings in Metric Spaces: Modeling Real-World Preferences using Proximity[END_REF]

f D U (x) = 1 x √ ρ e (λ+µ)x I 1 (2x λµ), x > 0, (6)
where ρ = λ/µ and I 1 is the modified Bessel function of the first kind. Thus the expected request distance is equivalent to the average busy cycle duration in a LCFS-PR queue given by 1/(µ -λ) [START_REF] Abadi | Stable Matchings in Metric Spaces: Modeling Real-World Preferences using Proximity[END_REF]. When servers have capacities c > 1 it is difficult to characterize the expected request distance explicitly. However, by Theorem 1, the expected request distance under UGS is the same as that of MTR given by [START_REF] Ahuja | Network Flows: Theory, Algorithms, and Applications[END_REF].

Distribution Parameters F X (x) F X (x) F X (x) B(x) B(x) B(x) Exponential µ: rate 1 -e -µx 1 λ 1 -e -λx -1 λ+µ 1 -e -(λ+µ)x Uniform b : maximum value x/b, 0 ≤ x ≤ b 1 λ 2 b 1 -e -λb -e -λx λ Deterministic d 0 : constant 1, x ≥ d 0 e -λd 0 -e -λx λ Hyper l: order 1 - l j=1 p j e -µ j x 1 λ 1 -e -λx - l j=1 p j λ+µ j 1 -e -(λ+µ j )x
-exponential p j : phase probability µ j : phase rate

VI. UNIDIRECTIONAL GENERAL MATCHING

We now derive expressions for the expected request distance when either users or servers are distributed according to a Poisson process and the other by renewal process.

A. Notion of exceptional service and accessible batches

We discuss the notion of exceptional service and accessible batches applicable to our service network as follows. Consider a service network with c = 2 as shown in Figure 2. Consider a user r i . Let s j be the server immediately to the left of r i . We assume all users prior to r i have already been allocated to servers {s k , 1 ≤ k ≤ j}. MTR allocates both r i and r i+1 to s j+1 and allocates r i+2 to s j+2 . We denote [r i , s j+2 ] as a busy cycle of the service network. We have the following queueing theory analogy.

User r i can be thought of as the first customer in a queueing system that initiates a busy period while r i+1 sees the system busy when it arrives. Because only r i is in service at the arrival of r i+1 , r i+1 enters service with r i and the two customers form a batch of size 2. and depart at time s j+1 . This is an example of an accessible batch [START_REF] Goswami | A Renewal Input Single and Batch Service Queues with Accessibility to Batches[END_REF]. Recall that an accessible batch admits subsequent arrivals, while the service is on, until the server capacity c is reached.

The service time for the batch, r i , r i+1 , is described by the random variable Z j+1 which is different or exceptional when compared to service times of successive batches such as the one consisting of r i+2 . The service time for the second batch is X j+2 . Note that, Z j+1 only depends on X j+2 and Y i+2 . Thus when either X j+2 or Y i+2 is described by a Poisson process and the other by renewal process, Z j+1 converges to a random variable Z under steady state conditions. Denote F Z (x) and f Z (x) as the distribution and density functions for the random variable Z. Thus the service network can be mapped to an exceptional service with accessible batches queueing (ESABQ) model. We formally define ESABQ as follows.

ESABQ: Consider a queueing system where customers are served in batches of maximum size c. A customer entering the queue and finding fewer than c customers in the system joins the current batch and enters service at once, otherwise it joins a queue. After a batch departs leaving k customers in the buffer, min(c, k) customers form a batch and enter service immediately. There are two different service times cdfs, F Z (x) (exceptional batch) with mean α Z = 1/µ Z and F X (x) (ordinary batch) with mean α X = 1/µ. A batch is exceptional if its oldest customer entered an empty system, otherwise it is a regular batch. When the service time expires, all customers in the server depart at once, regardless of the nature of the batch (exceptional or regular).

1) Evaluation of the distribution function: F Z (x): In this Section, we compute explicit expressions for the distribution function F Z (x) applicable to our service network.

When F X (x) ∼ F X (x) ∼ F X (x) ∼ Expo(µ) (µ) (µ):
In this case, we invoke the memoryless property of the exponential distribution F X . Thus the exceptional distribution, F Z , is

F Z (x) = F X (x) = 1 -e -µx , x ≥ 0. ( 7
)
When F Y (x) ∼ F Y (x) ∼ F Y (x) ∼ Expo(λ) (λ) (λ):
Using the memoryless property of F Y , F Z can be computed as

FZ (x) = Pr(X -Y < x|Y < X) = Pr(X -Y < x|X -Y > 0) = Pr(X -Y < x) -Pr(X -Y < 0) 1 -Pr(X -Y < 0) = DXY (x) -DXY (0) 1 -DXY (0) , x ≥ 0, (8)
where D XY (x) is the distribution of the random variable X -Y (also known as difference distribution). D XY (x) can be expressed as

DXY (x) = Pr(X -Y ≤ x) = ∞ 0 Pr(X -y ≤ x)Pr(Y = y)dy = ∞ 0 FX (x + y)λe -λy dy = ∞ x FX (z)λe -λ(z-x) dz = λe λx ∞ 0 FX (z)e -λz dz - x 0 FX (z)e -λz dz = λe λx [A(FX ) -B(x)] , (9)
where A is the Laplace Transform operator on the function F X and B(x) is denoted by

B(x) = x 0 F X (z)e -λz dz (10)
Clearly B(0) = 0. Thus combining ( 8) and ( 9) yields

F Z (x) = λe λx [A(F X ) -B(x)] -λA(F X ) 1 -λA(F X ) , (11)
f Z (x) = λ 2 e λx [A(F X ) -B(x)] -λF X (x) 1 -λA(F X ) , (12)
α Z = ∞ 0 xf Z (x)dx, σ 2 Z = ∞ 0 x 2 f Z (x)dx -α 2 Z . (13)
Expressions for B(x) are presented in Table I. We can evaluate A(F X ) by setting A(F X ) = B(∞). Detailed derivations are relegated to [START_REF] Panigrahy | Resource Allocation in One-dimensional Distributed Service Networks[END_REF].

B. General requests and Poisson distributed servers (GRPS)

From our discussion in Section VI-A1, it is clear that when servers are distributed according to a Poisson process, the exceptional service time distribution equals the regular batch service time distribution. In such a case we have the following queueing model.

Under GRPS, inter-arrival times and batch service times are, respectively, arbitrarily and exponentially distributed. Before initiating a service, a server finds the system in any of the following conditions. (i) 1 ≤ n ≤ c -1 and (ii) n ≥ c.

Here n is the number of customers in the waiting buffer. For case (i) the server provides service to all n customers and admits subsequent arrivals until c is reached. For case (ii) the server takes c customers with no admission for subsequent customers arriving within its service time.

In such a case ESABQ can directly be modeled as a special case of a renewal input bulk service queue with accessible and non-accessible batches proposed in [START_REF] Goswami | A Renewal Input Single and Batch Service Queues with Accessibility to Batches[END_REF] with parameter values a = 1 and d = b = c. Let N s and N q denote random variables for numbers of customers in the system and in the waiting buffer respectively for ESABQ under GRPS. We borrow the following definitions from [START_REF] Goswami | A Renewal Input Single and Batch Service Queues with Accessibility to Batches[END_REF].

P n,0 = Pr[N s = n]; 0 ≤ n c -1 P n,1 = Pr[N q = n]; n ≥ 0. ( 14
)
Using results from [START_REF] Goswami | A Renewal Input Single and Batch Service Queues with Accessibility to Batches[END_REF] we obtain the following expressions for equilibrium queue length probabilities.

P 0,1 = C µ r c-1 0 -r c 0 1 -r c 0 + 1 r 0 -1 , P n,1 = Cr n-1 0 (1 -r 0 ) µ(1 -r c 0 ) ; n ≥ 1, (15)
where 0 < r 0 < 1 is the real root of the equation r = F * Y (µµr c ) and C is the normalization constant 7 given by

C = λ 1 -ω c 1 -ω + 1 1 -r 0 - ω(r 0 -F * Y (µ)) r c 0 (1 -r 0 ω) 1 -r c 0 1 -r 0 -r c-1 0 1 -w c 1 -w -1 , (16)
with ω = 1/F * Y (µ). We then derive the expected queue length as

E[N q ] = ∞ n=0 nP n,1 = ∞ n=1 n Cr n-1 0 (1 -r 0 ) µ(1 -r c 0 ) = C(1 -r 0 ) µ(1 -r c 0 ) ∞ n=1 nr n-1 0 = C µ(1 -r c 0 )(1 -r 0 ) . (17)
Applying Little's law and considering the analogy between our service network and ESABQ we obtain the following expression for the expected request distance.

E[D] = C λµ(1 -r c 0 )(1 -r 0 ) + 1 µ . (18)

C. Poisson distributed requests and general distributed servers (PRGS)

As discussed in Section VI-A1, if servers are placed on a 1-d line according to a renewal process with requests being Poisson distributed, the service time distribution for the first batch in a busy period differs from those of subsequent batches. Below we derive expressions for queue length distribution and expected request distance for ESABQ under PRGS.

1) Queue length distribution: We use a supplementary variable technique to derive the queue length distribution for ESABQ under PRGS as follows.

Let L(t) be the number of customers at time t ≥ 0, R(t) the residual service time at time t ≥ 0 (with R(t) = 0 if L(t) = 0), and I(t) the type of service at time t ≥ 0 with I(t) = 1 (resp. I(t) = 2) if exceptional (resp. ordinary) service time.

Let us write the Chapman-Kolmorogov equations for the Markov chain {(L(t), R(t), I(t)), t ≥ 0}.

For t ≥ 0, n ≥ 1, x > 0, i = 1, 2 define

p t (n, x; i) = P(L(t) = n, R(t) < x, I(t) = i) p t (0) = P(L(t) = 0). Also, define for x > 0, i = 1,
With further simplification (See [START_REF] Panigrahy | Resource Allocation in One-dimensional Distributed Service Networks[END_REF]), for n ≥ 1, x > 0 we get

∂ ∂x g(n, x) -λg(n, x) - ∂ ∂x g(n, 0) + λg(n -1, x)1(n ≥ 2) + λp(0)F Z (x)1(n = 1) + F X (x) ∂ ∂x g(n + c, 0) = 0, (20)
where g(n, x) = p(n, x; 1) + p(n, x; 2) for n ≥ 1, x > 0. Introduce

G(z, s) := n≥1 z n ∞ 0 e -sx g(n, x)dx ∀|z| ≤ 1, s ≥ 0.
Denote by

F * Z (s) = ∞ 0 e -sx dF Z (x) the LST of F Z for s ≥ 0. Note that ∞ 0 e -sx F Z/X (x)dx = F * Z/X (s) s , ∀s > 0.
Multiplying both sides of ( 20) by z n e -sx , integrating over x ∈ [0, ∞) and summing over all n ≥ 1, yields

(λ(1 -z) -s) G(z, s) =λzp(0)F * Z (s) - n≥1 z n ∂ ∂x g(n, 0) + F * X (s) n≥1 z n ∂ ∂x g(n + c, 0)) (21)
where

λp(0) = c k=1 ∂ ∂x g(k, 0) from (19). We have 1 z c n≥1 z n+c ∂ ∂x g(n + c, 0)) = 1 z c n≥1 z n ∂ ∂x g(n, 0) - 1 z c H(z) (22)
where H(z) = c k=1 z k a k with a k := ∂ ∂x g(k, 0), for k = 1, . . . , c. Introducing the above into (21) gives

(λ(1 -z) -s) G(z, s) = F * X (s) z c -1 Ψ(z) -F * X (s) H(z) z c + λzp(0)F * Z (s) (23)
where Ψ(z) := n≥1 z n ∂ ∂x g(n, 0). Since G(z, s) is welldefined for |z| ≤ 1 and s ≥ 0, the r.h.s. of (23) must vanish when s = λ(1 -z). This gives the relation

Ψ(z) = z c z c -F * X (θ(z)) -F * X (θ(z)) H(z) z c + λzp(0)F * Z (θ(z))
with θ(z) = λ(1 -z) and |z| ≤ 1. Introducing the above in (23) gives

(λ(1 -z) -s) G(z, s) = -F * X (s) H(z) z c + λzp(0)F * Z (s) + F * X (s) -z c z c -F * X (θ(z)) λzp(0)F * Z (θ(z)) -F * X (θ(z)) H(z) z c . ( 24
)
Let N (z) be the z-transform of the stationary number of customers in the system. Integrating by part, we get for n ≥ 1,

s ∞ 0 e -sx g(n, x)dx = ∞ 0 e -sx dg(n, x), so that lim s→∞ s ∞ 0 e -sx g(n, x)dx = lim s→0 ∞ 0 e -sx dg(n, x) = ∞ 0 dg(n, x) = g(n, ∞), (25)
where the interchange between the limit and the integral sign is justified by the bounded convergence theorem. Therefore,

N (z) = n≥1 z n g(n, ∞) + p(0) = n≥1 z n lim s→∞ s ∞ 0 e -sx g(n, x)dx from (25) = lim s→0 sG(z, s) + p(0), (26)
where the interchange between the summation over n and the integral sign is again justified by the bounded convergence theorem. Letting now s → 0 in (24) and using (26), gives

θ(z)N (z) = 1 -z c z c -F * X (θ(z)) -F * X (θ(z)) H(z) z c + λzp(0)F * Z (θ(z)) - H(z) z c + λp(0). ( 27
)
By noting that λp(0) = c k=1 a k (cf. ( 19)), Eq. ( 27) can be rewritten as

N (z) = 1 θ(z) z(1 -z c ) z c -F * X (θ(z)) c k=1 a k F * Z (θ(z)) -z k-c-1 F * X (θ(z)) + c k=1 a k (1 -z k-c ) . (28)
The r.h.s. of (28) contains c unknown constants a 1 , . . . , a c yet to be determined. Define A(z) = F * X (θ(z)). It can be shown that z c -A(z) has c-1 zeros inside and one on the unit circle, |z| = 1 (See [START_REF] Panigrahy | Resource Allocation in One-dimensional Distributed Service Networks[END_REF]). Denote by ξ 1 , . . . , ξ q the 1 ≤ q ≤ c distinct zeros of z c -A(z) in {|z| ≤ 1}, with multiplicity n 1 , . . . , n q , respectively, with

n 1 + • • • + n q = c. Hence, z c -F * X (k(z)) = γ q i=1 (z -ξ i ) ni .
Since z c -A(z) vanishes when z = 1 and that d dz (z c -A(z))| z=1 = c -ρ > 0, we conclude that z c -A(z) has one zero of multiplicity one at z = 1.

Without loss of generality assume that ξ q = 1 and let us now focus on the zeros ξ 1 , . . . , ξ q-1 . When z = ξ i , i = 1, . . . , q-1, the term 28) must have a zero of multiplicity (at least) n i since N (ξ i ) is well defined. This gives c -1 linear equations to be satisfied by ξ 1 , . . . , ξ q . In the particular case where all zeros have multiplicity one (see [START_REF] Panigrahy | Resource Allocation in One-dimensional Distributed Service Networks[END_REF]), namely q = c, these c -1 equations are since

F * Z (θ(z))-z k-c-1 F * X (θ(z)) in (
c k=1 a k F * Z (θ(ξ i )) -ξ k-c-1 i F * X (θ(ξ i )) = 0, i = 1, . . . , c-1. (29) With U (z) := F * Z (θ(z))/F * X (θ(z)) (29) is equivalent to c k=1 a k U (ξ i ) -ξ k-c-1 i ) = 0, i = 1, . . . , c -1, (30)
F * X (θ(ξ i )) = 0 for i = 1, . . . , c -1 (F * X (θ(ξ i )) = 0 implies that ξ i =0 which contradicts that ξ i a zero of z c - F * X (θ(z)) since F * X (θ(0)) = F * X (λ) > 0).
Eq. ( 28) can be rewritten as

N (z) = c k=1 a k z c -z k + z(1 -z c )F * Z (θ(z)) -(1 -z k )F * X (θ(z)) θ(z)(z c -F * X (θ(z)) . (31)
A c-th equation is provided by the normalizing condition N (z) = 1. Since the numerator and denominator in (31) have a zero of order 2 at z = 1, differentiating twice the numerator and the denominator w.r.t z and letting z = 1 gives

c k=1 a k (c(1 + ρ z ) -ρk) = λ(c -ρ), (32)
where ρ z = λα Z . We consider few special cases of the model in [START_REF] Panigrahy | Resource Allocation in One-dimensional Distributed Service Networks[END_REF] and verify with the expressions of queue length distribution available in the literature.

2) Expected request distance: From (31) the expected queue length is

N = d dz N (z) z=1 = 1 2λ(c -ρ) 2 c k=1 a k λ 2 σ (2) Z c(c -ρ) + λ 2 σ (2) X c(1 + ρz -k) + (ck(c -k) + k(k -1)ρ -c(c -1))ρ + 2c 2 ρz -c(c + 1)ρzρ , (33)
where σ

(2)

Z and σ (2)
X are the second order moments of distributions F Z and F X respectively. Again by applying Little's law and considering the analogy between our service network with ESABQ we get the following expression for the expected request distance.

E[D] = N /λ. ( 34
)

VII. DISCUSSION OF UNIDIRECTIONAL ALLOCATION POLICIES

In this section we describe generalizations of models and results for unidirectional allocation policies. We first consider the case when inter-user and inter-server distances both have general distributions.

A. Heavy traffic limit for general request and server spatial distributions Consider the case when the inter-user and inter-server distances each are described by general distributions. We assume server capacity, c = 1. As ρ → 1, we conjecture that the behavior of MTR approaches that of the G/G/1 queue. One argument in favor of our conjecture is the following. As ρ → 1, the busy cycle duration tends to infinity. Consequently, the impact of the exceptional service for the first customer of the busy period on all other customers diminishes to zero as there is an unbounded increasing number of customers served in the busy period.

It is known that in heavy traffic waiting times in a G/G/1 queue are exponentially distributed and the mean sojourn time is given by α

X + [(σ 2 X + σ 2 Y )/2α Y (1 -ρ)] [9]
. We expect the expected request distance to exhibit similar behavior. Thus we have the following conjecture.

Conjecture 1. At heavy traffic i.e. as ρ → 1, the expected request distance for the G/G/1 spatial system with c = 1 is given by

E[D] = α X + σ 2 X + σ 2 Y 2α Y (1 -ρ) . (35)
Denote by D s the average request distance as obtained from simulation. We plot the ratio E[D]/D s across various interrequest and inter-server distance distributions in Figure 3. It is evident that as ρ → 1, the ratio E[D]/D s converges to 1 across different inter-server distance distributions.

B. Heterogeneous server capacities under PRGS

We now proceed to analyze a setting where server capacity is a random variable. Assume server capacity C takes values from {1, 2, . . . , c} with distribution Pr(C = j) = p j , ∀j ∈ {1, 2, . . . , c}, s.t. c j=1 p j = 1 and p c > 0. We also assume the stability condition ρ < C where C is the average server capacity. Denote H as the random variable associated with number of requests that traverse through a point just after a server location 8 .

1) Distribution of H: Let V denote the number of new requests generated during a service period with k v = Pr(V = v), ∀v ≥ 0. According to the law of total probability, it holds that

k v = ∞ 0 Pr(V = v|X = ν)f X (ν) = 1 v! ∞ 0 e -λν (λν) v dF X (ν).
Then the corresponding generating function K(z) is denoted by

K(z) = ∞ v=0 k v z v = F * X (λ(1 -z))
. We now consider an embedded Markov chain generated by H. Denote the corresponding transition matrix as M. Then we have

M m,l =                    c-m i=0 k i P i+m , 0 ≤ m ≤ c, l = 0; c i=0 k i+l-m p i , 0 ≤ m ≤ l, l = 0; c i=m-l k i+l-m p i , l + 1 ≤ m ≤ c + l, l = 0; 0, o.w., (36)
where P i = c j=i p j and p 0 = 0. Let π = [π j , j ≥ 0] and N (z) = j≥0 π j z j denote the steady state distribution and its z-transform respectively. π is obtained out by solving

π l = ∞ m=0 π m M m,l , l = 0, 1, . . . . (37)
Thus we have for l ∈ N,

π 0 = c m=0 π m c-m i=0 k i P i+m , π l = l m=0 π m c i=0 k i+l-m p i + c+l m=l+1 π m c i=m-l k i+l-m p i . (38)
Multiplying by z l and summing over l gives

N (z) = Eπ + v 1 (z) + v 2 (z) (39)
Eπ = π 0 c-1 i=0 k i P i+1 + c-1 m=1 πm c-1 i=m k i-m P i+1 (40)
v 1 (z) = ∞ l=0 z l l m=0 πm c i=0 k i+l-m p i (41) v 2 (z) = ∞ l=0 z l c+l m=l+1 πm c i=m-l k i+l-m p i . (42)
The expressions for v 1 (z) and v 2 (z) can be further simplified (see [START_REF] Panigrahy | Resource Allocation in One-dimensional Distributed Service Networks[END_REF]) to

v 1 (z) = N (z) c i=0 p i z -i K(z) - i j=0 k j z j + c i=0 k i z i (43) v 2 (z) = c m=0 z -m c i=m k i-m p i N (z) - m-1 j=0 π j z j -N (z) c i=0 k i z i . (44)
Combining (39), ( 43) and (44) yields

N (z) = Eπ + N (z) K(z) c i=0 p i z -i - c-1 j=0 π j c-j m=1 z -m c i=m+j k i-(m+j) p i . (45)
Thus we obtain

N (z) = Eπ - c-1 j=0 π j c-j m=1 z -m c i=m+j k i-(m+j) p i 1 -K(z) c i=0 p i z -i . ( 46
)
Multipying numerator and denominator by z c yields

N (z) = z c Eπ - c-1 j=0 π j c-j m=1 z c-m c i=m+j k i-(m+j) p i z c -K(z) c i=0 p c-i z i . (47)
To determine N (z), we need to obtain the probabilities π i , 0 ≤ i ≤ c -1. It can be shown that the denominator of (47) has c -1 zeros inside and one on the unit circle, |z| = 1 (See [START_REF] Panigrahy | Resource Allocation in One-dimensional Distributed Service Networks[END_REF]). As N (z) is analytic within and on the unit circle, the numerator must vanish at these zeros, giving rise to c equations in c unknowns.

Let ξ q : 1 ≤ q ≤ c be the zeros of z c -K(z) c i=0 p c-i z i in {|z| ≤ 1}. W.l.o.g let ξ c = 1. We have the following c -1 equations.

Eπ - c-1 j=0 π j c-j m=1 ξ -m q c i=m+j k i-(m+j) p i = 0, i = 1, . . . , c -1, (48)
A c-th equation is provided by the normalizing condition lim z→1 N (z) = 1. In the particular case where all zeros have multiplicity one, it can be shown that these c equations are linearly independent 9 . Once the parameters {π i , 0 ≤ i ≤ c-1} are known, E[H] can be expressed as

E[H] = H = lim z→1 N (z). (49)
2) Expected Request Distance: To evaluate the expected request distance we adopt arguments from [START_REF] Bailey | On Queueing Processes with Bulk Service[END_REF]. Consider any interval of length ν between two consecutive servers. There are on average H requests at the beginning of the interval , each of which must travel ν distance. New users are spread randomly over the interval and there are on an average λν new users. The request made by each new user must travel on average ν/2. Thus we have

E[D] = 1 ρ ∞ 0 (Hν + 1 2 λν 2 )dF X (ν) = 1 ρ H µ + λ 2 σ 2 X + 1 µ 2 . (50)

C. Uncapacitated request allocation

An interesting special case of the unidirectional general matching is the uncapacitated scenario. Consider the case where servers do not have any capacity constraints, i.e. c = ∞. In such a case, all users are assigned to the nearest server to their right. 16) and simplifying yields

GRPS: When c → ∞ and given 0 < r 0 < 1, r 0 = F * Y (µ - µr c 0 ) = F * Y (µ). Setting ω = 1/F * Y (µ) = 1/r 0 in (
C → 0, as c → ∞, =⇒ E[D] → 1 µ as c → ∞. (51)
PRGS: Under PRGS, when c → ∞ there exists no request allocated to a server other than the nearest server to its right.

Again using Bailey's method as in [START_REF] Bailey | On Queueing Processes with Bulk Service[END_REF] and setting H = 0 in (50) we get

E[D] → µ 2 σ 2 X + 1 µ 2 as c → ∞. (52)

VIII. BIDIRECTIONAL ALLOCATION POLICIES

Both UGS and MTR minimize expected request distance among all unidirectional policies. In this section we formulate the bi-directional allocation policy that minimizes expected request distance. Let η : R → S be any mapping of users to servers. Our objective is to find a mapping η * : R → S, that satisfies

η * = arg min η i∈R d L (r i , s η(i) ) s.t. i∈R 1 η(i)=j ≤ c, ∀j ∈ S (53) W.l.o.g, let r 1 ≤ r 2 ≤ • • • ≤ r i ≤ • • • ≤ r |R| be locations of requests and s 1 ≤ s 2 ≤ • • • ≤ s i ≤ • • • ≤ s |S| be locations of servers.
We first focus on the case when c = 1. We consider the following two scenarios.

Case 1:

|R| = |S| |R| = |S| |R| = |S| When |R| = |S|,
an optimal allocation strategy is given by the following theorem [START_REF] Bukac | Matching On a Line[END_REF].

Theorem 2. When |R| = |S|, an optimal assignment is obtained by the policy:

η * (i) = i, ∀i ∈ {1, • • • , |R|} i.e.
allocating the i th request to the i th server and the average request distance is given by

E[D] = 1 |R| |R| i=1 |s(i) -r(i)|. ( 54
)
Case 2: |R| < |S| |R| < |S| |R| < |S| This is the case where there are fewer requesters than servers. In this case, a Dynamic Programming (DP) based algorithm (Algorithm 1) obtains the optimal assignment.

Let C[i, j] denote the optimal cost (i.e., sum of distances) of assigning the first i requests (counting from the left) located at r 1 ≤ r 2 ≤ . . . ≤ r i to the first j servers (also counting from the left) located at s 1 ≤ s 2 ≤ . . . ≤ s j . If j == i, the optimal assignment is trivial due to Theorem 2 and C[i, i] is computed easily for all i ≤ |R| by summing pairwise distances d [START_REF] Abadi | Stable Matchings in Metric Spaces: Modeling Real-World Preferences using Proximity[END_REF][START_REF] Abadi | Stable Matchings in Metric Spaces: Modeling Real-World Preferences using Proximity[END_REF], d[2, 2], . . . , d[i, i] (Lines 6-7). For the base case, i = 1, j > 1, only the first user needs to be assigned to its nearest server (Lines 9-16). For the general dynamic programming step, consider j > i. Then C[i, j] can be expressed in terms of the costs of two subproblems, i.e., C[i-1, j -1] and C[i, j -1] (Lines 19-24). In the optimal solution, two cases are possible: either request i is assigned to server j, or the latter is left unallocated. The former case occurs if the first i -1 requests are assigned to the first j -1 servers at cost C[i-1, j -1], and the latter case occurs when the first i requests are assigned to the first j -1 servers at cost C[i, j -1]. This is a consequence of the no-crossing lemma (Lemma 1). The optimal C[i, j] is

9 3 3 1+ℇ 1 1 1 1 1+ℇ 1+ℇ 1+ℇ 1+ℇ 1+ℇ 1+ℇ 1+ℇ
Optimal minimum weight matching Gale-Shapley stable matching Lemma 1. In an optimal solution, η * , to the problem of matching users at r 1 ≤ r 2 ≤ . . . ≤ r |R| to servers at s 1 ≤ s 2 ≤ . . . ≤ s |S| , where |S| ≥ |R|, there do not exist indices i, j such that η * (i) > η * (i ) when i > i.

Proof. See [START_REF] Panigrahy | Resource Allocation in One-dimensional Distributed Service Networks[END_REF].

The dynamic programming algorithm fills cells in an |R| × |S| matrix C whose origin is in the north-west corner. The lower triangular portion of this matrix is invalid since |R| ≤ |S|. The base cases populate the diagonal and the northernmost row, and in the general DP step, the value of a cell depends on the previously computed values in the cells located to its immediate west and diagonally north-west. As an optimization, for a fixed i, the j-th loop index needs to run only from i+1 through i+|S|-|R| (Lines 11 and 18) instead of from i + 1 through |S|. This is because the first request has to be assigned to a server s j with j ≤ |S| -|R| + 1 so that the rest of the |R| -1 requests have a chance of being placed on unique servers 10 Note that retrieving the optimal assignment requires more book-keeping. An |R| × |S| matrix A stores key intermediate steps in the assignment as the DP algorithm progresses (Lines 8, 16, 21, 24). The optimal assignment vector π can be retrieved from matrix A using procedure READOPTASSIGN-MENT.

Another bidirectional assignment scheme is the Gale-Shapley algorithm [START_REF] Gale | College Admissions and Stability of Marriage[END_REF], which produces stable assignments, though in the worst case it can yield an assignment that is O(|R| ln 3/2 ) ≈ O(|R| 0.58 ) times costlier than the optimal assignment yielded by Algorithm 1, where |R| is the number of users [START_REF] Reingold | On a Greedy Heuristic for Complete Matching[END_REF]. The worst case scenario is illustrated in Figure 4, with |R| = 2 t-1 , where t is the number of clusters of users and servers; and the largest distance between adjacent points is Algorithm 1 Optimal Assignment by Dynamic Programming 1: Input:

r 1 ≤ • • • ≤ r |R| ; s 1 ≤ • • • ≤ s |S| 2:
Output: The optimal assignment π 3: procedure OPTDP(r, s) server. While both the curves exhibit similar performance under H 2 distribution, we observe better performance for constant server capacity curve at lower values of c under Deterministic distribution. Variability in constant server case is zero, thus explaining its better performance.

C. Comparison of different allocation policies

We consider the case in which both users and servers are distributed according to Poisson processes. From Figure 9 (a), we observe that due to its directional nature MTR has a larger expected request distance compared to other policies while GS provides near optimal performance. In Figure 9 (b), we compare the performance of allocation policies across different server capacities. The expected request distance decreases with increase in server capacities across all policies. Both GS and the optimal policy converge to the same value as c gets higher.

We observe similar trends in the case of deterministic interserver distance distributions. However, under equal densities, all the policies produce smaller expected request distance as compared to their Poisson counterpart. This advocates for placing equidistant servers in a bidirectional system with Poisson distributed requesters to minimize expected request distance.

X. CONCLUSION

We introduced a queuing theoretic model for analyzing the behavior of unidirectional policies to allocate tasks to servers on the real line. We showed the equivalence of UGS and MTR w.r.t the expected request distance and presented results associated with the case when either requesters or servers are Poisson distributed. In this context, we analyzed a new queueing theoretic model: ESABQ, not previously studied in queueing literature. We also proposed a dynamic programming based algorithm to obtain an optimal allocation policy in a bi-directional system. We performed sensitivity analysis for unidirectional system and compared the performance of various greedy allocation strategies along with the unidirectional policies to that of optimal policy. Going further, we aim to extend our analysis for unidirectional policies to a twodimensional geographic region.

XI. ACKNOWLEDGMENT

This research was sponsored by the U.S. ARL and the U.K. MoD under Agreement Number W911NF-16-3-0001 and by the NSF under Grant CNS-1617437. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the National Science Foundation, U.S. ARL or the U.K. MoD. This document does not contain technology or technical data controlled under either the U.S. International Traffic in Arms Regulations or the U.S. Export Administration Regulations. The authors thank Prof. Amotz Bar-Noy for initial discussions on the optimal dynamic programming solution.

  have time complexities O(|R| 3 ) and O(|R| 2+ ) respectively and assume |R| = |S| for general and Euclidean distance measures. However, we are interested in the case when |R| < |S|. We propose a Dynamic Programming based algorithm which solves this case with time complexity O(|R|(|S| -|R| + 1)).

Fig. 3 :

 3 Fig. 3: The plot shows the ratio E[D]/D s for deterministic and uniform inter-server distance distributions.

Fig. 4 :

 4 Fig. 4: Worst case scenario for Gale-Shapley.

4 :d 5 :C = {∞} |R|×|S| 6 :Fig. 6 :Fig. 7 : 3 )

 456673 Fig. 6: Effect of squared coefficient of variation on expected request distance with λ = µ = 1 λ = µ = 1 λ = µ = 1 and c = 2 c = 2 c = 2.

Fig. 8 :Fig. 9 :

 89 Fig. 8: Effect of variability in server capacity on expected request distance for H 2 (a) and Deterministic (b) distributions with ρ = 0.8 ρ = 0.8 ρ = 0.8. 4) Expected request distance vs. capacity moments: We investigate the heterogeneous capacity scenario as discussed in Section VII-B. Consider the plot shown in Figure8. We fix ρ = 0.8. For the variable server capacity curve we choose a value for server capacity for each server uniformly at random from the set {1, 2, . . . , 2c}. For the constant server capacity curve we deterministically assign server capacity c to each

TABLE I :

 I Properties of specific inter-server distance distributions.

	Z j+1	Servers Users
	X j+1	X j+2
	s j r i r i+1 r i+2 s j+1	s j+2
	Busy Cycle
	Fig. 2: Allocation of users to servers under MTR policy.

  . The optimal average request distance is given by C[|R|, |S|]. The time complexity of the main DP step is O(|R| × (|S| -|R| + 1)). Note that this assumes that the pairwise distance matrix d of dimension |R| × |S| has been precomputed. The optimization applied above can be similarly applied to this computation and hence the overall time complexity of Algorithm 1 is O(|R|×(|S|-|R|+1)). Therefore, if |S| = O(|R|), the worst case time complexity is quadratic in |R|. However, if |S|-|R| grows only sub-linearly with |R|, the time complexity is sub-quadratic in |R|.

We use the terms "users" and "requesters" interchangeably and same holds true for the terms "resources" and "servers".

We rename queue matching defined in[START_REF] Abadi | Stable Matchings in Metric Spaces: Modeling Real-World Preferences using Proximity[END_REF] as Unidirectional Gale-Shapley Matching to avoid overloading the term queue.

Furthermore,[START_REF] Ho | Stochastic Model and Connectivity Dynamics for VANETs in Signalized Road Systems[END_REF] confirms that vehicle location distribution on the streets in Central London can be closely approximated by a Poisson distribution.

Sojourn time is the sum of waiting and service times in a queue.

It is well known in queueing theory that among all service disciplines the variance of the waiting time is minimized under FCFS policy[START_REF] Kingman | The Effect of Queue Discipline on Waiting Time Variance[END_REF]. In Section V we show that MTR maps to a temporal FCFS queue.

We drop the superscript (M ) for brevity.

The normalization constant C derived in[START_REF] Goswami | A Renewal Input Single and Batch Service Queues with Accessibility to Batches[END_REF] is incorrect. The correct constant for our case is given in[START_REF] Mezard | The Euclidean Matching Problem[END_REF].

An analysis for the distribution of number of requests that traverse through any random location would involve the notions of exceptional service and accessible batches.

For all cases evaluated across uniform, deterministic and hyperexponential distributions we found the set of c equations to be linearly independent.

Note that in this exposition, we consider server capacity c = 1. If c > 1, we simply add c servers at each prescribed server location, and requests will still be placed on unique servers.

return π 3 t-2 . However at low/moderate loads for the cases evaluated in Section IX, we find its performance to be not much worse than optimal.

IX. NUMERICAL EXPERIMENTS

In this section, we examine the effect of various system parameters on expected request distance under MTR policy. We also compare the performance of various greedy allocation strategies along with the unidirectional policies to the optimal strategy.

A. Experimental setup

In our experiments, we consider a mean requester rate λ ∈ (0, 1). We consider various inter-server distance distributions with density one. In particular, (i) for exponential distributions, the density is set to µ = 1; (ii) for deterministic distributions, we assign parameter d 0 = 1. (iii) for second order hyper-exponential distribution (H 2 ), denote p 1 and p 2 as the phase probabilities. Let µ 1 and µ 2 be corresponding phase rates. We assume p 1 /µ 1 = p 2 /µ 2 . We express H 2 parameters in terms of the squared coefficient of variation, c 2 v , and mean inter-server distance, α X , i.e. we set

Unless specified, for H 2 we take c 2 v = 4 with c = 2. Also if not specified, users are distributed according to a Poisson process and servers a according to a renewal process.

We consider a collection of 10 5 users and 10 5 servers, i.e. |R| = |S| = 10 5 . We assign users to servers according to MTR. Let R M ⊆ R be the set of users allocated under MTR. Clearly |R M | ≤ |R|. We then run optimal and other greedy policies on the set R M and S. For each of the experiments, the expected request distance for the corresponding policy is averaged over 50 trials. 2) Expected request distance vs. squared coefficient of variation: We now examine how c 2 v affects E[D] when ρ is fixed. We compare two systems: a general request with Poisson distributed servers (H 2 /M) and a Poisson request with general distributed servers (M/H 2 ) where the general distribution is a H 2 distribution with the same set of parameters, i.e. we fix λ = µ = 1 with c = 2. The results are shown in Figure 6. Note that, when c 2 v = 1 H 2 is an exponential distribution and both H 2 /M and M/H 2 are identical M/M/1 systems. As discussed for the previous graph, performance of both systems decreases with increase in c 2 v due to increase in the variability of user and server placements. However, from Figure 6 it is clear that performance is more sensitive to server placement as compared to the corresponding user placement.

B. Sensitivity analysis