We study the relation between the stable throughput regions and the capacity regions for a Gaussian multiple-access channel. Our main focus is to study how the extent of side information about source arrival statistics and/or instantaneous queue states at each transmitter influence the achievable stable throughput region. Two notions of MAC capacity are studied. The first notion is the conventional Shannon capacity which relies on large coding block lengths for finiteSNR, while the second uses finite code blocks with highSNR. We find that the stable throughput region coincides with the Shannon capacity region for many scenarios of side information, where side information is defined as a mix of statistical description and instantaneous queue states. However, a lack of sufficient side information about arrival statistics can lead to a significant reduction in the stable throughput region. Finally, our results lend strong support to centralized architectures implementing some form of congestion/rate control to achieve Shannon capacity, primarily to counter lack of detailed information about source statistics at the mobile nodes.

Often in communication networks, the traffic distribution is unknown. However, in bounding the performance of a network, it is commonly assumed [1-5] that the transmitters and the receivers have complete knowledge of the source arrival distribution (or the probability distribution of the number of packets arriving per unit time), which is then used in the design of optimal transmission methods. In this paper, we study the impact of such side information regarding the traffic on the stability performance of Gaussian multiple- access channels.

We will focus our attention on a slotted Gaussian multiple-access channel withK users sending bursty data to a single receiver. In capacity analysis, it is implicitly assumed that the users are aware of all the transmission rates (of every user) and have optimal codebooks, which allows the whole system to operate close to the boundary of the capacity region; this can be understood as all nodes having complete statistical knowledge regarding all sources. In this work, we will take the first step towards understanding exactly how much information is needed at each node about theother sources. We will study this through a series of five cases with different amount of statistical information at each node. Furthermore, we will adopt a more general source model, unlike prior work [3,4], in which data arrives randomly at a user with general distribution in each symbol duration. This arrival process decouples the definition of source arrivals from that of communication system design, which will occur in blocks of lengthn codewords.

In the first of the five cases, the transmitters and the receiver will be assumed to know the arrival distribution of all the sources, which represents the case of complete statistical information. We show that in this case the stable throughput region coincides with the Shannon capacity region. A similar result was shown in [3] for two-user multiple-access system, by requiring not only complete distributional knowledge but also one bit of instantaneous queue state information. Our encoding strategy holds for a generalK-user systemand requires no instantaneous state information to achieve every point in the Shannon capacity region. Keeping our objective in mind, we reduce the amount of side information in the second case from full statistical knowledge to only the knowledge of the mean arrival rates of every node. Since the probability of a certain input bit pattern depends on the length of the bit pattern, the coding techniques which assume equally likely bit arrival for every input bit pattern are not optimal. As a result, it appears that the knowledge of mean arrival rates alone is insufficient to guarantee achieving every point in the Shannon capacity region (optimal operation will potentially require a multiuser universal source coder and since we are transmitting over a noisy channel, we will also need multiuser source/channel separation. Thus, the chances that full Shannon capacity region is achievable with only information about mean arrival rates appear slim). However,we show that if each node sends quantized one- bit information about its own queue state to the receiver every time-slot, then the entire Shannon capacity region can be achieved with reduced statistical information. Again, in contrast to the main result in [3], we show that limited statistical information suffices if one bit of instantaneous system state information is available.

In contrast to the above cases, we consider a case where the sources are not aware of the mean arrival rates of other nodes. In this case, the stability region is significantly reduced compared to Shannon capacity region, even with one bit of quantized state information every time-slot. The significant loss can be attributed to the fact that each node has to essentially assume that other nodes potentially have highest possible load, thuspredividing the total available capacity intoK equal portions. This division is inefficient in the cases where some of the nodes have lower-than-maximum arrival rates. Thus the stable throughput region of actual systems may be significantly lower than the Shannon capacity region due to lack of knowledge of source arrival distribution, thereby underscoring the importance of side information.

We next show that this loss can be completely recovered if the receiver has either full statistical knowledge (like in first case above) or knows the mean arrivals of all nodes along with one-bit instantaneous queue state information, and the receiver can send feedback to each node once during system operation. This one-time feedback is akin to congestion/rate control [6,7], where the receiver informs each node of their allowable rate at the beginning of the communication. In this case, the stable throughput region coincides with the Shannon capacity region. This scenario is akin to the congestion control via feedback from the base station. Hence, compared to the first scenario, we traded the knowledge of complete arrival distribution of other sources at a source with a feedback from the receiver.

For each case of side information, we consider two notions of Shannon capacity. The first is the conventional notion of capacity, which is defined for a fixed value ofSNR with growing encoding block length [5]. In this notion, the problem of understanding delay in an information- theoretic setting remains intractable, sincen → ∞ makes all talk of per-bit delay irrelevant. A bit, even if it is in the queue for finite number of time-slots, will have infinitely large delay since time-slot is infinite. Hence, we explore an alternate asymptote, partially inspired by age-old diversity order analysis, where we study finite block lengths in a high-SNR regime. In this regime, we no longer work with the exact capacity region, but with the rates of growth. However, asSNR increases, the capacity increases in an unbounded fashion. So for, any meaningful discussion about stability regions, the sources have to produce data at rates which scale with theSNR. This leads us to reconsider the definition of stability. Note that this is not an uncommon assumption, and is implicitly assumed in asymptotic inSNR frameworks like diversity-multiplexing studies [8,9]. We formalize these new notions of capacity and stable throughput region and show that conceptually similar results hold for the finite block length case. While conceptually the results are similar in two notions of the capacity, they differ in the details of their proofs.

We quickly note that the problem of not knowing statistics of other nodes can be understood as a multiuser universal source-coding problem, where the distributed sources are not aware of the full joint distribution. In this case, the transmitters will encode assuming incomplete system knowledge and the receiver will decode assuming similarly reduced information about the system. Such a general formulation will form the obvious next step following our current work, and will be a topic of discussion elsewhere.

The relation between queuing stability and Shannon capacity remains a problem of interest, since most sources are bursty and require a delay-bounded delivery. For random access systems, the problem has been studied extensively (e.g., see [1,4,10-13]). A key result in [2,4] is that the queuing stability region coincides with the Shannon capacity region in many cases on the collision channel, illustrating that the bursty nature of the arriving packets does not limit the data rate at which the probability of error can be made arbitrarily small. The entire body of work on collision channels assumes that the arrival distributions are known to all the users, and also that the receiver knows if a particular user is sending the data in order to decide collisions. Also, the transmitting users have some side information, by which they know if a collision has occurred and, hence, decide to retransmit. Similar information is needed for random-access systems with multipacket reception capability in order to decide retransmissions.

Following the work on the collision channel, the effect of scheduling and power control on the stability in multiuser channels under Poisson arrivals was studied in [7,14-16]. The stability of the queues in wired switches has been studied for general arrivals [17,18] for certain scheduling algorithms. While numerous works characterize stability conditions, stability policies and stable-system behavior, we concentrate on the influence of side information on the stable throughput region.

The relation between queuing stability and Shannon capacity for multiple-access systems over AWGN channels has been studied earlier in [3,7,14,15,19].Most of this work [7,14,15,19] assumes complete knowledge of the queue states. In [3], with the assumptions of time slots being large, and a maximum of one packet of fixed length arriving at each user in a time slot for a system with two users, it was shown that the stable throughput region was independent of the burstiness and the shared queue information. The model assumed a fixed form of side information rather than the tradeoff of side information with stable throughput regions that is addressed in this paper.

We begin in Section 2 by describing the channel model and the capacity regions. In Section 3, we assume finiteSNR with large time-slots. Various achievable stable throughput regions are described depending on the amount of side information. In Section 4, we consider the dual problem of finite time-slots with largeSNR, where the influence of the amount of side information on the achievable stable throughput region is studied.

2.1. Channel and source model

We consider a multiple-access system, as the illustrated in Figure 1, whereK users transmit to a single receiver. We will assume a time-slotted system where the transmissions only occur at the slot boundaries. Each slot is indexed byk and within each slot, then symbols will be indexed byj.

Gaussian multiple-access channel with random arrivals.

Full size image

The received signal at time unitj is the sum of the transmissions of the users and Gaussian noise at time unitj,

whereZ[j] is zero mean i.i.d. Gaussian noise with varianceN, and is independent of channel inputsX_i[j] ϵℝ,i = 1,2,…,K ((X_i[1],…,X_i[n]) represents the n-length codeword sent in a time-slot). The channel output isY[j] ϵℝ. The transmit power of useri averaged over all the codewords isP_i if it is transmitting and 0 otherwise. Thus, no power control is performed. We also assume that receiver has the perfect timing information to ensure the synchronization at the receiver. Finally defineSNR = (SNRU₁,SNR₂,…,SNR_K), whereSNR_j = P_i/N, is the signal-to-noise ratio for useri (SNR_i is the ratio of the average signal power ofith user to the noise variance, and does not include interference from other users).

While the transmissions occur only at the slot boundaries, the data can arrive anytime during the slot. Data arrives for useri in form of bits with an average rate ofλ_i bits per unit time (one time unit represents one symbol duration). So the arrival process is defined independent of the slot boundaries or the slot length and directly on the smallest time unit, the symbol time-duration. We define Δ_i(k) to be the number of bits that arrive for transmission at useri in time-slotk,E[Δ_i(k)] = nλ_i. Thus, unlike the previous works [1,2,4], we do not assume that the arrivals occur only at the start or the end of the time-slot, which makes the definition of arrival process independent of the communication-system design, notably the slot lengthn.

We denote the number of bits departing from the queue of useri in time slotk as Ω_i(k). Further, we denote the number of bits in theith queue at the beginning of time-slotk as Q_i(k). The queue is updated as

withQ_i(1) = 0. We assume that the number of elements in the queue ofith user (or the queue state) is known only toith user. The stable throughput region is the region where the queues do not grow unbounded in the steady state. The mathematical definitions for these stability regions for large time slots and largeSNRs are defined in Section 2.3.

2.2. Capacity regions

In this section, we define the two notions of capacity. First is the conventional definition where theSNR is held fixed and the blocklength is allowed to grow unbounded. And in the second case, blocklength is held fixed andSNR is increased unbounded. To contrast the two definitions, we state the preliminaries for conventional definition of capacity.

A$\left(\left(2^{n{R}_1},2^{n{R}_2},\dots ,2^{n{R}_K}\right),n\right)$ code for multiple-access channel consists ofK encoding functionsf_i : $\mathbb{W}$_i → Wⁿ_i where Wd_i is the input to the encoder at useri and takes$2^{n{R}_K}$ values, and a decoding function g :g : $\mathbb{R}$ⁿ → $\mathbb{W}$₁ × $\mathbb{W}$₂ × ⋯ × $\mathbb{W}$_k, where$\mathbb{X}$ⁿ_i ⊆ Rⁿ

Definition 1. A rate tuple (R₁,R₂,…,R_K) is achievable if there exists a sequence of$\left(\left(2^{n{R}_1},2^{n{R}_2},\dots 2^{n{R}_K}\right),n\right)$ codeswith error probabilityP_e → 0 as n → ∞. The capacity region is the closure of all achievable rate tuples (R₁,R₂,…,R_K).

Lemma 1 (see [5]).The capacity region of Gaussian multiple- access channel is given by closure of convex hull of all (R₁,R₂,…,R_k) satisfying

where S is any subset of {1,2, …K},and C(x) = (1/2)log (1 + x)

The classical definition of capacity requires the block lengthn to approach infinity. In contrast, we will define the SNR-capacity region for a fixed blocklengthn but with increasingSNR. Our motivation stems from our aim to analytically understand the role of delay in communication. Towards that end, the high-SNR regime allows keeping delay in check and is useful for high-data-rate systems. Part of our motivation for choosing high-SNR regime comes from diversity-multiplexing tradeoff [8,9], which has proven useful in fading channels.

To maintain differentiation in the quality of user channels, we will model the growth ofSNR on different transmitter-receiver links with different exponents. Let$SN{R}_i\doteq u^{{\alpha }_i}$ for some fixedα_i greater than zero (we adopt the notation of [8]to denote≐,$\stackrel{\text{.}}{\le }$ and$\stackrel{\text{.}}{\ge }$ to represent exponential equality and inequalities) for some baseSNR denoted byu (In other words,α_i ≜ lim u → ∞ (log(SNR_i)/log(u))) (u can be chosen to be any baseSNR, e.g., max(SNR_i) or min(SNR_i) or an average). For our asymptotic analysis, we take the rates to vary asRi≐r_i, log(SNR_i). Thus,R,≐r_i, log(SNR_i)≐r_iα_ilog(u)

Definition 2. A rate tuple (r₁,r₂,…,r_K) is SNR-achievable if there exists a sequence of$\left(\left(2^{n{r}_{1}log\left(SN{R}_1\right)},2^{n{r}_{2}log\left(SN{R}_2\right)},\dots 2^{n{r}_{K}log\left(SN{R}_K\right)}\right),n\right)$ codes with error probabilityP_e → 0 asu — to (equivalently,$SN{R}_i\doteq u^{{\alpha }_i}\to \infty$). TheSNR- capacity region is the closure of allSNR-achievable rate tuples (r₁,r₂,…,r_K).

The next result proves theSNR-capacity region; and Figure 2 shows an example capacity-region whenα₁ > α₂.

SNR capacity region for the case where α₁ > α₂.

Full size image

Lemma 2.The SNR-capacity region of Gaussian multiple- access channel is given by closure of all (r₁,r₂,…,r_K)satisfying

where S is any subset of {1,2,…K},where α_iis defined as above.

Proof. The achievability proof can be given on similar lines as in [9]. Consider the ensemble of i.i.d. random codes. Specifically, each user generates a codebookℂ⁽ⁱ⁾ containing$2^{n{R}_i}\doteq SN{R}_i^{r_{i}n}$ codewords denoted as${\mathrm{X}}_1^{\left(i\right)},\dots ,{\mathrm{X}}_{SN{R}_i^{r_{i}n}}^{\left(i\right)}$. Each codeword isn-length vector with i.i.d. Gaussian entries with zero mean and unit variance. Once picked, the codebooks are revealed to the receiver. In each block period, transmitted signal of useri is chosen fromℂ⁽ⁱ⁾.

Consider detection error probability of joint maximum- likelihood receiver. We first define for each nonempty setS ⊆ {1, 2, … K} an error event

where${\widehat{m}}_i$ is the decoded message of useri whilem_i is the actual message. Thusε^S is the event that receiver makes wrong decisions of all users in setS and makes correct for the rest. Clearly, we have the probability of errorP_e(u) as

Without loss of generality, we assumeS = {1, 2,…, |S|}. Let X0 = (X⁽¹⁾₀, …, X^(K)₀) be the transmitted signal where X⁽ⁱ⁾₀∈ℂ⁽ⁱ⁾ is the codeword transmitted by user i. Denote by X₁ another codeword that differs from X₀ on the symbols transmitted by all users in S but coincide on those by other users, that is, X₁ = (X⁽¹⁾₁, … X^(|S|)₁, X^{(|S| + 1)}₀, … X^(K)₀).

The error eventε^S occurs if the receiver makes a wrong decision in favor of any such X₁. This happens when

Note that (7) is similar to (27) in [9] with$H=\left[\sqrt{SN{R}_1},\sqrt{SN{R}_2},\dots ,\sqrt{SN{R}_{\left|S\right|}}\right]$ and number of transmit and receive antennas as unity. Hence by comments following (27) in [9], we consider this as a single-user error probability with overall rate ∑_i ∈ SR_i, |S| transmit antennas and 1 receive antenna.

Following [8], we use pairwise error probability (PEP) to bound average probability of error. Recall thatX₀ andX₁ differ in setS ⊆ {1, 2, …, K}. Construct a matrix ΔX of size |S| × n containingX₀ –X₁ at all |S| users.This reflects the difference in transmit matrices for|S| transmit antennas.

Since ΔX is isotropic, ||HΔX||² has same distribution asev(HH^†)||Δx||² whereev(HH^†) is defined as the eigen-value ofHH^† and equals${\displaystyle {\sum }_{i\in S}SN{R}_i\doteq u^{{max}_{i\in S}{\alpha }_i}}$, and Δx any row vector of ΔX. Hence,

As the number of possible choices ofX₁ is${\displaystyle {\prod }_{i\in S}}\left(SN{R}_i^{n{r}_i}-1\right)$, the overall error probability

Hence, the error probability goes to zero whenΣ_i ∈ Sr_iα_i − (1/2 max_i ∈ Sα_i < 0 for allS which is true by the statement of the theorem.

For the converse, letΣ_i ∈ Sr_iα_i > (1/2)max_i ∈ Sα_i for some S. Again, assume thatS = {1,2,…, |S|} without loss of generality. The probability of error can be bounded by Fano’s inequality as

whereR = Σ_iϵSR_i. SinceI(Xⁿ₁, Xⁿ_2, …, Xⁿ_|S|; Yⁿ|Xⁿ_|S| + 1, … Xⁿ_K) = (n/2)log(1 + Σ_i ∈ SP_i/N) we get

This shows that the error probability cannot be brought arbitrarily close to zero in the limit of highSNR whenΣ_i ∈ Sr_iα_i > (1/2)max_i ∈ Sα_i for anyS, thus proving the converse.□

We will sometimes use the terminterior of the capacity region orinterior of SNR-capacity region to imply that the vector is not on the boundary, but inside the region.

2.3. Stable throughput region

In the case of finiteSNR, stable throughput region is the region formed by the closure of vectors of mean arrival rates at the different queues for which there exists a transmission scheme in which the queues are stable. In our discussion, stability of queues implies that the ratio of queue length to block length is finite with probability one for large block-lengths. The above definition of stability of queues corresponds to a “time-observed” version of the stability definition used in standard practice [12,20,21], according to which the queue length is finite with probability one. There are some other weaker notions of stability in literature like substability [12,17,20,21] which also hold when the queues satisfy stability. Formally, we will use the following definition of the stable throughput region

Definition 3 (Stable throughput (largen and finiteSNR)). The stable throughput region in the case whenn → ∞ is defined as the closure of all (λ₁, λ₂,…, λ_K), such that, there exists a transmission scheme, such that, the signal received at destination has probability of errorP_e → 0 asn → ∞. Furthermore, there exists an integerM such that all the queues are stable forn > M .In other words, there exists an integerM such that lim_j→∞ Pr[Q_i(j) < nx] = F(x,n) and lim_x→∞F(x,n) = 1, fori = 1,2,…,K andn > M, when the arrival rates at useri isλ_i.

When theSNR is large, large amount of data can be serviced in a time-slot even if the time-slot is not large. Hence, the stability of the queue is defined by normalizing with the order of amount of information that can be serviced in each block-length which is of the order of log(u) as mentioned in Section 2.2. As we can serve such large rates, the incoming rates which are of lower order than log(u) can definitely be served; hence we assume that the incoming arrival rates are also of the order of log(u) (i.e.,λ_i ≐ l_i log(SNR_i) ≐ l_iα_i log(u)). Hence, stable throughput region in this case is the region formed by the closure of vectors of normalized mean arrival rates at the different queues for which there exists a transmission scheme in which the queues are stable. In our discussion, stability of queues implies that the ratio of queue length to log(u) is finite with probability one for largeSNR (oru). Hence, the stable throughput region in this case is defined as follows.

Definition 4 (SNR-stable throughput (finiten and largeSNR)). The SNR-stable throughput region in the case whenSNR → ∞ is defined as the closure of all (l₁,l₂,…,l_K) such that there exists a transmission scheme such that the signal received at destination has probability of errorP_e → 0 asu → ∞. Furthermore, all the queues are stable foru large enough. In other words, there existsM < ∞ such that lim_{j → ∞} Pr[Q_i,(j) < xlog(u)] = F(x,u) and lim_x→∞F(x,u) = 1, fori = 1,2,…,K andu > M, when the arrival rate at useri isλ_i ≐ l_iα_i log(u).

Asu → ∞, the region is defined as the closure of (l₁,l₂,…,l_K) which is a finite region although λi, go to to. Let us sayl_i as the arrival rate perSNR-unit which we use in defining the stable throughput region for largeSNR in contrast toλ_i, which is the arrival rate per unit time and is used to define stable throughput region for largen. The stability of the queues refer to the queue length per growth is finite with probability one, where the growth is the block-length (f) in case of largen, while log(u) in the case of largeSNR. Also, the stable throughput region is defined as the region in which the arrival rates per unit-growth (per time-unit or per SNR-unit in the two cases) lie so that the queues remain stable.

2.4. Source side information

To keep our analysis tractable, we consider the case of i.i.d. arrivals. Thus, each sourcei is described by an arrival distributionp_i,(a), and the joint distribution of the arrival process isp(a) = Π_ip_i(a). While the joint distribution is often used in capacity analysis to obtain best possible capacity region [5], it is seldom known in such detail in operational systems. In source coding parlance, this is a problem of universal source coding over noisy channels, where the distribution is only partially known (see universal source coding over noiseless channels in [5]). Our objective is to study the role of this statistical information on the stability of multiuser-queuing system and, in the process, understand the interplay between statistical information and instantaneous source information (in the form of queue stateQ_i,(j)). Hence we will study the following series of cases.

1. (1a)

   Full statistical informationp(a) known to all nodes—K transmitters and the central receiver.

2. (1b)

   Each node knows arrival means ($\mathbb{E}$(a₁),$\mathbb{E}$(a₂),…,$\mathbb{E}$(a_K)) for all nodes and transmitters convey 1-bit of quantized queue information to the receiver every time-slot.

3. (2a)

   Each transmitter only knows its own arrival statisticsp_i,(a) but the receiver knowsp(a) and is allowed to feedback some information to all the transmitters.

4. (2b)

   Each transmitter knows only its own arrival mean$\mathbb{E}$(a_i), and conveys 1-bit of quantized queue information to the receiver every time-slot. In this case, the receiver knows ($\mathbb{E}$(a₁),$\mathbb{E}$(a₂),…,$\mathbb{E}$(a_K)), and is allowed to feedback some information to all the transmitters.

5. (3)

   No statistical information is available to any node and the transmitters can convey 1-bit of queue information.

Our focus is on finite-bit overhead information about the queue state from transmitters to receiver to counter lack of statistical knowledge. In the process, we discovered that a single bit of queue state information is sufficient to achieve our goals; as a result, we state our results only for single-bit information and note that the proof techniques can be generalized to multi bit information case. Furthermore, implicit in our constructions is the desire to use the simplest multiuser receiver and avoid universal decoding (which is not matched to any particular source distribution but to a whole class). Thus, the receiver adapts its decoder to match the current state of the queues in those cases where the arrival distributions (and hence the prior message probabilities) are (partially) unknown.

An analogue of quantized instantaneous source information is the quantized channel state information studied in fading channels [22,23] where the receivers convey a few bits of information about the current fading states. In the current case, the transmitters have instantaneous information about the sources; and, hence, they convey a few bits to the receiver to enable improved decoding. This source-channel duality in information sharing, while interesting in its own right, is not further discussed in this paper.

Finally, we note that each node in the system is assumed to know the transmit powers of each user and their channel gains, and hence knows the capacity region accurately. Thus the only uncertainty at the transmitters is potentially about the source arrival statistics of other nodes; and, in some cases (2a, 2b and 3), about the available capacity for each node.

In this section, we assume that the time-slots can be made arbitrarily large so that we can use the conventional large block length coding strategies [5] for multiple-access channels. We will give an achievable rate region for all five side information cases listed in Section 2.4. Two main code constructions are used, namely in Theorem 1 for Case 1a and Theorem 2 for Case 1b, and rest of the side-information cases follow from them (Cases 2a, 2b and 3). Throughout this section, we assume thatλ_i,< ∞ and lim_n→∞(Var(Δ_i,(k))/n²) < ∞

Theorem 1 (side-information Case 1a). The stable throughput region (as in Definition 3) coincides with the Shannon capacity region given in Lemma 1, when all K + 1nodes know the complete arrival distribution of all K sources.

Proof. Let the incoming rates (λ₁,λ₂,…,λ_K) be such that Σ_iϵSλ_i < C (Σ_iϵSP_i/N) where S ϵ$\mathbb{S}$ and$\mathbb{S}$ is set of all nonempty subsets of {1,2,…,K}. Letτ = (1/2 K)min_sϵ$\mathbb{S}$(C(ΣiϵsP_i/N) – Σ_iϵsλ_i). Letγ_i = λ_i, +τ. Note that (γ₁,γ₂,…,γ_K) is also in the interior of the capacity region of Lemma 1.

Suppose that the number of bits with the transmitteri at the beginning of time-slotk isQ_i(k). Then, Ω_i(k) = min(Q_i(k),nγ_i) bits are sent to the encoder. The encoding and decoding operations make use of the prior probabilities of all the possible2^nγi+1 – 1 messages (consisting of all messages of length ≤ nγ_i). The asymptotic rate at useri is thus no more thanγ_i. Since (γ₁,γ₂,…,γ_K) is in the interior of the capacity region, there exists an encoding and decoding scheme in which average probability of error at the decoder goes to 0 asn → ∞. Note here that we do not change the codebooks in every time slot. Once chosen in the first time-slot, the codebook for each user remains the same throughout the use of the channel in all subsequent timeslots.

Using the above encoding scheme, the queue update equation for useri (2) reduces toQ_i(k + 1) = Q_i(k) –min(Q_i(k),ny_i) + Δ_i(k) = (Q_i(k) –ny_i)⁺ + Δ_i(k). This queue update equation is different from [24] because in our case, the encoding is done at the beginning of a time-slot. Hence, Δ_i(k) bits will remain in the queue at the start of the next time-slot.We prove that this queue is stable in the appendix. This completes the proof. □

When there is incomplete information about statistical information, we can assume a distribution and encode as if the distribution is known. But, this approach will lead to a loss in stable throughput region due to mismatch of the probability distributions at the sources and the actual distribution (this leads to a loss in the achievable rates as shown in [25]). To avoid this loss, we consider 1-bit queue state information which can aid in alleviating the loss in performance.

Theorem 2 (side-information Case 1b).The stable throughput region (as in Definition 3)coincides with the Shannon capacity region given in Lemma 1,when all K +1nodes know the mean arrival rates of all K sources and transmitters convey 1-bit of quantized queue state information to the receiver in each time-slot.

Proof. Let the incoming rates (λ₁,λ₂,…,λ_K) be such that Σ_iϵSλ_i,< C (Σ_iϵsP_i/N) whereS ϵ$\mathbb{S}$ where$\mathbb{S}$ is set of all nonempty subsets of {1,2,…,K}. Lett = (1/2 K)min_sϵs(C(Σ_iϵSP/N) – Σ_iϵSλ_i). Letγ_i,= λ_i, + min(τ,λ_i). Note that (γ₁,γ₂,…,γ_K) is also in the interior of the capacity region.

Let us consider transmitteri. Suppose that the number of bits with the transmitter at the beginning of time-slotk beQ_i(k). IfQ_i(k) < nγ_i, we serve Ω_i,(k) = 0 bits, else we serve Ω_i,(k) = nγ_i bits. The input to the encoder at transmitteri can have any bit-sequence of lengthnγ_i. These are encoded to2^nγi codewords of lengthn (since we do not know the whole statistical information,we encode only the equally likely symbols in contrast to Theorem 1 where we encode all the possible bit sequences having length at-mostnγ_i). The transmitter sends the information of Ω_i(k) = 0 by sending the single bit quantized queue state information. The codebooks are chosen at the beginning of operation and stay fixed throughout. Since (y₁,y₂,…,y_K) is in the interior of the capacity region, there exists an encoding and decoding scheme with average probability of error at the decoder going to 0 asn goes to infinity.

Using the above scheme, the queue update (2) reduces toQ_i(k +1) = f (Q_i(k),nγ_i) + Δ_i(k), wheref (A,B) = A –B if A ≥ B, and = A otherwise. Note thatQ_i(k +1) ≤ (Q_i(k) –2ny_i)⁺ + (ny_i + Δ_i(k)). In other words, this queue is upper bounded by a queue whose stability can be proven similar to the appendix. Hence, we see that the queues are stable. This completes the proof. □

Lemma 3 (side-information Case 3).Suppose that the transmit power P_i = P for all i. All transmitters send 1-bit queue information as in Theorem 2. If nodes do not know anything about arrival distribution of any node (not even its own),then the stable throughput region contains the closure of (λ₁,λ₂,…, λ_k)where (λ₁,λ₂,…,λ_K)satisfy

for any predecided variable S > 0chosen without any knowledge ofarrival distribution or arrival means,and known to all the transmitting nodes and the base station.

Proof. By choosingγ_i = (1/K)C(KP/N) –δ/2 K and using the same protocol as in the proof of Theorem 2 to encode, we see that any point in the above region is in stable throughput region. □

Remark 1. AlthoughS can be chosen arbitrarily small, the knowledge of sameδ > 0 at all the nodes can be considered as a side-information.

Two important conclusions can be drawn from studying Theorems 1 and 2 and Lemma 3. First, there is a significant loss in the achievable stable throughput region if the transmitters do not know anything about the source arrival statistics at all nodes. This situation represents the common scenario in actual practice. The loss is entirely due to the fact that any transmitter has to guarantee that its packets will be received error-freewithout any knowledge of amount of data which other transmitters may be trying to send. Thus, each transmitter assumes that every source is sending at its peak rate, so that they essentially split the sum-rate capacity equally. However, in cases where some sources have lower arrival rates, this scheme can lead to a large loss compared to full-information scenario of Theorem 1 or partial knowledge with feed-forward bit of Theorem 2.

Second, the proofs of Theorems 1 and 2 suggest a simple architecture to get around the problem of every transmitter knowing the statistics of every source in the system. Essentially the transmitters need to know only an appropriate value oft to calculate how far the arrival rate is from the capacity region and hence decide their transmission rate. Thus if the receiver knows the statistics or arrival rates at each node, it can calculate the appropriate “backoff” parametert and send it to each transmitter. This is akin to congestion/rate control by base-stations and leads to the following result.

Corollary 1 (side-information Case 2).The stable throughput region (as in Definition 3)coincides with the Shannon capacity region given in Lemma 1 if

1. (2a)

   the K transmitters know only their own complete arrival distribution but the base station knows the complete arrival distribution ofall K sources,or

2. (2b)

   the K transmitters know only their own mean arrival rates but the base station knows all the mean arrival rates; in addition,transmitters send one bit ofinstanta- neous queue state information

if the base station can feedback a real number to all K sources.

Proof. The proof is similar to that of Theorems 1 and 2 except thatt is calculated at the base station and is fedback to all theK sources. □

3.1. Discussion

In Theorem 1, it is shown that with full statistical information aboutall the nodes atall the nodes guarantees that every point in the Shannon capacity region of Lemma 1 is in stable throughput region. Thus, full statistical information guarantees maximal achievable performance. The key ingredient of this result is that the probability of different bit sequences is known to the receiver which allows the receiver to use the optimal maximuma posteriori probability decoder. Thus, while each codeblock may have different number of information bits, the receiver has accurate knowledge of the probability of each message.

As the information about the distribution of source information bits reduces, the transmitter and the receiver no longer can perform optimal allocation of code rates and thus suffer from additional “overhead” of indicating the number of encoded bits in every codeword. If we reduce the information, we may not have the same knowledge of the encoding rate at the senders and the receiver, which will result in significant number of errors, and the stable throughput regions will be much less than the capacity region. This overhead can surprisingly be eliminated if the encoders can share one-bit information about their current queue state. When the distribution of arrivals is not known, we have to assume that the incoming symbols are equally likely. For this assumption to hold, we encode equally likely symbols which have the same number of input bits. Hence, we send one bit of queue information when the respective queue has less elements than that supported by the service rate of that particular transmitter, and send the bits supported by service rate otherwise. This helps us to send all the blocks with equal probability. The encoding rates just need the side information of mean arrival rates rather than the whole distribution since we know the prior probabilities of each codeword and do not need the whole distribution for this information. This is why in Theorem 2 when each node knows the arrival rates at all the nodes, we get stable queues when the mean arrival rates are within the capacity region. There is a loss in achievable rates as we know less and less information.

We further see in Lemma 3 that if we do not know any information, we have to predecide the encoding and decoding rates in the interior of the capacity region which leads to the stability region being smaller than the capacity region. Note that the 1-bit side information is not needed when all the queues always have data to send, the case which is commonly considered in information theoretic analysis resulting in Lemma 1.

We further see in Corollary 1 that if the base station can feedback a real number to the transmitting users once, we need much less side information at the transmitters. This side information is needed only once and hence can be communicated the same time when the codebooks are told to the receivers. In this case, every point in the capacity region is stable. Hence, we have a practical way akin to congestion control where we trade side information of other transmitters at a transmitter by some information from receiver.

Till now, we concentrated on the block-length being large enough to make the error probability at the receiver decrease to 0. We now consider the dual-like problem to keep the block-length fixed, while letting theSNR = (SNR₁,SNR₂,…,SNR_K) high enough for the probability of error at the decoder to be very small, where$SN{R}_i=P_i/N\doteq u^{{\alpha }_i}$, whereu is some baseSNR. We will give an achievable rate region for all five side-information cases listed in Section 2.4. Two main code constructions are used, namely in Theorem 3 for Case 1a and Theorem 4 for Case 1b, and rest of the side-information cases follows from them (Cases 2a, 2b, and 3).

In this section, we also assume that lim_SNR→∞($\mathbb{E}$(Δi(k))/log(SNR_i)) < ∞ and lim_SNR→∞(Var(Δ_i(k))/log²(SNRi)) < ∞. As theSNR is large enough, the channel can support rates that are logarithmic inSNR. Hence, we can also support the arrival rates that are logarithmic inSNR. Hence, we let all the arrival rates be assumed to be a function ofSNR asλ_i ≐ l_i log(SNR_i) ≐ l_iα_i log(u). We also assume thatSNR_i for alli is known to all the nodes.

Theorem 3 (side-information Case 1a).The SNR-stable throughput region (as in Definition 4)coincides with the SNR- capacity region given in Lemma 2,when all K +1nodes know the complete arrival distribution of all K sources.

Proof. Let the incoming rates (λ₁,λ₂,…,λ_K) beλ_i ≐ l_iα_i log(u), with Σ_iϵSl_iα_i < (1/2)max_iϵSα_i, whereS ϵ$\mathbb{S}$, where$\mathbb{S}$ is set of all nonempty subsets of {1,2,…,K}. Letτ = (1/K)(1 – max_SϵSΣ_iϵS l_iα_i/(1/2)max_iϵSα_i)). Letg_i = l_i + τ/4. Note that (g₁,g₂,…,g_K) is also in the interior of theSNR-capacity region. We can take the departure rateγ_i = λ_i + (g_i − l_i)logSNR_i≐g_i logSNR_i≐g_iα_i log u.

The constructive queuing scheme is similar to that in Theorem 1 with the above arrival and departure rates. We get probability of error at the decoder going to 0 asu → ∞ since (g₁,g₂,…,g_K) is in the interior of the SNR-capacity region.

Using the above scheme, the queue states emerge asQ_i(k + 1) = (Q_i(k)– nγ_i)⁺ + Δ_i(k). Using similar procedure as in the appendix, we can easily show that the queues are stable. □

Theorem 4 (side-information Case 1b).The SNR-stable throughput region (as in Definition 4)coincides with the SNR- capacity region given in Lemma 2,when all K +1nodes know the mean arrival rates of all K sources and transmitters convey 1-bit of quantized queue state information to the receiver in each time-slot.

Proof. Let the incoming rates (λ₁,λ₂,…,λ_K) beλ_i ≐ l_iα_i log(u), with Σ_iϵSl_iα_i < (1/2)max_iϵSα_i, whereS ϵ$\mathbb{S}$, and$\mathbb{S}$ is set of all nonempty subsets of {1,2,…,K}. Letτ = (1/K)(1 – max_SϵS(Σ_iϵs l_iα_i/(1/2)max_iϵsα_i)). Letg_i = l_i + min(l_i,τ/4). Note that (g₁,g₂,…,g_K) is also in the interior of theSNR-capacity region. We can take the departure rateγ_i = λ_i + (g_i, −l_i)logSNR ≐ g_iα_i log u.

Let us consider transmitteri. Suppose that the number of bits with the transmitter at the beginning of time-slotk isQ_i(k). IfQ_i(k) < nγ_i, we serve Ω_i(k) = 0 bits, else we serve Ω_i,(k) = nγ_i bits. The input to the encoder at transmitteri can be any bit-sequence of lengthnγ_i. These are encoded to2^nγi codewords of lengthn. The transmitter sends the information of Ω_i(k) = 0 by sending the single-bit information that the queue is empty. Since (g₁,g₂,.…,g_K) is in the interior of the SNR-capacity region, there existsu large enough so that there exist an encoding and decoding scheme with arbitrarily small average probability of error asu goes to infinity.

Using the above scheme, the queue states emerge asQ_i (k +1) = f (Q_i(k),nγ_i,) + Δ_i,(k), wheref (A,B) = A –B ifA ≥ B, and = A otherwise. Using arguments similar to those used in the proof of Theorem 2, we can show that the queues are stable. □

Lemma 4 (side-information Case 3).Suppose that the transmit power P_i = P for all i,hence SNR_i = u. All transmitters send 1-bit queue information as in Theorem 4. If nodes do not know anything about arrival distribution of any node (not even its own),then the SNR-stable throughput region contains the closure of (l₁,(l₂,…,l_K),where (l₁,l₂,…,l_K)satisfy

for any predecided variable δ > 0chosen without any knowledge of arrival distribution or arrival means,and known to all the transmitting nodes and the base station.

Proof. The SNR-capacity region in this case is the closure of Σ_1≤i≤Kr_i < 1/2. By choosingg_i = 1/2K − δ/2K, γ_i ≐ g_i log u and using the same protocol as in the proof of Theorem 4 to encode, we see that any point in the above region as stable. □

We further see that both the Cases 1a and 1b in Theorems 3 and 4 suggest that at a transmitting node, we use the information of its own arrival distribution/means while the arrival distributions/means at other nodes are absorbed into the parameterτ similar to that in Section 3. Hence we consider a method where only the receiver knows the full arrival distribution/mean, computes an appropriateτ, and then relays it to all the transmitters as in Section 3. Note that this parameter is needed only once and not in every time slot. Using this, Theorems 3 and 4 change as follows.

Corollary 2 (side-information Case 2).The SNR-stable throughput region (as in Definition 4)coincides with the SNR- capacity region given in Lemma 2,when

1. (2a)

   all K-transmitting nodes know the complete arrival distribution of its own source,the base station knows the complete arrival distribution of all K sources,or

2. (2b)

   all K-transmitting nodes know the mean arrival rates of its own source,the base station knows the mean arrival rates of all K sources,transmitters convey 1-bit of quantized queue state information to the receiver in each time-slot

if the base station can feedback a real number to all K sources.

Proof. The proof is similar to that of Theorems 3 and 4 except thatτ is calculated at the base station and is fedback to all theK sources. □

4.1. Discussion

The results follow the similar behavior as in Section 3 for finiteSNR. When each node knows the distribution of arrivals at all the nodes, theSNR-stable throughput region coincides with theSNR-capacity region as in Theorem 3. As we decrease the side information, we loose in theSNR-stable throughput regions since we would have to predecide something. With the knowledge of whole distribution of arrival, we estimated the a priori probability of all the messages sent from the encoder that gave us the maximum stable throughput region. We show that the knowledge of whole distribution of arrival can be relaxed if we allow one bit of information from the transmitters to indicate whether the queue is empty. On these lines, if each node knows the mean arrival rate at all the queues, stable queues are achieved as long as the mean arrival rates are in the interior of the SNR-capacity region (Theorem 4). We further see that there is a loss in the throughput stability regions due to predeciding some terms when there is a less information. We further see in Corollary 2 that the knowledge of arrival distribution/means of other transmitters is not needed at a transmitter as long as there is a real feedback from the base station.

Till now, we saw the similarities in the two cases when theSNR is finite with infinite block-length and when the block- length is finite whileSNR is infinite. The main difference in the two approaches is the definition of stability. The definition of stability in the case of infinite block length means that the queue length has to be finite multiple of block-length with probability 1. This would mean that a bit would take extremely large amount of time to get serviced (Asn → ∞, each bit even if waits one time-slot means that it waits for infinite time). In the case of infiniteSNR stability refers to queue length being a finite multiple of log(SNR) with probability 1. Since, increasingly large number of bits are being served each time unit, the average bit delay is smaller.

In this paper, we studied the impact of side information on the stable throughput regions. We found that when every node knows the distribution of the arrival rates of every node, the stable throughput region coincides with the Shannon capacity region for both finite time-slots with largeSNR and finiteSNR with large time-slots. We also considered a variant of the side information in which the knowledge of the whole of the distribution is replaced by the arrival means, along with one bit of side-information in every time-slot; and that seems enough. Further, the case of side information at a node in which a transmitter knows only its own arrival statistics was studied, and we found that a feedback from the receiver is enough. Finally, we showed that any information content that is less than the mean arrival rates known to all nodes implies a reduced stable throughput region, a case which is indicative of the performance of real systems.

We acknowledge fruitful discussions with Robert Calderbank and Tian Lan (Princeton University). We would also like to thank the anonymous reviewers for many suggestions that improved this paper. V. Aggarwal was partially supported by NSF Awards ANI-0338807, CCF-0635331, CNS-0325971, and AFOSR under Contract 00852833. A. Sabharwal was partially supported by NSF Awards CCF-0635331 and CNS- 0325971.

Authors and Affiliations

1. Department of Electrical Engineering, Princeton University, Princeton, NJ, 08544, USA

   Vaneet Aggarwal

2. Department of Electrical & Computer Engineering, Rice University, Houston, TX, 77005, USA

   Ashutosh Sabharwal

Corresponding author

Correspondence toVaneet Aggarwal.

Appendix

Stability of Queues In Theorem 1

The queues emerge asQ_i(k + 1) = (Q_i(k) –nγ_i)⁺ + Δ_i(k). LetQ_i(k)/n = V_i(k) andb_i(k) = Δ_i(k)/n –y_i. Using this, we see that

Continuing in this way, we get

Asb_i(1) ≤ Δ_i(1)/n,

Let

whered_i(k) = (Δ_i(k) – Δ_i(k – 1))/n + b_i(k).V_i(j) andV′_i (j) have same distribution since we just renamed the labels and all theb_i’s were i.i.d.

Lete_i(k) = d_i(2) + d_i(j – 2) + …d_i(k – 1) fork ≥ 3 and 0 otherwise. We see thatV′_i (j) can only increase withj, and hence asj → ∞must converge to the (possibly infinite) random variableṼ_i,

As E(d,(k)) < 0, it follows being similar analysis as of [26, Section 1.7] that sup_k≥2e_i(k) is finite with probability 1 and has a proper probability distribution (by proper, we mean that limit of the distribution is 0 and 1 at –∞ and to, resp.). As mean and variance of Δ_i(1)/n is finite forn large enough, this has a proper distribution function,Ṽ_i is finite with probability 1 and forms a proper distribution function. SinceṼ_i is finite with probability 1, bothV_i(j) andV′_i(j) converge to the same distribution, which is the distribution ofṼ_i. Hence, there exists an integerM such that lim_j→∞ Pr[Q_i(j) < nx] = F (x,n) and lim_x→∞F(x,n) = 1, fori = 1,2,…,K andn > M. Thus, the queues are stable forn large enough.

Open Access This article is distributed under the terms of the Creative Commons Attribution 2.0 International License (https://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Reprints and permissions