Integrating churn into the formal analysis of routing algorithms

Mathematical modeling and analysis of distributed systems, mostly applied with the goal of the correctness or asymptotic behavior of a system, rarely provides concrete results and often disregards or simplifies network dynamics. However, concrete performance bounds on a system under churn are highly useful both as a validation of empirical results and a scalable alternative to simulations. In this paper, we first present an abstract methodology for deriving the success probability of an action, such as routing, in a dynamic system, using the session length distribution as the decisive parameter. We evaluate the developed methodology by giving concrete bounds on the success probability of recursive routing. The results do not only show the adaptability of our model, but also reveal that a considerable fraction of routing attempts fails due to a leaving node on the return path rather than due to not reaching the target.