Resums pendents

En los últimos años, el relaying ha surgido como una poderosa técnica para mejorar la cobertura y el rendimiento de las redes inalámbricas. En consecuencia, la creciente demanda de servicios basados en redes inalámbricas con relays, ha conducido al desarrollo de técnicas de networking nuevas y eficientes. Estas técnicas pueden ser utilizadas en diferentes capas de la pila de protocolos y pueden ser optimizadas para cumplir diversos objetivos, como la maximización del rendimiento, mejora de cobertura, etc. en el marco de las redes existentes. En esta tesis se presenta una serie de contribuciones para las técnicas de networking, utilizando una variedad de herramientas a fin de maximizar el rendimiento de la red y satisfacer las demandas de los usuarios. Para hacer contribuciones efectivas y concretas, hemos seleccionado problemas exigentes en varios aspectos de las técnicas avanzadas de networking en redes inalámbricas y presentamos soluciones hábiles a éstos. En particular, hacemos uso de diferentes herramientas como network coding, técnicas de transmisión cognitiva y teoría de juegos, con el fin de diseñar soluciones para las redes inalámbricas modernas con relays. Las principales técnicas de networking, para diferentes capas de la pila de protocolos, presentadas en esta tesis son las siguientes. En primer lugar, a nivel de capa física, maximizamos el rendimiento de la red mediante la herramienta de network coding en la capa física (PNC) basada en el método compute and forward (CF) en redes con relays. Se sabe que las tasas máximas alcanzables en la transmisión basada en CF están limitadas debido a las aproximaciones de los canales en el relay. Proponemos el Integer Forcing Precoder (IFP), para superar esta limitación. Con la ayuda del IFP, demostramos una posible implementación de la prometedora técnica de CF, que allanaría el camino para un diseño avanzado del precodificador para maximizar el rendimiento de la red. En segundo lugar, en la capa de enlace de la red, maximizamos el rendimiento con el uso de dos herramientas diferentes: (a) network coding junto con una optimización cross-layer condicionada a la calidad de experiencia (QoE), (b) técnicas de transmisión cognitiva. En (a), utilizamos el network coding en la capa de enlace, en coherencia con la optimización cross-layer y demostramos la existencia de compromisos importantes entre rendimiento y QoE alcanzable. Por otra parte, proponemos utilizar factores realistas como la ubicación de los usuarios finales en la red de relays para optimizar el servicio obtenido en presencia de tales compromisos. En (b), utilizamos las técnicas de transmisión cognitiva para analizar la mejora en el rendimiento de una red inalámbrica particular, el sistema de satélites duales (DSS). Además, presentamos un análisis taxonómico exhaustivo de las diferentes técnicas cognitivas en DSS. Con la ayuda de este trabajo, proponemos posibles diseños para las técnicas "inteligentes" de networking, las cuales constituyen una plataforma para maximizar el rendimiento de futuras redes inalámbricas con relays. En tercer lugar, en la capa de transporte-aplicación, maximizamos no sólo el rendimiento, si no también una utilidad conjunta compuesta de rendimiento, QoE y coste del servicio, utilizando herramientas de la teoría de juegos. Consideramos una aplicación de video transmitida por una red inalámbrica en la que las usuarios que compiten tratan de maximizar sus utilidades. Modelamos y predecimos los puntos de equilibrio alcanzados usando repetidas formulaciones del juego, teniendo en cuenta factores reales como la tolerancia de los usuarios y el criterio óptimo de Pareto. Con la ayuda de este trabajo, se demuestra el potencial del uso de técnicas repetidas de teoría de juegos en redes inalámbricas, prometiendo así mejorar el rendimiento del sistema existente de manera categórica. En general, esta tesis presenta propuestas prácticas y efectivas junto con un análisis holístico para diferentes aspectos en el desarrollo de técnicas modernas de networking para redes inalámbricas con relays. / In the recent years, relaying has emerged as a powerful technique to improve the coverage and throughput of wireless networks. Consequently, the growing demands of the wireless relay networks based services has led to the development of novel and efficient networking techniques. These techniques can be used at different layers of the protocol stack and can be optimized to meet different objectives like throughput maximization, improving coverage etc. within existent networking framework. This thesis presents a series of contributions towards the networking techniques using a variety of tools in order to maximize the throughput of the network and satisfy the user demands. To make effective and concrete contributions, we have selected challenging problems in various aspects of advanced wireless networking techniques and presented neat solutions to these problems. In particular, we make use of the different tools like network coding, cognitive transmission techniques and game theory in order to design networking solutions for modern wireless relay networks. The main contributions of this thesis towards networking techniques at different layers of the protocol stack are as follows. Firstly, at the physical layer, we maximize the throughput of the network using the tool of physical layer network coding (PNC) based on compute and forward (CF) in relay networks. It is known that the maximum achievable rates in CF-based transmission are limited due to the channel approximations at the relay. We propose the integer forcing precoder (IFP), which bypasses this maximum rate achievability limitation. With the help of IFP, we demonstrate a possible implementation of the promising scheme of CF thereby paving the way for an advanced precoder design to maximize network throughput. Secondly, at the link-network layer, we maximize throughput with the use of two different tools: (a) network coding along with Quality of Experience (QoE) driven cross-layer optimization and (b) cognitive transmission techniques. For (a), we use network coding at link layer in coherence with cross-layer optimization and prove the existence of crucial trade-offs between throughput and achievable QoE. Moreover, it is proposed to use the realistic factors such as positioning of the end users in the relay network to optimize the service obtained in presence of such trade-offs. For (b), we use the cognitive transmission techniques to analyze the improvement in throughput of a particular wireless network, namely Dual Satellite systems (DSS). Moreover, an exhaustive taxonomic analysis of the different cognitive techniques in DSS is presented. With the help of this work, the possible designs for 'intelligent' networking techniques are proposed, which form a platform for maximizing the throughput performance of future wireless, relay networks. Thirdly, at the transport-application layer, we maximize not only the throughput but a joint utility comprised of throughput, QoE and cost of service, with the use of game theoretical tools. We consider a video application relayed over a wireless network and competing users trying to maximize their utilities. We model and predict the equilibriums achieved using repeated game formulations taking into account the realistic factors such as tolerance of the users and pareto optimality. With the help of this work, the potential of use of repeated game theoretical tools in wireless networks is proved which also promises to improve the existing system performance categorically. Overall, this thesis presents effective and practical propositions along with holistic analysis towards different aspects of development of modern networking techniques for wireless relay networks.

Los servicios de video hoy en día hacen parte de nuestras interacciones cotidianas y aportan la mayor parte del tráfico en la red. Su uso más amplio incluye escenarios fuera de lo común como lo son la ayuda en emergencias o en telemedicina. Por otra parte, las demandas de los usuarios de tales servicios, en términos de experiencia usuario, sigue en aumento, llevando a requerimientos más especializados de Calidad de Experiencia ( QoE en ínglés). Garantizar cierto nivel de satisfacción de usuario en escenarios exigentes donde las redes a disposición son heterogéneas continua siendo in problema abierto. Los objetivos principales de esta tesis han sido: 1) proponer un marco de trabajo para networking heterogéneo que permita la transmisión de video de manera impecable a través de redes heterogéneas, 2) proponer un marco centrado en el usuario, para transmitir video que sea coherente con el networking heterogéneo, y 3) diseñar un modelo y solución completos para ofrecer video adaptativo tal que se cumplan los requerimientos de satisfacción de usuario. A continuación se presentan las contribuciones de esta tesis que cumplen los tres objetivos trazados. Primero, proponemos modelar las redes heterogéneas desde un ángulo holístico. La metodología de este diseño holístico de sistema está basado en dos conceptos novedosos. En primer lugar, proveer un marco a través del cual las instancias de red pueden ser modeladas para garantizar generalidad y robustez. En segundo lugar, caracterizar de manera única las instancias de red a través de su min-cut. La ventaja de este marco es que puede verse como un modelo de sistema subyacente que garantiza una impecable transmisión de contenido sin importar la instancia de red. Esto es posible formulando una optimización cross-layer para transmisión de contenido, coherente con la filosofía de networking centrada en la información (information-centric networking). Segundo, proponemos un marco para video adaptativo impulsado por el QoE, basado en una formulación de optimización cross-layer. El algoritmo resultante permite la adaptación de video y se basa en los retardos de redes variantes en el tiempo, por lo tanto tiene en cuenta las restricciones de redes con retardos largos y las dificultades de establecer un camino de retorno que permita la adaptabilidad a los cambios en la red. Esta solución se ha evaluado sistemáticamente, tanto en entornos emulados como en una solución complemente implementada experimentalmente. Tercero, proponemos la contribución principal de esta tesis: un modelo completo centrado en el usuario, que ofrece servicios de video en redes heterogéneas. El problema de borrado de paquetes y de congestión en las redes sin garantías (best-effort) es desacoplado para así hacerlos coincidir con los efectos respectivos que degradan el video. Esto permite la formulación de dos problemas de optimización, en tiempo (fotogramas congelados) y espacio (artefactos en la imagen). La solución completa además una novedosa dimensión semántica coherente con information-centric networking, que propone reflejar las necesidades perceptuales del usuario final. Probamos las ventajas de nuestro diseño para escenarios donde el video es necesario para adquirir conciencia de situaciones (situation awareness), donde se usan comúnmente redes heterogéneas y mostramos ganancias considerables en términos de reducción de los efectos de la congestión y el borrado de paquetes, mientras que mejoramos el QoE y cumplimos las demandas perceptuales de los usuarios. / Video services have become part of everyday interactions and contribute to a major portion of network traffic. Their broader usage includes out-of-the-ordinary scenarios as aid in emergencies, or telemedicine. Moreover, user demands of such services in terms of overall user experience continue to increase, leading to more specialized Quality of Experience (QoE) requirements. Guaranteeing a level of satisfaction to the user in challenging scenarios where the alternative networks are heterogeneous in nature continues to be an open issue. The main objectives of this thesis have been to: 1) propose a framework for heterogeneous networking that allows for a seamless delivery of video content along diverse heterogeneous networks, 2) propose a user-centric framework for video transmission in line with heterogeneous networking, and 3) design a complete model and solution to provide video adaptation in heterogeneous networks such that it meets the requirements for user satisfaction. The contributions of this thesis, such that the three objectives are met are as follows. First, we propose to model heterogeneous networks with a holistic approach. The methodology of this holistic system design is based on two novel concepts. On one hand, to provide a framework by which heterogeneous network instances can be modeled to guarantee generality and robustness. On the other hand, to uniquely characterize the network instances via their min-cut. The strength of this framework is its usage as an underlying system model that can guarantee seamless content delivery regardless of the network instance. The latter is possible by formulating a general cross-layer optimization for content delivery, coherent to information-centric networking philosophy. Second, we propose a QoE-driven adaptive video framework, based on a cross-layer optimization formulation. The derived adaptive video algorithm for time-variant networks is delay-driven, hence contemplates the constraints of long-delayed networks and the challenges of establishing a feedback loop to enable the network adaptability. The framework is evaluated systematically, in both an emulation and a fully implemented experimental environment. Third, we propose the main contribution of this thesis: a complete model to provide user-centric video services in heterogeneous networks. The problem of combined erasures and congestion in best effort network is decoupled to match the specific degrading effects on the video. This allows for two separate QoE driven optimization approaches in time (freezes) and space (artifacts) domain. The complete solution offers a feasible dynamic streaming adaptation that suits constraint heterogeneous networks such as satellite. The performance is evaluated through a novel QoE three-dimensional analysis. The overall solution contemplates a novel semantical dimension, in line with information-centric networking, with an unexplored take on semantics that intends to reflect on the perceptual needs of the end user. We prove the strength of our design for the situation awareness scenario, where heterogeneous networks are often used, and show substantial gain in terms of mitigation of the effects of congestion and erasures while improving QoE and achieving the expected user's perceptual demands.

Esta tesis doctoral se centra en esquemas de codificación de red sistemáticos (SNC por sus siglas en inglés para systematic network coding) a nivel de paquete para proporcionar resistencia a la pérdida de paquetes en redes lineales con pérdidas. En la teoría, la codificación de red ( network coding ) es conocida por la mejora en rendimiento y fiabilidad en redes con pérdidas. Sin embargo, la traducción de la teoría del network coding en soluciones prácticas comprende algunos desafíos críticos. Esta tesis aborda estos desafíos e investiga soluciones de network coding que puedan ser usadas en la práctica para diferentes instancias de redes lineales con pérdidas. Los objetivos principales de esta tesis doctoral son: 1) desarrollar un modelo matricial que permita el tratamiento analítico de network coding para redes con pérdidas, 2) investigar de manera semi-analítica el rendimiento alcanzable y la fiabilidad para redes lineales, un simple pero útil modelo de red conceptual, 3) desarrollar esquemas prácticos de network coding para redes lineales que superen significativamente el rendimiento del estado del arte en esquemas basados puramente en la correción de borrado hacia adelante (FEC por sus siglas en ingles para forward erasure correction), y 4) estar en línea con los esfuerzos del equipo de trabajo de la investigación en internet, Internet Research Task Force (IRTF) y presentar contribuciones. Las contribuciones de esta tesis, tal que se cumplen los objetivos son las siguientes. Primero, investigamos el uso de SNC en redes con pérdida de un solo salto. Desarrollamos un modelo matricial para este caso sin re-codificar en la red. Esto nos permite comparar códigos separables de máxima distancia (MDS por su sigla en inglés) con SNC cuando se usan únicamente como FEC. Derivamos la mínima distancia de SNC y mostramos que SNC puede proporcionar fiabilidad tan cercana al MDS como se desee y lo permita el tamaño del campo. Simulamos aplicaciones prácticas a nivel de capa de aplicación de la pila de protocolos con dos resultados concretos. Primero, se muestra que utilizando decodificación progresiva de SNC se alcanzan retardos más bajos que con un código MDS y segundo, se obtiene una distribución óptima del ancho de banda para la tasa de network coding mientras se aplica SNC in redes con bandas limitadas. Segundo, investigamos la aplicación de SNC en redes de dos saltos con pérdidas. Extendemos el modelo matricial para redes con un nodo intermedio. Usando el planteamiento semi-análitico, estudiamos y caracterizamos la fiabilidad y tasa alcanzable como una función de la tasa de network coding y de la capacidad de la red. Simulamos las aplicaciones prácticas en la capa de enlace del estándar Digital Video Broadcasting via Satellite-Second Generation (DVB-S2). Proponemos un marco con arquitectura y encapsulamiento tal que se pueda usar network coding en protocolos de la capa de enlace del DVB-S2. Tercero, extendemos el modelo matricial para una red con varios nodos intermedios. Esto nos permite entender el marco matemático de mapear entidades de comunicaciones con entidades matemáticas en diferentes nodos intermedios de la red. Analizamos la fiabilidad, las tasas alcanzables, el retardo y la complejidad de los esquemas de network coding de manera semi-analítica y probamos que nuestros resultados están en línea con los resultados de la teoría de la información. Finalmente, desarrollamos un esquema inteligente de re-codificación de network coding que incluye la planificación de paquetes en los nodos intermedios. Nuestra propuesta proporciona menor retardo y menor complejidad comparada con el estado del arte en esquemas de network coding. / This dissertation focuses on packet-level systematic network coding (SNC) schemes to provide resilience to packet losses in lossy line networks. In theory, network coding is known to improve throughput and reliability of lossy networks. However, the translation of the network coding theory into efficient practical network coding solutions involves some critical challenges. This dissertation addresses those challenges and investigates on network coding solutions that can be utilized in practice for different instances of the lossy line networks. The main objectives of this dissertation are: 1) to develop a matricial model that allows analytical treatment of network coding for lossy networks, 2) semi-analytical investigation of achievable throughput and reliability for line networks, a simple yet useful conceptual network model, 3) to develop practical network coding schemes for line networks that significantly outperform state-of-the-art purely forward erasure correction (FEC)-based schemes and 4) to be in line with Internet Research Task Force (IRTF) efforts and eventually contribute. The contributions of this thesis, such that the objectives are met are as follows. First, we investigate the application of SNC in one-hop lossy networks. We develop a matricial model for the case without re-encoding in the network. This allows us to compare maximum distance separable (MDS) codes with SNC when used as FEC only. We derive the minimum distance of SNC and show that SNC can provide as closed as wished to MDS reliability as the field sizes is allowed to grow. We simulate practical applications at application layer of the protocol stack with two concrete results. First, it is shown that by using progressive decoding SNC achieves smaller delay than the MDS code and second, an optimal bandwidth distribution for network coding rate is obtained while applying SNC in band-limited networks. Second, we investigate the application of SNC in two-hop lossy networks. We extend the matricial model for the networks with one intermediate node. Using the semi-analytical approach, we study and characterize the reliability and achievable rate as a function of network coding rate and capacity of the network. We simulate practical applications at link layer of Digital Video Broadcasting via Satellite-Second Generation (DVB-S2). We propose an architectural and encapsulation framework so that network coding can be used over the state-of-the-art protocols at link layer of DVB-S2. Third, we extend the matricial model for the network with several intermediate nodes. This allows us to understand the mathematical framework of mapping communication entities to mathematical entities at different intermediate nodes of the network. We analyze semi-analytically reliability, achievable rates, delay and complexity of network coding schemes and prove that our results are inline with information theoretical results. Finally, we develop a smart re-encoding network coding scheme that includes packet scheduling at the intermediate nodes. Our proposal is shown to provide smaller delay and smaller complexity than state-of-the-art network coding schemes.

Una sèrie de col·lisions aèries que van succeir durant un període d’uns 30 anys (1956-1986) van ser un dels principals motius pels quals l’Administració Federal d’Aviació (FAA) va prendre la decisió de desenvolupar i implementar un sistema de prevenció de col·lisions eficaç que actués com a últim recurs, quan es produís una fallada del servei de separació d’aeronaus per part del controlador de trànsit aeri (ATC). El Sistema d’Alerta de Trànsit i Anticol·lisió (TCAS) va ser desenvolupat per a aquest objectiu a partir d’una anàlisi completa de dades de vol. Com a resultat, la influència de TCAS en la seguretat del vol ha estat eficaç, beneficiosa i significativa en la reducció de la probabilitat de col·lisions. Els projectes Single European Sky ATM Research (SESAR) i Next Generation Air Transportation System (NextGen) pretenen millorar l’eficiència en la gestió del tràfic aeri (ATM) al mateix temps que es pretén reduir l’actual capacitat latent en el costat aire mitjançant la incorporació de noves tecnologies i procediments. En conseqüència, serà necessari investigar l’impacte en seguretat en augmentar la capacitat de l’espai aeri mitjançant una anàlisi exhaustiva i una avaluació efectiva del vol. En aquesta tesi, es proposen diversos models causals de colisions entre aeronaus per millorar el rendiment del TCAS tenint en compte el potencial efecte sobre el trànsit colindant, considerant escenaris futurs amb un nombre elevat de trajectòries. Els diferents models han estat especificats com a sistemes a esdeveniments discrets mitjançant el formalisme de Xarxes de Petri Acolorides. Mitjançant l’anàlisi de l’espai d’estat d’un volum d’espai aeri amb diverses aeronaus, els models desenvolupats avaluen els efectes dels diferents RAs generats pel TCAS sobre el tràfic col·lindant. Els models han estat validats utilitzant InCAS i ofereixen una perspectiva global de les dinàmiques que es generen, i una millor comprensió de les potencials col·lisions induïdes per a una millor valoració del risc de col·lisió. Com a resultat, els escenaris amb tràfic col·lindant que podrien iniciar col·lisions induïdes han estat identificats i caracteritzats. L’anàlisi quantitativa del factor de risc de col·lisions induïdes per TCAS ha estat realitzat per avaluar l’impacte de la demora del pilot per respondre als avisos TCAS durant el vol en escenaris d’alta densitat. Mitjançant l’ús de models estocàstics per representar la resposta del pilot s’han analitzat els diferents estats assolibles amb l’objectiu de generar resolucions cooperatives. En conseqüència, el rendiment de TCAS es podria millorar de forma innovadora sense necessitat d’introduir canvis rellevants en la lògica. Els models causals de col·lisions proposats poden ser utilitzats com a eines auxiliars en l’anàlisi d’escenaris de tràfic dens, i augmentar la capacitat de l’espai aeri, gestionant de manera eficient i segura un major nombre de vols. El present treball contribueix a continuar les investigacions en l’anàlisi de la seguretat dels conceptes ATM actuals i avançats, incloent les futures extensions de TCAS. / Una serie de colisiones en el aire que ocurrieron durante un período de unos 30 años (1956-1986) fueron uno de los principales motivos por los que la Administración Federal de Aviación (FAA) tomó la decisión de desarrollar e implementar un sistema de prevención de colisiones eficaz que actuara como último recurso, cuando se produjese un fallo del servicio de separación de aeronaves por parte del controlador de tránsito aéreo (ATC). El Sistema de Alerta de Tráfico y Anticolisión (TCAS) fue desarrollado para este objetivo a partir de un análisis completo de datos de vuelo. Como resultado La influencia de TCAS en la seguridad del vuelo ha sido eficaz, beneficiosa y significativa en la reducción de la probabilidad de colisiones. Los proyectos Single European Sky ATM Research (SESAR) y Next Generation Air Transportation System (NextGen) pretenden mejorar la eficiencia en la gestión del tráfico aéreo (ATM) al mismo tiempo que se pretende reducir la actual capacidad latente en el lado aire mediante la incorporación de nuevas tecnologías y procedimientos,. En consecuencia, va a ser necesario investigar el impacto en seguridad al aumentar la capacidad del espacio aéreo mediante un análisis exhaustivo y una evaluación efectiva del vuelo. En esta tesis, se proponen varios modelos causales de encuentro entre aeronaves para mejorar el rendimiento del TCAS teniendo en cuenta el potencial efecto sobre el tráfico colindante, considerando escenarios futuros con un número elevado de trayectorias. Los diferentes modelos han sido especificados como sistemas a eventos discretos mediante el formalismo de Redes de Petri Coloreadas. Mediante el análisis del espacio de estado de un volumen de espacio aéreo con varias aeronaves, los modelos desarrollados evalúan los efectos de los distintos RAs generados por TCAS sobre el tráfico colindante. Los modelos han sido validados utilizando InCAS y ofrecen una perspectiva global de las dinámicas que se generan, y una mejor comprensión de las potenciales colisiones inducidas para una mejor valoración del riesgo de colisión. Como resultado, los escenarios con tráfico colindante que podrían iniciar colisiones inducidas han sido identificados y caracterizados. El análisis cuantitativo del factor de riesgo de colisiones inducidas por TCAS ha sido realizado para evaluar el impacto de la demora del piloto para responder a los avisos TCAS durante el vuelo en escenarios de alta densidad. Mediante el uso de modelos estocásticos para representar la respuesta del piloto se han analizado los diferentes estados alcanzables con el objetivo de generar resoluciones cooperativas. En consecuencia, el rendimiento de TCAS se podría mejorar de forma innovadora sin necesidad de introducir cambios relevantes en la lógica. Los modelos de encuentros causales propuestos pueden ser utilizados como herramientas auxiliares en el análisis de escenarios de tráfico denso, y aumentar la capacidad del espacio aéreo, gestionando de manera eficiente y segura un mayor número de vuelos. El presente trabajo contribuye a continuar las investigaciones en el análisis de la seguridad de los conceptos ATM actuales y avanzados, incluyendo las futuras extensiones de TCAS.

In just four decades the Internet has gone from a lab experiment to a worldwide, business critical infrastructure that caters to the communication needs of almost a half of the Earth's population. With these figures on its side, arguing against the Internet's scalability would seem rather unwise. However, the Internet's organic growth is far from finished and, as billions of new devices are expected to be joined in the not so distant future, scalability, or lack thereof, is commonly believed to be the Internet's biggest problem. While consensus on the exact form of the solution is yet to be found, the need for a semantic decoupling of a node's location and identity, often called a location/identity separation, is generally accepted as a promising way forward. Typically, this requires the introduction of new network elements that provide the binding of the two names-paces and caches that avoid hampering router packet forwarding speeds. But due to this increased complexity the solution's scalability is itself questioned. This dissertation evaluates the suitability of using the Locator/ID Separation Protocol (LISP), one of the most successful proposals to follow the location/identity separation guideline, as a solution to the Internet's scalability problem. However, because the deployment of any new architecture depends not only on solving the incumbent's technical problems but also on the added value that it brings, our approach follows two lines. In the first part of the thesis, we develop the analytical tools to evaluate LISP's control plane scalability while in the second we show that the required control/data plane separation provides important benefits that could drive LISP's adoption. As a first step to evaluating LISP's scalability, we propose a methodology for an analytical analysis of cache performance that relies on the working-set theory to estimate traffic locality of reference. One of our main contribution is that we identify the conditions network traffic must comply with for the theory to be applicable and then use the result to develop a model that predicts average cache miss rates. Furthermore, we study the model's suitability for long term cache provisioning and assess the cache's vulnerability in front of malicious users through an extension that accounts for cache polluting traffic. As a last step, we investigate the main sources of locality and their impact on the asymptotic scalability of the LISP cache. An important finding here is that destination popularity distribution can accurately describe cache performance, independent of the much harder to model short term correlations. Under a small set of assumptions, this result finally enables us to characterize asymptotic scalability with respect to the amount of prefixes (Internet growth) and users (growth of the LISP site). We validate the models and discuss the accuracy of our assumptions using several one-day-long packet traces collected at the egress points of a campus and an academic network. To show the added benefits that could drive LISP's adoption, in the second part of the thesis we investigate the possibilities of performing inter-domain multicast and improving intra-domain routing. Although the idea of using overlaid services to improve underlay performance is not new, this dissertation argues that LISP offers the right tools to reliably and easily implement such services due to its reliance on network instead of application layer support. In particular, we present and extensively evaluate Lcast, a network-layer single-source multicast framework designed to merge the robustness and efficiency of IP multicast with the configurability and low deployment cost of application-layer overlays. Additionally, we describe and evaluate LISP-MPS, an architecture capable of exploiting LISP to minimize intra-domain routing tables and ensure, among other, support for multi protocol switching and virtual networks. / En menos de cuatro décadas Internet ha evolucionado desde un experimento de laboratorio hasta una infraestructura de alcance mundial, de importancia crítica para negocios y que atiende a las necesidades de casi un tercio de los habitantes del planeta. Con estos números, es difícil tratar de negar la necesidad de escalabilidad de Internet. Sin embargo, el crecimiento orgánico de Internet está aún lejos de finalizar ya que se espera que mil millones de dispositivos nuevos se conecten en el futuro cercano. Así pues, la falta de escalabilidad es el mayor problema al que se enfrenta Internet hoy en día. Aunque la solución definitiva al problema está aún por definir, la necesidad de desacoplar semánticamente la localización e identidad de un nodo, a menudo llamada locator/identifier separation, es generalmente aceptada como un camino prometedor a seguir. Sin embargo, esto requiere la introducción de nuevos dispositivos en la red que unan los dos espacios de nombres disjuntos resultantes y de cachés que almacenen los enlaces temporales entre ellos con el fin de aumentar la velocidad de transmisión de los enrutadores. A raíz de esta complejidad añadida, la escalabilidad de la solución en si misma es también cuestionada. Este trabajo evalúa la idoneidad de utilizar Locator/ID Separation Protocol (LISP), una de las propuestas más exitosas que siguen la pauta locator/identity separation, como una solución para la escalabilidad de la Internet. Con tal fin, desarrollamos las herramientas analíticas para evaluar la escalabilidad del plano de control de LISP pero también para mostrar que la separación de los planos de control y datos proporciona un importante valor añadido que podría impulsar la adopción de LISP. Como primer paso para evaluar la escalabilidad de LISP, proponemos una metodología para un estudio analítico del rendimiento de la caché que se basa en la teoría del working-set para estimar la localidad de referencias. Identificamos las condiciones que el tráfico de red debe cumplir para que la teoría sea aplicable y luego desarrollamos un modelo que predice las tasas medias de fallos de caché con respecto a parámetros de tráfico fácilmente medibles. Por otra parte, para demostrar su versatilidad y para evaluar la vulnerabilidad de la caché frente a usuarios malintencionados, extendemos el modelo para considerar el rendimiento frente a tráfico generado por usuarios maliciosos. Como último paso, investigamos como usar la popularidad de los destinos para estimar el rendimiento de la caché, independientemente de las correlaciones a corto plazo. Bajo un pequeño conjunto de hipótesis conseguimos caracterizar la escalabilidad con respecto a la cantidad de prefijos (el crecimiento de Internet) y los usuarios (crecimiento del sitio LISP). Validamos los modelos y discutimos la exactitud de nuestras suposiciones utilizando varias trazas de paquetes reales. Para mostrar los beneficios adicionales que podrían impulsar la adopción de LISP, también investigamos las posibilidades de realizar multidifusión inter-dominio y la mejora del enrutamiento dentro del dominio. Aunque la idea de utilizar servicios superpuestos para mejorar el rendimiento de la capa subyacente no es nueva, esta tesis sostiene que LISP ofrece las herramientas adecuadas para poner en práctica de forma fiable y fácilmente este tipo de servicios debido a que LISP actúa en la capa de red y no en la capa de aplicación. En particular, presentamos y evaluamos extensamente Lcast, un marco de multidifusión con una sola fuente diseñado para combinar la robustez y eficiencia de la multidifusión IP con la capacidad de configuración y bajo coste de implementación de una capa superpuesta a nivel de aplicación. Además, describimos y evaluamos LISP-MPS, una arquitectura capaz de explotar LISP para minimizar las tablas de enrutamiento intra-dominio y garantizar, entre otras, soporte para conmutación multi-protocolo y redes virtuales.

Els convertidors commutats de potència són solucions apropiades per subministrar energia a dispositius electrònics per la seva elevada eficiència i reduït cost. El seu ús extensiu en les últimes dècades ha motivat els investigadors a millorar els seus dissenys i aprofundir en la comprensió del seu comportament el qual, com la majoria de dispositius electrònics de potència, presenta dinàmiques no lineals. Recentment, han aparegut equipaments electrònics que disposen de múltiples càrregues com són els PDA, telèfons mòbils, MP3... Freqüentment, aquestes aplicacions necessiten múltiples alimentacions amb doble polaritat. Els convertidors amb inductor únic i múltiples sortides, Single-Inductor Multiple-Input Multiple-Output (SIMIMO), han esdevingut solucions per subministrar energia a dispositius de baixa potència, com pantalles LCD, i per carregar bateries ja que l'ús d'un sol inductor redueix significativament la mida del convertidor. La inherent naturalesa commutada d'aquests sistemes classifica la seva dinàmica dins el camp de sistemes d'estructura variable, Variable Structure Systems (VSS), els quals també es coneixen com a sistemes suaus a trams, Piecewise Smooth (PWS) systems. Atès que la teoria clàssica per a sistemes suaus no pot explicar completament el seu comportament, en els últims anys s'han dirigit molts esforços cap a la recerca de les propietats de la dinàmica no suau en diferent camps d'aplicació. Aquesta tesi aprofundeix en la caracterització de convertidors SIMIMO, que ens permetrà provar la seva viabilitat. Es proposen dues estratègies de control basades en el conegut control PWM (Pulse Width Modulation). En la primera alternativa, el control ens permet regular un convertidor amb dues entrades i dues sortides (Two-Input Two-Output , SITITO), amb polaritats oposades. En aquest cas, les dues senyals moduladores necessàries són generades sincronitzadament i per aquest motiu, en aquesta tesi ens referirem a aquesta estratègia de control PWM com a SPC (Single Phase Control) en contraposició amb la segona alternativa, la qual serà anomenada IC (Interleaved Control), capaç de regular un número generalitzat de sortides. Aquest control està basat en l'ús de diverses senyals moduladores, tantes com a sortides, les quals s'han desfasat progressivament. La dinàmica dels convertidors SIMIMO, al igual que els convertidors bàsics contínua - contínua, exhibeix una rica varietat de fenòmens, els quals engloben des de bifurcacions suaus, com són les bifurcacions de doblament de període (period doubling bifurcation), Saddle-Node o Hopf, fins a bifurcacions no suaus. Un cop verificada l'existència de dinàmica estable quan els paràmetres s'han seleccionatapropiadament, aquesta tesi aborda la recerca de models amb els quals analitzar la complexa dinàmica dels convertidors en un rang ampli de paràmetres. Es proposen i analitzen alguns models que s'utilitzen complementàriament: els anomenats averaged models, amb els quals es pot analitzar la dinàmica lenta, i els models discrets, capaços de detectar les inestabilitats degudes a la dinàmica ràpida. A més a més, alguns d'aquest models seran definits i analitzats. La seva utilitat s'ha provat no només en la predicció de la estabilitat, sinó també en la caracterització de bifurcacions no suaus presents en el circuit. Es demostra que senzills sistemes lineals a trams de dimensió ú proporcionen expressions analítiques per a les condicions d'estabilitat y existència de punts fixos. Per finalitzar, es desenvolupen mapes de dimensió més elevada per tal d'incrementar la precisió de les prediccions obtingudes mitjançat els averaged models i els models discrets. L'anàlisi discreta del convertidor SITITO governat per cadascuna d'aquestes estratègies ha revelat que la dinàmica por ser modelada per un sistema lineal a trams en un rang específic de paràmetres. Fins on sabem, la bibliografia proporcionada sobre mapes PWL inclou tant mapes continus com discontinus, encara que limitats a dos trams. Per tant, aquesta tesi contribueix en el camp de la dinàmica no suau amb el desenvolupament de les propietats d'un mapa de tres trams. Respecte al control IC, s'ha obtingut una anàlisi general de la seva estabilitat per a un convertidor SIMIMO amb un nombre genèric de càrregues. L'estudi de l'estabilitat del model discret de dimensió ú ha revelat l'existència d'un tipus de bifurcació no suau la qual ha estat classificada con una non-smooth pitchfork atesa l'aparició de nous punts fixos després de produir-se la bifurcació. Una anàlisi més detallada de models discrets de dimensions més elevades, associa aquesta bifurcació a una Neimark-Sacker. Finalment, aquesta tesi també inclou alguns resultats experimentals obtinguts amb un prototip d'un convertidor SITITO, per tal de validar els escenaris trobats en l'anàlisi del comportament dinàmic del convertidor regulat per les dues estratègies de control. / Switching power converters are known to be appropriate solutions to supply energy to electronic devices owing to their high efficiency and low cost. Their extensive use in the last decades has motivated researches to improve their designs and to go deeply into the comprehension of their behavior which, like most power electronic devices, exhibit nonlinear dynamics. More recently, electronic equipments containing multiple loads have been arisen such as PDA, mobile phones, MP3... These applications frequently require multiple supplies with different polarities. Single-Inductor Multiple-Input Multiple-Output (SIMIMO) switching dc-dc converters are becoming as solutions to supply low power devices as LCD displays and to charge batteries due to the significant reduction of size because the use of a single inductor. The inherent switching nature of these systems classifies their dynamics into the field of Variable Structure Systems (VSS), which are also known as Piecewise Smooth (PWS) systems. Due to the fact that their dynamics cannot be completely explained with the classical smooth theory, in the last years a lot of effort has been addressed towards the research on a theory of non-smooth dynamics motivated by different fields of application. This dissertation deals with the dynamical characterization of SIMIMO converters, which can help us to prove their viability. Two strategies of control, both of them based on the widely used Pulse Width Modulation (PWM) control, are discussed. In the first alternative, the control is used to regulate a Two-Input Two-Output (SITITO) converter with opposite polarity. The two required modulate signals are generated synchronizely. This strategy of PWM control is called in this work Single Phase Control (SPC) in contrast to a second strategy, which is noted here as Interleaved Control (IC), capable of driving a generalized single inductor multiple-input multiple-output converters. This control is based on the use of various modulating signals, equal to the number of outputs, which are progressively time delayed. The dynamics of the SIMIMO converters, just like of the basic dc-dc converters, presents a rich variety of nonlinear phenomena, which covers from smooth bifurcations, such as period doubling, Saddle-Node or Hopf bifurcations, to non-smooth bifurcations. After proving the existence of stable dynamics if appropriate parameters are selected, this dissertation will deal with the investigation of models to analyze the complex dynamics of the converter in a wide range of parameters. Several models are proposed and analyzed in this work. Averaged models, from which slow scale instability condition can be determined, and discrete-time models, able to prove fast scale instabilities, are used in a complementary way. Besides this, several approaches of these models will be established and validated. Their usefulness will be proved not only in the prediction of the stability, but also in the characterization of the non-smooth bifurcations presents in this converter. It will be shown that simple one-dimensional Piecewise-Linear (PWL) models provide analytical expressions for the stability and existence conditions of fixed points of the discrete-time models. Furthermore, higher dimensional maps are developed to improve the accuracy of the predictions obtained by means of one-dimensional maps and averaged models. The discrete-time analysis of a SITITO converter driven by each of the two strategies of control has revealed that its dynamics can be modeled by a PWL with three trams in a specific range of parameters. To our best knowledge, the literature on PWL maps includes continuous and discontinuous maps but is limited to two trams. Therefore, this dissertation is a contribution in the field of non-smooth dynamics in base to the unfolding of specific dynamics of three-piece maps. Concerning the IC control, a generalized analysis of the stability is obtained for a SIMIMO converter with a generic number of loads. The stability analysis of the one-dimensional model has revealed the existence of a type of non-smooth bifurcation, which has been classified in this dissertation as a non-smooth pitchfork owing to the appearance of two new fixed points after undergoing the bifurcation. Detailed analysis in higher dimensional maps associates this bifurcation to a Neimark-Sacker, whose existence cannot be predicted by averaged models. This dissertation also includes some experimental results obtained with a SITITO dc-dc converter prototype, to validate some of the scenarios found in the analysis.

This thesis addresses the problem of visual object retrieval, where a user formulates a query to an image database by providing one or multiple examples of an object of interest. The presented techniques aim both at finding those images in the database that contain the object as well as locating the object in the image and segmenting it from the background. Every considered image, both the ones used as queries and the ones contained in the target database, is represented as a Binary Partition Tree (BPT), the hierarchy of regions previously proposed by Salembier and Garrido (2000). This data structure offers multiple opportunities and challenges when applied to the object retrieval problem. A first application of BPTs appears during the formulation of the query, when the user must interactively segment the query object from the background. Firstly, the BPT can assist in adjusting an initial marker, such as a scribble or bounding box, to the object contours. Secondly, BPT can also define a navigation path for the user to adjust an initial selection to the appropriate spatial scale. The hierarchical structure of the BPT is also exploited to extract a new type of visual words named Hierarchical Bag of Regions (HBoR). Each region defined in the BPT is described with a feature vector that combines a soft quantization on a visual codebook with an efficient bottom-up computation through the BPT. These descriptors allow the definition of a novel feature space, the Parts Space, where each object is located according to the parts that compose it. HBoR descriptors have been applied to two scenarios for object retrieval, both of them solved by considering the decomposition of the objects in parts. In the first scenario, the query is formulated with a single object exemplar which is to be matched with each BPT in the target database. The matching problem is solved in two stages: an initial top-down one that assumes that the hierarchy from the query is respected in the target BPT, and a second bottom-up one that relaxes this condition and considers region merges which are not in the target BPT. The second scenario where HBoR descriptors are applied considers a query composed of several visual objects. In this case, the provided exemplars are considered as a training set to build a model of the query concept. This model is composed of two levels, a first one where each part is modelled and detected separately, and a second one that characterises the combinations of parts that describe the complete object. The analysis process exploits the hierarchical nature of the BPT by using a novel classifier that drives an efficient top-down analysis of the target BPTs.

Esta tesis está enfocada en el diseño, simulación, fabricación y caracterización de sensores de masa basados en microcantilevers de silicio. Los cantilevers con forma de T son diseñados como estructuras formadas por 3 vigas unidas en su extremo por medio de una masa rectangular extra. Los cantilevers son excitados para alcanzar su resonancia mecánica, en modo flexión perpendicular al sustrato, con un piezoactuador PZT pegado en la parte posterior del sustrato y la frecuencia de resonancia es monitoreada por cuatro piezoresistencias configuradas en un puente de Wheastone. Diversos cantilever son fabricados variando su proceso de fabricación, dimensiones y geometrías, su operación es verificada y su desempeño mecánico y eléctrico evaluado. El desempeño del dispositivo es comparado con los valores obtenidos del modelo analítico y de las simulaciones con ANSYS, obteniendo buena concordancia. Se seleccionan las dos estructuras con los mayores valores de frecuencia de resonancia y factor de calidad. Para el primer cantilever, de 400μm de largo, 300μm ancho y 15μm de espesor, la frecuencia de resonancia, del primer y segundo modo de vibración, se encuentra en 97kHz y 690kHz respectivamente, ambos con un factor de calidad de ~800. Para el segundo cantilever, de 200μm de largo, 150μm ancho y 15μm de espesor, la frecuencia de resonancia fundamental se encuentra en 400kHz con un factor de calidad de ~900. Los dispositivos son caracterizados como sensores de masa al adherir microesferas de poliestireno a la superficie del cantilever y medir los cambios en la frecuencia. Para el primer cantilever, los valores de sensibilidad de masa son: 12,4pg/Hz y 3,1pg/Hz para el primer y el segundo modo respectivamente y 0,8pg/Hz para el segundo cantilever. Además, los cantilevers son caracterizados como sensores de gas al recubrir su superficie con PDMS, exponerlos a vapor de etanol y medir los cambios en la frecuencia. Para la primera y segunda estructura, el valor de sensibilidad al etanol es de 13,2ppm/Hz y 0,6ppm/Hz respectivamente. Estos resultados ilustran el alto potencial para utilizar estas sencillas estructuras como plataforma en aplicaciones sensitivas. / This work has been focused on the design, simulation, fabrication and characterization of silicon microcantilevers based mass sensors. The T-shape cantilever was designed as a structure formed by 3 cantilevers that are hold together by means of an extra rectangular mass. Cantilevers were driven at their mechanical resonance in flexural mode perpendicular to the substrate by a ceramic-insulated multilayer piezoactuator PZT glued at the backside and the resonance frequency was monitored by reading the signal generated by four piezoresistors in a Wheatstone bridge configuration. Several cantilevers structures have been fabricated with different process, dimensions and geometries, its operation verified and their mechanical and electrical performance evaluated. Device performance was compared with analytical model and simulation predictions obtained using ANSYS achieving good agreement. Two different structures were selected based on the high resonance frequency and quality factor values. For the first cantilever of 400μm long, 300μm wide and 15μm thick, the fundamental and second resonance frequency in air were 97kHz and 690kHz respectively, both with a quality factor of ~800. And for the second cantilever of 200μm long, 150μm wide, 15μm thick the fundamental resonance frequency in air was 400kHz with a quality factor of ~900. The devices were characterized as mass sensor attaching microspheres of polystyrene to the cantilever’s surface tip and measuring resonance frequency changes. For the first cantilever mass sensitivity values of 12,4pg/Hz and 3,1pg/Hz for the fundamental and second mode respectively were achieved and 0,8pg/Hz for the second cantilever. Also the cantilevers were characterized as gas sensor, covering the cantilever’s surface tip with PDMS, exposing it to ethanol vapor and measuring resonance frequency changes. For the first cantilever ethanol sensitivity values of 13,2ppm/Hz were achieved and 0,6ppm/Hz for the second cantilever. These results show the great potential for high sensitive sensor of this simple device.

No description available.