Performance evaluation continues to play an important role in network research. Two types of research efforts related to network performance evaluation are particularly noteworthy: (1) using performance evaluation to understand specific problems and to design better solutions, and (2) designing efficient performance evaluation methodologies. This thesis addresses several performance evaluation challenges, encompassing both categories of effort listed above, in building high-performance TCP-based network services in the context of overlay routing and peer-to-peer systems. With respect to the first type of research effort, this thesis addresses two issues related to the design of TCP-based network services: 1. Prediction of large transfer TCP throughput: Predicting the TCP throughput attainable on given paths is used for applications such as route selection in overlay routing. Based on a systematic measurement study, we evaluate the accuracy of two categories of TCP throughput prediction techniques. We then analyze the factors that affect the accuracy of each. 2. Congestion control and message loss in Gnutella peer-to-peer networks: We evaluate the congestion control mechanisms and message loss behavior in a real-world overlay network, the Gnutella system. The challenges for congestion control in such a network are analyzed, as are the design tradeoffs of alternative mechanisms. In order to study systems such as the above with details of the network, we build a scalable, extensible and portable packet-level simulator of peer-to-peer systems. The second part of the thesis, representing the second type of effort above, proposes two techniques to improve network simulation by exploiting the detailed knowledge of TCP: 1. Speed up network simulation by exploiting TCP steady-state predictability: We develop a technique that uses prediction to accurately summarize a series of packet events and, therefore, to save on processing cost while maintaining fidelity. Our technique integrates well with packet-level simulations and is more faithful in several respects than previous optimization techniques. 2. TCP workload generation under link load constraints: We develop an algorithm that generates traffic for a specific network configuration such that realistic and specific load conditions are obtained on user-specified links. At the same time, the algorithm minimizes the simulation memory requirement.

As computers become pervasive and better connected, the popularity of peer-to-peer computing has grown immensely. The sharing of unused resources at peers is desirable and practically important because they can collectively comprise a powerful system. The potential benefit, however, can be undermined by uncooperative behavior of some peers because they are managed individually and hence may not follow the expected protocols. To build robust systems, we must incorporate proper trust and incentive mechanisms so that peers would rather cooperate. In this dissertation, we demonstrate that building robust peer-to-peer information dissemination systems is important and viable, using four concrete cases. First, we investigate the incentive mechanism of BitTorrent, an exchange-based file distribution protocol. Our framework based on iterated prisoner's dilemma provides an insight into users' tension between eagerness to download and unwillingness to upload. By using both analytical and experimental approaches, we show that the current incentive mechanism of BitTorrent is susceptible to free riding. We propose an improved mechanism that punishes free riders effectively. Second, we present a trust-aware overlay multicast system that performs well in the presence of uncooperative nodes, which may block, delay, fabricate, or forge the messages they forward. We develop (1) a set of protocols that detect uncooperative behavior, (2) a scheme of trust value assignment according to the behavior of nodes, and (3) an algorithm that adapts the multicast tree based on trust values, all of which allows the system to remain stable and responsive over time. Third, we propose an alternative news feed dissemination system, called FeedEx, in which feed subscribers mesh into a network and exchange news feeds with neighbors. The collaborative exchange in FeedEx, with the help of the incentive-compatible design using the pair-wise fairness principle, reduces the server load and hence increases the scalability. Fourth, we introduce a new concept of peer-to-peer computing, that is, continual service using ephemeral servers. To this end, we develop a system model for the concept and implement a discrete-time simulator to find the conditions and the system support for eliciting cooperation. All four cases are substantiated by experimental results.

The Internet has scaled massively over the past 15 years to extend to billions of users. These users increasingly require extensive applications and capabilities from the Internet, such as Quality of Service (QoS) optimized paths between end hosts. When default Internet paths may not meet their requirements adequately, there is a need to facilitate the discovery of such QoS optimized paths. Fortunately, even though the route offered by the Internet may not work (to the required level of performance), often there exist alternate routes that do work. When the direct Internet path between two Internet hosts for instance is sub-optimal (according to specific user defined criterion), there is a possibility that the direct paths of both to a third host may not be suffering from the same problem owing to path disjointness. Overlay Networks facilitate the discovery of such composite alternate paths through third party hosts. To discover such alternate paths, overlay hosts regularly monitor both Internet path quality and choose better alternate paths via other hosts. Such measurements are costly and pose scalability problems for large overlay networks. This thesis asserts and shows that these overheads could be lowered substantially if the network layer path information between overlay hosts could be obtained, which facilitates selection of disjoint paths. This thesis further demonstrates that obtaining such network layer path information is very challenging. As opposed to the path monitoring which only requires cooperation of overlay hosts, disjoint path selection depends on the accuracy of information about the underlay, which is out of the domain of control of the overlay and so may contain inaccuracies. This thesis investigates how such information could be gleaned at different granularities for optimal tradeoffs between spatial and/or temporal methods for selection of alternate paths. The main contributions of this thesis are: (i) investigation of scalable techniques to facilitate alternate path computation using network layer path information; (ii) a review of the realistic performance gains achievable using such alternate paths; and (iii) investigation of techniques for revealing the presence of incorrect network layer path information, proposal of new techniques for its removal.

The Internet has scaled massively over the past 15 years to extend to billions of users. These users increasingly require extensive applications and capabilities from the Internet, such as Quality of Service (QoS) optimized paths between end hosts. When default Internet paths may not meet their requirements adequately, there is a need to facilitate the discovery of such QoS optimized paths. Fortunately, even though the route offered by the Internet may not work (to the required level of performance), often there exist alternate routes that do work. When the direct Internet path between two Internet hosts for instance is sub-optimal (according to specific user defined criterion), there is a possibility that the direct paths of both to a third host may not be suffering from the same problem owing to path disjointness. Overlay Networks facilitate the discovery of such composite alternate paths through third party hosts. To discover such alternate paths, overlay hosts regularly monitor both Internet path quality and choose better alternate paths via other hosts. Such measurements are costly and pose scalability problems for large overlay networks. This thesis asserts and shows that these overheads could be lowered substantially if the network layer path information between overlay hosts could be obtained, which facilitates selection of disjoint paths. This thesis further demonstrates that obtaining such network layer path information is very challenging. As opposed to the path monitoring which only requires cooperation of overlay hosts, disjoint path selection depends on the accuracy of information about the underlay, which is out of the domain of control of the overlay and so may contain inaccuracies. This thesis investigates how such information could be gleaned at different granularities for optimal tradeoffs between spatial and/or temporal methods for selection of alternate paths. The main contributions of this thesis are: (i) investigation of scalable techniques to facilitate alternate path computation using network layer path information; (ii) a review of the realistic performance gains achievable using such alternate paths; and (iii) investigation of techniques for revealing the presence of incorrect network layer path information, proposal of new techniques for its removal.

Devido à evolução e à crescente complexidade dos sistemas computacionais, grandes mudanças ocorreram na área de gerenciamento de redes. Os modelos tradicionais centralizados se mostraram limitados, e novos modelos de gerenciamento de redes estão sendo propostos e investigados. Neste cenário, modelos de comunicação P2P permitem a construção de ambientes dinâmicos e versáteis capazes de resolver problemas de diferentes áreas da computação, entre elas o gerenciamento de redes. O modelo P2P torna-se atrativo porque se encaixa perfeitamente no gerenciamento de redes distribuído atualmente solicitado. A partir da proposta de gerenciamento de redes usando P2P e da apresentação de um novo modelo conceitual usando essa nova perspectiva, foi desenvolvido um projeto de arquiteturas para gerenciamento baseadas em P2P, focando-se em entidades tais como peers de gerenciamento Top-Level (TLM) e Mid-Level (MLM). A fim de efetivamente concretizar o gerenciamento baseado em P2P, foram introduzidas definições de blocos básicos para sistemas de gerenciamento baseados em P2P. A integração desses blocos básicos com soluções tradicionais de gerenciamento, tal como a estrutura SNMP, também foi apresentada. Um dos conceitos centrais da arquitetura apresentada são os Serviços de Gerenciamento, que definem as tarefas básicas de gerenciamento do sistema, e foram inspirados nos conceitos de Web Services e na concepção de serviços das Arquiteturas Orientadas a Serviço (SOA). Para a avaliação desse novo modelo de gerenciamento de redes e da arquitetura associada, surgiu a necessidade do desenvolvimento de um protótipo do sistema, com o intuito de servir como uma plataforma para desenvolvimento e implantação de Serviços de Gerenciamento. Esse protótipo é usado para avaliação e análise de testes e resultados associados. Para preservar as características de disponibilidade e escalabilidade que são inerentes dos sistemas P2P, definiu-se que os Serviços de Gerenciamento devem ser disponibilizados por Grupos de MLMs, organizados de forma a fazer a distribuição de tarefas de gerenciamento entre si. Diversos modelos de distribuição de carga foram investigados, foram realizadas avaliações e gráficos comparativos, e foram estabelecidas diretrizes sobre quando e como deve ser aplicado cada modelo, de modo a alcançar sempre o melhor rendimento e a maximização do aproveitamento dos recursos disponíveis ao sistema. A avaliação realizada consistiu na execução de diversas requisições com diferentes números de MLMs usando diferentes algoritmos de distribuição de carga, e na comparação entre a vazão, os tempos de resposta e o tráfego de rede gerados pelos diferentes casos de uso. A implementação desenvolvida neste trabalho demonstrou ser promissora, apresentando resultados bastante satisfatórios com relação aos parâmetros avaliados. / Due to the increasing complexity of computer systems, deep changes have occurred in network management in the past few years. Traditional centralized models have been proved limited, and new network management models are being proposed and investigated. In this scenery, P2P communication models allow for the creation of dynamic and versatile environments, able to solve problems in various computational areas, one of them being network management. The P2P model fits perfectly in the current demands of distributed network management. Starting from the proposed P2P-based network management model, a new P2P-based network management architecture has been developed, focusing on entities like Top-Level (TLM) and Mid-Level (MLM) management peers. With the purpose of making the P2P-based network management real, new building blocks for P2P-based network management systems have been defined. In the present work, an integration of these new building blocks with traditional network management solutions - like SNMP - is presented. One of the main concepts of the proposed architecture is on Management Services, inspired by Web Services and in the service definition of Service Oriented Architectures (SOA). To evaluate this new network management model and its associated architecture, it was necessary to develop a prototype system to be used as platform for development and deployment of Management Services. This prototype was used for evaluation, testing and result analysis. To hold the characteristics of availability and scalability that are inherent to the P2P systems, the Management Services had to be served by MLM groups, organized in a way to distribute the management tasks between them. Several load distribution models were investigated, with evaluation and comparative graphics fulfilled, and some guidelines were established as to when and how each model should be applied to reach the best performance and the maximization of the computational resources available to the system. The evaluation consisted in the execution of several requests in groups with distinct MLM numbers and using distinct load distribution algorithms. Then, the response time and network traffic generated by use cases were compared. We then showed that the developed implementation of our proposal is promising, and presents good results in relation with the evaluated parameters.

Devido à evolução e à crescente complexidade dos sistemas computacionais, grandes mudanças ocorreram na área de gerenciamento de redes. Os modelos tradicionais centralizados se mostraram limitados, e novos modelos de gerenciamento de redes estão sendo propostos e investigados. Neste cenário, modelos de comunicação P2P permitem a construção de ambientes dinâmicos e versáteis capazes de resolver problemas de diferentes áreas da computação, entre elas o gerenciamento de redes. O modelo P2P torna-se atrativo porque se encaixa perfeitamente no gerenciamento de redes distribuído atualmente solicitado. A partir da proposta de gerenciamento de redes usando P2P e da apresentação de um novo modelo conceitual usando essa nova perspectiva, foi desenvolvido um projeto de arquiteturas para gerenciamento baseadas em P2P, focando-se em entidades tais como peers de gerenciamento Top-Level (TLM) e Mid-Level (MLM). A fim de efetivamente concretizar o gerenciamento baseado em P2P, foram introduzidas definições de blocos básicos para sistemas de gerenciamento baseados em P2P. A integração desses blocos básicos com soluções tradicionais de gerenciamento, tal como a estrutura SNMP, também foi apresentada. Um dos conceitos centrais da arquitetura apresentada são os Serviços de Gerenciamento, que definem as tarefas básicas de gerenciamento do sistema, e foram inspirados nos conceitos de Web Services e na concepção de serviços das Arquiteturas Orientadas a Serviço (SOA). Para a avaliação desse novo modelo de gerenciamento de redes e da arquitetura associada, surgiu a necessidade do desenvolvimento de um protótipo do sistema, com o intuito de servir como uma plataforma para desenvolvimento e implantação de Serviços de Gerenciamento. Esse protótipo é usado para avaliação e análise de testes e resultados associados. Para preservar as características de disponibilidade e escalabilidade que são inerentes dos sistemas P2P, definiu-se que os Serviços de Gerenciamento devem ser disponibilizados por Grupos de MLMs, organizados de forma a fazer a distribuição de tarefas de gerenciamento entre si. Diversos modelos de distribuição de carga foram investigados, foram realizadas avaliações e gráficos comparativos, e foram estabelecidas diretrizes sobre quando e como deve ser aplicado cada modelo, de modo a alcançar sempre o melhor rendimento e a maximização do aproveitamento dos recursos disponíveis ao sistema. A avaliação realizada consistiu na execução de diversas requisições com diferentes números de MLMs usando diferentes algoritmos de distribuição de carga, e na comparação entre a vazão, os tempos de resposta e o tráfego de rede gerados pelos diferentes casos de uso. A implementação desenvolvida neste trabalho demonstrou ser promissora, apresentando resultados bastante satisfatórios com relação aos parâmetros avaliados. / Due to the increasing complexity of computer systems, deep changes have occurred in network management in the past few years. Traditional centralized models have been proved limited, and new network management models are being proposed and investigated. In this scenery, P2P communication models allow for the creation of dynamic and versatile environments, able to solve problems in various computational areas, one of them being network management. The P2P model fits perfectly in the current demands of distributed network management. Starting from the proposed P2P-based network management model, a new P2P-based network management architecture has been developed, focusing on entities like Top-Level (TLM) and Mid-Level (MLM) management peers. With the purpose of making the P2P-based network management real, new building blocks for P2P-based network management systems have been defined. In the present work, an integration of these new building blocks with traditional network management solutions - like SNMP - is presented. One of the main concepts of the proposed architecture is on Management Services, inspired by Web Services and in the service definition of Service Oriented Architectures (SOA). To evaluate this new network management model and its associated architecture, it was necessary to develop a prototype system to be used as platform for development and deployment of Management Services. This prototype was used for evaluation, testing and result analysis. To hold the characteristics of availability and scalability that are inherent to the P2P systems, the Management Services had to be served by MLM groups, organized in a way to distribute the management tasks between them. Several load distribution models were investigated, with evaluation and comparative graphics fulfilled, and some guidelines were established as to when and how each model should be applied to reach the best performance and the maximization of the computational resources available to the system. The evaluation consisted in the execution of several requests in groups with distinct MLM numbers and using distinct load distribution algorithms. Then, the response time and network traffic generated by use cases were compared. We then showed that the developed implementation of our proposal is promising, and presents good results in relation with the evaluated parameters.

Devido à evolução e à crescente complexidade dos sistemas computacionais, grandes mudanças ocorreram na área de gerenciamento de redes. Os modelos tradicionais centralizados se mostraram limitados, e novos modelos de gerenciamento de redes estão sendo propostos e investigados. Neste cenário, modelos de comunicação P2P permitem a construção de ambientes dinâmicos e versáteis capazes de resolver problemas de diferentes áreas da computação, entre elas o gerenciamento de redes. O modelo P2P torna-se atrativo porque se encaixa perfeitamente no gerenciamento de redes distribuído atualmente solicitado. A partir da proposta de gerenciamento de redes usando P2P e da apresentação de um novo modelo conceitual usando essa nova perspectiva, foi desenvolvido um projeto de arquiteturas para gerenciamento baseadas em P2P, focando-se em entidades tais como peers de gerenciamento Top-Level (TLM) e Mid-Level (MLM). A fim de efetivamente concretizar o gerenciamento baseado em P2P, foram introduzidas definições de blocos básicos para sistemas de gerenciamento baseados em P2P. A integração desses blocos básicos com soluções tradicionais de gerenciamento, tal como a estrutura SNMP, também foi apresentada. Um dos conceitos centrais da arquitetura apresentada são os Serviços de Gerenciamento, que definem as tarefas básicas de gerenciamento do sistema, e foram inspirados nos conceitos de Web Services e na concepção de serviços das Arquiteturas Orientadas a Serviço (SOA). Para a avaliação desse novo modelo de gerenciamento de redes e da arquitetura associada, surgiu a necessidade do desenvolvimento de um protótipo do sistema, com o intuito de servir como uma plataforma para desenvolvimento e implantação de Serviços de Gerenciamento. Esse protótipo é usado para avaliação e análise de testes e resultados associados. Para preservar as características de disponibilidade e escalabilidade que são inerentes dos sistemas P2P, definiu-se que os Serviços de Gerenciamento devem ser disponibilizados por Grupos de MLMs, organizados de forma a fazer a distribuição de tarefas de gerenciamento entre si. Diversos modelos de distribuição de carga foram investigados, foram realizadas avaliações e gráficos comparativos, e foram estabelecidas diretrizes sobre quando e como deve ser aplicado cada modelo, de modo a alcançar sempre o melhor rendimento e a maximização do aproveitamento dos recursos disponíveis ao sistema. A avaliação realizada consistiu na execução de diversas requisições com diferentes números de MLMs usando diferentes algoritmos de distribuição de carga, e na comparação entre a vazão, os tempos de resposta e o tráfego de rede gerados pelos diferentes casos de uso. A implementação desenvolvida neste trabalho demonstrou ser promissora, apresentando resultados bastante satisfatórios com relação aos parâmetros avaliados. / Due to the increasing complexity of computer systems, deep changes have occurred in network management in the past few years. Traditional centralized models have been proved limited, and new network management models are being proposed and investigated. In this scenery, P2P communication models allow for the creation of dynamic and versatile environments, able to solve problems in various computational areas, one of them being network management. The P2P model fits perfectly in the current demands of distributed network management. Starting from the proposed P2P-based network management model, a new P2P-based network management architecture has been developed, focusing on entities like Top-Level (TLM) and Mid-Level (MLM) management peers. With the purpose of making the P2P-based network management real, new building blocks for P2P-based network management systems have been defined. In the present work, an integration of these new building blocks with traditional network management solutions - like SNMP - is presented. One of the main concepts of the proposed architecture is on Management Services, inspired by Web Services and in the service definition of Service Oriented Architectures (SOA). To evaluate this new network management model and its associated architecture, it was necessary to develop a prototype system to be used as platform for development and deployment of Management Services. This prototype was used for evaluation, testing and result analysis. To hold the characteristics of availability and scalability that are inherent to the P2P systems, the Management Services had to be served by MLM groups, organized in a way to distribute the management tasks between them. Several load distribution models were investigated, with evaluation and comparative graphics fulfilled, and some guidelines were established as to when and how each model should be applied to reach the best performance and the maximization of the computational resources available to the system. The evaluation consisted in the execution of several requests in groups with distinct MLM numbers and using distinct load distribution algorithms. Then, the response time and network traffic generated by use cases were compared. We then showed that the developed implementation of our proposal is promising, and presents good results in relation with the evaluated parameters.

Video delivery over the Internet is becoming increasingly popular and comes in many flavors, such as Live Streaming and Video-on-Demand. In the recent years, many peer to peer solutions for Live Streaming and VoD have been proposed as opposed to the centralized solutions that are not scalable due to the high bandwidth requirements. In all existing solutions, Live Streaming and VoD have traditionally and artificially been considered as separate technical problems. We propose an integrated Live Streaming with VoD system that offers the potential for users to watch live TV with short delays. In Live Streaming, peers are interested in the content that is being generated live by the streaming source, unlike VoD in which peers are interested in the content that has been generated from the beginning of the streaming. In this manner, Live nodes can contribute to VoD nodes and send them the pieces they have downloaded since their joining time. In this work, we demonstrate that our system, called Live-VoD, brings out the possibility of having both types of nodes in one system, each being served based on their interest. We propose a P2P Live-VoD protocol for overlay construction based on peer’s upload bandwidth that is built on top of the Gradient topology and an innovative algorithm based on the number of pieces peers can contribute to each other. We also propose an innovative stochastic algorithm for data dissemination based on the rareness of the piece and the requesting node’s download position. Our experiments show that Live-VoD is decentralized, scalable and self-organizing. We also show that even when most of the nodes in the system are VoDs, all VoD nodes regardless of their joining time, manage to download the whole movie with no assistance from the streaming source.

京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第19131号 / 情博第577号 / 新制||情||101(附属図書館) / 32082 / 京都大学大学院情報学研究科通信情報システム専攻 / (主査)教授 高橋 達郎, 教授 守倉 正博, 高橋 豊 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DGAM

In this thesis, we consider a distributed collaborative platform in which each peer hosts his private information, such as the URLs he liked or the news articles that grabbed his interest or videos he watched, on his own machine. Then, without relying on a trusted third party, the peer engages in a distributed protocol, combining his private data with other peers' private data to perform collaborative filtering. The main objective is to be able to receive personalized recommendations or other services such as a personalized distributed search engine. User-based collaborative filtering protocols, which depend on computing user-to-user similarity, have been applied to distributed systems. As computing the similarity between users requires the use of their private profiles, this raises serious privacy concerns. In this thesis, we address the problem of privately computing similarities between peers in collaborative platforms. Our work provides a private primitive for similarity computation that can make collaborative protocols privacy-friendly. We address the unique challenges associated with applying privacy-preserving techniques for similarity computation to dynamic large scale systems. In particular, we introduce a two-party cryptographic protocol that ensures differential privacy, a strong notion of privacy. Moreover, we solve the privacy budget issue that would prevent peers from computing their similarities more than a fixed number of times by introducing the notion of bidirectional anonymous channel. We also develop a heterogeneous variant of differential privacy that can provide different level of privacy to different users, and even different level of privacy to different items within a single user's profile, thus taking into account different privacy expectations. Moreover, we propose a non-interactive protocol that is very efficient for releasing a small and private representation of peers' profiles that can be used to estimate similarity. Finally, we study the problem of choosing an appropriate privacy parameter both theoretically and empirically by creating several inference attacks that demonstrate for which values of the privacy parameter the privacy level provided is acceptable.