Compatibility between Optimal Tree-Based Broadcast Routing and Metric Design

Broadcast routing is a critical component in the routing design. While there are plenty of routing metrics and broadcast routing schemes in current literature, it remains an unsolved problem as to which metrics are compatible to a specific broadcast routing scheme. In particular, in the wireless broadcast routing context where transmission has an inherent broadcast property, there is a potential danger of incompatible combination of broadcast routing algorithms and metrics. This paper shows that different broadcast routing algorithms have different requirements on the properties of broadcast routing metrics. The metric properties for typical broadcast routing algorithms in undirected topologies are developed and proved. They are successfully used to verify the compatibility between broadcast routing metrics and these algorithms. This work provides important criteria in broadcast routing metric design.