Patent ID: 8422379

Claim:
A method for balancing load in a network after failure of a link, the network comprising a plurality of interconnected vertices and edges eεE and a set of traffic demands dεD, each demand d defining a flow requirement h d from an ingress router u d to an egress router v d , the network further comprising a set of failure states s, the method comprising: at an ingress router u d , routing traffic by automatically balancing traffic load over a predefined set of paths P d from the ingress router u d to the egress router v d according to a set of splitting ratios α p o , each splitting ratio defining a fraction of the demands d to be transmitted over a path p of the set of paths P d in a case of a detectable failure state o corresponding to a subset of a set of modeled failure states s, the set of modeled failure states being states that cause at least one path p of the predefined set of paths P d to fail, the set of modeled failure states including a no-failure state in which the network has no failures, each modeled failure state having at least a predetermined probability of occurrence; and in an off-line management system, pre-computing the paths P d and the splitting ratios α p o , wherein pre-computing the splitting ratios α p o further comprises solving a linear program wherein the following objective function is minimized: obj( l e 1 s 1 /c e 1 , . . . )=Σ sεS w S Σ eεE Φ( l e s /c e ), wherein l e 1 s 1 is a total flow on edge e 1 in failure state s 1 , c e 1 is a capacity of an edge e 1 , w s is a weight given to a failure state s based on a frequency of occurrence, and Φ is a convex function of link load.