ToleranceZone - A Fault Tolerant Middleware Idioms based on Self-Stabilizing Techniques

点击翻译按钮获取中文摘要

Self-Stabilizing Algorithms (SSAs) have the inherent property to return into a stable state even when non-anticipated errors occur. This implicit robustness is certainly beneficial for error prone wireless networks. However, it comes at a price: convergence time is not predictable and possibly unbounded. Furthermore, neighboring nodes need to exchange state information periodically, which may lead to intolerable energy consumption.The ToleranceZone project investigates ways to implement self-stabilizing communication and middleware platforms for wireless ad hoc networks. Understanding the relationship between the rate of state exchange among neighbors and the convergence time is particularly important. Specifically we would like to know, whether self-stabilizing algorithms (SSAs) can cope with typical network topology changes in a reasonable time with a reasonable energy consumption.We started our research by implementing common communication patterns in a self-stabilizing way and evaluated our approach in experiments with real networks. We were able to show, that SSAs work in principle but we detected phenomenons that were both hard to explain and hard to reproduce. The bad reproducibility turned out to be our major challenge. Therefore we developed a methodology that allows us to feed topology data collected in real experiments into reproducible, deterministic simulations. This allows us to study the impact of topology changes on our SSAs as well as the impact of the exchange frequency to convergence time in detail.We could already show that SSAs are much more sensitive to topology changes than anticipated. Changes in the neighborhood are not implicitly repaired as expected, but may lead to significant instability on higher software layers resulting in either poor convergence time or no convergence at all. In fact, multiple SSAs on different layers tend to work against each other like contradicting control loops. These cross layer effects have a significant impact, but so far this phenomenon has not been studied. Therefore we will focus in the final phase of our project on understanding these interdependencies. Based on those insights we will derive cross layer feedback mechanisms that allow us to adapt the neighbor exchange rate to the perceived stability in the neighborhood. We will evaluate our approach with the aforementioned methodology as well as experiment with real networks. Finally we will compare the results against state of the art approaches to robustness in wireless networks.