Network Convergence Analysis Using Indirect Next Hop Approach

Spanning trees are used in networking to determine routes and corresponding next hops. Topology changes due to link failure or recovery cause spanning trees to be rebuilt on each router. After the new spanning tree is calculated, the router updates its tables, where number of affected entries depends on the new tree and may be significant for large-scale network. Possible solution to minimize routing table update time is the indirect next hop approach in which we divide network hosts into clusters and split routing table into two, where the first one matches destination for its cluster and redirects to the second table that contains mapping between clusters and next hops appointed to them. In this paper we evaluate the performance of two algorithms aimed at minimizing spanning tree recalculation time and measure how many entries in routing table need to be updated. We also propose clustering algorithms that divide network hosts into clusters so that topology changes are likely to affect the next hop for the whole cluster, thereby minimizing changes in the routing table.