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.

Accurate vehicular localization is important for various cooperative vehicle safety (CVS) applications such as collision avoidance, turning assistant, etc. In this paper, we propose a cooperative vehicular distance measurement technique based on the sharing of GPS pseudorange measurements and a weighted least squares method. The classic double difference pseudorange solution, which was originally designed for high-end survey level GPS systems, is adapted to low-end navigation level GPS receivers for its wide availability in ground vehicles. The Carrier to Noise Ratio (CNR) of raw pseudorange measurements are taken into account for noise mitigation. We present a Dedicated Short Range Communications (DSRC) based mechanism to implement the exchange of pseudorange information among neighboring vehicles. As demonstrated in field tests, our proposed technique increases the accuracy of the distance measurement significantly compared with the distance obtained from the GPS fixes.

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.

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.

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.

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 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.

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.

Runlength limited (RLL) codes are essential in recording systems for minimizing distortions and maintaining bit synchronization. In this paper, we investigate the application of turbo codes on RLL (1,7) coded partial response equalized recording channels. We proposed a 'combined trellis' approach for doing 'soft-in soft-out' (SISO) channel detection and RLL decoding jointly. This approach makes the implementation of turbo equalization easier since it eliminates the need for a 'SISO RLL encoder' in the feedback path from turbo decoder to channel detector. Simulation studies on magnetic recording channels show that our approach provides a coding gain of about 4 dB compared to Viterbi detection at 10/sup -6/ bit error rate.

The application of iterative detection using turbo codes for signal detection in magnetic recording channels has become a topic of intense research. Interesting results have been reported for partial response equalized recording channels. This paper investigates the performance of turbo codes on decision feedback equalized (DFE) recording channels. The channel detector used is a soft-in soft-out parallel DFE (PDFE) detector. Simulation results shows a coding gain of more than 3 dB at a bit error rate of 10/sup -6/. Further, the error propagation in PDFE has been significantly minimized by the de-interleaver between PDFE and turbo decoder, and it does not influence the overall burst error performance.