En esta tesis doctoral se presenta TAP (Trusted and Active Protocol PDU transfer), una arquitectura para redes de tecnología ATM, novedosa por sus características distribuida, activa y multiagente. El protocolo propuesto para la arquitectura ofrece transferencias garantizadas a un conjunto privilegiado de conexiones VPI/VCI. Se propone también una extensión de la capa AAL-5 de ATM que hemos denominado EAAL-5 (Extended AAL type 5) usada para la gestión de las conexiones privilegiadas extremo-extremo.TAP ofrece garantía de servicio (GoS) cuando la red está perdiendo células ATM y aprovecha los periodos de inactividad en los enlaces para realizar las retransmisiones de las CPCS-PDU-EAAL-5. El protocolo propuesto emplea mecanismos NACK (mediante células RM de retorno) y es soportado por conmutadores ATM activos equipados con una memoria de almacenamiento de PDU denominada DMTE (Dynamic Memory to store Trusted native EAAL-5 PDU). La arquitectura activa propuesta está basada en un SMA (Sistema Multiagente) constituido por agentes programables colaborativos y distribuidos en la red. Las simulaciones realizadas demuestran la efectividad del mecanismo de recuperación de PDU propuesto con un mejor goodput en la red.La arquitectura TAP es soportada sobre conmutadores ATM activos que denominamos AcTMs (Active Asynchronous Transfer Mode Switch) y que hemos diseñado con técnicas software para: garantizar la gestión justa de colas de entrada basadas en WFQ (Weighted Fair Queueing); realizar el control de congestiones del buffer inspirado en EPD (Early Packet Discard); y evitar, con VC Merge, la mezcla de las PDU de conexiones diferentes. Estas técnicas software se proponen, por tanto, con la intención de: distribuir de forma justa la carga de los conmutadores; optimizar las retransmisiones de PDU; aliviar la implosión sobre las fuentes; evitar la fragmentación de las PDU y disminuir el interleaving de células, optimizando el goodput.Los conmutadores AcTMs requieren también el hardware apropiado para soportar TAP. Para ello, además del buffer, se proponen, la memoria DMTE y un conjunto de tablas de E/S asociadas a cada uno de los puertos de los AcTMs. Se demuestra que estos requerimientos hardware son realistas y viables para ser incorporados en los conmutadores activos. Destacamos el carácter multidisciplinar de esta tesis, donde la base de las investigaciones es la ingeniería de protocolos ATM, complementada con las novedosas ventajas que los agentes software pueden aportar. No obstante, los conmutadores finalmente obtenidos podrían ser objeto del ámbito de las arquitecturas especializadas, de forma que varios módulos del prototipo presentado, podrían ser implementados como componentes hardware para optimizar su rendimiento.Una vez identificadas las limitaciones de la tecnología ATM para soportar las transferencias garantizadas, que son nuestro principal objetivo, se describe la motivación general de estas investigaciones en entornos donde ATM es la base del tráfico IP. De este modo, se emplea NS (Network Simulator) para el estudio de escenarios donde el protocolo TAP puede aportar importantes beneficios al conocido protocolo TCP.Para poder estudiar el comportamiento de todas estas propuestas hemos implementado un simulador de TAP que aprovecha las ventajas que aporta el lenguaje Java para el desarrollo de protocolos de comunicaciones y de SMA. Este simulador permite definir múltiples escenarios y analizar los resultados de la simulación del prototipo para poder llegar a una serie de interesantes conclusiones. Las simulaciones a través de fuentes ON/OFF analizan conexiones punto-a-punto y punto-a-multipunto usando clases, objetos, threads, sincronizaciones y procesos distribuidos implementados en lenguaje Java.La memoria de tesis doctoral ha sido organizada en tres grandes apartados con el objeto de estructurar adecuadamente los contenidos presentados. La Parte I está dedicada a analizar las investigaciones relacionadas con este trabajo, de forma que se describen en siete capítulos los aspectos básicos de la tecnología ATM y se aprovecha cada uno de los capítulos para presentar resumidamente nuestras aportaciones, las cuales son ampliadas en las Partes II y III. De este modo, comenzamos destacando en el Capítulo 1 los fundamentos de la tecnología, para pasar después a describir en el Capítulo 2 una taxonomía de arquitecturas y protocolos para las redes ATM que nos sirven para identificar la propuesta TAP cuya arquitectura básica es incluida al final del capítulo. El Capítulo 3 se centra en los conceptos de fiabilidad y garantía de servicio (GoS) destacando éste último, ya que es una de nuestras propuestas a los parámetros generales de calidad de servicio (QoS) y que se deriva de éstos. Así, se explica el mecanismo con el que se ofrece la GoS a las fuentes privilegiadas. Seguidamente, el Capítulo 4 se centra en el control de congestión y la justicia, ambos aplicados sobre las colas de entrada de los conmutadores ATM. Éstos son también dos aspectos básicos en nuestra propuesta para conseguir aportar soluciones al problema de las congestiones en las fuentes privilegiadas, pero garantizando además la justicia a aquellas fuentes que no lo son. Una vez estudiadas las propuestas de la literatura se presenta un esquema de nuestro algoritmo QPWFQ. El Capítulo 5 estudia los diversos mecanismos de control de congestión aplicados sobre el buffer de los conmutadores y, después de analizar las propuestas más extendidas, comentamos nuestro algoritmo EPDR inspirado en EPD para conseguir atender las solicitudes de retransmisión de las PDU congestionadas. En el Capítulo 6 se realiza una revisión de la literatura en materia de agentes software orientada hacia las redes de comunicaciones, con la intención de centrar adecuadamente el SMA que proponemos como soporte de TAP y con el objetivo de conseguir una red activa formada por conmutadores AcTMs cuya arquitectura es adelantada al final de este capítulo. El Capítulo 7 justifica el carácter distribuido del protocolo TAP sobre una VPN (Virtual Private Network) constituida por nodos AcTMs que coexisten con conmutadores no activos en la misma red. En resumen, la Parte I trata de justificar nuestras propuestas, reafirmándolas sobre los propios fundamentos de la tecnología actual.La Parte II identifica las motivaciones generales de esta tesis, partiendo de las limitaciones actuales de la tecnología ATM que se pretenden solventar con la propuesta de TAP. Esta parte se ha dividido en dos capítulos, dedicándose el Capítulo 8 a describir las motivaciones generales, de modo que el control de congestión en los nodos de la red no sólo beneficia al tráfico ATM nativo, sino que puede ser también de utilidad para protocolos tan extendidos como TCP. Se identifican, por tanto, los beneficios aportados por TAP a las redes actuales. En el Capítulo 9 se discuten las limitaciones de ATM frente al parámetro de GoS propuesto y se explica cómo TAP puede evitar problemas tan indeseables como la fragmentación de las PDU, el interleaving del tráfico, las retransmisiones extremo-extremo y la implosión en las fuentes de tráfico.El objetivo de la Parte III es detallar las soluciones propuestas, de forma que en cuatro capítulos se realiza una descripción detallada, tanto de la arquitectura, como del protocolo que se implementa sobre ella. El Capítulo 10 describe la arquitectura distribuida y multiagente TAP, relacionándola con el modelo arquitectónico ATM, y analizando cada uno de los componentes hardware y software de los conmutadores AcTMs. El Capítulo 11 se centra específicamente en detallar el conjunto de algoritmos que constituyen el protocolo TAP y, por tanto, en el SMA que lo constituye. También se formaliza la idea intuitiva de aprovechar los tiempos de inactividad de la red para atender las retransmisiones de las PDU congestionadas. El Capítulo 12 presenta los detalles de implementación del simulador de TAP que proponemos como prototipo para analizar los resultados obtenidos en diversos escenarios. Se argumenta la elección del lenguaje Java como herramienta para el desarrollo de protocolos y SMA, para pasar después a describir la metodología y las decisiones de diseño más importantes, así como de las clases Java más destacables del prototipo. Este capítulo concluye con el análisis de los resultados más significativos de las simulaciones. Por último, el Capítulo 13 se dedica a identificar líneas futuras de acción que aporten continuidad al conjunto de investigaciones de las que ha sido objeto esta tesis doctoral. / In this doctoral thesis, TAP (Trusted and Active Protocol PDU Transfer) is presented as an innovative architecture for ATM networks due to its active multi-agent and distributive characteristics. The protocol proposed for this architecture offers guaranteed transfer of a privileged group of VPI/VCI connections. We also propose an extension of the AAL-5 layer of ATM which we have called EAAL-5 ( Extended AAL type 5) which is used for the management of privileged end-to end connections.TAP offers Guarantee of Service (GoS) when the network is losing ATM cells and it takes advantage of the inactive periods in the links in order to retransmit the CPCS-PDU-EAAL-5. The protocol we propose uses NACK mechanisms (using backwards RM cells) and is supported by active ATM switches that have a PDU storage memory called DMTE (Dynamic Memory to store Trusted Native EAAL-5 PDU).Our proposed active architecture is based on a MAS (Multi-Agent System) formed by programmable collaborative agents, distributed in the network. The simulations carried out have proved the effectiveness of the PDU recovery mechanism that we have proposed for a better goodput in the net.The TAP architecture is supported over active ATM switches which we have called AcTMs (Active Asynchronous Transfer Mode Switch) and which we have designed with software technology in order to:· guarantee the fair management of entry queues based on WFQ (Weighted Fair Queueing);· manage the control of buffer congestion, using a device inspired by EPD (Early Packet Discard)· and prevent, with VCmerge, the mixing of PDUs coming from different connections.We therefore propose this software technology in order to: fairly distribute the load on the switches; optimize the PDU retransmissions; alleviate the implosion on the sources; prevent PDU fragmentation and decrease the interleaving of cells, thereby optimizing goodput.The AcTM switches also need the appropriate hardware in order to support TAP. Therefore, we propose not only the buffer but also DMTE memory and a set of I/O tables that go with each AcTM port. It has been proved that these hardware requirements are realistic and viable and can be integrated in the active switches. We would also like to point out the multidisciplinary nature of this thesis in which the basis of the research is ATM protocol engineering, complemented by the innovative advantages that the software agents can provide. Nevertheless, the switches that we have finally managed to obtain could be regarded as within the field of specialized architectures; thus several modules of the prototype we have presented could be implemented as hardware components in order to optimize performance.Once the limitations of ATM technology in supporting guaranteed transfer have been identified, which is our principal objective, we describe the general motive for this research in environments where ATM is the basis of IP traffic. An NS (Network Simulator) has thus been used in order to study scenarios in which TAP protocol can significantly improve the already familiar TCP protocol.In order to study the performance of all these proposed improvements, we have used a TAP simulator, which has the advantages that Java language offers for the development of MAS and communication protocols. This simulator can define a variety of scenarios and analyse the results of the simulation of the prototype thus reaching a series of interesting conclusions. The simulations, via ON/OFF sources, analyse point-to-point and point-to-multipoint connections using classes, objects, threads, synchronizations and distributed processes carried out under Java.This dissertation has been organized in three parts in order to adequately structure the contents presented. Part I analyses the research related to this work; thus the first seven chapters describe the basic aspects of ATM technology. Each chapter briefly presents our contributions, which are studied in greater detail in Parts II and III.Thus, in Chapter 1 we point out the basic concepts of this technology and, in Chapter 2, we describe a taxonomy of architectures and protocols for ATM networks which will serve to identify our TAP proposal whose basic architecture is included at the end of the chapter.Chapter 3 deals with the concepts of reliability and GoS, with an emphasis on the latter since this is one of our proposals for the improvement of the general parameters of Quality of Service (QoS). Thus, we explain the mechanism, which is used in order to provide GoS to privileged sources.Following this, Chapter 4, deals with congestion control and fairness, which are applied to ATM switch entry queues. These concepts are also two basic aspects of our proposal to provide solutions to the problem of congestion at privileged sources, while -at the same time- guaranteeing fairness to those sources, which are not privileged. After studying the proposals that have already been published in this area of research, we present an outline of our QPWFQ (Queue PDU Weighted Fair Queueing) algorithm.In Chapter 5 we study the various congestion control mechanisms applied to switch buffers (that already exist) and, after analysing the most common proposals and solutions, we describe our EPDR (Early Packet Discard and Relay) algorithm inspired by EPD and which aims to attend the retransmission requests of congested PDUs.Chapter 6 reviews the literature on software agents designed for communication networks since we intend to explain the relevance of the MAS that we propose as a support for TAP. Thus, our objective is to obtain an active network formed by AcTMs switches whose architecture is outlined at the end of the chapter.In Chapter 7 we justify the distributive characteristics of the TAP protocol over a VPN (Virtual Private Network) formed by AcTMs nodes which exist side by side with non-active switches in the same network.Thus, in Part I we intend to justify our proposals by basing them on the fundamentals of the present technology.Part II describes the general motivation of this thesis, beginning with an analysis of the present limitations of ATM technology, which we propose to solve by using TAP. This part is divided into two chapters: Chapter 8 describes our general objectives whereby the control of congestion at the network nodes not only benefits native ATM traffic but can also be of use for such widespread protocols as TCP. We thus point out the advantages that TAP can provide for present-day networks.In Chapter 9 the limitations of ATM are discussed vis a vis the GoS parameter we have proposed and we explain how TAP can avoid such undesirable problems as PDU fragmentation, traffic interleaving, end-to-end retransmissions and the implosion of traffic sources.The objective of Part III is a comprehensive description of the solutions that we propose and, in the following four chapters, we provide a detailed description both of the architecture and of the protocol that goes with it.Chapter 10 describes the TAP distributed, multi-agent architecture, relating it to the ATM architectural model and analysing each of the hardware and software components of the AcTMs switches.Chapter 11 specifically focuses on the exhaustive description of the complete set of algorithms that make up the TAP protocol and therefore within the MAS which constitutes it. Moreover, the intuitive idea of making use of the periods of inactivity in the network in order to deal with the retransmissions of congested PDUs is formalized as a theory.In Chapter 12 we present the details of the implementation of the TAP simulator proposed as a prototype in order to analyse the results obtained under different scenarios. We argue in favour of the choice of Java language as a tool for the development of protocols and MAS and we then describe the methodology and the most important decisions concerning design as well as the most outstanding classes of Java used in the prototype. This chapter ends with an analysis of the most significant results of the simulations.Finally, Chapter 13 focuses on identifying future lines of action that would give continuity to the whole range of research which has been the object of study of this doctoral thesis.

El objetivo de la tesis "Modelos para Comercio Electrónico basados en Sistemas Intermediarios" es el estudio, desarrollo y aplicación de una serie de modelos para sistemas de comercio electrónico abiertos que utilicen un intermediario electrónico y que contemplen todos los aspectos relacionados con la comercialización mediante medios electrónicos, de cualquier tipo de bienes.La primera parte presenta el estado del arte del comercio electrónico centrado en el análisis de las propuestas internacionales existentes en la actualidad para caracterizar un sistema abierto de comercio electrónico mediante modelos. En la segunda parte se describen las aportaciones de la tesis relacionadas con el desarrollo de una serie de modelos que sirvan para caracterizar los sistemas de comercio electrónico, especialmente los basados en intermediarios electrónicos. La tercera parte contiene las conclusiones de la tesis, las líneas de investigación abiertas y las referencias bibliográficas.En la primera parte correspondiente al estado del arte, se describen los siguientes modelos para sistemas de comercio electrónico desarrollados por diferentes iniciativas internacionales como son, EBES Buildings Blocks for Electronic Commerce, EWOS Technical Guide on Electronic Commerce, ECDTF-OMG/CommerceNet Joint Electronic Commerce Reference Model, eCo Framework (CommerceNet), IOTP (Internet Open Trading Protocol), OBI (Open Buying on the Internet), JEPI (Joint Electronic Payment Initiative) y SET (Secure Electronic Transaction). También se describen algunos proyectos europeos relacionados con el comercio electrónico y en especial aquellos basados en sistemas intermediarios, como son los proyectos ABS (An Architecture for Information Brokerage Services), ABROSE (Agent Based Brokerage Services in Electronic Commerce), COBRA (Common Brokerage Architecture), GAIA (Generic Architecture for Information Availability), OSM (An Open Service Model for Global Information) y SEMPER (A Security Framework for the Global Electronic Marketplace). Finalmente se describen algunos modelos existentes para sistemas electrónicos de gestión de derechos de la propiedad intelectual (IPR) de contenidos multimedia como los modelos de los proyectos europeos IMPRIMATUR, FILIGRANE y COPEARMS. En la segunda parte se desarrollan las principales contribuciones del trabajo de tesis. La primera contribución consiste en la caracterización de los sistemas de comercio electrónico en función de las actividades comerciales y los valores asociados. Se introducen también los conceptos de provisión de productos a medida y de servicios como una evolución de la clásica provisión de productosUna de las principales contribuciones de la tesis que consiste en caracterizar un sistema de comercio electrónico mediante un modelo jerárquico compuesto por tres niveles, modelo funcional, modelo operacional y modelo arquitectónico. Cada uno de estos niveles corresponde a una visión del sistema, desde la visión más general que corresponde al modelo funcional o de negocio, hasta el nivel de detalle relacionado con la implementación, que es el modelo arquitectónico, pasando por el nivel en el que se identifican las tareas necesarias en el sistema, que es el modelo operacional.Con el modelo funcional podemos identificar las entidades que intervienen en el modelo de negocio del sistema, cual es su rol y las relaciones entre ellas. La mayoría de modelos que hemos estudiado en el estado del arte se concentran en este tipo de modelo funcional que, aun siendo muy útil para abordar las primeras etapas de la caracterización del sistema, es claramente insuficiente para poder avanzar y acercarnos a niveles más próximos al diseño del sistema. De ahí la necesidad de introducir más niveles en la jerarquía de modelos.El modelo operacional permite identificar una serie de fases necesarias para llevar a cabo la actividad comercial. La mayor parte de los modelos analizados en el estado del arte sólo contemplan como fase final la de "acuerdo", que únicamente permite resolver el caso de la provisión de productos predefinidos o preexistentes. Una contribución de la tesis relacionada con el modelo operacional es la inclusión de una nueva fase de "postacuerdo" para aquellos sistemas de comercio electrónico en los que los bienes comercializados requieran un seguimiento posterior al acuerdo hasta la entrega final del producto elaborado a medida o del servicio encargado. Con la inclusión de la fase de postacuerdo podemos resolver la provisión de ambos tipos de bienes, es decir, productos a medida o servicios.Finalmente, el nivel de la jerarquía más relacionado con la tecnología es el modelo arquitectónico, con el que podemos identificar los módulos necesarios para implementar las operaciones que hemos descrito en el modelo operacional en función del tipo de sistema de que se trate. Cada uno de estos módulos arquitectónicos se implementarán en cada momento con la tecnología disponible más adecuada, de esta forma nuestra propuesta de modelos para sistemas de comercio electrónico no está ligada al estado de la tecnología en un momento determinado.Otra de las contribuciones de la tesis que consiste en una clasificación de los sistemas de comercio electrónico realizada en función del tipo de bienes que comercializa y que además nos da una idea de su complejidad. Mediante la clasificación hemos podido relacionar todas las aportaciones de la tesis descritas anteriormente, como son la identificación de las actividades comerciales, el modelo funcional y el modelo operacional. La clasificación consta de tres niveles, sistemas de comercio electrónico de productos (Nivel 1), sistemas de comercio electrónico de productos a medida (Nivel 2) y sistemas de comercio electrónico de servicios (Nivel 3).Con el objetivo de validar las aportaciones de la tesis descritas anteriormente, se han utilizado los modelos en la especificación y diseño de sistemas reales. Se describen dos casos reales en los que se ha podido validar la jerarquía de modelos propuesta en la tesis, se trata de dos proyectos europeos del programa ACTS, el proyecto MULTIMEDIATOR y el proyecto TRADE.Finalmente, describe un problema de los sistemas de comercio electrónico basados en intermediarios de mucho interés en la actualidad, como es la problemática asociada a la comercialización a través de la red de material sometido a derechos de autor y se hacen algunas propuestas de cómo abordar su solución. En este tipo de sistemas, el intermediario electrónico puede ser, por una parte, el elemento en el que compradores y vendedores depositen la confianza, pero también por otra parte, puede residir en el intermediario la responsabilidad de la comercialización y posterior seguimiento del cumplimiento de los acuerdos suscritos en el momento de la compra. Se hace una propuesta de un sistema, y una arquitectura asociada, para la negociación de las condiciones de comercialización de material sujeto a copyright (protocolo de negociación del IPR), la materialización del acuerdo negociado en un contrato electrónico específico para IPR y también mecanismos para el seguimiento de su cumplimiento. / The objective of the Ph. D. Thesis "Electronic Commerce Models based on Brokerage Systems" is the study, development and application of a series of models for open electronic commerce (e-commerce, in short) systems using a broker and considering all aspects related with the commercialisation, by electronic means, of any kind of goods.The first part presents the state-of-the-art of e-commerce, focussing on the analysis of the current international proposals for the characterisation of an open e-commerce system through models. The second part describes the contributions of the Thesis related to the development of a series of models to characterise e-commerce systems, mainly those based on electronic brokers. The third part contains the conclusions of the Thesis, the open research lines, and the bibliographic references.With respect to the state-of-the-art, the following models for e-commerce systems, developed by different international initiatives, are described: EBES Buildings Blocks for Electronic Commerce, EWOS Technical Guide on Electronic Commerce, ECDTF-OMG/CommerceNet Joint Electronic Commerce Reference Model, eCo Framework (CommerceNet), IOTP (Internet Open Trading Protocol), OBI (Open Buying on the Internet), JEPI (Joint Electronic Payment Initiative) and SET (Secure Electronic Transaction). Furthermore, some European projects related to e-commerce, and especially to brokerage systems, are also described, such as the ABS (An Architecture for Information Brokerage Services), ABROSE (Agent Based Brokerage Services in Electronic Commerce), COBRA (Common Brokerage Architecture), GAIA (Generic Architecture for Information Availability), OSM (An Open Service Model for Global Information) and SEMPER (A Security Framework for the Global Electronic Marketplace) projects. Finally, some existing models for the management of Intellectual Property Rights (IPR) of multimedia content are also described, such as the models coming from the European projects IMPRIMATUR, FILIGRANE and COPEARMS.In the second part, the main contributions of the work are developed. The first contribution consists on the characterisation of e-commerce systems according to the commercial activities and associated values. Also the concepts of customised products and services provision, as an evolution of the classical products provision, are introduced.One of the main contributions of the Thesis is the characterisation of an e-commerce system by means of a hierarchical model consisting of three levels: the functional, the operational, and the architectural models. Each of these models corresponds to a view of the system, from the more general one of the functional (or business) model, till the detailed level related to the implementation of the architectural model, going through the model that identifies the tasks needed in the system, that is the operational one.With the functional model we can identify the entities participating in the business model of the system, their role, and the relationships between them. Most of the models analysed in the state-of-the-art study concentrate in this kind of functional model, that, although very useful to cope with the first steps in the system characterisation, is clearly not enough to advance to levels closer to the system design. From this, the need to introduce more levels in the hierarchy of models.The operational model allows the identification of a series of phases needed to carry out the commercial activity. Most of the analysed models only consider as final phase the "agreement" one, that only allows to solve the case of the provision of existing or pre-defined products. A contribution of the Thesis in relation to the operational model is the inclusion of a "post-agreement" phase, for those e-commerce systems in which the commercialised goods require a follow-up after the agreement and until the final delivery of the customised product, or the agreed service. With the inclusion of the post-agreement step we can solve the provision of both kinds of goods, i.e., customised products or services.Finally, the level of the hierarchy more related to the technology is the architectural model, which allow us to identify the modules needed to implement the operations described in the operational model according to the kind of system. Each of these architectural modules will be implemented following the most adequate available technology. In this way, our proposal of models for e-commerce systems is independent from the technology.Another contribution of the Thesis consists on the classification of the e-commerce systems based on the kind of goods that they commercialise, giving also an idea of its complexity. With this classification, we have been able to inter-relate all the described contributions, i.e., the identification of the commercial activities, the functional model and the operational model. The classification consists of three levels: systems for e-commerce of products (Level 1), systems for e-commerce of customised products (Level 2), and systems for e-commerce of services (Level 3).With the objective of validating the contributions of the Thesis already described, we have used the models in the specification and design of real systems. We describe two real cases in which the proposed hierarchy of models has been validated. They are two European projects of the ACTS programme: the MULTIMEDIATOR project and the TRADE project.Finally, we deal with a problem of broker-based e-commerce systems, very relevent nowadays, that is the issue of the commercialisation through the network of multimedia material with property rights. We make some proposals about how to deal with this problem. In this kind of systems, the broker might be, on the one side, the element in which buyers and sellers trust, but, on the other hand, the broker might have the responsibility of the commercialisation and further follow-up of the fulfillment of the agreements reached at purchase moment. A proposal is made of a system, and an associated architecture, for the negotiation of the conditions for the commercialisation of copyrighted material (IPR negotiation protocol), the materialisation of the reached agrement in an electronic contract, specific for IPR, and also mechanisms for the control of its fulfillment.

El rendimiento de los actuales sistemas multiprocesador de memoria compartida depende tanto de la utilización eficiente de todos los componentes del sistema (procesadores, memoria, etc), como de las características del conjunto de aplicaciones a ejecutar. Esta Tesis tiene como principal objetivo mejorar la ejecución de conjuntos de aplicaciones paralelas en sistemas multiprocesador de memoria compartida mediante la utilización de información sobre el rendimiento de las aplicaciones para la planificación de los procesadores.Es una práctica común de los usuarios de un sistema multiprocesador reservar muchos procesadores para ejecutar sus aplicaciones asumiendo que cuantos más procesadores utilicen mejor rendimiento sacarán sus aplicaciones. Sin embargo, normalmente esto no es cierto. Las aplicaciones paralelas tienen diferentes características respecto a su escalabilidad. Su rendimiento depende además de parámetros que sólo son conocidos en tiempo de ejecución, como por ejemplo el conjunto de datos de entrada o la influencia que pueden ejercer determinadas aplicaciones que se ejecutan de forma concurrente.En esta tesis proponemos que el sistema no base sus decisiones solamente en las peticiones de recursos de los usuarios sino que él, dinámicamente, mida el rendimiento que están consiguiendo las aplicaciones y base, o ajuste, sus decisiones teniendo en cuenta esa información.El rendimiento de las aplicaciones paralelas puede ser medido por el sistema de forma dinámica y automática sin introducir una sobrecarga significativa en la ejecución de las aplicaciones. Utilizando esta información, la planificación de procesadores puede ser decidida, o ajustada, siendo mucho más robusta a requerimientos incorrectos por parte de los usuarios, que otras políticas que no consideran este tipo de información. Además de considerar el rendimiento, proponemos imponer una eficiencia objetivo a las aplicaciones paralelas. Esta eficiencia objetivo determinará si la aplicación está consiguiendo un rendimiento aceptable o no, y será usada para ajustar la asignación de procesadores. La eficiencia objetivo de un sistema podrá ser un parámetro ajustable dinámicamente en función del estado del sistema: número de aplicaciones ejecutándose, aplicaciones encoladas, etc.También proponemos coordinar los diferentes niveles de planificación que intervienen en la planificación de procesadores: Nivel librería de usuario, planificador de procesadores (en el S.O), y gestión del sistema de colas. La idea es establecer una interficie entre niveles para enviar y recibir información entre niveles, así como considerar esta información para tomar las decisiones propias de cada nivel.La evaluación de esta Tesis ha sido realizada utilizando un enfoque práctico. Hemos diseñado e implementado un entorno de ejecución completo para ejecutar aplicaciones paralelas que siguen el modelo de programación OpenMP. Hemos introducido nuestras propuestas modificando los tres niveles de planificación mencionados. Los resultados muestran que las ideas propuestas en esta tesis mejoran significativamente el rendimiento del sistema. En aquellos casos en que tanto las aplicaciones como los parámetros del sistema han sido previamente optimizados, las propuestas realizadas introducen una penalización del 5% en el peor de los casos, comparado con el mejor de los resultados obtenidos por otras políticas evaluadas. Sin embargo, en otros casos evaluados, las propuestas realizadas en esta tesis han mejorado el rendimiento del sistema hasta un 400% también comparado con el mejor resultado obtenido por otras políticas evaluadas.Las principales conclusiones que podemos obtener de esta Tesis son las siguientes: - El rendimiento de las aplicaciones paralelas puede ser medido en tiempo de ejecución. Los requisitos para aplicar el mecanismo de medida propuesto en esta Tesis son que las aplicaciones sean maleables y estar en un entorno de ejecución multiprocesador de memoria compartida. - El rendimiento de las aplicaciones paralelas debe ser considerado para decidir la asignación de procesadores a aplicaciones. El sistema debe utilizar la información del rendimiento para auto-ajustar sus decisiones. Además, el sistema debe imponer una eficiencia objetivo para asegurar el uso eficiente de procesadores.- Los diferentes niveles de planificación deben estar coordinados para evitar interferencias entre ellos / The performance of current shared-memory multiprocessor systems depends on both the efficient utilization of all the architectural elements in the system (processors, memory, etc), and the workload characteristics.This Thesis has the main goal of improving the execution of workloads of parallel applications in shared-memory multiprocessor systems by using real performance information in the processor scheduling.It is a typical practice of users in multiprocessor systems to request for a high number of processors assuming that the higher the processor request, the higher the number of processors allocated, and the higher the speedup achieved by their applications. However, this is not true. Parallel applications have different characteristics with respect to their scalability. Their speedup also depends on run-time parameters such as the influence of the rest of running applications.This Thesis proposes that the system should not base its decisions on the users requests only, but the system must decide, or adjust, its decisions based on real performance information calculated at run-time. The performance of parallel applications is information that the system can dynamically measure without introducing a significant penalty in the application execution time. Using this information, the processor allocation can be decided, or modified, being robust to incorrect processor requests given by users. We also propose that the system use a target efficiency to ensure the efficient use of processors. This target efficiency is a system parameter and can be dynamically decided as a function of the characteristics of running applications or the number of queued applications.We also propose to coordinate the different scheduling levels that operate in the processor scheduling: the run-time scheduler, the processor scheduler, and the queueing system. We propose to establish an interface between levels to send and receive information, and to take scheduling decisions considering the information provided by the rest of levels.The evaluation of this Thesis has been done using a practical approach. We have designed and implemented a complete execution environment to execute OpenMP parallel applications. We have introduced our proposals, modifying the three scheduling levels (run-time library, processor scheduler, and queueing system).Results show that the ideas proposed in this Thesis significantly improve the system performance. If the evaluated workload has been previously tuned, in the worst case, we have introduced a slowdown around 5% in the workload execution time compared with the best execution time achieved. However, in some extreme cases, with a workload and a system configuration not previously tuned, we have improved the system performance in a 400%, also compared with the next best time.The main results achieved in this Thesis can be summarized as follows:- The performance of parallel applications can be measured at run-time. The requirements to apply the mechanism proposed in this Thesis are to have malleable applications and shared-memory multiprocessor architectures.- The performance of parallel applications 1must be considered to decide the processor allocation. The system must use this information to self-adjust its decisions based on the achieved performance. Moreover, the system must impose a target efficiency to ensure the efficient use of processors.- The different scheduling levels must be coordinated to avoid interferences between levels.

En los últimos años, el diseño de procesadores de altas prestaciones ha progresado a lo largo de dos corrientes de investigación: incrementar la profundidad del pipeline para permitir mayores frecuencias de reloj, y ensanchar el pipeline para permitir la ejecución paralela de un mayor numero de instrucciones. Diseñar un procesador de altas prestaciones implica balancear todos los componentes del procesador para asegurar que el rendimiento global no esta limitado por ningún componente individual. Esto quiere decir que si dotamos al procesador de una unidad de ejecución mas rápida, hay que asegurarse de que podemos hacer fetch y decodificar instrucciones a una velocidad suficiente para mantener ocupada a esa unidad de ejecución.Esta tesis explora los retos presentados por el diseño de la unidad de fetch desde dos puntos de vista: el diseño de un software mas adecuado para las arquitecturas de fetch ya existente, y el diseño de un hardware adaptado a las características especiales del nuevo software que hemos generado.Nuestra aproximación al diseño de un suevo software ha sido la propuesta de un nuevo algoritmo de reordenación de código que no solo pretende mejorar el rendimiento de la cache de instrucciones, sino que al mismo tiempo pretende incrementar la anchura efectiva de la unidad de fetch. Usando información sobre el comportamiento del programa (profile data), encadenamos los bloques básicos del programa de forma que los saltos condicionales tendrán tendencia a ser no tomados, lo cual favorece la ejecución secuencial del código. Una vez hemos organizado los bloques básicos en estas trazas, mapeamos las diferentes trazas en memoria de forma que minimicen la cantidad de espacio requerida para el código realmente útil, y los conflictos en memoria de este código. Además de describir el algoritmo, hemos realizado un análisis en detalle del impacto de estas optimizaciones sobre los diferentes aspectos del rendimiento de la unidad de fetch: la latencia de memoria, la anchura efectiva de la unidad de fetch, y la capacidad de predicción del predictor de saltos.Basado en el análisis realizado sobre el comportamiento de los códigos optimizados, proponemos también una modificacion del mecanismo de la trace cache que pretende realizar un uso mas efectivo del escaso espacio de almacenaje disponible. Este mecanismo utiliza la trace cache únicamente para almacenar aquellas trazas que no podrían ser proporcionadas por la cache de instrucciones en un único ciclo.También basado en el conocimiento adquirido sobre el comportamiento de los códigos optimizados, proponemos un nuevo predictor de saltos que hace un uso extensivo de la misma información que se uso para reordenar el código, pero en este caso se usa para mejorar la precisión del predictor de saltos.Finalmente, proponemos una nueva arquitectura para la unidad de fetch del procesador basada en explotar las características especiales de los códigos optimizados. Nuestra arquitectura tiene un nivel de complejidad muy bajo, similar al de una arquitectura capaz de leer un único bloque básico por ciclo, pero ofrece un rendimiento muy superior, siendo comparable al de una trace cache, mucho mas costosa y compleja.

Les xarxes IP tradicionals utilitzen el model de transmissió "best-effort" per transportar tràfic entre clients de la xarxa. Aquest model de transmissió de tràfic no és el més adequat per les aplicacions en temps real com per exemple, vídeo sota demanda, conferències multimedia o realitat virtual que per altra banda tenen cada cop més adeptes entre els clients de la xarxa. A fi de garantir el correcte funcionament d'aquest tipus d'aplicacions, l'estructura de la xarxa ha de ser substancialment modificada amb l'objectiu final de poder optimitzar els seus propis recursos i així poder fer front a aquells tipus de tràfics i de clients que requereixen certes garanties de "Qualitat de Servei" (QoS) per a la seva correcta transmissió.Aquestes modificacions o millores de la xarxa poden ser perfectament realitzades sota l'entorn d'Enginyeria de Tràfic (Traffic Engineering, TE). Dos són els principals aspectos relacionats amb el funcionament de la xarxa en aquest entorn de TE: els mecanismes de commutació i els mecanismes d'encaminament. Així, per una banda es necessita un mecanisme de commutació molt ràpid en els nodes interns de la xarxa a fi de que els paquets de dades puguin ser processats amb el menor temps possible. En xarxes IP aquest objectiu s'aconsegueix amb el Multiprotocol Label Switching (MPLS). Per altra banda, a fi de garantir certa QoS, les decisions d'encaminament s'han de realitzar tenint en compte quines són les restriccions de QoS sol·licitades per el node client que origina el tràfic. Aquest objectiu s'aconsegueix modificant els esquemes d'encaminament tradicionals, incorporant-hi els paràmetres de QoS en les decisions d'encaminament, generant el que es coneix com algorismes d'encaminament amb QoS (QoS routing).Centrant-nos en aquest darrer aspecte, la majoria dels algorismes d'encaminament amb QoS existents, realitzen la selecció de la ruta a partir de la informació d'estat de l'enllaç emmagatzemada en les bases de dades d'estat de l'enllaç contingudes en els nodes. Per poder garantir que els successius canvis en l'estat de la xarxa estiguin perfectament reflectits en aquesta informació d'encaminament, el protocol d'encaminament ha d'incloure un mecanisme d'actualització que faci possible garantir que la selecció de les rutes es fa a partir d'informació acurada de l'estat real de la xarxa. En un entorn IP tradicional, el qual inicialment no inclou paràmetres de QoS, els canvis produïts en la informació d'encaminament són tan sols deguts a modificacions en la topologia i connectivitat de la xarxa. En aquest entorn, donat que la freqüència en la qual s'espera rebre missatges advertint d'aquestes modificacions no és elevada, la majoria dels mecanismes d'actualització es basen en la inclusió d'un cert període de refresc. Així, les bases de dades s'actualitzen periòdicament mitjançant la distribució d'uns missatges que informen a la resta de nodes de l'estat de la xarxa,a fi de que cada node pugui actualitzar la seva base de dades.No obstant això, hem de tenir en compte que en aquelles xarxes IP/MPLS altament dinàmiques amb requeriments de QoS, aquest mecanisme d'actualització basat en un refresc periòdic no serà útil. Això és degut a la rigidesa que presenta aquest mecanisme, la qual fa que no sigui aplicable a un entorn que presenti contínues variacions del paràmetres dels enllaços cada cop que s'estableixi o s'alliberi una connexió (ara a més de la topologia i connectivitat, s'inclouen paràmetres de QoS, com ampla de banda, retard, variació del retard, etc.). Per tot això, s'haurà de generar un mecanisme d'actualització molt més eficient que sigui capaç de mantenir les bases de dades dels nodes perfectament actualitzades reflectint els continus canvis en l'estat de la xarxa. L'alta granularitat d'aquest mecanisme provocarà una sobrecàrrega de la xarxa, degut a l'enorme quantitat de missatges d'actualització que seran necessaris per poder mantenir informació actualitzada en les bases de dades d'estat de l'enllaç en cada node.Per reduir aquesta sobrecàrrega de senyalització apareixen les polítiques d'activació (triggering policies) que tenen per objectiu determinar en quin moment un node ha d'enviar un missatge d'actualització a la resta de nodes de la xarxa advertint-los de les variacions produïdes en els seus enllaços. Desafortunadament, l'ús d'aquestes polítiques d'activació produeix un efecte negatiu sobre el funcionament global de la xarxa. En efecte, si l'actualització de la informació de l'estat de l'enllaç en els nodes no es fa cada cop que aquesta informació es veu modificada, sinó que es fa d'acord a una certa política d'activació, no es podrà garantir que aquesta informació representi de forma acurada l'esta actual de la xarxa en tot moment. Això pot provocar una selecció no òptima de la ruta seleccionada i un increment en la probabilitat de bloqueig de noves connexions a la xarxa. / Las redes IP tradicionales utilizan el modelo de transmisión best-effort para transportar tráfico entre clientes de la red. Es bien sabido que este modelo de transmisión de tráfico no es el más adecuado para las aplicaciones en tiempo real, tales como video bajo demanda, conferencias multimedia o realidad virtual, que cada vez son más de uso común entre los clientes de la red. Para garantizar el correcto funcionamiento de dichas aplicaciones la estructura de la red debe ser modificada a fin de optimizar la utilización de sus propios recursos y para poder hacer frente a aquellos tráficos que requieran ciertas garantías de Calidad de Servicio (QoS) para su correcta transmisión.Estas modificaciones o mejoras de la red pueden ser perfectamente realizadas bajo el entorno de Traffic Engineering (TE). Dos son los principales aspectos relacionados con el funcionamiento de la red en el entorno de TE: los mecanismos de conmutación y los mecanismos de encaminamiento. Así, por una parte, se necesita un mecanismo de conmutación muy rápido en los nodos intermedios de la red a fin de que los paquetes de datos puedan ser procesados con el menor tiempo posible. En redes IP este objetivo se consigue con el Multiprotocol Label Switching (MPLS). Por otra parte a fin de garantizar cierta QoS, las decisiones de encaminamiento se deben realizar acorde con los parámetros de QoS requeridos por el cliente que origina tráfico. Este objetivo se consigue modificando los esquemas de encaminamiento tradicionales e incorporando parámetros de QoS en las decisiones de encaminamiento, lo que deriva en la generación de encaminamiento con QoS (QoS routing).Centrándonos en este último aspecto de encaminamiento, la mayoría de los algoritmos de QoS routing existentes realizan la selección de la ruta a partir de la información de estado del enlace que está almacenada en las bases de datos de estado del enlace contenidas en los nodos. A fin de garantizar que los sucesivos cambios en el estado de la red estén perfectamente reflejados en dicha información, el mecanismo de encaminamiento debe incorporar un mecanismo de actualización cuyo objetivo sea garantizar que las decisiones de encaminamiento se realizan a partir de información fidedigna del estado de la red. En un entorno IP tradicional, el cual no incluye parámetros de QoS, los cambios producidos en dicha información son los debidos a modificaciones en la topología y conectividad. En dicho entorno dado que no son esperadas frecuentes variaciones de la topología de la red, la mayoría de los mecanismos de actualización están basados en la inclusión de un cierto periodo de refresco.Sin embargo, en redes IP/MPLS altamente dinámicas con requerimientos de QoS, este mecanismo de actualización no será adecuado debido a su rigidez y a las continuas variaciones de los parámetros de los enlaces (que ahora incluirá parámetros de QoS, tales como, ancho de banda, retardo, variación del retado, etc.) que se producirán cada vez que se establezca/libere una conexión. Por tanto, se deberá generar un mecanismo de actualización mucho más eficiente que sea capaz de actualizar las bases de datos de los nodos a fin de reflejar las constantes variaciones del estado de la red. La alta granularidad de este mecanismo provocará una sobrecarga de la red, debido a la enorme cantidad de mensajes de actualización necesarios para mantener información actualizada del estado de la red. Para reducir esta sobrecarga de señalización aparecen las políticas de disparo (triggering policies), cuyo objetivo es determinar en qué momento un nodo debe enviar un mensaje de actualización al resto de nodos de la red advirtiéndoles de las variaciones producidas en sus enlaces.Desafortunadamente el uso de dichas políticas de disparo produce un efecto negativo sobre el funcionamiento global de la red. En efecto, si la actualización de la información de estado del enlace en los nodos no se realiza cada vez que dicha información es modificada sino de acuerdo con cierta política de disparo, no se puede garantizar que dicha información represente fielmente el estado de la red. Así, la selección de la ruta, podrá ser realizada basada en información inexacta o imprecisa del estado de lo red, lo cual puede provocar una selección no óptima de la ruta y un incremento en la probabilidad de bloqueo de la red.Esta Tesis se centra en definir y solucionar el problema de la selección de rutas bajo información inexacta o imprecisa de la red (routing inaccuracy problem). Se consideran dos escenarios de trabajo, las actuales redes MPLS y las futuras redes WDM, para los cuales se propone un nuevo mecanismo de encaminamiento: BYPASS Based Routing (BBR) para redes IP/MPLS y BYPASS Based Optical Routing (BBOR) para redes WDM. Ambos mecanismos de encaminamiento se basan en un concepto común denominado "bypass dinámico".El concepto de "bypass dinámico" permite que un nodo intermedio de la red encamine el mensaje de establecimiento que ha recibido del nodo fuente, a través de una ruta distinta a la calculada por el nodo fuente (y explícitamente indicada en el mensaje de establecimiento), cuando detecte que inesperadamente el enlace de salida no dispone de recursos suficientes para soportar las garantías de QoS requeridas por la conexión a establecer. Estas rutas alternativas, denominadas bypass-paths, son calculadas por el nodo fuente o de entrada a la red simultáneamente con la ruta principal para ciertos nodos intermedios de la misma. En redes IP/MPLS el mecanismo BBR aplica el concepto de "bypass dinámico" a las peticiones de conexión con restricciones de ancho de banda. En cambio, en redes WDM, el mecanismo BBOR aplica el concepto de "bypass dinámico" a la hora de asignar una longitud de onda por la cual se va a transmitir el trafico. / Traditional IP networks are based on the best effort model to transport traffic flowsbetween network clients. Since this model cannot properly support the requirements demanded by several emerging real time applications (such as video on demand, multimedia conferences or virtual reality), some modifications in the network structure, mainly oriented to optimise network performance, are required in order to provide Quality of Service (QoS) guarantees.Traffic Engineering is an excellent framework to achieve these network enhancements.There are two main aspects in this context that strongly interact with network performance: switching mechanisms and routing mechanisms. On one hand, a quick switching mechanism is required to reduce the processing time in the intermediate nodes. In IP networks this behaviour is obtained by introducing Multiprotocol Label Switching (MPLS). On the other hand, a powerful routing mechanism that includes QoS attributes when selecting routes (QoS Routing) is also required.Focusing on the latter aspect, most QoS routing algorithms select paths based on the information contained in the network state databases stored in the network nodes. Because of this, routing mechanisms must include an updating mechanism to guarantee that the network state information perfectly represents the current network state. Since network state changes (topology) are not produced very often, in conventional IP networks without QoS capabilities, most updating mechanisms are based on a periodic refresh.In contrast, in highly dynamic large IP/MPLS networks with QoS capabilities a finer updating mechanism is needed. This updating mechanism generates an important and nondesirablesignalling overhead if maintaining accurate network state information is pursued. To reduce the signalling overhead, triggering policies are used. The main function of a triggering policy is to determine when a network node must advertise changes in its directly connected links to other network nodes. As a consequence of reduced signalling, the information in the network state databases might not represent an accurate picture of the actual network state.Hence, path selection may be done according to inaccurate routing information, which could cause both non-optimal path selection and an increase in connection blocking frequency.This Thesis deals with this routing inaccuracy problem, introducing new mechanisms to reduce the effects on global network performance when selecting explicit paths under inaccurate routing information. Two network scenarios are considered, namely current IP/MPLS networks and future WDM networks, and one routing mechanism per scenario is suggested:BYPASS Based Routing (BBR) for IP/MPLS and BYPASS Based Optical Routing (BBOR) for WDM networks. Both mechanisms are based on a common concept, which is defined as dynamic bypass.According to the dynamic bypass concept, whenever an intermediate node along the selected path (unexpectedly) does not have enough resources to cope with the incoming MPLS/optical-path demand requirements, it has the capability to reroute the set-up message through alternative pre-computed paths (bypass-paths). Therefore, in IP/MPLS networks the BBR mechanism applies the dynamic bypass concept to the incoming LSP demands under bandwidth constraints, and in WDM networks the BBOR mechanism applies the dynamic bypass concept when selecting light-paths (i.e., selecting the proper wavelength in both wavelength selective and wavelength interchangeable networks). The applicability of the proposed BBR and the BBOR mechanisms is validated by simulation and compared with existing methods on their respective network scenarios. These network scenarios have been selected so that obtained results may be extrapolated to a realistic network.

Las redes de transporte se mueven hacia un modelo de redes formadas por routers IP/MPLS (Internet Protocol/Multiprotocol Laebel Switching) de altas prestaciones interconectadas a través redes troncales inteligentes. Actualmente la tecnología ATM está ampliamente desarrollada en dichas redes troncales que utilizan los protocolos PNNI (Private Network- Network Interface) como plano de control. En cambio la interoperabilidad entre redes IP/MPLS a través de redes PNNI-ATM es todavía un aspecto en proceso de estudio. Por otro lado, la tendencia futura de Internet es ir hacia redes troncales completamente ópticas con capacidad automática de conmutación para permitir un mejor tratamiento del tráfico solicitado. Debido al esfuerzo realizado por los organismos de estandarización sobre redes ópticas, se ha definido un primer modelo de red llamado ASON (Automatic Switched Optical Network). Mientras las redes actuales basadas en SDH (Synchronous Digital Hierarchy) ofrecen sólo capacidad de transporte, la futura ASON permitirá el establecimiento y la liberación de canales ópticos de forma automática. Un aspecto clave para conseguir esta funcionalidad es la definición de un plano de control óptico que será el responsable de realizar las funciones de señalización y encaminamiento.Diferentes estudios han sido realizados para conseguir interoperabilidad entre redes con tecnología IP/MPLS y ATM basados esencialmente en la distribución de información de señalización MPLS a través de una red troncal ATM. Una de las soluciones planteadas se basa en la utilización sobre cada uno de los conmutadores ATM, un dispositivo capaz de procesar información MPLS, llamado LSR (Label Switched Router). Otra, en cambio, propone el establecimiento de un camino MPLS, llamado LSP (Label Switched Path), encapsulado dentro de un camino ATM o VPC (Virtual Path Connection). Ambas soluciones presentan el inconveniente de utilizar un tiempo de establecimiento demasiado elevado.Respecto al plano de control para ASON, decir que una de las opciones propuestas es la de utilizar el GMPLS (Generalizad MPLS) que es una extensión del modelo MPLS con ingeniería de tráfico. Sin embargo, recientemente se ha iniciado un debate en lo foros de estandarización sobre la posibilidad de utilizar el PNNI como plano de control en ASON. Los argumentos que justifican esta opción son que el PNNI, después de unas apropiadas modificaciones, puede ser adecuado para ASON y lleva años funcionando en muchas de las actuales redes de transporte.Esta tesis está basada en el estudio de los dos casos mencionados anteriormente. El primero caso es el de dos redes IP/MPLS conectadas a través de una red troncal ATM la cual utiliza el PNNI como plano de control. En este contexto, el objetivo principal será el de definir un mecanismo rápido de establecimiento de la conexión que proporcione los parámetros requeridos de calidad deservicio entre dos nodos pertenecientes a cada una de las redes IP/MPLS. Para conseguirlo se realizarán las modificaciones pertinentes en el PNNI y se añadirán nuevos elementos de señalización.El segundo caso consiste en interconectar dos redes IP/MPLS a través de una red tronca l´óptica. En primer lugar se adaptará el PNNI para conseguir un protocolo de encaminamiento para ASON con el fin de proporcionar un establecimiento rápido de la conexión en un entorno IP/MPLS-ASON. Finalmente, se definirá un plano de control, llamado O-PNNI (Optical PNNI) basado en la adaptación total del ATM PNNI a redes ASON. Esta tesis finaliza con un análisis de las ventajas y desventajas de los modelos GMPLS y O-PNNI como planos de control en ASON.

Dos de las limitaciones de rendimiento más importantes en los procesadores de hoy en día provienen de las operaciones de memoria y de las dependencias de control. Para resolver estos problemas, las memorias cache y los predictores de salto son dos alternativas hardware bien conocidas que explotan, entre otros factores, el reuso temporal de memoria y la correlación de saltos. En otras palabras, estas estructuras tratan de explotar la redundancia dinámica existente en los programas. Esta redundancia proviene parcialmente de la forma en que los programadores escriben código, pero también de limitaciones existentes en el modelo de compilación tradicional, lo cual introduce instrucciones de memoria y de salto innecesarias. Pensamos que los compiladores deberían ser muy agresivos optimizando programas, y por tanto ser capaces de eliminar una parte importante de esta redundancia. Por otro lado, las optimizaciones aplicadas en tiempo de enlace o directamente al programa ejecutable final han recibido una atención creciente en los últimos años, debido a limitaciones existentes en el modelo de compilación tradicional. Incluso aplicando sofisticados análisis y transformaciones interprocedurales, un compilador tradicional no es capaz de optimizar un programa como una entidad completa. Un problema similar aparece aplicando técnicas de compilación dirigidas por profiling: grandes proyectos se ven forzados a recompilar todos y cada uno de sus módulos para aprovechar dicha información. Por el contrario, seria más conveniente construir la aplicación completa, instrumentarla para obtener información de profiling y optimizar entonces el binario final sin recompilar ni un solo fichero fuente.En esta tesis presentamos nuevas técnicas de compilación dirigidas por profiling para eliminar la redundancia encontrada en programas ejecutables a nivel binario (esto es, redundancia binaria), incluso aunque estos programas hayan sido compilados agresivamente con un novísimo compilador comercial. Nuestras técnicas de eliminación de redundancia están diseñadas para eliminar operaciones de memoria y de salto redundantes, que son las más importantes para mitigar los problemas de rendimiento que hemos mencionado. Estas propuestas están basadas en técnicas de eliminación de redundancia parcial sensibles al camino de ejecución. Los resultados muestran que aplicando nuestras optimizaciones, somos capaces de alcanzar una reducción del 14% en el tiempo de ejecución de nuestro conjunto de programas.En este trabajo también revisamos el problemas del análisis de alias en programas ejecutables, identificando el por qué la desambiguación de memoria es uno de los puntos débiles en la modificación de código objeto. Proponemos varios análisis para ser aplicados en el contexto de optimizadores binarios. Primero un análisis de alias estricto para descubrir dependencias de memoria sensibles al camino de ejecución, el cual es usado en nuestras optimizaciones para la eliminación de redundancias de memoria. Seguidamente, dos análisis especulativos de posibles alias para detección de independencias de memoria. Estos análisis están basados en introducir información especulativa en tiempo de análisis, lo que incrementa la precisión en partes importantes de código manteniendo el análisis eficiente. Los resultados muestran que nuestras propuestas son altamente útiles para incrementar la desambiguación de memoria de código binario, lo que se traduce en oportunidades para aplicar optimizaciones. Todos nuestros algoritmos, tanto de análisis como de optimización, han sido implementados en un optimizador binario, enfatizando los problemas más relevantes en la aplicaciones de nuestros algoritmos en código ejecutable, sin la ayuda de gran parte de la información de alto nivel presente en compiladores tradicionales. / Two of the most important performance limiters in today's processor families comes from solving the memory wall and handling control dependencies. In order to address these issues, cache memories and branch predictors are well-known hardware proposals that take advantage of, among other things, exploiting both temporal memory reuse and branch correlation. In other words, they try to exploit the dynamic redundancy existing in programs. This redundancy comes partly from the way that programmers write source code, but also from limitations in the compilation model of traditional compilers, which introduces unnecessary memory and conditional branch instructions. We believe that today's optimizing compilers should be very aggressive in optimizing programs, and then they should be expected to optimize a significant part of this redundancy away.On the other hand, optimizations performed at link-time or directly applied to final program executables have received increased attention in recent years, due to limitations in the traditional compilation model. First, even though performing sophisticated interprocedural analyses and transformations, traditional compilers do not have the opportunity to optimize the program as a whole. A similar problem arises when applying profile-directe compilation techniques: large projects will be forced to re-build every source file to take advantage of profile information. By contrast, it would be more convenient to build the full application, instrument it to obtain profile data and then re-optimize the final binary without recompiling a single source file.In this thesis we present new profile-guided compiler optimizations for eliminating the redundancy encountered on executable programs at binary level (i.e.: binary redundancy), even though these programs have been compiled with full optimizations using a state-ofthe- art commercial compiler. In particular, our Binary Redundancy Elimination (BRE) techniques are targeted at eliminating both redundant memory operations and redundant conditional branches, which are the most important ones for addressing the performance issues that we mentioned above in today's microprocessors. These new proposals are mainly based on Partial Redundancy Elimination (PRE) techniques for eliminating partial redundancies in a path-sensitive fashion. Our results show that, by applying our optimizations, we are able to achieve a 14% execution time reduction in our benchmark suite.In this work we also review the problem of alias analysis at the executable program level, identifying why memory disambiguation is one of the weak points of object code modification. We then propose several alias analyses to be applied in the context of linktime or executable code optimizers. First, we present a must-alias analysis to recognize memory dependencies in a path- sensitive fashion, which is used in our optimization for eliminating redundant memory operations. Next, we propose two speculative may-alias data-flow algorithms to recognize memory independencies. These may-alias analyses are based on introducing unsafe speculation at analysis time, which increases alias precision on important portions of code while keeping the analysis reasonably cost-efficient. Our results show that our analyses prove to be very useful for increasing memory disambiguation accuracy of binary code, which turns out into opportunities for applying optimizations.All our algorithms, both for the analyses and the optimizations, have been implemented within a binary optimizer, which overcomes most of the existing limitations of traditional source-code compilers. Therefore, our work also points out the most relevant issues of applying our algorithms at the executable code level, since most of the high-level information available in traditional compilers is lost.

L'anàlisi i el disseny dels sistemes de control de temps real és una tasca complexa, que requereix la integració de dues disciplines, la dels sistemes de control i la dels sistemes de temps real. Tradicionalment però, els sistemes de control de temps real s'han dissenyat diferenciant, de forma independent, dues fases, primerament el disseny del controlador, i després, la seva implementació en un computador. Això ha desembocat en solucions no òptimes tant en termes de planificabilitat del sistema i com en el rendiment dels sistemes controlats.Normalment, els mètodes i models de la teoria de control de temps discret no consideren durant la fase de disseny dels controladors les limitacions que es puguin derivar de la implementació. En la fase de disseny s'assumeix que els algorismes de control s'executaran en processadors dedicats i que els processadors seran prou ràpids i determinístics per no haver-se de preocupar del comportament temporal que aquests algorismes de control tindran en temps d'execució. Tot i així, quan els recursos - per exemple, processadors - són limitats, apareixen variacions temporals en l'execució dels algorismes de control. En concret, en els sistemes de planificació de tasques de temps real, un algorisme de control s'implementa en una tasca periòdica caracterizada per restriccions temporals estàndards com períodes i terminis. És sabut que, en la planificació de tasques de temps real, les variacions temporals en l'execució d'instàncies de tasques és permesa sempre i quan les restriccions de planificabilitat estiguin garantides. Aquesta variabilitat per tasques de control viola l'estricte comporament temporal que la teoria de control de temps discret pressuposa en l'execució dels algorismes de control.Això té dos efectes negatius: la variabilitat temporal en l'execució de les tasques de control degrada el rendiment del sistema controlat, fins i tot causant inestabilitat. A més, si es minimitza la probabilitat d'aparició d'aquesta variabilitat en l'execució de les tasques de control a través d'especificacións més limitants, la planificabilitat del conjunt de tasques del sistema disminueix.Cal tenir en compte que la teoria de control no dóna directrius de com incloure, en la fase de disseny dels controladors, aquesta variabilitat en l'execució de tasques que es deriva de les limitacions d'implementació. A més, la teoria de sistemes de temps real no proporciona ni models de tasques ni restriccions temporals que puguin ser usats per garantir l'execució periòdica, i sense variabilitats temporals, de tasques sense sobrelimitar la planificabilitat dels sistema.En aquesta tesi es presenta un entorn integrat i flexible de planificació i de control per a l'anàlisi i el disseny de sistemes de control de temps real que dóna solucions als problemes esmentats anteriorment (baixa planificabilitat en el sistema i degradació del rendiment dels sistemes controlats). Mostrem que, fusionant les activitats de la comunitat de temps real amb les de la comunitat de control, això és, integrant la fase de disseny de controladors amb la fase d'implementació en un computador, es millora tant la planificabilitat del sistema com el rendiment dels sistemes controlats.També es presenta una nova aproximació al disseny de controladors de temps discret que té en compte les limitacions derivables de la implementació i relaxa les tradicionals assumpcions dels controladors de temps discret (mostreig i actuació equidistants). En lloc d'especificar, en la fase de disseny, únics valors pel període de mostreig i pel retard temporal, especifiquem un conjunt de valors tant per l'un com per l'altre. Aquesta nova aproximació al disseny de controladors es basa en la idea d'ajustar, en temps d'execució, els paràmetres del controlador d'acord amb el comportament temporal específic de la implementació (per exemple, d'acord amb la variabilitat en l'execució de les tasques deguda a la planificació). Els llaços de control resultants esdevenent sistemes variants en el temps, amb mostreig irregular i retards temporals variables. Per a aquests sistemes, i utilitzant formulació en l'espai d'estat, presentem una anàlisi completa d'estabilitat, així com l'anàlisi de la resposta. També mostrem com, a partir de les propietats temporals d'aquesta nova aproximació al disseny de controladors, podem obtenir restriccions temporals més flexibles per a les tasques de control. Les restriccions temporals estàndards, per a les tasques periòdiques en els sistemes de temps real, són constants per a totes les instàncies d'una tasca. Això és, només un sol valor per a una restricció és aplicable a totes les instàncies. Les noves restriccions temporals que presentem per a tasques de control no forcen a aplicar un valor específic, sinó que permeten aplicar valors diferents a cada instància d'una tasca, tenint en compte, per exemple, la planificabilitat d'altres tasques.Aquestes restriccions temporals flexibles per a tasques de control ens permeten obtenir planificacions viables i sistemes de control estables a partir de conjunts de tasques (incloent tasques de control i d'altres) que no eren planificables en usar mètodes estàndards tant de planificació de temps real com de disseny de controladors. A més, associant informació de rendiment de control a aquestes noves restriccions temporals per a tasques de control, mostrem com podem prendre decisions de planificació que, anant més enllà de complir amb les restriccions temporals, milloren el rendiment dels sistemes controlats quan aquests sofreixen perturbacions. / The analysis and design of real-time control systems is a complex task, requiring the integration and good understanding of both control and real-time systems theory. Traditionally, such systems are designed by differentiating two separate stages: first, control design and then its computer implementation, leading to sub-optimal solutions in terms of both system schedulability and controlled systems performance.Traditional discrete-time control models and methods consider implementation constraints only to a very small extent. This is due to the fact that in the control design stage, controllers are assumed to execute in dedicated processors and processors are assumed to be fast and deterministic enough not to worry about the timing that the controlling activities may have on the implementation. However, when resources (e.g., processors) are limited, timing variations in the execution of control algorithms occur. Specifically, a control algorithm in traditional real-time scheduling is implemented as a periodic task characterized by standard timing constraints such as period and deadline. In real-time scheduling, timing variations in task instance executions (i.e., jitters) are allowed as far as the schedulability constraints are preserved. Consequently, the resulting jitters for control task instances do not comply with the strict timing demanded by discrete-time control theory. This has two pervasive effects: the presence of jitters for control tasks degrades the controlled system performance, even causing instability. On the other hand, minimizing the likelihood of jitters for control tasks by over-constraining the control task specification reduces the schedulability of the entire task set. It is worth mentioning that control theory offers no advice on how to include, into the design of controllers, the effects that implementation constraints have in the timing of the control activities (e.g., scheduling inherent jitters). Also, real-time theory lacks task models and timing constraints that can be used to guarantee a periodic task execution free of jitters without over-constraining system schedulability. In this thesis we present a flexible integrated scheduling and control analysis and design framework for real-time control systems that solves the problems outlined above: poor system schedulability and controlled systems performance degradation. We show that by merging the activities of the control and real-time communities, that is, by integrating control design with computer implementation, both system schedulability and controlled systems performance are improved. We present a new approach to discrete-time controller design that takes implementation constraints into account and relaxes the equidistant sampling and actuation assumptions of traditionally designed discrete-time controllers. Instead of specifying a single value for the sampling period and a single value for the time delay at the design stage, we specify a set of values for both the sampling period and for the time delay. This new approach for the controller design relies on the idea of adjusting controller parameters at run time according to the specific implementation timing behaviour, i.e., scheduling inherent jitters. The resulting closed-loop systems are based on irregularly sampled discrete-time system models with varying time delays. We have used state space formulation to present a complete stability and response analysis for such models.We also show how to derive more flexible timing constraints for control tasks by exploiting the timing properties imposed by this new approach to discrete-time controller design. Real-time scheduling standard timing constraints for periodic tasks are constant for all task instances. That is, a single value of a constraint (e.g., period or deadline) holds for all task instances. Our flexible timing constraints for control tasks do not set specific values. Rather, they provide ranges and combinations to choose from (at each control task instance execution), taking into account, for example, schedulability of other tasks. That is, these more flexible timing constraints for control tasks allow us to obtain feasible schedules and stable control systems from task sets (including control and non-control tasks) that are not feasible using traditional real-time scheduling and discrete-time control design methods. In addition, by associating control performance information with these new timing constraints for control tasks, we show how scheduling decisions, going beyond meeting timing constraints, can be taken to improve the performance of the controlled systems when they are affected by perturbations.

Magnetic fluid hyperthermia is a potential therapy for achieving interstitial hyperthermia and is currently under clinical trials. This approach is based on the instillation of magnetic nanoparticles at the tumour site, which dissipate heat when exposed to an alternating magnetic field. This procedure leads to a local increase of temperature and induction of tumour death or regression. Nanoparticles of metallic iron are potential heating agents for this therapy, but rely on the presence of a protecting coat that avoids reactions with their environment. In this work, iron nanospheres and iron nanowires with a graphite coat are explored for this purpose. From these two nanostructures, the nanospheres are shown to have a greater potential in terms of heat dissipation. The graphite shell is further investigated as an interface for conjugation with other molecules of relevance such as drugs and fluorescent probes. The effect of acidic treatments on the magnetic and surface properties of the nanospheres is systematically studied and a suitable method to generate carboxylic functionalities on the nanoparticle surface alongside with a good preservation of the magnetic properties is developed. These carboxylic groups are shown to work as a bridge for conjugation with a model molecule, methylamine, as well as with a fluorescent dye, allowing the detection of the nanoparticles in cells by means of optical methods. The carboxylic functionalities are further explored for the conjugation with the anti-cancer drug cisplatin, where the amount of drug loaded per particle is found to be dependent on the density of free carboxylic groups. The release of the drug in physiological salt solutions is time and temperature dependent, making them particularly interesting for multi-modal anti-cancer therapies, where concomitant hyperthermia and chemotherapy could be achieved. Their potential for such therapies is shown in vitro by inducing hyperthermia in cell suspensions containing these nanoparticles. These results are finally translated to a three dimensional cell culture model where the in vitro growth of tumour spheroids is inhibited. The developed nanostructures have a great potential for therapeutic approaches based on the synergistic effects of hyperthermia and chemotherapy.

En esta tesis analizamos y presentamos algoritmos de ordenación secuencial y paralelo que explotan la jerarquía de memoria del computador usado y/o reducen la comunicación de los datos. Sin embargo, aunque los objetivos de esta tesis son los mismo que los de otros trabajos, la forma de conseguirlos es diferente.En esta tesis los conseguimos haciendo que los algoritmos de ordenación propuestos sean conscientes de la arquitectura del computador y las características de los datos que queremos ordenar.Los conjuntos de datos que consideramos son conjuntos que caben en memoria principal, pero no en memoria cache.Los algoritmos presentados se adaptan, en tiempo de ejecución, a las características de los datos (duplicados, con sesgo, etc.) para evitar pérdidas de rendimiento dependiendo de estas características. Para ello, estos algoritmos realizan un particionado de los datos, utilizando una técnica que llamamos Mutant Reverse Sorting y que presentamos en esta tesis. Mutant Reverse Sorting se adapta dinámicamente a las características de los datos y del computador. Esta técnica analiza una muestra del conjunto de datos a ordenar para seleccionar la forma más rápida de particionar los datos. Esta técnica elige entre Reverse Sorting y Counting Split en función de la distribución de los datos. Estas técnicas también son propuestas en esta tesis. El análisis de estas técnicas, junto con los algoritmos de ordenación presentados, se realiza en un computador IBM basado en módulos p630 con procesadores Power4 y en un computador SGI O2000 con procesadores R10K. En el análisis realizado para ambos computadores se presentan modelos de comportamiento que se comparan con ejecuciones reales.Con todo ello, conseguimos los algoritmos de ordenación secuencial y paralelo más rápidos para las características de los datos y los computadores utilizados. Esto es gracias a que estos algoritmos se adaptan a los computadores y las características de los datos mejor que el resto de algoritmos analizados.Así, por un lado, el algoritmo secuencial propuesto, SKC-Radix sort, consigue unas mejoras de rendimiento de más de 25% comparado con los mejores algoritmos que encontramos en la literatura. Es más, cuanto mayor es el número de duplicados o el sesgo de los datos, mayor es la mejora alcanzada por el SKC-Radix sort.Por otro lado, el algoritmo paralelo presentado, PSKC-Radix sort, es capaz de ordenar hasta 4 veces más datos que Load Balanced Radix sort en la misma cantidad de tiempo. Load Balanced Radix sort era el algoritmo más rápido de ordenación en memoria y en paralelo para los conjunto de datos que ordenamos hasta la publicación de nuestros trabajos. / In this thesis we analyze and propose parallel and sequential sorting algorithms that exploit the memory hierarchy of the computer used and/or reduce the data communication. So, the objectives of this thesis are not different from the objectives of other works. However, the way to achieve those objectives is different.We achieve those objectives by being conscious of the computer architecture and the data characteristics of the data set we want to sort.We have focused on the data sets that fit in main memory but not in cache.So, the sorting algorithms that we present take into account the data characteristics (duplicates, skewed data, etc.) in order to avoid any lose of performance in execution time depending on those characteristics. That is done by partitioning the data set using Mutant Reverse Sorting, which is a partition technique that we propose in this thesis.Mutant Reverse Sorting dynamically adapts to the data characteristics and the computer architecture. This technique analyzes a set of samples of the data set to choose the best way to partition this data set. This chooses between Reverse Sorting and Counting Split, which are selected depending on the data distribution. Those techniques are also proposed in this thesis.The analysis of the partitioning techniques and the sorting algorithms proposed is done in an IBM computer based on p630 nodes with Power4 processors and in a SGI O2000 with R10K processors. Also, we present models of the behavior of the algorithms for those machines.The sequential and parallel algorithms proposed are the fastest for the computer architectures and data set characteristics tested. That is so because those algorithms adapt to the computer architecture and data characteristics better than others.On one hand, the sequential sorting algorithm presented, SKC-Radix sort, achieves performance improvements of more than 25% compared to other sequential algorithms found in the literature. Indeed, the larger the number of duplicates or data skew, the larger the improvement achieved by SKC-Radix sort. On the other hand, the parallel sorting algorithm proposed, PSKC-Radix sort, sorts 4 times the number of keys that Load Balanced Radix can sort in the same amount of time. Load Balanced Radix sort was the fastest in-memory parallel sorting algorithm for the kind of data set we focus on.