Overview of IEEE NetSoft Conference 2017 Best Paper: “Catena: A Distributed Architecture for Robust Service Function Chain Instantiation with Guarantees”

Flavio Esposito, Saint Louis University, USA

IEEE Softwarization, July 2017

 

To offer wide-area distributed virtual network services, resources from multiple end-users and federated or geo-distributed) providers need to be managed. Such virtual resource management is, however, very complex, given the scale and constraints required by various applications. Moreover, multiple virtual network functions need to coexist in support of service function chains. For example, in an edge computing scenario supporting first responders in case of a natural or man-made disaster, or to support remote data-intensive edge processing for medical applications, service functions involving edge clouds (i.e. edge functions) are needed. Edge functions may range from management plane mechanisms, such as load balancing, firewalls, data acceleration, intrusion detection, network address translators or deep-packet inspections to data plane mechanisms, such as congestion control and network scheduling. Orchestrating such edge functions in a multi-tenant scenario requires instantiation and programmability of several network policies (not merely forwarding), to adapt to the dynamic nature of the service. By policy, we mean a variant aspect of any network mechanism, e.g., a desirable high-level goal dictated by users, applications, (5G or edge) infrastructure or service providers. Many systems for distributed service function chain orchestration are actively being developed (see e:g:, [1].) However, the ability to guarantee convergence and performance of multiple (virtualized) instances of a service function chain in a fully distributed fashion is still missing.

To this end, we designed and implemented Catena, (“chain” in Italian), a system that guarantees quick, resilient and fully distributed orchestration of a service (edge) function, i:e:, virtual path discovery, service chain mapping and resilient chain instantiation. Our Catena architecture solves the distributed chain mapping problem with an asynchronous consensus protocol, even in presence of (non byzantine) failures of processes or physical links.

Solutions that provide resilient decentralized asynchronous consensus already exists, see e:g:, the Paxos consensus algorithm [2] (a version of which is used even within Google data centers [3]) or the more recent Raft [4], adopted by the Open Network Operating System (ONOS) [1]. The design behind these protocols is sound, and although these approaches have been subject to recent optimizations and improvements (see e:g:, [5]), none of them simultaneously provides: (i) guarantees on the Pareto optimality of the elected set of leaders, (ii) bounds on the agreement convergence time, and (iii) a fully distributed approach (as opposed to a decentralized one as in [4]). Our Catena architecture bridges this gap with the following contributions:

Architectural contributions: leveraging stochastic optimization theory, we identified the mechanisms and the interactions composing what we called the resilient service function chain instantiation problem. The three necessary and sufficient set of mechanisms to instantiate a chain are: (i) state retrieval, (ii) chain mapping, and (iii) resource binding.

Algorithmic contributions: To efficiently and effectively solve the service chain mapping problem, one of the three mechanisms of the resilient service function chain instantiation problem, we propose a fully Distributed Asynchronous Chain Consensus Algorithm (DACCA), that is guaranteed to converge in the least possible number of messages (showing overhead improvement of up to 32% w.r.t. the Raft [4] consensus), and has probabilistic guarantees on the expected chain instantiation performance, with respect to a Pareto optimal network utility. In a nutshell, DACCA allows edge and core cloud providers to cooperatively instantiate wide-area service function chains with guaranteed convergence and performance, even in presence of failures that do not partition the physical network.

System contributions: We compared our DACCA mechanism simulating a few representative policies and analyzing the tradeoff, and we confirmed our results over a (RINA-based) prototype implementation [6], whose link is available on the main paper [7]. Our evaluation of Catena showed a few surprising results, among which the lower overhead with respect to the Raft [4] consensus protocol, and an higher acceptance rate resulting from a sequential sub-chain request, i:e:, each hosting process should attempt to map a single chain node at the time. Our released Catena prototype can be used by the community interested in 5G and edge cloud provider mechanism design for chain instantiation policy tradeoff analysis.

References

[1] P. Berde, M. Gerola, J. Hart, Y. Higuchi, M. Kobayashi, T. Koide, B. Lantz, B. O’Connor, P. Radoslavov, W. Snow, and G. Parulkar, “Onos: Towards an open, distributed sdn os”, in Proceedings of the Third Workshop on Hot Topics in Software Defined Networking, ser. HotSDN’14. New York, NY, USA: ACM, 2014, pp. 1–6. [Online]. Available: http://doi.acm.org/10.1145/2620728.2620744

[2] L. Lamport, “The part-time parliament”, ACM Trans. Comput. Syst., vol. 16, no. 2, pp. 133–169, May 1998. [Online]. Available: http://doi.acm.org/10.1145/279227.279229

[3] T. D. Chandra, R. Griesemer, and J. Redstone, “Paxos made live: An engineering perspective”, in Proceedings of the Twenty-sixth Annual ACM Symposium on Principles of Distributed Computing, ser. PODC ’07, 2007, pp. 398–407.

[4] D. Ongaro and J. Ousterhout, “In search of an understandable consensus algorithm”, in 2014 USENIX Annual Technical Conference (USENIX ATC 14), Jun. 2014, pp. 305–319.

[5] L. Lamport, “Fast paxos,” Distributed Computing, vol. 19, no. 2, pp. 79–103, 2006. [Online]. Available: http://dx.doi.org/10.1007/s00446-006-0005-x

[6] F. Esposito, Y. Wang, I. Matta, and J. Day, “Dynamic Layer Instantiation as a Service”, in In Proc. of 10th USENIX Symp. on Networked Systems Design and Implementation (NSDI 2013), Lombard, IL, April 2013, p. 98.

[7] F. Esposito, “Catena: A Distributed Architecture for Robust Service Function Chain Instantiation with Guarantees”, in Proc. of IEEE 3rd Conf. on Network Softwarization (NetSoft 2017), Bologna, Italy, July 2017.

 

^* Best Paper at NetSoft 2017

 

---

 

Flavio Esposito is an Assistant Professor of Computer Science at Saint Louis University, in Missouri, USA and he is a visiting professor by courtesy at University of Missouri, Columbia. He got his PhD in Computer Science from Boston University, USA, in 2013, and his Master of Science in Telecommunication Engineering at University of Florence, Italy.

Before joining Saint Louis University, Flavio has worked on data and network management problems as research scientist and software engineer at Exegy, an high frequency trading company in Saint Louis, MO, at Raytheon BBN Technologies, in Cambridge MA, and at Bell Laboratories, NJ. Flavio has also worked as visiting researcher at Eurecom, France, and in two research centers affiliated with the University of Oulu, Finland: Centre for Wireless Communications and MediaTeam. Flavio is currently managing an NSF award and he is a recipient of a best paper award at IEEE NetSoft 2017.