Patent ID: 7656886

Claim:
A method for establishing service level agreements by an electronic computing device in a network with a plurality of routers with predetermined paths, comprising: Computing an admissible ingress traffic for a source router; Computing an admissible egress traffic for the source router; Computing an admissible ingress traffic for a destination router; Computing an admissible egress traffic for the destination router; and Adding a service level agreement to the network using the predetermined paths between the source router and the destination router if the computed admissible ingress and egress traffic for the source router and the destination router are not exceeded whereby the service level agreement is added without checking a capacity of internal links of the predetermined paths, wherein a maximum admissible ingress and a maximum egress traffic of the source and destination routers are computed based a congestion ratio comprising a minimum value r, wherein the minimum value r and the predetermined paths are solved by a linear programming formulation comprising a master-slave formulation where: Master linear programming is Master ⁢ ⁢ LP ⁢ ⁢ is s . t . ∑ e ∈ Γ + ⁡ ( v ) min ⁢ ⁢ r ⁢ x ij e - ⁢ ∑ e ∈ Γ - ⁡ ( v ) ⁢ x ij e = 0 i , j ∈ Q , v ≠ i , j ∑ e ∈ Γ + ⁡ ( v ) ⁢ x ij e - ∑ e ∈ Γ - ⁡ ( v ) ⁢ x ij e = 1 i , j ∈ Q , v = i ∑ e ∈ Γ + ⁡ ( v ) ⁢ x ij e - ∑ e ∈ Γ - ⁡ ( v ) ⁢ x ij e = - 1 i , j ∈ Q , v = j ∑ i , j ∈ Q ⁢ x ij e ⁢ d ij ≤ c e · r e ∈ E , T ∈ D 0 ≤ x ij e ≤ 1 i , j ∈ Q , e ∈ E and ⁢ ⁢ Slave ⁢ ⁢ LP ⁢ ⁢ ⁢ is max ⁢ ∑ i , j ∈ Q ⁢ x ij e ⁢ d ij s . t . ∑ j ∈ Q ⁢ d ij ≤ α ~ i i ∈ Q ∑ i ∈ Q ⁢ d ij ≤ β ~ j j ∈ Q and Slave linear programming is max ⁢ ⁢ ∑ i , j ∈ Q ⁢ ⁢ x ij e ⁢ d ij s . t . ∑ j ∈ Q ⁢ ⁢ d ij ≤ α ~ i ⁢ i ∈ Q ∑ i ∈ Q ⁢ ⁢ d ij ≤ β ~ j j ∈ Q ⁢ and where v, i, and j are indices; Q denotes a set of edge routers; E denotes the internal links, T denotes traffic matrixes; x ij e denotes a portion of traffic from node i to j through a link e and 0≦x ij e ≦1; d ij represents the traffic rate from node i to node j; and wherein the maximum admissible traffic of the ingress and egress direction are θ{tilde over (α)} i and θ{tilde over (β)} i with {tilde over (α)} i and {tilde over (β)} i being constants.