In this article we present CodeCast, a network-coding-based ad hoc multicast protocol. CodeCast is especially well-suited for multimedia applications with low-loss, low-latency constraints such as audio/video streaming. The key ingredient of CodeCast is random network coding, which transparently implements both localized loss recovery and path diversity with very low overhead. Simulation results show that in a typical setting, CodeCast yields a nearly 100 percent delivery ratio, as compared to a 94 percent delivery ratio by traditional multicast. More importantly, the overhead is reduced by as much as 50 percent

We develop algorithmic optimizations to improve the cache performance of four fundamental graph algorithms. We present a cache-oblivious implementation of the Floyd-Warshall algorithm for the fundamental graph problem of all-pairs shortest paths by relaxing some dependencies in the iterative version. We show that this implementation achieves the lower bound on processor-memory traffic of /spl Omega/(N/sup 3///spl radic/C), where N and C are the problem size and cache size, respectively. Experimental results show that this cache-oblivious implementation shows more than six times the improvement in real execution time over that of the iterative implementation with the usual row major data layout, on three state-of-the-art architectures. Second, we address Dijkstra's algorithm for the single-source shortest paths problem and Prim's algorithm for minimum spanning tree problem. For these algorithms, we demonstrate up to two times the improvement in real execution time by using a simple cache-friendly graph representation, namely adjacency arrays. Finally, we address the matching algorithm for bipartite graphs. We show performance improvements of two to three times in real execution time by using the technique of making the algorithm initially work on subproblems to generate a suboptimal solution and, then, solving the whole problem using the suboptimal solution as a starting point. Experimental results are shown for the Pentium III, UltraSPARC III, Alpha 21264, and MIPS R12000 machines.

In this study, we introduce the concept of a virtual ¿flea market¿ over a vehicular ad hoc network (VANET) called FleaNet. FleaNet customers express their demands/offers to buy/sell items via radio queries. These queries are opportunistically disseminated, exploiting the mobility of other customers, until a matching customer/vendor is found. We identify the key performance metrics, namely, query resolution latency, scalability, mobility, and churning, and evaluate their impact on performance using analytic and simulation models. The results show that FleaNet can function as an effective virtual marketplace.