Στοχαστικά μοντέλα για την ανάλυση δεδομένων στο διαδίκτυο

Abstract

The purpose of this dissertation was to study the characteristics of internet traffic and to develop appropriate models and techniques that address traffic load forecasting, dynamic bandwidth allocation based on predictions and generation of synthetic traffic that resembles real motion video. In addition, the connection between networks and their topology with time series has been explored so that the properties of the resulting time series can be used as means to classify the corresponding networks; a process which is particularly important since the networks can be more or less resistant to malicious attacks depending on their type. Internet traffic as we know is generated by the different types of media connected to it and it involves audio, video, images, Ethernet, LANs, WANs, etc. For all these different types of traffic, their modeling is necessary to solve their different arising problems. Τhe topics covered by the dissertation are of interest both in terms of stochastic modeling and in terms of of telecommunication engineering where the modeling of traffic is necessary for other tasks such as bandwidth allocation and generation of synthetic traffic.The first chapter of the dissertation presents a general overview of the Internet that concerns both a historical retrospect of its creation and organization, its modeling approaches, its movement and its topology. In the second chapter we study the basic characteristics of the Internet, both in terms of distributions for the various metrics (static characteristics) and its time dynamics . In terms of the time series models, we present only those with which Internet traffic can be modeled and which also constitute the basis of the methodologies that will be developed later in Chapters 3, 4 and 5. Finally, we present basic concepts and elements of network science that are necessary both for the understanding of the features of internet topology and for the development of the methodology which is proposed in Chapter 6 and it refers to the categorization of networks on scale-free or non scale-free.The first subject of the dissertation is presented in Chapter 3 and is the prediction of internet traffic. The most accurate forecast is necessary to resolve issues such as resource allocation of a system and network design. Based on models such as FARIMA, GARCH and Artificial Neural Networks, predictive schemes are proposed through their combinations, along with a model selection scheme that is based on testing for non-linearity and also hybrid models that combine structurally individual models. Lastly, a framework for the comparison of the different forecasting methodologies is suggested in order to decide about the most appropriate forecasting approach. In Chapter 4, the previously developed predictive approaches are used to dynamically allocate bandwidth to an end-to-end network, a very important problem that is part of the overall network resource management. The availability of bandwidth in general can be realized either statically, which does not take into account fluctuations in demand, either dynamically, so the prediction plays an essential role. For this chapter a process was also designed to select a prediction model that has the ability to be accurate in prediction, but at the same time it can be successfully applied to bandwidth allocation schemes. The candidate models were FARIMA and FARIMA / GARCH, the hybrid models FARIMA - MLP and FARIMA / GARCH - MLP as well as two prediction strategies where one selects a model depending on the result of a test for non - linearity in the dependence structure of data and the other combines predictions from different methodologies. Three different dynamic schemes are proposed for bandwidth allocation and are evaluated using metrics. From their comparison the best forecasting methodology is detected and significant conclusions are drawn on the proposed bandwidth allocation schemes. The third subject of this dissertation is presented in Chapter 5 and refers to the generation of synthetic traffic through time series models. The ability to simulate Internet traffic can contribute to more efficient network management and performance analysis. Because real-network performance analysis can be costly and measurements are difficult, the mathematical models that can be used to generate traffic are very important. In this context, FARIMA and FARIMA / GARCH time series models are considered in order to achieve synthetic traffic with characteristics similar to those of the real. However, due to the fact that their effectiveness as sole generators proved to be limited, in this chapter we propose a process that combines FARIMA models with the Lognormal distribution and produces synthetic traffic that approximates quite accurately the behavior of the real traffic. Finally, in Chapter 6 an attempt is made to solve the problem of classifying a network as scale-free or non scale-free. Nowadays networks are complex structures and graphically are represented by nodes, which are the entities of interest, and edges that form the relationships between them. Internet and every small private subnetwork that connects with it can be represented as such network with nodes the servers and edges their links. On the other hand the resilience of a network to various types of attacks can be judged also by its type. In particular, according to our experimental study scale-free networks appear to be resistant to random attacks but very vulnerable to targeted attacks. So a credible network classification process could be an important tool for their managers. In this dissertation it is proposed to transform each complex network into a time series. For this transformation, 3 specific metrics of the nodes are calculated, which then contribute to the definition of a final value for each node. Taking into account the connections between the nodes, we create a sequence of data which then treat as time series. With the help of parameters such as the Hurst and the maximum Lyapunov exponents for the time series, it is possible to characterize the network from which it originates as scale-free or non scale-free. The proposed transformation is applied to both simulated and real networks for which random and targeted attacks are also simulated in order to evaluate the classification of the networks.To summarize, in this dissertation new methods, which are mostly based on time series models, are proposed for the solution of problems related to internet traffic. Based on the experimental results presented in the dissertation we conclude that some of the proposed methods for solving these specific problems are much more effective and others are simply better than their alternatives.

Σκοπός της παρούσας διατριβής ήταν η μελέτη των χαρακτηριστικών της κίνησης στο διαδίκτυο και η ανάπτυξη κατάλληλων μοντέλων και τεχνικών για την αντιμετώπιση θεμάτων σχετικών με πρόβλεψη του φορτίου της κίνησης, τη δυναμική διάθεση εύρους ζώνης βασισμένη σε προβλέψεις και τη δημιουργία συνθετικής κίνησης που προσομοιάζει με πραγματική κίνηση βίντεο. Επιπλέον, μελετήθηκε η σύνδεση των δικτύων και της τοπολογίας τους με χρονοσειρές έτσι ώστε οι ιδιότητες των χρονοσειρών που προκύπτουν να μπορούν να χρησιμοποιηθούν για την κατηγοριοποίηση των δικτύων, μια διεργασία ιδιαίτερα σημαντική αφού τα δίκτυα είναι λιγότερο ή περισσότερο ανθεκτικά σε κακόβουλες επιθέσεις ανάλογα με τον τύπο τους. Η κίνηση στο διαδίκτυο όπως γνωρίζουμε δημιουργείται από τα διαφορετικά είδη πολυμέσων που είναι συνδεδεμένα σε αυτό και αφορά δεδομένα audio, video, εικόνες, Ethernet, LANs, WANs, κλπ. Για όλα αυτά τα διαφορετικά είδη κίνησης η μοντελοποίηση τους είναι απαραίτητη για την επίλυση των διαφορετικών προβλημάτων τους. Έτσι τα θέματα τα οποία πραγματεύεται η διατριβή παρουσιάζουν ενδιαφέρον τόσο από πλευράς στοχαστικής μοντελοποίησης όσο και από πλευράς τηλεπικοινωνιακής μηχανικής όπου η μοντελοποίηση της κίνησης είναι απαραίτητη για άλλες εργασίες όπως η διάθεση εύρους ζώνης και η δημιουργία συνθετικής κίνησης.Στο πρώτο κεφάλαιο της διατριβής παρουσιάζεται μια γενική επισκόπηση σχετικά με το διαδίκτυο που αφορά αφ' ενός την ιστορική αναδρομή της δημιουργίας του αφ' ετέρου την οργάνωσή του, τις μέχρι τώρα προσεγγίσεις μοντελοποίησής του, την κίνηση και την τοπολογία του. Στο δεύτερο κεφάλαιο μελετώνται τα βασικά χαρακτηριστικά του διαδικτύου, τόσο αναφορικά με τις κατανομές που παρουσιάζουν οι διάφορες μετρικές (στατικά χαρακτηριστικά) όσο και με τη δυναμική του στο χρόνο. Από πλευράς μοντέλων παρουσιάζονται εκείνα τα πρότυπα χρονοσειρών με τα οποία μπορεί να μοντελοποιηθεί η κίνηση στο διαδίκτυο και αποτελούν τη βάση των μεθοδολογιών που αναπτύσσονται αργότερα στα κεφάλαια 3, 4 και 5. Τέλος, παρουσιάζονται βασικές έννοιες και στοιχεία της επιστήμης δικτύων που είναι απαραίτητα τόσο για την κατανόηση των χαρακτηριστικών της τοπολογίας του διαδικτύου όσο και για την ανάπτυξη της μεθοδολογίας που προτείνεται στο κεφάλαιο 6 και αφορά τη κατηγοριοποίηση δικτύων σε ελεύθερης ή μη-ελεύθερης κλίμακας.Το πρώτο αντικείμενο μελέτης της διατριβής παρουσιάζεται στο κεφάλαιο 3 και είναι η πρόβλεψη της κίνησης στο διαδίκτυο. Η όσο το δυνατόν ακριβέστερη πρόβλεψή της είναι απαραίτητη για επίλυση θεμάτων όπως είναι η κατανομή πόρων ενός συστήματος και ο σχεδιασμός δικτύων. Έχοντας σαν βάση μοντέλα όπως το FARIMA, το GARCH και τα τεχνητά νευρωνικά δίκτυα, προτείνονται προβλεπτικά σχήματα μέσω των συνδυασμών τους, επίσης ένα σχήμα επιλογής μοντέλου που βασίζεται σε έλεγχο μη-γραμμικότητας καθώς και υβριδικά μοντέλα που συνδυάζουν κατασκευαστικά τα επιμέρους μοντέλα. Σχεδιάστηκε επίσης ένα σχήμα σύγκρισης των διαφορετικών μεθοδολογιών αναφορικά με την πρόβλεψη ώστε να προκύψει η καταλληλότερη. Στο κεφάλαιο 4 οι προβλεπτικές προσεγγίσεις που αναπτύχθηκαν προηγουμένως χρησιμοποιούνται για τη δυναμική διάθεση εύρους ζώνης σε ένα end-to-end δίκτυο, ένα πολύ σημαντικό πρόβλημα που εντάσσεται στη γενικότερη διαχείριση πόρων του δικτύου. Η διάθεση εύρους ζώνης γενικά μπορεί να υλοποιηθεί είτε στατικά, κάτι το οποίο δε λαμβάνει υπόψη διακυμάνσεις στη ζήτηση, είτε δυναμικά, οπότε η πρόβλεψη παίζει ουσιατικό ρόλο. Για τις ανάγκες αυτού του κεφαλαίου ορίστηκε μία διαδικασία επιλογής του κατάλληλου μοντέλου πρόβλεψης που να έχει την ικανότητα να είναι ακριβές στην πρόβλεψη, αλλά ταυτόχρονα να μπορεί να εφαρμοστεί με επιτυχία σε σχήματα διάθεσης εύρους ζώνης. Τα υποψήφια μοντέλα ήταν τα FARIMA και τα FARIMA/GARCH, τα υβριδικά μοντέλα FARIMA-MLP και FARIMA/GARCH-MLP καθώς και δύο στρατηγικές πρόβλεψης όπου η μία επιλέγει μοντέλο ανάλογα με το αποτέλεσμα του ελέγχου για μη-γραμμικότητα στη δομή εξάρτησης των δεδομένων και η άλλη συνδυάζει προβλέψεις από διαφορετικές μεθοδολογίες. Για τη διάθεση εύρους ζώνης προτείνονται τρία διαφορετικά δυναμικά σχήματα τα οποία και αξιολογούνται με τη βοήθεια μετρικών. Από τη σύγκρισή τους εντοπίζεται η καλύτερη μεθοδολογία πρόβλεψης και καταγράφονται σημαντικά συμπεράσματα σχετικά με τα προτεινόμενα σχήματα διάθεσης εύρους ζώνης. Το τρίτο αντικείμενο μελέτης βρίσκεται στο κεφάλαιο 5 και είναι η δημιουργία συνθετικής κίνησης μέσω μοντέλων χρονοσειρών. Η δυνατότητα προσομοίωσης της κίνησης στο διαδίκτυο μπορεί να συμβάλλει στην αποτελεσματικότερη διαχείριση των δικτύων και την ανάλυση απόδοσής τους. Λόγω του ότι η ανάλυση της απόδοσης δικτύων με πραγματική κίνηση μπορεί να έχει μεγάλο κόστος και οι μετρήσεις να είναι δύσκολες, τα μαθηματικά μοντέλα που μπορούν να χρησιμοποιηθούν για να δημιουργήσουν κίνηση είναι πολύ σημαντικά. Σε αυτό το πλαίσιο θεωρούνται μοντέλα χρονοσειρών FARIMA και FARIMA/GARCH προκειμένου να επιτύχουμε συνθετική κίνηση με χαρακτηριστικά παρόμοια με εκείνα της πραγματικής. Όμως λόγω του ότι η αποτελεσματικότητά τους αποδείχτηκε περιορισμένη, στο κεφάλαιο αυτό προτείνουμε μια διαδικασία η οποία συνδυάζει το FARIMA μοντέλο με τη λογαριθμοκανονική κατανομή και παράγει συνθετική κίνηση που προσεγγίζει με ικανοποιητική ακρίβεια τη συμπεριφορά της πραγματικής. Τέλος, στο κεφάλαιο 6 επιχειρείται η επίλυση του προβλήματος της κατηγοριοποίησης ενός δικτύου σε ελεύθερης κλίμακας ή μη ελεύθερης κλίμακας. Τα δίκτυα στη σημερινή εποχή αποτελούν πολύπλοκες δομές και παριστάνονται γραφικά με κόμβους, που αποτελούν τις οντότητες ενδιαφέροντος, και ακμές, που αποτελούν τις σχέσεις μεταξύ τους. Το διαδίκτυο αλλά και κάθε μικρότερο ιδιωτικό υποδίκτυο που το πλαισιώνει, είναι τέτοιο δίκτυο με κόμβους τους εξυπηρετητές και ακμές (σχέσεις) τις συνδέσεις τους. Η ανθεκτικότητα ενός δικτύου σε διαφόρων ειδών επιθέσεις όπως αποδεικνύεται, εξαρτάται και από τον τύπο του. Συγκεκριμένα, τα ελεύθερης κλίμακας δίκτυα δείχνουν να είναι ανθεκτικά στις τυχαίες επιθέσεις αλλά πολύ ευάλωτα σε στοχευμένες επιθέσεις. Έτσι μια αξιόπιστη διαδικασία κατηγοριοποίησης των δικτύων θα ήταν πολύ σημαντικό εργαλείο για τους διαχειριστές τους. Στην παρούσα διατριβή προτείνεται ο μετασχηματισμός κάθε πολύπλοκου δικτύου σε χρονοσειρά. Για το μετασχηματισμό αυτό υπολογίζονται 3 συγκεκριμένες μετρικές των κόμβων που στη συνέχεια συμβάλλουν στον ορισμό μιας τελικής τιμής για κάθε κόμβο. Λαμβάνοντας υπόψη τις συνδέσεις μεταξύ των κόμβων, στη συνέχεια δημιουργείται μια ακολουθία δεδομένων που της συμπεριφερόμαστε ως χρονοσειρά. Με τη βοήθεια παραμέτρων όπως η παράμετρος Hurst και ο μέγιστος εκθέτης Lyapunov για χρονοσειρές είναι δυνατόν να χαρακτηριστεί το δίκτυο από το οποίο προέρχεται. Ο μετασχηματισμός εφαρμόζεται τόσο σε προσομοιωμένα όσο και σε πραγματικά δίκτυα όπου προσομοιώνονται τυχαίες και στοχευμένες επιθέσεις με σκοπό την αξιολόγηση του χαρακτηρισμού.Συνοπτικά, στη διατριβή αυτή προτείνονται μέθοδοι επίλυσης προβλημάτων που αφορούν την κίνηση του διαδικτύου και οι οποίες έχουν τη βάση τους σε μοντέλα χρονοσειρών. Τα αποτελέσματα των πειραμάτων που παρουσιάζονται στη διατριβή οδηγούν στο συμπέρασμα ότι για την επίλυση αυτών των συγκεκριμένων προβλημάτων, κάποιες από τις προτεινόμενες μεθόδους είναι ιδιαίτερα αποτελεσματικές και άλλες είναι καλύτερες από τις εναλλακτικές τους.