QoS routing is one of the major building blocks for supporting QoS in communication networks and, hence, a necessary component of future communication networks. Bandwidth- Constrained Routing Algorithm (BCRA) may help to satisfy QoS requirements such as end-to-end delay, delay-jitter etc when WFQ-like (Weighted Fair Queuing) scheduling mechanisms are deployed. The existing algorithms for bandwidth constrained routing suffer from high message overhead and have a high computational and space complexity. The work presented in the thesis, therefore, focuses on the different techniques that an be used to reserve bandwidth for a unicast connection with low protocol overhead in terms of number of messages. We have compared the performance of the proposed routing algorithms using simulation studies with other bandwidth constrained routing algorithms. The call blocking ratio and message overhead have been used as the performance metric to compare the proposed algorithm with the existing ones. We present three source routing algorithms for unicast connections satisfying the band- width requirement. The first two routing algorithms are based on the partitioning of the network. The link-state broadcasts are limited to the partition. In the first algorithm, the source node queries the other partitions for the state information on a connection request and computes the path based on the information received from the other partitions. The second algorithm is based on state aggregation. The aggregated state of other partitions is maintained at every node. The source node finds a feasible path based on the aggregated information. The path is expanded in every partition, if required, at the time of resource reservation. The third QoS routing algorithm uses the Distance Vector Tables to find a route for a connection. If the shortest path satisfies the bandwidth requirement, then it is selected; otherwise a random deviation is taken at the point where bandwidth requirement is not satisfied and shortest path algorithm is again followed. In all the three algorithms presented, the packets carry the entire path information to the destination node. Therefore, no per connection information is required to be maintained at the intermediate nodes. Simulation results indicate that the proposed algorithms indeed help educing the protocol overhead considerably, and at the same time they give comparable or better performance in terms of resource utilization across a wide range of workloads.

Les noves tecnologies a la xarxa ens permeten transportar, cada cop més, grans volums d' informació i trànsit de xarxa amb diferents nivells de prioritat. En aquest escenari, on s'ofereix una millor qualitat de servei, les conseqüències d'una fallada en un enllaç o en un node esdevenen més importants. Multiprotocol Lavel Switching (MPLS), juntament amb l'extensió a MPLS generalitzat (GMPLS), proporcionen mecanismes ràpids de recuperació de fallada establint camins, Label Switch Path (LSPs), redundants per ser utilitzats com a camins alternatius. En cas de fallada podrem utilitzar aquests camins per redireccionar el trànsit. El principal objectiu d'aquesta tesi ha estat millorar alguns dels actuals mecanismes de recuperació de fallades MPLS/GMPLS, amb l'objectiu de suportar els requeriments de protecció dels serveis proporcionats per la nova Internet. Per tal de fer aquesta avaluació s'han tingut en compte alguns paràmetres de qualitat de protecció com els temps de recuperació de fallada, les pèrdues de paquets o el consum de recursos.En aquesta tesi presentem una completa revisió i comparació dels principals mètodes de recuperació de fallada basats en MPLS. Aquest anàlisi inclou els mètodes de protecció del camí (backups globals, backups inversos i protecció 1+1), els mètodes de protecció locals i els mètodes de protecció de segments. També s'ha tingut en compte l'extensió d'aquests mecanismes a les xarxes òptiques mitjançant el pla de control proporcionat per GMPLS.En una primera fase d'aquest treball, cada mètode de recuperació de fallades és analitzat sense tenir en compte restriccions de recursos o de topologia. Aquest anàlisi ens dóna una primera classificació dels millors mecanismes de protecció en termes de pèrdues de paquets i temps de recuperació. Aquest primer anàlisi no és aplicable a xarxes reals. Per tal de tenir en compte aquest nou escenari, en una segona fase, s'analitzen els algorismes d'encaminament on sí tindrem en compte aquestes limitacions i restriccions de la xarxa. Es presenten alguns dels principals algorismes d'encaminament amb qualitat de servei i alguna de les principals propostes d'encaminament per xarxes MPLS. La majoria dels actual algorismes d'encaminament no tenen en compte l'establiment de rutes alternatives o utilitzen els mateixos objectius per seleccionar els camins de treball i els de protecció. Per millorar el nivell de protecció introduïm i formalitzem dos nous conceptes: la Probabilitat de fallada de la xarxa i l'Impacte de fallada. Un anàlisi de la xarxa a nivell físic proporciona un primer element per avaluar el nivell de protecció en termes de fiabilitat i disponibilitat de la xarxa. Formalitzem l'impacte d'una fallada, quant a la degradació de la qualitat de servei (en termes de retard i pèrdues de paquets). Expliquem la nostra proposta per reduir la probabilitat de fallada i l'impacte de fallada. Per últim fem una nova definició i classificació dels serveis de xarxa segons els valors requerits de probabilitat de fallada i impacte.Un dels aspectes que destaquem dels resultats d'aquesta tesi és que els mecanismes de protecció global del camí maximitzen la fiabilitat de la xarxa, mentre que les tècniques de protecció local o de segments de xarxa minimitzen l'impacte de fallada. Per tant podem assolir mínim impacte i màxima fiabilitat aplicant protecció local a tota la xarxa, però no és una proposta escalable en termes de consum de recursos. Nosaltres proposem un mecanisme intermig, aplicant protecció de segments combinat amb el nostre model d'avaluació de la probabilitat de fallada. Resumint, aquesta tesi presenta diversos mecanismes per l'anàlisi del nivell de protecció de la xarxa. Els resultats dels models i mecanismes proposats milloren la fiabilitat i minimitzen l'impacte d'una fallada en la xarxa. / New network technology enables increasingly higher volumes of information to be carried. Various types of mission-critical, higher-priority traffic are now transported over these networks. In this scenario, when offering better quality of service, the consequences of a fault in a link or node become more pronounced. Multiprotocol Label Switching (MPLS) and the extended Generalized MPLS (GMPLS) provide fast mechanisms for recovery from failures by establishing redundant Label Switch Paths as backup paths. With these backups, traffic can always be redirected in case of failure. The main objective of this thesis is to improve some of the current MPLS/GMPLS fault recovery methods, in order to support the protection requirements of the new Internet services. Some parameters, such as fault recovery time, packet loss or resource consumption, all within the scope of this quality of protection, are considered. In this thesis a review and detailed comparison of the MPLS fault recovery methods are presented. Path protection methods (global backups, reverse backups and 1+1 methods), as well as segment protection and local methods are included in this analysis. The extension of these mechanisms to optical networks using GMPLS control plane is also taken into account.In the first phase MPLS fault recovery methods are analyzed without taking into account resource or network topology constraints. This analysis reported a first classification of the best protection methods in terms of packet loss and recovery time. This first analysis cannot be applied to real networks. In real networks, bandwidth or network topology constraints can force a change in the a priori optimal protection choice. In this new scenario, current routing algorithms must be analyzed. The main aspects of the QoS routing methods are introduced, and some of these mechanisms are described and compared. QoS routing algorithms do not include protection as a main objective and, moreover, the same QoS objectives for selecting the working path are used for selecting the backup path. In order to evaluate the quality of protection, two novel concepts are introduced and analyzed: the network failure probability and the failure impact. The physical network provides an initial value of the network protection level in terms of network reliability and availability. A proposal to evaluate network reliability is introduced, and a formulation to calculate the failure impact (the QoS degradation in terms of packet loss and delay) is presented. A proposal to reduce the failure probability and failure impact as well as the enhancement of some current routing algorithms in order to achieve better protection are explained. A review of the traffic services protection requirements and a new classification, based on the failure probability and failure impact values, is also provided in this work.Results show that path protection schemes improve network reliability. Segment/local protection schemes reduce the network failure impact. Minimum impact with maximum reliability can be achieved using local protection throughout the entire network. However, it is not scalable in terms of resource consumption. In this case our failure probability evaluation model can be used to minimize the required resources. Results demonstrate the reduction of the failure impact combining segment protection and our network reliability evaluation model in different network scenarios.In summary, an in-depth analysis is carried out and a formulation to evaluate the network protection level is presented. This evaluation is based on network reliability maximization and failure impact reduction in terms of QoS degradation. A scalable proposal in terms of resource consumption, detailed and experimentally analyzed, offers the required level of protection in different network scenarios for different traffic services.

Mobile Ad Hoc Networks (MANETs) are a class of infrastructure less network architecture which are formed by a collection of mobile nodes that communicate with each other using multi-hop wireless links. They eliminate the need for central management, hence each node must operate cooperatively to successfully maintain the network. Each node performs as a source, a sink and a router. Future applications of MANETs are expected to be based on all-IP architecture, carrying a multitude of real-time multimedia applications such as voice, video and data. It would be necessary for MANETs to have an efficient routing and quality of service (QoS) mechanism to support diverse applications. This thesis proposes a set of cooperative protocols that provide support for QoS routing. The first is the on-demand, Non-Disjoint Multiple Routes Discovery protocol (NDMRD). NDMRD allows the establishment of multiple paths with node non-disjoint between source and destination node. It returns to the source a collection of routes with the QoS parameters. The second part of the protocol is the Node State Monitoring protocol for the purpose of monitoring, acquisition, dissemination and accumulation of QoS route information. The third part of the protocol implements the QoS route selection based on a Genetic Algorithm. The GA is implemented online with predetermined initial population and weighted-sum fitness function which operates simultaneously on the node bandwidth, media access delay, end to end delay and the node connectivity index (NCI). The term node connectivity index is a numerical value designed to predict comparatively the longest time a node-pair might be connected wirelessly.

Orientador: Akebo Yamakami / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-06T20:32:53Z (GMT). No. of bitstreams: 1 Resende_RaulisonAlves_D.pdf: 558127 bytes, checksum: 8c65274e70573045a52e4b1101a2c32e (MD5) Previous issue date: 2006 / Resumo: A teoria de conjuntos fuzzy provê um ferramental para desenvolver processos aproximados de raciocínio quando a informação disponível é incerta, incompleta, imprecisa ou vaga. Com as novas ferramentas emergentes na área de inteligência computacional, tais como lógicas não padronizadas, redes neurais e raciocínio simbólico, esta nova teoria é um acréscimo bem-vindo ao repertório de ferramentas tradicionais apropriadas. Neste sentido, esta tese propõe três estratégias para o provimento de qualidade de serviço em redes IP, usando lógica fuzzy. Como primeira proposta é implementado um módulo inteligente para gerenciamento da QoS por meio da criação de políticas para roteadores do tipo DiffServ. A segunda estratégia consiste em um algoritmo fuzzy que resolve o problema de roteamento baseado em restrição de tempo com mínimo custo. Esta proposta apresentou resultados satisfatórios quando comparada com a solução sem lógica fuzzy. E, por último, se propõe um controlador de admissão de conexão para tratar as informações com certo grau de incertezas em redes IP com MPLS. O controlador apresenta as seguintes vantagens: flexibilização da admissão de conexão e possibilidade de incluir mais informações da rede e do tráfego na tomada da decisão sem aumentar consideravelmente a complexidade do controlador / Abstract: Fuzzy set theory provides a machinery for carrying out approximate reasoning processes when available information is uncertain, incomplete, imprecise, or vague. With the emergence of new tools in the area of computational intelligence, such as non standard logics, neural networks, and symbolic reasoning, this new theory is a welcome addition to the repertoire of traditional appropriate tools. In this sense, this thesis proposes three different strategies to apply Fuzzy Logic to provide QoS in IP Networks. The first one is the implementation of an intelligent, policy-based module for QoS management. The module permits the creation of policies to configure QoS in routers and a practical implementation has been performed for a DiffServ router. The second strategy proposes a fuzzy algorithm to solve the problem of routing based on time restrictions with minimum costs. The results obtained from this algorithm were satisfactory when compared to similar solutions that did not involve fuzzy logic. Finally, the third strategy proposes a Connection Admission Controller to process information that contains a high level of uncertainty in IP networks over MPLS. The controller offers the following advantages: flexibility for connections admission and the possibility of including more network and traffic information in the decision making process without considerably increasing the controller complexity / Doutorado / Telecomunicações e Telemática / Doutor em Engenharia Elétrica