RFC 2992 (rfc2992) - Page 2 of 8
Analysis of an Equal-Cost Multi-Path Algorithm
Alternative Format: Original Text Document
RFC 2992 Analysis of ECMP Algorithm November 2000 2. Analysis There are a few concerns when choosing an algorithm for deciding which next-hop to use. One is performance, the computational requirements to run the algorithm. Another is disruption (i.e., the changing of which path a flow uses). Balancing is a third concern; however, since the algorithm's balancing characteristics are directly related to the chosen hash function this analysis does not treat this concern in depth. For this analysis we will assume regions of equal size. If the output of the hash function is uniformly distributed the distribution of flows amongst paths will also be uniform, and so the algorithm will properly implement ECMP. One can implement non-equal-cost multi-path routing by using regions of unequal size; however, non- equal-cost multi-path routing is outside the scope of this document. 2.1. Performance The performance of the hash-threshold algorithm can be broken down into three parts: selection of regions for the next-hops, obtaining the key and comparing the key to the regions to decide which next-hop to use. The algorithm doesn't specify the hash function used to obtain the key. Its performance in this area will be exactly the performance of the hash function. It is presumed that if this calculation proves to be a concern it can be done in hardware parallel to other operations that need to complete before deciding which next-hop to use. Since regions are restricted to be of equal size the calculation of region boundaries is trivial. Each boundary is exactly regionsize away from the previous boundary starting from 0 for the first region. As we will show, for equal sized regions, we don't need to store the boundary values. To choose the next-hop we must determine which region contains the key. Because the regions are of equal size determining which region contains the key is a simple division operation. regionsize = keyspace.size / #{nexthops} region = key / regionsize; Thus the time required to find the next-hop is dependent on the way the next-hops are organized in memory. The obvious use of an array indexed by region yields O(1). Hopps Informational
