Algorithms and techniques for optimal virtual network embedding in a cloud computing environment

Abstract

Resource virtualization is the fundamental catalyst for the continuous transformation and evolution of the digital world. Through this doctrine, both at the infrastructure and application levels, it is possible to break away from once dominant technologies and consolidate new promising ones. To make this transformation possible, an inevitable simultaneous radical reconfiguration of all parties involved is required, especially in the context of efficiently and optimally serving resource demands from critical applications, leveraging new virtual environments and their latent capabilities. Over the past decade, established Network Management Systems (NMS) deployments have begun their transition to integrating complex operations and management functions. The first part of this thesis examines modern orchestration technologies that enable the computation of network resources to serve emerging applications in novel telecommunication architectures. The plethora of modern day specialized applications migrating to an abstract environment, introduces new challenges, first and foremost in the premises of restructuring the dominant resource orchestration business model. The first part of the thesis concludes by introducing the vital redesign of production operations for the successful functionality of modern virtualized asset management. Notwithstanding, the process of optimizing the mapping of virtual components over physical ones creates new challenges that need to be addressed. A considerable number of Virtual Network Embedding (VNE) strategies that efficiently map virtual computational and networking demands over physical resources have already been proposed, adopting different optimizations. After completing the introductory part of this dissertation with the documentation of the life cycle of VNE and its formulations, we proceed to the initial steps of our research contribution. We consolidate and record the established varieties of optimization objectives and the corresponding metrics that are suitable for describing the performance of next-generation networks (NGN). After distinguishing the most representative VNE solutions, we then proceed to the in-depth comparison process. The comparison of the selected practices is done thoroughly and according to the different optimization strategies, under the same simulation conditions. The experimental results produced are analyzed in order to judge their suitability for serving NG applications and to pave the way for creating a new alternative way of mapping virtual networks. Our investigation did not stop at the optimization objectives categorization, but expanded to the category of heuristic algorithms. This field of strategies have been adopted to generate acceptable, near-optimal results in deterministic execution time. In this next part of our research, we approach the embedding procedures in terms of the most important heuristic algorithms by keeping the optimization functions fixed. Our study confirms that the one-stage procedure produces overall more acceptable results, while the two-stage procedure is a reliable choice for solving better allocation scenarios for VNE-oriented virtual resource distribution. In the next part of this phase of our research, we focus on the proposed strategies that have adopted different coordination proposals for solving the node and link mapping subproblems. In the fifth chapter of this thesis, we present the important results that we extracted from the study of the most popular embedding strategies, based on their coordination categorization. From the data analysis, it is understood that experimentation with coordination strategies, especially the one-stage ones, can bring additional benefits at multiple performance levels. Utilizing the overall knowledge that we gained from these three stages of our research, we were led to propose a new mixed coordination algorithm, essentially creating a new category in the field of VNE coordination strategies. However, the fourth industrial revolution introduced an exponential growth in heterogeneous connected devices and specialized applications alike, already creating the need to transgress the boundaries of the Fifth-Generation (5G) communication system and replace it with Sixth-Generation (6G) agile technologies. Hence, a plethora of fundamental issues need to constantly be addressed to effectively optimize the deployment of resilient service-centric and user-centric scenarios in NG environments. Limiting energy consumption, ensuring virtual network reliability, and guarantying desirable performance thresholds, are three foundational challenges complex enough even for service-based orchestrating scenarios. Furthermore, the diversification of resource requirements becomes more intense by incorporating the user’s customized parameterization regarding operating modern-day applications. Human-centric resource management is intended to overcome service-centric orchestration, becoming increasingly important for the operational support of networking ecosystems over NG telecommunication networks. The ever-growing need to enhance critical applications either at the cloud or at the edge level, leads both the industry and the academic community to specify new rules, based on which resource allocation mechanisms should operate natively and reliably. The adoption of fully intelligent management systems is certainly one of the milestones of the future. However, until their universal and total consolidation, the enhancement of existing resource assessment and allocation mechanisms is a transitional process that must take place. Within this context, the already developed frameworks should be reviewed, evaluating the efficiency of their orchestration stages. Thus, to realize consistent and optimal provisioning upon the physical underlay, by also integrating mechanisms that support user-based specifications, we propose a comprehensive network path enumeration and ordering framework by the means of the Paths Algebra (PA). This novel path evaluation strategy revolves around the three fundamental pillars that support the accommodation of both service-centric and immersive user-centric applications. Depending on the scenario, our proposed solution can produce either power-saving, reliability prone, or performance driven resource allocations. Under this prism, throughout the sixth, seventh, and eighth Chapter of the thesis, we introduce new primary network metrics and by utilizing suitable algebraic case-by-case compositions, we achieve our energy-based, reliability-oriented, and optimization-prone goals respectively. By satisfying the PA-based fundamental properties of monotonicity and isotonicity, we enable the synthetic metrics we propose to describe and classify candidate paths validly and optimally. Another competitive feature of our implementation is its seamless deployment capabilities, either on legacy or modern architectures, due to its algebraic architecture. The use of the tools offered by PA undoubtedly enhances the innovative design properties of our proposed solution. Our solution comes as an enabler of the upcoming 6G-based human-centric era and tackles the dire need for a modular framework that can integrate with metric-based optimization constructs, offering a new evaluation mechanism to successfully replace traditional path ranking and path selection techniques. The value of this PhD thesis is confirmed by the experimental data of our simulations. They indicate that the proposed framework suggests substantially more suitable paths in each studied VNE scenario than the compared methodologies, achieving adaptive optimizations for mission critical tailored objectives. Its innovative algebraic design allows it to successfully describe and rank candidate paths multidimensionally in contrast to their monothematic counterparts. The thesis concludes with its final Chapter, which summarizes all the individual conclusions of our collective research and sets the milestones for future work.

Η εικονικοποίηση είναι κοινώς αποδεκτή ως ο καταλύτης που θα δώσει στο Διαδίκτυο τη δυνατότητα να σπάσει τα δεσμά των τεχνολογιών παλαιού τύπου και να εξελιχθεί στον μελλοντικό του εαυτό. Για να καταστεί εφικτός αυτός ο μετασχηματισμός, απαιτείται αναπόφευκτα η ταυτόχρονη ριζική αναδιαμόρφωση όλων των εμπλεκόμενων, ιδιαίτερα στο πλαίσιο της αποτελεσματικής και βέλτιστης εξυπηρέτησης των αιτημάτων εφαρμογών, αξιοποιώντας νέα εικονικά περιβάλλοντα και τις κρυμμένες δυνατότητές τους. Κατά την τελευταία δεκαετία, τα καθιερωμένα Συστήματα Διαχείρισης Δικτύων (ΣΔΔ) ξεκίνησαν τη μετάβασή τους στην ενσωμάτωση πολύπλοκων διαδικασιών και λειτουργιών διαχείρισης. Το πρώτο μέρος αυτής της διατριβής εξετάζει τις σύγχρονες τεχνολογίες ενορχήστρωσης που επιτρέπουν τον υπολογισμό των πόρων του δικτύου για να εξυπηρετήσει αναδυόμενες εφαρμογές πάνω από νέες αρχιτεκτονικές τηλεπικοινωνιών. Η πληθώρα των σύγχρονων εξειδικευμένων εφαρμογών που μετεγκαθίστανται σε ένα αφηρημένο περιβάλλον, εισάγει νέες προκλήσεις, πρώτα και κύρια στο πλαίσιο της αναδιάρθρωσης του κυρίαρχου επιχειρηματικού μοντέλου ενορχήστρωσης πόρων. Το πρώτο μέρος της διατριβής ολοκληρώνεται με την παρουσίαση του ζωτικού επανασχεδιασμού των λειτουργιών παραγωγής για την επιτυχή λειτουργία της σύγχρονης εικονικής διαχείρισης εικονικών στοιχείων.Ωστόσο, η διαδικασία βελτιστοποίησης της αντιστοίχισης των εικονικών στοιχείων έναντι των φυσικών, δημιουργεί νέες προκλήσεις που πρέπει να αντιμετωπιστούν. Ένας σημαντικός αριθμός στρατηγικών της Ενσωμάτωσης Εικονικών Δικτύων (ΕΕΔ), που δεσμεύουν αποτελεσματικά τις εικονικές υπολογιστικές και δικτυακές απαιτήσεις πάνω σε φυσικούς πόρους, έχουν ήδη προταθεί ακολουθώντας διαφορετικούς στόχους βελτιστοποίησης. Αφού ολοκληρώσουμε το εισαγωγικό μέρος αυτής της διατριβής με την τεκμηρίωση του κύκλου ζωής της ΕΕΔ και τις διατυπώσεις της, προχωράμε στα αρχικά βήματα της ερευνητικής μας συνεισφοράς. Καταγράφουμε την ποικιλία των στόχων και των μετρικών απόδοσης που είναι κατάλληλες για Δίκτυα Επόμενης Γενιάς (ΔΝΓ). Εν συνεχεία, συγκρίνουμε διεξοδικά τις πιο κοινές προτεινόμενες λύσεις της ΕΕΔ με διαφορετικές στρατηγικές βελτιστοποίησης κάτω από τις ίδιες συνθήκες προσομοίωσης και διερευνούμε την καταλληλότητά τους για την εξυπηρέτηση εφαρμογών ΝΓ, κρίνοντάς τες από τα πειραματικά τους αποτελέσματα. Οι περισσότερες από αυτές τις προτεινόμενες στρατηγικές έχουν υιοθετήσει ευρετικούς αλγόριθμους για τη δημιουργία αποδεκτών, σχεδόν βέλτιστων αποτελεσμάτων σε προσιτό χρόνο εκτέλεσης. Ακολούθως, παρουσιάζουμε τη σημασία των ευρετικών αλγορίθμων στο πλαίσιο των διαδικασιών ενσωμάτωσης και συγκρίνουμε διεξοδικά δύο από τις πιο χαρακτηριστικές μεθοδολογίες εικονικής δέσμευσης πόρων με παρόμοιες συναρτήσεις στόχων, που χρησιμοποιούν ευρετικές μεθόδους για την επίλυση σεναρίων προσανατολισμένων στην ΕΕΔ. Η μελέτη μας επιβεβαιώνει ότι η διαδικασία ενός σταδίου παράγει πιο συγκεκριμένα αποτελέσματα συνολικά, ενώ αυτή των δύο σταδίων αποτελεί μια αξιόπιστη επιλογή για καλύτερη κατανομή εικονικών πόρων. Εν τούτοις, μεταξύ αυτών των προτεινόμενων στρατηγικών, έχουν υιοθετηθεί διαφορετικές προτάσεις συντονισμού, προκειμένου να υπολογιστούν οι φάσεις της εναπόθεσης των εικονικών κόμβων και των συνδέσμων. Στο πέμπτο μέρος της Διατριβής, μελετάμε τις δυνατότητες των πιο δημοφιλών στρατηγικών ενσωμάτωσης, βάσει της κατηγορίας συντονισμού όπου ανήκουν τους. Η μελέτη μας επιβεβαιώνει ότι με τη χρήση μιας στρατηγικής συντονισμού, ειδικά του ενός σταδίου, μπορούν να επιτευχθούν πρόσθετα οφέλη σε πολλαπλά επίπεδα απόδοσης. Επιπλέον, προτείνουμε έναν νέο αλγόριθμο μικτού συντονισμού, δημιουργώντας ουσιαστικά μια νέα κατηγορία στον τομέα των στρατηγικών ΕΕΔ που υιοθετούν τον συντονισμό. Μολαταύτα, η τέταρτη βιομηχανική επανάσταση εισήγαγε μια εκθετική ανάπτυξη σε ετερογενείς συνδεδεμένες συσκευές και εξειδικευμένες εφαρμογές, δημιουργώντας ήδη την ανάγκη υπέρβασης των ορίων των συστημάτων επικοινωνίας πέμπτης γενιάς (5Γ) και αντικατάστασής τους με ευέλικτες τεχνολογίες έκτης γενιάς (6Γ). Ως εκ τούτου, μια πληθώρα θεμελιωδών ζητημάτων πρέπει να αντιμετωπίζονται συνεχώς για να βελτιστοποιηθεί αποτελεσματικά η ανάπτυξη ανθεκτικών σεναρίων τόσο με επίκεντρο τις υπηρεσίες όσο και τον ίδιο τον χρήστη, σε περιβάλλοντα ΝΓ. Ο περιορισμός της κατανάλωσης ενέργειας, η διασφάλιση της αξιοπιστίας του εικονικού δικτύου και η εγγύηση των επιθυμητών ορίων απόδοσης είναι τρεις θεμελιώδεις προκλήσεις αρκετά περίπλοκες ακόμη και για υπηρεσιοκεντρικά σενάρια ενορχήστρωσης. Επιπλέον, η διαφοροποίηση των απαιτήσεων πόρων γίνεται εντονότερη με την ενσωμάτωση της προσαρμοσμένης παραμετροποίησης του χρήστη κατά τη λειτουργία σύγχρονων εφαρμογών. Η ανθρωποκεντρική διαχείριση πόρων έχει σκοπό να ξεπεράσει την ενορχήστρωση με επίκεντρο τις υπηρεσίες, καθιστώντας την ολοένα και πιο σημαντική για τη λειτουργική υποστήριξη των οικοσυστημάτων δικτύωσης μέσω των τηλεπικοινωνιακών δικτύων ΝΓ. Η ανάγκη για ενίσχυση κρίσιμων εφαρμογών υπαγορεύει την εμφάνιση μηχανισμών που θα μπορούσαν εγγενώς να παράγουν πιο αξιόπιστες κατανομές πόρων, είτε σε επίπεδο υπολογιστικού νέφους είτε ακροδικτυακά. Μέχρι την υιοθέτηση πλήρως τεχνητά ευφυών συστημάτων διαχείρισης, η ενίσχυση των υφιστάμενων μηχανισμών αξιολόγησης και κατανομής πόρων είναι υποχρεωτική κατά τη διάρκεια αυτής της μεταβατικής εποχής. Για να φτάσουμε σε αυτό το πιεστικό ορόσημο, θα πρέπει να αναθεωρήσουμε τα ήδη ανεπτυγμένα πλαίσια, αξιολογώντας τα στάδια ενορχήστρωσής τους. Έτσι, για να πραγματοποιηθεί συνεπής και βέλτιστη παροχή στο φυσικό υπόστρωμα, ενσωματώνοντας επίσης μηχανισμούς που υποστηρίζουν προδιαγραφές βασισμένες στον χρήστη, προτείνουμε ένα ολοκληρωμένο πλαίσιο απαρίθμησης και ταξινόμησης μονοπατιών δικτύου μέσω της Άλγεβρας Δρομολόγησης ή αλλιώς Άλγεβρας Διαδρομών (ΑΔ). Αυτή η νέα στρατηγική αξιολόγησης μονοπατιών περιστρέφεται γύρω από τους τρεις θεμελιώδεις πυλώνες που υποστηρίζουν τη διευθέτηση τόσο των εφαρμογών με επίκεντρο τις υπηρεσίες όσο και των καινοτόμων χρηστοκεντρικών εφαρμογών. Ανάλογα με το σενάριο, η λύση που προτείνουμε μπορεί να παράγει κατανομές πόρων με γνώμονα είτε την εξοικονώμηση ενέργειας, είτε την εξασφάλιση της αξιοπιστίας, είτε τη διασφάλιση της βέλτιστης απόδοσης. Υπό αυτό το πρίσμα, σε όλο το τέταρτο, πέμπτο και έκτο μέρος της Διατριβής, εισάγουμε νέες πρωτογενείς μετρήσεις δικτύου και χρησιμοποιώντας κατάλληλες αλγεβρικές συνθέσεις κατά περίπτωση, επιτυγχάνουμε τους ενεργειακούς στόχους, τους στόχους αξιοπιστίας ή εκείνων της απόδοσης, αντίστοιχα. Οι προτεινόμενες συνθετικές μετρικές διαβαθμίζουν τα υποψήφια μονοπάτια έγκυρα και βέλτιστα, τηρώντας τις θεμελιώδεις ιδιότητες της μονοτονικότητας και ισοτονικότητας της ΑΔ. Η λύση μας έρχεται ως ενεργοποιητής της επερχόμενης ανθρωποκεντρικής εποχής μέσω των δικτύων τηλεπικοινωνιών 6Γ και αντιμετωπίζει την απόλυτη ανάγκη για ένα αρθρωτό πλαίσιο που μπορεί να ολοκληρωθεί με μετρικές δομές βελτιστοποίησης, προσφέροντας έναν νέο μηχανισμό αξιολόγησης για την επιτυχή αντικατάσταση των παραδοσιακών τεχνικών κατάταξης και επιλογής μονοπατιών. Η αξία αυτής της διδακτορικής διατριβής επιβεβαιώνεται από τα πειραματικά δεδομένα των προσομοιώσεών μας. Τα αποτελέσματα υποδεικνύουν ότι το προτεινόμενο πλαίσιο παράγει ουσιαστικά πιο κατάλληλα μονοπάτια σε κάθε μελετημένο σενάριο ΕΕΔ από τις συγκριτικές μεθοδολογίες, επιτυγχάνοντας προσαρμοστικές βελτιστοποιήσεις για κρίσιμους προσαρμοσμένους στόχους. Ο πρωτοποριακός αλγεβρικός σχεδιασμός του επιτρέπει να περιγράφει και να ταξινομεί με επιτυχία υποψήφια μονοπάτια πολυδιάστατα, σε αντίθεση με τις μονοθεματικές αντίστοιχες λύσεις. Η διατριβή ολοκληρώνεται με το τελευταίο της κεφάλαιο, το οποίο συνοψίζει όλα τα επιμέρους συμπεράσματα της συλλογικής μας έρευνας και θέτει τα σημεία αναφοράς για μελλοντικούς ερευνητικούς στόχους.