Transforming general networks into feed-forward by using turn-prohibition

The issue of breaking cycles in communication networks is an important topic for several reasons. For instance, it is required when transparent bridges are filling the forwarding tables. It is also needed to prevent the occurrence of deadlocks caused by certain routing protocols. Furthermore, most of the techniques used to work with communication networks can only be applied if the network topology is free of cycles.We present a distributed protocol which, applied to any network topology, provides a cycle-free topology. Our approach is based on the prohibition of only certain turns in the network. In contrast to previous proposals, our protocol is fully distributed, and thus does not require nodes to have knowledge of the global network topology. Furthermore, it allows multiple nodes to initiate the protocol in an independent manner. This feature can be used to cope with new nodes entering the system, as well as with nodes leaving it (voluntarily or due to a failure). We provide a detailed description of our proposal, formal proof of correctness, and an analysis of its performance.