Local Topology Pruning for Algebraic QoS Path Computations for Link-State Routing

Kiran K. Somasundaram and John S. Baras

submitted

 

Abstract

Topology control for link-state routing is a mechanism to reduce link-state broadcast. Local pruning is a distributed mechanism where nodes prune local link-state information with exclusively local neighbor(-hood) information. An example of a local pruning mechanism is the topology selection mechanism used in Optimized Link State Routing (OLSR), which selects a reduced topology from the two-hop neighbor connectivity information. In local pruning mechanisms, the links that are removed by pruning are not broadcast, and consequently, the link-state information that is broadcast constitutes a reduced subgraph of the original link-state graph. The non-triviality in these mechanisms arise from the requirement that the local pruning policy must ensure that certain QoS optimal paths are preserved
in the reduced sub-graph for subsequent QoS path computations. In a previous work, we introduced a local pruning policy that ensures that certain class of global path-QoS properties are preserved in the reduced sub-graph. We showed that this pruning policy uses a certain ”distribution of order” property that the class of QoS rules satisfy to guarantee global QoS properties from local pruning.

In this paper, we use an algebraic framework introduced for generalized QoS path computations to derive sufficient conditions on the class of QoS metrics and rules for our pruning policy. The works of Sobrinho and Griffin introduced an algebraic path problem defined over semirings to prove the correctness of hopby- hop routing and distance vector routing protocols. We invoke and extend this algebra to prove loop-freedom of our local pruning mechanism. We define an instance of an idempotent semiring over vector metrics that handles multi-metric QoS path weights. We show that the ”strict-inflatory” condition that ensures loop-freedom for hop-by-hop and distance vector routing, shown in prior work, is also a sufficient condition for loop-free pruning for our local pruning policy. Index Terms—Topology control, Link-state routing, Semiring algebra, Pareto efficiency, Bellman’s optimality principle