Ad Hoc and Sensor Networks

Self-management of Routing on Human Proximity Networks

Abstract

Many modern network applications, including sensor networks and MANETs, have dynamic topologies that reflect processes occurring in the outside world. These dynamic processes are a challenge to traditional information dissemination techniques, as the appropriate strategy changes according to the changes in topology. We show how network dynamics can be exploited to design a self-organising data dissemination mechanism using only node-level (local) information, which detects and adapts to periodic patterns in the network topology. We demonstrate our approach against real-world human-proximity networks.

Graham Williamson, Davide Cellai, Simon Dobson, Paddy Nixon

Revisiting P2P Content Sharing in Wireless Ad Hoc Networks

Abstract

Classical content sharing applications like BitTorrent are not designed to run over wireless networks. When adapting them to these constrained networks, two main problems arise. On one hand, exchanging content pieces with far nodes results in an important routing overhead. On the other hand, it is necessary to send some content pieces to far nodes to increase the diversity of information in the network, which fosters reciprocity and parallel exchanges. In this paper, we study both of these problems and propose a joint solution for them. Unlike uni-metric approaches, our solution considers relevant performance metrics together as throughput, sharing and routing overhead. We define a new neighbor selection strategy that balances sharing and diversification efforts and decides on the optimal neighboring scope of a node. We also consider the diversification incentives problem and evaluates the impact of nodes’ mobility on the P2P strategy to be adopted. Through extensive simulations, we prove that our solution achieves both better download time and sharing ratio than uni-metric solutions.

Mohamed Karim Sbai, Chadi Barakat

Event Detection Using Unmanned Aerial Vehicles: Ordered versus Self-organized Search

Abstract

Event coverage problem in wireless sensor networks has drawn the interest of several researchers. While most of the previous work has been on static or ground mobile sensor networks, airborne sensor networks have also found its way into several civil and military applications such as environmental monitoring or battlefield assistance. In this work, we study the mobility pattern of an Unmanned Aerial Vehicle (UAV) network and explore the benefits of ordered and self-organized random mobility in terms of event detection performance, when the event is stationary and event duration is finite. Specifically, we compare the performance of a UAV network flying in parallel formation to a simple, distributed, locally-interactive coverage-based mobility model as well as legacy mobility models such as random walk and random direction. We study the event detection probability of the UAV network with both perfect and imperfect sensing capabilities. Our results show that when the timing constraints are highly stringent or when the UAV sensors have a high miss probability, flying in formation cannot achieve a high detection probability and a self-organized distributed mobility model is more effective.

Evşen Yanmaz

Services, Storage, and Internet Routing

A Survey of Models and Design Methods for Self-organizing Networked Systems

Abstract

Self-organization, whereby through purely local interactions, global order and structure emerge, is studied broadly across many fields of science, economics, and engineering. We review several existing methods and modeling techniques used to understand self-organization in a general manner. We then present implementation concepts and case studies for applying these principles for the design and deployment of robust self-organizing networked systems.

Wilfried Elmenreich, Raissa D’Souza, Christian Bettstetter, Hermann de Meer

Laying Pheromone Trails for Balanced and Dependable Component Mappings

Abstract

This paper presents an optimization framework for finding efficient deployment mappings of replicated service components (to nodes), while accounting for multiple services simultaneously and adhering to non-functional requirements. Currently, we consider load-balancing and dependability requirements. Our approach is based on a variant of Ant Colony Optimization and is completely decentralized, where ants communicate indirectly through pheromone tables in nodes. In this paper, we target scalability; however, existing encoding schemes for the pheromone tables did not scale. Hence, we propose and evaluate three different pheromone encodings. Using the most scalable encoding, we evaluate our approach in a significantly larger system than our previous work. We also evaluate the approach in terms of robustness to network partition failures.

Máté J. Csorba, Hein Meling, Poul E. Heegaard

Self-organized Data Redundancy Management for Peer-to-Peer Storage Systems

Abstract

In peer-to-peer storage systems, peers can freely join and leave the system at any time. Ensuring high data availability in such an environment is a challenging task. In this paper we analyze the costs of achieving data availability in fully decentralized peer-to-peer systems. We mainly address the problem of churn and what effect maintaining availability has on network bandwidth. We discuss two different redundancy techniques – replication and erasure coding – and consider their monitoring and repairing costs analytically. We calculate the bandwidth costs using basic costs equations and two different Markov reward models. One for centralized monitoring system and the other for distributed monitoring. We show a comparison of the numerical results accordingly. Depending on these results, we determine the best redundancy and maintenance strategy that corresponds to peer’s failure probability.

Yaser Houri, Manfred Jobmann, Thomas Fuhrmann

Self-organization of Internet Paths

Abstract

The Internet consists of a constantly evolving complex hierarchical architecture where routers are grouped into autonomous systems (ASes) that interconnect to provide global connectivity. Routing is generally performed in a decentralized fashion, where each router determines the route to the destination based on the information gathered from neighboring routers. Consequently, the impact of a route update broadcasted by one router may affect many other routers, causing an avalanche of update messages broadcasted throughout the network. In this paper we analyze an extensive dataset with measurements on Internet routes between a set of highly stable testboxes for a period of five years. The measurements provide insight into the coherence between routing events in the Internet and we argue that the routing dynamics exhibit self-organized criticality (SOC). The SOC property provides an explanation for the power-law behavior that we observe in the operational times of routes.

Tom Kleiberg, Piet Van Mieghem

Peer-to-Peer Systems

Non-Sticky Fingers: Policy-Driven Self-optimization for DHTs

Abstract

It is a common situation with distributed hash tables (DHT) that insertions and lookups frequently target only specific fractions of the entire value range. We present in this paper a self-optimization scheme for DHTs that optimizes the routing behavior in such situations. In our scheme, called Non-Sticky (NS) fingers, each node continuously measures the routing behavior and guides neighboring nodes to adjust their NS fingers (a subset of all the long distance links that the node establishes) accordingly in order to shortcut the most popular sections of routes. Our scheme enables self-optimization, which means that it adapts to the current system state and only operates when advantageous. It is also policy-driven, which means that the application can specify its policy on the tradeoff between performance and cost efficiency. We implemented the NS-fingers scheme for an existing order-preserving DHT and report the evaluation results. Our simulation results show that in a realistic application scenario, NS-fingers can halve the number of routing hops.

Matti Siekkinen, Vera Goebel

Passive/Active Load Balancing with Informed Node Placement in DHTs

Abstract

Distributed key/value stores are a basic building block for large-scale Internet services. Support for range queries introduces new challenges to load balancing since both the key and workload distribution can be non-uniform.

We build on previous work based on the power of choice to present algorithms suitable for active and passive load balancing that adapt to both the key and workload distribution. The algorithms are evaluated in a simulated environment, focusing on the impact of load balancing on scalability under normal conditions and in an overloaded system.

Mikael Högqvist, Nico Kruber

Optimal TCP-Friendly Rate Control for P2P Streaming: An Economic Approach

Abstract

TCP and TCP-friendly rate control protocols, designed for unicast, do not take neighbor connections into account in P2P networks. In this paper, we study the topic of distributed and optimal rate control for scalable video streams in P2P streaming applications. First, we propose a fully distributed and TCP-friendly network analytical model for rate control and formulate an optimization problem to maximize the aggregate utility for the P2P streams. In the model, we further extend the definition of TCP-friendliness for P2P network. Second, we propose a shadow price-based distributed algorithm for P2P Streaming that solves the optimization problem. Finally, we evaluate the performance of the proposed algorithm in terms of streaming quality and messaging overhead. Extensive simulations show that the proposed algorithms generate very small overhead and that they are optimal in terms of overall quality for scalable streams.

Jinyao Yan, Martin May, Bernhard Plattner

Theory and General Approaches

The Degree of Global-State Awareness in Self-Organizing Systems

Abstract

Since the entities composing self-organizing systems have direct access only to information provided by their vicinity, it is a non-trivial task for them to determine properties of the global system state. However, this ability appears to be mandatory for certain self-organizing systems in order to achieve an intended functionality.

Based on Shannon’s information entropy, we introduce a formal measure that allows to determine the entities’ degree of global-state awareness. Using this measure, self-organizing systems and suitable system settings can be identified that provide the necessary information to the entities for achieving the intended system functionality.

Hence, the proposed degree supports the evaluation of functional properties during the design and management of self-organizing systems. We show this by applying the measure exemplarily to a self-organizing sensor network designed for intrusion detection. This allows us to find preferable system parameter settings.

Christopher Auer, Patrick Wüchner, Hermann de Meer

Revisiting the Auto-Regressive Functions of the Cross-Entropy Ant System

Abstract

The Cross-Entropy Ant System (CEAS) is an Ant Colony Optimization (ACO) system for distributed and online path management in telecommunication networks. Previous works on CEAS have enhanced the system by introducing new features. This paper takes a step back and revisits the auto-regressive functions at the core of the system. These functions are approximations of complicated transcendental functions stemming from the Cross-Entropy (CE) method for stochastic optimization, computationally intensive and therefore not suited for online and distributed operation. Using linear instead of hyperbolic approximations, new expressions are derived and shown to improve the adaptivity and robustness of the system, in particular on the occurrence of radical changes in the cost of the paths sampled by ants.

Laurent Paquereau, Bjarne E. Helvik

Quantitative Modeling of Self-organizing Properties

Abstract

For analyzing properties of complex systems, a mathematical model for these systems is useful. In this paper we give quantitative definitions of adaptivity, target orientation, homogeneity and resilience with respect to faulty nodes or attacks by intruders. The modeling of the system is done by using a multigraph to describe the connections between objects and stochastic automatons for the behavior of the objects. The quantitative definitions of the properties can help for the analysis of existing systems and for the design of new systems. To show the practical usability of the concepts, the definitions are applied to a slot synchronization algorithm in wireless sensor networks.

Richard Holzer, Hermann de Meer

Overlay Networks

Resolving the Noxious Effect of Churn on Internet Coordinate Systems

Abstract

Internet Coordinate Systems (ICS) provide easy and practical latency predictions in the Internet. However, peer dynamics (i.e, churn), which is an inherent property of peer-to-peer (P2P) systems, affects the accuracy of such systems. This paper addresses the problem of churn in an ICS without landmarks, like Vivaldi. We propose a framework to assess the robustness of such an ICS in the presence of churn, and evaluate two models for handling churn. The key idea is to reactively recover lost neighbours, either by picking new nodes at random, or by selecting a new one among the node’s two-hop neighbours, while maintaining high reliability and low communication overhead. We then show by simulations that our models mitigate the impact of churn, and lead to a good accuracy compared to an instance of an ICS running without churn.

Bamba Gueye, Guy Leduc

Tuning Vivaldi: Achieving Increased Accuracy and Stability

Abstract

Network Coordinates are a basic building block for most peer-to-peer applications nowadays. They optimize the peer selection process by allowing the nodes to preferably attach to peers to whom they then experience a low round trip time. Albeit there has been substantial research effort in this topic over the last years, the optimization of the various network coordinate algorithms has not been pursued systematically yet. Analyzing the well-known Vivaldi algorithm and its proposed optimizations with several sets of extensive Internet traffic traces, we found that in face of current Internet data most of the parameters that have been recommended in the original papers are a magnitude too high. Based on this insight, we recommend modified parameters that improve the algorithms’ performance significantly.

Benedikt Elser, Andreas Förschler, Thomas Fuhrmann

Short Papers

Peer-to-Peer Systems and Internet Routing

A Stable Random-Contact Algorithm for Peer-to-Peer File Sharing

Abstract

We consider a BitTorrent type file sharing algorithm with randomized chunk copying process. The system functions in completely distributed way without any ‘Tracker’, just relying on randomness. In such case the stability becomes an issue. It may happen, say, that some chunk becomes rare. This problem can persist and cause accumulation of peers in the system, resulting in unstable system. The considered algorithms result in processes similar to urn-processes. The rare chunk phenomenon corresponds to Polya-urn type process, where common chunks are favored. However, some urn-processes like the Friedman-urn can provide good balance by favoring rare chunks in copying process. Recently, we showed that an algorithm based on Friedman-urn is efficient in two chunk case. We generalize this algorithm for the more realistic case of many chunks. It shows good performance in terms of balance of chunks in an open system with constant flow of incoming peers. Further, the system is able to cope with instances like ‘flash crowd’, with large burst of incoming peers. The open system can also quickly reach equilibrium after an initial imbalance, when the system starts from a state with one rare chunk. We constructed a simplified model, assuming a good balance of chunks, and get results surprisingly close to simulations for Friedman-urn based random process.

Hannu Reittu

A Decentralized Architecture for Distributed Neighborhood Based Search

Abstract

We present a decentralized self-X architecture for distributed neighborhood based search problems using an overlay network based on random graphs. This approach provides a scalable and robust architecture with low requirements for bandwidth and computational power as well as an adequate neighborhood topology, e.g. for several instances of parallel local search and distributed learning. Together with an adapted load balancing schema our architecture is self-organizing, self-healing and self-optimizing.

Pascal Katzenbach, Yann Lorion, Tjorben Bogon, Ingo J. Timm

Scheduling in P2P Streaming: From Algorithms to Protocols

Abstract

Chunk and peer scheduling is among the main driver of performance in P2P streaming systems. While previous work has analytically proved that optimal scheduling algorithms exist, such strategies are based on a large number of strong assumptions about the knowledge that a single peer has of the rest of the system. This short paper presents a protocol for turning these theoretical results into practical ones, by taking into account practical aspects like the diffusion time of signaling messages and a partial knowledge of the participating peers.

Luca Abeni, Alberto Montresor

Network Heterogeneity and Cascading Failures – An Evaluation for the Case of BGP Vulnerability

Abstract

Large-scale outages of computer networks, particularly the Internet, can have a significant impact on their users and society in general. There have been a number of theoretical studies of complex network structures that suggest that heterogeneous networks, in terms of node connectivity and load, are more vulnerable to cascading failures than those which are more homogeneous. In this paper, we describe early research into an investigation of whether this thesis holds true for vulnerabilities in the Internet’s inter-domain routing protocol – BGP – in light of different network structures. Specifically, we are investigating the effects of BGP routers creating blackholes – observed phenomena in the Internet in recent years. We describe our evaluation setup, which includes a bespoke topology generator that can fluidly create any topology configuration from the current scale-free AS-level to the investigated homogeneous graphs. We find that network homogeneity as suggested by theory does not protect the overall network from failures in practice, but instead may even be harmful to network operations.

Christian Doerr, Paul Smith, David Hutchison

Wireless Networks

A Self-organizing Approach to Activity Recognition with Wireless Sensors

Abstract

In this paper, we describe an approach to activity recognition, which is based on a self-organizing, ad hoc network of body-worn sensors. It makes best use of the available sensors, and autonomously adapts to dynamically varying sensor setups in terms of changing sensor availabilities, characteristics and on-body locations. For a widespread use of activity recognition systems, such an opportunistic approach is better suited than a fixed and application-specific deployment of sensor systems, as it unburdens the user from placing specific sensors at pre-defined locations on his body. The main contribution of this paper is the presentation of an interaction model for the self-organization of sensor nodes, which enables a cooperative recognition of activities according to the demands of a user’s mobile device. We implemented it with an embedded system platform, and conducted an evaluation showing the feasibility and performance of our approach.

Clemens Holzmann, Michael Haslgrübler

Congestion Control in Wireless Sensor Networks Based on the Bird Flocking Behavior

Abstract

Recently, performance controlled wireless sensor networks have attracted significant interest with the emergence of mission-critical applications (e.g. health monitoring). Performance control can be carried out by robust congestion control approaches that aim to keep the network operational under varying network conditions. In this study, swarm intelligence is successfully employed to combat congestion by mimicking the collective behavior of bird flocks, having the emerging global behavior of minimum congestion and routing of information flow to the sink, achieved collectively without explicitly programming them into individual nodes. This approach is simple to implement at the individual node, while its emergent collective behavior contributes to the common objectives. Performance evaluations reveal the energy efficiency of the proposed flock-based congestion control (Flock-CC) approach. Also, recent studies showed that Flock-CC is robust and self-adaptable, involving minimal information exchange and computational burden.

Pavlos Antoniou, Andreas Pitsillides, Andries Engelbrecht, Tim Blackwell, Loizos Michael

A Distributed Range Assignment Protocol

Abstract

We present a new distributed algorithm for creating and maintaining power-efficient topologies in a wireless network. The wireless nodes establish links to neighbouring nodes in a self-organizing fashion. The protocol is designed to first create a connected topology and then iteratively search for better links to reduce the overall power consumption. First results from simulated experiments with various network sizes show that the resulting topologies are close to optimal in respect to the total energy consumption.

Steffen Wolf, Tom Ansay, Peter Merz

A Distributed Power Saving Algorithm for Cellular Networks

Abstract

We consider power saving in a cellular network. Subject to constraints generated by network planning and dynamic Radio Resource Management algorithms, there is room for reducing Base Station (BS) transmit powers. We suggest that power is reduced in a way that does not move cell boundaries significantly. For this, there is a power difference constraint d _max that upper limits the difference in power reductions in neighboring BSs. The BSs exchange information about their current level of power. Each BS has a target maximum power reduction. We propose a distributed algorithm, where the BSs take turns to reduce their power, respecting their neighbors current power settings and the power difference constraint. We show that this algorithm converges to a global optimum.

Ingo Viering, Matti Peltomäki, Olav Tirkkonen, Mikko Alava, Richard Waldhauser

Local Optimum Based Power Allocation Approach for Spectrum Sharing in Unlicensed Bands

Abstract

We present a novel local optimum based power allocation approach for spectrum sharing in unlicensed frequency bands. The proposed technique is based on the idea of dividing the network in a number of smaller sub-networks or clusters. Sum capacity of each cluster is maximized subject to constraint on total power of each user in a cluster. On its turn each user in a cluster maximizes the sum capacity by calculating power allocations that correspond to a local optimum. Total power constraint of each user and effect of interference from other users in the network is taken into account for finding local optimum solution. Comparison of achieved network sum capacity is done with the well known iterative water filling method. Numerical results show that the proposed cluster based local optimum method achieves higher capacity than selfish iterative water filling and is therefore suitable for geographically distributed networks.

Furqan Ahmed, Olav Tirkkonen

Networking Topics

Economics-Driven Short-Term Traffic Management in MPLS-Based Self-adaptive Networks

Abstract

Today’s networking environment exhibits significant traffic variability and squeezing profit margins. An adaptive and economics-aware traffic management approach, needed to cope with such environment, is proposed that acts on short timescales (from minutes to hours) and employs an economics-based figure of merit to rellocate bandwidth in an MPLS context. Both underload and overload deviations from the optimal bandwidth allocation are sanctioned through the economical evaluation of the consequences of such non-optimality. A description of the traffic management system is provided together with some simulation results to show its operations.

Paola Iovanna, Maurizio Naldi, Roberto Sabella, Cristiano Zema

Self-organized Evacuation Based on LifeBelt

Abstract

In this paper, we have investigated the feasibility of a self-organized evacuation process when compared with a centralized control. The evacuation strategy is based on ’predicted exit time’ (a relation of ’estimated time to reach to an exit’, ’exit capacity’ and ’exit population’) for each of the exit in a multi-exit environment, selecting the minimum value exit. The self-organized strategy is based on information propagation in a peer-to-peer fashion, initiated by a special agent in each of the exit area. The propagation range (’zone of influence’) is dependent on intensity and direction of peers interaction. Based on the propagated dataset, each agent can make an autonomous decision, conceptually a converse of centralized strategy where each agent is directed by a server. The evacuation process in supported by a wearable device, i.e. LifeBelt. Through large scale simulations using cellular automata technique and a challenging airport terminal model, we have proved that an efficient evacuation based on principles of self-organization is a real possibility, even in an infrastructureless environment.

Kashif Zia, Alois Ferscha

On the Role of Self-organisation as a Model for Networked Systems

Abstract

In this paper, the role of the concept of self-organisation as a model in the analysis and design of advanced networked systems is investigated. In a first step, criteria for the definition of scientific models and their explanatory roles are introduced on the background of theories of models in the philosophy of science: intended scope, selection of the properties modelled, type of analogy, and levels of formalisation, abstraction and idealisation. In a second step, the applicability of these criteria to model-building in engineering is discussed, in order to assess some of the implications and limitations of modelling networked systems as self-organised systems, with particular attention to the role of the systems’ environments in these models.

Hajo Greif

Addressing Stability of Control-Loops in the Context of the GANA Architecture: Synchronization of Actions and Policies

Abstract

As research on self-managing networks is on the rise, a very important question requiring answers is: How to ensure that all autonomic entities/elements in a network or in a single node work together harmoniously with the aim of maintaining service availability and good levels of quality of service (QoS) provided to the end users? In this paper, we propose to enhance the Generic Autonomic Network Architecture (GANA) – a recently emerged architectural Reference-Model for Autonomic Networking, such that actions, policy enforcements and/or (re-) configurations, issued by different autonomic (decision making) entities, are synchronized in such a way that they lead to the best possible (long-term) reaction of the system to the challenging conditions the network is exposed to.

Nikolay Tcholtchev, Ranganai Chaparadza, Arun Prakash

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

Ad Hoc and Sensor Networks

Self-management of Routing on Human Proximity Networks

Revisiting P2P Content Sharing in Wireless Ad Hoc Networks

Event Detection Using Unmanned Aerial Vehicles: Ordered versus Self-organized Search

Services, Storage, and Internet Routing

A Survey of Models and Design Methods for Self-organizing Networked Systems

Laying Pheromone Trails for Balanced and Dependable Component Mappings

Self-organized Data Redundancy Management for Peer-to-Peer Storage Systems

Self-organization of Internet Paths

Peer-to-Peer Systems

Non-Sticky Fingers: Policy-Driven Self-optimization for DHTs

Passive/Active Load Balancing with Informed Node Placement in DHTs

Optimal TCP-Friendly Rate Control for P2P Streaming: An Economic Approach

Theory and General Approaches

The Degree of Global-State Awareness in Self-Organizing Systems

Revisiting the Auto-Regressive Functions of the Cross-Entropy Ant System

Quantitative Modeling of Self-organizing Properties

Overlay Networks

Resolving the Noxious Effect of Churn on Internet Coordinate Systems

Tuning Vivaldi: Achieving Increased Accuracy and Stability

Short Papers

Peer-to-Peer Systems and Internet Routing

A Stable Random-Contact Algorithm for Peer-to-Peer File Sharing

A Decentralized Architecture for Distributed Neighborhood Based Search

Scheduling in P2P Streaming: From Algorithms to Protocols

Network Heterogeneity and Cascading Failures – An Evaluation for the Case of BGP Vulnerability

Wireless Networks

A Self-organizing Approach to Activity Recognition with Wireless Sensors

Congestion Control in Wireless Sensor Networks Based on the Bird Flocking Behavior

A Distributed Range Assignment Protocol

A Distributed Power Saving Algorithm for Cellular Networks

Local Optimum Based Power Allocation Approach for Spectrum Sharing in Unlicensed Bands

Networking Topics

Economics-Driven Short-Term Traffic Management in MPLS-Based Self-adaptive Networks

Self-organized Evacuation Based on LifeBelt

On the Role of Self-organisation as a Model for Networked Systems

Addressing Stability of Control-Loops in the Context of the GANA Architecture: Synchronization of Actions and Policies

Backmatter