Overlay network placement for diagnosability

Overlay networks have become an effective method to help overcome the limitations of the Internet in the last decade. Overlays must be monitored for various kinds of problems so that efficient performance can be sustained. An overlay's topology and placement on the substrate have a considerable effect on the level of difficulty in monitoring it. In this paper, we study the problem of placing overlay networks onto the substrate in a way that makes it easier to detect and localize faults, in other words, improves their diagnosability. Overlay network fault diagnosis is especially challenging because of their construction as virtual networks on top of a network substrate. We give a practical definition of diagnosability, and develop an overlay assignment algorithm that aims to optimize overlay placement for the ease and quickness of fault diagnosis. We evaluate the efficiency of this algorithm using an existing passive fault diagnosis scheme, and show that we are able to improve diagnosability without placing a significant strain on the network. We also analyze diagnosability in situations where traffic is sufficient for passive measurements on a percentage of paths rather than the whole network, and study how to augment passive diagnosis with selective active probing in order to raise diagnosability to a desired level.