Recently, erasure networks have received significant attention in the literature as they are used to model both wireless and wireline packet-switched networks. Many packet-switched data networks like wireless mesh networks, the Internet, and Peer-to-peer networks can be modeled as erasure networks. In any erasure network, path diversity works by setting up multiple parallel connections between the end points using the topological path redundancy of the network. Our analysis of diversity over erasure networks studies the problem of rate allocation (RA) across multiple independent paths, coding over erasure channels, and the trade-off between rate and diversity gain in three consecutive chapters. In the chapter 2, Forward Error Correction (FEC) is applied across multiple independent paths to enhance the end-to-end reliability. We prove that the probability of irrecoverable loss (P_E) decays exponentially with the number of paths. Furthermore, the RA problem across independent paths is studied. Our objective is to find the optimal RA, i.e. the allocation which minimizes P_E. Using memoization technique, a heuristic suboptimal algorithm with polynomial runtime is proposed for RA over a finite number of paths. This algorithm converges to the asymptotically optimal RA when the number of paths is large. For practical number of paths, the simulation results demonstrate the close-to-optimal performance of the proposed algorithm. Chapter 3 addresses the problem of lower-bounding the probability of error (PE) for any block code over an input-independent channel. We derive a lower-bound on PE for a general input-independent channel and find the necessary and sufficient condition to meet this bound with equality. The rest of this chapter applies this lower-bound to three special input-independent channels: erasure channel, super-symmetric Discrete Memoryless Channel (DMC), and q-ary symmetric DMC. It is proved that Maximum Distance Separable (MDS) codes achieve the minimum probability of error over any erasure channel (with or without memory). Chapter 4 addresses a fundamental trade-off between rate and diversity gain of an end-to-end connection in erasure networks. We prove that there exist general erasure networks for which any conventional routing strategy fails to achieve the optimum diversity-rate trade-off. However, for any general erasure graph, we show that there exists a linear network coding strategy which achieves the optimum diversity-rate trade-off. Unlike the previous works which suggest the potential benefit of linear network coding in the error-free multicast scenario (in terms of the achievable rate), our result demonstrates the benefit of linear network coding in the erasure single-source single-destination scenario (in terms of the diversity gain).

Recently, erasure networks have received significant attention in the literature as they are used to model both wireless and wireline packet-switched networks. Many packet-switched data networks like wireless mesh networks, the Internet, and Peer-to-peer networks can be modeled as erasure networks. In any erasure network, path diversity works by setting up multiple parallel connections between the end points using the topological path redundancy of the network. Our analysis of diversity over erasure networks studies the problem of rate allocation (RA) across multiple independent paths, coding over erasure channels, and the trade-off between rate and diversity gain in three consecutive chapters. In the chapter 2, Forward Error Correction (FEC) is applied across multiple independent paths to enhance the end-to-end reliability. We prove that the probability of irrecoverable loss (P_E) decays exponentially with the number of paths. Furthermore, the RA problem across independent paths is studied. Our objective is to find the optimal RA, i.e. the allocation which minimizes P_E. Using memoization technique, a heuristic suboptimal algorithm with polynomial runtime is proposed for RA over a finite number of paths. This algorithm converges to the asymptotically optimal RA when the number of paths is large. For practical number of paths, the simulation results demonstrate the close-to-optimal performance of the proposed algorithm. Chapter 3 addresses the problem of lower-bounding the probability of error (PE) for any block code over an input-independent channel. We derive a lower-bound on PE for a general input-independent channel and find the necessary and sufficient condition to meet this bound with equality. The rest of this chapter applies this lower-bound to three special input-independent channels: erasure channel, super-symmetric Discrete Memoryless Channel (DMC), and q-ary symmetric DMC. It is proved that Maximum Distance Separable (MDS) codes achieve the minimum probability of error over any erasure channel (with or without memory). Chapter 4 addresses a fundamental trade-off between rate and diversity gain of an end-to-end connection in erasure networks. We prove that there exist general erasure networks for which any conventional routing strategy fails to achieve the optimum diversity-rate trade-off. However, for any general erasure graph, we show that there exists a linear network coding strategy which achieves the optimum diversity-rate trade-off. Unlike the previous works which suggest the potential benefit of linear network coding in the error-free multicast scenario (in terms of the achievable rate), our result demonstrates the benefit of linear network coding in the erasure single-source single-destination scenario (in terms of the diversity gain).

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-05-31T17:34:37Z No. of bitstreams: 1 thiagoboubeecardozo.pdf: 664105 bytes, checksum: c76b7de470f214d95d3054d0ac7b8232 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-06-01T11:40:26Z (GMT) No. of bitstreams: 1 thiagoboubeecardozo.pdf: 664105 bytes, checksum: c76b7de470f214d95d3054d0ac7b8232 (MD5) / Made available in DSpace on 2017-06-01T11:40:26Z (GMT). No. of bitstreams: 1 thiagoboubeecardozo.pdf: 664105 bytes, checksum: c76b7de470f214d95d3054d0ac7b8232 (MD5) Previous issue date: 2013-05-27 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A Internet é um sistema em contínua evolução. Nesta dissertação, é caracterizada e analisada a recente evolução da conectividade fim-a-fim da Internet, comparando métricas importantes ao desempenho fim-a-fim de dois períodos distintos separados por 5 anos. Os resultados mostram que a distribuição do tamanho médio dos caminhos se mantém pouco alterada de 2006 para 2011, mas a distribuição do atraso acabou piorando, com um aumento de 45% no atraso dos caminhos de 2006 para 2011. Isso afeta diretamente o desempenho e degrada a experiência do usuário. Além disso, é mostrado que a diversidade de caminhos diminuiu e, com isso, os caminhos distintos ficaram um pouco mais similares. Esse resultado tem um impacto direto nos algoritmos de roteamento que tentam explorar a diversidade de caminhos para uma maior tolerância a falhas. Depois foi estudado mais a fundo o fenômeno conhecido como bufferbloat, que é uma das possíveis causas do aparente aumento da latência. Os resultados mostraram que filas muito grandes podem impactar fortemente no desempenho da rede, mas também indicaram que provavelmente o problema não irá ocorrer em máquinas Unix Like com as configurações padrão. / The Internet is a system under continuous evolution. In this dissertation, it is characte rized and analyzed the recent end-to-end connectivity evolution of the Internet, comparing key end-to-end performance metrics from two distinct periods separated by five years. The findings show that the average path length distribution remains virtually unchanged from 2006 to 2011, but the delay distribution actually became worse, with a 45% increase in path delay from 2006 to 2011. This directly affects network performance and degrades user experience. Furthermore, it is shown that path diversity decreased, and accordingly, distinct paths became slightly more similar. This result has a direct impact on routing algorithms that try to explore path diversity to become more fault-tolerant. Later it was studied more deeply the phenomenon known as bufferbloat, which is one of the possible causes of the apparent increase of latency. The results show that large buffers can strongly degrade the network performance, but they also show that the problem is not likely to occur in Unix Like machines with default settings.