We consider a communication network consisting of nodes and directed edges that connect the nodes. The network may contain cycles. The communications are slotted where the duration of each time slot is equal to the maximum propagation delay experienced by the edges. The edges with negligible delays are allowed to be operated before the other edges in each time slot. For any pair of adjacent edges @math and @math , where @math terminates at node @math and @math originates from node @math , we say @math incurs zero delay on @math if @math is operated before @math ; otherwise, we say @math incurs a unit delay on @math . In the classical model, every edge incurs a unit delay on every adjacent edge and the cut-set bound is a well-known outer bound on the capacity region. In this paper, we investigate the multimessage multicast network (MMN) consisting of independent channels, where each channel is associated with a set of edges and each edge may incur zero delay on some other edges. Our result reveals that the capacity region of the MMN with independent channels and zero-delay edges lies within the classical cut-set bound despite a violation of the unit-delay assumption.
It was shown by Effros @cite_4 that under the positive-delay assumption Effros's framework does not consider zero-delay edges, which can be seen from the encoding rules stated in [Def. 1] EffrosIndependentDelay that assumes @math is a function of @math . in the classical setting, the set of achievable rate tuples for the MMN with independent channels does not depend on the amount of positive delay incurred by each edge on each other edge. Our capacity result for the MMN with independent DMCs (as well as AWGNs) complements Effros's finding as follows: The set of achievable rate tuples for the MMN with independent DMCs (as well as AWGNs) does not depend on the amount of delay incurred by each edge on each other edge, even with the presence of zero-delay edges. From a practical point of view, the capacity region of the MMN with independent DMCs (as well as AWGNs) is not affected by the way of handling delays among the channels or how the channels are synchronized, even when zero-delay edges are present.
@cite_4
2107543180 1512015702 2143157029 1965978478
For output-symmetric discrete memoryless channels (DMCs) at even moderately high rates, fixed-block-length communication systems show no improvements in their error exponents with feedback. This paper studies systems with fixed end-to-end delay and shows that feedback generally provides dramatic gains in the error exponents. A new upper bound (the uncertainty-focusing bound) is given on the probability of symbol error in a fixed-delay communication system with feedback. This bound turns out to have a form similar to Viterbi's bound used for the block error probability of convolutional codes as a function of the fixed constraint length. The uncertainty-focusing bound is shown to be asymptotically achievable with noiseless feedback for erasure channels as well as for any output-symmetric DMC that has strictly positive zero-error capacity. Furthermore, it can be achieved in a delay-universal (anytime) fashion even if the feedback itself is delayed by a small amount. Finally, it is shown that for end-to-end delay, it is generally possible at high rates to beat the sphere-packing bound for general DMCs - thereby providing a counterexample to a conjecture of Pinsker. We address an open question, regarding whether a lattice code with lattice decoding (as opposed to maximum-likelihood (ML) decoding) can achieve the additive white Gaussian noise (AWGN) channel capacity. We first demonstrate how minimum mean-square error (MMSE) scaling along with dithering (lattice randomization) techniques can transform the power-constrained AWGN channel into a modulo-lattice additive noise channel, whose effective noise is reduced by a factor of spl radic (1+SNR SNR). For the resulting channel, a uniform input maximizes mutual information, which in the limit of large lattice dimension becomes 1 2 log (1+SNR), i.e., the full capacity of the original power constrained AWGN channel. We then show that capacity may also be achieved using nested lattice codes, the coarse lattice serving for shaping via the modulo-lattice transformation, the fine lattice for channel coding. We show that such pairs exist for any desired nesting ratio, i.e., for any signal-to-noise ratio (SNR). Furthermore, for the modulo-lattice additive noise channel lattice decoding is optimal. Finally, we show that the error exponent of the proposed scheme is lower bounded by the Poltyrev exponent. Upper and lower bounds on the capacity and minimum energy-per-bit for general additive white Gaussian noise (AWGN) and frequency-division AWGN (FD-AWGN) relay channel models are established. First, the max-flow min-cut bound and the generalized block-Markov coding scheme are used to derive upper and lower bounds on capacity. These bounds are never tight for the general AWGN model and are tight only under certain conditions for the FD-AWGN model. Two coding schemes that do not require the relay to decode any part of the message are then investigated. First, it is shown that the "side-information coding scheme" can outperform the block-Markov coding scheme. It is also shown that the achievable rate of the side-information coding scheme can be improved via time sharing. In the second scheme, the relaying functions are restricted to be linear. The problem is reduced to a "single-letter" nonconvex optimization problem for the FD-AWGN model. The paper also establishes a relationship between the minimum energy-per-bit and capacity of the AWGN relay channel. This relationship together with the lower and upper bounds on capacity are used to establish corresponding lower and upper bounds on the minimum energy-per-bit that do not differ by more than a factor of 1.45 for the FD-AWGN relay channel model and 1.7 for the general AWGN model. This paper analyzes the worst-case performance of randomized backoff on simple multiple-access channels. Most previous analysis of backoff has assumed a statistical arrival model.For batched arrivals, in which all n packets arrive at time 0, we show the following tight high-probability bounds. Randomized binary exponential backoff has makespan Θ(nlgn), and more generally, for any constant r, r-exponential backoff has makespan Θ(nloglgr n). Quadratic backoff has makespan Θ((n lg n)3 2), and more generally, for r>1, r-polynomial backoff has makespan Θ((n lg n)1+1 r). Thus, for batched inputs, both exponential and polynomial backoff are highly sensitive to backoff constants. We exhibit a monotone superpolynomial subexponential backoff algorithm, called loglog-iterated backoff, that achieves makespan Θ(nlglg n lglglg n). We provide a matching lower bound showing that this strategy is optimal among all monotone backoff algorithms. Of independent interest is that this lower bound was proved with a delay sequence argument.In the adversarial-queuing model, we present the following stability and instability results for exponential backoff and loglog-iterated backoff. Given a (λ,T)-stream, in which at most n=λT packets arrive in any interval of size T, exponential backoff is stable for arrival rates of λ=O(1 lgn) and unstable for arrival rates of λ=Ω(lglgn lgn); loglog-iterated backoff is stable for arrival rates of λ=O(1 (lglgn )) and unstable for arrival rates of λ=Ω(1 lgn). Our instability results show that bursty input is close to being worst-case for exponential backoff and variants and that even small bursts can create instabilities in the channel.