There is a high degree of uncertainty regarding the nature of traffic on future integrated service networks. This uncertainty motivates the use of adaptive resource allocation policies that can take advantage of the statistical fluctuations in the traffic demands. The adaptive control mechanisms must be 'lightweight', in terms of their overheads, and scale to potentially large networks with many traffic flows. Adaptive routing is one form of adaptive resource allocation, and this thesis considers the application of Stochastic Learning Automata (SLA) for distributed, lightweight adaptive routing in future integrated service communication networks. The thesis begins with a broad critical review of the use of Artificial Intelligence (AI) techniques applied to the control of communication networks. Detailed simulation models of integrated service networks are then constructed, and learning automata based routing is compared with traditional techniques on large scale networks. Learning automata are examined for the 'Quality-of-Service' (QoS) routing problem in realistic network topologies, where flows may be routed in the network subject to multiple QoS metrics, such as bandwidth and delay. It is found that learning automata based routing gives considerable blocking probability improvements over shortest path routing, despite only using local connectivity information and a simple probabilistic updating strategy. Furthermore, automata are considered for routing in more complex environments spanning issues such as multi-rate traffic, trunk reservation, routing over multiple domains, routing in high bandwidth-delay product networks and the use of learning automata as a background learning process. Automata are also examined for routing of both 'real-time' and 'non-real-time' traffics in an integrated traffic environment, where the non-real-time traffic has access to the bandwidth 'left over' by the real-time traffic. It is found that adopting learning automata for the routing of the real-time traffic may improve the performance to both real and non-real-time traffics under certain conditions. In addition, it is found that one set of learning automata may route both traffic types satisfactorily. Automata are considered for the routing of multicast connections in receiver-oriented, dynamic environments, where receivers may join and leave the multicast sessions dynamically. Automata are shown to be able to minimise the average delay or the total cost of the resulting trees using the appropriate feedback from the environment. Automata provide a distributed solution to the dynamic multicast problem, requiring purely local connectivity information and a simple updating strategy. Finally, automata are considered for the routing of multicast connections that require QoS guarantees, again in receiver-oriented dynamic environments. It is found that the distributed application of learning automata leads to considerably lower blocking probabilities than a shortest path tree approach, due to a combination of load balancing and minimum cost behaviour.

The problem of multicasting in wireless multihop networks was studied in this dissertation. Nodes in the multicast routing structures were classified into different classes based on their roles in the multicast routing structures. Optimal multicast routing strategies for different classes were analyzed using the most accurate interference model. Based on the analyses, two algorithms to create interference-aware multicast routing tree and three algorithms to create interference-aware multicast routing mesh were proposed. The proposed multicast routing structures were evaluated using wireless network simulations. To improve the credibility of the wireless network simulations, a frame-level bursty link model was proposed and implemented in ns-3 network simulator. The results showed that, by taking interference into account when building multicast routing structures, the proposed multicast routing structures provided improved performance over other multicast routing structures that do not consider wireless interference when building multicast routing structures.

We propose a novel multicast routing protocol, called adaptive multicast routing protocol for MANETs (Mobile ad hoc routing protocol). Multicast routing protocols can be classified two types according the structure used to establish route. Existing protocols are either tree-based or mesh-based. In mesh-based routing protocols, a reliable protocol ODMRP was proposed. In ODMRP, each sender has to broadcast control packet periodically in order to build mesh. But with an increase of number of senders, control overhead causes reliability reduced because of a large amount of overhead and collisions. Hence, ODMRP is not work well in this case. We proposed our scheme to aim at the drawback of ODMRP. We use packet delivery ratio (PDR) to determine if the load of network is congestion. When packet delivery ratio is high, it means that the network traffic load is low, and vice versa. We determine whether a sender broadcasts Join-Query control packet or not according to packet delivery ratio. As packet delivery ratio is decrease, a sender does not broadcast Join-Query as far as it can in order to avoid collisions. However the packet delivery ratio is increase, senders have strong probability to broadcast Join-Query to establish mesh nodes. We can improve reliability and reduce overhead is caused by control packets with this way.

Support of multicast routing and its implementation is one of the main goals in nowadays computer networks. Adapting new technology could be often challenging and connected with difficulties. For this reason its better to try it in some simulating enviroment and implement it only after successful results of tests and simulations. The aim of this diploma thesis is to familiarize the reader with the multicast routing, describe the possibilities of network testing in OMNeT++ and come up with new multicast routing framework for this discrete simulation tool.

Au cours des dernières années, le trafic réseau nécessitant une qualité de service (QoS) a augmenté de façon exponentielle. Dans cette thèse, notre objectif est de trouver des routages dans les réseaux câblés et sans fil en prenant en compte les contraintes liées à la QoS et en minimisant le coût de la communication. Nous nous intéressons tout d’abord à la résolution du problème du chemin multi-contraint (MCP) pour lequel un algorithme exact efficace est proposé. Cet algorithme permet d'améliorer le temps d'exécution tout en maintenant la qualité de la solution. En ce qui concerne le problème de la diffusion multipoint (multicast) multi-contraint de coût minimal (MCMCM), une nouvelle formulation utilisant la Programmation Linéaire en Nombres Entiers est proposée. Elle permet de calculer les hiérarchies optimales, structures les plus pertinentes pour résoudre de manière exacte le problème MCMCM. Un algorithme de prétraitement efficace est également conçu pour accélérer le temps de résolution dans les réseaux de grande taille. En ce qui concerne le problème du routage avec QoS dans les « Low Power et Lossy Networks » (LLN), une solution basée sur une nouvelle fonction objective est présentée. Cette solution minimisant une longueur non linéaire est la première à prendre en compte un nombre quelconque de contraintes pour le routage avec QoS. Nous avons conçu un algorithme exact et deux algorithmes de routage heuristique pour résoudre ce problème dans les réseaux LLN avec QoS. / In recent years, the network traffic requiring Quality of Service (QoS) has been growing explosively. In this thesis, we study the multi-constrained QoS routing in networks. The objective is to find routes in wired and wireless networks taking into account constraints related to the QoS and minimizing the cost of the communication. We present several propositions. To solve the Multi-Constrained Path problem (MCP), an efficient exact algorithm is proposed. This algorithm is shown to be able to improve the execution time while maintaining the quality of the solution. Concerning the Multi-Constrained Multicast Minimum Cost problem (MCMCM), a new Integer Linear Programming (ILP) formulation is proposed to compute hierarchies, which are the exact solutions for MCMCM. An efficient preprocessing-based algorithm is also designed to accelerate the resolution time in large size networks. Regarding the problem of QoS routing in Low Power and Lossy Networks (LLNs), a new Objective Function (OF)-based solution is presented. This solution uses a non-linear length function. It is the first that takes into account any number of metrics and constraints for QoS routing. We designed an exact and two heuristic routing algorithms with QoS constraints for LLNs.

Ad hoc wireless networks are increasingly being used to provide connectivity where a wired networking infrastructure is either unavailable or inaccessible. Many deployments utilize group communication, where several senders communicate with several receivers; multicasting has long been seen as an efficient way to provide this service. While there has been a great deal of research on multicast routing in ad hoc networks, relatively little attention has been paid to the design of multicast transport protocols, which provide reliability and congestion control. In this dissertation we design and implement a complete multicast transport architecture that includes both routing and transport protocols. Our multicast transport architecture has three modules: (a) a multicast routing and state setup protocol, (b) a mobility detection algorithm, and (c) a hop-by-hop transport protocol. The multicast routing and state setup protocol, called ASSM, is lightweight and receiver-oriented, making it both efficient and scalable. A key part of ASSM is its use of Source Specific Multicast semantics to avoid broadcasting when searching for sources. ASSM also uses routes provided by the unicast protocol to greatly reduce routing overhead. The second module, MDA, solves the problem of determining the cause of frame loss and reacting properly. Frame loss can occur due to contention, a collision, or mobility. Many routing protocols make the mistake of interpreting all loss as due to mobility, resulting in significant overhead when they initiate a repair that is not required. MDA enables routing protocols to react to frame loss only when necessary. The third module is a hop-by-hop multicast transport protocol, HCP. A hop-by-hop algorithm has a faster response time than that of an end-to-end algorithm, because it invokes congestion control at each hop instead of waiting for an end-to-end response. An important feature of HCP is that it can send data at different rates to receivers with different available bandwidth. We evaluate all three components of this architecture using simulations, demonstrating the improved performance, efficiency and scalability of our architecture as compared to other solutions.

Wireless ad-hoc networks are easily deployed, untethered to infrastructure, and have virtually an unlimited number of applications. However, this flexibility comes at the cost of finite and often unreplenishable power supplies. Once a node has consumed all of its power, it can no longer receive, transmit, gather information, or otherwise participate in the network. Therefore, reducing the amount of energy necessary for node communication has been an area of intense research. Previous work has investigated the use of directional antennas as a method to reduce inter-node power requirements. However, most proposed methods ignore inter-session interference, propose heuristic solution methods, and ignore the use of directional antennas for signal reception. We develop a flexible mixed-integer linear program (MILP) designed to optimize max-min multicast path lifetime for directional antenna equipped networks in the presence of interference. The MILP is utilized to perform a comparison directional antenna use for signal transmission and reception. Results indicate that directional reception is slightly superior to transmission for the defined max-min lifetime metric, and vastly superior when considering cumulative power use. We further analyze the performance of interference-ignorant link-based heuristics designed for both directional transmission and directional reception as they perform in our more realistic model. Our results show that interference-ignorant methods cannot find feasible solutions unless all nodes are equipped with high gain, high efficiency directional antennas. Even in these cases, directional reception outperforms directional transmission. Because of the superiority of directional reception, we focus our attention on this method. A heterogeneity study is performed, and two heuristic methods for approximating the MILP optima are developed. We find that even under heterogeneous conditions, directional reception can increase network lifetime. Finally, a genetic algorithm (GA) and semi-distributed heuristic method are developed as alternatives to the MILP. Results show that the GA often can find solutions with lifetimes 85% as long as the optimal. Our semi-distributed heuristic, designed to be even more computationally simple than the GA, and to serve as a basis for a distributed protocol, is almost as effective as the GA as approximating optimal solutions. We conclude that directional reception is the superior method of antenna use for extending max-min multicast tree lifetime, that it works well in heterogeneous conditions, and lends itself well to heuristic design. / Ph. D.

No description available.

In this master's thesis I deal with modelling and simulating of multicast routing protocol PIM Sparse Mode in OMNeT++. I also describe basic information about multicast, protocol PIM-SM, its configuration and multicast data streams visualization in computer networks. The thesis is especially focused on design and implementation of PIM-SM in OMNeT++ and extension of ANSAINET library.

Au cours de la dernière décennie, le trafic dans les réseaux a connu une croissance explosive en double environ tous les trente trois mois. Les sources à l'origine de cette croissance proviennent de nombreuses applications à grande vitesse qui impliquent la transmission de données dans des groupes de multicast. Pour réaliser la multicast optique, les routeurs optiques peuvent avoir des répartiteurs de lumière spéciaux pour diviser des signaux lumineux et des convertisseurs de longueur d'onde pour modifier les longueurs d'onde où c'est nécessaire. Cependant, la division réduit l'énergie du signal qui nécessite alors une amplification ou une régénération qui nécessitent du matériel coûteux. Les convertisseurs de longueurs d'onde aussi ne sont pas suffisamment matures pour être largement déployés dans les technologies optiques actuelles. Par conséquent, dans les réseaux tout-optique, les unités de transformation des routeurs sont souvent hétérogènes et les algorithmes de routage doivent en tenir compte tout en parvenant à des solutions de compromis coût-performances qui satisfassent les exigences de bande passante et les contraintes optiques.Dans cette thèse, nous étudions les problème de routage multicast tout-optique (AOMR) dans les réseaux tout-optique hétérogènes. L'hétérogénéité provient principalement de l'absence / présence de séparateurs de lumière et de convertisseurs de longueur d'onde et de la répartition inégale des longueurs d'onde dans les liens du réseau. En général, les problèmes de AOMR sont NP-difficiles. L'objectif de la thèse est d'analyser et de formuler les problèmes sous différentes contraintes optiques, pour rechercher des solutions optimales ou proposer des heuristiques efficaces. Les deux contextes possibles, la demande unique ou multiple de multicast, sont examinés. Toutes les propositions présentées dans la thèse sont validées par des simulations approfondies. Les principales contributions peuvent être résumées comme il suit.1) Nous identifions les structures des routes optimales pour les problèmes de l'AOMR dans les réseaux WDM hétérogènes. Comme indiqué dans la thèse, les solutions optimales ne sont plus basées sur des arbres de lumière classiques, mais sur une structure arborescente plus générale appelée hiérarchie. Certaines formes de hiérarchie pour la multicast WDM sont des parcours optiques, des hiérarchies optiques, des hiérarchies-araignée optiques ou encore des ensembles de ces routes optiques. Les algorithmes exacts et les heuristiques proposés dans la thèse sont principalement basés sur les hiérarchies.2) Dans le cas du problème de multicast avec une seule demande dans des réseaux partiellement équipés de diviseurs de lumière, nous proposons une heuristique efficace dont les résultats font le compromis entre la consommation de longueur d'onde, le coût total, et le délai de bout-en-bout.3) Dans le même cas mais dans des réseaux non équipés de diviseurs de lumière, nous prouvons la NP-difficulté, exprimons les problèmes au moyen d'un programme linéaire (ILP) pour trouver les solutions exactes et proposons plusieurs heuristiques pour calculer de bonnes solutions.4) Pour le cas de demandes multicast multiples, nous nous concentrons sur les modèles de trafic statiques dans des réseaux partiellement équipés de diviseurs mais sans convertisseurs de longueur d'onde. Tout d'abord nous proposons une formulation ILP sur la base de hiérarchies optiques afin de rechercher la solution optimale. Ensuite, utilisant un modèle de graphe en couches, nous développons plusieurs heuristiques adaptatives pour calculer des hiérarchies optiques de solutions approximatives. Ces algorithmes adaptatifs surpassent les techniques de routage existants pour minimiser la probabilité de blocage.Dans l'ensemble, la thèse souligne que les solutions optimales pour les problèmes de l'AOMR considérés correspondent à des hiérarchies, que ce soit pour une seule demande ou des demandes multiples. / Over the past decade, network traffic levels experienced an explosive growth at about double amount in approximately every thirty months. The sources accounting for this growth come from numerous high-speed applications (e.g., video-on-demand, high-definition television) which involve the data transmission in multicast groups. To realize optical multicasting, optical routers should have light splitters to split light signals and wavelength converters to change the wavelengths wherever needed. However, the splitting reduces the energy of the output signal which in turn requires the costly power amplification or regeneration. Wavelength converters are also immature to be deployed widely in current optical technologies. Consequently, in all-optical networks, routers are often heterogeneous in their processing units, which challenges the routing. Therefore, it is crucial to design efficient multicast routing strategies at the backbone optical networks, in order to achieve cost-performance tradeoff solutions while satisfying the ever-increasing bandwidth demands and optical constraints.In this thesis, we investigate the all-optical multicast routing (AOMR) problems in heterogeneous optical networks. The heterogeneity mainly comes from the absence/presence of light splitters and wavelength converters and the uneven distribution of wavelengths in the network links. In general, AOMR problems are often NP-hard. The objective of the thesis is to analyze and formulate the problems, to search for the optimal solutions, and to propose efficient heuristics to solve the problems under different optical constraints. Both possible contexts, i.e., single-multicast request and multiple-multicast requests, are examined. All the reported results in the thesis are supported by extensive and careful simulations. The major contributions can be summarized as follows.1) We identify the optimal route structures for AOMR problems under heterogeneous mesh WDM networks. As shown in the thesis, the optimal solutions are no longer based on conventional light-trees, but a more general tree-like structure called hierarchy. Some forms of hierarchy realized for WDM multicasting are light-trails, light-hierarchies, light-spider hierarchies and a set of these light-structures. The exact and heuristic algorithms proposed in the thesis are mainly based on hierarchy. 2) For single-multicast with sparse-splitting case, we propose an efficient heuristic algorithm to produce a good tradeoff solution among wavelength consumption, channel total cost and end-to-end delay.3) For single-multicast with non-splitting case, we prove the NP-hardness, identify the optimal solution as a set of light-spider hierarchies, formulate the problems by means of Integer Linear Program (ILP) formulations to find the exact solution, and propose several cost-effective heuristic algorithms to compute the approximate solutions. 4) For the case with multiple-multicast requests, we focus on static traffic patterns under sparse-splitting without wavelength conversion case. First, an ILP formulation based on light-hierarchies is proposed to search for the optimal solution. By applying the layered graph model, we then develop several adaptive heuristic algorithms to compute light-hierarchies for approximate solutions. These adaptive algorithms outperform the existing fixed routing ones in minimizing the blocking probability. Overall, the thesis points out that the optimal solutions for heterogeneously constrained AOMR problems correspond to hierarchies, regardless of request multiplicity consideration.