National and Kapodistrian University of Athens
Approximation Algorithms for Virtual Service Functions Chain Placement
Abstract
dc:descriptionΗ εικονικοποίηση λειτουργιών δικτύου (NFV) είναι μια αναδυόμενη τεχνολογία στην οποία η επεξεργασία των ροών του δικτύου δεν εκτελείται πλέον από εξειδικευμένο hardware, αλλά αντίθετα, μπορεί να επιτελείται σε απλούστερους servers που βρίσκονται σε κόμβους ενός κατανεμημένου υπολογιστικού νέφους (cloud). Αυτές οι λειτουργίες συνήθως εκτελούνται σύμφωνα με πολιτικές που έχουν σχεδιαστεί από τους μηχανικούς του δικτύου. Τέτοιες λειτουργίες μπορεί να είναι τείχη προστασίας, εξισορροπητές φορτίου, φίλτρα περιεχομένου και βαθιά επιθεώρηση πακέτων. Αυτή η τεχνολογία στοχεύει στην αντιμετώπιση των βασικών προκλήσεων της δικτυακής υποδομής (data centers) των παρόχων υπηρεσιών, όπως το χρηματικό κόστος, οι περιορισμοί χωρητικότητας, η πολυπλοκότητα της διαχείρισης του δικτύου, η κατανάλωση ενέργειας και οι αστοχίες λογισμικού. Ένα από τα κύρια πλεονεκτήματα αυτής της προσέγγισης είναι ότι οι λειτουργίες εικονικού δικτύου (VNF) μπορούν να δημιουργηθούν και να κλιμακωθούν κατ’ απαίτηση χωρίς την ανάγκη εγκατάστασης νέου εξοπλισμού. Οι ροές δικτύου συχνά απαιτείται να υποβάλλονται σε επεξεργασία από μια διατεταγμένη ακολουθία λειτουργιών δικτύου. Για παράδειγμα, ένα σύστημα ανίχνευσης εισβολής μπορεί να χρειαστεί να επιθεωρήσει τα πακέτα πριν από τη συμπίεση ή κρυπτογράφηση τους. Επιπλέον, διαφορετικοί πελάτες μπορούν να έχουν διαφορετικές απαιτήσεις λειτουργίας σχετικά με την ακολουθία των λειτουργιών δικτύου που πρέπει να εκτελεστούν. Η διατεταγμένη ακολουθία πολλαπλών VNFs που απαιτείται να εκτελεστεί σε ένα δίκτυο ονομάζεται αλυσίδα εικονικών λειτουργιών (Service Function Chain - SFC). Ένα θεμελιώδες πρόβλημα που προκύπτει όταν ασχολούμαστε με αλυσίδες λειτουργιών δικτύου είναι η ανάθεσή τους σε επιλεγμένους κόμβους του δικτύου με σκοπό την βελτιστοποίηση κάποιου κριτηρίου. Αυτό το πρόβλημα είναι γενικά πολύ δύσκολο να λυθεί και οι περισσότε-ροι υπάρχοντες αλγόριθμοι, κυρίως ευρετικοί, δεν έχουν εγγυημένη απόδοση. Για το λόγο αυτό, στην παρούσα διπλωματική εργασία μελετάμε κάποιους σημαντικούς προσεγγιστικούς αλγόριθμους για την τοποθέτηση SFCs/VNFs. Προσπαθούμε να δείξουμε πώς ορισμένες περιπτώσεις του προβλήματος τοποθέτησης SFC/VNF μεταπίπτουν σε γνωστά προβλήματα, όπως το Πρόβλημα Πολλαπλών Σακιδίων με Περιορισμούς Ανάθεσης και το Πρόβλημα Μεγιστικού Καλύμματος με Περιορισμό Πόρων. Προτείνουμε επίσης έναν ορισμό προβλήματος που προκύπτει σε περιβάλλοντα υπολογιστικού νέφους. Εκεί οι διαχειριστές αποσκοπούν στις πιο προσοδοφόρες, από πλευράς ρυθμού μετάδοσης δεδομένων, αλυσίδες υπηρεσιών υπό περιορισμούς πόρων και προτείνουμε μια πιθανή λύση για μια ειδική περίπτωση του προβλήματος.
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Λαζαρόπουλος Νικόλαος
- Lazaropoulos Nikolaos
Subjects
dc:subject × 2Rights
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
- uoadl:3232784