Reversed Roadmap example (abridged) for

Bhamare, Deval, et al. “Optimal virtual network function placement in multi-cloud service function chaining architecture.” Computer Communications 102 (2017): 1-16.

ABSTRACT

• TOPIC: Service Function Chaining (SFC) is the problem of deploying various network service instances over geo-graphically distributed data centers and providing inter-connectivity among them.

• Topic 2 level of detail: The goal is to enable the network traffic to flow smoothly through the underlying network, resulting in an optimal quality of experience to the end-users. Proper chaining of network functions leads to optimal utilization of distributed resources. This has been a de-facto model in the telecom industry with network functions deployed over underlying hardware.

• PROBLEM: Though this model has served the telecom industry well so far, it has been adapted mostly to suit the static behavior of network services and service demands due to the deployment of the services directly over physical resources.

• Importance of solving the problem: This results in network ossification with larger delays to the end-users, especially with the data-centric model in which the computational resources are moving closer to end users.

• Highlight of the chosen approach to problem: A novel networking paradigm, Network Function Virtualization (NFV), meets the user demands dynamically and reduces operational expenses (OpEx) and capital expenditures (CapEx), by implementing network functions in the software layer known as virtual network functions (VNFs). VNFs are then interconnected to form a complete end-to-end service, also known as service function chains (SFCs).

• WORK AIM: In this work, we study the problem of deploying service function chains over network function virtualized architecture.

• Subobjectives: Specifically, we study virtual network function placement problem for the optimal SFC formation across geographically distributed clouds.

• APPROACH TO MEET THE AIM: We set up the problem of minimizing inter-cloud traffic and response time in a multi-cloud scenario as an ILP optimization problem, along with important constraints such as total deployment costs and service level agreements (SLAs). We consider link delays and computational delays in our model. The link queues are modeled as M/D/1 (single server/Poisson arrival/deterministic service times) and server queues as M/M/1 (single server/Poisson arrival/exponential service times) based on the statistical analysis. In addition, we present a novel affinity-based approach (ABA) to solve the problem for larger networks. We provide a performance comparison between the proposed heuristic and simple greedy approach (SGA) used in the state-of-the-art systems. Greedy approach has already been widely studied in the literature for the VM placement problem. Especially we compare our proposed heuristic with a greedy approach using first-fit decreasing (FFD) method.

• RESULTS: not explicitly individualized.

STUDY CONTRIBUTIONS:

• By observing the results, we conclude that the affinity-based approach for placing the service functions in the network produces better results compared against the simple greedy (FFD) approach in terms of both, total delays and total resource cost.

• We observe that with a little compromise (gap of less than 10% of the optimal) in the solution quality (total delays and cost), affinity-based heuristic can solve the larger problem more quickly than ILP.

1. INTRODUCTION

1 paragraph: Introduces the concept of Network Function Virtualization (NFV) in a way that conveys a CURRENT need for it

• Introduce concept of Virtualized Network Functions (VNFs)

2 paragraph: NFV infrastructure in the context of virtual infrastructure cloud service providers

3 paragraph: Description of Virtual network functions (VNFs) deployment challenges

• Introduce Service Function Chaining (SFC) concept

• Argue for the dynamics between NFV and SFC techniques

4 paragraph: Describes an SFC service chain example to bring the reader closer to the subtopics

5 paragraph: Introduces ASP potential complexity by using a figure to showcase Network service, Service functions and Service chain dynamics.

6 paragraph:

• Work objective/contribution
• Why there is a need for the work objective
• Identify state of the art advancements if the objective is met
• General approach to address the objective
• Study boundaries (e.g. With the simulation results using regression methods, we demonstrate that..)

7 paragraph: Sublevels of study boundaries

• ILP not scalable
• performance comparison between the proposed heuristic and simple greedy approach
• compare the performance of the proposed ABA approach with “Simple Greedy Allocation”
• demonstrate that with affinity-based approach, one can accommodate more stringent service level agreements
• demonstrate that ABA produces results that are closer to optimal (gap within 10% of the optimal solution) compared against SGA

Last paragraph: Key in a long paper as this one, it provides framework mindset for the reader.

2. RELATED WORK

1 paragraph: Service Function Chaining (SFC) in depth description

• Include NFV architecture proposed by ETSI.

2 paragraph: Approaches to practical deployment of service function chains in cloud environments

3 paragraph: Discuss literature for models for formalizing the chaining of network functions using a context-free language

4 paragraph: Discuss optimization models for dynamic composition of the network service chains

5 paragraph: Discuss use of virtualization techniques

6 paragraph: Present the need for efficiently perform the placement and chaining of virtual network functions to make NFV a reality

7 paragraph: introduce Service Level Agreements (SLAs)

8 paragraph: Argue for the study angle motivation, i.e., we argue that the problem needs to be revisited in the context of service function chaining.

9 paragraph: Argue for the study focus, i.e., there is a dearth of the research works which take interconnectivity between various workloads or service chains into account

10 paragraph: Summarise approaches to study objectives

3. Optimization model

Set up the problem of minimizing inter-cloud traffic and response time in a multi-cloud scenario as an ILP optimization problem.

• Include:
• Tables (List of acronyms, Parameters for Integer Linear Program (ILP))
• Figure (Service function chains)
• Functions 1-16

4. Heuristics

Propose ABA heuristic to solve the problem in real time scenarios for larger networks

• Include:
• interpret Tables (Heuristic step I., VNF placement constraints for SFC 5, Fraction of data flows between the VNFs, Greedy heuristic step II., User types, Affinity-based heuristic step II.)
• interpret Figures (A service flow Graph for SFC 5, Predicting user delays.)

5. Experimental setup and results

Introduce 3 analysis:

• analyze the performance of the proposed affinity-based (ABA) heuristics against simple greedy approach using first-fit decreasing (FFD) method

• compare their results with the results of the ILP based solution.

• compare the results of the greedy (FFD) approach with the affinity-based (ABA) approach

• Include + interpret figures

• A sample 200 node topology generated using GUESS, A closer look at the user-cluster, ILP vs. FFD greedy (varying cluster size), ILP vs. FFD greedy (varying traffic load), ILP vs. FFD greedy column-chart (varying user cluster size), ILP vs. affinity-based heuristic (varying cluster size), ILP vs. affinity-based heuristic (varying traffic loads), ILP vs. affinity-based heuristic column-chart (varying cluster size), Performance of FFD greedy, Performance of affinity-based approach.

• Include + interpret tables

• Resource configuration from EC2, ILP vs. FFD greedy, ILP vs. affinity-based, Comparison of heuristic results, Standard deviation for results, Margin of error for results.

6. Conclusions

1ST paragraph:

• Reminds the reader on the current need/interest of/on service function chaining and network function virtualization
• Summarizes the approach (analytical study…)
• Provides the focus and next the aim

2ND paragraph:

• Summarizes main achievements
• optimization model with applicable constraints
• novel Affinity-based approach
• quality of the solution is much improved using Affinity-based approach with only a marginal increase in execution time as compared to the FFD greedy approach.
• Highlights solutions potential for more complex SLAs and QoS constraints.