Patent ID: 7898957

Claim:
A method of routing data through a network having a plurality of nodes interconnected by a plurality of links in a hop-by-hop network using a shortest-path routing protocol, the network connected to one or more other networks by edge nodes, comprising: a device for: computing an admissible ingress traffic for an ingress node; computing an admissible egress traffic for an egress node; computing and optimizing a set of link weights; determining equal-distance routes between the ingress node and the egress node in the network according to the optimized set of link weights; computing a network congestion ratio according to a minimum value r, r being subjected to ∑ e ∈ Γ + ⁡ ( v ) ⁢ x i ⁢ ⁢ j e - ∑ e ⁢ ∈ ⁢ Γ - ⁢ ( v ) ⁢ x ⁢ i ⁢ ⁢ j ⁢ e = 0 i , j ∈ Q , v ≠ i , j ∑ e ∈ Γ + ⁡ ( v ) ⁢ x i ⁢ ⁢ j e - ∑ e ⁢ ∈ ⁢ Γ - ⁢ ( v ) ⁢ x ⁢ i ⁢ ⁢ j ⁢ e = 1 i , j ∈ Q , v = i ∑ e ∈ Γ + ⁡ ( v ) ⁢ x i ⁢ ⁢ j e - ∑ e ⁢ ∈ ⁢ Γ - ⁢ ( v ) ⁢ x ⁢ i ⁢ ⁢ j ⁢ e = - 1 i , j ∈ Q , v = j ∑ i ⁢ ∈ ⁢ Q ⁢ ⁢ α ∼ i · π e ⁡ ( i ) + ∑ i ⁢ ∈ ⁢ Q ⁢ β ∼ i · λ e ⁡ ( i ) ≤ c e · r e ∈ E x i ⁢ ⁢ j e ≤ π e ⁡ ( i ) + λ e ⁡ ( j ) i , j ∈ Q , e ∈ E 0 ≤ f i ⁢ ⁢ j ⁡ ( o ⁡ ( e ) ) - x i ⁢ ⁢ j e ≤ 1 - δ ⁡ ( e , j ) i , j ∈ Q , e ∈ E x i ⁢ ⁢ j e ≤ δ ⁡ ( e , j ) i , j ∈ Q , e ∈ E 0 ≤ W ⁡ ( t ⁡ ( e ) , j ) + w e - W ⁡ ( o ⁡ ( e ) , j ) ≤ ( 1 - δ ⁡ ( e , j ) ) ⁢ M j ∈ Q , e ∈ E 1 - δ ⁡ ( e , j ) ≤ W ⁡ ( t ⁡ ( e ) , j ) + w e - W ⁡ ( o ⁡ ( e ) , j ) j ∈ Q , e ∈ E 0 ≤ x i ⁢ ⁢ j e ≤ 1 i , j ∈ Q , e ∈ E π e ⁡ ( i ) , λ e ⁡ ( i ) ≥ 0 i ∈ Q , e ∈ E f i ⁢ ⁢ j ⁡ ( t ) ≥ 0 i , j ∈ Q , t ∈ V W ⁡ ( t , j ) ≥ 0 j ∈ Q , t ∈ V δ ⁡ ( e , j ) ∈ { 0 , 1 } j ∈ Q , e ∈ E 1 ≤ w e ≤ K e ∈ E where the network being described by graph G(V,E), G representing nodes, E representing the set of links, Q ⊂ V being the set of edge routers through which traffic is admitted into the network, (θ{tilde over (α)} i ,θ{tilde over (β)} i ) representing the admissible ingress and egress traffic allowed to enter the network at the edge router i and where {tilde over (α)} i and {tilde over (β)} i comprising constants describing a degree of unevenness of traffic patterns, c e being the capacity for link eεE, w e being the weight of link e, {1, . . . , K} be the set of possible weights, x ij e representing a portion of traffic from node iεQ to jεQ routed through link e in even load-balancing framework; and adjusting the admissible ingress traffic and the admissible egress traffic by the network congestion ratio so that a flow can be admitted to the network if the adjusted admissible ingress traffic and the adjusted admissible egress traffic are not exceeded.