This dissertation presents algorithms for data structures called distributed hash tables (DHT) or structured overlay networks, which are used to build scalable self-managing distributed systems. The provided algorithms guarantee lookup consistency in the presence of dynamism: they guarantee consistent lookup results in the presence of nodes joining and leaving. Similarly, the algorithms guarantee that routing never fails while nodes join and leave. Previous algorithms for lookup consistency either suffer from starvation, do not work in the presence of failures, or lack proof of correctness. Several group communication algorithms for structured overlay networks are presented. We provide an overlay broadcast algorithm, which unlike previous algorithms avoids redundant messages, reaching all nodes in O(log n) time, while using O(n) messages, where n is the number of nodes in the system. The broadcast algorithm is used to build overlay multicast. We introduce bulk operation, which enables a node to efficiently make multiple lookups or send a message to all nodes in a specified set of identifiers. The algorithm ensures that all specified nodes are reached in O(log n) time, sending maximum O(log n) messages per node, regardless of the input size of the bulk operation. Moreover, the algorithm avoids sending redundant messages. Previous approaches required multiple lookups, which consume more messages and can render the initiator a bottleneck. Our algorithms are used in DHT-based storage systems, where nodes can do thousands of lookups to fetch large files. We use the bulk operation algorithm to construct a pseudo-reliable broadcast algorithm. Bulk operations can also be used to implement efficient range queries. Finally, we describe a novel way to place replicas in a DHT, called symmetric replication, that enables parallel recursive lookups. Parallel lookups are known to reduce latencies. However, costly iterative lookups have previously been used to do parallel lookups. Moreover, joins or leaves only require exchanging O(1) messages, while other schemes require at least log(f) messages for a replication degree of f. The algorithms have been implemented in a middleware called the Distributed k-ary System (DKS), which is briefly described. / QC 20100824

The main contributions of this thesis are located in the domain of wireless sensor netorks. More in detail, we introduce energyaware algorithms and protocols in the context of the following topics: self-synchronized duty-cycling in networks with energy harvesting capabilities, distributed graph coloring and minimum energy broadcasting with realistic antennas. In the following, we review the research conducted in each case. We propose a self-synchronized duty-cycling mechanism for sensor networks. This mechanism is based on the working and resting phases of natural ant colonies, which show self-synchronized activity phases. The main goal of duty-cycling methods is to save energy by efficiently alternating between different states. In the case at hand, we considered two different states: the sleep state, where communications are not possible and energy consumption is low; and the active state, where communication result in a higher energy consumption. In order to test the model, we conducted an extensive experimentation with synchronous simulations on mobile networks and static networks, and also considering asynchronous networks. Later, we extended this work by assuming a broader point of view and including a comprehensive study of the parameters. In addition, thanks to a collaboration with the Technical University of Braunschweig, we were able to test our algorithm in the real sensor network simulator Shawn (http://shawn.sf.net). The second part of this thesis is devoted to the desynchronization of wireless sensor nodes and its application to the distributed graph coloring problem. In particular, our research is inspired by the calling behavior of Japanese tree frogs, whose males use their calls to attract females. Interestingly, as female frogs are only able to correctly localize the male frogs when their calls are not too close in time, groups of males that are located nearby each other desynchronize their calls. Based on a model of this behavior from the literature, we propose a novel algorithm with applications to the field of sensor networks. More in detail, we analyzed the ability of the algorithm to desynchronize neighboring nodes. Furthermore, we considered extensions of the original model, hereby improving its desynchronization capabilities.To illustrate the potential benefits of desynchronized networks, we then focused on distributed graph coloring. Later, we analyzed the algorithm more extensively and show its performance on a larger set of benchmark instances. The classical minimum energy broadcast (MEB) problem in wireless ad hoc networks, which is well-studied in the scientific literature, considers an antenna model that allows the adjustment of the transmission power to any desired real value from zero up to the maximum transmission power level. However, when specifically considering sensor networks, a look at the currently available hardware shows that this antenna model is not very realistic. In this work we re-formulate the MEB problem for an antenna model that is realistic for sensor networks. In this antenna model transmission power levels are chosen from a finite set of possible ones. A further contribution concerns the adaptation of an ant colony optimization algorithm --currently being the state of the art for the classical MEB problem-- to the more realistic problem version, the so-called minimum energy broadcast problem with realistic antennas (MEBRA). The obtained results show that the advantage of ant colony optimization over classical heuristics even grows when the number of possible transmission power levels decreases. Finally we build a distributed version of the algorithm, which also compares quite favorably against centralized heuristics from the literature. / Las principles contribuciones de esta tesis se encuentran en el domino de las redes de sensores inalámbricas. Más en detalle, introducimos algoritmos y protocolos que intentan minimizar el consumo energético para los siguientes problemas: gestión autosincronizada de encendido y apagado de sensores con capacidad para obtener energía del ambiente, coloreado de grafos distribuido y broadcasting de consumo mínimo en entornos con antenas reales. En primer lugar, proponemos un sistema capaz de autosincronizar los ciclos de encendido y apagado de los nodos de una red de sensores. El mecanismo está basado en las fases de trabajo y reposo de las colonias de hormigas tal y como estas pueden observarse en la naturaleza, es decir, con fases de actividad autosincronizadas. El principal objectivo de este tipo de técnicas es ahorrar energía gracias a alternar estados de forma eficiente. En este caso en concreto, consideramos dos estados diferentes: el estado dormido, en el que los nodos no pueden comunicarse y el consumo energético es bajo; y el estado activo, en el que las comunicaciones propician un consumo energético elevado. Con el objetivo de probar el modelo, se ha llevado a cabo una extensa experimentación que incluye tanto simulaciones síncronas en redes móviles y estáticas, como simulaciones en redes asíncronas. Además, este trabajo se extendió asumiendo un punto de vista más amplio e incluyendo un detallado estudio de los parámetros del algoritmo. Finalmente, gracias a la colaboración con la Technical University of Braunschweig, tuvimos la oportunidad de probar el mecanismo en el simulador realista de redes de sensores, Shawn (http://shawn.sf.net). La segunda parte de esta tesis está dedicada a la desincronización de nodos en redes de sensores y a su aplicación al problema del coloreado de grafos de forma distribuida. En particular, nuestra investigación está inspirada por el canto de las ranas de árbol japonesas, cuyos machos utilizan su canto para atraer a las hembras. Resulta interesante que debido a que las hembras solo son capaces de localizar las ranas macho cuando sus cantos no están demasiado cerca en el tiempo, los grupos de machos que se hallan en una misma región desincronizan sus cantos. Basado en un modelo de este comportamiento que se encuentra en la literatura, proponemos un nuevo algoritmo con aplicaciones al campo de las redes de sensores. Más en detalle, analizamos la habilidad del algoritmo para desincronizar nodos vecinos. Además, consideramos extensiones del modelo original, mejorando su capacidad de desincronización. Para ilustrar los potenciales beneficios de las redes desincronizadas, nos centramos en el problema del coloreado de grafos distribuido que tiene relación con diferentes tareas habituales en redes de sensores. El clásico problema del broadcasting de consumo mínimo en redes ad hoc ha sido bien estudiado en la literatura. El problema considera un modelo de antena que permite transmitir a cualquier potencia elegida (hasta un máximo establecido por el dispositivo). Sin embargo, cuando se trabaja de forma específica con redes de sensores, un vistazo al hardware actualmente disponible muestra que este modelo de antena no es demasiado realista. En este trabajo reformulamos el problema para el modelo de antena más habitual en redes de sensores. En este modelo, los niveles de potencia de transmisión se eligen de un conjunto finito de posibilidades. La siguiente contribución consiste en en la adaptación de un algoritmo de optimización por colonias de hormigas a la versión más realista del problema, también conocida como broadcasting de consumo mínimo con antenas realistas. Los resultados obtenidos muestran que la ventaja de este método sobre heurísticas clásicas incluso crece cuando el número de posibles potencias de transmisión decrece. Además, se ha presentado una versión distribuida del algoritmo, que también se compara de forma bastante favorable contra las heurísticas centralizadas conocidas.

Thesis (Ph. D.)--State University of New York at Binghamton, Thomas J. Watson School of Engineering and Applied Science, Department of Systems Science and Industrial Engineering, 2009. / Includes bibliographical references.

We analyze spatio-temporal routing under various constraints specific to multi-robot applications. Spatio-temporal routing requires multiple robots to visit spatial locations at specified time instants, while optimizing certain criteria like the total distance traveled, or the total energy consumed. Such a spatio-temporal concept is intuitively demonstrable through music (e.g. a musician routes multiple fingers to play a series of notes on an instrument at specified time instants). As such, we showcase much of our work on routing through this medium. Particular to robotic applications, we analyze constraints like maximum velocities that the robots cannot exceed, and information-exchange networks that must remain connected. Furthermore, we consider a notion of heterogeneity where robots and spatial locations are associated with multiple skills, and a robot can visit a location only if it has at least one skill in common with the skill set of that location. To extend the scope of our work, we analyze spatio-temporal routing in the context of a distributed framework, and a dynamic environment.

Wireless networks promise ubiquitous communication, and thus facilitate an array of applications that positively impact human life. At a fundamental level, these networks deal with compression and transmission of sources over channels. Thus, accomplishing this task efficiently is the primary challenge shared by these applications. In practice, sources include data and video while channels include interference and relay networks. Hence, effective source and channel aware resource allocation for these scenarios would result in a comprehensive solution applicable to real-world networks. This dissertation studies the problem of source and channel aware resource allocation in certain scenarios. A framework for network resource allocation that stems from rate-distortion theory is presented. Then, an optimal decomposition into an application-layer compression control, a transport-layer congestion control and a network-layer scheduling is obtained. After deducing insights into compression and congestion control, the scheduling problem is explored in two cross-layer scenarios. First, appropriate queue architecture for cooperative relay networks is presented, and throughput-optimality of network algorithms that do not assume channel-fading and input-queue distributions are established. Second, decentralized algorithms that perform rate allocation, which achieve the same overall throughput region as optimal centralized algorithms, are derived. In network optimization, an underlying throughput region is assumed. Hence, improving this throughput region is the next logical step. This dissertation addresses this problem in the context of three significant classes of interference networks. First, degraded networks that capture highly correlated channels are explored, and the exact sum capacity of these networks is established. Next, multiple antenna networks in the presence of channel uncertainty are considered. For these networks, robust optimization problems that result from linear precoding are investigated, and efficient iterative algorithms are derived. Last, multi-cell time-division-duplex systems are studied in the context of corrupted channel estimates, and an efficient linear precoding to manage interference is developed. / text

Video traffic constitutes a major part of the Internet traffic nowadays. Yet most video delivery services remain best-effort, relying on server bandwidth over-provisioning to guarantee Quality of Service (QoS). Cloud computing is changing the way that video services are offered, enabling elastic and efficient resource allocation through auto-scaling. In this thesis, we propose a new framework of cloud workload management for multimedia delivery services, incorporating demand forecast, predictive resource allocation and quality assurance, as well as resource pricing as inter-dependent components. Based on the trace analysis of a production Video-on-Demand (VoD) system, we propose time-series techniques to predict video bandwidth demand from online monitoring, and determine bandwidth reservations from multiple data centers and the related load direction policy. We further study how such quality-guaranteed cloud services should be priced, in both a game theoretical model and an optimization model.Particularly, when multiple video providers coexist to use cloud resources, we use pricing to control resource allocation in order to maximize the aggregate network utility, which is a standard network utility maximization (NUM) problem with coupled objectives. We propose a novel class of iterative distributed solutions to such problems with a simple economic interpretation of pricing. The method proves to be more efficient than the conventional approach of dual decomposition and gradient methods for large-scale systems, both in theory and in trace-driven simulations.

Video traffic constitutes a major part of the Internet traffic nowadays. Yet most video delivery services remain best-effort, relying on server bandwidth over-provisioning to guarantee Quality of Service (QoS). Cloud computing is changing the way that video services are offered, enabling elastic and efficient resource allocation through auto-scaling. In this thesis, we propose a new framework of cloud workload management for multimedia delivery services, incorporating demand forecast, predictive resource allocation and quality assurance, as well as resource pricing as inter-dependent components. Based on the trace analysis of a production Video-on-Demand (VoD) system, we propose time-series techniques to predict video bandwidth demand from online monitoring, and determine bandwidth reservations from multiple data centers and the related load direction policy. We further study how such quality-guaranteed cloud services should be priced, in both a game theoretical model and an optimization model.Particularly, when multiple video providers coexist to use cloud resources, we use pricing to control resource allocation in order to maximize the aggregate network utility, which is a standard network utility maximization (NUM) problem with coupled objectives. We propose a novel class of iterative distributed solutions to such problems with a simple economic interpretation of pricing. The method proves to be more efficient than the conventional approach of dual decomposition and gradient methods for large-scale systems, both in theory and in trace-driven simulations.

In todays heterogeneous network environment, there is a growing demand for distrusted parties to jointly execute distributed algorithms on private data whose secrecy needed to be safeguarded. Platforms that support such computation on image processing purposes are called secure image processing protocols. In this thesis, we propose a new security model, called quasi information theoretic (QIT) security. Under the proposed model efficient protocols on two basic image processing algorithms linear filtering and thresholding are developed. For both problems we consider two situations: 1) only two parties are involved where one holds the data and the other possesses the processing algorithm; 2) an additional non-colluding third party exists. Experiments show that our proposed protocols improved the computational time significantly compared with the classical cryptographical couterparts as well as providing reasonable amount of security as proved in the thesis

Περιληπτικά, στη συγκεκριμένη διδακτορική διατριβή μελετήθηκαν οι θεωρίες της βελτιστοποίησης και των κατανεμημένων αλγορίθμων με σκοπό την χρήση τους σε ένα διομότιμο σύστημα σύγχρονου διαμοιρασμού αντικειμένων. Επιπλέον μελετήθηκε το περιβάλλον και οι συνθήκες λειτουργίας ενός τέτοιου συστήματος. καθώς και τα χαρακτηριστικά του. Αποτέλεσμα της μελέτης αυτής είναι η εξαγωγή συμπερασμάτων σχετικά με τις απαιτήσεις που πρέπει να πληρούνται κατά τη δημιουργία ενός διομότιμου συστήματος σύγχρονου διαμοιρασμού αντικειμένων και οι τεχνικοί στόχοι που πρέπει αυτό να ικανοποιεί. Με αυτά τα κριτήρια σχεδιάστηκε η αρχιτεκτονική του συστήματος και ορίστηκαν τα προβλήματα που πρέπει να επιλυθούν. Για την λειτουργία ενός τέτοιου συστήματος ορίστηκαν οι ακόλουθες απαιτήσεις: • Μεγιστοποίηση της χρήσης από το σύστημα του διαθέσιμου εύρους ζώνης των συμμετεχόντων κόμβων. Φυσικά, οι κόμβοι έχουν ετερογενείς τιμές του διαθέσιμου εύρους ζώνης και, μάλιστα, με μεγάλη διασπορά. • Ελαχιστοποίηση της καθυστέρησης από τη στιγμή δημιουργίας ενός αντικειμένου μέχρι τον διαμοιρασμό του σε κάθε συμμετέχοντα κόμβο. • Ομοιόμορφη διαρκής κατανομή του συνολικού εύρους ζώνης του συστήματος στους συμμετέχοντες κόμβους. • Ανεκτικότητα του συστήματος στη δυναμική συμπεριφορά των χρηστών που προκαλείται από εισόδους και εξόδους των χρηστών στο σύστημα σε μη προκαθορισμένες χρονικές στιγμές. • Ικανότητα κλιμάκωσης του συστήματος σε αριθμό συμμετεχόντων χρηστών κάτι που επάγει την κατανεμημένη διαχείριση του συστήματος. • Προσαρμογή του σχεδιαζόμενου συστήματος στην κίνηση του δικτύου στο οποίο αυτό επικάθεται και ανεκτικότητά του στις μεταβολές του εύρους ζώνης των συμμετεχόντων κόμβων. • Ελαχιστοποίηση του φορτίου το οποίο εισάγει η λειτουργία του συστήματος στο δίκτυο. Για τη λειτουργία του προτεινόμενου συστήματος απαιτείται η δημιουργία ενός γράφου διασύνδεσης. Ως γράφος διασύνδεσης ορίζεται ο γράφος που προκύπτει αν κάθε κόμβος συνδεθεί με ένα μικρό υποσύνολο των συμμετεχόντων κόμβων που ονομάζονται και γείτονες του κόμβου. Για την ικανοποίηση των προαναφερθεισών απαιτήσεων. μελετήθηκαν τα χαρακτηριστικά του γράφου διασύνδεσης και προέκυψε ότι κάθε κόμβος: α) πρέπει να έχει γείτονες με όσο το δυνατόν μικρότερη δικτυακή καθυστέρηση μεταξύ τους, β) πρέπει να έχει αριθμό εξερχόμενων συνδέσεων ανάλογο με το εύρος ζώνης του, γ) οι συνδέσεις αυτές πρέπει να κατανέμονται ομοιόμορφα στους συμμετέχοντες κόμβους για την ικανοποίηση των αναγκών όλων των κόμβων, δ) οι κόμβοι με σχετικά μεγάλο εύρος ζώνης πρέπει να ομαδοποιούνται στο γράφο με σκοπό την γρήγορη αρχικά διάχυση του αντικειμένου και ε) ο γράφος διασύνδεσης πρέπει να αναδιατάσσεται δυναμικά έτσι ώστε να διατηρεί τις ιδιότητες αυτές στο δυναμικό δικτυακό περιβάλλον που επικάθεται και για δυναμική συμπεριφορά των συμμετεχόντων κόμβων. Για την ικανοποίηση αυτών των τεχνικών στόχων αναπτύχθηκε μία δομή του γράφου που ικανοποιεί αυτά τα χαρακτηριστικά. Η βελτιστοποίηση του γράφου γίνεται μέσω αλγορίθμων κατά την λειτουργία των οποίων κάθε κόμβος επιλέγει περιοδικά ένα τυχαίο κόμβο ο οποίος είναι γείτονάς του στον γράφο διασύνδεσης. Μεταξύ των δύο αυτών κόμβων εκτελείται ανακατανομή των γειτόνων τους με σκοπό την εξισορρόπηση του αριθμού των γειτόνων που κάθε ένας από αυτούς διαθέτει. αλλά και την ελαχιστοποίηση της μέσης καθυστέρησης που έχουν αθροιστικά οι κόμβοι από τους γείτονές τους. Οι αλλαγές στον γράφο διασύνδεσης που προκύπτουν από κάθε εκτέλεση του αλγορίθμου αυτού μεταβάλλουν και τους γείτονες ενός υποσυνόλου κόμβων εκτός των δύο συμμετεχόντων στον αλγόριθμο εναλλαγής. Οι αλλαγές αυτές επιφέρουν άλλες αλλαγές με την σειρά τους και έτσι προκύπτει τελικά ένας γράφος διασύνδεσης όπου κάθε κόμβος έχει τον προκαθορισμένο αριθμό γειτόνων και. παράλληλα. ελαχιστοποιείται το άθροισμα των μέσων δικτυακών καθυστερήσεων που έχουν οι συμμετέχοντες κόμβοι με τους γείτονές τους. Για τον διαμοιρασμό του αντικειμένου ο δημιουργός του το τεμαχίζει σε τεμάχια (μπλοκ). Τα τεμάχια προωθούνται σε ένα πολύ μικρό σύνολο κόμβων και αποτελούν τις λογικές μονάδες δεδομένων που ανταλλάσσονται μεταξύ των κόμβων. Σκοπός είναι ο διαμοιρασμός του κάθε τεμαχίου σε κάθε κόμβο μέσα σε ένα προκαθορισμένο χρονικό διάστημα. Για την ανταλλαγή τεμαχίων μεταξύ των γειτόνων του γράφου διασύνδεσης του προς διαμοιρασμού αντικειμένου μεταξύ των συμμετεχόντων κόμβων αναπτύχθηκε ένας Κατανεμημένος Χρονοπρογραμματιστής Ανταλλαγής Τεμαχίων (ΚΧΑΤ). Τεχνικοί στόχοι της ανάπτυξης του ΚΧΑΜ αποτέλεσαν α) ο χρονισμός διαπραγμάτευσης αποστολής τεμαχίων μεταξύ κάθε αποστολέα και παραλήπτη, β) η γρήγορη διάδοση πρόσφατα παραγόμενων τεμαχίων και σπάνιων σε μία γειτονία του γράφου διασύνδεσης (τεμάχια που δημιουργήθηκαν μεταγενέστερα από άλλα ευνοούνται από το χρονοπρογραμματιστή αρχικά για την επιτυχή και γρήγορη διάδοσή τους σε μία κρίσιμη μάζα από κόμβους), γ) η τροφοδότηση όλων των κόμβων με ομοιόμορφο και σταθερό ρυθμό, δ) η προτεραιότητα σε κόμβους με μεγάλο εύρος ζώνης, ε) η αποφυγή μετάδοσης του ίδιου τεμαχίου από δύο αποστολείς προς τον ίδιο παραλήπτη και στ) η αποφυγή μιας κατάστασης όπου αποστολέας και παραλήπτης δεν έχουν τεμάχια προς ανταλλαγή. Ο χρονισμός του ΚΧΑΜ που αναπτύχθηκε αποτελείται από τρείς φάσεις. Στην πρώτη φάση που εκτελείται περιοδικά από κάθε αποστολέα εκδίδεται και αποστέλλεται στους πιθανούς παραλήπτες ένα σύνολο από «κουπόνια» μεγέθους ανάλογου με το εύρος ζώνης του αποστολέα. Στη δεύτερη φάση ο εκάστοτε παραλήπτης ζητά προκαταβολικά ένα τεμάχιο στην περίπτωση που επιλεγεί από τον αποστολέα για μετάδοση τεμαχίου. Στην τρίτη φάση ο αποστολέας επιλέγει τον παραλήπτη ακριβώς πριν την μετάδοση κάθε τεμαχίου και αποστέλλει το τεμάχιο που έχει ζητηθεί. Ο αλγόριθμος ο οποίος προτείνεται για τη δημιουργία κουπονιών έχει ως στόχο τη μεγιστοποίηση της χρήσης του εύρους ζώνης όλων των κόμβων και την ικανοποίηση των αναγκών κάθε συμμετέχοντα κόμβου. Είναι αυτός που, στην ουσία, καθορίζει τις ροές δεδομένων μεταξύ των γειτόνων του γράφου διασύνδεσης. Η χρησιμότητά του αναδεικνύεται σε περιπτώσεις όπου ο ρυθμός αναπαραγωγής του προς διαμοιρασμό αντικειμένου είναι παρόμοιος με το μέσο εύρος ζώνης του συστήματος. Οι απαιτήσεις του αλγορίθμου ζήτησης τεμαχίων μοντελοποιούνται μέσω της γραμμικής βελτιστοποίησης και διασφαλίζεται η γρήγορη και αποτελεσματική διάχυση των τεμαχίων ελαχιστοποιώντας την ύπαρξη ανενεργών πόρων. Τέλος, ο αλγόριθμος επιλογής γείτονα είναι αυτός που ρυθμίζει την ομοιόμορφη κατανομή του εύρους ζώνης στους συμμετέχοντες κόμβους, αλλά και δίνει προτεραιότητα στους κόμβους με μεγάλο εύρος ζώνης έτσι ώστε να επιτευχθεί ο γρήγορος διαμοιρασμός κάθε τεμαχίου και η ελαχιστοποίηση της καθυστέρησης του συστήματος. Η αξιολόγηση της προτεινόμενης αρχιτεκτονικής, της τοπολογίας του γράφου διασύνδεσης και του ΚΧΑΜ, έγινε μέσω προσομοίωσης σε προσομοιωτή δικτυακών συστημάτων. Μοντελοποιήθηκε το εύρος ζώνης των συμμετεχόντων κόμβων και δικτυακές καθυστερήσεις χρησιμοποιώντας πραγματικά δεδομένα από διομότιμα συστήματα.. Το σύστημα που αναπτύχθηκε μοντελοποιήθηκε πλήρως σε επίπεδο πακέτου. Εξετάστηκαν αρκετά σενάρια αξιολόγησης του συστήματος τα οποία, μεταξύ άλλων, περιλαμβάνουν, ευαισθησία του συστήματος σε παραμέτρους των προτεινόμενων αλγορίθμων, δυναμικά σενάρια όσον αφορά τη συμπεριφορά των χρηστών και του δικτύου και σενάρια εύρεσης των ορίων του προτεινόμενου συστήματος. Η αξιολόγηση των αποτελεσμάτων έδειξε ότι ικανοποιούνται οι απαιτήσεις που τέθηκαν για τη δημιουργία του συστήματος, καθώς και βελτίωση της συμπεριφοράς του συστήματος σε σχέση με αντίστοιχα συστήματα της διεθνούς βιβλιογραφίας με τα οποία συγκρίθηκε. / 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.

DANTAS, Allberson Bruno de Oliveira. Uma interface de programação distribuída para aplicações em otimização combinatória. 2011. 86 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2011. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-08T17:57:51Z No. of bitstreams: 1 2011_dis_abodantas.pdf: 805347 bytes, checksum: c9671608a7d738f843239856e546e201 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-13T12:23:03Z (GMT) No. of bitstreams: 1 2011_dis_abodantas.pdf: 805347 bytes, checksum: c9671608a7d738f843239856e546e201 (MD5) / Made available in DSpace on 2016-07-13T12:23:03Z (GMT). No. of bitstreams: 1 2011_dis_abodantas.pdf: 805347 bytes, checksum: c9671608a7d738f843239856e546e201 (MD5) Previous issue date: 2011 / This work was motivated by the need of exploiting the potential of distributed paralelism in combinatorial optimization applications. propose a distributed programming interface, To achieve this goal, we in which we cherish two main requirements: e ciency and reuse. The rst stems from the need of HPC (High applications require maximum possible performance. Performance Computing) Therefore, we specify our interface as an extension of the MPI library, which is assumed to be e cient for distributed applications. The reuse requirement must make compatible two important features: asynchronism and collective operations. Asynchronism must be present at our interface, once most of combinatorial optimization applications have an asynchronous nature. Collective operations are features that should be available in the interface, so that they can be used by applications in their execution. In order reach the reuse requirement, we based this interface on the Event- and Pulse-driven Models of Distributed Computing, once they are asynchronous and allow the incorporation of collective operations. We implemented partially the interface de ned in this work. In order to validate the use of the inteface by combinatorial optimization applications, we selected two applications and implemented them using our interface. They are the Branch-and-Bound technique and the Maximum Stable Set Problem (MSSP). We also provide some experimental results. / Este trabalho foi motivado pela necessidade da exploração do potencial do paralelismo distribuído em aplicações em Otimização Combinatória. Para tanto, propomos uma interface de programação distribuída, na qual prezamos dois requisitos principais: eficiência e reuso. O primeiro advém da necessidade de aplicações de CAD exigirem máximo desempenho possível. Assim sendo, especificamos esta interface como uma extensão da biblioteca MPI, a qual é assumida como eficiente para aplicações distribuídas. O requisito reuso deve tornar compatíveis duas características importantes: assincronismo e operações coletivas. O assincronismo deve estar presente na interface, uma vez que as aplicações em Otimização Combinatória, em sua maioria, possuem uma natureza assíncrona. Operações coletivas são funcionalidades que devem estar disponíveis na interface, de modo que possam ser utilizadas por aplicações em suas execuções. Tendo em vista atender o requisito reuso, baseamos esta interface nos Modelos de Computação Distribuída Dirigidos por Eventos e por Pulsos, pois os mesmos são assíncronos e permitem a incorporação de operações coletivas. Implementamos parcialmente a inteface definida neste trabalho. Tendo em vista validar uso desta inteface por aplicações em Otimização Combinatória, selecionamos duas aplicações e as implementamos utilizando a interface. São elas a técnica Branch-and-Bound e o Problema do Conjunto Independente Máximo (CIM). Fornecemos também alguns resultados experimentais.