Shared workload optimization is feasible if the set of tasks to be executed is known in advance, as is the case in updating a set of materialized views or executing an extract-transform-load workflow. In this paper, we consider data-intensive workloads with precedence constraints arising from data dependencies. While there has been previous work on identifying common subexpressions and task re-ordering to enable shared scans, in this paper we solve the problem of scheduling shared data-intensive workloads in a cache-oblivious way. Our solution relies on a novel formulation of precedence constrained scheduling with the additional constraint that once a data item is in the cache, all tasks that require this item should execute as soon as possible thereafter. We give an optimal algorithm using A* search over the space of possible orderings, and we propose efficient and effective heuristics that obtain nearly-optimal schedules in much less time. We present experimental results on real-life data warehouse workloads and the TCP-DS benchmark to validate our claims.

Geographic routing is a method to distribute information in vehicular ad hoc networks over multiple hops. The basic principle is to forward a message to a neighboring station in the network that is closest to the destination area. In contention-based algorithms this next neighbor selection is done in a distributed way, where potential next hop candidates delay their forwarding attempt in a way that the candidate with the largest progress to the destination forwards the message first; other candidates cancel their scheduled retransmissions then. This elegant principle unfortunately depends on a consistent timing and the absence of transmission failures, which cannot be expected in vehicular networks based on IEEE 802.11. This paper illustrates how the re-ordering of channel access attempts through the 802.11 MAC layer and the transmission errors caused by simultaneous broadcast transmissions impact delivery rate and communication overhead. A counter-intuitive finding is that the delivery rate of contention-based forwarding increases when fading is significant (i.e. higher frame errors), but at the cost of higher overhead due to packet duplication. Without fading, duplication is low, but more delivery failures occur. In this paper, we explain the reasons for this behaviour analytically and illustrate it in simulations. Furthermore, we propose a randomized contention- based routing algorithm that balances the trade-off between high end-to- end delivery and low overhead better than the deterministic algorithm and shows a significant performance increase independent of whether fading or frame collisions are present.

The representation of Internet traffic as connection graphs augments anomaly detection systems by providing insight on the structural connection properties, i.e., who-talks-to-whom. However, these graphs are extremely large and one has to decide in advance on which aspect to focus. In the context of malware detection, this is difficult as malware often mimics legitimate traffic. In this paper, we present a statistical approach for extracting the typical traffic destinations for a set of monitored hosts, and derive a reduced graph that contains only connections that are anomalous for that host. This graph can then be analyzed efficiently. Our system is designed to scale to thousands of monitored hosts. We evaluate our approach using a data set from a real network, and show that we can reliably detect injected malware activity.

Channel access in vehicular networks (VANETs) according to the IEEE 802.11p standard relies on CSMA/CA. The specific challenge lies in optimizing the reception rate of broadcast messages carrying awareness information about neighboring vehicles. Several studies have focused on algorithms and protocols that control the channel access in vehicular ad hoc networks, often with a focus on performance analysis of a specific algorithm under certain simulation model assumptions. Among the parameters that influence simulation results, the clear channel assessment (CCA) threshold is a parameter, which is often overlooked. While having low impact in under-utilized channels, the CCA threshold can change the perception of the channel load resulting in interfering transmissions, which in turn have a negative impact on reception rates at larger distances. In this work we investigate the variation of CCA threshold, contention window, and transmit rate for different vehicle densities and demonstrate the impact on received packets at certain distances as well as on the overall channel load.

In this paper we review state-of-the-art botnet detection algorithms that reveal the control traffic of malicious peer-topeer (P2P) networks by targeting topological properties of their interconnectivity graph. This class of detection methods does not rely on the exchanged content and therefore is also applicable to encrypted control traffic. However, in practice, an ISP monitoring customer traffic over an edge router will usually see only a fraction of the overall botnet, thus restricting the available bot connectivity information and limiting the applicability of general community detection approaches. In this paper we critically review graph based detection methods suitable for edge router monitoring using two types of real network traces. We show experimentally that using meta-graphs of mutual contacts proposed by Coskun et al. 2010 has the highest potential on result quality. We improve this approach by presenting a computationally less complex algorithm with similar result quality. Furthermore we explain ways to alleviate the cost of dealing with false positives in the result set.

Beaconless or contention-based geographic routing algorithms forward packets toward a geographical destination reactively without the knowledge of the neighborhood. Such algorithms allow greedy forwarding, where only the next hop neighbor responds after a timer-based contention using only three messages (RTS, CTS, and DATA) per forwarding step. However, existing contention-based schemes for recovery from greedy failures do not have this property. In this paper, we show that recovery is possible within this 3-message scheme: the Rotational Sweep (RS) algorithm directly identifies the next hop after timer-based contention and constructs a traversal path that ensures progress after a greedy failure. It uses a traversal scheme (called Sweep Circle) that forwards a message along the $(\alpha)$-shape of the network and provides recovery paths shorter or equal to the prominent face routing with Gabriel graph planarization. An alternative traversal scheme (called Twisting Triangle) provides even shorter routes on average, as shown by simulations. They both also reduce per-node overall network contention delays. We prove that both traversal schemes guarantee delivery in unit disk graphs. Our traversal schemes avoid planarization and are easy to implement, based merely on the evaluation of a function of a neighbor node's relative position. They can also be used for boundary detection and improve path-length in conventional beacon-based routing.

Nodes in contention-based (beaconless) georouting forward packets towards a known destination position without the knowledge of the neighborhood. The only existing methods [17], [20] that guarantee delivery in unit disk graphs (UDG) require runtime planarization of the communication graph with either unbounded message overhead per hop while preserving the Gabriel graph property of the subgraph, or a constant overhead per hop with up to 13 control messages. In this paper we show that the next hop can be selected directly by a contention mechanism and without prior planarization. Existing greedy routing methods select the next hop with 3 messages using a RTS-CTS-DATA scheme in a timer-based contention where only the next hop neighbor responds. We extend this to provide also recovery from local minima with 3 messages per hop by the Rotational Sweep algorithm. We prove that our algorithm guarantees delivery in UDGs, and also yields routes that are shorter than or equal to the combined greedy and face routing with Gabriel graph planarization. Simulation results show that especially the duration of the contention process can be significantly reduced. Our algorithm can be also used for conventional beacon-based routing with guaranteed delivery without prior planarization, replacing the complicated implementation from [19] by a very simple method which evaluates angular distances to select the proper forwarding neighbor. It also provides a simple network boundary detection algorithm, with or without beacons.

Recently proposed beaconless georouting algorithms are fully reactive, with nodes forwarding packets without prior knowledge of their neighbors. However, existing approaches for recovery from local minima can either not guarantee delivery or they require the exchange of complete neighborhood information. We describe two general methods that enable completely reactive face routing with guaranteed delivery. The Beaconless Forwarder Planarization (BFP) scheme finds correct edges of a local planar subgraph at the forwarder node without hearing from all neighbors. Face routing then continues properly. Angular Relaying determines directly the next hop of a face traversal. Both schemes are based on the Select and Protest principle. Neighbors respond according to a delay function, if they do not violate the condition for a planar subgraph construction. Protest messages are used to remove falsely selected neighbors that are not in the planar subgraph. We show that a correct beaconless planar subgraph construction is not possible without protests. We also show the impact of the chosen planar subgraph construction on the message complexity. This leads to the definition of the Circlunar Neighborhood Graph (CNG), a new proximity graph, that enables BFP with a bounded number of messages in the worst case, which is not possible when using the Gabriel graph (GG). The CNG is sparser than the GG, but this does not lead to a performance degradation. Simulation results show similar message complexities in the average case when using CNG and GG. Angular Relaying uses a delay function that is based on the angular distance to the previous hop. Simulation results show that in comparison to BFP more protests are used, but overall message complexity can be further reduced.

We assume that sensors are aware of the positions of neighbors within a specific knowledge range, which is smaller than their maximum transmission range. We propose the GRoVar protocol (Geographic Routing with Variable transmission range) that extends the well-known GFG protocol [2], a combination of greedy forwarding and recovery, by applying variable transmission range and beaconless routing techniques. In our protocol, each node locally selects the best forwarding neighbor within its knowledge range, using power or other metric. If no neighbor is closer to the destination, the current node may incrementally increase its transmission range to find suitable candidates for the next hop, with the help of request messages. Face routing is applied when no forwarding neighbor is found after sending requests with the maximum transmission range. It also applies range increases until recovery is possible. We investigated different possibilities: a linear increase, doubling the range in each iteration or directly jumping to the maximum range possible. The comparison of energy usage for data transfer from source to sink shows that a significant saving in energy consumption can be achieved using the proposed method.

We investigate distributed algorithms for mobile ad hoc networks for moving radio stations with adjustable transmission power in a worst case scenario. We consider two models to find a reasonable restriction on the worst-case mobility. In the pedestrian model we assume a maximum speed vmax of the radio stations, while in the vehicular model we assume a maximum acceleration amax of the points.Our goal is to maintain persistent routes with nice communication network properties like hop distance, energy-consumption, congestion and number of interferences. A route is persistent, if we can guarantee that all edges of this route can be uphold for a given time span Δ, which is a parameter denoting the minimum time the mobile network needs to adopt changes, i.e. update routing tables, change directory entries, etc. This Δ can be used as the length of an update interval for a proactive routing scheme.We extend some known notions such as transmission range, interferences, spanner, power spanner and congestion to both mobility models and introduce a new parameter called crowdedness that states a lower bound on the number of radio interferences. Then we prove that a mobile spanner hosts a path system that polylogarithmically approximates the optimal congestion.We present distributed algorithms based on a grid clustering technique and a high-dimensional representation of the dynamical start situation which construct mobile spanners with low congestion, low interference number, low energy-consumption, and low degree. We measure the optimality of the output of our algorithm by comparing it with the optimal choice of persistent routes under the same circumstances with respect to pedestrian or vehicular worst-case movements. Finally, we present solutions for dynamic position information management under our mobility models.