Load balancing enables the use of linear programming techniques to reduce the complexity of computing backup tunnel placement for guaranteed bandwidth protection. The ability to load balance among multiple backup tunnels transforms the placement problem into one that may be characterized as a series of linear constraints usable as input to a linear programming procedure such as the simplex method. Each node may compute its own backup tunnels and signal the tunnels to its neighbors with zero bandwidth to allow implicit sharing of backup bandwidth.
In one embodiment, a node (e.g., a "rearranging node") receives a trigger to rearrange one or more tunnels having a respective bandwidth value. In response, the rearranging node signals each of the tunnels with zero bandwidth at a configured time shared by the node and one or more other rearranging nodes. The node then signals each of the tunnels with its respective bandwidth value at a corresponding calculated time beyond the configured time, the corresponding calculated time for each tunnel being inversely proportional to the respective bandwidth value of that corresponding tunnel. Also, in one embodiment, a node may determine that a reason exists to rearrange tunnels, and in response, may send a trigger to one or more rearranging nodes to request that those nodes rearrange their tunnels.
In a mesh communications network, in which working and protection paths may be established, channels used to carry protection traffic between nodes are shared across multiple protection paths. Channels need only be shared if sharing does not adversely impact network usage. If working and protection paths become susceptible to single points of failure, channels need not be shared.
A method of determining a placement of services of a distributed application onto nodes of a distributed resource infrastructure comprises first, second, and third steps. The first step forms communication constraints between node pairs. The communication constraints ensure that a sum of transport demands between a particular node pair does not exceed a transport capacity between the particular node pair. Each term of the sum comprises a product of a first placement variable, a second placement variable, and the transport demand between the services associated with the first and second placement variables. The second step forms an objective. The communication constraints and the objective comprise an integer program. The third step employs a local search solution to solve the integer program, which determines the placement of the services onto the nodes.
