2019 · 33 citations · 29 references
ComputingCloud ComputingComputer ScienceCloud InfrastructureDistributed SystemsEdge ComputingCloud Capacity PlanningCloud Infrastructure DesignEdge Computing InfrastructureLatency OptimizationResource SchedulingApproximation GuaranteesBackupCapacity ConstraintsChance ConstraintsFunction ChainingGeo-distributed SystemsService ChainingService Function Chaining
Traditionally, Network Function Virtualization uses Service Function Chaining (SFC) to place service functions and chain them with corresponding flows allocation. With the advent of Edge computing and IoT, a retiable composition of latency-sensitive SFCs is needed to support applications in geo-distributed cloud infrastructures. However, the optimal SFC composition in this case becomes the NP-hard integer multi-commodity-chain flow (MCCF) problem that has no known approximation guarantees. In this paper, we present a novel practical and near optimal SFC composition approach for geo-distributed cloud infrastructures that also admits end-to-end network QoS constraints such as latency, packet loss, etc. Specifically, we propose a novel metapath composite variable approach that reaches 99% optimality on average and takes seconds for practically sized integer MCCF problems of US Tier-1 (~300 nodes) and regional (~600 nodes) infrastructure providers' topologies. To ensure reliability, we compose SFCs with capacity chance-constraints and backup policies. Using trace-driven simulations comprising of challenging disaster-incident conditions, we show that our solution composes twice as many SFCs than the state-of-the-art network virtualization methods.
29
Network Flows: Theory, Algorithms, and Applications.
David K. Smith, Ravindra K. Ahuja, Thomas L. Magnanti et al. · Journal of the Operational Research Society · 1994 · 8.2K citations · Full text
Network flows: Theory, algorithms and applications
Discrete Applied Mathematics · 1994 · 2.6K citations
Sushant Jain, Alok Kumar, Subhasree Mandal et al. · 2013 · 1.8K citations
Simon Knight, Hung Nguyen, Nickolas Falkner et al. · IEEE Journal on Selected Areas in Communications · 2011 · 1.7K citations