Service function chain composition and placement using grammar‐based genetic algorithm.

Summary: Service function chaining (SFC) creates a requested orchestration for composition and placement of several service functions. One of the most critical issues for the service function providers is achieving the highest quality of service. We consider the problem of optimal Service Function composition and placement in an SFC‐enabled network with the aim of achieving maximum Quality of Service (QoS). To this end, a method of merging the composition, routing, and placement phases is introduced. A genetic algorithm is designed to find the service chain instance with the maximum QoS using grammar‐based Genetic Algorithm (GA) operators. This grammar is provided to filter invalid service compositions based on the data center, security, and mobile scenarios defined by Internet engineering task force. A chromosome in the proposed genetic algorithm corresponds to a service chain instance that matches the proposed grammar. For routing, strongly connected components (SCCs) are extracted to reduce search time in the network. Consequently, the search space is reduced for requests whose start and end nodes are placed in a SCC. Besides, the Floyd Warshall algorithm is used for routing between consecutive services. According to the results, the proposed method outperformed other methods in terms of the number of responded requests, runtime, and cost. [ABSTRACT FROM AUTHOR]