We consider the problem of decodability when random linear coding (RLC) is performed on a stream of packets in a line network. First, we clearly define the problem of decodability for a stream of arriving packets, and discuss its importance with some examples. Then, we will find the limits on the mean arrival rate under which the stream is decodable. Further, upper bounds will be derived for the average length of a decoded block of packets in multi-hop line networks. Finally, these analytical results are validated via simulations.

In this paper, we study the block delivery delay of random linear network coding in two-hop single-unicast delay-tolerant networks with grid-based mobility. By block delivery delay, we mean how long it takes the destination to receive all the K information packets of a single block. Our work includes two parts. First, we give a general analysis of the dependency between packet spaces spanned by different nodes in a stochastic way. Then we simplify the result by means of the approximation. By the dependency analysis, we can accurately update nodes' innovativeness rank. Second, via tracking the innovativeness ranks of all nodes, we develop an analytic framework to iteratively compute the cumulative distribution function of the block delivery delay. Our simulation results verify that both parts of our analysis are sufficiently accurate. Copyright © 2013 John Wiley & Sons, Ltd.

We consider disruption tolerant networks (DTNs) wherein a direct communication path from a source to a destination via multiple hops does not exist due to both mobility and sparseness of the nodes. Hence, mobile nodes will deliver messages from source to destination using a “store, carry, and forward” strategy. In this paper, our goal is to analytically study the packet latency in such networks for a two-hop unicast scenario with Bernoulli packet arrivals at the source. We exploit an embedded Markov chain approach combined with our novel iterative estimation technique to study both network delay and queuing delay. Constraints posed by both the limited node buffer size and contention between nodes for wireless channel are also considered to obtain a more realistic model. Finally, our results are validated using simulations for a random-walk on a two-dimensional grid mobility model.

We consider sparse mobile ad-hoc networks (i.e., disruption-tolerant networks or DTNs) wherein a direct communication path from a source to a destination via multiple hops does not exist due to both mobility and sparseness of the nodes. Hence, the nodes will deliver messages from source to destination using a “store, carry, and forward” strategy. Our goal is to analytically study the packet latency in such networks for a two-hop unicast scenario with bursty packet arrivals at the source. We exploit an embedded Markov chain approach combined with our novel iterative estimation technique to study both network delay and queuing delay. Constraints posed by both the limited node buffer size and contention between nodes for wireless channel are also considered in order to obtain a more realistic model. Finally, our iterative results are validated using simulations for well-known mobility models such as random walk on a grid and the random waypoint mobility.

We consider the problem of estimating throughput and average latency in wireless erasure networks with nodes having finite buffers. In these networks, packets are either lost due to link erasures or dropped because of full buffers. Further, a finite-buffer adaptation of backpressure routing policy is used. The exact Markov chain modeling of such networks for the sake of performance analysis turns out to be an extremely difficult problem in general due to the large number of states and their complicated transitions. In this paper, we propose a novel iterative method that estimates the performance parameters of such networks with much less complexity comparing to the exact analysis. The proposed framework leads to an accurate estimate of the steady-state probability distribution of buffer occupancies using which analytical expressions are obtained for throughput and average packet delay in the network. Finally, these analytical results are validated via simulations.

In this paper, we present an exact model for the analysis of the performance of Random Linear Network Coding (RLNC) in wired erasure networks with finite buffers. In such networks, packets are delayed due to either random link erasures or blocking by full buffers. We assert that because of RLNC, the content of buffers have dependencies which cannot be captured directly using the classical queueing theoretical models. We model the performance of the network using Markov chains by a careful derivation of the buffer occupancy states and their transition rules. We verify by simulations that the proposed framework results in an accurate measure of the network throughput offered by RLNC. Further, we introduce a class of acyclic networks for which the number of state variables is significantly reduced.

This work investigates the effect of finite buffer sizes on the throughput capacity and packet delay of line networks with packet erasure links that have perfect feedback. These performance measures are shown to be linked to the stationary distribution of an underlying irreducible Markov chain that models the system exactly. Using simple strategies, bounds on the throughput capacity are derived. The work then presents two iterative schemes to approximate the steady-state distribution of node occupancies by decoupling the chain to smaller queueing blocks. These approximate solutions are used to understand the effect of buffer sizes on throughput capacity and the distribution of packet delay. Using the exact modeling for line networks, it is shown that the throughput capacity is unaltered in the absence of hop-by-hop feedback provided packet-level network coding is allowed. Finally, using simulations, it is confirmed that the proposed framework yields accurate estimates of the throughput capacity and delay distribution and captures the vital trends and tradeoffs in these networks.

The exact Markov modeling analysis of erasure networks with finite buffers is an extremely hard problem due to the large number of states in the system. In such networks, packets are lost due to either link erasures or blocking by the full buffers. In this paper, we propose a novel method that iteratively estimates the performance parameters of the network and more importantly reduces the computational complexity compared to the exact analysis. This is the first work that analytically studies the effect of finite memory on the throughput and latency in general wired acyclic networks with erasure links. As a case study, a random packet routing scheme with ideal feedback on the links is used. The proposed framework yields a fairly accurate estimate of the probability distribution of buffer occupancies at the intermediate nodes using which we can not only identify the congested and starving nodes but also obtain analytical expressions for throughput and average delay of a packet in the network. The theoretical framework presented here can be applied to many wired networks, from Internet to more futuristic applications such as networks-on-chip under various communication and network coding scenarios.