Improved balancing heuristics for optimizing shortest path routing

Open Shortest Path First (OSPF) is the most commonly used intra-domain routing protocol. OSPF routes traffic flows along shortest paths and the traffic will be split evenly when several shortest paths are found to the destination. An integer value is assigned to each link as a weight in OSPF networks. The weights highly affect the selection of links in the shortest paths. One of the default heuristics recommended by Cisco is to set the weights inversely proportional to link capacities. Overloaded links could appear if they have lower weights, while still other links are under-utilized. Many balancing heuristics were proposed to avoid congestion and utilize un-used network resources. This paper presents an improved balancing heuristics that solve two problems found in the evenly balancing heuristic proposed by Fortz and Thorup in their OSPF optimization model. Results show that our improved balancing heuristics work better in terms of routing cost and algorithm convergence.