Centralized route determination in communication networks

A method for route determination, the method comprising:

• accessing, with a controller of a software defined network, a first set of constraints specifying whether route splitting is permissible for respective ones of a set of flows in the software defined network;
• accessing, with the controller, a second set of constraints specifying respective bandwidth demands for the respective ones of the set of flows in the software defined network;
• and
• determining, with a linear programming model implemented by the controller, a set of routes based on the first and second sets of constraints, the set of routes to route the set of flows in the software defined network, wherein the second set of constraints specifies respective first bandwidth demands expected at a future first time for the respective ones of the set of flows in the software defined network, the set of routes is a first set of routes to route the set of flows in the software defined network at the first time, the determining of the first set of routes is performed prior to the first time, and further including:
• accessing, prior to the first time, a third set of constraints specifying respective second bandwidth demands expected at a future second time later than the first time for the respective ones of the set of flows in the software defined network;
• determining, with the linear programming model and prior to the first time, a second set of routes based on the first and third sets of constraints, the second set of routes to route the set of flows in the software defined network at the second time;
• transmitting first routing information to a first set of nodes of the software defined network prior to the first time to cause routing tables maintained by respective ones of the first set of nodes to be updated to implement the first set of routes at the first time;
• and
• transmitting second routing information to a second set of nodes of the software defined network after the first time and prior to the second time to cause routing tables maintained by respective ones of the second set of nodes to be updated to implement the second set of routes at the second time.

A non-transitory computer readable medium comprising computer readable instructions which, when executed, cause a processor to perform operations comprising:

• accessing a first set of constraints specifying whether route splitting is permissible for respective ones of a set of flows in a software defined network;
• accessing a second set of constraints specifying respective bandwidth demands for the respective ones of the set of flows in the software defined network;
• determining, with a linear programming model, a set of routes based on the first and second sets of constraints, the set of routes to route the set of flows in the software defined network, the determining of the set of routes based on the first and second sets of constraints including:
• determining whether a combination of the first and second sets of constraints specified for the set of flows is able to be satisfied in the software defined network;
• and
• when the combination of the first and second sets of constraints specified for the set of flows is not able to be satisfied, determining the set of routes to meet a combination of a first subset of the first set of constraints and a first subset of the second set of constraints specified for a first subset of the set of flows having a first priority, but to not meet a combination of a second subset of the first set of constraints and a second subset of the second set of constraints specified for a second subset of the set of flows having a second priority different from the first priority;
• and
• transmitting routing information to a set of nodes implementing the software defined network to cause routing tables maintained by respective ones of the set of nodes to be updated to implement the set of routes.

An apparatus to perform route determination, the apparatus comprising:

• memory including machine readable instructions;
• and
• a processor to execute the instructions to perform operations including:
• accessing a first set of constraints specifying whether route splitting is permissible for respective ones of a set of flows in a software defined network;
• accessing a second set of constraints specifying respective bandwidth demands for the respective ones of the set of flows in the software defined network;
• determining, with a linear programming model, a set of routes based on the first and second sets of constraints, the set of routes to route the set of flows in the software defined network, the determining of the set of routes based on the first and second sets of constraints including:
• determining whether a combination of the first and second sets of constraints specified for the set of flows is able to be satisfied in the software defined network;
• and
• when the combination of the first and second sets of constraints specified for the set of flows is not able to be satisfied, determining the set of routes to meet a combination of a first subset of the first set of constraints and a first subset of the second set of constraints specified for a first subset of the set of flows having a first priority, but to not meet a combination of a second subset of the first set of constraints and a second subset of the second set of constraints specified for a second subset of the set of flows having a second priority different from the first priority;
• and
• transmitting routing information to a set of nodes implementing the software defined network to cause routing tables maintained by respective ones of the set of nodes to be updated to implement the set of routes.