IEEE Transactions on Parallel and Distributed Systems

PrePrint: Opportunistic Optical Hyperchannel and Its Distributed QoS Assuring Access Control

Light-trail is proposed as a candidate to carry IP traffic over wavelength division multiplexing (WDM) optical networks given its capability of enabling high speed provisioning and accommodating multi-granularity traffic. In a light-trail, the optical shutters at the start node and the end node are configured to be in OFF state and the optical shutters at the intermediate nodes are configured to be in ON state. Thus, an optical bus is formed allowing traffic multiplexing without the state change of any optical shutter. This, however, limits the system throughput and also makes it impossible to implement a fully distributed MAC protocol to assure QoS in a light-trail. With the recent development on ultrafast optical shutter, we propose an improved light-trail architecture, called opportunistic hyperchannel in this paper. In an opportunistic hyperchannel, an intermediate node can dynamically control its optical shutter which makes it possible to design a fully distributed QoS assuring MAC protocol. We then present a QoS assuring distributed dynamic scheduling protocol, namely, minSrcRR protocol, for opportunistic hyperchannels. Theoretical analyses on the effectiveness of the proposed QoS assuring protocol and the worst case delay bound are also derived in the paper. The simulation results quantitatively demonstrate the advantage of opportunistic hyperchannels and the effectiveness of minSrcRR protocol.

PrePrint: Group-Based Trust Management Scheme for Clustered Wireless Sensor Networks

Traditional trust management schemes developed for wired and wireless ad-hoc networks are not well-suited for sensor networks due to their higher consumption of resources such as memory and power. In this work, we propose a new lightweight Group-based Trust Management Scheme (GTMS) for wireless sensor networks which employs clustering. Our approach reduces the cost of trust evaluation. Also, theoretical as well as simulation results show that our scheme demands less memory, energy and communication overheads as compared to the current state-of-the-art trust management schemes and it is more suitable for large-scale sensor networks. Furthermore, GTMS also enables us to detect and prevent malicious, selfish and faulty nodes.

PrePrint: Building Ring-Like Overlays on Wireless Ad Hoc and Sensor Networks

In this paper, we discuss distributed algorithms to construct ring-like overlays over a subset of scattered nodes in a static, random wireless ad hoc and sensor network (WASN). A ring-like overlay consists of a unidirectional ring plus side-paths or loops, in which the given subset of nodes may appear multiple times. Different from a Hamiltonian cycle, a ring-like overlay is easier to construct and more efficient to operate. Yet, it can support many useful control operations in WASN such as mutual exclusion, clock synchronization, and cluster management. Compared with other topologies, a ring-like overlay allows conflict-free two-way communications, supports node ordering, and provides cost-free status feedbacks of operations. In this paper, we first present a distributed algorithm to construct a proximity-aware ring-like overlay in WASN. We then show optimization techniques to adapt the primitive overlays to meet the various application requirements.

PrePrint: How to Effectively Use Multiple Channels in Wireless Mesh Networks?

IEEE 802.11 is now widely used in Wireless Mesh Networks (WMNs). Many multi-channel MAC protocols are proposed to improve the spatial reuse in the network under the assumption that the transmissions on non-overlapping channels do not interfere with each other. Some joint routing and channel assignment algorithms are also designed to increase the network throughput based on the premise that we can switch between different channels freely. Although simulations show that great improvements on network throughput can be observed in both cases, two fundamental questions remain: (1) Can we really use multiple non-overlapping channels freely in wireless mesh networks? (2) If we can, what will be the cost when we switch channels dynamically and frequently? In this paper, by conducting extensive experiments on our testbed, we attempt to answer these questions. We find that in spite of interference between both overlapping and non-overlapping channels, we can still use multi-channel in mesh networks under certain conditions, but with care. We also show that the channel switching cost is actually very significant in WMNs. We recommend not to switch the channels too frequently when designing the channel assignment algorithms and those channel assignment algorithms selecting one channel for each packet are not really beneficial.

PrePrint: An Invisible Localization Attack to Internet Threat Monitors

Internet threat monitoring (ITM) systems have been deployed to detect widespread attacks on the Internet in recent years. However, the effectiveness of ITM systems critically depends on the confidentiality of the location of their monitors. If adversaries learn the monitor locations of an ITM system, they can bypass the monitors and focus on the uncovered IP address space without being detected. In this paper, we study a new class of attacks, the Invisible LOCalization (iLOC) attack. The iLOC attack can accurately and invisibly localize monitors of ITM systems. In the iLOC attack, the attacker launches low-rate port-scan traffic, encoded with a selected pseudo-noise code (PN-code), to targeted networks. While the secret PN-code is invisible to others, the attacker can accurately determine the existence of monitors in the targeted networks based on whether the PN-code is embedded in the report data queried from the data center of the ITM system. We formally analyze the impact of various parameters on attack effectiveness. We implement the iLOC attack and conduct the performance evaluation on a real-world ITM system to demonstrate the possibility of such attacks. We also conduct extensive simulations on the iLOC attack using real-world traces. Our data show that the iLOC attack can accurately identify monitors while being invisible to ITM systems. Finally, we present a set of guidelines to counteract the iLOC attack.

PrePrint: Parallel Genomic Alignments on the Cell Broadband Engine

Genomic alignments as a means to uncover evolutionary relationships are a fundamental tool in computational biology. There is considerable recent interest in using the Cell Broadband Engine, a heterogenous multicore chip that provides high performance, for biological applications. However, work in subfloat alignments so far has been limited to computing optimal alignment scores using quadratic space for the basic global/local alignment problem. In this paper, we present a comprehensive study of developing alignment algorithms on the Cell exploiting its thread and data level parallelism features. First, we develop a parallel implementation on the Cell that computes optimal alignments and adopts Hirschberg's linear space technique. The former is essential as merely computing optimal alignment scores is not useful, while the latter is needed to permit alignments of longer sequences. We then present Cell implementations of two advanced alignment techniques — spliced alignments and syntenic alignments. Spliced alignments are useful in aligning mRNA sequences with corresponding subfloat sequences to uncover gene structure. Syntenic alignments are used to discover conserved exons and other sequences between long subfloat sequences from different organisms. We present experimental results for these three types of alignments on 16 SPUs of the IBM QS20 dual-Cell blade system.

PrePrint: On Game Theoretic Peer Selection for Resilient Peer-to-Peer Media Streaming

Peer-to-peer (P2P) media streaming quickly emerges as an important application over the Internet. A plethora of approaches have been suggested and implemented to support P2P media streaming. In our study, we first classified existing approaches and studied their characteristics by looking at three important quantities: number of upstream peers (parents), number of downstream peers (children) and average number of links per peer. We find that in existing approaches, peers are assigned with a fixed number of parents without regard to their contributions, measured by the amount of outgoing bandwidths. Obviously, this is an undesirable arrangement as it leads to highly inefficient use of the P2P links. This observation motivates us to model the peer selection process as a cooperative game among peers. This results in a novel peer selection protocol such that the number of upstream peers of a peer is related to its outgoing bandwidth. Specifically, peers with larger outgoing bandwidth are given more parents, which makes them less vulnerable to peer dynamics. Simulation results show that the proposed protocol improves delivery ratio using similar number of links per peer, comparing with existing approaches in a wide range of settings.

PrePrint: Balancing Energy Consumption to Maximize Network Lifetime in Data-Gathering Sensor Networks

Unbalanced energy consumption is an inherent problem in wireless sensor networks characterized by multi-hop routing and many-to-one traffic pattern, and this uneven energy dissipation can significantly reduce the sensor network lifetime. In this paper, we study the problem of maximizing network lifetime through energy consumption balancing techniques for uniformly deployed data gathering sensor networks. We formulate the energy consumption balancing problem as an optimal transmitting data distribution problem by combining the ideas of corona-based network division and mixed-routing strategy together with data aggregation. We first propose a zone-based routing scheme that guarantees balanced energy consumption among nodes within each corona. We then design an offline centralized algorithm with time complexity $O(n)$ ($n$ is the number of coronas) to solve the transmitting data distribution problem aimed at balancing energy consumption across coronas. The approach for computing the optimal number of coronas in terms of maximizing network lifetime is also presented. Based on our mathematical model, an energy-balanced data gathering protocol (EBDG) is designed and the solution for extending EBDG to large-scale data gathering sensor networks is also presented. Simulation results demonstrate that EBDG can improve system lifetime by an order of magnitude compared with conventional multi-hop transmission scheme, direct transmission scheme and cluster-heads rotation scheme.

PrePrint: Priority Random Linear Codes for Distributed Storage Systems

Both peer-to-peer and sensor networks have the fundamental characteristics of node churn and failures. Peers in P2P networks are highly dynamic, whereas sensors are not dependable. As such, maintaining the persistence of periodically measured data in a scalable fashion has become a critical challenge in such systems, without the use of centralized servers. To better cope with node dynamics and failures, we propose priority random linear codes, as well as their affiliated predistribution protocols, to maintain measurement data in different priorities, such that critical data have a higher opportunity to survive node failures than data of less importance. A salient feature of priority random linear codes is the ability to partially recover more important subsets of the original data with higher priorities, when it is not feasible to recover all of them due to node dynamics. We present extensive analytical and experimental results to show the effectiveness of priority random linear codes.

PrePrint: Advance Reservation and Scheduling for Bulk Transfers in Research Networks

Data-intensive e-science collaborations often require the transfer of large files with predictable performance. To meet this need, we design novel admission control and scheduling algorithms for bulk data transfer in research networks for e-science. Due to their small sizes, the research networks can afford a centralized resource management platform. In our design, each bulk transfer job request, which can be made in advance to the central network controller, specifies a start time and an end time. If admitted, the network guarantees to complete the transfer before the end time. However, there is flexibility in how the actual transfer is carried out, that is, in the bandwidth assignment on each allowed path of the job on each time interval, and it is up to the scheduling algorithm to decide this. To improve the network resource utilization or lower the job rejection ratio, the network controller solves optimization problems in making admission control and scheduling decisions. Our design combines the following elements into a cohesive optimization-based framework: advance reservations, multi-path routing, and bandwidth reassignment via periodic re-optimization. We evaluate our algorithm in terms of both network efficiency and the performance level of individual transfer. We also evaluate the feasibility of our scheme by studying the algorithm execution time.

PrePrint: Leveraging Identity-Based Cryptography for Node ID Assignment in Structured P2P Systems

Structured peer-to-peer systems have grown enormously because of their scalability, efficiency and reliability. These systems assign a unique identifier to each user and object. However, current assignment schemes allow an adversary to carefully select user IDs and/or simultaneously obtain many pseudo-identities—leading ultimately to an ability to disrupt the P2P system in very targeted (and dangerous) ways. In this paper, we propose novel ID assignment protocols based on identity-based cryptography. This approach permits the acquisition of node IDs to be tightly regulated without many of the complexities and costs associated with traditional certificate solutions. We broadly consider the security requirements of ID assignment and present three protocols representing distinct threat and trust models. A detailed empirical study of the protocols is given. Our analysis shows that the cost of our identity-based protocols is nominal, and that the associated identity services can scale to millions of users using a limited number of servers.

PrePrint: Reliable and Energy Efficient Routing for Static Wireless Ad Hoc Networks with Unreliable Links

Energy efficient routing and power control techniques in wireless ad hoc networks have drawn considerable research interests recently. In this paper, we address the problem of energy efficient reliable routing for wireless ad hoc networks in the presence of unreliable communication links or devices or lossy wireless link layers by integrating the power control techniques into the energy efficient routing. We consider both the case when the link layer implements a perfect reliability and the case when the reliability is implemented through the transportation layer, e.g., TCP. We study the energy efficient unicast and multicast when the links are unreliable. Subsequently, we study how to perform power control (thus, controlling the reliability of each communication link) such that the unicast routings use the least power when the communication links are unreliable while the power used by multicast is close to optimum. Extensive simulations have been conducted to study the power consumption, the end-to-end delay, and the network throughput of our proposed protocols compared with existing protocols.

IEEE Transactions on Parallel and Distributed Systems - January 2009 (Vol. 20, No. 1)

IEEE Transactions on Parallel and Distributed Systems

PrePrint: Enhancing the Schedulability of Real-Time Heterogeneous Network of Workstations (NOWs)

This paper proposes a Real-Time Duplication Based Algorithm (RT-DBA) for scheduling precedence related periodic tasks with hard deadlines on NoWs. We have utilized selective subtask duplication that enables some tasks to have earlier start times, which enables additional tasks (and hence task sets) to finish before their deadlines, thereby increasing the schedulability of a real-time application . We strongly believe that duplication can be used as a tool for obtaining a better quality of service (QoS) from the real-time heterogeneous system and is our major contribution. We have taken both the computation as well as the communication heterogeneities into account while modeling such a system. Both data and control dependencies between the tasks have also been considered. Our algorithm exhibits scalability, fully exploit the underlying parallelism, and is capable of scheduling an application, even if the available number of processors is less than the required number of processors. Based on extensive simulation studies, we observe that RT-DBA offers enhanced success ratio as compared to other scheduling schemes when communication is a dominant factor.

PrePrint: Movement-Assisted Connectivity Restoration in Wireless Sensor and Actor Networks

Recent years have witnessed a growing interest in applications of wireless sensor and actor networks (WSANs). In these applications, a set of mobile actor nodes are deployed in addition to sensors in order to collect sensors' data and perform specific tasks in response to detected events/objects. In most scenarios actors have to respond collectively which requires an inter-actor coordination. Therefore, maintaining a connected inter-actor network is critical to the effectiveness of WSANs. However, WSANs often operate unattended in harsh environments where actors can easily fail or get damaged. An actor failure may lead to partitioning the inter-actor network and thus hinder the fulfillment of the application requirements. In this paper we present DARA; a Distributed Actor Recovery Algorithm, which opts to efficiently restore the connectivity of the inter-actor network that has been affected by the failure of an actor. Two variants of the algorithm are developed to address 1 and 2-connectivity requirements. The idea is to identify the least set of actors that should be repositioned in order to re-establish a particular level of connectivity. DARA strives to localize the scope of the recovery process and minimize the movement overhead imposed on the involved actors. The effectiveness of DARA is validated through simulation experiments.

PrePrint: A Class of Cross-Layer Optimization Algorithms for Performance and Complexity Trade-offs in Wireless Networks

In this paper, we solve the problem of a joint optimal design of congestion control and wireless MAC-layer scheduling using a column generation approach with imperfect scheduling. We point out that the general subgradient algorithm has difficulty in recovering the time-share variables and experiences slower convergence. We first propose a two-timescale algorithm that can recover the optimal time-share values. Most existing algorithms have a component, called global scheduling, which is usually NP-hard. We apply imperfect scheduling and prove that if the imperfect scheduling achieves an approximation ratio $\rho$, then our algorithm converges to a sub-optimum of the overall problem with the same approximation ratio. By combining the idea of column generation and the two-timescale algorithm, we derive a family of algorithms that allow us to reduce the number of times the global scheduling is needed.

PrePrint: Developing a Consistent Domain-Oriented Distributed Object Service

This paper presents a new algorithm for a reconfigurable distributed domain-oriented atomic object service, called DO-RAMBO, which stands for Domain-Oriented Reconfigurable Atomic Memory for Basic Objects. This service is suitable for inclusion as a middleware system service for distributed applications requiring atomic read/write data. The implementation substantially extends and refines the abstract RAMBO algorithm of Lynch and Shvartsman that supports individual atomic objects. In this paper domains are introduced to allow the users to group related atomic objects. The new implementation manages configurations on the basis of domains, significantly improving the utility and the performance of the resulting service. DO-RAMBO guarantees consistency under asynchrony, message loss, node crashes, new node arrivals, and node departures. We present the formal algorithm development for DO-RAMBO and give analytical and empirical results that illustrate the benefit of the new approach.

PrePrint: Delay Asymptotics and Scalability for Peer-to-Peer Live Streaming

A large number of peer-to-peer streaming systems has been proposed and deployed in recent years. Yet, there is no clear understanding of how these systems scale and how multi-path and multihop transmission, properties of all recent systems, affect the quality experienced by the peers. In this paper we present an analytical study that considers the relationship between delay and loss for general overlays: we study the trade-off between the playback delay and the probability of missing a packet and we derive bounds on the scalability of the systems. We present an exact model of push-based overlays and show that the bounds hold under diverse conditions: in the presence of errors, under node churn, and when using forward error correction and various retransmission schemes.

PrePrint: Securing Structured Overlays Against Identity Attacks

Structured overlay networks can greatly simplify data storage and management for a variety of distributed applications. Despite their attractive features, these overlays remain vulnerable to the Identity attack, where malicious nodes assume control of application components by intercepting and hijacking key-based routing (KBR) requests. Attackers can assume arbitrary application roles such as storage node for a given file, or return falsified contents of an online shopper's shopping cart. In this paper, we define a generalized form of the Identity attack, and propose a light-weight detection and tracking system that protects applications by redirecting traffic away from attackers. We describe how this attack can be amplified by a Sybil or Eclipse attack, and analyze the costs of performing such an attack. Finally, we present measurements of a deployed overlay that show our techniques to be significantly more light-weight than prior techniques, and highly effective at detecting and avoiding both single node and colluding attacks under a variety of conditions.

PrePrint: Context-Based Operational Transformation in Distributed Collaborative Editing Systems

Operational Transformation (OT) is a consistency maintenance technique for collaborative editing systems - a special class of distributed applications for supporting human-computer-human interaction and collaboration over communication networks. The theory of causality has been the foundation of all prior OT systems, but it is inadequate to meet essential OT requirements in functionality and correctness. In this paper, we analyze the limitation of the causality theory, propose a novel theory of operation context as the new foundation for OT systems, and present a new OT algorithm - COT (Context-based OT), which provides uniformed and efficient solutions to both consistency maintenance and undo problems. The COT algorithm has been implemented and used for supporting a range of novel collaborative applications. The context theory and context vectors are potentially applicable to other distributed computing applications

PrePrint: Range-Free Localization Algorithm using Expected Hop Progress in Wireless Sensor Networks

Localization algorithm continues to be an important and challenging topic in today's wireless sensor networks (WSNs). In this paper, a novel range-free localization algorithm using expected hop progress (LAEP) to predict the location of any sensor in a WSN is proposed. This algorithm is based on an accurate analysis of hop progress in a WSN with randomly deployed sensors and arbitrary node density. By deriving the expected hop progress from a network model for WSNs in terms of network parameters, the distance between any pair of sensors can be accurately computed. Since the distance estimation is a key issue in localization systems for WSNs, the proposed range-free localization algorithm LAEP achieves better performance and less communication overhead as compared to some existent schemes like DV-Hop and RAW. In addition, we study the effect of anchor placement on the algorithm performance by deriving the corresponding mean position error range. Extensive simulations are performed and the results are observed to be in good agreement with the theoretical analysis.

PrePrint: Fat H-Tree: A Cost-Efficient Tree-Based On-Chip Network

The topological explorations of on-chip networks are important for efficiently using their enormous wire resources for low-latency and high-throughput communications using a modest silicon budget. In this paper, we propose a novel tree-based interconnection network called Fat H-Tree that meets these requirements. Fat H-Tree provides a torus structure by combining two folded H-Tree networks, and is an attractive alternative to tree-based networks, such as the Fat Trees in a microarchitecture domain. We also propose three deadlock-free routing schemes for Fat H-Tree. The performance, network logic area, wire resource, and energy consumption of Fat H-Tree are compared with other tree-based topologies, based on a typical implementation of on-chip routers synthesized with a 90nm standard cell library. The results show that 1) a Fat H-Tree outperforms a Fat Tree with two upward and four downward connections in terms of the throughput and average hop count; 2) a Fat H-Tree requires 19.8%-27.8% smaller network logic area than the Fat Tree; 3) a Fat H-Tree consumes slightly less energy than the Fat Tree does; 4) a Fat H-Tree uses slightly more wire resources than the Fat Tree, but the current process technology can provide sufficient wire resources for implementing Fat H-Tree based on-chip networks.

PrePrint: A Distributed Stream Query Optimization Framework Through Integrated Planning and Deployment

This paper addresses the problem of optimizing multiple distributed stream queries that are executing simultaneously in distributed data stream systems. We argue that the static query optimization approach of "plan, then deployment" is inadequate for handling distributed queries involving multiple streams and node dynamics faced in distributed data stream systems and applications. Thus, the selection of an optimal execution plan in such dynamic and networked computing systems must consider operator ordering, reuse, network placement, and search space reduction. We propose to use hierarchical network partitions to exploit various opportunities for operator level reuse while utilizing network characteristics to maintain a manageable search space during query planning and deployment. We develop top-down, bottom-up and hybrid algorithms for exploiting operator-level reuse through hierarchical network partitions. Formal analysis is presented to establish the bounds on the search-space and sub-optimality of our algorithms. We have implemented our algorithms in the IFLOW [23] system, an adaptive distributed stream management system. Through simulations and experiments using a prototype deployed on Emulab [3] we demonstrate the effectiveness of our framework and our algorithms.

PrePrint: FTPA: Supporting Fault Tolerant Parallel Computing through Parallel Recomputing

As the size of large-scale computer systems increases, their mean-time-between-failures are becoming significantly shorter than the execution time of any current scientific applications. To complete the execution of scientific applications, they must tolerate hardware failures. Conventional rollbackrecovery protocols redo the computation of the crashed process since the last checkpoint on a single processor. As a result, the recovery time of all protocols is no less than the time between the last checkpoint and the crash. In this paper we propose a new application-level fault-tolerant approach for parallel applications called Fault-Tolerant Parallel Algorithm (FTPA) which provides fast self-recovery. When failstop failures occur and are detected, all surviving processes recompute the workload of failed processes in parallel. FTPA, however, requires the user to be involved in fault tolerance. In order to ease the FTPA implementation, we developed GiFT (Get it Fault-Tolerant), a source-to-source precompiler tool to automate the FTPA implementation. We evaluate the performance of FTPA with parallel matrix multiplication and five kernels of NAS Parallel Benchmarks on a cluster system with 1024 CPUs. The experimental results show that the performance of FTPA is better than the performance of the traditional checkpointing approach.

PrePrint: An Adaptive Partitioning Scheme for Sleep Scheduling and Topology Control in Wireless Sensor Networks

This paper presents an adaptive partitioning scheme of sensor networks for node scheduling and topology control with the aim of reducing energy consumption. Our scheme partitions sensors into groups such that a connected backbone network can be maintained by keeping only one arbitrary node from each group in active status while putting others to sleep. Unlike previous approaches that partition nodes geographically, our scheme is based on the measured connectivity between pairwise nodes and does not depend on nodes' locations. In this paper, we formulate node scheduling with topology control as a constrained optimal graph partition problem, which is NP-hard, and propose a Connectivity based Partition Approach (CPA), which is a distributed heuristic algorithm, to approximate a good solution. We also propose a probability-based CPA algorithm to further save energy. CPA can ensure K-vertex connectivity of the backbone network, which achieves the trade-off between saving energy and preserving network quality. Moreover, simulation results show that CPA outperforms other approaches in complex environments where the ideal radio propagation model does not hold.

PrePrint: Enforcing Minimum-Cost Multicast Routing Against Selfish Information Flows

We study multicast in a non-cooperative environment where information flows selfishly route themselves through the cheapest paths available. The main challenge is to enforce such selfish multicast flows to stabilize at a socially optimal operating point incurring minimum total edge cost, through appropriate cost allocation and other economic measures, with replicable and encodable properties of information flows considered. We show that known cost allocation schemes are not sufficient. We provide a shadow-price based cost allocation for networks without capacity limits, and show it enforces minimum-cost multicast. This improves previous result where a 2-approximate multicast flow is enforced. For capacitied networks, computing cost allocation by ignoring edge capacities will not yield correct results. We show that an edge tax scheme can be combined with a cost allocation to strictly enforce optimal multicast flows in this more realistic case. If taxes are not desirable, they can be returned to flows while maintaining weak enforcement of the optimal flow. We relate the taxes to VCG payment schemes and discuss an efficient primal-dual algorithm that simultaneously computes the taxes, the cost allocation, and the optimal multicast flow, with potential of fully distributed implementations.

PrePrint: Efficient and Scalable Hardware-Based Multicast in Fat-Tree Networks

This article presents an efficient and scalable mechanism to overcome the limitations of collective communication in fat-tree interconnection networks in the presence of faults. Considering that current trends in supercomputing are moving toward massively parallel computers, with many thousands of components, reliability becomes a challenge. In such scenario, fat-tree networks that provide hardware support for collective communication suffer from serious performance degradation due to the presence of, even, a single faulty node. This paper describes a new mechanism to provide high-performance collective communication in such situations. The feasibility of the proposed technique is formally demonstrated. We present the design of a new hardware-based routing algorithm for multicast, that is at the base of our proposal. The proposed mechanism is implemented and experimentally evaluated. Our experimental results show that hardware-based multicast trees provide an efficient and scalable solution for collective communication in fat-tree networks, significantly outperforming traditional solutions.

PrePrint: A Parameterized Approach to Spam-Resilient Link Analysis of the Web

Link-based analysis of the Web provides the basis for many important applications – like Web search, Web-based data mining, and Web page categorization – that bring order to the massive amount of distributed Web content. Due to the overwhelming reliance on these important applications, there is a rise in efforts to manipulate (or spam) the link structure of the Web. In this manuscript, we present a parameterized framework for link analysis of the Web that promotes spam-resilience through a source-centric view of the Web. We provide a rigorous study of the set of critical parameters that can impact source-centric link analysis, and propose the novel notion of influence throttling for countering the influence of link-based manipulation. Through formal analysis and a large-scale experimental study, we show how different parameter settings may impact the time complexity, stability, and spam-resilience of Web link analysis. Concretely, we find that the source-centric model supports more effective and robust rankings in comparison with existing Web algorithms such as PageRank.

PrePrint: The Effects of Stitching Orders in Patch-and-Stitch WSN Localization Algorithms

A "patch-and-stitch" localization algorithm divides the network into small overlapping subregions. Typically each subregion consists of a node and all or some of its neighbors. For each subregion, the algorithm builds a local map, called a patch, which is actually an embedding of the nodes it spans in a relative coordinate system. Finally, the algorithm stitches those patches to form a single global map. In a patch-and-stitch algorithm, the stitching order makes an influence on both the performance and the complexity of the algorithm. In this paper, we present a formal framework to deal with stitching orders in patch-and-stitch localization algorithms. In our framework, the stitching order is determined by a stitching scheme and the stitching scheme consists of a stitching policy and a potential function. The potential function is to predict how well a patch will be stitched if patches are stitched according to a given partial order. The stitching policy is a mechanism that determines the stitching order based on the predictions by the potential function. We present various stitching schemes and evaluate them though simulations.

PrePrint: On the Performance of a Dual-Objective Optimization Model for Workflow Applications on Grid Platforms

In an attempt to exploit a diverse set of resources in grids efficiently, numerous assays in resource management, particularly scheduling, have been made. The primary objective of these efforts is the minimization of application completion time; however, they tend to achieve this objective at the expense of redundant resource usage. This paper investigates the problem of scheduling workflow applications on grids and presents a novel scheduling algorithm for the solution of this problem. Our algorithm performs the scheduling by accounting for both completion time and resource usage—dual objectives. Since the performance of grid resources changes dynamically and the accurate estimation of their performance is very difficult—our algorithm incorporates rescheduling to deal with unforeseen performance fluctuations effectively. The paper provides a comparative evaluation study conducted by using an extensive set of experiments. The study demonstrates that the proposed algorithm delivers promising performance in three respects: completion time, resource utilization, and robustness to resource-performance fluctuations.

PrePrint: Prefetching with Helper Threads for Loosely-Coupled Multiprocessor Systems

This paper presents a helper thread prefetching scheme that is designed to work on loosely-coupled processors, such as in a standard chip multiprocessor (CMP) system or an intelligent memory system. Loosely-coupled processors have an advantage in that those resources, such as processor and L1 cache resources, are not contended by the application and helper threads, hence preserving the speed of the application. However, inter-processor communication is expensive in such a system. We present techniques to alleviate this. Our approach exploits large loop-based code regions and is based on a new synchronization mechanism between the application and helper threads. This mechanism precisely controls how far ahead the execution of the helper thread can be with respect to the application thread. We found that this is important in ensuring prefetching timeliness and avoiding cache pollution. To demonstrate that prefetching in a loosely-coupled system can be done effectively, we evaluate our prefetching by simulating a standard, unmodified CMP system, and an intelligent memory system where a simple processor in memory executes the helper thread.

PrePrint: Asynchronous Corona Training Protocols in Wireless Sensor and Actor Networks

Scalable energy-efficient training protocols are proposed for wireless networks consisting of sensors and a single actor, where the sensors are initially anonymous and unaware of their location. The protocols are based on an intuitive coordinate system imposed onto the deployment area which partitions the sensors into clusters. The protocols are asynchronous, in the sense that the sensors wake up for the first time at random, then alternate between sleep and awake periods both of fixed length, and no explicit synchronization is performed between them and the actor. Theoretical properties are stated under which the training of all the sensors is possible. Moreover, both a worst-case and an average case analysis of the performance, as well as an experimental evaluation, are presented showing that the protocols are lightweight and flexible.

PrePrint: Full Information Lookups for Peer-to-Peer Overlays

Most peer-to-peer lookup schemes keep a small amount of routing state per node, typically logarithmic in the number of overlay nodes. This design assumes that routing information at each member node must be kept small, so that the bookkeeping required to respond to system membership changes is also small, given that aggressive membership dynamics are expected. As a consequence, lookups have high latency as each lookup requires contacting several nodes in sequence. In this paper, we question these assumptions by presenting a peer-to-peer routing algorithm with small lookup paths. Our algorithm, called "OneHop", maintains full information about the system membership at each node, routing in a single hop whenever that information is up-to-date, and in a small number of hops otherwise. We show how to disseminate information about membership changes quickly enough so that nodes maintain accurate complete membership information. We also present analytic bandwidth requirements for our scheme that demonstrate it could be deployed in systems with hundreds of thousands of nodes and high churn. We validate our analytic model using a simulated environment and a real implementation. Our results confirm that OneHop is able to achieve high efficiency, reaching the correct node directly 99% of the time.

PrePrint: A Faithful Distributed Mechanism for Sharing the Cost of Multicast Transmissions

The problem of sharing the cost of multicast transmissions was studied in the past and two mechanisms, Marginal Cost (MC) and Shapley Value (SH), were proposed to solve it. Although both of them are strategyproof mechanisms, the distributed protocols implementing them are susceptible to manipulation by autonomous nodes. We propose a distributed Shapley Value mechanism in which the participating nodes do not have incentives to deviate from the mechanism specifications. We show that the proposed mechanism is a faithful implementation of the Shapley Value mechanism. We experimentally investigate the performance of the existing and the proposed cost sharing mechanisms by implementing and deploying them on PlanetLab. We compare the execution time of MC and SH mechanisms for the Tamper-Proof and Autonomous Node models. We also study the convergence and scalability of the mechanisms by varying the number of nodes and the number of users per node. We show that the MC mechanisms generate a smaller revenue compared to the SH mechanisms and thus they are not attractive to the content provider. We also show that increasing the number of users per node is beneficial for the systems implementing the SH mechanisms from both computational as well as economic perspectives.

PrePrint: An In-Network Querying Framework for Wireless Sensor Networks

In contrast to traditional wireless sensor network (WSN) applications that perform only data collection and aggregation, new generation of information processing applications require in-network information storage and querying. Due to the resource limitations of WSNs, it is challenging to implement in-network querying in a distributed, lightweight, resilient, and energy-efficient manner. We address these challenges by exploiting location information and geometry of the network and propose an in-network querying framework, namely the Distributed Quad-Tree(DQT). DQT is distance-sensitive for querying of an event: the cost of answering a query for an event is at most 2√2 of the distance "d" to the event. DQT construction is local and does not require any communication. Moreover, due to its minimalist infrastructure and stateless nature, DQT shows graceful resilience to node failures and topology changes. Since event-based querying is inherently limited to the anticipated types of inquiries, we further extend our framework to achieve complex range-based querying. To this end, we use a decentralized multi-resolution algorithm, that is optimal with respect to least square errors. Our analysis and experiments show that our framework achieves distance-sensitivity and resiliency for event-based querying, as well as greatly reducing the cost of complex range querying.

PrePrint: A Unified Analytic Framework Based on Minimum Scan Statistics for Wireless Ad Hoc and Sensor Networks

Due to limitations on transmission power of wireless devices, areas with sparse nodes are decisive to some extreme properties of network topology. In this paper, we assume wireless ad hoc and sensor networks are represented by uniform point processes or Poisson point processes. Asymptotic analyses based on minimum scan statistics which are the minimum number of nodes that can be covered by a copy of some convex region are given for some crucial network properties, including coverage of wireless sensor networks, connectivity of wireless ad hoc networks, the largest edge length of geometric structures, and local-minimum-free geographic routing protocols. First, we derive explicit formulas of minimum scan statistics. Then, by taking the transmission radius as a major parameter, our results are applied to various network problems. Compared with related works in literature, this work offers a unified approach to solve various problems and reveals the evolution of network topology. In addition, boundary effects are thoroughly handled.

PrePrint: Complete Redundancy Removal for Packet Classifiers in TCAMs

In this paper, for the first time, we give a necessary and sufficient condition for identifying all redundant rules in a packet classifier. Based on this condition, we categorize redundant rules into upward redundant rules and downward redundant rules. Second, we present two algorithms for detecting and removing the two types of redundant rules respectively. Third, we formally prove that the resulting packet classifiers have no redundant rules after running the two algorithms. Last, we conduct extensive experiments on both real-life and synthetic packet classifiers. The experimental results show that our redundancy removal algorithms are both effective and efficient.

PrePrint: Recording Process Documentation for Provenance

Scientific and business communities are adopting large scale distributed systems as a means to solve a wide range of resource intensive tasks. These communities also have requirements in terms of provenance. We define the provenance of a result produced by a distributed system as the process that led to that result. This paper describes a protocol for recording documentation of a distributed system's execution. The distributed protocol guarantees that documentation with characteristics suitable for accurately determining the provenance of results is recorded. These characteristics are confirmed through a number of proofs based on an abstract state machine formalisation.

PrePrint: Building Small-World Peer-to-Peer Networks Based on Hierarchical Structures

Small-world (SW) networks possess two properties, namely low diameter and high clustering coefficient, that are often desired by large-scale peer-to-peer networks. Prior studies have shown that the construction of an SW network can be based on a d-regular graph, and each node in the graph maintains d local neighbors and a small constant number of long-distance contacts. In this paper, we present a novel navigable SW network based on a hierarchical model. Compared to previous efforts, the novelty of our study presents (i) that our network construction based on a hierarchical model is decentralized, (ii) that routing a message between any two nodes in our SW network takes logarithmic hopcount in expectation, (iii) that our SW network has high cluster coefficient, and (iv) that the performance of our proposal is mathematically provable. We support the performance of our proposal in this study through rigorous, thorough performance analysis and extensive simulations.

PrePrint: Replication-Based Fault-Tolerance For MPI Applications

As computational clusters increase in size, their mean-time-to-failure reduces drastically. Typically, checkpointing is used to minimize the loss of computation. Most checkpointing techniques, however, require central storage for storing checkpoints. This results in a bottleneck and severely limits the scalability of checkpointing, while also proving to be too expensive for dedicated checkpointing networks and storage systems. We propose a scalable replication-based MPI checkpointing facility. Our reference implementation is based on LAM/MPI, however, it is directly applicable to any MPI implementation. We extend the existing state of fault-tolerant MPI with asynchronous replication, eliminating the need for central or network storage. We evaluate centralized storage, a Sun X4500-based solution, an EMC SAN, and the Ibrix commercial parallel file system and show that they are not scalable, particularly after 64 CPUs. We demonstrate the low overhead of our checkpointing and replication scheme with the NAS Parallel Benchmarks and the High Performance LINPACK benchmark with tests up to 256 nodes while demonstrating that checkpointing and replication can be achieved with much lower overhead than that provided by current techniques. Finally, we show that the monetary cost of our solution is as low as 25% of that of a typical SAN/parallel file system-equipped storage system.

PrePrint: SORD: A Fault-Resilient Service Overlay for MediaPorts Resource Discovery

This paper proposes a new, fault-resilient service overlay for MediaPorts resource discovery that allows services to be efficiently and accurately located. MediaPorts are network side functions used in the path between the source (media server) and the sink (media client). MediaPorts enable the adaptation of media content by providing value-added services such as caching, synchronization, and special routing functions. Our new approach addresses the problems of inefficiency and large message overhead, both typical of traditional approaches to resource discovery. The approach is based on a widely studied family of chordal rings, called the optimal chordal ring. Our solution is based on the types of services offered and also on the geographical locations of nodes. Extensive simulation results are presented to validate the effectiveness of the new approach, when compared to several other service-discovery solutions.

PrePrint: Fei Teng 64 Stream Processing System: Architecture, Compiler, and Programming

Stream architecture is a novel microprocessor architecture with wide application potential. It is critical to study how to use the stream architecture to accelerate scientific computing programs. However, existing stream processors and stream programming languages are not designed for scientific computing. To address this issue, we design and implement a 64-bit stream processor, Fei Teng 64 (FT64), which has a peak performance of 16GFLOPS. FT64 supports two kinds of communications, message passing and stream communications, based on which, an interconnection architecture is designed for FT64-based high performance computer. This high performance computer contains multiply modules, with each module containing eight FT64s. We also design a novel stream programming language, Stream FORTRAN95 (SF95), together with the compiler, SF95Compiler, so as to facilitate the development of scientific applications. We test nine typical scientific application kernels on our FT64 platform to evaluate this design. The results demonstrate the effectiveness and efficiency of FT64 and its compiler for scientific computing.

PrePrint: A Polynomial Time Solution to Minimum Forwarding Set Problem in Wireless Networks under Unit Disk Coverage Model

Network-wide broadcast (simply broadcast) is a frequently used operation in wireless ad hoc networks. One promising practical approach for energy efficient broadcast is to use localized algorithms to minimize the number of nodes involved in the propagation of the broadcast messages. In this context, the minimum forwarding set problem (MFSP) (also known as multi-point relay (MPR) problem) has received a considerable attention in the research community. Even though the general form of the problem is shown to be NP-complete, the complexity of the problem has not been known under the practical application context of ad hoc networks. In this paper, we present a polynomial time algorithm to solve the MFSP problem for wireless network under unit disk coverage model. We prove the existence of some geometrical properties for the problem and then propose a polynomial time algorithm to build an optimal solution based on these properties. To the best of our knowledge, our algorithm is the first polynomial time solution to the MFSP problem under the unit disk coverage model. We believe that the work presented in this paper will have an impact on the design and development of new algorithms for several wireless network applications including energy efficient multicast, broadcast, and topology control protocols for wireless ad hoc networks and sensor networks.

PrePrint: The Proportional-Share Allocation Market for Computational Resources

We study the problem of allocating shared resources, such as bandwidth in computer networks and computational resources in shared clusters, among multiple users by the proportional-share market mechanism. Under this mechanism, each user partitions his budget among the multiple resources and receives a fraction of each resource proportional to his bid. We first formulate the resource allocation game under the proportional-share mechanism and study the efficiency and fairness of the equilibrium in this game. We present analytic and simulation results demonstrating that the proportional-share mechanism achieves a reasonable balance of high degrees of efficiency and fairness at the equilibrium.

PrePrint: Efficient and Reliable Lock-Free Memory Reclamation Based on Reference Counting

We present an efficient and practical lock-free method for semi-automatic (application-guided) memory reclamation based on reference counting, aimed for use with arbitrary lock-free dynamic data structures. The method guarantees the safety of local as well as global references, supports arbitrary memory reuse, uses atomic primitives that are available in modern computer systems, and provides an upper bound on the amount of memory waiting to be reclaimed. To the best of our knowledge, this is the first lock-free method that provides all of these properties. We provide analytical and experimental study of the method. The experiments conducted have shown that the method can also provide significant performance improvements for lock-free algorithms of dynamic data structures that require strong memory management.

PrePrint: Design and Verification of Enhanced Secure Localization Scheme in Wireless Sensor Networks

In this paper, we focus on the need for secure and efficient localization for wireless sensor networks in adversarial settings. An attack-resistant and efficient localization scheme is developed, which extends the scheme proposed in [1].The method offers strong defense against not only distance reduction attacks, but also distance enlargement attacks. Furthermore, our method does not employ any device-dependent variables, hence yields more accurate localization. An attack-driven model is also specified using Petri net. It provides a formal method for the verification of our scheme when considering distance enlargement attacks. The state analysis shows that the potential insecure states are unreachable, implying the model can offer strong defense against these attacks. To the best of our knowledge, it is the first time that the Petri net has been introduced to validate security scheme for wireless sensor networks in the literature.

PrePrint: QoS-Aware Shared Component Composition for Distributed Stream Processing Systems

Many emerging on-line data analysis applications require applying continuous query operations such as correlation, aggregation, and filtering to data streams in real-time. Distributed stream processing systems allow in-network stream processing to achieve better scalability and quality-of-service (QoS) provision. In this paper we present Synergy, a novel distributed stream processing middleware that provides automatic sharing- aware component composition capability. Synergy enables efficient reuse of both result streams and processing components, while composing distributed stream processing applications with QoS demands. It provides a set of fully distributed algorithms to discover and evaluate the reusability of available result streams and processing components when instantiating new stream applications. Specifically, Synergy performs QoS impact projection to examine whether the shared processing can cause QoS violations on currently running applications. The QoS impact projection algorithm can handle different types of streams including both regular traffic and bursty traffic. If no existing processing components can be reused, Synergy dynamically deploys new components at strategic locations to satisfy new application requests. We have implemented a prototype of the Synergy middleware and evaluated its performance on both PlanetLab and simulation testbeds. The experimental results show that Synergy can achieve much better resource utilization and QoS provisioning than previously proposed schemes, by judiciously sharing streams and components during application composition.

PrePrint: Multipath Dissemination in Regular Mesh Topologies

Mesh topologies are important for large-scale, peer-to-peer, systems that use low-power transceivers. However, the Quality of Service (QoS) in such systems is known to decrease as the scale increases. We present a scalable approach for dissemination that improves the QoS. Our method exploits all the shortest paths between a pair of nodes. We characterize the set of shortest paths between a pair of nodes in regular mesh topologies. Despite the presence of multiple shortest paths in a system, we show that these paths cannot be exploited by spreading the messages over the paths in a straightforward manner. The results in this paper show that nodes on one of the paths will always handle more messages than the nodes on other paths when the messages are spread in a straightforward manner. By exploiting our characterization of the set shortest paths, we derive rules for optimally spreading messages over all the available paths. By modeling the multihop propagation in the mesh topology as a multistage queuing network, we present simulation results from a variety of scenarios that include link failures and propagation irregularities, to reflect real-world characteristics. Our method achieves improved QoS in all these scenarios.

PrePrint: Using Parallel DRAM to Scale Router Buffers

This paper addresses the design of high performance buffers Internet routers. The buffers are typically implemented using a combination of SRAM and DRAM technologies in order to simultaneously meet the routers' high speed and capacity requirements. The major challenge in designing routers' buffers is to maintain multiple flow queues in the memory, unlike a computer's memories. The major objective is to minimize the use of the expensive but fast SRAM while providing acceptable delay guarantees to packets. In this paper, we first investigate hybrid SRAM/DRAM solutions proposed in the past. We show that one of their architectural limitations is that the required SRAM size grows linearly with the number of flows in the system. This prevents the solutions from scaling to support a large number of flows. We then break down this shortcoming by proposing a parallel hybrid SRAM/DRAM architecture (named PHSD). We design a series of memory management algorithms (MMA) for PHSD, based on tradeoffs between the complexity of the MM algorithms and the guarantee of in-order delivery of packets (segmentations). We perform a detailed analysis of the proposed algorithms and conduct extensive simulations to show that PHSD can significantly outperform solutions proposed in the past in terms of the SRAM requirements and packet delay.

PrePrint: Dynamic Multicast in Overlay Networks with Linear Capacity Constraints

A peer-to-peer overlay network is a virtual network of peers (end systems) and unicast connections, residing on top of an IP network. The mapping of peer-to-peer overlay links to paths in the underlying network causes the phenomenon of multiple overlay links sharing bottleneck physical links, which leads to correlation of overlay link capacities. We integrate these link capacity correlations by modeling the overlay using linear capacity constraints (LCC) and demonstrate through analysis and simulations that this model is more accurate in representing the true network topology and hence enables higher-bandwidth peer-to-peer overlay multicast. We formulate the problem of maximizing bandwidth in overlay multicast using LCC. We show that finding a multicast tree in an overlay network with LCC is NP-complete. Therefore, an efficient heuristics algorithm is designed to solve the problem. Extensive simulations show that our algorithm is able to construct multicast trees that are optimal or extremely close to optimal, with significantly higher bandwidth than trees formed in overlays with no LCC. Furthermore, we develop a fully distributed algorithm for obtaining near-optimal multicast trees, by means of gossip-based algorithms and a restricted but inherently distributed class of LCC (node-based LCC). We demonstrate that the distributed algorithm converges quickly to the centralized optimal and is highly scalable.