Patent ID: 7567516

Claim:
A method of capacity allocation by a network controller, in a network including a plurality of N>2 switching nodes interconnected by links, the network controller being communicatively coupled to said switching nodes, the method comprising: defining, by the network controller, a plurality of N(N−1) route sets, where each route set of said plurality of N(N−1) route sets is defined for a switching node of said plurality of N switching nodes and another switching node of said plurality of N switching nodes, said each route set including at least one route; receiving, by the network controller, at said network controller, current traffic data from each switching node of said plurality of N switching nodes; determining, by the network controller, a traffic-deviation metric based on comparing said current traffic data with previous traffic data; determining, by the network controller, whether said traffic-deviation metric exceeds a predefined threshold; and responsive to determining that said traffic-deviation metric exceeds said predefined threshold, updating a current capacity allocation, by the network controller, for each route in said each route set, said step of updating comprising: ranking said at least one route, included in said each route set, to produce a set of ranked routes for said each route set; allocating capacity for each route in said set of ranked routes according to a selfish allocation process by allocating capacity to routes of high rank; ascertaining excess capacity-allocation of a particular link in said network resulting from said selfish-allocation process; and reallocating capacity, in a selected route set among said plurality of N(N−1) route sets, where said selected route set includes a route that includes said particular link, to reduce said excess capacity allocation of the particular link; wherein said traffic-deviation metric, as represented by Δ, is determined as: Δ = ∑ i ⁢ ∑ j ⁢  y i ⁢ ⁢ j - x i ⁢ ⁢ j  ∑ k ⁢ c k , where i, j, and k are indices bounded by 0≦i<N, 0≦j<N, 0≦k<N, y ij is an element in a new traffic matrix corresponding to said current traffic data for a source node i and a sink node j, x ij is an element in a previous traffic matrix corresponding to said previous traffic data for said source node i and said sink node j, and c k is a total access capacity of a node k.