Network traffic typically traverses a sequence of middleboxes forming a service function chain, or simply a chain. Tolerating failures when they occur along chains is imperative to the availability and reliability of enterprise applications. Making a chain fault-tolerant is challenging since, in the event of failures, the state of faulty middleboxes must be correctly and quickly recovered while providing high throughput and low latency.

A service-function chain, or simply a chain, is an ordered sequence of service functions, e.g., firewalls and load balancers, composing a service. A chain deployment involvesselectingand instantiating a number of virtual network functions (VNFs), i.e., softwarized service functions,placingVNF instances, androutingtraffic through them. In the current optimization-models of a chain deployment, the instances of the same function are assumed to be identical, while typical service providers offer VNFs with heterogeneous throughput and resource configurations. The VNF instances of the same function are installed in a single physical machine, which limits a chain to the throughput of a few instances that can be installed in one physical machine. Furthermore, theselection,placement, androutingproblems are solved in isolation. We present distributed service function chaining that coordinates these operations, places VNF-instances of the same functiondistributedly, and selects appropriate instances from typical VNF offerings. Such a deployment uses network resources more efficiently and decouples a chain’s throughput from that of physical machines. We formulate this deployment as a mixed integer programming (MIP) model, prove its NP-Hardness, and develop a local search heuristic called Kariz. Extensive experiments demonstrate that Kariz achieves a competitive acceptance-ratio of 76%–100% with an extra cost of less than 24% compared with the MIP model.