Patent ID: 7395351
Filing Date: 2008-07-01
Classification: H04L

Abstract:
1. A method for determining link weights that when utilized will optimize the performance of a network in the event of a link failure without the need to alter the link weights, said network including a plurality of nodes connected by a plurality of links, said network operable to transfer information from a first node to a second node over one or more of said links wherein the one or more links utilized to transfer said information constitute a route, said route determined by a weight that is assigned to each link, said set of link weights being a solution, said method comprising the following steps: (a) receiving an initial solution; (b) making said initial solution the current optimal solution; (c) computing one or more admissible routes between the plurality of nodes; (d) evaluating the initial solution utilizing both a full network and every single-link failure state; (e) determining a set of heavily-loaded links and a set of lightly-loaded links; (f) selecting randomly one link from said set of heavily-loaded links and one link from said set of lightly-loaded links; (g) generating a set of permissible solutions from the randomly selected links, said set of permissible solutions excluding previous best permissible solutions; (h) evaluating each permissible solution utilizing both the full network and every single-link failure state; (i) determining the best permissible solution; (j) comparing the best permissible solution to the current optimal solution; (k) if the best permissible solution is better than the current optimal solution then making the best permissible solution the next current optimal solution; (l) if a first maximum number of iterations has been evaluated, then making at least one of the current optimal solution and the next current optimal solution the final solution; (m) if a second maximum number of iterations has been evaluated without making a change to at least one of the current optimal solution and the next current optimal solution, then randomly obtaining a new number of links to evaluate; and (n) repeating steps (f) through (n) utilizing the new number of links to evaluate until the first maximum number of iterations has been evaluated.