5391500
A High-Throughput Overlay Multicast Infrastructure with Network Coding
Network coding has been recently proposed in information theory as a new dimension of the information multicast problem that helps achieve optimal transmission rate or cost. End hosts in overlay networks are natural candidates to perform network coding, due to its available computational capabilities. In this paper, we seek to bring theoretical advances in network coding to the practice of high-throughput multicast in overlay networks. We have completed the first real implementation of network coding in end hosts, as well as decentralized algorithms to construct the routing strategies and to perform random code assignment. Our experiences suggest that approaching maximum throughput with network coding is not only theoretically sound, but also practically promising. We also present a number of unique challenges in designing and realizing coded data dissemination, and corresponding solution techniques to address them.
9219226
iFlow: Middleware-assisted Rendezvous-based Information Access for Mobile Ad Hoc Applications
Due to node mobility and limitations on bandwidth availability in wireless channels, there exist unique challenges towards achieving efficient and effective information access in wireless ad hoc networks with mobile nodes. In this paper, we address two critical questions: (1) How may information be accessed with the highest degree of bandwidth efficiency? and (2) How should algorithms be designed so that node mobility contributes positively towards high performance and efficiency? We present iFlow, a middleware-based framework for bandwidth-efficient and delay-aware information access for mobile ad hoc applications. We present the case of information rendezvous, where the demands for information are satisfied by the supplies in a fully distributed fashion, across third-party nodes beyond information suppliers and consumers. Such rendezvous is achieved via controlled diffusion of information from the suppliers, matched by the gleaning process on the consumers. We validate our claims using simulation and experimental results.
14995802
Efficient and distributed computation of maximum multicast rates
The transmission of information within a data network is constrained by network topology and link capacities. In this paper, we study the fundamental upper bound of information multicast rates with these constraints, given the unique replicable and encodable property of information flows. Based on recent information theory advances in coded multicast rates, we are able to formulate the maximum multicast rate problem as a linear network optimization problem, assuming the general undirected network model. We then proceed to apply Lagrangian relaxation techniques to obtain (1) a necessary and sufficient condition for multicast rate feasibility, and (2) a subgradient solution for computing the maximum rate and the optimal routing strategy to achieve it. The condition we give is a generalization of the well-known conditions for the unicast and broadcast cases. Our subgradient solution takes advantage of the underlying network flow structure of the problem, and therefore outperforms general linear programming solving techniques. It also admits a natural intuitive interpretation, and is amenable to fully distributed implementations.
1327847
On achieving maximum multicast throughput in undirected networks
The transmission of information within a data network is constrained by the network topology and link capacities. In this paper, we study the fundamental upper bound of information dissemination rates with these constraints in undirected networks, given the unique replicable and encodable properties of information flows. Based on recent advances in network coding and classical modeling techniques in flow networks, we provide a natural linear programming formulation of the maximum multicast rate problem. By applying Lagrangian relaxation on the primal and the dual linear programs (LPs), respectively, we derive a) a necessary and sufficient condition characterizing multicast rate feasibility, and b) an efficient and distributed subgradient algorithm for computing the maximum multicast rate. We also extend our discussions to multiple communication sessions, as well as to overlay and ad hoc network models. Both our theoretical and simulation results conclude that, network coding may not be instrumental to achieve better maximum multicast rates in most cases; rather, it facilitates the design of significantly more efficient algorithms to achieve such optimality.
5878041
sFlow: towards resource-efficient and agile service federation in service overlay networks
Existing research work towards the composition of complex federated services has assumed that service requests and deliveries flow through a particular service path or tree. Here, we extend such a service model to a directed acyclic graph, allowing services to be delivered via parallel paths and interleaved with each other. Such an assumption of the service flow model has apparently introduced complexities towards the development of a distributed algorithm to federate existing services, as well as the provisioning of the required quality in the most resource-efficient fashion. To this end, we propose sFlow, a fully distributed algorithm to be executed on all service nodes, such that the federated service flow graph is resource efficient, performs well, and meets the demands of service consumers.
2459398
On increasing end-to-end throughput in wireless ad hoc networks
One of the main characteristics of wireless ad hoc networks is their node-centric broadcast nature of communication, leading to interferences and spatial contention between adjacent wireless links. Due to such interferences, pessimistic concerns have been recently raised with respect to the decreasing network capacity in wireless ad hoc networks when the number of nodes scales to several orders of magnitude higher. In this paper, we argue that in all cases of end-to-end data communications - including one-to-k unicast and multicast data dissemination as well as k-to-one data aggregation - the maximum achievable end-to-end data throughput (measured on the sources) heavily depends on the strategy of arranging the topology of transmission between sources and destinations, as well as possible per-node operations such as coding. An optimal strategy achieves better end-to-end throughput than an arbitrary one. We present theoretical studies and critical insights with respect to how these strategies may be designed so that end-to-end throughput may be increased
12665870
Robust statistical methods for securing wireless localization in sensor networks
Many sensor applications are being developed that require the location of wireless devices, and localization schemes have been developed to meet this need. However, as location-based services become more prevalent, the localization infrastructure will become the target of malicious attacks. These attacks will not be conventional security threats, but rather threats that adversely affect the ability of localization schemes to provide trustworthy location information. This paper identifies a list of attacks that are unique to localization algorithms. Since these attacks are diverse in nature, and there may be many unforeseen attacks that can bypass traditional security countermeasures, it is desirable to alter the underlying localization algorithms to be robust to intentionally corrupted measurements. In this paper, we develop robust statistical methods to make localization attack-tolerant. We examine two broad classes of localization: triangulation and RF-based fingerprinting methods. For triangulation-based localization, we propose an adaptive least squares and least median squares position estimator that has the computational advantages of least squares in the absence of attacks and is capable of switching to a robust mode when being attacked. We introduce robustness to fingerprinting localization through the use of a median-based distance metric. Finally, we evaluate our robust localization schemes under different threat conditions.
11054473
Applying array contraction to a sequence of DOALL loops
Efficient program execution on multiprocessor computers requires both sufficient parallelism and good data locality. Recent research found that, using a combination of loop shifting, loop fusion, and array contraction, one can reduce the memory required to execute a sequence of serial loops, thereby to improve the cache locality. This paper studies how to extend such a memory-reduction scheme to a sequence of DOALL loops, which are executed in parallel on multiprocessors. Two methods are proposed to overcome difficulties caused by loop-carried dependences. Data copy-in is performed to remove anti-dependences between different parallel threads, and computation duplication is performed to remove flow dependences. Experiments performed on a number of benchmark programs show that the proposed technique improves both cache locality and parallel execution speed for the DOALL loops. The scheme achieves an average speedup of 1.41 for 17 programs on a 4-processor SUN machine.
3705333
Rate-distortion optimal video summary generation
The need for video summarization originates primarily from a viewing time constraint. A shorter version of the original video sequence is desirable in a number of applications. Clearly, a shorter version is also necessary in applications where storage, communication bandwidth, and/or power are limited. The summarization process inevitably introduces distortion. The amount of summarization distortion is related to its "conciseness", or the number of frames available in the summary. If there are m frames in the original sequence and n frames in the summary, we define the summarization rate as m/n, to characterize this "conciseness". We also develop a new summarization distortion metric and formulate the summarization problem as a rate-distortion optimization problem. Optimal algorithms based on dynamic programming are presented and compared experimentally with heuristic algorithms. Practical constraints, like the maximum number of frames that can be skipped, are also considered in the formulation and solution of the problem.
10936659
Haplotype reconstruction from SNP fragments by minimum error correction
MOTIVATION
Haplotype reconstruction based on aligned single nucleotide polymorphism (SNP) fragments is to infer a pair of haplotypes from localized polymorphism data gathered through short genome fragment assembly. An important computational model of this problem is the minimum error correction (MEC) model, which has been mentioned in several literatures. The model retrieves a pair of haplotypes by correcting minimum number of SNPs in given genome fragments coming from an individual's DNA.


RESULTS
In the first part of this paper, an exact algorithm for the MEC model is presented. Owing to the NP-hardness of the MEC model, we also design a genetic algorithm (GA). The designed GA is intended to solve large size problems and has very good performance. The strength and weakness of the MEC model are shown using experimental results on real data and simulation data. In the second part of this paper, to improve the MEC model for haplotype reconstruction, a new computational model is proposed, which simultaneously employs genotype information of an individual in the process of SNP correction, and is called MEC with genotype information (shortly, MEC/GI). Computational results on extensive datasets show that the new model has much higher accuracy in haplotype reconstruction than the pure MEC model.
15151643
QMBF: a QoS-aware multicast routing protocol
Many multicast applications, such as video-on-demand and tele-education, desire quality of service (QoS) support from the underlying network. Recently, many QoS-based multicast protocols have been proposed to meet this requirement. However, few of them can achieve high success ratios while maintaining good scalability. In this paper, we propose a new QoS-aware multicast protocol based on a bounded flooding technique (QMBF). In this protocol, every network node maintains the knowledge of a local network cell (LNC) topology as well as QoS state information (collected from the bounded flooding messages). QMBF utilizes this knowledge to increase the probability and accuracy of finding a feasible branch which connects a new member to an existing multicast tree. The protocol exploits two approaches to find feasible branches: repeatedly computing partial feasible branches using the LNC information and searching multiple paths. The design of QMBF allows it to operate on top of any unicast routing protocol or cooperate with a QoS-based unicast routing protocol. Results obtained using NS-2 simulator demonstrate high success ratio for locating feasible branches for multicast paths.