Orchestrating service function chains over resource-constrained network function virtualization (NFV) infrastructures

Abstract

Network Function Virtualization (NFV) has recently emerged as a prominent cloud computing paradigm to address the scalability limitations of middleboxes, such as firewalls, load-balancers, and proxies. By decoupling them from their underlying hardware and fostering their implementation in the form of virtual network functions (VNFs), middleboxes can now be deployed on commodity servers in the form of virtual machines or containers and scale on-demand in response to evolving resource requirements. In addition, multiple VNFs can be organized into an ordered sequence to form a service function chain (SFC). Admittedly, VNFs and SFCs are the two primary constructs within the NFV ecosystem. While NFV renders middlebox deployments more elastic and consequently cost-effective, it also introduces several challenges, primarily related to the management and orchestration of VNFs and SFCs. A particularly significant challenge is the SFC embedding (SFCE) problem, which pertains to the optimal mapping of VNFs and virtual links to their physical counterparts, namely servers and links within a substrate network. The optimization of SFCE is NP-hard, with both exact and approximate methods proposed in the literature. However, as the NFV landscape evolves, leaning towards localized and resource-constrained compute models such as edge clouds, the relevance and scope of prevailing SFCE methods shall be revisited. To substantiate this, we identify four critical limitations of existing SFCE methods in resourceconstrained NFV. The first one stems from SFCE optimization over a single resource dimension, i.e., the CPU. While in core datacenters the CPU is indeed the main resource bottleneck, this might not hold in resource-constrained networks, given the high versatility of resource demands, along with the potentially lower capacity of remaining resource types, e.g., storage, memory, etc. Another limitation of prevailing SFCE has its grounds on its lack to handle imminent cross-service communications. The latter, which are particularly attractive in edge clouds, introduce additional constraints to the standard SFCE scope, and these necessitate substantial SFCE adjustments. A third limitation results from centralized reinforcement learning (RL) schemes that can be found in the respective SFCE literature. These typically make highly optimistic assumptions with regard to the observability of the underlying network, challenging their practicality in real-life deployments. To this end, we identify the need for the investigation of more appropriate RL schemes in the context of SFCE and NFV orchestrators in general. Last, not much light has been shed on SFC pre-processing methods. As such, SFCs are mostly perceived as invariable constructs, which contradicts their very virtual structure. In extension, SFCE solvers might struggle to obtain solutions on par with the optimization objective during unfavourable network states (e.g., high utilization). This raises the need for SFC pre-processing algorithms that can optimize the SFC structure according to fluctuating network conditions. This thesis sets out to explore the aforementioned challenges. Specifically, (i) we investigate SFCE across multiple resource dimensions as a means to minimize resource wastage in resource constrained NFV, proposing adept heuristic and exact algorithms to handle the intricacies of the problem at hand. Subsequently, (ii) we study SFCE through the lens of cross-service communications, which is a relatively new concept in the realm of NFV that advocates for crossservice interactions, thus amplifying network capabilities. Further, (iii) we examine multi-agent RL schemes within SFCE, paying particular attention to concise cross-agent communications and the interpretation of the scheme’s learning capacity across various network topologies. Last, (iv) we delve into SFC graph transformations in order to adapt the SFC request according to the resource conditions of the underlying network, thus enabling SFCE solvers sustain highquality solutions even in conditions of limited resource availability and/or high level of resource fragmentation.

Η Εικονικοποίηση Δικτυακών Λειτουργιών (NFV) έχει πρόσφατα αναδειχθεί ως ένα σημαντικό πρότυπο υπολογιστικής νέφους για την αντιμετώπιση των περιορισμών κλιμάκωσης των middleboxes, όπως τα τείχη προστασίας και οι εξισορροπητές φορτίου. Με την αποσύνδεσή τους από το υποκείμενο υλικό τους και την προώθηση της υλοποίησής τους με τη μορφή εικονικών δικτυακών λειτουργιών (VNFs), τα middleboxes μπορούν πλέον να αναπτυχθούν σε διακομιστές γενικού σκοπού με τη μορφή εικονικών μηχανών ή container, και να κλιμακώνονται κατ' απαίτηση ανταποκρινόμενοι στις εξελισσόμενες απαιτήσεις πόρων. Επιπλέον, πολλαπλά VNFs μπορούν να οργανωθούν σε μια διατεταγμένη ακολουθία για να σχηματίσουν μια αλυσίδα δικτυακών λειτουργιών (SFC). Ενώ το NFV καθιστά τις αναπτύξεις των middleboxes πιο ευέλικτες και οικονομικά αποδοτικές, εισάγει επίσης αρκετές προκλήσεις, κυρίως όσον αφορά τη διαχείριση και την ενορχήστρωση των VNFs και SFCs. Μια ιδιαίτερα σημαντική πρόκληση είναι το πρόβλημα της τοποθέτησης των SFCs (SFCE), το οποίο αφορά τη βέλτιστη αντιστοίχιση των VNFs και των εικονικών συνδέσεων στα αντίστοιχα φυσικά τους στοιχεία, δηλαδή σε διακομιστές και συνδέσεις ενός φυσικού υποκείμενου δικτύου. Η βελτιστοποίηση του SFCE είναι NP-hard, και στη βιβλιογραφία προτείνονται τόσο ακριβείς αλλά και προσεγγιστικές μέθοδοι. Ωστόσο, καθώς το τοπίο του NFV εξελίσσεται, ανακύπτει μια έντονη τάση προς τοπικά δίκτυα που χαρακτηρίζονται από περιορισμένους πόρους, όπως τα δίκτυα παρυφών (edge). Υπό αυτό το πρίσμα, η συνάφεια και το πεδίο εφαρμογής των υφιστάμενων SFCE μεθόδων θα πρέπει να επανεξεταστούν. Eντοπίζουμε τέσσερις κρίσιμους περιορισμούς των υφιστάμενων μεθόδων SFCE σε δίκτυα NFV με περιορισμένους πόρους. Ο πρώτος προέρχεται από τη βελτιστοποίηση του SFCE σε μία μόνο διάσταση πόρων, δηλαδή, την CPU. Ενώ στα κεντρικά κέντρα δεδομένων (core datacenters) η CPU είναι πράγματι ο σπανιότερος πόρος, αυτό μπορεί να μην ισχύει στα δίκτυα περιορισμένων πόρων, δεδομένης της μεγάλης ευελιξίας των απαιτήσεων πόρων, σε συνδυασμό με τη δυνητικά χαμηλότερη χωρητικότητα των υπόλοιπων τύπων πόρων, π.χ., μνήμη, αποθηκευτικός χώρος, κ.λπ. Ένας άλλος περιορισμός του SFCE οφείλεται στην έλλειψη χειρισμού επικείμενων επικοινωνιών μεταξύ διαφορετικών SFCs. Τέτοιες επικοινωνίες εισάγουν πρόσθετους περιορισμούς στο τυπικό SFCE και απαιτούν σημαντικές προσαρμογές του. Ένας τρίτος περιορισμός προκύπτει από την κεντρικοποιημένη εφαρμογή ενισχυτικής μάθησης (RL) για το πρόβλημα του SFCE. Εδώ συνήθως γίνονται ιδιαίτερα αισιόδοξες υποθέσεις όσον αφορά την παρατηρησιμότητα του υποκείμενου δικτύου, αμφισβητώντας την πρακτικότητά τους σε πραγματικές εφαρμογές. Για το σκοπό αυτό, εντοπίζουμε την ανάγκη για τη διερεύνηση καταλληλότερων σχημάτων RL στο πλαίσιο του SFCE και των ενορχηστρωτών NFV γενικότερα. Τέλος, δεν έχει δοθεί πολύ φως στις μεθόδους προ-επεξεργασίας SFC. Ως εκ τούτου, τα SFCs ως επί το πλείστον εκλαμβάνονται ως αμετάβλητες οντότητες. Έτσι, οι SFCE solvers μπορεί να δυσκολεύονται να βρουν λύσεις που ικανοποιούν το κριτήριο βελτιστοποίησης όταν το φυσικό δίκτυο βρίσκεται σε μη ευνοϊκές καταστάσεις. Αυτό εγείρει την ανάγκη για αλγορίθμους προ-επεξεργασίας SFCs που μπορούν να βελτιστοποιήσουν τη δομή τους σύμφωνα με τις κυμαινόμενες συνθήκες του δικτύου.Η παρούσα διατριβή αποσκοπεί στη διερεύνηση των προαναφερθέντων προκλήσεων. Συγκεκριμένα, (i) διερευνούμε το SFCE σε πολλαπλές διαστάσεις πόρων ως μέσο ελαχιστοποίησης της σπατάλης πόρων σε NFV με περιορισμένους πόρους, προτείνοντας προσεγγιστικούς αλλά και ακριβείς αλγορίθμους για τον χειρισμό των επιπλοκών αυτού του προβλήματος. Στη συνέχεια, (ii) μελετάμε το SFCE μέσα από το πρίσμα της επικοινωνίας μεταξύ διαφορετικών SFCs, η οποία είναι μια σχετικά νέα έννοια στον τομέα του NFV που υποστηρίζει τις αλληλεπιδράσεις μεταξύ υπηρεσιών, ενισχύοντας έτσι τις δυνατότητες του δικτύου. Επιπλέον, (iii) εξετάζουμε σχήματα RL πολλαπλών πρακτόρων στο πλαίσιο του SFCE, δίνοντας ιδιαίτερη προσοχή στις συνοπτικές επικοινωνίες μεταξύ των πρακτόρων και ερμηνεύοντας την ικανότητα μάθησης του σχήματος σε διαφορετικές τοπολογίες δικτύου. Τέλος, (iv) εμβαθύνουμε στους μετασχηματισμούς γραφημάτων SFC προκειμένου να προσαρμόσουμε το αίτημα SFC σύμφωνα με τις συνθήκες πόρων του υποκείμενου δικτύου, επιτρέποντας έτσι στους SFCE solvers να βρίσκουν λύσεις υψηλής ποιότητας ακόμη και υπό συνθήκες περιορισμένων πόρων ή/και υψηλού κατακερματισμού πόρων.