BROWSE
Detail
Conference Paper
Path Selection Algorithm over Equal Cost Multiple Paths in Router
Cited - time in 
Share 
Share
- Authors
- Jae Young Kim, Byung Jun Ahn, Kwang Sun Ahn
- Issue Date
- 2007-01
- Citation
- International Conference on Information Networking (ICOIN) 2007, pp.1-10
- Language
- English
- Type
- Conference Paper
- Abstract
- A novel algorithm for next-hop selection over a set of Equal Cost Multiple Paths (ECMP) in a router is presented, which provides for load sharing among multiple routes. The main idea of proposed algorithm is that the remainders are distributed equally when the multiples of a number are divided by prime number. Based on this specific property, this algorithm assigns incoming flows to a next-hop selected. The hashed value of flow is divided by the maximum number of multiple paths. If a next-hop pointed the remainder is available, this next-hop selected to forward packet. But if not, prime number exceeding the number of available multiple paths divides the hashed value. If a next-hop pointed the remainder is not available, the prime number not exceeding the number of available multiple paths divides the hashed value. A next-hop is selected using this remainder. The disruption characteristic is remarkably improved using prime number division scheme The lookup performance of this algorithm is an optimal O(1) and disruptive behavior is between 0.06 and 0.59 in case N is the number of next-hops and N is equal to sixteen. The disruptive behaviors are the similar though N is not sixteen. And the disruption average of proposed algorithm is 0.24. In case N is equal to eight, disruptive behavior is between 0.12 and 0.53 and the disruption average is 0.29. The optimal disruption average is 0.16 where N is equal to sixteen. As compared with other algorithm decided which next-hop to use, the performance of proposed algorithm like modulo-N is an optimal O(1), the disruptive behavior of proposed algorithm is better than that of modulo-N and that of hash-threshold algorithm. But Highest Random Weight (HRW)'s disruptive behavior with 1/N is better than that of proposed algorithm. Load balancing per flow is nearly good.
- KSP Keywords
- Load Sharing, Load balancing, Lookup performance, Multiple routes, Next-Hop Selection, Novel algorithm, Prime Number, Random weight, Threshold algorithm, disruptive behavior, multiple paths