An efficient multi-path generation method for hierarchical network model

In traditional multi-path routing schemes such as ECMP(Equal-Cost MultiPath), a method to generate multi-path computes only the lowest equal cost paths based on Dijkstra algorithm. This method is appropriate to link cost sensitive network such as flat network model. However, it is not proper to hierarchical network model that is less sensitive to link cost and interested in cost-length tradeoff. Also, it is not sufficient for load balancing and link failure recovery function because it does not guarantee to provide available alternative paths. This paper proposes an efficient multi-path generation algorithm for multi-path routing scheme in hierarchical network model. We enhance existing Dijkstra algorithm to guarantee multi-path with low time-complexity and low implementation cost. The proposed method is verified in terms of implementation on Quagga routing protocol suite and time-complexity comparison.