Modern 5G communication systems implement a combination of error correction and feedback-based erasure correction (HARQ/ARQ) as reliability mechanisms, which can introduce substantial delay and resource inefficiency. We propose forward erasure correction using network coding as a more delay-efficient alternative. We present a mathematical characterization of network delay for existing reliability mechanisms and network coding. Through simulations in a network slicing environment, we demonstrate that network coding not only improves the inorder delivery delay and goodput for the applications utilizing the slice, but also benefits other applications sharing the network by reducing resource utilization for the coded slice. Our analysis and characterization point towards ideas that require attention in the 6G standardization process. These findings highlight the need for greater modularity in protocol stack design that enables the integration of novel technologies in future wireless networks.

For data streaming applications, existing solutions are not yet able to close the gap between high data rates and low delay. This work considers the problem of data streaming under mixed delay constraints over a single communication channel with delayed feedback. We propose a novel layered adaptive causal random linear network coding (LAC-RLNC) approach with forward error correction. LAC-RLNC is a variable-to-variable coding scheme, i.e., a variable amount of recovered information at the receiver over variable short block length and rate. Specifically, for data streaming with base and enhancement layers of content, we characterize a high-dimensional throughput-delay trade-off managed by the adaptive causal layering coding scheme. The base layer is designed to satisfy the strict delay constraints, as it contains the data needed to allow the streaming service. Then, the sender can manage the throughput-delay trade-off of the second layer by adjusting the retransmission rate a-priori and a-posteriori since the enhancement layer, which contains the remaining data to augment the streaming service’s quality, operates under relaxed delay constraints. We provide numerical evidence that the layered network coding strategy significantly boosts performance. Specifically, our results show that LAC-RLNC achieves up to a twofold reduction in mean delay for the base layer compared to the non-layered method, up to 3.5× compared to SR-ARQ, nearing the theoretical lower limit, while maintaining comparable enhancement layer delay and slightly improving throughput. These findings are corroborated by our analytical work, which produces bounds that closely align with simulation results and facilitates the management of the throughput-delay trade-off.

Binary turbo product codes (TPCs) are powerful error-correcting codes constructed from short component codes. Traditionally, turbo product decoding passes log likelihood ratios (LLRs) between the component decoders, inherently losing information when bit correlation exists. Such correlation can arise exogenously from sources like intersymbol interference and endogenously during component code decoding. To preserve these correlations and improve performance, we propose turbo product decoding based on group probabilities. We theoretically predict mutual information and signal-to-noise ratio (SNR) gains of group over bit-probability decoding. To translate these theoretical insights to practice, we revisit non-binary TPCs that naturally support group-probability decoding. We show that any component list decoder that takes group probabilities as input and outputs block-wise soft-output can partially preserve bit correlation, which we demonstrate with symbol-level ORBGRAND combined with soft-output GRAND (SOGRAND). Our results demonstrate that group-probability-based turbo product decoding achieves SNR gains of up to 0.3 dB for endogenous correlation and 0.7 dB for exogenous correlation, compared to bit-probability decoding.

We introduce and analyze a discrete soft-decision channel called the linear reliability channel (LRC) in which the soft information is the rank-ordering of the received symbol reliabilities. We prove that the LRC is an appropriate approximation to a general class of binary-input, continuous-output channels when the noise variance is high. The central feature of the LRC is that its combinatorial nature allows for an extensive mathematical analysis of the channel and its corresponding hard- and soft-decision maximum-likelihood (ML) decoders. In particular, we establish explicit error exponents for ML decoding in the LRC when using random codes under both hard- and soft-decision decoding. This analysis allows for a direct, quantitative evaluation of the relative advantage of soft-decision decoding. The discrete geometry of the LRC is distinct from that of the BSC, which is characterized by the Hamming weight, offering a new perspective on code construction for soft-decision settings.

Gossip algorithms are pivotal in the dissemination of information within decentralized systems. Consequently, numerous gossip libraries have been developed and widely utilized especially in blockchain protocols for the propagation of blocks and transactions. A well-established library is libp $2 p$, which provides two gossip algorithms: floodsub and gossipsub. These algorithms enable the delivery of published messages to a set of peers. In this work we aim to enhance the performance and reliability of libp $2 p$ by introducing OptimumP2P, a novel gossip algorithm that leverages the capabilities of Random Linear Network Coding (RLNC) to expedite the dissemination of information in a peer-to-peer (P2P) network. Preliminary research from the Ethereum Foundation has demonstrated the use of RLNC in the significant improvement in the block propagation time [15]. Here we present extensive evaluation results both in simulation and real-world environments that demonstrate the performance gains of OptimumP2P over the Gossipsub protocol.

We present a novel method for error correction in the presence of fading channel estimation errors (CEE). When such errors are significant, considerable performance losses can be observed if the wireless transceiver is not adapted. Instead of refining the estimate by increasing the pilot sequence length or improving the estimation algorithm, we propose two new approaches based on Guessing Random Additive Noise Decoding (GRAND) decoders. The first method involves testing multiple candidates for the channel estimate located in the complex neighborhood around the original pilot-based estimate. All these candidates are employed in parallel to compute log-likelihood ratios (LLR). These LLRs are used as soft input to Ordered Reliability Bits GRAND (ORBGRAND). Posterior likelihood formulas associated with ORBGRAND are then computed to determine which channel candidate leads to the most probable codeword. The second method is a refined version of the first approach accounting for the presence of residual CEE in the LLR computation. The performance of these two techniques is evaluated for [128, 112] 5G NR CA-Polar and CRC codes. For the considered settings, block error rate (BLER) gains of several dBs are observed compared to cases where CEE is ignored.

Guessing Random Additive Noise Decoding (GRAND) and its variants, known for their near-maximum likelihood performance, have been introduced in recent years. One such variant, Segmented GRAND, reduces decoding complexity by generating only noise patterns that meet specific constraints imposed by the linear code. In this paper, we introduce a new method to efficiently derive multiple constraints from the parity check matrix. By applying a random invertible linear transformation and reorganizing the matrix into a tree structure, we extract up to$\log _{2} n$constraints, reducing the number of decoding queries while maintaining the structure of the original code for a code length of$n$. We validate the method through theoretical analysis and experimental simulations.

We present CHOKE, a novel code-based hybrid key-encapsulation mechanism (KEM) designed to securely and efficiently transmit multiple session keys simultaneously. By encoding n independent session keys with an individually secure linear code and encapsulating each resulting coded symbol using a separate KEM, CHOKE achieves computational individual security–each key remains secure as long as at least one underlying KEM remains unbroken. Compared to traditional serial or combiner-based hybrid schemes, CHOKE reduces computational and communication costs by an n-fold factor. Furthermore, we show that the communication cost of our construction is optimal under the requirement that each KEM must be used at least once.

This work presents the design and implementation of a real-time network coding system integrated into the IP layer of a 5G testbed, offering an alternative to conventional retransmission-based reliability mechanisms such as ARQ and HARQ. Using a netfilter-based packet interception framework, we inject forward erasure correction using Random Linear Network Coding (RLNC) into live traffic between a gNB and UE over a 3GPP RF link. We evaluate a block coding scheme, analyzing its impact on throughput, jitter, and resource usage. Results show that with appropriate code rate selection, RLNC can fully recover from packet losses using fewer transmissions than ARQ/HARQ and maintain a high throughput, particularly under moderate-to-high packet loss rates. These findings demonstrate that network coding can effectively replace retransmission-based reliability in future wireless systems, with the potential for more efficient resource utilization.

We propose a novel demodulation technique that leverages developments in guesswork-based forward error correction decoders and variable-length bit-to-symbol mappings. For most common channel models, the optimal modulation schemes are known to require nonuniform probability distributions over signal points, which presents practical challenges. An established way to map uniform binary sources to non-uniform symbol distributions is to assign a different number of bits to different constellation points. Doing so, however, means that erroneous demodulation at the receiver can lead to bit insertions or deletions, turning a channel with Hamming-type errors into an insertion-deletion channel. The demodulator we propose provides error detection and correction through the use of a low-overhead padding bit sequence. We evaluate the performance of the proposed demodulator in various channel models and various communication settings. We verify that the demodulator successfully corrects the insertion-deletion errors. Using the proposed demodulator, we study different constellation design schemes and how they behave in different channel conditions. Overall, we observe considerable gains that suggest, in some circumstances, one may improve the throughput while keeping the error rate the same.

A fully integrated hardware design of the universal maximum likelihood Guessing Random Additive Noise Decoding (GRAND) algorithm implemented in 40 nm CMOS is presented. It is shown how this integrated hard-detection decoder, which is designed to process component codes of up to 128 bits in length, can be extended to efficiently decode product codes as long as 16,384 bits using the Iterative GRAND (IGRAND) algorithm. Pipelined stages provide throughput gain and dynamic energy savings when channel noise conditions improve. The chip allows for decoding product codes with two distinct component codes due to its ability to interleave between two codebooks without any switch-over time. Measurements demonstrate the decoder’s accuracy and efficiency in decoding a broad selection of product codes, including the capacity-achieving random linear product codes. The chip consumes an average energy of 30.6 pJ/b with a latency of 1.04 μs when decoding the BCH(127,106,7) component code at 68 MHz from 1.1 V at a bit flip probability of 10-5. Using a single chip to decode a BCH(127,106,7)2product code which results in 16,129-bit code of rate 0.68, we demonstrate an average energy consumption of 61.2 pJ/b with an average latency of 265 μs for the same operating conditions.

We present a communication scheme using guessing random additive noise decoding (GRAND) to improve flexibility and reliability of the existing compressed error (CE) framework. The CE framework uses information feedback to construct follow-up transmissions by compressing previous noise realizations, offering high reliability at a code rate close to the forward channel capacity. The channel decoding algorithm GRAND allows us to efficiently maintain this performance in noisy feedback settings by shifting redundancy for forward message protection to the feedback channel. Our scheme, GRAND-CE, is therefore appropriate for cases where forward and feedback channel usage costs are asymmetric, e.g. uplink communications. GRAND-CE offers super-exponential error rate performance as channel use increases, with finite usage of a noisy feedback channel. Unlike the traditional forward error correction model, the receiver performs error correction encoding and the sender handles decoding. We also propose a technique for pipelining sequential transmissions to maintain fixed forward transmission length and good feedback channel coding performance.

We introduce an algorithm for approximating the codebook probability that is compatible with all successive cancellation (SC)-based decoding algorithms, including SC list (SCL) decoding. This approximation is based on an auxiliary distribution that mimics the dynamics of decoding algorithms with an SC decoding schedule. Based on this codebook probability and SCL decoding, we introduce soft-output SCL (SO-SCL) to generate both blockwise and bitwise soft-output (SO). Using that blockwise SO, we first establish that, in terms of both block error rate (BLER) and undetected error rate (UER), SO-SCL decoding of dynamic Reed-Muller (RM) codes significantly outperforms the CRC-concatenated polar codes from 5G New Radio under SCL decoding. Moreover, using SO-SCL, the decoding misdetection rate (MDR) can be constrained to not exceed any predefined value, making it suitable for practical systems. Proposed bitwise SO can be readily generated from blockwise SO via a weighted sum of beliefs that includes a term where SO is weighted by the codebook probability, resulting in a soft-input soft-output (SISO) decoder. Simulation results for SO-SCL iterative decoding of product codes and generalized LDPC (GLDPC) codes, along with information-theoretical analysis, demonstrate significant superiority over existing list-max and list-sum approximations.

We establish that a large, flexible class of long, high redundancy error correcting codes can be efficiently and accurately decoded with guessing random additive noise decoding (GRAND). Performance evaluation demonstrates that it is possible to construct simple product codes with lengths of approximately 200 to 4000 bits and rates between 0.2 and 0.8 that outperform low-density parity-check (LDPC) codes from the 5G New Radio standard in both AWGN and fading channels. The concatenated structure enables many desirable features, including: low-complexity hardware-friendly encoding and decoding; significant flexibility in length and rate through modularity; and high levels of parallelism in encoding and decoding that enable low latency. Central is the development of a method through which any soft-input (SI) GRAND algorithm can provide soft-output (SO) in the form of an accurate a-posteriori estimate of the likelihood that a decoding is correct or, in the case of list decoding, the likelihood that each element of the list is correct. The distinguishing feature of soft-output GRAND (SOGRAND) is the provision of an estimate that the correct decoding has not been found, even when providing a single decoding. Per-block SO can be converted into accurate per-bit SO by a weighted sum that includes a term for the SI. Implementing SOGRAND adds negligible computation and memory to the existing decoding process, and using it results in a practical, low-latency alternative to LDPC codes.

The use of Mutual Information (MI) as a measure to evaluate the efficiency of cryptosystems has an extensive history. However, estimating MI between unknown random variables in a high-dimensional space is challenging. Recent advances in machine learning have enabled progress in estimating MI using neural networks. This work presents a novel application of MI estimation in the field of cryptography. We propose applying this methodology directly to estimate the MI between plaintext and ciphertext in a chosen plaintext attack. The leaked information, if any, from the encryption could potentially be exploited by adversaries to compromise the computational security of the cryptosystem. We evaluate the efficiency of our approach by empirically analyzing multiple encryption schemes and baseline approaches. Furthermore, we extend the analysis to novel network coding-based cryptosystems that provide individual secrecy and study the relationship between information leakage and input distribution.

In this work, we introduce a new technique for taking a single-secret sharing scheme with a general access structure and transforming it into an individually secure multi-secret sharing scheme where every secret has the same general access structure. To increase the information rate, we consider Individual Security which guarantees zero mutual information with each secret individually, for any unauthorized subsets. Our approach involves identifying which shares of the single-secret sharing scheme can be replaced by linear combinations of messages. When$m-1$shares are replaced, our scheme obtains an information rate of$m/\vert S\vert$, where$S$is the set of shares. This provides an improvement over the information rate of$1/\vert S\vert$in the original single-secret sharing scheme.

With the exponential growth in data volume and the emergence of data-intensive applications, particularly in the field of machine learning, concerns related to resource utilization, privacy, and fairness have become paramount. This paper focuses on the textual domain of data and addresses challenges regarding encoding sentences to their optimized representations through the lens of information-theory. In particular, we use empirical estimates of mutual information, using the Donsker-Varadhan definition of Kullback-Leibler divergence. Our approach leverages this estimation to train an information-theoretic sentence embedding, called TexShape, for (task-based) data compression or for filtering out sensitive information, enhancing privacy and fairness. In this study, we employ a benchmark language model for initial text representation, complemented by neural networks for information-theoretic compression and mutual information estimations. Our experiments demonstrate significant advancements in preserving maximal targeted information and minimal sensitive information over adverse compression ratios, in terms of predictive accuracy of downstream models that are trained using the compressed data.

We present a framework that can exploit the tradeoff between the undetected error rate (UER) and block error rate (BLER) of polar-like codes. It is compatible with all successive cancellation (SC)-based decoding methods and relies on a novel approximation that we call codebook probability. This approximation is based on an auxiliary distribution that mimics the dynamics of decoding algorithms following an SC decoding schedule. Simulation results demonstrates that, in the case of SC list (SCL) decoding, the proposed framework outperforms the state-of-art approximations from Forney's generalized decoding rule for polar-like codes with dynamic frozen bits. In addition, dynamic Reed-Muller (RM) codes using the proposed generalized decoding significantly outperform CRC-concatenated polar codes decoded using SCL in both BLER and UER.

We propose guessing random additive noise decoding-aided macrosymbols (GRAND-AMs) as a nonorthogonal multiple access (NOMA) method that can detect, error correct, and decode multiple users with imperfect channel estimation, asynchronous transmission, and interference, which are all topics of concern for Internet of Things. GRAND-AM is a NOMA method that uses both joint multiuser detection and joint error correction decoding to handle multiple access interference (MAI). For the joint multiuser detector, we introduce the concept of a macrosymbol, which is constructed from the combination of all user symbols. For the error correction decoding component, we introduce multiple access channel (MAC) codes, which are codes that are used to split the channel rate between users and correct errors due to MAI. In this scheme, each user has their information bits encoded with independent MAC codes. We use a soft detection variant of GRAND, an efficient and practical decoding method that inverts noise effect sequences from a sequence of symbols to arrive at a codeword, to correct a sequence of macrosymbols, ensuring that all user codebooks are simultaneously satisfied. The joint detection and decoding of GRAND-AM can outperform time division multiple access (TDMA) by 10 dB with perfect channel estimation, and by 6 dB with imperfect channel estimation. Considering a more complete communication chain, when additional forward error correction is used along with the MAC code, the GRAND-AM method performs similarly to a same rate low-density parity-check-coded TDMA system.

To meet the Ultra Reliable Low Latency Communication (URLLC) needs of modern applications, there have been significant advances in the development of short error correction codes and corresponding soft detection decoders. A substantial hindrance to delivering low-latency is, however, the reliance on interleaving to break up omnipresent channel correlations to ensure that decoder input matches decoder assumptions. Consequently, even when using short codes, the need to wait to interleave data at the sender and de-interleave at the receiver results in significant latency that acts contrary to the goals of URLLC. Moreover, interleaving provably reduces capacity in channels with correlation, so that potential decoding performance is degraded. Here we introduce a variant of Ordered Reliability Bits Guessing Random Additive Noise Decoding (ORBGRAND), which we call ORBGRAND-Approximate Independence (ORBGRAND-AI), a soft-detection decoder that can decode any moderate redundancy code and overcomes the limitation of existing decoding paradigms by leveraging channel correlations and circumventing the need for interleaving. By leveraging correlation, not only is latency reduced, but error correction performance can be enhanced by multiple dB, while decoding complexity is also reduced, offering one potential solution for the provision of URLLC.

We establish that during the execution of any Guessing Random Additive Noise Decoding (GRAND) algorithm, an interpretable, useful measure of decoding confidence can be evaluated. This measure takes the form of a log-likelihood ratio (LLR) of the hypotheses that, should a decoding be found by a given query, the decoding is correct versus its being incorrect. That LLR can be used as soft output for a range of applications and we demonstrate its utility by showing that it can be used to confidently discard likely erroneous decodings in favor of returning more readily managed erasures. We show that feature can be used to compromise the physical layer security of short length wiretap codes by accurately and confidently revealing a proportion of a communication when code-rate is far above the Shannon capacity of the associated hard detection channel.

Guessing Random Additive Noise Decoding (GRAND) is a family of hard- and soft-detection error correction decoding algorithms that provide accurate decoding of any moderate redundancy code of any length. Here we establish a method through which any soft-input GRAND algorithm can provide soft output in the form of an accurate a posteriori estimate of the likelihood that a decoding is correct or, in the case of list decoding, the likelihood that the correct decoding is an element of the list. Implementing the method adds negligible additional computation and memory to the existing decoding process. The output permits tuning the balance between undetected errors and block errors for arbitrary moderate redundancy codes including CRCs.

The use of mutual information as a tool in private data sharing has remained an open challenge due to the difficulty of its estimation in practice. In this paper, we propose InfoShape, a task-based encoder that aims to remove unnecessary sensitive information from training data while maintaining enough relevant information for a particular ML training task. We achieve this goal by utilizing mutual information estimators that are based on neural networks, in order to measure two performance metrics, privacy and utility. Using these together in a Lagrangian optimization, we train a separate neural network as a lossy encoder. We empirically show that InfoShape is capable of shaping the encoded samples to be informative for a specific downstream task while eliminating unnecessary sensitive information. Moreover, we demonstrate that the classification accuracy of downstream models has a meaningful connection with our utility and privacy measures.

Random jammers that overpower transmitted signals are a practical concern for many wireless communication protocols. As such, wireless receivers must be able to cope with standard channel noise and jamming (intentional or unintentional). To address this challenge, we propose a novel method to augment the resilience of the recent family of universal error-correcting GRAND algorithms. This method, called Erasure Decoding by Gaussian Elimination (EDGE), impacts the syndrome check block and is applicable to any variant of GRAND. We show that the proposed EDGE method naturally reverts to the original syndrome check function in the absence of erasures caused by jamming. We demonstrate this by implementing and evaluating GRAND-EDGE and ORBGRAND-EDGE. Simulation results, using a Random Linear Code (RLC) with a code rate of 105/128, show that the EDGE variants lower both the Block Error Rate (BLER) and the computational complexity by up to five order of magnitude compared to the original GRAND and ORBGRAND algorithms. We further compare ORBGRAND-EDGE to Ordered Statistics Decoding (OSD), and demonstrate an improvement of up to three orders of magnitude in the BLER.

Multiuser detection in multiple access channels is typically handled through individual detection of each user followed by individual error correction with a long error correcting code. In contrast, we introduce an alternative approach that uses guessing random additive noise decoding for macrosymbols, which is a joint multiuser detection method that works well with short error correcting codes. The macrosymbols are generated from the combination of the received symbols across all users, which are individually coded with short error correcting codes such as (8,4) cyclic redundancy check codes or (7,4) Hamming codes. Guessing random additive noise decoding with soft information on symbol level basis is then used to jointly correct both users on a macrosymbol level basis. The joint detection and error correction using the guessing random additive noise decoding algorithm aided macrosymbols method gives a 4 dB improvement in$E_{b}/N_{0}$over individual maximum likelihood multiuser detection and error correction.

For spectral efficiency, higher order modulation symbols confer information on more than one bit. As soft detection forward error correction decoders assume the availability of information at binary granularity, however, soft demappers are required to compute per-bit reliabilities from complex-valued signals. Here we show that the recently introduced universal soft detection decoder ORBGRAND can be adapted to work with symbol-level soft information, obviating the need for energy expensive soft demapping. We establish that doing so reduces complexity while retaining the error correction performance achieved with the optimal demapper.

For communications subject to correlated channel effects, noise recycling has recently been shown to enhance channel capacity with receiver-side-only changes. Using a taped-out chip, in a hard-detection scenario with guessing random additive noise decoding (GRAND), noise recycling has been established to both increase decoding accuracy and decrease decoding energy in single communication channels that employ interleavers. This paper presents results for the related soft-detection scenario by investigating noise recycling with an in-silicon realization of Ordered Reliability Bits Guessing Random Additive Noise Decoding (ORBGRAND). Measurements demonstrate that noise recycling leads to a significant reduction in the block error rate (BLER) and substantial improvements in latency and energy consumption by reducing the number of queries required for decoding. We also discuss dynamic lead channel selection for the soft detection scenario and show the importance of lead channel on overall decoding performance.

The problem of mismatched guesswork considers the additional cost incurred by using a guessing function which is optimal for a distribution q when the random variable to be guessed is actually distributed according to a different distribution p. This problem has been well-studied from an asymptotic perspective, but there has been little work on quantifying the difference in guesswork between optimal and suboptimal strategies for a finite number of symbols. In this non-asymptotic regime, we consider a definition for mismatched guesswork which we show is equivalent to a variant of the Kendall tau permutation distance applied to optimal guessing functions for the two distributions. We use this formulation to bound the cost of guesswork under mismatch given a bound on the total variation distance between those distributions.

Guessing random additive noise decoding (GRAND) has recently demonstrated maximum-likelihood (ML) decoding performance on efficient, universal silicon realizations. Leveraging input bit-reliability soft information extracted from the channel and noise statistics, GRAND rank-orders and queries noise sequences in non-decreasing likelihood to recover code-words of arbitrary code-book structures. We consider soft-input, soft-output (SISO) GRAND that generates bit-reliability log-likelihood ratios (LLRs) via successive Euclidean-distance computations over a list of noise-recovered words. Noise guessing and list construction follow an ordered reliability bits GRAND (ORBGRAND) mechanism, the guess budget of which controls the performance and complexity trade-offs. The generated LLRs form enhanced a priori information that adapts noise-sequence ordering in a subsequent soft-GRAND iteration. We derive bounds on the achievable rates under per-realization and marginal input soft information and empirically study the achievable rates of SISO-GRAND. We also examine the complexity of the joint data detection and GRAND core, highlighting its superiority to conventional list-based detection schemes. SISO-ORBGRAND can outperform conventional sphere decoding in data detection and LLR generation; the corresponding channel-mismatched rates approximate ML decoding.

In a setting where the forward and feedback channel are noisy BSCs, we show how capacity is nearly achievable in a scheme with only source coding on the forward channel. In representative settings with noisy feedback, GRAND makes the scheme not only possible but practical. The sender transmits uncoded messages, and the receiver provides a noise effect guess as in GRAND, which is channel-encoded and sent to the receiver. With noiseless, finite-length feedback our scheme provides the type of super exponential error behavior associated in previous work with infinite-capacity feedback channels. With noisy feed-back, which is the more common setting in most systems, our scheme permits forward throughput that is effectively the same as in a noiseless feedback case. Moreover, the feedback channel usage remains limited. We propose a target error rate as a useful design parameter.

Network coding has been widely used as a technology to ensure efficient and reliable communication. The ability to recode packets at the intermediate nodes is a major benefit of network coding implementations. This allows the intermediate nodes to choose a different code rate and fine-tune the outgoing transmission to the channel conditions, decoupling the requirement for the source node to compensate for cumulative losses over a multi-hop network. Block network coding solutions already have practical recoders but an on-the-fly recoder for sliding window network coding has not been studied in detail. In this paper, we present the implementation details of a practical recoder for sliding window network coding for the first time along with a comprehensive performance analysis of a multi-hop network using the recoder. The sliding window recoder ensures that the network performs closest to its capacity and that each node can use its outgoing links efficiently.

We provide a flow-based coded caching framework for information centric networks. We jointly optimize delivery rates, cross coding, and cache contents allocation as a function of demand and the network's topology. Our model accounts for stor-age and transmission costs, demand asymmetry, and arbitrary multi-hop topologies, and relies on an ordered flow-based de-coding schedule for the transmissions created by pairwise coded flows. Through extensive experiments over multiple topologies, we observe that our coded caching scheme reduces transmission costs over competitors by several orders of magnitude.

Modeling realistic millimeter-wave (mmWave) channels is crucial to the study of ultra-reliable communication in next-generation wireless networks. MmWave provides significant gains over sub-6GHz communication but has very stringent requirements on channel conditions, since slight variations in the channel may result in significant performance degradation of mmWave communication. In this work, we present an experimental mmWave testbed and the mathematical modeling of the channels using the measurements collected from an outdoor testbed that complies with IEEE 802.11ad. We show how the model fits the reality and demonstrate the impact of adaptive causal network coding in mmWave real and simulated networks.

This work presents an interactive real-time demonstration of the first-integrated universal soft-detection decoder with an ultra-low energy consumption of 0.76pJ/bit and the lowest power of 4.9mW using Ordered Reliability Bits Guessing Random Additive Noise Decoding (ORBGRAND) [1]. The chip has a reconfigurable code length of 32 to 256 bits. The chip’s universality is demonstrated by decoding multimedia messages using different codebooks through an interactive Graphics User Interface (GUI). It is shown that the chip’s performance is independent of the codebook used and dynamically adapts to the channel noise conditions where lower energy is consumed as the Signal-to-Noise Ratio (SNR) of the channel improves.

With the large bandwidths available in the terahertz regime, directional transmissions can exhibit angular dispersion, i.e., frequency-dependent radiation direction. Unfortunately, angular dispersion introduces new security threats as increased bandwidth necessarily yields a larger signal footprint in the spatial domain and potentially benefits an eavesdropper. This paper is the first study of secure transmission strategies on angularly dispersive links. Based on information theoretic foundations, we propose a transmission strategy that channelizes the wideband transmission in frequency, and performs secure coding across frequency channels. With model-driven evaluations and over-the-air experiments, we show that the proposed method exploits the properties of angular dispersion to realize secure wideband transmissions, despite the increased signal footprint and even for practical irregular beams with side lobes and asymmetry. In contrast, without the proposed cross-channel coding strategy, angularly dispersive links can suffer from significant security degradation when bandwidth increases. In addition, we find that the security degradation due to bandwidth increment for angularly dispersive links is secondary compared to other factors including the selected secrecy rate or the directivity of the link. Nonetheless, we find that a higher angular dispersion level, i.e., a larger angular spread with the same bandwidth, results in a higher security degradation as bandwidth increases.

Packet losses are common events in today’s networks. They usually result in longer delivery times for application data since retransmissions are the de facto technique to recover from such losses. Retransmissions is a good strategy for many applications but it may lead to poor performance with latency-sensitive applications compared to network coding. Although different types of network coding techniques have been proposed to reduce the impact of losses by transmitting redundant information, they are not widely used. Some niche applications include their own variant of Forward Erasure Correction (FEC) techniques, but there is no generic protocol that enables many applications to easily use them. We close this gap by designing, implementing and evaluating a new Flexible Erasure Correction (FlEC) framework inside the newly standardized QUIC protocol. With FlEC, an application can easily select the reliability mechanism that meets its requirements, from pure retransmissions to various forms of FEC. We consider three different use cases:$(i)$bulk data transfer,$(ii)$file transfers with restricted buffers and$(iii)$delay-constrained messages. We demonstrate that modern transport protocols such as QUIC may benefit from application knowledge by leveraging this knowledge in FlEC to provide better loss recovery and stream scheduling. Our evaluation over a wide range of scenarios shows that the FlEC framework outperforms the standard QUIC reliability mechanisms from a latency viewpoint.

Optimal modulation (OM) schemes for Gaussian channels with peak and average power constraints are known to require nonuniform probability distributions over signal points, which presents practical challenges. An established way to map uniform binary sources to non-uniform symbol distributions is to assign a different number of bits to different constellation points. Doing so, however, means that erroneous demodulation at the receiver can lead to bit insertions or deletions that result in significant binary error propagation. In this paper, we introduce a light-weight variant of Guessing Random Additive Noise Decoding (GRAND) to resolve insertion and deletion errors at the receiver by using a simple padding scheme. Performance evaluation demonstrates that our approach results in an overall gain in demodulated bit-error-rate of over 2 dB Eb/NO when compared to 128-Quadrature Amplitude Modulation (QAM). The GRAND-aided OM scheme outperforms coding with a low-density parity check code of the same average rate as that induced by our simple padding.

Guessing random additive noise decoding (GRAND) is a universal maximum-likelihood decoder that recovers codewords by guessing rank-ordered putative noise sequences and inverting their effect until one or more valid code-words are obtained. This work explores how GRAND can leverage additive-noise statistics and channel-state information in fading channels. Instead of computing per-bit reliability information in detectors and passing this information to the decoder, we propose leveraging the colored noise statistics following channel equalization as pseudo-soft information for sorting noise sequences. We investigate the efficacy of pseudo-soft information extracted from linear zero-forcing and minimum mean square error equalization when fed to a hardware-friendly soft-GRAND (ORBGRAND). We demonstrate that the proposed pseudo-soft GRAND schemes approximate the performance of state-of-the-art decoders of CA-Polar and BCH codes that avail of complete soft information. Compared to hard-GRAND, pseudo-soft ORBGRAND introduces up to 10 dB SNR gains for a target 10–3block-error rate.

Guessing random additive noise decoding (GRAND) is a maximum likelihood (ML) decoding method that identifies the noise effects corrupting code-words of arbitrary code-books. In a joint detection and decoding framework, this work demonstrates how GRAND can leverage crude soft information in received symbols and channel state information to generate, through guesswork, soft bit reliability outputs in log-likelihood ratios (LLRs). The LLRs are generated via successive computations of Euclidean-distance metrics corresponding to candidate noise-recovered words. Noting that the entropy of noise is much smaller than that of information bits, a small number of noise effect guesses generally suffices to hit a code-word, which allows generating LLRs for critical bits; LLR saturation is applied to the remaining bits. In an iterative (turbo) mode, the generated LLRs at a given soft-input, soft-output GRAND iteration serve as enhanced a priori information that adapts noise-sequence guess ordering in a subsequent iteration. Simulations demonstrate that a few turbo-GRAND iterations match the performance of ML-detection-based soft-GRAND in both AWGN and Rayleigh fading channels at a complexity cost that, on average, grows linearly (instead of exponentially) with the number of symbols.

Noise recycling is a recently proposed method that significantly enhances decoding performance when used for orthogonal channels impacted by correlated noise with only receiver side changes. In this paper, we establish that noise recycling can be applied in a single communication channel that is subject to temporally correlated noise by leveraging a standard matrix interleaver to create the effect of orthogonal channels. The proposed interleaved noise recycling technique works with any code, requires no sender-side alterations, and only minor changes to the receiver architecture. In a hard-detection scenario, we demonstrate noise recycling can enable an accurate estimate of continuous realization of noise without using any soft information, resulting in a gain of more than 2 dB in Block Error Rate (BLER). We use the first hardware implementation of Guessing Random Additive Noise Decoding (GRAND), a universal noise-centric decoder, to illustrate the advantages of noise recycling in hardware performance. At a correlation coefficient of 0.75, Eb/N0of 4 dB, a maximum of 36× decoding energy savings with a 12× reduction in latency is achieved using a BCH(127,113) code when GRAND is equipped with the proposed noise recycling.

To improve the utility of learning applications and render machine learning solutions feasible for complex applications, a substantial amount of heavy computations is needed. Thus, it is essential to delegate the computations among several workers, which brings up the major challenge of coping with delays and failures caused by the system’s heterogeneity and uncertainties. In particular, minimizing the end-to-end job in-order execution delay, from arrival to delivery, is of great importance for real-world delay-sensitive applications. In this paper, for computation of each job iteration in a stochastic heterogeneous distributed system where the workers vary in their computing and communicating powers, we present a novel joint scheduling-coding framework that optimally split the coded computational load among the workers. This closes the gap between the workers’ response time, and is critical to maximize the resource utilization. To further reduce the in-order execution delay, we also incorporate redundant computations in each iteration of a distributed computational job. Our simulation results demonstrate that the delay obtained using the proposed solution is dramatically lower than the uniform split which is oblivious to the system’s heterogeneity and, in fact, is very close to an ideal lower bound just by introducing a small percentage of redundant computations.

We consider the problem of secure and reliable communication over a noisy multipath network. Previous work considering a noiseless version of our problem proposed a hybrid universal network coding cryptosystem (HUNCC). By combining an information-theoretically secure encoder together with partial encryption, HUNCC is able to obtain security guarantees, even in the presence of an all-observing eavesdropper. In this paper, we propose a version of HUNCC for noisy channels (N-HUNCC). This modification requires four main novelties. First, we present a network coding construction which is jointly, individually secure and error-correcting. Second, we introduce a new security definition which is a computational analogue of individual security, which we call individual indistinguishability under chosen ciphertext attack (individual IND-CCA1), and show that N-HUNCC satisfies it. Third, we present a noise based decoder for N-HUNCC, which permits the decoding of the encoded-then-encrypted data. Finally, we discuss how to select parameters for N-HUNCC and its error-correcting capabilities.

For data streaming applications, existing solutions are not yet able to close the gap between high data rates and low delay. This work considers the problem of data streaming under mixed delay constraints over a single communication channel with delayed feedback. We propose a novel layered adaptive causal random linear network coding (LAC-RLNC) approach with forward error correction. LAC-RLNC is a variable-to-variable coding scheme, i.e., variable recovered information data at the receiver over variable short block length and rate is proposed. Specifically, for data streaming with base and enhancement layers of content, we characterize a high dimensional throughput-delay trade-off managed by the adaptive causal layering coding scheme. The base layer is designed to satisfy the strict delay constraints, as it contains the data needed to allow the streaming service. Then, the sender can manage the throughput-delay trade-off of the second layer by adjusting the retransmission rate a priori and posterior as the enhancement layer, that contains the remaining data to augment the streaming service’s quality, is with the relax delay constraints. We numerically show that the layered network coding approach can dramatically increase performance. We demonstrate that LAC-RLNC compared with the non-layered approach gains a factor of three in mean and maximum delay for the base layer, close to the lower bound, and factor two for the enhancement layer.

This paper is eligible for the Jack Keil Wolf ISIT Student Paper Award. We generalize a previous framework for designing utility-optimal differentially private (DP) mechanisms via graphs, where datasets are vertices in the graph and edges represent dataset neighborhood. The boundary set contains datasets where an individual’s response changes the binary-valued query compared to its neighbors. Previous work was limited to the homogeneous case where the privacy parameter ε across all datasets was the same and the mechanism at boundary datasets was identical. In our work, the mechanism can take different distributions at the boundary and the privacy parameter ε is a function of neighboring datasets, which recovers an earlier definition of personalized DP as special case. The problem is how to extend the mechanism, which is only defined at the boundary set, to other datasets in the graph in a computationally efficient and utility optimal manner. Using the concept of strongest induced DP condition we solve this problem efficiently in polynomial time (in the size of the graph).

We extend a previous framework for designing differentially private (DP) mechanisms via randomized graph colorings that was restricted to binary functions, corresponding to colorings in a graph, to multi-valued functions. As before, datasets are nodes in the graph and any two neighboring datasets are connected by an edge. In our setting, we assume that each dataset has a preferential ordering for the possible outputs of the mechanism, each of which we refer to as a rainbow. Different rainbows partition the graph of datasets into different regions. We show that if the DP mechanism is pre-specified at the boundary of such regions and behaves identically for all same-rainbow boundary datasets, at most one optimal such mechanism can exist and the problem can be solved by means of a morphism to a line graph. We then show closed form expressions for the line graph in the case of ternary functions. Treatment of ternary queries in this paper displays enough richness to be extended to higher-dimensional query spaces with preferential query ordering, but the optimality proof does not seem to follow directly from the ternary proof.

A notable result from analysis of Boolean functions is the Basic Invariance Principle (BIP), a quantitative nonlinear generalization of the Central Limit Theorem for multilinear polynomials. We present a generalization of the BIP for bivariate multilinear polynomials, i.e., polynomials over two n-length sequences of random variables. This bivariate invariance principle arises from an iterative application of the BIP to bound the error in replacing each of the two input sequences. In order to prove this invariance principle, we first derive a version of the BIP for random multilinear polynomials, i.e., polynomials whose coefficients are random variables. As a benchmark, we also state a naive bivariate invariance principle which treats the two input sequences as one and directly applies the BIP. Neither principle is universally stronger than the other, but we do show that for a notable class of bivariate functions, which we term separable functions, our subtler principle is exponentially tighter than the naive benchmark.

Randomized backoff protocols, such as exponential backoff, are a powerful tool for managing access to a shared resource, often a wireless communication channel (e.g., [1]). For a wireless device to transmit successfully, it uses a backoff protocol to ensure exclusive access to the channel. Modern radios, however, do not need exclusive access to the channel to communicate; in particular, they have the ability to receive useful information even when more than one device transmits at the same time. These capabilities have now been exploited for many years by systems that rely on interference cancellation, physical layer network coding and analog network coding to improve efficiency. For example, Zigzag decoding [56] demonstrated how a base station can decode messages sent by multiple devices simultaneously.

With the large bandwidths available in the terahertz regime, directional transmissions can exhibit angular dispersion, i.e., frequency-dependent radiation direction. Unfortunately, angular dispersion introduces new security threats as increased bandwidth necessarily yields a larger signal footprint in the spatial domain and potentially benefits an eavesdropper. This paper is the first study of secure transmission strategies on angularly dispersive links. Based on information theoretic foundations, we propose to channelize the wideband transmission in frequency, and perform secure coding across frequency channels. With over-the-air experiments, we show that the proposed method exploits the properties of angular dispersion to realize secure wideband transmissions, despite the increased signal footprint and even for practical irregular beams with side lobes and asymmetry. In contrast, without the proposed cross-channel coding strategy, angularly dispersive links can suffer from significant security degradation when bandwidth increases.

While many communications media, such as wireless and certain classes of wireline channels, typically lead to bursty errors, most decoders are designed assuming memoryless channels. Consequently, communication systems generally rely on interleaving over tens of thousands of bits to match decoder assumptions. Even for short high rate codes, awaiting sufficient data in interleaving and de-interleaving is a significant source of unwanted latency. We construct an extension to the recently proposed Guessing Random Additive Noise Decoding (GRAND) algorithm, which we call GRAND-MO for GRAND Markov Order. By foregoing interleaving and instead making use of the bursty nature of noise, low-latency communication is possible with block error rates outperforming their interleaved counterparts by a substantial margin. We establish that certain well-known binary codes with structured code-word patterns are ill-suited for use in bursty channels, but Random Linear Codes (RLCs) prove robust to correlated noise. We further demonstrate that by operating directly on modulated symbols rather than de-mapped bits, GRAND-MO achieves further performance and complexity gains by exploiting information that is lost in demodulation. As a result, GRAND-MO provides one potential solution for applications that require ultra-reliable low latency communication.

The design and implementation of error correcting codes has long been informed by two fundamental results: Shannon’s 1948 capacity theorem, which established that long codes use noisy channels most efficiently; and Berlekamp, McEliece, and Van Tilborg’s 1978 theorem on the NP-completeness of decoding linear codes. These results shifted focus away from creating code-independent decoders, but recent low-latency communication applications necessitate relatively short codes, providing motivation to reconsider the development of universal decoders. We introduce a scheme for employing binarized symbol soft information within Guessing Random Additive Noise Decoding, a universal hard detection decoder. We incorporate codebook-independent quantization of soft information to indicate demodulated symbols to be reliable or unreliable. We introduce two decoding algorithms: one identifies a conditional Maximum Likelihood (ML) decoding; the other either reports a conditional ML decoding or an error. For random codebooks, we present error exponents and asymptotic complexity, and show benefits over hard detection. As empirical illustrations, we compare performance with majority logic decoding of Reed-Muller codes, with Berlekamp-Massey decoding of Bose-Chaudhuri-Hocquenghem codes, with CA-SCL decoding of CA-Polar codes, and establish the performance of Random Linear Codes, which require a universal decoder and offer a broader palette of code sizes and rates than traditional codes.

Emulating a shared atomic , read/write storage system is a fundamental problem in distributed computing. Replicating atomic objects among a set of data hosts was the norm for traditional implementations (e.g., [ 11 ]) in order to guarantee the availability and accessibility of the data despite host failures. As replication is highly storage demanding, recent approaches suggested the use of erasure-codes to offer the same fault-tolerance while optimizing storage usage at the hosts. Initial works focused on a fixed set of data hosts. To guarantee longevity and scalability, a storage service should be able to dynamically mask hosts failures by allowing new hosts to join, and failed host to be removed without service interruptions. This work presents the first erasure-code -based atomic algorithm, called Ares , which allows the set of hosts to be modified in the course of an execution. Ares is composed of three main components: (i) a reconfiguration protocol , (ii) a read/write protocol , and (iii) a set of data access primitives (DAPs) . The design of Ares is modular and is such to accommodate the usage of various erasure-code parameters on a per-configuration basis. We provide bounds on the latency of read/write operations and analyze the storage and communication costs of the Ares algorithm.

As a building block toward a simple and scalable solution for massive random access, we introduce collision-resolution algorithms using successive interference cancellation (SIC) based on the received signals, with no need for any coordination or codebook differentiation. We first consider two-user multiple access with the ZigZag algorithm. We prove that the original ZigZag and a modified version of it, calleddouble-zipper ZigZag, attain the same performance as the optimal coordinated time-sharing in the high signal to noise ratio (SNR) regime, even in the presence of channel state information (CSI) errors. We then extend the results to the case of arbitrary number of users employing delay-domain processing. Specifically, we introduce delay-domain zero forcing and its regularized version, which are able to cancel and suppress the interference among users, respectively. By obtaining a post-processing system model and characterizing the accumulated noise during the decoupling process, we also derive bounds on the achievable sum-rates of the proposed algorithm for both cases of perfect and imperfect CSI. Simulation results show that the newly proposed approach have comparable performance with coordinated time-sharing at high SNRs.

We introduce Iterative GRAND (IGRAND), a universal product code decoder that applies iterative bounded distance decoding and decodes component codes using code-agnostic Guessing Random Additive Noise Decoding (GRAND). We empirically determine its accuracy and, based on GRAND hardware measurements, its complexity, showing gains over alternative algorithms. We prove that the class of product codes with random linear component codes, which IGRAND is capable of decoding, are capacity-achieving in hard-decision channels.

One of the main challenges in containing the Coronoavirus disease 2019 (COVID-19) pandemic stems from the difficulty in carrying out efficient mass diagnosis over large populations. The leading method to test for COVID-19 infection utilizes qualitative polymerase chain reaction, implemented using dedicated machinery which can simultaneously process a limited amount of samples. A candidate method to increase the test throughput is to examine pooled samples comprised of a mixture of samples from different patients. In this work we study pooling-based COVID-19 tests. We identify the specific requirements of COVID-19 testing, including the need to characterize the infection level and to operate in a one-shot fashion, which limit the application of traditional group-testing (GT) methods. We then propose a multi-level GT scheme, designed specifically to meet the unique requirements of COVID-19 tests, while exploiting the strength of GT theory to enable accurate recovery using much fewer tests than patients. Our numerical results demonstrate that multi-level GT reliably and efficiently detects the infection levels, while achieving improved accuracy over previously proposed one-shot COVID-19 pooled-testing methods.

CRC codes have long since been adopted in a vast range of applications. The established notion that they are suitable primarily for error detection can be set aside through use of the recently proposed Guessing Random Additive Noise Decoding (GRAND). Hard-detection (GRAND-SOS) and soft-detection (ORBGRAND) variants can decode any short, high-rate block code, making them suitable for error correction of CRC-coded data. When decoded with GRAND, short CRC codes have error correction capability that is at least as good as popular codes such as BCH codes, but with no restriction on either code length or rate.The state-of-the-art CA-Polar codes are concatenated CRC and Polar codes. For error correction, we find that the CRC is a better short code than either Polar or CA-Polar codes. Moreover, the standard CA-SCL decoder only uses the CRC for error detection and therefore suffers severe performance degradation in short, high rate settings when compared with the performance GRAND provides, which uses all of the CA-Polar bits for error correction.Using GRAND, existing systems can be upgraded from error detection to low-latency error correction without re-engineering the encoder, and additional applications of CRCs can be found in IoT, Ultra-Reliable Low Latency Communication (URLLC), and beyond. The universality of GRAND, its ready parallelized implementation in hardware, and the good performance of CRC as codes make their combination a viable solution for low-latency applications.

We consider a wireless communication network with an adaptive scheme to select the number of packets to be admitted and encoded for each transmission, and characterize the information timeliness. For a network of erasure channels and discrete time, we provide closed form expressions for the Average and Peak Age of Information (AoI) as functions of admission control and adaptive coding parameters, the feedback delay, and the maximum feasible end-to-end rate that depends on channel conditions and network topology. These new results guide the system design for robust improvements of the AoI when transmitting time sensitive information in the presence of topology and channel changes. We illustrate the benefits of using adaptive packet coding to improve information timeliness by characterizing the network performance with respect to the AoI along with its relationship to throughput (rate of successfully decoded packets at the destination) and per-packet delay. We show that significant AoI performance gains can be obtained in comparison to the uncoded case, and that these gains are robust to network variations as channel conditions and network topology change.

We present a framework for designing differentially private (DP) mechanisms for binary functions via a graph representation of datasets. Datasets are nodes in the graph and any two neighboring datasets are connected by an edge. The true binary function we want to approximate assigns a value (or true color) to a dataset. Randomized DP mechanisms are then equivalent to randomized colorings of the graph. A key notion we use is that of the boundary of the graph. Any two neighboring datasets assigned a different true color belong to the boundary. Under this framework, we show that fixing the mechanism behavior at the boundary induces a unique optimal mechanism. Moreover, if the mechanism is to have a homogeneous behavior at the boundary, we present a closed expression for the optimal mechanism, which is obtained by means of a pullback operation on the optimal mechanism of a line graph. For balanced mechanisms, not favoring one binary value over another, the optimal (ε, 6)-DP mechanism takes a particularly simple form, depending only on the minimum distance to the boundary, on ε, and on 6. A full version of this paper can be found in [1].

Two main problems arise in the Multiple Access Channel (MAC): interference from different users, and additive noise channel noise. Maximum A-Posteriori (MAP) joint decoding or successive interference cancellation are known to be capacity-achieving for the MAC when paired with appropriate codes. We extend the recently proposed Soft Guessing Random Additive Noise Decoder (SGRAND) to guess, using soft information, the effect of noise on the sum of users' transmitted codewords. Next, we manage interference by applying ZigZag decoding over the resulting putative noiseless MAC to obtain candidate codewords. Guessing continues until the candidate codewords thus obtained pertain to the corresponding users' codebooks. This MAC SGRAND decoder is a MAP decoder that requires no coordination between users, who can use arbitrary moderate redundancy short length codes of different types and rates.

In this paper we consider the problem of encoding data into repeat-free sequences in which sequences are imposed to contain any k-tuple at most once (for predefined k). First, the capacity of the repeat-free constraint are calculated. Then, an efficient algorithm, which uses two bits of redundancy, is presented to encode length- n sequences for k=2+2log(n). This algorithm is then improved to support any value of k of the form k=alog(n), for 1 <; a, while its redundancy is o(n). We also calculate the capacity of repeat-free sequences when combined with local constraints which are given by a constrained system, and the capacity of multi-dimensional repeat-free codes.

Let$T_{\epsilon }$be the noise operator acting on Boolean functions$f:\{0, 1\}^{n}\to \{0, 1\}$, where$\epsilon \in [{0, 1/2}]$is the noise parameter. Given$\alpha >1$and fixed mean$\mathbb {E} f$, which Boolean function$f$has the largest$\alpha $-th moment$\mathbb {E}(T_\epsilon f)^\alpha $? This question has close connections with noise stability of Boolean functions, the problem of non-interactive correlation distillation, and Courtade-Kumar’s conjecture on the most informative Boolean function. In this paper, we characterize maximizers in some extremal settings, such as low noise ($\epsilon =\epsilon (n)$close to 0), high noise ($\epsilon =\epsilon (n)$close to 1/2), as well as when$\alpha =\alpha (n)$is large. Analogous results are also established in more general contexts, such as Boolean functions defined on discrete torus$(\mathbb {Z}/p \mathbb {Z})^{n}$and the problem of noise stability in a tree model.

In this article, we address the scheduling problem in wireless ad hoc networks by exploiting the computational advantage that comes when scheduling problems can be represented by claw-free conflict graphs where we consider a wireless broadcast medium. It is possible to formulate a scheduling problem of broadcast transmissions as finding the maximum weighted independent set (MWIS) in the conflict graph of the network. Finding the MWIS of a general graph is NP-hard leading to an NP-hard complexity of scheduling. In a claw-free conflict graph, MWIS may be found in polynomial time leading to a throughput-optimal scheduling. We show that the conflict graphs of certain wireless ad hoc networks are claw-free. In order to obtain claw-free conflict graphs in general networks, we suggest introducing additional conflicts (edges) with the aim of keeping the decrease in MWIS size minimal. To this end, we introduce an iterative optimization problem to decide where to introduce edges and investigate its efficient implementation. We conclude that the claw breaking method by adding extra edges can perform very close to optimal scenario and better than the polynomial time maximal independent set scheduling benchmark under the necessary assumptions.

To facilitate applications in IoT, 5G, and beyond, there is an engineering need to enable high-rate, low-latency communications. Errors in physical channels typically arrive in clumps, but most decoders are designed assuming that channels are memoryless. As a result, communication networks rely on interleaving over tens of thousands of bits so that channel conditions match decoder assumptions. Even for short high rate codes, awaiting sufficient data to interleave at the sender and de-interleave at the receiver is a significant source of unwanted latency. Using existing decoders with non-interleaved channels causes a degradation in block error rate performance owing to mismatch between the decoder's channel model and true channel behaviour.Through further development of the recently proposed Guessing Random Additive Noise Decoding (GRAND) algorithm, which we call GRAND-MO for GRAND Markov Order, here we establish that by abandoning interleaving and embracing bursty noise, low-latency, short-code, high-rate communication is possible with block error rates that outperform their interleaved counterparts by a substantial margin. Moreover, while most decoders are twinned to a specific code-book structure, GRANDMO can decode any code. Using this property, we establish that certain well-known structured codes are ill-suited for use in bursty channels, but Random Linear Codes (RLCs) are robust to correlated noise. This work suggests that the use of RLCs with GRAND-MO is a good candidate for applications requiring high throughput with low latency.

Analog signals processed in digital hardware are quantized into a discrete bit-constrained representation. Quantization is typically carried out using analog-to-digital converters (ADCs), operating in a serial scalar manner. In some applications, a set of analog signals are acquired individually and processed jointly. Such setups are referred to as distributed quantization. In this work we propose a distributed quantization scheme for representing a set of sparse time sequences acquired using conventional scalar ADCs. Our approach utilizes tools from secure group testing theory to exploit the sparse nature of the acquired analog signals, obtaining a compact and accurate representation while operating in a distributed fashion. We then show how our technique can be implemented when the quantized signals are transmitted over a multihop communication network providing a low-complexity network policy for routing and signal recovery. Our numerical evaluations demonstrate that the proposed scheme notably outperforms conventional methods based on the combination of quantization and compressed sensing tools.

We propose a novel multipath multi-hop adaptive and causal random linear network coding (AC-RLNC) algorithm with forward error correction. This algorithm generalizes our joint optimization coding solution for point-to-point communication with delayed feedback. AC-RLNC is adaptive to the estimated channel condition, and is causal, as the coding adjusts the retransmission rates using a priori and posteriori algorithms. In the multipath network, to achieve the desired throughput and delay, we propose to incorporate an adaptive packet allocation algorithm for retransmission, across the available resources of the paths. This approach is based on a discrete water filling algorithm, i.e., bit-filling, but, with two desired objectives, maximize throughput and minimize the delay. In the multipath multi-hop setting, we propose a new decentralized balancing optimization algorithm. This balancing algorithm minimizes the throughput degradation, caused by the variations in the channel quality of the paths at each hop. Furthermore, to increase the efficiency, in terms of the desired objectives, we propose a new selective recoding method at the intermediate nodes. We derive bounds on the throughput and the mean and maximum in-order delivery delay of AC-RLNC, both in the multipath and multipath multi-hop case. In the multipath case, we prove that in the non-asymptotic regime, the suggested code may achieve more than 90% of the channel capacity with zero error probability under mean and maximum in-order delay constraints, namely a mean delay smaller than three times the optimal genie-aided one and a maximum delay within eight times the optimum. In the multipath multi-hop case, the balancing procedure is proven to be optimal with regards to the achieved rate. Through simulations, we demonstrate that the performance of our adaptive and causal approach, compared to selective repeat (SR)-ARQ protocol, is capable of gains up to a factor two in throughput and a factor of more than three in mean delay and eight in maximum delay. The improvements on the throughput delay trade-off are also shown to be significant with regards to the previously developed singlepath AC-RLNC solution.

As a building block toward a simple and scalable solution to massive random access, we consider two-user multiple access with ZigZag decoding, with no need for any coordination or codebook differentiation. We derive closed-form bounds on the achievable sum-rates of the original ZigZag and a modified version of it, called double-zipper ZigZag, for both cases of perfect and imperfect channel state information (CSI). We also show that performances of both versions of ZigZag approach that of optimal coordinated time-sharing in the high signal to noise ratio regime, even in the presence of CSI errors.

In this paper we introduce Neural Network Coding (NNC), a data-driven approach to joint source and network coding. In NNC, the encoders at each source and intermediate node, as well as the decoder at each destination node, are neural networks which are all trained jointly for the task of communicating correlated sources through a network of noisy point-to-point links. The NNC scheme is application-specific and makes use of a training set of data, instead of making assumptions on the source statistics. In addition, it can adapt to any arbitrary network topology and power constraint. We show empirically that, for the task of transmitting MNIST images over a network, the NNC scheme shows improvement over baseline schemes, especially in the low-SNR regime.

Maximum Likelihood (ML) decoding of forward error correction codes is known to be optimally accurate, but is not used in practice as it proves too challenging to efficiently implement. Here we propose a development of a previously described hard detection ML decoder called Guessing Random Additive Noise Decoding (GRAND). We introduce Soft GRAND (SGRAND), a ML decoder that fully avails of soft detection information and is suitable for use with any arbitrary high-rate, short-length block code. We assess SGRAND's performance on Cyclic Redundancy Check (CRC)-aided Polar (CA-Polar) codes, which will be used for all control channel communication in 5G New Radio (NR), comparing its accuracy with CRC-Aided Successive Cancellation List decoding (CA-SCL), a state-of-the-art soft-information decoder specific to CA-Polar codes.

In network function computation is as a means to reduce the required communication flow in terms of number of bits transmitted per source symbol. However, the rate region for the function computation problem in general topologies is an open problem, and has only been considered under certain restrictive assumptions (e.g. tree networks, linear functions, etc.). In this paper, we propose a new perspective for distributing computation, and formulate a flow-based delay cost minimization problem that jointly captures the costs of communications and computation. We introduce the notion of entropic surjectivity as a measure to determine how sparse the function is and to understand the limits of computation. Exploiting Little's law for stationary systems, we provide a connection between this new notion and the computation processing factor that reflects the proportion of flow that requires communications. This connection gives us an understanding of how much a node (in isolation) should compute to communicate the desired function within the network without putting any assumptions on the topology. Our analysis characterizes the functions only via their entropic surjectivity, and provides insight into how to distribute computation. We numerically test our technique for search, MapReduce, and classification tasks, and infer for each task how sensitive the processing factor to the entropic surjectivity is.

We introduce Noise Recycling, a method that enhances decoding performance of channels subject to correlated noise without joint decoding. The method can be used with any combination of codes, code-rates and decoding techniques. In the approach, a continuous realization of noise is estimated from a lead channel by subtracting its decoded output from its received signal. This estimate is then used to improve the accuracy of decoding of an orthogonal channel that is experiencing correlated noise. In this design, channels aid each other only through the provision of noise estimates post-decoding. In a Gauss-Markov model of correlated noise, we constructively establish that noise recycling employing a simple successive order enables higher rates than not recycling noise. Simulations illustrate noise recycling can be employed with any code and decoder, and that noise recycling shows Block Error Rate (BLER) benefits when applying the same predetermined order as used to enhance the rate region. Finally, for short codes we establish that an additional BLER improvement is possible through noise recycling with racing, where the lead channel is not pre-determined, but is chosen on the fly based on which decoder completes first.

We propose to exploit the structure of the correlation between two random variables X and Y via a relaxation on the Common Information problem of Gács and Körner (GK Common Information). Consider two correlated sources X and Y generated from a joint distribution PX,Y. We study embeddings of X into discrete random variables U, such that H(U|Y) ≤ δ, while maximizing I(X; U). When δ = 0, this reduces to the GK Common Information problem. However, unlike the GK Common Information, which is known to be zero for many pairs of random variables (X, Y), we show that this relaxation allows to capture the structure in the correlation between X and Y for a much broader range of joint distributions, and showcase applications for some problems in multi-terminal information theory.

We study the performance of a coded point-to-point multi-path (MP) packet erasure channel (PEC) network model consisting of one sender (Tx) and one receiver (Rx). A network coded discrete water filling (DWF) scheduler is the core invention of this work. We provide an optimization framework to allocate coded packets over multiple network paths of varying channel conditions while minimizing the transmission delay. Applying the DWF framework to a feedback-based protocol shows significant throughput gains, delay and efficiency improvements compared to single path (SP) systems: In an example network with 4 paths we improve the transmission rate by a factor up to 2. This is not only beneficial for throughput-demanding applications such as large file downloads, but also for real-time systems such as livevideo streams which require low-latency environments. Moreover, we provide the optimization formulation for the DWF algorithm and a low-complexity implementation. The presented findings pave the way for efficient scheduling in next-generation transmission protocols for network coded MP and mesh networks.

In this work, we propose an erasure coding-based protocol that implements a key-value store with atomicity and near-optimal storage cost. Our protocol supports concurrent read and write operations while tolerating asynchronous communication and crash failures of any client and some fraction of servers. One novel feature is a tunable knob between the number of supported concurrent operations, availability, and storage cost. We implement our protocol into Cassandra, namely Cassan-drEAS (Cassandra + Erasure-coding Atomic Storage). Extensive evaluation using YCSB on Google Cloud Platform shows that CassandrEAS incurs moderate penalty on latency and throughput, yet saves significant amount of storage space.

We present a wideband time frequency coding scheme which combines the impulsive frequency shift keying scheme, shown to achieve the additive white Gaussian noise channel capacity in the wideband regime, with pulse position modulation. This coding scheme allows for information to be encoded in the position of the signal, which impulsive frequency shift keying does not take advantage of. We show that this scheme achieves rates which are comparable with the additive white Gaussian noise channel capacity upper bound, and performs well under a wide range of fading statistics and bandwidths. We show that our proposed scheme outperforms the impulsive frequency shift keying in lower bandwidths, even without optimization of the duty cycle. The scheme is also shown to perform similarly to impulsive frequency shift keying with smaller duty cycles in the wideband regime, indicating that continually decreasing duty cycles are not necessary to achieve rates on the order of additive white Gaussian noise channel capacity. We also discuss comparisons with other spread-spectrum signaling methods under noncoherent fading.

We propose a novel adaptive and causal random linear network coding (AC-RLNC) algorithm with forward error correction (FEC) for a point-to-point communication channel with delayed feedback. AC-RLNC is adaptive to the channel condition, that the algorithm estimates, and is causal, as coding depends on the particular erasure realizations, as reflected in the feedback acknowledgments. Specifically, the proposed model can learn the erasure pattern of the channel via feedback acknowledgments, and adaptively adjust its retransmission rates using a priori and posteriori algorithms. By those adjustments, AC-RLNC achieves the desired delay and throughput, and enables transmission with zero error probability. We upper bound the throughput and the mean and maximum in order delivery delay of AC-RLNC, and prove that for the point to point communication channel in the non-asymptotic regime the proposed code may achieve more than 90% of the channel capacity. To upper bound the throughput we utilize the minimum Bhattacharyya distance for the AC-RLNC code. We validate those results via simulations. We contrast the performance of AC-RLNC with the one of selective repeat (SR)-ARQ, which is causal but not adaptive, and is a posteriori. Via a study on experimentally obtained commercial traces, we demonstrate that a protocol based on AC-RLNC can, vis-à-vis SR-ARQ, double the throughput gains, and triple the gain in terms of mean in order delivery delay when the channel is bursty. Furthermore, the difference between the maximum and mean in order delivery delay is much smaller than that of SR-ARQ. Closing the delay gap along with boosting the throughput is very promising for enabling ultra-reliable low-latency communications (URLLC) applications.

According to recent empirical studies, a majority of users have the same, or very similar, passwords across multiple password-secured online services. This practice can have disastrous consequences, as one password being compromised puts all the other accounts at much higher risk. Generally, an adversary may use any side-information he/she possesses about the user, be it demographic information, password reuse on a previously compromised account, or any other relevant information to devise a better brute-force strategy (so called targeted attack). In this work, we consider a distributed brute-force attack scenario in which m adversaries, each observing some side information, attempt breaching a password secured system. We compare two strategies: an uncoordinated attack in which the adversaries query the system based on their own side-information until they find the correct password, and a fully coordinated attack in which the adversaries pool their side-information and query the system together. For passwords X of length n, generated independently and identically from a distribution PX, we establish an asymptotic closed-form expression for the uncoordinated and coordinated strategies when the side-information Y(m) are generated independently from passing X through a memoryless channel PY|X, as the length of the password n goes to infinity. We illustrate our results for binary symmetric channels and binary erasure channels, two families of side-information channels which model password reuse. We demonstrate that two coordinated agents perform asymptotically better than any finite number of uncoordinated agents for these channels, meaning that sharing side-information is very valuable in distributed attacks.

By extending the traditional store-and-forward mechanism, network coding has the capability to improve a network's throughput, robustness, and security. Given the fundamentally different packet processing required by this new paradigm and the inflexibility of hardware, existing solutions are based on software. As a result, they have limited performance and scalability, creating a barrier to its wide-spread adoption. By leveraging the recent advances in programmable networking hardware, in this paper we propose a random linear network coding data plane written in P4, as a first step towards a production-level platform. Our solution includes the ability to combine the payload of multiple packets and of executing the required Galois field operations, and shows promise to be practical even under the strict memory and processing constraints of switching hardware.

In future content-centric networks, content is identified independently of its location. From an end-user's perspective, individual storage systems dissolve into a seemingly omnipresent structureless 'storage fog'. Content should be delivered oblivious of the network topology, using multiple storage systems simultaneously, and at minimal coordination overhead. Prior works have addressed the advantages of error correction coding for distributed storage and content delivery separately. This work takes a comprehensive approach to highlighting the tradeoff between storage overhead and transmission overhead in uncoordinated content delivery from multiple coded storage systems. Our contribution is twofold. First, we characterize the tradeoff between storage and transmission overhead when all participating storage systems employ the same code. Second, we show that the resulting stark inefficiencies can be avoided when storage systems use diverse codes. What is more, such code diversity is not just technically desirable, but presumably will be the reality in the increasingly heterogeneous networks of the future. To this end, we show that a mix of Reed-Solomon, low-density parity-check and random linear network codes achieves close-to-optimal performance at minimal coordination and operational overhead.

In this paper, we propose a selective-repeat (SR) automatic repeat-request (ARQ) model for multi-source download scenarios and analyze their useful throughput that we refer to as goodput. The multi-source scenario comprises a set of transmitters that send packets to a receiver. We characterize the forward channels from the transmitters to the receiver via a general hidden Markov model (HMM) and assume that the reverse channels from the receiver to the transmitter are lossless. To find the average goodput of the network, we exploit the probability-generation function. We consider different packet transmission schemes, including uncoded random, network coded and sliding window-based network coded packets, and contrast their performance. Our calculations show that using network coding in a multi-source scenario can increase the average goodput, while sliding window-based coding may also archive the theoretical maximum goodput. We show that our multi-source approach avoids the straggler problem, therefore adding more transmitters to the network increases its throughout and the system does not get limited by the weakest transmitter. We also verify our analytic results with extensive simulations.

Emulating a shared atomic, read/write storage system is a fundamental problem in distributed computing. Replicating atomic objects among a set of data hosts was the norm for traditional implementations (e.g., [6]) in order to guarantee the availability and accessibility of the data despite host failures. As replication is highly storage demanding, recent approaches suggested the use of erasure-codes to offer the same fault-tolerance while optimizing storage usage at the hosts. Initial works focused on a fix set of data hosts. To guarantee longevity and scalability, a storage service should be able to dynamically mask hosts failures by allowing new hosts to join, and failed host to be removed without service interruptions. This work presents the first erasure-code based atomic algorithm, called ARES, which allows the set of hosts to be modified in the course of an execution. ARES is composed of three main components: (i) a reconfiguration protocol, (ii) a read/write protocol, and (iii) a set of data access primitives. The design of ARES is modular and is such to accommodate the usage of various erasure-code parameters on a per-configuration basis. We provide bounds on the latency of read/write operations and analyze the storage and communication costs of the ARES algorithm.

We recently introduced a noise-centric algorithm, Guessing Random Additive Noise Decoding (GRAND), that identifies a Maximum Likelihood (ML) decoding for arbitrary code-books. GRAND has the unusual property that its complexity decreases as code-book rate increases. Here we provide an extension to GRAND, soft-GRAND (SGRAND), that incorporates soft detection symbol reliability information and identifies a ML decoding in that context. In particular, we assume symbols received from the channel are declared to be error free or to have been potentially subject to additive noise. SGRAND inherits desirable properties of GRAND, including being capacity achieving when used with random code-books, and having a complexity that reduces as the code-rate increases.

In this paper we consider the problem of encoding data into repeat-free sequences in which sequences are imposed to contain any k-tuple at most once (for predefined k). First, the capacity and redundancy of the repeat-free constraint are calculated. Then, an efficient algorithm, which uses a single bit of redundancy, is presented to encode length-n sequences for k = 2 + 2 log n. This algorithm is then improved to support any value of k of the form k = a log n, for 1 <; a ≤ 2, while its redundancy is o(n). Lastly, we also calculate the capacity of this constraint when combined with local constraints which are given by a constrained system.

We propose a decentralized spatial soft-core cache placement (SSCC) policy for wireless networks. SSCC yields a spatially balanced sampling via negative dependence across caches, and can be tuned to satisfy cache size constraints with high probability. Given a desired cache hit probability, we compare the 95% confidence intervals of the required cache sizes for independent placement, hard-core placement and SSCC policies. We demonstrate that in terms of the required cache storage size, SSCC can provide up to more than 180% and 100% gains with respect to the independent and hard-core placement policies, respectively. SSCC can be used to enable proximity-based applications such as device-to-device communications and peer-to-peer networking as it promotes the item diversity and reciprocation among the nodes.

Quantization allows physical signals to be processed using digital devices. Quantizers are commonly implemented using analog-to-digital converters (ADCs), which operate in a serial and scalar manner and are designed to yield an accurate digital representation of the observed signal. However, in many practical scenarios quantization is part of a system whose task is not to recover the observed signal, but some function of it. Recent works have shown that properly designed task-based quantizers, which include pre-quantization analog combining as well as digital processing, can achieve notable gains in recovering linear functions of the observations. In this work we focus on quantization for the task of recovering quadratic functions. Our analysis is based on principal inertia components (PICs), which form a basis for decomposing the statistical dependence between random quantities. Using PICs, we identify a practical structure of the pre-quantization mapping for recovering quadratic functions, which allows us to design a task-based quantization system capable of accurately estimating these functions. Our numerical study demonstrates that, when using scalar ADCs, notable performance gains that can be achieved using the proposed design over intuitive approaches such as quantizing the quadratic function directly as well as task-ignorant quantization.

Sampling enables physical signals to be processed using digital hardware. When multiple signals are sampled, the spatial correlation between them may be utilized to reduce the overall reconstruction error. In this work we study joint sampling and reconstruction of multiple correlated stochastic sources, exploiting their correlation to improve recovery. We derive the achievable reconstruction error and the corresponding sampling system for arbitrary sampling rates and spectral structures. The proposed system minimizes the error when sampling below the Nyquist rate by preserving only the most dominant spatial eigenmodes aliased to each frequency. Using this characterization, we obtain sufficient conditions for error free recovery. We also discuss a distributed sampling setting, where each signal is acquired separately, while reconstruction is performed jointly. We characterize conditions under which distributed sampling performs as well as joint sampling. Our numerical results illustrate that joint sampling can achieve negligible reconstruction error using low sampling rates when the signals exhibit notable spatial correlation, and demonstrate that properly exploiting this correlation can dramatically improve reconstruction accuracy.

In this work we investigate the capacity of multilayer relaying networks operating over multipath fading channels under a non-coherent wideband regime and physically degraded broadcast stages. First, based on hyper-graph models and network equivalence techniques, we derive an upper bound on the network capacity. Then, by considering a peaky, frequency-shift keying signaling scheme, we establish a set of point-to-point achievable rates for each communication link in the network. Finally, by capitalizing on this set of rates we devise an achievable transmission scheme for the entire network via network coding. Remarkably, it turns out that this achievable rate for the network coincides with its upper bound capacity. In other words, these results give ultimately the capacity of the investigated network.

One-shot inference is used in machine translation today. In practice, the output probability distribution is not concentrated since there might be multiple valid translations. Therefore, we propose to use a multi-shot inference mechanism in this paper. We analyze the Markovian property of sequence to sequence (seq2seq) model. Based on a large deviation principle satisfied by guesswork on Markov process, we derive theoretical upper bounds on the accuracy of the seq2seq model with single correct answer under one-shot inference and multi-shot inference. We establish analogous bounds when there are multiple correct answers in translating. We also discuss the extension of the results to translation with distortion tolerance.

We study the problem of mismatched guesswork, where we evaluate the number of symbols y ∈ Y which have higher likelihood than X ~ μ according to a mismatched distribution μ. We discuss the role of the tilted/exponential families of the source distribution μ and of the mismatched distribution ν. We show that the value of guesswork can be characterized using the tilted family of the mismatched distribution v, while the probability of guessing is characterized by an exponential family which passes through μ. Using this characterization, we demonstrate that the mismatched guesswork follows a large deviation principle (LDP), where the rate function is described implicitly using information theoretic quantities. We apply these results to one-to-one source coding (without prefix free constraint) to obtain the cost of mismatch in terms of average codeword length. We show that the cost of mismatch in one-to-one codes is no larger than that of the prefix-free codes, i.e., D(μ||ν). Further, the cost of mismatch vanishes if and only if ν lies on the tilted family of the true distribution μ, which is in stark contrast to the prefix-free codes. These results imply that one-to-one codes are inherently more robust to mismatch.

Overlapping clusters are common in models of many practical data-segmentation applications. Suppose we are given $n$ elements to be clustered into $k$ possibly overlapping clusters, and an oracle that can interactively answer queries of the form ``do elements $u$ and $v$ belong to the same cluster?'' The goal is to recover the clusters with minimum number of such queries. This problem has been of recent interest for the case of disjoint clusters. In this paper, we look at the more practical scenario of overlapping clusters, and provide upper bounds (with algorithms) on the sufficient number of queries. We provide algorithmic results under both arbitrary (worst-case) and statistical modeling assumptions. Our algorithms are parameter free, efficient, and work in the presence of random noise. We also derive information-theoretic lower bounds on the number of queries needed, proving that our algorithms are order optimal. Finally, we test our algorithms over both synthetic and real-world data, showing their practicality and effectiveness.

In this work, we propose FLECKS, an algorithm which implements atomic memory objects in a multi-writer multi-reader (MWMR) setting in asynchronous networks and server failures. FLECKS substantially reduces storage and communication costs over its replication-based counterparts by employing erasure-codes. FLECKS outperforms the previously proposed algorithms in terms of the metrics that to deliver good performance such as storage cost per object, communication cost a high fault-tolerance of clients and servers, guaranteed liveness of operation, and a given number of communication rounds per operation, etc. We provide proofs for liveness and atomicity properties of FLECKS and derive worst-case latency bounds for the operations. We implemented and deployed FLECKS in cloud-based clusters and demonstrate that FLECKS has substantially lower storage and bandwidth costs, and significantly lower latency of operations than the replication-based mechanisms.

We propose a Coded selective-repeat ARQ protocol with cumulative feedback, by building on the uncoded baseline scheme for ARQ, developed by Ausavapattanakun and Nosratinia. Our method leverages discrete-time queuing and coding theory to analyze the performance of the proposed data transmission method. We incorporate forward error-correction (FEC) to reduce in-order delivery delay, and exploit a matrix signal-flow graph approach to analyze the throughput and delay. We demonstrate and contrast the performance of the Coded ARQ protocol with that of the uncoded ARQ scheme, with minimum coding, i.e., with a sliding window of size 2. Coded ARQ can provide gains up to about 40% in terms of throughput. It also provides delay guarantees, and is robust to various challenges such as imperfect and delayed feedback, burst erasures, and round-trip time fluctuations.

Future 5G systems will need to support ultra-reliable low-latency communications scenarios. From a latency-reliability viewpoint, it is inefficient to rely on average utility-based system design. Therefore, we introduce the notion of guaranteeable delay which is the average delay plus three standard deviations of the mean. We investigate the trade-off between guaranteeable delay and throughput for the point-to-point wireless erasure links with unreliable and delayed feedback, by bringing together signal flow techniques to the area of coding. We use tiny codes, i.e., sliding window by coding with just 2 packets, and design three variations of selective-repeat ARQ protocols, by building on the baseline scheme, i.e., uncoded ARQ, developed by Ausavapattanakun and Nosratinia: (i) Hybrid ARQ with soft combining at the receiver; (ii) cumulative feedback-based ARQ without rate adaptation; and (iii) coded ARQ with rate adaptation based on the cumulative feedback. Contrasting the performance of these protocols with uncoded ARQ, we demonstrate that the HARQ performs only slightly better, the cumulative feedback-based ARQ does not provide significant throughput while it has a better average delay, and the Coded ARQ can provide gains up to about 40% in terms of throughput. The Coded ARQ also provides delay guarantees, and is robust to various challenges such as imperfect and delayed feedback, burst erasures, and round-trip time fluctuations. This feature may be preferable for meeting the strict end-to-end latency and reliability requirements of the future use cases of ultra-reliable low-latency communications in 5G, such as mission-critical communications and industrial control for critical control messaging.

The principal mission of multi-source multicast (MSM) is to disseminate all messages from all sources in a network to all destinations. MSM is utilized in numerous applications. In many of them, securing the messages disseminated is critical. A common secure model is to consider a network where there is an eavesdropper which is able to observe a subset of the network links, and seeks a code which keeps the eavesdropper ignorant regarding all the messages. While this is solved when all messages are located at a single source, secure MSM (SMSM) is an open problem, and the rates required are hard to characterize in general. In this paper, we consider individual security, which promises that the eavesdropper has zero mutual information with each message individually, or, more generally, with sub sets of messages. We completely characterize the rate region for SMSM under individual security, and show that such a security level is achievable at the full capacity of the network, that is, the cut-set bound is the matching converse, similar to non-secure MSM. Moreover, we show that the field size is similar to non-secure MSM and does not have to be larger due to the security constraint.

In September 2017, McAffee Labs quarterly report estimated that brute force attacks represent 20\% of total network attacks, making them the most prevalent type of attack ex-aequo with browser based vulnerabilities. These attacks have sometimes catastrophic consequences, and understanding their fundamental limits may play an important role in the risk assessment of password-secured systems, and in the design of better security protocols. While some solutions exist to prevent online brute-force attacks that arise from one single IP address, attacks performed by botnets are more challenging. In this paper, we analyze these distributed attacks by using a simplified model. Our aim is to understand the impact of distribution and asynchronization on the overall computational effort necessary to breach a system. Our result is based on Guesswork, a measure of the number of queries (guesses) required of an adversary before a correct sequence, such as a password, is found in an optimal attack. Guesswork is a direct surrogate for time and computational effort of guessing a sequence from a set of sequences with associated likelihoods. We model the lack of synchronization by a worst-case optimization in which the queries made by multiple adversarial agents are received in the worst possible order for the adversary, resulting in a min-max formulation. We show that, even without synchronization, and for sequences of growing length, the asymptotic optimal performance is achievable by using randomized guesses drawn from an appropriate distribution. Therefore, randomization is key for distributed asynchronous attacks. In other words, asynchronous guessers can asymptotically perform brute-force attacks as efficiently as synchronized guessers.

Given a collection of strings, each with an associated probability of occurrence, the guesswork of each of them is their position in a list ordered from most likely to least likely, breaking ties arbitrarily. The guesswork is central to several applications in information theory: average guesswork provides a lower bound on the expected computational cost of a sequential decoder to decode successfully the transmitted message; the complementary cumulative distribution function of guesswork gives the error probability in list decoding; the logarithm of guesswork is the number of bits needed in optimal lossless one-to-one source coding; and the guesswork is the number of trials required of an adversary to breach a password protected system in a brute-force attack. In this paper, we consider memoryless string sources that generate strings consisting of independent and identically distributed characters drawn from a finite alphabet, and characterize their corresponding guesswork. Our main tool is the tilt operation on a memoryless string source. We show that the tilt operation on a memoryless string source parametrizes an exponential family of memoryless string sources, which we refer to as the tilted family of the string source. We provide an operational meaning to the tilted families by proving that two memoryless string sources result in the same guesswork on all strings of all lengths if and only if their respective categorical distributions belong to the same tilted family. Establishing some general properties of the tilt operation, we generalize the notions of weakly typical set and asymptotic equipartition property to tilted weakly typical sets of different orders. We use this new definition to characterize the large deviations for all atypical strings and characterize the volume of tilted weakly typical sets of different orders. We subsequently build on this characterization to prove large deviation bounds on guesswork and provide an accurate approximation of its probability mass function.

We introduce a new algorithm for realizing maximum likelihood (ML) decoding for arbitrary codebooks in discrete channels with or without memory, in which the receiver rank-orders noise sequences from most likely to least likely. Subtracting noise from the received signal in that order, the first instance that results in a member of the codebook is the ML decoding. We name this algorithm GRAND for Guessing Random Additive Noise Decoding. We establish that GRAND is capacity-achieving when used with random codebooks. For rates below capacity, we identify error exponents, and for rates beyond capacity, we identify success exponents. We determine the scheme's complexity in terms of the number of computations that the receiver performs. For rates beyond capacity, this reveals thresholds for the number of guesses by which, if a member of the codebook is identified, that it is likely to be the transmitted code word. We introduce an approximate ML decoding scheme where the receiver abandons the search after a fixed number of queries, an approach we dub GRANDAB, for GRAND with ABandonment. While not an ML decoder, we establish that the algorithm GRANDAB is also capacity-achieving for an appropriate choice of abandonment threshold, and characterize its complexity, error, and success exponents. Worked examples are presented for Markovian noise that indicate these decoding schemes substantially outperform the brute force decoding approach.

The main goal in group testing is to recover a small subset of defective items from a larger population while efficiently reducing the total number of (possibly noisy) required tests/measurements. Under the assumption that the input-output statistical relationship (i.e., channel law) is known to the recovery algorithm, the fundamental as well as the computational limits of the group testing problem are relatively better understood than when these statistical relationships are unknown. Practical considerations, however, render this assumption inapplicable, and “blind” recovery/estimation procedures, independent of the input-output statistics, are desired. In this paper, we analyze the fundamental limits of a general noisy group testing problem, when this relationship is unknown. Specifically, in the first part of this paper, we propose an efficient scheme, based on the idea of separate-decoding of items (where each item is recovered separately), for which we derive sufficient conditions on the number of tests required for exact recovery. The difficulty in obtaining these conditions stems from the fact that we allow the number of defective items to grow with the population size, which in turn requires delicate concentration analysis of certain probabilities. Furthermore, we show that in several scenarios, our proposed scheme achieves the same performance as that of the corresponding non-blind recovery algorithm (where the input-output statistics are known), implying that the proposed blind scheme is robust/universal. Finally, in the second part of this paper, we propose also an inefficient combinatorial-based scheme (or, “joint-decoding”), for which we derive similar sufficient conditions.

This paper considers the problem of channel coding over Gaussian intersymbol interference (ISI) channels with a given decoding rule. Specifically, it is assumed that the mismatched decoder has an incorrect assumption on the channel impulse response. The mismatch capacity is the highest achievable rate for a given decoding rule. The existing achievable rates for channels and decoding metrics with memory (as in our model) are currently available only in the form of multi-letter expressions that cannot be calculated. Consequently, they provide little insight on the mismatch problem. In this paper, we derive the computable formulas of achievable rates and discuss some implications of our results. Our achievable rates are based on two ensembles: the ensemble of codewords generated by an autoregressive process and the ensemble of codewords drawn uniformly over a “type class” of real-valued sequences. We provide a few numerical results of our achievable rates, as functions of the mismatched ISI parameters. Finally, we compare our results with universal decoders which are designed outside the true class of channels that we consider in this paper.

We study the central problem in data privacy: how to share data with an analyst while providing both privacy and utility guarantees to the user that owns the data. In this setting, we present an estimation-theoretic analysis of the privacy-utility trade-off (PUT). Here, an analyst is allowed to reconstruct (in a mean-squared error sense) certain functions of the data (utility), while other private functions should not be reconstructed with distortion below a certain threshold (privacy). We demonstrate how chi-square information captures the fundamental PUT in this case and provide bounds for the best PUT. We propose a convex program to compute privacy-assuring mappings when the functions to be disclosed and hidden are known a priori and the data distribution is known. We derive lower bounds on the minimum mean-squared error of estimating a target function from the disclosed data and evaluate the robustness of our approach when an empirical distribution is used to compute the privacy-assuring mappings instead of the true data distribution. We illustrate the proposed approach through two numerical experiments.

We propose a cumulative feedback-based ARQ (CF ARQ) protocol for a sliding window of size 2 over packet erasure channels with unreliable feedback. We exploit a matrix signal-flow graph approach to analyze probability-generating functions of transmission and delay times. Contrasting its performance with that of the uncoded baseline scheme for ARQ, developed by Ausavapattanakun and Nosratinia, we demonstrate that CF ARQ can provide significantly less average delay under bursty feedback, and gains up to about 20% in terms of throughput. We also outline the benefits of CF ARQ under burst errors and asymmetric channel conditions. The protocol is more predictable across statistics, hence is more stable. This can help design robust systems when feedback is unreliable. This feature may be preferable for meeting the strict end-to-end latency and reliability requirements of future use cases of ultra-reliable low-latency communications in 5G, such as mission-critical communications and industrial control for critical control messaging.

Given a large wireless network consisting of randomly deployed nodes, where each of the nodes wants to transmit to a random destination node within the network at some equal rate, how fast can the sum rate grow as the number of nodes scales up at fixed density? This question is important because it captures the bottleneck of message exchanging among randomly deployed Internet-of-Things (IoT) devices, and it models nicely the wireless backhaul communication among access points or within airborne communication systems. Previous work has shown that, given an extended network with fixed density, multihop routing based approach provides sum rate that scales at most as the square root of network size, where as hierarchical cooperation protocols have the potential to support linear scaling. With limited power, the SNR decreases at least inverse proportional to the network size, and therefore the benefit of hierarchical cooperation will be curbed by the combined effects of path loss and local communication cost. We show in this paper how the path loss and local cooperation cost reshape the capacity scaling law results.

We introduce a new algorithm for Maximum Likelihood (ML) decoding for channels with memory. The algorithm is based on the principle that the receiver rank orders noise sequences from most likely to least likely. Subtracting noise from the received signal in that order, the first instance that results in an element of the code-book is the ML decoding. In contrast to traditional approaches, this novel scheme has the desirable property that it becomes more efficient as the code-book rate increases. We establish that the algorithm is capacity achieving for randomly selected code-books. When the code-book rate is less than capacity, we identify asymptotic error exponents as the block length becomes large. When the code-book rate is beyond capacity, we identify asymptotic success exponents. We determine properties of the complexity of the scheme in terms of the number of computations the receiver must perform per block symbol. Worked examples are presented for binary memoryless and Markovian noise. These demonstrate that block-lengths that offer a good complexity-rate tradeoff are typically smaller than the reciprocal of the bit error rate.

The main goal in group testing is to recover a small subset of defective items from a larger population, while efficiently reducing the total number of (possibly noisy) required tests/measurements. In this paper, we analyze the fundamental limits of a general noisy group testing problem when the channel law is unknown. Specifically, we obtain sufficient conditions on the number of tests required for exact recovery using two decoders; the first is based on joint-decoding (inefficient), and the second is a based on separate-decoding (efficient). We show that in several scenarios, our decoders achieve the same performance as if the channel was known, implying that the proposed decoders are robust/universal.

The capacity-achieving input distribution of the complex Gaussian channel with both average- and peak-power constraint is known to have a discrete amplitude and a continuous, uniformly-distributed, phase. Practical considerations, however, render the continuous phase inapplicable. This work studies the backoff from capacity induced by discretizing the phase of the input signal. A sufficient condition on the total number of quantization points that guarantees an arbitrarily small backoff is derived, and constellations that attain this guaranteed performance are proposed.

Let Tε be the noise operator acting on Boolean functions f:{0,1}n→{0,1}, where ε ∈ [0,1/2] is the noise parameter. Given and the mean \mathbbEf, which Boolean function f maximizes the p-th moment \mathbbE(Tεf)p?Our findings are: in the low noise scenario, i.e., ε is small, the maximum is achieved by the lexicographical function; in the high noise scenario, i.e., ε is close to 1/2, the maximum is achieved by Boolean functions with the maximal degree-1 Fourier weight; and when p is an integer, the maximum is achieved by some monotone function, and in particular, among balanced Boolean functions, the maximum is achieved by any function which is 0 on all strings with fewer than n/2 1,s when p is large enough. Our results recover Mossel and O'Donnell's results about the problem of non-interactive correlation distillation, and confirm a conjecture of Courtade and Kumar on the most informative Boolean function in the low noise and high noise regimes. We also observe that Courtade and Kumar's conjecture is equivalent to that the dictator function maximizes \mathbbE(Tεf)pfor p close to 1.

The problem of storing permutations in a distributed manner arises in several common scenarios, such as efficient updates of a large, encrypted, or compressed data set. This problem may be addressed in either a combinatorial or a coding approach. The former approach boils down to presenting large sets of permutations with locality, that is, any symbol of the permutation can be computed from a small set of other symbols. In the latter approach, a permutation may be coded in order to achieve locality. This paper focuses on the combinatorial approach. We provide upper and lower bounds for the maximal size of a set of permutations with locality, and provide several simple constructions which attain the upper bound. In cases where the upper bound is not attained, we provide alternative constructions using Reed-Solomon codes, permutation polynomials, and multi-permutations.

Motivated by applications to delivery of dynamically updated, but correlated data in settings such as content distribution networks, and distributed file sharing systems, we study a single source multiple destination network coded multicast problem in a cache-aided network. We focus on models where the caches are primarily located near the destinations and the source has no cache. The source observes a sequence of correlated frames and is expected to do frame-by-frame encoding with no access to prior frames. We present a novel scheme that shows how the caches can be advantageously used to decrease the overall cost of multicast, even though the source encodes without access to past data. Our cache design and update scheme works with any choice of network code designed for a corresponding cache-less network, is largely decentralized, and works for an arbitrary network. We study a convex relation of the optimization problem that results from the overall cost function. The results of the optimization problem determine the rate allocation and caching strategies. Numerous simulation results are presented to substantiate the theory developed.

We study a generalization of the setting of regenerating codes, motivated by applications to storage systems consisting of clusters of storage nodes. There are n clusters in total, with m nodes per cluster. A data file is coded and stored across the mn nodes, with each node storing α symbols. For availability of data, we require that the file be retrievable by downloading the entire content from any subset of k clusters. Nodes represent entities that can fail. We distinguish between intra-cluster and inter-cluster bandwidth (BW) costs during node repair. Node-repair in a cluster is accomplished by downloading β symbols each from any set of d other clusters, dubbed remote helper clusters, and also up to α symbols each from any set of I surviving nodes, dubbed local helper nodes, in the host cluster. We first identify the optimal trade-off between storage-overhead and inter-cluster repair-bandwidth under functional repair, and also present optimal exact-repair code constructions for a class of parameters. The new trade-off is strictly better than what is achievable via space-sharing existing coding solutions, whenever ℓ > 0. We then obtain sharp lower bounds on the necessary intracluster repair BW to achieve optimal trade-off. Under functional repair, random linear network codes (RLNCs) simultaneously optimize usage of both inter- and intra-cluster repair BW; simulation results based on RLNCs suggest optimality of the bounds on intra-cluster repair-bandwidth. Our bounds reveal the interesting fact that, while it is beneficial to increase the number of local helper nodes I in order to improve the storage-vs-inter-cluster-repair-BW trade-off, increasing I not only increases intracluster BW in the host-cluster, but also increases the intra-cluster BW in the remote helper clusters. We also analyze resilience of the clustered storage system against passive eavesdropping by providing file-size bounds and optimal code constructions.

We consider a communication problem in which an update of the source message needs to be conveyed to one or more distant receivers that are interested in maintaining specific linear functions of the source message. The setting is one in which the updates are sparse in nature, and where neither the source nor the receiver(s) is aware of the exact difference vector, but only know the amount of sparsity that is present in the difference vector. Under this setting, we are interested in devising linear encoding and decoding schemes that minimize the communication cost involved. We show that the optimal solution to this problem is closely related to the notion of maximally recoverable codes (MRCs), which were originally introduced in the context of coding for storage systems. In the context of storage, MRCs guarantee optimal erasure protection when the system is partially constrained to have local parity relations among the storage nodes. In our problem, we show that optimal solutions exist if and only if MRCs of certain kind (identified by the desired linear functions) exist. We consider point-to-point and broadcast versions of the problem and identify connections to MRCs under both these settings. For the point-to-point setting, we show that our linear-encoder-based achievable scheme is optimal even when non-linear encoding is permitted. The theory is illustrated in the context of updating erasure coded storage nodes. We present examples based on modern storage codes, such as the minimum bandwidth regenerating codes.

Parallelism has become one of the key architectural features in 40-/100-/400-Gb Ethernet multi lane distribution (MLD) standards. The MLD packetizes and distributes traffic adaptively over parallel lanes and maps them to parallel network interfaces for wide area transmission, typically over optical networks. As such, the MLD creates not only new network topology abstractions but also enables modular implementations of various new features to improve the system performance. In this paper, we study the performance of the parallelized Ethernet in combination with erasure coding and more specifically random linear network coding (RLNC). We present a novel theoretical modeling framework, including the derivation of upper and lower bounds of differential delay and the resulting receiver queue size-a critical performance measure in the high-speed Ethernet. The results show benefits of a combined usage of parallelism and RLNC: with a proper set of design parameters, the differential delay and the receiver buffer size can be reduced significantly, while cross-layer design and path computation greatly simplified.

Although network coding has shown the potential to revolutionize networking and storage, its deployment has faced a number of challenges. Usual proposals involve two approaches. First, deploying a new protocol (e.g., Multipath Coded TCP), or retrofitting another one (e.g., TCP/NC) to deliver benefits to any application in a computer. However, incorporating new protocols to the Internet is a challenging and slow process. Second, deploying coding at the application layer, which forces each application to implement network coding. This paper proposes an alternative approach through the use of a network coded filesystem shim (NCFSS), where coded data is generated at the filesystem level supporting any application and any network protocol. Our design allows multiple sources of a content to serve data without coordination to a receiver over multiple data paths. Another interesting feature of our approach is that it allows caches in the network to store only a fraction of a specific content in coded form, but sharing the same object identification, i.e., it simplifies the signaling and search of coded content. We describe the NCFSS design and implementation using FUSE and carry out measurements using servers in six countries to demonstrate gains of two to five fold in download speed.

The principal mission of Multi-Source Multicast (MSM) is to disseminate all messages from all sources in a network to all destinations. MSM is utilized in numerous applications. In many of them, securing the messages disseminated is critical. A common secure model is to consider a network where there is an eavesdropper which is able to observe a subset of the network links, and seek a code which keeps the eavesdropper ignorant regarding all the messages. While this is solved when all messages are located at a single source, Secure MSM (SMSM) is an open problem, and the rates required are hard to characterize in general. In this paper, we consider Individual Security, which promises that the eavesdropper has zero mutual information with each message individually. We completely characterize the rate region for SMSM under individual security, and show that such a security level is achievable at the full capacity of the network, that is, the cut-set bound is the matching converse, similar to non-secure MSM. Moreover, we show that the field size is similar to non-secure MSM and does not have to be larger due to the security constraint.

This work introduces the particle-intensity channel (PIC) as a model for molecular communication systems and characterizes the properties of the optimal input distribution and the capacity limits for this system. In the PIC, the transmitter encodes information, in symbols of a given duration, based on the number of particles released, and the receiver detects and decodes the message based on the number of particles detected during the symbol interval. In this channel, the transmitter may be unable to control precisely the number of particles released, and the receiver may not detect all the particles that arrive. We demonstrate that the optimal input distribution for this channel always has mass points at zero and the maximum number of particles that can be released. We then consider diffusive particle transport, derive the capacity expression when the input distribution is binary, and show conditions under which the binary input is capacity-achieving. In particular, we demonstrate that when the transmitter cannot generate particles at a high rate, the optimal input distribution is binary.

Suppose that we wish to guess the realization x of a discrete random variable X taking values in a finite set, by asking sequential questions of the form “Is X is equal to x?” exhausting the elements of X until the answer is Yes. [1, 2]. If the distribution of X is known to the guesser, and the guesser has memory of his previous has memory of his previous queries then the best strategy is to guess in decreasing order of probabilities. In this paper, we consider the problem of a memoryless guesser, namely, each new guess is independent of the previous guesses. We consider also the scenario of a guesser with a bounded number of guesses. For both cases we derive the optimal guessing strategies, and show new connections to Rényi entropy.

This paper considers the problem of channel coding over Gaussian intersymbol interference (ISI) channels with a given (possibly suboptimal) metric decoding rule. Specifically, it is assumed that the mismatched decoder has incorrect knowledge of the ISI coefficients (or, the impulse response function). The mismatch capacity is the highest achievable rate for a given decoding rule. Unfortunately, existing lower bounds to the mismatch capacity for multi-letter channels and decoding metrics (or, channels and decoding metrics with memory), as in our model, are presented only in the form of multi-letter expressions, and thus cannot be calculated in practice. In this paper, we derive a computable single-letter lower bound to the mismatch capacity, and discuss some implications of our results.

We study a notion of guesswork, where multiple agents intend to launch a coordinated brute-force attack to find a single binary secret string, and each agent has access to side information generated through either a BEC or a BSC. The average number of trials required to find the secret string grows exponentially with the length of the string, and the rate of the growth is called the guesswork exponent. We compute the guesswork exponent for several multi-agent attacks. We show that a multi-agent attack reduces the guesswork exponent compared to a single agent, even when the agents do not exchange information to coordinate their attack, and try to individually guess the secret string using a predetermined scheme in a decentralized fashion. Further, we show that the guesswork exponent of two agents who do coordinate their attack is strictly smaller than that of any finite number of agents individually performing decentralized guesswork.

We study the trade-off between storage overhead and inter-cluster repair bandwidth in clustered storage systems, while recovering from multiple node failures within a cluster. A cluster is a collection of m nodes, and there are n clusters. For data collection, we download the entire content from any k clusters. For repair of t ≥ 2 nodes within a cluster, we take help from ℓ local nodes, as well as d helper clusters. We characterize the optimal trade-off under functional repair, and also under exact repair for the minimum storage and minimum inter-cluster bandwidth (MBR) operating points. Our bounds show the following interesting facts: 1) When t|(m - ℓ) the tradeoff is the same as that under t = 1, and thus there is no advantage in jointly repairing multiple nodes, 2) When tł(m - ℓ), the optimal file-size at the MBR point under exact repair can be strictly less than that under functional repair. 3) Unlike the case of t = 1, increasing the number of local helper nodes does not necessarily increase the system capacity under functional repair.

This paper considers the problem of transmitting digital data from a source reliably to a legitimate user, subjected to a wiretap at a receiver that employs a fixed decoding strategy. Specifically, we assume that the wiretapper views the same channel output as the legitimate user, but decodes the message using some fixed decoding strategy which might be mismatched with respect to the channel. This model aims to capture the natural situation in privacy where knowledge of the privacy mapping at the source can me modeled as channel statistics. In that case, all observers receive the same data, but have different levels of knowledge, or familiarity, regarding the observed user who uses a privacy mapping. We analyze two different security metrics; probability of error at the eavesdropper and semantic-security, and provide achievable rates under both criteria.

In this paper, we address the scheduling problem in wireless ad hoc networks by exploiting the computational advantage that comes when such scheduling problems can be represented by claw-free conflict graphs. It is possible to formulate a scheduling problem of network coded flows as finding maximum weighted independent set (MWIS) in the conflict graph of the network. We consider activation of hyperedges in a hypergraph to model a wireless broadcast medium. We show that the conflict graph of certain wireless ad hoc networks are claw-free. It is known that finding MWIS of a general graph is NP-hard, but in a claw-free conflict graph, it is possible to apply Minty's or Faenza et al.'s algorithms in polynomial time. We discuss our approach on some sample networks.

Motivated by emerging applications to the edge computing paradigm, we introduce a two-layer erasure-coded fault-tolerant distributed storage system offering atomic access for read and write operations. In edge computing, clients interact with an edge-layer of servers that is geographically near; the edge-layer in turn interacts with a back-end layer of servers. The edge-layer provides low latency access and temporary storage for client operations, and uses the back-end layer for persistent storage. Our algorithm, termed Layered Data Storage (LDS) algorithm, offers several features suitable for edge-computing systems, works under asynchronous message-passing environments, supports multiple readers and writers, and can tolerate f1 < n1/2 and f2 < n2/3 crash failures in the two layers having n1 and n2 servers, respectively. We use a class of erasure codes known as regenerating codes for storage of data in the back-end layer. The choice of regenerating codes, instead of popular choices like Reed-Solomon codes, not only optimizes the cost of back-end storage, but also helps in optimizing communication cost of read operations, when the value needs to be recreated all the way from the back-end. The two-layer architecture permits a modular implementation of atomicity and erasure-code protocols; the implementation of erasure-codes is mostly limited to interaction between the two layers. We prove liveness and atomicity of LDS, and also compute performance costs associated with read and write operations. In a system with n1 = Θ(n2), f1 = Θ(n1), f2 = Θ(n2), the write and read costs are respectively given by Θ(n1) and Θ(1) + n1 I(δ > 0). Here δ is a parameter closely related to the number of write operations that are concurrent with the read operation, and I(δ > 0) is 1 if δ > 0, and 0 if δ = 0. The cost of persistent storage in the back-end layer is Θ(1). The impact of temporary storage is minimally felt in a multi-object system running N independent instances of LDS, where only a small fraction of the objects undergo concurrent accesses at any point during the execution. For the multi-object system, we identify a condition on the rate of concurrent writes in the system such that the overall storage cost is dominated by that of persistent storage in the back-end layer, and is given by Θ(N).

In this paper, we consider the design of forward error correction tailored specifically for the low end-to-end latency requirements in 5G networks. We present experimental results that highlight a number of issues with conventional approaches and then introduce a new low delay code construction that achieves a superior throughput-delay tradeoff. We analyze its performance both mathematically and experimentally. The mathematical analysis of throughput and delay requires the development of a number of novel analytic tools based on both queuing and coding theories. We implement the low delay code and evaluate its performance in an experimental test bed.

We explore properties and applications of the principal inertia components (PICs) between two discrete random variables X and Y. The PICs lie in the intersection of information and estimation theory, and provide a fine-grained decomposition of the dependence between X and Y. Moreover, the PICs describe which functions of X can or cannot be reliably inferred (in terms of MMSE), given an observation of Y. We demonstrate that the PICs play an important role in information theory, and they can be used to characterize information-theoretic limits of certain estimation problems. In privacy settings, we prove that the PICs are related to the fundamental limits of perfect privacy.

Current approaches to the practical implementation of network coding are batch-based, and often do not use feedback, except possibly to signal completion of a file download. In this paper, the various benefits of using feedback in a network coded system are studied. It is shown that network coding can be performed in a completely online manner, without the need for batches or generations, and that such online operation does not affect the throughput. Although these ideas are presented in a single-hop packet erasure broadcast setting, they naturally extend to more general lossy networks, which employ network coding in the presence of feedback. The impact of feedback on sender-side queue size and receiver-side decoding delay is studied in an asymptotic sense as the traffic load approaches capacity. Different notions of decoding delay are considered, including an order-sensitive notion, which assumes that packets are useful only when delivered in order. Strategies for adaptive coding based on feedback are presented. Our scheme achieves throughput optimality and asymptotically optimal sender queue size and is conjectured to achieve asymptotically optimal in-order delivery delay for any number of receivers. This paper may be viewed as a natural extension of Automatic Repeat reQuest to coded networks.

The problem of one-way file synchronization, henceforth called “file updates”, is studied in this paper. Specifically, a client edits a file, where the edits are modeled by insertions and deletions (InDels). An old copy of the file is stored remotely at a data-centre, and is also available to the client. We consider the problem of throughput- and computationally-efficient communication from the client to the data-centre, to enable the data-centre to update its old copy to the newly edited file. Two models for the source files and edit patterns are studied: the random pre-edit sequence left-to-right random InDel (RPES-LtRRID) process, and the arbitrary pre-edit sequence arbitrary InDel (APES-AID) process. In both models, we consider the regime, in which the number of insertions and deletions is a small (but constant) fraction of the length of the original file. For both models, information-theoretic lower bounds on the best possible compression rates that enable file updates are derived (up to first order terms). Conversely, a simple compression algorithm using dynamic programming (DP) and entropy coding (EC), henceforth called DP-EC algorithm, achieves rates that are within constant additive gap (which diminishes as the alphabet size increases) to information-theoretic lower bounds for both models. For the RPES-LtRRID model, a dynamic-programming-run-length-compression (DP-RLC) algorithm is proposed, which achieves a compression rate matching the information-theoretic lower bound up to first order terms. Therefore, when the insertion and deletion probabilities are small (such that first order terms dominate), the achievable rate by DP-RLC is nearly optimal for the RPES-LtRRID model.

In this paper, we propose a new proactive recovery scheme against single edge failures for unicast connections in transport networks. The new scheme is a generalization of diversity coding where the source data AB are split into two parts A and B and three data flows A, B, and their exclusive OR (XOR) A⊕B are sent along the network between the source and the destination node of the connection. By ensuring that two data flows out of the three always operate even if a single edge fails, the source data can be instantaneously recovered at the destination node. In contrast with diversity coding, we do not require the three data flows to be routed along three disjoint paths; however, in our scheme, a data flow is allowed to split into two parallel segments and later merge back. Thus, our generalized diversity coding (GDC) scheme can be used in sparse but still two-connected network topologies. Our proof improves an earlier result of network coding, by using purely graph theoretical tool set instead of algebraic argument. In particular, we show that when the source data are divided into two parts, robust intra-session network coding against single edge failures is always possible without any in-network algebraic operation. We present linear-time robust code construction algorithms for this practical special case in minimal coding graphs. We further characterize this question, and show that by increasing the number of edge failures and source data parts, we lose these desired properties.

The problem of finding network codes for general connections is inherently difficult in capacity constrained networks. Resource minimization for general connections with network coding is further complicated. Existing methods for identifying solutions mainly rely on highly restricted classes of network codes, and are almost all centralized. In this paper, we introduce linear network mixing coefficients for code constructions of general connections that generalize random linear network coding for multicast connections. For such code constructions, we pose the problem of cost minimization for the subgraph involved in the coding solution and relate this minimization to a path-based constraint satisfaction problem (CSP) and an edge-based CSP. While CSPs are NP-complete in general, we present a path-based probabilistic distributed algorithm and an edge-based probabilistic distributed algorithm with almost sure convergence in finite time by applying communication free learning. Our approach allows fairly general coding across flows, guarantees no greater cost than routing, and shows a possible distributed implementation. Numerical results illustrate the performance improvement of our approach over existing methods.

This paper proposes a partial packet recovery scheme called packetized rateless algebraic consistency (PRAC). PRAC exploits intra- and inter-packet consistency to identify and recover erroneous packet segments, without recourse to soft physical layer (PHY) or detailed feedback information. PRAC uses a rateless linear code for data encoding and an iterative decoding process for data reconstruction. It allows, but does not rely upon, the use of any PHY forward error correction code, and requires no feedback other than a notification of completion and, in the absence of partial packets, incurs no overhead. In order to quantify PRAC's performance in terms of both throughput and energy efficiency, experiments are conducted using commercial transceivers in two different scenarios. Our implementation results reveal that PRAC offers an average throughput gain of 35% compared with a baseline ARQ scheme discarding partial packets, and 13% compared with an ideal hybrid-ARQ scheme. On high PER links, throughput is improved by 148% and 34%, respectively. In addition, PRAC reduces on average the total energy consumption of the transmitting nodes by 16%, while, on high PER links, savings can be up to 50%.

In non-coherent wideband fading channels, where energy rather than spectrum is the limiting resource, peaky and non-peaky signaling schemes have long been considered species apart, as the first approaches asymptotically the capacity of a wideband AWGN channel with the same average SNR, whereas the second reaches a peak rate at some finite critical bandwidth and then falls to zero as bandwidth grows to infinity. In this paper, it is shown that this distinction is in fact an artifact of the limited attention paid in the past to the product between the bandwidth and the fraction of time it is in use. This fundamental quantity, called bandwidth occupancy, measures average bandwidth usage over time. For all signaling schemes with the same bandwidth occupancy, achievable rates approach to the wideband AWGN capacity within the same gap as the bandwidth occupancy approaches its critical value, and decrease to zero as the occupancy goes to infinity. This unified analysis produces quantitative closed-form expressions for the ideal bandwidth occupancy, recovers the existing capacity results for (non-) peaky signaling schemes, and unveils a tradeoff between the accuracy of approximating capacity with a generalized Taylor polynomial and the accuracy with which the optimal bandwidth occupancy can be bounded.

Distributed storage systems need to guarantee reliable access to stored data. Resilience to node failures can be increased by using erasure encoding. A variety of erasure codes are discussed in literature and implemented in practice. This multiplicity of codes puts a heavy burden on existing systems. In scenarios such as multi-cloud file delivery or migration of data to a new erasure code, the ability to combine data from diverse erasure codes of multiple cloud systems is essential. The methods presented in this paper enable combining symbols of different erasure codes regardless of their underlying generator matrix, finite field size, and source block size. Mathematical approaches are discussed using Reed-Solomon and RLNC codes as example but without loss of generality. The presented approaches enable multi-cloud file delivery across diverse coding algorithms and permits graceful migration of a legacy erasure coding without the need of re-ingestion of existing data.

The capability of mobile devices to use multiple interfaces to support a single session is becoming more prevalent. Prime examples include the desire to implement WiFi offloading and the introduction of 5G. Furthermore, an increasing fraction of Internet traffic is becoming delay sensitive. These two trends drive the need to investigate methods that enable communication over multiple parallel heterogeneous networks, while also ensuring that delay constraints are met. This paper approaches these challenges using a multi-path streaming code that uses forward error correction to reduce the in-order delivery delay of packets in networks with poor link quality and transient connectivity. A simple analysis is developed that provides a good approximation of the in-order delivery delay. Furthermore, numerical results help show that the delay penalty of communicating over multiple paths is insignificant when considering the potential throughput gains obtained through the fusion of multiple networks.

Erasure codes are increasingly being studied in the context of implementing atomic memory objects in large scale asynchronous distributed storage systems. When compared with the traditional replication based schemes, erasure codes have the potential of significantly lowering storage and communication costs while simultaneously guaranteeing the desired resiliency levels. In this work, we propose the Storage-Optimized Data-Atomic (SODA) algorithm for implementing atomic memory objects in the multi-writer multi-reader setting. SODA uses Maximum Distance Separable (MDS) codes, and is specifically designed to optimize the total storage cost for a given fault-tolerance requirement. For tolerating f server crashes in an n-server system, SODA uses an [n, k] MDS code with k = n - f, and incurs a total storage cost of n/n-f. SODA is designed under the assumption of reliable point-to-point communication channels. The communication cost of a write and a read operation are respectively given by O(f2) and n/n-f(δw+1), where δwdenotes the number of writes that are concurrent with the particular read. In comparison with the recent CASGC algorithm [1], which also uses MDS codes, SODA offers lower storage cost while pays more on the communication cost. We also present a modification of SODA, called SODAerr, to handle the case where some of the servers can return erroneous coded elements during a read operation. Specifically, in order to tolerate f server failures and e error-prone coded elements, the SODAerr algorithm uses an [n, k] MDS code such that k = n - 2e - f. SODAerr also guarantees liveness and atomicity, while maintaining an optimized total storage cost of n/n-f-2e.

Hierarchical cooperation schemes in wireless networks rely on local cooperation among neighboring nodes to create virtual multiple-input multiple-output (MIMO) connections between clusters of nodes. It was shown that, by applying the virtual MIMO technique recursively in a hierarchical manner, the sum rate of all source-destination pairs can scale linearly with the number of nodes in the network. In this paper we focus on the impact of local cooperation and establish new capacity scaling bounds for the virtual MIMO transmission taking into account the constraints of local communication both at the transmitters and the receivers. We show that the cost of local communication, which is inevitable to establish the virtual MIMO transmission, grows exponentially with the number of layers in the cooperation hierarchy and plays a vital role in determining the overall performance of the hierarchical virtual MIMO cooperation.

The problem of one-way file synchronization from the client to the data-center, namely, file updates, is studied. The problem is investigated in particular when an old version of a file which can be available at both client and data-center, is edited by the client to a new version. The edits are modeled as random insertions and deletions (InDels). Based on the updated and the previous version of the file, the client transmits a message to the data-center via a noiseless link, such that the data-center can update the file. A dynamic-programming-run-length-coding (DP-RLC) scheme is proposed for the message encoding in this paper. The lower order terms of the achievable rate are computed explicitly. It is worth noting that these terms match the information-theoretic lower bound derived in our previous work [1]. Therefore, when the insertion and deletion probabilities are small, the achievable rate is nearly optimal.

Erasure codes offer an efficient way to decrease storage and communication costs while implementing atomic memory service in asynchronous distributed storage systems. In this paper, we provide erasure-code-based algorithms having the additional ability to perform background repair of crashed nodes. A repair operation of a node in the crashed state is triggered externally, and is carried out by the concerned node via message exchanges with other active nodes in the system. Upon completion of repair, the node re-enters active state, and resumes participation in ongoing and future read, write, and repair operations. To guarantee liveness and atomicity simultaneously, existing works assume either the presence of nodes with stable storage, or presence of nodes that never crash during the execution. We demand neither of these; instead we consider a natural, yet practical network stability condition N1 that only restricts the number of nodes in the crashed/repair state during broadcast of any message. We present an erasure-code based algorithm RADON_{C} that is always live, and guarantees atomicity as long as condition N1 holds. In situations when the number of concurrent writes is limited, RADON_{C} has significantly improved storage and communication cost over a replication-based algorithm RADON_{R}, which also works under N1. We further show how a slightly stronger network stability condition N2 can be used to construct algorithms that never violate atomicity. The guarantee of atomicity comes at the expense of having an additional phase during the read and write operations.

For single-input multiple-output (SIMO) systems, Maximum Ratio Combining (MRC), employed at the receiver, achieves the best performance compared to other combining schemes in the literature, such as Selection Combining (SC) and Equal Gain Combining (EGC). However, for cooperative relay-based systems, MRC has limited performance due to the lack of relay decision information awareness at the destination combiner. To overcome this limitation, this paper proposes a new optimum combining scheme, which is being demonstrated for Hybrid-Decode-Amplify-Forward (HDAF) cooperative system. This scheme utilizes relay decision information in the form of the number of errors per received packet over the source-relay link. The derivation of the optimum combining scheme is based on a mathematical model that utilizes conditional error probability. The improved performance of the proposed optimum combining scheme is demonstrated through analytical results and Monte Carlo simulations.

The wide availability of power distribution cables provides an interesting no-new-wires communication channel. However, its electrical characteristics make it a harsh environment for the data transmission purpose and prevent the deployment of services with high reliability requirements. This paper proposes and implements an OSI-Layer2 network coding-based cooperative scheme with the aim of improving communication reliability in indoor narrowband powerline channels. The proposed scheme uses random linear network coding with a sliding window and relaying. We use network coding to replace the retransmissions triggered by legacy subsequent repeat request (ARQ) schemes. We evaluate the performance of our approach in terms of throughput and delay. Regarding the throughput achieved in harsh environments, we show that our scheme often more than doubles the throughput of existing legacy ARQ schemes. At the same time, and even under the large variation of traffic characteristics, it is shown that the delay is likely to be upper bounded by a few seconds, a bound that cannot be guaranteed in other existing transmission techniques.

The framework of network equivalence theory developed by Koetter et al. introduces a notion of channel emulation to construct noiseless networks as upper (respectively, lower) bounding models, which can be used to calculate the outer (respectively, inner) bounds for the capacity region of the original noisy network. Based on the network equivalence framework, this paper presents scalable upper and lower bounding models for wireless networks with potentially many nodes. A channel decoupling method is proposed to decompose wireless networks into decoupled multiple-access channels and broadcast channels. The upper bounding model, consisting of only point-to-point bit pipes, is constructed by first extending the one-shot upper bounding models developed by Calmon et al. and then integrating them with network equivalence tools. The lower bounding model, consisting of both point-to-point and point-to-points bit pipes, is constructed based on a two-step update of the lower bounding models to incorporate the broadcast nature of wireless transmission. The main advantages of the proposed methods are their simplicity and the fact that they can be extended easily to large networks with a complexity that grows linearly with the number of nodes. It is demonstrated that the resulting upper and lower bounds can approach the capacity in some setups.

In this paper, we study the wireline two-unicast-Z communication network over directed acyclic graphs. The two-unicast-$Z$ network is a two-unicast network where the destination intending to decode the second message has a priori side information of the first message. We make three contributions in this paper. First, we describe a new linear network coding algorithm for two-unicast-Z networks over the directed acyclic graphs. Our approach includes the idea of interference alignment as one of its key ingredients. For the graphs of a bounded degree, our algorithm has linear complexity in terms of the number of vertices, and the polynomial complexity in terms of the number of edges. Second, we prove that our algorithm achieves the rate pair (1, 1) whenever it is feasible in the network. Our proof serves as an alternative, albeit restricted to two-unicast-Z networks over the directed acyclic graphs, to an earlier result of Wang et al., which studied the necessary and sufficient conditions for the feasibility of the rate pair (1, 1) in two-unicast networks. Third, we provide a new proof of the classical max-flow min-cut theorem for the directed acyclic graphs.

Coding techniques for storage systems are gaining traction in data center (DC) applications, owing to their data survivability performance, and more recently, to their ability to mitigate traffic congestion. This paper considers stochastic allocation schedules in networks that admit bulk file requests, across three drive blocking models. We consider a block-based code and a stochastic scheduling algorithm which is beneficial in the case of continuous chunk read patterns. In particular, we demonstrate that in systems with continuous chunk reading patterns, when drive blocking is either independent or from traffic congestion, block coded storage can reduce average download time by 10 -- 66%, given modern system parameters. However, a distinction should be made between systems with continuous and those with interrupted chunk read patterns. For interrupted chunk read systems, given our allocation algorithm that performs well for continuous reads, block coded storage performance can be worse than replication, numerical illustrations show relative losses over 66%. These illustrations demonstrate that to harness the full benefits of coded storage and to avoid pitfalls, careful attention must be paid to continuous vs. Interrupted chunk reading patterns, codes other than block codes should be considered, as could joint code-scheduling design.

The problem of finding network codes for general connections is inherently difficult. Resource minimization for general connections with network coding is further complicated. Existing methods for identifying solutions mainly rely on very restricted classes of network codes, and are almost all centralized. In this paper, we introduce linear network mixing coefficients for code constructions of general connections that generalize random linear network coding (RLNC) for multicast connections. For such code constructions, we pose the problem of cost minimization for the subgraph involved in the coding solution and relate this minimization to a Constraint Satisfaction Problem (CSP) which we show can be simplified to have a moderate number of constraints. While CSPs are NP-complete in general, we present a probabilistic distributed algorithm with almost sure convergence in finite time by applying Communication Free Learning (CFL). Our approach allows fairly general coding across flows, guarantees no greater cost than routing, and shows a possible distributed implementation. Numerical results illustrate the performance improvement of our approach over existing methods.

This paper introduces AdaptCast, an integrated source to transmission scheme for wireless sensor networks (WSNs) that efficiently represents collected data and increases their robustness against channel errors across a wide range of signal to noise (SNR) values in a rateless fashion. AdaptCast leverages sparsity inherent in the majority of physical signals in order to parsimoniously represent them without relying on a specific signal model. The proposed scheme does not suffer from the sudden degradation in the tradeoff between distortion and SNR of rated channel coding schemes due to its direct, relative bit importance preserving modulation mapping. In addition, it does not require continuous feedback or channel state information (CSI) as a result of its rateless operation. Apart from point-to-point transmission, AdaptCast enables efficient multicasting to a set of nodes, serving each of them at a rate commensurate to its individual channel quality. We demonstrate AdaptCast's application-independent operation by using several typical signals captured in WSNs. Based on our analysis and simulation results, considering the tradeoff between distortion and channel quality, AdaptCast performs close in a point-to-point scenario to an idealized layered transmission scheme with instantaneous CSI and offers significant benefits in multiuser settings.

As optical networks evolve towards more dynamicity and an ever more efficient and elastic spectrum utilization, a more integrated, fault tolerant and system efficient design is becoming critical. To increase efficiency of spectral resource in bit rate per Hz (bit/s/Hz), high-level modulation formats are used, challenged by the accompanying optical impairments and the resulting limitation of optical reach. Previous work has addressed the issue of optical reach and transmission fault tolerance in the physical layer by deploying various FEC schemes and by a careful design of optical transceivers and links. This paper uses a different approach, applicable to link and networking layers. We propose a novel theoretical framework, whereby a randomized linear network coding (LNC) is applied to the main optical path, and in parallel, an auxiliary optical path is used at much lower transmission speeds, i.e., in addition to the main path. With the reception of the auxiliary path, as we analytically show, the system is highly tolerant to bit errors and packet loss caused by optical impairments in the main path, whereby alleviating the constraints on optical transmission quality and indirectly achieving better optical reach and spectral efficiency. The results are shown for a case study of high-speed Ethernet end-system transmitted over optical OFDM networks, which due to the inherent system-level parallelism in both networks, present one of the most interesting candidate technologies for the proposed method to yield best performance.

For general connections, the problem of finding network codes and optimizing resources for those codes is intrinsically difficult and little is known about its complexity. Most of the existing solutions rely on very restricted classes of network codes in terms of the number of flows allowed to be coded together, and are not entirely distributed. In this paper, we consider a new method for constructing linear network codes for general connections of continuous flows to minimize the total cost of edge use based on mixing. We first formulate the minimum-cost network coding design problem. To solve the optimization problem, we propose two equivalent alternative formulations with discrete mixing and continuous mixing, respectively, and develop distributed algorithms to solve them. Our approach allows fairly general coding across flows and guarantees no greater cost than any solution without inter-flow network coding.

Data transmission over multiple-hop networks is impaired by random deleterious events, and characterizing the probability of error for the end-to-end transmission is challenging as the size of networks grows. Adams et al. showed that, when re-encoding at intermediate nodes is enabled, coded transmission over tandem/parallel links can be reduced to a single equivalent link with a specified probability function. Although iterative application of the tandem/parallel reduction techniques in alternation can simplify the task, they are generally not sufficient to reduce an arbitrary network to a single link. In this paper, we propose upper- and lower- bounding processes to bound the end-to-end probability distribution of a network by combining the parallel/tandem link reduction with the structure of flows over the network. We evaluate the performance of the proposed bounding methods at the 99% success rate of end-to-end data transmission over randomly generated acyclic networks. The numerical results demonstrate that our bounding approaches enable us to characterize a network by a single probability function to a very good precision.

With the boom of big data, traditional source coding techniques face the common obstacle to decode only a small portion of information efficiently. In this paper, we aim to resolve this difficulty by introducing a specific type of source coding scheme called locally decodable source coding (LDSC). Rigorously, LDSC is capable of recovering an arbitrary bit of the unencoded message from its encoded version, by only feeding a small number of the encoded message to the decoder, and we call the decoder t-local if only t encoded symbols are required.We consider both almost lossless (block error) and lossy (bit error) cases for LDSC. First, we show that using linear encoder and a decoder with bounded locality, the reliable compress rate can not be less than one. More importantly, we show that even with a general encoder and 2-local decoders (t = 2), the rate of LDSC is still one. On the contrary, the achievability bounds for almost lossless and lossy compressions with excess distortion suggest that optimal compression rate is achievable when O(log n) encoded symbols is queried by the decoder with block-length n. We also show that, rate distortion is achievable when the number of queries is scaled over n with a bound on the rate in finite-length regime. Although the achievability bounds are simply based on the concatenation of code blocks, they outperform the existing bounds in succinct data structures literature.

Reducing the in-order delivery, or playback, delay of reliable transport layer protocols over error prone networks can significantly improve application layer performance. This is especially true for applications that have time sensitive constraints such as streaming services. We explore the benefits of a coded generalization of selective repeat ARQ for minimizing the in-order delivery delay. An analysis of the delay's first two moments is provided so that we can determine when and how much redundancy should be added to meet a user's requirements. Numerical results help show the gains over selective repeat ARQ, as well as the trade-offs between meeting the user's delay constraints and the costs inflicted on the achievable rate. Finally, the analysis is compared with experimental results to help illustrate how our work can be used to help inform system decisions.

Guesswork forms the mathematical framework for quantifying computational security subject to brute-force determination by query. In this paper, we consider guesswork subject to a per-symbol Shannon entropy budget. We introduce inscrutability rate as the asymptotic rate of increase in the exponential number of guesses required of an adversary to determine one or more secret strings. We prove that the inscrutability rate of any string-source supported on a finite alphabet χ, if it exists, lies between the per-symbol Shannon entropy constraint and log |χ|. We further prove that the inscrutability rate of any finite-order Markov string-source with hidden statistics remains the same as the unhidden case, i.e., the asymptotic value of hiding the statistics per each symbol is vanishing. On the other hand, we show that there exists a string-source that achieves the upper limit on the inscrutability rate, i.e., log |χ|, under the same Shannon entropy budget.

We investigate the problem of intentionally disclosing information about a set of measurement points X (useful information), while guaranteeing that little or no information is revealed about a private variable S (private information). Given that S and X are drawn from a finite set with joint distribution pS,X, we prove that a non-trivial amount of useful information can be disclosed while not disclosing any private information if and only if the smallest principal inertia component of the joint distribution of S and X is 0. This fundamental result characterizes when useful information can be privately disclosed for any privacy metric based on statistical dependence. We derive sharp bounds for the tradeoff between disclosure of useful and private information, and provide explicit constructions of privacy-assuring mappings that achieve these bounds.

Peaky and non-peaky signaling schemes have long been considered species apart in non-coherent wideband fading channels, as the first approaches asymptotically the linear-in-power capacity of a wideband AWGN channel with the same SNR, whereas the second reaches a nearly power-limited peak rate at some finite critical bandwidth and then falls to zero as bandwidth grows to infinity. In this paper it is shown that this distinction is in fact an artifact of the limited attention paid in the past to the product between the bandwidth and the fraction of time it is in use. This fundamental quantity, that is termed bandwidth occupancy, measures average bandwidth usage over time. The two types of signaling in the literature are harmonized to show that, for any type of signals, there is a fundamental limit-a critical bandwidth occupancy. All signaling schemes with the same bandwidth occupancy approach the capacity of wideband AWGN channels with the same asymptotic behavior as the bandwidth occupancy grows to its critical value. For a bandwidth occupancy above the critical, rate decreases to zero as the bandwidth occupancy goes to infinity.

We consider the problem of diluting common randomness from correlated observations by separated agents. This problem creates a new framework to study statistical privacy, in which a legitimate party, Alice, has access to a random variable X, whereas an attacker, Bob, has access to a random variable Y dependent on X drawn from a joint distribution pX,Y. Alice's goal is to produce a non-trivial function of her available information that is uncorrelated with (has small correlation with) any function that Bob can produce based on his available information. This problem naturally admits a minimax formulation where Alice plays first and Bob follows her. We define dilution coefficient as the smallest value of correlation achieved by the best strategy available to Alice, and characterize it in terms of the minimum principal inertia components of the joint probability distribution pX,Y. We then explicitly find the optimal function that Alice must choose to achieve this limit. We also establish a connection between differential privacy and dilution coefficient and show that if Y is ε-differentially private from X, then dilution coefficient can be upper bounded in terms of ε. Finally, we extend to the setting where Alice and Bob have access to i.i.d. copies of (Xi, Yi), i = 1, ..., n and show that the dilution coefficient vanishes exponentially with n. In other words, Alice can achieve better privacy as the number of her observations grows.

We introduce a property that we call Successive Description property for Slepian Wolf coding. We show that Monotone-Chain Polar Codes can be used to construct low-complexity codes that satisfy this property. We discuss applications of this property to network coding problems.

A client/encoder edits a file, as modeled by an insertion-deletion (InDel) process. An old copy of the file is stored remotely at a data-centre/decoder, and is also available to the client. We consider the problem of throughput- and computationally-efficient communication from the client to the data-centre, to enable the server to update its copy to the newly edited file. We study two models for the source files/edit patterns: the random pre-edit sequence left-to-right random InDel (RPES-LtRRID) process, and the arbitrary pre-edit sequence arbitrary InDel (APES-AID) process. In both models, we consider the regime in which the number of insertions/deletions is a small (but constant) fraction of the original file. For both models we prove information-theoretic lower bounds on the best possible compression rates that enable file updates. Conversely, our compression algorithms use dynamic programming (DP) and entropy coding, and achieve rates that are approximately optimal.

This paper proposes approximation approaches to the problem of finding optimal quantization schemes that maximize the mutual information of Gaussian channels, by deriving asymptotic solutions that are simple and analytical. Two major results are presented: i) we derived an approximation scheme with its quantization thresholds linearly depending on the standard deviation of noise, which has negligible loss on the entire range of the signal-to-noise ratio (SNR) for 2-PAM modulated channels; ii) based on the high-rate limit, we derived a simple estimator of the relative capacity loss, which is inversely proportional to the square of the number of quantization intervals. These solutions can potentially reduce the complexity of the design and implementation process of quantization schemes.

In this paper, we design and analyze information spreading algorithms for dynamic networks with correlated data. In these networks, either the data to be distributed, the data already available at the nodes, or both are correlated. Moreover, nodes' availability and connectivity is dynamic - a scenario typical for wireless networks. Our contribution is twofold. First, although coding schemes for correlated data have been studied extensively, the focus has been on characterizing the rate region in static networks. In an information spreading scheme, however, nodes may communicate by continuously exchanging packets according to some underlying communication model. The main figure of merit is the stopping time - the time required until nodes can successfully decode. While information spreading schemes, such as gossip, are practical, distributed, and scalable, they have only been studied for uncorrelated data. We close this gap by providing techniques to analyze network-coded information spreading in dynamic networks with correlated data. Second, we give a clean framework for oblivious dynamic network models that in particular applies to a multitude of wireless network and communication scenarios. We specify a general setting for the data model and give tight bounds on the stopping times of network-coded protocols in this wide range of settings. En route, we analyze the capacities seen by nodes under a network-coded information spreading protocol, a previously unexplored question. We conclude with extensive simulations, clearly validating the key trends and phenomena predicted in the analysis.

The guesswork problem was originally motivated by a desire to quantify computational security for single user systems. Leveraging recent results from its analysis, we extend the remit and utility of the framework to the quantification of the computational security of multi-user systems. In particular, assume that V users independently select strings stochastically from a finite, but potentially large, list. An inquisitor who does not know which strings have been selected wishes to identify U of them. The inquisitor knows the selection probabilities of each user and is equipped with a method that enables the testing of each (user, string) pair, one at a time, for whether that string had been selected by that user. Here, we establish that, unless U=V, there is no general strategy that minimizes the distribution of the number of guesses, but in the asymptote as the strings become long we prove the following: by construction, there is an asymptotically optimal class of strategies; the number of guesses required in an asymptotically optimal strategy satisfies a large deviation principle with a rate function, which is not necessarily convex, that can be determined from the rate functions of optimally guessing individual users' strings; if all users' selection statistics are identical, the exponential growth rate of the average guesswork as the string-length increases is determined by the specific Rényi entropy of the string-source with parameter (V-U+1)/(V-U+2), generalizing the known V=U=1 case; and that the Shannon entropy of the source is a lower bound on the average guesswork growth rate for all U and V, thus providing a bound on computational security for multi-user systems. Examples are presented to illustrate these results and their ramifications for systems design.

We investigate the performance of delay constrained data transmission over wireless networks without end-to-end feedback. Forward error-correction coding (FEC) is performed at the bit level to combat channel distortions and random linear network coding (RLNC) is performed at the packet level to recover from packet erasures. We focus on the scenario where RLNC re-encoding is performed at intermediate nodes and we assume that any packet that contains bit errors after FEC decoding can be detected and erased. To facilitate explicit characterization of data transmission over network-coded wireless systems, we propose a generic two-layer abstraction of a network that models both bit/symbol-level operations at the lower layer (termed PHY-layer) over several heterogeneous links and packet-level operations at the upper layer (termed NET-layer). Based on this model, we propose a network reduction method to characterize the throughput-reliability function of the end-to-end transmission. Our approach not only reveals an explicit tradeoff between data delivery rate and reliability, but also provides an intuitive visualization of the bottlenecks within the underlying network. We illustrate our approach via a point-to-point link and a relay network and highlight the advantages of this method over capacity-based approaches.

This paper proposes a partial packet recovery scheme, called Packetized Rateless Algebraic Consistency (PRAC). PRAC exploits intra and inter-packet consistency to identify and recover erroneous packet segments, without recourse to cross-layer or detailed feedback information. In the absence of cross-layer coordination or detailed feedback, the prevailing methods proposed in the literature have discarded packets with errors. PRAC uses a rateless linear packet code for data encoding and an iterative decoding process consisting of a search algorithm and an algebraic consistency rule (ACR) check. It allows, but not relies upon, the use of any PHY FEC code, requires no feedback other than a notification of completion and, in the absence of partial packets, incurs no overhead. Our implementation and experimental results in a 7-node indoor testbed using wireless boards equipped with CC2500 radio transceivers reveal that PRAC offers an average throughput gain of 35% compared to a baseline ARQ scheme discarding partial packets and 13% compared to an ideal genie-aided HARQ (iHARQ) scheme. Specifically for links with high PERs, PRAC significantly enhances their robustness and its maximum throughput gain is 148% and 34% compared against the baseline and iHARQ schemes, respectively.

The application of congestion control can have a significant detriment to the quality of service experienced at higher layers, especially under high packet loss rates. The effects of throughput loss due to the congestion control misinterpreting packet losses in poor channels is further compounded for applications such as HTTP and video leading to a significant decrease in the user's quality of service. Therefore, we consider the application of congestion control to transport layer packet streams that use error-correction coding in order to recover from packet losses. We introduce a modified AIMD approach, develop an approximate mathematic model suited to performance analysis, and present extensive experimental measurements in both the lab and the “wild” to evaluate performance. Our measurements highlight the potential for remarkable performance gains, in terms of throughput and upper layer quality of service, when using coded transports.

In this paper we close the gap between end-to-end diversity coding and intra-session network coding for unicast connections resilient against single link failures. In particular, we show that coding operations are sufficient to perform at the source and receiver if the user data can be split into at most two parts over the filed GF(2). Our proof is purely combinatorial and based on standard graph and network flow techniques. It is a linear time construction that defines the route of subflows A, B and A ⊕ B between the source and destination nodes. The proposed resilient flow decomposition method generalizes the 1+1 protection and the end-to-end diversity coding approaches while keeping both of their benefits. It provides a simple yet resource efficient protection method feasible in 2-connected backbone topologies. Since the core switches do not need to be modified, this result can bring benefits to current transport networks.

The framework of network equivalence theory developed by Koetter et al. introduces a notion of channel emulation to construct noiseless networks as upper/lower bounding models for the original noisy network. This paper presents scalable upper bounding models for wireless networks, by firstly extending the “one-shot” bounding models developed by Calmon et al. and then integrating them with network equivalence tools. A channel decoupling method is proposed to decompose wireless networks into decoupled multiple-access channels (MACs) and broadcast channels (BCs). The main advantages of the proposed method is its simplicity and the fact that it can be extended easily to large networks with a complexity that grows linearly with the number of nodes. It is demonstrated that the resulting upper bounds can approach the capacity in some setups.

The principal inertia components of the joint distribution of two random variables X and Y are inherently connected to how an observation of Y is statistically related to a hidden variable X. In this paper, we explore this connection within an information theoretic framework. We show that, under certain symmetry conditions, the principal inertia components play an important role in estimating one-bit functions of X, namely f(X), given an observation of Y. In particular, the principal inertia components bear an interpretation as filter coefficients in the linear transformation of pf(X)|Xinto pf(X)|Y. This interpretation naturally leads to the conjecture that the mutual information between f(X) and Y is maximized when all the principal inertia components have equal value. We also study the role of the principal inertia components in the Markov chain B → X → Y → B̂, where B and B̂ are binary random variables. We illustrate our results for the setting where X and Y are binary strings and Y is the result of sending X through an additive noise binary channel.

We focus on the privacy-utility trade-off encountered by users who wish to disclose some information to an analyst, that is correlated with their private data, in the hope of receiving some utility. We rely on a general privacy statistical inference framework, under which data is transformed before it is disclosed, according to a probabilistic privacy mapping. We show that when the log-loss is introduced in this framework in both the privacy metric and the distortion metric, the privacy leakage and the utility constraint can be reduced to the mutual information between private data and disclosed data, and between non-private data and disclosed data respectively. We justify the relevance and generality of the privacy metric under the log-loss by proving that the inference threat under any bounded cost function can be upperbounded by an explicit function of the mutual information between private data and disclosed data. We then show that the privacy-utility tradeoff under the log-loss can be cast as the non-convex Privacy Funnel optimization, and we leverage its connection to the Information Bottleneck, to provide a greedy algorithm that is locally optimal. We evaluate its performance on the US census dataset. Finally, we characterize the optimal privacy mapping for the Gaussian Privacy Funnel.

A locally decodable source code (LDSC) allows the recovery of arbitrary parts of an unencoded message from its encoded version, using only a part of the encoded message as input, a challenge that arises when searching within compressed data sets. Simple source codes such as Huffman codes or Lempel-Ziv compression are not well suited to this task: A decoder starting at an arbitrary point within the compressed sequence generally cannot determine its position with respect to the boundaries between encoded symbols, or requires information found before the starting point in order to be able to decode. In this paper, we propose the use of subsets of self-synchronising variable-length T-codes as source codes and show that local decoding is feasible and practical using subsets of T-codes with bounded synchronisation delay (BSD).

We derive a new linear network coding algorithm for two-unicast-Z networks over directed acyclic graphs, that is, for two-unicast networks where one destination has apriori information of the interfering source message. Our algorithm discovers linear network codes for two-unicast-Z networks by combining ideas of random linear network coding and interference neutralization. We show that our algorithm outputs an optimal network code for networks where there is only one edge emanating from each of the two sources. The complexity of our algorithm is polynomial in the number of edges of the graph.

This paper considers the communication and storage costs of emulating atomic (linearizable) multi-writer multi-reader shared memory in distributed message-passing systems. The paper contains two main contributions: 1) We present an atomic shared-memory emulation algorithm that we call Coded Atomic Storage (CAS). This algorithm uses erasure coding methods. In a storage system with 'N' servers that is resilient to 'f' server failures, we show that the communication cost of CAS is N/(N-2f). The storage cost of CAS is unbounded. 2) We present a variant of CAS known as CAS with Garbage Collection (CASGC). The CASGC algorithm is parametrized by an integer 'd' and has a bounded storage cost. We show that in every execution where the number of write operations that are concurrent with a read operation is no bigger than d, the CASGC algorithm with parameter d satisfies atomicity and liveness. We explicitly characterize the storage cost of CASGC, and show that it has the same communication cost as CAS.

Random Linear Network Coding (RLNC) provides a theoretically efficient method for coding. The drawbacks associated with it are the complexity of the decoding and the overhead resulting from the coding vector. This adds to the overall energy consumption and is problematic for computational limited and battery driven platforms. In this work we present an approach to RLNC where the code is sparse and non-uniform. The sparsity allow for fast encoding and decoding, and the non- uniform protection of symbols enables recoding where the produced symbols are indistinguishable from those encoded at the source. The results show that the approach presented here provides a better trade- off between coding throughput and code overhead. In particular it can provide a coding overhead identical to RLNC but at significantly reduced computational complexity. It also allow for easy adjustment of this trade-off, which make it suitable for a broad range of platforms and applications. Finally it is easy to perform recoding and coding vectors can be efficiently represented.

Traditionally, the idea of overlapping generations in network coding research has focused on reducing the complexity of decoding large data files while maintaining the delay performance expected of a system that combines all data packets. However, the effort for encoding and decoding individual generations can still be quite high compared to other sparse coding approaches. This paper focuses on an inherently different approach that combines (i) sparsely coded generations configured on-the- fly based on (ii) controllable and infrequent feedback that allows the system to remove some original packets from the pool of packets to be mixed in the linear combinations. The latter is key to maintain a high impact of the coded packets received during the entire process while maintaining very sparsely coded generations. Interestingly, our proposed approach naturally bridges the idea of overlapping generations with that of tunable sparse network coding, thus providing the system with a seamless and adaptive strategy to balance complexity and delay performance. We analyze two families of strategies focused on these ideas. We also compare them to other standard approaches both in terms of delay performance and complexity as well as providing measurements in commercial devices to support our conclusions. Our results show that a judicious choice of the overlapping of the generations provides close-to-optimal delay performance, while reducing the decoding complexity by up to an order of magnitude with respect to other schemes.

We present a natural and low-complexity technique for achieving the capacity of the Gaussian relay network in the high SNR regime. Specifically, we propose the use of end-to-end structured lattice codes with the amplify-and-forward strategy, where the source uses a nested lattice code to encode the messages and the destination decodes the messages by lattice decoding. All intermediate relays simply amplify and forward the received signals over the network to the destination. We show that the end-to-end lattice-coded amplify-and-forward scheme approaches the capacity of the layered Gaussian relay network in the high SNR regime. Next, we extend our scheme to non-layered Gaussian relay networks under the amplify-and-forward scheme, which can be viewed as a Gaussian intersymbol interference (ISI) channel. Compared with other schemes, our approach is significantly simpler and requires only the end-to-end design of the lattice precoding and decoding. It requires little knowledge of the network topology or the individual channel gains.

The capacity of multiuser networks has been a long-standing problem in information theory. Recently, Avestimehr et al. have proposed a deterministic network model to approximate multiuser wireless networks. This model, known as the ADT network model, takes into account the broadcast nature as well as the multiuser interference inherent in the wireless medium. For the types of connections we consider, we show that the results of Avestimehr et al. under the ADT model can be reinterpreted within the algebraic network coding framework introduced by Koetter and Médard. Using this framework, we propose an efficient distributed linear code construction for the deterministic wireless multicast relay network model. Unlike several previous coding schemes, we do not attempt to find flows in the network. Instead, for a layered network, we maintain an invariant where it is required that at each stage of the code construction, certain sets of codewords are linearly independent.

In this paper, we consider different aspects of the problem of compressing for function computation across a network, which we call network functional compression. In network functional compression, computation of a function (or, some functions) of sources located at certain nodes in a network is desired at receiver(s). The rate region of this problem has been considered in the literature under certain restrictive assumptions, particularly in terms of the network topology, the functions, and the characteristics of the sources. In this paper, we present results that significantly relax these assumptions. For a one-stage tree network, we characterize a rate region by introducing a necessary and sufficient condition for any achievable coloring-based coding scheme called coloring connectivity condition. We also propose a modularized coding scheme based on graph colorings to perform arbitrarily closely to rate lower bounds. For a general tree network, we provide a rate lower bound based on graph entropies and show that, this bound is tight in the case of having independent sources. In particular, we show that, in a general tree network case with independent sources, to achieve the rate lower bound, intermediate nodes should perform computations. However, for a family of functions and random variables, which we call chain-rule proper sets, it is sufficient to have no computations at intermediate nodes to perform arbitrarily closely to the rate lower bound. In addition, we consider practical issues of coloring-based coding schemes and propose an efficient algorithm to compute a minimum entropy coloring of a characteristic graph under some conditions on source distributions and/or the desired function. Finally, extensions of these results for cases of having feedback and lossy function computations are discussed.

A technique for bounding the capacities of networks of independent channels is introduced. Parts I and II treat point-to-point and multiterminal channels, respectively. Bounds are derived using a new tool called a bounding model. Channel 1 is an upper (lower) bounding model for channel 2 if replacing channel 2 by channel 1 in any network yields a new network whose capacity region is a superset (subset) of the capacity region of the original network. This paper derives bounding models from noiseless links, with lower bounding models corresponding to points in the channel's capacity region and upper bounding models corresponding to points in a new channel characterization called an emulation region. Replacing all channels in a network by their noiseless upper (lower) bounding models yields a network of lossless links whose capacity region is a superset (subset) of the capacity region for the original network. This converts a general (often stochastic) network into a network coding instance, enabling the application of tools and results derived in that domain. A channel's upper and lower bounding models differ when the channel can carry more information in some networks than in others. Bounding the difference between upper and lower bounding models bounds both the accuracy of the technique and the price of separating source-network coding from channel coding.

The problem of establishing minimum-cost multicast connections in coded networks can be viewed as an optimization problem, and decentralized algorithms were proposed by Lun to compute the optimal subgraph using the dual subgradient method. However, the convergence rate problem for these algorithms remains open. There are limited results in the literature, which bound the amount of infeasibility of the primal solution recovered after each iterations or the convergence rate. However, due to the special structure of the network coding problem, we have an algorithm that generates a feasible solution after each iterations. In addition, the convergence rate of the primal problem is O(1/n) to a neighborhood of the optimal solution. We also propose heuristics to further improve our algorithm and demonstrate through simulations that the distributed algorithm converges to the optimal subgraph quickly and is robust against network topology changes.

In this paper, we provide theoretical and simulation-based study of the delivery delay performance of a number of existing throughput-optimal coding schemes and use the results to design a new dynamic rate adaptation scheme that achieves improved overall throughput-delay performance. Under a baseline rate control scheme, the receivers' delay performance is examined. Based on their Markov states, the knowledge difference between the sender and receiver, three distinct methods for packet delivery are identified: zero state, leader state, and coefficient-based delivery. We provide analyses of each of these and show that, in many cases, zero state delivery alone presents a tractable approximation of the expected packet delivery behavior. Interestingly, while coefficient-based delivery has so far been treated as a secondary effect in the literature, we find that the choice of coefficients is extremely important in determining the delay, and a well-chosen encoding scheme can, in fact, contribute a significant improvement to the delivery delay. Based on our delivery delay model, we develop a dynamic rate adaptation scheme that uses performance prediction models to determine the sender transmission rate. Surprisingly, taking this approach leads us to the simple conclusion that the sender should regulate its addition rate based on the total number of undelivered packets stored at the receivers. We show that despite its simplicity, our proposed dynamic rate adaptation scheme results in noticeably improved throughput-delay performance over existing schemes in the literature.

Parallel transmission, as defined in high-speed Ethernet standards, enables to use less expensive optoelectronics and offers backwards compatibility with legacy Optical Transport Network (OTN) infrastructure. However, optimal parallel transmission does not scale to large networks, as it requires computationally expensive optimal multipath routing algorithms to minimize differential delay, and thus the required buffer size to ensure frame synchronization. In this paper, we propose a novel parallel transmission framework for high-speed Ethernet, which we refer to as network coded parallel transmission, capable of effective buffer management and frame synchronization without the need for complex multipath algorithms. We show that using network coding can reduce the delay caused by packet reordering at the receiver, thus requiring a smaller overall buffer size, while improving the network throughput. We design the framework in full compliance with high-speed Ethernet standards specified in IEEE802.3ba and present detailed schemes including encoding, data structure of coded parallel transmission, buffer management and decoding at the receiver side. The proposed network coded parallel transmission framework is simple to implement and presents a potential major breakthrough in the system design of future high-speed Ethernet.

In this paper, we evaluate the performance of random linear network coding (RLNC) in low data rate indoor sensor applications operating in the ISM frequency band. We also investigate the results of its synergy with forward error correction (FEC) codes at the PHY-layer in a joint channel-network coding (JCNC) scheme. RLNC is an emerging coding technique which can be used as a packet-level erasure code, usually implemented at the network layer, which increases data reliability against channel fading and severe interference, while FEC codes are mainly used for correction of random bit errors within a received packet. The hostile wireless environment that low power sensors usually operate in, with significant interference from nearby networks, motivates us to consider a joint coding scheme and examine the applicability of RLNC as an erasure code in such a coding structure. Our analysis and experiments are performed using a custom low power sensor node, which integrates on-chip a low-power 2.4 GHz transmitter and an accelerator implementing a multi-rate convolutional code and RLNC, in a typical office environment. According to measurement results, RLNC of code rate 4/8 can provide an effective SNR improvement of about 3.4 dB, outperforming a PHY-layer FEC code of the same code rate, at a PER of 10-2. In addition, RLNC performs very well when used in conjunction with a PHY-layer FEC code as a JCNC scheme, offering an overall coding gain of 5.6 dB.

A characterization of systematic network coding over multi-hop wireless networks is key towards understanding the trade-off between complexity and delay performance of networks that preserve the systematic structure. This paper studies the case of a relay channel, where the source's objective is to deliver a given number of data packets to a receiver with the aid of a relay. The source broadcasts to both the receiver and the relay using one frequency, while the relay uses another frequency for transmissions to the receiver, allowing for a full-duplex operation of the relay. We analyze the decoding complexity and delay performance of two types of relays: one that preserves the systematic structure of the code from the source; another that does not. A systematic relay forwards uncoded packets upon reception, but transmits coded packets to the receiver after receiving the first coded packet from the source. On the other hand, a non-systematic relay always transmits linear combinations of previously received packets. We compare the performance of these two alternatives by analytically characterizing the expected transmission completion time as well as the number of uncoded packets forwarded by the relay. Our numerical results show that, for a poor channel between the source and the receiver, preserving the systematic structure at the relay (i) allows a significant increase in the number of uncoded packets received by the receiver, thus reducing the decoding complexity, and (ii) preserves close to optimal delay performance.

Network coding has the potential to enhance energy efficiency of multicast sessions by providing optimal communication subgraphs for the transmission of the data. However, the coding requirement at intermediate nodes may introduce additional complexity and energy consumption in order to code the data packets. Previous work has shown that in lossless wireline networks, the performance of tree-packing mechanisms is comparable to network coding, albeit with added complexity at the time of computing the trees. This means that most nodes in the network need not code. Thus, mechanisms that identify intermediate nodes that do require coding is instrumental for the efficient operation of coded networks and can have a significant impact in overall energy consumption. We present a distributed, low complexity algorithm that allows every node to identify if it should code and, if so, through what output link should the coded packets be sent. Our algorithm uses as input the optimal subgraph determined by Lun et al's optimization formulation [13]. Numerical results are provided using common Internet Service Provider (ISP) network topologies and also random network deployments. Our results show that the number of coding nodes in the expectation is very low (typically below 1) and that the number of sessions that require coding is limited, e.g., less than 15% for sessions of 4 receivers for the ISP networks and below 0.1% for networks with random node deployments in a square of 1 × 1 km2with of up to 30 nodes and up to 20 receivers.

In this paper we consider the additive white Gaussian noise channel with an average input power constraint in the power-limited regime. A well-known result in information theory states that the capacity of this channel can be achieved by random Gaussian coding with analog quadrature amplitude modulation (QAM). In practical applications, however, discrete binary channel codes with digital modulation are most often employed. We analyze the matched filter decoding error probability in random binary and Gaussian coding setups in the wide bandwidth regime, and show that the performance in the two cases is surprisingly similar without explicit adaptation of the codeword construction to the modulation. The result also holds for the multiple access and the broadcast Gaussian channels, when signal-to-noise ratio is low. Moreover, the two modulations can be even mixed together in a single codeword resulting in a hybrid modulation with asymptotically close decoding behavior. In this sense the matched filter decoder demonstrates the performance that is largely insensitive to the choice of binary versus Gaussian modulation.

Consider the situation where a word is chosen probabilistically from a finite list. If an attacker knows the list and can inquire about each word in turn, then selecting the word via the uniform distribution maximizes the attacker's difficulty, its Guesswork, in identifying the chosen word. It is tempting to use this property in cryptanalysis of computationally secure ciphers by assuming coded words are drawn from a source's typical set and so, for all intents and purposes, uniformly distributed within it. By applying recent results on Guesswork, for i.i.d. sources it is this equipartition ansatz that we investigate here. In particular, we demonstrate that the expected Guesswork for a source conditioned to create words in the typical set grows, with word length, at a lower exponential rate than that of the uniform approximation, suggesting use of the approximation is ill-advised.

Motivated by the framework of network equivalence theory [1], [2], we present capacity lower bounding models for wireless networks by construction of noiseless networks which can be used to calculate an inner bound for the corresponding wireless network. We first extend the “one-shot” lower bounding model [6] to many-user scenarios, and then propose a two-step update of the one-shot models to incorporate the broadcast nature of wireless transmission. The main advantage of the proposed lower bounding method is its simplicity and the fact that it can be easily extended to larger networks. We demonstrate by examples that the resulting lower bounds can even approach the capacity in some setups.

We study two-unicast-Z networks1- two-source two-destination (two-unicast) wireline networks over directed acyclic graphs, where one of the two destinations (say the second destination) is apriori aware of the interfering (first) source's message. For certain classes of two-unicast-Z networks, we show that the rate-tuple (N, 1) is achievable as long as the individual source-destination cuts for the two source-destination pairs are respectively at least as large as N and 1, and the generalized network sharing cut - a bound previously defined by Kamath et. al. - is at least as large as N +1. We show this through a novel achievable scheme which is based on random linear coding at all the edges in the network, except at the GNS-cut set edges, where the linear coding co-efficients are chosen in a structured manner to cancel interference at the receiver first destination.

Existing mobile devices have the capability to use multiple network technologies simultaneously to help increase performance; but they rarely, if at all, effectively use these technologies in parallel. We first present empirical data to help understand the mobile environment when three heterogeneous networks are available to the mobile device (i.e., a WiFi network, WiMax network, and an Iridium satellite network). We then propose a reliable, multi-path protocol called Multi-Path TCP with Network Coding (MPTCP/NC) that utilizes each of these networks in parallel. An analytical model is developed and a mean-field approximation is derived that gives an estimate of the protocol's achievable throughput. Finally, a comparison between MPTCP and MPTCP/NC is presented using both the empirical data and mean-field approximation. Our results show that network coding can provide users in mobile environments a higher quality of service by enabling the use of multiple network technologies and the capability to overcome packet losses due to lossy, wireless network connections.

We investigate capacity bounds for a wireless multicast relay network where two sources simultaneously multicast to two destinations with the help of a full-duplex relay node. The two sources and the relay use the same channel resources (i.e. co-channel transmission). We assume Gaussian channels with time-invariant channel gains which are known by all nodes. The two source nodes are connected by orthogonal limited-rate error-free conferencing links. By extending the proof of the converse for the Gaussian relay channel and introducing two lemmas on conditional (co-)variance, we present two genie-aided outer bounds of the capacity region for this multicast relay network. We extend noisy network coding to use source cooperation with the help of the theory of network equivalence. We also propose a new coding scheme, partial-decode-and-forward based linear network coding, which is essentially a hybrid scheme utilizing rate-splitting and messages conferencing at the source nodes, partial decoding and linear network coding at the relay, and joint decoding at each destination. A low-complexity alternative scheme, analog network coding based on amplify-and-forward relaying, is also investigated and shown to benefit greatly from the help of the conferencing links and can even outperform noisy network coding when the coherent combining gain is dominant.

The throughput benefits of random linear network codes have been studied extensively for wirelined and wireless erasure networks. It is often assumed that all nodes within a network perform coding operations. In energy-constrained systems, however, coding subgraphs should be chosen to control the number of coding nodes while maintaining throughput. In this paper, we explore the strategic use of network coding in the wireless packet erasure relay channel according to both throughput and energy metrics. In the relay channel, a single source communicates to a single sink through the aid of a half-duplex relay. The fluid flow model is used to describe the case where both the source and the relay are coding, and Markov chain models are proposed to describe packet evolution if only the source or only the relay is coding. In addition to transmission energy, we take into account coding and reception energies. We show that coding at the relay alone while operating in a rateless fashion is neither throughput nor energy efficient. Given a set of system parameters, our analysis determines the optimal amount of time the relay should participate in the transmission, and where coding should be performed.

We consider an Adaptive Random Convolutional Network Coding (ARCNC) algorithm to address the issue of field size in random network coding for multicast, and study its memory and decoding delay performances through both analysis and numerical simulations. ARCNC operates as a convolutional code, with the coefficients of local encoding kernels chosen randomly over a small finite field. The cardinality of local encoding kernels increases with time until the global encoding kernel matrices at the related sink nodes have full rank. ARCNC adapts to unknown network topologies without prior knowledge, by locally incrementing the dimensionality of the convolutional code. Because convolutional codes of different constraint lengths can coexist in different portions of the network, reductions in decoding delay and memory overheads can be achieved. We show that this method performs no worse than block linear network codes in terms of decodability, and can provide significant gains in terms of average decoding delay or memory in combination, shuttle and random geometric networks.

In this paper, we introduce a time-stampless adaptive nonuniform sampling (TANS) framework, in which time increments between samples are determined by a function of the m most recent increments and sample values. Since only past samples are used in computing time increments, it is not necessary to save sampling times (time stamps) for use in the reconstruction process. We focus on two TANS schemes for discrete-time stochastic signals: a greedy method, and a method based on dynamic programming. We analyze the performances of these schemes by computing (or bounding) their trade-offs between sampling rate and expected reconstruction distortion for Markovian signals. Simulation results support the analysis of the sampling schemes. We show that by opportunistically adapting to local signal characteristics TANS may lead to improved power efficiency in some applications.

Survivable routing serves as a key role in connection-oriented communication networks for achieving desired service availability for each connection. This is particularly critical for the success of all-optical mesh networks where each lightpath carries a huge amount of data. Currently, 1+1 dedicated path protection appears to be the most widely deployed network resilience mechanism because it offers instantaneous recovery from network failures. However, 1+1 protection consumes almost twice as much capacity as required, which imposes a stringent constraint on network resource utilization. In addition, finding an SRLG-disjoint path is essential for 1+1 protection, which is nonetheless subject to non-trivial computation complexity and may fail in some SRLG scenarios. To address these problems, we introduce a novel framework of 1+1 protection, called Generalized Dedicated Protection (GDP), for achieving instantaneous recovery from any SRLG failure event. It is demonstrated, that finding a non-bifurcated optimal solution for GDP is NP-complete. Thus, the paper presents a novel scheme applying Generalized Dedicated Protection and Network Coding (GDP-NC) to ensure both optimal resource utilization among dedicated protection approaches and instantaneous recovery for single unicast flows, which can be split into multiple parts in all-optical networks. We demonstrate that the proposed GDP-NC survivable routing problem is polynomial-time solvable, owing to the ability to bifurcate flows. This flexibility comes at the expense of additional hardware for linear combination operations for the optical flows.

We design and analyze gossip algorithms for networks with correlated data. In these networks, either the data to be distributed, the data already available at the nodes, or both, are correlated. Although coding schemes for correlated data have been studied extensively, the focus has been on characterizing the rate region in static memory-free networks. In a gossip-based scheme, however, nodes communicate among each other by continuously exchanging packets according to some underlying communication model. The main figure of merit in this setting is the stopping time - the time required until nodes can successfully decode. While Gossip schemes are practical, distributed and scalable, they have only been studied for uncorrelated data. We wish to close this gap by providing techniques to analyze network coded gossip in (dynamic) networks with correlated data. We give a clean framework for oblivious network models that applies to a multitude of network and communication scenarios, specify a general setting for distributed correlated data, and give tight bounds on the stopping times of network coded protocols in this wide range of scenarios.

This paper shows how to reduce the otherwise hard joint relay positioning and flow optimization problem into a sequence a two simpler decoupled problems. We consider a class of wireless multicast hypergraphs not limited by interference and are mainly characterized by their hyperarc rate functions, that are increasing and convex in power, and decreasing in distance between the transmit node and the farthest end node of the hyperarc. The set-up consists of a single multicast flow session involving a source, multiple destinations and a relay that can be positioned freely. The first problem formulates the relay positioning problem in a purely geometric sense, and once the optimal relay position is obtained the second problem addresses the flow optimization. Furthermore, simple and efficient algorithms are presented that solve these problems.

Throughput and per-packet delay can present strong trade-offs that are important in the cases of delay sensitive applications. We investigate such trade-offs using a random linear network coding scheme for one or more receivers in single hop wireless packet erasure broadcast channels. We capture the delay sensitivities across different types of network applications using a class of delay metrics based on the norms of packet arrival times. With these delay metrics, we establish a unified framework to characterize the rate and delay requirements of applications and to optimize system parameters. In the single receiver case, we demonstrate the trade-off between average packet delay, which we view as the inverse of throughput, and maximum inorder inter-arrival delay for various system parameters. For a single broadcast channel with multiple receivers having different delay constraints and feedback delays, we jointly optimize the coding parameters and time-division scheduling parameters at the transmitter. We formulate the optimization problem as a Generalized Geometric Program (GGP). This approach allows the transmitter to adjust adaptively the coding and scheduling parameters for efficient allocation of network resources under varying delay constraints. In the case where the receivers are served by multiple non-interfering wireless broadcast channels, the same optimization problem is formulated as a Signomial Program, which is NP-hard in general. We provide approximation methods using successive formulation of geometric programs and show the convergence of approximations.

In this paper we study in-order packet delivery delay of two recently proposed network coded transmission schemes with applications in wireless broadcast. Unlike previous works where asymptotic behaviour of decoding or delivery delay was presented, we provide a general analysis of the three conditions under which in-order packet delivery is possible at a receiver: by 1) catching up with the sender, 2) receiving while a leader, and 3) chance decoding. We use a Markov model to represent the difference between the knowledge space of the sender and a receiver. For the first condition, we calculate the expected distribution of decoding cycle lengths under the Markov model. For the second condition, we propose to use a simplifying independent Markov model among receivers to shed light on the factors that determine the probability of receiving while a leader. Finally, we compare the chance decoding probabilities of two transmission schemes and a baseline random transmission algorithm to show that surprisingly (and fortunately) the probability of chance decoding is significant in one of the transmission schemes. We verify our analysis by extensive simulations and discuss the usefulness of our study for understanding and design of better transmission algorithms.

We design a cross-layer approach to aid in developing a cooperative solution using multi-packet reception (MPR), network coding (NC), and medium access (MAC). We construct a model for the behavior of the IEEE 802.11 MAC protocol and apply it to key small canonical topology components and their larger counterparts. The results obtained from this model match the available experimental results with fidelity. Using this model, we show that fairness allocation by the 802.11 MAC can significantly impede performance; hence, we devise a new MAC that not only substantially improves throughput, but provides fairness to flows of information rather than to nodes. We show that cooperation between NC, MPR, and our new MAC achieves super-additive gains of up to 6.3 times that of routing with the standard 802.11 MAC. Furthermore, we extend the model to analyze our MAC's asymptotic and throughput behaviors as the number of nodes increases or the MPR capability is limited to only a single node. Finally, we show that although network performance is reduced under substantial asymmetry or limited implementation of MPR to a central node, there are some important practical cases, even under these conditions, where MPR, NC, and their combination provide significant gains.

We introduce a novel feedback protocol, called SMART, for wireless broadcast networks that use linear network coding. We consider transmission of packets from a single source to many receivers over a single-hop broadcast erasure channel with heterogeneous links. We propose a predictive model to minimize feedback as well as extraneous data transmissions by the source. In addition, we use the method of types to provide a lower bound for the expected total transmission time, and use simulations to show that our protocol operates close to this lower bound. We show that with SMART, counter to conventional wisdom, the average user's QoE improves slightly as the number of users increases. We demonstrate that SMART's algorithmic simplicity enables multicast transmissions that on average take fewer than 2 feedback rounds to complete. We show the favorable scalability of our technique with the number of users, which enables reliable quality of experience. We also show the robustness of this scheme to uncertainty in the number of receiving nodes, and packet erasure probability, as well as to partial loss of the feedback. Furthermore, we show that SMART performs nearly as well as an omniscient transmitter that requires no feedback.

In this paper, we review recent networking developments that will help create the next-generation social television experiences. These include revisiting the way networks are created and using social connectivity to drive physical connectivity and network virtualization. Multipath dissemination and reduction of interruptions will provide better quality of experience. Content protection and privacy are also essential to enable social commentary and metadata applications and will be briefly introduced. Examples of potential applications and results of field trials are also included.

We focus on the problem of secure distributed storage over multiple untrusted clouds or networks. Our main contribution is a low complexity scheme that relies on erasure coding techniques for achieving prescribed levels of confidentiality and reliability. Using matrices that have no singular square submatrices, we subject the original data to a linear transformation. The resulting coded symbols are then stored in different networks. This scheme allows users with access to a threshold number of networks to reconstruct perfectly the original data, while ensuring that eavesdroppers with access to any number of networks smaller than this threshold are unable to decode any of the original symbols. This holds even if the attackers are able to guess some of the missing symbols. We further quantify the achievable level of security, and analyze the complexity of the proposed scheme.

In networks with large latency, feedback about received packets may lag considerably the transmission of the original packets, limiting the feedback's usefulness. Moreover, time duplex constraints may entail that receiving feedback may be costly. In this work, we consider tailoring feedback and coding jointly in such settings to reduce the expected delay for successful in order reception of packets. We find that, in certain applications, judicious choices provide results that are close to those that would be obtained with a full-duplex system. We study two cases of data transmission: one-to-all broadcast and all-to-all broadcast. We also analyze important practical considerations weighing the trade off between performance and complexity in applications that rely on random linear network coding. Finally, we study the problem of transmission of information under the large latency and time duplexing constraints in the presence of random packet arrivals. In particular, we analyze the problem of using a batch by batch approach and an online network coding approach with Poisson arrivals. We present numerical results to illustrate the performance under a variety of scenarios and show the benefits of the proposed schemes as compared to typical ARQ and scheduling schemes.

In the simplest relaying strategy, a network node amplifies and forwards a received signal over a wireless channel. Multihop amplify-and-forward allows for a (noisy) linear combination of signals simultaneously sent from multiple sources to be propagated through the network over multiple layers of relays. The performance of multihop amplify-and-forward is limited by noise propagated to the destination over multiple hops, and we expect this strategy to perform well only in high SNR. In this paper, this intuition is formalized and high-SNR conditions under which multihop amplify-and-forward approaches capacity in a layered relay network are determined. By relating the received signal power and the received power of the propagated noise at the nodes, the rate achievable with multihop amplify-and-forward is determined. In particular, when all received powers are lower bounded by$1/\delta $, the noise power propagated to the destination over$L$layers is of the order$L\delta $. The result demonstrates that multihop amplify-and-forward approaches the cut-set bound as received powers at relays increase. As all powers in the network increase at the same rate, the multihop amplify-and-forward rate and the upper bound are within a gap that is independent of channel gains. This gap grows linearly with the number of nodes.

We consider multicasting using random linear network coding over a multihop wireless network in the bandwidth limited regime. We address the associated medium access problem and propose a scheduling technique that activates hyperarcs rather than links, as in classical scheduling approaches. We encapsulate the constraints on valid network configurations in a conflict graph model and formulate a joint optimization problem taking into account both the network coding subgraph and the schedule. Next, using Lagrangian relaxation, we decompose the overall problem into two subproblems, a multiple-shortest-paths problem and a maximum weighted stable set (MWSS) problem. We show that if we use a greedy heuristic for the MWSS part of the problem, the overall algorithm is completely distributed. We provide extensive simulation results for both the centralized optimal and the decentralized algorithms. The optimal algorithm improves performance by up to a factor of two over widely used techniques such as orthogonal or two-hop-constrained scheduling. The decentralized algorithm is shown to buy its distributed operation with some throughput losses. Experimental results on randomly generated networks suggest that these losses are not large. Finally, we study the power consumption of our scheme and quantify the tradeoff between power and bandwidth efficiency.

We present a novel feedback protocol for wireless broadcast networks that utilize linear network coding. We consider transmission of packets from one source to many receivers over a single-hop broadcast erasure channel. Our method utilizes a predictive model to request feedback only when the probability that all receivers have completed decoding is significant. In addition, our proposed NACK-based feedback mechanism enables all receivers to request, within a single time slot, the number of retransmissions needed for successful decoding. We present simulation results as well as analytical results that show the favorable scalability of our technique as the number of receivers, file size, and packet erasure probability increase. We also show the robustness of this scheme to uncertainty in the predictive model, including uncertainty in the number of receiving nodes and the packet erasure probability, as well as to losses of the feedback itself. Our scheme, SMART, is shown to perform nearly as well as an omniscient transmitter that requires no feedback. Furthermore, SMART, is shown to outperform current state of the art methods at any given erasure probability, file size, and numbers of receivers.

Random Linear Network Coding (RLNC) provides a theoretically efficient method for coding. The drawbacks associated with it are the complexity of the decoding and the overhead resulting from the encoding vector. Increasing the field size and generation length presents a fundamental trade-off between packet-based throughput and operational overhead. On the one hand, decreasing the probability of redundant packets' being transmitted is beneficial for throughput and, consequently, reduces transmission energy. On the other hand, the decoding complexity and amount of header overhead increase with field size and generation length, leading to higher energy consumption. The main findings of this work are bounds for the transmission overhead due to linearly dependent packets. The optimal trade-off is system and topology dependent, as it depends on the cost in energy of performing coding operations versus transmitting data. We show that moderate field sizes are the correct choice when trade-offs are considered. The results show that sparse binary codes perform the best, unless the generation size is very low.

This paper addresses the problem of inter-session network coding to maximize throughput for multiple communication sessions in wireless networks. We introduce virtual multicast connections which can extract packets from original sessions and code them together. Random linear network codes can be used for these virtual multicasts. The problem can be stated as a flow-based convex optimization problem with side constraints. The proposed formulation provides a rate region which is at least as large as the region without inter-session network coding. We show the benefits of our technique for several scenarios by means of simulation.

We consider the broadcast relay channel (BRC), where a single source transmits to multiple destinations with the help of a relay, in the limit of a large bandwidth. We address the problem of optimal relay positioning and power allocations at source and relay, to maximize the multicast rate from source to all destinations. To solve such a network planning problem, we develop a three-faceted approach based on an underlying information theoretic model, computational geometric aspects, and network optimization tools. Firstly, assuming superposition coding and frequency division between the source and the relay, the information theoretic framework yields a hypergraph model of the wideband BRC, which captures the dependency of achievable rate-tuples on the network topology. As the relay position varies, so does the set of hyperarcs constituting the hypergraph, rendering the combinatorial nature of optimization problem. We show that the convex hull C of all nodes in the 2-D plane can be divided into disjoint regions corresponding to distinct hyperarcs sets. These sets are obtained by superimposing all k-th order Voronoi tessellation of C. We propose an easy and efficient algorithm to compute all hyperarc sets, and prove they are polynomially bounded. Then, we circumvent the combinatorial nature of the problem by introducing continuous switch functions, that allows adapting the network hypergraph in a continuous manner. Using this switched hypergraph approach, we model the original problem as a continuous yet non-convex network optimization program. Ultimately, availing on the techniques of geometric programming and p-norm surrogate approximation, we derive a good convex approximation. We provide a detailed characterization of the problem for collinearly located destinations, and then give a generalization for arbitrarily located destinations. Finally, we show strong gains for the optimal relay positioning compared to seemingly interesting positions.

We propose an efficient Adaptive Random Convolutional Network Coding (ARCNC) algorithm to address the issue of field size in random network coding. ARCNC operates as a convolutional code, with the coefficients of local encoding kernels chosen randomly over a small finite field. The lengths of local encoding kernels increase with time until the global encoding kernel matrices at related sink nodes all have full rank. Instead of estimating the necessary field size a priori, ARCNC operates in a small finite field. It adapts to unknown network topologies without prior knowledge, by locally incrementing the dimensionality of the convolutional code. Because convolutional codes of different constraint lengths can coexist in different portions of the network, reductions in decoding delay and memory overheads can be achieved with ARCNC.We show through analysis that this method performs no worse than random linear network codes in general networks, and can provide significant gains in terms of average decoding delay in combination networks.

Random Linear Network Coding (RLNC) has emerged as a powerful tool for robust high-throughput multicast. Projection analysis, a recently introduced technique, shows that the distributed packetized RLNC protocol achieves (order) optimal and perfectly pipelined information dissemination in many settings. In the original approach to RNLC intermediate nodes code together all available information. This requires intermediate nodes to keep considerable data available for coding. Moreover, it results in a coding complexity that grows linearly with the size of this data. While this has been identified as a problem, approaches that combine queuing theory and network coding have heretofore not provided a succinct representation of the memory needs of network coding at intermediates nodes. This paper shows the surprising result that, in all settings with a continuous stream of data, network coding continues to perform optimally even if only one packet per node is kept in active memory and used for computations. This leads to an extremely simple RLNC protocol variant with drastically reduced requirements on computational and memory resources. By extending the projection analysis, we show that in all settings in which the RLNC protocol was proven to be optimal its finite memory variant performs equally well. In the same way as the original projection analysis, our technique applies in a wide variety of network models, including highly dynamic topologies that can change completely at any time in an adversarial fashion.

We define a notion of network capacity region of networks that generalizes the notion of network capacity defined by Cannons et al. and prove its notable properties such as closedness, boundedness and convexity when the finite field is fixed. We show that the network routing capacity region is a computable rational polytope and provide exact algorithms and approximation heuristics for computing the region. We define the semi-network linear coding capacity region, with respect to a fixed finite field, that inner bounds the corresponding network linear coding capacity region, show that it is a computable rational polytope, and provide exact algorithms and approximation heuristics. We show connections between computing these regions and a polytope reconstruction problem and some combinatorial optimization problems, such as the minimum cost directed Steiner tree problem. We provide an example to illustrate our results. The algorithms are not necessarily polynomial-time.

Abstract-We provide a geometric solution to the problem of optimal relay positioning to maximize the multicast rate for low SNR networks. The network we consider consists of a single source, multiple receivers and the only intermediate and locatable node as the relay. We construct network the hypergraph of the system nodes from the underlying information theoretic model of low-SNR regime that operates using superposition coding and FDMA in conjunction (which we call the "achievable hypergraph model"). We make the following contributions. 1) We show that the problem of optimal relay positioning maximizing the multicast rate can be completely decoupled from the flow optimization by noticing and exploiting geometric properties of multicast flow. 2) All the flow maximizing the multicast rate is sent over at most two paths, in succession. The relay position depends on only one path (out of the two), irrespective of the number of receiver nodes in the system. Subsequently, we propose simple and efficient geometric algorithms to compute the optimal relay position. 3) Finally, we show that in our model at the optimal relay position, the difference between the maximized multicast rate and the cut-set bound is minimum. We solve the problem for all (Ps,Pr) pairs of source and relay transmit powers and the path loss exponent α ≥ 2.

The recently introduced network equivalence results are used to create bit-pipe models that can replace multi-terminal channels within a discrete memoryless network. The goal is to create a set of simple “components” or “blocks” that can be substituted for the channel in such a way that the resulting network is capable of emulating the operation of the original one. We develop general upper and lower bounding models for the multiple access channel and for a class of broadcast channels. These bounds are sharp in the sense that there exists networks where the original channel can achieve the maximum sum rate permissible through the upper or lower bounding models. This approach provides a simple method for analyzing the capacity of large networks, which we illustrate with an example.

We investigate the multipath fading relay channel in the limit of a large bandwidth, and in the non-coherent setting, where the channel state is unknown to all terminals, including the relay and the destination. We derive a lower bound on the capacity by proposing and analyzing a peaky frequency binning scheme. The achievable rate obtained coincides with the block-Markov lower bound on the capacity of the wideband frequency-division Gaussian relay channel. When the broadcast channel is physically degraded, this achievable rate meets the cut-set upper-bound, and thus reaches the capacity of the noncoherent wideband multipath fading relay channel. In this case, a hypergraph model of the multipath fading relay channel is proposed, and the relaying scheme of concern is shown to reach its min-cut. Even if the source treats the broadcast channel as physically degraded when it is stochastically degraded, the achievable hypergraph bound is the min-cut.

We analyze distributed and packetized implementations of random linear network coding (PNC) with buffers. In these protocols, nodes store received packets to later produce coded packets that reflect this information. We show the optimality of PNC for any buffer size; i.e., we show that PNC performs at least as good as any protocols with the same buffer size. In other words, a multicast task completes at exactly the first time in which in hindsight it was possible to route information from the sources to each receiver individually given the buffer constraint, i.e., that the buffer used at each node never exceeds its buffer size. This shows that PNC, even without any feedback or explicit buffer management, allows to keep minimal buffer sizes while maintaining its optimal performance.

We propose a secure scheme for wireless network coding, called the algebraic watchdog. By enabling nodes to detect malicious behaviors probabilistically and use overheard messages to police their downstream neighbors locally, the algebraic watchdog delivers a secure global self-checking network. Unlike traditional Byzantine detection protocols which are receiver-based, this protocol gives the senders an active role in checking the node downstream. The key idea is inspired by Marti et al.'s watchdog-pathrater, which attempts to detect and mitigate the effects of routing misbehavior. We first focus on a two-hop network. We present a graphical model to understand the inference process nodes execute to police their downstream neighbors; as well as to compute, analyze, and approximate the probabilities of misdetection and false detection. We also present an algebraic analysis of the performance using an hypothesis testing framework that provides exact formulae for probabilities of false detection and misdetection. We then extend the algebraic watchdog to a more general network setting, and propose a protocol in which we can establish trust in coded systems in a distributed manner. We develop a graphical model to detect the presence of an adversarial node downstream within a general multi-hop network. The structure of the graphical model (a trellis) lends itself to well-known algorithms (e.g. the Viterbi algorithm) which can compute the probabilities of misdetection and false detection. We show that as long as the min-cut is not dominated by the adversaries, upstream nodes can monitor downstream neighbors and allow reliable communication with certain probability. Finally, we present simulation results that support our analysis.

We take an analytical approach to study fundamental rate-delay-reliability trade-offs in the context of media streaming. We consider the probability of interruption in media playback (buffer underflow) as well as the number of initially buffered packets (initial waiting time) as the Quality of user Experience (QoE) metrics. We characterize the optimal trade-off between these metrics as a function of system parameters such as the packet arrival rate and file size, for different channel models. In the first model, we assume packets arrive according to independent Poisson processes from multiple servers or peers. We use random linear network coding to simplify the packet requests at the network layer and avoid duplicate packet reception. This allows us to model the receiver's buffer as a queue with Poisson arrivals and deterministic departures. For this model, we show that for arrival rates slightly larger than the play rate, the minimum initial buffering required to achieve certain level of interruption probability remains bounded as the file size grows. This is not the case when the arrival rate and the play rate match. In the second model, we consider channels with memory, which can be modeled using Markovian arrival processes. We characterize the optimal trade-off curves for the infinite file size case, in such Markovian environments.

We introduce the concept of a fiber aided wireless network architecture (FAWNA), which allows high-speed mobile connectivity by leveraging the speed of optical networks. Specifically, we consider a single-input, multiple-output (SIMO) FAWNA, which consists of a SIMO wireless channel interfaced with an optical fiber channel through wireless-optical interfaces. We propose a design where the received wireless signal at each interface is sampled and quantized before being sent over the fiber. The capacity of our scheme approaches the capacity of the architecture, exponentially with fiber capacity. We also show that for a given fiber capacity, there is an optimal operating wireless bandwidth and number of interfaces. We show that the optimal way to divide the fiber capacity among the interfaces is to ensure that each interface gets enough rate so that its noise is dominated by front end noise rather than by quantizer distortion. We also show that rather than dynamically change rate allocation based on channel state, a less complex, fixed rate allocation scheme can be adopted with very small loss in performance.

The theory of network coding promises significant benefits in network performance, especially in lossy networks and in multicast and multipath scenarios. To realize these benefits in practice, we need to understand how coding across packets interacts with the acknowledgment (ACK)-based flow control mechanism that forms a central part of today's Internet protocols such as transmission control protocol (TCP). Current approaches such as rateless codes and batch-based coding are not compatible with TCP's retransmission and sliding-window mechanisms. In this paper, we propose a new mechanism called TCP/NC that incorporates network coding into TCP with only minor changes to the protocol stack, thereby allowing incremental deployment. In our scheme, the source transmits random linear combinations of packets currently in the congestion window. At the heart of our scheme is a new interpretation of ACKs-the sink acknowledges every degree of freedom (i.e., a linear combination that reveals one unit of new information) even if it does not reveal an original packet immediately. Thus, our new TCP ACK rule takes into account the network coding operations in the lower layer and enables a TCP-compatible sliding-window approach to network coding. Coding essentially masks losses from the congestion control algorithm and allows TCP/NC to react smoothly to losses, resulting in a novel and effective approach for congestion control over lossy networks such as wireless networks. An important feature of our solution is that it allows intermediate nodes to perform re-encoding of packets, which is known to provide significant throughput gains in lossy networks and multicast scenarios. Simulations show that our scheme, with or without re-encoding inside the network, achieves much higher throughput compared to TCP over lossy wireless links. We present a real-world implementation of this protocol that addresses the practical aspects of incorporating network coding and decoding with TCP's window management mechanism. We work with TCP-Reno, which is a widespread and practical variant of TCP. Our implementation significantly advances the goal of designing a deployable, general, TCP-compatible protocol that provides the benefits of network coding.

We study joint network and channel code design to optimize delay performance. Here the delay is the transmission time of information packets from a source to sinks without considering queuing effects. In our systems, network codes (network layer) are on top of channel codes (physical layer) which are disturbed by noise. Network codes run in a rateless random method, and thus have erasure-correction capability. For the constraint of finite transmission time, transmission errors are inevitable in the physical layer. A detection error in the physical layer means an erasure of network codewords. For the analysis, we model the delay of each information generation in the network layer as independent, identically distributed random variables. The calculation approaches for delay measures are investigated for coded erasure networks. We show how to evaluate the rate and erasure probability of a set of channels belonging to one cut. We also show that the min-cut determines the decoding error probability in the sinks if the number of information packets is large. We observe that for a given amount of source information, larger packet length leads to fewer packets to be transmitted but higher physical-layer detection error probabilities. Further, longer transmission time (delay) in the physical-layer causes smaller detection error probability at the physical layer. Thus, both parameters have opposite impacts on the physical and network layer, considering delay. We should find the optimal values of them in a cross-layer approach. We then formulate the problems of optimizing delay performance, and discuss solutions for them.

Content distribution over networks is often achieved by using mirror sites that hold copies of files or portions thereof to avoid congestion and delay issues arising from excessive demands to a single location. Accordingly, there are distributed storage solutions that divide the file into pieces and place copies of the pieces (replication) or coded versions of the pieces (coding) at multiple source nodes. We consider a network which uses network coding for multicasting the file. There is a set of source nodes that contains either subsets or coded versions of the pieces of the file. The cost of a given storage solution is defined as the sum of the storage cost and the cost of the flows required to support the multicast. Our interest is in finding the storage capacities and flows at minimum combined cost. We formulate the corresponding optimization problems by using the theory of information measures. In particular, we show that when there are two source nodes, there is no loss in considering subset sources. For three source nodes, we derive a tight upper bound on the cost gap between the coded and uncoded cases. We also present algorithms for determining the content of the source nodes.

The problem of serving multicast flows in a crossbar switch is considered. Intraflow linear network coding is shown to achieve a larger rate region than the case without coding. A traffic pattern is presented which is achievable with coding but requires a switch speedup when coding is not allowed. The rate region with coding can be characterized in a simple graph-theoretic manner, in terms of the stable set polytope of the "enhanced conflict graph". No such graph-theoretic characterization is known for the case of fanout-splitting without coding. The minimum speedup needed to achieve 100% throughput with coding is shown to be upper bounded by the imperfection ratio of the enhanced conflict graph, where the imperfection ratio measures a certain graph theoretic property of the given graph. When applied to K × N switches with unicasts and broadcasts only, this gives a bound of min(2K-1/K, 2N/N+1) on the speedup. This shows that speedup, which is usually implemented in hardware, can often be substituted by network coding, which can be done in software. Computing an offline schedule (using prior knowledge of the flow rates) is reduced to fractional weighted graph coloring. A graph-theoretic online scheduling algorithm (using only queue occupancy information) is also proposed, that stabilizes the queues for all rates within the rate region.

A family of equivalence tools for bounding network capacities is introduced. Given a networkNwith node setV, the capacity ofNis a set of non-negative vectors with elements corresponding to all possible multicast connections inN; a vector ℜ is in the capacity region forNif and only if it is possible to simultaneously and reliably establish all multicast connections acrossNat the given rates. Any other demand type with independent messages is a special case of this multiple multicast problem, and is therefore included in the given rate region. In Part I, we show that the capacity of a networkNis unchanged if any independent, memoryless, point-to-point channel inNis replaced by a noiseless bit pipe with throughput equal to the removed channel's capacity. It follows that the capacity of a network comprised entirely of such point-to-point channels equals the capacity of an error-free network that replaces each channel by a noiseless bit pipe of the corresponding capacity. A related separation result was known previously for a single multicast connection over an acyclic network of independent, memoryless, point-to-point channels; our result treats general connections (e.g., a collection of simultaneous unicasts) and allows cyclic or acyclic networks.

The impact of Internet content and IP based television on networks is growing. Video is now ubiquitous in the home and on the street. It demands new approaches to video transmission to meet the growing traffic volume. This paper presents a novel strategy for network coding in video transmission. It uses a variety of coding approaches and adds feedback and device discovery to tailor the coding to the receiver ecosystems and can achieve better overall performance than the non coded versions.

We study an online random linear network coding approach for time division duplexing (TDD) channels under Poisson arrivals. We model the system as a bulk-service queue with variable bulk size and with feedback, i.e., when a set of packets are serviced at a given time, they might be reintroduced to the queue to form part of the next service batch. We show that there is an optimal number of coded data packets that the sender should transmit back-to-back before stopping to wait for an acknowledgement from the receiver. This number depends on the latency, probability of packet erasure, degrees of freedom at the receiver, the size of the coding window, and the arrival rate of the Poisson process. Random network coding is performed across a moving window of packets that depends on the packets in the queue, design constraints on the window size, and the feedback sent from the receiver. We study the mean time between generating a packet at the source and it being "seen", but not necessarily decoded, at the receiver. We also analyze the mean time between a decoding event and the next, defined as the decoding of all the packets that have been previously "seen" and those packets involved in the current window of packets. Inherently, a decoding event implies an in-order decoding of a batch of data packets. We present numerical results illustrating the trade-off between mean delay and mean time between decoding events.

We consider distributed storage over two untrusted networks, whereby coding is used as a means to achieve a prescribed level of confidentiality. The key idea is to exploit the algebraic structure of the Vandermonde matrix to mix the input blocks, before they are stored in different locations. The proposed scheme ensures that eavesdroppers with access to only one of the networks are unable to decode any symbol even if they are capable of guessing some of the missing blocks. Information-theoretic techniques allow us to quantify the achievable level of confidentiality. Moreover, the proposed approach is shown to offer low complexity and optimal rate.

The rate optimization for wireless networks with low SNR is investigated. While the capacity in the limit of disappearing SNR is known to be linear for fading and non-fading channels, we study the problem of operating in low SNR wireless network with given node locations that use network coding over flows. The model we develop for low SNR Gaussian broadcast channel and multiple access channel respectively operates in a non-trivial feasible rate region. We show that the problem reduces to the optimization of total network power which can be casted as standard linear multi-commodity min-cost flow program with no inherent combinatorially difficult structure when network coding is used with non integer constraints (which is a reasonable assumption). This is essentially due to the linearity of the capacity with respect to vanishing SNR which helps avoid the effect of interference for the degraded broadcast channel and multiple access environment in consideration, respectively. We propose a fully decentralized Primal-Dual Subgradient Algorithm for achieving optimal rates on each subgraph (i.e. hyperarcs) of the network to support the set of traffic demands (multicast/unicast connections).

We consider the problem of setting up a multicast connection of minimum cost using network coding. It is well-known that this can be posed in the form of a convex program. Our contribution is an asynchronous algorithm for solving the optimization problem, in analogy to the well-known distributed asynchronous Bellman-Ford algorithm for routing. Furthermore, we provide extensive simulation results showing fast convergence despite the lack of any central clock in the network and robustness with respect to link- or node failures.

Multi-resolution codes enable multicast at different rates to different receivers, a setup that is often desirable for graphics or video streaming. We propose a simple, distributed, two-stage message passing algorithm to generate network codes for single-source multicast of multi-resolution codes. The goal of this pushback algorithm is to maximize the total rate achieved by all receivers, while guaranteeing decodability of the base layer at each receiver. By conducting pushback and code assignment stages, this algorithm takes advantage of inter-layer as well as intra-layer coding. Numerical simulations show that in terms of total rate achieved, the pushback algorithm outperforms routing and intra-layer coding schemes, even with field sizes as small as 2^10(10 bits). In addition, the performance gap widens as the number of receivers and the number of nodes in the network increases. We also observe that naive inter-layer coding schemes may perform worse than intra-layer schemes under certain network conditions.

We investigate the multipath fading relay channel in the limit of a large bandwidth, and in the non-coherent setting, where the channel state is unknown to all terminals, including the relay and the destination.We propose a hypergraph model of the wideband multipath fading relay channel, and show that its min-cut is achieved by a non-coherent peaky frequency binning scheme. The so-obtained lower bound on the capacity of the wideband multipath fading relay channel turns out to coincide with the block-Markov lower bound on the capacity of the wideband frequency-division Gaussian (FD-AWGN) relay channel. In certain cases, this achievable rate also meets the cut-set upper-bound, and thus reaches the capacity of the non-coherent wideband multipath fading relay channel.

In this paper, we consider the problem of finding the minimum entropy coloring of a characteristic graph under some conditions which allow it to be in polynomial time. This problem arises in the functional compression problem where the computation of a function of sources is desired at the receiver. The rate region of the functional compression problem has been considered in some references under some assumptions. Recently, Feizi et al. computed this rate region for a general one-stage tree network and its extension to a general tree network. In their proposed coding scheme, one needs to compute the minimum entropy coloring (a coloring random variable which minimizes the entropy) of a characteristic graph. In general, finding this coloring is an NP-hard problem (as shown by Cardinal et al.). However, in this paper, we show that depending on the characteristic graph's structure, there are some interesting cases where finding the minimum entropy coloring is not NP-hard, but tractable and practical. In one of these cases, we show that, having a non-zero joint probability condition on RVs' distributions, for any desired function f, makes characteristic graphs to be formed of some non-overlapping fully-connected maximal independent sets. Therefore, the minimum entropy coloring can be solved in polynomial time. In another case, we show that if f is a quantization function, this problem is also tractable.

We present a systematic network coding approach for time-division duplexing channels. In particular, we study the case of a node transmitting to a single receiver. We show that the use of systematic network coding using XORs can provide the same or close to the same performance in terms of completion time as a random linear network coding scheme that uses a large field size, with the added advantage of requiring fewer and simpler operations during the decoding process. We show that the average computation required to decode using systematic network coding in an erasure channel grows as O(M3Pe3), where M is the number of original packets being coded together, and Pe is the packet erasure probability. This means that systematic network coding requires Pe-3times fewer operations on average than random linear network coding with the same field size.

We take an analytical approach to study Quality of user Experience (QoE) for media streaming applications. We use the fact that random linear network coding applied to blocks of video frames can significantly simplify the packet requests at the network layer and avoid duplicate packet reception. We model the receiver's buffer as a queue with Poisson arrivals and deterministic departures. We consider the probability of interruption in video playback (buffer underflow) as well as the number of initially buffered packets (initial waiting time) as the QoE metrics. We explicitly characterize the optimal trade-off between these metrics by providing upper and lower bounds on the minimum initial buffering required to achieve certain level of interruption probability for different regimes of the system parameters. Our bounds are asymptotically tight as the file size goes to infinity. Further, we show that for arrival rates slightly larger than the play rate, the minimum initial buffering remains bounded as the file size grows. This is not the case when the arrival rate and the play rate match.

Capacity scaling laws are analyzed in an underwater acoustic network with n regularly located nodes. A narrow-band model is assumed where the carrier frequency is allowed to scale as a function of n. In the network, we characterize an attenuation parameter that depends on the frequency scaling as well as the transmission distance. A cut-set upper bound on the throughput scaling is then derived in extended networks. Our result indicates that the upper bound is inversely proportional to the attenuation parameter, thus resulting in a highly power-limited network. Furthermore, we describe an achievable scheme based on the simple nearest-neighbor multi-hop (MH) transmission. It is shown under extended networks that the MH scheme is order-optimal as the attenuation parameter scales exponentially with √n (or faster). Finally, these scaling results are extended to a random network realization.

In our previous work (`An Algebraic Watchdog for Wireless Network Coding'), we proposed a new scheme in which nodes can detect malicious behaviors probabilistically, police their downstream neighbors locally using overheard messages; thus, provide a secure global self-checking network. As the first building block of such a system, we focused on a two-hop network, and presented a graphical model to understand the inference process by which nodes police their downstream neighbors and to compute the probabilities of misdetection and false detection. In this paper, we extend the Algebraic Watchdog to a more general network setting, and propose a protocol in which we can establish trust in coded systems in a distributed manner. We develop a graphical model to detect the presence of an adversarial node downstream within a general two-hop network. The structure of the graphical model (a trellis) lends itself to well-known algorithms, such as Viterbi algorithm, that can compute the probabilities of misdetection and false detection. Using this as a building block, we generalize our scheme to multi-hop networks. We show analytically that as long as the min-cut is not dominated by the Byzantine adversaries, upstream nodes can monitor downstream neighbors and allow reliable communication with certain probability. Finally, we present preliminary simulation results that support our analysis.

Random linear network coding can be used in peerto- peer networks to increase the efficiency of content distribution and distributed storage. However, these systems are particularly susceptible to Byzantine attacks. We quantify the impact of Byzantine attacks on the coded system by evaluating the probability that a receiver node fails to correctly recover a file. We show that even for a small probability of attack, the system fails with overwhelming probability. We then propose a novel signature scheme that allows packet-level Byzantine detection. This scheme allows one-hop containment of the contamination, and saves bandwidth by allowing nodes to detect and drop the contaminated packets. We compare the net cost of our signature scheme with various other Byzantine schemes, and show that when the probability of Byzantine attacks is high, our scheme is the most bandwidth efficient.

Emerging practical schemes indicate that algebraic mixing of different packets by means of random linear network coding can increase the throughput and robustness of streaming services over wireless networks. However, concerns with the security of wireless video, in particular when only some of the users are entitled to the highest quality, have uncovered the need for a network coding scheme capable of ensuring different levels of confidentiality under stringent complexity requirements. We show that the triple goal of hierarchical fidelity levels, robustness against wireless packet loss and efficient security can be achieved by exploiting the algebraic structure of network coding. The key idea is to limit the encryption operations to a critical set of network coding coefficients in combination with multi-resolution video coding. Our contributions include an information-theoretic security analysis of the proposed scheme, a basic system architecture for hierarchical wireless video with network coding and simulation results.

Motivated by applications to sensor networks and privacy preserving databases, we consider the problem of functional compression. The objective is to separately compress possibly correlated discrete sources such that an arbitrary but fixed deterministic function of those sources can be computed given the compressed data from each source. We consider both the lossless and lossy computation of a function. Specifically, we present results of the rate regions for three instances of the problem where there are two sources: 1) lossless computation where one source is available at the decoder; 2) under a special condition, lossless computation where both sources are separately encoded; and 3) lossy computation where one source is available at the decoder. For all of these instances, we present a layered architecture for distributed coding: first preprocess data at each source using colorings of certain characteristic graphs and then use standard distributed source coding (a laSlepian and Wolfs scheme) to compress them. For the first instance, our results extend the approach developed by Orlitsky and Roche (2001) in the sense that our scheme requires simpler structure of coloring rather than independent sets as in the previous case. As an intermediate step to obtain these results, we obtain an asymptotic characterization of conditional graph coloring for an OR product of graphs generalizing a result of Korner (1973), which should be of interest in its own right.

In this paper, we consider the problem of rate and power allocation in a multiple-access channel (MAC). Our objective is to obtain rate and power allocation policies that maximize a general concave utility function of average transmission rates on the information-theoretic capacity region of the MAC without using queue-length information. First, we address the utility maximization problem in a nonfading channel and present a gradient projection algorithm with approximate projections. By exploiting the polymatroid structure of the capacity region, we show that the approximate projection can be implemented in time polynomial in the number of users. Second, we present optimal rate and power allocation policies in a fading channel where channel statistics are known. For the case that channel statistics are unknown and the transmission power is fixed, we propose a greedy rate allocation policy and characterize the performance difference of this policy and the optimal policy in terms of channel variations and structure of the utility function. The numerical results demonstrate superior convergence rate performance for the greedy policy compared to queue-length-based policies. In order to reduce the computational complexity of the greedy policy, we present approximate rate allocation policies which track the greedy policy within a certain neighborhood.

Automated estimation of DNA base-sequences is an important step in genomics and in many other emerging fields in biological and medical sciences. Current automated sequencers process single strands only. To improve the utility of existing technologies, we propose to mix two independent strands prior to electrophoresis, and base-call jointly by applying the sum-product algorithm on factor graphs. We first present a statistical model for DNA sequencing data and examine the model parameters. A practical heuristic is then proposed to estimate the peaks, which are then separated into two source sequences (Major/Minor) by passing messages on a factor graph. Simulation results show that joint base-calling can provide less accurate but valid results for the minor. The algorithm presented provides a basis for future investigation of joint sequencing techniques.

In this paper, we consider the problem of multifunctional compression with side information. The problem is how we can compress a source X so that the receiver is able to compute some deterministic functions f1(X,Y1), ..., fm(X,Ym), where Yi, 1 ? i ? m, are available at the receiver as side information. In, Wyner and Ziv considered this problem for the special case of m = 1 and f1(X, Y1) = X and derived a rate-distortion function. Yamamoto extended this result in to the case of having one general function f1(X,Y1) . Both of these results were in terms of an auxiliary random variable. For the case of zero distortion, in, Orlitsky and Roche gave an interpretation of this variable in terms of properties of the characteristic graph which led to a particular coding scheme. This result was extended in by providing an achievable scheme based on colorings of the characteristic graph. In a recent work, reference has considered this problem for a general tree network where intermediate nodes are allowed to perform some computations. These previous works only considered the case where the receiver only wants to compute one function (m = 1). Here, we want to consider the case in which the receiver wants to compute several functions with different side information random variables and zero distortion. Our results do not depend on the fact that all functions are desired in one receiver and one can apply them to the case of having several receivers with different desired functions (i.e., functions are separable). We define a new concept named the multi-functional graph entropy which is an extension of the graph entropy defined by Korner in. We show that the minimum achievable rate for this problem is equal to the conditional multi-functional graph entropy of random variable X given side informations. We also propose a coding scheme based on graph colorings to achieve this rate.

We study the effect of the field size on the performance of random linear network coding for time division duplexing channels proposed in [1]. In particular, we study the case of a node broadcasting to several receivers. We show that the effect of the field size can be included in the transition probabilities of the Markov chain model of the system. Also, an improved upper bound on the mean number of coded packets required to decode M original data packets using random linear network coding is presented. This bound shows that even if the field size is 2, i.e. we perform XORs amongst randomly selected packets from the pool of M original ones, we will need on average at most M + 2 coded packets in order to decode. Thus, there will be only a very small degradation in performance if M is large. We present numerical results showing that the mean completion time of our scheme with a field size of 2 is close in performance to our scheme when we use larger field sizes. We also show that as M increases, the difference between using a field size of 2 and larger field sizes decreases. Finally, we show that we can get very close to the optimal performance with small field sizes, e.g. a field size of 4 or 8, even when M is not very large.

We consider a wireless multi-hop network and design an algorithm for jointly optimal scheduling of packet transmissions and network coding. We consider network coding across different users, however with the restriction that packets have to be decoded after one hop. We compute the stability region of this scheme and propose an online algorithm that stabilizes every arrival rate vector within the stability region. The online algorithm requires computation of stable sets in an appropriately defined conflict graph. We show by means of simulations that this inherently hard problem is tractable for some instances and that network coding extends the stability region over routing and leads, on average, to a smaller backlog.

We study the energy performance of random linear network coding for time division duplexing channels. We assume a packet erasure channel with nodes that cannot transmit and receive information simultaneously. The sender transmits coded data packets back-to-back before stopping to wait for the receiver to acknowledge the number of degrees of freedom, if any, that are required to decode correctly the information. Our analysis shows that, in terms of mean energy consumed, there is an optimal number of coded data packets to send before stopping to listen. This number depends on the energy needed to transmit each coded packet and the acknowledgment (ACK), probabilities of packet and ACK erasure, and the number of degrees of freedom that the receiver requires to decode the data. We show that its energy performance is superior to that of a full-duplex system. We also study the performance of our scheme when the number of coded packets is chosen to minimize the mean time to complete transmission as in. Energy performance under this optimization criterion is found to be close to optimal, thus providing a good trade-off between energy and time required to complete transmissions.

A wireless packet network is considered in which each user transmits a stream of packets to its destination. The transmit power of each user interferes with the transmission of all other users. A convex cost function of the completion times of the user packets are minimized by optimally allocating the users' transmission power subject to their respective power constraints. It is shown that, at all ranges of SINR, completion time minimization can be formulated as a convex optimization problem and hence can be efficiently solved. When channel knowledge is imperfect, robust power control is considered based on the channel fading distribution subject to outage probability constraints. The problem is shown to be convex when the fading distribution is log-concave in exponentiated channel power gains; e.g., when each user is under independent Rayleigh, Nakagami, or log-normal fading.

In our previous work, we presented optical flow switching (OFS) as a key enabler of scalable future optical networks. In the present work, we propose a practical scheduling algorithm and conduct an approximate throughput-delay analysis for OFS networks.

Whereas the theory and application of optimal network coding are well studied for the single-session multicast scenario, there is no known optimal network coding strategy for a more general connection problem where there are more than one session and receivers may demand different sets of information. Though there have been a number of recent studies that demonstrate various utilities of network coding in the multi- session scenario, they rely on very restricted classes of codes in terms of the coding operations allowed and/or the location of decoding. In this paper, we propose a novel inter-session network coding strategy for a general connection problem. Our coding strategy allows fairly general random linear coding over a large finite field, in which decoding is done at receivers and the mixture of information at interior nodes is controlled by evolutionary mechanisms. We demonstrate how our coding strategy may surpass existing end-to-end pairwise XOR coding schemes in terms of effectiveness and practicality.

A new random linear network coding scheme for reliable communications for time division duplexing channels is proposed. The setup assumes a packet erasure channel and that nodes cannot transmit and receive information simultaneously. The sender transmits coded data packets back-to-back before stopping to wait for the receiver to acknowledge (ACK) the number of degrees of freedom, if any, that are required to decode correctly the information. We provide an analysis of this problem to show that there is an optimal number of coded data packets, in terms of mean completion time, to be sent before stopping to listen. This number depends on the latency, probabilities of packet erasure and ACK erasure, and the number of degrees of freedom that the receiver requires to decode the data. This scheme is optimal in terms of the mean time to complete the transmission of a fixed number of data packets. We show that its performance is very close to that of a full duplex system, while transmitting a different number of coded packets can cause large degradation in performance, especially if latency is high. Also, we study the throughput performance of our scheme and compare it to existing half-duplex go-back-N and selective repeat ARQ schemes. Numerical results, obtained for different latencies, show that our scheme has similar performance to the selective repeat in most cases and considerable performance gain when latency and packet error probability is high.

We propose a mechanism that incorporates network coding into TCP with only minor changes to the protocol stack, thereby allowing incremental deployment. In our scheme, the source transmits random linear combinations of packets currently in the congestion window. At the heart of our scheme is a new interpretation of ACKs - the sink acknowledges every degree of freedom (i.e., a linear combination that reveals one unit of new information) even if it does not reveal an original packet immediately. Such ACKs enable a TCP-compatible sliding-window approach to network coding. Our scheme has the nice property that packet losses are essentially masked from the congestion control algorithm. Our algorithm therefore reacts to packet drops in a smooth manner, resulting in a novel and effective approach for congestion control over networks involving lossy links such as wireless links. Our scheme also allows intermediate nodes to perform re-encoding of the data packets. Our simulations show that our algorithm, with or without re-encoding inside the network, achieves much higher throughput compared to TCP over lossy wireless links. We also establish the soundness and fairness properties of our algorithm. Finally, we present queuing analysis for the case of intermediate node re-encoding.

In this paper, we propose a scheme, called the algebraic watchdog for wireless network coding, in which nodes can detect malicious behaviors probabilistically, police their downstream neighbors locally using overheard messages, and, thus, provide a secure global self-checking network. Unlike traditional Byzantine detection protocols which are receiver-based, this protocol gives the senders an active role in checking the node downstream. This work is inspired by Marti et al.'s watchdog-pathrater, which attempts to detect and mitigate the effects of routing misbehavior. As the first building block of a such system, we focus on a two-hop network. We present a graphical model to understand the inference process nodes execute to police their downstream neighbors; as well as to compute, analyze, and approximate the probabilities of misdetection and false detection. In addition, we present an algebraic analysis of the performance using an hypothesis testing framework, that provides exact formulae for probabilities of false detection and misdetection.

We study the performance of random linear network coding for time division duplexing channels with Poisson arrivals. We model the system as a bulk-service queue with variable bulk size. A full characterization for random linear network coding is provided for time division duplexing channels by means of the moment generating function. We present numerical results for the mean number of packets in the queue and consider the effect of the range of allowable bulk sizes. We show that there exists an optimal choice of this range that minimizes the mean number of data packets in the queue.

We describe an equivalence result for network capacity. Roughly, our main result is as follows. Given a network of noisy, independent, memoryless links, a collection of demands can be met on the given network if and only if it can be met on another network where each noisy link is replaced by a noiseless bit pipe with throughput equal to the noisy link capacity. This result was previously known only for multicast connections.

Emerging practical schemes indicate that algebraic mixing of different packets by means of random linear network coding can increase the throughput and robustness of streaming services over wireless networks. However, concerns with the security of streaming multimedia, in particular when only a subset of the users in the network is entitled to the highest quality, have uncovered the need for a network coding scheme capable of ensuring different levels of confidentiality under stringent complexity requirements. We consider schemes which exploit the algebraic structure of network coding to achieve the dual goal of hierarchical fidelity levels and efficient security. The key idea is to limit the encryption operations to the encoding vector, in combination with multi-resolution multimedia coding.

On behalf of the Technical Programme Committee, we are glad to welcome you to the 7th edition Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt).

We propose a linear network coding scheme to disseminate a finite number of data packets in arbitrary networks. The setup assumes a packet erasure channel, slotted time, and that nodes cannot transmit and receive information simultaneously. The dissemination process is completed when all terminals can decode the original data packets. We also assume a perfect knowledge of the information at each of the nodes, but not necessarily a perfect knowledge of the channel. A centralized controller decides which nodes should transmit, to what set of receiver nodes, and what information should be broadcasted. We show that the problem can be thought of as a scheduling problem, which is hard to solve. Thus, we consider the use of a greedy algorithm that only takes into account the current state of the system to make a decision. The proposed algorithm tries to maximize the impact on the network at each slot, i.e. maximize the number of nodes that will benefit from the coded packet sent by each active transmitter. We show that our scheme is considerably better, in terms of the number of slots to complete transmission, than schemes that choose the node with more information as the transmitter at every time slot.

To improve the utility of existing technologies based on Sanger sequencing, this paper examines the possibility of base-calling two superposed DNA sequences jointly. This approach allows a single electrophoresis experiment to process two sequences, using the same quantity of reagents and machine hours as for a single sequence. A practical heuristic is proposed to first estimate the peak parameters, then separate them into two sequences (major/minor) by passing messages on a factor graph. Base-calling on the major alone yields accuracy commensurate with single sequence approaches, and joint base-calling provides results for the minor which, while being of lesser quality, incurs no additional cost and can be ultimately used in the genome assembly process.

A new coding and queue management algorithm is proposed for communication networks that employ linear network coding. The algorithm has the feature that the encoding process is truly online, as opposed to a block-by-block approach. The setup assumes a packet erasure broadcast channel with stochastic arrivals and full feedback, but the proposed scheme is potentially applicable to more general lossy networks with link-by-link feedback. The algorithm guarantees that the physical queue size at the sender tracks the backlog in degrees of freedom (also called the virtual queue size). The new notion of a node ldquoseeingrdquo a packet is introduced. In terms of this idea, our algorithm may be viewed as a natural extension of ARQ schemes to coded networks. Our approach, known as the drop-when-seen algorithm, is compared with a baseline queuing approach called drop-when-decoded. It is shown that the expected queue size for our approach is O[(1)/(1-rho)] as opposed to Omega[(1)/(1-rho)2] for the baseline approach, where rho is the load factor.

We investigate a systematic construction of binary deterministic rateless codes (BDRCs). The codes are for networks with erasure channels. With a maximum distance separable (MDS) property, non-systematic BDRCs were first proposed in [1] with encoding complexity O(K), and decoding complexity is O(K2). Here K is the length of information bits. To reduce complexity, we study systematic-BDRCs (SBDRCs). For SBDRCs, the source first transmits m - 1 uncoded blocks, where m is the number of source blocks. Then, the source produces and transmits coded blocks in a rateless way. These coded blocks are produced using only cyclic-shift and XOR (exclusive or). The SBDRCs can use a large number of information blocks (potentially infinite m). On receiving any m distinct blocks (uncoded or coded), a sink can rebuild the source. The SBDRCs have encoding complexity O(∈K), and decoding complexity O(∈2K2), where ∈ is the source-to-sink block erasure probability.

We consider the problem of rate allocation in a fading Gaussian multiple-access channel with fixed transmission powers. The goal is to maximize a general concave utility function of the expected achieved rates of the users. There are different approaches to this problem in the literature. From an information theoretic point of view, rates are allocated only by using the channel state information. The queueing theory approach utilizes the global queue-length information for rate allocation to guarantee throughput optimality as well as maximizing a utility function of the rates. In this work, we make a connection between these two approaches by showing that the information theoretic capacity region of a multiple-access channel and its stability region are equivalent. Moreover, our numerical results show that a simple greedy policy which does not use the queue-length information can outperform queue-length based policies in terms of convergence rate and fairness.

This paper describes MIXIT, a system that improves the throughput of wireless mesh networks. MIXIT exploits a basic property of mesh networks: even when no node receives a packet correctly, any given bit is likely to be received by some node correctly. Instead of insisting on forwarding only correct packets, MIXIT routers use physical layer hints to make their best guess about which bits in a corrupted packet are likely to be correct and forward them to the destination. Even though this approach inevitably lets erroneous bits through, we find that it can achieve high throughput without compromising end-to-end reliability.

Transmitter knowledge of channel state has a great impact on wideband fading channel capacity. However, in the low SNR regime, power per dimension does not suffice to provide an accurate measurement of the channel over the entire spectrum. In the presence of feedback, we may collect information at the transmitter about some aspects of the channel quality over a certain portion of the spectrum. In this work, we investigate the effect of such information. We consider channel testing with a finite amount of energy over a block-fading channel in both time and frequency. We consider a transmission scheme in which the wideband channel is decomposed into many parallel narrowband subchannels, each used with a binary modulation scheme. The quality of each subchannel corresponds to the crossover probability of a binary symmetric channel. We use a multi-armed bandit approach to consider the relative costs and benefits of allotting energy for testing versus transmission, and for repeated testing a single subchannel versus testing different subchannels. We give both upper and lower bounds on the number of subchannels that should be probed for throughput maximization under the scheme we have chosen. Our bounds are in terms of available transmission energy, available bandwidth and fading characteristics of the channel. Moreover, in our numerical results, the two bounds are close.

The goal of this paper is two-fold. First, to establish a tractable model for the underwater acoustic channel useful for network optimization in terms of convexity. Second, to propose a network coding based lower bound for transmission power in underwater acoustic networks, and compare this bound to the performance of several network layer schemes. The underwater acoustic channel is characterized by a path loss that depends strongly on transmission distance and signal frequency. The exact relationship among power, transmission band, distance and capacity for the Gaussian noise scenario is a complicated one. We provide a closed-form approximate model for 1) transmission power and 2) optimal frequency band to use, as functions of distance and capacity. The model is obtained through numerical evaluation of analytical results that take into account physical models of acoustic propagation loss and ambient noise. Network coding is applied to determine a lower bound to transmission power for a multicast scenario, for a variety of multicast data rates and transmission distances of interest for practical systems, exploiting physical properties of the underwater acoustic channel. The results quantify the performance gap in transmission power between a variety of routing and network coding schemes and the network coding based lower bound. We illustrate results numerically for different network scenarios.

In an unreliable packet network setting, we study the performance gains of optimal transmission strategies in the presence and absence of coding capability at the transmitter, where performance is measured in delay and throughput. Although our results apply to a large class of coding strategies including maximum-distance separable (MDS) and Digital Fountain codes, we use random network codes in our discussions because these codes have a greater applicability for complex network topologies. To that end, after introducing a key setting in which performance analysis and comparison can be carried out, we provide closed-form as well as asymptotic expressions for the delay performance with and without network coding. We show that the network coding capability can lead to arbitrarily better delay performance as the system parameters scale when compared to traditional transmission strategies without coding. We further develop a joint scheduling and random-access scheme to extend our results to general wireless network topologies.

An information-theoretic approach for detecting Byzantine or adversarial modifications in networks employing random linear network coding is described. Each exogenous source packet is augmented with a flexible number of hash symbols that are obtained as a polynomial function of the data symbols. This approach depends only on the adversary not knowing the random coding coefficients of all other packets received by the sink nodes when designing its adversarial packets. We show how the detection probability varies with the overhead (ratio of hash to data symbols), coding field size, and the amount of information unknown to the adversary about the random code.

Network coding substantially increases network throughput. But since it involves mixing of information inside the network, a single corrupted packet generated by a malicious node can end up contaminating all the information reaching a destination, preventing decoding. This paper introduces distributed polynomial-time rate-optimal network codes that work in the presence of Byzantine nodes. We present algorithms that target adversaries with different attacking capabilities. When the adversary can eavesdrop on all links and jam links, our first algorithm achieves a rate of , where is the network capacity. In contrast, when the adversary has limited eavesdropping capabilities, we provide algorithms that achieve the higher rate of . Our algorithms attain the optimal rate given the strength of the adversary. They are information-theoretically secure. They operate in a distributed manner, assume no knowledge of the topology, and can be designed and implemented in polynomial time. Furthermore, only the source and destination need to be modified; nonmalicious nodes inside the network are oblivious to the presence of adversaries and implement a classical distributed network code. Finally, our algorithms work over wired and wireless networks.

Power efficiency is a capital issue in the study of mobile wireless nodes owing to constraints on their battery size and weight. In practice, especially for low-power nodes, it is often the case that the power consumed for non-transmission processes is not always negligible. In this paper, we consider the channels with a special form of overhead: a processing energy cost whenever a non-zero signal is transmitted. We show that under certain conditions, achieving the capacity of such channels requires intermittent, or `bursty', transmissions. Thus, an optimal sleeping schedule can be specified for wireless nodes to achieve the optimal power efficiency. We show that in the low SNR regime, there is a simple relation between the optimal burstiness and the overhead cost: one should use a fraction of the available degrees of freedom at an SNR level of radic2epsiv, where epsiv is the normalized overhead energy cost. We extend this result to use bursty Gaussian transmissions in multiple parallel channels with different noise levels. Our result can be intuitively interpreted as a 'glue pouring' process, generalizing the wellknown water pouring solution. We then use this approach to compute the achievable rate region of the multiple access channel with overhead cost.

We consider the distributed computation of a function of random sources with minimal communication. Specifically, given two discrete memoryless sources, X and Y, a receiver wishes to compute f(X, Y) based on (encoded) information sent from X and Y in a distributed manner. A special case, f(X, Y) = (X, Y), is the classical question of distributed source coding considered by Slepian and Wolf (1973). Orlitsky and Roche (2001) considered a somewhat restricted setup when Y is available as side information at the receiver. They characterized the minimal rate at which X needs to transmit data to the receiver as the conditional graph entropy of the characteristic graph of X based on f. In our recent work (2006), we further established that this minimal rate can be achieved by means of graph coloring and distributed source coding (e.g. Slepian-Wolf coding). This characterization allows for the separation between "function coding" and "correlation coding." In this paper, we consider a more general setup where X and Y are both encoded (separately). This is a significantly harder setup for which to give a single-letter characterization for the complete rate region. We find that under a certain condition on the support set of X and Y (called the zigzag condition), it is possible to characterize the rate region based on graph colorings at X and Y separately. That is, any achievable pair of rates can be realized by means of first coloring graphs at X and Y separately (function coding) and then using Slepian-Wolf coding for these colors (correlation coding). We also obtain a single-letter characterization of the minimal joint rate. Finally, we provide simulation results based on graph coloring to establish the rate gains on real sequences

We present a genetic algorithm which is distributed in two novel ways: along genotype and temporal axes. Our algorithm first distributes, for every member of the population, a subset of the genotype to each network node, rather thana subset of the population to each. This genotype distribution is shown to offer a significant gain in running time. Then, for efficient use of the computational resources in the network, our algorithm divides the candidate solutions intopipelined sets and thus the distribution is in the temporal domain, rather that in the spatial domain. This temporal distribution may lead to temporal inconsistency in selection and replacement, however our experiments yield better efficiency in terms of the time to convergence without incurring significant penalties.

In this work, we consider access network design for the Optical Flow Switching (OFS) transport architecture [1]-[3]. Our work addresses the all-optical physical layer of the data plane in the context of tree-based networks. We consider the advantages and disadvantages of passive and active components - including optical amplifiers - and ultimately integrate these building blocks in the most economically attractive fashion for the required number of users.

Network coding substantially increases network throughput. But since it involves mixing of information inside the network, a single corrupted packet generated by a malicious node can end up contaminating all the information reaching a destination, preventing decoding. This paper introducesthefirstdistributedpolynomial-timerate-optimalnetwork codes that work in the presence of Byzantine nodes. We present algorithms that target adversaries with different attacking capabilities. When the adversary can eavesdrop on all links and jam zOlinks , our first algorithm achieves a rate ofC- 2zO, where C is the network capacity. In contrast, when the adversary has limited snooping capabilities, we provide algorithms that achieve the higher rate ofC- zO. Our algorithms attain the optimal rate given the strength of the adversary. They are information-theoretically secure. They operate in a distributed manner, assume no knowledge of the topology, and can be designed and implemented in polynomial-time. Furthermore, only the source and destination need to be modified; non-malicious nodes inside the network are oblivious to the presence of adversaries and implement a classical distributed network code. Finally, our algorithms work over wired and wireless networks.

Abstract — We consider the problem of minimizing the resources used for network coding while achieving the desired throughput in a multicast scenario. Since this problem is NPhard, we seek a method for quickly finding sufficiently good solutions. To this end, we take evolutionary approaches based on a Genetic Algorithm. In this paper, we extend the evolutionary algorithm that we previously proposed in three perspectives. First, whereas the previous algorithm can be applied to only acyclic networks, we devise a modified evaluation method that works also with networks with cycles. Second, we introduce a new set of GA components that in our experiments outperforms the one used in the previous algorithm. Third, we present a new framework of the evolutionary approach, where fitness evaluation and population management are done in a decentralized manner with a limited amount of coordination. The new framework enables a network coding protocol where the resources used for coding are optimized in the setup phase as the proposed evolutionary algorithm being loaded and run at each node of the network. We demonstrate the effectiveness of our algorithms by carrying out simulations on a number of different sets of network topologies. I.

We consider the problem of serving multicast flows in a crossbar switch. We show that linear network coding across packets of a flow can sustain traffic patterns that cannot be served if network coding were not allowed. Thus, network coding leads to a larger rate region in a multicast crossbar switch. We demonstrate a traffic pattern which requires a switch speedup if coding is not allowed, whereas, with coding the speedup requirement is eliminated completely. In addition to throughput benefits, coding simplifies the characterization of the rate region. We give a graph-theoretic characterization of the rate region with fanout splitting and intra-flow coding, in terms of the stable set polytope of the "enhanced conflict graph" of the traffic pattern. Such a formulation is not known in the case of fanout splitting without coding. We show that computing the offline schedule (i.e. using prior knowledge of the flow arrival rates) can be reduced to certain graph coloring problems. Finally, we propose online algorithms (i.e. using only the current queue occupancy information) for multicast scheduling based on our graph-theoretic formulation. In particular, we show that a maximum weighted stable set algorithm stabilizes the queues for all rates within the rate region.

Recent research has shown that network coding can be used in content distribution systems to improve the speed of downloads and the robustness of the systems. However, such systems are very vulnerable to attacks by malicious nodes, and we need to have a signature scheme that allows nodes to check the validity of a packet without decoding. In this paper, we propose such a signature scheme for network coding. Our scheme makes use of the linearity property of the packets in a coded system, and allows nodes to check the integrity of the packets received easily. We show that the proposed scheme is secure, and its overhead is negligible for large files.

We consider the following rate distortion problem: given a source X and correlated, decoder side information Y, find the minimum encoding rate for X required to compute f(X,Y) at the decoder within distortion D. This is a generalization of the classical Wyner-Ziv setup and was resolved by Yamamoto (1982). However, this result involved an auxiliary random variable that lacks explicit meaning. To provide a more direct link between this variable and the function f, Orlitsky and Roche (2001) established the minimal rate required in the zero-distortion case as an extension of Korner's graph entropy. Recently, we (with Jaggi) showed that the zero-distortion rate can be achieved by minimum entropy graph coloring of an appropriate product graph. This leads to a modular architecture for functional source coding with a preprocessing "functional coding" scheme operating on top of a classical Slepian-Wolf source coding scheme. In this paper, we give a characterization of Yamamoto's rate distortion function in terms of a reconstruction function. This (non-single-letter) characterization is an extension of our previous results as well as Orlitsky and Roche's results. We obtain a modular scheme operating with Slepian-Wolf's scheme for the problem of functional rate distortion. Further, we give an achievable rate (with single-letter characterization) utilizing this scheme that intuitively extends our previous results.

Relaying is a fundamental building block of wireless networks. Sophisticated relaying strategies at the physical layer have been developed for a single flow, but multiple flows are typically handled by time sharing the channel between the flows at the network level. In this paper, time-sharing when forwarding two data streams at the relay is compared to joint relaying and network coding that allows the relay to combine data streams. Two commonly occurring blocks in wireless networks with both unicast and multicast traffic are considered. It is shown that joint relaying and network coding can achieve gains and even double the throughput for certain channel conditions.

We present a graph theoretic upper bound on speedup needed to achieve 100% throughput in a multicast switch using network coding. By bounding speedup, we show the equivalence between network coding and speedup in multicast switches - i.e. network coding, which is usually implemented using software, can in many cases substitute speedup, which is often achieved by adding extra switch fabrics. This bound is based on an approach to network coding problems called the "enhanced conflict graph". We show that the "imperfection ratio" of the enhanced conflict graph gives an upper bound on speedup. In particular, we apply this result to K times N switches with traffic patterns consisting of unicasts and broadcasts only to obtain an upper bound of min(2K-1/K, 2N/N+1).

We consider the level of information security provided by random linear network coding in network scenarios in which all nodes comply with the communication protocols yet are assumed to be potential eavesdroppers (i.e. "nice but curious"). For this setup, which differs from wiretapping scenarios considered previously, we develop a natural algebraic security criterion, and prove several of its key properties. A preliminary analysis of the impact of network topology on the overall network coding security, in particular for complete directed acyclic graphs, is also included.

We consider the problem of applying network coding in wireless networks with random medium access. To optimize the network coding subgraph and the transmission attempt probabilities jointly is a tractable problem only for rather small networks. Therefore, we suggest a suboptimal, yet practical and decentralized algorithm to combine network coding with random access. We illustrate the performance gains of our approach with simulations.

We investigate a deterministic binary coding approach for combination networks. In the literature, network coding schemes with large alphabet sizes achieve the min-cut capacity. Here, we propose an approach using binary (GF(2)) sequences instead of going to a large alphabet size. In the encoding process, only cyclic-shifting and XOR operations are used. The encoding complexity is linear with the length of information bits. The transfer matrix is sparse, and the decoder can perfectly decode source information by a sparse- matrix processing approach. Our approach does not use any redundant bits, and achieves the min-cut capacity. Further, the code blocks can be produced in a rateless way. The sink can decode source information from any subset of code blocks, if the number of received distinct blocks is the same as that of the information blocks. Thus, we use the code for general networks with erasure channels. The proposed binary rateless codes have quite small overheads and can work with a small number of blocks. With high probability, the codes behave as maximum distance separable (MDS) codes.

We propose a new queueing mechanism for coded networks with stochastic arrivals and/or lossy links. In this context, earlier work introduced the notion of "virtual queues" which represent the backlog in degrees of freedom. For instance, the work by Ho and Viswanathan defined the achievable rate region for which the virtual queue size is stabilized, using intra-session coding. The queueing scheme that we propose here forms a natural bridge between the virtual queue size and the physical queue size, and thus extends their result to the stability of the physical queues as well. Specifically, we show that the amount of memory used at the transmit buffer in our scheme is upper bounded by the total backlog in the number of linearly independent degrees of freedom. Moreover, our scheme gives an online algorithm for queue update and coding, in the sense that the coding does not happen block by block, but in a streaming manner. The main idea in our scheme is to ensure that the information stored at the sender excludes any knowledge that is common to all receivers. This requires the transmitting node to track the states of knowledge of its receivers. Therefore, if the links are lossy, some form of feedback may be necessary.

The Birkhoff-von Neumann (BVN) strategy for single-stage input-queued crossbar switches does not support multicast, as it considers only permutation-based switch configurations. This paper extends the BVN strategy to multicast switching, where an input can simultaneously transmit to multiple outputs. Knowledge of the average rates of flows is used to compute an offline schedule. We begin by considering a system in which the fanout of each flow is split in a predecided manner. We call this static splitting (as opposed to dynamic splitting where no such constraint is imposed), and we study the rate region of the switch under this restriction. We provide a graph-theoretic formulation of the rate region.

We compare three optical transport network architectures - optical packet switching (OPS), optical flow switching (OFS), and optical burst switching (OBS) - based on a notion of network capacity as the set of exogenous traffic rates that can be stably supported by a network under its operational constraints. We characterize the capacity regions of the transport architectures, and show that the capacity region of OPS dominates that of OFS, and that the capacity region of OFS dominates that of OBS. We then apply these results to two important network topologies - bidirectional rings and Moore graphs - under uniform all-to-all traffic. Motivated by the incommensurate complexity/cost of comparable transport architectures, we also investigate the dependence of the relative capacity performance of the switching architectures on the number of switch ports per fiber at core nodes.

We derive the capacity of time-varying channels with memory that have causal channel side information (CSI) at the sender and receiver. We obtain capacity of block-memoryless and asymptotically block-memoryless channels with block-memoryless or weakly decorrelating side information. Our coding theorems rely on causal generation of the codewords relative to the causal transmitter CSI. The CSI need not be perfect, and we consider the case where the transmitter and receiver have the same causal CSI as well as the case where the transmitter CSI is a deterministic function of the receiver CSI. For block-memoryless and asymptotically block-memoryless channels, our coding strategy averages mutual information density over multiple transmission blocks to achieve the maximum average mutual information. We apply the coding theorem associated with the block-memoryless channel to determine the capacity and optimal input distribution of intersymbol interference (ISI) time-varying channels with causal perfect CSI about the time-varying channel. The capacity of this channel cannot be found through traditional decomposition methods

We consider a multiple-input multiple-output (MIMO) wideband Rayleigh block-fading channel where the channel state is unknown to both the transmitter and the receiver and there is only an average power constraint on the input. We compute the capacity and analyze its dependence on coherence length, number of antennas and receive signal-to-noise ratio (SNR) per degree of freedom. We establish conditions on the coherence length and number of antennas for the noncoherent channel to have a “near-coherent” performance in the wideband regime. We also propose a signaling scheme that is near-capacity achieving in this regime. We compute the error probability for this wideband noncoherent MIMO channel and study its dependence on SNR, number of transmit and receive antennas and coherence length. We show that error probability decays inversely with coherence length and exponentially with the product of the number of transmit and receive antennas. Moreover, channel outage dominates error probability in the wideband regime. We also show that the critical as well as cutoff rates are much smaller than channel capacity in this regime.

Channel capacity in the limit of vanishing signal-to-noise ratio (SNR) per degree of freedom is known to be linear in SNR for fading and nonfading channels, regardless of channel state information at the receiver (CSIR). It has recently been shown that the significant engineering difference between the coherent and the noncoherent fading channels, including the requirement of peaky signaling and the resulting spectral efficiency, is determined by how the capacity limit is approached as SNR tends to zero, or in other words, the sublinear term in the capacity expression. In this paper, we show that this sublinear term is determined by the channel coherence level, which we define to quantify the relation between the SNR and the channel coherence time. This allows us to trace a continuum between the case with perfect CSIR and the case with no CSIR at all. Using this approach, we also evaluate the performance of suboptimal training schemes.

In this work, we evaluate an attractive candidate for optical network data transport: optical flow switching (OFS). We describe the operation and implementation of the architecture, characterize its capacity region and capacity-cost tradeoff, and compare it to other prominent optical network architectures.

We discuss two approaches for decoding at arbitrary rates in the Slepian-Wolf problem - time sharing and source splitting - both of which rely on constituent vertex decoders. We consider the error exponents for both schemes and conclude that source-splitting is more robust at coding at arbitrary rates, as the error exponent for time-sharing degrades significantly at rates near vertices. As a by-product of our analysis, we exhibit an interesting connection between minimum mean-squared error estimation and error exponents

In this work, we conduct a throughput-cost study of several optical network architectures: optical flow switching (OFS), tell-and-go (TaG), electronic packet switching (EPS), and generalized multiprotocol label switching (GMPLS). The simple, multi-tiered optical network that we consider comprises two groups of users, each in a distinct metropolitan-area network (MAN), which wish to communicate over a wide-area network (WAN). Our network cost model focuses on initial capital expenditure: transceiver, switching, routing, and amplification costs. Our results indicate that: OFS is the most scalable architecture of all, in that it is most cost-efficient when the average user data rate is high and the number of users in the network is large; EPS is most sensible when the product of the number of users and the average user data rate is low; the GMPLS architecture, which is conceptually intermediate to EPS and OFS, is optimal when the product of the number of users and the average user data rate is moderate; and, finally, there does not exist an optimal regime for TaG.

We compare three optical transport network architectures—optical packet switching (OPS), optical flow switching (OFS), and optical burst switching (OBS)—based on a notion of network capacity as the set of exogenous traffic rates that can be stably supported by a network under its operational constraints. We characterize the capacity regions of the transport architectures, and show that the capacity region of OPS dominates that of OFS, and that the capacity region of OFS dominates that of OBS. We then apply these results to two important network topologies—bidirectional rings and Moore graphs—under uniform all-to-all traffic. Motivated by the incommensurate complexity/cost of comparable transport architectures, we also investigate the dependence of the relative capacity performance of the switching architectures on the number of switch ports per fiber at core nodes.

Many of the multimedia applications such as video broadcasting and teleconferencing require the network to support dynamic multicast sessions when the membership of the multicast group changes over time. In this paper, we study this problem in the context of coded networks. While trying to minimize the cost of the multicast, we also want to minimize the disturbances to existing users when the multicast graph changes. To characterize disturbances to users, we define two types of rearrangements, link rearrangements and code rearrangements. We present four algorithms to solve the non-rearrangeable and rearrangeable versions of the dynamic multicast problem. Simulation results show that the ∝-scaled algorithm we proposed can keep the cost of the multicast close to that of the optimal solution when the multicast subgraph evolves, and, at the same time, causes very few rearrangements during the process.

We consider the problem of jamming in non-coherent wideband fading channels. While the problem is well understood for coherent channels, the results for the coherent case do not generalize in the non-coherent regime. We show that energy-limited jammers do not affect capacity in the wideband regime. We also propose a training based transmission scheme that is able to achieve the wideband limit in the presence of a jammer

We consider a multiple-input, multiple-output (MIMO) wideband Rayleigh block fading channel where the channel state is unknown to both the transmitter and the receiver and there is only an average power constraint on the input. We compute the error probability and study its dependence on receive signal-to-noise ratio (SNR), number of transmit and receive antennas and coherence length. We show that error probability decays inversely with coherence length and exponentially with the product of the number of transmit and receive antennas. Moreover, channel outage dominates error probability in the wideband regime. We also show that the critical as well as cut-off rates are much smaller than channel capacity in this regime

The concept of a fiber aided wireless network architecture (FAWNA) is introduced in [Ray et al., Allerton Conference 2005], which allows high-speed mobile connectivity by leveraging the speed of optical networks. In this paper, we consider a single-input, multiple-output (SIMO) FAWNA, which consists of a SIMO wireless channel and an optical fiber channel, connected through wireless-optical interfaces. We propose a scheme where the received wireless signal at each interface is quantized and sent over the fiber. Though our architecture is similar to that of the classical CEO problem, our problem is different from it. We show that the capacity of our scheme approaches the capacity of the architecture, exponentially with fiber capacity. We also show that for a given fiber capacity, there is an optimal operating wireless bandwidth and an optimal number of wireless-optical interfaces. The wireless-optical interfaces of our scheme have low complexity and do not require knowledge of the transmitter code book. They are also extendable to FAWNAs with large number of transmitters and interfaces and, offer adaptability to variable rates, changing channel conditions and node positions

In this paper we consider the application of network coding to a multiple unicast setup. We present two suboptimal, yet practical code construction techniques. One consists of a linear program and the other of an integer program with fewer variables and constraints. We discuss the performance of the proposed techniques as well as their complexity

This paper proposes COPE, a new architecture for wireless mesh networks. In addition to forwarding packets, routers mix (i.e., code) packets from different sources to increase the information content of each transmission. We show that intelligently mixing packets increases network throughput. Our design is rooted in the theory of network coding. Prior work on network coding is mainly theoretical and focuses on multicast traffic. This paper aims to bridge theory with practice; it addresses the common case of unicast traffic, dynamic and potentially bursty flows, and practical issues facing the integration of network coding in the current network stack. We evaluate our design on a 20-node wireless network, and discuss the results of the first testbed deployment of wireless network coding. The results show that COPE largely increases network throughput. The gains vary from a few percent to several folds depending on the traffic pattern, congestion level, and transport protocol.

This paper concerns error exponents and the structure of input distributions maximizing the random coding exponent for a stochastic channel model. The following conclusions are obtained under general assumptions on the channel statistics. 1) The optimal distribution has a finite number of mass points, or in the case of a complex channel, the amplitude has finite support. 2) A new class of algorithms is introduced based on the cutting-plane method to construct an optimal input distribution. The algorithm constructs a sequence of discrete distributions, along with upper and lower bounds on the random coding exponent at each iteration. 3) In some numerical example considered, the resulting code significantly outperforms traditional signal constellation schemes such as quadrature amplitude modulation and phase-shift keying for all rates below the capacity.

This paper discusses the Slepian-Wolf problem of distributed near-lossless compression of correlated sources. We introduce practical new tools for communicating at all rates in the achievable region. The technique employs a simple "source-splitting" strategy that does not require common sources of randomness at the encoders and decoders. This approach allows for pipelined encoding and decoding so that the system operates with the complexity of a single user encoder and decoder. Moreover, when this splitting approach is used in conjunction with iterative decoding methods, it produces a significant simplification of the decoding process. We demonstrate this approach for synthetically generated data. Finally, we consider the Slepian-Wolf problem when linear codes are used as syndrome-formers and consider a linear programming relaxation to maximum-likelihood (ML) sequence decoding. We note that the fractional vertices of the relaxed polytope compete with the optimal solution in a manner analogous to that observed when the "min-sum" iterative decoding algorithm is applied. This relaxation exhibits the ML-certificate property: if an integral solution is found, it is the ML solution. For symmetric binary joint distributions, we show that selecting easily constructable "expander"-style low-density parity check codes (LDPCs) as syndrome-formers admits a positive error exponent and therefore provably good performance

The problem of simultaneously disseminating k messages in a large network of n nodes, in a decentralized and distributed manner, where nodes only have knowledge about their own contents, is studied. In every discrete time-step, each node selects a communication partner randomly, uniformly among all nodes and only one message can be transmitted. The goal is to disseminate rapidly, with high probability, all messages to all nodes. It is shown that a random linear coding (RLC) based protocol disseminates all messages to all nodes in time ck+/spl Oscr/(/spl radic/kln(k)ln(n)), where c<3.46 using pull-based dissemination and c<5.96 using push-based dissemination. Simulations suggest that c<2 might be a tighter bound. Thus, if k/spl Gt/(ln(n))/sup 3/, the time for simultaneous dissemination RLC is asymptotically at most ck, versus the /spl Omega/(klog/sub 2/(n)) time of sequential dissemination. Furthermore, when k/spl Gt/(ln(n))/sup 3/, the dissemination time is order optimal. When k/spl Lt/(ln(n))/sup 2/, RLC reduces dissemination time by a factor of /spl Omega/(/spl radic/k/lnk) over sequential dissemination. The overhead of the RLC protocol is negligible for messages of reasonable size. A store-and-forward mechanism without coding is also considered. It is shown that this approach performs no better than a sequential approach when k=/spl prop/n. Owing to the distributed nature of the system, the proof requires analysis of an appropriate time-varying Bernoulli process.

We present a distributed random linear network coding approach for transmission and compression of information in general multisource multicast networks. Network nodes independently and randomly select linear mappings from inputs onto output links over some field. We show that this achieves capacity with probability exponentially approaching 1 with the code length. We also demonstrate that random linear coding performs compression when necessary in a network, generalizing error exponents for linear Slepian-Wolf coding in a natural way. Benefits of this approach are decentralized operation and robustness to network changes or link failures. We show that this approach can take advantage of redundant network capacity for improved success probability and robustness. We illustrate some potential advantages of random linear network coding over routing in two examples of practical scenarios: distributed network operation and networks with dynamically varying connections. Our derivation of these results also yields a new bound on required field size for centralized network coding on general multicast networks

We consider the problem of establishing minimum-cost multicast connections over coded packet networks, i.e., packet networks where the contents of outgoing packets are arbitrary, causal functions of the contents of received packets. We consider both wireline and wireless packet networks as well as both static multicast (where membership of the multicast group remains constant for the duration of the connection) and dynamic multicast (where membership of the multicast group changes in time, with nodes joining and leaving the group). For static multicast, we reduce the problem to a polynomial-time solvable optimization problem, and we present decentralized algorithms for solving it. These algorithms, when coupled with existing decentralized schemes for constructing network codes, yield a fully decentralized approach for achieving minimum-cost multicast. By contrast, establishing minimum-cost static multicast connections over routed packet networks is a very difficult problem even using centralized computation, except in the special cases of unicast and broadcast connections. For dynamic multicast, we reduce the problem to a dynamic programming problem and apply the theory of dynamic programming to suggest how it may be solved.

We investigate the following issue: if fast fades are Markovian and known at the receiver, while the transmitter has only a coarse quantization of the fading process, what capacity penalty comes from having the transmitter act on the current coarse quantization alone? For time-varying channels which experience rapid time variations, sender and receiver typically have asymmetric channel side information. To avoid the expense of providing, through feedback, detailed channel side information to the sender, the receiver offers the sender only a coarse, generally time-averaged, representation of the state of the channel, which we term slow variations. Thus, the receiver tracks the fast variations of the channel (and the slow ones perforce) while the sender receives feedback only about the slow variations. While the fast variations (micro-states) remain Markovian, the slow variations (macro-states) are not. We compute an approximate channel capacity in the following sense: each rate smaller than the "approximate" capacity, computed using results by Caire and Shamai, can be achieved for sufficiently large separation between the time scales for the slow and fast fades. The difference between the true capacity and the approximate capacity is O(/spl epsi/log/sup 2/(/spl epsi/)log(-log(/spl epsi/))), where /spl epsi/ is the ratio between the speed of variation of the channel in the macro- and micro-states. The approximate capacity is computed by power allocation between the slowly varying states using appropriate water filling.

Minimum-entropy decoding is a universal decoding algorithm used in decoding block compression of discrete memoryless sources as well as block transmission of information across discrete memoryless channels. Extensions can also be applied for multiterminal decoding problems, such as the Slepian-Wolf source coding problem. The 'method of types' has been used to show that there exist linear codes for which minimum-entropy decoders achieve the same error exponent as maximum-likelihood decoders. Since minimum-entropy decoding is NP-hard in general, minimum-entropy decoders have existed primarily in the theory literature. We introduce practical approximation algorithms for minimum-entropy decoding. Our approach, which relies on ideas from linear programming, exploits two key observations. First, the 'method of types' shows that that the number of distinct types grows polynomially in n. Second, recent results in the optimization literature have illustrated polytope projection algorithms with complexity that is a function of the number of vertices of the projected polytope. Combining these two ideas, we leverage recent results on linear programming relaxations for error correcting codes to construct polynomial complexity algorithms for this setting. In the binary case, we explicitly demonstrate linear code constructions that admit provably good performance.

We address practical coding schemes for the Slepian-Wolf distributed data compression problem. We consider three approaches. First, we apply a source-splitting technique to code at any rate in the achievable rate region with low complexity. It is well known that vertices in the achievable rate region can be implemented with low complexity. The source-splitting approach transforms any achievable rate point into a vertex in a higher-dimensional Slepian-Wolf achievable rate region. Secondly, we consider linear programming relaxations of the maximum-likelihood decoding problem. We give a polynomial complexity construction for linear codes with a certificate property. Lastly, when the decoder does not have any knowledge of the source statistics, we present practical schemes for universal decoding, a topic heretofore confined primarily to theory.

We present decentralized algorithms that compute minimum-cost subgraphs for establishing multicast connections in networks that use coding. These algorithms, coupled with existing decentralized schemes for constructing network codes, constitute a fully decentralized approach for achieving minimum-cost multicast. Our approach is in sharp contrast to the prevailing approach based on approximation algorithms for the directed Steiner tree problem, which is suboptimal and generally assumes centralized computation with full network knowledge. We also give extensions beyond the basic problem of fixed-rate multicast in networks with directed point-to-point links, and consider the case of elastic rate demand as well as the problem of minimum-energy multicast in wireless networks.

We show that the deterministic broadcast channel, where a single source transmits to M receivers across a deterministic mechanism, may be reduced, via a rate-splitting transformation, to another (2M - 1)-receiver deterministic broadcast channel problem where a successive encoding approach suffices. Analogous to rate-splitting for the multiple access channel and source-splitting for the Slepian-Wolf problem, all achievable rates (including non-vertices) apply. This amounts to significant complexity reduction at the encoder

We study the gains to be had by using random linear coding (RLC) for simultaneously disseminating k distinct messages in a network of n nodes in a decentralized and distributed manner for arbitrary k and n. The goal is to rapidly disseminate all the messages among all the nodes. Any node can communicate with any of the other nodes but only one at a time, nodes only have knowledge about their own contents, and the bandwidth for every transmission between two nodes is limited (does not scale with k or n). An efficient and well-studied protocol for message dissemination in such a framework is randomized gossip based message dissemination. The problem has been studied extensively without using any coding for message dissemination. We show using analysis and simulation that, in the regime k ges (ln(n))3, RLC based dissemination reduces the dissemination time (the time-steps to disseminate all the messages among all the nodes) by a factor of otimes(ln(n)) as compared to disseminating the messages sequentially (i.e., one after the other) as implicit in most non-coding based technique. In the regime k les (ln(n))2, the dissemination time with RLC goes down by a factor of Omega(radick / ln k). More precisely, our results indicate that a RLC based protocol disseminates all the messages among all the nodes in time ck + O(radick ln(k)(ln(n)) for a suitable constant c > 0. Analytical results show that, c < 3.46 using pull based dissemination, and c < 5.96 using push based dissemination, but reported simulations suggest c < 2 might be a tighter bound

Network coding is a method of data transmission across a network which involves coding at intermediate nodes. Network coding is particularly attractive for multicast. Building on the work done on random linear network codes, we develop a constrained, simplified code construction suitable for multicast in wireless networks. We analyze bounds on sufficient code size via an algebraic framework for network coding. We also present simulation results that compare unconstrained random network codes with our code construction. Issues unique to the simplified code are explored and a relaxation of the code to improve code performance is discussed

In "On Coding for Reliable Communication over Packet Networks" (Lun, Medard, and Effros, Proc. 42nd Annu. Allerton Conf. Communication, Control, and Computing, 2004), a capacity-achieving coding scheme for unicast or multicast over lossy wireline or wireless packet networks is presented. We extend that paper's results in two ways: First, we extend the network model to allow packets received on a link to arrive according to any process with an average rate, as opposed to the assumption of Poisson traffic with i.i.d. losses that was previously made. Second, in the case of Poisson traffic with i.i.d. losses, we derive error exponents that quantify the rate at which the probability of error decays with coding delay

It is known that, when using a multi-tone FSK scheme in a wideband fading channel to achieve the wideband capacity limit, the codeword probability of error decays very slowly with bandwidth. In this paper, we consider a modified multi-tone FSK scheme which employs a feedback link. We show that, a small amount of feedback improves the error performance significantly

We consider a multiple-input, multiple-output (MIMO) wideband Rayleigh block fading channel, where the channel state is unknown to both the transmitter and the receiver. With only an average power constraint, we compute the capacity of this channel and consider its interaction with the coherence length, number of transmit and receive antennas and receive signal-to-noise ratio (SNR) per degree of freedom. We establish how large the coherence length has to be in order for the non-coherent channel to have a "near coherent" performance in the wideband regime. More specifically, we show that if the coherence length of the channel is above a certain SNR (bandwidth) dependent threshold, the non-coherent and coherent capacities are the same in the large bandwidth regime. We also propose a signaling scheme that is near-optimal in the wideband regime

In this paper we propose an information theoretic framework for studying coding and throughput optimization for multi-layered packet transmission systems. Our approach assumes that the system is divided into two separate layers: One code word forms a packet at the physical layer and the code at the network layer spans over these packets. At the receiver, the network layer assumes that the decoded packets arriving from the physical layer either have no errors or are marked as deleted. Thus, albeit the packet loss may be caused, for example, by decoding error, congestion or channel conditions, the network layer treats all decoding errors as erasures regardless of the cause. This allows us to view the system at the network layer as transmission over memoryless erasure channel. We study the throughput optimization and code design across the layers under a total code length constraint while taking also into account the network layer imperfections in the transmission. We use random coding error exponents to achieve results that do not depend on specific coding scheme used. The proposed scheme provides also means for investigating important physical layer phenomena, such as, channel model and lower layer error correction coding in the packet erasure models. Our approach extends to fading channels and networks of multiple nodes and by viewing the two layers of coding as a concatenated coding scheme, a comparison between layer-by-layer and joint cross-layer rate optimization can be made, as outlined in this paper

We motivate the consideration of deterministic broadcast channel coding as an interference management technique in wireless scenarios. We address practical coding strategies for such channels and discuss two approaches. The first relies upon enumerative source coding and can be applied for any deterministic broadcast channel problem as the first step in pipelined encoding for vertex rates. The second approach addresses a wireless interference management scenario and is a complete, practical, capacity-achieving strategy that dualizes the Luby transform code construction and encoding/decoding algorithms. This results in the first practical, nontrivial, capacity achieving code construction for the deterministic broadcast channel.

A common problem in optical networking is that the large quantity of raw bandwidth available in such networks is often difficult to access. We show that time-division multiplexing (TDM) can be used to operate bus and ring architectures in a manner akin to a switch. Doing so substantially reduces the amount of hardware [particularly, add-drop multiplexers (ADMs)] needed to utilize fully the available bandwidth in a range of optical networks. We show that a significant fraction (and in some cases all) of the bandwidth available to the system can be utilized even if each node in the system has only a single ADM. Our approach is probabilistic in nature, using generalizations of the Birkhoff-von Neumann statistical multiplexing approaches that have been successful in switching theory. Our techniques rely on decompositions of fractional matchings (for architectures without erasures) and fractional interval graph colorings (for architectures with erasures) into integral matchings and colorings.

In the wideband limit, certain types of "flash" signaling, such as flash frequency-shift keying (FSK), achieve the capacity of multipath fading channels. It is not clear, however, whether these asymptotic results translate into insights for practical fading channels in the finite-bandwidth, power-limited regime. It is known that, for flash FSK, the size of the input alphabet grows slowly with increasing bandwidth, leading to very high-peak power per tone. Thus, for flash FSK, the codeword probability of error decays very slowly with bandwidth and feasible rates approach the wideband capacity limit extremely slowly. Without contradicting the above results, our results in this paper point to a more optimistic outlook, from the point of view of error exponents and achievable rates, for the applicability of flash techniques in practical scenarios. We consider multitone FSK (MFSK), which has the same asymptotic capacity-achieving property as flash FSK in the wideband limit, but allows a larger input alphabet size with the same bandwidth. First, we show, using an error exponent approach, that multitone FSK allows lower peak power per tone than flash FSK. Next, we present the capacity of single-tone and two-tone FSK schemes with hard-decision detection at finite bandwidths. For typical channel parameters, the capacities are close to the wideband capacity limit.

Pilot symbol assisted modulation (PSAM) is a standard approach for transceiver design for time-varying channels, with channel estimates obtained from pilot symbols being employed for coherent demodulation of the data symbols. In this paper, we show that PSAM schemes can be improved by adapting the coded modulation strategy at the sender to the quality of the channel measurement at the receiver, without requiring any channel feedback from the receiver. We consider performance in terms of achievable rate for binary signaling schemes. The transmitter employs interleaved codes, with data symbols coded according to their distance from the nearest pilot symbols. Symbols far away from pilot symbols encounter poorer channel measurements at the receiver and are therefore coded with lower rate codes, while symbols close to pilot symbols benefit from recent channel measurements and are coded with higher rate codes. The performance benefits from this approach are quantified in the context of binary signaling over time-varying Rayleigh fading channels described by a Gauss-Markov model. The spacing of the pilot symbols is optimized to maximize the mutual information between input and output in this setting. Causal and noncausal channel estimators of varying complexity and delay are considered. It is shown that, by appropriate optimization for the spacing between consecutive pilot symbols, the adaptive coding techniques proposed can improve achievable rate, without any feedback from the receiver to the sender. Moreover, channel estimation based on the two closest pilot symbols is generally close to optimal.

We present an information-theoretic framework for network management for recovery from nonergodic link failures. Building on recent work in the field of network coding, we describe the input-output relations of network nodes in terms of network codes. This very general concept of network behavior as a code provides a way to quantify essential management information as that needed to switch among different codes (behaviors) for different failure scenarios. We compare two types of recovery schemes, receiver-based and network-wide, and consider two formulations for quantifying network management. The first is a centralized formulation where network behavior is described by an overall code determining the behavior of every node, and the management requirement is taken as the logarithm of the number of such codes that the network may switch among. For this formulation, we give bounds, many of which are tight, on management requirements for various network connection problems in terms of basic parameters such as the number of source processes and the number of links in a minimum source-receiver cut. Our results include a lower bound for arbitrary connections and an upper bound for multitransmitter multicast connections, for linear receiver-based and network-wide recovery from all single link failures. The second is a node-based formulation where the management requirement is taken as the sum over all nodes of the logarithm of the number of different behaviors for each node. We show that the minimum node-based requirement for failures of links adjacent to a single receiver is achieved with receiver-based schemes.

We introduce three new innovations for compression using LDPCs for the Slepian-Wolf problem. The first is a general iterative Slepian-Wolf decoding algorithm that incorporates the graphical structure of all the encoders and operates in a 'turbo-like' fashion. The second innovation introduces source-splitting to enable low-complexity pipelined implementations of Slepian-Wolf decoding at rates besides corner points of the Slepian-Wolf region. This innovation can also be applied to single-source block coding for reduced decoder complexity. The third approach is a linear programming relaxation to maximum-likelihood sequence decoding that exhibits the ML-certificate property. This can be used for decoding a single binary block-compressed source as well as decoding at vertex points for the binary Slepian-Wolf problem. All three of these innovations were motivated by recent analogous results in the channel coding domain.

In very large networks with heavy traffic, congestion control plays an important role in network resource management. One approach to this is the active queue management (AQM) algorithms. Many AQM algorithms have been proposed and analyzed but they mainly focus on single queued links. Recognizing the fact that input queued switches are limited in throughput and output queued switches require a large speedup factor, we direct our attention to combined input and output queued (CIOQ) switches. We propose a simple modification to the RED AQM algorithm in order to account for the presence of both input and output queues in the switch. Specifically we use the weighted sum of input and output queue lengths as the congestion measure instead of just the output queue length. Simulations show that with such a simple modification, the average backlog in the switch is significantly reduced in the low speedup region as compared to RED without this modification. Unlike the traditional dynamic of having the loss rate grow with the length of the queue, simulations show that for a loss rate in the modified RED slightly larger than that in RED, the output queue length in modified RED is tremendously reduced. The weighting factor used in the computation of the congestion measure provides a means to balance the reduction in the average backlog on the one hand, and the increase in the loss rate on the other hand. Finally, simulations show that the improvement gained in terms of the queue length does not compromise in any way the utilization of the switch as compared to RED and Droptail.

We derive, for a binary antipodal input signal, the optimal uncoded regenerator function when the channels at the ingress and at the egress of the regenerator are degraded by AWGN. We show that the optimal function is a Lambert W function parametrized on the energies of the noises and the input. For comparison, we derive the performance of systems in which the regenerator uses a hard limiter or an amplifier.

In communication over time-varying Rayleigh fading channels, adaptive coded modulation for pilot symbol assisted modulation (PSAM) without feedback has been shown to yield significant benefits in terms of achievable rates (M. Medard et al., 2000). This technique adapts transmission rate at the sender to the quality of the channel estimate at the receiver but keeps the mean power constant throughout. In this paper, we show that this adaptive PSAM scheme can be further improved if power and rate are jointly adapted to the quality of the measurement at the receiver. We study the optimal power distribution scheme and find it to apply the following principle: more power is allocated to symbols corresponding to better estimates at the receiver, while maintaining the average energy constraint satisfied within a period. We find that this simple scheme is optimal and performs better than adapting to channel quality using schemes akin to 'water filling'. Our model is a Rayleigh fading channel where time-variance is described by a Gauss-Markov model (M. Medard, 2000). The transmitter periodically sends pilot tones to measure the channel at the receiver. We interleave different codes, while maintaining the power constant over a codebook, and the average power over codebooks satisfying the constraint. Performance is quantified in terms of achievable rates. Our scheme does not require any real time computation or adaptation at the transmitter, and so comes at no extra cost with respect to (M. Meadard et al., 2000). When considering causal and non causal estimation strategies at the receiver, considerable improvement was attained without any added complexity.

We consider the issue of protection in very large networks displaying randomness in topology. We employ random graph models to describe such networks, and obtain probabilistic bounds on several parameters related to reliability. In particular, we take the case of random regular networks for simplicity and consider the length of primary and backup paths in terms of the number of hops. First, for a randomly picked pair of nodes, we derive a lower bound on the average distance between the pair and discuss the tightness of the bound. In addition, noting that primary and protection paths form cycles, we obtain a lower bound on the average length of the shortest cycle around the pair. Finally, we show that the protected connections of a given maximum finite length are rare. We then generalize our network model so that different degrees are allowed according to some arbitrary distribution, and show that the second moment of degree over the first moment is an important shorthand for behavior of a network. Notably, we show that most of the results in regular networks carry over with minor modifications, which significantly broadens the scope of networks to which our approach applies. We present as an example the case of networks with a power-law degree distribution.

In this paper, we consider the design of a physical network topology that meets a high level of reliability using unreliable network elements. We are motivated by the use of networks, and in particular, all-optical networks, for high-reliability applications which involve unusual and catastrophic stresses. Our network model is one in which nodes are invulnerable and links are subject to failure, and we consider both statistically independent and dependent link failures. Our reliability metrics are the all-terminal connectedness measure and the less commonly considered two-terminal connectedness measure. We compare in the low and high stress regimes, via analytical approximations and simulations, common commercial architectures designed for all-terminal reliability when links are very reliable with alternative architectures which are mindful of both of our reliability metrics and regimes of stress. Furthermore, we show that for independent link failures network design should be optimized with respect to reliability under high stress, as reliability under low stress is less sensitive to graph structure; and that under high stress, very high node degrees are required to achieve moderate reliability performance. Finally, in our discussion of correlated failure models we show the danger in relying on an independent failure model and the need for the network architect to minimize component failure dependencies.

It is shown that achieving an arbitrary rate-point in the achievable region of the M-source Slepian-Wolf [1] problem may be reduced via a practical source-splitting transformation to achieving a corner point in a 2M - 1 source Slepian-Wolf problem. Moreover, each source must be split at most once. This approach extends the ideas introduced in [2] to a practical setting: it does not require common randomness shared between splitters and the decoders, the cardinality of each source split is strictly smaller than the original, and practical iterative decoding methods can achieve rates near the theoretical bound.

Distributed randomized network coding, a robust approach to multicasting in distributed network settings, can be extended to provide Byzantine modification detection without the use of cryptographic functions is presented in this paper.

We consider the optimization of the random coding error exponent of a class of memoryless channels where the input is subject to a peak and average-power constraints. The capacity-achieving input is shown to be typically discrete and an algorithm is developed for computing these optimal distributions. As one application, we propose a new signal constellation design which out-performs QAM and PSK for certain channels.

This paper shows that, for a particular class of channels that we believe applies to many physical problems of interest, the utility of feedback, insofar as channel capacity is concerned, is simply for allowing the transmitter to perform power control. This class of channels, which assumes noiseless feedback but allows for the feedback to be of arbitrary rate, includes channels that model slow, flat fading channels with variable input power. Thus our result gives some guidance on the design of effective transmission schemes for slow, flat fading channels with feedback.

The effect of channel coherence on the capacity and energy efficiency of noncoherent fading channels at low SNR is studied. A simple characterization is given, and a new approach is developed, which can be used to study a wide variety of problems for communications over a wideband channel. The flat block fading channel is studied, which transmits one scalar symbol per symbol time distorted by a multiplicative fading coefficient and the additive Gaussian noise.

We compare two strategies for lossy source description across a pair of unreliable channels. In the first strategy, we use a broadcast channel code to achieve a different rate for each possible channel realization, and then use a multiresolution source code to describe the source at the resulting rates. In the second strategy, we use a channel coding strategy for two independent channels coupled with a multiple description source code. In each case, we choose the coding parameters to minimize the expected end-to-end distortion in the source reconstruction. We demonstrate that in point-to-point communication across a pair of non-ergodic channels, multiple description coding can provide substantial gains relative to multiresolution and broadcast coding. We then investigate this comparison in a simple MIMO channel. We demonstrate the inferior performance of space time coding with multiresolution source coding and broadcast channel coding relative to multiple description codes and a time sharing channel coding strategy. These results indicate that for non-ergodic channels, the traditional definition of channel capacity does not necessarily lead to the best channel code from the perspective of end-to-end source distortion.

We study the capacity of fading channels with no CSI at both the transmitter and the receiver. We focus on the low SNR regime, and study the impact of channel memory on the capacity. While the current results on these issues are based on various limiting assumptions, we use a new approach of asymptotic analysis to capture the relation among the key system parameters, and depict the continuum between the extreme cases.

We consider a dynamical probabilistic traffic model for the number of users transmitting at any time. This model captures both user mobility and traffic burstiness. Moreover, we assume no centralized controller, such as a scheduler, is available. When multiple users transmit simultaneously, multiple-access interference (MAI) affects throughput considerably. Most queue control schemes assume individual users know the states of their own queues (local queue information) along with the states of other users queues (shared queue information) and address issues of scheduling; but this sharing of information may be onerous in a practical system. While shared queue information has recently been shown (Me/spl acute/dard et al., 2004) not to affect the capacity of such systems, it has a considerable impact on delay. We introduce a scheme, where for each user, a bit of shared queue information specifies whether its queue length is above or below a threshold. Our scheme relies on two different service classes implemented through a superposition coding scheme (first proposed with Me/spl acute/dard and Goldsmith, 1999, further studied and expanded with Me/spl acute/dard et al., 2004). The first class experiences no delay due to multiple-access interference, while the second class requires retransmissions when such an event occurs. We show how our scheme affords an energy-delay tradeoff. Moreover, when configured properly, our scheme can attain boundary points of the region corresponding to minimum energy with no shared queue information for zero delay along with minimum energy subject to system stability. We derive bounds on the performance of the multiple-access system using our proposed scheme by introducing Lyapunov function bounds in a manner similar to Bertsimas et al., 2001.

In this paper, we consider the design of a physical network topology that meets a high level of reliability using unreliable network elements. We are motivated by the use of networks and, in particular, all-optical networks, for high-reliability applications which involve unusual and catastrophic stresses. Our network model is one in which nodes are invulnerable and links are subject to failure - a good approximation for optical networks with passive nodes and vulnerable fiber under stress of disconnection - and we focus on statistically independent link failures with initial steps taken toward generalization to dependent link failures. Our reliability metrics are the all-terminal connectedness measure and the less commonly considered two-terminal connectedness measure. We compare in the low and high stress regimes, via analytical approximations and simulations, common commercial architectures designed for all-terminal reliability when links are very reliable with alternative architectures which are mindful of both of our reliability metrics and regimes of stress. We derive new results especially for one of these alternative architectures, Harary graphs, which have been shown to possess attractive reliability properties. Furthermore, we show that for independent link failures network design should be optimized with respect to reliability under high stress, as reliability under low stress is less sensitive to graph structure; and that under high stress, very high node degrees and small network diameters are required to achieve moderate reliability performance. Finally, in our discussion of correlated failure models, we show the danger in relying on an independent failure model and the need for the network architect to minimize component failure dependencies.

We analyze the error probability of peaky signaling on bandlimited multipath fading channels, the signaling strategy that achieves the capacity of such channels in the limit of infinite bandwidth under an average power constraint. We first derive an upper bound for general fading, then specialize to the case of Rayleigh fading, where we obtain upper and lower bounds that are exponentially tight and, therefore, yield the reliability function. These bounds constitute a strong coding theorem for the channel, as they not only delimit the range of achievable rates, but also give us a relationship among the error probability, data rate, bandwidth, peakiness, and fading parameters, such as the coherence time. They can be used to compare peaky signaling systems to other large bandwidth systems over fading channels, such as ultra-wideband radio and wideband code-division multiple access. We find that the error probability decreases slowly with the bandwidth W; under Rayleigh fading, the error probability varies roughly as W/sup -/spl alpha//, where /spl alpha/>0. With parameters typical of indoor wireless situations, we study the behavior of the upper and lower bounds on the error probability and the reliability function numerically.

We study different notions of capacity for time-slotted ALOHA systems. In these systems, multiple users synchronously send packets in a bursty manner over a common additive white Gaussian noise (AWGN) channel. The users do not coordinate their transmissions, which may collide at the receiver. For such a system, we define both single-slot capacity and multiple-slot capacity. We then construct a coding and decoding scheme for single-slot capacity that achieves any rate within this capacity region. This coding and decoding scheme for a single time slot combines aspects of multiple access rate splitting and of broadcast codes for degraded AWGN channels. This design allows some bits to be reliably received even when collisions occur and more bits to be reliably received in the absence of collisions. The exact number of bits reliably received under both of these scenarios is part of the code design process, which we optimize to maximize the expected rate in each slot. Next, we examine the behavior of the system asymptotically over multiple slots. We show that there exist coding and decoding strategies such that regardless of the burstiness of the traffic, the system is stable as long as the average rate of the users is within the multiple access capacity region of the channel. In other words, we show that bursty traffic does not decrease the Cover-Wyner capacity region of the multiple access channel. A vast family of codes, which includes the type of codes we introduce for the single-slot transmission, achieve the capacity region, in a sense we define, for multiple-slot transmissions. These codes are stabilizing, using only local information at each of the individual queues. The use of information regarding other queues or the use of scheduling does not improve the multiple-slot capacity region.

Flash signalling (with vanishing duty cycle) frequency shift keying (FSK) is known to be a capacity-achieving modulation for multipath fading channels in the limit of infinite bandwidth. However, since capacity-achieving schemes using flash FSK build the richness of their codebooks in frequency, the data rates of such schemes increase slowly with bandwidth. We seek to establish schemes that exhibit better performance than flash FSK for large but finite bandwidth. We consider multitone FSK, which we have shown in our previous work that can also achieve the infinite-bandwidth capacity limit for multipath fading channels, but is more general than FSK. Given its increased generality vis-a-vis FSK, and its optimality from a capacity point of view, multitone FSK is a good candidate for transmission over very wide bandwidth. In this paper, we discuss upper and lower bounds of error probabilities for the family of multitone FSK in Rayleigh fading channels. We find that these two bounds coincide in the infinite bandwidth limit and are therefore asymptotically tight. We compare the error probabilities of FSK and multitone FSK in different situations and conclude that FSK is the preferable scheme when average power is the biting constraint, and multitone FSK may be preferable when peak power is a limiting factor. We also explore the relationship among capacity and parameters related to time efficiency and spectrum efficiency.

A two transmitter single receiver multiple access noise-free network is considered where interference is additive and the transmit and receive alphabet size is the same. We consider two performance metrics - code rate and sum rate. Code rate is defined as the ratio of the symbols recovered, after multiple access interference, to the symbols sent by the transmitters. The sum rate is the number of symbols successfully received per unit time. A packet by packet coding scheme is presented where we determine how these rates change with redundancy. We propose a coding mechanism that maximizes the code and sum rates and show that it suffices to code at only one of the transmitters and that systematic codes are sufficient for this purpose. The development is independent of the alphabet size the symbols are defined over. We also show that we can achieve maximum rates by using a random code. This allows us to choose codes in a random fashion and the scheme achieves optimality with probability tending to 1 exponentially with the code length.

Spreading is used to provide diversity in frequency and results in a number of benefits. However, recent literature has shown that for a channel that decorrelates in time and frequency, the capacity of a wideband system in a fading channel goes to zero in the limit of infinite bandwidth (given second and fourth moment constraints that decay with the spreading bandwidth). We first extend to the two-user case the upper bound from Medard and Tse (Ref.5). Together with a lower bound based on binary transmission, meaningful bounds to the optimal spreading bandwidth using DS-CDMA are obtained. Given typical system and channel parameters, the minimum spreading bandwidth behaves as a linear function of channel strength. We will show that this result can be meaningfully applied as guidelines in the design of future communication systems.

We present an information theoretic framework for network management for recovery from nonergodic link failures. Building on recent work in the field of network coding, we describe the input-output relations of network nodes in terms of network codes. This very general concept of network behavior as a code provides a fundamental way to quantify essential management information as that needed to switch among different codes (behaviors) for different failure scenarios. We give bounds on the network management information needed for link failure recovery in various network connection problems, in terms of basic parameters such as the number of source processes and the number of links in a minimum source-receiver cut. This is the first paper to our knowledge that looks at network management for general connections.

We take a new look at the issue of network capacity. It is shown that network coding is an essential ingredient in achieving the capacity of a network. Building on recent work by Li et al.(see Proc. 2001 IEEE Int. Symp. Information Theory, p.102), who examined the network capacity of multicast networks, we extend the network coding framework to arbitrary networks and robust networking. For networks which are restricted to using linear network codes, we find necessary and sufficient conditions for the feasibility of any given set of connections over a given network. We also consider the problem of network recovery for nonergodic link failures. For the multicast setup we prove that there exist coding strategies that provide maximally robust networks and that do not require adaptation of the network interior to the failure pattern in question. The results are derived for both delay-free networks and networks with delays.

We consider the issue of network capacity. Recent work by Li and Yeung examined the network capacity of multicast networks and related capacity to cutsets. Capacity is achieved by coding over a network. We present a new framework for studying networks and their capacity. Our framework, based on algebraic methods, is surprisingly simple and effective. For networks which are restricted to using linear codes (we make the meaning of linear codes precise, since the codes are not bit-wise linear), we find necessary and sufficient conditions for any given set of connections to be achievable over a given network. For multicast connections, linear codes are not a restrictive assumption, since all achievable connections can be achieved using linear codes. Moreover, coding can be used to maintain connections after permanent failures, such as the removal of an edge from the network. We show necessary and sufficient conditions for a set of connections to be robust to a set of permanent failures. For multicast connections, we show the rather surprising result that, if a multicast connection is achievable under different failure scenarios, a single static code can ensure robustness of the connection under all of those failure scenarios.

We propose a new protection scheme, which we term partial path protection (PPP), to select end-to-end backup paths using local information about network failures. PPP designates a different restoration path for every link failure on each primary path. PPP also allows reuse of operational segments of the original primary path in the protection path. A novel approach used in this paper is that of a dynamic call-by-call model with blocking probability as the performance metric, this model is in contrast with traditional capacity-efficiency measurement for batch call arrivals. Additionally, we show that a simple method based on shortest path routing for which primary paths are selected first is more effective than a greedy approach that minimizes, for each call arrival, the number of wavelengths used by the primary and backup path jointly.

We describe an architecture for an optical local area network (LAN) or metropolitan area network (MAN) access. The architecture allows for bandwidth sharing within a wavelength and is robust to both link and node failures. The architecture can be utilized with an arbitrary, link-redundant mesh network (node-redundancy is necessary only to handle all node failures), and assumes neither the use of a star topology nor the ability to embed such a topology within the physical mesh. Reservation of, bandwidth is performed in a centralized fashion at a (replicated) head end node, simplifying the implementation of complex sharing policies relative to implementation on a distributed set of routers. Unlike a router, however, the head end does not take any action on individual packets and, in particular, does not buffer packets. The architecture thus avoids the difficulties of processing packets in the optical domain while allowing for packetized shared access of wavelengths. We describe the route construction scheme and prove its ability to recover from single link and single node failures, outline a flexible medium access protocol and discuss the implications for implementing specific policies, and propose a simple implementation of the recovery protocol in terms of state machines for per-link devices.

A network consisting of transparent optical nodes (TONs) can provide high speed end-to-end communication paths with very low bit-error rates (BERs). However, owing to component crosstalk and other degradations at TONs, the BER of a particular communication path traversing several TONs can be degraded by a few orders of magnitude even in the absence of component failure. Monitoring the quality-of-service (QoS) of a communication path has typically relied on sporadic BER testing and operation monitoring by the nodes using probe signals. Intermittent BER testing cannot provide continuous monitoring of the network QoS. On the other hand, the use of probe signals is not sensitive enough to detect the BER degradation. This work investigates a novel approach of monitoring service degradation at individual nodes using a wrap-around device which taps and compares signals from the input and the output at each TON along the lightpath. We propose a modification using hard limiters at TON inputs and derive the BER value that this modified method can guarantee in the presence of signal degradation due to coherent crosstalk at TONs.

We show that very large bandwidths on fading multipath channels cannot be effectively utilized by spread-spectrum systems that (in a particular sense) spread the available power uniformly over both time and frequency. The approach is to express the input process as an expansion in an orthonormal set of functions each localized in time and frequency. The fourth moment of each coefficient in this expansion is then uniformly constrained. We show that such a constraint forces the mutual information to 0 inversely with increasing bandwidth. Simply constraining the second moment of these coefficients does not achieve this effect. The results suggest strongly that conventional direct-sequence code-division multiple-access (CDMA) systems do not scale well to extremely large bandwidths. To illustrate how the interplay between channel estimation and symbol detection affects capacity, we present results for a specific channel and CDMA signaling scheme.

Current means of providing loop-back recovery, which is widely used in SONET, rely on ring topologies, or on overlaying logical ring topologies upon physical meshes. Loop-back is desirable to provide rapid preplanned recovery of link or node failures in a bandwidth-efficient distributed manner. We introduce generalized loop-back, a novel scheme for performing loop-back in optical mesh networks. We present an algorithm to perform recovery for link failure and one to perform generalized loop-back recovery for node failure. We illustrate the operation of both algorithms, prove their validity, and present a network management protocol algorithm, which enables distributed operation for link or node failure. We present three different applications of generalized loop-back. First, we present heuristic algorithms for selecting recovery graphs, which maintain short maximum and average lengths of recovery paths. Second, we present WDM-based loop-back recovery for optical networks where wavelengths are used to back up other wavelengths. We compare, for WDM-based loop-back, the operation of generalized loop-back operation with known ring-based ways of providing loop-back recovery over mesh networks. Finally, we introduce the use of generalized loop-back to provide recovery in a way that allows dynamic choice of routes over preplanned directions.

We study the relationship between failure localization and the properties of link restoration algorithms, employing a quantitative measure of a network's ability to recover from two-link failures. This model allows us to consider issues of failure localization that cannot be addressed through models that assume only single failures. Based on the relationship between algorithmic properties and restoration failures, we construct a failure classification hierarchy that provides insight as to the relative value of advances in algorithm design. Finally, we apply this classification scheme to three networks from the literature and discuss the results in terms of their importance for link restoration algorithms. We find that the topological constraints on restoration paths required by algorithms that embed rings within mesh networks result in significant degradation of failure localization. The preselection of restoration paths (as opposed to selection at the time of failure) also has a negative impact, although it is not as significant as the topological effect. Algorithms that make use of the mesh topology and dynamically route around existing failures come close to an inherent limit imposed by the complexity of additional algorithmic advances.

We present a model for time-varying communication single-access and multiple-access channels without feedback. We consider the difference between mutual information when the receiver knows the channel perfectly and mutual information when the receiver only has an estimate of the channel. We relate the variance of the channel measurement error at the receiver to upper and lower bounds for this difference in mutual information. We illustrate the use of our bounds on a channel modeled by a Gauss-Markov process, measured by a pilot tone. We relate the rate of time variation of the channel to the loss in mutual information due to imperfect knowledge of the measured channel.

Current means of providing loop-back recovery, which is widely used in SONET, relies on fiber-based recovery, where a fiber is used to back up another fiber. We present WDM-based loop-back recovery for optical networks where wavelengths are used to back up other wavelengths. We present two new algorithms for performing WDM-based loop-back over optical mesh networks. The first algorithm performs recovery for link failures. We compare its operation with known ways of providing loop-back recovery and show that the known methods are not applicable to WDM-based recovery. The second algorithm performs WDM loop-back recovery for node failures. We illustrate the operation of both algorithms and prove their validity. We discuss the advantages of WDM-based loop-back for flexibility in WDM service provisioning.

In order increase the capacity in the wireless domain, the signals from several distributed receivers may be combined. The combining of these signals typically requires transmission over a wireline network. In the wireline domain, signals may be transmitted to a single centralized processing node or may be processed in a distributed fashion at several nodes in the network. We compare, for white Gaussian noise channels, the capacity gains that can be obtained from distributed processing of wireline signals to the capacity gains obtained using maximum likelihood ratio combining at a single processing node. We find that, by using optimal detection techniques, the bandwidth requirements in the wireline domain can be significantly reduced without reducing the capacity in the wireless domain. These gains in capacity are achieved by eliminating transmission of redundant information in the wireline network.

We consider the capacity of time-slotted ALOHA systems, where multiple users synchronously send packets, which may collide at the receiver. Specific coding for ALOHA systems had previously been proposed to avoid complete loss of packets involved in collisions, but the capacity of ALOHA systems had not been previously determined. We consider capacity in terms of reliably received rate rather than transmitted rate. We consider capacity achieving strategies under AWGN for transmission of a single packet which is long enough to achieve capacity over the duration of the packet. We combine concepts from multi-access channels and broadcast channels to determine the capacity region for a single transmission of a packet in an ALOHA system. The coding for each user takes into account the possibility of collisions with other users in order to establish a capacity region. Next, we consider the case where we transmit several packets under a channel model where users receive the right to transmit the package according to independent Bernoulli processes. We can then apply the single-packet coding strategies in order to maximize the expected reliable received rate.

We present a new algorithm which creates redundant trees on arbitrary node-redundant or link-redundant networks. These trees are such that any node is connected to the common root of the trees by at least one of the trees in case of node or link failure. Our scheme provides rapid preplanned recovery of communications with great flexibility in the topology design. Unlike previous algorithms, our algorithm can establish two redundant trees in the case of a node failing in the network. In the case of failure of a communications link, our algorithm provides a superset of the previously known trees.

We present a new algorithm for automatic protection switching (APS) which creates node (edge) redundant trees on any node (edge)-redundant network. These trees are desirable for performing multicasting with APS. Our algorithm is based on constructing trees with appropriate associated directions. The algorithm gives great flexibility in the choice of trees.

We propose a new algorithm for constructing redundant trees over any edge or node-redundant network in order to perform automatic protection switching in the presence of edge or node failures. Existing redundancy schemes and their topological requirements are reviewed. We describe our algorithm and give an overview of its essential properties. The algorithm is polynomial in the number of nodes. We present an example of the construction of a lowest cost redundant topology for a given configuration and of the operation of our algorithm on that topology. The algorithm is particularly well suited to multicast networks and optical networks, where trees may be created by signal splitting.