D. Kohel, i més endavant M. Fouquet i F. Morain, van estudiar l’estructura dels volcans de ℓ–isogènies d’una corba el·líptica sobre un cos finit, sent ℓ un primer qualsevol, i van donar algorismes per anar des del terra fins al cràter del volcà. Seguint aquests treballs, en aquesta tesi estudiem noves propietats dels volcans de ℓ–isogènies. Així, caracteritzem l’altura d’un volcà de ℓ–isogènies d’una corba el·líptica sobre un cos finit Fq a partir de les valoracions ℓ–àdiques del cardinal de la corba i de q − 1, i analitzem detalladament el cas ℓ = 3. D’altra banda, per a volcans anomenats regulars donem, segons l’estructura del subgrup de ℓ–Sylow de la corba, el nivell on està ubicada dins del volcà. Utilitzant aquest estudi, hem dissenyat un algorisme que genera, a partir d’una corba donada, un llistat de corbes isògenes a la corba inicial de forma ordenada segons el grau ℓ de la isogènia. Amb aquest objectiu, introduïm el concepte ℓ–cordillera, estructura formada per tots els ℓ–volcans sobre un mateix cos, per a un primer ℓ. Així, per recórrer tota una ℓ–cordillera saltarem d’un ℓ–volcà a un altre considerant isogènies de grau un primer ℓ′, diferent de ℓ. En un vessant més pràctic, hem treballat en l’ús de la criptografia el·líptica en dispositius com les targetes intel·ligents. Més concretament, ens hem centrat en els atacs que pateixen aquests dispositius, com els Zero-Value Points (ZVP), presentats per L. Goubin i ampliats per T. Akishita i T. Takagi. En aquesta tesi, proposem una contramesura a aquests atacs, seguint la línia de la proposada per N. Smart. La contramesura està basada en l’ús d’una variant de l’algorisme esmentat anteriorment que busca corbes resistents recorrent les ℓ–cordilleres de la corba inicial. Finalment, estudiem el comportament d’aquests atacs considerant corbes el·líptiques donades en el model d’Edwards. A diferència de les corbes el·líptiques expressades mitjançant l’equació de Weierstraß, les corbes d’Edwards no són vulnerables als atacs ZVP. / D. Kohel, y más adelante M. Fouquet y F. Morain, estudiaron la estructura de los volcanes de ℓ–isogenias de una curva elíptica sobre un cuerpo finito, siendo ℓ un primo cualquiera, y propusieron algoritmos para ir desde el suelo hasta el cráter del volcán. Siguiendo estos trabajos, en esta tesis, estudiamos propiedades de los volcanes de ℓ–isogenias. Así, caracterizamos la altura de un volcán de ℓ–isogenias de una curva elíptica sobre un cuerpo finito Fq a partir de las valoraciones ℓ–ádicas del cardinal de la curva y de q − 1, analizando en detalle el caso ℓ = 3. Por otro lado, para los volcanes llamados regulares damos, según la estructura del subgrupo de ℓ–Sylow de la curva, el nivel donde está ubicada dentro del volcán. Utilizando este estudio, hemos diseñado un algoritmo que genera, a partir de una curva dada, un listado de curvas isógenas a la curva inicial de forma ordenada según el grado ℓ de la isogenia. Con este objetivo, introducimos el concepto de ℓ–cordillera, estructura formada por todos los ℓ–volcanes sobre un mismo cuerpo, para un primo ℓ dado. Así, para recorrer toda una ℓ–cordillera, saltaremos de un ℓ–volcán a otro, considerando isogenias de grado un primo ℓ′, diferente de ℓ. En una vertiente más práctica, hemos trabajado en el uso de la criptografía elíptica en dispositivos como las tarjetas inteligentes. Más concretamente, nos hemos centrado en los ataques que sufren estos dispositivos, como los ataques Zero-Value Points (ZVP), presentados por L. Goubin y ampliados por T. Akishita y T. Takagi. En esta tesis, proponemos una contramedida a estos ataques, siguiendo la línea de la propuesta por N. Smart. La contramedida está basada en el uso de una variante del algoritmo mencionado anteriormente que busca curvas resistentes recorriendo las ℓ–cordilleras de la curva inicial. Finalmente, estudiamos el comportamiento de estos ataques considerando curvas elípticas dadas en el modelo de Edwards. A diferencia de las curvas elípticas expresadas mediante la ecuación deWeierstraß, las curvas de Edwards no son vulnerables a los ataques ZVP. / D. Kohel and later M. Fouquet and F. Morain studied the structure of volcanoes of ℓ–isogenies of an elliptic curve over a finite field, being ℓ any prime number. They also proposed algorithms to go from the floor to the crater of a volcano. Following these works, in this thesis we studied some properties of the ℓ–isogeny volcanoes. Thus, we characterized the height of an ℓ–isogeny volcano of an elliptic curve over a finite field Fq from the ℓ–adic valuations of the cardinality of the curve and q − 1, analyzing the case ℓ = 3 in detail. On the other hand, for the so-called regular volcanoes, we give the level where a curve is located inside the volcano, according to the structure of its ℓ–Sylow subgroup. From this study, we have designed an algorithm that generates, from a given curve, a list of curves isogenous to the initial one, in an organized manner, according to the degree ℓ of the isogeny. With this objective, we introduce the concept of ℓ–cordillera, a structure consisting of all the ℓ–volcanoes over a field, for a given prime ℓ. Thus, in order to explore a whole ℓ–cordillera, we jump from an ℓ–volcano to another, considering isogenies of degree a prime ℓ′ different from ℓ. In a more practical aspect, we worked on the use of elliptic curve cryptography on devices such as smart cards. More specifically, we focused on the attacks suffered by these devices, such as the Zero-Value Point (ZVP) attacks, which were presented by L. Goubin and extended by T. Akishita and T. Takagi. In this thesis, we propose a countermeasure to these attacks, along the lines of the one proposed by N. Smart. The countermeasure is based on the use of a variant of the algorithm mentioned above, that searches for strong curves exploring the ℓ–cordilleras of the initial curve. Finally, we studied the behavior of these attacks considering elliptic curves given in the Edwards model. Unlike elliptic curves expressed by the Weierstraß equation, Edwards curves are not vulnerable to ZVP attacks.

Network monitoring has become a necessity to aid in the management and operation of large networks. Passive network monitoring consists of extracting metrics (or any information of interest) by analyzing the traffic that traverses one or more network links. Extracting information from a high-speed network link is challenging, given the great data volumes and short packet inter-arrival times. These difficulties can be alleviated by using extremely efficient algorithms or by sampling the incoming traffic. This work improves the state of the art in both these approaches. For one-way packet delay measurement, we propose a series of improvements over a recently appeared technique called Lossy Difference Aggregator. A main limitation of this technique is that it does not provide per-flow measurements. We propose a data structure called Lossy Difference Sketch that is capable of providing such per-flow delay measurements, and, unlike recent related works, does not rely on any model of packet delays. In the problem of collecting measurements under the sliding window model, we focus on the estimation of the number of active flows and in traffic filtering. Using a common approach, we propose one algorithm for each problem that obtains great accuracy with significant resource savings. In the traffic sampling area, the selection of the sampling rate is a crucial aspect. The most sensible approach involves dynamically adjusting sampling rates according to network traffic conditions, which is known as adaptive sampling. We propose an algorithm called Cuckoo Sampling that can operate with a fixed memory budget and perform adaptive flow-wise packet sampling. It is based on a very simple data structure and is computationally extremely lightweight. The techniques presented in this work are thoroughly evaluated through a combination of theoretical and experimental analysis.

On Computer Science research, traditionally, most efforts have been devoted to research hardness for the worst case of problems (proving NP completeness and comparing and reducing problems between them are the two most known). Artifcial Intelligence research, recently, has focused also on how some characteristics of concrete instances have dramatic effects on complexity and hardness while worst-case complexity remains the same. This has lead to focus research efforts on understanding which aspects and properties of problems or instances affect hardness, why very similar problems can require very diferent times to be solved. Research search based problems has been a substantial part of artificial intelligence research since its beginning. Big part of this research has been focused on developing faster and faster algorithms, better heuristics, new pruning techniques to solve ever harder problems. One aspect of this effort to create better solvers consists on benchmarking solver performance on selected problem sets, and, an, obviously, important part of that benchmarking is creating and defining new sets of hard problems. This two folded effort, on one hand to have at our disposal new problems, harder than previous ones, to test our solvers, and on the other hand, to obtain a deeper understanding on why such new problems are so hard, thus making easier to understand why some solvers outperform others, knowledge that can contribute towards designing and building better and faster algorithms and solvers. This work deals with designing better, that is harder and easy to generate, problems for CSP solvers, also usable for SAT solvers. In the first half of the work general concepts on hardness and CSP are introduced, including a complete description of the chosen problems for our study. This chosen problems are, Random Binary CSP Problems (BCSP), Quasi-group Completion Problems (QCP), Generalised Sudoku Problems (GSP), and a newly defined problem, Edge-Matching Puzzles (GEMP). Although BCSP and QCP are already well studied problems, that is not the case with GSP and GEMP. For GSP we will define new creation methods that ensure higher hardness than standard random methods. GEMP on the other hand is a newly formalised problem, we will define it, will provide also algorithms to build easily problems of tunable hardness and study its complexity and hardness. On the second part of the work we will propose and study new methods to increase the hardness of such problems. Providing both, algorithms to build harder problems and an in-depth study of the effect of such methods on hardness, specially on resolution time.

El tema d'aquesta tesi és el desenvolupament de mètodes de fitació per a una classe de models de confiabilitat basats en cadenes de Markov de temps continu (CMTC) de sistemes tolerants a fallades.Els sistemes considerats a la tesi es conceptualitzen com formats per components (hardware o software) que fallen i, en el cas de sistemes reparables, són reparats. Els components s'agrupen en classes de forma que els components d'una mateixa classe són indistingibles. Per tant, un component és considerat com a una instància d'una classe de components i el sistema inclou un bag de classes de components definit sobre un cert domini. L'estat no fallada/fallada del sistema es determina a partir de l'estat no fallada/fallada dels components mitjançant una funció d'estructura coherent que s'especifica amb un arbre de fallades amb classes d'esdeveniments bàsics. (Una classe d'esdeveniment bàsic és la fallada d'un component d'una classe de components.)La classe de models basats en CMTC considerada a la tesi és força àmplia i permet, per exemple, de modelar el fet que un component pot tenir diversos modes de fallada. També permet de modelar fallades de cobertura mitjançant la introducció de components ficticis que no fallen per ells mateixos i als quals es propaguen les fallades d'altres components. En el cas de sistemes reparables, la classe de models considerada admet polítiques de reparació complexes (per exemple, nombre limitat de reparadors, prioritats, inhibició de reparació) així com reparació en grup (reparació simultània de diversos components). Tanmateix, no és possible de modelar la reparació diferida (és a dir, el fet de diferir la reparació d'un component fins que una certa condició es compleixi).A la tesi es consideren dues mesures de confiabilitat: la no fiabilitat en un instant de temps donat en el cas de sistemes no reparables i la no disponibilitat en règim estacionari en el cas sistemes reparables.Els mètodes de fitació desenvolupats a la tesi es basen en el concepte de "distància a la fallada", que es defineix com el nombre mínim de components que han de fallar a més dels que ja han fallat per fer que el sistema falli.A la tesi es desenvolupen quatre mètodes de fitació. El primer mètode dóna fites per a la no fiabilitat de sistemes no reparables emprant distàncies a la fallada exactes. Aquestes distàncies es calculen usant el conjunt de talls mínims de la funció d'estructura del sistema. El conjunt de talls mínims s'obté amb un algorisme desenvolupat a la tesi que obté els talls mínims per a arbres de fallades amb classes d'esdeveniments bàsics. El segon mètode dóna fites per a la no fiabilitat usant fites inferiors per a les distàncies a la fallada. Aquestes fites inferiors s'obtenen analitzant l'arbre de fallades del sistema, no requereixen de conèixer el conjunt de talls mínims i el seu càlcul és poc costós. El tercer mètode dóna fites per a la no disponibilitat en règim estacionari de sistemes reparables emprant distàncies a la fallada exactes. El quart mètode dóna fites per a la no disponibilitat en règim estacionari emprant les fites inferiors per a les distàncies a la fallada.Finalment, s'il·lustren les prestacions de cada mètode usant diversos exemples. La conclusió és que cada un dels mètodes pot funcionar molt millor que altres mètodes prèviament existents i estendre de forma significativa la complexitat de sistemes tolerants a fallades per als quals és possible de calcular fites ajustades per a la no fiabilitat o la no disponibilitat en règim estacionari. / The subject of this dissertation is the development of bounding methods for a class of continuous-time Markov chain (CTMC) dependability models of fault-tolerant systems.The systems considered in the dissertation are conceptualized as made up of components (hardware or software) that fail and, for repairable systems, are repaired. Components are grouped into classes, the components of the same class being indistinguishable. Thus, a component is regarded as an instance of some component class and the system includes a bag of component classes defined over a certain domain. The up/down state of the system is determined from the unfailed/failed state of the components through a coherent structure function specified by a fault tree with basic event classes. (A basic event class is the failure of a component of a component class.)The class of CTMC models considered in the dissertation is quite wide and allows, for instance, to model the fact that a component may have different failure modes. It also allows to model coverage failures by means of introducing fictitious components that do not fail by themselves and to which uncovered failures of other components are propagated. In the case of repairable systems, the considered class of models supports very complex repair policies (e.g., limited repairpersons, priorities, repair preemption) as well as group repair (i.e., simultaneous repair of several components). However, deferred repair (i.e., the deferring of repair until some condition is met) is not allowed.Two dependability measures are considered in the dissertation: the unreliability at a given time epoch for non-repairable systems and the steady-state unavailability for repairable systems.The bounding methods developed in the dissertation are based on the concept of "failure distance from a state," which is defined as the minimum number of components that have to fail in addition to those already failed to take the system down.We develop four bounding methods. The first method gives bounds for the unreliability of non-repairable fault-tolerant systems using (exact) failure distances. Those distances are computed using the set of minimal cuts of the structure function of the system. The set of minimal cuts is obtained using an algorithm developed in the dissertation that obtains the minimal cuts for fault trees with basic event classes. The second method gives bounds for the unreliability using easily computable lower bounds for failure distances. Those lower bounds are obtained analyzing the fault tree of the system and do not require the knowledge of the set of minimal cuts. The third method gives bounds for the steady-state unavailability using (exact) failure distances. The fourth method gives bounds for the steady-state unavailability using the lower bounds for failure distances.Finally, the performance of each method is illustrated by means of several large examples. We conclude that the methods can outperform significantly previously existing methods and extend significantly the complexity of the fault-tolerant systems for which tight bounds for the unreliability or steady-state unavailability can be computed.

Aquest treball presenta una classe de funcions que serveixen de models neuronals generalitzats per ser usats en xarxes neuronals artificials. Es defineixen com una mesura de similitud que actúa com una definició flexible de neurona vista com un reconeixedor de patrons. La similitud proporciona una marc conceptual i serveix de cobertura unificadora de molts models neuronals de la literatura i d'exploració de noves instàncies de models de neurona. La visió basada en similitud porta amb naturalitat a integrar informació heterogènia, com ara quantitats contínues i discretes (nominals i ordinals), i difuses ó imprecises. Els valors perduts es tracten de manera explícita. Una neurona d'aquesta classe s'anomena neurona heterogènia i qualsevol arquitectura neuronal que en faci ús serà una Xarxa Neuronal Heterogènia.En aquest treball ens concentrem en xarxes neuronals endavant, com focus inicial d'estudi. Els algorismes d'aprenentatge són basats en algorisms evolutius, especialment extesos per treballar amb informació heterogènia. En aquesta tesi es descriu com una certa classe de neurones heterogènies porten a xarxes neuronals que mostren un rendiment molt satisfactori, comparable o superior al de xarxes neuronals tradicionals (com el perceptró multicapa ó la xarxa de base radial), molt especialment en presència d'informació heterogènia, usual en les bases de dades actuals. / This work presents a class of functions serving as generalized neuron models to be used in artificial neural networks. They are cast into the common framework of computing a similarity function, a flexible definition of a neuron as a pattern recognizer. The similarity endows the model with a clear conceptual view and serves as a unification cover for many of the existing neural models, including those classically used for the MultiLayer Perceptron (MLP) and most of those used in Radial Basis Function Networks (RBF). These families of models are conceptually unified and their relation is clarified. The possibilities of deriving new instances are explored and several neuron models --representative of their families-- are proposed. The similarity view naturally leads to further extensions of the models to handle heterogeneous information, that is to say, information coming from sources radically different in character, including continuous and discrete (ordinal) numerical quantities, nominal (categorical) quantities, and fuzzy quantities. Missing data are also explicitly considered. A neuron of this class is called an heterogeneous neuron and any neural structure making use of them is an Heterogeneous Neural Network (HNN), regardless of the specific architecture or learning algorithm. Among them, in this work we concentrate on feed-forward networks, as the initial focus of study. The learning procedures may include a great variety of techniques, basically divided in derivative-based methods (such as the conjugate gradient)and evolutionary ones (such as variants of genetic algorithms).In this Thesis we also explore a number of directions towards the construction of better neuron models --within an integrant envelope-- more adapted to the problems they are meant to solve.It is described how a certain generic class of heterogeneous models leads to a satisfactory performance, comparable, and often better, to that of classical neural models, especially in the presence of heterogeneous information, imprecise or incomplete data, in a wide range of domains, most of them corresponding to real-world problems.

En la presente tesis se analiza el problema del coloreado de grafos tanto desde el punto de vista teórico como en relación a la resolución del problema mediante técnicas algorítmicas, algunas de las cuales se describen por vez primera. Se estudian asimismo distintas variaciones del problema simple del coloreado incluyendo el coloreado de vértices etiquetados, en que se asigna un número variable de colores a cada vértice, y el coloreado con aristas etiquetadas, en el que los colores asignados a vértices adyacentes deben guardar una distancia mayor o igual a la etiqueta de la arista que los une, así como combinaciones de ambos.Las técnicas descritas para el coloreado de grafos han sido posteriormente adaptadas a un problema de asignación de frecuencias en telefonía móvil habiéndose aplicado los algoritmos sobre distintos tipos de redes celulares. Las distintas redes analizadas pueden incorporar o no conmutación en frecuencia, variando la naturaleza del problema en cada caso. Para el caso de coloreado múltiple asociado al problema de asignación de frecuencias se ha descrito un conjunto de matrices asociadas a un grafo G(V,E) y un coloreado simple C que permiten reasignar colores a distintos vértices de G(V,E) aprovechando colores de C. Este reciclaje, en combinación con las métodos algorítmicos aplicados en coloreados simples, ha permitido resolver con eficiencia el problema del multicoloreado de grafos y en consecuencia el problema de asignación de frecuencias en redes celulares.En la segunda parte de la tesis se estudian las redes pequeño-mundo y se describen pautas deterministas para su obtención. De este modo se describe en primer lugar el modelo probabilista definido por Watts y Strogatz y se analiza la aparición de autoorganización crítica en las redes pequeño-mundo (caracterizadas por un apiñamiento elevado y un diámetro o distancia máxima entre vértices reducido) para a continuación ampliar el concepto sobre modelos deterministas. Se ha demostrado de este modo la posibilidad de obtener redes pequeño-mundo sobre grafos circulantes, mallas toroidales e hipercubos.Finalmente se ha probado la universalidad del efecto pequeño-mundo, es decir, la posibilidad de recortar arbitrariamente el diámetro de un grafo genérico G(V,E) sin que se produzcan variaciones significativas en su topología local (medida a partir del factor de clustering o apiñamiento del grafo), explicando así la ubicuidad de las redes pequeño-mundo y su descripción en entornos de todo tipo: social, biológico, industrial, matemático, etcétera.

La premi ere partie de cette th ese s'int eresse au groupage de tra c dans les r eseaux de t el ecommunications. La notion de groupage de tra c correspond a l'agr egation de ux de faible d ebit dans des conduits de plus gros d ebit. Cependant, a chaque insertion ou extraction de tra c sur une longueur d'onde il faut placer dans le noeud du r eseau un multiplexeur a insertion/extraction (ADM). De plus il faut un ADM pour chaque longueur d'onde utilis ee dans le noeud, ce qui repr esente un co^ut d' equipements important. Les objectifs du groupage de tra c sont d'une part le partage e cace de la bande passante et d'autre part la r eduction du co^ut des equipements de routage. Nous pr esentons des r esultats d'inapproximabilit e, des algorithmes d'approximation, un nouveau mod ele qui permet au r eseau de pouvoir router n'importe quel graphe de requ^etes de degr e born e, ainsi que des solutions optimales pour deux sc enarios avec tra c all-to-all: l'anneau bidirectionnel et l'anneau unidirectionnel avec un facteur de groupage qui change de mani ere dynamique. La deuxi eme partie de la th ese s'interesse aux probl emes consistant a trouver des sousgraphes avec contraintes sur le degr e. Cette classe de probl emes est plus g en erale que le groupage de tra c, qui est un cas particulier. Il s'agit de trouver des sous-graphes d'un graphe donn e avec contraintes sur le degr e, tout en optimisant un param etre du graphe (tr es souvent, le nombre de sommets ou d'ar^etes). Nous pr esentons des algorithmes d'approximation, des resultats d'inapproximabilit e, des etudes sur la complexit e param etrique, des algorithmes exacts pour les graphes planaires, ainsi qu'une m ethodologie g en erale qui permet de r esoudre e cacement cette classe de probl emes (et de mani ere plus g en erale, la classe de probl emes tels qu'une solution peut ^etre cod e avec une partition d'un sous-ensemble des sommets) pour les graphes plong es dans une surface. Finalement, plurieurs annexes pr esentent des r esultats sur des probl emes connexes.

En les xarxes IP/MPLS sobre WDM on es transporta gran quantitat d'informacio, la capacitat de garantir que el trafic arriba al node de desti ha esdevingut un problema important, ja que la fallada d'un element de la xarxa pot resultar en una gran quantitat d'informacio perduda. Per garantir que el trafic afectat per una fallada arribi al node desti, s'han definit nous algoritmes d'encaminament que incorporen el coneixement de la proteccio en els dues capes: l'optica (WDM) i la basada en paquets (IP/MPLS). D'aquesta manera s'evita reservar recursos per protegir el trafic a les dues capes. Els nous algoritmes resulten en millor us dels recursos de la xarxa, ofereixen rapid temps de recuperacio, eviten la duplicacio de recursos i disminueixen el numero de conversions del trafic de senyal optica a electrica. / The use of optical technology in core networks combined with IP/Multi-Protocol Label Switching (MPLS) solution has been presented as a suitable choice for the next generation Internet architecture. The integration of both layers is facilitated by the development of Generalized MPLS (GMPLS). In this network architecture, a single fibre failure can result in potentially huge data losses as the effects propagate up and through the network causing disruptions in the service of many applications. This research provides and evaluates new QoSP routing schemes that consider both IP/MPLS and optical network layers to compute the paths and backup paths subject to the QoS requirements of the traffic. Although effort has been devoted in developing multi-layer routing algorithms that consider all switching layers, protection is not considered amongst them. This is considered in this thesis. Where electrical to optical signal conversions have been reduded as well as the avoidance of traffic duplications resulting in better use of the network resources.

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.

La necesidad de resolver ecuaciones y sistemas de ecuaciones no lineales surge de manera natural en discretizar las ecuaciones integro-diferenciales que modelan los problemas de los que se encargan las diferentes ramas de las ciencias y la ingeniería. Actualmente, se puede hacer uso de los ordenadores como herramientas para facilitar todas las tareas en torno a su resolución. Con la mejora de los dispositivos, el desarrollo de las técnicas de computación y la aritmética de precisión variable, se ha generalizado la demanda de métodos iterativos que resuelvan de forma rápida y eficiente las ecuaciones y sistemas de ecuaciones. El Análisis Numérico es la rama de las matemáticas que responde a estos requerimientos. En este trabajo trataremos algunos aspectos de interés de esta área. En concreto, mostraremos una aproximación de la derivada que nos permita modificar un resultado para obtener métodos de orden p+2 a partir de otras de orden p, de modo que se mantengan las propiedades de convergencia y estudiaremos la mejora de la eficiencia de esta técnica, debido al menor número de evaluaciones funcionales, aplicada a métodos de diferente orden. Otro resultado se ha alcanzado generalizando el método de Sharma, y generando así familias de métodos de orden 4 óptimos y de orden 6; con el estudio del número de operaciones obtendremos los dos métodos más eficientes de la familia de los que estudiaremos su dinámica. Otra línea de investigación consiste en el estudio de las diversas estrategias para aproximar el cálculo de las jacobiana, así los operadores de diferencias divididas han contribuido a estos objetivos. Nosotros hemos desarrollado un operador de diferencias divididas que, a pesar de ser más sencillo que otros ya conocidos, conserva las propiedades de convergencia de los métodos con derivadas. Posteriormente hemos adaptado las familias de métodos de orden 4 y 6 para ecuaciones con raíces múltiples obteniendo también métodos libres de derivadas aplicando el operador en diferencias divididas anteriores. A continuación hemos considerado hemos realizado el estudio del comportamiento dinámico de ciertos métodos aplicados sobre el problema de los N cuerpos. Finalmente hemos obtenido ciertos resultados referentes a la convergencia semilocal. Los resultados teóricos se han contrastado con diversas experiencias numéricas. / The need to solve equations and systems of nonlinear equations arises naturally in discretizing the integro-differential equations that model the problems that are responsible for the different branches of science and engineering. Currently, computers can be used as tools to facilitate all tasks related to their resolution. With the improvement of the devices, the development of computing techniques and variable accuracy arithmetic, the demand for iterative methods has been generalized to solve the equations and equation systems quickly and efficiently. Numerical Analysis is the branch of mathematics that meets these requirements. In this paper we will discuss some aspects of interest in this area. In particular, we will show an approximation of the derivative that allows us to modify a result to obtain methods of order p+2 from others of order p, so that the convergence properties are maintained and we will study the improvement of the efficiency of this technique, due to the smallest number of functional evaluations, applied to methods of different order. Another result has been achieved by generalizing the Sharma method, and thus constructing families of order 4 optimal and order methods 6; With the study of the number of operations, we will obtain the two most efficient methods of the family from which we will study its dynamics. Another line of research consists in the study of the various strategies to approximate the calculation of the Jacobins, thus the operators of divided differences have contributed to these objectives. We have developed a divided difference operator that, while being simpler than other ones already known, maintains the convergence properties of methods with derivatives. Later we have adapted families of order methods 4 and 6 for equations with multiple roots, also obtaining derivative free methods by applying the operator in previous divided differences. Below we have considered that we have done the study of the dynamic behavior of certain methods applied to the problem of the N-bodies. Finally we have obtained certain results referring to semilocal convergence. The theoretical results have been contrasted with several numerical experiences. / La necessitat de resoldre equacions i sistemes d'equacions no lineals sorgeix de manera natural en discretitzar les equacions integrodiferencials que modelen els problemes dels quals s'encarreguen les diferents branques de les ciències i l'enginyeria. Actualment, es pot fer ús dels ordinadors com a eines per facilitar totes les tasques entorn a la seua resolució. Amb la millora dels dispositius, el desenvolupament de les tècniques de computació i l'aritmètica de precisió variable, s'ha generalitzat la demanda de mètodes iteratius que resolguen de forma ràpida i eficient les equacions i sistemes d'equacions. L'Anàlisi Numèrica és la branca de les matemàtiques que respon a aquestos requeriments. En aquest treball tractarem alguns aspectes d'interés d'aquesta àrea. En concret, mostrarem una aproximació de la derivada que ens permeta modificar un resultat per obtenir mètodes d'ordre p+2 a partir d'altres d'ordre p, de manera que es mantinguen les propietats de convergència i estudiarem la millora de l'eficiència d'aquesta tècnica, degut al menor nombre d'avaluacions funcionals, aplicada a mètodes de diferent ordre. Un altre resultat s'ha assolit generalitzant el mètode de Sharma, i construint així famílies de mètodes d'ordre 4 òptims i d'ordre 6; amb l'estudi del nombre d'operacions obtindrem els dos mètodes més eficients de la família dels quals estudiarem la seua dinàmica. Una altra línia d'investigació consisteix en l'estudi de les diverses estratègies per aproximar el càlcul de les jacobianes, així els operadors de diferències dividides han contribuït a aquests objectius. Nosaltres hem desenvolupat un operador de diferències dividides que, tot i ser més senzill que d'altres ja coneguts, manté les propietats de convergència dels mètodes amb derivades . Posteriorment hem adaptat les famílies de mètodes d'ordre 4 i 6 per a equacions amb arrels múltiples obtenint també mètodes lliures de derivades aplicant l'operador en diferències dividides anteriors. A continuació hem considerat hem realitzat l'estudi del comportament dinàmic de certs mètodes aplicats sobre el problema dels N cossos. Finalment hem obtingut certs resultats referents a la convergència semilocal. Els resultats teòrics s'han contrastat amb diverses experiències numèriques. / Teruel Ferragud, C. (2018). Desenvolupament de nous mètodes per a la resolució d'equacions i sistemes d'equacions no lineals i Aplicacions [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/107325 / TESIS