Investigating Random Linear Coding from a Pricing Perspective

Abstract

In this paper, we study the implications of using a form of network coding known as Random Linear Coding (RLC) for unicast communications from an economic perspective by investigating a simple scenario, in which several network nodes, the users, download files from the Internet via another network node, the sender, and the receivers as users pay a certain price to the sender for this service. The mean packet delay for a transmission scheme with RLC is analyzed and applied into an optimal pricing model to characterize the optimal admission rate, price and revenue. The simulation results show that RLC achieves better performance in terms of both mean packet delay and revenue compared to the basic retransmission scheme.

1. Introduction

In the concept of network coding [1], encoding operations are performed on a group of data packets (e.g., by using the exclusive-OR (XOR) function) before they are forwarded towards their destinations, which departs from the conventional store-and-forward transmission paradigm. It is established in [1] (for linear network encoding) and [2] (for random linear network coding) that network coding benefits the throughput for multicast transmission by increasing the amount of data delivered per unit time. Since it is capable of increasing network throughput, improving robustness to channel errors and simplifying the design of distributed architectures, various applications based on the concept of network coding have been developed to improve throughput, reliability and energy efficiency in a number of related fields, such as multimedia applications [3,4]. In particular, Random Linear Coding (RLC) provides a fully distributed methodology for performing network coding [5]. With RLC, each node in the network independently selects random code vectors or coefficients to encode the data packets it receives into random linear combinations of the original data packets. These linear combinations are then transmitted with the associated code vectors until the receivers decode the original information packets using Gaussian elimination. By exploiting the broadcasting nature of the wireless medium, RLC has also been combined with opportunistic routing in wireless mesh networks to avoid node coordination, which is required by traditional opportunistic routing, while providing significant performance gains [6,7,8,9,10]. The common idea behind these applications is that a source node encodes information packets using RLC, all intermediate nodes also need to perform RLC to encode the random linear combinations that they hear from the source node or other intermediate nodes and send out these new random linear combinations until the receiver decodes the original information packets.

In this paper, we study the performance of RLC from an economic perspective by investigating a simple scenario where a network node, the receiver, downloads a file from another network node, the sender, and the receiver as a user pays a certain price to the sender for this service. Note that, in wireless mesh networks, this sender could be either a source node or an intermediate node. We compare two communication schemes: RLC, in which a group of packets is encoded and the random linear combinations are transmitted until the receiver successfully decodes all the original information packets, and the basic retransmission scheme, in which a single packet is transmitted continuously until a successful delivery is confirmed.

Recently, a great deal of effort has been devoted to understanding communication network economics by both the engineering and economic research communities. From a profit-maximizing service provider’s perspective, its aim is to maximize its revenue while inducing desirable user response by using price as a soft admission control mechanism. From a delay-sensitive user’s perspective, service delay is one of the main factors that affect his/her satisfaction with the service, which is normally expressed by net utility, besides price. In this paper, our analysis is based on a provider’s revenue optimization model with users’ compensated utility, which is a function of mean packet delay and price, integrated as a constraint.

Given the fact that with RLC all the original information packets have to be decoded together only after a destination node receives a sufficient number of encoded packets, the transmission delay (defined as the time between the moment when the packet arrives into a sender and the moment when the packet has been successfully delivered and decoded by a receiver) obviously differs from that caused in the conventional retransmission scheme. Shrader et al. in [11] analyze the queueing delay performance for two different block-based random RLC schemes: coding over a fixed blocksize and a variable blocksize, which adapts to the traffic load, for multicast transmission over packet erasure channels by modeling random coding of packets as a bulk-service queueing system, where packets are served and depart the queue in groups. It is shown that RLC can offer benefits over uncoded transmissions in terms of both throughput and delay if the blocksize is adapted to the traffic load. It is also suggested in [11] that bulk-service queueing , which has been applied in other works (e.g., [12,13,14]), for RLC performance analysis, is an appropriate model to capture the fact that randomly arriving packets are encoded, transmitted, and removed from the queue in groups corresponding to blocks.

Due to the impact of RLC on the delay performance, it is interesting to study the implications of RLC from an economic perspective. The objective of this paper is to study the mean packet delay with RLC and quantify the impact of RLC from a pricing perspective by comparing the optimal admission rate, the optimal price, and the corresponding expected delay as well as optimal revenue obtained by a node using RLC with those obtained from the basic retransmission scheme. In this paper, the $Geo/G^K/1$ bulk service queuing model presented by Shrader et al. is slightly modified. As a result, the processing of the bulk service can be compared with a simple and well-documented $Geo/Geo/1$ queuing model and an approximate but analytically tractable expression for the mean packet delay with RLC can be derived. Based on this approximate expression, we analyze the optimal admission rate, the optimal price and the corresponding expected delay when the sender node chooses to use RLC and compare them with those obtained from the basic retransmission scheme to study the performance of RLC from an economic point of view.

The rest of the paper is organized as follows: We briefly discuss the related works in Section 2. Section 3 describes the system model and introduces some basic notations. Section 4 focuses on the analysis of the mean packet delay with RLC adopting the method proposed in [13]. In Section 5, the revenue optimization problem is set up to characterize the optimal admission rate, the optimal price and the corresponding optimal delay. Numerical examples are given and comparisons between RLC and the basic retransmission are provided in Section 6. Section 7 contains concluding remarks and ideas for future work.

2. Related Work

A great deal of work has been done to gain a better understanding of the delay behavior of RLC, which is instrumental towards its successful application, especially in real-time applications. Lucani et al. in [15] investigated the mean time to complete the transmission of a block of packets to all receivers for broadcasting in time division duplexing channels with the use of random linear network coding by modeling the process as a Markov chain. It is shown that there is an optimal number of coded data packets to be transmitted back-to-back to minimize the mean time to complete transmission of the block of packets. Using the techniques discussed in [15], Lucani et al. further studied the performance of a systematic network coding approach over time division duplexing channels in terms of mean completion time taking the field size into consideration [16]. It is shown that the proposed systematic network coding scheme can provide the same or close to the same performance in terms of completion time as a random linear network coding scheme using a large field size. Cogill et al. [17] analyzed the delay of a simple RLC scheme for transmitting packets across a relay network, which is modeled as a continuous-time Markov chain, and provide an upper bound on the expected transmission time for RLC.

Eryilmaz et al. [18] studied a broadcast model with RLC involved and show that network coding offers better performance in terms of delay under the assumption that there is a fixed amount of data awaiting transmission at the sender node. However, in a realistic network setting, the number of packets awaiting transmission varies due to queuing effects when the channel is ready for transmission. Moreover, Shrader et al. [11] showed that random linear coding can offer benefits over uncoded transmissions in terms of both throughput and delay if the blocksize is adapted to the traffic load. Shrader et al. [12] developed a bulk-service queuing model for RLC, in which packets randomly arrive at a source node for transmission to a single destination and the number of packets used in encoding is a variable with a predefined maximum value. Based on this $Geo/G^K/1$ queuing model, an expression is derived for the steady-state probability distribution for the number of packets in the queue, by which the mean packet delay of RLC for such a unicast model can be computed approximately. Ravanbakhsh et al. [13] further extended the work of Shrader et al. [12] and computed the mean packet delay of RLC with an improved expression. Due to the complexity of the $Geo/G^K/1$ queuing model, there is no general expression for the mean packet delay derived in [12,13].

The economic aspects of data transmission systems with RLC involved are rarely studied. Our work is in line with the work of Ahmed et al. [19], who analyzed the economic gains obtained from RLC for a multicast set introduced in [18]. In [19], a single base station broadcasts incoming files to multiple receivers and the base station sets a price per receiver and per file to maximize its profit. By studying the mean file completion times of network coding and scheduling strategies, Ahmed et al. suggested that network coding offers significant economic gains as opposed to scheduling. Our work differs from [19] by considering a unicast model, which is more realistic than a broadcast model. Moreover, we focus on the queuing delay instead of assuming that there is a fixed amount of data awaiting transmission.

3. System Model

Assume there is a group of users, where each downloads a certain file consisting of a certain amount of packets from a sender. In this file transfer process, information packets demanded by a user arrive at the sender’s queueing system and the sender transmits these information packets to the user accordingly. This file transfer process can be viewed as a “one-sender one-unicast” scenario. As suggested in [12,13], this transmission can be modeled as a queuing system where packets demanded by the user arrive to the sender according to a Bernoulli process with a rate $\lambda$, meaning the number of new packets arrive is either 1 or 0 with probabilities of $\lambda$ or $1-\lambda$, respectively, during a given time slot. For the sake of simplification, $\lambda$ is referred to as the arrival rate for the rest of the paper. Upon arrival at the sender, the packet is stored in the buffer (queue) of the sender to await encoding and transmission. Assume that the sender has unlimited buffer memory. In each time slot, a packet is transmitted from the sender to a user with reception probability $\mu$, $0<\mu \le 1$. Thus, the average service time for a single packet is $\frac{1}{\mu }$ time slots.

Assume further that there is no delay between sending a packet and receiving an acknowledgment if a packet has been successfully received, meaning that only the queuing delay is being considered in this paper. In other words, the mean packet delay is defined as the average time between the moment when the packet arrives in the queue and the moment when the packet has been successfully delivered and decoded.

With RLC, the encoding and transmission are performed on groups of packets as shown in Figure 1. In reality, wireless channels are affected by impairments, such as multipath and shadow fading. In this paper, we assume the channel sending packets from the sender to the user as a packet-erasure channel where a packet transmitted by the sender is successfully delivered to the user with probability $\mu$. As suggested in [12,13], this data transmission system can be represented by a discrete-time bulk-service queuing model. In [12,13], the number of packets used in encoding and transmission is a variable and must be smaller or equal to a maximum value K. This bulk service is modeled as a discrete-time $Geo/G^K/1$ queue. In this paper, we present a slightly different queuing model, where there is no maximum value limit. In other words, once the channel becomes free, all the packets $I_1,\dots ,I_k$ waiting in the queue, instead of only $k\le K$ packets, are selected for encoding and transmission.

The set $\{I_1,\dots ,I_k\}$ is referred to as a bulk. Note that k is a variable. The sender generates encoded packets $I_j^{\prime }$ based on the bulk. These k uncoded packets are called message packets or native packets and each encoded packet $I_j^{\prime }$ is a random linear combination of these message packets. Denote an encoded packet by

$$I_j^{\prime }={\displaystyle \sum _{i=1}^k}{c}_{ji}{I}_i,$$

where $c_{ji}$ are random coefficients picked from some field $\mathbb{F}$, and $\overline{c_j}=(c_{j1},c_{j2},\dots ,c_{jk})$ is called the code vector of the encoded packet $I_j^{\prime }$. The code vector describes how to generate the encoded packet from the message packets. It needs to be sent along with the encoded packet as side information in its header. If the message packets are sufficiently large, the overhead to contain the code vectors is negligible.

The sender proceeds to generate and send randomly encoded packets until the receiver node has successfully decoded all of the message packets. It has been proven in [20] that, when coding is performed in a very large field $\mathbb{F}$, for a group of k message packets, the probability that a receiver can decode the k message packets upon successful reception of k encoded packets is close to 1. With this condition, it makes sense to compare the bulk service described above with a $Geo/Geo/1$ queuing system, since for both queuing systems transmission of k message packets will be completed when the channel has successfully delivered k packets.

To facilitate analysis, as in [14,18,21,22], we assume that RLC is performed over a sufficiently large field size, so that the expected number of successfully received packets at the receiver, to decode the original k data packets, is k. Thus, when the receiver node has successfully collected k linearly independent encoded packets $\{I_1^{\prime },\dots ,I_k^{\prime }\}$, all of the message packets $\{I_1,\dots ,I_k\}$ can be decoded using simple matrix inversion:

$$\left(\begin{array}{c}{I}_1\\ ⋮\\ I_k\end{array}\right)={\left(\begin{array}{ccc}{c}_{11}\hfill & \dots & \hfill c_{1k}\\ ⋮\hfill & \ddots & \\ c_{k1}\hfill & \dots & \hfill c_{kk}\end{array}\right)}^{-1}\left(\begin{array}{c}{I}_1^{\prime }\\ ⋮\\ I_k^{\prime }\end{array}\right),$$

where $I_i$ is a message packet, and $I_i^{\prime }$ is a linearly independent encoded packet whose code vector is $\overline{c_i}=(c_{i1},c_{i2},\dots ,c_{ik})$. As soon as the receiver node decodes the group of message packets, it sends an acknowledgment to the sender to allow it to move to the next group of packets. After receiving the acknowledgment confirming the successful delivery, the sender processes the next group of packets. Note that, in the unicast scenario considered in this paper, transmission of a group of encoded packets is completed as soon as the user successfully decodes the group of encoded packet. Conversely, in a broadcasting model where a sender broadcasts the encoded packets to a set of receivers, transmission of a group of encoded packets completes until all receivers successfully decode the group of encoded packets.

4. User Utility

The encoding and transmission are viewed as a service, for which a user needs to pay a certain price. According to [23], the user will decide to use the service as long as its net utility (utility minus waiting cost) minus the price charged by the sender, which is called compensated utility, is positive. Denote the utility that the user will derive from receiving a packet from the sender by U, and the sender charges a price p per packet. Then, the corresponding compensated utility, $\mathbb{U}$, is given by:

$$\mathbb{U}=U-p-\beta D$$

(1)

where D is the expected delay experienced by each packet, and $\beta$ is a constant converting delay from time units into money units. The parameter $\beta$ reflects the delay sensitivity of the user or the user’s application: the higher the value of $\beta$, the more sensitive the user’s application to delay. For example, multimedia services with stringent delay requirements will have high values of $\beta$. Thus, $\beta D$ can be viewed as a waiting cost of a service that spends a delay D and the parameter $\beta$ can be interpreted as a waiting cost per unit time.

A user will use the service if and only if $\mathbb{U}>0$. Thus, the effective arrival rate $\lambda$ is given by

$$\begin{array}{cc}\hfill \lambda & =\Lambda \mathbb{P}(\mathbb{U}>0)\hfill \\ & =\Lambda \mathbb{P}(U-p-\beta D>0)\hfill \\ & =\Lambda {\int }_{U>p-\beta D}f\left(u\right)du,\hfill \end{array}$$

(2)

where $\Lambda$ is a potential arrival rate without considering the price charged by the sender and $f\left(u\right)$ is the probability density function of U. Users are heterogeneous in terms of their valuations on the service. We assume that user valuations are upper bounded by $\alpha$. To reflect the range of valuations in the population of users in a simple manner to allow for analytical tractability, as suggested in [24,25], each user is characterized by a valuation that is an independent random variable uniformly distributed over the interval $[0,\alpha ]$. This assumption corresponds to the commonly used assumption in the literature [26,27,28] where users are characterized by user types that are uniformly distributed on the interval $[0,1]$. Thus, Equation (2) can be simplified to

$$\frac{1}{\alpha }(\alpha -p-\beta D)=\frac{\lambda }{\Lambda }.$$

(3)

With the condition that, when k message packets are being encoded over a sufficiently large field with RLC and transmitted, the receiver node can recover all of the k message packets after successfully receiving k encoded packets, Ravanbakhsh et al. [13] proposed a method to analyze the delay D for each packet by comparing the processing of the bulk service directly with a $Geo/Geo/1$ queuing system. The $Geo/Geo/1$ queuing model, which has been analyzed in [29], is used to model the basic retransmission scheme in [12,13]. For the basic retransmission scheme, the average waiting time $W_{RE}$ and the mean packet delay $D_{RE}$ are given by

$$\left\{\begin{array}{c}{W}_{RE}=\frac{\lambda (1-\mu )}{\mu (\mu -\lambda )},\hfill \\ D_{RE}=\frac{1}{\mu }+W_{RE}=\frac{1-\lambda }{\mu -\lambda }.\hfill \end{array}\right.$$

(4)

Note that Equation (4) holds provided that $\mu >\lambda$.

According to the analysis in [13], for a bulk of encoded packets $I_i^{\prime },I_2^{\prime },\cdots ,I_k^{\prime }$, a fictitious waiting time for each packet in the bulk is equal to the waiting time that a packet would experience in a $Geo/Geo/1$ queuing system, and the modified service time for each packet $I_j^{\prime }$ is $(k-j+1)/\mu$. Thus, for k message packets, the mean packet delay is given by [13]

$$D_{I_j^{\prime }}=W_{RE}+\frac{1}{k}\frac{{\sum }_{i=1}^{k}i}{\mu }=\frac{\lambda (1-\mu )}{\mu (\mu -\lambda )}+\frac{k+1}{2\mu }.$$

In this paper, we use the same method to analyze the queuing system model described in Section 3. Then, with RLC, the expected delay experienced by each packet is given by

$$D_{RLC}=\frac{\lambda (1-\mu )}{\mu (\mu -\lambda )}+\frac{{\sum }_{k=1}^{\infty }{B}_k(k+1)}{2\mu },$$

(5)

where $B_k$ is the probability that the bulk is of length k.

Here, Equation (5) can be written as

$$\begin{array}{cc}\hfill D_{RLC}& =\frac{\lambda (1-\mu )}{\mu (\mu -\lambda )}+\frac{{\sum }_{k=1}^{\infty }{B}_{k}k+{\sum }_{k=1}^{\infty }{B}_k}{2\mu }\hfill \\ & =\frac{\lambda (1-\mu )}{\mu (\mu -\lambda )}+\frac{{\sum }_{k=1}^{\infty }{B}_{k}k+1}{2\mu },\hfill \end{array}$$

(6)

where ${\sum }_{k=1}^{\infty }{B}_{k}k$ is the expected number of packets in the queue immediately after the previous bulk has been successfully delivered. Denote ${\sum }_{k=1}^{\infty }{B}_{k}k$ by $\overline{S}$. Note that $\overline{S}$ may not be the same as the average number in the system at an arbitrary point in time. To facilitate analysis, we use $\overline{S}$ as an approximation to the average number in the system at an arbitrary point in time. According to Little’s law,

$$\overline{S}=\lambda D.$$

Multiplying by $\lambda$ on both sides of Equation (6) and substituting $\lambda D$ and ${\sum }_{k=1}^{\infty }{B}_{k}k$ with $\overline{S}$, we obtain

$$\overline{S}=\lambda [\frac{\lambda (1-\mu )}{\mu (\mu -\lambda )}+\frac{\overline{S}+1}{2\mu }].$$

(7)

Thus,

$$\overline{S}=\frac{\lambda (\lambda -2\lambda \mu +\mu )}{(\mu -\lambda )(2\mu -\lambda )},$$

which implies that

$$D_{RLC}=\frac{\lambda -2\lambda \mu +\mu }{(\mu -\lambda )(2\mu -\lambda )}.$$

(8)

Note that Equation (8) holds provided that $\mu >\lambda$.

5. Revenue Optimization

The revenue generated by the sender per unit time is given by $\mathsf{\Pi }=p\lambda$. We evaluate the economic impact of RLC by comparing it with the basic retransmission scheme. Thus, the sender’s revenue maximization problem can be written as

$$\begin{array}{}\left(9\mathrm{a}\right)& \mathrm{Maximize}:\hfill & p\lambda \hfill \left(9\mathrm{b}\right)& \mathrm{Subject}\mathrm{to}:\hfill & \frac{1}{\alpha }(\alpha -p-\beta D)=\frac{\lambda }{\Lambda };\hfill \left(9\mathrm{c}\right)& & \lambda <\mu ,\hfill \end{array}$$

where

$$\begin{array}{cc}{D}_{RLC}=\frac{\lambda -2\lambda \mu +\mu }{(\mu -\lambda )(2\mu -\lambda )},\hfill & \mathrm{for}\mathrm{RLC};\hfill \\ D_{RE}=\frac{1-\lambda }{\mu -\lambda },\hfill & \mathrm{for}\mathrm{basic}\mathrm{retransmission}.\hfill \end{array}$$

Rearranging Equation (9b) yields

$$p=\alpha -\beta D-\frac{\alpha \lambda }{\Lambda }.$$

(10)

Substituting Equation (10) into Equation (9a), we rewrite the sender’s revenue as

$$\mathsf{\Pi }=\alpha \lambda -\beta \lambda D-\frac{\alpha {\lambda }^2}{\Lambda }.$$

(11)

Differentiating the revenue function in Equation (11) with respect to $\lambda$, we obtain

$$\frac{\partial \mathsf{\Pi }}{\partial \lambda }=\alpha -\beta D-\beta \lambda D^{\prime }-\frac{2\alpha }{\Lambda }\lambda .$$

(12)

where

$$\begin{array}{c}{D}_{RLC}^{\prime }=\frac{5{\mu }^2-4{\mu }^3-{\lambda }^2+2\mu {\lambda }^2-2\mu \lambda }{{(\mu -\lambda )}^2{(2\mu -\lambda )}^2},\mathrm{for}\mathrm{RLC};\hfill \\ D_{RE}^{\prime }=\frac{1-\mu }{{(\mu -\lambda )}^2},\mathrm{for}\mathrm{basic}\mathrm{retransmission}.\hfill \end{array}$$

Equating $\frac{\partial \mathsf{\Pi }}{\partial \lambda }$ to 0, expressions for the optimal arrival rates for RLC and basic retransmission, ${\lambda }_{op{t}_{RLC}}$ and ${\lambda }_{op{t}_{RE}}$, are given, respectively, by

$$1-\frac{2}{\Lambda }{\lambda }_{op{t}_{RLC}}-\frac{\beta }{\alpha }{D}_{op{t}_{RLC}}-\frac{\beta }{\alpha }{\lambda }_{op{t}_{RLC}}{D}_{op{t}_{RLC}}^{\prime }=0,$$

(13)

where

$$\begin{array}{c}{D}_{op{t}_{RLC}}=\frac{{\lambda }_{op{t}_{RLC}}-2{\lambda }_{op{t}_{RLC}}\mu +\mu }{(\mu -{\lambda }_{op{t}_{RLC}})(2\mu -{\lambda }_{op{t}_{RLC}})};\hfill \\ D_{op{t}_{RLC}}^{\prime }=\frac{5{\mu }^2-4{\mu }^3-{\lambda }_{op{t}_{RLC}}^2+2\mu {\lambda }_{op{t}_{RLC}}^2-2\mu {\lambda }_{op{t}_{RLC}}}{{(\mu -{\lambda }_{op{t}_{RLC}})}^2{(2\mu -{\lambda }_{op{t}_{RLC}})}^2},\hfill \end{array}$$

and

$$1-\frac{2}{\Lambda }{\lambda }_{op{t}_{RE}}-\frac{\beta }{\alpha }{D}_{op{t}_{RE}}-\frac{\beta }{\alpha }{\lambda }_{op{t}_{RE}}{D}_{op{t}_{RE}}^{\prime }=0,$$

(14)

where

$$\begin{array}{c}{D}_{op{t}_{RE}}=\frac{1-{\lambda }_{op{t}_{RE}}}{\mu -{\lambda }_{op{t}_{RE}}};\hfill \\ D_{op{t}_{RE}}^{\prime }=\frac{1-\mu }{{(\mu -{\lambda }_{op{t}_{RE}})}^2}.\hfill \end{array}$$

Note that Equations (13) and (14) hold provided that $\mu >{\lambda }_{op{t}_{RE}}$ and $\mu >{\lambda }_{op{t}_{RE}}$, respectively. The solutions to Equations (13) and (14), ${\lambda }_{op{t}_{RLC}}$ and ${\lambda }_{op{t}_{RE}}$, can be used as the optimal admission rates for the sender when it chooses to use RLC or the basic transmission scheme, respectively.

Subsequently, according to Equation (9b), the corresponding optimal prices $p_{op{t}_{RLC}}$ and $p_{op{t}_{RE}}$ are given, respectively, by:

$$p_{op{t}_{RLC}}=\alpha -\beta D_{op{t}_{RLC}}-\frac{\alpha {\lambda }_{op{t}_{RLC}}}{\Lambda },$$

(15)

and

$$p_{op{t}_{RE}}=\alpha -\beta D_{op{t}_{RE}}-\frac{\alpha {\lambda }_{op{t}_{RE}}}{\Lambda }.$$

(16)

For both cases, with the optimal admission rates and the corresponding optimal prices, the resulting sender’s revenues, which are given, respectively, by

$${\pi }_{op{t}_{RLC}}=p_{op{t}_{RLC}}{\lambda }_{op{t}_{RLC}}$$

(17)

and

$${\pi }_{op{t}_{RE}}=p_{op{t}_{RE}}{\lambda }_{op{t}_{RE}}$$

(18)

are maximized.

However, Equations (13) and (14) are difficult to solve mathematically. We study the impact of RLC in terms of the optimal admission rate ${\lambda }_{opt}$, the optimal price $p_{op{t}_{RLC}}$, the expected delay $D_{RLC}$ and the optimal revenue ${\mathsf{\Pi }}_{opt}$, through the following numerical examples.

6. Numerical Examples

Assume $\Lambda =1$ and $\alpha =5$ as listed in

Table 1. Simulation setting.

Parameter	Description	Value
$\Lambda$	Potential Arrival Rate	1
$\alpha$	Maximum User Utility	5
$\beta$	Waiting Cost Per Unit Time	0.2, 1, 3

. With the assumption $\Lambda =1$, we focus our attention on a high-traffic load service model to investigate the behavior of the admission rate under the impact of RLC. For ease of illustration, Figure 2, Figure 3, Figure 4 and Figure 5 plot the optimal admission rate, the corresponding mean packet delay under the optimal admission rate, the optimal price and the corresponding optimal revenue for RLC and the basic retransmission scheme as a function of $\mu$ with $\beta =0.2$, $\beta =1$ and $\beta =3$, respectively.

The following can be observed:

• In Figure 2, for both RLC and the the basic retransmission scheme, the optimal admission rate is proportional to the reception probability. The reason is that, the lower the reception probability, the longer the service time per packet, which results in a lower admission rate needed to avoid potential congestion. In addition, considering the pricing method involved as an admission control mechanism, both schemes allow lower admission rates when the user is more delay-sensitive. In addition, the optimal admission with the basic retransmission scheme is slightly higher when the user is more tolerant to delay (e.g., $\beta =0.2$), whereas RLC allows a higher optimal admission rate when the user is more delay-sensitive (e.g., $\beta =3$).
• In Figure 3, the corresponding mean packet delay with RLC is lower than that of the basic retransmission scheme, under their respective optimal admission rates. This can be explained as follows: when comparing $D_{RLC}$ with $D_{RE}$, it can be found that, if ${(1-\lambda )}^2\le 1-\mu$, we have $D_{RLC}\le D_{RE}$. For an arbitrary reception probability in the feasible range, the optimal admission rate with RLC, ${\lambda }_{op{t}_{RLC}}$, and that for the basic retransmission scheme, ${\lambda }_{op{t}_{RE}}$, clearly satisfy the condition ${(1-\lambda )}^2\le 1-\mu$. It can also be seen that, both RLC and the basic retransmission scheme enable lower expected mean packet delays when the user is more delay-sensitive due to the effect of optimal pricing on the delay-sensitive user. This result can be explained as follows: when the user is more delay sensitive, i.e., the waiting cost per unit time $\beta$ is higher, which in turn could lead to a higher waiting cost $\beta D$, accordingly, a lower delay D is resulted from a lower admission rate (as shown in Figure 2) induced by a higher price (as shown in Figure 4) to balance the waiting cost in such a way that the compensated utility $\mathbb{U}>0$ is guaranteed according to Equation (3).
• In Figure 4, for both cases, the optimal price is an increasing function of the reception probability. It is intuitive that the queuing delay is decreasing with the increase of the reception probability, as illustrated in Figure 3. According to Equation (1), as the queuing delay decreases, the sender can increase the price while guaranteeing the compensated utility $\mathbb{U}>0$. In addition, since $D_{RLC}\le D_{RE}$, under the respective optimal admission rates of both cases, $p_{RLC}$ can be higher than $p_{RE}$ while guaranteeing the compensated utility $\mathbb{U}>0$. Furthermore, for both cases, the optimal price reduces as a result of increased waiting cost $\beta D$ when the user is more delay-sensitive.
• In Figure 5, for both cases, the optimal revenue, which is the product of the corresponding optimal admission rate and optimal price, increases as the reception probability increases in a quasi-linear fashion. As expected, the optimal revenue with RLC is higher than that for the basic retransmission scheme under their respective optimal admission rates.

7. Conclusions

We have investigated a transmission scheme with RLC involved from a pricing viewpoint in a unicast setting, in which the message packets demanded arriving at the sender according to a random arrival pattern, are encoded and then transmitted to a single destination, taking user’s delay-sensitivity into consideration. It is shown that the optimal admission rate, the optimal price and the corresponding optimal revenue depend on the quality of the transmission channel. The optimal revenue is a monotonically increasing function of the reception probability. In comparison with the basic retransmission scheme, it is observed that RLC offers better performance in terms of both mean packet delay and revenue. In addition, compared to the basic retransmission scheme, RLC allows a higher admission rate when the user is more delay-sensitive.

In this paper, to facilitate the analysis, we assume a sufficiently large field size so that any k vectors of coding coefficients are linearly independent with a high probability, i.e., the expected number of successfully received packets to decode the original k packets is k. While the assumption not only significantly simplifies the analysis but also leads to better delay performance, the field size is limited in practice due to the encoding and decoding complexity. However, smaller finite field sizes result in a non-negligible probability that the vectors of coding coefficients collected by a user are linearly dependent, even if their number is larger than k, leading to a lower probability of successful decoding. As a result, with a finite field size, decoding probability should be derived and integrated into the delay analysis. This would be an extension for future work.

Note that the unicast setting discussed in this paper is a general model in which we only assume a lossy channel with certain reception probability. Exploiting the properties of networks (i.e., wireless mesh networks) and taking advantage of them when applying RLC may result in an improved delay performance. Therefore, to analyze a more complicated and realistic system model, for instance, an opportunistic wireless network with RLC, would be another interesting extension.