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

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

Title : Local Topology Pruning for Algebraic QoS Path Computations for Link-State Routing
Authors :
Somasundaram, Kiran K
Baras, John, S.
Conference : submitted to IEEE/ACM Transactions on Networking (TON)
Date: December 01 - December 01, 2012

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.