Search

We consider the $N$-user broadcast erasure channel with $N$ unicast sessions (one for each user) where receiver feedback is regularly sent to the transmitter in the form of ACK/NACK messages. We first provide a generic outer bound to the capacity of this system; we then propose a virtual-queue-based inter-session mixing coding algorithm, determine its rate region and show that it achieves capacity under certain conditions on channel statistics, assuming that instantaneous feedback is known to all users. Removing this assumption results in a rate region that asymptotically differs from the outer bound by 1 bit as $L\to \infty$, where $L$ is the number of bits per packet (packet length). For the case of arbitrary channel statistics, we present a modification of the previous algorithm whose rate region is identical to the outer bound for N=3, when instant feedback is known to all users, and differs from the bound by 1 bit as $L\to \infty$, when the 3 users know only their own ACK. The proposed algorithms do not require any prior knowledge of channel statistics., Comment: 54 pages, 3 figures, 3 tables, submitted to IEEE Transactions on Information Theory. Updated version to match reviewer comments

We consider a source node broadcasting to two receivers over a general erasure channel with receiver feedback. We characterize the capacity region of the channel and construct algorithms based on linear network coding (either randomized or depending on channel dynamics) that achieve this capacity. We then consider stochastic arrivals at the source for the two destinations and characterize the stable throughput region achieved by adapting the same algorithms that achieve capacity. Next, we modify these algorithms to improve their delay performance and characterize their stable throughput regions. Although the capacity and stability regions obtained by the algorithms are not always identical (because of the extra overhead needed for the algorithms to handle stochastic traffic), they are within a few bits of each other and have similar forms. This example exhibits an unusual relationship between capacity and stability regions and extends similar prior studies for multiple access channels.

The problem of sequentially finding an independent and identically distributed sequence that is drawn from a probability distribution Q1 by searching over multiple sequences, some of which are drawn from Q1 and the others of which are drawn from a different distribution Q0, is considered. In the problem considered, the number of sequences with distribution Q1 is assumed to be a random variable whose value is unknown. Within a Bayesian formulation, a sequential decision rule is derived that optimizes a trade-off between the probability of false alarm and the number of samples needed for the decision. In the case in which one can observe one sequence at a time, it is shown that the cumulative sum (CUSUM) test, which is well-known to be optimal for a non-Bayesian statistical change-point detection formulation, is optimal for the problem under study. Specifically, the CUSUM test is run on the first sequence. If a reset event occurs in the CUSUM test, then the sequence under examination is abandoned and the rule switches to the next sequence. If the CUSUM test stops, then the rule declares that the sequence under examination when the test stops is generated by Q1 . The result is derived by assuming that there are infinitely many sequences so that a sequence that has been examined once is not retested. If there are finitely many sequences, the result is also valid under a memorylessness condition. Expressions for the performance of the optimal sequential decision rule are also developed. The general case in which multiple sequences can be examined simultaneously is considered. The optimal solution for this general scenario is derived.

A single commodity network that models the information flow in an arbitrary topology sensor field that collects and forwards information to a backbone through certain designated gateway nodes is considered. Resilient operation in overload stress situations caused by unpredictable traffic or topology variations is investigated. That amounts to studying the network in instability mode, where the traffic load distribution is outside the throughput region. A fluid model is adopted where superflows model traffic forwarding and backlog formations at the network level. Quantitative performance metrics of the overload including throughput, lexicographic minimization, most balanced allocation, and amount of lost traffic due to buffer overflow are considered to capture the information loss process due to overflow in the network. Optimal superflows with respect to these metrics are characterized and a distributed asynchronous algorithm that computes such superflows is given. The characterization of the optimal superflow amounts to obtaining a structural decomposition of the network in a sequence of disjoint subregions with decreasing overload such that traffic flows only from regions of higher overload to regions of lower overload. The optimal superflow represents the smoothest trajectory to overflow, followed by the network in case of instability.

We consider a slotted ring that allows simultaneous transmissions of messages by different nodes, known as ring with spatial reuse. To alleviate fairness problems that arise in such networks, policies have been proposed that operate in cycles and guarantee that a certain number of packets, not exceeding a given number called a quota, will be transmitted by every node in every cycle. We provide sufficient and necessary stability conditions that implicitly characterize the stability region for such rings. These conditions are derived by extending a technique developed for some networks of queues satisfying a monotonicity property. Our approach to instability is novel and its peculiar property is that it is derived from the instability of a dominant system. Interestingly, the stability region depends on the entire distribution of the message arrival process and the steady-state average cycle lengths of lower dimensional systems, leading to a region with nonlinear boundaries, the exact computation of which is in general intractable. Next, we introduce the notions of essential and absolute stability region. An arrival rate vector belongs to the former region if the system is stable under any arrival distribution with this arrival vector, while it belongs to the latter if there exists some distribution with this rate vector for which the system is stable. Using a linear programming approach, we derive bounds for these stability regions that depend only on conditional average cycle lengths. For the case of two nodes, we provide closed-form expressions for the essential stability region.

We consider the $N$ -receiver broadcast erasure channel with feedback and message side information at the receivers prior to beginning of transmission. Specifically, the transmitter must deliver different, independent messages to each of the receivers, and each receiver knows a function of these messages before transmission begins. This situation can arise in multi-hop wireless networks, where a receiver may overhear transmissions consisting of possibly encoded combinations of messages (e.g., encoded using a network coding technique) prior to beginning of transmission over a given broadcast channel. We provide an outer bound to the capacity region of this system. For the case, where each message consists of a number of symbols taking values in a finite field and each receiver knows linear combinations of these symbols, the outer bound is given in terms of ranks of matrices expressing the linear combinations. For the latter case and when $N=2$ , the outer bound is tight under mild conditions on the limiting behavior of the ranks of matrices expressing the side information. We provide a capacity achieving code for this case. The special case, where each receiver either knows the entire message of another receiver or has no information about it, constitutes a generalization of the index coding problem that incorporates channel erasures. For this instance, and when there are no channel errors, we show that the outer bound reduces to the known maximum weighted acyclic induced subgraph bound.

We consider Poisson packet traffic accessing a single-slotted channel. We assume the existence of a ternary feedback per channel slot. We also adopt the limited feedback sensing model where each user senses the feedback only while he has a packet to transmit. For this model we develop a collision resolution algorithm with last come-first served characteristics. The algorithm attains the same throughput as Gallager's algorithm without the latter's full feedback sensing requirement. In addition, it is easy to implement, requires reasonable memory storage, induces uniformly good transmission delays, and is insensitive to feedback errors. In the presence of binary (collision versus noncollision) feedback the algorithm may attain a throughput of 0.4493 .

A slotted packet broadcast channel with an infinite user population is considered. A limited feedback sensing algorithm is proposed and analyzed for collision versus noncollision binary feedback. The algorithm bas maximum throughput equal to 0.42 (packets/slot), has uniformly good delay characteristics within its stability region, and is robust in the presence of feedback errors. A variation of the algorithm, for ternary feedback, attains maximum throughput 0.425 and bas uniformly good delay characteristics within its stability region. In contrast, the highest throughput limited feedback sensing algorithm existing for ternary feedback attains maximum throughput 0.456 , but induces relatively high delays for Poisson intensities below 0.3 .