Deterministic real-time communication with bounded delay is an essential requirement for many safety-critical cyber–physical systems, and has received much attention from major standardization bodies such as IEEE and IETF. In particular, Ethernet technology has been extended by time-triggered scheduling mechanisms in standards like TTEthernet and Time-Sensitive Networking. Although the scheduling mechanisms have become part of standards, the traffic planning algorithms to create time-triggered schedules are still an open and challenging research question due to the high complexity of the problem. In particular, so-called plug-and-produce scenarios require the ability to extend schedules on the fly within seconds. The need for scalable scheduling and routing algorithms is further supported by large-scale distributed real-time systems like smart energy grids with tight communication requirements. In this paper, we tackle this challenge by proposing two novel algorithms called Hierarchical Heuristic Scheduling (H2S) and Cost-Effective Lazy Forwarding Scheduling (CELF) to create time-triggered schedules for TTEthernet. H2S and CELF are highly efficient and scalable, computing schedules for more than 45,000 streams on random networks with 1000 bridges as well as a realistic energy grid network within seconds or even sub-seconds.

Many applications of cyber-physical systems require real-time communication: manufacturing, automotive, etc. Recent Ethernet standards for Time Sensitive Networking (TSN) offer time-triggered scheduling in order to guarantee low latency and jitter bounds. This requires precise frame transmission planning, which becomes especially hard when dealing with many streams, large networks, and dynamically changing communications. A very promising approach uses conflict graphs, modeling conflicting transmission configurations. Since the creation of conflict graphs is the bottleneck in these approaches, we provide an improvement to the conflict graph creation. We present a randomized selection process that reduces the overall size of the graph in half and three heuristics to improve the scheduling success. In our evaluations we show substantial improvements in the graph creation speed and the scheduling success compared to existing work, updating existing schedules in fractions of a second. Additionally, offline planning of 9000 streams was performed successfully within minutes.

Free WiFi services offer Internet access at many public places like airports or in public transport vehicles. However, the experienced Quality of Service is often poor and unequal between users. While some users can run bandwidth-intensive applications such as video streaming in these networks, others cannot even perform simple web browsing. The reason for this are extensive delays, caused by network congestion of bandwidth-intensive applications, which especially impair interactive applications such as web browsing.In this paper, we propose a novel approach to improve fairness and user experience when sharing common network resources. To this end, we present a Usage-Dependent Quality of Service model (UD-QoS) that dynamically prioritizes network traffic based on the usage intensity of each participant. It shields participants with low usage intensity from congestion delays caused by participants who use the service extensively. We describe the versatile configuration possibilities of UD-QoS and present a Linux-based proof-of-concept implementation.Our evaluations with a physical testbed and popular real-world applications such as video streaming, social media and web browsing show a significant reduction of response times by up to 79% with UD-QoS while keeping processing overhead low. The benefits are particularly large for participants with low usage intensity.

Since network delays can severely impact Networked Control Systems (NCS), both guaranteed Quality of Service (QoS) at the network level and guaranteed stability at the application level in the presence of delays are essential. The recently developed Dynamic Priority Token Bucket (DPTB) aims to meet network-level requirements through dynamic yet deterministic latency bounds that depend on the application’s sending behavior.This concept provides great potential for a combined design method with NCS controllers, which we propose in this paper. We design and implement two approaches that combine DPTB with (1) the well-known robust input/output (DPTB-RobustIO) controller to provide provable stability and (2) a novel multi-level linear quadratic regulator (DPTB-MLQR) to improve control performance.For the evaluation of the approaches, an Ethernet-based NCS with a Linux software switch and an inverted pendulum is used. This benchmark setup for fully automated evaluations of co-designs that combine network scheduling and QoS mechanisms with NCS controllers running on real hardware components is made available as an open source implementation. DPTB-RobustIO and DPTB-MLQR reduced the data rate by up to 26% and increased the control performance by 27% compared to regular token buckets with RobustIO control.

Overload situations, in the presence of resource limitations, in complex event processing (CEP) systems are typically handled using load shedding to maintain a given latency bound. However, load shedding might negatively impact the quality of results (QoR). To minimize the shedding impact on QoR, CEP researchers propose shedding approaches that drop events/internal state with the lowest importances/utilities. In both black-box and white-box shedding approaches, different features are used to predict these utilities. In this work, we propose a novel black-box shedding approach that uses a new set of features to drop events from the input event stream to maintain a given latency bound. Our approach uses a probabilistic model to predict these event utilities. Moreover, our approach uses Zobrist hashing and well-known machine learning models, e.g., decision trees and random forests, to handle the predicted event utilities. Through extensive evaluations on a real-world and several synthetic datasets and a representative set of CEP queries, we show that, in the majority of cases, our load shedding approach outperforms state-of-the-art black-box load shedding approaches, w.r.t. QoR.

Executing complex simulations on mobile devices such as augmented reality (AR) glasses or smartphones enables many novel pervasive applications. For instance, a physiotherapist can display muscles and bones in real-time as a visual overlay on the patient's body. The major challenge of such pervasive simulations is the complexity of the simulation, which typically exceeds the resources of the mobile device by far. Offloading computationally intensive simulations to a remote server is a promising method to enable real-time simulations on resource-constrained mobile devices without compromising the quality of the simulation results. However, the results of offloaded computations may arrive with an inevitable communication delay, which is critical for real-time simulations and also induces communication overhead. In this work, we tackle these challenges by proposing a novel approach for pervasive simulations on mobile devices. We combine a low-quality local Neural Network (NN) model on the mobile device with a high-quality NN model on a remote server, particularly taking care to integrate delayed updates from the server with the local simulation results. This distributed approach has several advantages over purely local or remote execution models: We benefit from high-quality remote results, while being robust to dynamic delays, server and network failures, and we reduce the communication overhead.

Many time-sensitive networked systems, such as networked control systems or other cyber/physical systems, require well-defined Quality of Service (QoS) with guaranteed deterministic bounds on network delay. Existing QoS models typically provide no guarantees for excess traffic beyond the traffic specified during the initial admission process. This can lead to a waste of resources when applications overcompensate during resource reservation to avoid traffic violations. In this work, we propose the Dynamic Priority Token Bucket (DPTB), a fundamentally different new QoS model. DPTB permits short-time violations without immediately dropping to best-effort guarantees for excess traffic. Instead, the priority of the application gets degraded to weaker but still deterministic guarantees. At any point in time, the application can calculate the currently guaranteed delay bounds, which depend only on its own past sending behavior, to enable application-level adaptation of the sending rate and application-side prediction of the implications onto the application performance. We designed DPTB as a token bucket extension that can be used on top of several existing scheduling mechanisms, such as the Asynchronous Traffic Shaper of IEEE Time-Sensitive Networking (TSN). Our evaluations show that DPTB is more resilient to bursty cross-traffic, resulting in significantly lower average delays than regular reservations.

Numerical simulations on mobile devices are an important tool for engineers and decision makers in the field. However, providing simulation results on mobile devices is challenging due to the complexity of the simulation, requiring remote server resources and distributed mobile computation. The additional large size of multi-dimensional simulation results leads to the insufficient performance of existing approaches, especially when the bandwidth of wireless communication is scarce. In this article, we present an optimized novel approach utilizing surrogate models and data assimilation techniques to reduce the communication overhead. Evaluations show that our approach is up to 6.5 times faster than streaming results from the server while still meeting required quality constraints.

Simulations are an important part of analyzing and understanding systems, including not only technical but also bio-mechanical subjects such as the musculoskeletal apparatus of the human body. Detailed, biophysical simulations are complex and require a substantial amount of computational resources. With the advent of mobile AR devices such as the Microsoft HoloLens, new challenges arise to run or represent the results of such complex simulations on resource-constrained devices. In this paper we propose a deep-learning-based mobile simulation approach for the contraction of a human muscle model on an AR device (MS HoloLens 2). To elaborate, we present a two-step workflow consisting of simulating the deformation of the 3D geometry of the biceps, of which a subset of points can be interpolated back to full resolution. This allows to either offload the full simulation, just communicating the subset of nodal points, or to use a lower-quality local simulation restricted to the subset. Interpolation is done locally in both cases. The interpolation model consists of a dense, single hidden layer neural network. A mesh simplification method is combined with a genetic algorithm to determine the optimal subset of mesh nodes to interpolate from. In purely local execution, our simulation and interpolation model is able to accurately predict the position of 2809 nodal points based on as few as 30, while using 97.78 % less energy and evaluating up to 1.23 times faster compared to the local reference model. In an ideal distributed scenario energy consumption decreases by 99 % and evaluation time is up to 32.42 times faster. For the latter, it also reduces communication-data to 1.2 % of the full resolution mesh.

In complex event processing (CEP), load shedding is performed to maintain a given latency bound during overload situations when there is a limitation on resources. However, shedding load implies degradation in the quality of results (QoR). Therefore, it is crucial to perform load shedding in a way that has the lowest impact on QoR. Researchers, in the CEP domain, propose to drop either events or partial matches (PMs) in overload cases. They assign utilities to events or PMs by considering either the importance of events or the importance of PMs but not both together. In this article, we combine these approaches where we propose to assign a utility to an event by considering both the event importance and the importance of PMs. We propose two load shedding approaches for CEP systems. The first approach drops events from PMs, while the second approach drops events from windows. We adopt a probabilistic model that uses the type and position of an event in a window and the state of a PM to assign a utility to an event. We, also, propose an approach to predict a utility threshold that is used to drop the required amount of events to maintain a given latency bound. By extensive evaluations on two real-world datasets and several representative queries, we show that, in the majority of cases, our load shedding approach outperforms state-of-the-art load shedding approaches, w.r.t. QoR.

Many networked applications, e.g., in the domain of cyber-physical systems, require strict service guarantees for time-triggered traffic flows, usually in the form of jitter and latency bounds. It is a notoriously hard problem to compute a network-wide traffic plan, i.e., a set of routes and transmission schedules, that satisfies these requirements, and dynamic changes in the flow set add even more challenges. Existing traffic-planning methods are ill-suited for dynamic scenarios because they either suffer from high computational cost, can result in low network utilization, or provide no explicit guarantees when transitioning to a new traffic plan that incorporates new flows. Therefore, we present a novel approach for dynamic traffic planning of time-triggered flows. Our conflict-graph-based modeling of the traffic planning problem allows for the reconfiguration of active flows to increase the network utilization, while also providing per-flow QoS guarantees during the transition to the new traffic plan. Additionally, we introduce a novel heuristic for computing the new traffic plans. Evaluations of our prototypical implementation show that we can efficiently compute new traffic plans in scenarios with hundreds of active flows for a wide range of settings.

The increasing number of cloud offerings makes it more challenging to find services that realize an optimal architecture. Hence, modeling cloud applications with the help of platform-independent models as known from Model-Driven Architecture (MDA) should aid developers in designing best-practice architectures. However, refining platform-independent architecture models into an architecture with concrete services might lead to a large number of potential solutions, raising the question of which solution is the best. Therefore, we propose a framework that uses meta-heuristics to approximate the search of concrete solutions for component-based architectures, using the notion of refinement trees to encode the potential solution space of abstract components. In this paper, we show how to transform the solution space of the refinement trees into a suitable input for the meta-heuristic. Moreover, we provide a class of loss functions with the objective to minimize cost, while also considering quality of service (QoS) constraints to demonstrate possible applications of the framework. The evaluation uses the Harmony Search algorithm as a concrete implementation of a meta-heuristic to exemplify our framework. We analyzed different cloud architecture examples from Microsoft Azure, where we show the advantages of the heuristic approach by proposing cost-minimal services for a given QoS constraint.

Workflows are the de facto standard for managing business processes and allow businesses to automate interactions between business locations and partners residing anywhere on the planet. This, however, requires the workflows to be executed in a dynamic environment, where device and communication failures occur frequently, making availability a key concern. In this work, we propose the replicated execution of workflows for ensuring availability in the presence of failures. The replicated execution has to yield the same result as a non-replicated execution of that workflow. Thus, we formally define Single-Execution-Equivalence and present a replication scheme that adheres to this definition. We implement a proof-of-concept using an open-source workflow engine for demonstrating the compatibility with current workflow technology. Our evaluations on Amazon EC2, OpenStack, and PlanetLab show that workflow replication ensures availability while being scalable and incurring low overhead in terms of execution time.

Many applications require the processing of event streams from different sources in combination with large amounts of background knowledge. Semantic CEP is a paradigm designed specifically for that. It extends complex event processing (CEP) with RDF support and uses a network of operators to process RDF streams in combination with RDF knowledge bases. Another popular class of systems designed for a similar purpose are the RDF stream processors (RSPs). These are systems that extend SPARQL (the RDF query language) with stream processing capabilities. Semantic CEP and RSPs have similar purposes but focus on different things. The former focuses on scalability and distributed processing while the latter tend to focus on the intricacies of RDF stream processing per se. In this paper we propose the use of RSP engines as building blocks for Semantic CEP. We present an infrastructure, called DSCEP, that allows the encapsulation of existing RSP engines into CEP-like operators so that these can be seamlessly interconnected in a distributed, decentralized operator network. DSCEP handles the hurdles of such interconnection, such as reliable communication, stream aggregation and slicing, event identification and time-stamping, etc., allowing users to concentrate on the queries. We also discuss in the paper how DSCEP can be used to speedup monolithic SPARQL queries by splitting them into parallel subqueries operating over restricted parts of the knowledge base.

Recently, named data networking (NDN) has been introduced to connect the world of computing devices via naming data instead of their containers. Through this strategic change, NDN brings several new features to network communication, including in-network caching, multipath forwarding, built-in multicast, and data security. Despite these unique features of NDN networking, there exist plenty of opportunities for continuing developments, especially with packet forwarding and caching. In this context, we introduce liteNDN, a novel forwarding and caching strategy for NDN networks. liteNDN comprises a cooperative forwarding strategy through which NDN routers share their knowledge, i.e. data names and interfaces, to optimize their packet forwarding decisions. Subsequently, liteNDN leverages that knowledge to estimate the probability of each downstream path to swiftly retrieve the requested data. Additionally, liteNDN exploits heuristics, such as routing costs and data significance, to make proper decisions about caching normal as well as segmented packets. The proposed approach has been extensively evaluated in terms of the data retrieval latency, network utilization, and the cache hit rate. The results showed that liteNDN, compared to conventional NDN forwarding and caching strategies, achieves much less latency while reducing the unnecessary traffic and caching activities.

Traffic planning is the key enabler of time-triggered real-time communication in distributed systems, and it is known to be notoriously hard. Current approaches predominantly tackle the problem in the domain of the traffic planning problem, e.g., by formulating constraints on the transmission schedules for individual data streams, or the links used by the data streams. This results in a high degree of coupling of the configuration of an individual data stream and the global (network-wide) traffic configuration with detrimental effects on the scalability and runtime of the planning phase.In contrast, we present a configuration-conflict graph based approach, which solves the original traffic planning problem by searching an independent vertex set in the conflict graph. We show how to derive the configuration-conflict graph, and discuss the conceptual advantages of this approach. To show the practical advantages of the conflict-graph based traffic planning approach we additionally present a proof-of-concept implementation and evaluate it against a reference ILP-based implementation. In our evaluations, our proof-of-concept implementation of the conflict-graph based approach outperforms the reference ILP and is more memory efficient, making it a promising alternative to current constraint-based traffic planning approaches.

Nowadays, autonomous driving and driver assistance applications are being developed at an accelerated pace. This rapid growth is primarily driven by the potential of such smart applications to significantly improve safety on public roads and offer new possibilities for modern transportation concepts. Such indispensable applications typically require wireless connectivity between the vehicles and their surroundings, i.e. roadside infrastructure and cloud services. Nevertheless, such connectivity to external networks exposes the internal systems of individual vehicles to threats from remotely-launched attacks. In this realm, it is highly crucial to identify any misbehavior of the software components which might occur owing to either these threats or even software/hardware malfunctioning. In this paper, we introduce AutoSec, a host-based anomaly detection algorithm which relies on observing four timing parameters of the executed software components to accurately detect malicious behavior on the operating system level. To this end, AutoSec formulates the task of detecting anomalistic executions as a clustering problem. Specifically, AutoSec devises a hybrid clustering algorithm for grouping a set of collected timing traces resulted from executing the legitimate code. During the runtime, AutoSec simply classifies a certain execution as an anomaly, if its timing parameters are distant enough from the boundaries of the predefined clusters. To show the effectiveness of AutoSec, we collected timing traces from a testbed composed of a set of real and virtual control units communicating over a CAN bus. We show that using our proposed AutoSec, compared to baseline methods, we can identify up to 21% less false positives and 18% less false negatives.

Recently, indoor modeling has gained increased attention, thanks to the immense need for realizing efficient indoor location-based services. Indoor environments differ from outdoor spaces in two aspects: spaces are smaller and there are many structural objects such as walls, doors, and furniture. To model the indoor environments in a proper manner, novel data acquisition concepts and data modeling algorithms have been devised to meet the requirements of indoor spatial applications. In this realm, several research efforts have been exerted. Nevertheless, these efforts mostly suffer either from adopting impractical data acquisition methods or from being limited to 2D modeling. To overcome these limitations, we introduce the MapSense approach, which automatically derives indoor models from 3D point clouds collected by individuals using mobile devices, such as Google Tango, Apple ARKit, and Microsoft HoloLens. To this end, MapSense leverages several computer vision and machine learning algorithms for precisely inferring the structural objects. In MapSense, we mainly focus on improving the modeling accuracy through adopting formal grammars that encode design-time knowledge, i.e., structural information about the building. In addition to modeling accuracy, MapSense considers the energy overhead on the mobile devices via developing a probabilistic quality model through which the mobile devices solely upload high-quality point clouds to the crowd-sensing servers. To demonstrate the performance of MapSense, we implemented a crowd-sensing Android App to collect 3D point clouds from two different buildings by six volunteers. The results showed that MapSense can accurately infer the various structural objects while drastically reducing the energy overhead on the mobile devices.

Typically, Function-as-a-Service (FaaS) involves state-less replication with very large numbers of instances. The reliability of such services can be evaluated using Bayesian Networks and k-out-of-n models. However, existing k-out-of-n models do not scale to the larger number of hosts of FaaS services. Therefore, we propose a scalable k-out-of-n model in this paper with the same semantics as the standard k-out-of-n voting gates in fault trees, enabling the reliability analysis of FaaS services.

Complex event processing (CEP) systems continuously process input event streams to detect patterns. Over time, the input event rate might fluctuate and overshoot the system's capabilities. One way to reduce the overload on the system is to use load shedding. In this paper, we propose a load shedding strategy for CEP systems which drops a portion of the CEP operator's internal state (a.k.a. partial matches) to maintain a given latency bound. The crucial question here is how many and which partial matches to drop so that a given latency bound is maintained while minimizing the degradation in the quality of results. In the stream processing domain, different load shedding strategies have been proposed that mainly depend on the importance of individual tuples. However, as CEP systems perform pattern detection, the importance of events is also influenced by other events in the stream. Our load shedding strategy uses Markov chain and Markov reward process to predict the utility/importance of partial matches to determine the ones to be dropped. In addition, we represent the utility in a way that minimizes the overhead of load shedding. Furthermore, we provide algorithms to decide when to start dropping partial matches and how many partial matches to drop. By extensively evaluating our approach on three real-world datasets and several representative queries, we show that the adverse impact of our load shedding strategy on the quality of results is considerably less than the impact of state-of-the-art load shedding strategies.

We present a communication abstraction for Networked Control Systems that is characterized by a slotted transmission classification model. We discuss, how such a model can be implemented over local area networks by using IEEE Time Sensitive Networking methods. Furthermore, it is shown how asymptotic stability can be analyzed for linear systems that communicate over such a network. Based on the stability result, a controller design procedure is derived that takes the information captured in the network model into account. Further topics and related open problems that are implicated by the proposed model are briefly discussed as an outlook.

Internet of Things (IoT) is expanding at a rapid rate where it allows for virtually endless opportunities and connections to take place. In general, IoT opens the door to a myriad of applications but also to many challenges. One of the major challenges is how to efficiently retrieve the sensory data from "resources-limited" IoT devices. Such devices typically have a restricted energy budget, which broadly hinders their direct connection to the Internet. In this realm, modern mobile devices, e.g. smartphones, tablets, smartwatches, have been harnessed to bridge between the low-power IoT devices and the Internet. However, the current vision which mainly relies on designing siloed gateways, i.e. a separate gateway/App for each IoT device, is certainly impractical, especially with the rapid growth in the number of IoT devices. Furthermore, the energy efficiency of the smart mobile devices hosting the IoT gateways has to be thoroughly considered. To tackle these challenges, we introduce GaaS (Gateway as a Service), a cross-platform gateway architecture for opportunistically retrieving sensory data from the low-power IoT sensors. Through Bluetooth low energy radios, GaaS is capable of simultaneously connecting to several nearby IoT sensors. To this end, we devise two distinct priority-based scheduling algorithms, namely the EP-WSM and FEP-AHP schedulers, which rank the detected IoT sensors, before estimating the connection time for each IoT sensor. The intuition behind ranking the IoT sensors is to improve the data retrieval rate from these sensors together with reducing the energy overhead on the mobile devices. Additionally, GaaS encompasses a self-adaptive engine to automatically balance the trade-off between energy efficiency and data retrieval rate through switching between schedulers according to the runtime dynamics. To demonstrate the effectiveness of GaaS, we implemented an IoT testbed to evaluate the energy consumption, the latency, and the data retrieval rate. The results show that using GaaS, compared to siloed gateways, we can identify up to 18% savings in the consumed energy while requiring much less data retrieval time.

Control mechanisms of stream processing applications (SPAs) that ensure latency bounds at minimal runtime cost mostly target a specific infrastructure, e.g., homogeneous nodes. With the growing popularity of the Internet of Things, fog, and edge computing, SPAs are more often distributed on heterogeneous infrastructures, triggering the need for a holistic SPA-control that still considers heterogeneity. We therefore combine individual control mechanisms via the latency-distribution problem that seeks to distribute latency budgets to individually managed components of distributed SPAs for a lightweight yet effective end-to-end control. To this end, we introduce a hierarchical control architecture, give a formal definition of the latency-distribution problem, and provide both an ILP formulation to find an optimal solution as well as a heuristic approach, thereby enabling the combination of individual control mechanisms into one SPA while ensuring global cost minimality. Our evaluations show that both solutions are effective---while the heuristic approach is only slightly more costly than the optimal ILP solution, it significantly reduces runtime and communication overhead.

Complex event processing systems process the input event streams on-the-fly. Since input event rate could overshoot the system's capabilities and results in violating a defined latency bound, load shedding is used to drop a portion of the input event streams. The crucial question here is how many and which events to drop so the defined latency bound is maintained and the degradation in the quality of results is minimized. In stream processing domain, different load shedding strategies have been proposed but they mainly depend on the importance of individual tuples (events). However, as complex event processing systems perform pattern detection, the importance of events is also influenced by other events in the same pattern. In this paper, we propose a load shedding framework called eSPICE for complex event processing systems. eSPICE depends on building a probabilistic model that learns about the importance of events in a window. The position of an event in a window and its type are used as features to build the model. Further, we provide algorithms to decide when to start dropping events and how many events to drop. Moreover, we extensively evaluate the performance of eSPICE on two real-world datasets.

We propose two extensions for a state-of-the-art method of rollback-recovery in distributed CEP (complex event processing). In CEP, an operator network is used to search for patterns in events streams. Sometimes these operators fail and lose their state. Rollback-recovery is a method for dealing with such state losses. The type of rollback-recovery we consider is upstream backup, where the state of a failed operator is recovered by replaying to it the input events that led it to that state. These events are kept in upstream operators' memory buffers, which are trimmed continuously as the downstream operator progresses. The first extension we propose saves memory and speeds up recovery by avoiding to store and retransmit unnecessary events. The second extension makes the base method of upstream backup compatible with data-parallel CEP, allowing that the windows into which operators partition their input be processed in parallel. We evaluated the proposed extensions through experiments that showed a significant reduction in memory usage and recovery time at the expense of a negligible processing overhead during normal operation.

Many important real-world applications-such as social networks or distributed data bases-can be modeled as hypergraphs. In such a model, vertices represent entities-such as users or data records-whereas hyperedges model a group membership of the vertices-such as the authorship in a specific topic or the membership of a data record in a specific replicated shard. To optimize such applications, we need an efficient and effective solution to the NP-hard balanced k-way hypergraph partitioning problem. However, existing hypergraph partitioners that scale to very large graphs do not effectively exploit the hy-pergraph structure when performing the partitioning decisions. We propose HYPE, a hypergraph partitionier that exploits the neighborhood relations between vertices in the hypergraph using an efficient implementation of neighborhood expansion. HYPE improves partitioning quality by up to 95% and reduces runtime by up to 39% compared to streaming partitioning.

In recent years, the graph partitioning problem gained importance as a mandatory preprocessing step for distributed graph processing on very large graphs. Existing graph partitioning algorithms minimize partitioning latency by assigning individual graph edges to partitions in a streaming manner - at the cost of reduced partitioning quality. However, we argue that the mere minimization of partitioning latency is not the optimal design choice in terms of minimizing total graph analysis latency, i.e., the sum of partitioning and processing latency. Instead, for complex and long-running graph processing algorithms that run on very large graphs, it is beneficial to invest more time into graph partitioning to reach a higher partitioning quality - which drastically reduces graph processing latency. In this paper, we propose ADWISE, a novel window-based streaming partitioning algorithm that increases the partitioning quality by always choosing the best edge from a set of edges for assignment to a partition. In doing so, ADWISE controls the partitioning latency by adapting the window size dynamically at run-time. Our evaluations show that ADWISE can reach the sweet spot between graph partitioning latency and graph processing latency, reducing the total latency of partitioning plus processing by up to 23-47 percent compared to the state-of-the-art.

Recently, mobile crowdsensing has become an appealing paradigm thanks to the ubiquitous presence of powerful mobile devices. Indoor mapping, as an example of crowdsensingdriven applications, is essential to provide many indoor locationbased services, such as emergency response, security, and tracking/navigation in large buildings. In this realm, 3D point clouds stand as an optimal data type which can be crowdsensed-using currently-available mobile devices, e.g. Google Tango, Microsoft Hololens and Apple ARKit-to generate floor plans with different levels of detail, i.e. 2D and 3D mapping. However, collecting such bulky data from "resources-limited" mobile devices can significantly harm their energy efficiency. To overcome this challenge, we introduce GreenMap, an energy-aware architectural framework for automatically mapping the interior spaces using crowdsensed point clouds with the support of structural information encoded in formal grammars. GreenMap reduces the energy overhead through projecting the point clouds to several filtration steps on the mobile devices. In this context, GreenMap leverages the potential of approximate computing to reduce the computational cost of data filtering while maintaining a satisfactory level of modeding accuracy. To this end, we propose two approximation strategies, namely DyPR and SuFFUSION. To demonstrate the effectiveness of GreenMap, we implemented a crowdsensing Android App to collect 3D point clouds from two different buildings. We show that GreenMap achieves significant energy savings of up to 67.8%, compared to the baseline methods, while generating comparable floor plans.

Location information sharing on popular online social networking platforms like Facebook and Foursquare brings mutual benefits for the users of these platforms (e.g., free locationbased services) as well as the platform providers (e.g., locationbased businesses). An obvious problem however that impedes these mutual benefits are privacy concerns related to location data of users, which also curb their active participation. In this paper, we analyze the role of existing location privacypreserving mechanisms in minimizing this mutual loss of benefits. Our analysis reveals that most existing mechanisms either ignore social platform related user-privacy concerns or they disregard location data-quality related demands of the platform providers. Moreover, we also point out concrete research gaps and implementation issues related to existing privacy mechanisms.

IEEE 802.1Q networks with extensions for time-sensitive networking aim to enable converged networks. Converged networks support hard-real time communication services in addition to the currently supported services classes. Real-time communication in these networks requires routes and schedules for the real-time transmissions. We present a formulation in the integer linear programming (ILP) framework which models the joint routing and scheduling problem for flows of periodic real-time transmissions in converged TSN networks. In the joint routing and scheduling problem, both routes and schedules for real-time transmissions are computed in one step, i.e. we do not schedule over predefined routes. We explore the practical limitations of this approach by evaluating the runtime of problem instances with widely varying parameters with a state-of-the-art ILP solver. The observed solver runtimes indicate the qualitative impact of the number of real-time flows, the size of the network, the transmission frequency of real-time transmissions, and the network topology.

Several networking architectures have been developed atop IEEE 802.3 networks to provide real-time communication guarantees for time-sensitive applications in industrial automation systems. The basic principle underlying these technologies is the precise transmission scheduling of time-triggered traffic through the network for providing deterministic and bounded latency and jitter. These transmission schedules are typically synthesized offline (computational time in the order of hours) and remain fixed thereafter, making it difficult to dynamically add or remove network applications. This paper presents algorithms for incrementally adding time-triggered flows in a time-sensitive software-defined network (TSSDN). The TSSDN is a network architecture based on software-defined networking, which provides real-time guarantees for time-triggered flows by scheduling their transmissions on the hosts (network edge) only. These algorithms exploit the global view of the control plane on the data plane to schedule and route time-triggered flows needed for the dynamic applications in the Industrial Internet of Things (Industry 4.0). The evaluations show that these algorithms can compute incremental schedules for time-triggered flows in subseconds with an average relative optimality of 68%.

Recent years have seen an evolution of software-defined networking (SDN) control plane architectures, starting from simple monolithic controllers, over modular monolithic controllers, to distributed controllers. We observe, however, that today's distributed controllers still exhibit inflexibility with respect to the distribution of control logic. Therefore, we propose a novel architecture of a distributed SDN controller, providing maximum flexibility with respect to distribution and improved manageability. Our architecture splits control logic into lightweight control modules, called controllets, based on a micro-kernel approach, reducing common controllet functionality to a bare minimum and factoring out all higher-level functionality. Lightweight controllets also allow for pushing control logic onto switches and enable local processing of data plane events to minimize control latency and communication overhead while leveraging SDN's global view to maximize control decision quality. Controllets are interconnected through a message bus supporting the publish/subscribe communication paradigm with specific extensions for content-based message filtering. Publish/subscribe allows for complete decoupling of controllets to further facilitate control plane distribution. Furthermore, we identify crucial requirements for practical on-switch deployments, where we employ lightweight virtualization techniques to ensure a safe control plane operation. We evaluate both, the scalability and performance properties of our architecture, including its deployment on a white-box networking hardware switch.

With the vision of Internet of Things gaining popularity at a global level, efficient publish/subscribe middleware for communication within and across data centers is extremely desirable. In this respect, the very popular Software-Defined Networking, which enables publish/subscribe middleware to perform line-rate filtering of events directly on hardware, can prove to be very useful. While deploying content filters directly on switches of a software-defined network allows optimized paths, high throughput rates, and low end-to-end latency, it suffers from certain inherent limitations with respect to number of bits available on hardware switches to represent these filters. Such a limitation affects expressiveness of filters, resulting in unnecessary traffic in the network. In this paper, we explore various complementary techniques to represent content filters expressively while being limited by hardware. We implement and evaluate techniques that i) use workload, in terms of events and subscriptions, to represent content, and ii) efficiently select attributes to reduce redundancy in content. Our detailed performance evaluations show the potential of these techniques in reducing unnecessary traffic when subjected to different workloads. Furthermore, the techniques proposed in this paper require significant updates to the network, i.e., the data plane, which must be performed in a consistent manner to ensure desired system behavior. As a result, in this paper, we, also, design and evaluate a light-weight approach that ensures data plane consistency in the presence of dynamic network updates.

Distributed graph processing systems such as Pregel, PowerGraph, or GraphX gained popularity due to their superior performance of data analytics on graph-structured data. These systems employ partitioning algorithms to parallelize graph analytics while minimizing inter-partition communication. Recent partitioning algorithms, however, unrealistically assume a uniform and constant amount of data exchanged between graph vertices (i.e., uniform vertex traffic) and homogeneous network costs between workers hosting the graph partitions. This leads to suboptimal partitioning decisions and inefficient graph processing. To this end, we developed Grapes, the first graph processing system using vertex-cut graph partitioning that considers both, diverse vertex traffic and heterogeneous network costs. The main idea is to avoid frequent communication over expensive network links using an adaptive edge migration strategy. Our evaluations show an improvement of 10 percent in graph processing latency and 60 percent in communication costs compared to state-of-the-art partitioning approaches.

Recent years have seen an evolution of SDN control plane architectures, starting from simple monolithic controllers, over modular monolithic controllers, to distributed controllers. We observe, however, that today's distributed controllers still exhibit inflexibility with respect to the distribution of control logic. Therefore, we propose a novel architecture of a distributed SDN controller in this paper, providing maximum flexibility with respect to distribution. Our architecture splits control logic into light-weight control modules, called controllets, based on a micro-kernel approach, reducing common controllet functionality to a bare minimum and factoring out all higher-level functionality. Light-weight controllets also allow for pushing control logic onto switches and enable local processing of data plane events to minimize latency and communication overhead. Controllets are interconnected through a message bus supporting the publish/subscribe communication paradigm with specific extensions for content-based OpenFlow message filtering. Publish/subscribe allows for complete decoupling of controllets to further facilitate control plane distribution. We evaluate both, the scalability and performance properties of our architecture, including its deployment on a White Box networking hardware switch.

Recent developments in networking hardware and software-defined networking have enabled full distribution of network control to reduce control latency and increase reliability. However, both, hardware and software of current white-box networking hardware are highly heterogeneous, which limits the deployment and operation of switch-local control applications. Furthermore, switch-local control raises yet unconsidered security concerns. In this paper, we present our concept of in-forward-element processing, which leverages the open access to the control plane of white-box networking hardware to deploy control logic directly onto switches. We combine local control applications with lightweight virtualization to cope with networking hardware heterogeneity and to achieve required isolation properties and ease of management. Beyond distributed network control, we show this scheme is also beneficial for implementing switch-local virtual network functions (NFV), processing packets. Highlighting the practicability of the concepts, we provide an overview of the current white-box networking hardware and software landscape and their compatibility with lightweight virtualization technologies. To this end, we perform an empirical evaluation of NOS-virtualization combinations on such hardware and compare the results with respect to incurring virtualization overhead.

Recently, crowd-sensing has rapidly been evolved thanks to the technological advancement in personal mobile devices. This emerging technology opens the door for numerous applications to collect sensory data from the crowd. To provide people with a motive for participating in data acquisition, the crowd-sensing systems have to sidestep burdening the resources allocated to the mobile devices, i.e. computing power and energy budget. In this paper, we propose iSense, a novel framework for reducing the energy costs of participating in crowd-sensing. We mainly target the superfluous energy overhead on the mobile devices to sense and report their position information to the back-end servers. To relieve such an overhead, iSense entirely offloads the localization burden to the crowd-sensing servers. In this manner, iSense enables the utilization of advanced localization approaches thanks to the high resources of the crowd-sensing servers. To this end, iSense opportunistically exploits the “already-existent” network signaling exchanged frequently between the mobile devices and the WiFi networks or the cellular networks. To collect the localization data, we implement a lightweight data collection algorithm on a set of off-the-shelves access points. As a case study, we implement a two-step localization method, including a coarse- and a fine-grained localization. In this regard, compressed sensing is employed to estimate the fine-grained solution. To assess the effectiveness of iSense, we implemented a testbed to evaluate the energy consumption and the localization accuracy with different mobility and usage patterns. The results show that using iSense, compared to some baseline methods, we can identify up to 95% savings in the consumed energy.

Distributed Complex Event Processing (DCEP) is a paradigm to infer the occurrence of complex situations in the surrounding world from basic events like sensor readings. In doing so, DCEP operators detect event patterns on their incoming event streams. To yield high operator throughput, data parallelization frameworks divide the incoming event streams of an operator into overlapping windows that are processed in parallel by a number of operator instances. In doing so, the basic assumption is that the different windows can be processed independently from each other. However, consumption policies enforce that events can only be part of one pattern instance; then, they are consumed, i.e., removed from further pattern detection. That implies that the constituent events of a pattern instance detected in one window are excluded from all other windows as well, which breaks the data parallelism between different windows. In this paper, we tackle this problem by means of speculation: Based on the likelihood of an event's consumption in a window, subsequent windows may speculatively suppress that event. We propose the SPECTRE framework for speculative processing of multiple dependent windows in parallel. Our evaluations show an up to linear scalability of SPECTRE with the number of CPU cores.

Recently, several approaches have been proposed to automatically model indoor environments. Most of such efforts principally rely on the crowd to sense data such as motion traces, images, and WiFi footprints. However, large datasets are usually required to derive precise indoor models which can negatively affect the energy efficiency of the mobile devices participating in the crowd-sensing system. Furthermore, the aforementioned data types are hardly suitable for deriving 3D indoor models. To overcome these challenges, we propose GraMap, a QoS-aware automatic indoor modeling approach through crowd-sensing 3D point clouds. GraMap exploits a recently-developed sensors fusion mechanism, namely Tango technology, to cooperatively collect point clouds from the crowd. Afterward, a set of backend servers extracts the required geometrical information to derive indoor models.

In today's online social networks such as Facebook, users increasingly share their location information as a popular type of personal information. However, since location data can leak privacy-sensitive information about individuals such as the type of places they like to visit, a number of location obfuscation mechanisms have been proposed to avoid such disclosure. These mechanisms publish bigger regions containing the actual user location in order to make it imprecise. Thus an attacker may find it hard to precisely locate the user in a privacy-sensitive place such as a hospital.

Currently, various hardware and software companies are developing augmented reality devices, most prominently Microsoft with its Hololens. Besides gaming, such devices can be used for serious pervasive applications, like interactive mobile simulations to support engineers in the field. Interactive simulations have high demands on resources, which the mobile device alone is unable to satisfy. Therefore, we propose a framework to support mobile simulations by distributing the computation between mobile device and a remote server. For the computation of parameter-dependent solutions of the simulation, we use the reduced basis method, which allows to drastically reduce the computation time and energy consumption. We present three approaches for the distributed execution of the reduced basis method between mobile device and server. Evaluations show that we can speed-up the numerical computation to over 131 times while using 73 times less energy compared to offloading everything to a server.

With the increasing popularity of software-defined networking (SDN), ternary content-addressable memory of switches can be directly accessed by a publish/subscribe middleware to perform filtering operations at low latency. In this way, three important requirements for a publish/subscribe middleware can be fulfilled, namely, bandwidth efficiency, line-rate performance, and low latency in forwarding messages between producers and consumers. Nevertheless, it is challenging to sustain line-rate performance in the presence of dynamically changing interests of producers and consumers. In this paper, we realize a scalable, SDN-based publish/subscribe middleware, called PLEROMA, that performs efficient forwarding at line-rate. Moreover, PLEROMA offers methods to efficiently reconfigure a deployed topology in the presence of dynamic subscriptions and advertisements. We evaluate the performance of both the data plane and the control plane of PLEROMA to support our claim. Furthermore, we evaluate and benchmark the performances of SDN-compliant hardware and software switches in the context of our middleware.

Over the past few decades, content-based publish/subscribe has been primarily implemented as an overlay network of software brokers. Even though such systems provide the possibility of bandwidth efficient expressive filtering in software, they cannot match up to the performance (in terms of end-to-end latency and throughput) of communication protocols implemented on the network layer. To exploit network layer performance benefits, recently, content-based publish/subscribe was realized using the capabilities of Software-defined Networking (SDN). While SDN allows line-rate forwarding of events by content filters directly installed on switches, it suffers from inherent hardware limitations (w.r.t. flow table size, limited availability of bits in header fields) that adversely impact expressiveness of these filters, resulting in unnecessary network traffic. In this paper, we strike a balance between purely application-layer-based and purely network-layer-based publish/subscribe implementations by realizing the first hybrid content-based middleware that enables filtering of events in both layers. Moreover, we provide different selection algorithms with varying degrees of complexity to determine the events to be filtered at each layer such that unnecessary network traffic can be minimized while also considering delay requirements of the middleware. Our hybrid middleware offers full flexibility to configure it according to the performance requirements of the system. We provide a detailed performance evaluation of the proposed selection algorithms to determine their impact on the performance of the designed hybrid middleware which we further compare to state-of-the art solutions.

Vertex-centric graph processing systems such as Pregel, PowerGraph, or GraphX recently gained popularity due to their superior performance of data analytics on graph-structured data. These systems exploit the graph structure to improve data access locality during computation, making use of specialized graph partitioning algorithms. Recent partitioning techniques assume a uniform and constant amount of data exchanged between graph vertices (i.e., uniform vertex traffic) and homogeneous underlying network costs. However, in real-world scenarios vertex traffic and network costs are heterogeneous. This leads to suboptimal partitioning decisions and inefficient graph processing. To this end, we designed GrapH, the first graph processing system using vertex-cut graph partitioning that considers both, diverse vertex traffic and heterogeneous network, to minimize overall communication costs. The main idea is to avoid frequent communication over expensive network links using an adaptive edge migration strategy. Our evaluations show an improvement of 60% in communication costs compared to state-of-the-art partitioning approaches.

With the fast adoption of location-enabled devices, Location-based Applications (LBAs) have become widely popular. While LBAs enable highly useful concepts such as geo-social networking, their use also raises serious privacy concerns as it involves sharing of location data with non-trusted third parties. In this respect, we propose an approach that protects the frequently visited locations of users, e.g., a bar, against inferences from long-term monitoring of their location data. Such inferences equate a privacy leak as they reveal a user's personal behavior and interests to possibly malicious non-trusted parties. To this end, we first present a study of a dataset of location check-ins to show the existence of this threat among users of LBAs. We then propose our approach to protect visit-frequency of the users to different locations by distributing their location data among multiple third-party Location Servers. This distribution not only serves to avoid a single point of failure for privacy in our system, it also allows the users to control which LBA accesses what information about them. We also describe a number of possible attacks against our privacy approach and evaluate them on real-data from the check-ins dataset. Our results show that our approach can effectively hide the frequent locations while supporting good quality-of-service for the LBAs.

Code offloading strives for increasing the energy efficiency and execution speed of mobile applications on resource-constrained mobile devices. First approaches considered only a code offloading between two (or three) tiers, executing code either locally on the mobile device or remotely on a powerful server in the vicinity or in a distant cloud. However, new execution environments comprise multiple tiers, containing highly distributed heterogeneous resources.

Updating a network is an essential and continual task in the management of today's softwarized networks. When applying updates on distributed network elements, desired network properties, such as drop- and loop-freeness, might be transiently violated. Although being crucial, update consistency has yet been less considered in network management. In this paper, we argue for incorporating the particularities of update consistency into the reconfiguration process of continuous network management. We present a generic management architecture allowing for an appropriate selection of an update mechanism and its parameters based on expected inconsistency effects. We investigate update consistency for the case of multicast routing and show in an extensive analysis why simultaneous drop- and duplicate-freeness is not possible. We present an update procedure for multicast routing updates that identifies critical update steps, which are fed back into the reconfiguration process, along with a lightweight approach that allows for the selection of an update strategy, preventing either drops or duplicates. Furthermore, we present an optimization of an existing powerful, but resource-intensive update approach as well as an approach for in-network filtering of duplicates.

Recently, a new class of mobile applications has appeared that takes into account the behavior of physical phenomenon. Prominent examples of such applications include augmented reality applications visualizing physical processes on a mobile device or mobile cyber-physical systems like autonomous vehicles or robots. Typically, these applications need to solve partial differential equations (PDE) to simulate the behavior of a physical system. There are two basic strategies to numerically solve these PDEs: (1) offload all computations to a remote server, (2) solve the PDE on the resource-constrained mobile device. However, both strategies have severe drawbacks. Offloading will fail if the mobile device is disconnected, and resource constraints require to reduce the quality of the solution. Therefore, we propose a new approach for mobile simulations using a hybrid strategy that is robust to communication failures and can still benefit from powerful server resources. The basic idea of this approach is to dynamically decide on the placement of the PDE solver based on a prediction of the wireless link availability using Markov Chains. Our tests based on measurement in real cellular networks and real mobile devices show that this approach is able to keep deadline constraints in more than 61 % of the cases compared to a pure offloading approach, while saving up to 74 % of energy compared to a simplified approach.

End users execute today on their smart phones different kinds of mobile applications like calendar apps or high-end mobile games, differing in local resource usage. Utilizing local resources of a smart phone heavily, like playing high-end mobile games, drains its limited energy resource in few hours. To prevent the limited energy resource from a quick exhaustion, smart phones benefit from executing resource-intensive application parts on a remote server in the cloud (code offloading). During the remote execution on the remote server, a smart phone waits in idle mode until it receives a result. However, code offloading introduces computation and communication overhead, which decreases the energy efficiency and induces monetary cost. For instance, sending or receiving execution state information to or from a remote server consumes energy. Moreover, executing code on a remote server instance in a commercial cloud causes monetary cost. To keep consumed energy and monetary cost low, we present in this paper the concept of remote-side caching for code offloading, which increases the efficiency of code offloading. The remote-side cache serves as a collective storage of results for already executed application parts on remote servers, avoiding the repeated execution of previously run application parts. The smart phone queries the remote-side cache for corresponding results of resource-intensive application parts. In case of a cache hit, the smart phone gets immediately a result and continues the application execution. Otherwise, it migrates the application part and waits for a result of the remote execution. We show in our evaluation that the use of a remote-side cache decreases energy consumption and monetary cost for mobile applications by up to 97% and 99%, respectively.

The tremendous number of sensors and smart objects being deployed in the Internet of Things (IoT) pose the potential for IT systems to detect and react to live-situations. For using this hidden potential, complex event processing (CEP) systems offer means to efficiently detect event patterns (complex events) in the sensor streams and therefore, help in realizing a “distributed intelligence” in the IoT. With the increasing number of data sources and the increasing volume at which data is produced, parallelization of event detection is crucial to limit the time events need to be buffered before they actually can be processed. In this paper, we propose a pattern-sensitive partitioning model for data streams that is capable of achieving a high degree of parallelism in detecting event patterns, which formerly could only consistently be detected in a sequential manner or at a low parallelization degree. Moreover, we propose methods to dynamically adapt the parallelization degree to limit the buffering imposed on event detection in the presence of dynamic changes to the workload. Extensive evaluations of the system behavior show that the proposed partitioning model allows for a high degree of parallelism and that the proposed adaptation methods are able to meet a buffering limit for event detection under high and dynamic workloads.

Complex Event Processing (CEP) systems enable applications to react to live-situations by detecting event patterns (complex events) in data streams. With the increasing number of data sources and the increasing volume at which data is produced, parallelization of event detection is becoming of tremendous importance to limit the time events need to be buffered before they actually can be processed by an event detector - named event processing operator. In this paper, we propose a pattern-sensitive partitioning model for data streams that is capable of achieving a high degree of parallelism for event patterns which formerly could only be consistently detected in a sequential manner or at a low parallelization degree. Moreover, we propose methods to dynamically adapt the parallelization degree to limit the buffering imposed on event detection in the presence of dynamic changes to the workload. Extensive evaluations of the system behavior show that the proposed partitioning model allows for a high degree of parallelism and that the proposed adaptation methods are able to meet the buffering level for event detection under high and dynamic workloads.

With the increasing popularity of Software-defined networks (SDN), TCAM memory of switches can be directly accessed by a publish/subscribe middleware to perform filtering operations at low latency. This way two important requirements for a publish/subscribe middleware can be fulfilled: namely bandwidth efficiency and line-rate performance in forwarding messages between producers and consumers. Nevertheless, it is challenging to sustain line-rate performance in the presence of dynamic changes in the interest of producers and consumers. In this paper, we propose and evaluate the PLEROMA middleware to realize publish/subscribe at line-rate and bandwidth efficiently in SDN. PLEROMA offers methods to efficiently reconfigure a deployed topology in the presence of dynamic subscriptions and advertisements. Furthermore, PLEROMA ensures interoperability and independent reconfiguration of multiple controlled SDN networks.

Modern mobile devices like smart phones and tablets are equipped with powerful processing and memory resources, enabling resource-intensive mobile applications such as high-end mobile games. The main limitation, however, remains the energy resource. To improve the energy efficiency, code offloading

While location-based services are already well established in outdoor scenarios, they are still not available in indoor environments. The reason for this can be found in two open problems: First, there is still no off-the-shelf indoor positioning system for mobile devices and, second, indoor maps are not publicly available for most buildings. While there is an extensive body of work on the first problem, the efficient creation of indoor maps remains an open challenge. We tackle the indoor mapping challenge in our MapGENIE approach that automatically derives indoor maps from traces collected by pedestrians moving around in a building. Since the trace data is collected in the background from the pedestrians' mobile devices, MapGENIE avoids the labor-intensive task of traditional indoor map creation and increases the efficiency of indoor mapping. To enhance the map building process, MapGENIE leverages exterior information about the building and uses grammars to encode structural information about the building. Hence, in contrast to existing work, our approach works without any user interaction and only needs a small amount of traces to derive the indoor map of a building. To demonstrate the performance of MapGENIE, we implemented our system using Android and a foot-mounted IMU to collect traces from volunteers. We show that using our grammar approach, compared to a purely trace-based approach we can identify up to four times as many rooms in a building while at the same time achieving a consistently lower error in the size of detected rooms.

The relevance of graphical functions in vehicular applications has increased significantly during the few last years. Modern cars are equipped with multiple displays used by different applications such as speedometer or navigation system. However, so far applications are restricted to using dedicated displays. In order to increase flexibility, the requirement of sharing displays between applications has emerged. Sharing displays leads to safety and security concerns since safety-critical applications as the dashboard warning lights share the same displays with uncritical or untrusted applications like the navigation system or third-party applications. To guarantee the safe and secure sharing of displays, we present a formal model for defining and controlling the access to display areas in this paper. We prove the validity of this model, and present a proof-of-concept implementation to demonstrate the feasibility of our concept.

With the proliferation of mobile devices and sensors, complex event proceesing (CEP) is becoming increasingly important to scalably detect situations in real time. Current CEP systems are not capable of dealing efficiently with highly dynamic mobile consumers whose interests change with their location. We introduce the distributed mobile CEP (MCEP) system which automatically adapts the processing of events according to a consumer's location. MCEP significantly reduces latency, network utilization, and processing overhead by providing on-demand and opportunistic adaptation algorithms to dynamically assign event streams and computing resources to operators of the MCEP system.

The provisioning of basic security mechanisms such as authentication and confidentiality is highly challenging in a content-based publish/subscribe system. Authentication of publishers and subscribers is difficult to achieve due to the loose coupling of publishers and subscribers. Likewise, confidentiality of events and subscriptions conflicts with content-based routing. This paper presents a novel approach to provide confidentiality and authentication in a broker-less content-based publish/subscribe system. The authentication of publishers and subscribers as well as confidentiality of events is ensured, by adapting the pairing-based cryptography mechanisms, to the needs of a publish/subscribe system. Furthermore, an algorithm to cluster subscribers according to their subscriptions preserves a weak notion of subscription confidentiality. In addition to our previous work , this paper contributes 1) use of searchable encryption to enable efficient routing of encrypted events, 2) multicredential routing a new event dissemination strategy to strengthen the weak subscription confidentiality, and 3) thorough analysis of different attacks on subscription confidentiality. The overall approach provides fine-grained key management and the cost for encryption, decryption, and routing is in the order of subscribed attributes. Moreover, the evaluations show that providing security is affordable w.r.t. 1) throughput of the proposed cryptographic primitives, and 2) delays incurred during the construction of the publish/subscribe overlay and the event dissemination.

Many location-based applications such as geo-social networks rely on location services storing mobile object positions. To update positions on location servers, position update protocols are used. On the one hand, these protocols decide when an update has to be sent to ensure a certain quality of position information. On the other hand, they try to minimize the energy consumption of the mobile device by reducing communication to a minimum.

The advent of mobile phones paved the way for a new paradigm for gathering sensor data termed Public Sensing (PS). PS uses built-in sensors of mobile devices to opportunistically gather sensor data. For instance, the microphones of a crowd of mobile phones can be used to capture sound samples, which can be used to construct a city noise map. A great challenge of PS is to reduce the energy consumption of mobile devices since otherwise users might not be willing to participate. One crucial part in the overall power consumption is the energy required for the communication between the mobile devices and the infrastructure. In particular, the communication required for sending sensing queries to mobile devices has been largely neglected in the related work so far. Therefore, in this paper, we address the problem of minimizing communication costs for the distribution of sensing queries. While existing systems simply broadcast sensing queries to all devices, we use a selective strategy by addressing only a subset of devices. In order not to negatively affect the quality of sensing w.r.t. completeness, this subset is carefully chosen based on a probabilistic sensing model that defines the probability of mobile devices to successfully perform a given sensing query. Our evaluations show that with our optimized sensing query distribution, the energy consumption can be reduced by more than 70% without significantly reducing the quality of sensing.

The proliferation of modern smartphones has given rise to Public Sensing, a new paradigm for data acquisition systems utilizing smartphones of mobile participants. In this paper, we present DrOPS, a system for improving the efficiency of data acquisition in Public Sensing systems. DrOPS utilizes a model-driven approach, where the number of required readings from mobile smartphones is reduced by inferring readings from the model. Furthermore, the model can be used to infer readings for positions where no sensor is available. The model is directly constructed from the observed phenomenon in an online fashion. Using such models together with a client-specified quality bound, we can significantly reduce the effort for data acquisition while still reporting data of required quality to the client. To this effect, we develop a set of online learning and control algorithms to create and validate the model of the observed phenomenon and present a sensing task execution system utilizing our algorithms in this paper. Our evaluations show that we obtain models in a matter of just hours or even minutes. Using the model-driven approach for optimizing the data acquisition, we can save up to 80% of energy for communication and provide inferred temperature readings for uncovered positions matching an error-bound of 1°C up to 100 % of the time.

Nowadays, millions of users share their complete movement trajectory online when using real-time traffic monitoring applications, pay-as-you-drive insurances, or when sharing their last road trip with friends. However, many users still hesitate to use location-based applications as they are not willing to reveal, for instance, their driving behavior or the occurrence of a speeding violation. Therefore, we present novel speed protection algorithms protecting users from revealing a violation of given speed limits when using location-based applications. Our algorithms support time-based and distance-based position updates. To protect positions indicating a speeding violation, we either adjust temporal information by delaying position updates or adjust their spatial information. We evaluate our algorithms by using real world traces and show that the protected movement trajectory of the user is of high quality even after removing speeding violations.

Complex pervasive applications need to be distributed for two main reasons: due to the typical resource restrictions of mobile devices, and to use local services to interact with the immediate environment. To set up such an application, the distributed components require spontaneous composition. Since dynamics in the environment and device failures may imply the unavailability of components and devices at any time, finding, maintaining, and adapting such a composition is a nontrivial task. Moreover, the speed of such a configuration process directly influences the user since in the event of a configuration, the user has to wait. In this article, we introduce configuration algorithms for homogeneous and heterogeneous environments. We discuss a comprehensive approach to pervasive application configuration that adapts to the characteristics of the environment: It chooses the most efficient configuration method for the given environment to minimize the configuration latency. Moreover, we propose a new scheme for caching and reusing partial application configurations. This scheme reduces the configuration latency even further such that a configuration can be executed without notable disturbance of the user.

Processes in the healthcare domain are characterized by coarsely predefined recurring procedures that are flexibly adapted by the personnel to suite-specific situations. In this setting, a workflow management system that gives guidance and documents the personnel's actions can lead to a higher quality of care, fewer mistakes, and higher efficiency. However, most existing workflow management systems enforce rigid inflexible workflows and rely on direct manual input. Both are inadequate for healthcare processes. In particular, direct manual input is not possible in most cases since (1) it would distract the personnel even in critical situations and (2) it would violate fundamental hygiene principles by requiring disinfected doctors and nurses to touch input devices. The solution could be activity recognition systems that use sensor data (e.g., audio and acceleration data) to infer the current activities by the personnel and provide input to a workflow (e.g., informing it that a certain activity is finished now). However, state-of-the-art activity recognition technologies have difficulties in providing reliable information. We describe a comprehensive framework tailored for flexible human-centric healthcare processes that improves the reliability of activity recognition data. We present a set of mechanisms that exploit the application knowledge encoded in workflows in order to reduce the uncertainty of this data, thus enabling unobtrusive robust healthcare workflows. We evaluate our work based on a real-world case study and show that the robustness of unobtrusive healthcare workflows can be increased to an absolute value of up to 91% (compared to only 12% with a classical workflow system). This is a major breakthrough that paves the way towards future IT-enabled healthcare systems.

Utilizing peoples' mobile devices for gathering sensor data has attracted a lot of attention within the last few years. As a result, a great variety of systems for sensing environmental phenomena like temperature or noise have been proposed. However, most of these systems do not take into account that mobile devices have only limited energy resources. For instance, an often assumed prerequisite is that mobile devices are always aware of their position. Given the fact that a position fix is a very energy consuming operation, continuous positioning would quickly drain a device's battery. Since the owners of the mobile devices will not tolerate a significant reduction of the devices' battery lifetime, such an approach is not suitable. To address this issue we present PSense, a flexible system for efficiently gathering sensor data with mobile devices. By avoiding unnecessary position fixes, PSense reduces the energy consumption of mobile devices by up to 70% compared to existing mobile sensing approaches. This is achieved by introducing an adaptive positioning mechanism and by utilizing energy efficient short-range communication to exchange position related information.

Nowadays, rich information about the context of mobile users is directly captured on the users' mobile phones in real-time. Especially, discrete context (e.g., the user's activity) has become highly interesting for many applications since it provides an intuitive and human-understandable description of the user's current state. However, while sensing is executed locally on the mobile device, changes of user context need to be distributed from the device to a large number of interested consumers, e.g., the friends in an online social network. This produces a large overhead for the continuous transmission of context updates and represents a serious challenge for the limited energy budget of battery-equipped mobile devices. In this paper, we propose different strategies for energy-efficient context updates. We present a number of update protocols that are characterized by an inherent trade-off between quality of context and message overhead. To this end, we investigate update criteria that allow consumers of context information to express their tolerance towards the inaccurateness of received context, and we propose update protocols that exploit this tolerance to save updates and, thus, energy. In our evaluation we analyse our update protocols based on a real-world trace of user activities and show that applications can save more than 80% of the messages when tolerating a minor degradation of the context quality only.

Recent forecasts predict that the amount of cellular data traffic will significantly increase within the next few years. The reason for this trend is on the one hand the high growth rate of mobile Internet users and on the other hand the growing popularity of high bandwidth streaming applications. Given the fact that cellular networks (e.g. UMTS) have only limited capacity, the existing network infrastructure will soon reach its limits. As a result, the concept of traffic offloading attracts more and more attention in research since it aims at the reduction of cellular traffic by shifting it to local-area networks like Wifi. One particular form of traffic offloading is known as opportunistic traffic offloading and follows the basic idea to shift traffic from the cellular network to the level of inter-device communication of mobile devices. To perform opportunistic traffic offloading in an efficient way, assumptions about the prospective inter-device connectivity of the mobile devices have to be made. In general, the more inter-device connections are possible the more traffic can be offloaded. To utilize this fact, we developed the TOMP system. TOMP is the first opportunistic traffic offloading system that uses movement predictions of mobile users to analyze the prospective inter-device connectivity. In this paper we propose three different metrics for analyzing movement predictions and present an algorithm, which uses these metrics to utilize an efficient opportunistic traffic offloading. To evaluate TOMP, we show by simulation that we can save up to 40% of cellular messages in comparison to a typical cellular network.

As mobile devices have become powerful sensor platforms, new applications have emerged which continuously stream mobile user context (location, activities, etc.). However, energy is a limited resource on battery-equipped mobile devices. Especially frequent transmissions of context updates over energy-expensive wireless channels drain the battery of mobile devices in an uncontrolled manner. It is a fundamental algorithmic challenge to design protocols such that users can control the energy consumption on mobile devices while, at the same time, optimizing the quality of mobile applications. To address this trade-off in the area of context update protocols, we propose a novel protocol that maximizes the context accuracy perceived by a remote consumer while guaranteeing that the consumed energy stays under a given limit. Our update protocol exploits predictions about a user's future behaviour to give priority to the most effective context updates. In our evaluation, we apply our predictive update protocol to a real-world trace of user context and show that the context accuracy is significantly increased compared to an update protocol which operates without predictions under the same energy budget.

Location-based applications such as Facebook Places, Foursquare, or Loopt attract millions of users by implementing point of interest finders, friend finders, geosocial networking, etc. Typically, these applications act as clients to a location service such as Google Latitude or Yahoo Fire Eagle, which manage mobile object positions and ensure the scalability to provide various clients with mobile object positions. However, exposing precise user positions raises user privacy concerns, especially if location service providers are not fully trusted, and private position information could be “lost”, leaked, stolen, etc. To enable the secure management of private user positions on non-trusted location servers (LSs), we present novel position sharing approaches based on the concept of multi-secret sharing. Our approaches split up a precise user position into position shares, which are distributed to different LSs of different providers such that a compromised provider only reveals user positions with degraded precision. On the other hand, clients can combine several shares queried from different LSs to increase their provided precision without the need to store precise information at a single LS. We propose two position sharing approaches: PShare-SLM is the first position sharing approach presented so far for symbolic location models. For geometric location models, we present PShare-GLM, which improves existing geometric position sharing approaches [1] by considering continuous position updates and by increasing the robustness against various attacks.

Sensors of various modalities and capabilities, especially cameras, have become ubiquitous in our environment. Their intended use is wide ranging and encompasses surveillance, transportation, entertainment, education, healthcare, emergency response, disaster recovery, and the like. Technological advances and the low cost of such sensors enable deployment of large-scale camera networks in large metropolises such as London and New York. Multimedia algorithms for analyzing and drawing inferences from video and audio have also matured tremendously in recent times. Despite all these advances, large-scale reliable systems for media-rich sensor-based applications, often classified as situation-awareness applications, are yet to become commonplace. Why is that? There are several forces at work here. First, the system abstractions are just not at the right level for quickly prototyping such applications on a large scale. Second, while Moore's law has held true for predicting the growth of processing power, the volume of data that applications are called upon to handle is growing similarly, if not faster. Enormous amount of sensing data is continually generated for real-time analysis in such applications. Further, due to the very nature of the application domain, there are dynamic and demanding resource requirements for such analyses. The lack of right set of abstractions for programing such applications coupled with their data-intensive nature have hitherto made realizing reliable large-scale situation-awareness applications difficult. Incidentally, situation awareness is a very popular but ill-defined research area that has attracted researchers from many different fields. In this paper, we adopt a strong systems perspective and consider the components that are essential in realizing a fully functional situation-awareness system.

Complex Event Processing (CEP) is of increasing importance in many industrial applications to integrate a huge number of events in a scalable manner. A core challenge towards scalable CEP is to efficiently distribute the rules which define how correlations between events can be detected within an event processing network. Although significant progress has been made recently, there remains a fundamental gap in supporting requirements that emerge from deploying CEP over heterogeneous and independent processing environments. Heterogeneity typically imposes many constraints on the placement of rules, which increases the complexity of the underlying optimization problem and cannot be handled efficiently by existing solutions. In this paper we examine the distributed placement, migration and optimization of rules in the context of the constraint optimization problem to minimize network usage. We propose and evaluate a placement algorithm that efficiently finds valid solutions in scenarios where the solution space is heavily restricted by constraints. The algorithm operates in a decentralized way and is adaptive to dynamic changes of processing nodes, rules, and load characteristics of the event processing network. The proposed rule migration policies resolve invalid placements quickly and thus ensure high availability. The evaluations show that the proposed algorithm is able to efficiently find near optimum solutions within heavy constraint-driven network conditions.

Many application classes such as monitoring applications, involve processing a massive amount of data from a possibly huge number of data sources. Complex Event Processing (CEP) has evolved as the paradigm of choice to determine meaningful situations (complex events) by performing stepwise correlation over event streams. To keep up with the high scalability demands of growing input streams, recent approaches distribute event correlation over several correlation nodes. However, already a failure of a single correlation node impacts the correctness of the final correlation result. In this paper, we illustrate the importance of a strong reliability semantics for CEP in the context of a monitoring application in a distributed production environment. Strong reliability ensures each complex event is detected and delivered exactly once to each application entity, and cannot be guaranteed by the naive application of established replication principles. We present a replication scheme which ensures strong reliability in an asynchronous system model and can be applied to an arbitrary distributed CEP system. The algorithm tolerates f simultaneous failures by introducing f additional replicas for each correlation node. We prove correctness as well as evaluate the overhead introduced by the algorithm. Results show, that the overhead scales linearly with the number of deployed replicas and the node failure rate.

Network emulation is an efficient method for evaluating distributed applications and communication protocols by combining the benefits of real world experiments and network simulation. The process of network emulation involves the execution of connected instances of the software under test (called virtual nodes) in a controlled environment. In previous work, we introduced an approach to minimize the runtime of network emulation experiments based on prior known average resource requirements of virtual nodes. In this paper, we introduce NETbalance, a novel approach to runtime reduction for experiments with unknown or varying resource requirements. NETbalance migrates virtual nodes during an experiment to distribute the load evenly across the physical nodes, avoiding overloaded nodes and exploiting the idle resources on underloaded nodes for speeding up the experiment execution. We make the following contributions: First, we present an emulation architecture for efficiently supporting live migration of virtual nodes. Second, we propose a cost model for determining the runtime reduction achieved through the migration. Third, we introduce an algorithm for calculating placements that minimize the experiment runtime. Our evaluations of the NETbalance prototype show, that it is able to reduce the experiment runtime by up to 70%.

The on-line processing of high volume data streams is a prerequisite for many modern applications relying on real-time data such as global sensor networks or multimedia streaming. In order to achieve efficient data processing and scalability w.r.t. the number of distributed data sources and applications, in-network processing of data streams in an overlay network of data processing operators has been proposed. For such stream processing overlay networks, the placement of operators onto physical hosts plays an important role for the resulting quality of service - in particular, the end-to-end latency - and network load. To this end, we present an enhanced placement algorithm that minimizes the network load put onto the system by a stream processing task under user-defined delay constraints in this paper. Our algorithm finds first the optimal solution in terms of network load and then degrades this solution to find a constrained optimum. In order to reduce the overhead of the placement algorithm, we included mechanisms to reduce the search space in terms of hosts that are considered during operator placement. Our evaluations show that this approach leads to an operator placement of high quality solution while inducing communication overhead proportional only to a small percentage of the total hosts.

With the increasing proliferation of small and cheap GPS receivers, a new way of generating road maps could be witnessed over the last few years. Participatory mapping approaches like OpenStreetMap introduced a way to generate road maps collaboratively from scratch. Moreover, automatic mapping algorithms were proposed, which automatically infer road maps from a set of given GPS traces. Nevertheless, one of the main problems of these maps is their unknown quality in terms of accuracy, which makes them unreliable and, therefore, not applicable for the use in critical scenarios. To address this issue, we propose MapCorrect: An automatic map correction and validation system. MapCorrect automatically collects GPS traces from people's mobile devices to correct a given road map and validate it by identifying those parts of the map that are accurately mapped with respect to some user provided quality requirements. Since fixing a GPS position is a battery draining operation, the collection of GPS data raises concerns about the energy consumption of the participating mobile devices. We tackle this issue by introducing an optimized sensing mechanism that gives the mobile devices notifications indicating those parts of the map that are considered as sufficiently mapped and, therefore, require no further GPS data for their validation. Furthermore, we show by simulation that using this approach up to 50% of the mobile phones' energy can be saved while not impairing the effectiveness of the map correction and validation process at all.

Public Sensing is a new paradigm for developing large-scale sensor networks at low cost by utilizing mobile phones that are already surrounding us in our everyday lives. In this paper we present a sensor network abstraction layer for creating flexible public sensing systems that can execute arbitrary queries. To this effect we develop several algorithms to select mobile nodes for executing a query. These algorithms allow a user to define a trade-off between quality and efficiency of query execution by choosing an appropriate algorithm. Our evaluations show that we can achieve a 99% increase in efficiency with the most efficient approaches and only about 10% decrease in result quality under worst conditions.

Many novel location-based services (LBS) such as a friend finder service require knowledge about the positions of mobile users. Usually, location services are used to manage these positions, and for providing basic functionality like spatial range queries or spatial events to the LBS. Managing and using the positions of mobile users raises privacy issues, in particular, if the providers of LBS and location services are only partially trusted. Many different approaches for preserving a user's privacy have been proposed in the literature, e.g. location obfuscation and the k-anonymity concept. However, most of them are not suitable if both LBS and location service providers are non-trusted. In contrast to these approaches, we present a novel approach for the secure management of private position information in partially trusted system environments. The main contribution in this paper is a position sharing concept which allows for the distribution of position information (shares) of strictly limited accuracy onto several location servers of different providers. With this approach, a compromised server will only reveal information of limited accuracy. Moreover, we will show how position shares of coarse granularity from multiple location servers can be fused into information of higher precision to satisfy the accuracy requirements of different LBS.

This paper introduces mechanisms for the automated detection of mobile objects in urban areas. Widely available devices such as mobile phones with integrated proximity sensors such as RFID readers or Bluetooth cooperatively perform sensing operations to discover mobile objects. In this paper, we propose a coverage metric for assessing the completeness of sensing that considers spatial and temporal aspects. To maximize coverage while minimizing energy consumption of mobile nodes, we propose both a centralized and a distributed coordination algorithm for selecting nodes that need to sense. Moreover, we present strategies that allow selected nodes to perform efficient sense operations. By extensive simulations, we show that distributed coordination achieves drastic energy savings of up to 63%, while limiting the coverage loss to 13%. Moreover, we show that the centralized algorithm loses less than 1% coverage compared to the maximum possible coverage.

Context-based communication allows for the dissemination of messages to mobile users with a specified context, i.e. at a location and with certain attribute values. This enables, e.g., a message to students on campus attending a certain class, with information about a study group for an upcoming exam. An overlay network of context-aware routers efficiently disseminate the messages to all matching receivers. Directed forwarding of such messages requires that the routers maintain knowledge about the contexts of connected users. Global knowledge, i.e., each router knowing about every user, scales poorly, though, because of the necessary updates.

SUMMARY Current distributed publish/subscribe systems consider all participants to have similar QoS requirements and contribute equally to the system's resources. However, in many real‐world applications, the message delay tolerance of individual participants may differ widely. Disseminating messages according to individual delay requirements not only allows for the satisfaction of user‐specific needs, but also significantly improves the utilization of the resources that participants contribute to a publish/subscribe system. In this article, we propose a peer‐to‐peer‐based approach to satisfy the individual delay requirements of subscribers in the presence of bandwidth constraints. Our approach allows subscribers to dynamically adjust the granularity of their subscriptions according to their bandwidth constraints and delay requirements. Subscribers maintain the overlay in a decentralized manner, exclusively establishing connections that satisfy their individual delay requirements, and that provide messages exactly meeting their subscription granularity. The evaluations show that for many practical workloads, the proposed publish/subscribe system can scale up to a large number of subscribers and performs robustly in a very dynamic setting. Copyright © 2011 John Wiley & Sons, Ltd.

Continuous queries are often employed to monitor the locations of mobile objects (MOs), which are determined by sensing devices like GPS receivers. In this paper, we tackle two challenges in processing continuous range queries (CRQs): coping with data uncertainty inherently associated with location data, and reducing the energy consumption of battery-powered MOs. We propose the concept of spatiotemporal tolerance for CRQ to relax a query's accuracy requirements in terms of a maximal acceptable error. Unlike previous works, our definition considers tolerance in both the spatial and temporal dimensions, which offers applications more flexibility in specifying their individual accuracy requirements. As we will show, these tolerance bounds can provide well-defined query semantics in spite of different sources of data uncertainty. In addition, we present efficient algorithms that carefully control when an MO should sense or report a location, while satisfying these tolerances. Thereby, we particularly reduce the number of position sensing operations substantially, which constitute a considerable source of energy consumption. Extensive simulations confirm that the proposed algorithms result in large energy savings compared to nontolerant query processing.

Wireless Mesh Networks are cost-efficient medium-scale networks that have the potential to serve as an infrastructure for advanced location-based services. As a basis for these services we present a routing algorithm that allows to address intuitive symbolic coordinates. This algorithm is based on a proactively maintained geographic routing structure that mimics the structure of a symbolic location model. Message forwarding is done greedily along short paths defined by a symbolic location model and if this fails, through an hierarchical overlay network built by selected mesh routers. We show how a geocast communication mechanism that allows to send messages to all hosts within a specific location can be implemented with this routing algorithm. In extensive evaluations we show that a low proactive routing overhead allows to achieve high message delivery rates even in case of mobility. Moreover, we show that the paths achieved are only 25% longer than the theoretic optimal paths for a wide range of simulation settings.

Real-time diagnostic simulations are one challenging application domain that is expected to introduce high requirements to global sensor applications. Besides having hard constraints on latency bounds at which data needs to be processed, such simulation applications will impose high requirements with respect to available bandwidth. Predictors, originally introduced in the domain of wireless sensor networks for energy saving, are one appealing solution to provide real-time estimates and at the same time significantly reduce the data rates. While in the setting of wireless sensor networks many prediction models have been analyzed, their behavior and use is unclear when applied to distributed data streams where aggregation results are typically processed over multilevel hierarchies. In the context of weather simulations, we propose a distributed R-Tree-based aggregation algorithm that allows for efficient reuse of aggregate queries. In the setting of real temperature readings taken from weather stations during one month, we study the trade-off between updates of the prediction model and the precision of the predicted values. Our evaluations indicate that even in situations where complex prediction models are expected to perform best, simple prediction models give higher benefits with respect to saving bandwidth while providing similar data accuracy.

Application areas like global sensor networks and data stream processing involve the on-line processing of large amounts of data in an overlay network of operators on top of the Internet infrastructure. Trying to fulfill QoS guarantees in such networks is a challenging task that should be realized under the requirement for optimal usage of common resources in the network. Therefore in this paper, we formalize a constrained optimization problem for the placement of operators in an overlay network which strives for satisfying user QoS constraints subject to latency, while minimizing the network load induced by the deployment of the operators in the network. Since the initial problem is NP-hard, we solve at a first step the problem in an intermediate continuous latency space and then we map the continuous solution to its discrete variant. Our evaluations provide an analysis about the inherent interdepedence between the two metrics, network usage and latency, subject to this paper and furthermore show that our algorithm achieves a good balance between the user requirements and the usage of the network resources.

Processing streams of data in an overlay network of operators distributed over a wide-area network is a common idea shared by different applications such as distributed event correlation systems and large-scale sensor networks. In order to utilize network resources efficiently and allow for the parallel deployment of a large number of large-scale operator networks, suitable placement algorithms are vital that place operators on physical nodes. In this paper, we present a distributed placement algorithm that minimizes the bandwidth-delay product of data streams between operators of the network in order to reduce the induced network load. Since the fundamental optimization problem is NP-hard, we propose a heuristic solution. First, we calculate an optimal solution in an intermediate continuous search space, called latency space. Subsequently the continuous solution is mapped to the physical network. Our evaluations show that this algorithm reduces the resulting network load significantly compared to state of the art algorithms and achieves results close to the optimum.

Scaling heterogeneous information systems (HIS) to thousands of sources poses particular challenges to source discovery. It requires a powerful formalism for describing the contents of the sources in a concise manner and for formulating compatible queries as well as a suitable structure for indexing and retrieving the source descriptions efficiently.

Distributed Hash Table (DHT)-based peer-to-peer information discovery systems have emerged as highly scalable systems for information storage and discovery in massively distributed networks. Originally DHTs supported only point queries. However, recently they have been extended to support more complex queries, such as multiattribute range (MAR) queries. Generally, the support for MAR queries over DHTs has been provided either by creating an individual index for each data attribute or by creating a single index using the combination of all data attributes. In contrast to these approaches, we propose to create and modify indices using the attribute combinations that dynamically appear in MAR queries in the system. In this paper, we present an adaptive information discovery system that adapts the set of indices according to the dynamic set of MAR queries in the system. The main contribution of this paper is a four-phase index adaptation process. Our evaluations show that the adaptive information discovery system continuously optimizes the overall system performance for MAR queries. Moreover, compared to a non-adaptive system, our system achieves several orders of magnitude improved performance.

Peer-to-peer (P2P) networks allow for efficient information discovery in large-scale distributed systems. Although point queries are well supported by current P2P systems - in particular systems based on distributed hash tables (DHTs) -, providing efficient support for more complex queries remains a challenge. Our research focuses on the efficient support for multiattribute range (MAR) queries over DHT-based information discovery systems. Traditionally, the support for MAR queries over DHTs has been provided either by creating an individual index for each data attribute or by creating a single index using the combination of all data attributes. In contrast to these approaches, we propose to create a set of indices over selected attribute combinations. In order to limit the overhead induced by index maintenance, the total number of created indices has to be limited. Thus, the resulting problem is to create a limited number of indices such that the overall system performance is optimal for MAR queries. In this paper, we propose an index recommendation tool that implements heuristic solutions to this NP-hard problem. Our evaluations show that these heuristics lead to a close-to-optimal system performance for MAR queries.

Simulation is a fundamental means for evaluating mobile applications based on ad-hoc networks. This has led to the design of a large number of mobility models for simulating realistic user movement under physical constraints (obstacles, acceleration, inertia etc.). In recent years, the new breed of social mobility models (SMMs) has risen. These SMMs model the social aspects of human mobility, i.e. which users meet, when and how often. Such information is indispensable for the simulation of a wide range of socially-aware communication protocols mostly based on delay-tolerant networks, including opportunistic ad-hoc routing and data dissemination systems. Each SMM needs a model of the relations between a set of relevant people (called social network model - SNM) in order to simulate their mobility. Existing SMMs lack flexibility since each of them is implicitly restricted to a specific, simplifying SNM. We present GeSoMo, a new SMM that separates the core mobility model from the structural description of the social network underlying the simulation. This simple and elegant design principle gives GeSoMo generalizing power: Arbitrary existing and future SNMs can be used without changing GeSoMo itself. Our evaluation results show that GeSoMo produces simulations that are coherent with a broad range of empirical data describing real-world human social behavior and mobility.

In this paper we introduce mechanisms for automated mapping of urban areas that provide a virtual sensor abstraction to the applications. We envision a participatory system that exploits widely available devices as mobile phones to cooperatively read environmental conditions as air quality or noise pollution, and map these measurements to stationary virtual sensors. We propose spatial and temporal coverage metrics for measuring the quality of acquired sensor data that reflect the conditions of urban areas and the uncontrolled movement of nodes. To achieve quality requirements and efficiency in terms of energy consumption, this paper presents two algorithms for coordinating sensing. The first is based on a central control instance, which assigns sensing tasks to mobile nodes based on movement predictions. The second algorithm is based on coordination of mobile nodes in an ad-hoc network. By extensive simulations, we show that these algorithms achieve a high quality of readings, which is about 95% of the maximum possible. Moreover, the algorithms achieve a very high energy efficiency allowing for drastic savings compared to uncoordinated sensing.

Summary form only given. Most pervasive computing systems are context-aware and thus are able to dynamically adapt their behavior to context changes. For many applications the relevant context is limited in both size and scope. However there is an emerging class of applications whose context may include a huge amount of entities possibly dispersed over the entire globe. Those applications, including logistics, production systems, traffic control or energy management, rely on highly dynamic context information that is captured by a huge number of networked sensors and potentially shared by a wide spectrum of applications. Due to the distributed nature as well as the varying dynamics and quality of context information, scalable context management becomes a challenging task. In this talk we give an overview on context management and present some approaches to increase scalability. Finally, we will discuss future research directions in that field.

High level context recognition and situation detection are enabling technologies for unobtrusive mobile computing systems. Significant progress has been made in processing and managing context information, leading to sophisticated frameworks, middlewares, and algorithms. Despite great improvements, context aware systems still require a significantly increased recognition accuracy for high-level context information on uncertain sensor data to enable the robust execution of context-aware applications. Recently Adaptable Pervasive Workflows (APF)s have been presented as innovative programming paradigm for mobile context-aware applications. We propose a novel Flow Context System (FlowCon) that builds upon APFs. FlowCon uses structural information from the APF to increase accuracy of uncertain high-level context information up to 49%. This way we make an important step to enable robust execution of mobile context-aware applications.

The dissemination of messages according to clients' contexts (i.e., location and other attributes) opens up new possibilities in context-aware systems. While geocast or content-based publish/subscribe forward messages according to client location or attributes, respectively, neither uses a combination of the two. In this paper, we present this new communication paradigm and the challenges it poses. We also extend concepts from publish/subscribe networks to efficiently deal with highly dynamic user location to lower update rates by approximating the user's location. This reduces update rates by between 25% and 90%, depending on the granularity of the approximation.

Performance analysis and functionality testing are major parts of developing distributed software systems. Since the number of communicating software instances heavily influences the behavior of distributed applications and communication protocols, evaluation scenarios have to consider a large number of nodes. Network emulation provides an infrastructure for running these experiments using real prototype implementations in a controllable and realistic environment. Large-scale experiments, however, have a high resource consumption which often exceeds available physical testbed resources. Time dilation allows for reducing the resource demands of a scenario at the expense of the experiment's runtime. However, current approaches only consider a constant time dilation factor, which wastes a lot of resources in case of scenarios with varying load. We propose a framework for adaptive time virtualization that significantly reduces the runtime of experiments by improving resource utilization in network emulation testbeds. In this framework, resource demands are monitored and the time dilation factor is dynamically adapted to the required level. Our evaluation shows that adaptive virtual time in combination with our lightweight node virtualization architecture allows us to increase the possible scenario sizes by more than an order of magnitude and, at the same time, ensure unbiased emulation results. This represents an important contribution to making network emulation systems highly scalable.

In this paper we introduce a novel scenario for environmental sensing based on the combination of simple and cheap RFID-based sensors and mobile devices like mobile phones with integrated RFID readers. We envision a system that exploits the availability of these devices to cooperatively read sensors installed in the environment, and transmit the data to a server infrastructure. To achieve quality requirements and efficiency in terms of communication cost and energy consumption, this paper presents several algorithms for coordinating update operations. First, mobile nodes form an ad-hoc network for the cooperative management of requested update times to meet the desired update interval and to avoid redundant sensor reading and collisions during read operations. Second, besides this decentralized coordination algorithm, we also show a complementary algorithm that exploits infrastructure based coordination. By extensive simulations we show that our algorithms allow for autonomous operation and achieve a high quality of sensor updates where nearly 100% of the possible updates are performed. Moreover, the algorithms achieve a very high energy efficiency allowing for several hundred hours of operation assuming a typical battery of a mobile phone.

Mobile clients in context-aware systems benefit from the indirect addressing of users via their context (contextcast), such as addressing messages to all users in downtown Toronto whose age is below 35. There is, however, almost no support for a temporal decoupling in such a contextcast system, i.e.

Context-aware applications rely on models of the physical world. Within the Nexus project, we envision a World Wide Space which provides the conceptual and technological framework for integrating and sharing such context models in an open, global platform of context providers. In our ongoing research we tackle important challenges in such a platform including distributed processing of streamed context data, situation recognition by distributed reasoning, efficient management of context data histories, and quality of context information. In this paper we discuss our approach to cope with these challenges and present an extended Nexus architecture.

Moving objects databases (MODs) have been proposed for managing trajectory data, an important kind of information for pervasive applications. To save storage capacity, a MOD generally stores simplified trajectories only. A simplified trajectory approximates the actual trajectory of the mobile object according to a certain accuracy bound. In order to minimize the costs of communicating position information between mobile object and MOD, the trajectory simplification should be performed by the mobile object. To assure that the MOD always has a valid simplified trajectory of the remote object, we propose the generic remote trajectory simplification protocol (GRTS) allowing for computing and managing a simplified trajectory in such a system in real-time. We show how to combine GRTS with existing line simplification algorithms for computing the simplified trajectory and analyze trade-offs between the different algorithms. Our evaluations show that GRTS outperforms the two existing approaches by a factor of two and more in terms of reduction efficiency. Moreover, on average, the reduction efficiency of GRTS is only 12% worse compared to optimal offline simplification.

Most work in sensor networks tries to maximize network lifetime. However, for many applications the required lifetime is known in advance. Therefore, application quality should rather be maximized for that given time. Levels , the approach presented in this article, is a programming abstraction for energy-aware sensor network applications that helps to meet such a user-defined lifetime goal by deactivating optional functionality. With this programming abstraction, the application developer defines so-called energy levels . Functionality in energy levels is deactivated if the required lifetime cannot be met otherwise. The runtime system uses data about the energy consumption of different levels to compute an optimal level assignment that maximizes each node's quality for the time remaining. As described in this paper, Levels includes a completely distributed coordination algorithm that balances energy level assignments and keeps the application quality of the network roughly constant over time. In this approach, each node computes its schedule based on those of its neighbors. As the evaluation shows, applications using Levels can accurately meet given lifetime goals with only small fluctuations in application quality. In addition, the runtime overhead both for computation and for communication is negligible.

In this paper, we propose an overlay network supporting world-wide geographic messaging. Our approach is based on hierarchical symbolic coordinates like /usa/fl/miami/. Although hierarchical network topologies lend themselves to the implementation of such overlay networks, they may lead to bottlenecks at the root of the hierarchy, long message paths, and inefficient bandwidth utilization. To avoid these problems, we propose an overlay network that adapts its structure to the users' communication patterns by dynamically adding "shortcut" links to the hierarchy leading to a routing mesh. We present an algorithm that carefully selects shortcuts based on their utility to assure short message paths on the one hand and to reduce the induced overhead on the other hand. Through simulations we show that this approach decreases the average path length significantly and reduces network load to about 50% compared to hierarchical routing.

Space-partitioned Moving Objects Databases (SP-MODs) allow for the scalable, distributed management of large sets of mobile objects' trajectories by partitioning the trajectory data to a network of database servers.

In this paper, we present the system design and evaluation of a Space Filling Curve (SFC)-based P2P information discovery system OID. The OID system uses multiple SFCs to significantly optimize the performance of multi-attribute range queries, particularly for applications with a large number of data attributes where a single big SFC-based index is inefficient. The basic idea is to have multiple SFC based indices and select the best one to perform a query. We also introduce two tree-based query optimizations that increase the scalability of the system.

Boundary recognition is an important and challenging issue in wireless sensor networks when no coordinates or distances are available. The distinction between inner and boundary nodes of the network can provide valuable knowledge to a broad spectrum of algorithms. This paper tackles the challenge of providing a scalable and range-free solution for boundary recognition that does not require a high node density. Our solution approximates the boundary of the sensor network by determining the inner nodes using geometric constructions that guarantee that, for a given d, a node lies inside of the construction for a d-quasi unit disk graph model of the wireless sensor network. Moreover, such geometric constructions make it possible to compute a guaranteed distance from a node to the boundary. We provide a thorough evaluation of our approach and show that it is applicable to dense as well as sparse deployments.

Moving objects databases (MODs) store objects’ trajectories by spatiotemporal polylines that approximate the actual movements given by sequences of sensed positions. Determining such a polyline with as few vertices as possible under the constraint that it does not deviate by more than a certain accu

The lifetime requirements on wireless sensor networks often require the redundant deployment of sensor nodes with appropriate management mechanisms based on node clustering. Yet, existing clustering approaches do not take the primary task of sensor networks into account: performing relevant measurements. They usually form 'arbitrary' clusters, e.g., using connectivity information, and thus, the resulting measurements are often of only limited use to the applications. This problem can be avoided by considering application-specific semantics. For indoor applications, the notion of a room provides a natural unit of clustering since walls are constructed deliberately to ensure locality. This paper shows that it is feasible to automatically create clusters that reflect boundaries between rooms by analyzing the measurements of inexpensive, broadly available sensors. The paper first analyzes the applicability of statistical clustering methods and based on this analysis, it proposes and evaluates a lightweight approach to determine clusters in real deployments.

Virtual memory has been successfully used in different domains to extend the amount of memory available to applications. We have adapted this mechanism to sensor networks, where, traditionally, RAM is a severely constrained resource. In this paper we show that the overhead of virtual memory can be significantly reduced with compile-time optimizations to make it usable in practice, even with the resource limitations present in sensor networks.

In location-based services, continuous queries are often employed to monitor the locations of mobile objects that are determined by sensing devices like GPS receivers. Due to limited battery resources, it is important for these objects to acquire and report location data only if necessary. We study how these energy- consuming operations can be reduced with a controlled impact on query accuracy of continuous range queries (CRQs). Specifically, we develop uncertainty- aware tolerances, which are user-defined error bounds that provide correctness guarantees, with consideration of different sources of data uncertainty: sensing uncertainty, sampling uncertainty, and communication delay. Novel algorithms are developed to control carefully when an object should acquire and update a location, while satisfying these tolerances. Extensive simulations validate the effectiveness of our methods.

Performance analysis is a necessary step during the development of distributed applications and communication protocols. Network emulation testbeds provide synthetic, configurable environments for comparative performance measurements of real implementations. However, realistic scenarios require more communicating nodes than usual testbeds are able to provide. In order to enable scalable network emulation, various concepts for the visualization of nodes have been proposed. The overhead of visualization strongly impacts the total size of a scenario, that can be emulated on a given testbed. However, the overhead of different visualization approaches in the context of network emulation has not been compared directly so far. In this paper, we present a comparison of different virtual machine implementations (Xen, User Mode Linux) and our own virtual routing approach (NET). We discuss qualitative evaluation criteria and present a quantitative evaluation showing the efficiency of each approach in a traditional wired infrastructure-based and in a wireless ad hoc network emulation scenario. Our results give insights on which visualization approach is best suited for which kind of network emulation.

The performance of distributed algorithms in mobile ad hoc networks is strongly influenced by the connectivity of the network. In cases where the connectivity is low, network partitioning occurs. The mobility and the density of network nodes as well as the communication technology are fundamental properties that have a large impact on partitioning. A detailed characterization of this behavior helps to improve the performance of distributed algorithms. In this paper we introduce a set of metrics that characterize partitioning in mobile ad hoc networks. Based on an extensive simulation study we show the impact of node mobility, density and transmission range on the proposed metrics for a wide range of network scenarios.

Many location-based systems rely on fine-grained tracking of mobile objects that determine their own locations with sensing devices like GPS receivers. For these objects, energy is a very valuable and limited resource. A distance-based reporting protocol can be employed to reduce the energy they consume by sending position updates. However, the energy required for position sensing has not been considered in the past. In this paper, we study how the resulting energy consumption from both sensing and update operations can be reduced for distance-based reporting. We show that significant savings are achieved by sending position updates earlier than actually required. For uniform movement, we derive the minimal power consumption analytically. Subsequently, two novel online heuristics are proposed that control the sending of position updates at runtime. Their effectiveness is validated by extensive simulations.

In this paper we present Levels, a programming abstraction for energy-aware sensor network applications. Unlike most previous work it does not try to maximize network lifetime but rather helps to meet user-defined lifetime goals while maximizing application quality. Levels is targeted to applications where there is no redundancy and no node should fail early.

Geocast, which allows for forwarding messages to hosts residing at specified geographic areas, is a promising communication paradigm with a wide range of applications. Geocast target areas can be specified either by geometric figures or symbolic addresses, such as /usa/f 1/miami/market-street. In this paper, we present a novel geocast routing protocol for symbolically addressed messages. Compared to geocast protocols based on geometric information, our protocol can operate on simple symbolic location models, and message forwarding does not require costly geometric operations. The proposed protocol is based on an overlay network that is mapped to an IP-based network infrastructure. The overlay network is structured in a hierarchical fashion, to ensure a scalable global geocast service supporting also large target areas. Although our protocol does not rely on a layer 3 multicast protocol, we also show how to improve the performance of message forwarding by integrating a light-weight layer 3 multicast protocol. Our evaluations of the protocol underline the scalability of our approach and show good routing quality leading to short message paths. I.

Data Centric Storage (DCS) is a powerful storage paradigm for wireless ad hoc networks. In mobile ad hoc networks (MANETs), however, the mobility and varying density of nodes may significantly impact the efficiency of data access and the level of data consistency for existing DCS mechanisms. In this paper, we propose an efficient resilience mechanism for data centric storage that supports DCS in mobile environments. We introduce a novel indirection strategy that enables us to distinguish the storage of data at dedicated server nodes from the storage of additional information to locate these servers. Our approach places server location information dynamically in strategic parts of the network based on its current topology. Combining our server location advertisement with any geographic routing protocol, we provide a robust data update and query processing technique for data centric storage in MANETs. We show analytically and by means of experimental evaluations that, despite the additional indirection during packet forwarding, our approach provides superior storage and retrieval performance than the original DCS algorithm even for large amounts of dynamic data.

In the area of wireless sensor networks, cross-layer interactions are often preferred to strictly layered architectures. However, architectural properties such as modularity and the reusability of components suffer from such optimizations. In this paper we present TinyXXL that provides programming abstractions for data exchange, a form of cross-layer interaction with a large potential for optimizations. Our approach decouples components providing and using data, and it allows for automatic optimizations of applications composed of reusable components. Its runtime representation is efficient regarding memory consumption and processing overhead

Geocast is used to send messages to all hosts located in a geographic area. This target area can be defined either by geometric figures like polygons or by symbolic addresses like city names or room numbers. Geographic routing algorithms, which forward messages based on geographic information, can be used to forward geocast messages. If routing of symbolically addressed messages is based on geometric coordinates, complex mappings between symbolic addresses and their geometric extent as well as complex geometric operations are required. Therefore, we propose a routing algorithm for symbolically addressed geocast messages that operates directly on a symbolic location model. This approach does not require any geometric information for message forwarding, and forwarding decisions can be realized efficiently by comparably simple operations.

Mobility plays a major role in mobile ad hoc networks (MANETs) since it stresses networking tasks such as routing on one hand but aids to increase the network capacity and to overcome network partitioning on the other hand. To benefit from node mobility, a new class of MANET protocols and applications are designed to be delay-tolerant and mobility-aided. For delay-tolerant mobility-aided networking mobility on a large time-scale is a key feature. So far, in MANETs, the mobility is investigated on a short time-scale. That is why we present novel mobility metrics that quantify large time-scale mobility. Our approach is based on the pair-wise contacts between mobile nodes. We present a detailed statistical study of our novel metrics using the widely used random waypoint mobility model as an example. For the random waypoint model we introduce an analytical model, which allows protocol developers to analytically compute some of the designed metrics. In order to provide an easy access to these metrics in a network simulator, we provide a framework for ns-2.

Wireless sensor networks based on highly resource-constrained devices require symmetric cryptography in order to make them secure. Integral to this is the exchange of unique symmetric keys between two devices. In this paper, we propose a novel decentralized key exchange protocol that guarantees the confidentiality of a key exchange even if an attacker has compromised some of the devices in the network. A central objective of the protocol design was to minimize resource consumption on the individual devices. We evaluate the resource requirements of our protocol in terms of memory requirements, CPU usage and network traffic both through theoretical analysis and through simulations.

Reputation systems suffer from easy copying of recommendations and from recommenders attaching themselves to trustworthy recommenders to benefit from their good reputation. Electronic commerce in general, and electronic payment systems in particular, suffer from the uncertainty of potential customers about the reputation of online merchants and the quality of the offered goods or services. We address these issues to a certain degree by creating an originality statement in the payment process that is included in recommendations to prove that a particular recommendation is indeed linked to a real world transaction. We present the initial protocol and two variations and discuss their distinct features. Although the protocol is described working in conjunction with the SET payment scheme, it is easily applicable to other payment systems with the described features.

MANETs are used in situations where networks need to be deployed immediately but no network infrastructure is available. If MANET nodes have sensing capabilities, they can capture and communicate the state of their surroundings, including environmental conditions or objects in their proximity. If the sensed state information is propagated to a database to build a consistent model of the real world, a variety of promising context-aware applications becomes possible. We introduce a novel consistency concept that preserves the chronological ordering of sensed state transition events. Based on this concept, we propose a data replication algorithm for MANETs that guarantees the consistency concept without relying on synchronized clocks and show its correctness. Our simulation experiments show that replicated copies are updated regularly even if the network load in the system is high.

The proliferation of mobile devices has led to the creation of hoarding algorithms that attempt to mitigate the problems related with disconnected operation or with the operation in areas where bandwidth is either scarce or very expensive. Traditional hoarding approaches use probability access tables to determine what information needs to be sent to the mobile device, but fail to take the structured nature of data into account. In this paper, we present an enhanced hoarding approach for semistructured information that relies on the analysis of graphs to determine the information that needs to be hoarded. We show by means of experimental evaluations on Web pages that our approach outperforms other hoarding algorithms that treat information as the combination of unrelated items.

Applications in the pervasive computing domain are challenged by the dynamism in which their execution environment changes, e.g. due to user mobility. As a result, applications have to adapt to changes regarding their required resources. In this paper we present PCOM, a component system for pervasive computing. PCOM offers application programmers a high-level programming abstraction which captures the dependencies between components using contracts. The resulting application architecture is a tree formed by components and their dependencies. PCOM supports automatic adaptation in cases where the execution environment changes to the better or to the worse. User supplied as well as system provided strategies take users out of the control loop while offering flexible adaptation control.

No abstract available.

Distribution of data in mobile ad hoc networks is challenged when the mobility of nodes leads to frequent topology changes. Existing approaches so far address either the network partitioning problem or are capable of handling large amounts of data, but not both at the same time. In this paper, a novel approach is presented which is based on a negotiation scheme enhanced by an adaptive repetition strategy. Different strategies for the selection of repeated data are presented and evaluated. Simulation results show a reduction of data transfer volume compared to hyper-flooding by 30% to 40% even in the presence of frequent network partitions.

Pervasive computing environments add a multitude of additional devices to our current computing landscapes. Specialized embedded systems provide sensor information about the real world or offer a distinct functionality, e.g. presentation on a "smart wall". Spontaneous networking leads to constantly changing availability of services. This requires middleware support to ease application development. Additionally, we argue that an extensible middleware platform covering small embedded systems to fill-fledged desktop computers is needed. Such a middleware should provide easy-to-use abstractions to access remote services and device-specific capabilities. We present a micro-broker-based approach which meets these requirements by allowing uniform access to device capabilities and services through proxies and the integration of different interoperability protocols. A minimum configuration of the middleware can be executed on embedded systems. Resource-rich execution environments are supported by the extensibility of the middleware.

Comparative performance measurements of distributed applications and network protocols require the availability of appropriate network environments. Network emulation approaches offer a flexible way to mimic the properties of a variety of networks. Existing emulation tools work either with centralized real-time simulation components, limiting the scenario size and maximum traffic, or focus on the emulation of some network properties at a single point. We propose a tool for the realistic emulation of network links, and show how several emulated links can be combined to reproduce a comprehensive network model. In addition to that, the model can include changing network properties, e.g. emerging from mobile communication partners. This facilitates the distributed emulation of a comprehensive, dynamic network scenario to support repeatable performance measurements.

Location-aware services are a promising way of exploiting the special possibilities created by ubiquitous mobile devices and wireless communication. Advanced location-aware applications will require highly accurate information about the geographic location of mobile objects and functionality that goes beyond simply querying the user's position, for example determining all mobile objects inside a certain geographic area. In this paper, we propose a generic large-scale location service, which has been designed with the goal of managing the highly dynamic location information for a large number of mobile objects, thus providing a common infrastructure that can be employed by location-aware applications. We propose a hierarchical distributed architecture, which can efficiently process these queries in a scalable way. To be able to deal with the frequent updates and queries resulting from highly dynamic location information, we propose a data storage component, which makes use of a main memory database.

Choosing appropriate information dissemination strategies is crucial in mobile ad hoc networks (MANET) due to the frequent topology changes. Flooding-based approaches like diffusion have a strong similarity with epidemic spreading of diseases. Applying epidemiological models to information diffusion allows the evaluation of such strategies depending on the MANET characteristics, e.g. the node density. In order to choose appropriate strategies at run time, the model should be easily evaluated.In this paper, an epidemic model is developed for a simple information diffusion algorithm based on simulation results. We analytically investigate the impact of node density on information diffusion. The analytical model allows the evaluation at runtime, even on devices with restricted resources, and thus enables mobile nodes to dynamically adapt their diffusion strategies depending on the local node density.

Abstract Due to its salient properties, mobile agent technology has received rapidly growing attention over the last few years. Many developments ofmobile agent systems are under way in both academic and industrial environments. MOLE is one of the first mobile agent systems that has been developed in the Java language; the first version came out in 1995. Since then MOLE has been constantly improved, and provides a stable environment for development and usage of mobile agents in the area of distributed applications. Furthermore, it has been used extensively in our research at the University of Stuttgart. In this paper we describe the system MOLE, some of its unique concepts and their implementation, and the results of our research in the areas of security, transactional support, and control mechanisms. Additionally, we discuss some applications built on MOLE. Copyright © 2002 John Wiley & Sons, Ltd.

We consider the problem of how to achieve a simultaneous arrival of information at a multitude of recipients for applications where the receivers are noncooperative. For that reason, we aim at designing an inter-receiver delay jitter fair service for Internet multicast delivery. In contrast to related work, we present an approach at the application layer, which does not assume special properties of the core network nodes and can be partially deployed. All necessary functions except a trusted time service are handled in the end systems. At the receivers, a secure hardware performs the security related functions. Additionally, the approach implicitly takes current network load into account, which gives the opportunity to keep the message delivery delay low. An analysis and simulation of the approach shows that the resulting inter-receiver delay jitter can be reduced to the order of tens of milliseconds.

We present a comparative delay analysis of tree-based reliable multicast protocols and show the influence of varying sending rates, group sizes, packet loss probabilities and branching factors of the control tree. Besides the average delivery delay we consider the delay to reliably deliver all packets and the round trip delay. The first two examine the delay between generation of a packet at the sender and correct reception at a randomly chosen receiver or all receivers, respectively. The latter is the delay between generation of a packet at the sender and reception of all acknowledgement packets at the sender. Our numerical results show that all tree-based protocols provide low delays and good scalability. From the four considered protocol classes, NAK-based protocols achieve the best scalability but ACK-based protocols achieve the lowest delays.

\n We present a delay analysis of three generic classes of multicast\n transport protocols. The first class considered is an unreliable\n scheme that works without retransmission of messages. This class\n also includes forward error correction approaches. The second class\n uses a positive acknowledgment and retransmission scheme to\n guarantee reliability. Finally, the third class is a hierarchical\n approach to avoid the well-known ACK implosion problem for large\n receiver groups. Our results show that only the unreliable and the\n hierarchical protocol class provide scalability for large receiver\n groups. For delay sensitive applications we can conclude from the\n results that in case of low packet loss probabilities, reliable\n multicast protocols provide low average delays, which are only\n slightly increased compared to unreliable protocols. However, if we\n take the maximum delay, the delay is significantly increased.\n

With the increasing pervasiveness of mobile computing devices, the need to access information in mobile environments has grown rapidly. Consequently, many mechanisms, e.g. broadcast dissemination, hoarding, or specialized caching mechanisms have been developed to overcome the disadvantages of wireless communication systems, which are usually used to access the information. To evaluate such mechanisms a simulation tool is needed that simulates both the users' mobility and their information access patterns. Since most existing user models either model only the mobility or the information access, we developed a new model that covers both aspects. Based on this model, we realized a flexible framework that allows to simulate all aspects of a mobile information access.

With the increasing popularity of mobile computing devices, the need to access information in mobile environments has grown rapidly. Since the information has to be accessed over wireless networks, mobile information systems often have to deal with problems like low bandwidth, high delay, and frequent disconnections. Information hoarding is a method that tries to overcome these problems by transferring information, which the user will probably need, in advance. The hoarding mechanism that we describe in this paper exploits the location dependence of the information access, which is often found in mobile information systems. Our simulation results show that it is beneficial to do so and that we achieve higher hit ratios than with a caching mechanism.

Computer networks and distribute systems are characterized by highly dynamic, concurrent, and complex processes. Thus, training in this area requires great effort from both teachers and learners. Teachers are disatisfied with available methods for presentation, explanation, and exercises, and they are looking for better methods to support learners. We have developed and architecture called Highly interactive simulation of algorithms and Protocols (HiSAP), consisting of a framework to build simulations and generate applets from formally specified algorithms or protocols. By modifying this specification and observing the resulting behavior, teaching and learning in a constructive manner is enabled. The framework is open to plug-in tools to show various aspects of HiSAP's behavior. We present the results of some experiments with HiSAP at three different lectures for graduate students of distributed systems and computer networks.

Tree-based reliable multicast protocols are known to provide better scalability than the protocols based on pure sender- and receiver-initiated schemes. However, previous analytical work that has provided these results is based on a system model which assumes reliable control message delivery and synchronized local clocks. These assumptions are questionable simplifications, since they favor protocols using multicasted negative acknowledgments with a NAK avoidance scheme. In this paper, we extend the previous analysis by taking into account control data loss and asynchronous local clocks. We further analyze a new protocol class with particular importance, the tree-based approach with aggregated acknowledgments. In contrast to other approaches, this class provides reliability not only in case of message loss but also in case of node failures. Our results show that the additional overhead to cope with node failures is very low and therefore acceptable for reliable multicast implementations.

Mobile agent technology has been proposed for various fault-sensitive application areas, including electronic commerce, systems management and active messaging. Recently proposed protocols providing the exactly-once execution of mobile agents allow the usage of mobile agents in these application areas. Based on these protocols, a mechanism for the application-initiated partial rollback of the agent execution is presented. The rollback mechanism uses compensation operations to roll back the effects of the agent execution on the resources and uses a mixture of physical logging and compensation operations to roll back the state of the agent. The introduction of different types of compensation operations allows performance improvements during the agent rollback.

There is an increasing number of Internet applications that attempt to optimize their network communication by considering the network distance across which data is transferred. Such applications range from replication management to mobile agent applications. One major problem of these applications is to efficiently acquire distance information for large computer networks. This paper presents an approach to creating a global view on the Internet, a so-called network distance map, which realizes a hierarchical decomposition of the network into regions and which allows us to estimate the network distance between any two hosts. This view is not only a single snapshot but is dynamically adapted to the continuously changing network conditions. The main idea is to use a certain set of hosts for performing distance measurements and to use the so-gained information for estimating the distance between arbitrary hosts. A hierarchical clustering provides the notion of regions and allows us to coordinate the measurements in such a way that the resulting network load is minimized. An experimental evaluation on the basis of 119 globally distributed measurement servers shows that already a small number of measurement servers allows us to construct fairly accurate distance maps at low cost.

When used in an outdoor environment mobile information systems often suffer from the disadvantages of wireless WANs. Hoarding is a method to overcome these disadvantages by transferring information which is probably needed by the user in advance. Existing hoarding mechanisms are either developed for a certain type of application or do not consider the user's location when selecting the information items to hoard. However, exploiting location information can be of great benefit with respect to the achievable hit-ratios. The hoarding mechanism suggested in this paper is both location-aware and universally applicable. Therefore, it can be used as a generic mechanism in a platform which supports different kinds of mobile information systems. In addition, it can be adapted to different degrees of knowledge about the user's movement.

Employing distributed multimedia applications (DMA) requires management support for multiple configuration steps including the definition of a desired DMA topology, the specification of a desired quality of service (QoS) and its enforcement through resource reservation. In this paper, we examine the additional aspect of finding an appropriate placement for a DMA within a distributed computer system (DCS). An overall approach is described for interrelating placement functions with existing procedures for topology and QoS specification and resource reservation. Then the problem of assigning a DMA within a DCS is formulated with the goal of finding a DMA placement with minimized computation and communication cost. For solving the assignment problem an efficient heuristic algorithm-SIGMA-is presented. Unlike other approaches, SIGMA takes into account requirements, which are specific for multimedia applications. Based on experiments conducted for randomly generated DMA and DCS graphs, the efficiency and accuracy of SIGMA is shown to be encouraging because, at low execution times, it finds assignments with cost very close to the optimal one.

A great variety of todays networked applications require a reliable multicast service. A number of the proposed reliable multicast protocols use a positive acknowledgment scheme, which returns ACKs to the sender to confirm correct delivery. To avoid the well-known implosion problem in the case of large receiver groups, often a tree-based approach is used, i.e., receivers are organized in a tree and ACK messages are passed along the edges of this so-called ACK tree. For building up this tree variations of the expanding ring search (ERS) scheme have been proposed. However, our simulations show that ERS scales poorly. In this paper, we propose an alternative scheme for building up ACK trees. This scheme is based on a so-called token repository service, where a token represents the right to connect to a certain node in the corresponding ACK tree. Nodes that want to join a group just request a token for this group from the (distributed) token repository service. Our simulations show that our scheme causes a much lower message overhead than ERS. Moreover, the quality of the resulting ACK trees in terms of delay and reliability is in many cases higher if generated with our scheme.

Due to the lack of a generic platform for location-and spatial-aware systems, many basic services have to be reimplemented in each application that uses spatial-awareness.A cooperation among different applications is also difficult to achieve without a common platform.In this paper we present a platform that solves these problems.It provides an infrastructure that is based on digital models of regions of the physical world, which are augmented by virtual objects.We show how virtual objects make the integration of existing information systems and services in spatial-aware systems easier.Furthermore, our platform supports interactions between the computer models and the real world and integrates single models in a global "Augmented World".

Mobile agent technology has been proposed for various fault-sensitive application areas, including electronic commerce, systems management and active messaging. Due to the autonomy of mobile agents, there is no natural instance that monitors the progress of an agent's execution. As a result, agents may be lost or blocked due to node crashes or network partitioning even if there are other nodes available that could continue processing. In this paper, we describe a protocol that provides exactly-once semantics of agent execution and additionally reduces the blocking probability of agents by introducing observer nodes for monitoring the progress of agents. This protocol is based on conventional transactional technology such as defined by X/Open DTP or CORBA OTS. It is being implemented in Mole, a mobile agent system developed at Stuttgart University.

The use of mobile agent technology has been proposed for various fault-sensitive application areas, including electronic commerce and system management. A prerequisite for the use of mobile agents in these environments is that agents have to be executed reliably, independent of communication and node failures. In this article, we present two approaches improving the level of fault-tolerance in agent execution. The introduction of an itinerary concept allows to specify an agent's travel plan flexibly and provides the agent system with the possibility to postpone the visit of currently unavailable nodes or to choose alternative nodes in case of node failures. The second approach is a recently proposed fault-tolerant protocol to ensure the exactly-once execution of an agent. With this protocol, agents are preformed in stages. Each stage consists of a number of nodes. One of these nodes executes the agent while the others monitor the execution. After a summary of this protocol, we focus on the construction of stages. In particular, we investigate how the number of nodes per stage influences the probability of an agent to be blocked due to failures and which nodes should be selected when forming a stage to minimize the protocol overhead.

The telecommunications environment is changing its face towards an open market of information services where the vision is "information any time, at any place, in any form". Within this electronic market the aspects of service customization and instant service provision are of fundamental importance. In this context a new paradigm is gaining momentum referred to as "intelligent agents". This paper provides an overview of the emerging field of intelligent agents (IAs) by identifying their basic properties. Focusing on mobile agents, which could be considered as a specific class of intelligent agents, we identify the chances of agent technology in the context of telecommunications. We look at their potential impacts on open service architectures, intelligent communications and network management.

Synchronization plays an important role in multimedia systems at various levels of abstraction. We propose a set of powerful abstractions for controlling and synchronizing continuous media streams in distributed environments. The proposed abstractions are based on a very general computation model, that allows media streams to be processed (i.e. produced, consumed or transformed) by arbitrarily structured networks of linked components. Further, compound components can be composed of existing ones to provide higher levels of abstractions. The clock abstraction is provided to control individual media streams, i.e., streams can be started, paused or scaled by issuing the appropriate clock operations. Clock hierarchies are used hierarchically group related streams, where each clock in the hierarchy identities and controls a certain group, or subgroup of streams. Control and synchronization requirements can be expressed in a uniform manner by associating group members with control or synchronisation attributes. An important property of the concept of clock hierarchy is that it can be combined in a natural way with component nesting.

Most of the proposed commit protocols assume that all participants of a transaction are sane, i.e., they only fail with omission failures and eventually recover. Unfortunately, this assumption is not realistic for open distributed systems (ODSs), which can be divided into a trusted and a nontrusted domain. While nodes in the trusted domain are assumed to be sane, nontrusted nodes may fail permanently and with commission failures. The open commit protocols presented are based on a model for consistency checking. The protocol also tolerates any number of commission failures in the nontrusted domain of an ODS. It guarantees that the trusted participants of a transaction terminate in a way that preserves consistency in the trusted domain, which generally does not mean that all trusted participants have to terminate consistently. The protocol groups those trusted participants that have to terminate consistently to maintain data consistency, and ensures that in each group the participants terminate in the same way. The advantages of the protocol are a simplified commit processing and a reduced message complexity. The message complexity of this protocol exceeds that of traditional two-phase commit protocols by no more than two messages for most practical cases.>

To ensure atomicity of transactions in distributed systems so-called 2-phase commit (2PC) protocols have been proposed. The basic assumption of these protocols is that the processing nodes involved in transactions are “sane,” i.e., they only fail with omission failures, and nodes eventually recover from failures. Unfortunately, this assumption is not realistic for so-called Open Distributed Systems (ODSs), in which nodes may have totally different reliability characteristics. In ODSs, nodes can be classified into trusted nodes (e.g., a banking server) and nontrusted nodes (e.g., a home PC requesting a remote banking service). While trusted nodes are assumed to be sane, nontrusted nodes may fail permanently and even cause commission failures to occur. In this paper, we propose a family of 2PC protocols that tolerate any number of omission failures at trusted nodes and any number of commission and omission failures at nontrusted nodes. The proposed protocols ensure that (at least) the trusted nodes participating in a transaction eventually terminate the transaction in a consistent manner. Unlike Byzantine commit protocols, our protocols do not incorporate mechanisms for achieving Byzantine agreement, which has advantages in terms of complexity: Our protocols have the same or only a slightly higher message complexity than traditional 2PC protocols.

The authors propose three different two-phase commit (2PC) protocols that ensure that, even in the presence of permanent node failures, all sane nodes participating in a particular transaction eventually terminate the transaction in a consistent way. A node is defined to be sane if it eventually recovers from failures. These protocols, called open 2PC protocols, are based on a tree-of-processes model and provide means for transferring the coordinator function within process trees. Besides describing the open 2PC protocols in detail, the authors compare these protocols with regard to their message and time complexity. They also include a discussion of related work.>

The concept of nested transactions offers more decomposable execution units and finer grained control over recovery and concurrency as compared to 'flat' transactions. To exploit these advantages, especially transaction recovery has to be refined and adjusted to the requirements of the control structure.In this paper, we investigate transaction recovery for nested transactions. Therefore, a model for nested transaction is introduced allowing for synchronous and asynchronous transaction invocation as well as single call and conversational interfaces. For the resulting four parameter combinations, the properties and dependencies of transaction recovery are explored if a transaction is 'unit of recovery' and if savepoints within transactions are used to gain finer recovery units.