Study of SDN Controller Locations in Network Environments - (:unkn) unknown (My University, 2021)
Η εμφάνιση των δημόσιων και ιδιωτικών υπηρεσιών cloud είχε ως αποτέλεσμα την κατ 'απαίτηση πρόσβαση σε υποδομές, εφαρμογές και άλλους πόρους. Για παράδειγμα, οι εφαρμογές μεγάλων δεδομένων απαιτούν παράλληλη επεξεργασία μαζικών δεδομένων σε χιλιάδες διακομιστές. Αυτοί οι διακομιστές πρέπει να είναι σε θέση να επικοινωνούν μεταξύ τους, προκειμένου να παράξουν το τελικό αποτέλεσμα. Αυτή η επικοινωνία απαιτεί τεράστιο bandwidth δικτύου. Αυτός ο όγκος δεδομένων έθεσε πολλές προκλήσεις στην υπάρχουσα αρχιτεκτονική δικτύου TCP/IP. Το Software Defined Networking (SDN) έχει προταθεί ως νέα αρχιτεκτονική δικτύου για να λύσει αυτού του είδους τις προκλήσεις. Τα \SDN είναι ικανά να διαχειρίζονται τους πόρους του δικτύου με κεντρικό τρόπο. Επιτρέπουν τη δυναμική και αποτελεσματική διαμόρφωση δικτύου για να αυξήσουν την απόδοσή του. Αυτή η αύξηση της απόδοσης επιτυγχάνεται με τον διαχορισμό της διαδικασίας προώθησης δεδομένων από τη διαδικασία δρομολόγησης των πακέτων. Η λειτουργία του δικτύου αποδομήται σε δύο διαφορετικά επίπεδα: το επίπεδο ελέγχου και το επίπεδο δεδομένων. Το επίπεδο ελέγχου είναι υπεύθυνο για τη αποτελεσματική διαχείριση των πόρων του δικτύου, ενώ το επίπεδο δεδομένων είναι υπεύθυνο για την προώθηση των πακέτων από την πηγή στον προορισμό. Μια συνηθισμένη περίπτωση χρήσης των SDN είναι η διαχείριση των backbone δικτύων. Αυτού του είδους δίκτυα αποτελούνται από μεγάλο αριθμό συσκευών στο δίκτυο και σχετικά μεγάλες αποστάσεις μεταξύ κόμβων. Οι μεγάλες αποστάσεις μεταξύ των κόμβων δημιουργούν έναν περιορισμό ότι ο controller ενός SDN δεν θα μπορούσε να τοποθετηθεί σε κακή θέση, δηλαδή σε σημείο όπου ο controller έχει ελάχιστες αποστάσεις από μερικούς κόμβους του δικτύου και μεγάλες αποστάσεις μεταξύ των υπόλοιπων κόμβων. Αντ 'αυτού, ο controller πρέπει να τοποθετηθεί σε μια θέση που η απόσταση του από τις υπόλοιπες συσκευές του δικτύου είναι ελάχιστη. Αυτό το πρόβλημα λέγεται 1-median. Υπάρχουν πολλοί τρόποι για την αντιμετώπιση του συγκεκριμένου προβλήματος, η πιο κοινή είναι η διατύπωσή του σε Integer Linear Problem και στη συνέχεια να επιλυθεί με την χρήση ευρετικών μεθόδων. Αυτή η μελέτη παρουσιάζει μια προσέγγιση που ενσωματώνει στοιχεία της αλγεβρικής θεωρίας γράφων. Η προτεινόμενη προσέγγιση χρησιμοποιεί τα φασματικά χαρακτηριστικά του distance matrix, στην οποία οι γραμμές και οι στήλες ευρετηριάζονται από τους κόμβους του γράφου και συμπληρώνεται με τη μικρότερη απόσταση μεταξύ κάθε ζεύγους κόμβων. Πιο συγκεκριμένα, η προτεινόμενη μέθοδος χρησιμοποιεί το ιδιοδιανύσμα του distance matrix που αντιστοιχεί στη μεγαλύτερη ιδιοτιμή του. Η επιλογή του median κόμβου γίνεται με την εύρεση του στοιχείου του κύριου ιδιοδιανύσματος που είναι πιο κοντά στο μηδέν. Η αξιολόγηση της προτεινόμενης μεθόδου πραγματοποιείται σε τυχαίους γράφους δέντρων και διάφορους αριθμούς κόμβων. Στόχος της είναι να επιλέξει τη βέλτιστη λύση του median προβλήματος εφαρμοσμένο στα SDNs. Ένα πρόγραμμα στη γλώσσα προγραμματισμού Python αναπτύσσεται προκειμένου να διευκολυνθεί τη διαδικασία αξιολόγησης. Αυτό το πρόγραμμα είναι υπεύθυνο για τη δημιουργία των τυχαίων γράφων δέντρων, την παραγωγή του distance matrix και στη συνέχεια τη σύγκριση της λύσης της προτεινόμενης μεθόδου με το πραγματικό median του δικτύου. Η προτεινόμενη μέθοδος αξιολογείται σε τυχαία γραφήματα δέντρων όπου το βάρος κάθε σύνδεσης είναι ίσο με ένα. Η προτεινόμενη μέθοδος δεν είναι σε θέση να βρει τη βέλτιστη λύση σε ορισμένες περιπτώσεις αυτών των γράφων. Η προτεινόμενη μέθοδος αξιολογείται επίσης σε τυχαία γραφήματα δέντρων που οι συνδέσεις της έχουν τυχαία βάρη. Τα αποτελέσματα δείχνουν ότι η προτεινόμενη μέθοδος μπορεί να βρει τον μέσο του γράφου στις περισσότερες περιπτώσεις δικτύων ακόμη και σε τοπολογίες μεγάλης κλίμακας.

The emergence of the public and private cloud services resulted in on demand access to infrastructure, applications and other resources. For instance the the big data applications requires parallel processing of massive data on thousands of servers. These servers must be able to communicate with each other, to produce the final result. This communication requires a huge amount of network bandwidth. This amount of data raised many challenges to the existing TCP/IP network architecture. Software Defined Networking (SDN) has been proposed as a new network architecture to tackle these challenges. The SDNs are capable of managing the network resources in a centralized manner. They allow dynamic and efficient network configuration to increase the network's performance. This increase in performance is accomplished by disassociating the forwarding process from the routing process. The network's function is decoupled into two distinct planes: the control plane and the data plane. The control plane is in charge of managing the network's resources efficiently, while the data plane is responsible for forwarding the packets from source to destination. A common use case of SDNs is to facilitate backbone networks. Backbone networks consist of large number of devices in the network and relatively long distances between nodes. The long distances of between nodes raises a constraint that the controller of a SDN could not be placed in a bad location, i.e. the controller has minimum distances between a handful of switches and long distances between the remaining devices. Instead, the controller must be placed at a location that its distance from the devices of the network is minimum. This problem is the 1-median problem. There are numerous ways to tackle this problem the most common is to formulate the problem in an integer linear problem and then solve it using heuristics. This study presents an approach that incorporates elements of algebraic graph theory. The proposed approach uses the spectral characteristics of the distance matrix, in which rows and columns are indexed from the nodes of the graph and is populated with the shortest distance between each pair of nodes. More specifically, the proposed method uses the eigenvector of the distance matrix that corresponds to its largest eigenvalue, this eigenvector is also named principal eigenvector of the distance matrix. The selection of median is done by finding the element of the principal eigenvector that is closer to zero. The evaluation of the proposed method is performed over various cases and number of nodes in random tree graphs. Its aim is to select the optimal solution of the median problem applied to SDNs. A program in Python programming language is developed in order to facilitate this evaluation process. This program is responsible to create the random tree graphs, produce the distance matrix and then to compare the acquired solution to the actual median. The proposed method is firstly evaluated on random tree graphs with each edge weight equal to one. The proposed method is not able to find the optimal solution in some cases of these graphs. The proposed method is also evaluated on random tree graphs that its edges have random weights. The results show that the proposed method can find the median of a graph in most cases even in large-scale topologies.
Μελέτη Τοποθέτησης SDN Ελεγκτών σε Σύγχρονα Δικτυακά Περιβάλλοντα
Keywords: τοποθέτιση ελεγκτή, αλγεβρικη θεωρεία γράφων, δίκτυα καθορισμένα από λογισμικό; controller placement, algebraic graph theory, software defined networks