Depletable Channels: Dynamics and Behaviour

A simple model of multi-hop communication in ad-hoc networks is considered. Similar models are often adopted for studying energy eciency and load balancing of dierent routing protocols. We address an orthogonal question never considered by the networking community: whether, regardless of specic protocols, two networks may be considered as equivalent from the viewpoint of the communication service they provide. In particular, we consider equivalent two networks with identical maximum and minimum inhibiting ow, and prove that this notion of equivalence coincides with a standard trace-based notion of equivalence borrowed from the theory of concurrency. We finally study the computational complexity of the proposed equivalence and discuss possible alternatives.