The latency and control overhead of sending the preamble in synchronous communications can be excessive when transmitting short sensing/control messages. To reduce these overheads, this work proposes a preamble-free solution based on the framework of quickest change detection. Specific contributions include a joint decoding/demodulation scheme that is provably asymptotically optimal, and a more practical CuSumlike implementation. Numerical results show that the proposed scheme reduces the latency by$\mathbf{4 7 \% - 7 9 \%}$when compared to the preamble-based solutions. The scheme is also inherently robust and automatically adapts to any unknown underlying SNRs.

Streaming codestake a string of source symbols as input and output a string of coded symbols in real time, which eliminate the queueing delay of traditionalblock codesand are thus especially appealing for delay sensitive applications. This work studies the asymptotics of random linear streaming codes (RLSCs) in the large finite-field-size regime under the i.i.d. symbol erasure channel models. Two important scenarios are analyzed: (i) tradeoff between decoding deadline Δ and probability of errorpeassuming infinite memory α = ∞; and (ii) tradeoff between α andpeassuming infinite Δ = ∞. For each scenario, this work derives the corresponding asymptotic constant ρ, power β and decay rate η that satisfype(x) ∼ ρxβe−ηx. The results of (i) and (ii) are then used to study an important code design problem: Under a given target deadline Δ, what is the memory length α needed for the error probabilitypeto be within a factor ofc> 1 of the best possiblep∗eover α. Further analysis also suggests that regardless thecvalue being considered, the necessary memory length is approximately 3–7% of the target deadline Δ when Δ is large, the actual percentage depending on the channel model and the coding rate. Such a prediction is consistent with existing brute-force-based evaluations.

This work generalizes the Age-of-Information (AoI) minimization problem of update-through-queue systems such that in addition to deciding the waiting time, the sender also chooses over which “channel” each update packet will be served. Different channels have different costs, delays, and quality characteristics that reflect the scheduler's selections of routing, communications, and update modes. Instead of considering only two channels with restricted parameters as in the existing works, this work studies the general$K$-channel problem with arbitrary parameters. The results show that both the optimal waiting time and the optimal channel-selection policies admit an elegant water-filling structure, and can be efficiently computed by the proposed low-complexity fixed- point- based numerical method.

We study reliable communication over point-to-point adversarial channels in which the adversary can observe the transmitted codeword via some function that takes the$n$-bit codeword as input and computes an$rn$-bit output for some given$r \in [{0,1}]$. We consider the scenario where the$rn$-bit observation is computationally bounded – the adversary is free to choose an arbitrary observation function as long as the function can be computed using a polynomial amount of computational resources. This observation-based restriction differs from conventional channel-based computational limitations, where in the later case, the resource limitation applies to the computation of the (adversarial) channel error/corruption. For all$r \in [0,1-H(p)]$where$H(\cdot)$is the binary entropy function and$p$is the adversary’s error budget, we characterize the capacity of the above channel and find that the capacity is identical to the completely oblivious setting ($r=0$). This result can be viewed as a generalization of known results on myopic adversaries and on channels with active eavesdroppers for which the observation process depends on a fixed distribution and fixed-linear structure, respectively, that cannot be chosen arbitrarily by the adversary.

Age-Of-Information (AoI) is a metric that focuses directly on the application-layer objectives, and a canonical AoI minimization problem is the update-through-queues models. Existing results in this direction fall into two categories: The open-loop setting for which the sender is oblivious of the packet departure time, versus the closed-loop setting for which the decision is based on instantaneous Acknowledgment (ACK). Neither setting perfectly reflects modern networked systems, which almost always rely on feedback that experiences some delay. Motivated by this observation, this work subjects the ACK traffic to a second queue so that the closed-loop decision is made based on delayed feedback. Near-optimal schedulers have been devised, which smoothly transition from the instantaneous-ACK to the open-loop schemes depending on how long the feedback delay is. The results quantify the benefits of delayed feedback for AoI minimization in the update-through-queues systems.

Streaming codes eliminate the queueing delay and are an appealing candidate for low latency communications. This work studies the tradeoff between error probability peand decoding deadline ∆ of infinite-memory random linear streaming codes (RLSCs) over i.i.d. symbol erasure channels (SECs). The contributions include (i) Proving pe(∆) ∼ ρ∆−1.5e−η∆. The asymptotic power term ∆−1.5of RLSCs is a strict improvement over the ∆−0.5term of random linear block codes; (ii) Deriving a pair of upper and lower bounds on the asymptotic constant ρ, which are tight (i.e., identical) for one specific class of SECs; (iii) For any c > 1 and any decoding deadline ∆, the c-optimal memory length $\alpha _c^{\ast}(\Delta )$ is defined as the minimal memory length α needed for the resulting peto be within a factor of c of the best possible $p_e^{\ast}$ under any α, an important piece of information for practical implementation. This work studies and derives new properties of $\alpha _c^{\ast}(\Delta )$ based on the newly developed asymptotics.

This work considers the problem of sending a 1-bit message over an acyclic network, where the “edge” connecting any two nodes is a memoryless binary-input/symmetric-output (BISO) channel. For any arbitrary acyclic network topology and constituent channel models, a min-cut-based converse of the learning rate, denoted by r*, is derived. It is then shown that for any r*, one can design a scheme with learning rate r. Capable of approaching the optimal r*, the proposed scheme is thus the asymptotically fastest for sending one bit over any acyclic BISO-channel network. The construction is based on a new concept of Lossless Amplify-&-Forward, a sharp departure from existing multi-hop communication scheme designs.

In this paper, we consider a status update system, where an access point collects measurements from multiple sensors that monitor a common physical process, fuses them, and transmits the aggregated sample to the destination over an erasure channel. Under a typical information fusion scheme, the distortion of the fused sample is inversely proportional to the number of measurements received. Our goal is to minimize the long-term average age while satisfying the average energy and general age-based distortion requirements. Specifically, we focus on the setting in which the distortion requirement is stricter when the age of the update is older. We show that the optimal policy is a mixture of two stationary, deterministic, threshold-based policies, each of which is optimal for a parameterized problem that aims to minimize the weighted sum of the age and energy under the distortion constraint. We then derive analytically the associated optimal average age-cost function and characterize its performance in the large threshold regime, the results of which shed critical insights on the tradeoff among age, energy, and the distortion of the samples. We have also developed a closed-form solution for the special case when the distortion requirement is independent of the age, arguably the most important setting for practical applications.

Many emerging applications require multi-hop wireless relaying, for which reliability requirements increase packet retransmissions, amplifying latency across hops. Existing works mostly focus on the simple two-hop, single-relay setting and ignore spatial diversity that enables a destination to receive independent noisy copies of data from multiple relays in parallel to improve error performance. In this paper, we consider a single-bit source message and construct learning-rate-optimal, delay-constrained multi-hop schemes by jointly designing time-varying, distributed relay mapping functions with destination decoding strategies. The learning-rate-optimal scheme, however, requires channel and relaying knowledge, which limits practical implementation. With the aim of practical implementation, we have also considered several low-complexity relay and destination strategies and analyzed their performances under different combinations. Numerical comparisons show that none of the alternatives universally dominate, and the system designer thus has to carefully opt for the best suitable schemes depending on the channel conditions. Finally, we show that carefully coordinating many low-quality relay channels in parallel can vastly outperform having only one high-quality relay channel, which demonstrates the spatial diversity gains for the first time in the learning over parallel-relay setting.

Multi-hop line networks have emerged as an important abstract model for modern and increasingly dense communication networks. In addition, the growth of real-time and mission-critical services has created high demand for and increased research interest in low-latency communications. The combination of these facts motivates a new investigation of data transmission schemes for$L$-hop line networks from a delay-vs-throughput perspective. To this end, this work defines a metric called the delay amplification factor for a target throughput$R$, denoted by${\mathsf {DAF}}(R)$, which characterizes the growth rate of the (asymptotic) delay with respect to the number of hops. We show that all existing relay schemes, e.g., Decode-&-Forward (DF), have$\lim _{R\nearrow C} {\mathsf {DAF}}(R)=\Omega (L)$, which is consistent with the decades-old perception that delay grows linearly with respect to$L$. We then design a scheme satisfying$\lim _{R\nearrow C} {\mathsf {DAF}}(R)=1$, if the bottleneck hop is the last hop, i.e., its asymptotic delay does not grow with respect to$L$. The results imply that this linearly growing delay is an artifact of the existing DF designs, and it is possible to surpass it and attain the true fundamental limit with a new delay-centric solution. In the second half of this work, we further show that if variable-length coding and one-bit stop-feedback are allowed, we can relax the condition bottleneck being the last hop and attain$\lim _{R\nearrow C} {\mathsf {DAF}}(R)= 1$for any arbitrary line networks.

The ever-increasing needs of supporting real-time applications have spurred new studies on minimizing Age-of-Information (AoI), a novel metric characterizing the data freshness of the system. This work studies the single-queue information update system and strengthens the seminal results of Sun et al. on the following fronts: (i) When designing the optimal offline schemes with full knowledge of the delay distributions, a newfixed-point-basedmethod is proposed withquadratic convergence rate, an order-of-magnitude improvement over the state-of-the-art; (ii) When the distributional knowledge is unavailable (which is the norm in practice), two new low-complexity online algorithms are proposed, which provably attain the optimal average AoI penalty; and (iii) the online schemes also admit a modular architecture, which allows the designer toupgradecertain components to handle additional practical challenges. Two such upgrades are proposed for the situations: (iii.1) The AoI penalty function is also unknown and must be estimated on the fly, and (iii.2) the unknown delay distribution is Markovian instead of i.i.d. The performance of our schemes is either provably optimal or within 3% of the omniscient optimal offline solutions in all simulation scenarios.

We study reliable communication over point-to-point adversarial channels in which the adversary can observe the transmitted codeword via some function that takes the n-bit codeword as input and computes an rn-bit output for some given r ∈ [0,1]. We consider the scenario where the rn-bit observation is computationally bounded – the adversary is free to choose an arbitrary observation function as long as the function can be computed using a polynomial amount of computational resources. This observation-based restriction differs from conventional channel-based computational limitations, where in the later case, the resource limitation applies to the computation of the (adversarial) channel error. For all r ∈ [0,1 − H(p)] where H(•) is the binary entropy function and p is the adversary’s error budget, we characterize the capacity of the above channel. For this range of r, we find that the capacity is identical to the completely obvious setting (r = 0). This result can be viewed as a generalization of known results on myopic adversaries and channels with active eavesdroppers for which the observation process depends on a fixed distribution and fixed-linear structure, respectively, that cannot be chosen arbitrarily by the adversary.

Channel dispersion quantifies the convergence speed of coding rate to channel capacity under different latency constraints. Under the setting of packet erasure channels (PECs) with Bernoulli packet arrivals, this work characterizes the channel dispersions of random linear streaming codes (RLSCs) and MDS block codes, respectively. New techniques are developed to quantify the channel dispersion of sequential (non-block-based) coding, the first in the literature. The channel dispersion expressions are then used to compare the levels of error protection between RLSCs and MDS block codes. The results show that if and only if the target error probability peis smaller than a threshold (≈0.1774), RLSCs offer strictly stronger error protection than MDS block codes, which is on top of the already significant 50% latency savings of RLSCs that eliminate the queueing delay completely.

One canonical example of Age-Of-Information (AoI) minimization is the update-through-queues models. Existing results fall into two categories: The open-loop setting for which the sender is oblivious of the actual packet departure time, versus the closed-loop setting for which the decision is based on instantaneous Acknowledgement (ACK). Neither setting perfectly reflects modern networked systems, which almost always rely on feedback that experiences some delay. Motivated by this observation, this work subjects the ACK traffic to an independent queue so that the closed-loop decision is made based on delayed feedback. Near-optimal schedulers have been devised, which smoothly transition from the instantaneous-ACK to the openloop schemes depending on how long the feedback delay is. The results thus quantify the benefits of delayed feedback for AoI minimization in the update-through-queues systems.

The most commonly used setting in the coded caching literature consists of the following four elements: (i) homogeneous file sizes, (ii) homogeneous cache sizes, (iii) user-independent homogeneous file popularity (i.e., all users share the same file preference), and (iv) worst-case rate analysis. While recent results have relaxed some of these assumptions, deeper understanding of the full heterogeneity setting is still much needed since traditional caching schemes place little assumptions on file/cache sizes and almost always allow each user to have his/her own file preference through individualized file request prediction. Taking a microscopic approach, this paper characterizes the exact capacity of the smallest 2-user/2-file ($N=K=2$) problem but under the most general setting that simultaneously allows for (i) heterogeneous files sizes, (ii) heterogeneous cache sizes, (iii) user-dependent file popularity, and (iv) average-rate analysis. Solving completely the case of$N=K=2$could shed further insights on the performance and complexity of optimal coded caching with full heterogeneity for arbitrary$N$and$K$.

Streaming codestake a string of source symbols as input and output a string of coded symbols in real time, which eliminate the queueing delay of traditionalblock codesand are thus especially appealing for delay sensitive applications. Existing works on streaming code performance either focused on the asymptotic error-exponent analyses, or on the optimal code construction underdeterministic adversarial channel models. In contrast, this work analyzes the exact error probability ofrandom linear streaming codes(RLSCs) in the large field size regime over the stochastic i.i.d. symbol erasure channel model. A closed-form expression of the error probability of large-field-size RLSCs is derived under, simultaneously, the finite memory length and decoding deadline constraints. The result is then used to examine the intricate tradeoff between memory length (complexity), decoding deadline (delay), code rate (throughput), and error probability (reliability). Numerical evaluation shows that under the same code rate and error probability requirements, the end-to-end delay of RLSCs is 40–48% of that of the optimal block codes (i.e., MDS codes). This implies that switching from block codes to streaming codes not only eliminates the queueing delay completely (which accounts for the initial 50% of the delay reduction) but also improves the reliability (which accounts for the additional 2–10% delay reduction).

The ubiquitous usage of communication networks in modern sensing and control applications has kindled new interests on the timing coordination between sensors and controllers, i.e., how to use the “waiting time” to improve the system performance. Contrary to the common belief that a zero-wait policy is optimal, Sunet al.showed that a controller can strictly improve the data freshness, the so-called Age-of-Information (AoI), by postponing transmission in order to lengthen the duration of staying in a good state. The optimal waiting policy for thesensorside was later characterized in the context of remote estimation. Instead of focusing on the sensor and controller sides separately, this work develops the jointly optimal sensor/controller waiting policy in a Wiener-process system. This work generalizes the above two important results in the sense that not only do we consider joint sensor/controller designs (as opposed to sensor-only or controller-only schemes), but we also assume random delay in both the forward and feedback directions (as opposed to random delay in only one direction). In addition to provable optimality, extensive simulation is used to verify the performance of the proposed scheme.

Motivated by the applications for low-delay communication networks, the finite-length analysis, or channel dispersion identification, of the multi-user channel is very important. Recent studies also incorporate the effects of feedback in point-to-point and common-message broadcast channels (BCs). However, with private messages and feedback, finite-length results for BCs are much more scarce. Though it is known that feedback can strictly enlarge the capacity, the ultimate feedback capacity regions remain unknown for even some classical channels including Gaussian BCs. In this work, we study the two-user broadcast packet erasure channel (PEC) with causal feedback, which is one of the cleanest feedback capacity results and the capacity region can be achieved by elegant linear network coding (LNC). We first derive a new finite-length outer bound for any LNCs and then accompanying inner bound by analyzing a three-phase LNC. For the outer-bound, we adopt a linear-space-based framework, which can successfully find the LNC capacity. However, naively applying this method in finite-length regime will result in a loose outer bound. Thus a new bounding technique based on carefully labelling each time slot according to the type of LNC transmitted is proposed. Simulation results show that the sum-rate gap between our inner and outer bounds is within 0.02 bits/channel use. Asymptotic analysis also shows that our bounds bracket the channel dispersion of LNC feedback capacity for broadcast PEC to within a factor of Q-l (E/2)/Q-l (E).

Streaming codes take a string of source symbols as input and output a string of coded symbols in real time, which effectively eliminate the queueing delay and are regarded as a promising scheme for low latency communications. Aiming at quantifying the fundamental latency performance of random linear streaming codes (RLSCs) over i.i.d. symbol erasure channels, this work derives the exact error probability under, simultaneously, the finite memory length and finite decoding deadline constraints. The result is then used to examine the tradeoff among memory length (complexity), decoding deadline (delay), and error probability (reliability) of RLSCs for the first time in the literature. Two critical observations are made: (i) Too much memory can adversely impact the performance under a finite decoding deadline constraint, a surprising finding not captured by the traditional wisdom that large memory length monotonically improves the performance in the asymptotic regime; (ii) The end-to-end delay of the RLSC is roughly 50% of that of the MDS block code when under identical code rate and error probability requirements. This implies that switching from block codes to RLSCs not only eliminates the queueing delay (thus 50%) but also has little negative impact on the error probability.

One main objective of ultra-low-latency communications is to minimize the data staleness at the receivers, recently characterized by a metric called Age-of-Information (AoI). While the question of when to send the next update packet has been the central subject of AoI minimization, each update packet also incurs the cost of transmission that needs to be jointly considered in a practical design. With the exponential growth of interconnected devices and the increasing risk of excessive resource consumption in mind, this work derives an optimal joint cost-and-AoI minimization solution for multiple coexisting source-destination (S-D) pairs. The results admit a new AoI-market-price-based interpretation and are applicable to the setting of (a) general heterogeneous AoI penalty functions and Markov delay distributions for each S-D pair, and (b) a general network cost function of aggregate throughput of all S-D pairs. Extensive simulation is used to demonstrate the superior performance of the proposed scheme.

With the recent emergence of many low-latency applications over wireless networks, the need for accurate finite-length analysis of channel coding over multi-user wireless channels is ever increasing. This paper focuses exclusively on the two-user broadcast packet erasure channel (PEC) with causal feedback, for which existing results show that various linear network coding (LNC) schemes can attain the broadcast capacity region when the block length approaches infinity. Instead of the asymptotic capacity-based analysis, this work derives the exact value of the LNC-based broadcast channel dispersion. Our approach is based on a new explicit characterization of the optimal LNC scheme under any arbitrarily given finite block length. The results show that among all existing asymptotically capacity-achieving LNC schemes, one (class) of them is provably finite-length optimal. By analyzing its second-order asymptotic, we have thus derived the exact (optimal) LNC broadcast channel dispersion, which closes the gap of the state-of-the-art inner and outer bounds previously derived in Lin et al. ISIT 2021

Coded caching is a technique for reducing congestion in communication networks by prefetching content during idle periods and exploiting multicasting opportunities during periods of heavy traffic. Most of the existing research in this area has focused on minimizing the worst case (i.e., peak) rate in a broadcast link with multiple identically distributed user requests. However, modern content delivery networks are investing very heavily in profiling their users and predicting their preferences. The minimal achievable rate of a coded caching scheme with heterogeneous user profiles is still unknown in general. This paper presents the first steps towards solving that problem by analyzing the case of two users with distinct but overlapping demand sets. Specifically, it provides a complete characterization of the uniform-average-rate capacity when the sets overlap in just one file and shows that such capacity can be achieved with selfish and uncoded prefetching. Then, it characterizes the same capacity under selfish and uncoded prefetching when the demand sets overlap in two or more files. The paper also provides explicit prefetching schemes that achieve those capacities. All our results allow for arbitrary (and not necessarily identical) users' cache sizes and number of files in each demand set.

The ubiquitous usage of communication networks in modern sensing and control applications has kindled new interests on the timing-based coordination between sensors and controllers, i.e., how to use the "waiting time" to improve the system performance. Contrary to the common belief that a zero-wait policy is always optimal, Sun et al. showed that a controller can strictly improve the data freshness, the so-called Age-of-Information (AoI), by postponing transmission in order to lengthen the duration of staying in a good state. The optimal waiting policy for the sensor side was later characterized in the context of remote estimation. Instead of focusing on the sensor and controller sides separately, this work develops the optimal joint sensor/controller waiting policy in a Wiener-process system. The results can be viewed as strict generalization of the above two important results in the sense that not only do we consider joint sensor/controller designs (as opposed to sensor-only or controller-only schemes), but we also assume random delay in both the forward and feedback directions (as opposed to random delay in only one direction). In addition to provable optimality, extensive simulation is used to verify the performance of the proposed scheme in various settings.

Streaming codes encode a string of source packets and output a string of coded packets in real time, which eliminate the queueing delay of block coding and are thus especially suitable for delay-sensitive applications. This work studies random linear streaming codes (RLSCs) and i.i.d. packet erasure channels. While existing works focused on the asymptotic error-exponent analyses, this work characterizes the error rate in the finite memory length regime and the contributions include: (i) A new information-debt-based description of the error event; (ii) A matrix-based characterization of the error rate; (iii) A closed-form approximation of the error rate that is provably tight for large memory lengths; and (iv) A new Markov-chainbased analysis framework, which can be of independent research interest. Numerical results show that the approximation, i.e. (iii), closely matches the exact error rate even for small memory length (≈ 20). The results can be viewed as a sequential- coding counterpart of the finite length analysis of block coding [Polyanskiy et al. 10] under the specialized setting of RLSCs.

The ever-increasing needs of supporting real-time applications have spurred a considerable number of studies on minimizing Age-of-Information (AoI), a new metric characterizing the data freshness of the system. This work revisits and significantly strengthens the seminal results of Sun et al. on the following fronts: (i) The optimal waiting policy is generalized from the 1-way delay to the 2-way delay setting; (ii) A new way of computing the optimal policy with quadratic convergence rate, an order-of-magnitude improvement over the state-of-the-art bisection methods; and (iii) A new low-complexity adaptive online algorithm that provably converges to the optimal policy without knowing the exact delay distribution, a sharp departure from the existing AoI algorithms. Contribution (iii) is especially important in practice since the delay distribution can sometimes be hard to know in advance and may change over time. Simulation results in various settings are consistent with the theoretic findings.

The capacity region of 1-to-K broadcast packet erasure channels with ACK/NACK is well known for some scenarios, e.g., K ≤ 3, etc. However, existing achievability schemes either require knowing the target rate R→in advance, and/or have a complicated description of the achievable rate region that is difficult to prove whether it matches the capacity or not. This work proposes a new network coding scheme with the following features: (i) its achievable rate region is identical to the capacity region for all the scenarios in which the capacity is known; (ii) its achievable rate region is much more tractable and has been used to derive new capacity rate vectors; (iii) it employs sequential encoding that naturally handles dynamic packet arrivals; (iv) it automatically adapts to unknown packet arrival rates R→; (v) it is based on GF(q) with q ≥ K. In addition to analytically characterizing the achievable rate region of the proposed scheme, numerical simulation has been used to verify its queue length and delay performance.

This work falls under the broad setting of coded caching with user-dependent file popularity and average-rate capacity analysis. In general, the exact capacity characterization with user-dependent file popularity remains an open problem. For example, user 1 may be interested in files 1 and 2 with probabilities 0.6 and 0.4, respectively, while user 2 may be interested in only files 2, and 3 with probabilities 1/3 and 2/3, respectively, but not interested in file 1 at all. An optimal scheme needs to carefully balance the conflicting interests under the given probabilistic weights. Motivated by this fundamental but intrinsically difficult problem, this work studies the following simplified setting: Each user k is associated with a file demand set (FDS) Θk; each file in Θkis equally desired by user k with probability 1/|Θk| and files outside Θkis not desired at all. Different users may have different Θk1≠ Θk2, which reflects the user-dependent file popularity. Various capacity results have been derived (mostly for the cases of K = 2 users). One surprising byproduct is a proof showing that selfish coded caching is insufficient to achieve the capacity. That is, in an optimal coded caching scheme, a user sometimes has to cache the files of which he/she has zero interests.

The most commonly used setting in the coded caching literature consists of the following five elements: (i) homogeneous file sizes, (ii) homogeneous cache sizes, (iii) user-independent homogeneous file popularity (i.e., all users share the same file preference), and (iv) worst-case rate analysis. While recent results have relaxed some of these assumptions, deeper understanding of the full heterogeneity setting is still much needed since traditional caching schemes place little assumptions on file/cache sizes and almost always allow each user to have his/her own file preference through individualized file request prediction. Taking a microscopic approach, this paper characterizes the exact capacity of the smallest 2-user/2-file (N = K = 2) problem but under the most general setting that simultaneously allows for (i) heterogeneous files sizes, (ii) heterogeneous cache size, (iii) user-dependent file popularity, and (iv) average-rate analysis. Solving completely the case of N = K = 2, the results would shed further insights on the performance and complexity of optimal coded caching with full heterogeneity for arbitrary N and K.

The abstract model of the multi-hop relay channel is fundamental to a vast variety of modern communication systems. This fact, coupled with the demand for ultra-reliable-low-latency communication (URLLC), motivates a new investigation of relay channels from a delay-vs-throughput perspective. This work seeks to analyze this tradeoff in the regime of asymptotically large, yet still finite delay. A new metric called the Delay Amplification Factor (DAF) is introduced, which allows analytic comparison of the asymptotic delay across different relay solutions, e.g. decode-&-forward (DF), compress-&-forward, etc. The optimal DAF (over all possible existing/future designs) is then characterized for two special settings, one with fixed-length coding and one with variable-length coding and 1-bit stop feedback. The results show that under some general conditions, the optimal end-to-end delay over an L-hop line network is asymptotically comparable to the delay over the single bottleneck hop, and it does not grow linearly with respect to L. The linearly growing delay penalty commonly encountered in DF and other schemes is thus an artifact rather than a fundamental limit of multi-hop relay communication.

Coded caching can exploit multicast opportunities even when multiple users request different pieces of content, and thus can significantly reduce the backhaul requirement to serve high-volume content. A common assumption in existing studies of coded caching is that all files are with the same size, which however may not be true in reality. Our previous work [1] first studied this problem, and proposed a non-trivial lower bound, as well as a new achievable scheme that uses a caching probability increasing proportionally with the file size. However, the gap [1] of the achievable rate and the lower bound still differs by a factor of Θ(log K), where K is the number of users in the system. In this paper, under a mild assumption that the total size of all files is larger than eight times the size of one individual cache, we will close this gap and reduce it to a constant by proposing a novel new lower bound and another new achievable scheme. Our lower bound is derived by considering a new cut-set bound, where files of a type1will be requested more often if the number of such files is smaller. Our achievable scheme uses a caching probability that decreases with the number of files with a same type. The improvements on both the lower bound and the achievable rate make their gap constant.

This work considers Gaussian linear control systems where the goal is to guarantee system-state mean-square stability (i.e., E(||x(t)||2) ≤ D) while minimizing the traffic rate R between the sensor(s) and the controller. Most existing results either assume zero delay or focus on the asymptotic setting that overlooks the impact of delay. Nonetheless, in practice the communication delay is randomly distributed due to varying channel/network conditions. When the sensor measurement finally arrives at the controller, the age-of-information is thus random. Heuristically, an “old” measurement provides less valuable information than a “young” measurement but the quantitative impact of random delay on the optimal rate-cost tradeoff R*(D) remains an open problem. This work provides the first lower bound RLB(D) for the random delay setting and designs a simple scheme that leads to a numerically evaluated upper bound RUB(D). Jointly RLB(D) and RUB(D) bracket the optimal tradeoff R*(D). The new RLB(D) is asymptotically tight when either D→∞ or R→∞, and sheds further insights on how the (random) age of information could impact the performance of a cyber-physical control system.

The concept of distributed storage networks (DSNs) mostly follows two main modeling assumptions: Any k out of n surviving nodes should be able to reconstruct the protected file; and if one node fails, the replacement node can access d helper nodes to repair its content either functionally or exactly. Two major existing approaches for DSNs are the so-called regenerating codes (RCs) and locally repairable codes (LRCs), which have different design philosophies and focus on distinct applications. Instead of being limited by the framework of either RCs or LRCs, this work answers a fundamental question for general DSNs: For an arbitrarily given (n,k,d) value, whether there exists an intelligent helper node selection design that can strictly improve the storage-bandwidth tradeoff when compared with naive blind helper selection. Surprisingly, the answer is negative for a large set of (n,k,d) values. Namely, for those (n,k,d) values even the best helper selection design offers no gain over a blind solution. We call those (n,k,d) values indifferent-to-helper-selection (ITHS). The main contribution of this work is a necessary and sufficient condition that characterizes whether an (n,k,d) value is ITHS. As a fundamental study, this work assumes functional repair with unlimited computing power for encoding/decoding and focuses on the fundamental performance limits of intelligent helper selection. A new helper selection scheme, termed family helper selection, is proposed and used in the achievability analysis. For some scenarios, the proposed scheme is indeed optimal (as good as any helper selection one can design).

Recent works by Ahmad et al. and by Hollmann studied the concept of “locally repairable regenerating codes (LRRCs)” that successfully combines the functional repair and partial information exchange of regenerating codes (RCs) with the much-desired local repairability feature of locally repairable codes (LRCs). One important issue that needs to be addressed by any local repair schemes (including both LRCs and LRRCs) is that sometimes designated helper nodes may be temporarily unavailable, the result of various reasons that include multiple failures, degraded reads, or power-saving strategies to name a few. Under the setting of LRRCs with temporary node unavailability, this paper studies the impact of different helper selection methods. It proves that with node unavailability, all existing methods of helper selection, including those used in RCs and LRCs, can be insufficient in terms of achieving the optimal repair-bandwidth. For some scenarios, it is necessary to combine LRRCs with a new class of helper selection methods, termed dynamic helper selection, to achieve optimal repair-bandwidth. This paper also compares the performance of different classes of helper selection methods and answers the following fundamental question: is one method of helper selection intrinsically better than the other? for various scenarios.

We consider the communication capacity of wireline networks for a two-unicast traffic pattern. The network has two sources and two destinations with each source communicating an independent message to its own destination, subject to the capacity constraints on the directed edges of the network. We propose a simple outer bound for the problem that we call the generalized network sharing (GNS) bound. We show that this bound is the tightest edge-cut bound for two-unicast networks and is tight in several cases, though it is not tight in general. We also show that the problem of computing the GNS bound is NP complete. Finally, we show that despite its seeming simplicity, the two-unicast problem is a very difficult problem: the general network coding problem can be reduced to two-unicast. As a consequence, linear coding is insufficient to achieve capacity for general two-unicast networks, and non-Shannon inequalities are necessary for characterizing the capacity of general two-unicast networks.

The capacity region of 1-to-K broadcast packet erasure channels with ACK/NACK is known for some scenarios, e.g., K ≤ 3, etc. However, existing achievability schemes either require knowing the target rate R in advance, and/or have a complicated description of the achievable rate region that is difficult prove whether it matches the capacity or not. This work proposes a new network coding protocol with the following unique set of features: (i) Its achievable rate region is identical to the capacity region for all the scenarios in which the capacity is known; (ii) Its achievable rate region is much more tractable that existing works and has been used to derive new capacity rate vectors; (iii) It employs sequential encoding that naturally handles dynamic packet arrivals; (iv) It automatically adapts to unknown packet arrival rates R⃗; (v) It is based on GF(q) with q > K. Numerically, for K = 4, it admits an average control overhead 2-4% (assuming each packet has 1000 bytes), average encoding memory usage 48.5 packets, and average per-packet delay 94.8 time slots, when operating at 95% of the capacity.

This paper considers network communications under a hard timeliness constraint, where a source node streams perishable information to a destination node over a directed acyclic graph subject to a hard delay constraint. Transmission along any edge incurs unit delay, and it is required that every information bit generated at the source at the beginning of time t to be received and recovered by the destination at the end of time t + D - 1, where D > 0 is the maximum allowed end-to-end delay. We study the corresponding delay-constrained unicast capacity problem. This paper presents the first example showing that network coding (NC) can achieve strictly higher delay-constrained throughput than routing even for the single unicast setting and the NC gain can be arbitrarily close to 2 in some instances. This is in sharp contrast to the delay-unconstrained (D = ∞) single-unicast case where the classic min-cut/max-flow theorem implies that coding cannot improve throughput over routing. Motivated by the above findings, a series of investigation on the delay-constrained capacity problem is also made, including: 1) an equivalent multiple-unicast representation based on a time-expanded graph approach; 2) a new delay-constrained capacity upper bound and its connections to the existing routing-based results [Ying et al. 2011]; 3) an example showing that the penalty of using random linear NC can be unbounded; and 4) a counter example of the tree-packing Edmonds' theorem in the new delay-constrained setting. Built upon the time-expanded graph approach, we also discuss how our results can be readily extended to cyclic networks. Overall, our results suggest that delay-constrained communication is fundamentally different from the well-understood delay-unconstrained one and call for investigation participation.

Most existing wireless networking solutions are best-effort and do not provide any delay guarantee required by important applications, such as mobile multimedia conferencing and real-time control of cyber-physical systems. Recently, Hou and Kumar provided a novel framework for analyzing and designing delay-guaranteed wireless networking solutions. While inspiring, their idle-time-based analysis applies only to flows with a special traffic pattern called the frame-synchronized setting. The problem remains largely open for general traffic patterns. This paper addresses this challenge by proposing a general framework that characterizes and achieves the complete delay-constrained capacity region with general traffic patterns in single-hop downlink access-point wireless networks. We first show that the timely wireless flow problem is fundamentally an infinite-horizon Markov decision process (MDP). Then, we judiciously combine different simplification methods to prove that the timely capacity region can be characterized by a finite-size convex polygon. This for the first time allows us to characterize the timely capacity region of wireless flows with general traffic patterns. We then design three scheduling policies to optimize network utility and/or support feasible timely throughput vectors for general traffic patterns. The first policy achieves the optimal network utility and supports any feasible timely throughput vector but suffers from the curse of dimensionality. The second and third policies are inspired by our MDP framework and are of much lower complexity. Simulation results show that both achieve near-optimal performance and outperform other existing alternatives.

This paper considers the downlink traffic from a base station to two different clients. When assuming infinite backlog, it is known that inter-session network coding (INC) can significantly increase the throughput. However, the corresponding scheduling solution (when assuming dynamic arrivals instead and requiring bounded delay) is still nascent. For the two-flow downlink scenario, we propose the first opportunistic INC + scheduling solution that is provably optimal for time-varying channels, i.e., the corresponding stability region matches the optimal Shannon capacity. In particular, we first introduce a new binary INC operation, which is distinctly different from the traditional wisdom of XORing two overheard packets. We then develop a queue-length-based scheduling scheme and prove that it, with the help of the new INC operation, achieves the optimal stability region with time-varying channel quality. The proposed algorithm is later generalized to include the capability of rate adaptation. Simulation results show that it again achieves the optimal throughput with rate adaptation. A byproduct of our results is a scheduling scheme for stochastic processing networks with random departure, which relaxes the assumption of deterministic departure in the existing results.

Next generation wireless networks will carry traffic from a wide range of applications, and many of them may require packets to be delivered before their respective deadlines. In this paper, we investigate using inter-session network coding to send packets wirelessly for two deadline-constrained unicast sessions. In particular, each unicast session aims to transmit a file, whose packets have hard sequential deadline constraints. We first characterize the corresponding deadline-constrained capacity region under heterogeneous channel conditions and heterogeneous deadline constraints. We show that this deadline-constrained capacity region can be achieved asymptotically by modifying the existing generation-based (G-B) schemes. However, despite its asymptotic optimality, the G-B scheme has very poor performance for small and medium file sizes. To address these problems, we develop a new immediately-decodable network coding (IDNC) scheme that empirically demonstrates much better performance for short file sizes, and we prove analytically its asymptotic optimality when used to send large files. Our analysis uses a novel version of drift analysis, which could also be of independent interest to other IDNC schemes.

Most existing wireless networking solutions are best-effort and do not provide any delay guarantee required by important applications such as the control traffic of cyber-physical systems. Recently, Hou and Kumar provided the first framework for analyzing and designing delay-guaranteed network solutions. While inspiring, their idle-time-based analysis appears to apply only to flows with a special traffic (arrival and expiration) pattern, and the problem remains largely open for general traffic patterns. This paper addresses this challenge by proposing a new framework that characterizes and achieves the complete delay-constrained capacity region with general traffic patterns in single-hop downlink access-point wireless networks. We first formulate the timely capacity problem as an infinite-horizon Markov Decision Process (MDP) and then judiciously combine different simplification methods to convert it to an equivalent finite-size linear program (LP). This allows us to characterize the timely capacity region of flows with general traffic patterns for the first time in the literature. We then design three timely-flow scheduling algorithms for general traffic patterns. The first algorithm achieves the optimal utility but suffers from the curse of dimensionality. The second and third algorithms are inspired by our MDP framework and are of polynomial-time complexity. Simulation results show that both achieve near-optimal performance and outperform other existing alternatives.

Recently, Wang and Chen [1] showed that network coding (NC) can double the throughput as compared to routing in delay-constrained single-unicast communication. This is in sharp contrast to its delay-unconstrained counterpart where coding has no throughput gain. The result reveals that the landscape of delay-constrained communication is fundamentally different from the well-understood delay-unconstrained one and calls for investigation participation. In this paper, we generalize the Koetter-Medard algebraic approach [2] for delay-unconstrained network coding to the delay-constrained setting. The generalized approach allows us to systematically model deadline-induced interference, which is the unique challenge in studying network coding for delay-constrained communication. Using this algebraic approach, we characterize the coding capacity for single-source unicast and multicast, as the rank difference between an information space and a deadline-induced interference space. The results allow us to numerically compute the NC capacity for any given graph, serving as a benchmark for existing and future solutions on improving delay-constrained throughput.

This work considers the smart repeater network where a single source s wants to send two independent packet streams to destinations {d1, d2} with the help of relay r. The transmission from s or r is modeled by packet erasure channels: For each time slot, a packet transmitted by s may be received, with some probabilities, by a random subset of {d1, d2, r}; and those transmitted by r will be received by a random subset of {d1, d2}. Interference is avoided by allowing at most one of {s, r} to transmit in each time slot. One example of this model is any cellular network that supports two cell-edge users when a relay in the middle uses the same downlink resources for throughput/safety enhancement. In this setting, we study the capacity region of (R1, R2) when allowing linear network coding (LNC). The proposed LNC inner bound introduces more advanced packing-mixing operations other than the previously well-known butterfly-style XOR operation on overheard packets of two co-existing flows. A new LNC outer bound is derived by exploring the inherent algebraic structure of the LNC problem. Numerical results show that, with more than 85% of the experiments, the relative sum-rate gap between the proposed outer and inner bounds is smaller than 0.08%, thus effectively bracketing the LNC capacity of the smart repeater problem.

Supporting delay-sensitive traffic is critical to the next-generation communication network. This work studies the 1-to-2 broadcast packet erasure channels with causal ACKnowledgement (ACK), which is motivated by practical downlink access point networks. While the corresponding delay-constrained Shannon capacity remains an open problem (no existing analysis tools can be directly applied), this work focuses on linear codes and proposes three new definitions of delay-constrained throughput based on different outage metrics: the file-based, the rank-based, and the packet-based ones. It then fully characterizes the corresponding linear coding capacity regions for relatively-short-delay flows - flows for which the delay requirement is no larger than the interval of file arrivals.

This paper studies the capacity region when three nodes {1, 2,3} communicate with each other by sending packets through unreliable wireless medium. For each time slot, with some probabilities a packet sent by node i may be received by both of the other nodes j and k; received only by node j (or node k); or received by neither node. Interference is avoided by enforcing that at most one node can transmit in each time slot. We assume that node i can always reach node j, possibly with the help of the third node k, for any i ≠ j pairs (thus the term fully connected). One notable example of this model is any CSMA-based Wi-Fi network with three nodes within the hearing range of each other. We consider the most general traffic demands possible in this setting. Namely, there are six private-information flows with rates (R1→2, R1→3, R2→1, R2→3, R3→1, R3→2), respectively, and three common-information flows with rates (R1→23, R2→31, R3→12), respectively. We characterize the 9-dimensional Shannon capacity region within a gap that is inversely proportional to the packet size (bits). The gap can be attributed to exchanging reception status (ACK/NACK) and can be further reduced to zero if we allow such feedbacks to be transmitted via a separate control channel. For normal-sized packets, say 12000 bits, our results effectively characterize the capacity region for many important scenarios, e.g., wireless access-point networks with client-to-client cooperative communications, and wireless two-way relay networks with packet-level coding and processing. Technical contributions of this paper include a new converse for many-to-many network communications and a new capacity-approaching scheme based on simple linear network coding operations.

This paper studies an optimal channel assignment problem for passive monitoring in multi-channel wireless networks, where a set of sniffers capture and analyze the network traffic to monitor the wireless network. The objective of this problem is to maximize the total amount of traffic captured by sniffers by judiciously assigning the radios of sniffers to a set of channels. This problem is NP-hard, with the computational complexity growing exponentially with the number of sniffers. We develop distributed online solutions for large-scale and dynamic networks. The dynamism in the network may arise from mobility of the nodes being monitored. Our algorithm is guaranteed to achieve at least 1 - 1/e times the optimum, regardless of the network topology and the channel assignment of nodes to be monitored, while providing a distributed solution amenable to online implementation. Further, our algorithm is cost-effective, in terms of communication and computational overheads, due to the use of purely local communication and the incremental adaptation to network changes. We present two operational modes of our algorithm for two types of networks that change at different rates; one is a proactive mode for fast-varying networks, while the other is a reactive mode for slowly-varying networks. Simulation results demonstrate the effectiveness of the two modes of our algorithm and compare it to the theoretically optimal algorithm.

Locally rapairable codes (LRCs) are ingeniously designed distributed storage codes with a (usually small) bounded number of helper nodes participating in repair. Since most existing LRCs assume exact repair and allow full exchange of the stored data (β = α), they can be viewed as a generalization of the traditional erasure codes (ECs) with a much desired feature of local repair. However, it also means that they lack the features of functional repair and partial information-exchange (β < α) in the original regenerating codes (RCs). Motivated by the significant bandwidth (BW) reduction of RCs over ECs, existing works by Ahmad et al and by Hollmann studied “locally repairable regenerating codes (LRRCs)” that simultaneously admit all three features: local repair, partial information-exchange, and functional repair. Significant BW reduction was observed. One important issue for any local repair schemes (including both LRCs and LRRCs) is that sometimes designated helper nodes may be temporarily unavailable, the result of multiple failures, degraded reads, or other network dynamics. Under the setting of LRRCs with temporary node unavailability, this work studies the impact of different helper selection methods. It proves, for the first time in the literature, that with node unavailability, all existing methods of helper selection, including those used in RCs and LRCs, are strictly repair-BW suboptimal. For some scenarios, it is necessary to combine LRRCs with a new helper selection method, termed dynamic helper selection, to achieve optimal BW. This work also compares the performance of different helper selection methods and answers the following fundamental question: whether one method of helper selection is intrinsically better than the other? for various different scenarios.

This work considers the fully-connected 3-node packet erasure network: For each time slot, with some probabilities a packet sent by any node i may be received by both of the other nodes j and k; received only by node j (or node k); or received by neither nodes. Interference is avoided by enforcing that at most one node can transmit in each time slot. We assume that node i can always reach node j, possibly with the help of the third node k, for any i ≠ j pairs (thus the term fully-connected). One example of this model is any Wi-Fi network with 3 nodes within the hearing range of each other. We consider the most general traffic demands. Namely, there are six private-information flows with rates (R1→2,R1→3,R2→1, R2→3,R3→1,R3→2), respectively, and three common-information flows with rates (R1→23,R2→31,R3→12), respectively. We characterize the 9-dimensional Shannon capacity region within a gap that is inversely proportional to the packet size (bits). The gap can be attributed to exchanging reception status (ACK) and can be further reduced to 0 if we allow ACK to be transmitted via a separate control channel. For normal-sized packets, say 12000 bits, our results have thus effectively characterized the capacity region. Technical contributions of this work include a new converse for many-to-many network communications and a new capacity-approaching simple linear network coding scheme.

Coded caching can exploit new multicast opportunities even when multiple users request different pieces of content, and thus can significantly reduce the backhaul requirement for serving high-volume content. However, existing studies of coded caching have been limited to the scenarios where all files of interest are of a common size. This work studies the performance limits of coded caching when the file sizes are different. We derive a new lower bound and an achievable upper bound for the worst-case transmission rate under coded caching, and show that these two bounds differ by at most a Θ(log K) factor, where K is the number of users in the system. There are two key novelties in our analysis. First, our lower bound is derived by considering a new cut-set bound where larger files are requested more times. The analysis of this new cut-set bound requires careful concatenation of several entropy inequalities. Compared to a lower bound using standard cut-set arguments, our lower bound is improved by a Θ(log K) factor. Second, our achievable scheme uses a caching probability that increases proportionally with the file size. Compared to schemes that use a common caching probability, the achievable rate of our scheme is reduced by a Θ K/logk2factor.

Linear coding schemes have been the main choice of coding for the additive white Gaussian noise broadcast channel (AWGN-BC) with noiseless feedback in the literature. The achievable rate regions of these schemes go well beyond the capacity region of the AWGN-BC without feedback. In this paper, a concatenated coding design for the K-user AWGN-BC with noisy feedback is proposed that relies on linear schemes as inner codes to achieve rate tuples outside the no-feedback capacity region. The boundary of an achievable rate region of purely linear coding schemes for noiseless feedback is shown to be arbitrarily closely approached by the concatenated coding scheme for sufficiently small feedback noise levels. Then, a linear coding scheme for the K-user symmetric AWGN-BC with noisy feedback is presented and optimized for use in the concatenated coding scheme. For noiseless feedback, the presented linear coding scheme achieves the optimal sum-rate of linear-feedback coding. An upper bound on the inner code blocklength needed to achieve a sum-rate above no-feedback sum-capacity is derived.

This paper considers the downlink traffic from a base station to two different clients. Assuming infinite backlog, it is known that inter-session network coding (INC) can significantly increase the throughput of each flow. However, the corresponding scheduling solution (assuming dynamic arrivals and requiring bounded delay) is still nascent. For the 2-flow downlink scenario, we propose the first opportunistic INC + scheduling solution that is provably optimal for time-varying channels, i.e., the corresponding stability region matches the optimal linear-INC capacity. To that end, we first introduce a new binary INC operation, which is distinctly different from the traditional wisdom of XORing two overheard packets. We then develop a queue-length-based scheduling scheme, which, with the help of the new INC operation, can robustly and optimally adapt to time-varying channel quality. A byproduct of our results is a scheduling scheme for stochastic processing networks (SPNs) with random departure. The new SPN results relax the previous assumption of deterministic departure, a major limitation of the existing SPN model, by considering stochastic packet departure behavior, and could further broaden the applications of SPN scheduling to other real-world scenarios.

Consider the k-unicast network coding problem over an acyclic wireline network: Given a rate vector k-tuple, determine whether the network of interest can support k unicast flows with those rates. It is well known that the one-unicast problem is easy and that it is solved by the celebrated max-flow min-cut theorem. The hardness of k-unicast problems with small k has been an open problem. We show that the two-unicast problem is as hard as any k-unicast problem for k ≥ 3. Our result suggests that the difficulty of a network coding instance is related more to the magnitude of the rates in the rate tuple than to the number of unicast sessions. As a consequence of our result and other well-known results, we show that linear coding is insufficient to achieve capacity, and non-Shannon inequalities are necessary for characterizing capacity, even for two-unicast networks.

We consider a delay-constrained unicast scenario, where a source node streams perishable information to a destination node over a directed acyclic graph subject to a delay constraint. Transmission along any edge incurs unit delay, and we require that every information bit generated at the source in the beginning of time t to be received and recovered by the destination in the end of time t + D - 1 where D > 0 is the maximum allowed communication delay. We study the corresponding delay-constrained (d-cn) unicast capacity problem. When only routing is allowed, [Ying, et al. 2011] showed that the aforementioned d-cn unicast routing capacity can be characterized and computed efficiently. However, the d-cn capacity problem changes completely when network coding (NC) is allowed. In this work, we construct the first example showing that NC can achieve strictly higher d-cn throughput than routing even for the single unicast setting and the NC gain can be arbitrarily close to 2 in some instances. This is in sharp contrast to the delay-unconstrained (D → ∞) single-unicast case where the classic min-cut/max-flow theorem implies that coding cannot improve throughput over routing. Finally, we propose a new upper bound on the d-cn unicast NC capacity and elaborate its connections to the existing routing-based results [Ying, et al. 2011]. Overall, our results suggest that d-cn communication is fundamentally different from the well-understood delay-unconstrained one and call for investigation participation.

This paper studies the capacity of the two-receiver multiple-input broadcast packet erasure channels (PECs) with channel output feedback, which is in contrast with the single-input setting of the existing works. Motivated by the immense success of linear network coding (LNC) in theory and in practice, this paper first focuses on LNC schemes and characterizes the LNC feedback capacity region of two-receiver multiple-input broadcast PECs. A new linear-space-based approach is proposed, which unifies the problems of finding a capacity outer bound and devising the achievability scheme into a single linear programming problem. In particular, an LP solver is used to exhaustively search for the LNC scheme(s) with the best possible throughput, the result of which is thus guaranteed to attain the LNC feedback capacity. It is then proven by pure algebraic arguments that the LNC capacity region matches a simple capacity region outer bound, which proves that the derived LNC capacity region is indeed the true capacity. A byproduct of the above results is a complete LNC capacity region characterization for two-receiver partially Markovian and partially controllable broadcast PECs.

This work considers a commonly encountered wireless transmission scenario. The base station s would like to send two independent packet streams to clients d1and d2, respectively. For each time slot, only one of the three nodes {s, d1, d2} can transmit a packet and the packet will be heard by a random subset of the other two nodes. We are interested in the corresponding capacity region (R1*, R2*). Such a setting can also be viewed as allowing receiver coordination for the s-to-{d1, d2} broadcast erasure channel with a critical feature that any coordination/transmission between d1and d2also takes away the precious time resources from s. With the exclusive focus on linear network coding (LNC) with causal packet acknowledgement feedback, this work characterizes the exact LNC capacity region with arbitrary security requirement, i.e, the system designer can decide for each di, respectively, whether the corresponding (s, di)-flow needs to be secure or not. The results show that for any channel parameters and any security requirement, the LNC capacity can always be achieved either by the XOR-in-the-air LNC scheme, or by random LNC, or by time-sharing between the two.

This paper studies the optimal sniffer-channel assignment for reliable monitoring in multi-channel wireless networks. This problem concerns how to deploy certain sniffers in a network (and tune their channels) so that they can overhear and verify communication among the other nodes, referred to as normal nodes. Prior works have studied the optimal sniffer-channel assignment, but they assume perfect sniffers. However, in practice, sniffers may probabilistically make errors in monitoring, e.g., due to poor reception and compromise by an adversary. Hence, to maintain acceptable monitoring quality, a node needs to be overheard by multiple sniffers. We show that the optimal sniffer-channel assignment with sniffer redundancy differs fundamentally from the previous works due to the absence of a desirable property called submodularity. As a result, in our problem, the prior approximation algorithms no longer maintain their performance guarantees. We propose a variety of approximation algorithms based on two approaches-greedy strategy and relaxation-and-rounding approach. We present an empirical performance analysis of the proposed algorithms through simulations in practical networks. Our results suggest that our two algorithms show a performance trade-off between coverage and running time and are therefore suitable for different kinds of deployment.

This paper characterizes the full capacity region of the COPE principle for 2-flow wireless butterfly networks with broadcast packet erasure channels (PECs). The capacity results in this paper allow for random overhearing with arbitrary overhearing probabilities, arbitrary scheduling policies, network-wide channel state information (CSI) feedback after each transmission, and potential use of nonlinear network codes. An information-theoretic outer bound is derived that takes into account the delayed CSI feedback of the underlying broadcast packet erasure channels. For the achievability, this paper proposes a new class of linear network codes, named as the space-based linear network coding (SBLNC), that achieves the capacity outer bound. Further, the proposed outer and inner bounds are later generalized for the setting in which a transmission may be heard by its 2-hop neighbor(s), the so-called opportunistic routing scenario. When allowing the possibility of opportunistic routing, the proposed inner and outer bounds do not always meet. Numerical experiments, however, show that the relative gap of the two bounds is less than 0.08% in average. The proposed bounds thus tightly bracket the capacity region even when combining the COPE principle with opportunistic routing.

Quantifying the end-to-end delay performance in multihop wireless networks is a well-known challenging problem. In this paper, we propose a new joint congestion control and scheduling algorithm for multihop wireless networks with fixed-route flows operated under a general interference model with interference degree K. Our proposed algorithm not only achieves a provable throughput guarantee (which is close to at least 1/K of the system capacity region), but also leads to explicit upper bounds on the end-to-end delay of every flow. Our end-to-end delay and throughput bounds are in simple and closed forms, and they explicitly quantify the tradeoff between throughput and delay of every flow. Furthermore, the per-flow end-to-end delay bound increases linearly with the number of hops that the flow passes through, which is order-optimal with respect to the number of hops. Unlike traditional solutions based on the back-pressure algorithm, our proposed algorithm combines window-based flow control with a new rate-based distributed scheduling algorithm. A key contribution of our work is to use a novel stochastic dominance approach to bound the corresponding per-flow throughput and delay, which otherwise are often intractable in these types of systems. Our proposed algorithm is fully distributed and requires a low per-node complexity that does not increase with the network size. Hence, it can be easily implemented in practice.

The error floor performance of a low-density parity-check (LDPC) code is highly related to the presence of error-prone substructures (EPSs). In general, existing characterizations of the EPSs are inspired by the LDPC decoding behavior under simple binary erasure channel (BEC) and binary symmetric channel (BSC) models. In this work, we first introduce a new class of EPSs: the 1-shot EPSs and static EPSs for the binary-input ternary-output channel (BITOC). By focusing on BITOCs, which are a step closer to additive white Gaussian channels (AWGNC), the proposed EPS would better characterize the decoding behavior of the AWGNC than the existing BEC-or BSC-based definitions. We then develop an efficient search algorithm that can exhaustively enumerate all small BITOC EPSs. The new exhaustive algorithm enables us to order the harmfulness of the EPSs and distinguish within a given EPS which bits are more prone to what types of errors. The proposed algorithm can also be regarded as a unified search method for the existing EPSs such as cycles, codewords, stopping sets, and fully absorbing sets. The proposed methodology is potentially generalizable to the binary-input m-ary output channel.

This paper studies an optimal channel assignment problem for passive monitoring in multi-channel wireless networks, where a set of sniffers capture and analyze the network traffic to monitor the network. The objective of this problem is to maximize the total amount of traffic captured by sniffers by judiciously assigning the radios of sniffers to a set of channels. This problem is NP-hard, with the computational complexity growing exponentially with the number of sniffers. We develop distributed online solutions to this problem for large-scale and dynamic networks. Prior works have attained a constant factor equation of the maximum monitoring coverage in a centralized setting. Our algorithm preserves the same ratio while providing a distributed solution that is amenable to online implementation. Also, our algorithm is cost-effective, in terms of communication and computational overheads, due to the use of only local communication and the adaptation to incremental network changes. We present two operational modes of our algorithm for two types of networks that have different rates of network changes. One is a proactive mode for fast varying networks, while the other is a reactive mode for slowly varying networks. Simulation results demonstrate the effectiveness of the two modes of our algorithm.

This work studies the capacity of the 2-receiver multiple-input/multiple-output (MIMO) broadcast packet erasure channels (PECs) with channel output feedback, which is in contrast with the single-input/single-output setting of the existing works. Motivated by the immense success of linear network coding (LNC) in theory and in practice, this work focuses exclusively on LNC schemes and characterizes the LNC feedback capacity region (R1*, R2*) of 2-receiver MIMO broadcast PECs. A new linear-space-based approach is proposed, which unifies the problems of finding a capacity outer bound and devising the achievability scheme into a single linear programming (LP) problem. Specifically, an LP solver is used to exhaustively search for the LNC scheme(s) with the best possible throughput, the result of which is thus guaranteed to attain the LNC feedback capacity.

This work considers a commonly encountered wireless transmission scenario: Two nearby 1-hop flows s1→ d1and s2→ d2are within the transmission range of each other. The network nodes thus have to share the time resources, which limits the sum-rate performance. On the other hand, both siand dican (occasionally) overhear the transmission of the other pair (sj, dj) for all i ≠ j, which opens up the opportunity of using network coding (NC) and ACK/NACK to improve the throughput. The key challenge, however, is that any dedicated communication between s1and s2also consumes the precious time resources. Hence NC coordination must be achieved through unreliable overhearing. In this work, the above scenario is modeled as four wireless nodes interconnected by broadcast erasure channels with channel state feedback. The corresponding capacity region (R1,R2) is fully characterized for the setting of symmetric, spatially independent erasure channels.

A primary challenge in exploiting Cognitive Radio Networks (CRNs), known as the rendezvous problem, is for the users to find each other in the dynamic open spectrum. We study blind rendezvous, where users search for each other without any infrastructural aid. Previous work in this area have focused on efficient blind rendezvous algorithms for two users but the solution for multiple users is still far from optimal. In particular, when two users encounter, one user inherits the other's hopping sequence but the sequence is never shortened or split among the encountering users. We denote this class of algorithms as uncoordinated channel hopping algorithms. In this paper, we introduce a new class of distributed algorithms for multi-user blind rendezvous, called Coordinated Channel Hopping (CCH), where users adjust, or coordinate, the sequence of channels being hopped as they rendezvous pairwise. Compared to existing rendezvous algorithms, our algorithms achieve 80% lower Time To Rendezvous (TTR) in case of multiple users.

This work provides an efficient exhaustive search algorithm for finding all small fully absorbing sets (FASs) of any arbitrary low-density parity-check (LDPC) code. The proposed algorithm is based on the branch-&-bound principle for solving NP-complete problems. In particular, given any LDPC code, the problem of finding all FASs of size less than t is formulated as an integer programming problem, for which a new branch-&-bound algorithm is devised with new node selection and tree-trimming mechanisms. The resulting algorithm is capable of finding all FASs of size <; 7 for LDPC codes of length <; 1000. When limiting the FASs of interest to those with the number of violated parity-check nodes <; 3, the proposed algorithm is capable of finding all such FASs of size <; 14 for LDPC codes of lengths <; 1000. The resulting exhaustive list of small FASs is then used to devise a new efficient post-processing low-error floor LDPC decoder. The numerical results show that by exploiting the exhaustive list of small FASs, the proposed post-processing decoder can significantly lower the error-floor performance of a given LDPC code. For various example codes of length <; 3000, the proposed post-processing decoder lowers the error floor by a couple of orders of magnitude when compared to the standard belief propagation decoder and by an order of magnitude when compared to other existing low error-floor decoders.

This paper focuses on the 1-to-$K$broadcast packet erasure channel (PEC), a generalization of the broadcast binary erasure channel from the binary symbol to a finite field$\mathop{\ssr GF}(q)$with sufficiently large$q$. We consider the setting in which the source node has instant feedback of the channel outputs of the$K$receivers after each transmission. The main results of this paper are: (i) The capacity region for general 1-to-3 broadcast PECs and (ii) The capacity region for two types of 1-to-$K$broadcast PECs: the symmetric PECs, and the spatially independent PECs with one-sided fairness constraints. This paper also develops (iii) A pair of outer and inner bounds of the capacity region for arbitrary 1-to-$K$broadcast PECs, which can be easily evaluated by any linear programming solver. The proposed inner bound is proven by a new class of intersession network coding schemes, termed the packet evolution schemes, which is based on the concept of code alignment in$\mathop{\ssr GF}(q)$that is in parallel with the interference alignment techniques for the Euclidean space. Extensive numerical experiments show that the outer and inner bounds meet for almost all broadcast PECs encountered in practical scenarios and thus effectively bracket the capacity of general 1-to-$K$broadcast PECs with COF.

Motivated by practical wireless network protocols, this paper focuses on wireless intersession network coding (INC) over a 1-hop neighborhood, of which the exact capacity region remains an open problem. Towards better understanding of the capacity, this work first models the wireless overhearing events by broadcast packet erasure channels that are memoryless and stationary. Since most INC gain is resulted from destinations overhearing packets transmitted by other sources, this work then focuses exclusively on the 2-staged INC schemes, which fully capture the throughput benefits of overheard message side information (MSI) through the use of one-time feedback but refrain from exploiting the broadcast spatial diversity gain of channel output feedback. Under this setting, a capacity outer bound is provided for any number ofMcoexisting unicast sessions. For the special cases ofM≤ 3, it is shown that the outer bound can be achieved and is indeed the capacity. To quantify the tightness of the outer bound forM≥ 4, a capacity inner bound for generalMis provided. Both the outer and inner bounds can be evaluated by any linear programming solver. Numeric results show that for 4 ≤M≤ 5 with randomly chosen channel parameters, the difference between the outer and inner bounds is within 1% for 96.7% of the times. Focusing exclusively on the benefits of MSI, the results in this paper can also be viewed as the generalization of index-coding capacity from wireline broadcast with binary alphabets to wireless broadcast with high-order alphabets.

In contrast to unicast routing, high-throughput reliable multicast routing in wireless mesh networks (WMNs) has received little attention. There are two primary challenges to supporting high-throughput, reliable multicast in WMNs. The first is no different from unicast: Wireless links are inherently lossy due to varying channel conditions and interference. The second, known as the “crying baby” problem, is unique to multicast: The multicast source may have varying throughput to different multicast receivers, and hence trying to satisfy the reliability requirement for poorly connected receivers can potentially result in performance degradation for the rest of the receivers. In this paper, we propose Pacifier, a new high-throughput, reliable multicast protocol for WMNs. Pacifier seamlessly integrates four building blocks-namely, tree-based opportunistic routing, intraflow network coding, source rate limiting, and round-robin batching-to support high-throughput, reliable multicast routing in WMNs, while at the same time it effectively addresses the “crying baby” problem. Our experiments on a 22-node IEEE 802.11 WMN testbed show that Pacifier increases the average throughput over a state-of-the-art reliable network coding-based protocol MORE by up to 144%, while at the same time it solves the “crying baby” problem by improving the throughput of well-connected receivers by up to a factor of 14.

A primary challenge in multi casting video in a wireless LAN to multiple clients is to deal with the client diversity -- clients may have different channel characteristics and hence receive different numbers of transmissions from the AP. A promising approach to overcome this problem is to combine multi-resolution (layered) video coding with interlayer network coding. The fundamental challenge in such an approach is to determine the strategy of coding the packets across different layers that maximizes the number of decoded layers at all clients. This paper makes three contributions. (1) We first show that even for one client, the previously proposed canonical triangular scheme for inter-layer network coding can perform poorly. We show how to enhance the triangular scheme by incorporating the estimated target number of layers which significantly improves its effectiveness. (2) We show that such an enhanced triangular scheme still performs poorly for multiple clients with diverse channel characteristics, which motivates the need for searching for the optimal coding strategy. The naive way of searching for the optimal strategy is computationally prohibitive. We present several optimizations that drastically reduce the complexity of exhaustively searching for the optimal strategy, making it feasible in real time. (3) Finally, we design and evaluate an on line video delivery scheme, Percy, to be deployed at a proxy behind the AP of a wireless LAN. Our simulation results show that Percy outperforms the previous inter-layer coding heuristic by up to 22-80% with varying numbers of clients.

We consider the problem of designing a joint congestion control and scheduling algorithm for multihop wireless networks. The goal is to maximize the total utility and achieve low end-to-end delay simultaneously. Assume that there are M flows inside the network, and each flow m has a fixed route with Hmhops. Further, the network operates under the one-hop interference constraint. We develop a new congestion control and scheduling algorithm that combines a window-based flow control algorithm and a new distributed rate-based scheduling algorithm. For any ϵ, ϵm∈ (0, 1), by appropriately choosing the number of backoff mini-slots for the scheduling algorithm and the window-size of flow m, our proposed algorithm can guarantee that each flow m achieves throughput no smaller than rm(1 - ϵ)(1 - ϵm), where the total utility of the rate allocation vector r⃗ = [rm] is no smaller than the total utility of any rate vector within half of the capacity region. Furthermore, the end-to-end delay of flow m can be upper bounded by Hm/(rm(1 - ϵ)ϵm). Since a flow-m packet requires at least Hmtime slots to reach the destination, the order of the per-flow delay upper bound is optimal with respect to the number of hops. To the best of our knowledge, this is the first fully-distributed joint congestion-control and scheduling algorithm that can guarantee order-optimal per-flow end-to-end delay and utilize close-to-half of the system capacity under the one-hop interference constraint. The throughput and delay bounds are proved by a novel stochastic dominance approach, which could be of independent value and be extended to general interference constraints. Our algorithm can be easily implemented in practice with a low per-node complexity that does not increase with the network size.

This work studies the capacity of 2-user 1-hop relay networks, for which the sources, destinations, and the common relay are interconnected by broadcast packet erasure channels. In contrast with the existing results, this paper allows (i) transmission from a source being heard directly by its 2-hop-away destination, the so-called opportunistic routing scenario, (ii) instant channel status feedback among all network nodes, and (iii) per-slot scheduling decisions that are functions of the traffic loads and the past channel status. A new pair of inner and outer bounds is provided, and a condition is identified for the scenario in which the bounds coincide. Numerical experiments show that for commonly encountered scenarios, the gap between the inner and the outer bounds is less than 0.2%, which demonstrates the effectiveness of the proposed bounding techniques.

Random linear network coding (RLNC) is widely used in practical network coding (NC) protocol design. Recent results show that RLNC also plays an important role in capacity-achieving intersession NC schemes for erasure-based 1-hop relay networks. This work quantifies the common information of RLNC over a 1-hop broadcast packet erasure channel. Several potential applications are discussed, including source coding, intersession NC, and broadcasting with common and private information.

A primary challenge in multicasting video in a wireless LAN is to deal with the client diversity -- clients may have different channel characteristics and hence receive different numbers of transmissions from the AP. A promising approach to overcome this problem is to combine scalable video coding techniques such as MRC or MDC, which divide a video stream into multiple substreams, with inter-layer network coding. The fundamental challenge in such an approach is to determine the strategy of coding the packets across different layers that maximizes the number of decoded layers at all clients. In [7], the authors showed that inter-layer NC indeed helps the delivery of MRC coded media over the WiFi, and proposed how to efficiently search for the optimal coding strategies online.

Multimedia streaming applications have stringent Quality-of-Service (QoS) requirements. Typically, each packet is associated with a packet delivery deadline. This work models and considers streaming broadcast of stored video over the downlink of a single cell. We first generalize the existing class of immediately-decodable network coding (IDNC) schemes to take into account the deadline constraints. The performance analysis of IDNC schemes are significantly complicated by the packet deadline constraints (from the application layer) and the immediate-decodability requirement (from the network layer). Despite this difficulty, we prove that for independent channels, the IDNC schemes are asymptotically throughput-optimal subject to the deadline constraints when there are no more than three users and when the video file size is sufficiently large. The deadline-constrained throughput gain of IDNC schemes over non-coding scheme is also explicitly quantified. Numerical results show that IDNC schemes strictly outperform the non-coding scheme not only in the asymptotic regime of large files but also for small files. Our results show that the IDNC schemes do not suffer from the substantial decoding delay that is inherent to existing generation-based network coding protocols.

We consider practical schemes for binary dirty-paper channels and broadcast channels (BCs) with two receivers and varying channel quality. With the BC application in mind, this paper proposes a new design for binary dirty paper coding (DPC). By exploiting the concept of coset binning, the complexity of the system is greatly reduced when compared to the existing works. Some design challenges of the coset binning approach are identified and addressed. The proposed binary DPC system achieves similar performance to the state-of-the-art, superposition-coding-based system while demonstrating significant advantages in terms of complexity and flexibility of system design. For binary BCs, achieving the capacity generally requires the superposition of a normal channel code and a carefully designed channel code with non-uniform bit distribution. The non-uniform bit distribution is chosen according to the channel conditions. Therefore, to achieve the capacity for binary BCs with varying channel quality, it is necessary to use quantization codes of different rates, which significantly increases the implementation complexity. In this paper, we also propose a broadcast scheme that generalizes the concept of binary DPC, which we term soft DPC. By combining soft DPC with time sharing, we achieve a large percentage of the capacity for a wide range of channel quality with little complexity overhead. Our scheme uses only one fixed pair of codes for users 1 and 2, and a single quantization code, which possesses many practical advantages over traditional time sharing and superposition coding solutions and provides strictly better performance.

The use of random linear network coding (NC) has significantly simplified the design of opportunistic routing (OR) protocols by removing the need of coordination among forwarding nodes for avoiding duplicate transmissions. However, NC-based OR protocols face a new challenge: How many coded packets should each forwarder transmit? To avoid the overhead of feedback exchange, most practical existing NC-based OR protocols compute offline the expected number of transmissions for each forwarder using heuristics based on periodic measurements of the average link loss rates and the ETX metric. Although attractive due to their minimal coordination overhead, these approaches may suffer significant performance degradation in dynamic wireless environments with continuously changing levels of channel gains, interference, and background traffic. In this paper, we propose CCACK, a new efficient NC-based OR protocol. CCACK exploits a novel Cumulative Coded ACKnowledgment scheme that allows nodes to acknowledge network-coded traffic to their upstream nodes in a simple way, oblivious to loss rates, and with negligible overhead. Through extensive simulations and testbed experiments, we show that CCACK greatly improves both throughput and fairness compared to MORE, a state-of-the-art NC-based OR protocol.

The use of random linear network coding (NC) has significantly simplified the design of opportunistic routing (OR) protocols by removing the need of coordination among forwarding nodes for avoiding duplicate transmissions. However, NC-based OR protocols face a new challenge: How many coded packets should each forwarder transmit? To avoid the overhead of feedback exchange, most practical existing NC-based OR protocols compute offline the expected number of transmissions for each forwarder using heuristics based on periodic measurements of the average link loss rates and the ETX metric. Although attractive due to their minimal coordination overhead, these approaches may suffer significant performance degradation in dynamic wireless environments with continuously changing levels of channel gains, interference, and background traffic. In this paper, we propose CCACK, a new efficient NC-based OR protocol. CCACK exploits a novel Cumulative Coded ACKnowledgment scheme that allows nodes to acknowledge network coded traffic to their upstream nodes in a simple way, oblivious to loss rates, and with practically zero overhead. In addition, the cumulative coded acknowledgment scheme in CCACK enables an efficient credit-based, rate control algorithm. Our evaluation shows that, compared to MORE, a state-of-the-art NC-based OR protocol, CCACK improves both throughput and fairness, by up to 20× and 124%, respectively, with average improvements of 45% and 8.8%, respectively.

Multimedia streaming applications have stringent QoS requirements. Typically each packet is associated with a packet delivery deadline. This work models and considers real-time streaming broadcast for stored-video over the downlink of a single cell. The broadcast capacity of the system subject to deadline constraints are derived for both uncoded and coded wireless broadcast schemes. Even under the deadline requirements, it is shown in this work that network coding is asymptotically throughput-optimal and can strictly outperform the best non-coding policy by analytically quantifying the optimal capacity when the file size is sufficiently large. A simple network coding policy is also proposed that achieves the asymptotic capacity while maintaining finite transmission delay (queueing + decoding delay). A new temporal-queue-length-based Lyapunov function is used to prove the optimality of this policy. Simulation shows that the simple coding policy outperforms the best non-coding policies even for broadcasting files of small sizes.

This work provides an exhaustive search algorithm for finding small fully absorbing sets (FASs) of arbitrary low-density parity-check (LDPC) codes. In particular, given any LDPC code, the problem of finding all FASs of size less than t is formulated as an integer programming problem, for which a new branch-&-bound algorithm is devised. New node selection and the tree-trimming mechanisms are designed to further enhance the efficiency of the algorithm. The proposed algorithm is capable of finding all FASs of size ≤ 11 with no larger than 2 induced odd-degree check nodes for LDPC codes of length ≤ 1000. The resulting exhaustive list of small FASs is then used to devise a new post-processing decoder. Numerical results show that by taking advantage of the exhaustive list of small FASs, the proposed decoder significantly lowers the error floor for codes of practical lengths and outperforms the state-of-the-art low-error-floor decoders.

Motivated by practical wireless network protocols, this paper answers the following questions: Exactly (or at most) how much throughput improvement one can expect from intersession network coding (INC) in a 1-hop neighborhood over non-coding solutions; and how to achieve (or approach) the capacity. Focusing on a two-stage setting, this work first provides a capacity outer bound for any number of M coexisting unicast sessions and any overhearing events modeled by broadcast packet erasure channels that are time-wise independently and identically distributed. For M ≤ 3, it is shown that the outer bound meets the capacity. To quantify the tightness of the outer bound for M ≥ 4, a capacity inner bound for general M is provided. Both bounds can be computed by a linear programming solver. Numeric results show that for 4 ≤ M ≤ 5 with randomly chosen channel parameters, the difference between the outer and inner bounds is within 1% for 99.4% of the times. The results in this paper can also be viewed as the generalization of index-coding capacity from wireline broadcast with binary alphabets to wireless broadcast with high-order alphabets.

This work explores new graph-theoretic and algebraic behaviors of network codes and provides a new class of coding-based, distributed max-flow algorithms. The proposed algorithm starts from broadcasting the coded packets, followed by continuously trimming the redundant traffic that does not constitute themaximum flowof the network information. The convergence speed of the proposed algorithms is no slower than that of the existing push-&-relabel max-flow algorithms. The algorithmic results in this work also possess several unique features that are especially suitable for practical network implementation with low control, communication, and complexity overhead.

When there exists only a single multicast session in a directed acyclic/cyclic network, the existence of a network coding solution is characterized by the classic min-cut/max-flow theorem. For the case of more than one coexisting sessions, network coding also demonstrates throughput improvement over noncoded solutions. This paper proposes pairwise intersession network coding, which allows for arbitrary directed networks but restricts the coding operations to being between two symbols (for acyclic networks) or between two strings of symbols (for cyclic networks). A graph-theoretic characterization of pairwise intersession network coding is proven based on paths with controlled edge-overlap. This new characterization generalizes the edge-disjoint path characterization of noncoded network communication and includes the well-studied butterfly graph as a special case. Based on this new characterization, various aspects of pairwise intersession network coding are studied, including the sufficiency of linear codes, the complexity of identifying coding opportunities, its topological analysis, and bandwidth- and coding-efficiency.

In this paper, we develop a distributed rate-control algorithm for networks with multiple unicast sessions when network coding is allowed across different sessions. Building on recent flow-based characterization ofpairwise intersession network coding, the corresponding optimal rate-control problem is formulated as a convex optimization problem. The formulation exploits pairwise coding possibilities between any pair of sessions, where any coded symbol is formed by coding over at most two original symbols. The objective function is the sum of the utilities based on the rates supported by each unicast session. Working on the Lagrangian of the formulated problem, a distributed algorithm is developed with little coordination among intermediate nodes. Each unicast session has the freedom to choose its own utility function. The only information exchange required by the source is the weighted sum of the queue length of each link, which can be piggybacked to the acknowledgment messages. In addition to the optimal rate-control algorithm, we propose a decentralizedpairwise random codingscheme that decouples the decision of coding from that of rate control, which further enhances the distributiveness of the proposed scheme. The convergence of the rate-control algorithm is proven analytically and verified by extensive simulations. Simulation results also demonstrate the advantage of the proposed algorithm over the state-of-the-art in terms of both throughput and fairness.

In contrast to unicast routing, high-throughput reliable multicast routing in wireless mesh networks (WMNs) has received little attention. There are two primary challenges to supporting high-throughput, reliable multicast in WMNs. The first is no different from unicast: wireless links are inherently lossy due to varying channel conditions and interference. The second, known as the "crying baby" problem, is unique to multicast: the multicast source may have varying throughput to different multicast receivers, and hence trying to satisfy the reliability requirement for poorly connected receivers can potentially result in performance degradation for the rest of the receivers. In this paper, we propose Pacifier, a new high-throughput reliable multicast protocol for WMNs. Pacifier seamlessly integrates four building blocks, namely, tree-based opportunistic routing, intra-flow network coding, source rate limiting, and round-robin batching, to support high-throughput, reliable multicast routing in WMNs, while at the same time effectively addresses the "crying baby" problem. Our evaluations show that Pacifier increases the average throughput over a practical, state-of-the-art reliable network coding-based protocol MORE by 171%, while improving the throughput of well-connected receivers by up to a factor of 20.

Recently, network coding has gained much popularity and several practical routing schemes have been proposed for wireless mesh networks that exploit interflow network coding for improved throughput. However, the evaluation of these protocols either assumed simple topologies and traffic patterns such as opposite flows along a single chain, or small, dense networks which have ample overhearing of each other's transmissions in addition to many overlapping flows. In this paper, we seek to answer the fundamental question: how much performance benefit from network coding can be expected for general traffic patterns in a moderate-sized wireless mesh network? We approach this question via an empirical study of both coordinated and opportunistic coding based protocols subject to general traffic patterns. Our study shows the performance benefits under both types of coding for general traffic patterns are extremely limited. We then analyze and uncover fundamental reasons for the limited performance benefits.

There has been significant recent interest in covert communication using timing channels. In network timing channels, information is leaked by controlling the time between transmissions of consecutive packets. Our work focuses on network timing channels and provides two main contributions. The first is to quantify the threat posed by covert network timing channels. The other is to use timing channels to communicate at a low data rate without being detected. In this paper, we design and implement a covert TCP/IP timing channel. We are able to quantify the achievable data rate (or leak rate) of such a covert channel. Moreover, we show that by sacrificing data rate, the traffic patterns of the covert timing channel can be made computationally indistinguishable from that of normal traffic, which makes detecting such communication virtually impossible. We demonstrate the efficacy of our solution by showing significant performance gains in terms of both data rate and covertness over the state-of-the-art.

In this paper, we develop a fast resource allocation algorithm that takes advantage of intra-session network coding. The algorithm maximizes the total utility of multiple unicast (or multicast) sessions subject to capacity constraints, where packets are coded within each session. Our solution is a primal solution that does not use duality or congestion prices. Thus, it does not require building up queues to achieve the optimal resource allocation. Hence, the queueing delay of the packets can be tightly controlled. The existing primal solution in the literature requires a separate graph-theoretic algorithm to find the min-cut of each session, whose complexity grows quadratically with the total number of nodes. In contrast, we provide a new coded-feedback approach whose complexity grows only linearly with the total number of nodes. More explicitly, by letting the ACK/feedback packets on the return paths also carry coding coefficients as does the forward coded traffic, key network information can be obtained more efficiently, which leads to a fast resource allocation scheme fully integrated with the network coding operation.

We propose a practical scheme for binary dirty-paper channels. By exploiting the concept of random binning instead of superposition coding, the complexity of the system is greatly reduced. For comparison, the existing approaches require one of the native codes to be of non-uniform a priori distribution, which is generally achieved by combining a symbol mapper and high-order-alphabet low-density parity-check (LDPC) codes. Using high-order alphabets increases significantly the complexity and the resulting method is not flexible for designing systems of practical channel parameters. In contrast, we propose to implement the random binning concept using only binary LDPC and binary convolutional codes. In this work, some design challenges of this random binning approach are identified and addressed. Our systems are optimized by the joint use of density evolution (DE) and the extrinsic information transfer (EXIT) analysis. Simulation results using practical Quasi-Cyclic LDPC codes show that our system achieves similar performance to the state-of-the-art, high-order-alphabet LDPC-based systems while demonstrating significant advantages in terms of complexity and flexibility of system design.

For wireless multi-hop networks with unicast sessions, most coding opportunities involve only two or three sessions as coding across many sessions requires greater transmission power to broadcast the coded symbol to many receivers, which enhances interference. This work shows that with a new flow-based characterization of pairwise intersession network coding (coding across two unicast sessions), an optimal joint coding, scheduling, and rate-control scheme can be devised and implemented using only the binary XOR operation. The new scheduling/rate-control scheme demonstrates provably graceful throughput degradation with imperfect scheduling, which facilitates the design tradeoff between the throughput optimality and computational complexity of different scheduling schemes. Our results show that pairwise intersession network coding improves the throughput of non-coding solutions regardless of whether perfect/imperfect scheduling is used. Both the deterministic and stochastic packet arrivals and departures are considered. This work shows a striking resemblance between pairwise intersession network coding and non-coded solutions, and thus advocates extensions of non-coding wisdoms to their network coding counterpart.

It is proven in this work that it is NP-complete to exhaustively enumerate small error-prone substructures in arbitrary, finite-length low-density parity-check (LDPC) codes. Two error-prone patterns of interest include stopping sets for binary erasure channels (BECs) and trapping sets for general memoryless symmetric channels. Despite the provable hardness of the problem, this work provides an exhaustive enumeration algorithm that is computationally affordable when applied to codes of practical short lengthsnap 500. By exploiting the sparse connectivity of LDPC codes, the stopping sets of sizeles13and the trapping sets of sizeles11can be exhaustively enumerated. The central theorem behind the proposed algorithm is a new provably tightupperboundon the error rates of iterative decoding over BECs. Based on a tree-pruning technique, this upper bound can be iteratively sharpened until its asymptotic order equals that of the error floor. This feature distinguishes the proposed algorithm from existing non-exhaustive ones that correspond to findinglowerboundsof the error floor. The upper bound also provides a worst case performance guarantee that is crucial to optimizing LDPC codes when the target error rate is beyond the reach of Monte Carlo simulation. Numerical experiments on both randomly and algebraically constructed LDPC codes demonstrate the efficiency of the search algorithm and its significant value for finite-length code optimization.

There are two primary challenges to supporting high-throughput, reliable multicast in wireless mesh networks (WMNs). The first is no different from unicast: wireless links are inherently lossy due to varying channel conditions and interference. The second, known as the "crying baby" problem, is unique to multicast: the multicast source may have varying throughput to different multicast receivers, and hence trying to satisfy the reliability requirement for poorly connected receivers can potentially result in performance degradation for the rest of the receivers.

In this paper we develop a distributed rate control algorithm for multiple-unicast-sessions when network coding is allowed. Building on our recent flow-based characterization of network coding, we formulate the problem as a convex optimization problem. The formulation exploits pairwise coding possibilities between any pair of sessions, where the objective function is the sum of the utilities based on the rates supported by each session. With some manipulation on the Lagrangian of the formulated problem, a distributed algorithm is developed with no interaction between intermediate nodes, and each source having the freedom to choose its own utility function. The only information required by the source is the weighted sum of the queue length updates of each link, which can be piggy-backed on the acknowledgment messages. In addition to the optimal rate control algorithm, we propose a decentralized pairwise random coding scheme (PRC) that is optimal when a sufficiently large finite field is used for network coding. The convergence of the rate control algorithm is proved analytically and verified by extensive simulations. Simulations also demonstrate the advantage of our algorithm over the state-of-the-art in terms of throughput and fairness.

For a unicast/multicast session, network coding is generally implemented via random coding and broadcasting at intermediate nodes, an especially favorable solution in wireless networks. The corresponding broadcast traffic can be minimized by finding the max (s, t)-flow of the network and by sending packets only along the max flow. All existing algorithms for this task, e.g. the push-&-relabel algorithm, are based on the routing paradigm and do not take advantage of the network coded traffic, which undermines their practicality for network coding applications. This work provides the first network-coding-based max (s, t)-flow algorithm starting from broadcasting the coded packets and followed by continuously trimming the unnecessary traffic. The running time is O(|V|2), asymptotically no slower than that of the existing routing-based, distributed algorithms. Other important features include: (i) Limited exchange of control packets enables straightforward distributed implementation. (ii) The source-sink pair sustains uninterruptedly the optimal max-flow rate throughout iterations. (iii) All control packets are sent in the opposite direction of the data packets and can be readily piggybacked to the acknowledgment packets with minimal overhead. (iv) The control packet contains only easily computed coding coefficients and the algorithm imposes no additional requirement on the intermediate nodes nor on the format of each packet.

Code-division multiple access (CDMA) is the basis of a family of advanced air interfaces in current and future generation networks. The benefits promised by CDMA have not been fully realized partly due to the prohibitive complexity of optimal detection and decoding of many users communicating simultaneously using the same frequency band. From both theoretical and practical perspectives, this paper advocates a new paradigm of CDMA with sparse spreading sequences, which enables near-optimal multiuser detection using belief propagation (BP) with low-complexity. The scheme is in part inspired by capacity-approaching low-density parity-check (LDPC) codes and the success of iterative decoding techniques. Specifically, it is shown that BP-based detection is optimal in the large-system limit under many practical circumstances, which is a unique advantage of sparsely spread CDMA systems. Moreover, it is shown that, from the viewpoint of an individual user, the CDMA channel is asymptotically equivalent to a scalar Gaussian channel with some degradation in the signal-to-noise ratio (SNR). The degradation factor, known as the multiuser efficiency, can be determined from a fixed-point equation. The results in this paper apply to a broad class of sparse, semi-regular CDMA systems with arbitrary input and power distribution. Numerical results support the theoretical findings for systems of moderate size, which further demonstrate the appeal of sparse spreading in practical applications.

This paper studies the problem of estimating the vector input to a sparse linear transformation based on the observation of the output vector through a bank of arbitrary independent channels. The linear transformation is drawn randomly from an ensemble with mild regularity conditions. The central result is a decoupling principle in the large-system limit. That is, the optimal estimation of each individual symbol in the input vector is asymptotically equivalent to estimating the same symbol through a scalar additive Gaussian channel, where the aggregate effect of the interfering symbols is tantamount to a degradation in the signal-to-noise ratio. The degradation is determined from a recursive formula related to the score function of the conditional probability distribution of the noisy channel. A sufficient condition is provided for belief propagation (BP) to asymptotically produce the a posteriori probability distribution of each input symbol given the output. This paper extends the authors' previous decoupling result for Gaussian channels to arbitrary channels, which was based on an earlier work of Montanari and Tse. Moreover, a rigorous justification is provided for the generalization of some results obtained via statical physics methods.

It is well known that queues with exponentially distributed service times have the smallest Shannon capacity among all single-server queues with the same service rate. In this paper, we study the capacity of timing channels in which the service time distributions have bounded support, i.e., Bounded Service Timing Channels (BSTC). We derive an upper bound and two lower bounds on the capacity of such timing channels. The tightness of these bounds is investigated analytically as well as via simulations. We find that the uniform BSTC serves a role for BSTCs that is similar to what the exponential service timing channel does for the case of timing channels with unbounded service time distributions. That is, when the length of the support interval is small, the uniform BSTC has the smallest capacity among all BSTCs.

This paper studies a systematic treatment of trapping sets in finite-length LDPC codes and its related theoretic properties. It is proven that the complexity of deciding the minimal trapping distance is NP-complete. Furthermore, exhausting minimal trapping sets can be achieved by using any good stopping set exhaustion algorithm as a building block. The suppressing effect of cyclic lifting for trapping sets is also studied in this work, which characterizes the probability that a base code trapping sets survives after applying the cyclic lifting technique. The corresponding quantitative knowledge about the origin of small trapping sets in the cyclically lifted codes helps provide definite guidelines for the base code optimization to lower the error-floor over non-erasure channels. Extensive numerical experiments are provided to demonstrate the various techniques discussed in this work.

The problem of network coding with two simple unicast sessions is considered for general directed acyclic graphs. An explicit graph-theoretic characterization is provided for the feasibility of whether two symbols at different sources can be simultaneously transmitted to the designated sinks via network coding. The existence of a routing scheme is equivalent to finding edge-disjoint paths. Similarly, in this paper it is proven that the existence of a network coding scheme is equivalent to finding paths with controlled edge overlaps, and the characterization includes the well-studied butterfly graph as a special case. Various generalizations and implications are discussed based on the constructive nature of the flow-based conditions. For example, it is shown that a linear network coding scheme using only six paths is as effective as any non-linear network coding scheme.

This paper focuses on finite-dimensional upper and lower bounds on decodable thresholds of Zopfmand binary low-density parity-check (LDPC) codes, assuming belief propagation decoding on memoryless channels. A concrete framework is presented, admitting systematic searches for new bounds. Two noise measures are considered: the Bhattacharyya noise parameter and the soft bit value for a maximum a posteriori probability (MAP) decoder on the uncoded channel. For ZopfmLDPC codes, an iterative m-dimensional bound is derived for m-ary-input/symmetric-output channels, which gives a sufficient stability condition for ZopfmLDPC codes and is complemented by a matched necessary stability condition introduced herein. Applications to coded modulation and to codes with nonequiprobably distributed codewords are also discussed. For binary codes, two new lower bounds are provided for symmetric channels, including a two-dimensional iterative bound and a one-dimensional noniterative bound, the latter of which is the best known bound that is tight for binary-symmetric channels (BSCs), and is a strict improvement over the existing bound derived by the channel degradation argument. By adopting the reverse channel perspective, upper and lower bounds on the decodable Bhattacharyya noise parameter are derived for nonsymmetric channels, which coincides with the existing bound for symmetric channels

Assuming iterative decoding for binary erasure channels (BECs), a novel tree-based technique for upper bounding the bit error rates (BERs) of arbitrary, finite low-density parity-check (LDPC) codes is provided and the resulting bound can be evaluated for all operating erasure probabilities, including both the waterfall and the error floor regions. This upper bound can also be viewed as a narrowing search of stopping sets, which is an approach different from the stopping set enumeration used for lower bounding the error floor. When combined with optimal leaf-finding modules, this upper bound is guaranteed to be tight in terms of the asymptotic order. The Boolean framework proposed herein further admits a composite search for even tighter results. For comparison, a refinement of the algorithm is capable of exhausting all stopping sets of size les 13 for irregular LDPC codes of length n ap 500, which requires (13500) ap 1.67 times 1025trials if a brute force approach is taken. These experiments indicate that this upper bound can be used both as an analytical tool and as a deterministic worst-performance (error floor) guarantee, the latter of which is crucial to optimizing LDPC codes for extremely low BER applications, e.g., optical/satellite communications

Density evolution (DE) is one of the most powerful analytical tools for low-density parity-check (LDPC) codes and graph codes with message passing decoding algorithms. With channel symmetry as one of its fundamental assumptions, density evolution has been widely and successfully applied to different channels, including binary erasure channels (BECs), binary symmetric channels (BSCs), binary additive white Gaussian noise (BiAWGN) channels, etc. This paper generalizes density evolution for asymmetric memoryless channels, which in turn broadens the applications to general memoryless channels, e.g., z-channels, composite white Gaussian noise channels, etc. The central theorem underpinning this generalization is the convergence to perfect projection for any fixed-size supporting tree. A new iterative formula of the same complexity is then presented and the necessary theorems for the performance concentration theorems are developed. Several properties of the new density evolution method are explored, including stability results for general asymmetric memoryless channels. Simulations, code optimizations, and possible new applications suggested by this new density evolution method are also provided. This result is also used to prove the typicality of linear LDPC codes among the coset code ensemble when the minimum check node degree is sufficiently large. It is shown that the convergence to perfect projection is essential to the belief propagation (BP) algorithm even when only symmetric channels are considered. Hence, the proof of the convergence to perfect projection serves also as a completion of the theory of classical density evolution for symmetric memoryless channels.