RD: Reducing message overhead in DUAL

The efficiency of routing algorithms has always been an open question accompanied with the evolving history of routing problems. Message storm could easily be found in today´s Internet routing infrastructure, especially in the context of distance-vector like algorithm, requiring each node affected by network anomalies to send requests to all its neighbors and wait for response. Through in-depth analysis, we found that not everyone in network needs to know every cost change in the whole graph. In this paper, we present a new DUAL-based routing algorithm called reduction on message overhead in DUAL (RD), using two rules for suppressing some updates in network. In this way, we could minimize resources utilized for transmission of cost-change updates, thus improve the efficiency of DUAL. We give theoretical analysis about the correctness of RD and present detailed design and comparative characteristics of the protocol.