Future networks are expected to support cross-domain, cost-aware and fine-grained services in an efficient and flexible manner. Service Function Chaining (SFC) has been introduced as a promising approach to deliver these services. In the literature, centralized resource orchestration is usually employed to process SFC requests and manage computing and network resources. However, centralized approaches inhibit the scalability and domain autonomy in multi-domain networks. They also neglect location and hardware dependencies of service chains.

In this paper, we propose federated service chaining, a distributed framework which orchestrates and maintains the SFC placement while sharing a minimal amount of domain information and control. We first formulate a deployment cost minimization problem as an Integer Linear Programming (ILP) problem with fine-grained constraints for location and hardware dependencies, which is NP-hard. We then devise a Distributed Federated Service Chaining placement approach (DFSC) using inter-domain paths and border nodes information. Our extensive experiments demonstrate that DFSC efficiently optimizes the deployment cost, supports domain autonomy and enables faster decision-making. The results show that DFSC finds solutions within a factor 1.15 of the optimal solution. Compared to a centralized approach in the literature, DFSC reduces the deployment cost by 12% while being one order of magnitude faster.