As redes atuais de telecomunicações utilizam tecnologias de comutação de pacotes para integração de voz, dados, imagens e outros serviços. O tráfego nessas redes costuma ser feito por meio de tecnologias como o MPLS-TP e com regras heurísticas para a determinação dos melhores caminhos. O uso de boas regras afeta diretamente o desempenho e a segurança da operação. Este trabalho propõe o uso de simulação de baixo custo para prever o comportamento e avaliar regras de escolha de caminhos. Para isso, este trabalho avalia três métodos de seleção de caminhos de LSPs, combinados com duas heurísticas de recuperação, usados em redes MPLS-TP em malha com mecanismos de proteção em malha compartilhada. Os resultados das simulações medem o impacto dos métodos e heurísticas utilizados, demonstrando o quanto uma melhor seleção de caminhos pode contribuir para a redução do uso dos recursos da rede e do número máximo de LSPs afetados em caso de falhas na rede. Os resultados deste trabalho, bem como a técnica de análise proposta, almejam ser uma contribuição para a padronização de regras de seleção de LSPs em redes heterogêneas. / The telecommunications networks nowadays use packet-switching technologies for integration of voice, data, images and other services. The traffic on these networks is usually done through technologies such as MPLS-TP and with heuristic rules to determine the best paths. The use of good rules directly affect the performance and security of operation. This paper proposes the inexpensive use of simulation to predict the behavior and evaluate rules for choosing paths. For this, this study evaluates three methods of selection of LSPs paths, combined with two recovery heuristics, used in MPLS-TP mesh networks with shared mesh protection mechanisms. The results of the simulations measure the impact of the methods and heuristics used, demonstrating how much better path selection can contribute to reducing the use of network resources and the maximum number of LSPs affected in the event of network failures. These results and the proposed analysis technique yearn to be a contribution to the standardization of LSPs selection rules in heterogeneous networks.

In der vorliegenden Arbeit werden praktische Protokolle für spontane drahtlose Multi-Hop Maschennetze vorgestellt, diese betrachten das drahtlose System ganzheitlich und berücksichtigen damit die Besonderheiten des drahtlosen Mediums, wie Fading, Interferenz sowie starke Signaldämpfung aufgrund von Entfernung bzw. Hindernissen. Interferenz ist eine Hauptursache für Paketverlust, Durchsatz und Latenz können durch die gleichzeitige Verwendung mehrerer interferenzfreier Kanäle verbessert werden. In Sensor- bzw. Community-Netzen kommt preiswerte und energiesparende Hardware zum Einsatz, die Verwendung zusätzlicher Antennen bzw. Radios ist deshalb nicht möglich. Andererseits werden aber zukünftige drahtlose Netze eine 100-mal höhere Knotendichte, verglichen mit heutigen Netzen, zeigen. Durch die Ausnutzung der im System inhärent vorliegenden Ressource Nutzer (Multi-User Diversität) werden durch Kooperation virtuelle Multi-Antennen und Multi-Radiosysteme aufgebaut. Aufgrund des großen Abstands zwischen den Knoten erreicht man erstens eine hohe räumliche Diversität und zweitens lassen sich damit auch negative Effekte, wie Interferenz zwischen benachbarten Kanälen, minimieren. Es werden Algorithmen sowohl für die Mediumzugriff- als auch die Routing-Schicht vorgestellt. Da keine spezielle physikalische Schicht notwendig ist, kann IEEE 802.11 verwendet werden. Schließlich kann auch auf die bereits heute verfügbare IEEE 802.11 Hardware, die nur eine Kanalumschaltzeit im Millisekundenbereich erlaubt, zurückgegriffen werden. Die zwei vorgestellten Protokolle eignen sich für Umgebungen mit hoher bzw. geringer Interferenz durch fremde WiFi-Netze. Bezüglich Durchsatz werden moderne Protokolle, wie DSR auf Basis von IEEE 802.11 und ETX-Metrik, um ein Vielfaches übertroffen, außerdem ist die Latenz klein und das TCP/IP-Protokoll kann unverändert verwendet werden. / In this work practical protocols are introduced for spontaneous wireless multi-hop mesh networks which contemplate the wireless system integrally and therefore take into account particular features of the wireless medium, like fading, interference as well as strong signal attenuation due to distance or obstacles. Interference is one of the main causes for packet loss. Throughput and latency can be improved by the simultaneous use of several non-interfering channels. In sensor or community networks inexpensive and energy-saving hardware is used. Additional antennas or radios are impossible therefore; on the other hand future wireless networks will show a 100 times higher node density in comparison with today''s networks, however. By the usage of the resource user (multi-user diversity), that is inherently present in the system virtual multi-antennas and multi-radio systems can be built up by cooperation. Firstly, a high spatial diversity can be achieved due to the large distance between the nodes and secondly, negative effects like interference can be minimized between neighboring channels. Algorithms are introduced both for medium access and routing layer. Since a special physical layer is not required IEEE 802.11 can be used. These days already available 802.11 hardware, which allows a channel switching time in milliseconds, is finally usable. The two protocols introduced here are suitable for environments with a high or low interference caused by foreign WiFi networks. Regarding their performance modern protocols like DSR based on 802.11 and ETX metric are surpassed by far. Moreover, the latency is small and the TCP/IP protocol can be used in its unchanged form.

The super collision between the Internet phenomenon and the wireless communication revolution gives birth to a wealth of novel research problems, design challenges and standardization activities. Within this domain, spontaneous wireless IP networking are probably the most extreme example of new ''particles'' born from the collision. Indeed, these particles defy the laws of the Internet in many ways. The absorption of such peculiar particles in the global IP network has already started thanks to pioneering algorithmic and protocol work -- for instance OLSR -- and through the deployment of wireless mesh networks around the world, such as urban community wireless networks. With the recent revolutions in North Africa, and movements such as Occupy Wall Street, the prospect of spontaneous wireless IP networking has become even more attractive on social and political grounds. Dedicated conferences have recently been organized, and as a result, ambitious, multi-million dollar initiatives have been launched (e.g. the US Government-funded project Commotion Wireless, or the EU-funded initiative CONFINE). However, spontaneous IP wireless networks are not yet widely deployed because pioneer work such as OLSR is vastly insufficient to fully bridge the gap between the Internet and these new networks. This thesis presents work that analyzes this gap and proposes some solutions as to how to bridge it. The focus is put on three domains: a first part presents work in the domain of wireless mesh and ad hoc networks. A second part presents work on sensor networks and in the Internet of Things. And the last part presents work in the domain of delay tolerant networking and vehicular networks.

We study the problem of joint congestion control, routing and MAC layer scheduling in multi-hop wireless mesh networks, where the nodes in the network are subjected to energy expenditure rate constraints. As wireless scenario does not allow all the links to be active all the time, only a subset of given links can be active simultaneously. We model the inter-link interference using the link contention graph. All the nodes in the network are power-constrained and we model this constraint using energy expenditure rate matrix. Then we formulate the problem as a network utility maximization (NUM) problem. We notice that this is a convex optimization problem with affine constraints. We apply duality theory and decompose the problem into two sub-problems namely, network layer congestion control and routing problem, and MAC layer scheduling problem. The source adjusts its rate based on the cost of the least cost path to the destination where the cost of the path includes not only the prices of the links in it but also the prices associated with the nodes on the path. The MAC layer scheduling of the links is carried out based on the prices of the links. The optimal scheduler selects that set of non-interfering links, for which the sum of link prices is maximum. We study the effects of energy expenditure rate constraints of the nodes on the maximum possible network utility. It turns out that the dominant of the two constraints namely, the link capacity constraint and the node energy expenditure rate constraint affects the network utility most. Also we notice the fact that the energy expenditure rate constraints do not affect the nature of optimal link scheduling problem. Following this fact, we study the problem of distributed link scheduling. Optimal scheduling requires selecting independent set of maximum aggregate price, but this problem is known to be NP-hard. We first show that as long as scheduling policy selects the set of non-interfering links, it can not go unboundedly away from the optimal solution of network utility maximization problem. Then we proceed and evaluate a simple greedy scheduling algorithm. Analytical bounds on performance are provided and simulations indicate that the greedy heuristic performs well in practice.

為了降低無線網路基地台後端之backhaul成本及解決Ad hoc網路涵蓋面積問題，無線網狀網路WMNs(Wireless Mesh Networks)因此應運而生。WMNs網路上的節點裝置與Ad hoc網路上的行動裝置對電量消耗及負載的需求是非常不同的，所以在Ad hoc網路上可使用之路由協定在WMNs網路上是無法直接適用的。 在Pure Ad hoc網路上考量Power之MMBCR(Min-Max Battery Cost Routing)及考量Loading之CSLAR(Contention Sensitive Load Aware Routing)等路由協定並沒有考量到WMNs網路上不同元件間的不同特性。有鑑於此，我們著重在Hybrid WMNs網路環境上，並提出了在Mesh Clients及Routers上同時考量Power及Loading的路徑演算法，我們稱之為POLAR。實驗結果顯示我們的路由協定能夠提昇整體的網路效能及延長網路存活時間。 / In order to reduce the backhaul cost and solve Ad hoc network coverage problem, WMNs (Wireless Mesh Networks) arise at the historic moment. The requirements on power efficiency and loading are much different between mesh nodes of WMNs and mobile hosts of ad hoc networks. The routing protocol used in Ad hoc networks would be not suitable in WMN networks. The power-aware routing in MMBCR (Min-Max Battery Cost Routing) and load-aware routing in CSLAR (Contention Sensitive Load Aware Routing) used in pure Ad hoc networks don‘t consider the different characteristics of the components in WMNs. In view of this, we focus on the Hybrid WMNs environment, and propose a combined POwer-Aware with Load-Aware Routing algorithm (Called POLAR) along mesh clients and routers. The experimental results show that our routing protocol can enhance the network efficiency and lengthen the network live time.

Les réseaux maillés sans fil (RMSF), grâce à leurs caractéristiques avantageuses, sont considérés comme une solution efficace pour le support des services de voix, vidéo et de données dans les réseaux de prochaine génération. Le standard IEEE 802.16-d a spécifié pour les RMSF, à travers son mode maillé, deux mécanismes de planifications de transmission de données; à savoir la planification centralisée et la planification distribuée. Dans ce travail, on a évalué le support de la qualité de service (QdS) du standard en se focalisant sur la planification distribuée. Les problèmes du système dans le support du trafic de voix ont été identifiés. Pour résoudre ces problèmes, on a proposé un protocole pour le support de VoIP (AVSP) en tant qu’extension au standard original pour permettre le support de QdS au VoIP. Nos résultats préliminaires de simulation montrent qu’AVSP offre une bonne amélioration au support de VoIP. / Wireless mesh networks (WMNs), because of their advantageous characteristics, are considered as an effective solution to support voice services, video and data in next generation networks. The IEEE 802.16-d specified for WMNs, through its mesh mode, two mechanisms of scheduling data transmissions; namely centralized scheduling and distributed scheduling. In this work, we evaluated the support of the quality of service (QoS) of the standard by focusing on distributed scheduling. System problems in the support of voice traffic have been identified. To solve these problems, we proposed a protocol for supporting VoIP, called Assisted VoIP Scheduling Protocol (AVSP), as an extension to the original standard to support high QoS to VoIP. Our preliminary simulation results show that AVSP provides a good improvement to support VoIP.

In this study, the effect of implementing Network Coding on the aggregated throughput in Wireless Mesh Networks, was examined. Wireless Mesh Networks (WMNs) are multiple hop wireless networks, where routing through any node is possible. The implication of this characteristic, is that messages flow across the points where it would have been terminated in conventional wireless networks. User nodes in conventional wireless networks only transmit and receive messages from an Access Point (AP), and discard any messages not intended for them. The result is an increase in the volume of network traffic through the links of WMNs. Additionally, the dense collection of multiple RF signals propagating through a shared wireless medium, contributes to the situation where the links become saturated at levels below their capacity. The need exists to examine methods that will improve the utilisation of the shared wireless medium in WMNs. Network Coding is a coding and decoding technique at the network level of the OSI stack, aimed to improve the boundaries of saturated links. The technique implies that the bandwidth is simultaneously shared amongst separate message flows, by combining these flows at common intermediate nodes. The number of transmissions needed to convey information through the network, is decreased by Network Coding. The result is in an improvement of the aggregated throughput. The research approach followed in this dissertation, includes the development of a model that investigates the aggregated throughput performance of WMNs. The scenario of the model, followed a typical example of indoors WMN implementations. Therefore, the physical environment representation of the network elements, included an indoors log–distance path loss channel model, to account for the different effects such as: power absorption through walls; and shadowing. Network functionality in the model was represented through a network flow programming problem. The problem was concerned with determining the optimal amount of flow represented through the links of the WMN, subject to constraints pertaining to the link capacities and mass balance at each node. The functional requirements of the model stated that multiple concurrent sessions were to be represented. This condition implied that the network flow problem had to be a multi–commodity network flow problem. Additionally, the model requirements stated that each session of flow should remain on a single path. This condition implied that the network flow problem had to be an integer programming problem. Therefore, the network flow programming problem of the model was considered mathematically equivalent to a multi–commodity integer programming problem. The complexity of multi–commodity integer programming problems is NP–hard. A heuristic solving method, Simulated Annealing, was implemented to solve the goal function represented by the network flow programming problem of the model. The findings from this research provide evidence that the implementation of Network Coding in WMNs, nearly doubles the level of the calculated aggregated throughput values. The magnitude of this throughput increase, can be further improved by additional manipulation of the network traffic dispersion. This is achieved by utilising link–state methods, rather than distance vector methods, to establish paths for the sessions of flow, present in the WMNs. / Thesis (M.Ing. (Computer and Electronical Engineering))--North-West University, Potchefstroom Campus, 2012.

In this study, the effect of implementing Network Coding on the aggregated throughput in Wireless Mesh Networks, was examined. Wireless Mesh Networks (WMNs) are multiple hop wireless networks, where routing through any node is possible. The implication of this characteristic, is that messages flow across the points where it would have been terminated in conventional wireless networks. User nodes in conventional wireless networks only transmit and receive messages from an Access Point (AP), and discard any messages not intended for them. The result is an increase in the volume of network traffic through the links of WMNs. Additionally, the dense collection of multiple RF signals propagating through a shared wireless medium, contributes to the situation where the links become saturated at levels below their capacity. The need exists to examine methods that will improve the utilisation of the shared wireless medium in WMNs. Network Coding is a coding and decoding technique at the network level of the OSI stack, aimed to improve the boundaries of saturated links. The technique implies that the bandwidth is simultaneously shared amongst separate message flows, by combining these flows at common intermediate nodes. The number of transmissions needed to convey information through the network, is decreased by Network Coding. The result is in an improvement of the aggregated throughput. The research approach followed in this dissertation, includes the development of a model that investigates the aggregated throughput performance of WMNs. The scenario of the model, followed a typical example of indoors WMN implementations. Therefore, the physical environment representation of the network elements, included an indoors log–distance path loss channel model, to account for the different effects such as: power absorption through walls; and shadowing. Network functionality in the model was represented through a network flow programming problem. The problem was concerned with determining the optimal amount of flow represented through the links of the WMN, subject to constraints pertaining to the link capacities and mass balance at each node. The functional requirements of the model stated that multiple concurrent sessions were to be represented. This condition implied that the network flow problem had to be a multi–commodity network flow problem. Additionally, the model requirements stated that each session of flow should remain on a single path. This condition implied that the network flow problem had to be an integer programming problem. Therefore, the network flow programming problem of the model was considered mathematically equivalent to a multi–commodity integer programming problem. The complexity of multi–commodity integer programming problems is NP–hard. A heuristic solving method, Simulated Annealing, was implemented to solve the goal function represented by the network flow programming problem of the model. The findings from this research provide evidence that the implementation of Network Coding in WMNs, nearly doubles the level of the calculated aggregated throughput values. The magnitude of this throughput increase, can be further improved by additional manipulation of the network traffic dispersion. This is achieved by utilising link–state methods, rather than distance vector methods, to establish paths for the sessions of flow, present in the WMNs. / Thesis (M.Ing. (Computer and Electronical Engineering))--North-West University, Potchefstroom Campus, 2012.

As redes atuais de telecomunicações utilizam tecnologias de comutação de pacotes para integração de voz, dados, imagens e outros serviços. O tráfego nessas redes costuma ser feito por meio de tecnologias como o MPLS-TP e com regras heurísticas para a determinação dos melhores caminhos. O uso de boas regras afeta diretamente o desempenho e a segurança da operação. Este trabalho propõe o uso de simulação de baixo custo para prever o comportamento e avaliar regras de escolha de caminhos. Para isso, este trabalho avalia três métodos de seleção de caminhos de LSPs, combinados com duas heurísticas de recuperação, usados em redes MPLS-TP em malha com mecanismos de proteção em malha compartilhada. Os resultados das simulações medem o impacto dos métodos e heurísticas utilizados, demonstrando o quanto uma melhor seleção de caminhos pode contribuir para a redução do uso dos recursos da rede e do número máximo de LSPs afetados em caso de falhas na rede. Os resultados deste trabalho, bem como a técnica de análise proposta, almejam ser uma contribuição para a padronização de regras de seleção de LSPs em redes heterogêneas. / The telecommunications networks nowadays use packet-switching technologies for integration of voice, data, images and other services. The traffic on these networks is usually done through technologies such as MPLS-TP and with heuristic rules to determine the best paths. The use of good rules directly affect the performance and security of operation. This paper proposes the inexpensive use of simulation to predict the behavior and evaluate rules for choosing paths. For this, this study evaluates three methods of selection of LSPs paths, combined with two recovery heuristics, used in MPLS-TP mesh networks with shared mesh protection mechanisms. The results of the simulations measure the impact of the methods and heuristics used, demonstrating how much better path selection can contribute to reducing the use of network resources and the maximum number of LSPs affected in the event of network failures. These results and the proposed analysis technique yearn to be a contribution to the standardization of LSPs selection rules in heterogeneous networks.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2015-03-05T15:35:28Z No. of bitstreams: 2 Dissertação - Micael Oliveira Massula Carvalho de Mello - 2014.pdf: 489311 bytes, checksum: 15900b2c2d82201091cb1f73eeb459f4 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2015-03-06T10:37:11Z (GMT) No. of bitstreams: 2 Dissertação - Micael Oliveira Massula Carvalho de Mello - 2014.pdf: 489311 bytes, checksum: 15900b2c2d82201091cb1f73eeb459f4 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2015-03-06T10:37:11Z (GMT). No. of bitstreams: 2 Dissertação - Micael Oliveira Massula Carvalho de Mello - 2014.pdf: 489311 bytes, checksum: 15900b2c2d82201091cb1f73eeb459f4 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2014-12-19 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Wireless Mesh Networks (WMNs) are infrastructures with autonomic properties, such as self-organization and self-recovery, which can be developed with widely available technologies and low cost solutions. Besides their current applications, such as community networks and broad-band Internet access, WMNs can offer contributions in the context of the Internet of Things and help to build robust infrastructures to smart energy networks, among other uses. However, WMNs usually have performance issues due to overload in certain parts of the network and interference in wireless links. In this context, it is important that solutions are used to promote load-balancing and to mitigate interference between wireless links. Research in this area shows that one of the most promising approaches are in the subject of the joint routing and channel assignment. However, most of the previous works depends on the knowledge of the network traffic and handle flows with low granularity. In this thesis, we handle the performance problem in WMNs, in particular those having multiple radios and multiple available channels, using a joint approach, but without the mentioned restrictions. Our proposal is a joint heuristic, whose main contribution is the routing, which pursues the compromise between load-balancing and the path length of the network flows. We have developed our proposal in the Network Simulator 3 (ns-3) and have compared it with other works in literature. We found that our heuristic provides throughput improvements in most of the analyzed scenarios, besides promote greater justice between the flows that compete for resources. / Redes em Malha Sem Fio - Wireless Mesh Networks (WMNs) são infraestruturas com propriedades autonômicas, como auto-organização e autorrecuperação, que podem ser implementadas com tecnologias amplamente disponíveis e de custo acessível. Além de suas aplicações atuais, como redes comunitárias e redes de acesso à Internet, as WMNs podem auxiliar na comunicação de Internet das Coisas e constituir infraestruturas robustas para redes inteligentes de energia, dentre outros usos. No entanto, WMNs geralmente apresentam questões relativas a desempenho devido a fatores como sobrecarga em determinadas partes da rede e interferências nos enlaces sem fio. Nesse contexto, é importante que sejam utilizadas soluções que promovam balanceamento de carga na rede e que minimizem as interferências entre os enlaces sem fio. A pesquisa nessa área tem mostrado que uma das abordagens mais promissoras consiste em tratar de maneira conjunta o roteamento e a atribuição de canais. Porém, a maior parte dos trabalhos dependem de conhecimento prévio do tráfego da rede e tratam fluxos com baixa granularidade. Nesta dissertação, tratamos o problema de desempenho em WMNs, em especial as que possuem múltiplos rádios e múltiplos canais disponíveis, utilizando uma abordagem conjunta, mas sem as restrições anteriores. Nossa proposta é uma heurística conjunta, cuja principal contribuição está no roteamento, o qual persegue um compromisso entre o balanceamento de carga e o comprimento dos caminhos seguidos pelos fluxos. Implementamos nossa proposta no Network Simulator 3 (ns-3) e a comparamos com outros trabalhos da literatura. Verificamos que nossa heurística apresenta ganhos de vazão na maior parte dos cenários avaliados, além de promover maior justiça entre os fluxos que concorrem pelos recursos.