Courteous routing

In a network comprising nodes, links between said nodes and a network controller, a first node comprising:

• means for determining a capacity requirement to a second node in said network;
• means for communicating said capacity requirement to said network controller;
• means for receiving, from said network controller, a load-adaptation vector, said load-adaptation vector having a plurality of elements and corresponding to a route set comprising different routes between said first node and said second node, each element of said plurality of elements in said load-adaptation vector corresponding to a unique route in said route set and having a value for restricting allocation of traffic to said unique route;
• means for receiving a request to connect said first node to said second node, said request having an associated load size;
• and
• means for assigning each of said requests to one of said routes according to said load-adaptation vector.

In a network including nodes and links connecting said nodes, with each pair of said nodes designated a route set among a plurality of route sets, each route set of said plurality of route sets including a plurality of routes, each route of said plurality of routes traversing at least one link, a method of allocating capacity to each route of said plurality of routes, the method comprising:

• receiving a capacity requirement for said each pair of said nodes;
• ranking, according to a predetermined criterion, said routes in said plurality of routes, included in said each route set, to produce a set of ranked routes;
• allocating capacity for said each route in said each route set according to a selfish-allocation process by allocating capacity to routes of high rank in said set of ranked routes;
• ascertaining excess capacity-allocation of at least one link among said links, said excess capacity-allocation resulting from said selfish-allocation process;
• and
• reallocating capacity, in at least one route set of said route sets, to reduce said excess capacity allocation.

A method of reducing excess load of a common link traversed by a first route and a second route, said first route allocated a first capacity, said second route allocated a second capacity, said first route belonging to a first plurality of routes and said second route belonging to a second plurality of routes, where each route in said first plurality of routes and in said second plurality of routes traverses at least one link selected from among a plurality of links, the method comprising:

• determining a first difference between a cost associated with a first candidate route in said first plurality of routes and a cost associated with said first route;
• determining a second difference between a cost associated with a second candidate route in said second plurality of routes and a cost associated with said second route;
• if said second difference is greater than said first difference, diverting a portion of said first capacity to said first candidate route;
• and
• if said first difference is greater than said second difference, diverting a portion of said second capacity to said second candidate route.

A method of capacity allocation in a network comprising a plurality of nodes interconnected by a plurality of links, the method comprising:

• determining a plurality of route sets, each of said route sets corresponding to a pair of said nodes;
• determining a capacity requirement for each pair of nodes;
• allocating said capacity requirement to routes of a corresponding route set of said plurality of route sets to produce a route-set allocation for said each of said route sets;
• determining a capacity allocation associated with each link of said plurality of links based on said allocating;
• identifying a particular link, among said plurality of links, with an excess load, where said excess load is determined as a difference between the capacity allocation associated with said particular link and a known capacity of said particular link;
• and
• adjusting said route-set allocation for a selected route set, among said plurality of route sets, to reduce said excess load.

A method of capacity allocation, in a network including a plurality of N>2 switching nodes interconnected by links and a network controller communicatively coupled to said switching nodes, the method comprising:

• defining 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, at said network controller, current traffic data from each switching node of said plurality of N switching nodes;
• determining a traffic-deviation metric based on comparing said current traffic data with previous traffic data;
• determining 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 for each route in said each route set.