Probabilistic Breadth-First Search – A Method for Evaluation of Network-Wide Broadcast Protocols

Tuesday, January 21, 2014
Probabilistic Breadth-First Search – A Method for Evaluation of Network-Wide Broadcast Protocols Authors:
Björn Lichtblau
Andreas Dittrich

6th IEEE/ACM/IFIP International Conference on New Technologies, Mobility and Security, NTMS 2014, Dubai, UAE, March 30 – April 2, 2014

Download: accepted version, final published version

In wireless mesh networks (WMNs), network-wide broadcasts (NWBs) are a fundamental operation, required by routing and other mechanisms that distribute information to all nodes in the network. However, due to the characteristics of wireless communication, NWBs are generally problematic. Optimizing them is thus a prime target when improving the overall performance and dependability of WMNs. Most of the existing optimizations neglect the real nature of WMNs and are based on simple graph models, which provide optimistic assumptions of NWB dissemination. On the other hand, models that fully consider the complex propagation characteristics of NWBs quickly become unsolvable due to their complexity. In this paper, we present the Monte Carlo method probabilistic breadth-first search (PBFS) to approximate the reachability of NWB protocols. PBFS simulates individual NWBs on graphs with probabilistic edge weights, which reflect link qualities of individual wireless links in the WMN, and estimates reachability over a configurable number of simulated runs. This approach is not only more efficient than existing ones, but further provides additional information such as the distribution of path lengths. Furthermore, it is easily extensible to NWB schemes other than flooding. The applicability of PBFS is validated both theoretically and empirically, in the latter by comparing reachability as calculated by PBFS and measured in a real-world WMN. Validation shows that PBFS quickly converges to the theoretically correct value and approximates the behaviour of real-life testbeds very well. The feasibility of PBFS to support research on NWB optimizations or higher level protocols that employ NWBs is demonstrated in two use cases.

Modeling Responsiveness of Decentralized Service Discovery in Wireless Mesh Networks

Monday, December 9, 2013
Modeling Responsiveness of Decentralized Service Discovery in Wireless Mesh Networks Authors:
Andreas Dittrich
Björn Lichtblau
Rafael Rezende
Miroslaw Malek

17th International GI/ITG Conference on “Measurement, Modelling and Evaluation of Computing Systems” and “Dependability and Fault-Tolerance”, MMB & DFT 2014, Bamberg, Germany, March 17-19, 2014

Download: accepted version, the final publication is available at link.springer.com

In service networks, discovery plays a crucial role as a layer where providers can be published and enumerated. This work focuses on the responsiveness of the discovery layer, the probability to operate successfully within a deadline, even in the presence of faults. It proposes a hierarchy of stochastic models for decentralized discovery and uses it to describe the discovery of a single service using three popular protocols. A methodology to use the model hierarchy in wireless mesh networks is introduced. Given a pair requester and provider, a discovery protocol and a deadline, it generates specific model instances and calculates responsiveness. Furthermore, this paper introduces a new metric, the expected responsiveness distance der, to estimate the maximum distance from a provider where requesters can still discover it with a required responsiveness. Using monitoring data from the DES testbed at Freie Universität Berlin, it is shown how responsiveness and der of the protocols change depending on the position of nodes and the link qualities in the network.

User-Perceived Instantaneous Service Availability Evaluation

Friday, August 9, 2013
User-Perceived Instantaneous Service Availability Evaluation Authors:
Rafael Rezende
Andreas Dittrich
Miroslaw Malek

19th IEEE Pacific Rim International Symposium on Dependable Computing (PRDC), Vancouver, BC, Canada, December 2-4, 2013

Download: accepted version, final published version

Today’s businesses rely ever more on dependable service provision deployed on information and communications technology (ICT) infrastructures. Service dependability is highly influenced by the individual infrastructure component properties. Combining these properties for consistent dependability analysis is challenging as every service requester might use a different set of components during service usage, constituting the user-perceived view on a service. This paper presents a methodology to evaluate user-perceived instantaneous service availability. It uses three input models: (1) The ICT infrastructure, with failure rates, repair rates and deployment times of all components, (2) an abstract description of complex hierarchical services, (3) a mapping that contains concrete ICT components for the service pair requester and provider, as well as their existing replicas, and a duration of usage. The methodology then automatically generates an availability model from those parts of the ICT infrastructure needed during provision for the specified pair. To calculate instantaneous availability, the age of the ICT components, the order and time of their usage during service provision are taken into account. The methodology supports generation of different availability models, we demonstrate this by providing reliability block diagrams and fault-trees. We demonstrate the feasibility of the methodology by applying it to parts of the network infrastructure of University of Lugano, Switzerland.

Model-Driven Evaluation of User-Perceived Service Availability

Thursday, April 4, 2013
Model-Driven Evaluation of User-Perceived Service Availability Authors:
Andreas Dittrich
Rafael Rezende

14th European Workshop on Dependable Computing (EWDC), Coimbra, Portugal, May 15-16, 2013

Download: accepted version, the final publication is available at link.springer.com

Service-oriented architecture (SOA) has emerged as an approach to master growing system complexity by proposing services as basic building elements of system design. However, it remains difficult to evaluate dependability of such distributed and heterogeneous functionality as it depends highly on the properties of the enabling information and communications technology (ICT) infrastructure. Moreover, every specific pair service client and provider can utilize different ICT components, constituting for the user-perceived view of a service. We provide a model-driven methodology to automatically create reliability block diagrams of such views. Given a service description, a network topology model and a pair service client and provider, it identifies relevant ICT components and generates a user-perceived service availability model (UPSAM). We then use this UPSAM to calculate the steady-state availability of different views on an exemplary mail service deployed in the network infrastructure of University of Lugano, Switzerland.

A Model for Evaluation of User-Perceived Service Properties

Sunday, March 10, 2013
A Model for the Evaluation of User-Perceived Service Properties Authors:
Andreas Dittrich
Igor Kaitovic
Cristina Murillo
Rafael Rezende

27th IEEE International Symposium on Parallel Distributed Processing, Workshops and PhD Forum, IPDPSW 2013, Boston, MA, USA, May 20-24, 2013

Download: accepted version, final published version

An ever-increasing number of both functional and non-functional requirements has resulted in growing system complexity which demands new solutions in system modeling and evaluation. As a remedy, service-oriented architecture (SOA) offers services as basic building elements of system design. Service dependability is highly dependent on the properties of the underlying information and communications technology (ICT) infrastructure. This is especially true for the user-perceived dependability of a specific pair service client and provider as every pair may utilize different ICT components. We provide a model for the description of ICT components and their non-functional properties based on the Unified Modeling Language (UML). Given a service description, a network topology model and a pair service client and provider, we propose a methodology to automatically identify relevant ICT components and generate a user-perceived service infrastructure model (UPSIM). We demonstrate the feasibility of the methodology by applying it to parts of the service network infrastructure at University of Lugano (USI), Switzerland. We then show how this methodology can be used to facilitate user-perceived service dependability analysis.