Στατικοί και δυναμικοί γραφοθεωρητικοί αλγόριθμοι με εφαρμογές στη διαχείριση της υποδομής και του περιεχομένου των σύγχρονων δικτύων

Abstract

This thesis focuses on content networks, which are modelled with the help of graph theory and for which various algorithms are studied concerning the infrastructure and the content replication. In terms of the infrastructure the fundamental problem of maintaining a directed minimum cost spanning tree is studied, when the underlying graph changes through insertions or deletions of edges. In terms of content replication two different approaches are studied. The first concerns centralized replication of content by an external authority so as the total access cost over all users is minimized. For the case of constant number of users, optimal algorithms are designed. These algorithms constitute the first attempt to cope with non-metric topologies. The second approaches is based on the fact that participants are autonomous and behave selfishly. By defining an appropriate non-cooperative strategic game, existence of pure Nash equilibria is studied and tight bound on the prices of anarchy and stability are provided.

Η παρούσα διατριβή εστιάζει στα δίκτυα περιεχομένου. Τα δίκτυα αυτά μοντελοποιούνται με τη βοήθεια της θεωρίας γράφων και μελετώνται αλγόριθμοι που αφορούν στην διανομή περιεχομένου στους κόμβους τους και στην υποδομή τους. Σε σχέση με την υποδομή των δικτύων περιεχομένου, μελετάται το πρόβλημα της συντήρησης του δένδρου επικάλυψης ελαχίστου κόστους σε κατεθυνόμενους γράφους οι οποίοι υπόκεινται σε εισαγωγές και διαγραφές ακμών. H διανομή περιεχομένου μελετάται υπό δύο διαφορετικές οπτικές. Η πρώτη προϋποθέτει την ύπαρξη μιας εξωτερικής οντότητας, η οποία αποφασίζει σε ποιους κόμβους θα τοποθετηθούν ποια δεδομένα, με στόχο την ελαχιστοποίηση του συνολικού κόστους πρόσβασης από όλους τους αιτούντες. Εστιάζοντας σε δίκτυα όπου το πλήθος των κόμβων είναι σταθερό, προτείνονται βέλτιστοι αλγόριθμοι οι οποίοι αποφασίζουν τοποθετήσεις, ώστε το συνολικό κόστος πρόσβασης να είναι ελάχιστο. Οι αλγόριθμοι αυτοί συνιστούν την πρώτη ερευνητική προσπάθεια σε δίκτυα στα οποία οι τοπολογίες δεν είναι κατά ανάγκη μετρικές. Η δεύτερη οπτική βασίζεται στην υπόθεση ότι οι χρήστες δρουν ιδιοτελώς και αυτόνομα. Ορίζοντας ένα κατάλληλο μη συνεργατικό στρατηγικό παίγνιο, μελετάται η ύπαρξη απλών ισορροπιών Nash για διαφορετικές τοπολογίες ενώ παρέχονται σφικτά φράγματα για την τιμή της αναρχίας και την τιμή της ευστάθειας