{'fraction_non_alphanumeric': 0.03121336950333233, 'fraction_numerical': 0.009009009009009009, 'mean_word_length': 4.484937545922116, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Analysis of Non-Persistent CSMA Protocols with Exponential Backoff Scheduling

This paper studies the performance of Non-persistent CSMA/CA protocols with K-Exponential Backoff scheduling algorithms. A multi-queue single-server system is proposed to model multiple access networks. The input buffer of each access node is modeled as a Geo/G/1 queue, and the service time distribution of head-of-line packets is derived from the Markov chain of underlying scheduling algorithm. The main results include the complete analysis of the throughput and delay distribution, from which we obtained stable regions with respect to the throughput and bounded mean delay of the Geometric Retransmission and Exponential Backoff schemes. We show that the throughput stable region of Geometric Retransmission will vanish as the number of nodes n \rightarrow \infty; thus, it is inherently unstable for large n. In contrast to Geometric Retransmission, the throughput stable region of Exponential Backoff can be obtained for an infinite population. We found that the bounded mean delay region of Geometric Retransmission remains the same as its throughput stable region. Besides, the variance of service time of Exponential Backoff can be unbounded due to the capture effect; thus, its bounded delay region is only a sub-set of its throughput stable region. Analytical results presented in this paper are all verified by simulation.


I. INTRODUCTION
Carrier Sense Multiple Access (CSMA) is one of the most widely deployed Media Access Control (MAC) protocols that allow multiple users to share a common transmission channel, such as 802.11 wireless LAN and Ethernet. Since Abramson's landmark paper on the ALOHA systems [1] embarked on the throughput analysis of multiple access channels, many researchers have followed his approach in studying other MAC protocols including CSMA. The analysis of CSMA can be traced back to Kleinrock and Tobagi's paper [2]. Under the assumption that there are infinite numbers of nodes and the aggregate traffic form a Poisson stream, they derived the throughput of various CSMA protocols by using an approach based on renewal theory. Although the characteristic equation of throughput can be easily obtained by using this elegant method, the ability to guarantee a stable throughput of the entire network and to bound the mean delay of packets are still open problems when analyzing the performance of CSMA protocols.
In the Non-Persistent Carrier-Sense Multiple Access (NP-CSMA) protocol, the node takes action after sensing the channel status. If the channel is in the idle state, the packet is sent immediately; otherwise, the packet is delayed for a random amount of time before sensing the channel again. Collisions may occur when two or more packets are simultaneously transmitted.
Almost all follow-up research on the performance analysis of CSMA protocols [3]- [7] has been based on the network model originally proposed in [2]. For example, the characteristic equation for network throughput was re-derived in [3] by using a state-transition diagram of the transmission channel. The saturation throughput for NP-CSMA is deduced from the semi-Markovian property of the protocols in [4]. Some variants of slotted NP-CSMA with an adaptive array to improve throughput performance are proposed in [5].
Collisions are unavoidable in a shared environment, and a contention resolution algorithm is an essential mechanism in any MAC protocol to resolve contention among active nodes. However, previous analysis in [2]- [5] did not take the scheduling of collided packets into consideration.
Exponential Backoff algorithm is a widely adopted collision resolution scheme in most MAC protocols. It was shown in [6] that Exponential Backoff for MAC protocols was unstable for an infinite number of nodes. The authors of [7] claimed that if the arrival rate of the system is sufficiently small, the Exponential Backoff can still be stable. Despite these unfavorable observations, it is proven in [8] that a stable throughput can be achieved by the Exponential Backoff even if the number of nodes goes to infinity. Currently, a consensus on the stability issue of the Exponential Backoff scheme cannot be concluded from these controversial results.
A drastically different approach, based on a Markov chain model to analyze IEEE 802.11 with Exponential Backoff scheme, is proposed in [9], which provides extensive throughput analysis of the IEEE 802.11 with the Distributed Coordination Function (DCF) mechanism but ignored the delay aspect of performances. A frame delay analysis based on a similar Markov model is introduced in [10], which only covers the mean service time under the network saturation condition. Access delays of slotted ALOHA and CSMA without considering scheduling are given in [11]- [13]. It is arduous to study the queuing delay without a full analysis of the service time distribution that incorporates the scheduling algorithm. In facing the difficulty of precisely modeling the system, many simulation results on the performance of CSMA were reported in [14]- [16]. In a nutshell, any models of the network that ignored the queuing behavior of the input buffer of each node were unable to completely tackle the stability and delay issues of the protocol.
The intent of this paper is to provide a complete analysis of NP-CSMA/CA based on a multi-queue single-server model of the multiple access channel with n nodes, as shown in Fig. 1, that are governed by NP-CSMA/CA protocol. In this two-stage queuing model as mentioned in [17], the input buffer of each node in the first stage is a FIFO (first-in-first-out) queue, and we assume that the input to each node is a Bernoulli process with rate λ. The second stage is a fictitious queue that consists of all HOL (head-of-line) packets of n nodes with aggregate attempt rate G. According to the theorem on the superposition of point processes proved in [18], the aggregate attempts form a Poisson process for large population. The service time of HOL packets depends on the backoff scheduling algorithm when collision occurs. Therefore, it is impossible to achieve a comprehensive analysis of the system without considering the impact of the scheduling algorithm on the input queuing behavior. As mentioned earlier, most existing studies [8]- [11] and [19] focused on the aggregate attempts generated by HOL packets that input to the second-stage queue, from which an overall network throughput can be easily obtained. However, the stability and bounded delay conditions of each individual input queue cannot be comprehended by those simplified models. This point is clearly stated in [20] that focusing on aggregate attempt rate G only is not enough to study the effect of retransmission policy.
The second-stage queue is characterized by a system model of the transmission channel, from which we derived the characteristic equation of the throughput. The result is consistent with that reported in [2] and [3]. We then model the first stage input buffer as a Geo/G/1 queue, in which the service time is specified by a Markov chain that represents the backoff scheduling algorithm. The complete queuing analysis enables us to specify the stable regions of both throughput and bounded mean delay. The network has a stable throughput when the channel's output rate equals the aggregate input rate. Our queuing analysis shows that the condition of throughput stability is determined by the first moment of service time, or offered load. Moreover, the Pollaczek-Khinchin (P-K) formula of Geo/G/1 queue indicates that a bounded mean delay also requires a bounded second moment of service time, which depends on the retransmission scheduling algorithm employed in the NP-CSMA protocol.
Two retransmission schemes are of importance, Geometric Retransmission and Exponential Backoff. For the Geometric Retransmission scheme, we find that the stable region of throughput is the same as the bounded delay region for a finite number of users. However, it is intrinsically unstable if the number of nodes in the network is infinite. For the Exponential Backoff scheme, there exists a throughput stable region even for an infinite population, which agrees with the result of [8] that the network with Exponential Backoff can have stable throughput even if the number of nodes n→∞. This scheme is more robust and can scale to large numbers of nodes.
The rest of this paper is organized as follows. The system model and input buffer model that give the characteristic throughput equation of the NP-CSMA protocol are presented in section II and section III, respectively. The general stable condition is described in section IV. The throughput and delay stability issues of the Geometric Retransmission and Exponential Backoff schemes are discussed in section V and VI, respectively. The conclusion is given in section VII.

II. MARKOV CHAIN OF SLOTTED NP-CSMA
In a slotted NP-CSMA network, the time axis is slotted and the network is synchronized.
Packets can be sent only at the beginning of a timeslot, and each packet transmission takes one slot time. We adopt the assumptions made in [2] that the processing time for sending an acknowledgement packet is negligible, and the ratio of propagation delay to packet transmission time is a. Then the timeslot can be further divided into mini-slots of slot size a. According to the channel status, the time axis can be considered as a sequence of alternating busy periods and idle periods as shown in Fig. 2a. The duration of a busy period is 1+a timeslots because no packets will attempt to transmit in the mini-slot immediately following a busy period.
The length of an idle period is a random variable with geometric distribution. In each busy period, either a packet is successfully transmitted or a collision occurred. Therefore, the channel will be in one of three states: idle (Idle), successful transmission (Suc), and collision (Col). The state transitions of the channel can be described by the Markov chain shown in Fig. 3.

The limiting probabilities ,
Idle Suc π π , and Col π of the Markov chain satisfy the set of equations: (1) Since packets attempt to access the channel only when the channel is detected as idle, the attempt rate in any busy period is zero. During an idle period, the aggregate attempts generated by all fresh and re-scheduled HOL packets form a Poisson stream with rate G, and the probability that no attempts is generated in a mini-slot is e −aG . Viewed by the system, a transmission period is successful only if there is exactly one attempting packet in a mini-slot with the probability aGe −aG . Hence, the transition probabilities of the Markov chain are given by , , It is straightforward to show that the limiting probabilities are given as follows: The time-average probabilities of each state can be easily obtained from sojourn times of Idle, Suc, and Col states Idle t a = , 1 Suc t a = + , and 1 Col t a = + , respectively. Of particular importance, the probability that the channel is in Suc state is given by Since the successful transmission of a packet only takes 1/(1+a) of the time in a busy period, the throughput of the network is defined by the fraction of the time that the channel is productive: ( ) which is consistent with Kleinrock and Tobagi's result [2]. Although the network throughput can be obtained from the above model, it is by no means a comprehensive performance analysis of the system, because this model does not consider the re-scheduling of collided HOL packets. The next section describes a more detailed queuing model of the input buffer in which the service time distribution is derived in cooperation with the backoff scheduling scheme.

III. QUEUING MODEL OF INPUT BUFFER
The input buffer of each node is modeled as a Geo/G/1 with Bernoulli arrival process of rate λ packets/timeslot. In the NP-CSMA protocol, we consider a general backoff scheme, called the K-Exponential Backoff algorithm, for contention resolutions. A fresh HOL packet is sent only when the idle channel is being sensed, and the packet is scheduled for retransmission at a later time if a collision occurred. A backlogged HOL packet is in phase i if it has encountered collisions i times. The K-Exponential Backoff algorithm allows an HOL packet in phase i to retransmit with probability q i , for i = 1, …, K, where 0 < q < 1 is the retransmission factor and K is the cut-off phase. That is, the retransmission probability decreases exponentially with the number of collisions, up to K times, experienced by the HOL packet.
Let α be the probability that the channel is being sensed in idle. Besides idle periods, the channel will also be sensed in idle state in the first mini-slot of each busy period because of the propagation delay. Therefore, the time-average probability that the channel is sensed idle can be calculated from the limiting probabilities given by (3) as follows: As shown in Fig. 2b, the signal received by a node is shifted one mini-slot due to the propagation delay. Thus, the idle mini-slot immediately following a transmission period is still considered to be a part of the busy period by HOL packets. Also because of the propagation delay, a transmission can be successful only if all other nodes do not attempt to send in the first mini-slot of the busy period. Thus, the probability of a successful transmission of an HOL packet is p= e -aG . In the NP-CSMA protocol, an HOL packet in phase i can be in one of the three states: sensing (S i ), transmission (F i ), and waiting (W i ), i = 1, …, K at any time. The state transition diagram is shown in Fig. 4. If an idle channel is detected in the sensing state S i , then the packet will be transmitted in state F i with probability q i . If a busy channel is sensed, the packet is in waiting state W i . If the transmission is successful, a fresh HOL packet starts with the initial sensing state S 0 ; otherwise, the collided packet is moved to phase i + 1 and the above process repeats starting from the sensing state S i+1 . Moreover, we assume that a new packet arrived at an empty buffer will be delayed for one slot time in the waiting state if the channel is busy. The duration of this waiting time is not specified in non-persistent CSMA protocol. In fact, the sojourn time of the waiting state will not affect our analysis. Different waiting time may result in different delay, but the analyses of the stable throughput region and bounded delay region remain the same. Hence, the waiting time is assumed to be 1 slot time for the sake of simplicity.
From the Markov chain described in Fig. 4, we obtain the following set of state equations: , for 1,..., 1; It is easy to show from (7) that if p + q > 1 then all states of the Markov chain are positive recurrent and aperiodic. Let s i , f i , and w i be the limiting probabilities of states S i , F i , and W i, respectively. Thus, the time-average probabilities of those states can be determined from (7) The offered load ρ of each input queue is the probability that the queue is non-empty. It is the 8 basic measure for analyzing the performance of each input buffer. The input rate λ of the Bernoulli arrival process can be interpreted as the probability of finding a packet arrived at input in any time slot. Each input packet will eventually become a fresh HOL packet, and visit the transmission state in phase 0 for one slot time. Therefore, the input rate λ should equal 0 f ρ , the probability of finding an HOL packet in the phase 0 transmission state in any time slot. With the time-average probability of state F 0 given in (8), the expression of the offered load can be obtained as follows: Hence, the mean service time of each HOL packet [ ] E X is equal to 0 1 f . We show in the next theorem that the network throughput derived from the service time of HOL packet is the same as (5), which was obtained from the system model. Although the service time is obviously dependent on the retransmission factor q of the backoff scheduling, the fact that the throughput is invariant with respect to q implies that the stability of the system cannot be determined by the characteristic equation of throughput alone; it is mainly related to the queuing behavior of each input buffer.
The probability that the node senses an idle channel is given by Substituting (6) and (9) into (12) and (13), then the probability of successful transmission p defined by (11) can be expressed as It is easy to show from (14) that the network throughput in equilibrium is given by (10). □ It should be noted that the throughput given by (10) also agrees with that obtained by Kleinrock and Tobagi in [2] and our channel model in section II. The consistency between these approaches indicates that it is appropriate to adopt the independence assumption among input buffers. This is because the correlation among n input queues becomes weak in a multi-queue system when n is large [21].
Furthermore, let random variables , i i S F * * and i W * be the service completion time of an HOL packet, starting from the states S i , F i , and W i , respectively, until it is successfully transmitted. We assume, without loss of generality, that M = 1/a is an integer. It is easy to show from the Markov chain of Fig. 4 that the generating functions S i (z), F i (z), and W i (z) of these service completion times can be found by solving the following set of equations:  ( ) ( ).
Let X denote the service time of a HOL packet. Since the service of each HOL packet starts from state S 0 , therefore the first and second moments of service time, E[X] and E[X 2 ], can be derived from the generating function S 0 (z), which is given in Appendix I. Note that the mean service time derived in Appendix I is consistent with the expression 0 1 f given by (9). Based on the queuing model of the input buffer, we will investigate various stability issues of NP-CSMA concerning throughput and delay in the following sections.

IV. STABLE REGIONS
Intuitively, if the attempt rate G is too high, the probability of successful transmission p = e -aG will be too small; if it is too low, then the channel may not be fully utilized. Similar to the Aloha system discussed in [17] that the maximum throughput max λ can be expressed in terms of the Lambert W function 0 ( ) W z , which was first considered by J. Lambert in 1758, and later studied by L. Euler [22]. Taking the differentiation of the throughput equation (10), the maximum throughput max λ can be derived with a corresponding attempt rate G * and expressed as below, As plotted in Fig. 5, for any attempt rate G < G * , the network throughput increases with attempt rate G; otherwise, the throughput decreases with G. Therefore, for any throughput smaller than the maximum throughput, maxλ λ < , the characteristic equation (10)  , the attempt rate G should satisfy In general, the attempt rate G is an implicit function of the retransmission factor q associated with the underlying scheduling algorithm. This functional relationship, together with the inequality (17), determines a stable region of q. For the NP-CSMA protocol with exponential backoff scheduling algorithm, the expression of attempt rate G in terms of q is given below.
Suppose that there are a total . The attempt rate G can be obtained from (8) and (18), and expressed as follows: The retransmission factor q can be expressed as a function of the attempt rate G, denoted as ( ) q h G = , by solving equation (19). It is easy to show that the function ( ) h G is monotonic increasing with respect to G. Thus, a region of the retransmission factor q, called stable throughput region I, can be specified by the combination of (17) and (19) as follows: [ ] ( ), ( ) The network throughput is defined by In particular, the attempt rate G will reach G L when the offered load  = 1. T herefore, if the retransmission factor q is chosen from the stable region I R , the offered load ρ of Geo/G/1 queue of each input buffer should be strictly less than 1, which is the stable condition of any queuing systems that the arrival rate should be less than the service rate.
Let G t be the instantaneous attempt rate in timeslot t. Since the steady state mean attempt rate G of a Poisson stream is defined by the time average of instantaneous attempt rates: Thus, the stable throughput region I, determined by the steady state mean attempt rate G, could be too loose to cope with the fluctuations of the instantaneous attempt rates G t, and the network may become unstable if G t is larger than G L at some point in time t. To prevent this risk, the following conservative estimate ˆL G of the upper bound of the stable throughput region is given in (54) of Appendix II: which takes the variance of G t into consideration to ensure that the instantaneous attempt rate G t will be strictly less than G L with a probability higher than .99 at any instants of time. Solving (54) forˆL G , we have On the other hand, the risk is marginal if the instantaneous attempt rate G t drops below G S at some time t. Because the probability of success p becomes large when the attempt rate is so low, the throughput eventually climbs back and becomes equal to the input rateλ in steady state. Therefore, a conservative region of retransmission factor q, called stable throughput region II, can be specified by (23) as follows: As we mentioned before, the throughput stable condition (17) is not sufficient to guarantee a bounded mean delay of packets queued in each input buffer. To complete the analysis of stable regions, we deduce the following additional constraint from our queuing model of the input buffer.

Bounded Delay Condition
The condition BDC is more restrictive than the condition STC. A region of the factor q, denoted as D R , that guarantees bounded mean delay can be determined by the second moment of service time E[X 2 ]. In general, the bounded delay region is a subset of the throughput stable region.
Detailed discussions on these stable regions of two particularly important scheduling schemes, Geometric Retransmission and Exponential Backoff, are provided below.

V. ANALYSIS OF GEOMETRIC RETRANSMISSION
The simplest exponential backoff scheduling is the Geometric Retransmission with cutoff phase K=1. In this section, we study both stable throughput region and bounded delay region of the retransmission factor q of Geometric Retransmission.

A. Stable Throughput Condition of Geometric Retransmission
The attempt rate G for this scheme can be obtained by substituting K = 1 and p= e −aG into (19), which yields the following expression: or, equivalently, the retransmission factor q can be expressed as a function of G given by For retransmission factor q in the range 0 < q < 1, it is easy to show that the function h(G) is monotonic increasing with respect to the attempt rate G. Hence, the following stable throughput region I for Geometric Retransmission can be immediately obtained from (20) and (27): For a = 0.1 and n = 50, the stable region (28) of retransmission factor q lies in the shaded part displayed in Fig. 6, which shows the stable throughput range of q for a given input rate maxλ λ ≤ .
Moreover, the conservative stable throughput region Ge II R for Geometric Retransmission can be derived from (24) and (27), and given as follows: The above risk prevention mechanism is achieved at the expense of sacrificing the maximum For Geometric Retransmission, both throughput stable regions I (28) and II (29) will be vanished when the number of nodes n goes to infinity; hence, the network is unstable for any retransmission factor q. When the network is fully congested, the attempt rate G for a large number of nodes n is given by (27) as follows: That is, a large number of packets will be backlogged in phase 1 when n → ∞. As a result, the probability of successful transmission 0 anq p e − = → , and the network will become unstable. For the same reason, Exponential Backoff with finite cut-off phase K is not scalable. The instability of Geometric Retransmission has also been reported by others in [8] and [19]. Fig. 7 shows that our analysis is consistent with simulation results for a network with n = 50 and a = 0.1. Both results indicate that a stable throughput can be achieved if q is chosen within the region Ge II R , and the throughput quickly drops to zero outside this region.

B. Bounded Delay Condition of Geometric Retransmission
For the Geometric Retransmission scheme, the following second moment of service time is derived through (42) of Appendix I as follows: where A(p, q) is a polynomial of p and q, and A(p, q) > 0. From the expression shown in Appendix I, the second moment is always bounded within the stable throughput region II. Therefore, the bounded delay region is shown in Fig. 8. Both analysis and simulation demonstrate that the mean delay is unbounded when q is larger than 0.233, which is the upper bound of Ge II R calculated from (29). In sum, our results indicate that the NP-CSMA protocol with Geometric Retransmission cannot be scaled to a large number of nodes n. A much more robust scheduling algorithm, Exponential Backoff, is discussed in the next section.

VI. ANALYSIS OF EXPONENTIAL BACKOFF
The Exponential Backoff scheme has been studied in many previous papers [7]- [11]. In this section, we discuss the stability and delay performance of this scheduling algorithm based on the stable throughput and bounded delay conditions specified in section IV.

A. Stable throughput Condition of Exponential Backoff
The following attempt rate G of Exponential Backoff can be derived by taking the limit of (19) as K goes infinity and then substituting p= e −aG into the resulting (19), which gives the following or, equivalently, the retransmission factor q can be formulated as a function of attempt rate G as ( ) Again, this function ( ) q h G = is monotonically increasing with respect to the attempt rate G.
Hence, the following stable throughput region I of Exponential Backoff can be obtained from (20) and (33) Similar to the Geometric retransmission scheme, from (24) The retransmission factor Ex II q R ∈ ensures that the instantaneous attempt rate G t is strictly less than the desired upper bound L G with a probability higher than .99 at any time t.
Our stability analysis is confirmed by the simulation results shown in Fig. 10, which depicts that a stable throughput can always be achieved if the retransmission factor q is properly chosen from the stable throughput region Ex II 17 In contrast to Geometric Transmission, the following non-empty stable throughput region can be obtained from (35) when the number of nodes n goes to infinity: which coincides with Song's results on Aloha system with Exponential backoff shown in [8], [11] and [19] that the network throughput can be non-zero even when the number of nodes goes to infinity.

B. Bounded Delay Condition of Exponential Backoff
The second moment of service time of the Exponential Backoff scheme is given by (45) in Appendix I as follows: where B(p,q) and C(p,q) are two polynomials given by (46) and (47), respectively, in Appendix I.
Thus, the retransmission factor should satisfy following condition to guarantee a bounded second moment of service time E[X 2 ]: As shown in Fig. 9 stable throughput but the mean delay will quickly jump up to an unacceptable level as shown in Fig. 11, which exhibits the number of backlogged packets in the entire system versus retransmission factor q for a fixed aggregate input rateˆ0.3 λ = . It can be clearly seen that if 0.21<q<0.73, within the region of bounded delay, there is nearly zero backlogged packets in the system, and the mean delay is bounded according to Little's law in queuing theory. However, if the retransmission factor q is greater than the upper bound of the delay region, the number of packets in the system suddenly becomes much larger even when q is still within the throughput stable region, i.e., q>0.053. On the other hand, the simulation result of Fig. 11 also shows that the analytical lower bound of the region Ex D R given in (40) is much more conservative than the upper bound. Furthermore, compared with Geometric Retransmission for the case when n = 50 shown in Fig. 8, the Exponential Backoff has a larger bounded delay region for retransmission factor q.
In sum, the Exponential Backoff has two types of stable regions as shown in Fig. 9. The first type is the bounded delay region Ex D R , represented by the shaded area in Fig. 9, in which the network throughput is stable and the mean delay is bounded. The second type is the region \ Ex Ex II D R R that only guarantees stable throughput but with unacceptable large mean delay. In the Exponential Backoff, it is possible that predominating backlogged packets are pushed to deep phases with very low retransmission probabilities when the network becomes congested. If a node tries to send its HOL packet, the successful probability will be very high. Once the backlogged HOL packet is cleared, then the channel may be "captured" by subsequent packets in the input buffer, which are all in phase 0, until the queue is cleared. During this time, it appears that the network throughput is still stable, but the variance of the service time of each individual packet can be infinitely large due to this unfairness of services caused by the capture effect mentioned in [23]. Nevertheless, compared with the Geometric Retransmission, the Exponential Backoff is more robust and can scale to a larger population.

VII. CONCLUSION
A multi-queue-single-server model is proposed in this paper to explore the stability and delay issues of multiple access networks with the NP-CSMA protocol. We studied the throughput of the    28 Fig. 11. Number of packet in the system verses q for Exponential Backoff.