A New Distributed Routing Protocol for Forwarding Networks Using Linear Number of Packets

In this paper, we propose a new efficient distributed routing protocol for any general purpose destination-based forwarding networks (like Internet) which forward packets solely based on the destination address. Our approach is to minimize the number of messages and the time needed to recompute the relevant forwarding tables due to topology change by introducing a concept of senator nodes (a small subset of the nodes in the network) who are responsible for maintaining the system wide tables; all other nodes communicate with their respective senators. We deploy a self-stabilizing algorithm to create a k-hop dominating set as senator nodes, where k is a constant, 1 ¿ k ¿ D/2, D is the diameter of the network. The cost of route updates is measured in round, a time-slot such that each packet identified by the packet ID can be forwarded at least once. We show that, in response to topology change caused by link or node failures, the recomputation of forwarding tables is guaranteed to converge within 5k + 2 rounds (a constant) with O(n) messages, where n is the number of nodes in the network.