Theoretical bounds on control-plane self-monitoring in routing protocols

The distributed routing protocols in use today promise to operate correctly only if all nodes implement the protocol faithfully. A small insignificant set of nodes have, in the past, brought an entire network to a standstill by reporting incorrect route information. The damage caused by these erroneous reports, in some instances, could have been contained since incorrect route reports sometimes reveal themselves as inconsistencies in the state-information of correctly functioning nodes. By checking for such inconsitencies and taking preventive action, such as disregarding selected route-reports, a correctly functioning node could have limited the damage caused by the malfunctioning nodes. Our theoretical study attempts to understand when a correctly functioning node can, by analysing its routing-state, detect that some node is misimplementing route selection. We present a methodology, called Strong-Detection that helps answer the question. We then apply Strong-Detection to three classes of routing protocols: distance-vector, path-vector, and link-state. For each class, we derive low-complexity self-monitoring algorithms that take as input the routing state and output whether any detectable anomalies exist. We then use these algorithms to compare and contrast the self-monitoring power ofthese different classes of protocols in relation to the complexity of the irrouting-state.