Peer-to-Peer (P2P) networks provide an alternative approach to distributed systems, relaxing the requirements for dedicated servers from the client-server model. A P2P network operates as an overlay at application layer, on top of the physical network. In the early years of P2P, most applications lacked mechanisms for enforcing a particular overlay topology. This resulted in inefficient communication schemes, such as flooding or the maintenance of large numbers of connections with other peers. However, researchers and practitioners have realized the importance of constructing and maintaining appropriate overlay topologies for efficient and robust P2P systems. P2P-based Voice over IP (VoIP) networks, such as Skype, distinguish client peers from super peers. This results in a two-level hierarchy: Peers with powerful CPU, more free memory and greater bandwidth take on server-like responsibilities and provide services to a set of client peers. But building and maintaining a super peer-based overlay topology is not easy. In particular, the uncontrollable and unpredictable behaviour of peers results in volatile overlay topologies. This makes it challenging to design reconfigurable and stable networks that provide good Quality of Service (QoS). Various solutions have been proposed. However, peer dynamics, scale and complexity make it hard and expensive to validate them by testing. Simulation can help to validate network designs and protocols, but most existing approaches cannot cope with unbounded dynamic change of network topology. We propose a new approach to the modelling and simulation of P2P network reconfigurations using graph transformation, a visual rule based formalism. Based on existing alternatives we classify network design variations by means of a feature tree. Focussing on P2P VoIP applications, we develop a structural model and transformation rules to compare alternative solutions to the problems of selection and connection to super peers, peer promotion, and load balancing, evaluating their QoS properties. We validate the model using statistics from the real Skype network and experimental data in the literature.

In today's world a tremendous amount of information is produced daily. The plethora of data represents a challenge in terms of how to manage, represent and share it, in a meaningful and effective way. This increasing size of on-line information and its weak structuring, suggests the need for principles to make information accessible through well defined operations on well-defined data. The mixture of P2P and semantic technologies could harvest the advantages of both mechanisms and address the challenges of on-line information management and sharing. P2P networks combined with semantic technologies promise to achieve distributed management and exchange of information in an efficient manner. On the one hand, P2P computing offers a more effective alternative to existing client-server applications by providing a radical way of decentralised information management and sharing. On the other hand, semantic-oriented technologies present new approaches in solving the problems of information complexity by adding meaning and structure to data, in order to facilitate better information management, indexing and retrieval. This thesis proposes a system for distributed information management and sharing in unstructured P2P networks through the utilisation of semantic information, extracted from the network resources. Its aim is to facilitate an efficient way of information exchange while keeping low messaging cost and normal load balancing among the peers of the network. In particular, the proposed architecture follows a two-layer approach where the upper layer forms the semantic knowledge of the network through super-peers, and the lower layer of peers represents the network resources. The network knowledge is formally represented by a domain specific ontology using collective intelligence techniques to extract knowledge from the available resources. This semantic-driven approach along with dynamic topological adaptations is facilitated by two key components: the Semantic•Driven Architecture (SOA) and Dynamic Adaptive Topology (DAT). SDA aims to improve query efficiency and achieves this by mapping the network ontology to the overlay topology creating in this way a semantic•driven architecture. During the resource discovery process the query is intelligently routed in the semantic layer via ontology supported decisions and attaining in this way better query success and reduced network traffic. DAT introduces dynamic topological optimisation on top of the SDA component having as objectives scalability and fault tolerance. Since DAT component is based on SDA model, topological adaptations follow a semant1c•driven approach for retaining the successful architecture of SDA. Scalability is achieved through load balancing mechanisms, where overloaded or under-loaded super-peers are optimised accordingly, and the overall semantic image of the network is retained up to date, through reconceptualisation procedures.

This thesis presents a fault-tolerant, Peer-to-Peer (P2P) based grid scheduling system for highly dynamic and highly heterogeneous environments, such as home networks, where we can find a variety of devices (laptops, pes, game consoles, etc.) and networks. The number of devices found in a house that are capable of processing data has been increasing in the last few years. However, being able to process data does not mean that these devices are powerful, and, in a home environment, there will be a demand for some applications that need significant computing resources, beyond the capabilities of a single domestic device, such as a set top box (examples of such applications are TV recommender systems, image processing and photo indexing systems). A computational grid is a possible solution for this problem, but the constrained environment in the home makes it difficult to use conventional grid scheduling technologies, which demand a powerful infrastructure. Our solution is based on the distribution of the matchmaking task among providers, leaving the final allocation decision to a central scheduler that can be running on a limited device without a big loss in performance.

This thesis argues that a more nuanced study of online media piracy is necessary in order to augment the dominant focus on piracy's relationship to copyright. Copyright as a frame for understanding piracy's relationship to capitalism has left potentially more crucial areas of study neglected. An approach to understanding the relationship of media piracy to anticapitalist projects must engage with forms of media piracy in their specificity and not as a homogeneous field. The thesis argues that it is possible and necessary to push beyond the constraints of copyright activism and intellectual property and in so doing opens up new areas of inquiry into online media piracy's potential to challenge logics of property and commodification. Original research is presented in the form of a highly detailed description and analysis of private BitTorrent filesharing sites. These sites are secretive and yet to receive scholarly attention in such a detailed and systematic way. This research finds both public and private variants of BitTorrent media piracy to be highly ambivalent with regards to their transformative potentials in relation to capital and thus tempers more extreme views of piracy as wholly revolutionary and emancipatory, and those that see pirate as a 'simple' form of theft. Public and private BitTorrent filesharing are theorised through the lens of Autonomist Marxism, a perspective that has a novel view of technology both as a tool of domination and a force for potential emancipation. Piracy is analysed for its capacity to refuse the valorisation of the enjoyment of music or film via the surveillance and tracking of audiences, which has become typical for contemporary legal online distribution venues. The thesis further analyses BitTorrent piracy's relationship to the 'common', the shared capacities for creating knowledge, ideas, affects. The thesis concludes that further scholarly research must move beyond concerns for creators' remuneration and its focus on reforming existing copyright policy and instead engage with the emergent institutional structures of organised media piracy. Though publicly accessible BitTorrent piracy has contributed to a broadening of awareness about issues of access to information, such an awareness often leaves in place logics of private property and capitalist accumulation. Finally, the thesis argues that the richness and complexity of private sites' organisational valences carry with them greater potential for radically destabilising capitalist social relations with regard to the distribution of cultural production.

Περιληπτικά, στη συγκεκριμένη διδακτορική διατριβή μελετήθηκαν οι θεωρίες της βελτιστοποίησης και των κατανεμημένων αλγορίθμων με σκοπό την χρήση τους σε ένα διομότιμο σύστημα σύγχρονου διαμοιρασμού αντικειμένων. Επιπλέον μελετήθηκε το περιβάλλον και οι συνθήκες λειτουργίας ενός τέτοιου συστήματος. καθώς και τα χαρακτηριστικά του. Αποτέλεσμα της μελέτης αυτής είναι η εξαγωγή συμπερασμάτων σχετικά με τις απαιτήσεις που πρέπει να πληρούνται κατά τη δημιουργία ενός διομότιμου συστήματος σύγχρονου διαμοιρασμού αντικειμένων και οι τεχνικοί στόχοι που πρέπει αυτό να ικανοποιεί. Με αυτά τα κριτήρια σχεδιάστηκε η αρχιτεκτονική του συστήματος και ορίστηκαν τα προβλήματα που πρέπει να επιλυθούν. Για την λειτουργία ενός τέτοιου συστήματος ορίστηκαν οι ακόλουθες απαιτήσεις: • Μεγιστοποίηση της χρήσης από το σύστημα του διαθέσιμου εύρους ζώνης των συμμετεχόντων κόμβων. Φυσικά, οι κόμβοι έχουν ετερογενείς τιμές του διαθέσιμου εύρους ζώνης και, μάλιστα, με μεγάλη διασπορά. • Ελαχιστοποίηση της καθυστέρησης από τη στιγμή δημιουργίας ενός αντικειμένου μέχρι τον διαμοιρασμό του σε κάθε συμμετέχοντα κόμβο. • Ομοιόμορφη διαρκής κατανομή του συνολικού εύρους ζώνης του συστήματος στους συμμετέχοντες κόμβους. • Ανεκτικότητα του συστήματος στη δυναμική συμπεριφορά των χρηστών που προκαλείται από εισόδους και εξόδους των χρηστών στο σύστημα σε μη προκαθορισμένες χρονικές στιγμές. • Ικανότητα κλιμάκωσης του συστήματος σε αριθμό συμμετεχόντων χρηστών κάτι που επάγει την κατανεμημένη διαχείριση του συστήματος. • Προσαρμογή του σχεδιαζόμενου συστήματος στην κίνηση του δικτύου στο οποίο αυτό επικάθεται και ανεκτικότητά του στις μεταβολές του εύρους ζώνης των συμμετεχόντων κόμβων. • Ελαχιστοποίηση του φορτίου το οποίο εισάγει η λειτουργία του συστήματος στο δίκτυο. Για τη λειτουργία του προτεινόμενου συστήματος απαιτείται η δημιουργία ενός γράφου διασύνδεσης. Ως γράφος διασύνδεσης ορίζεται ο γράφος που προκύπτει αν κάθε κόμβος συνδεθεί με ένα μικρό υποσύνολο των συμμετεχόντων κόμβων που ονομάζονται και γείτονες του κόμβου. Για την ικανοποίηση των προαναφερθεισών απαιτήσεων. μελετήθηκαν τα χαρακτηριστικά του γράφου διασύνδεσης και προέκυψε ότι κάθε κόμβος: α) πρέπει να έχει γείτονες με όσο το δυνατόν μικρότερη δικτυακή καθυστέρηση μεταξύ τους, β) πρέπει να έχει αριθμό εξερχόμενων συνδέσεων ανάλογο με το εύρος ζώνης του, γ) οι συνδέσεις αυτές πρέπει να κατανέμονται ομοιόμορφα στους συμμετέχοντες κόμβους για την ικανοποίηση των αναγκών όλων των κόμβων, δ) οι κόμβοι με σχετικά μεγάλο εύρος ζώνης πρέπει να ομαδοποιούνται στο γράφο με σκοπό την γρήγορη αρχικά διάχυση του αντικειμένου και ε) ο γράφος διασύνδεσης πρέπει να αναδιατάσσεται δυναμικά έτσι ώστε να διατηρεί τις ιδιότητες αυτές στο δυναμικό δικτυακό περιβάλλον που επικάθεται και για δυναμική συμπεριφορά των συμμετεχόντων κόμβων. Για την ικανοποίηση αυτών των τεχνικών στόχων αναπτύχθηκε μία δομή του γράφου που ικανοποιεί αυτά τα χαρακτηριστικά. Η βελτιστοποίηση του γράφου γίνεται μέσω αλγορίθμων κατά την λειτουργία των οποίων κάθε κόμβος επιλέγει περιοδικά ένα τυχαίο κόμβο ο οποίος είναι γείτονάς του στον γράφο διασύνδεσης. Μεταξύ των δύο αυτών κόμβων εκτελείται ανακατανομή των γειτόνων τους με σκοπό την εξισορρόπηση του αριθμού των γειτόνων που κάθε ένας από αυτούς διαθέτει. αλλά και την ελαχιστοποίηση της μέσης καθυστέρησης που έχουν αθροιστικά οι κόμβοι από τους γείτονές τους. Οι αλλαγές στον γράφο διασύνδεσης που προκύπτουν από κάθε εκτέλεση του αλγορίθμου αυτού μεταβάλλουν και τους γείτονες ενός υποσυνόλου κόμβων εκτός των δύο συμμετεχόντων στον αλγόριθμο εναλλαγής. Οι αλλαγές αυτές επιφέρουν άλλες αλλαγές με την σειρά τους και έτσι προκύπτει τελικά ένας γράφος διασύνδεσης όπου κάθε κόμβος έχει τον προκαθορισμένο αριθμό γειτόνων και. παράλληλα. ελαχιστοποιείται το άθροισμα των μέσων δικτυακών καθυστερήσεων που έχουν οι συμμετέχοντες κόμβοι με τους γείτονές τους. Για τον διαμοιρασμό του αντικειμένου ο δημιουργός του το τεμαχίζει σε τεμάχια (μπλοκ). Τα τεμάχια προωθούνται σε ένα πολύ μικρό σύνολο κόμβων και αποτελούν τις λογικές μονάδες δεδομένων που ανταλλάσσονται μεταξύ των κόμβων. Σκοπός είναι ο διαμοιρασμός του κάθε τεμαχίου σε κάθε κόμβο μέσα σε ένα προκαθορισμένο χρονικό διάστημα. Για την ανταλλαγή τεμαχίων μεταξύ των γειτόνων του γράφου διασύνδεσης του προς διαμοιρασμού αντικειμένου μεταξύ των συμμετεχόντων κόμβων αναπτύχθηκε ένας Κατανεμημένος Χρονοπρογραμματιστής Ανταλλαγής Τεμαχίων (ΚΧΑΤ). Τεχνικοί στόχοι της ανάπτυξης του ΚΧΑΜ αποτέλεσαν α) ο χρονισμός διαπραγμάτευσης αποστολής τεμαχίων μεταξύ κάθε αποστολέα και παραλήπτη, β) η γρήγορη διάδοση πρόσφατα παραγόμενων τεμαχίων και σπάνιων σε μία γειτονία του γράφου διασύνδεσης (τεμάχια που δημιουργήθηκαν μεταγενέστερα από άλλα ευνοούνται από το χρονοπρογραμματιστή αρχικά για την επιτυχή και γρήγορη διάδοσή τους σε μία κρίσιμη μάζα από κόμβους), γ) η τροφοδότηση όλων των κόμβων με ομοιόμορφο και σταθερό ρυθμό, δ) η προτεραιότητα σε κόμβους με μεγάλο εύρος ζώνης, ε) η αποφυγή μετάδοσης του ίδιου τεμαχίου από δύο αποστολείς προς τον ίδιο παραλήπτη και στ) η αποφυγή μιας κατάστασης όπου αποστολέας και παραλήπτης δεν έχουν τεμάχια προς ανταλλαγή. Ο χρονισμός του ΚΧΑΜ που αναπτύχθηκε αποτελείται από τρείς φάσεις. Στην πρώτη φάση που εκτελείται περιοδικά από κάθε αποστολέα εκδίδεται και αποστέλλεται στους πιθανούς παραλήπτες ένα σύνολο από «κουπόνια» μεγέθους ανάλογου με το εύρος ζώνης του αποστολέα. Στη δεύτερη φάση ο εκάστοτε παραλήπτης ζητά προκαταβολικά ένα τεμάχιο στην περίπτωση που επιλεγεί από τον αποστολέα για μετάδοση τεμαχίου. Στην τρίτη φάση ο αποστολέας επιλέγει τον παραλήπτη ακριβώς πριν την μετάδοση κάθε τεμαχίου και αποστέλλει το τεμάχιο που έχει ζητηθεί. Ο αλγόριθμος ο οποίος προτείνεται για τη δημιουργία κουπονιών έχει ως στόχο τη μεγιστοποίηση της χρήσης του εύρους ζώνης όλων των κόμβων και την ικανοποίηση των αναγκών κάθε συμμετέχοντα κόμβου. Είναι αυτός που, στην ουσία, καθορίζει τις ροές δεδομένων μεταξύ των γειτόνων του γράφου διασύνδεσης. Η χρησιμότητά του αναδεικνύεται σε περιπτώσεις όπου ο ρυθμός αναπαραγωγής του προς διαμοιρασμό αντικειμένου είναι παρόμοιος με το μέσο εύρος ζώνης του συστήματος. Οι απαιτήσεις του αλγορίθμου ζήτησης τεμαχίων μοντελοποιούνται μέσω της γραμμικής βελτιστοποίησης και διασφαλίζεται η γρήγορη και αποτελεσματική διάχυση των τεμαχίων ελαχιστοποιώντας την ύπαρξη ανενεργών πόρων. Τέλος, ο αλγόριθμος επιλογής γείτονα είναι αυτός που ρυθμίζει την ομοιόμορφη κατανομή του εύρους ζώνης στους συμμετέχοντες κόμβους, αλλά και δίνει προτεραιότητα στους κόμβους με μεγάλο εύρος ζώνης έτσι ώστε να επιτευχθεί ο γρήγορος διαμοιρασμός κάθε τεμαχίου και η ελαχιστοποίηση της καθυστέρησης του συστήματος. Η αξιολόγηση της προτεινόμενης αρχιτεκτονικής, της τοπολογίας του γράφου διασύνδεσης και του ΚΧΑΜ, έγινε μέσω προσομοίωσης σε προσομοιωτή δικτυακών συστημάτων. Μοντελοποιήθηκε το εύρος ζώνης των συμμετεχόντων κόμβων και δικτυακές καθυστερήσεις χρησιμοποιώντας πραγματικά δεδομένα από διομότιμα συστήματα.. Το σύστημα που αναπτύχθηκε μοντελοποιήθηκε πλήρως σε επίπεδο πακέτου. Εξετάστηκαν αρκετά σενάρια αξιολόγησης του συστήματος τα οποία, μεταξύ άλλων, περιλαμβάνουν, ευαισθησία του συστήματος σε παραμέτρους των προτεινόμενων αλγορίθμων, δυναμικά σενάρια όσον αφορά τη συμπεριφορά των χρηστών και του δικτύου και σενάρια εύρεσης των ορίων του προτεινόμενου συστήματος. Η αξιολόγηση των αποτελεσμάτων έδειξε ότι ικανοποιούνται οι απαιτήσεις που τέθηκαν για τη δημιουργία του συστήματος, καθώς και βελτίωση της συμπεριφοράς του συστήματος σε σχέση με αντίστοιχα συστήματα της διεθνούς βιβλιογραφίας με τα οποία συγκρίθηκε. / Peer-to-peer live streaming is a network application, where peers (users) contribute their upload bandwidth for the real time distribution of a video stream. The objective of this work is the optimization of this data diffusion with a distributed and self-organized architecture. Peers have heterogeneous and dynamic uploading bandwidth. This fact combined with the characteristics of the topology of the underlying network and the dynamic traffic conditions e.g. latency create a volatile and complex environment for P2P live streaming delivery, which strongly affect the success of a P2P system measured by a number of performance metrics. The first important factor is the uploading bandwidth utilization that corresponds to the ability of the system to exploit as much as possible of the overall uploading bandwidth of the participating peers. The maximization of the upload bandwidth utilization increases the video playback delivery rate and ensures the stability of the distribution. Equally important parameter is the setup time defined as the time interval between the generation of a block from an origin server and its delivery to every peer in the system. Furthermore, a P2P live streaming system has to remain stable and its delivery rate must remain high in a dynamic environment, where peers arrive and depart randomly. .Finally, fairness among nodes indicates the ability of the system to distribute continuously and uniformly the aggregate uploading bandwidth to the participating peers. This ensures that every peer will acquire a percentage of blocks above a critical threshold for an “affordable” video playback regardless the aggregate uploading bandwidth is not sufficient for the complete delivery of the video stream. For the development of the proposed system is required the creation of a content diffusion overlay (CDO). For every peer, CDO defines the graph which includes the subset of adjacent participating peers (neighbors) that are connected with it. For the fulfillment of the aforementioned requirements CDO must ensure the following features: • Each peer must have neighbors close to it in the underlying network. • The number of the neighbors has to be proportional to its upload bandwidth. • The number of the neighbors from which each peer receives data has to be balanced among participating peers. • In the CDO, peers with high upload bandwidth must be clustered for the fast diffusion of each video block to a critical mass of peers. • The CDO has to be adapted dynamically according to the underlying network conditions and the behavior of the participating peers. The optimization of the CDO and the fulfillment of these technical objectives is done with the use of a distributed optimization and maintenance algorithm (DOMA) that reorganizes the “neighborhoods” of CDO and so it keeps almost stable the attributes of the graph during peer arrivals and departures. It also ensures the high levels of bandwidth utilization. The algorithm based on a cost function, denoted as energy function between two nodes and can represent for example the network latency between two nodes. DOMA is executed between two neighbors that we note as initiators and their neighbors that we called satellites. Its purpose is to minimize the sum of the energy functions between initiators and satellites under the constraints on the number of neighbors that the graph structure implies. In p2p live streaming every user and/or content provider that generates a multimedia block stream is indicated as source. A P2P block exchange scheduling algorithm (P2P-BESA) ensures the distribution of each block to every user and with low latency. P2P-BESA focuses on the following properties: • The consistent message sequence between two peers for the negotiation of the transmission of a video block. • The fast diffusion of blocks that are recently produced. • The transmission of blocks to every peer with a stable and equal rate among the peers. • The prioritization of transmission to peers with relatively high upload bandwidth. • The avoidance of block retransmission. • The avoidance of content bottleneck between two peers. The decision for the transmission of a block is done in three phases. In the first phase, every peer acting as block sender issues tokens periodically proportional with its upload bandwidth. This ensures the maximization of the upload bandwidth of the participating peers and determines the data flows between participating peers. In the second phase, each peer periodically is acting as receiver and requests a different block from each one of its potential senders. As potential senders we define the set of peers that have recently sent a token to it. This algorithm ensures the fast and complete diffusion of every block by also minimizing the idle bandwidth resources in the systems. Finally in the third phase, before the transmission of each block each sender selects the destination peer according to the blocks that it misses and its upload bandwidth capabilities. The evaluation of the proposed system is done with a network simulator. A detailed packet level P2P live streaming simulator models the bandwidth of the participating peers, the network latency between them, peer arrivals and departures and finally dynamic changes in the underlying network. The evaluation of the system shows that: • It achieves very high levels of bandwidth utilization (around 95%) • low latency in the diffusion of its video block (2-4 seconds) • system is almost immune to peer arrivals and departures • very tolerant to underlying network changes Finally the proposed system outperforms when it is compared with other recently proposed systems in the international bibliography.

Αντικείμενο αυτής της διδακτορικής διατριβής είναι η μελέτη και η υλοποίηση ενός ολοκληρωμένου κατανεμημένου συστήματος διανομής δεδομένων σε πραγματικό χρόνο. Η ταχεία ανάπτυξη του Διαδικτύου και η πολυπλοκότητα των υπηρεσιών που προσφέρονται μέσα από αυτό έχει εξαντλήσει τα περιθώρια- όρια της κλασικής αρχιτεκτονικής του εξυπηρετητή και του πελάτη , καθώς, ο συνεχώς αυξανόμενος αριθμός χρηστών που ζητούν διάφορες υπηρεσίες δημιουργούν ένα τεράστιο φορτίο στους εξυπηρετητές, το οποίο δεν είναι σε θέση πια να ικανοποιήσουν. Η αρχιτεκτονική των διομότιμων συστημάτων αποτελεί σήμερα τον πιο υποσχόμενο αντικαταστάτη της αρχιτεκτονικής του εξυπηρετητή-πελάτη για την παροχή υπηρεσιών μέσω του Διαδικτύου. Η υπόθεση αυτή δικαιολογείται, αφού αξιοποιώντας τους πόρους των ίδιων των χρηστών, που αποτελούν πλέον ενεργό κομμάτι του συστήματος, η συγκεκριμένη αρχιτεκτονική μπορεί να εξασφαλίσει κλιμάκωση των συστημάτων αυτών σε αριθμό χρηστών αλλά και σε πόρους, του οποίους και αυτό-διαχειρίζονται για την παροχή οποιασδήποτε υπηρεσίας. Η ανάπτυξη, όμως, διομότιμων συστημάτων προϋποθέτει την επίλυση ενός συνόλου προβλημάτων που προκύπτουν από την κατανεμημένη φύση τους και την πολυπλοκότητα τους. Τα τελευταία χρόνια, η επιστημονική κοινότητα έχει ασχοληθεί εκτενώς με τα συστήματα αυτά και έχει προτείνει τρόπους επίλυσης των προβλημάτων που εμφανίζουν, οι οποίες όμως επικεντρώνονται σε συγκεκριμένες πτυχές τους, με αποτέλεσμα να μην προσφέρουν ακόμα δυνατότητες επαρκούς αξιοποίησης των πλεονεκτημάτων τους. Στην παρούσα διδακτορική διατριβή μελετήθηκαν η ανάπτυξη και η υλοποίηση ενός ολοκληρωμένου κατανεμημένου συστήματος διαμοιρασμού δεδομένων σε πραγματικό χρόνο. Το σύστημα αυτό αποτελείται από τρία διακριτά υποσυστήματα: 1. Ένα διομότιμο σύστημα για το διαμοιρασμό δεδομένων σε πραγματικό χρόνο. Το υποσύστημα αυτό αποτελείται από το γράφο διασύνδεσης των κόμβων που το συγκροτούν και το χρονοπρογραμματιστή που εκτελείται σε κάθε κόμβο. 2. Ένα σύστημα υποστήριξης, το οποίο είναι υπεύθυνο για την παρακολούθηση της λειτουργίας του υποσυστήματος διαμοιρασμού και την παροχή επιπλέον εύρους ζώνης, στην περίπτωση που δεν επαρκούν οι πόροι του πρώτου. 3. Ένα διομότιμο σύστημα για την αποθήκευση και την εύρεση των αντικειμένων που είναι διαθέσιμα προς διανομή μέσω του πρώτου υποσυστήματος. Για την ανάπτυξη του πρώτου υποσυστήματος, αρχικά διερευνήθηκε η φύση της εφαρμογής και ορίστηκαν τα επιθυμητά χαρακτηριστικά. Αυτά είναι ο μικρός χρόνος στησίματος, η ανοχή του σε δυναμικά φαινόμενα, όπως είναι η δυναμική συμπεριφορά των χρηστών και του φυσικού δικτύου, η ικανότητα κλιμάκωσης ως προς τον αριθμό των κόμβων και η ικανότητα για διαμοιρασμό δεδομένων με το μεγαλύτερο δυνατό ρυθμό υπό τον περιορισμό του μέσου εύρους ζώνης των κόμβων που αποτελούν το σύστημα. Στη συνέχεια ακολούθησε η μοντελοποίηση της λειτουργίας των συστημάτων κατανεμημένου διαμοιρασμού μέσα από την οποία προέκυψε η κατάλληλη αρχιτεκτονική ενός τέτοιου συστήματος που εγγυάται τη βέλτιστη εκπλήρωση των παραπάνω χαρακτηριστικών. Η προσφορά της παρούσας διατριβής στην έρευνα του επιστημονικού πεδίου των διομότιμων συστημάτων διαμοιρασμού δεδομένων σε πραγματικό χρόνο συνοψίζεται στα παρακάτω σημεία/συμπεράσματα : • Αντίθετα με τη μέχρι τώρα πρακτική που εφαρμόζεται στα συστήματα κατανεμημένου διαμοιρασμού, είναι αναγκαία η παράλληλη ανάπτυξη του γράφου διασύνδεσης και του χρονοπρογραμματιστή έτσι ώστε να μπορεί το κάθε υποσύστημα να χρησιμοποιήσει με βέλτιστο τρόπο τα χαρακτηριστικά του άλλου. • Ο γράφος διασύνδεσης πρέπει να αντικατοπτρίζει τη θέση των κόμβων στο φυσικό υποδίκτυο και να μπορεί να αυτό-οργανώνεται στις δυναμικές αλλαγές του δικτύου ή του πληθυσμού των κόμβων. • Η λειτουργία του χρονοπρογραμματιστή γίνεται πιο αποτελεσματική όταν διαχωρίζεται σε τρεις διαφορετικούς μηχανισμούς. Στο μηχανισμό δημιουργίας κουπονιών, στο μηχανισμό προ-ενεργής αίτησης πακέτου και στο μηχανισμό απόφασης επόμενου κόμβου προς αποστολή πακέτου. Τέλος, υλοποιήθηκαν κατανεμημένοι αλγόριθμοι για τη δημιουργία και την αυτό-οργάνωση του γράφου διασύνδεσης καθώς και οι απαραίτητοι αλγόριθμοι για την υλοποίηση του χρονοπρογραμματιστή. Οι αλγόριθμοι αυτοί σχεδιάστηκαν με τέτοιο τρόπο έτσι ώστε να χρησιμοποιούν ένα ελάχιστο ποσοστό του εύρους ζώνης των κόμβων χωρίς να συμβιβάζουν την αποτελεσματικότητα και την ταχύτητα σύγκλισής τους. Το δεύτερο ζήτημα που μελετήθηκε είναι η βοηθητική χρήση εξυπηρετητών με στόχο την αδιάλειπτη διάθεση απαραίτητων δικτυακών πόρων (εύρος ζώνης) που απαιτούνται από το σύστημα για τον πλήρη και συνεχή διαμοιρασμό του αντικειμένου. Αναλυτικότερα, ο σύγχρονος διαμοιρασμός βίντεο μέσω διομότιμων συστημάτων απαιτεί τη συνεχή ύπαρξη μέσου εύρους ζώνης συμμετεχόντων κόμβων μεγαλύτερο από το ρυθμό αναπαραγωγής του αντικειμένου που διαμοιράζεται. Αντιθέτως, λόγω της δυναμικής συμπεριφοράς των χρηστών και του απρόβλεπτου μέσου όρου εύρους ζώνης που διατίθεται από τους κόμβους οδηγούμαστε συχνά στη μη ομαλή λειτουργία του συστήματος ή/και στο διαμοιρασμό ενός αντικειμένου με μικρό ρυθμό αναπαραγωγής. Η επίλυση αυτού του προβλήματος απαιτεί την εξασφάλιση του ακριβούς και σε πραγματικό χρόνο υπολογισμού των διαθέσιμων πόρων του συστήματος. Επιπλέον, προϋποθέτει το σχεδιασμό μιας αρχιτεκτονικής που είναι κλιμακούμενη, δηλαδή επιτρέπει την παρακολούθηση συστημάτων στα οποία συμμετέχει πολύ μεγάλος αριθμός χρηστών. Παράλληλα, το προτεινόμενο σύστημα παρακολούθησης και ελέγχου του εύρους ζώνης πρέπει να εισάγει στο σύστημα όσο το δυνατόν μικρότερη κατανάλωση πόρων. Ομοίως, το εύρος ζώνης που συνεισφέρουν οι εξυπηρετητές πρέπει να ελαχιστοποιείται με στόχο την ελαχιστοποίηση του κόστους λειτουργίας. Τέλος, οι συνδέσεις που δημιουργούνται μεταξύ εξυπηρετητών και κόμβων πρέπει να εισάγουν με τη σειρά τους ελάχιστο φορτίο στο δίκτυο του προτεινόμενου συστήματος. Εκμεταλλευόμενοι, λοιπόν, τις ιδιότητες του χρονοπρογραμματιστή που αναπτύχθηκε είμαστε σε θέση μετρώντας ένα μικρό μόνο υποσύνολο κόμβων να εκτιμήσουμε γρήγορα και με ακρίβεια το συνολικό διαθέσιμο εύρος ζώνης του συστήματος. Επιπλέον, μετρώντας κάποιες παραμέτρους του χρονοπρογραμματιστή ανταλλαγής μπλοκ εκτιμούμε δυναμικά το φορτίο που αυτός εισάγει για διαμοιρασμό ανάλογα με τις επικρατούσες συνθήκες. Ο αριθμός των κόμβων αυτών είναι αρκετά μικρός και ανεξάρτητος από τον αριθμό των συμμετεχόντων κόμβων καθιστώντας το προτεινόμενο σύστημα ικανό για εξαιρετική κλιμάκωση. Με τις μετρήσεις αυτές γίνεται εφικτός ο υπολογισμός του εύρους ζώνης που απαιτείται από τους εξυπηρετητές για την ομαλή λειτουργία του συστήματος διαμοιρασμού. Τέλος, με τη βοήθεια ενός δυναμικά προσαρμόσιμου στο δίκτυο γράφου διασύνδεσης επιτυγχάνεται η μέγιστη εκμετάλλευση του εύρους ζώνης που συνεισφέρουν οι εξυπηρετητές και ο διαμοιρασμός του σε κόμβους με τη μικρότερη δυνατή δικτυακή καθυστέρηση. Το προτεινόμενο σύστημα αξιολογήθηκε σε κάθε είδους κατάσταση όπως: αυξομειούμενο μέσο εύρος ζώνης, γρήγορες μεταβολές στο μέσο εύρος ζώνης, μέσο εύρος ζώνης μεγαλύτερο και μικρότερο από το ρυθμό αναπαραγωγής. Η αξιολόγηση απέδειξε ότι ο πλήρης διαμοιρασμός του αντικειμένου, η ελαχιστοποίηση του εύρους ζώνης που συνεισφέρουν οι εξυπηρετητές μέσω της ακριβούς εκτίμησης των διαθέσιμων πόρων και η δυνατότητα εκτίμησης μέσω ενός μικρού υποσυνόλου συμμετεχόντων κόμβων είναι εφικτά κάτω από οποιεσδήποτε συνθήκες. Ο τρίτος στόχος που επιδιώξαμε να εκπληρώσουμε είναι η δημιουργία ενός κατανεμημένου συστήματος αποθήκευσης δεδομένων. Αυτό το σύστημα βασίστηκε στους Κατανεμημένους Πίνακες Κατακερματισμού (ΚΠΚ). Σκοπός αυτού του συστήματος είναι η δημιουργία ενός κατανεμημένου αποθηκευτικού χώρου, αποτελούμενου από πόρους των συμμετεχόντων κόμβων, για την αποθήκευση και ανάκτηση δεδομένων που πρόκειται να διαμοιραστούν. Οι απαιτήσεις ενός τέτοιου συστήματος περιλαμβάνουν την γρήγορη αναζήτηση δεδομένων, τη χρησιμοποίηση του μικρότερου δυνατού ποσοστού εύρος ζώνης για τη δρομολόγηση των αναζητήσεων, τη δυνατότητα εκτέλεσης σύνθετων αναζητήσεων και τη συμμέτοχη των κόμβων στο σύστημα ανάλογα με τους διαθέσιμους πόρους τους. Οι παραπάνω απαιτήσεις είναι αδύνατον να ικανοποιηθούν από έναν μόνο γράφο διασύνδεσης, καθώς προϋποθέτουν ετερόκλητα χαρακτηριστικά από το γράφο. Προκειμένου να είναι εφικτή η γρήγορη δρομολόγηση ο γράφος πρέπει να αντανακλά τη θέση των κόμβων στο φυσικό δίκτυο συνεπώς η εισαγωγή των κόμβων στον γράφο πρέπει επίσης να βασίζεται σε αυτό το χαρακτηριστικό. Η δυνατότητα για σύνθετες αναζητήσεις και η συμμετοχή των κόμβων ανάλογα με τους διαθέσιμους πόρους τους προϋποθέτει την μη ομοιόμορφη κατανομή των δεδομένων στο γράφο καθώς και επίσης και την εισαγωγή των κόμβων σε αυτόν ανάλογα με τους πόρους τους και τα δεδομένα που επιθυμούν να αποθηκεύσουν στο δίκτυο. Στα πλαίσια αυτής της διδακτορικής διατριβής προτείνεται ένα σύστημα κατανεμημένης αποθήκευσης το οποίο αποτελείται από δύο συνδεόμενους γράφους διασύνδεσης και μπορεί να ικανοποιήσει τις απαιτήσεις που έχουν τεθεί. Αυτοί οι δύο γράφοι είναι: • Ο γράφος διασύνδεσης και δρομολόγησης ο οποίος είναι υπεύθυνος για τη δρομολόγηση των αιτήσεων αναζήτησης. Οι κόμβοι εισέρχονται σε αυτόν ανάλογα με τη θέση τους στο φυσικό δίκτυο. Η παραπάνω συνθήκη συντελεί στην ταχύτατη δρομολόγηση των αιτήσεων αναζήτησης και τη χρησιμοποίηση ελάχιστου εύρους ζώνης για την εκτέλεσή τους. Για τη δημιουργία αυτού του γράφου αναπτύχτηκαν/σχεδιάστηκαν δύο κατανεμημένοι αλγόριθμοι. Ο πρώτος είναι υπεύθυνος για την εισαγωγή ενός κόμβου στο γράφο ανάλογα με τη θέση του στο φυσικό δίκτυο. Ο δεύτερος είναι υπεύθυνος για τη βελτιστοποίηση και προσαρμοστικότητα του γράφου στις δυναμικές αλλαγές των ιδιοτήτων του φυσικού δικτύου ή του πληθυσμού των συμμετεχόντων κόμβων. • Ο γράφος αποθήκευσης δεδομένων. Αυτός ο γράφος είναι υπεύθυνος για την αποθήκευση των δεδομένων στους κόμβους του συστήματος με τέτοιο τρόπο ώστε να είναι δυνατή η σύνθετη αναζήτησή τους καθώς επίσης και η αποθήκευσή τους ανάλογα με τους διαθέσιμους πόρους κάθε κόμβου. Η αξιολόγηση του συστήματος αυτού απέδειξε ότι ο διαχωρισμός της διαδικασίας δρομολόγησης από τη διαδικασία αποθήκευσης δεδομένων με την δημιουργία δύο ξεχωριστών γράφων διασύνδεσης εξασφαλίζει την εκπλήρωση όλων των απαιτήσεων ενός τέτοιου συστήματος. / The subject of this phd thesis is the study and development of a complete distributed system for real time data distribution. The rapid growth of the Internet and the complexity of the provided services, renders the investigation for a new architectural paradigm necessary, since classic server-client architecture has reached its full potential. The main reason for the above is that the continuously increasing number of users demanding a diversity of services generates an enormous overhead on the servers, that can’t be dealt with efficiently. Today, Peer-to-Peer architecture is considered to be the most promising replacement for client-server architecture for providing such services via the Internet. This assumption can be easily justified since, taking advantage of users resources, who now become active members of the system, peer-to-peer architecture can guarantee the scalability of these systems in respect to the number of participating users as well as the amount of data that they can manage. The development, however, of peer-to-peer systems requires the clarification of a set of problems which stem from their distributed nature and their complexity. In recent years, scientific community has been focusing on these systems suggesting a number of solutions, which, however, deal with certain only aspects of them, thus are unable to provide a holistic approach that could benefit from their numerous advantages. The complete distributed system for the real time distribution of data developed in the current dissertation thesis consists of three discrete subsystems: • a peer-to-peer live streaming system. This subsystem consists of an overlay, for the interconnection of peers, and a scheduler, which runs in every peer. • a supporting system, responsible for the monitoring of live streaming system and the supply of extra bandwidth in cases when peers’ aggregated resources are insufficient to sustain the streaming process • a peer-to-peer system for the storage and query of objects available for streaming, aided by the first subsystem described above. For the development of the first subsystem initially we investigated the nature of the application and defined the required characteristics. Those are the small setup time values, the tolerance of the system in dynamic conditions, like the dynamic behavior of the participating users and the dynamic conditions of the underlying network, the increased scalability concerning the number of supported users, and the ability to support streaming rates as high as possible having as constrain the aggregated upload bandwidth of the participating peers. The contribution of the present dissertation in the research of the scientific field of P2P real time data distribution systems is summarized below: 1. in contrast to contemporary practices regarding distributed live streaming systems the parallel development of the overlay and scheduler are necessary in order for the systems to be able to benefit from each other characteristics 2. the overlay should reflect the locations of the peers in the underlying network and be able to self-organize in response to dynamic changes of the peer population and the network conditions 3. the performance of the scheduler is enhanced when it comprises of three different mechanisms: the token generation algorithm, the mechanism of pro-active block request and the mechanism for selecting the next peer for packet transmitting. At last, distributed algorithms for the realization and self-organization of the overlay along with the necessary algorithms for the actualization of the scheduler were developed. These algorithms were designed in a way that allows for the usage of a small percentage of the nodes’ upload capacities without compromising the efficiency and the speed of their convergence A second subject that was studied was the use of supporting servers for the continuous provision of the required resources (upload bandwidth) for the complete and uninterrupted delivery of a stream. In more detail, peer-to-peer live streaming requires the constant presence of aggregated upload bandwidth greater than the rate of the stream being delivered. In contrast, the dynamic behavior of peers and the unpredictable upload bandwidth of nodes and of the conditions of the underlying network, often result in the disturbance of the streaming process and/or the delivery of a stream with low rate. Solving the above problems requires precise and real time monitoring of participating peers’ resources. Moreover, it assumes the development of an architecture which is scalable, allowing for the monitoring of systems with large peers number. Additionally, the proposed monitoring and bandwidth control system should introduce as little overhead as possible to the system, meaning that the amount of bandwidth used by the servers should be the minimum required to support peer-to-peer streaming system. Finally, connections established between servers and nodes should introduce, in their turn, the least possible overhead. Benefitting from the properties of our proposed peer-to-peer live streaming system’s scheduler we manage, by monitoring a small subset of participating peers, to measure with accuracy and in real time the aggregated upload bandwidth of the total participating peers. In addition, by measuring some parameters of the scheduler of bloc exchange we can dynamically estimate the overhead introduced for the distribution depending on the present conditions. The number of nodes is quite small and independent of the number of participant nodes allowing for the exceptional scalability of the proposed system. Because of these measurements the approximation of the bandwidth necessary for the successful performance of the distribution system becomes feasible. The evaluation process proved that the complete distribution of data, the minimization of the available servers bandwidth through the precise estimation of the available resources as well as the potential for estimation of a small subset of participating nodes are possible under any given circumstances. The third goal we tried to achieve is the development of a distributed data storage system. This system is based on DHTs. It aims to create a distributed storage space that consists of resources belonging to participating nodes, for the storage and retrieval of data about to be distributed. The prerequisites of such a system include: - fast routing process - usage of the smallest possible percentage of bandwidth for the querying process - the potential for execution of complex queries and - the participation of nodes in the system depending on their available recourses The above prerequisites can not be met by one only overlay, since they require diverse characteristics/ from the overlay. In order to achieve fast queries the overlay should reflect the location of all nodes in the physical network, therefore the introduction of nodes in the overlay should also rely on the above feature. The potential for complex queries and the participation of nodes depending on their available resources assumes a non-uniform node distribution in the overlay as well as the introduction of nodes in the system depending on their resources and the data needed to be stored in the network. In this work we propose a system for distributed storage that comprises of two interconnected overlays and can achieve all the demands set. The two overlays are described below: - LCAN is responsible for the routing process. Nodes enter this overlay in terms of their location on the physical network. The condition above leads to the fast routing of queries and the usage of the least possible bandwidth for their execution. In order to design this overlay the development of two distributed algorithms was necessary. The first one performs the introduction of nodes in the overlay according to their location in the network. The second distributed algorithm is responsible for the optimization and the adjustability of the overlay to the dynamic changes of the physical network properties or the participating nodes population. - VCAN. This is responsible for the storage of data in the nodes of the system in a way their storage according to each node’s available resources becomes feasible, while complex queries can be performed. The evaluation of the system has proved that the separation of the routing process from the data storage process with the creation of two separate overlays can result in the successful achievement of all prerequisites set by a distributed data storage system.

Depuis quelques années, il y a un réel changement dans les usages des réseaux en termes d'applications véhiculées ainsi que dans leur nombre. On voit apparaître de plus en plus d'applications contraintes en termes de délai, comme par exemple la téléphonie sur IP, ainsi que d'applications gourmandes en ressources comme par exemple le Srteaming Video. La croissance en volume de ces applications copmmence à poser des problèmes de congestion dasn les réseaux filiares et sans fil. Les opérateurs réseaux doivent être capables d'absorber ces changements de trafic, de faire face à cette demande de plus en plus intensive en bande passante et de fournir une bonne qualité (QoS) aux applications. Cela nécessite des mécanismes intellignets en termes d'ordonnancement et de gestion des files d'attente, de contrôle d'admission, de contrôle de débit et/ou de routage. L'objectif initial de cette thèse étati d'aboutir à la conception d'une nouvelle architecture de traitement et de gestion du trafic et de la qualité de service pour le contrôle d'admission. Plus précisément nous présentons une nouvelle solution pour le contrôle d'admission qui repose sur l'élaboration en continu d'un plan de connaissance et sur la modélisatio automatique du comportement d'un lien réseau par une file d'attente monoserveur. Norte solution doit permettre d'offrir une garantie probabiliste d'un paramètre de performance QoS qui peut être le délai d'attente moyen des paquets dans le buffer du lien ou le taux de perte. Nous avons évalué les performances de notre nouveau contro^le d'admission par simulation en considérant diverses conditions possibles de trafic. Lers résultats obtenus indiquent que la solution proposée permet d'atteindre un contrôle d'admission ni trop conservateur, ni trop permissif. En outre, notre solution offre l'avantage de se baser uniquement sur une connaisssance acquise au cours du temps et permet ainsi de s'affranchir d'un paramétrage compliqué des paramètres comme c'est le cas pour les solutions classiques de contrôle d'admission / Over the las few years, new ussages such as streaming or live video watching are increasingly representing a significant part of Internet traffic. Network operators face the challenge of satisfying the quality of experience expected by end-users while, in the same time, avoiding the over-provisioning of transmission links. Bandwidth management offers a wide spectrum of policies to overcome this issue. Possible options include congestion control, scheduling algorithms, traffic shaping and admission control. The initial objective of this thesis was to design of a new architecture of traffic management and quality of service for admission control. More precisely, we introduce a novel data-driven method based on a time-varying model that we refer to as Knowledge-Based Admission Control solutions (KBAC). Our KBAC solution consists of three main stages : (i) collect leasurments on the on-going traffic over the communication link ; (ii) maintain an up-to-date broad view of the link behavior, and feed it to a Knowledge Plane ; (iii) model the observed link behavior by a mono-server queue whose parameters are set auutomatically and which predicts the expected QoS if a flow requesting admission were to be accepted. our KBAC solution provides a probalistic guarantee whose admission thresold is either expressed, as a bounded dealy or as a bounded loss rate. We run extensive siçmulations using various traffic conditions to assess the behavior of our KBAC solution in the case of a delay thresold. The results show that our KBAC solution leads to a good trade-off between flow performance and resource utilization. This ability stems from the quick and autoamtic adjustment of its admission policy according to the actual variations on the traffic conditions. On the other hand, our KBAC solution avoids the critical step of precisely calibrating key parameters.

Στο πλαίσιο της διδακτορικής διατριβής αυτής προσπαθήσαμε να δώσουμε λύση στο κεντρικό πρόβλημα του σχεδιασμού και της υλοποίησης κατανεμημένων αρχιτεκτονικών συστήματος, πρωτοκόλλων και αλγορίθμων που παρέχουν την αναγκαία υποδομή για τον υπολογισμό ορισμένων βασικών καθολικών ιδιοτήτων και μεταβλητών της κατάστασης ενός Δικτύου Ομοτίμων Εταίρων (ΔΟΕ). Μπορούμε να διακρίνουμε δύο κύριες διαστάσεις καθολικών ιδιοτήτων: (α) ιδιότητες που αναφέρονται στους κόμβους του δικτύου και τα ιδιαίτερα χαρακτηριστικά τους (υπολογιστική ισχύ, συμπεριφορά, κτλ.) και (β) ιδιότητες και μεταβλητές των αντικειμένων/δεδομένων που χειρίζεται το ΔΟΕ. Για το σκοπό αυτό, κινηθήκαμε προς δύο αλληλοσυμπληρούμενες κατευθύνσεις: (α) ποσοτικοποίηση και εκμετάλλευση της ετερογένειας των κόμβων ενός ΔΟΕ, και (β) υπολογισμός εκτιμήσεων καθολικών μεταβλητών του συστήματος, με απώτερο στόχο την υποστήριξη επεξεργασίας πολύπλοκων ερωτημάτων σε συστήματα διαχείρισης δεδομένων Διαδικτυακής κλίμακας. Στο πρώτο μέρος της διατριβής αυτής, ασχοληθήκαμε με το πρόβλημα της ετερογένειας στις υπολογιστικές δυνατότητες και στις συμπεριφορές των κόμβων ενός ΔΟΕ, καθ'οδόν προς ένα πιό αποδοτικό και ανθεκτικό περιβάλλον δρομολόγησης μηνυμάτων και επεξεργασίας ερωτημάτων, σε σχέση με τα κλασσικά υπάρχοντα δομημένα δικτυακά υποστρώματα ΔΟΕ Κατανεμημένων Πινάκων Κατακερματισμού. Έτσι, πρώτα παρουσιάζουμε ένα νέο παράδειγμα αρχιτεκτονικής δόμησης των ΔΟΕ, το οποίο ονομάζουμε AESOP. Ακόμα, ασχολούμαστε με το πρόβλημα της αποδοτικής επεξεργασίας ερωτημάτων εύρους σε ΔΟΕ βασισμένα σε DHT. Η καινοτομία της προτεινόμενης προσέγγισης βρίσκεται σε αρχιτεκτονικές, αλγορίθμους και πρωτόκολλα ταυτοποίησης και κατάλληλης εκμετάλλευσης δυνατών κόμβων του δικτύων αυτών. Στο δεύτερο μέρος της διατριβής αυτής, ασχολούμστε με την κατανεμημένη εκτίμηση καθολικών μεταβλητών συστημάτων ΔΟΕ, όπως ο πληθάριθμος κατανεμημένων πολυσυνόλων, η επεξεργασία καθολικών συναθροιστικών ερωτημάτων και η διατήρηση ιστογραμμάτων επί δεδομένων κατανεμημένων σε όλους του κόμβους του ΔΟΕ, ώστε να επιτρέψουμε την μεταφορά τεχνικών βελτιστοποίησης ερωτημάτων από τα κεντρικοποιημένα περιβάλλοντα στον ευρέος κατανεμημένο χώρο των συστημάτων διαχείρισης δεδομένων Διαδικτυακής κλίμακας. / As part of this doctoral thesis we tried to solve the central problem of the design and implementation of distributed system architectures, protocols and algorithms that provide the infrastructure necessary to calculate some basic global properties and variables of a peer-to-peer network. We can distinguish two main dimensions of such properties: (a) properties pertaining to the nodes of the network and their particular characteristics (computing power, behavior, etc.) and (b) properties of objects and variables/data managed by the P2P network. For this purpose, we moved in two complementary directions: (a) quantification and exploitation of heterogeneity of nodes in P2P networks, and (b) calculation of estimates of global variables, with a view to support complex query processing in Internet-scale data management systems. First, we dealt with the problem of heterogeneity in computing capabilities and behaviour patterns of the nodes in a P2P network, en route to a more efficient and fault resilient routing and query processing infrastructure compared to classic structure DHT-based data networks. So, first we present a new architecture paradigm, called AESOP. We then use this architecture to tackle the problem of efficient range query processing in DHT-based data management systems. The innovation of the proposed approach lies in architectures, algorithms and protocols for identification and proper exploitation of the powerful nodes of these networks. Then we deal with the distributed estimation of global system variables in P2P networks, such as the cardinality of distributed multisets, distributed aggregate query processing, and the maintenance of distributed histograms over data stored across all nodes of the P2P overlay, so as to allow the porting of query processing and optimization techniques from centralized environments to the widely distributed field of Internet-scale data management systems.

Face à la prolifération des technologies mobiles et à l’augmentation du volume des données utilisées par les applications mobiles, les périphériques consomment de plus en plus de bande passante. Dans cette thèse, nous nous concentrons sur les réseaux Wi-Fi denses comme cela peut être le cas lors d’événements à grande échelle (ex: conférences, séminaire, etc.) où un serveur doit acheminer des données à un grand nombre de périphériques dans une fenêtre temporelle réduite. Dans ce contexte, la consommation de bande passante et les interférences engendrées par les téléchargements parallèles d’une donnée volumineuse par plusieurs périphériques connectés au même réseau dégradent les performances. Les technologies de communication Device-to-Device (D2D) comme Bluetooth ou Wi-Fi Direct permettent de mieux exploiter les ressources du réseau et d’améliorer les performances pour offrir une meilleure qualité d’expérience (QoE) aux utilisateurs. Dans cette thèse nous proposons deux approches pour l’amélioration des performances de la dissémination de données. La première approche, plus adaptée à une configuration mobile, consiste à utiliser des connexions D2D en point-à-point sur une topologie plate pour les échanges de données. Nos évaluations montrent que notre approche permet de réduire les temps de dissémination jusqu’à 60% par rapport à l’utilisation du Wi-Fi seul. De plus, nous veillons à avoir une répartition équitable de la charge énergétique sur les périphériques afin de préserver les batteries les plus faibles du réseau. Nous avons pu voir qu’avec la prise en compte de l’autonomie des batteries et de la bande passante, la sollicitation des batteries les plus faibles peut être réduite de manière conséquente. La deuxième approche, plus adaptée à des configurations statiques, consiste à mettre en place des topologies hiérarchiques dans lesquelles on regroupe les périphériques par clusters. Dans chaque cluster, un périphérique est élu pour être le relais des données qu’il recevra depuis le serveur et qu’il transmettra à ses voisins. Cette approche permet de gérer plus efficacement les interférences en adaptant la puissance du signal afin de limiter la portée des clusters. Dans ce cas, nous avons observé jusqu’à 30 % de gains en temps de dissémination. Dans la continuité des travaux de cette thèse, nous discutons de plusieurs perspectives qu’il serait intéressant d’entreprendre par la suite, notamment l’adaptation automatique du protocole de dissémination à l’état du réseau et l’utilisation simultanée des deux types de topologie plate et hiérarchique. / We are witnessing a proliferation of mobile technologies and an increasing volume of data used by mobile applications. Devices consume thus more and more bandwidth. In this thesis, we focus on dense Wi-Fi networks during large-scale events (such as conferences). In this context, the bandwidth consumption and the interferences caused by the parallel downloads of a large volume of data by several mobile devices that are connected to the same Wi-Fi network degrade the performance of the dissemination. Device-to-Device (D2D) communication technologies such as Bluetooth or Wi-Fi Direct can be used in order to improve network performance to deliver better QoE to users. In this thesis we propose two approaches for improving the performance of data dissemination. The first approach, more suited to a dynamic configuration, is to use point-to-point D2D connections on a flat topology for data exchange. Our evaluations show that our approach can reduce dissemination times by up to 60% compared to using Wi-Fi alone. In addition, we ensure a fair distribution of the energy load on the devices to preserve the weakest batteries in the network. We have observed that by taking into account the battery life and the bandwidth of mobile devices, the solicitation of the weakest batteries can be reduced significantly. The second approach, more adapted to static configurations, consists in setting up hierarchical topologies by gathering mobile devices in small clusters. In each cluster, a device is chosen to relay the data that it receives from the server and forwards it to its neighbors. This approach helps to manage interference more efficiently by adjusting the signal strength in order to limit cluster reach. In this case, we observed up to 30% gains in dissemination time. In the continuity of this thesis work, we discuss three perspectives which would be interesting to be undertaken, in particular the automatic adaptation of the dissemination to the state of the network and the simultaneous use of both topology types, flat and hierarchical.

Τα κατανεμημένα δίκτυα κλίμακας Ίντερνετ και κυρίως τα δίκτυα ομοτίμων εταίρων, γνωστά και ως peer-to-peer (p2p), που αποτελούν το πιο αντιπροσωπευτικό παράδειγμά τους, προσελκύουν τα τελευταία χρόνια μεγάλο ενδιαφέρον από τους ερευνητές και τις επιχειρήσεις λόγω των ιδιόμορφων χαρακτηριστικών τους, όπως ο πλήρης αποκεντρωτικός χαρακτήρας, η αυτονομία των κόμβων, η ικανότητα κλιμάκωσης, κ.λπ. Αρχικά σχεδιασμένα να υποστηρίζουν εφαρμογές διαμοιρασμού αρχείων με βασική υπηρεσία την επεξεργασία απλών ερωτημάτων, σύντομα εξελίχτηκαν σε ένα καινούργιο μοντέλο κατανεμημένων συστημάτων, με μεγάλες και αυξανόμενες δυνατότητες για διαδικτυακές εφαρμογές, υποστηρίζοντας πολύπλοκες εφαρμογές διαμοιρασμού δομημένων και σημασιολογικά προσδιορισμένων δεδομένων. Η προσέγγισή μας στην περιοχή αυτή γίνεται προς δύο βασικές κατευθύνσεις: (α) την επεξεργασία πολύπλοκων ερωτημάτων και (β) την εκτίμηση των ανομοιομορφιών των διαφόρων κατανομών που συναντάμε στα δίκτυα αυτά (π.χ. φορτίου, προσφοράς ή κατανάλωσης ενός πόρου, τιμών των δεδομένων των κόμβων, κ.λπ.), που εκτός των άλλων αποτελεί ένα σημαντικό εργαλείο στην υποστήριξη πολύπλοκων ερωτημάτων. Συγκεκριμένα, ασχολούμαστε και επιλύουμε τρία βασικά ανοικτά προβλήματα. Το πρώτο ανοικτό πρόβλημα είναι η επεξεργασία ερωτημάτων εύρους τιμών σε ομότιμα συστήματα κατανεμημένου πίνακα κατακερματισμού, με ταυτόχρονη εξασφάλιση της εξισορρόπησης του φορτίου των κόμβων και της ανοχής σε σφάλματα. Προτείνουμε μια αρχιτεκτονική επικάλυψης, που ονομάζουμε Saturn, που εφαρμόζεται πάνω από ένα δίκτυο κατανεμημένου πίνακα κατακερματισμού. Η αρχιτεκτονική Saturn χρησιμοποιεί: (α) μια πρωτότυπη συνάρτηση κατακερματισμού που τοποθετεί διαδοχικές τιμές δεδομένων σε γειτονικούς κόμβους, για την αποδοτική επεξεργασία των ερωτημάτων εύρους τιμών και (β) την αντιγραφή, για την εξασφάλιση της εξισορρόπησης του φορτίου προσπελάσεων (κάθετη, καθοδηγούμενη από το φορτίο αντιγραφή) και της ανοχής σε σφάλματα (οριζόντια αντιγραφή). Μέσα από μια εκτεταμένη πειραματική αξιολόγηση του Saturn και σύγκριση με δύο βασικά δίκτυα κατανεμημένου πίνακα κατακερματισμού (Chord και OP-Chord) πιστοποιούμε την ανωτερότητα του Saturn να αντιμετωπίζει και τα τρία ζητήματα που θέσαμε, αλλά και την ικανότητά του να συντονίζει το βαθμό αντιγραφής ώστε να ανταλλάζει ανάμεσα στο κόστος αντιγραφής και στο βαθμό εξισορρόπησης του φορτίου. Το δεύτερο ανοικτό πρόβλημα που αντιμετωπίζουμε αφορά την έλλειψη κατάλληλων μετρικών που να εκφράζουν τις ανομοιομορφίες των διαφόρων κατανομών (όπως, για παράδειγμα, το βαθμό δικαιοσύνης μιας κατανομής φορτίου) σε κατανεμημένα δίκτυα κλίμακας Ίντερνετ και την μη αποτελεσματική ή δυναμική εκμετάλλευση μετρικών ανομοιομορφίας σε συνδυασμό με αλγορίθμους διόρθωσης (όπως ο αλγόριθμος εξισορρόπησης φορτίου). Το πρόβλημα είναι σημαντικό γιατί η εκτίμηση των κατανομών συντελεί στην ικανότητα κλιμάκωσης και στην επίδοση αυτών των δικτύων. Αρχικά, προτείνουμε τρεις μετρικές ανομοιομορφίας (το συντελεστή του Gini, τον δείκτη δικαιοσύνης και το συντελεστή διασποράς) μετά από μια αναλυτική αξιολόγηση μεταξύ γνωστών μετρικών εκτίμησης ανομοιομορφίας και στη συνέχεια, αναπτύσσουμε τεχνικές δειγματοληψίας (τρεις γνωστές τεχνικές και τρεις προτεινόμενες) για τη δυναμική εκτίμηση αυτών των μετρικών. Με εκτεταμένα πειράματα αξιολογούμε συγκριτικά τους προτεινόμενους αλγορίθμους εκτίμησης και τις τρεις μετρικές και επιδεικνύουμε πώς αυτές οι μετρικές και ειδικά, ο συντελεστής του Gini, μπορούν να χρησιμοποιηθούν εύκολα και δυναμικά από υψηλότερου επιπέδου αλγορίθμους, οι οποίοι μπορούν τώρα να ξέρουν πότε να επέμβουν για να διορθώσουν τις άδικες κατανομές. Το τρίτο και τελευταίο ανοικτό πρόβλημα αφορά την εκτίμηση του μεγέθους αυτοσύνδεσης μιας σχέσης όπου οι πλειάδες της είναι κατανεμημένες σε κόμβους δεδομένων που αποτελούν ένα ομότιμο δίκτυο επικάλυψης. Το μέγεθος αυτοσύνδεσης έχει χρησιμοποιηθεί εκτεταμένα σε συγκεντρωτικές βάσεις δεδομένων για τη βελτιστοποίηση ερωτημάτων και υποστηρίζουμε ότι μπορεί να χρησιμοποιηθεί και σε ένα πλήθος άλλων εφαρμογών, ειδικά στα ομότιμα δίκτυα (π.χ. συσταδοποίηση του Ιστού, αναζήτηση στον Ιστό, κ.λπ.). Η συνεισφορά μας περιλαμβάνει, αρχικά, τις προσαρμογές πέντε γνωστών συγκεντρωτικών τεχνικών εκτίμησης του μεγέθους αυτοσύνδεσης (συγκεκριμένα, σειριακή, ετεροδειγματοληπτική, προσαρμοστική και διεστιακή δειγματοληψία και δειγματοληψία με μέτρηση δείγματος) στο περιβάλλον ομοτίμων εταίρων και η ανάπτυξη μια πρωτότυπης τεχνικής εκτίμησης του μεγέθους αυτοσύνδεσης, βασισμένη στο συντελεστή του Gini. Με μαθηματική ανάλυση δείχνουμε ότι οι εκτιμήσεις του συντελεστή του Gini μπορούν να οδηγήσουν σε εκτιμήσεις των υποκείμενων κατανομών δεδομένων, όταν αυτά ακολουθούν το νόμο της δύναμης ή το νόμο του Zipf και αυτές, με τη σειρά τους, σε εκτιμήσεις του μεγέθους αυτοσύνδεσης των σχέσεων των δεδομένων. Μετά από αναλυτική πειραματική μελέτη και σύγκριση όλων των παραπάνω τεχνικών αποδεικνύουμε ότι η καινούργια τεχνική που προτείνουμε είναι πολύ αποτελεσματική ως προς την ακρίβεια, την πιστότητα και την απόδοση έναντι των άλλων πέντε μεθόδων. / The distributed, Internet-scale networks, and mainly, the peer-to-peer networks (p2p), that constitute their most representative example, recently attract a great interest from the researchers and the industry, due to their outstanding properties, such as full decentralization, autonomy of nodes, scalability, etc. Initially designed to support file sharing applications with simple lookup operations, they soon developed in a new model of distributed systems, with many and increasing possibilities for Internet applications, supporting complex applications of structured and semantically rich data. Our research to the area has two basic points of view: (a) complex query processing and (b) estimation of skewness in various distributions existing in these networks (e.g. load distribution, distribution of offer, or consumption of resources, data value distributions, etc), which, among others, it is an important tool to complex query processing support. Specifically, we deal with and solve three basic open problems. The first open problem is range query processing in p2p systems based on distributed hash tables (DHT), with simultaneous guarantees of access load balancing and fault tolerance. We propose an overlay DHT architecture, coined Saturn. Saturn uses a novel order-preserving hash function that places consecutive data values in successive nodes to provide efficient range query processing, and replication to guarantee access load balancing (vertical, load-driven replication) and fault tolerance (horizontal replication). With extensive experimentation, we evaluate and compare Saturn with two basic DHT networks (Chord and OP - Chord), and certify its superiority to cope with the three above requirements, but also its ability to tune the degree of replication to trade off replication costs for access load balancing. The second open problem that we face concerns the lack of appropriate metrics to express the degree of skewness of various distributions (for example, the fairness degree of load balancing) in p2p networks, and the inefficient and offline-only exploitation of metrics of skewness, which does not enable any cooperation with corrective algorithms (for example, load balancing algorithms). The problem is important because estimation of distribution fairness contributes to system scalability and efficiency. First, after a comprehensive study and evaluation of popular metrics of skewness, we propose three of them (the coefficient of Gini, the fairness index, and the coefficient of variation), and, then, we develop sampling techniques (three already known techniques, and three novel ones) to dynamically estimate these metrics. With extensive experimentation, which comparatively evaluates both the various proposed estimation algorithms and the three metrics we propose, we show how these three metrics, and especially, the coefficient of Gini, can be easily utilized online by higher-level algorithms, which can now know when to best intervene to correct unfairness. The third and last open problem concerns self-join size estimation of a relation whose tuples are distributed over data nodes which comprise an overlay network. Self-join size has been extensively used in centralized databases for query optimization purposes, and we support that it can also be used in various other applications, specifically in p2p networks (e.g. web clustering, web searching, etc). Our contribution first includes the adaptations of five well-known self-join size estimation, centralized techniques (specifically, sequential sampling, cross-sampling, adaptive and bifocal sampling, and sample-count) to the p2p environment and a novel estimation technique which is based on the Gini coefficient. With mathematical analysis we show that, the estimates of the Gini coefficient can lead to estimates of the degree of skewness of the underlying data distribution, when these follow the power, or Zipf’s law, and these estimates can lead to self-join size estimates of those data relations. With extensive experimental study and comparison of all above techniques, we prove that the proposed technique is very efficient in terms of accuracy, precision, and cost of estimation against the other five methods.