Computer Science
Computer Science-2021.gz:143206
Computer Science
28f72d5aeb0068d1aa45a8a01ced71d0f0eb0e0d
Discrete-Time Analysis of Wireless Blockchain Networks

Blockchain (BC) technology can revolutionize future networks by providing a distributed, secure, and unalterable way to boost collaboration among operators, users, and other stakeholders. Its implementations have traditionally been supported by wired communications, with performance indicators like the high latency introduced by the BC being one of the key technology drawbacks. However, when applied to wireless communications, the performance of BC remains unknown, especially if running over contention-based networks. In this paper, we evaluate the latency performance of BC technology when the supporting communication platform is wireless, specifically we focus on IEEE 802.11ax, for the use case of users' radio resource provisioning. For that purpose, we propose a discrete-time Markov model to capture the expected delay incurred by the BC. Unlike other models in the literature, we consider the effect that timers and forks have on the end-to-end latency.


I. INTRODUCTION
One of the main challenges to face for Beyond 5G (B5G) networks is the need to foster the economic sustainability of the increasingly complex mobile networks. In this regard, a new economy of sharing has long been proposed by the main standardization bodies in contexts such as spectrum sharing, RAN/network sharing or network slicing. The exchange of services or resources among actors in these scenarios could be significantly automated and secured by the introduction of Blockchain (BC) to enable an economically driven and flexible network management. Through BC, providers can operate from the cloud to trade radio and network resources as-a-service, which enables novel trends such as autonomous network slicing or spectrum sharing with programmable and scientific trust.
A BC is a decentralized, distributed record of transactions stored in a permanent and near inalterable way. Unlike traditional databases, typically administered by a central entity, BCs rely on a peer-to-peer (P2P) network of so-called miners that no single party can control. Authentication of transactions is achieved through cryptographic means and a mathematical consensus protocol that determines the rules by which the ledger is updated. This technology is useful to provide immutability, transparency, and security, which allows addressing multiple challenges in B5G networks. Besides the Bitcoin use case, BC technology has already been proposed to enhance multiple procedures in communications and networks [1], and some prominent examples are content delivery [2], network slicing [3], RAN sharing [4], or network management [5], [6]. Nevertheless, BC entails several widely documented technological challenges, such as heavy computational costs, scalability issues, high latency, and energy consumption [7].
While most of the BC applications and deployments in the real world are designed considering a stable wired communication environment, in this paper, we focus on a more challenging wireless network as the communication infrastructure of our BC. Specifically, we propose a BC-enabled resource provisioning approach where end users can apply for radio and network resources on-demand, according to an as-a-service vision, without being bound in the long term to a specific operator. The needed exchange of transactions happens over a wireless network. Without loss of generality, we consider BC transactions to be exchanged over an IEEE 802.11ax network, to account also for the additional challenge of decentralization in the unlicensed spectrum. In such types of contention-based networks, BC users and miners need to compete for wireless resources to exchange transactions and blocks.
In this context, we propose to model a wireless BC network through a batch-service queue based on a discrete-time Markov model that characterizes the latency introduced in the network. These aspects are key to the overall wireless system design. The longer it takes to distribute transactions and blocks in the BC network, the more the end-users performance is jeopardized, and the BC system becomes unstable, unreliable, and susceptible to forks. Based on the proposed model, we evaluate the resulting service latency using the Bianchi model [8] for IEEE 802.11ax. In close spirit to this paper, we find the works in [9], [10], where the Bianchi model was also used to characterize IEEE 802.11 links through which the BC operation takes place. In contrast to the available literature, our model considers the effect of timers, whereby blocks are mined periodically, and forks, which can be seen as a side effect of the distributed consensus mechanism.
We demonstrate through simulation results that the proposed discrete-time Markov model perfectly captures the wireless BC behavior when also forks and timers are considered. Model analysis, as a function of different key parameters, allows gaining interesting insight on the dropping probability, the delay introduced by the BC (for which it is possible to identify an optimal block size), and the characteristic of the fork probability. The rest of the paper is structured as follows: Section II overviews queue models for characterizing the delay incurred by the BC systems. Section III proposes a scenario where the BC is envisioned to enable resource provisioning in B5G. Section IV describes the proposed batch service queue model, and the corresponding results are provided in Section V. Finally, Section VI concludes the paper.

II. CHARACTERIZATION OF BLOCKCHAIN: RELATED WORK
A BC is a type of distributed ledger technology (DLT) that compiles transactions in blocks that are sequentially chained one after the other. The record of the transactions is maintained across several computers which communicate through a P2P network. Nodes enabled to add transactions to the BC are referred to as miners. The consensus mechanism allows the BC to operate without the need to rely on a central trusted central authority. This automation of transactions is one of the most valuable features of BC for trading in future mobile networks. BC was firstly introduced with the cryptocurrency Bitcoin [11]. Lately, and enabled by the advent of smart contracts (i.e., computer programs that self-execute the terms of a contract when specific conditions are met) introduced by Ethereum [12], the potential of BC was unleashed and incorporated into multiple domains [13].
The BC operation has been modeled in literature in multiple ways, ranging from analytical models to experimental tools [14]. In the analytical domain, one of the tools gaining importance is batch service queuing [15], [16], whereby packets leave the queue in batches, rather than individually. The batch property of these kinds of queues intuitively captures the BC idea of chains of blocks and has been already used to model the behavior of multiple technologies in communications [17] [18] [19].
Accordingly, the consensus-based confirmation procedure can be seen as a single-server batch service queue where packets (transactions) are served (mined) in batches (blocks). In this setting, the most relevant trade-off lies within the batch size and the fork probability. In both cases, the queuing delay is affected in a non-straightforward manner, and the most appropriate setting depends on factors like the arrivals rate, the number of miners, the implemented consensus mechanism, or the mining time (alternatively, the mining difficulty). Batch service queue models for BC have recently been introduced in [20], followed by the approaches in [21]- [25].
First, the work in [20] proposed a batch service queue model to understand the stochastic behavior of the transactionconfirmation process in Bitcoin. Later, this model was extended in [21] to improve its accuracy for short block sizes, which was achieved by modeling transaction inter-arrivals with a general distribution. To do so, a matrix analytic method was used to derive the steady-state distribution of the queue model states, which were defined by the number of transactions in the queue just before new transaction arrivals. This model was validated with trace-driven simulations, and results showed that exponential-type distributions are accurate for estimating the mean confirmation time in Bitcoin. Similarly, the work in [22] attempted to overcome the complexity of the model in [20], [21] by separating the batch service queue into two separate processes, corresponding to block generation and block mining, respectively. This approach was later generalized by the same authors in [24]. Finally, a further evaluation was provided in [25], where a slightly different discretetime queue model was used to study game-theoretical aspects related to the pricing associated with mining transactions.
Differently to the approaches discussed in [20]- [22], [24], in this work we model queue states at departure instants, which was also considered in [23]. Through this approach, the authors of [23] were able to provide a more detailed performance evaluation of BC, on Ethereum. Unlike what proposed until the date, we further extend the batch service queue to incorporate the key effects of timers and forks within the BC operation. To the best of our knowledge, none of these features has been considered before in any BC model. We believe that these features are fundamental to any BC model for multiple reasons. First, timers are important to break the dependence of the mining procedure on the arrivals rate, which allows guaranteeing a maximum waiting delay, even if blocks are not filled with transactions (i.e., blocks are mined periodically). Disregarding the effects of timers leads to poor accuracy when deriving the queue status or the expected delay [26]. Second, the forks are a dramatic source of instability in BC. The appropriate modeling of their behavior ensures high accuracy and fidelity to capture the BC network's real dynamics.

III. SYSTEM MODEL A. Overview of the scenario
End users are not necessarily bound to a specific operator in the long term but, at any moment, can trigger requests to get specific data services. Based on the BC technology, the User Equipment (UE) devices issue smart contracts that facilitate automatic, transparent, and auditable mechanisms whereby operators and service providers fulfill UE requests. The smart contracts (indicating service indicators such as duration, maximum latency, or throughput) are registered in a public BC, which enables flexible and decentralized ondemand network access.
In the proposed scenario, UE smart contracts are submitted to the closest AP [10], which, besides providing radio access to the UEs, act as peer nodes in the BC P2P network. An AP is responsible to carry out tasks such as broadcasting transactions, storing a copy of the BC, achieving consensus, or mining blocks. In this paper, we focus on analyzing the delays to get the UE requests to reach the mobile operators, leaving for future work the study of how the service is provided by the selected operator to the UEs.

B. Blockchain delays
In the proposed BC-enabled communication environment, peers (miners) generate candidate blocks with transactions (service requests) from the UEs, which are mined once the block size S B is reached, or when a timer T w expires. To mine a block, peer nodes run a given consensus mechanism such as Proof-of-Work (PoW) and then propagate it over the P2P network. Upon successful block propagation, the winning miner is allowed to append the candidate block to the BC.
To assess the feasibility of the BC operation, it is important to identify its associated delays, especially when running over wireless links. Despite providing security and decentralization capabilities, the delay associated to the BC may impact the performance of the underlying applications if the service latency is too high (e.g., V2X communications), and can also introduce instability in the BC, due to the increased risk of forks. Considering the proposed BC-enabled procedure, we identify the following steps for a UE request to be served: 1) Smart contract upload: first, the UE selects the closest peer node to submit a smart contract to indicate the requirements of the requested service. Then, P2P nodes verify and propagate the received transactions over the P2P network. At this stage, it is important to collect valid, non-conflicting transactions (e.g., to prevent double-spending). The delay for uploading smart contracts (T up ) depends on the capabilities of the communication links between UEs and peer nodes, which may vary depending on the technology (e.g., IEEE 802.11) and the environmental conditions (e.g., distance, interference, frequency of operation). 2) Queuing: Valid transactions are queued before being included into candidate blocks. The queuing delay (T q ) depends on the number of arrivals, the mining rate, and the block size. Transactions are included into the candidate block till the block size is reached, or the timer T w expires. The queuing delay is characterized in Section IV by modeling the BC as a batch-service queuing system. 3) Block generation: Peer nodes execute the consensus algorithm until finding the block's nonce, or until receiving a new valid mined block. As widely considered in the literature [27], [28], the block generation time (T bg ) is modeled as an exponential random variable with parameter µ, which is assumed to be the same for all the miners. 1 4) Block propagation: The winning miner generates a new block, based on its candidate block, which is distributed through the P2P network with a delay of T bp . Once the mined blocks are propagated, the included transactions are put into effect.
Notice that steps (2)-(4) may be repeated as a result of forks. A fork can be seen as a side effect of the consensus mechanism and the communication and distribution delay required for the synchronization of the BC, which leads to splitting the BC into different paths, each one representing a potentially different status of the BC. If a miner different than the winner (i.e., the miner that mined the block in the shortest amount of time) succeeds in generating a new block while the first successful block is still being propagated, some uninformed miners may mistakenly add the second block to their version of the BC. Assuming that M miners with the same exponentially distributed block generation rate µ start the mining process synchronously, the fork probability can be defined as: 2 where T bg (w) is the winner's block generation delay. It can be noticed that, for a fixed mining capacity, the higher the propagation delay, the higher the fork probability and the more unstable the BC will be.
To sum up, and taking into account the effect of forks, the BC operation incurs the following end-to-end delay to make a UE request effective:

IV. BATCH SERVICE QUEUE MODEL
We consider a batch-service queuing approach to model the time a transaction spends in the ledger before being validated. In a finite-length M/M s /1/K queue, s denotes the number of packets served altogether. The batch characteristic is useful to represent the BC operation, where the mining procedure starts when the block size S B is reached, or when the timer (T w ) expires (see Fig. 1). In particular, we are interested in calculating the average number of packets in the queue (E[Q]), which allows deriving the expected queuing delay (E[D]), including both T q and T bg . For that purpose, we first model the queue status at departure instants π d , as done in [17]. Then, we derive the queue's steady-state distribution π s by solving a finite number of system of equations. We use Little's law [29]

to obtain the expected delay, so that E[D] = E[Q]
λ(1−p b ) , where λ is the total arrival rate, considering all the UEs, and p b = π s K is the blocking probability (the probability of discarding a transaction because the queue of length K is full). Finally, the expected queue occupancy is obtained as E[Q] = K k=0 kπ s k .

A. Departures Distribution
We define the status of the batch service queue at the n-th departure instant as: where q n−1 is the status of the queue after the previous departure, a(q n−1 ) is the number of new arrivals during the last inter-departure epoch, s(q n−1 ) is the number of packets served in a batch, and K is the queue length. Based on this, we derive the departure probabilities by considering the set of feasible states Ω(q n ) that are reachable from any state q n . To further illustrate this, Fig. 2 shows an example of the possible transitions from state q n = S B +1. From that state, a(q n−1 ) is limited by K (the maximum reachable state is K−S B +1), and the minimum reachable state is upper bounded by q n − s(i). In general, the set of feasible destination states Ω(i) that can be reached from state i is j ∈ [i − s(i)] + , K − s(i) . Notice that any transition to j > K − s(i) is not possible because the transitions to be served are kept in the queue until the block is mined. Under the assumption that arrivals and departures follow independent Poisson and exponential distributions, respectively, and by being aware of the possible inter-departure transitions, the probability p i,j for reaching a state j from i is as follows: 0, otherwise (4) The first case ([i−s(i)] + ≤ j < K −s(i)) indicates that the maximum queue size is not reached with new transactions. In turn, the second case (j = K − s(i)) refers to the situation in which the queue is filled because the system received, at least, K − s(i) transactions during the inter-departure epoch. Other transitions are unfeasible. Since arrivals and departures follow independent Poisson and exponential distributions, respectively, the probability p i,j for [i − s(i)] + ≤ j < K − s(i) can be rewritten as: The departure probability distribution π d can be obtained from the transition-probability matrix P, which is built with probabilities p i,j . In particular, π d can be calculated by solving π d = π d P, provided that π d 1 T = 1.

B. Steady-state Distribution
From the departures distribution π d , the steady-state queue occupancy distribution π s can be derived thanks to the Poisson Arrivals See Time Averages (PASTA) property [30] (or random observer property). The PASTA property states that, for Poisson processes, the queue status at any arbitrary time, π s k , is equal to the status probability at which random arrivals find the queue, π a k . To compute the steady-state distribution, we must first consider the time the queue spends in each state i, T (i), which, as shown earlier, is divided into filling and mining periods. In particular, the time T (i) the system spends until the next departure from state i is given by: which depends on the probability τ (i) that the timer T w expires before the minimum block size S B is reached from state i. In particular, for any state i < S B , the timer expiration probability is given by: With the departures distribution π d and expected time spent in a given departure state, the steady-state probability of a state k ∈ [0, K] is derived as in Eq. 8. Notice that, to include the effect of the timer for k < K, we need to consider the exact amount of packets that can be observed during the filling procedure, which conditions the probability of observing state k in the mining phase. In particular, from any departure state i, we consider the probability of observing exactly n packets (denoted by P(n|τ )) independently, given that n < S B − i and that the timer expires.

C. Considering forks
To capture the effect of forks with the model, we need to consider that forks affect the mining procedure in two main ways: 1) The fact that several miners work concurrently affects the mining rate. 2) Transactions involved in a fork are re-added to the pool of unconfirmed transactions (i.e., the queue). Throughout this work, we assume the worst-case scenario where all the transactions involved in a fork are re-added. Regarding implication 1), we need to consider the first order statistics of the individual exponential random variables characterizing the mining time.
Definition 1. Let X i be an exponential random variable and X (k) be the k-th smallest instance among n occurrences X 1 , ..., X n . Assuming that X (i) is a reordered sequence of X i , s.t. X (1) ≤ X (2) ≤ ... ≤ X (n) , then X (1) is a random variable Exp(nλ) whose distribution is f X (1) (x) = nλe −nλx , and whose expected value is E[X (1) ] = 1 nλ . With this, we capture the competition among miners (the first one to mine a block, wins), which leads to characterizing the mining time as a joint exponential distribution Exp(nλ). Now, assuming synchronization among miners and that the same transactions are included in any block replica, we address implication 2) by modifying the behavior of the queue when a departure occurs. This affects the transition probability matrix P and the blocking probability p b , since transactions may not leave the queue after a departure epoch, provided that forks occur. In particular, the number of served transactions from departure state i, namely s(i), is defined as follows: where t b,w ∈ T i =w is the set of transactions included in winner's block b that have not been affected by the fork (i.e., the set of non-overlapping transactions). Assuming that miners include exactly the same set of transactions to every block replica, t b,w = ∅.

V. PERFORMANCE EVALUATION
In this Section, we validate the proposed batch-service queue model and evaluate the performance of BC IEEE 802.11ax networks in cellular-based random deployments.

A. Simulation Parameters
To characterize the IEEE 802.11ax links used by the BC nodes, we use the Bianchi's Distributed Coordination Function (DCF) model [8], which allows estimating the saturation throughput Γ of DCF overlapping devices as a two-step probability function: where p slot,s is the probability of transmitting successfully at a given slot, E  As for signal propagation effects, we have considered a standard log-distance path loss model with shadowing effects. In particular, the loss observed between nodes i and j is:

B. Numerical Results
We start validating our queue model with simulation results. 3 Fig. 3 shows both model and simulation results of the queuing delay, for different user arrivals rates and block sizes. For all λ and S B values, two different timers values (T w = 0.5s and T w = 2s) are selected to showcase the situations in which the timer is likely or not to expire, respectively, before filling a block. Besides, the presence or not of forks is included in the validation. As Fig. 3 shows, model results match with simulations, thus demonstrating that the model properly captures the effect of both timers and forks. To better illustrate the impact of the different parameters (λ, S B and T w ), Fig. 4(a) and Fig. 4(b) show the queuing delay and the drop probability, respectively, observed with and without forks. For each considered block size S B , we have averaged the results for different user arrivals, namely λ = {2.5, 5, 7.5, 10, 12.5, 15} arrivals per second. This time, only model results are provided.  As shown, the queue delay is optimum at S B = 6 Kbits. From that point, the delay increases with the block size, even if forks are enabled or not. As for the timer values, we observe that the queue delay is significantly reduced when the timer is low (e.g., T w = 0.1 s). The timer is particularly useful to reduce BC latency when the number of arrivals is low and blocks are not filled with transactions at the necessary speed. Nevertheless, setting the timer to a low value contributes to generating more overhead and may also be counterproductive in terms of delay (notice that the mining time is insensitive to the number of transactions in a block).
As for the fork probability, it increases with the block size until saturation. Specifically, the higher the block size, the higher the block propagation time, which, for a fixed mining rate, contributes to making forks more likely to occur. An increase in the fork probability has a great impact on the number of drops, thus packet losses are noticed even for small timer values (i.e., even if the queue is not full).
Finally, we assess the performance of the BC-enabled resource provisioning application for different user densities. Fig. 5 shows the end-to-end latency of the wireless BC for validating transactions. We have considered up to 30 concurrent STAs with full-buffer traffic. The block size is set to the fixed value of 6 Kbits so that the queue delay is minimized, whereas the transactions arrival rate (λ) is set to 7.5 arrivals per second. Moreover, for each considered density, we have simulated 10 random deployments for averaging purposes. The delay obtained over shared IEEE 802.11ax links is compared to the one where the P2P network operates over dedicated IEEE 802.11ax wireless channels.  As shown in Fig. 5(a), for the ideal case where no forks occur, the use of shared IEEE 802.11ax links is affordable even if network density increases. This is due to the low amount of network resources used by the BC application. In contrast, when forks are considered (see Fig. 5(b)), the latency increases dramatically with the network density. The block propagation delay increases when the number of concurrent users is high. This leads to a high fork probability, which negatively impacts the number of attempts for validating transactions.

VI. CONCLUSIONS
In this paper, we have envisioned a future wireless system where users are not bound to a specific operator and apply for resources through smart contracts. BC allows secure and decentralized transactions among users and operators, but its latency performance represents a challenge for the service perception of the UE and for the stability of the BC, which will increasingly suffer from forks as the latency augments. While BC systems are normally based on wired P2P networks, in this paper we foresee the BC to be based on a wireless infrastructure. We have focused on IEEE 802.11ax, to add the additional challenge of contention in the performance evaluation. With the aim to investigate the wireless BC performance, we have analytically modeled the BC through a batch queue serving system based on a discrete-time Markov model. Results have revealed that our model perfectly captures the behaviors of the wireless BC, including timers and forks, which is novel in literature, and shown interesting optimal points of the block size and behaviors of the fork probability, as a function of both the network and BC are designed.