Multicasting is a technique used for distributing data packets from one or more sources to a set of receivers on interconnected networks. Currently developing network applications bring specific quality of service (QoS) requirements like bounded delay, minimum bandwidth, and maximum data loss rate. Providing the required quality of service addresses routing and resource reservation concepts. In this study, a literature survey is carried out on traditional and QoS multicast routing protocols, and the need for QoS routing protocols is investigated. QoS multicast routing protocols are classified and compared according to their multicast tree construction and resource reservation approaches. Two QoS protocols, QROUTE and QMBF, are selected, and their performances are experimentally compared using the network simulation tool Network Simulator-2 (ns-2). The objective of the simulations is to compare the QoS routing algorithms and their tree construction efficiencies. The first contribution of the thesis is the survey and classification of traditional and QoS multicast routing protocols. Another contribution is the ns-2 implementation of two QoS multicast routing protocols. The final contribution of the thesis is the performance evaluation of the recent protocols from a different perspective.

Resource virtualization is emerging as a technology to enable the management and sharing of hardware resources including multiple core processors and accelerators such as Digital Signal Processors (DSP), Graphics Processing Units (GPU), and Field Programmable Gate Arrays (FPGA). Accelerators present unique problems for virtualization and sharing due to their specialized architectures and interaction modes. This thesis explores and proposes solutions for the virtualized operation of high performance, quality of service (QoS) packet scheduling accelerators. It specifically concentrates on challenges to meet 10Gbps Ethernet wire speeds. The packet scheduling accelerator is realized in a FPGA and implements the Sharestreams-V architecture. ShareStreams-V implements the Dynamic Window-Constrained Scheduler (DWCS) algorithm, and virtualizes the previous ShareStreams architecture. The original ShareStreams architecture, implemented on Xilinx Virtex-I and Virtex-II FPGAs, was able to schedule 128 streams at 10Gbps Ethernet throughput for 1500-byte packets. Sharestreams-V provides both hardware and software extensions to enable a single implementation to host isolated, independent virtual schedulers. Four methods for virtualization of the packet scheduler accelerator are presented: coarse- and fine-grained temporal partitioning, spatial partitioning, and dynamic spatial partitioning. In addition to increasing the utilization of the scheduler, the decision throughput of the physical scheduler can be increased when sharing the physical scheduler across multiple virtual schedulers among multiple processes. This leads to the hypothesis for this work: Virtualization of a quality of service packet scheduler accelerator through dynamic spatial partitioning is an effective and efficient approach to the accelerator virtualization supporting scalable decision throughput across multiple processes. ShareStreams-V was synthesized targeting a Xilinx Virtex-4 FPGA. While sharing among four processes, designs that supported up to 16, 32, and 64 total streams are able to reach 10Gbps Ethernet scheduling throughput for 64-byte packets. When sharing among 32 processes, a scheduler supporting 64 total streams was able to reach the same throughput. An access API presents the virtual scheduler abstraction to individual processes in order to allocate, deallocate, update and control virtual the scheduler allocated to a process. Practically, the bottleneck for the test system is the software to hardware interface. Effective future implementations are anticipated to use a tightly-coupled host CPU to accelerator interconnect.

In the past few years, we have witnessed the continuous growth in popularity of delay-sensitive applications. Applications like live video streaming, multimedia conferencing, VoIP and online gaming account for a major part of Internet traffic these days. It is also predicted that this trend will continue in the coming years. This emphasizes the significance of developing efficient scheduling algorithms in communication networks with guaranteed low delay performance. In our work, we try to address the delay issue in some major instances of wireless communication networks. First, we study a wireless content distribution network (CDN), in which the requests for the content may have service deadlines. Our wireless CDN consists of a media vault that hosts all the content in the system and a number of local servers (base stations), each having a cache for temporarily storing a subset of the content. There are two major questions associated with this framework: (i) content caching: which content should be loaded in each cache? and (ii) wireless network scheduling: how to appropriately schedule the transmissions from wireless servers? Using ideas from queuing theory, we develop provably optimal algorithms to jointly solve the caching and scheduling problems. Next, we focus on wireless relay networks. It is well accepted that network coding can enhance the performance of these networks by exploiting the broadcast nature of the wireless medium. This improvement is usually evaluated in terms of the number of required transmissions for delivering flow packets to their destinations. In this work, we study the effect of delay on the performance of network coding by characterizing a trade-off between latency and the performance gain achieved by employing network coding. More specifically, we associate a holding cost for delaying packets before delivery and a transmission cost for each broadcast transmission made by the relay node. Using a Markov decision process (MDP) argument, we prove a simple threshold-based policy is optimal in the sense of minimum long-run average cost. Finally, we analyze delay-sensitive applications in wireless peer-to-peer (P2P) networks. We consider a hybrid network which consists of (i) an expensive base station-to-peer (B2P) network with unicast transmissions, and (ii) a free broadcast P2P network. In such a framework, we study two popular applications: (a) a content distribution application with service deadlines, and (b) a multimedia live streaming application. In both problems, we utilize random linear network coding over finite fields to simplify the coordination of the transmissions. For these applications, we provide efficient algorithms to schedule the transmissions such that some quality of service (QoS) requirements are satisfied with the minimum cost of B2P usage. The algorithms are proven to be throughput optimal for sufficiently large field sizes and perform reasonably well for finite fields.

Providing service via theWeb differs from other service provision environments in that it is possible for the unexpected arrival of a massive number of service requests in a small time-frame, a situation commonly referred to as a flash crowd. Events of this nature are beyond the control of the service provider, and have the potential to severely degrade service quality and, in the worst case, to deny service to all clients completely. The occurrence, severity and sought Web content of a flash crowd is beyond the control of service provision software. How this software reacts to such a flash crowd, however, is not. Given the short-lived nature of flash crowds, it is unreasonable to expect such systems to increase the system resources they can apply to a particular flash crowd event. It is also difficult to predict the particular nature of any flash crowd, and subsequently which system resources will bottleneck. The driving hypothesis of this research is that, if we are to reasonably expect to have software react effectively to flash crowd events, we need to alter that software at runtime to remove system bottlenecks, whilst a flash crowd event is in progress. This is a special case of what is usually known as "unanticipated software evolution". This thesis reports on an investigation into how unanticipated software evolution can be applied to running Web service provision software to remove system bottlenecks. It does so by introducing automated dynamic Web content degradation to running software currently subject to simulated flash crowd events. The thesis describes and validates appropriate runtime extensions to allow generative object communication architectures (a promising class of architecture for unanticipated software evolution) to be converted initially into a Web application server, and then later accept further runtime behaviour changes. Such changes could alter system bottlenecks by replacing the key programming logic causing system bottlenecks at runtime.

This thesis presents three main contributions that aim to improve the transport layer of the current networking architecture. The transport layer is nowadays dominated by the use of TCP and its congestion control. Recently new congestion control mechanisms have been proposed. Among them, TCP Friendly Hate Control (TFRC) appears to be one of the most complete. Nevertheless this congestion control mechanism, as with TCP, does not take into account either the evolution of the network in terms of Quality of Service and mobility or the evolution of the applications. The first contribution of this thesis is a specialisation of TFRC congestion control to provide a QoS-aware Transport Protocol specifically designed to operate over QoS-enabled networks with bandwidth guarantee mechanisms. This protocol combines a QoS-aware congestion control, which takes into account network-level bandwidth reservations, with full ordered reliability mechanism to provide a transport service similar to TCP. As a result, we obtain the guaranteed throughput at the application level where TCP fails. This protocol is t he first transport protocol compliant with bandwidth guaranteed networks. At the same time the set of network services expands, new technologies have been proposed and deployed at the physical layer. These new technologies are mainly characterised by communications done without wire constraint and the mobility of the end-systems. Furthermore, these technologies are usually deployed on entities where the CPU power and memory storage are limited. The second contribution of this thesis is therefore to propose an adaptation of TFHC to these entities. This is accomplished with the proposition of a new sender-based version of TFHC. This version has been implemented, evaluated and its numerous contributions and advantages compare to usual TFHC version have been demonstrated. Finally, we proposed an optimisation of actual implementations of TFHC. This optimisation first consists in the proposition of an algorithm based on a numerical analysis of the equation used in TFHC and the use of the Newton's algorithm. We furthermore give a first step, with the introduction of a new framework for TFRC, in order to better understand TFHC behaviour and to optimise the computation of the packet loss rate according to loss probability distributions.

Αντικείμενο αυτής της διδακτορικής διατριβής είναι η μελέτη και η υλοποίηση ενός ολοκληρωμένου κατανεμημένου συστήματος διανομής δεδομένων σε πραγματικό χρόνο. Η ταχεία ανάπτυξη του Διαδικτύου και η πολυπλοκότητα των υπηρεσιών που προσφέρονται μέσα από αυτό έχει εξαντλήσει τα περιθώρια- όρια της κλασικής αρχιτεκτονικής του εξυπηρετητή και του πελάτη , καθώς, ο συνεχώς αυξανόμενος αριθμός χρηστών που ζητούν διάφορες υπηρεσίες δημιουργούν ένα τεράστιο φορτίο στους εξυπηρετητές, το οποίο δεν είναι σε θέση πια να ικανοποιήσουν. Η αρχιτεκτονική των διομότιμων συστημάτων αποτελεί σήμερα τον πιο υποσχόμενο αντικαταστάτη της αρχιτεκτονικής του εξυπηρετητή-πελάτη για την παροχή υπηρεσιών μέσω του Διαδικτύου. Η υπόθεση αυτή δικαιολογείται, αφού αξιοποιώντας τους πόρους των ίδιων των χρηστών, που αποτελούν πλέον ενεργό κομμάτι του συστήματος, η συγκεκριμένη αρχιτεκτονική μπορεί να εξασφαλίσει κλιμάκωση των συστημάτων αυτών σε αριθμό χρηστών αλλά και σε πόρους, του οποίους και αυτό-διαχειρίζονται για την παροχή οποιασδήποτε υπηρεσίας. Η ανάπτυξη, όμως, διομότιμων συστημάτων προϋποθέτει την επίλυση ενός συνόλου προβλημάτων που προκύπτουν από την κατανεμημένη φύση τους και την πολυπλοκότητα τους. Τα τελευταία χρόνια, η επιστημονική κοινότητα έχει ασχοληθεί εκτενώς με τα συστήματα αυτά και έχει προτείνει τρόπους επίλυσης των προβλημάτων που εμφανίζουν, οι οποίες όμως επικεντρώνονται σε συγκεκριμένες πτυχές τους, με αποτέλεσμα να μην προσφέρουν ακόμα δυνατότητες επαρκούς αξιοποίησης των πλεονεκτημάτων τους. Στην παρούσα διδακτορική διατριβή μελετήθηκαν η ανάπτυξη και η υλοποίηση ενός ολοκληρωμένου κατανεμημένου συστήματος διαμοιρασμού δεδομένων σε πραγματικό χρόνο. Το σύστημα αυτό αποτελείται από τρία διακριτά υποσυστήματα: 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.

Κύριος στόχος της διπλωματικής αυτής εργασίας είναι η διερεύνηση τεχνικών βελτίωσης της προσφερόμενης ποιότητας υπηρεσιών (QoS) σε ένα περιβάλλον συνλειτουργίας πολλαπλών HAPs. Στο περιβάλλον αυτό έχουμε διαφορετικούς τύπους χρηστών που μοιράζονται την περιοχή κάλυψης και το εύρος ζώνης. Παρουσιάζεται το θεωρητικό υπόβαθρο της μελέτης αυτής που περιλαμβάνει τη θεωρία τηλεπικοινωνιακής κίνησης. Αναπτύσσουμε ένα αναλυτικό μοντέλο ώστε να περιγράψουμε το περιβάλλον συνλειτουργίας στο οποίο έχουμε δύο κατηγορίες χρηστών. Η μία κατηγορία αποτελείται από χρήστες που έχουν πλήρη πρόσβαση στα HAPs, ενώ η άλλη κατηγορία αποτελείται από χρήστες με περιορισμένη πρόσβαση στα HAPs. Για να επιτύχουμε αυτή τη βελτίωση του QoS εφαρμόζουμε διάφορους μηχανισμούς περιορισμού. Σκοπός μας είναι να περιοριστεί η πρόσβαση στους πόρους του καναλιού για τους χρήστες με πλήρη πρόσβαση στα HAPs, ώστε να υπάρχει μεγαλύτερη πιθανότητα πρόσβασης για τους χρήστες με περιορισμένη πρόσβαση στα HAPs. Παρουσιάζονται και αναλύονται διάφοροι περιορισμοί με στόχο την εύρεση του καταλληλότερου για την επίτευξη μιας ισορροπημένης και χαμηλής πιθανότητας απόρριψης κλήσης. Αναλύεται, επίσης, και επεξηγείται η παρουσία φαινομένων παρεμβολής και πολυόδευσης στο σύστημά μας καθώς και η εξοικονόμηση συχνοτήτων. / The main objective of this thesis is to investigate techniques for improvement the Quality of Service (QoS) in an environment of multiple HAPs. In this environment there are different user types which share coverage area and radio spectrum. It is presented the theoretical background of this study that includes theory telecommunication traffic. We develop an analytical model to describe system behavior of a coexistence scenario containing two user groups, which have full and limited HAP availability. In order to achieve this improvement of QoS, operate different restrictions. Our aim is to limit access to channel resources to users with full access to HAPs, so that there is a greater probability of access for users with limited access to HAPs. Different types of restriction function are analyzed trying to find the most suitable for achieving a balanced low probability performance to both user groups simultaneously. It is also explained the presence of interference, small-scale fading and saving frequencies.

Depuis l'avènement du réseau Internet, le volume de données échangées sur les réseaux a crû de manière exponentielle. Le matériel présent sur les réseaux est devenu très hétérogène, dû entre autres à la multiplication des "middleboxes" (parefeux, routeurs NAT, serveurs VPN, proxy, etc.). Les algorithmes exécutés sur les équipements réseaux (routage, “spanning tree”, etc.) sont souvent complexes, parfois fermés et propriétaires et les interfaces de supervision peuvent être très différentes d'un constructeur/équipement à un autre. Ces différents facteurs rendent la compréhension et le fonctionnement du réseau complexe. Cela a motivé la définition d'un nouveau paradigme réseaux afin de simplifier la conception et la gestion des réseaux : le SDN (“Software-defined Networking”). Il introduit la notion de contrôleur, qui est un équipement qui a pour rôle de contrôler les équipements du plan de données. Le concept SDN sépare donc le plan de données chargés de l'acheminement des paquets, qui est opéré par des équipements nommés virtual switches dans la terminologie SDN, et le plan contrôle, en charge de toutes les décisions, et qui est donc effectué par le contrôleur SDN. Pour permettre au contrôleur de prendre ses décisions, il doit disposer d'une vue globale du réseau. En plus de la topologie et de la capacité des liens, des critères de performances comme le délai, le taux de pertes, la bande passante disponible, peuvent être pris en compte. Cette connaissance peut permettre par exemple un routage multi-classes, ou/et garantir des niveaux de qualité de service. Les contributions de cette thèse portent sur la proposition d'algorithmes permettant à une entité centralisée, et en particulier à un contrôleur dans un cadre SDN, d'obtenir des estimations fiables du délai de bout-en-bout pour les flux traversant le réseau. Les méthodes proposées sont passives, c'est-à-dire qu'elles ne génèrent aucun trafic supplémentaire. Nous nous intéressons tout particulièrement à la moyenne et l'écart type du délai. Il apparaît que le premier moment peut être obtenu assez facilement. Au contraire, la corrélation qui apparaît dans les temps d'attentes des noeuds du réseau rend l'estimation de l'écart type beaucoup plus complexe. Nous montrons que les méthodes développées sont capables de capturer les corrélations des délais dans les différents noeuds et d'offrir des estimations précises de l'écart type. Ces résultats sont validés par simulations où nous considérons un large éventail de scénarios permettant de valider nos algorithmes dans différents contextes d'utilisation / Since the early beginning of Internet, the amount of data exchanged over the networks has exponentially grown. The devices deployed on the networks are very heterogeneous, because of the growing presence of middleboxes (e.g., firewalls, NAT routers, VPN servers, proxy). The algorithms run on the networking devices (e.g., routing, spanning tree) are often complex, closed, and proprietary while the interfaces to access these devices typically vary from one manufacturer to the other. All these factors tend to hinder the understanding and the management of networks. Therefore a new paradigm has been introduced to ease the design and the management of networks, namely, the SDN (Software-defined Networking). In particular, SDN defines a new entity, the controller that is in charge of controlling the devices belonging to the data plane. Thus, in a SDN-network, the data plane, which is handled by networking devices called virtual switches, and the control plane, which takes the decisions and executed by the controller, are separated. In order to let the controller take its decisions, it must have a global view on the network. This includes the topology of the network and its links capacity, along with other possible performance metrics such delays, loss rates, and available bandwidths. This knowledge can enable a multi-class routing, or help guarantee levels of Quality of Service. The contributions of this thesis are new algorithms that allow a centralized entity, such as the controller in an SDN network, to accurately estimate the end-to-end delay for a given flow in its network. The proposed methods are passive in the sense that they do not require any additional traffic to be run. More precisely, we study the expectation and the standard deviation of the delay. We show how the first moment can be easily computed. On the other hand, estimating the standard deviation is much more complex because of the correlations existing between the different waiting times. We show that the proposed methods are able to capture these correlations between delays and thus providing accurate estimations of the standard deviation of the end-to-end delay. Simulations that cover a large range of possible scenariosvalidate these results

Redes sem fio devem prover qualidade de serviço para aplicações de voz, video e dados. Um padrão definido para oferecer qualidade de serviço nessas redes é o documento IEEE 802.16. Com o objetivo de melhorar a qualidade de transmissão, este padrão utiliza dois principais mecanismos físicos: (i) Orthogonal Frequency Division Multiple Access como interface física e (ii) a possibilidade de ajustar a robustez da transmissão em relação as imperfeições físicas que podem comprometer a transmissão. Além disso, o padrão define um conjunto de componentes na estação base, tal como alocadores, escalonadores e controles de admissões que devem ser modelados para prover uma arquitetura que garanta qualidade de serviço. Entretanto, o padrão não define nem os algoritmos de cada componente, nem a integração entre estes componentes. Investigações objetivando prover qualidade de serviço tem sido propostas no contexto de redes IEEE 802.16. A literatura sobre redes IEEE 802.16 móveis mostra que as atuais pesquisas estão focadas em soluções específicas para cada componente, ou em soluções com integrações parciais. O foco destas soluções é prover a melhor alternativa para problemas individuais para um componente particular. Entretanto, em todos os estudos realizadas nesta tese, não encontrou-se nenhuma pesquisa endereçando propostas sobre a qualidade de serviço global considerando a diversidade dos requisitos de tráfegos das aplicações e as condições de propagação do canal de rádio frequência. Neste contexto, essa tese propõe uma nova arquitetura para garantir qualidade de serviço em uma estão base que deve ser modelada usando uma infraestrutura entre camada para adaptar-se aos requisitos dinâmicos do tráfego, bem como as condições do canal de rádio frequência. O objetivo é integrar os componentes definidos pelo padrão com os mecanismos físicos. Outro objetivo é analisar a arquitetura proposta, através de uma metodologia de avaliação que é baseada segundo a especificação do sistema de avaliação do fórum Worldwide Interoperability for Microwave Access. Assim, a análise da nova arquitetura adaptativa entre camadas é realizada e os resultados mostram a eficiência na alocação dos dados, bem como o mínimo atraso e jitter gerado nas aplicações de tempo real. / Wireless networks must provide quality of service to voice, video and data applications. A standard defined to offer quality of service in these networks is the IEEE 802.16 document. In order to improve the quality of transmission, this standard uses two main physical mechanisms: (i) Orthogonal Frequency Division Multiple Access as physical interface and (ii) the possibility of adjusting the transmission robustness to face the physical impairments that may compromise the transmission. Moreover, the standard defines a set of components in the base station, such as allocators, schedulers, and connection admission controllers that must be modeled to provide an architecture that guarantees quality of service. However, the standard does not define either the algorithm running inside each one of the components nor the integration among them. Investigations aiming to provide quality of service have been proposed in the context of IEEE 802.16 networks. The literature on mobile IEEE 802.16 networks shows that the current research is focused on specific solutions for each component or in solutions with partial integration. The focus of those solutions is to provide the best alternative for individual problems of a particular component. However, to the best of our knowledge, no research addressing the overall quality of service architecture considering both the diversity of applications traffic requirements and the propagation conditions of the radio frequency channel has been proposed so far. In this context, this thesis proposes a new architecture to guarantee quality of service in the base station that must be modeled using a cross-layer infrastructure able to adapt to the dynamics of traffic requirements as well as to the radio frequency channel conditions. The aim is to integrate the components defined by the standard with the physical mechanisms. Another objective is to evaluate the proposed architecture, through an evaluation methodology that is defined following the specification of the system evaluation of the Worldwide Interoperability for Microwave Access forum. Therefore, the analysis on the new cross-layer adaptive architecture is performed and the results show efficient data allocation as well as a minimal delay and jitter for real-time applications.

[pt] Redes de comutação em pacotes vêm substituindo gradativamente as redes de comutação em circuitos, unificando assim, a forma como voz e dados são trafegados. Devido a esse novo conceito de redes comutadas por pacotes, novos desafios referentes ao surgimento de novas aplicações necessitando requisitos de qualidade cada vez mais estritos, vêm recentemente atraindo a atenção de pesquisadores da área de redes de computação. Entre os mecanismos existentes para determinar a qualidade de serviço oferecida por tais redes, o mecanismochave considerado, dos roteadores que desempenham tal função, é o escalonador de pacotes. O conceito que dita à operação de tais escalonadores é o conceito de disciplinas de serviço. No presente trabalho, é proposta uma nova disciplina de serviço onde os pacotes são escalonados de acordo com um indicador de desempenho que mede a satisfação dos usuários baseado no serviço recebido em relação ao serviço contratado. Esse indicador é trazido da economia e se chama Função Utilidade. O sistema considerado no trabalho leva em consideração o funcionamento do roteador de borda de uma provedora de serviços de telecomunicações onde os usuários requerem serviços de VoIP, FTP e HTTP. Os resultados de simulação do sistema mostram que o desempenho da disciplina proposta é comparável, sendo em alguns casos levemente insatisfatória, quando comparada a outras disciplinas existentes na literatura. A lista de trabalhos futuros sugere possibilidades de melhoria deste desempenho, mas que não foram testadas por falta de tempo. / [en] Packet-switched networks have recently replaced circuit-switched networks unifying the way voice and data are carried through those networks. Due to such a new switching concept, challenges related to new applications with different quality requirements have arisen and attracted much attention of computer network researchers. Among the mechanisms used to provide quality of service in those networks, the one chosen in this research is the router’s packet scheduler. The concept that governs packet schedulers is queuing scheduling discipline. In this research, a new queuing scheduling discipline is proposed where packets are scheduled based on a performance indicator that evaluates the user’s satisfaction with the service contracted. That performance indicator is a well-known economic function called utility function. The system considered on this research is focused on the operation of a telecommunications service provider network’s border router where users request FTP, VoIP and HTTP services. Simulation results show that the performance of the proposed service discipline is comparable, but not always to a satisfactory degree, when compared with other service disciplines found in the literature. Some suggestions for future research are added in this dissertation, in order to improve the performance of the proposed service discipline, but they have not been tested due to space and time limitations.