IETF-based Finite Automaton for Service Composition in Service Function Chaining

The Service Function Chaining (SFC) is an architecture to orchestrate network services by creating and deploying the rule-based service function chains and steering network traffic through them. One of the main tasks in SFC is the optimal composition of the service functions and checking the validation of the composed service chain based on the predefined rules. As the problem of optimal chain composition is NP hard, in this paper a Finite Automaton (FA) model is proposed to limit the solution space by considering the practical scenarios. Since the chaining rules depend on the substrate physical platform, the proposed FA is based on the data centre, mobile, and security scenarios introduced by Internet Engineering Task Force (IETF). Subsequently, Finite Automaton Matcher (FAM) shows that the proposed FA is an acceptable tool for validating the correctness of the composed service chain. Experimental results and complexity analysis show that this method reduces the number of service chain compositions and therefore the time complexity significantly.