Path determination method and system for delay-optimized service function chaining

A method as implemented in a controller in a software defined network (SDN) comprising a plurality of network switches interconnected with a plurality of transmission facilities, either the network switches or hardware platforms attached to the switches hosting a plurality of virtual network functions, the method comprising:

• (a) receiving one or more service function chain orders of packet flows, at least one of the orders comprising a service function chain;
• (b) receiving, in real-time, delay measurements from any of, or a combination of, the following:
• one of the virtual network functions and one of the network switches;
• (c) determining a plurality of realizations of the service function chain orders of (a) in order to minimize a total delay, where the total delay is computed from one or more delays incurred due to a chain of one or more virtual network functions in the plurality of virtual network functions and due to one or more network switches in the plurality of network switches;
• (d) choosing an optimal realization within the plurality of realizations corresponding to a least delay;
• (e) determining one or more flow rules for the one or more network switches in the plurality of network switches, the determining based on the optimal realization in, and
• (f) determining an alternative route for an active lower priority service chain if a feasible solution for a higher priority service chain is not realizable to re-optimize the network and preempts the active lower priority service chain by rerouting them towards alternative higher delay virtual service functions.

An article of manufacture comprising non-transitory computer storage medium storing computer readable program code which, when executed by a processor implements a method as implemented in a method as implemented in a controller in a software defined network (SDN) comprising a plurality of network switches interconnected with a plurality of transmission facilities, either the network switches or hardware platforms attached to the switches hosting a plurality of virtual network functions, the computer storage medium comprising:

• (a) computer readable program code receiving one or more service function chain orders of packet flows, at least one of the orders comprising a service function chain;
• (b) computer readable program code receiving, in real-time, delay measurements from any of, or a combination of, the following:
• one of the virtual network functions and one of the network switches;
• (c) computer readable program code determining a plurality of realizations of the service function chain orders of (a) in order to minimize a total delay, where the total delay is computed from one or more delays incurred due to a chain of one or more virtual network functions in the plurality of virtual network functions and due to one or more network switches in the plurality of network switches;
• (d) computer readable program code choosing an optimal realization within the plurality of realizations corresponding to a least delay;
• (e) computer readable program code determining one or more flow rules for the one or more network switches in the plurality of network switches, the determining based on the optimal realization in (d), and
• (f) computer readable program code determining an alternative route for an active lower priority service chain if a feasible solution for a higher priority service chain is not realizable to re-optimize the network and preempts the active lower priority service chain by rerouting them towards alternative higher delay virtual service functions.