Made available in DSpace on 2014-06-12T15:51:58Z (GMT). No. of bitstreams: 1 license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2008 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / Diversos trabalhos na área de redes dinâmicas têm sido propostos na literatura com o objetivo de prover à arquitetura da Internet o suporte à mobilidade. O problema dessas redes instáveis na Internet consiste em oferecer um conjunto de mecanismo, tais como endereçamento, gerenciamento da informação e encaminhamento da informação, que suportem informação e entidade (Sistema Autônomo, Provedor de Serviços na Internet e Clientes) móveis. Nesse contexto, alguns trabalhos para arquitetura da Internet têm proposto uma maneira de separar a localização (atualmente o IP) e o nome identificador, devido ao forte relacionamento entre o IP e o nome. Em geral, eles propõem uma abordagem de roteamento na camada overlay para separar essas informações. Outros trabalhos acreditam que este desacoplamento não é suficiente para solucionar os problemas de mobilidade, desde que a dinamicidade gera muitas mensagens de controle e atualizações do vínculo entre o IP e o nome. Por essa razão, os pesquisadores também têm proposto novos modelos para gerenciar a camada overlay. Uma das contribuições deste trabalho é a proposta de uma solução para arquitetura da Internet denominada Stable Society que adota a abordagem de papéis. Um papel é uma unidade funcional que é utilizada para organizar a comunicação. Um importante diferencial da proposta é que além de desvincular o nome e a localização, ela também oferece soluções para os problemas relacionados a estruturação e manutenção da camada overlay. Além disso, este trabalho define quatro papéis: o mensageiro encaminha os dados dentro da sociedade; o guarda é a entidade mais estável para encaminhar mensagens entre as sociedades; o operário armazena informações; e o líder estrutura e gerencia a rede overlay. Reduzindo o escopo para a implementação desta dissertação de mestrado, o mensageiro e o guarda foram considerados como a camada de rede sem distinção de estabilidade, desde que o fornecimento de um mecanismo de gerenciamento do overlay de roteamento foi o objetivo do trabalho. Portanto, como prova do conceito apresentado pela proposta, os líderes e operários foram implementados, porque eles agem de maneira independente de tecnologia de acesso e são fundamentais para solucionar o problema da instabilidade nos processos de armazenamento e descoberta da informação. Como resultado, um novo algoritmo denominado Stable Society model over Distributes Hash Table (SSDHT) foi proposto. Além disso, este algoritmo foi comparado com outras soluções DHT (Chord). Os resultados mostraram que o SSDHT é um bom algoritmo, principalmente quando se aumenta a instabilidade (carga do tráfego, grau de mobilidade e tamanho da rede). Por exemplo, a taxa de mensagens entregue com sucesso foi acima de 90% quando a carga de tráfego, o grau de mobilidade e o tamanho da rede foram variados

Despite the world-changing success of the Internet, shortcomings in its routing and forwarding system have become increasingly apparent. One symptom is an escalating tension between users and providers over the control of routing and forwarding of packets: providers understandably want to control use of their infrastructure, and users understandably want paths with sufficient quality-of-service (QoS) to improve the performance of their applications. As a result, users resort to various “hacks” such as sending traffic through intermediate end-systems, and the providers fight back with mechanisms to inspect and block such traffic. To enable users and providers to jointly control routing and forwarding policies, recent research has considered various architectural approaches in which provider- level route determination occurs separately from forwarding. With this separation, provider-level path computation and selection can be provided as a centralized service: users (or their applications) send path queries to a path service to obtain provider- level paths that meet their application-specific QoS requirements. At the same time, providers can control the use of their infrastructure by dictating how packets are forwarded across their network. The separation of routing and forwarding offers many advantages, but also brings a number of challenges such as scalability. In particular, the path service must respond to path queries in a timely manner and periodically collect topology information containing load-dependent (i.e., performance) routing information. We present a new design for a path service that makes use of expensive pre- computations, parallel on-demand computations on performance information, and caching of recently computed paths to achieve scalability. We demonstrate that, us- ing commodity hardware with a modest amount of resources, the path service can respond to path queries with acceptable latency under a realistic workload. The ser- vice can scale to arbitrarily large topologies through parallelism. Finally, we describe how to utilize the path service in the current Internet with existing Internet applica- tions.

Dans cette thèse nous avons tout d'abord abordé le problème de la stabilité des réseaux. Dans ce but, nous avons premièrement développé une méthode temps-réelle définissant des indicateurs de stabilités pour un flux quelconque de messages observé. Puis, nous nous sommes intéressé au cas particulier des flux d'alarmes, qui constituent actuellement un enjeu pour les réseaux du futur. Une méthode créant un graphe statistique de corrélation des alarmes fut développée. Nous avons montré que l'utilisation de la méthode précédente est très utile. Dans un second temps nous avons abordé les problèmes de paramétrisation des réseaux. Nous avons exploré une piste visant à représenter le comportement du protocole OSPF par un réseau de Petri temporisé. Alors, une heuristique à été crée afin de définir, le mieux possible certains paramètres du protocole modulant les arrivées de messages dans le réseau. Nous avons utilisé la simulation de réseau de Petri afin d'observer l'effet de l'heuristique sur le comportement du protocole OSPF. Finalement, nous avons étudié, à l'aide de la théorie du Network Calculus, les politiques de services à priorités fixes. Nous avons défini un programme linéaire, qui étant donné une paramétrisation des arrivées de message et des services, calcule une borne maximale du délai d'un flux observé dans un réseau de topologie quelconque.

Automated decision making is becoming the norm across large parts of society, which raises interesting liability challenges when human control over technical systems becomes increasingly limited. This article defines "quasi-automation" as inclusion of humans as a basic rubber-stamping mechanism in an otherwise completely automated decision-making system. Three cases of quasi- automation are examined, where human agency in decision making is currently debatable: self- driving cars, border searches based on passenger name records, and content moderation on social media. While there are specific regulatory mechanisms for purely automated decision making, these regulatory mechanisms do not apply if human beings are (rubber-stamping) automated decisions. More broadly, most regulatory mechanisms follow a pattern of binary liability in attempting to regulate human or machine agency, rather than looking to regulate both. This results in regulatory gray areas where the regulatory mechanisms do not apply, harming human rights by preventing meaningful liability for socio-technical decision making. The article concludes by proposing criteria to ensure meaningful agency when humans are included in automated decision-making systems, and relates this to the ongoing debate on enabling human rights in Internet infrastructure.

Redes definidas por software (SDN) são uma abordagem recente para o projeto e operação de redes de computadores. Este paradigma é empregado com sucesso em cenários de datacenter, no entanto redes de acesso definidas por software (SDAN) ainda são raras em operadoras de telefonia e provedores de Internet. Isso deve-se em grande parte à inexistência de uma arquitetura de referência, algo que diversos projetos tentaram suprir nos últimos anos. Independente da vertente escolhida, a opção por uma mudança tão disruptiva como o SDN precisa ser justificada. Modelos tecno-econômicos são comumente utilizados para estimar o impacto da mudança na rentabilidade da operação. O custo total de propriedade (TCO) é uma métrica utilizada para esse fim. O presente trabalho desenvolveu um modelo simplificado de comparação de arquiteturas de rede, que diferentemente dos demais, tem foco nos serviços oferecidos ao assinante e no custo de gerenciamento dos mesmos. A análise é realizada em duas dimensões. Na primeira o esforço de operar a rede é estimado através de uma análise qualitativa, de forma similar ao realizado por outros modelos. O segundo eixo é a quantidade de recursos exigida para provisionar e monitorar cada serviço. Essa estimativa é gerada através do uso de simulação de tempo discreto dos elementos e protocolos relevantes. A combinação das duas análises permite identificar as tendências de comportamento dos serviços geradas pela adoção de uma nova arquitetura de rede, e avaliar a conveniência dessa migração. O uso de simulação neste trabalho demandou a construção de modelos dos equipamentos e protocolos envolvidos. Elegeu-se o pacote NS-3 como ferramenta de simulação. Definir e implementar modelos para todos os serviços analisados poderia tornar-se tão oneroso quanto as técnicas que desejávamos suplantar, e por isso utilizou-se uma abordagem indireta. São simulados apenas os componentes essenciais, e os custos de cada serviço são inferidos a partir deles. O modelo de rede SDAN utilizado, denominado SDCN, é inspirado no SplitArchitecture, proposto pelo projeto SPARC. / Software defined networks are a novel approach to design and operation of computer networks. Although this paradigm is employed successfully in many data-centers and campus, software defined access networks (SDAN) are still in their infancy. Carriers and ISPs have not converged on a standard architecture to build their infrastructure upon, a problem many initiatives are trying to solve. Regardless of the chosen model, the option for such a disruptive change as SDN needs to be justified. Techno-economic models are commonly used to estimate the impact of a change in the operation. The Total Cost of Ownership (TCO) is a metric commonly used for this purpose. The present work developed a simplified evaluation model for network architectures, which focuses on the services offered to the subscriber and on the cost of managing them. The analysis is performed in two dimensions. In the first, the effort to operate the network is estimated through a qualitative analysis, similar to the one performed by other existing models. The second axis is the amount of resources required to provision and monitor each service. This estimation is produced through the use of discrete time simulation of selected elements and protocols. The combination of the analyzes allows us to identify the behavioral trends provoked by the adoption of a new network architecture, and to evaluate the convenience of such migration. The simulation in this work demanded models for the equipment and protocols involved. The package NS-3 was the chosen simulation tool. Defining and implementing models for all services analyzed could become as costly as the techniques we wish to overcome, so an indirect approach has been used. Only the essential components are simulated, and the costs of each service are inferred from them. The SDAN model evaluated in this work, called SDCN, is a simplification of the SplitArchitecture proposed by the SPARC project.

La géométrie stochastique est un outil puissant pour modéliser des grands réseaux sans fil avec une grande variation de la position des nœuds. Dans ce cadre, une hypothèse courante est que l'emplacement des nœuds forme une réalisation d'un processus ponctuel de Poisson (PPP). En utilisant les résultats disponibles concernant la transformée de Laplace du processus bruit de grenaille associé à des PPPs, on peut obtenir des solutions de forme fermée des métriques de performance de réseau telles que la probabilité d'accès au médium (MAP), la probabilité de couverture (COP) et de la densité spatiale de débit (SDT). Cependant, dans de nombreux déploiements de réseaux sans fil, il y a un mécanisme de détection des porteuses(CS) pour empêcher nœuds qui sont trop proches les uns des autres de transmettre en même temps. Dans ces réseaux, le processus des nœuds qui transmettent simultanément à tout moment ne forme plus une réalisation d'un PPP, ce qui rend l'analyse des performances des réseaux dans ces cas, un problème difficile. L'objectif de cette thèse est d'étudier ce problème dans deux directions. Dans la première direction, nous proposons un cadre complet de la géométrie stochastique qui utilise des processus ponctuels avec exclusion pour modéliser des transmetteurs dans différents types de réseaux sans fil avec un mécanisme de CS. Les réseaux considérés sont les réseaux à accès multiple en cherchant à détecter une porteuse (Carrier Sensing Multiple Access-CSMA) avec un mécanisme de détection (CS) parfait, les réseaux de radio-communications cognitifs où les utilisateurs secondaires utilisent la détection de porteuse pour détecter les utilisateurs principaux et les réeseaux CSMA avec un CS imparfait. Pour les deux premiers cas, nous dérivons des approximations des métriques de performances principales de réseau, c'est-à-dire la MAP, la COP et la SDT. Pour le dernier cas, nous donnons des bornes sur la densité spatiale critique des nœuds où CSMA commence à se comporter comme ALOHA (c'est-à-dire le processus de des nœuds qui transmettent simultanément dans le réseau forme une réalisation d'un PPP). Bien que ce phénomène ait été étudié auparavant par simulations, aucun résultat d'analyse n'a été connu à de notre connaissance. Dans la seconde direction, nous étudions la distribution processus ponctuel s' associés avec les classique Matérn modèles de type II et type III [Matérn 68]. Ce sont les deux modèles utilisés pour modéliser les réseaux CSMA avec un CS parfait. Bien que ces modèles aient été introduits il y a longtemps et qu'ils aient de nombreuses applications dans de nombreuses disciplines, la distribution de leurs processus ponctuels associés et la transformation de Laplace des processus bruit de grenaille correspondant est encore un problème ouvert. Nous montrons ici que la fonctionnelle génératrice des probabilités de ces processus ponctuels, lorsqu'elle est correctement paramétrée, est la solution unique de certain système d'équations différentielles. Grace à l'utilisation de ce système d'équations, on peut obtenir une borne inférieure et une borne supérieure de ces fonctionnelle. Ce résultat peut ensuite être appliqué au cadre de la géométrie stochastique mentionnée ci-dessus pour mieux connecter les cadres d'analyse mathématiques et les déploiements de réseaux pratiques.

Pour avoir une idée sur la qualité du réseau, la majorité des acteurs concernés (opérateurs réseau, fournisseurs de service) se basent sur la Qualité de Service (Quality of Service). Cette mesure a montré des limites et beaucoup d'efforts ont été déployés pour mettre en place une nouvelle métrique qui reflète, de façon plus précise, la qualité du service offert. Cette mesure s'appelle la qualité d'expérience (Quality of Experience). La qualité d'expérience reflète la satisfaction de l'utilisateur par rapport au service qu'il utilise. Aujourd'hui, évaluer la qualité d'expérience est devenu primordiale pour les fournisseurs de services et les fournisseurs de contenus. Cette nécessité nous a poussés à innover et concevoir des nouvelles méthodes pour estimer la QoE. Dans cette thèse, nous travaillons sur l'estimation de la QoE (1) dans le cas des communications Voix sur IP et (2) dans le cas des services de diffusion Vidéo sur IP. Nous étudions les performances et la qualité des codecs iLBC, Speex et Silk pour la VoIP et les codecs MPEG-2 et H.264/SVC pour la vidéo sur IP. Nous étudions l'impact que peut avoir la majorité des paramètres réseaux, des paramètres sources (au niveau du codage) et destinations (au niveau du décodage) sur la qualité finale. Afin de mettre en place des outils précis d'estimation de la QoE en temps réel, nous nous basons sur la méthodologie Pseudo-Subjective Quality Assessment. La méthodologie PSQA est basée sur un modèle mathématique appelé les réseaux de neurones artificiels. En plus des réseaux de neurones, nous utilisons la régression polynomiale pour l'estimation de la QoE dans le cas de la VoIP.

La mobilité est le caractère ou la propriété d'un objet qui a une capacité ou une possibilité de se mouvoir ou d'être mû. Elle caractérise toutes choses qui changent rapidement de forme, d'aspect ou qui est instable, variable ou fluctuant dans le temps et l'espace. L'introduction de la mobilité dans les réseaux a marqué une étape dans la description et la mise en place de systèmes communicants devant tenir compte de la mobilité d'une ou plusieurs entités composant ce système. L'évolution des paradigmes de communication actuels montre qu'il est de plus en plus difficile de concevoir un système de communication intégrant l'utilisateur final sans parler de mobilité. A partir du moment où l'on considère que la mobilité existe dans les réseaux qu'elle soit physique comme par exemple avec déplacement physique d'une entité ou logique avec le déplacement d'une ressource ou d'un service, les communications dans ces réseaux doivent tenir compte de cette mobilité. Les protocoles de communications doivent donc prendre en compte l'instabilité, la variabilité et la fluctuation imposées par la mobilité de certaines entités composants le réseau. C'est ainsi que beaucoup de protocoles de communications, surtout les protocoles pour les réseaux ad hoc, ont été conçus et évalués pour et selon leur résistance à la mobilité comme préconisé par Corson et Macker dans la RFC 2501. Au début des années 2000, des travaux montrent que la mobilité n'a pas que des inconvénients en soulignant que la mobilité permet d'augmenter la capacité, la sécurité et les zones couvertes. Ces articles et bien d'autres soulèvent deux points importants: (i) L'apport de la mobilité décrite dans ces articles concernent des services ou des fonctionnalités de niveau application si l'on s'en réfère au modèle OSI et (ii) la mobilité considérée est une mobilité subie par des entités composant le réseau. Les deux points soulevés précédemment seront abordés suivant différents angles ici. Par rapport au premier point les résultats que je montre ici considèrent deux aspects. Le premier aspect se concentre sur les apports de la mobilité au niveau application et plus spécifiquement au niveau de la couverture dans les réseaux de capteurs. Le deuxième aspect considère l'utilisation de la mobilité comme une primitive de réseau et utilise celle-ci pour augmenter les performances de la pile protocolaire. Concernant ces deux points et contrairement à la majorité des travaux de la littérature, la mobilité considérée est une mobilité contrôlée. Cet aspect permet entre autre de contrôler ou d'anticiper l'instabilité, la variabilité et la fluctuation du réseau mais aussi de maîtriser la couverture et la topologie dans les réseaux de capteurs. L'utilisation de la mobilité contrôlée pour les applications de réseau de capteurs et pour augmenter la qualité de service de la pile protocolaire sont les deux contributions qui sont abordés ici. Dans ce cadre, des algorithmes exploitant la mobilité contrôlée sont conçues et des propriétés sur ses algorithmes sont prouvées. De plus, des évaluations sur des plate-formes de robots mobiles montrent la faisabilité des ces algorithmes dans un cadre réel.

Les villes du futur et actuelles sont de plus en plus connectées. Les relèves de compteur électrique, de gaz et d'eau se font de plus en plus à distance et sans-fil. Les luminaires des villes deviennent intelligents et communiquent pour économiser l'énergie et offrir un éclairage adapté. Les engins de ramassage des ordures communiqueront bientôt avec les poubelles afin d'anticiper les tournées de ramassage et de mieux connaître le contenu des containers. Pour des questions de coûts et de rapidité de déploiement, ces réseaux sont souvent sans infrastructure. Par ailleurs, pour les mêmes raisons, chaque nœud du réseau puise son énergie dans une batterie donc la capacité est limitée. Il convient donc pour ces réseaux particuliers, déployés dans un environnement contraint, de trouver des solutions d'organisation et de communication adaptées. À travers cette thèse je propose d'étudier la problématique des réseaux sans-fil multi-sauts dans les villes intelligentes. J'étudie dans un premier temps l'importance et l'impact de la topologie sur les performances réseau. Plus précisément, au travers de simulations et d'études expérimentales, je démontre que le placement des nœuds impacte les performances des algorithmes et que, par conséquent, il est nécessaire d'étudier les algorithmes pour réseaux de capteurs sans-fil sur des topologies qui correspondent à l'application ciblée. Je propose ensuite une famille d'algorithmes de clustering pour réseaux de capteurs sans-fil permettant d'optimiser la durée de vie du réseau. L'hypothèse clé de ces algorithmes est qu'un chef de cluster (cluster-head ) consomme plus d'énergie qu'un nœud sans rôle particulier. En effet, le cluster-head se voit souvent attribuer des tâches supplémentaires telles que l'agrégation de données et la transmission à un nœud puits, plus lointain donc plus coûteux à joindre. Cette famille d'algorithmes nommée BLAC permet de créer des clusters multi-sauts dans lesquels chaque tête de cluster est la racine d'un arbre qui compose le cluster. Dans chaque cluster, les données sont acheminées vers le cluster-head grâce à un gradient routing. L'idée principale de ces algorithmes est que le rôle de cluster-head doit être attribué en fonction du niveau d'énergie des nœuds et de leur voisinage. Ces algorithmes ont été testés grâce à des simulations sur des topologies de villes réalistes avec des paramètres de simulation tirés du monde réel. Enfin, je propose un algorithme de routage pour des réseaux de villes intelligentes à large échelle. Cet algorithme repose sur l'hypothèse que seulement certains nœuds du réseau ont une connaissance de leur position. Cette position peut être acquise parce que ces nœuds sont équipés d'une puce de localisation (telle que le GPS) ou parce qu'ils sont fixes et configurés au moment du déploiement avec leur position pré-programmée. Cet algorithme epose sur la combinaison de deux techniques de routage, classique et géographique : AODV et Greedy geographic routing. Je montre qu'il est possible d'obtenir des performances proches des algorithmes de routage géographique alors même qu'un sous ensemble des nœuds du réseau n'a pas connaissance de sa position.

La cohabitation de plusieurs services différents sur un même réseau soulève de nombreux problèmes pour la gestion et la conception de réseau de télécommunication. L'introduction de mécanismes "intelligents " dans les réseaux multiservices permet de surmonter la difficulté de mettre en place des méthodes plus traditionnelles pour prendre en compte toute la complexité générée par la multiplication des services. Dans ce contexte, nous nous intéressons au problème de l'évaluation de performance dans les réseaux à l'état stationnaire, et plus spécifiquement l'évaluation des critères de qualité de service (QoS). Au lieu d'essayer de modéliser tous les mécanismes d'un routeur pour formaliser certains critères de QoS, nous proposons d'utiliser les capacités d'apprentissage et de généralisation des réseaux de neurones pour apprendre cette QoS à partir d'observations du système. Nous proposons ainsi des modèles neuro-mimétiques de différents critères de la QoS d'un noeud du réseau qui s'appuient sur une description statistique relativement simple des trafics incidents. Nous avons étudié l'apprentissage de plusieurs critères de qualité de service à partir de simulations à évènements discrets dans le cas de files d'attente élémentaires et de files d'attente à serveur partagé qui modélisent la différentiation de services dans les routeurs IP ou MPLS. Nous généralisons ensuite cette approche pour effectuer l'estimation de la QoS le long d'un chemin et proposons pour cela une coopération distribuée de modèles neuronaux. Les réseaux de neurones sont chargés d'estimer à la fois les critères de qualité de service et une description du trafic de sortie. Ce schéma couplé à un protocole de type RSVP permettrait à terme de propager les estimations le long du chemin pour établir une estimation de la QoS de bout en bout. Nous nous intéressons enfin au problème de routage optimal sous contraintes de QoS de bout en bout. Nous présentons une formalisation multiflot permettant de mettre en place une stratégie de résolution de type déviation de flot qui s'appuie sur une approche de type lagrangien augmenté pour relâcher les contraintes de QoS. Cette stratégie permet d'obtenir un optimum local réalisable. Nous proposons ensuite de remplacer l'approximation M/M/1 traditionnellement utilisée dans les modèles de multiflot par un modèle par réseaux de neurones de la QoS, plus réaliste notamment dans le cas de la différentiation de service. Toutefois il est nécessaire de garantir la croissance des fonctions évaluations pour assurer la validité du schéma d'optimisation. Cette monotonie peut être imposée lors de l'apprentissage du modèle neuronal par l'ajout de contraintes sur les dérivées premières. Nous avons développé ainsi un algorithme d'apprentissage sous contraintes qui impose la monotonie dans les réseaux de neurones feed-forward en utilisant des méthodes classiques de l'optimisation nonlinéaire sous contraintes.